JPH06125277A - ハフマン復号回路 - Google Patents

Abstract

(57)【要約】 （修正有） 【目的】処理スピードをあげ、必要メモリ３の容量を少
なくして集積化を容易にする。 【構成】リセット機能付ラッチ１と、ハフマン符号デー
タの一部およびラッチ１の出力の一部を選択するとセレ
クタ２と、メモリ３とを有する。まず、ラッチ回路１が
リセットされ、８ビット全てＱが出力される。このう
ち、上位５ビットがメモリ３のＡＨＨに送出され、また
下位３ビットはセレクタ２のＡＱに送られる。次に、ハ
フマン符号データ列ｄの先頭１ビットはメモリ３の最下
位アドレスＡＬに送られ、それ以下の３ビットはセレク
タ２のＡ１に入力される。ここで、４ビット単位で復号
される時はＡ１を、また１ビット単位で復号される時は
ＡＱのデータをセレクタ２はセレクト信号ｅにより選択
し、その出力３ビットをメモリ３のアドレスＡＨＬに送
る。メモリ３から復号語ａ、符号長ｂまたはポインタと
フラグｃが出力される。ポインタの場合は再度上記の動
作を繰り返す。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、ハフマン符号を復号処
理するハフマン復号回路に関し、特にハフマン復号処理
スピード等を改善するとともに、集積化に適したハフマ
ン復号回路に関する。

【０００２】

【従来の技術】従来のハフマン復号回路は、ハフマン符
号に対応する復号語を見つけるために、最大符号語長分
のアドレスを持ったメモリを使用したり、１ビット毎に
復号ツリーを追跡する回路あるいはメモリを分割した復
号回路を用いている。

【０００３】図６は従来の一例を示すハフマン復号回路
のブロック図である。図６に示すように、このハフマン
復号回路は最大符号長分のアドレスを持つメモリ９を設
けて構成されるが、このメモリ９は６４ＫＷ×１３ビッ
ト構成である。すなわち、メモリ９のアドレス入力にハ
フマン符号データ列ｈを与え、そのメモリ９の出力とし
て復号語ｊおよび符号長ｋからなる復号結果を得るよう
になっている。今、ハフマン符号データｈの最大符号語
長を１６ビット、復号語を８ビットとすれば、メモリ９
に復号語８ビットと符号長５ビットを設定する。例え
ば、復号語Ａに対するハフマン符号が‘０１０１’であ
れば、アドレス‘０１０１０…０’から‘０１０１１…
１’の全てに復号語Ａと符号長４を設定する。同様に、
各復号語に対するハフマン符号についてのアドレスを設
定する。

【０００４】このハフマン復号回路においては、まずハ
フマン符号データ列ｈの先頭から１６ビットをメモリ９
のアドレスに入力する。仮に、‘０１０１…’が送られ
てきたとすると、メモリ９のアドレス上位４ビットに
‘０１０１’が入力され、下位１２ビットには次のハフ
マン符号が入力される。このように、メモリ９のアドレ
ス‘０１０１０…０’から‘０１０１１…１’には全て
復号語Ａ，符号長４を設定してあるので、メモリ９から
復号語Ａ，符号長４が出力される。この符号長４はハフ
マン符号データ列へ送られ、次のハフマン符号データ列
の先頭が決り、先頭から１６ビットをメモリ９のアドレ
スへ入力する。以下同様に、この動作を繰り返すことに
よって復号される。

【０００５】図７は従来の他の例を示すハフマン復号回
路のブロック図である。図７に示すように、この復号回
路は１ビット毎に復号ツリーを追跡するものである。こ
の復号回路はラッチ１０と内部メモリ１１とを有する。
内部メモリ１１は５１２Ｗ×９ビット構成であり、ハフ
マン符号データ列ｈの先頭から１ビットを最下位のアド
レス入力とし且つラッチ回路１０の出力８ビットを上位
８ビットのアドレス入力とする。また、ラッチ回路１０
は内部メモリ１１からポインタが出力された場合にラッ
チする。この内部メモリ１１の出力９ビットの内８ビッ
トで復号語ｍもしくはポインタを表わし、他の１ビット
は復号語の出力であれば１、ポインタの出力であれば０
であればフラグｎを表わすこの復号回路の動作は、まず
最初にハフマン符号データ列ｈから入力した１ビットに
よりメモリアドレスを決定し、内部メモリ１１の出力を
得る。その出力結果がポインタであれば、そのポインタ
と次のハフマン符号データ列の１ビットで再び内部メモ
リ１１をアクセスする。一方、出力が復号語であれば、
１回の復号動作を終了する。以下具体的な１例をとりあ
げて動作を説明する。

