データデコーディング
【課題】コンテクストベースの適応演算エントロピーコード化データをデコーディングする方法を提供する。
【解決手段】例えば、Ｈ２６４デコーダから到来するデコードされたデータ(1)は、コンテクストベースの演算エンコーディングを含む並列エンコーディング機構を使用して、そのデコードされたデータをエントロピーエンコードするエンコーダユニット(2)へ供給される。シンタックスは、コンテクストがその直前にエンコードされた記号に依存しないように選択される。エンコーダ(2)の出力は、ＦＩＦＯメモリへ供給され、その出力は、相補的デコーダ(4)へ供給され、そしてその出力は、到来するデコードされたデータ(1)の遅延されたコピーを発生する。
【解決手段】例えば、Ｈ２６４デコーダから到来するデコードされたデータ(1)は、コンテクストベースの演算エンコーディングを含む並列エンコーディング機構を使用して、そのデコードされたデータをエントロピーエンコードするエンコーダユニット(2)へ供給される。シンタックスは、コンテクストがその直前にエンコードされた記号に依存しないように選択される。エンコーダ(2)の出力は、ＦＩＦＯメモリへ供給され、その出力は、相補的デコーダ(4)へ供給され、そしてその出力は、到来するデコードされたデータ(1)の遅延されたコピーを発生する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、エントロピーエンコードされたデータストリームの処理に係り、より詳細には、このようなデータストリームをデコードするための方法及び装置に係る。
【背景技術】
【０００２】
エントロピーエンコードされたデータストリームは、例えば、新規な“Ｈ２６４”ビデオエンコーディング規格（“ITU-T Recommendation H.264: Advanced video coding for generic audiovisual services”）のものを含む圧縮されたビデオデータストリームである。ウイジェンド氏等は、“An Overview of the H.264/AVC Video Coding Standard”（IEEE Trans. On Circuits and Systems for Video Technology July 2003）においてこの仕様書の若干短い概要を提供している。
【０００３】
ほとんどのビデオ圧縮機構は、「生」のデータ記号を、それらの発生確率を反映する表現に置き換えて、頻繁に発生する記号をより少ないビットの表現でエンコードする一方、あまり頻繁でない記号をより長い表現でエンコードするようなある形式のエントロピーエンコーディングを含む。シャノンの理論は、確率ｐをもつ記号に対する最適なビット数が−ｌｏｇ（ｐ）／ｌｏｇ（２）であると述べている。例えば、３回のうち１回の発生機会をもつ記号は、１．５８５ビットで最適に表わされる。
【０００４】
多くのエンコーディング機構は、エントロピーエンコーディングを行うために、ハフマンのシステムと同様の可変長さコーディング（ＶＬＣ）システムを使用している。このような機構は、一般に、エンコード及びデコードが非常に容易であるが、各コードの長さが常に整数のビット数であるために、一般に、シャノンにより述べられた最適状態を達成することができない。
【０００５】
ＶＬＣ機構に代わるより最近の機構は、演算エンコーディング（その紹介が、プレス氏等の“Numerical Recipes in C”、ＩＳＢＮ ０−５２１−４３１０８−５に見ることができる）、及び実質的に等価なレンジエンコーディングを含む。これら両エンコーディング機構は、実際に、記号を分数のビット数で表わすのを許すことにより、シャノンの最適状態に非常に近いものを得る、より進歩したエントロピーエンコーディング機構である。しかしながら、１つの欠点は、ＶＬＣ解決策よりもエンコード及びデコードが非常に複雑なことである。
【０００６】
新規なＨ．２６４規格、特にそのＣＡＢＡＣモード（マープ氏等の“Context-based adaptive binary arithmetic coding in the H.264/AVC video compression standard”,IEEE Transactions on Circuits and Systems for Video Technology, July 2003を参照）は、演算エンコーディングの一形式を使用している。Ｈ２６４ ＣＡＢＡＣ機構は、次のことによりプロセスをより難解なものにする。
ａ）演算エンコーダ／デコーダを使用して、値のセットではなく、２つの記号、即ち０か１だけをエンコードする。しかしながら、３つ以上の記号の選択からデコードできる演算デコーダは、構成費用も高いことに注意されたい。典型的に、Ｎ個の記号を直接取り扱うエンコーダ又はデコーダは、コストがＯ（Ｎ）となり、一方、２記号デコーダを使用して（複数のステップにわたり）Ｎ個の記号を処理するものは、コストがＯ（ｌｏｇ(Ｎ)）となる。
ｂ）エンコード／デコードされた各ビットの後にエンコーディング／デコーディングを遂行するのに使用される統計学的情報（Ｈ２６４ではコンテクストとして知られている）を更新する。
ｃ）ビットごとに選択できる多数のコンテクストを維持する。
ｄ）多数のステップを含むことのできる「デバイナライゼーション(debinarisation)」プロセスを使用することにより、デコードされた演算ビットを記号へアッセンブルする。
【０００７】
逆離散的コサイン変換（ＩＤＣＴ）パラメータの場合には、これは、意義マップをデコードし、非ゼロ記号に対してサインビットをデコードし、非ゼロ記号に対して単項ストリングデータをデコードし、そして大きな非ゼロ記号に対して指数関数的なゴロン(Golomb)データをデコードすることを含む。これらの各デコーディングステップは、演算デコーダを制御するためにフィードバックされる異なるコンテクストを選択する。
【０００８】
これらのステップをたどることにより、非常に高い圧縮比を得ることができる。しかしながら、コストペナルティがある。クロック（例えば、１００〜２００Ｍｈｚの範囲のクロックレートの）当たり１ビットを越えるものをデコードするのはハードウェアにとって不可能ではないまでも非常に困難である。並列な演算エンコーディングにおいてある程度の進歩がなされているが（コンテクストが一定に保たれると仮定すれば）、デコーディングに対してなされたと思われるものはない（スポール及びメリチャーの“Arithmetic Encoding in Parallel”を参照）。各フレームが多数の「スライス」（即ち、フレームの部分）で構成される場合には、各スライスを並列にデコードすることができるが、到来するビデオストリームがフレーム当り２つ以上のスライスを有することが保証されないので、これは、適当な解決策ではない。
【０００９】
更に、前記ｄ）で述べたように、ビデオストリームにおけるソース記号は、一般的に、多数のビットで構成され（例えば、ソース値は、１６ビット値でサインされ）、従って、ＣＡＢＡＣも、単項及びゴロンコーディングのようなＶＬＣエンコーディング機構を使用する。ビデオデータをエンコーディングするときには、システムは、最初に、各々の生の記号値をＶＬＣバイナリーエンコード化形態（Ｈ２６４では「バイナライゼーション(binarisation)」として知られた）へ変換し、これを、次いで、バイナリー演算エンコーダにより圧縮しなければならない。デコーダは、本質的に、これらのステップを逆に実行して、オリジナルのデータストリームを得る。これは、最悪のケースにおいて、演算デコーダがクロック当たり１ビットをデコードできるとしても、最終的な記号を得るのに多数のクロックサイクルを必要とする。例えば、ＩＤＣＴデータを処理するときに、クロック当たり１ビットの演算デコードレートを仮定すれば、ＣＡＢＡＣプロセスを使用して「６４」の記号値をデコードするのに３０サイクル程度を要し、一方、簡単な「＋１」値は、ＣＡＢＡＣでデコードするのに４つのクロックを要する。大きな値に関連したデコードコストは、それらの非常に低い確率により、そして非常に速いレートでデコードされるゼロ値の非常に高い確率により、相殺される。バイナライゼーションプロセスを使用してＩＤＣＴ係数（意義マップを含む）の値をエンコードするのに必要なビットの数の幾つかの例を、以下のテーブルに示す。
【００１０】
【００１１】
デコードタイミングは、ｄ）に述べたように、演算デコーダを制御するのに使用されるコンテクストデータが、以前にデコードされたビットの値に基づいて、しばしば、ビットごとに選択されることにより、更に複雑化される。これは、クロックごとに１ビットをデコードする必要がある場合に、ビットの演算デコーディング及びそのビットの値に基づくデバイナライゼーション判断ステップを同じクロック周期で行わねばならないか、或いはある種類の推論的並列デコーダを構成しなければならないことを意味する。その第１は、今日の技術では達成できないことがあり、そしてその第２は、実施コストがかかる。それ故、１００〜２００ＭＨｚで実行されるＨ２６４演算デコーダハードウェア解決策は、クロック当たり１ビットを達成しないことがあり、タイミングの問題を更に悪化させる。
【００１２】
圧縮されたビデオストリームは、充分な指定平均データレート、例えば、高鮮明度ビデオ（即ち、１９２０ｘ１０８０ピクセル＠３０ｆｐｓ）に対して５０Ｍビット／ｓを有するが、このビデオストリームにおける瞬時データレートは、フレームごとに著しく変化する。イントラ・エンコード化として知られている幾つかのフレーム（即ちＩ−フレーム）は、一般に、大きなデータを有するが、予想フレーム（Ｐ−フレーム）及び両方向フレーム（Ｂ−フレーム）は、以前にデコードされたフレームからデータを借りるので、遥かに少ないビットしか必要としない。例えば、４０Ｍビット／ｓでエンコードされる所与のサンプルビデオストリームでは、各Ｉ−フレームが、典型的に、ほぼ３Ｍビットを必要とし、Ｐ及びＢ−フレームは、各々、そのサイズのほぼ１／２及び１／３である。５０Ｍｂ／ｓの最大レートを使用するビデオストリームをデコードできるハードウェアＣＡＢＡＣデコーダ（例えば、１００〜２００ＭＨｚで動作する）を形成することは困難ではないが、従来のデコーダは、そのデータを定常のフレームごとのレートで発生しない。
【００１３】
各ビデオフレームの処理コストが、エントロピーエンコードされたデータに単純に依存する場合には、解決すべき問題はない。しかしながら、処理レートが更に固定された処理部分がある。例えば、ＩＤＣＴ計算、モーション補償、及びデリンギング／デブロッキングユニットは、一般に、処理されるピクセルの数に依存する時間を必要とする。これらのユニットは、処理時間がより一定であるので、実際には、著しく変化し得るソースプロジューサ、即ちエントロピーデコーダにより供給される比較的固定レートのコンシューマプロセス、即ちバックエンドビデオプロセッサが存在する状況となる。
【００１４】
例えば、ハードウェア解決策は、〜４００クロックサイクルにおいて３８４個のピクセルより成るＨ２６４マクロブロックに対してＩＤＣＴ処理を遂行する。エントロピーデコーダにより供給されるこのデータのパラメータは、マクロブロック領域における映像の複雑さに基づいて０から３８４個までのいずれかの数の記号を有し、従って、エントロピーデコードされるべきクロックサイクルがゼロから数千個までのいずれかとなる。
【００１５】
これは、処理レートの不一致のために、非常に頻繁に、あるユニットが他のユニットによりストールされるときの状況を招く。その結果、フレーム／秒での全処理レートが２の瞬時最小値に低下し、これは、システムが必要なデコーディングフレームレートを満足しないことを意味する。前記のＩＤＣＴの例を再び見ると、エントロピーエンコーダがクロック当たり１記号のレートで各記号をデコードできる場合には、問題が生じない。
【００１６】
上述したように、エントロピーデコーダをより速く動作することは（不可能でないまでも）実際的ではなく、コンシューマユニットをより速く動作することは、非常に経費高となる。これらの状況における明らかな昔ながらの慣習は、プロデューサとコンシューマとの間にレート平滑ＦＩＦＯを導入することである。この一般的なやり方は、３Ｄグラフィック処理チップからハードディスクコントローラまでの装置に広く使用されている。
【００１７】
簡単なＦＩＦＯは、問題を「解決」するが、データレートを有効に平滑化するのに多数のフレームの価値あるデータを含む必要があるという不便さがある。これは、典型的に、バッファが外部メモリであるように強制し、これは、大量のＲＡＭとタイアップするだけでなく、バッファの書き込み及び読み取りに著しい帯域巾を消費することも意味する。初期のビデオ規格は、ハフマン／ＶＬＣエンコーディングを使用し、これは、クロック当たり１記号のレートで容易にエンコード及びデコードすることができ、従って、非常に明らかな選択肢は、このようなエンコーディング機構を使用して、ＦＩＦＯへの入力のデータを再圧縮し、次いで、その圧縮されたデータを再び出口で解凍することである。実際に、多数の規格を取り扱うビデオエンコーディング／デコーディングチップでは、このようなＶＬＣハードウェアがとにかく存在する。この幾分か簡単な解決策は、リンザー及びレウン氏によって説明されていると思われる（米国特許第６，９２７，７１０号）。
【００１８】
それに関連する機構がシューマン氏により説明されている（米国特許出願第２００４０２６０７３９号）。この方法では、データを直ちに「デバイナライズ」するのではなく、ＣＡＢＡＣ演算デコーダから出力される「バイナライズ」されたビットがＦＩＦＯに送り込まれ、次いで、ＦＩＦＯの他端には、（第２の）デバイナライゼーションユニットが配置されている。（正しいコンテクストを選択するためには演算デコーダユニットの付近に部分的デバイナライゼーションユニットが依然必要とされることに注意されたい。）バイナライズされたデータ（即ち、例えば、依然として、意義マップ＋単項＋ゴロン形態でエンコードされたデータ）は、依然、合理的に充分に圧縮されたフォーマットである。不都合なことに、この方法に伴って生じ易い問題は、単一のクロックサイクルで各記号を解凍できるようにするために非常に大きなビットウインドウ及び複雑なハードウェアが必要になることである。これは、上述したＩＤＣＴバイナライゼーションコストテーブルから明らかである。
【００１９】
最後に関心のあるものは、Ｈ２６４ビデオストリームにおいてＣＡＢＡＣユニットからデコードされる典型的な値の検討である。特に関心のあるのは、ＩＤＣＴ係数である。というのは、これらは、通常、膨大な量のデコードされたデータを作り上げるからである。次のテーブルは、典型的なＨ２６４高鮮明度ビデオストリームからサンプリングされたＩＤＣＴの値及び確率を示す。確率と共に最適な記憶コストがリストされている。
【００２０】
【００２１】
ＩＤＣＴ値の各ブロックでは、多くの高周波数項がゼロになる見込みが非常に高い。高周波数の隣接するゼロが除去される（何らかのまだ未指定の手段により）場合には、テーブルが次のようになる。
【００２２】
【００２３】
残りのゼロを何らかの手段により（例えば、ラン・レベル又はおそらく意義マップエンコーディングの使用を経て）暗示できる場合には、非ゼロ値の確率が次のようになる。
【００２４】
【００２５】
これらの非常に一般的な値が、各記号を表わすのに整数個のビットを使用しなければならないハフマンのような簡単なＶＬＣエントロピー機構を使用してエンコードされる場合には、最適なものとは懸け離れたものになることが明らかである。というのは、非常に一般的な±１の値に対する最良の適合が２ビットであり、理想的な状態に対して記憶コストの約２５％の増加を表わすからである。
【発明の概要】
【発明が解決しようとする課題】
【００２６】
上述したように、演算エンコーディングは、分数個のビットで記号を表すことができ、潜在的に高い圧縮レベルを導くという点で、ＶＬＣ／ハフマン解決策よりも優れている。問題は、適応できる機構は、若干シーケンシャルにデコードできるものであり、従って、クロック当たりに１つの完全な（マルチビット）記号というピークレートの達成を困難にすることである。
【００２７】
デコードされたデータのプロデューサとコンシューマとの間にレート平滑ＦＩＦＯを導入することができるが、これが単純な形態で表わされる場合には、非常に大きなＦＩＦＯを必要とすることになる。ＦＩＦＯへ送られるデータに圧縮機構を適用して、ＦＩＦＯに必要なサイズを減少することはできるが、ＦＩＦＯの必要サイズを更に減少するために既知の圧縮機構の効率を高めることが望まれる。
【課題を解決するための手段】
【００２８】
第１の態様において、本発明は、コンテクストベースの適応演算エントロピーコード化データをデコーディングする方法であって、
ａ）エンコードされたデータをデコーディングして、第１のデコードされたデータを発生するステップと、
ｂ）記号の少なくとも一部分に対してコンテクストベースの適応演算エンコーディングを含む並列エンコーディング機構を使用して前記デコードされたデータをエントロピーエンコーディングして、第２のエンコードされたデータを発生するステップと、
ｃ）前記第２のエンコードされたデータを先入れ先出し（ＦＩＦＯ）メモリに記憶するステップと、
ｄ）前記第２のエンコードされたデータをＦＩＦＯメモリから読み取るステップと、
ｅ）ＦＩＦＯメモリから読み取ったデータをデコーディングして、デコードされたエントロピーコード化データである第２のデコードされたデータを発生するステップと、
を備えた方法を提供する。
【００２９】
前記ステップｂ）において、エンコーダは、Ｎビット記号をエンコードし、この記号は、複数のストリームに分割され、そしてそれらストリームの少なくとも２つは、対応する数の演算エンコーディングユニットを使用して並列にエンコードされる。
【００３０】
本発明は、
ａ）最大エンコードサイズを小さく保持することができ、
ｂ）演算エンコーディングを使用することによりＶＬＣ方法より高い圧縮比を得ることができ、そして
ｃ）ほとんどの環境の下で、クロック当たり１つ（多ビット）の記号というデコード／エンコードレートを達成することができる。
【００３１】
本出願は、クロック当たり１つの記号というレートを実質上保証しつつも、相応の圧縮比を達成する演算エンコーディング及びデコーディングを使用してＦＩＦＯデータを圧縮及び解凍する方法を説明する。これは、エンコード／デコードプロセスの少なくとも一部分を並列化することにより、そしてある実施形態では、以前にデコードされた記号から記号に対するコンテクスト選択をデカップルすることでシステムのパイプライン動作を改善することにより、行われる。更に、「言語シンタックス」をリエンコーダ−デコーダのトップに適用して、Ｈ２６４ビデオストリームの多数の部分及び他のビデオ規格（簡単なＶＬＣコードを使用するものでも）によりそれを使用できるようにし、これは、ひいては、これらデコーディングユニットに対するタイミング制約を容易にすることができる。
【００３２】
この説明及び特許請求の範囲において、「演算コーディング」という語は、（特定の実施形態の特定の細部に関するものを除いて）レンジコーディングを含むものと解釈されない。
【００３３】
エンコーダは、Ｎビットの数値である「記号」を受け入れ、そしてそれを単一クロックにおいてエンコードすることができる（非常に稀な環境を除いて）。このプロセスの一部分として、記号は多数のストリームに分割され、それらストリームの少なくとも２つは、多数の演算エンコーディングユニット、又は演算及びＶＬＣエンコーディングの組み合わせで並列に圧縮される。他の実施形態では、演算エンコーディングに代わってレンジエンコーディングを使用することができる。というのは、それらが非常に類似しているからである。各ストリームの出力は、外部メモリに存在できるＦＩＦＯ（１つ又は複数）へ送信される。マッチングデコーダは、ＦＩＦＯからのデータを受け入れ、そしてオリジナルの記号を再デコードし、アッセンブルする。
【００３４】
第２の態様において、本発明は、コンテクストベースの適応演算エントロピーエンコードデータをデコーディングする装置であって、エンコードされたデータをデコーディングして、第１のデコードされたデータを発生する第１デコーダと、その第１のデコードされたデータをエンコードするためのエンコーダであって、デコードされたデータの少なくとも一部分に対してコンテクストベースの適応演算エンコーディングを含む並列エンコーディング機構を使用して、第２のエンコードされたデータを発生するエンコーダと、その第２のエンコードされたデータを記憶するための先入れ先出し（ＦＩＦＯ）メモリと、前記第２のエンコードされたデータをＦＩＦＯの出力から読み取り、そしてその第２のエンコードされたデータをデコーディングして、デコードされたコンテクストベースの適応演算エントロピーエンコードデータを発生するためのデコーダと、を備えた装置を提供する。
【００３５】
エンコーダは、Ｎビット記号をエンコードするように構成され、この記号は、複数のストリームに分割され、そしてそれらストリームの少なくとも２つは、対応する数の演算エンコーディングユニットを使用して並列にエンコードされる。
【００３６】
エンコーダは、特定のシンタックスを解釈して、処理されているシンタックスエレメントに基づき演算エンコーダのコンテクストを選択するように構成された状態マシンを含み、シンタックスは、コンテクストが以前の記号に依存しないよう確保するために選択される。
【００３７】
デコーダは、特定のシンタックスを解釈して、処理されているシンタックスエレメントに基づき演算デコーダのコンテクストを選択するように構成された状態マシンを含み、シンタックスは、コンテクストが以前のデコードされた記号に依存しないよう確保するために選択される。
【００３８】
前記装置は、単一のＦＩＦＯを備え、前記エンコーダは、エンコードされたデータストリームを、ＦＩＦＯへ書き込む前に、インターリーブするための手段を備え、そして前記デコーダは、ＦＩＦＯから読み取ったデータストリームをデインターリーブするための手段を備えている。
【００３９】
前記エンコーダは、可変長さコード化機構を使用して、同程度の確率の見込みがあるか又は存在する見込みが少ない各記号を表わすデータビットの部分をエンコードするための手段を備えている。
【００４０】
これは、必要とされる演算エンコーダ／デコーダの数を減少することによりエンコーダ／デコーダのコストを最小限にすることができる。
【００４１】
本発明の前記及び他の特徴並びに効果は、添付図面を参照した本発明の実施形態の以下の説明から明らかとなろう。
【図面の簡単な説明】
【００４２】
【図１】本発明によるデコーダのブロック図である。
【図２】本発明によるデコーダに使用するためのエンコーダユニットの第１実施形態のブロック図である。
【図３】ハードウェアコストを節減する、本発明によるデコーダに使用するためのエンコーダユニットの第２実施形態のブロック図である。
【図４】制御シンタックス要素のビットエンコーディングの一例を示す図である。
【図５】図４のシンタックスで表わされたデータを処理するためのエンコーディング状態マシンの実施形態を示す図である。
【図６】図２又は図３のエンコーダ（及びマッチングデコーダ）に使用するためのＡＬＵユニットの実施形態を示す図である。
【図７】単一のＦＩＦＯが使用されるときのデータをインターリーブする構成を示す図である。
【図８】図２に示すエンコーダに対するマッチングデコーダの実施形態のブロック図である。
【図９】図４のシンタックスで表わされたデータを処理するためのデコーディング状態マシンの実施形態を示す図である。
【図１０】一度に２ビットをエンコードする演算エンコーダを使用する図２及び図３の実施形態の変形を示す図である。
【図１１】図１０に示すエンコーダによりエンコードされたデータをデコーディングするためのデコーダの実施形態を示す図である。
【図１２】演算エンコーディングのみを使用するエンコーダの別の実施形態を示す図である。
【発明を実施するための形態】
【００４３】
図１は、本発明の実施形態をブロック図の形態で示す。圧縮されたデータが上流のデコーダユニット１へ供給される。このデコーダユニットは、例えば、Ｈ２６４ビデオエンコーディング規格に規定されたものでよい。デコーダ１から供給される値は、予想されるシンタックスにフォーマットされ、リエンコーダユニット２へ１６ビット値のストリームとして入力される。リエンコーダ２は、これらの値を圧縮し、その結果を「先入れ先出し」（ＦＩＦＯ）メモリ３へ出力する。ＦＩＦＯ３は、単一のＦＩＦＯではなくＦＩＦＯのセットでもよい。デコーダユニット４は、ＦＩＦＯ３から圧縮されたデータを読み取り、そのデータを再拡張して、オリジナルデータストリームを得、そしてそれを出力５へ通す。特定記号のエンコーディングとデコーディングとの間には、ＦＩＦＯ３にどれほど多くのデータが維持されるかに基づいて、可変時間遅延が生じることが明らかである。本発明の目的は、パイプラインのストールを防止し、又は少なくとも必要なフレームデコードレートを満足するシステムを停止するストールを防止する最小サイズのＦＩＦＯを割り当てできるようにすることである。実際に、その構成体は、中央処理ユニットがＦＩＦＯ３におけるデータの量を監視できるようにするための手段を含むことができる。
【００４４】
本発明に使用するのに適したエンコーディングユニット２の実施形態を、図２を参照して以下に説明する。図２に示すように、上流のデコーダユニット１は、１６ビット値Ａをエンコーダユニット２に供給する。この１６ビット値Ａは、経路１３を経て状態マシン１０の第１入力に供給され、そして経路１４を経て演算論理ユニット（ＡＬＵ）２０の第１入力に供給される。１６ビット値の幾つかは、後続データの解釈を制御するためにシンタックスにより使用される。状態マシン内には、ｎビットカウンタ１１（ｎは、例えば、９である）と、以前の「記号数」を記憶するためのメモリ１２がある。実際には、考えられるエンコーディングモードの各々に対応する多数の「以前の記号数」レジスタがある。状態マシン１０は、ＡＬＵ２０によって遂行されるオペレーションを含むリエンコーダ２における種々のサブユニットの振舞いを制御する。従って、状態マシン１０からの出力は、ライン１５を経てＡＬＵ２０の第２入力に供給され、そしてライン６を経て「他のビット選択」ユニット３１の第１入力に供給される。
【００４５】
ＡＬＵ２０は、１６ビット値Ａを受け取り、そしてそれに対して状態マシン１０の制御の下で動作して、２つの出力を発生する。サインフラグである第１出力は、ライン２１を経て「他のビット選択」ユニット３１の第２入力に供給され、一方、非サインの１６ビット値Ｂは、ライン２２を経て先導１検出器３０に供給され、該検出器は、最上位ビットの位置を決定し、そしてそれを範囲（０から１６）の５ビット値Ｄとしてエンコードする。例えば、Ｂが０の場合には、Ｄも０であるが、Ｂが０ｘ１２の場合には、Ｄが５となる。値Ｂは、先導１検出器３０から経路３３を経て「他のビット選択」ユニット３１の更に別の入力へ供給され、一方、値Ｄは、先導１検出器３０から経路３４を経て「他のビット選択」ユニット３１の更に別の入力に供給される。「他のビット選択」ユニット３１は、ライン３３を経て与えられたＢ値から最上位ビットを剥離し、そしてライン２１を経て受け取られたサインフラグを他のビットに付加して、値Ｃを発生する。この振舞いは、次のＣ擬似コードにより正確に記述される。
【００４６】
【００４７】
それにより得られて、値Ｃを作り上げるビット数は、０ないし１６のいずれかであり、それらは、ライン３５を経て「出力ストリーム０」ユニット３２へ出力される。これは、ビットを収集して、全パケットを、経路３８を経て出力マージユニット８０へ出力する小型ＦＩＦＯでよい。
【００４８】
これは、次のことを除いて、Ｈ２６４規格で使用される指数関数的ゴロンエンコーディング機構における変形として見ることができる。
ａ）減算ユニットを必要とせず、従って、ハードウェアで実施するのが非常に低廉である。
ｂ）Ｂの長さ、即ちＤ値は、単項エンコーディング方法ではエンコードされず、むしろ、別のエンコーディングユニットへ通される。
ｃ）小さな値を好むエンコードされたデータの長さには若干の相違がある。
【００４９】
先導１検出器３０により発生された値Ｄは、ライン３６を経て小さな先導１検出器４０の入力に供給され、この検出器は、範囲（０から５）の３ビット値Ｆを生成する。値Ｄは、先導１検出器４０から経路４６を経て更に別の「他のビット選択」ユニット４１へ供給される。又、値Ｆは、先導１検出器４０から経路４３を経て「他のビット選択」ユニット４１へも供給される。ここでも、「他のビット選択」ユニット４１は、Ｄの最上位ビットを除去し、残りのビットＥを、ライン４４を経て出力ストリーム１ユニット４２へ出力するが、Ｆ＝５、即ちＤ＝１６、従って、Ｅが０で、出力する必要がない特殊なケースは除く。この振舞は、次の擬似コードにより記述される。
F = FindLeading1Position(D);
IF((F < 2 ) OR (F==5))
{
NumBitsToOutput = 0;
}
ELSE
{
NumBitsToOutput = F 1;
}
Output(D, NumBitsToOutput, Stream1);
【００５０】
出力ストリーム１ユニット４２の出力は、更に、経路３８を経て出力マージユニット１８へ供給される。
【００５１】
先導１検出器４０からの３ビット値Ｆは、経路４５を経て先導１検出器５０の入力に供給される。先導１検出器５０は、範囲（０から３）の２ビット値Ｈを発生する。３ビット値Ｆは、先導１検出器５０から経路５３を経て更に別の「他のビット選択」ユニット５１へ供給される。更に、２ビット値Ｈは、経路５４を経て「他のビット選択」ユニット５１へ供給される。「他のビット選択」ユニット５１は、暗示されたビット（先導１を含む）を除去して、出力Ｇを発生する。Ｆの限定入力値のために、出力Ｇは、単一ビット値を有し、ライン５５を経て出力ストリーム２ユニット５２へ供給され、従って、エンコードされる各記号に対して最大１ビットが必要とされる。これは、次の擬似コードにより記述される。
H = FindLeading1Position(F);
If(H < 2 )
{
NumBitsToOutput = 0;
}
Else
{
NumBitsToOutput = 1;
}
Output(F, NumBitsToOutput, Stream2);
【００５２】
これは、次のテーブルにより要約することができる。
【００５３】
２ビット値Ｈは、その後、演算エンコーディングを使用してエンコードされるので、Ｇ及びＨへのＦのエンコーディングが別の仕方で選択される場合には、システムがより効率的に機能できる。このため、「先導１検出器」５０及び「「他のビット選択」ユニット５１の別の実施形態では、次のエンコーディングが、次のテーブルにより要約されるように使用される。
【００５４】
【００５５】
この別の実施形態に対してデコーダ４に相補的なユニットが存在しなければならないことに注意されたい。
【００５６】
別の実施形態では、両エンコーディング方法が、エンコーダ（及びデコーダ）に合体され、そして各状態マシンは、現在エンコーディングモード及びエンコードされるべきシンタックスエレメントに基づいて必要なエンコーディング及びデコーディング方法を選択する。
【００５７】
値Ｈの２ビットは、先導１検出器５０から経路６２を経てコンテクストベースのバイナリー演算エンコーダ６０の第１入力へ供給され、そして経路７２を経て更に別のコンテクストベースのバイナリー演算エンコーダ７０の第１入力へ供給される。これらのエンコーダは、維持されるコンテクストの数が著しく減少される以外、Ｈ２６４エンコーダに使用されるものと同様である。エンコーダ６０及び７０のコンテクスト制御は、状態マシン１０により発生されて、経路１７を経てエンコーダ６０及び７０の第２入力に供給される。エンコーダ６０及び７０からの最終的なビットストリームは、各出力ストリームユニット６１及び７１を経、経路７５を経て、出力マージユニット８０へ供給される。出力マージユニット８０の出力は、エンコードされたデータであり、ＦＩＦＯ３の入力に供給される。
【００５８】
図３に示す別の構成において、図２に示した実施形態は、出力ストリーム０ユニット３２、出力ストリーム１ユニット４２及び出力ストリーム２ユニット５２を、少量のビットシフトハードウェアを使用してＣ、Ｅ及びＧ信号を連結する単一の出力ストリームユニット３９に置き換えることにより変更される。これは、実施コストを減少することができる。この変更は、ＡＬＵ２０のような図２の実施形態の無関係な部分には影響しないことに注意されたい。
【００５９】
状態マシン１０、ＡＬＵ２０、並びにエンコーダユニット６０及び７０の更に詳細な説明に進む前に、データストリームに対する支配シンタックスを見ることが重要である。これは、それ自体、制御値及びエンコードされるべき記号より成る１６ビット値のストリームに過ぎない。これは、次のＥＢＮＦ（Extended Backus-Naur Form）表現により最良に要約される。
【００６０】
【００６１】
図４に示すように、好ましい実施形態では、“UNIT_SEPARATOR”１００、“Data_Block_Header”１０１及び“NumSymbolsLess1”１０２も、「１６ビット」値である。この実施形態では、“UNIT_SEPARATOR”トークンは、１６ビット値、０ｘ３としてエンコードされる。“Data_Block_Header”トークン１０１は、２つのフィールド、即ち１４ビットの“Hardware_Code”値１０１ａ、及び２ビットの“encoding mode”フィールド１０１ｂより成る。この後者のフィールドは、３つの考えられる値を次のようにエンコードする。
【００６２】
【００６３】
所与のエンコーディングでは、“UNIT_SEPARATOR”及び“Data_Block_Header”は、最後の２ビットが常に異なるので、互いに間違えることはあり得ない点に注意されたい。又、これらの値は、数字的にできるだけ小さくなるように選択される。というのは、圧縮システムが小さな値を好むので、これが圧縮効率を改善するからである。
【００６４】
“HW_CODE”値は、エンコーダ／デコーダモジュールの各側でユニットにより使用するための任意のフィールドであるが、可能な限り小さな値が選択されることが推奨される。“Data_Block_Header”は、RUN_LEVEL_PAIR、SIGNED、又はSIG_MAP_VALUESの１つであるエンコーディング方法を含む。これらの名前は、おそらくそれらの意図された使い方を表すが、汎用性も高い。別の実施形態では、SIG_MAP_VALUESモードは、除去されてもよいし、又は優勢な大きな記号値を見込むもののような別のエンコーディング機構と置き換えてもよい。別の実施形態に対する他の組合せ又はエンコーディングパターンは、当業者に明らかであろう。
【００６５】
RUN_LEVEL_PAIRモードは、ペアのリストより成るデータに対して最適なものとされ、各ペアは、非サイン値と、それに続く（非ゼロ）サイン値で構成される。SIGNEDモードは、単に、サイン値のリストで構成され、そしてSIG_MAP_VALUESは、単一の非サイン値と、それに続く（非ゼロ）サイン値のリストで構成される。全てのケースにおいて、小さな値がデータを支配することが一般的に予想される。
【００６６】
これらのエンコーディング方法は、供給された記号リストをどのように処理するか、例えば、ＡＬＵ２０がどんなオペレーションを遂行すべきか、且つＣＡＢＡＣエンコーダユニット６０及び７０にどんなコンテクストを使用すべきか選択することを状態マシン１０に命令する。
【００６７】
“Separable_Unit”論理的グループ分けの目的は、システムがＦＩＦＯにおける圧縮されたデータに再同期ポイントをもつのを許すことである。状態マシン１０のエンコーダは、各“Separable_Unit”の後に、経路１８を経て内部バッファの出力ストリーム０ユニット３２、出力ストリーム１ユニット４２及び出力ストリーム２ユニット５２をフラッシュし、そして経路１９を経て出力３ユニット６１及び出力４ユニット６２をフラッシュし、必要に応じて、デコーダによりこれらを順にスキップできるようにする。例えば、Ｈ２６４では、フレームは、ある数の独立した「スライス」より成り、これらは、送信データが崩壊した場合に部分エラー回復を許すように意図される。スライスが“Separable_Unit”にパックされる場合には、デコーダ及びパイプラインの残りの部分によりそれを完全にスキップすることができる。この機構は、多数の異なるストリームを、例えば、スライスレベルで混合するのも許す。
【００６８】
各“Separable_Unit”内のデータは、Data_Blockの任意のリストより成り、その各々は、使用すべきエンコーディングの方法と、エンコードされるべき記号の数（１未満）と、ブロックにおいてエンコードされるべき記号とを記述するヘッダを含む。Data_Blockは、典型的に、ＩＤＣＴ係数のブロックのような記号の論理的グループに対して使用されるか、又はマクロブロックに属するモーションベクトル値のセットに対して使用される。
【００６９】
エンコーダのための状態マシンの概略が図５に示されている。プロセスがベース／アイドル状態２００でスタートすると仮定すれば、次の予想されるデータアイテムは、“UNIT_SEPARATOR”又は“Data_Block_Header”である。これらの値のいずれかが受け取られると、デコードプロセスについて考慮するときに明らかとなる理由で、それが全く同様にエンコードされる（２０１）。状態マシン１０は、状態２０２へ進む。これら記号の後に、常に、「非サイン」の１６ビット値が続き、これは、任意の値であるか、又はそれに続くデータの長さを表す。又、これらの値は、両方とも同様にエンコードされる（２１０）。以前の記号が“UNIT_SEPARATOR”であった場合には、経路２１１が取られ、状態マシン１０は、“Separable_Unit”のエンコーディングを終了し、演算エンコーダのコンテクスト／統計学的情報をリセットし、そしてバッファ２２０をフラッシュするようにエンコーダに通知する。これは、多数のクロックサイクルを要するが、非常に頻度の低いオペレーションであることが予想されるので、全コストを無視できる。これを達成するために、状態マシン１０は、経路１８を経てバッファ３２、４２、５２のコンテンツを空にし、経路１９を経てバッファ６１及び７１のコンテンツを空にし、且つ経路１７を経てエンコーダ６０及び７０のコンテクスト統計学的情報をリセットするためのインストラクションを発行する。
【００７０】
そうではなく、“Data_block_header”が状態２０１において受け取られた場合には、状態マシン１０は、経路２１２をたどり、少なくとも１つのデータ記号２３０を受け取ることを期待する。これは、“Data_block_header”に定義されたモードを使用してエンコードされる（２４０）。同時に、状態マシン１０の内部カウンタ１１がモードに基づいて初期化される。モードが“SIGNED”又は“SIG_MAP”である場合には、それが、供給されたNumSymbolsLess1にセットされ、さもなければ、NumSymbolsLess1*2+1にセットされる。後者が行われるのは、“RUN_LEVEL”値が常にペアで供給されて、その供給された値から冗長ビットを除去するからである。次いで、状態２７０及びプロセス２８０は、データブロックで供給された残りの記号をエンコードした後に、ベース状態２００に復帰する。プロセス２０８は、状態マシン１０のカウンタ１１を減少させ、従って、データブロックの全ての記号がエンコードされたときにベース状態２００に到達する。
【００７１】
ＡＬＵ２０の制御と、演算エンコーダ６０、７０の振舞いを支配するコンテクスト情報とについて、以下に説明する。文字通り数百のコンテクストを有するＨ２６４ ＣＡＢＡＣとは異なり、好ましい実施形態は、６個のコンテクストグループのセットしか有していない。各グループは、２つのＣＡＢＡＣユニットの各々について１つの、一対のコンテクスト値を有する。（コンテクストとは、全ての意図及び目的で２つのバイナリー値０及び１の現在の確率を記憶する。Ｈ２６４ ＣＡＢＡＣ設計では、これが８ビット値にパックされる。実施が容易であるために、同じ機構が実施形態により使用されてもよい。）
【００７２】
又、各グループには、ＡＬＵ２０により実行されるオペレーションに対する設定も関連付けられる。これらのオペレーションを、図６を参照して以下に説明する。到来するデータ値Ａに対して実行されて出力値Ｂを発生することのできる任意のオペレーションが３つある。この図において、これらは、３つの直列ステージとして説明されることに注意されたい。これは、単に明瞭化のために行われるが、ハードウェアシステムは、これらオペレーションを結合してもよく、そのようにした場合には、面積が減少され及び／又はタイミングが改善される。オプションがイネーブルされない場合には、そのオプションへの入力が、その出力へ通される。
【００７３】
第１のオプション３００は、到来する値Ａから以前のNumSymbolsLess1値１２を減算して、Ａ’を発生する。「Ｃ擬似コード」では、このオペレーションは、次の通りである。
IF(option_300_enabled)
{
A' = A Prev_NumSyms;
}
ELSE
{
A' = A;
}
【００７４】
第２の任意のオペレーション３０１は、その入力Ａ’の絶対値を計算し、そしてオリジナルサイン値フラグも出力する。「Ｃ擬似コード」では、このオペレーションは、次の通りである。
【００７５】
【００７６】
最終的に、オプション３０２は、入力値Ａ”から１を減算し、最下位１６ビットを保持する。「Ｃ擬似コード」では、このオペレーションは、次の通りである。
IF(option_302_enabled)
{
B = (A'' 1) & 0xFFFF;
}
ELSE
{
B = A'';
}
【００７７】
ＡＬＵに対する６個のコンテクストグループ及びそれらの設定は、次のテーブルに要約される。
【００７８】
【００７９】
各“Separable_Unit”の始めにコンテクストに指定される、コンテクストのための初期確率値は、例示のために示されたものに過ぎない。好ましい実施形態では、これらの値は、例えば、ＣＰＵによりプログラムできるレジスタのセットから得られる。又、例示値は、ＳＩＧＭＡＰエンコードモードを要求しない実施形態により生成されたものであり、従って、それに対する初期確率は含まれない。
【００８０】
コンテクストグループと図５に示す状態との関係を以下に説明する。
状態２０１において、「ヘッダ」グループが選択される。
【００８１】
状態２１０において、「デルタ長さ」グループが使用される。テーブルから明らかなように、供給された「長さ１」値が以前の値から減算され、その結果の絶対値が取り出される。この結果（及び減算結果のオリジナルサイン）がエンコードされる。
【００８２】
状態２４０及び２８０において、ヘッダデータで指定されたエンコーディングモードに基づいて残りの４つのコンテクストグループ‘S’、‘RL_U’、‘SM_M’又は‘S_NZ’の１つを使用して記号値がエンコードされる。‘SIGNED’モードを使用してエンコーディングするときには、データブロックにおける全ての残りの値に対して‘S’グループが使用される。
【００８３】
‘RUN_LEVEL’モードでエンコードするときには、選択されたグループが‘RL_U’と‘S_NZ’との間で交替し、一方、‘SIGMAP’モードの場合には、第１記号が‘SM_M’モードでエンコードされ、そして残りが‘S_NZ’でエンコードされる。
【００８４】
実施形態により多数のストリームが発生されるときには、単一のＦＩＦＯを有するのが好ましい。というのは、これは、システムが利用可能な外部メモリ空間を先験的に多数の固定サイズのＦＩＦＯに分割する必要がないことを意味するからである。従って、単一の外部ＦＩＦＯが存在する実施形態では、エンコーダにおいて種々の出力ストリームをインターリーブし、次いで、デコーダへデータが読み込まれるときにそれらをデインターリーブする効率的な手段があるのが好ましい。これは、実際には、多数の理由で、重要なタスクである。
ａ）ストリームは、各々、記号当り異なる数のビットを発生し、
ｂ）特定の記号‘ｘ’に対して、‘Ｃ’、‘Ｅ’及び‘Ｇ’に対応するビットは、ほとんど即座に発生されるが、演算エンコーダは、それらのエンコードされたビットを、ある数の記号の後まで発生しないことがある。ある状況において、これは、数十又は数百個の記号の後であり、そして
ｃ）記号のデコーディングを開始するために、ストリームに対する全ての関連データがデコーダにおいて同時に入手できねばならない。
【００８５】
更に、メモリサブシステムは、効率的に使用されねばならない。多くのシステムでは、これは、読み取り及び書き込みをあるサイズのバーストで行わねばならないことを意味し、これは、数十ないし数百のバイトを必要とすることがある。例えば、個々のバイトをランダムにアクセスすることは、効率的でない。
【００８６】
この問題に対する解決策を、図７を参照して以下に述べる。この実施形態ではサイズが約４ＭバイトであるＦＩＦＯメモリ５００は、固定サイズの「割り当てブロック」５０１へ論理的に分割され、各ブロックは、最小の効率的メモリ転送バーストサイズの倍数となるように選択されるのが好ましい。好ましい実施形態では、各ブロックは、サイズが２５６ビットである。ＦＩＦＯメモリに対する３つの「ポインタ」が維持される。「分離可能ユニットヘッド」５１０は、エンコーダ２によって現在記憶されている分離可能ユニットのためのデータの開始を指す。「分離可能ユニットテール」５１１は、デコーダ４により現在処理されている分離可能ユニットの開始を指す。これが「分離可能ユニットヘッド」ポインタと同じように前進する場合には、デコーダは、エンコーダがその現在の分離可能ユニットを終了するまでストールする。
【００８７】
「フリーブロックポインタ」５１２は、エンコーダがその出力ストリームの１つから新たなブロックの価値あるデータを発生するときに増加される。これがＦＩＦＯメモリブロックの終りに到達すると、開始点へラップアラウンドする。「フリーブロックポインタ」が「分離可能ユニットテール」に到達する場合には、ＦＩＦＯがいっぱいになったと考えられ、エンコーダは、デコーダがその現在分離可能ユニットを終了するまでストールし、そしてポインタを、次に記憶された分離可能ブロックの開始点へ前進させる。
【００８８】
各割り当てブロックは、データ部分５１２及び「次」のポインタ５１３を含む。好ましい実施形態では、「次」のポインタは、１６ビット値である。これは、ブロックのチェーンにおいて「次」の割り当てブロックをインデックスし、次のように使用される。
【００８９】
Ｎ個の出力ストリームをもつ実施形態のマージユニット８０内で、新たな「分離可能ユニット」の開始に、最初のＮ個の割り当てブロックが、現在の分離可能ブロックの開始点（「フリーブロックポインタ」に等しい）に対して、Ｎ個のストリームに予め指定され、そして「フリーブロックポインタ」がＮだけ前進される。マージユニットは、割り当てユニットのサイズのＮ個（多重バッファされる場合にはそれ以上）のバッファと、Ｎ個の１６ビットアドレス値、Ａ［０］・・・Ａ［Ｎ−１］とを含む。アドレス値は、「分離可能ユニットヘッド」ないし「分離可能ユニットヘッド＋（Ｎ−１）」の値に各々初期化される。データがそれに対応するストリーム［ｉ］により供給されるときには、マージユニットが各バッファ［ｉ］を並列に充填し始める。バッファ［ｊ］がいっぱいになると、バッファ［ｊ］の「次のポインタ」が「フリーブロックポインタ」の値にセットされ、バッファ［ｊ］がＡ［ｊ］のアドレスに書き込まれ、Ａ［ｊ］が「フリーブロックポインタ」にセットされ、そして「フリーブロックポインタ」が増加される。
【００９０】
デコーダ４において要求されるマッチングデマージユニットは、ブロックを単に読み取り、そしてコンテンツをそれらの各ストリームに転送する。ある事項に対して読み取るべき次のブロックが、現在読み取られたブロックに含まれたポインタにより指示される。
【００９１】
デコーダ４は、本質的にエンコードプロセスの逆であるデコーディングプロセスを遂行する。図８は、図２のエンコーダにより発生されたエンコードされたデータをデコードするのに適したデコーダをブロック図の形態で示す。
【００９２】
図８に示すデコーダは状態マシン８００を備え、これは、Ｎビットカウンタ８０１及び以前の数字記号のレジスタ８０２を含む。状態マシン８００の出力は、経路８０３を経て演算論理ユニット（ＡＬＵ）８６０の入力に接続されると共に、経路８０４を経て他ビット選択ユニット８５１の入力に接続される。入力デマージユニット８０５は、ＦＩＦＯから受け取られたデータを並列ストリームに分割し、その出力は、経路８５９を経て、入力ストリーム０ユニット８５０、入力ストリーム１ユニット８４０、及び入力ストリーム２ユニット８３０へ接続されると共に、経路８１９を経て、入力３ユニット８２１及び入力４ユニット８１１へ接続される。状態マシン８００の更に別の出力は、経路８０６を経て２つのコンテクストベースの適応演算（ＣＡＢＡＣ）デコーダ８１０及び８２０の入力に接続される。この経路は、８１０及び８２０に使用されるコンテクストを選択して、現在ビットをデコードする。入力３ユニット８２１は、その出力が経路８２２を経てＣＡＢＡＣデコーダ８２０の更に別の入力に接続され、一方、入力４ユニット８１１は、その出力が経路８１２を経てＣＡＢＡＣデコーダ８１０の更に別の入力に接続される。
【００９３】
ＣＡＢＡＣデコーダ８１０及び８２０の出力は、経路８２３を経て加算先導１ユニット８３２及び他ビット選択ユニット８３１の入力に接続される。加算先導１ユニット８３２の出力は、経路８３３を経て、更に別の加算先導１ユニット８４２及び更に別の他ビット選択ユニット８４１の入力に接続される。加算先導１ユニット８４２の出力は、経路８４３を経て、最終的な加算先導１ユニット８５２及び最終的な他ビット選択ユニット８５１の入力に接続される。加算先導１ユニット８５２の出力は、経路８５３を経てＡＬＵ８６０の更に別の入力に接続される。
【００９４】
入力ストリーム２ユニット８３０の出力は、経路８３４を経て他ビット選択ユニット８３１の更に別の入力に接続される。同様に、入力ストリーム１ユニット８４０の出力は、経路８４４を経て他ビット選択ユニット８４１の更に別の入力に接続され、一方、入力ストリーム０ユニット８５０の出力は、経路８５４を経て他ビット選択ユニット８５１の更に別の入力に接続される。
【００９５】
他ビット選択ユニット８３１の出力は、経路８３５を経て加算先導１ユニット８３２の更に別の入力に接続される。同様に、他ビット選択ユニット８４１の出力は、経路８４５を経て加算先導１ユニット８４２の更に別の入力に接続され、そして他ビット選択ユニット８５１の出力は、経路８５５を経て加算先導１ユニット８５２の更に別の入力に接続される。デコードされたサインフラグを任意に含む他ビット選択ユニット８５１の更に別の出力は、経路８５６を経て、ＡＬＵ８６０の更に別の入力に接続される。
【００９６】
状態マシン８００の更に別の再スタート出力は、経路８０７を経て、入力ストリーム０ユニット８５０、入力ストリーム１ユニット８４０及び入力ストリーム２ユニット８３０のリセット入力に接続され、一方、状態マシン８００の同じ出力が経路８０８を経て入力３ユニット８２１及び入力４ユニット８１１のリセット入力に供給される。この再スタート出力は、各Separable_Unitの始動時に状態マシン８００によりシグナリングされる。
【００９７】
オペレーション中に、ＦＩＦＯ３からのデータは、入力デマージユニット８０５へ供給され、このユニットが発生する５つのデータストリームは、入力データストリーム０ユニット８５０、入力ストリーム１ユニット８４０、入力ストリーム２ユニット８３０、入力３ユニット８２１及び入力４ユニット８１１へ供給される。入力３ユニット８２１は、データストリームの一部分をＣＡＢＡＣデコーダ８２０へビット０データとして供給し、一方、入力４ユニット８１１は、データストリームの一部分をＣＡＢＡＣデコーダ８１０へ供給する。ＣＡＢＡＣデコーダ８１０及び８２０は、図２のエンコーダ６０及び７０へ最初に供給された信号Ｈを再生する。
【００９８】
この点において、定義されたシンタックスは、演算デコーダのためのコンテクスト選択を、その直前の記号の値から分離するので、ハードウェアデコーダは、デコーディングステージにどこかに挿入されるパイプラインステージを有してもよく、ストールを招くことはないことに注意されたい。このようなパイプラインステージの便利な場所は、Ｈが計算されるポイントである。Ｈの値は、「他ビット選択」ユニット８３１及び加算先導１ユニット８３２へ供給される。入力ストリーム２ユニット８３０は、入力デマージストリームから値Ｇを選択し、そしてそれを「他ビット選択」ユニット８３１へ供給する。他ビット選択ユニット８３１は、Ｈの値に応答してＧの値から値Ｆを発生する。加算先導１ユニット８３２は、値Ｈにより指定された位置に基づく新たな最上位ビットを加算して、３ビット値Ｆを発生する。これは、エンコーダユニット５０ないし５２により実行されるプロセスの逆である。
【００９９】
加算先導１ユニット８３２の出力に発生された３ビット値Ｆは、更に別の加算先導１ユニット８４２の第１入力及び更に別の「他ビット選択」ユニット８４１の第１入力に供給される。入力ストリーム１ユニット８４０は、値Ｅを、「他ビット選択」ユニット８４１の第２入力に供給する。「他ビット選択」ユニット８４１は、その入力に値Ｅ及びＦを取り込み、そして値Ｄを発生する。値Ｄは、加算先導１ユニット８４２の第２入力に供給され、該ユニットは、データＤに対する５ビット値をその出力に発生する。加算先導１ユニット８４２からの出力は、更に別の加算先導１ユニット８５２の第１入力及び更に別の「他ビット選択」ユニット８５１の第１入力に供給される。「他ビット選択」ユニット８５１は、入力ストリーム０ユニット８５０の出力からの信号Ｃをその第２入力に受け取る。これは、エンコーダユニット４０、４１及び４２により遂行されるプロセスの逆である。
【０１００】
又、「他ビット選択」ユニット８５１は、状態マシン８００から経路８０４を経て制御入力も受け取る。又、「他ビット選択」ユニット８５１は、状態マシン８００から経路８０４を経て制御入力も受け取る。「他ビット選択」ユニット８５１は、出力信号Ｂを発生し、これは、加算先導１ユニット８５２の第２入力に供給される。又、「他ビット選択」ユニット８５１は、「サインアウト」出力も発生し、これは、経路８５６を経て演算論理ユニット（ＡＬＵ）８６０の入力へ供給される。加算先導１ユニット８５２は、信号Ｂをその出力に発生しそしてこれをＡＬＵ８６０の更に別の入力に供給する。これは、エンコーダユニット３０、３１及び３２により遂行されるプロセスの逆である。例示の目的で、ユニット８５０、８５１及び８５２のファンクションを擬似コードで以下に示す。
【０１０１】
【０１０２】
状態マシン８００が発生する出力は、デコーダ８２０及び８１０へ供給され、経路８０６を経てコンテクスト制御データが転送される。又、状態マシン８００が発生する制御出力は、経路８０３を経てＡＬＵ８６０の更に別の入力へ供給される。状態マシン８００からの更に別の出力は、入力ストリーム０ユニット８５０、入力ストリーム１ユニット８４０及び入力ストリーム２ユニット８３０の入力に供給される再スタート信号と、入力３ユニット８２１及び入力４ユニット８１１に供給されるフラッシュ信号とを発生する。演算論理ユニット８６０が発生する出力Ａは、出力値コードであって、状態マシン８００にも供給される。デコーダは、図２に示されたエンコーダとは逆のファンクションを有効に遂行し、従って、Ｈ２６４デコーダから図２に示すエンコーダへ供給されるデータを再生する。
【０１０３】
図６に戻り、デコーダＡＬＵ８６０の振舞いを説明する。これは、本質的に、‘Ｂ’値を‘Ａ’値に変換するという点で、エンコーダＡＬＵ２０のオペレーションの逆を遂行する。テーブルのコンテクストを再び参照すれば、所与のコンテクストに対してサブユニット３０２がエンコーダにおいてイネーブルされた場合には、そのコンテクストがデコーダに使用されるときに「加算１」ユニット３１０がデコーダＡＬＵにおいてイネーブルされる。同様に、ユニット３０１がエンコードに対してイネーブルされる場合には、「任意の否定」ユニット３１１がイネーブルされる。最終的に、エンコード手順においてコンテクストに対してユニット３００がイネーブルされると、デコード手順においてそのコンテクストに対して「加算以前のNumSyms」３１２がイネーブルされる。ユニット３１１は、次の擬似コードにより説明される。
【０１０４】
【０１０５】
ユニット３００及び３０２の前記説明を読めば、ユニット３１０及び３１２により遂行されるオペレーションが当業者に明らかであろう。
【０１０６】
図９に振舞いを示すデコーダ状態マシン８００は、図５のエンコーダ状態マシン１０の振舞いに類似している。プロセスがベース／アイドル状態９００でスタートすると仮定すれば、システムは（１６ビット）記号をデコードし（９０１）、これは後続システム５へ出力される。次いで、状態マシン８００は、別の１６ビット値９１０をデコードすることが期待される。９０１でデコードされた値がUNIT_SEPARATORである場合は、デコーダは、経路９１１を経てステージ９２０へ至り、これは、出力を終了し、エンコーダの統計学的情報を再初期化し、そして入力バッファをリセットした後に、状態９００へ戻る。
【０１０７】
そうではなくて、９０１でデコードされた値がData_Block_Headerである場合は、システムは、第１データ記号をデコードし（９４０）、次いで、ステップ９１０でデコードされてカウンタ８０１に記憶されたカウント値を使用して、残りの記号を通して繰り返した後に、最終的に、状態９００に復帰する。
【０１０８】
シンタックスは、直前の記号に基づいて「分岐」判断を行わないので、１つの記号のデコーディングの若干を、次のデコーディングと重畳させ、容易なハードウェアパイプライン構成を許すことに注意されたい。例えば、ステップ９０１及び９０２が完了する前に、デコーディングをスタートすることができる。
【０１０９】
上述したように、所与のシンタックスは、ハードウェアの容易なパイプライン構成を許すが、使用できる唯一のシンタックスがこの特性を有することを意味するのではない。実際に、ここに述べるシンタックスは、全ての用途には適さないことがある。ここに述べるシンタックスでは、「データブロック」でエンコードされるべき記号の数を、データ送信の前に、エンコーダ２へ送信しなければならない。あるアプリケーションでは、この情報が前もって分からないことがあり、従って、バッファすることが不可能であるか又は少なくとも高価なバッファを伴うことになる。この制約をもたない別のシンタックスは、次の通りである。
【０１１０】
【０１１１】
このシンタックスでは、１つの１６ビット値、例えば、ゼロが予約され、そして後続値を「最後」であるとして識別する。次いで、全ての値が調整されて、それらが、予約された値を偶発的に使用しないようにする。例えば、エスケープコードを使用する他の機構が当業者に明らかであろう。ここに示す実施形態は、この又は他の別のシンタックスを使用するように変更することができる。
【０１１２】
本発明は、デコードされた到来するデータを、そのデータの部分に対してコンテクストベースの適応演算エンコーディングを使用する第２の並列エントロピーエンコード化構成へ再エンコーディングし、コンテクストの数を、Ｈ２６４規格に使用されるものから減少し、そしてコンテクストを直前のデコードされた記号とは独立したものにするようにシンタックスを選択して、デコーダが、エンコードされたデータの特定の部分をデコードするのに要する時間にあまり変化がない状態で、エンコードされたデータをデコードできるようにすることにより、最小サイズのＦＩＦＯを使用できるようにすることが明らかであろう。
【０１１３】
図２を参照して述べたものとは別のエンコーダの実施形態では、図１０に示すように、エンコーダ２における２つの単一ビットＣＡＢＡＣエンコーダユニット６０、６１及びそれに関連するストリームデータユニット６１、７１が、単一の‘ＣＡＢＡＣ’エンコーダ６０ａに置き換えられ、これは、一度に２ビットを直接エンコードし、そして単一ストリーム出力ユニット６１ａへ出力する。この単一のＣＡＢＡＣエンコーダ６１ａは、６０又は６１（コスト〜Ｏ(２)）より高価であるが（コストはほぼＯ(４)）、結合したユニットよりは若干安価であり、出力ストリームの１つに対する必要性も排除する。当然、同等の２ビットＣＡＢＡＣデコーダユニットが、図１１に示すように、マッチングデコーダ４に存在することになろう。ここで、入力デマージャー８０５ａがデータを入力３ＦＩＦＯ８２１ａに供給し、これが、次いで、データを２ビットＣＡＢＡＣデコードユニット８２０ａに供給する。これは、値Ｈの量ビットを発生し、それらは、上述したように、「他ビット選択」ユニット８３１及び加算先導１ユニット８３２へ供給される。又、このシステムを使用する実施形態は、Ｈの４つの考えられる各値が、それ自身の正確な確率値を有し、従って、より高い圧縮ファクタを与えるという点で、前記実施形態に勝る効果を有する。（前記実施形態では、Ｈの各値の確率が、Ｈを形成する２つのビットの確率の積から有効に形成され、従って、これらは、最適状態に満たない仕方で相互作用し得る。）
【０１１４】
更に別の実施形態では、図１０の２ビットエンコーダ／デコーダ実施形態が、図３に示す実施形態でなされた変更と組み合わされる（デコーダのためのマッチングユニットと共に）。この実施形態では、出力ストリームの数が丁度２つに減少され、これは、エンコーダユニット３９及び６１ａに対応する。この実施形態は、図７のマージ構造及びユニット８０、８０５を見合わせ、エンコーダユニットとデコーダユニットとの間に２つの独立したＦＩＦＯを維持するだけである。
【０１１５】
上述した実施形態では、エンコードされるべきデータの上位ビットの大半が「直接エンコーディング」機構で取り扱われ、従って、それが存在するときには、ビットごとに５０：５０の確率を仮定する。これらビットの幾つかを演算エンコーディングでエンコードすることにより、より経費のかかる実施であることを犠牲にして、圧縮比のある程度の改善を得ることができる。典型的なビデオデータの分析から、値Ｂの先導意義ビットが除去されたときには、Ｂの、次の最上位５ビット（それらが存在するとき）がゼロである典型的な確率は、次のテーブルにより要約される。
【０１１６】
【０１１７】
明らかなように、これらビットがゼロであるのは、５０：５０確率より高く、従って、ある数の次の最上位ビットを演算エンコーダ／デコーダでエンコードすることにより、高レベルの圧縮を達成することができる。しかしながら、演算エンコーディングの経費が与えられると、より多くの演算エンコード／デコードユニットの追加が、利益を急速に縮小する結果となることに注意するのが重要である。
【０１１８】
例えば、このようなビットが、エンコードされる各記号に実際に存在する確率は、テーブルの第３列に要約されたように、著しく速く低下する。ここに示す実施形態は、最上位ビットの位置を暗示するので、使用しないビットに対する記憶コストは実際上生じない。それ故、このような実施形態では、コスト効率が良いのは、演算エンコーディングを使用して、せいぜい、次の最上位値をエンコードすることだけである。
【０１１９】
図１１に示すように、概念的に簡単であるが、一般的に効率の低い別の実施形態では、値Ｂは、同程度の確率であるサインビットはさておき、単にコンテクストベースの演算エンコーダユニットを使用してエンコードされる。値Ｂは、１６ビットに分割され（１０００）、そして最上位の１５から最下位の０まで番号が付けられた各ビットは、１１１５ないし１１００で各々示されたそれ自身の各ＣＡＢＡＣユニットへ供給される。これらからの出力ストリームは、１２１５ないし１２００であり、そしてサインビット値１２１６は、それが存在するときに、上述したように、ユニット８０を経てマージされる。
【０１２０】
示唆された実施形態（例えば、図２又は図１０）のいずれかへの拡張において、Ｍ個のエンコーダを並列に使用して、エンコーディングレートを高めることができる。１６ビット記号は、ラウンドロビンの順序で、Ｍ個のエンコーダの各々に順次に送信される。同様に、各エンコーダは、順次に結果を発生する。このような構成において、幾つかの簡単化が可能となる。
ａ）増加した並行性で個々のユニットのゆっくりとしたエンコードレートが相殺されるので、個々のエンコーダ／デコーダをゆっくりと動作することができる。
ｂ）デコーダは並列に動作され、直列化ペナルティを招くことなく以前の記号をデコーディングするデコーダの状態を知ることができないので、コンテクストが簡単化される。
【０１２１】
先の実施形態において拡張する別の実施形態では、各エンコーダは、最初に入力値をＶＬＣフォーマット、好ましくは、指数関数的ゴロンへ変換する「直列化ユニット」を含ませることにより、全てのデータに対して演算エンコーディングを使用する。次いで、各エンコーダは、それ自身の演算エンコーダを使用して、一度に１ビットずつ、多数のクロックサイクルにわたり、そのＶＬＣをエンコードする。各ビット位置が、それ自身のコンテクストを有するのが好ましい。数字Ｍは、各記号をエンコードするのに必要なＶＬＣビットの平均数より大きくなるように選択され、従って、平均で、リエンコーダ及びデコーダが、非常に稀な環境はさておき、クロック当たり１記号より高速で動作することを許す。
【０１２２】
しかしながら、本発明のこれら最後の実施形態は、先の実施形態と同じ圧縮性能を達成できない。というのは、エンコーディング／デコーディングユニットが、エンコーディング／デコーディングタスク間に、依存性、ひいては、直列化を導入せずに、統計学的情報を共有できないからである。
【０１２３】
又、本発明は、他のビデオデコーディング規格、例えば、ＶＣ１、又はおそらく、オーディオデコーディング規格にも適用でき、従って、より簡単なフロントエンドのエントロピーデコーディングユニットを使用できるようにする。同様に、均一に配布されず（即ち、圧縮可能であり）そしてＦＩＦＯを経てレートフィルタ（例えば、おそらく、ある送信システムを経てバーストで受信）されねばならないデータを有する他の（非ビデオ）システムも、本発明から利益を得ることができる。
【０１２４】
以上に鑑み、本発明の概念は、次の方法にあることが明らかであろう。
エントロピーデコーディング機構をレート平滑化する方法であって、
ａ）第１のエントロピーエンコードされた表現をデコードされた表現へと変換するステップと、
ｂ）前記デコードされた表現を、データの部分に対してコンテクストベースの適応演算エンコーディングを含む並列エンコーディング機構を使用する第２のエントロピーエンコードされた機構へとエンコードするステップと、
ｃ）前記第２のエンコードされたデータをＦＩＦＯに記憶するステップと、
ｄ）前記ＦＩＦＯから第２のデータを検索するステップと、
ｅ）第２のデータをデコードされたデータへとデコーディングするステップと、
を備えた方法。
【０１２５】
この方法は、更に、ほぼ同程度の確率のデータ又は非常に発生頻度の低いデータに対して安価なエンコーディング技術を使用すると共に、他の部分に対して演算コーディングを使用することを含んでもよい。
【０１２６】
この方法は、更に、少なくとも１つの記号によりデコードコンテクストをデカップルする制御シンタックスの適用を含んでもよい。
【技術分野】
【０００１】
本発明は、エントロピーエンコードされたデータストリームの処理に係り、より詳細には、このようなデータストリームをデコードするための方法及び装置に係る。
【背景技術】
【０００２】
エントロピーエンコードされたデータストリームは、例えば、新規な“Ｈ２６４”ビデオエンコーディング規格（“ITU-T Recommendation H.264: Advanced video coding for generic audiovisual services”）のものを含む圧縮されたビデオデータストリームである。ウイジェンド氏等は、“An Overview of the H.264/AVC Video Coding Standard”（IEEE Trans. On Circuits and Systems for Video Technology July 2003）においてこの仕様書の若干短い概要を提供している。
【０００３】
ほとんどのビデオ圧縮機構は、「生」のデータ記号を、それらの発生確率を反映する表現に置き換えて、頻繁に発生する記号をより少ないビットの表現でエンコードする一方、あまり頻繁でない記号をより長い表現でエンコードするようなある形式のエントロピーエンコーディングを含む。シャノンの理論は、確率ｐをもつ記号に対する最適なビット数が−ｌｏｇ（ｐ）／ｌｏｇ（２）であると述べている。例えば、３回のうち１回の発生機会をもつ記号は、１．５８５ビットで最適に表わされる。
【０００４】
多くのエンコーディング機構は、エントロピーエンコーディングを行うために、ハフマンのシステムと同様の可変長さコーディング（ＶＬＣ）システムを使用している。このような機構は、一般に、エンコード及びデコードが非常に容易であるが、各コードの長さが常に整数のビット数であるために、一般に、シャノンにより述べられた最適状態を達成することができない。
【０００５】
ＶＬＣ機構に代わるより最近の機構は、演算エンコーディング（その紹介が、プレス氏等の“Numerical Recipes in C”、ＩＳＢＮ ０−５２１−４３１０８−５に見ることができる）、及び実質的に等価なレンジエンコーディングを含む。これら両エンコーディング機構は、実際に、記号を分数のビット数で表わすのを許すことにより、シャノンの最適状態に非常に近いものを得る、より進歩したエントロピーエンコーディング機構である。しかしながら、１つの欠点は、ＶＬＣ解決策よりもエンコード及びデコードが非常に複雑なことである。
【０００６】
新規なＨ．２６４規格、特にそのＣＡＢＡＣモード（マープ氏等の“Context-based adaptive binary arithmetic coding in the H.264/AVC video compression standard”,IEEE Transactions on Circuits and Systems for Video Technology, July 2003を参照）は、演算エンコーディングの一形式を使用している。Ｈ２６４ ＣＡＢＡＣ機構は、次のことによりプロセスをより難解なものにする。
ａ）演算エンコーダ／デコーダを使用して、値のセットではなく、２つの記号、即ち０か１だけをエンコードする。しかしながら、３つ以上の記号の選択からデコードできる演算デコーダは、構成費用も高いことに注意されたい。典型的に、Ｎ個の記号を直接取り扱うエンコーダ又はデコーダは、コストがＯ（Ｎ）となり、一方、２記号デコーダを使用して（複数のステップにわたり）Ｎ個の記号を処理するものは、コストがＯ（ｌｏｇ(Ｎ)）となる。
ｂ）エンコード／デコードされた各ビットの後にエンコーディング／デコーディングを遂行するのに使用される統計学的情報（Ｈ２６４ではコンテクストとして知られている）を更新する。
ｃ）ビットごとに選択できる多数のコンテクストを維持する。
ｄ）多数のステップを含むことのできる「デバイナライゼーション(debinarisation)」プロセスを使用することにより、デコードされた演算ビットを記号へアッセンブルする。
【０００７】
逆離散的コサイン変換（ＩＤＣＴ）パラメータの場合には、これは、意義マップをデコードし、非ゼロ記号に対してサインビットをデコードし、非ゼロ記号に対して単項ストリングデータをデコードし、そして大きな非ゼロ記号に対して指数関数的なゴロン(Golomb)データをデコードすることを含む。これらの各デコーディングステップは、演算デコーダを制御するためにフィードバックされる異なるコンテクストを選択する。
【０００８】
これらのステップをたどることにより、非常に高い圧縮比を得ることができる。しかしながら、コストペナルティがある。クロック（例えば、１００〜２００Ｍｈｚの範囲のクロックレートの）当たり１ビットを越えるものをデコードするのはハードウェアにとって不可能ではないまでも非常に困難である。並列な演算エンコーディングにおいてある程度の進歩がなされているが（コンテクストが一定に保たれると仮定すれば）、デコーディングに対してなされたと思われるものはない（スポール及びメリチャーの“Arithmetic Encoding in Parallel”を参照）。各フレームが多数の「スライス」（即ち、フレームの部分）で構成される場合には、各スライスを並列にデコードすることができるが、到来するビデオストリームがフレーム当り２つ以上のスライスを有することが保証されないので、これは、適当な解決策ではない。
【０００９】
更に、前記ｄ）で述べたように、ビデオストリームにおけるソース記号は、一般的に、多数のビットで構成され（例えば、ソース値は、１６ビット値でサインされ）、従って、ＣＡＢＡＣも、単項及びゴロンコーディングのようなＶＬＣエンコーディング機構を使用する。ビデオデータをエンコーディングするときには、システムは、最初に、各々の生の記号値をＶＬＣバイナリーエンコード化形態（Ｈ２６４では「バイナライゼーション(binarisation)」として知られた）へ変換し、これを、次いで、バイナリー演算エンコーダにより圧縮しなければならない。デコーダは、本質的に、これらのステップを逆に実行して、オリジナルのデータストリームを得る。これは、最悪のケースにおいて、演算デコーダがクロック当たり１ビットをデコードできるとしても、最終的な記号を得るのに多数のクロックサイクルを必要とする。例えば、ＩＤＣＴデータを処理するときに、クロック当たり１ビットの演算デコードレートを仮定すれば、ＣＡＢＡＣプロセスを使用して「６４」の記号値をデコードするのに３０サイクル程度を要し、一方、簡単な「＋１」値は、ＣＡＢＡＣでデコードするのに４つのクロックを要する。大きな値に関連したデコードコストは、それらの非常に低い確率により、そして非常に速いレートでデコードされるゼロ値の非常に高い確率により、相殺される。バイナライゼーションプロセスを使用してＩＤＣＴ係数（意義マップを含む）の値をエンコードするのに必要なビットの数の幾つかの例を、以下のテーブルに示す。
【００１０】
【００１１】
デコードタイミングは、ｄ）に述べたように、演算デコーダを制御するのに使用されるコンテクストデータが、以前にデコードされたビットの値に基づいて、しばしば、ビットごとに選択されることにより、更に複雑化される。これは、クロックごとに１ビットをデコードする必要がある場合に、ビットの演算デコーディング及びそのビットの値に基づくデバイナライゼーション判断ステップを同じクロック周期で行わねばならないか、或いはある種類の推論的並列デコーダを構成しなければならないことを意味する。その第１は、今日の技術では達成できないことがあり、そしてその第２は、実施コストがかかる。それ故、１００〜２００ＭＨｚで実行されるＨ２６４演算デコーダハードウェア解決策は、クロック当たり１ビットを達成しないことがあり、タイミングの問題を更に悪化させる。
【００１２】
圧縮されたビデオストリームは、充分な指定平均データレート、例えば、高鮮明度ビデオ（即ち、１９２０ｘ１０８０ピクセル＠３０ｆｐｓ）に対して５０Ｍビット／ｓを有するが、このビデオストリームにおける瞬時データレートは、フレームごとに著しく変化する。イントラ・エンコード化として知られている幾つかのフレーム（即ちＩ−フレーム）は、一般に、大きなデータを有するが、予想フレーム（Ｐ−フレーム）及び両方向フレーム（Ｂ−フレーム）は、以前にデコードされたフレームからデータを借りるので、遥かに少ないビットしか必要としない。例えば、４０Ｍビット／ｓでエンコードされる所与のサンプルビデオストリームでは、各Ｉ−フレームが、典型的に、ほぼ３Ｍビットを必要とし、Ｐ及びＢ−フレームは、各々、そのサイズのほぼ１／２及び１／３である。５０Ｍｂ／ｓの最大レートを使用するビデオストリームをデコードできるハードウェアＣＡＢＡＣデコーダ（例えば、１００〜２００ＭＨｚで動作する）を形成することは困難ではないが、従来のデコーダは、そのデータを定常のフレームごとのレートで発生しない。
【００１３】
各ビデオフレームの処理コストが、エントロピーエンコードされたデータに単純に依存する場合には、解決すべき問題はない。しかしながら、処理レートが更に固定された処理部分がある。例えば、ＩＤＣＴ計算、モーション補償、及びデリンギング／デブロッキングユニットは、一般に、処理されるピクセルの数に依存する時間を必要とする。これらのユニットは、処理時間がより一定であるので、実際には、著しく変化し得るソースプロジューサ、即ちエントロピーデコーダにより供給される比較的固定レートのコンシューマプロセス、即ちバックエンドビデオプロセッサが存在する状況となる。
【００１４】
例えば、ハードウェア解決策は、〜４００クロックサイクルにおいて３８４個のピクセルより成るＨ２６４マクロブロックに対してＩＤＣＴ処理を遂行する。エントロピーデコーダにより供給されるこのデータのパラメータは、マクロブロック領域における映像の複雑さに基づいて０から３８４個までのいずれかの数の記号を有し、従って、エントロピーデコードされるべきクロックサイクルがゼロから数千個までのいずれかとなる。
【００１５】
これは、処理レートの不一致のために、非常に頻繁に、あるユニットが他のユニットによりストールされるときの状況を招く。その結果、フレーム／秒での全処理レートが２の瞬時最小値に低下し、これは、システムが必要なデコーディングフレームレートを満足しないことを意味する。前記のＩＤＣＴの例を再び見ると、エントロピーエンコーダがクロック当たり１記号のレートで各記号をデコードできる場合には、問題が生じない。
【００１６】
上述したように、エントロピーデコーダをより速く動作することは（不可能でないまでも）実際的ではなく、コンシューマユニットをより速く動作することは、非常に経費高となる。これらの状況における明らかな昔ながらの慣習は、プロデューサとコンシューマとの間にレート平滑ＦＩＦＯを導入することである。この一般的なやり方は、３Ｄグラフィック処理チップからハードディスクコントローラまでの装置に広く使用されている。
【００１７】
簡単なＦＩＦＯは、問題を「解決」するが、データレートを有効に平滑化するのに多数のフレームの価値あるデータを含む必要があるという不便さがある。これは、典型的に、バッファが外部メモリであるように強制し、これは、大量のＲＡＭとタイアップするだけでなく、バッファの書き込み及び読み取りに著しい帯域巾を消費することも意味する。初期のビデオ規格は、ハフマン／ＶＬＣエンコーディングを使用し、これは、クロック当たり１記号のレートで容易にエンコード及びデコードすることができ、従って、非常に明らかな選択肢は、このようなエンコーディング機構を使用して、ＦＩＦＯへの入力のデータを再圧縮し、次いで、その圧縮されたデータを再び出口で解凍することである。実際に、多数の規格を取り扱うビデオエンコーディング／デコーディングチップでは、このようなＶＬＣハードウェアがとにかく存在する。この幾分か簡単な解決策は、リンザー及びレウン氏によって説明されていると思われる（米国特許第６，９２７，７１０号）。
【００１８】
それに関連する機構がシューマン氏により説明されている（米国特許出願第２００４０２６０７３９号）。この方法では、データを直ちに「デバイナライズ」するのではなく、ＣＡＢＡＣ演算デコーダから出力される「バイナライズ」されたビットがＦＩＦＯに送り込まれ、次いで、ＦＩＦＯの他端には、（第２の）デバイナライゼーションユニットが配置されている。（正しいコンテクストを選択するためには演算デコーダユニットの付近に部分的デバイナライゼーションユニットが依然必要とされることに注意されたい。）バイナライズされたデータ（即ち、例えば、依然として、意義マップ＋単項＋ゴロン形態でエンコードされたデータ）は、依然、合理的に充分に圧縮されたフォーマットである。不都合なことに、この方法に伴って生じ易い問題は、単一のクロックサイクルで各記号を解凍できるようにするために非常に大きなビットウインドウ及び複雑なハードウェアが必要になることである。これは、上述したＩＤＣＴバイナライゼーションコストテーブルから明らかである。
【００１９】
最後に関心のあるものは、Ｈ２６４ビデオストリームにおいてＣＡＢＡＣユニットからデコードされる典型的な値の検討である。特に関心のあるのは、ＩＤＣＴ係数である。というのは、これらは、通常、膨大な量のデコードされたデータを作り上げるからである。次のテーブルは、典型的なＨ２６４高鮮明度ビデオストリームからサンプリングされたＩＤＣＴの値及び確率を示す。確率と共に最適な記憶コストがリストされている。
【００２０】
【００２１】
ＩＤＣＴ値の各ブロックでは、多くの高周波数項がゼロになる見込みが非常に高い。高周波数の隣接するゼロが除去される（何らかのまだ未指定の手段により）場合には、テーブルが次のようになる。
【００２２】
【００２３】
残りのゼロを何らかの手段により（例えば、ラン・レベル又はおそらく意義マップエンコーディングの使用を経て）暗示できる場合には、非ゼロ値の確率が次のようになる。
【００２４】
【００２５】
これらの非常に一般的な値が、各記号を表わすのに整数個のビットを使用しなければならないハフマンのような簡単なＶＬＣエントロピー機構を使用してエンコードされる場合には、最適なものとは懸け離れたものになることが明らかである。というのは、非常に一般的な±１の値に対する最良の適合が２ビットであり、理想的な状態に対して記憶コストの約２５％の増加を表わすからである。
【発明の概要】
【発明が解決しようとする課題】
【００２６】
上述したように、演算エンコーディングは、分数個のビットで記号を表すことができ、潜在的に高い圧縮レベルを導くという点で、ＶＬＣ／ハフマン解決策よりも優れている。問題は、適応できる機構は、若干シーケンシャルにデコードできるものであり、従って、クロック当たりに１つの完全な（マルチビット）記号というピークレートの達成を困難にすることである。
【００２７】
デコードされたデータのプロデューサとコンシューマとの間にレート平滑ＦＩＦＯを導入することができるが、これが単純な形態で表わされる場合には、非常に大きなＦＩＦＯを必要とすることになる。ＦＩＦＯへ送られるデータに圧縮機構を適用して、ＦＩＦＯに必要なサイズを減少することはできるが、ＦＩＦＯの必要サイズを更に減少するために既知の圧縮機構の効率を高めることが望まれる。
【課題を解決するための手段】
【００２８】
第１の態様において、本発明は、コンテクストベースの適応演算エントロピーコード化データをデコーディングする方法であって、
ａ）エンコードされたデータをデコーディングして、第１のデコードされたデータを発生するステップと、
ｂ）記号の少なくとも一部分に対してコンテクストベースの適応演算エンコーディングを含む並列エンコーディング機構を使用して前記デコードされたデータをエントロピーエンコーディングして、第２のエンコードされたデータを発生するステップと、
ｃ）前記第２のエンコードされたデータを先入れ先出し（ＦＩＦＯ）メモリに記憶するステップと、
ｄ）前記第２のエンコードされたデータをＦＩＦＯメモリから読み取るステップと、
ｅ）ＦＩＦＯメモリから読み取ったデータをデコーディングして、デコードされたエントロピーコード化データである第２のデコードされたデータを発生するステップと、
を備えた方法を提供する。
【００２９】
前記ステップｂ）において、エンコーダは、Ｎビット記号をエンコードし、この記号は、複数のストリームに分割され、そしてそれらストリームの少なくとも２つは、対応する数の演算エンコーディングユニットを使用して並列にエンコードされる。
【００３０】
本発明は、
ａ）最大エンコードサイズを小さく保持することができ、
ｂ）演算エンコーディングを使用することによりＶＬＣ方法より高い圧縮比を得ることができ、そして
ｃ）ほとんどの環境の下で、クロック当たり１つ（多ビット）の記号というデコード／エンコードレートを達成することができる。
【００３１】
本出願は、クロック当たり１つの記号というレートを実質上保証しつつも、相応の圧縮比を達成する演算エンコーディング及びデコーディングを使用してＦＩＦＯデータを圧縮及び解凍する方法を説明する。これは、エンコード／デコードプロセスの少なくとも一部分を並列化することにより、そしてある実施形態では、以前にデコードされた記号から記号に対するコンテクスト選択をデカップルすることでシステムのパイプライン動作を改善することにより、行われる。更に、「言語シンタックス」をリエンコーダ−デコーダのトップに適用して、Ｈ２６４ビデオストリームの多数の部分及び他のビデオ規格（簡単なＶＬＣコードを使用するものでも）によりそれを使用できるようにし、これは、ひいては、これらデコーディングユニットに対するタイミング制約を容易にすることができる。
【００３２】
この説明及び特許請求の範囲において、「演算コーディング」という語は、（特定の実施形態の特定の細部に関するものを除いて）レンジコーディングを含むものと解釈されない。
【００３３】
エンコーダは、Ｎビットの数値である「記号」を受け入れ、そしてそれを単一クロックにおいてエンコードすることができる（非常に稀な環境を除いて）。このプロセスの一部分として、記号は多数のストリームに分割され、それらストリームの少なくとも２つは、多数の演算エンコーディングユニット、又は演算及びＶＬＣエンコーディングの組み合わせで並列に圧縮される。他の実施形態では、演算エンコーディングに代わってレンジエンコーディングを使用することができる。というのは、それらが非常に類似しているからである。各ストリームの出力は、外部メモリに存在できるＦＩＦＯ（１つ又は複数）へ送信される。マッチングデコーダは、ＦＩＦＯからのデータを受け入れ、そしてオリジナルの記号を再デコードし、アッセンブルする。
【００３４】
第２の態様において、本発明は、コンテクストベースの適応演算エントロピーエンコードデータをデコーディングする装置であって、エンコードされたデータをデコーディングして、第１のデコードされたデータを発生する第１デコーダと、その第１のデコードされたデータをエンコードするためのエンコーダであって、デコードされたデータの少なくとも一部分に対してコンテクストベースの適応演算エンコーディングを含む並列エンコーディング機構を使用して、第２のエンコードされたデータを発生するエンコーダと、その第２のエンコードされたデータを記憶するための先入れ先出し（ＦＩＦＯ）メモリと、前記第２のエンコードされたデータをＦＩＦＯの出力から読み取り、そしてその第２のエンコードされたデータをデコーディングして、デコードされたコンテクストベースの適応演算エントロピーエンコードデータを発生するためのデコーダと、を備えた装置を提供する。
【００３５】
エンコーダは、Ｎビット記号をエンコードするように構成され、この記号は、複数のストリームに分割され、そしてそれらストリームの少なくとも２つは、対応する数の演算エンコーディングユニットを使用して並列にエンコードされる。
【００３６】
エンコーダは、特定のシンタックスを解釈して、処理されているシンタックスエレメントに基づき演算エンコーダのコンテクストを選択するように構成された状態マシンを含み、シンタックスは、コンテクストが以前の記号に依存しないよう確保するために選択される。
【００３７】
デコーダは、特定のシンタックスを解釈して、処理されているシンタックスエレメントに基づき演算デコーダのコンテクストを選択するように構成された状態マシンを含み、シンタックスは、コンテクストが以前のデコードされた記号に依存しないよう確保するために選択される。
【００３８】
前記装置は、単一のＦＩＦＯを備え、前記エンコーダは、エンコードされたデータストリームを、ＦＩＦＯへ書き込む前に、インターリーブするための手段を備え、そして前記デコーダは、ＦＩＦＯから読み取ったデータストリームをデインターリーブするための手段を備えている。
【００３９】
前記エンコーダは、可変長さコード化機構を使用して、同程度の確率の見込みがあるか又は存在する見込みが少ない各記号を表わすデータビットの部分をエンコードするための手段を備えている。
【００４０】
これは、必要とされる演算エンコーダ／デコーダの数を減少することによりエンコーダ／デコーダのコストを最小限にすることができる。
【００４１】
本発明の前記及び他の特徴並びに効果は、添付図面を参照した本発明の実施形態の以下の説明から明らかとなろう。
【図面の簡単な説明】
【００４２】
【図１】本発明によるデコーダのブロック図である。
【図２】本発明によるデコーダに使用するためのエンコーダユニットの第１実施形態のブロック図である。
【図３】ハードウェアコストを節減する、本発明によるデコーダに使用するためのエンコーダユニットの第２実施形態のブロック図である。
【図４】制御シンタックス要素のビットエンコーディングの一例を示す図である。
【図５】図４のシンタックスで表わされたデータを処理するためのエンコーディング状態マシンの実施形態を示す図である。
【図６】図２又は図３のエンコーダ（及びマッチングデコーダ）に使用するためのＡＬＵユニットの実施形態を示す図である。
【図７】単一のＦＩＦＯが使用されるときのデータをインターリーブする構成を示す図である。
【図８】図２に示すエンコーダに対するマッチングデコーダの実施形態のブロック図である。
【図９】図４のシンタックスで表わされたデータを処理するためのデコーディング状態マシンの実施形態を示す図である。
【図１０】一度に２ビットをエンコードする演算エンコーダを使用する図２及び図３の実施形態の変形を示す図である。
【図１１】図１０に示すエンコーダによりエンコードされたデータをデコーディングするためのデコーダの実施形態を示す図である。
【図１２】演算エンコーディングのみを使用するエンコーダの別の実施形態を示す図である。
【発明を実施するための形態】
【００４３】
図１は、本発明の実施形態をブロック図の形態で示す。圧縮されたデータが上流のデコーダユニット１へ供給される。このデコーダユニットは、例えば、Ｈ２６４ビデオエンコーディング規格に規定されたものでよい。デコーダ１から供給される値は、予想されるシンタックスにフォーマットされ、リエンコーダユニット２へ１６ビット値のストリームとして入力される。リエンコーダ２は、これらの値を圧縮し、その結果を「先入れ先出し」（ＦＩＦＯ）メモリ３へ出力する。ＦＩＦＯ３は、単一のＦＩＦＯではなくＦＩＦＯのセットでもよい。デコーダユニット４は、ＦＩＦＯ３から圧縮されたデータを読み取り、そのデータを再拡張して、オリジナルデータストリームを得、そしてそれを出力５へ通す。特定記号のエンコーディングとデコーディングとの間には、ＦＩＦＯ３にどれほど多くのデータが維持されるかに基づいて、可変時間遅延が生じることが明らかである。本発明の目的は、パイプラインのストールを防止し、又は少なくとも必要なフレームデコードレートを満足するシステムを停止するストールを防止する最小サイズのＦＩＦＯを割り当てできるようにすることである。実際に、その構成体は、中央処理ユニットがＦＩＦＯ３におけるデータの量を監視できるようにするための手段を含むことができる。
【００４４】
本発明に使用するのに適したエンコーディングユニット２の実施形態を、図２を参照して以下に説明する。図２に示すように、上流のデコーダユニット１は、１６ビット値Ａをエンコーダユニット２に供給する。この１６ビット値Ａは、経路１３を経て状態マシン１０の第１入力に供給され、そして経路１４を経て演算論理ユニット（ＡＬＵ）２０の第１入力に供給される。１６ビット値の幾つかは、後続データの解釈を制御するためにシンタックスにより使用される。状態マシン内には、ｎビットカウンタ１１（ｎは、例えば、９である）と、以前の「記号数」を記憶するためのメモリ１２がある。実際には、考えられるエンコーディングモードの各々に対応する多数の「以前の記号数」レジスタがある。状態マシン１０は、ＡＬＵ２０によって遂行されるオペレーションを含むリエンコーダ２における種々のサブユニットの振舞いを制御する。従って、状態マシン１０からの出力は、ライン１５を経てＡＬＵ２０の第２入力に供給され、そしてライン６を経て「他のビット選択」ユニット３１の第１入力に供給される。
【００４５】
ＡＬＵ２０は、１６ビット値Ａを受け取り、そしてそれに対して状態マシン１０の制御の下で動作して、２つの出力を発生する。サインフラグである第１出力は、ライン２１を経て「他のビット選択」ユニット３１の第２入力に供給され、一方、非サインの１６ビット値Ｂは、ライン２２を経て先導１検出器３０に供給され、該検出器は、最上位ビットの位置を決定し、そしてそれを範囲（０から１６）の５ビット値Ｄとしてエンコードする。例えば、Ｂが０の場合には、Ｄも０であるが、Ｂが０ｘ１２の場合には、Ｄが５となる。値Ｂは、先導１検出器３０から経路３３を経て「他のビット選択」ユニット３１の更に別の入力へ供給され、一方、値Ｄは、先導１検出器３０から経路３４を経て「他のビット選択」ユニット３１の更に別の入力に供給される。「他のビット選択」ユニット３１は、ライン３３を経て与えられたＢ値から最上位ビットを剥離し、そしてライン２１を経て受け取られたサインフラグを他のビットに付加して、値Ｃを発生する。この振舞いは、次のＣ擬似コードにより正確に記述される。
【００４６】
【００４７】
それにより得られて、値Ｃを作り上げるビット数は、０ないし１６のいずれかであり、それらは、ライン３５を経て「出力ストリーム０」ユニット３２へ出力される。これは、ビットを収集して、全パケットを、経路３８を経て出力マージユニット８０へ出力する小型ＦＩＦＯでよい。
【００４８】
これは、次のことを除いて、Ｈ２６４規格で使用される指数関数的ゴロンエンコーディング機構における変形として見ることができる。
ａ）減算ユニットを必要とせず、従って、ハードウェアで実施するのが非常に低廉である。
ｂ）Ｂの長さ、即ちＤ値は、単項エンコーディング方法ではエンコードされず、むしろ、別のエンコーディングユニットへ通される。
ｃ）小さな値を好むエンコードされたデータの長さには若干の相違がある。
【００４９】
先導１検出器３０により発生された値Ｄは、ライン３６を経て小さな先導１検出器４０の入力に供給され、この検出器は、範囲（０から５）の３ビット値Ｆを生成する。値Ｄは、先導１検出器４０から経路４６を経て更に別の「他のビット選択」ユニット４１へ供給される。又、値Ｆは、先導１検出器４０から経路４３を経て「他のビット選択」ユニット４１へも供給される。ここでも、「他のビット選択」ユニット４１は、Ｄの最上位ビットを除去し、残りのビットＥを、ライン４４を経て出力ストリーム１ユニット４２へ出力するが、Ｆ＝５、即ちＤ＝１６、従って、Ｅが０で、出力する必要がない特殊なケースは除く。この振舞は、次の擬似コードにより記述される。
F = FindLeading1Position(D);
IF((F < 2 ) OR (F==5))
{
NumBitsToOutput = 0;
}
ELSE
{
NumBitsToOutput = F 1;
}
Output(D, NumBitsToOutput, Stream1);
【００５０】
出力ストリーム１ユニット４２の出力は、更に、経路３８を経て出力マージユニット１８へ供給される。
【００５１】
先導１検出器４０からの３ビット値Ｆは、経路４５を経て先導１検出器５０の入力に供給される。先導１検出器５０は、範囲（０から３）の２ビット値Ｈを発生する。３ビット値Ｆは、先導１検出器５０から経路５３を経て更に別の「他のビット選択」ユニット５１へ供給される。更に、２ビット値Ｈは、経路５４を経て「他のビット選択」ユニット５１へ供給される。「他のビット選択」ユニット５１は、暗示されたビット（先導１を含む）を除去して、出力Ｇを発生する。Ｆの限定入力値のために、出力Ｇは、単一ビット値を有し、ライン５５を経て出力ストリーム２ユニット５２へ供給され、従って、エンコードされる各記号に対して最大１ビットが必要とされる。これは、次の擬似コードにより記述される。
H = FindLeading1Position(F);
If(H < 2 )
{
NumBitsToOutput = 0;
}
Else
{
NumBitsToOutput = 1;
}
Output(F, NumBitsToOutput, Stream2);
【００５２】
これは、次のテーブルにより要約することができる。
【００５３】
２ビット値Ｈは、その後、演算エンコーディングを使用してエンコードされるので、Ｇ及びＨへのＦのエンコーディングが別の仕方で選択される場合には、システムがより効率的に機能できる。このため、「先導１検出器」５０及び「「他のビット選択」ユニット５１の別の実施形態では、次のエンコーディングが、次のテーブルにより要約されるように使用される。
【００５４】
【００５５】
この別の実施形態に対してデコーダ４に相補的なユニットが存在しなければならないことに注意されたい。
【００５６】
別の実施形態では、両エンコーディング方法が、エンコーダ（及びデコーダ）に合体され、そして各状態マシンは、現在エンコーディングモード及びエンコードされるべきシンタックスエレメントに基づいて必要なエンコーディング及びデコーディング方法を選択する。
【００５７】
値Ｈの２ビットは、先導１検出器５０から経路６２を経てコンテクストベースのバイナリー演算エンコーダ６０の第１入力へ供給され、そして経路７２を経て更に別のコンテクストベースのバイナリー演算エンコーダ７０の第１入力へ供給される。これらのエンコーダは、維持されるコンテクストの数が著しく減少される以外、Ｈ２６４エンコーダに使用されるものと同様である。エンコーダ６０及び７０のコンテクスト制御は、状態マシン１０により発生されて、経路１７を経てエンコーダ６０及び７０の第２入力に供給される。エンコーダ６０及び７０からの最終的なビットストリームは、各出力ストリームユニット６１及び７１を経、経路７５を経て、出力マージユニット８０へ供給される。出力マージユニット８０の出力は、エンコードされたデータであり、ＦＩＦＯ３の入力に供給される。
【００５８】
図３に示す別の構成において、図２に示した実施形態は、出力ストリーム０ユニット３２、出力ストリーム１ユニット４２及び出力ストリーム２ユニット５２を、少量のビットシフトハードウェアを使用してＣ、Ｅ及びＧ信号を連結する単一の出力ストリームユニット３９に置き換えることにより変更される。これは、実施コストを減少することができる。この変更は、ＡＬＵ２０のような図２の実施形態の無関係な部分には影響しないことに注意されたい。
【００５９】
状態マシン１０、ＡＬＵ２０、並びにエンコーダユニット６０及び７０の更に詳細な説明に進む前に、データストリームに対する支配シンタックスを見ることが重要である。これは、それ自体、制御値及びエンコードされるべき記号より成る１６ビット値のストリームに過ぎない。これは、次のＥＢＮＦ（Extended Backus-Naur Form）表現により最良に要約される。
【００６０】
【００６１】
図４に示すように、好ましい実施形態では、“UNIT_SEPARATOR”１００、“Data_Block_Header”１０１及び“NumSymbolsLess1”１０２も、「１６ビット」値である。この実施形態では、“UNIT_SEPARATOR”トークンは、１６ビット値、０ｘ３としてエンコードされる。“Data_Block_Header”トークン１０１は、２つのフィールド、即ち１４ビットの“Hardware_Code”値１０１ａ、及び２ビットの“encoding mode”フィールド１０１ｂより成る。この後者のフィールドは、３つの考えられる値を次のようにエンコードする。
【００６２】
【００６３】
所与のエンコーディングでは、“UNIT_SEPARATOR”及び“Data_Block_Header”は、最後の２ビットが常に異なるので、互いに間違えることはあり得ない点に注意されたい。又、これらの値は、数字的にできるだけ小さくなるように選択される。というのは、圧縮システムが小さな値を好むので、これが圧縮効率を改善するからである。
【００６４】
“HW_CODE”値は、エンコーダ／デコーダモジュールの各側でユニットにより使用するための任意のフィールドであるが、可能な限り小さな値が選択されることが推奨される。“Data_Block_Header”は、RUN_LEVEL_PAIR、SIGNED、又はSIG_MAP_VALUESの１つであるエンコーディング方法を含む。これらの名前は、おそらくそれらの意図された使い方を表すが、汎用性も高い。別の実施形態では、SIG_MAP_VALUESモードは、除去されてもよいし、又は優勢な大きな記号値を見込むもののような別のエンコーディング機構と置き換えてもよい。別の実施形態に対する他の組合せ又はエンコーディングパターンは、当業者に明らかであろう。
【００６５】
RUN_LEVEL_PAIRモードは、ペアのリストより成るデータに対して最適なものとされ、各ペアは、非サイン値と、それに続く（非ゼロ）サイン値で構成される。SIGNEDモードは、単に、サイン値のリストで構成され、そしてSIG_MAP_VALUESは、単一の非サイン値と、それに続く（非ゼロ）サイン値のリストで構成される。全てのケースにおいて、小さな値がデータを支配することが一般的に予想される。
【００６６】
これらのエンコーディング方法は、供給された記号リストをどのように処理するか、例えば、ＡＬＵ２０がどんなオペレーションを遂行すべきか、且つＣＡＢＡＣエンコーダユニット６０及び７０にどんなコンテクストを使用すべきか選択することを状態マシン１０に命令する。
【００６７】
“Separable_Unit”論理的グループ分けの目的は、システムがＦＩＦＯにおける圧縮されたデータに再同期ポイントをもつのを許すことである。状態マシン１０のエンコーダは、各“Separable_Unit”の後に、経路１８を経て内部バッファの出力ストリーム０ユニット３２、出力ストリーム１ユニット４２及び出力ストリーム２ユニット５２をフラッシュし、そして経路１９を経て出力３ユニット６１及び出力４ユニット６２をフラッシュし、必要に応じて、デコーダによりこれらを順にスキップできるようにする。例えば、Ｈ２６４では、フレームは、ある数の独立した「スライス」より成り、これらは、送信データが崩壊した場合に部分エラー回復を許すように意図される。スライスが“Separable_Unit”にパックされる場合には、デコーダ及びパイプラインの残りの部分によりそれを完全にスキップすることができる。この機構は、多数の異なるストリームを、例えば、スライスレベルで混合するのも許す。
【００６８】
各“Separable_Unit”内のデータは、Data_Blockの任意のリストより成り、その各々は、使用すべきエンコーディングの方法と、エンコードされるべき記号の数（１未満）と、ブロックにおいてエンコードされるべき記号とを記述するヘッダを含む。Data_Blockは、典型的に、ＩＤＣＴ係数のブロックのような記号の論理的グループに対して使用されるか、又はマクロブロックに属するモーションベクトル値のセットに対して使用される。
【００６９】
エンコーダのための状態マシンの概略が図５に示されている。プロセスがベース／アイドル状態２００でスタートすると仮定すれば、次の予想されるデータアイテムは、“UNIT_SEPARATOR”又は“Data_Block_Header”である。これらの値のいずれかが受け取られると、デコードプロセスについて考慮するときに明らかとなる理由で、それが全く同様にエンコードされる（２０１）。状態マシン１０は、状態２０２へ進む。これら記号の後に、常に、「非サイン」の１６ビット値が続き、これは、任意の値であるか、又はそれに続くデータの長さを表す。又、これらの値は、両方とも同様にエンコードされる（２１０）。以前の記号が“UNIT_SEPARATOR”であった場合には、経路２１１が取られ、状態マシン１０は、“Separable_Unit”のエンコーディングを終了し、演算エンコーダのコンテクスト／統計学的情報をリセットし、そしてバッファ２２０をフラッシュするようにエンコーダに通知する。これは、多数のクロックサイクルを要するが、非常に頻度の低いオペレーションであることが予想されるので、全コストを無視できる。これを達成するために、状態マシン１０は、経路１８を経てバッファ３２、４２、５２のコンテンツを空にし、経路１９を経てバッファ６１及び７１のコンテンツを空にし、且つ経路１７を経てエンコーダ６０及び７０のコンテクスト統計学的情報をリセットするためのインストラクションを発行する。
【００７０】
そうではなく、“Data_block_header”が状態２０１において受け取られた場合には、状態マシン１０は、経路２１２をたどり、少なくとも１つのデータ記号２３０を受け取ることを期待する。これは、“Data_block_header”に定義されたモードを使用してエンコードされる（２４０）。同時に、状態マシン１０の内部カウンタ１１がモードに基づいて初期化される。モードが“SIGNED”又は“SIG_MAP”である場合には、それが、供給されたNumSymbolsLess1にセットされ、さもなければ、NumSymbolsLess1*2+1にセットされる。後者が行われるのは、“RUN_LEVEL”値が常にペアで供給されて、その供給された値から冗長ビットを除去するからである。次いで、状態２７０及びプロセス２８０は、データブロックで供給された残りの記号をエンコードした後に、ベース状態２００に復帰する。プロセス２０８は、状態マシン１０のカウンタ１１を減少させ、従って、データブロックの全ての記号がエンコードされたときにベース状態２００に到達する。
【００７１】
ＡＬＵ２０の制御と、演算エンコーダ６０、７０の振舞いを支配するコンテクスト情報とについて、以下に説明する。文字通り数百のコンテクストを有するＨ２６４ ＣＡＢＡＣとは異なり、好ましい実施形態は、６個のコンテクストグループのセットしか有していない。各グループは、２つのＣＡＢＡＣユニットの各々について１つの、一対のコンテクスト値を有する。（コンテクストとは、全ての意図及び目的で２つのバイナリー値０及び１の現在の確率を記憶する。Ｈ２６４ ＣＡＢＡＣ設計では、これが８ビット値にパックされる。実施が容易であるために、同じ機構が実施形態により使用されてもよい。）
【００７２】
又、各グループには、ＡＬＵ２０により実行されるオペレーションに対する設定も関連付けられる。これらのオペレーションを、図６を参照して以下に説明する。到来するデータ値Ａに対して実行されて出力値Ｂを発生することのできる任意のオペレーションが３つある。この図において、これらは、３つの直列ステージとして説明されることに注意されたい。これは、単に明瞭化のために行われるが、ハードウェアシステムは、これらオペレーションを結合してもよく、そのようにした場合には、面積が減少され及び／又はタイミングが改善される。オプションがイネーブルされない場合には、そのオプションへの入力が、その出力へ通される。
【００７３】
第１のオプション３００は、到来する値Ａから以前のNumSymbolsLess1値１２を減算して、Ａ’を発生する。「Ｃ擬似コード」では、このオペレーションは、次の通りである。
IF(option_300_enabled)
{
A' = A Prev_NumSyms;
}
ELSE
{
A' = A;
}
【００７４】
第２の任意のオペレーション３０１は、その入力Ａ’の絶対値を計算し、そしてオリジナルサイン値フラグも出力する。「Ｃ擬似コード」では、このオペレーションは、次の通りである。
【００７５】
【００７６】
最終的に、オプション３０２は、入力値Ａ”から１を減算し、最下位１６ビットを保持する。「Ｃ擬似コード」では、このオペレーションは、次の通りである。
IF(option_302_enabled)
{
B = (A'' 1) & 0xFFFF;
}
ELSE
{
B = A'';
}
【００７７】
ＡＬＵに対する６個のコンテクストグループ及びそれらの設定は、次のテーブルに要約される。
【００７８】
【００７９】
各“Separable_Unit”の始めにコンテクストに指定される、コンテクストのための初期確率値は、例示のために示されたものに過ぎない。好ましい実施形態では、これらの値は、例えば、ＣＰＵによりプログラムできるレジスタのセットから得られる。又、例示値は、ＳＩＧＭＡＰエンコードモードを要求しない実施形態により生成されたものであり、従って、それに対する初期確率は含まれない。
【００８０】
コンテクストグループと図５に示す状態との関係を以下に説明する。
状態２０１において、「ヘッダ」グループが選択される。
【００８１】
状態２１０において、「デルタ長さ」グループが使用される。テーブルから明らかなように、供給された「長さ１」値が以前の値から減算され、その結果の絶対値が取り出される。この結果（及び減算結果のオリジナルサイン）がエンコードされる。
【００８２】
状態２４０及び２８０において、ヘッダデータで指定されたエンコーディングモードに基づいて残りの４つのコンテクストグループ‘S’、‘RL_U’、‘SM_M’又は‘S_NZ’の１つを使用して記号値がエンコードされる。‘SIGNED’モードを使用してエンコーディングするときには、データブロックにおける全ての残りの値に対して‘S’グループが使用される。
【００８３】
‘RUN_LEVEL’モードでエンコードするときには、選択されたグループが‘RL_U’と‘S_NZ’との間で交替し、一方、‘SIGMAP’モードの場合には、第１記号が‘SM_M’モードでエンコードされ、そして残りが‘S_NZ’でエンコードされる。
【００８４】
実施形態により多数のストリームが発生されるときには、単一のＦＩＦＯを有するのが好ましい。というのは、これは、システムが利用可能な外部メモリ空間を先験的に多数の固定サイズのＦＩＦＯに分割する必要がないことを意味するからである。従って、単一の外部ＦＩＦＯが存在する実施形態では、エンコーダにおいて種々の出力ストリームをインターリーブし、次いで、デコーダへデータが読み込まれるときにそれらをデインターリーブする効率的な手段があるのが好ましい。これは、実際には、多数の理由で、重要なタスクである。
ａ）ストリームは、各々、記号当り異なる数のビットを発生し、
ｂ）特定の記号‘ｘ’に対して、‘Ｃ’、‘Ｅ’及び‘Ｇ’に対応するビットは、ほとんど即座に発生されるが、演算エンコーダは、それらのエンコードされたビットを、ある数の記号の後まで発生しないことがある。ある状況において、これは、数十又は数百個の記号の後であり、そして
ｃ）記号のデコーディングを開始するために、ストリームに対する全ての関連データがデコーダにおいて同時に入手できねばならない。
【００８５】
更に、メモリサブシステムは、効率的に使用されねばならない。多くのシステムでは、これは、読み取り及び書き込みをあるサイズのバーストで行わねばならないことを意味し、これは、数十ないし数百のバイトを必要とすることがある。例えば、個々のバイトをランダムにアクセスすることは、効率的でない。
【００８６】
この問題に対する解決策を、図７を参照して以下に述べる。この実施形態ではサイズが約４ＭバイトであるＦＩＦＯメモリ５００は、固定サイズの「割り当てブロック」５０１へ論理的に分割され、各ブロックは、最小の効率的メモリ転送バーストサイズの倍数となるように選択されるのが好ましい。好ましい実施形態では、各ブロックは、サイズが２５６ビットである。ＦＩＦＯメモリに対する３つの「ポインタ」が維持される。「分離可能ユニットヘッド」５１０は、エンコーダ２によって現在記憶されている分離可能ユニットのためのデータの開始を指す。「分離可能ユニットテール」５１１は、デコーダ４により現在処理されている分離可能ユニットの開始を指す。これが「分離可能ユニットヘッド」ポインタと同じように前進する場合には、デコーダは、エンコーダがその現在の分離可能ユニットを終了するまでストールする。
【００８７】
「フリーブロックポインタ」５１２は、エンコーダがその出力ストリームの１つから新たなブロックの価値あるデータを発生するときに増加される。これがＦＩＦＯメモリブロックの終りに到達すると、開始点へラップアラウンドする。「フリーブロックポインタ」が「分離可能ユニットテール」に到達する場合には、ＦＩＦＯがいっぱいになったと考えられ、エンコーダは、デコーダがその現在分離可能ユニットを終了するまでストールし、そしてポインタを、次に記憶された分離可能ブロックの開始点へ前進させる。
【００８８】
各割り当てブロックは、データ部分５１２及び「次」のポインタ５１３を含む。好ましい実施形態では、「次」のポインタは、１６ビット値である。これは、ブロックのチェーンにおいて「次」の割り当てブロックをインデックスし、次のように使用される。
【００８９】
Ｎ個の出力ストリームをもつ実施形態のマージユニット８０内で、新たな「分離可能ユニット」の開始に、最初のＮ個の割り当てブロックが、現在の分離可能ブロックの開始点（「フリーブロックポインタ」に等しい）に対して、Ｎ個のストリームに予め指定され、そして「フリーブロックポインタ」がＮだけ前進される。マージユニットは、割り当てユニットのサイズのＮ個（多重バッファされる場合にはそれ以上）のバッファと、Ｎ個の１６ビットアドレス値、Ａ［０］・・・Ａ［Ｎ−１］とを含む。アドレス値は、「分離可能ユニットヘッド」ないし「分離可能ユニットヘッド＋（Ｎ−１）」の値に各々初期化される。データがそれに対応するストリーム［ｉ］により供給されるときには、マージユニットが各バッファ［ｉ］を並列に充填し始める。バッファ［ｊ］がいっぱいになると、バッファ［ｊ］の「次のポインタ」が「フリーブロックポインタ」の値にセットされ、バッファ［ｊ］がＡ［ｊ］のアドレスに書き込まれ、Ａ［ｊ］が「フリーブロックポインタ」にセットされ、そして「フリーブロックポインタ」が増加される。
【００９０】
デコーダ４において要求されるマッチングデマージユニットは、ブロックを単に読み取り、そしてコンテンツをそれらの各ストリームに転送する。ある事項に対して読み取るべき次のブロックが、現在読み取られたブロックに含まれたポインタにより指示される。
【００９１】
デコーダ４は、本質的にエンコードプロセスの逆であるデコーディングプロセスを遂行する。図８は、図２のエンコーダにより発生されたエンコードされたデータをデコードするのに適したデコーダをブロック図の形態で示す。
【００９２】
図８に示すデコーダは状態マシン８００を備え、これは、Ｎビットカウンタ８０１及び以前の数字記号のレジスタ８０２を含む。状態マシン８００の出力は、経路８０３を経て演算論理ユニット（ＡＬＵ）８６０の入力に接続されると共に、経路８０４を経て他ビット選択ユニット８５１の入力に接続される。入力デマージユニット８０５は、ＦＩＦＯから受け取られたデータを並列ストリームに分割し、その出力は、経路８５９を経て、入力ストリーム０ユニット８５０、入力ストリーム１ユニット８４０、及び入力ストリーム２ユニット８３０へ接続されると共に、経路８１９を経て、入力３ユニット８２１及び入力４ユニット８１１へ接続される。状態マシン８００の更に別の出力は、経路８０６を経て２つのコンテクストベースの適応演算（ＣＡＢＡＣ）デコーダ８１０及び８２０の入力に接続される。この経路は、８１０及び８２０に使用されるコンテクストを選択して、現在ビットをデコードする。入力３ユニット８２１は、その出力が経路８２２を経てＣＡＢＡＣデコーダ８２０の更に別の入力に接続され、一方、入力４ユニット８１１は、その出力が経路８１２を経てＣＡＢＡＣデコーダ８１０の更に別の入力に接続される。
【００９３】
ＣＡＢＡＣデコーダ８１０及び８２０の出力は、経路８２３を経て加算先導１ユニット８３２及び他ビット選択ユニット８３１の入力に接続される。加算先導１ユニット８３２の出力は、経路８３３を経て、更に別の加算先導１ユニット８４２及び更に別の他ビット選択ユニット８４１の入力に接続される。加算先導１ユニット８４２の出力は、経路８４３を経て、最終的な加算先導１ユニット８５２及び最終的な他ビット選択ユニット８５１の入力に接続される。加算先導１ユニット８５２の出力は、経路８５３を経てＡＬＵ８６０の更に別の入力に接続される。
【００９４】
入力ストリーム２ユニット８３０の出力は、経路８３４を経て他ビット選択ユニット８３１の更に別の入力に接続される。同様に、入力ストリーム１ユニット８４０の出力は、経路８４４を経て他ビット選択ユニット８４１の更に別の入力に接続され、一方、入力ストリーム０ユニット８５０の出力は、経路８５４を経て他ビット選択ユニット８５１の更に別の入力に接続される。
【００９５】
他ビット選択ユニット８３１の出力は、経路８３５を経て加算先導１ユニット８３２の更に別の入力に接続される。同様に、他ビット選択ユニット８４１の出力は、経路８４５を経て加算先導１ユニット８４２の更に別の入力に接続され、そして他ビット選択ユニット８５１の出力は、経路８５５を経て加算先導１ユニット８５２の更に別の入力に接続される。デコードされたサインフラグを任意に含む他ビット選択ユニット８５１の更に別の出力は、経路８５６を経て、ＡＬＵ８６０の更に別の入力に接続される。
【００９６】
状態マシン８００の更に別の再スタート出力は、経路８０７を経て、入力ストリーム０ユニット８５０、入力ストリーム１ユニット８４０及び入力ストリーム２ユニット８３０のリセット入力に接続され、一方、状態マシン８００の同じ出力が経路８０８を経て入力３ユニット８２１及び入力４ユニット８１１のリセット入力に供給される。この再スタート出力は、各Separable_Unitの始動時に状態マシン８００によりシグナリングされる。
【００９７】
オペレーション中に、ＦＩＦＯ３からのデータは、入力デマージユニット８０５へ供給され、このユニットが発生する５つのデータストリームは、入力データストリーム０ユニット８５０、入力ストリーム１ユニット８４０、入力ストリーム２ユニット８３０、入力３ユニット８２１及び入力４ユニット８１１へ供給される。入力３ユニット８２１は、データストリームの一部分をＣＡＢＡＣデコーダ８２０へビット０データとして供給し、一方、入力４ユニット８１１は、データストリームの一部分をＣＡＢＡＣデコーダ８１０へ供給する。ＣＡＢＡＣデコーダ８１０及び８２０は、図２のエンコーダ６０及び７０へ最初に供給された信号Ｈを再生する。
【００９８】
この点において、定義されたシンタックスは、演算デコーダのためのコンテクスト選択を、その直前の記号の値から分離するので、ハードウェアデコーダは、デコーディングステージにどこかに挿入されるパイプラインステージを有してもよく、ストールを招くことはないことに注意されたい。このようなパイプラインステージの便利な場所は、Ｈが計算されるポイントである。Ｈの値は、「他ビット選択」ユニット８３１及び加算先導１ユニット８３２へ供給される。入力ストリーム２ユニット８３０は、入力デマージストリームから値Ｇを選択し、そしてそれを「他ビット選択」ユニット８３１へ供給する。他ビット選択ユニット８３１は、Ｈの値に応答してＧの値から値Ｆを発生する。加算先導１ユニット８３２は、値Ｈにより指定された位置に基づく新たな最上位ビットを加算して、３ビット値Ｆを発生する。これは、エンコーダユニット５０ないし５２により実行されるプロセスの逆である。
【００９９】
加算先導１ユニット８３２の出力に発生された３ビット値Ｆは、更に別の加算先導１ユニット８４２の第１入力及び更に別の「他ビット選択」ユニット８４１の第１入力に供給される。入力ストリーム１ユニット８４０は、値Ｅを、「他ビット選択」ユニット８４１の第２入力に供給する。「他ビット選択」ユニット８４１は、その入力に値Ｅ及びＦを取り込み、そして値Ｄを発生する。値Ｄは、加算先導１ユニット８４２の第２入力に供給され、該ユニットは、データＤに対する５ビット値をその出力に発生する。加算先導１ユニット８４２からの出力は、更に別の加算先導１ユニット８５２の第１入力及び更に別の「他ビット選択」ユニット８５１の第１入力に供給される。「他ビット選択」ユニット８５１は、入力ストリーム０ユニット８５０の出力からの信号Ｃをその第２入力に受け取る。これは、エンコーダユニット４０、４１及び４２により遂行されるプロセスの逆である。
【０１００】
又、「他ビット選択」ユニット８５１は、状態マシン８００から経路８０４を経て制御入力も受け取る。又、「他ビット選択」ユニット８５１は、状態マシン８００から経路８０４を経て制御入力も受け取る。「他ビット選択」ユニット８５１は、出力信号Ｂを発生し、これは、加算先導１ユニット８５２の第２入力に供給される。又、「他ビット選択」ユニット８５１は、「サインアウト」出力も発生し、これは、経路８５６を経て演算論理ユニット（ＡＬＵ）８６０の入力へ供給される。加算先導１ユニット８５２は、信号Ｂをその出力に発生しそしてこれをＡＬＵ８６０の更に別の入力に供給する。これは、エンコーダユニット３０、３１及び３２により遂行されるプロセスの逆である。例示の目的で、ユニット８５０、８５１及び８５２のファンクションを擬似コードで以下に示す。
【０１０１】
【０１０２】
状態マシン８００が発生する出力は、デコーダ８２０及び８１０へ供給され、経路８０６を経てコンテクスト制御データが転送される。又、状態マシン８００が発生する制御出力は、経路８０３を経てＡＬＵ８６０の更に別の入力へ供給される。状態マシン８００からの更に別の出力は、入力ストリーム０ユニット８５０、入力ストリーム１ユニット８４０及び入力ストリーム２ユニット８３０の入力に供給される再スタート信号と、入力３ユニット８２１及び入力４ユニット８１１に供給されるフラッシュ信号とを発生する。演算論理ユニット８６０が発生する出力Ａは、出力値コードであって、状態マシン８００にも供給される。デコーダは、図２に示されたエンコーダとは逆のファンクションを有効に遂行し、従って、Ｈ２６４デコーダから図２に示すエンコーダへ供給されるデータを再生する。
【０１０３】
図６に戻り、デコーダＡＬＵ８６０の振舞いを説明する。これは、本質的に、‘Ｂ’値を‘Ａ’値に変換するという点で、エンコーダＡＬＵ２０のオペレーションの逆を遂行する。テーブルのコンテクストを再び参照すれば、所与のコンテクストに対してサブユニット３０２がエンコーダにおいてイネーブルされた場合には、そのコンテクストがデコーダに使用されるときに「加算１」ユニット３１０がデコーダＡＬＵにおいてイネーブルされる。同様に、ユニット３０１がエンコードに対してイネーブルされる場合には、「任意の否定」ユニット３１１がイネーブルされる。最終的に、エンコード手順においてコンテクストに対してユニット３００がイネーブルされると、デコード手順においてそのコンテクストに対して「加算以前のNumSyms」３１２がイネーブルされる。ユニット３１１は、次の擬似コードにより説明される。
【０１０４】
【０１０５】
ユニット３００及び３０２の前記説明を読めば、ユニット３１０及び３１２により遂行されるオペレーションが当業者に明らかであろう。
【０１０６】
図９に振舞いを示すデコーダ状態マシン８００は、図５のエンコーダ状態マシン１０の振舞いに類似している。プロセスがベース／アイドル状態９００でスタートすると仮定すれば、システムは（１６ビット）記号をデコードし（９０１）、これは後続システム５へ出力される。次いで、状態マシン８００は、別の１６ビット値９１０をデコードすることが期待される。９０１でデコードされた値がUNIT_SEPARATORである場合は、デコーダは、経路９１１を経てステージ９２０へ至り、これは、出力を終了し、エンコーダの統計学的情報を再初期化し、そして入力バッファをリセットした後に、状態９００へ戻る。
【０１０７】
そうではなくて、９０１でデコードされた値がData_Block_Headerである場合は、システムは、第１データ記号をデコードし（９４０）、次いで、ステップ９１０でデコードされてカウンタ８０１に記憶されたカウント値を使用して、残りの記号を通して繰り返した後に、最終的に、状態９００に復帰する。
【０１０８】
シンタックスは、直前の記号に基づいて「分岐」判断を行わないので、１つの記号のデコーディングの若干を、次のデコーディングと重畳させ、容易なハードウェアパイプライン構成を許すことに注意されたい。例えば、ステップ９０１及び９０２が完了する前に、デコーディングをスタートすることができる。
【０１０９】
上述したように、所与のシンタックスは、ハードウェアの容易なパイプライン構成を許すが、使用できる唯一のシンタックスがこの特性を有することを意味するのではない。実際に、ここに述べるシンタックスは、全ての用途には適さないことがある。ここに述べるシンタックスでは、「データブロック」でエンコードされるべき記号の数を、データ送信の前に、エンコーダ２へ送信しなければならない。あるアプリケーションでは、この情報が前もって分からないことがあり、従って、バッファすることが不可能であるか又は少なくとも高価なバッファを伴うことになる。この制約をもたない別のシンタックスは、次の通りである。
【０１１０】
【０１１１】
このシンタックスでは、１つの１６ビット値、例えば、ゼロが予約され、そして後続値を「最後」であるとして識別する。次いで、全ての値が調整されて、それらが、予約された値を偶発的に使用しないようにする。例えば、エスケープコードを使用する他の機構が当業者に明らかであろう。ここに示す実施形態は、この又は他の別のシンタックスを使用するように変更することができる。
【０１１２】
本発明は、デコードされた到来するデータを、そのデータの部分に対してコンテクストベースの適応演算エンコーディングを使用する第２の並列エントロピーエンコード化構成へ再エンコーディングし、コンテクストの数を、Ｈ２６４規格に使用されるものから減少し、そしてコンテクストを直前のデコードされた記号とは独立したものにするようにシンタックスを選択して、デコーダが、エンコードされたデータの特定の部分をデコードするのに要する時間にあまり変化がない状態で、エンコードされたデータをデコードできるようにすることにより、最小サイズのＦＩＦＯを使用できるようにすることが明らかであろう。
【０１１３】
図２を参照して述べたものとは別のエンコーダの実施形態では、図１０に示すように、エンコーダ２における２つの単一ビットＣＡＢＡＣエンコーダユニット６０、６１及びそれに関連するストリームデータユニット６１、７１が、単一の‘ＣＡＢＡＣ’エンコーダ６０ａに置き換えられ、これは、一度に２ビットを直接エンコードし、そして単一ストリーム出力ユニット６１ａへ出力する。この単一のＣＡＢＡＣエンコーダ６１ａは、６０又は６１（コスト〜Ｏ(２)）より高価であるが（コストはほぼＯ(４)）、結合したユニットよりは若干安価であり、出力ストリームの１つに対する必要性も排除する。当然、同等の２ビットＣＡＢＡＣデコーダユニットが、図１１に示すように、マッチングデコーダ４に存在することになろう。ここで、入力デマージャー８０５ａがデータを入力３ＦＩＦＯ８２１ａに供給し、これが、次いで、データを２ビットＣＡＢＡＣデコードユニット８２０ａに供給する。これは、値Ｈの量ビットを発生し、それらは、上述したように、「他ビット選択」ユニット８３１及び加算先導１ユニット８３２へ供給される。又、このシステムを使用する実施形態は、Ｈの４つの考えられる各値が、それ自身の正確な確率値を有し、従って、より高い圧縮ファクタを与えるという点で、前記実施形態に勝る効果を有する。（前記実施形態では、Ｈの各値の確率が、Ｈを形成する２つのビットの確率の積から有効に形成され、従って、これらは、最適状態に満たない仕方で相互作用し得る。）
【０１１４】
更に別の実施形態では、図１０の２ビットエンコーダ／デコーダ実施形態が、図３に示す実施形態でなされた変更と組み合わされる（デコーダのためのマッチングユニットと共に）。この実施形態では、出力ストリームの数が丁度２つに減少され、これは、エンコーダユニット３９及び６１ａに対応する。この実施形態は、図７のマージ構造及びユニット８０、８０５を見合わせ、エンコーダユニットとデコーダユニットとの間に２つの独立したＦＩＦＯを維持するだけである。
【０１１５】
上述した実施形態では、エンコードされるべきデータの上位ビットの大半が「直接エンコーディング」機構で取り扱われ、従って、それが存在するときには、ビットごとに５０：５０の確率を仮定する。これらビットの幾つかを演算エンコーディングでエンコードすることにより、より経費のかかる実施であることを犠牲にして、圧縮比のある程度の改善を得ることができる。典型的なビデオデータの分析から、値Ｂの先導意義ビットが除去されたときには、Ｂの、次の最上位５ビット（それらが存在するとき）がゼロである典型的な確率は、次のテーブルにより要約される。
【０１１６】
【０１１７】
明らかなように、これらビットがゼロであるのは、５０：５０確率より高く、従って、ある数の次の最上位ビットを演算エンコーダ／デコーダでエンコードすることにより、高レベルの圧縮を達成することができる。しかしながら、演算エンコーディングの経費が与えられると、より多くの演算エンコード／デコードユニットの追加が、利益を急速に縮小する結果となることに注意するのが重要である。
【０１１８】
例えば、このようなビットが、エンコードされる各記号に実際に存在する確率は、テーブルの第３列に要約されたように、著しく速く低下する。ここに示す実施形態は、最上位ビットの位置を暗示するので、使用しないビットに対する記憶コストは実際上生じない。それ故、このような実施形態では、コスト効率が良いのは、演算エンコーディングを使用して、せいぜい、次の最上位値をエンコードすることだけである。
【０１１９】
図１１に示すように、概念的に簡単であるが、一般的に効率の低い別の実施形態では、値Ｂは、同程度の確率であるサインビットはさておき、単にコンテクストベースの演算エンコーダユニットを使用してエンコードされる。値Ｂは、１６ビットに分割され（１０００）、そして最上位の１５から最下位の０まで番号が付けられた各ビットは、１１１５ないし１１００で各々示されたそれ自身の各ＣＡＢＡＣユニットへ供給される。これらからの出力ストリームは、１２１５ないし１２００であり、そしてサインビット値１２１６は、それが存在するときに、上述したように、ユニット８０を経てマージされる。
【０１２０】
示唆された実施形態（例えば、図２又は図１０）のいずれかへの拡張において、Ｍ個のエンコーダを並列に使用して、エンコーディングレートを高めることができる。１６ビット記号は、ラウンドロビンの順序で、Ｍ個のエンコーダの各々に順次に送信される。同様に、各エンコーダは、順次に結果を発生する。このような構成において、幾つかの簡単化が可能となる。
ａ）増加した並行性で個々のユニットのゆっくりとしたエンコードレートが相殺されるので、個々のエンコーダ／デコーダをゆっくりと動作することができる。
ｂ）デコーダは並列に動作され、直列化ペナルティを招くことなく以前の記号をデコーディングするデコーダの状態を知ることができないので、コンテクストが簡単化される。
【０１２１】
先の実施形態において拡張する別の実施形態では、各エンコーダは、最初に入力値をＶＬＣフォーマット、好ましくは、指数関数的ゴロンへ変換する「直列化ユニット」を含ませることにより、全てのデータに対して演算エンコーディングを使用する。次いで、各エンコーダは、それ自身の演算エンコーダを使用して、一度に１ビットずつ、多数のクロックサイクルにわたり、そのＶＬＣをエンコードする。各ビット位置が、それ自身のコンテクストを有するのが好ましい。数字Ｍは、各記号をエンコードするのに必要なＶＬＣビットの平均数より大きくなるように選択され、従って、平均で、リエンコーダ及びデコーダが、非常に稀な環境はさておき、クロック当たり１記号より高速で動作することを許す。
【０１２２】
しかしながら、本発明のこれら最後の実施形態は、先の実施形態と同じ圧縮性能を達成できない。というのは、エンコーディング／デコーディングユニットが、エンコーディング／デコーディングタスク間に、依存性、ひいては、直列化を導入せずに、統計学的情報を共有できないからである。
【０１２３】
又、本発明は、他のビデオデコーディング規格、例えば、ＶＣ１、又はおそらく、オーディオデコーディング規格にも適用でき、従って、より簡単なフロントエンドのエントロピーデコーディングユニットを使用できるようにする。同様に、均一に配布されず（即ち、圧縮可能であり）そしてＦＩＦＯを経てレートフィルタ（例えば、おそらく、ある送信システムを経てバーストで受信）されねばならないデータを有する他の（非ビデオ）システムも、本発明から利益を得ることができる。
【０１２４】
以上に鑑み、本発明の概念は、次の方法にあることが明らかであろう。
エントロピーデコーディング機構をレート平滑化する方法であって、
ａ）第１のエントロピーエンコードされた表現をデコードされた表現へと変換するステップと、
ｂ）前記デコードされた表現を、データの部分に対してコンテクストベースの適応演算エンコーディングを含む並列エンコーディング機構を使用する第２のエントロピーエンコードされた機構へとエンコードするステップと、
ｃ）前記第２のエンコードされたデータをＦＩＦＯに記憶するステップと、
ｄ）前記ＦＩＦＯから第２のデータを検索するステップと、
ｅ）第２のデータをデコードされたデータへとデコーディングするステップと、
を備えた方法。
【０１２５】
この方法は、更に、ほぼ同程度の確率のデータ又は非常に発生頻度の低いデータに対して安価なエンコーディング技術を使用すると共に、他の部分に対して演算コーディングを使用することを含んでもよい。
【０１２６】
この方法は、更に、少なくとも１つの記号によりデコードコンテクストをデカップルする制御シンタックスの適用を含んでもよい。
【特許請求の範囲】
【請求項１】
コンテクストベースの適応演算エントロピーコード化データをデコーディングする方法において、
ａ）エンコードされたデータをデコーディングして第１のデコードされたデータを発生するステップと、
ｂ）記号の少なくとも一部分に対してコンテクストベースの適応演算エンコーディングを含む並列エンコーディング機構を使用して前記デコードされたデータをエントロピーエンコーディングして、第２のエンコードされたデータを発生するステップと、
ｃ）前記第２のエンコードされたデータを先入れ先出し（ＦＩＦＯ）メモリに記憶するステップと、
ｄ）前記第２のエンコードされたデータをＦＩＦＯメモリから読み取るステップと、
ｅ）ＦＩＦＯメモリから読み取ったデータをデコーディングして、デコードされたエントロピーコード化データである第２のデコードされたデータを発生するステップと、
を備えた方法。
【請求項２】
前記ステップｂ）において、エンコーダは、Ｎビット記号をエンコードし、この記号は、複数のストリームに分割され、そしてそれらストリームの少なくとも２つは、対応する数の演算エンコーディングユニットを使用して並列にエンコードされる、請求項１に記載の方法。
【請求項３】
前記ステップｂ）において、コンテクストの数は、データを最初にエンコーディングするのに使用されるものより小さい、請求項１又は２に記載の方法。
【請求項４】
前記ステップｂ）において、特定のシンタックスが解釈され、そして演算エンコーディングのためのコンテクストは、エンコードされるシンタックスエレメントに基づいて選択され、前記シンタックスは、コンテクストがその直前にエンコードされた記号に依存しないよう確保するように構成される、請求項１から３のいずれかに記載の方法。
【請求項５】
前記ステップｂ）において、ほぼ同程度の確率であるデータをエンコードするのに演算コーディングが使用されない、請求項１から４のいずれかに記載の方法。
【請求項６】
ほぼ同程度の確率であるデータは、可変長さコーディング機構を使用してエンコードされる、請求項５に記載の方法。
【請求項７】
前記ステップｂ）において、発生確率の低いデータをエンコードするのに演算コーディングが使用されない、請求項１から６のいずれかに記載の方法。
【請求項８】
発生確率の低いデータは、可変長さコーディング機構を使用してエンコードされる、請求項７に記載の方法。
【請求項９】
コンテクストベースの適応演算エントロピーエンコードデータをデコーディングする装置において、エンコードされたデータをデコーディングして、第１のデコードされたデータを形成する第１デコーダと、その第１のデコードされたデータをエンコードするためのエンコーダであって、デコードされたデータの少なくとも一部分に対してコンテクストベースの適応演算エンコーディングを含む並列エンコーディング機構を使用して、第２のエンコードされたデータを発生するエンコーダと、その第２のエンコードされたデータを記憶するための先入れ先出し（ＦＩＦＯ）メモリと、前記第２のエンコードされたデータをＦＩＦＯの出力から読み取り、そしてその第２のエンコードされたデータをデコーディングして、デコードされたコンテクストベースの適応演算エントロピーエンコードデータを発生するためのデコーダと、を備えた装置。
【請求項１０】
前記エンコーダは、Ｎビット記号をエンコードするように構成され、この記号は、複数のストリームに分割され、そしてそれらストリームの少なくとも２つは、それに対応する数の演算エンコーディングユニットを使用して並列にエンコードされる、請求項９に記載の装置。
【請求項１１】
前記エンコーダは、特定のシンタックスを解釈して、処理されるシンタックスエレメントに基づき演算エンコーダのコンテクストを選択するように構成された状態マシンを含み、前記シンタックスは、コンテクストが直前の記号に依存しないよう確保するために選択される、請求項９又は１０に記載の装置。
【請求項１２】
前記デコーダは、特定のシンタックスを解釈して、処理されるシンタックスエレメントに基づき演算デコーダのコンテクストを選択するように構成された状態マシンを含み、前記シンタックスは、コンテクストが直前にデコードされた記号に依存しないよう確保するために選択される、請求項１１に記載の装置。
【請求項１３】
コンテクストの数は、最初にエンコードされたデータをエンコードするのに使用されるコンテクストの数より小さい、請求項９から１２のいずれかに記載の装置。
【請求項１４】
単一のＦＩＦＯを備え、前記エンコーダは、エンコードされたデータストリームを、ＦＩＦＯへ書き込む前に、インターリーブするための手段を備え、そして前記デコーダは、ＦＩＦＯから読み取ったデータストリームをデインターリーブするための手段を備えた、請求項９ないし１３のいずれかに記載の装置。
【請求項１５】
前記エンコーダは、可変長さコード化機構を使用して、同程度の確率の見込みがあるか又は存在する見込みが少ない各記号を表わすデータビットの部分をエンコードするための手段を備えた、請求項９ないし１４のいずれかに記載の装置。
【請求項１６】
第１のデコードされたデータをエンコーディングするための複数のエンコーダと、ラウンドロビン形態でエンコーダに記号を付与するための手段と、エンコードされたデータをデコーディングするための対応する複数のデコーダとを備え、各デコーダは、デコードされた記号を順次発生するように構成される、請求項９から１５のいずれかに記載の装置。
【請求項１】
コンテクストベースの適応演算エントロピーコード化データをデコーディングする方法において、
ａ）エンコードされたデータをデコーディングして第１のデコードされたデータを発生するステップと、
ｂ）記号の少なくとも一部分に対してコンテクストベースの適応演算エンコーディングを含む並列エンコーディング機構を使用して前記デコードされたデータをエントロピーエンコーディングして、第２のエンコードされたデータを発生するステップと、
ｃ）前記第２のエンコードされたデータを先入れ先出し（ＦＩＦＯ）メモリに記憶するステップと、
ｄ）前記第２のエンコードされたデータをＦＩＦＯメモリから読み取るステップと、
ｅ）ＦＩＦＯメモリから読み取ったデータをデコーディングして、デコードされたエントロピーコード化データである第２のデコードされたデータを発生するステップと、
を備えた方法。
【請求項２】
前記ステップｂ）において、エンコーダは、Ｎビット記号をエンコードし、この記号は、複数のストリームに分割され、そしてそれらストリームの少なくとも２つは、対応する数の演算エンコーディングユニットを使用して並列にエンコードされる、請求項１に記載の方法。
【請求項３】
前記ステップｂ）において、コンテクストの数は、データを最初にエンコーディングするのに使用されるものより小さい、請求項１又は２に記載の方法。
【請求項４】
前記ステップｂ）において、特定のシンタックスが解釈され、そして演算エンコーディングのためのコンテクストは、エンコードされるシンタックスエレメントに基づいて選択され、前記シンタックスは、コンテクストがその直前にエンコードされた記号に依存しないよう確保するように構成される、請求項１から３のいずれかに記載の方法。
【請求項５】
前記ステップｂ）において、ほぼ同程度の確率であるデータをエンコードするのに演算コーディングが使用されない、請求項１から４のいずれかに記載の方法。
【請求項６】
ほぼ同程度の確率であるデータは、可変長さコーディング機構を使用してエンコードされる、請求項５に記載の方法。
【請求項７】
前記ステップｂ）において、発生確率の低いデータをエンコードするのに演算コーディングが使用されない、請求項１から６のいずれかに記載の方法。
【請求項８】
発生確率の低いデータは、可変長さコーディング機構を使用してエンコードされる、請求項７に記載の方法。
【請求項９】
コンテクストベースの適応演算エントロピーエンコードデータをデコーディングする装置において、エンコードされたデータをデコーディングして、第１のデコードされたデータを形成する第１デコーダと、その第１のデコードされたデータをエンコードするためのエンコーダであって、デコードされたデータの少なくとも一部分に対してコンテクストベースの適応演算エンコーディングを含む並列エンコーディング機構を使用して、第２のエンコードされたデータを発生するエンコーダと、その第２のエンコードされたデータを記憶するための先入れ先出し（ＦＩＦＯ）メモリと、前記第２のエンコードされたデータをＦＩＦＯの出力から読み取り、そしてその第２のエンコードされたデータをデコーディングして、デコードされたコンテクストベースの適応演算エントロピーエンコードデータを発生するためのデコーダと、を備えた装置。
【請求項１０】
前記エンコーダは、Ｎビット記号をエンコードするように構成され、この記号は、複数のストリームに分割され、そしてそれらストリームの少なくとも２つは、それに対応する数の演算エンコーディングユニットを使用して並列にエンコードされる、請求項９に記載の装置。
【請求項１１】
前記エンコーダは、特定のシンタックスを解釈して、処理されるシンタックスエレメントに基づき演算エンコーダのコンテクストを選択するように構成された状態マシンを含み、前記シンタックスは、コンテクストが直前の記号に依存しないよう確保するために選択される、請求項９又は１０に記載の装置。
【請求項１２】
前記デコーダは、特定のシンタックスを解釈して、処理されるシンタックスエレメントに基づき演算デコーダのコンテクストを選択するように構成された状態マシンを含み、前記シンタックスは、コンテクストが直前にデコードされた記号に依存しないよう確保するために選択される、請求項１１に記載の装置。
【請求項１３】
コンテクストの数は、最初にエンコードされたデータをエンコードするのに使用されるコンテクストの数より小さい、請求項９から１２のいずれかに記載の装置。
【請求項１４】
単一のＦＩＦＯを備え、前記エンコーダは、エンコードされたデータストリームを、ＦＩＦＯへ書き込む前に、インターリーブするための手段を備え、そして前記デコーダは、ＦＩＦＯから読み取ったデータストリームをデインターリーブするための手段を備えた、請求項９ないし１３のいずれかに記載の装置。
【請求項１５】
前記エンコーダは、可変長さコード化機構を使用して、同程度の確率の見込みがあるか又は存在する見込みが少ない各記号を表わすデータビットの部分をエンコードするための手段を備えた、請求項９ないし１４のいずれかに記載の装置。
【請求項１６】
第１のデコードされたデータをエンコーディングするための複数のエンコーダと、ラウンドロビン形態でエンコーダに記号を付与するための手段と、エンコードされたデータをデコーディングするための対応する複数のデコーダとを備え、各デコーダは、デコードされた記号を順次発生するように構成される、請求項９から１５のいずれかに記載の装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２０１２−８０５６５（Ｐ２０１２−８０５６５Ａ）
【公開日】平成２４年４月１９日（２０１２．４．１９）
【国際特許分類】
【出願番号】特願２０１１−２５７２７２（Ｐ２０１１−２５７２７２）
【出願日】平成２３年１１月２５日（２０１１．１１．２５）
【分割の表示】特願２００８−５４３９０１（Ｐ２００８−５４３９０１）の分割
【原出願日】平成１８年１２月７日（２００６．１２．７）
【出願人】（５０１１７６０３７）イマジネイション テクノロジーズ リミテッド (59)
【Ｆターム（参考）】
【公開日】平成２４年４月１９日（２０１２．４．１９）
【国際特許分類】
【出願日】平成２３年１１月２５日（２０１１．１１．２５）
【分割の表示】特願２００８−５４３９０１（Ｐ２００８−５４３９０１）の分割
【原出願日】平成１８年１２月７日（２００６．１２．７）
【出願人】（５０１１７６０３７）イマジネイション テクノロジーズ リミテッド (59)
【Ｆターム（参考）】
[ Back to top ]