復号装置、復号方法および復号プログラム
【課題】復号の高速化を図ること。
【解決手段】復号装置は、マルチコンテキスト型の算術符号化により所定の数値範囲に割り当てられた符号値から算術符号化の前のデータ列１１０を復号する。復号装置は、データ列１１０の各位置ｘ１〜ｘ１０における所定シンボルの発生確率ｐ１〜ｐ１０を取得する。復号装置は、発生確率ｐ１〜ｐ１０の中の、復号対象位置１０１が属するグループ１１１における最小の発生確率に相当する割合による数値範囲の減少幅を導出する。復号装置は、数値範囲の限界値と符号値との差分を、導出した減少幅によって除算する。復号装置は、除算により得た商が所定値以上である場合に、商だけ連続する所定シンボルとなる復号結果を出力する。
【解決手段】復号装置は、マルチコンテキスト型の算術符号化により所定の数値範囲に割り当てられた符号値から算術符号化の前のデータ列１１０を復号する。復号装置は、データ列１１０の各位置ｘ１〜ｘ１０における所定シンボルの発生確率ｐ１〜ｐ１０を取得する。復号装置は、発生確率ｐ１〜ｐ１０の中の、復号対象位置１０１が属するグループ１１１における最小の発生確率に相当する割合による数値範囲の減少幅を導出する。復号装置は、数値範囲の限界値と符号値との差分を、導出した減少幅によって除算する。復号装置は、除算により得た商が所定値以上である場合に、商だけ連続する所定シンボルとなる復号結果を出力する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、復号装置、復号方法および復号プログラムに関する。
【背景技術】
【０００２】
算術符号化は、データ列全体をひとつの符号値に置き換えることにより、ハフマン符号化より圧縮率を高める符号化技術である。しかし、算術符号化は、符号化および復号に要する処理量がハフマン符号化より多い。
【０００３】
たとえば動画像圧縮の分野において、算術符号化は、Ｈ．２６４やＶＰ８などの規格にも採用されており、動画像の時間的または空間的相関性を利用した圧縮を施した後のエントロピー符号化として利用されている。また、Ｈ．２６４やＶＰ８ではマルチコンテキスト方式が採用されており、符号化するデータ列の内容に応じてシンボルの発生確率を切り替えることでより圧縮効率を向上させている。
【０００４】
算術符号化されたデータは１ビットずつ復号していくことになるため、処理を並列化して複数のビットを同時に復号することは困難である。このため、復号性能を向上させるには、動作周波数を向上させることが考えられるが、マルチコンテキスト方式ではコンテキストの切り替え処理も必要なため、動作周波数の高速化にも限度がある。
【０００５】
このため、従来はある特定の条件を満たすケースにおいて複数シンボルの同時復号を行うことにより復号処理の高速化を図る一括復号の手法が用いられている（たとえば、下記特許文献１，２参照。）。たとえば、同一コンテキストのＭＰＳ（Ｍｏｒｅ ｐｒｏｂａｂｌｅ Ｓｙｍｂｏｌ：優勢シンボル）が、予め定められた２、４、８または１６連続する場合で、かつ復号途中の正規化処理が不要な場合において、１サイクルで一括して複数のビットを復号する手法が知られている。また、コンテキストが切り替わる際において、予めＭＰＳが連続する場合のコンテキスト情報を内部に持っておくことにより、１サイクルで複数のビットを一括して復号する手法等が知られている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０００−３５００４３号公報
【特許文献２】特開２００５−２１７８７１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上述した従来技術では、一括復号するビット数を予め決定しておくことになるため、予め決定された数だけ同一シンボルが連続しない場合は一括復号が実行されない。このため、シンタクスによっては一括復号の発生確率が低くなり、復号の高速化を図ることができないという問題がある。
【０００８】
本発明は、上述した従来技術による問題点を解消するため、復号の高速化を図ることができる復号装置、復号方法および復号プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上述した課題を解決し、目的を達成するため、本発明の一側面によれば、マルチコンテキスト型の算術符号化により所定の数値範囲に割り当てられた符号値から前記算術符号化の前のデータ列を復号する復号方法において、前記数値範囲を記憶し、前記データ列の各位置における所定シンボルの発生確率を取得し、取得した発生確率の中の、前記データ列を区切った複数のグループのうちの復号対象の位置が属するグループにおける最小の発生確率に基づく前記数値範囲の減少幅を導出し、前記数値範囲の限界値と前記符号値との差分を、前記導出した減少幅によって除算し、除算により得た商が所定値以上である場合に、前記商だけ連続する前記所定シンボルとなる、前記復号対象の位置以降の復号結果を出力する復号装置、復号方法および復号プログラムが提案される。
【発明の効果】
【００１０】
本発明の一側面によれば、復号の高速化を図ることができるという効果を奏する。
【図面の簡単な説明】
【００１１】
【図１−１】図１−１は、実施の形態１にかかる復号装置による復号処理の一例を示す図（その１）である。
【図１−２】図１−２は、実施の形態１にかかる復号装置による復号処理の一例を示す図（その２）である。
【図１−３】図１−３は、実施の形態１にかかる復号装置による復号処理の一例を示す図（その３）である。
【図２】図２は、復号装置のハードウェア構成の一例を示す図である。
【図３−１】図３−１は、シンタクスとグループＩＤとの対応情報の一例を示す図である。
【図３−２】図３−２は、グループＩＤと発生確率の対応情報の一例を示す図である。
【図４】図４は、復号装置による復号処理の一例を示すフローチャートである。
【図５】図５は、１ビット復号処理の一例を示すフローチャートである。
【図６】図６は、１ビット復号処理の一例を示す図である。
【図７】図７は、Ｎビット復号処理の一例を示すフローチャートである。
【図８】図８は、一括復号ビット数Ｎの算出処理の一例を示すフローチャートである。
【図９】図９は、Ｎビット復号処理の一例を示す図である。
【図１０】図１０は、復号装置の構成の一例を示す図である。
【図１１】図１１は、１ビット復号処理部の構成の一例を示す図である。
【図１２】図１２は、Ｎビット復号装置の構成の一例を示す図である。
【図１３】図１３は、一括復号ビット数算出部の構成の一例を示す図である。
【図１４】図１４は、グループＩＤと減少値の対応情報の一例を示す図である。
【図１５】図１５は、一括復号ビット数Ｎの算出処理の一例を示すフローチャートである。
【図１６】図１６は、実施の形態２にかかる一括復号ビット数算出部の構成の一例を示す図である。
【図１７】図１７は、符号化処理の一例を示すフローチャートである。
【図１８】図１８は、符号化処理における再正規化処理の一例を示すフローチャートである。
【図１９】図１９は、再正規化処理におけるライト処理の一例を示すフローチャートである。
【図２０】図２０は、シンタクスのグループ分けの一例を示す図である。
【図２１−１】図２１−１は、具体例にかかるシンタクスとグループＩＤの対応情報を示す図である。
【図２１−２】図２１−２は、具体例にかかるグループＩＤと減少値の対応情報を示す図である。
【発明を実施するための形態】
【００１２】
以下に添付図面を参照して、本発明にかかる復号装置、復号方法および復号プログラムの実施の形態を詳細に説明する。
【００１３】
（実施の形態１）
（実施の形態１にかかる復号装置による復号処理）
図１−１〜図１−３は、実施の形態１にかかる復号装置による復号処理の一例を示す図である。実施の形態１にかかる復号装置１００（たとえば図２−１参照）は、マルチコンテキスト型の算術符号化により所定の数値範囲に割り当てられた符号値から、算術符号化の前のデータを復号する。算術符号化は、たとえばレンジコーダである。
【００１４】
ここではＶＰ８による復号処理について説明するが、エンコードおよびデコードの方式はＶＰ８に限らない。ＶＰ８で使用されている算術符号化はマルチコンテキスト型であるため、シンタクスやシンタクス内のビット位置によって二値（０／１）の発生確率が変化する。また算術符号化に用いる数直線（範囲Ｒａｎｇｅ）は０から２５５の整数値として扱われる。そして、範囲Ｒａｎｇｅの値が１２８未満になった場合には、範囲Ｒａｎｇｅと現在の符号値（符号値Ｖａｌｕｅ）の値を倍にすること（再正規化）により、精度を保ったまま符号化および復号が行われる。
【００１５】
図１−１に示すデータ列１１０は、復号装置１００によって復号されるデータである。位置ｘ１〜ｘ１０は、データ列１１０における各位置（たとえばビット位置）を示している。復号装置１００は、復号処理を行うことによって位置ｘ１〜ｘ１０における各値を得る。
【００１６】
発生確率ｐ１〜ｐ１０は、それぞれ位置ｘ１〜ｘ１０における所定シンボルの発生確率（以下、単に「発生確率」とも称する。）を示している。所定シンボルは、たとえばデータ列１１０における優勢シンボルである。また、以下の説明において、データ列１１０における優勢シンボルは“０”とする。復号対象位置１０１は、復号装置１００による現在の復号対象の位置を示している。初期状態における復号対象位置１０１は位置ｘ１である。
【００１７】
図１−２に示す数値範囲１２１は、データ列１１０が算術符号化により割り当てられた所定の数値範囲（たとえば０〜２５５）を示している。限界値１２１ａは、数値範囲１２１の限界値（たとえば上限値）を示している。符号値１０２は、数値範囲１２１に割り当てられた復号対象の符号値を示している。
【００１８】
復号装置１００は、データ列１１０の位置ｘ１〜ｘ１０を複数のグループに分けておく。各グループには連続する複数の位置が含まれる。図１−１に示す例では、位置ｘ１〜ｘ１０がグループ１１１〜１１３に分けられている。位置ｘ１〜ｘ３はグループ１１１に含まれている。位置ｘ４〜ｘ７はグループ１１２に含まれている。位置ｘ８〜ｘ１０はグループ１１３に含まれている。
【００１９】
たとえば、復号装置１００は、位置ｘ１〜ｘ１０を所定数ずつ区切ってグループ分けしてもよいし、位置ｘ１〜ｘ１０を発生確率ｐ１〜ｐ１０に基づいて区切ってグループ分けしてもよい（たとえば図２０参照）。
【００２０】
復号装置１００は、数値範囲１２１を取得して記憶する。また、復号装置１００は、発生確率ｐ１〜ｐ１０を取得する。そして、復号装置１００は、グループ１１１〜１１３のうちの現在の復号対象位置１０１が属するグループの各発生確率の中から最小の発生確率を特定する。図１−１に示す例では、復号対象位置１０１の位置ｘ１はグループ１１１に属しているため、グループ１１１に属する位置ｘ１〜ｘ３における発生確率ｐ１〜ｐ３のうちの最小の発生確率が特定される。
【００２１】
また、復号装置１００は、特定した発生確率に相当する割合で数値範囲１２１を縮小した場合における数値範囲１２１の減少幅を算出する。数値範囲１２２は、特定した発生確率に相当する割合で数値範囲１２１を縮小した数値範囲である。減少幅１２２ａは、数値範囲１２１に対する数値範囲１２２の減少幅である。たとえば、減少幅１２２ａは、数値範囲１２１の幅から数値範囲１２２の幅を減算することによって算出することができる。
【００２２】
そして、復号装置１００は、数値範囲１２１の限界値１２１ａと符号値１０２との差分１２２ｂを減少幅１２２ａによって除算した商を算出する。これにより、復号対象位置１０１以降の復号結果において所定シンボルが連続する最小の回数を算出することができる。図１−２に示す例では、商として２が算出される。
【００２３】
つぎに、復号装置１００は、算出した商が所定値以上である場合に、算出した商だけ連続する所定シンボルとなる復号結果を出力する。所定値は、連続復号を行うか否かを判定するための所定シンボルの連続数の閾値であり、たとえば１である。図１−２に示した例では商は２であるため、図１−３に示すように、２回連続する所定シンボル“０”、すなわち“００”が位置ｘ１，ｘ２の復号結果として出力される。これにより、一括復号による復号結果を得ることができる。
【００２４】
また、復号装置１００は、一括復号により復号結果を出力した場合に、現在の復号対象位置１０１から商の数だけ先の位置を次の復号対象位置１０１とする。図１−１の例では復号対象位置１０１が位置ｘ１であり、商が２であるため、図１−３に示すように、新たな復号対象位置１０１は位置ｘ１の２つ先の位置ｘ３となる。復号装置１００は、新たな復号対象位置１０１について再度復号処理を行う。
【００２５】
また、復号装置１００は、算出した商が所定値以上である場合に、減少幅１２２ａに商を乗じた幅だけ数値範囲１２１を縮小する。図１−２に示す例では、商が２であるため、減少幅１２２ａの２倍の幅だけ数値範囲１２１が縮小される。このため、数値範囲１２１は縮小されて数値範囲１２３のようになる。
【００２６】
また、復号装置１００は、縮小した数値範囲１２３の限界値が閾値（たとえば１２８）を下回った場合は、数値範囲１２３および符号値１０２を同一比率で増大させる再正規化を行ってもよい。たとえば、復号装置１００は、数値範囲１２３の幅が閾値を下回った場合は、数値範囲１２３の幅が閾値以上になるまで、数値範囲１２３および符号値１０２を倍増する処理を繰り返す。これにより、精度を保ったまま復号処理を行うことができる。
【００２７】
再正規化を行う場合は、復号装置１００は、数値範囲１２１の限界値１２１ａと符号値１０２との差分１２２ｂと、数値範囲１２１の限界値１２１ａと閾値との差分と、のうちの小さい方の差分を減少幅１２２ａによって除算した商を算出する。これにより、復号対象位置１０１以降の復号結果において所定シンボルが連続し、かつ再正規化が発生しない最小の回数を算出することができる。
【００２８】
また、復号装置１００は、算出した商が所定値未満（たとえば０）であった場合に、数値範囲１２１と、復号対象位置１０１に対応する発生確率ｐ１と、符号値１０２と、に基づいて復号対象位置１０１（位置ｘ１）を復号した復号結果を出力する。この場合は、復号装置１００は、復号結果と、発生確率ｐ１と、に応じて復号対象位置１０１を縮小する。また、この場合は、復号装置１００は、位置ｘ１〜ｘ１０のうちの現在の復号対象位置１０１から１つ先の位置を次の復号対象位置１０１とする。
【００２９】
このように、復号装置１００によれば、復号データの各位置をグループ分けし、復号対象の位置が属するグループの所定シンボルの最小の発生確率に基づいて所定シンボルの最小の連続数を算出することができる。これにより、一括復号数を予め定めておかなくても、所定シンボルの発生確率に基づいて一括復号数を適応的に変化させて一括復号を行うことができる。このため、一括復号の実施確率を高めて復号の高速化を図ることができる。
【００３０】
（復号装置のハードウェア構成）
図２は、復号装置のハードウェア構成の一例を示す図である。図１に示した復号装置１００は、たとえば図２に示す情報処理装置２００によって実現することができる。情報処理装置２００は、ＣＰＵ２１０と、メインメモリ２２０と、補助メモリ２３０と、ユーザインタフェース２４０と、通信インタフェース２５０と、バス２０１と、を備えている。ＣＰＵ２１０、メインメモリ２２０、補助メモリ２３０、ユーザインタフェース２４０および通信インタフェース２５０は、バス２０１によって接続されている。
【００３１】
ＣＰＵ２１０（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）は、情報処理装置２００の全体の制御を司る。また、情報処理装置２００はＣＰＵ２１０を複数備えていてもよい。メインメモリ２２０は、たとえばＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）である。メインメモリ２２０は、ＣＰＵ２１０のワークエリアとして使用される。補助メモリ２３０は、たとえば、ハードディスク、光ディスク、フラッシュメモリなどの不揮発メモリである。補助メモリ２３０には、情報処理装置２００を動作させる各種のプログラムが記憶されている。補助メモリ２３０に記憶されたプログラムは、メインメモリ２２０にロードされてＣＰＵ２１０によって実行される。
【００３２】
ユーザインタフェース２４０は、たとえば、ユーザからの操作入力を受け付ける入力デバイスや、ユーザへ情報を出力する出力デバイスなどを含む。入力デバイスは、たとえばキー（たとえばキーボード）やリモコンなどによって実現することができる。出力デバイスは、たとえばディスプレイやスピーカなどによって実現することができる。また、タッチパネルなどによって入力デバイスおよび出力デバイスを実現してもよい。ユーザインタフェース２４０は、ＣＰＵ２１０によって制御される。
【００３３】
通信インタフェース２５０は、たとえば、無線によって情報処理装置２００の外部との間で通信を行う通信インタフェースである。たとえば、復号装置１００は、算術符号化されたストリームデータを通信インタフェース２５０によって受信し、受信したストリームデータを復号する。通信インタフェース２５０は、ＣＰＵ２１０によって制御される。
【００３４】
（シンタクスとグループＩＤとの対応情報）
図３−１は、シンタクスとグループＩＤとの対応情報の一例を示す図である。図３−１に示す対応情報３１０は、シンタクスとグループＩＤとを対応付ける対応情報である。対応情報３１０は、たとえば復号装置１００のメインメモリ２２０や補助メモリ２３０に記憶されている。対応情報３１０に示すように、シンタクス「Ｓｙｎｔａｘ＿Ａ」〜「Ｓｙｎｔａｘ＿Ｘ」のそれぞれは、グループＩＤが「０」〜「Ｙ」の各グループに分類されている。
【００３５】
たとえば、シンタクス「Ｓｙｎｔａｘ＿Ａ」はグループＩＤ「０」のグループに属している。シンタクス「Ｓｙｎｔａｘ＿Ｂ」〜「Ｓｙｎｔａｘ＿Ｄ」はグループＩＤ「１」のグループに属している。図３−１に示す例では、シンタクス単位でグループ分けを行う例について説明したが、グループ分けはシンタクス単位に限らず、シンタクスのビット位置単位など、コンテキスト（優勢シンボルの発生確率）単位で行ってもよい。
【００３６】
（グループＩＤと発生確率の対応情報）
図３−２は、グループＩＤと発生確率の対応情報の一例を示す図である。図３−２に示す対応情報３２０は、グループＩＤと優勢シンボルの最小の発生確率とを対応付ける対応情報である。対応情報３２０は、たとえば復号装置１００のメインメモリ２２０や補助メモリ２３０に記憶されている。
【００３７】
対応情報３２０に示す最小の発生確率ｐｒｏｂＧ（０）〜ｐｒｏｂＧ（Ｙ）は、それぞれグループＩＤ「０」〜「Ｙ」が示すグループに属する各シンタクスの優勢シンボルの発生確率のうちの最小の発生確率を示している。たとえば、最小の発生確率ｐｒｏｂＧ（１）は、グループＩＤ「１」が示すグループに属するシンタクス「Ｓｙｎｔａｘ＿Ｂ」〜「Ｓｙｎｔａｘ＿Ｄ」の優勢シンボルの発生確率のうちの最小の発生確率を示している。
【００３８】
（復号装置による復号処理）
図４は、復号装置による復号処理の一例を示すフローチャートである。復号装置１００は、復号処理としてたとえば以下の各ステップを実行する。まず、復号装置１００は、復号対象のシンタクスを初期化する（ステップＳ４０１）。ステップＳ４０１において、復号装置１００は、たとえば、最初の復号位置におけるシンタクスを、符号化側から予め通知されたシンタクスに設定する。
【００３９】
つぎに、復号装置１００は、入力されたデータストリームの先頭の８ビット（ｒｅａｄ＿ｂｉｔ（８））を取り出して符号値Ｖａｌｕｅの初期値として設定する（ステップＳ４０２）。また、復号装置１００は、数直線を示す範囲Ｒａｎｇｅの初期値として２５５を設定する（ステップＳ４０３）。
【００４０】
つぎに、復号装置１００は、復号対象のシンタクスの各ビットにおける“０”（優勢シンボル）の発生確率ｐｒｏｂを取得する（ステップＳ４０４）。つぎに、復号装置１００は、一括復号ビット数Ｎを算出する（ステップＳ４０５）。一括復号ビット数Ｎは、以降の復号結果において優勢シンボルである“０”が連続する回数である。ステップＳ４０５における一括復号ビット数Ｎの算出処理については後述する（たとえば図８参照）。
【００４１】
つぎに、復号装置１００は、ステップＳ４０５によって算出した一括復号ビット数Ｎが０であるか否かを判断する（ステップＳ４０６）。一括復号ビット数Ｎが０でない場合（ステップＳ４０６：Ｎｏ）は、復号装置１００は、Ｎビット復号処理を行い（ステップＳ４０７）、ステップＳ４０９へ移行する。Ｎビット復号処理は、Ｎビットの“０”を一括して復号する処理である。ステップＳ４０７におけるＮビット復号処理については後述（たとえば図７参照）する。
【００４２】
ステップＳ４０６において、一括復号ビット数Ｎが０である場合（ステップＳ４０６：Ｙｅｓ）は、復号装置１００は、１ビット復号処理を行い（ステップＳ４０８）、ステップＳ４０９へ移行する。１ビット復号処理は、次の復号結果が“０”および“１”のいずれであるかを判定して復号する処理である。ステップＳ４０８における１ビット復号処理については後述（たとえば図５参照）する。
【００４３】
つぎに、復号装置１００は、ステップＳ４０７のＮビット復号処理またはステップＳ４０８の１ビット復号処理による復号結果を逆二値化する（ステップＳ４０９）。つぎに、復号装置１００は、ステップＳ４０９の逆二値化の結果に基づいて復号対象のシンタクスを更新する（ステップＳ４１０）。つぎに、復号装置１００は、復号対象の全てのシンタクスを復号したか否かを判断する（ステップＳ４１１）。
【００４４】
ステップＳ４１１において、全てのシンタクスを復号していない場合（ステップＳ４１１：Ｎｏ）は、復号装置１００は、ステップＳ４０４へ戻る。全てのシンタクスを復号した場合（ステップＳ４１１：Ｙｅｓ）は、復号装置１００は、ステップＳ４０９の逆二値化により得られた復号結果のデータを出力し（ステップＳ４１２）、一連の処理を終了する。以上の各ステップにより、入力されたデータストリームの復号結果のデータを得ることができる。
【００４５】
（１ビット復号処理）
図５は、１ビット復号処理の一例を示すフローチャートである。復号装置１００は、図４に示したステップＳ４０８における１ビット復号処理として、たとえば以下の各ステップを実行する。
【００４６】
まず、復号装置１００は、現在の範囲Ｒａｎｇｅと、復号対象の１ビットにおける優勢シンボルの発生確率ｐｒｏｂに基づいて境界値ｓｐｌｉｔを算出する（ステップＳ５０１）。境界値ｓｐｌｉｔは、範囲Ｒａｎｇｅにおける“０”と“１”の境界値である。優勢シンボルの発生確率ｐｒｏｂは、復号対象のシンタクスおよびシンタクスのビット位置に基づいて求めることができる。ステップＳ５０１において、復号装置１００は、たとえば１＋（（（範囲Ｒａｎｇｅ−１）＊ｐｒｏｂ）＞＞８）によって境界値ｓｐｌｉｔを算出することができる。
【００４７】
つぎに、復号装置１００は、現在の符号値Ｖａｌｕｅが、ステップＳ５０１によって算出された境界値ｓｐｌｉｔ以上であるか否かを判断する（ステップＳ５０２）。現在の符号値Ｖａｌｕｅが境界値ｓｐｌｉｔ以上である場合（ステップＳ５０２：Ｙｅｓ）は、復号装置１００は、復号値として“１”を出力する（ステップＳ５０３）。
【００４８】
つぎに、復号装置１００は、範囲Ｒａｎｇｅから境界値ｓｐｌｉｔを減算する（ステップＳ５０４）。また、復号装置１００は、符号値Ｖａｌｕｅから境界値ｓｐｌｉｔを減算し（ステップＳ５０５）、ステップＳ５０８へ移行する。
【００４９】
ステップＳ５０２において、現在の符号値Ｖａｌｕｅが境界値ｓｐｌｉｔ未満である場合（ステップＳ５０２：Ｎｏ）は、復号装置１００は、復号値として“０”を出力する（ステップＳ５０６）。つぎに、復号装置１００は、範囲Ｒａｎｇｅに境界値ｓｐｌｉｔの値を設定し（ステップＳ５０７）、ステップＳ５０８へ移行する。
【００５０】
つぎに、復号装置１００は、範囲Ｒａｎｇｅが１２８未満か否かを判断する（ステップＳ５０８）。範囲Ｒａｎｇｅが１２８未満である場合（ステップＳ５０８：Ｙｅｓ）は、復号装置１００は、再正規化を行う。すなわち、復号装置１００は、範囲Ｒａｎｇｅの値を１ビット左シフトさせることで２倍にする（ステップＳ５０９）。
【００５１】
また、復号装置１００は、符号値Ｖａｌｕｅの値を１ビット左シフトさせることで２倍にする（ステップＳ５１０）。つぎに、復号装置１００は、ストリームデータから１ビット（ｒｅａｄ＿ｂｉｔ（１））を取り出して符号値Ｖａｌｕｅの最下位ビットとして補充し（ステップＳ５１１）、ステップＳ５０８へ戻る。このように、復号装置１００は、再正規化を実行する度にストリームデータを１ビットずつ読み出す。
【００５２】
ステップＳ５０８において、範囲Ｒａｎｇｅが１２８以上である場合（ステップＳ５０８：Ｎｏ）は、復号装置１００は、一連の処理を終了する。以上の各ステップにより、復号装置１００は、１ビットの復号を行うことができる。また、復号装置１００は、１ビットの復号によって範囲Ｒａｎｇｅが１２８未満になった場合は、範囲Ｒａｎｇｅおよび符号値Ｖａｌｕｅを２倍にしてストリームデータを１ビット読み出すことができる。
【００５３】
図６は、１ビット復号処理の一例を示す図である。図６においては、図５に示した１ビット復号処理を連続して４回行った場合の例について説明する。１〜４回目の１ビット復号処理において、シンタクスの優勢シンボル“０”の発生確率は、それぞれ２０４／２５６，２３０／２５６，１７９／２５６，２０４／２５６と遷移するものとする。まず、初期化処理として、ストリームデータ６１０から先頭の８ビットのデータ列６１１が符号値Ｖａｌｕｅに設定される。データ列６１１は“１０１０１０００”（１６８）とする。また、範囲Ｒａｎｇｅに２５５が設定される。
【００５４】
１回目の１ビット復号処理においては、範囲Ｒａｎｇｅが２５５であり、発生確率が２０４／２５６であるため、境界値ｓｐｌｉｔは２０３（小数点以下切り捨て。以下同様）となる。したがって、符号値Ｖａｌｕｅの１６８は境界値ｓｐｌｉｔ未満であるため、復号値は“０”となる。また、以降の範囲Ｒａｎｇｅは境界値ｓｐｌｉｔの２０３となる。また、範囲Ｒａｎｇｅは１２８以上であるため、再正規化は発生しない。
【００５５】
２回目の１ビット復号処理においては、範囲Ｒａｎｇｅが２０３であり、発生確率が２３０／２５６であるため、境界値ｓｐｌｉｔは１８２となる。したがって、符号値Ｖａｌｕｅの１６８は境界値ｓｐｌｉｔ未満であるため、復号値は“０”となる。また、以降の範囲Ｒａｎｇｅは境界値ｓｐｌｉｔの１８２となる。また、範囲Ｒａｎｇｅは１２８以上であるため、再正規化は発生しない。
【００５６】
３回目の１ビット復号処理においては、範囲Ｒａｎｇｅが１８２であり、発生確率が１７９／２５６であるため、境界値ｓｐｌｉｔは１２７となる。したがって、符号値Ｖａｌｕｅの１６８は境界値ｓｐｌｉｔ以上であるため、復号値は“１”となる。また、範囲Ｒａｎｇｅは境界値ｓｐｌｉｔの１２７を減算した５５となる。また、符号値Ｖａｌｕｅは境界値ｓｐｌｉｔの１２７を減算した４１となる。
【００５７】
また、範囲Ｒａｎｇｅが１２８未満となったため、再正規化が発生する。再正規化により、範囲Ｒａｎｇｅは２倍の１１０となり、符号値Ｖａｌｕｅも２倍の８２となる。そして、ストリームデータ６１０から新たに読み出した１ビットは“１”となるため、符号値Ｖａｌｕｅは８３となる。
【００５８】
１回目の再正規化後の範囲Ｒａｎｇｅはまだ１２８未満であるため、２回目の再正規化が発生する。２回目の再正規化により、範囲Ｒａｎｇｅは２倍の２２０となり、符号値Ｖａｌｕｅも２倍の１６６となる。そして、ストリームデータ６１０から新たに読み出した１ビットは“１”となるため、符号値Ｖａｌｕｅは１６７となる。２回目の再正規化後の範囲Ｒａｎｇｅは１２８以上であるため、３回目の１ビット復号処理においてはこれ以上の再正規化は発生しない。
【００５９】
４回目の１ビット復号処理においては、範囲Ｒａｎｇｅが２２０であり、発生確率が２０４／２５６であるため、境界値ｓｐｌｉｔは１７５となる。したがって、符号値Ｖａｌｕｅの１６７は境界値ｓｐｌｉｔ未満であるため、復号値は“０”となる。また、以降の範囲Ｒａｎｇｅは境界値ｓｐｌｉｔの１７５となる。１〜４回目の１ビット復号処理により、復号値として“００１０”を得ることができる。
【００６０】
（Ｎビット復号処理）
図７は、Ｎビット復号処理の一例を示すフローチャートである。復号装置１００は、図４に示したステップＳ４０７におけるＮビット復号処理として、たとえば以下の各ステップを実行する。
【００６１】
まず、復号装置１００は、現在の範囲Ｒａｎｇｅおよび優勢シンボルの発生確率ｐｒｏｂに基づいて境界値ｓｐｌｉｔを算出する（ステップＳ７０１）。ステップＳ７０１における境界値ｓｐｌｉｔの算出は、図５に示したステップＳ５０１と同様である。
【００６２】
つぎに、復号装置１００は、復号値として優勢シンボルである“０”を出力する（ステップＳ７０２）。つぎに、復号装置１００は、範囲Ｒａｎｇｅに境界値ｓｐｌｉｔの値を設定する（ステップＳ７０３）。また、復号装置１００は、一括復号ビット数Ｎをデクリメント（−１）する（ステップＳ７０４）。つぎに、復号装置１００は、優勢シンボルの発生確率ｐｒｏｂを、次のビット位置の発生確率に更新する（ステップＳ７０５）。
【００６３】
つぎに、復号装置１００は、一括復号ビット数Ｎが０になったか否かを判断する（ステップＳ７０６）。一括復号ビット数Ｎが０になっていない場合（ステップＳ７０６：Ｎｏ）は、復号装置１００は、ステップＳ７０１へ戻る。一括復号ビット数Ｎが０になった場合（ステップＳ７０６：Ｙｅｓ）は、復号装置１００は一連の処理を終了する。以上の各ステップにより、Ｎビットの復号値“０”を得ることができる。
【００６４】
（一括復号ビット数Ｎの算出処理）
図８は、一括復号ビット数Ｎの算出処理の一例を示すフローチャートである。復号装置１００は、図４に示したステップＳ４０５における一括復号ビット数Ｎの算出処理として、たとえば以下の各ステップを実行する。図８に示す差分Ｄｉｆｆは、再正規化が発生し、または復号値が“１”となるまでの範囲Ｒａｎｇｅの余剰を示す値である。まず、復号装置１００は、現在の符号値Ｖａｌｕｅと再正規化の閾値である１２８を比較し、符号値Ｖａｌｕｅが１２８未満であるか否かを判断する（ステップＳ８０１）。
【００６５】
符号値Ｖａｌｕｅが１２８未満である場合は、復号処理を繰り返した場合に、復号値が“１”となる以前に再正規化が発生すると判断することができる。このため、ステップＳ８０１において符号値Ｖａｌｕｅが１２８未満である場合（ステップＳ８０１：Ｙｅｓ）は、復号装置１００は、差分Ｄｉｆｆに範囲Ｒａｎｇｅと１２８の差分を設定し（ステップＳ８０２）、ステップＳ８０４へ移行する。これにより、再正規化が発生するまでの範囲Ｒａｎｇｅの余剰を差分Ｄｉｆｆに設定することができる。
【００６６】
符号値Ｖａｌｕｅが１２８以上である場合は、復号処理を繰り返した場合に、再正規化が発生する以前に復号値が“１”となると判断することができる。このため、ステップＳ８０１において符号値Ｖａｌｕｅが１２８以上である場合（ステップＳ８０１：Ｎｏ）は、復号装置１００は、差分Ｄｉｆｆに範囲Ｒａｎｇｅと符号値Ｖａｌｕｅの差分を設定し（ステップＳ８０３）、ステップＳ８０４へ移行する。これにより、復号値が“１”となるまでの範囲Ｒａｎｇｅの余剰を差分Ｄｉｆｆに設定することができる。
【００６７】
つぎに、復号装置１００は、復号対象のシンタクスに対応するグループＩＤを対応情報３１０から取得する（ステップＳ８０４）。つぎに、復号装置１００は、ステップＳ８０４によって取得したグループＩＤに対応する最小の発生確率ｐｒｏｂＧ（グループＩＤ）を対応情報３２０から取得する（ステップＳ８０５）。
【００６８】
つぎに、復号装置１００は、復号処理を１回行うことによる範囲Ｒａｎｇｅの減少量の最大値である減少値ＳｕｂＶａｌを算出する（ステップＳ８０６）。具体的には、復号装置１００は、現在の範囲Ｒａｎｇｅに、ステップＳ８０５によって取得した発生確率ｐｒｏｂＧ（グループＩＤ）を８ビットシフトさせた値を乗算し、乗算結果を現在の範囲Ｒａｎｇｅから減算することで減少値ＳｕｂＶａｌを算出する。
【００６９】
つぎに、復号装置１００は、ステップＳ８０６により算出した減少値ＳｕｂＶａｌを除数とし、差分Ｄｉｆｆを被除数として除算した商を一括復号ビット数Ｎとして算出し（ステップＳ８０７）、一連の処理を終了する。以上の各ステップにより、復号値が“０”となりかつ再正規化が発生しない最小の復号処理の回数を一括復号ビット数Ｎとして算出することができる。
【００７０】
（Ｎビット復号処理）
図９は、Ｎビット復号処理の一例を示す図である。図９において、範囲Ｒａｎｇｅ１〜ＲａｎｇｅＮは、それぞれ１〜Ｎ回目の復号処理における範囲Ｒａｎｇｅを示している。境界値ｓｐｌｉｔ１〜ｓｐｌｉｔＮは、それぞれ１〜Ｎ回目の復号処理における境界値ｓｐｌｉｔを示している。発生確率ｐｒｏｂ１〜Ｎは、それぞれ１〜Ｎ回目の復号処理における“０”の発生確率ｐｒｏｂである。
【００７１】
図９に示すように、１〜Ｎ回目の復号処理において範囲Ｒａｎｇｅは範囲Ｒａｎｇｅ１〜ＲａｎｇｅＮのように減少していく。そして、Ｎ回目の復号処理の範囲ＲａｎｇｅＮまで範囲Ｒａｎｇｅが符号値Ｖａｌｕｅより大きければ、１〜Ｎ回目の復号処理における各復号値は“０”となる。また、Ｎ回目の復号処理の範囲ＲａｎｇｅＮまで範囲Ｒａｎｇｅが１２８（閾値）以上であれば、１〜Ｎ回目の復号処理において再正規化が発生しない。
【００７２】
すなわち、復号値がＮ回連続して“０”となる条件は範囲ＲａｎｇｅＮ＞Ｖａｌｕｅである。また、Ｎ回の復号処理において再正規化が発生しない条件は範囲ＲａｎｇｅＮ≧１２８である。したがって、範囲ＲａｎｇｅＮ＞Ｖａｌｕｅおよび範囲ＲａｎｇｅＮ≧１２８を満たす場合はＮビット復号処理が可能と判定する。一方、範囲ＲａｎｇｅＮ＞Ｖａｌｕｅおよび範囲ＲａｎｇｅＮ≧１２８のいずれか一方でも満たさない場合はＮビット復号処理は不可と判定することができる。
【００７３】
（復号装置の構成）
図１０は、復号装置の構成の一例を示す図である。図１０に示すように、復号装置１００は、シンタクス情報管理ＦＦ１００１と、確率テーブル部１００２と、Ｒａｎｇｅ＿ＦＦ１００３と、Ｖａｌｕｅ＿ＦＦ１００４と、一括復号ビット数算出部１００５と、１ビット復号処理部１００６と、Ｎビット復号処理部１００７と、ＭＵＸ１００８と、逆二値化部１００９と、次シンタクス判定部１０１０と、を備えている。復号装置１００の復号対象のデータストリームは１ビット復号処理部１００６へ入力される。
【００７４】
シンタクス情報管理ＦＦ１００１は、復号対象のシンタクスのステートマシンである。シンタクス情報管理ＦＦ１００１は、初期状態において、復号対象のシンタクスの初期値を示すシンタクス情報を出力する。また、シンタクス情報管理ＦＦ１００１は、次シンタクス判定部１０１０から次の復号対象のシンタクス情報が入力されると、入力されたシンタクス情報を出力する。シンタクス情報管理ＦＦ１００１から出力されたシンタクス情報は、確率テーブル部１００２、一括復号ビット数算出部１００５および逆二値化部１００９へ入力される。
【００７５】
確率テーブル部１００２は、シンタクスごとの“０”の発生確率ｐｒｏｂを示す確率テーブルを有する。確率テーブル部１００２は、シンタクス情報管理ＦＦ１００１から出力されたシンタクス情報が示すシンタクスに対応する発生確率ｐｒｏｂを確率テーブルから取得する。そして、確率テーブル部１００２は、取得した発生確率ｐｒｏｂを１ビット復号処理部１００６およびＮビット復号処理部１００７へ出力する。
【００７６】
Ｒａｎｇｅ＿ＦＦ１００３は、現在の範囲Ｒａｎｇｅのステートマシンである。Ｒａｎｇｅ＿ＦＦ１００３は、初期状態において、２５５を現在の範囲Ｒａｎｇｅとして出力する。また、Ｒａｎｇｅ＿ＦＦ１００３は、ＭＵＸ１００８からＮｅｗＲａｎｇｅ２またはＮｅｗＲａｎｇｅ１が入力されると、入力されたＮｅｗＲａｎｇｅ１またはＮｅｗＲａｎｇｅ２を現在の範囲Ｒａｎｇｅとして出力する。Ｒａｎｇｅ＿ＦＦ１００３から出力された範囲Ｒａｎｇｅは、一括復号ビット数算出部１００５、１ビット復号処理部１００６およびＮビット復号処理部１００７へ入力される。
【００７７】
Ｖａｌｕｅ＿ＦＦ１００４は、現在の符号値Ｖａｌｕｅのステートマシンである。Ｖａｌｕｅ＿ＦＦ１００４は、初期状態において、データストリームの先頭の８ビットを符号値Ｖａｌｕｅとして出力する。また、Ｖａｌｕｅ＿ＦＦ１００４は、１ビット復号処理部１００６からＮｅｗＶａｌｕｅが入力されると、入力されたＮｅｗＶａｌｕｅを現在の符号値Ｖａｌｕｅとして出力する。Ｖａｌｕｅ＿ＦＦ１００４から出力された符号値Ｖａｌｕｅは、一括復号ビット数算出部１００５、１ビット復号処理部１００６およびＮビット復号処理部１００７へ入力される。
【００７８】
一括復号ビット数算出部１００５は、シンタクス情報管理ＦＦ１００１からのシンタクス情報と、Ｒａｎｇｅ＿ＦＦ１００３からの範囲Ｒａｎｇｅと、Ｖａｌｕｅ＿ＦＦ１００４からの符号値Ｖａｌｕｅと、に基づいて一括復号ビット数Ｎを算出する。一括復号ビット数算出部１００５は、算出した一括復号ビット数Ｎを、Ｎビット復号処理部１００７、ＭＵＸ１００８および逆二値化部１００９へ出力する。一括復号ビット数算出部１００５の構成例については後述する（たとえば図１３参照）。
【００７９】
１ビット復号処理部１００６は、確率テーブル部１００２からの発生確率ｐｒｏｂと、Ｒａｎｇｅ＿ＦＦ１００３からの範囲Ｒａｎｇｅと、Ｖａｌｕｅ＿ＦＦ１００４からの符号値Ｖａｌｕｅと、に基づいてデータストリームの１ビット復号処理を行う。１ビット復号処理部１００６は、１ビット復号処理により得られた復号値（１／０）を逆二値化部１００９へ出力する。また、１ビット復号処理部１００６は、１ビット復号処理後の符号値ＶａｌｕｅをＮｅｗＶａｌｕｅとしてＶａｌｕｅ＿ＦＦ１００４へ出力する。また、１ビット復号処理部１００６は、１ビット復号処理後の範囲ＲａｎｇｅをＮｅｗＲａｎｇｅ１としてＭＵＸ１００８へ出力する。
【００８０】
Ｎビット復号処理部１００７には、確率テーブル部１００２からの発生確率ｐｒｏｂと、Ｒａｎｇｅ＿ＦＦ１００３からの範囲Ｒａｎｇｅと、が入力される。また、Ｎビット復号処理部１００７には、一括復号ビット数算出部１００５からの一括復号ビット数Ｎと、Ｖａｌｕｅ＿ＦＦ１００４からの符号値Ｖａｌｕｅと、が入力される。
【００８１】
Ｎビット復号処理部１００７は、入力された発生確率ｐｒｏｂ、範囲Ｒａｎｇｅ、一括復号ビット数Ｎおよび符号値Ｖａｌｕｅに基づいてデータストリームのＮビット復号処理を行う。また、Ｎビット復号処理部１００７は、Ｎビット復号処理後の範囲ＲａｎｇｅをＮｅｗＲａｎｇｅ２としてＭＵＸ１００８へ出力する。
【００８２】
また、Ｎビット復号処理部１００７は、ＮｅｗＲａｎｇｅ２＞符号値ＶａｌｕｅおよびＮｅｗＲａｎｇｅ２≧１２８の少なくともいずれかを満たさない場合にＮ＿ｂｉｔ＿ｅｒｒをＭＵＸ１００８および逆二値化部１００９へ出力してもよい。Ｎビット復号処理部１００７の構成例については後述する（たとえば図１２参照）。
【００８３】
ＭＵＸ１００８には、１ビット復号処理部１００６からのＮｅｗＲａｎｇｅ１と、Ｎビット復号処理部１００７からのＮｅｗＲａｎｇｅ２と、が入力される。ＭＵＸ１００８は、一括復号ビット数算出部１００５から出力された一括復号ビット数Ｎが０である場合は、１ビット復号処理部１００６からのＮｅｗＲａｎｇｅ１をＲａｎｇｅ＿ＦＦ１００３へ出力する。また、ＭＵＸ１００８は、一括復号ビット数算出部１００５から出力された一括復号ビット数Ｎが１以上である場合は、Ｎビット復号処理部１００７からのＮｅｗＲａｎｇｅ２をＲａｎｇｅ＿ＦＦ１００３へ出力する。
【００８４】
また、ＭＵＸ１００８は、Ｎビット復号処理部１００７からＮ＿ｂｉｔ＿ｅｒｒが出力された場合は、一括復号ビット数Ｎが１以上であっても１ビット復号処理部１００６からのＮｅｗＲａｎｇｅ１をＲａｎｇｅ＿ＦＦ１００３へ出力するようにしてもよい。これにより、Ｎビットを一括復号するとグループを跨いでしまう場合は、一括復号ビット数Ｎが１以上であっても１ビット復号結果を用いることができる。
【００８５】
逆二値化部１００９は、シンタクス情報管理ＦＦ１００１から出力されるシンタクス情報に基づいて復号値を逆二値化する。具体的には、一括復号ビット数算出部１００５から出力された一括復号ビット数Ｎが０である場合は、１ビット復号処理部１００６から出力された復号値を逆二値化する。また、逆二値化部１００９は、一括復号ビット数算出部１００５から出力された一括復号ビット数Ｎが１以上である場合は、一括復号ビット数Ｎだけ連続する“０”を復号値として逆二値化する。
【００８６】
逆二値化部１００９は、逆二値化したデータを復号データとして出力する。逆二値化部１００９から出力された復号データは、復号結果として復号装置１００から出力される。また、復号データは次シンタクス判定部１０１０へ入力される。また、逆二値化部１００９は、Ｎビット復号処理部１００７からＮ＿ｂｉｔ＿ｅｒｒが出力された場合は、一括復号ビット数Ｎが１以上であっても１ビット復号処理部１００６から出力された復号値を逆二値化してもよい。これにより、Ｎビットを一括復号するとグループを跨いでしまう場合は、一括復号ビット数Ｎが１以上であっても１ビット復号結果を用いることができる。
【００８７】
次シンタクス判定部１０１０は、逆二値化部１００９から出力された復号データに基づいて次の復号対象のシンタクスを判定する。次シンタクス判定部１０１０は、判定したシンタクスを示すシンタクス情報をシンタクス情報管理ＦＦ１００１へ出力する。
【００８８】
このように、マルチコンテキスト型の算術符号に対応する復号装置１００において、グループごとに一つの発生確率を用いて一括復号ビット数Ｎを算出することができる。これにより、一括復号ビット数Ｎを算出するためにＮビット復号処理部１００７と同等の回路を設けなくても、一括復号ビット数Ｎを算出することが可能になり、回路規模を小さくすることができる。
【００８９】
図１０に示したＲａｎｇｅ＿ＦＦ１００３は、範囲Ｒａｎｇｅ（数値範囲）を記憶する記憶部である。記憶部は、たとえば図２に示したメインメモリ２２０、補助メモリ２３０などによって実現してもよい。確率テーブル部１００２は、復号データの各位置における“０”（所定シンボル）の発生確率を取得する取得部である。取得部は、たとえば図２に示したＣＰＵ２１０、メインメモリ２２０、通信インタフェース２５０などによって実現してもよい。
【００９０】
一括復号ビット数算出部１００５は、確率テーブル部１００２で取得された発生確率のうちの、復号対象の位置が属するグループにおける最小の発生確率を特定する特定部である。また、一括復号ビット数算出部１００５は、特定した発生確率に相当する割合で範囲Ｒａｎｇｅを縮小した場合における範囲Ｒａｎｇｅの減少幅を算出する算出部である。また、一括復号ビット数算出部１００５は、範囲Ｒａｎｇｅの限界値と符号値Ｖａｌｕｅとの差分を、算出した減少幅によって除算した商を算出する除算部である。特定部、算出部および除算部は、たとえば図２に示したＣＰＵ２１０によって実現してもよい。
【００９１】
Ｎビット復号処理部１００７は、一括復号ビット数算出部１００５によって算出された商が１（所定値）以上である場合に、商だけ連続する“０”（所定シンボル）となる復号結果を出力する一括復号処理部である。一括復号処理部は、たとえば図２に示したＣＰＵ２１０によって実現してもよい。また、Ｎビット復号処理部１００７は、一括復号ビット数算出部１００５によって算出された商が１以上である場合に、減少幅に商を乗じた幅だけ範囲Ｒａｎｇｅを縮小する縮小部である。縮小部は、たとえば図２に示したＣＰＵ２１０によって実現してもよい。
【００９２】
１ビット復号処理部１００６は、一括復号ビット数算出部１００５によって算出された商が１未満である場合に、範囲Ｒａｎｇｅと、復号対象の位置における発生確率と、符号値Ｖａｌｕｅと、に基づいて復号対象の位置を復号する個別復号処理部である。個別復号処理部は、たとえば図２に示したＣＰＵ２１０によって実現してもよい。また、１ビット復号処理部１００６は、復号結果と、復号対象の位置における発生確率と、に応じて範囲Ｒａｎｇｅを縮小する縮小部である。また、１ビット復号処理部１００６は、縮小した範囲Ｒａｎｇｅの限界値が１２８（閾値）を下回った場合に、範囲Ｒａｎｇｅおよび符号値Ｖａｌｕｅを同一比率で増大させる再正規化を行う再正規化部である。再正規化部は、たとえば図２に示したＣＰＵ２１０によって実現してもよい。
【００９３】
（１ビット復号処理部の構成）
図１１は、１ビット復号処理部の構成の一例を示す図である。図１１に示すように、１ビット復号処理部１００６は、減算部１１０１と、乗算部１１０２と、シフト部１１０３と、加算部１１０４と、減算部１１０５，１１０６と、比較部１１０７と、ＭＵＸ１１０８，１１０９と、再正規化制御部１１１０と、シフト部１１１１，１１１２と、シフト部１１１３と、ＯＲ部１１１４と、を備えている。
【００９４】
データストリームは、シフト部１１１３へ入力される。確率テーブル部１００２（図１０参照）からの発生確率ｐｒｏｂは、乗算部１１０２へ入力される。Ｒａｎｇｅ＿ＦＦ１００３（図１０参照）からの範囲Ｒａｎｇｅは、減算部１１０１および減算部１１０５へ出力される。Ｖａｌｕｅ＿ＦＦ１００４（図１０参照）からの符号値Ｖａｌｕｅは、減算部１１０６、比較部１１０７およびＭＵＸ１１０９へ出力される。
【００９５】
減算部１１０１は、Ｒａｎｇｅ＿ＦＦ１００３からの範囲Ｒａｎｇｅを１で減算し、減算結果を乗算部１１０２へ出力する。乗算部１１０２は、確率テーブル部１００２からの発生確率ｐｒｏｂと、減算部１１０１から出力された値と、を乗算する。乗算部１１０２は、乗算結果をシフト部１１０３へ出力する。
【００９６】
シフト部１１０３は、乗算部１１０２から出力された値を８ビットシフトさせ、８ビットシフトさせた値を加算部１１０４へ出力する。加算部１１０４は、シフト部１１０３から出力された値に１を加算し、加算結果を境界値ｓｐｌｉｔとして出力する。加算部１１０４から出力された境界値ｓｐｌｉｔは、減算部１１０５，１１０６、比較部１１０７およびＭＵＸ１１０８へ入力される。
【００９７】
減算部１１０５は、Ｒａｎｇｅ＿ＦＦ１００３からの範囲Ｒａｎｇｅから、加算部１１０４から出力された境界値ｓｐｌｉｔを減算し、減算結果をＭＵＸ１１０８へ出力する。減算部１１０６は、Ｖａｌｕｅ＿ＦＦ１００４からの符号値Ｖａｌｕｅから、加算部１１０４から出力された境界値ｓｐｌｉｔを減算し、減算結果をＭＵＸ１１０８へ出力する。
【００９８】
比較部１１０７は、Ｖａｌｕｅ＿ＦＦ１００４からの符号値Ｖａｌｕｅと、加算部１１０４から出力された境界値ｓｐｌｉｔと、を比較し、符号値Ｖａｌｕｅが境界値ｓｐｌｉｔ以上であるか否かを判断する。比較部１１０７は、符号値Ｖａｌｕｅが境界値ｓｐｌｉｔ以上である場合は“１”を出力し、符号値Ｖａｌｕｅが境界値ｓｐｌｉｔ未満である場合は“０”を出力する。比較部１１０７から出力された値はＭＵＸ１１０８，１１０９へ出力される。また、比較部１１０７から出力された値は、１ビット復号処理による復号値（１／０）として逆二値化部１００９（図１０参照）へ出力される。
【００９９】
ＭＵＸ１１０８は、比較部１１０７から“１”が出力された場合は減算部１１０５から出力された値を範囲Ｒａｎｇｅとして出力する。また、ＭＵＸ１１０８は、比較部１１０７から“０”が出力された場合は加算部１１０４から出力された境界値ｓｐｌｉｔを範囲Ｒａｎｇｅとして出力する。ＭＵＸ１１０８から出力された範囲Ｒａｎｇｅは再正規化制御部１１１０およびシフト部１１１１へ出力される。
【０１００】
ＭＵＸ１１０９は、比較部１１０７から“１”が出力された場合は減算部１１０６からの値を符号値Ｖａｌｕｅとして出力する。また、ＭＵＸ１１０９は、比較部１１０７から“０”が出力された場合はＶａｌｕｅ＿ＦＦ１００４からの符号値Ｖａｌｕｅを出力する。ＭＵＸ１１０９から出力された符号値Ｖａｌｕｅはシフト部１１１２へ出力される。
【０１０１】
再正規化制御部１１１０（Ｒｅｎｏｒｍ：Ｒｅｎｏｒｍａｌｉｚａｔｉｏｎ）は、ＭＵＸ１１０８から出力された範囲Ｒａｎｇｅに基づいて、再正規化を実行する回数を算出する。たとえば再正規化の閾値が１２８である場合は、再正規化制御部１１１０は、１２８を範囲Ｒａｎｇｅで除算した商を再正規化を実行する回数として算出する。再正規化制御部１１１０は、算出した回数をシフト量としてシフト部１１１１，１１１２およびシフト部１１１３へ出力する。
【０１０２】
シフト部１１１１は、ＭＵＸ１１０８から出力された範囲Ｒａｎｇｅを、再正規化制御部１１１０から出力されたシフト量（ビット数）だけシフトさせる。シフト部１１１１は、シフトさせた範囲ＲａｎｇｅをＮｅｗＲａｎｇｅ１としてＲａｎｇｅ＿ＦＦ１００３（図１０参照）へ出力する。シフト部１１１２は、ＭＵＸ１１０９から出力された符号値Ｖａｌｕｅを、再正規化制御部１１１０から出力されたシフト量（ビット数）だけシフトさせ、シフトさせた符号値ＶａｌｕｅをＯＲ部１１１４へ出力する。
【０１０３】
シフト部１１１３は、入力されたビットストリームを、再正規化制御部１１１０から出力されたシフト量（ビット数）だけ読み出す。そして、シフト部１１１３は、読み出したビットをＯＲ部１１１４へ出力する。ＯＲ部１１１４は、シフト部１１１２から出力された符号値Ｖａｌｕｅと、シフト部１１１３から出力されたビットと、の和をＮｅｗＶａｌｕｅとしてＶａｌｕｅ＿ＦＦ１００４（図１０参照）へ出力する。
【０１０４】
（Ｎビット復号装置の構成）
図１２は、Ｎビット復号装置の構成の一例を示す図である。図１２に示すように、Ｎビット復号処理部１００７は、Ｍ個（Ｍ≧Ｎ）のＭＵＸ１２１１〜１２１Ｍと、Ｍ個の境界値算出部１２２１〜１２２Ｍと、範囲チェック部１２３０と、を備えている。
【０１０５】
ＭＵＸ１２１１〜１２１Ｍには、それぞれ発生確率ｐｒｏｂ＿１〜ｐｒｏｂ＿Ｍが入力される。発生確率ｐｒｏｂ＿１〜ｐｒｏｂ＿Ｍは、それぞれ１〜Ｍビット目における“０”の発生確率ｐｒｏｂである。また、ＭＵＸ１２１１〜１２１Ｍには、それぞれ２５６の値が入力される。また、ＭＵＸ１２１１〜１２１Ｍには、一括復号ビット数算出部１００５から出力された一括復号ビット数Ｎが入力される。
【０１０６】
ＭＵＸ１２１１〜１２１Ｍのうちの１〜Ｎ番目のＭＵＸ１２１１〜１２１Ｎは、それぞれ入力された発生確率ｐｒｏｂ＿１〜ｐｒｏｂ＿Ｎを発生確率ｐｒｏｂとしてそれぞれ境界値算出部１２２１〜１２２Ｎへ出力する。一方、ＭＵＸ１２１１〜１２１ＭのうちのＮ＋１〜Ｍ番目のＭＵＸ１２１（Ｎ＋１）〜１２１Ｍは、入力された２５６を発生確率ｐｒｏｂとしてそれぞれ境界値算出部１２２（Ｎ＋１）〜１２２Ｍへ出力する。
【０１０７】
境界値算出部１２２１は、Ｒａｎｇｅ＿ＦＦ１００３から出力された範囲Ｒａｎｇｅと、ＭＵＸ１２１１から出力された発生確率ｐｒｏｂと、に基づいて１ビット目の復号処理後の境界値ｓｐｌｉｔを算出する。境界値算出部１２２１は、算出した境界値ｓｐｌｉｔを境界値算出部１２２２へ出力する。
【０１０８】
境界値算出部１２２２は、境界値算出部１２２１から出力された境界値ｓｐｌｉｔを範囲Ｒａｎｇｅとし、ＭＵＸ１２１２から出力された発生確率ｐｒｏｂに基づいて２ビット目の復号処理後の境界値ｓｐｌｉｔを算出する。境界値算出部１２２２は、算出した境界値ｓｐｌｉｔを境界値算出部１２２３へ出力する。
【０１０９】
同様に、境界値算出部１２２３〜１２２Ｍは、前段の境界値算出部から出力された境界値ｓｐｌｉｔを範囲Ｒａｎｇｅとし、ＭＵＸ１２１３〜１２１Ｍから出力された発生確率ｐｒｏｂに基づいて３〜Ｍビット目の復号処理後の境界値ｓｐｌｉｔを算出する。
【０１１０】
ここで、境界値算出部１２２（Ｎ＋１）〜１２２Ｍは、入力される発生確率が２５６となっているため、前段の境界値算出部から出力された境界値ｓｐｌｉｔを変更せずに後段の境界値算出部へ出力することになる。このように、境界値算出部１２２１〜１２２Ｍの前段で入力を選択しておくことにより、後段に必要とされる境界値算出部ごとの比較器と、比較結果をまとめるプライオリティエンコーダ、その出力によって最終データの選択を行うＭｔｏ１セレクタが不要となるため、Ｎビット復号処理部１００７における一括復号処理を高速化することができる。境界値算出部１２２Ｍから出力された境界値ｓｐｌｉｔは、ＮｅｗＲａｎｇｅ２としてＭＵＸ１００８（図１０参照）へ出力されるとともに範囲チェック部１２３０へ入力される。
【０１１１】
範囲チェック部１２３０には、Ｖａｌｕｅ＿ＦＦ１００４（図１０参照）からの符号値Ｖａｌｕｅと、１２８の値と、境界値算出部１２２Ｍからの境界値ｓｐｌｉｔと、が入力される。範囲チェック部１２３０は、ＮｅｗＲａｎｇｅ２＞符号値ＶａｌｕｅおよびＮｅｗＲａｎｇｅ２≧１２８を満たす場合はＮ＿ｂｉｔ＿ｅｒｒを出力しない。また、範囲チェック部１２３０は、ＮｅｗＲａｎｇｅ２＞符号値ＶａｌｕｅおよびＮｅｗＲａｎｇｅ２≧１２８の少なくともいずれかを満たさない場合はＮ＿ｂｉｔ＿ｅｒｒを出力する。範囲チェック部１２３０から出力されたＮ＿ｂｉｔ＿ｅｒｒは、ＭＵＸ１００８および逆二値化部１００９（図１０参照）へ出力される。
【０１１２】
（一括復号ビット数算出部の構成）
図１３は、一括復号ビット数算出部の構成の一例を示す図である。図１３に示すように、一括復号ビット数算出部１００５は、比較部１３０１と、減算部１３０２、減算部１３０３と、ＭＵＸ１３０４と、グループＩＤ＿ＬＵＴ部１３０５と、ｐｒｏｂＧ＿ＬＵＴ部１３０６と、乗算部１３０７と、シフト部１３０８と、減算部１３０９と、除算部１３１０と、を備えている。
【０１１３】
比較部１３０１は、Ｖａｌｕｅ＿ＦＦ１００４から出力された符号値Ｖａｌｕｅと、１２８の値と、を比較する。比較部１３０１は、比較結果をＭＵＸ１３０４へ出力する。減算部１３０２は、Ｒａｎｇｅ＿ＦＦ１００３から出力された範囲Ｒａｎｇｅから、１２８の値を減算する。減算部１３０２は、減算結果をＭＵＸ１３０４へ出力する。減算部１３０３は、Ｒａｎｇｅ＿ＦＦ１００３から出力された範囲Ｒａｎｇｅから、Ｖａｌｕｅ＿ＦＦ１００４から出力された符号値を減算する。減算部１３０３は、減算結果をＭＵＸ１３０４へ出力する。
【０１１４】
ＭＵＸ１３０４は、符号値Ｖａｌｕｅが１２８未満である旨の比較結果が比較部１３０１から出力された場合は、減算部１３０２から出力された減算結果を差分Ｄｉｆｆとして出力する。また、ＭＵＸ１３０４は、符号値Ｖａｌｕｅが１２８以上である旨の比較結果が比較部１３０１から出力された場合は、減算部１３０３から出力された減算結果を差分Ｄｉｆｆとして除算部１３１０へ出力する。
【０１１５】
グループＩＤ＿ＬＵＴ部１３０５（Ｌｏｏｋ Ｕｐ Ｔａｂｌｅ：ルックアップテーブル）は、シンタクスとグループＩＤとの対応情報（たとえば図３−１の対応情報３１０）を記憶している。グループＩＤ＿ＬＵＴ部１３０５は、シンタクス情報管理ＦＦ１００１から出力されたシンタクス情報が示すシンタクスに対応するグループＩＤを対応情報から取得し、取得したグループＩＤをｐｒｏｂＧ＿ＬＵＴ部１３０６へ出力する。
【０１１６】
ｐｒｏｂＧ＿ＬＵＴ部１３０６は、グループＩＤと発生確率ｐｒｏｂＧとの対応情報（たとえば図３−２の対応情報３２０）を記憶している。ｐｒｏｂＧ＿ＬＵＴ部１３０６は、グループＩＤ＿ＬＵＴ部１３０５から出力されたグループＩＤが示すシンタクスに対応する最小の発生確率ｐｒｏｂＧ（グループＩＤ）を対応情報から取得し、取得した発生確率ｐｒｏｂＧ（グループＩＤ）を乗算部１３０７へ出力する。
【０１１７】
乗算部１３０７は、Ｒａｎｇｅ＿ＦＦ１００３から出力された範囲Ｒａｎｇｅと、ｐｒｏｂＧ＿ＬＵＴ部１３０６から出力された発生確率ｐｒｏｂＧ（グループＩＤ）と、を乗算する。乗算部１３０７は、乗算結果をシフト部１３０８へ出力する。シフト部１３０８は、乗算部１３０７から出力された値を８ビットシフトさせる。シフト部１３０８は、８ビットシフトさせた値を減算部１３０９へ出力する。
【０１１８】
減算部１３０９は、Ｒａｎｇｅ＿ＦＦ１００３から出力された範囲Ｒａｎｇｅを、シフト部１３０８から出力された値で減算する。減算部１３０９は、減算結果を減少値ＳｕｂＶａｌとして除算部１３１０へ出力する。除算部１３１０は、ＭＵＸ１３０４から出力された差分Ｄｉｆｆを、減算部１３０９から出力された減少値ＳｕｂＶａｌで除算する。除算部１３１０は、除算結果の商を一括復号ビット数Ｎとして出力する。
【０１１９】
このように、実施の形態１にかかる復号装置１００によれば、優勢シンボルの発生確率をグループ分けし、復号対象が属するグループの最小の発生確率に基づいて優勢シンボルの連続数を算出し、算出結果に基づいて一括復号を行うことができる。これにより、一括復号の実施確率を高くし、復号処理の高速化の確率を高めることができる。
【０１２０】
（実施の形態２）
実施の形態２においては、実施の形態１と異なる部分について説明する。
【０１２１】
（グループＩＤと減少値の対応情報）
図１４は、グループＩＤと減少値の対応情報の一例を示す図である。図１４に示す対応情報１４００は、グループＩＤと減少値とを対応付ける対応情報である。対応情報１４００は、たとえば復号装置１００のメインメモリ２２０や補助メモリ２３０に記憶されている。対応情報１４００に示す最大の減少値ＳｕｂＶａｌＧ（０）〜ＳｕｂＶａｌＧ（Ｙ）は、それぞれグループＩＤ「０」〜「Ｙ」が示すグループに属する各シンタクスの復号処理において、範囲Ｒａｎｇｅの最大の減少値ＳｕｂＶａｌを示している。
【０１２２】
実施の形態１においては、図８に示したように、復号処理ごとに変化する範囲Ｒａｎｇｅ（≦２５５）に基づいて減少値ＳｕｂＶａｌが算出される。これに対して、実施の形態２においては、範囲Ｒａｎｇｅが常に２５５であると仮定して減少値ＳｕｂＶａｌＧ（０）〜ｐｒｏｂＧ（Ｙ）が予め算出され、対応情報１４００として記憶されている。この場合は、図３−２に示した対応情報３２０は復号装置１００に記憶されていなくてもよい。このように、実施の形態２においては、シンボル発生確率ではなく、数直線幅に換算した値を直接設定しておく。
【０１２３】
（一括復号ビット数Ｎの算出処理）
図１５は、一括復号ビット数Ｎの算出処理の一例を示すフローチャートである。実施の形態２にかかる復号装置１００は、図４に示したステップＳ４０５における一括復号ビット数Ｎの算出処理として、たとえば図１５に示す各ステップを実行する。
【０１２４】
図１５に示すステップＳ１５０１〜Ｓ１５０４は、図８に示したステップＳ８０１〜Ｓ８０４と同様である。ステップＳ１５０４のつぎに、復号装置１００は、ステップＳ１５０４によって取得したグループＩＤに対応する減少値ＳｕｂＶａｌＧ（グループＩＤ）を減少値ＳｕｂＶａｌとして対応情報１４００から取得する（ステップＳ１５０５）。
【０１２５】
つぎに、復号装置１００は、ステップＳ１５０５により算出した減少値ＳｕｂＶａｌを除数とし、差分Ｄｉｆｆを被除数として除算した商をＮとして算出し（ステップＳ１５０６）、一連の処理を終了する。これにより、復号値が“０”となりかつ再正規化が発生しない最小の復号処理の回数をＮとして算出することができる。
【０１２６】
また、対応情報１４００を用いることで、復号処理ごとに減少値ＳｕｂＶａｌを算出しなくても一括復号ビット数Ｎを算出することができるため、計算量を少なくすることができる。なお、実施の形態２においては、現在の範囲Ｒａｎｇｅに基づく減少値ＳｕｂＶａｌの算出を行わず、範囲Ｒａｎｇｅの最大値に基づく減少値ＳｕｂＶａｌを用いるため、実施の形態１に比べて一括復号ビット数Ｎが小さくなる傾向となる。
【０１２７】
（実施の形態２にかかる一括復号ビット数算出部の構成）
図１６は、実施の形態２にかかる一括復号ビット数算出部の構成の一例を示す図である。図１６において、図１３に示した部分と同様の部分については同一の符号を付して説明を省略する。図１６に示すように、実施の形態２にかかる一括復号ビット数算出部１００５は、対応情報１４００を用いることで復号対象の位置が属するグループに対応する減少幅を導出する導出部である。具体的には、実施の形態２にかかる一括復号ビット数算出部１００５は、図１３に示したｐｒｏｂＧ＿ＬＵＴ部１３０６、乗算部１３０７、シフト部１３０８および減算部１３０９に代えてＳｕｂＶａｌ＿ＬＵＴ部１６０１を備えている。
【０１２８】
ＳｕｂＶａｌ＿ＬＵＴ部１６０１は、グループＩＤと減少値ｐｒｏｂＧとの対応情報（たとえば図１４に示した対応情報１４００）を記憶している。ＳｕｂＶａｌ＿ＬＵＴ部１６０１は、シンタクス情報管理ＦＦ１００１から出力されたシンタクス情報が示すシンタクスに対応する減少値ＳｕｂＶａｌＧ（グループＩＤ）を対応情報から取得する。そして、ＳｕｂＶａｌ＿ＬＵＴ部１６０１は、取得した減少値ＳｕｂＶａｌＧ（グループＩＤ）を減少値ＳｕｂＶａｌとして除算部１３１０へ出力する。
【０１２９】
除算部１３１０は、ＭＵＸ１３０４から出力された差分Ｄｉｆｆを、ＳｕｂＶａｌ＿ＬＵＴ部１６０１から出力された減少値ＳｕｂＶａｌで除算する。除算部１３１０は、除算結果の商を一括復号ビット数Ｎとして出力する。
【０１３０】
このように、対応情報１４００を用いることで、復号処理ごとに減少値ＳｕｂＶａｌを算出しなくても一括復号ビット数Ｎを算出することができるため、一括復号ビット数算出部１００５の回路規模を小さくすることができる。
【０１３１】
このように、実施の形態２にかかる復号装置１００においては、グループごとに、グループにおける最小の発生確率に相当する割合で範囲Ｒａｎｇｅを縮小した場合における範囲Ｒａｎｇｅの減少幅が対応付けられた対応情報１４００を用意しておく。そして、復号装置１００は、対応情報１４００を用いることで、復号対象の位置が属するグループに対応する減少幅を導出する。これにより、復号処理ごとに減少値を算出しなくても一括復号ビット数Ｎを算出することができるため、計算量を少なくすることができる。
【０１３２】
（符号化処理）
図１７は、符号化処理の一例を示すフローチャートである。復号装置１００の復号対象のビットストリームを生成する符号化装置は、たとえば以下の各ステップを実行する。図１７において、下限値ｌｏｗｖａｌｕｅは範囲Ｒａｎｇｅの下限値である。下限値ｌｏｗｖａｌｕｅの初期値は０とする。範囲Ｒａｎｇｅの初期値は２５５とする。カウント値ｃｏｕｎｔの初期値は０とする。まず、符号化装置は、現在の範囲Ｒａｎｇｅと、符号化対象の１ビットにおける優勢シンボルの発生確率ｐｒｏｂに基づいて境界値ｓｐｌｉｔを算出する（ステップＳ１７０１）。
【０１３３】
つぎに、符号化装置は、符号化対象の値が“１”であるか否かを判断する（ステップＳ１７０２）。符号化対象の値が“１”である場合（ステップＳ１７０２：Ｙｅｓ）は、符号化装置は、ステップＳ１７０１によって算出した境界値ｓｐｌｉｔを下限値ｌｏｗｖａｌｕｅに加算する（ステップＳ１７０３）。また、符号化装置は、ステップＳ１７０１によって算出した境界値ｓｐｌｉｔを範囲Ｒａｎｇｅから減算し（ステップＳ１７０４）、ステップＳ１７０６へ移行する。
【０１３４】
ステップＳ１７０２において、符号化対象の値が“１”でない場合（ステップＳ１７０２：Ｎｏ）は、符号化装置は、ステップＳ１７０１によって算出した境界値ｓｐｌｉｔを範囲Ｒａｎｇｅに設定し（ステップＳ１７０５）、ステップＳ１７０６へ移行する。
【０１３５】
つぎに、符号化装置は、範囲Ｒａｎｇｅが１２８未満であるか否かを判断する（ステップＳ１７０６）。範囲Ｒａｎｇｅが１２８以上である場合（ステップＳ１７０６：Ｎｏ）は、符号化装置は、一連の処理を終了する。範囲Ｒａｎｇｅが１２８未満である場合（ステップＳ１７０６：Ｙｅｓ）は、符号化装置は、再正規化処理を実行し（ステップＳ１７０７）、一連の処理を終了する。ステップＳ１７０７による再正規化処理については後述する（たとえば図１８参照）。
【０１３６】
図１８は、符号化処理における再正規化処理の一例を示すフローチャートである。符号化装置は、図１７に示したステップＳ１７０７による再正規化処理として、たとえば図１７に示す各ステップを実行する。まず、符号化装置は、範囲Ｒａｎｇｅが１２８以上か否かを判断する（ステップＳ１８０１）。
【０１３７】
ステップＳ１８０１において、範囲Ｒａｎｇｅが１２８以上である場合（ステップＳ１８０１：Ｙｅｓ）は、符号化装置は、下限値ｌｏｗｖａｌｕｅが１２８未満であるか否かを判断する（ステップＳ１８０２）。下限値ｌｏｗｖａｌｕｅが１２８未満である場合（ステップＳ１８０２：Ｙｅｓ）は、符号化装置は、引数ｘを“０”とするライト処理を実行し（ステップＳ１８０３）、ステップＳ１８０９へ移行する。ライト処理については後述する（たとえば図１９参照）。
【０１３８】
ステップＳ１８０２において、下限値ｌｏｗｖａｌｕｅが１２８以上である場合（ステップＳ１８０２：Ｎｏ）は、符号化装置は、下限値ｌｏｗｖａｌｕｅが２５６以上であるか否かを判断する（ステップＳ１８０４）。下限値ｌｏｗｖａｌｕｅが２５６未満である場合（ステップＳ１８０４：Ｎｏ）は、符号化装置は、下限値ｌｏｗｖａｌｕｅから１２８を減算する（ステップＳ１８０５）。また、符号化装置は、カウント値ｃｏｕｎｔに１を加算し（ステップＳ１８０６）、ステップＳ１８０９へ移行する。
【０１３９】
ステップＳ１８０４において、下限値ｌｏｗｖａｌｕｅが２５６以上である場合（ステップＳ１８０４：Ｙｅｓ）は、符号化装置は、下限値ｌｏｗｖａｌｕｅから２５６を減算する（ステップＳ１８０７）。つぎに、符号化装置は、引数ｘを“１”とするライト処理を実行し（ステップＳ１８０８）、ステップＳ１８０９へ移行する。ライト処理については後述する（たとえば図１９参照）。
【０１４０】
つぎに、符号化装置は、範囲Ｒａｎｇｅを１ビット左シフトさせる（ステップＳ１８０９）。また、符号化装置は、下限値ｌｏｗｖａｌｕｅを１ビット左シフトさせ（ステップＳ１８１０）、ステップＳ１８０１へ戻る。ステップＳ１８０１において、範囲Ｒａｎｇｅが１２８未満である場合（ステップＳ１８０１：Ｎｏ）は、符号化装置は、一連の再正規化処理を終了する。
【０１４１】
図１９は、再正規化処理におけるライト処理の一例を示すフローチャートである。符号化装置は、図１８のステップＳ１８０３，Ｓ１８０８におけるライト処理として、図１９に示す各ステップを実行する。まず、符号化装置は、ＦｉｒｓｔＦｌａｇが０であるか否かを判断する（ステップＳ１９０１）。ＦｉｒｓｔＦｌａｇが０である場合（ステップＳ１９０１：Ｙｅｓ）は、符号化装置は、ＦｉｒｓｔＦｌａｇに０を設定し（ステップＳ１９０２）、ステップＳ１９０４へ移行する。
【０１４２】
ステップＳ１９０１において、ＦｉｒｓｔＦｌａｇが０でない場合（ステップＳ１９０１：Ｎｏ）は、符号化装置は、符号値として引数“ｘ”を出力し（ステップＳ１９０３）、ステップＳ１９０４へ移行する。つぎに、符号化装置は、カウント値ｃｏｕｎｔが０より大きいか否かを判断する（ステップＳ１９０４）。
【０１４３】
ステップＳ１９０４において、カウント値ｃｏｕｎｔが０より大きい場合（ステップＳ１９０４：Ｙｅｓ）は、符号化装置は、符号値として引数“１−ｘ”を出力する（ステップＳ１９０５）。また、符号化装置は、カウント値ｃｏｕｎｔをデクリメント（−１）し（ステップＳ１９０６）、ステップＳ１９０４へ戻る。ステップＳ１９０４において、カウント値ｃｏｕｎｔが０より大きくない場合（ステップＳ１９０４：Ｎｏ）は、符号化装置は、一連の処理を終了する。
【０１４４】
（符号化の具体例）
ここでは、符号化対象の最初のシンタクスがＳｙｎｔａｘＡ（８ビット）であり、ＳｙｎｔａｘＡの次のシンタクスがＳｙｎｔａｘＢ（８ビット）であるとする。ＳｙｎｔａｘＡの各ビット位置ｋにおける“０”の発生確率は、ＰｒｏｂＴａｂｌｅＡ［ｋ］＝｛２１７，２２３，２４５，２４５，２４４，２４２，２４４，２４５｝とする。ＳｙｎｔａｘＢの各ビット位置ｋにおける“０”の発生確率は、ＰｒｏｂＴａｂｌｅＢ［ｋ］＝｛２３４，２５１，２４４，２５４，２１６，１９９，１７９，２３３｝とする。ｓｐｌｉｔ計算式には下記（１）式を用いるとする。
【０１４５】
ｓｐｌｉｔ＝１＋（（（Ｒａｎｇｅ−１）＊ｐｒｏｂ）＞＞８） …（１）
【０１４６】
また、たとえばＳｙｎｔａｘＡ＝“００００００１０”とする。ＳｙｎｔａｘＡのビット位置０（０）の符号化は下記（２）式のようになる。
【０１４７】
ｓｐｌｉｔ＝１＋（（（２５５−１）＊２１７）＞＞８）＝２１６
Ｒａｎｇｅ＝ｓｐｌｉｔ＝２１６ …（２）
【０１４８】
ＳｙｎｔａｘＡのビット位置１（０）の符号化は下記（３）式のようになる。
【０１４９】
ｓｐｌｉｔ＝１＋（（（２１６−１）＊２２３）＞＞８）＝１８８
Ｒａｎｇｅ＝ｓｐｌｉｔ＝１８８ …（３）
【０１５０】
ＳｙｎｔａｘＡのビット位置２（０）の符号化は下記（４）式のようになる。
【０１５１】
ｓｐｌｉｔ＝１＋（（（１８８−１）＊２４５）＞＞８）＝１７９
Ｒａｎｇｅ＝ｓｐｌｉｔ＝１７９ …（４）
【０１５２】
ＳｙｎｔａｘＡのビット位置３（０）の符号化は下記（５）式のようになる。
【０１５３】
ｓｐｌｉｔ＝１＋（（（１７９−１）＊２４５）＞＞８）＝１７１
Ｒａｎｇｅ＝ｓｐｌｉｔ＝１７１ …（５）
【０１５４】
ＳｙｎｔａｘＡのビット位置４（０）の符号化は下記（６）式のようになる。
【０１５５】
ｓｐｌｉｔ＝１＋（（（１７１−１）＊２４４）＞＞８）＝１６３
Ｒａｎｇｅ＝ｓｐｌｉｔ＝１６３ …（６）
【０１５６】
ＳｙｎｔａｘＡのビット位置５（０）の符号化は下記（７）式のようになる。
【０１５７】
ｓｐｌｉｔ＝１＋（（（１６３−１）＊２４２）＞＞８）＝１５４
Ｒａｎｇｅ＝ｓｐｌｉｔ＝１５４ …（７）
【０１５８】
ＳｙｎｔａｘＡのビット位置６（１）の符号化は下記（８）式のようになる。
【０１５９】
ｓｐｌｉｔ＝１＋（（（１５４−１）＊２４４）＞＞８）＝１４６
ｌｏｗｖａｌｕｅ＋＝ｓｐｌｉｔ＝１４６
Ｒａｎｇｅ＝Ｒａｎｇｅ−ｓｐｌｉｔ＝８ …（８）
【０１６０】
ここで、範囲Ｒａｎｇｅが１２８未満となったため、１ビット正規化処理が発生し、下記（９）式のようになる。
【０１６１】
ｃｏｕｎｔ＝ｃｏｕｎｔ＋１＝１
ｌｏｗｖａｌｕｅ＝ｌｏｗｖａｌｕｅ−１２８＝１８
Ｒａｎｇｅ＝Ｒａｎｇｅ＜＜１＝１６
ｌｏｗｖａｌｕｅ＝ｌｏｗｖａｌｕｅ＜＜１＝３６ …（９）
【０１６２】
範囲Ｒａｎｇｅが１２８未満のままであるため、さらに１ビット正規化処理が発生し、下記（１０）式のようになる。また、ｃｏｕｎｔ＝１により符号値“１”が出力される。
【０１６３】
ｃｏｕｎｔ＝ｃｏｕｎｔ−１＝０
Ｒａｎｇｅ＝Ｒａｎｇｅ＜＜１＝３２
ｌｏｗｖａｌｕｅ＝ｌｏｗｖａｌｕｅ＜＜１＝７２ …（１０）
【０１６４】
範囲Ｒａｎｇｅが１２８未満のままであるため、さらに１ビット正規化処理が発生し、下記（１１）式のようになる。また、ｃｏｕｎｔ＝０により符号値“０”が出力される。
【０１６５】
Ｒａｎｇｅ＝Ｒａｎｇｅ＜＜１＝６４
ｌｏｗｖａｌｕｅ＝ｌｏｗｖａｌｕｅ＜＜１＝１４４ …（１１）
【０１６６】
範囲Ｒａｎｇｅが１２８未満のままであるため、さらに１ビット正規化処理が発生し、下記（１２）式のようになる。また、ｃｏｕｎｔ＝０により符号値“０”が出力される。
【０１６７】
ｃｏｕｎｔ＝ｃｏｕｎｔ＋１＝１
ｌｏｗｖａｌｕｅ＝ｌｏｗｖａｌｕｅ−１２８＝１６
Ｒａｎｇｅ＝Ｒａｎｇｅ＜＜１＝１２８
ｌｏｗｖａｌｕｅ＝ｌｏｗｖａｌｕｅ＜＜１＝３２ …（１２）
【０１６８】
範囲Ｒａｎｇｅが１２８以上となったため、ＳｙｎｔａｘＡのビット位置７（０）の符号化が実行される。ＳｙｎｔａｘＡのビット位置７（０）の符号化は下記（１３）式のようになる。
【０１６９】
ｓｐｌｉｔ＝１＋（（（１２８−１）＊２４５）＞＞８）＝１２２
Ｒａｎｇｅ＝ｓｐｌｉｔ＝１２２ …（１３）
【０１７０】
範囲Ｒａｎｇｅが１２８未満となったため、１ビット正規化処理が発生し、下記（１４）式のようになる。また、ｃｏｕｎｔ＝１により符号値“１”が出力される。
【０１７１】
ｃｏｕｎｔ＝ｃｏｕｎｔ−１＝０
Ｒａｎｇｅ＝Ｒａｎｇｅ＜＜１＝２４４
ｌｏｗｖａｌｕｅ＝ｌｏｗｖａｌｕｅ＜＜１＝６４ …（１４）
【０１７２】
これにより、ＳｙｎｔａｘＡを符号化した時点で符号値“１００１”までが確定したこととなる。以下、ＳｙｎｔａｘＢ以降も同様の処理を行い、符号値“１００１＿００１０＿１１１０＿００１０＿ｘｘｘｘ＿”が得られるとする。
【０１７３】
（復号の具体例）
ここでは、上記の符号化の具体例によって符号化されたストリームデータ（“１００１＿００１０＿１１１０＿００１０＿ｘｘｘｘ＿”）を対象とする復号の具体例について説明する。したがって、復号対象の最初のシンタクスはＳｙｎｔａｘＡ（８ビット）であり、ＳｙｎｔａｘＡの次のシンタクスはＳｙｎｔａｘＢ（８ビット）である。
【０１７４】
ＳｙｎｔａｘＡの各ビット位置ｋにおける“０”の発生確率は、ＰｒｏｂＴａｂｌｅＡ［ｋ］＝｛２１７，２２３，２４５，２４５，２４４，２４２，２４４，２４５｝である。ＳｙｎｔａｘＢの各ビット位置ｋにおける“０”の発生確率は、ＰｒｏｂＴａｂｌｅＢ［ｋ］＝｛２３４，２５１，２４４，２５４，２１６，１９９，１７９，２３３｝である。また、復号対象のストリームデータの先頭の１６ビットは「１００１＿００１０＿１１１０＿００１０」となる。
【０１７５】
図２０は、シンタクスのグループ分けの一例を示す図である。復号装置１００においては、ＰｒｏｂＴａｂｌｅＡ［ｋ］およびＰｒｏｂＴａｂｌｅＢ［ｋ］の各発生確率が図２０のグループ２００１〜２００６のようにグループ分けされているとする。
【０１７６】
たとえば、復号装置１００は、各発生確率を順に読み出し、発生確率を１つ読み出すごとに、読み出した各発生確率の最大値および最小値を算出する。そして、復号装置１００は、算出した最大値および最小値の差が所定値を超えない範囲で最大数の各発生確率を１つのグループとする。これにより、各グループにおいて、発生確率の最大値と最小値の差が所定値以下となるようにすることができる。
【０１７７】
たとえば、図２０に示す例は、所定値を２５としてグループ分けを行った例である。たとえば、復号装置１００は、各発生確率を順に読み出し、３つめの発生確率（２４５）を読み出した時点で最大値（２４５）と最小値（２１７）の差が２８となり所定値（２５）を超えるため、１つ目および２つ目の発生確率（２１７，２２３）をグループ２００１とする。
【０１７８】
このように、復号装置１００は、復号データの各位置（各発生確率）を、同一グループ内の各位置における発生確率の最大値と最小値との差が所定値以内になるようにグループ２００１〜２００６に分けておく。これにより、たとえば“０”の発生確率の高い各位置が同一グループにまとまるため、一括復号の発生確率をさらに高めることができる。ただし、グループ分けの方法はこれに限らない。たとえば、各発生確率を、一定数ずつの各グループに分けてもよい。
【０１７９】
図２１−１は、具体例にかかるシンタクスとグループＩＤの対応情報を示す図である。図３−１に示した対応情報３１０は、図２０に示したグループ分けの例においては図２１−１に示す対応情報２１１０のようになる。
【０１８０】
図２１−２は、具体例にかかるグループＩＤと減少値の対応情報を示す図である。図１４に示した対応情報１４００は、図２０に示したグループ分けの例においては図２１−２に示す対応情報２１２０のようになる。
【０１８１】
まず、復号装置１００は、ストリームデータの先頭８ビット「１００１＿００１０」（１４６）を取得してＶａｌｕｅに設定する。また、復号装置１００は、Ｒａｎｇｅの初期値を２５５とする。復号装置１００は、ＳｙｎｔａｘＡ［０］はグループＩＤ「０」のグループに属するため、グループＩＤ「０」に対応するＳｕｂＶａｌ＝３９を取得する。そして、図１５に示した処理により、一括復号ビット数Ｎとして２が算出される。したがって、Ｎ＝２としてＮビット復号処理（図７参照）が実行される。Ｎビット復号処理においては、境界値ｓｐｌｉｔが下記（１）式のように算出される。
【０１８２】
Ｓｐｌｉｔ＝１＋（（（２５５−１）×２１７）＞＞８）＝２１６
Ｓｐｌｉｔ＝１＋（（（２１６−１）×２２３）＞＞８）＝１８８ …（１）
【０１８３】
したがって、Ｎビット復号処理の復号値は“００”となり、範囲Ｒａｎｇｅは１８８となる。復号装置１００は、２ビット復号したため、つぎにＳｙｎｔａｘＡ［２］の復号を行う。図１５に示した処理により、一括復号ビット数Ｎとして３が算出される。したがって、Ｎ＝３としてＮビット復号処理（図７参照）が実行される。Ｎビット復号処理においては、境界値ｓｐｌｉｔが下記（２）式のように算出される。
【０１８４】
Ｓｐｌｉｔ＝１＋（（（１８８−１）×２４５）＞＞８）＝１７９
Ｓｐｌｉｔ＝１＋（（（１７９−１）×２４５）＞＞８）＝１７１
Ｓｐｌｉｔ＝１＋（（（１７１−１）×２４４）＞＞８）＝１６３ …（２）
【０１８５】
したがって、Ｎビット復号処理の復号値は“０００”となり、範囲Ｒａｎｇｅは１６３となる。復号装置１００は、３ビット復号したため、つぎにＳｙｎｔａｘＡ［５］の復号を行う。図１５に示した処理により、一括復号ビット数Ｎとして１が算出される。したがって、Ｎ＝１としてＮビット復号処理（図７参照）が実行される。Ｎビット復号処理においては、境界値ｓｐｌｉｔが下記（３）式のように算出される。
【０１８６】
Ｓｐｌｉｔ＝１＋（（（１６３−１）×２４２）＞＞８）＝１５４ …（３）
【０１８７】
したがって、Ｎビット復号処理の復号値は“０”となり、範囲Ｒａｎｇｅは１５４となる。復号装置１００は、１ビット復号したため、つぎにＳｙｎｔａｘＡ［６］の復号を行う。図１５に示した処理により、一括復号ビット数Ｎとして０が算出される。したがって、１ビット復号処理（図６参照）が実行される。１ビット復号処理においては、境界値ｓｐｌｉｔが下記（４）式のように算出される。
【０１８８】
Ｓｐｌｉｔ＝１＋（（（１５４−１）×２４４）＞＞８）＝１４６ …（４）
【０１８９】
したがって、１ビット復号処理の復号値は“１”となり、範囲Ｒａｎｇｅは８となり、符号値Ｖａｌｕｅは１となる。範囲Ｒａｎｇｅが１２８未満となったため、復号装置１００は再正規化を行う。具体的には、復号装置１００は、ストリームデータから４ビット補充してＶａｌｕｅ＝３０とする。範囲Ｒａｎｇｅは１２８となる。
【０１９０】
つぎに、復号装置１００は、１ビット復号したため、ＳｙｎｔａｘＡ［７］の復号を行う。図１５に示した処理により、一括復号ビット数Ｎとして０が算出される。したがって、１ビット復号処理（図６参照）が実行される。１ビット復号処理においては、境界値ｓｐｌｉｔが下記（５）式のように算出される。
【０１９１】
Ｓｐｌｉｔ＝１＋（（（１２８−１）×２４５）＞＞８）＝１２２ …（５）
【０１９２】
したがって、１ビット復号処理の復号値は“０”となり、範囲Ｒａｎｇｅは１２２となる。範囲Ｒａｎｇｅが１２８未満となったため、復号装置１００は再正規化を行う。具体的には、復号装置１００は、ストリームデータから１ビット補充してＶａｌｕｅ＝６０とする。範囲Ｒａｎｇｅは２４４となる。これにより、ＳｙｎｔａｘＡを“００００００１０”として復号することができる。ＳｙｎｔａｘＢについても同様の手順で復号することができる。
【０１９３】
このように、復号装置１００においては、特定の条件を満たす複数のシンタクス（またはシンタクスのビット位置）がひとつのグループとして予めまとめられる。そして、あるシンタクスの復号を行う際は、そのシンタクスが含まれているグループ内の最も低い発生確率により優勢シンボルが出力されると仮定した場合の範囲Ｒａｎｇｅの減少値（減少値ＳｕｂＶａｌ）が算出される。
【０１９４】
つぎに、算出された減少値を元に再正規化が発生するまでの最小の連続復号ビット数が算出され、算出されたビット数だけ１サイクルで一括して復号処理が行われる。これにより、予め一括復号ビット数を決定しなくても、シンタクスに応じた復号ビット数を選択することにより、一括復号が実施される割合が高くなり、算術復号処理の高速化を図ることが可能となる。
【０１９５】
また、連続復号ビット数の計算においては、グループ内でひとつの発生確率を代表して使用するため、マルチコンテキスト型の算術復号においても、多入力の乗算処理を行わなくてもよく、回路規模を小さくすることができる。また、グループの分類をシンタクス単位、またはシンタクスのビット単位と切り替えることにより、一括復号が発生する確率を調整することができる。
【０１９６】
以上説明したように、復号装置、復号方法および復号プログラムによれば、復号の高速化を図ることができる。
【０１９７】
なお、各実施の形態で説明した復号方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。このプログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ等のコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。またこのプログラムは、インターネット等のネットワークを介して配布することが可能な伝送媒体であってもよい。
【０１９８】
また、各実施の形態で説明した復号装置１００は、スタンダードセルやストラクチャードＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ Ｓｐｅｃｉｆｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ）などの特定用途向けＩＣ（以下、単に「ＡＳＩＣ」と称す。）やＦＰＧＡなどのＰＬＤ（Ｐｒｏｇｒａｍｍａｂｌｅ Ｌｏｇｉｃ Ｄｅｖｉｃｅ）によっても実現することができる。具体的には、たとえば、上述した復号装置１００の機能をＨＤＬ記述によって機能定義し、そのＨＤＬ記述を論理合成してＡＳＩＣやＰＬＤに与えることにより、復号装置１００を製造することができる。
【０１９９】
上述した各実施の形態に関し、さらに以下の付記を開示する。
【０２００】
（付記１）マルチコンテキスト型の算術符号化により所定の数値範囲に割り当てられた符号値から前記算術符号化の前のデータ列を復号する復号装置において、
前記数値範囲を記憶する記憶部と、
前記データ列の各位置における所定シンボルの発生確率を取得する取得部と、
前記取得部によって取得された発生確率の中の、前記データ列を区切った複数のグループのうちの復号対象の位置が属するグループにおける最小の発生確率に基づく前記数値範囲の減少幅を導出する導出部と、
前記数値範囲の限界値と前記符号値との差分を、前記導出部によって導出された減少幅によって除算する除算部と、
前記除算部によって得られた商が所定値以上である場合に、前記商だけ連続する前記所定シンボルとなる、前記復号対象の位置以降の復号結果を出力する一括復号処理部と、
を備えることを特徴とする復号装置。
【０２０１】
（付記２）前記商が前記所定値以上である場合に、前記記憶部に記憶された数値範囲の前記限界値を、前記減少幅に前記商を乗じた幅だけ変化させて前記数値範囲を縮小する縮小部を備えることを特徴とする付記１に記載の復号装置。
【０２０２】
（付記３）前記除算部は、前記限界値と前記符号値との差分および前記限界値と所定の閾値との差分のうちの小さい方の差分を前記減少幅によって除算し、
前記縮小部によって縮小された数値範囲の幅が前記所定の閾値以上となるように前記数値範囲および前記符号値を正規化する正規化部を備えることを特徴とする付記２に記載の復号装置。
【０２０３】
（付記４）前記導出部は、
前記最小の発生確率を特定する特定部と、
前記記憶部によって記憶された数値範囲を、前記特定部によって特定された発生確率に相当する割合で縮小した場合における前記数値範囲の減少幅を算出する算出部と、
を備えることを特徴とする付記１〜３のいずれか一つに記載の復号装置。
【０２０４】
（付記５）前記一括復号処理部によって復号結果が出力された場合に、前記データ列の各位置のうち、前記復号対象の位置から前記商の数だけ先の位置を次の復号対象とすることを特徴とする付記１〜４のいずれか一つに記載の復号装置。
【０２０５】
（付記６）前記商が前記所定値未満である場合に、前記記憶部によって記憶された数値範囲と、前記取得部によって取得された発生確率のうち前記復号対象の位置における発生確率と、前記符号値と、に基づく前記復号対象の位置の復号結果を出力する個別復号処理部を備え、
前記縮小部は、前記個別復号処理部によって復号結果が出力された場合に、前記個別復号処理部によって出力された復号結果と、前記復号対象の位置における発生確率と、に応じて前記記憶部によって記憶された数値範囲を縮小することを特徴とする付記２または３に記載の復号装置。
【０２０６】
（付記７）前記個別復号処理部によって復号結果が出力された場合に、前記データ列の各位置のうち、前記復号対象の１つ先の位置を次の復号対象とすることを特徴とする付記６に記載の復号装置。
【０２０７】
（付記８）前記導出部は、前記グループごとに、前記最小の発生確率に相当する割合による前記所定の数値範囲の減少幅が対応付けられた対応情報に基づいて、前記復号対象の位置が属するグループに対応する前記減少幅を導出することを特徴とする付記１〜３のいずれか一つに記載の復号装置。
【０２０８】
（付記９）前記減少幅に前記商を乗じた幅だけ縮小した前記数値範囲が前記符号値以下であり、または前記減少幅に前記商を乗じた幅だけ縮小した前記数値範囲が前記閾値未満である場合に、前記一括復号処理部は、前記商だけ連続する前記所定シンボルとなる復号結果を出力せず、前記個別復号処理部は、前記復号対象の位置を復号した復号結果を出力することを特徴とする付記６または７に記載の復号装置。
【０２０９】
（付記１０）前記データ列の各位置は、同一グループ内の各位置における前記発生確率の最大値と最小値との差が所定値以内になるように前記複数のグループに分けられていることを特徴とする付記１〜９のいずれか一つに記載の復号装置。
【０２１０】
（付記１１）マルチコンテキスト型の算術符号化により所定の数値範囲に割り当てられた符号値から前記算術符号化の前のデータ列を復号する復号方法において、
前記数値範囲を記憶し、
前記データ列の各位置における所定シンボルの発生確率を取得し、
取得した発生確率の中の、前記データ列を区切った複数のグループのうちの復号対象の位置が属するグループにおける最小の発生確率に基づく前記数値範囲の減少幅を導出し、
前記数値範囲の限界値と前記符号値との差分を、前記導出した減少幅によって除算し、
除算により得た商が所定値以上である場合に、前記商だけ連続する前記所定シンボルとなる、前記復号対象の位置以降の復号結果を出力することを特徴とする復号方法。
【０２１１】
（付記１２）マルチコンテキスト型の算術符号化により所定の数値範囲に割り当てられた符号値から前記算術符号化の前のデータ列を復号する復号プログラムにおいて、
前記数値範囲を記憶し、
前記データ列の各位置における所定シンボルの発生確率を取得し、
取得した発生確率の中の、前記データ列を区切った複数のグループのうちの復号対象の位置が属するグループにおける最小の発生確率に基づく前記数値範囲の減少幅を導出し、
前記数値範囲の限界値と前記符号値との差分を、前記導出した減少幅によって除算し、
除算により得た商が所定値以上である場合に、前記商だけ連続する前記所定シンボルとなる、前記復号対象の位置以降の復号結果を出力する処理をコンピュータに実行させることを特徴とする復号プログラム。
【符号の説明】
【０２１２】
ｘ１〜ｘ１０ 位置
ｐ１〜ｐ１０，ｐｒｏｂ１〜ｐｒｏｂＭ 発生確率
１００ 復号装置
１０１ 復号対象位置
１０２ 符号値
１１０，６１１ データ列
１１１〜１１３，２００１〜２００６ グループ
１２１〜１２３ 数値範囲
１２１ａ 限界値
１２２ａ 減少幅
１２２ｂ 差分
２００ 情報処理装置
２０１ バス
３１０，３２０，１４００，２１１０，２１２０ 対応情報
６１０ ストリームデータ
１１０３，１１１１〜１１１３，１３０８ シフト部
１１１０ 再正規化制御部
１１１４ ＯＲ部
１２２１〜１２２Ｍ 境界値算出部
【技術分野】
【０００１】
本発明は、復号装置、復号方法および復号プログラムに関する。
【背景技術】
【０００２】
算術符号化は、データ列全体をひとつの符号値に置き換えることにより、ハフマン符号化より圧縮率を高める符号化技術である。しかし、算術符号化は、符号化および復号に要する処理量がハフマン符号化より多い。
【０００３】
たとえば動画像圧縮の分野において、算術符号化は、Ｈ．２６４やＶＰ８などの規格にも採用されており、動画像の時間的または空間的相関性を利用した圧縮を施した後のエントロピー符号化として利用されている。また、Ｈ．２６４やＶＰ８ではマルチコンテキスト方式が採用されており、符号化するデータ列の内容に応じてシンボルの発生確率を切り替えることでより圧縮効率を向上させている。
【０００４】
算術符号化されたデータは１ビットずつ復号していくことになるため、処理を並列化して複数のビットを同時に復号することは困難である。このため、復号性能を向上させるには、動作周波数を向上させることが考えられるが、マルチコンテキスト方式ではコンテキストの切り替え処理も必要なため、動作周波数の高速化にも限度がある。
【０００５】
このため、従来はある特定の条件を満たすケースにおいて複数シンボルの同時復号を行うことにより復号処理の高速化を図る一括復号の手法が用いられている（たとえば、下記特許文献１，２参照。）。たとえば、同一コンテキストのＭＰＳ（Ｍｏｒｅ ｐｒｏｂａｂｌｅ Ｓｙｍｂｏｌ：優勢シンボル）が、予め定められた２、４、８または１６連続する場合で、かつ復号途中の正規化処理が不要な場合において、１サイクルで一括して複数のビットを復号する手法が知られている。また、コンテキストが切り替わる際において、予めＭＰＳが連続する場合のコンテキスト情報を内部に持っておくことにより、１サイクルで複数のビットを一括して復号する手法等が知られている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０００−３５００４３号公報
【特許文献２】特開２００５−２１７８７１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上述した従来技術では、一括復号するビット数を予め決定しておくことになるため、予め決定された数だけ同一シンボルが連続しない場合は一括復号が実行されない。このため、シンタクスによっては一括復号の発生確率が低くなり、復号の高速化を図ることができないという問題がある。
【０００８】
本発明は、上述した従来技術による問題点を解消するため、復号の高速化を図ることができる復号装置、復号方法および復号プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上述した課題を解決し、目的を達成するため、本発明の一側面によれば、マルチコンテキスト型の算術符号化により所定の数値範囲に割り当てられた符号値から前記算術符号化の前のデータ列を復号する復号方法において、前記数値範囲を記憶し、前記データ列の各位置における所定シンボルの発生確率を取得し、取得した発生確率の中の、前記データ列を区切った複数のグループのうちの復号対象の位置が属するグループにおける最小の発生確率に基づく前記数値範囲の減少幅を導出し、前記数値範囲の限界値と前記符号値との差分を、前記導出した減少幅によって除算し、除算により得た商が所定値以上である場合に、前記商だけ連続する前記所定シンボルとなる、前記復号対象の位置以降の復号結果を出力する復号装置、復号方法および復号プログラムが提案される。
【発明の効果】
【００１０】
本発明の一側面によれば、復号の高速化を図ることができるという効果を奏する。
【図面の簡単な説明】
【００１１】
【図１−１】図１−１は、実施の形態１にかかる復号装置による復号処理の一例を示す図（その１）である。
【図１−２】図１−２は、実施の形態１にかかる復号装置による復号処理の一例を示す図（その２）である。
【図１−３】図１−３は、実施の形態１にかかる復号装置による復号処理の一例を示す図（その３）である。
【図２】図２は、復号装置のハードウェア構成の一例を示す図である。
【図３−１】図３−１は、シンタクスとグループＩＤとの対応情報の一例を示す図である。
【図３−２】図３−２は、グループＩＤと発生確率の対応情報の一例を示す図である。
【図４】図４は、復号装置による復号処理の一例を示すフローチャートである。
【図５】図５は、１ビット復号処理の一例を示すフローチャートである。
【図６】図６は、１ビット復号処理の一例を示す図である。
【図７】図７は、Ｎビット復号処理の一例を示すフローチャートである。
【図８】図８は、一括復号ビット数Ｎの算出処理の一例を示すフローチャートである。
【図９】図９は、Ｎビット復号処理の一例を示す図である。
【図１０】図１０は、復号装置の構成の一例を示す図である。
【図１１】図１１は、１ビット復号処理部の構成の一例を示す図である。
【図１２】図１２は、Ｎビット復号装置の構成の一例を示す図である。
【図１３】図１３は、一括復号ビット数算出部の構成の一例を示す図である。
【図１４】図１４は、グループＩＤと減少値の対応情報の一例を示す図である。
【図１５】図１５は、一括復号ビット数Ｎの算出処理の一例を示すフローチャートである。
【図１６】図１６は、実施の形態２にかかる一括復号ビット数算出部の構成の一例を示す図である。
【図１７】図１７は、符号化処理の一例を示すフローチャートである。
【図１８】図１８は、符号化処理における再正規化処理の一例を示すフローチャートである。
【図１９】図１９は、再正規化処理におけるライト処理の一例を示すフローチャートである。
【図２０】図２０は、シンタクスのグループ分けの一例を示す図である。
【図２１−１】図２１−１は、具体例にかかるシンタクスとグループＩＤの対応情報を示す図である。
【図２１−２】図２１−２は、具体例にかかるグループＩＤと減少値の対応情報を示す図である。
【発明を実施するための形態】
【００１２】
以下に添付図面を参照して、本発明にかかる復号装置、復号方法および復号プログラムの実施の形態を詳細に説明する。
【００１３】
（実施の形態１）
（実施の形態１にかかる復号装置による復号処理）
図１−１〜図１−３は、実施の形態１にかかる復号装置による復号処理の一例を示す図である。実施の形態１にかかる復号装置１００（たとえば図２−１参照）は、マルチコンテキスト型の算術符号化により所定の数値範囲に割り当てられた符号値から、算術符号化の前のデータを復号する。算術符号化は、たとえばレンジコーダである。
【００１４】
ここではＶＰ８による復号処理について説明するが、エンコードおよびデコードの方式はＶＰ８に限らない。ＶＰ８で使用されている算術符号化はマルチコンテキスト型であるため、シンタクスやシンタクス内のビット位置によって二値（０／１）の発生確率が変化する。また算術符号化に用いる数直線（範囲Ｒａｎｇｅ）は０から２５５の整数値として扱われる。そして、範囲Ｒａｎｇｅの値が１２８未満になった場合には、範囲Ｒａｎｇｅと現在の符号値（符号値Ｖａｌｕｅ）の値を倍にすること（再正規化）により、精度を保ったまま符号化および復号が行われる。
【００１５】
図１−１に示すデータ列１１０は、復号装置１００によって復号されるデータである。位置ｘ１〜ｘ１０は、データ列１１０における各位置（たとえばビット位置）を示している。復号装置１００は、復号処理を行うことによって位置ｘ１〜ｘ１０における各値を得る。
【００１６】
発生確率ｐ１〜ｐ１０は、それぞれ位置ｘ１〜ｘ１０における所定シンボルの発生確率（以下、単に「発生確率」とも称する。）を示している。所定シンボルは、たとえばデータ列１１０における優勢シンボルである。また、以下の説明において、データ列１１０における優勢シンボルは“０”とする。復号対象位置１０１は、復号装置１００による現在の復号対象の位置を示している。初期状態における復号対象位置１０１は位置ｘ１である。
【００１７】
図１−２に示す数値範囲１２１は、データ列１１０が算術符号化により割り当てられた所定の数値範囲（たとえば０〜２５５）を示している。限界値１２１ａは、数値範囲１２１の限界値（たとえば上限値）を示している。符号値１０２は、数値範囲１２１に割り当てられた復号対象の符号値を示している。
【００１８】
復号装置１００は、データ列１１０の位置ｘ１〜ｘ１０を複数のグループに分けておく。各グループには連続する複数の位置が含まれる。図１−１に示す例では、位置ｘ１〜ｘ１０がグループ１１１〜１１３に分けられている。位置ｘ１〜ｘ３はグループ１１１に含まれている。位置ｘ４〜ｘ７はグループ１１２に含まれている。位置ｘ８〜ｘ１０はグループ１１３に含まれている。
【００１９】
たとえば、復号装置１００は、位置ｘ１〜ｘ１０を所定数ずつ区切ってグループ分けしてもよいし、位置ｘ１〜ｘ１０を発生確率ｐ１〜ｐ１０に基づいて区切ってグループ分けしてもよい（たとえば図２０参照）。
【００２０】
復号装置１００は、数値範囲１２１を取得して記憶する。また、復号装置１００は、発生確率ｐ１〜ｐ１０を取得する。そして、復号装置１００は、グループ１１１〜１１３のうちの現在の復号対象位置１０１が属するグループの各発生確率の中から最小の発生確率を特定する。図１−１に示す例では、復号対象位置１０１の位置ｘ１はグループ１１１に属しているため、グループ１１１に属する位置ｘ１〜ｘ３における発生確率ｐ１〜ｐ３のうちの最小の発生確率が特定される。
【００２１】
また、復号装置１００は、特定した発生確率に相当する割合で数値範囲１２１を縮小した場合における数値範囲１２１の減少幅を算出する。数値範囲１２２は、特定した発生確率に相当する割合で数値範囲１２１を縮小した数値範囲である。減少幅１２２ａは、数値範囲１２１に対する数値範囲１２２の減少幅である。たとえば、減少幅１２２ａは、数値範囲１２１の幅から数値範囲１２２の幅を減算することによって算出することができる。
【００２２】
そして、復号装置１００は、数値範囲１２１の限界値１２１ａと符号値１０２との差分１２２ｂを減少幅１２２ａによって除算した商を算出する。これにより、復号対象位置１０１以降の復号結果において所定シンボルが連続する最小の回数を算出することができる。図１−２に示す例では、商として２が算出される。
【００２３】
つぎに、復号装置１００は、算出した商が所定値以上である場合に、算出した商だけ連続する所定シンボルとなる復号結果を出力する。所定値は、連続復号を行うか否かを判定するための所定シンボルの連続数の閾値であり、たとえば１である。図１−２に示した例では商は２であるため、図１−３に示すように、２回連続する所定シンボル“０”、すなわち“００”が位置ｘ１，ｘ２の復号結果として出力される。これにより、一括復号による復号結果を得ることができる。
【００２４】
また、復号装置１００は、一括復号により復号結果を出力した場合に、現在の復号対象位置１０１から商の数だけ先の位置を次の復号対象位置１０１とする。図１−１の例では復号対象位置１０１が位置ｘ１であり、商が２であるため、図１−３に示すように、新たな復号対象位置１０１は位置ｘ１の２つ先の位置ｘ３となる。復号装置１００は、新たな復号対象位置１０１について再度復号処理を行う。
【００２５】
また、復号装置１００は、算出した商が所定値以上である場合に、減少幅１２２ａに商を乗じた幅だけ数値範囲１２１を縮小する。図１−２に示す例では、商が２であるため、減少幅１２２ａの２倍の幅だけ数値範囲１２１が縮小される。このため、数値範囲１２１は縮小されて数値範囲１２３のようになる。
【００２６】
また、復号装置１００は、縮小した数値範囲１２３の限界値が閾値（たとえば１２８）を下回った場合は、数値範囲１２３および符号値１０２を同一比率で増大させる再正規化を行ってもよい。たとえば、復号装置１００は、数値範囲１２３の幅が閾値を下回った場合は、数値範囲１２３の幅が閾値以上になるまで、数値範囲１２３および符号値１０２を倍増する処理を繰り返す。これにより、精度を保ったまま復号処理を行うことができる。
【００２７】
再正規化を行う場合は、復号装置１００は、数値範囲１２１の限界値１２１ａと符号値１０２との差分１２２ｂと、数値範囲１２１の限界値１２１ａと閾値との差分と、のうちの小さい方の差分を減少幅１２２ａによって除算した商を算出する。これにより、復号対象位置１０１以降の復号結果において所定シンボルが連続し、かつ再正規化が発生しない最小の回数を算出することができる。
【００２８】
また、復号装置１００は、算出した商が所定値未満（たとえば０）であった場合に、数値範囲１２１と、復号対象位置１０１に対応する発生確率ｐ１と、符号値１０２と、に基づいて復号対象位置１０１（位置ｘ１）を復号した復号結果を出力する。この場合は、復号装置１００は、復号結果と、発生確率ｐ１と、に応じて復号対象位置１０１を縮小する。また、この場合は、復号装置１００は、位置ｘ１〜ｘ１０のうちの現在の復号対象位置１０１から１つ先の位置を次の復号対象位置１０１とする。
【００２９】
このように、復号装置１００によれば、復号データの各位置をグループ分けし、復号対象の位置が属するグループの所定シンボルの最小の発生確率に基づいて所定シンボルの最小の連続数を算出することができる。これにより、一括復号数を予め定めておかなくても、所定シンボルの発生確率に基づいて一括復号数を適応的に変化させて一括復号を行うことができる。このため、一括復号の実施確率を高めて復号の高速化を図ることができる。
【００３０】
（復号装置のハードウェア構成）
図２は、復号装置のハードウェア構成の一例を示す図である。図１に示した復号装置１００は、たとえば図２に示す情報処理装置２００によって実現することができる。情報処理装置２００は、ＣＰＵ２１０と、メインメモリ２２０と、補助メモリ２３０と、ユーザインタフェース２４０と、通信インタフェース２５０と、バス２０１と、を備えている。ＣＰＵ２１０、メインメモリ２２０、補助メモリ２３０、ユーザインタフェース２４０および通信インタフェース２５０は、バス２０１によって接続されている。
【００３１】
ＣＰＵ２１０（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）は、情報処理装置２００の全体の制御を司る。また、情報処理装置２００はＣＰＵ２１０を複数備えていてもよい。メインメモリ２２０は、たとえばＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）である。メインメモリ２２０は、ＣＰＵ２１０のワークエリアとして使用される。補助メモリ２３０は、たとえば、ハードディスク、光ディスク、フラッシュメモリなどの不揮発メモリである。補助メモリ２３０には、情報処理装置２００を動作させる各種のプログラムが記憶されている。補助メモリ２３０に記憶されたプログラムは、メインメモリ２２０にロードされてＣＰＵ２１０によって実行される。
【００３２】
ユーザインタフェース２４０は、たとえば、ユーザからの操作入力を受け付ける入力デバイスや、ユーザへ情報を出力する出力デバイスなどを含む。入力デバイスは、たとえばキー（たとえばキーボード）やリモコンなどによって実現することができる。出力デバイスは、たとえばディスプレイやスピーカなどによって実現することができる。また、タッチパネルなどによって入力デバイスおよび出力デバイスを実現してもよい。ユーザインタフェース２４０は、ＣＰＵ２１０によって制御される。
【００３３】
通信インタフェース２５０は、たとえば、無線によって情報処理装置２００の外部との間で通信を行う通信インタフェースである。たとえば、復号装置１００は、算術符号化されたストリームデータを通信インタフェース２５０によって受信し、受信したストリームデータを復号する。通信インタフェース２５０は、ＣＰＵ２１０によって制御される。
【００３４】
（シンタクスとグループＩＤとの対応情報）
図３−１は、シンタクスとグループＩＤとの対応情報の一例を示す図である。図３−１に示す対応情報３１０は、シンタクスとグループＩＤとを対応付ける対応情報である。対応情報３１０は、たとえば復号装置１００のメインメモリ２２０や補助メモリ２３０に記憶されている。対応情報３１０に示すように、シンタクス「Ｓｙｎｔａｘ＿Ａ」〜「Ｓｙｎｔａｘ＿Ｘ」のそれぞれは、グループＩＤが「０」〜「Ｙ」の各グループに分類されている。
【００３５】
たとえば、シンタクス「Ｓｙｎｔａｘ＿Ａ」はグループＩＤ「０」のグループに属している。シンタクス「Ｓｙｎｔａｘ＿Ｂ」〜「Ｓｙｎｔａｘ＿Ｄ」はグループＩＤ「１」のグループに属している。図３−１に示す例では、シンタクス単位でグループ分けを行う例について説明したが、グループ分けはシンタクス単位に限らず、シンタクスのビット位置単位など、コンテキスト（優勢シンボルの発生確率）単位で行ってもよい。
【００３６】
（グループＩＤと発生確率の対応情報）
図３−２は、グループＩＤと発生確率の対応情報の一例を示す図である。図３−２に示す対応情報３２０は、グループＩＤと優勢シンボルの最小の発生確率とを対応付ける対応情報である。対応情報３２０は、たとえば復号装置１００のメインメモリ２２０や補助メモリ２３０に記憶されている。
【００３７】
対応情報３２０に示す最小の発生確率ｐｒｏｂＧ（０）〜ｐｒｏｂＧ（Ｙ）は、それぞれグループＩＤ「０」〜「Ｙ」が示すグループに属する各シンタクスの優勢シンボルの発生確率のうちの最小の発生確率を示している。たとえば、最小の発生確率ｐｒｏｂＧ（１）は、グループＩＤ「１」が示すグループに属するシンタクス「Ｓｙｎｔａｘ＿Ｂ」〜「Ｓｙｎｔａｘ＿Ｄ」の優勢シンボルの発生確率のうちの最小の発生確率を示している。
【００３８】
（復号装置による復号処理）
図４は、復号装置による復号処理の一例を示すフローチャートである。復号装置１００は、復号処理としてたとえば以下の各ステップを実行する。まず、復号装置１００は、復号対象のシンタクスを初期化する（ステップＳ４０１）。ステップＳ４０１において、復号装置１００は、たとえば、最初の復号位置におけるシンタクスを、符号化側から予め通知されたシンタクスに設定する。
【００３９】
つぎに、復号装置１００は、入力されたデータストリームの先頭の８ビット（ｒｅａｄ＿ｂｉｔ（８））を取り出して符号値Ｖａｌｕｅの初期値として設定する（ステップＳ４０２）。また、復号装置１００は、数直線を示す範囲Ｒａｎｇｅの初期値として２５５を設定する（ステップＳ４０３）。
【００４０】
つぎに、復号装置１００は、復号対象のシンタクスの各ビットにおける“０”（優勢シンボル）の発生確率ｐｒｏｂを取得する（ステップＳ４０４）。つぎに、復号装置１００は、一括復号ビット数Ｎを算出する（ステップＳ４０５）。一括復号ビット数Ｎは、以降の復号結果において優勢シンボルである“０”が連続する回数である。ステップＳ４０５における一括復号ビット数Ｎの算出処理については後述する（たとえば図８参照）。
【００４１】
つぎに、復号装置１００は、ステップＳ４０５によって算出した一括復号ビット数Ｎが０であるか否かを判断する（ステップＳ４０６）。一括復号ビット数Ｎが０でない場合（ステップＳ４０６：Ｎｏ）は、復号装置１００は、Ｎビット復号処理を行い（ステップＳ４０７）、ステップＳ４０９へ移行する。Ｎビット復号処理は、Ｎビットの“０”を一括して復号する処理である。ステップＳ４０７におけるＮビット復号処理については後述（たとえば図７参照）する。
【００４２】
ステップＳ４０６において、一括復号ビット数Ｎが０である場合（ステップＳ４０６：Ｙｅｓ）は、復号装置１００は、１ビット復号処理を行い（ステップＳ４０８）、ステップＳ４０９へ移行する。１ビット復号処理は、次の復号結果が“０”および“１”のいずれであるかを判定して復号する処理である。ステップＳ４０８における１ビット復号処理については後述（たとえば図５参照）する。
【００４３】
つぎに、復号装置１００は、ステップＳ４０７のＮビット復号処理またはステップＳ４０８の１ビット復号処理による復号結果を逆二値化する（ステップＳ４０９）。つぎに、復号装置１００は、ステップＳ４０９の逆二値化の結果に基づいて復号対象のシンタクスを更新する（ステップＳ４１０）。つぎに、復号装置１００は、復号対象の全てのシンタクスを復号したか否かを判断する（ステップＳ４１１）。
【００４４】
ステップＳ４１１において、全てのシンタクスを復号していない場合（ステップＳ４１１：Ｎｏ）は、復号装置１００は、ステップＳ４０４へ戻る。全てのシンタクスを復号した場合（ステップＳ４１１：Ｙｅｓ）は、復号装置１００は、ステップＳ４０９の逆二値化により得られた復号結果のデータを出力し（ステップＳ４１２）、一連の処理を終了する。以上の各ステップにより、入力されたデータストリームの復号結果のデータを得ることができる。
【００４５】
（１ビット復号処理）
図５は、１ビット復号処理の一例を示すフローチャートである。復号装置１００は、図４に示したステップＳ４０８における１ビット復号処理として、たとえば以下の各ステップを実行する。
【００４６】
まず、復号装置１００は、現在の範囲Ｒａｎｇｅと、復号対象の１ビットにおける優勢シンボルの発生確率ｐｒｏｂに基づいて境界値ｓｐｌｉｔを算出する（ステップＳ５０１）。境界値ｓｐｌｉｔは、範囲Ｒａｎｇｅにおける“０”と“１”の境界値である。優勢シンボルの発生確率ｐｒｏｂは、復号対象のシンタクスおよびシンタクスのビット位置に基づいて求めることができる。ステップＳ５０１において、復号装置１００は、たとえば１＋（（（範囲Ｒａｎｇｅ−１）＊ｐｒｏｂ）＞＞８）によって境界値ｓｐｌｉｔを算出することができる。
【００４７】
つぎに、復号装置１００は、現在の符号値Ｖａｌｕｅが、ステップＳ５０１によって算出された境界値ｓｐｌｉｔ以上であるか否かを判断する（ステップＳ５０２）。現在の符号値Ｖａｌｕｅが境界値ｓｐｌｉｔ以上である場合（ステップＳ５０２：Ｙｅｓ）は、復号装置１００は、復号値として“１”を出力する（ステップＳ５０３）。
【００４８】
つぎに、復号装置１００は、範囲Ｒａｎｇｅから境界値ｓｐｌｉｔを減算する（ステップＳ５０４）。また、復号装置１００は、符号値Ｖａｌｕｅから境界値ｓｐｌｉｔを減算し（ステップＳ５０５）、ステップＳ５０８へ移行する。
【００４９】
ステップＳ５０２において、現在の符号値Ｖａｌｕｅが境界値ｓｐｌｉｔ未満である場合（ステップＳ５０２：Ｎｏ）は、復号装置１００は、復号値として“０”を出力する（ステップＳ５０６）。つぎに、復号装置１００は、範囲Ｒａｎｇｅに境界値ｓｐｌｉｔの値を設定し（ステップＳ５０７）、ステップＳ５０８へ移行する。
【００５０】
つぎに、復号装置１００は、範囲Ｒａｎｇｅが１２８未満か否かを判断する（ステップＳ５０８）。範囲Ｒａｎｇｅが１２８未満である場合（ステップＳ５０８：Ｙｅｓ）は、復号装置１００は、再正規化を行う。すなわち、復号装置１００は、範囲Ｒａｎｇｅの値を１ビット左シフトさせることで２倍にする（ステップＳ５０９）。
【００５１】
また、復号装置１００は、符号値Ｖａｌｕｅの値を１ビット左シフトさせることで２倍にする（ステップＳ５１０）。つぎに、復号装置１００は、ストリームデータから１ビット（ｒｅａｄ＿ｂｉｔ（１））を取り出して符号値Ｖａｌｕｅの最下位ビットとして補充し（ステップＳ５１１）、ステップＳ５０８へ戻る。このように、復号装置１００は、再正規化を実行する度にストリームデータを１ビットずつ読み出す。
【００５２】
ステップＳ５０８において、範囲Ｒａｎｇｅが１２８以上である場合（ステップＳ５０８：Ｎｏ）は、復号装置１００は、一連の処理を終了する。以上の各ステップにより、復号装置１００は、１ビットの復号を行うことができる。また、復号装置１００は、１ビットの復号によって範囲Ｒａｎｇｅが１２８未満になった場合は、範囲Ｒａｎｇｅおよび符号値Ｖａｌｕｅを２倍にしてストリームデータを１ビット読み出すことができる。
【００５３】
図６は、１ビット復号処理の一例を示す図である。図６においては、図５に示した１ビット復号処理を連続して４回行った場合の例について説明する。１〜４回目の１ビット復号処理において、シンタクスの優勢シンボル“０”の発生確率は、それぞれ２０４／２５６，２３０／２５６，１７９／２５６，２０４／２５６と遷移するものとする。まず、初期化処理として、ストリームデータ６１０から先頭の８ビットのデータ列６１１が符号値Ｖａｌｕｅに設定される。データ列６１１は“１０１０１０００”（１６８）とする。また、範囲Ｒａｎｇｅに２５５が設定される。
【００５４】
１回目の１ビット復号処理においては、範囲Ｒａｎｇｅが２５５であり、発生確率が２０４／２５６であるため、境界値ｓｐｌｉｔは２０３（小数点以下切り捨て。以下同様）となる。したがって、符号値Ｖａｌｕｅの１６８は境界値ｓｐｌｉｔ未満であるため、復号値は“０”となる。また、以降の範囲Ｒａｎｇｅは境界値ｓｐｌｉｔの２０３となる。また、範囲Ｒａｎｇｅは１２８以上であるため、再正規化は発生しない。
【００５５】
２回目の１ビット復号処理においては、範囲Ｒａｎｇｅが２０３であり、発生確率が２３０／２５６であるため、境界値ｓｐｌｉｔは１８２となる。したがって、符号値Ｖａｌｕｅの１６８は境界値ｓｐｌｉｔ未満であるため、復号値は“０”となる。また、以降の範囲Ｒａｎｇｅは境界値ｓｐｌｉｔの１８２となる。また、範囲Ｒａｎｇｅは１２８以上であるため、再正規化は発生しない。
【００５６】
３回目の１ビット復号処理においては、範囲Ｒａｎｇｅが１８２であり、発生確率が１７９／２５６であるため、境界値ｓｐｌｉｔは１２７となる。したがって、符号値Ｖａｌｕｅの１６８は境界値ｓｐｌｉｔ以上であるため、復号値は“１”となる。また、範囲Ｒａｎｇｅは境界値ｓｐｌｉｔの１２７を減算した５５となる。また、符号値Ｖａｌｕｅは境界値ｓｐｌｉｔの１２７を減算した４１となる。
【００５７】
また、範囲Ｒａｎｇｅが１２８未満となったため、再正規化が発生する。再正規化により、範囲Ｒａｎｇｅは２倍の１１０となり、符号値Ｖａｌｕｅも２倍の８２となる。そして、ストリームデータ６１０から新たに読み出した１ビットは“１”となるため、符号値Ｖａｌｕｅは８３となる。
【００５８】
１回目の再正規化後の範囲Ｒａｎｇｅはまだ１２８未満であるため、２回目の再正規化が発生する。２回目の再正規化により、範囲Ｒａｎｇｅは２倍の２２０となり、符号値Ｖａｌｕｅも２倍の１６６となる。そして、ストリームデータ６１０から新たに読み出した１ビットは“１”となるため、符号値Ｖａｌｕｅは１６７となる。２回目の再正規化後の範囲Ｒａｎｇｅは１２８以上であるため、３回目の１ビット復号処理においてはこれ以上の再正規化は発生しない。
【００５９】
４回目の１ビット復号処理においては、範囲Ｒａｎｇｅが２２０であり、発生確率が２０４／２５６であるため、境界値ｓｐｌｉｔは１７５となる。したがって、符号値Ｖａｌｕｅの１６７は境界値ｓｐｌｉｔ未満であるため、復号値は“０”となる。また、以降の範囲Ｒａｎｇｅは境界値ｓｐｌｉｔの１７５となる。１〜４回目の１ビット復号処理により、復号値として“００１０”を得ることができる。
【００６０】
（Ｎビット復号処理）
図７は、Ｎビット復号処理の一例を示すフローチャートである。復号装置１００は、図４に示したステップＳ４０７におけるＮビット復号処理として、たとえば以下の各ステップを実行する。
【００６１】
まず、復号装置１００は、現在の範囲Ｒａｎｇｅおよび優勢シンボルの発生確率ｐｒｏｂに基づいて境界値ｓｐｌｉｔを算出する（ステップＳ７０１）。ステップＳ７０１における境界値ｓｐｌｉｔの算出は、図５に示したステップＳ５０１と同様である。
【００６２】
つぎに、復号装置１００は、復号値として優勢シンボルである“０”を出力する（ステップＳ７０２）。つぎに、復号装置１００は、範囲Ｒａｎｇｅに境界値ｓｐｌｉｔの値を設定する（ステップＳ７０３）。また、復号装置１００は、一括復号ビット数Ｎをデクリメント（−１）する（ステップＳ７０４）。つぎに、復号装置１００は、優勢シンボルの発生確率ｐｒｏｂを、次のビット位置の発生確率に更新する（ステップＳ７０５）。
【００６３】
つぎに、復号装置１００は、一括復号ビット数Ｎが０になったか否かを判断する（ステップＳ７０６）。一括復号ビット数Ｎが０になっていない場合（ステップＳ７０６：Ｎｏ）は、復号装置１００は、ステップＳ７０１へ戻る。一括復号ビット数Ｎが０になった場合（ステップＳ７０６：Ｙｅｓ）は、復号装置１００は一連の処理を終了する。以上の各ステップにより、Ｎビットの復号値“０”を得ることができる。
【００６４】
（一括復号ビット数Ｎの算出処理）
図８は、一括復号ビット数Ｎの算出処理の一例を示すフローチャートである。復号装置１００は、図４に示したステップＳ４０５における一括復号ビット数Ｎの算出処理として、たとえば以下の各ステップを実行する。図８に示す差分Ｄｉｆｆは、再正規化が発生し、または復号値が“１”となるまでの範囲Ｒａｎｇｅの余剰を示す値である。まず、復号装置１００は、現在の符号値Ｖａｌｕｅと再正規化の閾値である１２８を比較し、符号値Ｖａｌｕｅが１２８未満であるか否かを判断する（ステップＳ８０１）。
【００６５】
符号値Ｖａｌｕｅが１２８未満である場合は、復号処理を繰り返した場合に、復号値が“１”となる以前に再正規化が発生すると判断することができる。このため、ステップＳ８０１において符号値Ｖａｌｕｅが１２８未満である場合（ステップＳ８０１：Ｙｅｓ）は、復号装置１００は、差分Ｄｉｆｆに範囲Ｒａｎｇｅと１２８の差分を設定し（ステップＳ８０２）、ステップＳ８０４へ移行する。これにより、再正規化が発生するまでの範囲Ｒａｎｇｅの余剰を差分Ｄｉｆｆに設定することができる。
【００６６】
符号値Ｖａｌｕｅが１２８以上である場合は、復号処理を繰り返した場合に、再正規化が発生する以前に復号値が“１”となると判断することができる。このため、ステップＳ８０１において符号値Ｖａｌｕｅが１２８以上である場合（ステップＳ８０１：Ｎｏ）は、復号装置１００は、差分Ｄｉｆｆに範囲Ｒａｎｇｅと符号値Ｖａｌｕｅの差分を設定し（ステップＳ８０３）、ステップＳ８０４へ移行する。これにより、復号値が“１”となるまでの範囲Ｒａｎｇｅの余剰を差分Ｄｉｆｆに設定することができる。
【００６７】
つぎに、復号装置１００は、復号対象のシンタクスに対応するグループＩＤを対応情報３１０から取得する（ステップＳ８０４）。つぎに、復号装置１００は、ステップＳ８０４によって取得したグループＩＤに対応する最小の発生確率ｐｒｏｂＧ（グループＩＤ）を対応情報３２０から取得する（ステップＳ８０５）。
【００６８】
つぎに、復号装置１００は、復号処理を１回行うことによる範囲Ｒａｎｇｅの減少量の最大値である減少値ＳｕｂＶａｌを算出する（ステップＳ８０６）。具体的には、復号装置１００は、現在の範囲Ｒａｎｇｅに、ステップＳ８０５によって取得した発生確率ｐｒｏｂＧ（グループＩＤ）を８ビットシフトさせた値を乗算し、乗算結果を現在の範囲Ｒａｎｇｅから減算することで減少値ＳｕｂＶａｌを算出する。
【００６９】
つぎに、復号装置１００は、ステップＳ８０６により算出した減少値ＳｕｂＶａｌを除数とし、差分Ｄｉｆｆを被除数として除算した商を一括復号ビット数Ｎとして算出し（ステップＳ８０７）、一連の処理を終了する。以上の各ステップにより、復号値が“０”となりかつ再正規化が発生しない最小の復号処理の回数を一括復号ビット数Ｎとして算出することができる。
【００７０】
（Ｎビット復号処理）
図９は、Ｎビット復号処理の一例を示す図である。図９において、範囲Ｒａｎｇｅ１〜ＲａｎｇｅＮは、それぞれ１〜Ｎ回目の復号処理における範囲Ｒａｎｇｅを示している。境界値ｓｐｌｉｔ１〜ｓｐｌｉｔＮは、それぞれ１〜Ｎ回目の復号処理における境界値ｓｐｌｉｔを示している。発生確率ｐｒｏｂ１〜Ｎは、それぞれ１〜Ｎ回目の復号処理における“０”の発生確率ｐｒｏｂである。
【００７１】
図９に示すように、１〜Ｎ回目の復号処理において範囲Ｒａｎｇｅは範囲Ｒａｎｇｅ１〜ＲａｎｇｅＮのように減少していく。そして、Ｎ回目の復号処理の範囲ＲａｎｇｅＮまで範囲Ｒａｎｇｅが符号値Ｖａｌｕｅより大きければ、１〜Ｎ回目の復号処理における各復号値は“０”となる。また、Ｎ回目の復号処理の範囲ＲａｎｇｅＮまで範囲Ｒａｎｇｅが１２８（閾値）以上であれば、１〜Ｎ回目の復号処理において再正規化が発生しない。
【００７２】
すなわち、復号値がＮ回連続して“０”となる条件は範囲ＲａｎｇｅＮ＞Ｖａｌｕｅである。また、Ｎ回の復号処理において再正規化が発生しない条件は範囲ＲａｎｇｅＮ≧１２８である。したがって、範囲ＲａｎｇｅＮ＞Ｖａｌｕｅおよび範囲ＲａｎｇｅＮ≧１２８を満たす場合はＮビット復号処理が可能と判定する。一方、範囲ＲａｎｇｅＮ＞Ｖａｌｕｅおよび範囲ＲａｎｇｅＮ≧１２８のいずれか一方でも満たさない場合はＮビット復号処理は不可と判定することができる。
【００７３】
（復号装置の構成）
図１０は、復号装置の構成の一例を示す図である。図１０に示すように、復号装置１００は、シンタクス情報管理ＦＦ１００１と、確率テーブル部１００２と、Ｒａｎｇｅ＿ＦＦ１００３と、Ｖａｌｕｅ＿ＦＦ１００４と、一括復号ビット数算出部１００５と、１ビット復号処理部１００６と、Ｎビット復号処理部１００７と、ＭＵＸ１００８と、逆二値化部１００９と、次シンタクス判定部１０１０と、を備えている。復号装置１００の復号対象のデータストリームは１ビット復号処理部１００６へ入力される。
【００７４】
シンタクス情報管理ＦＦ１００１は、復号対象のシンタクスのステートマシンである。シンタクス情報管理ＦＦ１００１は、初期状態において、復号対象のシンタクスの初期値を示すシンタクス情報を出力する。また、シンタクス情報管理ＦＦ１００１は、次シンタクス判定部１０１０から次の復号対象のシンタクス情報が入力されると、入力されたシンタクス情報を出力する。シンタクス情報管理ＦＦ１００１から出力されたシンタクス情報は、確率テーブル部１００２、一括復号ビット数算出部１００５および逆二値化部１００９へ入力される。
【００７５】
確率テーブル部１００２は、シンタクスごとの“０”の発生確率ｐｒｏｂを示す確率テーブルを有する。確率テーブル部１００２は、シンタクス情報管理ＦＦ１００１から出力されたシンタクス情報が示すシンタクスに対応する発生確率ｐｒｏｂを確率テーブルから取得する。そして、確率テーブル部１００２は、取得した発生確率ｐｒｏｂを１ビット復号処理部１００６およびＮビット復号処理部１００７へ出力する。
【００７６】
Ｒａｎｇｅ＿ＦＦ１００３は、現在の範囲Ｒａｎｇｅのステートマシンである。Ｒａｎｇｅ＿ＦＦ１００３は、初期状態において、２５５を現在の範囲Ｒａｎｇｅとして出力する。また、Ｒａｎｇｅ＿ＦＦ１００３は、ＭＵＸ１００８からＮｅｗＲａｎｇｅ２またはＮｅｗＲａｎｇｅ１が入力されると、入力されたＮｅｗＲａｎｇｅ１またはＮｅｗＲａｎｇｅ２を現在の範囲Ｒａｎｇｅとして出力する。Ｒａｎｇｅ＿ＦＦ１００３から出力された範囲Ｒａｎｇｅは、一括復号ビット数算出部１００５、１ビット復号処理部１００６およびＮビット復号処理部１００７へ入力される。
【００７７】
Ｖａｌｕｅ＿ＦＦ１００４は、現在の符号値Ｖａｌｕｅのステートマシンである。Ｖａｌｕｅ＿ＦＦ１００４は、初期状態において、データストリームの先頭の８ビットを符号値Ｖａｌｕｅとして出力する。また、Ｖａｌｕｅ＿ＦＦ１００４は、１ビット復号処理部１００６からＮｅｗＶａｌｕｅが入力されると、入力されたＮｅｗＶａｌｕｅを現在の符号値Ｖａｌｕｅとして出力する。Ｖａｌｕｅ＿ＦＦ１００４から出力された符号値Ｖａｌｕｅは、一括復号ビット数算出部１００５、１ビット復号処理部１００６およびＮビット復号処理部１００７へ入力される。
【００７８】
一括復号ビット数算出部１００５は、シンタクス情報管理ＦＦ１００１からのシンタクス情報と、Ｒａｎｇｅ＿ＦＦ１００３からの範囲Ｒａｎｇｅと、Ｖａｌｕｅ＿ＦＦ１００４からの符号値Ｖａｌｕｅと、に基づいて一括復号ビット数Ｎを算出する。一括復号ビット数算出部１００５は、算出した一括復号ビット数Ｎを、Ｎビット復号処理部１００７、ＭＵＸ１００８および逆二値化部１００９へ出力する。一括復号ビット数算出部１００５の構成例については後述する（たとえば図１３参照）。
【００７９】
１ビット復号処理部１００６は、確率テーブル部１００２からの発生確率ｐｒｏｂと、Ｒａｎｇｅ＿ＦＦ１００３からの範囲Ｒａｎｇｅと、Ｖａｌｕｅ＿ＦＦ１００４からの符号値Ｖａｌｕｅと、に基づいてデータストリームの１ビット復号処理を行う。１ビット復号処理部１００６は、１ビット復号処理により得られた復号値（１／０）を逆二値化部１００９へ出力する。また、１ビット復号処理部１００６は、１ビット復号処理後の符号値ＶａｌｕｅをＮｅｗＶａｌｕｅとしてＶａｌｕｅ＿ＦＦ１００４へ出力する。また、１ビット復号処理部１００６は、１ビット復号処理後の範囲ＲａｎｇｅをＮｅｗＲａｎｇｅ１としてＭＵＸ１００８へ出力する。
【００８０】
Ｎビット復号処理部１００７には、確率テーブル部１００２からの発生確率ｐｒｏｂと、Ｒａｎｇｅ＿ＦＦ１００３からの範囲Ｒａｎｇｅと、が入力される。また、Ｎビット復号処理部１００７には、一括復号ビット数算出部１００５からの一括復号ビット数Ｎと、Ｖａｌｕｅ＿ＦＦ１００４からの符号値Ｖａｌｕｅと、が入力される。
【００８１】
Ｎビット復号処理部１００７は、入力された発生確率ｐｒｏｂ、範囲Ｒａｎｇｅ、一括復号ビット数Ｎおよび符号値Ｖａｌｕｅに基づいてデータストリームのＮビット復号処理を行う。また、Ｎビット復号処理部１００７は、Ｎビット復号処理後の範囲ＲａｎｇｅをＮｅｗＲａｎｇｅ２としてＭＵＸ１００８へ出力する。
【００８２】
また、Ｎビット復号処理部１００７は、ＮｅｗＲａｎｇｅ２＞符号値ＶａｌｕｅおよびＮｅｗＲａｎｇｅ２≧１２８の少なくともいずれかを満たさない場合にＮ＿ｂｉｔ＿ｅｒｒをＭＵＸ１００８および逆二値化部１００９へ出力してもよい。Ｎビット復号処理部１００７の構成例については後述する（たとえば図１２参照）。
【００８３】
ＭＵＸ１００８には、１ビット復号処理部１００６からのＮｅｗＲａｎｇｅ１と、Ｎビット復号処理部１００７からのＮｅｗＲａｎｇｅ２と、が入力される。ＭＵＸ１００８は、一括復号ビット数算出部１００５から出力された一括復号ビット数Ｎが０である場合は、１ビット復号処理部１００６からのＮｅｗＲａｎｇｅ１をＲａｎｇｅ＿ＦＦ１００３へ出力する。また、ＭＵＸ１００８は、一括復号ビット数算出部１００５から出力された一括復号ビット数Ｎが１以上である場合は、Ｎビット復号処理部１００７からのＮｅｗＲａｎｇｅ２をＲａｎｇｅ＿ＦＦ１００３へ出力する。
【００８４】
また、ＭＵＸ１００８は、Ｎビット復号処理部１００７からＮ＿ｂｉｔ＿ｅｒｒが出力された場合は、一括復号ビット数Ｎが１以上であっても１ビット復号処理部１００６からのＮｅｗＲａｎｇｅ１をＲａｎｇｅ＿ＦＦ１００３へ出力するようにしてもよい。これにより、Ｎビットを一括復号するとグループを跨いでしまう場合は、一括復号ビット数Ｎが１以上であっても１ビット復号結果を用いることができる。
【００８５】
逆二値化部１００９は、シンタクス情報管理ＦＦ１００１から出力されるシンタクス情報に基づいて復号値を逆二値化する。具体的には、一括復号ビット数算出部１００５から出力された一括復号ビット数Ｎが０である場合は、１ビット復号処理部１００６から出力された復号値を逆二値化する。また、逆二値化部１００９は、一括復号ビット数算出部１００５から出力された一括復号ビット数Ｎが１以上である場合は、一括復号ビット数Ｎだけ連続する“０”を復号値として逆二値化する。
【００８６】
逆二値化部１００９は、逆二値化したデータを復号データとして出力する。逆二値化部１００９から出力された復号データは、復号結果として復号装置１００から出力される。また、復号データは次シンタクス判定部１０１０へ入力される。また、逆二値化部１００９は、Ｎビット復号処理部１００７からＮ＿ｂｉｔ＿ｅｒｒが出力された場合は、一括復号ビット数Ｎが１以上であっても１ビット復号処理部１００６から出力された復号値を逆二値化してもよい。これにより、Ｎビットを一括復号するとグループを跨いでしまう場合は、一括復号ビット数Ｎが１以上であっても１ビット復号結果を用いることができる。
【００８７】
次シンタクス判定部１０１０は、逆二値化部１００９から出力された復号データに基づいて次の復号対象のシンタクスを判定する。次シンタクス判定部１０１０は、判定したシンタクスを示すシンタクス情報をシンタクス情報管理ＦＦ１００１へ出力する。
【００８８】
このように、マルチコンテキスト型の算術符号に対応する復号装置１００において、グループごとに一つの発生確率を用いて一括復号ビット数Ｎを算出することができる。これにより、一括復号ビット数Ｎを算出するためにＮビット復号処理部１００７と同等の回路を設けなくても、一括復号ビット数Ｎを算出することが可能になり、回路規模を小さくすることができる。
【００８９】
図１０に示したＲａｎｇｅ＿ＦＦ１００３は、範囲Ｒａｎｇｅ（数値範囲）を記憶する記憶部である。記憶部は、たとえば図２に示したメインメモリ２２０、補助メモリ２３０などによって実現してもよい。確率テーブル部１００２は、復号データの各位置における“０”（所定シンボル）の発生確率を取得する取得部である。取得部は、たとえば図２に示したＣＰＵ２１０、メインメモリ２２０、通信インタフェース２５０などによって実現してもよい。
【００９０】
一括復号ビット数算出部１００５は、確率テーブル部１００２で取得された発生確率のうちの、復号対象の位置が属するグループにおける最小の発生確率を特定する特定部である。また、一括復号ビット数算出部１００５は、特定した発生確率に相当する割合で範囲Ｒａｎｇｅを縮小した場合における範囲Ｒａｎｇｅの減少幅を算出する算出部である。また、一括復号ビット数算出部１００５は、範囲Ｒａｎｇｅの限界値と符号値Ｖａｌｕｅとの差分を、算出した減少幅によって除算した商を算出する除算部である。特定部、算出部および除算部は、たとえば図２に示したＣＰＵ２１０によって実現してもよい。
【００９１】
Ｎビット復号処理部１００７は、一括復号ビット数算出部１００５によって算出された商が１（所定値）以上である場合に、商だけ連続する“０”（所定シンボル）となる復号結果を出力する一括復号処理部である。一括復号処理部は、たとえば図２に示したＣＰＵ２１０によって実現してもよい。また、Ｎビット復号処理部１００７は、一括復号ビット数算出部１００５によって算出された商が１以上である場合に、減少幅に商を乗じた幅だけ範囲Ｒａｎｇｅを縮小する縮小部である。縮小部は、たとえば図２に示したＣＰＵ２１０によって実現してもよい。
【００９２】
１ビット復号処理部１００６は、一括復号ビット数算出部１００５によって算出された商が１未満である場合に、範囲Ｒａｎｇｅと、復号対象の位置における発生確率と、符号値Ｖａｌｕｅと、に基づいて復号対象の位置を復号する個別復号処理部である。個別復号処理部は、たとえば図２に示したＣＰＵ２１０によって実現してもよい。また、１ビット復号処理部１００６は、復号結果と、復号対象の位置における発生確率と、に応じて範囲Ｒａｎｇｅを縮小する縮小部である。また、１ビット復号処理部１００６は、縮小した範囲Ｒａｎｇｅの限界値が１２８（閾値）を下回った場合に、範囲Ｒａｎｇｅおよび符号値Ｖａｌｕｅを同一比率で増大させる再正規化を行う再正規化部である。再正規化部は、たとえば図２に示したＣＰＵ２１０によって実現してもよい。
【００９３】
（１ビット復号処理部の構成）
図１１は、１ビット復号処理部の構成の一例を示す図である。図１１に示すように、１ビット復号処理部１００６は、減算部１１０１と、乗算部１１０２と、シフト部１１０３と、加算部１１０４と、減算部１１０５，１１０６と、比較部１１０７と、ＭＵＸ１１０８，１１０９と、再正規化制御部１１１０と、シフト部１１１１，１１１２と、シフト部１１１３と、ＯＲ部１１１４と、を備えている。
【００９４】
データストリームは、シフト部１１１３へ入力される。確率テーブル部１００２（図１０参照）からの発生確率ｐｒｏｂは、乗算部１１０２へ入力される。Ｒａｎｇｅ＿ＦＦ１００３（図１０参照）からの範囲Ｒａｎｇｅは、減算部１１０１および減算部１１０５へ出力される。Ｖａｌｕｅ＿ＦＦ１００４（図１０参照）からの符号値Ｖａｌｕｅは、減算部１１０６、比較部１１０７およびＭＵＸ１１０９へ出力される。
【００９５】
減算部１１０１は、Ｒａｎｇｅ＿ＦＦ１００３からの範囲Ｒａｎｇｅを１で減算し、減算結果を乗算部１１０２へ出力する。乗算部１１０２は、確率テーブル部１００２からの発生確率ｐｒｏｂと、減算部１１０１から出力された値と、を乗算する。乗算部１１０２は、乗算結果をシフト部１１０３へ出力する。
【００９６】
シフト部１１０３は、乗算部１１０２から出力された値を８ビットシフトさせ、８ビットシフトさせた値を加算部１１０４へ出力する。加算部１１０４は、シフト部１１０３から出力された値に１を加算し、加算結果を境界値ｓｐｌｉｔとして出力する。加算部１１０４から出力された境界値ｓｐｌｉｔは、減算部１１０５，１１０６、比較部１１０７およびＭＵＸ１１０８へ入力される。
【００９７】
減算部１１０５は、Ｒａｎｇｅ＿ＦＦ１００３からの範囲Ｒａｎｇｅから、加算部１１０４から出力された境界値ｓｐｌｉｔを減算し、減算結果をＭＵＸ１１０８へ出力する。減算部１１０６は、Ｖａｌｕｅ＿ＦＦ１００４からの符号値Ｖａｌｕｅから、加算部１１０４から出力された境界値ｓｐｌｉｔを減算し、減算結果をＭＵＸ１１０８へ出力する。
【００９８】
比較部１１０７は、Ｖａｌｕｅ＿ＦＦ１００４からの符号値Ｖａｌｕｅと、加算部１１０４から出力された境界値ｓｐｌｉｔと、を比較し、符号値Ｖａｌｕｅが境界値ｓｐｌｉｔ以上であるか否かを判断する。比較部１１０７は、符号値Ｖａｌｕｅが境界値ｓｐｌｉｔ以上である場合は“１”を出力し、符号値Ｖａｌｕｅが境界値ｓｐｌｉｔ未満である場合は“０”を出力する。比較部１１０７から出力された値はＭＵＸ１１０８，１１０９へ出力される。また、比較部１１０７から出力された値は、１ビット復号処理による復号値（１／０）として逆二値化部１００９（図１０参照）へ出力される。
【００９９】
ＭＵＸ１１０８は、比較部１１０７から“１”が出力された場合は減算部１１０５から出力された値を範囲Ｒａｎｇｅとして出力する。また、ＭＵＸ１１０８は、比較部１１０７から“０”が出力された場合は加算部１１０４から出力された境界値ｓｐｌｉｔを範囲Ｒａｎｇｅとして出力する。ＭＵＸ１１０８から出力された範囲Ｒａｎｇｅは再正規化制御部１１１０およびシフト部１１１１へ出力される。
【０１００】
ＭＵＸ１１０９は、比較部１１０７から“１”が出力された場合は減算部１１０６からの値を符号値Ｖａｌｕｅとして出力する。また、ＭＵＸ１１０９は、比較部１１０７から“０”が出力された場合はＶａｌｕｅ＿ＦＦ１００４からの符号値Ｖａｌｕｅを出力する。ＭＵＸ１１０９から出力された符号値Ｖａｌｕｅはシフト部１１１２へ出力される。
【０１０１】
再正規化制御部１１１０（Ｒｅｎｏｒｍ：Ｒｅｎｏｒｍａｌｉｚａｔｉｏｎ）は、ＭＵＸ１１０８から出力された範囲Ｒａｎｇｅに基づいて、再正規化を実行する回数を算出する。たとえば再正規化の閾値が１２８である場合は、再正規化制御部１１１０は、１２８を範囲Ｒａｎｇｅで除算した商を再正規化を実行する回数として算出する。再正規化制御部１１１０は、算出した回数をシフト量としてシフト部１１１１，１１１２およびシフト部１１１３へ出力する。
【０１０２】
シフト部１１１１は、ＭＵＸ１１０８から出力された範囲Ｒａｎｇｅを、再正規化制御部１１１０から出力されたシフト量（ビット数）だけシフトさせる。シフト部１１１１は、シフトさせた範囲ＲａｎｇｅをＮｅｗＲａｎｇｅ１としてＲａｎｇｅ＿ＦＦ１００３（図１０参照）へ出力する。シフト部１１１２は、ＭＵＸ１１０９から出力された符号値Ｖａｌｕｅを、再正規化制御部１１１０から出力されたシフト量（ビット数）だけシフトさせ、シフトさせた符号値ＶａｌｕｅをＯＲ部１１１４へ出力する。
【０１０３】
シフト部１１１３は、入力されたビットストリームを、再正規化制御部１１１０から出力されたシフト量（ビット数）だけ読み出す。そして、シフト部１１１３は、読み出したビットをＯＲ部１１１４へ出力する。ＯＲ部１１１４は、シフト部１１１２から出力された符号値Ｖａｌｕｅと、シフト部１１１３から出力されたビットと、の和をＮｅｗＶａｌｕｅとしてＶａｌｕｅ＿ＦＦ１００４（図１０参照）へ出力する。
【０１０４】
（Ｎビット復号装置の構成）
図１２は、Ｎビット復号装置の構成の一例を示す図である。図１２に示すように、Ｎビット復号処理部１００７は、Ｍ個（Ｍ≧Ｎ）のＭＵＸ１２１１〜１２１Ｍと、Ｍ個の境界値算出部１２２１〜１２２Ｍと、範囲チェック部１２３０と、を備えている。
【０１０５】
ＭＵＸ１２１１〜１２１Ｍには、それぞれ発生確率ｐｒｏｂ＿１〜ｐｒｏｂ＿Ｍが入力される。発生確率ｐｒｏｂ＿１〜ｐｒｏｂ＿Ｍは、それぞれ１〜Ｍビット目における“０”の発生確率ｐｒｏｂである。また、ＭＵＸ１２１１〜１２１Ｍには、それぞれ２５６の値が入力される。また、ＭＵＸ１２１１〜１２１Ｍには、一括復号ビット数算出部１００５から出力された一括復号ビット数Ｎが入力される。
【０１０６】
ＭＵＸ１２１１〜１２１Ｍのうちの１〜Ｎ番目のＭＵＸ１２１１〜１２１Ｎは、それぞれ入力された発生確率ｐｒｏｂ＿１〜ｐｒｏｂ＿Ｎを発生確率ｐｒｏｂとしてそれぞれ境界値算出部１２２１〜１２２Ｎへ出力する。一方、ＭＵＸ１２１１〜１２１ＭのうちのＮ＋１〜Ｍ番目のＭＵＸ１２１（Ｎ＋１）〜１２１Ｍは、入力された２５６を発生確率ｐｒｏｂとしてそれぞれ境界値算出部１２２（Ｎ＋１）〜１２２Ｍへ出力する。
【０１０７】
境界値算出部１２２１は、Ｒａｎｇｅ＿ＦＦ１００３から出力された範囲Ｒａｎｇｅと、ＭＵＸ１２１１から出力された発生確率ｐｒｏｂと、に基づいて１ビット目の復号処理後の境界値ｓｐｌｉｔを算出する。境界値算出部１２２１は、算出した境界値ｓｐｌｉｔを境界値算出部１２２２へ出力する。
【０１０８】
境界値算出部１２２２は、境界値算出部１２２１から出力された境界値ｓｐｌｉｔを範囲Ｒａｎｇｅとし、ＭＵＸ１２１２から出力された発生確率ｐｒｏｂに基づいて２ビット目の復号処理後の境界値ｓｐｌｉｔを算出する。境界値算出部１２２２は、算出した境界値ｓｐｌｉｔを境界値算出部１２２３へ出力する。
【０１０９】
同様に、境界値算出部１２２３〜１２２Ｍは、前段の境界値算出部から出力された境界値ｓｐｌｉｔを範囲Ｒａｎｇｅとし、ＭＵＸ１２１３〜１２１Ｍから出力された発生確率ｐｒｏｂに基づいて３〜Ｍビット目の復号処理後の境界値ｓｐｌｉｔを算出する。
【０１１０】
ここで、境界値算出部１２２（Ｎ＋１）〜１２２Ｍは、入力される発生確率が２５６となっているため、前段の境界値算出部から出力された境界値ｓｐｌｉｔを変更せずに後段の境界値算出部へ出力することになる。このように、境界値算出部１２２１〜１２２Ｍの前段で入力を選択しておくことにより、後段に必要とされる境界値算出部ごとの比較器と、比較結果をまとめるプライオリティエンコーダ、その出力によって最終データの選択を行うＭｔｏ１セレクタが不要となるため、Ｎビット復号処理部１００７における一括復号処理を高速化することができる。境界値算出部１２２Ｍから出力された境界値ｓｐｌｉｔは、ＮｅｗＲａｎｇｅ２としてＭＵＸ１００８（図１０参照）へ出力されるとともに範囲チェック部１２３０へ入力される。
【０１１１】
範囲チェック部１２３０には、Ｖａｌｕｅ＿ＦＦ１００４（図１０参照）からの符号値Ｖａｌｕｅと、１２８の値と、境界値算出部１２２Ｍからの境界値ｓｐｌｉｔと、が入力される。範囲チェック部１２３０は、ＮｅｗＲａｎｇｅ２＞符号値ＶａｌｕｅおよびＮｅｗＲａｎｇｅ２≧１２８を満たす場合はＮ＿ｂｉｔ＿ｅｒｒを出力しない。また、範囲チェック部１２３０は、ＮｅｗＲａｎｇｅ２＞符号値ＶａｌｕｅおよびＮｅｗＲａｎｇｅ２≧１２８の少なくともいずれかを満たさない場合はＮ＿ｂｉｔ＿ｅｒｒを出力する。範囲チェック部１２３０から出力されたＮ＿ｂｉｔ＿ｅｒｒは、ＭＵＸ１００８および逆二値化部１００９（図１０参照）へ出力される。
【０１１２】
（一括復号ビット数算出部の構成）
図１３は、一括復号ビット数算出部の構成の一例を示す図である。図１３に示すように、一括復号ビット数算出部１００５は、比較部１３０１と、減算部１３０２、減算部１３０３と、ＭＵＸ１３０４と、グループＩＤ＿ＬＵＴ部１３０５と、ｐｒｏｂＧ＿ＬＵＴ部１３０６と、乗算部１３０７と、シフト部１３０８と、減算部１３０９と、除算部１３１０と、を備えている。
【０１１３】
比較部１３０１は、Ｖａｌｕｅ＿ＦＦ１００４から出力された符号値Ｖａｌｕｅと、１２８の値と、を比較する。比較部１３０１は、比較結果をＭＵＸ１３０４へ出力する。減算部１３０２は、Ｒａｎｇｅ＿ＦＦ１００３から出力された範囲Ｒａｎｇｅから、１２８の値を減算する。減算部１３０２は、減算結果をＭＵＸ１３０４へ出力する。減算部１３０３は、Ｒａｎｇｅ＿ＦＦ１００３から出力された範囲Ｒａｎｇｅから、Ｖａｌｕｅ＿ＦＦ１００４から出力された符号値を減算する。減算部１３０３は、減算結果をＭＵＸ１３０４へ出力する。
【０１１４】
ＭＵＸ１３０４は、符号値Ｖａｌｕｅが１２８未満である旨の比較結果が比較部１３０１から出力された場合は、減算部１３０２から出力された減算結果を差分Ｄｉｆｆとして出力する。また、ＭＵＸ１３０４は、符号値Ｖａｌｕｅが１２８以上である旨の比較結果が比較部１３０１から出力された場合は、減算部１３０３から出力された減算結果を差分Ｄｉｆｆとして除算部１３１０へ出力する。
【０１１５】
グループＩＤ＿ＬＵＴ部１３０５（Ｌｏｏｋ Ｕｐ Ｔａｂｌｅ：ルックアップテーブル）は、シンタクスとグループＩＤとの対応情報（たとえば図３−１の対応情報３１０）を記憶している。グループＩＤ＿ＬＵＴ部１３０５は、シンタクス情報管理ＦＦ１００１から出力されたシンタクス情報が示すシンタクスに対応するグループＩＤを対応情報から取得し、取得したグループＩＤをｐｒｏｂＧ＿ＬＵＴ部１３０６へ出力する。
【０１１６】
ｐｒｏｂＧ＿ＬＵＴ部１３０６は、グループＩＤと発生確率ｐｒｏｂＧとの対応情報（たとえば図３−２の対応情報３２０）を記憶している。ｐｒｏｂＧ＿ＬＵＴ部１３０６は、グループＩＤ＿ＬＵＴ部１３０５から出力されたグループＩＤが示すシンタクスに対応する最小の発生確率ｐｒｏｂＧ（グループＩＤ）を対応情報から取得し、取得した発生確率ｐｒｏｂＧ（グループＩＤ）を乗算部１３０７へ出力する。
【０１１７】
乗算部１３０７は、Ｒａｎｇｅ＿ＦＦ１００３から出力された範囲Ｒａｎｇｅと、ｐｒｏｂＧ＿ＬＵＴ部１３０６から出力された発生確率ｐｒｏｂＧ（グループＩＤ）と、を乗算する。乗算部１３０７は、乗算結果をシフト部１３０８へ出力する。シフト部１３０８は、乗算部１３０７から出力された値を８ビットシフトさせる。シフト部１３０８は、８ビットシフトさせた値を減算部１３０９へ出力する。
【０１１８】
減算部１３０９は、Ｒａｎｇｅ＿ＦＦ１００３から出力された範囲Ｒａｎｇｅを、シフト部１３０８から出力された値で減算する。減算部１３０９は、減算結果を減少値ＳｕｂＶａｌとして除算部１３１０へ出力する。除算部１３１０は、ＭＵＸ１３０４から出力された差分Ｄｉｆｆを、減算部１３０９から出力された減少値ＳｕｂＶａｌで除算する。除算部１３１０は、除算結果の商を一括復号ビット数Ｎとして出力する。
【０１１９】
このように、実施の形態１にかかる復号装置１００によれば、優勢シンボルの発生確率をグループ分けし、復号対象が属するグループの最小の発生確率に基づいて優勢シンボルの連続数を算出し、算出結果に基づいて一括復号を行うことができる。これにより、一括復号の実施確率を高くし、復号処理の高速化の確率を高めることができる。
【０１２０】
（実施の形態２）
実施の形態２においては、実施の形態１と異なる部分について説明する。
【０１２１】
（グループＩＤと減少値の対応情報）
図１４は、グループＩＤと減少値の対応情報の一例を示す図である。図１４に示す対応情報１４００は、グループＩＤと減少値とを対応付ける対応情報である。対応情報１４００は、たとえば復号装置１００のメインメモリ２２０や補助メモリ２３０に記憶されている。対応情報１４００に示す最大の減少値ＳｕｂＶａｌＧ（０）〜ＳｕｂＶａｌＧ（Ｙ）は、それぞれグループＩＤ「０」〜「Ｙ」が示すグループに属する各シンタクスの復号処理において、範囲Ｒａｎｇｅの最大の減少値ＳｕｂＶａｌを示している。
【０１２２】
実施の形態１においては、図８に示したように、復号処理ごとに変化する範囲Ｒａｎｇｅ（≦２５５）に基づいて減少値ＳｕｂＶａｌが算出される。これに対して、実施の形態２においては、範囲Ｒａｎｇｅが常に２５５であると仮定して減少値ＳｕｂＶａｌＧ（０）〜ｐｒｏｂＧ（Ｙ）が予め算出され、対応情報１４００として記憶されている。この場合は、図３−２に示した対応情報３２０は復号装置１００に記憶されていなくてもよい。このように、実施の形態２においては、シンボル発生確率ではなく、数直線幅に換算した値を直接設定しておく。
【０１２３】
（一括復号ビット数Ｎの算出処理）
図１５は、一括復号ビット数Ｎの算出処理の一例を示すフローチャートである。実施の形態２にかかる復号装置１００は、図４に示したステップＳ４０５における一括復号ビット数Ｎの算出処理として、たとえば図１５に示す各ステップを実行する。
【０１２４】
図１５に示すステップＳ１５０１〜Ｓ１５０４は、図８に示したステップＳ８０１〜Ｓ８０４と同様である。ステップＳ１５０４のつぎに、復号装置１００は、ステップＳ１５０４によって取得したグループＩＤに対応する減少値ＳｕｂＶａｌＧ（グループＩＤ）を減少値ＳｕｂＶａｌとして対応情報１４００から取得する（ステップＳ１５０５）。
【０１２５】
つぎに、復号装置１００は、ステップＳ１５０５により算出した減少値ＳｕｂＶａｌを除数とし、差分Ｄｉｆｆを被除数として除算した商をＮとして算出し（ステップＳ１５０６）、一連の処理を終了する。これにより、復号値が“０”となりかつ再正規化が発生しない最小の復号処理の回数をＮとして算出することができる。
【０１２６】
また、対応情報１４００を用いることで、復号処理ごとに減少値ＳｕｂＶａｌを算出しなくても一括復号ビット数Ｎを算出することができるため、計算量を少なくすることができる。なお、実施の形態２においては、現在の範囲Ｒａｎｇｅに基づく減少値ＳｕｂＶａｌの算出を行わず、範囲Ｒａｎｇｅの最大値に基づく減少値ＳｕｂＶａｌを用いるため、実施の形態１に比べて一括復号ビット数Ｎが小さくなる傾向となる。
【０１２７】
（実施の形態２にかかる一括復号ビット数算出部の構成）
図１６は、実施の形態２にかかる一括復号ビット数算出部の構成の一例を示す図である。図１６において、図１３に示した部分と同様の部分については同一の符号を付して説明を省略する。図１６に示すように、実施の形態２にかかる一括復号ビット数算出部１００５は、対応情報１４００を用いることで復号対象の位置が属するグループに対応する減少幅を導出する導出部である。具体的には、実施の形態２にかかる一括復号ビット数算出部１００５は、図１３に示したｐｒｏｂＧ＿ＬＵＴ部１３０６、乗算部１３０７、シフト部１３０８および減算部１３０９に代えてＳｕｂＶａｌ＿ＬＵＴ部１６０１を備えている。
【０１２８】
ＳｕｂＶａｌ＿ＬＵＴ部１６０１は、グループＩＤと減少値ｐｒｏｂＧとの対応情報（たとえば図１４に示した対応情報１４００）を記憶している。ＳｕｂＶａｌ＿ＬＵＴ部１６０１は、シンタクス情報管理ＦＦ１００１から出力されたシンタクス情報が示すシンタクスに対応する減少値ＳｕｂＶａｌＧ（グループＩＤ）を対応情報から取得する。そして、ＳｕｂＶａｌ＿ＬＵＴ部１６０１は、取得した減少値ＳｕｂＶａｌＧ（グループＩＤ）を減少値ＳｕｂＶａｌとして除算部１３１０へ出力する。
【０１２９】
除算部１３１０は、ＭＵＸ１３０４から出力された差分Ｄｉｆｆを、ＳｕｂＶａｌ＿ＬＵＴ部１６０１から出力された減少値ＳｕｂＶａｌで除算する。除算部１３１０は、除算結果の商を一括復号ビット数Ｎとして出力する。
【０１３０】
このように、対応情報１４００を用いることで、復号処理ごとに減少値ＳｕｂＶａｌを算出しなくても一括復号ビット数Ｎを算出することができるため、一括復号ビット数算出部１００５の回路規模を小さくすることができる。
【０１３１】
このように、実施の形態２にかかる復号装置１００においては、グループごとに、グループにおける最小の発生確率に相当する割合で範囲Ｒａｎｇｅを縮小した場合における範囲Ｒａｎｇｅの減少幅が対応付けられた対応情報１４００を用意しておく。そして、復号装置１００は、対応情報１４００を用いることで、復号対象の位置が属するグループに対応する減少幅を導出する。これにより、復号処理ごとに減少値を算出しなくても一括復号ビット数Ｎを算出することができるため、計算量を少なくすることができる。
【０１３２】
（符号化処理）
図１７は、符号化処理の一例を示すフローチャートである。復号装置１００の復号対象のビットストリームを生成する符号化装置は、たとえば以下の各ステップを実行する。図１７において、下限値ｌｏｗｖａｌｕｅは範囲Ｒａｎｇｅの下限値である。下限値ｌｏｗｖａｌｕｅの初期値は０とする。範囲Ｒａｎｇｅの初期値は２５５とする。カウント値ｃｏｕｎｔの初期値は０とする。まず、符号化装置は、現在の範囲Ｒａｎｇｅと、符号化対象の１ビットにおける優勢シンボルの発生確率ｐｒｏｂに基づいて境界値ｓｐｌｉｔを算出する（ステップＳ１７０１）。
【０１３３】
つぎに、符号化装置は、符号化対象の値が“１”であるか否かを判断する（ステップＳ１７０２）。符号化対象の値が“１”である場合（ステップＳ１７０２：Ｙｅｓ）は、符号化装置は、ステップＳ１７０１によって算出した境界値ｓｐｌｉｔを下限値ｌｏｗｖａｌｕｅに加算する（ステップＳ１７０３）。また、符号化装置は、ステップＳ１７０１によって算出した境界値ｓｐｌｉｔを範囲Ｒａｎｇｅから減算し（ステップＳ１７０４）、ステップＳ１７０６へ移行する。
【０１３４】
ステップＳ１７０２において、符号化対象の値が“１”でない場合（ステップＳ１７０２：Ｎｏ）は、符号化装置は、ステップＳ１７０１によって算出した境界値ｓｐｌｉｔを範囲Ｒａｎｇｅに設定し（ステップＳ１７０５）、ステップＳ１７０６へ移行する。
【０１３５】
つぎに、符号化装置は、範囲Ｒａｎｇｅが１２８未満であるか否かを判断する（ステップＳ１７０６）。範囲Ｒａｎｇｅが１２８以上である場合（ステップＳ１７０６：Ｎｏ）は、符号化装置は、一連の処理を終了する。範囲Ｒａｎｇｅが１２８未満である場合（ステップＳ１７０６：Ｙｅｓ）は、符号化装置は、再正規化処理を実行し（ステップＳ１７０７）、一連の処理を終了する。ステップＳ１７０７による再正規化処理については後述する（たとえば図１８参照）。
【０１３６】
図１８は、符号化処理における再正規化処理の一例を示すフローチャートである。符号化装置は、図１７に示したステップＳ１７０７による再正規化処理として、たとえば図１７に示す各ステップを実行する。まず、符号化装置は、範囲Ｒａｎｇｅが１２８以上か否かを判断する（ステップＳ１８０１）。
【０１３７】
ステップＳ１８０１において、範囲Ｒａｎｇｅが１２８以上である場合（ステップＳ１８０１：Ｙｅｓ）は、符号化装置は、下限値ｌｏｗｖａｌｕｅが１２８未満であるか否かを判断する（ステップＳ１８０２）。下限値ｌｏｗｖａｌｕｅが１２８未満である場合（ステップＳ１８０２：Ｙｅｓ）は、符号化装置は、引数ｘを“０”とするライト処理を実行し（ステップＳ１８０３）、ステップＳ１８０９へ移行する。ライト処理については後述する（たとえば図１９参照）。
【０１３８】
ステップＳ１８０２において、下限値ｌｏｗｖａｌｕｅが１２８以上である場合（ステップＳ１８０２：Ｎｏ）は、符号化装置は、下限値ｌｏｗｖａｌｕｅが２５６以上であるか否かを判断する（ステップＳ１８０４）。下限値ｌｏｗｖａｌｕｅが２５６未満である場合（ステップＳ１８０４：Ｎｏ）は、符号化装置は、下限値ｌｏｗｖａｌｕｅから１２８を減算する（ステップＳ１８０５）。また、符号化装置は、カウント値ｃｏｕｎｔに１を加算し（ステップＳ１８０６）、ステップＳ１８０９へ移行する。
【０１３９】
ステップＳ１８０４において、下限値ｌｏｗｖａｌｕｅが２５６以上である場合（ステップＳ１８０４：Ｙｅｓ）は、符号化装置は、下限値ｌｏｗｖａｌｕｅから２５６を減算する（ステップＳ１８０７）。つぎに、符号化装置は、引数ｘを“１”とするライト処理を実行し（ステップＳ１８０８）、ステップＳ１８０９へ移行する。ライト処理については後述する（たとえば図１９参照）。
【０１４０】
つぎに、符号化装置は、範囲Ｒａｎｇｅを１ビット左シフトさせる（ステップＳ１８０９）。また、符号化装置は、下限値ｌｏｗｖａｌｕｅを１ビット左シフトさせ（ステップＳ１８１０）、ステップＳ１８０１へ戻る。ステップＳ１８０１において、範囲Ｒａｎｇｅが１２８未満である場合（ステップＳ１８０１：Ｎｏ）は、符号化装置は、一連の再正規化処理を終了する。
【０１４１】
図１９は、再正規化処理におけるライト処理の一例を示すフローチャートである。符号化装置は、図１８のステップＳ１８０３，Ｓ１８０８におけるライト処理として、図１９に示す各ステップを実行する。まず、符号化装置は、ＦｉｒｓｔＦｌａｇが０であるか否かを判断する（ステップＳ１９０１）。ＦｉｒｓｔＦｌａｇが０である場合（ステップＳ１９０１：Ｙｅｓ）は、符号化装置は、ＦｉｒｓｔＦｌａｇに０を設定し（ステップＳ１９０２）、ステップＳ１９０４へ移行する。
【０１４２】
ステップＳ１９０１において、ＦｉｒｓｔＦｌａｇが０でない場合（ステップＳ１９０１：Ｎｏ）は、符号化装置は、符号値として引数“ｘ”を出力し（ステップＳ１９０３）、ステップＳ１９０４へ移行する。つぎに、符号化装置は、カウント値ｃｏｕｎｔが０より大きいか否かを判断する（ステップＳ１９０４）。
【０１４３】
ステップＳ１９０４において、カウント値ｃｏｕｎｔが０より大きい場合（ステップＳ１９０４：Ｙｅｓ）は、符号化装置は、符号値として引数“１−ｘ”を出力する（ステップＳ１９０５）。また、符号化装置は、カウント値ｃｏｕｎｔをデクリメント（−１）し（ステップＳ１９０６）、ステップＳ１９０４へ戻る。ステップＳ１９０４において、カウント値ｃｏｕｎｔが０より大きくない場合（ステップＳ１９０４：Ｎｏ）は、符号化装置は、一連の処理を終了する。
【０１４４】
（符号化の具体例）
ここでは、符号化対象の最初のシンタクスがＳｙｎｔａｘＡ（８ビット）であり、ＳｙｎｔａｘＡの次のシンタクスがＳｙｎｔａｘＢ（８ビット）であるとする。ＳｙｎｔａｘＡの各ビット位置ｋにおける“０”の発生確率は、ＰｒｏｂＴａｂｌｅＡ［ｋ］＝｛２１７，２２３，２４５，２４５，２４４，２４２，２４４，２４５｝とする。ＳｙｎｔａｘＢの各ビット位置ｋにおける“０”の発生確率は、ＰｒｏｂＴａｂｌｅＢ［ｋ］＝｛２３４，２５１，２４４，２５４，２１６，１９９，１７９，２３３｝とする。ｓｐｌｉｔ計算式には下記（１）式を用いるとする。
【０１４５】
ｓｐｌｉｔ＝１＋（（（Ｒａｎｇｅ−１）＊ｐｒｏｂ）＞＞８） …（１）
【０１４６】
また、たとえばＳｙｎｔａｘＡ＝“００００００１０”とする。ＳｙｎｔａｘＡのビット位置０（０）の符号化は下記（２）式のようになる。
【０１４７】
ｓｐｌｉｔ＝１＋（（（２５５−１）＊２１７）＞＞８）＝２１６
Ｒａｎｇｅ＝ｓｐｌｉｔ＝２１６ …（２）
【０１４８】
ＳｙｎｔａｘＡのビット位置１（０）の符号化は下記（３）式のようになる。
【０１４９】
ｓｐｌｉｔ＝１＋（（（２１６−１）＊２２３）＞＞８）＝１８８
Ｒａｎｇｅ＝ｓｐｌｉｔ＝１８８ …（３）
【０１５０】
ＳｙｎｔａｘＡのビット位置２（０）の符号化は下記（４）式のようになる。
【０１５１】
ｓｐｌｉｔ＝１＋（（（１８８−１）＊２４５）＞＞８）＝１７９
Ｒａｎｇｅ＝ｓｐｌｉｔ＝１７９ …（４）
【０１５２】
ＳｙｎｔａｘＡのビット位置３（０）の符号化は下記（５）式のようになる。
【０１５３】
ｓｐｌｉｔ＝１＋（（（１７９−１）＊２４５）＞＞８）＝１７１
Ｒａｎｇｅ＝ｓｐｌｉｔ＝１７１ …（５）
【０１５４】
ＳｙｎｔａｘＡのビット位置４（０）の符号化は下記（６）式のようになる。
【０１５５】
ｓｐｌｉｔ＝１＋（（（１７１−１）＊２４４）＞＞８）＝１６３
Ｒａｎｇｅ＝ｓｐｌｉｔ＝１６３ …（６）
【０１５６】
ＳｙｎｔａｘＡのビット位置５（０）の符号化は下記（７）式のようになる。
【０１５７】
ｓｐｌｉｔ＝１＋（（（１６３−１）＊２４２）＞＞８）＝１５４
Ｒａｎｇｅ＝ｓｐｌｉｔ＝１５４ …（７）
【０１５８】
ＳｙｎｔａｘＡのビット位置６（１）の符号化は下記（８）式のようになる。
【０１５９】
ｓｐｌｉｔ＝１＋（（（１５４−１）＊２４４）＞＞８）＝１４６
ｌｏｗｖａｌｕｅ＋＝ｓｐｌｉｔ＝１４６
Ｒａｎｇｅ＝Ｒａｎｇｅ−ｓｐｌｉｔ＝８ …（８）
【０１６０】
ここで、範囲Ｒａｎｇｅが１２８未満となったため、１ビット正規化処理が発生し、下記（９）式のようになる。
【０１６１】
ｃｏｕｎｔ＝ｃｏｕｎｔ＋１＝１
ｌｏｗｖａｌｕｅ＝ｌｏｗｖａｌｕｅ−１２８＝１８
Ｒａｎｇｅ＝Ｒａｎｇｅ＜＜１＝１６
ｌｏｗｖａｌｕｅ＝ｌｏｗｖａｌｕｅ＜＜１＝３６ …（９）
【０１６２】
範囲Ｒａｎｇｅが１２８未満のままであるため、さらに１ビット正規化処理が発生し、下記（１０）式のようになる。また、ｃｏｕｎｔ＝１により符号値“１”が出力される。
【０１６３】
ｃｏｕｎｔ＝ｃｏｕｎｔ−１＝０
Ｒａｎｇｅ＝Ｒａｎｇｅ＜＜１＝３２
ｌｏｗｖａｌｕｅ＝ｌｏｗｖａｌｕｅ＜＜１＝７２ …（１０）
【０１６４】
範囲Ｒａｎｇｅが１２８未満のままであるため、さらに１ビット正規化処理が発生し、下記（１１）式のようになる。また、ｃｏｕｎｔ＝０により符号値“０”が出力される。
【０１６５】
Ｒａｎｇｅ＝Ｒａｎｇｅ＜＜１＝６４
ｌｏｗｖａｌｕｅ＝ｌｏｗｖａｌｕｅ＜＜１＝１４４ …（１１）
【０１６６】
範囲Ｒａｎｇｅが１２８未満のままであるため、さらに１ビット正規化処理が発生し、下記（１２）式のようになる。また、ｃｏｕｎｔ＝０により符号値“０”が出力される。
【０１６７】
ｃｏｕｎｔ＝ｃｏｕｎｔ＋１＝１
ｌｏｗｖａｌｕｅ＝ｌｏｗｖａｌｕｅ−１２８＝１６
Ｒａｎｇｅ＝Ｒａｎｇｅ＜＜１＝１２８
ｌｏｗｖａｌｕｅ＝ｌｏｗｖａｌｕｅ＜＜１＝３２ …（１２）
【０１６８】
範囲Ｒａｎｇｅが１２８以上となったため、ＳｙｎｔａｘＡのビット位置７（０）の符号化が実行される。ＳｙｎｔａｘＡのビット位置７（０）の符号化は下記（１３）式のようになる。
【０１６９】
ｓｐｌｉｔ＝１＋（（（１２８−１）＊２４５）＞＞８）＝１２２
Ｒａｎｇｅ＝ｓｐｌｉｔ＝１２２ …（１３）
【０１７０】
範囲Ｒａｎｇｅが１２８未満となったため、１ビット正規化処理が発生し、下記（１４）式のようになる。また、ｃｏｕｎｔ＝１により符号値“１”が出力される。
【０１７１】
ｃｏｕｎｔ＝ｃｏｕｎｔ−１＝０
Ｒａｎｇｅ＝Ｒａｎｇｅ＜＜１＝２４４
ｌｏｗｖａｌｕｅ＝ｌｏｗｖａｌｕｅ＜＜１＝６４ …（１４）
【０１７２】
これにより、ＳｙｎｔａｘＡを符号化した時点で符号値“１００１”までが確定したこととなる。以下、ＳｙｎｔａｘＢ以降も同様の処理を行い、符号値“１００１＿００１０＿１１１０＿００１０＿ｘｘｘｘ＿”が得られるとする。
【０１７３】
（復号の具体例）
ここでは、上記の符号化の具体例によって符号化されたストリームデータ（“１００１＿００１０＿１１１０＿００１０＿ｘｘｘｘ＿”）を対象とする復号の具体例について説明する。したがって、復号対象の最初のシンタクスはＳｙｎｔａｘＡ（８ビット）であり、ＳｙｎｔａｘＡの次のシンタクスはＳｙｎｔａｘＢ（８ビット）である。
【０１７４】
ＳｙｎｔａｘＡの各ビット位置ｋにおける“０”の発生確率は、ＰｒｏｂＴａｂｌｅＡ［ｋ］＝｛２１７，２２３，２４５，２４５，２４４，２４２，２４４，２４５｝である。ＳｙｎｔａｘＢの各ビット位置ｋにおける“０”の発生確率は、ＰｒｏｂＴａｂｌｅＢ［ｋ］＝｛２３４，２５１，２４４，２５４，２１６，１９９，１７９，２３３｝である。また、復号対象のストリームデータの先頭の１６ビットは「１００１＿００１０＿１１１０＿００１０」となる。
【０１７５】
図２０は、シンタクスのグループ分けの一例を示す図である。復号装置１００においては、ＰｒｏｂＴａｂｌｅＡ［ｋ］およびＰｒｏｂＴａｂｌｅＢ［ｋ］の各発生確率が図２０のグループ２００１〜２００６のようにグループ分けされているとする。
【０１７６】
たとえば、復号装置１００は、各発生確率を順に読み出し、発生確率を１つ読み出すごとに、読み出した各発生確率の最大値および最小値を算出する。そして、復号装置１００は、算出した最大値および最小値の差が所定値を超えない範囲で最大数の各発生確率を１つのグループとする。これにより、各グループにおいて、発生確率の最大値と最小値の差が所定値以下となるようにすることができる。
【０１７７】
たとえば、図２０に示す例は、所定値を２５としてグループ分けを行った例である。たとえば、復号装置１００は、各発生確率を順に読み出し、３つめの発生確率（２４５）を読み出した時点で最大値（２４５）と最小値（２１７）の差が２８となり所定値（２５）を超えるため、１つ目および２つ目の発生確率（２１７，２２３）をグループ２００１とする。
【０１７８】
このように、復号装置１００は、復号データの各位置（各発生確率）を、同一グループ内の各位置における発生確率の最大値と最小値との差が所定値以内になるようにグループ２００１〜２００６に分けておく。これにより、たとえば“０”の発生確率の高い各位置が同一グループにまとまるため、一括復号の発生確率をさらに高めることができる。ただし、グループ分けの方法はこれに限らない。たとえば、各発生確率を、一定数ずつの各グループに分けてもよい。
【０１７９】
図２１−１は、具体例にかかるシンタクスとグループＩＤの対応情報を示す図である。図３−１に示した対応情報３１０は、図２０に示したグループ分けの例においては図２１−１に示す対応情報２１１０のようになる。
【０１８０】
図２１−２は、具体例にかかるグループＩＤと減少値の対応情報を示す図である。図１４に示した対応情報１４００は、図２０に示したグループ分けの例においては図２１−２に示す対応情報２１２０のようになる。
【０１８１】
まず、復号装置１００は、ストリームデータの先頭８ビット「１００１＿００１０」（１４６）を取得してＶａｌｕｅに設定する。また、復号装置１００は、Ｒａｎｇｅの初期値を２５５とする。復号装置１００は、ＳｙｎｔａｘＡ［０］はグループＩＤ「０」のグループに属するため、グループＩＤ「０」に対応するＳｕｂＶａｌ＝３９を取得する。そして、図１５に示した処理により、一括復号ビット数Ｎとして２が算出される。したがって、Ｎ＝２としてＮビット復号処理（図７参照）が実行される。Ｎビット復号処理においては、境界値ｓｐｌｉｔが下記（１）式のように算出される。
【０１８２】
Ｓｐｌｉｔ＝１＋（（（２５５−１）×２１７）＞＞８）＝２１６
Ｓｐｌｉｔ＝１＋（（（２１６−１）×２２３）＞＞８）＝１８８ …（１）
【０１８３】
したがって、Ｎビット復号処理の復号値は“００”となり、範囲Ｒａｎｇｅは１８８となる。復号装置１００は、２ビット復号したため、つぎにＳｙｎｔａｘＡ［２］の復号を行う。図１５に示した処理により、一括復号ビット数Ｎとして３が算出される。したがって、Ｎ＝３としてＮビット復号処理（図７参照）が実行される。Ｎビット復号処理においては、境界値ｓｐｌｉｔが下記（２）式のように算出される。
【０１８４】
Ｓｐｌｉｔ＝１＋（（（１８８−１）×２４５）＞＞８）＝１７９
Ｓｐｌｉｔ＝１＋（（（１７９−１）×２４５）＞＞８）＝１７１
Ｓｐｌｉｔ＝１＋（（（１７１−１）×２４４）＞＞８）＝１６３ …（２）
【０１８５】
したがって、Ｎビット復号処理の復号値は“０００”となり、範囲Ｒａｎｇｅは１６３となる。復号装置１００は、３ビット復号したため、つぎにＳｙｎｔａｘＡ［５］の復号を行う。図１５に示した処理により、一括復号ビット数Ｎとして１が算出される。したがって、Ｎ＝１としてＮビット復号処理（図７参照）が実行される。Ｎビット復号処理においては、境界値ｓｐｌｉｔが下記（３）式のように算出される。
【０１８６】
Ｓｐｌｉｔ＝１＋（（（１６３−１）×２４２）＞＞８）＝１５４ …（３）
【０１８７】
したがって、Ｎビット復号処理の復号値は“０”となり、範囲Ｒａｎｇｅは１５４となる。復号装置１００は、１ビット復号したため、つぎにＳｙｎｔａｘＡ［６］の復号を行う。図１５に示した処理により、一括復号ビット数Ｎとして０が算出される。したがって、１ビット復号処理（図６参照）が実行される。１ビット復号処理においては、境界値ｓｐｌｉｔが下記（４）式のように算出される。
【０１８８】
Ｓｐｌｉｔ＝１＋（（（１５４−１）×２４４）＞＞８）＝１４６ …（４）
【０１８９】
したがって、１ビット復号処理の復号値は“１”となり、範囲Ｒａｎｇｅは８となり、符号値Ｖａｌｕｅは１となる。範囲Ｒａｎｇｅが１２８未満となったため、復号装置１００は再正規化を行う。具体的には、復号装置１００は、ストリームデータから４ビット補充してＶａｌｕｅ＝３０とする。範囲Ｒａｎｇｅは１２８となる。
【０１９０】
つぎに、復号装置１００は、１ビット復号したため、ＳｙｎｔａｘＡ［７］の復号を行う。図１５に示した処理により、一括復号ビット数Ｎとして０が算出される。したがって、１ビット復号処理（図６参照）が実行される。１ビット復号処理においては、境界値ｓｐｌｉｔが下記（５）式のように算出される。
【０１９１】
Ｓｐｌｉｔ＝１＋（（（１２８−１）×２４５）＞＞８）＝１２２ …（５）
【０１９２】
したがって、１ビット復号処理の復号値は“０”となり、範囲Ｒａｎｇｅは１２２となる。範囲Ｒａｎｇｅが１２８未満となったため、復号装置１００は再正規化を行う。具体的には、復号装置１００は、ストリームデータから１ビット補充してＶａｌｕｅ＝６０とする。範囲Ｒａｎｇｅは２４４となる。これにより、ＳｙｎｔａｘＡを“００００００１０”として復号することができる。ＳｙｎｔａｘＢについても同様の手順で復号することができる。
【０１９３】
このように、復号装置１００においては、特定の条件を満たす複数のシンタクス（またはシンタクスのビット位置）がひとつのグループとして予めまとめられる。そして、あるシンタクスの復号を行う際は、そのシンタクスが含まれているグループ内の最も低い発生確率により優勢シンボルが出力されると仮定した場合の範囲Ｒａｎｇｅの減少値（減少値ＳｕｂＶａｌ）が算出される。
【０１９４】
つぎに、算出された減少値を元に再正規化が発生するまでの最小の連続復号ビット数が算出され、算出されたビット数だけ１サイクルで一括して復号処理が行われる。これにより、予め一括復号ビット数を決定しなくても、シンタクスに応じた復号ビット数を選択することにより、一括復号が実施される割合が高くなり、算術復号処理の高速化を図ることが可能となる。
【０１９５】
また、連続復号ビット数の計算においては、グループ内でひとつの発生確率を代表して使用するため、マルチコンテキスト型の算術復号においても、多入力の乗算処理を行わなくてもよく、回路規模を小さくすることができる。また、グループの分類をシンタクス単位、またはシンタクスのビット単位と切り替えることにより、一括復号が発生する確率を調整することができる。
【０１９６】
以上説明したように、復号装置、復号方法および復号プログラムによれば、復号の高速化を図ることができる。
【０１９７】
なお、各実施の形態で説明した復号方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。このプログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ等のコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。またこのプログラムは、インターネット等のネットワークを介して配布することが可能な伝送媒体であってもよい。
【０１９８】
また、各実施の形態で説明した復号装置１００は、スタンダードセルやストラクチャードＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ Ｓｐｅｃｉｆｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ）などの特定用途向けＩＣ（以下、単に「ＡＳＩＣ」と称す。）やＦＰＧＡなどのＰＬＤ（Ｐｒｏｇｒａｍｍａｂｌｅ Ｌｏｇｉｃ Ｄｅｖｉｃｅ）によっても実現することができる。具体的には、たとえば、上述した復号装置１００の機能をＨＤＬ記述によって機能定義し、そのＨＤＬ記述を論理合成してＡＳＩＣやＰＬＤに与えることにより、復号装置１００を製造することができる。
【０１９９】
上述した各実施の形態に関し、さらに以下の付記を開示する。
【０２００】
（付記１）マルチコンテキスト型の算術符号化により所定の数値範囲に割り当てられた符号値から前記算術符号化の前のデータ列を復号する復号装置において、
前記数値範囲を記憶する記憶部と、
前記データ列の各位置における所定シンボルの発生確率を取得する取得部と、
前記取得部によって取得された発生確率の中の、前記データ列を区切った複数のグループのうちの復号対象の位置が属するグループにおける最小の発生確率に基づく前記数値範囲の減少幅を導出する導出部と、
前記数値範囲の限界値と前記符号値との差分を、前記導出部によって導出された減少幅によって除算する除算部と、
前記除算部によって得られた商が所定値以上である場合に、前記商だけ連続する前記所定シンボルとなる、前記復号対象の位置以降の復号結果を出力する一括復号処理部と、
を備えることを特徴とする復号装置。
【０２０１】
（付記２）前記商が前記所定値以上である場合に、前記記憶部に記憶された数値範囲の前記限界値を、前記減少幅に前記商を乗じた幅だけ変化させて前記数値範囲を縮小する縮小部を備えることを特徴とする付記１に記載の復号装置。
【０２０２】
（付記３）前記除算部は、前記限界値と前記符号値との差分および前記限界値と所定の閾値との差分のうちの小さい方の差分を前記減少幅によって除算し、
前記縮小部によって縮小された数値範囲の幅が前記所定の閾値以上となるように前記数値範囲および前記符号値を正規化する正規化部を備えることを特徴とする付記２に記載の復号装置。
【０２０３】
（付記４）前記導出部は、
前記最小の発生確率を特定する特定部と、
前記記憶部によって記憶された数値範囲を、前記特定部によって特定された発生確率に相当する割合で縮小した場合における前記数値範囲の減少幅を算出する算出部と、
を備えることを特徴とする付記１〜３のいずれか一つに記載の復号装置。
【０２０４】
（付記５）前記一括復号処理部によって復号結果が出力された場合に、前記データ列の各位置のうち、前記復号対象の位置から前記商の数だけ先の位置を次の復号対象とすることを特徴とする付記１〜４のいずれか一つに記載の復号装置。
【０２０５】
（付記６）前記商が前記所定値未満である場合に、前記記憶部によって記憶された数値範囲と、前記取得部によって取得された発生確率のうち前記復号対象の位置における発生確率と、前記符号値と、に基づく前記復号対象の位置の復号結果を出力する個別復号処理部を備え、
前記縮小部は、前記個別復号処理部によって復号結果が出力された場合に、前記個別復号処理部によって出力された復号結果と、前記復号対象の位置における発生確率と、に応じて前記記憶部によって記憶された数値範囲を縮小することを特徴とする付記２または３に記載の復号装置。
【０２０６】
（付記７）前記個別復号処理部によって復号結果が出力された場合に、前記データ列の各位置のうち、前記復号対象の１つ先の位置を次の復号対象とすることを特徴とする付記６に記載の復号装置。
【０２０７】
（付記８）前記導出部は、前記グループごとに、前記最小の発生確率に相当する割合による前記所定の数値範囲の減少幅が対応付けられた対応情報に基づいて、前記復号対象の位置が属するグループに対応する前記減少幅を導出することを特徴とする付記１〜３のいずれか一つに記載の復号装置。
【０２０８】
（付記９）前記減少幅に前記商を乗じた幅だけ縮小した前記数値範囲が前記符号値以下であり、または前記減少幅に前記商を乗じた幅だけ縮小した前記数値範囲が前記閾値未満である場合に、前記一括復号処理部は、前記商だけ連続する前記所定シンボルとなる復号結果を出力せず、前記個別復号処理部は、前記復号対象の位置を復号した復号結果を出力することを特徴とする付記６または７に記載の復号装置。
【０２０９】
（付記１０）前記データ列の各位置は、同一グループ内の各位置における前記発生確率の最大値と最小値との差が所定値以内になるように前記複数のグループに分けられていることを特徴とする付記１〜９のいずれか一つに記載の復号装置。
【０２１０】
（付記１１）マルチコンテキスト型の算術符号化により所定の数値範囲に割り当てられた符号値から前記算術符号化の前のデータ列を復号する復号方法において、
前記数値範囲を記憶し、
前記データ列の各位置における所定シンボルの発生確率を取得し、
取得した発生確率の中の、前記データ列を区切った複数のグループのうちの復号対象の位置が属するグループにおける最小の発生確率に基づく前記数値範囲の減少幅を導出し、
前記数値範囲の限界値と前記符号値との差分を、前記導出した減少幅によって除算し、
除算により得た商が所定値以上である場合に、前記商だけ連続する前記所定シンボルとなる、前記復号対象の位置以降の復号結果を出力することを特徴とする復号方法。
【０２１１】
（付記１２）マルチコンテキスト型の算術符号化により所定の数値範囲に割り当てられた符号値から前記算術符号化の前のデータ列を復号する復号プログラムにおいて、
前記数値範囲を記憶し、
前記データ列の各位置における所定シンボルの発生確率を取得し、
取得した発生確率の中の、前記データ列を区切った複数のグループのうちの復号対象の位置が属するグループにおける最小の発生確率に基づく前記数値範囲の減少幅を導出し、
前記数値範囲の限界値と前記符号値との差分を、前記導出した減少幅によって除算し、
除算により得た商が所定値以上である場合に、前記商だけ連続する前記所定シンボルとなる、前記復号対象の位置以降の復号結果を出力する処理をコンピュータに実行させることを特徴とする復号プログラム。
【符号の説明】
【０２１２】
ｘ１〜ｘ１０ 位置
ｐ１〜ｐ１０，ｐｒｏｂ１〜ｐｒｏｂＭ 発生確率
１００ 復号装置
１０１ 復号対象位置
１０２ 符号値
１１０，６１１ データ列
１１１〜１１３，２００１〜２００６ グループ
１２１〜１２３ 数値範囲
１２１ａ 限界値
１２２ａ 減少幅
１２２ｂ 差分
２００ 情報処理装置
２０１ バス
３１０，３２０，１４００，２１１０，２１２０ 対応情報
６１０ ストリームデータ
１１０３，１１１１〜１１１３，１３０８ シフト部
１１１０ 再正規化制御部
１１１４ ＯＲ部
１２２１〜１２２Ｍ 境界値算出部
【特許請求の範囲】
【請求項１】
マルチコンテキスト型の算術符号化により所定の数値範囲に割り当てられた符号値から前記算術符号化の前のデータ列を復号する復号装置において、
前記数値範囲を記憶する記憶部と、
前記データ列の各位置における所定シンボルの発生確率を取得する取得部と、
前記取得部によって取得された発生確率の中の、前記データ列を区切った複数のグループのうちの復号対象の位置が属するグループにおける最小の発生確率に基づく前記数値範囲の減少幅を導出する導出部と、
前記数値範囲の限界値と前記符号値との差分を、前記導出部によって導出された減少幅によって除算する除算部と、
前記除算部によって得られた商が所定値以上である場合に、前記商だけ連続する前記所定シンボルとなる、前記復号対象の位置以降の復号結果を出力する一括復号処理部と、
を備えることを特徴とする復号装置。
【請求項２】
前記商が前記所定値以上である場合に、前記記憶部に記憶された数値範囲の前記限界値を、前記減少幅に前記商を乗じた幅だけ変化させて前記数値範囲を縮小する縮小部を備えることを特徴とする請求項１に記載の復号装置。
【請求項３】
前記除算部は、前記限界値と前記符号値との差分および前記限界値と所定の閾値との差分のうちの小さい方の差分を前記減少幅によって除算し、
前記縮小部によって縮小された数値範囲の幅が前記所定の閾値以上となるように前記数値範囲および前記符号値を正規化する正規化部を備えることを特徴とする請求項２に記載の復号装置。
【請求項４】
前記導出部は、
前記最小の発生確率を特定する特定部と、
前記記憶部によって記憶された数値範囲を、前記特定部によって特定された発生確率に相当する割合で縮小した場合における前記数値範囲の減少幅を算出する算出部と、
を備えることを特徴とする請求項１〜３のいずれか一つに記載の復号装置。
【請求項５】
前記一括復号処理部によって復号結果が出力された場合に、前記データ列の各位置のうち、前記復号対象の位置から前記商の数だけ先の位置を次の復号対象とすることを特徴とする請求項１〜４のいずれか一つに記載の復号装置。
【請求項６】
前記商が前記所定値未満である場合に、前記記憶部によって記憶された数値範囲と、前記取得部によって取得された発生確率のうち前記復号対象の位置における発生確率と、前記符号値と、に基づく前記復号対象の位置の復号結果を出力する個別復号処理部を備え、
前記縮小部は、前記個別復号処理部によって復号結果が出力された場合に、前記個別復号処理部によって出力された復号結果と、前記復号対象の位置における発生確率と、に応じて前記記憶部によって記憶された数値範囲を縮小することを特徴とする請求項２または３に記載の復号装置。
【請求項７】
前記導出部は、前記グループごとに、前記最小の発生確率に相当する割合による前記所定の数値範囲の減少幅が対応付けられた対応情報に基づいて、前記復号対象の位置が属するグループに対応する前記減少幅を導出することを特徴とする請求項１〜３のいずれか一つに記載の復号装置。
【請求項８】
前記減少幅に前記商を乗じた幅だけ縮小した前記数値範囲が前記符号値以下であり、または前記減少幅に前記商を乗じた幅だけ縮小した前記数値範囲が前記閾値未満である場合に、前記一括復号処理部は、前記商だけ連続する前記所定シンボルとなる復号結果を出力せず、前記個別復号処理部は、前記復号対象の位置を復号した復号結果を出力することを特徴とする請求項６に記載の復号装置。
【請求項９】
マルチコンテキスト型の算術符号化により所定の数値範囲に割り当てられた符号値から前記算術符号化の前のデータ列を復号する復号方法において、
前記数値範囲を記憶し、
前記データ列の各位置における所定シンボルの発生確率を取得し、
取得した発生確率の中の、前記データ列を区切った複数のグループのうちの復号対象の位置が属するグループにおける最小の発生確率に基づく前記数値範囲の減少幅を導出し、
前記数値範囲の限界値と前記符号値との差分を、前記導出した減少幅によって除算し、
除算により得た商が所定値以上である場合に、前記商だけ連続する前記所定シンボルとなる、前記復号対象の位置以降の復号結果を出力することを特徴とする復号方法。
【請求項１０】
マルチコンテキスト型の算術符号化により所定の数値範囲に割り当てられた符号値から前記算術符号化の前のデータ列を復号する復号プログラムにおいて、
前記数値範囲を記憶し、
前記データ列の各位置における所定シンボルの発生確率を取得し、
取得した発生確率の中の、前記データ列を区切った複数のグループのうちの復号対象の位置が属するグループにおける最小の発生確率に基づく前記数値範囲の減少幅を導出し、
前記数値範囲の限界値と前記符号値との差分を、前記導出した減少幅によって除算し、
除算により得た商が所定値以上である場合に、前記商だけ連続する前記所定シンボルとなる、前記復号対象の位置以降の復号結果を出力する処理をコンピュータに実行させることを特徴とする復号プログラム。
【請求項１】
マルチコンテキスト型の算術符号化により所定の数値範囲に割り当てられた符号値から前記算術符号化の前のデータ列を復号する復号装置において、
前記数値範囲を記憶する記憶部と、
前記データ列の各位置における所定シンボルの発生確率を取得する取得部と、
前記取得部によって取得された発生確率の中の、前記データ列を区切った複数のグループのうちの復号対象の位置が属するグループにおける最小の発生確率に基づく前記数値範囲の減少幅を導出する導出部と、
前記数値範囲の限界値と前記符号値との差分を、前記導出部によって導出された減少幅によって除算する除算部と、
前記除算部によって得られた商が所定値以上である場合に、前記商だけ連続する前記所定シンボルとなる、前記復号対象の位置以降の復号結果を出力する一括復号処理部と、
を備えることを特徴とする復号装置。
【請求項２】
前記商が前記所定値以上である場合に、前記記憶部に記憶された数値範囲の前記限界値を、前記減少幅に前記商を乗じた幅だけ変化させて前記数値範囲を縮小する縮小部を備えることを特徴とする請求項１に記載の復号装置。
【請求項３】
前記除算部は、前記限界値と前記符号値との差分および前記限界値と所定の閾値との差分のうちの小さい方の差分を前記減少幅によって除算し、
前記縮小部によって縮小された数値範囲の幅が前記所定の閾値以上となるように前記数値範囲および前記符号値を正規化する正規化部を備えることを特徴とする請求項２に記載の復号装置。
【請求項４】
前記導出部は、
前記最小の発生確率を特定する特定部と、
前記記憶部によって記憶された数値範囲を、前記特定部によって特定された発生確率に相当する割合で縮小した場合における前記数値範囲の減少幅を算出する算出部と、
を備えることを特徴とする請求項１〜３のいずれか一つに記載の復号装置。
【請求項５】
前記一括復号処理部によって復号結果が出力された場合に、前記データ列の各位置のうち、前記復号対象の位置から前記商の数だけ先の位置を次の復号対象とすることを特徴とする請求項１〜４のいずれか一つに記載の復号装置。
【請求項６】
前記商が前記所定値未満である場合に、前記記憶部によって記憶された数値範囲と、前記取得部によって取得された発生確率のうち前記復号対象の位置における発生確率と、前記符号値と、に基づく前記復号対象の位置の復号結果を出力する個別復号処理部を備え、
前記縮小部は、前記個別復号処理部によって復号結果が出力された場合に、前記個別復号処理部によって出力された復号結果と、前記復号対象の位置における発生確率と、に応じて前記記憶部によって記憶された数値範囲を縮小することを特徴とする請求項２または３に記載の復号装置。
【請求項７】
前記導出部は、前記グループごとに、前記最小の発生確率に相当する割合による前記所定の数値範囲の減少幅が対応付けられた対応情報に基づいて、前記復号対象の位置が属するグループに対応する前記減少幅を導出することを特徴とする請求項１〜３のいずれか一つに記載の復号装置。
【請求項８】
前記減少幅に前記商を乗じた幅だけ縮小した前記数値範囲が前記符号値以下であり、または前記減少幅に前記商を乗じた幅だけ縮小した前記数値範囲が前記閾値未満である場合に、前記一括復号処理部は、前記商だけ連続する前記所定シンボルとなる復号結果を出力せず、前記個別復号処理部は、前記復号対象の位置を復号した復号結果を出力することを特徴とする請求項６に記載の復号装置。
【請求項９】
マルチコンテキスト型の算術符号化により所定の数値範囲に割り当てられた符号値から前記算術符号化の前のデータ列を復号する復号方法において、
前記数値範囲を記憶し、
前記データ列の各位置における所定シンボルの発生確率を取得し、
取得した発生確率の中の、前記データ列を区切った複数のグループのうちの復号対象の位置が属するグループにおける最小の発生確率に基づく前記数値範囲の減少幅を導出し、
前記数値範囲の限界値と前記符号値との差分を、前記導出した減少幅によって除算し、
除算により得た商が所定値以上である場合に、前記商だけ連続する前記所定シンボルとなる、前記復号対象の位置以降の復号結果を出力することを特徴とする復号方法。
【請求項１０】
マルチコンテキスト型の算術符号化により所定の数値範囲に割り当てられた符号値から前記算術符号化の前のデータ列を復号する復号プログラムにおいて、
前記数値範囲を記憶し、
前記データ列の各位置における所定シンボルの発生確率を取得し、
取得した発生確率の中の、前記データ列を区切った複数のグループのうちの復号対象の位置が属するグループにおける最小の発生確率に基づく前記数値範囲の減少幅を導出し、
前記数値範囲の限界値と前記符号値との差分を、前記導出した減少幅によって除算し、
除算により得た商が所定値以上である場合に、前記商だけ連続する前記所定シンボルとなる、前記復号対象の位置以降の復号結果を出力する処理をコンピュータに実行させることを特徴とする復号プログラム。
【図１−１】
【図１−２】
【図１−３】
【図２】
【図３−１】
【図３−２】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１−１】
【図２１−２】
【図１−２】
【図１−３】
【図２】
【図３−１】
【図３−２】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１−１】
【図２１−２】
【公開番号】特開２０１３−９０１８９（Ｐ２０１３−９０１８９Ａ）
【公開日】平成２５年５月１３日（２０１３．５．１３）
【国際特許分類】
【出願番号】特願２０１１−２２９７３１（Ｐ２０１１−２２９７３１）
【出願日】平成２３年１０月１９日（２０１１．１０．１９）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２５年５月１３日（２０１３．５．１３）
【国際特許分類】
【出願日】平成２３年１０月１９日（２０１１．１０．１９）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]