(57)【要約】  発明は、２以上の情報値をタプル順でタプルにグループ化し、異なる順序で同じ情報値を有するタプルに同じ符号語を割り当て、かつタプル順を示す順序情報を生成する符号化ルールを使用し、かつ符号語が順序情報と関連して出力される場合、情報値を符号化するための効率的な符号が生成できるとする知見に基づく。
2008536410.tif 000002
【特許請求の範囲】
【請求項１】
情報値を符号化するためのエンコーダであって、
２以上の情報値をタプル順にタプルにグループ化するグループ化器と、
符号化ルールを用いて、タプル順を示す順序情報およびタプルのための符号語を生成するための符号情報生成器を備え、符号化ルールでは、同じ符号語が、異なる順序で同じ情報値を有するタプルに割り当てられるようにされ、さらに、
符号語と、それに関連して順序情報とを出力するための出力インタフェースとを備える、エンコーダ。
【請求項２】
符号情報生成器は、
順序情報を生成するための順序エンコーダと、
異なる順序で同じ情報値を有するタプルを同じ符号語に割り当てるコードブックを用いて符合語を生成するためのエントロピーエンコーダとを含む、請求項１に記載のエンコーダ。
【請求項３】
順序エンコーダが、タプル内の情報値を再順序づけするべく動作して、タプル順をそのタプルに予め規定されたタプル順に変更し、その予め規定されたタプル順が、同じ情報値を有するタプルのグループのための情報値の符号化順を規定し、かつ順序エンコーダが、タプル順の偏りおよび符号化順を検出して符号化するべく動作し、かつ
エントロピーエンコーダが、符号化順に順序づけされた情報値を有するタプルに対して符合語を割り当てる、減少されたコードブックを有する、請求項２に記載のエンコーダ。
【請求項４】
順序エンコーダが、第１の情報値を第２の情報値と交換することにより、タプル内の情報値を再順序づけするべく動作する、請求項３に記載のエンコーダ。
【請求項５】
符号情報生成器は、タプル内の情報値の符号組み合わせを示す符号情報を生成する符号エンコーダを有し、
符号化ルールでは、タプル内における各情報値の符号のみ異なるタプルに対して、同じ符合語が割り当てられるようにされ、かつ
出力インタフェースが、符合語と関連する符号情報を出力するよう動作する、請求項１に記載のエンコーダ。
【請求項６】
符号エンコーダは、タプル内の情報値の符号を変更するべく動作して、符号の組み合わせを予め規定された符号組み合わせに変更し、この予め規定された符号組み合わせは、情報値の個々の符号においてのみ異なるタプル内の情報値の順序について符号化符号組み合わせを規定し、かつ
符号情報生成器は、エントロピーエンコーダを有し、エントロピーエンコーダが、同じ符合語を情報値の絶対値の同じ順序を有する各タプルに割り当てる、減じられたコードブックを有する、請求項５に記載のエンコーダ。
【請求項７】
符号エンコーダが、タプル内の第１および第２の情報値の符号を変更するべく動作する、請求項６に記載のエンコーダ。
【請求項８】
入力値を差分符号化して、情報値として入力値の差分符号化表現を得るための差分エンコーダをさらに備える、請求項１に記載のエンコーダ。
【請求項９】
差分符号化表現が、時間または周波数において差分符号化された入力値の表現である、請求項８に記載のエンコーダ。
【請求項１０】
情報値が、ビデオ信号またはオーディオ信号のフレームを記述する情報値を含む、請求項１に記載のエンコーダ。
【請求項１１】
情報値が、第１および第２のオーディオチャネル間の空間的相関を記述するＢＣＣパラメータを含み、かつＢＣＣパラメータが、以下のＢＣＣパラメータのリスト、すなわちチャネル間相関（ＩＣＣ）、チャネル間レベル差（ＩＣＬＤ）、チャネル間時間差（ＩＣＴＤ）、およびチャネル間位相差（ＩＰＤ）から選択される、請求項１に記載のエンコーダ。
【請求項１２】
符号化ルールでは、情報値の符号化により、異なる長さの符合語のシーケンスが生じるようにされている、請求項１のエンコーダ。
【請求項１３】
情報値に基づく符合語を復号化するためのデコーダであって、
符合語と、これに関連してタプル順を示す順序情報とを与えるための入力インタフェースを備え、このタプル順は情報値のタプル内の２以上の情報値の順序であり、さらに、
符合語を創出するために用いた符号化ルールに基づく復号化ルールを用いて、タプルを生成するための符号プロセッサを備え、
復号化ルールでは、異なるタプルが、異なる順序情報により関連付けられた同じ符合語から生成され、これらの異なるタプルが、異なるタプル順で同じ情報値を有する、デコーダ。
【請求項１４】
符号プロセッサが、
各符号語を予備タプルに割り当てるコードブックを用いて、予備タプルを生成するためのエントロピーデコーダと、
順序情報により示されるように予備タプル内の情報値を再順序づけすることによりタプルを生成するための順序デコーダとを備える、請求項１３に記載のデコーダ。
【請求項１５】
順序デコーダが、第１の情報値を第２の情報値と交換することにより、予備タプルの情報値を再順序づけするよう動作する、請求項１４に記載のデコーダ。
【請求項１６】
入力インタフェースが、タプル内の情報値の符号組み合わせを示す符号情報をさらに与え、かつ
符号プロセッサが、符号情報により示されるように予備タプル内の情報値の符号を変更することにより、予備タプルからタプルを生成するための符号デコーダをさらに含む、請求項１４に記載のデコーダ。
【請求項１７】
符号デコーダが、予備タプル内の各情報値の符号を変更するよう動作する、請求項１６に記載のデコーダ。
【請求項１８】
符号デコーダが、予備タプル内の第１および第２の情報値の符号を変更するべく動作する、請求項１６に記載のデコーダ。
【請求項１９】
情報値を差分復号化して、情報値の差分復号化表現を得るための差分デコーダをさらに備える、請求項１３に記載のデコーダ。
【請求項２０】
情報値の差分復号化表現が、時間または周波数において差分復号化される、請求項１９に記載のデコーダ。
【請求項２１】
情報値が、ビデオ信号またはオーディオ信号のフレームを記述する情報値を含む、請求項１３に記載のデコーダ。
【請求項２２】
情報値が、第１および第２のオーディオチャネル間の空間的相関を記述するＢＣＣパラメータを含み、かつＢＣＣパラメータが、以下のＢＣＣパラメータのリスト、すなわちチャネル間相関（ＩＣＣ）、チャネル間レベル差（ＩＣＬＤ）、チャネル間時間差（ＩＣＴＤ）、およびチャネル間位相差（ＩＰＤ）から選択される、請求項１３に記載のデコーダ。
【請求項２３】
情報値を符号化する方法であって、この方法が、
２以上の情報値をタプル順でタプルにグループ化するステップと、
タプル順を示す順序情報を生成するステップと、
符号化ルールを用いてタプルのための符合語を生成するステップを含み、
符号化ルールでは、同じ符合語が異なる順序で同じ情報値を有するタプルに割り当てられ、さらに、
符号語と、それに関連して順序情報とを出力するステップとを含む、方法。
【請求項２４】
情報値に基づく符合語を復号化するための方法であって、
符号語と、それに関連してタプル順を示す順序情報とを与えるステップを含み、このタプル順とは、情報値からなるタプル内の２以上の情報値の順序であり、さらに、
符号語を創出するために使用した符号化ルールに基づく復号化ルールを使用してタプルを生成するステップを含み、復号化ルールでは、異なるタプルが、異なる順序情報で関連付けられる同じ符号語から生成され、異なるタプルが異なるタプル順で同じ情報値を有し、さらに、
タプルを２以上の情報値に非グループ化するステップとを含む、方法。
【請求項２５】
コンピュータ上で作動させて、情報値を符号化するための方法を実行するためのプログラムコードを有するコンピュータプログラムであって、この方法が、
２以上の情報値をタプル順でタプルにグループ化するステップと、
タプル順を示す順序情報を生成するステップと、
符号化ルールを用いてタプルための符号語を生成するステップを含み、この符号化ルールでは、異なる順序で同じ情報値を有するタプルに同じ符号語が割り当てられるようにされ、さらに、
符号語と、それに関連して順序情報とを出力するステップとを備える、コンピュータプログラム。
【請求項２６】
コンピュータ上で作動させて、情報値に基づく符号語を復号化する方法を実行するためのプログラムコードを有するコンピュータプログラムであって、この方法が、
符合語と、それに関連してタプル順を示す順序情報とを与えるステップを含み、このタプル順は情報値のタプル内の２以上の情報値の順序であり、さらに、
符合語を創出するために用いた符号化ルールに基づく復号化ルールを用いてタプルを生成するステップを含み、復号化ルールでは、異なるタプルが、異なる順序情報により関連付けられた同じ符合語から生成され、これら異なるタプルは、異なるタプル順で同じ情報値を有し、さらに、
タプルを２以上の情報値に非グループ化するステップとを備える、コンピュータプログラム。
【請求項２７】
情報値に基づく符号化データであって、タプル順にタプルにおいて配列される２以上の情報値からなるタプルのための符号語と、
タプル順を示す順序情報とを含む、符号化データ。
【請求項２８】
コンピュータ読み取り可能な媒体に記憶される、請求項２７に記載の符号化データ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報値の符号化／復号化に関し、特に効率的な符号を生成するためのコンパクトなコードブックを用いたエントロピー符号化に関する。
【背景技術】
【０００２】
［発明の背景および先行技術］
最近、マルチチャネルオーディオ再生技術の重要性がますます増大している。これは、周知のｍｐ３技術等のオーディオ圧縮/符号化技術により、インターネットや他の帯域幅が限られた伝送チャネルを経由してオーディオ録音を配信することが可能になったことが要因としてあげられる。ｍｐ３符号化技術が有名になったのは、この技術のおかげで、ステレオ方式の全ての録音、すなわち第１または左ステレオチャネルおよび第２または右ステレオチャネルからなるオーディオ録音のデジタル表現を配信できるからである。
【０００３】
しかしながら、従来技術の２チャンネル音声システムには、基本的な欠点がある。そこで、サラウンド技術が開発された。推奨のマルチチャネルサラウンド表現は、２つのステレオチャネルＬおよびＲに加えて、追加の中央チャネルＣならびに２つのサラウンドチャネルＬｓおよびＲｓを備える。この参照音声形式は、３つの前方チャネルと２つのサラウンドチャネルとを意味する、３／２ステレオのことも指す。一般に、５つの伝送チャネルが必要である。再生環境においては、ラウドスピーカからある距離に位置で最適のスィートスポットを取得するには、５つの良好な場所に設置された５つ以上のスピーカが必要である。
【０００４】
先行技術において、マルチチャネルオーディオ信号を送信するために必要なデータ量を減らすための技術が、いくつか知られている。これらの技術は、ジョイントステレオ技術と呼ばれる。これについて、ジョイントステレオ装置６０を示す図９を参照する。この装置は、たとえば強度ステレオ（ＩＳ）またはバイノーラルキューコーディング（ＢＣＣ）等を実現する装置でもよい。この装置は、一般に入力として２以上のチャネル（ＣＨ１、ＣＨ２、…、ＣＨｎ）を受信しかつ少なくとも１つのキャリアチャネルおよびパラメトリックデータを出力する。パラメトリックデータは、デコーダ内で、元のチャネル（ＣＨ１、ＣＨ２、…、ＣＨｎ）の概算が計算できるように定義される。
【０００５】
通常、キャリアチャネルは、基礎信号の比較的細かい表現を与えるサブバンドサンプル、スペクトル係数、時間領域サンプル等を含み、パラメトリックデータは、スペクトル係数のサンプルのようなものは含まず、乗算、時間シフト、周波数シフト、位相シフト等による重み付けなど、ある再構成アルゴリズムを制御するための制御パラメータを含む。したがって、パラメトリックデータは、信号または関連のチャネルの比較的粗い表現のみを含む。数字を挙げると、キャリアチャネルにより必要とされるデータ量は、６０から７０ｋｂｉｔ／ｓであり、１チャネルのパラメトリック補助情報に必要とされるデータ量は、１．５から２．５ｋｂｉｔ／ｓの範囲である。パラメトリックデータの例は、後述のとおり、周知のスケールファクタである、強度ステレオ情報、またはバイノーラルキューパラメータである。
【０００６】
ＢＣＣ技術については、たとえば、ＡＥＳ会議論文５５７４の「ステレオおよびマルチチャネルオーディオ圧縮に適用するバイノーラル・キュー・符号化」、シー・ファーラーおよびエフ・バウムガルト、２００２年５月、ミュンヘン（AES convention paper 5574, “Binaural Cue Coding applied to Stereo and Multi-Channel Audio Compression", C. Faller, F. Baumgarte, May 2002, Munich）、ＩＥＥＥ  ＷＡＳＰＡＡ論文、「知覚パラメタライゼーションを用いる空間オーディオの効率的表現」、２００１年１０月、ニューヨーク州、モホンク（IEEE WASPAA Paper "Efficient representation of spatial audio using perceptual parametrization", October 2001, Mohonk, NY）、「フレキシブルレンダリングを伴うオーディオ圧縮に適用するバイノーラル・キュー・符号化」、シー・ファーラーおよびエフ・バウムガルト、ＡＥＳ第１１３回会議、ロサンジェルス、予稿５６８６、２００２年１０月（"Binaural cue coding applied to audio compression with flexible rendering", C. Faller and F. Baumgarte, AES 113th Convention, Los Angeles, Preprint 5686, October 2002）、および「バイノーラル・キュー・符号化−パートＩＩ：構成と応用」、シー・ファーラーおよびエフ・バウムガルト、音声とオーディオ処理に関するＩＥＥＥ会議、第１１巻、第６号、２００３年１１月（"Binaural cue coding-Part II: Schemes and applications", C. Faller and F. Baumgarte, IEEE Trans. on Speech and Audio Proc., volume level. 11, no. 6, Nov. 2003）に記載される。
【０００７】
ＢＣＣ符号化においては、ＤＦＴ（離散フーリエ変換）を用いて、オーバラッピングウィンドウでの変換に基づき、オーディオ入力チャネルのいくつかが、スペクトル表現に変換される。結果として得られる一定のスペクトルは、非オーバラップのパーティションに分けられる。各パーティションは、等価矩形帯域幅（ＥＲＢ）に概ね比例する帯域幅を有する。そして、ＢＣＣパラメータは、各パーティションについて、２つのチャネル間で予測される。これらのＢＣＣパラメータは、通常、参照チャネルに関してチャネルごとに与えられ、かつさらに量子化される。伝送されたパラメータは、最終的に所定の方式で計算され（符号化され）るが、これは、処理する信号の特定のパーティションにも依存し得る。
【０００８】
いくつかのＢＣＣパラメータが存在する。ＩＣＬＤパラメータは、たとえば２つの比較されるチャネルに含まれるエネルギの差（比率）を記述する。ＩＣＣパラメータ（チャネル間コヒーレンス／相関）は、２つのチャネル間の相関を記述し、これはその２つのチャネルの波形の類似性として理解することができる。ＩＣＴＤパラメータ（チャネル間時間差）は、２つのチャネル間の全体的時間シフトを記述し、ＩＰＤパラメータ（チャネル間位相差）は、信号の位相についてのそれを記述する。
【０００９】
オーディオ信号のフレーム処理においては、ＢＣＣ分析が、フレーム的、すなわち、時間可変で、かつ周波数によっても行われることに留意すべきである。これは、各スペクトル帯について、ＢＣＣパラメータを個々に得ることを意味する。これはまた、オーディオフィルタバンクが入力信号をたとえば３２の帯域通過信号に分解する場合、ＢＣＣ分析ブロックが、３２の帯域各々について、ＢＣＣパラメータのセットを得ることを意味する。
【００１０】
パラメトリック・ステレオとしても知られる関連技術が、ジェイ・ブリーバート、エス・ヴァン・デ・パル、エイ・コールラウシュ、イー・シュイジャーズ、「低ビットレートでの高品質パラメトリック空間オーディオ符号化」、ＡＥＳ、第１１６回会議、ベルリン、予稿６０７２、２００４年５月（J. Breebaart, S. van de Par, A. Kohlrausch, E. Schuijers, "High-Quality Parametric Spatial Audio Coding at Low Bitrates", AES 116th Convention, Berlin, Preprint 6072, May 2004）およびイー・シュイジャーズ、ジェイ・ブリーバート、エイチ・プルナゲン、ジェイ・エンゲガルド、「低複雑性パラメトリック・ステレオ符号化」、ＡＥＳ、第１１６回会議、ベルリン、予稿６０７３、２００４年５月（E. Schuijers, J. Breebaart, H. Purnhagen, J. Engdegard, "Low Complexity Parametric Stereo Coding", AES 116th Convention, Berlin, Preprint 6073, May 2004）に説明されている。
【００１１】
マルチチャネルオーディオ信号のパラメトリック符号化に関する最近のやり方（「空間オーディオ符号化」、「バイノーラル・キュー・符号化」（ＢＣＣ）等」を要約すると、ダウンミックス信号によるマルチチャネルオーディオ信号（モノフォニックかまたは複数チャネルを含み得る）およびその知覚空間音声ステージを特徴付けるパラメトリック補助情報（「空間キュー」）により代表される。付加情報を最小限にして、ダウンミックス信号の符号化に利用可能な伝送容量をできるだけ確保するために、補助情報のレートをできるだけ低く保つことが望ましい。
【００１２】
補助情報のビットレートを低く保つ１つの方法は、たとえば補助情報にエントロピー符号化アルゴリズム等を適用することにより、空間オーディオ構成の補助情報を無損失で符号化する方法である。
【００１３】
無損失符号化は、量子化スペクトル係数および他の補助情報の表現を確実に最適にコンパクトにできるよう、一般のオーディオ符号化では、広範に適用されてきた。適切な符号化構成および方法の例がＩＳＯ／ＩＥＣ標準ＭＰＥＧ１、パート３、ＭＰＥＧ２、パート７およびＭＰＥＧ４、パート３の範囲に示される。
【００１４】
これらの標準およびたとえばＩＥＥＥ論文「ＭＰＥＧ２高度オーディオ符号化における量子化スペクトル係数のノイズレス符号化」、エス・アール・クァッケンブッシュ、ジェイ・ディー・ジョンストン、ＩＥＥＥ  ＷＡＳＰＡＡ、モホンク、ニューヨーク州、１９９７年１０月（IEEE paper "Noiseless Coding of Quantized Spectral Coefficients in MPEG-2 Advanced Audio Coding", S. R. Quackenbush, J. D. Johnston, IEEE WASPAA, Mohonk,  NY, October 1997）は、量子化パラメータを無損失で符号化する以下の手段を含む前提技術を記載する。
【００１５】
・量子化スペクトル係数の多次元ハフマン符号化。
【００１６】
・係数のセットについて、共通の（多次元）ハフマン・コードブックを用いる方法。
【００１７】
・ホールまたは符号化サイン情報としての値と大きさの情報とを別に符号化する（すなわち必要なコードブックの大きさを減じる所与の絶対値についてのみハフマン・コードブックのエントリーを有する、すなわち「有符号」対「無符号」コードブック）方法。
【００１８】
・異なる最大絶対値（ＬＡＶ）、すなわち符号化するパラメータの範囲の様々な最大絶対値からなる別のコードブックを使用する方法。
【００１９】
・各ＬＡＶについて異なる統計的分布の別のコードブックを使用する方法。
【００２０】
ハフマン・コードブックの選択をを補助情報としてデコーダへ送信する方法。
【００２１】
・各選択されたハフマン・コードブックの適用範囲を規定する「セクション」を使用する方法。
【００２２】
・周波数にわたるスケールファクタの差分符号化を行い、その結果を引き続きハフマン符号化する方法。
【００２３】
粗く量子化した値を単一のＰＣＭ符号に符号化するための無損失符号化のもうひとつの技術が、ＭＰＥＧ１オーディオ標準（標準内でのグルーピングと呼ばれ、層２に使用）の範囲で提案されている。これについては、標準ＩＳＯ／ＩＥＣ  １１１７２−３：９３に詳しい。
【００２４】
刊行物「バイノーラル・キュー符号化−パートＩＩ：構成と応用」、シー・ファーラーおよびエフ・バウムガルト、音声とオーディオ処理に関するＩＥＥＥ会議、第１１巻、第６号、２００３年１１月により、ＢＣＣパラメータの符号化に関する情報が得られる。量子化されたＩＣＬＤパラメータを以下のように差分符号化することが提案されている。すなわち、
・周波数にわたって差分符号化し、かつその結果をその後、ハフマン符号化（一次元ハフマン符号で）する。
【００２５】
・時間にわたって差分符号化し、その結果をその後、ハフマン符号化（一次元ハフマン符号で）する。
【００２６】
そして、最終的に元のオーディオ信号の表現としてより効率的な変形を選択することが提案されている。
【００２７】
上記のとおり、差分符号化を周波数にわたってかつまたは時間にわたって適用することにより圧縮性能を最適化し、より効率的な変形を選択することが提案されている。そして、選択された変形をなんらかの補助情報を経由してデコーダへ信号で送る。
【００２８】
上記の先行技術は、たとえばオーディオまたはビデオストリームで送信する必要があるデータ量を減らすために有用である。上記のエントロピー符号化構成に基づく無損失符号化技術を用いることで、一般に非定値のビットレートのビットストリームが生じる。
【００２９】
ＡＡＣ（Ａｄｖａｎｃｅｄ  Ａｕｄｉｏ  Ｃｏｄｅｃ）標準では、符号化される情報値の確率分布が、符号化される値の符号ではなく、大きさにのみ依存すると仮定して、「無符号」のコードブックを使用することによる符号語と基礎コードブック両方の大きさの低減が提案されている。そして、符号ビットを別に送信して、ポストフィックス符号と考えることができ、符号化された大きさ情報を実際の値（符号×大きさ）にマッピングする。たとえば、四次元ハフマン・コードブックを仮定すると、この場合、コードブックの大きさを、２^４＝１６分の１に節約できる（全ての値が符号を伴うと仮定して）。
【００３０】
これまで、エントロピー符号化により符号の大きさを低減するために、かなりの努力が払われてきた。にもかかわらず、先行技術の方法では、いまだにいくつかの主要な欠点が克服されていない。たとえば、多次元ハフマン・コードブックを用いる場合、なんらかの符号化情報を送信するのに必要なビットレートを低減することができる。そのかわり、次元が増えるごとに、ハフマン・コードブックの大きさは、２倍に増えるため、使用すべきハフマン・コードブックの大きさが増大してしまう。これは、いくつかのコンピュータ圧縮プログラム等の場合のように、ハフマン・コードブックを符号化情報とともに送信する応用の場合には、非常に不都合である。ハフマン・コードブックをデータとともに送信する必要がない場合でも、エンコーダおよびデコーダには記憶する必要があり、限られた量でしか使用可能ではないスペース、特に、携帯での応用における映像やオーディオストリーミングまたは再生用の高価な記憶スペースを必要とすることになる。
【発明の開示】
【発明が解決しようとする課題】
【００３１】
本発明の目的は、より効率的な符号を生成かつ使用して情報値を圧縮し、かつ基礎コードブックの大きさを低減するための概念を提供することである。
【課題を解決するための手段】
【００３２】
本発明の第１の局面によれば、この目的は、情報値を符号化するためのエンコーダにより達成され、このエンコーダは、２以上の情報値をタプル順にタプルにグループ化するグループ化器と、符号化ルールを用いて、タプル順を示す順序情報およびタプルのための符号語を生成するための符号情報生成器を備え、符号化ルールでは、同じ符号語が、異なる順序で同じ情報値を有するタプルに割り当てられるようにされ、さらに、符号語と、それに関連して順序情報とを出力するための出力インタフェースとを備える。
【００３３】
本発明の第２の局面によれば、この目的は、情報値に基づく符合語を復号化するためのデコーダにより達成され、このデコーダは、符合語と、それに関連してタプル順を示す順序情報とを与えるための入力インタフェースを備え、このタプル順とは、情報値のタプル内の２以上の情報値の順序であり、さらに、符合語を創出するために用いた符号化ルールに基づく復号化ルールを用いて、タプルを生成するための符号プロセッサとを備え、復号化ルールでは、異なるタプルが同じ符合語から生成され、これらの異なるタプルが、異なる順序情報により示される異なるタプル順で同じ情報値を有し、さらに、タプルを２以上の情報値に非グループ化するための非グループ化器とを備える。
【００３４】
この発明の第３の局面によれば、この目的は、情報値を符号化する方法により達成され、この方法は、２以上の情報値をタプル順でタプルにグループ化するステップと、タプル順を示す順序情報を生成するステップと、符号化ルールを用いてタプルのための符合語を生成するステップを備え、符号化ルールでは、異なる順序で同じ情報値を有するタプルに同じ符合語が割り当てられ、さらに、
符号語と、それに関連して順序情報とを出力するステップを備える。
【００３５】
この発明の第４の局面によれば、この目的は、コンピュータ上で作動させて、上記の方法を実現するコンピュータプログラムにより達成される。
【００３６】
この発明の第５の局面によれば、この目的は、情報値に基づく符号語を復号化する方法により達成され、この方法は、符合語と、それに関連してタプル順を示す順序情報とを与えるステップを備え、このタプル順とは、情報値のタプル内の２以上の情報値の順序であり、さらに、符合語を創出するために用いた符号化ルールに基づく復号化ルールを用いてタプルを生成するステップを備え、復号化ルールでは、異なるタプルが同じ符合語から生成され、これら異なるタプルは、異なる順序情報により示される異なるタプル順で同じ情報値を有し、さらに、タプルを２以上の情報値に非グループ化するステップとを備える。
【００３７】
この発明の第６の局面によれば、この目的は、コンピュータ上で作動させて、上記の方法を実現するコンピュータプログラムにより達成される。
【００３８】
この発明の第７の局面によれば、この目的は、情報値に基づく符号化データにより達成され、この符号化データは、タプル順にタプルにおいて配列される２以上の情報値からなるタプルのための符号語と、タプル順を示す順序情報とを備える。
【００３９】
本発明は、２以上の情報値をタプル順でタプルにグループ化し、異なる順序で同じ情報値を有するタプルに同じ符号語を割り当て、かつタプル順を示す順序情報を生成し符号語に関連付ければ、情報値を符号化するための効率的な符号が生成できるとする知見に基づく。
【００４０】
ハフマン符号を用いたエントロピー符号化については、上記の発明の概念をより効率的に実現することができる。ハフマン・コードブックの大きさは、符号化される可能な値の数およびともに符号化される値の数（ハフマン・コードブックの次元）に依存する。特定の応用において、ハフマン・コードブックを表現するのに必要な記憶空間を減じるためには、１つのハフマン符号語が、等しい確率でともに符号化される値のグループの組全体を表すように、符号化されるデータの確率分布における対称性を利用することが効果的である。ともに符号化される値の実際のグループは、そのときの特定のポストフィックス符号として特定される。
【００４１】
タプルにおける２つ以上の値の順序は、値がある程度相関していなければ、値により表される内容には依存しないので、同じ値の異なる順序に対して等しい確率を仮定することができる（値が相関していないため）。可変長符号、すなわち、様々な長さの符号語を有する符号については、特にかつ好ましくは、同じ値の異なる順序のタプルが、１つの符号語に割り当てられる場合、これらの等しい確率により、より小さなコードブックが得られかつ効率的な符号が得られる。
【００４２】
したがって、本発明の好ましい実施例においては、二次元ハフマンエンコーダによって符号化される情報値は、まず差分符号化され、後で詳述するある種の対称性を有する差分表現が得られる。その後、いくつかの対称操作を差分表現に適用し、符号化する可能なタプルの数を減じ、それにより必要なコードブックの大きさを減じる。
【００４３】
所与の確率分布で生じる値の分布を差分符号化することで、対称な確率分布を有する、ゼロを中心とする異なる値、すなわち絶対値が同じでも符号が異なる値の分布が同じ確率で生じることになる。
【００４４】
たとえばハフマン符号化のようなエントロピー符号化の基本原則では、使用するコードブックが、実質上、発生頻度が最も高い情報値に対して、最短の符号語を割り当てるとう観点から可能な所与の情報値の確率分布を表す。多次元ハフマン符号化も同じ原則に従うが、２以上の情報値をタプルに組み合わせており、タプル全体が１つの符号語に関連付けられる。
【００４５】
したがって、差分符号化と二次元ハフマン符号化とを組み合わせることにより、２つのタイプの対称性が得られ、これらを利用することができる。
【００４６】
第１の対称性は、タプル（ａ、ｂ）の発生確率が、タプル（−ａ、−ｂ）と概ね同じとする観察から生じる。これは、座標系の原点に対する点対称に相当し、タプルの第１の値が、Ｘ軸を規定し、かつタプルの第２の値がＹ軸を規定する。
【００４７】
第２の対称性は、タプルにおいて２つの値が生じる順序を変更しても、そのタプルの発生の確率が変化しない、すなわち（ａ、ｂ）および（ｂ、ａ）の確率が等しいとする仮定に基づく。これは、座標が上記のとおり規定される場合、座標系の二等分線、第１象限と第３象限に対する軸対称に相当する。
【００４８】
この２つの対称性については、ハフマン・コードブックの大きさが、４分の１縮小される、すなわち、対称のタプルには同じ符号語を割り当てるように、利用することができる。対称情報、すなわち、元のタプルの順序と元のタプルの符号が、順序情報および符号情報により示され、かつ符号語とともに送信され、符号および順序情報を含む元のタプルの復号化および再構成が可能となる。
【００４９】
二次元の座標系におけるタプルの、上に述べる表現を振り返ると、対称性はいずれもともに、直角座標に対して４５°回転させた基本軸を備える楕円に似た、同じレベルの曲線（等しい確率の曲線）を備える二次元確率分布と理解することができる。
【００５０】
この２つの対称性を利用すれば、ハフマン符号が網羅する必要があるのは、座標系における可能なエントリーのおよそ４分の１（１象限）にすぎない。２ビットのポストフィックス符号が、４つの象限のうち１つにおける値の各対と、残りの３つの象限における対応の値の対との間の独自のマッピングを決定する。なお、いずれかの象限の境界線上に位置する値の対については、ポストフィックス符号は、１ビットのみからなり、両方の境界線上、すなわち分布の中心に位置する値の対の場合には、省略してもかまわない。
【００５１】
発明の概念によれば、上記の対称性を示さないデータの分、ハフマン・コードブックの大きさが低減されることになる。このようなデータが符号化されれば、異なる確率で発生する値が同じ符号語で表現されるので、ハフマン・コードブックの大きさは小さくなる一方、符号化された表現がかならずしも理想的に圧縮されないかもしれず、ハフマン・コードブックを最適な態様でデータに適合させるべく調節することができないので、ビットレートの無駄が生じる。
【００５２】
したがって、差分符号化すれば、自動的に効果的な対称性が得られるので、対称性処理を適用する前に、データを差分符号化することが好ましい。こうして、情報値を差分符号化することにより、可能な情報値の数が倍増するという欠点を、対称性を利用して均衡させることができるので、情報値の基礎セットごとにコンパクトな表現と小さいハフマン・コードブックを確保する、本発明の概念を利用することができる。
【００５３】
次に、本発明の好ましい実施例について、添付の図面を参照して説明する。
【発明を実施するための最良の形態】
【００５４】
［好ましい実施例の詳細な説明］
図１は、発明のエンコーダ１００を示し、このエンコーダ１００は、グループ化器１０２および出力インタフェースを含む符号情報生成器１０４を含む。
【００５５】
情報値１０６は、グループ化器により、情報値１０８ａ〜１０８ｃからなるタプルにグループ化される。図１に示す例では、発明の概念を、それぞれ２つの情報値からなるタプルを構築することにより、すなわち二次元ハフマン符号を使用することにより説明する。
【００５６】
タプル１０８ａ〜１０８ｃは、符号情報生成器１０４へ転送され、符号情報生成器は、異なる順序で同じ情報値を有するタプルに対して、同じ符号語を割り当てる符号化ルールを実行する。したがって、タプル１０８ａおよび１０８ｃは、同じ符号語１１０ａおよび１１０ｂに符号化される一方、タプル１０８ｂは、異なる符号語１１２に符号化される。発明の概念によれば、異なる順序情報１１４ａおよび１１４ｂを生成して、情報値がタプル１０８ａ〜１０８ｃ内部でグループ化される順序の情報を保存する。したがって、順序情報と符号語との組み合わせを、元のタプル１０８ａ〜１０８ｃを再構成するために使用することができる。順序情報は、出力インタフェースにより符号語に関連して配信される。一般には、異なる順序構成は、異なる順序情報ビットを生じるとされる。図１の例では、タプル１０８ａおよび１０８ｂのように、タプル内の値が昇順の場合、再順序づけられない。さらに、再順序づけていないタプルに、０の順序情報を割り当てるということにすれば、図１における符号語に割り当てられたような順序情報値が得られる。
【００５７】
図２は、本発明の好ましい実施例を示し、符号情報生成器１０４は、順序エンコーダ１２０およびエントロピーエンコーダ１２２を備え、かつエンコーダ１００は、出力インタフェース１２４をさらに備える。
【００５８】
順序エンコーダ１２０は、（タプル順を示す）タプルの順序情報１１４ａ〜１１４ｃを生成しかつこれら順序情報を出力インタフェース１２４へ転送する。同時に、順序エンコーダ１２０は、タプル１０８ａ〜１０８ｃ内の情報値を再順序づけ、予め規定されたタプル順によりタプルの順序を変え、タプル１２６ａ〜１２６ｃを生成する。予め規定されたタプル順とは、同じ情報値を有するタプルのグループについて情報値の符号化順を規定するものである。
【００５９】
この再順序づけは、たとえば２を超える数の情報値を有するタプルについても、タプル内で２つの情報値の位置を交換する複数の後続のステップにより実行することもできる。各ステップの後、所与のタプル順について順序エンコーダのコードブックにおいてエントリーが存在するかどうか確認する。存在する場合、再順序づけを止めて、符号語を生成することができる。存在しない場合には、上記の過程を、符号語が発見されるまで繰り返す。そして、順序情報は、たとえば符号語を生成するのに必要な交換の回数から生成することができる。同様に、正しいタプル順を、デコーダ側の順序情報を用いて再構成することもできる。
【００６０】
エントロピー符号化器は、タプル１２６ａ〜１２６ｃを符号化して、符号語１１０ａ、１１０ｂおよび１１２を生成し、これらの符号語を出力インタフェース１２４へ転送する。
【００６１】
出力インタフェースは、最終的に符号語１１０ａ、１１０ｂおよび１１２ならびにこれらに関連して順序情報１１４ａ〜１１４ｃを出力する。
【００６２】
図３は、本発明の他の好ましい実施例を示し、符号情報生成器は、タプル内の情報値の符号組み合わせを示す符号情報を生成するための符号エンコーダ１３０をさらに備える。
【００６３】
図３に示す発明のエンコーダは、第２の対称性も利用し、同じ符号語を、同じ絶対値でその絶対値に関して同じ順序の情報値を有するタプルに割り当てる。したがって、符号エンコーダ１３０は、タプル１３４a〜１３４ｃの各々について、タプル内の値の符号を示す符号情報１３２ａ〜１３２ｃを生成する。符号エンコーダ１３０は、同時にタプル内の情報値の符号を変更して、タプル内の絶対値の各順序に関して、すなわち情報値の符号についてのみ異なるタプルについて符号化符号組み合わせを規定する予め規定された符号組み合わせを生成する。
【００６４】
符号情報１３２ａ〜１３２ｃは、順序エンコーダ１２０から順序情報およびエントロピーエンコーダ１２２から符号語も受信する出力インタフェース１２４へ追加的に転送される。そして、出力インタフェース１２４は、符号語ならびに関連する順序情報および符号情報を供給する。
【００６５】
図４ａは、符号情報が符号エンコーダ１３０から生成できる態様と、符号に関する対称性を利用して必要なハフマン・コードブックの大きさを低減することができる態様とを示す図である。
【００６６】
行列で図示する、タプルの可能な値（ａ、ｂ）を示し、ａの値は、ｘ軸上に示し、かつｂの可能な値は、Ｙ軸上に示す。ａおよびｂの値は、（たとえば事前の差分符号化により）ゼロを中心に対称であり、かつ各々−４〜４の範囲にある。
【００６７】
行列は、パラメータ値ａおよびｂの８１全ての可能な組み合わせを示す。また、行列のエントリーを示す第１軸１５０が示され、ａおよびｂの和（ａ+ｂ）＝０となっている。この図は、第２軸１５２も示し、ａおよびｂの差（ａ-ｂ）＝０である。この２つの軸１５０および１５２が、行列を１から４の番号で示す４象限に分割していることがわかる。
【００６８】
（ａ、ｂ）の組み合わせおよび（-ａ、-ｂ）の組み合わせの確率が等しいと仮定すると、第１の対称性は、原点に対する点対称に等しく、これは、行列の２つの任意のエントリー１５４ａおよび１５４ｂについて明示される。
【００６９】
発明のエンコーダは、第３象限のエントリーを第１象限のエントリーに鏡映し、第４象限のエントリーを第２象限のエントリーに鏡映する対称操作を行うことで、必要なハフマン・コードブックの大きさをおよそ２分の１減らすことができる。このように、符号エンコーダ１３０が符号情報によりタプルがどの象限からのものかを付加的に示せば、第３および第４象限のコードブックエントリを省くことができる。
【００７０】
図４ｂは、順序コーダ１２０が第２の対称を利用して、ハフマン・コードブックの大きさをさらに２分の１にする態様を示す。タプル（ａ、ｂ）および（ｂ、ａ）の確率が等しいことを意味する第２の対称は、残りの行列のエントリーを軸１５２で鏡映することに等しい。たとえば、これは、２つの行列エントリー１５６ａおよび１５６ｂについて示され、タプル（０、２）をタプル（２、０）に鏡映する様子を示す。したがって、第２および第１象限の対応するエントリーに同じ符号語を割り当てることにより、コードブックの大きさをさらに２分の１省くことができる。順序コーダ１２０は、元のタプルが第１または第２象限のいずれから来たにせよ、情報を保存するための順序情報を生成する。
【００７１】
図４ａおよび図４ｂに示すとおり、符号エンコーダおよび順序エンコーダを組み込む発明のエンコーダにより、ハフマン符号でカバーする必要があるのは、４つの象限のうち１つだけということになる。２ビットのポストフィックス符号が、これら４つの象限のうちの１つにおける値の全ての対と残りの３つの象限における対応する値の対との間の独自のマッピングを決定する。なお、いずれかの象限の境界線に位置する値の対については、ポストフィックス符号を１ビットのみで構成するかまたは、値の対が、両方の境界線上、すなわち行列の中心に位置する場合には、省略してもかまわない。
【００７２】
図４ａおよび図４ｂに示す対称操作に続き、象限表現に対してアルゴリズムを作動させることは、より都合がよいので、実用的な理由で残りの象限の値の対を再順序づけ（マッピング）して二次行列にするのは、好都合である。
【００７３】
本発明の一実施例により組み込まれるマッピング法について、図５に示す。二次行列１６０にマッピングされる第１象限を有する元の行列は、左に示す。また、二次行列１６０は、Ｘ軸上にパラメータａのパラメータ値と、Ｙ軸上にパラメータｂのパラメータ値を有する。マッピングアルゴリズムに従うこの再順序づけを図面に示し、行列要素の各々が独自の数字で記される。なお、情報値を合計すると偶数になるタプル（ａ+ｂは偶数で、これは第１象限のハッチングをしていない行列要素全てについて真である）は、二次行列１６０の左下側に再順序づけられ、情報値の合計が奇数であるタプル（ハッチングされた要素）は、図５においてハッチングされ、行列１６０の右上側に再順序づけられる。
【００７４】
上記のマッピングプロセスの後、ハフマン符号化されるタプルを二次表現とし、扱いやすくする。
【００７５】
図６は、情報値に基づく符号語を復号化するための発明のデコーダのブロック図である。
【００７６】
デコーダ２００は、入力インタフェース２０２と、符号プロセッサ２０４と、非グループ化器２０６とを備える。入力インタフェース２０２は、符号語２１０ａ、２１０ｂおよび２１２ならびに関連の順序情報２１４ａ、２１４ｂおよび２１６を与え、これらはいずれも符号プロセッサ２０４へ送られる。
【００７７】
符号プロセッサは、復号化ルールを用いて、情報値からなるタプル２１８ａ、２１８ｂおよび２１８ｃを生成し、この復号化ルールでは、異なるタプルを同じ符号語から生成し、これら異なるタプルは、異なる順序情報により示される異なるタプル順の同じ情報値を有する。
【００７８】
したがって、異なるタプル２１８ａおよび２１８ｃは、関連する異なる順序情報２１４ａおよび２１４ｂを有するので、同じ符号語２１０ａおよび２１０ｂから生成される。そして、情報値のタプル２１８ａ〜２１８ｃは、非グループ化器２０６により非グループ化され、情報値２２０を生成する。
【００７９】
図７は、好ましい発明のデコーダを示し、符号プロセッサ２０４は、エントロピーデコーダ２２２と順序デコーダ２２４とを備える。
【００８０】
エントロピーデコーダ２２２は、ハフマン・コードブックを用いて、符号語２１０ａ、２１０ｂおよび２１２の各々を１つのタプル２２６ａ〜２２６ｃへ割り当てる。タプル２２６ａ〜２２６ｃは、関連の順序情報も受信する順序デコーダ２２４へ転送される。順序デコーダ２２４は、タプル２２６ａ〜２２６ｃを順序情報に示されるとおり修正して情報値を生成する。そして、生成された最終タプル２２８ａ〜２２８ｃは、非グループ化器２０６へ転送され、非グループ化器がタプル２２８ａ〜２２８ｃを非グループ化して情報値２２０を生成する。
【００８１】
図８は、発明のデコーダ２００の他の好ましい実施例を示し、符号プロセッサ２０４は、符号デコーダ２３０をさらに備える。
【００８２】
入力インタフェースは、３つの同じ符号語２３２ａ〜２３２ｃ、符号情報ビット２３４ａ〜２３４ｃおよび順序情報ビット２３６ａ〜２３６ｃを与える。
【００８３】
エントロピーデコーダ２２２は、３つの同じ符号語２３２ａ〜２３２ｃを３つの同じタプル２３８ａ〜２３８ｃへ復号化し、そして、それらは符号デコーダ２３０へ転送される。
【００８４】
符号デコーダ２３０は、追加的に符号情報２３４ａ〜２３４ｃを受信し、かつ符号情報２３４ａ〜２３４ｃによって示されるようにタプル２３８ａ〜２３８ｃを修正して、タプル２４０ａ〜２４０ｃを生成し、これで、それらは、正しい符号を伴う情報値を有する。
【００８５】
タプル２４０ａ〜２４０ｃは、順序デコーダ２２４へ転送され、同デコーダは、追加的に順序情報２３６ａ〜２３６ｃを受信し、タプル２０４ａ〜２４０ｃ内の情報値の順序を変更して正しい順序のタプル２４２ａ〜２４２ｃを受信する。そして、タプル２４２ａ〜２４２ｃは、非グループ化器２０６へ転送され、非グループ化器はタプル２４２ａ〜２４２ｃを非グループ化することにより情報値２２０を生成する。
【００８６】
図２および図３に示す発明のエンコーダの好ましい実施例は、順序エンコーダ１２０および符号エンコーダ１３０が順序または符号情報を回収すると同時にタプルを変更することを提案するが、別の態様では、符号エンコーダおよび順序エンコーダが、タプルを変更せずに順序および符号情報を回収することも可能である。ハフマン・コードブックは、そのような場合、異なる符合と順序情報を伴うタプルに、同じ符号語を割り当てるよう設計する必要がある。
【００８７】
図に示す好ましい実施例は、二次元ハフマン・コードブックを使用することにより発明の概念を詳しく示すが、グループ化された値およびその対称性を利用するという発明の思想を、他の無損失符号化法、特により高次元すなわち２を超える数の情報値を有するタプルを構築するハフマン・コードブックと組み合わせることも可能である。
【００８８】
図４ａおよび図４ｂは、より小さいハフマン・コードブックを可能にするために使用される対称情報を生成する方法を示す。第１のステップでは、所与の行列の第３および第４象限が、第１および第２象限にマッピングされる。別の態様では、マッピングを元にもどせるように、対称性の情報が保存されている限り、２つの隣接する象限の他の組み合わせを残りの２つの象限にマッピングすることも可能である。図４ｂに示す第２の対称操作についても同じことが当てはまる。
【００８９】
図５は、大きさが減じられたコードブックの記述の利用を可能にする二次行列に行列の１象限をマッピングする方法を示す。このマッピング法は、複数の可能なマッピング構成の一例であり、マッピングは、独自かつ可逆であればよい。
【００９０】
発明の方法の実現の要件により、発明の方法をハードウェアまたはソフトウェアで実現することができる。このような例は、デジタル記憶媒体、特に、プログラマブルコンピュータシステムと協働して、発明の方法が実行されるようにする、電子的に読み取り可能な制御信号を記憶したＤＶＤやＣＤなどのディスクを用いて実行が可能である。したがって、本発明は一般には、機械可読担体に記憶されたプログラムコードを備えるコンピュータプログラム製品であって、このプログラムコードは、このコンピュータプログラム製品をコンピュータ上で作動させて、発明の方法を実行するために作用する。したがって、言い換えれば、発明の方法は、コンピュータプログラムをコンピュータ上で作動させて、本発明の方法の少なくとも１つを実行するためのプログラムコードを有するコンピュータプログラムである。
【００９１】
上記の発明は、特定の実施例について詳細に図示説明したが、当業者は、形式および細部において、本発明の趣旨を逸脱することなく、様々な変更が可能であることを理解するであろう。ここに開示されかつ添付の請求項により解釈される広義の概念から逸脱することなく、様々な実施例に適合させる上で、様々な変更が可能であることを理解されたい。
【図面の簡単な説明】
【００９２】
【図１】図１は、発明のエンコーダのブロック図である。
【図２】発明のエンコーダの好ましい実施例を示す図である。
【図３】発明のエンコーダの別の好ましい実施例を示す図である。
【図４ａ】符号化されるデータに対する第１の対称操作を示す図である。
【図４ｂ】符号化されるデータに対する第２の対称操作を示す図である。
【図５】データの対称表現の生成を示す図である。
【図６】発明のデコーダのブロック図である。
【図７】発明のデコーダの好ましい実施例を示す図である。
【図８】発明のデコーダの別の好ましい実施例を示す図である。
【図９】先行技術のマルチチャネルエンコーダを示す図である。
【図１】
2008536410.tif 000003
【図２】
2008536410.tif 000004
【図３】
2008536410.tif 000005
【図４ａ】
2008536410.tif 000006
【図４ｂ】
2008536410.tif 000007
【図５】
2008536410.tif 000008
【図６】
2008536410.tif 000009
【図７】
2008536410.tif 000010
【図８】
2008536410.tif 000011
【図９】
2008536410.tif 000012
【手続補正書】
【提出日】平成19年2月13日(2007.2.13)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
情報値を符号化するためのエンコーダであって、
入力値を差分符号化して、情報値として入力値の差分符号化表現を得るための差分エンコーダと、
２以上の情報値をタプル順にタプルにグループ化するグループ化器と、
符号化ルールを用いて、タプル順を示す順序情報およびタプルのための符号語を生成するための符号情報生成器を備え、符号化ルールでは、同じ符号語が、異なる順序で同じ情報値を有する異なるタプルに割り当てられ、
符号化ルールでは、さらに、同じ順序で絶対値が同じで、タプル内の各情報値の符号が異なる情報値を有する異なるタプルに同じ符号語が割り当てられるようにされ、さらに、
タプル内の情報値の符号組合せを示す符号情報を生成する符号エンコーダと、
符号語と、それに関連して順序情報と符号情報とを出力するための出力インタフェースとを備える、エンコーダ。
【請求項２】
符号情報生成器は、
順序情報を生成するための順序エンコーダと、
異なる順序で同じ情報値を有するタプルを同じ符号語に割り当てるコードブックを用いて符合語を生成するためのエントロピーエンコーダとを含む、請求項１に記載のエンコーダ。
【請求項３】
順序エンコーダが、タプル内の情報値を再順序づけするべく動作して、タプル順をそのタプルに予め規定されたタプル順に変更し、その予め規定されたタプル順が、同じ情報値を有するタプルのグループのための情報値の符号化順を規定し、かつ順序エンコーダが、タプル順の偏りおよび符号化順を検出して符号化するべく動作し、かつ
エントロピーエンコーダが、符号化順に順序づけされた情報値を有するタプルに対して符合語を割り当てる、減少されたコードブックを有する、請求項２に記載のエンコーダ。
【請求項４】
順序エンコーダが、第１の情報値を第２の情報値と交換することにより、タプル内の情報値を再順序づけするべく動作する、請求項３に記載のエンコーダ。
【請求項５】
符号エンコーダは、タプル内の情報値の符号を変更するべく動作して、符号の組み合わせを予め規定された符号組み合わせに変更し、この予め規定された符号組み合わせは、情報値の個々の符号においてのみ異なるタプル内の情報値の順序について符号化符号組み合わせを規定し、かつ、
符号情報生成器は、エントロピーエンコーダを有し、エントロピーエンコーダが、同じ符合語を情報値の絶対値の同じ順序を有する各タプルに割り当てる、減じられたコードブックを有する、請求項４に記載のエンコーダ。
【請求項６】
符号エンコーダが、タプル内の第１および第２の情報値の符号を変更するべく動作する、請求項５に記載のエンコーダ。
【請求項７】
差分符号化表現が、時間または周波数において差分符号化された入力値の表現である、請求項１に記載のエンコーダ。
【請求項８】
情報値が、ビデオ信号またはオーディオ信号のフレームを記述する情報値を含む、請求項１に記載のエンコーダ。
【請求項９】
情報値が、第１および第２のオーディオチャネル間の空間的相関を記述するＢＣＣパラメータを含み、かつＢＣＣパラメータが、以下のＢＣＣパラメータのリスト、すなわちチャネル間相関（ＩＣＣ）、チャネル間レベル差（ＩＣＬＤ）、チャネル間時間差（ＩＣＴＤ）、およびチャネル間位相差（ＩＰＤ）から選択される、請求項１に記載のエンコーダ。
【請求項１０】
符号化ルールでは、情報値の符号化により、異なる長さの符合語のシーケンスが生じるようにされている、請求項１のエンコーダ。
【請求項１１】
情報値に基づく符合語を復号化するためのデコーダであって、
符合語と、これに関連してタプル順を示す順序情報とを与え、さらに関連して、タプル内の情報値のための符号組合せを示す符号情報を与えるための入力インタフェースを備え、タプル順とは情報値のタプル内の２以上の情報値の順序であって、さらに、
符合語を創出するために用いた符号化ルールに基づく復号化ルールを用いて、タプルを生成するための符号プロセッサを備え、
復号化ルールでは、異なる順序で同じ情報値を有する異なるタプルが、異なる順序情報により関連付けられた同じ符合語から生成され、かつ同じ順序で同じ絶対値で、タプル内の各情報値の符号が異なる情報値を有する異なるタプルが、異なる符合情報により関連付けられる同じ符号語から生成され、さらに、
情報値の差分復号化を行って、情報値の差分復号化表現を得るための差分デコーダとを含む、デコーダ。
【請求項１２】
符号プロセッサが、
各符号語を予備タプルに割り当てるコードブックを用いて、予備タプルを生成するためのエントロピーデコーダと、
順序情報により示されるように予備タプル内の情報値を再順序づけすることによりタプルを生成するための順序デコーダとを備える、請求項１１に記載のデコーダ。
【請求項１３】
順序デコーダが、第１の情報値を第２の情報値と交換することにより、予備タプルの情報値を再順序づけするよう動作する、請求項１２に記載のデコーダ。
【請求項１４】
符号プロセッサが、符号情報により示されるように予備タプル内の情報値の符号を変更することにより、予備タプルからタプルを生成するための符号デコーダをさらに含む、請求項１３に記載のデコーダ。
【請求項１５】
符号デコーダが、予備タプル内の各情報値の符号を変更するよう動作する、請求項１４に記載のデコーダ。
【請求項１６】
符号デコーダが、予備タプル内の第１および第２の情報値の符号を変更するべく動作する、請求項１４に記載のデコーダ。
【請求項１７】
情報値の差分復号化表現が、時間または周波数において差分復号化される、請求項１１に記載のデコーダ。
【請求項１８】
情報値が、ビデオ信号またはオーディオ信号のフレームを記述する情報値を含む、請求項１１に記載のデコーダ。
【請求項１９】
情報値が、第１および第２のオーディオチャネル間の空間的相関を記述するＢＣＣパラメータを含み、かつＢＣＣパラメータが、以下のＢＣＣパラメータのリスト、すなわちチャネル間相関（ＩＣＣ）、チャネル間レベル差（ＩＣＬＤ）、チャネル間時間差（ＩＣＴＤ）、およびチャネル間位相差（ＩＰＤ）から選択される、請求項１１に記載のデコーダ。
【請求項２０】
情報値を符号化する方法であって、この方法が、
入力値を差分符号化して、情報値として入力値の差分符号化表現を得るステップと、
２以上の情報値をタプル順でタプルにグループ化するステップと、
タプル順を示す順序情報を生成するステップと、
タプル内の情報値の符号を示す符号情報を生成するステップと、
符号化ルールを用いてタプルのための符合語を生成するステップを含み、
符号化ルールでは、同じ符合語が、異なる順序で同じ情報値を有する異なるタプルに割り当てられ、かつさらに符号化ルールでは、同じ符号語が、同じ順序で絶対値が同じで、タプル内の各情報値の符号が異なる情報値を有する異なるタプルに割り当てられるようにされ、さらに、
符号語と、それに関連して順序情報と符号情報とを出力するステップとを含む、方法。
【請求項２１】
情報値に基づく符合語を復号化するための方法であって、
符号語と、それに関連してタプル順を示す順序情報とを与え、さらに関連して、タプル内の情報値のための符号組合せを示す符号情報を与えるステップを含み、このタプル順とは、情報値からなるタプル内の２以上の情報値の順序であり、さらに、
符号語を創出するために使用した符号化ルールに基づく復号化ルールを使用してタプルを生成するステップを含み、復号化ルールでは、異なる順序で同じ情報値を有する異なるタプルが、異なる順序情報で関連付けられる同じ符号語から生成され、かつ同じ順序で同じ絶対値で、タプル内の各情報値の符合が異なる情報値を有する異なるタプルが、異なる符合情報により関連付けられる同じ符号語から生成され、さらに、
タプルを２以上の情報値に非グループ化するステップと、
情報値の差分復号化を行って、情報値の差分復号化表現を得るステップとを含む、方法。
【請求項２２】
コンピュータ上で作動させて、情報値を符号化するための方法を実行するためのプログラムコードを有するコンピュータプログラムであって、この方法が、
入力値を差分符号化して、情報値として入力値の差分符号化表現を得るステップと、
２以上の情報値をタプル順でタプルにグループ化するステップと、
タプル順を示す順序情報を生成するステップと、
タプル内の情報値の符号を表す符合情報を生成するステップと
符号化ルールを用いてタプルための符号語を生成するステップを含み、この符号化ルールでは、異なる順序で同じ情報値を有する異なるタプルに同じ符号語が割り当てられるようにされ、かつ符号化ルールではさらに、同じ順序で同じ絶対値で、タプル内の各情報値の符合が異なる異なる情報値に、同じ符号語が割り当てられるようにされ、さらに、
符号語と、それに関連して順序情報と、符号情報とを出力するステップとを備える、コンピュータプログラム。
【請求項２３】
コンピュータ上で作動させて、情報値に基づく符号語を復号化する方法を実行するためのプログラムコードを有するコンピュータプログラムであって、この方法が、
符合語と、それに関連してタプル順を示す順序情報とを与え、さらに関連して、タプル内の情報値のための符号組合せを示す符号情報を与えるステップを含み、このタプル順は情報値のタプル内の２以上の情報値の順序であり、さらに、
符合語を創出するために用いた符号化ルールに基づく復号化ルールを用いてタプルを生成するステップを含み、復号化ルールでは、異なる順序で同じ情報を有する異なるタプルが、異なる順序情報により関連付けられた同じ符合語から生成され、かつ、同じ順序で同じ絶対値で、タプル内の各情報値の符合が異なる情報値を有する異なるタプルが、異なる符合情報により関連付けられる同じ符号語から生成され、さらに、
タプルを２以上の情報値に非グループ化するステップと、
情報値の差分復号化を行って、情報値の差分復号化表現を得るステップとを備える、コンピュータプログラム。
【請求項２４】
情報値に基づく符号化データであって、タプル順にタプルにおいて配列される２以上の情報値からなるタプルのための符号語と、
タプル順を示す順序情報と、タプル内の情報値のための符号組合せを示す符号情報とを含む、符号化データ。
【請求項２５】
コンピュータ読み取り可能な媒体に記憶される、請求項２４に記載の符号化データ。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００３０
【補正方法】変更
【補正の内容】
【００３０】
これまで、エントロピー符号化により符号の大きさを低減するために、かなりの努力が払われてきた。にもかかわらず、先行技術の方法では、いまだにいくつかの主要な欠点が克服されていない。たとえば、多次元ハフマン・コードブックを用いる場合、なんらかの符号化情報を送信するのに必要なビットレートを低減することができる。そのかわり、次元が増えるごとに、ハフマン・コードブックの大きさは、２倍に増えるため、使用すべきハフマン・コードブックの大きさが増大してしまう。これは、いくつかのコンピュータ圧縮プログラム等の場合のように、ハフマン・コードブックを符号化情報とともに送信する応用の場合には、非常に不都合である。ハフマン・コードブックをデータとともに送信する必要がない場合でも、エンコーダおよびデコーダには記憶する必要があり、限られた量でしか使用可能ではないスペース、特に、携帯での応用における映像やオーディオストリーミングまたは再生用の高価な記憶スペースを必要とすることになる。
同様の問題に関連する刊行物がいくつか存在する。たとえば、米国特許第５５５０５４１号は、エンコーダ／デコーダシステムのためのコンパクトなソース符号化テーブルの生成に関連する。符号化の前にメッセージ内の記号を順序付け、さらに順序情報を結果として得られる符号語とともに送ることにより、従来のテーブルより小さい多次元ハフマン符号化テーブルを生成する。
パティチス・エム・エス他、「無損失符号化のための順列を用いた広帯域画像の表現について」、画像分析と解釈に関する第４回ＩＥＥＥサウスウエスト・シンポジウム、Ｓ.２３７−２４１(Pattichis M. S. et al: "On the representation of wideband images using permutations for lossless coding", PROCEEDINGS OF THE 4TH IEEE SOUTHWEST SYMPOSIUM ON IMAGE ANALYSIS AND INTERPRETATION, S. 237-241)は、順列を使用して広帯域画像符号化を表現するための新規な方法を提案する。差分符号化されたサンプルは、ランレングスが符号化される。
ヴァシラッシュ・エー他、「格子符号ベクトルのインデキシングとエントロピー符号化」、２００１年、音響、音声および信号処理に関するＩＥＥＥ国際会議講演集、第６の１巻、第２．６０５頁から２．６０８頁（VASILACHE A. et al: "Indexing and entropy coding of lattice code vectors", 2001, IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH, AND SIGNAL PROCESSING PROCEEDINGS, Vol. 1 of 6, pages 2.605-2.608）は、格子符号ベクトルのエントロピー符号化に関する。ハフマン符号化と固定長符号化を組み合わせた方法が提案される。符号ベクトルをクラスにグループ化し、個々のクラスのインデックス番号を、エントロピー符号化を用いて符合化する。さらに、個々のクラス内の符号ベクトルの位置を固定レートの数え上げ符号化を用いて符号化することも提案される。
クァッケンブッシュ他、「ＭＰＥＧ２高度オーディオ符号化における量子化スペクトル係数のノイズレス符号化」、オーディオおよび音響に対する信号処理の応用に関するＩＥＥＥ  ＡＡＳＳＰワークショップ(QUACKENBUSH et al: "Noiseless Coding of Quantized Spectral Components in MPEG-2 Advanced Audio Coding", IEEE ASSP WORKSHOP ON APPLICATIONS OF SIGNAL PROCESSING TO AUDIO AND ACOUSTICS）は、量子化スペクトル成分を符号化する上で使用するフレキシブルハフマン符号化アルゴリズムの適用に関する。Ｎ個のタプルを異なるハフマン・コードブックで符号化し、コードブックの記憶を節約するため、そのうちのいくつかは、絶対値しか有していない。この場合、各非ゼロ係数の符号ビットは符号語に添付される。
「Ｚｎ，Ａｎ，Ｄｎ，およびＤｍ＋＋格子ベクトル量子化器のためのインデキシング・アルゴリズム」、パトリック・ラウルおよびクリスティン・ギルモント("Indexing Algorithms for Zn, An, Dn, and Dm++ Lattice Vector Quantizers", Patrick Raul and Christine Guillement)は、オーディオ−ビジュアル信号圧縮において使用される格子の大きなクラスに有効なベクターインデキシングアルゴリズムに関連する。各クラスは、所謂「リーダーベクトル」の成分の可能な「無符号」順列として定義される。符号無リーダーベクトルを使用するには、クラスのメンバーの各ノンゼロ要素について、符号ビットを送信することが必要である。
本発明の第１の局面によれば、この目的は、情報値を符号化するためのエンコーダにより達成され、このエンコーダは、２以上の情報値をタプル順にタプルにグループ化するグループ化器と、符号化ルールを用いて、タプル順を示す順序情報およびタプルのための符号語を生成するための符号情報生成器を備え、符号化ルールでは、同じ符号語が、異なる順序で同じ情報値を有するタプルに割り当てられるようにされ、さらに、符号語と、それに関連して順序情報とを出力するための出力インタフェースとを備える。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００４８
【補正方法】変更
【補正の内容】
【００４８】
この２つの対称性については、ハフマン・コードブックの大きさが、およそ４分の１縮小される、すなわち、対称のタプルには同じ符号語を割り当てるように、利用することができる。対称情報、すなわち、元のタプルの順序と元のタプルの符号が、順序情報および符号情報により示され、かつ符号語とともに送信され、符号および順序情報を含む元のタプルの復号化および再構成が可能となる。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００５１
【補正方法】変更
【補正の内容】
【００５１】
発明の概念によれば、上記の対称性を示さないデータの分、ハフマン・コードブックの大きさも低減されることになる。このようなデータが符号化されれば、異なる確率で発生する値が同じ符号語で表現されるので、ハフマン・コードブックの大きさは小さくなる一方、符号化された表現がかならずしも理想的に圧縮されないかもしれず、ハフマン・コードブックを最適な態様でデータに適合させるべく調節することができないので、ビットレートの無駄が生じる。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００５２
【補正方法】変更
【補正の内容】
【００５２】
したがって、差分符号化すれば、自動的に効果的な対称性が得られるので、対称性処理を適用する前に、データを差分符号化することが好ましい。こうして、情報値を差分符号化することにより、可能な情報値の数が倍増するという欠点を、対称性を利用して均衡させることができるので、本発明の概念を利用して情報値の基礎セットごとにコンパクトな表現と小さいハフマン・コードブックを保証することができる。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００６６
【補正方法】変更
【補正の内容】
【００６６】
行列で図示する、タプルの可能な値（ａ、ｂ）を示し、ａの値は、ｘ軸上に示し、かつｂの値を、Ｙ軸上に示す。ａおよびｂの値は、（たとえば事前の差分符号化により）ゼロを中心に対称であり、かつ各々−４から４の範囲にある。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００６８
【補正方法】変更
【補正の内容】
【００６８】
（ａ、ｂ）の組み合わせおよび（-ａ、-ｂ）の組み合わせの確率が等しいと仮定すると、第１の対称性は、原点に対する点対称に等しく、これは、行列の２つの任意のエントリー１５４ａ（−２、−１）および１５４ｂ（２、１）について明示される。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００７０
【補正方法】変更
【補正の内容】
【００７０】
図４ｂは、順序コーダ１２０が第２の対称を利用して、さらにハフマン・コードブックの大きさを２分の１にする態様を示す。タプル（ａ、ｂ）および（ｂ、ａ）の確率が等しいことを意味する第２の対称は、残りの行列のエントリーを軸１５２で鏡映することに等しい。たとえば、これは、２つの行列エントリー１５６ａおよび１５６ｂについて示され、タプル（０、２）をタプル（２、０）に鏡映する様子を示す。したがって、同じ符号語を、第２および第１象限の対応するエントリーに割り当てることにより、コードブックの大きさをさらに２分の１省くことができる。順序コーダ１２０は、元のタプルが第１または第２象限のいずれから来たにせよ、情報を保存するための順序情報を生成する。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００８０
【補正方法】変更
【補正の内容】
【００８０】
エントロピーデコーダ２２２は、ハフマン・コードブックを用いて、符号語２１０ａ、２１０ｂおよび２１２をタプル２２６ａないし２２６ｃそれぞれに割り当てる。タプル２２６ａから２２６ｃは、関連の順序情報も受信する順序デコーダ２２４へ転送される。順序デコーダ２２４は、タプル２２６ａから２２６ｃを順序情報に示されるとおり修正して情報値を生成する。そして、生成された最終タプル２２８ａから２２８ｃは、非グループ化器２０６へ転送され、非グループ化器がタプル２２８ａから２２８ｃを非グループ化して情報値２２０を生成する。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００８９
【補正方法】変更
【補正の内容】
【００８９】
図５は、大きさが減じられたコードブックの記述を可能にする二次行列に行列の１象限をマッピングする方法を示す。このマッピング法は、複数の可能なマッピング構成の一例であり、マッピングは、独自かつ可逆であればよい。
【手続補正書】
【提出日】平成19年3月16日(2007.3.16)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００７３
【補正方法】変更
【補正の内容】
【００７３】
本発明の一実施例により組み込まれるマッピング法について、図５に示す。二次行列１６０にマッピングされる第１象限を有する元の行列は、左に示す。また、二次行列１６０は、Ｘ軸上にパラメータａのパラメータ値と、Ｙ軸上にパラメータｂのパラメータ値を有する。マッピングアルゴリズムに従うこの再順序づけを図面に示し、行列要素の各々が独自の数字で記される。なお、情報値を合計すると偶数になるタプル（ａ+ｂは偶数で、これは第１象限の薄く陰影をつけた行列要素全てについて真である）は、二次行列１６０の左下側に再順序づけられ、情報値の合計が奇数であるタプル（陰影をつけていない要素）は、図５において陰影をつけず、行列１６０の右上側に再順序づけられる。
【手続補正書】
【提出日】平成20年4月10日(2008.4.10)
【手続補正１】
【補正対象書類名】図面
【補正対象項目名】図２
【補正方法】変更
【補正の内容】
【図２】
2008536410.tif 000013
【手続補正２】
【補正対象書類名】図面
【補正対象項目名】図３
【補正方法】変更
【補正の内容】
【図３】
2008536410.tif 000014
【手続補正３】
【補正対象書類名】図面
【補正対象項目名】図５
【補正方法】変更
【補正の内容】
【図５】
2008536410.tif 000015
【手続補正４】
【補正対象書類名】図面
【補正対象項目名】図６
【補正方法】変更
【補正の内容】
【図６】
2008536410.tif 000016
【手続補正５】
【補正対象書類名】図面
【補正対象項目名】図７
【補正方法】変更
【補正の内容】
【図７】
2008536410.tif 000017
【手続補正６】
【補正対象書類名】図面
【補正対象項目名】図８
【補正方法】変更
【補正の内容】
【図８】
2008536410.tif 000018
【国際調査報告】
2008536410.tif 000019
2008536410.tif 000020
2008536410.tif 000021