JPH06139346A - ハフマン復号化回路およびハフマン復号化方法 - Google Patents

Abstract

(57)【要約】 【目的】 高速動作が可能でかつ回路規模が小さいハフ
マン復号化回路を提供することである。 【構成】 複数のハフマン符号を符号長に基づいて３つ
のグループに分類する。６ビット以下のハフマン符号は
ロジック回路からなるデコード回路５１によりデコード
する。７ビット以上１２ビット以下のハフマン符号は、
スタティックＲＡＭからなるメモリテーブル５２により
デコードする。１３ビット以上１６ビット以下のハフマ
ン符号は、スタティックＲＡＭからなるメモリテーブル
５３によりデコードする。メモリテーブル５２，５３の
各々から出力されるトータルビット長データＴＢＬから
付加ビット長データＡＢＬを減算することにより、ハフ
マン符号長データＨＣＬが算出される。

Description

【発明の詳細な説明】

【０００１】

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

【０００２】

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

【０００３】画像データ圧縮の国際標準の１つとしてＪ
ＰＥＧ（Joint Photographic Expert Group ）がある。
ＪＰＥＧでは、非可逆符号化を行なうＤＣＴ（離散コサ
イン変換）方式と、二次元空間でＤＰＣＭ（Differenti
alＰＣＭ）を行なう可逆符号化方式が採用されている。
以下、ＤＣＴ方式の画像データ圧縮を説明する。

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

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

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

【０００７】（２） ＤＣＴ変換 次に、ＤＣＴ変換を説明する。まず、図１１に示すよう
に、画像データを複数の８×８画素ブロックに分割す
る。図１２に示すように、１つの８×８画素ブロック内
の各画素データの値をＰ_{X Y} （Ｘ，Ｙ＝０，…，７）で
示す。ここで、Ｘ，Ｙがブロック内の画素データの位置
を表わしている。

【０００８】分割された各８×８画素ブロックに対して
次式による二次元ＤＣＴ変換を行なう。

【０００９】

【数１】

【００１０】ここで、Ｓ_{U V} はＤＣＴ係数を表わし、
Ｕ，ＶはＤＣＴ係数の位置を表わす。Ｕ＝Ｖ＝０の場合
にはＣ_U ＝Ｃ_V ＝１／√２となり、その他の場合にはＣ
_U ＝Ｃ _V ＝１となる。さらに、画素データＰ_{X Y} のビッ
ト精度が８ビットの場合にはＬ _S ＝１２８となり、画素
データＰ_{X Y} のビット精度が１２ビットの場合にはＬ_S
＝２０４８となる。

【００１１】ＤＣＴ変換の結果、６４個のＤＣＴ係数Ｓ
_{U V} が得られる。ＤＣＴ係数Ｓ_{0 0}はＤＣ係数と呼ば
れ、残りの６３個のＤＣＴ係数はＡＣ係数と呼ばれる。

【００１２】ＤＣ係数は８×８画素データの平均値（直
流成分）を示している。式（１）に示されるように、各
画素データＰ_{X Y} よりＬ_S を引くことにより、ＤＣ係数
の期待値を０にレベルシフトしている。

【００１３】図１２に示すように、ＤＣＴ変換されたブ
ロックの左上および右下がそれぞれＤＣＴ係数Ｓ_{0 0} ，
Ｓ_{7 7} に対応している。ＤＣＴ変換されたブロックの左
から右に進むにつれて高周波の水平周波数成分を多く含
み、上から下に進むにつれて高周波の垂直周波数成分を
多く含むことになる。

【００１４】一方、次式に示す逆ＤＣＴ変換によりＤＣ
Ｔ係数Ｓ_{U V} から６４個の画素データＰ_{X Y} （Ｘ，Ｙ＝
０，…，７）を得ることができる。

【００１５】

【数２】

【００１６】式（２）に示されるように、各画素データ
にＬ_S を加えることにより、レベルシフト分を元に戻し
ている。

【００１７】図１３に、８×８画素ブロックの一例およ
びその画素ブロックをＤＣＴ変換した結果を示す。図１
３からわかるように、ＤＣ係数および低周波成分のＡＣ
係数の絶対値が大きくなっている。たとえば、ＤＣ係数
Ｓ_{0 0} は２６０、ＡＣ係数Ｓ _{0 1} は４９、ＡＣ係数Ｓ
_{1 0} は−７９である。

【００１８】（３） 量子化 ＤＣＴ係数Ｓ_{U V} は係数位置ごとに異なる量子化テーブ
ルＱ_{U V} を用いて次式により線形量子化され、量子化Ｄ
ＣＴ係数ｒ_{U V} が得られる。

【００１９】 ｒ_{U V} ＝ｒｏｕｎｄ（Ｓ_{U V} ／Ｑ_{U V} ） …（３） ｒｏｕｎｄは、最も近い整数への整数化を意味する。図
１４に、量子化ＤＣＴ係数ｒ_{U V} 、ＤＣＴ係数Ｓ_{U V} お
よび量子化テーブルＱ_{U V} の関係が示される。

【００２０】復号化側では、逆量子化が行なわれる。後
述のハフマン復号化で得られた量子化ＤＣＴ係数をｒ
_{U V} とすると、次式により逆量子化を行なう。

【００２１】 Ｓ_{U V} ＝ｒ_{U V} ×Ｑ_{U V} …（４） 量子化テーブルＱ_{U V} の値を変化させることにより画質
を制御することができる。量子化テーブルＱ_{U V} の値を
小さく設定すると、量子化ＤＣＴ係数ｒ_{U V} の値が大き
くなり、画質のよい画像を符号化することができる。逆
に、量子化テーブルＱ_{U V} の値を大きく設定すると、量
子化ＤＣＴ係数ｒ_{U V} の値が小さくなり、符号化情報量
は減少するが、画質は劣化する。

【００２２】このように、量子化テーブルＱ_{U V} の値を
変えることにより、画質および符号化情報量を自由に制
御することができる。

【００２３】図１５に量子化テーブルの一例を示す。一
般に、人間の視覚はローパスフィルタの特性を持ってい
るといわれており、高周波成分には鈍感である。したが
って、高周波成分に対応するＤＣＴ係数には荒い量子化
を行なってもその影響があまり目立たない。そのため、
図１５に示すように、量子化テーブルの高周波成分には
大きな値が設定されている。

【００２４】図１６は、図１３に示されるＤＣＴ係数に
対して図１５に示される量子化テーブルを用いて量子化
を行なった結果を示す。たとえば、Ｓ_{0 0} ＝２６０，Ｑ
_{0 0}＝１６であるので、ｒ_{0 0} ＝ｒｏｕｎｄ（２６０／
１６）＝１６となる。また、Ｓ_{0 1} ＝４９，Ｑ_{0 1} ＝１
１であるので、ｒ_{0 1} ＝ｒｏｕｎｄ（４９／１１）＝４
となる。さらに、Ｓ_{1 0} ＝−７９，Ｑ_{1 0} ＝１２である
ので、ｒ_{1 0} ＝ｒｏｕｎｄ（４９／１２）＝−７とな
る。

