(57)【要約】【課題】従来に比べて小さなサイズのテーブルで可変長符号を復号する。【解決手段】ハフマンデコーダは、入力ビット列を４つの小ビット列に分割し、これらのうち今回復号しようとしているハフマン符号の末尾のビットを含む小ビット列を末尾小ビット列とし、該末尾小ビット列内の最上位のビットからそのハフマン符号の末尾のビットまでを検索用ビット列とする。また、末尾小ビット列よりも上位に存在する各小ビット列のビットの並びに対応する数値を第１テーブルから読み出し、各数値の総和を検索用サムとする。第１テーブルでは、各小ビット列のそれぞれの４ビット長のビットの並びごとに固有の数値が対応し、第ｉ小ビット列のビットの並びに対応する数値はいずれも第（ｉ−１）小ビット列のビットの並びに対応する数値より大きくなっている。そして、第２テーブルから、今回設定された検索用ビット列と検索用サムとの組合せに対応するカテゴリ値を読み出す。【選択図】図２
2010041179.tif 000002
【特許請求の範囲】
【請求項１】
今回復号しようとしている可変長符号を含むビット列を、ｎ個（ｎは３以上の整数）の小ビット列に分割するビット列分割手段と、
前記小ビット列のうち今回復号しようとしている可変長符号の末尾のビットを含む小ビット列を末尾小ビット列とし、該末尾小ビット列内の最上位のビットから今回復号しようとしている可変長符号の末尾のビットまでのビット列を検索用ビット列に設定する検索用ビット列設定手段と、
各小ビット列のビットの並びごとに異なる数値を対応づけて記憶する数値記憶手段と、
前記末尾小ビット列よりも上位に存在する各小ビット列のビットの並びに対応する数値を前記数値記憶手段から読み出し、該読み出した数値の総和を検索用サムに設定する検索用サム設定手段と、
予め検索用ビット列と検索用サムとの取りうる組合せと可変長符号の表す情報とを１対１に対応づけて記憶する情報記憶手段と、
前記検索用ビット列設定手段によって設定された前記検索用ビット列と前記検索用サム設定手段によって設定された検索用サムとの組合せに対応する情報を前記情報記憶手段から読み出す情報読出手段と、
を備え、
前記数値記憶手段は、先頭からｉ番目（ｉは２以上ｎ未満の整数）の小ビット列のビットの並びに対応する数値が、いずれも第（ｉ−１）番目の小ビット列のビットの並びに対応する数値より大きくなるように設定されているか、又は、先頭からｉ番目の小ビット列のビットの並びに対応する数値が、いずれも第（ｉ−１）番目の小ビット列のビットの並びに対応する数値より小さくなるように設定されている、
可変長符号の復号装置。
【請求項２】
前記ビット列分割手段は、可変長符号の最長のビット長さ分のビット列を入力し、該入力したビット列をｎ個の小ビット列に分割する、
請求項１に記載の可変長符号の復号装置。
【請求項３】
前記検索用ビット列設定手段は、各小ビット列内の上位ｊビット（ｊは１以上小ビット列内の最大ビット数以下の整数）である部分ビット列の各々につき、可変長符号の有効な候補か否かの第１判定を実行し、各小ビット列で前記有効な候補と判定された部分ビット列同士の組合せが可変長符号となり得るかの第２判定を実行し、前記可変長符号となり得る組合せの末尾の部分ビット列を前記検索用ビット列に設定する、
請求項１又は２に記載の可変長符号の復号装置。
【請求項４】
前記検索用ビット列設定手段は、前記ビット列分割手段によって分割された複数の小ビット列の各々に対する前記第１判定を同時並行で処理すると共に、前記複数の小ビット列の各々に対する前記第２判定も同時並行で処理する、
請求項３に記載の可変長符号の復号装置。
【請求項５】
（ａ）今回復号しようとしている可変長符号を含むビット列を、ｎ個（ｎは３以上の整数）の小ビット列に分割するステップと、
（ｂ）前記小ビット列のうち今回復号しようとしている可変長符号の末尾のビットを含む小ビット列を末尾小ビット列とし、該末尾小ビット列内の最上位のビットから今回復号しようとしている可変長符号の末尾のビットまでのビット列を検索用ビット列に設定するステップと、
（ｃ）各小ビット列のビットの並びごとに異なる数値を対応づけて記憶する数値記憶手段から、前記末尾小ビット列よりも上位に存在する各小ビット列のビットの並びに対応する数値を読み出し、該読み出した数値の総和を検索用サムに設定するステップと、
（ｄ）予め検索用ビット列と検索用サムとの取りうる組合せと可変長符号の表す情報とを１対１に対応づけて記憶する情報記憶手段から、前記設定された前記検索用ビット列と前記設定された検索用サムとの組合せに対応する情報を読み出すステップと、
を含み、
前記数値記憶手段は、先頭からｉ番目（ｉは２以上ｎ未満の整数）の小ビット列のビットの並びに対応する数値が、いずれも第（ｉ−１）番目の小ビット列のビットの並びに対応する数値より大きくなるように設定されているか、又は、先頭からｉ番目の小ビット列のビットの並びに対応する数値が、いずれも第（ｉ−１）番目の小ビット列のビットの並びに対応する数値より小さくなるように設定されている、
可変長符号の復号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、可変長符号の復号装置及びその復号方法に関する。
【背景技術】
【０００２】
従来より、種々の画像圧縮技術が知られている。例えば、静止画の圧縮画像技術としてはＪＰＥＧ（Ｊｏｉｎｔ Ｐｈｏｔｏｇｒａｐｈｉｃ Ｅｘｐｅｒｔｓ Ｇｒｏｕｐ）が広く利用され、動画の圧縮画像技術としてはＭＰＥＧ（Ｍｏｖｉｎｇ Ｐｉｃｔｕｒｅ ＥｘｐｅｒｔｓＧｒｏｕｐ）が広く利用されている。ＪＰＥＧの場合、画像を水平８画素×垂直８画素の合計６４画素からなる複数のブロックに分割し、それぞれのブロックを単位として符号化及び復号化の処理が行われる。符号化では、まず、各画素の画素値（０〜２５５）から１２８を差し引いて−１２８〜１２７の範囲の数にレベルシフトしてから、周波数成分の大きさを表す離散コサイン係数（ＤＣＴ係数）に変換する。通常の画像では高い周波数成分が少ないため、ＤＣＴ係数は水平８画素×垂直８画素の合計６４画素のうち左上が大きく左下が小さい値になる。そして、高い周波数成分の変化は視覚上捉えにくいという特徴があることから、低い周波数成分の省略が少なく、高い周波数成分の省略が大きくなるようにＤＣＴ係数の量子化を行う。各ブロックの左上端のＤＣＴ係数は、直流（ＤＣ）成分なのでＤＣ係数と呼ばれ、ブロック内の各画素値の平均を表す。なお、第１番目のブロック以外のＤＣ係数は、後続のブロックのＤＣ係数との差分すなわちＤＣ差分値であるが、便宜上ＤＣ係数と呼ぶ。また、各ブロックのうちＤＣ成分以外の６３個のＤＣＴ係数は、交流（ＡＣ）成分なのでＡＣ係数と呼ばれ、ブロック内で画素値がどのように変化しているかを表す。
【０００３】
ＤＣ係数については、ＤＣ係数をそのまま符号化できるようにハフマン符号が用意されている。例えば、ＤＣ係数が１１ビットで表される場合には、ＤＣ係数は−１０２４〜１０２３の値をとるので、後続のブロックのＤＣ係数との差分は−２０４７〜２０４７の値を取ることになる。このため、−２０４７〜２０４７の数を１２グループに分け、第０グループはゼロのみ、第１グループは−１と１、第２グループは−３，−２，２，３、……というように分類する。そして、差分を表す各数字がどのグループに属するかをハフマン符号（例えば００とか０１０とか１００など）で区別する。このハフマン符号は、圧縮効率を考慮して、出現頻度が多いほど短い符号となるように定められている。また、グループ内の区別は、ハフマン符号に続く付加ビットにより行う。例えば、第０グループの場合は０しか存在しないため付加ビットはなし、第１グループの場合は−１か１を区別するのに１ビットあれば十分なため付加ビットは１ビット、第２グループの場合は−３，−２，２，３を区別するのに２ビットあれば十分なため付加ビットは２ビット、という具合に定められている。
【０００４】
ＡＣ係数については、水平８画素×垂直８画素の合計６４画素のうち、各画素を周波数の低い順となるように図７に示すようにジグザグにスキャンされる。具体的には、左上端のＤＣ係数（値１２）のあと、ＡＣ係数の符号化順序は値７２，１６，７，−３０，０，０，５，０，０，…となる。ＡＣ係数は、ブロック内の明るさの変化を表すが、その変化はあまり大きくないため、多くはゼロ（無効係数）になる。このため、ＡＣ係数は、ゼロが連続する個数（ゼロランレングス）と、連続するゼロの次に来るゼロでない係数（有効係数）を表す付加ビットの長さ（付加ビット数）とをセットにして符号化する。これを繰り返し、残りがゼロばかりになれば、ブロックの符号は終了という意味でＥＯＢ符号（ＥＯＢはエンド・オブ・ブロックの略）を付けてブロックの符号化を終了する。なお、ＤＣ係数は、後続のブロックとの相関が強いので後続のブロックとの差分を取ったが、ＡＣ係数は、後続のブロックとの相関が弱いのでブロック内だけで符号化する。図７の例では、ビット列は、ゼロランレングスの値０と有効係数の値７２を表す付加ビットの長さを意味するハフマン符号、有効係数の値７２を表す付加ビット、ゼロランレングスの値０と有効係数の値１６を表す付加ビットの長さを意味するハフマン符号、有効係数の値１６を表す付加ビット、ゼロランレングスの値０と有効係数の値７を表す付加ビットの長さを意味するハフマン符号、有効係数の値７を表す付加ビット、ゼロランレングスの値０と有効係数の値−３０を表す付加ビットの長さを意味するハフマン符号、有効係数の値−３０を表す付加ビット、ゼロランレングスの値２と有効係数の値５を表す付加ビットの長さを意味するハフマン符号、有効係数の値５を表す付加ビット、最後にＥＯＢを表すハフマン符号となる。こうしたＤＣ係数及びＡＣ係数のそれぞれのハフマン符号のテーブルの一例が、特許文献１に記載されている。
【特許文献１】特開２００６−２９５６３１
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、特許文献１に記載されたＡＣ係数のハフマン符号のテーブルは、最大１６ビット長のハフマン符号をインデックスとしてゼロランレングスの値と付加ビット数とを読み出すものであるから、インデックスのデータサイズが大きくなり、ひいては大きなサイズのテーブルが必要になるという問題があった。
【０００６】
本発明は、従来に比べて小さなサイズのテーブルでハフマン符号に代表される可変長符号を復号することを主目的とする。
【課題を解決するための手段】
【０００７】
本発明は、上述の主目的を達成するために以下の手段を採った。
【０００８】
本発明の可変長符号の復号装置は、
今回復号しようとしている可変長符号を含むビット列を、ｎ個（ｎは３以上の整数）の小ビット列に分割するビット列分割手段と、
前記小ビット列のうち今回復号しようとしている可変長符号の末尾のビットを含む小ビット列を末尾小ビット列とし、該末尾小ビット列内の最上位のビットから今回復号しようとしている可変長符号の末尾のビットまでのビット列を検索用ビット列に設定する検索用ビット列設定手段と、
各小ビット列のビットの並びごとに異なる数値を対応づけて記憶する数値記憶手段と、
前記末尾小ビット列よりも上位に存在する各小ビット列のビットの並びに対応する数値を前記数値記憶手段から読み出し、該読み出した数値の総和を検索用サムに設定する検索用サム設定手段と、
予め検索用ビット列と検索用サムとの取りうる組合せと可変長符号の表す情報とを１対１に対応づけて記憶する情報記憶手段と、
前記検索用ビット列設定手段によって設定された前記検索用ビット列と前記検索用サム設定手段によって設定された検索用サムとの組合せに対応する情報を前記情報記憶手段から読み出す情報読出手段と、
を備え、
前記数値記憶手段は、先頭からｉ番目（ｉは２以上ｎ未満の整数）の小ビット列のビットの並びに対応する数値が、いずれも第（ｉ−１）番目の小ビット列のビットの並びに対応する数値より大きくなるように設定されているか、又は、先頭からｉ番目の小ビット列のビットの並びに対応する数値が、いずれも第（ｉ−１）番目の小ビット列のビットの並びに対応する数値より小さくなるように設定されている、
ものである。
【０００９】
この可変長符号の復号装置では、予め検索用ビット列と検索用サムとの取りうる組合せと可変長符号の表す情報とを１対１に対応づけて記憶する情報記憶手段を用意しておく。そして、検索用ビット列設定手段によって設定された検索用ビット列と検索用サム設定手段によって設定された検索用サムとの組合せに対応づけられている情報を、その情報記憶手段から読み出す。ここで、検索用サムを設定する際に用いる数値記憶手段は、先頭からｉ番目（ｉは２以上ｎ未満の整数）の小ビット列のビットの並びに対応する数値が、いずれも第（ｉ−１）番目の小ビット列のビットの並びに対応する数値より大きくなるように設定されているか、又は、先頭からｉ番目の小ビット列のビットの並びに対応する数値が、いずれも第（ｉ−１）番目の小ビット列のビットの並びに対応する数値より小さくなるように設定されている。可変長符号の性質上、検索用ビット列が同じ可変長符号は、その検索用ビット列よりも上位のビットの並びが必ず異なることから、上述した数値記憶手段を用いて検索用サムを設定することにより各検索用サムは必ず異なる値となる。また、検索用サムが同じ可変長符号は、その検索用ビット列が必ず異なるビットの並びとなる。このため、検索用ビット列と検索用サムとの組合せは、それぞれ異なる可変長符号に対応することになる。また、検索用ビット列と検索用サムとの組合せを表すデータ量は、可変長符号を表すデータ量よりも容易に少なくすることができる。したがって、従来に比べて小さなサイズのテーブルでハフマン符号に代表される可変長符号を復号することができる。
【００１０】
本発明の可変長符号の復号装置において、前記ビット列分割手段は、可変長符号の最長のビット長さ分のビット列を入力し、該入力したビット列をｎ個の小ビット列に分割してもよい。可変長符号を連続して入力する場合、一つ一つの可変長符号のビット長は入力時には不明である。このため、とりあえず可変長符号の最長のビット長さ分のビット列を入力するのが好ましい。
【００１１】
本発明の可変長符号の復号装置において、前記検索用ビット列設定手段は、各小ビット列内の上位ｊビット（ｊは１以上小ビット列内の最大ビット数以下の整数）である部分ビット列の各々につき、可変長符号の有効な候補か否かの第１判定を実行し、各小ビット列で前記有効な候補と判定された部分ビット列同士の組合せが可変長符号となり得るかの第２判定を実行し、前記可変長符号となり得る組合せの末尾の部分ビット列を前記検索用ビット列に設定してもよい。こうすれば、検索用ビット列を確実に設定することができる。
【００１２】
このように前記検索用ビット列設定手段が前記第１判定及び前記第２判定を行うことにより前記検索用ビット列の設定を行う本発明の可変長符号の復号装置において、前記検索用ビット列設定手段は、前記ビット列分割手段によって分割された複数の小ビット列の各々に対する前記第１判定を同時並行で処理すると共に、前記複数の小ビット列の各々に対する前記第２判定も同時並行で処理してもよい。こうすれば、可変長符号のビット長にかかわらず、可変長符号を復号するのに要する時間を同じにすることが可能となる。具体的には、小ビット列の数だけ第１及び第２判定を実行可能な比較器あるいはプロセッサを備えるようにしてもよい。
【００１３】
本発明の可変長符号の復号方法は、
（ａ）今回復号しようとしている可変長符号を含むビット列を、ｎ個（ｎは３以上の整数）の小ビット列に分割するステップと、
（ｂ）前記小ビット列のうち今回復号しようとしている可変長符号の末尾のビットを含む小ビット列を末尾小ビット列とし、該末尾小ビット列内の最上位のビットから今回復号しようとしている可変長符号の末尾のビットまでのビット列を検索用ビット列に設定するステップと、
（ｃ）各小ビット列のビットの並びごとに異なる数値を対応づけて記憶する数値記憶手段から、前記末尾小ビット列よりも上位に存在する各小ビット列のビットの並びに対応する数値を読み出し、該読み出した数値の総和を検索用サムに設定するステップと、
（ｄ）予め検索用ビット列と検索用サムとの取りうる組合せと可変長符号の表す情報とを１対１に対応づけて記憶する情報記憶手段から、前記設定された前記検索用ビット列と前記設定された検索用サムとの組合せに対応する情報を読み出すステップと、
を含み、
前記数値記憶手段は、先頭からｉ番目（ｉは２以上ｎ未満の整数）の小ビット列のビットの並びに対応する数値が、いずれも第（ｉ−１）番目の小ビット列のビットの並びに対応する数値より大きくなるように設定されているか、又は、先頭からｉ番目の小ビット列のビットの並びに対応する数値が、いずれも第（ｉ−１）番目の小ビット列のビットの並びに対応する数値より小さくなるように設定されている、
ものである。
【００１４】
この可変長符号の復号方法では、予め検索用ビット列と検索用サムとの取りうる組合せと可変長符号の表す情報とを１対１に対応づけて記憶する情報記憶手段を用意しておく。そして、検索用ビット列設定手段によって設定された検索用ビット列と検索用サム設定手段によって設定された検索用サムとの組合せに対応づけられている情報を、その情報記憶手段から読み出す。ここで、検索用サムを設定する際に用いる数値記憶手段は、先頭からｉ番目（ｉは２以上ｎ未満の整数）の小ビット列のビットの並びに対応する数値が、いずれも第（ｉ−１）番目の小ビット列のビットの並びに対応する数値より大きくなるように設定されているか、又は、先頭からｉ番目の小ビット列のビットの並びに対応する数値が、いずれも第（ｉ−１）番目の小ビット列のビットの並びに対応する数値より小さくなるように設定されている。可変長符号の性質上、検索用ビット列が同じ可変長符号は、その検索用ビット列よりも上位のビットの並びが必ず異なることから、上述した数値記憶手段を用いて検索用サムを設定することにより各検索用サムは必ず異なる値となる。また、検索用サムが同じ可変長符号は、その検索用ビット列が必ず異なるビットの並びとなる。このため、検索用ビット列と検索用サムとの組合せは、それぞれ異なる可変長符号に対応することになる。また、検索用ビット列と検索用サムとの組合せを表すデータ量は、可変長符号を表すデータ量よりも容易に少なくすることができる。したがって、従来に比べて小さなサイズのテーブルでハフマン符号に代表される可変長符号を復号することができる。なお、こうした復号方法において、上述した本発明の可変長符号の復号装置が備える各種の構成によって奏される作用・機能を実現するためのステップを追加してもよい。
【発明を実施するための最良の形態】
【００１５】
次に、本発明の実施の形態を図面に基づいて説明する。図１は、本発明の一実施形態であるハフマンデコーダ１０の構成の概略を示す構成図である。
【００１６】
本実施形態のハフマンデコーダ１０は、静止画の圧縮画像技術の一つであるＪＰＥＧに用いられるビット長が最大１６ビットのハフマン符号を復号化するための装置である。このハフマンデコーダ１０は、図１に示すように、入力ビット列を分割するビット列分割器２０と、第１〜第４小ビット列ａ〜ｄの処理を各々実行する第１〜第４比較器群２１〜２４と、各種のデータを格納するメモリ２５〜３０と、ハフマン符号を復号して量子化ＤＣＴ係数に変換する変換器３２とを備えている。このハフマンデコーダ１０には、入力器４０を介して、ハフマン符号の最大長（１６ビット長）の入力ビット列が入力される。入力器４０は、バス５２を介してＣＰＵ５０からデータを入力し、そのデータの先頭から１６ビット分を入力ビット列としてハフマンデコーダ１０に出力する。また、ハフマンデコーダ１０からは、量子化ＤＣＴ係数が逆量子化回路６０に出力される。逆量子化回路６０は、図示しない量子化テーブルを利用してハフマンデコーダ１０から入力した量子化ＤＣＴ係数を逆量子化してＤＣＴ係数を復元する。なお、ＣＰＵ５０は、このように復元されたＤＣＴ係数に逆ＤＣＴを施すことによりレベルシフト後の画素値に変換し、その画素値を逆レベルシフトを施すことにより１ブロック分の復号画像に変換し、復号画像に変換された各ブロックを合成することにより全体画像に変換する。
【００１７】
ビット列分割器２０は、１６ビット長の入力ビット列を、４ビットごとに４つに分割して第１小ビット列ａ、第２小ビット列ｂ、第３小ビット列ｃ及び第４小ビット列ｄとする。なお、ここでは４つに分割したが、いくつに分割しても構わない。また、各小ビット列を同じビット長になるように分割したが、異なるビット長に分割してもよい。
【００１８】
第１比較器群２１は、４ビット長の第１小ビット列ａの上位１ビット、上位２ビット、上位３ビット及び上位４ビットのそれぞれについて各種の比較を行う上位１ビット比較器２１１、上位２ビット比較器２１２、上位３ビット比較器２１３及び上位４ビット比較器２１４を備えている。第２〜第４比較器群２２〜２４も、第１比較器群２１と同様の構成である。
【００１９】
メモリ２５は、比較用ビット列ｃ＿ｘ（ｘは１〜４ビット長のビットの並び）を格納している。各比較器２１１〜２１４は、上位１〜４ビットのビットの並びと比較用ビット列ｃ＿ｘとを比較することにより、上位１〜４ビットのそれぞれのビットの並びを認識する。例えば、第１小ビット列ａが“１１１０”のときには、上位１ビットが“１”、上位２ビットが“１１”、上位３ビットが“１１１”、上位４ビットが“１１１０”であると認識する。
【００２０】
メモリ２６は、第１小ビット列ａの有効ビット長ｖａｌｉｄ  ａ＿ｘ、第２小ビット列ｂの有効ビット長ｖａｌｉｄ  ｂ＿ｘ、第３小ビット列ｃの有効ビット長ｖａｌｉｄ  ｃ＿ｘ、第４小ビット列ｄの有効ビット長ｖａｌｉｄ  ｄ＿ｘを格納している。ここで、第１小ビット列ａの有効ビット長ｖａｌｉｄ  ａ＿ｘは、上位１〜４ビットのビットの並びがｘと一致するハフマン符号の桁数を表す１６ビットのデータ、第２小ビット列ｂの有効ビット長ｖａｌｉｄ  ｂ＿ｘは、上位５〜８ビットのビットの並びがｘと一致するハフマン符号の桁数を表す１６ビットのデータ、第３小ビット列ｃの有効ビット長ｖａｌｉｄ  ｃ＿ｘは、上位９〜１２ビットのビットの並びがｘと一致するハフマン符号の桁数を表す１６ビットのデータ、第４小ビット列ｄの有効ビット長ｖａｌｉｄ  ｄ＿ｘは、上位１３〜１６ビットのビットの並びがｘと一致するハフマン符号の桁数を表す１６ビットのデータであり、そのハフマン符号の桁数がｐ桁（ｐは１〜１６の整数）の場合、１６ビットのデータのうち右から数えてｐ番目のビットが値１に設定される。なお、第１小ビット列ａでは、ｘが１〜３ビット長のビットの並びを表す場合には、ハフマン符号の桁数はそれぞれ１〜３桁、ｘが４ビット長つまり第１小ビット列ａの最大ビット長のビットの並びを表す場合には、ハフマン符号の桁数は４桁以上となる。第２小ビット列ｂでは、ｘが１〜３ビット長のビットの並びを表す場合には、ハフマン符号の桁数はそれぞれ５〜７桁、ｘが４ビット長つまり第２小ビット列ｂの最大ビット長のビットの並びを表す場合には、ハフマン符号の桁数は８桁以上となる。第３小ビット列ｃでは、ｘが１〜３ビット長のビットの並びを表す場合には、ハフマン符号の桁数はそれぞれ９〜１１桁、ｘが４ビット長つまり第３小ビット列ｃの最大ビット長のビットの並びを表す場合には、ハフマン符号の桁数は１２桁以上となる。第４小ビット列ｄでは、ｘが１〜３ビット長のビットの並びを表す場合には、ハフマン符号の桁数はそれぞれ１３〜１５桁、ｘが４ビット長つまり第３小ビット列ｃの最大ビット長のビットの並びを表す場合には、ハフマン符号の桁数は１６桁となる。例えば、第１小ビット列ａが“１１１０”の場合、“１”（１桁）、“１１”（２桁）、“１１１”（３桁）のハフマン符号が存在せず、“１１１０”で始まる５桁及び６桁のハフマン符号が存在する場合には、下記式（１）〜（４）に示すように、有効ビット長ｖａｌｉｄ  ａ＿１，ｖａｌｉｄ  ａ＿１１，ｖａｌｉｄ  ａ＿１１１は１６ビットすべてが値０，有効ビット長ｖａｌｉｄ  ａ＿１１１０は１６ビットのデータのうち右から５，６番目のビットが値１で他のビットが値０に設定される。
valid a＿1   =0000000000000000  (1)
valid a＿11  =0000000000000000  (2)
valid a＿111 =0000000000000000  (3)
valid a＿1110=0000000000110000  (4)
【００２１】
メモリ２７は、第１小ビット列ａの確認フラグｆａ＿ｙ（ｙは４ビット長のビットの並びを表す）、第２小ビット列ｂの確認フラグｆｂ＿ｙ、第３小ビット列ｃの確認フラグｆｃ＿ｙを格納している。ここで、第１小ビット列ａの確認フラグｆａ＿ｙは、第１小ビット列ａの上位４ビットの有効ビット長ｖａｌｉｄ  ａ＿ｙが値１のビットを有しているときにその上位４ビットがハフマン符号を構成するビット列の有効な候補であることを表すために値１に設定され、それ以外のときに値０に設定される。例えば、先ほどの例のように、第１小ビット列ａが“１１１０”で、上位４ビットが“１１１０”で始まる５桁及び６桁のハフマン符号が存在する場合には、有効ビット長ｖａｌｉｄａ＿１１１０は値１のビットを有しているため、確認フラグｆａ＿１１１０は値１に設定される。なお、第２，第３小ビット列ｂ，ｃの確認フラグｆｂ＿ｙ、ｆｃ＿ｙもこれと同様である。
【００２２】
メモリ２８は、第２小ビット列ｂのマスクｍｂ＿ｚ（ｚは１〜４ビットの並びを表す）、第３ビット列ｃのマスクｍｂ＿ｃ、第４小ビット列ｄのマスクｍｂ＿ｄを格納している。ここで、第２小ビット列ｂのマスクｍｂ＿ｚは、上位から数えて５桁目から８桁目までの上位１〜４ビットの並びが第２小ビット列ｂの上位１〜４ビットの並びｚと一致するハフマン符号における、上位から数えて１桁目から４桁目までの４ビットの並びを表すものである。また、第３小ビット列ｃのマスクｍｃ＿ｚは、上位から数えて９桁目から１２桁目までの上位１〜４ビットの並びが第３小ビット列ｃの上位１〜４ビットの並びｚと一致するハフマン符号における、上位から数えて５桁目から８桁目までの４ビットの並びを表すものである。第４小ビット列ｄのマスクｍｄ＿ｚは、上位から数えて１３桁目から１６桁目までの上位１〜４ビットの並びが第４小ビット列ｄの上位１〜４ビットの並びｚと一致するハフマン符号における、上位から数えて９桁目から１２桁目までの４ビットの並びを表すものである。例えば、第１小ビット列ａは“１１０１”でも“１１１０”でも“１１１１”でもハフマン符号を構成するビット列の有効な候補になり、第２小ビット列ｂは“１０”で有効な候補になり、上位から数えて５〜６桁目が“１０”であるハフマン符号は“１１１０１０”だけだとすると、このハフマン符号の上位から数えて１〜４桁目のビットの並びは“１１１０”であるから、マスクｍｂ＿１０は“１１１０”を表すデータとなる。
【００２３】
メモリ２９は、第１小ビット列ａ、第２小ビット列ｂ及び第３小ビット列ｃのそれぞれの４ビット長のビットの並びごとに固有の数値（つまりそれぞれ異なる数値）を対応づけた第１テーブルを格納している。この第１テーブルでは、第ｉ小ビット列（ｉは２又は３を表す）のビットの並びに対応する数値は、いずれも第（ｉ−１）番目の小ビット列のビットの並びに対応する数値より大きくなるように設定されている。こうした第１テーブルの一例を図２に示す。図２では、対応する数値を１６進数で表記した。この第１テーブルでは、第２小ビット列ｂのビットの並びに対応する数値３〜８は、いずれも第１小ビット列ａのビットの並びに対応する数値０〜２より大きくなるように設定されている。また、第３小ビット列ｃのビットの並びに対応する数値９〜ｆは、いずれも第２小ビット列ｂのビットの並びに対応する数値３〜８より大きくなるように設定されている。なお、図２の第１テーブルでは、第１小ビット列ａのビットの並びに対応する数値は、ビットの並びの表す数（２進数）が小さいほど小さくなるようにした。この点は、第２小ビット列ｂ及び第３小ビット列ｃも同様である。
【００２４】
メモリ３０は、検索用ビット列と検索用サムとの取りうる組合せとハフマン符号の表すカテゴリ値（ゼロランレングスの値と付加ビット数との組合せ）とを１対１に対応づけた第２テーブルを格納している。検索用ビット列は、第１〜第４小ビット列ａ〜ｄのうち今回復号しようとしているハフマン符号の末尾のビットを含む小ビット列を末尾小ビット列とし、この末尾小ビット列内の最上位のビットから今回復号しようとしているハフマン符号の末尾のビットまでのビット列である。また、検索用サムは、ハフマン符号において末尾小ビット列よりも上位に存在する各小ビット列のビットの並びに対応する数値（図２の第１テーブル参照）の総和である。第２テーブルの一例を図３に示す。図３には、説明の便宜上、ハフマン符号も併記したが、メモリ３０にはハフマン符号は記憶されていない。また、検索用サムは１６進数で表記した。この第２テーブルでは、５桁〜８桁のハフマン符号については、第２小ビット列ｂのビットの並びが検索用ビット列になり、第１小ビット列ａのビットの並びに対応する数値がそのまま検索用サムになる。また、９桁〜１２桁のハフマン符号については、第３小ビット列ｃのビットの並びが検索用ビット列になり、第１及び第２小ビット列ａ，ｂの各ビットの並びに対応する数値の総和が検索用サムになる。更に、１３〜１６桁のハフマン符号については、第４小ビット列ｄのビットの並びが検索用ビット列になり、第１〜第３小ビット列ａ〜ｃの各ビットの並びに対応する数値の総和が検索用サムになる。
【００２５】
本実施形態では、図３に示すように、検索用ビット列が同じハフマン符号は、その検索用ビット列よりも上位のビットの並びが必ず異なるため、検索用サムは必ず異なる値となる。また、検索用サムが同じハフマン符号は、その検索用ビット列が必ず異なるビットの並びとなる。このように、検索用ビット列と検索用サムとの組合せとハフマン符号とが１対１に対応するように設定されている。また、図３では検索用サムは１６進数で表記したが、これを２進数で表記すると、いずれもハフマン符号から末尾の小ビット列を除いたビット列よりも短いビット列で表記される。例えば、１６桁のハフマン符号“１１１１１１１１１１００１１００”は末尾の小ビット列を除くと“１１１１１１１１１１００”の１２桁となるが、検索用サムは１６進数で“１６”であり２進数で“１０１１０”の５ビットとなる。したがって、第２テーブルの容量は、ハフマン符号とカテゴリ値とを対応づけたテーブルに比べて小さくなる。
【００２６】
変換器３２は、検索用ビット列と検索用サムとの組合せからゼロのランレングスの値と付加ビット数を求め、付加ビットから有効係数の値を算出し、符号化のときのジグザグスキャンと同様にしてゼロと有効係数の値をブロックの各画素の位置に戻す。
【００２７】
ここで、第１比較器群２１の各比較器２１１〜２１４は、上位１ビット、上位２ビット、上位３ビット及び上位４ビットに関する各種の処理（比較用ビット列との比較処理、有効な候補か否かの判定処理、有効な候補同士の組合せがハフマン符号となり得るかの判定処理、検索用ビット列と検索用サムとの組合せの決定処理）を順次実行するが、同種の処理については同時並行に実行する。また、第２比較器群２２の各比較器、第３比較器群２３の各比較器及び第４比較器群２４も、これと同様である。したがって、ハフマン符号のビット長にかかわらず、１６ビット長の入力ビット列から検索用ビット列と検索用サムとの組合せを決定し付加ビットを読み出すまでに要する時間を一定にすることができる。
【００２８】
次に、検索用ビット列と検索用サムとの組合せから、ゼロのランレングスの値と付加ビット数を求める具体例を説明する。ここでは、予め設定されているハフマン符号は、図３のとおりとする。また、今回の入力ビット列を“１１１０１０１０１００１００１０”とし、これを第１〜第４小ビット列ａ〜ｄに分割して各種の処理を実行することにより、検索用ビット列と検索用サムとの組合せを求める場合について、図４を参照して説明する。図４は、各小ビット列の各種処理を実行するときに用いるデータの説明図である。なお、１６ビットのデータである有効ビット長ｖａｌｉｄ  ａ＿ｘ、ｖａｌｉｄ  ｂ＿ｘ、ｖａｌｉｄ  ｃ＿ｘ、ｖａｌｉｄ  ｄ＿ｘの各ビットの値は、図３のハフマン符号に基づいて定められている（図４参照）。
【００２９】
第１〜第４比較器群２１〜２４は、ぞれぞれ第１〜第４小ビット列ａ〜ｄにつき、上位１ビット〜上位４ビットの並びｘを比較用ビット列ｃ＿ｘとの比較により同時に認識し、各並びｘに応じた有効ビット長ｖａｌｉｄ  ａ〜ｄが値１のビットを含むか否かによってハフマン符号を構成するビット列の有効な候補か否かを同時に判定する。また、確認フラグｆａ〜ｆｃの設定やマスクｍｂ〜ｍｄの設定もそれぞれ同時に行う。その結果を図４に示す。
【００３０】
まず、第１小ビット列ａの上位１ビットから順に見ていくと、上位１ビットは比較用ビット列ｃ＿１と一致し、その有効ビット長ｖａｌｉｄ  ａ＿１は１６ビットのすべてが値０のため有効な候補ではないと判定される。続いて、上位２ビットを見る。上位２ビットは比較用ビット列ｃ＿１１と一致し、その有効ビット長ｖａｌｉｄ  ａ＿１１は１６ビットのすべてが値０のため有効な候補ではないと判定される。続いて、上位３ビットを見る。上位３ビットは比較用ビット列ｃ＿１１１と一致し、その有効ビット長ｖａｌｉｄ  ａ＿１１１は１６ビットのすべてが値０のため有効な候補ではないと判定される。続いて、上位４ビットを見る。上位４ビットは比較用ビット列ｃ＿１１１０と一致し、その有効ビット長ｖａｌｉｄ  ａ＿１１１０は値１のビットが存在するため有効な候補であると判定される。なお、有効ビット長ｖａｌｉｄ  ａ＿１１１０のうち右から５つめと６つめのビットが値１であるため、予め設定されているハフマン符号には上位４ビットが“１１１０”でビット長が５桁のものと６桁のものとが存在することがわかる。
【００３１】
次に、第２小ビット列ｂの上位１ビットから順に見ていくと、上位１ビットは比較用ビット列ｃ＿１と一致し、その有効ビット長ｖａｌｉｄ  ｂ＿１は値１のビットが存在するため有効な候補であると判定される。有効ビット長ｖａｌｉｄ  ｂ＿１は右から５つめが値１であるため、予め設定されているハフマン符号には上位から５ビット目が値１でビット長が５桁のものが存在することがわかる。ここで、第２小ビット列ｂより前の第１小ビット列ａで有効なものを表すマスクｍｂ＿１は“１１０１”であり、今回有効な候補に挙がっている第１小ビット列ａの“１１１０”とは一致しない。つまり、第２小ビット列ｂの上位１ビットが“１”で第１小ビット列ａの上位４ビットが“１１１０”という組合せは、ハフマン符号となり得ない。このため、第２小ビット列ｂの上位１ビットが値１であるものは有効な候補から外される。続いて、上位２ビットを見る。上位２ビットは比較用ビット列ｃ＿１０と一致し、その有効ビット長ｖａｌｉｄ  ｂ＿１０は値１のビットが存在するため有効な候補であると判定される。有効ビット長ｖａｌｉｄ  ｂ＿１０は右から６つめが値１であるため、予め設定されているハフマン符号には上位から５，６ビット目がそれぞれ値１，０でビット長が６桁のものが存在することがわかる。ここで、第２小ビット列ｂより前の第１小ビット列ａで有効なものを表すマスクｍｂ＿１０は“１１１０”であり、今回有効な候補に挙がっている第１小ビット列ａの“１１１０”と一致する。つまり、第２小ビット列ｂの上位２ビットが“１０”で第１小ビット列ａの上位４ビットが“１１１０”という組合せは、ハフマン符号となり得る。したがって、今回のハフマン符号は、上位４ビットが“１１１０”、それに続く２ビットが“１０”であることがわかる。また、末尾小ビット列は第２小ビット列ｂであり、検索用ビット列は“１０”であり、検索用サムは図２の第１テーブルに照らして“１”となる。
【００３２】
その後、変換器３２は、図３の第２テーブルから、検索用ビット列が値１０で検索用サムが値１の組合せに対応するカテゴリ値（ゼロのランレングスの値と付加ビット数）を読み出す。いま、読み出したカテゴリ値が、ゼロのランレングスが値３で付加ビット数が値４だったとすると、今回の６桁のハフマン符号の後に続く４ビット（ここでは“１０１０”）から有効係数の値を算出する。なお、付加ビットから有効係数の値を算出するための手順は周知であるため、ここでは説明を省略する。このようにして、今回のハフマン符号に対応するゼロのランレングスの値と有効係数の値がわかる。そして、次回の入力ビット列は、今回のハフマン符号“１１１０１０”とそれに続く付加ビット“１０１０”の次からの１６ビット分のデータとなる。
【００３３】
ここで、本実施形態の構成要素と本発明の構成要素との対応関係を明らかにする。本実施形態のハフマンデコーダ１０が本発明の可変長符号の復号装置に相当し、ビット列分割器２０がビット列分割手段に相当し、第１〜第４比較器群２１〜２４の上位１〜４ビット比較器が検索用ビット列設定手段及び検索用サム設定手段に相当し、メモリ２９が数値記憶手段に相当し、メモリ３０が情報記憶手段に相当する。また、第１〜第４小ビット列ａ〜ｄにおける上位１〜４ビットが部分ビット列に相当する。なお、本実施形態では、ハフマンデコーダ１０の動作を説明することにより本発明の可変長符号の復号方法の一例も明らかにしている。
【００３４】
以上詳述した本実施形態のハフマンデコーダ１０によれば、検索用ビット列−検索用サムの組合せとカテゴリ値とを対応づけた第２テーブルの容量を従来のハフマン符号とカテゴリ値とを対応づけたテーブルに比べて小さくすることができるため、小さなサイズのテーブルでハフマン符号を復号することができる。
【００３５】
また、１６ビット長の入力ビット列を第１〜第４小ビット列ａ〜ｄに分割し、各小ビット列ａ〜ｄの上位１〜４ビットである部分ビット列についてハフマン符号の有効な候補か否かを判定し、各小ビット列ａ〜ｄで有効な候補と判定された部分ビット列同士の組合せがハフマン符号となり得るか否かを判定し、ハフマン符号となり得る組合せの末尾の部分ビット列を検索用ビット列に設定する。このため、検索用ビット列を確実に設定することができる。
【００３６】
更に、各小ビット列ａ〜ｄごとに第１〜第４比較器群２１〜２４を設けたため、ハフマン符号のビット長にかかわらず、１６ビット長の入力ビット列から検索用ビット列と検索用サムとの組合せを決定し付加ビットを読み出すまでに要する時間を一定にすることができる。
【００３７】
なお、本発明は上述した実施形態に何ら限定されることはなく、本発明の技術的範囲に属する限り種々の態様で実施し得ることはいうまでもない。
【００３８】
例えば、上述した実施形態では、第１〜第４比較器群２１〜２４を設けてハードウェアにより本発明を実現したが、第１〜第４比較器群２１〜２４の代わりにプロセッサがソフトウェアにより本発明を実現してもよい。例えば、プロセッサが、図５に示すカテゴリ値確定処理ルーチンのフローチャートにしたがって処理を実行するようにしてもよい。すなわち、まず、１６ビット長の入力ビット列を入力し（ステップＳ１１０）、第１小ビット列ａを把握すると共に比較用ビット列を用いてその上位１〜４ビットの部分ビット列を把握する（ステップＳ１２０）。そして、第１小ビット列ａの上位１〜３ビットが有効な候補か否かを順次判定し（ステップＳ１３０〜Ｓ１５０）、上位１〜３ビットのいずれかが有効な候補だった場合には、検索用ビット列−検索用サムの組合せを確定し（ステップＳ４５０）、その組合せに対応するカテゴリ値を第２テーブルから読み出し（ステップＳ４６０）、本ルーチンを終了する。一方、第１小ビット列ａの上位１〜３ビットがいずれも有効な候補でなかった場合、上位４ビットが有効な候補で且つ有効ビット長ｖａｌｉｄ  ａが４桁を表すか否かを判定し（ステップＳ１６０）、肯定判定された場合にはステップＳ４５０，Ｓ４６０の処理を行ったあと本ルーチンを終了する。
【００３９】
一方、ステップＳ１６０で否定判定された場合には、第２小ビット列ｂを把握すると共に比較用ビット列を用いてその上位１〜４ビットの部分ビット列を把握する（ステップＳ１７０）。そして、その上位１ビットが有効な候補か否かを判定し（ステップＳ１８０）、有効な候補だった場合（つまり有効ビット長が５ビットだった場合）には、上述したように確認フラグｆｂとマスクｍｂとを用いて第１小ビット列ａが有効か否かを判定し（ステップＳ１９０）、第１小ビット列ａが有効だった場合にはステップＳ４５０へ進む。一方、ステップＳ１８０又はＳ１９０で否定判定された場合には、第２小ビット列ｂの上位２ビットが有効な候補か否かを判定し（ステップＳ２００）、有効な候補だった場合（つまり有効ビット長が６ビットだった場合）には、第１小ビット列ａが有効か否かを判定し（ステップＳ２１０）、第１小ビット列ａが有効だった場合にはステップＳ４５０へ進む。一方、ステップＳ２００又はＳ２１０で否定判定された場合には、第２小ビット列ｂの上位３ビットが有効な候補か否かを判定し（ステップＳ２２０）、有効な候補だった場合（つまり有効ビット長が７ビットだった場合）には、第１小ビット列ａが有効か否かを判定し（ステップＳ２３０）、第１小ビット列ａが有効だった場合にはステップＳ４５０へ進む。一方、ステップＳ２２０又はＳ２３０で否定判定された場合には、第２小ビット列ｂの上位４ビットが有効な候補で且つ有効ビット長が８ビットか否かを判定し（ステップＳ２４０）、肯定判定された場合には、第１小ビット列ａが有効か否かを判定し（ステップＳ２５０）、第１小ビット列ａが有効だった場合にはステップＳ４５０へ進む。
【００４０】
一方、ステップＳ２４０又はＳ２５０で否定判定された場合には、第３小ビット列ｃを把握すると共に比較用ビット列を用いてその上位１〜４ビットの部分ビット列を把握する（ステップＳ２６０）。その後のステップＳ２７０〜Ｓ３４０は、ステップＳ１８０〜Ｓ２５０に準ずる処理のため、説明を省略する。ただし、ステップＳ２８０，Ｓ３００，Ｓ３２０，Ｓ３４０では、第３小ビット列ｃの前に第１，第２小ビット列ａ，ｂが存在するため、第１，第２小ビット列ａ，ｂが有効か否かを判定することになる。この判定は、確認フラグｆｂとマスクｍｃ、確認フラグｆａとマスクｍｂを用いて行う。
【００４１】
さて、ステップＳ３３０又はＳ３４０で否定判定された場合には、第４小ビット列ｄを把握すると共に比較用ビット列を用いてその上位１〜４ビットの部分ビット列を把握する（ステップＳ３５０）。その後のステップＳ３６０〜Ｓ４３０は、ステップＳ１８０〜Ｓ２５０に準ずる処理のため、説明を省略する。ただし、ステップＳ３７０，Ｓ３９０，Ｓ４１０，Ｓ４３０では、第４小ビット列ｄの前に第１〜第３小ビット列ａ〜ｃが存在するため、第１〜第３小ビット列ａ〜ｃが有効か否かを判定することになる。この判定は、確認フラグｆｃとマスクｍｄ、確認フラグｆｂとマスクｍｃ、確認フラグｆａとマスクｍｂを用いて行う。そして、ステップＳ４２０又はＳ４３０で否定判定された場合には、ハフマン符号を特定できないことになるため、エラーを出力し（ステップＳ４４０）、本ルーチンを終了する。
【００４２】
このように、プロセッサがソフトウェアにより本発明を実現する場合でも、上述した実施形態と同様の効果が得られる。ただし、第１〜第４小ビット列ａ〜ｄの処理をステップ・バイ・ステップで行うため、ハフマン符号のビット長が異なると複合化に要する時間も異なることになる。なお、例えば各小ビット列ａ〜ｄごとにプロセッサを設けておき、同時並行して各小ビット列ａ〜ｄの処理を行うようにすれば、ハフマン符号のビット長にかかわらず複合化に要する時間を同じにすることが可能である。
【００４３】
上述した実施形態では、図２の第１テーブルを採用したが、その代わりに、図６の第１テーブルを採用してもよい。図６の第１テーブルでは、第１小ビット列ａ、第２小ビット列ｂ及び第３小ビット列ｃのそれぞれの４ビット長のビットの並びごとに固有の数値（つまりそれぞれ異なる数値）が対応づけられている。この第１テーブルでは、第ｉ小ビット列（ｉは２又は３）のビットの並びに対応する数値は、いずれも第（ｉ−１）番目の小ビット列のビットの並びに対応する数値より小さくなるように設定されている。ここでは各数値を１６進数で表記した。具体的には、この第１テーブルでは、第２小ビット列ｂのビットの並びに対応する数値７〜ｃは、いずれも第１小ビット列ａのビットの並びに対応する数値ｄ〜ｆより小さくなるように設定されている。また、第３小ビット列ｃのビットの並びに対応する数値０〜６は、いずれも第２小ビット列ｂのビットの並びに対応する数値７〜ｃより小さくなるように設定されている。なお、図６の第１テーブルでは、第１小ビット列ａのビットの並びに対応する数値は、ビットの並びの表す数（２進数）が小さいほど大きくなるようにした。この点は、第２小ビット列ｂ及び第３小ビット列ｃも同様である。この第１テーブルを採用した場合でも、上述した実施形態と同様の効果が得られる。
【００４４】
上述した実施形態では、ＡＣ係数を求める場合を例に挙げて説明したが、ＤＣ係数も同様にして求めることができる。ただし、ＤＣ係数ではゼロのランレングスは不要であるため、カテゴリ値は付加ビット数を表すことになる。
【００４５】
上述した実施形態では、１６ビット長の入力ビット列を４ビットずつ４つに分割したが、特にこれに限定されるものではなく、例えば８ビットずつ２つに分割してもよいし、２ビットずつ８つに分割してもよい。また、各小ビット列のビット長は一定であってもよいし、異なっていてもよい。
【００４６】
上述した実施形態では、静止画の圧縮画像技術の一つであるＪＰＥＧに用いられるハフマン符号を例に挙げて説明したが、動画の圧縮画像技術の一つであるＭＰＥＧに用いられる可変長符号や他の技術に用いられる可変長符号に本発明を適用してもよい。
【図面の簡単な説明】
【００４７】
【図１】ハフマンデコーダの構成の概略を示す構成図。
【図２】第１テーブルの一例を示す説明図。
【図３】第２テーブルの一例を示す説明図。
【図４】各小ビット列の各種処理を実行するときに用いるデータの説明図。
【図５】カテゴリ値確定処理ルーチンのフローチャート。
【図６】第１テーブルの別例を示す説明図。
【図７】水平８画素×垂直８画素の合計６４画素からなるブロックの説明図。
【符号の説明】
【００４８】
１０  ハフマンデコーダ、２０  ビット列分割器、２１〜２４  第１〜第４比較器群、２５〜３０  メモリ、３２  変換器、４０  入力器、５０  ＣＰＵ、５２  バス、６０  逆量子化回路、２１１〜２１４  上位１〜４ビット比較器、ａ〜ｄ  第１〜第４小ビット列、ｆａ〜ｆｃ  確認フラグ、ｍｂ〜ｍｄ  マスク、ｖａｌｉｄ  ａ〜ｄ  有効ビット長。
【図１】
2010041179.tif 000003
【図２】
2010041179.tif 000004
【図３】
2010041179.tif 000005
【図４】
2010041179.tif 000006
【図５】
2010041179.tif 000007
【図６】
2010041179.tif 000008
【図７】
2010041179.tif 000009