(57)【特許請求の範囲】
【請求項１】
オーディオ周波数係数のシーケンスを符号化する方法であって、
符号化方式の異なる複数のエントロピー符号器を用いてエントロピー符号化を行うために、オーディオ周波数係数のシーケンスの周波数領域範囲を、第１の周波数範囲が主としてゼロ以外の値の周波数係数を含み、第２の周波数範囲が主としてゼロの値の周波数係数を含むように、少なくとも第１の周波数範囲と第２の周波数範囲とに分割するステップと、
前記複数の異なるエントロピー符号器から、前記オーディオ周波数係数のシーケンスの符号化に使用すべきエントロピー符号器を選択するステップであって、前記第１および第２の周波数範囲の各々の周波数係数の符号化にそれぞれ使用すべき第１および第２のエントロピー符号器を選択するステップと、
前記第１のエントロピー符号器を用いて、前記オーディオ周波数係数のシーケンスのうちの前記第１の周波数範囲の周波数係数を符号化するステップと、
前記第２のエントロピー符号器を用いて、前記第１のエントロピー符号器によるエントロピー符号化処理とは異なるランレングスエントロピー符号化処理によって、前記オーディオ周波数係数のシーケンスのうちの前記第２の周波数範囲の周波数係数を符号化するステップと
を含むことを特徴とする方法。
【請求項２】
前記分割するステップは、予め決定された分割境界を設定することを特徴とする請求項１に記載の方法。
【請求項３】
前記分割するステップは、前記オーディオ周波数係数のシーケンスに適応的な分割境界を設定し、
前記分割境界を示すフラグを、符号化したオーディオ周波数係数のシーケンスのデータストリーム内に埋め込むステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項４】
前記第１のエントロピー符号器は、可変長記号に可変長符号を割り当てる可変−可変エントロピー符号器を含むことを特徴とする請求項１乃至３のいずれかに記載の方法。
【請求項５】
前記第２のエントロピー符号器による前記ランレングスエントロピー符号化処理は、
（ａ）前記第２の周波数範囲内においてゼロの値の係数が連続するランレングスと、
（ｂ）前記第２の周波数範囲内において前記連続するゼロの値の係数に隣接したゼロ以外の値の係数のレベルと
の組み合わせを表す、エントロピー符号を使用することを含むことを特徴とする請求項１に記載の方法。
【請求項６】
前記第２のエントロピー符号器による符号化処理は、コードブックを使用し、前記第２のエントロピー符号器を用いて符号化するステップは、前記コードブックから除外されたエスケープ符号のレベルの値、または前記コードブックから除外されたエスケープ符号のランレングスの値を符号化することを含むことを特徴とする請求項５に記載の方法。
【請求項７】
前記ゼロ以外の値の係数の前記レベルに対するサインビットが、ビットストリーム内の前記エントロピー符号の後に続くことを特徴とする請求項５に記載の方法。
【請求項８】
前記第２のエントロピー符号器による符号化処理は、コードブックを使用し、該コードブックは、高確率のランレベルの組み合わせの各々に対するエントロピー符号を含み、低確率のランレベルの組み合わせに対するエントロピー符号を除外していることを特徴とする請求項５に記載の方法。
【請求項９】
請求項１乃至８のいずれかに記載の方法をコンピュータに実行させるためのコンピュータ実行可能命令を記録したことを特徴とするコンピュータ読み取り可能記憶媒体。
【請求項１０】
オーディオ周波数係数のシーケンスを符号化するためのシステムであって、
符号化方式の異なる複数のエントロピー符号器を用いてエントロピー符号化を行うために、オーディオ周波数係数のシーケンスの周波数領域範囲を、第１の周波数範囲が主としてゼロ以外の値の周波数係数を含み、第２の周波数範囲が主としてゼロの値の周波数係数を含むように、少なくとも第１の周波数範囲と第２の周波数範囲とに分割するための手段と、
前記複数の異なるエントロピー符号器の間で前記オーディオ周波数係数のシーケンスの符号化に使用すべきエントロピー符号器を切り替えるためのモードセレクタであって、前記第１および第２の周波数範囲の各々の周波数係数の符号化にそれぞれ使用すべき第１および第２のエントロピー符号器を選択するモードセレクタと、
前記第１の周波数範囲の周波数係数を符号化する前記第１のエントロピー符号器と、
前記第１のエントロピー符号器によるエントロピー符号化処理とは異なるランレングスエントロピー符号化処理によって、前記第２の周波数範囲の周波数係数を符号化する前記第２のエントロピー符号器と
を備え、
前記第２のエントロピー符号器による前記ランレングスエントロピー符号化処理は、（ａ）前記第２の周波数範囲内においてゼロの値の係数が連続するランレングスと、（ｂ）前記第２の周波数範囲内において前記連続するゼロの値の係数に隣接したゼロ以外の値の係数のレベルとの組み合わせを表す、エントロピー符号を使用することを特徴とするシステム。
【請求項１１】
符号化済みオーディオ周波数係数のシーケンスを復号化するための方法において、
符号化済みオーディオ周波数係数のシーケンスを受信するステップであって、前記符号化済みオーディオ周波数係数のシーケンスは、第１の周波数範囲が主としてゼロ以外の値の周波数係数を含み、第２の周波数範囲が主としてゼロの値の周波数係数を含むように、少なくとも第１の周波数範囲と第２の周波数範囲とに分割された周波数領域範囲を有し、各範囲の周波数係数が各々異なる符号化方式により符号化されている、ステップと、
前記複数の異なるエントロピー復号器のうちの第１のエントロピー復号器を用いて、前記符号化済みオーディオ周波数係数のシーケンスのうち前記第１の周波数範囲の周波数係数を復号化するステップと、
前記複数の異なるエントロピー復号器のうちの第２のエントロピー復号器を用いて、前記第１のエントロピー復号器によるエントロピー復号化処理とは異なるランレングスエントロピー復号化処理によって、前記符号化済みオーディオ周波数係数のシーケンスのうち前記第２の周波数範囲の周波数係数を復号化するステップと
を含むことを特徴とする方法。
【請求項１２】
前記第１の周波数範囲と前記第２の周波数範囲との間の分割境界は、予め決定されていることを特徴とする請求項１１に記載の方法。
【請求項１３】
前記第１および第２の周波数範囲の各々の周波数係数の復号化に各々使用すべき第１または第２のエントロピー復号器は、復号化すべき周波数係数の周波数範囲に応じて自動的に決定されることを特徴とする請求項１２に記載の方法。
【請求項１４】
前記第１の周波数範囲と前記第２の周波数範囲との間の分割境界は適応的であることを特徴とする請求項１１に記載の方法。
【請求項１５】
前記第１および第２の周波数範囲の各々の周波数係数の復号化に各々使用すべき第１または第２のエントロピー復号器は、前記シーケンスのデータストリーム内のフラグに応じて決定されることを特徴とする請求項１４に記載の方法。
【請求項１６】
前記第１のエントロピー復号器は、可変長符号に可変長記号を割り当てる可変−可変エントロピー復号器であることを特徴とする請求項１１乃至１５のいずれかに記載の方法。
【請求項１７】
前記受信するステップは、リアルタイムの再生のためのチャネルを介してストリーミングのパケットとして前記シーケンスを伝送するストリーミング伝送システムから前記シーケンスを受信することを含むことを特徴とする請求項１１乃至１６のいずれかに記載の方法。
【請求項１８】
前記第２のエントロピー復号器によるランレングスエントロピー復号化処理は、
（ａ）前記第２の周波数範囲内のゼロの値の係数が連続するランレングスと、
（ｂ）前記第２の周波数範囲内において前記連続するゼロの値の係数の後に続くゼロ以外の値の係数のレベルと
の組み合わせを示す、エントロピー符号を復号化することを特徴とする請求項１１に記載の方法。
【請求項１９】
前記第２のエントロピー復号器によるランレングスエントロピー復号化処理は、コードブックを使用し、当該第２のエントロピー復号器によるランレングスエントロピー復号化処理は、前記コードブックから除外されたエスケープ符号のレベル値を復号する処理を含むことを特徴とする請求項１８に記載の方法。
【請求項２０】
前記ゼロ以外の値の係数の前記レベルに対するサインビットは、ビットストリームの中の前記エントロピー符号の後に続いていることを特徴とする請求項１８に記載の方法。
【請求項２１】
前記第２のエントロピー復号器による復号化処理は、コードブックを使用し、当該コードブックは、複数の高確率のランレベルの結合の各々についてのエントロピー符号を含み、低確率のランレベルの結合についてのエントロピー符号を除外していることを特徴とする請求項１８に記載の方法。
【請求項２２】
請求項１乃至２１のいずれかに記載の方法をコンピュータに実行させるためのコンピュータ実行可能命令を格納したことを特徴とするコンピュータ読み取り可能記憶媒体。
【請求項２３】
符号化済みオーディオ周波数係数のシーケンスを復号化するためのシステムであって、
第１の周波数範囲が主としてゼロ以外の値の周波数係数を含み、第２の周波数範囲が主としてゼロの値の周波数係数を含むように少なくとも第１の周波数範囲と第２の周波数範囲とに分割された周波数領域範囲を有し、各範囲の周波数係数が各々異なる符号化方式により符号化された、符号化済みオーディオ周波数係数のシーケンスを受信するオーディオデータ受信手段と、
前記複数の異なるエントロピー復号器の間で、前記符号化済みオーディオ周波数係数のシーケンスの復号化に使用すべきエントロピー復号器を切り替えるためのモードスイッチャと、
前記符号化済みオーディオ周波数係数のシーケンスのうち前記第１の周波数範囲の周波数係数を復号化する第１のエントロピー復号器と、
前記符号化済みオーディオ周波数係数のシーケンスのうち前記第２の周波数範囲の周波数係数を、前記第１のエントロピー復号器によるエントロピー復号化処理とは異なるランレングスエントロピー復号化処理により復号化する第２のエントロピー復号器と
を備えたことを特徴とするシステム。
【請求項２４】
前記第１の周波数範囲と前記第２の周波数範囲との間の分割境界は予め決定されており、前記第１および第２の周波数範囲の各々の周波数係数の復号化に各々使用すべき第１または第２のエントロピー復号器は、復号化すべき周波数係数の周波数範囲に応じて自動的に決定されることを特徴とする請求項２３に記載のシステム。
【請求項２５】
前記第１の周波数範囲と前記第２の周波数範囲との間の分割境界は適応的であり、前記第１および第２の周波数範囲の各々の周波数係数の復号化に各々使用すべき第１または第２のエントロピー復号器は、前記シーケンスのデータストリームの中のフラグに応じて決定されることを特徴とする請求項２３に記載のシステム。
【請求項２６】
前記第２のエントロピー復号器によるランレングスエントロピー復号化処理は、
（ａ）前記第２の周波数範囲内のゼロの値の係数が連続するランレングスと、
（ｂ）前記第２の周波数範囲内において前記連続するゼロの値の係数の後に続くゼロ以外の値の係数のレベルと
の組み合わせを示す、エントロピー符号を復号化する処理を含むことを特徴とする請求項２３に記載のシステム。
【発明の詳細な説明】
【０００１】
（発明の分野）
本発明は、一般的に、周波数領域オーディオ符号化に関し、より詳細には、周波数領域オーディオ符号器および復号器で使用するエントロピー符号化方法に関する。
【０００２】
（背景）
通常のオーディオ符号化環境では、データが、必要な場合（例えば、アナログ形式から）、符号器に入力される記号の長いシーケンスにフォーマットされる。この入力データは、符号器によって符号化され、通信チャネルを介して伝送され（または単に格納し）、復号器によって復号化される。符号化中、この入力は、事前処理され、サンプリングされ、変換され、圧縮され、または別様に操作されて、伝送またはストレージ（ｓｔｒａｇｅ）のための形式になる。伝送またはストレージの後、復号器は、元の入力を再構成しようとする。
【０００３】
オーディオ符号化技法は、２つのクラス、すなわち、時間領域技法および周波数領域のものに分類することができる。時間領域技法、例えば、ＡＤＰＣＭ、ＬＰＣは、時間領域内で直接的に動作し、他方、周波数領域技法は、オーディオ信号をそこで圧縮が行われる周波数領域に変換する。周波数領域コーデック（圧縮器／圧縮解除器）は、さらに、副帯域コーダまたは変換コーダのいずれかに分けられる。ただし、この２つの間の区別は、常に明確なわけではない。つまり、副帯域コーダは、通常、帯域フィルタを使用して入力信号を少数（例えば、４つ）の副帯域に分割し、他方、変換コーダは、通常、多くの副帯域を（また、したがって、それに応じて、多数の変換係数を）有する。
【０００４】
周波数領域内でのオーディオ信号の処理は、従来の信号処理理論と人間の心理音響学モデルの両方によって動機づけられている。心理音響学は、情報内容を縮小するために、聴取者の既知の特性を利用する。例えば、内耳、詳細には、基底膜は、スペクトル解析器のように動作して、オーディオ信号をさらなる神経処理を行う前に、スペクトルデータに変換する。周波数領域オーディオコーデックは、しばしば、元の信号を変更して情報の冗長性を除去することによって、人間の聴力システム内で起っている聴覚マスキングを利用する。人間の耳は、これらの変更を知覚することができないので、ひずみなしの効率的な圧縮を得ることができる。
【０００５】
通常、マスキング分析が、量子化雑音を都合よく「マスク」できるように、量子化と併せて行われる。最近のオーディオ符号化技法では、量子化されたスペクトルデータは、通常、エントロピー符号化、例えば、ハフマン符号化を適用してさらに圧縮する。圧縮は、通信チャネルが、通常、限られた利用可能な容量または帯域幅を有するので、必要とされる。それが通信チャネルを介して確実に伝送される、または単に伝送され得るようにするために、入力データの情報内容を削減することが、しばしば、必要である。
【０００６】
伝送または記憶するデータのサイズを縮小するための可逆的圧縮と非可逆的圧縮の技法を開発するのに、相当な努力が注がれてきた。１つの一般的な可逆技法は、ハフマン符号化であり、これは、特定の形式のエントロピー符号化である。エントロピー符号化は、符号ワードを異なる入力シーケンスに割り当てて、すべての入力シーケンスをコードブック内に記憶する。エントロピー符号化の複雑さは、入力シーケンスＸが取り得る可能な値の数ｍに依存する。小さなｍの場合、可能な入力の組合せは、ほとんど存在せず、したがって、そのメッセージに対するコードブックは、非常に小さいものであり得る（例えば、すべての可能な入力シーケンスを明確に表すのに、数ビットしか必要ない）。デジタルの適用形態の場合、符号英字は、シリーズの２進数｛０，１｝である可能性が非常に高く、符号ワード長は、ビットで測定される。
【０００７】
入力が等しい生起確率を有する記号から構成されていることが既知である場合、最適符号化は、等長符号ワードを使用することである。しかし、入力ストリームが、任意の特定メッセージを等確率で受信する可能性を有することは、通常ではない。実際、あるメッセージは、他のメッセージよりも確率が高く、エントロピー符号器は、これを利用して、予期される入力の間での符号ワードの平均長を最小化する。ただし、従来、固定長入力シーケンスには、可変長符号が割り当てられる（または、逆に、可変長シーケンスには、固定長符号が割り当てられる）。
【０００８】
（概要）
本発明は、周波数領域オーディオ符号化のためにエントロピー符号化モードを選択するための方法に関する。より詳細には、オーディオ入力を表す所与の入力ストリームが、符号化されるべき代表的入力または実際の入力の統計分析から導出した何らかの統計基準によって、周波数範囲に分割される。各範囲には、その範囲の型のデータを符号化するように最適化されたエントロピー符号器を割り当てる。符号化中および復号化中、モードセレクタが、正しいエントロピー方法を様々な周波数範囲に適用する。分割境界は、事前に決定することができ、復号器が、暗黙的に、どの復号化方法を符号化済みデータに適用するかを知ることができるようにする。または、後続データに関する符号化モードの変更を示すことによって、出力ストリーム内で境界にフラグが付けられる転送適応構成を使用することができる。
【０００９】
音声や音楽などの自然音の場合、情報内容は、低周波数範囲に集中している。このことは、統計上、より低い周波数が、より多くの非ゼロのエネルギー値（量子化の後）を有し、他方、より高い周波数範囲は、より高い周波数での内容の欠如を反映して、より多くのゼロ値を有することを意味している。より低い周波数範囲とより高い周波数範囲を分ける１つまたは複数の分割境界を定義するのに、この統計分析を使用することができる。例えば、単一の分割は、周波数成分の低い方１／４が、その分割より下になるように定義することができる。別法では、臨界帯域のほぼ半分が、各定義された周波数帯域内に入るように分割を設定することができる。（臨界帯域は、特定周波数に対する人間聴覚システムの感度に対応する非一様な幅である。）そのような分割の結果は、その１つは、主に非ゼロの周波数係数を含み、もう１つは、主にゼロの周波数周波数係数を含んだ２つの周波数範囲を定義することである。その範囲が主にゼロの値および非ゼロの値を含むという事前の知識は、そのようなゼロの値および非ゼロの値に対して最適化した符号器を使用して、符号化することが可能である。
【００１０】
一実施形態では、主にゼロの値を含んだ範囲は、多重レベルランレングス符号器（ＲＬＥ）を使用して符号化される。すなわち、これは、ゼロの値のシーケンスを１つまたは複数の非ゼロの記号に統計的に相関させて、可変長符号ワードをそのようなゼロの値および非ゼロの値の任意に長い入力シーケンスに割り当てる符号器である。同様に、主に非ゼロの値を含んだ範囲は、可変長符号ワードが量子化記号の任意に長い入力シーケンスに割り当てられる可変−可変エントロピー符号器を使用して符号化される。全体的なより効率的な処理は、入力データの特性に応じて符号化方法を基づけることによって達せられる。実際、分割の数および周波数範囲は、符号化および復号化すべきデータの型によって異なる。
【００１１】
（詳細な説明）
例としての動作環境
図１および下記の議論は、そこで本発明を実施することが可能である適切なコンピュータ環境の簡単な一般的説明を提供することを目的とする。パーソナルコンピュータ上で動作するコンピュータプログラムのコンピュータ実行可能命令の一般的文脈で本発明を説明するが、当分野の技術者には、他のプログラムモジュールとの組合せでも、本発明を実施できることが理解されよう。一般的に、プログラムモジュールには、特定のタスクを実行する、または特定の抽象データ型を実施する、ルーチン、プログラム、構成要素、データ構造などが含まれる。さらに、当分野の技術者には、ハンドヘルド装置、マルチプロセッサシステム、マイクロプロセッサベースの、またはプログラム可能な家庭用電化製品、ミニコンピュータ、メインフレームコンピュータなどを含む、他のコンピュータシステム構成を使用しても本発明を実行できることが理解されよう。本発明の例示する実施形態は、通信ネットワークを介してリンクされている遠隔処理装置によってタスクが実行される分散コンピュータ環境でも実行される。ただし、本発明のいくつかの実施形態は、独立型コンピュータ上でも実行することが可能である。分散コンピュータ環境では、プログラムモジュールは、ローカルと遠隔の両方のメモリ記憶装置に配置することが可能である。
【００１２】
図１を参照すると、本発明を実施するための例としてのシステムが、コンピュータ２０を含み、これが、処理装置２１、システムメモリ２２、および処理装置２１に対するシステムメモリを含んだ様々なシステム構成要素を結合するシステムバス２３を含んでいる。処理装置は、Ｉｎｔｅｌ  ｘ８６、Ｐｅｎｔｉｕｍ、Ｉｎｔｅｌおよび他社からの互換マイクロプロセッサ、ＤｉｇｉｔａｌによるＡｌｐｈａプロセッサ、ならびにＩＢＭおよびＭｏｔｏｒｏｌａからのＰｏｗｅｒＰＣを含む、様々な市販のプロセッサのうちの任意のものであり得る。デュアルマイクロプロセッサおよび他のマルチプロセッサのアーキテクチャも、処理装置２１として使用することができる。
【００１３】
システムバスは、メモリバスまたはメモリコントローラ、周辺バス、ならびに、そのいくつかを挙げれば、ＰＣＩ、ＡＧＰ、ＶＥＳＡ、Ｍｉｃｒｏｃｈａｎｎｅｌ、ＩＳＡ、ＥＩＳＡなどの様々な従来バスアーキテクチャのうちの任意のものを使用するローカルバスを含んだ、いくつかの型のバス構造のうちの任意のものであり得る。システムメモリは、読取り専用メモリ（ＲＯＭ）２４およびランダムアクセスメモリ（ＲＡＭ）２５を含む。始動時などに、コンピュータ２０内の要素間で情報を転送するのを助ける基本ルーチンを含んだ基本入力／出力システム（ＢＩＯＳ）は、ＲＯＭ２４内に記憶されている。
【００１４】
コンピュータ２０は、さらに、例えば、取外し可能ディスク２９から読み取る、またはそれに書き込むために、ハードディスクドライブ２７、磁気ディスクドライブ２８を、また、例えば、ＣＤ−ＲＯＭディスク３１を読み取るため、あるいは他の光学式媒体から読み取る、またはそれに書き込むために、光ディスクドライブ３０をさらに含む。ハードディスクドライブ２７、磁気ディスクドライブ２８、および光ディスクドライブ３０は、それぞれ、ハードディスクドライブインターフェース３２、磁気ディスクドライブインターフェース３３、および光ディスクドライブインターフェース３４によって、システムバス２３に接続されている。これらのドライブおよびその関連するコンピュータ可読媒体は、コンピュータ２０のためのデータ、データ構造、コンピュータ実行可能命令などの不揮発性ストレージを提供する。コンピュータ可読媒体の説明は、ハードディスク、取外し可能磁気ディスク、およびＣＤに関連するが、当分野の技術者には、磁気カセット、フラッシュメモリカード、デジタルビデオディスク、ベルヌーイカートリッジなど、コンピュータによって読取り可能な他の型の媒体も、例としての動作環境内で使用できることが理解されよう。
【００１５】
オペレーティングシステム３５、１つまたは複数のアプリケーションプログラム（例えば、インターネットブラウザソフトウェア）３６、他のプログラムモジュール３７、およびプログラムデータ３８を含む、いくつかのプログラムモジュールをドライブおよびＲＡＭ２５内に記憶することが可能である。
【００１６】
ユーザは、キーボード４０、およびマウス４２などのポインティングデバイスを介して、コマンドおよび情報をコンピュータ２０に入力することができる。他の入力装置（図示せず）には、マイクロホン、ジョイスティック、ゲームパッド、サテライトディッシュ、スキャナ、またはそれらに類するものが含まれ得る。これらの入力装置および他の入力装置は、しばしば、システムバスに結合されたシリアルポートインターフェース４６を介して処理装置２１に接続するが、パラレルポート、ゲームポート、または汎用シリアルバス（ＵＳＢ）などの、他のインターフェースによって接続することも可能である。モニタ４７または他の型の表示装置も、ビデオアダプタ４８などのインターフェースを介してシステムバス２３に接続されている。モニタに加えて、パーソナルコンピュータは、通常、スピーカまたはプリンタなどの、他の周辺出力装置（図示せず）を含む。
【００１７】
コンピュータ２０は、遠隔コンピュータ４９などの、１つまたは複数の遠隔コンピュータに対する論理接続を使用するネットワークされた環境内で動作するものが望まれる。遠隔コンピュータ４９は、ウェブサーバ、ルータ、ピア装置、または他の一般のネットワークノードであることが可能であり、図１ではメモリ記憶装置５０だけを図示しているが、通常、コンピュータ２０に関して記載した多くのまたはすべての要素を含む。コンピュータ２０は、ゲートウェイ５５（例えば、ルータ、専用回線、または他のネットワークリンク）、モデム５４リンクを介して、あるいはオフィス内ローカルエリアネットワーク（ＬＡＮ）５１またはワイドエリアネットワーク（ＷＡＮ）５２によって確立されたインターネット接続を介して、遠隔コンピュータ４９に接触することができる。図示したネットワーク接続は、例としてのものであり、コンピュータ間に通信リンクを確立する他の手段も使用できることが理解されよう。
【００１８】
コンピュータプログラミング分野の技術者の慣行により、本発明は、そうでないことを示さない限り、コンピュータ２０によって実行される動作およびオペレーションの記号表現を参照して下記に説明する。そのような動作およびオペレーションは、時として、コンピュータ実行と呼ばれる。この動作および記号で表されるオペレーションには、処理装置２１による、データビットを表す電気信号の操作が含まれることを理解されたい、これは、結果として電気信号表現での変換および縮小を引き起こし、またメモリシステム（システムメモリ２２、ハードドライブ２７、フロッピーディスク２９、ＣＤ−ＲＯＭ３１を含む）内のメモリロケーションでのデータビットの保持を引き起こす。また、これによりコンピュータシステムのオペレーションならびに信号の他の処理を再構成したり、変更する。そこにデータビットが保持されているメモリロケーションは、そのデータビットに対応する特定の電気特性、磁気特性、または光特性を有する物理ロケーションである。
【００１９】
図２は、チャネル２１０を介してオーディオデータを伝送するための伝送モデルを示している。この伝送のソースは、ライブのブロードキャスト、記憶済みデータ、または配線式／無線通信リンク（例えば、ＬＡＮまたはインターネット）を介してリトリーブされた情報とすることができる。チャネル２１０は、限られた帯域幅のものであると想定し、したがって、データがチャネルを介して確実に送信され得るようにするには、ソースデータ２００の圧縮が望ましい。この議論は、オーディオデータの伝送を中心的に扱うが、本発明は、埋め込まれたオーディオデータ（例えば、ＭＰＥＧデータストリーム内で多重化された）を有するオーディオビジュアル情報、または圧縮データパターン（例えば、コヒーレントデータ）を有する他のデータソースなど、他のデータの転送にも適用することに留意されたい。
【００２０】
図示するとおり、ソースデータ２００は、フィルタバンク変換または離散余弦変換などの時間／周波数変換符号器２０２に入力される。変換符号器２０２は、オーディオデータソースなどの、連続する、またはサンプリングされた時間領域入力を所定（ただし、多分、異なる）帯域幅の複数周波数帯域に変換するように設計されている。次に、可聴な影響なしに、問題なく削減できる信号の成分を判定するために、これらの帯域を、人間聴覚知覚モデル２０４（例えば、心理音響学モデル）に関して分析することができる。例えば、ある周波数は、ある別の音または周波数が入力信号内に存在するとき、不可聴であることがよく知られている（同時マスキング）。したがって、そのような不可聴信号は、入力信号から問題なく除去することができる。人間聴覚モデルの使用は、よく知られており、例えば、これは、ＭＰＥＧ１、２、および４の規格である。（そのようなモデルは、量子化２０６の操作に組み合わせることができることに留意されたい。）
【００２１】
時間／周波数変換２０２を実行した後、各範囲内の周波数係数を量子化２０６して、各係数（振幅レベル）を有限セットの可能な値から取った値に変換する。ここで、各値は、周波数範囲を表すように割振られたビットに基づくサイズを有する。量子化器は、メモリを有する（または有さない）ミッドライザまたはミッドトレッダなど、従来の一様または非一様の量子化器であり得る。一般的な量子化の目的は、入力信号データを表すのに最適のビット割振りを識別すること、すなわち、ソースデータの（聴覚上）重要な部分を確実に符号化するため、利用可能な符号化ビットの使用を割り当てることである。所望のビット伝送速度（一定のビット伝送速度を想定して）を満たすために、量子化ステップサイズ予測など、様々な量子化方法を使用することができる。ソース２００を量子化した後、結果のデータをエントロピー符号化する２０８（図６〜１３の議論を参照）。
【００２２】
エントロピー符号化した出力は、通信チャネル２１０を介して伝送する（または後の伝送のために記憶する）。次に、受信端２１６が、逆符号化処理、すなわち、ソースデータ２００の符号化を戻す（ｕｎｄｏ，復号化する）一連のステップ）を実施する。つまり、符号化済みデータが、エントロピー復号器２１２に対する入力として、チャネル２１０を介して受信されて、この復号器が、逆コードブックルックアップを実行して、符号化済み出力を入力記号シリーズ２００に対する元の量子化出力に近似するものに変換する。この近似データが、次に、量子化解除器２１４および時間／周波数変換復号器２１８によって処理されて、元の符号化操作を逆転して、元のソースデータ２００に類似した再構成データ２２０をもたらす。再構成データ２２０は、元のソースデータ２００を近似するに過ぎないことに留意されたい。というのは、ステップ２０４〜２０８を適用することは、不可逆的処理だからである。
【００２３】
この伝送モデルのための１つの可能な実施形態は、リアルタイムデータがサーバ／サーバ機能アプリケーションからネットワークリンクを介してリトリーブされるのにつれて、それを処理、表示、または再生しようとするクライアントアプリケーションプログラムである。例えば、クライアントは、適応帯域幅予約を提供するストリーミング送達システムを使用し得る。（１つのそのようなストリーミングフォーマットは、Ｍｉｃｒｏｓｏｆｔ  Ａｄｖａｎｃｅｄ  Ｓｔｒｅａｍｉｎｇ  Ｆｏｒｍａｔである。）ストリーミング環境は、データ送達を、回線速度制約など、特定のリトリーブ要件に対して最適化することを可能にすることによって、従来のネットワーク機能プログラムと対照をなす。ストリーミングデータの際立った特徴は、クライアントがデータを受信するのにつれて、それをリアルタイムで漸進的に見ることができることである。処理済のデータは、クライアントによる後のリトリーブのために記憶することができ、またそのようなリトリーブは、非ストリーミングフォーマットで（例えば、小さな再生装置によって）実行され得ることに留意されたい。
【００２４】
ストリーミングフォーマットは、同期オブジェクトデータストリームの構造を定義し、任意のオブジェクト、例えば、オーディオおよびビデオのデータオブジェクト、スクリプト、ＡｃｔｉｖｅＸコントロール、ＨＴＭＬ文書をデータストリームに入れることができるようにする。アプリケーションプログラミングインターフェース（１つのそのようなＡＰＩは、Ｍｉｃｒｏｓｏｆｔ  Ａｕｄｉｏ  Ｃｏｍｐｒｅｓｓｉｏｎ  Ｍａｎａｇｅｒである）が、ストリーミングフォーマットに対するアプリケーションサポートを円滑にするために提供される。通信チャネル２１０を介するストリーミングフォーマットデータの伝送では、ソース情報が、ネットワークに対して適切な形式に変換に変換されることを必要とする。しかし、経路指定情報およびデータを含む従来のパケットとは異なり、ストリーミングパケットは、ストリーム内の異なるオブジェクトからの優先順位付き混合データを含み、したがって、帯域幅は、より高い優先順位のオブジェクトに、最初に、割り振ることが可能である。受信端２１６で、受信側による使用のために、優先順位付きデータストリーム内のオブジェクトが再構成される。
【００２５】
データは、多分、それが受信された時、使用されるので、ストリーミング内容は、伝送遅延の影響を受ける。データが確実に到着しない場合、または伝送速度が、許容可能な最低限を下回って低下する場合、そのデータは、使用不可能になる可能性がある（例えば、ビデオシーケンスの再生が失敗し得る）。したがって、帯域幅を多く使用するデータ（オーディオフィードなど）は、その帯域幅要件が通信チャネル２１０によって確実に満たされ得るようにするために、相当の圧縮を必要とする。非可逆的圧縮の程度は、再構成信号の品質に必然的に影響するので、サーバは、異なるクライアントネットワーク接続速度に対する選択可能な符号化を提供する（またはリアルタイムスループットを識別する適応フィードバックシステムを使用する）べきである。
【００２６】
周波数係数ソースデータ２００を符号化して、通信チャネル２１０を介する確実な伝送を保証するのに特に有効な方法は、エントロピー符号化である。後述のとおり、入力データの異なる部分に対して最適化された異なる符号化方法を適用することによって、データコヒーレンシーを十分に利用することができる。エントロピー符号化は、記号が非一様の確率分布を有するとき、有効である。後述する可変−可変コーダおよびＲＬＥコーダなど、多くの入力記号をグループ化するエントロピー符号化方法は、データコヒーレンシーを十分に利用することに優れている。異なる周波数範囲に対して異なる符号化方法を使用することは、符号器がそれぞれのそのような範囲ごとの確率分布に対して調整されているとき、より最適な符号化を可能にする。
【００２７】
図３は、周波数領域に変換されている時間領域信号を図示している。Ｘ軸に沿って、ゼロ３０２から最大周波数３０４までの範囲３００の周波数がある。分割３０６は、範囲３００内で定義されており、この分割は、予期される入力ストリームの統計分析（例えば、エントロピーコードブックを慣らしている最中にえられた統計情報、または実際の入力の適合分析による）によって決定され、この統計モデルが、符号化のために、実際の入力３０８に対して適用される。
【００２８】
分割を設定する１つの手法は、前述のとおり、周波数または臨界帯域のあるパーセンテージを境界より下に置くことである。
【００２９】
代替方法は、各周波数ごとの確率分布によるゼロおよび非ゼロの確率などの基本統計を集めることである。各周波数の統計の検査は、周波数にわたる緩やかな変化を示し、分割境界は、各分割内の分布が類似するように選択することができる。周波数分割は、入力のサンプリング速度および予期されるビット伝送速度に対して敏感であることに留意されたい。サンプリング速度およびビット伝送速度は、量子化された周波数係数の確率的特性を決定し、この特性が基本的に、分割の配置を決定することを担う。
【００３０】
より最適な方法は、「最適」境界位置を決定するために、全数探索を実行することによって適合的に分割を配置することである。つまり、最適の解決法は、すべての周波数（またはそのサブセット）を分割位置として試し、エントロピー符号化を実施して、どの境界の可能な位置が、符号化のために最小数のビットをもたらすか、追跡することである。計算上、よりインテンシブではあるが、計算コストが問題なのであれば、複数の分割が使用される場合、全数探索（または周波数サブセットが使用される場合、ほぼ全数探索）の圧縮の利点が、コストを上回る。
【００３１】
周波数スペクトル３００を別々の周波数下位領域３１０、３１２に分けることによって、符号器は、異なる周波数範囲を符号化するように最適化されている異なる符号化方式を適用することができる。これは、符号化すべきデータの特性に応じて異なるエントロピー符号化テーブルを置き換えたエントロピー符号化方式などの、前の方法と対照をなす。こうした従来の方法は、その単一エントロピー符号化アルゴリズムの柔軟性により、符号化テーブルが異なる種類の入力データを考慮できないことにより、またいつ異なるテーブルを使用するべきか識別することに関連するオーバーヘッドによって、制限を受ける。１つの型のデータに対して最適化された方法は、異なる型のデータに効率的に適用することができない。
【００３２】
図示する実施形態では、範囲３００に対して選択された分割基準は、特定のスペクトルイベントが、特定の強度（例えば、ゼロ）またはそれに近いところでの一連の係数である確率Ｃ（Ｆ）（Ｙ軸）である。コードブック生成の場合と同様に、ゼロの値のデータを受信する確率は、例としての入力に関して、事前計算することができる。図示するとおり、入力信号３０８は、示された分割３０６の後、ゼロである確率が高い。（分割の仕切り３０６の位置は、その仕切りを越える入力の８０％または９０％がゼロまたはそれに近くなるように選択されている。）
【００３３】
最低限、入力信号３０８は、それぞれの範囲が異なる符号化方法による圧縮に最も適したデータ特性を有する２つの範囲に分割されるものと想定する。図示する実施形態では、一方の範囲は、主にゼロの値を有し、もう一方の範囲は、非ゼロの値を有する。したがって、２つの符号器が使用され、そのそれぞれは、それに対応する範囲内の型のデータに対して最適化されている。図示する実施形態は、周波数係数を２つの範囲に分割するが、それぞれがそれ自体の最適化された符号器を有する２つより多くの範囲を定義することができる、あるいは異なる範囲が、類似の特性を共有し、したがって、同一の符号器を使用することが可能である。
【００３４】
主に非ゼロの範囲３１０を符号化するのに、図６〜１３に関して述べたようなエントロピー符号器を使用することができる。後述するとおり、図６〜１３の符号化方法は、非ゼロの聴覚入力データを符号化するのに特によく適している。主にゼロの値の範囲３１２の場合、そのようなデータに対して最適化された符号器を使用する。図示する実施形態では、ランレングス符号器が、ある支配的値（例えばゼロ）を有するデータを符号化するのに最適化されているので、それを使用する。図１３は、主にゼロの値の範囲３１２を効率的に符号化することができる、１つのＲＬＥベースのエントロピー符号器を図示している。
【００３５】
図４は、チャネル（図２を参照）を介してオーディオデータを伝送するための伝送モデルを図示しており、そこでは、複数のエントロピー符号化／復号化方法が、入力データ２００を操作するのに使用される。ソースオーディオデータ２００は、ある周波数範囲内の値を有することが知られている。図２に関して前述したとおり、ソースデータ２００は、周波数領域に変換し２０２、心理聴覚モデルに従って縮小し２０４、量子化する２０６ことができる。量子化は、かなりの数のゼロに近い出力値を生成し得るので、エントロピー符号器２０８は、この量子化出力を符号化するように最適化することができる。
【００３６】
量子化の後、量子化済みデータに関するスペクトル係数は、通常のオーディオデータの情報内容を追跡する傾向がある。量子化係数の分析は、それらが、より低い周波数範囲で、非ゼロであり、より高い周波数で、主にゼロ係数である可能性が高いことを示す。したがって、ある周波数位置に位置する周波数分割の場合、モードセレクタ４００が、符号化される周波数範囲に応じて、符号器を決定することができる。
【００３７】
分割の配置を決定することは、いくつかの既知のエントロピー符号器のうちのどれが、異なる下位範囲に対してより良好な符号化効率を実現するかを識別する、統計分析に基づくことが可能である。１つの構成では、分析は、例としての入力に関する符号化または復号化に先立って実行される。これは、分割位置、および各下位範囲に対する対応する符号器の事前決定を可能にして、該当するコーダでの変更にフラグを付けるのに、何もオーバーヘッドを導入する必要がないようにする。
【００３８】
別の方法では、現行のデータに対して、統計分析を実行することができる（リアルタイムで、またはオフラインで）。この構成では、符号器／復号器は事前に知られているが、該当するコーダでの変化を示すのに、フラグを符号化済みデータストリームに埋め込む必要がある。前述のとおり、各下位範囲ごとにある程度の符号化効率が得られるまで、異なる可能な分割位置を試みることが可能である。復号器によるフラグの受信は、下位範囲の終りを示し、フラグの値は、逐次のデータに対してどの復号器を使用するかを示す。
【００３９】
マーカを挿入することは、符号化／復号化処理にある程度のオーバーヘッドを追加するが、そのようなマーカは、従来技術の符号化方法に対する改良を表すものである。例えば、図示する実施形態をオーディオデータの従来の（例えば、ＭＰＥＧ１、２、４を参照）エントロピー符号化と比較されたい。従来のシステムは、すべてのデータに対して単一のエントロピー符号器を使用し、異なるコードブックが、入力データの周波数範囲内にある多くの臨界帯域（通常、サンプリング速度に応じて、２４またはそれより多くの帯域）のそれぞれに関連付けられる。２４の帯域を想定して、各臨界帯域遷移で、２４個のコードブックのうちのどれを使用してそのバンドのデータを符号化すべきかを示すのに、２ビット（またはそれより長い）フラグが、必要とされる。（２４の状態を追跡するのに５ビットが必要とされるが、このフラグ自体を効果的により少ないビットに符号化することができる。）これは、フラグを全く必要としないか、あるいはフラグを使用するが、下位範囲の数が、臨界帯域の数に比するものになり、符号化方法の数がテーブルの数に近づかない限り、従来の方法よりも効率的である、図示する実施形態と明確な対照をなす。つまり、臨界帯域を使用する符号化ごとに、２４個の下位範囲が存在して、どの符号化テーブルを使用すべきかを示すのに、２〜５ビットのフラグを必要とする。対照的に、図示する実施形態は、２つまたは３つの下位範囲しか有さないことが可能であり、したがって、オーバーヘッドがずっと少ない。
【００４０】
図示するとおり、Ｎ個の所定の符号器４０２〜４０６が存在し、そのそれぞれは、何らかの支配的特徴を備えたデータを有する周波数範囲を符号化するように最適化されている。このことは、Ｎ個の別々の入力範囲が存在することを必ずしも意味しない。というのは、異なる周波数範囲が、そのデータに関して、類似の統計的特徴を有し、したがって、同一の符号器を使用することが可能であるからである。図示する例では、２つの範囲（１つの分割）だけが存在し、これらは低い（主に非ゼロの係数）周波数範囲および高い（主にゼロの係数）周波数範囲に対応している。したがって、分割を越えた主にゼロのデータは、ＲＬＥ型符号器（例えば、図１３参照）を使用して符号化され、分割の前のデータは、可変−可変エントロピー型エントロピー符号器を使用して符号化される。
【００４１】
ただし、一般的な場合、特定の入力に関して統計情報が利用可能になると、どの符号器が入力を最も良く圧縮できるかに応じて、異なる符号器を選択することができる。例えば、従来のハフマン符号化、ベクトルハフマン変種、ＲＬＥ符号化などの符号化方法を最適化し、高いスペクトル値、低いスペクトル値、混合したまたは変更するスペクトル値、または別の何らかの所望の／ありそうな特徴を有する入力に対して、そのコードブックを教えることができる。すべての入力に対する単一符号器の従来の使用とは対照的に、図示する構成は、入力に関する統計プロファイルと、符号器のコードブックが教えられるデータに関する統計プロファイルとの間の最適なマッチンク（対応）に応じて、異なる符号化方法を使用（ｍａｔｃｈ）する。
【００４２】
どの符号器４０２〜４０６を使用するか決定した後、処理は、図２に関連して述べたとおり、データを復号化のために受信側２１６に送信し続ける。逆モードセレクタは図示していないことに留意されたい。適切な復号器を適切に選択してモードセレクタ４００の動作を逆にするために、モードスイッチャが必要である（例えば、図２の復号器２１２の一環として）。ただし、前述のとおり、範囲の仕切り位置を事前に決定し、これにより、復号化の間での識別をやめることができる。さもなくば、動的適応符号化／復号化のため、埋込みフラグを使用して、復号器選択を起動することができる。フラグを使用することは、モードセレクタを使用することと同じであり、所定のおよび適応するように配置された分割の双方に対して動作するように、モードセレクタを設計することが可能である。
【００４３】
図５は、非ゼロ周波数係数の高い確率を有する入力に対するエントロピー符号器のコードブックを生成するための、好ましい方法を示すフローチャートである。詳細には、従来技術の技法とは対照的に、図５は、可変長記号グループに対する可変長符号割当てを有するコードブックを作成することを図示している。（従来技術の技法は、入力の固定長符号または入力の固定長ブロックのいずれかを必要とする。）好ましい実施形態は、可変長Ｘシーケンスを符号化するのに可変長符号ワードを使用するエントロピーベースの可変−可変符号を提供することによって、大きい次元のベクトル符号化のリソース要件、および等長のワードへの符号化の非実用性を克服する。リソース要件は、固定最大コードブックサイズを設定することによって、任意に制限することができる。このコードブックは以下のように生成する。
【００４４】
１＜＝ｊ＜＝Ｎｉについて、入力ストリーム内で発生する確率Ｐｉを有する各ソース記号グループ｛ｘｊ｝をｙｉが表すものとして、各グループにＬｉビットを有する対応する符号ワードを割り当てるものとする。各ｘｊは、所定サイズの固定英字から選び出すものと想定すると、目的は、方程式Ｌ＝
【００４５】
【数１】
0004786796.tif 000002
【００４６】
を最小化することである。
【００４７】
この問題に対する一般的な解を見つけ出す代わりに、問題を２つの異なるタスクに分離する。第１タスクは、後述の経験的手法を介する入力記号｛ｘｉ｝のセットの（部分最適）グループの識別である。第２タスクは、グループ化された記号｛ｙｉ｝に対してエントロピー型符号を割り当てることである。ソースがコヒーレントではない（すなわち、入力が独立である、またはメモリが無い）場合、｛Ｎｊ｝という同一構成を有するどのグループも同一の符号化効率を達成することができることが知られていることに留意されたい。この状況では、第１タスクは、重要ではない。
【００４８】
第１タスクを実行するため、｛ｙｉ｝＝｛ｘｉ｝などの、初期の単純記号グループ５００が用意される。この初期構成は、例としてコードブックの作成を教えるために、入力ストリームが使用されることを想定している。コンピュータは、入力からの各記号の受信を追跡するために、データ構造などのソフトウェア構造体を使用してプログラムすることができるものと理解されたい。そのようなデータ構造は、２進型ツリー構造、ハッシュテーブル、またはこの２つの何らかの組合せとして実施することが可能である。他の等価の構造を使用することも可能である。
【００４９】
単純グループを決定した後、各ｙｉごとの生起確率を計算する（５０２）。そのような確率は、コードブック生成を教えるために使用される任意の例としての入力を考慮して決定される。さらなる記号が記号データ構造に追加された時、この確率は、動的に調整される。
【００５０】
次に、最高確率のグループｙｉ（ｙｍｐと表す）を識別する（５０４）。最高確率の記号が、以前の低い確率であった記号のグループである場合（５０６）には、そのグループをそれを構成する記号に分割して（５０８）、ステップ５０２から処理を再開する。（記号は結合されるものの、記号を抽出することができるように、グループは、その中にあるすべての記号が記憶される。）
【００５１】
その記号が１つのグループではない場合には、処理は、ステップ５１０において、最高確率のグループを単一記号拡張ｘｉで試験的に拡張し続ける。好ましくは、ｙｍｐは、英文字Ｘからの各記号で拡張する。ただし、英文字が非常に大きく、多くの拡張は確率が低いことが既知である場合、予測器を使用して、確率の高い拡張だけを含んだ拡張セットのみを生成することが可能である。例えば、そのような予測器は、意味構造上の意味または文脈的（前後関係の）意味に基づいて非常に確率の低い拡張を推測的に無視できる。
【００５２】
次に、ｙｍｐの各試験的拡張に関する確率を計算して（５１２）、最高確率の拡張だけを保持する（５１４）。より低い確率の拡張は、結合グループとして縮小してまとめ（５１６）、結合グループを示す特別記号（イベント）を付けて、コードブック内に記憶する。このワイルドカード記号は、ｙｍｐをプレフィックスとして有する任意の記号グループを表すが、最高確率の拡張とは異なる拡張（サフィックス）が付いている。つまり、ｙｍｐ＋ｘｍｐが最高確率のルートおよび拡張である場合には、他のそれほど確率の高くない拡張は、ｙｍｐ＊、＊≠ｘｍｐとして表される。（この議論は、明確にするために、単一記号拡張の逐次処理を想定しているが、複数の記号拡張の並列実行が考慮されていることに留意されたい。）
【００５３】
単一の記号拡張を適用すること、および最高確率のグループだけを保持することは、論議を明確にするために課した制約であることが、当分野の技術者には理解されよう。議論は、逐次処理を中心的に扱うが、コードブック構成は、並列で行い得ることをさらに理解されたい。
【００５４】
コードブック構成は、すべての可能な拡張が作成されるまで、またはコードブックエントリの数が所定の限界に達するまで、ステップ５０２〜５１６を繰り返す（５１８）ことによって完了する。つまり、現行のｙｉごとの確率の計算（５０２）、最高確率の拡張および最低確率の拡張をそれぞれ選択し（５０４）およびグループ化することを繰り返す。ここで、コードブックセット｛Ｙ｝が、この時点でｙｍｐ＋ｘｍｐを含む。の操作を繰り返し適用することの効果は、高い相関を有する記号グループを自動的に集め、グループ間の相関が最小化されるようにすることである。これは、Ｌの分子を最小化し、他方、同時に、Ｌの分母が最大化されるように、最高確率のｙｉの長さを最大化する。
【００５５】
図６〜１３は、例としての英字｛Ａ，Ｂ，Ｃ｝に対する、図５に準拠するコードブックの作成を図示する。この論議のため、コードブックは、例としての入力ストリーム「Ａ  Ａ  Ａ  Ｂ  Ｂ  Ａ  Ａ  Ｃ  Ａ  Ｂ  Ａ  Ｂ  Ｂ  Ａ  Ｂ」に対して定義される。前述のとおり、１つまたは複数の例としての入力を使用して、コードブックを生成することが可能であり、これが、次に、符号器および復号器によって使用されて、任意の入力を処理する。明確にするため、このコードブックは、ツリー構造として提示する。ただし、これは、実際には、リニアテーブル、ハッシュテーブル、データベースなどとして実施することが可能である。図示するとおり、ツリーは、左から右に向いており、そこで左列（例えば、「Ａ」および「Ｘ０」）は、ツリー型構造の一番上の行を表し、順次、字下げされている行が、前の行のノードの「子」を表す（例えば、図７のトップダウンツリー内で、ノード「Ａ」は、第２行の中間子ノード「Ｂ」に対する第１行の親ノードである。）。
【００５６】
コードブックを用意する上で、一般的規則は、最高確率のリーフノードを選出し、それを拡張し、最高確率のリーフノードを決定するために確率を再計算し、次に、残りの兄弟ノードを単一Ｘｎノード（ｎ＝０．．Ｎ、ノードが結合されるたびに毎回、追跡する）に縮小することである。最高確率ノードがグループノードであると判明した場合には、そのグループを分割し、確率を再計算して、最高確率のメンバノードを保持する（すなわち、残りのグループメンバは、再グループ化する）。処理は、所定サイズを有するコードブックなど、ストップ状態に達するまで、循環する。
【００５７】
図６は、入力ストリーム「Ａ  Ａ  Ａ  Ｂ  Ｂ  Ａ  Ａ  Ｃ  Ａ  Ｂ  Ａ  Ｂ  Ｂ  Ａ  Ｂ」に対する初期グループを図示している。この入力の初期構文解析は、Ａ＝８／１５、Ｂ＝６／１５、Ｃ＝１／１５の生起確率を示す。この初期単純グループは、異なる基準に基づいて作成することが可能であり、その最も単純なものは、英字内の各文字に対する第１レベルノードを有する。ただし、入力英字が大きい場合、単純グループは、最高確率を有する記号の何らかのサブセットに制限することが可能であり、残りの記号はＸグループに結合される。図６は、２つの初期グループだけで開始することによってこの技法を図示し、グループＡ  ６００は、確率８／１５を有し、グループＸ０  ６０２は、確率７／１５を有し、ここで、Ｘ０は、英字内のすべての残りの低確率の記号、例えば、ＢおよびＣを表す。
【００５８】
初期単純グループを用意した後、最高確率を有するリーフノードを拡張のために選択する（処理シーケンスに関する図５の議論も参照）。したがって、図７で示すとおり、グループＡ  ６００は、英字内の各文字によって試験的に拡張される（または、初期グループの作成に関して述べたとおり、その何らかのサブセットにこの拡張を制限することも可能である）。次に、入力ストリーム「Ａ  Ａ  Ａ  Ｂ  Ｂ  Ａ  Ａ  Ｃ  Ａ  Ｂ  Ａ  Ｂ  Ｂ  Ａ  Ｂ」に関して確率を再計算して、試験的拡張Ａ  ６０６、Ｂ  ６０８、およびＣ  ６１０に対する値を決定する。この結果は、９つの構文解析グループであり、ここで「Ａ  Ａ」は２／９出現し、「Ａ  Ｂ」は４／９出現し、「Ａ  Ｃ」は０／９出現する。したがって、最高確率の拡張「Ａ  Ｂ」を保持し、他の拡張をＸ１＝Ａ，Ｃに縮小する。この議論では、すべての確率を再計算するが、より効率的な手法は、ノード内の各ノードに対する確率と記号関連を保持して、必要となる情報だけを計算することである。
【００５９】
図８は、図７のＸ１  ６１２への縮小を示す。処理は、最高確率を有するノード、例えば、確率４／９のノードＢ  ６０８の識別で繰り返す。
【００６０】
図９に示すとおり、このノード６０８は、前述のとおり、記号Ａ  ６１４、Ｂ  ６１６、Ｃ  ６１８で試験的に拡張され、最高確率を有する試験的グループが保持される。確率を再計算した後、その結果は、８つの構文解析グループであり、そこでは、記号シーケンス「Ａ  Ｂ  Ａ」６１４が一度、出現し、「Ａ  Ｂ  Ｂ」６１６が一度、出現し、「Ａ  Ｂ  Ｃ」６１８は全く出現しない。試験的拡張Ａ  ６１４と試験的拡張Ｂ  ６１６は、同一の生起確率を有するので、どちらの記号を保持するかを選択する規則を定義する必要がある。この議論の場合、等確率が存在するときはいつでも、一番高い行のノード（例えば、トップダウンツリー内の一番左の子ノード）が保持される。同様に、ツリーの行の間に競合が存在する場合、一番左の行のノード（例えば、トップダウンツリーのルートに一番近いノード）が保持される。
【００６１】
したがって、図１０に示すとおり、ノードＡ  ６１４（図９）が保持され、ノードＢ  ６１６とノードＣ  ６１８が結合されて、１／８＋０／８という結合確率を有するノードＸ２＝Ｂ，Ｃ  ６２０になる。ここで、次のステップは、入力ストリームに関して現行で最高確率を有するノードを拡張することである。図示するとおり、ノードＸ１＝Ａ，Ｃ  ６１２とＸ０＝Ｂ，Ｃ  ６０２は、同一の生起確率（３／８）を有する。前述のとおり、ツリー内の最高ノード（Ｘ０  ６０２）が拡張されるように、デフォルト規則が使用される。（整合的であることだけが必要であるが、より高いレベルのノードを拡張することが望ましい。というのは、そうすることが、長い符号ワードの数を増加させることによって、符号化効率を向上させ得るからである。）
【００６２】
ただし、Ｘ０  ６０２は、結合ノードであり、したがって、これは拡張するのではなく、分割しなければならない。図１１は、ノードＸ０をその構成記号Ｂ  ６２２とＣ  ６２４に分割することの結果を図示している。確率を再計算することが、記号シーケンス「Ａ  Ｂ  Ａ」は１／８出現し、「Ａ  Ｂ  Ｘ２」は１／８出現し、「Ａ  Ｘ１」は３／８出現し、「Ｂ」  ４２２は２／８出現し、「Ｃ」は１／８出現することを示す。これは、分割オペレーションであるので、最高確率を有する分割ノード、例えば、ノードＢ  ６２２が保持され、残りのノードは、再結合されてＸ０６０２に戻る。
【００６３】
図１２は、高確率ノードＢ  ６２２を保持することの結果を示している。グループＸ０６０２は、この場合、単一記号「Ｃ」だけを表すことに留意されたい。確率を改訂した後、最高確率を有するノードを識別して、分割または拡張しなければならない。図示するとおり、記号シーケンス「Ａ  Ｂ  Ａ」は１／８出現し、「Ａ  Ｂ  Ｘ２」は１／８出現し、「Ａ  Ｘ１」は３／８出現し、「Ｂ」は２／８出現し、「Ｘ０」は１／８出現する。したがって、ノードＸ１  ６１２は、結合ノードであるので、分割しなければならない。
【００６４】
分割は、前述のとおりの手順で行われて、図５に関連して前述したとおり、入力サイクルを処理する。ここで、停止状態に達するまで（例えば、コードブックが、最大サイズに達する）、最高確率ノードが、拡張または分割される。コードブックが停止状態に達すると、データを符号化して、通信チャネルを介して伝送することに利用することができる。
【００６５】
図１３は、コードブック生成の図５の方法を変更するために使用することができるしきい値格子を図示している。図３および４に関して述べたとおり、入力データのある部分を処理するように符号器を調整することができる場合、符号化はより効率的になる。詳細には、符号化方法が、相当な数の反復する値を生成することが知られている場合、エントロピーコーダをＲＬＥ型符号化と組み合わせて、反復する値を含んだデータについて符号化効率を高めることが可能である。
【００６６】
図示する実施形態では、入力データの量子化では、入力データに対する周波数範囲のかなりの部分に対して、ゼロのスペクトル係数またはゼロに近いスペクトル係数を導入する。したがって、主に非ゼロのデータに対して使用される同一のエントロピーコーダを適用するというよりは、むしろ、（すなわち、図５の符号器とコードブック）、代わりにＲＬＥベースのエントロピーコーダを使用する。
【００６７】
ＲＬＥベースのエントロピー符号器のためのコードブックを構成するため、非ゼロのスペクトルサンプルの絶対値が整数セットＬｉ＝｛１，２，３．．．，Ｌｎ｝を形成するものとし、ここでＬｎは、Ｌｎに等しい、またはそれより大きい任意の値を表す。入力ストリーム内のゼロのスペクトルサンプルのランレングスが、別のセットＲｊ＝｛１，２，３．．．，Ｒｍ｝を形成し、Ｒｍが、Ｒｍに等しい、またはそれより長い長さを有する任意のゼロの連続を表すものとする。この表記を使用して、（Ｒｉ，Ｌｉ）として定義された入力記号のストリングを有する入力スペクトルを表すことができ、これは、Ｒｉ個のゼロのスペクトルサンプルに対応し、その後にＬｉ（すなわち、エントロピー符号器を使用して符号化した記号）が続く。
【００６８】
図５以下に関して述べたとおり、コードブックを構成する上での第１ステップは、すべての入力イベントの確率を集めることである。この場合、入力は、定義されたしきい値に対して調整され、したがって、確率は、すべての１＜＝ｉ＜＝ｎかつ１＜＝ｊ＜＝ｍについて、（Ｒｉ，Ｌｉ）に対して決定される。これらの確率は、図１３で、図示されており、そこでより暗い正方形（例えば、８０６、８０８）は、より高い確率を有するイベントに対応し、より明るい正方形（例えば、８１０、８１２）は、低い確率またはゼロに近い確率を有する。すべての高い確率の入力構成は、まとめて範囲８００と呼び、すべての低い確率の構成は、範囲８０２と呼んでいる。すべての低い確率の組合せは、コードブックから除外する。確率しきい値８０４は、仕切りより下のすべての値がゼロにセットされてコードブックから除外されるように定義する。残りのしきい値を上回る構成には、その確率に反比例する長さを有するエントロピー型符号を割り当てる。量子化されたオーディオデータの場合、高い振幅の入力は、低い確率を有する。したがって、それらはしきい値を下回り、コードブックから除外される（ただし、それらはエスケープさせて、符号化済みビットストリーム内に入れることが可能である）。
【００６９】
第２符号器を使用してエントロピー符号化出力をインターリーブするため、特別エントロピーコードブック符号をリザーブして、除外されたイベント（例えば、ＲＬＥ符号化されたデータ）をマーク解除（ｄｅｍａｒｋ）する。符号化時に、スペクトルサンプル（入力記号）を可能なイベントのリストと比較し、マッチ（対応）が見つかった場合（例えば、可変−可変符号器を使用している場合、コードブックを表すのに使用するツリー、テーブル、ハッシュ構造またはそれに相当するものの中で）、対応するエントロピー型符号が出力されて、その後に符号ビットが続く。
【００７０】
マッチが見つからなかった場合、エスケープ符号が送信され、その後にイベントを識別するのに必要な情報、すなわち、データのＲＬＥ符号化に関する情報が続く。Ｎ個のゼロで終了する入力スペクトルの場合、明示的（特別）終了信号が必要とされるか、あるいは、復号器が、サンプルの総数を知っており、限界が越えられたとき、復号化を停止することができるので、（Ｎ，１）などの特別イベントで十分であるかのいずれかである。
【００７１】
復号化のためには、しきい値格子は必要ない。というのは、この格子は、コードブックエントリを淘汰するのに使用するからである。本明細書で開示した復号化方法は、説明のとおり生成した図１３のコードブックとともに使用することができる。
【００７２】
図１４は、図５により導出したコードブックの量子化されたデータに対する適用を介する、図２のエントロピー符号器２０８を実施するための一方法を示している。（可変−可変符号化方法は、一般的に、他の型のデータを符号化するのに適用可能であることに留意されたい。）図示するとおり、量子化されたデータは、図２のエントロピー符号器に対する入力として受信される９００。この入力は、何らかの形式の離散信号またはデータパケットになっており、議論を単純にするため、すべての入力は、長いシリーズの離散記号であると想定されるものと理解する。受信された入力９００は、図５のコードブック内で対応するコードブックキーを探し出すために走査する９０２。こうした走査は、データルックアップに対応し、コードブックを実施するのに、どのようにデータ構造が使用されるかに応じて、ルックアップの正確な方法は異なる。
【００７３】
符号器のコードブックを記憶して、操作するのに利用可能な、様々な技法が存在することに留意されたい。例えば、可変−可変コードブックのための１つの構造は、記号グループがツリー構造の走査をガイドするＮ進（例えば、２進、３進など）ツリーの走査およびストレージである。ツリーのリーフノードに対するパスは、認識済みの記号シーケンスの終了を表し、そこでエントロピー型符号が、そのシーケンスと関連付けられる。（コードクックは、テーブルエントリが、入力シーケンス全体、例えば、ノードに対するパスを含んだテーブルとして実施できることに留意されたい。）ノードは、ソフトウェア内で、そのノードと関連付けられた１つまたは複数の記号、および対応するエントロピー型符号の関連９０６のストレージを可能にする構造、クラス定義、または他の構造として符号化することが可能である。
【００７４】
または、ＲＬＥ符号器の場合、そのコードブックは、永久ストレージ内に２次元格子として記憶することができ、データのリトリーブは、２つの指標を識別することによって実行される。したがって、ランレングスと特定の記号値の指定によって、テーブルエントリをリトリーブすることができる。復号化テーブルは、ハフマンツリーとして実施することが可能である。別のコードブック実施形態は、Ｒｉｃｅ−Ｇｏｌｏｍｂ構造およびそれに相当するものを含む。
【００７５】
明示的に図示していないが、図２に関連して述べたとおり、復号化は、符号化の逆操作として機能し、元の入力周波数係数９００の近似を生成するために、符号化済みデータ９０８が復号化コードブック内でルックアップされる９０６。
【００７６】
私の発明の原理を図示した実施形態との関連で説明し、図示してきたが、そのような原理を逸脱することなく、この図示した実施形態の構成および詳細を変更できることが理解されよう。したがって、頭記の特許請求の範囲およびそれに相当するものの範囲および趣旨内に入る得るすべてのそのような変更は、本発明として請求する。
【図面の簡単な説明】
【図１】  エントロピー符号モードスイッチングを使用する周波数領域オーディオ符号化および復号化を実施するのに使用することが可能なコンピュータシステムのブロック図である。
【図２】  周波数領域オーディオコーダ内でのオーディオデータの符号化および復号化を示すフローチャートである。
【図３】  オーディオに応じて分割された周波数範囲を図示する図である。
【図４】  エントロピー符号化モードスイッチングを使用するを図示する図である。
【図５】  可変長記号グループに対する可変長エントリを有するコードブックの作成を示すフローチャートである。
【図６】  英文字｛Ａ，Ｂ，Ｃ｝に対する、図５に準ずるコードブックの作成を示す図である。
【図７】  英文字｛Ａ，Ｂ，Ｃ｝に対する、図５に準ずるコードブックの作成を示す図である。
【図８】  英文字｛Ａ，Ｂ，Ｃ｝に対する、図５に準ずるコードブックの作成を示す図である。
【図９】  英文字｛Ａ，Ｂ，Ｃ｝に対する、図５に準ずるコードブックの作成を示す図である。
【図１０】  英文字｛Ａ，Ｂ，Ｃ｝に対する、図５に準ずるコードブックの作成を示す図である。
【図１１】  英文字｛Ａ，Ｂ，Ｃ｝に対する、図５に準ずるコードブックの作成を示す図である。
【図１２】  英文字｛Ａ，Ｂ，Ｃ｝に対する、図５に準ずるコードブックの作成を示す図である。
【図１３】  反復するスペクトル係数を有するオーディオシーケンスを符号化するのに使用するスペクトルしきい値格子を図示する図である。
【図１４】  図２のエントロピー符号器の実施を図示する図である。
【図１】
0004786796.tif 000003
【図２】
0004786796.tif 000004
【図３】
0004786796.tif 000005
【図４】
0004786796.tif 000006
【図５】
0004786796.tif 000007
【図６】
0004786796.tif 000008
【図７】
0004786796.tif 000009
【図８】
0004786796.tif 000010
【図９】
0004786796.tif 000011
【図１０】
0004786796.tif 000012
【図１１】
0004786796.tif 000013
【図１２】
0004786796.tif 000014
【図１３】
0004786796.tif 000015
【図１４】
0004786796.tif 000016