JP3136796B2 - 可変長符号デコーダ - Google Patents

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は画像データや音声データ
を圧縮して伝送するのに使用して好適なハフマン符号等
の可変長符号を復元する可変長符号デコーダに関する。

【０００２】

【従来の技術】一般に限られたデータ転送能力の通信回
線を用いて、画像データ等の大量のデータを伝送する場
合や、少ない容量の蓄積媒体に長時間の画像データを記
録する場合等においては、このデータ量を削減するデー
タ圧縮技術が用いられている。

【０００３】このデータを圧縮する方法として多くの技
術が開発され、実用化されている。例えば画像データを
コサイン変換してその係数を用いて圧縮するＤＣＴ変換
符号化、データの発生頻度に合わせて対応する符号の長
さを変化させて全体の符号量を削減する可変長符号化等
がある。

【０００４】この可変長符号化の例として従来ハフマン
符号化が提案されている。このハフマン符号の基本的考
えは、発生頻度の高い事象（データ）には短い符号を割
当て、発生頻度の低いものには長い符号を割当てること
により、平均の符号長（あるいはトータルの符号量）を
減らしデータを圧縮することにある。

【０００５】各事象に対応した具体的なハフマン符号の
生成は各事象の発生確率に依存し、事象の統計データか
らのハフマン符号の生成の仕方は種々の情報理論の本に
述べられているので、ここではその説明を省略する。説
明の便宜上、ここでは下記のような５つのデータ
（“０”，“１”，“２”，“３”，“４”）に対応し
た簡単なハフマン符号を取り上げて説明する（数が小さ
い程発生頻度が高いものとする）。

【０００６】 データ ハフマン符号 “０” 「 １」 “１” 「 ０１」 “２” 「 ００１」 “３” 「 ０００１」 “４” 「００００１」

【０００７】例として“２”，“３”，“０”，
“１”，“３”，“０”，“４”のデータのシーケンス
のハフマン符号列を示すと次のようになる。

【０００８】 「００１０００１１０１０００１１００００１」 このデータは左側から順次出力される。

【０００９】このハフマン符号を復元する従来のハフマ
ンデコーダは図３に示す如くであった。即ち図３におい
て、１はハフマン符号列が供給される入力端子を示し、
この入力端子１にはシステムのバス幅、入出力の方法に
より１ビットシリアルに入力されたり、バイト単位、ワ
ード単位で入力される。

【００１０】この入力端子１よりのハフマン符号列は一
旦ｎビットのレジスタ２に保持される。ここでｎはハフ
マン符号の最大長ｍよりも大きい値とする。このレジス
タ２のｎビットのうちハフマン符号の最大長であるｍビ
ットがバレルシフタ３によってデコーダ回路４に供給さ
れる。

【００１１】このバレルシフタ３は入力符号列をシフト
するビット数に関係なく一定時間でシフトすることがで
き、１クロックパルスで１ビットシフトするシフトレジ
スタに比べ高速処理が可能である。

【００１２】またこのデコーダ回路４はＲＯＭ，ＰＬＡ
（Ｐｒｏｇｒａｍａｂｌｅ Ｌｏｇｉｃ Ａｒｒｅ
ｙ）、論理ゲート等より構成される。このデコーダ回路
４においては入力信号がハフマン符号と一致したときに
ヒット信号出力端子４ａにヒット信号を出力すると共に
復元されたデータをデータ出力端子５に出力し、更にそ
のときのハフマン符号の長さを示す符号長信号を符号長
信号出力端子４ｂに出力する。

【００１３】このヒット信号出力端子４ａに得られるヒ
ット信号を、このハフマン符号デコーダのコントローラ
６に供給し、このヒット信号によりコントローラ６はこ
のハフマン符号の復元データを次段に伝送すると共に符
号長出力端子４ｂに得られるこの符号長信号を用いて、
シフトコントローラ７によりバレルシフタ３を制御し、
つぎの入力信号をデコーダ回路４に供給する。再びハフ
マン符号が合致すれば上述同様の動作を続けてレジスタ
２のハフマン符号列を順次復元していく。

【００１４】このレジスタ２のハフマン符号列が不足し
たときには新たに入力端子１からハフマン符号を読み込
む。このシフトコントローラ７はレジスタ２のビット数
ｎによって決まる剰余系の加算器を持ち、デコーダ回路
４から出力される符号長を累積してゆき、バレルシフタ
３のシフト量を制御する。デコーダ回路４に符号列が入
力されていながらこの符号が合致しない（ヒットしな
い）ときには、入力されたハフマン符号に誤りがあると
いうことであり、ハフマンデコーダはエラーの処理に移
る。

