(57)【要約】【課題】有符号演算に制限されたプロセッサを用いる効率的な大数乗算を実行するデバイスおよび方法を導入する。【解決手段】第一の被乗数を第二の被乗数で乗算するための有符号乗算方法および対応デバイス。このデバイスは、第一の被乗数を、少なくとも一つの各デジットの第一のベクトルとして第一のレジスタ内に記憶する。そして第二の被乗数を、少なくとも一つの各デジットの第二のベクトルとして第二のレジスタ内に記憶する。この場合、各デジットは所定のビット数を持つ。この方法は、さらに、第一のベクトルおよび第二のベクトルのデジットを、各々が所定のビット数よりも１ビット少ない対応デジットへ変換する。プロセッサは、被乗数の有符号乗算を実行する。【選択図】図４
2008544344.tif 000002
【特許請求の範囲】
【請求項１】
第一の被乗数を第二の被乗数で乗算するための、無符号乗算方法であって、（ａ）前記第一の被乗数を、少なくとも一つの各デジットの第一のベクトルとして第一のレジスタ内に記憶するステップ、なお、前記デジットの各々は所定のビット数を持つ、（ｂ）前記第二の被乗数を、少なくとも一つの各デジットの第二のベクトルとして第二のレジスタ内に記憶するステップ、なお、前記デジットの各々は前記所定のビット数を持つ、（ｃ）前記第一のベクトルの前記デジットを、各々、前記所定のビット数よりも１ビット少ない対応デジットへ変換するステップ、（ｄ）前記第二のベクトルの前記デジットを、各々、前記所定のビット数よりも１ビット少ない対応デジットへ変換するステップ、そして（ｅ）すべての乗算が有符号乗算に制限されたプロセッサを用いて、前記第一の被乗数に対応する前記デジットの各々を、前記第二の被乗数に対応する前記デジットの各々で乗算することを含むステップによって、有符号乗算結果を算出するステップからなる、無符号乗算方法。
【請求項２】
前記有符号乗算結果が複数のデジットを含み、そして、前記算出が、前記有符号乗算結果の前記複数のデジットの中間値のマスキングを含む、請求項１の方法。
【請求項３】
さらに、（ｆ）前記有符号乗算結果を、対応する無符号乗算結果へ変換するステップからなる、請求項１の方法。
【請求項４】
第一の被乗数を第二の被乗数で乗算するためのデバイスであって、（ａ）前記第一の被乗数を、少なくとも一つの各デジットの第一のベクトルとして記憶するための第一のレジスタ、なお、前記デジットの各々は所定のビット数を持つ、（ｂ）前記第二の被乗数を、少なくとも一つの各デジットの第二のベクトルとして記憶するための第二のレジスタ、なお、前記デジットの各々は前記所定のビット数を持つ、そして（ｃ）すべての乗算が有符号乗算に制限されたプロセッサからなり、前記プロセッサは、前記第一のベクトルおよび前記第二のベクトルを、各々、少なくとも一つの各デジットの対応変換第一ベクトルおよび対応変換第二ベクトルへ変換し、そして前記対応変換第一ベクトルのビットを前記対応変換第二ベクトルのビットで乗算し、有符号乗算結果を算出するためのものであり、この場合の前記デジットの各々は前記所定のビット数よりも１ビット少ない、デバイス。
【請求項５】
前記プロセッサが、その場で、前記第一のベクトルおよび前記第二のベクトルの前記変換を適用する、請求項４のデバイス。
【請求項６】
さらに、（ｄ）前記対応変換第一ベクトルおよび前記対応変換第二ベクトルを記憶するための記憶ユニットからなる、請求項４のデバイス。
【請求項７】
前記有符号乗算結果が複数のデジットを含み、そして前記プロセッサが、前記有符号乗算結果の前記デジットの中間値をマスクするためのマスキング・オペレーションを適用する、請求項４のデバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、大数の乗算の分野に関し、特に、符号付き演算のみを用いて大数の乗算を提供するための方法およびデバイスに関する。
【背景技術】
【０００２】
大数乗算は、本技術で既知である、多数のコンピュータ・アルゴリズムに使用されている。大数演算の一般的な用途は、（各々が１０００ビット程度の）非常に大きな数の、多数の乗算オペレーションを実行する公開鍵暗号法およびモンゴメリー乗算を含む。  
【０００３】
「大数」は、レジスタを持つプロセッサが用いる、Ｎビットの整数、または幅がＷビットのワード・サイズである。この場合、Ｎ>２×Ｗである。用語「ワード・サイズ」は、単精度レジスタのビット数、または使用中のプロセッサのメモリ幅を指す。Ｗビットのワード・サイズを持つ一般的なプロセッサは、Ｗビットの二つのワードを乗算し、その結果を、２×Ｗビットの二倍幅レジスタに記憶することが可能である。乗算すべきオペランドのサイズがＷビットよりも大きい場合は、専用の乗算アルゴリズムが必要である。  
【０００４】
図１は、ペンと紙とを使用して、二つの、複数桁の数字を掛け算するための、従来の技術による乗算プロシージャ１０を表す。各数は、二つの十六進数字から構成されている。第一の数は、（参照番号１２によって示す）３Ｂであり、第二の数は、（参照番号１４によって示す）ＣＡである。乗算プロシージャ１０は、第二の数１４の最下位の数字（ＬＳＤ）のみを、第一の数１２の二つの数字に乗算することから開始し、第一の中間結果を生み出す。この第一の中間結果は、参照番号１６によって示す。  
【０００５】
次に、類似のオペレーションを実行し、第二の数１４の最上位の数字（ＭＳＤ）を、第一の数１２の二つの数字に乗算して、第二の中間結果を生み出す。参照番号１８によって示す第二の中間結果は、第一の中間結果１６の下方、一桁左へ移して書き込む。  
【０００６】
乗算プロシージャ１０が完了すると、第一の中間結果１６と第二の中間結果１８との合計が、（参照番号２０によって示す）乗算結果２Ｅ８Ｅである。  
【０００７】
ここに示す十六進数の乗算は、説明を明瞭にするためにのみ用いている。本技術において既知であるコンピュータ・アルゴリズムは、二進数に対して乗算を適用する。  
【０００８】
図２は、図１に示す二つの、複数ワードの数の乗算に適用した、従来の技術によるコンピュータ乗算アルゴリズム３０のフロー・チャートである。コンピュータを用いる場合、数の各デジットは、Ｗビットのコンピュータ・ワードで表す。用語デジットは、コンピュータ・ワードのサイズである大数の一部分に言及する。  
【０００９】
一般に、コンピュータ乗算アルゴリズム３０は、従来の技術によるプロシージャ１０に同様な様式で適用する（図１を参照）。しかし、コンピュータ乗算アルゴリズムによれば、各中間乗算の結果は、乗算アルゴリズムの進行に応じて、結果ベクトルへ加算するが、図１の乗算プロシージャ１０によれば、途中結果は別個に記憶し、最終段階で合計する。  
【００１０】
最初のステップ３２で、二つの被乗数ベクトルＸおよびＹと、その結果を保持するための結果ベクトルＺを提供する。ベクトルＸ、ＹおよびＺは、Ｗビット・ワードからなる。入力ベクトルＸおよびＹの長さは、各々、ｍａｘ_ｘおよびｍａｘ_ｙである。乗算結果を一時的に保持するために、（２×Ｗビット構成の）二倍幅レジスタｒを用いる。  
【００１１】
ステップ３４で、結果ベクトルＺをクリアする。  
【００１２】
ステップ３６で、二つの被乗数ベクトルＸおよびＹの内部変数ｉ、ｊ、ｃ１およびｃ２をクリアする。この場合、ｉは第一数デジット・インデックスであり、ｊは第二数デジット・インデックスであり、ｃ１は直前の乗算オペレーションからの高位のワードであり、そしてｃ２は直前の加算演算からの繰り上げである。  
【００１３】
以下のステップ３８、４０、４２、４４、４６および４８は、主要な乗算ループを構成する。ステップ３８で、二つのデジットを乗算し、直前の乗算高位のワードｃ１と、直前の加算オペレーションｃ２からの繰り上げを加算する。その結果を、二倍幅レジスタｒ内に一時的に記憶する。  
【００１４】
ステップ４０で、高位ワード乗算の結果ｒをｃ１内に記憶する。  
【００１５】
次のステップ４２で、加算繰り上げを計算してｃ２内に記憶する。  
【００１６】
ステップ４４で、結果ベクトル要素Ｚｉ＋ｊを、それに乗算結果を加算することによって更新する。各結果ベクトル要素の幅がＷであるため、ｒの低位ワードのみがエレメントＺｉ＋ｊに加算される。  
【００１７】
ステップ４６で、Ｘ被乗数インデックスｉを、１だけ増加させる。  
【００１８】
次のステップ４８で、ｉの値が入力ベクトルＸの長さよりも大きいかどうかを判定する。肯定の場合は、コンピュータ乗算アルゴリズムは、ステップ５０へ進む。しかし、否定の場合は、コンピュータ乗算アルゴリズムは、ステップ３８へ戻り、主要な乗算ループを繰り返す。  
【００１９】
ステップ５０で、次の結果ワードを、それにｃ１およびｃ２の値を加算することによって更新する。  
【００２０】
ステップ５２で、第二の被乗数インデックスｊを１だけ増加させて、内部変数ｉ、ｃ１およびｃ２をクリアする。  
【００２１】
次のステップ５４で、内部変数ｊが入力ベクトルＹの長さよりも大きいかどうかを判定する。肯定の場合（すなわち、ｍａｘ_ｘ掛けるｍａｘ_ｙ乗算オペレーションを実行した後）、コンピュータ乗算アルゴリズムはステップ５６で終了し、結果ベクトルＺが最終的な乗算結果を保持する。しかし、否定の場合は、コンピュータ乗算アルゴリズムは、ステップ３８から内部ループを繰り返して、第一の被乗数を第二の被乗数の次のワードで乗算する。  
【００２２】
従来の技術によるコンピュータ乗算アルゴリズムは、無符号の乗算オペレーションに基づく、大数の乗算を提供する。換言すれば、入力ベクトルＸ、Ｙ、また結果ベクトルＺは、すべて、デジット毎にＷビットの正数を含む（符号ビットが全くない）。  
【００２３】
しかしながら、本技術において既知であるいくつかのデジタル信号プロセッサ（ＤＳＰ）は、符号付きオペレーションのみに対する演算サポートを持つ。無符号演算をサポートしない（すなわち、有符号演算のみに制限した）従来の技術によるＤＳＰの一例は、例えばＬＳＩロジック社が提供するＺＳＰ２００ＤＳＰである。  
【００２４】
そのようなタイプのＤＳＰにおいては、各ワードの最上位ビット（ＭＳＢ）は、常に符号ビットである。上記説明のままの、従来の技術によるコンピュータ乗算アルゴリズムを使用して、有符号乗算オペレーションを実行すると、誤った結果を生じることになる。例えば、ワード・サイズが８ビット（Ｗ＝８）である場合、数０ｘＦＦ×０ｘＦＦの無符号乗算オペレーションの結果は、０ｘＦＥ０１である（２５５×２５５は、６５，０２５である）。有符号オペレーションのみをサポートする場合、数２５５は−１を表す。数−１×−１の乗算オペレーションの結果は、＋１を生じるが、これは、無符号オペレーションを用いた結果とは異なる。  
【００２５】
有符号オペレーションを実行可能な、本技術において既知であるプロセッサを使用するコンパイラは、有符号乗算結果を無符号結果へ変換する一連のオペレーションを実行することによってのみ、上述の問題を解決する。  
【００２６】
本技術において既知である変換プロセスは、典型的に、以下のように実行される。＜定義＞Ｗは、レジスタ内のビット数、またはメモリ幅である。ＡおよびＢは、被乗数である。各被乗数は、長さがＷビットである。ｒは、無符号Ａ×Ｂオペレーションの結果を記憶するために用いる、二倍幅の変数（２×Ｗビット）である。ｒｓは、二つの被乗数ＡおよびＢの有符号乗算積（２×Ｗビット）である。ＡのＭＳＢが１である（Ａを負の数とみなす）場合、〜Ａは、二つの、Ａの補数である、と定義する。０−〜Ａ＝Ａであることに留意する。  
【００２７】
有符号乗算オペレーションＡ×Ｂを実行するとき、Ａが負数であり（そのＭＳＢが１である）場合、Ａは、Ａ＝２Ｗ−〜Ａである、と定義する。この数にＢを乗算すると、ｒ＝（２Ｗ−（〜Ａ））ｘＢ＝２Ｗ×Ｂ＋−（〜Ａ×Ｂ）＝２Ｗ×Ｂ＋ｒｓという結果を生じる。  
【００２８】
それゆえ、正数Ｂによる負数Ａの無符号乗算オペレーションを実行するためには、ＡとＢの有符号乗算オペレーションを実行してから、その結果にＢ×２Ｗの値を加算することができる。注目すべきは、Ｂ×２Ｗの乗算プロセスは、ＢをＷビットだけ左へ移すのと同じである、ということである（Ｂ×２Ｗ＝Ｂ<<Ｗ）。同様に、被乗数ＡおよびＢが負である場合、結果は、ｒ＝２Ｗ×Ａ＋２Ｗ×Ｂ＋ｒｓまたはｒ＝（Ａ<<Ｗ）＋（Ｂ<<Ｗ）＋ｒｓである。  
【００２９】
結論として、有符号のみの演算ユニットを持つ、無符号乗算を実行する一般的な、従来の技術によるプロセッサは、以下のオペレーションを実行する。（１）被乗数ＡおよびＢの有符号乗算を実行する。そして（２）各被乗数（ＡおよびＢ）の符号ビットをテストする。被乗数が負である場合、他の被乗数を左へＷビットだけ移し、その移した他の被乗数を、有符号乗算オペレーションの結果に加算する。  
【００３０】
負数の確率は５０%であるため、平均で、既存のプロセッサは、乗算オペレーション毎に、二倍サイズの数の一回の移動と、二倍サイズの数の一回の加算を実行しなければならない。そのようなプロセッサは、各被乗数が正あるいは負であるのかを判定するために、各被乗数をテストしなければならない。  
【００３１】
これらの追加の算術演算は、有符号限定プロセッサの乗算性能を、無符号乗算を実行可能なプロセッサに比べ、著しく減少させる。ＤＳＰを用いる場合、状況はさらに悪化する。ＤＳＰは、単一オペレーション内で乗算および加算を実行することが可能であるが、上述のように追加の算術オペレーションを実行する必要があると、ＤＳＰの乗算および加算命令の単一オペレーションという利点を利用できない。
【００３２】
したがって、既存技術の欠点を解決する、有符号演算限定のプロセッサを用いて効率的な大数乗算を実行するデバイスおよび方法の必要性が広く認識される。また、そのようなものを得ることは非常に有利である。
【発明の開示】
【課題を解決するための手段】
【００３３】
したがって、本発明の主要な目的は、有符号演算に制限されたプロセッサを用いる効率的な大数乗算を実行するデバイスおよび方法を導入することによって、従来の技術の欠点を解決することである。  
【００３４】
本発明によれば、次のことを含む、第一の被乗数を第二の被乗数で乗算するための無符号乗算方法が提供される。（ａ）第一の被乗数を第一のレジスタ内に、少なくとも一つの各デジットの第一のベクトルとして記憶すること。なお、各デジットは、所定のビット数を持つ。（ｂ）第二の被乗数を第二のレジスタ内に、少なくとも一つの各デジットの第二のベクトルとして記憶すること。なお、各デジットは、所定のビット数を持つ。（ｃ）第一のベクトルのデジットを、各々、所定のビット数よりも１ビット少ない対応デジットへ変換すること。（ｄ）第二のベクトルのデジットを、各々、所定のビット数よりも１ビット少ない対応デジットへ変換すること。そして（ｅ）すべての乗算が有符号乗算に制限されたプロセッサを用い、第一の被乗数に対応する各デジットを第二の被乗数に対応する各デジットで乗算することを含むステップによって、有符号乗算結果を算出すること。  
【００３５】
算出ステップは、有符号乗算結果のデジットの中間値をマスクすることを含むことが好ましい。有符号乗算結果のデジットの中間値は、図４に示すボックス８６内のエレメントＺｉ＋ｊである。  
【００３６】
この方法は、さらに、（ｆ）有符号乗算結果を、対応する無符号乗算結果へ変換
することを含むことが好ましい。  
【００３７】
本発明によれば、さらに、第一の被乗数を第二の被乗数で乗算するための、次のものを含むデバイスが提供される。（ａ）第一の被乗数を、少なくとも一つの各デジットの第一のベクトルとして記憶するための第一のレジスタ。この場合、各デジットは、所定のビット数を持つ。（ｂ）第二の被乗数を、少なくとも一つの各デジットの第二のベクトルとして記憶するための第二のレジスタ。この場合、各デジットは、前記所定のビット数を持つ。そして（ｃ）すべての乗算が有符号乗算に制限されたプロセッサ。このプロセッサは、第一のベクトルおよび第二のベクトルを、各々、各デジットが上記所定のビット数よりも１ビット少ない少なくとも一つの各デジットの対応変換第一ベクトルおよび対応変換第二ベクトルへ変換し、そして対応変換第一ベクトルのビットを対応変換第二ベクトルのビットで乗算して、有符号乗算結果を算出するためのものである。  
【００３８】
プロセッサは、既存の第一および第二のレジスタを用いて、その場で第一のベクトルおよび第二のベクトルの変換を適用することが好ましい。代替的に、対応変換第一ベクトルおよび対応変換第二ベクトルを記憶するために、第三の記憶ユニットを備えてもよい。  
【００３９】
プロセッサは、有符号乗算結果のデジットの中間値をマスクするためのマスキング・オペレーションを適用することが好ましい。  
【００４０】
本発明の、他の特徴および利点は、以下の図面および説明文から明らかになる。  
【００４１】
本発明をより良く理解するために、その実施例に関する添付の図面を参照する。図中、類似符号は、対応するセクションまたはエレメントを示す。
【発明を実施するための最良の形態】
【００４２】
本発明は、有符号演算のみに限定したプロセッサを用いて効率的な大数乗算を実行する、革新的なデバイスおよび方法である。本発明の好適方法は、二つの主な段階で実行される。第一に、最上位ビットがゼロ・ビットとなるよう、Ｗビット・ワードで表す乗数を、Ｗ−１ビット・ワードへ変換する。この変換は、有符号ビット（ＭＳＢ）が常に０であることを保証する。第二に、本技術において既知である乗算アルゴリズムを用いる長数乗算プロシージャを実行する。  
【００４３】
さて、被乗数が正数になったので、（本技術において既知である乗算技術が必要とする）有符号乗算結果を無符号の結果へ変換するための、算術オペレーションの追加のシーケンスを適用する必要はない。  
【００４４】
したがって、非常に大きな被乗数に対して本発明の方法を実行すれば、本技術において既知である標準乗算技術に比べ、著しいコスト低減が達成できる。さらに、本発明は、単一オペレーションで加算と乗算を実行するためにＤＳＰの機能を利用して、さらに高度な乗算性能を得る。  
【００４５】
本技術において既知である他の乗算システムとの互換性を保つために、本発明は、乗算プロシージャのＷ−１ビット・ワード結果を、所定のワード表記（本文ではＷビット・ワード）へと変換するオプションを提供する。そのような変換は、少なくとも一つの出力ワードのＭＳＢが、『１』ビットであることを可能にする。  
【００４６】
さて、図３を参照する。複数のＷビット・ワードを複数のＷ-１ビット・ワードへ変換するための、従来の技術による変換プロシージャ６０を示すブロック図である。この場合、例えば、Ｗ＝８。  
【００４７】
ｎビットを持つ被乗数のワード数［ｎ/Ｗ］であり、この場合、Ｗは、各ワードのビット数（例えば、Ｗ＝８）である。例えば、第一のワードｗ１の８ビットは、Ａ０（ＬＳＢ）、Ａ１、Ａ２、Ａ３、Ａ４、Ａ５、Ａ６およびＡ７（ＭＳＢ）によって表し、第二のワードｗ２の８ビットは、Ｂ０（ＬＳＢ）、Ｂ１、Ｂ２、Ｂ３、Ｂ４、Ｂ５、Ｂ６およびＢ７（ＭＳＢ）によって表す。第三のワードｗ３の８ビットは、Ｃ０（ＬＳＢ）、Ｃ１、Ｃ２、Ｃ３、Ｃ４、Ｃ５、Ｃ６およびＣ７（ＭＳＢ）と表し、以下、同様に表す。  
【００４８】
第一のオペレーションは、被乗数の最下位デジット（ＬＳＤ）を保持する第一のワードｗ１の最上位ビット（ＭＳＢ）Ａ７を、第二のワードｗ２の最下位ビット（ＬＳＢ）Ｂ０へコピーし、第二のワードｗ２のビットＢ０、Ｂ１、Ｂ２、Ｂ３、Ｂ４およびＢ５を１位置だけ左へシフトすることを伴う。  
【００４９】
第二のオペレーションは第二のワードｗ２に対して適用するが、今度は二つの最上位ビットＢ６およびＢ７を、第三のワードｗ３の二つの最下位ビットＣ０およびＣ１へコピーし、第三のワードｗ３のビットＣ０、Ｃ１、Ｃ２、Ｃ３およびＣ４を２位置だけ左へシフトする。  
【００５０】
被乗数のすべての［ｎ/Ｗ］ワードに類似オペレーションを適用した後、［ｎ/（Ｗ−１）］新変換ワードが生じ、各新変換ワードはＷ−１ビットのみで表される。  
【００５１】
実際には、上記の、ＷビットからＷー１ビットへの変換プロシージャを（例えば共通バッファを用いて）その場で実行する場合、これらのオペレーションは、ＭＳＤ（最上位デジット）からＬＳＤ（最下位デジット）へ適用する。例えば、第二のオペレーションの場合には、第三のワードｗ３のビットＣ０、Ｃ１、Ｃ２、Ｃ３およびＣ４を２位置だけ左へシフトさせる前に、二つの最上位ビットＢ６およびＢ７を二つの最下位ビットＣ０およびＣ１へコピーする。  
【００５２】
さて、図４を参照する。これは、本発明の方法７０を表すフロー・チャートである。  
【００５３】
最初のステップ７２で、図３の変換プロシージャ６０を実行して、被乗数のＷビット・ワード表記をＷ−１ビット・ワード表記へ変換する。両入力オペランドＸおよびＹを、新しいＷ−１ビット・ワード表記へ変換する（すなわち、乗数を保持するのに用いる各ワードは、Ｗ−１ビットを含む）。変換には、（十分なメモリが割り当てられるならば）、「オリジナル」Ｗビット・ワード表記の入力被乗数を保持する、同じ入力バッファを採用してもよいし、または別個に割り当てたバッファをさらに採用してもよい。入力ベクトルＸおよびＹの長さは、それぞれ、ｍａｘ_ｘおよびｍａｘ_ｙである。  
【００５４】
ｍａｘ_ｘおよびｍａｘ_ｙは、以下の通りに計算する。  
【００５５】
ｍａｘ_ｘ＝［ｎｘ/（Ｗ−１）］、そしてｍａｘ_ｙ＝［ｎｙ/（Ｗ−１）］。この場合、ｎｘは、オペランドＸの長さ（すなわちビット数）を表し、ｎｙは、オペランドＹの長さ（すなわちビット数）を表す。  
【００５６】
次のステップ７４で、結果を保持するための結果ベクトルＺを提供する。乗算結果を一時的に保持するために、（２×Ｗビット構成の）二倍幅レジスタｒを用いる。本発明のマスクは、２Ｗ−１−１（ＭＳＢビットは「０」で、すべての他のビットは「１」である）と定義する。本文では、マスキング・オペレーションを、Ｗビット・ワードをマスクに対して論理的にＡＮＤするオペレーションと定義する。  
【００５７】
以下のステップ７６、７８、８０、８２および８４は、図２に示すコンピュータ乗算アルゴリズム３０の対応するステップ３４、３６、３８、４０および４２と同一である。  
【００５８】
ステップ７６で、結果ベクトルＺをクリアする。  
【００５９】
ステップ７８で、二つの被乗数ベクトルＸおよびＹの内部変数ｉ、ｊ、ｃ１およびｃ２をクリアする。この場合、ｉは第一数デジット・インデックスであり、ｊは第二数デジット・インデックスであり、ｃ１は直前の乗算オペレーションからの高位ワードであり、そして、ｃ２は直前の加算オペレーションからの繰り上げである。  
【００６０】
ステップ８０、８２、８４、８６、８８および９０は、主要な乗算ループである。ステップ８０で、二つのデジットを乗算し、直前の乗算高位ワードｃ１と、直前の加算オペレーションｃ２からの繰り上げを加算する。結果は、二倍幅レジスタｒ内に一時的に記憶する。  
【００６１】
ステップ８２で、高位ワード乗算の結果ｒをｃ１内に記憶する。  
【００６２】
次のステップ８４で、加算繰り上げを計算して、ｃ２内に記憶する。  
【００６３】
ステップ８６で、結果ベクトル要素Ｚｉ＋ｊを、それに乗算結果を加算することによって更新する。結果ベクトル要素の幅がＷであるので、ｒの低位ワードだけをＺｉ＋ｊへ加算する。それから、この結果ベクトル要素Ｚｉ＋ｊに対してマスキング・オペレーションを適用する。有符号算術オペレーションを実行する場合、結果ベクトル要素Ｚｉ＋ｊの符号ビット（ＭＳＢ）は無関係であるため、（Ｗ−１「１」−ビット・マスクの）マスキング・オペレーションは、結果ベクトル要素Ｚｉ＋ｊのこの符号ビット（ＭＳＢ）をクリアすることを保証する。  
【００６４】
以下のステップ８８、９０、９２、９４、９６および９８は、図２に示す、対応する従来の技術によるステップ４６、４８、５０、５２、５４および５６と同様な様式で適用する。  
【００６５】
ステップ８８で、Ｘ被乗数インデックスｉを、１だけ増加させる。  
【００６６】
ステップ９０で、ｉの値が入力ベクトルＸの長さよりも大きいかどうかを判定する。肯定の場合は、長数乗算プロシージャはステップ９２へ進む。しかしながら、否定の場合には、長数乗算プロシージャは、ステップ７８を適用するために戻り、主要な乗算ループを繰り返す。  
【００６７】
ステップ９２で、次の結果ワードを、それにｃ１およびｃ２の値を加算することによって更新する。  
【００６８】
ステップ９４で、第二の被乗数インデックスｊを１だけ増加させ、内部変数ｉ、ｃ１およびｃ２をクリアする。  
【００６９】
次のステップ９６で、内部変数ｊが入力ベクトルＹの長さよりも大きいかどうかを判定する。肯定の場合（すなわち、ｍａｘ_ｘ掛けるｍａｘ_ｙの乗算オペレーションの実行後）、最終的な乗算結果を保持する有符号結果ベクトルＺを、無符号結果ベクトルへ変換する。これは、複数のＷー１ビット・ワードを複数のＷビット・ワードへ変換するための、例えば、従来の技術による変換プロシージャ（例えば、図３の逆変換プロシージャ）を用いることによって実行する。しかし、否定の場合は、長数乗算プロシージャは、ステップ８０から内部ループを繰り返して、第一の被乗数を第二の被乗数の次のワードに乗算する。  
【００７０】
図５を参照する。これは、本発明によるデバイス１００の高度な概略ブロック図である。各々をＷビットで表したデジットの第一のベクトルとして第一の被乗数を記憶するためにレジスタ１０２を備え、各々をＷビットで表したデジットの第二のベクトルとして第二の被乗数を記憶するためにレジスタ１０４を備える。  
【００７１】
有符号乗算のみに制限されたプロセッサ１０６は、第一の被乗数の、そして第二の被乗数のデジットの各々を、Ｗ−１ビット表記へ変換し、それから、第一の被乗数の変換デジットを第二の被乗数の変換デジットで乗算して有符号乗算結果を算出する。  
【００７２】
第一の被乗数の変換デジットおよび第二の被乗数の変換デジットをそれぞれ記憶するために、記憶装置１０３（例えば、ＲＡＭ、レジスタ、その他）を備えることが好ましい。プロセッサ１０６が算出した有符号乗算結果も、Ｗ−１ビットで各々を表したワードとして、記憶ユニット１０３内に記憶する。  
【００７３】
プロセッサ１０６は、また、有符号乗算結果を無符号乗算結果へ変換し、この無符号乗算結果を、Ｗビットで各々を表したワードとして記憶ユニット１０３内に記憶する。  
【００７４】
代替的に、第一の被乗数の、そして第二の被乗数のＷ−１ビット表記への変換は、適所あるプロセッサ１０６によって（すなわち、各々レジスタ１０２およびレジスタ１０４を用いて）適用できる。  
【００７５】
本文では、本発明を、特定乗算アルゴリズムによって実行するものとして説明している。しかしながら、本発明の範囲内で他の実施例が可能であることは理解すべきである。したがって、本発明は、効率的な大数乗算を実行する前に被乗数の各Ｗビット・ワ
ードを、Ｗ−１ビット・ワードへ変換する他の方法およびデバイスにも関する。  
【００７６】
本発明をその特定な実施例に関して説明したが、理解すべきことは、その説明は制限を意味せず、当業技術者による修正はさらに可能であるため、そのような修正は添付の請求項の範囲内に含むことを意図している、ということである。
【図面の簡単な説明】
【００７７】
【図１】ペンと紙を用いる、二つの複数桁の数字を乗算するための、従来の技術による乗算プロシージャを表す。
【図２】図１に示す二つの複数ワードの数の乗算に適用した、従来の技術によるコンピュータ乗算アルゴリズムを表すフロー・チャートである。
【図３】Ｗビット・ワードをＷ−１ビット・ワードへ変換するための、従来の技術による変換プロシージャを示すブロック図である。この場合、例えば、Ｗ＝８。
【図４】本発明による方法を表すフロー・チャートである。
【図５】本発明によるデバイスの、高度な概略ブロック図である。
【図１】
2008544344.tif 000003
【図２】
2008544344.tif 000004
【図３】
2008544344.tif 000005
【図４】
2008544344.tif 000006
【図５】
2008544344.tif 000007
【国際調査報告】
2008544344.tif 000008