(57)【特許請求の範囲】
【請求項１】
符号化対象データを入力するデータ入力手段と、
前記データ入力手段から入力される前記符号化対象データに含まれるシンボルのうち予め選択された支配候補シンボルの各々の出現度数を計数する度数集計手段と、
前記度数集計手段により計数された出現度数に基づいて、前記支配候補シンボルのセットから支配シンボルを選択するデータ選択手段と、
各シンボルの予測される出現確率に従って予め設計した符号語を保持する固定符号語記憶手段と、
前記支配シンボルに対しては所定の手法で新たに符号語を生成し、さらにその他のシンボルに対しては、前記支配シンボル以外のシンボルであることを示す符号語と前記固定符号語記憶手段に保持された符号語とを組み合せたものを新たな符号語として割当てる符号割当手段と、
前記符号割当手段で生成された符号語を保持する符号語記憶手段と、
前記符号語記憶手段に保持した符号語に基づいて前記データ入力手段から入力される前記符号化対象データを符号化する符号化手段と、
前記符号化手段で生成された符号データを出力する符号出力手段とを有することを特徴とする符号化装置。
【請求項２】
前記支配候補シンボルは発生頻度が高いと推測されるものとする請求項１記載の符号化装置。
【請求項３】
前記符号割当手段における符号語作成処理は、予め候補としてあげた符号表のいずれかになるよう限定する請求項１または２記載の符号化装置。
【請求項４】
前記候補としてあげる符号表は発生頻度が高いと推測される種類、および、他の候補との関係から削除した場合に圧縮率の悪化が推測される種類のうち少なくとも一方の種類のものとする請求項３記載の符号化装置。
【請求項５】
前記符号化手段は前記符号化対象データに加えて、前記符号割当手段で生成した符号語を特定する符号表データを符号化する請求項１、２、３または４記載の符号化装置。
【請求項６】
符号データを入力する符号入力手段と、
符号語を記憶する符号語記憶手段と、
前記符号語記憶手段に保持した符号語に基づいて前記符号入力手段から入力される前記符号データを復号する復号手段と、
前記復号手段の復号により生成したデータに含まれるシンボルのうち予め選択された支配候補シンボルの各々の出現度数を計数する度数集計手段と、
前記度数集計手段により計数した出現度数に応じて、前記支配候補シンボルのセットから支配シンボルを選択するデータ選択手段と、
各シンボルの予測される出現確率に従って予め設計した符号語を保持する固定符号語記憶手段と、
前記支配シンボルに対しては所定の手法で新たに符号語を生成し、さらにその他のシンボルに対しては前記支配シンボル以外のシンボルであることを示す符号語と前記固定符号語記憶手段に保持された符号語とを組み合せたものを新たな符号語として割当てる符号割当手段とを有し、
前記符号割当手段で生成された符号語を前記符号語記憶手段に記憶させ、さらに、
前記復号手段が復号したデータを出力するデータ出力手段を有することを特徴とする復号装置。
【請求項７】
請求項５記載の符号化装置により符号化された符号データを入力する符号データ入力手段と、
符号語を記憶する符号語記憶手段と、
前記符号語記憶手段に保持した符号語に基づいて前記符号入力手段から入力される前記符号データを復号する復号手段とを有し、
前記符号語記憶手段に保持する符号語を、前記復号手段で復号した上記符号表データに基づいて設定することを特徴とする復号装置。
【請求項８】
前記符号語記憶手段に初期値として設定される符号は予め定数が設定してある請求項７記載の復号装置。
【請求項９】
符号化対象データを入力するデータ入力手段と、
前記データ入力手段から入力される前記符号化対象データに含まれる各シンボルの出現度数を計数する度数集計手段と、
前記度数集計手段により計数された出現度数に基づいて、前記シンボルのセットから支配シンボルを選択するデータ選択手段と、
各シンボルの予測される出現確率に従って予め設計した符号語を保持する固定符号語記憶手段と、
前記支配シンボルに対しては所定の手法で新たに符号語を生成し、さらにその他のシンボルに対しては、前記支配シンボル以外のシンボルであることを示す符号語と前記固定符号語記憶手段に保持された符号語とを組み合せたものを新たな符号語として割当てる符号割当手段と、
前記符号割当手段で生成された符号語を保持する符号語記憶手段と、
前記符号語記憶手段に保持した符号語に基づいて前記データ入力手段から入力される前記符号化対象データと、前記データ選択手段で選択した支配シンボルを特定する中間シンボルデータとを符号化する符号化手段と、
前記符号化手段で生成された符号データを出力する符号出力手段とを有することを特徴とする符号化装置。
【請求項１０】
前記符号化手段は前記符号化対象データと前記データ選択手段で選択した支配シンボルを特定する中間シンボルデータとに加えて、前記符号割当手段で生成した符号語を特定する符号表データを符号化する請求項９記載の符号化装置。
【請求項１１】
中間シンボルを記憶する中間シンボル記憶手段を有し、
前記中間シンボル記憶手段の内容は前記データ選択手段で選択した中間シンボルデータに基づいて設定し、
前記符号化手段で行う符号化は前記符号語記憶手段に保持した符号語に加えて前記中間シンボル記憶手段に保持した中間シンボルデータに基づく請求項９または１０記載の符号化装置。
【請求項１２】
請求項９〜１１のいずれかに記載の符号化装置により符号化された符号データを入力する符号データ入力手段と、
符号語を記憶する符号語記憶手段と、
前記符号語記憶手段に保持した符号語に基づいて前記符号入力手段から入力される前記符号データを復号する復号手段と、
前記中間シンボルを記憶する中間シンボル記憶手段とを有し、
前記中間シンボル記憶手段の内容は前記復号手段で復号した中間シンボルデータに基づいて設定し、
前記復号手段で行う復号は前記符号語記憶手段に保持した符号語に加えて前記中間シンボル記憶手段に保持した中間シンボルデータに基づくことを特徴とする復号装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明はデータの圧縮技術、例えばハフマン符号を用いた圧縮技術に関するものである。
【０００２】
【従来の技術】
一般に通信、蓄積等を行う場合、データの圧縮を行うとデータ量を削減する効果が得られる。このような圧縮技術の代表例としてハフマン符号がある。
【０００３】
以下ハフマン符号について説明する。ハフマン符号は公知の技術であり、例えば『文書データ圧縮アルゴリズム入門（植松著／ＣＱ出版社）』（ｐｐ．４６−５）にその記載がある。ハフマン符号は大まかに言うと多く発生するシンボルには短い符号、発生しづらいシンボルには長い符号を与えることによってデータを圧縮する。ハフマン符号の一例を図２０に示す。
【０００４】
ハフマン符号が有効であるための条件として、以下の２つがあげられる。
（１）各シンボルの出現確率が既知であること
（２）各シンボルの出現確率が定常的であること
条件（１）はハフマン符号の生成が出現確率に依存すること、条件（２）はハフマン符号が固定の符号表を用いることに起因する。しかし条件（１）を満たすためには入力データに対して符号化前に一度統計処理を行う必要があり、処理が重くなる。また条件（２）は一般のデータ系列では成立しない。
【０００５】
条件（１）と（２）を緩和する従来技術として、符号化しながら適当な間隔でハフマン符号を更新する技術がある。この場合、直前に符号化したデータの統計に基づいて符号を設計するので条件（１）の必要がなく、また更新間隔毎に最適な符号を使うので条件（２）も緩い変化であれば許容できる。以下、特開平７−７４３６号公報を参考に、この従来例について説明する。図２１および２３はそれぞれ従来例の符号化装置、復号装置を説明するブロック図である。まず図２１を用いて従来例の符号化装置について説明する。図中、１０はデータ入力部、２０は度数集計部、４０は符号割当部、６０は符号語メモリ、７０はハフマン符号化部、８０は符号出力部、１００は入力データ、１１０は度数データ、１４１は符号語データ、１５１は符号データである。
【０００６】
図２１の各部について説明する。データ入力部１０は外部から符号化すべきデータを入力し、入力データ１００として度数集計部２０およびデータメモリ９０へ送出する。度数集計部２０は入力データ１００に含まれるシンボルの出現度数を計数し、度数データ１１０として符号割当部４０へ送出する。符号割当部４０は度数データ１１０を基に符号語データ１４１を生成し、符号語メモリ６０に蓄積する。ハフマン符号化部７０は符号語メモリ６０に蓄積された符号語データ１４１を用いて入力データ１００に対してハフマン符号化を行い、符号データ１５１として符号出力部８０へ送出する。符号出力部８０は作成された符号データ１５１を外部へ出力する。
【０００７】
次に図２３を用いて従来例の復号装置について説明する。図２１と同様の部分には同じ符号を付して説明を省略する。１５は符号入力部、７５はハフマン復号部、８５はデータ出力部である。
【０００８】
図２３の各部について説明する。符号入力部１５は外部から復号すべき符号を入力し、符号データ１５１としてハフマン復号部７５へ送出する。ハフマン復号部７５は符号語メモリ６０に蓄積された符号語データ１４１を用いて符号入力部１５から入力された符号データ１５１に対してハフマン復号を行い、入力データ１００としてデータ出力部８５へ送出する。データ出力部８５は作成された入力データ１００を外部へ出力する。
【０００９】
以上の構成に基づいて従来例の動作について説明する。図２２、２４はそれぞれ従来例の符号化、復号動作を説明するフローチャートである。
【００１０】
以下、図２２を用いて符号化処理を説明する。Ｓ１０では度数集計部２０において入力データ１００に含まれるシンボルを種類別にカウントし、度数データ１１０を得る。Ｓ２１１ではその時点で予め定められた符号表更新処理条件を満たしているかどうかを判定し、満たしていればＳ２１２へ、そうでなければＳ３０へ進む。Ｓ２１２では符号割当部４０において度数データ１１０に基づいてハフマン符号を生成し符号語データ１４１を得る。Ｓ３０ではハフマン符号化部７０において符号語データ１４１を用いて入力データ１００にハフマン符号化を行う。Ｓ４０では未処理の入力データ１００の有無を判定し、あればＳ１０へ、なければ符号化処理を終了する。
【００１１】
次に図２４を用いて復号処理を説明する。図２２と同様の処理には同じ符号を付して説明を省略する。Ｓ５０ではハフマン復号部７５において符号語データ１４１を用いて符号データ１５１に対してハフマン復号を行う。
【００１２】
以上の動作の中で、最初の符号化および復号処理を行う際に用いる符号は同一の初期値が与えられるものとする。予め汎用的に設計されたものを固定的に用いてもよいし、入力データ用に特に設計した符号を用いてもよいが、後者の場合には符号データのヘッダに符号表を付与するなどして、復号側に符号表を知らせる必要がある。
【００１３】
Ｓ２１１における符号表更新処理条件は任意である。例えば前出の特開平７−７４３６号公報では特に動画像を対象とし、１枚の画像毎に符号表を更新する。
【００１４】
Ｓ２１２におけるハフマン符号の作成アルゴリズムは公知であり、例えば前出の『文書データ圧縮アルゴリズム入門（植松著／ＣＱ出版社）』にも記載があるのでここでは詳述しない。おおざっぱにいえば各シンボルを出現確率順にソートし、出現確率の小さい２つのシンボルを組み合せ新たなシンボルとする。これを繰り返しながら符号を割り振る。
【００１５】
以下、従来例の問題点について述べる。従来例では符号表の更新は、入力されるシンボルの出現確率分布の定常性が成立する単位で行われることが望ましい。そのためには各シンボルの出現確率分布を推定するのに十分な統計さえとれれば、更新の間隔はなるべく短いほうがよい。例えば前出の特開平７−７４３６号公報とは違って静止画像を対象とするような場合、画像間の出現確率分布の類似性は期待できないので、画像内での更新が有効になる。
【００１６】
一方でＳ２１２におけるハフマン符号の生成処理は、ソート処理を多用する。このため、符号表の更新間隔の短縮は全体の処理負荷の増加を招く。
【００１７】
これを改善する従来例としては、例えば特開昭６３−２３２６２６号公報があげられる。特開昭６３−２３２６２６号公報ではシンボルを出現頻度順に並べ換え、予め用意された符号表に書き込むことで疑似的にハフマン符号を構成する。この手法だとソート処理が一度で済むのでハフマン符号生成処理の負荷を削減できる。
【００１８】
この場合の問題点は符号量を効率的に小さくできる保証がないことにある。つまり、頻度順にソートしたとしてもその結果出てくる確率分布は何通りも考えられるので、最適な符号を生成する保証がない。
【００１９】
【発明が解決しようとする課題】
本発明は上記の事情を鑑みてなされたもので、簡易に適応的な圧縮符号例えばハフマン符号を生成する符号化技術を提供することを目的とする。本発明は、さらに、ハードウェアの実装において最適な符号化技術を提供することを目的とする。
【００２０】
【課題を解決するための手段】
本発明の第１の側面によれば、符号化装置に、符号化対象データを入力するデータ入力手段と、前記データ入力手段から入力される前記符号化対象データに含まれるシンボルのうち予め選択された支配候補シンボルの各々の出現度数を計数する度数集計手段と、前記度数集計手段により計数された出現度数に基づいて、前記支配候補シンボルのセットから支配シンボルを選択するデータ選択手段と、各シンボルの予測される出現確率に従って予め設計した符号語を保持する固定符号語記憶手段と、前記支配シンボルに対しては所定の手法で新たに符号語を生成し、さらにその他のシンボルに対しては、前記支配シンボル以外のシンボルであることを示す符号語と前記固定符号語記憶手段に保持された符号語とを組み合せたものを新たな符号語として割当てる符号割当手段と、前記符号割当手段で生成された符号語を保持する符号語記憶手段と、前記符号語記憶手段に保持した符号語に基づいて前記データ入力手段から入力される前記符号化対象データを符号化する符号化手段と、前記符号化手段で生成された符号データを出力する符号出力手段とを設けている。
【００２１】
また、本発明の第２の側面によれば、復号装置に、符号データを入力する符号入力手段と、符号語を記憶する符号語記憶手段と、前記符号語記憶手段に保持した符号語に基づいて前記符号入力手段から入力される前記符号データを復号する復号手段と、前記復号手段の復号により生成したデータに含まれるシンボルのうち予め選択された支配候補シンボルの各々の出現度数を計数する度数集計手段と、前記度数集計手段により計数した出現度数に応じて、前記支配候補シンボルのセットから支配シンボルを選択するデータ選択手段と、各シンボルの予測される出現確率に従って予め設計した符号語を保持する固定符号語記憶手段と、前記支配シンボルに対しては所定の手法で新たに符号語を生成し、さらにその他のシンボルに対しては前記支配シンボル以外のシンボルであることを示す符号語と前記固定符号語記憶手段に保持された符号語とを組み合せたものを新たな符号語として割当てる符号割当手段とを設け、前記符号割当手段で生成された符号語を前記符号語記憶手段に記憶させ、さらに、前記復号手段が復号したデータを出力するデータ出力手段を設けるようにしている。
【００２２】
このような構成によれば、平均符号語長にとくに影響がある支配シンボルについて適応的に符号語を更新するので符号量を小さくすることができ、しかも符号語の更新の付加を少なくできる。さらに、支配シンボル候補を予め決めてそれらの度数のみを計数するのでカウンタの個数を少なくすることができる（計数処理を簡略化できる）。
【００２３】
この構成においては、前記支配候補シンボルを発生頻度が高いと推測されるものとすることができる。
【００２４】
また、前記符号割当手段における符号語作成処理は、予め候補としてあげた符号表のいずれかになるよう限定するようにしてもよい。
【００２５】
また、前記候補としてあげる符号表は発生頻度が高いと推測される種類、および、他の候補との関係から削除した場合に圧縮率の悪化が推測される種類のうち少なくとも一方の種類のものとすることができる。
【００２６】
また、前記符号化手段は前記符号化対象データに加えて、前記データ選択手段で選択した支配シンボルを特定する中間シンボルデータを符号化するようにしてもよい。
【００２７】
また、前記符号化手段は前記符号化対象データに加えて、前記符号割当手段で生成した符号語を特定する符号表データを符号化するようにしてもよい。
【００２８】
また、中間シンボルを記憶する中間シンボル記憶手段を設け、前記中間シンボル記憶手段の内容は前記データ選択手段で選択した中間シンボルデータに基づいて設定し、前記符号化手段で行う符号化は前記符号語記憶手段に保持した符号語に加えて前記中間シンボル記憶手段に保持した中間シンボルデータに基づくようにしてもよい。
【００２９】
また、本発明の第３の側面によれば、符号化対象データに加え、中間シンボルデータや符号表データを符号化する符号化装置から出力された符号データを復号する復号装置を、符号データを入力する符号データ入力手段と、符号語を記憶する符号語記憶手段と、前記符号語記憶手段に保持した符号語に基づいて前記符号入力手段から入力される前記符号データを復号する復号手段とを設け、前記符号語記憶手段に保持する符号語を、前記復号手段で復号した上記符号表データおよび上記中間シンボルデータの少なくとも一方に基づいて設定するようにしている。
【００３０】
この構成によれば、復号装置側で符号表を作成する必要がなく、構成や処理を簡略化できる。また、中間シンボルデータを送ることにより、復号装置側で用意する符号表を少なくすることができる。
【００３１】
また、この構成において、前記符号語記憶手段に初期値として設定される符号を、予め定めた定数にしてもよい。
【００３２】
また、本発明の第４の側面によれば、符号化対象データに加えて、中間シンボルデータを符号化する符号化装置からの符号データを復号する復号装置に、符号データを入力する符号データ入力手段と、符号語を記憶する符号語記憶手段と、前記符号語記憶手段に保持した符号語に基づいて前記符号入力手段から入力される前記符号データを復号する復号手段と、前記中間シンボルを記憶する中間シンボル記憶手段とを設け、前記中間シンボル記憶手段の内容は前記復号手段で復号した中間シンボルデータに基づいて設定し、前記復号手段で行う復号は前記符号語記憶手段に保持した符号語に加えて前記中間シンボル記憶手段に保持した中間シンボルデータに基づくようにしている。
【００３３】
この構成においても、復号装置側で用意する符号表を少なくすることができる。
【００３４】
また、本発明は、前記符号化装置および復号装置を適宜組み合わせて符号化復号装置として実装することもできるし、方法として実現することもできる。
【００３５】
また、以上の構成において、前記データ選択手段で行われる選択処理は、前記度数集計手段の集計結果に基づいて、予め定められた閾値より大きい度数を持つシンボルを前記支配シンボルとして選択するようにすることができる。
【００３６】
また、前記データ選択手段で行われる選択処理は、前記度数集計手段の集計結果に基づいて、出現頻度の大きさ順に並べたときに予め定められた順位より若い順位を持つシンボルを前記支配シンボルとして選択するようにしてもよい。
【００３７】
また、前記データ選択手段で行われる選択処理は、前記度数集計手段の集計結果に基づいて、出現頻度の大きさ順に並べ大きい方から出現頻度を累積したときの累積頻度が予め定められた閾値より小さいシンボルを前記支配シンボルとして選択するようにしてもよい。
【００３８】
また、前記符号割当手段で行われる符号化はハフマン符号化とすることができる。
【００３９】
また、前記符号割当手段において前記支配シンボルに割当てるはずだった固定符号語が余っており、かつそれより符号長の長い符号を持つ支配シンボルでないシンボルがある場合、一時的にそのシンボルに前記固定符号語を割当てるようにしてもよい。
【００４０】
また、前記符号割当手段における符号語作成処理は、各シンボルの出現確率が所定値を外れた場合に行われるようにしてもよい。
【００４１】
また、前記符号割当手段における符号語作成処理は、所定数のシンボルの符号化または復号が完了した場合に行われるようにしてもよい。
【００４２】
また、前記符号割当手段で生成された符号語の平均符号語長が前記固定符号語手段に保持された符号語の平均符号語長より長くなると予測される場合には前記固定符号語を新たな符号語とするようにしてもよい。
【００４３】
また、前記度数集計手段で行われる統計値の初期化はそれまでの統計値に１以下の正の数を乗算して行うようにしてもよい。
【００４４】
また、前記固定符号語記憶手段に保持する符号語を既処理データの統計に基づいて新たに生成した符号語で置き換えるようにしてもよい。
【００４５】
また、前記符号割当手段における符号語作成処理は、予めシンボルの出現確率パターンとそれに対応する符号語を用意しておき、前記支配シンボルを前記出現確率パターンへ分類することによって簡易に前記符号語を得るようにしてもよい。
【００４６】
また、前記支配シンボルに対するパターン分類は、最頻シンボルの出現確率と閾値の大小比較によって行うようにしてもよい。
【００４７】
また、前記支配シンボルに対するパターン分類は、支配シンボルを頻度順に並べたとき複数の予め定められた順番に対応したシンボルの頻度による演算結果で決定するようにしてもよい。
【００４８】
また、前記符号語記憶手段に初期値として設定される符号は予め定数が設定してあってもよい。
【００４９】
また、前記符号語記憶手段に初期値として設定される符号は前記固定符号語記憶手段に保持された符号を用いてもよい。
また、中間シンボルを記憶する中間シンボル記憶手段を有し、前記中間シンボル記憶手段の内容は前記データ選択手段で選択した中間シンボルデータまたは前記復号手段で復号した中間シンボルデータに基づいて設定し、前記符号化手段で行う符号化または前記復号手段で行う復号は前記符号語記憶手段に保持した符号語に加えて前記中間シンボル記憶手段に保持した中間シンボルデータに基づくようにしてもよい。
【００５０】
【発明の実施の態様】
以下、本発明について詳細に説明する。ここでは、まず、本発明の背景技術について説明し、その後、実施例を挙げることにする。なお、この背景技術は本出願人が特願平９−１０１２１６号（平成９年４月１８日出願、現時点では未公開）で提案した技術である。
【００５１】
［背景技術具体例１］
背景技術の具体的な説明に入る前に、その原理について説明する。従来のハフマン符号化復号装置の問題点はハフマン符号の生成処理の負荷が重く、更新処理を短くしにくいことであった。そこでこれを解決するために、ハフマン符号を簡易的に生成することにする。すなわち、平均符号長に影響が大きいと思われる出現頻度の高いシンボルに対しては通常どおりのハフマン符号を生成し、それ以外のシンボルについては予め汎用的に用意された符号を与えることにする。以下、このように出現頻度の高いシンボルを支配シンボルと呼ぶ。
【００５２】
以上の点を具体的に説明する。ハフマン符号の平均符号長は各シンボルｓに与えられた符号長ｌ（ｓ）と出現確率ｐ（ｓ）の積和で表される。すなわち、
【００５３】
【数１】
0003593884.tif 000002
ただしＳはシンボル全体の集合を表す。いまｓ０からｓ５まで６個のシンボルがあり、ｓ０とｓ１の出現確率がそれぞれ１／２、１／４で、それ以外のシンボルは１／４に満たなかったとする。この仮定の下でエントロピーすなわち理論平均符号長が最小となるのは、例えばｓ２の出現確率がぎりぎり１／４に届かず、それ以外のシンボルの出現確率がほぼ０となる場合である。この条件で通常のハフマン符号を生成すると、最終的にｓ０、ｓ１、ｓ２にそれぞれ符号長１、２、３［ｂｉｔ］の符号が割当てられる。従って平均符号長は（１）式より、
【００５４】
【数２】
0003593884.tif 000003
と計算できる。次に本背景技術において出現確率１／４以上のシンボルを支配シンボルとみなしたとする。この場合ｓ０とｓ１にそれぞれ符号長１、２［ｂｉｔ］の符号が割当てられる。またその他のシンボルは支配シンボルでないことを表す２［ｂｉｔ］の符号と、ｓ２〜ｓ５のいずれかを示す２［ｂｉｔ］の符号で表す。この場合の平均符号長は（１）式より、
【００５５】
【数３】
0003593884.tif 000004
となる。出現確率にかかわらず符号を生成した場合の平均符号長はｌｏｇ２（６）＝２．６［ｂｉｔ］となるから、（３）式の値は（２）式には及ばないものの符号量としては小さくなることがわかる。また以上の見積りは本背景技術に対してかなり厳しい条件で計算したもので、実際にはｓ２〜ｓ５の中でｓ２の出現確率だけが突出するような状況は考えにくいので、現実の（２）式と（３）式の差はもっと小さいと考えられる。
【００５６】
以下に本背景技術具体例１について詳細に説明する。図１および図４はそれぞれ本具体例の符号化装置および復号装置の構成を示すブロック図である。図２１および、２３に示した従来例と同様の部分には同じ符号を付して説明を省略する。図中、３０は支配シンボル選択部、５０は固定符号語メモリ、１２０は支配シンボル度数データ、１３０は固定符号語データ、１４０は符号語データ、１５０は符号データである。
【００５７】
まず図１を用いて本具体例の符号化装置について説明する。図１の各部について説明する。支配シンボル選択部３０は度数データ１２０から所定の閾値より大きい度数をもつデータだけを支配シンボル度数データ１２０として符号割当部４０へ送出する。固定符号語メモリ５０は入力データ１００の想定される確率分布に対して予め生成されたハフマン符号を蓄積し、固定符号語データ１３０として符号割当部４０へ送出する。
【００５８】
図４は本具体例の復号装置の構成を示す。図４の各部の構成は従来例および本具体例の符号化装置に関連して説明したものと同様であるので、説明を繰り返さない。
【００５９】
以上の構成に基づき、本具体例の動作について説明する。図２および図３は本具体例における符号化処理の動作を、また図５は本具体例における復号処理の動作を示すフローチャートである。
【００６０】
まず図２および図３を用いて本具体例の符号化処理の動作について説明する。ただし図２の各処理については従来例と同様のため、同じ符号を付して説明を省略する。以下、図３を用いてＳ２０の符号表更新について説明する。Ｓ２０１では符号表更新条件が成立しているかどうかを判定し、成立していればＳ２０２へ、そうでなければＳ３０へ進む。Ｓ２０２ではシンボルのＩＤを示す変数ｎと支配シンボル度数データ１２０を蓄積する支配シンボルリストを初期化する。Ｓ２０３では度数データ１１０から変数ｎが示すシンボルの度数を取り出して、所定の閾値Ｔｈと比較し大ならばＳ２０４へ、小ならばＳ２０５へ進む。Ｓ２０４ではＳ２０３で比較した度数データを、符号割当部４０の支配シンボルリストに加える。Ｓ２０５では変数ｎに１を加える。Ｓ２０６では処理されていないシンボルの有無を判断し、未処理データがあればＳ２０３へ、なければＳ２０７へ進む。Ｓ２０７では符号割当部４０において支配シンボルリストに存在する支配シンボルに対してハフマン符号を生成する。Ｓ２０８では符号割当部４０においてＳ２０７で作成されたハフマン符号と固定符号語メモリ５０に蓄積された固定符号語データ１３０を合成して全体のハフマン符号を得る。
【００６１】
図５は本具体例の復号処理の動作を示す。図５の全体は従来例と同様であり、また図５のＳ２０は本具体例の符号化処理の動作と同様であるので省略する。
【００６２】
以上の動作の中で、最初の符号化および復号は例えば固定符号語メモリ５０の符号語に従う。このとき、従来例で述べたように別の初期値が符号語メモリ６０に書き込まれてもよい。
【００６３】
次に符号割当部４０で行われる処理の詳細について説明する。以下、説明を簡単化するためシンボルをアルファベットの小文字２６個とする。符号割当部４０の支配シンボルリストには選択されなかったシンボルに符号を与えるため、”その他”というシンボルを初期化時に登録しておく。このときの支配シンボルリストの内部フォーマット例を図６（ａ）に示す。Ｓ２０３で用いる閾値Ｔｈを例えば全体の１／４とすれば、Ｔｈに等しい度数を持つシンボルは選択されないので、支配シンボルは最大で３個となる。支配シンボル度数データ１２０のフォーマット例を図６（ｂ）に、全てのシンボルに対する選択処理が終了しＳ２０７に入る直前の支配シンボルリスト例を図６（ｃ）に示す。ただし符号表更新条件を１００個のシンボルの符号化が終了した場合とした。このとき”その他”の出現度数は全体の度数から支配シンボルの度数を減算したものとする。もしくはＳ２０３の直後において選択されなかったシンボルの度数を逐次的に加算していってもよい。図６（ｃ）で選択されたシンボルに対してＳ２０７でハフマン符号化を行った例を図６（ｄ）に示す。これで”ａ”、”ｅ”、”ｓ”の３つの支配シンボルに対応する符号が生成された。
【００６４】
これ以外のシンボルに対しては”その他”の符号と固定符号語メモリ５０にデフォルトとして用意された固定符号語を合成して割当てる。固定符号語の例を図７（ｂ）に示す。この符号表は予め符号化処理開始前にシンボルの出現確率を推定して作成しておく。Ｓ２０７で作成した符号を図７（ａ）に、固定符号語と合成した最終的な符号を図７（ｃ）にそれぞれ示す。このとき支配シンボルに対して固定符号語が割当てた符号、図７の例でいえばシンボル”ａ”を示す”１１１０００”等が無駄になるが、平均符号長への影響は少ないので無視する。ただし簡易的な処置として例えば固定符号語のシンボルを符号長の長いものと入れ換えるような処理を行ってもよい。図７の例でいえば”１１１０００”がどうせ使われないのであるから、図７（ｂ）の”ａ”と”ｂ”を一時的に入れ替えて”１１１０００”を”ｂ”の符号としてもよい。
【００６５】
もしＳ２０７に達したとき支配シンボルが”その他”以外になかった場合には、固定符号語をそのまま符号語データ１４０として用いる。ところで支配シンボルが”その他”を含めて２つ以上あっても、固定符号語を用いた方が平均符号長が短くなる場合がある。これを避けるためには以下のような処理を追加すればよい。
【００６６】
簡単のため支配シンボルが”その他”を含めて２つと仮定する。これ以外の条件でも以下の説明から容易に類推が可能である。まず固定符号語の理想的な確率分布が発生したとしたときの平均符号長をｌｔｈとし、これを固定符号語の理論的平均符号長と考える。すなわち、シンボル”ａ”の推定出現確率をｐｔｈ（ａ）、割当てられた符号長をｌｆｉｘ（ａ）とすれば（４）式のようになる。
【００６７】
【数４】
0003593884.tif 000005
ただし総和は出現し得るシンボル全てについてとる。次に支配シンボルを”その他”と”ｘ”とし、Ｓ２０７でそれぞれ”１”、”０”の符号を割当てられたとする。このときの平均符号長ｌｓｅｌは以下の式で近似的に求められる。
【００６８】
【数５】
0003593884.tif 000006
ここでｐ（ａ）はシンボル”ａ”の出現頻度を実測して計算した出現確率である。２項目のｌｔｈ’は固定符号語から”ｘ”が抜けた場合の理論的平均符号長である。これは（４）式から、
【００６９】
【数６】
0003593884.tif 000007
として近似する。ただし総和は”ｘ”以外の出現し得るシンボル全てについてとる。（５）式に対して”ｘ”が選択されたにもかかわらず固定符号語を使いつづける場合の平均符号長ｌｆｉｘは、
【００７０】
【数７】
0003593884.tif 000008
となるから、（５）式−（７）式を計算して、
【００７１】
【数８】
0003593884.tif 000009
となる。従ってこの（８）式が正であれば固定符号語そのままを、負であれば新たに合成した符号語を用いればよい。
【００７２】
上記の動作の中で符号表更新条件は、従来例同様に任意にとることができる。例えば上述の説明例のように処理データ量に依存してもよいし、確率分布の変化度合いに応じてもよい。例えば出現度数を監視しておき、支配シンボル以外のシンボル（上述の例では出現確率が１／４を越えないシンボル）の出現度数がある出現確率（例えば１／３とか）を越えて出現しつづけるようであれば、確率分布が変化したと判定する。この例を図８に示す。これとは逆に支配シンボルの出現確率低下を監視してもよい。
【００７３】
また、上述の例では、支配シンボルは出現頻度を閾値処理して選択したが、その他の手法で支配シンボルを決定してもよい。要するに出現頻度に応じて支配シンボルを決定すればよい。例えば、頻度順にソートしたときの上からの順位を閾値処理してもよい。すなわち、上位の所定番目までのシンボルを支配シンボルとしてもよい。こうすれば、支配シンボルの個数を一定に保つことができる。また頻度順にソートし、上の順位のシンボルから順番にその頻度を累積し、その累積値を閾値処理するようにしてもよい。すなわち、累積値が所定値以下となるシンボルを支配シンボルとする。例えば、１番目から５番目のシンボルを累積した値が所定値以下であり、６番目までの累積値が所定値を超える場合には、１番目から５番目までのシンボルを支配シンボルとする。このようにすると、支配シンボルの影響を定性的に安定化させることができる。すなわち、支配シンボルの全頻度が上述の所定値となるので、支配シンボルの影響を安定化させることができる。
【００７４】
また、度数集計部２０における出現度数の計数は０で初期化しているが、既処理データに応じて初期化時にオフセットされていても構わない。例えば初期値をｃｏｕｎｔｉ、直前の出現度数をｃｏｕｎｔｉ−１とすれば（９）式のような初期化が考えられる。
【００７５】
【数９】
0003593884.tif 000010
これにより度数データの平滑化が図れ、局所的な確率分布の変動に左右されない大局的な符号を作成することができる。
【００７６】
また、最初の符号更新までに用いる初期値の符号は固定符号語メモリ５０に蓄積したハフマン符号を用いてもよいし、仕様として適当な初期値を設定してもよい。
【００７７】
また、適当なタイミングで固定符号語メモリ５０に蓄積するハフマン符号を変更すれば符号量の減少が図れる。すなわち、既処理データの統計に基づいて事前に推定した出現確率を補正し、新たにハフマン符号を生成する。この場合は全てのシンボルに対して通常の手法で生成する必要がある。
【００７８】
また、以上ではすべてハフマン符号を前提に説明したが、適応的に設計できる符号であれば他の符号でも応用できる。整数長の符号でいえば、シャノン・ファノ符号等が応用可能であるし、算術符号も符号語をオージェンドの分割に置き換えれば応用が可能である。
【００７９】
［背景技術具体例２］
本背景技術をさらに簡易な処理で実現するため、具体例２として支配シンボルのハフマン符号生成処理を簡略化した例について述べる。本具体例の原理は、選択されるシンボルの出現確率がある閾値より大きいことを利用し、ビット割当をいくつかのパターンに分類して予め対応する符号を用意しておくことにある。さらにパターンの分類はごく簡単な処理で近似的に行う。
【００８０】
本具体例の全体の構成と動作は具体例１と同様のため、説明を省略する。本具体例は具体例１における図３のＳ２０７の処理の変形例として位置づけられる。以下、説明を簡略化するために閾値をシンボル度数の総数の１／８とし、かつ”その他”の出現確率が１／８より大きいと仮定した場合について述べるが、他の場合についても容易に類推が可能であり一般性は失われない。
【００８１】
具体的な説明に入る。支配シンボル数が”その他”を含めて３個以下の場合は自明なので、まず４個の場合について述べる。いま４個の支配シンボルは出現度数順にソートされているものとし、順にシンボル１、シンボル２、…と呼ぶ。またシンボルｎの出現確率をｐ（ｎ）と書く。従って
【００８２】
【数１０】
0003593884.tif 000011
となる。このときビット割当ては図９（ａ）の２通りが考えられる。それぞれの符号木を図９（ｂ）（ｃ）に示す。さて両符号木の平均符号長はそれぞれ、
【００８３】
【数１１】
0003593884.tif 000012
で表すことができる。さてｌｃａｓｅ１＝ｌｃａｓｅ２となるための条件は次のようになる。
【００８４】
【数１２】
0003593884.tif 000013
ｐ（ｎ）の総和は１となるので、次式を得る。
【００８５】
【数１３】
0003593884.tif 000014
（１０）式の条件を考慮するとｌｃａｓｅ１＝ｌｃａｓｅ２が成立するｐ（１）の範囲は１／３≦ｐ（１）≦２／５となる。この範囲でｐ（１）が極値をとったときの平均符号長の上限、下限を図９（ｄ）に示す。例えばｐ（１）が１／３の場合２／９≦ｐ（２）≦１／３でなければならず、さらにそれぞれの場合にｐ（３）、ｐ（４）の値も限定される。その結果ｃａｓｅ１の平均符号長は２ないし２．１１となることがわかる。図９（ｄ）よりｐ（１）が２／５を越えれば必ず図９（ａ）のｃａｓｅ１の、逆に１／３を下回れば必ずｃａｓｅ２のビット割当てが最適となることがわかる。１／３＜ｐ（１）＜２／５の場合は最適ビット割当ては特定できないが、いずれか判断を誤っても符号量の差は少ないので無視する。
【００８６】
図１０は具体例２の動作を説明するフローチャートである。図１０を用いて処理手順を説明する。Ｓ２０７１では支配シンボルを度数順にソートする。Ｓ２０７２では出現頻度の最大値ｐ（１）が閾値ｐｔｈを越えているかどうか判定し、ｐ（１）＞ｐｔｈであればＳ２０７４へ、そうでなければＳ２０７３へ進む。Ｓ２０７３では図９（ａ）のｃａｓｅ２の符号を選択し、Ｓ２０７４ではｃａｓｅ１の符号を選択する。Ｓ２０７５では支配シンボルとＳ２０７３もしくはＳ２０７４で得られた符号を対応づける符号表を生成する。以上の動作の中でｐｔｈは１／３＜ｐ（１）＜２／５の範囲で適当に選択する。例えば中間値である１１／３０でもよいし、判定の容易さを考慮して１／３としてもよい。もし判定の容易さが符号量の増大よりも重要な場合には上記の範囲を越えても評価が簡単な２のベキ乗の逆数、例えば１／４や１／２としてもよい。ただし最適な符号を得られない可能性が高くなる。
【００８７】
逆に最適な符号を期すならば、ｌｃａｓｅ２−ｌｃａｓｅ１＝ｐ（１）−ｐ（３）−ｐ（４）の正負を計算してもよい。この場合処理負荷が若干増加するが、符号は必ず最適となる。
【００８８】
もうひとつの例として支配シンボルが”その他”を含めて５個の場合について述べる。ビット割当てを出現頻度順に列記する形式で示せば、支配シンボルが５個の場合１２３４４、１３３３３、２２２３３の３つのケースが考えられる。しかし各シンボルの出現確率が１／８より大きいこととハフマン符号の生成規則から、１２３４４となるケースは存在しない。従って実際には図１１（ａ）の２つのケースを考えればよい。
【００８９】
さてこの場合の両者の平均符号長はそれぞれ次式でかける。
【００９０】
【数１４】
0003593884.tif 000015
前と同様にｌｃａｓｅ１＝ｌｃａｓｅ２が成立するｐ（１）の範囲を考えると、１／３≦ｐ（１）≦３／８となる。それぞれの平均符号長の上限、下限を図１１（ｄ）に示す。これよりｐ（１）≦１／３のときｃａｓｅ２の、ｐ（１）≧３／８のときｃａｓｅ１のビット割当てが最適となる。従って図１０のＳ２０７２で用いるｐｔｈは１／３から３／８の範囲、もしくはその近辺の値から選べばよい。またシンボル数４個の時同様、ｌｃａｓｅ２−ｌｃａｓｅ１＝ｐ（１）−ｐ（２）−ｐ（３）の正負を計算すれば、最適な符号を得ることも可能である。
【００９１】
本具体例によればハフマン符号化処理が前もって用意したパターンに分類するだけで行え、しかもパターンの分類は支配シンボルのソート処理と比較処理で行えるので、具体例１の処理の大幅な簡略化が図れる。
【００９２】
最後に本背景技術の効果を示す実験結果例を図１２に示す。６ｂｉｔデータを入力とし次の４つの手法で符号化した結果である。
【００９３】
（１）従来例
（２）本背景技術  （支配シンボルが全体の１／１０）
（３）本背景技術  （支配シンボルが全体の１／５０）
（４）一般的ハフマン符号  （まずシンボルの統計をとって符号生成し、２パス目で符号化するもの）
実験によれば（２）、（３）、（４）の処理時間はほぼ等しく、（１）の約１／２０〜１／５０程度であった。図１２から本背景技術の効果は明らかである。
【００９４】
［実施例１］
つぎに、本発明の実施例について説明する。本発明は、上述の背景技術を改善するものであり、とくに、ハードウェア上の実装において格別な効果をもたらすものである。
【００９５】
まず、本発明の実施例１を説明する。上述背景技術の具体例１および２では、支配シンボルの選択およびハフマン符号生成処理に、全てのシンボルの出現度数を知る必要がある。これは本背景技術をソフトウェアで実現する際にはあまり問題にならないが、ハードウェアでの実装を考えるとシンボル数分のカウンタが必要になるので、シンボル数によっては限られた資源では実現が難しくなる。
【００９６】
ところで背景技術の具体例１および２では入力データに対して何の仮定も置いてこなかったが、現実には入力データの性質が既知であるような場合がある。例えば入力データを英文内の１文字とすれば、”ｑ”、”ｖ”、”ｘ”などに比べて”ａ”、”ｅ”、”ｓ”などはより頻繁に出現することが予想される。これはつまり前者に比べて後者の方がより支配シンボルとして選択される可能性が高いことを示す。
【００９７】
そこで本実施例ではシンボルを非候補シンボルと支配候補シンボルの２種類に分類する。非候補シンボルは必ず支配シンボルとして選択しないこととし、個別の出現頻度カウントはしない。一方、支配候補シンボルに対しては第１、第２の実施例同様に出現度数をカウントし、支配シンボルを選択する。こうして得られた支配シンボルと、非候補シンボルおよび支配候補シンボルで選択されなかったシンボルからなる”その他”シンボルに基づいて新たな符号表を生成する。この符号表の生成については上述背景技術の具体例１および２と同様である。
【００９８】
具体的には、図１３に示すように、度数集計部２０にハードウェアカウンタ２０１、２０２、・・・２０ｎを設ける。そして支配候補シンボル設定部２００でカウンタ２０１、２０２、・・・２０ｎで計数するシンボルを設定する。
【００９９】
本実施例は、全てのシンボルについて出現頻度を計数したとしても非候補シンボルからは支配シンボルが選択されないことを仮定しているのと同値である。現実の情報源の出現確率分布は変動するから、このような仮定が必ず成立するとは限らない。しかしある程度の確率で成立すれば、圧縮率の悪化は抑えることができる。この小さなリスクに対して、非候補シンボルに対応するカウンタが不要になるメリットは特にハードウェア規模に対して非常に大きい。
【０１００】
以上では支配シンボルの候補となるシンボルの省略について述べたが、符号木についても同様の省略が可能である。以下、これについて説明する。上述背景技術の具体例２では支配シンボルの個数毎に可能性のある全ての符号木を候補とし、適当な判断基準を設けて符号表を生成した。しかし符号木によっては発生確率がごく稀なものも含まれる。例えば支配シンボルの閾値を１／８とした場合、支配シンボルが７個になることは理論的には有り得るが、現実にはほぼ起こらないと考えてよい。従って例えば装置規模が制限されるような場合には、支配シンボル７個の符号表を用意することによる圧縮率向上のメリットよりも装置規模増大のデメリットの方が大きいと考えられる。
【０１０１】
そこで符号木に対しても候補の符号木を制限する。これは例えば実験的に発生頻度が少ない符号木を削除すればよい。もし削除した符号木に対応するような支配シンボルが得られた場合、近い符号木に振り替えて代用する。上述の例でいえば、例えば支配シンボル５個用の符号木を用意しておき、支配シンボルが６個以上になった場合には５個用の符号木で代用する。これにより背景技術の具体例２でいうＳ２０７にあたる符号木の選択処理を簡略化することができ、また符号割当部４０で用意するパターン数を減らすことができる。候補の符号木選択のバリエーションとしては、その符号木を削除して他の符号木で置き換えても原理的に圧縮率に与える影響が少ないと予想できるものから削除してもよい。例えば支配シンボル２個用と３個用の符号木が２個づつある場合、２個用の２つを削除するより２個用と３個用から１つづつ削除した方が圧縮率への影響が少ないことが予想される。
【０１０２】
本実施例に関する構成および動作は上述背景技術の具体例１および２から容易に類推が可能なので、ここでは説明を省略する。以下、本実施例の効果を説明するため、本実施例を画像符号化に適用した実験例について述べる。ここでとりあげる画像符号化は予測符号化とランレングス符号化を組み合わせたものだが、このランレングスに対するハフマン符号化の部分に本実施例を適用した。
【０１０３】
この画像符号化ではラン長を１〜５００までとるが、１〜８を支配候補シンボルとし９以上を非候補シンボルとした。支配シンボルは０〜７個まで考えられるので理論的な符号木の種類は１１個だが、ここでは支配シンボルが０〜２個だった場合に対応する４個の符号木だけを候補とした。従って支配シンボルが３個以上だった場合は、出現度数の順に上位２個の支配シンボルを選択し、これに対応する符号木を用いることにした。
【０１０４】
本実施例によれば予め支配シンボルの候補を絞ることができるので、符号化装置および復号装置の簡略化が図れる。
【０１０５】
本実施例によって実験的に得られた符号量の比較を図１４に示す。グラフは左から固定の符号表、背景技術具体例２、本実施例による符号量を示している。同図より本実施例の効果は明らかである。
【０１０６】
［実施例２］
本発明の実施例２として、特に復号装置の簡易化に有効な構成を説明する。本実施例は２つの技術的特徴からなる。まず第１の特徴について説明する。
【０１０７】
上述背景技術の具体例１、２や実施例１では、符号化装置で行われる符号表生成処理を復号装置でも模倣することにより、変化する符号表に対応した復号を可能とした。しかし本来符号表を生成すべきなのは符号化装置のみであり、復号装置は使用した符号表を知ることさえできればよい。またこのような構成の場合、符号化装置側の符号表生成処理の仕様が変わった場合に対応することが難しい。そこで本実施例では使用した符号表もしくはその識別番号を符号データに埋め込む。これによって異なるアルゴリズムで符号表を生成する複数の符号化装置に対しても、一つの復号装置で対応することができる。
【０１０８】
次に第２の特徴について説明する。上述背景技術の具体例１、２や実施例１では明記しなかったが、符号表はシンボルと符号が対応した表を想定していた。しかしこうすると例えば支配シンボルが１個の符号表だけとっても、全てのシンボルが支配シンボルになる可能性があるのだから、符号木の形が１つなのにもかかわらずシンボル数分の符号表が必要になる。これは例えばハードウェアで実装する場合には重要なポイントになり得る。
【０１０９】
そこで本実施例では中間に抽象的な中間シンボルを挟むことにする。復号の場合、符号表による復号結果は中間シンボル、すなわちどの支配シンボルかという情報までにしておいて、続く後段でその中間シンボルに該当する実際の入力シンボルに復号する。符号表では中間シンボルまでわかればよいのだから、符号木が１つなら１つの符号表ですみ、装置の縮小が可能となる。この技術的特徴は符号化装置に適用しても同様な効果をもたらす。
【０１１０】
この第２の特徴を上述第１の特徴と組み合わせる場合、符号には、符号表だけでなく、中間シンボルと支配シンボルの関係も埋め込むことになる。
【０１１１】
以下、本実施例について具体的に説明する。図１５、図１８はそれぞれ本実施例の符号化装置、復号装置の構成を示すブロック図である。図１および図４に示した背景技術の具体例１と同様の部分は同一の符号を付して説明を省略する。図中、１４２は符号表データ、１４３は中間シンボルデータ、６１は中間シンボルメモリである。
【０１１２】
まず、図１５に示した符号化装置の各部について第１の従来例と異なる点に絞って説明する。符号割当部４０は背景技術具体例１の動作に加え、生成した符号表を示すデータを符号表データ１４２としてハフマン符号化部７０へ送出する。同時に生成した符号表で選択された支配シンボルを示すデータを中間シンボルデータ１４３としてハフマン符号化部７０および中間シンボルメモリ６１へ送出する。中間シンボルメモリ６１は中間シンボルデータ１４３を保持し、ハフマン符号化部７０へ送出する。ハフマン符号化部７０は中間シンボルメモリ６１に蓄積された中間シンボルデータ１４３と符号メモリ６０に蓄積された符号語データ１４０を用いて、符号表データ１４２、中間シンボルデータ１４３、入力データ１００のそれぞれに対してハフマン符号化を行い、符号データ１５１として符号出力部８０へ送出する。
【０１１３】
符号化装置の動作についての説明は背景技術の具体例や実施例１と大差ないので省略するが、ハフマン符号化部７０についてだけ説明しておく。まず他の構成と異なる点として、符号語データ１４０には入力データ１００だけでなく、符号表データ１４２、中間シンボルデータ１４３がとるそれぞれの値に対応する符号語が含まれていなければならない。ハフマン符号化部７０はこの符号語データ１４０に基づいて、符号表データ１４２および中間シンボルデータ１４３の符号化を行う。また、これらのデータの符号化は符号割当部４０で符号表を更新したときに行う。
【０１１４】
本実施例における符号データ１５０、符号表データ１４２の概念図をそれぞれ図１６（ａ）、同図（ｂ）に示す。図中入力１〜Ｎは入力データ１００に含まれる入力シンボルを示す。ここでは符号表データ１４２は特定の符号表を対応する数字で指定する形式を示した。これ以外に直接符号語を埋め込むような形式でもよいし、あるいはその中間をとって部分的に符号語を埋め込むような形式でもよい。同図（ｂ）の例えば符号表データの２に示したように、符号表によっては支配シンボルの個数が少ないために、後半の中間シンボルに符号が割り当てられないようなものもあり得る。
【０１１５】
図１６（ｃ）、同図（ｄ）には中間シンボルデータ１４３の概念図を示す。ここでは直接中間シンボルに対応する入力シンボルを指定する形式を示した。これも符号表データ同様、特定の組み合わせそれぞれに対応する数字で表現するような形式にしてもよい。同図（ｃ）では中間シンボルの個数は３つとしたが、これは符号表データがいくつの中間データに対応するかによって、中間シンボルデータの長さが変化するような形式を仮定した。バリエーションとして簡単化のために中間シンボルの個数を固定してもよい。同図（ｄ）がそのような例で、この場合中間シンボルの個数が少ない符号表データに対しては、ダミーの中間シンボルデータを埋めておく。
【０１１６】
なお、図１６の例のように符号表データと中間シンボルデータが必ずセットになるような形式では、中間シンボルデータの位置が特定できるので、中間シンボルデータに与える符号が入力シンボルおよび符号表データに与える符号と重なっていても構わない。逆に入力シンボル、符号表データ、中間シンボルデータの３種類の符号が重ならないように設計しておけば、これらのデータの並ぶ順番は任意であって、特に図１６（ａ）のような形式を守る必要はない。
【０１１７】
次に入力データ１００の符号化について説明する。ハフマン符号化部７０は入力データ１００を受け取るとまず中間シンボルメモリ６１と照合し、入力データ１００が支配シンボルだった場合には、該当する中間シンボルに対応した符号を符号語メモリ６０から読み出して符号とする。入力データ１００が支配シンボルでなかった場合には、入力データ１００に対応した符号を符号語メモリ６０から読み出して符号とする。符号語メモリ６０の内部データは、例えば図１６（ｂ）に示した”対応する符号表”の欄の中の一つの行のような形式をとる。また中間シンボルメモリ６１の内部データは例えば図１７のような形式をとる。
【０１１８】
次に図１８に示した復号装置の各部について、第１の従来例および図１５に示した符号化装置と異なる点に絞って説明する。ハフマン復号部７５は中間シンボルメモリ６１に蓄積された中間シンボルデータ１４３と符号メモリ６０に蓄積された符号語データ１４０を用いて、符号データ１５０にハフマン復号を行い、その結果得られる符号表データ１４２、中間シンボルデータ１４３、入力データ１００をそれぞれ符号語メモリ６０、中間シンボルメモリ６１、データ出力部８５に送出する。
【０１１９】
以上の構成に基づいて本実施例の復号装置の動作について説明する。図１９は本実施例の復号動作を説明するフローチャートである。
【０１２０】
以下、図１９を用いて復号処理を説明する。ただし他の構成と同様の部分には同一の符号を付して説明を省略する。Ｓ２０１ではハフマン復号部７５においてＳ５０の復号処理の復号結果が符号表データだった場合にはＳ２０９へ、そうでなければＳ４０へ進む。Ｓ２０９ではハフマン復号部７５において、まず符号表データに基づき符号語メモリ６０の内容を新たな符号表に更新する。続いて符号データ１５０から中間シンボルデータ１４３を復号し、その内容に基づいて支配シンボルメモリ６１の内容を更新する。
【０１２１】
ここでは図１６（ａ）に示したように、符号表データの直後に中間シンボルデータが埋め込まれているような符号データ１５０を想定した。
【０１２２】
本実施例によれば符号表更新情報を符号に埋め込んだので、復号装置の簡略化が図れる。また符号表の内容を直接支配シンボルではなく中間シンボルに置き換えたので、符号化装置および復号装置の簡略化が図れる。
【０１２３】
【発明の効果】
本発明によれば大量のメモリや処理負荷なしに、簡易かつ適応的なハフマン符号を生成することができる。さらに、ハードウェアで実装する際に、回路構成を簡略化することができる。
【図面の簡単な説明】
【図１】背景技術の具体例１の符号化装置を示す構成図である。
【図２】背景技術の具体例１の符号化装置における符号化処理の動作の一例を示すフローチャートである。
【図３】背景技術の具体例１の符号化装置における符号表更新処理の動作の一例を示すフローチャートである。
【図４】背景技術の具体例１の復号装置を示す構成図である。
【図５】背景技術の具体例１の復号装置における復号処理の動作の一例を示すフローチャートである。
【図６】背景技術の具体例１の符号化装置における支配シンボルリストの内部フォーマット例を示す説明図である。
【図７】背景技術の具体例１の符号化装置において作成される符号例を示す説明図である。
【図８】背景技術の具体例１の符号化装置における符号表更新に用いる条件例を示す説明図である。
【図９】背景技術の具体例２の符号化復号装置において作成される符号例を示す説明図である。
【図１０】背景技術の具体例２の符号化復号装置における符号表更新処理の部分動作の一例を示すフローチャートである。
【図１１】背景技術の具体例２の符号化復号装置において作成される符号例を示す説明図である。
【図１２】背景技術の具体例の符号化復号装置による実験結果例を示す説明図である。
【図１３】本発明の実施例１の符号化復号装置の要部を説明する図である。
【図１４】本発明の実施例１の符号化復号装置による実験結果例を示す説明図である。
【図１５】本発明の実施例２の符号化装置を示す構成図である。
【図１６】本発明の実施例２における各データの概念を示す説明図である。
【図１７】本発明の実施例２における中間シンボルメモリの内部データ例を示す説明図である。
【図１８】本発明の実施例２の復号装置を示す構成図である。
【図１９】本発明の実施例２の復号装置における復号処理の動作の一例を示すフローチャートである。
【図２０】従来のハフマン符号例を示す説明図である。
【図２１】従来例の符号化装置を示す構成図である。
【図２２】従来例の符号化装置における符号化処理の動作の一例を示すフローチャートである。
【図２３】従来例の復号装置を示す構成図である。
【図２４】従来例の復号装置における復号処理の動作の一例を示すフローチャートである。
【符号の説明】
１０    データ入力部
１５    符号入力部
２０    度数集計部
３０    支配シンボル選択部
４０    符号割当部
５０    固定符号語メモリ
６０    符号語メモリ
６１    中間シンボルメモリ
７０    ハフマン符号化部
７５    ハフマン復号部
８０    符号出力部
８５    データ出力部
１００    入力データ
１１０    度数データ
１２０    支配シンボル度数データ
１３０    固定符号語データ
１４０、１４１    符号語データ
１４２    符号表データ
１４３    中間シンボルデータ
１５０、１５１    符号データ
【図１】
0003593884.tif 000016
【図２】
0003593884.tif 000017
【図３】
0003593884.tif 000018
【図４】
0003593884.tif 000019
【図５】
0003593884.tif 000020
【図６】
0003593884.tif 000021
【図７】
0003593884.tif 000022
【図８】
0003593884.tif 000023
【図９】
0003593884.tif 000024
【図１０】
0003593884.tif 000025
【図１１】
0003593884.tif 000026
【図１２】
0003593884.tif 000027
【図１３】
0003593884.tif 000028
【図１４】
0003593884.tif 000029
【図１５】
0003593884.tif 000030
【図１６】
0003593884.tif 000031
【図１７】
0003593884.tif 000032
【図１８】
0003593884.tif 000033
【図１９】
0003593884.tif 000034
【図２０】
0003593884.tif 000035
【図２１】
0003593884.tif 000036
【図２２】
0003593884.tif 000037
【図２３】
0003593884.tif 000038
【図２４】
0003593884.tif 000039