【００２５】（４） エントロピー符号化 量子化ＤＣＴ係数ｒ_{U V} はエントロピー符号化されて圧
縮データが出力される。以下に示すように、ＤＣ係数と
ＡＣ係数とで符号化方法が異なる。

【００２６】（ａ） ＤＣ係数の符号化 図１７に、ＤＣ係数のハフマン符号化のフロー図を示
す。ＤＣ係数のハフマン符号化では、１つ前のブロック
のＤＣ係数Ｄ_{i - 1} と現在のブロックのＤＣ係数Ｄ_i と
の差分の値（ＤＣ差分値）ΔＤＣ_i を符号化する。上述
したように、ＤＣ係数は８×８画素ブロックの画素デー
タの平均値を示している。したがって、コンピュータグ
ラフィック画像のような特殊な画像を除いて、隣接する
ブロックのＤＣＴ係数が大きく変化することはあまりな
い。そのため、ＤＣ差分値は０の近傍に集中する。ＤＣ
差分値を符号化することにより高能率な符号化が期待で
きる。

【００２７】ＤＣ差分値は、図１９に示すテーブルに従
って１６のグループに分類される。すなわち、図１９の
テーブルに従って、求められたＤＣ差分値がどのグルー
プに属するかを求める。たとえば、ＤＣ差分値０のグル
ープ番号ＳＳＳＳは“０”であり、ＤＣ差分値−１，１
のグループ番号ＳＳＳＳは“１”である。また、ＤＣ差
分値−３，−２，２，３のグループ番号ＳＳＳＳは
“２”であり、ＤＣ差分値−７〜−４，４〜７のグルー
プ番号ＳＳＳＳは“３”である。

【００２８】ＤＣ差分値は、図２０に示すハフマン符号
テーブルを用いてハフマン符号に符号化される。たとえ
ば、グループ番号ＳＳＳＳが“２”であるＤＣ差分値に
はハフマン符号“０１１”が割当てられ、グループ番号
ＳＳＳＳが“３”であるＤＣ差分値にはハフマン符号
“１００”が割当てられている。

【００２９】たとえば、グループ番号“２”には８個の
ＤＣ差分値−７〜−４，４〜７が含まれるので、３ビッ
トの付加ビットにより８個のＤＣ差分値のうち１つが特
定される。付加ビットはＤＣ差分値の小さい方から順に
小さい値が割当てられる。たとえば、グループ番号
“２”の場合には、ＤＣ差分値−７に付加ビット“００
０”を割当て、ＤＣ差分値−６に付加ビット“００１”
を割当て、ＤＣ差分値７に“１１１”を割当てる。

【００３０】前のブロックのＤＣ係数が２５であり、現
在のブロックのＤＣ係数が１６であるとすれば、ＤＣ差
分値は−９となる。図１９のテーブルより、ＤＣ差分値
−９のグループ番号ＳＳＳＳは“４”である。したがっ
て、図２０のハフマン符号テーブルにより、グループ番
号“４”のハフマン符号は“１０１”となる。ＤＣ差分
値−９はグループ番号“４”に属するＤＣ差分値のうち
小さい方から７番目であるため、図２０に示すように、
付加ビットは“０１１０”となる。

【００３１】（ｂ） ＡＣ係数の符号化 図２２に、ＡＣ係数のハフマン符号化のフロー図を示
す。ＡＣ係数のハフマン符号化では、図２３に示すよう
に、ＡＣ係数が、まずジグザグスキャンによって一次元
に配列される。この一次元に配列されたＡＣ係数は、以
下に説明するように、連続する“０”の係数（無効係
数）の長さを示すラン長と“０”以外の係数（有効係
数）の値とを用いて符号化される。すなわち、無効係数
のラン長ＮＮＮＮと有効係数のグループ番号ＳＳＳＳと
を用いてハフマン符号化される。

【００３２】ＡＣ係数は、図２４に示すテーブルに従っ
てグループ分けされる。図２４に示すように、グループ
番号ＳＳＳＳは有効係数が属するグループを限定するだ
けである。１つのグループに属する有効係数のうちの１
つを特定するために、付加ビットが用いられる。ＡＣ係
数のハフマン符号化では、ラン長ＮＮＮＮとグループ番
号ＳＳＳＳとの組合せに対してハフマン符号が割当てら
れる。図２５に、ＡＣ係数のためのハフマン符号テーブ
ルを示す。そのハフマン符号テーブルを用いて、ラン長
／グループ番号がハフマン符号に符号化される。

【００３３】ブロック内の最後のＡＣ係数が０のときに
は、最後の有効係数に対応するハフマン符号の直後に
“ＥＯＢ”（Ｅｎｄ ｏｆ Ｂｌｏｃｋ）を付け、その
ブロックのハフマン符号化を終了する。ただし、ブロッ
ク内の最後のＡＣ係数が０以外のときには、“ＥＯＢ”
は付けない。また、無効係数のラン長が“１５”を越え
る場合には、１６の無効係数ごとに無効係数のラン長１
６を表わす“ＺＲＬ”を残りのラン長が１５以下になる
まで続けて付けた後、残りのラン長をＮＮＮＮとしてハ
フマン符号化する。

【００３４】たとえば、図１６に示されるＡＣ係数のハ
フマン符号化を説明する。まず、最初のＡＣ係数の有効
係数はｒ_{0 1} ＝４である。図２４のテーブルより、グル
ープ番号ＳＳＳＳは“３”となる。また、無効係数のラ
ン長ＮＮＮＮは０である。したがって、図２５のハフマ
ン符号テーブルより、ハフマン符号は“１００”とな
る。図２６に示すように、有効係数４はグループ番号
“３”に属するＡＣ係数のうち小さい方から５番目であ
るので、付加ビットは“１００”となる。よって、有効
係数ｒ_{0 1} は“１００１００”と符号化される。

【００３５】次の有効係数はｒ_{1 0} ＝−７である。グル
ープ番号ＳＳＳＳは“３”であり、無効係数のラン長Ｎ
ＮＮＮは０である。図２６に示すように、有効係数−７
はグループ番号“３”に属するＡＣ係数のうち最も小さ
いので、付加ビットは“０００”となる。よって、有効
係数ｒ_{1 0} は“１０００００”と符号化される。

【００３６】ジグザグスキャンによって、次の有効係数
はｒ_{1 1} ＝３である。図２４のテーブルよりグループ番
号ＳＳＳＳは“２”となる。この場合、ＡＣ係数ｒ_{2 0}
が０であるので、ラン長ＮＮＮＮは１となる。したがっ
て、図２５のハフマン符号テーブルよりハフマン符号は
“１１０１１”となる。図２６に示すように、有効係数
３はグループ番号“２”に属するＡＣ係数のうち最も大
きいので、付加ビットは“１１”となる。よって、ＡＣ
係数ｒ_{2 0} ，ｒ_{1 1} は“１１０１１１１”と符号化され
る。