【００１５】次に図４を参照し上述のハフマン符号列の
例を上げて、このハフマン符号デコーダの動作を説明す
る。図４Ａは初期状態でレジスタ２にハフマン符号列が
入力された状態を示す。このときはバレルシフタ３のシ
フト量は「０」であり、図４Ａに示すようにレジスタ２
の左端の５ビット（ハフマン符号の最大長）がデコーダ
回路４に入力される。

【００１６】このデコーダ回路４では“２”に対応する
データがヒットするので、データ出力端子５にデータ
“２”が出力され、符号長信号として「３」が出力さ
れ、コントローラ６によりデコーダ回路４よりの出力デ
ータ“２”が次段へ送られ、シフトコントローラ７内
で、このシフト量「３」が加算される。

【００１７】図４Ｂは次の状態を示す。バレルシフタ３
のシフト量は「３」となっており、レジスタ２の左から
４ビット目から５ビットがデコーダ回路４に供給され
る。デコーダ回路４ではデータとして“３”が出力さ
れ、符号長信号として「４」が出力される。シフトコン
トローラ７内で符号長「４」が累積され、シフト量は
「７」となる。

【００１８】図４Ｃはその次の状態を示す。バレルシフ
タ３のシフト量は「７」となるので、レジスタ２の左か
ら８ビット目から５ビットがデコーダ回路４に入力され
る。以下順次この動作を続けて行く。

【００１９】

【発明が解決しようとする課題】斯るハフマンデコーダ
の高速化を計る際、最も問題となるのは図３のバレルシ
フタ３、デコーダ回路４及びシフトコントローラ７のル
ープでの遅延であり、特に１クロックで一つのデータを
処理するような高速なハフマンデコーダであれば、大き
なバレルシフタ（通常は３２ビット程度）での遅延、大
きなＲＯＭ、ＰＬＡ、論理ゲートでの遅延及びシフトコ
ントローラ７内でのシフト量の加算の遅延等の総和が１
クロック以内でなければいけないという制約があり、ハ
ードウェアの設計上厳しくなることである。

【００２０】このクリティカルバスでの高速動作の限界
を避けるため、このループを２クロックの動作とするこ
とも考えられるが、このときにはこのハフマンデコーダ
の動作性能は一挙に半分に落ちるという問題が生じる。

【００２１】今後扱う画像が高画質となり、入力端子１
に供給されるハフマン符号列が高ビットレイトになるに
したがい、ますますこのハフマンデコーダの高速動作が
要求される。

【００２２】本発明は斯る点に鑑み、クロック周波数を
上げることなく、高速の可変長符号デコーダを実現する
ことを目的とする。

【００２３】

【課題を解決するための手段】本発明可変長符号デコー
ダは例えば図１に示す如く、可変長符号をデータへ復元
する可変長符号デコーダにおいて、可変長符号列の先頭
の可変長符号を復元するための第１のデコーダ回路４
と、この可変長符号列の発生頻度の高い先頭から複数個
の可変長符号の連続したシーケンスを復元することがで
きる第２のデコーダ回路８とを有し、この第２のデコー
ダ回路８に優先権を付与したものである。

【００２４】

【００２５】また本発明可変長符号デコーダは上述にお
ける可変長符号がハフマン符号であるものである。

【００２６】

【作用】本発明は一度のデコーダ動作において頻度の高
い複数個のデータを復元できるので、クロックの周波数
を上げることなく、高速の可変長符号デコーダを実現す
ることができる。

【００２７】

【実施例】以下図１を参照して本発明可変長符号デコー
ダをハフマン符号を復元するハフマン符号デコーダに適
用した例につき説明しよう。この図１において、図３に
対応する部分には同一符号を付し、その詳細説明を省略
する。

【００２８】図１例においては、図３例同様に、入力端
子１よりのハフマン符号列を一旦、ｎビットのレジスタ
２に保持する。この場合このｎはハフマン符号の最大長
ｍよりも大きい値とする。

【００２９】本例においてはこのレジスタ２のｎビット
のうちハフマン符号の最大長であるｍビットをバレルシ
フタ３によってデコーダ回路４及びデコーダ回路８に並
列に供給する。

