(57)【特許請求の範囲】
【請求項１】
入力データを可変長符号化して符号化ストリームを生成する符号化装置と、
前記符号化ストリームを復号化して出力データを生成する復号化装置と、を備え、
前記符号化装置は、
入力データを可変長符号化して、第１の可変長符号を生成する可変長符号化器と、
ｎ個の前記第１の可変長符号を第２の可変長符号に変換する符号変換器と、
前記第２の可変長符号をバッファして、前記符号化ストリームを生成するバッファと、を有し、
前記第１の可変長符号の符号長はｍパターンあり、
前記第２の可変長符号の少なくとも一部をインデックスとして、前記第２の可変長符号の符号長を導出可能であり、
前記インデックスの数は、ｍｎより少なく、
前記復号化装置は、
前記第２の可変長符号の一部をインデックスとして、前記第２の可変長符号の符号長を導出する符号長導出部と、
前記導出された符号長に基づいて、前記符号化ストリームから前記第２の可変長符号を切り出す切り出し器と、
前記第２の可変長符号を、前記ｎ個の第１の可変長符号に変換する符号逆変換部と、
前記第１の可変長符号を復号化して前記出力データを生成する可変長復号化部と、を有する、データ処理システム。
【請求項２】
前記第１の可変長符号は、可変長である第１のプレフィックスを含み、
前記第２の可変長符号は、前記ｎ個の第１の可変長符号におけるｎ個の第１のプレフィックスに基づく第２のプレフィックスを含む、請求項１に記載のデータ処理システム。
【請求項３】
前記第２の可変長符号は、前記第２のプレフィックスと、可変長の第２のサフィックスとを含み、
前記符号変換器は、前記ｎ個の第１の可変長符号におけるｎ個の第１のプレフィックスを、前記第２のプレフィックスおよび前記第２のサフィックスに変換する変換テーブルを有する、請求項２に記載のデータ処理システム。
【請求項４】
前記符号変換器は、前記変換テーブルを生成するテーブル生成器を有し、
このテーブル生成器は、
前記ｎ個の第１の可変長符号で発生する前記第１のプレフィックスのすべての組み合わせを列挙し、
その組み合わせの総ビット長が等しいものをグループ化してグループを生成し、
前記グループごとに、互いに異なる前記第２のプレフィックスを割り当て、
前記グループごとに、前記第２のサフィックスのビット長をｃｅｉｌ｛ｌｏｇ２（｜Ｄｋ｜）｝（ここで、ｃｅｉｌは天井関数、Ｄｋは当該グループに属する前記組み合わせの数）ビットとし、
前記グループに属する組み合わせのそれぞれに、互いに異なる前記第２のサフィックスを割り当てて、前記変換テーブルを生成する、請求項３に記載のデータ処理システム。
【請求項５】
入力データを可変長符号化して、第１の可変長符号を生成する可変長符号化器と、
ｎ個の前記第１の可変長符号を第２の可変長符号に変換する符号変換器と、
前記第２の可変長符号から符号化ストリームを生成する出力部と、を備え、
前記第１の可変長符号の符号長はｍパターンあり、
前記第２の可変長符号の少なくとも一部をインデックスとして、前記第２の可変長符号の符号長を導出可能であり、
前記インデックスの数は、ｍｎより少ない、符号化装置。
【請求項６】
請求項５に記載の符号化装置により生成された符号化ストリームを復号化する復号化装置であって、
前記第２の可変長符号の一部をインデックスとして、前記第２の可変長符号の符号長を導出する符号長導出器と、
前記導出された符号長に基づいて、前記符号化ストリームから前記第２の可変長符号を切り出す可変長符号切り出し器と、
前記第２の可変長符号を、前記ｎ個の第１の可変長符号に変換する符号逆変換器と、
前記第１の可変長符号を復号化して出力データを生成する可変長復号化器と、を備える、復号化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、符号化装置、復号化装置およびデータ処理システムに関する。
【背景技術】
【０００２】
入力データを可変長符号化して得られた符号化ストリームを復号化する際、１サイクルあたり２つ以上の可変長符号を切り出すことで処理時間を短縮できる。そのために、符号化ストリームに含まれる複数の可変長符号をパッキングして並列処理することが行われている。しかしながら、複数の可変長符号をパッキングすると、その符号長のパターン数が多くなる。
【０００３】
符号長のパターン数が多くなると、可変長符号の符号長導出に使用されるテーブルのエントリ数が多くなり、処理の遅延が増大するおそれがある。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１０−５０６９７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
簡易に符号長を切り出すことができる符号化装置、復号化装置およびデータ処理システムを提供する。
【課題を解決するための手段】
【０００６】
実施形態によれば、入力データを可変長符号化して符号化ストリームを生成する符号化装置と、前記符号化ストリームを復号化して出力データを生成する復号化装置と、を備えるデータ処理システムが提供される。前記符号化装置は、入力データを可変長符号化して、第１の可変長符号を生成する可変長符号化器と、ｎ個の前記第１の可変長符号を第２の可変長符号に変換する符号変換器と、記第２の可変長符号をバッファして、前記符号化ストリームを生成するバッファと、を有する。前記第１の可変長符号の符号長はｍパターンあり、前記第２の可変長符号の少なくとも一部をインデックスとして、前記第２の可変長符号の符号長を導出可能であり、前記インデックスの数は、ｍｎより少ない。前記復号化装置は、前記第２の可変長符号の一部をインデックスとして、前記第２の可変長符号の符号長を導出する符号長導出部と、前記導出された符号長に基づいて、前記符号化ストリームから前記第２の可変長符号を切り出す切り出し器と、前記第２の可変長符号を、前記ｎ個の第１の可変長符号に変換する符号逆変換部と、前記第１の可変長符号を復号化して前記出力データを生成する可変長復号化部と、を有する。
【図面の簡単な説明】
【０００７】
【図１】第１の実施形態に係るデータ処理システムの概略構成を示すブロック図。
【図２】符号化装置１の処理動作の一例を示すフローチャート。
【図３】可変長符号化器１１の処理の一例を説明する図。
【図４】符号変換器１２の内部構成の一例を示すブロック図。
【図５】変換テーブル１２ａの一例を示す図。
【図６】図５の変換テーブル１２ａを生成する手順の一例を示す図。
【図７】復号化装置２の処理動作の一例を示す図。
【図８】プレフィックスＰｒｅ−Ｔと符号長との関係を示す図。
【図９】変換テーブル１２ａを生成する手順の一例を示す図。
【図１０】図９の手順により生成される変換テーブル１２ａを示す図。
【図１１】図９の手順により生成される変換テーブル１２ａを示す図。
【図１２】図９の手順により生成される変換テーブル１２ａを示す図。
【図１３】図９の手順により生成される変換テーブル１２ａを示す図。
【図１４】プレフィックスＰｒｅ−Ｔと符号長との関係を示す図。
【図１５】可変長符号化器１１の処理の一例を説明する図。
【図１６】プレフィックスＰｒｅ０〜Ｐｒｅ２の組み合わせを示す図。
【図１７】２分木を用いて変換テーブル１２ａを生成する手順の一例を示すフローチャート。
【図１８】図１７の手順に基づく２分木を示す図。
【図１９】図１７の手順で生成される変換テーブル１２ａを示す図。
【図２０】符号ＶＬＣ−Ｔと符号長との関係を示す図。
【発明を実施するための形態】
【０００８】
以下、実施形態について、図面を参照しながら具体的に説明する。
【０００９】
（第１の実施形態）
図１は、第１の実施形態に係るデータ処理システムの概略構成を示すブロック図である。データ処理システム１００は、符号化装置１と、復号化装置２とを備えている。このデータ処理システム１００は、符号化装置１により入力データを符号化して符号化ストリームを生成し、復号化装置２により符号化ストリームを復号化して出力データを得るものである。
【００１０】
符号化装置１について説明する。符号化装置１は、可変長符号化器１１と、符号変換器１２と、パッキングバッファ（出力部）１３とを有する。可変長符号化器１１は入力データをゴロムライス符号化してゴロムライス符号（第１の可変長符号）ＶＬＣを生成する。符号変換器１２はｎ個（ｎは２以上の整数）のゴロムライス符号ＶＬＣを１つの符号（第２の可変長符号）ＶＬＣ−Ｔに変換する。パッキングバッファ１３は符号ＶＬＣ−Ｔをバッファし、所定ビット長に達すると符号化ストリームとして出力する。
【００１１】
図２は、符号化装置１の処理動作の一例を示すフローチャートである。まず、可変長符号化器１１は入力データをゴロムライス符号化し、ゴロムライス符号ＶＬＣを生成する（Ｓ１）。
【００１２】
図３は、可変長符号化器１１の処理の一例を説明する図であり、可変長符号化器１１に入力される入力データの値と、可変長符号化器１１から出力される符号ＶＬＣの値との関係を示している。符号ＶＬＣは、可変長のプレフィックスＰｒｅと、固定長のサフィックスＳｕｆとから構成され、最下位ビットがサフィックスＳｕｆである。なお、図３は、入力データが０〜９の１０値を採り得るものとする。この場合、符号ＶＬＣが採り得る符号長は２〜６の５パターンである。
【００１３】
入力データが０および１の場合、プレフィックスＰｒｅは１ビットの“１”である。また、入力データが２以上の場合、プレフィックスＰｒｅは、ｃｅｉｌ｛（入力データ−１）／２｝ビットの“０”と、１つの“１”とを連結した値である（ｃｅｉｌ｛ｘ｝は天井関数であり、｛ｘ｝はｘ以上の最小の整数を表す）。サフィクスＳｕｆは１ビットの値であり、入力データが偶数であれば“０”、奇数であれば“１”である。入力データが２である場合、例えばプレフィックスＰｒｅ＝“０１”およびサフィックスＳｕｆ＝“０”となり、ＶＬＣ＝“０１０”となる。
【００１４】
次に、符号変換器１２は３つの符号ＶＬＣをパッキングして１つの符号ＶＬＣ−Ｔに変換する（Ｓ２）。複数の符号をパッキングすることで、復号時の処理を高速化できる。以下では、３つの符号ＶＬＣをＶＬＣ０，ＶＬＣ１，ＶＬＣ２とし、そのそれぞれのプレフィックスをＰｒｅ０〜Ｐｒｅ２、サフィックスをＳｕｆ０〜Ｓｕｆ２とする。そして、パッキングバッファ１３は生成された符号ＶＬＣ−Ｔをバッファし（Ｓ３）、符号化ストリームとして出力する。
【００１５】
図４は、符号変換器１２の内部構成の一例を示すブロック図である。符号化変換器１２は、変換テーブル１２ａと、連結器１２ｂと、テーブル生成器１２ｃとを有する。
【００１６】
変換テーブル１２ａは、符号ＶＬＣ０〜ＶＬＣ２のプレフィックスＰｒｅ０〜Ｐｒｅ２から、符号ＶＬＣ−ＴのプレフィックスＰｒｅ−ＴおよびサフィックスＳｕｆ−Ｔを生成する。プレフィックスＰｒｅ−ＴおよびサフィックスＳｕｆ−Ｔは可変長である。
【００１７】
連結器１２ｂは、生成されたプレフィックスＰｒｅ−ＴおよびサフィックスＳｕｆ−Ｔと、サフィックスＳｕｆ０〜Ｓｕｆ２とを連結して、符号ＶＬＣ−Ｔを生成する。すなわち、符号ＶＬＣ−Ｔは、可変長のプレフィックスＰｒｅ−ＴおよびサフィックスＳｕｆ−Ｔと、固定長のサフィックスＳｕｆ０〜Ｓｕｆ２とから構成される。よって、符号ＶＬＣ−Ｔの符号長は、プレフィックスＰｒｅ−Ｔのビット長およびサフィックスＳｕｆ−Ｔのビット長に、サフィックスＳｕｆ０〜Ｓｕｆ２の３ビットを加えたものである。
【００１８】
図５は、変換テーブル１２ａの一例を示す図である。変換テーブル１２ａは、プレフィックスＰｒｅ０〜Ｐｒｅ２から、プレフィックスＰｒｅ−ＴおよびサフィックスＳｕｆ−Ｔを特定する。このような、プレフィックスＰｒｅ０〜Ｐｒｅ２と、プレフィックスＰｒｅ−ＴおよびサフィックスＳｕｆ−Ｔとの関係は、前もってテーブル生成器１２ｃが生成する。なお、図５には「グループ」および「ＶＬＣ−Ｔの符号長」も合わせて描いている。
【００１９】
一例として、（ＶＬＣ０，ＶＬＣ１，ＶＬＣ２）＝（“０１０”，“０１１”，“１１”）の場合、プレフィックスＰｒｅ０〜Ｐｒｅ２を連結すると“０１０１１”であるから、Ｐｒｅ−Ｔ＝“００１”，Ｓｕｆ−Ｔ＝“１００”となる。結果として、ＶＬＣ−Ｔ＝“００１１０００１１”となる。
【００２０】
図６は、図５の変換テーブル１２ａを生成する手順の一例を示すフローチャートである。まず、３つの符号ＶＬＣ０〜ＶＬＣ２で発生するプレフィクスのすべての組み合わせ（Ｐｒｅ０＆Ｐｒｅ１＆Ｐｒｅ２）を列挙する（Ｓ１１）。図３の例では、プレフィックスは５パターンであるから、符号ＶＬＣ０〜ＶＬＣ２で５３＝１２５種類のプレフィクスが発生する。
【００２１】
続いて、発生する３つのプレフィックスの組み合わせ（Ｐｒｅ０＆Ｐｒｅ１＆Ｐｒｅ２）の総ビット長が等しいもののをグループ化し、グループＤ０〜Ｄｍを生成する（Ｓ１２）。なお、グループＤ０〜Ｄｍの順に上記総ビット数が長くなるものとする。図３の例では、プレフィクスの組み合わせ（Ｐｒｅ０＆Ｐｒｅ１＆Ｐｒｅ２）の総ビット長は、最短で３ビット、最長で１５ビットであり、１３個のグループＤ０〜Ｄ１２が生成される。そして、ｋの初期値を０とし（Ｓ１３）、テーブル生成器１２ｃはグループＤｋを順に選択し（Ｓ１４）する。
【００２２】
グループＤｋに対して以下のようにプレフィックスＰｒｅ−ＴおよびサフィックスＳｕｆ−Ｔを割り当てる。グループＤｋ−１のプレフィックスの最上位ビットに“０”を連結し、グループＤｋのプレフィックスＰｒｅ−Ｔとする（Ｓ１５）。そして、グループＤｋに含まれるプレフィックスの組み合わせに対して、ビット長ｃｅｉｌ｛ｌｏｇ２（｜Ｄｋ｜）｝のサフィックスＳｕｆ−Ｔを割り当てる（Ｓ１６）。ここで｜Ｄｋ｜はグループＤｋに含まれる組み合わせの数である。ただし、グループＤ０のＰｒｅ−Ｔは“１”とする（Ｓ１５）。また、グループＤ０にはサフィックスは割り当てられない（Ｓ１６）。
【００２３】
例えば、グループＤ１のプレフィックスＰｒｅ−Ｔは、グループＤ０のプレフィックス“１”の最上位ビットに“０”を連結してＰｒｅ−Ｔ＝“０１”とする（Ｓ１５）。また、グループＤ１に含まれる組み合わせの数｜Ｄ１｜＝４に対して、サフィックスＳｕｆ−Ｔのビット長はｃｅｉｌ｛ｌｏｇ２（｜Ｄ１｜）｝＝２ビットである。そして、テーブル生成器１２ｃは、グループＤ１におけるプリフィックスの組み合わせ（Ｐｒｅ０＆Ｐｒｅ１＆Ｐｒｅ２）＝“１１０１”，“１０１１”，“０１１１”に対して、サフィックスＳｕｆ−Ｔをそれぞれ“００”，“０１”，“１０”を割り当てる（Ｓ１６）。
【００２４】
以下、ｋを１ずつインクリメントしながら全てのグループＤ０〜Ｄｍに対して、プレフィックスＰｒｅ−ＴおよびサフィックスＳｕｆ−Ｔを割り当てる（Ｓ１７，Ｓ１８）。これにより、各グループＤ０〜Ｄｍについて、互いにビット長が異なる固有のプレフィックスＰｒｅ−Ｔが割り当てられる。
【００２５】
以上のようにして、図５に示す変換テーブル１２ａが生成される。図５において着目すべき点は、プレフィックスＰｒｅ−Ｔの値と、符号ＶＬＣ−Ｔの符号長とが１対１に対応している点である。例えば、プレフィックスＰｒｅ−Ｔが“１”であれば、符号ＶＬＣ−Ｔの符号長は４ビットである。また、プレフィックスＰｒｅ−Ｔが“０１”であれば、符号ＶＬＣ−Ｔの符号長は７ビットである。これにより、符号ＶＬＣ−ＴのプレフィックスＰｒｅ−Ｔをインデックスとして、当該符号ＶＬＣ−Ｔの符号長を導出できる。
【００２６】
続いて、復号化装置２について説明する。復号化装置２は、符号化ストリームバッファ２１と、符号長導出器２２と、可変長符号切り出し器２３と、符号逆変換器２４と可変長復号化器２５とを有する。
【００２７】
符号化ストリームバッファ２１は、符号化ストリームをバッファするとともに、符号化ストリームを可変長符号の符号長分シフトする。符号長導出器２２は符号化ストリームに含まれる各符号ＶＬＣ−Ｔの符号長を導出する。この符号長は符号化ストリームバッファ２１および可変長符号切り出し器２３に供給される。
【００２８】
可変長符号切り出し器２３は、供給された符号長に基づいて、符号化ストリームから各符号ＶＬＣ−Ｔを切り出す。符号逆変換器２４は、符号ＶＬＣ−Ｔに対して、符号変換器１２とは逆の処理を行ってゴロムライス符号ＶＬＣ０〜ＶＬＣ２を生成する。可変長復号化器２５はゴロムライス符号ＶＬＣをゴロムライス復号化して出力データを生成する。
【００２９】
図７は、復号化装置２の処理の一例を示すフローチャートである。まず、符号化ストリームバッファ２１は符号化ストリームをバッファする（Ｓ２１）。続いて、符号長導出器２２は、符号化ストリームにおけるプレフィックスＰｒｅ−Ｔを参照して、各符号ＶＬＣ−Ｔの符号長を導出する（Ｓ２２）。なお、図５から分かるように、符号ＶＬＣ−Ｔにおいて、初めて“１”が現れるまでがプレフィックスＰｒｅ−Ｔである。図８は、プレフィックスＰｒｅ−Ｔと符号長との関係を示す図である。プレフィックスＰｒｅ−Ｔの値と、符号ＶＬＣ−Ｔの符号長とが１対１に対応している。よって、符号長導出器２２は、符号化ストリームにおいてプレフィックスＰｒｅ−Ｔを検出でき、プレフィックスＰｒｅ−Ｔをインデックスとして、符号ＶＬＣ−Ｔの符号長を一意に導出できる。符号長が導出されると、可変長符号切り出し器２３は符号化ストリームから符号ＶＬＣ−Ｔを切り出す（Ｓ２３）。
【００３０】
本実施形態における符号長を導出するためのテーブルのエントリ数は１３個である。このエントリ数はグループ数と対応している。仮に、符号化時に符号変換器１２による変換処理を行わない場合、符号長が５パターンある３つの符号ＶＬＣのプレフィックスの種類は５３＝１２５個である。すなわち、符号長の導出に、エントリ数が１２５個であるテーブルが必要となってしまう。より一般的には、符号ＶＬＣの符号長がｍパターンあり、ｎ個の符号ＶＬＣから１つの符号ＶＬＣ−Ｔを生成する場合、ｍｎこのエントリが必要となってしまう。
【００３１】
これに対し本実施形態では、符号ＶＬＣ０〜ＶＬＣ２を、これらのプレフィックスＰｒｅ０〜Ｐｒｅ２の組み合わせの総ビット長に応じたプレフィックスＰｒｅ−Ｔを有する符号ＶＬＣ−Ｔに変換する。プレフィックスＰｒｅ０〜Ｐｒｅ２の組み合わせの総ビット長は３〜１５の１３通りであるため、テーブルのエントリ数を１３個に減らすことができる。すなわち、本実施形態では、一般的なエントリ数ｍｎより少なくできる。
【００３２】
続いて、符号逆変換器２４は、符号ＶＬＣ−Ｔに対して、符号変換器１２とは逆の処理を行ってゴロムライス符号ＶＬＣ０〜ＶＬＣ２を生成する（Ｓ２４）。具体的には、まず符号逆変換器２４は、変換テーブルを参照して、プレフィックスＰｒｅ−ＴからサフィックスＳｕｆ−Ｔを特定する。例えば、プレフィックスＰｒｅ−Ｔ＝“００１”であれば、サフィックスＳｕｆ−Ｔのビット長は３ビットであり、サフィックスＳｕｆ−Ｔの値を特定できる。なお、参照する変換テーブルは、予め変換テーブル１２ａと同様のものを符号逆変換器２４で持っているか、符号変換器１２と同様に、テーブル生成器を用いて生成する。
【００３３】
さらに、符号化変換器２４は、プレフィックスＰｒｅ−ＴおよびサフィックスＳｕｆ−Ｔから、ＶＬＣ０〜ＶＬＣ２をそれぞれ構成するプレフィックスＰｒｅ０〜Ｐｒｅ２を特定する。例えば、プレフィックスＰｒｅ−Ｔ＝“００１”かつサフィックスＳｕｆ−Ｔ＝“００１”であれば、（Ｐｒｅ０，Ｐｒｅ１，Ｐｒｅ２）＝（“１”，“００１”，“１”）である。
【００３４】
そして、符号逆変換器２４は、符号ＶＬＣ−ＴのサフィックスＳｕｆ−Ｔより後に付されているビットから、符号ＶＬＣ０〜ＶＬＣ２をそれぞれ構成するサフィックスＳｕｆ０〜Ｓｕｆ２を特定する。
【００３５】
以上により、符号逆変換器２４は符号ＶＬＣ−Ｔから３つの符号ＶＬＣ０〜ＶＬＣ２を得ることができる。そして、可変長復号化器２５はゴロムライス符号ＶＬＣ０〜ＶＬＣ２のそれぞれをゴロムライス復号化して出力データを生成する（Ｓ２５）。
【００３６】
第１の実施形態では、符号ＶＬＣ０〜ＶＬＣ２を、これらのプレフィックス長の総和に応じたプレフィックスＰｒｅ−Ｔを有する符号ＶＬＣ−Ｔに変換する。そのため、復号化の際にエントリ数の小さなテーブルで簡易に符号長を導出できる。
【００３７】
（第２の実施形態）
第２の実施形態では、変換テーブル１２ａが第１の実施形態とは異なる。以下、第１の実施形態との相違点を中心に説明する。
【００３８】
本実施形態におけるデータ処理システムの概略構成は、図１および図４に示すものとほぼ同様である。そして、テーブル生成器１２ｃによる変換テーブル１２ａの生成手法が第１の実施形態とは異なっている。
【００３９】
図９は、変換テーブル１２ａを生成する手順の一例を示す図である。また、図１０〜図１３は、図９の手順により生成される変換テーブル１２ａを示す図である。図９のＳ３１〜Ｓ３３は、図６のＳ１１〜Ｓ１３と同様である。続いて、テーブル生成器１２ｃはプレフィックスの組み合わせの総ビット長が連続する２つのグループＤｋ，Ｄｋ＋１を選択する（Ｓ３４）。これら２つのグループＤｋ，Ｄｋ＋１ごとに、以下のようにプレフィックスＰｒｅ−ＴおよびサフィックスＳｕｆ−Ｔを割り当てる。
【００４０】
プレフィックスＰｒｅ−Ｔは第１の実施形態と同様である（Ｓ３５）。そして、テーブル生成器１２ｃは下記（１）式を満たすか否かを判定する（Ｓ３６）。
Lp(a)≧ceil{log2(|Dk| + |Dk+1|)}, a∈Dk  ・・・（１）
【００４１】
（１）式の左辺Ｌｐ（ａ）はグループＤｋにおけるプレフィックスの組み合わせの総ビット長である。例えば、ｋ＝０すなわちグループＤ０，Ｄ１が選択された場合、Ｌｐ（ａ）＝３である。
【００４２】
（１）式を満たす場合、テーブル生成器１２ｃはサフィックスＳｕｆ−Ｔのビット長をｃｅｉｌ｛ｌｏｇ２（｜Ｄｋ｜＋｜Ｄｋ＋１｜）｝ビットとする（Ｓ３７）。一方、（１）式を満たさない場合、テーブル生成器１２ｃはＤｋ，Ｄｋ＋１に対するサフィックスＳｕｆ−Ｔのビット長をｃｅｉｌ｛ｌｏｇ２（｜Ｄｋ｜）｝、ｃｅｉｌ｛ｌｏｇ２（｜Ｄｋ＋１｜）｝ビットとする（Ｓ３８）。そして、テーブル生成器１２ｃはグループＤｋ，Ｄｋ＋１に含まれる各組み合わせに固有の値を割り当てる。
【００４３】
式（１）を満たさない場合、以下の式（１’）が成り立つ。
Lp(a)＜ceil{log2(|Dk| + |Dk+1|)}, a∈Dk  ・・・（１’）
式（１’）の右辺が集合Ｄｋ，Ｄｋ＋１に対応するＳｕｆ−Ｔのビット長となるが、これがＬｐ（ａ）より大きいので、少なくとも集合Ｄｋに関しては符号変換の結果圧縮率の悪化が発生している。悪化は、Ｐｒｅ−Ｔ＋Ｓｕｆ−Ｔ−Ｌｐ（ａ）である。よって、このような場合にＤｋのサフィックス長を式（１）ではなくｃｅｉｌ｛ｌｏｇ２（｜Ｄｋ｜）｝とすることによってＤｋに対するＳｕｆ−Ｔのビット削減を試みる。Ｄｋ＋１に関してはより悪化する可能性があるが、集合の選択順を考慮すると元の符号長はＤｋの方がＤｋ＋１より短く、可変長符号の前提として短い符号の方が発生確率が高いのでＤｋに対するＳｕｆ−Ｔを優先的に削減する。
【００４４】
以上の処理を全てのグループについて行う（Ｓ３９，Ｓ４０）。
【００４５】
本実施形態では、２つずつのグループにつき１つの固有のプレフィックスＰｒｅ−Ｔが割り当てられる。また、プレフィックスＰｒｅ−Ｔが符号ＶＬＣ−Ｔの符号長と１対１に対応している。
【００４６】
グループＤ０については、符号ＶＬＣ０〜ＶＬＣ２の総符号長が６であるのに対し、符号ＶＬＣ−Ｔの符号長は６である。符号ＶＬＣ−Ｔに変換することによる圧縮率の低下はない。グループＤ１についても符号ＶＬＣ−Ｔに変換することによる圧縮率の低下はない。
【００４７】
グループＤ２については、符号ＶＬＣ０〜ＶＬＣ２の総符号長が８であるのに対し、符号ＶＬＣ−Ｔの符号長は９である。符号ＶＬＣ−Ｔに変換することによる圧縮率の低下はわずか１ビットである。他のグループについても、符号ＶＬＣ−Ｔに変換することによる圧縮率の低下は最大でも２ビットである。
【００４８】
このように、本実施形態の手法によれば、第１の実施形態に比べて圧縮率の低下を抑えることができる。図１４は、プレフィックスＰｒｅ−Ｔと符号長との関係を示す図である。本実施形態では、エントリ数を７つまで減らすことができ、プレフィックスＰｒｅ−Ｔをインデックスとして、符号ＶＬＣ−Ｔの符号長も導出できる。
【００４９】
第２の実施形態では、２つの連続するグループにつき１つのプリフィックスＰｒｅ−Ｔを割り当て、（１）式に基づいてサフィックスＳｕｆ−Ｔのビット長を設定する。そのため、符号ＶＬＣ０〜ＶＬＣ２を１つの符号ＶＬＣ−Ｔに変換する際の圧縮率低下を抑えることができ、かつ、エントリ数を減らすことができる。
【００５０】
（第３の実施形態）
第３の実施形態では、２分木を用いて変換テーブル１２ａを生成するものである。以下、第１および第２の実施形態との相違点を中心に説明する。
【００５１】
説明を簡略化するために、本実施形態では、入力データが０〜３の４値を採り得るものとする。この場合、図１５は、入力データが０〜３の場合の可変長符号化器１１の入出力関係を示す図である。図１６は、符号ＶＬＣ０〜ＶＬＣ２のプレフィックスＰｒｅ０〜Ｐｒｅ２の組み合わせを示す図である。組み合わせの総ビット長は３〜６ビットの４種類であり、これらをそれぞれグループＤ０〜Ｄ３とする。
【００５２】
図１７は、２分木を用いて変換テーブル１２ａを生成する手順の一例を示すフローチャートである。また、図１８は、図１７の手順に基づく２分木を示す図である。さらに、図１９は、図１７の手順で生成される変換テーブル１２ａを示す図である。なお、本実施形態では、符号変換器１２が生成する符号ＶＬＣ−Ｔは、サフィックスＳｕｆ−Ｔを含まなくてもよい。
【００５３】
図１７のＳ４１〜Ｓ４３は、図６のＳ１１〜Ｓ１３と同様である。そして、テーブル生成器１２ｃはグループＤｋについて以下のＳ４４〜Ｓ４８の処理を行う。
【００５４】
まず、テーブル生成器１２ｃは組み合わせのそれぞれに対応する葉ノードを追加する（Ｓ４４）。各葉ノードは第１ラベルおよび第２ラベルを含む。第１ラベルはグループＤｋにおけるプレフィックスの総ビット長である。第２ラベルはグループＤｋのサフィックスの総ビット長すなわち３である。例えばグループＤ１には３つの組み合わせ“１１０１”，”１０１１”および“０１１１”が含まれるため、図１８に示す３つの葉ノードＬ１〜Ｌ３が追加される。そして、第１ラベルは４であり、第２ラベルは３である。
【００５５】
続いて、テーブル生成器１２ｃは、親ノードを持たない葉ノードが２つ未満になるまで（Ｓ４５）、任意の２つの葉ノードを子ノードとする親ノードを、内部ノードとして追加する（Ｓ４６）。このとき、内部ノードの第１ラベルおよび第２ラベルは、子ノードの第１ラベルおよび第２ラベルをそれぞれ引き継ぐ。例えばグループＤ１では、初め、親ノードを持たない葉ノードはＬ１〜Ｌ３の３つである。そこで、例えば葉ノードＬ１，Ｌ２を子ノードとする親ノードが、図１８に示す内部ノードＩ１として追加される。これにより、親ノードを持たない葉ノードはＬ３のみとなる。
【００５６】
続いて、テーブル生成器１２ｃは、親ノードを持たないノード（単に「ノード」といった場合、内部ノードでも葉ノードでもよい。以下同じ）が２つ未満になるまで（Ｓ４７）、親ノードを持たない２つのノードを選択し、これら２つのノードを子ノードとする親ノードを、内部ノードとしてさらに追加する（Ｓ４８）。親ノードを持たない内部ノードおよび葉ノードが複数ある場合には、葉ノードが優先して選択される。このとき、内部ノードの第１ラベルおよび第２ラベルは、子ノードの第１ラベルおよび第２ラベルをそれぞれ引き継ぐ。グループＤ１の例では、初め、親ノードを持たないノードは、内部ノードＩ１および葉ノードＬ３の２つである。そこで、内部ノードＩ１および葉ノードＬ３を子ノードとする親ノードが、図１８の内部ノードＩ２として追加される。これにより、親ノードを持たないノードは内部ノードＩ２のみとなる。
【００５７】
以上を全てのグループＤ０〜Ｄｍについて行う（Ｓ４９，Ｓ５０）。続いて、テーブル生成器１２ｃはグループを跨いで以下のＳ５１〜５４の処理を行う。
【００５８】
テーブル生成器１２ｃは、親ノードを持たないノードが１つになるまで（Ｓ５１）、親ノードを持たない２つのノードを選択し、これら２つのノードを子ノードとする親ノードを、内部ノードとして追加する（Ｓ５２）。選択の基準として、第一ラベルの値が大きな順に２つのノードを選択する。第１ラベルの値が最大のノードが複数存在する場合には、それらの中から第２ラベルの値が大きい順に２つのノードを選択する。内部ノードの第１ラベルおよび第２ラベルはそれぞれ、子ノードの第１ラベルおよび第２ラベルの平均値とする。最後に生成された内部ノードが根ノードとなり、２分木が完成する。例えば、図１８において、グループＤ２についての内部ノードＩ３およびグループＤ３についての葉ノードＬ４を子ノードとする親ノードが、内部ノードＩ４として追加される。続いて、内部ノードＩ２，Ｉ４を子ノードとする親ノードが、内部ノードＩ５として追加される。さらに、グループＤ０についての葉ノードＬ５および内部ノードＩ５を子ノードとする親ノードが、内部ノードＩ６として追加される。この時点で、親ノードを持たないノードが内部ノードＩ６のみとなる。よって、内部ノードＩ６が根ノードＲとなる。
【００５９】
根ノードＲが生成されると、テーブル生成器１２ｃは各枝に“０”または“１”を割り振る（Ｓ５３）。例えば、根ノードＲから葉ノードＬ５への枝には“１”が割り振られ、同内部ノードＩ５への枝には“０”が割り振られる。その他の枝にも “０”または“１”が割り振られる。なお、どちらの枝に“０”および“１”を割り振るのかは任意であり、図１８に限定されるものではない。
【００６０】
そして、テーブル生成器１２ｃは、２分木を根ノードから辿り、葉ノードに対応する各プレフィックスの組み合わせのそれぞれに符号ＶＬＣ−Ｔを設定する（Ｓ５４）。例えば、葉ノードＬ５（プレフィックスの組み合わせ“１１１”）には“１”が割り振られる。また、葉ノードＬ１（プレフィックスの組み合わせ“１１０１”）には“０１１１”が割り振られる。
【００６１】
以上のようにして、図１９に示す変換テーブル１２ａが生成される。なお、符号ＶＬＣ−Ｔは、プレフィックスＰｒｅ−Ｔに、サフィックスＳｕｆ０〜Ｓｕｆ２を連結したものである。よって、符号ＶＬＣ−Ｔの符号長はプレフィックスＰｒｅ−Ｔのビット長に、サフィックスＳｕｆ０〜Ｓｕｆ２の３ビットを加えたものである。図１９から分かるように、プリフィックスＰｒｅ０〜Ｐｒｅ２の組み合わせの総ビット数より、変換後のプリフィックスＰｒｅ−Ｔのビット数が多くなることはなく、変換による圧縮率の悪化は発生していない。
【００６２】
図２０は、符号ＶＬＣ−Ｔと符号長との関係を示す図である。本実施形態では、符号長導出器２２は、プレフィックスＰｒｅ−Ｔまたはその先頭の一部のビットに基づいて、符号長を導出する。例えば、プレフィックスＰｒｅ−Ｔが“０１１１”であっても“０１１０”であっても、符号ＶＬＣ−Ｔの符号長は７ビットである。よって、符号ＶＬＣ−Ｔの先頭３ビットが“０１１”であれば（すなわち、４ビット目が“０”であっても“１”であっても）、符号ＶＬＣ−Ｔの符号長は７ビットと、一意に定まる。
【００６３】
仮に符号変換器１２による変換を行わないと、符号長導出器２２では、エントリ数が８個のテーブルが必要になる。これに対し本実施形態では、図２０に示すようにエントリ数を６個に減らすことができる。
【００６４】
このように、第３の実施形態では、２分木を用いて変換テーブル１２ａを生成する。そのため、変換による圧縮率の悪化を抑えつつ、符号長導出に必要なテーブルのエントリ数を削減できる。
【００６５】
上述した実施形態で説明したデータ処理システムの少なくとも一部は、ハードウェアで構成してもよいし、ソフトウェアで構成してもよい。ソフトウェアで構成する場合には、データ処理システムの少なくとも一部の機能を実現するプログラムをフレキシブルディスクやＣＤ−ＲＯＭ等の記録媒体に収納し、コンピュータに読み込ませて実行させてもよい。記録媒体は、磁気ディスクや光ディスク等の着脱可能なものに限定されず、ハードディスク装置やメモリなどの固定型の記録媒体でもよい。
【００６６】
また、データ処理システムの少なくとも一部の機能を実現するプログラムを、インターネット等の通信回線（無線通信も含む）を介して頒布してもよい。さらに、同プログラムを暗号化したり、変調をかけたり、圧縮した状態で、インターネット等の有線回線や無線回線を介して、あるいは記録媒体に収納して頒布してもよい。
【００６７】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれると同様に、特許請求の範囲に記載された発明とその均等の範囲に含まれるものである。
【符号の説明】
【００６８】
１  符号化装置
１１  可変長符号化器
１２  符号変換器
１２ａ  変換テーブル
１２ｂ  連結器
１２ｃ  テーブル生成器
１３  パッキングバッファ
２  復号化装置
２１  符号化ストリームバッファ
２２  符号長導出器
２３  可変長符号切り出し器
２４  符号逆変換器
２５  可変長復号化器
【図１】
0005872513.tif 000002
【図２】
0005872513.tif 000003
【図３】
0005872513.tif 000004
【図４】
0005872513.tif 000005
【図５】
0005872513.tif 000006
【図６】
0005872513.tif 000007
【図７】
0005872513.tif 000008
【図８】
0005872513.tif 000009
【図９】
0005872513.tif 000010
【図１０】
0005872513.tif 000011
【図１１】
0005872513.tif 000012
【図１２】
0005872513.tif 000013
【図１３】
0005872513.tif 000014
【図１４】
0005872513.tif 000015
【図１５】
0005872513.tif 000016
【図１６】
0005872513.tif 000017
【図１７】
0005872513.tif 000018
【図１８】
0005872513.tif 000019
【図１９】
0005872513.tif 000020
【図２０】
0005872513.tif 000021