"イベントシーケンスの各イベントが個別の値を有する確率推定値を生成するための確率推定器であって、前記各イベントに対応するコンテクスト情報に応じて前記確率推定値を生成する確率推定器と、前記確率推定器に接続され、各イベント及び対応の確率推定値に応じてゼロ以上のビットの情報シーケンスを生成する符号化エンジンであって、スライス終了信号を符号化する前に、レンジレジスタの値とは独立したサブレンジインターバル用の定数を用いて、前記情報シーケンスにおける算術符号化データの終了を知らせるためのイベントを符号化する符号化エンジンと、を備える算術エンコーダ。前記イベントシーケンスにおけるイベントの終了を知らせるためのイベントを符号化するために定数を使用する前記符号化エンジンは、ローレジスタに残っているコンテンツを前記情報シーケンスに含ませることが可能である、請求項1に記載のエンコーダ。前記符号化エンジンは、前記ローレジスタに残っているコンテンツをフラッシュし、当該フラッシュ中に書き込まれる最後のビットを1に等しくセットする、請求項2に記載のエンコーダ。データを符号化する方法であって、イベントシーケンスのイベントを符号化して、符号化データを生成するステップと、前記符号化データを用いて、ビットストリームを生成するステップであって、前記ビットストリームにおける算術符号化データの終了を指示するために復号時に使用するインジケータを符号化することを含むステップと、を備える方法。非算術符号化データが、前記ビットストリームにおいて算術符号化データに続く、請求項4に記載の方法。前記インジケータを符号化するステップは、スライスの終了を知らせるためのイベントを符号化するステップを含む、請求項4に記載の方法。スライスの終りを知らせるためのイベントを符号化する前記ステップは、スライス終了信号を符号化する前に、レンジレジスタの値とは独立したサブレンジインターバルの定数を使用することを含む、請求項6に記載の方法。定数を使用してスライスの終りを知らせるためのイベントを符号化する前記ステップは、ローレジスタに残っているコンテンツを前記情報シーケンスへフラッシュすることができる、請求項7に記載の方法。前記ローレジスタに残っているコンテンツをフラッシュする処理は、フラッシュ中に書き込まれる最後のビットを1に等しくセットすることを含む、請求項8に記載の方法。命令を記憶する一つ以上の記録可能な媒体を有し、システムによって実行されたときに、イベントシーケンスのイベントを符号化して、符号化データを生成するステップと、前記符号化データを使用して、ビットストリームを生成するステップであって、スライス終了信号を符号化する前にレンジレジスタの値とは独立したサブレンジインターバルの定数を使用して、前記ビットストリームにおける符号化データの終了を知らせるためのイベントを符号化することを含んでいるステップと、によって前記命令が前記システムにデータを符号化させる、製造品。前記システムによって実行されたときに、前記システムにローレジスタのコンテンツをフラッシュさせる命令であって、フラッシュ中に書き込まれる最後のビットを1に等しくセットすることを含む命令を更に備える、請求項10に記載の製造品。データを符号化する装置であって、データのブロックを符号化して、符号化データを生成する手段と、前記符号化データを使用して、ビットストリームを生成する手段であって、符号化エンジンが、スライス終了信号を符号化する前にレンジレジスタの値とは独立したサブレンジインターバルの定数を使用して、前記ビットストリームにおける算術符号化データの終了を知らせるためのイベントを符号化することを含んでいる手段と、を備える装置。確率推定のための状態マシンを生成する方法であって、ルックアップテーブルLUTの状態に確率を割り当てるステップであって、所与の状態の番号をiとし、かつ、適応レートが1より小さいとする場合に、前記状態の各状態iに対する確率を、LPSの最大確率に適応レートのi乗を乗算した値に等しくセットする処理を含むステップと、MPS及びLPSを観察し、遷移れるべきLUTの状態に対して状態遷移を発生するステップであって、MPSが観察されたときに現在の状態から状態マシンが遷移する次の状態が、当該現在の状態が最も高い状態でない場合には、当該現在の状態より高い次の状態であり、当該現在の状態が最も高い状態である場合には当該現在の状態であり、更に、複数の状態に対しLPSが観察されたときに当該現在の状態から状態マシンが遷移する次の状態が、現在の状態の番号log現在の状態の確率適応レート1-適応レート/現在の状態の確率/log適応レートの計算結果が丸められた値である、ステップと、を含む方法。前記結果の丸められた値は、LPSが観察されて次の状態を発生するときに導入される丸めが平均で実質的にゼロとなるようになっている、請求項13に記載の方法。前記LUTは、各状態に関連付けられた複数の値を有し、該複数の値の各々は、予想されるインターバルレンジに前記状態に関連した確率を乗算した積に近似する、請求項13に記載の方法。状態に関連付けられた値は、配列における列のインデックスをjとし、当該配列における列の数をMとし、定数をNとする場合に、N/2MlogjM1/jMと状態に関連付けられた確率との積を整数に丸めることによって得られる、請求項15に記載の方法。前記複数の状態の少なくとも一つに対する前記複数の値の少なくとも一つは、所定値に切り取られる、請求項15に記載の方法。前記所定値は、MPSの符号化中に再正規化を多くて1回繰り返せるようにする、請求項17に記載の方法。前記LUTにおける状態の数は、63であり、前記適応レートは、0.5/0.01875の1.0/63乗であり、LPSの最高確率は、0.5であり、前記配列における列の数は、4であり、前記配列の第1列における値は、N/4に切り取られる、請求項16に記載の方法。前記定数Nは、512である、請求項19に記載の方法。イベントシーケンスの各イベントが個別の値を有する確率推定値を発生するための確率推定器と、前記確率推定器に接続され、各イベント及び対応の確率推定値に応じて情報シーケンスのゼロ以上のビットを生成する符号化エンジンと、を備え、前記確率推定器は、前記各イベントに対応するコンテクスト情報に応じて、確率推定状態マシンを使用して前記確率推定値を発生し、前記確率推定状態マシンは、所与の状態の番号をiとし、適応レートが1より小さい場合に、各状態iに対する確率を、LPSの最大確率に適応レートのi乗を乗算した値に等しくセットして、ルックアップテーブルLUTの状態に確率を割り当て、MPSが観察されたときに現在の状態から状態マシンが遷移する次の状態が、当該現在の状態が最も高い状態でない場合には当該現在の状態より高い次の状態となり、当該現在の状態が最も高い状態である場合には当該現在の状態となり、更に、複数の状態に対しLPSが観察されたときに現在の状態から状態マシンが遷移する次の状態が、現在の状態の番号log現在の状態の確率適応レート1-適応レート/現在の状態の確率/log適応レートの計算結果が丸められた値となるように、MPS及びLPSを観察して、遷移されるべきLUTの状態に対して状態遷移を発生することによって生成される、算術エンコーダ。前記結果の丸められた値は、LPSが観察されて次の状態を発生するときに導入される丸めが平均で実質的にゼロとなるようになっている、請求項21に記載の算術エンコーダ。前記LUTは、各算術エンコーダに関連付けられた複数の値を有し、該複数の値の各々は、予想されるインターバルレンジに、前記状態に関連した確率を乗算した積に近似する、請求項21に記載の算術エンコーダ。状態に関連した値は、配列における列インデックスをjとし、当該配列における列の数をMとし、定数をNとした場合、N/2MlogjM1/jMと状態に関連付けられた確率との積を整数へと丸めることによって得られる、請求項23に記載の算術エンコーダ。前記複数の状態の少なくとも一つに対する前記複数の値の少なくとも一つは、ある数に切り取られる、請求項23に記載の前記エンコーダ。前記数は、MPSの符号化中に再正規化を多くて1回繰り返せるようにする、請求項25に記載の算術エンコーダ。前記LUTにおける状態の数は、63であり、前記適応レートは、0.5/0.01875の1.0/63乗であり、LPSの最高確率は、0.5であり、前記配列における列の数は、4であり、前記配列の第1列における値は、N/4に切り取られる、請求項21に記載の算術エンコーダ。前記定数Nは、512である、請求項27に記載の算術エンコーダ。イベントシーケンスのイベントが個別の値を有する確率推定値を生成する確率推定器と、前記確率推定器に接続され、対応する確率推定値及び情報シーケンスに応じてイベントシーケンスのイベントを生成するための復号エンジンと、を備え、前記確率推定器は、前記イベントシーケンスの前記イベントに対応するコンテクスト情報に応じて、確率推定状態マシンを使用して前記確率推定値を生成し、前記確率推定状態マシンは、所与の状態の番号をiとし、適応レートが1より小さいとする場合に、各状態iに対する確率を、LPSの最大確率に適応レートのi乗を乗算した値に等しくセットして、ルックアップテーブルLUTの状態に確率を割り当て、MPSが観察されたときに現在の状態から状態マシンが遷移する次の状態が、当該現在の状態が最も高い状態でない場合には当該現在の状態より高い次の状態となり、当該現在の状態が最も高い状態である場合には当該現在の状態となり、更に、複数の状態に対しLPSが観察されたときに現在の状態から状態マシンが遷移する次の状態が、現在の状態の番号log現在の状態の確率適応レート1-適応レート/現在の状態の確率/log適応レートの計算結果が丸められた値となるように、MPS及びLPSを観察して、遷移されるべきLUTの状態に対する状態遷移を発生することによって生成される、算術デコーダ。前記結果の丸められた値は、LPSが観察されて次の状態を発生するときに導入される丸めが平均で実質的にゼロとなるようになっている、請求項29に記載の算術デコーダ。前記LUTは、各算術エンコーダに関連付けられた複数の値を有し、該複数の値の各々は、予想されるインターバルレンジに、前記状態に関連付けられた確率を乗算した積に近似する、請求項29に記載の算術デコーダ。状態に関連した値は、配列における列インデックスをjとし、配列における列の数をMとし、定数をNとすれば、N/2MlogjM1/jMと状態に関連した確率との積を整数へと丸めることによって得られる、請求項31に記載の算術デコーダ。前記複数の状態の少なくとも一つに対する前記複数の値の少なくとも一つは、ある数に切り取られる、請求項31に記載の算術デコーダ。前記数は、MPSの符号化中に再正規化を多くて1回繰り返せるようにする、請求項33に記載の算術デコーダ。前記LUTにおける状態の数は、63であり、前記適応レートは、0.5/0.01875の1.0/63乗であり、LPSの最高確率は、0.5であり、前記配列における列の数は、4であり、前記配列の第1列における値は、N/4に切り取られる、請求項29に記載の算術デコーダ。前記定数Nは、512である、請求項35に記載の算術デコーダ。イベントシーケンスのイベントが個別の値を有する確率推定値を生成するステップであって、前記確率推定値は、前記イベントシーケンスの前記各イベントに対応するコンテクスト情報に応じて、確率推定状態マシンを使用して生成される、ステップと、対応する確率推定値及び情報シーケンスに応答してイベントシーケンスのイベントを生成するステップと、を含み、前記確率推定状態マシンは、所与の状態の番号をiとし、適応レートが1より小さいとする場合に、各状態iに対する確率を、LPSの最大確率に適応レートのi乗を乗算した値に等しくセットして、ルックアップテーブルLUTの状態に確率を割り当て、MPSが観察されたときに現在の状態から状態マシンが遷移する次の状態が、当該現在の状態が最も高い状態でない場合には当該現在の状態より高い次の状態となり、当該現在状態が最も高い状態である場合には当該現在の状態となり、更に、複数の状態に対しLPSが観察されたときに現在の状態から状態マシンが遷移する次の状態が、現在の状態の番号log現在の状態の確率適応レート1-適応レート/現在の状態の確率/log適応レートの計算の結果が丸められた値になるように、MPS及びLPSを観察して遷移されるべきLUTの状態に対する状態遷移を発生することによって、生成される、復号方法。0010これら従来の解決策は、両者ともに、効率が悪い。符号化アルゴリズム及び復号アルゴリズムの複雑さを低減し、符号化、送信、及び復号を行うデータを減らし、更に、記憶の必要性を緩和するために、より効率の良い解決策が要望されている。算術符号化及び/又は算術復号を実行する方法及び装置を開示する。一実施形態において、データ符号化方法は、イベントシーケンスにおける複数のイベントを符号化して、符号化データを生成するステップと、当該符号化データを用いてビットストリームを生成するとともに、当該符号化データの後のビットストリームにゼロ以上のスタフィングビットを追加することを含むステップとを備える。当該ゼロ以上のスタフィングビットは、符号化されたイベントの量と、符号化されているブロックの数と、ビットストリームにおけるビットの数との間の関係を実質的に維持するように機能する。別の実施形態において、算術デコーダは、イベントシーケンスのイベントに対してコンテクスト識別子を生成するシーケンサと、LPSの値及びLPSの確率推定値を決定する確率推定器と、LPSのレンジに値を割り当てるレンジレジスタを含む復号エンジンとを備えている。コンテクスト識別子がインデックスに等しくない場合に、当該値は、LPSの確率推定値と、レンジレジスタに記憶された値と、LPSのレンジへのコンテクスト識別子とに基づき、また、コンテクスト識別子がインデックスに等しい場合に、当該値は、レンジレジスタに記憶された値に基づかない。復号エンジンは、更に、LPSのレンジの値及び情報シーケンスからのビットに基づいて2進イベントの値を決定する。他の実施形態において、確率推定のための状態マシンを生成する方法は、ルックアップテーブルLUTの状態に確率を割り当てるステップを含み、このステップは、所与の状態の番号をiとし、かつ、適応レートが1より小さいとする場合に、各状態iに対する確率を、適応レートのi乗が乗算されたLPSの最大確率に等しくセットする処理を含む。この方法は、また、MPS及びLPSを観察して、遷移されるべきLUTの状態に対する状態遷移を発生させるステップを備え、MPSが観察されたときに現在の状態から状態マシンが遷移する次の状態を、当該現在の状態が最も高い状態でない場合に現在の状態より高い次の状態とし、当該現在の状態が最も高い状態である場合に当該現在の状態とする。更に、複数の状態に対しLPSが観察されたときに現在の状態から状態マシンが遷移する次の状態は、現在の状態の番号log現在状の態の確率適応レート1-適応レート/現在の状態の確率/log適応レートの計算結果が丸められた値となる。0011本発明は、本発明の種々の実施形態を示す添付図面及び以下の詳細な説明から完全に理解されるであろうが、これは、本発明を特定の実施形態に限定するものではなく、本発明を例示し理解するためのものに過ぎない。0029以下、情報、特にビデオデータを符号化及び復号する方法及び装置について説明する。符号化及び復号中に、算術符号化されているイベントの終了を知らせるために、インジケータ例えば、スライスの終了が使用される。一実施形態では、情報の符号化中に、エンコーダによって生成される符号化データのビットストリームに、数ビット又は数バイトのスタフィング情報が追加される。これら追加のビットを符号化データのビットストリームの中間にスタフィングするのではなく、スタフィングバイト又はビットを、符号化データの最後に追加する。このようなスタフィングを使用することによって、符号化されているイベントの数と、ビデオデータのブロック例えばマクロブロックの数と、生成されている情報シーケンスのサイズとの間の関係を維持することができる。0030以下、本発明をより完全に説明するために多数の細部について述べる。しかしながら、当業者であれば、これら特定の細部がなくとも本発明を実施できることが明らかであろう。他の例では、本発明を不明瞭にしないために、周知の構造及び装置を、詳述する代わりに、ブロック図形態で示す。0031以下の詳細な説明では、コンピュータメモリ内のデータビットに対する操作のアルゴリズム及び記号表示の形で記載している部分がある。これらのアルゴリズム記述及び表示は、データ処理分野の当業者によって、当該当業者の仕事の実体をその分野の他の当事者に最も効果的に伝達するために使用される手段である。アルゴリズムとは、ここにおいても、且つ一般においても、所望の結果を導く自己一貫性のあるステップのシーケンスであると考えられる。ステップとは、物理的な量の物理的な操作を要求するものである。必ずしもそうでないが、通常、これらの量は、記憶、転送、合成、比較、及びその他操作を行うことができる電気的又は磁気的信号の形態をとる。主として一般に使用される理由は、これらの信号を、ビット、値、エレメント、シンボル、キャラクタ、用語、番号等として参照することが時に便利であるとわかっているからである。0032しかしながら、これら及び同様の全ての用語は、適切な物理量に関連付けられており、これらの量に適用される単なる便利な表示に過ぎないことに留意されたい。以下の説明から明らかなように、特に指示のない限り、説明全体にわたり、処理又は計算又は算出又は決定或いは表示等の用語を用いた説明は、コンピュータシステムのレジスタ及びメモリ内の物理電子量として表わされたデータを、コンピュータシステムのメモリ又はレジスタ或いは他の情報記憶、送信又は表示装置内の物理的量として同様に表わされた他のデータへと操作及び変換するコンピュータシステム、又は同様の電子計算装置のアクション及びプロセスを指すことは理解されよう。0033また、本発明は、本明細書に記載されたオペレーションを実行する装置に関する。この装置は、要求された目的のために特別に構成されてもよく、又はコンピュータ内に記憶されたコンピュータプログラムによって選択的に起動され又は再構成される汎用コンピュータを備えてもよい。このようなコンピュータプログラムは、コンピュータ読み取り可能な記憶媒体、例えば、フロッピーディスク、光学的ディスク、CD-ROM、磁気-光学ディスクを含む任意の形式のディスク、リードオンリメモリROM、ランダムアクセスメモリRAM、EPROM、EEPROM、磁気又は光学カード、或いは電子的命令の記憶に適した任意の形式の媒体に記憶され得るが、これらに限定されない。これらは各々、コンピュータのシステムバスに接続される。0034本明細書に記載したアルゴリズム及び表示は、特定のコンピュータ又は他の装置に固有に関連するものではない。本明細書の教示に基づくプログラムと共に種々の汎用システムを使用することができ、また、要求の方法のステップを実行するための更に特殊な装置を構成することも便利であることは理解されよう。種々のこれらシステムに必要とされる構造は、以下の説明から明らかとなろう。更に、本発明を、特定のプログラミング言語を参照して説明していない。本明細書に記載された本発明の教示を実施するために、種々のプログラミング言語を使用できることは明らかであろう。0035マシン読み取り可能な媒体は、マシン例えばコンピュータで読み取りできる形態で情報を記憶又は転送するためのメカニズムを含む。例えば、マシン読み取り可能な媒体は、リードオンリメモリROM、ランダムアクセスメモリRAM、磁気ディスク記憶媒体、光学記憶媒体、フラッシュメモリデバイス、電気的、光学的、音響的又は他の形態の伝播信号例えば、搬送波、赤外線信号、デジタル信号等、等々を含む。<符号化及び復号システムの概要>0036図1は、符号化及び復号システム100の実施形態のブロック図である。図1に示すように、システム100は、チャンネル120を介して通信するエンコーダ102及びデコーダ104を備えている。これに代えて、システム100は、エンコーダ102又はデコーダ104だけを備えてもよい。0037チャンネル120は、有線チャンネル、無線チャンネル又はそれらの組合せを含む相応のデータ通信チャンネルとすることができる。チャンネル120には、適当なデータ通信及び変調機構が使用される。システム100の一例は、画像のシーケンスを含むビデオデータを符号化し、圧縮し、復号するためのシステムである。一実施形態では、各ピクチャーは、一つ以上のスライスに分割される。0038エンコーダ102は、入力データ例えばビデオ情報といった入力情報を受信する入力106を有する。一実施形態では、エンコーダ102は、算術符号化を使用してデータを符号化する。したがって、エンコーダ102は、データ記憶部、操作レジスタ、及び算術符号化エンジンを備えている。一実施形態では、エンコーダ102は、レンジレジスタ、即ちRレジスタと、ローレジスタ、即ちLレジスタとを含む。更に、一実施形態では、エンコーダ102は、確率推定状態マシンを含む。エンコーダ102によって実行される符号化アルゴリズムは、当該技術において周知のコンテクスト適応二値算術符号化であり、本明細書ではCABACと称している。また、本明細書に記載された技術及び構成を、他の符号化及び復号のアルゴリズム並びに手順に拡張することもできる。エンコーダ102は、符号化データをチャンネル120へ供給する出力108を有する。0039一実施形態において、エンコーダ102は、算術符号化データの終了を指示する符号化イベント例えば、決定を含む符号化データのビットストリームを生成する。一実施形態において、算術符号化データの終了を示すイベントは、スライス終了フラグを含む。また、ビットストリームは、より詳細には以下に述べるスタフィングバイト又はビットを含んでもよい。0040デコーダ104は、チャンネル120から符号化データを受信する入力110と、復号データを供給する出力112とを有する。一実施形態において、符号化データを復号するためのデコーダ104のオペレーションは、エンコーダ102の符号化のオペレーションと概ね対称である。尚、システム100は、2つ以上のエンコーダ及び/又は2つ以上のデコーダを備えてもよい。0041エンコーダ102及びデコーダ104は、ビデオデータ、例えば、ビデオプロセッサ例えばビデオコーデックによって生成されたビデオデータの処理に使用される。一実施形態では、ビデオ画像は、記録され、当該記録された画像の16×16、8×8又は4×4のサンプルを表すデータのサンプルブロックに分割される。これらブロックは、次いで、ビデオプロセッサによって例えば、離散コサイン変換を使用して変換、量子化されて、サンプルブロックを表す整数値が得られる。これら整数値は、ビデオプロセッサによってイベント例えば2進イベントのシーケンスに変換され、エンコーダへ送られて、符号化される。或いは又、ビデオプロセッサは、個々のサンプルを直接操作してもよく、この操作は、サンプルを変換及び量子化し、サンプルに対する個別の量子化整数値をイベントシーケンスに変換する処理を含むものであってもよい。0042図2は、ビットストリームを生成するための符号化プロセスのフロー図である。このプロセスは、処理ロジックによって実行される。当該処理ロジックは、ハードウェア例えば、回路、専用ロジック等、ソフトウェア例えば、汎用コンピュータシステム又は専用マシンで実行されるソフトウェア或いはその両方の組合せによって構成され得る。0043図2に示すように、この処理ロジックは、イベントシーケンス内のイベントを符号化して、符号化データを生成する処理ブロック201。イベントは、2進決定とすることができる。また、イベントは、同じスライスからのものであってもよい。一実施形態では、イベントの一つは、算術符号化の終了例えば、スライスの終了を指示する。次いで、処理ロジックは、全てのイベントに対する符号化データと、それに続くスタフィングバイト又はビットとをもつビットストリームを生成する処理ロジック202。このスタフィングバイト又はビットは、ビットストリームにおいて、算術符号化の終了を指示する符号化インジケータの後に入れられる。0044図3は、符号化データを、図1のシステムのようなシステムにおいて送信することのできる例示のデータフォーマット300を示す。フォーマット300は、ヘッダ302と、算術符号304と、一つ以上のストップビット306と、0,1又はそれより多くの整列ビット308と、0,1又はそれより多くのスタフィングバイト310とを含む。別の実施形態では、0,1又はそれ以上のスタフィングビットをバイトに代えて使用することができる。0045上述したように、図1のシステム及び図3のデータフォーマットを使用して、ピクチャーのシーケンスに関連するデータを含むビデオ情報の符号化及び送信を行うことができる。一実施形態では、ピクチャーが一つ以上のスライスに分割される。ここで、1スライスは、16×16ピクセルのアレーのマクロブロックを一つ以上含む。各スライスは、ピクチャー内の他のスライスと独立して符号化される。ピクチャーデータは、図3に示すフォーマットで符号化される。0046一実施形態では、ヘッダ302は、バイト境界で始まり、固定長符号又は可変長符号のいずれかを用いて符号化例えば、ハフマン符号化されたデータを含む。ヘッダ302は、スライスヘッダとすることができる。スライスヘッダの場合に、ヘッダ302の前に、スタートコードSCと、その次に続くスライスデータの形式を識別するインジケータとを設けることができる。0047算術符号304は、エンコーダ102図1のようなエンコーダの算術符号化エンジンによって生成されたビットのシーケンスである。一実施形態では、ビットのシーケンスがバイト境界でスタートする。一つ以上のストップビット303が、算術符号304に続く。別の実施形態では、ストップビット303が算術符号304に含まれてもよい。幾つかの0から7の後続の整列ビット308がストップビット306に続き、一実施形態では、スタフィングバイト310のバイト整列を保証する。データに追加されるスタフィングバイト310の数は、符号化されているイベントの数と、ビデオデータのブロック例えばマクロブロックの数と、生成された情報シーケンスのサイズとの間の関係を維持することに要するバイト数に基づいて、0バイト、1バイト又は2バイト以上にすることができる。<コードストリームの終了>0048一実施形態では、エンコーダは、算術符号化データの終了をデコーダに指示するイベント例えば決定を符号化する。算術符号化データの終了は、スライスの終了に達したときに指示されてもよい。また、算術符号化データの終了は、ビットストリームにおける算術符号化データがストップし、その後に非算術符号化データが続くときにも発生させてもよい。0049図3に戻り、一実施形態では、スライス内の各マクロブロックに対して、算術符号204は、典型的には、以下のデータ、即ちマクロブロックモード、任意に動きベクトル及び変換係数、並びにend_of_slice_flagを含む。このend_of_slice_flagによって、デコーダ104図1がスライス内の最後のマクロブロックがいつ復号されたかを画定することが可能となる。このフラグが使用されるのは、算術符号の最終ビットが、2つ以上のマクロブロックを記述するデータを含む可能性があるからである。0050算術符号化データの終了を符号化することの利点は、従来の手法を検討することによって説明できる。従来の手法では、算術エンコーダの終了は、通常、2つの代案のうちの一方に基づいて行われる。第1のアプローチでは、そのままのレジスタLが送信される。第2のアプローチでは、レジスタLのコンテンツにオフセットが追加され、レジスタLの最上位ビットだけが送信される。第1のアプローチの利点は、デコーダが、エンコーダによって生成されたものと同数のビットを正確に読み取ることである。しかしながら、これによって、余分なビットを送信するという損失がもたらされる。第2のアプローチでは、ビットは節約されるが、デコーダは、エンコーダによって生成されたものより多くのビットを読み取る。これは、デコーダでビットストリームにパディングを行うことによって克服することができる。0051本明細書に開示するアプローチは、両者の最良な点を供する。即ち、デコーダはエンコーダによって生成されたものと同数のビットを読み取り、エンコーダには必要以上のビットを送信させない。これは、イベント、即ちend_of_slice_flagを符号化して、スライスの終了を知らせることによって可能となっている。良好に定められた確率がこのイベントに割り付けられると、デコーダはそれを復号でき、当該イベントの結果が終了を知らせる場合に、デコーダは再正規化を先行することができる。即ち、通常、符号化中に、符号化される全てのシンボルについて、値Rに確率が乗算されて、サブインターバルが得られる。その後、再正規化が行われて、Rの値がある範囲の値に戻される。再正規化は、算術符号化の当業者に周知である。再正規化を先行することによって、読み取られるビットの数がエンコーダによって生成されるビットの数に一致することが保証される。0052一実施形態では、end_of_sliceイベント又は算術符号化の終了を指示する他のイベントに割り当てられる確率は、符号化の終了中にレジスタRに割り当てられた数値によって、再正規化が実行される前に、定められる。一実施形態では、エンコーダとデコーダとが同期することを保証するために、スライス終了フラグに対して、サブインターバルの計算は、Rに記憶された値に確率を乗算することによって実行されない。代わりに、サブインターバルには、固定値、即ち定数が割り当てられる。一実施形態では、固定値2が使用される。より一般的には、end_of_slice_flagを符号化する前に、この値は、レジスタRのコンテンツの値とは独立していなければならない。これは、ビットストリームに入れられる最後のシンボルビットのために行われる。サブインターバルを値2に設定することによって、デコーダのオペレーションに影響なく、値1をレジスタLの値に加算することができる。これによって、ローLレジスタ全体のコンテンツをビットストリームに送り込むことが可能となる。全レジスタLのコンテンツが送信されるので、この例では再正規化が不要である。0053一実施形態では、レジスタLの最下位ビットを1に設定して、Lのコンテンツを送信する。レジスタLの最下位ビットを1に設定することは、その最下位ビットがゼロである場合にLに1を加算することと等価である。したがって、算術エンコーダによって生成される最終ビットは1に等しく、算術符号を含むビットストリームの最終バイトは非ゼロの値を有する。結果において、レジスタLの最下位ビットは、ストップビットとなる。<スタフィングバイトの追加>0054一実施形態では、エンコーダは、圧縮されたデータのビットストリームにスタフィングバイト又はビットを挿入する。一実施形態では、スタフィングバイトは、スライスの算術符号の後に、ストップビット及び0、1又はそれ以上の整列ビットに続いて挿入される。整列ビットを挿入して、追加されるスタフィングバイトがバイト境界に挿入されることを保証する。ストップビットの後にスタフィングバイトを入れることの利点の一つは、デコーダがスタフィングバイトを復号する必要がないことである。したがって、デコーダは、エンコーダによって生成された符号化データのビット数と同数のビットを復号する。0055一実施形態では、圧縮されたビットストリームに挿入されるスタフィングバイトの数は、エンコーダに入力されるイベントの数と、データブロックの数と、エンコーダから出力されるビットの数との間の関係を維持することに基づいている。この関係を、より詳細に以下に説明する。0056一実施形態では、スタフィングバイトが特定のパターンを有している。このパターンは、ユニークであり、デコーダは、スタフィングバイトが存在することを、ストップビット及び一つ以上の整列ビットに続くこの特定パターンのビットを識別することによって、決定することができる。このような決定がなされると、デコーダは、スタフィングバイトを復号する必要がない。一実施形態では、デコーダは、デマルチプレクス機能を有しており、この機能は、ヘッダビットヘッダビットは復号エンジンへ送信されないと同様に、スタフィングバイトがデコーダの算術復号エンジンへ送信されることを防止する。0057一実施形態では、スタフィングビットのパターンは、16進表記で000003の3バイトシーケンスであり、当該バイトシーケンスがビットストリームに追加される。最初の2バイトは、ゼロワード0000となっており、第3バイト03は、スライスの終了の後に、デコーダによって認識され、当該バイトがスタフィングバイトとして識別される。0058一実施形態では、スライスの終了に詰め込まれたスタフィングバイト310の数は、算術復号のオペレーション数とビット数との関係が4以下であることを保証する。図1のエンコーダ102のようなエンコーダは、レジスタCを使用して、イベント復号オペレーション対ビット又はバイトの比をカウントし、さもなければ、追跡することができる。イベントが処理されるたびに、カウンタCが1増加され、更に、ビットが生成されるたびに、カウンタCが4又はバイト生成のたびに32減らされる。一実施形態では、カウント処理は、ヘッダ及びそれに後続するストップ及び整列ビットを含むスライス又は他のイベントセットの全ビットを考慮に入れている。0059一実施形態では、end_of_slice_flagに対する復号オペレーションは、カウンタCによってカウントされない代替の方法ではカウントされるがことに注意されたい。しかしながら、マクロブロック当たり一つのこのようなイベントがあり、このようなイベントの数は、ピクチャーサイズによって良好に制限されることが知られている。この場合、end_of_slice_flagイベントをカウントしないことは、それらをカウントする故に、マクロブロックごとに一度、Cを1増加するが、同時に、256ピクセルごとにマクロブロックごとに一度Cを1減少させることと等価である。或いは又、マクロブロックごとにCを任意の値だけ減少させることもできる。0060一実施形態では、本明細書に記載された手法でスタフィングバイトを追加すると、符号化されたスライスの最小長さが保証される。符号化されたスライスの中間にスタフィングビットを挿入する従来の技術に対し、この進歩によって、エンコーダがデータを符号化する規定、特に、どれほど多くのデータを符号化するかを定める規定が簡単になる。0061エンコーダは、イベントシーケンスにおけるイベントの数を、情報ビットのシーケンスにおける情報ビットの数と、イベントシーケンスで表わされた入力データのセグメント数、即ちブロック数との関数として制約する。例えば、この制約は、次のような線形結合の形態をとる。e≦αBβSここで、eは、情報ビット又は他のエレメントのシーケンスで表わされたイベントの数であり、Bは、情報ビット又は他のエレメントのシーケンスにおける情報ビットの数であり、Sは、イベントシーケンスで表わされたセグメント例えばマクロブロックの数である。また、α及びβは、カウンタへの減少値を表しており、生成される情報ビットの数及び処理されるセグメントの数に対するイベントシーケンスのイベント数の制約を実質的に維持する。0062α及びβの値は、通常、算術コーダのコントローラへ提供される。α及びβの導出について以下に説明する。αの値は、例えば、算術コーダにおいて情報ビットを生成する際のカウンタへの減少値を表わす。一方、βの値は、例えば、データブロックの処理が完了した際のカウンタへの減少値を表わす。別の形態では、当業者には明らかなように、値βを、セグメントの処理の開始時に又はデータブロックの処理中の他の任意の時間にカウンタ値から減少させてもよい。0063全ブロック数S及び値βは既知であるから、β×Sの積を、入力データのブロック例えばマクロブロックの処理後にイベントシーケンスのイベントの数eから減算してもよい。例えば、カウンタを使用して、生成されたビットの数に応じてイベントの数を制約する場合に、当該カウンタを、最初にβ×Sの値だけ減少させ、情報ビットが生成されるたびに値αだけ減少させ、一方、イベントシーケンスの各イベントがエントロピーエンコーダによって処理される度に、1だけ増加させる。0064βの値は、通常、1から100までの範囲内の任意の値であることができ、例えば、以下に述べるように、決定される。αの値は、通常、1から10までの範囲内の任意の値であり、例えば、以下に述べるように決定される。0065ある環境において、例えば、通信媒体が、情報シーケンスに与えられる情報ビットの数を制限する場合には、処理されるべき入力データのブロック数が前もって分からない。これは、例えば、情報シーケンスがインターネットプロトコルIPパケットとしてインターネットを経て送信されるものであって、このIPパケットが最大サイズ制限を有する場合に生じる。これらの環境では、個別の画像の複雑さに依存するが、一つ以上の情報ビットのシーケンスが、入力データの一画像を表わすために、必要となる。しかしながら、情報ビットのシーケンスの生成に使用されるブロックの数は、前もって分からない。その理由は、どれほど多くのセグメントを処理した後に情報ビットシーケンスの最大サイズに達するか分からないからである。処理されるべき入力データのセグメント数が前もって分からない場合には、コントローラは、個別のイベントシーケンスを表す一つ以上のブロックが符号化されるときに、イベントシーケンスを考慮する。例えば、カウンタを使用し、生成されたビットの数に応じてイベントの数を制約する場合には、当該カウンタを、各ブロックが処理されるたびに値βだけ減少させ、情報ビットが生成されるたびに値αだけ減少させ、一方、イベントシーケンスのイベントがエントロピーエンコーダによって処理される度に1だけ増加させる。0066α及びβの値は、エンコーダのシステム設計者が上述した一つ以上の制限を考慮することによって前もって決定されて、コントローラに与えられてもよい。これに代えて又はこれに加えて、α及びβの値は、上述した制限の一つ以上に基づいて、又はエンコーダのデフォルト値として、コントローラ、又はエンコーダの他の要素によって、決定されてもよい。コントローラが、規格又は復号装置によって課せられる制限の一つ又は両者を使用してα及びβの値を決定する場合に、一つ以上の当該制限に関する情報がコントローラのメモリ図示せずに記憶され、α及びβの値を決定する際にコントローラによって使用される。加えて又はこれに代えて、当該制限に関する情報は、例えば、外部メモリ即ちデジタルビデオディスクDVDや、DVDプレーヤ装置のような外部装置によって、或いは、例えば特定の入力データの符号化に関する幾つかの機能を取り扱うシステムエンジニアから、コントローラへ供給されてもよい。後者の場合に、システムエンジニアは、当業者には明らかなように、符号化規格及び/又は復号装置によって課せられる制限に関する情報をコンソール又は他の入力装置図示せずに入力することができ、又は、他の方法で指定することができる。0067更に、α及びβの値を決定する場合に、複雑さの制約が厳し過ぎるかどうか、例えば、α及び/又はβの値が低過ぎるかどうかを考慮してもよい。情報ビットシーケンスの終端に存在するスタフィング情報ビットの割合が高いこと即ち、スタフィングバイト又はビットの数が情報シーケンスの情報ビットの約1又は2以上であることは、その制約が厳し過ぎることを示す。当業者であれば、例えば、使用できる特定の規格及び/又はデコーダを考慮に入れて、他の割合がスタフィング情報ビットの高い割合を示してもよいことは明らかであろう。0068例えば、α及びβの値が制約を過度に厳しくすると決定された場合に、α及びβの値を高くして、スタフィングバイトが追加される見込みを低減する即ち、符号化情報シーケンスにおけるクオリティペナルティの見込みを低減することができる。α及びβの値を高くする場合には、符号化された情報シーケンスの復号に使用されるデコーダについて得られる複雑さの限界に対してその影響が考慮される。このような考慮は、デコーダを実施するためのコストを含むことができる。複雑さの限界が高い場合には、より大きな処理能力がデコーダに必要とされる。必要な処理能力の増加は、おそらく高い実施コストを招く。尚、一実施形態では、各マクロブロックからデータを符号化した後にα及びβの変更がなされてもよい。0069α及びβの値は、線形回帰技術を使用して実験的に決定することができる。各々がS個のセグメントを表すイベントシーケンスが、複雑さの制約を強いることなく、符号化されてもよい。イベントシーケンスzごとに、イベント数ezに対し、生成される情報ビット数Bzが分かる。これは、線形回帰式、即ちデータ対ez、Bzを近似する線ecBdを使用して決定することができる。したがって、線e=αββSの上に存在するデータ対ez、Bzの数を減らし、潜在的にはそれを最小にするように、α及び/又はβの初期値を高くすることができる。0070上述した種々の技術の一つ以上によって決定されたα及びβの値を使用して、エンコーダは、生成される各情報ビットに対しαの値を考慮し即ち、αの値だけカウンタを減少させ、入力データのセグメントが完了した際にβの値を考慮する即ち、βの値だけカウンタを減少させることができる。例えば、α及びβが整数値である場合には、このような考慮即ち、一つ以上のカウンタに対する減少を直接行うことができる。0071例えば、α及びβの一方又は両方が分数値である場合には、共通の分母を決定して、α及びβの非分数値を与えることができる。この環境では、α及びβの新たな非分数値は、例えば、情報ビットの発生時及びセグメント処理の完了時に各々α及びβの値だけカウンタを減少させることによって、上述したように考慮される。決定された共通の分母は、例えば、イベントシーケンスにおける各イベントを処理する際に共通の分母の値をカウンタ値に加算することによって考慮される。例えば、α及びβの値が各々4/3及び25と決定された場合には、共通の分母は、3と決定される。したがって、α及びβの非分数値は、共通の分母を使用して各々4及び75と決定される。したがって、カウンタを使用してα及びβの値を考慮する場合には、カウンタを、情報ビットが発生されるたびに4だけ減少させ、各セグメントの処理が完了すると75だけ減少させ、更に、イベントが処理されるたびに3だけ増加させる。<エンコーダのオペレーションの例>0072図4は、算術エンコーダの一実施形態のブロック図である。図4に示すように、算術エンコーダ400は、シーケンサ405と、確率推定器410と、符号化エンジン415とを備え、これらは互いに接続されている。一つ以上の入力データライン420は、エンコーダ400にイベントシーケンス425例えば、2進イベントの順序付けされたシーケンスを受信するための入力ポートを備えている。イベントシーケンスは、エンコーダ400によって、以下に述べるように処理されて、情報シーケンスを生成する。一実施形態では、この情報シーケンスは、順序付けされたシーケンスであり、少なくとも一つの情報エレメント例えばビットで構成されている。一実施形態では、情報シーケンスにおける情報ビットの数は、イベントシーケンスにおけるイベントの数より少ない。出力430は、エンコーダ400から情報シーケンス435を送信するための出力ポートを備えている。この情報シーケンスの順序付けされたビットのシーケンスは、0又は1の値を有する一つ以上のビットを含む。0073イベントシーケンス425を受信すると、シーケンサ405は、確率推定器410及び符号化エンジン415の両者にイベント425を順次送信する。また、イベントシーケンス425の2進イベントごとに、シーケンサ405は、当該2進イベント用に確率推定器410へコンテクスト情報を送信する。確率推定器410は、受信したコンテクスト情報を使用して、確率推定値PAを生成する。確率推定値PAは、符号化エンジン415へ送信される。一実施形態において、確率推定器410は、多数の確率推定値を符号化エンジン415へ送信し、符号化エンジン415は、確率推定値の一つをR値に基づいて選択する。これに代えて、R値が確率推定器410へ送信され、確率推定器が当該R値を使用して、送信されるべき一つの確率推定値を選択してもよい。確率推定器410は、次いで、受信した2進イベントの値に基づいてその内部状態を更新する。符号化エンジン415は、受信した2進イベント及び対応の確率推定値PAを使用して0以上の情報ビットを生成する。0074一実施形態において、符号化エンジン415は、算術符号化データの終了を指示するイベントを符号化する。このイベントは、スライス終了フラグであってもよく、又はビットストリームにおいて非算術符号化データが少なくとも続くという別のインジケータであってもよい。0075ゼロ以上の情報ビットを発生する際に、符号化エンジン415は、レンジレジスタ465、ローレジスタ470、ビットアウトスタンディングレジスタ475及びカウンタレジスタ480を含む種々のレジスタを使用する。算術符号化を実行するエンコーダ400のオペレーションは、この技術分野では周知である。0076一実施形態では、エンコーダ400は、情報ビットに対するイベントの関係を限定する。このことは、本明細書の他の部分で説明している。エンコーダ400は、このオペレーションを、その一部分については、上述したようにスタフィングバイト又はビットを情報シーケンスに挿入することによって実行する。0077図5は、イベントの符号化に関する一実施形態のフロー図である。このプロセスは、ハードウェア例えば、回路、専用ロジック等、ソフトウェア例えば、汎用コンピュータシステム又は専用マシンで実行されるようなソフトウェア或いはその両方の組合せで構成される処理ロジックによって実行される。算術符号化プロセスへの入力は、コンテクストを識別するコンテクストID、値R、L、及びsymCntを用いて復号される2進イベントであり、出力に書き込まれるのは、符号化によって生じたビットである。一実施形態では、符号化は、復号と対称であり、算術符号化エンジンの状態は、上述したように、サブインターバルの下端を指すLの値と、サブインターバルの対応レンジを特定するRの値とで表わされる。0078一実施形態では、符号化プロセスは、符号化エンジンが初期化された後にのみ呼び出される。一実施形態では、初期化は、ゼロに等しいLの値及び0x01FEに等しいRの値を送信し、第1ビットフラグを1に、ビットアウトスタンディングBO値及びsymCntCカウンタを0にセットすることによって実行される。第1ビットフラグは、符号化中に、エンコーダが初めてプットビット手順に入るときを指示するために使用される。symCntカウンタは、符号化されるイベントの数を指示する値を記憶する。0079図5を参照する。このプロセスは、値RLPSを次のように導出することによって処理ブロック501、単一イベント例えばビットの符号化を開始する。一実施形態では、処理ロジックは、Rインデックス即ちRidxを、Rの値を右へ6位置シフトして数値3Hexとアンドした値に等しくすることによって、変数RLPSを導出する。次いで、処理ロジックは、RLPSの値を、Ridxの値と、コンテクストに関連付けられている現在のコンテクストに対する状態の値とを使用し、図16Aに示すテーブルのような確率推定状態マシンテーブルにアクセスすることによって決定される値に、等しくする。Rの値は、次いで、現在のR値からRLPSを引いたものにセットされる。0080MPSカウントに対するサブレンジインターバルを計算した後に、処理ロジックは、符号化されている2進イベントの値がMPSの値に等しくないかどうかテストする処理ブロック502。2進イベントの値がMPSに等しい場合には、処理ロジックは、MPSパスをとって処理ブロック503へ移行し、そこで、処理ロジックは、状態マシンを、図16Bのテーブルを使用して、そのコンテクストに対して状態マシンに指示された次の状態へと更新し、次いで、プロセスが処理ブロック508へ移行する。符号化されている2進イベントがMPSの値に等しくないと判断すると、処理ロジックは、LPSパスをとって処理ブロック504へ移行し、そこで、処理ロジックは、Lの値を、Lの値とRの値の和に等しくセットし、次いで、Rの値を、RLPSの値に等しくする。0081その後、処理ロジックは、特定のコンテクストに対する状態がゼロに等しくないかどうか決定する処理ブロック505。一実施形態では、状態ゼロは、50/50の確率に対応する状態である。或いは又、状態ゼロは、例えば、50/50の確率に近い別の確率に対応する状態である。コンテクストの状態がゼロに等しくない場合には、処理ロジックは、処理ブロック507へ移行する。コンテクストの状態がゼロに等しい場合には、処理ロジックは、MPSの意味を切り換え処理ブロック506、次いで、処理ブロック507へ移行し、ここで、処理ロジックは、コンテクストの状態番号を、図16Bのテーブルを使用して次の状態へ更新する処理ブロック507。0082処理ブロック507及び503を実行した後に、プロセスは、処理ブロック508へ移行し、そこで、処理ロジックは、図6に示す再正規化のような再正規化手順を実行する。次いで、処理ロジックは、イベントカウンタの値を1だけ増加し処理ブロック509、処理を終了する。0083図6は、エンコーダの再正規化手順の一実施形態のフロー図である。このプロセスは、ハードウェア例えば、回路、専用ロジック等、ソフトウェア例えば、汎用コンピュータシステム又は専用マシンで実行される或いはその両方の組合せで構成される処理ロジックによって実行される。0084次に、図6を参照する。まず、処理ロジックは、Rの値が100Hex未満であるかどうかテストする処理ブロック601。Noの場合、プロセスは終了となる。Yesの場合、プロセスは、処理ブロック602へ移行し、そこで、処理ロジックは、Lの値が100Hex未満であるかどうかテストする。Yesの場合、処理ブロックは、処理ブロック603へ移行し、そこで、プットビット手順がパラメータ0で実行され、その後、プロセスは、処理ブロック608へ移行する。処理ロジックは、Lの値が100Hex以上であると判断すると、Lの値が200Hexより大きいかどうかテストする。Noの場合、処理ロジックは、Lの値から100Hexを減算した値にLの値をセットし、ビットアウトスタンディングBOの値を、パラメータ1で1だけ増加する処理ブロック605。次いで、プロセスは、処理ブロック608へ移行する。Lの値が200Hex以上である場合には、プロセスは、処理ブロック606へ移行し、そこで、処理ロジックは、Lの値を、Lの値から200Hexを減算した値にセットし、プットビット手順を実行し処理ブロック607、次いで、処理ブロック608へ移行する。0085処理ブロック608では、処理ロジックがRの値を左へ1位置シフトし、且つLの値を1位置シフトする。その後、プロセスは、処理ブロック601へ移行し、プロセスが繰り返される。0086図7は、プットビット手順の実施形態を実行するプロセスの一実施形態を示す。プットビット手順は、ゼロ以上のビットをビットストリームに書き込む。このプロセスは、ハードウェア例えば、回路、専用ロジック等、ソフトウェア例えば、汎用コンピュータシステム又は専用マシンで実行される或いはその両方の組合せで構成される処理ロジックによって実行される。0087図7に示すように、処理ロジックは、最初に、第1ビットフラグがゼロに等しくないかどうかチェックする処理ブロック701。第1ビットフラグが1にセットされている場合には、処理ロジックは、第1ビットフラグをゼロに等しくセットする処理ブロック702。次いで、プロセスは、処理ブロック704へ移行する。Noの場合、処理ロジックは、値Bをもつビットを送信し処理ブロック703、次いで、処理ロジックが、処理ブロック704へ移行する。0088処理ブロック704において、処理ロジックは、ビットアウトスタンディングBOの値がゼロより大きいかどうかテストする。Noの場合、プロセスは終了となる。Yesの場合、処理ロジックは、値1-Bをもつビットを送信し、BOの値を1だけ減少させる処理ブロック705。その後、処理ロジックが、処理ブロック704へと移行する。0089図8は、終了前にイベントを符号化するプロセスの一実施形態を示すフロー図である。このプロセスは、スライスの終了と、算術符号化の終了を知らせる他の2進イベントとの符号化に使用される。このプロセスは、ハードウェア例えば、回路、専用ロジック等、ソフトウェア例えば、汎用コンピュータシステム又は専用マシンで実行される或いはその両方の組合せで構成される処理ロジックによって実行される。0090図8に示すように、処理ロジックは、最初にRの値を2だけ減少させる処理ブロック801。次いで、処理ロジックは、符号化されている2進イベントの値がゼロに等しくないかどうかテストする処理ブロック802。イベントがゼロに等しい場合には、処理ロジックは、図6に示したような再正規化手順を実行し処理ブロック803、次いで、プロセスは、処理ブロック806へ移行する。符号化されるべき2進イベントの値がゼロに等しくない場合には、処理ロジックは、Lの値を、Lの値とRの値の加算値にセットし処理ブロック804、エンコーダフラッシング手順を実行し処理ブロック805、次いで、処理ブロック806へ移行する。処理ブロック806では、処理ロジックが、イベントカウンタの値を1だけ増加し、符号化プロセスが終了する。0091上記プロセスにおいて明らかなように、一実施形態では、2進イベントの値が1に等しい場合に、算術符号化が終了となり、イベントを符号化した後にフラッシング手順が適用される。このようなイベントを符号化すると、書き込まれる最後のビットは、1に等しいストップビットを含む。0092図9は、終了時のフラッシュに係るプロセスの一実施形態を示すフロー図である。このプロセスは、ハードウェア例えば、回路、専用ロジック等、ソフトウェア例えば、汎用コンピュータシステム又は専用マシンで実行される或いはその両方の組合せで構成される処理ロジックによって実行される。0093図9に沿って説明する。処理ロジックは、最初に、Rの値を2にセットする処理ブロック901。処理ロジックは、次いで、図6に示した再正規化手順のような再正規化手順を実行する処理ブロック902。処理ロジックは、次いで、Lの値を右に9位置シフトして、値1Hexとアンドしたものに等しい値に対して図7に示すプットビット手順を実行する処理ブロック903。Lレジスタの値をシフトしたコンテンツに対してアンドオペレーションを実行した結果は、10番目のビット位置最下位ビットから数えてにビットを生成させ、その後、プットビット手順を使用して出力される。0094最終的に、処理ロジックは、Lレジスタの値を7位置右へシフトして、3Hexの値とアンドし、次いで、1Hexとオアしたものに等しい2つのビットを送信する処理ブロック904。1Hexとのオアオペレーションは、ストップビットを追加するために実行される。<デコーダのオペレーションの例>0095図10は、算術デコーダ1000の一実施形態を示すブロック図である。図10に示すように、デコーダ1000は、シーケンサ1005と、確率推定器1010と、復号エンジン1015とを備え、これらは互いに接続されている。入力1020は、デコーダ1000への情報シーケンス1025例えば2進ビットの順序付けされたシーケンスのためのポートを提供する。シーケンス1025の2進ビットは、0又は1の値を有する。一実施形態では、デコーダ1000は、情報シーケンスを処理して、イベントシーケンス1035を生成する。生成されたイベントシーケンスは、単一ビット値以外の値を有する多数のイベント例えば2進イベントを含む順序付けされたイベントシーケンスである。このイベントシーケンスは、デコーダ1000からの少なくとも一つの出力ポートを含む出力1030へ供給される。0096情報シーケンス1025を受信すると、シーケンサ1005は、復号エンジン1015に一つ以上のビットを送信する。デコーダ1000は、イベントシーケンスの一つ以上のイベントを次のように繰り返し生成する。シーケンサ1005は、各イベントについて、対応のコンテクストを確率推定器1010に送信する。0097確率推定器1010は、受け取ったコンテクストの値に基づいて、対応の確率推定値PAを発生する。この確率推定値PAは、復号エンジン1015へ送信され、復号エンジン1015によってイベントの生成に使用される。一実施形態では、確率推定器1010は、多数の確率推定値を復号エンジン1015へ送信し、次いで、復号エンジン1015は、Rの値に基づいて確率推定値の一つを選択する。或いは又、Rの値が確率推定器1010へ送信され、確率推定器がこれを使用して、送信されるべき一つの確率推定値を選択してもよい。次いで、確率推定器1010は、復号エンジン1015から受け取った2進イベントの値に基づいてその内部状態を更新する。0098復号エンジン1015は、生成された各イベントを確率推定器1010及びシーケンサ1005へ送信する。復号エンジン1015は、生成された各2進イベントに対してゼロ以上の情報ビットを消費する。したがって、シーケンサ1005は、イベントの生成後に、情報シーケンスからのゼロ以上のビットを復号エンジン1015へ送信する。復号エンジン1015は、レンジレジスタ1065や値レジスタ1070を含む種々のレジスタを使用して、イベントシーケンス1035のイベントを生成する。デコーダ1000のオペレーションは、以下に説明するフロー図に示されている。0099以下のフロー図は、デコーダ1000のようなデコーダの一実施形態によってスライスに対して実行される復号オペレーションを示している。一実施形態において、デコーダは、図12、14A、14B、15A又は15Bに示されたフロー図に従い、コンテクストの値に基づいて復号を実行する。図示されたプロセスは、他のプロセスに組み込まれてもよく、それに具体化された改善の利益を得るように他の方法で適用、或いは変更されてもよい。一実施形態では、デコーダは、一度に1バイトを読み取る。別の実施形態では、デコーダは、一度に1ビットを読み取る。0100図11は、算術デコーダの初期化プロセスの一実施形態を示すフロー図である。このプロセスは、ハードウェア例えば、回路、専用ロジック等、ソフトウェア例えば、汎用コンピュータシステム又は専用マシンで実行される或いはその両方の組合せで構成される処理ロジックによって実行される。0101図11を参照する。まず、プロセスは、処理ロジックがレンジRを所定の数値にセットすることで始まる処理ブロック1101。一実施形態において、当該所定の数値は、0xff00である。レンジRを初期化した後、処理ロジックは、圧縮されたデータの2バイトをレジスタVへ読み込む処理ブロック1102。一実施形態では、レジスタVは、圧縮されたビットを一度に1バイト記憶する。レジスタVは、圧縮されたデータを一度に1ビット記憶するように実施されてもよいが、本明細書に記載されたプロセスに使用される定数が、それに応じて変更されなければならない。0102より詳細には、図示されたように、処理ロジックは、1バイトを読み込み、それを左に8位置シフトし、次いで、別のバイトを取得し、それを算術オアオペレーションを用いてレジスタVへ加算する。圧縮されたデータがレジスタVに読み込まれると、処理ロジックは、レジスタBの値を所定値にセットする。レジスタBは、処理に使用できるレジスタV内の余りのビット数を指示する。レジスタBの値が0未満になると、圧縮されたデータの別のバイトをフェッチすることが必要となる。一実施形態では、所定値は7である。0103図12は、2進イベントを復号するプロセスの一実施形態を示すフロー図である。このプロセスは、ハードウェア例えば、回路、専用ロジック等、ソフトウェア例えば、汎用コンピュータシステム又は専用マシンで実行される或いはその両方の組合せで構成される処理ロジックによって実行される。0104図12に示すように、このプロセスは、LPSのインターバルのサイズを計算することによって開始する処理ブロック1202。一実施形態において、この計算は、乗算によって実行される。乗算は、コンテクストCTXに関連付けられた状態に基づくテーブルルックアップを使用することによって近似される。一実施形態では、有限状態マシンを使用して、マシンの状態に依存している確率が何であるかを指示する。次いで、ルックアップするのは、状態の値と、Rの最上位ビット後の次の2つの最上位ビットである。ルックアップを実行するテーブルの例を図16Aに示す。また、テーブルを生成する方法の例を以下に示す。0105テーブルルックアップの結果は、7シフトされる。その理由は、この手法では、一度にビットではなくバイトが読み取られるからである。テーブルルックアップのシフトされた結果は、LPSのサブレンジインターバルであり、RLPSと称される。0106また、処理ブロック1202の一部分として、処理ロジックは、LPSのサブレンジインターバルRLPSをレジスタRの値から減算することによって、MPSのサブインターバルレンジを計算する。処理ロジックは、Rの値を減算の結果に等しくセットする。0107MPSのサブレンジインターバルを計算した後に、処理ロジックは、レジスタVの値が、レジスタRに記憶されたMPSのサブインターバル以上であるかどうかテストし、処理されている現在のビットがLPSのサブレンジ内であることを指示する処理ブロック1203。Noの場合、処理ロジックは、MPSパスをとって処理ブロック1204へ移行し、そこで、処理ロジックは、復号される値即ち戻される結果Sを、その特定のコンテクストに対するMPSであると定義された値に等しくセットする。次いで、処理ロジックは、当該コンテクストに対する状態マシンを、図16Bのテーブルを使用して当該コンテクストに対して状態マシンに指示された次の状態へと更新する。一実施形態では、MPSに対し、状態マシンの更新は、状態テーブルの状態を1だけ増加することからなる。0108処理ロジックは、値VがレジスタRの値以上であると判断すると、LPS経路をとって処理ブロック1205へ移行し、そこで、結果Sを、特定のコンテクストCTXに対するLPSMPSではないに等しくセットし、値Vを、Vの現在値からレンジRの値を減算した結果に等しくセットし、更に、レンジRを、LPSのレンジ、即ちRLPSに等しくセットする処理ブロック1205。0109また、処理ロジックは、2進イベントのコンテクストに対する状態がゼロであるかどうかもチェックする処理ブロック1206。一実施形態では、状態0は、50/50の確率に対応する状態である。或いは又、状態ゼロは、例えば、50/50の確率に近い別の確率に対応する状態であってもよい。2進イベントのコンテクストに対する状態がゼロでない場合に、プロセスは、処理ブロック1208へ移行する。2進イベントのコンテクストに対する状態がゼロである場合に、処理ロジックは、MPSの意味を切り換える処理ブロック1207。0110その後、コンテクストの状態番号は、図16Bのテーブルを使用して次の状態へ更新され処理ブロック1208、処理ロジックは、以下に詳細に述べる再正規化手順を実行する処理ブロック1209。0111図13は、再正規化手順のフロー図である。このプロセスは、ハードウェア例えば、回路、専用ロジック等、ソフトウェア例えば、汎用コンピュータシステム又は専用マシンで実行される或いはその両方の組合せで構成される処理ロジックによって実行される。0112図13に示すように、プロセスは、Rが8000Hex未満であるかどうか処理ロジックがテストすることによって開始する処理ブロック1301。Rが8000Hex以上である場合には、再正規化プロセスが終了となる。Yesの場合、処理ロジックは、R及びVの値を2倍にする処理ブロック1302。一実施形態では、処理ロジックは、R及びVのビットを左へ1位置シフトすることによってR及びVの値を2倍にする。また、Bの値は、1だけ減少される。その理由は、シフト処理によって処理に利用可能なビットが一つ少なくなるからである。次いで、処理ロジックは、Bの値が0未満であるかどうかチェックする処理ブロック1303。Noの場合、処理は処理ブロック1301へ移行し、プロセスが繰り返される。Bの値が0未満である場合には、処理が処理ブロック1304へ移行し、そこで、Bの値が7にセットされ、処理されるべき別のバイトがフェッチされて、レジスタVの現在のコンテンツと論理オアされる。その後、処理は処理ブロック1301へ移行し、プロセスが繰り返される。0113図14A及び14Bは、同じ確率でイベントを復号するためのフロー図である。図14Aは、レジスタVのサイズが16ビットより大きいときに使用され、一方、図14Bは、レジスタVのサイズが16ビットであるときに使用される。これらの手法は、一度に1バイトをフェッチするときに使用される。0114これらのプロセスは、ハードウェア例えば、回路、専用ロジック等、ソフトウェア例えば、汎用コンピュータシステム又は専用マシンで実行される或いはその両方の組合せで構成される処理ロジックによって実行される。0115分布がゼロを中心とするものであって、正の値又は負の値を得る見込みがほぼ同じである場合に、これらのプロセスを使用できる。例えば、これらプロセスは、係数の符号値を処理するときに使用される。それが正であるか負であるかの見込みを推定するのではなく、固定推定値を使用して、確率が50/50であることを認識する。したがって、Rに確率を乗算するためのテーブルルックアップを実行する必要がない。尚、これらは、終了に影響しない。0116図14Aを参照する。プロセスは、処理ロジックがVの値を2倍にすると共にBの値を1だけ減少させることによって開始する処理ロジック1401。Vの値を2倍にすることは、Vのビットを左へ1位置シフトすることで行われる。0117次いで、処理ロジックは、Bの値が0未満であるかどうかチェックする処理ブロック1402。Noの場合、処理は、処理ブロック1404へ移行する。Bの値が0未満である場合には、処理ブロック1403へ移行し、そこで、Bの値が7にセットされ、処理されるべき別のバイトをフェッチされて、レジスタVの現在のコンテンツと論理オアされる。0118処理ブロック1404において、処理ロジックは、Vの値がRの値以上であるかどうかテストする。Yesの場合、処理ロジックは、結果Sを1にセットし、更に、Vの値を、Vの値からRの値を減算した結果にセットし処理ブロック1405、プロセスが終了する。Noの場合、処理ロジックは、結果Sを0にセットし処理ブロック1406、プロセスは終了となる。0119次に、図14Bを参照する。処理ロジックが値V’をVに等しくセットし、Vの値を2倍にし、Bの値を1だけ減少させることによって、プロセスが開始する処理ロジック1411。Vの値を2倍にすることは、Vのビットを左へ1位置シフトすることによって実行される。0120次いで、処理ロジックは、Bの値が0未満であるかどうかチェックする処理ブロック1412。Noの場合、処理は、処理ブロック1414へ移行する。Bの値が0未満である場合には、処理ブロック1413へ移行し、そこで、Bの値が7にセットされ、処理されるべき別のバイトがフェッチされて、レジスタVの現在のコンテンツと論理オアされる。0121処理ブロック1414では、処理ロジックは、Vの値がRの値以上であるかどうか、又はV’が8000Hex以上であるかどうかテストする。Yesの場合、処理ロジックは、結果Sを1にセットすると共に、Vの値を、Vの値からRの値を減算した結果にセットし処理ブロック915、プロセスが終了する。Noの場合、処理ロジックは、結果Sを0にセットし処理ブロック916、プロセスは終了となる。0122図15Aは、算術符号化の終了を示す符号化イベントを復号するための一実施形態を示すフロー図である。このようなイベントは、スライス終了フラグを構成する。スライス終了フラグについては、シンタックスを使用して、スライス終了フラグの存在をデコーダに指示することができる。一実施形態では、このプロセスは、各マクロブロックについて実行されるが、スライスにおける最後のマクロブロックについてのみ、スライスの終了を指示する結果が得られる例えば、1の結果が出力される。0123算術符号化の終了を知らせるためのイベントデコーダに対するは、ビットストリームにおいて算術符号化の後に続こうとするデータが、非圧縮のものか又は算術符号化以外の別の符号化技術で圧縮されたものであるときに使用される。尚、この非圧縮のデータ又は非算術符号化技術で圧縮されたデータの後に、追加の算術符号化データが続いてもよい。したがって、終了を知らせるためのイベントは、非算術符号化データがビットストリームにおいて算術符号化データとインターリーブされる場合に使用される。0124このプロセスは、ハードウェア例えば、回路、専用ロジック等、ソフトウェア例えば、汎用コンピュータシステム又は専用マシンで実行される或いはその両方の組合せで構成される処理ロジックによって実行される。0125図15Aに沿って説明する。まず、処理ロジックは、Vの値が100Hex未満であるかどうかテストし処理ブロック1501、それによって、スライスにおける最後のマクロブロックに到達したことを指示する。Vの値が100Hex未満である場合に、処理ロジックは、復号されたシンボルを表わす結果Sを1にセットし処理ブロック1502、スライスに対する復号プロセスが終了する。Vの値が100Hex未満でない場合に、処理ロジックは、出力結果Sを0にセットし、Rの値を、Rの値から100Hexを減算した結果にセットし、更に、Vの値を、Vの値から100Hexを減算した結果にセットする処理ロジック1503。次いで、処理ロジックが、図3の再正規化手順を実行して処理ブロック1504、プロセスが終了となる。0126尚、一実施形態では、MPSとLPSとの間の規定を切り換えてもよい。図15Bは、MPSとLPSとの間の規定を切り換えた場合に、終了前のイベントを符号化するプロセスの一実施形態を示すフロー図である。このプロセスは、ハードウェア例えば、回路、専用ロジック等、ソフトウェア例えば、汎用コンピュータシステム又は専用マシンで実行される或いはその両方の組合せで構成される処理ロジックによって実行される。0127図15Bに示すように、処理ロジックは、Rの値から100Hexを減算することで開始する処理ブロック1511。次いで、処理ロジックは、Vの値がRの値以上であるかどうかテストする処理ブロック1512。Yesの場合、処理ロジックは、復号されたシンボルを表わす出力結果Sを1にセットし処理ブロック1513、次いで、終了前のイベントを復号する復号プロセスが終了となる。したがって、再正規化は実行されない。Noの場合、処理ロジックは、出力結果Sを0にセットし処理ブロック1514、図13の再正規化手順を実行し処理ブロック1515、次いで、プロセスは終りとなる。<確率推定のための状態マシンの構造>0128図16A及び16Bにおける状態マシンを構成するためのプロセスの一例をCコードで以下に示す。CcodedefineNb4definePmax05definePmin001875defineregsize9defineONEdoublealphadoublesumintijdoubleqfloatprob64NintnextstateMPS64NintnextstateLPS64NintswitchMPS64NintgLPSN4alphapowsum05forprob64iPmaxpownextstateMPS64iN1i1qprob64ialphaqqprob64iqloglogsumqksumknextstateLPS64iOikforRTABij05ifRTABijONE40129上記コードにおいて、Nは、状態マシンにおける状態の数を定める。一実施形態において、状態マシンは対称的であり、合計状態数は、2Nこの例では128である。状態は、状態0とN-1それらも含めてとの間の数値と、MPSフラグ0又は1のいずれがMPSであるかを決定するとの2つの変数で表わされる。0130一実施形態では、大きな状態番号がLPSの低確率に対応するように、状態が編成される。状態マシンは、以下の手順に近づくように定義される。ap91sendbit1sendbitstopbitwhilesendbitalignmentbitvoidbitplusfollowifFB0elsesendbitwhileBOsendbitvoidencoderenormwhileifbitplusfollowelseifbitplusfollowL0x200elseBOL0x100R64RrLPSifstatectxnextstateMPSstatectxelseLRRrLPSifMPSstatectxMPSstatectxstatectxnextstateLPSstatectxencoderenormvoidencodeequiprobeventL0x400bitplusfollowL0x400elseBOL0x200voidencodeendofsliceflagifR2L2encoderenormDecodervoidstartdecodedecodesliceheaderwhilegetbitR0xff80VgetbyteRVRbit1elsebit0returnbitintdecodeeventrLPStablestatectx4Rbit1elsebit0decoderenormreturnbitDecodervoidstartdecodedecodesliceheaderwhilegetbitR0x1feV0forVgetbitvoidfinishdecodewhilegetbitalignementbitwhilegetbytestuffingbyteintdecoderenormwhileRRVRbit1elsebit0returnbitintdecodeeventrLPStablestatectx4RrLPSifstatectxnextstateMPSstatectxbitMPSstatectxelsebitMPSstatectxVRRrLPSifMPSstatectxMPSstatectxstatectxnextstateLPSstatectxdecoderenormreturnbitintdecodeendofsliceflagifbit1elsebit0R2V2decoderenormreturnbitAlternativebitbasedendofsliceflagdecodingforusewhentheMPSLPSconventionisswitchedMPS/LPSの規定が切り替えられるときに使用される、代替のビットベースのスライス終了フラグの復号intdecodeendofsliceflagR2ifbit1elsebit0decoderenormreturnbit0139尚、上述した算術コーダには、上部インターバル及び下部インターバルの2つに分割されるインターバルがある。一方のインターバルは、MPSを表わし、他方のインターバルは、LPSを表わす。一実施形態では、MPS及びLPSをインターバルに割り当てる処理は、一方のインターバルに1を割り当て、他方のインターバルに0を割り当てる処理を含む。上述したソースコードでは、end_of_slice_flagを符号化するためにインターバルが分割される場合に、MPS値0が上部サブインターバルに割り当てられる。また、MPSを下部サブインターバルに割り当てることもできる。0140以下のコードは、別のエンコーダ例を示す。尚、このコードでは、Sは、上述したように制限する関係を満足するためのスライスにおける最小バイト数である。voidstartencodesendNALfirstbyteencodesliceheaderwhilesendbitR0x1ferangeL0lowBO0bitsoutstandingC0eventcounterFB1firstbitflagvoidfinishencodebitplusfollow1forsendbit1sendbitstopbitwhilesendbitalignmentbitRBSPtoEBSPSminbyteswhilesendthreebyteswritebytesdirectlyintoNALunitvoidbitplusfollowifFB0elsesendbitwhileBOsendbitvoidencoderenormwhileifbitplusfollowelseifbitplusfollowL0x200elseBOL0x100R64RrLPSifstatectxnextstateMPSstatectxelseLRRrLPSifMPSstatectxMPSstatectxstatectxnextstateLPSstatectxencoderenormCvoidencodeequiprobeventL0x400bitplusfollowL0x400elseBOL0x200CvoidencodeendofsliceflagifR2L2encoderenorm0141上記コードにおいて、ヘッダの一部分である第1バイトをNALユニットに送信する処理は、後続するデータの形式を指示するために実行される。NALユニット及びその使用法は、この技術分野では周知である。0142RBSP_to_EBSPの関数呼び出しは、データをビットストリームに挿入させる。より好ましくは、一実施形態において、ビットストリームに所定数の連続するゼロが発生するのを防止する方法として、03Hexが0000Hexバイトの後に次のパターン、例えば、000000、000001、000002、000003で挿入される。その結果、000000Hex、000001Hex及び000002Hexのパターンが圧縮されたデータに現われることがなく、これを再同期マーカーとして使用することができる。デコーダが000003Hexパターンに遭遇すると、逆の手順によって03がビットストリームから除去される。0143本明細書に説明したエンコーダ及びデコーダのこのような一つの使い方は、ビデオデータを符号化及び復号するものであるが、当業者であれば、本明細書に説明したエンコーダ及びデコーダは、エンコーダの場合にイベントシーケンスが情報シーケンスへ圧縮され、デコーダの場合にその情報シーケンスが圧縮解除されるような任意の場面に使用できることが明らかであろう。更に、エンコーダの上記説明は、多数の2進イベントで構成されたイベントシーケンスを、少なくとも1ビットで構成された情報シーケンスへと処理することに関して述べ、デコーダについては、少なくとも1ビットで構成された情報シーケンスを、多数の2進イベントで構成されたイベントシーケンスへと処理することに関して述べたが、エンコーダ及びデコーダは、当業者に明らかなように、本明細書に説明した教示を利用して、M進性のイベント即ち、各M進イベントは2ビット以上のデータを表わすで構成されたイベントシーケンス及び情報シーケンスに対して演算を行うことができる。<コンピュータシステムの例>0144図17は、本明細書に説明された一つ以上のオペレーションを実行することのできるコンピュータシステムの一例を示すブロック図である。尚、これらのブロック又はブロックのサブセットは、本明細書に説明された技術を実行するように、例えば、セルラー電話のような装置に一体化できる。0145図17を参照すれば、コンピュータシステム1700は、情報を通信するための通信メカニズム即ちバス1711と、情報を処理するためにこのバス1711に接続されたプロセッサ1712とを備えている。このプロセッサ1712は、例えば、Pentium登録商標、PowerPC登録商標、Alpha登録商標等のマイクロプロセッサを含むが、これに限定されない。0146システム1700は、更に、プロセッサ1712によって実行される情報及び命令を記憶するためにバス1711に接続されたランダムアクセスメモリRAM又は他のダイナミック記憶装置1704を備えている。また、このメインメモリ1704は、プロセッサ1712によって命令を実行する間に一時的な変数又は他の中間情報を記憶するために使用されることができる。0147また、コンピュータシステム1700は、プロセッサ1712用のスタティック情報及び命令を記憶するためにバス1711に接続されたリードオンリメモリROM及び/又は他のスタティック記憶装置1706と、磁気ディスク又は光学ディスク及びそれに対応するディスクドライブのようなデータ記憶装置1707とを備えている。このデータ記憶装置1707は、情報及び命令を記憶するためにバス1711に接続される。0148コンピュータシステム1700は、更に、コンピュータのユーザに情報を表示するためにバス1711に接続された陰極線管CRT又は液晶ディスプレイLCDのようなディスプレイ装置1721にも接続される。また、アルファニューメリック及び他のキーを含むアルファニューメリック入力装置1722も、情報及びコマンドの選択をプロセッサ1712へ通信するためにバス1711に接続される。更に別のユーザ入力装置は、マウス、トラックボール、トラックパッド、スタイラス、又はカーソル方向キーのようなカーソル制御器1723であり、これは、方向情報及びコマンド選択をプロセッサ1712と送受すると共に、ディスプレイ1721上のカーソル移動を制御するためにバス1711に接続される。0149バス1711に接続される別の装置は、ハードコピー装置1724である。ハードコピー装置1724は、命令、データ又は他の情報をペーパーやフィルムのような媒体や同様の形式の媒体にプリントするために使用される。更に、スピーカ及び/又はマイクロホンのような音声記録及び再生装置も、コンピュータシステム1700と音声インターフェイスするようにバス1711に任意に接続できる。バス1711に接続できる別の装置は、電話、ハンドヘルド式の手のひら装置又は他の装置と通信するための有線/無線通信装置1725である。0150尚、システム1700のいずれか又は全部の要素及びそれに関連したハードウェアを本発明に適用できる。しかしながら、当該コンピュータシステムの他の構成は、上記デバイスの幾つか又は全てを含められることは明らかであろう。0151当業者であれば、以上の説明を読んだ後、本発明の多数の変更や修正が明らかとなるであろうが、図示して説明した特定の実施形態は、本発明を限定するためのものではないことを理解されたい。それ故、種々の実施形態の詳細な説明は、本発明の本質とみなす特徴のみを記載した特許請求の範囲を何ら限定するものではない。"