【０００６】図８は図７に示す内部メモリをあらかじめ
設定した状態を表わす図である。図８に示すように、こ
こではハフマン符号が‘０１０１’の復号語Ａを例にし
たが、同様にして各復号語に対するハフマン符号につい
てのアドレスも設定する。

【０００７】再び、図７に戻ると、ハフマン符号データ
列の先頭から１ビットとラッチ回路１０からの８ビット
の計９ビットのアドレスが内部メモリ１１へ送られる。
ハフマン符号データ列ｈの先頭の１ビットは内部メモリ
１１のアドレス最下位ビットに入力される。例えば、復
号語Ａに対するハフマン符号‘０１０１’が送られてき
たとすると、ラッチ回路１０はリセットされ、８ビット
全てに‘０’が出力され、ハフマン符号の４ビット目の
‘０’と共に内部メモリ１１に送られる。ここで、ハフ
マン符号の‘０’は最下位アドレスに入力される。内部
メモリ１１はポインタ‘０００００００１’とポイント
の出力を表わすフラグ＝０が出力される。ポインタ，フ
ラグ＝０がラッチ回路１０に送られると、ラッチ回路１
０は‘０００００００１’を出力し、ハフマン符号の３
ビット目の‘１’と共に内部メモリ１１に送出する。従
って、内部メモリ１１からポインタ‘００００００１
０’とポイントの出力を表わすフラグ＝０が出力され
る。ポインタ，フラグ＝０がラッチ回路１０に送られる
ので、ラッチ回路１０は‘００００００１０’を出力
し、ハフマン符号の２ビット目の‘０’と共に内部メモ
リ１１に送出する。再び、内部メモリ１１はポインタ
‘００００００１１’とポイントの出力を表わすフラグ
＝０を出力し、ポインタ，フラグ＝０はラッチ回路１０
に転送される。ラッチ回路１０は‘００００００１１’
を出力し、ハフマン符号の１ビット目の‘１’と共に内
部メモリ１１に送られる。内部メモリ１１で復号語Ａと
復号語の出力を表わすフラグ＝１を出力する。このフラ
グ＝１により、ラッチ回路１０はリセットされ、そして
次のハフマン符号データ列の先頭が送られてくる。以下
同様に、この動作を繰り返すことにより復号される。

【０００８】図９は従来のまた別の例を示すハフマン復
号回路のブロック図である。図９に示すように、ここで
はメモリを分割し、ハフマン符号データｒの最大符号語
長を１６ビットとするとともに、符号長の小さい順に符
号を割り付け直したものとする。この復号回路はハフマ
ン符号データ列ｒの先頭から１０ビットをアドレス入力
とする半導体集積回路内の内部メモリ１２と、データ列
ｒの１３ビット目から１ビット目までをアドレス入力と
する半導体集積回路外の外部メモリ１３と、これら内部
メモリ１２，外部メモリ１３の出力を選択する復号語の
セレクタ１４および符号長のセレクタ１５と、内部メモ
リ１２の出力が有効であれば内部メモリ１２の出力を選
択するセレクト信号をセレクタ１４に送るセレクト信号
生成部１６とを有する。内部メモリ１２は１ＫＷ×１３
ビット、外部メモリ１３は８ＫＷ×１３ビット構成であ
る。

【０００９】まず、内部メモリ１２，外部メモリ１３に
復号語８ビットと符号長５ビットを設定する。内部メモ
リ１２には、ハフマン符号データ列ｒの１６ビットのう
ち上位１０ビット以下で復号語を表わすものについて復
号語と符号長を設定し、その内部メモリ１２の出力が有
効な場合は１、無効な場合は０であるフラグを符号長５
ビット目に設定する。一方、外部メモリ１３には１１ビ
ット以上１６ビットまでのハフマン符号に対する復号語
および符号長を設定する。但し、符号長の順にハフマン
コードが割り当ててあれば、１１ビット以上のハフマン
符号の先頭３ビットは必ず‘１１１’になるので、外部
メモリ１３のアドレス入力には先頭３ビットを除いて入
力している。