【００３７】図２７に、上記のハフマン符号例を示す。
図２７に示すように、８×８画素ブロックの６４個の画
素データを、連続する符号化データ（圧縮データ）に符
号化することができる。

【００３８】図２８に示すように、各圧縮データは可変
長のハフマン符号および可変長の付加ビットからなる。
ハフマン符号の長さをハフマン符号長と呼び、付加ビッ
トの長さを付加ビット長と呼ぶ。また、ハフマン符号長
と付加ビット長との合計をトータルビット長と呼ぶ。ハ
フマン符号長および付加ビット長は各圧縮データによっ
て異なる。

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

【００４０】図２９において、連続する圧縮データの３
２ビットが、ラッチイネーブル機能を有する３２ビット
のレジスタ１に並列に与えられる。レジスタ１の出力デ
ータは、同様にラッチイネーブル機能を有する３２ビッ
トのレジスタ２に与えられる。レジスタ２の出力データ
およびレジスタ１の出力データは、６４ビットのバレル
シフタ３に並列に与えられる。バレルシフタ３は、与え
られたデータを最大３２ビットまでビットシフトする機
能を有する。

【００４１】バレルシフタ３に保持されるデータの先頭
の１６ビットは、メモリテーブル１２に与えられる。メ
モリテーブル１２は、与えられた１６ビットのデータに
基づいて、トータルビット長データＴＢＬ、エンドオブ
ブロック符号ＥＯＢ、ラン長データＲＬ、付加ビット長
データＡＢＬおよびハフマン符号長データＨＣＬを出力
する。

【００４２】５ビットの加算器６は、メモリテーブル１
２から与えられるトータルビット長データＴＢＬを累積
加算してバレルシフタ３のシフト量を算出する。加算器
６は、累積加算結果が３２以上になるとキャリー信号Ｃ
Ｒを出力する。５ビットのレジスタ７は、加算器６の出
力データをラッチする。デコーダ８は、レジスタ７の出
力データをデコードしてバレルシフタ３のシフト量を制
御する。

【００４３】一方、レジスタ９は、メモリテーブル１２
から出力されるエンドオブブロック符号ＥＯＢ、ラン長
データＲＬ、付加ビット長データＡＢＬおよびハフマン
符号長データＨＣＬならびにバレルシフタ３に保持され
る先頭の３２ビットのデータをラッチする。付加ビット
抽出回路１０は、レジスタ９から出力される付加ビット
長データＡＢＬおよびハフマン符号長データＨＣＬに基
づいて３２ビットのデータから付加ビットＡＢを抽出す
る。

【００４４】コントロール回路１３は、加算器６からの
キャリー信号ＣＲを受け、レジスタ１，２にラッチイネ
ーブル信号ＬＥ１を与え、レジスタ７，９にラッチイネ
ーブル信号ＬＥ２を与える。また、コントロール回路１
３は、メモリテーブル１２の読出動作を制御する制御信
号ＣＮＴを発生する。

【００４５】レジスタ１，２，７，９およびコントロー
ル回路１３にはクロック信号ＣＫが与えられ、レジスタ
７およびコントロール回路１３にはリセット信号ＲＳＴ
が与えられる。

【００４６】次に、図２９のハフマン復号化回路の動作
を説明する。まず、リセット信号ＲＳＴによりコントロ
ール回路１３がリセットされ、かつレジスタ７の内容が
０にクリアされる。それにより、デコーダ８から出力さ
れるバレルシフタ３のシフト量が０に設定される。

【００４７】まず、ＤＣハフマン符号（ＤＣ係数に対応
するハフマン符号）がデコードされる。コントロール回
路１３からのイネーブル信号ＬＥ１によりレジスタ２に
圧縮データの最初の３２ビットがラッチされ、レジスタ
１に圧縮データの次の３２ビットがラッチされる。それ
により、バレルシフタ３にレジスタ２から出力される最
初の３２ビットの圧縮データおよびレジスタ１から出力
される次の３２ビットの圧縮データが与えられる。

【００４８】バレルシフタ３２内の圧縮データの先頭の
１６ビットが、アドレス信号としてメモリテーブル１２
に与えられる。コントロール回路１３からの制御信号Ｃ
ＮＴに応答してメモリテーブル１２の読出動作が行なわ
れる。それにより、先頭の１６ビットのデータに含まれ
るＤＣハフマン符号に対応するハフマン符号長データＨ
ＣＬ、付加ビット長データＡＢＬおよびトータルビット
長データＴＢＬが出力される。トータルビット長データ
ＴＢＬは、加算器６に与えられ、累積加算される。

【００４９】次に、コントロール回路１３は、レジスタ
７，９にラッチイネーブル信号ＬＥ２を与える。レジス
タ７は、ラッチイネーブル信号ＬＥ２に応答して加算器
６の累積加算結果をラッチしてデコーダ８に与える。デ
コーダ８は、レジスタ７からの累積加算結果をデコード
してバレルシフタ３にシフト量を示すシフト信号を与え
る。バレルシフタ３は、圧縮データを累積加算結果分ビ
ットシフトする。

【００５０】レジスタ９は、ラッチイネーブル信号ＬＥ
２に応答して、メモリテーブル１２から読出されたハフ
マン符号長データＨＣＬおよび付加ビット長データＡＢ
Ｌならびにバレルシフタ３から出力される３２ビットの
データをラッチして出力する。付加ビット抽出回路１０
は、ハフマン符号長データＨＣＬおよび付加ビット長デ
ータＡＢＬに基づいて、３２ビットのデータから付加ビ
ットＡＢを抽出する。このようにして、ＤＣハフマン符
号のデコードが終了する。

【００５１】同様にして、ＡＣハフマン符号（ＡＣ係数
に対応するハフマン符号）がデコードされる。ＡＣハフ
マン符号のデコード時には、メモリテーブル１２から、
ハフマン符号長データＨＣＬ、付加ビット長データＡＢ
Ｌ、ラン長データＲＬおよびトータルビット長データＴ
ＢＬが出力される。

【００５２】その間、加算器６の累積加算結果が３２以
上になると、加算器６からキャリー信号ＣＲが出力され
る。コントロール回路１３は、キャリー信号ＣＲに応答
して、レジスタ１にラッチイネーブル信号ＬＥ１を与え
る。それにより、バレルシフタ３の後半の３２ビットに
新たな３２ビットの圧縮データが与えられる。

【００５３】このようにして、メモリテーブル１２から
エンドオブブロック符号ＥＯＢが読出されるまで、ＡＣ
ハフマン符号のデコードが続けられる。

【００５４】上記のようにして得られた付加ビットＡＢ
およびラン長データＲＬに基づいて量子化ＤＣＴ係数を
得ることができる。

【００５５】

【発明が解決しようとする課題】従来のハフマン復号化
回路において、ハフマン符号化の速度は、バレルシフタ
３、加算器６、デコーダ８およびメモリテーブル１２を
構成するハードウェアの動作速度により決定される。こ
れらのうち、メモリテーブル１２のアクセス時間が、ハ
フマン符号化処理の高速化の妨げとなっている。

