JP3005385B2 - ハフマン復号化回路 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は、ハフマン符号化方式
により符号化されたハフマン符号を復号するためのハフ
マン復号化回路に関する。

【０００２】

【従来の技術】画像データは非常に多くの情報量を含ん
でいる。そのため、画像データをそのままの形で処理す
るのは、メモリ容量および通信速度の点で実用的ではな
い。そこで、画像データ圧縮技術が重要となる。

【０００３】画像データ圧縮の国際標準の１つとしてＪ
ＰＥＧ（Ｊｏｉｎｔ Ｐｈｏｔｏｇｒａｐｈｉｃ Ｅｘ
ｐｅｒｔ Ｇｒｏｕｐ）がある。非可逆符号化を行なう
ＤＣＴ（離散コサイン変換）方式と、二次元空間でＤＰ
ＣＭ（Ｄｉｆｆｅｒｅｎｔｉａｌ ＰＣＭ）を行なう可
逆符号化方式が採用されている。以下、ＤＣＴ方式の画
像データ圧縮を説明する。

【０００４】図３は、ＤＣＴ方式を実行するためのシス
テムの基本構成を示すブロック図である。

【０００５】符号化側では、ＤＣＴ装置１００が、入力
される原画像データにＤＣＴ変換を行ない、ＤＣＴ係数
を出力する。量子化器２００は、量子化テーブル４００
を参照してＤＣＴ係数に量子化処理を行ない、量子化さ
れたＤＣＴ係数（以下、量子化ＤＣＴ係数と呼ぶ）を出
力する。エントロピー符号化器３００は、符号化テーブ
ル５００を参照して量子化ＤＣＴ係数にエントロピー符
号化処理を行ない、圧縮データを出力する。エントロピ
ー符号化の方式としてハフマン符号化方式が用いられ
る。

【０００６】復号化側では、エントロピー復号器６００
が、符号化テーブル５００を参照して圧縮データにエン
トロピー復号化処理を行ない、量子化ＤＣＴ係数を出力
する。逆量子化器７００は、量子化テーブル４００を参
照して量子化ＤＣＴ係数に逆量子化処理を行ない、ＤＣ
Ｔ係数を出力する。逆ＤＣＴ装置８００は、ＤＣＴ係数
に逆ＤＣＴ変換を行ない、再生画像データを出力する。

【０００７】図４に示すように、各圧縮データ（符号デ
ータ）は可変長のハフマン符号および可変長の付加ビッ
トからなる。ハフマン符号の符号長および付加ビットの
符号長は各圧縮データによって異なる。

【０００８】図５は、従来のハフマン復号化回路の主要
部の構成を示すブロック図である。ハフマンテーブル１
は、２^m ワードの記憶容量を有するメモリ回路からな
る。ここで、ｍはハフマン符号の最大符号長を表す。メ
モリ回路としては、スタティックランダムアクセスメモ
リ（ＳＲＡＭ）、ダイナミックランダムアクセスメモリ
（ＤＲＡＭ）等が用いられる。

【０００９】ハフマンテーブル１のアドレス入力端子Ａ
Ｄには、圧縮データの先頭のｍビットがアドレス信号と
して与えられる。ハフマンテーブル１内の各アドレスに
は、そのアドレスが表すハフマン符号に対応する復号デ
ータが格納される。

【００１０】たとえば、ハフマン符号の最大符号長ｍを
１６とすると、１６ビット長のハフマン符号“１１１１
１１１１１１１１０１０１”に対応する復号データは、
アドレス“１１１１１１１１１１１１０１０１”に格納
される。１５ビット長のハフマン符号“１１１１１１１
１１００００１０”に対応する復号データは、２つのア
ドレス“１１１１１１１１１００００１０Ｘ”に格納さ
れる。ここで、Ｘは０および１を表す。また、２ビット
長のハフマン符号“０１”に対応する復号データは、２
¹⁴個のアドレス“０１ＸＸＸＸＸＸＸＸＸＸＸＸＸＸ”
に格納される。

【００１１】このように、ハフマンテーブル１には、最
大符号長に相当する１６ビットの圧縮データがアドレス
信号として与えられるので、最大符号長よりも短いハフ
マン符号に対応する復号データは、複数のアドレスに格
納しておく必要がある。