【００３０】このバレルシフタ３は入力符号列をシフト
するビット数に関係なく一定時間で、シフトすることが
でき、１クロックパルスで１ビットシフトするシフトレ
ジスタに比べ高速処理が可能である。

【００３１】またこのデコーダ回路４は図３のデコーダ
回路と同様に取り得るハフマン符号の全部を復元できる
如くする。説明の便宜上、上述の如く５つのデータ
（“０”，“１”，“２”，“３”，“４”）に対応し
た簡単なハフマン符号を取り得るとしたときには、この
全部の５つのハフマン符号を復元できる如く構成する。

【００３２】このデコーダ回路４においては、入力信号
がハフマン符号と一致したときに、ヒット信号出力端子
４ａにヒット信号を出力すると共に復元されたデータを
選択回路９に供給し、更にそのときハフマン符号の長さ
を示す符号長信号を符号長信号出力端子４ｂに出力す
る。

【００３３】このヒット信号出力端子４ａに得られるヒ
ット信号をこのハフマン符号デコーダのコントローラ６
に供給し、また符号長信号出力端子４ｂに得られる符号
長信号をシフトコントローラ７に供給する如くする。

【００３４】またデコーダ回路８は発生頻度の高い、選
択した２個のハフマン符号の連続したシーケンスを復元
できる如くする。例えば下記の３つのシーケンスについ
てのみ復元できる如くする。

【００３５】 シーケンス ハフマン符号列 “０”→“０” 「 １１」 “０”→“１” 「１０１」 “１”→“０” 「０１１」

【００３６】このデコーダ回路８に入力信号が特定のハ
フマン符号列例えば先頭から２個のハフマン符号が「１
１」「１０１」「０１１」と一致したときにヒット信号
出力端子８ａにヒット信号を出力すると共に復元された
２個のデータ例えば“０”“０”，“０”“１”，
“１”“０”を選択回路９に供給し、更にそのときのこ
の２個のハフマン符号長の和の符号長信号を符号長信号
出力端子８ｂに出力する。

【００３７】このヒット信号出力端子８ａに得られるヒ
ット信号をコントローラ６に供給する。このヒット信号
出力端子８ａにヒット信号が得られたときには選択回路
９は優先的にデコーダ回路８の出力側に得られる２個の
データをデータ出力端子５に出力するようにすると共に
シフトコントローラ７においては符号長信号出力端子８
ｂに得られる２個のハフマン符号の符号長の和の符号長
信号を使用してシフトコントロール動作を行う如くす
る。

【００３８】ヒット信号出力端子４ａにしかヒット信号
が得られないときには選択回路９においてはデコーダ４
の復元データをデータ出力端子５に出力すると共にシフ
トコントローラ７においては符号長信号出力端子４ｂに
得られる符号長信号を使用してシフトコントロール動作
を行う。その他は図３と同様に構成する。

【００３９】次に図２及び図４を参照し、上述のハフマ
ン符号列の例を上げて、本例のハフマン符号デコーダの
動作を説明する。図４Ａは初期状態でレジスタ２上にハ
フマン符号列が入力された状態を示す（図２のステップ
Ｓ１）。このときはバレルシフタ３のシフト量は「０」
であり、ステップＳ２でデータを読み込み図４Ａに示す
ようにレジスタ２の左端の５ビット（ハフマン符号の最
大長）がデコーダ回路４及び８に入力される。

【００４０】このデコーダ回路４では“２”に対応する
データがヒットする（ステップＳ４）が、デコーダ回路
８はヒットしない（ステップＳ３）ので、デコーダ回路
４で１つのデータをデコードし（ステップＳ５）コント
ローラ６によりデータ出力端子５よりデータ“２”が出
力され、符号長信号として「３」がシフトコントローラ
７に供給され、このシフトコントローラ７内で、このシ
フト量が加算される（ステップＳ６）。

【００４１】次にステップＳ７に移行し、次のデータが
あるかどうかを判断する。図４Ｂは次の状態を示す。バ
レルシフタ３のシフト量は「３」となっており、レジス
タ２の左から４ビット目から５ビットがデコーダ回路４
及び８に供給される（ステップＳ２）。このときはデコ
ーダ回路４では“３”に対応するデータがヒットする
（ステップＳ４）が、デコーダ回路８はヒットしない
（ステップＳ３）ので、デコーダ回路４で１つのデータ
をデコードし（ステップＳ５）コントローラ６によりデ
ータ出力端子５にデータ“３”が出力され、符号長信号
として「４」がシフトコントローラ７に供給され、この
シフトコントローラ７内で、このシフト量が加算される
（ステップＳ６）。

