(57)【特許請求の範囲】
【請求項１】
入力するハフマン符号データからビット長が異なる全ての復号候補データを抽出して前記ビット長の昇順で出力する復号候補データ抽出部と、
ビット長毎のハフマン符号における最小値である最小値データを生成する最小値データ生成部と、
前記復号候補データ抽出部により出力された前記各復号候補データ毎に、該復号候補データのビット長に対応する前記最小値データを各復号候補データから各々減算して減算結果を順次出力すると共に、該減算結果が０以上の正の値から負の値に変わった場合にその極性変化を信号出力する減算器と、
前記極性変化が信号出力されたときの当該減算結果よりも１つ前に前記減算器から出力された減算結果により固定長データを生成する固定長データ生成部と
を有し、
前記最小値データ生成部は、
各ビット長毎にビット長が同じハフマン符号の予め計数された個数を格納する個数記憶回路と、
ビット長が最大であるハフマン符号を格納できる容量を有し、入力データを格納するとともに格納データを前記最小値データとして出力するデータ生成処理を実行する最小値データ生成用レジスタと、
前記最小値データ生成用レジスタの出力に対して、前記個数記憶回路から出力された当該個数を加算して、該加算結果を出力する加算処理を実行する最小値データ生成用加算器と、
前記最小値データ生成用加算器の出力の最上位１ビットを捨てると共に最下位１ビットに０を付加してから前記最小値データ生成用レジスタに格納させるシフト出力処理を実行する最小値データ生成用シフト出力回路と
を含み、
前記最小値データ生成用レジスタ、前記最小値データ生成用加算器及び前記最小値データ生成用シフト出力回路は、前記データ生成処理、前記加算処理及び前記シフト出力処理を前記復号候補データの符号ビット数に従って繰り返す
ことを特徴とするハフマン符号復号化装置。
【請求項２】
前記復号候補データ抽出部は、入力するハフマン符号データのビット長を１ビットづつシフトして各復号候補データを出力するシフト出力回路からなることを特徴とする請求項１記載のハフマン符号復号化装置。
【請求項３】
前記固定長データ生成部は、
各ビット長毎にビット長が同じハフマン符号の予め計数された個数を、さらにビット長の昇順で累積加算することにより得られる各ビット長毎の累積個数を格納する累積個数記憶回路と、
前記減算器の減算結果出力と前記累積個数記憶回路の出力を加算して復号候補データとして出力する固定長データ生成用加算器と、
前記固定長データ生成用加算器の加算結果を次の加算結果が入力されるまで格納する固定長データ生成用レジスタと、
前記減算器から極性変化が信号出力された時に、前記固定長データ生成用レジスタに格納されていた復号候補データを出力するバッファと
を備えることを特徴とする請求項１又は２記載のハフマン符号復号化装置。
【請求項４】
前記最小値データ生成部は、
前記個数記憶回路の出力が０個数である場合を検出する個数零検出部を備え、
前記最小値データ生成用シフト出力回路は、前記個数零検出部が０個数を検出した場合には、入力をシフトさせないで出力することを特徴とする請求項１〜３の何れか１項に記載のハフマン符号復号化装置。
【請求項５】
ビット長毎に分別されたハフマン符号中から各ビット長毎の最小値である最小値データを生成するステップと、
ハフマン符号化された入力信号からビット長が異なる各復号候補データを抽出して前記ビット長の昇順で出力するデータ抽出ステップと、
前記データ抽出ステップで出力された前記各復号候補データ毎に、該復号候補データのビット長に対応する前記最小値データを各復号候補データから各々減算して減算結果を順次出力する減算ステップと、
前記減算結果が０以上の正の値から負の値に変わった場合にその極性変化を信号出力するステップと、
前記極性変化が信号出力されたときの減算結果よりも１つ前に前記減算ステップで出力された減算結果により固定長データを生成するステップと
を有し、
前記最小値データを生成するステップでは、
前記復号化に用いる全ハフマン符号から、ビット長が同じハフマン符号の個数を各ビット長毎に計数して予め格納しておき、
前記最小値データは、使用するハフマン符号の最大ビット長を格納できるレジスタの初期値出力に対して、各ビット長毎のハフマン符号の個数を順次加算し、該加算結果を最上位ビットを捨てると共に最下位ビットに０を入力するようにして１ビット分上位桁にシフトしてから前記レジスタに再格納するまでの処理を、復号候補データの符号ビット数に従って繰り返すことにより生成される
ことを特徴とするハフマン符号復号化方法。
【請求項６】
前記固定長データを生成するステップは、
復号化に使用する全てのハフマン符号から、ビット長が同じハフマン符号の個数を各ビット長毎に計数し、さらに前記個数をビット長が昇順となるように累積加算した各ビット長毎の累積個数を予め格納しておき、
前記固定長データは、減算結果の出力と各ビット長毎の累積個数とを加算して保持し、前記極性変化の信号出力により出力することを特徴とする請求項５記載のハフマン符号復号化方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、静止画像を圧縮あるいは伸長して効率良く伝送または記録するために用いられる可変長符号の固定長データ生成部および復号化方法に関し、特に、ＪＰＥＧ（ジョイント・フォトグラフィック・エキスパーツ・グループ）方式の伝送または記録等に用いられる可変長符号であるハフマン符号の固定長データ生成部および復号化方法に関する。
【０００２】
【従来の技術】
従来から、デジタルデータを効率良く伝送または記録するための圧縮と伸張方法が知られている。例えば、固定長のデータからなるデジタルデータを送信または記録する際には、出現確率の高いデータを符号長の短いデータに変換（符号化）する一方で、出現確率の低いデータを符号長の長いデータに符号化（可変長符号化）する。また、その可変長符号化されたデジタルデータを受信または再生する際には、上記のように可変長符号化されたデータを固定長のデータに復号化して使用する。
【０００３】
デジタルデータを圧縮あるいは伸張する符号化データのうち、例えば、上記のように符号長が一定でなく、出現確率に対応して符号長が変わる符号化データを可変長符号と呼んでいる。
【０００４】
可変長符号を用いることにより、デジタルデータを送信する時や記録する時に、上記のようにデジタルデータのデータ量を減少させたり、デジタルデータの符号長の平均値を減少させることができるので、デジタルデータを効率良く伝送または記録することができる。
【０００５】
可変長符号では、代表的なものとしてハフマン符号が良く知られており、静止画像の標準方式であるＪＰＥＧ（ジョイント・フォトグラフィック・エキスパーツ・グループ）方式でも用いられている。
【０００６】
ハフマン符号は、情報源から出力される様々なデジタルデータの各々の生起される確率が不均一であり、且つ、個々のデジタルデータに相関性がない場合に用いられる。また、ハフマン符号は、上記したように可変長符号であり、出現確率の高い（出現頻度の高い）デジタルデータである程、短い符号に変換するので、元の固定長のデータからなるデジタルデータを効率良く圧縮して伝送または記録できるという特長を有している。
【０００７】
ところで、一般的にデジタルデータの伝送や記録はシリアルデータ（連続するデータ）で実施されるため、可変長符号であるハフマン符号を復号化する際には、シリアルデータ中から目的とする符号長のハフマン符号を検出し、そのハフマン符号を固定長のデジタルデータに変換（復号化）する作業が必要になる。
【０００８】
図１６は、従来のハフマン符号を復号化するハフマン符号復号化装置を示すブロック図である。
【０００９】
図１６のハフマン符号復号化装置９１は、直列／並列変換部２、および、復号出力データ部９３からなり、復号データ出力部９３は、さらに固定長データ変換部９４、符号長計数部９５、および、ラッチ部９６から構成される。また、固定長データ変換部９４には、変換データ記憶部９７と符号長データ記憶部９８とを有している。
【００１０】
直列／並列変換部２は、１ビット毎にシリアル形式で入力される可変長のハフマン符号ＨＤ（Ｓ）を、８ビット又は１６ビット等のパラレル形式のデータＨＤ（Ｐ）に変換する。
【００１１】
復号出力データ部９３は、パラレル形式で入力されるハフマン符号を復号データである固定長データＦＤに変換して出力する。
【００１２】
固定長データ変換部９４は、パラレル形式で入力されるハフマン符号を固定長のデータ固定長データＦＤに変換する固定長データ変換部であり、ハフマン符号の符号長を記憶したＲＯＭなどの記憶素子（メモリ）で構成される。
【００１３】
また、固定長データ変換部９４内には、入力する各ハフマン符号に対応させて固定長の符号データ（固定長データ）固定長データＦＤが格納される変換データ記憶部９７と、入力する各ハフマン符号に対応させて各符号長データＬＤが格納される符号長データ記憶部９８とがメモリにより形成されている。
【００１４】
符号長計数部９５は、固定長データ変換部９４からの符号長データＬＤが入力されて、カウンタ値をデクリメントしていきカウンタの値が０になったときに後述するラッチ部９６にラッチ信号ＬＳを出力する。
【００１５】
ラッチ部９６は、固定長データ変換部９４から出力される固定長データＦＤをラッチ信号ＬＳが入力されるまでラッチできるＤフリップフロップ（ＤＦＦ）等からなる。
【００１６】
次に、図１６に示したハフマン符号復号化回路の動作を説明する。
【００１７】
図１６のハフマン符号復号化装置９１に入力される可変長のハフマン符号からなるシリアルデータＨＤ（Ｓ）は、直列／並列変換部２によって、例えば、１６ビットのパラレルデータＨＤ（Ｐ）に変換される。パラレルデータＨＤ（Ｐ）は、次ぎに、各ビット長毎に固定長データ変換部９４内の変換データ記憶部９７と符号長データ記憶部９８に照合されて、変換データ記憶部９７に格納されたハフマン符号とパラレルデータＨＤ（Ｐ）の全て又は抽出された一部分のビット長のデータが一致する場合、そのビット長のハフマン符号に対応する固定長データＦＤ及び符号長データＬＤが生成される。
【００１８】
外部から入力されるスタート信号ＳＳにより符号長計数部９５で発生する第１のラッチ信号ＬＳがラッチ部９６に入力すると、固定長データ変換部９４で生成された固定長データＦＤがラッチ部９６にラッチされる。符号長計数部９５では、入力する符号長データＬＤをデクリメントしていき、その符号長データＬＤの値が”０”になった場合に、第２のラッチ信号ＬＳがラッチ部９６に出力される。
【００１９】
一方、符号長計数部９５における符号長データＬＤのデクリメントに同期されて、直列／並列変換部２では、パラレルデータＨＤ（Ｐ）の内容を上位桁に１ビットづつシフトさせて出力する。従って、第２のラッチ信号が符号長計数部９５から出力される時には、固定長データ変換部９４では次にラッチ部９６に送出するための固定長データＦＤがすでに復号化されているため、第２のラッチ信号により、次の固定長データＦＤをラッチ部９６にラッチさせることができる。以上の動作を繰り返すことにより、連続して入力するハフマン符号からなるシリアルデータＨＤ（Ｓ）を、固定長データＦＤに復号化することができる。
【００２０】
【発明が解決しようとする課題】
しかしながら、前述した従来のハフマン符号復号化装置９１では、ＲＯＭなどの記憶素子（メモリー）からなる固定長データ変換部９４の内部に、例えば、ハフマン符号を固定長データＦＤに変換するための変換テーブルを有する変換データ記憶部９７と、そのハフマン符号に対応させた符号長データＬＤのテーブルを有する符号長データ記憶部９８とを備える必要がある。
【００２１】
復号するハフマン符号が最大１６ビットである場合には、ハフマン符号の種類は２16種になる。ハフマン符号の一意復号可能な符号であるという特性や瞬時復号可能な符号であるという特性を利用して、その種類の数を減らしたとしても、メモリからなる固定長データ変換部９４の記憶容量としてかなり大きなものが必要となる。また、大記憶容量の固定長データ変換部９４を用いて周辺回路を構成する際にも、回路構成が複雑になるという問題があった。
【００２２】
本発明は、上述した如き従来の問題を解決するためになされたものであって、ハフマン符号の復号に必要な記憶容量を減少させることができ、メモリ周辺の回路規模を減少させることができるハフマン符号復号化装置を提供することを目的とする。
【００２３】
【課題を解決するための手段】
上述の目的を達成するため、請求項１に記載した本発明のハフマン符号復号化装置は、入力するハフマン符号データからビット長が異なる全ての復号候補データを抽出して前記ビット長の昇順で出力する復号候補データ抽出部と、ビット長毎のハフマン符号における最小値である最小値データを生成する最小値データ生成部と、前記復号候補データ抽出部により出力された前記各復号候補データ毎に、該復号候補データのビット長に対応する前記最小値データを各復号候補データから各々減算して減算結果を順次出力すると共に、該減算結果が０以上の正の値から負の値に変わった場合にその極性変化を信号出力する減算器と、前記極性変化が信号出力されたときの当該減算結果よりも１つ前に前記減算器から出力された減算結果により固定長データを生成する固定長データ生成部とを有し、前記最小値データ生成部は、各ビット長毎にビット長が同じハフマン符号の予め計数された個数を格納する個数記憶回路と、ビット長が最大であるハフマン符号を格納できる容量を有し、入力データを格納するとともに格納データを前記最小値データとして出力するデータ生成処理を実行する最小値データ生成用レジスタと、前記最小値データ生成用レジスタの出力に対して、前記個数記憶回路から出力された当該個数を加算して、該加算結果を出力する加算処理を実行する最小値データ生成用加算器と、前記最小値データ生成用加算器の出力の最上位１ビットを捨てると共に最下位１ビットに０を付加してから前記最小値データ生成用レジスタに格納させるシフト出力処理を実行する最小値データ生成用シフト出力回路とを含み、前記最小値データ生成用レジスタ、前記最小値データ生成用加算器及び前記最小値データ生成用シフト出力回路は、前記データ生成処理、前記加算処理及び前記シフト出力処理を前記復号候補データの符号ビット数に従って繰り返すことを特徴とする。
【００２４】
請求項２の本発明は、請求項1記載のハフマン符号復号化装置において、前記復号候補データ抽出部は、入力するハフマン符号データのビット長を1ビットづつシフトして各復号候補データを出力するシフト出力回路からなることを特徴とする。
【００２６】
請求項３の本発明は、請求項１又は２記載のハフマン符号復号化装置において、前記固定長データ生成部は、各ビット長毎にビット長が同じハフマン符号の予め計数された個数を、さらにビット長の昇順で累積加算することにより得られる各ビット長毎の累積個数を格納する累積個数記憶回路と、前記減算器の減算結果出力と前記累積個数記憶回路の出力を加算して復号候補データとして出力する固定長データ生成用加算器と、前記固定長データ生成用加算器の加算結果を次の加算結果が入力されるまで格納する固定長データ生成用レジスタと、前記減算器から極性変化が信号出力された時に、前記固定長データ生成用レジスタに格納されていた復号候補データを出力するバッファとを備えることを特徴とする。
【００２７】
請求項４の本発明は、請求項１〜３の何れか１項に記載のハフマン符号復号化装置において、前記最小値データ生成部は、前記個数記憶回路の出力が０個数である場合を検出する個数零検出部を備え、最小値データ生成用シフト出力回路は、前記個数零検出部が０個数を検出した場合には、入力をシフトさせないで出力することを特徴とする。
【００３２】
請求項５に記載した本発明のハフマン符号復号化方法は、ビット長毎に分別されたハフマン符号中から各ビット長毎の最小値である最小値データを生成するステップと、ハフマン符号化された入力信号からビット長が異なる各復号候補データを抽出して前記ビット長の昇順で出力するデータ抽出ステップと、前記データ抽出ステップで出力された前記各復号候補データ毎に、該復号候補データのビット長に対応する前記最小値データを各復号候補データから各々減算して減算結果を順次出力する減算ステップと、前記減算結果が０以上の正の値から負の値に変わった場合にその極性変化を信号出力するステップと、前記極性変化が信号出力されたときの減算結果よりも１つ前に前記減算ステップで出力された減算結果により固定長データを生成するステップとを有し、 前記最小値データを生成するステップでは、前記復号化に用いる全ハフマン符号から、ビット長が同じハフマン符号の個数を各ビット長毎に計数して予め格納しておき、前記最小値データは、使用するハフマン符号の最大ビット長を格納できるレジスタの初期値出力に対して、各ビット長毎のハフマン符号の個数を順次加算し、該加算結果を最上位ビットを捨てると共に最下位ビットに０を入力するようにして１ビット分上位桁にシフトしてから前記レジスタに再格納するまでの処理を、復号候補データの符号ビット数に従って繰り返すことにより生成されることを特徴とする。
【００３４】
請求項６の本発明は、請求項５記載のハフマン符号復号化方法において、前記固定長データを生成するステップは、復号化に使用する全てのハフマン符号から、ビット長が同じハフマン符号の個数を各ビット長毎に計数し、さらに前記個数をビット長が昇順となるように累積加算した各ビット長毎の累積個数を予め格納しておき、前記固定長データは、減算結果の出力と各ビット長毎の累積個数とを加算して保持し、前記極性変化の信号出力により出力することを特徴とする。
【００３５】
【発明の実施の形態】
以下、本発明を図示した実施形態に基づいて説明する。
【００３６】
（第１の実施形態）
図１は、本発明の第１の実施形態のハフマン符号復号化装置の概略構成を示すブロック図である。図２は、図１のハフマン符号復号化装置の内部の復号データ出力部の構成をさらに詳しく示すブロック図である。図３は、（ａ）が図２のシフト出力回路の入出力対応表、（ｂ）が図２の個数記憶回路の入出力対応表、（ｃ）が図２の累積個数記憶回路の入出力対応表である。
【００３７】
図１のハフマン符号復号化装置１は、直列／並列変換部２、および、復号データ出力部３からなり、復号データ出力部３は、さらに復号候補データ抽出部４とデータ生成基本回路部５から構成される。また、データ生成基本回路部５は、さらに最小値データ生成部６と減算器７と固定長データ生成部８により構成される。
【００３８】
直列／並列変換部２は、図１６に示した従来のハフマン符号復号化装置９１中の直列／並列変換部２と同様に、１ビット毎にシリアル形式で入力される可変長のハフマン符号ＨＤ（Ｓ）を、８ビット又は１６ビット等のパラレル形式のデータＨＤ（Ｐ）に変換する。
【００３９】
復号データ出力部３は、パラレル形式で入力されるハフマン符号を復号データである固定長データＦＤに変換して出力するものであり、図１６に示した従来のハフマン符号復号化装置９１中の復号データ出力部９３とは内部構成が異なっている。図１及び図２を用いて、以下に復号データ出力部３の内部構成について説明する。
【００４０】
まず、復号データ出力部３は、復号候補データ抽出部４とデータ生成基本回路部５とから構成される。
【００４１】
復号候補データ抽出部４は、８ビットのパラレル形式で入力されるハフマン符号の先頭ビットから１ビットづつ漸増させた受信データを復号候補データＥＤとして切り出し（抽出し）、後段のデータ生成基本回路部５に供給するものである。本実施形態では、図２に示すように復号候補データ抽出部４はシフト出力回路４１から構成される。パラレルの８ビットハフマン符号データＨＤ（Ｐ）は、シフト出力回路４１の入力に接続され、シフト出力回路４１のシフト信号入力ＳＦ１にはカウンタ６１の出力ＣＳが接続される。シフト出力回路４１の出力ＥＤは、減算器７の一方の入力に接続され、減算器７の他方の入力には、最小値データ生成部６の出力ＭＤが接続される。
【００４２】
データ生成基本回路部５は、最小値データ生成部６と、減算器７、および、固定長データ生成部８とから構成される。
【００４３】
最小値データ生成部６は、受信データから切り出す（抽出する）復号候補データＥＤのビット長、後述する個数記憶回路６２から読み出すハフマン符号の個数を決定するためのビット長、および、後述する累積個数記憶回路８１から読み出すハフマン符号の累積個数出力ＡＮを決定するためのビット長を計数する８ビットのカウンタ６１と、１〜８ビットの各ビット長のハフマン符号の個数を格納できるランダム・アクセス・メモリ（固定長データ記憶部）からなる個数記憶回路６２と、最小値データＭＤを出力する８ビットのレジスタ６３と、レジスタ６３と個数記憶回路６２の各出力を加算して再度レジスタ６３に出力する加算器６４と、加算器６４の出力を再度レジスタ６３に入力させる前に、最上位桁を捨てて最下位桁に０を付加することにより１ビットだけ上位桁にシフトさせるシフト出力回路６５と、カウンタ６１をリセットさせるために不図示の制御装置からのＨアクティブのリセット入力か減算器７からの減算結果極性出力ＰＳのどちらか一方の入力でも入力されればリセット信号を出力するＯＲ回路６７と、レジスタ６３をリセットさせるために不図示の制御装置からのＨアクティブのリセット入力か減算器７からの減算結果極性出力ＰＳのどちらか一方の入力でも入力されればリセット信号を出力するＯＲ回路６８とを有している。
【００４４】
カウンタ６１は”０”〜”７”までインクリメントしていくカウンターである。カウンタ６１にリセット入力があると”０”がセットされる。
【００４５】
また、カウンタ６１の出力ＣＳは、前述したシフト出力回路４１のシフト信号入力ＳＦ１の他に、個数記憶回路６２のアドレス入力Ａ２と、累積個数記憶回路８１のアドレス入力Ａ４とに接続されている。加算器６４の出力ＭＡはシフト出力回路６５の入力に接続されており、シフト出力回路６５により加算器６４の出力ＭＡの最上位１ビットが捨てられ、最下位１ビットに”０”を付加されたデータがレジスタ６３の入力に入力される。レジスタ６３の出力ＭＤは加算器６４の一方の入力と減算器７の前記した他方の入力に接続される。
【００４６】
減算器７は、シフト出力回路４１からの８ビットの復号候補データＥＤと、レジスタ６３からの最小値データＭＤとが入力され、復号候補データＥＤから最小値データＭＤの減算処理を実施し、減算結果データ減算結果出力ＳＤを固定長データ生成部８に出力する。また、本実施形態の減算器７は、減算結果データ減算結果出力ＳＤが０以上の正の値であるか、０未満の負の値であるかを判定し、判定結果が正から負に変わった場合に減算結果極性出力ＰＳを出力する。減算結果極性出力ＰＳは、レジスタ６３を初期値（例えば、「００００００００」）にリセットする信号となり、カウンタ６１を０にリセットする信号になると共に、後述するレジスタ８３に格納した加算結果ＦＡを出力させる信号としても機能する。
【００４７】
減算器７の減算結果極性出力ＰＳは、カウンタ６１のリセット入力Ｒ１とレジスタ６３のリセット入力Ｒ４とバッファ８４の制御信号入力Ｃ１に接続される。減算器７の出力減算結果出力ＳＤは、加算器８２の一方の入力に接続される。加算器８２の出力ＦＡは、レジスタ８３の入力に接続される。
【００４８】
固定長データ生成部８は、１〜８ビットの各ビット長のハフマン符号の累積個数出力ＡＮを格納できるランダム・アクセス・メモリ（固定長データ記憶部）からなる累積個数記憶回路８１と、減算結果データ減算結果出力ＳＤと累積個数出力ＡＮを加算して加算結果データＦＡを後述するレジスタ８３に出力する加算器８２と、加算結果データＦＡを一時的に格納するレジスタ８３と、減算器７からの減算結果極性出力ＰＳにより、レジスタ８３に格納されていた加算結果データＦＡを復号された固定長データＦＤとして出力させるトライステートバッファからなるバッファ８４とを有している。
【００４９】
累積個数記憶回路８１の累積個数データ出力累積個数出力ＡＮは、加算器８２の他方の入力に接続される。累積個数記憶回路８１の出力累積個数出力ＡＮの値と、減算器７の出力減算結果出力ＳＤの値とが加算器８２の各入力に入力されて加算される。加算器８２の加算結果出力ＦＡの値がレジスタ８３に入力されて保持される。レジスタ８３の出力ＦＡは、バッファ８４に入力されており、レジスタ８３に保持された値は、復号候補データ抽出部４や最小値データ生成部６で次の処理が実施される時（次サイクル時）にバッファ８４に出力される。バッファ８４からは、減算結果極性出力ＰＳがバッファ８４の制御信号入力Ｃ１に入力される時のみに、復号された固定長データである固定長データＦＤが出力される。
【００５０】
ここで、本実施形態でハフマン符号を固定長データに復号化する方法について説明する。
【００５１】
図３（ａ）は、図２のシフト出力回路４１のカウンタ出力ＣＳに対応する入出力対応表であり、図３（ｂ）は、図２の個数記憶回路６２のカウンタ出力ＣＳに対応する入出力対応表であり、図３（ｃ）は、図２の累積個数記憶回路８１のカウンタ出力ＣＳに対応する入出力対応表である。
【００５２】
なお、個数記憶回路６２の中には、各ビット長毎のハフマン符号の個数ＮＳがビット長毎に記憶されているものとし、また、累積個数記憶回路８１の中には、各ビット長毎のハフマン符号をビット長の小さいものから昇順に累積したときの各ビット長における累積個数出力ＡＮが記憶されているものとする。
【００５３】
図３に示したように、本実施形態では、シフト出力回路４１、個数記憶回路６２、および、累積個数記憶回路８１からの出力をカウンタ出力ＣＳに対応させることにより、各出力を復号候補データのビット長に対応させている。
【００５４】
図４は、各ビット長毎に最小値データ生成部６で生成される最小値データＭＤ、個数記憶回路６２から出力される個数ＮＳ、および累積個数記憶回路８１から出力される累積個数出力ＡＮの対応表である。なお、本実施形態は８ビットまでのものを示しているが、図４では参考として１６ビットまでの中の９ビット、１５ビットおよび１６ビットについても示た。
【００５５】
まず、図４に示した各ビット長毎のハフマン符号の中で、その生成アルゴリズムにおいて最初に出てくるもの(絶対値が最小のもの)を最小値データ：ＭＤと称することと定義し、図４に例示したように、ビット長毎の各ハフマン符号の個数のテーブルを用意し、さらに、ビット長毎の各ハフマン符号の個数を昇順に累積加算してビット長毎の累積個数のテーブルを用意する。
【００５６】
次に、図４に示した最小値データ、ビット長毎の各ハフマン符号の個数のテーブル、および、ビット長毎の累積個数のテーブルに基づいて、ハフマン符号復号化アルゴリズムの具体例を示す。
【００５７】
図５（ａ）は、本実施形態のハフマン符号復号化装置１に入力される可変長である１６ビットのハフマン符号を使用する場合のシリアル入力データの一例を示し、図５（ｂ）は、図５（ａ）のシリアル入力データを各ビット長毎に抽出した復号候補データＥＤから最小値データＭＤの減算結果出力ＳＤを一覧表にしてその減算結果出力ＳＤの減算結果極性出力ＰＳが正から負に変わる様子を示し、さらに各ビット長に対応する累積個数出力ＡＮを示した一覧表であり、図５（ｃ）は、図５（ｂ）の７ビット長の減算結果出力ＳＤと累積個数出力ＡＮからその加算結果ＦＡが固定長データＦＤとなる様子を示す。
【００５８】
本実施形態では、図５（ａ）に示すようなシリアルな可変長符号入力データＨＤ（Ｓ）が入力されると、復号候補データ抽出部４で図５（ｂ）に示したように復号候補データＥＤが各ビット長毎に抽出される。その各ビット長毎に抽出された復号候補データＥＤは、減算器７で同ビット長の最小値データＭＤが各々減算されて、各ビット長毎の減算結果出力ＳＤが加算器８２に出力される。また、減算器７では、減算結果出力ＳＤが“０”以上の正の値であるか、或いは、“０”未満の負の値であるかを判断し、減算結果が正の値から負の値に変わった場合に、減算結果極性出力ＰＳ（減算結果極性出力信号）を制御出力Ｃ５から出力し、１つ手前の減算結果を用いて固定長データを生成する。なお、本実施形態は８ビットまでのものを示しているが、図５（ｂ）では参考として９ビットについても示した。
【００５９】
図５（ｂ）の場合には、８ビット長の減算時に減算結果出力ＳＤが“０”未満の負の値に変わっているので、図５（ｃ）に示したように、７ビット長の減算結果出力ＳＤ（＝３）を用いると共に、累積個数記憶回路８１内の累積個数出力ＡＮのテーブルから７ビット長の累積個数（＝１５）が読み出されて加算器８２で加算される。加算結果（＝１８）は、レジスタ８３に格納される。ここまでの処理は、減算器７の減算結果極性出力ＰＳに関係無く実施される。
【００６０】
レジスタ８３に格納された加算結果は、次のサイクル時にバッファ８４に出力される。バッファ８４では、その加算結果が入力する際に、減算器７から減算結果極性出力ＰＳが制御入力部Ｃ１に入力していれば、加算結果をそのまま固定長データＦＤとして出力するが、減算結果極性出力ＰＳが制御入力部Ｃ１に入力していなければ、加算結果は破棄される。
【００６１】
すなわち、減算器７の減算結果出力ＳＤが負の値となる８ビット長より１つ前の減算結果が正の値である７ビット長の復号候補データＥＤが、求めるハフマン符号であることになる。また、本実施形態では、求めるハフマン符号を、７ビット長の減算結果（＝３）と、７ビット長の累積個数（＝１５）と、の加算結果（＝１８）により得られるようにした。
【００６２】
図６は、各ビット長毎に図２の最小値データ生成部６の内部処理に用いられる各データ（カウンタ出力ＣＳ、最小値データＭＤ、個数記憶回路６２から出力される個数ＮＳ、加算器６４の出力ＭＡ、および、減算器７の減算結果極性出力ＰＳ）の対応表である。
【００６３】
まず、不図示の制御手段からリセット入力（Ｈアクティブ）が最小値データ生成部６に入力されると、ビット長が“１”の時の動作にリセットされる。リセット入力によりレジスタ６３の８ビットの出力ＭＤは“００００００００”となり、カウンタ６１の出力ＣＳは“００ｈ”となる。すると、個数記憶回路６２の出力ＮＳも“０”（“００００００００”）となるので、加算器６４の出力ＭＡも“００００００００”となる。なお、その際の減算器７の減算結果極性出力ＰＳは“０”である。
【００６４】
シフト出力回路６５では、入力される加算器６４の出力ＭＡの“００００００００”から最上位ビットが抜かれると共に最下位ビットに“０”が入力されることにより、レジスタ６３に出力する値は入力に対して１ビットづつ上位にシフトされる。
【００６５】
次に、ビット長が“２”の時の動作となり、レジスタ６３の出力ＭＤは依然として“００００００００”であるが、カウンタ６１の出力ＣＳは“０１ｈ”となる。また、個数記憶回路６２の出力ＮＳは“２”（“００００００１０”）となるので、加算器６４の出力ＭＡは“００００００１０”となる。また、その際の減算器７の減算結果極性出力は“０”である。
【００６６】
このようにして、図６に示された対応表のビット長が昇順になるように順次最小値データＭＤが生成されて出力されるが、ビット長が“８”になると、減算器７の減算結果が負になり、減算結果極性出力ＰＳが“１”になる。すると、ＯＲ回路６７と６８を介してリセット信号がカウンタ６１とレジスタ６３に入力され、カウンタ出力ＣＳと最小値データＭＤは再びビット長が“１”の時の動作となり、レジスタ６３の出力ＭＤは“００００００００”となり、カウンタ６１の出力ＣＳは“００ｈ”となる。
【００６７】
次に、本実施形態の動作について以下の図７、図８及び図２を用いて説明する。
【００６８】
図７は、ハフマン符号復号化の動作を示すフローチャートである。
【００６９】
ハフマン符号復号化装置１にシリアルの可変長符号データＨＤ（Ｓ）が入力されると（ステップＳ１）、制御装置からＨアクティブのリセット入力がハフマン符号復号化装置１に入力されて、最小値データ生成部５内のカウンタ６１が“０”にリセットされているか否かが判断され（ステップＳ２）、カウンタ６１が“０”にリセットされていれば（ステップＳ２：ＹＥＳ）、次のステップＳ３に進み、カウンタ６１が“０”にリセットされていなければ（ステップＳ２：ＮＯ）、ステップＳ１１カウンタリセットを実施する。
【００７０】
シフト出力回路４１では、シフト制御入力ＳＦ１にカウンタ６１からのカウンタ出力値ＣＳ＝“０”が入力され、図３（ａ）に示したカウンタ出力ＣＳ＝“０”の行に示す抽出出力データＥＤが出力される。可変長符号データＨＤ（Ｓ）から復号候補データＥＤが各ビット長毎に抽出される（ステップＳ３）。一方、最小値データ生成部６では、復号候補データＥＤのビット数に対応させて最小値データＭＤを生成する（ステップＳ４）。減算器７では、各ビット長毎に抽出された各復号候補データから各候補データと同ビット長の最小値データを減算する（ステップＳ５）。
【００７１】
減算器７は、次に減算結果出力ＳＤが０以上の正の値であるか０未満の負の値であるかを判断し（ステップＳ６）、減算結果出力ＳＤが０以上の正の値である場合（ステップＳ６：ＹＥＳ）には、加算器８２で減算結果出力ＳＤと図３（ｃ）に示したカウンタ出力ＣＳ＝“０”の行に示す累積個数出力ＡＮを加算し（ステップＳ７）、加算結果をレジスタ８３に格納し（ステップＳ８）、カウンタ６１の計数値ＮをＮ＝Ｎ＋１として（ステップＳ９）、再び入力データから復号候補データＥＤを抽出するステップＳ３以降の処理が実施される。このステップＳ３〜ステップＳ９の処理は、ステップＳ６で減算結果出力ＳＤが負になるまでカウンタ値を１つづつインクリメントさせながら繰り返される。
【００７２】
一方、減算結果出力ＳＤが０未満の負の値である場合（ステップＳ６：ＮＯ）には、減算結果極性出力ＰＳを出力して、レジスタ８３に格納されていた１つ前（Ｎ＝Ｎ−１）のビット長時の減算結果と累積個数の加算結果をバッファ８４から出力する（ステップＳ１０）。１つ前の加算結果がバッファ８４の出力と共にカウンタ６１のリセットが実施される（ステップＳ１１）。その後、次の復号候補データＥＤが有るか否かが判断され（ステップＳ１２）、次の復号候補データＥＤが有る場合（ステップＳ１２：ＹＥＳ）には、再びステップＳ２から処理を実行し、次の復号候補データＥＤが無い場合（ステップＳ１２：ＮＯ）には、処理を終了する。
【００７３】
また、上記した最小値データ生成部６による最小値データの生成について、更に詳細に動作を説明する。
【００７４】
図８は、図７のステップＳ４に示した最小値データ生成部の動作を更に詳しく示すフローチャートである。
【００７５】
図７のステップＳ２により、カウンタ６１のリセット（”０”であること）は確認されているため、個数記憶回路６２のアドレス入力Ａ２に“０”が入力され、個数記憶回路６２の０アドレスにセットされている値である１ビット長のハフマン符号の個数が個数記憶回路６２の出力データＤ２(ＮＳ)に出力されている。その状態で、まず、レジスタ６３がリセットされて初期値であるか否かの判断が実施される（ステップＳ４１）。レジスタ６３にリセット入力（減算器７からの減算結果極性出力ＰＳ）があると初期値“００００００００”がセットされ、その値が最小値データＭＤとしてレジスタ６３から出力される。レジスタ６３が初期値である場合（ステップＳ４１：ＹＥＳ）には、レジスタ６３の格納内容ＭＤを加算器６４及び減算器７に出力し（ステップＳ４２）、レジスタ６３が初期値でない場合（ステップＳ４１：ＮＯ）には、レジスタ６３をリセットする（ステップＳ４８）。
【００７６】
レジスタ６３から加算器６４に格納内容ＭＤが出力されると共に、個数記憶回路６２から図３（ｂ）に示したカウンタ出力ＣＳ＝“０”の行に示すハフマン符号の個数ＮＳが加算器６４に出力される（ステップＳ４３）。加算器６４では、格納内容ＭＤと個数ＮＳを加算し（ステップＳ４４）、加算結果ＭＡは、シフト出力回路６５に入力される。シフト出力回路６５では、加算結果の最上位ビットを破棄して最下位ビットに“０”を足すことにより、加算結果ＭＡを１ビット上位桁にシフトする（ステップＳ４５）。１ビット上位桁にシフトされた加算結果ＭＡは、次の復号候補データの処理サイクルで再びレジスタ６３に格納される（ステップＳ４６）。
【００７７】
一方、ステップＳ４２では、レジスタ６３の格納内容ＭＤを減算器７にも最小値データＭＤとして出力しており、図７のステップＳ６の判断結果から、減算器７の減算結果が負であるか否かの判断が行われる（ステップＳ４７）。減算器７の減算結果が負である場合（ステップＳ４７：ＹＥＳ）には、目的のハフマン符号は検出されたことになるので、レジスタ６３のリセットを行い（ステップＳ４８）、減算器７の減算結果が負でない場合（ステップＳ４７：ＮＯ）には、図７のステップＳ９でカウンタが１つアップ（インクリメント）された状態となるので、再び、ステップＳ４２のレジスタ６３の格納内容ＭＤを加算器６４及び減算器７に出力する処理以降を実施する。このステップＳ４２〜ステップＳ４７の処理も、図７のステップＳ３〜ステップＳ９の処理と同様に、ステップＳ６で減算結果出力ＳＤが負になるまでカウンタ値を１つづつインクリメントさせながら繰り返される。
【００７８】
レジスタ６３のリセット後、図７のステップＳ１２の次の復号候補データＥＤが有るか否かの判断により、最小値データの生成が終了したか否かの判断が実施され（ステップＳ４９）、最小値データの生成が終了した場合（ステップＳ４９：ＹＥＳ）には、処理を終了し、最小値データの生成が終了しない場合（ステップＳ４９：ＮＯ）には、再びステップＳ４１から処理を実行する。
【００７９】
このようにして、ビット数毎の復号候補データＥＤから最小値データＭＤを減算した減算結果が正から負に変わった時に、その１つ手前のビット数の加算結果をレジスタから出力させることにより、目的とするハフマン符号を検出して復号化した固定長データＦＤとして出力することができる。その際に、必要となるメモリ量は、各ビット長毎のハフマン符号の個数ＮＳおよび累積個数出力ＡＮであり、従来のハフマン符号復号化装置９１のように全てのハフマン符号と固定長符号を対応させてメモリに記憶させる必要が無くなる。また、復号時に符号長データを検出するために、符号長データをメモリに記憶させる必要も無くなる。そのため、本実施形態では、ハフマン符号の復号に必要な記憶容量を減少させることができ、メモリの出力を計数する必要も無くなるので、メモリ周辺の回路規模を減少させることがすることができる。
【００８０】
(第２の実施形態)
上記した第１の実施形態では、最小値データ生成部６において、個数記憶回路６２の出力ＮＳは、例えば、図４のビット長が１ビットの行に示したように、加算されるハフマン符号の個数ＮＳが“０”の場合でも、加算器６４の出力ＭＡを１ビット上位桁にシフトさせてレジスタ６３に入力させていた。すなわち、任意のビット数のハフマン符号の個数が“０”であるかないかに係わらず、レジスタ６３の出力は加算器６４で個数データＮＳと加算されてから１ビット上位桁にシフトされていた。
【００８１】
すると、レジスタ６３から減算器７へ出力される最小値データＭＤは、任意のビット数のハフマン符号の個数が“０”の場合には、そのビット数の復号候補データは減算処理に使用されないことになる。したがって、その最小値データＭＤは、例えば、次のビット数の復号候補データからの減算処理にはそのまま使用することができる。ところが、第１の実施形態では、その最小値データＭＤは使用されないで１ビット上位桁にシフトされてしまうので、復号できないハフマン符号が発生する可能性を有している。
【００８２】
そこで、以下に説明する第２の実施形態では、任意のビット数のハフマン符号の個数が“０”のような特殊な場合には、加算結果に対してシフト出力回路６５で１ビット上位桁にシフトさせないようにして、復号できないハフマン符号が発生しないようにした。
【００８３】
本実施形態が第１の実施形態と異なる主な点は、個数記憶回路６２の出力ＮＳから任意ビット数のハフマン符号の個数が“０”である場合を検出する個数零検出部６６を設けた点と、個数零検出部６６の出力ＺＤにより、任意ビット数のハフマン符号の個数が“０”である場合には、シフト出力回路６５で加算結果ＭＡを１ビット上位桁にシフトする処理を実施しないで出力するようにした点である。
【００８４】
図９は、本発明の第２の実施形態のハフマン符号化装置の最小値データ生成部の構成を示すブロック図である。
【００８５】
図９のハフマン符号復号化装置１０１の最小値データ生成部１０６は、図２に示した第１の実施形態のハフマン符号復号化装置１の最小値データ生成部６に置き替わるものであり、その他の部分については第１の実施形態と同様であるので重複する記載を省略する。また、図９の本実施形態の最小値データ生成部１０６についても、第１の実施形態と同様な機能の部分には、同じ符号を付して重複する記載を省略する。
【００８６】
本実施形態のハフマン符号復号化装置１０１の最小値データ生成部１０６には、個数記憶回路６２の出力ＮＳから個数が“０”の出力を検出するために、８ＮＯＲ回路からなる個数零検出部６６を有している。個数記憶回路６２の出力データＮＳは、加算器６４の一方の入力に接続されると共に個数零検出部６６にも接続される。また、個数零検出部６６の出力ＺＤはシフト出力回路６５のシフト入力Ｓ０に接続されている。そして、他の接続は第１の実施形態と同様に、シフト出力回路６５の出力ＭＳは、レジスタ６３の入力に接続され、レジスタ６３の格納内容ＭＤは加算器６４の一方の入力に接続され、加算器６４の出力ＭＡは、シフト出力回路６５の入力に接続されている。
【００８７】
次に本実施形態の動作について説明する。
【００８８】
本実施形態の動作は、第１の実施形態の動作に個数零検出部６６の動作が追加され、それによりシフト出力回路６５の動作が選択（切り替え）されるようになっている。
【００８９】
個数記憶回路６２の８ビットの出力ＮＳは、加算器６４に入力される際に、同時に個数零検出部６６にも入力される。個数零検出部６６では、８ＮＯＲ回路により出力ＮＳから個数が“０”である出力を検出し、個数が“０”である場合に限って“１”の出力ＺＤを出力する。個数が“０”でない場合には“０”の出力ＺＤを出力する。
【００９０】
個数零検出部６６の出力ＺＤ“１”がシフト出力回路６５に入力されると、シフト出力回路６５は、図１０のＺＤが“１”の行に示したようにシフトしない出力ＭＳの値を出力する。そして、この出力ＭＳがレジスタ６３に入力される。
【００９１】
このように本実施形態では、ハフマン符号の個数が“０”のビット数の場合には、シフト出力回路６５で入力信号をシフトさせないようにし、ハフマン符号の個数が“１”以上のビット数の場合のみに、シフト出力回路６５で入力信号をシフトさせるようにしたので、ビット数が１ビットの場合以外にもハフマン符号の個数が“０”であるハフマン符号についても検出できるので、あらゆる種類のハフマン符号を復号化することができる。
(第３の実施形態)
上記の第１及び第２の実施形態のハフマン符号復号化装置では、図１の復号候補データ抽出部４からデータ生成基本回路部５に入力するハフマン符号の各復号候補データＥＤを固定長データに復号化するには、１ビットからそのハフマン符号の各復号候補データＥＤのビット長分までに相当する処理サイクルが必要であるので、処理時間が長くなる。
【００９２】
そこで、以下に示す第３の実施形態では、並列処理回路を設けることにより、ハフマン符号の各復号候補データＥＤについて、複数のビット長の各候補データＥＤを１サイクル中で並列処理して処理時間を短縮できるようにした。
【００９３】
図１１は、本発明の第３の実施形態のハフマン符号化装置の復号データ出力部の構成を示すブロック図である。
【００９４】
図１１の復号データ出力部２０３は、図２に示した第１の実施形態のハフマン符号復号化装置１の復号データ出力部３に置き替わるものであり、その他の部分については第１の実施形態と同様であるので重複する記載を省略する。
【００９５】
復号データ出力部２０３は、受信信号を１ビットから８ビットのハフマン符号の復号候補データＥＤに切り分けた場合の各々の復号候補データＥＤを並列処理するための回路を有しており、具体的には、入力したパラレルのハフマン符号データＨＤ（Ｐ）を１ビットから８ビットのハフマン符号の復号候補データＥＤに切り分けて、各データ毎に対応する並列回路に出力する復号候補データ抽出部２０４と、１ビットから８ビットのハフマン符号の復号候補データＥＤに各々対応した個別の復号データ（固定長データ）を生成し、各生成データについて、復号候補データＥＤからそのビット長のハフマン符号中の最小値を減算した減算結果極性出力ＰＳの極性変化を判別することにより復号データを検出するデータ生成基本回路部２０５とから構成される。
【００９６】
復号候補データ抽出部２０４は、入力するハフマン符号データの上位ビットからビット長を1ビットづつ漸増させて出力させることにより抽出した各復号候補データを、対応する各減算器２２１〜２２８に向けて並列出力する分岐出力回路である。
【００９７】
データ生成基本回路部２０５は、１ビットから８ビットの復号候補データＥＤに各々対応した最小値データＭＤを格納するレジスタ２１１〜２１８および減算器２２１〜２２８と、２ビットから８ビットの復号候補データＥＤに各々対応した累積個数データＡＮを格納するレジスタ２４２〜２４８、加算器２５２〜２５８およびバッファ２６２〜２６８と、各減算器２２１〜２２８からの極性出力ＰＳにより、どのビットの復号候補データＥＤに対応したバッファ２６２〜２６８の格納内容（復号データ）を出力させるかを判断する復号データ検出回路２３１とからなる。
【００９８】
図２に示した第１の実施形態の復号データ出力部３の最小値データ生成部６は、１サイクル毎に順次各ビット毎の最小値データを出力させるため複雑な構成であったが、本実施形態では各ビット毎に独立した回路構成となっているため、最小値データ生成部としては各ビット毎にレジスタのみの構成となっている。
【００９９】
また、第１の実施形態の復号データ出力部３ではＲＡＭ等により構成された固定長データ生成部８内の累積個数記憶回路８１についても、本実施形態では各ビット毎に独立した回路構成となっているため、やはり各ビット毎にレジスタのみの構成となっている。
【０１００】
また、第１の実施形態の復号データ出力部３では、１サイクル毎に各ビット毎の復号データを演算し、次のビットの減算結果により前のビットの演算結果が目的の復号データであることがわかったので、前のビットの演算結果を次ビットの減算が終了するまで格納するレジスタ８３が必要であったが、本実施形態では、各ビット毎に独立した回路構成となっているため、復号データを格納するための図２に示したレジスタ８３が不要となっている。
【０１０１】
以下、各ビットの復号候補データ毎に個別の本実施形態の回路構成の動作について説明する。
【０１０２】
例えば、復号候補データ抽出部２０４から出力された１ビットのハフマン符号の復号候補データＥＤ１１に対しては、レジスタ２１１と減算器２２１が設けられており、レジスタ２１１に格納された１ビットの最小値データＭＤ１１と１ビットの復号候補データＥＤ１１が減算器２２１に入力される。減算器２２１からの極性出力ＰＳ１１は復号データ検出回路２３１に入力される。１ビットのハフマン符号の個数は“０”であるので減算器２２１からは減算結果は出力されない。
【０１０３】
また、２ビットのハフマン符号の復号候補データＥＤに対しては、レジスタ２１２と減算器２２２に加え、さらに、レジスタ２４２、加算器２５２及びバッファ２６２が設けられており、減算器２２２からの極性出力ＰＳ１２は復号データ検出回路２３１に入力される。減算器２２２の２ビットの減算結果出力ＳＤ１２は、レジスタ２４２に格納された２ビットの累積個数データＡＮ１２と共に加算器２５２に入力される。加算器２５２の加算結果ＦＡ１２には６ビットの“０”が上の桁に付加された加算結果ＦＣ１２となってバッファ２６２に格納される。
【０１０４】
復号データ検出回路２３１は、減算器２２３からの減算結果極性出力ＰＳ１３により２ビットの復号候補データＥＤが復号化するべき信号と判断した場合に、バッファ２６２の制御信号入力部に対して出力指示信号ＤＳ１２を出力し、バッファ２６２からその格納値を出力させる。
【０１０５】
また、３ビットのハフマン符号の復号候補データＥＤに対しては、レジスタ２１３と減算器２２３に加え、さらに、レジスタ２４３、加算器２５３及びバッファ２６３が設けられており、減算器２２３からの極性出力ＰＳ１３は復号データ検出回路２３１に入力される。減算器２２３の３ビットの減算結果出力ＳＤ１３は、レジスタ２４３に格納された３ビットの累積個数データＡＮ１３と共に加算器２５３に入力される。加算器２５３の加算結果ＦＡ１３には５ビットの“０”が上の桁に付加された加算結果ＦＣ１３となってバッファ２６３に格納される。
【０１０６】
復号データ検出回路２３１は、減算器２２４からの減算結果極性出力ＰＳ１４により３ビットの復号候補データＥＤが復号化するべき信号と判断した場合に、バッファ２６３の制御信号入力部に対して出力指示信号ＤＳ１３を出力し、バッファ２６３からその格納値を出力させる。
【０１０７】
同様にして、４ビットのハフマン符号の復号候補データＥＤに対しては、レジスタ２１４と減算器２２４に加え、さらに、レジスタ２４４、加算器２５４及びバッファ２６４が設けられており、減算器２２４からの極性出力ＰＳ１４は復号データ検出回路２３１に入力される。減算器２２４の４ビットの減算結果出力ＳＤ１４は、レジスタ２４４に格納された４ビットの累積個数データＡＮ１４と共に加算器２５４に入力される。加算器２５４の加算結果ＦＡ１４には４ビットの“０”が上の桁に付加された加算結果ＦＣ１４となってバッファ２６４に格納される。
【０１０８】
復号データ検出回路２３１は、減算器２５からの減算結果極性出力ＰＳ１５により４ビットの復号候補データＥＤが復号化するべき信号と判断した場合に、バッファ２６４の制御信号入力部に対して出力指示信号ＤＳ１４を出力し、バッファ２６４からその格納値を出力させる。
【０１０９】
同様にして、５ビットのハフマン符号の復号候補データＥＤに対しては、レジスタ２１５と減算器２２５に加え、さらに、レジスタ２４５、加算器２５５及びバッファ２６５が設けられており、減算器２２５からの極性出力ＰＳ１５は復号データ検出回路２３１に入力される。減算器２２５の５ビットの減算結果出力ＳＤ１５は、レジスタ２４５に格納された５ビットの累積個数データＡＮ１５と共に加算器２５５に入力される。加算器２５５の加算結果ＦＡ１５には３ビットの“０”が上の桁に付加された加算結果ＦＣ１５となってバッファ２６５に格納される。
【０１１０】
復号データ検出回路２３１は、減算器２２６からの減算結果極性出力ＰＳ１６により５ビットの復号候補データＥＤが復号化するべき信号と判断した場合に、バッファ２６５の制御信号入力部に対して出力指示信号ＤＳ１５を出力し、バッファ２６５からその格納値を出力させる。
【０１１１】
同様にして、６ビットのハフマン符号の復号候補データＥＤに対しては、レジスタ２１６と減算器２２６に加え、さらに、レジスタ２４６、加算器２５６及びバッファ２６６が設けられており、減算器２２６からの極性出力ＰＳ１６は復号データ検出回路２３１に入力される。減算器２２６の６ビットの減算結果出力ＳＤ１６は、レジスタ２４６に格納された６ビットの累積個数データＡＮ１６と共に加算器２５６に入力される。加算器２５６の加算結果ＦＡ１６には２ビットの“０”が上の桁に付加された加算結果ＦＣ１６となってバッファ２６６に格納される。
【０１１２】
復号データ検出回路２３１は、減算器２２７からの減算結果極性出力ＰＳ１７により６ビットの復号候補データＥＤが復号化するべき信号と判断した場合に、バッファ２６６の制御信号入力部に対して出力指示信号ＤＳ１６を出力し、バッファ２６６からその格納値を出力させる。
【０１１３】
同様にして、７ビットのハフマン符号の復号候補データＥＤに対しては、レジスタ２１７と減算器２２７に加え、さらに、レジスタ２４７、加算器２５７及びバッファ２６７が設けられており、減算器２２７からの極性出力ＰＳ１７は復号データ検出回路２３１に入力される。減算器２２７の７ビットの減算結果出力ＳＤ１７は、レジスタ２４７に格納された７ビットの累積個数データＡＮ１７と共に加算器２５７に入力される。加算器２５７の加算結果ＦＡ１７には１ビットの“０”が上の桁に付加された加算結果ＦＣ１７となってバッファ２６７に格納される。
【０１１４】
復号データ検出回路２３１は、減算器２２８からの減算結果極性出力ＰＳ１８により７ビットの復号候補データＥＤが復号化するべき信号と判断した場合に、バッファ２６７の制御信号入力部に対して出力指示信号ＤＳ１７を出力し、バッファ２６７からその格納値を出力させる。
【０１１５】
同様にして、８ビットのハフマン符号の復号候補データＥＤに対しては、レジスタ２１８と減算器２２８に加え、さらに、レジスタ２４８、加算器２５８及びバッファ２６８が設けられており、減算器２２８からの極性出力ＰＳ１８は復号データ検出回路２３１に入力される。減算器２２８の８ビットの減算結果出力ＳＤ１８は、レジスタ２４８に格納された８ビットの累積個数データＡＮ１８と共に加算器２５８に入力される。加算器２５８の加算結果ＦＡ１８（ＦＣ１８）はそのままバッファ２６８に格納される。
【０１１６】
復号データ検出回路２３１は、減算器２２１〜２２８から全く減算結果極性出力ＰＳ１１〜ＰＳ１８が出力されず、８ビットの復号候補データＥＤが復号化するべき信号と判断した場合に、バッファ２６８の制御信号入力部に対して出力指示信号ＤＳ１８を出力し、バッファ２６８からその格納値を出力させる。
【０１１７】
このように本実施形態では、各ビットの復号候補データ毎に個別の並列処理回路を設け、復号データ検出回路２３１により全ての入力データから復号化するべき信号と判断された復号候補データＥＤに対応するバッファからの出力が、復号データ出力部２０３から８ビットの固定長データ（復号データ）ＦＤとして出力されるようにしたので、ハフマン符号の各復号候補データＥＤについて、複数のビット長の各候補データＥＤを１サイクル中で並列処理することにより処理時間を短縮することができる。
(第４の実施形態)
上記の第３の実施形態のハフマン符号復号化装置では、各ビット毎の減算器２２１〜２２８の減算結果出力ＳＤ１２〜ＳＤ１８は加算器２５２〜２５８に入力され、加算器２５２〜２５８では、レジスタ２４２〜２４８からの入力と減算結果出力ＳＤ１２〜ＳＤ１８とが加算されて加算結果ＦＡ１２〜ＦＡ１８として出力され、加算結果ＦＡ１２〜ＦＡ１８は、８ビットデータにするために各々上位桁に必要となる桁分の“０”が付加された加算結果ＦＣ１２〜ＦＣ１８としてバッファ２６２〜２６８に入力される。
【０１１８】
その場合、各ビット長毎の固定長データ（復号データ）は、予め設定されている値（１つ以上の設定値中から減算結果出力ＳＤ１２〜ＳＤ１８により決定されるの１つの値）が出力されることになる。この出力は、加算処理してから上位桁に必要となる桁分の“０”を付加するものではなく、予め記憶部に格納しておいた値を減算結果出力ＳＤ１２〜ＳＤ１８により読み出したものである。このことから、第３の実施形態の加算処理してから上位桁に必要となる桁分の“０”が付加する処理よりも、記憶素子中のデータを読み出すのみのほうが処理が簡潔であるため処理時間を短縮できると考えられる。
【０１１９】
そこで、以下に示す第４の実施形態では、第３の実施形態の加算器２５２〜２５８とレジスタ２４２〜２４８に代えて各ビット用の固定長データ記憶部３１２〜３１８を設けることにより、より処理時間を短縮できるようにした。
【０１２０】
図１２は、本発明の第４の実施形態のハフマン符号化装置の復号データ出力部の構成を示すブロック図である。
【０１２１】
図１２の復号データ出力部３０３は、復号候補データ抽出部２０４とデータ生成基本部３０５とから構成され、上記したように、第３の実施形態の加算器２５２〜２５８とレジスタ２４２〜２４８に代えて各ビット用の固定長データ記憶部３１２〜３１８を設け、復号データ検出回路２３１の検出結果を固定長データ記憶部３１２〜３１８に入力するようにした点以外は、第３の実施形態と同様である。また、図１２中の図１１と同様な機能の部分には同じ符号を付与して、重複する部分の記載を省略する。
【０１２２】
ここで、固定長データ記憶部３１２〜３１８の代表として、固定長データ記憶部３１２に予め格納されている値について図を用いて説明する。
【０１２３】
図１３は、２ビット用固定長データ記憶部３１２に予め格納された値を示す図である。
【０１２４】
図１３に示されたように、固定長データ記憶部３１２の中には、アドレス入力となる減算結果ＳＤ１２が０の場合に出力される２ビット長の累積個数（ＡＮ＝２）に“０”を足した数値である“２”、減算結果ＳＤ１２が１の場合に出力されるＡＮ＝２に“１”を足した数値である“３”、減算結果ＳＤ１２が２の場合に出力されるＡＮ＝２に“２”を足した数値である“４”、というように０から１づつ漸増した数字を順に足したものを、そのビット長（この場合２ビット長）のハフマンデータの個数（２個）分だけ少ないほうから予め記憶される。
【０１２５】
固定長データ記憶部３１２は、２ビットの復号候補データから最小値データを減算した減算結果ＳＤ１２が減算器２２２からアドレス入力として入力されると共に、復号データ検出回路２３１の検出結果が２ビットとなった場合には、その検出結果の出力指示信号ＤＳ１２が入力される。復号データ検出回路２３１の検出結果が２ビットでない場合には、その検出結果の出力指示信号ＤＳ１３〜ＤＳ１８は、固定長データ記憶部３１２に入力されない。
【０１２６】
復号データ検出回路２３１の出力指示信号ＤＳ１２は、固定長データ記憶部３１２の、例えば、リードイネーブル入力リセット入力（ＲＥ）に入力される。すると、減算結果ＳＤ１２の入力が有効になり、例えば、図１３中の固定長データ記憶部３１２に予め格納された値から選択された値が固定長データＦＣ１２として出力される。
【０１２７】
固定長データ記憶部３１２から出力される固定長データＦＣ１２は、バッファ２６２に入力され、またバッファ２６２から出力指示信号ＤＳ１２により出力された値が固定長データＦＤとなる。
【０１２８】
３ビット長の場合には、上記の減算器２２２、２ビット用固定長データ記憶部３１２およびバッファ２６２が、減算器２２３、３ビット用固定長データ記憶部３１３およびバッファ２６３になり、出力指示信号ＤＳ１２が出力指示信号がＤＳ１３になり、累積個数が３ビット長用のＡＮ＝３になり、固定長データ記憶部３１３に予め格納された値から選択された値が固定長データＦＣ１３として出力される。固定長データＦＣ１３は、バッファ２６３に入力され、またバッファ２６３から出力指示信号ＤＳ１３により出力された値が固定長データＦＤとなる。
【０１２９】
４ビット長の場合には、４ビット用の減算器２２４、４ビット用固定長データ記憶部３１４およびバッファ２６４になり、出力指示信号がＤＳ１４になり、累積個数が４ビット長用のＡＮ＝６になり、固定長データ記憶部３１４に予め格納された値から選択された値が固定長データＦＣ１４として出力される。固定長データＦＣ１４は、バッファ２６４に入力され、またバッファ２６４から出力指示信号ＤＳ１４により出力された値が固定長データＦＤとなる。
【０１３０】
以下同様に、５ビット長の場合には、５ビット用の減算器２２５、５ビット用固定長データ記憶部３１５およびバッファ２６５になり、出力指示信号がＤＳ１５になり、累積個数が５ビット長用のＡＮ＝９になり、固定長データ記憶部３１５に予め格納された値から選択された値が固定長データＦＣ１５として出力される。固定長データＦＣ１５は、バッファ２６５に入力され、またバッファ２６５から出力指示信号ＤＳ１５により出力された値が固定長データＦＤとなる。
【０１３１】
同様に、６ビット長の場合には、６ビット用の減算器２２６、６ビット用固定長データ記憶部３１６およびバッファ２６６になり、出力指示信号がＤＳ１６になり、累積個数が６ビット長用のＡＮ＝１１になり、固定長データ記憶部３１６に予め格納された値から選択された値が固定長データＦＣ１６として出力される。固定長データＦＣ１６は、バッファ２６６に入力され、またバッファ２６６から出力指示信号ＤＳ１６により出力された値が固定長データＦＤとなる。
【０１３２】
同様に、７ビット長の場合には、７ビット用の減算器２２７、７ビット用固定長データ記憶部３１７およびバッファ２６７になり、出力指示信号がＤＳ１７になり、累積個数が７ビット長用のＡＮ＝１５になり、固定長データ記憶部３１７に予め格納された値から選択された値が固定長データＦＣ１７として出力される。固定長データＦＣ１７は、バッファ２６７に入力され、またバッファ２６７から出力指示信号ＤＳ１７により出力された値が固定長データＦＤとなる。
【０１３３】
同様に、８ビット長の場合には、８ビット用の減算器２２８、８ビット用固定長データ記憶部３１８およびバッファ２６８になり、出力指示信号がＤＳ１８になり、累積個数が８ビット長用のＡＮ＝１８になり、固定長データ記憶部３１８に予め格納された値から選択された値が固定長データＦＣ１８として出力される。固定長データＦＣ１８は、バッファ２６８に入力され、またバッファ２６８から出力指示信号ＤＳ１８により出力された値が固定長データＦＤとなる。
【０１３４】
このように本実施形態では、第３の実施形態の各ビット用に個別の構成に各ビット用固定長データ記憶部３１２〜３１８を設けたので、より処理時間を短縮することができる。
(第５の実施形態)
上記の第４の実施形態のハフマン符号復号化装置では、各ビット毎の減算器２２１〜２２８の減算結果極性出力ＰＳ１１〜ＰＳ１８は復号データ検出回路２３１に入力され、復号データ検出回路２３１から各ビット用固定長データ記憶部３１２〜３１８、バッファ２６２〜２６８に出力指示信号ＤＳ１２〜ＤＳ１８出力されている。
【０１３５】
その場合、復号データ検出回路２３１では、減算結果極性出力ＰＳ１１〜ＰＳ１８中から減算結果が正から負に変わったビット長よりも１つ少ないビット長用の固定長データ記憶部３１２〜３１８およびバッファ２６２〜２６８に対して、出力指示信号ＤＳ１２〜ＤＳ１８を出力させているので、例えば、減算結果極性出力ＰＳ１２〜ＰＳ１８を直接に１ビット少ない固定長データ記憶部３１１〜３１７およびバッファ２６１〜２６７の各々対応する素子に入力させると共に、減算結果極性出力ＰＳ１２〜ＰＳ１８が全て無い場合には固定長データ記憶部３１８およびバッファ２６８に入力させるようにすれば、復号データ検出回路２３１を削除することができる。
【０１３６】
その場合には、１ビット用の固定長データ記憶部３１１、バッファ２６１、および、８ビット用のＮＯＲ素子等からなる個数零検出部４１１が必要になるが、復号データ検出回路２３１を用いた場合よりも、各減算結果極性出力ＰＳ１１〜ＰＳ１８により減算結果が正から負に変わったビット長よりも１つ少ないビット長を判断する判断時間が省略することができるので、より処理時間を短縮させることができると考えられる。
【０１３７】
そこで、以下に示す第５の実施形態では、第４の実施形態の復号データ検出回路２３１を削除して、減算結果極性出力ＰＳ１２〜ＰＳ１８を直接に１ビット少ない固定長データ記憶部３１１〜３１７およびバッファ２６１〜２６７の各々対応する素子に入力させる等により、より処理時間を短縮できるようにした。
【０１３８】
図１４は、本発明の第５の実施形態のハフマン符号化装置の復号データ出力部の構成を示すブロック図である。
【０１３９】
図１４の復号データ出力部４０３は、復号候補データ抽出部２０４とデータ生成基本部４０５とから構成され、上記したように、第４の実施形態の復号データ検出回路２３１を削除して、減算結果極性出力ＰＳ１２〜ＰＳ１８を直接に１ビット少ない固定長データ記憶部３１１〜３１７およびバッファ２６１〜２６７の各々対応する素子に入力させると共に、減算結果極性出力ＰＳ１２〜ＰＳ１８が全て無い場合には固定長データ記憶部３１８およびバッファ２６８に入力させるようにＮＯＲ素子等からなる個数零検出部４１１、及び、１ビット用の固定長データ記憶部３１１、バッファ２６１を設けた点以外は、第４の実施形態と同様である。また、図１４中の図１２と同様な機能の部分には同じ符号を付与して、重複する部分の記載を省略する。
【０１４０】
本実施形態では、例えば１ビット長の復号候補データ用の回路については、減算結果極性出力ＰＳ１２が出力指示信号として固定長データ記憶部３１１のリセット入力ＲＥに入力されると共に、バッファ２６１の制御入力にも入力される。また、減算結果極性出力ＰＳ１２は、さらに、個数零検出部４１１にも入力される。
【０１４１】
固定長データ記憶部３１１のリセット入力ＲＥに減算結果極性出力ＰＳ１２が入力されると減算結果ＳＤ１１の入力が有効になり、固定長データ記憶部３１１に予め格納された値から選択された値が固定長データＦＣ１１として出力されてバッファ２６１に入力され、またバッファ２６１から減算結果極性出力ＰＳ１２により出力された値が固定長データＦＤとなる。
【０１４２】
同様に２ビット長の復号候補データ用の回路については、減算結果極性出力ＰＳ１３が出力指示信号として固定長データ記憶部３１２のリセット入力ＲＥに入力されると共に、バッファ２６２の制御入力にも入力される。また、減算結果極性出力ＰＳ１３は、さらに、個数零検出部４１１にも入力される。
【０１４３】
固定長データ記憶部３１２のリセット入力ＲＥに減算結果極性出力ＰＳ１３が入力されると減算結果ＳＤ１２の入力が有効になり、固定長データ記憶部３１２に予め格納された値から選択された値が固定長データＦＣ１２として出力されてバッファ２６２に入力され、またバッファ２６２から減算結果極性出力ＰＳ１３により出力された値が固定長データＦＤとなる。
【０１４４】
同様に３ビット長の復号候補データ用の回路については、減算結果極性出力ＰＳ１４が出力指示信号として固定長データ記憶部３１３のリセット入力ＲＥに入力されると共に、バッファ２６３の制御入力にも入力される。また、減算結果極性出力ＰＳ１４は、さらに、個数零検出部４１１にも入力される。
【０１４５】
固定長データ記憶部３１３のリセット入力ＲＥに減算結果極性出力ＰＳ１４が入力されると減算結果ＳＤ１３の入力が有効になり、固定長データ記憶部３１３に予め格納された値から選択された値が固定長データＦＣ１３として出力されてバッファ２６３に入力され、またバッファ２６３から減算結果極性出力ＰＳ１４により出力された値が固定長データＦＤとなる。
【０１４６】
同様に４ビット長の復号候補データ用の回路については、減算結果極性出力ＰＳ１５が出力指示信号として固定長データ記憶部３１４のリセット入力ＲＥに入力されると共に、バッファ２６４の制御入力にも入力される。また、減算結果極性出力ＰＳ１５は、さらに、個数零検出部４１１にも入力される。
【０１４７】
固定長データ記憶部３１４のリセット入力ＲＥに減算結果極性出力ＰＳ１５が入力されると減算結果ＳＤ１４の入力が有効になり、固定長データ記憶部３１４に予め格納された値から選択された値が固定長データＦＣ１４として出力されてバッファ２６４に入力され、またバッファ２６４から減算結果極性出力ＰＳ１５により出力された値が固定長データＦＤとなる。
【０１４８】
同様に５ビット長の復号候補データ用の回路については、減算結果極性出力ＰＳ１６が出力指示信号として固定長データ記憶部３１５のリセット入力ＲＥに入力されると共に、バッファ２６５の制御入力にも入力される。また、減算結果極性出力ＰＳ１６は、さらに、個数零検出部４１１にも入力される。
【０１４９】
固定長データ記憶部３１５のリセット入力ＲＥに減算結果極性出力ＰＳ１６が入力されると減算結果ＳＤ１５の入力が有効になり、固定長データ記憶部３１５に予め格納された値から選択された値が固定長データＦＣ１５として出力されてバッファ２６５に入力され、またバッファ２６５から減算結果極性出力ＰＳ１６により出力された値が固定長データＦＤとなる。
【０１５０】
同様に６ビット長の復号候補データ用の回路については、減算結果極性出力ＰＳ１７が出力指示信号として固定長データ記憶部３１６のリセット入力ＲＥに入力されると共に、バッファ２６６の制御入力にも入力される。また、減算結果極性出力ＰＳ１７は、さらに、個数零検出部４１１にも入力される。
【０１５１】
固定長データ記憶部３１６のリセット入力ＲＥに減算結果極性出力ＰＳ１７が入力されると減算結果ＳＤ１６の入力が有効になり、固定長データ記憶部３１６に予め格納された値から選択された値が固定長データＦＣ１６として出力されてバッファ２６６に入力され、またバッファ２６６から減算結果極性出力ＰＳ１７により出力された値が固定長データＦＤとなる。
【０１５２】
同様に７ビット長の復号候補データ用の回路については、減算結果極性出力ＰＳ１８が出力指示信号として固定長データ記憶部３１７のリセット入力ＲＥに入力されると共に、バッファ２６７の制御入力にも入力される。また、減算結果極性出力ＰＳ１８は、さらに、個数零検出部４１１にも入力される。
【０１５３】
固定長データ記憶部３１７のリセット入力ＲＥに減算結果極性出力ＰＳ１８が入力されると減算結果ＳＤ１７の入力が有効になり、固定長データ記憶部３１７に予め格納された値から選択された値が固定長データＦＣ１７として出力されてバッファ２６７に入力され、またバッファ２６７から減算結果極性出力ＰＳ１８により出力された値が固定長データＦＤとなる。
【０１５４】
８ビット長の復号候補データ用の回路については、上記した７ビット長までと異なり、減算結果極性出力ＰＳ１２〜ＰＳ１８が入力された個数零検出部４１１の出力が、固定長データ記憶部３１８のリセット入力ＲＥに入力されると共に、バッファ２６８の制御入力にも入力される。
【０１５５】
固定長データ記憶部３１８のリセット入力ＲＥに個数零検出部４１１の出力ＰＳ１９が入力されると減算結果ＳＤ１８の入力が有効になり、固定長データ記憶部３１８に予め格納された値から選択された値が固定長データＦＣ１８として出力されてバッファ２６８に入力され、またバッファ２６８から出力ＰＳ１９により出力された値が固定長データＦＤとなる。
【０１５６】
このように本実施形態では、第４の実施形態の復号データ検出回路２３１を削除してもデータ生成処理をできるようにしたので、回路規模を小さくするとともに、より処理時間を短縮することができる。
(第６の実施形態)
上記の第３の実施形態のハフマン符号復号化装置では、復号候補データ抽出部２０４は、入力するハフマン符号データの上位ビットからビット長を1ビットづつ漸増させて出力させることにより抽出した各復号候補データを、対応する各減算器２２１〜２２８に向けて分岐させた出力をそのまま並列出力していた。
【０１５７】
しかし、その場合、入力信号から単純に上位から切り出し出力を各減算器２２１〜２２８に向けて出力すると、ハフマン符号の構成上の特性から、存在可能性が全く無いハフマン符号の復号候補データについてもそのまま出力されるので、データ生成基本回路部２０５における固定長データＦＤのデータ生成処理に無駄が生じていた。この無駄な処理により処理時間が増加していた。
【０１５８】
そこで、以下に示す第６の実施形態では、第３の実施形態の復号候補データ抽出部２０４からデータ生成基本回路部２０５に出力される各復号候補データを選択することにより、データ生成基本回路部２０５における処理時間をより短縮できるようにした。
【０１５９】
図１５は、本発明の第６の実施形態のハフマン符号化装置の復号データ出力部の構成を示すブロック図である。
【０１６０】
図１５の復号データ出力部５０３は、復号候補データ抽出部２０４と、データ生成基本部４０５に加えて、復号候補データ抽出部２０４からデータ生成基本部４０５に出力される復号候補データを選択するデータ選択回路部５０１を有している。
【０１６１】
データ選択回路部５０１は、各ビット数の復号候補データ毎に１個づつ割り当てられたＡＮＤ回路であるＡＮＤ５２１〜５２８と、選択用のＡＮＤ回路であるＡＮＤ５１２、５１４とから構成される。
【０１６２】
復号候補データ抽出部２０４から出力されるパラレル８ビットのハフマン符号のデータ入力ＨＤ（Ｐ）における上位１ビットのデータＥＤ１１は、データ選択回路部５０１内の３入力１出力であるＡＮＤ５２１の上位１入力に入力される。同様にしてデータ入力ＨＤ（Ｐ）における上位２ビットのデータＥＤ１２は、データ選択回路部５０１内の４入力２出力であるＡＮＤ５２２の上位２入力に入力される。また、データＥＤ１２は、２入力１出力であるＡＮＤ５１２にも入力される。データ入力ＨＤ（Ｐ）における上位３ビットのデータＥＤ１３は、データ選択回路部５０１内の５入力３出力であるＡＮＤ５２３の上位３入力に入力される。同様にしてデータ入力ＨＤ（Ｐ）における上位４ビットのデータＥＤ１４は、データ選択回路部５０１内の６入力４出力であるＡＮＤ５２４の上位４入力に入力される。また、データＥＤ１４は、４入力１出力であるＡＮＤ５１４にも入力される。データ入力ＨＤ（Ｐ）における上位５ビットのデータＥＤ１５は、データ選択回路部５０１内の７入力５出力であるＡＮＤ５２５の上位５入力に入力される。同様にしてデータ入力ＨＤ（Ｐ）における上位６ビットのデータＥＤ１６は、データ選択回路部５０１内の８入力６出力であるＡＮＤ５２６の上位６入力に入力される。同様にしてデータ入力ＨＤ（Ｐ）における上位７ビットのデータＥＤ１７は、データ選択回路部５０１内の９入力７出力であるＡＮＤ５２７の上位７入力に入力される。同様にしてデータ入力ＨＤ（Ｐ）における８ビットのデータＥＤ１８は、データ選択回路部５０１内の１０入力８出力であるＡＮＤ５２８の上位８入力に入力される。
【０１６３】
ＡＮＤ５１２の出力ＳＬ１は、８分岐されてＡＮＤ５２１〜ＡＮＤ５２８の各下位２入力の何れかに入力されるが、ＡＮＤ５２１とＡＮＤ５２２については、出力ＳＬ１が反転されて入力される。また、ＡＮＤ５１４の出力ＳＬ２も、８分岐されてＡＮＤ５２１〜ＡＮＤ５２８の各下位２入力の何れかに入力されるが、ＡＮＤ５２３とＡＮＤ５２４については、出力ＳＬ２が反転されて入力される。
【０１６４】
ＡＮＤ５２１は、上位１ビットのデータＥＤ１１、出力ＳＬ１の反転入力、出力ＳＬ２の３入力が全て入力された場合に、上位１ビットのデータＥＤ１１Ｓを出力する。ＡＮＤ５２２は、上位２ビットのデータＥＤ１２、出力ＳＬ１の反転入力、出力ＳＬ２の４入力が全て入力された場合に、上位２ビットのデータＥＤ１２Ｓを出力する。ＡＮＤ５２３は、上位３ビットのデータＥＤ１３、出力ＳＬ１、出力ＳＬ２の反転入力の５入力が全て入力された場合に、上位３ビットのデータＥＤ１３Ｓを出力する。ＡＮＤ５２４は、上位４ビットのデータＥＤ１４、出力ＳＬ１、出力ＳＬ２の反転入力の６入力が全て入力された場合に、上位４ビットのデータＥＤ１４Ｓを出力する。ＡＮＤ５２５は、上位５ビットのデータＥＤ１５、出力ＳＬ１、出力ＳＬ２の７入力が全て入力された場合に、上位５ビットのデータＥＤ１５Ｓを出力する。ＡＮＤ５２６は、上位６ビットのデータＥＤ１６、出力ＳＬ１、出力ＳＬ２の８入力が全て入力された場合に、上位６ビットのデータＥＤ１６Ｓを出力する。ＡＮＤ５２７は、上位７ビットのデータＥＤ１７、出力ＳＬ１、出力ＳＬ２の９入力が全て入力された場合に、上位７ビットのデータＥＤ１７Ｓを出力する。ＡＮＤ５２８は、上位８ビットのデータＥＤ１８、出力ＳＬ１、出力ＳＬ２の１０入力が全て入力された場合に、上位８ビットのデータＥＤ１８Ｓを出力する。
【０１６５】
ＡＮＤ５２１〜５２８から出力される各データＥＤ１１Ｓ〜ＥＤ１８Ｓは、図１１に示したデータ生成基本回路部２０５中の各復号候補データのビット数毎に対応する減算器２２１〜２２８に入力される。
【０１６６】
次に、図１５に示すデータ選択回路部５０１の動作について説明する。
【０１６７】
復号候補データ抽出部２０４から出力される各ビット長のハフマン符号の各復号候補データ中には、ハフマン符号の性質上から存在する可能性の全くないハフマン符号の復号候補データも出力される。データ選択回路部５０１は、この存在可能性の全くない復号候補データについて、後段のデータ生成基本回路部２０５に入力させないようにして、データ生成基本回路部２０５に無駄な処理をさせないようにした回路である。
【０１６８】
例えば、まず、復号候補データ抽出部２０４から出力される復号候補データの上位２ビットのデータＥＤ１２が“１１”である場合には、ハフマン符号の性質上から３ビット長以上のハフマン符号と考えられ、１ビット長と２ビット長のハフマン符号の復号候補データとは考えられない。そこで、１ビット長と２ビット長のＡＮＤ５２１およびＡＮＤ５２２にＡＮＤ５１２の出力ＳＬ１を反転させて入力させることにより、ＡＮＤ５２１およびＡＮＤ５２２はＡＮＤ条件が揃わないことになり、その出力データＥＤ１１Ｓ、ＥＤ１２Ｓは“０”、“００”に固定される。
【０１６９】
また、逆に、復号候補データの上位２ビットが”１１”以外である場合には、ハフマン符号の性質上から３ビット長未満のハフマン符号と考えられ、３ビット長以上のハフマン符号の復号候補データとは考えられないため、ＡＮＤ５２３〜５２８にＡＮＤ５１２の出力ＳＬ１を入力させることにより、ＡＮＤ５２３〜５２８はＡＮＤ条件が揃わないことになり、その出力データＥＤ１３Ｓ〜ＥＤ１８Ｓは“０００”〜“００００００００”に固定される。
【０１７０】
次に、復号候補データの上位４ビットが”１１１１”である場合には、ハフマン符号の性質上から５ビット長以上のハフマン符号と考えられ、１ビット長〜４ビット長のハフマン符号の復号候補データとは考えられない。そこで、１ビット長〜４ビット長のＡＮＤ５２１〜ＡＮＤ５２４にＡＮＤ５１４の出力ＳＬ２を反転させて入力させることにより、ＡＮＤ５２１〜ＡＮＤ５２４はＡＮＤ条件が揃わないことになり、その出力データＥＤ１１Ｓ〜ＥＤ１４Ｓは“０”、“００”、“０００”、“００００”に固定される。ところが、ＡＮＤ５２１およびＡＮＤ５２２については、ＡＮＤ５１２の出力ＳＬ１が反転させて入力されるようになっていることから、ＡＮＤ５２３およびＡＮＤ５２４についてのみ、ＡＮＤ５１４の出力ＳＬ２を反転させて入力させてやれば良い。
【０１７１】
また、逆に、復号候補データの上位４ビットが”１１１１”以外である場合には、ハフマン符号の性質上から５ビット長未満のハフマン符号と考えられ、５ビット長以上のハフマン符号の復号候補データとは考えられないため、ＡＮＤ５２５〜５２８にＡＮＤ５１４の出力ＳＬ２を入力させることにより、ＡＮＤ５２５〜５２８はＡＮＤ条件が揃わないことになり、その出力データＥＤ１５Ｓ〜ＥＤ１８Ｓは“０００００”〜“００００００００”に固定される。
【０１７２】
上記のようにデータ選択回路５０１からデータ生成基本回路部２０５に入力された出力データED１１〜ED１８は、第３の実施形態と同様に処理されるので、以降の重複する動作については記載を省略する。
【０１７３】
このように本実施形態では、ハフマン符号の性質を利用しており、第３の実施形態における復号候補データ抽出部２０４とデータ生成基本回路部２０５との間に、ハフマン符号の性質上から存在する可能性の全くないハフマン符号の復号候補データを出力しないようにするデータ選択回路５０１を設けて、各ビット毎の入力候補データED11〜ED18を選択するようにしたことから、回路の動作確率を下げることができるので、ハフマン符号復号化装置を低消費電力化させることができる。
【０１７４】
なお、上記した各実施形態では、８ビットのハフマン符号の復号化アルゴリズムの実施形態を説明したが、本発明はこれに限られるものではなく、例えば、ハフマン符号の復号化アルゴリズムを１６ビットに拡張した場合を考えると、ＪＰＥＧの画像圧縮伸長の回路アルゴリズムを適用した画像圧縮伸長処理装置に適用することができる。また、このアルゴリズムは、画像圧縮伸長ソフトウェアにも応用することができる。
【０１７５】
また、上記した各実施形態では、ハフマン符号復号化装置を８ビットまでハフマン符号を復号化する回路として示したが、本発明はこれに限られるものではなく、例えば、任意の数値であるｎビットまでハフマン符号を復号化する回路にも適用することができる。
【０１７６】
また、上記した各実施形態では、８ビットまでハフマン符号を復号化するハフマン符号復号化装置の実施形態を示したが、本発明はこれに限られるものではなく、例えば、逆にデータをハフマン符号化する符号化装置に適用することができる。その場合には、例えば、上記した最小値データの概念を用いて、最小値データとの差分データを用いてハフマン符号化するように符号化回路を実現すれば、データ変換回路の記憶容量を減少させることができる。
【０１７７】
【発明の効果】
上記のように請求項１および請求項５の本発明は、ビット長毎の復号候補データから最小値データを減算した結果により固定長データを生成するようにしたので、あらゆる種類のハフマン符号を小容量の符号テーブルと演算のみで効率的に固定長データに復号化することができ、記憶容量を減らせることから、復号データ出力部の回路規模を縮小することができる。
【０１７８】
請求項２の本発明は、復号候補データ抽出部をシフト出力回路としたので、復号データ出力部の回路規模を縮小することができる。
【０１７９】
請求項１の本発明は、さらに、最小値データを各ビット長毎に記憶されたハフマン符号の個数とレジスタの出力とを加算することにより生成するようにしたので、記憶容量を減らすことができる。
【０１８０】
請求項３および請求項６の本発明は、固定長データを各ビット長毎に記憶された累積個数と、ビット長毎の復号候補データから最小値データを減算した結果とを加算して生成するようにしたので、記憶容量を減らすことができる。
【０１８１】
請求項５の本発明は、最小値データ生成部に個数零検出部を備えたので、ビット数が１ビットの場合以外にもハフマン符号の個数が“０”であるハフマン符号についても検出できるので、あらゆる種類のハフマン符号を復号化することができる。
【図面の簡単な説明】
【図１】  本発明の第１の実施形態のハフマン符号復号化装置の概略構成を示すブロック図である。
【図２】  図１のハフマン符号復号化装置の内部の復号データ出力部の構成をさらに詳しく示すブロック図である。
【図３】  （ａ）は図２のシフト出力回路の入出力対応表であり、（ｂ）は図２の個数記憶回路の入出力対応表であり、（ｃ）は図２の累積個数記憶回路の入出力対応表である。
【図４】  各ビット長毎の最小値データ、個数、および累積個数出力の対応表である。
【図５】  （ａ）はハフマン符号復号化装置に入力されるシリアル入力データの一例を示す図であり、（ｂ）は（ａ）のシリアル入力データを各ビット長毎に抽出した復号候補データから最小値データを減算した結果の一覧を示す図であり、（ｃ）は（ｂ）の減算結果出力と累積個数出力からその加算結果が固定長データとなる様子を示す図である。
【図６】  最小値生成部内の各データの対応表である。
【図７】  ハフマン符号復号化の動作を示すフローチャートである。
【図８】  図７のステップＳ４に示した最小値データ生成部の動作を更に詳しく示すフローチャートである。
【図９】  本発明の第２の実施形態のハフマン符号化装置の最小値データ生成部の構成を示すブロック図である。
【図１０】  シフト出力回路の入出力対応表。
【図１１】  本発明の第３の実施形態のハフマン符号化装置の復号データ出力部の構成を示すブロック図である。
【図１２】  本発明の第４の実施形態のハフマン符号化装置の復号データ出力部の構成を示すブロック図である。
【図１３】  ２ビット用固定長データ記憶部に予め格納された値を示す図である。
【図１４】  本発明の第５の実施形態のハフマン符号化装置の復号データ出力部の構成を示すブロック図である。
【図１５】  本発明の第６の実施形態のハフマン符号化装置の復号データ出力部の構成を示すブロック図である。
【図１６】  従来のハフマン符号を復号化するハフマン符号復号化装置を示すブロック図である。
【符号の説明】
１  ハフマン符号復号化回路、  ２  直列／並列変換部、  ３  復号データ出力部、  ４  復号候補データ抽出部、  ５  データ生成基本回路部、  ６  最小値データ生成部、  ７  減算器、  ８  固定長データ生成部、  ４１  シフト出力回路、  ６１  カウンタ、  ６２  個数記憶回路、  ６３  レジスタ、  ６４加算器、  ６５  シフト出力回路、  ６７、６８  ＯＲ回路、  ８１  累積個数記憶回路、  ８２  加算器、  ８３  レジスタ、  ８４  バッファ。
【図１】
0004393685.tif 000002
【図２】
0004393685.tif 000003
【図３】
0004393685.tif 000004
【図４】
0004393685.tif 000005
【図５】
0004393685.tif 000006
【図６】
0004393685.tif 000007
【図７】
0004393685.tif 000008
【図８】
0004393685.tif 000009
【図９】
0004393685.tif 000010
【図１０】
0004393685.tif 000011
【図１１】
0004393685.tif 000012
【図１２】
0004393685.tif 000013
【図１３】
0004393685.tif 000014
【図１４】
0004393685.tif 000015
【図１５】
0004393685.tif 000016
【図１６】
0004393685.tif 000017