【００１２】たとえば、圧縮データが２ビットのハフマ
ン符号“０１”を含む場合には、ハフマンテーブル１に
は、１６ビットの圧縮データ“０１…”がアドレス信号
として与えられる。それにより、アドレス“０１…”に
格納された復号データが読み出され、データ出力端子Ｄ
Ｏから出力される。このようにして、圧縮データに含ま
れるハフマン符号が復号される。

【００１３】

【発明が解決しようとする課題】上記のように、従来の
ハフマン復号化回路では、ハフマン符号の最大符号長ｍ
に相当するビット数の圧縮データがアドレス信号として
ハフマンテーブル１に与えられるので、ハフマンテーブ
ル１を構成するメモリ回路の記憶容量は２^m ワード必要
となる。この場合、最大符号長ｍよりも短いハフマン符
号に対応する復号データは複数のアドレスに格納され
る。最大符号長が１６ビットのとき、メモリ回路の記憶
容量は２¹⁶＝６４Ｋワード必要となる。

【００１４】このように、従来のハフマン復号化回路で
は、ハフマン符号の数よりもはるかに多くの数のアドレ
スに余分な復号データを書き込む必要があり、容量の大
きいメモリ回路が必要となる。その結果、ハフマン復号
化回路の回路規模が大きくなる。

【００１５】この発明の目的は、回路規模の小さいハフ
マン復号化回路を提供することである。

【００１６】

【課題を解決するための手段】（１）第１の発明 第１の発明に係るハフマン復号化回路は、任意の符号長
を有するハフマン符号を復号するためのハフマン復号化
回路であって、符号長検出手段、記憶手段、および選択
手段を備える。

【００１７】符号長検出手段は、復号されるべきハフマ
ン符号を含む符号データを受け、復号されるべきハフマ
ン符号の符号長を検出する。記憶手段は、複数のハフマ
ン符号の符号長のいずれかがそれぞれ割り当てられた複
数のブロックを含む。複数のブロックの各々は、割り当
てられた符号長のハフマン符号に対応する復号データを
記憶し、かつ符号データの所定のビットをアドレス信号
として受ける。

【００１８】選択手段は、符号長検出手段により検出さ
れた符号長に基づいて複数のブロックのいずれかを選択
し、選択されたブロックから読み出された復号データを
出力する。

【００１９】（２） 第２の発明 第２の発明に係るハフマン復号化回路においては、記憶
手段が第１ないし第ｎのブロックを含む。複数のブロッ
クの各々は２^C ワードの記憶容量を有する。前記Ｃは、 ２^C-1 ＜Ａ≦２^C の関係を満足する整数を表す。Ａは複数のハフマン符号
の総数を表す。前記ｎは、 ｎ＝Ｂ−Ｃ＋１ の関係を満足する。Ｂは複数のハフマン符号の最大符号
長を表す。

【００２０】第１のブロックにはＣビット以下の符号長
が割り当てられ、第ｉのブロックには（Ｃ＋ｉ−１）ビ
ットの符号長が割り当てられる。ｉは２からｎまでの整
数を表す。

【００２１】第１のブロックは符号データの第１ビット
から第Ｃビットをアドレス信号として受ける。第ｉのブ
ロックは符号データの第ｉビットから第（Ｃ＋ｉ−１）
ビットをアドレス信号として受ける。

【００２２】（３） 第３の発明 第３の発明に係るハフマン復号化回路においては、複数
のブロックが第１ないし第ｎのブロックを含む。第１の
ブロックは２^C ワードの記憶容量を有する。前記Ｃは、 ２^C-1 ＜Ａ≦２^C の関係を満足する整数を表す。Ａは複数のハフマン符号
の総数を表す。前記ｎは、 ｎ＝Ｂ−Ｃ＋１ の関係を満足する。Ｂは複数のハフマン符号の最大符号
長を表す。第ｉのブロックは２^K ワードの記憶容量を有
する。前記ｉは２からｎまでの整数を表す。前記Ｋは、 ２^K-1 ＜Ａ／（ｉ−１）≦２^K の関係を満足する整数を表す。Ａ／（ｉ−１）は小数点
以下を切捨てた整数を表す。

【００２３】第１のブロックにはＣビット以下の符号長
が割り当てられる。第２ないし第ｎのブロックには同一
の符号長を有するハフマン符号の数に基づいてハフマン
符号の符号長がそれぞれ割り当てられる。