【００１０】更に、内部メモリ１２には、例えば復号語
Ａに対するハフマン符号が‘０１０１’であれば、アド
レス‘０１０１０…０’から‘０１０１１…１’の全て
に復号語Ａ，符号長４を設定する。外部メモリ１３に
は、例えば復号語Ｂに対するハフマン符号が‘１１１１
１０１０００１’であれば、アドレス‘１１０１０００
１０…０’から‘１１０１０００１１…１’の全てに復
号語Ｂ，符号長１１を設定する。同様に、各復号語に対
するハフマン符号についてのアドレスを設定する。

【００１１】次に、かかる復号回路の動作は、ハフマン
符号データ列ｒの先頭から上位１０ビット（１５：６）
を内部メモリ１２のアドレスに、下位１３ビット（１
２：０）を外部メモリ１３のアドレスに与える。仮に、
ハフマン符号‘０１０１…’が送られてきたとすると、
内部メモリ１２のアドレス上位４ビットに‘０１０１’
が入力され、復号語Ａ，符号長４を出力する。このと
き、フラグ＝１も出力し、内部メモリ１２からの出力が
有効であることをセレクト信号生成部１６に送る。ま
た、外部メモリ１３はアドレス入力された１３ビットで
得られた復号語と符号長を出力する。これらメモリ１
２，１３から得られた復号語と符号長はそれぞれセレク
タ１４，１５に送られる。一方、セレクト信号生成部１
６はフラグ＝１より内部メモリ１２の出力を選択するよ
うにセレクタ１４，１５にセレクト信号を送る。これに
より、各セレクタ１４，１５は内部メモリ１２からの復
号語Ａ，符号長４を出力する。この符号長４はハフマン
符号データ列に送られ、次のハフマン符号データ列の先
頭が決る。以下同様に、この動作を繰り返すことによっ
て符号データが復号される。

【００１２】

【発明が解決しようとする課題】上述した従来のハフマ
ン復号回路は、１ビット毎にコード・ツリーを追跡した
場合、符号ビット数回のメモリ・アクセスを必要とする
ので、処理スピードの時間かかるという欠点がある。

【００１３】また、これを避ける回路として、最大符号
語長分のビット・アドレスを持つメモリを使用する回路
を用いることがある。しかしながら、この復号回路は、
例えば１６ビットで６５５３６ワードの大きなメモリを
必要とし、このように大きなメモリをチップにのせる
と、面積が大きくなり、価格が高くなるという欠点があ
る。

【００１４】更に、これらを避ける回路として、メモリ
を分割するものがある。この回路は、前述した復号回路
と比べると、１０２４ワードの内部メモリですむが、外
部メモリも必要とするため、システム全体では価格が高
くなるという欠点がある。

【００１５】本発明の目的は、復号処理スピードを速く
し、必要とするメモリ容量も少なくするとともに、集積
化の容易なハフマン復号回路を提供することにある。

【００１６】

【課題を解決するための手段】本発明のハフマン復号回
路は、復号語を保持しフラグによりリセットされるラッ
チ手段と、前記ラッチ手段の出力の一部およびハフマン
符号データの一部を選択する選択手段と、前記ハフマン
符号の先頭の１ビットを含む残りのデータと前記ラッチ
手段の出力の残りのデータと前記選択手段の出力データ
により前記復号語および符号長と前記フラグを出力する
メモリ手段とを有して構成される。

【００１７】

【実施例】次に、本発明の実施例について図面を参照し
て説明する。図１は本発明の第１の実施例を示すハフマ
ン復号回路のブロック図である。図１に示すように、本
実施例は４ビットのハフマン符号データ列ｄの先頭１ビ
ットを最下位のアドレス入力とする５１２Ｗ×９ビット
構成のメモリ３と、このメモリ３からのＱＦの出力すな
わちフラグｃが０である場合にデータＱ７−Ｑ０の８ビ
ットをラッチするリセット付ラッチ回路１と、ハフマン
復号を１ビット単位に行う場合はラッチ回路１からの３
ビットを選択し、４ビット単位で行う場合にはハフマン
符号データｄの３ビットを選択するセレクタ２とから構
成される。特に、メモリ３は最下位アドレスＡＬのほか
にセレクタ２の出力３ビットをアドレス２ビット目から
４ビット目とし且つラッチ回路１から出力８ビットの内
５ビットを上位５ビットのアドレス入力とし、ＱＤから
復号語ａと符号長ｂを出力し、ＱＦからフラグｃを出力
する。このメモリ３のＱＦの出力は、ＱＤの出力が復号
語であれば１、ポインタであれば０を表わすフラグであ
る。

