(57)【特許請求の範囲】
【請求項１】
データシンボルに対する算術デコーディングを遂行する方法であって、
デコーディングテーブルインデックスを生成するステップと、
ＲＯＭに格納されたデコーディングテーブルからシンボルに割り当てられた区間内の地点と区間長さとの間の割合（Ｄk／Ｌk）の上位境界値（Ｅｍａｘ）及び下位境界値（Ｅｍｉｎ）を獲得するステップと、
前記上位境界値及び前記下位境界値に基づいて、ＲＡＭに格納されたデコーディングテーブルからバイセクション（ｂｉｓｅｃｔｉｏｎ）探索のための初期値を獲得するステップと、
前記区間内でシーケンス値を探索するステップと、
前記シーケンス値に対応する前記データシンボルをデコーディングするステップとを含み、
前記デコーディングテーブルインデックスは、前記区間長さの最上位ビットと、前記シンボルに割り当てられた前記区間内の前記地点の最上位ビットとを結合することにより生成され、
前記区間は、前記初期値に基づいて決定される、方法。
【請求項２】
前記区間長さの最上位１ビットの位置を決定するステップと、
前記位置に１ビットを加えた位置から始めて前記最上位１ビットの以後の前記区間長さの最上位ビットを抽出するステップと、
前記位置から始めて前記地点の前記最上位ビットを抽出するステップと、の後に、前記生成するステップが実行される、請求項１に記載の方法。
【請求項３】
前記上位境界値は、前記シンボルに割り当てられた前記区間内の地点の最大値と前記区間長さの最小値との割合に基づいて決定される、請求項１に記載の方法。
【請求項４】
前記下位境界値は、前記シンボルに割り当てられた前記区間内の地点の最小値と前記区間長さの最大値との割合に基づいて決定される、請求項１に記載の方法。
【請求項５】
前記上位境界値及び前記下位境界値は、掛け算近似に対応するビットシフトに基づいて決定される、請求項１に記載の方法。
【請求項６】
データシンボルに対する算術デコーディングを遂行する装置であって、
デコーディングテーブルインデックスを生成するように構成されたインデックス生成ユニットと、
ＲＯＭに格納されたデコーディングテーブルからシンボルに割り当てられた区間内の地点と区間長さとの割合の上位境界値及び下位境界値を獲得し、前記上位境界値及び前記下位境界値に基づいて、ＲＡＭに格納されたデコーディングテーブルからバイセクション（ｂｉｓｅｃｔｉｏｎ）探索のための初期値を獲得するように構成された連結されたＲＯＭ−ＲＡＭテーブルユニットと、
前記区間内でシーケンス値を探索するように構成されたバイセクション探索ユニットと、
前記シーケンス値に対応する前記データシンボルをデコードするように構成されたエントロピーデコーディングユニットとを含み、
前記エントロピーデコーディングユニットは、前記インデックス生成ユニットと、前記ＲＯＭ−ＲＡＭテーブルユニットと、前記バイセクション探索ユニットとを備え、
前記デコーディングテーブルインデックスは、前記区間長さの最上位ビットと、前記シンボルに割り当てられた前記区間内の前記地点の最上位ビットとを結合することにより生成され、
前記区間は、前記初期値に基づいて決定される、装置。
【請求項７】
前記インデックス生成ユニットは、
前記区間長さの最上位１ビットの位置を決定し、
前記位置に１ビットを加えた位置から始めて前記最上位１ビットの以後の前記区間長さの最上位ビットを抽出し、
前記位置から始めて前記地点の最上位ビットを抽出するように構成された、請求項６に記載の装置。
【請求項８】
前記上位境界値は、前記地点の最大値と前記区間長さの最小値との割合に基づいて決定される、請求項６に記載の装置。
【請求項９】
前記下位境界値は、前記地点の最小値と前記区間長さの最大値との割合に基づいて決定される、請求項６に記載の装置。
【請求項１０】
前記上位境界値及び前記下位境界値は、掛け算近似に対応するビットシフトに基づいて決定される、請求項６に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はビデオ信号を処理するための方法及び装置に関し、より詳しくは、連結された（ｃｏｎｃａｔｅｎａｔｅｄ）ＲＯＭ−ＲＡＭテーブルに基づいて算術コーディングを遂行する技術に関する。
【背景技術】
【０００２】
エントロピーコーディングは圧縮されたデータシーケンスに挿入されるビットの数を最適に定義するために使われる過程である。したがって、この過程は如何なる種類のデータ及びメディア圧縮においても基本技術となり、最終の圧縮効率及び演算の複雑度に大きな影響を及ぼす。算術コーディングは最適のエントロピーコーディング技術であって、相対的に高い複雑度を有するが、最近広く採択されており、Ｈ．２６４／ＡＶＣ、Ｈ．２６５／ＨＥＶＣ、ＶＰ８、及びＶＰ９ビデオコーディング規格の一部となった。しかしながら、ＵＨＤ及び高フレーム割合ビデオのような応用分野での非常に高度に圧縮されたデータ処理率に対する損傷が増加するにつれて、新たな形態の速いエントロピーコーディングが必要となった。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
二進化のためにはコーディングされる全てのデータが順次に分解されなければならないという問題があり、これによってクロック速度の高い時にのみ早く遂行できる。
【０００４】
狭いレジスタが精度の損失を避けるために、個別データビットをできる限り速く抽出することを必要とし、これによって直列化の形態を取らざるを得ない。そして、複雑な掛け算近似が直列化された形態に定義され、速い掛け算は非常に値高いシステムを要するという問題がある。
【０００５】
また、コーディング機器がバイセクション（ｂｉｓｅｃｔｉｏｎ）や更に他の形態の二進木探索を使用する場合、デコーディング過程を二進決定で順次的分解するようになり、コーディングシステムが二進算術コーディングの速度に対する相当な改善をもたらさないという問題がある。
【０００６】
また、算術コーディングでシンボルに対する情報がビットに対して直接的に定義されず、要素ＤkとＬkとの間の割合で定義される問題がある。
【課題を解決するための手段】
【０００７】
本発明の一実施形態は、テーブル索引（ｌｏｏｋｕｐ）を使用して算術コーディングの処理率を増加させる方法を提供する。
【０００８】
また、本発明の一実施形態は、連結されたＲＯＭ−ＲＡＭテーブル索引を有するデコーダを提供する。
【０００９】
また、本発明の一実施形態は、ＲＡＭ基盤テーブルを大きくて高くないＲＯＭテーブルとより小さなＲＡＭテーブルの連結された形態に取り替える方法を提供する。
【００１０】
また、本発明の一実施形態は、分割近似のためにテーブル索引を活用する方法を提供する。
【発明の効果】
【００１１】
本発明によれば、テーブル索引を使用することによって、算術コーディングの処理率が増加できる。
【００１２】
また、本発明によれば、連結されたＲＯＭ−ＲＡＭテーブル索引を有するデコーダは、圧縮効率及び演算の複雑度を向上させることができる。
【００１３】
また、本発明によれば、連結されたＲＯＭ−ＲＡＭテーブル索引を有するデコーダは、算術コーディングの如何なる形態にも適用できる。
【００１４】
また、本発明によれば、連結されたＲＯＭ−ＲＡＭテーブル索引を有するデコーダは、非常に速いデコーディングを可能にする。
【図面の簡単な説明】
【００１５】
【図１】本発明が適用される一実施形態であって、ビデオ信号を処理するエンコーダ及びデコーダの概略的なブロック図を図示する。
【図２】本発明が適用される一実施形態であって、ビデオ信号を処理するエンコーダ及びデコーダの概略的なブロック図を図示する。
【図３】本発明が適用される一実施形態であって、算術コーディング区間データをアップデートするために必要とする演算集合を例示するフローチャートである。
【図４】本発明が適用される一実施形態であって、二進算術コーディングに基づいてビデオ信号を処理するエンコーダ及びデコーダの概略的ブロック図を示す。
【図５】本発明が適用される一実施形態であって、二進算術コーディングに基づいてビデオ信号を処理するエンコーダ及びデコーダの概略的ブロック図を示す。
【図６】本発明が適用される一実施形態であって、大容量データアルファベット（ｌａｒｇｅ  ｄａｔａ  ａｌｐｈａｂｅｔ）及び長いレジスタ（ｌｏｎｇ  ｒｅｇｉｓｔｅｒ）を使用して設計された算術コーディングシステムのエンコーダ及びデコーダの概略的なブロック図を示す。
【図７】本発明が適用される一実施形態であって、大容量データアルファベット（ｌａｒｇｅ  ｄａｔａ  ａｌｐｈａｂｅｔ）及び長いレジスタ（ｌｏｎｇ  ｒｅｇｉｓｔｅｒ）を使用して設計された算術コーディングシステムのエンコーダ及びデコーダの概略的なブロック図を示す。
【図８】本発明が適用される一実施形態であって、Ｐビットレジスタ上にＤk及びＬkの二進表現ダイヤグラムを示す。
【図９】本発明が適用される一実施形態であって、連結されたＲＯＭ−ＲＡＭテーブルを含む算術デコーダの概略的なブロック図を示す。
【図１０】本発明が適用される一実施形態であって、データシンボルをデコーディングする方法を例示するフローチャートである。
【図１１】本発明が適用される一実施形態であって、連結されたＲＯＭ−ＲＡＭテーブルを使用して算術デコーディングを遂行する方法を例示するフローチャートである。
【発明を実施するための形態】
【００１６】
本発明はデータシンボルに対する算術デコーディングを遂行する方法であって、デコーディングテーブルインデックスを生成するステップと、ＲＯＭテーブルからシンボルに割り当てられた区間内の地点と区間長さとの間の割合の上位境界値及び下位境界値を獲得するステップと、前記上位境界値及び前記下位境界値に基づいて、ＲＡＭテーブルからバイセクション探索のための初期値を獲得するステップと、区間内でシーケンス値を探索するステップとを含み、前記区間は、前記初期値に基づいて決定されることを特徴とする、方法を提供する。
【００１７】
本発明は、前記区間長さの最上位１ビットの位置を決定するステップと、前記位置に１ビットを加えた位置から始めて前記最上位１ビットの以後の前記区間長さの最上位ビットを抽出するステップと、前記位置から始めて前記区間ベースの最上位ビットを抽出するステップとをさらに含むことを特徴とする。
【００１８】
本発明は、前記区間長さの最上位ビットとシンボルに割り当てられた区間内の前記地点の最上位ビットとを結合することによって、デコーディングテーブルインデックスを生成するステップをさらに含むことを特徴とする。
【００１９】
本発明において、前記上位境界値は、シンボルに割り当てられた区間内の地点の最大値と前記区間長さの最小値との間の割合に基づいて決定されることを特徴とする。
【００２０】
本発明において、前記下位境界値は、シンボルに割り当てられた区間内の地点の最小値と前記区間長さの最大値との間の割合に基づいて決定されることを特徴とする。
【００２１】
本発明において、前記上位境界値及び前記下位境界値は、掛け算近似に対応するビットシフト演算に基づいて決定されることを特徴とする。
【００２２】
本発明は、データシンボルに対する算術デコーディングを遂行する装置において、デコーディングテーブルインデックスを生成するように構成されたインデックス生成ユニットと、ＲＯＭテーブルからシンボルに割り当てられた区間内の地点と区間長さとの間の割合の上位境界値及び下位境界値を獲得し、前記上位境界値及び前記下位境界値に基づいて、ＲＡＭテーブルからバイセクション（ｂｉｓｅｃｔｉｏｎ）探索のための初期値を獲得するように構成された連結されたＲＯＭ−ＲＡＭテーブルユニットと、区間内でシーケンス値を探索するように構成されたバイセクション探索ユニットとを含み、前記区間は、前記初期値に基づいて決定されることを特徴とする、装置を提供する。
【００２３】
以下、添付の図面を参照して本発明の実施形態の構成及びその作用を説明し、図面により説明される本発明の構成及び作用は１つの実施形態として説明されるものであり、これによって本発明の技術的思想とその核心構成及び作用が制限されるものではない。
【００２４】
併せて、本発明で使われる用語はできる限り現在広く使われる一般的な用語を選択したが、特定の場合は出願人が任意に選定した用語を使用して説明する。そのような場合には該当部分の詳細説明でその意味を明確に記載するので、本発明の説明で使われた用語の名称だけで単純解析されてはならず、その該当用語の意味まで把握して解析されるべきであることを明らかにする。
【００２５】
また、本発明で使われる用語は発明を説明するために選択された一般的な用語であるが、類似の意味を有する他の用語がある場合、より適切な解析のために代替可能である。例えば、信号、データ、サンプル、ピクチュア、フレーム、ブロックなどの場合、各コーディング過程で適切に代替されて解析できるものである。また、範囲、長さ、区間（または、コーディング区間、算術コーディング区間）、及び区間長さは、各々の算術コーディング過程で適切に代替されて解析できるものである。
【００２６】
図１及び図２は、本発明が適用される一実施形態であって、ビデオ信号を処理するエンコーダ及びデコーダの概略的なブロック図を示す。
【００２７】
図１のエンコーダ１００は、変換ユニット１１０、量子化ユニット１２０、及びエントロピーエンコーディングユニット１３０を含む。図２のデコーダ２００は、エントロピーデコーディングユニット２１０、逆量子化ユニット２２０、及び逆変換ユニット２３０を含む。
【００２８】
前記エンコーダ１００は、ビデオ信号を受信して前記ビデオ信号から予測された信号を差し引きすることによって予測エラーを生成する。
【００２９】
生成された前記予測エラーは、変換ユニット１１０に転送される。前記変換ユニット１１０は予測エラーに変換方式を適用することによって、変換係数を生成する。
【００３０】
前記量子化ユニット１２０は、前記生成された変換係数を量子化して前記量子化された係数をエントロピーエンコーディングユニット１３０に転送する。
【００３１】
前記エントロピーエンコーディングユニット１３０は、前記量子化された係数に対するエントロピーコーディングを遂行し、エントロピーコーディングされた信号を出力する。この場合、前記エントロピーコーディングは、圧縮されたデータシーケンスに入るビットの個数を最適に定義するために使われる過程である。最適のエントロピーコーディング技術のうちの１つである算術コーディングは、多重シンボルを単一の実数で示す方法である。
【００３２】
本発明はテーブル索引を使用することによって、また、より特定的には、ＲＡＭ基盤テーブルを連続して大きくて高くないＲＯＭテーブル及びより小さなＲＡＭテーブルに取り替えることによって、算術コーディング技術の処理率（秒当たり処理されるビット）を向上させる方法上の改善を定義する。
【００３３】
本発明の一側面で、前記エントロピーエンコーディングユニット１３０は、各々のデータシンボルに対して掛け算近似を使用して区間をアップデートし、ビットシフト演算及びアップデートされた区間内での足し算を使用して掛け算結果に対する掛け算近似を計算することができる。
【００３４】
前記計算過程で、前記エントロピーエンコーディングユニット１３０は、長さの最上位１ビットの位置を決定することができ、近似した長さを獲得するために前記最上位１ビットの以後の長さの最上位ビットのうちの一部を抽出することができる。このような場合に、前記区間は近似した長さ及び掛け算結果の結果として示されるビットに基づいてアップデートされる。
【００３５】
図２のデコーダ２００は、図１のエンコーダ１００により出力された信号を受信する。
【００３６】
前記エントロピーデコーディングユニット２１０は、受信された信号に対するエントロピーデコーディングを遂行することができる。例えば、前記エントロピーデコーディングユニット２１０は、コード値の位置情報を含む信号を受信し、前記コード値の位置情報に対応するシンボルを確認し、確認されたシンボルをデコーディングすることができる。
【００３７】
本発明の更に他の側面で、前記エントロピーデコーディングユニット２１０は、区間長さの最上位ビットとコード値の最上位ビットを結合することによって、デコーディングテーブルインデックスを生成することができる。
【００３８】
このような場合に、区間長さの最上位ビットは前記最上位１ビットの以後に前記位置に１ビットを加えた地点から出発して抽出されることができ、前記コード値の最上位ビットは区間長さの最上位１ビットの位置から出発して抽出できる。
【００３９】
一方、前記逆量子化ユニット２２０は前記エントロピーデコーディングされた信号から量子化ステップの大きさに対する情報に基づいて変換係数を獲得する。
【００４０】
前記逆変換ユニット２３０は、前記変換係数に対する逆変換を遂行することによって、予測エラーを獲得する。前記予測エラーを予測信号に加えることによって、復元された信号が生成される。
【００４１】
図３は本発明が適用される一実施形態であって、算術コーディング区間データをアップデートするために必要な演算集合を例示するフローチャートである。
【００４２】
本発明が適用される算術コーディング器は、データソースユニット３１０、データモデリングユニット３２０、１次遅延ユニット３３０、及び２次遅延ユニット３４０を含むことができる。
【００４３】
前記データソースユニット３１０は、次の＜数式１＞のようにＭ個のシンボルのアルファベットから各々Ｎ個のランダムなシンボルのシーケンスを生成することができる。
【００４４】
【数１】
0006509916.tif 000002
【００４５】
この場合、本発明は前記データシンボルが次の＜数式２＞のように０でない確率を有しながら全て独立的で、かつ同一に分布したものとして仮定する。
【００４６】
【数２】
0006509916.tif 000003
【００４７】
また、本発明は次の＜数式３＞のように累積確率分布を定義することができる。
【００４８】
【数３】
0006509916.tif 000004
【００４９】
この場合、ｃ（ｓ）は厳格に単調的（ｍｏｎｏｔｏｎｉｃ）であり、ｃ（０）＝０で、ｃ（Ｍ）＝１である。
【００５０】
このような条件が実際の複雑な媒体信号で発見されるものと大きく異なるものと見えることもできるが、事実相、全てのエントロピーコーディング道具がこのような仮定から導出された技術に基づいており、したがって、本発明はこのような単純なモデルに制限された具現を提供することができる。
【００５１】
算術コーディングは主に実数直線上の［ｂk、ｂk＋ｌk］形態の半開区間をアップデートするステップで構成され、この際、ｂkは区間ベースを示し、ｌkはその長さを示す。これら区間は各々のデータシンボルｓkによってアップデートされ、初期条件ｂ１＝０及びｌ１＝１から始まって次の＜数式４＞及び＜数式５＞を使用してｋ＝１，２，．．．Ｎに対して再帰的にアップデートされる。
【００５２】
【数４】
0006509916.tif 000005
【００５３】
【数５】
0006509916.tif 000006
【００５４】
この場合、前記区間は次の＜数式６＞のように徐々に内部に含まれることができる。
【００５５】
【数６】
0006509916.tif 000007
【００５６】
前記説明したように、図３を参照すると、前記データモデリングユニット３２０はＮ個のランダムなシンボルＳkのシーケンスを受信することができ、前記累積確率分布Ｃ（Ｓk）及びシンボル確率ｐ（Ｓk）を出力することができる。
【００５７】
区間長さｌk+1はデータモデリングユニット３２０から出力されたＳk及び１次遅延ユニット３３０から出力されたｌkの掛け算演算により獲得できる。
【００５８】
また、前記区間ベースｂk+1は２次遅延ユニット３４０から出力されたｂkの足し算演算及びＣ（Ｓk）とｌkの掛け算から獲得できる。
【００５９】
本発明が適用される算術コーディングは、掛け算と足し算の算術演算で定義できる。この場合、ｂk及びｌkは無限精度（ｉｎｆｉｎｉｔｅ  ｐｒｅｃｉｓｉｏｎ）で示すことができるが、これははじめに直観的に簡単なバージョンで表現を導入するために使われる。以後、本発明は有限精度（ｆｉｎｉｔｅ  ｐｒｅｃｉｓｉｏｎ）動作を使用して算術コーディングを近似するように具現する方法を提供する。
【００６０】
【表１】
0006509916.tif 000008
【００６１】
【表２】
0006509916.tif 000009
【００６２】
【数７】
0006509916.tif 000010
【００６３】
【数８】
0006509916.tif 000011
【００６４】
【数９】
0006509916.tif 000012
【００６５】
【表３】
0006509916.tif 000013
【００６６】
実際的な算術コーディングの具現のために、本発明は全ての足し算が無限精度で遂行されるが、掛け算は有限精度を使用して一部の特性が保存されるように近似するという事実を考慮することができる。本明細書では、本発明の理解のために必要な内容のみを扱う。例えば、区間再正規化は本発明を説明するに当たって必要な部分であるが、これは本発明に影響を及ぼさないので、本明細書で説明されない。
【００６７】
【表４】
0006509916.tif 000014
【００６８】
【数１０】
0006509916.tif 000015
【００６９】
【数１１】
0006509916.tif 000016
【００７０】
この場合、掛け算値を囲む二重大括弧（ｄｏｕｂｌｅ  ｂｒａｃｋｅｔｓ）は前記掛け算が有限精度近似（ｆｉｎｉｔｅ  ｐｒｅｃｉｓｉｏｎ  ａｐｐｒｏｘｉｍａｔｉｏｎｓ）によるものであることを示す。
【００７１】
【表５】
0006509916.tif 000017
であるので、前記＜数式１０＞は＜数式４＞に対応する。
【００７２】
したがって、前記デコーディング過程は次の＜数式１２＞から＜数式１４＞のように定義できる。
【００７３】
【数１２】
0006509916.tif 000018
【００７４】
【数１３】
0006509916.tif 000019
【００７５】
【数１４】
0006509916.tif 000020
【００７６】
算術デコーディングの重要な側面のうちの１つは、一部の非常に簡単な場合を除いて、＜数式７＞からｓkを直接的に探し出す方法がないし、一部の類型の探索が必要であるということである。例えば、ｃ（ｓ）は厳格に単調的であるので、本発明はバイセクション探索を使用することができ、ｓkを０（ｌｏｇ2Ｍ）回のテストにより探すことができる。これは、平均的探索性能もシンボル確率の分布を用いる探索技術を使用することによって改善できる。
【００７７】
図４及び図５は本発明が適用される一実施形態であって、二進算術コーディングに基づいてビデオ信号を処理するエンコーダ及びデコーダの概略的ブロック図を示す。
【００７８】
本発明が適用された算術コーディングの具現は、次のような要素に基づくことができる。
【００７９】
第１に、掛け算のような算術演算は相対的に費用が高くて、これら演算は概略的近似及びテーブル索引方式に取り替えることができる。
【００８０】
第２に、掛け算結果を除去するとしても、本発明は中間結果及び足し算を維持するためにプロセッサレジスタを必要とすることができる。より簡単なハードウェア具現のために、８または１６ビットだけのレジスタが利用できる。
【００８１】
第３に、デコーダは＜数式１２＞の探索を具現しなければならないので、エンコーダに比べて非常に遅いことがあり、このような複雑度はアルファベット大きさＭが大きくなるほど増加する。
【００８２】
このような問題点を全て解決したコーディングの一形態が二進算術コーディングであり、これは二進入力アルファベット（即ち、Ｍ＝２）のみに適用された。如何なるアルファベットからのデータシンボルも二進シンボルのシーケンスに変換（二進化）できるので、これは実際的に根本的な制限ではない。図４及び図５は、このような類型のコーディングを具現するエンコーダとデコーダを各々示す。
【００８３】
前記エンコーダ４００は、二進化ユニット４１０、遅延ユニット４２０、確率推定ユニット４３０、及びエントロピーエンコーディングユニット４４０を含む。また、前記デコーダ５００は、エントロピーデコーディングユニット５１０、遅延ユニット５２０、確率推定ユニット５３０、及び集積ユニット５４０を含む。
【００８４】
前記二進化ユニット４１０は、データシンボルのシーケンスを受信し、二進化を遂行することによって、二進化された値０または１で構成された二進データストリングを出力することができる。前記出力された二進データストリングは、遅延ユニット４２０を通じて確率推定ユニット４３０に転送される。前記確率推定ユニット４３０は、エントロピー−エンコーディングのための確率推定を遂行する。
【００８５】
前記エントロピーエンコーディングユニット４４０は、出力されたビットストリング及び出力された圧縮データビットに対するエントロピーエンコーディングを遂行する。
【００８６】
前記デコーダ５００は、前記エンコーディング過程を逆に遂行することができる。
【００８７】
しかしながら、図４及び図５のコーディングシステムは、次のような問題を有することができる。
【００８８】
まず、二進化のためにはコーディングされる全てのデータが順次に分解されなければならず、これによってクロック速度が高い時のみに早く遂行できる。そして、狭いレジスタ（ｎａｒｒｏｗ  ｒｅｇｉｓｔｅｒｓ）が精度の損失を避けるために、個別データビットをできる限り速く抽出することを必要とし、これによって直列化の形態を取らざるを得ない。
【００８９】
本発明が解決しようとする部分は、＜数式１２＞を用いるｓkの探索における複雑度である。コーディングシステムがバイセクションまたは更に他の形態の二進木探索を使用する場合、前記コーディングシステムはデコーディング過程を二進決定に順次に分解しなければならない問題を有することができ、これは二進算術コーディングの速度に対する相当な改善をもたらさない。
【００９０】
したがって、本発明は如何なる形態の算術コーディングにも適用できるシステムを提案しようとし、これは図６及び図７のエンコーダ及びデコーダを通じて説明する。
【００９１】
図６及び図７は本発明が適用される一実施形態であって、大容量データアルファベット（ｌａｒｇｅ  ｄａｔａ  ａｌｐｈａｂｅｔ）及び長いレジスタ（ｌｏｎｇ  ｒｅｇｉｓｔｅｒ）を使用して設計された算術コーディングシステムのエンコーダ及びデコーダの概略的なブロック図を示す。
【００９２】
図６及び図７を参照すると、前記エンコーダ６００は、遅延ユニット６２０、確率推定ユニット６３０、及びエントロピーエンコーディングユニット６４０を含む。また、前記デコーダ７００は、エントロピーデコーディングユニット７１０、遅延ユニット７２０、及び確率推定ユニット７３０を含む。ここで、前記エントロピーエンコーディングユニット６４０は大容量のデータアルファベット（ｌａｒｇｅ  ｄａｔａ  ａｌｐｈａｂｅｔ）を直接受信して、大容量のデータアルファベット及び長いレジスタ（ｌｏｎｇ  ｒｅｇｉｓｔｅｒ）に基づいて二進ワード（ｂｉｎａｒｙ  ｗｏｒｄ）の圧縮されたデータを生成することができる。
【００９３】
データシンボルに対する算術コーディングのために、まずエントロピーエンコーディングユニット６４０が各々のデータシンボルに対する区間を生成することができる。このような場合に、前記区間は開始地点及び区間の長さに基づいて表現できる。
【００９４】
前記エントロピーエンコーディングユニット６４０は、掛け算近似を使用して各々のデータシンボルに対して区間をアップデートすることができる。このような場合に、前記掛け算結果に対する掛け算近似は、負数を含む因子（ｆａｃｔｏｒ）の最適化により遂行できる。また、掛け算結果に対する掛け算近似の大きさがレジスタビットの個数に調整できる。
【００９５】
この後、前記エントロピーエンコーディングユニット６４０は、ビットシフト演算及び前記アップデートされた区間内での足し算を使用して掛け算結果の掛け算近似を計算することができる。このような場合、前記エンコーダは長さの最上位１ビットの位置を決定し、近似化された長さを獲得するために前記最上位１ビットの以後に長さの上位ビットのうちの一部を抽出することができる。前記区間は、前記近似化した長さ及び結果的に示される掛け算結果のビットに基づいてアップデートできる。
【００９６】
前記過程を通じて大容量データアルファベット（ｌａｒｇｅ  ｄａｔａ  ａｌｐｈａｂｅｔ）と長いレジスタ（ｌｏｎｇ  ｒｅｇｉｓｔｅｒ）を使用することによって、算術コーディングの毎秒当たり処理されたビットが増加できる。
【００９７】
また、図４及び図５の説明は、前記エンコーダ６００及び前記デコーダ７００の機能ユニットに適用できる。
【００９８】
図８は本発明が適用される一実施形態であって、Ｐビットレジスタ上にＤk及びＬkの二進表現ダイヤグラムを示す。
【００９９】
本発明において、ハフマン（Ｈｕｆｆｍａｎ）コードのデコーディングを加速させるために使用する方式のうちの１つは、テーブル索引を使用するものである。即ち、１回に１つのビットを読んで、新たなコードツリーに移動する代わり、多数のビットを読んで、読まれたビットは既に算術されたテーブルのインデックスを生成するために用いられる。ハフマンコードは、コーディングされたシンボルに対して整数個のビットを生成することによって、読まれる次のビットの集合を容易に定義することができる。しかしながら、このような内容は算術コーディングには適合しないことがある。
【０１００】
算術コーディングは、シンボルに対する情報がビットに対して定義されず、ＤkとＬkとの間の割合として定義できる。
【０１０１】
本発明は、Ｄkを正規化するために割算を使用することができる。
【０１０２】
【数１５】
0006509916.tif 000021
【０１０３】
【数１６】
0006509916.tif 000022
【０１０４】
＜数式１５＞で、Ｅは分数Ｄk／Ｌkの量子化されたバージョンである。本発明は、＜数式１５＞のＥから＜数式１６＞のバイセクション探索（ｂｉｓｅｃｔｉｏｎ  ｓｅａｒｃｈ）のための初期値を探すことができ、これはＫt個の元素を有するテーブルに格納されることができ、より速いデコーディングを可能にする。前記テーブル項目は以下の数式により決定できる。
【０１０５】
【数１７】
0006509916.tif 000023
【０１０６】
【数１８】
0006509916.tif 000024
【０１０７】
【表６】
0006509916.tif 000025
であるので、デコーディングを矯正するために１つのテーブルであれば充分である。前記‘１つのテーブル’は周期的にアップデートされるＲＡＭに格納されなければならないので、ＲＡＭテーブルとして定義できる。また、テーブル索引はバイセクション探索（ｂｉｓｅｃｔｉｏｎ  ｓｅａｒｃｈ）を初期化するためのものであるので、モデルがアップデートされる度にテーブルを計算するオーバーヘッドは小さいことがある。
【０１０８】
テーブル索引デコーディング（ｔａｂｌｅ  ｌｏｏｋ−ｕｐ  ｄｅｃｏｄｉｎｇ）での制限事項（ｃｏｎｓｔｒａｉｎｔ）は低い複雑度のハードウェアプラットフォームで割算が３２ビットレジスタを使用するとしても高いということである。
【０１０９】
したがって、本発明はテーブル基盤デコーディング方法を提案し、具体的に割算近似のためにテーブル索引を使用する方法を提供する。本発明は、テーブルインデックスを生成するためにＤk及びＬkから抽出される特別な部分集合を定義することができる。ここで、前記テーブルインデックスは追加的な探索を必要とするシンボルの範囲を知らせるテーブル要素を含むことができる。
【０１１０】
以下、本発明の一実施形態であるテーブルインデックス及び項目を生成する方法を説明する。
【０１１１】
次の＜数式１９＞に基づいて、本発明はＤk及びＬkの割合が０でない最上位ビット（ｍｏｓｔ  ｓｉｇｎｉｆｉｃａｎｔ  ｎｏｎｚｅｒｏ  ｂｉｔｓ）により大部分定義できることを確認することができる。
【０１１２】
【数１９】
0006509916.tif 000026
【０１１３】
図８を参照すると、Ｐビット整数として格納されるＤk及びＬkの二進表現を示す。本発明は、速いプロセッサ演算を使用してＬkの最上位１ビットの位置Ｑを探し出すことができる。これを通じて、本発明は図８に示すように、ＬkからＴ個のビットｕ1ｕ2・・・ｕTを抽出し、ＤkからＴ＋１個のビットｖ0ｖ1ｖ2・・・ｖTを抽出することができる。このようなビットは二進表現ｕ1ｕ2・・・ｕTｖ0ｖ1ｖ2・・・ｖTとして整数Ｚを生成するために使われることができ、これは２2T+1個の項目を有するデコーディングテーブルのインデックスに使用できる。
【０１１４】
ビット位置Ｑが与えられれば、割算（Ｄk／Ｌk）の上位境界値と下位境界値は＜数式２０＞により定義できる。
【０１１５】
【数２０】
0006509916.tif 000027
【０１１６】
ここで、Ｅminは割算（Ｄk／Ｌk）の上位境界値を意味し、Ｅmaxは割算（Ｄk／Ｌk）の下位境界値を意味する。例えば、Ｅminは［Ｄmin／Ｌmax］として定義されることができ、Ｅmaxは［Ｄmax／Ｌmin］として定義できる。したがって、Ｅmin及びＥmaxは＜数式２１＞及び＜数式２２＞で表現できる。
【０１１７】
【数２１】
0006509916.tif 000028
【０１１８】
【数２２】
0006509916.tif 000029
【０１１９】
ここで、‘ａ’は掛け算近似に対応するビットシフト（ｂｉｔ  ｓｈｉｆｔ）を示す。このような値をＲＡＭ−テーブルのインデックスに使用することによって、バイセクション探索（ｂｉｓｅｃｔｉｏｎ  ｓｅａｒｃｈ）のための初期値が＜数式２３＞及び＜数式２４＞のように獲得できる。
【０１２０】
【数２３】
0006509916.tif 000030
【０１２１】
【数２４】
0006509916.tif 000031
【０１２２】
これによって、本発明は次のようなシンボルデコーディング過程を提供することができる。
【０１２３】
前記デコーダはＬkの最上位１ビットのビット位置Ｑを決定し、ビット位置Ｑ＋１から始めて、ＬkのＴ個の最上位ビットを抽出することができる。また、ビット位置Ｑから始めて、前記デコーダはＤkのＴ＋１個の最上位ビットを抽出することができる。
【０１２４】
この後、前記デコーダは前記２Ｔ＋１個のビットを結合してテーブルインデックスＺを形成することができる。前記デコーダは、前記テーブルからＥmin及びＥmaxを獲得し、区間［ｓmin（Ｚ）、ｓmax（Ｚ）］のみで次の＜数式２５＞を満たすｓの値を探索することができる。
【０１２５】
【数２５】
0006509916.tif 000032
【０１２６】
図９は本発明が適用される一実施形態であって、連結されたＲＯＭ−ＲＡＭテーブルを含む算術デコーダの概略的なブロック図を示す。
【０１２７】
本発明が適用されるデコーダは、インデックス生成ユニット９１０、連結されたＲＯＭ−ＲＡＭテーブルユニット９２０、バイセクション探索ユニット９３０、及びデータモデルユニット９４０を含む。前記連結されたＲＯＭ−ＲＡＭテーブルユニット９２０は、ＲＯＭテーブル９２１、及びＲＡＭテーブル９２２を含む。
【０１２８】
前記インデックス生成ユニット９１０はＤkとＬKを受信し、Ｄk及びＬKから特定のビットの集合を抽出することができる。また、前記インデックス生成ユニット９１０は前記特定のビットの集合に基づいてデコーディングテーブルに対するインデックスＺを生成することができる。このような場合に、前記インデックスＺはＬKのＴ個の最上位ビット及びＤkのＴ＋１個の最上位ビットに基づいて形成できる。
【０１２９】
前記生成されたインデックスＺは、前記連結されたＲＯＭ−ＲＡＭテーブルユニット９２０に転送できる。前記転送されたインデックスＺは、前記連結されたＲＯＭ−ＲＡＭテーブルユニット９２０のＲＯＭテーブル９２１に格納できる。割算（Ｄk／Ｌk）の上部境界及び下部境界、ＥmaxとＥminはＲＯＭテーブル９２１から獲得されることができ、ＲＡＭテーブル９２２に転送できる。例えば、Ｅmax及びＥminは＜数式２１＞及び＜数式２２＞に基づいて獲得できる。
【０１３０】
前記ＲＡＭテーブル９２２は、ＲＯＭテーブル９２１からＥmax及びＥminを受信し、バイセクション探索のための初期値を出力することができる。このような値をＲＡＭテーブルに対するインデックスに使用して、バイセクション探索の初期値、Ｓmax及びＳminが獲得できる。このような場合、＜数式２３＞及び＜数式２４＞が使用できる。
【０１３１】
前記バイセクション探索ユニット９３０は、該当区間［Ｓmin（Ｅmin）、Ｓmax（Ｅmax）］でｓの値のみを探索して、ｓの値を出力することができる。このような場合、前記ｓの値は＜数式２５＞を満たす。
【０１３２】
より大きいテーブルを使用することによって、よりよい近似を得ることができるということは明らかであり、十分に大きいテーブルに対してＥmin＝Ｅmaxの結果を得ることができ、これはこれらが実際の割算値のような効率として探索範囲を狭めることができることを意味する。
【０１３３】
前記連結されたＲＯＭ−ＲＡＭテーブルはアップデートを要せず、ＲＯＭに格納できるのでＲＯＭテーブルと呼ばれることができる。また、ＲＡＭテーブル内の項目の個数が知られれば、Ｅmin及びＥmaxの該当最上位ビットのみ格納される必要がある。例えば、ＲＡＭテーブル内の項目の個数が２５６の場合には、Ｅmin及びＥmaxの最上位８ビットのみを格納するだけで充分でありうる。
【０１３４】
図１０は本発明が適用される一実施形態であって、データシンボルをデコーディングする方法を例示するフローチャートである。
【０１３５】
本発明が適用されるデコーダは、コード値の位置情報を含むビットストリームを受信することができる（Ｓ１０１０）。
【０１３６】
例えば、前記位置情報は初期範囲及び区間情報のうち、少なくとも１つを含むことができる。
【０１３７】
また、前記デコーダはコード値の位置情報に対応するシンボルを確認し（Ｓ１０２０）、確認されたシンボルをデコーディングすることができる（Ｓ１０３０）。
【０１３８】
この際、各シンボルの確率によって範囲が分割されることができ、分割された範囲内に如何なるシンボルが含まれているかを確認することによって、シンボルをデコーディングすることができる。
【０１３９】
図ｌ１は本発明が適用される一実施形態であって、連結されたＲＯＭ−ＲＡＭテーブルを使用して算術デコーディングを遂行する方法を例示するフローチャートである。
【０１４０】
本発明が適用される前記デコーダは、区間長さの最上位１ビットの位置を決定することができる（Ｓ１１１０）。
【０１４１】
また、前記デコーダは最上位１ビットの以後に前記位置に１ビットを加えた位置から始まって区間長さの最上位ビットを抽出することができ（Ｓ１１２０）、前記位置で出発してコード値の最上位ビットを抽出することができる（Ｓ１１３０）。
【０１４２】
この後、前記デコーダは前記区間長さの最上位ビットと前記コード値の最上位ビットとを結合することによって、デコーディングテーブルインデックスを生成することができる（Ｓ１１４０）。
【０１４３】
前記デコーダはＲＯＭテーブルから分割の上部及び下部境界を獲得することができ（Ｓ１１５０）、前記上部及び下部境界に基づいてＲＡＭテーブルからバイセクション探索に対する初期値を獲得することができる（Ｓ１１６０）。この際、前記連結されたＲＯＭ−ＲＡＭテーブルはＳ１１５０及びＳ１１６０の過程で使用できる。
【０１４４】
この後、前記デコーダは該当区間内のシーケンスの値を探索することができる（Ｓ１１７０）。
【０１４５】
前述したように、本発明で説明した実施形態は、プロセッサ、マイクロプロセッサ、コントローラ、またはチップ上で具現されて遂行できる。例えば、前記図１から図７及び図９に図示した機能ユニットは、コンピュータ、プロセッサ、マイクロプロセッサ、コントローラ、またはチップ上で具現されて遂行できる。
【０１４６】
また、本発明が適用されるデコーダ及びエンコーダは、マルチメディア放送送受信装置、モバイル通信端末、ホームシネマビデオ装置、デジタルシネマビデオ装置、監視用カメラ、ビデオ対話装置、ビデオ通信のようなリアルタイム通信装置、モバイルストリーミング装置、格納媒体、キャムコーダ、注文型ビデオ（ＶｏＤ）サービス提供装置、インターネットストリーミングサービス提供装置、３次元（３Ｄ）ビデオ装置、画像電話ビデオ装置、及び医療用ビデオ装置などに含まれることができ、ビデオ信号及びデータ信号を処理するために使用できる。
【０１４７】
また、本発明が適用される処理方法はコンピュータにより実行されるプログラムの形態に生産されることができ、コンピュータにより読取可能な記録媒体に格納できる。本発明に従うデータ構造を有するマルチメディアデータもまたコンピュータにより読取可能な記録媒体に格納できる。前記コンピュータにより読取することができる記録媒体はコンピュータにより読取可能なデータが格納される全ての種類の格納装置を含む。前記コンピュータにより読取可能な記録媒体は、例えば、ブルーレイディスク（ＢＤ）、汎用直列バス（ＵＳＢ）、ＲＯＭ、ＲＡＭ、ＣＤ−ＲＯＭ、磁気テープ、フロッピーディスク、及び光学的データ格納装置を含むことができる。また、前記コンピュータにより読取可能な記録媒体は、搬送波（例えば、インターネットを通じての転送）の形態に具現されたメディアを含む。また、エンコーディング方法により生成されたビットストリームがコンピュータにより読取することができる記録媒体に格納されるか、または有無線通信ネットワークを介して転送できる。
【産業上の利用可能性】
【０１４８】
以上、前述した本発明の好ましい実施形態は、例示の目的のために開示されたものであって、当業者であれば、以下の添付された特許請求範囲に開示された本発明の技術的思想とその技術的範囲内で、多様な他の実施形態を改良、変更、代替、または付加などが可能である。
【図１】
0006509916.tif 000033
【図２】
0006509916.tif 000034
【図３】
0006509916.tif 000035
【図４】
0006509916.tif 000036
【図５】
0006509916.tif 000037
【図６】
0006509916.tif 000038
【図７】
0006509916.tif 000039
【図８】
0006509916.tif 000040
【図９】
0006509916.tif 000041
【図１０】
0006509916.tif 000042
【図１１】
0006509916.tif 000043