(57)【特許請求の範囲】
【請求項１】
データ処理装置であって：
（ｉ）  Ｎビットデータ処理レジスタのレジスタバンク；そして
（ｉｉ）前記レジスタバンクに結合され、前記Ｎビットデータ処理レジスタ内に保持されている被演算子に対して掛け算累算演算処理を実行するための掛け算累算器とを含み；ここに於いて
（ｉｉｉ）前記掛け算累算器は掛け算累算命令の第１クラスに応答して、第１データ処理レジスタ内に保持されているＮビット被演算子と第２データ処理レジスタ内に保持されているＮビット被演算子とを掛け算し、そして第３データ処理レジスタ内に保持されているＮビット被演算子を加算して、第４データ処理レジスタの中に格納されるＮビットの結果を算出し、前記第１、第２、第３および第４データ処理レジスタは掛け算累算命令の前記第１クラスの中のフィールドとして独立に指定され；そして
（ｉｖ）前記掛け算累算器は掛け算累算命令の第２クラスに応答して、第１データ処理レジスタ内に保持されているＮビット被演算子と第２データ処理レジスタ内に保持されているＮビット被演算子とを掛け算し、そして第３および第４データ処理レジスタ内に保持されている２Ｎビット被演算子を加算して、第３および第４データ処理レジスタの中に格納される２Ｎビットの結果を算出し、前記第１、第２、第３および第４データ処理レジスタは掛け算累算命令の前記第２クラスの中のフィールドとして独立に指定されている、前記装置。
【請求項２】
請求項第１項記載の装置に於いて、前記掛け算累算器は掛け算と、累算とを単一組み合わせ演算として実行する、前記装置。
【請求項３】
請求項第１項記載の装置に於いて、
前記掛け算累算器は掛け算命令の第１クラスに応答して、第１データ処理レジスタ内に保持されているＮビット被演算子と第２データ処理レジスタ内に保持されているＮビット被演算子とを掛け算してＮビットの結果を算出し、これは第３データ処理レジスタ内に格納され、前記第１、第２、および第３データ処理レジスタは前記掛け算命令の第１クラスの中のフィールドとして独立に指定されており；そして
前記掛け算累算器は掛け算命令の第２クラスに応答して、第１データ処理レジスタ内に保持されているＮビット被演算子と第２データ処理レジスタ内に保持されているＮビット被演算子とを掛け算して２Ｎビットの結果を算出し、これは第３並びに第４データ処理レジスタ内に格納され、前記第１、第２、第３及び第４データ処理レジスタは前記掛け算命令の第２クラスの中のフィールドとして独立に指定されている、前記装置。
【請求項４】
請求項第１項記載の装置に於いて、前記データ処理レジスタを指定する前記フィールドが、前記第１クラスの掛け算累算命令に含まれる命令ビットおよび前記第２クラスの掛け算累算命令に含まれる命令の半分を超えて占めないことを特徴とする、前記装置。
【請求項５】
請求項第１項記載の装置に於いて、前記データ処理レジスタの前記バンクが１６個以下のデータ処理レジスタを含む、前記装置。
【請求項６】
請求項第１項記載の装置に於いて、前記装置が集積回路マイクロプロセッサを含む、前記装置。
【請求項７】
請求項第１項記載の装置に於いて、前記第１クラスの掛け算累算命令に含まれる命令および前記第２クラスの掛け算累算命令に含まれる命令が、条件付き実行コードを含み、そして前記条件付き実行コードに応答して命令がスキップされるべきかまたは実行されるべきかの制御を行うための装置を含む、前記装置。
【請求項８】
請求項第１項記載の装置に於いて、前記掛け算累算器が専用のハードウェア掛け算累算器である、前記装置。
【請求項９】
請求項第１項記載の装置に於いて、Ｎが３２に等しい前記装置。
【請求項１０】
Ｎビットデータ処理レジスタのレジスタバンクと、前記レジスタバンクに結合され、前記Ｎビットデータ処理レジスタ内に保持されている被演算子に対して掛け算累算演算処理を実行するための掛け算累算器とを有する装置を使用したデータ処理の方法であって、該方法が：
（ｉ）掛け算累算命令の第１クラスに応答して、第１データ処理レジスタ内に保持されているＮビット被演算子と第２データ処理レジスタ内に保持されているＮビット被演算子とを掛け算し、そして第３データ処理レジスタ内に保持されているＮビット被演算子を加算して、第４データ処理レジスタの中に格納されるＮビットの結果を算出し、前記第１、第２、第３および第４データ処理レジスタは掛け算累算命令の前記第１クラスの中のフィールドとして独立に指定され；そして
（ｉｉ）掛け算累算命令の第２クラスに応答して、第１データ処理レジスタ内に保持されているＮビット被演算子と第２データ処理レジスタ内に保持されているＮビット被演算子とを掛け算し、そして第３および第４データ処理レジスタ内に保持されている２Ｎビット被演算子を加算して、第３および第４データ処理レジスタの中に格納される２Ｎビットの結果を算出し、前記第１、第２、第３および第４データ処理レジスタは掛け算累算命令の前記第２クラスの中のフィールドとして独立に指定される、以上の手順を含む、前記方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明はデータ処理の分野に関する。更に詳細には、本発明は掛け算累算命令が第１被演算子が第２被演算子と掛け算されそして第３被演算子が加算されることで結果を算出するように指定するように使用されている種類のデータ処理に関する。被演算子はシステム内のデータ処理レジスタのバンクからデータ処理レジスタの中に格納される。
【０００２】
【従来の技術】
その命令セットの中に掛け算累算命令を有するデータ処理システムを用意することは知られている。その様なシステムの１つの例は、アドバンストＲＩＳＣマシン有限会社で製造されるＡＲＭ６集積回路マイクロプロセッサである。ＡＲＭ６マイクロプロセッサは、第１の３２ビット被演算子を第２の３２ビット被演算子に掛け算し、次に第３の３２ビット被演算子を加算するための掛け算累算命令を組み込んでいる。この命令に対する３つの入力被演算子を含むレジスタは、この結果がその中に書き込まれるべきレジスタと共に掛け算累算命令の中のフィールドで指定されている。例としてあげれば、互いに掛け算される２つの３２ビット被演算子はレジスタ５並びにレジスタ６であり、累算値はレジスタ１０の中にあってその結果がレジスタ２に書き込まれるといった具合である。
【０００３】
データ処理システムは使用者から要求されるデータ処理演算を最少数の命令で指定できることが望ましい。これは結果としてプログラムサイズがより少なくなり、一般的により早くそして更に効率的な演算が得られる。しかしながら、この様に更に複雑で高度なデータ処理演算を単一命令の中に用意する際の問題は、この命令で指定される必要のある情報の量である。更に詳細には、もしも命令が多数のデータ処理レジスタをその命令を実行するための資源として使用する場合は、これらのレジスタの同一性識別がその命令の中で指定されなければならない。これは命令の中で許容できないほどのビット空間量を使用する可能性がある。比較的大きな数のデータ処理レジスタをシステムの中で使用する、この様に高度で複雑な命令に関連する更に別の問題は、プログラムの効率的なコンパイルが更に難しくなることであり、それは使用される多くの異なる被演算子の間で、有限のレジスタ資源を共有しなければならないためである。
【０００４】
【発明の目的と要約】
上述の問題を解決することが本発明の目的である。
【０００５】
ひとつの特徴から見ると、本発明はデータ処理用の装置を提供し、前記装置は：
（ｉ）  Ｎビットデータ処理レジスタのレジスタバンク；そして
（ｉｉ）前記レジスタバンクに結合され、前記Ｎビットデータ処理レジスタ内に保持されている被演算子に対して掛け算累算演算処理を実行するための掛け算累算器とを含み；ここに於いて
（ｉｉｉ）前記掛け算累算器は掛け算累算命令の第１クラスに応答して、第１データ処理レジスタ内に保持されているＮビット被演算子と第２データ処理レジスタ内に保持されているＮビット被演算子とを掛け算し、そして第３データ処理レジスタ内に保持されているＮビット被演算子を加算して、第４データ処理レジスタの中に格納されるＮビットの結果を算出し、前記第１、第２、第３および第４データ処理レジスタは掛け算累算命令の前記第１クラスの中のフィールドとして独立に指定され；そして
（ｉｖ）前記掛け算累算器は掛け算累算命令の第２クラスに応答して、第１データ処理レジスタ内に保持されているＮビット被演算子と第２データ処理レジスタ内に保持されているＮビット被演算子とを掛け算し、そして第３および第４データ処理レジスタ内に保持されている２Ｎビット被演算子を加算して、第３および第４データ処理レジスタの中に格納される２Ｎビットの結果を算出し、前記第１、第２、第３および第４データ処理レジスタは掛け算累算命令の前記第２クラスの中のフィールドとして独立に指定されている。
【０００６】
本発明は、利用可能なレジスタ資源に対して高い要求を課す掛け算累算命令の場合には、異なる精度並びにシステム資源に対する要求とを有する複数のクラスの掛け算累算命令を用意することが非常に都合が良いことを認識している。（Ｎ＊Ｎ）＋Ｎ演算を実行する掛け算累算命令の第１クラスは、Ｎビットの結果を算出しこれは、２Ｎビットの結果を算出する（Ｎ＊Ｎ）＋２Ｎ演算を実行する掛け算累算命令の第２クラスよりも比較的精度が低い。掛け算累算命令り第２クラスは、結果を入力変数を保持していた２つのレジスタの中に書き込むように要求することで、命令の中のビット空間を過度に圧迫することを回避している。これらの掛け算累算命令を具備した装置を使用するプログラマは、関係している個別の環境に最も適した命令を選択することが可能である；自由に入力および出力レジスタの両方を指定したいという要求は、一命令で２Ｎビットの結果を得たいという要求との対比の上に立っていると言える。２つの命令を用意することによって、関連するプログラムがより小さくなりそして更に高速に実行されるという波及効果を生む。
【０００７】
掛け算累算器は多くの異なる手法で構成できるであろう。ひとつの可能性としては、掛け算累算器が最初に掛け算演算を完了し、そして次に加算演算を別の後処理として実行する方法である。しかしながら本発明は、前記掛け算累算器が掛け算と加算とを単一の組み合わされた演算として実行するアプリケーションに特に適している。
【０００８】
単一に組み合わされた演算としての掛け算及び加算は、速度が速くなりデータ経路幅が小さくなるという特長を有するが、全ての入力被演算子が同時に利用可能であることという要求を課する。
【０００９】
掛け算累算器はその機能ユニットのいくつかをバイパスする事により、別の算術演算を実行させるように作ることも可能である。この方法により、本発明の提出された実施例では前記掛け算累算器は掛け算命令の第１クラスに応答して、第１データ処理レジスタ内に保持されているＮビット被演算子と第２データ処理レジスタ内に保持されているＮビット被演算子とを掛け算してＮビットの結果を算出し、これは第３データ処理レジスタ内に格納され、前記第１、第２、および第３データ処理レジスタは前記掛け算命令の第１クラスの中のフィールドとして独立に指定されており；そして
前記掛け算累算器は掛け算命令の第２クラスに応答して、第１データ処理レジスタ内に保持されているＮビット被演算子と第２データ処理レジスタ内に保持されているＮビット被演算子とを掛け算して２Ｎビットの結果を算出し、これは第３並びに第４データ処理レジスタ内に格納され、前記第１、第２、第３及び第４データ処理レジスタは前記掛け算命令の第２クラスの中のフィールドとして独立に指定されている。
【００１０】
異なる精度を有する掛け算命令の第１および第２クラスを用意することは、異なる精度を有する掛け算累算命令を補足することである。
【００１１】
この様に比較的高度で複雑な掛け算累算命令を用意することにより、命令セットの密度が過度に薄くならないようにするために、前記データ処理レジスタを指定する前記フィールドが、掛け算累算命令の前記第１クラス内の命令ビット、および掛け算累算命令の前記第２クラス内の命令の半分を超えて占めないようにすることが望ましい。
【００１２】
データ処理レジスタを指定するフィールド用の空間が削減されると、指定できる異なるレジスタの最大数もまた削減される。この文脈に於いて、本発明は前記データ処理レジスタのバンクが、１６個以下の同時に使用されるデータ処理レジスタ、すなわち命令内でレジスタを指定するために唯４ビットのみを必要とする、を含む実施例に特に適している。
【００１３】
本発明を個別の回路素子で構成することも可能であるが、本発明は集積回路マイクロプロセッサの一部として実施することが特に適していることを理解されよう。
【００１４】
システムのコーディング効率は、掛け算累算命令の前記第１クラス内の命令および掛け算累算命令の前記第２クラス内の命令が、条件付き実行コードを含み、そして前記条件付き実行コードに応答して命令が実行せずにスキップされるか否かを制御するための手段とで構成されたフィールドを含む時に改善される。
【００１５】
条件付き実行コードを用意することはコーディング効率を増加させる一方で、命令内で利用可能なビット空間、結果としてはその命令でどのレジスタが使用されるべきかを指定するために利用可能な空間を多く必要とする。この理由から、本発明はこの様な関係に於いては特に助けとなる。
【００１６】
掛け算累算器を更に汎用なマイクロプロセッサ内のマイクロコードとして実現することも可能であろうが、本発明で得られる性能上の利益は前記掛け算累算器が専用のハードウェア掛け算累算器であるシステムに於いて特に有用である。
【００１７】
本発明は多くの異なるビット長のアーキテクチャに基づくシステムの中で使用できるであろうが、本発明はＮが３２に等しいシステムに特に適している。この様なシステムでは命令内のビット空間は非常に貴重であり、６４ビットの結果が得られる追加的な精度はまれに必要となるだけである。この様にして、本発明は特に有効である。
【００１８】
本発明の別の特徴から見ると、本発明はＮビットデータ処理レジスタのレジスタバンクと、前記レジスタバンクに結合され、前記Ｎビットデータ処理レジスタ内に保持されている被演算子に対して掛け算累算演算処理を実行するための掛け算累算器とを有する装置を使用したデータ処理の方法を提供しており、前記方法は以下の手順を含む：
（ｉ）掛け算累算命令の第１クラスに応答して、第１データ処理レジスタ内に保持されているＮビット被演算子と第２データ処理レジスタ内に保持されているＮビット被演算子とを掛け算し、そして第３データ処理レジスタ内に保持されているＮビット被演算子を加算して、第４データ処理レジスタの中に格納されるＮビットの結果を算出し、前記第１、第２、第３および第４データ処理レジスタは掛け算累算命令の前記第１クラスの中のフィールドとして独立に指定され；そして
（ｉｉ）掛け算累算命令の第２クラスに応答して、第１データ処理レジスタ内に保持されているＮビット被演算子と第２データ処理レジスタ内に保持されているＮビット被演算子とを掛け算し、そして第３および第４データ処理レジスタ内に保持されている２Ｎビット被演算子を加算して、第３および第４データ処理レジスタの中に格納される２Ｎビットの結果を算出し、前記第１、第２、第３および第４データ処理レジスタは掛け算累算命令の前記第２クラスの中のフィールドとして独立に指定される。
【００１９】
本発明の上記、およびその他の目的、特徴並びに特長は添付図と関連して読まれる図示された実施例の以下の詳細な説明から明らかとなろう。
【００２０】
【実施例】
図１はデータ処理システム（集積回路の一部として形成されている）を図示し、メモリシステム１０４に結合されている処理装置コア１０２を含む。
【００２１】
処理装置コア１０２はレジスタバンク１０６、掛け算累算器１０８並びに書き込みデータレジスタ１１４とを含む。処理装置コア１０２はまた、命令パイプライン１１６、命令デコーダ１１８並びに処理装置コア１０２の残りの素子をメモリシステム１０４にリンクする読み込みデータレジスタ１２０をも含む。処理装置コア１０２の一部であるプログラム計数レジスタ１２２はメモリシステム１０４のアドレス指定をするように図示されている。プログラム計数器更新器１２４はプログラム計数レジスタ１２２内のプログラム計数値を、各々の命令が実行され新たな命令が命令パイプライン１１６に対してフェッチされなければならない時に更新するように動作する。
【００２２】
処理装置コア１０２はＮビットデータ通路（この場合は３２ビットデータ通路）を種々の機能ユニットの間に組み込んでいる。動作に際して、命令パイプライン１１６内の命令は命令デコーダ１１８でデコードされ、これは種々のコア制御信号を生成し、これらは処理装置コア１０２内の異なる機能素子に送られる。これらのコア制御信号に応答して、処理装置コア１０２の異なる部分は３２ビット処理演算、例えば３２ビット掛け算、３２ビット加算、異なる精度の掛け算累算演算、．．．を実施する。
【００２３】
レジスタバンク１０６は現行プログラム状態レジスタ１２６と保存プログラム状態レジスタ１２８とを含む。現行プログラム状態レジスタ１２６は処理装置コア１０２用の種々の条件および状態フラグとを保持する。これらのフラグは算術演算でのゼロ結果の発生を示すフラグ、桁上がり等と同様に、処理モードフラグ（例えば、システムモード、使用者モード、メモリアボートモード等）を含む。これらのフラグはプログラム命令の条件付き実行を、各命令の最初の４ビットの条件コードで指定されたパラメータに従って制御する。保存プログラム状態レジスタ１２８（これは格納されている複数のこの様なセーブされたプログラム状態レジスタの中の１つであろうが）は、処理モードの切り替えのきっかけとなる例外が発生したときに現行プログラム状態レジスタ１２６の内容を一時的に格納するために使用される。この様にして、例外処理がより高速にかつ、更に効率的に実行できる。
【００２４】
要求されるプログラム命令ワードがメモリシステム１０４から復元されると、これらは命令デコーダ１１８でデコードされ３２ビット処理を処理装置コア１０２の中で開始する。
【００２５】
図２は、３２＊３２＋３２−＞３２掛け算累算演算に応答する資源の使用を図式的に図示する。プログラム命令ワード３２は、条件コードフィールド３４を含み、これは命令が命令デコーダ１１８で実行されるのかスキップされるのかを示す条件を指定するパラメータを格納している。ビットフィールド３６は、命令ワード３２をこれが３２ビットの結果を算出する低精度掛け算累算演算であることを識別する。累算フラグ３８は１の値を有し、この命令ワード３２に対して累算演算が形成されることを示す。もしもこの累算フラグ３８が０の場合は、従って累算演算は実行されない。セット条件コードフラグ４０は現在のプログラム状態レジスタフラグが命令ワード３２を実行した際に更新されるべきか否かを指定する。
【００２６】
命令ワード３２はそれぞれフィールド４２、４４、４６および４８を指定する４つのレジスタを含む。もしも実行される演算が（Ａ＊Ｂ）＋Ｃ＝Ｄ、の様に表現される場合はレジスタフィールド４２は変数Ａを含むレジスタ（この場合Ｒ０）を指定し、レジスタフィールド４４は変数Ｂを含むレジスタ（この場合Ｒ２）を指定し、レジスタフィールド４６は変数Ｃを含むレジスタ（この場合Ｒ５）を指定しそしてレジスタフィールド４８はその中に結果Ｄが書き込まれるべきレジスタ（この場合Ｒ１０）を指定する。レジスタフィールド４２、４４、４６および４８の中に格納される値は、レジスタバンク１０６内のレジスタの読み込み並びに書き込みを制御するように作用する。この３２＊３２＋３２−＞３２命令の場合、全ての３つの入力変数レジスタおよび出力変数レジスタは独立に指定されるはずである。
【００２７】
図２に図示されている命令ワード３２はＮビット入力変数に演算を行い、Ｎビット出力を生成する掛け算累算命令の第１クラスに属すると考えることが出来る。この命令は４つの独立に指定されるレジスタを使用する。命令内のレジスタフィールドは１６ビットを占める（各々のレジスタフィールドはレジスタバンク１０６内の１６個のレジスタの内の１つを指定するように４ビット長である。）
【００２８】
図３は掛け算累算命令の第２クラスの命令ワード３２を図示し、この中で６４ビットの結果が掛け算累算演算（すなわち３２ｘ３２＋６４−＞６４）によって生成される。この場合、累算値はＣＤでありこれはそれぞれレジスタフィールド４８および４６で指定されたレジスタの中に格納されている。累算値ＣＤの最上位３２ビットＣはレジスタＲ７の中に格納され、累算値ＣＤの最下位３２ビットＤはレジスタＲ１１の中に格納されている。
【００２９】
命令ワード３２内の十分な空間は４つのレジスタを指定するだけなので、演算結果ＥＦはそこから累算値が取り出されたのと同一のレジスタ（Ｒ７，Ｒ１１）の中に書き込まれる。これは命令セット空間を節約し、かつ単一命令ワード３２で実行される精度を上げた６４ビット算術演算を可能とする。
【００３０】
処理装置コア１０２は２サイクルの初期化を実行し、各サイクル毎に２つのレジスタの読み込みを行う。これはレジスタバンク１０６に対して２つの読み込みポートしか持たない結果である。
【００３１】
図３の命令ワード３２は追加フラグ５０を含み、これはその算術が符号付きであるか符号無しであるかを指示する。
【００３２】
図４は掛け算累算器１０８で実行される掛け算命令の第１クラスを図示する。これらの命令は３２ビットの結果（すなわち３２ｘ３２−＞３２）を算出する。この場合、レジスタフィールド４６は使用されず任意の値を含むことが出来る。
【００３３】
図５は６４ビットの結果（すなわち３２ｘ３２−＞６４）が生成される掛け算命令の第２クラスを図示する。この場合、４つの全てのレジスタフィールド４２、４４、４６および４８はそこから入力変数が取り込まれるレジスタ並びにそこに６４ビットの結果であるＣＤのそれぞれ高位および低位部が書き込まれるレジスタを指定するために使用される。
【００３４】
図６および図７は掛け算累算演算実行用回路の異なる部分を図示する。
【００３５】
説明された回路は掛け算累算器を実現しこれが処理できるのは：
（１）Ｎビットの積を生成するためのＮビットとＮビットの数の掛け算；
（２）２Ｎビットの結果を生成するためのＮビットとＮビットの数の掛け算；
（３）Ｎビットの結果を得るように、ＮビットとＮビットの数を互いに掛け合わせ、そしてＮビットの累算値を加算する掛け算累算演算；そして
（４）２Ｎビットの結果を得るように、ＮビットとＮビットの数を互いに掛け合わせ、そして２Ｎビットの累算値を加算する掛け算累算演算である。
【００３６】
この回路はこれらの全てを、符号付きおよび符号無しの異なる方式で提供可能である。記述されている回路は例として特定のＮ＝３２のケースを使用している。（すなわち３２ｘ３２−３２および３２ｘ３２−＞６４掛け算、そして３２ｘ３２＋３２−＞３２並びに３２ｘ３２＋６４−＞６４掛け算累算である。）
【００３７】
用語”マルチプライア”は以下では掛け算回路並びに、掛け算をされるふたつの被演算子の一方のいずれにも使用される。そのどちらを意図しているかは、”回路”または”被演算子”の使用法または文脈から明らかとなろう。
【００３８】
Ｎビット被乗数ＤとＮビット乗数Ｒとの掛け算は通常はハードウェアでふたつの主手順として実行される：
（１）  被乗数Ｄの倍数  Ｘ０＊Ｄ，Ｘ１＊Ｄ，．．．，Ｘｋ＊Ｄの集合を（ａ）各々の倍数が容易に生成出来るように；（ｂ）Ｘ０＋Ｘ１＋．．．＋Ｘｋ＝Ｒとなり、これが  Ｘ０＊Ｄ，Ｘ１＊Ｄ，．．．，そしてＸｋ＊Ｄの合計が、希望する生成物Ｒ＊Ｄに等しくなることを保証するように形成する。
（２）  手順（１）で生成された被乗数倍数を互いに加算する。
【００３９】
段階（１）：被乗数倍数の形成
段階（１）は種々の方法で実行できる。最も単純なのはｋ＝Ｎ−１とし（従って全体でＮ個の被乗数倍数が存在する）、続いてＲのビットｉ（これはＲ［ｉ］またはＲｉと記述される）が０の場合はＸｉ＝０、そしてもしもＲ［ｉ］が１の場合はＸｉ＝２ｉ  とする。全てのＸｉがゼロまたは２の累乗であるので、被乗数倍数Ｘｉ＊Ｄは、ゼロを用いるかまたはＤを左にｉビットシフトすることで簡単に形成できる。
【００４０】
掛け算の結果はいずれの被演算子よりも長いので、Ｘｉ＊Ｄ被乗数倍数は積の全てのビットを決定するのに十分なビットで生成されるべきである：これは被乗数のビットをその左側に拡張することを必要とする。符号付きおよび符号無し被乗数の違いを取り扱うのはこの点である：符号付き被乗数はその符号ビットをコピーして拡張され、一方符号無し被乗数はゼロを付けて拡張される。この被乗数の拡張はしばしばゼロをひとつまたは符号ビットのコピーを付けるだけで物理的に実行され、この単独の追加ビットが残りのビット全てに対する（共通）値を表現するという理解のもとになされる。
【００４１】
この技法の元でなされる符号無しおよび符号付き乗数Ｒの間の違いの取り扱いは幾分手の込んだものである。最初に、Ｘｉの合計がＲの符号無し値になる場合を注目する：この技法は”当然”符号無し掛け算アルゴリズムとなる。従って必要なのは符号付き乗数の取り扱い方法である。この取り扱い方には多数の方法が存在し、その主なものは（ａ）Ｒが負の場合は特別の２Ｎ  ＊  Ｄを引き算することで最終結果を調整する；または（ｂ）もしもＲ［ｋ］＝１、すなわちＲが負の場合はＸｋを＋２ｋ  ではなく−２ｋ  とする。
【００４２】
もっと複雑で手の込んだ技術は修正ブース符号化法である。これはＮが偶数か奇数かによってふたつの少し異なる形式となる。もしもＮが偶数の場合は、ｋ＝Ｎ／２−１（従ってＮ／２個の被乗数倍数を形成することになる）とし、次のように定義する：
Ｘ０＝−２＊Ｒ［１］＋Ｒ［０］
そして：
ｉ＝１，２，．．．，ｋに対して
Ｘｉ＝（−２＊Ｒ［２＊ｉ＋１］＋Ｒ［２＊ｉ］＋Ｒ［２＊ｉ−１］）＊２（２＊ｉ）  
【００４３】
これを考察する別の方法は、乗数を二進小数点の後ろに一ビットＲ［−１］を拡張し、Ｒ［−１］をゼロに設定する（これは乗数の値を変更せずにそのまま残す）。従って上記の２番目の式は同様にｉ＝０の場合にも適用可能であり、この様な場合の上記第１番目の式を簡略化する、すなわちこの定義またはＲ［−１］を０とする事でＸ０の明らかに特別な場合が取り除かれる。
【００４４】
従ってＸｉの合計はＲの符号付きの値と等しくなる：
0003605181.tif 000002
【００４５】
さらに、各Ｘｉは２の累乗に群｛−２，−１，０，１，２｝の内のひとつの数を掛けたものであるから、値としてはゼロ、２の累乗または２の累乗のマイナスを取らなければならない。これは被乗数倍数Ｘｉ＊Ｄの形成を容易にする。これらは、正と同様に２の負の累乗をも取り扱わなければならないので先の方法と全く同じように容易と言うわけではないが、第２段階でＮ個ではなくＮ／２個の被乗数倍数を加算するだけで良いという大きな利点が得られる。負の被乗数倍数の形成は被乗数をシフトして対応する正の倍数を作り、次に”１の補数を取って１を加える”方法で負とすることにより実現できる、この段階では１の加算は実行しないで第２段階に回している。この様にして第２段階で加算され、Ｎ／２個の被乗数倍数および、Ｎ／２個の単一ビット（これらは対応する被乗数倍数が正の場合はゼロ、そしてそれが負の場合は１）が完了する；これもＮ個の全被乗数倍数に比較して改善である。
【００４６】
もしもＮが奇数の場合は、非常に似たことを行うが、Ｋ＝（Ｎ−１）／２としＸｉに対する式は：
Ｘ０＝−Ｒ［０］
そして：
ｉ＝１，２，．．，ｋに対して
Ｘｉ＝（−２＊Ｒ［２＊ｉ  ］＋Ｒ［２＊ｉ−１  ］＋Ｒ［２＊ｉ−２  ］）＊２（２＊ｉ−１）  
（ここでも、Ｘ０に対する式は特別な場合ではない：Ｒ［−１］＝Ｒ［−２］＝０と定義することにより、第２番目の式が正しい値を生成するように出来る。）
【００４７】
修正ブース符号化法は互いに加算する被乗数倍数の数を半分にするという事実と同様に別の特長も有する：これは当然のように乗数を符号無し数ではなく符号付き数として取り扱う。先の技法では符号付き乗数を特別な場合として取り扱わなければならなかった、その理由は符号無し数をいかに長くしたとしてもこれは負の符号が着いた値を保持することが出来ないためであった。その逆はより簡単である：Ｎ＋１ビット長またはそれを越える符号付き数はＮビット長の符号無し数（または実際Ｎビット長の符号付き数）を保持する事が出来る。従ってもしも我々が、３２ビットの符号付きおよび符号無し乗数を取り扱える掛け算回路を望むのであれば、例えば３３ビットまたはそれより長い修正ブース符号化器がこの作業を実行できるであろう：我々がしなければならないことはひとつまたは複数の追加ビットをその左端に付けて乗数を拡張し、この乗数が符号無しとして取り扱われる場合はこれらのビットをゼロとし、この乗数が符号付きとして取り扱われる場合は既存の符号をコピーする事である。
【００４８】
符号付きおよび符号無し被乗数の間の違いの処理は先と同様の技法で実施できる。
【００４９】
別の、さらに複雑で込み入った被乗数倍数を作り出す方法も存在し、複雑さが増すことと引き替えにそれらの個数を更に削減する。
【００５０】
段階（２）：被乗数倍数の加算
段階（１）の後、我々は互いに加算すべきかなり多数の被乗数倍数を持つことになる、例えば符号付きおよび符号無し３２ｘ３２ビット掛け算の両方を実行できる回路用の３３ビットまたは３４ビット修正ブース符号化器を使用する場合は１７個である。
【００５１】
最も簡単なやり方はこれらの内の２つを互いに足し算し、第３番目を最初のふたつの和に加え、第４番目を加算結果に加える、等々と最終合計値を得るまで続ける方法である。（ついでながら、各々の足し算は修正ブース符号化法で生成される付加ビットのひとつをも取り扱うことが可能であり、これを加算器の桁上げ入力として使用する。従って我々はこれらのビットを取り扱うのに特別な加算は必要ない。）これはアドバンストＲＩＳＣマシン有限会社のＡＲＭ６マイクロプロセッサで使用している技法に類似している。
【００５２】
ひとつの違いは、全ての被乗数倍数を一度に生成しないということである：代わりにここではそれらを必要に応じて生成する。その他の主な違いはこの技法の内での不規則性の処理である：最初の足し算を行う前に２つの被乗数倍数を生成しなければならないが、それ以外の足し算ではその各々を行う前に唯ひとつだけを生成すればよい。これは累算値として”小計”を初期化し、次にひとつの被乗数倍数を生成しそれを小計の中に加算することにより、この不規則を伴うことなく掛け算累算機能を提供するために利用可能であり（かつ利用している）。（単純な掛け算を実行する際に、我々は同様のことをその小計を累算値ではなくゼロに初期化する点は異なるが、行っている。）
【００５３】
これはまた先の段落の中で示唆されていたこともうまく行っている：実際修正ブース符号化器からの全ての追加ビットをひとつの足し算で取り扱うのは少なすぎるが、ここでは適当な数となっている。
【００５４】
この技術の主な問題は、それが含む桁上がりチェインが長いために、各々の足し算がかなりな時間を取ることである。これに対する良好な解決策は”桁上がり保存”足し算であり、これはふたつの数とひとつの桁上げビットを足し算してひとつの数を得る場合は長い桁上がりチェインを含むが、３つの数とひとつの桁上げビットとを足し算して２つの数を得る場合は必要は無いという観察から考え出された。特に、仮に今３つの数Ｘ［Ｎ：０］，Ｙ［Ｎ：０］と桁上がりビットＷがあるとすると、これらを２つの数Ｓ［Ｎ：０］およびＣ［Ｎ＋１：０］に減らすことが出来て、これは単純に３つの単独ビットを各ビット列毎に個別に足し算することにより同じ値の足し算となる：
【表１】
0003605181.tif 000003
【００５５】
ここで：
Ｃ［０］＝Ｗ  そして
ｉ＝０，１，．．．，Ｎ：に対して
（Ｃ［ｉ＋１］，Ｓ［ｉ］）はＸ［ｉ］，Ｙ［ｉ］およびＺ［ｉ］の２ビット和である。
【００５６】
計算は各列毎に個別に、桁上がりチェイン無しに行われるので、これは通常の足し算よりもかなり早い。（例えば、ＡＲＭ６マイクロプロセッサ上の掛け算では通常の足し算を使用しこれらの１つをクロックサイクル毎に実行する。桁上がり保存足し算を使用している集積回路ではクロックサイクル毎に４からそれ以上の足し算を実行する。）
ここにＪ個の足し算されるべき被乗数倍数があるとすると、この技術をＪ−２回使用して最終結果を得るために足し算しなければならない数として、これらを２つの数に削減する事ができる。この最終の足し算は通常の足し算を必要とするが、全体としてＪ−２回の桁上がり保存足し算とひとつの通常の足し算は、元のＪ−１回の足し算に比較してかなりの改善である。
【００５７】
通常の対処法は通常の加算器用のそれと類似している：最初に”桁上がり”と”保存”値とをそれらの合計値がゼロとなるように初期化する（例えば、これらを共にゼロに初期化する事により）、次に桁上がり保存足し算を使用して被乗数倍数への加算を１つずつ実行する。最後に、通常の足し算を用いて”桁上がり”と”保存”値の最終合計値を求める。先と同様に掛け算累算演算を自由に行うことが出来て、これは”桁上がり”と”保存”値とをそれらの和が累算値となるように、例えばそれらの１つをゼロにもう一方を累算値とするように初期化する事によって行える。実際、初期化する値が２つあるので、ふたつの累算値に足し算することが出来るが、これは非常に有用というわけでは無い：この第２累算値スロットの有効な使用方法は後で説明する。
【００５８】
上記の全ては我々が２Ｎビットの足し算を実行していることを仮定している、例えば３２ｘ３２の掛け算を実行する場合は、６４ビットの足し算を行うことになる。これはやっかいである、何故ならば典型的には結果としてデータ経路部分に他の残りのデータ経路の２倍の長さを必要とするためである。
【００５９】
しかしながら、足し算する値を調べてみると”関心のある”値はＮビットよりも僅かに多い部分にしか含まれていないことが分かる。例えば、Ｎが奇数の修正ブース符号化器でのＸｉ＊Ｄを考えてみる。Ｘｉは−２（２＊ｉ）  ，  −２（２＊ｉ−１）  ，  ０，２（２＊ｉ−１）  および２（２＊ｉ）  ，  の内の一つであり、これは下記のいずれか一つのＸｉ＊Ｄに対応する：
【表２】
0003605181.tif 000004
【００６０】
先頭Ｎ−２＊ｉビットも後尾２＊ｉ−１ビットも非常に関心があるわけでは無い。特に桁上げビットを全てがゼロとなるように後尾２＊ｉ−１ビットに加えて、同じ桁上げを各々の場合に中間Ｎ＋１ビットに加えることが出来る、すなわち上記を次のように置き換えることが出来る
【表３】
0003605181.tif 000005
【００６１】
次に後尾２＊ｉ−１ビットに対しては桁上げ保存足し算をする必要が無いことが分かる：２つの値とゼロとの桁上げ保存足し算を行うよりもむしろ、ふたつの値を変更せずにそのまま残すことが出来る。更に、もしも”保存”および”桁上げ”の先頭Ｎ−２＊ｉビットが全て同一である場合は、先頭Ｎ−２＊ｉ列足し算の全ては同一となり、従って我々はそれら全ての評価を行うのにひとつの回路のみを必要とする。その結果として、我々は丁度Ｎ＋２列の加算器（中間Ｎ＋１ビット用のＮ＋１と先頭Ｎ−２＊ｉビット用のひとつ）が用意されれば全てを実行できる：
（ａ）その先頭Ｎビットが同一の”保存”値から始める；
（ｂ）その先頭Ｎビットが同一の”桁上げ”値から始める；
（ｃ）被乗数倍数をＸ０＊Ｄ，Ｘ１＊Ｄ，Ｘ２＊Ｄ，．．．，ｘｋ＊Ｄの順番に、各々の足し算がその先頭に前回のものより少ない数の同一ビットを必要
とするように足し算する；そして
（ｄ）我々が”関心を有する領域”を各繰り返し毎に左に２ビットシフトし、後尾の端から脱落するビットを格納する。計算の最後に、これらのビットが最終”桁上げ”および”保存”値の低端を形成し、一方最終の”関心を有
する領域”がそれらの高端を形成するはずである。
【００６２】
これは我々が掛け算器の主要部をそのデータ経路の幅が、その幅の２倍ではなく、少し”出っ張った”もので実現することを可能としている。最終の足し算だけは未だ２倍幅で無ければならないが、単一幅の加算器を２つ使用し、第１足し算からの桁上げビットを第２足し算の繰り入れビットとして使用することで実施できる。
【００６３】
制約条件の中でも、最後の２つは回路を正しく実現する事に関するものである。しかしながら、最初の２つはいずれの累算値もそれが符号付きの場合は最大Ｎビット幅であり、約２Ｎビット幅では無いことを意味している。累算値に対するこの制約を回避し、例えば３２ｘ３２＋３２の代わりに３２ｘ３２＋６４掛け算累算命令を実行するための技法が以下に説明されている。
【００６４】
任意の個別の掛け算器はハードウェアで構成された倍数の段階を含む事に注意されたい、これは被乗数倍数を生成し現状の”桁上げ”および”保存”形式の中への桁上げ保存足し算を実行する（このハードウェアを以降”掛け算器列”と呼ぶ）。極端な例では、各々の繰り返し用の個別の掛け算器列を具備した全掛け算器配列が存在する。
【００６５】
一方では、全ての繰り返しを取り扱う唯ひとつの掛け算器列を具備した、完全に繰り替えし実行掛け算器も存在する。この中間として、ひとつより多い複数列を具備した繰り返し方式のものも存在する。
【００６６】
桁上げ保存形式の初期化
上記のように、我々は桁上げ保存形式の”桁上げ”と”保存”の両方を初期化することが可能である。これらの内の１つは累算値用に必要である。もう一方は被乗数倍数の内のひとつとして使用できるであろう。これに関する主な問題は、桁上げ保存形式初期化装置が被乗数倍数生成器を含まなければならないことを意味している。これはスペースを消費する：更に重要なことは、これが余分の初期化遅れを引き起こすことである。
【００６７】
この余分の遅れの大きさは、関係する被乗数倍数の生成の複雑さに依存する。先に示されている修正ブース符号化で生成されるＸｉに関する式を見ると、ひとつは特に単純である、すなわちＮが奇数の場合、Ｘ０＝−Ｒ［０］である。勿論通常我々はＮが偶数の場合にも関心がある；しかしながら、先に見たように符号付きおよび符号無しＮビット数値の掛け算の要求を処理する良い方法は、実際（Ｎ＋１）ビット数値を掛け算することである。
【００６８】
これらの考察から以下の符号付きおよび符号無し変数の両方を取り扱い、修正ブース符号化および桁上げ保存足し算を使用し、Ｎが偶数の場合のＮビットとＮビットとの掛け算累算に対する初期化方法が導かれる：
内部掛け算被演算子Ｒ［Ｎ：０］を次のように初期化する：
0003605181.tif 000006
”桁上げ”および”保存”値の内の１つを供給されるＮビットまたは２Ｎビット累算値（それが符号無しかまたは符号付きかに基づいてゼロまたは符号ビットのコピーで拡張されている。）に初期化する
【００６９】
”桁上げ”および”保存”値の内の残りのもう一方をＲ［０］＝０の場合はゼロに、そしてＲ［０］＝１の場合は供給された被乗数にマイナスを付けたもの（状況に応じて符号付きまたは符号無しとして取り扱われる）に初期化される。
【００７０】
この最後のものは供給された被乗数のマイナス、すなわち２の補数を生成しなければならないので少し複雑に見える。その代わりに１の補数を形成し１を加えるという便法を使用する方が都合が良いであろう。問題は：いつこの１を加算するかである。
【００７１】
良い答えは掛け算の最後に於いてである。その理由は、桁上げ保存形式への最後の足し算は現在の所、その”桁上げ”および”保存”部を互いに足し算するだけで良いからである。ほとんどの加算器ではふたつの数と桁上げビットとを足し算するので、従って桁上げビットは使用されていない。桁上げビットをＲ［０］と等しく設定する事により、Ｒ［０］＝１の際の初期化中に被乗数の２の補数と１の補数を使用することの間の違いを補償することが出来る。従って我々は下記の初期化法を得る：
内部乗数被演算子Ｒ［Ｎ：０］を下記のように初期化する：
0003605181.tif 000007
”桁上げ”および”保存”値の１つを供給されたＮビットまたは２Ｎビット累算値（適当に符号付きまたは符号無しとして取り扱われる）で初期化する。
”桁上げ”および”保存”値の残りの１つを、Ｒ［０］＝０の場合はゼロに、Ｒ［０］＝１の場合は供給された被乗数（適当に符号付きまたは符号無しとして取り扱われる）のビット毎に反転したもの（すなわち１の補数）に初期化する。
最終足し算用の繰り越しビットをＲ［０］に設定する。
【００７２】
長い累算値の取り扱い
先に述べたように、掛け算の第ｉ段階における全ての先頭Ｎ−２＊ｉビットを単一ビットで表現できる場合は、累算値の長さはＮビットにしかならない。もしも累算値がもっと長い場合は、これにまともに対処するためにデータ経路の幅を増やす必要がある。
【００７３】
先頭Ｎ−２＊ｉビットの中で、我々が最初に必要とするのは同一ではないビットを含むことの出来る”桁上げ”および”保存”値の１つであることに注意されたい：その他のものは、被乗数倍数の先頭Ｎ−２＊ｉビットと同様に、全て同一ビットを含むことが出来る。不幸にして、先頭桁上げ保存足し算を行った後では、”桁上げ”および”保存”の両方ともそれらの先頭ビットの中に同一ではないビット列を含む可能性がある。もしもこれが発生しない場合で、我々が足し算によって累算値の先頭ビットが変更されずに残り、そして全てのその他の値が同一ビット列として残るように構成できれば、我々は再び主作業をほぼＮビット幅のデータ経路で繰り返し行うことが出来る：先の事象の状態からの唯一の違いは、繰り返し演算毎に主計算に対して累算値の２ビットを供給しなければならない点である。
【００７４】
これに対処する方法は、単純な桁上げ保存”各々の列に３ビットを加算”技術を修正することである。上記と同様の方法で、我々は”桁上げ”および”保存”値を３つの領域に分割する：
（ａ）”低”領域、ここでは”桁上げ”および”保存”値に対して変更は加えられない。Ｘｉ＊Ｄをこれらに加算した後、この領域はＬｉビットを含み、ここでＮが奇数の場合はＬｉ＝２＊ｉ＋１（先に図示した通り）、そしてＮが偶数の場合はＬｉ＝２＊ｉ＋２である。Ｎが偶数の場合は、これはＸｉ＊Ｄが加算される前はＬｉ＝２＊ｉと言って表現するとも出来る；Ｎが奇数の場合もまたＸｉ＊Ｄが加算される前はＬｉ＝２＊ｉ−１と言って表現出来る、もしもｉ＝０に対して特別ケースが定められていればの話である（例えば、Ｘ０＊Ｄの加算を、先に述べたのと同様初期化に組み込む等）；ＳＬ［Ｌｉ−１：０］およびＣＬ［Ｌｉ−１：０］はそれぞれ低”桁上げ”および”保存”ビットを表す。
（ｂ）”中間”または”活性”領域、ここでは主たる桁上げ保存足し算が実行される。この領域はＮ＋１ビットを含み、それぞれ”桁上げ”および”保存”値としてＳ［Ｎ：０］およびＣ［Ｎ：０］と表される。
（ｃ）”高”領域、ここでは”保存”値は累算値のここまでは未使用のビットを含み、”桁上げ”値は単にＣ［Ｎ］のコピー列である。桁上げ保存形式の中にＸｉ＊Ｄを加算する前、この領域は２＊（ｋ−１）＋２ビット長、すなわち我々が活性領域の中に加算毎に２ビットで持ち込みたい累算ビットの数である。（ｋは最後のＸｉのインデックスであることを想起されたい。）
【００７５】
確認すると、”桁上げ”および”保存”値の全長は次のようになる：
0003605181.tif 000008
従って我々は当然、長さ２Ｎ＋１ビットの累算値Ａ［２Ｎ：０］を取り扱うことになる。（勿論我々はもっと短い累算値（例えばＮビット）を、必要に応じてそれらにゼロ拡張または符号拡張を施すだけで取り扱うことが可能である；また我々はより長い累算値を取り扱うことも可能であるが、余分なビットは主演算で全く変更されることなく、最終足し算の間に単に対応する”桁上げ”値ビット（すなわちＣ［Ｎ］のコピー）に加算される必要があるだけである。）
【００７６】
従って、我々がＸｉ＊Ｄを桁上げ保存形式の中に加算する前の、”桁上げ”および”保存”値は次のようになる：
【表４】
0003605181.tif 000009
【００７７】
次に、被乗数倍数がどの様になっているかを調べる必要がある。最初にＮビットの符号付きまたは符号無し倍数Ｄ［Ｎ−１：０］から始める、これに符号拡張またはゼロ拡張をそれぞれ施して、（Ｎ＋１）ビット符号付き倍数Ｄ［Ｎ：０］を形成する。上記の様に被乗数倍数を形成すると、下記の形式の被乗数倍数を、”ブース桁”−２＊Ｒ［２＊ｉ＋１］＋Ｒ［２＊ｉ］＋Ｒ［２＊ｉ−１］（Ｎが偶数の場合）または−２＊Ｒ［２＊ｉ］＋Ｒ［２＊ｉ−１］＋Ｒ［２＊ｉ−２］（Ｎが奇数の場合）に応じて得る：
【表５】
0003605181.tif 000010
ここで、Ｉ［Ｎ：０］はＤ［Ｎ：０］をビット毎に反転したもの（または１の補数）である。
【００７８】
これらすべてはＸ［Ｎ＋１：０］およびＸＣという値に対して次の形式となる：
【表６】
0003605181.tif 000011
従って我々が実行したいと望む加算の形式は：
【表７】
0003605181.tif 000012
【００７９】
我々は同じ形式で”桁上げ”および”保存”値を纏めたいのであるが、ｉでひとつ大きく、また従ってＬｉで２つ大きくなる。処理過程で我々はＳ［Ｎ：０］およびＣ［Ｎ：０］の新たな値を生成しようとしており、これはそれぞれＳ’［Ｎ：０］およびＣ’［Ｎ：０］と呼ばれる。我々はまたＳＬ［Ｌｉ＋１：Ｌｉ］も生成し、これはＳＬ［］の新たな２ビットであるが、これは既存のＳＬ［Ｌｉ−１：０］の外乱とはならない。同様にわれわれは新たな２ビットＣＬ［Ｌｉ＋１：Ｌｉ］を生成するが、これは既存のＣＬ［Ｌｉ−１：０］の外乱とはならない。最後にＡ［２Ｎ：Ｌｉ＋Ｎ＋１］の最下位２ビットが消費される、従って我々は修正桁上げ保存足し算が下記の形式を生成する事を欲する：
【表８】
0003605181.tif 000013
【００８０】
我々が実行させたい足し算をこれに整合させるために、我々は我々の修正桁上げ保存加算が下記の形式であれば良いことが分かる：
【表９】
0003605181.tif 000014
【００８１】
我々は直ちに”低”領域を除去できる、何故ならばこの領域が最終合計値には何の変化も与えないためである。同様に、線の上下の同じ位置に現れるビット、Ａ［２Ｎ：Ｌｉ＋Ｎ＋３］を除去する事も可能である：これらが最終の形に変更を与えないことも明白だからである。この後我々の修正桁上げ保存加算が下記の形式を取らなければならないことが分かる：
【表１０】
0003605181.tif 000015
【００８２】
次に、通常の桁上げ保存加算を”活性”領域ならびにその下の二つの遷移ビットに対して行う。次の操作を行うことにより：
ＣＬ［Ｌｉ］                                ＝    ＸＣ；
（ＣＬ［Ｌｉ＋１］，ＳＬ［Ｌｉ］）          ＝    Ｓ［０］，Ｃ［０］およびＸ［０］の２ビット和；
（Ｃ’［０］，ＳＬ［Ｌｉ＋１］）            ＝    Ｓ［１］，Ｃ［１］およびＸ［１］の２ビット和；
ｉ＝２，３，．．．．Ｎ  に対して：
（Ｃ’［ｉ−１］，Ｓ’［ｉ−２］            ＝    Ｓ［ｉ］，Ｃ［ｉ］およびＸ［ｉ］の２ビット和；
線の下側のＳ’［Ｎ−２：０］，ＳＬ［Ｌｉ＋１］，ＳＬ［Ｌｉ］，Ｃ’［Ｎ−１：０］，ＣＬ［Ｌｉ＋１］およびＣＬ［Ｌｉ］とが、最終合計値に対して線の上側のＳ［Ｎ：０］，Ｃ［Ｎ−１：０］，Ｘ［Ｎ：０］，ＸＣ  およびＣ［Ｎ］の”活性”領域コピーと同じ寄与をする事を保証出来る。従ってここでこれら全てを、ＸＣを含む線上の全てのゼロといっしょに除去することが可能であり、残った修正桁上げ保存加算は次の形式を取らねばならない：
【表１１】
0003605181.tif 000016
【００８３】
この時点で我々は、この残りの合計に対していくつかの数学的変更を加える。最初に、その第２行を下記の２行の合計で置き換えることが出来る：
１，．．．，１      １        １
０，．．．，０      ０        ＮＯＴ（Ｃ［Ｎ］）
【００８４】
証明：もしもＣ［Ｎ］が１であれば、これは全てが１の行または全てが０の行の合計であり、これは全てが１の行となる。逆に、もしもＣ［Ｎ］が０の場合は、これは全てが１の行とその右端のひとつが１の合計となる。これは全てが０の行プラスその左端の桁上げを作り出す。桁上げは無視される、何故ならばそれは我々が加算を行っている領域の外側だからである。従っていずれの場合も、合計はＣ［Ｎ］のコピーの行となる。
【００８５】
同様に、第３行は下記２行の合計で置き換えることが出来る：
１，．．．，１      １        １
０，．．．，０      ０        ＮＯＴ（Ｘ［Ｎ＋１］）
【００８６】
これは要求される桁上げ保存加算を次の形式に変更する：
【表１２】
0003605181.tif 000017
【００８７】
次に我々は１で構成された２つの行を加算する、ここでも桁上げは無視する、何故ならばそれは我々が加算を行っている領域の外側だからである。これは要求される桁上げ保存加算を次の形式に変更する：
【表１３】
0003605181.tif 000018
【００８８】
この時点で、次の操作を行うとすると：
（Ｓ’［Ｎ］，Ｓ’［Ｎ−１］）      ＝        Ａ［Ｌｉ＋Ｎ＋１］，ＮＯＴ（Ｃ［Ｎ］）およびＮＯＴ（Ｘ［Ｎ＋１］）  の２ビット和
【００８９】
我々はこれら全てのビットを要求される加算から、いくつかのゼロと共に除去することが分かり、以下が残る：
【表１４】
0003605181.tif 000019
【００９０】
最後に、次の操作を行うとすると：
Ｃ’［Ｎ］        ＝      ＮＯＴ（Ａ［Ｌｉ＋Ｎ＋２］）
この加算合計の残りの部分を、引数の逆で解き、これは我々が全てがＣ［Ｎ］の行を全てが１の行並びにその右端にＮＯＴ（Ｃ［Ｎ］）のみを含む行で置き換えられることを示している。
【００９１】
最終的な結論：下記の一連の操作を実行する：
ｉ＝２，３，．．．．，Ｎ    に対して
ＣＬ［Ｌｉ］                                ＝ＸＣ；
（ＣＬ［Ｌｉ＋１］，ＳＬ［Ｌｉ］）          ＝Ｓ［０］，Ｃ［０］  及び  Ｘ［０］の２ビット和
（Ｃ’［０］，ＳＬ［Ｌｉ＋１］）            ＝Ｓ［１］，Ｃ［１］  及び  Ｘ［１］の２ビット和
（Ｃ’［ｉ−１］，Ｓ’［ｉ−２］）          ＝Ｓ［ｉ］，Ｃ［ｉ］  及び  Ｘ［ｉ］の２ビット和
（Ｓ’［Ｎ］，Ｓ’［Ｎ−１］）              ＝Ａ［Ｌｉ＋Ｎ＋１］，ＮＯＴ（Ｃ［Ｎ］）及び  ＮＯＴ（Ｘ［Ｎ＋１］）  の２ビット和
Ｃ’［Ｎ］                                  ＝ＮＯＴ（Ａ［Ｌｉ＋Ｎ＋２］）
我々は変更された桁上げ保存加算を我々が要求する演算に対して実施できる：
【表１５】
0003605181.tif 000020
【００９２】
従って、もしも我々が”桁上げ”および”保存”値を正しく初期化出来れば、我々は２Ｎビット累算値を備えたＮビットとＮビットの掛け算累算演算を、初期化し、被乗数倍数への加算を上記の修正された桁上げ保存加算を用いて行い、そして最終足し算を桁上げ保存値に対して実行することにより実施することが可能である。
【００９３】
次に掛け算器の例を説明する、これは上記を使用して３２ｘ３２−＞６４掛け算と、３２ｘ３２＋６４−＞６４掛け算累算演算を、符号付きおよび符号無しの両方で算出するものである。３２ｘ３２−＞３２と、３２ｘ３２＋３２−＞３２演算は、下位３２ビットが決定された時点で掛け算を早めに終了するか、累算値の初期化を下位のみに行うことで生成できる。
【００９４】
この例では図示されていない更に別の可能な改善は：
＊  早めの終了、これは基本的に残りの全ての被乗数倍数がゼロになった時点の検出（従って更なる加算は実際上必要とされない）を含み、続いて”低”、”活性”および”高”領域内のビットの無駄な再構成の代わりに、正しい最終加算を生成するための何か別のことを実行する。
＊  この回路内に最終加算器を用意する必要を、データ経路上に存在する別の加算器、例えばＡＬＵを使用することにより無くする。
＊  ”保存低ラッチ”は最後尾から２ビット／乗数行までを満たし、一方”累算値高ラッチ”は最後尾からその同じ所まで空であるという事実をうまく利用し、同一の物理的レジスタを用いて、２つの値を保持することが可能である。最初にこれは累算値の高位部分を含む；最終的にこれは”保存”値の低位部分を含む；その間は、未消費の高累算値ビットと生成途中の”保存”ビットとを含む。
これは回路にとって有益な改善である。
掛け算器は下記の入力を使用する：
0003605181.tif 000021
【００９５】
回路はＲＥＳＵＬＴ［６３：０］をその結果として生成する。
【００９６】
この掛け算器の基本ブロック図が図６並びに図７に示されている（分かり易くするために制御信号は図示されていない）：
【００９７】
この掛け算器は、ＭＰＬＩＥＲ［３１：０］＊ＭＣＡＮＤ  ［３１：０］＋ＡＣＣＶＡＬ［６３：０］を５サイクルの間に計算し、種々のブロックは各サイクル毎に下記の機能を実行する：
0003605181.tif 000022
サイクル２−５  ：  変化無し
桁上げ保存ラッチＡ
サイクル１−３：フェーズ２で、Ｓ０［３２：０］およびＣ０［３２：０］がそれぞれＳ６［３２：０］並びにＣ６［３２：０］からロードされる。
サイクル４−５：変化無し。
桁上げ保存ラッチＢ
サイクル１−４：フェーズ１で、Ｓ４［３２：０］およびＣ４［３２：０］がそれぞれＳ３［３２：０］並びにＣ３［３２：０］からロードされる。
サイクル５    ：変化無し。
0003605181.tif 000023
サイクル５：変化無し
ここでＢｏｏｔｈＥｎｃ機能は下記の表で指定される：
【表１６】
0003605181.tif 000024
【００９８】
掛け算器行１，２，４および５
全てのサイクルに於いて、掛け算器行ｋは入力Ｄ［３２：０］，Ｂｋ［４：０］，ＡＨｋ［１：０］，Ｓｋ［３２：０］およびＣｋ［３２：０］をとり、下記の式に従って出力Ｓ（ｋ＋１）［３２：０］，Ｃ（ｋ＋１）［３２：０］，ＳＬｋ［１：０］およびＣＬｋ［１：０］を生成する：
【００９９】
最初にマルチプレクサを用い、下記の表に従ってＸ［３３：０］並びにＸＣを生成する：
【表１７】
0003605181.tif 000025
次に
0003605181.tif 000026
【０１００】
これらは内部信号ＡＣＣＨＩ［３１：０］を含む
0003605181.tif 000027
0003605181.tif 000028
マルチプレクサＣ
サイクル１−４：  ＣＩＮ＝Ｒ［０］
サイクル５    ：  ＣＩＮ＝ＮＥＷＣ
桁上げラッチ
サイクル１−３：変化無し
サイクル４    ：ＮＥＷＣ＝ＣＯＵＴ
サイクル５    ：変化無し
最終加算器
全てのサイクルに於いて：（ＣＯＵＴ，ＳＵＭ［３１：０］）＝ＳＦ［３１：０］，ＣＦ［３１：０］およびＣＩＮ  の３３ビット和。
結果ラッチ
サイクル１−３：変化無し
サイクル４    ：ＲＥＳＵＬＴ［３１：０］    ＝ＳＵＭ［３１：０］
サイクル５    ：ＲＥＳＵＬＴ［６３：３２］  ＝ＳＵＭ［３１：０］
【０１０１】
図６並びに図７は共に、Ｎビット被乗数（ＭＣＡＮＤ［］）とＮビット乗数（ＭＰＬＩＥＲ［］）とを掛け算し、続いて２Ｎビットの累算値（ＡＣＣＶＡＬ［］）を加算するための、掛け算累算回路を図示しており、この例ではＮ＝３２である。Ｎビット乗数は乗数ラッチ２の中に取り込まれ、Ｍビット被乗数が被乗数ラッチ４の中に取り込まれる。２Ｎビット累算値の下位部分が、桁上げ保存初期化器６に送られ、２Ｎビット累算値の上位部分は累算値上位ラッチ８に送られる。桁上げ保存初期化器６はＮビット被乗数（Ｄ［］）を受け取り、これのビットのビット毎反転またはゼロを、それぞれ乗数ラッチ２の最下位ビットの値が１であるかまたはゼロであるかに応じて、生成する。この結果はマルチプレクサＡ１０に送られ、桁上げ値または保存値のいずれかひとつとなる。桁上げ値または保存値のもう一方は累算値の最下位ビットを構成する。
【０１０２】
Ｎビット乗数はまた、一連のブースエンコーダ１２にも送られ、これは修正されたブース被加数を生成し、これは後続の掛け算器行のそれぞれひとつに送られる。
【０１０３】
図７に示されるように、掛け算器行１４，１６，１８，２０の順番は各々先に説明した掛け算器アルゴリズムを実行するものと仮定している。この掛け算器アルゴリズムは各々の繰り返し演算に於いて、累算値の２ビットを組み入れている。各サイクルでの各々の掛け算器行１４，１６，１８，２０への入力は、ブース桁（Ｂ１［］，Ｂ２［］，Ｂ４［］，Ｂ５［］）、累算値高ラッチ８の中に格納されている累算値からのビット、被乗数ラッチ４からのＮビット被乗数のビット並びに直接または間接的に先に実行された掛け算器行からの保存値および桁上げ値である。
【０１０４】
各々の掛け算器行からの出力は、以降の繰り返し演算ではもはや変化しない最下位ビット（ＳＬ，ＣＬ）と、現行の保存値および桁上げ値である。これらの最下位ビットは桁上げ低ラッチ２４の中に累算される。保存値並びに桁上げ値（Ｓ６［］，Ｃ６［］）は桁上げ保存ラッチＡ２２とマルチプレクサＡ１０を経由して、最初の掛け算器行１４に送り返される。最後の掛け算繰り返し演算が完了すると、最後の掛け算器行２０および桁上げ保存低ラッチ２４からの桁上げ値並びに保存値はそれぞれ最終加算器２６に送られ、ここでそれらは２サイクルにわたって加算され（桁上げ保存低ラッチ２４からの値は最終加算器２６に第１サイクルで送られ、最終掛け算器行２０からの値は第２サイクルで送られる）、その結果は結果ラッチ２８の中に格納される。マルチプレクサＣ３０は１の補数を取る初期化の時に出た桁上げビットＲ［０］を最終加算器２６の第１加算サイクル中に供給し、最終加算器の第１と第２サイクルとの間では必要に応じて任意の桁上げビットを供給するように作用する。
【０１０５】
本発明の例示を目的とした実施例を添付図を参照してここに詳細に説明してきたが、本発明はこれらの詳細な実施例に制限されるものではなく、当業者によって種々の変更並びに修正を添付の特許請求の項に定義されている本発明の範囲並びに精神から逸脱することなく行えることは理解されよう。
【図面の簡単な説明】
【図１】集積回路マイクロプロセッサ内の機能ユニットを図示する。
【図２】レジスタ資源の使用と、種々のプログラム命令ワードに応答して実行される算術演算とを図式的に図示し、３２＊３２＋３２−＞３２掛け算累算演算に応答する資源の使用を図示する。
【図３】レジスタ資源の使用と、種々のプログラム命令ワードに応答して実行される算術演算とを図式的に図示し、３２＊３２＋６４−＞６４掛け算累算演算に応答する資源の使用を図示する。
【図４】レジスタ資源の使用と、種々のプログラム命令ワードに応答して実行される算術演算とを図式的に図示し、３２＊３２−＞３２掛け算演算に応答する資源の使用を図示する。
【図５】レジスタ資源の使用と、種々のプログラム命令ワードに応答して実行される算術演算とを図式的に図示し、３２＊３２−＞６４掛け算演算に応答する資源の使用を図示する。
【図６】掛け算累算器ユニットの部分を図示し、データ取り込み部分を主として図示する。
【図７】掛け算累算器ユニットの部分を図示し、演算処理部分を主として図示する。
【符号の説明】
２  乗数ラッチ
４  被乗数ラッチ
６  桁上げ保存初期化器
１０  マルチプレクサ
１２  ブースエンコーダ
１４，１６，１８，２０  掛け算器行
２６  最終加算器
２８  結果ラッチ
３２  命令ワード
１０２  処理装置コア
１０４  メモリシステム
１０６  レジスタバンク
１０８  掛け算累算器
１１４  書き込みデータレジスタ
１１６  命令パイプライン
１１８  命令デコーダ
１２０  読み込みデータレジスタ
１２２  プログラム計数レジスタ
１２４  プログラム計数器更新器
１２６  現行プログラム状態レジスタ
１２８  保存プログラム状態レジスタ
【図１】
0003605181.tif 000029
【図２】
0003605181.tif 000030
【図３】
0003605181.tif 000031
【図４】
0003605181.tif 000032
【図５】
0003605181.tif 000033
【図６】
0003605181.tif 000034
【図７】
0003605181.tif 000035