【００２４】第１のブロックは符号データの第１ビット
から第Ｃビットをアドレス信号として受ける。

【００２５】このハフマン復号化回路は、符号長検出手
段により検出された符号長に基づいて符号データのＫ個
のビットを選択して第２ないし第ｎのブロックにアドレ
ス信号として与えるビット選択手段をさらに含む。

【００２６】

【作用】（１） 第１の発明 第１の発明に係るハフマン復号化回路においては、符号
長検出手段により復号されるべきハフマン符号の符号長
が検出される。記憶手段の各ブロックでは、符号データ
の所定のビットに基づいてアドレス指定が行なわれ、対
応する復号データが読み出される。そして、検出された
符号長に基づいて、選択手段により記憶手段のブロック
のいずれかが選択され、そのブロックから読み出された
復号データが出力される。

【００２７】記憶手段の各ブロックは、割り当てられた
符号長のハフマン符号に対応する復号データを記憶すれ
ば足りるので、各ブロックの記憶容量は小さくなる。

【００２８】（２） 第２の発明 第２の発明に係るハフマン復号化回路においては、記憶
手段がｎ個のブロックを含み、各ブロックは２^C ワード
の記憶容量を有する。

【００２９】第１のブロックにはＣビット以下の符号長
が割り当てられる。Ｃビット以下の符号長を有するハフ
マン符号の数は２^C 個以下であるので、Ｃビット以下の
符号長を有するすべてのハフマン符号に対応する復号デ
ータを第１のブロックに記憶することができる。

【００３０】一方、Ｃビットを越える符号長はそれぞれ
１つのブロックに割り当てられる。各ブロックの記憶容
量２^C がハフマン符号の総数Ａ以上であるので、たとえ
すべてのハフマン符号が同じ符号長を有していても、す
べてのハフマン符号に対応する復号データを対応するブ
ロックに記憶することができる。

【００３１】また、ハフマン符号の総数Ａは２^C 以下で
あるので、同じ符号長を有するハフマン符号について
は、下位Ｃビットの値は必ず異なる。したがって、第１
のブロックに符号データの第１ビットから第Ｃビットま
でをアドレス信号として与え、第ｉのブロックに符号デ
ータの第ｉビットから第（Ｃ＋ｉ−１）までをアドレス
信号として与えることによって、各ブロック内の対応す
る復号データを特定することができる。

【００３２】（３） 第３の発明 第３の発明に係るハフマン復号化回路においては、記憶
手段がｎ個のブロックを含み、第１のブロックは２^C ワ
ードの記憶容量を有する。

【００３３】第１のブロックにはＣビット以下の符号長
が割り当てられる。Ｃビット以下の符号長を有するハフ
マン符号の数は２^C 個以下であるので、Ｃビット以下の
符号長を有するすべてのハフマン符号に対応する復号デ
ータを第１のブロックに記憶することができる。

【００３４】Ｃビットを越えるハフマン符号は、同一の
符号長ごとにグループ分けされる。第ｉのブロックは２
^K ワードの記憶容量を有する。

【００３５】第２のブロックは、２^K-1 ＜Ａ≦２^K の関
係を満足する２^K ワードの記憶容量を有する。第２のブ
ロックには、最も多くの数のハフマン符号を含むグルー
プの符号長が割り当てられる。それにより、たとえすべ
てのハフマン符号の符号長が１つの符号長に集中して
も、すべてのハフマン符号に対応する復号データを第２
のブロックに記憶することができる。

【００３６】第３のブロックは、２^K-1 ＜Ａ／２≦２^K
の関係を満足する２^K ワードの記憶容量を有する。第３
のブロックには、２番目に多くの数のハフマン符号を含
むグループの符号長が割り当てられる。それにより、す
べてのハフマン符号の符号長が２つの符号長に分散した
場合に、すべてのハフマン符号に対応する復号データを
第２および第３のブロックに記憶することができる。

【００３７】第４のブロックは、２^K-1 ＜Ａ／３≦２^K
の関係を満足する２^K ワードの記憶容量を有する。第４
のブロックには、３番目に多くの数のハフマン符号を含
むグループの符号長が割り当てられる。それにより、す
べてのハフマン符号の符号長が３つの符号長に分散した
場合に、すべてのハフマン符号に対応する復号データを
第２ないし第４のブロックに記憶することができる。