【００１８】図２（ａ），（ｂ）はそれぞれ図１に示す
メモリの２つの設定例を説明するための図である。図２
（ａ），（ｂ）に示すように、メモリ３にはあらかじめ
復号語ＡおよびＣのデータが設定されているとする。以
下、ハフマン符号ｄが‘０１０１’の復号語Ａと、‘１
１０１０００１０１’の復号語Ｃとを４ビット単位で復
号した場合について説明する。

【００１９】まず、図２（ａ）に示すように、復号語Ａ
に対するハフマン符号‘０１０１’が送られてくると、
ラッチ回路１はリセットされ、８ビット全て‘０’を出
力する。この８ビットの内上位５ビットはメモリ３のア
ドレス上位５ビットに入力される。また、下位３ビット
はセレクタ２のＡ０端子に入力されるが、４ビット単位
の時のセレクタ２は外部からのセレクト信号ｅによりＡ
１端子側を選択するので、この下位３ビットデータは無
視される。次に、ハフマン符号データｄの４ビット目の
‘０’はメモリ３の最下位アドレスに入力される。３ビ
ット目から１ビット目の‘１０１’はセレクタ２のＡ１
端子を経由してメモリ３のアドレスＡＨＬに送られる。
結局、メモリ３にはアドレス‘０００００１０１０’が
送られるので、メモリ３は復号語Ａ，符号長４と復号語
の出力を表わすフラグ＝１を出力する。このフラグ＝１
により、ラッチ回路１はリセットされる。そして、次の
ハフマン符号データ列ｄの先頭が送られてくる。

【００２０】次に、図２（ｂ）に示すように、復号語Ｃ
に対するハフマン符号‘１１０１０００１０１’が送ら
れてきたとする。このときのラッチ回路１はリセットさ
れ、８ビット全て‘０’が出力される。従って、メモリ
アドレスＡＨＨには‘０００００’が入力され、一方ハ
フマン符号データｄの１０ビット目の‘１’はセレクタ
２のＡ１を経由してメモリアドレスＡＨＬに入力され
る。結局、メモリ３にはアドレス‘０００００１０１
１’が入力され、メモリ３からポインタ‘００００１０
００’とフラグ＝０が出力される。このメモリ３の出力
がポインタであるので、このポインタとハフマン符号デ
ータ列ｄの次の４ビットに基づいて再度追跡を行う。

【００２１】次に、ラッチ回路１はポインタをラッチす
るので、‘００００１０００’を出力する。この出力の
うち、上位５ビット‘００００１’はメモリアドレスＡ
ＨＨに入力される。また、ハフマン符号データｄの６ビ
ット目の‘０’はメモリ３の最下位アドレスＡＬに入力
される。更に、５ビット目から３ビット目の‘００１’
はセレクタ２のＡ１を経由してメモリアドレスＡＨＬに
入力される。結局、メモリ３にはアドレス‘００００１
１０００’が入力され、メモリ３からはポインタ‘００
０１００００’とフラグ＝０が出力される。この出力が
またもポインタであるので、再度追跡を行う。

【００２２】これにより、ラッチ回路１はポインタをラ
ッチするので、‘０００１００００’を出力する。この
うち、上位５ビット‘０００１０’はメモリアドレスＡ
ＨＨに入力され、ハフマン符号データｄの２ビット目の
‘０’はメモリ３の最下位アドレスＡＬに入力される。
更に、１ビット目の‘１’と次のハフマン符号データ列
ｄの先頭２ビット‘××’はセレクタ２のＡ１端子を経
由し、メモリアドレスＡＨＬに入力される。従って、メ
モリ３にはアドレス‘０００１０××１０’が入力さ
れ、メモリ３からは復号語Ｃ，符号長１０と復号語の出
力をあらわすフラグ＝１が出力される。このフラグによ
ってラッチ回路１はリセットされる。

【００２３】以上のように、４ビット単位でハフマン復
号を行うのであるが、復号テーブルの大きさは最悪の場
合１ビット単位に比べ１６倍の容量が必要になる。この
ような場合は、１ビット単位の復号ツリーをメモリ３に
設定し、セレクタ２をＡ０端子側にして１ビット単位で
復号ツリーを追跡する。

