(57)【特許請求の範囲】
【請求項１】
可変長符号化データと復号化後のデータとが対応付けられた復号表を用いて復号化する可変長符号化データの復号化方法であって、
前記可変長符号化データの最大符号長をｎビット（ｎは正の整数）としたとき前記ｎビットの符号の１番目からｎ番目の各ビット位置ごとに各可変長符号化データのビット反転を調べ、ビット反転回数の少ないビット位置に分割位置を設定して、前記設定された分割位置で分割されたあとのビット数の符号群で構成される復号表を、分割された数以上生成し、前記生成された復号表を順次参照することによって前記可変長符号化データの復号化を行うことを特徴とする可変長符号化データの復号化方法。
【請求項２】
可変長符号化データと復号化後のデータとが対応付けられた復号表を用いて復号化する可変長符号化データの復号化方法であって、
前記可変長符号化データの最大符号長をｎビット（ｎは正の整数）としたとき前記ｎビットの符号の１番目からｎ番目のそれぞれのビット位置ごとに、それぞれの前記可変長符号化データのビット反転回数を調べ、前記ビット反転回数の少ないビット位置に分割位置を設定して、
前記設定された分割位置で、前記復号表を分割した場合のビット数の符号群で構成される復号表を、前記設定された分割位置の数以上生成し、
前記生成された復号表を順次参照することによって前記可変長符号化データの復号化を行う
ことを特徴とする可変長符号化データの復号化方法。
【請求項３】
前記分割位置はビット反転回数の少ない複数の箇所に設定され、前記複数の箇所を分割候補位置とし、それぞれの前記分割候補位置を少なくとも１箇所用いて複数通りの分割を行い、前記複数通りの分割ごとに複数の復号表の生成を試み、当該複数通りの分割ごとに生成された複数の復号表の合計の復号表サイズを求めるととともに、実際の復号処理における復号表参照回数を求め、両者の値に基づいて前記複数の分割候補位置のうち、少なくとも１箇所を実際に分割する分割位置として選定することを特徴とする請求項１または２に記載の可変長符号化データの復号化方法。
【請求項４】
前記分割位置として設定された位置で分割されることによって、第１番目から第ｍ番目（ｍは正の整数）までの復号表が生成された場合、前記第１番目から第ｍ番目までの復号表を用いて復号化する際は、当該第１番目の復号表を参照して復号化を試み、復号化が可能であれば、当該第１番目の復号表によって復号化を行い、当該第１番目の復号表での復号化ができなければ当該第1番目の復号表により指示される次の復号表を参照して復号化を試みるというように、第１番目から必要に応じて第ｍ番目までのいずれかの復号表を選択して行うことを特徴とする請求項１から３のいずれかに記載の可変長符号化データの復号化方法。
【請求項５】
可変長符号化データと復号化後のデータとが対応付けられた復号表を用いて復号化する可変長符号化データの復号化装置であって、
前記可変長符号化データの最大符号長をｎビット（ｎは正の整数）としたとき前記ｎビットの符号の１番目からｎ番目の各ビット位置ごとに各可変長符号化データのビット反転を調べ、ビット反転回数の少ないビット位置を求める符号ビット反転計測手段と、
前記符号ビット反転計測手段によって求められたビット反転回数の少ないビット位置に分割位置を設定して、前記設定された分割位置で分割されたあとのビット数の符号群で構成される復号表を、分割された数以上生成する復号表生成手段と、
前記生成された復号表を、順次参照することによって前記可変長符号化データの復号化を行う復号処理手段と、
を有したことを特徴とする可変長符号化データの復号化装置。
【請求項６】
可変長符号化データと復号化後のデータとが対応付けられた復号表を用いて復号化する可変長符号化データの復号化装置であって、
前記可変長符号化データの最大符号長をｎビット（ｎは正の整数）としたとき、前記ｎビットの符号の１番目からｎ番目のそれぞれのビット位置ごとに、それぞれの前記可変長符号化データのビット反転回数を調べ、前記ビット反転回数の少ないビット位置に分割位置を設定する分割位置設定手段と、
前記設定された分割位置で、前記復号表を分割した場合のビット数の符号群で構成される復号表を、前記設定された分割位置の数以上生成する復号表生成手段と、
前記生成された復号表を順次参照することによって前記可変長符号化データの復号化を行う復号処理手段と、
を有する可変長符号化データの復号化装置。
【請求項７】
前記分割位置はビット反転回数の少ない複数の箇所に設定され、前記複数の箇所を分割候補位置とし、それぞれの前記分割候補位置を少なくとも１箇所用いて複数通りの分割を行い、前記複数通りの分割ごとに複数の復号表の生成を試み、当該複数通りの分割ごとに生成された複数の復号表の合計の復号表サイズを求めるととともに、実際の復号処理における復号表参照回数を求め、両者の値に基づいて前記複数の分割候補位置のうち、少なくとも１箇所を実際に分割する分割位置として選定することを特徴とする請求項５または６に記載の可変長符号化データの復号化装置。
【請求項８】
前記分割位置として設定された位置で分割されることによって、第１番目から第ｍ番目（ｍは正の整数）までの復号表が生成された場合、前記第１番目から第ｍ番目までの復号表を用いて復号化する際は、当該第１番目の復号表を参照して復号化を試み、復号化が可能であれば、当該第１番目の復号表によって復号化を行い、当該第１番目の復号表での復号化ができなければ当該第1番目の復号表により指示される次の復号表を参照して復号化を試みるというように、第１番目から必要に応じて第ｍ番目まで順次、復号表を選択して行うことを特徴とする請求項５から７のいずれかに記載の可変長符号化データの復号化装置。
【請求項９】
可変長符号化データと復号化後のデータとが対応付けられた復号表を用いて復号化する可変長符号化データの復号化処理プログラムを記録した記録媒体であって、その可変長符号化データの復号化処理プログラムは、
前記可変長符号化データの最大符号長をｎビット（ｎは正の整数）としたとき前記ｎビットの符号の１番目からｎ番目の各ビット位置ごとに各可変長符号化データのビット反転を調べ、ビット反転回数の少ないビット位置に分割位置を設定する手順と、
前記設定された分割位置で分割されたあとのビット数の符号群で構成される復号表を、分割された数以上生成する手順と、
前記生成された復号表を順次参照することによって前記可変長符号化データの復号化を行う手順と、
を含むことを特徴とする可変長符号化データの復号化処理プログラムを記録した記録媒体。
【請求項１０】
可変長符号化データと復号化後のデータとが対応付けられた復号表を用いて復号化する可変長符号化データの復号化処理プログラムを記録した記録媒体であって、その可変長符号化データの復号化処理プログラムは、
前記可変長符号化データの最大符号長をｎビット（ｎは正の整数）としたとき前記ｎビットの符号の１番目からｎ番目のそれぞれのビット位置ごとに、それぞれの前記可変長符号化データのビット反転回数を調べ、前記ビット反転回数の少ないビット位置に分割位置を設定する手順と、
前記設定された分割位置で、前記復号表を分割した場合のビット数の符号群で構成される復号表を、前記設定された分割位置の数以上生成する手順と、
前記生成された復号表を順次参照することによって前記可変長符号化データの復号化を行う手順と、
を含むことを特徴とする可変長符号化データの復号化処理プログラムを記録した記録媒体。
【請求項１１】
前記分割位置はビット反転回数の少ない複数の箇所に設定され、前記複数の箇所を分割候補位置とし、それぞれの前記分割候補位置を少なくとも１箇所用いて複数通りの分割を行い、前記複数通りの分割ごとに複数の復号表の生成を試み、当該複数通りの分割ごとに生成された複数の復号表の合計の復号表サイズを求めるととともに、
実際の復号処理における復号表参照回数を求め、両者の値に基づいて前記複数の分割候補位置のうち、少なくとも１箇所を実際に分割する分割位置として選定することを特徴とする請求項９または１０に記載の可変長符号化データの復号化処理プログラムを記録した記録媒体。
【請求項１２】
前記分割位置として設定された位置で分割されることによって、第１番目から第ｍ番目（ｍは正の整数）までの復号表が生成された場合、前記第１番目から第ｍ番目までの復号表を用いて復号化する際は、当該第１番目の復号表を参照して復号化を試み、復号化が可能であれば、当該第１番目の復号表によって復号化を行い、当該第１番目の復号表での復号化ができなければ当該第１番目の復号表により指示される次の復号表を参照して復号化を試みるというように、第１番目から必要に応じて第ｍ番目まで順次、復号表を選択して行うことを特徴とする請求項９から１１のいずれかに記載の可変長符号化データの復号化処理プログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、マルチメディアデータなどに多用される可変長符号化データを高速に、かつ、少ないメモリ量で復号化を可能とする可変長符号化データの復号化方法及び可変長符号化データの復号化装置並びに可変長符号化データの復号化処理プログラムを記録した記録媒体に関する。
【０００２】
【従来の技術】
可変長符号化は、マルチメディアデータ、たとえば、静止画像を取り扱うＪＰＥＧや、動画像、音声、音楽などを取り扱うＭＰＥＧなどにおいて多用されている。この可変長符号の有効性について図１３を参照しながら以下に説明する。
【０００３】
ここでは、データとしてＡからＰの１６種類のみを取り扱うものとし、かつ、それぞれのデータの出現確率（情報量を表す）が、図１３に示したような値であるとする。幾つかを例に挙げれば、データＡは２５％、データＢは２１％、データＣは１２％、データＦ〜Ｈは３％、データＭ〜Ｐは１％といった値となっているとする。
【０００４】
ここでのデータは１６種類であるので、固定長符号化においては、Ａ〜Ｐのそれぞれのデータは図示のように４ビットで表現することができる。この場合は、当然のことながら平均符号長は４ビットである。
【０００５】
一方、それぞれのデータの出現確率を考慮し、最大符号長８ビットの可変長符号化を行うとする。このとき、 Ａ〜Ｐのそれぞれのデータに図１３で示すような可変長符号を割り当てたとする。たとえば、データＡに対しては、「００」（符号長２）、データＢに対しては「０１」（符号長２）、データＣに対しては「１００」（符号長３）、・・・、データＰに対しては「１１１１１１１１」（符号長８）といった可変長符号を割り当てる。この場合、平均符号長は、3.25ビットとなる。
【０００６】
これは、先に説明した固定符号長の場合に比較して、データの誤差なしにほぼ１９％だけデータ圧縮されたことになる。この圧縮率はデータの偏りに依存し、偏りが大きければ圧縮率はより大きくなる。また、データの偏りがいくら小さくても、平均の符号長は固定長符号化データのデータサイズ（上述の例では４ビット）を超えることはない。つまり、データがより冗長になる事はない。
【０００７】
図１４は可変長符号の構成方法を木構造を用いてに説明するもので、図中、小さな丸を「節」、Ａ，Ｂ，Ｃ，・・・などの記号（データ名）が記入された大きな丸を「葉」と呼び、「葉」と「節」、または、「節」と「節」を結ぶ線を「枝」と呼ぶ。そして、それぞれの「節」は、上位の「節」に接続された１本の「枝」と下位の「節」または「葉」に接続された２本の「枝」を持つ。この下位の「節」または「葉」に接続された２本の「枝」は、その一方の「枝」が、ある１ビット分の「１」に対応し、他方が「０」に対応している。
【０００８】
可変長符号はこのような木構造において、図中、「ROOT」（「根」）を開始点とし、「ROOT」から下位方向へ「枝」、「節」をたどり、「葉」に至る経路によって表現される。なお、「根」から特定の「葉」に至る経路は唯一しかない。これによって、特定の「葉」の符号は一意に決まる。たとえば、データＡは、「ROOT」から「０」の枝ｂ１と「０」の枝ｂ２を辿ることによって到達できるので、符号「００」が割り当てられ、また、データＢは、「ROOT」から「０」の枝ｂ１と「１」の枝ｂ３を辿ることによって到達できるので、符号「０１」が割り当てられ、また、もう一つ例を挙げれば、データＥは、「ROOT」から「１」の枝ｂ４、「１」の枝ｂ８、「０」の枝ｂ９を辿ることによって到達できるので、符号「１１０」が割り当てられることになる。
【０００９】
なお、図１４の木構造において、破線で示すラインＬ１，Ｌ２，・・・Ｌ８が記述されているが、このそれぞれのラインＬ１，Ｌ２，・・・Ｌ８上に存在する「枝」に、「葉」（データ）が存在する場合、そのライン番号が符号長を示している。たとえば、ラインＬ２上に存在する「枝」 ｂ２，ｂ３には、データＡとデータＢの「葉」がそれぞれ接続されており、この場合、データＡとデータＢはともに符号長が「２」である。また、ラインＬ３上に存在する「枝」 ｂ６，ｂ７，ｂ９には、データＣとデータＤとデータＥの「葉」がそれぞれ接続されており、この場合、データＣ、データＤ、データＥはともに符号長が「３」である。
【００１０】
図１５は上述のようにして構成された可変長符号の特性を表現するためのデータ構造を示すものである。このデータ構造は３つの要素からなる。その１つめ要素は可変長符号の長さ（符号長）であり、２つめ要素はその符号長を持つ符号として割り当てられるデータの数（割当て数）であり、３つめの要素は割当て数に対して割り当てるデータである。
【００１１】
たとえば幾つか例を挙げれば、図１５の１番目に記述されている符号長「１」、割当数「０」、データ「なし」というのは、１ビットの符号長に対して割り当てられるデータ数は０であり、それに割り当てられるデータは無いということである。また、符号長「２」、割当数「２」、データ「ＡＢ」というのは、２ビットの符号長に対して割り当てられるデータ数は「２」であって、その２つのデータはデータＡとデータＢである。また、符号長「８」、割当数「４」、データ「ＭＮＯＰ」というのは、８ビットの符号長に対して割り当てられるデータ数は「４」であって、その４つのデータはデータＭ、データＮ、データＯ、データＰであることを示している。
【００１２】
図１６は図１５で示した可変長符号の特性を示すデータ構造を基にして、Ａ〜Ｐの各データに対して、どのような符号長の可変長符号を割り当てるかを示すアルゴリズムをフローチャートとして示すものである。
【００１３】
図１６において、符号（CODE）を０とするとともに符号長（LEN）を１とし（ステップｓ１，ｓ２）、そのあと、符号長は最大長（この例では最大の符号長は「８」）以下かどうかを見て（ステップｓ３）、符号長が最大長に達していれば符号生成処理は終了し（ステップｓ４）、最大長に達していなければ、当該符号長に割当てられた割当て数（Ｑ）を読み込む（ステップｓ５）。そして、割当て数（Ｑ）が正であるか否かを見て（ステップｓ６）、正でなければCODEを１ビット左シフトし（ステップｓ７）、符号長（LEN）を（LEN＋１）して（ステップｓ８）、ステップｓ３に戻る。
【００１４】
一方、ステップｓ６において、割当て数（Ｑ）が正であれば、データに符号長（LEN）の符号（CODE）を割り当て（ステップ９）、符号（CODE)を（CODE＋１）する（ステップｓ１０）。そして、割当て数（Ｑ）を（Ｑ−１）してステップｓ６に戻る。
【００１５】
以上のようなアルゴリズムによって、データＡ〜Ｐに対してどのような符号長でどのような可変長符号を割り当てるかを決めることができ、データＡ〜Ｐに対するそれぞれの符号長と可変長符号を得ることができる。
【００１６】
図１７は実際にデータを符号化しようとする場合の具体例を示すもので、ここでは、「ＣＡＢＩＮ」というデータを可変長符号化する例が示されている。まず、「Ｃ」に対しては、図１３により、符号長は「３」でその符号は「１００」ということが記述されているので、図１７（ａ）のように「１００」が書き込まれる。次に、「Ａ」に対しては、符号長は「２」でその符号は「００」ということが記述されているので、図１７（ｂ）のように「００」が書き込まれ、また、「Ｂ」に対しては、符号長は「２」でその符号は「０１」ということが記述されているので、図１７（ｃ）のように「０１」が書き込まれる。同様にして、「Ｉ」に対しては、図１７（ｄ）のように「１１１０１１」が書き込まれ、「Ｎ」に対しては、図１７（ｅ）のように「１１１１１１０１」が書き込まれる。
【００１７】
これによって、「ＣＡＢＩＮ」というデータに対する可変長符号化データ「１０００００１１１１０１１１１１１１１０１」が得られる。
【００１８】
このようにして符号化された可変長符号化データを復号化する場合の従来の復号化方法について説明する。まず、従来の復号化方法その１として、図１４で示した木構造を辿る方法について説明する。この方法は図１８のフローチャートに示すように、まず、現在位置を「ROOT」に設定し（ステップｓ２１）、処理対象となる可変長符号化データから１ビットを読み込む（ステップｓ２２）。読み込んだ１ビットのデータが「０」かどうかを見て（ステップｓ２３）、読み込んだ１ビットのデータが「０」であれば、「０」の枝を進み（ステップｓ２４）、読み込んだ１ビットのデータが「１」であれば、「１」の枝を進む（ステップｓ２５）。
【００１９】
そして、その進んだ先が「葉」であるか否かを見て（ステップｓ２６）、「葉」でなければステップｓ２２に戻る。一方、進んだ先が「葉」であれば、その「葉」のデータを結果として得る（ステップｓ２７）。以下に具体例について図１９を参照しながら説明する。ここでは、処理対象の可変長符号化データが上述した「１０００００１１１１０１１１１１１１１０１」であるとする。
【００２０】
図１９において、まず、処理対象となる可変長符号化データから１ビットを読み込むと、読み込まれた１ビットのデータは「１」であるので、「ROOT」に続く「１」の枝ｂ４を通って節ｎ１に到達する。ここではまだ「葉」には到達していないので、次の１ビットを読み込む。読み込まれた１ビットのデータは「０」であるので、今度は枝ｂ５を通って節ｎ２に到達するが、ここでもまだ「葉」には到達していないので、次の１ビットを読み込む。読み込まれた１ビットのデータは「０」であるので、今度は枝ｂ６を辿る。この枝ｂ６の先は「葉」に到達し、その葉であるデータ「Ｃ」に到達する。なお、「葉」に到達した場合には、その「葉」のデータを復号化データとするので、ここではまず、復号化データとして「Ｃ」を得る。
【００２１】
続いて、次のデータを１ビット読み込むと、読み込まれた１ビットのデータは「０」であるので、「ROOT」から続く「０」の枝ｂ１を通って節ｎ３に到達する。ここではまだ「葉」には到達していないので、次の１ビットを読み込む。読み込まれた１ビットのデータは「０」であるので、今度は枝ｂ２を通って「葉」に到達し、その葉であるデータ「Ａ」に到達する。
【００２２】
同様にして、次のデータを１ビット読み込むと、読み込まれた１ビットのデータは「０」であるので、「ROOT」から続く「０」の枝ｂ１を通って節ｎ３に到達する。ここではまだ「葉」には到達していないので、次の１ビットを読み込む。読み込まれた１ビットのデータは「１」であるので、今度は枝ｂ３を通って「葉」に到達し、その葉であるデータ「Ｂ」に到達する。
【００２３】
そして、そのあとに続く「１１１０１１・・・」について同じように処理して行くと、データ「Ｉ」を得る。さらに、そのあとに続く、「１１１１１１０１」について同じように処理して行くと、データ「Ｎ」を得る。
【００２４】
以上のようにして、可変長符号化データを復号化することができるが、この木構造を利用した復号化処理は、１ビットづつのデータの読み込み回数が多く、かつ、条件分岐回数も多いので、復号化処理量が非常に大きくなる問題がある。たとえば、「１１１１１１０１」からデータ「Ｎ」が得られるまでには、図１９の太線で示す経路をたどることになるので、１ビットずつの読み込み回数が８回、条件分岐が１６回必要となり、これは、非常に大きな処理量である。
【００２５】
次に、従来の復号化方法その２として、復号表を用いる方法について説明する。この方法は図２０に示すような復号表を予め用意しておくもので、ここでは、上述した例について説明する。上述した例では、最大符号長が８ビットであるので、可能である全ての８ビットパターン、つまり、２の８乗である２５６通りのすべての８ビットパターンが記述されている。
【００２６】
この復号表は２つの要素からなり、その１つめの要素は、８ビットパターンの中の有効ビット長としての符号長であり、２つめの要素は、その符号長のビットが示すデータである。たとえば、図２０において幾つか例を挙げれば、１〜２５６で示される番号（エントリ番号という）の１番目の８ビットパターンは「００００００００」であり、その有効ビット長である符号長は２ビット（ここでは左端からのビット数としているので、「００」が有効ビット）であって、その２ビットに対するデータは「Ａ」であることが記述され、また、エントリ番号の６５番目の８ビットパターンは「０１０００００００」であり、その有効ビット長である符号長は２ビット（「０１」）であって、その２ビットに対するデータは「Ｂ」であることが記述され、また、エントリ番号の２５６番目の８ビットパターンは「１１１１１１１１」であり、その有効ビット長である符号長は８ビット（「１１１１１１１１」）であって、その８ビットに対するデータは「Ｐ」であることが記述されている。
【００２７】
このような復号表を用いた復号化方法を図２１のフローチャートにより説明する。まず、処理対象となる可変長符号化データから８ビットを読み込む（ステップｓ３１）。そして、読み込んだ８ビットの符号に対応する符号長を図２０に示すような復号表から読み込み（ステップｓ３２）、読み込んだ符号長さ分だけ符号読み込み位置を進める（ステップｓ３３）。そして、読み込んだ８ビットに対応するデータを復号表から読み込んで（ステップｓ３４）、その読み込んだデータを復号結果とする（ステップｓ３５）。
【００２８】
以下、具体例について図２２を参照しながら説明する。ここでは、処理対象の可変長符号化データは前述同様「１０００００１１１１０１１１１１１１１０１」であるとする。
【００２９】
まず、図２２（ａ）に示すように、８ビット分の符号「１０００００１１」（図２２（ａ）の太線ｘ１を施した部分）を読み込む。そして、読み込んだ符号「１０００００１１」に対応する符号長を図２０に示す復号表から読み込む。この場合、読み込んだ符号「１０００００１１」は、図２０の復号表において、エントリ番号の１２９番から１６０番の間に存在するので、符号長「３」を読み込み、読み込んだ符号長「３」の分だけ（図２２（ｂ）の太線ｘ２で示す）符号読み込み位置を進める。そして、読み込んだ符号に対応するデータを復号表から読み込む。この場合、読み込んだ符号は「１０００００１１」であるので、それに対応するデータとして「Ｃ」を読み込み、そのデータを復号結果とする。
【００３０】
次に、図２２（ｂ）によって設定された符号読み込み位置から、図２２（ｃ）にを示すように、８ビット分の符号「０００１１１１０」（図２２（ｃ）の太線ｘ３を施した部分）を読み込む。そして、読み込んだ符号「０００１１１１０」に対応する符号長を図２０に示す復号表から読み込む。この場合、読み込んだ符号「０００１１１１０」は、図２０の復号表において、符号番号の２番から６４番の間に存在するので、符号長「２」を読み込み、読み込んだ符号長さ「２」の分だけ（図２２（ｄ）の太線ｘ４で示す）符号読み込み位置を進める。
【００３１】
そして、読み込んだ符号に対応するデータを復号表から読み込む。この場合、読み込んだ符号は「０００１１１１０」であるので、それに対応するデータとして「Ａ」を読み込み、そのデータを復号結果とする。以下、同様にして図２２（ｅ），（ｆ）のようにして復号結果を得て行く。
【００３２】
このように、復号表を利用した復号化処理は、１つの可変長符号化データに対する復号化処理において、８ビットのデータ読み込みが１回、復号表の参照が１回、符号読み込み位置の更新操作が１回といった処理が必要となるが、これは、前述の木構造を用いた復号化処理に比べれば、その処理量が大幅に少なくなる。
【００３３】
【発明が解決しようとする課題】
以上、従来の復号化方法について２つの方法を例にとって説明した。先に説明した木構造を用いた復号化方法では、１つの符号化データを構成する１つ１つのビットに対する復号化処理を行う際のビット読み込み回数や条件分岐などが、データによっては非常に大きくなる場合もある。このため、１つの符号化データを復号化するために、１ビットの読み込みや条件分岐を何回も繰り返し行う必要があることから処理量がきわめて大きくなるり、高速処理が要求されるシステムにおいては問題がある。
【００３４】
これに対して復号表を用いる復号化方法では、処理量は大幅に削減でき高速処理が可能となるが、復号表サイズがきわめて大きくなる可能性があり、それを格納するために大容量のメモリを用意する必要が出てくる。なお、前述の例では、最大符号長が８ビットの例で説明したので、８ビット（２の８乗＝２５６）の復号表サイズで済んだが、ＪＰＥＧなどの場合には、最大符号長が１６ビットであり、その場合の復号表サイズは、１６ビット（２の１６乗＝６５５３６）にもなり、大容量のメモリを必要とする。さらには、もっと大きな最大符号長を有するものにも対応できるようにするには、復号表の大きさは膨大なものとなり、現実的な大きさの範囲を超えたものとなる。
【００３５】
そこで本発明は、マルチメディアデータなどに多用される可変長符号化データを高速に、かつ、少ないメモリ量で復号化を可能とすることを目的としている。
【００３６】
【課題を解決するための手段】
上述の問題を解決するため本発明の可変長符号化データの復号化方法は、可変長符号化データと復号化後のデータとが対応付けられた復号表を用いて復号化する可変長符号化データの復号化方法であって、前記可変長符号化データの最大符号長をｎビット（ｎは正の整数）としたとき前記ｎビットの符号の１番目からｎ番目の所定ビット位置に分割位置を設定して、前記設定された分割位置で分割されたあとのビット数の符号群で構成される復号表を、分割された数以上生成し、前記生成された復号表を順次参照することによって前記可変長符号化データの復号化を行うようにしている。
【００３７】
この可変長符号化データの復号化方法において、前記分割位置は、前記ｎビットの符号の１番目からｎ番目の各ビット位置ごとに各可変長符号化データのビット反転を調べ、ビット反転回数の少ないビット位置に設定するようにしている。
【００３８】
そして、前記分割位置はビット反転回数の少ない複数の箇所に設定され、前記複数の箇所を分割候補位置とし、それぞれの前記分割候補位置を少なくとも１箇所用いて複数通りの分割を行い、前記複数通りの分割ごとに複数の復号表の生成を試み、当該複数通りの分割ごとに生成された複数の復号表の合計の復号表サイズを求めるととともに、実際の復号処理における復号表参照回数を求め、両者の値に基づいて前記複数の分割候補位置のうち、少なくとも１箇所を実際に分割する分割位置として選定するようにしている。
【００３９】
また、このような可変長符号化データの復号化方法において、前記分割位置として設定された位置で分割されることによって、第１番目から第ｍ番目（ｍは正の整数）までの復号表が生成された場合、前記第１番目から第ｍ番目までの復号表を用いて復号化する際は、当該第１番目の復号表を参照して復号化を試み、復号化が可能であれば、当該第１番目の復号表によって復号化を行い、当該第１番目の復号表での復号化ができなければ当該第1番目の復号表により指示される次の復号表を参照して復号化を試みるというように、第１番目から必要に応じて第ｍ番目までのいずれかの復号表を選択して行うようにしている。
【００４０】
また、本発明の可変長符号化データの復号化装置は、可変長符号化データと復号化後のデータとが対応付けられた復号表を用いて復号化する可変長符号化データの復号化装置であって、前記可変長符号化データの最大符号長をｎビット（ｎは正の整数）としたとき前記ｎビットの符号の１番目からｎ番目の所定ビット位置に分割位置を設定して、前記設定された分割位置で分割されたあとのビット数の符号群で構成される復号表を、分割された数以上生成する復号表生成手段と、前記生成された復号表を、第１番目の復号表からの連鎖に従って参照することによって前記可変長符号化データの復号化を行う復号処理手段と、を有した構成としている。
【００４１】
この可変長符号化データの復号化装置において、前記復号表生成手段と復号処理手段に加えて符号ビット反転計測手段を有し、前記符号ビット反転計測手段は、前記ｎビットの符号の１番目からｎ番目の各ビット位置ごとに各可変長符号化データのビット反転を調べ、ビット反転回数の少ないビット位置を求める処理を行い、前記復号表生成手段は、前記符号ビット反転計測手段によって求められたビット反転回数の少ないビット位置を分割位置として複数の復号表を生成するようにしている。
【００４２】
そして、前記分割位置はビット反転回数の少ない複数の箇所に設定され、前記複数の箇所を分割候補位置とし、それぞれの前記分割候補位置を少なくとも１箇所用いて複数通りの分割を行い、前記複数通りの分割ごとに複数の復号表の生成を試み、当該複数通りの分割ごとに生成された複数の復号表の合計の復号表サイズを求めるととともに、実際の復号処理における復号表参照回数を求め、両者の値に基づいて前記複数の分割候補位置のうち、少なくとも１箇所を実際に分割する分割位置として選定するようにしている。
【００４３】
また、このような可変長符号化データの復号化装置において、前記分割位置として設定された位置で分割されることによって、第１番目から第ｍ番目（ｍは正の整数）までの復号表が生成された場合、前記第１番目から第ｍ番目までの復号表を用いて復号化する際は、当該第１番目の復号表を参照して復号化を試み、復号化が可能であれば、当該第１番目の復号表によって復号化を行い、当該第１番目の復号表での復号化ができなければ当該第1番目の復号表により指示される次の復号表を参照して復号化を試みるというように、第１番目から必要に応じて第ｍ番目まで順次、復号表を選択して行うようにしている。
【００４４】
また、本発明の可変長符号化データの復号化処理プログラムを記録した記録媒体は、可変長符号化データと復号化後のデータとが対応付けられた復号表を用いて復号化する可変長符号化データの復号化処理プログラムを記録した記録媒体であって、その可変長符号化データの復号化処理プログラムは、前記可変長符号化データの最大符号長をｎビット（ｎは正の整数）としたとき前記ｎビットの符号の１番目からｎ番目の所定ビット位置に分割位置を設定する手順と、前記設定された分割位置で分割されたあとのビット数の符号群で構成される復号表を、分割された数以上生成する手順と、前記生成された復号表を順次参照することによって前記可変長符号化データの復号化を行う手順とを含んでいる。
【００４５】
この可変長符号化データの復号化処理プログラムを記録した記録媒体において、前記分割位置は、前記ｎビットの符号の１番目からｎ番目の各ビット位置ごとに、各可変長符号化データのビット反転を調べ、ビット反転回数の少ないビット位置に設定するようにしている。
【００４６】
そして、前記分割位置はビット反転回数の少ない複数の箇所に設定され、前記複数の箇所を分割候補位置とし、それぞれの前記分割候補位置を少なくとも１箇所用いて複数通りの分割を行い、前記複数通りの分割ごとに複数の復号表の生成を試み、当該複数通りの分割ごとに生成された複数の復号表の合計の復号表サイズを求めるととともに、実際の復号処理における復号表参照回数を求め、両者の値に基づいて前記複数の分割候補位置のうち、少なくとも１箇所を実際に分割する分割位置として選定するようにしている。
【００４７】
また、このような可変長符号化データの復号化処理プログラムを記録した記録媒体は、前記分割位置として設定された位置で分割されることによって、第１番目から第ｍ番目（ｍは正の整数）までの復号表が生成された場合、前記第１番目から第ｍ番目までの復号表を用いて復号化する際は、当該第１番目の復号表を参照して復号化を試み、復号化が可能であれば、当該第１番目の復号表によって復号化を行い、当該第１番目の復号表での復号化ができなければ当該第１番目の復号表により指示される次の復号表を参照して復号化を試みるというように、第１番目から必要に応じて第ｍ番目まで順次、復号表を選択して行うようにしている。
【００４８】
このように本発明は、複数の復号表を生成し、生成された複数の復号表を参照して前記可変長符号化データの復号化を行うようにしている。なお、複数の復号表は、処理対象となる各可変長符号化データのビット反転を調べ、ビット反転回数の少ないビット位置を分割位置として得て、その分割位置で分割することによって生成される。このように、ビット反転回数の少ないビット位置を分割位置とすることによって、それによって生成される複数の復号表の合計のサイズを小さくすることができる。
【００４９】
なお、このとき前記分割位置はビット反転回数の少ない複数の箇所に設定され、その複数の箇所を分割候補位置とし、それぞれの分割候補位置を少なくとも１箇所用いて複数通りの分割を行い、その複数通りの分割ごとに複数の復号表の生成を試み、当該複数通りの分割ごとに生成された複数の復号表の合計の復号表サイズを求めるととともに、実際の復号処理における復号表参照回数を求め、両者の値に基づいて、どの分割候補位置を用いるかを決定するようにしている。このように、複数の分割候補位置のうちどれを用いて（２つ以上の分割候補位置を用いてもよい）分割した場合が最適なものとなるかを調べ、その結果、実際に分割する位置を決めるようにしているので、本発明を適用しようとするシステムの状況、つまり、使用できるメモリの容量やＣＰＵなどの処理能力を考慮して最適な復号表を得ることができる。
【００５０】
また、このように選択された分割位置により分割されて生成された複数（第１番目〜第ｍ番目）の復号表を用いて復号化する際は、処理対象符号に対し、まず、第１番目の復号表復号表を参照して復号化処理を試み、この第１番目の復号表での復号化ができなければ、当該復号表により指示される次の復号表を参照するという手順で復号化を行うようにしている。これら、第１番目〜第ｍ番目の復号表は、出現確率の高い順となっているので、上位の復号表によって復号化される確率が高く、ある１つの可変長符号化データを復号化する際に参照される復号表参照回数の平均値はそれほど大きくなることはなく、復号化を行うための全体的な処理量を小さく抑えることができる。
【００５１】
【発明の実施の形態】
以下、本発明の実施の形態について説明する。なお、この実施の形態で説明する内容は、本発明の可変長符号化データの復号化方法及び可変長符号化データの復号化装置についての説明であるとともに、本発明の可変長符号化データの復号化処理プログラムを記録した記録媒体における可変長符号化データの復号化処理プログラムの具体的な処理内容をも含むものである。
【００５２】
まず、本発明の概要を説明する。本発明は、基本的には復号表を用いて復号化処理するものであるが、復号表はそのサイズを大きくしないために、適宜分割して複数の復号表（復号表が始めから小さなサイズであれば特に分割する必要はなく１つの復号表であってもよい）を持つことに大きな特徴がある。なお、分割された複数の復号表は、それぞれの復号表サイズが異なってもよい。
【００５３】
たとえば、図１に示すような木構造（この木構造は図３で示した木構造と同じ内容である）を単純に２分割し（分割位置をこの場合はラインＬ５としそれを太線で示す）、それに対応する復号表を生成してみる。
【００５４】
図２はこれによって作成された複数の復号表、つまり、第１の復号表ｚ１とこの第１の復号表ｚ１によって指定される２つの第２の復号表（一方を第２の復号表（その１）ｚ２１とし、他方を第２の復号表（その２）ｚ２２とする）を示すもので、この場合、それぞれの復号表サイズは４ビット（２の４乗＝１６）で構成されることになる。なお、ここでは、前述した例と同様に最大符号長を８ビットとして説明し、また、ＡからＰまでの各データに対応付けられる符号は前述の例と同じとする。幾つか例を挙げれば、データＡは符号長「２」であって符号「００」で表され、データＢは符号長「２」であって符号「０１」で表され、データＣは符号長「３」であって符号「１００」で表され、、データＩは符号長「６」であって符号「１１１０１１」で表され、データＮは符号長「８」であって符号「１１１１１１０１」で表され、データＰは符号長「８」であって符号「１１１１１１１１」で表される。
【００５５】
このようにして作成された第１の復号表ｚ１と、第２の復号表（その１）ｚ２１または第２の復号表（その２）ｚ２２を用いて復号化する処理を図３のフローチャートにより説明する。まず、最初の復号表（第１の復号表ｚ１）を読み込む（ステップｓ４１）。そして、処理対象の可変長符号化データから当該第１の復号表ｚ１のサイズ分（図２で示される復号表においては４ビット分）を読み込んで（ステップｓ４２）、その読み込んだ復号表サイズ分の符号に対応する符号長を読み込む（ステップｓ４３）。その読み込まれた符号長が「０」であるか否かを見て（ステップｓ４４）、「０」であれば次の復号表を読み込んで（ステップｓ４５）、再びステップｓ４２以降の処理を行う。
【００５６】
一方、読み込んだ符号長が「０」でなければ、読み込んだ符号長さ分だけ符号読み込み位置を進め（ステップｓ４６）、読み込んだ符号に対応するデータを当該復号表から読み込む（ステップｓ４７）。そして、その読み込んだデータを復号結果とする（ステップｓ４８）。
【００５７】
以下、具体例について図４を参照しながら説明する。ここでは、前述同様、処理対象の可変長符号化データが「１０００００１１１１０１１１１１１１１０１」であるとする。
【００５８】
まず、図４（ａ）に示すように、処理対象の可変長符号化データから４ビット分の符号「１０００」（図４（ａ）の太線ｘ１を施した部分）を読み込む。そして、読み込んだ符号「１０００」に対応する符号長を図２に示す第１の復号表ｚ１から読み込む。この場合、読み込んだ符号「１０００」は、図２の第１の復号表ｚ１において、番号（エントリ番号）の９番に存在するので、符号長「３」を読み込み、読み込んだ符号長「３」の分だけ（図４（ｂ）の太線ｘ２で示す）符号読み込み位置を進める。そして、読み込んだ符号に対応するデータを第１の復号表ｚ１から読み込む。この場合、読み込んだ符号は「１０００」であるので、それに対応するデータとして「Ｃ」を読み込み、そのデータを復号結果とする。
【００５９】
次に、図４（ｂ）で設定された符号読み込み位置から、図４（ｃ）の図中の太線ｘ３を施した部分の４ビット分の符号「０００１」を読み込む。そして、読み込んだ符号「０００１」に対応する符号長を図２に示す第１の復号表ｚ１から読み込む。この場合、読み込んだ符号「０００１」は、図２の第１の復号表ｚ１において、エントリ番号の２番に存在するので、符号長「２」を読み込み、読み込んだ符号長「２」の分だけ（図４（ｄ）の太線ｘ４で示す）符号読み込み位置を進める。そして、読み込んだ符号に対応するデータを第１の復号表ｚ１から読み込む。この場合、読み込んだ符号は「０００１」であるので、それに対応するデータとして「Ａ」を読み込み、そのデータを復号結果とする。
【００６０】
次に、図４（ｄ）で設定された符号読み込み位置から、図４（ｅ）の図中の太線ｘ５を施した４ビット分の符号「０１１１」を読み込む。そして、読み込んだ符号「０１１１」に対応する符号長を図２に示す第１の復号表ｚ１から読み込む。この場合、読み込んだ符号「０１１１」は、図２の第１の復号表ｚ１において、エントリ番号の８番に存在するので、符号長「２」を読み込み、読み込んだ符号長「２」の分だけ（図４（ｆ）の太線ｘ６で示す）符号読み込み位置を進める。そして、読み込んだ符号に対応するデータを第１の復号表ｚ１から読み込む。この場合、読み込んだ符号は「０１１１」であるので、それに対応するデータとして「Ｂ」を読み込み、そのデータを復号結果とする。
【００６１】
次に、図４（ｆ）で設定された符号読み込み位置から、図４（ｇ）の図中の太線ｘ７を施した４ビット分の符号「１１１０」を読み込む。そして、読み込んだ符号「１１１０」に対応する符号長を図２に示す第１の復号表ｚ１から読み込む。この場合、読み込んだ符号「１１１０」は、図２の第１の復号表ｚ１において、エントリ番号の１５番に存在するので、符号長「０」を読み込み、読み込んだ符号長が「０」である場合には、図３のフローチャートで説明したように、次の復号表を読み込む処理を行う。つまり、この場合は、第２の復号表（その１）ｚ２１が指定されるので、それを読み込むことになる。そして、先に読み込んだ「１１１０」に続く４ビット分の符号「１１１１」を読み込んで、今度は、第２の復号表（その１）ｚ２１によって、上述したと同様の処理を行う。
【００６２】
すなわち、読み込んだ符号「１１１０」に対応する符号長を図２に示す第２の復号表（その１）ｚ２１から読み込むと、この場合、読み込んだ符号「１１１１」は、第２の復号表（その１）ｚ２１において、エントリ番号の１６番に対応する符号長「６」を読み込む。そして、読み込んだ符号長「６」の分だけ（図４（ｈ）の太線ｘ８で示す）符号読み込み位置を進める。そして、読み込んだ符号に対応するデータを第２の復号表（その１）ｚ２１から読み込む。この場合、読み込んだ符号は「１１１０」であるので、それに対応するデータとして「Ｉ」を読み込み、そのデータを復号結果とする。
【００６３】
次に、図４（ｈ）で設定された符号読み込み位置から、図４（ｉ）の図中の太線ｘ９を施した４ビット分の符号「１１１１」を読み込む。そして、読み込んだ符号「１１１１」に対応する符号長を図２に示す第１の復号表ｚ１から読み込む。この場合、読み込んだ符号「１１１１」は、図２の第１の復号表ｚ１において、エントリ番号の１６番に存在するので、符号長「０」を読み込み、読み込んだ符号長が「０」である場合には、図３のフローチャートで説明したように、次の復号表を読み込む処理を行う。つまり、この場合は、第２の復号表（その２）ｚ２２が措定されるので、それを読み込むことになる。そして、先に読み込んだ「１１１０」に続く４ビット分の符号「１１０１」を読み込んで、今度は、第２の復号表（その２）ｚ２２によって上述したと同様の処理を行う。
【００６４】
すなわち、読み込んだ符号「１１０１」に対応する符号長を図２に示す第２の復号表（その２）ｚ２２から読み込むと、この場合、読み込んだ符号「１１０１」は、第２の復号表（その２）ｚ２２において、エントリ番号の１４番に対応する符号長「８」を読み込む。そして、読み込んだ符号長さ「８」の分だけ（図４（ｊ）の太線ｘ１０で示す）符号読み込み位置を進める。そして、読み込んだ符号に対応するデータを他方の第２の復号表ｚ２２から読み込む。この場合、読み込んだ符号は「１１０１」であるので、それに対応するデータとして「Ｎ」を読み込み、そのデータを復号結果とする。
【００６５】
以上のような処理によって、可変長符号化データ「１０００００１１１１０１１１１１１１１０１」を復号化することができ、復号結果として「ＣＡＢＩＮ」というデータを得ることができる。この例では、第１の復号表とそれによって指定される第２の復号表（その１）ｚ２１または第２の復号表（その２）ｚ２２は、それぞれ１６個（合計４８個）の符号を持つだけの小さなデータサイズの復号表とすることができ、それらの復号表を用いて復号化する際の復号表の参照回数は、まず、第１の復号表ｚ１を参照し、それによって復号結果が得られない場合には、第２の復号表（その１）ｚ２１または第２の復号表（その２）ｚ２２のいずれかを参照すればよいので、最大でも２回の参照で済む。
【００６６】
以上説明した例は、図１に示すような木構造を単純に２分割し、その２分割によって図２のような第１の復号表ｚ１とそれによって指定される２つの第２の復号表ｚ２１，ｚ２２が得られた例であり、たまたま都合のよい復号表が得られた例である。
【００６７】
しかしながら、単純に２分割しても常に好都合な復号表が生成されるとは限らない。本発明はどのような状況、つまり、ＪＰＥＧなどのように最大符号長が１６ビットやそれ以上のデータを扱う場合にも、可能な限りそれぞれの復号表のサイズを小さく、しかも、複数の復号表の参照回数を少なくすることができるような最適な復号表を生成可能とすることを考慮する。以下、詳細に説明する。なお、説明をわかりやすくするため、ここでも最大符号長を８ビットとし、Ａ〜Ｐのデータに対する可変長符号化データは前述したと同様のものを使用する。
【００６８】
本発明は、Ａ〜Ｐの各データに対する符号化データにおいて、各データごとの可変長符号化データ同志における同じビット位置の符号ビットの反転回数を調べ、その反転回数に基づいて、復号表を分割する。
【００６９】
図５はこれまで説明した例に用いたデータＡからＰのそれぞれの符号化データを図示の左揃えで並べたとき、それぞれの符号ビット位置（ここでは、符号ビット位置の番号を右端から順に１〜８の数字で示している）における可変長符号化データ同志の符号ビット反転回数を記述したものである。
【００７０】
なお、図５において、Ａ〜Ｐの各データにおける可変長符号化データでは有効ビット部分のみが「１」または「０」で記述され、その他は「×」で示されている。たとえば、データＡに対する可変長符号化データは「００」で示すことができ、データＢに対する可変長符号化データは「０１」で示すことができ、データＣに対する可変長符号化データは「１００」で示すことができるといった具合である。そして、それぞれが左揃えで記述され、有効ビット以外は「×」が記述されている。
【００７１】
この図５において、黒い三角印で示す箇所は符号ビットが反転（「１」から「０」、または「０」から「１」）している箇所を示している。この符号ビット反転箇所を図５における同じ符号ビット位置で調べると、８番目の符号ビット位置では１回、７番目の符号ビット位置では３回、６番目の符号ビット位置では３回、５番目の符号ビット位置では１回、４番目の符号ビット位置では３回、３番目の符号ビット位置では７回、２番目の符号ビット位置では１回、１番目の符号ビット位置では３回というようになっている。
【００７２】
なお、図５に示す８番目から１番目の各符号ビット位置は、図１や図３で示した木構造に記されたラインＬ１，Ｌ２，Ｌ３，・・・上に存在するそれぞれの「枝」に対応している。すなわち、図５に示す各データＡ〜Ｐの８番目の符号ビット位置はラインＬ１上に存在するそれぞれの「枝」に対応し、７番目の符号ビット位置はラインＬ２上に存在するそれぞれの「枝」に対応し、以下同様に、６番目の符号ビット位置はラインＬ３上に存在するそれぞれの「枝」に対応するというようになっている。
【００７３】
このようにして符号ビット反転回数を調べ、得られた符号ビット反転回数を基に、分割候補位置を設定する。本発明では、符号ビット反転回数の少ない符号ビット位置を選んでそれに対応する箇所を分割候補位置とする。上述の例では、符号ビット反転回数の少ない箇所としては、８番目の符号ビット位置、５番目の符号ビット位置、２番目の符号ビット位置がそれぞれ１回で最も少ない。
【００７４】
そこで、これらの符号ビット反転回数の少ない符号ビット位置を分割候補位置とする。ただし、８番目の符号ビット位置で分割するのは現実的でないので、それを除く２箇所（５番目の符号ビット位置と２番目の符号ビット位置）を分割候補位置とする。なお、以下では、５番目の符号ビット位置を第１の分割候補位置といい、２番目の符号ビット位置を第２の分割候補位置という。
【００７５】
図６の木構造において、太線で示すラインＬ４は５番目の符号ビット位置（第１の分割候補位置）で分割した場合、太線で示すラインＬ７は２番目の符号ビット位置（第２の分割候補位置）で分割した場合である。なお、この図６に示される木構造は図１や図３の木構造とその構成内容は同じである。
【００７６】
このように、符号ビット反転回数の少ない順から幾つかの分割候補位置（ここでは２つの分割候補位置）を設定する。そして、第１の分割候補位置のみの１箇所で分割するケース（第１のケースという）と、第２の分割候補位置のみの１箇所で分割するケース（第２のケースという）と、第１の分割候補位置と第２の分割候補位置の２箇所で分割するケース（第３のケースという）の３つのケースを考える。
【００７７】
まず、第２のケースについて説明する。この第２のケースは、図６に示す木構造において、木構造を太線のラインＬ７で分割した場合であり、この場合、作成される復号表は図７に示すように、６ビットのサイズでなる第１の復号表ｚ１と２ビットのサイズでなる第２の復号表ｚ２を持つことになる。すなわち、図６に示す木構造において、太線Ｌ７よりも上位に存在する各データ（データＡ〜データＬ）は前述したようにそれぞれの符号長が「６」以下であるので、第１の復号表ｚ１のみを参照することで復号することができるが、太線Ｌ７よりも下位に存在する各データ（データＭ〜データＰ）は、前述したようにそれぞれの符号長が「８」であるので、第１の復号表ｚ１と第２の復号表ｚ２を参照することで復号することができる。
【００７８】
この場合も前述した図３のフローチャートに示す手順に従って処理を行うことができる。この場合は、まず、処理対象となる可変長符号化データから６ビットの可変長符号化データを読み込む。
【００７９】
そして、６ビットで確定できる場合（符号長「６」以下のデータ）には、第１の復号表ｚ１を参照することによって、データＡからデータＬを復号結果として得ることができるが、６ビットで確定できない場合（第１の復号表ｚ１では符号長「０」と記述）は、第２の復号表ｚ２を参照する。
【００８０】
幾つか具体例を挙げれば、可変長符号化データから６ビットの符号化データを読み込んだとき、その６ビットの符号化データが「１０００００」であるとすると、その符号長は第１の復号表ｚ１には「３」と記述されており、読み込んだ符号長さ「３」の分だけ符号読み込み位置を進め、読み込んだ符号に対応するデータを第１の復号表ｚ１から読み込む。この場合、読み込んだ符号は「１０００００」であるので、それに対応するデータとして「Ｃ」を読み込み、そのデータを復号結果とする。
【００８１】
また、可変長符号化データから６ビットの符号化データを読み込んだとき、その６ビットの符号化データが「１１１１１１」であるとすると、その符号長は第１の復号表ｚ１には「０」と記述されている。これにより、次の復号表（第２の復号表ｚ２）を読み込み、先に読み込んだ「１１１１１１」に続く符号を第２の復号表ｚ２のサイズ分（２ビット）を読み込む。読み込んだ２ビット分の復号データが、「０１」であったとすれば、その符号長は第２の復号表ｚ２には「８」と記述されており、読み込んだ符号長「８」の分だけ符号読み込み位置を進め、読み込んだ符号に対応するデータを第２の復号表ｚ２から読み込む。この場合、読み込んだ符号は「０１」であるので、それに対応するデータとして「Ｎ」を読み込み、そのデータを復号結果とする。
【００８２】
このように、第２のケースで分割した場合（第２の分割候補位置、つまり、ラインＬ７で分割した場合）、２つの復号表が作成され、第１の復号表ｚ１のサイズは６ビット（２の６乗＝６４）であり、第２の復号表ｚ２のサイズは２ビット（２の２乗＝４）であるため、合計の復号表サイズは６８となる。そして、この場合、最大の参照回数は２回であるが、第１の復号表ｚ１のサイズは６４、第２の復号表ｚ２のサイズは４であり、参照回数期待値は1.04となり、殆どは第１の復号表ｚ１を参照することで復号化データを得ることができる。
【００８３】
次に第３のケースについて説明する。この第３のケースは図６に示す木構造を太線で示すラインＬ４とＬ７の両方を用いて３分割した場合であり、この場合、作成される復号表は図８に示すように、３ビットの復号表サイズでなる第１の復号表ｚ１と同じく３ビットの復号表サイズでなる第２の復号表ｚ２と２ビットの復号表サイズでなる第３の復号表ｚ３の３種類である。
【００８４】
すなわち、図６に示す木構造において、太線で示すラインＬ４よりも上側に存在する各データ（データＡ〜データＥ）は、前述したようにそれぞれの符号長が「３」以下であるので、第１の復号表ｚ１を参照することで復号することができ、太線Ｌ４とＬ７との間に存在する各データ（データＦ〜データＬ）は、前述したようにそれぞれの符号長が「６」であるので、第１の復号表ｚ１と第２の復号表ｚ２を参照することで復号することができ、太線Ｌ７よりも下側に存在する各データ（データＭ〜データＰ）は、前述したようにそれぞれの符号長が「８」であるので、第１の復号表ｚ１、第２の復号表ｚ２、第３の復号表ｚ３をそれぞれ参照することで復号することができる。
【００８５】
この場合も図３のフローチャートに示す手順に従って処理を行うことができる。その具体例について図９を参照しながら説明する。この場合もこれまでの説明同様、処理対象の可変長符号化データが「１０００００１１１１０１１１１１１１１０１」であるとする。
【００８６】
ここでは、図９（ａ）に示すようにデータＣとＡは復号化処理が終了しているとして、それ以降の復号化処理について説明する。まず、図９（ａ）で設定された符号読み込み位置から、図９（ｂ）の図中の太線ｘ１を施した３ビット分の符号「０１１」を読み込む。そして、読み込んだ符号「０１１」に対応する符号長を図８の第１の復号表ｚ１から読み込むと、その符号長「２」を読み込み、読み込んだ符号長さ「２」の分だけ（図９（ｃ）の太線ｘ２で示す）符号読み込み位置を進める。そして、読み込んだ符号に対応するデータを第１の復号表ｚ１から読み込む。この場合、読み込んだ符号は「０１１」であるので、それに対応するデータとして「Ｂ」を読み込み、そのデータを復号結果とする。
【００８７】
同様にして、図９（ｃ）で設定された符号読み込み位置から、図９（ｄ）の図中の太線ｘ３を施した３ビット分の符号「１１１」を読み込む。そして、読み込んだ符号「１１１」に対応する符号長を図８の第１の復号表ｚ１から読み込むと、その符号長は「０」と記述されている。これにより、次の復号表（第２の復号表ｚ２）を読み込み、図９（ｅ）の太線ｘ４に示すように、先に読み込んだ「１１１」に続く符号を第２の復号表のサイズ分（３ビット）を読み込む。読み込んだ３ビット分の符号は「０１１」であるので、その符号長「６」を読み込み、読み込んだ符号長「６」の分だけ（図９（ｆ）の太線ｘ５で示す）符号読み込み位置を進める。そして、読み込んだ符号に対応するデータを復号表から読み込む。この場合、読み込んだ符号は「０１１」であるので、それに対応するデータとして「Ｉ」を読み込み、そのデータを復号結果とする。
【００８８】
続いて、図９（ｆ）で設定された符号読み込み位置から、図９（ｇ）の図中の太線ｘ６を施した３ビット分の符号「１１１」を読み込む。その読み込んだ符号「１１１」に対応する符号長を図２２の第１の復号表ｚ１から読み込むと、その符号長は「０」と記述されている。これにより、次の復号表（第２の復号表ｚ２）を読み込み、先に読み込んだ「１１１」に続く符号を第２の復号表のサイズ分（３ビット）を読み込む。読み込んだ３ビット分の符号（図９（ｇ）の太線ｘ７を施した部分）は、「１１１」であるので、その符号長は「０」と記述されており、この場合、次の復号表（第３の復号表ｚ３）を読み込み、先に読み込んだ「１１１」に続く符号を第３の復号表のサイズ分（２ビット）を読み込む。読み込んだ２ビット分の符号（図９（ｇ）の太線ｘ８を施した部分）は「０１」であるので、その符号長は「８」と記述されており、読み込んだ符号長さ「８」の分だけ符号読み込み位置を進め（図９（ｈ）の太線ｘ９で示す）、読み込んだ符号に対応するデータを復号表から読み込む。この場合、読み込んだ符号は「０１」であるので、それに対応するデータとして「Ｎ」を読み込み、そのデータを復号結果とする。
【００８９】
以上のような処理によって、可変長符号化データ「１０００００１１１１０１１１１１１１１０１」を復号化することができ、「ＣＡＢＩＮ」というデータを得ることができる。
【００９０】
このように、第３のケースで分割した場合（第１および第２の両方の分割候補位置、つまり、ラインＬ４とラインＬ７の両方で分割した場合）、３つの復号表が作成され、第１の復号表ｚ１と第２の復号表ｚ２のサイズはそれぞれ３ビット（２の３乗＝８）であり、第３の復号表ｚ３のサイズは２ビット（２の２乗＝４）であるため、合計の復号表サイズは２０となる。そして、この場合、最大の参照回数は３回であり、参照回数期待値は1.25となり、前述した第２のケースに比べると復号表を平均で1.25回参照することになり、少し参照回数が増えるが、合計の復号表サイズは２０と非常に小さくすることができる。
【００９１】
以上、第２のケースと第３のケースについて説明したが、第１のケースについても同様に考えることができる。ここでは詳細な説明は省略するが、第１のケースの場合は、第１及び第２の２つの復号表からなり、第１の復号表のサイズは３ビット（２の３乗＝８）であり、第２の復号表のサイズは５ビット（２の５乗＝３２）でとなる。したがって、合計の復号表サイズは４０、最大参照回数は２回、参照回数期待値は1.21となる。
【００９２】
図１０は上述した第１のケース（第１の分割候補位置のみで分割した場合）、第２のケース（第２の分割候補位置のみで分割した場合）、第３のケース（第１の分割候補位置と第２の分割候補位置の両方で分割した場合）のそれぞれにおける復号表の合計のサイズ、最大参照回数、参照回数期待値を一覧表として示す図であり、この図１０からもわかるように、それぞれのケースごとに特徴を持っている。たとえば、第２のケースは復号表の合計のサイズは、他のケースに比べて大きいが、参照回数期待値は最も小さく、殆どが第１の復号表を参照することで復号化できることがわかる。また、第３のケースは参照回数期待値は1.25と少し高い値となるが、復号表の合計のサイズは２０と他のケースに比べて小さくすることができ、復号表を記憶させるためのメモリ容量を小さくすることができる。また、第１のケースはこれらの中間的な内容である。
【００９３】
したがって、どのケースを選ぶかは使用するシステムの状況に応じて決めればよい。たとえば、メモリをできるだけ小さくする必要があれば、上述の３つのケースの中では第３のケースが最適であり、処理の高速化を優先するのであれば第２のケースが最適である。
【００９４】
図１１は復号表の分割処理手順を説明するフローチャートである。図１１において、まず、分割候補位置を求め（ステップｓ５１）、分割候補位置があるか否かを見て（ステップｓ５２）、なければ復号表分割処理は不成功として処理を終了する（ステップｓ５３）。一方、分割候補位置があれば、１つ以上の分割候補位置を選択する（ステップｓ５４）。なお、この分割候補位置は前述したように、符号ビット反転回数を調べて符号ビット反転回数の少ない順から分割候補位置とする。
【００９５】
そして、その１つ以上の分割候補位置がすでに調べた組み合わせかどうかを見て（ステップｓ５５）、すでに調べた組み合わせであれば、他の組み合わせはあるかどうかを調べ（ステップｓ５６）、他の組み合わせがあればステップｓ５４に戻り、他の組み合わせがなければステップｓ５１に戻る。
【００９６】
一方、ステップｓ５５においてすでに調べた組み合わせでないと判断した場合には、その分割候補位置に基づいて複数の復号表を生成する（ステップｓ５７）。そして、生成された複数の復号表のサイズの合計（Ｓ）を求め（ステップｓ５８）、さらに、それらの復号表による参照回数の合計（Ｔ）を求める（ステップｓ５９）。これら、復号表のサイズの合計（Ｓ）と参照回数の合計（Ｔ）が当該システムの条件を満たすか否かを調べ（ステップｓ６０）、条件を満たさなければステップｓ５４に戻り、条件を満たせば復号表分割処理が成功したとして処理を終了する（ステップｓ６１）。なお、条件を満たすかどうかは、復号表のサイズの合計（Ｓ）と参照回数の合計（Ｔ）としたが、参照回数の合計（Ｔ）を基に参照回数期待値を求めてその参照回数期待値を参照回数の合計（Ｔ）の代わりに用いるようにしてもよい。
【００９７】
また、図１２は本発明を実現するための可変長符号化データの復号化装置の構成を示す図であり、構成要素のみを列挙すれば、符号特性入力手段１、符号生成手段２、符号ビット反転計測手段３、復号表生成手段４、復号表記憶手段５、復号表選択手段６、復号表読み出し制御手段７、符号読み込み位置更新手段８、符号入力手段９、復号結果出力手段１０などを有した構成となっている。
【００９８】
符号特性入力手段１には図１５で示したような符号特性情報が入力され、このような符号特性情報に基づいて、符号生成手段２が図１６に示したアルゴリズムにより、たとえば、データＡ〜データＰに対して図１３で示したような可変長符号化データを生成する。
【００９９】
そして、符号生成手段２によって生成された可変長符号データから符号ビット反転計測手段３によって図５で説明したように符号ビット反転を調べ、これに基づいて、復号表生成手段４が複数の復号表（第１〜第ｍの復号表）を生成し、それを復号表記憶手段５に記憶させる。この復号表記憶手段５に記憶されている複数の復号表は、たとえば、図７や図８で示したようなものであり、複数の分割候補位置を用いて生成された複数の復号表のサイズの合計と参照回数の合計（参照回数期待値でもよい）を求め、それらが条件を満たすか否かを判断することによって生成されたものである
このようにして分割された複数の復号表を用いて復号化処理を行う際は、符号入力手段９に入力される処理対象となる可変長符号化データに対して、復号表選択手段６、復号表読み出し制御手段７、符号読み込み位置更新手段８、復号結果出力手段１０などからなる復号処理手段が図３に示すアルゴリズムに従って復号処理を行う。
【０１００】
なお、この復号処理についてはすでに詳細に説明したのでここでは簡単に説明する。まず、復号表読み出し制御手段７の制御によって復号表選択手段６が第１の復号表を読み込む。そして、復号表読み出し制御手段７は、符号入力手段９に入力された処理対象の可変長符号化データから当該第１の復号表のサイズ分の符号（４ビットで構成される復号表であれば４ビット分の符号）を読み込んで、その読み込んだ符号に対応する符号長を読み込み、その読み込まれた符号長が「０」であるか否かを見て、「０」であれば次の復号表を読み込むように復号表選択手段６に指示を出す。一方、読み込んだ符号長が「０」でなければ、符号読み込み位置更新手段８が、読み込んだ符号長さ分だけ符号読み込み位置を進めるとともに、復号表読み出し制御手段７が、読み込んだ符号に対応するデータを当該復号表から読み込む。そして、その読み込んだデータを復号結果として復号結果出力手段１０から出力する。
【０１０１】
以上説明したように、前述の実施の形態では、処理対象となる可変長符号化データの最大符号長が８ビットである場合について説明した。この場合、前述したように、第１のケース、第２のケース、第３のケースそれぞれにおける復号表の合計のサイズ、最大参照回数、参照回数期待値は、図１０によって示される通り、それぞれのケースによって異なってくる。したがって、どのケースを選ぶかは使用するシステムの状況に応じて決めればよい。
【０１０２】
ちなみに、この実施の形態と前述した従来の復号表を用いて復号化する方法と比べると、復号表の合計のサイズを大幅に小さくすることができ、復号表を記憶させるためのメモリを小さくできる。しかも、復号表を参照する回数もそれ程大きく増えることがないので高速処理を維持できることは勿論である。
【０１０３】
なお、前述の実施の形態の例では、最大符号長は８ビットの例であったが、本発明は、最大符号長が８ビットに限られるものではないことは勿論であり、最大符号長がそれよりも大きい可変長符号データに対しても同様に実施可能である。その他、本発明は以上説明した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲で種々変形実施可能となるものである。また、以上説明した本発明の処理を行う可変長符号化データの復号化処理プログラムは、フロッピィディスク、光ディスク、ハードディスクなどの記録媒体に記録させておくことができ、本発明はその記録媒体をも含むものである。また、ネットワークから処理プログラムを得るようにしてもよい。
【０１０４】
【発明の効果】
以上説明したように本発明によれば、複数の復号表を生成し、生成された複数の復号表を参照して前記可変長符号データの復号化を行うようにしている。なお、複数の復号表は、処理対象となる各可変長符号化データのビット反転を調べ、ビット反転回数の少ないビット位置を分割位置として得て、その分割位置で分割することによって生成される。このように、ビット反転回数の少ないビット位置を分割位置とすることによって、それによって生成される複数の復号表の合計のサイズを小さくすることができ、復号表を記憶させるメモリを小容量化することができる。
【０１０５】
なお、このとき前記分割位置はビット反転回数の少ない複数の箇所に設定され、その複数の箇所を分割候補位置とし、それぞれの分割候補位置を少なくとも１箇所用いて複数通りの分割を行い、その複数通りの分割ごとに複数の復号表の生成を試み、当該複数通りの分割ごとに生成された複数の復号表の合計の復号表サイズを求めるととともに、実際の復号処理における復号表参照回数を求め、両者の値に基づいて、どの分割候補位置を用いるかを決定するようにしている。このように、複数の分割候補位置のうちどれを用いて（２つ以上の分割候補位置を用いてもよい）分割した場合が最適なものとなるかを調べ、その結果、実際に分割する位置を決めるようにしているので、本発明を適用しようとするシステムの状況、つまり、使用できるメモリの容量やＣＰＵなどの処理能力を考慮して最適な復号表を得ることができる。
【０１０６】
このように本発明は、マルチメディアデータなどに多用される可変長符号化データを高速に、かつ、少ないメモリ量で復号化を可能とすることができる。
【図面の簡単な説明】
【図１】本発明の概要を説明する図であり、木構造で表される可変長符号化データを単純に２分割して復号表を生成する例を説明する図である。
【図２】図１の方法によって生成された複数の復号表の一例を示す図である。
【図３】本発明の復号処理手順を概略的に説明するフローチャートである。
【図４】図２で示した復号表を用いて処理対象の可変長符号化データの復号処理手順を説明する図である。
【図５】各データに対する可変長符号化データの各符号ビット位置における符号ビット反転回数を測定し、それによって分割候補位置の設定を説明する図である。
【図６】図５で得られた第１の分割候補位置（ラインＬ４）および第２の分割候補位置（ラインＬ７）を図１で示した木構造上で示す図である。
【図７】図６の木構造上を第２の分割位置で分割することによって生成された復号表を示す図である。
【図８】図６の木構造上を第１の分割候補位置と第２の分割候補位置の両方で分割することによって生成された復号表を示す図である。
【図９】図８の復号表を用いて処理対象の可変長符号化データの復号化処理手順を説明する図である。
【図１０】図６で示した第１の分割候補位置で分割した場合、第２の分割候補位置で分割した場合、第１及び第２の両方の分割候補位置で分割した場合の復号表サイズの合計、最大参照回数、参照回数期待値を示す図である。
【図１１】本発明の復号表生成処理を説明するフローチャートである。
【図１２】本発明の可変長符号化データの復号装置の構成を示す図である。
【図１３】幾つかのデータに対する固定長符号とそれぞれのデータの出現確率に基づく可変長符号の一例を示す図である。
【図１４】図１３で示した可変長符号を木構造で表した図である。
【図１５】図１３で示された可変長符号の特性を示す図である。
【図１６】図１５で示した可変長符号の特性に基づいて可変長符号を生成する手順を示すフローチャートである。
【図１７】図１４に示される木構造を用いて符号化する手順を説明する図である。
【図１８】従来より行われている復号化方法（その１）として木構造を用いて復号化する処理手順を示すフローチャートである。
【図１９】図１８の復号化手順により木構造をたどって復号化する例を示す図である。
【図２０】従来より行われている復号化方法（その２）として復号表を用いて復号化する場合の復号表の一例を示す図である。
【図２１】復号表を用いて復号化する処理手順を示すフローチャートである。
【図２２】図２１の復号表を用いて処理対象の可変長符号化データの復号処理手順を説明する図である。
【符号の説明】
１  符号特性入力手段
２  符号生成手段
３  符号ビット反転計測手段
４  復号表生成手段
５  復号表記憶手段
６  復号表選択手段
７  復号表読み出し制御手段
８  符号読み込み位置更新手段
９  符号入力手段
１０  復号結果出力手段
ｚ１  第１の復号表
ｚ２  第２の復号表
ｚ３  第３の復号表
【図１】
0003975661.tif 000002
【図２】
0003975661.tif 000003
【図３】
0003975661.tif 000004
【図４】
0003975661.tif 000005
【図５】
0003975661.tif 000006
【図６】
0003975661.tif 000007
【図７】
0003975661.tif 000008
【図８】
0003975661.tif 000009
【図９】
0003975661.tif 000010
【図１０】
0003975661.tif 000011
【図１１】
0003975661.tif 000012
【図１２】
0003975661.tif 000013
【図１３】
0003975661.tif 000014
【図１４】
0003975661.tif 000015
【図１５】
0003975661.tif 000016
【図１６】
0003975661.tif 000017
【図１７】
0003975661.tif 000018
【図１８】
0003975661.tif 000019
【図１９】
0003975661.tif 000020
【図２０】
0003975661.tif 000021
【図２１】
0003975661.tif 000022
【図２２】
0003975661.tif 000023