JP3778087B2

JP3778087B2 - データ符号化装置及びデータ復号装置

Info

Publication number: JP3778087B2
Application number: JP2002010179A
Authority: JP
Inventors: 太郎横瀬
Original assignee: Fuji Xerox Co Ltd; Fujifilm Business Innovation Corp
Current assignee: Fujifilm Business Innovation Corp
Priority date: 2002-01-18
Filing date: 2002-01-18
Publication date: 2006-05-24
Anticipated expiration: 2022-01-18
Also published as: JP2003218703A; US20030137438A1; US6717534B2

Description

【０００１】
【発明の属する技術分野】
本発明は、データ符号化装置及びデータ復号装置に関する。
【０００２】
【従来の技術】
データ圧縮の基本的な技術思想は、ハフマン（Huffman）符号に見ることができる。ハフマン符号化では、出現頻度の高い文字にビット長の短い符号を割り当て、出現頻度の順にビット長を増大させながら、互いに区別できる符号を割り当てていく。この基本的な符号化の方法は、「データ圧縮ハンドブック」，Ｍ．ネルソン著，荻原剛志・山口英訳，株式会社トッパン発行，１９９４年３月初版発行に詳細な説明があるので、ここでの詳しい説明を省略する。
【０００３】
ハフマン符号化では、符号化の単位となるデータ要素と、符号の最小単位（符号語）とが１：１関係（１つのデータ要素に１つの符号語が対応付けられ、１つの符号語に１つのデータ要素が対応付けられる関係）にある。このような符号化方法ではデータ要素と符号語の対応付けを、「符号テーブル」と呼ばれるテーブルとして保持するのが一般的である。
【０００４】
符号テーブルを利用した符号化は、一連の符号化対象データについて、各符号化対象データが、数少ないデータ要素の集合に含まれる場合はよいが、データ要素の種類が多くなると、対応づけるべき符号語の数が増大し、符号テーブルのエントリを大きくする必要がある。具体的にアルファベット２６文字をデータ要素として英文文字列のデータを符号化するには、２６個の符号語を定義した符号テーブルを生成すればよいのに対し、日本語の五十音をデータ要素とする仮名文のデータを符号化するには、５０個の符号語を定義した符号テーブルを生成しなければならない。
【０００５】
このように符号語の数が増大すると、符号テーブルを作成する手間がかかり、実装が困難になる。また符号テーブルを符号化データに添付する符号化方式もあるが、この場合、符号テーブルが長大になる結果、圧縮率悪化の原因となり得る。そこで圧縮率に影響を与えない範囲で符号テーブルのサイズを小さくするべく、従来から付加ビットの技術が国際画像符号化標準ＪＰＥＧ（Joint Photographic Experts Group）のベースライン方式などで採用されている。
【０００６】
以下、このＪＰＥＧを例として、付加ビットの技術について説明する。ＪＰＥＧは、端的には、写真などの画像データにおいて、隣接画素間の画素値の変化が少ないことに着目して、画素値の空間周波数成分のうち、高周波成分を除去することでデータを圧縮するものである。この圧縮の過程で、画像データは例えば８×８画素の画素ブロックに分割され、当該画素ブロック内の周波数成分がＤＣＴ（離散コサイン変換）されて直流（ＤＣ）成分と、交流（ＡＣ）成分とに分けて取り扱われる。
【０００７】
具体的にＤＣ成分については、隣接する画素ブロックとの差分がハフマン符号化される。このハフマン符号化において、ＤＣ成分の差分値はグループ分けされて符号化される。すなわち、このハフマン符号化では、グループが符号化の単位であるデータ要素となって、このグループと符号語とを対応づけた符号テーブルが用いられる。また、ＤＣ成分の差分値（現差分値）を正確に表現するために当該グループに分類される最小の差分値（グループ最小値）と、現差分値との差をさらに付加ビットとしてハフマン符号化の符号語に付加する。この付加ビットの算出方法は、例えば次のようになる。
【０００８】
(付加ビット)＝(現差分値)−(グループ最低値) …(現差分値)＜0 のとき
＝(現差分値)＋(グループ最低値)＋Ｍ−1 …それ以外のとき
ここでＭはこのグループに含まれるデータの種類の数である。また、この算出方法は、理論的もので現実的には符号テーブルの特性を使って簡略化されたものが用いられる。
【０００９】
また、このようにして符号化されたデータを復号する際には、符号化の際に利用された符号テーブルが参照され、ハフマン符号化による符号語からグループが特定され、当該特定されたグループのグループ最小値と付加ビットとから元のＤＣ成分の差分値が再生される。
【００１０】
このように、従来の符号化技術のある例では、符号テーブルを小さくするために、グループ化された符号テーブルと、グループ内でのデータの特定のための付加情報（付加ビット）とを採用していた。
【００１１】
【発明が解決しようとする課題】
しかしながら、上記従来のグループ化された符号テーブルと付加情報とを用いる符号化技術では、グループに分類されるデータの出現頻度がほぼ一定の場合には、圧縮効率が向上できるが、グループに分類されるデータの出現頻度にばらつきがある場合、圧縮効率を向上させようとすると、符号テーブルが大きくなって実装が困難になる問題点があった。
【００１２】
すなわちＪＰＥＧのように数値をグループに分類する場合の例でいえば、連続性を有する数値が１つのグループに分類できればよいが、連続性を有しない場合には問題となる。すなわち、ＪＰＥＧでは、ＤＣ成分の差分値はほぼ「０」である（隣接画素間の画素値変化は小さいという仮定の下）と期待できるので、「０」に近い数値ほど出現頻度が高くなるので、これに短い符号語を割り当てればよい。この場合、例えば「３」以下の数値は最短の符号語を割り当てるなどのようにグループ分けすることができるのである。しかし、仮に「０．８〜１．２」の値は出現頻度が低い、という場合、「０〜０．８」と、「０．８〜１．２」と、「１．２〜３」の３つのグループ分けをする方が圧縮効率が高くなるのである。
【００１３】
この例のように特異な数値範囲があるといった場合、つまり出現頻度との関係で連続性を有しない数値範囲がある場合や、出現頻度の想定が困難な場合には、グループの数を増大させる必要があって、結局符号テーブルのエントリが大きくなって符号テーブルの形成が難しくなり、実装が困難になってしまう。
【００１４】
本発明は、上記実情に鑑みて為されたもので、符号テーブルの構成を容易にして実装を容易にできるデータ符号化装置及びデータ復号装置を提供することを目的とする。
【００１５】
【課題を解決するための手段】
上記従来例の問題点を解決するための本発明は、データ符号化装置であって、データの符号化単位であるデータ要素と、符号語とを対応づける符号テーブルであって、１つのデータ要素にＮ（Ｎは１以上の整数）個の符号語を対応付け、各符号語には１つのデータ要素を対応付ける符号テーブルを保持する手段と、一連の符号化対象データの各々について、その符号化対象データに対応するデータ要素を決定し、当該データ要素に対応するＮ個の符号語を前記符号テーブルから検索する検索手段と、所定の基準に基づき、前記Ｎ個の符号語から１つの符号語を選択する選択手段と、前記選択した符号語が対応するデータ要素の中で、当該符号語に対応付けた符号化対象データを特定するための付加情報を必要に応じて生成する手段と、を含み、各符号化対象データを、符号語と付加情報とからなる付加情報表現符号データ又は、符号語からなる通常表現符号データのいずれかに変換することを特徴としている。
【００１６】
また、上記従来例の問題点を解決するための本発明は、データ符号化装置であって、データの符号化単位であるデータ要素と符号語とを対応づける複数の符号テーブルであって、各符号テーブル間で、１つのデータ要素に対し、相異なる符号語の対応付けを許容して定義された符号テーブルを保持する手段と、一連の符号化対象データについて、各符号化対象データに対応するデータ要素を決定し、当該データ要素に対応する符号語が関連づけられたＮ個（Ｎは２以上の整数）の符号テーブルを検索する検索手段と、所定の基準に基づき、前記Ｎ個の符号テーブルから１つの符号テーブルを選択し、当該選択した符号テーブルにおいて、前記データ要素に関連づけられた符号語を出力する選択手段と、前記選択した符号語が対応するデータ要素の中で、当該符号語に対応付けた符号化対象データを特定するための付加情報を必要に応じて生成する手段と、を含み、各符号化対象データを、符号語と付加情報とからなる付加情報表現符号データ又は、符号語からなる通常表現符号データのいずれかに変換することを特徴としている。
【００１７】
これらにおいて、前記選択手段は、前記所定の基準として、Ｎ個の符号語のうち、最短の符号語を選択することとしてもよいし、前記選択手段は、前記所定の基準として、事前に定められた優先順位に従って１つの符号語を選択することとしてもよい。
【００１８】
また、複数の符号テーブルから一つの符号テーブルを選択する場合、前記選択手段は、各符号語に関連づけて、選択した符号テーブルを特定する選択情報を出力することも好ましい。
【００１９】
また上記従来例の問題点を解決するための本発明は、データの符号化単位であるデータ要素と符号語とを対応づける符号テーブルであって、１つのデータ要素にＮ（Ｎは１以上の整数）個の符号語を対応付け、各符号語には１つのデータ要素を対応付ける符号テーブルを保持するデータ復号装置であって、前記データ符号化装置により符号化されて得られた一連の符号データから各符号データを順次取り出し、当該取り出した符号データに含まれる符号語に対応するデータ要素を前記符号テーブルから検索する手段と、前記取り出した符号データが付加情報表現符号データであるときに、当該符号データから付加情報を取り出し、前記検索されたデータ要素と当該取り出した付加情報とにより、符号化前のデータを復号する手段と、を含むことを特徴としている。
【００２０】
また、上記従来例の問題点を解決するための本発明は、データ復号装置であって、データの符号化単位であるデータ要素と符号語とを対応づける複数の符号テーブルであって、各符号テーブル間で、１つのデータ要素に対し、相異なる符号語の対応付けを許容して定義された符号テーブルを保持する手段と、前記複数の符号テーブルを備えたデータ符号化装置により符号化されて得られた一連の符号データから各符号データを順次取り出し、当該取り出した符号データに含まれる符号語に対応するデータ要素を前記複数の符号テーブルから検索する手段と、前記取り出した符号データが付加情報表現符号データであるときに、当該符号データから付加情報を取り出し、前記検索されたデータ要素と当該取り出した付加情報とにより、符号化前のデータを復号する手段と、を含むことを特徴としている。
【００２１】
さらに、上記従来例の問題点を解決するための本発明は、データ復号装置であって、データの符号化単位であるデータ要素と符号語とを対応づける複数の符号テーブルであって、各符号テーブル間で、１つのデータ要素に対し、相異なる符号語の対応付けを許容して定義された符号テーブルを保持する手段と、前記複数の符号テーブルを備え、選択した符号テーブルに関する選択情報を出力するデータ符号化装置により符号化されて得られた一連の符号データから各符号データを順次取り出し、当該取り出した符号データに含まれる符号語を抽出し、前記データ符号化装置が当該抽出した符号語との関係において出力した選択情報に基づいて前記複数の符号テーブルから１つの符号テーブルを選択し、前記抽出した符号語に対応するデータ要素を前記選択した符号テーブルから検索する手段と、前記取り出した符号データが付加情報表現符号データであるときに、当該符号データから付加情報を取り出し、前記検索されたデータ要素と当該取り出した付加情報とにより、符号化前のデータを復号する手段と、を含むことを特徴としている。
【００２２】
さらに、上記従来例の問題点を解決するための本発明によれば、データ符号化方法であって、データの符号化単位であるデータ要素と符号語とを対応づける符号テーブルであって、１つのデータ要素にＮ（Ｎは１以上の整数）個の符号語を対応付け、各符号語には１つのデータ要素を対応付ける符号テーブルを用い、一連の符号化対象データについて、各符号化対象データに対応するデータ要素を決定し、当該データ要素に対応するＮ個の符号語を前記符号テーブルから検索する工程と、所定の基準に基づき、前記Ｎ個の符号語から１つの符号語を選択する工程と、前記選択した符号語が対応するデータ要素の中で、当該符号語に対応付けた符号化対象データを特定するための付加情報を必要に応じて生成する工程と、を含み、各符号化対象データを、符号語と付加情報とからなる付加情報表現符号データ又は、符号語からなる通常表現符号データのいずれかに変換することを特徴としている。さらに、本発明のある態様によれば、符号化データであって、上記データ符号化方法によって生成されたことを特徴とする。
【００２３】
さらに上記従来例の問題点を解決するための本発明は、データ復号方法であって、データの符号化単位であるデータ要素と符号語とを対応づける符号テーブルであって、１つのデータ要素にＮ（Ｎは１以上の整数）個の符号語を対応付け、各符号語には１つのデータ要素を対応付ける符号テーブルを用い、前記データ符号化方法により符号化されて得られた一連の符号データから各符号データを順次取り出し、当該符号データに含まれる符号語に対応するデータ要素を前記符号テーブルから検索する工程と、前記取り出した符号データが付加情報表現符号データであるときに、当該符号データから付加情報を取り出し、前記検索されたデータ要素と当該取り出した付加情報とにより、符号化前のデータを復号する工程と、を含むことを特徴とする。
【００２４】
また、本発明のある態様によれば、符号化データであって、一連の符号化対象データを符号化処理して得られた符号化データであって、符号語と付加情報とからなる付加情報表現符号データと、符号語からなる通常表現符号データとを含むことを特徴としている。
【００２５】
さらに本発明の別の態様によれば、符号化データであって、データの符号化単位であるデータ要素と符号語とを対応づける複数の符号テーブルであって、各符号テーブル間で、１つのデータ要素に対し、相異なる符号語の対応付けを許容して定義された符号テーブルを用い、一連の符号化対象データについて、各符号化対象データが属するデータ要素を決定し、当該データ要素に対応する符号語が関連づけられたＮ個（Ｎは２以上の整数）の符号テーブルを検索する工程と、所定の基準に基づき、前記Ｎ個の符号テーブルから１つの符号テーブルを選択し、当該選択した符号テーブルにおいて、前記データ要素に関連づけられた符号語を出力する選択工程と、前記選択した符号語が対応するデータ要素の中で、当該符号語に対応付けた符号化対象データを特定するための付加情報を必要に応じて生成する工程と、を行って、各符号化対象データを符号語と付加情報とからなる付加情報表現符号データ又は、符号語からなる通常表現符号データのいずれかに変換されることにより生成され、一連の符号化対象データに基づき、前記付加情報表現符号データと、通常表現符号データとの少なくとも一方を含んでなることを特徴としている。
【００２６】
またこの符号化データであって、一連の付加情報表現符号データ又は通常表現符号データの各々との関連において、各符号語の出力の際に選択された符号テーブルを特定する情報をさらに含んでなることも好ましい。
【００２７】
【発明の実施の形態】
本発明の実施の形態について図面を参照しながら説明する。まず、本発明の実施の形態におけるデータ符号化装置及びデータ復号装置にて採用される符号化の処理の原理について述べる。本発明においては、従来ハフマン符号のごとく符号化対象のデータの要素１つに対して１つの符号語を関連づける、いわば１：１符号の概念を拡張し、データの要素１つに対してＮ（Ｎは１以上の整数）の符号語を対応付ける。この場合において復号側から見れば１つの符号語には１つのデータ要素が定まるようにしておくことで、復号に影響がでないようにする。
【００２８】
このように、符号語を重複させることで同一のデータ要素に対して付加情報を用いた連続的な符号語と、特定の符号語との両方を定義できる。これによって付加情報によるコンパクトな符号テーブルと、細かい符号語割り当てによる高い圧縮率の双方が同時に実現可能となる。
【００２９】
本発明の実施の形態に係るデータ処理システムは、図１に示すように、データ符号化装置１と、データ復号装置２とを含んで構成される。ここでデータ符号化装置１及びデータ復号装置２は、いずれも一般的なパーソナルコンピュータであり、データ符号化装置１は、ＣＰＵ１１と記憶部１２とハードディスク１３と表示部１４と操作部１５とを含み、これら各部は互いにバスを介して接続されている。また、データ復号装置２は、ＣＰＵ２１と記憶部２２とハードディスク２３と表示部２４と操作部２５とを含み、これら各部も互いにバスを介して接続されている。なお、ここでは説明の便宜上、データ符号化装置１とデータ復号装置２とを別体の装置として説明しているが、例えばデータ符号化装置１のハードディスク１３にデータ復号プログラムをインストールすれば、データ符号化装置１とデータ復号装置２とは一体の装置としても実現できる。
【００３０】
データ符号化装置１のＣＰＵ１１は、ハードディスク１３に格納されているプログラムに従って動作し、データの符号化処理等を実行する。このデータの符号化処理については、後に詳しく述べる。記憶部１２は、ＣＰＵ１１のワークメモリとして動作する。ハードディスク１３は、ＣＰＵ１１により実行されるプログラムや、ＣＰＵ１１のプログラム実行時に用いられるパラメータ情報（符号テーブル等）を格納している。表示部１４は、ＣＰＵ１１から入力される指示に従って、情報をディスプレイ等に表示する。操作部１５は、ユーザの操作内容をＣＰＵ１１に出力する。
【００３１】
データ復号装置２の各部も同様の動作を行うもので、ＣＰＵ２１は、ハードディスク２３に格納されているプログラムに従って動作し、データの復号処理等を実行する。このデータの復号処理については、後に詳しく述べる。記憶部２２は、ＣＰＵ２１のワークメモリとして動作する。ハードディスク２３は、ＣＰＵ２１により実行されるプログラムや、ＣＰＵ２１のプログラム実行時に用いられるパラメータ情報（符号テーブル等）を格納している。ここで格納している符号化テーブルは、一般にはデータ符号化装置１のハードディスク１３に格納されているものと同じものである。表示部２４は、ＣＰＵ２１から入力される指示に従って、情報をディスプレイ等に表示する。操作部２５は、ユーザの操作内容をＣＰＵ２１に出力する。
【００３２】
［符号テーブル］
ここで、ハードディスク１３やハードディスク２３に格納されている符号テーブルの具体的な内容について説明する。この符号テーブルは、データの符号化単位であるデータ要素と符号語とを対応づけるものである。本実施の形態において特徴的なことは、符号テーブルを複数備え、各符号テーブル間で、１つのデータ要素に対し、相異なる符号語の対応付けを許容して定義していることである。また、本実施の形態においては、データをグループに分類し、当該グループをデータ要素とする符号テーブル（付加情報を利用する符号化のための符号テーブル）と、データを構成する要素そのものをデータ要素とする符号テーブル（付加情報を用いない、通常の符号化のための符号テーブル）とを含んでいる。
【００３３】
つまり、本実施の形態の符号テーブルは、例えば図２に示すように、グループをデータ要素とする第１符号テーブルと、データの構成要素そのものをデータ要素とする第２符号テーブルとを備える（図２では、これらの符号テーブルを連結した１つのテーブルファイルとして図示しているが、別のテーブルファイルとしてハードディスク内に格納してもよい）。図２の例では、第１符号テーブルは、ｎ〜ｎ＋７までのデータが属するグループをデータ要素として、符号ｘｘを対応付けている。また、第２符号テーブルではｎ＋４のデータをデータ要素として、符号ｙｙを対応付けている。さらに第１符号テーブルにおいては、グループに属するデータの種類の数（ｎ〜ｎ＋７の８個）に応じ、各データを区別するための付加情報に必要となるビット数として３ビット（８個あるデータのどれかを表現すればよいので３ビットとなる）を関連づけており、第２符号テーブルでは、付加情報を要しないので、付加情報として必要なビット数として０ビットを関連づけている。
【００３４】
従って、本実施の形態の符号テーブルによると、符号化の単位であるデータ要素からなる数学的空間（データ要素空間）と、符号語からなる数学的空間（符号語空間）との間の写像は、データ要素空間の各要素から符号語空間の各要素へは１：Ｎで写るのに対し、符号語空間の各要素からデータ要素空間の各要素への写像はＮ：１となる（図３）。
【００３５】
［符号化処理］
次に、データ符号化装置１のＣＰＵ１１により実行される符号化処理について説明する。ＣＰＵ１１により実行される符号化プログラムは、機能的には、図４に例示するような機能ブロック図で表すことができる。すなわち、この符号化プログラムは、データ入力部３１と、第１符号テーブル参照部３２と、第２符号テーブル参照部３３と、符号選択部３４と、付加情報生成部３５と、出力部３６と、を含んで構成される。なお、テーブル参照部は、ハードディスク１３に格納されている符号テーブルの数に応じて設けられる。ここでは、図２に示した２つの符号テーブルがある場合を例として説明する。
【００３６】
データ入力部３１は、符号化の対象となる一連のデータを記憶部１２に読込み、各符号化対象データを順次、第１符号テーブル参照部３２と、第２符号テーブル参照部３３とに出力する。第１符号テーブル参照部３２は、ハードディスク１３に格納されている第１符号化テーブルを参照し、データ入力部３１から入力された符号化対象データに対応するデータ要素を決定し（当該入力された符号化対象データがどのグループに属するかを判断して）、そのデータ要素に対応付けられた符号語を符号選択部３４に出力する。
【００３７】
また第２符号テーブル参照部３３は、ハードディスク１３に格納されている第２符号化テーブルを参照し、データ入力部３１から入力された符号化対象データに対応するデータ要素を決定し（当該符号化対象データそのものをデータ要素として決定し）、そのデータ要素に対応付けられた符号語を符号選択部３４に出力する。これらの第１符号テーブル参照部３２及び第２符号テーブル参照部３３が本発明の検索手段に相当する。
【００３８】
符号選択部３４は、本発明の選択手段に相当するもので、第１符号テーブル参照部３２と第２符号テーブル参照部３３とからそれぞれ入力される符号語のうち、一方を所定の条件に基づいて選択して付加情報生成部３５と出力部３６とに出力する。ここで所定の条件としては、例えば符号語の長さが短いものを選択するとの条件とする。
【００３９】
また、ここではこれらの符号テーブル参照部３２，３３がそれぞれ符号語を出力することとしているが、符号テーブルの構成によっては、あるデータ要素に対応する符号語が第１符号テーブルにのみ存在するという場合もある。この場合、第２符号テーブル参照部３３は、符号語を検索できないため、無効データを出力するようにすればよい。そして符号選択部３４は、無効データを無視して、符号語を選択するようにすればよい。すなわち第１符号テーブル参照部３２と第２符号テーブル参照部３３とのうち、第２符号テーブル参照部３３が無効データを出力しているときには、第１符号テーブル参照部３２が出力する符号語を選択せざるを得ないから、当該第１符号テーブル参照部３２が出力する符号語を選択的に出力する。
【００４０】
付加情報生成部３５は、符号選択部３４から符号語の入力を受けるとともに、データ入力部３１から符号化対象データの入力を受けて、当該入力された符号語と符号化対象データとを参照し、付加情報が必要か否かを判断し、必要であれば付加情報を生成して出力部３６に出力する。
【００４１】
出力部３６は、符号選択部３４から入力される符号語を符号データとして所定の出力先（例えばハードディスク１３）に出力する。この出力部３６は、符号語に対応する付加情報が付加情報生成部３５から入力されたときには、符号語と付加情報とからなる付加情報表現符号データを符号データとして出力し、付加情報が入力されない場合には、符号語からなる通常表現符号データを符号データとして出力する。
【００４２】
すなわち、このデータ符号化プログラムを実行するＣＰＵ１１は、操作部１５を介してユーザからハードディスク１３内のデータファイルの内容を符号化する指示を受けて、当該データファイルから一連の符号化対象データを読込んで記憶部１２に格納し、各符号化対象データを順次取り出して、当該符号化対象データに対応するデータ要素を決定し、そのデータ要素に対応する符号語をハードディスク１３内の第１符号テーブル及び第２符号テーブルから検索する。そして、第１符号テーブルから検索された第１符号語と、第２符号テーブルから検索された第２符号語とのうち、所定の条件（例えばいずれか短い語長を有するとの条件）に基づき一方の符号語を選択し、選択した符号語が付加情報を要するものであれば（上記の例で言えば、第１符号語であった場合）、付加情報を当該符号語と元の符号化対象データとから演算して、符号語と付加情報とからなる付加情報表現符号データを出力する。そして、未処理の符号化対象データがあるか否かを判断し、未処理のものがあれば、さらに当該符号化対象データについて符号テーブルを参照する処理から繰返す。また未処理のものがなければ、処理を終了する。
【００４３】
一方、選択した符号語が付加情報を有しないものであれば（上記の例で言えば、第２符号語であれば）、当該符号語を通常表現符号データとしてそのまま出力する。そして、未処理の符号化対象データがあるか否かを判断し、未処理のものがあれば、さらに当該符号化対象データについて符号テーブルを参照する処理から繰返す。また未処理のものがなければ、処理を終了する。従って、本実施の形態のデータ符号化装置１により生成される符号データは、一般には付加情報表現符号データと、通常表現符号データとを含んだものとなる。
【００４４】
［データ復号装置］
次に、本実施の形態のデータ復号装置２におけるデータ復号プログラムの処理について説明する。本実施の形態のデータ復号プログラムは、図５に機能的に示すように、符号データ入力部４１と、第１符号テーブル参照部４２と、第２符号テーブル参照部４３と、データ選択部４４と、付加情報演算部４５と、出力部４６とを含んで構成される。なお、テーブル参照部は、ハードディスク２３に格納されている符号テーブルの数に応じて設けられる。ここでは、図２に示した２つの符号テーブルがある場合を例として説明する。
【００４５】
符号データ入力部４１は、一連の符号データを記憶部２２に読込み、各符号データから符号語を抽出して、当該符号語を第１符号テーブル参照部４２と、第２符号テーブル参照部４３とに出力する。また、この符号データ入力部４１は、当該符号データに付加情報が含まれていれば、当該付加情報を付加情報演算部４５に出力する。
【００４６】
第１符号テーブル参照部４２は、ハードディスク２３に格納されている第１符号テーブルを参照し、符号データ入力部４１から入力された符号語を検索する。そして第１符号テーブルから当該入力された符号語が検索されれば、当該符号語に対応付けられているデータ要素をデータ選択部４４に出力する。また、符号語が検索されなければ、所定の無効データ（事前に定められたもの）をデータ選択部４４に出力する。
【００４７】
また第２符号テーブル参照部４３は、ハードディスク２３に格納されている第２符号化テーブルを参照し、符号データ入力部４１から入力された符号語を検索する。そして第２符号テーブルから当該入力された符号語が検索されれば、当該符号語に対応づけられたデータ要素をデータ選択部４４に出力する。また符号語が検索されなければ、所定の無効データ（事前に定められたもの）をデータ選択部４４に出力する。
【００４８】
データ選択部４４は、第１符号テーブル参照部４２と第２符号テーブル参照部４３とのいずれか一方から入力されるデータ要素（無効データでないものを選択すればよい）を付加情報演算部４５に出力する。なお、符号テーブルの構成によっては、各符号テーブル参照部から入力されるデータとして複数の無効データでないもの（有効なデータ要素）が含まれている可能性もある。しかし、符号テーブルは、１つの符号語については１つのデータ要素を対応付けるので、この場合有効なデータ要素は、いずれも同一のデータ要素となっているはずである。そこでこの場合、データ選択部４４は、入力された有効なデータ要素のいずれかを任意に（例えば最初に入力されたものとしてもよいし、各符号テーブル参照部に優先順位を割当てておき、その優先順位順としてもよい）選択して出力することとすればよい。
【００４９】
付加情報演算部４５は、データ選択部４４からデータ要素の入力を受けて、これを保持し、符号データ入力部４１から付加情報が入力されていれば、データ要素と当該付加情報とに基づき符号化前のデータ（符号化対象データ）を再現して出力部４６に出力する。また、この付加情報演算部４５は、符号データ入力部４１から付加情報が入力されていなければ、保持したデータ要素をそのまま符号化前のデータ（符号化対象データ）として出力部４６に出力する。出力部４６は、付加情報演算部４５から入力されるデータを所定の出力先（例えばハードディスク２３）に出力する。
【００５０】
すなわち、このデータ復号プログラムを実行するＣＰＵ２１は、操作部２５を介して一連の符号データを含む符号データファイルから、元のデータファイルを復号する旨の指示を受けて、当該符号データファイルに含まれる一連の符号データを読込んで記憶部２２に格納する。そして、読込んだ一連の符号データから順次、各符号データを取り出して注目符号データとし、当該注目符号データから符号語を抽出する。また、この注目符号データに付加情報が含まれていれば、それを保持する。
【００５１】
ＣＰＵ２１は、ハードディスク２３に格納されている第１符号テーブルを参照し、第１符号テーブル内から上記抽出した符号語を検索する。ここで第１符号テーブルに当該符号語が含まれていれば、つまり第１符号テーブルにて当該符号語とデータ要素とが対応づけられていれば、当該対応付けられたデータ要素を第１候補として保持する。また、第１符号テーブル内から上記抽出した符号語が検索されなければ、無効データを第１候補として保持する。
【００５２】
ＣＰＵ２１は、さらにハードディスク２３に格納されている第２符号テーブルを参照し、第２符号テーブル内から上記抽出した符号語を検索する。ここで第２符号テーブルに当該符号語が含まれていれば、つまり第２符号テーブルにて当該符号語とデータ要素とが対応付けられていれば、当該対応付けられたデータ要素を第２候補として保持する。また、第２符号テーブル内から上記抽出した符号語が検索されなければ、無効データを第２候補として保持する。
【００５３】
そしてＣＰＵ２１は、第１候補と第２候補とのうち、無効データでない方を有効なデータ要素とする。また、ＣＰＵ２１は、注目符号データに付加情報が含まれており、当該付加情報を保持しているときには、その付加情報と上記有効なデータ要素とに基づき、元のデータを再現してハードディスク２３に書き出す。一方、ＣＰＵ２１は、注目符号データに付加情報が含まれておらず、付加情報を保持していないときには、上記有効なデータ要素をそのまま元のデータとしてハードディスク２３に書き出す。
【００５４】
ＣＰＵ２１は、さらに未だ取り出していない符号データがあるか否かを調べ、未だ取り出していない符号データがあれば、当該符号データを注目符号データとして上記処理を繰返す。また、未だ取り出していない符号データがなくなれば（一連の符号データのすべてについて上記処理を完了すれば）、処理を終了する。
【００５５】
こうして、ハードディスク２３には、符号化前のデータ（一連の符号化対象データを含んでなるデータファイル）が作成される。
【００５６】
［動作］
次に、本実施の形態に係るデータ処理システムでのデータ符号化装置１の動作と、データ復号装置２の動作とをそれぞれ説明する。まず、データ符号化装置１の動作について説明する。なお、以下の説明においては、データ符号化装置１のハードディスク１３とデータ復号装置２のハードディスク２３とには、いずれも図２に示した符号テーブルが格納されているものとする。
【００５７】
具体的に入力される一連の符号化対象データが、「ｎ」，「ｎ＋４」，「ｎ＋７」であるとする。データ符号化装置１は、まず符号化対象データ「ｎ」について、第１符号テーブルと第２符号テーブルとから検索する。第１符号テーブルについては、そのグループ分けから、「ｎ」がデータ要素「ｎ〜ｎ＋７」のグループに属すると判断し、当該データ要素「ｎ〜ｎ＋７」に対応付けられた符号語「ｘｘ」が得られる。一方、第２符号テーブルについては、符号化対象データ「ｎ」そのものに対応する符号語を検索しても、当該エントリがないので、これを無効データとする。従って、符号化対象データ「ｎ」は、符号語「ｘｘ」となる。そして、この符号語「ｘｘ」に対応する複数のデータの種類のどれであるかを判別させるための付加情報（例えば「０００」）が生成され、これが符号語に連接されて「ｘｘ０００」なる符号データがハードディスク１３に書込まれる。
【００５８】
続いて「ｎ＋４」なる符号化対象データについて、第１符号テーブルからは符号語「ｘｘ」が得られ、この場合、（第１符号テーブルから）付加情報３ビットを要することがわかる。また、第２符号テーブルからは符号語「ｙｙ」が得られ、この場合、付加情報は０ビットであることがわかる。従って、付加情報表現符号データであれば「ｘｘ１００」となり、通常表現符号データであれば「ｙｙ」となるから、例えば符号長の短いものを選択する場合、「ｎ＋４」の符号化対象データは、「ｙｙ」と符号化され、「ｘｘ０００」の符号データに追記してハードディスク１３に書込まれる。
【００５９】
同様に「ｎ＋７」なる符号化対象データについて、第１符号テーブルからは符号語「ｘｘ」と付加情報「１１１」の３ビットとの合計５ビットの符号データが得られ、第２符号テーブルからは６ビットの符号語「ｚｚｚｚｚｚ」が得られるから、「ｎ＋７」の符号化対象データは、「ｘｘ１１１」と符号化される。こうして、一連の符号データ、「ｘｘ０００，ｙｙ，ｘｘ１１１」を含んだ符号化データファイルがハードディスク１３に格納されているようになる。
【００６０】
そして、データ復号装置２においてこれを復号する場合、各符号データが第１、第２の符号テーブルから参照され、まず、「ｘｘ０００」については符号語「ｘｘ」と付加情報「０００」とに分けられ符号語「ｘｘ」に対応するデータ要素「ｎ〜ｎ＋７」が第１符号テーブルから得られる（このとき第２符号テーブルを参照して得られるのは無効データとなる）。そして、このデータ要素と付加情報とから「ｎ」が再現されハードディスク２３に書込まれる。
【００６１】
次に符号データ「ｙｙ」は符号語「ｙｙ」のみであるので、これに対応するデータ要素「ｎ＋４」が第２符号テーブルから得られ、このデータ要素がそのまま元のデータとしてハードディスク２３に追記される。符号データ「ｘｘ１１１」についても同様にして処理され、「ｎ＋７」が得られる。そうして、ハードディスク２３に「ｎ，ｎ＋４，ｎ＋７」というデータが再現される。
【００６２】
またここまでの説明では、データ符号化装置１における、符号選択部３４が所定の条件として符号長の短いものを選択するとしていたが、各符号テーブルに事前に優先順位を設けておき、この優先順位に従って、符号語を選択するようにしてもよい。これにより符号長の比較処理がなくなるので、処理効率を改善できる。このときあるデータ要素に対してより短い符号語を持つ符号テーブルが優先されるように配置しておけば、圧縮率が悪化することはない。
【００６３】
このように本実施の形態によれば１つのデータ要素に対して２以上の符号語を対応可能にする（対応させることを許容する）よう構成したので、各データ要素の出現確率分布にかかわらず、圧縮率を高く保ったまま、付加ビット表現による小さい符号テーブルを用いた符号化及び復号化処理を実現でき、実装が容易になる。
【００６４】
［選択情報を含める例］
なお、ここまでの説明では、復号処理の際に、各符号テーブルから復号の対象となった符号語を検索し、検索の結果得られたデータ要素のいずれかを選択するようにしていたが、符号化処理の段階で、どの符号テーブルの符号語を選択したかを表す選択情報を各符号語との関係において出力しておき、復号の処理において、この選択情報を参照して符号語を検索する符号テーブルを決定してもよい。
【００６５】
この場合、データ符号化プログラムでは、符号選択部３４が、選択した符号語に対応する符号テーブルを識別する情報を選択情報として出力部３６に出力し、出力部３６が各符号データ（付加情報表現符号データ又は通常表現符号データ）に選択情報を関連づけて出力する。そのため、符号化されたデータには、一連の符号データと選択情報との組が含まれることとなる。
【００６６】
また、この場合のデータ復号プログラムは、符号データ入力部４１が注目符号データに関連づけられた選択情報に基づき、当該注目符号データに含まれる符号語を第１符号テーブル参照部４２又は第２符号テーブル参照部４３のいずれかに選択的に出力する。そして、第１符号テーブル参照部４２又は第２符号テーブル参照部４３のうち、符号語の入力を受けた側が、当該符号語に対応するデータ要素をデータ選択部４４に出力するようになる。この場合データ選択部４４は、当該入力されたデータ要素をそのまま付加情報演算部４５に出力するだけとなるので、データ選択部４４は必ずしも必要でない。すなわち、データ選択部４４を省略することによりプログラムの構成をより簡略化でき、実装がより容易になる。
【００６７】
なお、符号選択部３４と符号データ入力部４１とにおいて選択情報の解釈には、予め整合をとっておく必要がある。これには例えば選択情報を２値表現し、次のデータが０であれば第１符号テーブルから符号語を選択したことを、１であれば第２符号テーブルから符号語を選択したことを表す、といったように決めておけばよい。
【００６８】
［符号語選択の条件の他の例］
さらに上述の例では、符号選択部３４は、符号長や事前に定めた優先順位に従って符号語の選択を行うこととしていたが、各データ要素ごとに外部からどちらの符号語を選択するかの情報（サイド情報）の入力を受けて、このサイド情報に基づき符号選択部３４が符号語を選択するようにしてもよい。この場合、当該サイド情報を復号の際にも利用できるように、上述の選択情報としてデータに含めたり、又は、サイド情報のみを別途保持して、この復号処理においてデータ選択部４４が当該サイド情報を参照できるようにしておく必要がある。
【００６９】
この場合、サイド情報によって圧縮率が変動してしまうので、圧縮率を極端に落としたくない場合は、同一のデータに極端に異なる符号長の符号語を割り振らないようにするといった設計が必要となる。
【図面の簡単な説明】
【図１】本発明の実施の形態に係るデータ処理システムの構成ブロック図である。
【図２】本発明の実施の形態に係る符号テーブルの一例を表す説明図である。
【図３】本発明の実施の形態における符号語空間とデータ要素空間との関係を表す説明図である。
【図４】本発明の実施の形態に係るデータ符号化プログラムの機能ブロック図である。
【図５】本発明の実施の形態に係るデータ復号プログラムの機能ブロック図である。
【符号の説明】
１データ符号化装置、２データ復号装置、１１，２１ＣＰＵ、１２，２２記憶部、１３，２３ハードディスク、１４，２４表示部、１５，２５操作部、３１データ入力部、３２，４２第１符号テーブル参照部、３３，４３第２符号テーブル参照部、３４符号選択部、３５付加情報生成部、３６，４６出力部、４１符号データ入力部、４４データ選択部、４５付加情報演算部。

