(57)【要約】  データのグループ内の最大絶対値（ＬＡＶ）を判定する。ＬＡＶに基づいて、データのグループのために最適なハフマンコードブックを選択するために用いられる差分テーブルを特定する。差分テーブルは、複数のハフマンコードブックのうちの２つに関連する。複数のハフマンコードブックのうちの２つに関連する式を用いて、データのグループの１つ以上のインデクスを算出し、１つ以上のインデクス及び差分テーブルを用いてデータのグループのサイズ差分値を判定する。判定されたサイズ差分値に基づいて、複数のハフマンコードブックのうちの２つのうちの１つを選択する。
2007510170.tif 000002
【特許請求の範囲】
【請求項１】
データのグループ内の最大絶対値（ＬＡＶ）を判定するステップと、
上記ＬＡＶに基づいて、複数のハフマンコードブックのうちの２つに関連し、上記データのグループのために最適なハフマンコードブックを選択するために用いられる差分テーブルを特定するステップと、
上記複数のハフマンコードブックのうちの２つに関連する式を用いて、上記データのグループの１つ以上のインデクスを算出するステップと、
上記１つ以上のインデクス及び上記差分テーブルを用いて上記データのグループのサイズ差分値を判定するステップと、
上記判定されたサイズ差分値に基づいて、上記複数のハフマンコードブックのうちの２つのうちの１つを選択するステップとを有するコードブック選択方法。
【請求項２】
上記別個の複数のハフマンコードブックのうちの２つにそれぞれ関連する複数の差分テーブルを作成するステップを更に有する請求項１記載のコードブック選択方法。
【請求項３】
上記それぞれの複数の差分テーブルの各エントリは、上記別個の複数のハフマンコードブックのうちの２つにおける対応するコード長エントリの間の差分である長さ差分値を含むことを特徴とする請求項２記載のコードブック選択方法。
【請求項４】
上記データのグループは、量子化されたスペクトル係数の１つ以上のｎ−タプルを含むセクションであることを特徴とする請求項１記載のコードブック選択方法。
【請求項５】
上記差分テーブルは、上記ＬＡＶ及び上記差分テーブルとの間の予め定義された対応関係に基づいて特定されることを特徴とする請求項１記載のコードブック選択方法。
【請求項６】
上記予め定義された対応関係は、上記複数のハフマンコードブックのうちの関連する２つが、上記ＬＡＶを有するデータのグループの最適のコードブックである可能性を有することを示す統計情報に基づいて判定されることを特徴とする請求項５記載のコードブック選択方法。
【請求項７】
上記データのグループのサイズ差分値を判定するステップは、
上記１つ以上のインデクスのそれぞれについて、上記差分テーブルから対応するエントリを検索するステップと、
上記検索したエントリを合計し、上記データのグループのサイズ差分値を判定するステップとを有することを特徴とする請求項１記載のコードブック選択方法。
【請求項８】
上記決定されたサイズ差分値が０より大きいか否かに基づいて、上記複数のハフマンコードブックのうちの２つのうちの１つを選択することを特徴とする請求項１記載のコードブック選択方法。
【請求項９】
上記複数のハフマンコードブックは、１１個のハフマンコードブックであり、上記差分テーブルは、５個の差分テーブルのうちの１つであることを特徴とする請求項１記載のコードブック選択方法。
【請求項１０】
上記５個の差分テーブルは、上記１１個のハフマンコードブックにおける第１及び第２のハフマンコードブックに関連する第１の差分テーブルと、上記１１個のハフマンコードブックにおける第３及び第４のハフマンコードブックに関連する第２の差分テーブルと、上記１１個のハフマンコードブックにおける第５及び第６のハフマンコードブックに関連する第３の差分テーブルと、上記１１個のハフマンコードブックにおける第７及び第８のハフマンコードブックに関連する第４の差分テーブルと、上記１１個のハフマンコードブックにおける第９及び第１０のハフマンコードブックに関連する第５の差分テーブルとからなることを特徴とする請求項９記載のコードブック選択方法。
【請求項１１】
上記複数のハフマンコードブックのうちの２つに関連する式は、乗算を含まないことを特徴とする請求項１記載のコードブック選択方法。
【請求項１２】
プロセッサにより実行されて、該プロセッサにコードブック選択方法を実行させる命令を提供するコンピュータにより読取可能な媒体において、該コードブック選択方法は、
データのグループ内の最大絶対値（ＬＡＶ）を判定するステップと、
上記ＬＡＶに基づいて、複数のハフマンコードブックのうちの２つに関連し、上記データのグループのために最適なハフマンコードブックを選択するために用いられる差分テーブルを特定するステップと、
上記複数のハフマンコードブックのうちの２つに関連する式を用いて、上記データのグループの１つ以上のインデクスを算出するステップと、
上記１つ以上のインデクス及び差分テーブルを用いて上記データのグループのサイズ差分値を判定するステップと、
上記判定されたサイズ差分値に基づいて、上記複数のハフマンコードブックのうちの２つのうちの１つを選択するステップとを有するコンピュータにより読取可能な媒体。
【請求項１３】
上記コードブック選択方法は、上記別個の複数のハフマンコードブックのうちの２つにそれぞれ関連する複数の差分テーブルを作成するステップを更に有することを特徴とする請求項１２記載のコンピュータにより読取可能な媒体。
【請求項１４】
上記データのグループは、量子化されたスペクトル係数の１つ以上のｎ−タプルを含むセクションであることを特徴とする請求項１２記載のコンピュータにより読取可能な媒体。
【請求項１５】
上記差分テーブルは、上記ＬＡＶ及び上記差分テーブルとの間の予め定義された対応関係に基づいて特定されることを特徴とする請求項１２記載のコンピュータにより読取可能な媒体。
【請求項１６】
メモリと、
上記メモリに接続された、少なくとも１つのプロセッサとを備えるコンピュータシステムにおいて、
上記少なくとも１つのプロセッサは、一連のインストラクションを実行することにより、
データのグループ内の最大絶対値（ＬＡＶ）を判定し、
上記ＬＡＶに基づいて、複数のハフマンコードブックのうちの２つに関連し、上記データのグループのために最適なハフマンコードブックを選択するために用いられる差分テーブルを特定し、
上記複数のハフマンコードブックのうちの２つに関連する式を用いて、上記データのグループの１つ以上のインデクスを算出し、
上記１つ以上のインデクス及び差分テーブルを用いて上記データのグループのサイズ差分値を判定し、
上記判定されたサイズ差分値に基づいて、上記複数のハフマンコードブックのうちの２つのうちの１つを選択するコンピュータシステム。
【請求項１７】
上記少なくとも１つのプロセッサは、一連のインストラクションを実行することにより、
更に、上記別個の複数のハフマンコードブックのうちの２つにそれぞれ関連する複数の差分テーブルを作成することを特徴とする請求項１６記載のコンピュータシステム。
【請求項１８】
上記データのグループは、量子化されたスペクトル係数の１つ以上のｎ−タプルを含むセクションであることを特徴とする請求項１６記載のコンピュータシステム。
【請求項１９】
上記差分テーブルは、上記ＬＡＶ及び差分テーブルとの間の予め定義された対応関係に基づいて特定されることを特徴とする請求項１６記載のコンピュータシステム。
【請求項２０】
それぞれが２つの複数のハフマンコードブックに関連する１組の差分テーブルと、
データのグループ内の最大絶対値（ＬＡＶ）を判定し、上記ＬＡＶに基づいて、複数のハフマンコードブックのうちの２つに関連し、上記データのグループのために最適なハフマンコードブックを選択するために用いられる差分テーブルを特定し、上記複数のハフマンコードブックのうちの２つに関連する式を用いて、上記データのグループの１つ以上のインデクスを算出し、上記１つ以上のインデクス及び差分テーブルを用いて上記データのグループのサイズ差分値を判定し、上記判定されたサイズ差分値に基づいて、上記複数のハフマンコードブックのうちの２つのうちの１つを選択するハフマン符号化モジュールとを備える符号化装置。
【請求項２１】
上記データのグループは、量子化されたスペクトル係数の１つ以上のｎ−タプルを含むセクションであることを特徴とする請求項２０記載の符号化装置。
【請求項２２】
上記差分テーブルは、上記ＬＡＶ及び上記差分テーブルとの間の予め定義された対応関係に基づいて特定されることを特徴とする請求項２０記載の符号化装置。
【請求項２３】
データのグループ内の最大絶対値（ＬＡＶ）を判定する判定手段と、
上記ＬＡＶに基づいて、複数のハフマンコードブックのうちの２つに関連し、上記データのグループのために最適なハフマンコードブックを選択するために用いられる差分テーブルを特定する特定手段と、
上記複数のハフマンコードブックのうちの２つに関連する式を用いて、上記データのグループの１つ以上のインデクスを算出する算出手段と、
上記１つ以上のインデクス及び差分テーブルを用いて上記データのグループのサイズ差分値を判定する判定手段と、
上記判定されたサイズ差分値に基づいて、上記複数のハフマンコードブックのうちの２つのうちの１つを選択する選択手段とを備えるコードブック選択装置。
【請求項２４】
回路の記述を保存するマシンにより読取可能な媒体において、
上記回路は、
それぞれが２つの複数のハフマンコードブックに関連する１組の差分テーブルと、
データのグループ内の最大絶対値（ＬＡＶ）を判定し、上記ＬＡＶに基づいて、複数のハフマンコードブックのうちの２つに関連し、上記データのグループのために最適なハフマンコードブックを選択するために用いられる差分テーブルを特定し、上記複数のハフマンコードブックのうちの２つに関連する式を用いて、上記データのグループの１つ以上のインデクスを算出し、上記１つ以上のインデクス及び差分テーブルを用いて上記データのグループのサイズ差分値を判定し、上記判定されたサイズ差分値に基づいて、上記複数のハフマンコードブックのうちの２つのうちの１つを選択するハフマン符号化モジュールとを含むマシンにより読取可能な媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、オーディオ符号化に関する。詳しくは、本発明は、デジタルデータの符号化のための最適なハフマンコードブックの選択に関する。
【著作権表示／許諾】
【０００２】
この明細書の開示内容の一部は、著作権保護の対象となるマテリアルを含む。著作権所有者は、この明細書が特許商標庁への特許出願であると認められるファックスコピーに対しては異議を唱えないが、この他のあらゆる全ての著作権を主張する。以下の表示は、後述するソフトウェア及びデータ、並びに添付の図面に適用される。：著作権（ｃ）２００１：全ての著作権はソニーエレクトロニクスインク社に帰属する（Copyright (c) 2001, Sony Electronics, Inc., All Rights Reserved）。
【背景技術】
【０００３】
近年の効率的なオーディオ信号圧縮法は、ハフマン符号化法を用いて、量子化されたオーディオ信号のスペクトルデータを符号化する。標準化組織であるモーションピクチャエキスパートグループ（Motion Picture Experts Group：ＭＰＥＧ）は、例えば、ＭＰＥＧ−２アドバンスドオーディオ符号化（advanced audio coding：ＡＡＣ）規格（ＩＳＯ／ＩＥＣ１３８１８−７参照）及びＭＰＥＧ−４ＡＡＣ規格（ＩＳＯ／ＩＥＣ１４４９６−３参照）等の仕様書において、データ圧縮方法を開示している。本明細書では、これらの規格を総称的にＭＰＥＧ規格と呼ぶ。
【０００４】
ＭＰＥＧ規格では、入力パルスコード変調（pulse code modulationＰＣＭ）信号を、修正離散コサイン変換（ＭＤＣＴ）処理により、周波数スペクトルデータの１０２４個の要素に変換し、非線型量子化法を用いて量子化（整数に変換）する。そして、量子化された周波数スペクトルデータの１０２４個の要素は、複数の換算係数帯域（scale factor band：ＳＦＢ）にグループ化される。各ＳＦＢは、２又は４の倍数個の量子化されたスペクトル係数を含む。また、ＳＦＢは、複数のセクションにグループ化することもできる。
【０００５】
次に、量子化され、グループ化された周波数スペクトルデータは、ハフマン符号化される。ハフマン符号化処理は、ハフマンコードブックに基づいて実行される。各セクションは、ＭＰＥＧ規格が提供する１１個のハフマンコードブックから選択された単一のハフマンコードブックを用いて符号化される。各ハフマンコードブックは、符号化されるデータアイテムのインデクス、対応する「コードワード」（符号化されたデータアイテムの１６進表示）及び各コードワードのコード長に関する情報を含む。
【０００６】
ＭＰＥＧ規格では、セクションについて選択できるハフマンコードブックは、セクション内のスペクトルデータの最大絶対値（ＬＡＶ）により制限される。すなわち、スペクトルデータのＬＡＶは、セクションに用いることができるハフマンコードブックに関連するＬＡＶより小さくなければならない。ＭＰＥＧ規格では、セクション内のスペクトルデータのＬＡＶが２未満である場合、候補ハフマンコードブックは、コードブック０、１、２である。また、セクション内のスペクトルデータのＬＡＶが３未満である場合、候補ハフマンコードブックは、コードブック０〜４である。また、セクション内のスペクトルデータのＬＡＶが５未満である場合、候補ハフマンコードブックは、コードブック０〜６である。また、セクション内のスペクトルデータのＬＡＶが８未満である場合、候補ハフマンコードブックは、コードブック０〜８である。また、セクション内のスペクトルデータのＬＡＶが１３未満である場合、候補ハフマンコードブックは、コードブック０〜１０である。また、セクション内のスペクトルデータのＬＡＶが１３以上である場合、候補ハフマンコードブックは、コードブック０〜１１である。
【０００７】
候補ハフマンコードブックが選択されると、各候補ハフマンコードブックでデータを符号化した場合のコード長が判定され、この結果が比較される。そして、そのセクションのスペクトルデータのハフマン符号化のために、コード長がより短くなる候補ハフマンコードブックが選択及び使用される。
【０００８】
上述した、セクションに最適なハフマンコードブックを選択する従来の手法は、各候補ハフマンコードブックについて、インデクスを算出し、対応するコード長を得る処理を別々に実行しなければならず、演算負荷が大きい。
【発明の開示】
【課題を解決するための手段】
【０００９】
データのグループ内の最大絶対値（ＬＡＶ）を判定する。ＬＡＶに基づいて、複数のハフマンコードブックのうちの２つに関連し、データのグループのために最適なハフマンコードブックを選択するために用いられる差分テーブルを特定する。複数のハフマンコードブックのうちの２つに関連する式を用いて、データのグループの１つ以上のインデクスを算出し、１つ以上のインデクス及び差分テーブルを用いてデータのグループのサイズ差分値を判定する。判定されたサイズ差分値に基づいて、複数のハフマンコードブックのうちの２つのうちの１つを選択する。
【００１０】
本発明は、以下の詳細な説明及び本発明の様々な実施形態を示す添付の図面によって、より明瞭になるが、これらは、本発明を説明するために本発明を例示的に示すものであり、本発明は、特定の実施形態に制限されるものではない。
【発明を実施するための最良の形態】
【００１１】
以下、添付の図面を用いて、本発明の実施例を詳細に説明する。添付の図面においては、類似する要素には、類似する参照符号を付す。添付の図面は、本発明を実現する特定の実施例を例示的に示している。これらの実施例については、当業者が本発明を実施することができるよう、詳細に説明するが、この他の実施例も可能であり、本発明の範囲から逸脱することなく、論理的、機械的、電気的、機能的及びこの他の変更を行うことができる。したがって、以下の詳細な説明は、限定的には解釈されず、本発明の範囲は、添付の請求の範囲によってのみ定義される。
【００１２】
まず、図１に示す符号化装置１００の一実施形態により、本発明の動作の概観について説明する。符号化装置１００は、本明細書では総称的にＭＰＥＧ規格と呼ぶＭＰＥＧ音声符号化規格（例えば、ＭＰＥＧ−２ＡＡＣ規格、ＭＰＥＧ−４ＡＡＣ規格等）に準拠する。符号化装置１００は、フィルタバンクモジュール１０２と、符号化ツール１０４と、心理音響モデラ１０６と、量子化モジュール１１０と、ハフマン符号化モジュール１１４とを備える。
【００１３】
フィルタバンクモジュール１０２は、パルスコード変調（pulse code modulation：ＰＣＭ）信号を受信し、窓関数を用いてこれを変調し、修正離散コサイン変換（modified discrete cosine transform：ＭＤＣＴ）処理を実行する。窓関数は、解析される信号を時間的に拡張し、周波数分解能を向上させるロングウィンドウタイプ及び解析される信号を時間的に縮小し、時間分解能を向上させるショートウィンドウタイプの２つのタイプのウィンドウを用いて信号を処理する。ロングウィンドウタイプは、安定した信号のみが存在する場合に使用され、ショートウィンドウタイプは、急速な信号変化がある場合に使用される。解析される信号の特性に基づくこれらの２つのタイプの処理を用いることによって、時間分解能が不十分な場合に生じるプレエコーと呼ばれる不快な雑音の発声を防止することができる。ＭＤＣＴ処理は、時間領域信号を周波数スペクトルデータの複数のサンプルに変換する。
【００１４】
符号化ツール１０４は、スペクトル処理の任意のツールのセットを含む。例えば、符号化ツール１０４は、予測符号化を実行するためのゆらぎ雑音シェーピング（temporal noise shaping：ＴＮＳ）ツール及び予測ツールを含む。ＴＮＳツールを用いて、変換の各ウィンドウ内で雑音の時間的なシェープを制御し、プレエコー問題を解決することができる。また、予測ツールを用いて、サンプル間の相関性を排除することができる。
【００１５】
心理音響モデラ１０６は、サンプルを分析し、聴覚マスキング曲線を決定する。聴覚マスキング曲線は、各サンプルに重畳しても、人間の耳には聞こえない雑音の最大レベルを示す。ここで、人間の耳に聞き取られるレベルは、人間の聴覚の心理音響モデルに基づいて判定される。聴覚マスキング曲線は、望ましい雑音スペクトルの推定値として機能する。
【００１６】
量子化モジュール１１０は、最適な換算係数を用いてサンプルを量子化する（また、量子化器とも呼ばれる）。最適な換算係数は、レートコントローラ１０８及び歪みコントローラ１１２を用いて決定される。レートコントローラ１０８は、必要なビットレートに基づいてレートを制御し、歪みコントローラ１１２は、心理音響モデラ１０６が提供するマスキング曲線によって定義される望ましい雑音スペクトルに基づいて歪みを制御する。この結果得られる量子化されたスペクトル係数は、換算係数帯域（scalefactor band：ＳＦＢ）にグループ化される。各ＳＦＢは、同じ量子化器を用いて得られた係数を含む。一実施形態においては、各ＳＦＢは、４の倍数個の量子化されたスペクトル係数を含む。
【００１７】
ハフマン符号化モジュール１１４は、量子化されたスペクトル係数の各グループに最適なハフマンコードブックを選択し、この最適なハフマンコードブックを用いてハフマン符号化処理を実行する。これにより得られる可変長符号（variable length code：ＶＬＣ）及び符号化で用いられるコードブックを特定するデータ（及び必要であれば他の情報）を統合して、ビットストリームを生成する。
【００１８】
一実施形態においては、ＭＰＥＧ規格は、選択可能な１１個のハフマンコードブックを提供する。各ハフマンコードブックは、符号化されるデータアイテムのインデクス、対応する「コードワード」（符号化されたデータアイテムの１６進表示）及び各コードワードのコード長に関する情報を含む。スペクトルデータのグループのために選択できる候補ハフマンコードブックは、グループ内のスペクトルデータの最大絶対値（largest absolute value：ＬＡＶ）によって制限される。すなわち、スペクトルデータのＬＡＶは、セクションに用いることができる候補ハフマンコードブックに関連するＬＡＶより小さくなければならない。この結果、データのグループについて最適のコードブックを選択するために使用される候補ハフマンコードブックの数は、データのグループ内のＬＡＶに基づき、ＬＡＶが２未満の場合の２つの候補コードブックから、ＬＡＶが１３以上の場合の１１個の候補コードブックまで、様々である。
【００１９】
後により詳細に説明するように、ハフマン符号化モジュール１１４は、１組の差分テーブルを作成し、これらの差分テーブルのコンテンツを予め算出し、ハフマン符号化処理において使用するためにこれらをメモリに保存することにより、データのグループの候補ハフマンコードブックの数を２個に制限する。各差分テーブルは、２個の別個のハフマンコードブックに関連する。一実施形態においては、差分テーブルの各エントリは、差分テーブルに関連する２つのハフマンコードブックからの対応するコード長エントリ間の差分である長さ差分値（length difference value）を含む。
【００２０】
以下、ハフマン符号化モジュール１１４における処理の利点を明らかにするために、従来のコードブック選択法について説明する。
【００２１】
図２はＭＰＥＧ規格が提供するハフマンコードブックのパラメータを示すテーブル２００を示している。
【００２２】
図２に示すように、テーブル２００は、コードブック番号情報２０２、サイン情報２０４、コードブック次元（dimension）情報２０６、コードブックＬＡＶ情報２０８及びコードブックテーブル情報２１０を含んでいる。コードブック次元情報２０６は、ハフマンコードブックが、量子化されたスペクトル係数の２又は４個で１組（2- or 4-tuples：以下、２−タプル又は４−タプルという）を符号化するか否かを示す。コードブックサイン情報２０４は、ハフマンコードブックが、符号付きのスペクトルデータ（例えば、ｕｎｓｉｇｎｅｄ＿ｃｂ［ｉ］＝０）又は、符号なしのスペクトルデータ（例えば、ｕｎｓｉｇｎｅｄ＿ｃｂ［ｉ］＝１）を表現できるか否かを示す。符号なしのコードブックが選択された場合、データのグループ内の０ではない各係数についてコードブックから抽出されたコードワードの直後に符号ビットを設ける。
【００２３】
データのグループは、ＳＦＢ又はセクションであってもよい。セクションは、単一のハフマンコードブックで表される１つ以上のＳＦＢから構成される。
【００２４】
図３は、従来のコードブック選択方法３００のフローチャートである。コードブック選択方法３００は、まず、データのグループ内のＬＡＶに基づいて、データのグループの全ての候補コードブックを検出する（処理ステップ３０２）。テーブル２００に示すように、グループ内のＬＡＶが２未満である場合、候補ハフマンコードブックは、コードブック０、１、２である。グループ内のＬＡＶが３未満である場合、候補ハフマンコードブックは、コードブック０〜４である。グループ内のＬＡＶが５未満である場合、候補ハフマンコードブックは、コードブック０〜６である。グループ内のＬＡＶが８未満である場合、候補ハフマンコードブックは、コードブック０〜８である。グループ内のＬＡＶが１３未満である場合、候補ハフマンコードブックは、コードブック０〜１０である。そして、グループ内のＬＡＶが１３以上である場合、候補ハフマンコードブックは、コードブック０〜１１である。
【００２５】
次に、処理のために、候補コードブックから第１のコードブックを選択する（処理ステップ３０４）。
【００２６】
処理ステップ３０６において、テーブル２００内の選択されたコードブックの次元を確認し、このコードブックが係数の２−タプル又は４−タプルを符号化するかを判定し、これに応じて、データのグループ内の係数の２−タプル又は４−タプルを特定する。
【００２７】
処理ステップ３０８においては、選択されたコードブックに関連する式を用いて、これらの係数の２−タプル又は４−タプルのコードブックインデクスを算出する。ＭＰＥＧ規格では、コードブックインデクスを算出するための式は以下の通りである。
（ａ）コードブック１、２の場合
codebook_index=27*C[i]+9*C[i+1]+3*C[i+2]+C[i+3]+46
（ｂ）コードブック３、４の場合
codebook_index=27*abs(C[i])+9*abs(C[i+1])+3*abs(C[i+2])+abs(C[i+3])
（ｃ）コードブック５、６場合
codebook_index=9*C[i]+C[i+1]+40
（ｂ）コードブック７、８の場合
codebook_index=8*abs(C[i])+abs(C[i+1])
（ｂ）コードブック９、１０の場合
codebook_index=13*abs(C[i])+abs(C[i+1])
ここで、Ｃ［ｉ］、Ｃ［ｉ＋１］、Ｃ［ｉ＋２］及びＣ［ｉ＋３］は、データのグループ内の量子化されたスペクトル係数の値である。
【００２８】
データのグループ内のＬＡＶが１２以上である場合、コードブックインデクスを算出するための式は、以下の通りである。
（ａ）ａｂｓ（Ｃ［ｉ］）≧１６及びａｂｓ（Ｃ［ｉ＋１］）≧１６の場合
codebook_index=272+abs(C[i]) 
（ｂ）ａｂｓ（Ｃ［ｉ］）≧１６及びａｂｓ（Ｃ［ｉ＋１］）＜１６の場合
codebook_index=17*abs(C[i])+16
（ｃ）ａｂｓ（Ｃ［ｉ］）＜１６及びａｂｓ（Ｃ［ｉ＋１］）≧１６の場合
codebook_index=17*abs(C[i])+abs(C[i+1])
上の式の１つを用いてインデクスを算出した後、このインデクスを用いて、選択されたコードブックにアクセスし、対応するコードワード長を得る（処理ステップ３１０）。そして、このコードワード長をこのコードブックのために累積されている総データ長値（初期的には０に設定されている。）に加算する（処理ステップ３１２）。
【００２９】
次に、グループ内に未処理の係数の２−タプル又は４−タプルが残っているかの判定を行う（判定ステップ３１４）。これに該当する場合、次の係数の２−タプル又は４−タプルを特定し（処理ステップ３１６）、コードブック選択方法３００は、処理ステップ３０８に戻る。グループ内の全ての係数を処理すると、コードブック選択方法３００は、候補コードブックから次の未検査のコードブックを選択し（処理ステップ３２０）、ステップ３０６〜３１４の処理を繰り返す。これらのステップの処理は、全ての候補コードブックが検査されるまで繰り返される（判定ステップ３１８）。そして、候補コードブックについて累積された総データ長値を比較し（処理ステップ３２２）、コードワードが最も短くなるコードブックをこのスペクトルデータのグループについて最適のコードブックとして選択する（処理ステップ３２４）。
【００３０】
このようにして上述した従来の手法は、各候補者コードブックテーブルについて、処理ステップ３０６〜３１８を繰り返し、したがって、最大１１回、処理を繰り返す。
【００３１】
図１のハフマン符号化モジュール１１４では、１組の差分テーブルを作成し、これらの差分テーブルのコンテンツを予め算出し、ハフマン符号化処理において使用するためにこれらをメモリに保存することにより、これらの繰返しを省略できる。上述のように、各差分テーブルは、２つの別個のハフマンコードブックに関連する。例えば、差分テーブル１は、コードブック１、２に関連し、差分テーブル２は、コードブック３、４に関連し、差分テーブル３は、コードブック５、６に関連し、差分テーブル４は、コードブック７、８に関連し、差分テーブル５は、コードブック９、１０に関連する。一実施形態においては、差分テーブルの各エントリは、差分テーブルに関連する２つのハフマンコードブックからの対応するコード長エントリ間の差分である長さ差分値（length difference value）を含む。
【００３２】
図４及び図５は、図１のハフマン符号化モジュール１１４が実行できるコードブック選択処理の２つの実施形態のフローチャートである。この処理は、ハードウェア（例えば回路、専用ロジック等）、ソフトウェア（汎用コンピュータシステム又は専用マシン上で実行されるソフトウェア）又はこれらの両方の組合せを含む処理ロジックによって実行してもよい。ソフトウェアによって実現できる処理については、これらのフローチャートを用いて本発明を説明することにより、当業者は、適切に構成されたコンピュータによってこの処理を実行するための命令を含むプログラムを開発することができる（コンピュータのプロセッサは、メモリを含むコンピュータにより読取可能な媒体から命令を読み出し、実行する）。コンピュータにより実行可能な命令は、コンピュータプログラミング言語として書いてもよく、ファームウェアロジックとして実現してもよい。一般的に認知されている規格に準拠するプログラミング言語で書いた場合、このような命令は、様々なオペレーティングシステムにインタフェースされ、様々な種類のハードウェアプラットホームで実行できる。更に、本発明では、如何なる特定のプログラミング言語にも基づくことなく、本発明を説明する。ここに開示する本発明の処理を実現するために、様々なプログラミング言語を用いることができることは明らかである。更に、当分野においては、動作を行い又は結果を生じるものとして、ソフトウェアを様々な呼び方で呼ぶことがある（例えば、プログラム、手続き、プロセス、アプリケーション、モジュール、ロジック等）。これらの表現は、コンピュータによるソフトウェアの実行によって、コンピュータのプロセッサが動作を実行し又は結果を生じるということを単に簡略的に表現しているに過ぎない。また、本発明の範囲から逸脱することなく、図４及び図５に示す処理ステップを省略してもよく、他のステップを追加してもよく、更に、ここで説明する処理ステップの実行順序を変更してもよい。
【００３３】
図４に示すように、処理ロジックは、まず、処理すべきデータのグループ（例えば、ＳＦＢ、セクション等）を特定する（処理ステップ４０２）。次に、処理ロジックは、データのグループ内のＬＡＶを判定し（処理ステップ４０４）、このＬＡＶに基づいて、このデータのグループのために用いる差分テーブルを特定する（処理ステップ４０６）。差分テーブルは、このデータのグループに最適のコードブックの選択において考慮すべき２つの特定のハフマンコードブックに関連する。一実施形態においては、処理ロジックは、ＬＡＶ及び差分テーブルの間の予め定義された対応関係に基づいて、差分テーブルを特定する。一実施形態においては、予め定義された対応関係は、関連する候補ハフマンコードブックを介して判定され、２つの候補コードブックがこのＬＡＶの最適のコードブックであるの可能性が最も高いことを示す統計情報に基づいて、ＬＡＶにリンクされる。他の実施形態においては、処理ロジックは、各コードブック選択処理の間、ＬＡＶ及び差分テーブルの間の対応関係を動的に判定することによって、差分テーブルを特定する。この判定は、先のコードブック選択処理の間に収集された統計情報に基づいて行うことができる。
【００３４】
処理ステップ４０８において、処理ロジックは、２つの候補ハフマンコードブックに関連する式を用いて、データのグループ内のデータ値の第１のｎ個で１組（n-tuples：以下、ｎ−タプルという）のインデクスを算出する。数ｎは、例えば、図２のテーブル２００によって定義される候補ハフマンコードブックの次元に依存する。一実施形態においては、この式は、乗法を含まないように構成され、これにより、インデクス算出処理の速度を高めることができる。一実施形態においては、ハフマンコードブックの異なる対に関連する式は、ＭＰＥＧ規格が提供する式及び差分テーブルを算出及び構造化する際の処理に基づいて導出される。
【００３５】
次に、処理ロジックは、差分テーブルにアクセスし、算出されたインデクスを用いて対応するサイズ差分値を検索し（処理ステップ４１０）、このサイズ差分値を総差分値に加算する（処理ステップ４１２）。
【００３６】
判定ステップ４１４において、処理ロジックは、データのグループが未処理のデータ値のｎ−タプルを含んでいるかを判定する。これに該当する場合、処理ロジックは、データのグループ内で次のｎ−タプルを特定し（処理ステップ４１８）、処理ステップ４１０〜４１４を繰り返す。この処理は、グループ内の全てのデータ値が処理されるまで繰り返される。
【００３７】
更に、処理ロジックは、総差分値に基づいて、２つの候補ハフマンコードブックから、最適なハフマンコードブックを選択する（処理ステップ４１６）。一実施形態においては、処理ロジックは、総差分値が０以上である場合、２つの候補ハフマンコードブックのうちの第１の候補ハフマンコードブックを選択する。この他の場合、処理ロジックは、２つの候補ハフマンコードブックの第２の候補ハフマンコードブックを選択する。
【００３８】
図５は、ＭＰＥＧ企画に準拠するオーディオ符号化のために用いられるコードブック選択処理５００の一実施形態のフローチャートである。ＭＰＥＧ規格は、各セクションについて最適のコードブックを選択するために、１１個のハフマンコードブックを提供する。
【００３９】
図５に示すように、処理ロジックは、まず、処理するセクションを特定する（処理ステップ５０２）。セクションは、１つ以上のＳＦＢを含むことができ、各ＳＦＢは、量子化されたスペクトル係数の複数の４−タプルを含むことができる。
【００４０】
次に、処理ロジックは、セクション内のＬＡＶを判定する（処理ステップ５０４）。
【００４１】
判定ステップ５０６において、処理ロジックは、ＬＡＶが０であるかを判定する。これに該当する場合、処理ロジックは、セクションをハフマン符号化するために、コードブック０を選択する（処理ステップ５０８）。これ以外の場合、処理ロジックは、ＬＡＶが２未満であるかを判定する（判定ステップ５１０）。これに該当する場合、処理ロジックは、ハフマンコードブック１、２に関連する式１を用いて量子化されたスペクトル係数の各ｎ−タプルのインデクスを算出する（処理ステップ５１２）。一実施形態においては、式１は、以下のように定義される。
codebook_index=C[i]<<6+C[i+1]<<4+C[i+2]<<2+C[i+3]+85
次に、処理ロジックは、量子化されたスペクトル係数の各ｎ−タプルのインデクスを用いて、差分テーブル１にアクセスし、対応するビット差分値を得る（処理ステップ５１４）。差分テーブル１の各エントリ（ＤＩＦＦ＿ＴＡＢ＿１）は、コードブック１、２からの対応するコードワードの長さの差分を示す。
【００４２】
処理ステップ５１６において、処理ロジックは、総ビット差分値を判定する。総ビット差分値が０より大きい場合（判定ステップ５１８）、処理ロジックは、コードブック２を選択する（処理ステップ５２０）。この他の場合、処理ロジックは、コードブック１を選択する（処理ステップ５２２）。
【００４３】
処理ロジックは、ＬＡＶが３未満であると判定した場合（判定ステップ５２４）、ハフマンコードブック３、４に関連する式２を用いて量子化されたスペクトル係数の各ｎ−タプルのインデクスを算出する（処理ステップ５２６）。一実施形態においては、式２は、以下のように定義される。
codebook_index=abs(C[i])<<6+abs(C[i+1])<<4+abs(C[i+2])<<2+abs(C[i+3])
次に、処理ロジックは、量子化されたスペクトル係数の各ｎ−タプルのインデクスを用いて、差分テーブル２にアクセスし、対応するビット差分値を得る（処理ステップ５２８）。差分テーブル２の各エントリ（ＤＩＦＦ＿ＴＡＢ＿２）は、コードブック３、４からの対応するコードワードの長さの差分を示す。
【００４４】
処理ステップ５３０において、処理ロジックは、総ビット差分値を判定する。総ビット差分値が０より大きい場合（判定ステップ５３２）、処理ロジックは、コードブック４を選択する（処理ステップ５３４）。この他の場合、処理ロジックは、コードブック３を選択する（処理ステップ５３６）。
【００４５】
処理ロジックは、ＬＡＶが５未満であると判定した場合（判定ステップ５３８）、ハフマンコードブック５、６に関連する式３を用いて量子化されたスペクトル係数の各ｎ−タプルのインデクスを算出する（処理ステップ５４０）。一実施形態においては、式３は、以下のように定義される。
codebook_index=C[i]<<4+C[i+1]+68
次に、処理ロジックは、量子化されたスペクトル係数の各ｎ−タプルのインデクスを用いて、差分テーブル３にアクセスし、対応するビット差分値を得る（処理ステップ５４２）。差分テーブル３の各エントリ（ＤＩＦＦ＿ＴＡＢ＿３）は、コードブック５、６からの対応するコードワードの長さの差分を示す。
【００４６】
処理ステップ５４４において、処理ロジックは、総ビット差分値を判定する。総ビット差分値が０より大きい場合（判定ステップ５４６）、処理ロジックは、コードブック６を選択する（処理ステップ５４８）。この他の場合、処理ロジックは、コードブック５を選択する（処理ステップ５５０）。
【００４７】
処理ロジックは、ＬＡＶが８未満であると判定した場合（判定ステップ５５２）、ハフマンコードブック７、８に関連する式４を用いて量子化されたスペクトル係数の各ｎ−タプルのインデクスを算出する（処理ステップ５５４）。一実施形態においては、式４は、以下のように定義される。
codebook_index=abs(C[i])<<3+abs(C[i+1])
次に、処理ロジックは、量子化されたスペクトル係数の各ｎ−タプルのインデクスを用いて、差分テーブル４にアクセスし、対応するビット差分値を得る（処理ステップ５５６）。差分テーブル４の各エントリ（ＤＩＦＦ＿ＴＡＢ＿４）は、コードブック７、８からの対応するコードワードの長さの差分を示す。
【００４８】
処理ステップ５５８において、処理ロジックは、総ビット差分値を判定する。総ビット差分値が０より大きい場合（判定ステップ５６０）、処理ロジックは、コードブック８を選択する（処理ステップ５６２）。この他の場合、処理ロジックは、コードブック７を選択する（処理ステップ５６４）。
【００４９】
処理ロジックは、ＬＡＶが１３未満であると判定した場合（判定ステップ５６６）、ハフマンコードブック９、１０に関連する式５を用いて量子化されたスペクトル係数の各ｎ−タプルのインデクスを算出する（処理ステップ５６８）。一実施形態においては、式５は、以下のように定義される。
codebook_index=abs(C[i])<<4+abs(C[i+1])
次に、処理ロジックは、量子化されたスペクトル係数の各ｎ−タプルのインデクスを用いて、差分テーブル５にアクセスし、対応するビット差分値を得る（処理ステップ５７０）。差分テーブル５の各エントリ（ＤＩＦＦ＿ＴＡＢ＿５）は、コードブック９、１０からの対応するコードワードの長さの差分を示す。
【００５０】
処理ステップ５７２において、処理ロジックは、総ビット差分値を判定する。総ビット差分値が０より大きい場合（判定ステップ５７４）、処理ロジックは、コードブック１０を選択する（処理ステップ５７６）。この他の場合、処理ロジックは、コードブック９を選択する（処理ステップ５７８）。
【００５１】
判定ステップ５６６において、ＬＡＶが１３以上であると判定した場合、処理ロジックは、セクションをハフマン符号化するためにコードブック１１を選択する（処理ステップ５８０）。
【００５２】
一実施形態においては、各差分テーブルは、ビット差分値をエントリのリストとして格納する。この結果、算出されたインデクスのそれぞれは、序数（order number）を表し、リスト内のこの序数に関連するエントリを指す。本発明の一実施形態に基づく差分テーブルの構造を図６に示す。
【００５３】
図７は、本発明の一実施形態に基づく差分テーブル１〜５の例示的なコンテンツを示している。
【００５４】
以下に示す図８を参照した説明は、本発明の実施に適したコンピュータハードウェア及び他の操作コンポーネントに関する概要を明らかにするためのものであるが、これは、適用可能な環境を制限するものではない。図８は、コンピュータシステムの一実施形態を示す図１の符号化装置１００又はハフマン符号化モジュール１１４の実現に好適なコンピュータシステムを示している。
【００５５】
コンピュータシステム８４０は、それぞれがシステムバス８６５に接続されたプロセッサ８５０と、メモリ８５５と、入出力装置（input/output capability）８６０とを備える。メモリ８５５は、プロセッサ８５０によって実行されることにより、ここに説明する処理を実現する命令を格納するよう構成されている。更に、メモリ８５５は、ハフマン符号化モジュール１１４によって用いられる１組の差分テーブルを保存するように構成してもよい。入出力装置８６０は、プロセッサ８５０によってアクセス可能なあらゆる種類のストレージ装置を含む、様々な種類の、コンピュータにより読取可能な媒体を含んでいる。なお、「コンピュータにより読取可能な媒体」という用語は、デジタル信号がエンコードされた搬送波をも含むことは、当業者にとって明らかである。コンピュータシステム８４０は、メモリ８５５において実行されるオペレーティングシステムソフトウェアによって制御される。入出力装置８６０及びこれに関連する媒体は、このオペレーティングシステムソフトウェアと、本発明に基づく処理とに関する命令と、アクセスユニットとを格納している。図１に示すハフマン符号化モジュール１１４は、プロセッサ８５０に接続されたそれぞれ独立した要素であってもよく、プロセッサ８５０に接続されたそれぞれ独立した要素であってもよく、プロセッサ８５０によって実行される、コンピュータにより実行可能な命令として実現してもよい。一実施例においては、コンピュータシステム８４０は、インターネットサービスプロバイダ（Internet Service Provider：以下、ＩＳＰという。）の一部であってもよく、或いは、入出力装置８６０を介してＩＳＰに接続され、インターネットを介してアクセスユニットを送受信してもよい。なお、本発明は、インターネットアクセス及びインターネットウェブサイトに限定されるものではなく、直接接続されたコンピュータシステム及びプライベートネットワークに適用してもよいことは明らかである。
【００５６】
なお、コンピュータシステム８４０は、異なるアーキテクチャを有する様々な可能なコンピュータシステムの一例に過ぎないことは明らかである。一般的なコンピュータシステムは、少なくともプロセッサと、メモリと、プロセッサ及びメモリを接続するバスとを備えている場合が多い。なお、本発明は、マルチプロセッサシステム、ミニコンピュータ、メインフレームコンピュータ等を含む、他のコンピュータシステム構成によっても実現できることは当業者にとって明らかである。更に、本発明は、通信ネットワークを介してリンクされたリモートの処理装置によってタスクが実行される分散型コンピュータシステム環境によっても実現することができる。
【００５７】
ハフマン符号化の様々な側面について説明した。ここでは、特定の実施の形態を示したが、ここに示した特定の実施の形態に代えて、同じ目的を達成する如何なる構成を用いてもよいことは当業者にとって明らかである。したがって、本出願は、本発明のあらゆる適応例及び変形例を包含するものとする。
【図面の簡単な説明】
【００５８】
【図１】符号化装置の一実施形態のブロック図である。
【図２】ＭＰＥＧ規格が提供するハフマンコードブックのパラメータを含むテーブルを示す図である。
【図３】従来のコードブック選択方法のフローチャートである。
【図４】図１のハフマン符号化モジュール１１４によって実行されるコードブック選択処理の一実施形態のフローチャートである。
【図５Ａ】ＭＰＥＧ規格に準拠するオーディオ符号化のために用いられるコードブック選択処理の一実施形態のフローチャートである。
【図５Ｂ】ＭＰＥＧ規格に準拠するオーディオ符号化のために用いられるコードブック選択処理の一実施形態のフローチャートである。
【図５Ｃ】ＭＰＥＧ規格に準拠するオーディオ符号化のために用いられるコードブック選択処理の一実施形態のフローチャートである。
【図６】本発明の一実施形態に基づく差分テーブルの構造を示す図である。
【図７】本発明の一実施形態に基づく差分テーブル１〜５の例示的なコンテンツを示す図である。
【図８】本発明の実施形態の実現に適するコンピュータ環境のブロック図である。
【図１】
2007510170.tif 000003
【図２】
2007510170.tif 000004
【図３】
2007510170.tif 000005
【図４】
2007510170.tif 000006
【図５Ａ】
2007510170.tif 000007
【図５Ｂ】
2007510170.tif 000008
【図５Ｃ】
2007510170.tif 000009
【図６】
2007510170.tif 000010
【図７】
2007510170.tif 000011
【図８】
2007510170.tif 000012
【国際調査報告】
2007510170.tif 000013