【００５６】また、メモリテーブル１２には、ハフマン
符号の最大符号長に等しい１６ビットの圧縮データがア
ドレス信号として与えられる。そのため、メモリテーブ
ル１２のアドレス空間は２^{1 6} ワードとなる。このよう
に、メモリテーブル１２の容量が非常に大きくなる。

【００５７】そこで、最大符号長の前半のビットおよび
後半のビットでメモリテーブルを分割することにより必
要なメモリ容量を減らすことが行なわれている。しか
し、それでも、ハフマン符号の数の約５〜６倍のメモリ
容量が必要となる。このように、依然としてハフマン復
号化回路の回路規模は大きい。

【００５８】この発明の目的は、小さい回路規模で高速
にハフマン復号化処理を行なうことができるハフマン復
号化回路およびハフマン復号化方法を提供することであ
る。

【００５９】

【課題を解決するための手段】この発明にかかるハフマ
ン復号化回路は、複数のデコード手段および選択手段を
備える。複数のハフマン符号は符号長に基づいて複数の
グループに分類される。複数のデコード手段は、複数の
グループに対応して設けられかつ各々が対応するグルー
プ内のハフマン符号をデコードする。選択手段は、与え
られたハフマン符号の先頭ビットから連続する同一値の
ビット数に基づいて複数のデコード手段の１つを選択し
て活性化する。

【００６０】複数のデコード手段は、メモリ素子からな
る第１のデコード手段およびロジック回路からなる第２
のデコード手段を含んでもよい。第１のデコード手段は
長い符号長のハフマン符号を含むグループに割当てら
れ、第２のデコード手段は短い符号長のハフマン符号を
含むグループに割当てられる。

【００６１】複数のデコード手段の各々は、付加ビット
長およびトータルビット長を出力する。付加ビット長お
よびトータルビット長からハフマン符号長を算出する演
算手段をさらに含んでもよい。

【００６２】この発明に係るハフマン復号化方法は次の
ステップを含む。複数のハフマン符号を符号長に基づい
て複数のグループに分類する。与えられたハフマン符号
をデコードする複数のデコード手段を複数のグループに
それぞれ割当てる。与えられたハフマン符号の先頭ビッ
トから連続する同一値のビット数に基づいて複数のデコ
ード手段の１つを選択して活性化する。

【００６３】複数のデコード手段は、メモリ素子からな
る第１のデコード手段およびロジック回路からなる第２
のデコード手段を含んでもよい。第１のデコード手段を
長い符号長のハフマン符号を含むグループに割当て、第
２のデコード手段を短い符号長のハフマン符号を含むグ
ループに割当てる。

【００６４】

【作用】この発明に係るハフマン復号化回路およびハフ
マン復号化方法においては、複数のハフマン符号が符号
長に基づいて複数のグループに分類され、複数のグルー
プに複数のデコード手段がそれぞれ割当てられる。それ
により、デコード手段の全体の容量および回路規模が小
さくなる。

【００６５】ハフマン符号の性質に着目すると、長い符
号長のハフマン符号では先頭ビットからあるビットまで
同一値が連続し、短い符号長のハフマン符号では先頭ビ
ットからあるビットまでに異なる値が混在する。

【００６６】この性質を利用すると、先頭ビットから連
続する同一値のビット数に基づいて、与えられたハフマ
ン符号がどのグループに属するかを判別することがで
き、そのグループに割当てられたデコード手段を選択す
ることができる。

【００６７】ハフマン符号化方式においては、出現頻度
の高いデータには短い符号長のハフマン符号が割当てら
れ、出現頻度の低いデータには長い符号長のハフマン符
号が割当てられる。

【００６８】一方、ロジック回路により構成されるデコ
ード手段は、動作速度は速いが回路規模が比較的大きく
なる。それに対して、メモリ素子により構成されるデコ
ード手段は、動作速度は速くないが、回路規模は比較的
小さくなる。

【００６９】したがって、出現頻度の高い短い符号長の
ハフマン符号を高速動作が可能なロジック回路によりデ
コードし、出現頻度の低い長い符号長のハフマン符号を
回路規模が小さいメモリ素子によりデコードすると、全
体として、高速動作が可能でかつ回路規模が小さい復号
化回路が得られる。

【００７０】また、付加ビット長およびトータルビット
長からハフマン符号長を算出する演算手段をさらに設け
れば、各デコード手段が付加ビット長、トータルビット
長およびハフマン符号長を出力する場合に比べて、各デ
コード手段の回路規模が小さくなる。

【００７１】

【実施例】以下、この発明の一実施例によるハフマン復
号化回路およびハフマン復号化装置を図面を参照しなが
ら詳細に説明する。

【００７２】この実施例のハフマン復号化回路およびハ
フマン復号化方法では、図１に示すようにハフマン符号
がハフマン符号長に基づいて３つのグループＧ１，Ｇ
２，Ｇ３に分類される。

【００７３】ハフマン符号長が６ビット以下のハフマン
符号はグループＧ１に割当てられ、ハフマン符号長が７
ビット以上１２ビット以下のハフマン符号はグループＧ
２に割当てられ、ハフマン符号長が１３ビット以上１６
ビット以下のハフマン符号はグループＧ３に割当てられ
る。

【００７４】ハフマン符号は次のような規則性を有す
る。６ビット以下のハフマン符号では、先頭ビットから
第４ビットまでに少なくとも１つの“０”が存在する。
また、７ビット以上１２ビット以下のハフマン符号で
は、先頭ビットから第４ビットまでがすべて“１”であ
りかつ第５ビットから最終ビットまでに少なくとも１つ
の“０”が存在する。さらに、１３ビット以上１６ビッ
ト以下のハフマン符号では、先頭ビットから第９ビット
までがすべて“１”となっている。

【００７５】この規則性を利用することによって、与え
られたハフマン符号がグループＧ１，Ｇ２，Ｇ３のいず
れに属するかを判別することができる。

【００７６】グループＧ１に属するハフマン符号は高速
のロジック回路からなるデコード回路によりデコードさ
れ、グループＧ２，Ｇ３に属するハフマン符号はＲＡＭ
（ランダムアクセスメモリ）からなるメモリテーブルに
よりデコードされる。

【００７７】図２に示すように、デコード回路には、グ
ループＧ１のハフマン符号を含む圧縮データの先頭ビッ
トから第６ビットまでが入力される。

【００７８】グループＧ２のハフマン符号については先
頭ビットから第４ビットまでがすべて“１”であるの
で、第５ビットから第１２ビットまでを用いて１つのハ
フマン符号を特定することができる。そのため、メモリ
テーブルには、グループＧ２のハフマン符号を含む圧縮
データの第５ビットから第１２ビットまでがアドレス信
号として与えられる。

