"1回の符号化のたびに、マッピング単位値を非2値シンボルから1つの2値シンボルに2値化するように構成されたバイナライザと、複数回の符号化を通じて遷移することが可能な確率パラメータを使用して、前記バイナライザからの2値シンボルを1回の符号化のたびに1つ符号化するように構成された算術符号化エンジンと、を備え、前記非2値シンボルからの前記マッピング単位値は、前記確率パラメータに合わせて適応的に可変である、算術エンコーダ。ビデオエンコーダのプロセッサによって実行されて、1回の符号化のたびに、マッピング単位値を非2値シンボルから1つの2値シンボルに2値化するステップと、複数回の符号化を通じて遷移することが可能な確率パラメータを使用して、2値シンボルを1回の符号化のたびに1つ符号化するステップと、を実施させるコンピュータ実行可能ステップを含み、前記マッピング単位値は、前記確率パラメータに合わせて適応的に可変である、算術符号化方法。前記確率パラメータに合わせて適応的に可変のサイズパラメータを使用して、前記マッピング単位値を求めるステップをさらに含む、請求項2に記載の算術符号化方法。前記非2値シンボルの残り値が前記マッピング単位値以下になるまで、1回の符号化のたびに前記非2値シンボルから前記マッピング単位値を反復的に減算するステップをさらに含む、請求項3に記載の算術符号化方法。1回の符号化のたびに前記確率パラメータを更新するステップをさらに含む、請求項2に記載の算術符号化方法。前記確率パラメータに基づいて、前記サイズパラメータを変更する必要があるかどうかを1回ごとに判定するステップをさらに含む、請求項3に記載の算術符号化方法。前記確率パラメータが低い場合に前記サイズパラメータを変更することにより前記マッピング単位値を増大させるステップをさらに含む、請求項3に記載の算術符号化方法。前記確率パラメータを調整して前記マッピング単位値の増大を補償するステップをさらに含む、請求項7に記載の算術符号化方法。前記確率パラメータが高い場合に前記サイズパラメータを変更して前記マッピング単位値を減少させるステップをさらに含む、請求項3に記載の算術符号化方法。前記確率パラメータを調整して前記マッピング単位値の減少を補償するステップをさらに含む、請求項9に記載の算術符号化方法。前記非2値シンボルの前記残り値が前記マッピング単位値以下になった時に、前記サイズパラメータを使用して前記非2値シンボルの前記残り値をサフィックス2値シンボルに変換し、前記サフィックス2値シンボルを即座に符号化するステップをさらに含む、請求項4に記載の算術符号化方法。複数回の復号を通じて遷移することが可能な確率パラメータを使用して、算術符号語を1回の復号のたびに1つ復号して2値シンボルにするように構成された算術復号エンジンと、前記2値シンボルを1回の復号のたびに1つ逆2値化して、非2値シンボルを再構築するために合計されるマッピング単位値にするように構成されたデバイナライザと、を備え、前記マッピング単位値は、前記確率パラメータに合わせて適応的に可変である、算術デコーダ。ビデオデコーダのプロセッサによって実行されて、複数回の復号を通じて遷移することが可能な確率パラメータを使用して、算術符号語を1回の復号のたびに1つ復号して2値シンボルにするステップと、前記2値シンボルを1回の復号のたびに1つ逆2値化して、非2値シンボルを再構築するために合計されるマッピング単位値にするステップと、を実施させるコンピュータ実行可能ステップを含み、前記マッピング単位値は、前記確率パラメータに合わせて適応的に可変である、算術復号方法。前記確率パラメータに合わせて適応的に可変のサイズパラメータを使用して、前記マッピング単位値を求めるステップをさらに含む、請求項13に記載の算術復号方法。1回の符号化のたびに前記確率パラメータを更新するステップをさらに含む、請求項13に記載の算術復号方法。前記確率パラメータに基づいて、1回の復号のたびに、前記サイズパラメータを変更する必要があるかどうかを判定するステップをさらに含む、請求項14に記載の算術復号方法。前記確率パラメータが低い場合に前記サイズパラメータを変更することにより前記マッピング単位値を増大させるステップをさらに含む、請求項14に記載の算術復号方法。前記確率パラメータを調整して前記マッピング単位値の増大を補償するステップをさらに含む、請求項17に記載の算術復号方法。前記確率パラメータが高い場合に前記サイズパラメータを変更して前記マッピング単位値を減少させるステップをさらに含む、請求項14に記載の算術復号方法。前記確率パラメータを調整して前記マッピング単位値の減少を補償するステップをさらに含む、請求項19に記載の算術復号方法。前記算術復号エンジンからの2値シンボルが、分離点となる2値シンボルである時に、残りの算術符号語を復号してサフィックスの2値シンボルにするステップをさらに含む、請求項13に記載の算術復号方法。前記サフィックス2値シンボルを逆2値化して、前記非2値シンボルを再構築するために加算される値にするステップをさらに含む、請求項21に記載の算術復号方法。0039図1は、本発明を実施することが可能なコンピュータ100の例示的ハードウェアアーキテクチャを示す。図1に示すハードウェアアーキテクチャは、本発明の実施形態を実施するビデオエンコーダ及びビデオデコーダの両方に共通でよいことに留意されたい。コンピュータ100は、ローカルインタフェース107を介して通信可能に結合された、プロセッサ101、メモリ102、記憶装置105、及び入力及び/又は出力I/O装置106若しくは周辺装置を含む。ローカルインタフェース105は当技術分野で知られるように、これらに限定されないが、例えば1つ若しくは複数のバス又は他の有線若しくは無線接続とすることができる。0040プロセッサ101は、ソフトウェア、特にメモリ102に記憶されたソフトウェアを実行するハードウェア装置である。プロセッサ101は、任意の特別注文若しくは市販のプロセッサ、中央演算処理装置CPU、コンピュータ100に関連する数個のプロセッサのうちの補助プロセッサ、半導体を利用したマイクロプロセッサマイクロチップ若しくはチップセットの形態、又は一般にソフトウェア命令を実行する任意の装置とすることができる。0041メモリ102は、コンピュータ可読媒体からなり、コンピュータ可読媒体は、揮発性のメモリ要素例えばランダムアクセスメモリDRAM、SRAM、SDRAM等のRAM、及び不揮発性のメモリ要素例えばROM、ハードドライブ、テープ、CDROM等のいずれか1つ又は組み合わせを含むことができる。さらに、メモリ102には、電子、磁気、光学、及び/又は他の種の記憶媒体を採用することができる。コンピュータ可読媒体は、命令実行システム、装置、又はデバイスにより使用されるプログラム、又はそれらシステム、装置、デバイスに関連するプログラムを記憶、通信、伝搬、又は搬送することが可能な任意の手段とすることができる。メモリ102は分散アーキテクチャを有することができ、その場合、各種構成要素は互いから遠隔に位置するが、プロセッサ101からアクセスすることができることを留意されたい。0042メモリ102内のソフトウェア103は1つ又は複数の別個のプログラムを含むことができ、各プログラムは、下記で説明するコンピュータ100の論理的機能を実装する実行可能命令の順序付けられたリストを含んでいる。図1の例では、メモリ102のソフトウェア103は、本発明によるコンピュータ100の映像符号化及び映像復号機能を定義する。また、これは必須ではないが、メモリ102がオペレーティングシステムO/S104を保持することが可能である。オペレーティングシステム104は基本的にコンピュータプログラムの実行を制御し、スケジューリング、入出力制御、ファイル及びデータの管理、メモリ管理、並びに通信の制御とそれに関連するサービスを提供する。0043コンピュータ100の記憶装置105は、固定記憶装置又は携帯可能記憶装置を含む、多くの異なる種類の記憶装置の1つとすることができる。一例として、記憶装置105は、磁気テープ、ディスク、フラッシュメモリ、揮発性メモリ、又は別種の記憶装置とすることができる。また、記憶装置105は、セキュアデジタルメモリカードや他の取り外し可能記憶装置105とすることができる。0044I/O装置106は、これらに限定されないが、タッチスクリーン、キーボード、マウス、スキャナ、マイクロフォン、又は他の入力装置等の入力装置を含むことができる。さらに、I/O装置106は出力装置、これらに限定されないが、例えばディスプレイ、又は他の出力装置も含むことができる。I/O装置106は、入力と出力の両方を介して通信する装置、例えば、これらに限定されないが、変調器/復調器別の装置、システム、又はネットワークにアクセスするためのモデム、無線周波RF、ワイヤレス、又は他のトランシーバ、電話インタフェース、ブリッジ、ルータ、又は入力と出力の両方として機能する他の装置をさらに含むことができる。0045当業者にはよく知られるように、映像の圧縮は、映像シーケンス中の冗長な情報を取り除くことによって実現される。多くの異なる映像符号化標準が存在しており、その例にはMPEG-1、MPEG-2、MPEG-4、H.261、H.263、及びH.264/AVCが含まれる。本発明は、特定の映像符号化標準の適用に限定される意図はないことに留意されたい。ただし、最新の映像符号化標準であるため、以下ではH.264/AVC標準の例を使用して本発明を説明する。H.264/AVCでは、映像の各フレーム又はピクチャを数個のスライスに分割することができる。そしてスライスを、マクロブロックと呼ばれる16×16画素のブロックに分割し、そのマクロブロックをさらに、8×16、16×8、8×8、4×8、8×4、そして4×4までのブロックに分割することができる。0046図2に、本発明を適用することができるビデオエンコーダの概略図を示す。図に示すブロックは、プロセッサ101がメモリ102のソフトウェア103を実行することによって実現される機能モジュールを表す。ビデオフレーム200のピクチャがビデオプリコーダ201に供給される。ビデオプリコーダは、ピクチャ200をマクロブロック200A単位で処理する。各マクロブロックは、ピクチャ200の数個のピクチャサンプルを含んでいる。各マクロブロックに対して変換係数への変換が行われ、次いで、変換係数レベルへの量子化が行われる。さらに、符号化ステップを直接画素データに行うのではなく、画素データと予測画素値との差に行うために、フレーム内予測又は動き保証を使用し、それにより、より容易に圧縮できる小さな値を実現する。0047各スライスに対して、プリコーダ201はいくつかの構文要素を生成し、その構文要素が、個々のスライスのマクロブロックを符号化したバージョンを形成する。構文要素中のすべての残余データ要素変換係数レベルや、スキップされた変換係数レベルを示す重要度マップ等、変換係数の符号化に関連するを残余データ構文要素と呼ぶ。この残余データ構文要素の他に、プリコーダ201によって生成される構文要素は、各マクロブロックがどのように符号化され、どのように復号すべきかについての制御情報をそれぞれ含む制御情報構文要素を含んでいる。すなわち、構文要素は2つのカテゴリに分けることができる。第1のカテゴリでは、制御情報構文要素は、例えば、マクロブロックの種類、部分マクロブロックの種類に関係する要素、空間タイプと時間タイプ両方の予測モードについての情報、スライス単位及びマクロブロック単位の制御情報を含む。第2のカテゴリでは、量子化された変換係数のブロック内のすべての有意係数の位置を示す重要度マップや、有意係数の値量子化ステップに対応するレベルを単位として示される等のすべての残余データ要素が組み合わせられ、残余データ構文要素になる。0048プリコーダ201は構文要素をエントロピーコーダ202に出力する。エントロピーコーダ202は、CABACエンコーダであり、下記でより詳細に説明する。エントロピーコーダ202は、各スライスの算術符号語を生成する。スライスの算術符号語を生成する際、エントロピーコーダ202は、映像信号のビットストリーム中の構文要素のデータ値間の統計的依存関係を利用する。エントロピーコーダ202は、ピクチャ200のスライスの算術符号語を図3に示すエントロピーデコーダに出力する。0049図3は、本発明を適用することが可能なビデオデコーダの概略図である。上記と同様に、図3に示すブロックは、プロセッサ101がメモリ102のソフトウェア103を実行することによって実現される機能モジュールを表す。エントロピーデコーダ301は、CABACデコーダであり、下記でより詳細に説明するが、算術符号語を受け取り、符号語を復号して構文要素に戻す。プリコードデコーダ302は、マクロブロック単位、次いでスライス単位でピクチャ300内の画素のピクチャサンプルを取得するために構文要素を使用する。0050図4は、構文要素を符号化して算術符号語にするエントロピーコーダ202の機能モジュールを示す。これらの機能モジュールは、プロセッサ101がメモリ102のソフトウェア103を実行することによって実現される。シンボルのCABAC符号化処理は、3段階の処理、すなわち、2値化、コンテクストのモデル化、及び2値算術符号化、からなる。第1段階の処理を行うために、エントロピーコーダ202はバイナライザ401を備える。バイナライザ401の入力は、スイッチ403を介して入力402に接続される。入力402は、エントロピーコーダ202で符号化する構文要素を提供する。スイッチ403は、入力402に到着する構文要素を、バイナライザ401又は2値化出力404のいずれかに渡すことができ、それによりバイナライザ401を迂回バイパスする。スイッチ403は、2値でない構文要素はバイナライザ401に渡すように機能する。2値化形態にない構文要素の例は、動きベクトル差及び変換係数レベルである。スイッチ403はまた、構文要素がすでに2値化形態である場合は、入力402からの構文要素を2値化出力404に直接渡すように機能する。0051バイナライザ401は、非2値の構文要素をビン列に対応付ける。ビンbinとは、非2値をビット列に対応付ける2値化マッピングを定義する符号化ツリーのノードにおいて、符号化ツリーの根ノードから、2値化しようとする非2値構文要素の非2値に対応する符号化ツリーの葉ノードに遷移する際に行わなければならない二分決定を意味する。したがって、ビン列は、ビン又は二分決定のシーケンスであり、各ビットが二分決定の結果である同数のビットを有する符号語に対応する。ビン列は、非常に効率的な2値算術符号化を可能にするように、構文要素の確率分布に合わせて適合される。0052バイナライザ401から出力されたビン列は、直接2値化出力404に渡してはならず、バイナライザ401から出力されるビン列と、すでに2値化された構文要素とを併合するために、バイナライザ401の出力と出力404との間に配置されたビンループオーバー手段405によって出力404に制御可能に渡され、それにより、バイナライザ401を迂回して出力404で単一のビットストリームにする。0053第2段階の処理を行うために、エントロピーコーダ202は、コンテクストモデラー406とスイッチ407を備える。コンテクストモデラー406の入力は、スイッチ407を介して2値化出力404に接続される。コンテクストモデラー406の出力は、通常符号化エンジン408に接続される。スイッチ407は、ビンシーケンスのビット又はビンをコンテクストモデラー406又はバイパス符号化エンジン409のいずれかに渡すように機能し、それによりコンテクストモデラー406を迂回する。0054到着する各ビンについて、コンテクストモデラー406はコンテクストモデルを選択し、コンテクストモデルは、ビン列中のビンの値間の統計的依存関係をモデル化する確率分布を近似し、ビン列中での個々のビンの出現頻度を推定するために通常符号化エンジン408で使用される。各ビンには数個のコンテクストが割り当てられ、所与のビンを符号化するために選択されるコンテクストは、処理中の構文要素によって記述される現在のマクロブロックの前後にあるマクロブロックの特性に応じて決まる。コンテクストモデルへのビンの割り当ては、同じコンテクストモデルに属するビンの実際の確率分布が同一又は類似した振る舞いを示すようになされ、特定のコンテクストモデルによるビン値の確率推定が、そのコンテクストモデルに割り当てられたすべてのビンの実際の確率の良好な近似となるようにする。0055ビン値の確率分布は符号化の開始時には未知であり、異なる映像シーケンスごとに異なることに留意されたい。その結果、CABACに高い符号化効率をもたらす特性の1つは、符号化対象のビンの確率を記憶するコンテクストが適応的であることである。具体的には、符号化中に、ビン確率の正確な推定を実現するためにコンテクストが更新される。コンテクストの更新は、先に符号化されたビンの値に応じて行われる。同じビン又は同じ構文要素はビン内で数回出現するが、先に符号化されたビンに応じて、出現のたびに異なるコンテクストモデルに割り当てることができる。2値算術符号化に使用される確率推定が符号化の効率を決定するので、符号化中に確率推定が常に実際の確率を非常に有効に近似するように、ビン値間の統計的依存関係を高度に活用する適切なコンテクストモデルを持つことが重要である。0056入力されたビンにコンテクストモデルを割り当てると、コンテクストモデラー406は、そのビンを、ビンが割り当てられたコンテクストモデルと共に通常符号化エンジン408に渡す。通常符号化エンジン408は、第3段階の処理を行い、コンテクストモデラー406から渡されたビンの値を、同じくコンテクストモデラー406から渡されたコンテクストモデルを使用して算術符号化する。さらに、通常符号化エンジン408は、コンテクストモデルを更新するためのビン値を、フィードバック線410を通じてコンテクストモデラー406に渡す。0057通常符号化エンジン408は、コンテクストモデラー406からビンを受け取るたびに、同じくコンテクストモデラー406から受け取られるコンテクストモデルに従って、ビン値の出現確率を推定する。そして、通常符号化エンジン408は、その確率の推定を使用してビンを算術符号化する。また、ビンを符号化するたびに、通常符号化エンジン408は、先に符号化された少なくとも1つのビンの値に基づいて、次のビンの符号化のための確率推定を適応的に更新する。一実施形態では、通常符号化エンジン408は、先に符号化した少なくとも1つのビンの値に基づいて、受け取ったコンテクストモデルに従って確率推定を計算する。0058別の実施形態では、通常符号化エンジン408は、H.264/AVCで定義されるように有限状態機械であり、コンテクストモデルに関連するテーブルを有する。各コンテクストモデルテーブルには確率推定が記憶されている。有限状態機械であるため、通常符号化エンジン408は確率推定の計算は行わない。代わりに、通常符号化エンジン408は、すべての確率推定を事前定義された定数としてコンテクストモデルテーブルに有する。各コンテクストモデルテーブルに記憶された確率推定は、選択的に確率索引で識別される。したがって、コンテクストモデラー406からビン及びコンテクストモデルを受け取るたびに、通常符号化エンジン408は、まず、受け取ったコンテクストモデルに関連付けられたテーブルを選択する。そして、通常符号化エンジン408は、そのテーブルを探索し、確率索引を使用して、ビンを符号化するために必要な確率推定をテーブルから見つける。また、通常符号化エンジン408は、構文要素又はビンがそこから導出されたピクチャ又はビデオフレームの特性又は属性に合わせて確率推定を適応させるために、確率索引を更新することで確率推定を更新する。確率索引の更新も、同様に、先に符号化された少なくとも1つのビンに基づく。0059バイパス符号化エンジン409は、静的な所定の確率推定を使用してビン列を算術符号化するものである。バイナライザ401から出力されるビン列中のビンの一部は、確率が等しい分布を示す。これは、1つのビン列中のビンに対応するビットが半々の確率で1又は0であることを意味する。これらのビンがバイパス符号化エンジン409に供給され、確率が等しい確率推定を使用して算術符号化される。確率が等しい確率推定は一定であり、したがって、コンテクストモデルの選択と確率推定の更新に伴う計算オーバーヘッドを解消する。0060通常符号化エンジン408及びバイパス符号化エンジン409から出力される符号化ビットはスイッチ412により出力411で併合されて1つのビットストリームとなる。このビットストリームは、入力端子402に入力された構文要素の2値算術符号語に相当する。通常符号化エンジン408及びバイパス符号化409は、適応的又は静的な確率推定に基づく算術符号化を行うために協働する。0061図5は、算術符号語を復号して構文要素に戻すエントロピーデコーダ301の機能モジュールを示す。これらのモジュールは、プロセッサ101がメモリ102のソフトウェア103を実行することによって実現される。図5で、算術符号語は、スイッチ503の動作により、通常復号エンジン501又はバイパス復号エンジン502のいずれかで受け取られる。スイッチ503は、通常符号化エンジン408で符号化された算術符号語を選択的に通常復号エンジン501に渡し、バイパス符号化エンジン409で符号化された算術符号語をバイパス復号エンジン502に渡すように機能する。通常復号エンジン501は、コンテクストモデラー504から提供されるコンテクストモデルに従った適応確率推定を使用して、受け取った符号語を復号して復号ビンにする。バイパス復号エンジン502は、確率が等しい静的確率推定を使用して、受け取った符号語を復号して復号ビンにする。復号されたビンは、スイッチ506の動作により、逆2値化のためにデバイナライザdebinarizer505に進むか、又はデバイナライザ505を迂回する。デバイナライザ505は、復号されたビンを逆2値化して構文要素にする。構文要素は、通常復号エンジン501に提供されるコンテクストモデルの更新のために、コンテクストモデラー504にフィードバックされる。符号語を復号するたびに、通常復号エンジン501は、先に復号された少なくとも1つのビンに基づいて確率推定を更新する。0062一実施形態では、通常復号エンジン501は、先に復号された少なくとも1つのビンに基づいて、受け取ったコンテクストモデルに従って確率推定を計算する。別の実施形態では、通常復号エンジン501は、H.264/AVCで定義されるように有限状態機械であり、コンテクストモデルに関連付けられたテーブルを有する。各コンテクストモデルテーブルには確率推定が記憶されている。有限状態機械であるため、通常復号エンジン501は確率推定の計算は行わない。代わりに、通常復号エンジン501は、すべての確率推定を事前定義された定数としてコンテクストモデルテーブルに有する。各コンテクストモデルテーブルに記憶された確率推定は、確率索引で選択的に識別される。したがって、算術符号語及びコンテクストモデルを受け取るたびに、通常復号エンジン501は、まず、受け取ったコンテクストモデルに関連付けられたテーブルを選択する。そして、通常復号エンジンは、テーブルを探索し、確率索引を使用して、符号語の符号化に必要な確率推定をテーブルから見つける。また、通常復号エンジン501は、確率索引を更新することにより、確率推定を更新する。確率索引の更新は、先に復号された少なくとも1つのビンに基づく。0063次いで、エントロピーコーダ202及びエントロピーデコーダ301の詳細な動作を説明するために、添付のフローチャートに、CABAC符号化及び復号用のエントロピーコーダ202及びエントロピーデコーダ301によって行われるソフトウェア処理を示す。添付のフローチャートに記載される符号化及び復号処理は、プロセッサ101がメモリ102のソフトウェア103を実行することによって実現される図4及び図5に示すエントロピーコーダ202及びエントロピーデコーダ301の機能モジュールが共同して行うことを理解されたい。また、以下の説明では、まずテーブルを使用せずに確率を計算する実施形態を使用し、次いで、テーブルを使用して確率を得る有限状態機械を採用した別の実施形態を使用して本発明を説明することに留意されたい。0064以下の説明では、2値シンボルは、A又はBいずれかの値をとる。これらの値は、単に、2値シンボルがとる2つの可能な値を区別するために使用する。また、2値シンボルを算術符号化する処理では確率推定pが使用され、確率推定pは、シンボルBに関連付けられた確率を表す。或いは、確率推定pはq=1-pに置き換えてもよく、pの更新もそれに応じて変更される。0065図6は、エントロピーコーダ202で実施される例示的な初期化処理を示すフローチャートである。初期化処理では、ステップ601で確率推定pが初期確率推定p0に初期化される。初期確率推定p0は、予め決められた値である。一実施形態では、初期確率推定p0は、0より大きく、1より小さい確率の固定小数点表現である。ステップ602で、サフィックスsuffixの大きさsも初期サフィックスの大きさs0に初期化する。サフィックスの大きさsは、符号化するビン列の長さを決定し、本発明では、切捨て単項2値化処理と同様の処理で導出される。サフィックスの大きさsが大きくなるとビン列の長さが短くなり、その逆も同様である。一実施形態では、初期サフィックスの大きさs0は0ゼロである。0066ステップ603で、確率推定pを所定の閾値Thlowと比較する。一実施形態では、閾値Thlowは、値1/8の固定小数点表現に相当する。確率推定pが閾値Thlow以上である場合、初期化処理は終了する。確率推定pが閾値Thlowより小さい場合、処理は、ステップ604に進み、2×p-pの2乗を確率推定pに代入する。そして、ステップ605で、サフィックスの大きさsを1増分する。その後流れは比較ステップステップ603に戻る。ステップ604及び605は、確率推定pが閾値Thlow以上になるまで繰り返される。図6に示す初期化処理のためのC言語式の擬似コードを下記に示す。initsuffix160067本発明では、確率推定pの値に基づいてサフィックスの大きさsを適応的に変更する。確率推定pが小さい時は、サフィックスの大きさsを増して符号化するビン列の長さを短くすることが望ましい。CABACでは、部分範囲R0は範囲レジスタの値と確率推定pの積であるため、確率推定pが小さい場合は部分範囲R0が小さくなる。また、CABACでは部分範囲R0を求める処理は反復的であり、符号化するビン列中のビンの数に等しい回数繰り返され、部分範囲R0は、ビン列のビンに符号化が進行するにつれて反復的に小さくなる。したがって、確率推定pが小さい場合は、反復的に小さくなっていく部分範囲R0が、有限精度の制約下では符号化エンジンで正確に表現されなくなり、結果として符号化の非効率性を増大させ、計算量を増加させる。本発明では、確率推定pが小さい場合は、サフィックスの大きさsを大きくするように変更して、符号化するビン列を短くし、それにより、部分範囲R0の反復的な減少の回数を減らす。したがって、サフィックスの大きさsが増加すると、結果として算術符号化の効率が向上し、その複雑度が低減することが予想される。0068しかし、サフィックスの大きさsを増分すると、確率推定pの調整が必要となる。サフィックスの大きさsを1だけ増分することにより、確率推定pで別個に符号化されるはずのビン列中の2つの2値シンボル又はビンが共に符号化される。下記で述べるように、本発明によるシンボルの2値化では、一連の2値シンボルAが得られ、これは、切捨て単項2値化処理と同様の処理で導出される。また、上記のように、確率推定pは、シンボルBに関連付けられた確率を表すように定義される。したがって、それぞれが確率推定1-pに関連付けられた2つの2値シンボルAを共に符号化するために使用される調整後の確率推定1-p’は、1-p’=1-p2又はp’=2p-p2となる。0069別の実施形態では、初期確率推定p0及び初期サフィックスの大きさs0は、ステップ603、604及び605の補正ループを不要にするように選択することができる。別の実施形態では、p及びsの値をユーザが選択できるようにし、エンコーダからデコーダに送信される。さらに別の実施形態では、p及びsの値は、量子化ステップ又はフレームサイズの関数とすることができる。量子化の刻みを小さくすると変換係数が大きくなり、フレームサイズを大きくすると動きベクトル値が大きくなる。0070図7は、エントロピーコーダ202によって行われる、本発明の一実施形態による符号化処理を示すフローチャートである。このフローチャートに示す符号化処理は整数シンボルNを符号化することを想定し、シンボルNは符号付きである場合も、符号なしの場合もある。整数シンボルNは、画像コーデック、映像コーデック、若しくは音声コーデックの変換係数の値、映像コーデック中の動きベクトル差、又は他の類似の整数データを表すことができる。図7に示すフローチャートでは、ステップ701でNの値を0ゼロと比較する。Nの値が0に等しい場合は、ステップ702で確率推定pを使用して2値シンボルBを符号化し、ステップ702で確率推定pを更新し、その後流れが終了する。Nの値が0に等しくない場合は、ステップ704で確率推定pを使用して2値シンボルAを符号化し、ステップ705で確率推定pを更新する。0071図8は、図7のステップ703及び705で行われる確率推定pの更新処理を示すフローチャートである。図8のステップ801で、前回符号化されたシンボルがシンボルAであるかどうかを判定する。最後の符号化シンボルがシンボルAである場合、ステップ802で確率推定pの現在の値に定数aの値を乗算する。最後の符号化シンボルがシンボルAでない場合は、ステップ803で確率推定pの現在の値に定数aの値を乗算し、1-定数aの値を足す。定数aの値は、0より大きく、1より小さい。定数aの値は、確率推定pがどれほど迅速に基礎となるソースの確率分布に合わせて適応されるかを決定する。定数aの値が小さいほど、適応が速くなる。一実施形態では、定数aは、1-2-mで定義することができ、mは、更新処理で乗算の算術演算を回避するように正の整数から選択される。mは、5などの所定の値とするか、又はエンコーダからデコーダに送信することができる。確率推定pを更新するためのC言語式の擬似コードを下記に示す。updatepcontextlossrateelsepcontextlossrate0072図7に戻り、ステップ702又は704で符号化されたシンボルA又はBは、符号化されたシンボルが非ゼロの整数であるか、又はゼロに等しいかをデコーダに知らせるヘッダ情報として機能する。ステップ705の後、処理はステップ706に進み、Nの絶対値を符号化する。Nの絶対値を符号化する処理については、図9を参照して下記で詳細に説明する。引き続き図7で、シンボルNが符号付き整数の場合は、ステップ707で符号値を符号化する。符号値は、負のシンボルの場合は1の値を有する1ビットの符号シンボルで表される。1ビットの符号シンボルは、図4に示すバイパス符号化エンジン409を通じて算術符号化される。0073図9は、図7のステップ706の処理を詳細に示すフローチャートであり、このステップではシンボルNの絶対値が符号化される。図9のステップ901で、値Nが2のサフィックスの大きさs乗と比較される。演算子<<は、ビット単位の左シフトを要求し、1<<sは、2のサフィックスの大きさs乗の数学演算を要求する。シンボルNの絶対値が2のサフィックスの大きさs乗より大きい場合、流れはステップ902に進み、確率推定pを使用して2値シンボルAを符号化する。そして、ステップ903でNの値から2のサフィックスの大きさs乗を引く。2値化は、非2値シンボルを2値シンボルの列にマッピングする処理である。ステップ903は、シンボルNの値から取り出された1<<sの値が1つの2値シンボル又はビンにマッピングされることを示唆する。したがって、1<<sの値は、1つのビン当たりのマッピング値又はマッピング単位値を表す。0074次いで、ステップ904で、図8に示す上記処理を通じて確率推定pを更新する。ステップ905でサフィックスの大きさsも更新する。その後、流れはステップ901に戻り、値Nを2のサフィックスの大きさs乗、すなわちマッピング単位値と比較する。したがって、ステップ901、902、903、904及び905の処理ループは、値Nがマッピング単位値以下になるまで繰り返される。本発明では、符号化及び2値化は、1回の符号化ごとに並行して行われる。符号化のたびに、ステップ903でマッピング単位値がシンボルNの値から反復的に取り出され、1つのビンにマッピングされ、ステップ902でそのビンを符号化する。0075図10は、図9に示すステップ902の符号化処理を詳細に説明するフローチャートである。ステップ1001で、範囲レジスタの現在の値Rに確率推定pを乗算することにより2値シンボルBの部分範囲値R0を計算する。そして、ステップ1002で符号化対象の2値シンボルがシンボルBであるかどうかを判定する。符号化対象の2値シンボルがシンボルBである場合は、ステップ1003で範囲レジスタを部分範囲値R0に設定する。符号化対象の2値シンボルがシンボルAである場合は、ステップ1004で、範囲レジスタの現在の値Rから部分範囲R0を減算する。また、ステップ1004で、オフセットレジスタの現在の値Lに部分範囲値R0を加算する。図9のステップ901では2値シンボルAを符号化するため、図10のステップ1002で行われる判定はステップ1004に至ることに留意されたい。ステップ1003又は1004で範囲レジスタ及びオフセットレジスタを更新した後、ステップ1005で再正規化を行う。当業者は再正規化処理について知っていると思われるため、この処理については本明細書ではこれ以上詳細には説明しない。0076図11は、サフィックスの大きさsが更新される図9のステップ905で行われる処理を詳細に説明するフローチャートである。図11に示すフローチャートは、図9のステップ902で2値シンボルAが符号化された後に呼び出される。ステップ1101で、確率推定pを、図6に示す初期化処理で使用される閾値Thlowと比較する。閾値Thlowとは異なる値をステップ1101の比較ステップで使用してもよい。確率推定pが閾値Thlow以上の場合、処理は終了する。確率推定pが閾値Thlowより小さい場合は、ステップ1102で確率推定pを調整し、ステップ1103でサフィックスの大きさsを1増分する。サフィックスsが増分されると、1<<sのマッピング単位値が増し、シンボルNは、より少ない数のビンにマッピングされる。図9のステップ903を参照されたい。すなわち、ステップ1103でサフィックスsが増分されると、2値化の結果得られるビン列が短くなる。0077図6に示す初期化処理で述べたように、確率推定pが小さい場合は、サフィックスの大きさsを増して算術符号化の効率を改善し、その複雑度を低減させることが望ましい。確率推定pは、サフィックスの大きさsの増分のために調整する必要がある。ただし、図6のステップ604で確率推定pに行われる調整処理と異なり、ステップ1102で行われる調整処理は、乗算の演算を回避するために簡略化されている。具体的には、ステップ1102では、2×p-定数kを確率推定pに代入する。定数kの値は、Thlow2の値に近似するように選択する。この簡略化は、ステップ1101で確率推定pが閾値Thlowより小さいと判定された時に確率推定pが閾値Thlowに近くなることに基づく。一実施形態では、閾値Thlow及び定数kは、それぞれ1/8や1/64などの16ビットの固定小数点数を用いて表現される。0078図9に戻り、ステップ901でシンボルNの値が2のサフィックスの大きさs乗より大きくないと判定された場合は、ステップ906で確率推定pを使用して2値シンボルBを符号化する。2値シンボルBは、図10に示す符号化処理を通じて符号化される。符号化された2値シンボルBは、ビン列中でプレフィックスとサフィックスを分離するための分離ビットとして機能する。次いで処理はステップ907に進み、sビットを使用してN-1の値を2値化してサフィックスを表すビン列にし、それを符号化する。より具体的には、ステップ907では、長さSの固定長符号を使用してN-1の値を2値化する。サフィックスを生成するためのC言語型の擬似コードを以下に示す。whileputs0x010079次いで、生成されたサフィックスを図4のバイパス符号化エンジン212で符号化する。サフィックスの大きさsが0ゼロの場合は、値の符号化はない。この段階で、シンボルNの最大値は2のサフィックスの大きさs乗であり、シンボルNの最小値は1であるので、シンボルNの値を正確に符号化するには5ビットで足りる。次いで、図8に示す処理を通じて、ステップ908で確率推定pを更新する。0080図12は、図7のステップ707及び図9のステップ907で行われる迂回符号化の処理を示すフローチャートである。図12のステップ1201で、オフセットレジスタの現在の値について値1をビット単位で左シフトし、オフセットレジスタに代入する。次いで、ステップ1202で、符号化対象の2値シンボルがシンボルBであるかどうかを判定する。符号化対象の2値シンボルがシンボルBである場合は、流れはステップ1204に進み、再正規化を行う。符号化対象の2値シンボルがシンボルAである場合は、ステップ1203で、オフセットレジスタの現在の値Lに部分範囲値R0を加算する。オフセットレジスタを更新した後、ステップ1204で再正規化を行う。0081図9に戻り、ステップ909で図13に示す処理を通じてサフィックスの大きさsも更新する。図13の処理は、前回符号化された2値シンボルが2値シンボルBである時に呼び出される。0082図13で、ステップ1301で、確率推定pを閾値Thhighと比較し、サフィックスの大きさsを0と比較する。一実施形態では、閾値Thhighは、2×Thlow-k2Thlow-kに設定される。確率推定pが閾値Thhigh以下で、サフィックスの大きさsが0ゼロに等しい場合は、処理は終了する。確率推定pが閾値Thhighより大きく、サフィックスの大きさsが0ゼロより大きい場合は、処理はステップ1302及び1303に進み、サフィックスの大きさsを1減分し、確率推定pをpk/2に調整する。ステップ1302で行われる確率の調整は、図11のステップ1102に示す調整操作の逆であることに留意されたい。サフィックスsを減分すると、1<<sのマッピング単位値が減少し、シンボルNがより多くのビンにマッピングされる。図9のステップ903を参照されたい。すなわち、ステップ1303でサフィックスsが減分されると、2値化の結果得られるビン列が長くなる。0083確率推定pが小さいと符号化の効率が損なわれることは図11で説明した。本発明では、確率推定pが低い場合はサフィックスの大きさsを増分して符号化効率を向上させる。一方、確率推定pが高い場合は、ビンのストリームをより少ないビットで符号化することができ、符号化の効率が向上する。しかし、多数のシンボルを少数のビットに符号化すると、符号化効率は向上するが、デコーダにおける全体的な処理速度は低下する。本発明では、確率推定pが高い場合は、サフィックスの大きさsを減らしてビンストリーム中のビン数を増し、それにより符号化効率を下げる。サフィックスの大きさsを下げると符号化の効率は低下するが、デコーダにおける全体的な処理速度を向上させることが予想される。0084図11及び13に示す処理は組み合わせて図14に示すような単一の処理としてもよいことに留意されたい。図14では、図11及び13で用いる番号と同じ番号でステップを参照する。サフィックスの大きさsを更新するためのC言語型の擬似コードを以下に示す。updatesuffix2pcontext0x400suffixsizeelseif1suffixsizecontext0085次いで、本発明による復号処理を説明する。添付のフローチャートにエントロピーデコーダ301によって行われる復号処理を示す。復号処理では、算術符号語を復号してビン列に戻し、ビン列を逆2値化してシンボルNにする。復号処理は基本的に符号化処理の逆であり、エントロピーエンコーダ202でシンボルNに行われた処理を元に戻すものである。フローチャートに示す復号処理は、図5に示す機能モジュールが共同して実装し、それらの機能モジュールは、上述のように、プロセッサ101がメモリ102のソフトウェア103を実行することによって実現されることに留意されたい。0086図15は、エントロピーデコーダ301によって行われる初期化処理を示すフローチャートである。初期化処理では、ステップ1501で、確率推定pを初期化して初期確率推定p0にする。初期確率推定p0は予め決められた値である。一実施形態では、初期確率推定p0は、0より大きく1より小さい確率の固定小数点表現である。ステップ1502で、サフィックスの大きさsも初期化して初期サフィックスの大きさs0とする。サフィックスの大きさsは、ビン列中のビンの遷移を正確に追跡するためにデコーダ301で使用される。一実施形態では、初期サフィックスの大きさs0は0ゼロである。ステップ1503で、確率推定pを所定の閾値Thlowと比較する。閾値Thlowは、図6に示す閾値と同じ値とするべきである。一実施形態では、閾値Thlowは、値1/8の固定小数点表現に相当する。0087確率推定pが閾値Thlow以上である場合、初期化処理は終了する。確率推定pが閾値Thlowより小さい場合は、処理はステップ1504に進み、2×p-pの2乗を確率推定pに代入する。次いで、ステップ1505でサフィックスの大きさsを1増分する。流れはその後比較ステップステップ1502に戻る。ステップ1504及び1505は、確率推定pが閾値Thlow以上になるまで繰り返される。ステップ1504及び1505に示す動作の原理は、図6で説明したものと同じであり、そのためここでは繰り返さない。0088図16は、エントロピーデコーダ301によって行われる主要な復号処理を示すフローチャートである。ステップ1601で、1番目の算術符号語を復号して、シンボルNの値が0ゼロであるかどうかを判定する。この復号処理は図17に示す。ステップ1602で、図18に示す処理を通じて確率推定pを更新する。次いで、ステップ1603で、1番目の符号語の復号で2値シンボルBが得られたかどうかを判定する。復号で2値シンボルBが得られた場合は、ステップ1604でシンボルNを0ゼロに設定し、処理は終了する。0089図17は、図5に示す算術デコーダ501によって行われる復号処理を示すフローチャートである。ステップ1701で、範囲レジスタの値Rに確率推定pを乗算することにより、部分範囲値R0を計算する。次いで、ステップ1702で、部分範囲値R0を値レジスタの値Vと比較する。部分範囲値R0が値レジスタの値Vより大きい場合は、ステップ1703で範囲レジスタを部分範囲値R0に設定し、ステップ1704で2値シンボルBを放出する。部分範囲値R0が値レジスタの値V以下である場合は、ステップ1705で範囲レジスタから部分範囲値R0を減算し、値レジスタから部分範囲値R0を減算する。次いでステップ1706で2値シンボルAを放出する。流れはステップ1707に進み、再正規化を行う。当業者は再正規化処理を知っていると思われるため、この処理については本明細書ではこれ以上詳細には説明しない。0090図16に戻り、算術符号語の復号で2値シンボルAが得られた場合は、流れはステップ1605に進み、図18に示す処理を通じてシンボルNの絶対値を復号する。次いで、ステップ1606で、図19に示すバイパス復号処理を通じて、符号化された1ビットの符号シンボルを復号する。図19の処理は、図5に示すバイパス復号エンジン502によって行われる。2値シンボル又はビンを復号するためのC言語式の擬似コードを以下に示す。decodesymbol16R0R00isymboldecodesymbolfixediupdatesuffixreturnsymbol0096図23は本発明の効率を示すグラフである。横軸はソースのパラメータpを表す。縦軸は、本発明に係るモデルで生成したビットと、最適モデル又はソースのエントロピーで生成したビットとの比を表す。グラフには2つの曲線を示す。黒塗り四角をつなぐ曲線は、本発明による調整可能なサフィックスの大きさsを使用しない従来モデルで示される性能曲線である。黒塗り三角をつなぐ曲線は、サフィックスの大きさsが1に等しい、本発明を使用したモデルで示される性能曲線である。パラメータpが高い値をとる時は従来モデルが本発明によるモデルより効率的であるのに対し、パラメータpの値が低くなると本発明によるモデルが従来モデルより効率的になることが見て取れる。0097上記のように、図4に示す通常の符号化エンジン408及び図5に示す通常の復号エンジン501は、有限状態機械であってもよい。有限状態機械は、コンテクストモデルに関連するテーブルを有する。各コンテクストモデルテーブルには確率推定が記憶されている。有限状態機械は確率推定を計算しない。代わりに、有限状態機械は、すべての確率推定を事前定義された定数としてコンテクストモデルテーブルに備える。各コンテクストモデルテーブルに記憶された確率推定は、確率の索引で選択的に識別される。上記で説明したフローチャートの処理を以下のように変更すると、有限状態機械によって行われる処理の記述を提供することができる。0098本発明による有限状態機械はpStateIdx及びThStateIdxを使用する。pStateIdxは、コンテクストモデルテーブル中で索引付けされた確率推定の中から確率推定を識別する確率状態索引である。コンテクストモデルテーブルの例示的構造を図24に示し、索引0,1,2...、すなわちpStateIdxの索引値と関連付けて確率推定p0,p1,p2...が記憶されている。0099図6を以下のように変更して、有限状態機械の初期化処理を説明する。ステップ601の初期確率推定p0はppStateIdx0になる。pStateIdx0は、図24に示すようなコンテクストモデルテーブルに記憶された初期確率推定p0を識別する索引に相当する。ステップ603の比較演算p<Thlowは、ppStateIdx<pThlowStateIdxに置き換えられる。ppStateIdxは、pStateIdxの現在の索引値で識別されるコンテクストモデルテーブルに記憶された確率推定である。pThlowStateIdxは、閾値低を表す確率である。pStateIdxとppStateIdxの間、及びThlowStateIdxとpThlowStateIdxの間で、H.264/AVCに定義されるように索引値が大きくなるとppStateIdx及びpThlowStateIdxが小さくなる関係が成立する場合は、ステップ603の比較はpStateIdx>ThlowStateIdxに置き換えることができる。ステップ604におけるp←2p-p×pの更新動作は、pStateIdx←TransIdxpStateIdxに置き換えられる。有限状態機械は、また、図26に示すような遷移テーブルを有し、pStateIdxの調整後の索引値がpStateIdxの現在の索引値と関連付けて記憶される。遷移テーブルは、pStateIdxの現在の値で識別される確率推定pについて、TransIdxdxpStateIdxが、値2p-p×pが記憶されているコンテクストテーブルの位置を識別する調整後の索引を提供するように機能する。0100図7では、ステップ702及び704の確率pを使用する演算を確率ppStateIdxを使用する演算に置き換える。ステップ703及び705のpを更新する動作はpStateIdxの更新に置き換える。0101図8のステップ802のp←a×p及びステップ803のp←a×p1-aの更新動作は、それぞれpStateIdx←pUpdateIdxBpStateIdx及びpStateIdx←pUpdateIdxApStateIdxに置き換える。有限状態機械はまた、図26に示すような更新テーブルを有し、pStateIdxの更新された索引値がpStateIdxの現在の索引値と関連付けて記憶される。更新テーブルは、pStateIdxの現在の値で識別される確率推定pについて、pUpdateIdxApStateIdxが、値p←a×p1-aが記憶されたコンテクストテーブルの位置を識別する更新後の索引を提供し、pUpdateIdxBpStateIdxが、値p←a×pが記憶されたコンテクストテーブルの位置を識別する更新後の索引を提供するように機能する。0102図9では、ステップ902、904、906、及び908の動作を、図7のステップ703、704、704、及び705と同様に変更する。図10では、R0←R×pの演算をR0←R×ppStateIdxに置き換える。0103図11では、ステップ1102のp←2p-kの演算をpStateIdx←TransIdxpStateIdxに置き換えることができる。これは、p←2p-kは2p-p×pの近似であるためである。上記で説明したように、図26に示すような遷移テーブルには、pStateIdxの調整された索引値がpStateIdxの現在の索引値と関連付けて記憶される。ステップ1102の演算をそのように置き換えた場合は、図13のステップ1302のp←pk/2の演算がpStateIdx←TransIdx-1pStateIdxに置き換えられる。TransIdx-1pStateIdxは、TransIdxpStateIdxを行う際のテーブルの参照方向と逆の方向に遷移テーブルを参照することを意味する。ステップ1102のp←2p-kの演算は、pStateIdx←pStateIdx-kStateIdxに置き換えることができ、kStateIdxは、pStateIdxの現在の索引値と、その調整後の索引値との差を表す。ステップ1102の演算をそのように置き換えた場合は、図13のステップ1302のp←pk/2の演算はpStateIdx←pStateIdxkStateIdxに置き換えられる。図13のステップ1301の演算p>Thhighは、pStateIdx<ThhighStateIdxに置き換えられる。pThhighStateIdxは、閾値高を表す確率である。図13のステップ1301の演算p>Thhighは、pStateIdx<ThlowStateIdx-kStateIdxに置き換えることができる。0104図15のステップ1501、1503、及び1504は、図6の対応するステップと同様に変更される。図16のステップ1601及び1602は、図7ステップ702及び703と同様に変更される。図17のステップ1701は、図10のステップ1001と同様に変更される。ステップ1802、1805、及び1808は、図9の対応するステップと同様に変更される。図20は図8と同様に変更される。図21及び22はそれぞれ図11及び13と同様に変更される。0105図9及び18に示すように、上記の実施形態では、2値シンボルを符号化又は復号するたびにサフィックスの大きさsを更新するステップ905及びステップ1806。サフィックスの大きさsの更新頻度はより少なくしてもよい。例えば、サフィックスの大きさsの更新は、個々の整数シンボルNの符号化又は復号中に一度だけ行うのでもよい。0106前述の説明を読むと当業者には本発明の多くの改変及び変更が明らかになると思われるが、例示として図示及び記載される特定の実施形態は制限的と解釈すべきものでないことを理解されたい。したがって、各種実施形態の詳細の参照は、特許請求の範囲を制限するものではなく、特許請求の範囲自体は、本発明に必須と見なされる特徴のみを記載する。"