(57)【要約】【課題】モデムシステムデザイン技術において、多係数変換計算をより有効に行うための装置及び方法を提供する。【解決手段】除法操作をほとんど又はまったく使用しない多係数変換（ＭＭＣ）出力の計算を可能にする方法及び装置を提供する。除法操作の代わりに、乗法及び論理シフト操作が使用され、擬似の商及び擬似の剰余を作るために使用され、最終段階で修正され、正確なＭＭＣ出力を作り出してもよい。除法は通常、乗法及び論理シフトより効果的でないから、これはより効果的な手段を可能にする。その方法及び装置は、部分商リングシステムでディジットの数を変える部分商に分割されるＭＭＣ入力で動作する。乗法及び論理シフト操作は長い除法技術から導かれる手順によりそれぞれの部分商で行われる。
2005519506.tif 000002
【特許請求の範囲】
【請求項１】
所定の通信信号パラメータに情報ビットのフレームを写像するように構成された手段を有する通信システムの使用のため、複数の係数と関連した複数の指標値を取得するための多係数変換（ＭＭＣ）方法であって、
入力を取得し、
複数の部分商として前記入力を表わし、
少なくとも１つの前記部分商に被乗数を掛ける乗法操作を実行し、
前記被乗数と関連し、逆係数乗法操作に応答する指標値を決定する、
ことを含んでいることを特徴とする方法。
【請求項２】
整数の予想逆数に関連する被乗数を取得することをさらに含み、乗法操作を実行することは少なくとも１つの前記部分商に被乗数を掛けることを含んでいる請求項１に記載の方法。
【請求項３】
少なくとも１つの擬似剰余が作られる請求項２に記載の方法であって、少なくとも１つの前記擬似剰余を検査し、前記擬似剰余が所定範囲内にあるかどうかを決定し、それが前記所定範囲内にない場合には、前記擬似剰余が前記所定範囲内になるように前記擬似剰余を調整することをさらに含んでいる方法。
【請求項４】
少なくとも１つの擬似剰余が作られる請求項２に記載の方法であって、少なくとも１つの前記擬似剰余を検査し、前記擬似剰余が所定数より大きいか又は等しいかどうかを決定し、そうであれば、前記数を前記擬似の剰余から引くことをさらに含んでいる方法。
【請求項５】
前記擬似の剰余が前記所定数より小さくなるまで、前記所定数は前記擬似の剰余から引かれる請求項４に記載の方法。
【請求項６】
少なくとも１つの前記被乗数が予め計算され、表に格納される請求項２に記載の方法であって、少なくとも１つの被乗数を前記表から取得することをさらに含んでいる方法。
【請求項７】
前記被乗数のディジットＮ3の最大数、整数のディジットＮ2の最大数、及び前記部分商のほとんど最上位のディジットｎ（ｊ）の最大数は、不等式Ｎ3＞Ｎ2＋ｎ（ｊ）により関係付けられる請求項２に記載の方法。
【請求項８】
前記被乗数は次式：Ｃi＝floor（ＢN3／Ｙi）により計算され、Ｂはナンバリングシステムの基数であり、Ｎ3は前記被乗数のディジットの最大数であり、Ｙiは整数である請求項２に記載の方法。
【請求項９】
前記入力は、Ｑi-1＝Ｑi-1,0＋Ｑi-1,1*Ｂn(0)＋...＋Ｑi-1,k*Ｂn(0)+n(1)+...n(k-1)の形の部分商として表わされている請求項２に記載の方法。
【請求項１０】
出力した擬似の商の部分商は、次式：Ｑi,j＝((Ｑi-1,j＋Ｒi,j+1*Ｂn(j))*Ｃi)＞＞Ｎ3により、前記入力の一部分に前記被乗数Ｃiを掛けることにより得られ、前記部分商計算の前記出力された擬似の剰余は、次式：Ｒi,j＝(Ｑi-1,j＋Ｒi,j+1*Ｂn(j))−（Ｑi,j*Ｙi)により得られ、Ｂはナンバシステムの基数である請求項８に記載の方法。
【請求項１１】
出力された剰余Ｒi及び新しい商Ｑi＝Ｑi,0＋Ｑi,1*Ｂn(0)＋...＋Ｑi,k*Ｂn(0)+n(1)+...n(k-1)を作ることをさらに含んでいる請求項８に記載の方法。
【請求項１２】
複数のディジットにより表わされた入力データを受け取るように構成された入力と、
２個の数を掛けるための乗法手段と、
複数の部分商として前記入力を表わすように構成されたプロセッサとを備え、少なくとも１つの部分商に被乗数を掛け、前記被乗数と関連した指標値を作り、前記指標値は前記乗法操作に応答することを特徴とする多係数変換（ＭＭＣ）エンコーダ。
【請求項１３】
前記被乗数は整数の予想逆数に関連付けられている請求項１２に記載の係数エンコーダ。
【請求項１４】
前記プロセッサは擬似の剰余を発生するようにさらに構成され、前記擬似の剰余が所定範囲になるかどうかを調べるようにさらに構成されている請求項１３に記載の係数エンコーダ。
【請求項１５】
前記プロセッサは擬似の剰余を発生するようにさらに構成され、前記擬似の剰余が所定数より大きいか又は等しいかどうかを検査するようにさらに構成され、前記擬似の剰余が前記所定数より大きい場合には前記擬似の剰余から前記所定数を引くようにさらに構成されている請求項１３に記載の係数エンコーダ。
【請求項１６】
前記プロセッサは、前記擬似の剰余が前記所定数より小さくなるまで前記擬似の剰余から前記所定数を引き続けるように構成されている請求項１５に記載の係数エンコーダ。
【請求項１７】
少なくとも１つの被乗数を格納する格納手段をさらに含んでいる請求項１３に記載の係数エンコーダ。
【請求項１８】
前記プロセッサは、ディジットＮ3の最大数で被乗数を処理するように構成され、さらに、ディジットＮ2の最大数により係数を処理するように構成され、さらに、前記部分商のほとんど最上位のディジットｎ（ｊ）の最大数により部分商として表わされた入力を処理するように構成され、これらの数は不等式Ｎ3＞Ｎ2＋ｎ（ｊ）により関係付けられる請求項１３に記載の係数エンコーダ。
【請求項１９】
逆数概算計算手段をさらに含み、前記逆数概算は、次式：Ｃi＝floor（ＢN3／Ｙi）により計算され、Ｂはナンバシステムの基数であり、Ｎ3は前記被乗数のディジットの最大数であり、Ｙiは整数である請求項１３に記載の係数エンコーダ。
【請求項２０】
前記入力は、Ｑi-1＝Ｑi-1,0＋Ｑi-1,1*Ｂn(0)＋...＋Ｑi-1,k*Ｂn(0)+n(1)+...n(k-1)の形で入力値を取得するように構成されている請求項１３に記載の係数エンコーダ。
【請求項２１】
前記プロセッサは、次式：Ｑi,j＝((Ｑi-1,j＋Ｒi,j+1*Ｂn(j))*Ｃi)＞＞Ｎ3により、前記入力の一部分に概算逆係数を掛けることにより出力した擬似の商の部分商を取得するように構成され、前記プロセッサは、さらに次式：Ｒi,j＝(Ｑi-1,j＋Ｒi,j+1*Ｂn(j))−（Ｑi,j*Ｙi)により、擬似の剰余を取得するように構成され、Ｂはナンバリングシステムの基数である請求項１８に記載の係数エンコーダ。
【請求項２２】
前記プロセッサはさらに、出力された剰余Ｒi及び新しい商Ｑi＝Ｑi,0＋Ｑi,1*Ｂn(0)＋...＋Ｑi,k*Ｂn(0)+n(1)+...n(k-1)を発生するように構成されている請求項１８に記載の係数エンコーダ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般に、データ伝送のための数学アルゴリズムに関し、より詳細には、伝送されたデータの係数変換を行うためのアルゴリズムに関する。
【０００２】
【背景技術】
伝統的なコンピュータシステムは、電話線又は他の通信媒体に接続されるモデムを使用してデータを送信する。一般的に、そのようなシステムにおいて、サーバーモデムとクライアントモデムの２つのタイプのモデムがある。信号方向は、通常、この領域では、サーバモデムからクライアントモデムへのダウンストリームと、クライアントモデムからサーバモデムへのアップストリームと呼ばれる。サーバモデムは、通常、インターネットサービスプロバイダー（ＩＳＰ）により使用され、クライアントモデムにダウンストリームで信号を送り、クライアントモデムからアップストリームで信号を受け取る。同様に、クライアントモデムは、通常、ＩＳＰの顧客により使用され、ＩＳＰサーバモデムにアップストリームで信号を送り、ＩＳＰサーバモデムからダウンストリームで信号を受け取るように構成されている。
【０００３】
各タイプのモデムは、通常、アナログ・デジタル変換器及びデジタル・アナログ変換器（Ａ／Ｄ−Ｄ／Ａ変換器）を使用し、それは、通常、ＣＯＤＥＣと呼ばれる単一装置に結合される。このＣＯＤＥＣは、入ってくるアナログ信号を信号処理装置により処理可能なデジタル信号に変換し、信号処理装置からのデジタル信号を電話線のような通信媒体で送信可能な出て行くアナログ信号に変換する。多くの場合、サーバモデムはそれら自身のＣＯＤＥＣを有していないが、電話網内のＣＯＤＥＣに依存し、変換を行う。信号処理装置は、時々「データポンプ」と呼ばれるが、伝統的に、デジタル信号プロセッサ（ＤＳＰ）として公知な専用チップであり、デジタル信号を情報ビットに及びその逆に変換するためのアルゴリズムにより予めプログラム化されている。
【０００４】
モデムはまた、時々「コントローラ」と呼ばれる第２専用チップも含んでおり、それはＤＳＰを制御するために予めプログラム化されたマイクロプロセッサであり、ＤＳＰからの情報ビットをコンピュータシステムにより使用可能なデータに変換し、コンピュータシステムからのデータをＤＳＰのための情報ビットに変換する。コントローラはあるスキームを実行し、情報ビットの誤りを修正してもよく、また、あるスキームを実行し、より効率の良い伝送のため情報ビットを圧縮してもよい。幾つかのモデムはホストコンピュータシステムにおいて制御機能を実行することにより専用コントローラチップを取り除く。これらのモデムは、通常、コントローラレスモデムと呼ばれている。他のモデムは、通常、ホスト信号処理（ＨＳＰ）と呼ばれる技術を使用して、ホストコンピュータシステムの信号処理機能の幾つか又はすべてを実行してもよい。
【０００５】
モデムの通信システムで使用されるモデム変調スキームは、通常、アナログ信号により定義される。多くの変調スキームは正弦波の特性を変えることにより作動し、その周波数はキャリヤ周波数と呼ばれている。例えば、クアドラチュア振幅変調（ＱＡＭ）は一定の割合でキャリヤ周波数の振幅及び位相を変えることにより作動する。他の変調スキームはキャリヤなしで作動する。例えば、パルス符号変調（ＰＣＭ）は一定の割合で信号のレベルを直接変えることにより作動する。どちらの場合も、この一定の割合は、ボー周波数又は符号周波数として公知である。ほとんどの現代のモデムはデジタル信号処理技術を使用するから、これらのアナログ信号はサンプリングレートを使用してデジタル形式に変換されなければならず、それはボー周波数の倍数となることがよくある。したがって、サンプルの整数は「ボー」又は「符号」を表わすものとして考えられる。それが使用する変調スキーム及びアルゴリズムの複雑さにより、個別又はグループのいずれかにおいて、符号は一定数の情報ビットを表わしている。情報ビットと送られた符号との関係はスキームをマッピングすることにより決定される。秒毎に送られる情報ビットの平均数は、通常、「データレート」又は「ビットレート」と呼ばれている。
【０００６】
モデム変調スキームのための標準プロトコルは通信産業界において互換性を向上させるために開発された。例えば、国際電気通信連合（ＩＴＵ）、以前の国際電信電話諮問委員会（ＣＣＩＴＴ）は、モデム業界の技術を変えることにより発展する標準提案を開発した。Ｖ.２１，Ｖ.２２及びＶ.２３のような初期の提案は、二重通信のための周波数分割多重化（ＦＤＭ）を使用する。Ｖ.３２の２，Ｖ.３４，Ｖ.９０及びＶ.９２のようなより新しい提案は、二重通信のためエコーキャンセレーションを使用する。Ｖ.９０及びＶ.９２は少なくとも一方向においてＰＣＭ変調を使用し、二重通信を説明する。Ｖ.９０又はＶ.９２により設計されるモデムは、時々５６kbpsモデムと呼ばれ、ダウンストリームの方向で特定された最大ビットレートに関連している。特定の提案を実行するすべてのモデムは、複数のベンダーの製品の間での相互運用性を保証するため、データ伝送システムにおいてデータを送信する時に特定の変調及びマッピングスキームを使用しなければならない。
【０００７】
通常、変調スキームは配置として公知な許容可能な符号パラメータのセットを定義する。マッピング方法は情報ビットを表わす方法を供給し、配置の利用可能な点により送信される。Ｖ.９０及びＶ.９２の両方の提案において、多係数変換（ＭＭＣ）は、情報ビットの長いフレームを異なるサイズの複数の配置に写像するためマッピングスキームとして使用される。特に、Ｖ.９０の提案はＭＭＣを特定し、サーバモデムからクライアントモデムへのダウンストリームの方向において使用される。Ｖ.９２の提案はＭＭＣを特定し、両方の方向で使用される。
【０００８】
ＭＭＣの伝統的な適用では、入力データは商を形成するために使用され、それは１セットの公知な係数により連続して割られる。各除法の剰余は処理の出力として使用される。通常、除法操作は行うのに複数のサイクルを要求するので、この処理はモデムプロセッサに非常な負担となる。また、通常、入力データはモデムのプロセッサが１回の作動で処理可能なものより大きい。これらの問題に取り組むため、幾つかの技術が開発され、そのような計算を実行する。１つの通常使用される方法は長除法アルゴリズムを使用し、入ってくる商は幾つかのセグメントに分割され、それぞれ別個の除法操作を要求する。
【０００９】
一般的に、ＭＭＣアルゴリズムは、入力として負でない整数の数Ｑ0をとる。さらに、アルゴリズムは入力として複数の係数Ｙiをとり、１  ｉ  Ｍはすべて正の整数である。通常、Ｙi  ２及びＱ0＜Ｙ1*Ｙ2*...ＹMである。アルゴリズムの出力は１セットの値Ｑi及びＲiであり、すべて負でない整数で、以下の数学的関係が適用されるようになっている。
Ｑ0＝Ｙ1*Ｑ1＋Ｒ1
Ｑ1＝Ｙ2*Ｑ2＋Ｒ2
...
Ｑi-1＝Ｙi*Ｑi＋Ｒi
０≦Ｒi＜Ｙi
同等に、Ｑ0はＭＭＣ処理及び各係数Ｙiにより作られた剰余により表わすことができ、
Ｑ0＝Ｒ1＋Ｒ2Ｙ1＋Ｒ3Ｙ1Ｙ2＋...＋ＲMＹ1Ｙ2...ＹM-1＋ＱMＹ1Ｙ2...ＹM
通信システムにおける通常の場合のように、Ｑ0＜Ｙ1*Ｙ2*...ＹMの場合には、その時、ＱM＝０であることに注意しなさい。
【００１０】
このアルゴリズムは、除法操作が各係数のためになされることを要求し、各係数のために出力された商及び剰余を生じる。入力が上述したように制限される場合には最後の係数ＹMに対応する除法が省かれ、ＱMが０となることが予め知られるようになっている。その場合には、それは、
ＲM＝ＱM-1
で示されることができる。
【００１１】
以下の例はＭＭＣの数学的概念を示している。すべての値は十進法の形式で表わされている。この例では、入力Ｑ0＝９３３であり、４個の入力係数Ｙ1＝５，Ｙ2＝６，Ｙ3＝７，Ｙ4＝８がある。処理には複数のステップがある。
９３３の入力値を受け取る。
前記入力を第１係数５で割る。９３３／５＝商１８６、剰余３。
新しい商を第２係数６で割る。１８６／６＝商３１、剰余０。
新しい商を第３係数７で割る。３１／７＝商４、剰余３。
新しい商を第４係数８で割る。４／８＝商０、剰余４。
ＭＭＣ処理では、最後の出力が、それぞれ３，０，３及び４である。Ｑ0＜Ｙ1Ｙ2Ｙ3Ｙ4（９３３＜１６８０）であり、そのため、Ｑ4＝０であるから、最後の除法は省かれることに注目しなさい。最後の剰余Ｒ4は最後から２番目の商Ｑ3に等しい。
【００１２】
ＭＭＣの伝統的な手段では、幾つかのシステムの制限がある。通常、ＭＭＣを実行する装置は、二進法、又は基数２の、ナンバシステム（number system）の値で作動する。しかし、ＭＭＣ計算は基数Ｂのナンバシステムで実行可能である。例えば、十進法のナンバシステム（Ｂ＝１０）が使用可能であろう。通常、基数Ｂのナンバリングシステムのディジットの限定数を有する値で計算操作を行うことを装置は強いられる。通常、Ｑ0は装置が１回の計算で処理できるより多くのディジットで表わされるから、通常、除法の結果を計算するために「長除法」方法が使用される。
【００１３】
長除法は数学で周知な反復技術である。１８１６年に発行されたCharles Huttonによる「数学の講義」において、このタイプの除法は以下のように説明されている。「被除数は複数の部分に分割され、試験により、それらの部分のそれぞれに除数がどのくらいの頻度で含まれているかを次々に見つけられ、１つの数に商の幾つかの数字を次々に配列する。」（１８〜１９頁）。このごろは、通常、長除法は、大きな数（すなわち、暗算で割り算するのが困難な数）の割り算をするため鉛筆と紙による方法として小学校で教えられている。
【００１４】
長除法はまた「大きい」数を割り算を計算するための方法としてコンピュータ学の技術においても周知であり、それは目標のコンピュータでの単一の記録又は単一の計算に適応可能なもの以上に正確な数として定義されている。例えば、１９８１年に発行されたDonald Knuthによる「コンピュータプログラミングの技術」の第２版において、コンピュータアルゴリズムは長除法の一般的な問題を解決するために表わされている（２５５〜２６０頁）。鉛筆と紙による方法でのように、コンピュータ長除法は１以上の大きな数を一連の小さな数に分割することを要求している。Knuthのアルゴリズムは任意の基数になるこれらの小さい数を可能にし、（Huttonにより教示された鉛筆と紙による方法でのように）それらは基数１０の数のディジットとなることができ、又は、コンピュータは通常、二進法の算数のために設計されているから、おそらく、それらは２の累乗の基数となることができるだろう。例えば、小さい数は４ビットのショートワードとすることができるだろう（同等に、基数１６のディジット）。
【００１５】
ＭＭＣは直接、Knuthの長除法を使用して実行することができるだろう。しかし、幾つかの簡素化はＭＭＣの性質によりなされることができる。例えば、Knuthのアルゴリズムは、除数と被除数の両方が大きい数になることを許容し、それは小さい数に分割される。しかし、ＭＭＣにおいて、通常、除数はコンピュータにより直接処理されるのに十分小さく、被除数だけが分割される必要がある。また、Knuthのアルゴリズムにおいて、中間の商は幾つかの誤りを有することのある概算である。そのため、中間の剰余はそれらが有効な範囲になることを保証するために試験される必要がある。ＭＭＣの適用において、除数及び被除数の分割はこの試験が排除可能なように強要されることができる。簡略化された長除法アルゴリズムを使用するＭＭＣ方法の１つの例は、Xuming Zhangにより開示された、多係数変換コンテキストでのショートワードの除法技術を実行するための方法及び装置という米国特許6,065,030において見出すことができる。
【００１６】
Zhangの技術を使用してＭＭＣを実行するため、Ｑ0は最初、以下のように、ｋ＋１の部分に分割される。
Ｑ0＝Ｑ0,0＋Ｑ0,1*Ｂn(0)＋Ｑ0,2*Ｂn(0)+n(1)＋...Ｑ0,k*Ｂn(0)+n(1)+...n(k-1)
ｎ（ｊ）はＱ0,jを表わすために使用される基数Ｂのナンバリングシステムのディジットの数である。
【００１７】
第１係数Ｙ1によるＱ0の除数は、以下の擬似符号で表わされるように、それぞれのＱ0,jをＹ1で連続して割ることによりなされることができる。
Ｒ1,k+1=0
For（j=k;j≧0;j--）
{Ｑ1,j=floor((Ｑ0,j+Ｒ1,j+1*Ｂn(j))/Ｙ1)
Ｒ1,j=Ｑ0,j−Ｑ1,j*Ｙ1}
floor()関数はその引き数より小さいか又は等しい最大整数として定義される。この除法の結果は、以下のような、商及び剰余である。
Ｑ1＝Ｑ1,0＋Ｑ1,1*Ｂn(0)＋Ｑ1,2*Ｂn(0)+n(1)＋...Ｑ1,k*Ｂn(0)+n(1)+...n(k-1)
Ｒ1=Ｒ1,0
残りの係数Ｙiは同様の方法で除法可能である。
Ｒi,k+1=0
For（j=k;j≧0;j--）
{Ｑi,j=floor((Ｑi-1,j+Ｒi,j+1*Ｂn(j))/Ｙi)
Ｒi,j=Ｑi-1,j−Ｑi,j*Ｙi}
それから、最後の商及び剰余は、
Ｑi＝Ｑi,0＋Ｑi,1*Ｂn(0)＋Ｑi,2*Ｂn(0)+n(1)＋...Ｑi,k*Ｂn(0)+n(1)+...n(k-1)
Ｒi=Ｒi,0
として表わされる。
【００１８】
Zhangはまた、商が単一の伝統的な除法操作において処理されるのに十分小さい時はいつでも長除法ループ（又は、彼はそれを「ショートワード除法」と呼んでいる）が省かれることを提案している。
【００１９】
Ｑ0＝９３３，Ｙ1＝５，Ｙ2＝６，Ｙ3＝７，Ｙ4＝８の以前の例に戻り、以下の制約が存在し、伝統的な除法操作のため、商は２ディジットに制限され、除数は１ディジットに制限されると仮定する。上記仮定により制約されるZhangのＭＭＣ処理のステップは、次のとおりである。第１に、Ｑ0，９３３は（９*１００）＋（３*１０）＋３として表わされる。その後、長除法は第１係数５により入力を割るために使用される。
ａ．９を５で割り、１の商、及び４の剰余を与える。
ｂ．次に、４*１０が３に加えられ、４３を与える。
ｃ．４３を５で割り、８の商、剰余３を与える。
ｄ．次に、３*１０が３に加えられ、３３を与える
ｅ．３３を５で割り、商６、剰余３を与える。
ｆ．その後、新しい商が、商（１*１００）＋（８*１０）＋６＝１８６から形成される。
ｇ．最後の剰余は３となる。
これは、９３３／５の真の商及び剰余であり、それは１８６で、剰余３である。
【００２０】
次に、長除法は第２係数６により新しい商を割るために使用される。商１８６は（１*１００）＋（８*１０）＋（６*１）として表わされる。
ａ．最初に、１が６により割られ、０の商、１の剰余を与える。
ｂ．次に、１*１０が８に加えられ、１８を与える。
ｃ．１８を６で割り、３の商、剰余０を与える。
ｄ．次に、０*１０が６に加えられ、６を与える
ｅ．６を６で割り、１の商、剰余０を与える。
ｆ．新しい商が形成され、（０*１００）＋（３*１０）＋１＝３１となる。
ｇ．最後の剰余は０となる。
これは、１８６／６の真の商及び剰余であり、それは３１で、剰余０である。
【００２１】
最後の商の３１はたった２ディジットを有するだけであるから、伝統的な剰余は第３係数、７によりその商を割るために使用可能である。３１を７で割ると、４の商、剰余３を与える。
【００２２】
同様に、最後の商の４はたった１ディジットを有するだけであるから、伝統的な剰余は第４係数、８によりそれを割るために使用可能である。商４を８で割ることにより、最終的に計算された商は０で剰余は４となる。
【００２３】
この伝統的な方法では、その処理は長除法の手順を行う前に新しい商を検査する。結果としての商が閾値以下の場合には、それは伝統的な除法を行う。これは後の除法のため幾つかの除法命令を省く。しかし、検査により、その処理にさらなる処理サイクルが加えられる。
【００２４】
最後の剰余はＭＭＣの出力であるが、それぞれ３，０，３及び４である。Zhangの方法はこれの例のための正確な答えとなる。
【００２５】
Ｖ.９０及びＶ.９２の両方の提案で特定されているようにＭＭＣパラメータを参照すると、係数の総数Ｍはまた単一データフレームで送られる符号の数を表わす。Ｖ.９０及びＶ.９２のダウンストリームの送信機にとって、Ｍ＝６である。Ｖ.９２のＰＣＭアップストリームの送信機にとって、Ｍ＝１２である。Ｖ.９０及びＶ.９２のダウンストリームの送信機にとって、Ｙiの値は、データフレームのｉ番目の位相と関連する信号点の配列に含まれる信号点の大きさの数を表わしている。Ｖ.９２のＰＣＭのアップストリームの送信機にとって、Ｙiの値は、データフレームのｉ番目の位相と関連する同等のクラスの数を表わしている。各同等のクラスは信号点の配列での１以上の関連する信号点の大きさを有している。
【００２６】
５６kbpsベースのモデムシステムのような従来システムにおいて長除法を使用することによる問題は、最終結果を得るために非常に多くの除法操作を必要とすることである。二進法の除法を実行することは、通常、システムで使用されるプロセッサにより、非常に非効率的である。特に、Ｖ.９２の提案によると、ＭＭＣ操作はサーバモデムとクライアントモデムの両方の送信操作で要求される。したがって、今、データを送信するすべての装置は、Ｖ.９２の提案に従ってＭＭＣエンコーダ操作を実行可能でなければならない。多くの除法操作を実行する複雑さはシステムのプロセッサに非常に負担を掛ける。例えば、インテル（登録商標）のぺンティアム（登録商標）プロセッサでは、３２ビットの整数の除法は操作を行うためにプロセッサによる４６サイクルを必要とする。浮動小数点式の除法は操作を行うためにペンティアム（登録商標）プロセッサによる３９サイクルを必要とする。これは、そのようなプロセッサでのデータビットで実行可能な他の数学的操作と鮮明に対照的である。
【００２７】
【発明が解決しようとする課題】
そのため、モデムシステムデザイン技術において、多係数変換計算をより有効に行うための装置及び方法を開発する必要がある。
【００２８】
【課題を解決するための手段】
除法操作をほとんど又はまったく使用しない多係数変換（ＭＭＣ）出力の計算を可能にする所定の通信信号パラメータで情報ビットのフレームを写像するように構成された手段を有する通信システムでの使用のための方法及び装置が供給される。その発明は、複数の部分商としての入力の表示、部分商の少なくとも１つに被乗数を掛ける乗法操作の実行及び被乗数と関連する指標値の決定を可能にし、その指標値は逆係数乗法操作に応答する。伝統的な方法とは異なり、煩わしい除法操作を使用する代わりに、乗法及び論理シフト操作が使用され、擬似の商及び擬似の剰余を作り、それは最終段階で修正され、正確なＭＭＣ出力を作る。除法は、通常、乗法及び論理シフトより効率的でないから、これはより有効な実施を可能にする。その方法及び装置はＭＭＣ入力で作動し、ナンバリングシステムでディジットの数を変える部分商に分割される。
【００２９】
【発明の実施の形態】
簡単に言えば、本発明は、逆係数乗法の新しい方法を使用し、多係数変換を行うための装置及び方法を供給する。数による除法はその数の逆数による乗法と等価であることは数学において周知事実である。しかし、ＭＭＣ操作を実行する実際のシステムは、常に、有限の精度に限定され、通常、使用されるすべての係数の正確な逆数を表わすことができない。そのため、一般的に、直接の乗法操作を使用して正確な商及び剰余を得ることはできない。本発明は、各乗法操作後に修正を必要とすることなく、最後の剰余の誤りを修正する方法を供給する。本発明はモデム通信環境における手段に関して後述される。しかし、本発明は、より広範な適用を有することを意図し、それに説明された実施例に限定されず、本発明の範囲は特許請求の範囲及びそれらの均等物により定義される。
【００３０】
本発明は、複数のディジットを有するデータ入力として表わされる整数を受け取ることを含んでいる。その後、ディジットは複数の部分商として表わされる。少なくとも１つの被乗数が得られ、それは係数値の予想逆数に関連している。上述したように、通常、係数は正の整数２である。逆係数は有限の精度で計算され、それは係数の真の逆数に正確に等しくはない。次に、逆係数乗法は逆係数に個々の部分商を掛けることにより行われる。この段階は、係数と関連した「擬似の剰余」を発生させる。擬似の剰余Ｒ’は、入力された商Ｑi、出力された「擬似の商」Ｑ0’及び係数Ｙとの間の以下の関係により定義される。
Ｑi＝Ｑ0’*Ｙ＋Ｒ’
これは、真の剰余が範囲［０，Ｙ）にあることを要求される以外、剰余操作の真の出力された商と真の剰余の間の関係と類似しているが、擬似の剰余はそうではない。逆係数の概算において起こり得る誤りのため、擬似の剰余はこの範囲外であってもよい。そのため、さらなる段階は擬似の剰余を検査するために使用されてもよく、それが有効範囲外となった場合にはそれを調整する。上述したように、乗法操作の幾つかだけがこの検査を要求する。この検査を有しなければならない乗法操作は最も重要でない部分商に相当するものである。他の乗法操作は検査を有していても、又は有していなくてもよい。装置は、ＭＭＣ計算のための係数及び又は逆係数へのアクセスのため、複数の係数を格納するための記憶装置を有していてもよい。装置はさらに、複数の部分商としてデータディジットを表わし、逆係数乗法の方法を行うように構成されたデータプロセッサを有している。
【００３１】
上述したように、伝統的な装置及び方法では、ＭＭＣアルゴリズムは除法操作がそれぞれの係数のためになされることを要求し、それぞれの係数のための商及び剰余となる。本発明によれば、方法及び装置は一連の逆係数乗法を行うことにより除法操作を不要にするために供給される。これらの乗法操作は除法操作より実質的に短い処理時間を要求し、したがって、ＭＭＣ計算操作の効率を非常に改善する。
【００３２】
一般的に、乗法は剰余よりＤＳＰにおいてもっと有効である。例えば、実際に、本発明を使用するＤＳＰによる乗法は２個の１６ビットの数を掛けるために単一サイクルと同じ程度少ないサイクルを必要とする。伝統的なＤＳＰ方法を使用する１６ビットの数の除法は被除数の各ビットのために１サイクルを必要とする。結果として、１６ビットの被除数のため少なくとも１６サイクルが要求されるだろう。インテル（登録商標）のペンティアム（登録商標）のプロセッサを使用するシステムにおいて、整数の乗法は１０サイクルだけを要求する。ＭＭＸ命令による新しいペンティアム（登録商標）プロセッサを使用すると、整数の乗法はより少ないサイクルさえ可能となる。上述したように、同じプロセッサの整数の除法は４６サイクルを必要とし、浮動小数点式の除法は３９サイクルを必要とする。これらのタイプのプラットフォームにおいて、本発明により行われるＭＭＣ計算はもっと非常に有効である。本発明により行われるＭＭＣ処理は除法操作をほとんど又はまったく必要とせず、そのため、処理時間の消費が少ない。
【００３３】
本発明の一実施例では、係数値Ｙiは装置に又はそれによりアクセス可能な記憶装置の位置に配置された表に格納されている。逆係数値は逆係数乗法を行う前毎に除法操作を使用して計算される。本発明の別の方法では、係数値Ｙiは第１の表に格納され、逆係数は除法操作を使用する通信セッションの始めに計算され、逆係数はその通信セッションを通しての使用のため第２の表に格納される。本発明のさらに別の実施例では、すべての可能な係数のための逆数の概算は予め計算され、第１の表に格納される。実行時間では、係数値Ｙiは第２の表に格納される。通信セッションの始めに、逆係数は第１の表の始めからオフセットしたＹiでの値をとることにより得られ、第３の表に格納される。その後、逆係数値はデータ入力を通信セッションを通しての指標値に変換するために使用されることができる。したがって、本発明を具体化する装置は除法操作がほとんど又はまったくないＭＭＣ変換操作を行ってもよい。
【００３４】
図１を参照すると、本発明を具体化する５６kbps通信システム１００の概略図が示されている。図は本発明によりデータ符号を送ると共に受け取るためのモデムにより構成された２個の装置間のデータパスを示している。インターネットサービスプロバイダ（ＩＳＰ）１０２により操作されるようなサーバ機器は、サーバモデムとして当技術において公知なＩＳＰモデム１０４を介して通信システム内で通信する。ＩＳＰモデムはシステムを通ってデータフレームを受信装置に送るための送信回路（Ｔｘ）１０６を含んでいる。ＴｘはＭＭＣエンコーダ回路１０８を含み、本発明による逆係数乗法でＭＭＣ操作を行う。ＩＳＰモデムはさらに、他の送信装置からデータフレームを受け取るように構成された受信回路（Ｒｘ）１１０を含んでいる。Ｒｘ回路はＩＳＰのために予定されたデータフレームの送信を復号するように構成されたＭＭＣデコーダ回路１１０を含んでいる。
【００３５】
ＩＳＰはＩＳＰモデム１０４を介して公衆切替電話網（ＰＳＴＮ）にデジタル方式で接続されている。ＰＳＴＮは、パルス符号変調（ＰＣＭ）信号を処理するためのＣＯＤＥＣ１１８を通常有する電話局１１６を介して通信する。これらの信号は、自局ループを介してクライアントモデム１２０のようなＰＳＴＮと通信する装置に送信されると共にそのような装置から受信される。クライアントモデムは、通常、パーソナルコンピュータ、ラップトップ、パーソナルデータデバイス（ＰＤＡ）、又はＰＳＴＮと通信するように構成された他の装置に収容されたアナログモデムである。クライアントモデムはラインカード１１６を介してＰＳＴＮ１１４間で通信を送受信するための自局ループと通信するインターフェース１２２を含んでいる。インターフェースはクライアントモデムの受信回路（Ｒｘ）１２４への受信信号の経路を定めるように構成されている。受信機回路は入ってくるデータフレームを復号するように構成されたＭＭＣデコーダ回路１２６を含んでいる。インターフェースはまた送信回路１２８から出て行く信号の経路を定め、それはＭＭＣエンコーダ１３０を含んでいる。本発明によると、ＭＭＣエンコーダは、ＩＳＰモデムのＭＭＣエンコーダ１０８のように、ＭＭＣ操作を行うように構成されている。Ｒｘ回路とＴｘ回路の両方ともプロセッサ１３２と通信する。プロセッサはモデムカードの一部として統合され、クライアントモデムにより受信されたデータを処理するように構成されたＤＳＰであってもよい。
【００３６】
図１に示されたシステムがＶ.９２の提案のＰＣＭアップストリームモードに適用可能であることは、当業者により認識されるだろう。上述したように、Ｖ.９０の提案はサーバモデムがマッピングするアルゴリズムのためＭＭＣエンコーダ操作を行うことができるだけであることを要求する。Ｖ.９２のＰＣＭアップストリームモードはクライアント及びサーバモデムの両方がＭＭＣエンコーダ操作を実行可能であることを要求する。本発明により処理されるＭＭＣ操作はサーバモデム又はクライアントモデムのいずれかにおいて利用されてもよい。
【００３７】
図２を参照すると、ＭＭＣエンコーダ１０８を組み込んだモデムエンコーダ２００のより詳細な概略図が示されている。この特別の例はＶ.９０／Ｖ.９２のダウンストリームの送信のために使用されるエンコーダの後に作られている。データＤ0：Ｄd-1はデータスクランブラー２０２からビットパーサー２０４に送信される。ビットパーサーはスクランブルされたビットＢ0：Ｂk-1を係数エンコーダ２０６及びビットＳ0：Ｓs-1をスペクトル整形回路２０８に送る。
【００３８】
本発明はＭＭＣ変換処理に導かれ、それはスペクトル整形回路２０８で生じた値に依存せず、それがＶ.９０か、Ｖ.９２か、又は他の将来の提案か、どの標準が使用されるかによりアップストリーム又はダウンストリーム送信のいずれかのためのデータフレームの発生において起きてもよい。したがって、本発明は特定の標準の構成に限定されず、かなり多くの構成及び適用に適用されてもよい。この例では、ＭＭＣエンコーダは送信されるすべてのビットで動作するのではない。本発明は、ＭＭＣエンコーダが送信されるすべてのビットで動作しない他のものと同様に、この状態の方に導かれてもよい。
【００３９】
符号化回路は逆係数値を格納するように構成された逆係数記憶装置２１０をさらに有している。逆係数値は係数値から得られる。これらの係数値はＩＳＰモデムとクライアントモデムの間の適用できる初期設定処理の間に決定されてもよい。したがって、係数と関連する配列のための信号パラメータはまた初期化の間に確立されてもよい。係数値が選択される方法は複数の要因による。例えば、係数値の数は適用により変わってもよい。Ｖ.９０及びＶ.９２の提案において、例えば、６個の係数から生じた６ＰＣＭはダウンストリーム送信のための各データフレームのために要求される。しかし、Ｖ.９０とは異なり、Ｖ.９２はアップストリーム送信のためのＭＭＣ変換を必要とし、各データフレームは１２ＰＣＭ符号からなり、そのため、１２個の係数が要求される。本発明は特定数の係数又は特定の係数値に限定されるものではない。
【００４０】
本発明を具体化する一実施手段では、各係数は逆数に変換される。したがって、Ｙiによる各剰余は１／Ｙiの概算により乗法操作に変形される。この値はデータ符号を指標値にエンコードするために使用される。好適な実施例では、入力された整数Ｑ0は基数ＢのナンバシステムにおいてＮiディジットに限定され、入力された係数Ｙiは前記ナンバシステムにおいてＮ2にすべて限定され、逆係数は前記ナンバシステムにおいてＮ3にすべて限定される。典型的に、Ｎ3はＭＭＣに責任を有する装置が１つの操作で処理可能なディジットの最大数である。前述したように、Ｑ0は、通常、この最大値より大きいディジットを有し、Ｎ1はＮ3より大きい。また、好適な実施例では、Ｎ3はＮ2より大きくすべきである。
【００４１】
基数ＢのナンバリングシステムでのＮ3ディジット表示に逆数の概算を制限するため、１／Ｙiの概算は以下のフロア（floor）関数により計算される。
Ｃi＝floor（ＢN3／Ｙi）
結果としての値ＣiはＮ3ディジットを有し、固定小数点の右側にすべてのディジットを有する固定小数点として解釈可能である。この計算はＹi．２の場合にのみ適用されることに注意しなさい。Ｙi＝１の値が許容される場合、それは２つの方法の１つにより処理可能である。第１の方法では、ＣiはＢN3−１に設定され、逆係数乗法の方法が直接使用される。第２の方法では、逆係数乗法の方法はＹi＝１のために省かれ、Ｑi及びＲiの値はＱi＝Ｑi-1及びＲi＝０に設定される。
【００４２】
さらに、図２を参照すると、本発明により、作用では係数値を確立すると共に逆係数値と対応することにより、係数エンコーダ２０６は逆係数記憶装置２１０に格納されたルックアップ表を要求してもよい。逆係数値は、その後、整数を表わす符号の指標値への変換のために検索されてもよい。これらの指標値のそれぞれは、その後、ポイントマップ回路２１８に送られ、それぞれの指標値は一群のポイントマップ２２０〜２２６を割り当てられる。その後、これらの指標値は、クライアントモデムのような受信装置にＰＳＴＮを介して送られることができる。システムは、適用により、かなり多数の指標値を発生してもよい。Ｖ.９０及びＶ.９２では、６個までの指標値がＩＳＰから作られると共に送られる。その後、指標値はサイン割当回路２２８に送られ、指標値の極性を確立する。割当回路はＰＣＭi符号をマルチプレクサー２３０に出力し、それはクライアントモデムへの送信ため連続的方法でＰＣＭオクテットの符号を出力する。
【００４３】
図２に示された構成はサーバモデムのために設計された回路の例であることは、当業者により理解されるだろう。Ｖ.９０及びＶ.９２の提案により、そのようなサーバモデムはスペクトル整形機能及びサーバモデムの特徴に特定の他の特徴を行うために必要とされる。しかし、ＭＭＣ処理は、上述したようなＭＭＣ処理を使用して写像された符号を送信するためクライアントモデムに同様に適用される。作動において、そのようなクライアントモデムはＩＳＰモデムの係数エンコーダ２０６と同様の係数エンコーダを含み、本発明による新しい逆係数乗法の方法を含むＭＭＣ操作を行うだろう。
【００４４】
図３を参照すると、本発明により構成されたＭＭＣ変換処理３００が示されている。第１に、最初のＭＭＣパラメータはステップ３０２で得られる。そのようなパラメータは、ＭＭＣのフレーム当りのビット数、部分商のすべて又はほとんど最も重要な部分商のいずれかのためのビット長、ビットの分割で利用されるセグメントの数、係数又は逆係数の数Ｍ、及び実際の係数Ｙi、又は逆係数Ｃiの値を含んでいてもよい。ステップ３０４において係数エンコーダはデータビットＱ0の入力を得、係数の指標カウンターｉを初期化する。次のステップ３０６では、データビットの入力値は多数又は複数の部分商として表示される。部分商の総数はｋ＋１である。データビットを部分商に割る操作はビットマスキングルーチンを実行することにより行われてもよく、例えば、所定数の記憶位置にデータビットの部分を割り当てる。操作はまたＱi-1と関連する記憶位置に簡単にアクセスし、所定長の部分商を得る。これらの部分商は等しい長さであってもよく、そうでなくてもよい。好適な実施例では、ほとんど最も重要な部分商は等しい長さである。一般的に、部分商Ｑ0,iに対する入力された商Ｑ0の関係は次の通りである。Ｑ0＝Ｑ0,0＋Ｑ0,1*Ｂn(0)＋...＋Ｑ0,k*Ｂn(0)+n(1)+...n(k-1)、ｎ（ｊ）はｊ番目の部分商のディジットの数を表わしている。現在の係数値及び逆係数値はステップ３０８で得られる。逆係数はステップ３０８において、記憶装置に記憶されたルックアップ表から得られてもよく、又は、他の手段により得られた係数値から得たり、計算されたり、又はそうでなく発生したりしてもよい。現在の商Ｑi-1は、その後、ステップ３１０において、この発明の逆係数乗法の方法を使用して、逆係数値を掛けられる。新しい商Ｑi及び剰余Ｒiはこの操作から得られる。剰余はＭＭＣ処理の出力の１つである。ステップ３１２において、係数の指標カウンターｉが増やされる。ステップ３１４において、最後の係数値が入力データを変換するために使用されるかどうかの質問が提起される。それが使用されない場合には、出力された商は、その後、ステップ３０６に戻され、次の連続的な係数値と関連し、処理が繰り返される。最後の係数値が処理された場合、その後、処理はステップ３１６に進み、最後の剰余値が出力され、それは図２の係数エンコーダ２０６により出力されたＲMによるＲ1の値である。その後、処理はステップ３０４に戻り、次の入力が得られる。
【００４５】
図４を参照すると、本発明による逆係数乗法処理４００を擬似符号で示すフロー図が示されている。示された処理は図３のステップ３１０と同様である。ステップ４０２において、ｋ＋１の部分商として表わされる商Ｑi-1、係数Ｙi、及び逆係数の概算値Ｃiが得られる。Ｃiの値は上述したフロア関数により定義される。逆係数乗法処理では、それぞれの部分商は、上述したように、擬似の剰余及び擬似の商と関連している。以下の説明の簡略化のため、真の剰余と擬似の剰余、又は真の商と擬似の商との間に区別がなされていない。一般的に、検査が行われず、必要なように値が修正されない場合、処理のすべての中間のＲi,j及びＱi,jの値は擬似の剰余及び擬似の商である。最初に入力された商は剰余がないから、擬似の剰余の初期値はステップ４０４において０に設定される。ステップ４０６では、部分商の指標ｊはｋに初期化され、それはステップ４０２で受け取った部分商の総数より小さい。その後、その処理はステップ４０８，４１０，４１２及び４１４を含むループに進み、出力された擬似の商Ｑiを表わす部分商は逆係数乗法操作から得られる。ステップ４０８では、出力された擬似の商Ｑiのｊ番目の部分商が得られる。最初、以前の部分商の操作Ｒi,j+1の擬似の剰余は最初のｊ番目の部分商の長さｎ（ｊ）の累乗にＢの基数ナンバシステムにより掛けられる。その結果は入力された商のｊ番目の部分商Ｑi-1,jに加えられる。その後、この加算の結果は逆係数の概算値Ｃiにより掛けられる。最後に、この乗法の結果は、「＞＞」演算子により示されているように、Ｎ3の基数Ｂディジットにより右に論理的にシフトされる。その結果は有効に切り捨てられ、商の整数部分だけが残されるようになっている。通常の実施では、この切捨ては論理シフト操作に固有である。ステップ４１０では、ｊ番目の部分商の逆係数乗法操作の擬似の剰余が得られる。最初、出力された擬似の商のｊ番目の部分商Ｑi,jは係数値Ｙiにより掛けられる。その結果は、入力された商のｊ番目の部分商Ｑi-1,jと前の部分商の操作の擬似の剰余の積Ｒi,j+1とｎ（ｊ）の累乗のＢの合計から引かれる。ステップ４１２では、ｊの値はそれが０であるかどうかを調べるために質問される。そうでなければ、処理はステップ４１４で続き、ｊが減少される。ｊを減少させた後、処理はステップ４０８に進み、次の部分商を処理する。ステップ４１２において、ｊが０に等しい場合、処理はステップ４１６に進む。逆係数の概算値Ｃiの不正確さのため、最終的な部分商の擬似の剰余Ｒi,0はＹiより大きいか又はそれに等しくてもよい。前述したように、ＭＭＣは剰余がＹiより小さいことを厳密に要求する。ステップ４１６において、Ｒi,0の値はそれがＹiより小さいかどうかに関して質問される。小さくない場合には、その後、処理はステップ４１８に進む。ステップ４１８では、最終的な擬似の剰余が係数値Ｙiをそれから引くことにより修正される。擬似の商Ｑi,0の最後の部分商はまた、それに１を加えることにより修正される。一度、ステップ４１６での質問を通過するか又はステップ４１８での修正後のいずれかにおいて、真の剰余及び真の商が得られると、処理はステップ４２０で続く。ステップ４２０において、最終的な部分商のための真の剰余が出力された剰余Ｒiに写される。次に、ステップ４２２において、部分商により表わされた、出力された剰余及び出力された商は処理４００により戻される。
【００４６】
逆係数乗法処理を正確に作動させるため、一定の制約は部分商の長さ、係数の値、及び逆係数の概算の正確さに関連して満たされなければならない。これらの制約の幾つかはアルゴリズムに固有であり、他はシステムに依存している。主なアルゴリズムの制約は、ステップ４１８の修正前にｊ＝０の時にステップ４１０で得られる最終的な擬似の剰余が範囲０  Ｒi,0＜２*Ｙiとなるという仮定から生じる。それはこの条件を満たすためには以下の不等式を満たすことで十分であることを示している。
Ｎ3＞Ｎ2＋ｎ（ｊ）
その条件を言葉で説明するため、逆係数の概算値で使用されるディジットの数は最大の係数のディジット数と最長の部分商のディジット数の合計より多くなければならない。この規則には注目すべき幾つかの例外がある。第１に、その規則は最初の（最上位の）部分商Ｑi,kの長さｎ（ｋ）に適用されない。これはＲi,k+1＝０だからである。この場合には、アルゴリズムの制約は次のように示されることができる。
ｎ（ｋ）  Ｎ3
アルゴリズムの制約の別の例外は、Ｙi＝ＢN2の場合である。ＹiはＮ2ディジットより有しているが、逆係数の概算誤りは、Ｎ2  Ｎ3である限り０である。アルゴリズムの制約から計算されたＮ2は、通常、例外の場合を考慮に入れて、Ｙi＜ＢN2であること意味し、真の制約はＹi  ＢN2である。
【００４７】
アルゴリズムの制約が破られた時、擬似の剰余Ｒi,jはもはや範囲［0,2*Ｙi)になることを保証することができない。そのため、図４のステップ４１６で行われるように、範囲検査は複数回行われる必要がある。擬似の剰余が大きくなると、図４のステップ４０８で計算された部分商Ｑi,jはまた大きくなり、実質的に、中間の部分商を記憶するためには入力された部分商を記憶するために要求されるより多くのディジットが要求されてもよい。通常、これは、入力された部分商のディジットｎ（ｊ）の数が上述されたアルゴリズムの制約が使用される場合より少なくなければならないことを意味する。小さい部分商の使用は、通常、所定の入力を表わすためにより多くの部分商が必要とされる（すなわち、ｋはもっと大きくなければならない）ことを意味するから、これは要求される計算数を増加してもよい。逆係数の概算Ｃiを記憶するために使用されるディジットＮ3の数と、逆係数乗法処理を行うために要求される計算数との間に交換条件がある。上述したアルゴリズムの制約を破らないためにそれが意味をなす実際のシステムでは、本発明の小さな変化がＭＭＣ出力を得るために使用されてもよい。この変化は、図４のステップ４１８でのように、擬似の剰余Ｒi,0が範囲［0,Ｙi）となるまで、連続的に範囲検査を実行することから成る。この変形では、ステップ４１８からステップ４２０への矢印が取り除かれ、ステップ４１８からステップ４１６への矢印が追加される。
【００４８】
実際のシステムでは、Ｎ2，Ｎ3，及びｎ（ｊ）の値はそれらにより課せられた他の追加の制約を有していてもよい。例えば、多くのＤＳＰシステムでは、乗法操作への入力は１６ビットに制限される。このタイプのシステムでは、制約Ｎ3１６は、アルゴリズムが各部分商のため単一の乗法操作により実施された場合には維持されるだろう。他のシステムでは、乗法操作への入力とその積の両方が３２ビットに制限される。そのようなシステムでは、制約Ｎ3＋ｎ（ｊ）３２は維持される。
【００４９】
Ｑ0＝９３３，Ｙ1＝５，Ｙ2＝６，Ｙ3＝７，そしてＹ4＝８の以前の例に戻ると、伝統的な乗法操作のために以下の制約がある、すなわち、入力が３の十進法ディジットに制限され、積が５の十進法ディジットに制限される以下の制約があると仮定する。係数のために使用される十進法ディジットの最大値は１であるから、Ｎ2＝１である。乗法入力ディジットの最大数は逆係数の概算のために使用可能であるから、Ｎ3＝３である。アルゴリズムの制約を満たすため、ｊ＝０からｋ−１のためにｎ（ｊ）＝１が選択される。
【００５０】
ｎ（ｋ）はこの制約により制限されないが、それは依然として５ディジットの積の制約より制限される。そのため、ｎ（ｋ）＝１も選択されなければならない。逆係数１／５，１／６，１／７，及１／８の概算は、公式Ｃi＝floor（ＢN3／Ｙi）を使用して予め計算されてもよく、Ｂ＝１０，Ｎ3＝３，そしてＹi＝｛５，６，７，８｝である。結果として生じる値はＣi＝｛２００，１６６，１４２，１２５｝である。本発明の一実施例では、結果として生じる逆係数の概算値は係数エンコーダ２０６（図２）による容易なルックアップ表へのアクセスのため表に記憶され、指標値を発生させる。
【００５１】
上述した伝統的な方法との対照のため、Ｑ0＝９３３の値は本発明によるＭＭＣ変換処理を使用して変換される。最初、９３３は(９*１００)＋(３*１０)＋３として表わされる。
【００５２】
次に、Ｑ0の値は第１の係数Ｙ1＝５により有効に割られる。逆係数の概算値はＣ1＝２００となるように計算された。本発明により、最初のＭＭＣ値は、以下の通り、除法操作を使用することなく、発生させることができる。
ａ．最初、９に２００を掛け、１８００を与え、本発明により、Ｎ3＝３ディジット分シフトされ、切り捨てられ、１の擬似の商を与える。擬似の剰余は４と計算される。
ｂ．次に、４*１０が３に加えられ、４３を与える。
ｃ．４３に２００を掛け、８６００を与え、本発明により、Ｎ3＝３ディジット分シフトされ、切り捨てられ、８の擬似の商を与える。擬似の剰余は３と計算される。
ｄ．次に、３*１０が３に加えられ、３３を与える。
ｅ．３３に２００を掛け、６６００を与え、本発明により、Ｎ3＝３ディジット分シフトされ、切り捨てられ、６の擬似の商を与える。擬似の剰余は３と計算される。これは誤り検査前の最終剰余である。
ｆ．次に、本発明により、誤り検査は最終の擬似の剰余が第１の係数の５より大きいか又は等しいかどうか、或いは３≧５かどうかを決定するために行われる。これは問題ではなく、調整の必要はない。
ｇ．最後に、新しい商が形成され、(１*１００)＋(８*１０)＋６＝１８６となる。
ｈ．最終的な剰余は３となる。
【００５３】
次に、逆係数乗法の方法が使用され、新しい商を第２の係数Ｙ2＝６により有効に割る。逆係数の概算値はＣ2＝１６６となるように計算された。
ａ．１に１６６を掛け、１６６を与え、本発明により、Ｎ3＝３ディジット分シフトされ、切り捨てられ、０の擬似の商を与える。擬似の剰余は１と計算される。
ｂ．次に、１*１０が８に加えられ、１８を与える。
ｃ．１８に１６６を掛け、２９８８を与え、本発明により、Ｎ3＝３ディジット分シフトされ、切り捨てられ、２の擬似の商を与える。擬似の剰余は６と計算される。
ｄ．次に、６*１０が６に加えられ、６６を与える。
ｅ．６６に１６６を掛け、１０９５６を与え、本発明により、Ｎ3＝３ディジット分シフトされ、切り捨てられ、１０の擬似の商を与える。擬似の剰余は６と計算される。これは最終検査前の最終の擬似の剰余である。
ｆ．最後に、本発明により、最終の擬似の剰余が６より大きいか又は等しいかどうか、或いは６≧６かどうかを決定するための検査がある。この場合には、答えはイエスであり、擬似の商と擬似の剰余の両方が調整されなければならない。この場合、擬似の剰余６が６に等しいから、その方法は擬似の商に１を加え、擬似の剰余から６を引き、商が１１、剰余が０となる。
ｇ．その後、新しい商が形成され、(０*１００)＋(２*１０)＋１１＝３１となる。
ｈ．最終的な剰余は０となる。
【００５４】
次に、逆係数乗法の方法が使用され、新しい商３１を第３の係数Ｙ3＝７により有効に割る。逆係数の概算値はＣ3＝１４２となるように計算された。
ａ．０に１４２を掛け、０を与え、本発明により、Ｎ3＝３ディジット分シフトされ、切り捨てられ、０の擬似の商を与える。擬似の剰余は０と計算される。
ｂ．次に、０*１０が２に加えられ、２を与える。
ｃ．２に１４２を掛け、２８４を与え、本発明により、Ｎ3＝３ディジット分シフトされ、切り捨てられ、０の擬似の商を与える。擬似の剰余は２と計算される。
ｄ．次に、２*１０が１１に加えられ、３１を与える。
ｅ．３１に１４２を掛け、４４０２を与え、本発明により、Ｎ3＝３ディジット分シフトされ、切り捨てられ、４の擬似の商を与える。擬似の剰余は３と計算される。
ｆ．次に、最終の擬似の剰余はそれが最初の係数値の６より大きいか又は等しいかどうか、或いは３≧６かどうかを決定するために検査される。これは問題ではなく、調整の必要はない。
ｇ．最後に、新しい商が形成され、(０*１００)＋(０*１０)＋４＝４となる。
ｈ．最終的な剰余は３となる。
【００５５】
最後に、逆係数乗法の方法が使用され、新しい商を第４及び最終の係数Ｙ4＝８により有効に割る。逆係数の概算値はＣ4＝１２５となるように計算された。
ａ．０に１２５を掛け、０を与え、本発明により、Ｎ3＝３ディジット分シフトされ、切り捨てられ、０の擬似の商を与える。擬似の剰余は０と計算される。
ｂ．次に、０*１０が０に加えられ、０を与える。
ｃ．０に１２５を掛け、０を与え、本発明により、Ｎ3＝３ディジット分シフトされ、切り捨てられ、０の擬似の商を与える。擬似の剰余は０と計算される。
ｄ．次に、０*１０が４に加えられ、４を与える。
ｅ．４に１２５を掛け、５００を与え、本発明により、Ｎ3＝３ディジット分シフトされ、切り捨てられ、０の擬似の商を与える。擬似の剰余は４と計算される。
ｆ．上記のように、その方法は、最終の擬似の剰余が最初の係数値の６より大きいか又は等しいかどうか、或いは４≧６かどうかを検査する。これは問題ではなく、調整の必要はない。
ｇ．最終的な剰余は４となる。
【００５６】
最終的な出力はそれぞれ３，０，３及び４である。そのため、逆係数乗法の方法は、以前の例で計算されたように、正確なＭＭＣ値となる。Ｑ4＝０であることが予め知られているので、Ｙ4に対応する逆係数乗法は省略可能であることに注意しなさい。
【００５７】
今、ＩＴＵ−Ｔ提案のＶ.９２で定義されたようなＭＭＣの例を考え、乗法が１６ビットの被演算子で作動する二進法プロセッサを使用して実行され、３２ビットの結果を作る。簡略化のため、それは、
n(0)=n(1)=...=n(k-1)=Ｎ3-Ｎ2-１、及びn(k)=Ｎ3
と仮定される。Ｎ3-Ｎ2-１は前述したアルゴリズムの制約Ｎ3＞Ｎ2＋n(j)の下でのn(j)のための最大値である。
【００５８】
Ｖ.９２では、最大可能な係数は１２８であり、１２の係数がある。しかし、最大データレートは４８kbpsである。ＭＭＣは秒当り８０００／１２のレートでなされ、最大入力長は４８０００*１２／８０００＝７２ビットである。これは以下を与える。
Ｂ＝２
Ｎ1＝７２
Ｎ2＝７（Ｙi＝１２８の特別な８ビットの場合を可能にする）
Ｎ3＝１６
n(j)のための値が得られる。
n(0),n(1),...n(k-1)＝８
n(k)＝１６
７２ビットの入力を処理するため、ｋ＝８となる。
【００５９】
上記システムの機能を示すため、以下のパラメータによる通信セッションが供給される。
Ｙ1=0x3Ｃ,Ｙ2=0x3Ｄ,Ｙ3=0x3Ｅ,Ｙ4=0x3Ｆ,Ｙ5=0x40,Ｙ6=0x41,
Ｙ7=0x42,Ｙ8=0x43,Ｙ9=0x44,Ｙ10=0x45,Ｙ11=0x46,Ｙ12=0x47；
及び７２ビット入力Ｑ0=0x123456789ＡＢＣＢＡ9876であり、“0ｘ”は１６進法表記を示している。当業者は１６進法表記が２進法の数の略記として使用されることがよくあることを認識しているだろう。Ｑ0＜Ｙ1Ｙ2...Ｙ12であるから、Ｙ12に対応する逆係数乗法は省略可能である。１６ビットの逆係数の概算値Ｃiは、floor（２16／Ｙi）に等しい値を有し、ＭＭＣ処理の間に計算され、通信セッションの始めに計算され、又は幾つかの他の方法で得られる。所定値のＹiのため、対応するＣiの値は次の通りである。
Ｃ1=0x0444,Ｃ2=0x0432,Ｃ3=0x0421,Ｃ4=0x0410,Ｃ5=0x4000,Ｃ6=0x03Ｆ0,
Ｃ7=0x03Ｅ0,Ｃ8=0x03Ｄ2,Ｃ9=0x03Ｃ3,Ｃ10=0x03Ｂ5,Ｃ11=0x03Ａ8,Ｃ12=0x039Ｂ
本発明によるＭＭＣ操作を行うため、以下のＣ符号が使用されてもよい。
【００６０】
2005519506.tif 000003
【００６１】
第１に、Ｑ0は以下の通り、部分商として表わされる。
Ｑ0=0x1234；0x56；0x78；0x9Ａ；0xＢＣ；0xＢＡ；0x98；0x76
次に、逆係数乗法は、第１の係数、0x3ＣによりＱ0を有効に割るために使用される。この操作の結果は、上記Ｃ符合により確認可能であり、以下の通りである。Ｑ1=0x4Ｄ；0xＡＣ；0x1Ｂ；0x9Ｃ；0x2Ｄ；0xＣＦ；0xＥ8；0xＦ0
Ｒ1=0x36
このステップでは修正は不要である。
次に、逆係数乗法は、第２の係数、0x3ＤによりＱ1を有効に割るために使用される。その結果は、以下の通りである。
Ｑ2=0x01；0x45；0xＦ7；0x10Ｆ；0x26；0x85；0x81；0xＢ8
Ｒ2=0x18
このステップでは修正は不要である。
【００６２】
次に、逆係数乗法は、第３の係数、0x3ＥによりＱ2を有効に割るために使用される。その結果は、以下の通りである。
Ｑ3=0x00；0x05；0x41；0xＥＦ；0xＢＡ；0x6Ｄ；0x82；0x17
Ｒ3=0x26
このステップでは修正は不要である。
次に、逆係数乗法は、第４の係数、0x3ＦによりＱ3を有効に割るために使用される。修正前の結果は、以下の通りである。
Ｑ4,0=0x69
Ｒ4,0=0x40
Ｒ4,1  0x3Ｆであるから、修正は必要である。修正は以下の通りである。
Ｑ4,0=0x69＋１=0x6Ａ
Ｒ4,0=0x40-0x3Ｆ=0x01
【００６３】
修正後、第４の逆係数乗法の出力は以下の通りである。
Ｑ4=0x00；0x00；0x15；0x5Ｄ；0x33；0xＢ8；0x98；0x6Ａ
Ｒ4=0x01
次に、逆係数乗法は、第５の係数、0x40によりＱ4を有効に割るために使用される。その結果は、以下の通りである。
Ｑ5=0x00；0x00；0x00；0x55；0x74；0xＣＥ；0xＥ2；0x61
Ｒ5=0x2Ａ
このステップでは修正は不要である。
【００６４】
次に、逆係数乗法は、第６の係数、0x41によりＱ5を有効に割るために使用される。その結果は、以下の通りである。
Ｑ6=0x00；0x00；0x00；0x01；0x50；0x90；0xＦ7；0xＡＡ
Ｒ6=0x37
このステップでは修正は不要である。
【００６５】
次に、逆係数乗法は、第７の係数、0x42によりＱ6を有効に割るために使用される。その結果は、以下の通りである。
Ｑ7=0x00；0x00；0x00；0x00；0x05；0x19；0x77；0x11Ｄ
Ｒ7=0x30
このステップでは修正は不要である。
次に、逆係数乗法は、第８の係数、0x43によりＱ7を有効に割るために使用される。その結果は、以下の通りである。
Ｑ8=0x00；0x00；0x00；0x00；0x00；0x13；0x7Ｃ；0x0Ｆ
Ｒ8=0x30
このステップでは修正は不要である。
次に、逆係数乗法は、第９の係数、0x44によりＱ8を有効に割るために使用される。その結果は、以下の通りである。
Ｑ9=0x00；0x00；0x00；0x00；0x00；0x00；0x49；0x5Ａ
Ｒ9=0x27
このステップでは修正は不要である。
【００６６】
次に、逆係数乗法は、第１０の係数、0x45によりＱ9を有効に割るために使用される。その結果は、以下の通りである。
Ｑ10=0x00；0x00；0x00；0x00；0x00；0x00；0x01；0x10
Ｒ10=0x0Ａ
このステップでは修正は不要である。
次に、逆係数乗法は、第１１の係数、0x46によりＱ10を有効に割るために使用される。その結果は、以下の通りである。
Ｑ11=0x00；0x00；0x00；0x00；0x00；0x00；0x00；0x03
Ｒ11=0x3Ｅ
このステップでは修正は不要である。
次に、Ｑ12＝０であることは、予め知られているから、最終剰余Ｒ12は最後から２番目の商、Ｑ11に直接設定されることができる。その結果は、以下の通りである。
Ｑ12=0x00；0x00；0x00；0x00；0x00；0x00；0x00；0x00
Ｒ12=0x03
このステップでは修正は不要である。
【００６７】
図３及び４は部分商のそれぞれが各係数のために連続的に処理される逆係数乗法操作を説明しているが、手順はまた次の部分商に進む前に各部分商が各係数により連続的に処理されるように配列されてもよい。いずれの場合も、部分商に対応する擬似の剰余だけが修正される必要がある、以下のＣ符号は逆係数乗法の方法のこの変形を示している。
【００６８】
2005519506.tif 000004
【００６９】
上述した逆係数乗法の手順では、その手順の間、最下位の部分商のための擬似の剰余が検査され、必要な場合には擬似の剰余及び擬似の商が変更される。別の変形では、逆係数乗法の手順は検査なしで行われ、Ｍ個の擬似の剰余を作る。手順の終わりには、その後、すべての擬似の剰余が検査される。この点では、それらはその手順の次のステップですでに使用されているから、擬似の商を更新するには遅すぎる。事実、擬似の剰余がＹiにより減少されるときはいつでも、次の擬似の剰余は１、増加される。上述したアルゴリズムの制約が次に来た場合、その後、擬似の剰余は検査前に範囲［0,2*Ｙi）にある。検査は再度擬似の剰余を増加させる結果となるから、範囲は拡大される。そのため、検査は擬似の剰余が範囲［0,Ｙi）に入るまで連続的に行われるべきである。以下のＣ符号は、本発明のこの変形を示し、以前使用されているものと同一の入力及び係数を使用している。
【００７０】
2005519506.tif 000005
【００７１】
逆係数乗法の方法はフロア（）関数を使用して表わされ、逆数の概算を計算するが、当業者は他の概算技術が使用可能であることを認識するだろう。例えば、以下の公式が使用可能である。
Ｃi＝ceil(ＢN3/Ｙi)
ceil()関数は引き数より大きいか又は等しい最小の整数として定義される。この場合、擬似の剰余は負となることができ、修正ステップは、
if(Ｒi,0＜０)
{Ｒi,0＝Ｒi,0＋Ｙi
Ｑi,0＝Ｑi,0−１}
別の可能な逆数の概算技術は丸め関数を使用する。
Ｃi＝rnd(ＢN3/Ｙi)
rnd()関数は引き数に最も近い整数として定義される。この場合、擬似の剰余の修正技術は、最も近い整数がその引き数より大きいか又は小さいかに基づいて変化する。これは、前述した両方の検査を毎回行い、実行時間で行う検査をどれにするかを決定し、又は各逆係数のために行う検査をどれにするかを予め決定することにより処理可能である。
【００７２】
本発明は逆係数乗法の新しい方法を使用して多係数変換を行うための装置及び方法を供給する。その方法は複数のディジットを有するデータ入力として表わされた整数を受け取ることを含み、その後、複数の部分商として表わされる。逆係数乗法は逆係数の概算を個々の部分商に掛けることにより行われ、係数と関連した指標値を発生する。指標値を得るため複数の除法操作を使用する伝統的な装置及び方法とは異なり、本発明は一連の逆係数乗法を行うことにより除法操作を不要にする。これらの乗法操作は除法操作より実質的に少ない処理を要求し、それ故にＭＭＣ計算操作の効率を非常に改善する。ここに説明した実施例はどちらにしても本発明の範囲を制限する意図ではなく、特許請求の範囲及びそれらの均等物により確立される。
【図面の簡単な説明】
【図１】
本発明によるＭＭＣエンコーダにより構成されたモデムシステムの概略図である。
【図２】
本発明によるあるモデムハードウェアの概略図である。
【図３】
本発明によるＭＭＣプロセッサを示すフロー図である。
【図４】
本発明による擬似符号の逆係数乗法を示すフロー図である。
【図１】
2005519506.tif 000006
【図２】
2005519506.tif 000007
【図３】
2005519506.tif 000008
【図４】
2005519506.tif 000009
【国際調査報告】
2005519506.tif 000010
2005519506.tif 000011