(57)【要約】【課題】可変長符号化において、可変長符号ハッシュテーブルのメモリ量を小さくするとともに、演算量を少なくする。【解決手段】原データに基づくキーデータ（ＲＵＮ，ＬＥＶＥＬ，ＬＡＳＴ）に、ハッシュ演算手段１０２で、演算量の少ない第１のハッシュ演算を施して、ＶＬＣハッシュテーブル１０３のアドレスを直接求める。このアドレスでＶＬＣハッシュテーブル１０３を引いてテーブル情報を取得し、テーブル分離手段で、テーブル情報を分離して、２次キー（ＫＥＹ２）を得る。このＫＥＹ２と、キーデータから算出した２次キーを比較することにより、キーデータに対応するテーブル情報か否かを判定する。一致した場合は、可変長符号と符号長さを得ることができる。ＶＬＣハッシュテーブル１０３に２次キーを格納しておくことにより、テーブルのメモリ量を小さくしている。シノニムが発生しないハッシュ演算を用いているので、シノニム対策が不要である。【選択図】　　　図１
2004096692.tif 000002
【特許請求の範囲】
【請求項１】
可変長符号ハッシュテーブルを参照してデータを可変長符号に変換する可変長符号化装置において、原データの０の連続数であるＲＵＮ値の範囲をチェックするＲＵＮ範囲チェック手段と、前記原データの０でない数値のレベルを表すＬＥＶＥＬ値の範囲をチェックするＬＥＶＥＬ範囲チェック手段と、前記原データの最後か否かを示す識別子であるＬＡＳＴ値とＲＵＮ値とＬＥＶＥＬ値との組であるキーデータに第１のハッシュ演算を施してテーブルアドレスを算出するハッシュ演算手段と、前記キーデータに第２のハッシュ演算を施して２次キーを算出する２次ハッシュ演算手段と、可変長符号部と２次キー部とを含むテーブル情報を格納した可変長符号ハッシュテーブルと、前記テーブル情報を個別の情報に分離するテーブル分離手段と、前記２次キーと前記テーブル情報中の２次キー部とを比較するキー比較手段とを具備することを特徴とする可変長符号化装置。
【請求項２】
前記ＲＵＮ範囲チェック手段と前記ＬＥＶＥＬ範囲チェック手段と前記ハッシュ演算手段と前記２次ハッシュ演算手段とを２組備え、ＬＡＳＴ値に応じて前記２組のいずれか１組を選択する切替手段とを備えたことを特徴とする請求項１に記載の可変長符号化装置。
【請求項３】
前記ハッシュ演算手段は、前記第１のハッシュ演算の結果が所定の上限値以下であることをチェックする上限チェック手段を備え、前記上限チェック手段の結果が上限値以下であるときは前記可変長符号ハッシュテーブルのサイズを前記上限値に等しくすることを特徴とする請求項１または２に記載の可変長符号化装置。
【請求項４】
前記可変長符号ハッシュテーブルは制御ビット付可変長符号部と２次キー部とからなるテーブル情報を格納し、前記制御ビット付可変長符号部からコード長を算出する可変長符号長算出手段を備えたことを特徴とする請求項１〜３のいずれかに記載の可変長符号化装置。
【請求項５】
可変長符号ハッシュテーブルを参照してキーデータを可変長符号に変換する可変長符号化方法において、原データの０の連続数であるＲＵＮ値の範囲のチェックを行い、原データの０でない数値のレベルを表すＬＥＶＥＬ値の範囲のチェックを行い、原データの最後か否かを示す識別子であるＬＡＳＴ値とＲＵＮ値とＬＥＶＥＬ値との組であるキーデータに第１のハッシュ演算を施してテーブルアドレスを算出し、前記キーデータに第２のハッシュ演算を施して２次キーを算出し、可変長符号部と２次キー部とを含むテーブル情報を格納した可変長符号ハッシュテーブルを前記テーブルアドレスで参照し、前記テーブル情報を個別の情報に分離し、前記２次キーと前記テーブル情報中の２次キー部とを比較し、一致すれば前記可変長符号部を出力することを特徴とする可変長符号化方法。
【請求項６】
前記ＬＡＳＴ値が０か１かに応じて、前記キーデータに対して異なるＲＵＮ値の範囲のチェックと異なるＬＥＶＥＬ値の範囲のチェックと異なる第１のハッシュ演算処理と異なる第２のハッシュ演算処理とを行うことを特徴とする請求項５に記載の可変長符号化方法。
【請求項７】
前記第１のハッシュ演算の結果が所定の上限値以下であることをチェックし、前記上限値を超えていなければ、第１のハッシュ演算の結果をテーブルアドレスとして、前記上限値と同じサイズの可変長符号ハッシュテーブルを参照することを特徴とする請求項５または６に記載の可変長符号化方法。
【請求項８】
前記可変長符号部に制御ビットを付加して前記可変長符号ハッシュテーブルに格納しておき、制御ビットを付加した可変長符号部からコード長を算出することを特徴とする請求項５〜７のいずれかに記載の可変長符号化方法。
【請求項９】
請求項５〜８のいずれかに記載の可変長符号化方法をコンピュータによって実行するための手順を記述したことを特徴とするコンピュータプログラム。
【請求項１０】
請求項９に記載のコンピュータプログラムを記録したことを特徴とする記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ハッシュによる可変長符号化装置に関し、特に、画像圧縮処理などにおいて、可変長符号テーブルを用いてデータを可変長符号に変換するハッシュによる可変長符号化装置に関する。
【０００２】
【従来の技術】
画像情報は、非常に情報量が多いので、大量の画像情報をリアルタイムに送信することは、非常に困難である。そのため、画像データを圧縮して送信し、受信側で伸長するという技術が用いられている。画像データの典型的な圧縮方法として、出現頻度の高いビットパターンに短い符号を割り当て、出現頻度の低いビットパターンには長い符号を割り当てるという可変長符号化方法がある。画像データを高能率に符号化する技術として、ＤＣＴ（Ｄｉｓｃｒｅｔｅ　Ｃｏｓｉｎｅ　Ｔｒａｎｓｆｏｒｍ：離散コサイン変換）と、可変長符号化を組み合わせた方式が標準化され、広く用いられている。画像圧縮化装置では、動き予測でデータそのものを平坦化し、さらにＤＣＴ処理および量子化処理によって、高周波成分を削減している。圧縮処理の対象となる画像信号には０が多く含まれるので、可変長符号テーブルを用いることにより、効率よく画像信号を圧縮できる。また、テーブルを参照してデータ変換するので、複雑な処理も不要で、高速な符号化処理ができる。
【０００３】
画像データの圧縮方法を一般的に良く知られている動画像符号化標準であるＭＰＥＧ−１（Ｍｏｖｉｎｇ　Ｐｉｃｔｕｒｅ　Ｅｘｐｅｒｔｓ　Ｇｒｏｕｐｅ）を例に取り、簡単に説明する。画像データを、離散コサイン変換して、周波数成分のデータに変換し、高周波成分を小さくする量子化処理を行う。量子化されたデータは、ＲＵＮデータとＬＥＶＥＬデータとに変換される。ＬＥＶＥＬデータは、０でないデータのレベルを表す。ＲＵＮデータは、０でないデータの後に続く０のデータ数である。高周波成分には０が多く含まれるので、ＲＵＮレングス変換を用いて効率よく圧縮できる。ＲＵＮデータとＬＥＶＥＬデータは、（ＲＵＮ，ＬＥＶＥＬ）の形式に変換される。この（ＲＵＮ，ＬＥＶＥＬ）データを、可変長符号に変換する。すなわち、ＲＵＮデータおよびＬＥＶＥＬデータをアドレスとして、テーブルをアクセスすることにより、対応する可変長符号とその符号長データを読み出して、可変長符号を生成する。
【０００４】
可変長符号テーブルには、アドレスに対応する可変長符号データが格納されている。可変長符号データの格納領域には、（ＲＵＮ，ＬＥＶＥＬ）の組合せに対応する可変長符号を格納する可変長符号領域（１７ビット幅）と、可変長符号領域に格納されている可変長符号の長さを特定する情報を格納する５ビット幅の符号長領域とがある。可変長符号データをアクセスするためのアドレスは、６ビットのＲＵＮ領域と７ビットのＬＥＶＥＬ領域とからなる１３ビットのアドレスである。ＲＵＮデータとＬＥＶＥＬデータからアドレスを生成し、そのアドレスで可変長符号テーブルメモリをアクセスすることにより、対応する可変長符号データを得る。
【０００５】
アドレスのうち、ＲＵＮに６ビット、ＬＥＶＥＬに７ビットが割り当てられているのは、画像符号化標準方式ＭＰＥＧ１（Ｍｏｖｉｎｇ　Ｐｉｃｔｕｒｅ　Ｅｘｐｅｒｔｓ　Ｇｒｏｕｐ　１）において、ＲＵＮの範囲が０〜６３であり、ＬＥＶＥＬの範囲が±４１であり、これらを表現するためには、それぞれ６ビットおよび７ビットが必要なためである。可変長符号領域が１７ビットで、符号長領域が５ビットなのは、可変長符号の最大長が１７ビットであるためである。なお、符号長領域が必要なのは、可変長符号の扱いには符号長も必要であり、可変長符号と合わせて、その可変長符号の符号長も出力する必要があるためである。テーブルに記載されていないＲＵＮとＬＥＶＥＬとの組合せは、可変長符号化器と異なる符号化器により別途処理される。
【０００６】
可変長符号は、２ビット〜１７ビットの範囲の符号長を有している。しかし、メモリの可変長符号領域の長さを、任意のビット長とすることは困難である。そのため、最大の符号長に合わせた固定長のフィールドを、一つの可変長符号データに割り付ける必要がある。したがって、１つの可変長符号の情報を格納するためには、２２ビット（可変長符号１７ビット＋符号長データ５ビット）のデータ領域が必要である。この可変長符号テーブルをメモリ上に展開するためには、少なくとも８ｋワード（（１３ビットアドレスのアドレス空間）×（２２ビット））のメモリが必要である。このように、可変長符号テーブルでは、処理されるＲＵＮおよびＬＥＶＥＬの組合せは２５６種程度しかないのに対し、メモリ上にテーブルを展開する場合には、８ｋワードの空間を必要とする。したがって、メモリ空間をより効率的に使用して、より少ないメモリで可変長符号化処理を行う必要がある。
【０００７】
前記ＭＰＥＧ−１は、（ＲＵＮ，ＬＥＶＥＬ）で可変長符号に変換するので、２次元ランレングス符号化と呼ばれている。次に、新しい動画像符号化標準のＭＰＥＧ−４（Ｍｏｖｉｎｇ　Ｐｉｃｔｕｒｅ　Ｅｘｐｅｒｔｓ　Ｇｒｏｕｐｅ）を例に取り説明する。データを可変長符号化するために、ＲＵＮデータとＬＥＶＥＬデータとＬＡＳＴデータにより、（ＲＵＮ，ＬＥＶＥＬ，ＬＡＳＴ）で可変長符号（ＶＬＣ：　Ｖａｒｉａｂｌｅ　Ｌｅｎｇｔｈ　Ｃｏｄｅ）テーブルを参照して、３次元ランレングスにより可変長符号を生成する。ＲＵＮデータは、０でないデータの後ろに続く０のデータ数である。ＬＥＶＥＬデータは、０でないデータのレベルである。ＬＡＳＴは、該当ＬＥＶＥＬがデータの最後かどうかを識別するものである。可変長符号テーブル（ＶＬＣテーブル）を参照する方式としては、一般的には、図１２に示すように、大きなメモリテーブルを用意し、ＲＵＮ，ＬＥＶＥＬ，ＬＡＳＴを並べて、ＶＬＣテーブルのアドレスを生成して、ＶＬＣテーブルを参照する。例えば、ＭＰＥＧ−４のＩＮＴＲＡ　ＶＬＣを例にとると、図１５に示すように、ＲＵＮは０〜２０の範囲の値を取るので、５ｂｉｔで表現可能であり、ＬＥＶＥＬは、１〜２７の範囲の値を取るので、５ｂｉｔで表現可能であり、ＬＡＳＴは、０〜１の範囲の値を取るので１ｂｉｔで表現可能である。これを並べると、５ｂｉｔ＋５ｂｉｔ＋１ｂｉｔ＝１１ｂｉｔのアドレス空間となる。ＭＰＥＧ−４の可変長符号は、２ビット〜１２ビットの範囲の符号長を有しているので、１つの可変長符号の情報を格納するためには、１６ビット（可変長符号１２ビット＋符号長データ５ビット）のデータ領域が必要である。この可変長符号テーブルをメモリ上に展開するためには、少なくとも２Ｋ×１６ビットのメモリが必要である。このように、可変長符号テーブルでは、処理される（ＲＵＮ，ＬＥＶＥＬ，ＬＡＳＴ）の組合せが１０２個程度しかないのに対して、メモリ上にテーブルを展開する場合には、２Ｋワードの空間を必要とし、メモリ空間をより効率的に使用して、より少ないメモリで可変長符号化処理を行う必要がある。
【０００８】
可変長符号テーブルのサイズを削減する方法を説明する。可変長符号の符号語の上位ビットは、同じ符号の繰返しパターンが多いという特徴があることから、可変長符号化装置においては、可変長符号テーブルに格納する符号語を、同じビットが繰り返されるパターンの長さと、残りの符号で表現している。この表現によると、例えばＭＰＥＧ１のＤＣＴ係数の符号を表すためには、繰返し回数の表現のために４ビット、残りのデータのために６ビット使用し、さらに、符号長を表現するために４ビット使用する。１符号あたりの全体の長さは、１４ビットとなっている。テーブルサイズを削減する方法として、特許文献１に開示された「可変長符号テーブルおよび可変長符号化装置」や、特許文献２に開示された「可変長符号化装置」のように、データ（例えばＬＥＶＥＬ）の値の範囲によって、ＲＵＮ，ＬＥＶＥＬをクラスに分類し、クラスごとにＶＬＣテーブルのアドレスを生成するｂｉｔの割付けを変える方法がある。
【０００９】
係数の値（ＬＥＶＥＬ）の範囲によって、４つのクラスに分類する。係数値０が続く数（ＲＵＮ）とＬＥＶＥＬの組合せに対応する可変長符号テーブルのアドレスを、クラスにより識別されるフラグ領域と、ＲＵＮを表す領域と、ＬＥＶＥＬを表す領域から構成される固定長の領域の数値とする。ＲＵＮとＬＥＶＥＬの領域の大きさは、それぞれのクラスに含まれる最大値を格納するのに必要な最小限の大きさに定めている。例えば、ＭＰＥＧ１のＤＣＴ係数の符号を表すためには、１１ビット使用している。具体的には、アドレスは、クラスにより識別されるフラグ領域と、ＬＡＳＴを表す領域と、ＲＵＮを表す領域と、ＬＥＶＥＬを表す領域により構成されている。全体として固定長でＶＬＣテーブルのアドレスを生成することによって、テーブルサイズを小さくしている。ＭＰＥＧ−４のＩＮＴＲＡ　ＶＬＣを例にとると、図１３に示すように、９種類のクラス（クラスＡ〜クラスＩ）に分類し、８ｂｉｔのアドレス空間で表現し、２５６個のテーブルで実現可能である。
【００１０】
特許文献１に開示された「可変長符号テーブルおよび可変長符号化装置」は、可変長符号メモリの容量を小さくするものである。ＭＰＥＧ１のＤＣＴ出力係数の可変長符号テーブルにおいて、ＲＵＮとＬＥＶＥＬとの組合せを、ＬＥＶＥＬの絶対値の大きさによりクラス別に分類する。対応の可変長符号のアドレスを、ＬＥＶＥＬの属するクラスにより、値と長さとがユニークに特定されるフラグ領域と、ＲＵＮデータ領域と、ＬＥＶＥＬデータの領域とを含む固定長とする。ＲＵＮとＬＥＶＥＬとの領域長は、それぞれＬＥＶＥＬのクラスごとに、当該クラスに含まれる組合せのＲＵＮデータの絶対値と、ＬＥＶＥＬデータの絶対値との、それぞれの最大値を格納するのに必要な最小限の大きさに定める。可変長符号を、先頭から連続する０の個数と、残りの符号と、残りの符号の符号長とに分けて、テーブルに格納することもできる。
【００１１】
特許文献２に開示された「可変長符号化装置」は、高速でハードウェア規模の小さい可変長符号化装置である。量子化ＤＣＴ係数をメモリから順に読み出し、可変長符号化する場合には、可変長符号テーブルアドレスを出力し、固定長符号化する場合には、符号語と符号長を出力する。量子化ＤＣＴ係数以外の情報についても、可変長符号化する場合には、可変長符号テーブルアドレスを出力し、固定長符号化する場合には、符号語と符号長を出力する。その際、可変長符号のアドレスを候補群から選択し、固定長符号の符号を候補群から選択する。固定長符号を遅延させ、可変長符号または固定長符号のいずれかを選択する。選択された符号を連ねて、符号列を形成する。
【００１２】
テーブルサイズを削減する別の方法として、特許文献３に開示された「ハッシュテーブル検索方法および装置」のように、演算量が少なくシノニムの発生しないハッシュ演算で、直接ＶＬＣテーブルのアドレスを生成することによって、テーブルサイズを小さくする方法がある。特許文献４に開示された「ハッシュテーブル検索方法および装置」は、テーブルに格納したデータをキー項目により高速に検索し、かつテーブル容量を小さくするものである。キー取得部は、ハッシュ計算部のハッシュ値により、ハッシュ表格納部からキーを取得する。キー一致判定部により、検索キーと比較することにより、検索対象のキーであるかを判定する。不一致の場合は、テーブル未登録と判断する。一致した場合は、シノニムが発生しないので、目的のキーとなる。データ取得部によりデータを取得して、データ格納部に格納する。ハッシュ計算部の演算量が少なく、シノニム対策が不要であるため、検索を高速化できる。また、ハッシュ表格納部の空きエリアを利用して、データそのものを格納しているため、テーブルの容量を小さく抑えられる。
【００１３】
検索キーをもとにテーブルを直接参照して検索する手法としては、検索キーをテーブルのアドレスに変換する写像であるハッシュ関数を利用する方法がある。ハッシュ関数は、検索キーの集合からアドレスの集合への多対１の写像である。検索の手順は、以下のようになる。検索キーＫからＨ（Ｋ）を計算して、アドレスＡを求める。アドレスＡで示されるテーブル中のキー項目が、検索キーＫに対応するものかをどうかを検証する。これは、複数の検索キーが同じアドレスに写像されるシノニムという衝突現象が発生するからである。シノニムが発生していない場合は、アドレスＡで示されるデータ項目が、検索結果のデータとなる。シノニムが発生した場合は、２次検索を行い、目的の検索キーが格納されたアドレスを再び求める。ハッシュ関数において、シノニムの発生を減らすために、テーブルの大きさＮを素数とする。２次検索の方法には、Ｈ（Ｋ）の値が同一のすべての項目をリストでつなぎ、そのリンクをたどって目的の検索キーに対応する項目を求める方法や、目的の検索キーに対応する項目が見つかるまで、アドレスに別のハッシュ値を加算する方法がある。
【００１４】
ハッシュテーブルの検索を高速化する方法として、２分木構造でキー管理を行う方法（特許文献５）や、副次関数を用いて衝突管理を行う方法がある。ハッシュ表管理では、キーの衝突が多数発生しても検索効率が低下しないように、同一のハッシュ値に変換された複数の異なるキーを、２分木構造でチェーンさせてハッシュ表に登録して検索する方式を採っている。特許文献６に開示された「ハッシュ表管理装置」は、ハッシュ表に対する検索処理性能を低下させないようにするものである。ハッシュ表のエントリーに対し、２分木構造でキーを管理する。登録手段は、検索手段によってハッシュ表を検索する。検索手段は、ハッシュ表検索を行うと同時に、２分木検索経路記録手段を作成する。登録手段は、未登録キーの登録時に、２分木バランス手段によって、２分木をバランスさせる。２分木バランス手段は、２分木検索経路記録手段によって、節の入れ換え処理を行い、２分木をバランスさせる。これにより、データの登録順序に関係なく、バランスのとれた２分木を作成する。
【００１５】
図１４を参照しながら、ハッシュテーブルの具体的な検索処理手順を説明する。ＲＵＮとＬＥＶＥＬの範囲チェックを行い、ＬＡＳＴ，ＲＵＮ，ＬＥＶＥＬをキーとしてハッシュ演算を行い、ＶＬＣハッシュテーブルのアドレスＡを算出する。ハッシュ演算は、例えば、
Ａ＝（ＬＥＶＥＬ＊２３＋ＲＵＮ＊３＋ＬＡＳＴ＊１７）ｍｏｄ　２５６
というものである。アドレスＡで、ＶＬＣハッシュテーブルを参照し、テーブルに格納されたキー部（ＬＡＳＴ，ＲＵＮ，ＬＥＶＥＬ）を取得し、ハッシュ演算に用いたキーと比較する。不一致であれば、可変長符号に定義されていない無効なキーである。一致していれば該当のキーであるので、ＶＬＣコードと長さを取得する。シノニムが発生しないハッシュ演算であるので、該当キーは一意に定まる。ＶＬＣハッシュテーブルは、ハッシュ演算によりアドレスの生成範囲を２５６以内としているので、テーブルの個数は２５６個であり、ＬＡＳＴ（１ｂｉｔ）＋ＲＵＮ（５ｂｉｔ）＋ＬＥＶＥＬ（５ｂｉｔ）＋ＶＬＣ（１２ｂｉｔ）＋コード長（４ｂｉｔ）の合計４ｂｙｔｅ×２５６エントリー＝１０２４ｂｙｔｅで実現可能である。
【００１６】
【特許文献１】
特開平８−７９０９１号公報
【特許文献２】
特開平１０−１９１３３６号公報
【特許文献３】
特開２０００−１０５７７０号公報
【特許文献４】
特開２０００−１０５７７０号公報
【特許文献５】
特開平１０−４０２５５号公報
【特許文献６】
特開平１０−４０２５５号公報
【００１７】
【発明が解決しようとする課題】
しかしながら、大きなメモリテーブルを用いる従来手法では、ＶＬＣテーブルが大きいため、回路で実現した場合は、高価な高速メモリを大量に必要とするという問題がある。また、ＤＳＰなどのプロセッサを用いてソフトウェアで実現する場合は、高速なオンチップのメモリ量が少なく、テーブルを格納することができず、低速なメモリに配置することになり、高速に可変長符号化することができないという問題がある。
【００１８】
また、クラスに分類し、固定長のアドレスを生成する従来手法では、クラスに分類し、アドレスを生成する演算量が大きいため、回路で実現した場合は、回路規模の増大を招くという問題がある。また、ＤＳＰなどのプロセッサを用いてソフトウェアで実現した場合は、処理手順が増大し、高速に可変長符号化できないという問題がある。
【００１９】
また、ハッシュを用いてアドレスを生成する従来手法では、アドレスを生成するハッシュ演算量は少ないが、ＶＬＣハッシュテーブルの削減が十分ではなく、回路で実現した場合は、高価な高速メモリを大量に必要とするという問題がある。また、ＤＳＰなどのプロセッサを用いてソフトウェアで実現した場合は、高速なオンチップのメモリ量が少なく、テーブルを格納することができず、低速なメモリに配置することになり、高速に可変長符号化することができないという問題がある。
【００２０】
本発明は、上記の従来の問題を解決して、ＶＬＣテーブルのメモリ量を小さくするとともに、少ない演算量で可変長符号化することを目的とする。
【００２１】
【課題を解決するための手段】
上記の課題を解決するために、本発明では、可変長符号ハッシュテーブルを参照してキーデータを可変長符号に変換する可変長符号化装置に、原データの０の連続数であるＲＵＮ値の範囲をチェックするＲＵＮ範囲チェック手段と、原データの０でない数値のレベルを表すＬＥＶＥＬ値の範囲をチェックするＬＥＶＥＬ範囲チェック手段と、原データの最後か否かを示す識別子であるＬＡＳＴ値とＲＵＮ値とＬＥＶＥＬ値との組であるキーデータに第１のハッシュ演算を施してテーブルアドレスを算出するハッシュ演算手段と、キーデータに第２のハッシュ演算を施して２次キーを算出する２次ハッシュ演算手段と、可変長符号部と２次キー部とを含むテーブル情報を格納した可変長符号ハッシュテーブルと、テーブル情報を個別の情報に分離するテーブル分離手段と、２次キーとテーブル情報中の２次キー部とを比較するキー比較手段とを具備する構成とした。このように構成したことにより、可変長符号ハッシュテーブルにキーデータそのものを格納しなくてよくなり、可変長符号ハッシュテーブルのメモリ量を小さくできる。
【００２２】
また、ＲＵＮ範囲チェック手段とＬＥＶＥＬ範囲チェック手段とハッシュ演算手段と２次ハッシュ演算手段とを２組備え、ＬＡＳＴ値に応じて２組のいずれか１組を選択する切替手段とを備えた。このように構成したことにより、可変長符号ハッシュテーブルのアドレス生成範囲を小さくして、可変長符号ハッシュテーブルのメモリ量を小さくできる。
【００２３】
また、ハッシュ演算手段に、第１のハッシュ演算の結果が所定の上限値以下であることをチェックする上限チェック手段を備え、可変長符号ハッシュテーブルのサイズを上限値に等しくした。このように構成したことにより、可変長符号ハッシュテーブルのアドレス生成範囲を小さくして、可変長符号ハッシュテーブルのメモリ量を小さくできる。
【００２４】
また、制御ビット付可変長符号部と２次キー部とからなるテーブル情報を格納した可変長符号ハッシュテーブルと、制御ビット付可変長符号部からコード長を算出する可変長符号長算出手段とを備えた。このように構成したことにより、可変長符号ハッシュテーブル中のコード長データを不要とし、可変長符号ハッシュテーブルの１エントリーあたりの情報量を減らして、可変長符号ハッシュテーブルのメモリ量を小さくできる。
【００２５】
【本発明の実施の形態】
以下、本発明の実施の形態について、図１〜図１１を参照しながら詳細に説明する。
【００２６】
（第１の実施の形態）
本発明の第１の実施の形態は、可変長符号の情報を格納したＶＬＣハッシュテーブルに、キーデータに第２のハッシュ演算を施して求めた２次キー部を格納しておき、キーデータに第１のハッシュ演算を施して求めたテーブルアドレスで、ＶＬＣハッシュテーブルをアクセスして２次キー部を読み出し、キーデータに第２のハッシュ演算を施して求めたハッシュ値と比較して確認する可変長符号化装置である。
【００２７】
図１は、本発明の第１の実施の形態における可変長符号化装置の機能ブロック図である。図１において、ＲＵＮ範囲チェック手段１００は、原データにおいてゼロが連続する数（ＲＵＮ）の範囲をチェックする手段である。ＬＥＶＥＬ範囲チェック手段１０１は、原データのゼロでない係数値（ＬＥＶＥＬ）の範囲をチェックする手段である。ハッシュ演算手段１０２は、原データのキーデータ（ＲＵＮ，ＬＥＶＥＬ，ＬＡＳＴ）に第１のハッシュ演算を施す手段である。ＶＬＣハッシュテーブル１０３は、可変長符号（ＶＬＣ）の情報（２次キー部（ＫＥＹ２）、ＶＬＣ、コード長（ＬＥＮ））を格納したテーブルである。テーブル分離手段１０４は、ＶＬＣハッシュテーブルから得た情報を、３つの個別のデータに分離する手段である。２次ハッシュ演算手段１０５は、キーデータ（ＲＵＮ，ＬＥＶＥＬ，ＬＡＳＴ）に第２のハッシュ演算を施す手段である。キー比較手段１０６は、読み出した２次キー部（ＫＥＹ２）と演算で求めた２次キーとの比較を行う手段である。可変長符号化装置は、ＲＵＮ範囲チェック手段１００と、ＬＥＶＥＬ範囲チェック手段１０１と、ハッシュ演算手段１０２と、ＶＬＣハッシュテーブル１０３と、テーブル分離手段１０４と、２次ハッシュ演算手段１０５と、キー比較手段１０６とから構成されている。
【００２８】
図２は、本発明の第１の実施の形態における可変長符号化装置で用いるハッシュ演算とＶＬＣハッシュテーブルの説明図である。図３は、可変長符号化装置で用いる２次ハッシュ演算とＶＬＣハッシュテーブルの説明図である。図４は、可変長符号化装置の動作手順を示すフロー図である。
【００２９】
上記のように構成された本発明の第１の実施の形態における可変長符号化装置の動作を説明する。ここでは、ＭＰＥＧ−４のＩＮＴＲＡ可変長符号化を例にして説明するが、Ｈ．２６１、Ｈ．２６３、ＭＰＥＧ−２、ＪＰＥＧなどの画像符号化方式にも、本実施の形態で説明する可変長符号化方法を適用することができる。可変長符号化する対象の原データについて、ゼロの連続する数（ＲＵＮ）と、ゼロでない係数値（ＬＥＶＥＬ）と、最後のデータを識別するための識別子（ＬＡＳＴ）の組合せを、図示していない前段の装置から入力して、その組合せに基づいてＶＬＣハッシュテーブルを引き、可変長符号（ＶＬＣ）を求める。ＲＵＮは０〜６３の値をとり、ＬＥＶＥＬは１〜２０４７の値をとり、ＬＡＳＴは０、１の値を取る。しかし、図１５に示すように、ＲＵＮとＬＥＶＥＬとＬＡＳＴの全ての組合せに対して、可変長符号が定義されているわけではない。高い頻度で出現する１０２個の組合せだけについて、可変長符号が定義されている。残りの組合せについては、可変長符号が定義されていない。それ以外のデータの場合は、図示していない手段において、３　ｍｏｄｅ　ｅｓｃａｐｅ　ｃｏｄｉｎｇにより、エスケープ符号付可変長符号か、エスケープ符号付固定長符号を生成する。
【００３０】
図１を参照しながら、ＲＵＮ，ＬＥＶＥＬ，ＬＡＳＴの組合せから、可変長コード（ＶＬＣ）とその長さ（ＬＥＮ）と可変長コード生成結果（ＯＫ／ＮＧ）を求める動作を説明する。（ＲＵＮ，ＬＥＶＥＬ，ＬＡＳＴ）の組合せを、キーデータと呼ぶことにする。ＲＵＮ範囲チェック手段１００で、ＲＵＮが定義されているデータ範囲（０〜２０）に入っているか否かをチェックする。範囲内の場合はＯＫを出力し、範囲外の場合はＮＧを出力する。ＬＥＶＥＬ範囲チェック手段１０１で、ＬＥＶＥＬが定義されているデータ範囲（１〜２７）に入っているか否かをチェックする。範囲内の場合はＯＫを出力し、範囲外の場合はＮＧを出力する。ハッシュ演算手段１０２で、キーデータ（ＲＵＮ，ＬＥＶＥＬ，ＬＡＳＴ）に第１のハッシュ演算を施し、算出したハッシュ値を、ＶＬＣハッシュテーブル１０３のアドレスＡとする。ＶＬＣハッシュテーブル１０３は、後述するハッシュテーブルの条件を満足するハッシュ演算式に基づいて生成される。生成した時と同じハッシュ演算式で第１のハッシュ演算を行う。２次ハッシュ演算手段１０５で、キーデータ（ＲＵＮ，ＬＥＶＥＬ，ＬＡＳＴ）に第２のハッシュ演算を施し、２次キーを算出する。アドレスＡによってＶＬＣハッシュテーブル１０３を参照し、テーブル情報（ＫＥＹ２，ＶＬＣ，ＬＥＮ）を得る。テーブル情報（ＫＥＹ２，ＶＬＣ，ＬＥＮ）を、テーブル分離手段１０４で、３つの個別の情報ＫＥＹ２，ＶＬＣ，ＬＥＮに分離する。
【００３１】
キー比較手段１０６で、テーブル分離手段１０４で得られたＫＥＹ２と、２次ハッシュ演算手段１０５で得られた２次キーを比較し、不一致の場合はＮＧを出力する。ＲＵＮ範囲チェック手段１００と、ＬＥＶＥＬ範囲チェック手段１０１と、キー比較手段１０６から出力されたＮＧ信号は、論理和（ＯＲ）され、可変長コード生成結果（ＯＫ／ＮＧ）の出力信号となる。すなわち、いずれか１つでもＮＧが出力されると、可変長コード生成結果はＮＧとなる。可変長コード（ＶＬＣ）と、その長さ（ＬＥＮ）と、可変長コード生成結果（ＯＫ／ＮＧ）の出力は、入力の制御信号（ＣＴＬ）に一定のＤＥＬＡＹを加えた信号に同期してラッチされて、出力される。ここでは、非同期回路を用いる例を説明したが、同期回路で実現しても良い。
【００３２】
次に、ハッシュ演算手段１０２のハッシュ式について詳細に説明する。ハッシュ演算は、キーの集合から番地の集合への多対１の写像演算である。キーデータ（ＲＵＮ，ＬＥＶＥＬ，ＬＡＳＴ）をＫとし、ＶＬＣハッシュテーブルの大きさをＮとすると、アドレスＡを求めるハッシュ演算の式は、
Ａ＝Ｈａｓｈ（Ｋ）　ｍｏｄ　Ｎ　・・・　（１）
となる。Ｈａｓｈ（）は、一般のハッシュ関数である。
【００３３】
ハッシュ演算において、異なるキーのハッシュ値が同一になる（衝突する）シノニムの発生を抑えるために、一般的には、テーブルの大きさＮを素数とする。しかし、本実施の形態では、演算量を減らすために、テーブルの大きさＮを２のべき乗にする。すなわち、
Ａ＝Ｈａｓｈ（Ｋ）　ａｎｄ　（Ｎ−１）　・・・　（２）
のように、Ｎの剰余を求める演算を、論理積によるマスク演算で代用し、演算量を低減している。Ｎが２のべき乗の場合は、式（１）と式（２）は等価である。ａｎｄは、ビットごとの論理積である。
【００３４】
しかし、テーブルの大きさＮが素数でないので、ハッシュ効果が薄れて、シノニムの増大を招く。そこで、本実施の形態では、キーデータを構成するサブキー（ＲＵＮ，ＬＥＶＥＬ，ＬＡＳＴのそれぞれ）に対して、個別に演算するハッシュ関数を利用する。すなわち、
Ａ＝Ｈａｓｈ（Ｋ１，Ｋ２，Ｋ３）　ａｎｄ　（Ｎ−１）　・・・　（３）
というように、３変数のハッシュ演算を行うことにより、ハッシュ効果の薄れを防いでいる。３変数のハッシュ関数としては、周知のハッシュ関数のうち、演算が簡単なものを適宜選択して利用すればよい。
【００３５】
次に、図２を参照しながら、ＶＬＣハッシュテーブル１０３の構造について詳細に説明する。ハッシュ関数は、多対１の写像であるので、複数のキーのハッシュ値が同一となるシノニム現象が必ず発生する。例えば、ＲＵＮ＝０〜２０、ＬＥＶＥＬ＝１〜２７、ＬＡＳＴ＝０，１の範囲をとるキーの集合２０２を、テーブルサイズＮ＝２５６のハッシュテーブルの集合２０３に写像する場合を考えると、１１３４種類から２５６種類への写像となり、シノニムが多発する。しかし、そのうち可変長符号として定義されているキーの集合２０１の位数（元の数）は僅か１０２である。１０２種類から２５６種類への写像において、シノニムを発生させないことは明らかに可能である。本実施の形態においては、可変長符号に定義されているキーの集合２０１に対して、シノニムの発生しないハッシュ関数を用いる。このハッシュ関数は必ず存在し、具体的な条件に応じて生成することは容易である。可変長符号に定義されていないキーに対しては、シノニムを許している。すなわち、キーＡに対しハッシュ演算を施した結果のハッシュ値Ｐ１と、キーＢに対しハッシュ演算を施した結果のハッシュ値Ｐ２は、必ず異なった値を持つ。しかし、キーＣに対しハッシュ演算を施した結果のハッシュ値Ｐ３は、他のハッシュ値と一致してもよい。
【００３６】
このようなハッシュ関数を用いることにより、シノニム発生時の対策を不要としている。すなわち、ハッシュ演算した結果のハッシュ値が目的のキーのハッシュ値と一致するかどうかを判断するだけで、可変長符号を得ることができる。一般的には、ハッシュテーブルを引いて得たエントリー中のキーと、ハッシュテーブルを引くために用いたキーが一致しているかで判断を行う。しかし、ＶＬＣハッシュテーブル中にキーデータを格納するには、最低でも１１ｂｉｔ（ＲＵＮ＝５ｂｉｔ、ＬＥＶＥＬ＝５ｂｉｔ、ＬＡＳＴ＝１ｂｉｔ）必要となり、ＶＬＣハッシュテーブルが大きくなってしまう。そこで本実施の形態では、ＶＬＣハッシュテーブル中にキーデータそのものを格納するのではなく、２次キーを格納するようにして、ＶＬＣハッシュテーブルを小さくしている。
【００３７】
次に、図３を参照しながら、２次ハッシュ演算手段１０５の第２のハッシュ演算について詳細に説明する。キーの集合３０２に対しハッシュ演算を行った結果、シノニムが発生して同一のハッシュ値となった各々のキーに対し、シノニムを発生させない第２のハッシュ演算を施す。ＶＬＣハッシュテーブルには、キーデータ自体の代わりに、可変長符号として定義されているキーデータの集合３０１に、第２のハッシュ演算を施した結果のハッシュ値を格納する。すなわち、キーＢに対しハッシュ演算した結果のハッシュ値Ｐ２と、キーＣに対しハッシュ演算した結果のハッシュ値Ｐ３が一致して、シノニムが発生している場合、キーＢに対し第２のハッシュ演算を施した結果のハッシュ値ＸＢと、キーＣに対して第２のハッシュ演算を施した結果のハッシュ値ＸＣは一致することはない。したがって、ＶＬＣハッシュテーブルに格納された２次キー部ＸＢと、第２のハッシュ演算結果とを比較することにより、目的のキーかどうか判断できる。本実施の形態では、キーの集合３０２に対する第１のハッシュ演算によるシノニムの発生を、１テーブルあたり８個以内に制限しているので、２次キーは３ｂｉｔで表現できる。第２のハッシュ演算によるシノニムの発生はないので、８個以内の２次キーはすべてユニークとなる。
【００３８】
図４を参照しながら、ソフトウエアで可変長符号化処理を行う場合に、キーデータ（ＲＵＮ，ＬＥＶＥＬ，ＬＡＳＴ）から可変長コード（ＶＬＣ）と、その長さ（ＬＥＮ）と、可変長コード生成結果（ＯＫ／ＮＧ）を求める手順を説明する。ステップＳ１００で、ＲＵＮの範囲のチェックを行う。ＲＵＮが定義されているデータ範囲（０〜２０）に入っていれば、ＯＫを出力して、ＬＥＶＥＬの範囲のチェックに進む。範囲外の場合はＮＧを出力して終了する。ステップＳ１０１で、ＬＥＶＥＬの範囲のチェックを行う。ＬＥＶＥＬが定義されているデータ範囲（１〜２７）に入っていればＯＫを出力して、第１のハッシュ演算に進む。範囲外の場合はＮＧを出力して終了する。ステップＳ１０２で、キーデータ（ＲＵＮ，ＬＥＶＥＬ，ＬＡＳＴ）に第１のハッシュ演算を施して、算出したハッシュ値をＶＬＣハッシュテーブル１０３のアドレスＡとする。ステップＳ１０５で、キーデータ（ＲＵＮ，ＬＥＶＥＬ，ＬＡＳＴ）に第２のハッシュ演算を施して、２次キーＫを算出する。ステップＳ１０３で、アドレスＡでＶＬＣハッシュテーブルを参照して、テーブル情報（ＫＥＹ２，ＶＬＣ，ＬＥＮ）を取得する。ステップＳ１０４で、テーブル情報を、ＫＥＹ２，ＶＬＣ，ＬＥＮに分離する。ステップＳ１０６で、テーブル情報中のＫＥＹ２と算出した２次キーＫを比較する。一致すればＯＫを出力し、可変長コード（ＶＬＣ）とその長さ（ＬＥＮ）を出力する。不一致ならばＮＧを出力して終了する。この例は、ソフトウエアのみで実現する方法を示したものであるが、ソフトウエア処理に部分的にハードウエア処理を組み合わせて実行することも可能である。その場合、周知の方法で適宜組み合わせることにより実現できることは、当業者には明らかであろう。
【００３９】
このようにして、従来の可変長符号化装置に比べて少ない演算量のハッシュ演算で、ＶＬＣテーブルのアドレスを直接算出することができる。また、第２のハッシュ演算手段を設けることにより、ＶＬＣハッシュテーブルへのキーそのものの格納を不要とし、ＶＬＣハッシュテーブルのメモリ量を小さくできる。従来、ＶＬＣハッシュテーブルでは、キー部（１１ｂｉｔ）＋ＶＬＣコード（１２ｂｉｔ）＋コード長（４ｂｉｔ）の合計４ｂｙｔｅ×２５６エントリー＝１０２４ｂｙｔｅ必要だったものを、ＶＬＣハッシュテーブル中に必要なキー部（１１ｂｉｔ）を２次キー部（３ｂｉｔ）に置き換えることができ、２次キー部（３ｂｉｔ）＋ＶＬＣコード（１２ｂｉｔ）＋コード長（４ｂｉｔ）の合計３ｂｙｔｅ×２５６エントリー＝７６８ｂｙｔｅに縮小することができる。
【００４０】
上記のように、本発明の第１の実施の形態では、可変長符号化装置を、可変長符号の情報を格納したＶＬＣハッシュテーブルに、キーデータに第２のハッシュ演算を施して求めた２次キー部を格納しておき、キーデータに第１のハッシュ演算を施して求めたテーブルアドレスで、ＶＬＣハッシュテーブルをアクセスして２次キー部を読み出し、キーデータに第２のハッシュ演算を施して求めたハッシュ値と比較して確認する構成としたので、ＶＬＣハッシュテーブルにキーデータそのものを格納しなくてよくなり、ＶＬＣハッシュテーブルのメモリ量を小さくできる。
【００４１】
（第２の実施の形態）
本発明の第２の実施の形態は、ＲＵＮ範囲チェック手段と、ＬＥＶＥＬ範囲チェック手段と、第１のハッシュ演算手段と、第２のハッシュ演算手段とを、２組設け、ＬＡＳＴ値に応じていずれか１組を使用して、キーデータに対して異なるＲＵＮ値の範囲のチェックと異なるＬＥＶＥＬ値の範囲のチェックと異なる第１のハッシュ演算処理と異なる第２のハッシュ演算処理とを行うようにし、キーデータに第１のハッシュ演算を施して求めたテーブルアドレスで、ＶＬＣハッシュテーブルをアクセスして２次キー部を読み出し、キーデータに第２のハッシュ演算を施して求めたハッシュ値と比較して確認する可変長符号化装置である。
【００４２】
図５は、本発明の第２の実施の形態における可変長符号化装置のブロック図である。図５において、ＲＵＮ範囲チェック手段４００は、原データにおいてゼロが連続する数（ＲＵＮ）の範囲を、それぞれ異なる基準でチェックする２つのチェック手段である。ＬＥＶＥＬ範囲チェック手段４０１は、原データのゼロでない係数値（ＬＥＶＥＬ）の範囲を、それぞれ異なる基準でチェックする２つのチェック手段である。ハッシュ演算手段４０２は、キーデータ（ＲＵＮ，ＬＥＶＥＬ，ＬＡＳＴ）に、それぞれ異なる第１のハッシュ演算を施す２つの演算手段である。ＶＬＣハッシュテーブル４０３は、可変長符号（ＶＬＣ）の情報を格納したテーブルである。２次ハッシュ演算手段４０５は、キーデータ（ＲＵＮ，ＬＥＶＥＬ，ＬＡＳＴ）に、それぞれ異なる第２のハッシュ演算を施す２つの演算手段である。その他の構成要素に関しては、図１と同じ符号を付与し、個々の説明は省略する。図６は、可変長符号化装置の可変長符号化手順を示すフロー図である。
【００４３】
上記のように構成された本発明の第２の実施の形態における可変長符号化装置の動作を説明する。キーデータを、ＬＡＳＴ＝０のグループと、ＬＡＳＴ＝１のグループに分けて、それぞれ異なる範囲チェックとハッシュ演算を行う。すなわち、２つのＲＵＮ範囲チェック手段４００で、それぞれ異なる基準でＲＵＮの範囲をチェックする。２つのＬＥＶＥＬ範囲チェック手段４０１で、それぞれ異なる基準でＬＥＶＥＬの範囲をチェックする。２つのハッシュ演算手段４０２で、キーデータ（ＲＵＮ，ＬＥＶＥＬ，ＬＡＳＴ）に異なる第１のハッシュ演算を施す。２つの２次ハッシュ演算手段４０５で、キーデータ（ＲＵＮ，ＬＥＶＥＬ，ＬＡＳＴ）に異なる第２のハッシュ演算を施す。ＶＬＣハッシュテーブル４０３は、ＬＡＳＴ＝０とＬＡＳＴ＝１にグループ分けしたキーデータに基づいて生成されている。
【００４４】
図５を参照しながら、キーデータ（ＲＵＮ，ＬＥＶＥＬ，ＬＡＳＴ）から、可変長コード（ＶＬＣ）とその長さ（ＬＥＮ）と可変長コード生成結果（ＯＫ／ＮＧ）を求める動作を説明する。ＬＡＳＴが０か１に応じて、２組備えたＲＵＮ範囲チェック手段４００とＬＥＶＥＬ範囲チェック手段４０１のいずれか１組に、ＲＵＮとＬＥＶＥＬを入力する。１組目のＲＵＮ範囲チェック手段４００（ＬＡＳＴ＝０用）は、ＲＵＮが定義されているデータ範囲（０〜１４）をチェックする。２組目のＲＵＮ範囲チェック手段４００（ＬＡＳＴ＝１用）は、ＲＵＮが定義されているデータ範囲（０〜２０）をチェックする。範囲外の場合は、ＮＧを出力する。１組目のＬＥＶＥＬ範囲チェック手段４０１（ＬＡＳＴ＝０用）は、ＬＥＶＥＬが定義されているデータ範囲（１〜２７）をチェックする。２組目のＬＥＶＥＬ範囲チェック手段４０１（ＬＡＳＴ＝１用）は、ＬＥＶＥＬが定義されているデータ範囲（１〜８）をチェックする。範囲外の場合は、ＮＧを出力する。
【００４５】
１組目のハッシュ演算手段４０２（ＬＡＳＴ＝０用）は、ＲＵＮとＬＥＶＥＬに、式（４−０）のハッシュ演算を行い、ＶＬＣハッシュテーブル４０３のアドレスＡ１を算出する。他方の２組目（ＬＡＳＴ＝１用）は、ＲＵＮとＬＥＶＥＬに、式（４−１）のハッシュ演算を行い、ＶＬＣハッシュテーブル４０３のアドレスＡ２を算出する。１組目の２次ハッシュ演算手段４０５（ＬＡＳＴ＝０用）は、ＲＵＮとＬＥＶＥＬに、式（５−０）の第２のハッシュ演算を行い、２次キーを算出する。他方の２組目（ＬＡＳＴ＝１用）は、ＲＵＮとＬＥＶＥＬに、式（５−１）の第２のハッシュ演算を行い、２次キーを算出する。
【００４６】
ＶＬＣハッシュテーブル４０３は、ハッシュテーブルの条件を満足するハッシュ関数により生成されており、生成した時と同じハッシュ関数でキーデータにハッシュ演算を行って、アクセスする。アドレスＡ１またはＡ２によって、ＶＬＣハッシュテーブル４０３を引き、テーブル情報を得て、テーブル情報を、テーブル分離手段１０４で、ＫＥＹ２，ＶＬＣ，ＬＥＮに分離する。キー比較手段１０６で、テーブル分離手段１０４で得られたＫＥＹ２と、２次ハッシュ演算手段４０５で得られた２次キーを比較し、不一致の場合はＮＧを出力する。
【００４７】
ＲＵＮ範囲チェック手段４００と、ＬＥＶＥＬ範囲チェック手段４０１と、キー比較手段１０６のそれぞれから出力されたＮＧ信号は、論理和（ＯＲ）され、可変長コード生成結果（ＯＫ／ＮＧ）として出力される。可変長コード（ＶＬＣ）と、その長さ（ＬＥＮ）と、可変長コード生成結果（ＯＫ／ＮＧ）の出力は、入力の制御信号（ＣＴＬ）に同期して（但し、一定のＤＥＬＡＹを含む）ラッチされて、出力される。これらの回路を非同期回路で構成する例を説明したが、同期回路で実現しても良い。
【００４８】
ハッシュ演算手段４０２とＶＬＣハッシュテーブル４０３のテーブル構成について詳細に説明する。ＬＡＳＴ＝０の場合の可変長符号として定義されているキーの種類は、６７種類であるので、
Ａ１＝（ＲＵＮ＋１１２＋ＬＥＶＥＬ＊１０２）ａｎｄ（１２８−１）　・・・　（４−０）
というハッシュ演算式によりアドレスを算出して、大きさＮ＝１２８のハッシュテーブルに詰め込むことが可能である。また、ＬＡＳＴ＝１の場合の可変長符号として定義されているキーの種類は、３５種類であるので、
Ａ２＝（ＲＵＮ＋ＬＥＶＥＬ＊３１−２５）ａｎｄ（６４−１）　・・・　（４−１）
というハッシュ演算式によりアドレスを算出して、大きさＮ＝６４のハッシュテーブルに詰め込むことが可能である。すなわち、両方を合わせて、ＶＬＣハッシュテーブルの大きさを、Ｎ＝１９２とすることができる。なお、ここで示したハッシュ演算式は一例であり、この条件を満たすものであれば、どんなハッシュ演算式でも良い。
【００４９】
次に、２次ハッシュ演算手段４０５のハッシュ演算式について詳細に説明する。ＬＡＳＴ＝０の場合は、
（ＲＵＮ＞＞１）ａｎｄ（８−１）　・・・　（５−０）
［ただし、＞＞１は、１ビット右シフトを示す］という第２のハッシュ演算式により、最大８個のシノニムの中から該当のキーデータを特定することが可能である。また、ＬＡＳＴ＝１の場合は、
（ＬＥＶＥＬ）ａｎｄ（８−１）　・・・　（５−１）
という第２のハッシュ演算式により、最大８個のシノニムの中から該当のキーデータを特定することが可能である。なお、ここで示した第２のハッシュ演算式は一例であり、この条件を満たすものであれば、どんなハッシュ演算式でも良い。
【００５０】
図６を参照しながら、ソフトウエアで可変長符号化処理を行う場合に、キーデータ（ＲＵＮ，ＬＥＶＥＬ，ＬＡＳＴ）から、可変長コード（ＶＬＣ）とその長さ（ＬＥＮ）と可変長コード生成結果（ＯＫ／ＮＧ）を求める手順を説明する。キーデータを、ＬＡＳＴ＝０のグループと、ＬＡＳＴ＝１のグループに分けて、別々に第１と第２のハッシュ演算を行う。ステップＳ９９９で、ＬＡＳＴ＝０またはＬＡＳＴ＝１に応じて分岐を行う。以下、ＬＡＳＴ＝０の手順について説明する。ＬＡＳＴ＝１の場合も同様な手順である。ステップ２００−１で、ＲＵＮの範囲のチェックを行う。ＲＵＮが定義されているデータ範囲（０〜１４）内ならば、ＬＥＶＥＬの範囲のチェックに進む。範囲外ならばＮＧとなり処理を終了する。ステップＳ２０１−１で、ＬＥＶＥＬの範囲のチェックを行う。ＬＥＶＥＬが定義されているデータ範囲（１〜２７）内ならば、第１のハッシュ演算に進む、範囲外ならばＮＧとなり処理を終了する。ステップＳ２０２−１で、キーデータ（ＲＵＮ，ＬＥＶＥＬ）に、式（４−０）の第１のハッシュ演算を行い、ＶＬＣハッシュテーブルのアドレスＡ１を算出する。ステップＳ２０５−１で、キーデータ（ＲＵＮ，ＬＥＶＥＬ）に、式（５−０）の第２のハッシュ演算を行い、２次キーＫを算出する。ステップＳ２０３−１で、アドレスＡ１でＶＬＣハッシュテーブルを引いて、テーブル情報を得る。ステップＳ１０４で、テーブル情報をＫＥＹ２，ＶＬＣ，ＬＥＮに分離する。ステップＳ１０６で、テーブル中のＫＥＹ２と、算出した２次キーＫを比較する。一致すればＯＫを出力し、可変長コード（ＶＬＣ）とその長さ（ＬＥＮ）を出力する。不一致ならばＮＧを出力して終了する。この例は、ソフトウエアのみで実現する方法を示したものであるが、ソフトウエア処理に部分的にハードウエア処理を組み合わせて実行することも可能である。その場合、周知の方法で適宜組み合わせることにより実現できることは、当業者には明らかであろう。
【００５１】
このようにして、従来の可変長符号化装置に比べて少ない演算量のハッシュ演算でＶＬＣハッシュテーブルのアドレスを直接算出することができる。また、２組のハッシュ演算手段および２次ハッシュ演算手段により、キーデータを複数のグループに分けて別々にハッシュ演算を行い、ＶＬＣハッシュテーブルのアドレス生成範囲を小さくして、ＶＬＣハッシュテーブルのメモリ量を小さくできる。従来、ＶＬＣハッシュテーブルに、キー部（１１ｂｉｔ）＋ＶＬＣコード（１２ｂｉｔ）＋コード長（４ｂｉｔ）の合計４ｂｙｔｅ×２５６エントリー＝１０２４ｂｙｔｅ必要だったものを、１９２エリトリー（ＬＡＳＴ＝０に１２８エントリー、ＬＡＳＴ＝１に６４エントリー）にすることができ、２次キー部（３ｂｉｔ）＋ＶＬＣコード（１２ｂｉｔ）＋コード長（４ｂｉｔ）の合計３ｂｙｔｅ×１９２エントリー＝５７６ｂｙｔｅに縮小することができる。
【００５２】
上記のように、本発明の第２の実施の形態では、可変長符号化装置に、ＲＵＮ範囲チェック手段と、ＬＥＶＥＬ範囲チェック手段と、第１のハッシュ演算手段と、第２のハッシュ演算手段とを、２組設け、ＬＡＳＴ値に応じていずれか１組を使用して、キーデータに対して異なるＲＵＮ値の範囲のチェックと異なるＬＥＶＥＬ値の範囲のチェックと異なる第１のハッシュ演算処理と異なる第２のハッシュ演算処理とを行うようにし、キーデータに第１のハッシュ演算を施して求めたテーブルアドレスで、ＶＬＣハッシュテーブルをアクセスして２次キー部を読み出し、キーデータに第２のハッシュ演算を施して求めたハッシュ値と比較して確認する構成としたので、ＶＬＣハッシュテーブルのアドレス生成範囲を小さくして、ＶＬＣハッシュテーブルのメモリ量を小さくできる。
【００５３】
（第３の実施の形態）
本発明の第３の実施の形態は、キーデータに第１のハッシュ演算を施した結果が所定の上限値以下であることをチェックし、上限値を超えていなければ、第１のハッシュ演算の結果をテーブルアドレスとして、上限値と同じサイズの可変長符号ハッシュテーブルを参照する可変長符号化装置である。
【００５４】
図７は、本発明の第３の実施の形態における可変長符号化装置のブロック図である。図７において、上限チェック付ハッシュ演算手段５０２は、原データのキーデータ（ＲＵＮ，ＬＥＶＥＬ，ＬＡＳＴ）に第１のハッシュ演算を施す手段であり、ハッシュ演算結果の上限をチェックする機能を追加したものである。ＶＬＣハッシュテーブル５０３は、可変長符号（ＶＬＣ）の情報を格納した、上限値と同じサイズのテーブルである。その他の構成要素に関しては、図５と同じ符号を付与し、個々の説明は省略する。図８は、可変長符号化装置の動作手順を示すフロー図である。
【００５５】
上記のように構成された本発明の第３の実施の形態における可変長符号化装置の動作を説明する。図７を参照しながら、ハッシュ演算でハッシュテーブルのアドレスを求める動作を説明する。その他、キーデータ（ＲＵＮ，ＬＥＶＥＬ，ＬＡＳＴ）から可変長コード（ＶＬＣ）と、その長さ（ＬＥＮ）と、可変長コード生成結果（ＯＫ／ＮＧ）を求める動作は、第２の実施の形態と同様なので省略する。上限チェック付ハッシュ演算手段５０２の１組目（ＬＡＳＴ＝０用）は、ハッシュ演算結果のアドレスＡ１が１１３以上であれば、ＮＧを出力する。他方の２組目（ＬＡＳＴ＝１用）は、ハッシュ演算結果のアドレスＡ２が４４以上であれば、ＮＧを出力する。
【００５６】
上限チェック付ハッシュ演算手段５０２とＶＬＣハッシュテーブル５０３のテーブル構成について詳細に説明する。図２で説明したように、ハッシュテーブルには、可変長符号として定義されている有効なキーと無効なキーが存在する。ＬＡＳＴ＝０の場合は、可変長符号として定義されている有効なキーの種類は６７種類であり、ハッシュテーブルの大きさは１２８であるので、６１種類は無効なキーである。また、ＬＡＳＴ＝１の場合は、可変長符号として定義されているキーの種類は３５種類であり、ハッシュテーブルの大きさは６４であるので、２９種類は無効なキーである。そこで、テーブルの上部から有効なキーが詰まり、テーブルの下部には無効なキーがまとまるようなハッシュ演算式を用いることにより、ハッシュテーブルの下部を削除することができる。
【００５７】
ＬＡＳＴ＝０の場合は、
Ａ１＝（ＲＵＮ＋１１２＋ＬＥＶＥＬ＊１０２）ａｎｄ（１２８−１）　・・・　（６−０）
［但し、Ａ１＞１１３ならＮＧ］というハッシュ演算により、テーブルの上部１１３以内に有効なキーを詰め込むことができる。また、ＬＡＳＴ＝１の場合は、
Ａ２＝（ＲＵＮ＋ＬＥＶＥＬ＊３１−２５）ａｎｄ（６４−１）　・・・　（６−１）
［但し、Ａ２＞４４ならＮＧ］というハッシュ演算により、テーブルの上部４４以内に有効なキーを詰め込むことができる。すなわち、両方を合わせて、ハッシュテーブルの大きさを、Ｎ＝１１３＋４４＝１５７とすることができる。なお、ここで示したハッシュ演算式は一例であり、この条件を満たすものであればどんなハッシュ演算式でも良い。
【００５８】
図８を参照しながら、ソフトウエアで可変長符号化処理を行う場合に、ハッシュ演算でＶＬＣハッシュテーブルのアドレスを求める動作を説明する。その他、キーデータ（ＲＵＮ，ＬＥＶＥＬ，ＬＡＳＴ）から可変長コード（ＶＬＣ）と、その長さ（ＬＥＮ）と、可変長コード生成結果（ＯＫ／ＮＧ）を求める手順は、第２の実施の形態と同様なので、省略する。本実施の形態では、ＶＬＣハッシュテーブルの上部から有効なテーブル情報が埋まり、テーブルの下部に空き領域がまとまるハッシュ演算式を用いることにより、ＶＬＣハッシュテーブルの不要な領域を削減している。ステップＳ２０２−１で、ＲＵＮ，ＬＥＶＥＬに第１のハッシュ演算を行い、アドレスＡ１を算出する。ステップＳ３１０−１で、アドレスＡ１が上限を超えているかチェックする。上限を超えている場合は、ＮＧとなる。
【００５９】
このようにして、従来の可変長符号化装置に比べて少ない演算量のハッシュ演算でＶＬＣテーブルのアドレスを直接算出することができる。また、ハッシュ演算手段で、有効なハッシュ演算結果がＶＬＣハッシュテーブルの上部のアドレスとなり、下部に空き領域がまとまるようなハッシュ演算を用い、ハッシュ演算結果の上限チェックを行うことにより、ＶＬＣハッシュテーブルのアドレス生成範囲を小さくして、ＶＬＣハッシュテーブルのメモリ量を小さくできる。従来、ＶＬＣハッシュテーブルに、キー部（１１ｂｉｔ）＋ＶＬＣコード（１２ｂｉｔ）＋コード長（４ｂｉｔ）の合計４ｂｙｔｅ×２５６エントリー＝１０２４ｂｙｔｅ必要だったものを、１５７エリトリー（ＬＡＳＴ＝０の１１３エントリーと、ＬＡＳＴ＝１の４４エントリー）にすることができ、２次キー部（３ｂｉｔ）＋ＶＬＣコード（１２ｂｉｔ）＋コード長（４ｂｉｔ）の合計３ｂｙｔｅ×１５７エントリー＝４７１ｂｙｔｅに縮小することができる。
【００６０】
上記のように、本発明の第３の実施の形態では、可変長符号化装置を、キーデータに第１のハッシュ演算を施した結果が所定の上限値以下であることをチェックし、上限値を超えていなければ、第１のハッシュ演算の結果をテーブルアドレスとして、上限値と同じサイズの可変長符号ハッシュテーブルを参照する構成としたので、ＶＬＣハッシュテーブルのアドレス生成範囲を小さくして、ＶＬＣテーブルのメモリ量を小さくできる。
【００６１】
（第４の実施の形態）
本発明の第４の実施の形態は、ＶＬＣハッシュテーブル中の可変長符号部に制御ビットを付加し、可変長符号部からコード長を算出する可変長符号化装置である。
【００６２】
図９は、本発明の第４の実施の形態における可変長符号化装置のブロック図である。図９において、ＶＬＣハッシュテーブル６０３は、可変長符号（ＶＬＣ）に制御ビットを付加することにより、可変長符号長（ＬＥＮ）を不要としたハッシュテーブルである。コード長算出手段６０７は、可変長符号から符号長を算出する手段である。その他の構成要素に関しては、図７と同じ符号を付与し、個々の説明は省略する。図１０は、可変長符号装置で用いる可変長符号の説明図である。図１１は、可変長符号化装置の動作手順を示すフロー図である。
【００６３】
上記のように構成された本発明の第４の実施の形態における可変長符号化装置の動作を説明する。図９と図１０を参照しながら、コード長算出手段６０７とＶＬＣハッシュテーブル６０３のテーブル構成について詳細に説明する。可変長符号（ＶＬＣ）は最大１２ｂｉｔであり、可変長符号から一意に符号長を求めるために、可変長符号を１３ｂｉｔの中に右詰で格納し、可変長符号のＭＳＢ（最上位桁）に制御ビット‘１’を付加し、その上位に’０’を格納する。（例１）では、ビット位置１０に制御ビット’１’を付加し、ビット位置１３〜１１は’０’を格納する。同様に（例２）では、ビット位置７に制御ビット’１’を付加し、ビット位置１３〜８は’０’を格納する。可変長符号が１２ｂｉｔの場合も同様に、（例３）のように、ビット位置１３に制御ビット’１’を付加する。
【００６４】
コード長を求めるには、１３ｂｉｔ目からビット’１’が初めて現れるまでのカウントをＭとすると、符号長＝１２−Ｍで求めることができる。したがって、ＶＬＣハッシュテーブルには、コード長の４ｂｉｔは必要なく、ＶＬＣコードに１３ｂｉｔあれば十分である。
【００６５】
図１１を参照しながら、ソフトウエアで可変長符号化処理を行う場合に、ハッシュ演算でＶＬＣハッシュテーブルのアドレスを求める動作を説明する。ステップＳ９９９からＳ１０６までは、第３の実施の形態と同じである。図１１に示すステップＳ４１０のＣｏｄｅＬｅｎ（ＶＬＣ）は、可変長符号（ＶＬＣ）に制御ビットを付加することにより、可変長符号長（ＬＥＮ）を不要とした可変長符号から符号長を算出するものである。その他、キーデータ（ＲＵＮ，ＬＥＶＥＬ，ＬＡＳＴ）から可変長コード（ＶＬＣ）と、可変長コード生成結果（ＯＫ／ＮＧ）を求める手順は、第３の実施の形態と同様なので省略する。
【００６６】
このようにして、従来の可変長符号化装置に比べて少ない演算量のハッシュ演算でＶＬＣテーブルのアドレスを直接算出することができる。また、制御ビットを付加した可変長符号部からコード長を算出する可変長符号長算出手段を設けることにより、ＶＬＣハッシュテーブル中のコード長を不要とし、ハッシュテーブルの１エントリーあたりの情報量を減らして、ＶＬＣテーブルのメモリ量を小さくできる。従来、ＶＬＣハッシュテーブルに、キー部（１１ｂｉｔ）＋ＶＬＣコード（１２ｂｉｔ）＋コード長（４ｂｉｔ）の合計４ｂｙｔｅ×２５６エントリー＝１０２４ｂｙｔｅ必要だったものを、ＶＬＣコードに１ｂｉｔ付加するだけでコード長データの格納を不要にすることができ、２次キー部（３ｂｉｔ）＋ＶＬＣコード（１３ｂｉｔ）の合計２ｂｙｔｅ×１５７エントリー＝３１４ｂｙｔｅに縮小することができる。
【００６７】
上記のように、本発明の第４の実施の形態では、可変長符号化装置を、ＶＬＣハッシュテーブル中の可変長符号部に制御ビットを付加し、可変長符号部からコード長を算出する構成としたので、ＶＬＣハッシュテーブル中のコード長データを不要とし、ハッシュテーブルの１エントリーあたりの情報量を減らして、ＶＬＣテーブルのメモリ量を小さくできる。
【００６８】
本発明は、プログラムによって実現することも可能である。そのソフトウェアを磁気ディスク等の記録媒体に記録して移送することにより、独立した他のコンピュータ・システムで、このソフトウェアを収めた記録媒体から読み出して、実施することができる。記録媒体としては、磁気ディスクの他に、光ディスク、光磁気ディクス等を用いても同様に行うことができる。また、記録媒体は、これらに限られず、ＩＣカード、ＲＯＭカセット等、プログラムを記録できるものであれば、同様に実施することができる。
【００６９】
【発明の効果】
以上の説明から明らかなように、本発明では、可変長符号化装置に、キーデータ（ＲＵＮ，ＬＥＶＥＬ，ＬＡＳＴ）に第２のハッシュ演算を施して２次キーを算出する２次ハッシュ演算手段と、可変長符号部と２次キー部とを含むテーブル情報を格納した可変長符号ハッシュテーブルと、テーブル情報を個別の情報に分離するテーブル分離手段と、２次キーとテーブル情報中の２次キー部とを比較するキー比較手段とを具備する構成としたので、ＶＬＣハッシュテーブルにキーデータ（ＲＵＮ，ＬＥＶＥＬ，ＬＡＳＴ）そのものを格納する必要がなくなり、ＶＬＣハッシュテーブルのメモリ量を小さくできるという効果が得られる。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態における可変長符号化装置のブロック図、
【図２】本発明の第１の実施の形態における可変長符号化装置で用いるハッシュ演算とハッシュテーブルの説明図、
【図３】本発明の第１の実施の形態における可変長符号化装置で用いる２次ハッシュ演算とハッシュテーブルの説明図、
【図４】本発明の第１の実施の形態における可変長符号化装置の可変長符号化手順を示すフロー図、
【図５】本発明の第２の実施の形態における可変長符号装置のブロック図、
【図６】本発明の第２の実施の形態における可変長符号化装置の可変長符号化手順を示すフロー図、
【図７】本発明の第３の実施の形態における可変長符号装置のブロック図、
【図８】本発明の第３の実施の形態における可変長符号化装置の可変長符号化手順を示すフロー図、
【図９】本発明の第４の実施の形態における可変長符号装置のブロック図、
【図１０】本発明の第４の実施の形態における可変長符号装置で用いる可変長符号の説明図、
【図１１】本発明の第４の実施の形態における可変長符号化装置の可変長符号化手順を示すフロー図、
【図１２】従来の可変長符号テーブルのアクセス方法の説明図、
【図１３】従来のクラス分け可変長符号テーブルのアクセス方法の説明図、
【図１４】従来のハッシュを用いた可変長符号テーブルのアクセス方法の説明図、
【図１５】従来のＭＰＥＧ−４のＩＮＴＡＲ　ＶＬＣの説明図である。
【符号の説明】
１００　ＲＵＮ範囲チェック手段
１０１　ＬＥＶＥＬ範囲チェック手段
１０２　ハッシュ演算手段
１０３　ＶＬＣハッシュテーブル
１０４　テーブル分離手段
１０５　２次ハッシュ演算手段
１０６　キー比較手段
２０１　可変長符号として定義されているキー集合
２０２　キーの集合
２０３　ＶＬＣハッシュテーブル集合
３０１　可変長符号として定義されているキー集合
３０２　キーの集合
３０３　ＶＬＣハッシュテーブル集合
４００　ＲＵＮ範囲チェック手段
４０１　ＬＥＶＥＬ範囲チェック手段
４０２　ハッシュ演算手段
４０３　ＶＬＣハッシュテーブル
４０５　２次ハッシュ演算手段
５０２　上限チェック付ハッシュ演算手段
５０３　ＶＬＣハッシュテーブル
６０３　ＶＬＣハッシュテーブル
６０７　コード長算出手段
【図１】
2004096692.tif 000003
【図２】
2004096692.tif 000004
【図３】
2004096692.tif 000005
【図４】
2004096692.tif 000006
【図５】
2004096692.tif 000007
【図６】
2004096692.tif 000008
【図７】
2004096692.tif 000009
【図８】
2004096692.tif 000010
【図９】
2004096692.tif 000011
【図１０】
2004096692.tif 000012
【図１１】
2004096692.tif 000013
【図１２】
2004096692.tif 000014
【図１３】
2004096692.tif 000015
【図１４】
2004096692.tif 000016
【図１５】
2004096692.tif 000017