Claims

データの符号化単位であるデータ要素と符号語とを対応づける複数の符号テーブルであって、各符号テーブル間で、１つのデータ要素に対し、相異なる符号語の対応付けを許容して定義された符号テーブルを保持する手段と、
複数のデータ要素を含む符号化対象データについて、符号化対象データに含まれる各データ要素を抽出し、当該抽出されたデータ要素に対応する符号語が関連づけられたＮ個（Ｎは２以上の整数）の符号テーブルを検索する検索手段と、
前記Ｎ個の符号テーブルのうち、データ要素を最短の符号語に関連づけている１つの符号テーブルを選択し、当該選択した符号テーブルにおいて、前記抽出されたデータ要素に関連づけられた符号語を出力する選択手段と、
前記選択した符号語が対応するデータ要素の中で、前記複数の符号テーブルにおいて前記選択された符号語が異なる複数のデータ要素に対応付けられている場合に前記選択された符号語が対応するデータ要素を特定するための付加情報を必要に応じて生成する手段と、
を含み、
符号化対象データに含まれる各データ要素を、符号語と付加情報とからなる付加情報表現符号データ又は、符号語からなる通常表現符号データのいずれかに変換することを特徴とするデータ符号化装置。
データの符号化単位であるデータ要素と符号語とを対応づける複数の符号テーブルであって、各符号テーブル間で、１つのデータ要素に対し、相異なる符号語の対応付けを許容して定義された符号テーブルを保持する手段と、
複数のデータ要素を含む符号化対象データについて、符号化対象データに含まれる各データ要素を抽出し、当該抽出されたデータ要素に対応する符号語が関連づけられたＮ個（Ｎは２以上の整数）の符号テーブルを検索する検索手段と、
前記Ｎ個の符号テーブルのうち、データ要素を最短の符号語に関連づけている１つの符号テーブルを選択し、当該選択した符号テーブルにおいて、前記抽出されたデータ要素に関連づけられた符号語を出力する選択手段と、
前記選択した符号語が対応するデータ要素の中で、前記複数の符号テーブルにおいて前記選択された符号語が異なる複数のデータ要素に対応付けられている場合に前記選択された符号語が対応するデータ要素を特定するための付加情報を必要に応じて生成する手段と、
を含み、
符号化対象データに含まれる各データ要素を、符号語と付加情報とからなる付加情報表現符号データ又は、符号語からなる通常表現符号データのいずれかに変換することを特徴とするデータ符号化装置。
データの符号化単位であるデータ要素と符号語とを対応づける複数の符号テーブルであって、各符号テーブル間で、１つのデータ要素に対し、相異なる符号語の対応付けを許容して定義された符号テーブルを保持する手段と、
複数のデータ要素を含む符号化対象データについて、符号化対象データに含まれる各データ要素を抽出し、当該抽出されたデータ要素に対応する符号語が関連づけられたＮ個（Ｎは２以上の整数）の符号テーブルを検索する検索手段と、
所定の基準に基づき、前記Ｎ個の符号テーブルから１つの符号テーブルを選択し、当該選択した符号テーブルにおいて、前記抽出されたデータ要素に関連づけられた符号語を出力すると共に、各符号語に関連づけて、前記選択した符号テーブルを特定する選択情報を出力する選択手段と、
前記選択した符号語が対応するデータ要素の中で、前記複数の符号テーブルにおいて前記選択された符号語が異なる複数のデータ要素に対応付けられている場合に前記選択された符号語が対応するデータ要素を特定するための付加情報を必要に応じて生成する手段と、
を含み、
符号化対象データに含まれる各データ要素を、符号語と付加情報とからなる付加情報表現符号データ又は、符号語からなる通常表現符号データのいずれかに変換することを特徴とするデータ符号化装置。
データの符号化単位であるデータ要素と符号語とを対応づける複数の符号テーブルであって、各符号テーブル間で、１つのデータ要素に対し、相異なる符号語の対応付けを許容して定義された符号テーブルを保持する手段と、
請求項１に記載のデータ符号化装置により符号化されて得られた一連の符号データから各符号データを順次取り出し、当該取り出した符号データに含まれる符号語を抽出し、前記データ符号化装置が当該抽出した符号語との関係において出力した選択情報に基づいて前記複数の符号テーブルから１つの符号テーブルを選択し、前記抽出した符号語に対応するデータ要素を前記選択した符号テーブルから検索する手段と、
前記取り出した符号データが付加情報表現符号データであるときに、当該符号データから付加情報を取り出し、前記検索されたデータ要素と当該取り出した付加情報とにより、符号化前のデータ要素を復号する手段と、
を含むことを特徴とするデータ復号装置。
データの符号化単位であるデータ要素と符号語とを対応づける複数の符号テーブルであって、各符号テーブル間で、１つのデータ要素に対し、相異なる符号語の対応付けを許容して定義された符号テーブルを用い、
複数のデータ要素を含む符号化対象データについて、符号化対象データに含まれる各データ要素を抽出し、当該抽出されたデータ要素に対応する符号語が関連づけられたＮ個（Ｎは２以上の整数）の符号テーブルを検索する工程と、
前記Ｎ個の符号テーブルのうち、データ要素を最短の符号語に関連づけている１つの符号テーブルを選択し、当該選択した符号テーブルにおいて、前記抽出されたデータ要素に関連づけられた符号語を出力する工程と、
前記選択した符号語が対応するデータ要素の中で、前記複数の符号テーブルにおいて前記選択された符号語が異なる複数のデータ要素に対応付けられている場合に前記選択された符号語が対応するデータ要素を特定するための付加情報を必要に応じて生成する工程と、
を含み、
符号化対象データに含まれる各データ要素を、符号語と付加情報とからなる付加情報表現符号データ又は、符号語からなる通常表現符号データのいずれかに変換することを特徴とするデータ符号化方法。
データの符号化単位であるデータ要素と符号語とを対応づける複数の符号テーブルであって、各符号テーブル間で、１つのデータ要素に対し、相異なる符号語の対応付けを許容して定義された符号テーブルを用い、
請求項５に記載のデータ符号化方法により符号化されて得られた一連の符号データから各符号データを順次取り出し、当該取り出した符号データに含まれる符号語を抽出し、前記データ符号化装置が当該抽出した符号語との関係において出力した選択情報に基づいて前記複数の符号テーブルから１つの符号テーブルを選択し、前記抽出した符号語に対応するデータ要素を前記選択した符号テーブルから検索する工程と、
前記取り出した符号データが付加情報表現符号データであるときに、当該符号データから付加情報を取り出し、前記検索されたデータ要素と当該取り出した付加情報とにより、符号化前のデータ要素を復号する工程と、
を含むことを特徴とするデータ復号方法。
データの符号化単位であるデータ要素と符号語とを対応づける複数の符号テーブルであって、各符号テーブル間で、１つのデータ要素に対し、相異なる符号語の対応付けを許容して定義された符号テーブルを用い、コンピュータに、
複数のデータ要素を含む符号化対象データについて、符号化対象データに含まれる各データ要素を抽出し、当該抽出されたデータ要素に対応する符号語が関連づけられたＮ個（Ｎは２以上の整数）の符号テーブルを検索する手順と、
前記Ｎ個の符号テーブルのうち、データ要素を最短の符号語に関連づけている１つの符号テーブルを選択し、当該選択した符号テーブルにおいて、前記抽出されたデータ要素に関連づけられた符号語を出力する手順と、
前記選択した符号語が対応するデータ要素の中で、前記複数の符号テーブルにおいて前記選択された符号語が異なる複数のデータ要素に対応付けられている場合に前記選択された符号語が対応するデータ要素を特定するための付加情報を必要に応じて生成する手順と、
を実行させ、
符号化対象データに含まれる各データ要素を、符号語と付加情報とからなる付加情報表現符号データ又は、符号語からなる通常表現符号データのいずれかに変換することを特徴とするデータ符号化プログラム。
データの符号化単位であるデータ要素と符号語とを対応づける複数の符号テーブルであって、各符号テーブル間で、１つのデータ要素に対し、相異なる符号語の対応付けを許容して定義された符号テーブルを用い、コンピュータに、
請求項７に記載のデータ符号化プログラムにより符号化されて得られた一連の符号データから各符号データを順次取り出し、当該取り出した符号データに含まれる符号語を抽出し、前記データ符号化装置が当該抽出した符号語との関係において出力した選択情報に基づいて前記複数の符号テーブルから１つの符号テーブルを選択し、前記抽出した符号語に対応するデータ要素を前記選択した符号テーブルから検索する手順と、
前記取り出した符号データが付加情報表現符号データであるときに、当該符号データから付加情報を取り出し、前記検索されたデータ要素と当該取り出した付加情報とにより、符号化前のデータ要素を復号する手順と、
を実行させることを特徴とするデータ復号プログラム。