(57)【要約】本発明は、ディジタル信号の符号化／復号化に関するものであり、特に、結合表現の計算にかかわる置換符号を使用するものに関するものである。本発明によれば、前記結合表現は、素因数累乗分解によって表されるとともに、選択された整数の事前記録表現を事前に読み出すことによって判断される。【特許請求の範囲】
【請求項１】
結合表現の計算を含む置換符号を使用するディジタル信号の符号化／復号化方法であって、
前記結合表現を素因数累乗分解により表し、選択する整数の事前記録分解表現をメモリから読出すことにより判断することを特徴とする方法。
【請求項２】
請求項１に記載の方法において、前記事前記録表現が指数を表す値を含み、該指数を表す値を前記選択する整数のそれぞれに対する連続する素数を表す値と相関してそれぞれ蓄積することを特徴とする方法。
【請求項３】
請求項１および請求項２のいずれかに記載の方法において、前記結合表現が整数（ｌ）の階乗値（ｌ！）を含み、前記事前記録表現が少なくとも階乗値（ｌ！）の分解表現を含むことを特徴とする方法。
【請求項４】
請求項１乃至請求項３のいずれかに記載の方法において、前記結合表現（ｔ’）の少なくとも１つが整数の分子（υ）の整数の分母（ρ）による商を含み、前記商を素因数累乗分解により表し、該素因数累乗分解の各累乗が前記分子（υ）および前記分母（ρ）とそれぞれ関連し、１つのかつ同じ素数（ｐｉ）に割当てられる指数の差分
【数１】
2009527171.tif 000208
であることを特徴とする方法。
【請求項５】
請求項１乃至請求項４のいずれかに記載の方法において、選択する整数の前記事前記録表現をアドレス可能なメモリに蓄積し、前記メモリのアドレス指定がそれぞれの素数に割当てる連続する指数を示し、前記選択する整数を再構成することを特徴とする方法。
【請求項６】
請求項５に記載の方法において、選択する整数の前記事前記録表現を連続するアドレスの前記形式で蓄積し、該各アドレスが素数に対してこの素数に割当てる指数を示し、前記選択する整数を再構成することを特徴とする方法。
【請求項７】
請求項１乃至請求項４のいずれかに記載の方法において、連続するビットグループを含むワードの前記形式で、前記事前記録表現を蓄積し、該各グループが：
−素数に応じる重み、および
−この素数に関連する指数に応じる値を
有することを特徴とする方法。
【請求項８】
請求項７に記載の方法において、少なくとも１つの部分マスクをビットの前記ワードに連続的に適用することにより、前記ビットの前記重みによる後続のオフセットおよび前記残りのビットの読出しにより、前記素因数累乗を判断することを特徴とする方法。
【請求項９】
請求項２に記載の方法において、本方法が、結合表現の前記計算に対し、
−前記結合表現
【数２】
2009527171.tif 000209
を形成する積および／または商に現れる項（（ｎ−１−ｋ）！、Ｓｋ、Ｐｋ）を前記選択する整数から特定するステップと、
−前記項の前記素因数分解に含む指数
【数３】
2009527171.tif 000210
をメモリにおいて読出すステップと、
−前記読出した指数を加算および／または対応して減算し、
【数４】
2009527171.tif 000211
前記結合表現の前記素因数累乗分解に含む前記指数
【数５】
2009527171.tif 000212
を判断し、そのことからその素因数累乗分解から前記結合表現を計算するステップ
を含むことを特徴とする方法。
【請求項１０】
請求項２および請求項９のいずれかに記載の方法において、以前の再起で判断した積を乗算する項を各再起に含む積の計算の再起ステップ含み、
−以前の再起で判断した前記積を素因数累乗分解の前記形式でメモリに保持し、
−前記積を乗算する前記項が前記分解を事前記録する前記選択する整数の１つであり、
−以前の再起で判断した前記積および前記積を乗算する前記項の前記それぞれの分解から導出する前記指数を共に各素数について１つずつ加算し、現再起の前記積を判断する、
ことを特徴とする方法。
【請求項１１】
請求項２および請求項９のいずれかに記載の方法において、以前の再起で判断した商を除算する項を各再起に含む除算の計算の再起ステップ含み、
−以前の再起で判断した前記商を素因数累乗分解の前記形式でメモリに保持し、
−前記商を除算する前記項が前記分解を事前記録する前記選択する整数の１つであり、
−前記項の前記分解から導出する前記指数を以前の再起で判断した前記商の前記分解から導出する前記指数から各素数について１つずつ減算し、現再起の前記除算を判断する、
ことを特徴とする方法。
【請求項１２】
請求項１乃至請求項１１のいずれかに記載の方法において、前記置換符号が、各部分ランクが前記結合表現の１つに対応する部分ランク
【数６】
2009527171.tif 000213
の累積を含む置換ランク（ｔ）を表す量の前記計算を含むことを特徴とする方法。
【請求項１３】
請求項１２に記載の方法において、ベクトル量子化ディジタル信号を符号化する場合に、前記置換ランクの前記計算（ＯＰ２）を使用し、以前のステップ（ＯＰ１）で実行した先導ベクトルの前記構成要素の前記置換を指標指定し、入力ベクトルに最も近い符号ベクトルを判断することを特徴とする方法。
【請求項１４】
請求項１２および請求項１３に記載の方法において、ベクトル量子化ディジタル信号を復号化する場合に、置換ランク（ｔ）の所与の値から、
−構成する符号ベクトルの少なくとも１つの仮定する構成要素（ｄｋ）に従い前記所与の値に近い置換ランクを表す少なくとも１つの量を計算し（ＯＰ３）、
−前記置換ランクを表す量が前記ランクの前記所与の値との近接条件を満たせば、前記仮定する構成要素（ｄｋ）の前記選択が妥当である、
ことを特徴とする方法。
【請求項１５】
請求項１４に記載の方法において、一方で前記仮定する構成要素（ｄｋ）に関連する部分ランクへおよび他方で前記仮定する構成要素の増分（ｄｋ＋１）に対応する構成要素に関連する部分ランクへの前記部分ランクの累積により前記所与の前記ランク値（ｔ）を纏めて扱うことができれば、前記近接条件を満たすことを特徴とする方法。
【請求項１６】
請求項１３乃至請求項１５のいずれかに記載の方法において、前記符号化／復号化がベクトル量子化によるソース符号化／復号化の前記タイプに関するものであることを特徴とする方法。
【請求項１７】
請求項１２に記載の方法において、前記符号化／復号化がチャネル変調符号化／復号化の前記タイプに関するものであり、前記符号化／復号化が、
−送信前に前記置換ランクからの符号ベクトルの前記判断（ＯＰ３）および
−受信時に受信ベクトルに対応する符号ベクトルからの前記置換ランクの前記計算（ＯＰ２）
を含むことを特徴とする方法。
【請求項１８】
請求項１２乃至請求項１７のいずれかに記載の方法において、請求項３と共同して、前記置換符号が最大次元ｎを有し、前記選択する整数が少なくとも、
−１と前記最大次元ｎとの間の前記整数と、
−前記整数０の前記階乗値と、
−好ましくは１と前記最大次元ｎとの間の前記整数の前記階乗値
を含むことを特徴とする方法。
【請求項１９】
請求項１８に記載の方法において、前記選択する整数がまた前記値０を含むことを特徴とする方法。
【請求項２０】
請求項１２乃至請求項１９のいずれかに記載の方法において、前記置換符号がシャルクビック計数を使用し、符号ベクトル（ｙ０、．．．、ｙｎ‐１）の切取り（ｙｋ、．．．、ｙｎ−１）に関連する部分ランク
【数７】
2009527171.tif 000214
が、
【数８】
2009527171.tif 000215
により表され、上式で
【数９】
2009527171.tif 000216
−が０乃至ｍの範囲の整数指標ｉに対する積を表し、
【数１０】
2009527171.tif 000217
−が０乃至ｍの範囲の指標ｉに対する総和を表し、
−ｌ！がｌ＞０の場合  ｌ！＝１×２×３×．．．×（ｌ−１）×ｌであり、０！＝１である前記整数ｌの前記階乗値であり、
−前記整数ｎが、符号ベクトルが含む構成要素の前記総数に対応する前記置換符号の前記次元であり、
−０とｎ−１との間の前記整数ｋが前記符号ベクトルのｋ番目の構成要素ｙｋの前記指標であり、
−前記整数ｑが、前記符号ベクトルが含む個別構成要素の前記数であり、
−項ｗｋｄがｋとｋ−１との間の指標構成要素の前記数を表し、１つのかつ同じ指標構成要素ｄの数に等しい値を有する
ことを特徴とする方法。
【請求項２１】
請求項２０に記載の方法において、請求項９と共同して、結合表現として前記部分ランク
【数１１】
2009527171.tif 000218
を形成する積および／または商において特定し、現れる前記整数が、
−０とｎ−１との間の全ての前記整数ｋに対し前記階乗項（ｎ−１−ｋ）！であり、
−各項ｗｋｉの前記値および／または各項ｗｋｉが０とｎとの間にある前記積Ｐｋ
【数１２】
2009527171.tif 000219
に含まれるその階乗値であり、
−０とｎ−１との間の全ての前記整数ｋに対し、各項が、１とｎ−１との間にある前記項Ｓｋ
【数１３】
2009527171.tif 000220
である
ことを特徴とする方法。
【請求項２２】
請求項２０および請求項２１のいずれかに記載の方法において、請求項１３と共同して、ｎ−１乃至０の範囲の指標ｋに対する前記符号ベクトル（ｙ０、．．．、ｙｎ‐１）の切取り（ｙｋ、．．．、ｙｎ−１）に従い各部分ランクを推定する前記部分ランク
【数１４】
2009527171.tif 000221
の前記累積の判断により、符号化に関して前記ランクの前記計算が行われることを特徴とする方法。
【請求項２３】
請求項２２に記載の方法において、前記項Ｓｋ
【数１５】
2009527171.tif 000222
の前記値に関する検査を実行し、前記項Ｓｋがゼロであれば前記部分ランク
【数１６】
2009527171.tif 000223
の推定を回避することを特徴とする方法。
【請求項２４】
請求項２０および請求項２１のいずれかに記載の方法において、請求項１４および請求項１５のいずれかと共同して、前記部分ランク
【数１７】
2009527171.tif 000224
の累積解除を表す量の前記計算が復号化において行われ、０乃至ｎ−１の範囲の指標ｋの前記符号ベクトルの前記構成要素ｙｋを判断することを特徴とする方法。
【請求項２５】
請求項２２および請求項２４のいずれかに記載の方法において、請求項１０および請求項１１のいずれかと共同して、前指標ｋに対する前記項Ｐｋ
【数１８】
2009527171.tif 000225
の前記分解における前記指数の前記総和を一時的にメモリに蓄積し、現指標ｋに対する項ｗｋｉの前記分解指数に、またはから加算または減算することを特徴とする方法。
【請求項２６】
デバイスのメモリに蓄積する置換符号を使用するディジタル信号の符号化／復号化のためのコンピュータプログラムであって、コンピュータプログラムが請求項１乃至請求項２５のいずれかに記載するような前記方法の前記ステップを実施する命令を含むことを特徴とするコンピュータプログラム。
【請求項２７】
置換符号を使用するディジタル信号の符号化／復号化デバイスであって、本デバイスが、
−請求項２６に記載するようなコンピュータプログラムの前記命令および選択する整数の事前記録分解表現を蓄積するメモリユニットと、
−前記メモリユニットにアクセスし、請求項１乃至請求項２５のいずれかに記載するような前記方法を実施する計算モジュール
を含むことを特徴とするデバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、音声、ビデオおよびより一般的にマルチメディア信号などのディジタル信号のその蓄積または伝送のための符号化／復号化に関する。本発明は、特に置換符号の符号化および復号化が引起す問題への解決法を提案する。
典型的に、本発明をまたソース符号化と同等な、チャネル符号化または「変調」に適用する。
本発明の意味するディジタル信号の圧縮符号化／復号化は通話および／または音響信号周波数符号化器が持つ変換係数の量子化に極めて有用である。
【背景技術】
【０００２】
ベクトル量子化
【０００３】
１つの非常に広く使用されるディジタル信号圧縮の解決法はベクトル量子化である。ベクトル量子化は有限セットから選択する同じ次元のベクトルにより入力ベクトルを表す。Ｍレベルを持つ量子化器（または「符号ベクトル」）は入力ベクトルセットに関する非全単射適用、一般にｎ次元実ユークリッド空間ＲｎまたはＭ個別要素：Ｙ＝｛ｙ０、ｙ１、．．．ｙＭ−１｝を持つＲｎの有限サブセットＹにおけるＲｎのサブセットである。
Ｙは再生成アルファベットまたは「辞書」または「ディレクトリ」とも呼ばれ、その符号ベクトル要素は「符号語」（または「出力点」または「標本」とも）呼ばれる。
量子化器の各次元ｒのビット速度（またはその「リゾリューション」）を次関係式により定義する。
【０００４】
【数１】
2009527171.tif 000002
【０００５】
ベクトル量子化では、ｎサンプルブロックをｎ次元ベクトルとして扱う。次元が非常に大きくなる場合ソース符号化理論により、ベクトル量子化性能はソース歪みビット速度限界に近づく。量子化器の最適性に関する必要条件に基づき、汎用ロイドアルゴリズム（Generalized Lloyd Algorithm、ＧＬＡ）などの統計的方法を使用して、ベクトル量子化器辞書を設計することができる。当然得られる統計的ベクトル量子化器は構造を持たず、符号化および蓄積双方の複雑度はｎ２ｎｒに比例するので、これにより計算および蓄積リソースに関してその探索は経費を要する。
図１Ａを参照すると、３つの主な演算、即ち符号化の２つおよび復号化の１つがベクトル量子化器を使用する。まず辞書からの符号ベクトルの選択により、入力ベクトルを符号化する（ステップＣＯＤ）。これは、入力ベクトルに最も類似する符号ベクトルである（図１Ａにおける演算ＯＰ１）。次いで、この符号ベクトル指標を判断し（ステップＩＮＤ）、送信または蓄積する（図１Ａにおける演算ＯＰ２）。復号化器（ステップＤＥＣ）では、符号ベクトルをその指標から判断する（図１Ａにおける演算ＯＰ３）。
【０００６】
変調では、図１Ａの３つの演算ＯＰ１、ＯＰ２およびＯＰ３を適用するが、順序は異なる。この変調／量子化の双対性を示す図１Ｂを参照して、指標から符号ベクトルへの遷移の配備を行う（図１Ａの演算ＯＰ３に対応する図１ＢのＣＯＤ’ステップ）。次いで雑音の影響を受けるチャンネルを経る送信後に、受信ベクトルに最も近い符号ベクトルの検索を行う（図１Ａの演算ＯＰ１に対応する図１ＢのＤＥＣ’ステップ）。最後に、符号ベクトル指標の復号化が第３のステップである（図１Ａの演算ＯＰ２に対応する図１ＢのＩＮＤ’ステップ）。
【０００７】
次元、ベクトルおよびビット速度により複雑度は指数関数的に増大し、非構造化ベクトル量子化器の使用は実時間においてその使用が可能である小さな次元および／または低ビット速度に制限される。非構造化ベクトル量子化器にとり、最も近い近隣の検索（演算ＯＰ１）は、最も近い近隣と入力ベクトルとの間の距離の測定を最少にする辞書要素を選択する全辞書要素の全検索を必要とする。後者の２つの演算（指標指定ＯＰ２および逆演算ＯＰ３）は一般に表の簡単な読出しにより実行するが、それにもかかわらずこれはメモリ空間が高くつく。サイズおよび次元の制約を克服するために、基本ベクトル量子化の幾つかの変形が検討された。変形は辞書構造の欠落を修正し、従って複雑度の削減を試行するが、品質の代価を伴う。一方、性能／複雑度のトレードオフは高度化し、ベクトル量子化を効果的経費により適用することができるリゾリューションおよび／または次元の範囲を増すことを可能にする。多くの構造化ベクトル量子化器方式が提案されており、特に「置換符号」を実施するベクトル量子化器を以下に説明する。
【０００８】
置換符号
「置換符号」ベクトル量子化器では、「先導」と（または「先導ベクトル」とも）呼ぶ第１の符号ベクトル構成要素の（辞書編集順序への）置換により、符号ベクトルを得る。これらの構成要素はサイズｑ（ｉ≠ｊの場合にａｉ≠ａｊであるようなｑのアルファベットＡ）のアルファベットＡ＝｛ａ０、ａ１．．．、ａｑ−１｝からその値を採用する。構成要素ａｉは実数（または完全整数）である。重みｗｉ（ｉは０乃至ｑ−１の範囲の指標である）はアルファベット文字ａｉの反復回数である。重みｗｉは
【０００９】
【数２】
2009527171.tif 000003
【００１０】
であるような正整数である。規定により、アルファベットの値はａ０＞ａ１＞．．．＞ａｑ−１を満たす。先導構成要素ｎは位置０から位置（ｎ−１）へ降順に進む。それ故先導ベクトルｙ０は次形式の次元ｎのベクトルである。
【００１１】
【数３】
2009527171.tif 000004
【００１２】
異なる構成要素の順序、例えば
ａ０＜ａ１＜．．．＜ａｑ−１
を選択できるであろうことは理解されるであろう。
先導ベクトルを「符号付先導」と呼び、置換符号を「タイプＩに関するもの」であると言う。その他の符号ベクトルをｙ０の構成要素の置換により得る。置換の総数Ｍは次式の通りである。
【００１３】
【数４】
2009527171.tif 000005
【００１４】
別のタイプの置換符号（タイプII）が存在する。再度、先導ベクトルは以前と同じ形式を有するが、その構成要素は正でなければならない（ａ０＞ａ１＞．．．＞ａｑ−１≧０）。ｙ０の構成要素への全ての可能な符号結合の割当てによるｙ０の構成要素の置換により、その他の符号ベクトルをまた得る。置換の総数Ｍは次式の通りである。
【００１５】
【数５】
2009527171.tif 000006
【００１６】
ここで、ａｑ−１＞０であればｈ＝ｎであり、その他の場合ｈ＝ｎ−ｗｑ−１である。この場合、先導ベクトルをまた絶対先導と呼ぶ。
【００１７】
「置換符号」ベクトル量子化器を拡張して置換符号の合成（即ち結合）とし、最近この置換符号結合構造を次元およびリゾリューション可変ベクトル量子化に（出願者名がＷＯ−０４／００２１９の書類において）一般化した。置換符号は統計的ベクトル量子化において使用するだけではない。置換符号はまた代数ベクトル量子化に見られ、代数ベクトル量子化は正規ドット配列または誤り訂正符号から導出する高度構造化辞書を使用する。置換符号はまた変調において使用する。
【００１８】
置換符号構造の使用により最適、高速最近近隣検索アルゴリズムの開発を可能にする（図１Ａの演算ＯＰ１）。一方、符号ベクトルの指標指定（または番号指定）（図１Ａの演算ＯＰ２）および逆復号化演算（図１Ａの演算ＯＰ３）は非構造化ベクトル量子化器の場合におけるよりより多くの計算を必要とする。
置換を計数する幾つかの方法が存在する。シャルクビック（Schalkwijk）アルゴリズムはこれらの方法の１つである：
シャルクビックＪ．Ｐ．Ｍ（Schalkwijk J.P.M）著「ソース符号化アルゴリズム（An Algorithm for source coding）」、情報理論に関するＩＥＥＥ論文誌、ＩＴ１８巻３号、ページ３９５−３９９、１９７２年５月
結合分析を使用して、これらの技術は置換符号の符号ベクトルの指標指定（演算ＯＰ２）およびまた逆指標復号化演算（ＯＰ３）の実行を可能にする。置換指標指定アルゴリズムの中では、一般に使用するシャルクビックアルゴリズムを以下に例えば次の規格において検討している。
−［３ＧＰＰ  ＴＳ２６．２７３］（固定点拡張ＡＭＲ−広帯域（ＡＭＲ−ＷＢ＋）コーデック；Ｖ６．１．０（２００５−０６）（レリース６））および
−［３ＧＰＰ  ＴＳ２６．３０４］（拡張適応型多元速度−広帯域（ＡＭＲ−ＷＢ＋）コーデック；浮動点ＡＮＳＩ−Ｃ符号；Ｖ６．３．０（２００５−０６）（レリース６）、２００５年６月）。
【００１９】
符号化における置換ランクの計算（図１Ａの演算ＯＰ２）
【００２０】
これはベクトルｙ＝（ｙ０、ｙ１．．．、ｙｎ‐１）の構成要素に関する全ての可能な置換の順序化および指標指定を含む。順序は辞書編集式であり、指標をここでは「ランク」と呼ぶ。ベクトルｙのランクの計算は、ｙに関連し、ｙｋ＝ａｄであり、その場合にのみｄｋが指標値ｄを有するようなベクトルＤ＝（ｄ０、ｄ１．．．、ｄｎ‐１）のランクの計算を含む。
例えば、次元ｎ＝８のベクトルは以下の構成要素を有する。
ｙ＝（４、２、４、０、０、４、４、２）
ｑ＝３の文字（異なる値の構成要素）を持つアルファベットをａ０＝４、ａ１＝２およびａ２＝０であるＡ＝｛４、２、０｝により示す。
次いで、ベクトルｙはベクトルｙとベクトルＤ＝（０、１、０、２、２、０、０、１）を関連させ、その構成要素は単にアルファベットＡのｑ文字の指標である。
ｙおよびＤのランクは同じであるが、ベクトルＤの定義は（アルファベット｛ａ０、ａ１、．．．、ａｑ−１｝と同じ数の要素を含む）セット｛０、１、．．．、ｑ−１｝にその値を有するシーケンスＤのランクの計算に演算を削減する。
ベクトルｙおよびＤの重みが同じであるのはそのそれぞれの構成要素の発生が同じであるからである。中間重み（ｗｋ０、ｗｋ１、．．．、ｗｋｑ−１）をまた構成要素ベクトル（ｙｋ、ｙｋ＋１、．．．、ｙｎ−１）の重みとして定義し、それ故この重みは位置ｋ乃至ｎ−１を残すために端を切取るベクトルｙに対応する。従って、
【００２１】
【数６】
2009527171.tif 000007
【００２２】
であり、δ（ｘ、ｙ）はクロネッカ（Kronecker）演算子（ｘ＝ｙであればδ（ｘ、ｙ）＝１であり、他の場合０）である。
次式を適用する。
【００２３】
【数７】
2009527171.tif 000008
【００２４】
ベクトルｙのランクｔを下記の公式により結合分析により計算することができる。
【００２５】
【数８】
2009527171.tif 000009
【００２６】
この公式は以下のように単純化することができる。
【００２７】
【数９】
2009527171.tif 000010
【００２８】
使用することが多く、それ故ここで採用することにするのはこの後者の公式である。以後、Iｋｄｋを「順序ｋの部分ランク」と呼び、以下の通りとする。
【００２９】
【数１０】
2009527171.tif 000011
【００３０】
ランクの復号化（演算ＯＰ３）：置換のその指標からの判断
【００３１】
ランクｔの復号化はｙに関連するベクトルＤ＝（ｄ０、ｄ１、．．．、ｄｎ−１）の回復を伴う。ｄｋの連続検索の一方法を以下に説明する。構成要素ｄ０をまず判断し、構成要素ｄ１乃至構成要素ｄｎ−１により継続する。
【００３２】
＊ｄ０の判断：
ｄ０を以下の不等式を含む公式の使用により見つける。
【００３３】
【数１１】
2009527171.tif 000012
【００３４】
項（ｎ−１）！、ｔ、
【００３５】
【数１２】
2009527171.tif 000013
【００３６】
およびｄ＝０、．．．、ｑ−１に対する値ｗ０ｄは既知である。ｄ０の値を見つけるために、出発点としてｄ０＝０を使用し、上記の数１１に示す公式（８）を満たすまでｄ０を連続して１だけ増やす。部分ランクにより上記の数１１に示す公式（８）を書くことにより、値ｄ０は次のようになる。
【００３７】
【数１３】
2009527171.tif 000014
【００３８】
＊ｄ１の判断：
ｄ１を見つけるために、以下の関係を使用する。
【００３９】
【数１４】
2009527171.tif 000015
【００４０】
ｄ＝０、．．．、ｑ−１に対するｗ１ｄの値は以下のようにｗ０ｄの値から推論する。
−ｄ＝ｄ０であれば、ｗ１ｄ＝ｗ０ｄ−１および
−ｄ≠ｄ０であれば、ｗ１ｄ＝ｗ０ｄ（次いでｄがｄ０と異なる限りｗ０ｄを反復する）。
構成要素ｄ０の判断と同じ問題に戻る。ｄ１の値を見つけるために、出発点としてｄ１＝０を使用し、不等式（９）を満たすまでｄ１を連続して１だけ増やす
（Ｉ１ｄ１≦ｔ−Ｉ０ｄ０＜Ｉ１ｄ１＋１）。
【００４１】
＊その他のｄｋの判断：
【００４２】
後続するｄｋの計算は上記の場合から推論する。ｄｋの値を見つけるために、出発点としてｄｋ＝０を使用し、不等式
【００４３】
【数１５】
2009527171.tif 000016
【００４４】
を満たすまでｄｋを連続して１だけ増やす。
一度ベクトルＤ＝（ｄ０、ｄ１、．．．、ｄｎ−１）を復号化すると、単なるアルファベットの転位によりベクトルＤからベクトルｙを推論する。
【特許文献１】ＷＯ−０４／００２１９
【非特許文献１】シャルクビックＪ．Ｐ．Ｍ（Schalkwijk J.P.M）著「ソース符号化アルゴリズム（An Algorithm for source coding）」、情報理論に関するＩＥＥＥ論文誌、ＩＴ１８巻３号、ページ３９５−３９９、１９７２年５月
【非特許文献２】［３ＧＰＰ  ＴＳ２６．２７３］（固定点拡張ＡＭＲ−広帯域（ＡＭＲ−ＷＢ＋）コーデック；Ｖ６．１．０（２００５−０６）（レリース６））
【非特許文献３】［３ＧＰＰ  ＴＳ２６．３０４］（拡張適応型多元速度−広帯域（ＡＭＲ−ＷＢ＋）コーデック；浮動点ＡＮＳＩ−Ｃ符号；Ｖ６．３．０（２００５−０６）（レリース６）、２００５年６月）
【非特許文献４】ラゴット  Ｓ、べセット  Ｂ、ルフェーブル  Ｒ著「３２ｋビット／秒における広帯域ＴＣＸ通話符号化に適用する低複雑度多元速度格子ベクトル量子化」ＩＣＡＳＳＰ論文集、１巻、ＰＰ．５０１−４、２００４年５月
【発明の開示】
【発明が解決しようとする課題】
【００４５】
置換符号の指標指定および逆演算は複雑な演算である。使用するアルゴリズムは結合分析を適用する。結合の指標指定および逆演算は階乗積の除算を必要とする。
【００４６】
除算の複雑度
集積回路および信号処理プロセッサにおいてなされた進歩にもかかわらず、除算は複雑な演算に留まる。典型的に、１６ビットで表す整数の１６ビットで表す整数による除算はそれらの乗算より１８倍のコストを要する。３２ビットの整数の１６ビットの整数による除算の重みは３２であり、それらの乗算の重みは５である。
【００４７】
変数のフレーム化
除算コストは問題であるだけではない。以下の表１が示すように、変数のフレーム化は別の問題である。
８以下の整数の階乗のみを全１６ビットワードで表すことができる。１２より大きな数の場合、全３２ビットワードにおける階乗の表現は最早可能ではない。
さらに演算の複雑度は、また変数を表すのに使用するビット数と共に増大する。従って、３２ビットの整数の１６のビット整数による除算は１６ビットの整数の除算（重み１８）の殆ど２倍複雑（重み３２）である。
【００４８】
【表１】
2009527171.tif 000017
【００４９】
演算ＯＰ１の複雑度を削減する解決法が提案されている。演算ＯＰ２およびＯＰ３の複雑度の問題は極めて適切には扱われていない。一方、特に出願者のＴＤＡＣ符号化器／復号化器では、または３ＧＰＰ−ＡＮＲ−ＷＢ＋符号化器では、シャルクビック公式に基づき符号化および復号化に対し単純化が行われている。
【００５０】
置換および逆演算（演算ＯＰ２およびＯＰ３）の計数の単純化
【００５１】
ｎ項Ｉｋｄｋの計算に対して行った下記の単純化により、置換ランクｔおよび逆演算の計算は加速され、その定義を以下で検討する。
【００５２】
【数１６】
2009527171.tif 000018
【００５３】
最初の２つの項を使用して、符号化および復号化双方における複雑度を削減する。第３の項を符号化に使用し、最後に残る２つの項を復号化に使用する。
【００５４】
符号化技術を図２および図３により説明する。特に、図３は従来技術の意味するシャルクビック公式によるランクの計算を扱い、一方図２は予備ステップ（「ＥＰ−ｎと参照し、図２のｎ番目の予備ステップを示す）を説明する。
【００５５】
図２を参照すると、処理はステップＥＰ−１で始まり、ベクトルｙ＝（ｙ０、ｙ１．．．、ｙｎ‐１）の構成要素を回復する。後続の一般的ステップＥＰ−２はこのベクトルＡ＝（ａ０、ａ１、．．．、ａｑ−１）に使用するアルファベット要素の計算、および最大指標ｑの判断を扱う。これを行うためにｑ＝１、ａ０＝ｙ０を設定する初期化ステップＥＰ−２１の後に、１とｎ−１との間の指標ｋに関してループを実行し（検査終了ＥＰ−２６およびその他の場合増分ＥＰ−２７）、以下のように要素ａｑを検索する。
−現指標ｋの構成要素ｙｋが要素｛ａ０、ａ１、．．．、ａｑ−１｝の中に既になければ（検査ＥＰ−２２）、セット｛ａ０、ａ１、．．．、ａｑ−１｝に対してａｋ＝ｙｋ（ステップＥＰ−２２）であるように新要素ａｑを割り当てねばならず、ｑを１だけ増分しなければならない（ステップＥＰ−２５）。
【００５６】
後続の一般的、予備ステップＥＰ−３は以下のようにベクトルＤ＝（ｄ０、ｄ１、．．．、ｄｎ−１）の計算である。
−０乃至ｎ−１の範囲のｋに対して（ｋを０に初期化するステップＥＰ−３１、ｋに関する検査終了ＥＰ−３１、その他の場合増分ＥＰ−３８）、ｙｋ＝ａｋであるような値ｄを指標セット（０、．．．、ｑ−１）において見つける（ループにおけるｄに関する検査ＥＰ−３３、その他の場合ｄ＝ｄ＋１による増分ＥＰ−３６）。
【００５７】
図３を参照して次に、図２に示す予備処理に続くランクｔの計算ステップの説明に進む。図３に示すステップは「ＣＡ−ｎ」と参照し、従来技術の意味するｎ番目の符号化を意図する。
【００５８】
ステップＣＡ−１はランクｔの０、変数Ｐの１（ステップＣＡ−１３におけるランクの計算に使用する分母）およびｑの重みｗ０、ｗ１、．．．、ｗｑ−１の０への初期化である。
【００５９】
ここで、ｋの値をｎ−１から０へ減分する（ｋをｎ−１に初期化するステップＣＡ−２、検査終了ＣＡ−１４およびその他の場合減分ＣＡ−１５）。このような選択の利益を後に説明する。予備ステップＥＰ−３において得るベクトルＤの構成要素ｄｋを次いで使用し、現行ｋに対しｄ＝ｄｋを設定する（ステップＣＡ−３）。関連する重みｗｄを更新し（ステップＣＡ−４においてｗｄ＝ｗｄ＋１）、項Ｐを推定する（ステップＣＡ−５においてＰ＝Ｐｘｗｄ）。ステップＣＡ−１３に対応するランクの計算における分子に関して使用する総計Ｓを０に初期化し（ステップＣＡ−６）、次いで重みｗｉの指標ｉに関してループを実行し（検査終了ＣＡ−９およびその他の場合ｄ−１へ増分ＣＡ−１０）、総計Ｓを更新する（ステップＣＡ−８においてＳ＝Ｓ＋ｗｉ）。ステップＣＡ−１３におけるランクｔの計算の前に調査を行い、総計Ｓがゼロでないことを確認する（検査ＣＡ−１１）。この実施の利益を後に説明する。
【００６０】
ランクｔの計算（ステップＣＡ−１３）は以下のような階乗項（ｎ−ｋ−１）！を含む。
ｔ＝ｔ＋（Ｓ／Ｐ）（ｎ−ｋ−１）！
【００６１】
ランクｔの各更新に関する項（ｎ−ｋ−１）！の計算に代わって、これらの値をメモリに事前記録し、簡単なメモリアクセスを使用して（ステップＣＡ−１２）、（ｎ−ｋ−１）！の現行値を得ることを優先する。
【００６２】
従って、図３に示す処理の幾つかの利点を再び本発明の実施において取り上げることにする。これらの利点を以下に詳記する。
【００６３】
＊階乗の蓄積
【００６４】
項（ｎ−ｋ−１）！およびｗｋｉ！を実時間で計算することを避けるために、ｎ＋１の階乗（０！、１！、．．．、ｎ！）の値を事前に計算し、蓄積する。次元ｎが限定的に変化すれば（ｎ≦ｎｍａｘ）、値０！、１！、．．．、ｎｍａｘ！を事前に計算し、蓄積する。
【００６５】
＊除算を避ける中間重みの累積に関する検査
【００６６】
項Ｓｋ
【００６７】
【数１７】
2009527171.tif 000019
【００６８】
がゼロであれば、
【００６９】
【数１８】
2009527171.tif 000020
【００７０】
の計算に意味がない。次にこの項は、最終位置（ｎ−１に近いｋ）の場合特にゼロであることが多い。この項がゼロである性質に関する検査（図３の検査ＣＡ−１１）の追加により、除算（および乗算）を避けることができる。除算の計算は検査よりかなり複雑であるので、複雑度の除外は大きい。
【００７１】
＊符号化における位置に関するループの反転
【００７２】
１だけｗｋ＋１ｄを増分し、ｄ≠ｄｋに対してその他の値ｗｋ＋１ｄを反復することにより、重みｗｋ＋１ｄから（ｄ＝０、１、．．．、ｑ−１である）重みｗｋｄを推論する。その場合、ベクトルの最終位置（ｋ＝ｎ−１）から最初の位置（ｋ＝０）へ動作するループ（図３のステップＣＡ−２、ＣＡ−１４、ＣＡ−１５）を作成することが可能である。この「逆」ループは、１に初期化後項Ｐｋを以下のように、
【００７３】
【数１９】
2009527171.tif 000021
【００７４】
各反復に対して、増分および乗算のみ、即ち
【００７５】
【数２０】
2009527171.tif 000022
【００７６】
により計算することを可能にする。
最後の２つの位置（ｋ＝ｎ−１およびｋ＝ｎ−２）を個別に処理することがまた可能である。要するに、
・最後の位置（ｋ＝ｎ−１）について、
【００７７】
【数２１】
2009527171.tif 000023
【００７８】
それ故
【００７９】
【数２２】
2009527171.tif 000024
【００８０】
・最後から２番目の位置（ｋ＝ｎ−２）について、
ｄｎ−２＞ｄｎ−１であれば、
【００８１】
【数２３】
2009527171.tif 000025
【００８２】
それ故
【００８３】
【数２４】
2009527171.tif 000026
【００８４】
その他の場合
【００８５】
【数２５】
2009527171.tif 000027
【００８６】
それ故
【００８７】
【数２６】
2009527171.tif 000028
【００８８】
であり、ｄｎ−２＝ｄｎ−１であれば、Ｐｎー２＝２、その他の場合
Ｐｎー２＝１である。
【００８９】
下記のその他の有利な実施の詳細をまた提供することができる。
【００９０】
＊復号化における除算の除去
【００９１】
ｄ０を検索する場合に復号化における除算を避けるために、数１１に示した不等式（８）を以下の形式に再公式化することができる。
【００９２】
【数２７】
2009527171.tif 000029
【００９３】
同様に、数１４に示した不等式（９）を以下の形式に再公式化することにより、ｄ１の検索から除算を除去する。
【００９４】
【数２８】
2009527171.tif 000030
【００９５】
またはさらに、
【００９６】
【数２９】
2009527171.tif 000031
【００９７】
従ってｄｋ（０≦ｋ≦ｎ−１）の検索における除算の削除は可能であるが、Ｉｋｄｋ（０≦ｋ≦ｎ−３）の計算に（ｎ−１）除算の実行がなお必要である。
【００９８】
＊復号化における重みに関する検査
【００９９】
ｄのある値に対する最後の位置では、（位置ｋに先行する位置を占める値ｄのｗ０ｄの構成要素に対して）ｗｋｄ＝０である。ｄのこれらの値に対し不等式（８）および（９）の項を計算するのはそれ故意味がない。
【０１００】
従来技術のその他の問題：変数のフレーム化
【０１０１】
変数フレーム化の問題は出願者のＴＤＡＣ符号化器において取組んでいる。
第１の解決法は１２より大きな次元の処理演算をより小さな次元の演算と区別することであった。小さな次元（ｎ＜１２）の場合、３２ビットの符号のない整数に関して計算を実行する。より大きな次元の場合、計算複雑度および必要なメモリ容量の増大を犠牲にして、倍精度浮動変数を使用する（浮動倍精度演算はその整数精度に等価な演算よりより経費が掛かる）。
【０１０２】
さらに最大精度を符号のない３２ビットの整数（固定点プロセッサによる実施）に限定すれば、１２より大きな整数階乗を直接事前蓄積することはできず、１２より大きな次元のベクトルを個別に符号化しなければならない。この問題を解決するために、さらに高度な解決法は２ｊ×ｒの形式の階乗ｎ！の仮数および指数による擬似浮動点表現を使用する。この分解を以下の表２に詳しく示す。ｎ！の蓄積（１６以下のｎの場合）を最大３０ビットの精度を持つｒ並びに簡単なビットオフセットに対応する指数ｊの蓄積に削減する。
【０１０３】
【表２】
2009527171.tif 000032
【０１０４】
従って、大部分の場合従来技術は特に固定点における限定精度の変数フレーム化の問題を解決しない。ＴＤＡＣ符号化器における実施は、フレーム化問題を解決するが、２つの整数の経費の掛かる除算を回避しない。
【０１０５】
さらに大きな次元の場合、中間計算（例えば、部分ランクＩｋｄｋの分子および分母）は限界状態に近づきうる。この場合、上記の単純化を復号化処理に使用することができず、数１１および数１４に示した不等式（８）および（９）の公式化への逆戻りが必要であり、それ故多くの除算を再び持ち込まねばならない。
【０１０６】
シャルクビック技術以外の計数技術は同じ問題に苦しむ。計数技術がまた結合分析を使用する場合、計数技術は階乗積とその除算の計算を伴う。
【０１０７】
本発明はこの状況の改善を目的とする。
【課題を解決するための手段】
【０１０８】
このため、本発明はまず結合表現の計算を含む置換符号を使用するディジタル信号の符号化／復号化法を提案し、本方法ではこれらの結合表現を素因数累乗分解により表し、選択する整数の事前記録分解表現をメモリから読出すことにより判断する。
【０１０９】
次いで本発明は置換符号の指標指定および逆演算双方に関連する問題への効果的な解決法を提供する。同時に本発明は変数フレーム化および除算である２つの問題を解決する。
要するに有利な実施では、事前記録表現は前記選択する整数のそれぞれの連続する素数を表す値と相関してそれぞれ蓄積する指数を表す値を含む。
従来技術における変数フレーム化に関連する問題を従って既に解決する。
変数フレーム化の問題は階乗項を操作する場合、益々重大である。
有利な実施では、結合表現が整数の階乗値を含む場合結合表現を操作するために、事前記録表現は少なくとも階乗値の分解表現を含む。
次いでこの実施は変数フレーム化の制約を取除き、そのことから関係する置換符号の次元ｎに関して通常設定する制限を緩和することを可能にする。
【０１１０】
別の有利な特徴によれば、前記結合表現の少なくとも１つは整数の分子の整数の分母による商を含み、この商を素因数累乗分解により表し、素因数累乗分解の各累乗は分子および分母とそれぞれ関連し、１つのかつ同じ素数に割当てる指数の差分である。
従来技術の除算の計算に関連する問題は従って単純な減算計算によりこの計算を置換することにより解決する。
【０１１１】
第１の実施形態では、上述の選択する整数の１つの事前記録分解を取出すためにアドレス指定するメモリの配備を行う。
このため、選択する整数の事前記録表現をアドレス可能なメモリに蓄積し、前記メモリのアドレス指定はそれぞれの素数に割当てる連続する指数を示し、選択する整数を再構成する。
好ましくは、選択する整数の事前記録表現を素数に対し連続するアドレス形式で蓄積することとし、各アドレスはこの素数に割当てる指数を示し、選択する整数を再構成する。
第１の実施形態によるこの実施を以後「分解の分解による相互関係表現」と名付けることにする。
【０１１２】
変形として第２の実施形態では、連続するビットグループを含むワード形式で、事前記録表現を蓄積し、各グループは：
−素数に応じる重み、および
−この素数に関連する指数に応じる値を
有する。
好ましくは次いで、少なくとも１つの部分マスクをビットワードに連続的に適用することにより、ビットの重みによる連続オフセットおよび残るビットの読出しにより、素因数累乗を判断する。
第２の実施形態によるこの実施を以後「分解のコンパクトな表現」と名付けることにする。
【０１１３】
結合表現の計算の同じ方法の処理を、一般に次の：
−前記結合表現を形成する積および／または商に現れる項を前記選択する整数から特定するステップと、
−前記項の素因数分解に含む指数をメモリにおいて読出すステップと、
−読出した指数を加算および／または対応して減算し、前記結合表現の素因数累乗分解に含む指数を判断し、そのことからその素因数累乗分解から前記結合表現を計算するステップと、
により実行することができる。
【０１１４】
再起的に実行する積の計算および各再起に新しい項を含むことに関し、以前の再起に対して実行した積の計算の分解を一時的に蓄積するのは有利でありうる。従って、本方法が以前の再起において判断した積を乗算する項を各再起に含む積の計算に再起ステップを含めば、
−以前の再起において判断した前記積を有利には素因数累乗分解の形式でメモリに保持し、
−積を乗算する前記項が好ましくは分解を事前記録する選択する整数の１つであり、
−現再起における前記積を判断するために、以前の再起において判断した前記積および前記積を乗算する前記項のそれぞれの分解から導出する指数を共に１つずつ各素数に対し加算すれば十分である。
【０１１５】
同様に、本方法が以前の再起において判断した商を除算する項を各再起において含む除算の計算に再起ステップ含めば、
−以前の再起において判断した前記商を有利には素因数累乗分解の形式でメモリに保持し、
−商を除算する前記項が好ましくは分解を事前記録する選択する整数の１つであり、
−現再起における前記除算を判断するために、前記項の分解から導出する指数を以前の再起において判断した前記商の分解から導出する指数から１つずつ各素数に対し減算する。
再起的に計算する積および／または商に関する中間分解のこの一時的蓄積は再起部分ランクの判断に特に有利であり、再起部分ランクの累積は置換ランクを表す。
【０１１６】
従って本発明の有利な実施では、置換符号は各部分ランクが次いで前記結合表現の１つに対応する部分ランクの累積を含む置換ランクを表す量の計算を含む。
ベクトル量子化ディジタル信号を符号化する場合、次いで置換ランクの計算を使用し、入力ベクトルに最も近い符号ベクトルを判断するために以前のステップ（演算ＯＰ１）において実行した先導ベクトルの構成要素の置換を指標指定することができる（図１Ａの演算ＯＰ２）。
【０１１７】
同様にベクトル量子化ディジタル信号を復号化する場合に、置換ランクの所与の値から
−構成する符号ベクトルの少なくとも１つの仮定する構成要素に従い前記所与の値に近い置換ランクを表す少なくとも１つの量を計算し（図１Ａの演算ＯＰ３）、
−この量が所与のランク値との近接条件を満たせば仮定する構成要素の選択が妥当である
として置換ランクの推定が行われる。
実施例では、一方で仮定する構成要素に関連する部分ランクへおよび他方で仮定する構成要素の増分に対応する構成要素に関連する部分ランクへの部分ランクの累積により所与のランク値を纏めて扱うことができれば、この近接条件を満たす。
それ故、この近接条件はシャルクビック計数の場合の上記の不等式（８）の一般的公式化に対応しうる。
従って、本発明を有利には図１Ａの意味するベクトル量子化によるソース符号化／復号化に適用することができる。
一方、符号化／復号化が、
−送信前における置換ランクからの符号ベクトルの判断（図１Ａおよび図１Ｂの同じ演算ＯＰ３）および
−受信時における受信ベクトルに対応する符号ベクトルからの置換ランクの計算（図１Ａおよび図１Ｂの同じ演算ＯＰ２）
を含めば、符号化／復号化はまた図１Ｂの意味するチャネル変調符号化／復号化タイプに関するものでありうる。
【０１１８】
部分ランクの計算は、後に見られるであろうように一般的規則として置換符号の最大次元ｎ以下に留まる（積または商における）項を含む。従って有利な実施では、事前記録分解を伴う選択する整数は少なくとも、
−１と前記最大次元ｎとの間の整数と、
−整数０の階乗値と、
−好ましくは１と最大次元ｎとの間の整数の階乗値
を含む。
特定の選択可能な実施では、選択する整数はまた値０を含むことができる。
【０１１９】
従って、置換符号がシャルクビック計数を使用すれば、符号ベクトル（ｙ０、．．．、ｙｎ‐１）の切取り（ｙｋ、．．．、ｙｎ−１）に関連する部分ランクＩｋｄｋを、
【０１２０】
【数３０】
2009527171.tif 000033
【０１２１】
により表し、上式で、
−記法
【０１２２】
【数３１】
2009527171.tif 000034
【０１２３】
は０乃至ｍの範囲の整数指標ｉに対する積を表し、
−記法
【０１２４】
【数３２】
2009527171.tif 000035
【０１２５】
は０乃至ｍの範囲の指標ｉに対する総和を表し、
−記法ｌ！はｌ＞０の場合ｌ！＝１×２×３×．．．×（ｌ−１）×ｌであり、０！＝１である整数ｌの階乗値であり、
−整数ｎは符号ベクトルが含む構成要素の総数に対応する置換符号の次元であり、
−０とｎ−１との間の整数ｋは、ソース復号化における（対応してチャネル符号化における）ランク値から検索するかまたは置換をソース符号化において（対応してチャネル復号化において）指標指定する符号ベクトルのｋ番目の構成要素ｙｋの指標であり、
−整数ｑは符号ベクトルが含む個別構成要素数であり、
−項ｗｋｄ（「中間重み」と名付ける）はｋとｋ−１との間の指標を有し、１つのかつ同じ指標構成要素ｄの数に等しい値を有する構成要素の数を表す。
【０１２６】
この場合、事前記録分解を有し、次いで部分ランクＩｋｄｋの表現において、積および／または商において特定する、選択する整数は好ましくは、
−０とｎ−１との間の全ての整数ｋに対する階乗項（ｎ−１−ｋ）！（即ち、０と（ｎ−１）との間の全ての整数に対する階乗値）であり、
−各項ｗｋｉの値および／または各項ｗｋｉが０とｎとの間にある積
【０１２７】
【数３３】
2009527171.tif 000036
【０１２８】
に含むその階乗値であり、
−０とｎ−１との間の全ての整数ｋに対して、各項が１とｎ−１との間にある項
【０１２９】
【数３４】
2009527171.tif 000037
【０１３０】
である。
【０１３１】
さらにシャルクビック計数の特定の場合では、中間分解の一時蓄積を有利に以下のように適用する：先行指標ｋに対する項
【０１３２】
【数３５】
2009527171.tif 000038
【０１３３】
の分解における指数の総和を一時的にメモリに蓄積し、指数の総和にまたは指数の総和から現指標ｋに対する項ｗｋｉの分解指数を加算または減算する。
【０１３４】
本発明のその他の特徴および利点は、以下の「発明を実施するための最良の形態」および上記の図１Ａ、図１Ｂ、図２および図３に加えて図４乃至図９の添付する図面を考察することにより明らかになるであろう。
【０１３５】
思い出す契機として、特に以下の図４乃至図８を参照して、下記のことを強調すべきである。
−用語「符号化する」は置換ランクｔの計算を指示し（図１Ａおよび図１Ｂの演算ＯＰ２）、
−用語「復号化する」はこのランクｔからの置換の判断を指示する（図１Ａおよび図１Ｂの演算ＯＰ３）。
従って、これらの演算をベクトル量子化によるソース符号化／復号化の参照により指定する。これらの演算をまたチャネル符号化／復号化、変調において実行することができることを思い出すべきである。
【０１３６】
本発明の原理を単刀直入に示すために、素数累乗の階乗化を以下に説明する。
ゼロでない正整数Ｋの素数累乗への分解を以下のように表す。
【０１３７】
【数３６】
2009527171.tif 000039
【０１３８】
上式で、ｐｉはｉ番目の素数である（ｐ０＝１、ｐ１＝２、ｐ２＝３、ｐ３＝５、ｐ４＝７、ｐ５＝１１、ｐ６＝１３、ｐ７＝１７、など）。
ｐｉの指数を整数Ｋの分解ではｅＫｉと表示し、ｍＫはゼロでない指数を持つＫの分解に含む最大の素因数の指標を表示する。
例えば、数Ｋ＝１２０（または５！）を次のように表す。
１２０＝１．２３．３１．５１であり、最大の素因数「５」が指標３を有するので（ｐ３＝５）、ここではｍＫ＝３である。それ故、以下が当てはまる：ｅ５！０＝１、ｅ５！１＝３、ｅ５！２＝１およびｅ５！３＝１。
実際には、数「１」は乗算の中立の要素であり、ｐ０は分解から除くことができる、即ち、以下の通りである。
【０１３９】
【数３７】
2009527171.tif 000040
【０１４０】
勿論、Ｋ＝０は素因数の累乗には分解することはできない。
【０１４１】
１６以下の正整数の素数累乗積への分解を表３ａに示し、その階乗分解を表３ｂに示す。この分解は６つの素数を含む（２、３、５、７、１１および１３）。列を素数ｐｉにより指標指定し、行をｎにより指標指定するので、列ｐｉと行ｎの交点における表３ａ（対応して表３ｂ）のセルは数ｎ（対応してｎ！）の素数の累乗積分解における素数ｐｉの指数ｅｎｉ（対応してｅｎ！ｉ）である。
ｎ＞１の任意の正整数の場合、ｎ！の素因数の数ｍｎ！は次の通りである：ｐｍｎ！≦ｎ＜ｐｍｎ！＋１。数ｍｎ！（対応して数ｍｎ）を表３ｂ（対応して表３ａ）の最終（対応して最後から２番目の）列に示した。次の不等式に留意すべきである：ｍｎ≦ｍｎ！。
表３ａが示すように、数ｎの多くの分解指数はゼロである。表３ａの最終列に、ｎの分解におけるゼロでない指数ｍｎ１を注記した。ｎ＝０の場合分解の（それ故指数の）ないことを表３ａの行ｎ＝０に記号「−」により示す。
【０１４２】
【表３ａ】
2009527171.tif 000041
【０１４３】
【表３ｂ】
2009527171.tif 000042
【０１４４】
最初にシャルクビック公式の場合、次いで一般の場合の置換符号に関する部分ランクの計算へのこのような分解の適用に関する説明に進む。
Ｉｋｄｋと表示する部分ランクが本明細書の上記の数１０に示した関係式（７）により示されることを思い出すべきである。
【０１４５】
【数３８】
2009527171.tif 000043
【０１４６】
本式では、３つの項を素数累乗に分解することができる。これらは次の項である。
【０１４７】
【数３９】
2009527171.tif 000044
【０１４８】
（ｎ−１−ｋ）！、ＰｋおよびＳｋの分解指数から、Ｉｋｄｋの分解指数を簡単な加算および減算により計算する。
要するに、Ｉｋｄｋの分解における素因数ｐｉの指数
【０１４９】
【数４０】
2009527171.tif 000045
【０１５０】
を３つの項（ｎ−１−ｋ）！、ＳｋおよびＰｋの分解におけるｐｉの３つの指数から計算する。指数
【０１５１】
【数４１】
2009527171.tif 000046
【０１５２】
は最初の２つの項（Ｉｋｄｋの分子）のｐｉの指数の総和に等しく、指数の総和から最後の項（Ｉｋｄｋの分母）のｐｉの指数を減算する。一度公式化し、この結果を次のように表す。
【０１５３】
【数４２】
2009527171.tif 000047
【発明を実施するための最良の形態】
【０１５４】
図４は、符号化および復号化のために共に本発明の意味する処理演算に含むことができる（ｎ番目の一般的ステップを表すために「Ｇ−ｎ」と参照する）一般的ステップを示す。
【０１５５】
従って図４を参照して、現指標ｋから（ステップＧ−１）および後に詳細に説明することにする幾つかの中間ステップにより、（図４に例示するステップＧ−２においてＤｌおよびＤｌ！と表示する）事前記録表を参照する配備を行い、本明細書の以上の式（１０）により、素因数累乗における中間ランクＩｋｄｋの分解に特定のグローバル指数
【０１５６】
【数４３】
2009527171.tif 000048
【０１５７】
を計算する（ステップＧ−３）ことを就中思い出すべきである。素因数に特定の指標ｉに関するループを実行することにより恐らくこれ（ステップＧ−４）から、中間ランクＩｋｄｋの値を次いで推論する。次いでこの中間ランクの計算は置換の全ランクｔの更新を、
−指標ｋの減分によるランクの符号化のためのタイプの関係式ｔ＝ｔ＋Ｉｋｄｋ（ステップＧ−６）によるかまたは
−後述のように、指標ｋの増分によるランクの復号化のためのタイプの関係式ｔ＝ｔ−Ｉｋｄｋ（ステップＧ−６）により、
継続することができる（ステップＧ−５）。
【０１５８】
最後に、ステップＧ−７の符号化または復号化（図４の破線）において置換のランクｔを得、ベクトルＤの構成要素ｄｋをステップＧ−８における以上の公式（８）の不等式および本明細書の以上の式ｙｋ＝ａｄによるベクトルＹに関する不等式から推論する。
【０１５９】
一般の場合およびシャルクビック計数とは独立に、置換の部分ランクｔ’（ｔ’＞０）が以下のようにＮｔ’の項ｖｊ（１≦ｊ≦Ｎｔ’）を有する分子およびＤｔ’の項ρｊ（１≦ｊ≦Ｄｔ’）を有する分母の形式であれば、
【０１６０】
【数４４】
2009527171.tif 000049
【０１６１】
その場合、部分ランクｔ’の分解指数ｅｔ’ｉをＮｔ’ｖｊおよびＤｔρｊの分解である中間分解から判断し、ｅｔ’ｉを以下のように表す。
【０１６２】
【数４５】
2009527171.tif 000050
【０１６３】
素因数への分解をまた本明細書で後に部分ランクｔ’の整数の商の積への公式化に使用することにする。
また一般的規則として、
【０１６４】
【数４６】
2009527171.tif 000051
【０１６５】
であれば、その場合
【０１６６】
【数４７】
2009527171.tif 000052
【０１６７】
である。
【０１６８】
シャルクビック計数の特定の場合に戻り、次いで一度この分解を判断し、その分解から部分ランクＩｋｄｋを計算するために、計算を次のように実行することができる。
式
【０１６９】
【数４８】
2009527171.tif 000053
【０１７０】
の精神を守り、単に対応する累乗の乗算により部分ランクＩｋｄｋを以下のように計算する。
【０１７１】
【数４９】
2009527171.tif 000054
【０１７２】
ここで、項（ｎ−１−ｋ）！およびＰｋは厳密に正整数であるが、項Ｓｋはゼロでありえ、それ故分解可能でないことがありうることを示すべきである。この場合、部分ランクＩｋｄｋはゼロである。次いで、項Ｓｋ（Ｓｋ＝０？）の値に関する検査を行い、本明細書の以上の説明（図３のステップＣＡ−１１）のようにＳｋ≠０の場合にのみ部分ランクＩｋｄｋを計算する。
【０１７３】
より一般的には、
【０１７４】
【数５０】
2009527171.tif 000055
【０１７５】
であれば、その場合
【０１７６】
【数５１】
2009527171.tif 000056
【０１７７】
であり、
【０１７８】
【数５２】
2009527171.tif 000057
【０１７９】
であれば、その場合
【０１８０】
【数５３】
2009527171.tif 000058
【０１８１】
である。
【０１８２】
次いで、素因数累乗の乗算により、特にこれらの素数に関連する指数の簡単な加算および減算により除算を置換することにより、部分ランクを構成する項の素因数階乗化が除算の排除を可能にすることを思い出すであろう。
【０１８３】
従って、本発明の意味するメモリに蓄積する整数の素因数分解（以後「基本分解」と呼ぶ）の限られた数から、
−図４のステップＧ−２の意味する置換ランクに現れる
【０１８４】
【数５４】
2009527171.tif 000059
【０１８５】
のような項の素因数分解（本明細書で以後「中間分解」と呼ぶ）を判断し、
−図４のステップＧ−３の意味する特にこの部分ランクの分解に含む指数の（例えば、
【０１８６】
【数５５】
2009527171.tif 000060
【０１８７】
タイプの式による）計算により、これらの中間分解から置換の部分ランクｔ’（Ｉｋｄｋ）の素因数分解を判断し、
−図４のステップＧ−４の意味する部分ランクｔ’（Ｉｋｄｋ）をその分解から（例えば、
【０１８８】
【数５６】
2009527171.tif 000061
【０１８９】
タイプの式を使用して）計算する、
以上のステップを配備する。
【０１９０】
勿論、蓄積する基本分解は好ましくは有利な選択の対象である。好ましいが、限定しない実施では、関係する置換符号の最大次元（この最大次元をｎと表示する）により、蓄積する基本分解を選択することにする。従って、基本分解は好ましくは：
−整数ｌの階乗（ｌ！と表示する）の分解であり、整数ｌは０≦ｌ≦ｎであり、
−整数ｌ自体の分解であり、この場合０≦ｌ≦ｎであり、
ｎは関係する置換符号の最大次元であることを思い出すであろう。
【０１９１】
次いで、
−考察する素因数の数ｍ、
−これらｍの素因数自体および
−そのそれぞれの指数
を付与する数ｍにより基本分解を特定することが可能である。
分解の所謂「分解相互関係」表現のコンテキストにおいて表４ａ乃至表４ｄを参照して、この実施例を後に説明することにする。後に詳しく説明する所謂「コンパクトな」表現は単一のワードの蓄積にあり、ワードのビットは分解に含む全ての指数を付与することを指摘すべきである。
次いで種々の基本分解セットおよびこれら基本分解の表現および蓄積手順の定義が可能である。
【０１９２】
その上、中間分解を判断する項の選択およびこれら中間分解の判断そのものは後述することにする有利な実施の対象である。部分ランクの分解およびその分解からの部分ランクの計算はまた後述する有利な実施の対象である。
【０１９３】
次に蓄積する基本分解の選択に関する説明に進む。
一般に、次元ｎの置換符号に関する計数技術とは独立に、置換ランクの計算は整数ｌ（０≦ｌ≦ｎ）および就中その階乗ｌ！（０≦ｌ≦ｎ）を使用する。好ましい実施では、基本分解は階乗ｌ！（０≦ｌ≦ｎ）およびｌ（０≦ｌ≦ｎ）の階乗分解であり、ここでｎは本明細書で以上に示したように関係する置換符号の最大次元である。（２ｎ＋１）の基本分解をそれ故この好ましい実施において配備する。
にもかかわらず、その他の実施が可能である。
例えば、（ｎ＋１）の基本分解のみ、即ちｌ（０≦ｌ≦ｎ）および０！の基本分解を配備する必要がある。従って、ｌ！（ｌ＞０）の分解が部分ランクの計算に必要であれば、
【０１９４】
【数５７】
2009527171.tif 000062
【０１９５】
であるｊ（０≦ｊ≦ｌ）のｌの基本分解から中間分解を判断するステップにおいて、ｌ！（ｌ＞０）の分解を計算する。
逆に、ｌ！（０≦ｌ≦ｎ）の（ｎ＋１）の分解のみを配備する必要がある。ｌ（ｌ＞０）の分解が部分ランクの計算に必要であれば、ｌ！および（ｌ−１）！の底を持つ２つの基本分解からおよび以下の式
【０１９６】
【数５８】
2009527171.tif 000063
【０１９７】
から中間分解を判断するステップにおいて、ｌ（ｌ＞０）の分解を計算する。
それ故、基本分解セットの選択が有利にはこれら基本分解表現の蓄積に必要なメモリの最少化と中間分解を判断するステップの複雑度の最小化との間のトレードオフになりうることが理解されるであろう。
【０１９８】
以下で、本発明の意味する分解表現を説明する。
以上に示したように、分解（部分ランク、中間または基本のいずれであれ）を数ｍにより定義し、数ｍは考察する素因数の数、これらｍの素因数およびそのそれぞれの指数を付与する。以下では、分解を表し、基本分解データを蓄積する種々の解決法を提案する。
【０１９９】
指数の分解相互関係表現
【０２００】
＊階乗ｌ！（０≦ｌ≦ｎ）の表現
【０２０１】
値ｌ！の分解に含む素因数の数ｍｌ！は数ｌと共に増加する。ｌ！（０≦ｌ≦ｎ）の分解を表す第１の解決法は、ｌ（０≦ｌ≦ｎ）の各値に対する数ｍｌ！およびｐｉ（０≦ｉ≦ｍｌ！）のｍｌ！の累乗指数の蓄積にある。ｌ！のｍｌ！の指数がゼロでないことを注記することにする。
より有利な変形では、基本分解セットは同じ数ｍｎ！の素因数を共有し、各基本分解に対しｍｎ！の指数を蓄積し、ｍｌ！より大きな指標のｌ！の基本分解指数はゼロである。この解決法は表の正規アドレス指定を提供することによりこの指数表の使用を可能にする。一方このような実施は、かなりのメモリサイズを必要とする。この表はｍｎ！×（ｎ＋１）の値を含み、指数
【０２０２】
【数５９】
2009527171.tif 000064
【０２０３】
をこの表のアドレス（ｍｎ！、ｌ＋（ｉ−１））に蓄積し、ここで記法（ｘ、ｙ）は行ｘおよび列ｙにおけるこの表のセルを目標にする。勿論、その他の規定を考慮することができることは理解されるであろう。従って、ｍ列およびＮ行を有し、それ故ｍ×Ｎセル（または要素）を含む２次元の表を考察する代わりに、ｍ×Ｎセルを有する１次元の表を考察することが可能であり、２次元テーブルのアドレス（ｘ、ｙ）におけるセルはその場合１次元テーブルのアドレスｍ×ｘ＋ｙに位置する。２次元テーブルのアドレス（ｌ、（ｉ−１））に蓄積する指数
【０２０４】
【数６０】
2009527171.tif 000065
【０２０５】
をその場合１次元テーブルのアドレス（ｍｎ！×ｌ＋（ｉ−１））に蓄積する。例えば、構成上表３ｂの４つの列（列ｐｉ＝２、３、５、７）および９つの行（行ｎ＝０、．．８）を含む３６のセルを有する２次元テーブルに、数０乃至８の階乗分解指数を蓄積することができる。本明細書で以下に提示する（付録Ａ−１１）３６セルを持つ単一次元のテーブルＤｌ！に、これらの同じ指数を蓄積することができる。第１のテーブルのアドレス（ｘ、ｙ）におけるセルはアドレスＤｌ！：４ｘ＋ｙにおけるセルに等しい。
加えて、ｍｌ！の（ｎ＋１）の値を蓄積し、ｌ！の基本分解を使用して、中間分解の計算を削減することができる配備を行うことができる。
【０２０６】
＊整数ｌ（０≦ｌ≦ｎ）の表現
【０２０７】
基本分解ｌ（０≦ｌ≦ｎ）を表現するために、幾つかの解決法をまた提供することができる。第１の解決法は各値ｌに対し、数ｍｌおよびｌのｐｉ（０≦ｉ≦ｍｌ）のｍｌの累乗指数を蓄積することである。変形では、ｌ！（ｍｌ！またはｍｎｌ）の指数に対するのと同様に多くの指数を蓄積するのが好ましいであろう。ｌおよびｌ！の基本分解はその場合同じ数ｍを共有する。
別の変形では、ｌのゼロでない分解指数の数ｍ’ｌが小さいことを活用することができる。例えば、この数ｍ’ｌが最大で２（ｌ＝１６の場合）であることは表３ａにおいて明らかであった。従って、この数および対応する値ｐｉまたは指標ｉのみを蓄積することが可能である。
一方、またゼロでないこれらの累乗素因数の指標ｉを蓄積する配備が必要であるが、これは表における対応する指数のアドレスにより指標ｉは最早暗黙には認識されないからである。
【０２０８】
＊基本分解以外の分解表現
【０２０９】
中間分解表現は中間分解を判断する基本分解表現に依存する。同様に、部分ランクの分解表現は部分ランクの分解表現を判断する中間分解の表現に依存する。
【０２１０】
＊基本分解の蓄積
【０２１１】
典型的に、次元８（ｎ＝８）の置換符号のための本明細書の以下の表４ａ乃至表４ｄによる例示により、４つの可能な蓄積の解決法を示すことができ、この解決法では４つの（ｍ８！＝４）素数（２、３、５および７）を考慮する。これらの例を３ＧＰＰ  ＡＭＲ−ＷＢ＋符号化器（規格［３ＧＰＰＴＳ２６．２７３］および［３ＧＰＰＴＳ２６．３０４］）に適用することができる。この符号化器は代数ベクトル量子化を使用し、代数ベクトル量子化辞書は次元８のゴセット（Gosset）配列ＲＥ８の置換符号結合である。
最初の３つの解決法（表４ａ乃至表４ｃ）は同じ方法でｌ！の基本分解を表し、蓄積する。要するに、ｍｌ！およびｌ！のｐｉ（０≦ｉ≦ｍｌ！）のｍｌ！の累乗指数の蓄積を配備する。以上の解決法はｌの基本分解表現および蓄積において異なる。表４ａはｍｌおよびｌのｐｉ（０≦ｉ≦ｍｌ！）のｍｌ！の累乗指数の蓄積を目的とする第１の解決法を示す。表４ｂはｌのｐｉ（０≦ｉ≦ｍｌ！）のｍｌ！の累乗指数の蓄積を目的とする第２の解決法を示す。
【０２１２】
【表４ａ】
2009527171.tif 000066
【表４ｂ】
2009527171.tif 000067
【０２１３】
表４ｃはｌのｐｉのゼロでないが累乗指数の数ｍ’ｌ、対応する指数ｉ、およびその指数の蓄積を目的とする第３の解決法を示す。明瞭さを増すため提示する表で示すのは、素数ｐｉである。
【０２１４】
【表４ｃ】
2009527171.tif 000068
【０２１５】
第４の解決法（以下の表４ｄにより示す）では、基本分解セットを数ｍｎｌにより表し、各基本分解（ｌまたはｌ！）に対し、ｍｎｌの指数を蓄積する。以前に提示した表３ａおよび表３ｂの４つの列（ｐｉ＝２、３、５および７）および９つの行（ｎ＝０乃至８）から表４ｄを抽出する。
【０２１６】
【表４ｄ】
2009527171.tif 000069
【０２１７】
可変次元およびリゾリューションを持つ統計的ベクトル量子化を使用する最大次元１５のＴＤＡＣ符号化器では、６つの（ｍ１５１＝６）素数：２、３、５、７、１１および１３を考慮する。次いで、表３ａおよび表３ｂの６つの列（ｐｉ＝２、３、５、７、１１および１３）および１６の行（ｎ＝０乃至１５）は第４の解決法に対する基本分解セットの蓄積を示すことができる。
【０２１８】
指数のコンパクトな表現
【０２１９】
蓄積を最少にし、限定数のワードに関する基本分解指数をコンパクトに表すことにある別の有利な解決法に関する説明に進む。基本分解表現のこの変形では、中間分解および部分ランクの中間分解をまたコンパクトに表す。有利には、この解決法はまた分かるであろうようにこれらの分解に関する判断の複雑度を最少にする。
【０２２０】
＊分解のコンパクトな表現
【０２２１】
各素因数ｐｉに対する部分ランクの分子におけるその指数が持つ最大値の上限βｉを判断するために検索を行う。この限界はｐｉの指数に関する可能な値の最大数、即ちβｉ＋１を与える。バイナリにより値（βｉ＋１）を表現する整数ビット数の表示にｂｎｉを使用することにより、次式をえ、
【０２２２】
【数６１】
2009527171.tif 000070
【０２２３】
上式で、
【０２２４】
【数６２】
2009527171.tif 000071
【０２２５】
はｘ以上の直近の整数を表示する。
【０２２６】
【数６３】
2009527171.tif 000072
【０２２７】
部分ランクｔ’に含む項Ｋの累乗因数分解指数をＢｎビットのワードｅＫによりコンパクトに表現することができ、
【０２２８】
【数６４】
2009527171.tif 000073
【０２２９】
このワードｅＫは以下の通りである。
【０２３０】
【数６５】
2009527171.tif 000074
【０２３１】
記法「≪Ｂ」はＢビットの左シフトを表す。
【０２３２】
数ｎが大きければ、整数の表現に使用するビット数Ｂ０（１６、３２または４０ビット）よりＢｎが大きいであろうことを注記することにする。この場合、ｔ’に含む整数Ｋの素因数分解指数をＭの完全整数ｅＫ（ｍ）、０≦ｍ＜Ｍ（勿論、Ｍ＞１である）の形式で表す。
【０２３３】
有利には、Ｍワードを以下のように形成することができる。
・ｅＫ（０）はｉ０の第１の指数（ｐ１乃至ｐｉ０の指数）を含む：
【０２３４】
【数６６】
2009527171.tif 000075
【０２３５】
上式で
【０２３６】
【数６７】
2009527171.tif 000076
【０２３７】
である。
・ｅＫ（１）はｐｉ０＋１乃至ｐｉ１の指数を含む：
【０２３８】
【数６８】
2009527171.tif 000077
【０２３９】
上式で
【０２４０】
【数６９】
2009527171.tif 000078
【０２４１】
である。
・ｐｍｎ！の指数を含む最終ワードを構成するまで、後者の関係式を任意のｍについて一般化することができる。
勿論、その他の変形を提供することができる。例えば、１つの変形はｐ１の指数を個別に蓄積し、ｐ２の指数から以上の処理演算を適用することにある。
【０２４２】
＊上限の判断
【０２４３】
限界βｉを幾つかの方法で判断することができる。置換符号に関する情報（アルファベットのサイズｑ、重みｗｉ、０≦ｉ＜ｑ）を使用して、部分ランクの分子が持つ各指数の最大値を明確に判断することができる。幾つかの（恐らく異なる次元の）置換符号を使用すれば、好ましくは最大の最大値を各指数に対して選択する。
本発明は有利にはシャルクビック計数のコンテキストにおける上限を判断する汎用処理演算を提案する。処理演算は使用する置換符号に関して最大次元以外の事前情報を使用しない。処理演算は単に、
【０２４４】
【数７０】
2009527171.tif 000079
【０２４５】
を使用し、次いで
【０２４６】
【数７１】
2009527171.tif 000080
【０２４７】
を選択する。
非常に多様な置換符号を使用する場合、この非常に汎用的処理は特に適する。
表５ａは次元が８乃至１５の場合のＩｋｄｋの分子における最大指数値に関する上限を示す。表５ｂは次元が８乃至１５の場合のこれらの指数を表すビット数ｂｎｉおよびその総和Ｂｎ（最終列）を示す。次元８では、素因数２の指数を３ビットで表し、その他の素因数（３、５および７）の指数を２ビットで表す。次元１５では、素因数２の指数を４ビットで表し、素因数３の指数は３ビットで、その他の素因数（５、７、１１および１３）の指数は２ビットで表す。
【０２４８】
【表５ａ】
2009527171.tif 000081
【表５ｂ】
2009527171.tif 000082
【０２４９】
表６ａ（対応して表６ｂ）は８（対応して１５）に等しい次元ｎに対するｌおよびｌ！の指数のコンパクトな表現を示す。
【０２５０】
【表６ａ】
2009527171.tif 000083
【表６ｂ】
2009527171.tif 000084
【０２５１】
純粋な例示として、表６ｂを使用して整数ｌ＝１２の分解の判断を試行しよう。
好ましくは表６ｂで、符号の最大次元がｎ＝１５であるので、「２」の指数を４ビットで表し、「３」の指数を３ビットで、その他の素因数５、７、１１、１３を２ビットで表す。表では列ｌ＝１２において、そのコンパクトな指数ｅ１２＝１８を読むことができる。
【０２５２】
以下の表の読出しを信頼すると、Ｂ１５＝１５ビットにおける１８（＝１６＋２）のバイナリ表現は、１つのかつ同じ素数に関連するビットを共にグループ化することにより：
０００  ００００  ０００１  ００１０、即ち００  ００  〇〇  ００  ００１  ００１０となる。
【０２５３】
【表６ｃ】
2009527171.tif 000085
【０２５４】
４つの低順位ビット（重みｉ＝０乃至３）は素因数２の指数、即ち００１０＝２であり、これは２が素数２に割当てるべき指数であることを意味する。
次の３ビット（重みｉ＝４乃至６）は素因数３の指数、即ち００１＝１であり、これは１が素数３に割当てるべき指数であることを意味する。
次の２ビット（重みｉ＝７乃至８）は素因数５の指数、即ち００＝０である。
次の２ビット（重みｉ＝９乃至１０）は素因数７の指数、即ち００＝０である。
次の２ビット（重みｉ＝１１乃至１２）は素因数１１の指数、即ち００＝０である。
次の２ビット（重みｉ＝１３乃至１４）は素因数１３の指数、即ち００＝０である。
抽出手順は高順位ビットをマスクし、低順位ビットに含む素因数指数を回復し、次いで回復したビット数のコンパクトな指数をシフトし、次の素因数指数への切り替えを伴う。
従って次元１５では、２の指数を始めとして６つの抽出すべき指数がある。
【０２５５】
２の指数のバイナリ表現は１８の４つの低順位ビット、即ち００１０に対応し、これは２に相当する。これらを回復するために、１８の高順位ビットを１５によりマスク（１８＆１５と表示）し、これは：２４−１＝１１１１に等価である。
得られる結果はｅ１２＝１８＆（２≪４−１）＝２であり、これは２が素数２に割当てるべき指数であることを意味する。
次いで、１８を右に４ビットシフトし、０００  ００００  ０００１＝１を与える。
３の指数のバイナリ表現は１の３つの低順位ビット、即ち００１（＝１）に対応する。これらを回復するために、１の高順位ビットを７によりマスクする（１＆７と表示し、値
２３−１＝１１１をうる）。
得られる結果はｅ１２１＝１＆（２≪３−１）＝１であり、これは１が素数３に割当てるべき指数であることを意味する。
次いで、１を右に２ビットシフトし、そうするとこれは全てのその他の高順位ビットに対し００００  ００００＝０を示す。
それ故ｌ＝１２の累乗が
−素数２に対して２、および
−素数３に対して１、
即ちｌ＝１２＝２２×３１であることを思い出すであろう。
【０２５６】
＊分解の上限
【０２５７】
ここで各素因数に対し、部分ランクｔ’の分母におけるその指数がｔ’の分子におけるその指数以下であることを仮定する。
【０２５８】
【数７２】
2009527171.tif 000086
【０２５９】
であるので、ｔ’が厳密に正であればこれは当てはまり、それ故
【０２６０】
【数７３】
2009527171.tif 000087
【０２６１】
である。
実際には、シャルクビック公式により、およびｑ＞１であれば、値
【０２６２】
【数７４】
2009527171.tif 000088
【０２６３】
は分母Ｐｋ（ｑ＞１であればＰｋ≦（ｎ−１）！）の指数の最大値β’ｉの上限である。
【０２６４】
それ故、不等式
【０２６５】
【数７５】
2009527171.tif 000089
【０２６６】
を調べれば十分であり、これは以上で説明したβｉの値を判断する処理演算により既に実行している。その他の場合、β’ｉを明確に検索し、最大のβｉおよびβ’ｉを使用してｂｎｉを計算することが可能である。
ｑ＝１の場合、既知ランク（ｔ＝０）の単一符号ワードを置換符号に含むことは理解されるであろうし、それ故事前にランクの計算および対応する逆演算を実行することは無用である。一方この特定の場合を個別に扱うことを望まない場合でも最大のβｉおよびｅｎ！ｉにより、なお値ｂｎｉを計算する配備をなしうる。以下の表７はｎ＝１６のこの場合を示す。
【０２６７】
【表７】
2009527171.tif 000090
【０２６８】
次に、基本分解を蓄積するのに必要なメモリ容量の簡潔な説明に進む。
基本分解の表現に選択する解決法とは独立に、基本分解をテーブルに蓄積し、次いでランクの符号化および復号化演算においてこれらのテーブルのアドレス指定に使用することができる。０の分解は可能ではない（そして、その上使用しない）が、０の分解に対し「ダミー」指数（例えば複数の０または複数の１）を蓄積し、アドレス計算を簡単にすることは好ましいであろう。
以下の表８は、これら２つ（０のダミー分解の蓄積の有無）の場合を説明する５つの解決法の基本分解に関係するデータを蓄積するのに必要なメモリサイズを要約する。
【０２６９】
【表８】
2009527171.tif 000091
【０２７０】
第５の解決法では、ビット数ｂｎｉの蓄積（＋ｍｎ！）を考慮する。一方実際にはビット数をメモリから読出すよりむしろ、以下の実施形態に見るであろうように、ビット数のメモリからの読出しは「ハードにより布線」する（その値を変数として宣言することなく計算プログラムに設定する）。それ故、ビット数を実際に蓄積するのは無意味に思われた。
表９は、ｎｍａｘ＝８および１５（０のダミー蓄積を伴う）の場合のこれら５つの解決法の分解指数に関係するデータを蓄積するのに必要なメモリを示す。
【０２７１】
【表９】
2009527171.tif 000092
【０２７２】
次に、素因数累乗の蓄積に関する説明に進む。
基本分解以外に、本発明は素因数累乗を使用し、その分解から部分ランクを計算する。これら素因数テーブルからその累乗を実時間（「オンライン」）で計算することが可能である。好ましくは、２以外の素数の累乗を事前計算して蓄積し、２の累乗のみを実時間で計算する。以下の表１０ａは（ＡＭＲ−ＷＢ＋符号化器で使用するもののような）次元８の置換符号に必要な３、５および７の累乗を示す。表１０ｂは（ＴＤＡＣ符号化器で使用するもののような）最大次元１５の置換符号に必要な３、５、７，１１および１３の累乗を示す。
【０２７３】
【表１０ａ】
2009527171.tif 000093
【表１０ｂ】
2009527171.tif 000094
【０２７４】
ここで再び、各素因数に必要な累乗数のみを蓄積することが可能である。変数として規則的にアドレス可能な単一の累乗テーブルのみを有することが好ましければ、各素因数に対し必要なｐ２（ｐ２＝３）の累乗数と同様に多くの値を蓄積する配備を行うことができる。使用しない累乗については、勿論複数の１または複数の０などのダミー値の蓄積を使用することが可能である。
【０２７５】
次に、本発明を使用して符号化を実行する置換ランクの計算に関する説明に進む。
選択する基本分解セットおよびその表現に応じて幾つかの変形が存在する。簡明さのため、ｌ！およびｌの階乗分解を伴う基本分解セットに好ましい実施形態の場合に、以下の可能な実施の説明を限定する。
以下では、最も一般的な場合である各基本分解のｍｎ！の指数を持つ指数の分解相互関係表現に関する解決法をまず説明する。指数に関する分解相互関係表現の変形を次いで記述する。最後に、基本分解指数のコンパクトな表現に関する解決法を幾つかの変形と共に説明する。その上で、本発明が置換ランクの符号化の処理演算に完全に適用できることが明らかになるであろう。
【０２７６】
計数処理の例として、シャルクビックアルゴリズムを以下で考察する。
【０２７７】
分解指数の分解相互関係表現
【０２７８】
ｎを使用する置換符号の最大次元であるとし、ｍｎ！を量ｎ！の分解に含む素因数の数とする。
分解指数の分解相互関係表現を使用する符号化に関する第１の実施形態の説明を以下に提示する。
【０２７９】
第１の実施形態による符号化
【０２８０】
ここで、ｌ！およびｌの基本分解指数をｌ＝０に対するダミー蓄積と共に本明細書の以上の表４ｄの「第４の」解決法により、ｍｎ！×（ｎ＋１）セルを有するそれぞれＤｌおよびＤｌ！と表示する２つの単一次元テーブルに好ましくは蓄積する。本明細書で以上に記述したように、ｍｎ！の列および（ｎ＋１）の行を有する２次元テーブルを考慮することもまた可能であろう。ｌ（対応してｌ！）の指数を規則的に（ｍｎ！の値毎に）蓄積するので、基本分解指数を読出す演算はテーブルＤｌ（対応してＤｌ！）におけるアドレス計算を必要とする。ｌ！（対応してｌ）の分解指数を読出すために、テーブルＤｌ！（対応してＤｌ）のアドレス（ｌ×ｍｎ！）を指示し、従って指数
【０２８１】
【数７６】
2009527171.tif 000095
【０２８２】
（対応してｅｌ１）、次アドレス（ｌ×ｍｎ！＋１）にある指数
【０２８３】
【数７７】
2009527171.tif 000096
【０２８４】
（対応してｅｌ２）、より一般的にはアドレス（ｌ×ｍｎ！＋ｉ−１）にある指数
【０２８５】
【数７８】
2009527171.tif 000097
【０２８６】
（対応してｅｌｉ）を目標とすることが必要である。本明細書で以上に記述したように２次元テーブルでは、指数
【０２８７】
【数７９】
2009527171.tif 000098
【０２８８】
（またはｅｌｉ）はアドレス（（ｌ；（ｉ−１））（列（ｉ−１）および行ｌ）にある。
ｌ＝０に対するダミー蓄積の配備がなされなければ、ｌ（ｌ＞０）のｎの基本分解テーブルＤｌにおけるアドレス計算は（ｌ−１）×ｍｎ！であることに留意すべきである。
【０２８９】
初期化
【０２９０】
・Ｐｋのｍｎ！の中間分解指数（以下のステップＣ−３を参照して分かるであろうように好ましくは各位置で更新するｍｎ！のセルを有するテーブルＰに蓄積する）をゼロに初期化する。従って、命令は以下の通りである。
【０２９１】
【数８０】
2009527171.tif 000099
【０２９２】
・ランクｔおよびｑの重みｗｋｄ（各位置で更新するであろうｑセルを有するテーブルｗに蓄積する（本明細書の以下のステップＣ−２））をまたゼロに初期化する。命令は以下の通りである。
【０２９３】
【数８１】
2009527171.tif 000100
【０２９４】
指標ｋに関する反復
【０２９５】
図５を参照して、ｎの位置に関する反復（変数ｋに関するループにより）に進む。図５のステップＣ−ｎの記法における文字「Ｃ」は用語「符号化」を示す。
ステップＣ−１で、変数ｄｋを読む。ステップＣ−２は構成上テーブルｗのセルｄｋの更新を含む：ｗ［ｄｋ］＝ｗ［ｄｋ］＋１
ステップＣ−３はＰｋの分解指数（テーブルＰ）の更新であり、特に
−アドレスｍｎ！×ｗ［ｄｋ］からテーブルＤｌの基本分解ｗ［ｄｋ］のｍｎ！の指数
【０２９６】
【数８２】
2009527171.tif 000101
【０２９７】
の読出し（ステップＣ−３１）および
−更新：１≦ｉ≦ｍｎ！に対し、
【０２９８】
【数８３】
2009527171.tif 000102
【０２９９】
（ステップＣ−３２）を伴う。
【０３００】
従ってステップＣ−３１を実施するには、
【０３０１】
【数８４】
2009527171.tif 000103
【０３０２】
と表示するテーブルＤｌの基本分解ｗ［ｄｋ］の第１の指数がアドレスｍｎ！×ｗ［ｄｋ］にあり、
【０３０３】
【数８５】
2009527171.tif 000104
【０３０４】
と表示する第２の指数がアドレス（ｍｎ！×ｗ［ｄｋ］＋１）にあるなどである。より一般的には、指数
【０３０５】
【数８６】
2009527171.tif 000105
【０３０６】
はアドレスｍｎ！×ｗ［ｄｋ］＋ｉ−１にある。
平行してステップＣ−４で、通常の関係式
【０３０７】
【数８７】
2009527171.tif 000106
【０３０８】
からＳｋを計算する。
ステップＣ−５はＳｋ値に関する検査である。部分ランクＩｋｄｋがゼロであり（本明細書の以上の公式（７））、ランクｔが不変であることを意味するＳｋがゼロ（矢印Ｙ）であれば、処理はステップＣ−１１により後に続く。その他の場合（Ｓｋ≠０である矢印Ｎ）、処理はステップＣ−６により継続し、ステップＣ−６で基本分解Ｓｋのｍｎ！の指数
ｅＳｋｉをテーブルＤｌのアドレスｍｎ！×Ｓｋにおいて読出す。
平行して、ステップＣ−７はテーブルＤｌ！のアドレスｍｎ！×（ｎ−１−ｋ）において基本分解（ｎ−１−ｋ）！のｍｎ！の指数
【０３０９】
【数８８】
2009527171.tif 000107
【０３１０】
を読むことにある。総和Ｓｋがゼロでなければ（検査Ｃ−５のＮの出口）、ステップＣ−７を実行し、何れにしろ部分ランクＩｋｄｋがゼロであれば、テーブルＤｌ！における不要な読出しを回避するようにすることを注記することにする。
ステップＣ−８で、種々のテーブルの読出し結果を共にグループ化し、１≦ｉ≦ｍｎ！の場合の関係式
【０３１１】
【数８９】
2009527171.tif 000108
【０３１２】
により、まず部分ランクＩｋｄｋのｍｎ！の分解指数を計算することができる。
最後にステップＣ−９で、部分ランクＩｋｄｋ自体を次式により計算する。
【０３１３】
【数９０】
2009527171.tif 000109
【０３１４】
項ｗ［ｄｋ］が関係する置換符号の必ず最大次元ｎ以下である重みであることを思い出すであろう。同様にこのような重みの総和Ｓｋは最大次元ｎより小さく留まり、同じことが勿論（ｎ−１−ｋ）に対しても当てはまる。ｗ［ｄｋ］、Ｓｋおよび（ｎ−１−ｋ）！の分解を、実際、表４ｄなどの整数分解または最大次元ｎに至る範囲の整数階乗のテーブルにリストする。テーブルにリストする分解ｗ［ｄｋ］および先行ループ（ｋ−１）で判断し、メモリに保持するＰｋ−１の分解から、Ｐｋの分解を判断する。
【０３１５】
図５の部分ランク計算ステップの純粋な例示として、次元ｎ＝８およびｑ＝４の置換符号を考察する。この例では、４つの列および９つの行を持ち、それ故３６のセルを含む２次元テーブルに指数を蓄積する。それ故、列がｐｉ＝２、３、５、７および行がｌ＝０、．．．、８の本明細書で以上に提示した表４ｄから指数を抽出することができる。
この例では先行位置ｋ＝３において、重みｗのテーブルが｛１、１、０、３｝であり、それ故Ｐ３＝１！１０！３！＝６であると仮定する。Ｐ３（＝２１×３１×５０×７０）の分解指数テーブルＰはそれ故｛１、１、０、０｝である。ステップＣ−１の位置ｋ＝２では、ｄ２＝２を読出したと仮定する。この例のステップＣ−２では、セルｗ［２］を１（ｗ［２］＝０＋１＝１）だけ増分することによりセルｗ［２］を更新する。
ステップＣ−３１で、１（＝ｗ［２］）の４つの分解指数、即ち０、０、０、０を読む（表４ｄの６番目乃至９番目の列および３番目の行ｌ＝１を参照）。
次いで（ステップＣ−３２で）、テーブルＰを更新し、従ってＰ＝｛１、１、０、０｝を得る。
ステップＣ−４で、Ｓｋを：Ｓｋ＝ｗ［０］＋ｗ［１］＝１＋１＝２と計算する。それ故、Ｓｋはゼロではない（検査Ｃ−５）。
・Ｓｋの４つの分解指数を読み（表４ｄの６番目乃至９番目の列であるが、４番目の行ｌ＝２をさらに参照して）（ステップＣ−６）、ｐ１＝２（６番目の列）の場合、指数は１、ｐｉ＝３、５、７（７番目乃至９番目の列）の場合、指数は０である。
・表４ｄであるが、今回は２番目乃至５番目の列および７番目の行ｌ＝５をさらに参照して、５！（（ｎ−１−ｋ）！に相当）の４つの分解指数を読む（ステップＣ−７）。ｐ１＝２（２番目の列）の場合、指数は３である。ｐ２＝３（３番目の列）の場合、指数は１であり、ｐ３＝５（４番目の列）の場合、指数はまた１である。他方、ｐ４＝７（５番目の列）の場合、指数は０である。
・ステップＣ−８で、部分ランクＩｋｄｋの４つの分解指数を計算する。
【０３１６】
【数９１】
2009527171.tif 000110
【０３１７】
ステップＣ−９で、部分ランクＩｋｄｋをその２３×３０×５１×７０＝４０の分解指数から計算する。
【０３１８】
再び図５を参照して、ステップＣ−１０で関係式ｔ＝ｔ＋Ｉｋｄｋに従う（ステップＣ−９に見出す部分ランクＩｋｄｋの加算により）更新により、置換のグローバルランクｔを自ら判断する。
次いで、ステップＣ−１１は変数ｋ（ｋ＝ｋ−１）を減分することを目的とし、ステップＣ−１２は処理を継続するかを決めるｋの値に関する検査である。従って、ｋ≧０（検査Ｃ−１２の出口のＹの矢印）であれば、処理演算のステップはｋの値を１ユニットだけ減分して最初のステップＣ−１から再反復する。その他の場合（検査Ｃ−１２の出口のＮの矢印）処理はステップＣ−１３の終わり（「終了」）で終了する。
【０３１９】
従って、ステップＣ−９より上で、ステップＣ−８で判断するその分解から部分ランクを計算し、以下の３つの中間分解から部分ランク自体を判断することが理解されるであろう：
−（ｎ−１−ｋ）！
−Ｓｋ、および
−Ｐｋ。
ステップＣ−６およびＣ−７において実行する３つの中間分解の内の２つ（ｎ−１−ｋ）！およびＳｋの判断は基本分解のそれぞれのテーブルＤｌおよびＤｌ！における簡単な読出しを含む。また以下のタイプの関係式によりテーブルＤｌ！において読出すｗ［ｄ］！のｑの基本分解から、第３の中間分解（Ｐｋの中間分解）の判断を簡単に実行することができる。
【０３２０】
【数９２】
2009527171.tif 000111
【０３２１】
直接的変形
【０３２２】
ステップＣ−３はこの中間分解の判断に関するより有利な変形を提示する。テーブルＤｌにおいて読出す基本分解および別の部分ランク（Ｉｋ＋１ｄｋ）、例えばｋの反復における先行部分ランクＩｋ＋１ｄｋについて計算する別の中間分解（Ｐｋ＋１の中間分解）から、Ｐｋの中間分解を要するに判断することができる。
本発明の変形ではより一般的に、少なくとも１つの他の部分ランクについて以前に判断した少なくとも１つの中間分解から、中間分解をまた推論することができる。
【０３２３】
本明細書の以上で、最後の位置（ｋ＝ｎ−１）から最初の位置（ｋ＝０）へのループによりランクの計算を実行した。一方、本発明はまた勿論最初から最後の位置へのループにも適合する。全て必要なことは、初期化フェーズを変更し、ステップＣ−２およびＣ−３およびその順序に適合することである。
このために、重みのテーブルｗをｑの重みｗ０ｄにより初期化することができる。次いで０乃至ｑ−１の範囲のｄに対して、ｗ［ｄ］！のｍｎ！の分解指数をテーブルＤｌ！において読出し、中間分解テーブルのｍｎ！の値（Ｐ０の分解指数）を累積加算により計算する。
次いで、ステップＣ−１０の後、ステップＣ−２の前で、ステップＣ−３を実行する。ｗ［ｄｋ］の基本分解指数
【０３２４】
【数９３】
2009527171.tif 000112
【０３２５】
をＰ［ｉ］から減算する
【０３２６】
【数９４】
2009527171.tif 000113
【０３２７】
ことにより、Ｐの中間分解を更新する。次いでｗ［ｄｋ］の値を１だけ減算する（ｗ［ｄｋ］＝ｗ［ｄｋ］−１）ことにより、ステップＣ−２を実行することができる。ステップＣ−１１は変数ｋの１の増分を目的とし、ステップＣ−１２はｋ＝ｎであるかを単に検査する。
【０３２８】
可変次元ｎの置換符号に対して
【０３２９】
【数９５】
2009527171.tif 000114
【０３３０】
の演算を実行するよりむしろ、初期化においてｍｎ！を読み、演算をただｍｎ！回のみ実行するのが好ましいであろうことは簡単に注記する価値がある。
【０３３１】
第１の実施形態に関する一般的な変形
【０３３２】
より一般的には、本発明の意味する符号化に対し図５で表す実施は多数の変形を可能にする。
従って第１の変形では、（ｌまたはｌ！の）各基本分解はまたテーブルｍｌ！を含む。数ｍｌ！（１≦ｌ≦ｎ）を読出すのは利点をもたらす。要するに、ステップＣ−３およびＣ−６乃至Ｃ−１０を最早それぞれｍｎ！回実行せず、ただ：
・ステップＣ−３について
【０３３３】
【数９６】
2009527171.tif 000115
【０３３４】
回、
・ステップＣ−６およびステップＣ−８の加算
【０３３５】
【数９７】
2009527171.tif 000116
【０３３６】
について
【０３３７】
【数９８】
2009527171.tif 000117
【０３３８】
回、および
・ステップＣ−７およびＣ−９についておよびステップＣ−８の減算
【０３３９】
【数９９】
2009527171.tif 000118
【０３４０】
についてｍ（ｎ−１−ｋ）！回実行する。
さらに値ｍｌを蓄積していれば、その場合全て必要なことは：
・ステップＣ−３を
【０３４１】
【数１００】
2009527171.tif 000119
【０３４２】
回、および
・ステップＣ−６を
【０３４３】
【数１０１】
2009527171.tif 000120
【０３４４】
回およびステップＣ−８の加算を実行することである。
【０３４５】
符号化の別の変形で、加算にｌの基本分解指数の蓄積を第３の解決法（本明細書の以上の表４ｃ）により使用すれば、ステップＣ−３を
【０３４６】
【数１０２】
2009527171.tif 000121
【０３４７】
の値について実行することができる。同様に、ステップＣ−６を
【０３４８】
【数１０３】
2009527171.tif 000122
【０３４９】
の値について実行する。ステップＣ−８においてｍ（ｎ−１−ｋ）！の加算およびｍ（ｎ−１−ｋ）！の減算を配備する代わりに、実行する減算の数はｍ（ｎ−１−ｋ）！に留まるが、
【０３５０】
【数１０４】
2009527171.tif 000123
【０３５１】
の加算のみが必要である。特に以下の通りである。
【０３５２】
【数１０５】
2009527171.tif 000124
【０３５３】
第３の変形で部分ランクの３つの項（分子の２つおよび分母の１つ）への分解に代わり、部分ランクを２つの項へ分解し、その１つは商である。従って、部分ランクＩｋｄｋを次の２つの項に分解する。
−総和Ｓｋおよび
−商
【０３５４】
【数１０６】
2009527171.tif 000125
【０３５５】
この商を次の関係式により更新することができる。
【０３５６】
【数１０７】
2009527171.tif 000126
【０３５７】
従ってｑ＋１の基本分解（（ｎ−１−ｋ）！およびテーブルＤｌ！において読出すｑｗ［ｄｋ］！の基本分解）からのＲｋの分解の判断よりむしろ、
【０３５８】
【数１０８】
2009527171.tif 000127
【０３５９】
と表すＲｋ＋１の中間分解および（ｎ−１−ｋ）およびｗ［ｄｋ］の基本分解（これら２つの基本分解をテーブルＤｌにおいて読出す）から、Ｒｋの中間分解を判断する。
先の変形と比較して
【０３６０】
【数１０９】
2009527171.tif 000128
【０３６１】
の分母に関する中間分解の判断および蓄積（テーブルＰ）に代わり、商Ｒｋの中間分解を判断し、次いで蓄積する（このためにテーブルＲを配備する）。テーブルＰのゼロへの初期化をこの比の指数に関するテーブルＲのゼロへの初期化により置換する。ステップＣ−３はテーブルＲを更新する（（ｎ−１−ｋ）およびｗ［ｄｋ］の基本分解指数を読むことにより）簡単なステップとなり、これを次式で表す。
【０３６２】
【数１１０】
2009527171.tif 000129
【０３６３】
蓄積の選択肢により、ｍｌ！の加算と減算またはｍ（ｎ−１−ｋ）！の加算（対応して
【０３６４】
【数１１１】
2009527171.tif 000130
【０３６５】
の減算）またはｍ（ｎ−１−ｋ）の加算（対応して
【０３６６】
【数１１２】
2009527171.tif 000131
【０３６７】
の減算）すら、またはｗ［ｄｋ］および（ｎ−１−ｋ）のゼロでない指数についてのみ：ｍ’（ｎ−１−ｋ）の加算および
【０３６８】
【数１１３】
2009527171.tif 000132
【０３６９】
の減算により、この更新を行うことができる。この場合、ステップＣ−８は以下のタイプの加算のみを含む。
【０３７０】
【数１１４】
2009527171.tif 000133
【０３７１】
蓄積の選択肢により、ｍｎ！の加算または
【０３７２】
【数１１５】
2009527171.tif 000134
【０３７３】
の加算、または
【０３７４】
【数１１６】
2009527171.tif 000135
【０３７５】
の加算すら、またはＳｋのゼロでない指数についてのみ：
【０３７６】
【数１１７】
2009527171.tif 000136
【０３７７】
の加算を次いで計数する。
この比Ｒｋは必ずしも整数ではなく、これは指数Ｒ［ｉ］が負でありうることを意味することを注記することにする。この変形では、符号化における階乗分解（それ故テーブルＤｌ！）は最早有用ではなく、ただテーブルＤｌのみの蓄積により整数ｌ（ｌ≦ｎ）の簡単な（ｎ＋１）の基本分解セットを使用することができる。
【０３７８】
分解指数のコンパクトな表現
【０３７９】
次に、分解指数のコンパクトな表現に基づく符号化の第２の実施形態の説明に進む。
基本分解指数はコンパクトに表現され、第１の実施形態を参照して本明細書で以上に説明したような分解相互関係形式では最早ない。簡明さのため、単一ワードに指数のコンパクトな表現を含む場合のみを説明する。それ故本明細書で以上に説明したように（ｎ＋１）セルを持つそれぞれＤ’ｌおよびＤ’ｌ！と表示する２つのテーブルにｌ＝０に対するダミーワードの蓄積と共にこれらのワードを蓄積する。ｌ！（対応してｌ）の分解ワードを読むために全て必要なことは、テーブルＤ’ｌ！（対応してＤ’ｌ）のアドレスｌを指示することであるので、基本分解指数を含むこれら２つのワードテーブルにおけるアドレス計算は直接的である。
ｌ＝０に対するダミーワードの蓄積のない、基本分解ｌ（ｌ＞０である）に対応するワードはテーブルＤ’ｌのアドレス（ｌ−１）にあることを注記することにする。
【０３８０】
第２の実施形態による符号化
【０３８１】
初期化
【０３８２】
・Ｐｋのｍｎ！の中間分解指数のコンパクトな表現を含むワードｅＰをゼロに初期
化する：ｅＰ＝０
ワードｅＰを各位置に関して更新することにする（以下のステップＣＣ−３）。
・以前のように、各位置において更新することにする（本明細書の以下のステップＣＣ
−２）ｑセルを有するテーブルｗに蓄積するランクｔおよびｑの重みｗｋｄをまた値ゼ
ロに初期化する。対応する命令は以下の通りである：
・ｔ＝０
・ｗ［ｉ］＝０、０≦ｉ＜ｑ
・ｋ＝ｎ−１
【０３８３】
ｎ位置に関する反復（ｋに関するループ）
【０３８４】
次に、図６を参照して、この第２の実施形態における符号化の主ステップに進む。図６のステップＣＣ−ｎの記法の文字「ＣＣ」は「コンパクトな表現」による「符号化」を示す。
ステップＣＣ−１で、変数ｄｋを読む。ステップＣＣ−２は構成上変数ｗの更新を含む：ｗ［ｄｋ］＝ｗ［ｄｋ］＋１
ステップＣＣ−３はワードｅＰの特に以下による更新である：
−ステップＣＣ−３１のテーブルＤ’ｌにおけるｗ［ｄｋ］の分解指数のコンパクトな表現を含むワード
【０３８５】
【数１１８】
2009527171.tif 000137
【０３８６】
の読み取り、次いで
−ステップＣＣ−３２におけるワードｅＰ自体の更新
【０３８７】
【数１１９】
2009527171.tif 000138
【０３８８】
平行してステップＣＣ−４で、総和Ｓｋを計算する。
【０３８９】
【数１２０】
2009527171.tif 000139
【０３９０】
次ステップＣＣ−５はＳｋ値に関する検査である。総和Ｓｋがゼロであれば（矢印Ｎ）、指標ｋを直ちに減分する。その他の場合（検査ＣＣ−５の出口の矢印Ｙ）、ステップＣＣ−６のテーブルＤ’ｌにおけるＳｋの分解指数のコンパクトな表現を含むワード
【０３９１】
【数１２１】
2009527171.tif 000140
【０３９２】
の読出しにより、処理は継続する。
平行して（有利には検査ＣＣ−５の結果に応じて）、（ｎ−１−ｋ）！の指数のコンパクトな表現を含むワードｅ（ｎ−１−ｋ）！をステップＣＣ−７でテーブルＤ’ｌ！において読む。
ステップＣＣ−８で、種々のステップＣＣ−３、ＣＣ−６、ＣＣ−７から得る結果を共にグループ化し、以下の２つの簡単な演算（好ましくは加算続いて減算）により部分ランク
【０３９３】
【数１２２】
2009527171.tif 000141
【０３９４】
の分解のコンパクトな表現を含むワード
【０３９５】
【数１２３】
2009527171.tif 000142
【０３９６】
を計算する。
【０３９７】
【数１２４】
2009527171.tif 000143
【０３９８】
以前に説明したようにワードビットの適するオフセットにより、ステップＣＣ−９は部分ランク
【０３９９】
【数１２５】
2009527171.tif 000144
【０４００】
の、ワード
【０４０１】
【数１２６】
2009527171.tif 000145
【０４０２】
に含むｍｎ！の分解指数
【０４０３】
【数１２７】
2009527171.tif 000146
【０４０４】
の抽出を目的とする。このため、１乃至ｍｎ！の範囲の指標ｉに関するループを配備する（１へのｉの初期化ＣＣ−９１、ｉの値の検査ＣＣ−９３およびｉがｍｎ！の値に達するまでの増分ＣＣ−９４）。次いで、ｉの各ループは自らに以下のタイプの命令ＣＣ−９２を適用した。
【０４０５】
【数１２８】
2009527171.tif 000147
【０４０６】
記法「≪ｂ」および「≫ｂ」はそれぞれｂビットの左シフトおよび右シフトを示すことが思い出されるであろう。その上、記法「＆」はビット毎の「ＡＮＤ」論理演算を示す。命令ｉ’１）は
【０４０７】
【数１２９】
2009527171.tif 000148
【０４０８】
のｂｎｉの低順位ビットを回復することにある。実際には、命令「（（１≪ｂｎｉ）−１）」に対応するマスクをハードにより布線する。
換言すれば、高順位ビットのマスク（（１≪ｂｎｉ）−１）を初めに（１に等しいループ指標ｉに対して）適用し、まず第１の素因数ｐ１に関連する
【０４０９】
【数１３０】
2009527171.tif 000149
【０４１０】
の指数を付与する
【０４１１】
【数１３１】
2009527171.tif 000150
【０４１２】
のｂｎ１の低位順位ビットのみを回復する。
次いで、
−
【０４１３】
【数１３２】
2009527171.tif 000151
【０４１４】
のビットをｂｎ１だけ「右に」シフトし、高順位ビットの次の素因数ｐ２に関連する指数を付与する（マスク（（１≪ｂｎｉ）−１））最高順位ビットを回復し、
−次いで、指数
【０４１５】
【数１３３】
2009527171.tif 000152
【０４１６】
を抽出し、
−次いで、ｂｎ２ビットの右シフトを適用し、
−ｉ＝ｍｎ！まで継続する。
次のステップＣＣ−１０は以下のように部分ランクＩｋｄｋを計算することにある。
【０４１７】
【数１３４】
2009527171.tif 000153
【０４１８】
次いで、部分ランクＩｋｄｋを全ランクｔに加える（ステップＣＣ−１１のｔ＝ｔ＋Ｉｋｄｋ）。
指標ｋの値を次ステップＣＣ−１２において減分し（ｋ＝ｋ−１）、この減分した値によりステップＣＣ−４、ＣＣ−１、ＣＣ−７および後続のステップを再開する前に、ｋの値が−１に達していないか（ｋ＜０）を確かめるために検査ＣＣ−１３において調査を実行し、−１になっている場合は処理を終了する（ステップＣＣ−１４）。
【０４１９】
このように分解表現とは独立に、本発明は部分ランクを効果的に計算することを可能にする。ステップＣＣ−１０は先行ステップＣＣ−８およびＣＣ−９において判断したその分解からの部分ランクの計算を目的とする。３つの（項（ｎ−１−ｋ）！、ＳｋおよびＰｋの）中間分解を使用する。ステップＣＣ−６およびＣＣ−７で実行するその内の２つ（（ｎ−１−ｋ）！およびＳｋ）の判断はテーブルＤ’ｌ！およびテーブルＤ’ｌにおけるそのコンパクトな表現の簡単な読出しにある。ステップＣＣ−３で実行する第３の中間分解（Ｐｋ）の判断は、またテーブルＤｌの読出しに続く、読出した基本分解のコンパクトな表現の加算によるこの中間分解のコンパクトな表現の更新を必要とする。
以前に示したように第１の実施形態を参照して、値ｍｎ！（０≦ｌ≦ｎ）の蓄積はステップＣＣ−９およびＣＣ−１０の複雑度の削減を可能にする。部分ランクＩｋｄｋに関する分解指数の抽出ループをｍｎ！回に代わってｍ（ｎ−１−ｋ）！回実行する。同様に、ステップＣＣ−１０は最早乗算ｍｎ！ではなく、乗算ｍ（ｎ−１−ｋ）！を含む。
【０４２０】
次に、本発明を使用する置換ランクの復号化に関する説明に進む。
ここで再び、基本分解表現の解決法に応じる幾つかの（分解相互関係またはコンパクトな）変形がある。復号化の第１の実施形態に関する説明に進み、これは分解相互関係分解表現を使用する符号化および以上に提示した表４ｄに関係する第４の解決法によるその蓄積について本明細書で以上に説明した第１の実施形態に似る。例としてシャルクビックアルゴリズムを採用する置換ランクの復号化に本発明が完全に適用できることが明らかになるであろう。
【０４２１】
第１の実施形態による復号化
【０４２２】
分解指数の分解相互関係表現を使用する復号化は好ましくは以下のようにデータの初期化により始まる。
【０４２３】
初期化
【０４２４】
・値ｗのテーブルをｑの重みｗ０ｄにより初期化する（以下で説明することにするステ
ップＤ−１９の各位置に関するループの終わりでｗを更新する）。適する命令は以下の
タイプでありうる：
・ｗ［ｉ］＝ｗ０ｉ、０≦ｉ＜ｑ
・項Ｐ０のｍｎ！の分解指数を計算する（下記ステップＤ−１８の各位置に関するルー
プの終わりの各位置でまた更新するｍｎ！のセルを有するテーブルＰに蓄積する）。適
する命令は以下のタイプでありうる：
・１≦ｉ≦ｍｎ！についてＰ［ｉ］＝０
・ｄ＝０乃至ｑ−１のループ
・テーブルＤｌ！における
【０４２５】
【数１３５】
2009527171.tif 000154
【０４２６】
のｍｎ！の分解指数
【０４２７】
【数１３６】
2009527171.tif 000155
【０４２８】
の読出し、次いで
【０４２９】
【数１３７】
2009527171.tif 000156
【０４３０】
・最後に、ｋ＝０に初期化する。
次に図７を参照して、第１の実施形態による復号化の主ステップに進む。図７のステップＤ−ｎの記法における文字「Ｄ」は「復号化」を表す。
【０４３１】
ｎ位置に関する反復（指標ｋに関するループ）
【０４３２】
第１のステップＤ−１はテーブルＤｌ！における（ｎ−１−ｋ）！のｍｎ！の分解指数
【０４３３】
【数１３８】
2009527171.tif 000157
【０４３４】
を読出すことにある。
次ステップＤ−２は値ｄｋ＝０およびＩｋｄｋ＝０を設定する。
次いで、ｗ［ｄｋ］≠０であるようなアルファベットのｄｋに関する第１の値の検索に進む。このため、ｗ［ｄｋ］＝０であるかを調べる検査Ｄ−３を配備し、該当する場合（矢印Ｙ）、ｄｋの値を増分し（ｄｋ＝ｄｋ＋１）、ゼロでないｗ［ｄｋ］の値を見つけるまで検査Ｄ−３を反復する。この値が見つかれば（ｗ［ｄｋ］≠０の場合矢印Ｎ）、次ステップはランクｔの値に関する検査Ｄ−５である。ランクがゼロであれば（検査Ｄ−５の出口の矢印Ｙ）、Ｐｋの指数を更新する（ステップＤ−１８）まで以下のステップを適用するのは無意味である。ランクがゼロでなければ（検査Ｄ−５の出口の矢印Ｎ）、処理を後続のステップＤ−６およびＤ−７により継続し、これらのステップでそれぞれＳｋ＝０および中間値ＩｋをＩｋ＝Ｉｋｄｋに設定する。
【０４３５】
次ステップＤ−８は総和Ｓｋ＝Ｓｋ＋ｗ［ｄｋ］を更新する計算である。Ｓｋであることが判明する総和のｍｎ！の分解指数
【０４３６】
【数１３９】
2009527171.tif 000158
【０４３７】
に関するテーブルＤｌの読出し（ステップＤ−９）が次ステップＤ−８に続く。
ステップＤ−１０は、１≦ｉ≦ｍｎ！である関係式
【０４３８】
【数１４０】
2009527171.tif 000159
【０４３９】
の部分ランク分解指数
【０４４０】
【数１４１】
2009527171.tif 000160
【０４４１】
の計算を目的とする。現ループの終わりで、および次ループに対して後に説明することにするステップＤ−１８で、上記のように初期化する指数Ｐ［ｉ］を更新する。
ステップＤ−１１は部分ランクの計算
【０４４２】
【数１４２】
2009527171.tif 000161
【０４４３】
を目的とする。
次の３ステップは、全ランクｔの値の部分ランクの値との比較による全ランクｔの値に関する検査を目的とする。これを行うためにステップＤ−１２で、ｄｋの値を増分し（ｄｋ＝ｄｋ＋１）、検査Ｄ−１３は次の通りである：ｔ−Ｉｋｄｋ≧０？。
不等式を満たせば（矢印Ｙ）、ステップＤ−７乃至Ｄ−１３を新しく増分したｄｋの値により反復する。その他の場合（矢印Ｎ）、ステップＤ−１２の前のｄｋの値に戻るために、ｄｋの値を減分する（ｄｋ＝ｄｋ−１）ステップＤ−１４により処理を継続する。このｄｋの値に対し、部分ランクＩｋｄｋは上述の中間値Ｉｋを取る（ステップＤ−１５で、Ｉｋｄｋ＝Ｉｋ）。
次いで、ランクｔを更新し、ランクｔはｔ＝ｔ−Ｉｋｄｋとなり（ステップＤ−１６）、テーブルＤｌにおけるｗ［ｄｋ］のｍｎ！の分解指数
【０４４４】
【数１４３】
2009527171.tif 000162
【０４４５】
の読出し（ステップＤ−１７）から、Ｐｋの指数を（テーブルＰにおいて）更新し、続けて１≦ｉ≦ｍｎ！に対し指数自体を
【０４４６】
【数１４４】
2009527171.tif 000163
【０４４７】
により更新する（ステップＤ−１８）。次いで、ｗ［ｄｋ］の値を減分し（ｗ［ｄｋ］＝ｗ［ｄｋ］−１：ステップＤ−１９）、指標ｋの値を増分（ｋ＝ｋ＋１：ステップ２０）し、次のループに備える。
第１のステップＤ−１にループにより戻る前に、ｎ構成要素を全て処理していないことを確認するために調査を実行する。このために、ｋの値のｎとの比較（ｋ＜ｎ）によるｋの値に関する検査Ｄ−２１を配備する。指標ｋが値ｎに達しない限り（検査Ｄ−２１の出口の矢印Ｙ）、ｋの次の値についてステップＤ−１において処理を再開する。その他の場合（検査Ｄ−２１の出口の矢印Ｎ）、ステップＤ−２２の終わりで処理を終了する。
【０４４８】
ステップ１１はそれぞれの項（ｎ−１−ｋ）！、ＳｋおよびＰｋの３つの中間分解からステップ１０で判断したその分解の使用による部分ランクの計算を目的とすることを思い出すべきである。ステップＤ−１およびＤ−９で実行するそのうちの２つ（（ｎ−１−ｋ）！およびＳｋ）の判断は構成上それぞれのテーブルＤｌ！およびＤｌにおける簡単な読出しを含む。テーブルＤｌの読出し（ステップＤ−１７）に続く読出した（ステップＤ−１８）基本分解指数の減算によるこの中間分解指数による更新により、またステップＤ−１８で実行した第３の中間分解（Ｐｋ）の判断を実行する。この中間分解の本明細書で以上に説明した初期化はテーブルＤｌ！のｑの読出しに続く読出したｑの基本分解指数の加算によるこの中間分解指数による更新を必要とする。
【０４４９】
本明細書で以上に説明した符号化に関しては、図７の処理は、適する場合一定のステップの複雑度を削減する変形を可能にする。
比Ｒｋの指数の使用（前記のように）を含む変形には特に関心を持てる。要するに、図７を参照して本明細書で以上に説明した復号化処理演算では、所与の位置ｋについてｄの幾つかの値に対する指数
【０４５０】
【数１４５】
2009527171.tif 000164
【０４５１】
を計算する。検査するｄの各値について、その他の変形は各指数に対する減算および加算を必要とする。
【０４５２】
【数１４６】
2009527171.tif 000165
【０４５３】
一方、総和Ｓｋおよびその指数
【０４５４】
【数１４７】
2009527171.tif 000166
【０４５５】
のみが所与の位置ｋに関してｄにより変化するので、比Ｒｋの指数を使用する変形は加算
【０４５６】
【数１４８】
2009527171.tif 000167
【０４５７】
のみを必要とする。
【０４５８】
第２の実施形態による復号化
【０４５９】
次に、図８を参照して分解のコンパクトな表現を使用する復号化の実施例の説明に進む。
まず、データを以下のように初期化する。
【０４６０】
初期化
【０４６１】
・まず、ｑのセルを有するテーブルを参照して、０≦ｉ＜ｑに対する項ｗ［ｉ］＝ｗ０
ｉを判断するべきである。
・Ｐｋのｍｎ！の分解指数のコンパクトな表現を含むワードｅＰを計算する。このため：
・ｅＰ＝０を設定し、
・ｄ＝０乃至ｑ−１に対するループを配備し：
・ループはテーブルＤ’ｌ！にｗ０d！の指数ｍｎ！のコンパクトな表現を含むワー
ド
【０４６２】
【数１４９】
2009527171.tif 000168
【０４６３】
の読取り、および
【０４６４】
【数１５０】
2009527171.tif 000169
【０４６５】
・の更新を伴い、
・次いで、ｋ＝０に設定する。
【０４６６】
ｎ位置に関する反復（ｋに関するループ）
【０４６７】
図８のステップＤＣ−ｎの記法における文字「ＤＣ」は「コンパクトな表現」による「復号化」を示す。
ステップＤＣ−１はテーブルＤ’ｌ！において項（ｎ−１−ｋ）！の指数ｍｎ！のコンパクトな表現を含むワードｅ（ｎ−１−ｋ）！の読出しにある。
ステップＤＣ−２乃至ＤＣ−８は図７を参照して本明細書で以上に説明したステップＤ−２乃至Ｄ−８に類似である。
他方ステップＤＣ−９では、テーブルＤ’ｌに総和Ｓｋのｍｎ！の指数のコンパクトな表現を含むワード
【０４６８】
【数１５１】
2009527171.tif 000170
【０４６９】
を読む。
次いでステップＤＣ−１０で、部分ランクＩｋｄｋの指数のコンパクトな表現を含むワードを好ましくは以下のように計算する。
【０４７０】
【数１５２】
2009527171.tif 000171
【０４７１】
汎用ステップＤＣ−１１はグローバルに部分ランクＩｋｄｋの指数の抽出にある。このため、次の配備を行う。
−ｉ（１≦ｉ≦ｍｌ！）に関するループ（ＤＣ−１１１におけるｉ＝１の初期化、本明細書で以下に説明する指数
【０４７２】
【数１５３】
2009527171.tif 000172
【０４７３】
の抽出（ステップＤＣ−１１２）後、値ｍｎ！に達するまで指標ｉを増分して（ステップＤＣ−１１４）ループ指標ｉを値ｍｎ！と比較する（ステップＤＣ−１１３））。
−指数
【０４７４】
【数１５４】
2009527171.tif 000173
【０４７５】
の抽出（ステップＤＣ−１１２）を：
マスク（（１≪ｂｎｉ）−１）による
【０４７６】
【数１５５】
2009527171.tif 000174
【０４７７】
の高順位ビットのマスク化によるコンパクトな指数
【０４７８】
【数１５６】
2009527171.tif 000175
【０４７９】
の低順位ビットにおいて以下のように表し：
【０４８０】
【数１５７】
2009527171.tif 000176
【０４８１】
このマスク化に以下のコンパクトな指数
【０４８２】
【数１５８】
2009527171.tif 000177
【０４８３】
のｂｎ１の「右」シフトが続く。
【０４８４】
【数１５９】
2009527171.tif 000178
【０４８５】
この汎用ステップＤＣ−１１は符号化のための図６の汎用ステップＣＣ−９に類似である。
ステップＤＣ−１２乃至ＤＣ−１７は、それ自体分解相互関係表現における復号化に特定の図７を参照する本明細書で以上に説明したステップＤ−１１乃至Ｄ−１６に類似である。
他方、テーブルＤ’ｌ！にｗ［ｄｋ］のｍｎ！の指数のコンパクトな表現を含むワード
【０４８６】
【数１６０】
2009527171.tif 000179
【０４８７】
の読出しにより、汎用ステップＤＣ−１８におけるＰｋの指数（テーブルＰ）の更新をステップＤＣ−１８１で行い、次いでＰｋの指数の更新自体
【０４８８】
【数１６１】
2009527171.tif 000180
【０４８９】
をステップＤＣ−１８２で実行する。
次いで、ステップＤＣ−１９乃至ＤＣ２２は、分解相互関係分解を使用する復号化に特定の図７のステップＤ−１９乃至Ｄ−２２に類似である。
【０４９０】
次に、本明細書で以上に説明した変形により提供する種々の利点の説明に進む。
ｍｎ！（および／またはｍｌまたはｍ’ｌ）のテーブルを使用する分解相互関係表現による第１の実施形態の変形は、値ｍｎ！のテーブルのみを使用する主実施形態よりさらに少ない加算／減算演算を含む。
この場合、複雑度の削減は何にもまして最後の位置（即ち、ｍ（ｎ−ｋ）！、ｍ’ｌまたはｍｌがｍｎ！より小さい場合）において大きい。にもかかわらず、複雑度のこの削減はメモリ読出しステップ（ステップＣ−３１、Ｃ−６およびＣ−７）の複雑度の増加を伴う。読み出すべき値は少ないが、他方でアドレス計算がより複雑である。
この場合、関心の持てるトレードオフは（ｍｎ！の指数を持つ）基本分解の規則的な蓄積を含み、テーブルＤｌおよびＤｌ！のアドレス指定を容易にし、次いで（ｎ＋１）セルを持つテーブルＤｍに値ｍｌ！を蓄積する。次いで、値ｍｌを蓄積し、加算／減算の数を効果的に削減するべきである。とはいえ、この測定はステップＣ−６およびＤ−９（対応してＣ−３およびＤ−１９）の前に値ｍＳｋ（対応してｍｗ［ｄｋ］）の読出しを必ず伴うが、一方値ｍ（ｎ−ｋ）！はｋに関する各反復の開始時にのみ読まねばならない。
【０４９１】
その上、分解相互関係表現に比しコンパクトな表現が提供する利益は以下の通りである。
−次に、テーブルＰを更新するステップは符号化（対応して復号化）では単一の加算（対応して減算）以上を含まない。
−指数
【０４９２】
【数１６２】
2009527171.tif 000181
【０４９３】
の計算は、また単一の加算および単一の減算のみを必要とする。
−ワードｅＫを読むアドレス計算は直接的であり、各値Ｋに対し単一のメモリアクセスおよび読出しのみを必要とする。
一方、コンパクトな表現はワード
【０４９４】
【数１６３】
2009527171.tif 000182
【０４９５】
に含む部分ランクＩｋｄｋの指数の抽出（ステップＣＣ−９およびＤＣ−１１）を必要とする。
一方、本明細書の以下で分かるように、部分ランクの素因数分解からの計算に取り、この演算は必ずしも欠点ではない。
【０４９６】
次に、素因数分解からの部分ランクの計算のこのような変形の利点に関する説明に進む。
符号化における（対応して復号化における）ステップＣ−９およびＣＣ−１０（対応してＤ−１１およびＤＣ−１２）の意味する素因数累乗積の計算ステップの複雑度は、従来技術の意味する除算より遥かに小さい複雑度に留まるとはいえ、因数の数と共に大きく増加する。次に、部分ランクの多くの分解指数は実際にはゼロであり、それ故対応する累乗はまた１にある。多くの場合、全指数がゼロであるかまたは第１の指数のみがゼロでない。それ故、ゼロでない指数の累乗のみを検出し、維持することが有用である。詳細な表現では、この検出を検査ｍｎ！または検査ｍ（ｎ−１−ｋ）！（各素因数に対し１回）のみにより実行することができる。
【０４９７】
有利には、コンパクトな表現は単一の検査により全指数がゼロであるか
【０４９８】
【数１６４】
2009527171.tif 000183
【０４９９】
の検査を可能にし、該当する場合ランクｔ’＝１である。さらに、ｅｔ’の高順位ビットの検出はランクｔ’における最大のゼロでない指数の素因数指標の獲得、および符号化における（対応して復号化における）ステップＣ−９（対応してＤＣ−１１）のループ反復数の削減を可能にする。
にもかかわらず、コンパクトな表現におけるように詳細な表現では、ゼロでない指数の検出は複雑度を増すことに留意すべきである。全指数がゼロでなければ、素因数の累乗乗算の複雑度は同じに留まり、この複雑度はその場合ゼロでない指数の検出手順の複雑度により倍加する。
従って第１の変形では、素因数の可能な数が大きくなり（ｋがｎより遥かに小さい）、その累乗乗算の複雑度が検出手順の複雑度より大きい場合にのみ、ゼロでない指数の検出を行うことができる。このため、命令行の増加の犠牲においてこの実施を適用するとしても、位置により異なるループを配備することが出来る。
分解相互関係表現およびコンパクトな表現を結合することがまた可能である。最終位置（小さい値ｍｌ！）に対する中間分解の計算は演算を殆ど伴わない。その場合、分解相互関係表現の使用が好都合であり、この表現は部分ランク指数の抽出を必要としない。他方第１の位置の場合、コンパクトな表現の使用がより好都合である。
【０５００】
次に、既存の符号化／復号化における幾つかの実施例の説明に進む。
【０５０１】
３ＧＰＰ  ＡＭＲ−ＷＢ＋符号化器
３ＧＰＰ  ＡＭＲ−ＷＢ＋符号化器（規格［３ＧＰＰＴＳ２６．３０４］）は代数ベクトル量子化を使用し、その辞書は次元８を有するゴセットネットワークＲＥ８の置換符号結合である。
ＴＣＸ技術は変換による予測符号化に対応する。より詳細には、ＴＣＸ技術は知覚重みフィルタリングの後に適用するＦＦＴ変換符号化法を含む。規格［３ＧＰＰＴＳ２６．３０４］では、得られるＦＦＴスペクトラムを次元ｎ＝８の下位帯域（または補助ベクトル）に細分化し、これらの補助ベクトルを個別に符号化する。補助ベクトルの量子化にはポイントの正規ネットワークＲＥ８を使用する。次元８の量子化辞書は構成上ポイントのネットワークＲＥ８から得るタイプＩの置換符号結合を含む。
規格［３ＧＰＰＴＳ２６．３０４］によるＴＣＸ符号化器では、各置換符号は次元ｎ＝８における所与の符号付先導ベクトルに対応する。ネットワークＲＥ８のポイントの量子化指標を以下のタイプの公式により計算する：
指標＝基本オフセット＋置換ランク
基本オフセットはテーブル化されているが、ランクはシャルクビック公式により計算する。にもかかわらず、これら符号付先導をその絶対先導により表し、置換符号における蓄積および検索を最適化する。関連する絶対先導リストは以下の参考文献に見ることができる。
ラゴット  Ｓ、べセット  Ｂ、ルフェーブル  Ｒ著「３２ｋビット／秒における広帯域ＴＣＸ通話符号化に適用する低複雑度多元速度格子ベクトル量子化」ＩＣＡＳＳＰ論文集、１巻、ＰＰ．５０１−４、２００４年５月
【０５０２】
本発明の種々の変形を示すために、３つの実施例を以下で説明する。最初の２つの実施例は置換ランクの計算（符号化）に関係し、一方は分解相互関係分解表現を使用し、他方はコンパクトな表現を使用する。
本明細書の以下のおよび対応する付録のこれらの実施例では、テーブルＲおよびＰをＲ［０］からＲ［ｍｎ！−１］へおよびＰ［０］からＰ［ｍｎ！−１］へ指標指定するが（本明細書の以上の例により説明するように１からｍｎ！へではなく）、ランク計算処理には特定の影響はない。
【０５０３】
第１の実施例（符号化）
【０５０４】
この実施形態では、分解相互関係基本分解表現を使用する。
その指数を３６セル（＝（８＋１）×４）を持つ２つのテーブルに蓄積する。これらは付録Ａ−１１に提示し、Ｄｌ［３６］（それ故０のダミー分解の蓄積を伴う整数ｌ（０≦ｌ≦８）の分解指数を含む）およびＤｌ！［３６］（その階乗分解指数を含む）と表示するテーブルである。
３、５および７の累乗の３つのテーブルをまた以下のように蓄積する：
Ｐｏｗ３［４］＝｛１、３、９、２７｝；Ｐｏｗ５［３］＝｛１、５、２５｝；
Ｐｏｗ７［３］＝｛１、７、４９｝
【０５０５】
この実施形態では、一方が整数の基本分解Ｓｋであり、他方が商の中間分解である２つの中間分解から、部分ランク分解を判断する。
【０５０６】
【数１６５】
2009527171.tif 000184
【０５０７】
以上に示すように、（７−ｋ）！および
【０５０８】
【数１６６】
2009527171.tif 000185
【０５０９】
の基本分解（ｑ＋１）に対応する基本分解からＲｋの中間分解を判断するよりむしろ、Ｒｋ＋１の中間分解および（７−ｋ）および
【０５１０】
【数１６７】
2009527171.tif 000186
【０５１１】
の２つの基本分解から、この中間分解を判断する。
【０５１２】
【表１１】
2009527171.tif 000187
【０５１３】
本発明は以上の表１１において各位置に対して示すｍ（７−ｋ）！および
【０５１４】
【数１６８】
2009527171.tif 000188
【０５１５】
の最大値に関する知見を適用し、これらの限界より大きな指標を持つ素因数指数を計算しないようにする。
【０５１６】
対応する処理を付録Ａ−１２に提示する。位置に関するループを分解して相互関係を表示することを注記することにする。また、商の素因数指数ｐｉを４セルを持つテーブルＲが有するセルＲ［ｉ−１］に蓄積することを注記することにする。
【０５１７】
第２の実施例（符号化）
【０５１８】
３ＧＰＰ  ＡＭＲ−ＷＢ＋符号化器による変形では、基本分解をコンパクトに表現する。その指数を含むワードを９セル（＝（８＋１））を持つ２つのテーブルに蓄積する。付録Ａ−２１を参照すると、テーブルＤ’ｌは整数ｌ（０≦ｌ≦８）の分解のためのワードを含み（それ故ｌ＝０の分解のダミー蓄積を伴い）、テーブルＤ’ｌ！はその階乗分解のためのワードを含む。
３、５、および７の累乗をまた（使用しない累乗の０のダミー蓄積を伴う）１２セルを持つテーブルＰｏｗ［１２］に蓄積する。
２つが整数Ｓｋおよび階乗（７−ｋ）！の基本分解であり、第３の中間分解が部分ランクの分母の中間分解である３つの中間分解から、部分ランクの分解を判断する。
【０５１９】
【数１６９】
2009527171.tif 000189
【０５２０】
以前に示したように
【０５２１】
【数１７０】
2009527171.tif 000190
【０５２２】
の基本分解ｑからＰｋの中間分解を判断するよりむしろ、Ｐｋ＋１の中間分解からおよび
【０５２３】
【数１７１】
2009527171.tif 000191
【０５２４】
の基本分解から、この分解を判断する。４つのこの中間分解指数を含むコンパクトなワードを付録Ａ−２２で「ｅＰ」と表示する。また、「ｅｌ」は４つの部分ランク分解指数を含むコンパクトなワードを表示する。
ここで再び、ｍ（７−ｋ）！に関する知見を適用し、部分ランク分解を表現するコンパクトなワード指数ｍ（７−ｋ）！のみを抽出する。
【０５２５】
対応する処理は付録Ａ−２２の主題である。ここで再び、位置に関するループを分解して相互関係を表示する。
【０５２６】
第３の実施例（復号化）
【０５２７】
第３の実施例は３ＧＰＰ  ＡＭＲ−ＷＢ＋符号化における置換ランクの復号化を扱う。
第１の実施例におけるように基本分解の分解相互関係表現を好ましくは使用し、第２の実施例におけるように３つの項の部分ランク分解を好ましくは使用する。しかしながら位置に関するループは分解相互関係表示しない。
以前に示したように基本分解からＰｋの中間分解を判断するよりむしろ、Ｐｋー１の中間分解からおよび
【０５２８】
【数１７２】
2009527171.tif 000192
【０５２９】
の基本分解から、Ｐｋの中間分解を判断する。４つのこの中間分解指数をテーブルＰに蓄積する。同様にＰｋの中間分解からおよび（７−ｋ）！の基本分解から、別の中間分解（商の中間分解）を計算し、その指数をテーブルＲに蓄積する。
対応する処理は付録Ａ−３の主題である。商の（対応して積の）素因数指数ｐｉの指数を４セルを持つテーブルＲ（対応してＰ）のセルＲ［ｉ−１］（対応してＰ［ｉ−１］）に蓄積する。
【０５３０】
従って、本明細書の以上の第１の例は（商を含む）２つの項の部分ランク分解を使用し、他の２つの例は３つの項（分子の２つおよび分母の１つ）の分解を使用する。２つの符号化モードは個別の位置処理を使用し、ゴセットネットワークのポイントの８つの位置に関するループの分解相互関係表示によるアルゴリズムにおいて読出さず、ハードウェアにより布線するｍｌ！またはｍｌの項を使用するが、復号化モードはｍ８！（＝４）の項のみを使用する。
【０５３１】
ＴＤＡＣ符号化器の実施例
【０５３２】
最後の実施例は、１６ｋＨｚ（広帯域）でサンプル化するディジタルオーディオ信号の符号化に使用する出願者のＴＤＡＣ知覚周波数符号化器に関係し、その原理を本明細書で以下に説明する。
【０５３３】
ＴＤＡＣ符号化器は可変次元およびリゾリューション並びに最大次元１５を持つ統計的ベクトル量子化を使用する。
次元８を持つポイントの正規ネットワークＲＥ８の置換符号の場合、本発明は本質的に複雑度の削減を可能にする。一方１２より大きな次元の置換符号を使用するＴＤＡＣ符号化器の場合、本発明は非常に有利であることを証明するが、これは本発明が複雑度の削減のみならず、また固定点プロセッサに関する符号化器の実施を可能にし、その最大精度を符号のない３２ビットの整数に限定するからである。本発明がなければ、このような実施は極めて複雑であろう。
【０５３４】
この符号化器の原理は以下の通りである。
帯域幅を７ｋＨｚに制限し、１６ｋＨｚでサンプル化するオーディオ信号を３２０サンプル（２０ｍｓ）のフレームに細分化する。５０％の重複を持つ６４０サンプルの入力信号ブロック（２０ｍｓ毎のＭＤＣＴ分析のリフレッシュに相当する）に、修正離散コサイン変換（modified discrete cosine transform、「ＭＤＣＴ」）を適用する。最後の３１の係数をゼロに設定する（その場合、最初の２８９の係数のみが０と異なる）ことにより、スペクトラムを７２２５Ｈｚに制限する。マスク化曲線をこのスペクトラムから判断し、全マスク係数をゼロに設定する。スペクトラムを不等幅の３２帯域に分割する。信号の変換係数により任意のマスク帯域を判断する。各帯域のスペクトラムに対し、ＭＤＣＴ係数のエネルギを（測定尺度要因を推定するために）計算する。３２の測定尺度要因は信号スペクトル包絡線を構成し、信号スペクトル包絡線を次いで量子化、符号化し、フレームで送信する。ビットの動的割当はスペクトル包絡線の量子化解除バージョンから計算する各帯域のマスク化曲線に基づき、符号化器および復号化器のバイナリ割当間の両立性を得るようにする。タイプII置換符号結合を構成上含む辞書である、サイズに応じてネスト化する辞書を使用するベクトル量子化器により、各帯域にける規格化ＭＤＣＴ係数を次いで量子化する。最後に、トーンおよび音声情報、スペクトル包絡線並びに符号化係数を多重化し、フレームで送信する。
【０５３５】
置換ランク（符号化）に関する計算の実施例はここでコンパクトな分解表現を使用する。使用する置換符号の次元は可変であり、位置に関するループは分解相互関係を表示しない。この実施形態は部分ランク分解のゼロでない指数の検出法を示す。
ここで、基本分解をコンパクトに表現する。その指数を含むワードを１６セル（＝（１５＋１））を持つ２つのテーブルに蓄積する。付録Ｂ−１で、テーブルＤ’ｌは整数ｌ（０≦ｌ≦１５）の分解のためのワードを含み、テーブルＤ’ｌ！はその階乗分解のためのワードを含む。
３の累乗をまた８セルを持つテーブル（Ｐｏｗ３と表示）に蓄積し、５、７、１１、および１３の累乗を２０セル（使用しない累乗のための０のダミー蓄積を伴う）を持つテーブル（Ｐｏｗと表示）に蓄積する。
【０５３６】
対応する処理を付録Ｂ−２において再度書き換える。
【０５３７】
勿論、本発明は例により本明細書で以上に説明した実施形態に限定しない。本発明は他の変形を包含する。
【０５３８】
出願者の知見では、本発明は置換符号における素因数累乗分解の最初の使用を含む。一方置換符号によるベクトル量子化におけるように結合表現の計算を配備する場合、この使用は特に有利である。従って一般に、本発明は置換ランクとは異なるが１つまたは複数の置換符号による符号化／復号化における任意の結合表現にこの素因数累乗分解を使用することを目的とする。
【０５３９】
本発明は、通話信号の符号化／復号化、例えば電話端末、特にセルラーにおいて有利に適用可能である。とはいえ、本発明はあらゆるタイプの信号、特にイメージまたはビデオ信号の符号化／復号化および符号化変調に適合する。
【０５４０】
本発明はまた置換符号を使用するディジタル信号の符号化／復号化デバイスのメモリに蓄積するように設計するコンピュータプログラムを目的にする。その場合、このプログラムは本発明の意味する方法のステップを実施する命令を含む。典型的に、本明細書で以上に説明した図４乃至図８はこのようなプログラムが含むことのできるアルゴリズムのフローチャートに相当することができる。
【０５４１】
本発明はまた置換符号を使用するディジタル信号の符号化／復号化デバイスを目的にし、図９を参照して、
−上述のタイプのコンピュータプログラム命令および選択する整数の事前記録分解表現を蓄積するメモリユニットＭＥＭおよび、
−本発明の意味する方法を実施するこのメモリユニットＭＥＭにアクセスする計算モジュールＰＲＯＣ
を含む。
【０５４２】
これらの手段ＭＥＭ、ＰＲＯＣを設計し、
・ソース符号化器の指標指定モジュールにおいて、または
・チャネル復号化器の指標指定モジュールにおいて
・選択する符号ベクトルｙから置換ランクｔを供給し（図９の実線の矢印）、
・ソース復号化器の復号化モジュールの、または
・チャネル符号化器の符号化モジュールの
・置換ランクｔから再構築する符号ベクトルｙを供給することができる（図９の破線の矢印）。
【０５４３】
勿論、メモリＭＥＭに事前記録する表現はアドレスの内容形式（分解相互関係表現）またはビットワード形式（コンパクトな表現）でありうる。
【０５４４】
付録
【０５４５】
【数１７３】
2009527171.tif 000193
【数１７４】
2009527171.tif 000194
【数１７５】
2009527171.tif 000195
【数１７６】
2009527171.tif 000196
【数１７７】
2009527171.tif 000197
【数１７８】
2009527171.tif 000198
【数１７９】
2009527171.tif 000199
【数１８０】
2009527171.tif 000200
【数１８１】
2009527171.tif 000201
【数１８２】
2009527171.tif 000202
【数１８３】
2009527171.tif 000203
【数１８４】
2009527171.tif 000204
【数１８５】
2009527171.tif 000205
【数１８６】
2009527171.tif 000206
【数１８７】
2009527171.tif 000207
【図面の簡単な説明】
【０５４６】
【図１Ａ】ベクトル量子化によるソース符号化／復号化を示す。
【図１Ｂ】変調／量子化の双対性を示す。
【図２】符号化技術を説明するための図である。
【図３】符号化技術を説明するための図である。
【図４】本発明の使用による置換ランクの符号化／復号化原理を示す。
【図５】第１の実施形態に従う本発明の使用による置換ランクの符号化のための処理演算を示し、この演算ではこの計算に使用する項の素数累乗分解指数の分解相互関係表現を提供する。
【図６】第２の実施形態により本発明を使用する置換ランクの符号化のための処理演算を示し、この演算では分解指数のコンパクトな表現を提供する。
【図７】第１の実施形態により本発明を使用する置換ランクの復号化のための処理演算を示し、この演算では分解指数の分解相互関係表現を提供する。
【図８】第２の実施形態により本発明を使用する置換ランクの復号化のための処理演算を示し、この演算では分解指数のコンパクトな表現を提供する。
【図９】本発明を実施する符号化／復号化デバイスを図的に表す。
【符号の説明】
【０５４７】
ＭＥＭ    メモリユニット
ＰＲＯＣ  計算モジュール
【図１Ａ】
2009527171.tif 000226
【図１Ｂ】
2009527171.tif 000227
【図２】
2009527171.tif 000228
【図３】
2009527171.tif 000229
【図４】
2009527171.tif 000230
【図５】
2009527171.tif 000231
【図６】
2009527171.tif 000232
【図７】
2009527171.tif 000233
【図８−１】
2009527171.tif 000234
【図８−２】
2009527171.tif 000235
【図９】
2009527171.tif 000236
【手続補正書】
【提出日】平成21年3月19日(2009.3.19)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
結合表現の計算を含む置換符号を使用するディジタル信号の符号化／復号化方法であって、
前記結合表現を素因数累乗分解により表し、選択する整数の事前記録分解表現をメモリから読出すことにより判断する方法。
【請求項２】
請求項１に記載の方法において、前記置換符号が、各部分ランクが前記結合表現の１つに対応する部分ランクの累積を含む置換ランクを表す量の前記計算を含む方法。
【請求項３】
請求項２に記載の方法において、ベクトル量子化ディジタル信号を符号化する場合に、前記置換ランクの前記計算を使用し、以前のステップで実行した先導ベクトルの前記構成要素の前記置換を指標指定し、入力ベクトルに最も近い符号ベクトルを判断することとする方法。
【請求項４】
請求項２に記載の方法において、ベクトル量子化ディジタル信号を復号化する場合に、置換ランクの所与の値から、
−構成する符号ベクトルの少なくとも１つの仮定する構成要素に従い前記所与の値に近い置換ランクを表す少なくとも１つの量を計算し、
−前記置換ランクを表す量が前記ランクの前記所与の値との近接条件を満たせば、前記仮定する構成要素の前記選択が妥当であるとする方法。
【請求項５】
請求項４に記載の方法において、一方で前記仮定する構成要素に関連する部分ランクへおよび他方で前記仮定する構成要素の増分に対応する構成要素に関連する部分ランクへの前記部分ランクの累積により前記所与の前記ランク値を纏めて扱うことができれば、前記近接条件を満たすこととする方法。
【請求項６】
請求項３に記載の方法において、前記符号化／復号化がベクトル量子化によるソース符号化／復号化の前記タイプに関するものであることとする方法。
【請求項７】
請求項２に記載の方法において、前記符号化／復号化がチャネル変調符号化／復号化の前記タイプに関するものであり、前記符号化／復号化が、
−送信前に前記置換ランクからの符号ベクトルの前記判断および
−受信時に受信ベクトルに対応する符号ベクトルからの前記置換ランクの前記計算
を含むこととする方法。
【請求項８】
請求項２に記載の方法において、前記置換符号がシャルクビック計数を使用し、符号ベクトル（ｙ０、．．．、ｙｎ‐１）の切取り（ｙｋ、．．．、ｙｎ−１）に関連する部分ランク
【数１】
2009527171.tif 000237
が、
【数２】
2009527171.tif 000238
により表され、上式で
【数３】
2009527171.tif 000239
−が０乃至ｍの範囲の整数指標ｉに対する積を表し、
【数４】
2009527171.tif 000240
−が０乃至ｍの範囲の指標ｉに対する総和を表し、
−ｌ！がｌ＞０の場合  ｌ！＝１×２×３×．．．×（ｌ−１）×ｌであり、０！＝１である前記整数ｌの前記階乗値であり、
−前記整数ｎが、符号ベクトルが含む構成要素の前記総数に対応する前記置換符号の前記次元であり、
−０とｎ−１との間の前記整数ｋが前記符号ベクトルのｋ番目の構成要素ｙｋの前記指標であり、
−前記整数ｑが、前記符号ベクトルが含む個別構成要素の前記数であり、
−項ｗｋｄがｋとｋ−１との間の指標構成要素の前記数を表し、１つのかつ同じ指標構成要素ｄの数に等しい値を有する
こととする方法。
【請求項９】
請求項８に記載の方法において、請求項３と共同して、ｎ−１乃至０の範囲の指標ｋに対する前記符号ベクトル（ｙ０、．．．、ｙｎ‐１）の切取り（ｙｋ、．．．、ｙｎ−１）に従い各部分ランクを推定する前記部分ランク
【数５】
2009527171.tif 000241
の前記累積の判断により、符号化に関して前記ランクの前記計算が行われることとする方法。
【請求項１０】
請求項９に記載の方法において、前記項Ｓｋ
【数６】
2009527171.tif 000242
の前記値に関する検査を実行し、前記項Ｓｋがゼロであれば前記部分ランク
【数７】
2009527171.tif 000243
の推定を回避することとする方法。
【請求項１１】
請求項８に記載の方法において、請求項４と共同して、前記部分ランク
【数８】
2009527171.tif 000244
の累積解除を表す量の前記計算が復号化において行われ、０乃至ｎ−１の範囲の指標ｋの前記符号ベクトルの前記構成要素ｙｋを判断することとする方法。
【請求項１２】
デバイスのメモリに蓄積する置換符号を使用するディジタル信号の符号化／復号化のためのコンピュータプログラムであって、コンピュータプログラムが請求項１に記載する方法の各ステップを実施する命令を含むコンピュータプログラム。
【請求項１３】
置換符号を使用するディジタル信号の符号化／復号化デバイスであって、本デバイスが、
−請求項１２に記載するコンピュータプログラムの前記命令および選択する整数の事前記録分解表現を蓄積するメモリユニットと、
−前記メモリユニットにアクセスし、請求項１に記載する方法を実施する計算モジュール
を含むことを特徴とするデバイス。
【国際調査報告】
2009527171.tif 000245
2009527171.tif 000246
2009527171.tif 000247
2009527171.tif 000248