【００７９】グループＧ３のハフマン符号については先
頭ビットから第９ビットまでがすべて“１”であるの
で、第１０ビットから第１６ビットまでを用いて１つの
ハフマン符号を特定することができる。そのため、メモ
リテーブルには、グループＧ３のハフマン符号を含む圧
縮データの第１０ビットから第１６ビットまでがアドレ
ス信号として与えられる。

【００８０】上記のようにグループ分けすることによっ
て、デコード回路の回路規模が小さくなり、かつ各メモ
リテーブルに必要なメモリ容量が小さくなる。

【００８１】また、出現頻度の高い６ビット以下のハフ
マン符号を高速のロジック回路によりデコードすること
によって、ハフマン復号化回路の全体の処理速度が高速
化する。なお、シミュレーションによれば、６ビット以
下のハフマン符号の出現頻度は約８５％である。

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

【００８３】図３のハフマン復号化回路が図２９のハフ
マン復号化回路と異なるのは、メモリテーブル１２の代
わりにデコーダ４およびデコーダブロック５が設けら
れ、コントロール回路１３の代わりにコントロール回路
１１が設けられている点である。

【００８４】図３において、圧縮データの３２ビット
は、ラッチイネーブル機能を有する３２ビットのレジス
タ１に並列に与えられる。レジスタ１の出力データは、
同様にラッチイネーブル機能を有する３２ビットのレジ
スタ２に与えられる。レジスタ２の出力データおよびレ
ジスタ１の出力データは、６４ビットのバレルシフタ３
に並列に与えられる。バレルシフタ３は、与えられたデ
ータを最大３２ビットまでビットシフトする機能を有す
る。

【００８５】バレルシフタ３に保持されるデータの先頭
の１６ビットは、デコーダ４およびデコーダブロック５
に与えられる。デコーダ４は、バレルシフタ３から与え
られる１６ビットのデータに基づいて、与えられたデー
タが６ビット以下のハフマン符号（グループＧ１）を含
むか、７ビット以上１２ビット以下のハフマン符号（グ
ループＧ２）を含むかあるいは１３ビット以上１６ビッ
ト以下のハフマン符号（グループＧ３）を含むかを検出
し、デコーダ選択信号ＤＳ１，ＤＳ２，ＤＳ３を発生す
る。

【００８６】ただし、デコーダ４は、コントロール回路
１１から与えられるＤＣ符号選択信号ＤＣＳＬがアクテ
ィブ状態のときには、デコーダ選択信号ＤＳ１，ＤＳ
２，ＤＳ３を出力しない。

【００８７】デコーダブロック５は、デコーダ選択信号
ＤＣ１，ＤＣ２，ＤＣ３に応答して、バレルシフタ３か
ら与えられる１６ビットのデータをデコードし、トータ
ルビット長データＴＢＬ、エンドオブブロック符号ＥＯ
Ｂ、ラン長データＲＬ、付加ビット長データＡＢＬおよ
びハフマン符号長データＨＣＬを発生する。

【００８８】５ビットの加算器６は、デコーダブロック
５から与えられるトータルビット長データＴＢＬを累積
加算してバレルシフタ３のシフト量を算出する。加算器
６は、累積加算結果が３２以上になると、キャリー信号
ＣＲを出力する。５ビットのレジスタ７は、加算器６の
出力データをラッチする。デコーダ８は、レジスタ７の
出力データをデコードしてバレルシフタ３のシフト量を
制御する。

【００８９】一方、レジスタ９は、デコーダブロック５
から出力されるエンドオブブロック符号ＥＯＢ、ラン長
データＲＬ、付加ビット長データＡＢＬおよびハフマン
符号長データＨＣＬならびにバレルシフタ３から出力さ
れる先頭の３２ビットのデータをラッチする。付加ビッ
ト抽出回路１０は、レジスタ９から出力される付加ビッ
ト長データＡＢＬおよびハフマン符号長データＨＣＬに
基づいて、バレルシフタ３から出力される３２ビットの
データから付加ビットＡＢを抽出する。

【００９０】コントロール回路１１は、デコーダ４によ
り発生されるデコーダ選択信号ＤＣ１および加算器６か
ら出力されるキャリー信号ＣＲを受け、レジスタ１，２
にラッチイネーブル信号ＬＥ１を与え、レジスタ７，９
にラッチイネーブル信号ＬＥ２を与える。

【００９１】レジスタ１，２，７，９およびコントロー
ル回路１１にはクロック信号ＣＫが与えられ、レジスタ
７およびコントロール回路１１にはリセット信号ＲＳＴ
が与えられる。

【００９２】図４は、デコーダブロック５の詳細な構成
を示すブロック図である。デコーダブロック５は、デコ
ード回路５１、メモリテーブル５２、メモリテーブル５
３、デコード回路５４、減算器５５、３ステートバッフ
ァ５６およびゲート回路５７を含む。

【００９３】デコード回路５１，５４は高速動作が可能
なロジック回路により構成され、メモリテーブル５２，
５３はＲＡＭにより構成される。

【００９４】デコード回路５１には、１６ビットの圧縮
データの先頭ビットから第６ビットまでが与えられる。
メモリテーブル５２には、１６ビット圧縮データの第５
ビットから第１２ビットまでが与えられる。メモリテー
ブル５３には、１６ビットの圧縮データの第１０ビット
から第１６ビットまでが与えられる。デコード回路５４
には、１６ビットの圧縮データの先頭ビットから第９ビ
ットまでが与えられる。

【００９５】デコード回路５１は、デコーダ選択信号Ｄ
Ｓ１に応答して活性化され、６ビット以下のＡＣハフマ
ン符号をデコードして、ハフマン符号長データＨＣＬ、
ラン長データＲＬ、付加ビット長データＡＢＬ、トータ
ルビット長データＴＢＬおよびエンドオブブロック符号
ＥＯＢを出力する。メモリテーブル５２は、デコーダ選
択信号ＤＣ２に応答して活性化され、７ビット以上１２
ビット以下のＡＣハフマン符号をデコードして、ラン長
データＲＬ、付加ビット長データＡＢＬおよびトータル
ビット長データＴＢＬを出力する。メモリテーブル５３
は、デコーダ選択信号ＤＳ３に応答して活性化され、１
３ビット以上１６ビット以下のＡＣハフマン符号をデコ
ードして、ラン長データＲＬ、付加ビット長データＡＢ
Ｌおよびトータルビット長データＴＢＬを出力する。

【００９６】デコード回路５４は、ＤＣ符号選択信号Ｄ
ＣＳＬに応答して活性化され、ＤＣハフマン符号をデコ
ードして、ハフマン符号長データＨＣＬ、付加ビット長
データＡＢＬおよびトータルビット長データＴＢＬを出
力する。

【００９７】減算器５５は、メモリテーブル５２，５３
から出力されるトータルビット長データＴＢＬから付加
ビット長データＡＢＬを減算し、ハフマン符号長データ
ＨＣＬを出力する。減算器５５から出力されるハフマン
符号長データＨＣＬは３ステートバッファ５６に与えら
れる。一方、ゲート回路５７の一方の入力端子にはデコ
ーダ選択信号ＤＣ２が与えられ、他方の入力端子にはデ
コーダ選択信号ＤＳ３が与えられる。３ステートバッフ
ァ５６はゲート回路５７の出力信号により制御される。