【００３８】同様にして、第ｉのブロックは、２^K-1 ＜
Ａ／（ｉ−１）≦２^K の関係を満足する２^K ワードの記
憶容量を有する。第ｉのブロックには、（ｉ−１）番目
に多くの数のハフマン符号を含むグループの符号長が割
り当てられる。それにより、すべてのハフマン符号の符
号長が（ｉ−１）個の符号長に分散した場合に、すべて
のハフマン符号に対応する復号データを第２ないし第ｉ
のブロックに記憶することができる。

【００３９】したがって、検出された符号長に基づいて
符号データのＫ個のビットを選択して第ｉのブロックに
アドレス信号として与えることによって、第ｉのブロッ
ク内の対応する復号データを特定することができる。

【００４０】

【実施例】以下、この発明の実施例を図面を参照しなが
ら詳細に説明する。図１は、この発明の第１の実施例に
よるハフマン復号化回路の構成を示すブロック図であ
る。

【００４１】このハフマン復号化回路は、符号長検出回
路１、メモリ回路２およびデータセレクタ３を含む。

【００４２】符号長検出回路１は、それぞれ８〜１６ビ
ットの９個の比較器１１，１２，…，１９およびプライ
オリティエンコーダ１０を含む。８ビットの比較器１１
の一方の入力端子には圧縮データの第１ないし第８ビッ
トＤ０〜Ｄ７が与えられ、他方の入力端子には８ビット
長のハフマン符号の最大符号値Ｍ８が与えられる。９ビ
ットの比較器１２の一方の入力端子には圧縮データの第
１ないし第９ビットＤ０〜Ｄ８が与えられ、他方の入力
端子には９ビット長のハフマン符号の最大符号値Ｍ９が
与えられる。以下同様にして、１６ビットの比較器１９
の一方の入力端子には圧縮データの第１ないし第１６ビ
ットＤ０〜Ｄ１５が与えられ、他方の入力端子には１６
ビット長のハフマン符号の最大符号値Ｍ１６が与えられ
る。

【００４３】各比較器は、一方の入力端子に与えられる
圧縮データと他方の入力端子に与えられる最大符号値と
を比較し、圧縮データの値が最大符号値よりも大きい場
合に“Ｈ”を出力し、それ以外の場合に“Ｌ”を出力す
る。プライオリティエンコーダ１０は、比較器１１〜１
９の出力信号に応答してブロック選択信号ＢＳを発生す
る。

【００４４】比較器１１〜１９の出力信号が“Ｌ”であ
れば、ブロック選択信号ＢＳは“１”を示す。比較器１
１の出力信号が“Ｈ”であり、他の比較器１２〜１９の
出力信号が“Ｌ”であれば、ブロック選択信号ＢＳは
“２”を示す。比較器１１，１２の出力信号が“Ｈ”で
あり、他の比較器１３〜１９の出力信号が“Ｌ”であれ
ば、ブロック選択信号ＢＳは“３”を示す。同様にし
て、比較器１１〜１８の出力信号が“Ｈ”であり、比較
器１９の出力信号が“Ｌ”であれば、ブロック選択信号
ＢＳは“９”を示す。

【００４５】メモリ回路２は９個のブロックＢＬ１，Ｂ
Ｌ２，…，ＢＬ９を含む。各ブロックＢＬ１〜ＢＬ９は
２５６ワードＲＡＭ（ランダムアクセスメモリ）からな
る。

【００４６】ブロックＢＬ１には圧縮データの第１ない
し第８ビットＤ０〜Ｄ７がアドレス信号として与えられ
る。ブロックＢＬ２には圧縮データの第２ないし第９ビ
ットＤ１〜Ｄ８がアドレス信号として与えられる。以下
同様にして、ブロックＢＬ９には圧縮データの第９ない
し第１６ビットＤ８〜Ｄ１５がアドレス信号として与え
られる。

【００４７】ブロックＢＬ１には１〜８ビットの符号長
を有するハフマン符号に対応する復号データが記憶され
る。ブロックＢＬ２には９ビットの符号長を有するハフ
マン符号に対応する復号データが記憶される。以下同様
にして、ブロックＢＬ９には１６ビットの符号長を有す
るハフマン符号に対応する復号データが記憶される。各
復号データは、対応するハフマン符号により示されるア
ドレスに格納される。