【００４２】次にステップＳ７に移行し、次のデータが
あるかどうかを判断する。図４Ｃはその次の状態を示
す。バレルシフタ３のシフト量は「７」となるので、レ
ジスタ２の左から８ビット目から５ビットがデコーダ回
路４及び８に供給される（ステップＳ２）。このときは
デコーダ回路４では“０”に対応するデータがヒット
し、デコーダ回路８では“０”及び“１”に対応するデ
ータがヒットする（ステップＳ３）ので、コントローラ
６により優先的にこのデコーダ回路８の２個のデータ
“０”及び“１”の２つのデータがデコードされ（ステ
ップＳ８）、この２つのデータがデータ出力端子５に出
力され、符号長信号として「１」＋「２」の「３」がシ
フトコントローラ７に供給され、このシフトコントロー
ラ７内で、このシフト量が加算される（ステップＳ
９）。

【００４３】次にステップＳ７に移行し、次のデータが
あるかどうかを判断する。図４Ｄはその次の状態を示
す。バレルシフタ３のシフト量は「１０」となるので、
レジスタ２の左から１１ビット目から５ビットがデコー
ダ回路４及び８に入力される（ステップＳ２）。以下順
次この動作を続けて行く。ステップＳ７で、次のデータ
がないと判断したときは終了する。

【００４４】また、データを読み込（ステップＳ２）ん
だときに、デコーダ回路４及び８が共にヒットしない
（ステップＳ３及びＳ４）ときはエラー処理を行う如く
する（ステップＳ１０）。

【００４５】本例は上述の如くハフマン符号列に頻度の
高いハフマン符号が２個連続しているときに一度のデコ
ーダ動作において、２個のデータを復元できるので、ク
ロックの周波数を上げることなく、高速のハフマン符号
デコーダを実現することができる。

【００４６】尚上述実施例についてはハフマン符号をデ
コードする例につき述べたが、本発明をその他の可変長
符号をデコードする可変長符号デコーダに適用できるこ
とは容易に理解できよう。

【００４７】また上述実施例においてはデコーダ回路８
を２個の連続するシーケンスを復元できるように述べた
が、これを３個以上の連続するシーケンスを復元できる
ようにしても良いことは勿論である。

【００４８】また本発明は上述実施例に限ることなく本
発明の要旨を逸脱することなくその他種々の構成が採り
得ることは勿論である。

【００４９】

【発明の効果】本発明によれば一度のデコーダ動作で頻
度の高い複数のデータを復元できるので、クロックの周
波数を上げることなく、高速の可変長符号デコーダを実
現できる利益がある。

【図面の簡単な説明】

【図１】本発明可変長符号デコーダの一実施例を示す構
成図である。

【図２】本発明の説明に供する流れ図である。

【図３】従来のハフマン符号デコーダの例を示す構成図
である。

【図４】本発明の説明に供する線図である。

【符号の説明】

１ 入力端子 ２ レジスタ ３ バレルシフタ ４，８ デコーダ回路 ５ データ出力端子 ６ コントローラ ７ シフトコントローラ ９ 選択回路

Claims (3)

(57)【特許請求の範囲】
1. 【請求項１】 可変長符号をデータへ復元する可変長符
   号デコーダにおいて、 可変長符号列の先頭の可変長符号を復元するための第１
   のデコーダ回路と、前記可変長符号列の発生頻度の高い
   先頭から複数個の可変長符号の連続したシーケンスを復
   元することができる第２のデコーダ回路とを有し、 前記第２のデコーダ回路に優先権を付与したことを特徴
   とする可変長符号デコーダ。
2. 【請求項２】 請求項１記載の可変長符号デコーダにお
   いて、 前記可変長符号がハフマン符号であることを特徴とする
   可変長符号デコーダ。
3. 【請求項３】 請求項２記載の可変長符号デコーダにお
   いて、 前記ハフマン符号の最大長であるｍビットをバレルシフ
   タに供給し、このバレルシフタの出力を前記第１及び第
   ２のデコーダ回路に夫々供給するようにしたことを特徴
   とする可変長符号デコーダ。