【００９８】デコーダ選択信号ＤＣ２，ＤＣ３のいずれ
かがアクティブ状態になると、３ステートバッファ５６
は同通状態となり、デコーダ選択信号ＤＣ２，ＤＣ３の
両方が非アクティブ状態になると、３ステートバッファ
５６は高インピーダンス状態になる。

【００９９】次に、図３および図４に示されるハフマン
復号化回路の動作を説明する。まず、リセット信号ＲＳ
Ｔによりコントロール回路１１がリセットされ、かつレ
ジスタ７の内容が０にクリアされる。それにより、デコ
ーダ８から出力されるバレルシフタ３のシフト量が０に
設定される。

【０１００】まず、ＤＣハフマン符号がデコードされ
る。コントロール回路１１は、ＤＣ符号選択信号ＣＤＳ
Ｌをアクティブ状態にする。このとき、デコーダ４から
発生されるデコーダ選択信号ＤＣ１，ＤＣ２，ＤＣ３は
すべて非アクティブ状態となっている。それにより、デ
コーダブロック５内のデコード回路５４が活性状態にな
り、デコード回路５１およびメモリテーブル５２，５３
が非活性状態になる。

【０１０１】次に、コントロール回路１１からのラッチ
イネーブル信号ＬＥ１によりレジスタ２に圧縮データの
最初の３２ビットがラッチされ、レジスタ１に圧縮デー
タの次の３２ビットがラッチされる。それにより、バレ
ルシフタ３に、レジスタ２から出力される最初の３２ビ
ットの圧縮データおよびレジスタ１から出力される次の
３２ビットの圧縮データが与えられる。

【０１０２】バレルシフタ３２内の圧縮データの先頭の
１６ビットはデコーダ４およびデコーダブロック５に与
えられる。デコーダブロック５内のデコード回路５１に
より１６ビットの圧縮データに含まれるＤＣハフマン符
号がデコードされ、ハフマン符号長データＨＣＬ、付加
ビット長データＡＢＬおよびトータルビット長データＴ
ＢＬが出力される。トータルビット長データＴＢＬは加
算器６に与えられ、累積加算される。

【０１０３】コントロール回路１１は、デコーダ４から
出力されるデコード終了信号（図示せず）に応答してラ
ッチイネーブル信号ＬＥ１，ＬＥ２のタイミングを制御
する。コントロール回路１１は、デコーダ４からデコー
ド終了信号を受けると、直ちにレジスタ７，９にラッチ
イネーブル信号ＬＥ２を与える。

【０１０４】レジスタ７は、ラッチイネーブル信号ＬＥ
２に応答して、加算器６の累積加算結果をラッチしてデ
コーダ８に与える。デコーダ８は、レジスタ７からの累
積加算結果をデコードして、バレルシフタ３にシフト量
を示すシフト信号を与える。バレルシフタ３は、圧縮デ
ータを累積加算結果分ビットシフトする。

【０１０５】レジスタ９は、ラッチイネーブル信号ＬＥ
２に応答して、デコーダブロック５から出力されるハフ
マン符号長データＨＣＬおよび付加ビット長データＡＢ
Ｌならびにバレルシフタ３から出力される３２ビットの
圧縮データをラッチして出力する。付加ビット抽出回路
１０は、レジスタ９から与えられるハフマン符号長デー
タＨＣＬおよび付加ビット長データＡＢＬに基づいて、
３２ビットの圧縮データから付加ビットＡＢを抽出して
出力する。

【０１０６】ＤＣハフマン符号のデコードが終了する
と、コントロール回路１１は、ＤＣ符号選択信号ＤＣＳ
Ｌを非アクティブ状態にする。それにより、デコーダ４
は、バレルシフタ３から与えられる１６ビットの圧縮デ
ータに基づいて、デコーダ選択信号ＤＳ１，ＤＳ２，Ｄ
Ｓ３の１つをアクティブ状態にする。

【０１０７】デコーダ選択信号ＤＳ１がアクティブ状態
になると、デコーダブロック５内のデコード回路５１に
より圧縮データに含まれるＡＣハフマン符号がデコード
され、ハフマン符号長データＨＣＬ、ラン長データＲ
Ｌ、付加ビット長データＡＢＬおよびトータルビット長
データＴＢＬが出力される。

【０１０８】デコーダ選択信号ＤＳ２がアクティブ状態
になると、デコーダブロック５内のメモリテーブル５２
から、圧縮データに含まれるＡＣハフマン符号に対応す
るラン長データＲＬ、付加ビット長データＡＢＬおよび
トータルビット長データＴＢＬが読出される。

【０１０９】デコーダ選択信号ＤＣ３がアクティブ状態
になると、デコーダブロック５内のメモリテーブル５３
から、圧縮データに含まれるＡＣハフマン符号に対応す
るラン長データＲＬ、付加ビット長データＡＢＬおよび
トータルビット長データＴＢＬが読出される。

【０１１０】デコーダ選択信号ＤＳ２，ＤＳ３がアクテ
ィブ状態のときには、コントロール回路１１から減算器
５５に与えられるイネーブル信号ＳＥがアクティブ状態
になり、減算器５５が活性化される。減算器５５は、ト
ータルビット長データＴＢＬから付加ビット長データＡ
ＢＬを減算し、ハフマン符号長データＨＣＬを３ステー
トバッファ５６に与える。このとき、ゲート回路５７の
出力信号はアクティブ状態となっているので、３ステー
トバッファ５６は同通状態となる。したがって、ハフマ
ン符号長データＨＣＬが３ステートバッファ５６から出
力される。減算器５５の演算は加算器６の演算と並列に
行なわれるので、減算器５５の演算により処理時間が増
大することはない。このように減算器５５を用いてハフ
マン符号長データＨＣＬを算出することによりメモリテ
ーブル５２，５３のメモリ容量を削減することが可能と
なる。

【０１１１】コントロール回路１１は、デコーダ４から
デコード終了信号を受けると、レジスタ７，９にラッチ
イネーブル信号ＬＥ２を与える。レジスタ７は、ラッチ
イネーブル信号ＬＥ２に応答して、加算器６の累積加算
結果をラッチしてデコーダ８に与える。デコーダ８は、
レジスタ７から与えられる累積加算結果をデコードし
て、バレルシフタ３にシフト量を示すシフト信号を与え
る。バレルシフタ３は、圧縮データを累積加算結果分ビ
ットシフトする。

【０１１２】レジスタ９は、ラッチイネーブル信号ＬＥ
２に応答して、デコーダブロック５から出力されるハフ
マン符号長データＨＣＬ、付加ビット長データＡＢＬお
よびラン長データＲＬならびにバレルシフタ３から出力
される３２ビットの圧縮データをラッチして出力する。
付加ビット抽出回路１０は、レジスタ９から出力される
ハフマン符号長データＨＣＬおよび付加ビット長データ
ＡＢＬに基づいて、３２ビットの圧縮データから付加ビ
ット長ＡＢを抽出して出力する。

