(57)【要約】【課題】  パイプライン段数の増加に伴う回路規模の増大を抑制しコスト低減に寄与する。【解決手段】  予測された文脈インデックスを出力する文脈インデックス予測器１１、予測された文脈インデックスを用いてビットストリームに復号化処理を行い復号化シンボルを出力するパイプライン式算術符号復号器１２、過去の復号化シンボル、シンタックスエレメント、周囲の情報を与えられ正しい文脈インデックスを生成する文脈インデックス生成器１４、復号化シンボルを用いて２値化テーブルを探索しシンタックスエレメントの値を出力する２値化テーブル探索器１５、正しい文脈インデックスと予測された文脈インデックスとを比較し異なっていた場合予測失敗信号を出力する予測失敗検出器１６を備え、パイプライン式算術符号復号器１２は予測失敗信号が出力されるとこれまでの復号化処理をフラッシュし正しい文脈インデックスを用いて復号化処理を再度行って正しい復号化シンボルを出力する。【選択図】  図１
2006033335.tif 000002
【特許請求の範囲】
【請求項１】
情報が符号化されたビットストリームを与えられて復号化して復号化シンボルを生成し、この復号化シンボルに対応したシンタックスエレメントの値を出力する算術符号復号化装置であって、
前記ビットストリームに含まれる前記情報の種類を示す前記シンタックスエレメントを与えられ、前記ビットストリームの復号化に必要な文脈インデックスを予測し、予測された文脈インデックスを出力する文脈インデックス予測器と、
前記予測された文脈インデックスと、前記ビットストリームとを与えられ、前記予測された文脈インデックスを用いて前記ビットストリームに復号化処理を行い、予測に基づく復号化シンボルを生成して出力する、複数段のパイプラインを有するパイプライン式算術符号復号器と、
前記パイプライン式算術符号復号器から出力された前記復号化シンボルのうち、現時点のものより前に出力された過去の復号化シンボルを与えられて保持する記憶部を含み、この過去の前記復号化シンボルと、さらに前記シンタックスエレメントと、前記ビットストリームの周囲の情報とを与えられ、現時点での復号化に必要な正しい文脈インデックスを生成する文脈インデックス生成器と、
前記シンタックスエレメントを与えられてこのシンタックスエレメントのタイプに対応する予め定められた２値化テーブルを外部から取得し、また前記パイプライン式算術符号復号器から出力された現時点の前記復号化シンボルを与えられ、この復号化シンボルを用いて前記２値化テーブルを探索することで、前記シンタックスエレメントの値を得て出力する２値化テーブル探索器と、
前記文脈インデックス生成器が出力した前記正しい文脈インデックスと、前記文脈インデックス予測器が出力した前記予測された文脈インデックスとを与えられて比較し、両者が異なっていた場合に予測失敗信号を出力する予測失敗検出器とを備え、
前記パイプライン式算術符号復号器は、前記予測失敗信号が出力されると、前記予測された文脈インデックスを用いて行った復号化処理をフラッシュし、前記正しい文脈インデックスを用いて復号化処理を再度行って正しい復号化シンボルを出力することを特徴とする算術符号復号化装置。
【請求項２】
情報が符号化されたビットストリームを与えられて復号化して復号化シンボルを生成し、この復号化シンボルに対応した複数のシンタックスエレメントの値を連続して出力する算術符号復号化装置であって、
前記ビットストリームに含まれる前記情報の種類を示す前記シンタックスエレメントを与えられ、前記ビットストリームの復号化に必要な文脈インデックスを予測し、予測された文脈インデックスを出力する文脈インデックス予測器と、
前記予測された文脈インデックスと、前記ビットストリームとを与えられ、前記予測された文脈インデックスを用いて前記ビットストリームに復号化処理を行い、予測に基づく復号化シンボルを生成して出力する、複数段のパイプラインを有するパイプライン式算術符号復号器と、
前記シンタックスエレメントを与えられて保持し、順次出力する入力バッファと、
前記パイプライン式算術符号復号器から出力された前記復号化シンボルのうち、現時点のものより前に出力された過去の復号化シンボルを与えられて保持する記憶部を含み、この過去の前記復号化シンボルと、さらに前記入力バッファから出力された前記シンタックスエレメントと、前記ビットストリームの周囲の情報とを与えられ、現時点での復号化に必要な正しい文脈インデックスを生成する文脈インデックス生成器と、
前記入力バッファから出力された前記シンタックスエレメントのタイプに対応する予め定められた２値化テーブルを外部から取得し、また前記パイプライン式算術符号復号器から出力された現時点の前記復号化シンボルを与えられ、この復号化シンボルを用いて前記２値化テーブルを探索することで、複数の前記シンタックスエレメントのそれぞれの値を得て順次出力する２値化テーブル探索器と、
前記２値化テーブル探索器から出力された前記シンタックスエレメントの値を与えられて保持し、出力する出力バッファと、
前記文脈インデックス生成器が出力した前記正しい文脈インデックスと、前記文脈インデックス予測器が出力した前記予測された文脈インデックスとを与えられて比較し、両者が異なっていた場合に予測失敗信号を出力する予測失敗検出器とを備え、
前記パイプライン式算術符号復号器は、前記予測失敗信号が出力されると、前記予測された文脈インデックスを用いて行った復号化処理をフラッシュし、前記正しい文脈インデックスを用いて復号化処理を再度行って正しい復号化シンボルを出力することを特徴とする算術符号復号化装置。
【請求項３】
前記文脈インデックス予測器は、１サイクル前に出力した文脈インデックスと今回予測する文脈インデックスとの対応関係を示したテーブルを与えられ、このテーブルに基づいて前記文脈インデックスを予測して出力することを特徴とする請求項１又は２記載の算術符号復号化装置。
【請求項４】
前記文脈インデックス予測器は、前記シンタックスエレメントと、前記パイプライン式算術符号復号器から出力された前記復号化シンボルの順番を示す復号化シンボル番号と、今回予測する文脈インデックスとの対応関係を示したテーブルを与えられ、このテーブルに基づいて前記文脈インデックスを予測して出力することを特徴とする請求項１又は２記載の算術符号復号化装置。
【請求項５】
情報が符号化されたビットストリームを与えられて復号化して復号化シンボルを生成し、この復号化シンボルに対応したシンタックスエレメントの値を出力する算術符号復号化方法であって、
文脈インデックス予測器、パイプライン式算術符号復号器、文脈インデックス生成器、２値化テーブル探索器、予測失敗検出器を有する復号化装置を用いて、
前記文脈インデックス予測器により、前記ビットストリームに含まれる前記情報の種類を示す前記シンタックスエレメントを与えられ、前記ビットストリームの復号化に必要な文脈インデックスを予測し、予測された文脈インデックスを生成するステップと、
前記パイプライン式算術符号復号器により、前記予測された文脈インデックスと、前記ビットストリームとを与えられ、前記予測された文脈インデックスを用いて前記ビットストリームに復号化処理を行い、予測に基づく復号化シンボルを生成して出力するステップと、
前記文脈インデックス生成器により、前記パイプライン式算術符号復号器から出力された前記復号化シンボルのうち、現時点のものより前に出力された過去の復号化シンボルと、さらに前記シンタックスエレメントと、前記ビットストリームの周囲の情報とを与えられ、現時点での復号化に必要な正しい文脈インデックスを生成するステップと、
前記２値化テーブル探索器により、前記入力バッファが出力した前記シンタックスエレメントを与えられてこのシンタックスエレメントのタイプに対応する予め定められた２値化テーブルを外部から取得し、また前記パイプライン式算術符号復号器から出力された現時点の前記復号化シンボルを与えられ、この復号化シンボルを用いて前記２値化テーブルを探索することで、前記シンタックスエレメントの値を得て出力するステップと、
前記予測失敗検出器により、前記文脈インデックス生成器が出力した前記正しい文脈インデックスと、前記文脈インデックス予測器が出力した前記予測された文脈インデックスとを与えられて比較し、両者が異なっていた場合に予測失敗信号を出力するステップとを備え、
前記予測失敗信号が出力されると、前記予測された文脈インデックスを用いて前記パイプライン式算術符号復号器が行った復号化処理をフラッシュし、前記正しい文脈インデックスを用いて復号化処理を再度行って正しい復号化シンボルを出力することを特徴とする算術符号復号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、算術符号復号化方法及びその装置に関する。
【背景技術】
【０００２】
規格書「Ｈ.２６４ Main Profile」により規定されている文脈適応算術符号の復号化処理には、大きな処理能力が必要とされる。
【０００３】
１シンボルの復号化には、最低４ステップの手順を必要とする。その上、あるシンボルについて算術符号の復号化を行う際に必要となる文脈インデックスを求めるためには、それより以前のシンボルについての算術符号の復号化が終了するまで待つ必要があり、パイプライン化による並列処理で処理速度を高速化することは困難であった。
【０００４】
他の画像関係の処理は並列処理により高速化することは可能であると思われるが、文脈適応算術符号の復号化処理は動作周波数をあげるより他に高速化する手法がなかった。
【０００５】
従来から、算術符号はファクシミリやJBIG(ITU勧告T.82)等において用いられている。算術符号を復号化する回路をパイプライン化して高速化する回路として、後述する特許文献１や特許文献２等、様々なものが提案されている。それらの回路では、可能性がある全ての文脈インデックスを用いて、シンボルについての算術符号の復号化処理を同時に実行していき、いずれの文脈インデックスが正しかったかが判明した時点で的中したものを採用するという手法が取られていた。
【０００６】
以下に、従来の算術符号復号化技術に関する文献名を記載する。
【特許文献１】特開２００２−３３９２５号公報
【特許文献２】特開２０００−３５００４３号公報  しかし、上述したような全ての可能性を同時並行で処理していく従来の復号化装置では、パイプラインの段数が増えるとそれに伴い回路規模が指数関数的に増大するという問題があった。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明は上記事情に鑑み、パイプライン段数にかかわらず回路規模の増大を抑制しコスト低減に寄与することが可能な算術符号復号化方法及びその装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の一態様による算術符号復号化装置は、
情報が符号化されたビットストリームを与えられて復号化して復号化シンボルを生成し、この復号化シンボルに対応したシンタックスエレメントの値を出力する算術符号復号化装置であって、
前記ビットストリームに含まれる前記情報の種類を示す前記シンタックスエレメントを与えられ、前記ビットストリームの復号化に必要な文脈インデックスを予測し、予測された文脈インデックスを出力する文脈インデックス予測器と、
前記予測された文脈インデックスと、前記ビットストリームとを与えられ、前記予測された文脈インデックスを用いて前記ビットストリームに復号化処理を行い、予測に基づく復号化シンボルを生成して出力する、複数段のパイプラインを有するパイプライン式算術符号復号器と、
前記パイプライン式算術符号復号器から出力された前記復号化シンボルのうち、現時点のものより前に出力された過去の復号化シンボルを与えられて保持する記憶部を含み、この過去の前記復号化シンボルと、さらに前記シンタックスエレメントと、前記ビットストリームの周囲の情報とを与えられ、現時点での復号化に必要な正しい文脈インデックスを生成する文脈インデックス生成器と、
前記シンタックスエレメントを与えられてこのシンタックスエレメントのタイプに対応する予め定められた２値化テーブルを外部から取得し、また前記パイプライン式算術符号復号器から出力された現時点の前記復号化シンボルを与えられ、この復号化シンボルを用いて前記２値化テーブルを探索することで、前記シンタックスエレメントの値を得て出力する２値化テーブル探索器と、
前記文脈インデックス生成器が出力した前記正しい文脈インデックスと、前記文脈インデックス予測器が出力した前記予測された文脈インデックスとを与えられて比較し、両者が異なっていた場合に予測失敗信号を出力する予測失敗検出器とを備え、
前記パイプライン式算術符号復号器は、前記予測失敗信号が出力されると、前記予測された文脈インデックスを用いて行った復号化処理をフラッシュし、前記正しい文脈インデックスを用いて復号化処理を再度行って正しい復号化シンボルを出力することを特徴とする。
【０００９】
また本発明の一態様による算術符号復号化装置は、
前記ビットストリームに含まれる前記情報の種類を示す前記シンタックスエレメントを与えられ、前記ビットストリームの復号化に必要な文脈インデックスを予測し、予測された文脈インデックスを出力する文脈インデックス予測器と、
前記予測された文脈インデックスと、前記ビットストリームとを与えられ、前記予測された文脈インデックスを用いて前記ビットストリームに復号化処理を行い、予測に基づく復号化シンボルを生成して出力する、複数段のパイプラインを有するパイプライン式算術符号復号器と、
前記シンタックスエレメントを与えられて保持し、順次出力する入力バッファと、
前記パイプライン式算術符号復号器から出力された前記復号化シンボルのうち、現時点のものより前に出力された過去の復号化シンボルを与えられて保持する記憶部を含み、この過去の前記復号化シンボルと、さらに前記入力バッファから出力された前記シンタックスエレメントと、前記ビットストリームの周囲の情報とを与えられ、現時点での復号化に必要な正しい文脈インデックスを生成する文脈インデックス生成器と、
前記入力バッファから出力された前記シンタックスエレメントのタイプに対応する予め定められた２値化テーブルを外部から取得し、また前記パイプライン式算術符号復号器から出力された現時点の前記復号化シンボルを与えられ、この復号化シンボルを用いて前記２値化テーブルを探索することで、複数の前記シンタックスエレメントのそれぞれの値を得て順次出力する２値化テーブル探索器と、
前記２値化テーブル探索器から出力された前記シンタックスエレメントの値を与えられて保持し、出力する出力バッファと、
前記文脈インデックス生成器が出力した前記正しい文脈インデックスと、前記文脈インデックス予測器が出力した前記予測された文脈インデックスとを与えられて比較し、両者が異なっていた場合に予測失敗信号を出力する予測失敗検出器とを備え、
前記パイプライン式算術符号復号器は、前記予測失敗信号が出力されると、前記予測された文脈インデックスを用いて行った復号化処理をフラッシュし、前記正しい文脈インデックスを用いて復号化処理を再度行って正しい復号化シンボルを出力することを特徴とする。
【００１０】
本発明の一態様による算術符号復号化方法は、
情報が符号化されたビットストリームを与えられて復号化して復号化シンボルを生成し、この復号化シンボルに対応したシンタックスエレメントの値を出力する算術符号復号化方法であって、
文脈インデックス予測器、パイプライン式算術符号復号器、文脈インデックス生成器、２値化テーブル探索器、予測失敗検出器を有する復号化装置を用いて、
前記文脈インデックス予測器により、前記ビットストリームに含まれる前記情報の種類を示す前記シンタックスエレメントを与えられ、前記ビットストリームの復号化に必要な文脈インデックスを予測し、予測された文脈インデックスを生成するステップと、
前記パイプライン式算術符号復号器により、前記予測された文脈インデックスと、前記ビットストリームとを与えられ、前記予測された文脈インデックスを用いて前記ビットストリームに復号化処理を行い、予測に基づく復号化シンボルを生成して出力するステップと、
前記文脈インデックス生成器により、前記パイプライン式算術符号復号器から出力された前記復号化シンボルのうち、現時点のものより前に出力された過去の復号化シンボルと、さらに前記シンタックスエレメントと、前記ビットストリームの周囲の情報とを与えられ、現時点での復号化に必要な正しい文脈インデックスを生成するステップと、
前記２値化テーブル探索器により、前記入力バッファが出力した前記シンタックスエレメントを与えられてこのシンタックスエレメントのタイプに対応する予め定められた２値化テーブルを外部から取得し、また前記パイプライン式算術符号復号器から出力された現時点の前記復号化シンボルを与えられ、この復号化シンボルを用いて前記２値化テーブルを探索することで、前記シンタックスエレメントの値を得て出力するステップと、
前記予測失敗検出器により、前記文脈インデックス生成器が出力した前記正しい文脈インデックスと、前記文脈インデックス予測器が出力した前記予測された文脈インデックスとを与えられて比較し、両者が異なっていた場合に予測失敗信号を出力するステップとを備え、
前記予測失敗信号が出力されると、前記予測された文脈インデックスを用いて前記パイプライン式算術符号復号器が行った復号化処理をフラッシュし、前記正しい文脈インデックスを用いて復号化処理を再度行って正しい復号化シンボルを出力することを特徴とする。
【００１１】
また本発明の一態様による算術符号復号化方法は、
前記文脈インデックス予測器により、前記ビットストリームに含まれる前記情報の種類を示す前記シンタックスエレメントを与えられ、前記ビットストリームの復号化に必要な文脈インデックスを予測し、予測された文脈インデックスを生成するステップと、
前記パイプライン式算術符号復号器により、前記予測された文脈インデックスと、前記ビットストリームとを与えられ、前記予測された文脈インデックスを用いて前記ビットストリームに復号化処理を行い、予測に基づく復号化シンボルを生成して出力するステップと、
前記入力バッファにより、前記シンタックスエレメントを与えられて保持し、順次出力していくステップと、
前記文脈インデックス生成器により、前記復号化シンボルのうち、現時点のものより前に出力された過去の復号化シンボルと、さらに前記シンタックスエレメントと、前記ビットストリームの周囲の情報とを与えられ、現時点での復号化に必要な正しい文脈インデックスを生成するステップと、
前記２値化テーブル探索器により、前記シンタックスエレメントのタイプに対応する予め定められた２値化テーブルを外部から取得し、また前記復号化シンボルを順次与えられ、この復号化シンボルを用いて前記２値化テーブルを探索することで、複数の前記シンタックスエレメントのそれぞれの値を得て順次生成していくステップと、
前記出力バッファにより、生成された前記シンタックスエレメントの値を与えられて保持し、出力していくステップと、
前記正しい文脈インデックスと、前記予測された文脈インデックスとを比較し、両者が異なっていた場合に予測失敗を検出するステップとを備え、
前記予測失敗が検出された場合には、前記パイプライン式算術符号復号器により、前記予測された文脈インデックスを用いて行った復号化処理をフラッシュし、前記正しい文脈インデックスを用いて復号化処理を再度行って正しい復号化シンボルを出力することを特徴とする。
【発明の効果】
【００１２】
本発明の算術符号復号化方法及びその装置は、パイプライン段数が増えた場合にも回路規模の増大を抑制しコストを低減することが可能である。
【発明を実施するための最良の形態】
【００１３】
以下、本発明の実施の形態について図面を参照して説明する。
【００１４】
（１）第１の実施の形態
図１に、第１の実施の形態による算術符号復号化装置の構成を示し、また比較例としての算術符号復号化装置の構成を図２に示す。
【００１５】
比較例による装置は、文脈インデックス生成器２１と、ｎ（ｎは２以上の整数）＋１個のパイプライン式算術符号復号器３１、３２、…、３ｎ＋１と、復号化シンボルセレクタ４１とを備える。
【００１６】
文脈インデックス生成器２１に、シンタックスエレメント（Syntax Element）が入力される。ここで、符号化された情報としてのビットストリームは、シンタックスに基づいて情報の配列が規定されている。シンタックスエレメントは、ある特定の場所に配置された情報の種類を示す。例えば、シンタックスに基づいてある場所には情報の種類として「色」に関する情報が格納されている場合、シンタックスエレメントは「色」であり、シンタックスエレメントの値（Value of Syntax Element）は具体的な「赤」、「緑」、「青」等を示すことになる。
【００１７】
このようなシンタックスエレメントが文脈インデックス生成器２１に入力されると、とり得る全ての可能性としてｎ＋１種類の文脈インデックス（context index）０〜ｎが生成される。この文脈インデックスは、ビットストリームの復号化処理に必要なものである。
【００１８】
パイプライン式算術符号復号器３１〜３ｎ＋１は、それぞれが複数段のパイプラインを独立して有し、並列に配置されている。そして、各々のパイプライン式算術符号復号器３１〜３ｎ＋１に、符号化されたビットストリームが同時に与えられ、またそれぞれに異なる文脈インデックス０〜ｎが与えられる。各々のパイプライン式算術符号復号器３１〜３ｎ＋１において、文脈インデックス０〜ｎを用いて複数段のパイプライン化された並列処理によりビットストリームが復号化処理され、得られた復号化シンボルが復号化シンボルセレクタ４１に出力される。
【００１９】
復号化シンボルセレクタ４１は、与えられたｎ＋１個の復号化シンボルのうち、各々のパイプライン式算術符号復号器３１〜３ｎ＋１において処理が進んでいき後に正しいことが判明した文脈インデックスｉ（ｉは０〜ｎの整数）を用いて復号化したものを採用し、外部へ出力する。
【００２０】
しかし、このような構成では、可能性のある全ての文脈インデックス０〜ｎを用いて復号化処理を同時に実行していく必要上、パイプラインの段数の増加に伴い回路規模が指数関数的に増大する。具体的には、パイプラインの段数をｋとすると、２Ｅ（ｋ−２）個のパイプライン式算術符号復号器を備える必要が生じる。
【００２１】
図３を参照して、文脈インデックスを用いて復号化する手順について説明する。先ず０番目のシンボルに対し、例えば「０」という文脈インデックスを用いて復号化した結果、得られる復号化シンボルには可能性として「０」又は「１」の２つが存在する。
【００２２】
復号化結果が「０」の場合は、次の１番目のシンボルに対し、例えば文脈インデックス「５」を用いて復号化し、得られる復号化シンボルには可能性として「０」又は「１」の２つが存在する。同様に、復号化結果が「１」の場合は、次の１番目のシンボルに対し、例えば文脈インデックス「７」を用いて復号化し、得られる復号化シンボルには可能性として「０」又は「１」の２つが存在する。よって、全体として得られる復号化結果には４つの可能性がある。
【００２３】
文脈インデックス「５」を用いて復号化結果が「０」の場合は、次の２番目のシンボルに対し、例えば文脈インデックス「８」を用いて復号化し、得られる復号化シンボルには可能性として「０」又は「１」の２つが存在する。文脈インデックス「５」を用いて復号化結果が「１」の場合は、次の２番目のシンボルに対し、例えば文脈インデックス「１０」を用いて復号化し、得られる復号化シンボルには可能性として「０」又は「１」の２つが存在する。文脈インデックス「７」を用いて復号化結果が「０」の場合は、次の２番目のシンボルに対し、例えば文脈インデックス「４」を用いて復号化し、得られる復号化シンボルには可能性として「０」又は「１」の２つが存在する。文脈インデックス「７」を用いて復号化結果が「１」の場合は、次の２番目のシンボルに対し、例えば文脈インデックス「６」を用いて復号化し、得られる復号化シンボルには可能性として「０」又は「１」の２つが存在する。従って、全体として得られる復号化結果には８つの可能性がある。
【００２４】
このような復号化を、例えば図４に示されたように、３段のパイプライン化された並列処理により行う場合について考える。
【００２５】
０番目のシンボルに対して、文脈インデックス「０」を用いて、Ａ工程、Ｂ工程及びＣ工程で復号化処理を進めていき、Ｃ工程の終了時に復号化結果として「０」又は「１」の復号化シンボルが出力される。
【００２６】
この０番目のシンボルの復号化結果とが「０」又は「１」のいずれであるかが確定しなければ、次の１番目のシンボルの復号化に必要な文脈インデックスが「５」又は「７」のいずれであるか、確定しない。
【００２７】
しかし、パイプライン処理を行うためには、この２つの可能性に対して並行して処理を進める必要がある。即ち、１番目のシンボルに対して、文脈インデックス「５」を用いて、Ａ工程、Ｂ工程及びＣ工程で復号化処理を進めていき、復号化結果として「０」又は「１」の復号化シンボルが出力される。同様に、１番目のシンボルに対して、文脈インデックス「７」を用いて、Ａ工程、Ｂ工程及びＣ工程で復号化処理を進めていき、復号化結果として「０」又は「１」の復号化シンボルが出力される。
【００２８】
次の２番目のシンボルに対して復号化処理を行う場合、０番目のシンボルの復号化結果が出力されるので、１番目のシンボルの復号化を行う際に用いるべき文脈インデックスがいずれであるかが判明する。ここで、０番目のシンボルの復号化結果が「０」であり、１番目のシンボルの復号化を行う際に用いるべき文脈インデックスが「５」であったとする。この場合には、２番目のシンボルに対する復号化に必要な文脈インデックスは、「８」又は「１０」のいずれかに限られ、「４」、「６」は排除される。
【００２９】
従って、パイプラインの段数ｋ＝３の場合には、２Ｅ（３−２）、即ち２個のパイプライン式算術符号復号器を備える必要がある。
【００３０】
同様に、例えば図５に示されたように、４段のパイプライン化された並列処理を行う場合は以下のようである。
【００３１】
０番目のシンボルに対して、文脈インデックス「０」を用いて、Ａ工程、Ｂ工程、Ｃ工程及びＤ工程で復号化処理を進めていき、Ｄ工程の終了時に復号化結果として「０」又は「１」の復号化シンボルが出力される。
【００３２】
１番目のシンボルに対して、文脈インデックス「５」を用いて、Ａ工程、Ｂ工程、Ｃ工程及びＤ工程で復号化処理を進めていき、復号化結果として「０」又は「１」の復号化シンボルが出力される。また１番目のシンボルに対して、文脈インデックス「７」を用いて復号化処理を進めていき、復号化結果として「０」又は「１」の復号化シンボルが出力される。
【００３３】
次の２番目のシンボルに対して復号化処理を行う場合にも、未だ０番目のシンボルの復号化結果は確定していない。よって、４つの全ての可能性について復号化処理を並行して進める必要がある。
【００３４】
２番目のシンボルに対して、文脈インデックス「８」、「１０」、「４」、「６」を用いてそれぞれ復号化処理を進めていき、復号化結果としてそれぞれ「０」又は「１」の復号化シンボルが出力され、全体として８種類の結果が出力されることになる。
【００３５】
次の３番目のシンボルに対して復号化処理を行う場合、０番目のシンボルの復号化結果が出力され、１番目のシンボルの復号化を行う際に用いるべき文脈インデックスがいずれであるかが判明する。ここで、０番目のシンボルの復号化結果が「０」であり、１番目のシンボルの復号化を行う際に用いるべき文脈インデックスが「５」であったとする。この場合には、２番目のシンボルに対する復号化に必要な文脈インデックスは、「８」又は「１０」のいずれかに限られ、「４」、「６」は排除される。さらに、３番目のシンボルに対する復号化に必要な文脈インデックスは、「１１」、「１２」、「１６」又は「１４」のいずれかに限られ、「１３」、「１０」、「１７」、「９」は排除される。
【００３６】
従って、パイプラインの段数ｋ＝４の場合には、２Ｅ（４−２）、即ち４個のパイプライン式算術符号復号器を備える必要がある。
【００３７】
これに対し、第１の実施の形態による算術符号復号化装置は、図１に示すように、文脈インデックス予測器１１、記憶部１４ａを含む文脈インデックス生成器１４、２値化テーブル探索器１５、予測失敗検出器１６、遅延パイプライン１３を備え、さらにパイプラインの段数にかかわらず、パイプライン式算術符号復号器１２を１個備えている。
【００３８】
パイプライン式算術符号復号器１２の前段にある文脈インデックス予測器１１には、文脈インデックス生成器１４から予測に必要な現在のシンタックスエレメントが入力され、また予測に必要な後述するテーブルが図示されていないＣＰＵ等から入力される。ここで、複数の予測手法が存在する場合、特に複数のテーブルが存在するような場合には、いずれの予測手法を用いるかを指示する切り替え信号が図示されていないＣＰＵ等から入力される。
【００３９】
さらに、文脈インデックス生成器１４から、現在のシンタックスエレメントに加えて、復号化シンボル番号（binIdx）が与えられることが望ましいが、必らずしも不可欠な情報ではない。復号化シンボル番号（binIdx）は、パイプライン式算術符号復号器１２からシーケンシャルに出力されていく復号化シンボルが何番目のものであるかを示すものであり、どの段階で予測したかを知るために用いることができる。
【００４０】
図６に、文脈インデックスの予測に用いるテーブルの一例を示す。１サイクル前に出力した文脈インデックスと、現在のシンタックスエレメントに対して予測する文脈インデックスとの対応関係を示す。例えば、１サイクル前に出力した文脈インデックスが「３」である場合、今回予測する文脈インデックスは「４」であり、１サイクル前に出力した文脈インデックスが「５」である場合、今回予測する文脈インデックスは「１０」である。
【００４１】
このテーブルは、文脈インデックスの遷移を示すものであり、予め文脈インデックスに関する過去の履歴に基づいて統計的手法を用いて作成してもよい。
【００４２】
図７に、文脈インデックスの予測に用いるテーブルの他の例を示す。現在のシンタックスエレメントと、現時点でパイプライン式算術符号復号器１２から出力された復号化シンボル番号（binIdx）と、予測する文脈インデックスとの対応関係を示す。例えば、現在のシンタックスエレメントが「０」、復号化シンボル番号（binIdx）が「３」である場合、今回予測する文脈インデックスは「４」である。同様に、現在のシンタックスエレメントが「１」、復号化シンボル番号（binIdx）が「２」である場合、今回予測する文脈インデックスは「７」である。
【００４３】
この場合は、パイプライン式算術符号復号器１２から現在のシンタックスエレメントと、復号化シンボル番号（binIdx）とが与えられる。
【００４４】
２種類以上のテーブルが与えられる場合には、図示されていないＣＰＵ等からいずれのテーブルを用いるかを示す切り替え信号が与えられる。この切り替え信号により、いずれのテーブルを用いた予測手法を行うかが指示される。
【００４５】
このような予測手法を用いて、文脈インデックス予測器１１が、可能性のある複数個の文脈インデックスのうちのいずれか一つを予測して出力する。
【００４６】
出力された文脈インデックスは、パイプライン式算術符号復号器１２に与えられ、また遅延パイプライン１３を経て、パイプラインの段数に対応した時間だけ遅延された後、予測失敗検出器１６に与えられる。
【００４７】
パイプライン式算術符号復号器１２は、符号化された情報であるビットストリームを与えられ、予測された文脈インデックスを用いて、予測が外れる可能性があることを踏まえた上で投機的に復号化し、予測に基づいた復号化シンボルを出力する。
【００４８】
パイプライン式算術符号復号器１２の後段にある文脈インデックス生成器１４は、正しい文脈インデックスの生成に必要な情報として、パイプライン式算術符号復号器１２から出力された予測に基づく復号化シンボルと、シンタックスエレメント、周囲の情報（context information）を与えられる。
【００４９】
先ず、パイプライン式算術符号復号器１２から与えられた復号化シンボルを、記憶部１４ａに記憶していく。文脈インデックスを生成するためには、現時点（ｉ）で復号化を行った復号化シンボルより１つ遡った時点（ｉ−１）から開始時点（０）に至る全ての過去の復号化シンボルが必要である。
【００５０】
周囲の情報とは、ソフトウェアにより文脈インデックス生成器１４に与えられる情報であって、現在復号化しようとしている情報の周囲に関する情報である。例えば、ある場所の画像情報を復号化する際に、その周囲の場所における画像情報をいう。
【００５１】
このような情報を用いて、文脈インデックス生成器１４が正しい文脈インデックスを生成して、予測失敗検出器１６と、次の文脈インデックスの予測に用いるため文脈インデックス予測器１１とに与える。
【００５２】
２値化テーブル探索器１５には、シンタックスエレメントと、このシンタックスエレメントのタイプに対応した、予め定められている２値化テーブルと、パイプライン式算術符号復号器１２から出力された予測に基づく復号化シンボルとが与えられる。
【００５３】
２値化テーブルには、後述するように複数ビットの復号化シンボルが配列された復号化シンボル列と、シンタックスエレメントの値とが１対１に対応付けられている。この２値化テーブルを、復号化シンボル列を用いて探索することで、シンタックスエレメントの値が求まる。
【００５４】
予測失敗検出器１６は、文脈インデックス生成器１４から出力された正しい文脈インデックスと、これと比較するために遅延パイプライン１３を介して与えられた予測された文脈インデックスとを比較し、予測が的中したかあるいは失敗したかを検出する。
【００５５】
両者が異なる場合は、文脈インデックスの予測に失敗したことになる。この場合は、予測失敗検出器１６から予測失敗信号が出力されて、２値化テーブル探索器１５、パイプライン式算術符号復号器１２、文脈インデックス予測器１１に通知される。
【００５６】
また、予測失敗検出器１６から、文脈インデックス予測器１１が行った予測が失敗したことが検出されない場合は、パイプライン式算術符号復号器１２から与えられた予測に基づく復号化シンボルを正しいものとし、求めたシンタックスエレメントの値を最終的な復号化結果として出力する。
【００５７】
文脈インデックス予測器１１は、予測失敗信号が与えられると、文脈インデックスの予測をやり直す。具体的には、文脈インデックス生成器１４から与えられた正しい文脈インデックスを、予測された文脈インデックスとして出力する。
【００５８】
パイプライン式算術符号復号器１２は、予測失敗信号が与えられると、誤った当該予測された文脈インデックスを用いて行った復号化処理からそれ以降の処理までを含むパイプライン処理をフラッシュし、文脈インデックス予測器１１から与えられた正しい文脈インデックスを用いて復号化処理をやり直す。
【００５９】
文脈インデックス生成器１４は、予測失敗信号を与えられると、パイプライン式算術符号復号器１２から与えられていた誤った予測に基づく復号化シンボルをフラッシュし、正しい文脈インデックスを用いてやり直した正しい復号化シンボルを与えられて記憶部１４ａに記憶し、以降の文脈インデックスの生成に用いる。
【００６０】
２値化テーブル探索器１５は予測失敗信号を与えられると、パイプライン式算術符号復号器１２から与えられていた誤った予測に基づく復号化シンボルを用いた探索処理をフラッシュする。そして、正しい文脈インデックスを用いてやり直した正しい復号化シンボルを与えられ、これを用いて２値化テーブルの探索を行い、正しいシンタックスエレメントの値を出力する。
【００６１】
以上のような文脈インデックス予測器１１における予測処理、パイプライン式算術符号復号器１２におけるパイプライン処理、予測失敗検出器１６における失敗検出処理、文脈インデックス生成器１４、２値化テーブル探索器１５における出力処理の流れについて、図８を用いて説明する。
【００６２】
ここでは、パイプライン式算術符号復号器１２のパイプライン段数は５段、文脈インデックス予測器１１のパイプライン段数は１段、文脈インデックス生成器１４のパイプライン段数は１段とする。
【００６３】
尚、図８の縦軸に示されたように、復号化すべきシンボルには順にシンボル番号０、１、２、３、…が付されており、処理が横軸のサイクル０、１、２、３、…に沿って順に進められていくものとする。
【００６４】
また、図８で用いられている記号Ｐ、ＡＤ、ＲＣ、Ｏ、さらにハッチングの意味は、図９（ａ）及び（ｂ）に示された通りである。
【００６５】
ここでは、ある一つのシンボルについて算術符号の復号化を行う処理は、以下の合計８ステージから成っている。
（１）文脈インデックス予測器１１により、ｉ番目のシンボルについて、文脈インデックスを予測するＰ（ｉ）ステージ
（２）パイプライン式算術符号復号器１２により、ｉ番目のシンボルについて、予測された文脈インデックスを用いて算術符号を復号化する５段のＡＤ０（ｉ）〜ＡＤ４（ｉ）ステージ
（３）文脈インデックス生成器１４により、ｉ番目のシンボルについて、Ｏ（ｉ−１）ステージの出力結果を用いて正しい文脈インデックスを求める。ここで、０番目のシンボルについては、前ステージの出力結果が存在せず不要であり、１番目のシンボル以降においてそれぞれ前ステージの出力結果を用いる。そして予測失敗検出器１６により、正しい文脈インデックスと予測された文脈インデックスとを比較し、予測した文脈インデックスが正しいかどうかを検出するＲＣ（ｉ）ステージ
（４）２値化テーブル探索器１４により、ｉ番目のシンボルについて、正しいシンボルの復号化結果として、シンタックスエレメントの値を出力するＯ（ｉ）ステージ
【００６６】
先ず、０番目のシンボルについて行う処理の流れを、図８を用いて述べる。本来の処理はサイクル１から開始され、サイクル０における処理は初期段階において存在した値に対するものであり意味はない。例えば、ＲＣ（０）ステージとして、０番目のシンボルに対して文脈インデックス予測器１１が予測した文脈インデックスが正しいかどうか、予測検出器１５が検出する。しかし、０番目のシンボルに対する文脈インデックスの本来の予測は、７番目のサイクルにおいて行われる。サイクル０における文脈インデックス予測器１１からの出力には意味がなく、この段階での予測失敗検出器１６の検出結果としては予測に失敗したものとなる。
【００６７】
サイクル１において、Ｐ（０）ステージとして、０番目のシンボルについて、文脈インデックス予測器１１が文脈インデックスを予測する。
【００６８】
サイクル２〜６において、５段階のパイプラインから成るＡＤ０（０）〜ＡＤ４（０）ステージとして、０番目のシンボルについて、パイプライン式算術符号復号器１２が、予測された文脈インデックスを用いて算術符号の復号化処理を行う。
【００６９】
サイクル７において、ＲＣ（０）ステージとして、０番目のシンボルについて、文脈インデックス生成器１４が、正しい文脈インデックスを生成する。予測失敗検出器１６が、この正しい文脈インデックスと、遅延パイプライン１３を介してサイクル１において予測され、６つのサイクル分遅延されて与えられた文脈インデックスとを比較し、正しいかどうか検出する。
【００７０】
ここでは予測された文脈インデックスが正しいことが判明したため、次のサイクル８において、Ｏ（０）ステージとして、２値化テーブル探索器１４が、０番目のシンボルについての復号結果として、シンタックスエレメントの値を出力する。
【００７１】
パイプライン処理ゆえ、次の１番目のシンボルを復号化する処理は、ステージ２から開始される。
【００７２】
サイクル２において、Ｐ（１）ステージとして、１番目のシンボルについて、文脈インデックス予測器１１が文脈インデックスを予測する。
【００７３】
サイクル３〜７において、ＡＤ０（１）〜ＡＤ４（１）ステージとして、１番目のシンボルについて、パイプライン式算術符号復号器１２が、予測された文脈インデックスを用いて算術符号の復号化処理を行う。
【００７４】
サイクル８において、ＲＣ（１）ステージとして、１番目のシンボルについて、文脈インデックス生成器１４が、前回のパイプラインの最後段からの出力Ｏ（０）を用いて、正しい文脈インデックスを生成する。予測失敗検出器１６が、この正しい文脈インデックスと、サイクル２において予測され、遅延パイプライン１３により６サイクル分遅延されて与えられた文脈インデックスとを比較し、正しいかどうか検出する。
【００７５】
ここでは予測された文脈インデックスが正しいことが判明したため、次のサイクル９において、Ｏ（１）ステージとして、２値化テーブル探索器１５が、１番目のシンボルについての復号結果を出力する。
【００７６】
次の２番目のシンボルを復号化する処理は、ステージ３から開始される。サイクル３において、Ｐ（２）ステージとして文脈インデックスを予測する。
【００７７】
サイクル４〜８において、ＡＤ０（２）〜ＡＤ４（２）ステージとして予測された文脈インデックスを用いて算術符号の復号化処理を行う。
【００７８】
サイクル９において、ＲＣ（２）ステージとして前回のパイプラインの最後段からの出力Ｏ（１）を用いて正しい文脈インデックスを生成する。この正しい文脈インデックスと遅延パイプライン１３を介してサイクル３において予測された文脈インデックスとを比較し、正しいかどうか検出する。
【００７９】
ここでは予測された文脈インデックスが正しいことが判明したため、サイクル１０において、Ｏ（２）ステージとして２番目のシンボルについての復号結果を出力する。
【００８０】
さらに次の３番目のシンボルを復号化する処理は、ステージ４から開始される。サイクル４において、Ｐ（３）ステージとして文脈インデックスを予測する。
【００８１】
サイクル５〜９において、ＡＤ０（３）〜ＡＤ４（３）ステージとして予測された文脈インデックスを用いて算術符号の復号化処理を行う。
【００８２】
サイクル１０において、ＲＣ（３）ステージとして前回のパイプラインの最後段からの出力Ｏ（２）を用いて正しい文脈インデックスを生成する。この正しい文脈インデックスと遅延パイプライン１３を介してサイクル４において予測された文脈インデックスとを比較し、正しいかどうか検出する。
【００８３】
ここでは、予測された文脈インデックスと正しい文脈インデックスとが相違し、予想された文脈インデックスが正しくないことが判明したとする。
【００８４】
そこで、３番目以降のシンボルに対してサイクル４からサイクル９までに行った全ての処理をフラッシュし、サイクル１１以降においてやり直す。
【００８５】
先ず３番目のシンボルに対し、サイクル１１において、Ｐ（３）ステージとして文脈インデックス予測器１１が文脈インデックス生成器１４から正しい文脈インデックスを与えられ、これを予測した文脈インデックスとして出力する。
【００８６】
サイクル１２〜１６において、ＡＤ０（３）〜ＡＤ４（３）ステージとして正しい文脈インデックスを用いて算術符号の復号化処理を行う。
【００８７】
サイクル１７において、ＲＣ（３）ステージとして、正しい文脈インデックスと遅延パイプライン１３を介してサイクル１１においてやり直した文脈インデックスとを比較し、正しいかどうか検出する。この場合は両者が一致し正しいので、次のサイクル１８において、Ｏ（３）ステージとして３番目のシンボルについての復号結果を出力する。
【００８８】
また、サイクル１０におけるＲＣ（３）ステージとして、予測された文脈インデックスと正しい文脈インデックスとが相違し、予想が正しくなかったことが検出されたことにより、このサイクル１０までの間に並行して処理が進んでいた４〜９番目のシンボルに関する処理もフラッシュし、Ｐ（４）〜Ｐ（９）の予想ステージからやり直す必要がある。
【００８９】
４番目のシンボルを例にとると、サイクル１２から再開し、Ｐ（４）ステージとして正しい文脈インデックスを与えられ、これを予測した文脈インデックスとして出力する。
【００９０】
以降、サイクル１３〜１７において、ＡＤ０（４）〜ＡＤ４（４）ステージとして正しい文脈インデックスを用いて算術符号の復号化処理を行う。
【００９１】
サイクル１８において、ＲＣ（４）ステージとして、正しい文脈インデックスと遅延パイプライン１３を介してサイクル１２においてやり直した文脈インデックスとを比較し、正しいかどうか検出する。この場合は両者が一致し正しいので、次のサイクル１９において、Ｏ（４）ステージとして４番目のシンボルについての復号結果を出力する。
【００９２】
同様に、５番目のシンボルについての処理をサイクル１３から再開し、Ｐ（５）ステージとして正しい文脈インデックスを与えられ、これを予測した文脈インデックスとして出力する。
【００９３】
以降、サイクル１４〜１８において、ＡＤ０（５）〜ＡＤ４（５）ステージとして正しい文脈インデックスを用いて算術符号の復号化処理を行う。
【００９４】
サイクル１９において、ＲＣ（５）ステージとして、正しい文脈インデックスと遅延パイプライン１３を介してサイクル１３においてやり直した文脈インデックスとを比較し、正しいかどうか検出する。この場合は両者が一致し正しいので、次のサイクル２０において、Ｏ（５）ステージとして５番目のシンボルについての復号結果を出力する。
【００９５】
ここで、パイプライン式算術符号復号器１２が文脈インデックスを用いてビットストリームに復号化処理を行って復号化シンボルを生成し、２値化テーブル探索器１５が２値化データである復号化シンボルを用いて２値化テーブルを探索し、シンタックスエレメントの値を求める手順について説明する。
【００９６】
復号化処理では、ビットストリームからシンタックスエレメントに対応した情報を、シンタックスエレメントの値として切り出す作業を行う。
【００９７】
規格書「Ｈ.２６４ Main Profile」では、シンタックスエレメントのタイプ別に、シンタックスエレメントの値（Syntax Element）と復号化シンボル列（bin String）とが、２値化テーブル（Binarization Table）により対応付けられている。
【００９８】
図１０に、シンタックスエレメントの一例として、マクロブロックタイプにおけるシンタックスエレメントの値と、２値化されたデータとしての復号化シンボル列ｂ（０）〜ｂ（２５）とを対応付けた２値化テーブルを示す。
【００９９】
符号化処理の際には、１シンボル毎に、そのシンタックスエレメントの値を２値化する処理が行われる。例えば、シンタックスエレメントの値「５」は、２値化データとして復号化シンボル列「１００１０００」に符号化される。このような２値化データに変換した後、算術符号化を行ってビットストリームを生成する。
【０１００】
復号化する処理では、逆に１シンボルずつ復号化する毎に、ビットストリームを算術符号化して２値化データであるシンボル列ｂ（０）〜ｂ（２５）に変換し、２値化テーブルを用いてこのシンボル列に対応するシンタックスエレメントの値を探索する。
【０１０１】
また、算術符号化及び復号化の際には、上述したように処理に必要な情報として文脈インデックスを用いる。この文脈インデックスは、上述したように、シンタックスエレメントや周囲の情報、１つ前の番号のシンボルに対して符号化あるいは復号化された結果によって決まる。
【０１０２】
従って、復号化処理に必要な情報には、ビットストリーム、シンタックスエレメント、周囲の情報が含まれ、出力される情報はシンタックスエレメントの値である。
【０１０３】
規格書「Ｈ.２６４ Main Profile」により規定されている、２値化データを与えられてシンタックスエレメントの値を求める手順について、図１１のフローチャートを用いて述べる。
【０１０４】
ステップＳ１１として、外部から、復号化すべきビットストリームのシンタックスエレメントが与えられる。これにより、シンタックスエレメントのタイプが例えばマクロブロックタイプであることが判明する。
【０１０５】
ステップＳ１２として、このシンタックスエレメントのタイプに対応する２値化テーブルを外部から取得する。この２値化テーブルは、シンタックスエレメントのタイプ毎に予め定められており、ここでは図１０に示されたマクロブロックタイプの２値化テーブルを例にとり説明する。
【０１０６】
ステップＳ１３において、ビット位置を示す変数（binIdx）０〜ｎ毎の２値化データである復号化シンボル列（Bin String）を求めるため、変数binIdxの初期値として、「−１」を設定する。
【０１０７】
ステップＳ１４において、変数binIdxの値に「１」を加算する。
【０１０８】
ステップＳ１５として、この時のビット位置（binIdx）、即ち最初はビット「０」における、シンタックスエレメント、周囲の情報、以前に符号化された復号化シンボルｂ（０）〜ｂ（binIdx−１）により決定される文脈インデックスを得る。
【０１０９】
ステップＳ１６として、得た文脈インデックスを用いて、当該ビット位置（binIdx）における復号化シンボルｂ（binIdx）を、ビットストリームから復号化する。
【０１１０】
ステップＳ１７において、ステップＳ１２において取得した２値化テーブルを用いて、最初のビット位置「０」から当該ビット位置（binIdx）に至る復号化シンボルデータｂ（０）〜ｂ（binIdx）に対応するシンタックスエレメントの値を探索する。１つのシンタックスエレメントの値に決定されない間は、ステップＳ１４へ戻り、ステップＳ１５〜Ｓ１７までの処理を繰り返す。１つのシンタックスエレメントの値に決定されると、その値を出力してステップＳ１８へ移行し終了する。
【０１１１】
例えば、先ずビット位置「０」における２値化データとして「１」が求まった段階では、シンタックスエレメントの値をいずれかに決定することはできない。
【０１１２】
次に、ビット位置「１」における２値化データとして「０」が求まった段階でも、シンタックスエレメントの値を決定することができない。
【０１１３】
このようにして、順にビット位置「２」、「３」、…における２値化データを求めていき、ビット位置「０」〜「６」までの２値化データとして「１００１１０１」が求まった場合は、一つのシンタックスエレメントの値として「１０」が決定される。
【０１１４】
このようにして復号化処理では、ビットストリームからシンタックスエレメントに対応したシンタックスエレメントの値を切り出していく。
【０１１５】
本実施の形態によれば、復号化処理をパイプライン化された並行処理を行う際に、シンタックスエレメントから文脈インデックスを予想し、予想した文脈インデックスを用いて復号化していき、予想が外れたことが判明した場合にはそれまでに行ったパイプライン処理をフラッシュすることにより、全ての可能性のある文脈インデックスを用いて復号化する場合と異なり、パイプライン段数が増えた際にも回路規模の増大を抑制することができるので、コスト低減が可能である。
【０１１６】
（２）第２の実施の形態
図１２に、本発明の第２の実施の形態による算術符号復号化装置の構成を示す。
【０１１７】
本実施の形態による算術符号復号化装置は、文脈インデックス予測器５１、パイプライン式算術符号復号器５２、遅延パイプライン５３、入力バッファ５４、文脈インデックス生成器５５、２値化テーブル探索器５６、予測失敗検出器５７、出力バッファ５８を備えている。
【０１１８】
上記第１の実施の形態と同様に、パイプライン式算術符号復号器５２の前段に、文脈インデックスを予測する文脈インデックス予測器５１が配置されている。
【０１１９】
また、パイプライン式算術符号復号器５２の後段に、記憶部５５ａに蓄積された過去の復号化シンボルの履歴に基づいて正しい文脈インデックスを生成する文脈インデックス生成器５５、２値化テーブルを探索して復号化シンボル列に対応するシンタックスエレメントの値を求める２値化テーブル探索器５６が配置されている。
【０１２０】
またパイプライン式算術符号復号器５２の後段に、文脈インデックス予測５１が予測した文脈インデックスと文脈インデックス生成器５５が生成した正しい文脈インデックスとを比較し、両者が異なっていた場合に予測失敗信号を出力する予想失敗検出器５７が設けられている。予測失敗信号が出力されると、パイプライン式算術符号復号器５２において、この予測された文脈インデックスを用いて復号化した処理をフラッシュし、正しい文脈インデックスを用いて処理をやり直するようにしている。
【０１２１】
さらに本実施の形態では、上記第１の実施の形態と異なり、複数のシンタックスエレメントＳＥ（０）、ＳＥ（１）、…、ＳＥ（ｎ）を文脈インデックス生成器５５及び２値化テーブル探索器５６に一旦保持して必要なタイミングで入力するため、入力バッファ５４が設けられている。また、２値化テーブル探索器５６から順次出力されていく複数のシンタックスエレメントの値value（０）、value（１）、…、value（ｎ）を一旦保持し、必要なタイミングで出力する出力バッファ５８が設けられている。入力バッファ５４、出力バッファ５８は、それぞれ例えばＦＩＦＯ（First-In First-Out）バッファで構成されている。
【０１２２】
文脈インデックス予測器５１、パイプライン式算術符号復号器５２、遅延パイプライン５３、文脈インデックス生成器５５、２値化テーブル探索器５６、予想失敗検出器５７の動作は、上記第１の実施の形態における文脈インデックス予測器１１、パイプライン式算術符号復号器１２、遅延パイプライン１３、文脈インデックス生成器１４、２値化テーブル探索器１５、予想失敗検出器１６の動作と同様であり、説明を省略する。
【０１２３】
本実施の形態において、ビットストリームから、複数のシンタックスエレメントＳＥ（０）、ＳＥ（１）、…、ＳＥ（ｎ）にそれぞれ対応するシンタックスエレメントの値を切り出して連続的に復号化し出力していく処理の手順について、図１３のフローチャートを参照して説明する。
【０１２４】
ステップＳ２１として、外部から復号化すべきシンタックスエレメントＳＥ（０）、ＳＥ（１）、…、ＳＥ（ｎ）が入力バッファ５４を介して文脈インデックス生成器５５及び２値化テーブル探索器５６に与えられる。これにより、シンタックスエレメントのタイプが例えばマクロブロックタイプであることが判明する。
【０１２５】
ステップＳ２２として、複数のシンタックスエレメントＳＥ（０）、ＳＥ（１）、…、ＳＥ（ｎ）毎にシンタックスエレメントの値を求めていくため、シンタックスエレメントの数に対応した変数ｉの初期値「−１」を設定する。
【０１２６】
ステップＳ２３として、変数ｉの値に「１」を加算する。
【０１２７】
ステップＳ２４として、このシンタックスエレメントのタイプに対応する２値化テーブルを取得する。
【０１２８】
ステップＳ２５において、ビット位置を示す変数（binIdx）０〜ｎ毎の２値化されたデータである復号化シンボル列（Bin String）を求めるため、変数binIdxの初期値として、「−１」を設定する。
【０１２９】
ステップＳ２６において、変数binIdxの値に「１」を加算する。
【０１３０】
ステップＳ２７として、この時のビット位置（binIdx）、即ち最初はビット「０」における、シンタックスエレメントＳＥ（ｉ）、周囲の情報、以前に復号化された復号化シンボル列ｂ（０）〜ｂ（binIdx−１）により決定される文脈インデックスを得る。
【０１３１】
ステップＳ２８として、得た文脈インデックスを用いて、当該ビット位置（binIdx）における符号化された復号化シンボルｂ（binIdx）を、ビットストリームから復号化する。
【０１３２】
ステップＳ２９において、ステップＳ２４において取得した２値化テーブルを用いて、最初のビット位置「０」から当該ビット位置（binIdx）に至る復号化シンボルｂ（０）〜ｂ（binIdx）に対応するシンタックスエレメントの値value（ｉ）を探索する。１つのシンタックスエレメントの値に決定されない間は、ステップＳ２６へ戻り、ステップＳ２７〜Ｓ２９までの処理を繰り返す。１つのシンタックスエレメントの値に決定されると、その値を出力する。
【０１３３】
このステップＳ２４からステップＳ２９までの処理は、上記第１の実施の形態における図１１のステップＳ１２〜Ｓ１７までの処理と同様である。
【０１３４】
ステップＳ３０において、ステップＳ２９で探索して得られたシンタックスエレメントの値value（ｉ）を出力バッファ５８に格納する。
【０１３５】
ステップＳ３１において、全てのシンタックスエレメントＳＥ（ｉ）に対して処理が終了していた場合（ｉ＝ｎ）はステップＳ３２へ移行して終了する。処理が終了していない場合（ｉ＜ｎ）は、ステップＳ２３へ戻り、同様の処理を繰り返す。
【０１３６】
ステップＳ２８において行う算術符号の復号化処理は、上述したように通常複数ステップを必要とする。この場合、パイプライン化された並列処理により、高速に処理を進めることができる。しかし、このような処理を行うためには、パイプライン式算術符号復号器５２に連続して文脈インデックスを供給しなければならない。
【０１３７】
ステップＳ２８における復号化処理に必要な文脈インデックスは、ステップＳ２７で求められる。この文脈インデックスを求める際には、後のステップＳ２８における復号化処理の結果である復号化シンボルｂ（binIdx−１）が必要とされる。
【０１３８】
また、ステップＳ２９においてステップＳ２６に分岐する場合と、ステップＳ３０に分岐する場合とで、異なったシンタックスエレメントＳＥ（ｉ）が与えられる。このため、文脈インデックスを求めるには、その分岐がどちらになるかという情報も必要である。
【０１３９】
従って、「Ｈ.２６４ Main Profile」で規定される算術符号の復号化処理には、通常のパイプライン化された並列処理機構をそのまま適用することはできない。
【０１４０】
本実施の形態では、上述したように、復号化シンボルｂ（binIdx−１）の確定に先行して文脈インデックス予測器５１により文脈インデックスを予測し、パイプライン式算術符号復号器５２に投入する。
【０１４１】
また、復号化シンボルｂ（binIdx−１）が確定し正しい文脈インデックスが求まった時点で、予測された文脈インデックスと比較して両者が異なっていた場合、誤った予測に基づいてその時点までに行ったパイプラインによる復号化処理をフラッシュして処理をやり直すようにしている。
【０１４２】
これにより、本実施の形態によれば、パイプライン式算術符号復号器１２における復号化シンボルｂ（binIdx−１）の確定を待たずして連続的にパイプライン式算術符号復号化装置に文脈インデックスを予想して投入し復号化処理を進めていくことができるため、文脈インデックスの予測が正しい状況においては高速に復号化を行うことができる。
【０１４３】
また、従来と異なり、算術符号復号器のパイプライン段数にかかわりなくパイプライン式算術符号復号器を１つ備えればよいので、回路規模の増大を抑制することができる。
【０１４４】
上述した実施の形態はいずれも一例であって、本発明を限定するものではない。例えば、図１０に示された２値化テーブルはシンタックスエレメントがマクロブロックタイプである場合に用いられるが、これに限らず他のタイプのシンタックスエレメントに対しても本発明の適用が可能である。
【図面の簡単な説明】
【０１４５】
【図１】本発明の第１の実施の形態による算術符号復号化装置の構成を示すブロック図。
【図２】比較例による算術符号復号化装置の構成を示すブロック図。
【図３】復号化処理の手順を示す説明図。
【図４】３段のパイプライン化された並列処理により復号化を進めている手順を示す説明図。
【図５】４段のパイプライン化された並列処理により復号化を進めている手順を示す説明図。
【図６】上記第１の実施の形態における文脈インデックス予測器が用いるテーブルの一例を示した説明図。
【図７】同文脈インデックス予測器が用いるテーブルの一例を示した説明図。
【図８】上記第１の実施の形態による算術符号復号化装置におけるパイプラインステージを示す説明図。
【図９】同パイプラインステージにおける処理内容を示す説明図。
【図１０】上記第１の実施の形態による算術符号復号化装置において用いられる、マクロブロック型シンタックスエレメントの値と２値化データとの対応関係を示す説明図。
【図１１】上記第１の実施の形態による算術符号復号化装置における文脈適応算術符号の復号化手順を示すフローチャート。
【図１２】本発明の第２の実施の形態による算術符号復号化装置の構成を示すブロック図。
【図１３】同第２の実施の形態による算術符号復号化装置における文脈適応算術符号の復号化処理を連続して行う手順を示すフローチャート。
【符号の説明】
【０１４６】
１１、２１、５１  文脈インデックス予測器
１２、３１〜３ｎ＋１、５２  パイプライン式算術符号復号器
１３、５３  遅延パイプライン
１４、５５  文脈インデックス生成器
１４ａ、５５ａ  記憶部
１５、５６  ２値化テーブル探索器
１６、５７  予測失敗検出器
４１  復号化シンボルセレクタ
５４  入力バッファ
５８  出力バッファ
【図１】
2006033335.tif 000003
【図２】
2006033335.tif 000004
【図３】
2006033335.tif 000005
【図４】
2006033335.tif 000006
【図５】
2006033335.tif 000007
【図６】
2006033335.tif 000008
【図７】
2006033335.tif 000009
【図８】
2006033335.tif 000010
【図９】
2006033335.tif 000011
【図１０】
2006033335.tif 000012
【図１１】
2006033335.tif 000013
【図１２】
2006033335.tif 000014
【図１３】
2006033335.tif 000015