(57)【要約】エンコーダの動作中に、信号ベクトル（ｘ）が受信される。第１の多倍精度オペランド（Ψ’ｋ）が、エンコードされる信号ベクトルに基づいて生成される。仮数オペランドと指数オペランドが生成される。仮数オペランドと指数オペランドは双方とも、エンコードされる信号ベクトルに基づく第２の多倍精度オペランドを表している。Ψ’ｋの一部分を修正するために指数オペランドに基づいて選択する。Ψ’ｋの一部を仮数オペランドに基づいて修正して、修正済みの多倍精度オペランド（Ψ’ｋ＋１）を生成する。最終的に、多倍精度コード語を生成して、対応するデコーダで用いるようにする。
2011501511.tif 000002
【特許請求の範囲】
【請求項１】
入力ベクトル（ｘ）からコード語（Ｃ）を生成するエンコーダを操作する方法であって、
エンコードされる前記入力ベクトルを受信するステップと、
前記入力ベクトルに基づいて、第１の多倍精度オペランド（Ψ’ｋ）を生成するステップと、
仮数オペランド（Ｍ）および指数オペランド（ｈ）を生成するステップであって、前記仮数オペランドおよび前記指数オペランドは、エンコードされる信号ベクトルに基づく第２の多倍精度オペランド（Ｆ’（ｐｋ，ｋ））を表す、前記仮数オペランド（Ｍ）および指数オペランド（ｈ）を生成するステップと、
修正される前記第１の多倍精度オペランドの一部分を前記指数オペランドに基づいて選択するステップと、
前記第１の多倍精度オペランドの前記一部分を前記仮数オペランドに基づいて修正して、修正済みの多倍精度オペランド（Ψ’ｋ＋１）を生成するステップと、
前記修正済みの多倍精度オペランドに基づいて前記コード語（Ｃ）を生成するステップと
を含む方法。
【請求項２】
Ψ’ｋが、Ｆ’（ｐｉ，ｉ）；１≦ｉ≦ｋを表す仮数オペランドと指数オペランドの集合に基づいており、ｐｉは、前記入力ベクトルｘの非ゼロ要素の位置である、請求項１に記載の方法。
【請求項３】
【数１】
2011501511.tif 000073
である、請求項１に記載の方法。
【請求項４】
ｈが関数ｋｉである、請求項１に記載の方法。
【請求項５】
修正される前記第１の多倍精度オペランドΨ’ｋの前記一部分が、整数ｗｉとｗｕとで定義される位置インジケータによって表される、請求項１に記載の方法。
【請求項６】
【数２】
2011501511.tif 000074
であり、１６が語長であり、ｌＲが前記仮数の長さである、請求項５に記載の方法。
【請求項７】
エンコーダ（１００）であって、
エンコードされるベクトルｘを受信するステップと、
ｘに基づいて第１の多倍精度オペランド（Ψ’ｋ）を生成するステップと、
仮数オペランド（Ｍ）および指数オペランド（ｈ）を生成するステップであって、前記仮数オペランドと前記指数オペランドは、エンコードされる信号ベクトルに基づく第２の多倍精度オペランド（Ｆ’（ｐｋ，ｋ））を表す、前記仮数オペランド（Ｍ）および指数オペランド（ｈ）を生成するステップと、
修正されるΨ’ｋの一部分を前記指数オペランドに基づいて選択するステップと、
Ψ’ｋの前記一部分を前記仮数オペランドおよび位置インジケータに基づいて修正して、修正済みの多倍精度オペランド（Ψ’ｋ＋１）を生成するステップと、
Ψ’ｋ＋１に基づいてコード語（Ｃ）を生成するステップと
を実行する組み合わせコーディング回路（１０６）を備えるエンコーダ（１００）。
【請求項８】
コード語（Ｃ）からベクトル（ｘ）を生成するデコーダを操作する方法であって、
前記コード語（Ｃπ）を受信するステップと、
Ｃπに基づいて、第１の多倍精度オペランド（Ψ’ｋ＋１）を生成するステップと、
仮数オペランド（Ｍ）および指数オペランド（ｈ）を生成するステップであって、前記仮数オペランドと前記指数オペランドは、第２の多倍精度オペランド（Ｆ’（ｐｋ、ｋ））を表す、前記仮数オペランド（Ｍ）および指数オペランド（ｈ）を生成するステップと、
修正されるΨ’ｋ＋１の一部分を前記指数オペランドに基づいて選択するステップと、
Ψ’ｋ＋１の前記一部分を前記仮数オペランドおよび位置インジケータに基づいて修正して、修正済みの多倍精度オペランド（Ψ’ｋ）を生成するステップと、
ベクトルｘの（ｋ−１）番目の非ゼロ要素の位置ｐｋ−１をデコードするステップと、
前記位置ｐｋ−１に基づいて前記ベクトル（ｘ）を生成するステップと
を含む方法。
【請求項９】
デコーダ（３００）であって、
コード語（Ｃπ）を受信するステップと、
Ｃπに基づいて第１の多倍精度オペランド（Ψ’ｋ＋１）を生成するステップと、
仮数オペランド（Ｍ）および指数オペランド（ｈ）を生成するステップであって、前記仮数オペランドおよび前記指数オペランドは、エンコードされる信号ベクトルに基づく第２の多倍精度オペランド（Ｆ’（ｐｋ，ｋ））を表す、前記仮数オペランド（Ｍ）および指数オペランド（ｈ）を生成するステップと、
修正されるΨ’ｋ＋１の一部分を前記指数オペランドに基づいて選択するステップと、
Ψ’ｋ＋１の前記一部分を前記仮数オペランドおよび位置インジケータに基づいて修正して、修正済みの多倍精度オペランド（Ψ’ｋ）を生成するステップと、
ベクトルｘの（ｋ−１）番目の非ゼロ要素の位置ｐｋ−１をデコードするステップと、
前記位置ｐｋ−１に基づいて前記ベクトル（ｘ）を生成するステップと
を実行する組み合わせコーディング回路（３０６）を備えるデコーダ（３００）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般的にはベクトルのコーディングに関し、より詳細には、ベクトルの低複雑度組み合わせ階乗パルスコーディングに関する。
【背景技術】
【０００２】
音声、オーディオ、画像、ビデオおよび他の信号のベクトル量やマトリクス量をコーディングする方法が公知である。参照して本明細書に組み込むパン（Ｐｅｎｇ）らによる米国特許第６，２３６，９６０号に記載されているこのような方法のひとつが、階乗パルスコーディング（Ｆａｃｔｏｒｉａｌ  Ｐｕｌｓｅ  Ｃｏｄｉｎｇ：ＦＰＣ）として周知である。ＦＰＣは、合計でＭビットを用いてベクトルｘｉをコーディングすることが可能であるが、前提条件は、
【０００３】
【数１】
2011501511.tif 000003
、およびベクトルｘｉの値がすべて、−ｍ≦ｘｉ≦ｍとなるような整数であることであり、式中ｍは単位振幅パルスの総数であり、ｎはベクトル長である。全Ｍビットを用いて、最大限に効率的にＮ個の組み合わせをコーディングし、組み合わせの理論的に最小数を与える以下の式、
【０００４】
【数２】
2011501511.tif 000004
が成立する。この式の場合、Ｆ（ｎ，ｄ）は、
【０００５】
【数３】
2011501511.tif 000005
によって与えられるｎ個の位置上でのｄ個の非ゼロベクトル要素の組み合わせの数であり、Ｄ（ｍ，ｄ）は、ｍ個の全単位パルスが
【０００６】
【数４】
2011501511.tif 000006
によって与えられるとした場合に、ｄ個の非ゼロベクトル要素の組み合わせの数であり、２ｄは、ｄ個の非ゼロベクトル要素の極性（符号）を表すために必要な組み合わせを表す。項ｍｉｎ（ｍ，ｎ）は、単位振幅パルス（ｕｎｉｔ  ｍａｇｎｉｔｕｄｅ  ｐｕｌｓｅ）の数ｍがベクトル長ｎを超えた場合を想定している。この形式のベクトルをコーディングおよびデコーディングする方法および装置の全体は、従来技術に詳述されている。さらにこのコーディング方法の実用例が、３ＧＰＰ２規格Ｃ．Ｓ００１４−Ｂに記載されているが、ここで、ベクトル長ｎ＝５４、単位振幅パルスの個数ｍ＝７で、Ｍ＝３５ビットコード語となる。
【０００７】
ｎやｍのこれらの値は、なんら不条理な複雑度の重荷となるものではないが、これより大きい値になると、特に、メモリと計算上の複雑度をできる限り低く保つことが必要とされるモバイル携帯機器には即座に問題を引き起こしかねない。たとえば、ある応用分野（オーディオのコーディングなど）にこのコーディング方法を用いるには、ｎ＝１４４、ｍ＝２８以上の値が必要となる。このような状況下では、従来技術による方法を用いた組み合わせ式Ｆ（ｎ，ｄ）を生成するためのコストはあまり高すぎて実用的ではない。
【０００８】
このコストをさらに詳しく見ると、式３は、
【０００９】
【数５】
2011501511.tif 000007
と書き換えられる。これを直接実現しようとすると問題が発生するが、それは、Ｆ（１４４，２８）では、９９ビットの商（ｑｕｏｔｉｅｎｔ）を生成するには分子の精度が１９７ビットで分母の精度が９８ビットである必要があるからである。今日の携帯機器で用いられる大抵のデジタル信号プロセッサ（ｄｉｇｉｔａｌ  ｓｉｇｎａｌ  ｐｒｏｃｅｓｓｏｒｓ：ＤＳＰｓ）では、一般的に１６ビット×１６ビットの乗算しかサポートしていないため、特殊な多倍精度乗算／除算ルーチンを用いる必要がある。このようなルーチンでは、一般にｋ次の倍数／累算（ＭＡＣ）演算を必要とする一連のネスティングされた乗算／累算演算を必要とし、ここでｋはオペランド中にある１６ビットセグメントの数である。１９７ビットのオペランドの場合、
【００１０】
【数６】
2011501511.tif 000008
である。したがって、１９７×１６ビットの乗算単独の実行でも、最小で１３のＭＡＣ演算とシフト演算およびストア演算が必要となる。分母の項は同様に計算して、９８ビットの結果となる。加えて、１９７／９８ビットの除算が必要であるが、これは極めて複雑な演算であり、式５の階乗関係式をすべて計算するには、かなりの量のリソースが必要となる。
【００１１】
複雑度を軽減するには、式５を書き直して、除算を次のように分割して次式を生成すればよい。
【００１２】
【数７】
2011501511.tif 000009
この式で、除算のダイナミックレンジは縮小するが、残念なことに、３、７、９などによる除算を正確に表すには商の分解能をあげる必要がある。この構造に対処するために、結果が整数となることを保証するには丸め演算も必要となる。高精度の除算が多く存在することを考えれば、この実施方法ではｍおよびｎが大きい値の場合に複雑度の問題を適切に解決することはないし、また、精度誤差が累積して不正確な結果となる可能性もある。
【００１３】
さらに別の実施例では、式５を次のように再編成してもよい。
【００１４】
【数８】
2011501511.tif 000010
この式を左から右に評価すると、その結果は常に整数値となる。この方法では精度およびダイナミックレンジの問題をある程度制御するが、ｍおよびｎが大きい場合にはやはり多倍精度の乗算と除算を広範囲に用いる必要がある。
【００１５】
最後に、計算の複雑度を最小化するには、参照テーブルにすべての階乗組み合わせを事前計算してストアしておくのがよいかもしれない。こうしておけば、Ｆ（ｎ，ｍ）のすべての値を単にｎ×ｍマトリクスにストアしておいて、わずかなプロセッササイクルでメモリから適当に検索すればよい。しかしながら、この方式の問題点は、ｎおよびｍが大きくなるに連れて、関連するメモリ要件も大きくなることである。前の例を参照すると、Ｆ（１４４，２８）では、
【００１６】
【数９】
2011501511.tif 000011
のストレージが必要となり、これは、ほとんどのモバイル携帯機器にとっては不条理な値である。
【発明の概要】
【発明が解決しようとする課題】
【００１７】
したがって、ベクトルの低複雑度組み合わせ階乗パルスコーディングのための方法および装置に対する必要性が存在する。
【課題を解決するための手段】
【００１８】
上記の必要性を解決するため、本明細書に、ベクトルの低複雑度組み合わせコーディングの方法および装置を提供する。エンコーダの動作中に、信号ベクトル（ｘ）を受信する。第１の多倍精度オペランド（Ψ’ｋ）を、エンコードされる信号ベクトルに基づいて生成する。仮数オペランドと指数オペランドを生成する。仮数オペランドと指数オペランドは双方とも、エンコードされる信号ベクトルに基づく第２の多倍精度オペランドを表している。Ψ’ｋの一部分を修正するために指数オペランドに基づいて選択する。Ψ’ｋの一部分を仮数オペランドに基づいて修正して、修正済みの多倍精度オペランド（Ψ’ｋ＋１）を生成する。最終的に、多倍コード語を生成して、対応するデコーダで用いるようにする。
【００１９】
本発明には、ベクトル（ｘ）からコード語（Ｃ）をエンコードするエンコーダを操作する方法がその範囲に含まれる。この方法には、エンコードされるベクトルｘを受信するステップと、第１の多倍精度オペランド（Ψ’ｋ）をｘに基づいて生成するステップと、仮数オペランド（Ｍ）および指数オペランド（ｈ）を生成するステップとが含まれる。仮数オペランドおよび指数オペランドは、エンコードされる信号ベクトルに基づく第２の多倍精度オペランド（Ｆ’（ｐｋ，ｋ））を表している。次に、Ψ’ｋの一部分を修正するために指数オペランドに基づいて選択し、このΨ’ｋの一部を仮数オペランドと位置インジケータに基づいて修正して、修正済みの多倍精度オペランド（Ψ’ｋ＋１）を生成する。最終的に、Ψ’ｋ＋１に基づいてコード語（Ｃ）を生成する。
【００２０】
本発明にはさらに、エンコードされるベクトルｘを受信するステップと、第１の多倍精度オペランド（Ψ’ｋ）をｘに基づいて生成するステップと、仮数オペランド（Ｍ）および指数オペランド（ｈ）を生成するステップとを実行する組み合わせコーディング回路を備えるエンコーダがその範囲に含まれる。仮数オペランドと指数オペランドは、エンコードされる信号ベクトルに基づく第２の多倍精度オペランド（Ｆ’（ｐｋ，ｋ））を表している。次に、Ψ’ｋの一部分を修正するために指数オペランドに基づいて選択し、このΨ’ｋの一部を仮数オペランドと位置インジケータに基づいて修正して、修正済みの多倍精度オペランド（Ψ’ｋ＋１）を生成する。最終的に、Ψ’ｋ＋１に基づいてコード語（Ｃ）を生成する。
【００２１】
本発明には、コード語（Ｃ）からベクトル（ｘ）を生成するデコーダを操作する方法がその範囲に含まれる。この方法には、コード語（Ｃπ）を受信するステップと、第１の多倍精度オペランド（Ψ’ｋ＋１）をＣπに基づいて生成するステップと、仮数オペランド（Ｍ）および指数オペランド（ｈ）を生成するステップとが含まれる。仮数オペランドと指数オペランドは、コード語に基づく第２の多倍精度オペランド（Ｆ’（ｐｋ，ｋ））を表している。Ψ’ｋ＋１の一部分を修正するために指数オペランドに基づいて選択し、このΨ’ｋ＋１の一部を仮数オペランドと位置インジケータに基づいて修正して、修正済みの多倍精度オペランド（Ψ’ｋ）を生成する。ベクトルｘの（ｋ−１）番目の非ゼロ要素の位置ｐｋ−１をデコードして、ベクトル（ｘ）を位置ｐｋ−１に基づいて生成する。
【００２２】
本発明にはさらに、コード語（Ｃπ）を受信するステップと、第１の多倍精度オペランド（Ψ’ｋ＋１）をＣπに基づいて生成するステップと、仮数オペランド（Ｍ）および指数オペランド（ｈ）を生成するステップとを実行する組み合わせコーディング回路を備えるデコーダがその範囲に含まれる。仮数オペランドと指数オペランドは、コード語に基づく第２の多倍精度オペランド（Ｆ’（ｐｋ，ｋ））を表している。Ψ’ｋ＋１の一部分を修正するために指数オペランドに基づいて選択し、このΨ’ｋ＋１の一部分を仮数オペランドと位置インジケータに基づいて修正して、修正済みの多倍精度オペランド（Ψ’ｋ）を生成する。ベクトルｘの（ｋ−１）番目の非ゼロ要素の位置ｐｋ−１をデコードして、ベクトル（ｘ）を位置ｐｋ−１に基づいて生成する。
【図面の簡単な説明】
【００２３】
【図１】エンコーダのブロック図である。
【図２】コード語の生成を示す図である。
【図３】デコーダのブロック図である。
【図４】図１及び図３の組み合わせ関数発生器の動作を示すフローチャートである。
【図５】図１のエンコーダの動作を示すフローチャートである。
【図６】図３のデコーダの動作を示すフローチャートである。
【図７】図１の組み合わせコーディング回路の動作を示すフローチャートである。
【図８】図３の組み合わせデコーディング回路の動作を示すフローチャートである。
【発明を実施するための形態】
【００２４】
ここで図面を見ると（同じ番号は同じ構成要素を示している）、図１はエンコーダ１００のブロック図である。エンコーダ１００は、ベクトル発生器１０２と、組み合わせコーディング回路（コーダ）１０６と、組み合わせ関数発生器１０８と、他のコーディング回路１０４とを備えている。動作中、コーディングされる入力信号がベクトル発生器１０２に受信される。当技術分野において周知であるように、入力信号には、音声、オーディオ、画像、ビデオおよび他の信号などの信号が含まれている。
【００２５】
ベクトル発生器１０２は入力信号を受信して、ベクトルｘｉを生成する。ベクトル発生器１０２は、これに限られないが、パン（Ｐｅｎｇ）らが記載しているようなコード励起線形予測（Ｃｏｄｅ−Ｅｘｃｉｔｅｄ  Ｌｉｎｅａｒ  Ｐｒｅｄｉｃｔｉｏｎ：ＣＥＬＰ）音声コーディング、離散フーリエ変換（Ｄｉｓｃｒｅｔｅ  Ｆｏｕｒｉｅｒ  Ｔｒａｎｓｆｏｒｍ：ＤＦＴ）、離散コサイン変換（Ｄｉｓｃｒｅｔｅ  Ｃｏｓｉｎｅ  Ｔｒａｎｓｆｏｒｍ：ＤＣＴ）および修正離散コサイン変換（Ｍｏｄｉｆｉｅｄ  Ｄｉｓｃｒｅｔｅ  Ｃｏｓｉｎｅ  Ｔｒａｎｓｆｏｒｍ：ＭＤＣＴ）に基づいた方法を含むオーディオ、画像およびビデオのための変換ドメインコーディング、ウェーブレットに基づいた変換コーディング、直接時間ドメインパルスコード変調（ＰＣＭ）、差分ＰＣＭ、適応差分ＰＣＭ（ＡＤＰＣＭ）または、当技術分野において周知であるサブバンドコーディング技法のファミリの内のいずれかを含むエンコーディングパラダイムのうちの任意数のものを含む。これらの上記形態のうちの実質的にどの信号ベクトルでも本発明にしたがって処理すれば利点となる。
【００２６】
組み合わせコーディング回路１０６は、ベクトルｘｉを受信し、階乗パルスコーディングを用いてコード語Ｃを生成する。上述したように、階乗パルスコーディングでは、合計でＭビットを用いてベクトルｘｉをコーディングすることが可能であるが、前提条件は、
【００２７】
【数１０】
2011501511.tif 000012
、及びベクトルｘｉの値がすべて、−ｍ≦ｘｉ≦ｍとなるような整数であることであり、式中ｍは単位振幅パルスの総数であり、ｎはベクトル長である。上述したように、ｍとｎが大きい値になると、特に、メモリと計算上の複雑度をできる限り低く保つことが必要とされるモバイル携帯機器には即座に問題を引き起こしかねない。
【００２８】
この問題点を解決するため、組み合わせ関数発生器１０８は、Ｆ’（ｎ，ｄ）を生成する低複雑度技法を利用する。次に、組み合わせコーディング回路１０６がＦ’（ｎ，ｄ）を利用して、コード語Ｃを生成する。回路１０８は、比較的低分解能の近似（精度ビット）の階乗組み合わせＦ’（ｎ，ｄ）を利用するが、これは、有効なコード語の生成を可能とするのに十分な精度を提供するだけである。すなわち、ある特性が維持される限り、関数Ｆ（ｎ，ｄ）を適当に近似するだけで、結果得られるコード語が一意にデコーディング可能であることを保証するに十分である。Ｆ’（ｎ，ｄ）をどのように生成するかを説明するために、最初に、Ｆ（ｎ，ｄ）の適切な近似である関数Ｆ’（ｎ，ｄ）を導出する。第一のステップでは、式５の任意のベースａの対数を取って、配列し直した項の逆ｌｏｇベースａを取る。
【００２９】
【数１１】
2011501511.tif 000013
式中、関数ｅｘｐａ（ｋ）＝ａｋである。次に、関数Ｐ（ｉ）、Ｑ（ｄ）およびＲ（ｋ）を定義して、次式のように式８に代入する。
【００３０】
【数１２】
2011501511.tif 000014
式中、Ｐ（ｉ）＝ｌｏｇａ（ｉ）、
【００３１】
【数１３】
2011501511.tif 000015
およびＲ（ｋ）＝ｅｘｐａ（ｋ）＝ａｋである。
【００３２】
しかしながら、本発明の好ましい実施形態によれば、結果得られるコード語が一意にデコーディング可能であるようにするために、Ｆ（ｎ，ｄ）とＦ’（ｎ，ｄ）が等価である必要はない。これが成立するための十分条件は次の２つの式だけである。
【００３３】
【数１４】
2011501511.tif 000016
および
【００３４】
【数１５】
2011501511.tif 000017
第一の条件では、制約は単に、Ｆ’（ｎ，ｄ）＜Ｆ’（ｎ，ｄ）の場合、コードスペースがオーバーラップし、その結果、特定のコード語を生成することが可能な入力が２つ以上存在することになり、このため、このコード語は一意にデコーディング可能ではないと述べている。第二の条件は、所与のｎとｄの「誤差」は、米国特許第６，２３６，９６０号でパン（Ｐｅｎｇ）らが述べた再帰的な関係の前の要素と関連する誤差の項の合計以上でなければならないことを述べている。Ｆ（ｎ，ｄ）＝Ｆ’（ｎ−１，ｄ）＋Ｆ’（ｎ−１，ｄ−１）と示すことが可能であるが、これは、組み合わせ式が
【００３５】
【数１６】
2011501511.tif 000018
にまさに等しい場合にのみ真である。しかしながら、式１１の不等式で十分であるとはいえ、ｎとｄのすべての値に対して必ずしも真であるとは言えない。このような値に対して、Ｆ（ｎ，ｄ）は、パン（Ｐｅｎｇ）らの式３１から導出された別の不等式を満足するが、これは次式で与えられる。
【００３６】
【数１７】
2011501511.tif 000019
この場合、式１１は、ある（ｍ，ｋ）、（ｍ≦ｎ）、（ｋ≦ｄ）に対して厳密な不等式を満たす必要がある、すなわち、次式を満たす必要がある。
【００３７】
【数１８】
2011501511.tif 000020
式９に戻って、次に、関数Ｐ’（ｉ）、Ｑ’（ｄ）およびＲ’（ｋ）を作成してＦ’（ｎ，ｄ）を生成するが、ここで、オリジナルの関数の低複雑度近似を取って次式のようにした。
【００３８】
【数１９】
2011501511.tif 000021
また、式１０および式１１の条件が満たされる。Ｐ’（ｉ）を考慮すると、Ｐ’（ｉ）≧ｌｏｇａ（ｉ）（ｉ∈［１，２，・・・，ｎ］）となるように関数を近似させたいところである。ａ＝２としてＰ’（ｉ）を３２ビットの精度に制限すると、その結果、演算は携帯モバイル機器で容易に実施可能となるが、これは、ほとんどのＤＳＰで単一サイクルでの３２ビットの加算がサポートされているからである。したがって、次のように定義する。
【００３９】
【数２０】
2011501511.tif 000022
式中、ｌ（ｉ）は、ｉの関数として変化する移動係数である。好ましい実施形態では、ｌ（ｉ）＝ｌ＝２１であるが、他の値の集合も可能である。この例の場合、係数２ｌは左にｌビット分移動させることと等価であり、これによって、床関数
【００４０】
【数２１】
2011501511.tif 000023
から端数ビットが除去され、一方、次に最も高い整数に丸められて、最終的に係数２−ｌが結果を右にｌビットだけ戻して移動させる。この方法を用いると、すべてのｉ≧１に対してＰ’（ｉ）≧ｌｏｇ２（ｉ）となり、また、たった３２ビットを用いるだけで十分なダイナミックレンジと精度が得られるが、これは、ｌｏｇ２ドメインでの正の整数の分解能が９ビットであるため、５１２ビットの数を表すことが可能であるからである。これらの値をリアルタイムで計算するという複雑度を避けるために、Ｆ（１４４，２８）の例の場合のたった１４４×４バイトというメモリを用いて事前計算してテーブルにストアすることが可能である。Ｑ（ｄ）を近似させる際に同様の方法を用いると、次式が得られる。
【００４１】
【数２２】
2011501511.tif 000024
式中、床関数
【００４２】
【数２３】
2011501511.tif 000025
を用いるが、これは、合計から個数を減算するためである。こうすることによって、Ｑ’（ｄ）が寄与してＦ’（ｎ，ｄ）≧Ｆ’（ｎ，ｄ）が保証されるように
【００４３】
【数２４】
2011501511.tif 000026
となることが保証される。ｌ（ｊ）は、ｍおよびｎの配列次第で多くの値をとることが可能であるが、好ましい実施形態では、可変の移動係数に対してｌ（ｊ）＝ｌ＝１４という値を用いている。Ｐ’（ｉ）と同じように、Ｑ’（ｄ）も、Ｆ（１４４，２８）の例の場合のたった２８×４バイトというメモリを用いて事前計算してテーブルにストアすることが可能である。Ｒ’（ｋ）を定義するには、最初にｋを次のように定義する必要がある。
【００４４】
【数２５】
2011501511.tif 000027
Ｐ’（ｉ）とＱ’（ｄ）を上記のように定義すると、ｋは、８ビットの符号なし整数成分ｋｉおよび２４ビットの端数成分ｋｆを有する３２ビットの数であることが望ましい。これを用いて、ｋ＝ｋｉ＋ｋｆとし、次にベース２の逆対数を取って２ｋ＝２ｋｉ２ｋｆとしてＲ’（ｋ）≧ｅｘｐ２（ｋ）＝２ｋを導出する。次に、テイラー級数展開を用いて、Ｋｆ＝２ｋｆで代表されるように所望の精度で端数成分を推定し、天井関数を用いて結果を丸め、その結果を適切に移動して、多倍精度結果（ｌ個のみの有効ビットを有する）を形成し、これで、
【００４５】
【数２６】
2011501511.tif 000028
とするが、式中、２ｋｉはテイラー級数展開の結果に適用される整数移動係数である。式中、ｌはＲ’（ｋ）≧２ｋを保証するために式１５と１６に同様に用いられる移動係数である。しかしながら、Ｒ’（ｋ）は効率的なリアルタイム演算目的で実際に事前計算することは不可能であるため、再構成された信号ベクトルが入力された信号ベクトルに正確に適合することを保証するためにエンコーダとデコーダの双方で必要とされる演算を正確に指定する際には特に注意が必要である。式中、Ｒ’（ｋ）は、正確にｌビットで表すことが可能な
【００４６】
【数２７】
2011501511.tif 000029
を左へ移動することによって得られる。
【００４７】
上記において、関数Ｐ’（ｉ）、Ｑ’（ｄ）およびＲ’（ｋ）を、個々の関数の推定値がそれぞれ、結果としてＦ’（ｎ，ｄ）≧Ｆ（ｎ，ｄ）となることを保証するように選択されている。しかしながら、集合効果がこの条件を満足すれば十分である。たとえば、Ｐ’（ｉ）およびＱ’（ｄ）は上記の通りで良いが、Ｒ’（ｋ）はＲ’（ｋ）≒２ｋ関数とすればより便利となるが、これは、最下位ビットを切り捨てまたは丸め、これで、Ｒ’（ｋ）がｋがある値の場合には２ｋ未満となるようにするものである。これは、この効果がＰ’（ｉ）およびＱ’（ｄ）の影響よりも小さく、式１０および式１１の特性が真である限りは問題ない。
【００４８】
また、Ｐ’（ｉ）、Ｑ’（ｄ）およびＲ’（ｋ）がどのような関数でも、式１０および式１１の特性が満足される限り、一般性を失うことなく用いることができる。しかしながら、用いる精度があまりに低いとビットレートが増大しかねないことに注意しなければならない。また、ビットレートと複雑度には固有のトレードオフがあり、ｍおよびｎの値が大きい場合、複雑度を著しく低減するためには、１ビットまたは２ビットの増加は適当なトレードオフである。
【００４９】
組み合わせコーディング回路１０６での位置とサイズの部分コード語Ｃの形成を次に述べる。p＝｛ｐ１，ｐ２，・・・，ｐｖ｝を非ゼロパルス位置（増加数）としμ＝｛ｍ１，ｍ２，・・・，ｍｖ｝をベクトルｘ内のそれぞれの位置での大きさとする。パルス位置のコードは次式で与えられる。
【００５０】
【数２８】
2011501511.tif 000030
また、パルス振幅のコードは次式で与えられる。
【００５１】
【数２９】
2011501511.tif 000031
したがって、これらのコード語を形成するにはｖ個とｖ−１個の多倍精度数を加える必要がある。デコーダでは同じような減算が必要である。これらの演算もまた、ｎおよびｍが大きい場合にはＦＰＣ方法の複雑度を増大させることになる。多層埋め込みコーディングシステムの場合でのオーディオ信号のエンコーディング／デコーディングを考えてみる。この技法は、多層システムの３つの層での残余誤差信号の変換物をエンコーディングするのに用いられる。２０ｍｓのブロックのサイズをｎ＝２８０とし、すべての層で同じであるとする。エンコーディング用のパルスの数は、それぞれの層のビットレートによって異なる。それぞれの層で８ｋｂｐｓ、１６ｋｂｐｓまたは３２ｋｂｐｓであれば、それぞれ２０ｍｓのブロックのコーディングには１６０ビット、３２０ビット、６４０ビットが必要となる。ＦＰＣ技法を用いると、２８０という長さを有するブロックは、それぞれ層当たり１６０ビット、３２０ビット、６４０ビットに対して２８パルス、７４パルス、２３０パルスを用いてコーディング可能である。式（１９）および式（２０）での多倍精度演算は、一般に１６ビット語で動作するデジタル信号プロセッサで実行される。したがって、１６０ビットのコード語を形成するには、１０語を超えると追加演算が必要となり、６４０ビットのコード語を形成するには、４０語を超えると追加演算が必要となる。各々の追加演算で４単位（桁上げの発生、配列への移動、桁上げつきの加算）が必要となる。したがって、多倍システムのｐ層でｋビットのコード語をエンコーディング／デコーディングするには、
【００５２】
【数３０】
2011501511.tif 000032
を必要とする。ｎ、ｍ、ｐの様々な値に対する、多倍精度加算／減算演算の複雑度を表１に示す。この表において、ＷＭＯＰＳとは毎秒での１００万の重み付け演算（Ｗｅｉｇｈｔｅｄ  Ｍｉｌｌｉｏｎｓ  ｏｆ  Ｏｐｅｒａｔｉｏｎ  Ｐｅｒ  Ｓｅｃｏｎｄ）のことである。
【００５３】
【表１】
2011501511.tif 000033
表１から、ビットレートが倍になると、多倍精度加算の複雑度は６倍に増えることが分かる。
【００５４】
すでに述べたように、組み合わせ関数は、次式で与えられる近似関数で置換される。
【００５５】
【数３１】
2011501511.tif 000034
式中、
【００５６】
【数３２】
2011501511.tif 000035
であり、Ｒ’（ｋ）は次式で与えられるＲ’（ｋ）≒２ｋの近似式である。
【００５７】
【数３３】
2011501511.tif 000036
式中、ｋ＝ｋｉ＋ｋｆをｋの整数成分と端数成分とに分割すると、Ｋｆ＝２ｋｆが、ｋの端数成分の低分解能テイラー級数展開式となる。上記の事前定義された関数Ｑ’（ｒ）とＲ’（ｋ）とに基づいて、Ｐ’（ｉ）が最初に得られ、これで、次式の一意のデコーディング可能性の不等式、
【００５８】
【数３４】
2011501511.tif 000037
がｎおよびｄのすべての値に対して満足される。
【００５９】
式（１９）および式（２０）に戻って、実際の関数Ｆの代わりに近似関数Ｆ’を置換すると、次式が得られる。
【００６０】
【数３５】
2011501511.tif 000038
式（２３）で得られるバイナリ表示Ｆ’（ｎ，ｒ）は、ｋ＞ｌＲの場合にはｋｉ−ｌＲ個の終端ゼロを有する。Ｆ’（ｎ，ｒ）は、ｌＲビットの数を左に移動（ｈ＝ｋｉ−ｌＲだけ移動）することによって多倍精度数として得られたものである。Ｆ’（ｐｋ，ｋ）のｈ個の終端ビットはゼロであるので、コード語のこれらのｈ個の終端ビットは、Ｆ’（ｐｋ，ｋ）を式（２５）中の既存の部分和に加算すれば影響されることはない。この特性を効率的に用いるには、Ｆ’（ｐｋ，ｋ）を擬似浮動小数点形式で計算する、すなわち、Ｒ’（ｋ）がｌＲビットの仮数（Ｍ）と対応する非ゼロ指数（ｈ）とを出力する。ｌＲビットの仮数（Ｍ）は次のように定義される。
【００６１】
【数３６】
2011501511.tif 000039
また、指数ｈは次のように定義される。
【００６２】
【数３７】
2011501511.tif 000040
式中、式２５および式２６中の合計では、
【００６３】
【数３８】
2011501511.tif 000041
個の語は、Ｆ’（ｐｋ，ｋ）を部分和に加算すれば影響されないという事実を容易に用いることが可能である。
【００６４】
上記の方法では、複雑度が幾分か軽減される。しかしながら、それでも演算で発生した桁上げは、コード語の終わりまで伝播しなければならない。その結果、Ｆ’（ｋ，ｒ）がある特性を満足すれば、桁上げはコード語全体のより小さい部分に伝播するだけでよいことがわかる。
【００６５】
第一に、正確に組み合わせ関数Ｆ（ｐｋ，ｋ）が（式（１９）中でのように）加算され、合計がｋの昇順で計算されるのであれば、１つの余剰の語に桁上げが伝播されることになるということを次のように見極める。
【００６６】
【数３９】
2011501511.tif 000042
すなわち、Ｆ（ｐｋ，ｋ）が加算される部分和Ψｋは次式で与えられる。
【００６７】
【数４０】
2011501511.tif 000043
多倍精度オペランドΨｋはＦ（ｐｋ，ｋ−１）未満であることがわかる。Ｆ（ｐｋ，ｋ）に対するyｋの最大比率はｋ／（ｐｋ−ｋ＋１）未満である。この比率はまた、ｋの最大可能値でもあるｋ＝ｐｋ＋１の場合には無限大である。Ｆ（ｐｋ，ｐｋ＋１）＝０であるため、この特殊な場合には桁上げを伝播させる必要はない。ｋが他の値の場合、この比率はｎおよびｍのうちのどちらか小さい方以下である。したがって、次式となる。
【００６８】
【数４１】
2011501511.tif 000044
ｍｉｎ（ｍ，ｎ）は３２７６８未満であるから、上記の合計では、桁上げを余剰の１語を超えて伝播させることはない。これは、順序付けられた合計（２９）中の組み合わせ関数をそのまま用いれば、たった１つの余剰の語に桁上げを伝播するという効果が得られることを示唆するが、組み合わせ関数そのままでは、終端のゼロという利点がなく、したがって、Ｆ（ｐｋ，ｋ）の全長にわたって加算が実行される。
【００６９】
明らかに、一意のデコーディング可能性および終端のゼロを有することに加えて、式（２９）中のＦ’（ｐｋ，ｋ）の順序付けされた合計では桁上げを伝播させる必要がないように近似関数Ｆ’（ｐｋ，ｋ）を設計することが好まれる。Ｆ’（ｐｋ，ｋ）が加算される部分和（第一の多倍精度コード語）が次式で与えられることがわかる。
【００７０】
【数４２】
2011501511.tif 000045
これは、Ｆ’（ｐｋ，ｋ−１）未満である。したがって、次の不等式：
【００７１】
【数４３】
2011501511.tif 000046
は、次式のようにＦ’（ｐｋ，ｋ）をΨ’ｋに加算すれば、Ψ’ｋ＋１（修正された多倍精度コード語）が生成され、
【００７２】
【数４４】
2011501511.tif 000047
桁上げはたった１つの余分の語に伝播するだけでよい。このことは、式（２１）、式（２２）、および式（２３）によって定義されたＦ’（ｎ，ｒ）に対して実験的に決定されている。一意のデコーディング可能性不等式だけではなく、次の部分和不等式も満足させる必要がある。すなわち、
【００７３】
【数４５】
2011501511.tif 000048
一意のデコーディング可能性不等式がｎ＜ｐｋの場合に対して成立すると、次式となることがわかる。
【００７４】
【数４６】
2011501511.tif 000049
したがって、次式を満足するＰ’（ｉ）を生成すれば十分である。
【００７５】
【数４７】
2011501511.tif 000050
式中、近似組み合わせ関数Ｆ’は次のことを満足する。
１．一意のデコーディング可能性不等式
２．終端ゼロ特性
３．部分和不等式
したがって、これらの関数を、多倍精度のコード語全体の非常に小さい部分集合（１０、２０または３０語のうちのたった３語）だけを修正することによって、階乗パッキングコード語の構築に用いることが可能である。この小さい部分集合は、修正される多倍精度コード語中の語を特定する整数ｗｉおよびｗｕによって定義される位置インジケータによって表される。位置インジケータは次のように計算される。
【００７６】
【数４８】
2011501511.tif 000051
式中、１６は語長であり、ｌＲ＝１６は仮数の長さとして選ばれている。多倍精度コード語（Ｃπ）の語であるｗｉからｗｕは仮数Ｍに基づいて修正されている。ここで、多倍精度コード語は次式である。
【００７７】
【数４９】
2011501511.tif 000052
デコーダでは、Ψ’ｋ＋１＝Ψ’ｋ＋Ｆ’（ｐｋ，ｋ）からＦ’（ｐｋ，ｋ）を減算する。合計で用いたような引数を用いると、関数Ｆ’が上述の３つの特性を満足すれば、デコーディング中でも、コード語全体の非常に小さい部分集合だけを修正するだけでよいことがわかる。デコーダでは、ｐｋ−１は次のように得られる。
【００７８】
【数５０】
2011501511.tif 000053
従来技術による方法を用いて位置と大きさをエンコーディング／デコーディングする複雑度を表１に示した（複雑度は、合計と減算に対してしか示されていない。ここで複雑度は、Ｆ’を生成する複雑度を含んでいない）。多層埋め込みシステムの３層においてこの提案のエンコーディング／デコーディング方法を用いるとその結果、多倍精度加算／減算の複雑度がかなり軽減する。本発明を用いた場合の対応する複雑度を表２に示す。ここで、エンコーディングでより多くのパルス（より長いコード語）を用いると複雑度がより改善される。
【００７９】
【表２】
2011501511.tif 000054
非ゼロ位置の数のエンコーディング
ｌＲビットの仮数と指数を表示する形式もまた、非ゼロ位置の数をコーディングする際に利点がある。非ゼロ位置ｖの数の数値のコーディングは次式で与えられる。
【００８０】
【数５１】
2011501511.tif 000055
二つの近似関数の乗算では、多倍精度形式より仮数と指数による形式の場合の方がはるかに容易になり得ることが簡単にわかる。しかしながら、その主な利点は、複雑度を軽減しようとして、ｌＲビットの仮数および指数表示を用いて、Ｆ’（ｎ，ｋ）およびＦ’（ｍ−１、ｋ−１）をそれぞれたった２つの語（そのｌＲビットの仮数の積とその指数の和もまた事前ストア可能である）を用いて事前ストアすることが可能であるという事実である。これによって、なんら深刻なＲＯＭの要件なしでｖを迅速にエンコーディングすることが可能となる。
【００８１】
エンコーダ１００の動作中は、組み合わせコーディング回路１０６が、エンコーディングされる信号ベクトル（ｘ）を受信する。第１の多倍精度オペランド（Ψ’ｋ）が、エンコーディングされる信号ベクトルに基づいて生成される。より具体的には、
【００８２】
【数５２】
2011501511.tif 000056
となるが、式中、ｐｉはベクトルｘの非ゼロ要素の位置である。仮数オペランド（
【００８３】
【数５３】
2011501511.tif 000057
）と指数オペランド（ｈ＝ｍｉｎ（０，ｋｉ―ｌＲ）が生成される。仮数オペランドと指数オペランドは双方とも、エンコーディングされる信号ベクトルに基づく第２の多倍精度オペランド（Ｆ’（ｐｋ，ｋ））を表している。次に、回路１０６は修正されるΨ’ｋの一部分を指数オペランドに基づいて選択する。上述したように、この部分は、修正される多倍精度コード語中の語を特定する整数ｗｉおよびｗｕによって定義される位置インジケータによって表される。位置インジケータは式（３８）に示すように計算される。次に、Ψ’ｋの一部を仮数オペランドと位置インジケータに基づいて修正して、式（３４）中のように修正済み多倍精度オペランド（Ψ’ｋ＋１）を生成し、また、対応するデコーダで用いる目的で、多倍精度コード語を、式（３９）に示すように修正済み多倍精度オペランドに基づいて生成する。
【００８４】
図２に、上記の技法を介してコード語を生成する一例を示す。上記したように、
【００８５】
【数５４】
2011501511.tif 000058
である。図２に示すように、Ψ’ｋからy’ｋ＋１に移る際には、多倍精度コード語の語３、４および５だけが修正される。修正予定であると選ばれる特定の語は、多倍精度コード語Ｃπから取られたｗｉからｗｕ個の語であり、ｗｉおよびｗｕは指数ｈ＝５０に基づいており、そのため、次式のようになる：
【００８６】
【数５５】
2011501511.tif 000059
Ψ’ｋのｗｉ個の語は、仮数Ｍの最下位ビットである左に移動されたｈ−１６×ｗｉを加算することによって修正される。ｗｉ＋１から語ｗｕ−１個の語は、仮数Ｍの次の１６ビットを加算することによって修正される。これら加算ではそれぞれ、桁上げ付き加算が実行され、次の段階のために繰越が発生する。語ｗｕは前の加算からの繰越分だけを加算することによって修正される。式中、ｌＲ＝１６であり、ｗｕ＝ｗｉ＋２である。デコーダでの場合、減算が加算の代わりに実行される。
【００８７】
図３は、デコーダ３００のブロック図である。図示するように、デコーダ３００は、組み合わせデコーディング回路３０６、信号再構築回路３１０、他のデコーディング回路３０４および組み合わせ関数発生器１０８を備えている。動作中、組み合わせコード語が、組み合わせデコーディング回路３０６によって受信される。組み合わせデコーディング回路３０６は、組み合わせ関数発生器にｎおよびｄを提供し、それに応答してＦ’（ｎ，ｄ）を受信する。次に、デコーディング回路３０６は、Ｆ’（ｎ，ｄ）に基づいてベクトルｘｉを生成する。回路３０６は、回路１０６と同様に動作するが、加算の代わりに減算が実行されるという点で異なる。言い換えれば、Ψ’ｋ＝Ψ’ｋ＋１―Ｆ’（ｐｋ，ｋ）となる。ベクトルｘｉは信号再構築回路３１０に渡され、ここで、出力信号（たとえば、音声、オーディオ、画像、ビデオまたは他の信号）が、ｘｉと他のデコーディング回路３０４からの他のパラメータとに基づいて生成される。より具体的には、他のパラメータには、特定の実施形態で使用中の信号コーディングパラダイムと関連する任意の数の信号再構築パラメータが含まれる。これらには、信号スケーリングとエネルギーパラメータ、およびスペクトル整形パラメータおよび／または合成フィルタパラメータが含まれるが、これに限られない。通常は、これらのパラメータは、最終的な出力信号を再現するように、エネルギーをスケーリングするおよび／または再構築された信号ベクトルｘｉをスペクトル的に整形するために用いられる。
【００８８】
図４は、図１と図３の組み合わせ関数発生器の動作を示すフローチャートである。より具体的には、図４の論理の流れは、組み合わせ関数発生器１０８がＦ’（ｎ，ｄ）を生成するために必要なステップを示している。論理の流れはステップ４０２から始まり、ここで入力ｎおよびｄが受信される。ステップ４０３で、アキュムレータＡが０に設定される。ステップ４０４で、カウンタｉが、ｎ−ｄ＋１に等しくなるように設定される。ステップ４０６で、対数近似値Ｐ’（ｉ）がアキュムレータＡに加算される。ステップ４１０で、カウンタｉが１だけ増分される。ｉがｎより大きくなるまでステップ４０６およびステップ４１０がループ内で繰り返される。ステップ４１２でｉ＞ｎであるかを試験し、ｉがｎより大きくなればループを終了する。この段階では、アキュムレータには、組み合わせ関数Ｆ（ｎ，ｄ）の分子の対数近似値が入っている。組み合わせ関数Ｑ’（ｄ）の分母の対数近似値をステップ４１６でアキュムレータから減算して、組み合わせ関数の対数近似値を得る。ステップ４１８で、アキュムレータの指数近似値Ｒ’（Ａ）を取って、組み合わせ関数の近似値Ｂを生成する。ステップ４１４で、ＢをＦ’（ｎ，ｄ）として出力する。
【００８９】
図５は、図１のエンコーダの動作を示すフローチャートである。論理の流れはステップ５０１から始まり、ここで入力信号がベクトル発生器１０２によって受信される。上述したように、入力信号には、音声、オーディオ、画像、ビデオまたは他の信号が含まれる。ステップ５０３で、ベクトルｘｉが生成されて組み合わせコーディング回路１０６に入力され、ここでｍとｄが決定されて組み合わせ関数発生器１０８に渡される。上述したように、ｍは単位振幅パルスの合計数（またはｘｉの整数値成分の絶対値の和）であり、ｄはｘｉの非ゼロベクトル要素の数である。ステップ５０５で、Ｆ’（ｎ，ｄ）が組み合わせ関数発生器１０８で生成されて組み合わせコーディング回路１０６に渡され、ここでベクトルｘｉをコーディングして、組み合わせコード語Ｃを生成する（ステップ５０７）。上述したように、Ｆ’（ｎ，ｄ）は、Ｆ（ｎ，ｄ）中の関数Ｐ（ｉ）、Ｑ（ｄ）およびＲ（ｋ）を、式１０および式１１中の条件を満足するようにオリジナルの関数の低複雑度近似値で置換することによって生成される。
【００９０】
図６は、図３のデコーダの動作を示すフローチャートである。論理の流れはステップ６０１から始まり、ここで組み合わせコード語が組み合わせデコーダ３０６によって受信される。ステップ６０３で、ｎおよびｄが組み合わせデコーダ３０６から組み合わせ関数発生器１０８に渡され、Ｆ’（ｎ，ｄ）がデコーダ３０６に返される（ステップ６０５）。コード語がデコーダ３０６によってＦ’（ｎ，ｄ）に基づいてデコーディングされて（ステップ６０７）、ベクトルｘｉを生成し、ｘｉは信号再構築回路３１０に渡され、ここで、出力信号が生成される（ステップ６０９）。
【００９１】
図７は、組み合わせコーディング回路１０６の動作を示すフローチャートである。論理の流れはステップ７０１から始まり、ここで信号ベクトル（ｘ）が受信される。第１の多倍精度オペランド（Ψ’ｋ）が、エンコードされる信号ベクトルに基づいて生成される（ステップ７０３）。より詳細には、
【００９２】
【数５６】
2011501511.tif 000060
であり、式中、ｐｉはベクトルｘの非ゼロ要素の位置である。仮数オペランド（
【００９３】
【数５７】
2011501511.tif 000061
）と指数オペランド（ｈ＝ｍｉｎ（０，ｋｒ―ｌＲ）が生成される（ステップ７０５）。仮数オペランドと指数オペランドは双方とも、エンコーディングされる信号ベクトルに基づく第２の多倍精度オペランド（Ｆ’（ｐｋ，ｋ））を表している。次に、回路１０６は修正されるΨ’ｋの一部分を指数オペランドに基づいて選択する（ステップ７０７）。上述したように、この部分は、修正される多倍精度コード語中の語を特定する整数ｗｉおよびｗｕによって定義される位置インジケータによって表される。位置インジケータは式（３８）に示すように計算される。ステップ７０９で、Ψ’ｋの一部を仮数オペランドと位置インジケータに基づいて修正して、式（３４）中のように修正済み多倍精度オペランド（Ψ’ｋ＋１）を生成し、また、ステップ７１１で、対応するデコーダで用いられる目的で、多倍精度コード語を、式（３９）に示すように修正済み多倍精度オペランドに基づいて生成する。
【００９４】
図８は、組み合わせデコーディング回路３０６の動作を示すフローチャートである。論理の流れはステップ８０１から始まり、ここでコード語（Ｃπ）が受信される。第１の多倍精度オペランド（Ψ’ｋ＋１）が、受信されたコード語に基づいて生成される（ステップ８０３）。より具体的には、
【００９５】
【数５８】
2011501511.tif 000062
であり、式中ｐｉはベクトルｘの非ゼロ要素の位置である。仮数オペランド（
【００９６】
【数５９】
2011501511.tif 000063
）と指数オペランド（ｈ＝ｍｉｎ（０，ｋｉ−ｌＲ）が生成される（ステップ８０５）。仮数オペランドと指数オペランドは双方とも、コード語に基づく第２の多倍精度オペランド（Ｆ’（ｐｋ，ｋ））を表している。次に、回路３０６は、修正されるΨ’ｋ＋１の一部分を指数オペランドに基づいて選択する（ステップ８０７）。上述したように、この部分は、修正される多倍精度コード語中の語を特定する整数ｗｉおよびｗｕによって定義される位置インジケータによって表される。位置インジケータは式（３８）に示すように計算される。ステップ８０９で、Ψ’ｋ＋１の一部を仮数オペランドと位置インジケータに基づいて修正して、Ψ’ｋ＝Ψ’ｋ＋１−Ｆ’（ｐｋ，ｋ）のように修正済み多倍精度オペランド（Ψ’ｋ）を生成し、また、ステップ８１１で、ベクトルｘの（ｋ−１）番目の非ゼロ要素の位置ｐｋ−１を、式（４０）中でのように修正済み多倍精度コード語に基づいてデコードする。ステップ８１３で、デコーディングされたベクトルｘをデコーディングされた位置ｐｋ−１に基づいて生成する。
【００９７】
表１は、従来技術と比較して本発明と関連する複雑度の軽減状態を示す。ｍとｎのさまざまな値に対して、ビットの近接数ＭとＦ（ｎ，ｍ）に対するフレームあたりの関数コールの平均数とが与えられている。これらの例の場合、フレーム長のインターバルは２０ｍｓであり、これは毎秒５０フレームという率に相当する。複雑度比較の尺度単位は、毎秒での１００万の重み付け演算数、すなわちＷＭＯＰＳである。コンピュータシミュレーションを用いて、制限された精度固定小数点ＤＳＰ上で実行されたとして、複雑度の推定値を生成する。これらの例の場合、適宜多倍精度ライブラリを用い、また、各々の基本命令に適当な重みを割り当てた。たとえば、乗算と加算には、１つの演算の重みを与え、基本除算と超越（たとえば２ｘ）演算には、２５演算という重みが与えられた。表から、Ｆ’（ｎ，ｄ）を用いると、従来技術よりかなり複雑度が軽減されたことと、ｎおよびｍが増すのに比例して、複雑度が軽減することがわかる。この複雑度の軽減度は、Ｆ（１４４，６０）の場合の２桁高いが、ｎおよびｍがさらに増すに連れて増大し続けることが示されている。これは主として、従来技術で組み合わせ式を正確に実行するために必要とされるオペランドの精度が増大するためである。これらの演算は、ｍとｎが大きい値となる可能性があるベクトルをコーディングする方法としては複雑度の重荷が過度のものとなり、階乗パルスコーディングが実質的に消去されるという結果となることを証明している。本発明は、このタイプのコーディングにとって必要とされる複雑な組み合わせ式の推定値を生成するために小さいメモリ容量と結合した単一サイクル低精度演算しか必要としないようにすることによってこれらの問題を解決するものである。
【００９８】
【表３】
2011501511.tif 000064
以下のテキストと式は、広帯域拡散スペクトルデジタルシステムの向上可変レートコーデック、音声サービスオプション３、６８、および７０の第３世代パートナーシップ・プロジェクト２（３ＧＰＰ２）Ｃ．Ｐ００１４−Ｃ仕様のコーディングおよびこれへのデコーディングのための上記の技法を実施するものである。
４．１３．５  ＭＤＣＴ残存線スペクトル量子化
残存線スペクトルと呼ばれるＭＤＣＴ係数は、４．１１．８．３のＦＣＢ階乗コードブックと同様の方法で量子化される。基本的には、Ｎ＝ｎＦＰＣｍ個の可能な組み合わせの階乗コーディングは、長さｎのベクトルｖが特性
【００９９】
【数６０】
2011501511.tif 000065
であり、すべての要素ｖｉが整数値であれば実行可能である。すなわち、ｖの整数要素の絶対値の和がｍに等しい。この場合、Ｘｋのエネルギー・スケーリング・バージョンをコーディングすることが望ましく、これで、
【０１００】
【数６１】
2011501511.tif 000066
となるが、式中、γｍはグローバルスケール係数であり、領域０〜１４３は周波数領域０〜３６００Ｈｚに対応している。この場合、ｍはＮＢ入力の場合で２８またはＷＢ入力で２３のいずれかとなり得る。上記の目的を実施するために用いられるγｍの値は、次の擬似コードにしたがって繰り返して決定される（非ゼロ‖Ｘｋ‖２の場合）。
【０１０１】
【数６２】
2011501511.tif 000067
量子化された残存線スペクトルＸｃｃが次のように計算される、
【０１０２】
【数６３】
2011501511.tif 000068
まれな場合であるが、ｍとｍ’が互いに異なる値であれば、線スペクトルは、量子化された線スペクトルＸｃｃに単位値を加算または減算することによって修正しなければならない。これによって、結果としての線スペクトルが階乗コーディング方法を用いて正確にコーディングされることが保証される。線スペクトルＸｃｃを表す出力インデックスは、指定されたＲＬＳＩＤＸである。このインデックスは、１４４ＦＰＣ２８の場合には１３１ビット含み、１４４ＦＰＣ２３の場合には１１４ビット含んでいる。
【０１０３】
Ｘｃｃをエンコーディングおよびデコーディングすることに伴う複雑度という問題を解決するために、標準の組み合わせ関係式Ｆ（ｎ，ｒ）＝ｎＣｒ＝ｎ！／ｒ！（ｎ−ｒ）！の代わりに低分解能組み合わせ近似関数Ｆ’（ｎ，ｒ）を用いなければならない。特に、エンコーダとデコーダは双方とも、ベクトルＸｃｃを一意にエンコーディング／デコーディングする目的に対して十分である、特性Ｆ’（ｎ，ｒ）≧Ｆ（ｎ，ｒ）と特性Ｆ’（ｎ，ｒ）≧Ｆ’（ｎ−１、ｒ）＋Ｆ’（ｎ−１、ｒ−１）とを有する組み合わせ関数発生器Ｆ’（ｎ，ｒ）を利用する。関数Ｆ’（ｎ，ｒ）は次式で与えられる。
【０１０４】
【数６４】
2011501511.tif 000069
式中、Ｐ’（ｉ）およびＱ’（ｒ）は、次式で与えられる３２ビットの参照テーブルであり、
【０１０５】
【数６５】
2011501511.tif 000070
および
【０１０６】
【数６６】
2011501511.tif 000071
式中、Ｒ’（ｋ）は次式で与えられる、関数Ｒ’（ｋ）≒２ｋの多倍精度整数近似値である、
【０１０７】
【数６７】
2011501511.tif 000072
式中、ｋ＝ｋｉ＋ｋｆをｋの整数成分と端数成分とに分割すると、Ｋｆ＝２ｋｆが、ｋの端数成分のテイラー級数展開式となる。これらの演算によって、多倍精度の乗算と除算とを３２ビットの加算と２ｋの低複雑度テイラー級数展開、次いで多倍精度シフト演算とで置換することによって組み合わせ式を計算する際に必要とされる複雑度がかなり軽減される。エンコーディング／デコーディング演算の他のすべての要素は４．１１．８．３中の要素と同様である。
【０１０８】
本発明を特定の実施形態を参照して具体的に図示し説明したが、本発明の技術思想と範囲から逸脱することなく、本発明にさまざまな変更が可能であることが当業者に理解されるであろう。このような変更が添付の請求の範囲内であることを意図するものである。
【図１】
2011501511.tif 000075
【図２】
2011501511.tif 000076
【図３】
2011501511.tif 000077
【図４】
2011501511.tif 000078
【図５】
2011501511.tif 000079
【図６】
2011501511.tif 000080
【図７】
2011501511.tif 000081
【図８】
2011501511.tif 000082
【国際調査報告】
2011501511.tif 000083