【００４８】データセレクタ３は、プライオリティエン
コーダ１０から発生されるブロック選択信号ＢＳに応答
して、ブロックＢＬ１〜ＢＬ９から読み出された復号デ
ータのうち１つを選択して出力する。

【００４９】ブロック選択信号ＢＳが“１”のときに
は、データセレクタ３はブロックＢＬ１から読み出され
た復号データを選択して出力する。ブロック選択信号Ｂ
Ｓが“２”のときには、データセレクタ３はブロックＢ
Ｌ２から読み出された復号データを選択して出力する。
以下同様にして、ブロック選択信号ＢＳが“９”のとき
には、データセレクタ３はブロックＢＬ９から読み出さ
れた復号データを選択して出力する。

【００５０】ＪＰＥＧのベースライン方式におけるＡＣ
ハフマン符号の総数は１６２であり、ＪＰＥＧの拡張方
式におけるＡＣハフマン符号の総数は２２６である。こ
こで、拡張方式を考えると、ＡＣハフマン符号の総数Ａ
は２２６であり、ハフマン符号の最大符号長Ｂは１６で
ある。２⁷ ＜Ａ≦２⁸ であるので、Ｃ＝８である。した
がって、この実施例では、メモリ回路２のブロックの数
ｎは、ｎ＝Ｂ−Ｃ＋１＝１６−８＋１＝９となる。ま
た、各ブロックの記憶容量は２^C ＝２⁸ ＝２５６ワード
となる。

【００５１】各ブロックの記憶容量がハフマン符号の総
数よりも大きいので、ハフマン符号の符号長がどのよう
に分布しても、すべてのハフマン符号に対応する復号デ
ータをメモリ回路２内の対応するブロックに記憶するこ
とができる。

【００５２】また、各符号長のハフマン符号の数の最大
値は２⁸ （＝２５６）以下になるので、同一符号長を有
するハフマン符号の下位８ビットの値が同一になること
はない。したがって、圧縮データに含まれるハフマン符
号の符号長およびそのハフマン符号の下位８ビットの値
より、対応する復号データを特定することができる。

【００５３】次に、図１のハフマン復号化回路の動作の
一例を説明する。ここでは、圧縮データが９ビット長の
ハフマン符号“１１１１１０１１０”を含むものとす
る。すなわち、圧縮データの第１ないし第９ビットは
“１１１１１０１１０”である。また、８ビット長のハ
フマン符号の最大符号値を“１１１１１０１０”とし、
９ビット長のハフマン符号の最大符号値を“１１１１１
１０１０”とする。また、１０ビット長のハフマン符号
の最大符号値を“１１１１１１１０１０”とする。

【００５４】この場合、圧縮データの第１ないし第８ビ
ットＤ０〜Ｄ７が８ビットのハフマン符号の最大符号値
Ｍ８よりも大きいので、８ビットの比較器１１の出力信
号は”Ｈ”となる。一方、圧縮データの第１ないし第９
ビットＤ０〜Ｄ８の値は９ビットのハフマン符号の最大
符号値Ｍ９よりも小さくなる。したがって、９ビット比
較器１２の出力信号は”Ｌ”となる。同様に、圧縮デー
タの第１ないし第１０ビットＤ０〜Ｄ９の値は１０ビッ
トのハフマン符号の最大符号値Ｍ１０よりも小さくな
る。したがって、１０ビットの比較器１３の出力信号
も”Ｌ”となる。

【００５５】その結果、圧縮データに含まれるハフマン
符号の符号長が９ビットであることが検出される。この
場合、プライオリティエンコーダ１０は、ブロック選択
信号ＢＳを“２”に設定する。

【００５６】データセレクタ３は、そのブロック選択信
号ＢＳに応答して、ブロックＢＬ２の出力データを選択
する。ブロックＢＬ２には、圧縮データの第２ないし第
９ビットＤ１〜Ｄ８、すなわち、９ビット長のハフマン
符号の下位８ビットがアドレス信号として与えられる。
それにより、ブロックＢＬ２からは、９ビット長のハフ
マン符号“１１１１１０１１０”に対応する復号データ
が読み出され、データセレクタ３を介して出力される。

