(57)【要約】【課題】ハフマン符号の分布特性の変化に対して高速に対応し、高速且つ高性能の可変長符号復号装置および復号方法を提供する。【解決手段】それぞれテーブル構成の異なる復号用参照テーブル１０４および１０５を設け、スイッチ１０３によって復号用参照テーブル１０４および１０５のいずれかを選択しテーブル参照部１０２に接続する。最適テーブル判定部１０６は圧縮符号化信号の所望のパラメータに基づいて可変長符号の一時的な分布特性を判定し、複数の復号用参照テーブルから最適な１つを選択するようにスイッチ１０３を制御する。選択された復号用参照テーブルを参照しながら、テーブル参照部は可変長符号の復号を行う。【選択図】　　図１
2004120274.tif 000002
【特許請求の範囲】
【請求項１】
可変長符号の復号を行う装置において、
それぞれテーブル構成の異なる複数の復号用参照テーブルを格納するテーブル格納手段と、
前記可変長符号の一時的な分布特性に応じて、前記複数の復号用参照テーブルの１つを選択する選択手段と、
前記選択手段により選択された復号用参照テーブルを参照しながら、前記可変長符号の復号を行うテーブル参照手段と、
を有することを特徴とする可変長符号復号装置。
【請求項２】
前記テーブル格納手段は、
複数のサブテーブルからなる第１の復号用参照テーブルと、
前記第１の復号用参照テーブルより容量が大きく、１つ以上のテーブルからなる第２の復号用参照テーブルと、
を格納したことを特徴とする請求項１記載の可変長符号復号装置。
【請求項３】
可変長符号の復号を行う装置において、
同一の可変長符号セットに対して複数の復号用参照テーブルを格納するテーブル格納手段と、
前記可変長符号の一時的な分布特性に応じて、前記複数の復号用参照テーブルから１つを選択する選択手段と、
前記選択手段により選択された復号用参照テーブルを参照しながら、前記可変長符号の復号を行うテーブル参照手段と、
を有し、
前記テーブル格納手段に格納された前記複数の復号用参照テーブルは、複数の符号語が連接された連接語エントリと単一の符号語の単一語エントリとを含み、連接語エントリの数がそれぞれ異なるテーブルである、
ことを特徴とする可変長符号復号装置。
【請求項４】
前記テーブル格納手段は、第１及び第２の復号用参照テーブルを有し、前記第２の復号用参照テーブルの連接語エントリ数は、前記第１の復号用参照テーブルのそれより大きいことを特徴とする請求項３記載の可変長符号復号装置。
【請求項５】
前記選択手段は、前記入力符号化信号の所定信号単位あたりの符号語数が所定値未満の場合には前記第１の復号用参照テーブルを選択し、前記入力符号化信号の所定信号単位あたりの符号語数が所定値以上の場合には前記第２の復号用参照テーブルを選択する、ことを特徴とする請求項４記載の可変長符号復号装置。
【請求項６】
前記選択手段は、入力符号化信号の所定信号単位あたりの符号語数に基づいて前記可変長符号の一時的な分布特性を判定することを特徴とする請求項３記載の可変長符号復号装置。
【請求項７】
前記入力符号化信号の複数の所定パラメータのうちの少なくとも１つのパラメータに基づいて所定信号単位あたりの符号語数を判定することを特徴とする請求項６記載の可変長符号復号装置。
【請求項８】
前記選択手段は、前記入力符号化信号の前記所定信号単位より大きい信号単位の先頭で前記可変長符号の一時的な分布特性を判定することを特徴とする請求項６記載の可変長符号復号装置。
【請求項９】
Ｎ（Ｎは２以上の整数）種の可変長符号セットが用いられて生成された可変長符号系列を復号化する可変長符号復号装置において、
前記Ｎ種の可変長符号化セットの各々に対応して設けられ、それぞれ１種の可変長符号セットに対して複数の復号用参照テーブルを格納するＮ個のテーブル格納手段と、
前記可変長符号系の可変長符号に対応したテーブル格納手段から、前記可変長符号の一時的な分布特性に応じて１つの復号用参照テーブルを選択する選択手段と、
前記選択手段により選択された復号用参照テーブルを参照しながら、前記可変長符号の復号を行うテーブル参照手段と、
を有し、前記Ｎ個のテーブル格納手段の各々に格納された複数の復号用参照テーブルは、複数の符号語が連接された連接語エントリと単一の符号語の単一語エントリとを含み、連接語エントリの数がそれぞれ異なるテーブルである、
ことを特徴とする可変長符号復号装置。
【請求項１０】
前記選択手段は、入力符号化信号の所定信号単位あたりの符号語数に基づいて前記可変長符号の一時的な分布特性を判定することを特徴とする請求項９記載の可変長符号復号装置。
【請求項１１】
前記Ｎ個のテーブル格納手段の各々には第１の復号用参照テーブル及び第２の復号用参照テーブルが格納され、前記第２の復号用参照テーブルの連接語エントリの数は前記第１の復号用参照テーブルのそれより大きく、
前記選択手段は、前記入力符号化信号の所定信号単位あたりの符号語数が所定値未満の場合には前記第１の復号用参照テーブルを選択し、前記入力符号化信号の所定信号単位あたりの符号語数が所定値以上の場合には前記第２の復号用参照テーブルを選択する、ことを特徴とする請求項９記載の可変長符号復号装置。
【請求項１２】
前記選択手段は、前記入力符号化信号の前記所定信号単位より大きい信号単位の先頭で前記可変長符号の分布特性を判定することを特徴とする請求項９記載の可変長符号復号装置。
【請求項１３】
可変長符号の復号方法において、
同一の可変長符号セットに対して、複数の符号語が連接された連接語エントリと単一の符号語の単一語エントリとを含み、連接語エントリの数がそれぞれ異なる復号用参照テーブルを複数個用意し、
前記可変長符号の一時的な分布特性に応じて、前記複数の復号用参照テーブルから１つを選択し、
前記選択された復号用参照テーブルを参照しながら、前記可変長符号の復号を行う、
ことを特徴とする可変長符号復号方法。
【請求項１４】
Ｎ（Ｎは２以上の整数）種の可変長符号セットが用いられて生成された可変長符号系列を復号化する可変長符号復号方法において、
前記Ｎ種の可変長符号化セットの各々に対応して複数の復号用参照テーブルからなるテーブル群を用意し、前記テーブル群の各々における複数の復号用参照テーブルは、複数の符号語が連接された連接語エントリと単一の符号語の単一語エントリとを含み、その連接語エントリの数がそれぞれ異なり、
前記可変長符号系中で使用されている可変長符号セットに対応したテーブル群から、前記可変長符号の一時的な分布特性に応じて１つの復号用参照テーブルを選択し、
選択された復号用参照テーブルを参照しながら、前記可変長符号の復号を行う、
ことを特徴とする可変長符号復号方法。
【請求項１５】
コンピュータに可変長符号の復号処理を実行させるためのプログラムにおいて、
同一の可変長符号セットに対して、複数の符号語が連接された連接語エントリと単一の符号語の単一語エントリとを含み、連接語エントリの数がそれぞれ異なる復号用参照テーブルを複数用意するステップと、
前記可変長符号の一時的な分布特性に応じて、前記複数の復号用参照テーブルから１つを選択するステップと、
前記選択された復号用参照テーブルを参照しながら、前記可変長符号の復号を実行するステップと、
を有することを特徴とする可変長符号復号プログラム。
【請求項１６】
Ｎ（Ｎは２以上の整数）種の可変長符号セットが用いられて生成された可変長符号系列を復号化する可変長符号の復号処理をコンピュータに実行させるためのプログラムにおいて、
前記Ｎ種の可変長符号化セットの各々に対応して複数の復号用参照テーブルからなるテーブル群であって、前記テーブル群の各々における複数の復号用参照テーブルが、複数の符号語が連接された連接語エントリと単一の符号語の単一語エントリとを含み、その連接語エントリの数がそれぞれ異なる、テーブル群を用意するステップと、
前記可変長符号系中で使用されている可変長符号セットに対応したテーブル群の中から、前記可変長符号の一時的な分布特性に応じて１つの復号用参照テーブルを選択するステップと、
選択された復号用参照テーブルを参照しながら、前記可変長符号の復号を実行するステップと、
を有することを特徴とする可変長符号復号プログラム。
【請求項１７】
可変長符号の復号を行う装置において、
それぞれテーブル構成の異なる複数の復号用参照テーブルと、
前記テーブル構成に依存する復号性能と前記可変長符号の一時的な分布特性との予め設定された対応づけに基づいて、前記可変長符号の一時的な分布特性から前記複数の復号用参照テーブルの１つを選択する選択手段と、
前記選択手段により選択された復号用参照テーブルを参照しながら、前記可変長符号の復号を行うテーブル参照手段と、
を有することを特徴とする可変長符号復号装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は圧縮符号化された信号の復号技術に係り、特に可変長符号の復号装置及び方法に関する。
【０００２】
【従来の技術】
動画像の圧縮符号化を例にとれば、動画像信号の符号化は、ＭＰＥＧ（ＭｏｔｉｏｎＰｉｃｔｕｒｅ　ｉｍａｇｅ　ｃｏｄｉｎｇ　Ｅｘｐｅｒｔｓ　Ｇｒｏｕｐ）−１（ＩＳＯ／ＩＥＣ　１１１７２−２、１９９３年）、ＭＰＥＧ−２（ＩＳＯ／ＩＥＣ　１３８１８−２、１９９５年）、ＭＰＥＧ−４（ＩＳＯ／ＩＥＣ　１４４９６−２、１９９８年）等の動画像圧縮規格に準拠して行なわれることが多い。以下、これらの規格を「ＭＰＥＧ」と総称する。
【０００３】
ＭＰＥＧ方式では、画像を８画素×８画素のブロックに分割し、このブロックを最小の単位として動き補償と変換符号化とを行うことでデータサイズの圧縮を実現している。変換符号化では、一般に、離散コサイン変換（ＤＣＴ）、量子化、およびハフマン符号化の３つを連続して実行する。
【０００４】
周知のように、ハフマン符号化では、ジグザグスキャンにより得られた一次元の量子化ＤＣＴ係数について、連続する零係数の個数（ラン）とそれに続く非零係数の量子化値（レベル）の組み合わせを求め、それらを符号化方式により予め規定されたハフマンテーブルを参照しながら順次符号の割り当てが行われる。
【０００５】
こうして変換符号化された信号は次のように復号化される。まず、同じハフマンテーブルを用いてハフマン符号からランとレベルの組み合わせを順次求め、次に、量子化されたＤＣＴ係数を逆ジグザグスキャンによって並べ替えて８行８列の量子化されたＤＣＴ係数ブロックを得る。そして量子化されたＤＣＴ係数ブロックの各係数に対して逆量子化を行ない、ＤＣＴ係数ブロックを得る。最後にＤＣＴ係数ブロックを８点×８点逆離散コサイン変換することで復号処理が完了する。
【０００６】
ところで、一般に、量子化されたＤＣＴ係数ブロックには、ハフマン符号の符号語が複数個存在していることが多い。したがって、複数のハフマン符号を１回の復号操作で復号すれば高速復号が可能となる。その反面、多数の符号語を同時に復号するには、膨大なメモリ量が必要となり、ソフトウエアにより可変長符号の復号を実行する際にキャッシュミスが生じやすくなる。
【０００７】
この点に着目して、２符号を同時に復号できる復号用参照テーブルと１符号を復号するための復号用参照テーブルとを択一的に選択できる復号装置が提案されている（特許第３２３５５５５号公報）。この復号装置では、複数符号を同時復号できる確率、テーブル選択に起因する条件分岐ミスが発生する確率およびキャッシュミスが発生する確率のトレードオフを考慮して、復号用参照テーブルを適切な数および適切な容量になるように分割し、それらを適切に選択することで高速かつ高性能の復号を実現している。
【０００８】
また、符号化パラメータによってシンボルの生起確率が変化する点に着目した階層的画像復号装置が特開２００１−９４９８２号公報に開示されている。この階層的画像復号装置は階層符号化方式を前提としており、下位層の復号によって得られた低解像度のベースレイヤ画像と、上位層の復号によって得られた差分画像とを加算することで高解像度の画像が復元される。上位層の復号処理において、符号化パラメータに従って複数の符号割当テーブルの１つが選択され、それを用いて復号が行われる。
【０００９】
【特許文献１】
特許第３２３５５５５号公報（段落番号００２９〜００３５、図１）
【特許文献２】
特開２００１−９４９８２号公報（段落番号００３０〜００３５、図１）。
【００１０】
【発明が解決しようとする課題】
ハフマン符号の符号語の分布特性（語数、符号長）は、動画像の場合、ピクチャタイプ、マクロブロックタイプ、ビットレートなどのパラメータによって異なってくる。ハフマン符号の分布が異なると、最適な復号用テーブルも異なる。例えば、ＤＣＴ係数ブロックに含まれるハフマン符号の語数が多ければ、２符号同時復号できる確率が高いほうが有利である。ハフマン符号の語数が少なければ、２符号同時復号できる確率が高いよりもキャッシュミスが発生する確率が低いほうが有利な場合がある。したがって、復号性能を向上させるには、ハフマン符号の分布特性の変化に対応することが必要である。
【００１１】
特許文献２には、符号化パラメータによってシンボルの生起確率が変化する点に着目した階層的画像復号装置が開示されている。しかしながら、この復号装置では、複数の符号割当テーブルの選択は差分画層を得る上位層の復号だけで使用され、ベースレイヤ画像を得るための下位層の復号では使用されない。また、符号割当テーブルの選択基準となる符号化パラメータは下位層の復号で用いたものである。したがって、ベースレイヤ画像を得るための下位層の復号には通常の符号割当テーブルが用いられるだけであり、複数の符号割当テーブルは用意されていない。
【００１２】
【発明の目的】
本発明の第一の目的は、可変長符号の分布特性の変化に対して高速に対応し、高速且つ高性能の可変長符号復号装置および復号方法を提供することにある。
【００１３】
本発明の第二の目的は、可変長符号の分布特性を少ない演算量で判定し、最適の復号用参照テーブルを選択する可変長符号復号装置および復号方法を提供することにある。
【００１４】
【課題を解決するための手段】
本発明の第１の観点による可変長符号復号装置は、それぞれテーブル構成の異なる複数の復号用参照テーブルを格納するテーブル格納手段と、前記可変長符号の一時的な分布特性に応じて、前記複数の復号用参照テーブルの１つを選択する選択手段と、前記選択手段により選択された復号用参照テーブルを参照しながら、前記可変長符号の復号を行うテーブル参照手段と、を有することを特徴とする。
【００１５】
本発明の第２の観点による可変長符号復号装置は、同一の可変長符号セットに対して複数の復号用参照テーブルを格納するテーブル格納手段と、前記可変長符号の一時的な分布特性に応じて、前記複数の復号用参照テーブルから１つを選択する選択手段と、前記選択手段により選択された復号用参照テーブルを参照しながら、前記可変長符号の復号を行うテーブル参照手段と、を有し、前記テーブル格納手段に格納された前記複数の復号用参照テーブルは、複数の符号語が連接された連接語エントリと単一の符号語の単一語エントリとを含み、連接語エントリの数がそれぞれ異なるテーブルである、ことを特徴とする。
【００１６】
前記テーブル格納手段が第１及び第２の復号用参照テーブルを有し、前記第２の復号用参照テーブルの連接語エントリ数は前記第１の復号用参照テーブルのそれより大きい場合には、前記選択手段は、前記入力符号化信号の所定信号単位あたりの符号語数が所定値未満の時に前記第１の復号用参照テーブルを選択し、前記入力符号化信号の所定信号単位あたりの符号語数が所定値以上の時に前記第２の復号用参照テーブルを選択する。前記選択手段は、入力符号化信号の所定信号単位あたりの符号語数に基づいて前記可変長符号の一時的な分布特性を判定することができる。また、前記入力符号化信号の複数の所定パラメータのうちの少なくとも１つのパラメータに基づいて所定信号単位あたりの符号語数を判定することができる。また、選択手段は、前記入力符号化信号の前記所定信号単位より大きい信号単位の先頭で前記可変長符号の一時的な分布特性を判定してもよい。
【００１７】
本発明の第３の観点による可変長符号復号装置は、Ｎ（Ｎは２以上の整数）種の可変長符号セットが用いられて生成された可変長符号系列を復号化する可変長符号復号装置であって、前記Ｎ種の可変長符号化セットの各々に対応して設けられ、それぞれ１種の可変長符号セットに対して複数の復号用参照テーブルを格納するＮ個のテーブル格納手段と、前記可変長符号系の可変長符号に対応したテーブル格納手段から、前記可変長符号の一時的な分布特性に応じて１つの復号用参照テーブルを選択する選択手段と、前記選択手段により選択された復号用参照テーブルを参照しながら、前記可変長符号の復号を行うテーブル参照手段と、を有し、前記Ｎ個のテーブル格納手段の各々に格納された複数の復号用参照テーブルは、複数の符号語が連接された連接語エントリと単一の符号語の単一語エントリとを含み、連接語エントリの数がそれぞれ異なるテーブルである、ことを特徴とする。
【００１８】
本発明の第４の観点による可変長符号復号装置は、それぞれテーブル構成の異なる複数の復号用参照テーブルと、前記テーブル構成に依存する復号性能と前記可変長符号の一時的な分布特性との予め設定された対応づけに基づいて、前記可変長符号の一時的な分布特性から前記複数の復号用参照テーブルの１つを選択する選択手段と、前記選択手段により選択された復号用参照テーブルを参照しながら、前記可変長符号の復号を行うテーブル参照手段と、を有することを特徴とする。
【００１９】
本発明によれば、テーブル構成の異なる複数の復号用参照テーブルを設け、可変長符号の一時的な分布特性に基づいて最適な復号用参照テーブルを選択できるために、可変長符号を高速に復号することができる。また、入力符号化信号の前記所定信号単位より大きい信号単位の先頭で可変長符号の分布特性を判定することで、テーブルの切換判定頻度を少なくすることができ、演算量が低減して更に高速で復号処理を実行させることができる。
【００２０】
【発明の実施の形態】
１．第１実施形態
１．１）構成
図１は、本発明の第１実施形態によるハフマン符号復号装置の構成を示すブロック図である。本実施形態によるハフマン符号復号装置は２つの異なる復号用参照テーブル１０４および１０５を格納し、入力符号化信号のパラメータに基づいていずれか一方の復号用参照テーブルを選択して復号処理を行う。
【００２１】
図１において、ハフマン符号復号装置は、入力ビット列ＢＳＩＮを一時記憶するビット列バッファ１０１と、後述するように復号用参照テーブル１０４および１０５の選択された方を参照することで復号データを生成するテーブル参照部１０２と、を有する。ビット列バッファ１０１には、格納された入力ビット列に対する読み出しポインタが設けられ、テーブル参照部１０２から通知される符号長に従って読み出し先頭ビットを順次移動させる。
【００２２】
テーブル参照部１０２は、スイッチ１０３を介して、復号用参照テーブル１０４および１０５のいずれかに接続される。復号用参照テーブル１０４および１０５は、それぞれ異なるハフマン符号分布特性に適したテーブル構成を有する。テーブル参照部１０２は、入力ビット列から生成されたインデックスをスイッチ１０３により選択された復号用参照テーブルへ出力し、それに対応したテーブルエントリを受け取り、そのエントリから復号データを抽出する。
【００２３】
復号用参照テーブル１０４および１０５は、共にハフマン符号復号用のテーブルであり、それぞれ単独で入力ビット列の復号が可能であるがテーブル構成が異なっている。詳しくは後述するが、たとえば、復号用参照テーブル１０４は同時復号できる確率は小さいが容量の小さいテーブルであり、復号用参照テーブル１０５は同時復号できる確率は大きいが容量の大きいテーブルである。
【００２４】
スイッチ１０３は、最適テーブル判定部１０６からの選択制御信号ＳＥＬに従って動作し、復号用参照テーブル１０４および復号用参照テーブル１０５のいずれかをテーブル参照部１０２に接続する。最適テーブル判定部１０６は、入力ビット列に対応する動画像圧縮信号のビットレートＢＲ、ピクチャタイプＰＴおよび／またはマクロブロックタイプＭＢＴのパラメータに基づいて、ハフマン符号の一時的な分布特性を判定し、判定されたハフマン符号分布特性に最適な復号用参照テーブルを選択するための選択制御信号ＳＥＬをスイッチ１０３へ出力する。
【００２５】
１．２）復号用参照テーブル
図２は、ハフマン符号の定義の一例を示す模式図である。図３（Ａ）および（Ｂ）は、図２に示す定義例における復号用参照テーブル１０４の一例を示す模式図であり、図４は、図２に示す定義例における復号用参照テーブル１０５の一例を示す模式図である。ここでは、説明を簡単にするために、図２に示すように定義された最大符号長が４ビットのハフマン符号を復号する場合の参照テーブル１０４および１０５が例示されている。実際には、ＭＰＥＧ２の場合、最大符号長が１７であり、ハフマン符号のエントリ数は２７オーダーである。
【００２６】
まず、図３あるいは図４に示すように、ハフマン符号の復号に用いる復号用参照テーブルの各エントリには、インデックスが付され、各符号語の復号データが格納されている。インデックスｉは任意のビット列Ｓから一意に生成できるように規則を定めておく。
【００２７】
ビット列Ｓがハフマン符号の符号語ｃ１およびｃ２を連接したものから始まる時には、対応する復号用参照テーブルエントリに符号語ｃ１およびｃ２のための復号データを格納しておく。この場合、復号データは、符号語ｃ１およびｃ２の符号長の和（符号長）、ｃ１のラン（ラン１）、ｃ１のレベル（レベル１）、ｃ２のラン（ラン２）、ｃ２のレベル（レベル２）からなる５つ一組のデータ＜ｌｅｎ，ｒｕｎ＿１，ｌｅｖｅｌ＿１，ｒｕｎ＿２，ｌｅｖｅｌ＿２＞である。また、ビット列Ｓがハフマン符号の符号語ｃ１からはじまり、他の符号語を含まないときには、符号語ｃ１のための復号データを格納しておく。この場合、ｌｅｎにはｃ１の符号長を格納し、ｒｕｎ＿２とｌｅｖｅｌ＿２には不定値を格納しておく。また、ビット列Ｓの始まりがどの符号語にも対応しない場合には、復号データの全ての項目に不定値を格納しておく。このように復号用参照テーブルを構成しておけば、ハフマン符号化されたビット列Ｓを次に示すような手順を繰り返すことにより復号することができる。
【００２８】
まず、ビット列Ｓからインデックスｉを生成し、続いて復号用参照テーブル１０４のなかでインデックスｉに対応するエントリを参照し取り出す。そして、ビット列Ｓの最初の符号語ｃ１（あるいはｃ１およびｃ２）に対応するｒｕｎ＿１（あるいはｒｕｎ＿１およびｒｕｎ＿２）とｌｅｖｅｌ＿１（あるいはｌｅｖｅｌ＿１およびｌｅｖｅｌ＿２）とを復号結果として出力する。また、ビット列Ｓから最初の符号語ｃ１の符号長（あるいは符号語ｃ１およびｃ２の符号長の和）ｌｅｎだけのビット列を取り除く。
【００２９】
次に、図２の定義例に従った復号用参照テーブル１０４および１０５のテーブル構成例を具体的に示す。
【００３０】
復号器Ａの復号用参照テーブル１０４
復号用参照テーブル１０４は、図３（Ａ）および（Ｂ）に示すテーブルの組み合わせであり、２符号同時復号できる確率は小さいが容量の小さいテーブルからなる。図３（Ａ）は、ビット列Ｓの先頭２ビットの値が「１１」、「１０」、「０１」のいずれかである場合のサブテーブルであり、図３（Ｂ）はビット列Ｓの先頭の２ビットが「００」である場合のサブテーブルである。
【００３１】
図３（Ａ）に示すサブテーブルの各エントリには、２ビットのインデックスが、図３（Ｂ）では４ビットのインデックスが、それぞれ付けられている。すなわち、この例では、任意のビット列Ｓからインデックスｉを一意に生成する規則は、ビット列Ｓの先頭２ビットを抽出して、その２ビットの値が「１１」、「１０」、「０１」であれば、その２ビットの値をインデックスｉとすることであり、また、ビット列Ｓの先頭２ビットの値が「００」であればビット列Ｓの先頭４ビットの値をインデックスｉとすることである。なお、ＭＰＥＧ２の場合、サブテーブルのエントリは２９オーダー以下に分割するのが好適である。
【００３２】
図２における符号語「０１」のランおよびレベルの値がＥＯＢ（Ｅｎｄ　ｏｆＢｌｏｃｋ）となっているのは、復号の対象としているＤＣＴ係数ブロックにこれ以上非零係数が存在しないことを示す。このＥＯＢ符号語に対応する復号データは、図３（Ａ）ではランの値として「６４」を用いている。これは、６４要素からなるＤＣＴ係数ブロックではランが６４となることはありえないからである。このように、復号用参照テーブルを参照することでＥＯＢを判定できる。
【００３３】
なお、図３（Ａ）および（Ｂ）のように２個のサブテーブルを組み合わせてもよいし、３個以上のサブテーブルを組み合わせて復号用参照テーブル１０４を構成してもよい。また、２つのサブテーブルの組み合わせについても、図３（Ａ）および（Ｂ）の例では先頭２ビットを基準に切り分けたが、１ビットを基準にしてもよいし、３ビットを基準にしてもよい。
【００３４】
復号用参照テーブル１０５
復号用参照テーブル１０５は、図４に示すように、２符号同時復号できる確率は大きいが容量の大きいテーブルからなる。図４のテーブル作成方法は、４ビットのインデックスｉが符号語ｃ１およびｃ２を連接したものから始まる場合には、そのインデックスｉに対応するテーブルエントリに、符号語ｃ１およびｃ２のための復号データを格納する。また、インデックスｉの値がある符号語ｃ１で始まるときには、そのインデックスｉに対応するテーブルエントリに符号語ｃ１のための復号データを格納し、ラン２とレベル２には不定値を格納する。
【００３５】
この例において、任意のビット列Ｓからインデックスｉを一意に生成する規則は、ビット列Ｓの先頭４ビットを抽出して、その４ビットの値をインデックスｉとすることである。
【００３６】
なお、復号用参照テーブル１０５は、図４のように１個のテーブルで構成することもできるが、復号用参照テーブル１０４よりも同時復号できる確率を大きくすれば、２個以上のサブテーブルを組み合わせることも可能である。２個のサブテーブルに分割する場合、ＭＰＥＧ２ではテーブルエントリが２１２オーダーと２５オーダーの組み合わせが好適である。
【００３７】
テーブル構成の性能比較
上述したように、ハフマン符号の１つの定義（図２）に対して、復号用参照テーブルの構成は１つではなく、図３及び図４のように複数存在する。このようなテーブル構成の差異は復号速度などの性能に影響する。
【００３８】
例えば、図３に示すサブテーブルの組み合わせである復号用参照テーブル１０４と図４に示す復号用参照テーブル１０５とを比較した場合、図４のテーブル１０５の方が２符号同時復号できる確率が大きいというメリットがある。すなわち、復号用参照テーブル１０４では２符号同時復号できる符号語の組み合わせは「１，１」と「００１，１」の２通りだが、図４のテーブル１０５では更に「１，００１」、「１，０１」を含む４通りである。
【００３９】
たとえば、入力ビット列が“０００１１０１”の場合、図３の復号用参照テーブル１０４であれば０００１／１／０１の３回のテーブル参照で復号されるが、図４の復号用参照テーブル１０５であれば０００１／｛１，０１｝の２回のテーブル参照で復号することができる。
【００４０】
また、図４に示すテーブル１０５ではテーブルを分割していないので、どちらのテーブルを選択するかの条件分岐が不要となり、ソフトウエアで実装した場合、条件分岐のペナルティを受けずに済むというメリットもある。
【００４１】
このようなテーブル構成の相違は、ブロックあたりの符号語数に依存して復号速度に影響する。
【００４２】
図５は、復号用参照テーブル１０４と復号用参照テーブル１０５との、ブロックあたりの符号語数に対する復号時間の変化を示すグラフである。このグラフから分かるように、ブロックあたりの符号語数が少ないときには復号用参照テーブル１０４の方が高速であるが、ある符号語数を超えて増加すると復号用参照テーブル１０５の方が効率的になる。
【００４３】
１．３）最適テーブル判定部
最適テーブル判定部１０６は、ビットレートＢＲ、ピクチャタイプＰＴおよび／またはマクロブロックタイプＭＢＴをパラメータとしてハフマン符号の一時的な分布特性を判定し、こうして判定されたハフマン符号分布特性に最適なテーブルを選択するための選択制御信号ＳＥＬを生成する。このような最適テーブル判定は、たとえば上記３つの入力条件のいずれかあるいはそれらの組み合わせと選択制御信号ＳＥＬとを関係づける判定テーブルを用いることで実現できる。
【００４４】
図６（Ａ）〜（Ｄ）および図７（Ａ）〜（Ｃ）は、それぞれ最適テーブル判定で用いられる判定テーブルの例を示す模式図である。最適テーブル判定パラメータとしては、ビットレートＢＲ、ピクチャタイプＰＲおよび／またはマクロブロックタイプＭＢＴを用いる。以下、図６および図７に例示した各判定テーブルにおける判定方法およびその利点について説明する。
【００４５】
図６（Ａ）に示す判定テーブルでは、ビットレートＢＲだけをパラメータとして用いる。この例では、４Ｍｂｐｓを境にハフマン符号の分布量の大小を判定している。ビットレートが４Ｍｂｐｓ以上ならば、１ブロックあたりのハフマン符号の個数が多いと判定し、図５に示す関係を利用して、２符号同時復号ができる確率の高い復号用参照テーブル１０５を選択する。
【００４６】
一方、ビットレートが４Ｍｂｐｓ未満ならば１ブロックあたりのハフマン符号の個数が少ないと判定し、２符号同時復号ができる確率は小さいがキャッシュミスを起こす確率の低い復号用参照テーブル１０４を選択する。
【００４７】
最適判定のためのパラメータにビットレートＢＲを用いる利点は、最適判定を行なう回数が少なくて済むことである。なぜならば、復号対象がＭＰＥＧ動画であればビットレートＢＲの値が変化するのはシーケンスの先頭だけだからである。
【００４８】
図６（Ｂ）に示す判定テーブルでは、ピクチャタイプＰＴだけをパラメータとして用いる。この例では、ピクチャタイプＰＴがＩならば１ブロックあたりのハフマン符号の個数が多いと判定し、２符号同時復号ができる確率の高い復号用参照テーブル１０５を選択する。
【００４９】
一方、ピクチャタイプＰＴがＰまたはＢならば１ブロックあたりのハフマン符号の個数が少ないと判定し、２符号同時復号ができる確率は小さいがキャッシュミスを起こす確率の低い復号用参照テーブル１０４を選択する。
【００５０】
最適判定のためのパラメータにピクチャタイプＰＴを用いる利点は、最適判定を行なう回数が比較的少なくて済むからである。なぜならば、復号対象がＭＰＥＧ動画であればピクチャタイプＰＴの値が変化するのはピクチャの先頭だけだからである。また、もう一つの利点として、最適判定に各ピクチャの性質を利用できる点である。なぜならば、復号対象がＭＰＥＧ動画であれば１ブロックあたりのハフマン符号の個数はピクチャタイプＰＴがＩ、Ｐ、Ｂの順に少なくなるからである。
【００５１】
図６（Ｃ）に示す判定テーブルでは、マクロブロックタイプＭＢＴだけをパラメータとして用いる。この例では、マクロブロックタイプＭＢＴがｉｎｔｒａならば１ブロックあたりのハフマン符号の個数が多いと判定し、２符号同時復号ができる確率の高い復号用参照テーブル１０５を選択する。
【００５２】
一方、マクロブロックタイプＭＢＴがｎｏｎ−ｉｎｔｒａならば１ブロックあたりのハフマン符号の個数が少ないと判定し、２符号同時復号ができる確率は小さいがキャッシュミスを起こす確率の低い復号用参照テーブル１０４を選択する。
【００５３】
最適判定のためのパラメータにマクロブロックタイプＭＢＴを用いる利点は、最適判定を各マクロブロックの性質を利用できる点である。なぜならば、復号対象がＭＰＥＧ動画であれば、１ブロックあたりのハフマン符号の個数はマクロブロックタイプＭＢＴがｉｎｔｒａ、ｎｏｎ−ｉｎｔｒａの順に少なくなるからである。
【００５４】
図６（Ｄ）に示す判定テーブルでは、ビットレートＢＲおよびピクチャタイプＰＴの二つをパラメータとして用いる。この例では、ビットレートＢＲが４Ｍｂｐｓ未満ならばピクチャタイプＰＴに関わらず、１ブロックあたりのハフマン符号の個数が少ないと判定し、２符号同時復号ができる確率は小さいがキャッシュミスを起こす確率の低い復号用参照テーブル１０４を選択する。
【００５５】
また、ビットレートＢＲが４Ｍｂｐｓ以上の場合は以下のような判定を行う。ピクチャタイプＰＴがＩならば１ブロックあたりのハフマン符号の個数が多いと判定し、２符号同時復号ができる確率の高い復号用参照テーブル１０５を選択する。一方、ピクチャタイプＰＴがＰまたはＢならば１ブロックあたりのハフマン符号の個数が少ないと判定し、２符号同時復号ができる確率は小さいがキャッシュミスを起こす確率の低い復号用参照テーブル１０４を選択する。
【００５６】
最適判定のためのパラメータにビットレートＢＲおよびピクチャタイプＰＴの二つを用いる利点は、最適判定を行なう回数が比較的少なくて済むからである。なぜならば、復号対象がＭＰＥＧ動画であればビットレートＢＲおよびピクチャタイプＰＴの値が変化するのは、頻度が高いピクチャタイプＰＴであってもピクチャの先頭だけだからである。また、もう一つの利点として、最適判定にビットレートＢＲおよびピクチャタイプＰＴの各性質を組み合わせて考えることで、きめ細かい判定が可能な点である。
【００５７】
図７（Ａ）に示す判定テーブルでは、ビットレートＢＲおよびマクロブロックタイプＭＢＴの二つをパラメータとして用いる。この例では、ビットレートＢＲが４Ｍｂｐｓ未満ならばマクロブロックタイプＭＢＴに関わらず、１ブロックあたりのハフマン符号の個数が少ないと判定し、２符号同時復号ができる確率は小さいがキャッシュミスを起こす確率の低い復号用参照テーブル１０４を選択する。
【００５８】
また、ビットレートＢＲが４Ｍｂｐｓ以上の場合は以下のような判定を行なう。マクロブロックタイプＭＢＴがｉｎｔｒａならば１ブロックあたりのハフマン符号の個数が多いと判定し、２符号同時復号ができる確率の高い復号用参照テーブル１０５を選択する。一方、マクロブロックタイプＭＢＴがｎｏｎ−ｉｎｔｒａならば１ブロックあたりのハフマン符号の個数が少ないと判定し、２符号同時復号ができる確率は小さいがキャッシュミスを起こす確率の低い復号用参照テーブル１０４を選択する。
【００５９】
最適判定のためのパラメータにビットレートＢＲおよびマクロブロックタイプＭＢＴの二つを用いる利点は、最適判定にビットレートＢＲとマクロブロックタイプＭＢＴの各性質を組み合わせて考えることで、きめ細かい判定が可能な点である。
【００６０】
図７（Ｂ）に示す判定テーブルでは、ピクチャタイプＰＴおよびマクロブロックタイプＭＢＴの二つをパラメータとして用いる。この例では、ピクチャタイプＰＴがＩならば１ブロックあたりのハフマン符号の個数が多いと判定し、２符号同時復号ができる確率の高い復号用参照テーブル１０５を選択する。
【００６１】
また、ピクチャタイプＰＴがＰでマクロブロックタイプＭＢＴがｉｎｔｒａならば１ブロックあたりのハフマン符号の個数が多いと判定し、２符号同時復号ができる確率の高い復号用参照テーブル１０５を選択する。
【００６２】
それ以外の場合は、１ブロックあたりのハフマン符号の個数が少ないと判定し、２符号同時復号ができる確率は小さいがキャッシュミスを起こす確率の低い復号用参照テーブル１０４を選択する。
【００６３】
最適判定のためのパラメータにピクチャタイプＰＴおよびマクロブロックタイプＭＢＴの二つを用いる利点は、最適判定にピクチャタイプＰＴとマクロブロックタイプＭＢＴの各性質を組み合わせて考えることで、きめ細かい判定が可能な点である。
【００６４】
図７（Ｃ）に示す判定テーブルでは、ビットレートＢＲ、ピクチャタイプＰＴおよびマクロブロックタイプＭＢＴの三つをパラメータとして用いる。この例では、ビットレートＢＲが４Ｍｂｐｓ未満ならば、ピクチャタイプＰＴおよびマクロブロックタイプＭＢＴに関わらず、１ブロックあたりのハフマン符号の個数が少ないと判定し、２符号同時復号ができる確率は小さいがキャッシュミスを起こす確率の低い復号用参照テーブル１０４を選択する。
【００６５】
また、ビットレートＢＲが４Ｍｂｐｓ以上の場合は以下のような判定を行う。ピクチャタイプＰＴがＩならば１ブロックあたりのハフマン符号の個数が多いと判定し、２符号同時復号ができる確率の高い復号用参照テーブル１０５を選択する。
【００６６】
また、ピクチャタイプＰＴがＰでマクロブロックタイプＭＢＴがｉｎｔｒａならば１ブロックあたりのハフマン符号の個数が多いと判定し、２符号同時復号ができる確率の高い復号用参照テーブル１０５を選択する。
【００６７】
それ以外の場合は、１ブロックあたりのハフマン符号の個数が少ないと判定し、２符号同時復号ができる確率は小さいがキャッシュミスを起こす確率の低い復号用参照テーブル１０４を選択する。
【００６８】
最適判定のためのパラメータにビットレートＢＲ、ピクチャタイプＰＴおよびマクロブロックタイプＭＢＴの三つを用いる利点は、最適判定にビットレートＢＲ、ピクチャタイプＰＴおよびマクロブロックタイプＭＢＴの各性質を組み合わせて考えることで、きめ細かい判定が可能な点である。
【００６９】
以上例示した最適判定のパラメータとして最も優れた組み合わせは、図６（Ｄ）に示すビットレートＢＲおよびピクチャタイプＰＴの組み合わせである。その理由は、きめ細かい判定ができるのにも関わらず判定が必要なのはピクチャの先頭だけであるので、判定に要する演算時間が非常に短くて済むからである。
【００７０】
１．４）動作
図８は、図１に示すハフマン符号復号装置の全体的動作を示すフローチャートである。
【００７１】
まず、最適テーブル判定部１０６は、上述したようにビットレートＢＲ、ピクチャタイプＰＴおよび／またはマクロブロックタイプＭＢＴをパラメータとしてハフマン符号の一時的な分布特性を判定し、判定されたハフマン符号分布特性に最適な復号用参照テーブルを選択するための選択制御信号ＳＥＬをスイッチ１０３へ出力する。スイッチ１０３は、選択制御信号ＳＥＬに従って、テーブル参照部１０２を復号用参照テーブル１０４および１０５のいずれかに接続する（ステップＡ０）。
【００７２】
続いて、ビット列バッファ１０１では、読み出しポインタが指すビットからＮビット長（Ｎはハフマン符号の最大符号長）のビット列をテーブル参照部１０２へ出力する（ステップＡ１）。
【００７３】
テーブル参照部１０２は、Ｎビット長のビット列を用いて復号用参照テーブルのインデックス（ｉ）を生成し（ステップＡ２）、スイッチ１０３を通して接続された復号用参照テーブルへ出力する。インデックス（ｉ）を入力した復号用参照テーブルは、対応するエントリ＜ｌｅｎ，ｒｕｎ＿１，ｌｅｖｅｌ＿１，ｒｕｎ＿２，ｌｅｖｅｌ＿２＞を検索し、スイッチ１０３を通してテーブル参照部１０２へ返す。
【００７４】
インデックス（ｉ）が指すエントリを受け取ると（ステップＡ３）、テーブル参照部１０２は、符号長（ｌｅｎ）をビット列バッファ１０１に出力する。符号長（ｌｅｎ）を受け取ると、ビット列バッファ１０２は読み出しポインタを符号長（ｌｅｎ）だけ進める（ステップＡ４）。
【００７５】
さらに、テーブル参照部１０２は、受け取ったエントリから＜ｒｕｎ＿１，ｌｅｖｅｌ＿１＞の組を復号結果（１）として出力し、＜ｒｕｎ＿２，ｌｅｖｅｌ＿２＞の組を復号結果（２）として出力する（ステップＡ５）。
【００７６】
ここで、エントリ＜ｌｅｎ，ｒｕｎ＿１，ｌｅｖｅｌ＿１，ｒｕｎ＿２，ｌｅｖｅｌ＿２＞にＥＯＢを示す値が含まれていれば（ステップＡ６のイエス）、処理を終了し、そうでなければ（ステップＡ６のノー）、ステップＡ１へ戻って上述した処理を繰り返す。
【００７７】
以上の処理を繰り返すことにより、量子化されたＤＣＴ係数ブロックからハフマン符号を復号することができる。
【００７８】
なお、この動作手順では、全てのＤＣＴ係数ブロックに対してステップＡ０で最適なテーブルを選択しているが、マクロブロックの先頭でのみテーブルを選択し、マクロブロックの先頭のブロック以外ではステップＡ０を省略してステップＡ１から実行してもよい。これにより、テーブル選択に必要な演算量を削減することができる。また、テーブル選択の判定がマクロブロックタイプＭＢＴに依存しなければ、テーブルの選択はピクチャの先頭で一度行うだけでよいので、さらに演算量を削減することができる。
【００７９】
また、全ての符号語においてＥＯＢが含まれるか否かをステップＡ６でチェックしているが、多くの符号化方式においてＤＣＴ係数ブロックの最初の符号語にＥＯＢが含まれることはないので、最初の符号語に対してはステップＡ６を省略してステップＡ１を実行してもよい。
【００８０】
また、ビット列バッファ１０１からＮビットのビット列を読み込む場合について説明したが、Ｎビットより多くのビット数を読み込む場合でも本実施形態を適用できるのは明らかである。また、Ｎビット未満のビット数を読み込むときは、読み込んだビット数が符号長に満たない場合だけ最終的にＮビット読み込めばよい。
【００８１】
さらに、２つの復号用参照テーブル１０４および１０５を選択する場合について説明したが、３つ以上のそれぞれ異なる構成の復号用参照テーブルを設け、それらをパラメータに従って選択する場合でも本発明を適用できるのは明らかである。
【００８２】
なお、ここでは、動画像信号の可変長符号を一例として説明したが、本発明がオーディオ信号あるいは音声信号のハフマン符号の復号にも適用できることは言うまでもない。
【００８３】
１．５）効果
本実施形態によるハフマン符号復号装置は、それぞれテーブル構成が異なる複数の復号用参照テーブルを設け、それらをハフマン符号の一時的な分布特性に応じて切り替える。このような構成により、ハフマン符号の分布に応じた最適な復号用参照テーブルを選択することができ、従来よりも高速にハフマン符号を復号できる。
【００８４】
２．第２実施形態
２．１）構成
図９は、本発明の第２実施形態によるハフマン符号復号装置の構成を示すブロック図である。ここでは、本発明をＭＰＥＧ２に準拠した動画像信号のハフマン符号の復号に適用する。ＭＰＥＧ２ではハフマン符号化に２種類の符号化方法を用いているため、符号化方法に応じた復号用参照テーブルが必要である。したがって、本実施形態によるハフマン符号復号装置は、２つの符号化方法の各々に２つの復号用参照テーブルを設け、入力符号化信号のパラメータに基づいていずれかの復号用参照テーブルを選択して復号処理を行う。以下、詳述する。
【００８５】
図９において、ビット列バッファ１０１およびテーブル参照部１０２は、図１に示す第１実施形態と同様であるから、同一参照番号を付して説明は省略する。
【００８６】
テーブル参照部１０２は、スイッチ２０１とスイッチ２０３あるいは２０４とを介して、復号用参照テーブル２０５、２０６，２０７および２０８のいずれかに接続される。復号用参照テーブル２０５および２０６は、一方の符号化方法に対応し、テーブル格納手段Ｃ１に格納される。復号用参照テーブル２０７および２０８は、他方の符号化方法に対応し、テーブル格納手段Ｃ２に格納される。
【００８７】
テーブル参照部１０２は、入力ビット列から生成されたインデックスをスイッチ２０１とスイッチ２０３あるいは２０４とを介して選択された復号用参照テーブルへ出力し、それに対応したテーブルエントリを受け取り、そのエントリから復号データを抽出する。
【００８８】
復号用参照テーブル２０５〜２０８は、ハフマン符号復号用のテーブルであり、それぞれ単独で入力ビット列の復号が可能であるがテーブル構成が異なっている。復号用参照テーブル２０５および２０６は、一方の符号化方法（Ｃ１）に対応するテーブルであり、復号用参照テーブル２０５は同時復号できる確率は小さいが容量の小さいテーブル、復号用参照テーブル２０６は同時復号できる確率は大きいが容量の大きいテーブルである。他方、復号用参照テーブル２０７および２０８は、他方の符号化方法（Ｃ２）に対応するテーブルであり、復号用参照テーブル２０７は同時復号できる確率は小さいが容量の小さいテーブル、復号用参照テーブル２０８は同時復号できる確率は大きいが容量の大きいテーブルである。
【００８９】
スイッチ２０１は、符号化方法判定部２０２からの選択制御信号ＳＥＬ０に従って動作し、スイッチ２０３および２０４のいずれかをテーブル参照部１０２に接続する。符号化方法判定部２０２は、ＭＰＥＧ２のマクロブロックタイプＭＢＴおよびｉｎｆｒａ＿ｖｌｃ＿ｆｏｒｍａｔを入力し、それらの値の組み合わせから、どちらの符号化方法が用いられたのかを判定し、符号化方法の選択制御信号ＳＥＬ０をスイッチ２０１へ出力する。
【００９０】
スイッチ２０３および２０４は、それぞれ、最適テーブル判定部２０９からの選択制御信号ＳＥＬ１およびＳＥＬ１に従って動作する。スイッチ２０３は、復号用参照テーブル２０５および２０６のいずれかをスイッチ２０１に接続し、スイッチ２０４は、復号用参照テーブル２０７および２０８のいずれかをスイッチ２０１に接続する。
【００９１】
最適テーブル判定部２０９は、ＭＰＥＧ２のビットレートＢＲ、ピクチャタイプＰＴおよび／またはマクロブロックタイプＭＢＴに基づいてハフマン符号の一時的な分布特性を判定し、判定されたハフマン符号分布特性に最適なテーブルを選択するための選択制御信号ＳＥＬ１およびＳＥＬ１をそれぞれスイッチ２０３および２０４へ出力する。その際、符号化方法判定部２０２から符号化方法の選択制御信号ＳＥＬ０を入力してどちらの符号化方法が使用されているが分かっていれば、選択されている符号化方法のスイッチだけを制御すればよい。したがって、最適テーブル判定部２０９の動作は、基本的に第１実施形態の最適テーブル判定部１０６と同様である。
【００９２】
２．２）動作
符号化方法が切り替えられるのはマクロブロック単位であるから、ＤＣＴ係数ブロックごとに復号用参照テーブル２０５および２０６と復号用参照テーブル２０７および２０８とを切り替える必要はない。したがって、マクロブロックの最初のＤＣＴ係数ブロックにおいて、いずれかの符号化方法の復号用参照テーブルへ切り替えておけば、ＭＰＥＧ２に準拠した動画像信号のハフマン符号参照手順は図８のフローチャートをそのまま用いることができる。
【００９３】
まず、符号化方法判定部２０２は、ＭＰＥＧ２のマクロブロックタイプＭＢＴおよびｉｎｆｒａ＿ｖｌｃ＿ｆｏｒｍａｔを入力し、それらの値の組み合わせから、どちらの符号化方法が用いられたのかを判定し、符号化方法の選択制御信号ＳＥＬ０をスイッチ２０１へ出力する。これによって、テーブル参照部１０２は、符号化方法Ｃ１の側のスイッチ２０３および符号化方法Ｃ２の側のスイッチ２０４のいずれかに接続される。
【００９４】
続いて、最適テーブル判定部２０９は、ビットレートＢＲ、ピクチャタイプＰＴおよび／またはマクロブロックタイプＭＢＴをパラメータとしてハフマン符号の一時的な分布特性を判定し、判定されたハフマン符号分布特性に最適なテーブルを選択するための選択制御信号ＳＥＬ１あるいはＳＥＬ２をスイッチ２０３あるいは２０４へ出力する。これによって、テーブル参照部１０２は、復号用参照テーブル２０５〜２０８のいずれかに接続される（図８のステップＡ０）。
【００９５】
続いて、ビット列バッファ１０１では、読み出しポインタが指すビットからＮビット長（Ｎはハフマン符号の最大符号長）のビット列をテーブル参照部１０２へ出力する（図８のステップＡ１）。
【００９６】
テーブル参照部１０２は、Ｎビット長のビット列を用いて復号用参照テーブルのインデックス（ｉ）を生成し（図８のステップＡ２）、スイッチ２０１とスイッチ２０３あるいは２０４とを通して接続された復号用参照テーブルへ出力する。インデックス（ｉ）を入力した復号用参照テーブルは、対応するエントリ＜ｌｅｎ，ｒｕｎ＿１，ｌｅｖｅｌ＿１，ｒｕｎ＿２，ｌｅｖｅｌ＿２＞を検索しテーブル参照部１０２へ返す。
【００９７】
インデックス（ｉ）が指すエントリを受け取ると（図８のステップＡ３）、テーブル参照部１０２は、符号長（ｌｅｎ）をビット列バッファ１０１に出力する。符号長（ｌｅｎ）を受け取ると、ビット列バッファ１０２は読み出しポインタを符号長（ｌｅｎ）だけ進める（図８のステップＡ４）。
【００９８】
さらに、テーブル参照部１０２は、受け取ったエントリから＜ｒｕｎ＿１，ｌｅｖｅｌ＿１＞の組を復号結果（１）として出力し、＜ｒｕｎ＿２，ｌｅｖｅｌ＿２＞の組を復号結果（２）として出力する（図８のステップＡ５）。
【００９９】
ここで、エントリ＜ｌｅｎ，ｒｕｎ＿１，ｌｅｖｅｌ＿１，ｒｕｎ＿２，ｌｅｖｅｌ＿２＞にＥＯＢを示す値が含まれていれば（図８のステップＡ６のイエス）、処理を終了し、そうでなければ（図８のステップＡ６のノー）、ステップＡ１へ戻って上述した処理を繰り返す。
【０１００】
以上の処理を繰り返すことにより、量子化されたＤＣＴ係数ブロックからハフマン符号を復号することができる。
【０１０１】
２．３）効果
本実施形態によれば、ハフマン符号の符号化方法の１つに対して、複数の復号用参照テーブルを設け、それらをハフマン符号の一時的な分布特性に応じて切り替える。これにより、ＭＰＥＧ２におけるハフマン符号の分布に応じて最適な復号用参照テーブルを参照してハフマン符号を復号でき、従来よりも高速にハフマン符号を復号できる。
【０１０２】
３．第３実施形態
図１０は、本発明の第３実施形態によるハフマン符号復号装置のブロック図である。本実施形態は、プロセッサ３０１と、上述したハフマン符号復号装置を実現するためのハフマン符号復号プログラムを格納したプログラムメモリ３０２と、複数の復号用参照テーブルを格納したメモリ３０３とを有し、ソフトウエアにより可変長符号の復号を実行する。すなわち、プロセッサ３０１上でハフマン符号復号プログラムを実行することにより、図１あるいは図９に示すハフマン符号復号装置を構成し、図８に示す動作を実行することができる。なお、プログラムメモリ３０２は、磁気ディスク、半導体メモリ、ＣＤ−ＲＯＭその他の記録媒体であってよい。
【０１０３】
このように、ソフトウエアにより可変長符号の復号を実行する場合でも、本発明によれば、高速性、２符号同時復号できる確率、条件分岐ミスが発生する確率およびキャッシュミスが発生する確率のトレードオフを最適に調整することができ、復号性能を向上させることができる。
【０１０４】
【発明の効果】
以上説明したように、本発明によれば、テーブル構成の異なる復号用参照テーブルを設け、可変長符号の一時的な分布特性に基づいて最適な復号用参照テーブルを選択できるために、可変長符号を高速に復号することができる。また、その分布特性を判定するための演算量が少ないために、可変長符号の分布特性の変化に対して高速に対応することができ、高速且つ高性能の可変長符号復号を実現できる。
【図面の簡単な説明】
【図１】本発明の第１実施形態によるハフマン符号復号装置の構成を示すブロック図である。
【図２】ハフマン符号の定義の一例を示す模式図である。
【図３】（Ａ）および（Ｂ）は、それぞれ、図２に示すハフマン符号定義例に従った復号用参照テーブル１０４のサブテーブルの一例を示す模式図である。
【図４】図２に示すハフマン符号定義例に従った復号用参照テーブル１０５の一例を示す模式図である。
【図５】復号用参照テーブル１０４と復号用参照テーブル１０５との、ブロックあたりの符号語数に対する復号時間の変化を示すグラフである。
【図６】（Ａ）〜（Ｄ）は、それぞれ最適テーブル判定で用いられる判定テーブルの例を示す模式図である。
【図７】（Ａ）〜（Ｃ）は、それぞれ最適テーブル判定で用いられる判定テーブルの例を示す模式図である。
【図８】図１に示すハフマン符号復号装置の全体的動作を示すフローチャートである。
【図９】本発明の第２実施形態によるハフマン符号復号装置の構成を示すブロック図である。
【図１０】本発明の第３実施形態によるハフマン符号復号装置のブロック図である。
【符号の説明】
１０１　ビット列バッファ
１０２　テーブル参照部
１０３　スイッチ
１０４　復号用参照テーブル
１０５　復号用参照テーブル
１０６　最適テーブル判定部
２０１　スイッチ
２０２　符号化方法判定部
２０３　スイッチ
２０４　スイッチ
２０５〜２０８　復号用参照テーブル
２０９　最適テーブル判定部
３０１　プロセッサ
３０２　プログラムメモリ
３０３　メモリ
【図１】
2004120274.tif 000003
【図２】
2004120274.tif 000004
【図３】
2004120274.tif 000005
【図４】
2004120274.tif 000006
【図５】
2004120274.tif 000007
【図６】
2004120274.tif 000008
【図７】
2004120274.tif 000009
【図８】
2004120274.tif 000010
【図９】
2004120274.tif 000011
【図１０】
2004120274.tif 000012