【００２４】図３は本発明の第２の実施例を示すハフマ
ン復号回路のブロック図である。図３に示すように、本
実施例はラッチ１およびセレクタ２と、１６ビットのハ
フマン符号データ列ｈの先頭から２ビットをメモリアド
レス下位２ビットに入力し且つセレクタ２の出力８ビッ
トをアドレス３ビット目から１０ビット目のアドレス入
力とする内部メモリ４と、ハフマン符号データ列ｈの下
位１３ビットをアドレス入力とする外部メモリ５と、内
部メモリ４の出力が有効であれば内部メモリ４の出力を
選択するセレクト信号をセレクタ６，７に送るセレクト
信号生成部８とを有する。このうち、ラッチ回路１は内
部メモリ４からのフラグの出力が０である場合にデータ
（Ｑ７−Ｑ０）をラッチする。セレクタ２は２ビット毎
の追跡を行う場合にラッチ回路１からの８ビットを選択
し、それ以外の場合にハフマン符号データ８ビット（１
３−６）を選択する。更に、内部メモリ４は１ＫＷ×１
３ビット、外部メモリ５は８ＫＷ×１３ビットで構成さ
れる。

【００２５】まず、内部メモリ４および外部メモリ５に
それぞれ復号語８ビットと符号長５ビット以下で復号語
をあらわすものについて復号語および符号長を設定す
る。また、内部メモリ４の出力が有効な場合は１、無効
な場合は０であるフラグを符号長５ビット目に設定す
る。一方、外部メモリ５には、１１ビット以上１６ビッ
トまでのハフマン符号に対する復号語および符号長を設
定する。

【００２６】次に、かかるハフマン復号回路において、
ハフマン符号長が１０ビット以内であれば内部メモリ４
だけで高速に復号出来る。復号処理スピードが遅くても
良い場合は、１ビット毎の復号ツリーを追跡して復号す
る。逆に、価格が高くても処理スピードを速くする必要
がある場合は、内部メモリ４と外部メモリ５を用いて復
号する。以下、内部メモリ４の具体的設定例をとり上げ
て説明する。

【００２７】図４は図３に示す内部メモリの一設定例を
表わす図である。図４に示すように、まずハフマン符号
データｈが１０ビット以内であり、内部メモリだけで十
分な場合について説明する。この内部メモリ４には、復
号語Ｄと符号長６が設定されているとし、今ハフマン符
号データ列ｈに‘０１０１０１…’が送られてきたとす
る。このとき、ラッチ回路１はリセットされ、８ビット
全て‘０’が出力される。この８ビットはセレクタ２の
Ａ０端子に入力されるが、この場合はセレクタ２が外部
セレクト信号ｅによりＡ１端子を選択するので、８ビッ
トは無視される。次に、ハフマン符号データ列ｈの先頭
２ビット‘０１’は内部メモリ４に送られ、３ビット目
から８ビットはセレクタ２のＡ１端子を経て内部メモリ
４に送られる。この内部メモリ４はアドレス‘××××
１０１０１０’が入力されるので、復号語Ｄと符号長６
およびフラグ＝１を出力する。これらのデータは各セレ
クタ６，７に送出される。しかるに、フラグ＝１により
内部メモリ４からの出力が有効であることをセレクト信
号生成部８に送出するので、セレクト信号生成部８は内
部メモリ４の出力を選択するように各セレクタ６，７に
セレクト信号を送る。従って、各セレクタ６，７は内部
メモリ４からの復号語Ｄおよび符号長６を出力する。こ
のうち、符号長６はハフマン符号データ列ｈに送られ、
次のハフマン符号データ列ｈの先頭が決まる。

【００２８】図５は図３に示す内部メモリの他の設定例
を表わす図である。図５に示すように、この内部メモリ
４は２ビット単位でハフマン復号が行われる場合であ
り、復号語Ｂと符号長１１が設定されているとする。
今、ハフマン符号データ列‘１１１１１０１０００１
…’が送られてきたとすると、ラッチ回路１はリセット
され、出力８ビットは全て‘０’が出力される。この８
ビットはセレクタ２のＡ０端子を経て内部メモリ４に入
力される。一方、セレクタ２のＡ１にはハフマン符号８
ビットが入力されるが、２ビット毎の追跡の場合はセレ
クタ２がＡ０側を選択するので、無視される。このハフ
マン符号データｈの先頭２ビット‘１１’は内部メモリ
４のアドレスの下位２ビットに送られる。従って、内部
メモリ４はアドレス‘００００００００１１’が入力さ
れ、ポインタ‘０００００００１’とフラグ＝０を出力
する。このポインタ８ビットはラッチ回路１でラッチさ
れ、その出力８ビットに‘０００００００１’を出力す
る。このラッチ１の出力８ビット‘０００００００１’
はセレクタ２のＡ０端子を経て内部メモリ４に入力され
る。