【００５７】上記実施例のハフマン復号化回路では、メ
モリ回路２の記憶容量は２３０４ワードとなり、従来の
ハフマン復号化回路における６４Ｋワードの約２８分の
１となる。

【００５８】図２は、第２の実施例によるハフマン復号
化回路の構成を示すブロック図である。

【００５９】このハフマン復号化回路は、符号長検出回
路１、メモリ回路２、レジスタ４、セレクタ５およびデ
ータセレクタ６を含む。符号長検出回路１の構成および
動作は、図１に示される符号長検出回路１の構成および
動作と同様である。

【００６０】レジスタ４は、プライオリティエンコーダ
１０から発生されるブロック選択信号ＢＳをアドレス信
号として受け、データ選択信号ＤＳを出力する。データ
選択信号ＤＳは、メモリ回路２の出力データのうちハフ
マン符号の符号長に対応するデータを選択するための信
号である。

【００６１】セレクタ５は８個の入力端子Ｓ１〜Ｓ８を
有する。入力端子Ｓ１には圧縮データの第２ないし第９
ビットＤ１〜Ｄ８が与えられる。入力端子Ｓ２には圧縮
データの第３ないし第１０ビットＤ２〜Ｄ９が与えられ
る。以下同様にして、入力端子Ｓ８には圧縮データの第
９ないし第１６ビットＤ８〜Ｄ１５（８ビットデータ）
が与えられる。

【００６２】セレクタ５は、プライオリティエンコーダ
１０により発生されるブロック選択信号ＢＳに応答し
て、８個の入力端子Ｓ１〜Ｓ８に与えられるデータのい
ずれか１つを選択して出力する

【００６３】ブロック選択信号ＢＳが“１”のときに
は、セレクタ５はどのデータも出力しない。ブロック選
択信号ＢＳが“２”のときには、セレクタ５は入力端子
Ｓ１のデータを選択して出力する。ブロック選択信号Ｂ
Ｓが“３”のときには、セレクタ５は入力端子Ｓ２のデ
ータを選択して出力する。以下同様にして、ブロック選
択信号ＢＳが“９”のときには、セレクタ５は入力端子
Ｓ８のデータを選択して出力する。

【００６４】メモリ回路２は９個のブロックＢＫ１，Ｂ
Ｋ２，…，ＢＫ９を含む。ブロックＢＫ１，ＢＫ２は２
５６ワードのＲＡＭからなる。ブロックＢＫ３，ＢＫ４
は１２８ワードのＲＡＭからなる。ブロックＢＫ５，Ｂ
Ｋ６，ＢＫ７は６４ワードのＲＡＭからなる。ブロッＢ
Ｋ８，ＢＫ９は３２ワードのＲＡＭからなる。

【００６５】ブロックＢＫ１には１〜８ビットの符号長
が割り当てられる。９〜１６ビットの符号長を有するハ
フマン符号は、同一符号長ごとに８個のグループに分類
される。ブロックＢＫ２には、最も多くの数のハフマン
符号を含むグループの符号長が割り当てられる。ブロッ
クＢＫ３には、２番目に多くの数のハフマン符号を含む
グループの符号長が割り当てられる。以下、ブロックＢ
Ｋ４〜ＢＫ９には、多くの数のハフマン符号を含む順
に、順次符号長が割り当てられる。

【００６６】各ブロックには割り当てられた符号長のハ
フマン符号に対応する復号データが記憶される。各復号
データは、対応するハフマン符号により示されるアドレ
スに格納される。

【００６７】ブロックＢＫ１には、圧縮データの第１な
いし第８ビットＤ０〜Ｄ７がアドレス信号として与えら
れる。ブロックＢＫ２〜ＢＫ９にはセレクタ５の出力デ
ータ（８ビットデータ）のうち最下位ビットから該当す
るブロックのアドレスのビット数分のデータがアドレス
信号として与えられる。

【００６８】データセレクタ６は、レジスタ４から出力
されるデータ選択信号ＤＳに応答して、ブロックＢＫ１
〜ＢＫ９から読み出された復号データの１つを選択して
出力する。

