(57)【要約】オーディオ信号を符号化及び復号化する方法と、かかる方法を実行する装置とが開示される。符号化方法は、符号化されたフレーム中の所与の正弦波成分を、同じフレーム中の他の成分に対して差分的に、又は直接的に、即ち差分符号化なしに符号化する段階を特徴とする。符号化が差分的であるか直接的であるかは、アルゴリズムにより決定される。第１の種類のアルゴリズムは、グラフ理論から導出される方法を用いて最適な結果を与える。計算的にあまり強くない他のアルゴリズムは、反復的な貪欲探索アルゴリズムにより近似的な結果を与える。
2005506581.tif 000002
【特許請求の範囲】
【請求項１】
符号化されたフレーム中の所与の正弦波成分のパラメータを、同じフレーム中の他の成分に対して差分的に、又は、直接的に、即ち差分符号化なしに、符号化する段階を有することを特徴とする、オーディオ信号を符号化する方法。
【請求項２】
パラメータが差分的に符号化されるべきか直接的に符号化されるべきかをアルゴリズムにより決定する段階を含む、請求項１記載の方法。
【請求項３】
前記アルゴリズムは、パラメータが差分的に符号化されるべきか直接的に符号化されるべきかについて最適の決定を行う、請求項２記載の方法。
【請求項４】
前記アルゴリズムは、
（ａ）直接的に及び差分的に量子化された成分の全ての可能な組合せの集合の有向グラフＤを構築し、そこからグラフＧを構築する段階と、
（ｂ）最小の総重みでＧ中の割り当てを決定し、
（ｃ）前記Ｇ中の割り当てから直接的及び差分的符号化の最善の組合せを導出する段階とを含む、請求項２又は３記載の方法。
【請求項５】
前記アルゴリズムは、パラメータが差分的に符号化されるべきか直接的に符号化されるべきかについて近似的な決定を行う、請求項２記載の方法。
【請求項６】
前記アルゴリズムは、反復的な貪欲アルゴリズムである、請求項２又は５記載の方法。
【請求項７】
前記アルゴリズムは、
（ａ）直接的に及び差分的に量子化された成分の全ての可能な組合せの集合の有向グラフＤを構築し、そこからグラフＧを構築する段階と、
（ｂ）グラフＧの頂点ｓ1，．．．，ｓkを添え字の昇順に一回に一つずつ処理する段階と、
（ｃ）ｋ番目の繰り返しにおいて、以前に選択された出辺のない頂点から出発するｓkの入辺及び直接的符号化辺ｓ0ｓkを有する候補辺集合から頂点ｓkの入辺のうちの１つが選択される段階と、
（ｄ）前記集合から、最小の重みを有する辺を選択する段階とを含む、請求項６記載の方法。
【請求項８】
各頂点にちょうど１つの辺が割り当てられるよう最小の総重みを有する２Ｋ−１個の辺の集合のグラフＧ中で最適な組合せを探す段階を含む、請求項１乃至７のうちいずれか一項記載の方法。
【請求項９】
最小の重みを有する辺の集合は、前記割り当て問題を解決するハンガリー法の使用を含む手順によって見つけられる、請求項８記載の方法。
【請求項１０】
最小の重みを有する辺の集合は、前記割り当て問題を解決するための最短増大経路アルゴリズムの使用を含む手順によって見つけられる、請求項８記載の方法。
【請求項１１】
フレーム中の構成要素が差分的に符号化されるか又は直接的に符号化されるかを特定する副次情報を発生する段階を更に含む、請求項１乃至１０のうちいずれか一項記載の方法。
【請求項１２】
所与の正弦波成分のパラメータを符号化する手段を有する、オーディオ信号を符号化する装置であって、
符号化されたフレーム中のパラメータは、同じフレーム中の他の成分に対して差分的に、又は、直接的に、即ち差分符号化なしに符号化されることを特徴とする、装置。
【請求項１３】
請求項１乃至１１のうちいずれか一項記載の方法に従って動作可能な請求項１２記載の符号化装置。
【請求項１４】
所与の正弦波成分のパラメータを有する符号化されたオーディオ信号を復号化する方法であって、
前記パラメータは、同じフレーム中の他の成分に対して差分的に、又は、直接的に、即ち差分符号化なしに、符号化されたフレーム中で符号化されていることを特徴とする方法。
【請求項１５】
前記信号は請求項１乃至１１のうちいずれか一項記載の方法によって符号化されている、請求項１２記載の符号化されたオーディオ信号を復号化する方法。
【請求項１６】
前記符号化された信号中の副次情報は、フレーム中の成分が差分的に復号化されるべきか直接的に復号化されるべきかを決定するべく解釈される、請求項１５記載の方法。
【請求項１７】
符号化されたフレーム中で、同じフレーム中の他の成分に対して差分的に、又は直接的に、即ち差分符号化なしに符号化された所与の正弦波成分のパラメータを含む符号化されたオーディオ信号を復号化する装置。
【請求項１８】
請求項１４乃至１６のうちいずれか一項記載の方法によって動作する請求項１７記載の装置。
【請求項１９】
符号化されたフレーム中で、同じフレーム中の他の成分に対して差分的に、又は直接的に、即ち差分符号化なしに符号化された所与の正弦波成分のパラメータを含む符号化されたオーディオ信号。
【請求項２０】
フレーム中の成分が差分的に符号化されるか直接的に符号化されるかを特定する副次情報を含む、請求項１９記載の符号化されたオーディオ信号。
【請求項２１】
請求項１９又は２０記載の符号化されたオーディオ信号が格納された記憶媒体。
【請求項２２】
符号化されたオーディオ信号を送信又は記録する装置であって、
（ａ）オーディオ信号を取得する入力ユニットと、
（ｂ）前記符号化されたオーディオ信号を取得するよう前記オーディオ信号を符号化する請求項１２又は１３記載の装置と、
（ｃ）前記符号化されたオーディオ信号を送信又は記録する出力ユニットとを有する装置。
【請求項２３】
符号化されたオーディオ信号を受信及び／又は再生する装置であって、
（ａ）前記符号化されたオーディオ信号を受信する入力ユニットと、
（ｂ）復号化されたオーディオ信号を取得するよう前記符号化されたオーディオ信号を復号化する請求項１７又は１８記載の装置と、
（ｃ）前記復号化されたオーディオ信号を出力する出力ユニットとを含む、装置。
【発明の詳細な説明】
【０００１】
本発明は、正弦波モデルパラメータの周波数差分符号化に係る。
【０００２】
近年、低ビットレートオーディオ圧縮に対するモデルに基づくアプローチがますます関心を集めている。一般的には、これらのパラメトリック法は、オーディオ波形を、様々な同時に存在する信号部分、例えば、正弦波部分、ノイズ状部分、及び／又は、遷移部分へと分解する。続いて、各信号部分を示すモデルパラメータが量子化され、符号化され、復号化器へ送信され、復号化器において、量子化された信号部分は再構成された信号を形成するよう合成され加算される。しばしば、オーディオ信号の正弦波部分は、振幅、周波数、及び場合によっては位相パラメータを用いて特定される正弦波モデルを用いて表わされる。殆どのオーディオ信号について、正弦波信号部分は、知覚的にノイズ部分及び遷移部分よりも重要であり、従って、正弦波モデルパラメータを表わすために比較的多くの量の全ビット割当量が割り当てられる。例えば、ティー・エス・ヴァーマ（T.  S.  Verma）及びティー・エイチ・ワイ・メン（T.  H.  Y.  Meng）により、「６ｋｂｐｓ乃至８５ｋｂｐｓのスケーラブルオーディオ符号化器（A  6  kbps  to  85  kbps  scalable  audio  coder）」、Proc.  IEEE  Inst,.  Conf.  Acoust.,  Speech  Signal  Processing,  第８７７−８８０頁、２０００年、に記載の公知のスケーラブルオーディオ符号化器では、利用可能なビットのうちの７０％よりも多くが、正弦波パラメータを表わすのに用いられる。
【０００３】
通常は、正弦波モデルに必要なビットレートを減少するために、時間差分（ＴＤ）符号化法を用いた正弦波パラメータ間のフレーム間相関が利用される。現在信号フレーム中の正弦波成分は、先行フレーム中の量子化された成分に関連付けられ（従って時間・周波数平面上に「トーントラック（tonal  track）」を形成し）、パラメータの差分（differences）が量子化され符号化される。現在フレーム中の成分であって過去の成分とはリンクできないものは、新しいトラックの起点であると考えられ、通常は差分符号化なしに直接的に符号化される。ＴＤ符号化は、変動のない信号領域中でビットレートを減少させるには効率的であるが、突然の信号変化を伴う領域では、比較的少ない成分がトーントラックに関連付けられうるため、従って多数の成分が直接的に符号化されるため、あまり効率的ではない。更に、復号化器において差分パラメータから信号を再構成することが可能であるよう、ＴＤ符号化は、先行フレームのパラメータが無事に到着したという仮定に必ず依存する。例えばインターネットのような損失の多いパケットネットワーク等の伝送路では、この仮定は妥当ではないかもしれない。従って、幾つかの場合には、ＴＤ符号化に代わるものが望まれる。
【０００４】
このような代替策の１つに、正弦波成分間のフレーム間相関が利用される周波数差分（ＦＤ）符号化がある。ＦＤ符号化では、同じ信号フレームに属するパラメータ間の差分は量子化され、符号化され、従って先行フレームからのパラメータの依存性をなくす。ＲＦ符号化は、正弦波に基づく音声（speech）符号化においては周知であり、近年ではオーディオ符号化にも使用されている。一般的には、フレーム中の正弦波成分は周波数の昇順で量子化され符号化され、まず、最も低い周波数を有する成分が直接的に符号化され、次に、より高い周波数の成分が、それらに対して最も近くのより低い周波数の近傍に対して一回に一つずつ量子化され符号化される。このアプローチは単純であるが、最適ではないかもしれない。例えば、幾つかのフレーム中では、最近傍（nearest-neighbour）制約条件を緩めることがより効率的であるかもしれない。
【０００５】
本発明に想到するにあたって、発明者は、より一般的な正弦波モデルパラメータのＲＦ符号化の方法を探した。本発明の方法は、所与のパラメータ量子化器及び各量子化レベルに対応する符号語の長さ（ビット単位）について、フレーム中の正弦波成分の周波数差分及び直接符号化の最善の組合せを見つける。方法は、任意の成分対を含むパラメータの差を許すという意味で、即ち周波数領域の近傍である必要はないという意味で、既存の方法よりも一般的である。更に、上述の単純な方法とは異なり、最も効率的な結果が得られるならば、幾つかの（極端な場合は全ての）成分が直接的に符号化されてもよい。
【０００６】
オーディオ信号を符号化する方法から、方法は、符号化されたフレーム中の所与の正弦波成分のパラメータを、同じフレーム中の他の成分に対して差分的に、又は、直接的に、即ち差分符号化なしに、符号化する段階を有することを特徴とする。
【０００７】
様々な面から、本発明は特許請求の範囲の独立項に記載の方法及び装置を提供する。本発明の実施例の更なる望ましい特徴は従属項に記載されている。
【０００８】
本発明の実施例について、例として、添付の図面を参照して、以下に詳述する。
【０００９】
本発明の実施例は、インターネット等の信頼性の低い通信リンクを通じてオーディオ信号を伝送するシステム中に構成されうる。図８に示すこのようなシステムは、一般的には、オーディオ信号の源１０と、源１０からのオーディオ信号を伝送する伝送装置１２とを有する。伝送装置１２は、源１０からのオーディオ信号を得るための入力ユニット２０と、符号化されたオーディオ信号を得るためにオーディオ信号を符号化する符号化装置２２と、符号化された信号をネットワークリンク２６へ与えることにより符号化されたオーディオ信号を伝送又は記録する出力ユニット２４とを含む。受信装置３０は、符号化されたオーディオ信号を受信するようネットワークリンク２６に接続される。受信装置３０は、符号化されたオーディオ信号を受信する入力ユニット３２と、復号化されたオーディオ信号を得るために符号化されたオーディオ信号を復号化する装置３４と、復号化されたオーディオ信号を出力する出力ユニット３６とを含む。出力信号は、適当な装置４０によって要求されるように再生され、記録され、又は他の処理がされる。
【００１０】
符号化装置２２内では、信号は、所与の正弦波成分のパラメータを、同じフレーム中の他の成分に対して差分的に、又は直接的に、即ち、差分符号化なしに、符号化する段階を含む方法に従って符号化される。方法は、符号化処理中の任意の段階において差分符号化を用いるか否かを決定せねばならない。
【００１１】
この決定に至るために方法によって解決されねばならない問題を定式化するために、多数の正弦波成分ｓ1，．．．，ｓkが信号フレーム中で推定されている状況を考える。各成分ｓkは、振幅ａk及び周波数の値ωkで表わされる。本願の説明においては、位相値を考える必要はなく、なぜならば、位相値は周波数パラメータから導出されるか直接量子化されうるからである。それでも、本発明は、実際は、位相値及び／又は減衰係数等の他の値へ拡張されることがわかるであろう。
【００１２】
所与の成分のパラメータの量子化についての以下の可能性を考える。
（１）直接的な量子化（即ち、差分的でない）、又は
（２）より低い周波数の成分のうちの１つの成分の量子化されたパラメータに対する差分量子化。
【００１３】
図１に示すように、直接的及び差分的な量子化の全ての可能な組合せの組を、有向グラフ（ダイグラフ）Ｄを用いて表わす。
【００１４】
頂点（vertex）ｓ1，．．．，ｓkは、量子化されるべき正弦波成分を表わす。これらの頂点の間の辺（edge）は、差分符号化の可能性を表し、例えば、ｓ1とｓ4の間の辺は、ｓ1に対するｓ4のパラメータの量子化を表す（即ち、振幅パラメータについては
【００１５】
【数１】
2005506581.tif 000003
である）。頂点ｓ0は、直接的な量子化の可能性を表わすために導入されるダミー頂点である。例えば、ｓ0とｓ2の間の辺は、ｓ2のパラメータの直接的な量子化を表す。各辺には、辺によって表わされる特定の量子化を選ぶときのレート及び歪みに関するコストに対応する重みｗijが割り当てられる。基本的なタスクは、直接的及び差分的な符号化のレート・歪みの最適の組合せを見つけることである。このことは、各頂点ｓ1，．．．，ｓkにちょうど１つの入辺（in-edge）が割り当てられるよう、最小の総コストでＤ中にＫ個の辺の部分集合（subset）を見つけることに対応する。
【００１６】
ここで、辺の重みの計算について説明する。原理的には、各辺の重みは、
ｗij＝ｒij＋λｄij                                  式１
の形であり、式中、ｒijはこの特定の量子化に関連するレート（即ちビット数）であり、ｄijはこの特定の量子化に関連する歪みであり、λはラグランジュ乗数である。一般的には、図１に示すように、より高い添え字を有する成分ｓjは（既に量子化されている）より低い添え字の成分に対して量子化されるため、重みｗijの正確な値は、より低い添え字を有する成分ｓiの特定の量子化に依存する。換言すれば、ｗijの値は、ｓiが量子化される前には計算されえない。この依存性を除去するために、ここでは、振幅パラメータについて図２に示されるように同様の量子化器が直接的及び差分的な量子化に用いられると想定する。
【００１７】
図２中、縦列（column）１は、直接振幅量子化器についての出力レベルを示し、縦列２は差分振幅増幅器についての出力レベルを示し、縦列３は差分量子化後の達成可能な振幅レベルの組を示す。
【００１８】
この仮定の下、直接的及び差分的量子化を通じて達成されうる量子化レベルは同じであり、所与の成分は、直接的な量子化が用いられるのか差分的な量子化が用いられるのかには関係なく、同様に量子化される。このことは、直接的及び差分的な符号化の任意の組合せに対して総歪みが一定であることを意味するため、式１中でλ＝０とすることができる。更に、Ｄの全ての重みの値は、予めｗij＝ｒijとして計算されえ、ただし、
【００１９】
【数２】
2005506581.tif 000004
であり、
【００２０】
（外１）
2005506581.tif 000005
は、
【００２１】
（外２）
2005506581.tif 000006
を表わすのに必要とされるビットの数を表わす。この例では、
【００２２】
（外３）
2005506581.tif 000007
の値は、予め計算されたハフマン符号語テーブル中のエントリとして見つけることができる。
【００２３】
例をよく理解するために、扱われている問題を定式化することが必要である。当該の信号フレームは、符号化されるべきＫ個の正弦波成分を含むと仮定し、最適ＦＤ符号化問題を以下のように定式化する：
問題１：辺の重みがｗijである所与の有向グラフＤについて、
（ａ）各頂点ｓ1，．．．，ｓkにちょうど１つの入辺が割り当てられ、及び、
（ｂ）各頂点ｓ1，．．．，ｓkに最大で１つの出辺（out-edge）が割り当てられる
よう、全体の重みが最小となるＫ個の辺の集合を見つける。
【００２４】
制約条件（ａ）は、Ｋ個の正弦波成分の夫々が、ちょうど一回量子化され符号化されることを保証するため、重要である。制約条件（ｂ）は、Ｋ個の辺の解の木上の特定の簡単な構造を実行する。これは、復号化器に対して、送信された（デルタ）振幅及び周波数をどのように組み合わせるかを知らせるのに必要な辺情報の量を減少させるために重要である。図３は、制約条件（ａ）と（ｂ）を満たす可能な解の木の例を示す。尚、例えば従来技術の提案で用いられる「標準」ＦＤ符号化設定は、図示の枠組みの図３ｃの特別な場合である。
【００２５】
上述の問題を解決するとき、２つのアルゴリズム（アルゴリズム１及びアルゴリズム２と称する）が与えられる。アルゴリズム１は数学的に最適であるのに対して、アルゴリズム２はより低い計算上の費用で近似的な解を与える。
【００２６】
アルゴリズム１：問題１を解決するために、グラフ理論で周知の問題であるいわゆる割り当て（assignment）問題として定式化する。有向グラフＤ（図１）を用いて、図４に示すグラフＧを構築する。Ｇの頂点は、２つの部分集合へ分けられ得る。即ち、頂点ｓ1，．．．，ｓk-1及びｓ0のＫ個のコピーを含む左側部分集合Ｘと、頂点ｓ1，．．．，ｓk及び
【００２７】
（外４）
2005506581.tif 000008
で示されるＫ−１個のダミー頂点を含む右側部分集合Ｙへ分けられる。
【００２８】
多数の辺がＸとＹの頂点を連結する。Ｘ中の頂点に連結される辺は有向グラフＤ中の出辺に対応し、頂点ｓ1，．．．，ｓk∈Ｙに連結される辺は有向グラフＤ中の入辺に対応する。例えば、Ｇ中のｓ2∈Ｘからｓ4∈Ｙへの辺は、有向グラフＤ中の辺ｓ2ｓ4に対応する。従って、グラフＧ中の実線で示される辺は有向グラフＤ中の「差分符号化」辺を表わす。更に、頂点｛ｓ0｝∈Ｘからｓ1，．．．，ｓk∈Ｙへの破線で示される辺は全て、成分ｓ1，．．．，ｓkの直接的符号化に対応する。Ｘ中の頂点を頂点ｓ1，．．．，ｓk∈Ｙに連結する辺の重みは、有向グラフＤ中の対応する辺の重みと同じである。最後に、Ｋ−１個のダミー頂点
【００２９】
（外５）
2005506581.tif 000009
は、解の木の中の幾つかの頂点は「葉（leaves）」であってもよいこと、即ち、出辺を有さないこと、を表わすために用いられる。例えば、図３ａ中、頂点ｓ2は葉である。グラフＧ中、このことは、ｓ2∈Ｘから頂点
【００３０】
（外６）
2005506581.tif 000010
のうちの１つへの辺として表わされる。
【００３１】
（外７）
2005506581.tif 000011
に連結される全ての辺は、重みが０である。
【００３２】
問題１の制約条件（ａ）及び（ｂ）を満たすＤ中のＫ個の辺の各集合は、ＧにおけるＹ中の頂点に対するＸ中の頂点の割り当てとして、即ち各頂点にちょうど１つの辺が割り当てられるようなＧ中の２Ｋ−１個の辺の部分集合として表わされうる。図５ａ乃至図５ｃは、図３ａ乃至図３ｃ中の木に対応する割り当ての例を示す。従って、問題１は、いわゆる割り当て問題として再び定式化されえ、これを以下、問題２と称するものとする。
【００３３】
問題２：各頂点にちょうど１つの辺が割り当てられるよう、グラフＧ中で、総重み（total  weight）が最小である２Ｋ−１の辺の集合を見つける。
【００３４】
問題２を解決する幾つかのアルゴリズムがあり、例えば、エイチ・ダブリュ・クーン（Ｈ．Ｗ．Ｋｕｈｎ）著、「割り当て問題におけるハンガリー法（The  Hungarian  Method  for  the  Assignment  Problem）」、海軍研究ロジスティックス季刊誌（Naval  Research  Logistics  Quarterly）、２：第８３−９７頁、１９９５年、に記載のＯ（（２Ｋ−１）3）の算術演算で問題を解決するいわゆるハンガリー法がある。他の実現方法に、アール・ジョンカー（R.  Jonker）及びエイ・ヴォルジェナン（A.  Volgenant）著、「密及び粗な線形割り当て問題に対する最短増大路アルゴリズム（A  Shortest  Augmenting  Path  Algorithm  for  Dense  and  Sparse  Linear  Assignment  Problems）」、コンピューティング（Computing）誌、第３８巻、第３２５乃至３４０頁、１９８７年、に記載のアルゴリズムがある。複雑さはハンガリー法と同様であるが、ジョンカー・ヴォルジェナン・アルゴリズムは、実用面ではより高速である。更に、このアルゴリズムは粗問題をより高速に解決でき、このことはこの実施例のマルチフレームリンク問題において重要である。
【００３５】
概して、アルゴリズム１は、以下の段階を有する。まず、有向グラフＤ（及びその結果としてグラフＧ）が構築される。次に、最小の重みを有するＧにおける割り当て（問題２）が決定される。最後に、Ｇにおける割り当てから、直接的及び差分的な符号化の最適な組合せが容易に導出される。
【００３６】
アルゴリズム２は、グラフＤの頂点ｓ1，．．．，ｓkを添え字の昇順に一回に１つずつ処理する反復的な貪欲（greedy）アルゴリズムである。ｋ番目の繰り返しにおいて、候補辺集合から頂点ｓkの入辺のうちの１つが選択される。候補集合は、以前に選択された出辺のない頂点から出発するｓkの入辺と、直接符号化辺ｓ0ｓkとからなる。この集合から、最小の重みを有する辺が選択される。この手順により、問題１の制約条件（ａ）及び（ｂ）を満たすＫ個の辺の集合が得られる。一般的には、この貪欲アプローチは最適ではなく、即ち、制約条件（ａ）及び（ｂ）を満たすより低い総重みを有するＫ個の辺の他の集合が存在しうる。アルゴリズム２は、Ｏ（Ｋ2）の計算上の複雑さを有する。
【００３７】
上述のように符号化される正弦波（デルタ）パラメータに加え、本発明を具現化する符号化された信号は、復号化器においてどのようにパラメータを組み合わせるかを表わす副次情報を含まねばならない。１つの可能性は、考えられうる各解の木に対して、副次情報アルファベット中の１つの記号（symbol）を割り当てることである。しかしながら、異なる解の木（solution  tree）の数は大きく、例えばフレーム中にＫ＝２５個の正弦波成分があるとき、異なる解の木の数は約１０18であり、これは副次情報アルファベット中の解の木に索引付けするための６２ビットに対応する。明らかに、この数は殆どの用途において大きすぎる。幸いなことに、（デルタ）パラメータシーケンスに特定の順序が適用されていれば、副次情報アルファベットは、トポロジー的に別個の解の木を表わすだけでよい。トポロジー的に別個の木であること及びパラメータ順序の表記をはっきりとさせるため、図６ａ及び図６ｃ中の解の木の例と、木の下に列挙された対応するパラメータシーケンスとを考える。図６ａ及び図６ｂ中のスパニングツリーは、夫々が３つの辺と２つの辺の枝から構成され、従って副次情報アルファベット中の同じ記号で表わされるため、トポロジー的に同一である。逆に、図６ｃの木は、５つの辺を含む単一の枝から構成され、トポロジー的に他の木とは別個である。トポロジー的な木構造を知り、例えば（デルタ）パラメータはまず最初に最長の枝でパラメータストリーム中に枝ごとに生ずると想定すると、復号化器は受信したパラメータを正確に組み合わせることが可能である。
【００３８】
従って、本発明の望ましい実施例は、トポロジー的に別個の解の木に対応する記号を有する副次情報アルファベットを提供する。副次情報の上限は、このような木の数によって与えられる。トポロジー的に別個の木の数についての表現がそれに続く。
【００３９】
図６ａ乃至図６ｃの例に示すように、解の木の構造は、木の中の各枝の長さを特定することによって表わされうる。最長の枝が最初であるという順序を想定すると、トポロジー的に別個の木の集合は、和がＫとなる増加しない正の整数の別個のシーケンスによって特定され、組み合わせ論（combinatorics）では、このようなシーケンスは正の整数Ｋの「整数区画（integer  partitions）」と称される。例えば、Ｋ＝５のとき、次の７つの整数区画がある：｛５｝（図１ｃ），｛４，１｝，｛３，２｝（図１ａ及び図１ｂ），｛３，１，１｝，｛２，２，１｝，｛２，１，１，１｝及び｛１，１，１，１，１｝である。従って、Ｋ＝５のとき、７つのトポロジー的に別個の解の木があり、副次情報アルファベットは７つの記号からなる。Ｐj（Ｋ）を、最初の整数がｊであるＫ個の整数区画の数を表わすものとすると、別個の解の木の数Ｐは以下の帰納式で表わすことができる。
【００４０】
【数３】
2005506581.tif 000012
但し、
【００４１】
【数４】
2005506581.tif 000013
図７は、正弦波成分の数Ｋの関数としてトポロジー的に別個の木の数を示す図である。従って、Ｋ＝２５のときの副次情報アルファベットのインデックス付けは、最大で１１ビットを必要とする。尚、グラフは副次情報の上限を示し、例えばエントロピー符号化を用いる統計的な性質の利用は副次情報レートを更に減少させうる。
【００４２】
提案されるアルゴリズムのパフォーマンスは、オーディオ信号を用いたシミュレーション研究で示されうる。４４．１ｋＨｚのレートでサンプリングされ、約２０秒間の持続時間で夫々サンプリングされた４つの異なるオーディオ信号は、連続するフレーム間に５０％の重なり合いを有するＨａｎｎｉｎｇウィンドウを用いて１０２４サンプルの固定長のフレームへ分割された。
【００４３】
各信号フレームは、そのパラメータがマッチング追跡アルゴリズムを用いて抽出される固定数のＫ＝２５個の、一定振幅、一定周波数の正弦波成分を有する正弦波モデルを用いれ表わされた。振幅及び周波数パラメータは、夫々２０％及び０．５％の相対量子化レベル間隔を用いて対数領域で均一に量子化される。同様に相対量子化レベルは、図２に示すような直接的及び差分的量子化に使用され、量子化されたパラメータはハフマン符号化を用いて符号化された。
【００４４】
各フレームについてどのように直接的及びＦＤ符号化を組み合わせるかを決定するのにアルゴリズム1及び２を用いて、実験が行われた。更に、振幅及び周波数のパラメータが図３ｃ中、Ｋ＝５について示される「標準」ＦＤ符号化形態を用いて量子化されるシミュレーションが行われた。最後に、ＦＤ符号化の可能な利得を決定するために、パラメータは、直接的に、即ち差分符号化なしに量子化された。各実験は、実験において推定された異なるハフマン符号を用いたものである。
【００４５】
これらの各符号化手順について、（デルタ）振幅及び周波数を符号化するのに必要なビットレートＲparsが（１次のエントロピーを用いて）推定された。更に、アルゴリズム１及び２は、解の木構造に関する情報が復号化器へ送信されることを必要とするため、この副次情報を表わすのに必要なビットレートＲS.Iもまた推定された。以下の表１は、様々な符号化戦略及びテスト信号についての推定されたビットレートを示す。このコンテキストでは、同様の量子化器が全ての実験に対して使用され、従ってテスト信号は同じ歪みレベルで符号化されるため、ビットレートの比較は妥当である。
【００４６】
以下の表１の縦列は、様々な符号化法及びテスト信号に対するビットレート［ｋｂｐｓ］を示す。テーブルの縦列は、Ｒpars：（デルタ）振幅及び周波数についてのビットレートと、ＲS.I：副次情報（木構造）に必要なレートと、ＲTotal：総レートである。利得は、様々なＦＤ符号化法での直接的な符号化（差分的ではない）に対する相対的な改善である。
【００４７】
表１は、直接的及びＦＤ符号化の組合せを決定するアルゴリズム１を用いることは、直接的な符号化に対する１８．８％−２７．０％の範囲のビットレート低下を与えることを示す。アルゴリズム２は、１８．５％−２６．７％の範囲におけるビットレート低下で殆ど同じ動作を与える。アルゴリズム２から生ずる僅かに低い副次情報は、アルゴリズムがより少ないがより長い「枝」を生じさせる傾向があるため、観察される異なる解の木の数を減少させることによる。最後に、ＦＤ符号化の「標準」方法は、１２．７−２４．０％でビットレートを減少させる。
【００４８】
従って、所与のフレーム中で正弦波成分の直接的及びＦＤ符号化のビットレート最適な組合せを決定する２つのアルゴリズムを用いる符号化方法が与えられる。オーディオ信号を用いたシミュレーション実験では、提案されるアルゴリズムは、直接的な符号化に対して最大で２７％のビットレートの低下を示した。提案されるアルゴリズムは更に、一般的に用いられるＦＤ符号化法と比較して最大で７％のビットレートを低下させる。本発明について、単独の技術としてＦＤ符号化に焦点を当てて考えてきたがが、方法の更なる実施例は、ＦＤ符号化をＴＤ符号化と組み合わせて示すよう一般化される。このような結合ＴＤ／ＦＤ符号化法では、２つの符号化技術の強さを組み合わせる実施例を与えることが可能である。
【００４９】
上述の実施例は、本発明を制限するものではなく例示的なものであって、当業者は、特許請求の範囲を逸脱することなく多くの他の実施例を設計することが可能であることに留意すべきである。特許請求の範囲において、括弧内に示す全ての参照符号は、特許請求の範囲を制限するものと考えられるべきではない。「有する」又は「含む」という単語は、特許請求の範囲に列挙する要素又は段階以外の要素又は段階の存在を排除するものではない。単数形で記載された要素は、その要素が複数存在する場合を排除するものではない。本発明は、幾つかの別々の要素を有するハードウエアによって、また、適切にプログラムされたコンピュータによって実現されうる。幾つかの手段を列挙した装置に関する請求項では、これらの手段のうちの幾つかは、同一のハードウエアアイテムによって実現されうる。互いに異なる従属項に幾つかの手段が記載されているという事実は、これらの手段の組合せが利用されうるものではないことを示すものではない。
【００５０】
【表１】
2005506581.tif 000014
【図面の簡単な説明】
【００５１】
【図１】所与のフレームにおける正弦波成分（Ｋ＝５）の直接的及び周波数差分的な符号化の全ての可能な組合せを表わすのに用いられる有向グラフＤを示す図である。
【図２】本発明の実施例におけるスカラ振幅量子化器についての出力レベルの例を示す図である。
【図３ａ】Ｋ＝５の場合の許可された解の木の例を示す図である。
【図３ｂ】Ｋ＝５の場合の許可された解の木の例を示す図である。
【図３ｃ】Ｋ＝５の場合の許可された解の木の例を示す図である。
【図４】割り当てとして（明細書中に定義した）問題１の可能な解を表わすグラフＧ（Ｋ＝５）であり、明瞭性のため、幾つかの辺及び重みを示す図である。
【図５】図３の木に対応するグラフＧ中の割り当てを示す図である。
【図６ａ】トポロジー的に同一の及び別個の木の例を示す図である。
【図６ｂ】トポロジー的に同一の及び別個の木の例を示す図である。
【図６ｃ】トポロジー的に同一の及び別個の木の例を示す図である。
【図７】本発明を実現する符号化された信号中のトポロジー的に別個の解の木の数を正弦波成分の数Ｋの関数として示すグラフである。
【図８】本発明を実現するオーディオデータを伝送するシステムの簡単化されたブロック図である。
【図２】
2005506581.tif 000015
【図７】
2005506581.tif 000016
【国際公開パンフレット】
2005506581.tif 000017
2005506581.tif 000018
2005506581.tif 000019
2005506581.tif 000020
2005506581.tif 000021
2005506581.tif 000022
2005506581.tif 000023
2005506581.tif 000024
2005506581.tif 000025
2005506581.tif 000026
2005506581.tif 000027
2005506581.tif 000028
2005506581.tif 000029
2005506581.tif 000030
2005506581.tif 000031
2005506581.tif 000032
2005506581.tif 000033
2005506581.tif 000034
2005506581.tif 000035
2005506581.tif 000036
2005506581.tif 000037
2005506581.tif 000038
2005506581.tif 000039
【国際調査報告】
2005506581.tif 000040
2005506581.tif 000041