【００２９】次に、ハフマン符号データ列ｈの次の２ビ
ットの‘１１’は内部メモリ４のアドレスの下位２ビッ
トに送られる。すなわち、内部メモリ４には、アドレス
‘０００００００１１１’が入力され、その出力側には
ポインタ‘００００００１０’を出力する。この８ビッ
ト‘００００００１０’はセレクタ２のＡ０端子を経て
内部メモリ４に入力される。また、ハフマン符号データ
列ｈの次の２ビットの‘１０’は内部メモリ４のアドレ
スの下位２ビットに送られるので、内部メモリ４にはア
ドレス‘００００００１００１’が入力され、ポインタ
‘００００００１１’とフラグ＝０を出力する。このポ
インタはラッチ回路１でラッチし、８ビット‘００００
００１１’をセレクタ２に出力する。この８ビット‘０
０００００１１’はセレクタ２のＡ０端子を経て内部メ
モリ４に入力される。

【００３０】更に、ハフマン符号データ列ｈの次の２ビ
ットの‘１０’は内部メモリ４のアドレスの下位２ビッ
トに送られる。すると、内部メモリ４にはアドレス‘０
０００００１１０１’が入力され、ポインタ‘００００
０１００’とフラグ＝０を出力する。このポインタはラ
ッチ回路１でラッチし、‘０００００１００’を出力す
る。この８ビット‘０００００１００’はセレクタ２の
Ａ０端子を経て内部メモリ４に入力される。また、ハフ
マン符号データ列ｈの次の２ビットの‘００’は内部メ
モリ４のアドレスの下位２ビットに送られる。これによ
り、内部メモリ４には、アドレス‘０００００１０００
０’が入力され、ポインタ‘０００００１０１’とフラ
グ＝０を出力する。同様に、ポインタはラッチ回路１で
ラッチされ、‘０００００１０１’をセレクタ２に出力
する。この８ビット‘０００００１０１’はセレクタ２
のＡ０端子を経て内部メモリ４に入力される。

【００３１】次に、ハフマン符号データ列ｈの次の２ビ
ットの‘１×’が内部メモリ４のアドレスの下位２ビッ
トに送られると、内部メモリ４にはアドレス‘００００
０１０１×１’が入力されるので、復号語Ｂと符号長１
１およびフラグ＝１を出力する。この内部メモリ４の出
力は各セレクタ６，７に送られるとともに、フラグ＝１
により内部メモリ４からの出力が有効であることをセレ
クト信号生成部８に送出する。従って、セレクト信号生
成部８は内部メモリ４の出力を選択するように、各セレ
クタ６，７にセレクト信号を送出する。これを受けて各
セレクタ６，７は内部メモリ４からの復号語Ｂおよび符
号長１１を出力する。この符号長１１はハフマン符号デ
ータ列ｈに送られ、次のハフマン符号データ列ｈの先頭
が決まる。

【００３２】次に、内部メモリ４と外部メモリ５の両者
を使用する場合についての回路動作を説明する。まず、
内部メモリ４にはハフマン符号データ列１６ビットの上
位１０ビット以下で復号語をあらわすものについて復号
語および符号長を設定する。また、内部メモリ４の出力
が有効な場合は１、無効な場合は０であるフラグを符号
長５ビット目に設定する。更に、外部メモリ５には、１
１ビット以上１６ビットまでのハフマン符号に対する復
号語および符号長を設定する。但し、符号長の順にハフ
マンコードが割り当ててあれば、１１ビット以上のハフ
マン符号の先頭３ビットは必ず‘１１１’になるので、
外部メモリ５のアドレス入力には先頭３ビットを除いて
入力している。しかも、内部メモリ４には、例えば復号
語Ｄに対するハフマン符号が‘０１０１０１’であれ
ば、アドレス‘××××０１０１０１’の全てに復号語
Ｄと符号長６を設定し、外部メモリ５には、例えば復号
語Ｂに対するハフマン符号が‘１１１１１０１０００
１’であれば、アドレス‘１１０１０００１０…０’か
ら‘１１０１０００１１…１’の全てに復号語Ｂと符号
長１１を設定する。