【００６９】ここで、ＪＰＥＧの拡張方式を考えると、
ＡＣハフマン符号の総数Ａは２２６であり、ハフマン符
号の最大符号長Ｂは１６である。２⁷ ＜Ａ≦２⁸ である
ので、Ｃ＝８である。したがって、この実施例では、メ
モリ回路２のブロックの数ｎは、ｎ＝Ｂ−Ｃ＋１＝１６
−８＋１＝９となる。また、ブロックＢＫ１の記憶容量
は２^C ＝２⁸ ＝２５６ワードとなる。

【００７０】ブロックＢＫ２については、２⁷ ＜Ａ≦２
⁸ であるので、記憶容量は２⁸ ＝２５６ワードとなる。
ブロックＢＫ３については、２⁶ ＜Ａ／２≦２⁷ である
ので、記憶容量は２⁷ ＝１２８ワードとなる。ブロック
ＢＫ４については、２⁶ ＜Ａ／３≦２⁷ であるので、記
憶容量は２⁷ ＝１２８ワードとなる。ブロックＢＫ５に
ついては、２⁵ ＜Ａ／４≦２⁶ であるので、記憶容量は
２⁶ ＝６４ワードとなる。

【００７１】ブロックＢＫ６については、２⁵ ＜Ａ／５
≦２⁶ であるので、記憶容量は２⁶＝６４ワードとな
る。ブロックＢＫ７については、２⁵ ＜Ａ／６≦２⁶ で
あるので、記憶容量は２⁶ ＝６４ワードとなる。ブロッ
クＢＫ８については、２⁴ ＜Ａ／７≦２⁵ であるので、
記憶容量は２⁵ ＝３２ワードとなる。ブロックＢＫ９に
ついては、２⁴ ＜Ａ／８≦２⁵ であるので、記憶容量は
２⁵ ＝３２ワードとなる。

【００７２】この実施例においても、ハフマン符号の符
号長がどのように分布しても、すべてのハフマン符号に
対応する復号データをメモリ回路２内の対応するブロッ
クに記憶することができる。

【００７３】また、圧縮データに含まれるハフマン符号
の符号長およびそのハフマン符号の下位８ビットの値よ
り、対応する復号データを特定することができる。

【００７４】次に、図２のハフマン復号化回路の動作の
一例を説明する。例えば、１６ビットの符号長を有する
ハフマン符号の数が最も多く、９ビットの符号長を有す
るハフマン符号の数が２番目に多く、１０ビットの符号
長を有するハフマン符号の数が３番目に多いものとす
る。

【００７５】この場合、ブロックＢＫ２には１６ビット
の符号長が割り当てられ、ブロックＢＫ３には９ビット
の符号長が割り当てられ、ブロックＢＫ４には１０ビッ
トの符号長が割り当てられる。

【００７６】与えられた圧縮データが８ビット長以下の
ハフマン符号を含むときには、ブロック選択信号ＢＳは
“１”を示す。この場合、セレクタ５は出力データを供
給しない。また、データセレクタ６は、ブロックＢＫ１
から読み出された復号データを選択して出力する。

【００７７】与えられた圧縮データが９ビット長のハフ
マン符号を含む場合には、ブロック選択信号ＢＳは
“２”を示す。それにより、セレクタ５は、入力端子Ｓ
１に与えられるデータを選択して出力する。このとき、
データセレクタ６は、ブロックＢＫ３から読み出された
復号データを選択してして出力する。

【００７８】与えられた圧縮データが１６ビット長のハ
フマン符号を含む場合には、ブロック選択信号ＢＳは
“９”を示す。それにより、セレクタ５は、入力端子Ｓ
８に与えられるデータを選択して出力する。このとき、
データセレクタ６は、ブロックＢＫ２から読み出された
復号データを選択してして出力する。

【００７９】上記実施例のハフマン復号化回路では、メ
モリ回路２の記憶容量は１０２４ワードとなり、従来の
ハフマン復号化回路における６４Ｋビットの６４分の１
となる。

【００８０】第１の実施例と第２の実施例とを比較する
と、メモリ回路２の記憶容量については第２の実施例の
方が小さく、処理速度については第１の実施例の方が速
い。

【００８１】

【発明の効果】以上のように、この発明によれば、記憶
手段の各ブロックにはハフマン符号の符号長のいずれか
が割り当てられ、割り当てられた符号長のハフマン符号
に対応する復号データのみが記憶されるので、記憶手段
の記憶容量および回路規模が小さくなる。したがって、
回路規模が小さいハフマン復号化回路が得られる。

