(57)【要約】符号化されたシンボルへの参照先をシンボルごとに対応させるシンボル対応手段１０１が設けられ、参照先特定手段１０２は、シンボルに割り当てられた最大符号長分のビット列を入力ビット列から切り出し、切り出された各ビット列ごとにシンボルへの参照先を特定し、シンボル対応手段１０１を参照することにより、その特定された参照先に対応するシンボルを出力する。
2002101935.tif 000002
【特許請求の範囲】
【請求項１】
符号化されたシンボルへの参照先を前記シンボルごとに対応させるシンボル対応手段と、
前記シンボルに割り当てられた最大符号長分の切り出しビット列ごとに、前記シンボルへの参照先を特定する参照先特定手段とを備えることを特徴とする復号化装置。
【請求項２】
所定の長さのビット列に基づいて、前記ビット列に含まれる符号に対応する復号結果への参照先情報を取得する参照情報取得手段と、
前記参照先情報取得手段により取得された参照先情報に基づいて、前記ビット列に含まれる符号に対応する復号結果を取得する復号結果取得手段とを備えることを特徴とする復号化装置。
【請求項３】
符号化されたシンボルを復号する復号化装置において、
入力ビット系列から前記シンボルの最大符号長分の長さのビット列を読み込む入力バッファと、
前記シンボルへの参照先情報が、前記シンボルの最大符号長分の長さのビット列ごとに登録された第１の配列表と、
前記シンボルおよびその符号長が、前記シンボルごとに登録された第２の配列表と、
前記入力バッファに読み込まれたビット列に基づいて前記第１の配列表を参照することにより、前記ビット列に含まれる符号に対応するシンボルへの参照先情報を取得する第１参照手段と、
前記第１参照手段により取得された参照先情報に基づいて前記第２の配列表を参照することにより、前記ビット列に含まれる符号に対応するシンボルおよびその符号長を取得する第２参照手段と、
前記入力バッファに読み込まれたビット列から前記シンボルの符号長分だけ除いた残りのビットを、前記入力ビット系列に差し戻す差し戻し手段とを備えることを特徴とする復号化装置。
【請求項４】
符号化されたシンボルを復号する復号化装置において、
入力ビット系列から前記シンボルの最大符号長分の長さのビット列を読み込む入力バッファと、
前記シンボルへの参照先情報が、前記シンボルの最大符号長分の長さのビット列ごとに登録された第１の配列表と、
前記シンボルおよびその符号長の前記最大符号長からの差分が、前記シンボルごとに登録された第２の配列表と、
前記入力バッファに読み込まれたビット列に基づいて前記第１の配列表を参照することにより、前記ビット列に含まれる符号に対応するシンボルへの参照先情報を取得する第１参照手段と、
前記第１参照手段により取得された参照先情報に基づいて前記第２の配列表を参照することにより、前記ビット列に含まれる符号に対応するシンボルおよび前記差分を取得する第２参照手段と、
前記入力バッファに読み込まれたビット列を前記差分だけ前記入力ビット系列に差し戻す差し戻し手段とを備えることを特徴とする復号化装置。
【請求項５】
前記第１の配列表は、前記最大符号長分の長さのビット列の上位ビット列および下位ビット列に対応して複数に分割されていることを特徴とする請求項３または４記載の復号化装置。
【請求項６】
入力ビット系列から最大符号長分の長さのビット列を読み込むステップと、
前記読み込まれたビット列に基づいて、前記ビット列に含まれる符号に対応するシンボルへの参照先情報を取得するステップと、
前記取得された参照先情報から、前記ビット列に含まれる符号に対応するシンボルおよびその符号長を取得するステップと、
前記読み込みビット列に含まれる符号の復号結果として、前記取得されたシンボルを出力するステップと、
前記読み込みビット列から前記シンボルの符号長分だけ除いた残りのビットを、前記入力ビット系列に戻すステップとを備えることを特徴とする復号化方法。
【請求項７】
シンボルへの参照先情報が、復号化される符号の候補ごとに登録された第１の配列表と、
前記シンボルおよびその符号の符号長が、前記シンボルごとに登録された第２の配列表とを備えることを特徴とするルックアップテーブル。
【請求項８】
シンボルおよびその符号長の最大符号長に対する差分が、前記シンボルの最大符号長分の長さのビット列で特定されるエントリーごとに登録されていることを特徴とするルックアップテーブル。
【請求項９】
入力ビット系列から最大符号長分の長さのビット列を読み込むステップと、
前記読み込まれたビット列に基づいて、前記ビット列に含まれる符号に対応するシンボルへの参照先情報を取得するステップと、
前記取得された参照先情報から、前記ビット列に含まれる符号に対応するシンボルおよびその符号長を取得するステップと、
前記読み込みビット列に含まれる符号の復号結果として、前記取得されたシンボルを出力するステップと、
前記読み込みビット列から前記シンボルの符号長分だけ除いた残りのビットを、前記入力ビット系列に戻すステップとをコンピュータで実行させるための復号化プログラム。
【請求項１０】
入力ビット系列から最大符号長分の長さのビット列を読み込むステップと、
前記読み込まれたビット列に基づいて、前記ビット列に含まれる符号に対応するシンボルへの参照先情報を取得するステップと、
前記取得された参照先情報から、前記ビット列に含まれる符号に対応するシンボルおよびその符号長の前記最大符号長分からの差分を取得するステップと、
前記読み込みビット列に含まれる符号の復号結果として、前記取得されたシンボルを出力するステップと、
前記読み込みビット列を前記差分だけ前記入力ビット系列に戻すステップとをコンピュータで実行させるための復号化プログラム。
【発明の詳細な説明】
技術分野
本発明は、復号化装置、復号化方法、ルックアップテーブルおよび復号化プログラムに関し、特に、可変長符号の復号に適用して好適なものである。
背景技術
従来の可変長符号の復号化では、入力ビット系列から符号ビットを１ビットずつ読み込み、符号表で定義されたビット列に一致した時に、そのビット列に対応するシンボルを復号結果として出力する方法がある。この方法では、各シンボルに対応する符号ビットを保持するだけで復号を行なうことができ、少ない記憶容量で済ませることができるが、入力ビット系列から符号ビットを１ビットずつ読み込むため、復号に時間がかかる。
一方、復号を高速に行なうため、最大符号長分の各ビット列で特定される全てのエントリー（候補）に対し、復号結果となるシンボルおよびその符号長をルックアップテーブルに登録する方法がある。
図８は、この従来のルックアップテーブルの構成例を示す図である。
図８（ａ）において、例えば、シンボルＳ０には、符号ビット‘１’が割り当てられ、シンボルＳ１には、符号ビット‘０１’が割り当てられ、シンボルＳ２には、符号ビット‘００１’が割り当てられ、シンボルＳ３には、符号ビット‘０００’が割り当てられた符号表１１が定義されているものとする。
この場合、符号ビットの最大符号長は３であるので、図８（ｂ）に示すように、３ビット分の各ビット列で特定される２３個のエントリーに対し、配列番号、シンボルおよび符号長をルックアップテーブル１２に登録する。ここで、配列番号は、３ビット分のビット列の１０進表示に対応させることができる。
そして、入力ビット系列から３ビットずつ読み込み、その３ビットを１０進表示に変換することにより、配列番号を求める。配列番号が求まると、その配列番号をキーとして、ルックアップテーブル１２を参照することにより、その配列番号に対応するシンボルを取得する。そして、そのシンボルを復号結果として出力するとともに、その３ビット分のビット列からそのシンボルの符号長分を差し引いた残りのビットを、入力ビット系列に差し戻す。
例えば、入力ビット系列が‘１０１００１０１１０・・・’であるとすると、この入力ビット系列から最初の３ビット‘１０１’を読み込み、この‘１０１’を１０進表示に変換することにより、配列番号‘５’を求める。そして、この配列番号‘５’をキーとして、図８（ｂ）のルックアップテーブル１２を参照することにより、シンボル‘Ｓ０’およびそのシンボル‘Ｓ０’の符号長‘１’を取得し、そのシンボル‘Ｓ０’を復号結果として出力する。
また、シンボル‘Ｓ０’の符号長‘１’を最大符号長‘３’と比較し、最大符号長‘３’とシンボル‘Ｓ０’の符号長‘１’との差分２ビット分‘０１’は、シンボル‘Ｓ０’の復号には使用されなかったとして、この２ビット分‘０１’を入力ビット系列に‘００１０１１０・・・’に差し戻す。
以後、この差し戻し後の入力ビット系列‘０１００１０１１０・・・’から、次の３ビット‘０１０’を読み込み、以上の処理を繰り返す。
このように、上述した従来の方法では、入力ビット系列から最大符号長分のビット列を１回読み込むだけで復号が可能となるため、復号を高速化することができる。
しかしながら、上述した従来の方法では、最大符号長分の各ビット列で特定される全てのエントリーに対して、シンボルおよびその符号長を登録する必要があるため、ルックアップテーブル１２の容量が大きくなるという問題があった。
すなわち、図８の例では、シンボルが４つしかないにもかかわらず、シンボルおよびその符号長を２３個のエントリーだけ登録する必要があることから、同一のシンボルが何度も重複して登録される。
特に、最大符号長が大きい場合には、シンボルが重複して登録される回数も増えるため、ルックアップテーブルの容量が膨大になり、例えば、最大符号長が１６で、１シンボル当たり１００バイト、符号長を記憶するのに１バイト必要とすると、２１６×１０１バイトの容量が必要になる。
そこで、本発明の目的は、少ない記憶容量で復号を高速化することができる復号化装置、復号化方法、ルックアップテーブルおよび復号化プログラムを提供することである。
発明の開示
上述した課題を解決するために、本発明に係る復号化装置によれば、符号化されたシンボルへの参照先を前記シンボルごとに対応させるシンボル対応手段と、前記シンボルに割り当てられた最大符号長分の切り出しビット列ごとに、前記シンボルへの参照先を特定する参照先特定手段とを備えることを特徴とする。
これにより、最大符号長分の各ビット列で特定される全てのエントリーに対応してシンボルを登録することなく、各ビット列を切り出すごとに、符号化されたシンボルを特定することが可能となり、復号時の高速性を維持しつつ、記憶容量を低減させることが可能となる。
また、本発明に係る復号化装置の別形態によれば、所定の長さのビット列に基づいて、前記ビット列に含まれる符号に対応する復号結果への参照先情報を取得する参照先情報取得手段と、前記参照先情報取得手段により取得された参照先情報に基づいて、前記ビット列に含まれる符号に対応する復号結果を取得する復号結果取得手段とを備えることを特徴とする。
これにより、復号結果となる同一のシンボルを重複して登録することなく、所定の長さのビット列で特定されるエントリーとシンボルとを対応づけることが可能となり、復号時の高速性を維持しつつ、記憶容量を低減させることが可能となる。
また、本発明に係る復号化装置の別形態によれば、符号化されたシンボルを復号する復号化装置において、入力ビット系列から前記シンボルの最大符号長分の長さのビット列を読み込む入力バッファと、前記シンボルへの参照先情報が、前記シンボルの最大符号長分の長さのビット列ごとに登録された第１の配列表と、前記シンボルおよびその符号長が、前記シンボルごとに登録された第２の配列表と、前記入力バッファに読み込まれたビット列に基づいて前記第１の配列表を参照することにより、前記ビット列に含まれる符号に対応するシンボルへの参照先情報を取得する第１参照手段と、前記第１参照手段により取得された参照先情報に基づいて前記第２の配列表を参照することにより、前記ビット列に含まれる符号に対応するシンボルおよびその符号長を取得する第２参照手段と、前記入力バッファに読み込まれたビット列から前記シンボルの符号長分だけ除いた残りのビットを、前記入力ビット系列に差し戻す差し戻し手段とを備えることを特徴とする。
これにより、最大符号長分の長さの各ビット列に対し、シンボルへの参照先を第１の配列表に登録するだけで、シンボルおよびその符号長を第２の配列表から取得することが可能となる。
このため、第１の配列表および第２の配列表への２回のアクセスを行なうだけで、可変長符号の復号を行なうことが可能となるとともに、最大符号長分の長さの各ビット列に対応して、同じシンボルおよびその符号長を何度も重複して登録する必要がなくなることから、復号時の高速性を維持しつつ、記憶容量を低減させることが可能となる。
また、本発明に係る復号化装置の別形態によれば、符号化されたシンボルを復号する復号化装置において、入力ビット系列から前記シンボルの最大符号長分の長さのビット列を読み込む入力バッファと、前記シンボルへの参照先情報が、前記シンボルの最大符号長分の長さのビット列ごとに登録された第１の配列表と、前記シンボルおよびその符号長の前記最大符号長からの差分が、前記シンボルごとに登録された第２の配列表と、前記入力バッファに読み込まれたビット列に基づいて前記第１の配列表を参照することにより、前記ビット列に含まれる符号に対応するシンボルへの参照先情報を取得する第１参照手段と、前記第１参照手段により取得された参照先情報に基づいて前記第２の配列表を参照することにより、前記ビット列に含まれる符号に対応するシンボルおよび前記差分を取得する第２参照手段と、前記入力バッファに読み込まれたビット列を前記差分だけ前記入力ビット系列に差し戻す差し戻し手段とを備えることを特徴とする。
これにより、最大符号長分の長さの各ビット列に対し、シンボルへの参照先を第１の配列表に登録するだけで、シンボルおよびその符号長の前記最大符号長からの差分を第２の配列表から取得することが可能となる。
このため、第１の配列表および第２の配列表への２回のアクセスを行なうだけで、可変長符号の復号を行なうことが可能となるとともに、その可変長符号の復号に使用されなかったビット数を第２の配列表から直接取得することが可能となり、アクセス回数を削減しつつ、ビット列を差し戻す際に行なわれていた減算処理を省略して、復号のさらなる高速化を図ることが可能となる。
また、本発明に係る復号化装置の別形態によれば、前記第１の配列表は、前記最大符号長分の長さのビット列の上位ビット列および下位ビット列に対応して複数に分割されていることを特徴とする。
これにより、エントリーを特定するための配列数を削減することができ、記憶容量をさらに低減させることが可能となる。
また、本発明に係る復号化方法によれば、入力ビット系列から最大符号長分の長さのビット列を読み込むステップと、前記読み込まれたビット列に基づいて、前記ビット列に含まれる符号に対応するシンボルへの参照先情報を取得するステップと、前記取得された参照先情報から、前記ビット列に含まれる符号に対応するシンボルおよびその符号長を取得するステップと、前記読み込みビット列に含まれる符号の復号結果として、前記取得されたシンボルを出力するステップと、前記読み込みビット列から前記シンボルの符号長分だけ除いた残りのビットを、前記入力ビット系列に戻すステップとを備えることを特徴とする。
これにより、最大符号長分の長さの読み出しごと、可変長符号を復号する場合においても、最大符号長分の長さの各ビット列に対し、シンボルの参照先のみを登録すればよく、同じシンボルおよびその符号長を何度も重複して登録する必要がなくなることから、復号時の高速性を維持しつつ、記憶容量を低減させることが可能となる。
また、本発明に係るルックアップテーブルによれば、シンボルへの参照先情報が、復号化される符号の候補ごとに登録された第１の配列表と、前記シンボルおよびその符号の符号長が、前記シンボルごとに登録された第２の配列表とを備えることを特徴とする。
これにより、復号化される符号の各候補に対し、第１の配列表を１回参照するだけで、その候補に対応するシンボルにアクセスすることが可能となり、シンボルを各候補ごとに登録する必要がなくなることから、記憶容量の増大を抑制しつつ、復号時の高速化を図ることが可能となる。
また、本発明に係るルックアップテーブルの別形態によれば、シンボルおよびその符号長の最大符号長に対する差分が、前記シンボルの最大符号長分の長さのビット列で特定されるエントリーごとに登録されていることを特徴とする。
これにより、ルックアップテーブルに１回アクセスするだけで、復号されたシンボルを出力することが可能となるとともに、そのシンボルの復号に使用されなかったビット数を取得することが可能となり、そのビット列を差し戻す際に行なわれていた減算処理を省略して、復号のさらなる高速化を図ることが可能となる。
また、本発明に係る復号化プログラムによれば、入力ビット系列から最大符号長分の長さのビット列を読み込むステップと、前記読み込まれたビット列に基づいて、前記ビット列に含まれる符号に対応するシンボルへの参照先情報を取得するステップと、前記取得された参照先情報から、前記ビット列に含まれる符号に対応するシンボルおよびその符号長を取得するステップと、前記読み込みビット列に含まれる符号の復号結果として、前記取得されたシンボルを出力するステップと、前記読み込みビット列から前記シンボルの符号長分だけ除いた残りのビットを、前記入力ビット系列に戻すステップとをコンピュータで実行させることを特徴とする。
これにより、復号化プログラムをインストールすることで、可変長符号の復号を高速化することが可能となるとともに、ルックアップテーブルの記憶容量を低減することが可能となる。
また、本発明に係る復号化プログラムの別態様によれば、入力ビット系列から最大符号長分の長さのビット列を読み込むステップと、前記読み込まれたビット列に基づいて、前記ビット列に含まれる符号に対応するシンボルへの参照先情報を取得するステップと、前記取得された参照先情報から、前記ビット列に含まれる符号に対応するシンボルおよびその符号長の前記最大符号長分からの差分を取得するステップと、前記読み込みビット列に含まれる符号の復号結果として、前記取得されたシンボルを出力するステップと、前記読み込みビット列を前記差分だけ前記入力ビット系列に戻すステップとをコンピュータで実行させることを特徴とする。
これにより、復号化プログラムをインストールすることで、シンボルの復号に使用されなかったビット数を直接取得することが可能となり、ビット列を差し戻す際に行なわれていた減算処理を省略して、復号のさらなる高速化を図ることが可能となる。
発明を実施するための最良の形態
以下、本発明の実施形態に係わる復号化装置および復号化方法について、図面を参照しながら説明する。
図１は、本発明の第１実施形態に係わる復号化装置の概略構成を示すブロック図である。
図１において、復号化装置には、シンボル対応手段１０１および参照先特定手段１０２が設けられている。
ここで、シンボル対応手段１０１は、符号化されたシンボルへの参照先をシンボルごとに対応させる。また、参照先特定手段１０２は、シンボルに割り当てられた最大符号長分のビット列を入力ビット列から切り出し、切り出された各ビット列ごとにシンボルへの参照先を特定する。そして、シンボル対応手段１０１を参照することにより、その特定された参照先に対応するシンボルを出力する。
これにより、最大符号長分の各ビット列で特定される全てのエントリーに対応してシンボルを登録することなく、各ビット列を切り出すごとに、符号化されたシンボルを特定することが可能となり、復号時の高速性を維持しつつ、記憶容量を低減させることが可能となる。
図２は、本発明の第２実施形態に係わる復号化装置の構成を示すブロック図である。
図２において、入力バッファ１は、シンボルＳＹの最大符号長分の長さのビット列を、入力ビット系列から読み込む。参照部２は、入力バッファ１に読み込まれたビット列で特定される配列番号ＬＮをキーとして、第１の配列表３ａを参照することにより、そのビット列に含まれる符号に対応するシンボルＳＹへのインデックス（参照先）ＩＮを取得する。さらに、そのインデックスＩＮをキーとして、第２の配列表３ｂを参照することにより、入力バッファ１に読み込まれたビット列に含まれる符号に対応するシンボルＳＹおよびその符号長ＬＣを取得する。
ルックアップテーブル３は、第１の配列表３ａおよび第２の配列表３ｂを備えている。ここで、第１の配列表３ａは、シンボルＳＹの最大符号長分の長さのビット列で特定される配列番号ＬＮごとに、復号結果となるシンボルＳＹへのインデックスＩＮを登録する。第２の配列表３ｂは、復号結果となるシンボルＳＹおよびその符号長ＬＣを、インデックスＩＮごとに登録する。
差し戻し部４は、入力バッファ１に読み込まれたビット列から、そのシンボルＳＹの符号長ＬＣだけ除いた残りのビットを、入力ビット系列に差し戻す。
図３は、本発明の第２実施形態に係わるルックアップテーブル３の構成例を示す図である。ここで、図８（ａ）に示すように、シンボルＳ０には、符号ビット‘１’が割り当てられ、シンボルＳ１には、符号ビット‘０１’が割り当てられ、シンボルＳ２には、符号ビット‘００１’が割り当てられ、シンボルＳ３には、符号ビット‘０００’が割り当てられているものとする。
この場合、これらの符号ビットの最大符号長は３であるので、第１の配列表３ａには、図３（ａ）に示すように、３ビット分の各ビット列で特定されるエントリーに対し、配列番号ＬＮおよびインデックスＩＮを登録する。ここで、配列番号ＬＮは、３ビット分のビット列の１０進表示に対応させることができる。
一方、第２の配列表３ｂには、図３（ｂ）に示すように、各インデックスＩＮで特定される配列番号に対応して、シンボルＳＹおよび符号長ＬＣを登録する。
そして、入力バッファ１が、入力ビット系列から３ビットずつ読み込むと、参照部２は、その３ビットを１０進表示に変換することにより、配列番号ＬＮを求める。配列番号ＬＮが求まると、参照部２は、その配列番号ＬＮをキーとして、第１の配列表３ａを参照することにより、その配列番号ＬＮに対応するインデックスＩＮを求める。そして、インデックスＩＮが求まると、そのインデックスＩＮをキーとして、第２の配列表３ｂを参照することにより、そのインデックスＩＮに対応するシンボルＳＹおよび符号長ＬＮを求め、そのシンボルＳＹを復号結果として出力するとともに、その符号長ＬＮを差し戻し部４に出力する。
差し戻し部４は、符号長ＬＮを参照部２から受け取ると、最大符号長と参照部２から受け取った符号長ＬＮとの差分を算出する。そして、入力バッファ１に読み込まれた３ビット分のビット列のうち、差分のビット数だけ後方のビット列を入力ビット系列に差し戻す。
このように、シンボルＳＹおよびその符号長ＬＣの代わりに、インデックスＩＮを配列番号ＬＮに対応させて登録することにより、シンボルＳＹおよびその符号長ＬＣを１回ずつ保持するだけで、配列番号ＬＮからシンボルＳＹへのアクセスが可能となり、シンボルＳＹおよびその符号長ＬＣを何度も重複して保持する必要がなくなる。ここで、インデックスＩＮを配列番号ＬＮに対応させて登録すると、インデックスＩＮを何度も重複して保持する必要があるが、インデックスＩＮは、単に番号（数字）に対応させることができるため、数字だけでなく、文字や記号なども含まれるシンボルＳＹに比べて、少ないビット数で表すことができる。このため、シンボルＳＹおよびその符号長ＬＣを配列番号ＬＮに対応させて登録した場合に比べ、記憶容量を低減させることが可能となる。
また、インデックスＩＮを配列番号ＬＮに対応させて登録した場合においても、第１の配列表３ａおよび第２の配列表３ｂへの２回のアクセスを行なうだけで、可変長符号の復号を行なうことができ、復号時の高速性を維持することが可能となる。
さらに、第１の配列表３ａおよび第２の配列表３ｂへのアクセスを行なう場合においても、出現頻度の多いシンボルＳＹおよびその符号長ＬＣをキャッシュ上に保持することにより、アクセス時間を減らすことができ、復号時の高速性を向上させることが可能となる。
図４は、本発明の一実施形態に係わる復号化方法を示す図である。
図４（ａ）において、例えば、入力ビット系列が‘１０１００１０１１０・・・’であるとすると、入力バッファ１は、この入力ビット系列から最初の３ビット‘１０１’を読み込み、参照部２に出力する。参照部２は、ビット列‘１０１’を受け取ると、このビット列‘１０１’を１０進表示に変換することにより配列番号‘５’を求める。そして、この配列番号‘５’をキーとして、配列表３ａを参照することにより、インデックス‘０’を取得する（▲１▼）。
参照部２は、インデックス‘０’を取得すると、このインデックス‘０’をキーとして、配列表３ｂを参照することにより、シンボル‘Ｓ０’およびそのシンボル‘Ｓ０’の符号長’１’を取得する（▲２▼）。そして、そのシンボル‘Ｓ０’を復号結果として出力するとともに（▲３▼）、そのシンボル‘Ｓ０’の符号長‘１’を差し戻し部４に出力する（▲４▼）。
差し戻し部４は、シンボル’Ｓ０’の符号長‘１’を受け取ると、最大符号長‘３’とそのシンボル‘Ｓ０’の符号長‘１’との差分＝２を算出する。そして、入力バッファ１に読み込まれた３ビット分のビット列‘１０１’のうち、後方の２ビット分‘０１’を入力ビット系列に‘００１０１１０・・・’に差し戻す（▲５▼）。
次に、図４（ｂ）に示すように、入力バッファ１は、差し戻し後の入力ビット系列‘０１００１０１１０・・・’から、３ビット‘０１０’を読み込み、参照部２に出力する。参照部２は、ビット列‘０１０’を受け取ると、このビット列‘０１０’を１０進表示に変換することにより配列番号‘２’を求める。そして、この配列番号‘２’をキーとして、配列表３ａを参照することにより、インデックス‘１’を取得する（▲６▼）。
参照部２は、インデックス‘１’を取得すると、このインデックス‘１’をキーとして、配列表３ｂを参照することにより、シンボル‘Ｓ１’およびそのシンボル‘Ｓ１’の符号長‘２’を取得する（▲７▼）。そして、そのシンボル‘Ｓ１’を復号結果として出力するとともに（▲８▼）、そのシンボル‘Ｓ１’の符号長‘２’を差し戻し部４に出力する（▲９▼）。
差し戻し部４は、シンボル‘Ｓ１’の符号長‘２’を受け取ると、最大符号長‘３’とそのシンボル‘Ｓ１’の符号長‘２’との差分＝１を算出する。そして、入力バッファ１に読み込まれた３ビット分のビット列‘０１０’のうち、後方
2002101935.tif 000003
）。
次に、図４（ｃ）に示すように、入力バッファ１は、差し戻し後の入力ビット系列‘００１０１１０・・・’から、３ビット‘００１’を読み込み、参照部２に出力する。参照部２は、ビット列‘００１’を受け取ると、このビット列‘００１’を１０進表示に変換することにより配列番号‘１’を求める。そして、この配列番号‘１’をキーとして、配列表３ａを参照することにより、インデック
2002101935.tif 000004
参照部２は、インデックス‘２’を取得すると、このインデックス‘２’をキーとして、配列表３ｂを参照することにより、シンボル‘Ｓ２’およびそのシン
2002101935.tif 000005
’を差し戻し部４に出力する。
差し戻し部４は、シンボル‘Ｓ２’の符号長‘３’を受け取ると、最大符号長‘３’とそのシンボル‘Ｓ２’の符号長‘３’との差分＝０を算出する。そして、入力バッファ１に読み込まれた３ビット分のビット列‘１０１’のうち、後方の０ビット分を入力ビット系列に‘００１０１１０・・・’に差し戻す。すなわち、最大符号長と差し戻し部４が取得した符号長との差分が０の場合、ビット列の差し戻しは行なわれない。
この結果、図４（ｄ）に示すように、図４（ｃ）の入力ビット系列‘００１０１１０・・・’から、最初の３ビット‘００１’が除かれた入力ビット系列‘０１１０・・・’に対して、次の符号の復号が続行される。
図５は、本発明の一実施形態に係わる復号化方法を示すフローチャートである。
図５において、未復号の入力ビット系列がある場合（ステップＳ１）、その入力ビット系列から最大符号長分の長さのビット列を読み込む（ステップＳ２）。そして、読み込んだビット列から配列番号ＬＮを算出し（ステップＳ３）、その配列番号ＬＮをキーとして、第１の配列表３ａを参照することにより、インデックスＩＮを取得する（ステップＳ４）。
次に、そのインデックスＩＮをキーとして、第２の配列表３ｂを参照することにより、シンボルＳＹおよびその符号長ＬＣを取得し（ステップＳ５）、そのシンボルＳＹを復号結果として出力する（ステップＳ６）。
次に、ステップＳ２で読み込まれたビット列から、そのシンボルＳＹの符号長ＬＣ分だけ除いた残りのビット（またはビット列）を、未復号の入力ビット系列に差し戻す（ステップＳ７）。
なお、第１の配列表３ａは、複数のテーブルに分割してもよく、これにより、インデックスＩＮを特定するために必要な配列数を減らすことができ、記憶容量をさらに低減させることが可能となる。
図６は、本発明の第３実施形態に係わるルックアップテーブルの構成例を示す図である。
図６（ａ）において、シンボルＳ０〜Ｓ１９に対して、最大符号長が９の符号ビットが割り当てられているものとする。
そして、図６（ａ）の符号ビットを、上位３ビットおよび下位６ビットで分割すると、図６（ｂ）の符号表が得られる。
ここで、図６（ａ）の符号ビットを、上位３ビットおよび下位６ビットで分割した場合、この分割された配列に対して、各シンボルへのインデックスを割り当てることにより、各シンボルを特定することができ、記憶容量を減らすことが可能となる。
例えば、９ビットの上位３ビットが‘０１１’の場合、符号をシンボルＳ４に確定させることができる。
また、９ビットの上位３ビットが‘０００’の場合、さらに、６ビットを読み込み、テーブル０００を参照することにより、シンボルを確定させることができる。
また、９ビットの上位３ビットが‘００１’の場合、さらに、６ビットを読み込み、テーブル００１を参照することにより、シンボルを確定させることができる。
ただし、テーブル０００は、図６（ａ）で定義されたシンボルＳ０〜Ｓ１９の中で、上位３ビットが‘０００’のもので、上位３ビットを取り除いたシンボルに対して作成されたテーブル、テーブル００１は、図６（ａ）で定義されたシンボルＳ０〜Ｓ１９の中で、上位３ビットが‘００１’のもので、上位３ビットを取り除いたシンボルに対して作成されたテーブルである。
図７は、本発明の第４実施形態に係わるルックアップテーブル１２´の構成例を示す図である。なお、この第２実施形態のルックアップテーブル１２´では、図８（ｂ）のルックアップテーブル１２に登録されている符号長の代わりに、その符号長の最大符号長に対する差分を登録するようにしたものである。
すなわち、シンボルＳ０〜Ｓ３に対応する符号ビットが、図８（ａ）の符号表１１のように定義されているものとする。この場合、符号ビットの最大符号長は３であるので、図６に示すように、３ビット分の各ビット列で特定される２３個のエントリーに対し、配列番号、シンボルおよびその符号長の最大符号長に対する差分をルックアップテーブル１２´に登録する。例えば、ビット列‘０００’で特定される配列番号０に対しては、そこに登録されるシンボルＳ３の符号長が３であるので、最大符号長３とシンボルＳ３の符号長３との差分＝０を登録する。また、例えば、ビット列‘０１０’で特定される配列番号２に対しては、そこに登録されるシンボルＳ１の符号長が２であるので、最大符号長３とシンボルＳ１の符号長２との差分＝１を登録する。
これにより、そのシンボルの復号に必要がなかったビットを元に戻す際に、何ビット分戻したらよいかを、ルックアップテーブル１２´を参照するだけで認識することができ、減算処理を省略することが可能となることから、復号のさらなる高速化を図ることが可能となる。
なお、図７の実施形態では、図８（ｂ）のルックアップテーブル１２の符号長を、その符号長の最大符号長に対する差分で置き換える方法について説明したが、この置き換えを図３（ｂ）の第２の配列表３ｂに行なうようにしてもよい。
産業上の利用可能性
以上説明したように、本発明によれば、同一のシンボルを重複して登録することなく、最大符号長分の長さのビット列で特定されるエントリーとシンボルとを対応づけることが可能となり、復号時の高速性を維持しつつ、記憶容量を低減させることが可能となる。
【図面の簡単な説明】
図１は、本発明の第１実施形態に係わる復号化装置の概略構成を示すブロック図である。
図２は、本発明の第２実施形態に係わる復号化装置の構成を示すブロック図である。
図３は、本発明の第２実施形態に係わるルックアップテーブルの構成例を示す図である。
図４は、本発明の第２実施形態に係わる復号化方法を示す図である。
図５は、本発明の第２実施形態に係わる復号化方法を示すフローチャートである。
図６は、本発明の第３実施形態に係わるルックアップテーブルの構成例を示す図である
図７は、本発明の第４実施形態に係わるルックアップテーブルの構成例を示す図である。
図８は、従来のルックアップテーブルの構成例を示す図である。
【図１】
2002101935.tif 000006
【図２】
2002101935.tif 000007
【図３】
2002101935.tif 000008
【図４】
2002101935.tif 000009
【図５】
2002101935.tif 000010
【図６】
2002101935.tif 000011
【図７】
2002101935.tif 000012
【図８】
2002101935.tif 000013
【国際調査報告】
2002101935.tif 000014
2002101935.tif 000015