【０１１３】その間、加算器６の累積加算結果が３２以
上になると、加算器６からキャリー信号ＣＲが出力され
る。コントロール回路１１は、キャリー信号ＣＲに応答
して、レジスタ１にラッチイネーブル信号ＬＥ１を与え
る。これにより、バレルシフタ３の後半の３２ビットに
新たな３２ビットの圧縮データが与えられる。

【０１１４】このようにして、デコーダブロック５内の
デコード回路５１からエンドオブブロック符号ＥＯＢが
出力されるまで、ＡＣハフマン符号のデコードが続けら
れる。

【０１１５】図５は、デコーダ４の構成を示す回路図で
ある。デコーダ４は、４入力ＡＮＤゲート４１、６入力
ＮＡＮＤゲート４２および２入力ＮＡＮＤゲート４３を
含む。

【０１１６】ＡＮＤゲート４１の４つの入力端子には、
１６ビットの圧縮データの先頭ビットから第４ビットま
でが与えられる。ＡＮＤゲート４１の出力端子からデコ
ーダ選択信号ＤＳ１が出力される。ＮＡＮＤゲート４２
の１つの入力端子にはＡＮＤゲート４１の出力信号が与
えられ、残りの５つの入力端子には１６ビットの圧縮デ
ータの第５ビットから第９ビットまでが与えられる。Ｎ
ＡＮＤゲート４２の出力端子からデコーダ選択信号ＤＳ
３が出力される。ＮＡＮＤゲート４３の一方の入力端子
にはＮＡＮＤゲート４２の出力信号が与えられ、他方の
入力端子にはＡＮＤゲート４１の出力信号が与えられ
る。ＮＡＮＤゲート４３の出力端子からデコーダ選択信
号ＤＳ２が出力される。

【０１１７】１６ビットの圧縮データの先頭ビットから
第４ビットまでの少なくとも１つが“０”であれば、Ａ
ＮＤゲート４１から出力されるデコーダ選択信号ＤＳ１
がローレベル（アクティブ状態）となる。このとき、Ｎ
ＡＮＤゲート４２から出力されるデコーダ選択信号ＤＳ
３およびＮＡＮＤゲート４３から出力されるデコーダ選
択信号ＤＳ２はハイレベル（非アクティブ状態）とな
る。

【０１１８】１６ビットの圧縮データの先頭ビットから
第４ビットまでがすべて“１”であれば、ＡＮＤゲート
４１から出力されるデコーダ選択信号ＤＳ１はハイレベ
ルとなる。このとき、１６ビットの圧縮データの第５ビ
ットから第９ビットまでの少なくとも１つが“０”であ
れば、ＮＡＮＤゲート４２から出力されるデコーダ選択
信号ＤＳ３がハイレベルとなり、ＮＡＮＤゲート４３か
ら出力されるデコーダ選択信号ＤＳ２がローレベル（ア
クティブ状態）となる。

【０１１９】１６ビットの圧縮データの先頭ビットから
第９ビットまでがすべて“１”であれば、ＡＮＤゲート
４１から出力されるデコーダ選択信号ＤＳ１がハイレベ
ルとなり、ＮＡＮＤゲート４２から出力されるデコーダ
選択信号ＤＳ３がローレベル（アクティブ状態）とな
る。このとき、ＮＡＮＤゲート４３から出力されるデコ
ーダ選択信号ＤＳ２をハイレベルとなる。

【０１２０】図６は、デコーダ回路５１の構成を示すブ
ロック図である。デコーダ回路５１は、組合せ回路５１
１、および６ビット以下のハフマン符号の数と同じ数の
１９ビットのレジスタ５１２を含む。

【０１２１】組合せ回路５１１には、１６ビットの圧縮
データの先頭ビットから第６ビットまでが与えられる。
各レジスタ５１２には、ＡＣハフマン符号に対応するハ
フマン符号長データＨＣＬ、ラン長データＲＬ、付加ビ
ット長データＡＢＬおよびトータルビット長データＴＢ
Ｌが予め記憶される。また、エンドオブブロック符号Ｅ
ＯＢが、該当するレジスタ５１２に予め記憶される。

【０１２２】組合せ回路５１１に与えられるデータに従
って、複数のレジスタ５１２の１つが選択され、選択さ
れたレジスタ５１２からハフマン符号長データＨＣＬ、
ラン長データＲＬ、付加ビット長データＡＢＬおよびト
ータルビット長データＴＢＬが出力される。選択された
レジスタ５１２にエンドオブブロック符号ＥＯＢが記憶
されている場合には、エンドオブブロック符号ＥＯＢも
出力される。

【０１２３】図７は、メモリテーブル５２の構成を示す
ブロック図である。メモリテーブル５２はスタティック
ＲＡＭ５２１からなる。

【０１２４】スタティックＲＡＭ５２１のアドレス線５
２２には、１６ビットの圧縮データの第５ビットから第
１２ビットまでがアドレス信号として与えられる。

【０１２５】スタティックＲＡＭ５２１のアドレス信号
は８ビットであるので、スタティックＲＡＭ５２１のア
ドレス空間は２⁸ ワードとなる。スタティックＲＡＭ５
２１の各アドレスには、ハフマンＡＣ符号に対応するラ
ン長データＲＬ、付加ビット長データＡＢＬおよびトー
タルビット長データＴＢＬが予め記憶される。

【０１２６】スタティックＲＡＭ５２１のアドレス線５
２２に与えられるデータに従って、データ線５２３を介
してラン長データＲＬ、付加ビット長データＡＢＬおよ
びトータルビット長データＴＢＬが読出される。

【０１２７】図８は、メモリテーブル５３の構成を示す
ブロック図である。メモリテーブル５３はスタティック
ＲＡＭ５３１からなる。

【０１２８】スタティックＲＡＭ５３１のアドレス線５
３２には、１６ビットの圧縮データの第１０ビットから
第１６ビットまでがアドレス信号として与えられる。

【０１２９】スタティックＲＡＭ５３１に与えられるア
ドレス信号は７ビットであるので、スタティックＲＡＭ
５３１のアドレス空間は２⁷ ワードとなる。スタティッ
クＲＡＭ５３１の各アドレスには、ＡＣハフマン符号に
対応するラン長データＲＬ、付加ビット長データＡＢＬ
およびトータルビット長データＴＢＬが予め記憶され
る。

【０１３０】スタティックＲＡＭ５３１のアドレス線５
３２に与えられるデータに従って、データ線５３３を介
してラン長データＲＬ、付加ビット長データＡＢＬおよ
びトータルビット長データＴＢＬが読出される。

【０１３１】図９は、デコード回路５４の構成を示すブ
ロック図である。デコード回路５４は、組合せ回路５４
１、およびＤＣハフマン符号の数と等しい数の１４ビッ
トのレジスタ５４２を含む。