【図面の簡単な説明】

【図１】この発明の第１の実施例のハフマン復号化回路
の構成を示すブロック図である。

【図２】この発明の第２の実施例のハフマン復号化回路
の構成を示すブロック図である。

【図３】ＤＣＴ方式の画像データ圧縮システムの基本構
成を示すブロック図である。

【図４】圧縮データの構成を示す図である。

【図５】従来のハフマン復号化回路の主要部の構成を示
すブロック図である。

【符号の説明】

１ 符号長検出回路 ２ メモリ回路 ３，６ データセレクタ ４ レジスタ ５ セレクタ １０ プライオリティエンコーダ １１〜１９ 比較器 ＢＬ１〜ＢＬ９，ＢＫ１〜ＢＫ９ ブロック なお、各図中同一符号は同一または相当部分を示す。

Claims (3)

(57)【特許請求の範囲】
1. 【請求項１】 任意の符号長を有するハフマン符号を復
   号するためのハフマン復号化回路であって、 復号されるべきハフマン符号を含む符号データを受け、
   前記復号されるべきハフマン符号の符号長を検出する符
   号長検出手段と、 前記複数のハフマン符号の符号長のいずれかがそれぞれ
   割り当てられた複数のブロックを含む記憶手段とを備
   え、 前記複数のブロックの各々は、割り当てられた符号長の
   ハフマン符号に対応する復号データを記憶し、かつ前記
   符号データの所定のビットをアドレス信号として受け、 前記符号長検出手段により検出された符号長に基づい
   て、前記複数のブロックのいずれかを選択し、選択され
   たブロックから読み出された復号データを出力する選択
   手段をさらに備えた、ハフマン復号化回路。
2. 【請求項２】 前記記憶手段は第１ないし第ｎのブロッ
   クを含み、前記複数のブロックの各々は２^C ワードの記
   憶容量を有し、前記Ｃは、 ２^C-1 ＜Ａ≦２^C の関係を満足する整数を表し、前記Ａは前記複数のハフ
   マン符号の総数を表し、前記ｎは、 ｎ＝Ｂ−Ｃ＋１ の関係を満足し、前記Ｂは前記複数のハフマン符号の最
   大符号長を表し、 第１のブロックにはＣビット以下の符号長が割り当てら
   れ、第ｉのブロックには（Ｃ＋ｉ−１）ビットの符号長
   が割り当てられ、前記ｉは２からｎまでの整数を表し、 前記第１のブロックは前記符号データの第１ビットから
   第Ｃビットをアドレス信号として受け、前記第ｉのブロ
   ックは前記符号データの第ｉのビットから第（Ｃ＋ｉ−
   １）ビットをアドレス信号として受ける、請求項１に記
   載のハフマン復号化回路。
3. 【請求項３】 前記複数のブロックは第１ないし第ｎの
   ブロックを含み、前記第１のブロックは２^C ワードの記
   憶容量を有し、前記Ｃは、 ２^C-1 ＜Ａ≦２^C の関係を満足する整数を表し、前記Ａは前記複数のハフ
   マン符号の総数を表し、前記ｎは、 ｎ＝Ｂ−Ｃ＋１ の関係を満足し、前記Ｂは前記複数のハフマン符号の最
   大符号長を表し、第ｉのブロックは２^K ワードの記憶容
   量を有し、前記ｉは２からｎまでの整数を表し、前記Ｋ
   は、 ２^K-1 ＜Ａ／（ｉ−１）≦２^K の関係を満足する整数を表し、Ａ／（ｉ−１）は小数点
   以下を切捨てた整数を表し、 第１のブロックにはＣビット以下の符号長が割り当てら
   れ、前記第２ないし第ｎのブロックには同一の符号長を
   有するハフマン符号の数に基づいてハフマン符号の符号
   長がそれぞれ割り当てられ、 前記第１のブロックは前記符号データの第１ビットから
   第Ｃビットをアドレス信号として受け、 前記符号長検出手段により検出された符号長に基づいて
   前記符号データのＫ個のビットを選択して前第２ないし
   第ｎのブロックにアドレス信号として与えるビット選択
   手段をさらに含む、請求項１に記載のハフマン復号化回
   路。