【００３３】今、ハフマン符号データ列ｈに‘０１０１
０１…’が送られてきたとする。このハフマン符号デー
タ列ｈの先頭４ビット‘０１０１’は内部メモリ４に送
られ、先頭から５ビット目と６ビット目の‘０１’と次
のハフマン符号データｈの先頭４ビットはセレクタ２の
Ａ１端子を経て内部メモリ４に送られる。これら内部メ
モリ４と外部メモリ５の両方を用いるときは、セレクタ
２がＡ１端子を選択するからである。従って、内部メモ
リ４には、アドレス‘××××０１０１０１’が入力さ
れ、復号語Ｄと符号長６およびフラグ＝１が出力され
る。このフラグ＝１により、内部メモリ４からの出力が
有効であることをセレクト信号生成部８に送出する。一
方、外部メモリ５はアドレス入力された１３ビットで得
られるた復号語Ｂと符号長１１を出力する。これら各メ
モリ４，５から得られた復号語と符号長は各セレクタ
６，７に送られが、セレクト信号生成部８はフラグ＝１
により内部メモリ４の出力を選択するように各セレクタ
６，７に選択信号を送る。従って、各セレクタ６，７は
内部メモリ４からの復号語Ｄと符号長６を出力する。こ
の符号長６はハフマン符号データ列ｈに送られ、次のハ
フマン符号データ列ｈの先頭が決まる。以下同様に、こ
の動作を繰り返すことによってハフマン符号が復号され
る。

【００３４】

【発明の効果】以上説明したように、本発明のハフマン
復号回路は１ビット追跡に必要な容量のメモリしか持た
ないので、処理スピードが早く、４ビット復号でもコス
トが安くて済むという効果がある。例えば、メモリ容量
は４ビット追跡の場合の最悪のメモリ容量に比べ１６分
の１で済む。また、本発明において外部メモリを設ける
場合、ユーザがコストとスピードにより各種方式を選択
できるという効果がある。尚、本発明はハフマン符号の
構成条件によっては１ビット単位の低速の復号ツリー追
跡しか出来なくなるが、静止画符号化等で常用されてい
る符号では４ビット追跡出来る範囲に収まっている。

【図面の簡単な説明】

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

【図２】図１に示すメモリの２つの設定例を説明するた
めの図である。

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

【図４】図３に示す内部メモリの一設定例を表わす図で
ある。

【図５】図３に示す内部メモリの他の設定例を表わす図
である。

【図６】従来の一例を示すハフマン復号回路のブロック
図である。

【図７】従来の他の例を示すハフマン復号回路のブロッ
ク図である。

【図８】図７に示す内部メモリの設定例を表わす図であ
る。

【図９】従来のまた別の例を示すハフマン復号回路のブ
ロック図である。

【符号の説明】

１ リセット付ラッチ回路 ２，６，７ セレクタ ３，４ 内部メモリ ５ 外部メモリ ８ セレクト信号生成部 ａ，ｆ 復号語 ｄ，ｇ 符号長 ｃ フラグ ｄ，ｈ ハフマン符号データ ｅ 外部セレクト信号

Claims (3)

【特許請求の範囲】
1. 【請求項１】 復号語を保持しフラグによりリセットさ
   れるラッチ手段と、前記ラッチ手段の出力の一部および
   ハフマン符号データの一部を選択する選択手段と、前記
   ハフマン符号の先頭の１ビットを含む残りのデータと前
   記ラッチ手段の出力の残りのデータと前記選択手段の出
   力データにより前記復号語および符号長と前記フラグを
   出力するメモリ手段とを有することを特徴とするハフマ
   ン復号回路。
2. 【請求項２】 前記選択手段は、セレクタを用いた請求
   項１記載のハフマン復号回路。
3. 【請求項３】 内部メモリおよび外部メモリに対応した
   各セレクタと、前記内部メモリのフラグ出力により前記
   各セレクタを制御するセレクト信号を作成するセレクト
   信号生成部とを設けた請求項１記載のハフマン復号回
   路。