【０１３２】組合せ回路５４１には、１６ビットの圧縮
データの先頭ビットから第９ビットまでが与えられる。
各レジスタ５４２には、ＤＣハフマン符号に対応するハ
フマン符号長データＨＣＬ、付加ビット長データＡＢＬ
およびトータルビット長データＴＢＬが予め記憶され
る。

【０１３３】組合せ回路５４１に与えられるデータに従
って、複数のレジスタ５４２の１つが選択され、選択さ
れたレジスタ５４２からハフマン符号長データＨＣＬ、
付加ビット長データＡＢＬおよびトータルビット長デー
タＴＢＬが出力される。

【０１３４】図６に示されるデコード回路５１および図
９に示されるデコード回路５４の動作速度は、図７に示
されるメモリテーブル５２および図８に示されるメモリ
テーブル５３の動作速度よりも１桁速い。上記実施例の
ように、デコードブロック５を構成することによって、
ハフマン復号化回路の処理速度が高速になり、かつ回路
規模が小さくなる。

【０１３５】

【発明の効果】以上のようにこの発明によれば、複数の
ハフマン符号を符号長に基づいて複数のグループに分類
し、複数のグループに複数のデコード手段をそれぞれ割
当てることにより、デコード手段の全体の容量および回
路規模が小さくなる。

【０１３６】また、出現頻度の高い短い符号長のハフマ
ン符号を高速動作が可能なロジック回路によりデコード
し、かつ出現頻度の低い長い符号長のハフマン符号を回
路規模が小さいメモリ素子によりデコードすることによ
り、全体として、高速動作が可能でかつ回路規模が小さ
いハフマン復号化回路が得られる。

【０１３７】さらに、付加ビット長およびトータルビッ
ト長からハフマン符号長を算出する演算手段をさらに設
けることによって、各デコード手段の回路規模をさらに
縮小することが可能となる。

【図面の簡単な説明】

【図１】この発明の実施例のハフマン復号化回路および
ハフマン復号化方法におけるハフマン符号のグループ化
を示す図である。

【図２】各グループに属するハフマン符号のデコードの
際にデコード回路またはメモリテーブルに与えられるビ
ットを示す図である。

【図３】この発明の実施例のハフマン複合化回路の主要
部の構成を示すブロック図である。

【図４】図３のハフマン複合化回路に含まれるデコーダ
ブロックの詳細な構成を示すブロック図である。

【図５】図３のハフマン複合化回路に含まれるデコーダ
の詳細な構成を示す回路図である。

【図６】図４のデコーダブロックに含まれるデコード回
路の構成を示すブロック図である。

【図７】図４のデコーダブロックに含まれるメモリテー
ブルの構成を示すブロック図である。

【図８】図４のデコーダブロックに含まれるメモリテー
ブルの構成を示すブロック図である。

【図９】図４のデコーダブロックに含まれるデコード回
路の構成を示すブロック図である。

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

【図１１】画像データのブロック化を示す図である。

【図１２】８×８画素ブロックおよびＤＣＴ変換された
ブロックを示す図である。

【図１３】８×８画素ブロックおよびＤＣＴ係数の一例
を示す図である。

【図１４】ＤＣＴ係数、量子化ＤＣＴ係数および量子化
テーブルの関係を示す図である。

【図１５】量子化テーブルの一例を示す図である。

【図１６】量子化ＤＣＴ係数の一例を示す図である。

【図１７】ＤＣ係数のハフマン符号化を示すフロー図で
ある。

【図１８】ＤＣ差分値を説明するための図である。

【図１９】ＤＣ差分値のグループ化を示す図である。

【図２０】ＤＣ差分値のためのハフマン符号テーブルを
示す図である。

【図２１】ＤＣ差分値のための付加ビットを示す図であ
る。

【図２２】ＡＣ係数のハフマン符号化を示すフロー図で
ある。

【図２３】ジグザグスキャンを説明するための図であ
る。

【図２４】ＡＣ係数のグループ化を示す図である。

【図２５】ＡＣ係数のためのハフマン符号テーブルを示
す図である。

【図２６】ＡＣ係数のための付加ビットを示す図であ
る。

【図２７】ハフマン符号化の一例を示す図である。

【図２８】圧縮データの構造を示す図である。

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

【符号の説明】

１，２ レジスタ ３ バレルシフタ ４ デコーダ ５ デコーダブロック ６ 加算器 ７ レジスタ ８ デコーダ ９ レジスタ １０ 付加ビット抽出回路 １１ コントロール回路 ５１，５４ デコード回路 ５２，５３ メモリテーブル ５５ 減算器 ５６ ３ステートバッファ ５７ ゲート回路 ＤＳ１，ＤＳ２，ＤＳ３ デコーダ選択信号 ＤＣＳＬ ＤＣ符号選択信号 ＬＥ１，ＬＥ２ ラッチイネーブル信号 ＨＣＬ ハフマン符号長データ ＡＢＬ 付加ビット長データ ＲＬ ラン長データ ＥＯＢ エンドオブブロック符号 ＡＢ 付加ビット なお、各図中同一符号は同一または相当部分を示す。

Claims (5)

【特許請求の範囲】
1. 【請求項１】 複数のハフマン符号が符号長に基づいて
   複数のグループに分類され、前記複数のグループに対応
   して設けられかつ各々が対応するハフマン符号をデコー
   ドするための複数のデコード手段と、 与えられたハフマン符号の先頭ビットから連続する同一
   値のビット数に基づいて前記複数のデコード手段の１つ
   を選択して活性化する選択手段とを備えた、ハフマン復
   号化回路。
2. 【請求項２】 前記複数のデコード手段は、メモリ素子
   からなる第１のデコード手段およびロジック回路からな
   る第２のデコード手段を含み、 前記第１のデコード手段は長い符号長のハフマン符号を
   含むグループに割当てられ、前記第２のデコード手段は
   短い符号長のハフマン符号を含むグループに割当てられ
   る、請求項１記載のハフマン復号化回路。
3. 【請求項３】 前記複数のデコード手段の各々は、付加
   ビット長およびトータルビット長を含む復号化情報を出
   力し、 前記付加ビット長および前記トータルビット長からハフ
   マン符号長を算出する演算手段をさらに含む、請求項１
   記載のハフマン復号化回路。
4. 【請求項４】 複数のハフマン符号を符号長に基づいて
   複数のグループに分類し、 与えられたハフマン符号をデコードする複数のデコード
   手段を前記複数のグループにそれぞれ割当て、 与えられたハフマン符号の先頭ビットから連続する同一
   値のビット数に基づいて前記複数のデコード手段の１つ
   を選択して活性化する、ハフマン復号化方法。
5. 【請求項５】 前記複数のデコード手段はメモリ素子か
   らなる第１のデコード手段およびロジック回路からなる
   第２のデコード手段を含み、 前記第１のデコード手段を長い符号長のハフマン符号を
   含むグループに割当て、前記第２のデコード手段を短い
   符号長のハフマン符号を含むグループに割当てる、請求
   の範囲４記載のハフマン復号化方法。