(57)【特許請求の範囲】
【請求項１】
オリジナルストリームのシンボルを、符号化されたストリームに圧縮するための方法であって、
（ａ）前記オリジナルストリームのシンボルのｍシンボルを、コードブックを使用して、前記符号化ストリームのｍ符号語に符号化するステップを含み、
前記ｍシンボルは、全部の組のシンボル値の１つ以上のシンボル値を含み、
前記コードブックは、前記全部の組のシンボル値の、一組の固定長符号語へのマッピングを表し、前記全部の組のシンボル値中の少なくとも１つのシンボル値は、前記コードブックにおいて２つ以上の異なる符号語に対応し、前記２つ以上の異なる符号語の各々は少なくとも１つの冗長ビットを含み、
前記ｍ符号語は、前記固定長の前記符号語に基づく前記符号化ストリーム中で規則的な間隔で出現し、
（ｂ）少なくとも１つの追加シンボルを、ｍ符号語に対応する前記符号化ストリームの前記ビットに符号化するステップ、を含む方法。
【請求項２】
前記シンボルは、ビデオまたはオーディオデータを表す、請求項１記載の方法。
【請求項３】
前記符号化ストリームは、前記シンボルのストリームより少ないビットを有し、それによって、前記符号化ストリームが前記シンボルのストリームより効率的に記憶または伝送されることを可能にする、請求項１記載の方法。
【請求項４】
前記２つ以上の異なる符号語の各々は、更に、可変長（ＶＬ）コードブックのＶＬ符号語に対応する一組のビットを含み、前記ＶＬ符号語は、前記少なくとも１つのシンボル値に対応する前記２つ以上の異なる符号語の各々と同一である、請求項１記載の方法。
【請求項５】
前記少なくとも１つの追加シンボルは、前記ｍ符号語が前記少なくとも１つの追加シンボルを符号化するのに充分な数の冗長ビットを含む場合、ｍ符号語に対応する前記符号化ストリームの前記ビットに符号化される、請求項１記載の方法。
【請求項６】
符号化したプログラムコードを有するマシン可読媒体であって、前記プログラムコードがマシンにより実行される場合、前記マシンはオリジナルストリームのシンボルを符号化ストリームに圧縮するための方法を実行し、前記方法は、
（ａ）前記オリジナルストリームのシンボルのｍシンボルを、コードブックを使用して、前記符号化ストリームのｍ符号語に符号化するステップを含み、
前記ｍシンボルは、全部の組のシンボル値の１つ以上のシンボル値を含み、
前記コードブックは、前記全部の組のシンボル値の、一組の固定長符号語へのマッピングを表し、前記全部の組のシンボル値中の少なくとも１つのシンボル値は、前記コードブックにおいて２つ以上の異なる符号語に対応し、前記２つ以上の異なる符号語の各々は少なくとも１つの冗長ビットを含み、
前記ｍ符号語は、前記固定長の前記符号語に基づく前記符号化ストリーム中で規則的な間隔で出現し、
（ｂ）少なくとも１つの追加シンボルを、ｍ符号語に対応する前記符号化ストリームの前記ビットに符号化するステップ、を含む、符号化したプログラムコードを上に有するマシン可読媒体。
【請求項７】
符号化ストリームを復号化シンボルのストリームに復号化するための方法であって、
（１）前記符号化ストリーム中のｍ符号語を復号化するステップを含み、前記ｍ符号語は、
（ａ）オリジナルストリームのシンボルのｍシンボルを、コードブックを使用して、前記符号化ストリームの前記ｍ符号語に符号化することによって生成され、
前記ｍシンボルは、全部の組のシンボル値の１つ以上のシンボル値を含み、
前記コードブックは、前記全部の組のシンボル値の、一組の固定長符号語へのマッピングを表し、前記全部の組のシンボル値中の少なくとも１つのシンボル値は、前記コードブックにおいて２つ以上の異なる符号語に対応し、前記２つ以上の異なる符号語の各々は、可変長（ＶＬ）コードブックのＶＬ符号語に対応する少なくとも１つの冗長ビットと一組のビットとを含み、前記ＶＬ符号語は、前記少なくとも１つのシンボル値に対応する前記２つ以上の異なる符号語の各々と同一であり、
前記ｍ符号語は、前記固定長の前記符号語に基づく前記符号化ストリーム中で規則的な間隔で出現し、
（ｂ）前記ｍ符号語が、前記少なくとも１つの追加シンボルを符号化することに充分な数の冗長ビットを含む場合、少なくとも１つの追加シンボルを、ｍ符号語に対応する前記符号化ストリームの前記ビットに符号化することによって生成され、（２）前記ｍ符号語に対応する前記符号化ストリームの前記ビットから前記少なくとも１つの追加シンボルを復号化するステップ、を含む方法。
【請求項８】
前記シンボルは、ビデオまたはオーディオデータを表す、請求項７記載の方法。
【請求項９】
前記符号化ストリームのビット数は、前記復号化シンボルのストリームより少なくし、それによって、前記符号化ストリームが前記復号化シンボルのストリームより効率的に記憶または伝送されることを可能にする、請求項７記載の方法。
【請求項１０】
前記ｍシンボルは、前記ｍ符号語から並列で復号化される、請求項７記載の方法。
【請求項１１】
前記ｍシンボルと前記少なくとも１つの追加シンボルとは、前記ｍ符号語から並列で復号化される、請求項１０記載の方法。
【請求項１２】
前記２つ以上の異なる符号語の各々は、更に、ＶＬコードブックのＶＬ符号語に対応する一組のビットを含み、前記ＶＬ符号語は、前記少なくとも１つのシンボル値に対応する前記２つ以上の異なる符号語の各々と同一である、請求項７記載の方法。
【請求項１３】
前記少なくとも１つの追加シンボルは、前記ｍ符号語が前記少なくとも１つの追加シンボルを符号化するのに充分な数の冗長ビットを含む場合、ｍ符号語に対応する前記符号化ストリームの前記ビットに符号化される、請求項７記載の方法。
【請求項１４】
マシン可読媒体であって、符号化したプログラムコードを有し、前記プログラムコードがマシンにより実行される場合、前記マシンは符号化ストリームを復号化シンボルのストリームに復号化するための方法を実行し、前記方法は、
（１）前記符号化ストリーム中のｍ符号語を復号化するステップを含み、前記ｍ符号語は、
（ａ）オリジナルストリームのシンボルのｍシンボルを、コードブックを使用して、前記符号化ストリームの前記ｍ符号語に符号化することにより生成され、
前記ｍシンボルは、全部の組のシンボル値の１つ以上のシンボル値を含み、
前記コードブックは、前記全部の組のシンボル値の、一組の固定長符号語へのマッピングを表し、前記全部の組のシンボル値中の少なくとも１つのシンボル値は、前記コードブックにおいて２つ以上の異なる符号語に対応し、前記２つ以上の異なる符号語の各々は、可変長（ＶＬ）コードブックのＶＬ符号語に対応する少なくとも１つの冗長ビットと一組のビットとを含み、前記ＶＬ符号語は、前記少なくとも１つのシンボル値に対応する前記２つ以上の異なる符号語の各々と同一であり、
前記ｍ符号語は、前記固定長の前記符号語に基づく前記符号化ストリーム中で規則的な間隔で出現し、
（ｂ）前記ｍ符号語が前記少なくとも１つの追加シンボルを符号化することに充分な数の冗長ビットを含む場合、少なくとも１つの追加シンボルを、ｍ符号語に対応する前記符号化ストリームの前記ビットに符号化することにより生成され、
（２）前記ｍ符号語に対応する前記符号化ストリームの前記ビットから前記少なくとも１つの追加シンボルを復号化するステップを含む、マシン可読媒体。
【発明の詳細な説明】
【０００１】
【発明の分野】
本発明は、データ圧縮に関し、詳細には、可変長符号化方策(scheme) に関する。
【０００２】
【関連技術の説明】
可変長（ＶＬ）符号は、幾つかのデータ圧縮アルゴリズムの重要な部分である。例えば、ＭＰＥＧ (Moving Picture Experts Group)（動画像符号化標準化組織）標準に基づくような、幾つかの従来のビデオ圧縮アルゴリズムは、（１）生の画素 (raw pixel) データ、または動き補償されたフレーム間画素差分データ (motion- compensated interframe pixel difference data) のブロックへ、離散コサイン変換（ＤＣＴ）のような、変換を適用すること、（２）結果として得られる変換係数のブロックを量子化すること、及び（３）結果として得られる量子化係数のブロックをランレングス符号化すること、により生成されるランレングス符号化されたデータへ可変長符号化を適用して、それで可変長符号化されたランレングス符号化データを生成する。
【０００３】
従来の非可変長符号化では、シンボルは、固定長データ（すなわち、全てのシンボルに対して同じビット数を有するデータ）により表される。例えば、十進整数の０から２５５に対応するシンボルは、８ビットのバイナリ値、それぞれ（００００００００）から（１１１１１１１１）により表すことができ、ここで、各８ビットのバイナリ値は、異なる整数を表す固定長（すなわち、８ビット）の符号語である。
【０００４】
可変長符号化では、一組のシンボルは、異なるビット数を有する一組のＶＬ符号語により表される。データ圧縮を達成するために、より少ないビットを有するＶＬ符号語が、好ましくは、より頻繁に出現するシンボルへ割当てられる。例えば、表 Iは、ハフマン型ＶＬ符号のコードブックを示し、それは、整数の桁数が増大するのに従い整数の出現頻度が減少する整数データを効率的に表すことに使用できる。一般に、コードブックは、シンボルと対応する符号語との間のマッピングを表す表である。この明細書では、用語「符号 (code)」と「符号語 (code word)」は互換可能で使用する。
【０００５】
【表１】
0004603659.tif 000002
【０００６】
表 Iにおける各ＶＬ符号は、接頭辞と１つ以上の自由ビットを含む。接頭辞は、その符号語にある全ビット数を識別する１つ以上のビットの組（表 Iでは、無、１つ、またはそれより多い「０」に先行される１）である一方で、自由ビットは、同じ全ビット数を有する異なる符号語の間を区別する。表 Iで「Ｘ」はＶＬ符号での自由ビットを表す。自由ビットは、０か１のいずれかに対応する。従って、例えば、表 Iで（１ＸＸ）により表される４つのＶＬ符号は、
ｏ  整数０を表すＶＬ符号（１００）
ｏ  整数１を表すＶＬ符号（１０１）
ｏ  整数２を表すＶＬ符号（１１０）、及び
ｏ  整数３を表すＶＬ符号（１１１）、
及び、類似して、他のコードブック記載項に対応する。
【０００７】
表 Iのコードブックが、大きな整数は小さな整数より頻繁には出現しないという少なくとも一般的な傾向を有する整数０〜２５５の組を符号化することに使用される場合、各整数を表すことに使用される平均ビット数は、固定長バイナリ表示のビット数である８より少ないであろう、それによって、固定長８ビットバイナリ符号を使用することに比較して、整数データの全体の組を表すことに使用されるビット数の総合的な低下を達成する。
【０００８】
可変長符号化データにおいて、ビット数は、ＶＬ符号からＶＬ符号へとで変化し得るので、従来のＶＬ符号化方策では、可変長符号化データは順次に復号化されなくてはならない。いずれの当該のＶＬ符号語のビット位置の、前のＶＬ符号語への依存性は、ＶＬ符号化データを復号化するプロセスの複雑さと待ち時間 (latency) とを増大させる。このＶＬ符号化の不利点は、全ての固定長符号語のビット位置が先験的に既知である、固定長符号化方策では出現しない。結果として、並列処理技術が、固定長符号化データの復号化へ容易に適用され得る。
【０００９】
【発明の概要】
本発明は、ＶＬ符号化データの連鎖における各ＶＬ符号のビット位置の、前のＶＬ符号語への依存性から結果として生じる、従来技術の可変長符号化における複雑さと待ち時間の問題を解決する符号化技術に向けられる。本発明は、可変長符号化の圧縮効率の利点と固定長符号化の既知のビット位置の利点とを融合する簡単で効率的な方式を提供する。本発明は、本発明により生成された符号化データに対する復号化器の実行法において、並列復号化処理の使用を含む、著しい改善を可能にする。
【００１０】
１つの実施の形態では、本発明は、オリジナルストリームのシンボルを符号化ストリームに圧縮する方法であって、
（ａ）オリジナルストリームのシンボルのｍシンボルを、コードブックを使用して、符号化ストリームのｍ符号語に符号化するステップを含み、
ｍシンボルは、全部の組のシンボル値の１つ以上のシンボル値を含み、
コードブックは、全部の組のシンボル値の、一組の固定長符号語へのマッピングを表し、全部の組のシンボル値中の少なくとも１つのシンボル値は、コードブックにおいて２つ以上の異なる符号語に対応し、２つ以上の異なる符号語の各々は少なくとも１つの冗長ビットを含み、
ｍ符号語は、固定長の符号語に基づく符号化ストリーム中で規則的な間隔で出現し、
（ｂ）少なくとも１つの追加シンボルを、ｍ符号語に対応する符号化ストリームのビットに符号化するステップを含む。
【００１１】
別の実施の形態では、本発明は、符号化ストリームを復号化シンボルのストリームに復号化するための方法であって、
（１）符号化ストリーム中のｍ符号語を復号化するステップを含み、
ｍ符号語は、
（ａ）オリジナルストリームのシンボルのｍシンボルを、コードブックを使用して、符号化ストリームのｍ符号語に符号化することにより生成され、
ｍシンボルは、全部の組のシンボル値の１つ以上のシンボル値を含み、
コードブックは、全部の組のシンボル値の、一組の固定長符号語へのマッピングを表し、全部の組のシンボル値中の少なくとも１つのシンボル値は、コードブックにおいて２つ以上の異なる符号語に対応し、２つ以上の異なる符号語の各々は、可変長（ＶＬ）コードブックのＶＬ符号語に対応する、少なくとも１つの冗長ビットと一組のビットとを含み、ＶＬ符号語は、少なくとも１つのシンボル値に対応する２つ以上の異なる符号語の各々と同一であり、
ｍ符号語は、固定長の符号語に基づく符号化ストリーム中で規則的な間隔で出現し、
（ｂ）ｍ符号語が少なくとも１つの追加シンボルを符号化することに充分な数の冗長ビットを含む場合、少なくとも１つの追加シンボルを、ｍ符号語に対応する符号化ストリームのビットに符号化することにより生成され、
（２）ｍ符号語に対応する符号化ストリームのビットから少なくとも１つの追加シンボルを復号化するステップを含む。
【００１２】
【詳細な説明】
本発明は、同じ全ビット数を有する少なくとも２つの符号が、単一シンボルへ割当てられる符号化技術へ向けられる。これらの「冗長」符号における１つ以上の自由ビットが、ストリーム中のいずれか他のシンボルを表すことに使用されるように、符号が割当てられる。
【００１３】
第１実施例、３シンボル組に対する２ビット符号
本発明を、第１に比較的単純な実施例を使用して説明する。符号化されるデータが、３シンボル、「Ａ」、「Ｂ」、と「Ｃ」で構成されると仮定する。表IIは、従来のＶＬコードブックを示し、ここで、シンボル「Ａ」、「Ｂ」、と「Ｃ」は、それぞれＶＬ符号語（０）、（１０）、と（１１）で表される。
【００１４】
【表２】
0004603659.tif 000003
【００１５】
表IIのコードブックを使用して、シンボル連鎖｛Ａ、Ｂ、Ａ、Ｃ｝は、（０、１０、０、１１）つまり単に（０１００１１）とＶＬ符号化されるであろう。シンボル連鎖の前知識なしでは、各先行するシンボルが復号化されなくては、及び復号化されるまで、（または、各先行するＶＬ符号の長さを決定するよう充分な度合まで少なくとも処理されるまで、）符号化連鎖（０１００１１）での各シンボルに対応するＶＬ符号のビット位置は、（全く最初のシンボルを除き）分からないであろう。これは、復号化処理が順次の手法でなされなくてはならず、復号化効率を達成するための並列処理技術の使用を排除することを暗示する。
【００１６】
表IIIは、本発明の１つの実施の形態による、シンボル「Ａ」、「Ｂ」、と「Ｃ」に対するコードブックを示す。表 IIIの符号は、全ての符号に同じ固定長を持たせるよう充分な数の「冗長」ビットＹを加えることにより、表 IIのＶＬ符号から構成された、ここで、各冗長ビットＹは、「０」か「１」のいずれかであり得る。表 IIIに示すように、シンボル「Ａ」は、２ビット符号（００）または２ビット符号（０１）のいずれかにより表し得る。
【００１７】
【表３】
0004603659.tif 000004
【００１８】
本発明の１つの実施の形態によると、連鎖｛Ａ、Ｂ、Ａ、Ｃ｝での最初の３シンボル｛Ａ、Ｂ、Ａ｝は、表IIIのコードブックを使用して（０Ｙ1、１０、０Ｙ2）と符号化されるであろう、ここで、Ｙ1とＹ2は、２つの異なる冗長ビットを識別する。第４シンボルは、次に、２つの冗長ビットＹ1とＹ2を使用して符号化でき、ここで、第１冗長ビットＹ1は、第４シンボルに対する２ビット符号での第１ビットに対応し、第２冗長ビットＹ2は、第４シンボルに対する２ビット符号での第２ビットに対応する。連鎖｛Ａ、Ｂ、Ａ、Ｃ｝における第４シンボルはシンボル「Ｃ」であり、それは表IIIに２ビット符号（１１）として表され、４シンボル連鎖｛Ａ、Ｂ、Ａ、Ｃ｝は、表IIIのコードブックを使用して６ビット符号連鎖（０１１００１）により表されるであろう。従って、表IIIが全てのシンボルに対して２ビット符号を定義しているとしても、連鎖｛Ａ、Ｂ、Ａ、Ｃ｝での４シンボルは、本発明によると、６ビットだけを使用して表すことができる。
【００１９】
符号連鎖（０１１００１）は、最初の３つの２ビット符号語を順次に復号化する一方で、第４符号語を復号化するために、シンボル「Ａ」に対して使用された符号語での冗長ビットを蓄積することにより、従来のＶＬ復号化と同様に、順次の手法で復号化できる。
【００２０】
代替として、符号連鎖（０１１００１）は、並列で復号化できる。詳細には、最初の３シンボルは、それらが全て２ビット符号語を使用して符号化されている事実により、それらのビット位置が先験的に既知である故に、並列で復号化できる。その上、次の段落で説明するように、第４シンボルも、最初の３シンボルの復号化と並行して復号化できる。
【００２１】
各６ビット符号連鎖を、一般に、（ｈｉｊｋｌｍ）と表すとする、ここで、各文字は、符号連鎖での異なるビットを表す。第４符号語の第１ビットｄ１は、次のように復号化できる、
ｄ１＝（（ｈ  ＡＮＤ  ｉ）ＸＯＲ（ｊ  ＡＮＤ  ｋ）、
そして、第４符号語の第２ビットｄ２は、次のように復号化できる、
ｄ２＝（（ｊ  ＡＮＤ  ｋ）ＸＯＲ（ｌ  ＡＮＤ  ｍ）、
ここで、ＸＯＲは、排他的論理和関数を表し、下線付きは、論理否定を表す（ここで、０＝１及び１＝０）。
【００２２】
先の例の６ビット符号連鎖（０１１００１）に対して、
ｄ１＝（（ｈ  ＡＮＤ  ｉ）ＸＯＲ（ｊ  ＡＮＤ  ｋ）
＝（（１  ＡＮＤ  １）ＸＯＲ（０  ＡＮＤ  ０）＝（１ＸＯＲ０）＝１
ｄ２＝（（ｊ  ＡＮＤ  ｋ）ＸＯＲ（ｌ  ＡＮＤ  ｍ）
＝（（０  ＡＮＤ  ０）ＸＯＲ（１  ＡＮＤ  １）＝（０ＸＯＲ１）＝１
その場合、第４符号語（ｄ１、ｄ２）＝（１１）、これはシンボル「Ｃ」に対する符号語である。この復号化処理は、最初の３シンボルの復号化と並行して実行でき、４シンボル連鎖｛Ａ、Ｂ、Ａ、Ｃ｝での全ての４シンボルを、６ビット符号連鎖（０１１００１）から同時に復号化する。
【００２３】
４シンボルが６ビットに符号化される、表IIIに基づく上記の符号化方策は、４シンボル連鎖の最初の３シンボル中に少なくとも２つのシンボル「Ａ」の出現があることを仮定する。この仮定の下で、第４シンボルを符号化するための少なくとも２つの冗長ビットがあるであろう。この符号化方策は、シンボル「Ａ」の出現率が、シンボル「Ｂ」と「Ｃ」と組合せた出現率の２倍の可能性（すなわち、ｐ（Ａ）＝ｐ（Ｂ）＋ｐ（Ｃ））である場合に最良に働く。シンボル「Ａ」の出現率がそれ未満である場合、符号化方策は、それに応じて、例えば、５シンボル連鎖を８ビットに符号化することに、調整できる。
【００２４】
どんな場合でも、各特定の符号化方策は、追加シンボルを符号化するために充分な数の冗長ビットを供給しない場合を含む、他の可能なシンボルの連鎖の各々をなお勘案する必要がある。例えば、最初の３シンボル中に２つより少ないシンボル「Ａ」の出現を有する４シンボル連鎖は、表 IIIのコードブックを使用する符号化データの最初の６ビット内に第４シンボルの各可能な値を正確に符号化することに必要とされる２つの冗長ビットを供給しないであろう。これらの他の可能な連鎖の取扱いは、以下の例に関して非常に詳細に探究する。
【００２５】
第２実施例、４シンボル組に対する３ビット符号
本発明の実施の形態の第２実施例として、４シンボル「Ａ」、「Ｂ」、「Ｃ」、と「Ｄ」に対する表 IVの従来の可変長コードブックを考える。
【００２６】
【表４】
0004603659.tif 000005
【００２７】
この従来のＶＬコードブックは、表Vに示すように、各符号語が３ビットを有することを確実にするよう充分な冗長ビットを加えることにより、本発明によるコードブックに変換できる。表Vのコードブックによると、シンボル「Ａ」に対する符号は、２つの冗長ビットＹを有する。その場合、シンボル「Ａ」は、４つの符号語（０００）、（００１）、（０１０）、または（０１１）のいずれかにより表し得る。同様に、シンボル「Ｂ」に対する符号は、１つの冗長ビットＹを有し、それ故に、シンボル「Ｂ」は、２つの符号語（１００）または（１０１）のいずれかにより表し得る。
【００２８】
【表５】
0004603659.tif 000006
【００２９】
符号化されるシンボルデータが、ｐ（Ａ）、シンボル「Ａ」の出現率、が０．５、ｐ（Ｂ）＝０．２５、とｐ（Ｃ）＝ｐ（Ｄ）＝０．１２５である通りであると仮定する。「Ａ」に対する符号は２冗長ビットを有し、「Ｂ」に対する符号は１冗長ビットを有するので、平均して、普通のシンボルの連鎖に対して符号語当り約１．２５冗長ビットがあるであろう。その上、各語の第２ビットは、およそ５０％の冗長ビットである確率を有する一方で、各語の第３（すなわち、最終）ビットは、およそ７５％の冗長ビットである確率を有する。表IIIに基づく符号化方策での場合であったように、これらの冗長ビットは、連鎖中の他のシンボルを符号化することに使用できる。
【００３０】
詳細には、表Vのコードブックは、３シンボル｛Ｓ１、Ｓ２、Ｓ３｝の連鎖を６ビットの符号化データを使用して符号化することに使用でき、ここで、Ｓ３のビットは、Ｓ１とＳ２に対する２つの３ビット符号語に埋込まれる。
【００３１】
ｏ  （ｂ１  ｂ２  ｂ３）が、第１シンボルＳ１に対する最下位（すなわち、最小のバイナリ値）符号語の３ビットを表す、
ｏ  （ｂ４  ｂ５  ｂ６）が、第２シンボルＳ２に対する最下位符号語の３ビットを表す、
ｏ  （ｒ１  ｒ２  ｒ３）が、第３シンボルＳ３に対する最下位符号語の３ビットを表す、及び
ｏ  （ｃ１  ｃ２  ｃ３  ｃ４  ｃ５  ｃ６）が、シンボル連鎖｛Ｓ１、Ｓ２、Ｓ３｝に対する符号化データの６ビットを表す、
とする。
表Vに示すように、（０００）がシンボル「Ａ」に対する最下位符号語であり、「Ｂ」に対して（１００）、「Ｃ」に対して（１１０）、及び、「Ｄ」に対して（１１１）。本発明の１つの実施の形態によると、３シンボル｛Ｓ１、Ｓ２、Ｓ３｝は、以下の符号化疑似コードを使用して符号化できる、
0004603659.tif 000007
この疑似コードは、「ｉｆ」ステートメントをシンプルロジックにアンラップすることによりソフトウエアまたはハードウエアで実行できる。
【００３２】
表 VIＡ−Ｂは、４シンボルの６４の異なる可能な３シンボル組合せへ符号化疑似コードを適用することから結果として得られる６ビットの符号化データ（ｃ１  ｃ２  ｃ３  ｃ４  ｃ５  ｃ６）を示す。
【００３３】
結果として得られた６ビット符号連鎖（ｃ１  ｃ２  ｃ３  ｃ４  ｃ５  ｃ６）は、以下の復号化疑似コードにより、３シンボル｛Ｓ１、Ｓ２、Ｓ３｝に復号化できる、
0004603659.tif 000008
先の例のように、全ての３シンボルは、並列で復号化でき、処理は、ソフトウエアまたはハードウエアのいずれかで実行できる。
【００３４】
表 VIＡ〜Ｂは、符号化疑似コードを使用して生成された６ビット符号化データの６４の異なる組へ復号化疑似コードを適用することから結果として得られる３ビットの復号化データ（ｄ１  ｄ２  ｄ３）も示す。符号化データでのビット値の隣の「ｘ」は、９ビットのオリジナルのシンボル連鎖へ符号化疑似コードを適用することから「間違い」ビット値が結果として得られた、状況を示す。同様に、復号化データでのビット値の隣の「ｘ」は、６ビットの符号化データへ復号化疑似コードを適用することから「間違い」ビット値が結果として得られた、状況を示す。
【００３５】
例えば、入力シンボル連鎖｛Ａ、Ｃ、Ｃ｝に対して、符号化疑似コードは、６ビットの符号データを（００１１１０）と生成するであろう一方で、復号化疑似コードは、３ビットの復号化データを（１１１）と生成するであろう。符号化データの最初の３ビットは（００１）であり、これはシンボル「Ａ」に対する４つの符号値の１つである。符号化データの第２の３ビットは（１１０）であり、これはシンボル「Ｃ」に対する符号値である。これは、復号化疑似コードの最初の２ステップが、オリジナルの３シンボル連鎖での最初の２シンボルに対する正しい値を生出するであろうことを意味する。しかし、第３シンボルに対する３ビットの復号化データは（１１１）であり、これは、シンボル「Ｄ」に対応し、オリジナルの連鎖での第３シンボルであった「Ｃ」ではない。従って、符号化と復号化の疑似コードの組合せは、入力連鎖｛Ａ、Ｃ、Ｃ｝に対する正しい復号化連鎖を生出しない。
【００３６】
別の例として、入力シンボル連鎖｛Ｂ、Ｂ、Ｄ｝に対して、符号化疑似コードは、６ビットの符号データを（１０１１１０）と生成するであろう一方で、復号化疑似コードは、３ビットの復号化データを（１１１）と生成するであろう。符号化データの最初の３ビットは（１０１）であり、これはシンボル「Ｂ」に対する２つの符号値の１つである。符号化データの第２の３ビットは（１１０）であり、これはシンボル「Ｃ」に対する符号値である。第３シンボルに対する３ビットの復号化データは（１１１）であり、これはシンボル「Ｄ」に対応する。従って、この場合には、第１と第３のシンボルは正しく復号化されるであろうが、第２シンボルは、正しいシンボル「Ｂ」の代りに「Ｃ」と復号化されるであろう。
【００３７】
３シンボルの２つが間違って復号化されるであろう、なお他の組合せがある。例えば、入力シンボル連鎖｛Ｄ、Ｃ、Ｂ｝は、符号化と復号化の疑似コードを使用して、｛Ｄ、Ｄ、Ａ｝と間違って復号化されるであろう。
【００３８】
符号化と復号化の疑似コードが正しい３シンボル連鎖を再生しないこれらの組合せの例にも関らず、表VIＡ−Ｂを検査すると、多くの組合せが実際正しい結果へ符号化し復号化することが明らかになる。詳細には、｛Ａ、Ａ｝、｛Ａ、Ｂ｝、または｛Ｂ、Ａ｝で始まる全ての３シンボルの組合せは、第３シンボルの値が何であろうと正しく符号化し復号化するであろう。これらは、最初の２シンボルが、第３の３ビットシンボルを符号化することにその後使用できる、冗長ビットを合計少なくとも３つ有する、組合せである。
【００３９】
加えて、充分な数の冗長ビットが無いように見える場合でさえ、正しい結果を生成する多くの他のシンボルの組合せがある。例えば、入力シンボル連鎖｛Ｃ、Ａ、Ｄ｝は、全ての３シンボル中に２つの冗長ビットしかないのに、偶然正しく符号化し復号化する。
【００４０】
表VIＡ〜Ｂでの結果は、符号化と復号化の疑似コードに具現化される符号化方策に対して数多くの異なる可能な実行法を示唆する。実行法の１つのカテゴリは、無損失符号化に対応し、そこでは、復号化シンボル連鎖が、オリジナルの入力シンボル連鎖と同一であると保証される。別の種類は、多損失符号化に対応し、そこでは、正確な復号化に対する要求事項が緩和される。
【００４１】
１つの可能な多損失実行法は、シンボルストリームでの各及びことごとくの３シンボル連鎖へ符号化と復号化の疑似コードを適用することである。結果として得られる復号化シンボルストリームは、オリジナルの入力シンボルストリームと多分同一でないであろうが、用途により、誤りは許容可能であり得る。例えば、ビデオ圧縮用途では、符号化／復号化の誤りは、人間の眼に知覚され得ない。その上、「良い」組合せ（すなわち、正しく符号化し復号化するもの）の出現頻度が、「悪い」組合せ（すなわち、間違って符号化し復号化するもの）の出現頻度をはるかに超える場合（そのような符号化方策が使用される場合であるべきであるように）、誤りは、なおさら許容可能であろう。
【００４２】
本発明の下で無損失符号化を達成する１つの方式は、符号化器で、シンボルを符号化する前に、３シンボル連鎖が、「良い」組合せに対応するか「悪い」組合せに対応するかを決定することであろう。３シンボルが「良い」組合せに対応する場合、符号化疑似コードは、対応する６ビットの符号化データを生成するよう無事に適用できる。しかし、３シンボルが「悪い」組合せに対応する場合、３シンボルの組は、符号化器により異なって処理されよう。復号化器も、復号化処理中に、オリジナルの３シンボル連鎖が「良い」組合せであったか「悪い」組合せであったかを決定するある種の試験を適用するであろう。図１と２のそれぞれ符号化と復号化の処理は、そのような無損失実行法に対応する。
【００４３】
図１は、本発明の１つの可能な無損失実行法による、符号化疑似コードに対応するシンボル符号化処理のフロー図である。状況により、図１の処理は、シンボル連鎖における次の２シンボルかまたは次の３シンボルのいずれかを６ビットの符号化データに符号化する。図１で使用されるポインタは、シンボル連鎖中の次のシンボルを識別する。
【００４４】
詳細には、図１のステップ１０２でポインタが初期化された後に、現在の３シンボル連鎖｛Ｓ１、Ｓ２、Ｓ３｝での第１シンボルＳ１が、６ビット符号連鎖の最初の３ビット（ｃ１  ｃ２  ｃ３）に符号化され（ステップ１０４及び符号化疑似コードの行１）、ポインタは繰上され（ステップ１０６）、第２シンボルＳ２が、最後の３ビット（ｃ４  ｃ５  ｃ６）に符号化され（ステップ１０８及び行２）、ポインタは再度繰上される（ステップ１１０）。最初の２つのシンボルＳ１とＳ２が両方共「Ａ」である場合、または、１つが「Ａ」であり、もう一方が「Ｂ」である場合、Ｓ３が「Ａ」、「Ｂ」、「Ｃ」、または「Ｄ」のいずれであっても第３シンボルＳ３を符号化することに充分な冗長ビットがあるであろう。そうである場合（ステップ１１２で決定されるように）、第３シンボルＳ３は、冗長ビットを使用して６ビットの符号化データに符号化され（ステップ１１４）、次の組のシンボルを処理するようステップ１０４へ戻る前に、ポインタが再度繰上される（ステップ１１６）。厳密な符号化手順は、符号化疑似コードの行４−１０に提示されるように、第１シンボルＳ１が「Ａ」であるか否かに依存する。そうでなく、最初の２つのシンボルを符号化することから充分な冗長ビットが無い場合（ステップ１１２）、処理は、ポインタを更に繰上せずにステップ１０４へ戻る。
【００４５】
図１のシンボル符号化処理は、これらの３シンボルの最初の２つが、｛Ａ、Ａ｝、｛Ａ、Ｂ｝、または｛Ｂ、Ａ｝である場合のみ、３シンボルを６ビットの符号化データに符号化する。全ての他の可能な組合せは（符号化と復号化の疑似コードを使用して正しく符号化されるであろう他の組合せを含み）、２つのシンボルのみが対応する６ビットの符号化データに符号化されるような方式で取扱われる。これらの場合、次の３シンボル連鎖は、入力シンボルストリーム中のいずれのシンボルもとばさないように、ストリーム中のすぐ次のシンボルで始まる。
【００４６】
図２は、本発明の１つの可能な無損失実行法による、復号化疑似コードに対応するシンボル復号化処理のフロー図である。図２の復号化処理は、図１の符号化処理を使用して生成された符号化データを復号化するよう設計されている。その場合、状況により、図２の処理は、６ビットの符号化データの各組を２シンボルまたは３シンボルいずれかの復号化シンボル連鎖に復号化するよう使用される。
【００４７】
詳細には、次の６ビットの符号化データが図２のステップ２０２で取出された後に、３つのシンボルＳ１、Ｓ２、及びＳ３が、疑似コードのそれぞれ行１、２、及び３〜６を使用して並列で復号化される（ステップ２０４）。最初の２つのシンボルＳ１とＳ２が、第３シンボルＳ３を符号化することに充分な冗長ビットを提供するであろう値（すなわち、２つの「Ａ」、または「Ａ」と「Ｂ」と）を有する場合（ステップ２０６）、処理は、ステップ２０２へ戻り、次の６ビットの符号化データを復号化する。そうでない場合、充分な冗長ビットが無く、第３シンボルは破棄されなくてはならない（２０８）。
【００４８】
先に記載のように、図１と２の実行法は、無損失の符号化と復号化にそれぞれ対応し、ここでは、復号化シンボル連鎖は、オリジナルの入力シンボル連鎖と同一である。この無損失性に対して支払われる代償は、追加シンボルが各組の符号化データに符号化されたか否かを検証しなくてはならないことである（例えば、図２のステップ２０６）。代替として、本発明の多損失実行法は、たとえ符号化することに充分な冗長ビットが無い場合でも、オリジナルのシンボル連鎖を正確に再構成する復号化器の能力に悪影響を及ぼさず、追加のシンボルがビットストリームに「符号化される」。そのような多損失実行法の符号化処理は、ステップ１１２の無い図１に対応できる一方で、復号化処理は、ステップ２０６と２０８との無い図２に対応できる。結果として、そのような多損失実行法の下での復号化は、無損失実行法に対応する復号化より速く遂行できる。総合的な用途の要求事項に依存して、復号化速度が復号化精度より重要であるかもしれず、より速い多損失実行法が、より遅い無損失実行法より好ましいかもしれない。
【００４９】
一般に、一定数の符号の正しい復号化が、常に保証され得る。より正確には、所望する場合、最初のＮ／Ｋ符号の正しい復号化が保証され得る、ここで、Ｎは（グループに対する）ビット数であり、Ｋは各語長である。例えば、９ビットのグループが３ビット語で使用される場合、最初の３符号は、常に正しく復号化できることになる。一定の語の完全な復号化の保証は、一定の用途で非常に有益であり得るが、しかし、他の用途では、各ビットのグループの終りに誤りを集中させる代りに、誤りを幾つかの符号中に散在させることがより有益であり得る。
【００５０】
第３実施例、  ４シンボル組に対する３ビット符号
以下は、４シンボル組に対する３つの３ビット符号を６ビットのデータに符号化するための、本発明による対応する符号化と復号化の方策の別の例を提供する。この方策は、表 Vに示す第２実施例と同じコードブックに基づき、最初の２つの符号を常に正しく復号化することになり、オプションのステップが実行される場合、この方策は、利用可能なビット数と同じ数の正しいビットを第３符号において有することになる。符号化方策に対する疑似コードを以下に与える、
0004603659.tif 000009
0004603659.tif 000010
【００５１】
代替の実施の形態
本発明は、２つの特定の例に沿って説明された、第１実施例では、３シンボル組が表IIIの２ビット符号により表され、第２実施例では、４シンボル組が表Vの３ビット符号により表される。この技術に精通した者は理解するように、本発明は、より長い符号により表される大きな数のシンボルを有する他のシンボル組に沿って適用できる。
【００５２】
図１と２の実行法は、シンボルが個別に符号化され復号化される実施の形態に対応する。図１の復号化処理は、２つまたは３つのシンボルが並列で復号化されるように実行され得るが、しかし、なお、各シンボルは個別に復号化される。この技術に精通した者は理解するように、本発明は、例えば、２つ以上のシンボルの組に対応する表示を含有するルックアップテーブルを使用して、実行することもできる。そのような実行法では、２つ以上のシンボルが、例えば、入力及び符号化のビット連鎖をそれぞれ対応する符号化及び復号化のルックアップテーブルへのアドレスとして使用して、一緒に符号化及び／または復号化できる。用途により、そのようなルックアップテーブル技術は、リアルタイムで実行される必要がないかもしれない、符号化処理より復号化処理においてより有益であり得る。
【００５３】
一般に、特定のシンボル組と対応するコードブックとに対する符号化と復号化の手順は、以下の指針を使用して生成され得る、
（１）本明細書で先に記載のように「固定長」符号を生成する。
【００５４】
（２）利用可能になり得るビットの位置（と確率）を検証する。第２と第３の例では、ｃ２、ｃ３、ｃ５、とｃ６は利用可能であり得るが、ｃ１とｃ４は、決して利用可能でない。
【００５５】
（３）異なるグループのビットを各符号ビットへ関連させ、ＸＯＲ（及び／または他の論理）を使用して、復号化式を書く。第３実施例では、ｄ１＝ｃ５ＸＯＲｃ６；ｄ２＝ｃ２ＸＯＲｃ３；及びｄ３＝ｃ３ＸＯＲｃ５。
【００５６】
（ａ）幾つかの符号に一斉に出現するグループのビットを回避することが最良である。
【００５７】
（ｂ）ビットの１つが固定される場合、結果の情報内容を保存する故に、ＸＯＲが他の論理関係より好ましい。
【００５８】
（４）符号化方法を書く。符号化式を書く場合、どのビットが（例えば、第２と第３の例で「ｉｆ」ステートメントを生成することに）実際に利用可能であるかを識別する。より少ない自由ビットと組合せて存在するビットを最初に識別する（及び、符号化する／固定化する (freeze)）（例えば、第３実施例では、ｃ２、ｃ３とｃ６が自由である場合（第１の場合）、符号化方策は、ｒ３に対する式を符号化することで開始する、何故なら、それは１つだけの自由ビットを有するものであるから）。
【００５９】
（５）所望の場合、「ｉｆ」ステートメントは、単純論理（ＡＮＤ／ＯＲステートメント）にアンラップできる。
【００６０】
本発明の符号化と復号化の方策は、異なるデータ圧縮用途に対して実行できる。例えば、本発明は、ビデオ圧縮アルゴリズムの可変長符号化器に関連して実行でき、ここでは、可変長符号化器は、データの各ブロックに対して全符号長を一定に保つよう冗長ビットの存在を利用でき、それによって、データの圧縮と効率的（例えば、並列）復号化との両方を可能にする。
【００６１】
本発明は、これらの方法を実現するための方法と装置の形態で実施できる。本発明は、また、フロッピディスケット、ＣＤ−ＲＯＭ，ハードドライブ、または他のマシン可読媒体のような、有形の媒体中に具現化されるプログラムコードの形態で実施でき、プログラムコードが、コンピュータ等のマシンによりローディングされ、実行される場合、マシンは本発明を実現するための装置となる。本発明は、また、例えば、記憶媒体に格納される、マシンによりローディングされ及び／または実行される、または、電線または電気ケーブル上で、光ファイバを通し、または電磁波を介し、等の伝送媒体上で伝送される、プログラムコードの形態で実施でき、プログラムコードが、コンピュータ等のマシンによりローディングされ、実行される場合、マシンは、本発明を実現するための装置となる。汎用プロセッサ上で実行される場合、プログラムコード部分は、プロセッサと結合して、特定の論理回路に類似して動作する独特な装置を提供する。
【００６２】
本発明の本質を説明するために記載され図解された部分の詳細、材料、及び編成における種々の変更が、先に記載の特許請求の範囲に表出された本発明の原理と範囲から逸脱することなく、当該技術に精通した者によりなされ得ることは、更に理解されるであろう。
【図面の簡単な説明】
本発明の他の局面、特長、及び利点は、先に記載の詳細な説明、付帯する特許請求の範囲、及び添付図面からより完全に明白になるであろう。
【図１】本発明の１つの可能な無損失実行法による、符号化疑似コードに対応するシンボル符号化処理のフロー図を示す。
【図２】本発明の１つの可能な無損失実行法による、復号化疑似コードに対応するシンボル復号化処理のフロー図を示す。
【図１】
0004603659.tif 000011
【図２】
0004603659.tif 000012