ブースの乗算アルゴリズム

ブースの乗算アルゴリズムは、 2の補数表記の2つの符号付き2進数を乗算する乗算アルゴリズムです。このアルゴリズムは、1950年にロンドンのブルームズベリーにあるバークベック大学で結晶学の研究をしていたアンドリュー・ドナルド・ブースによって発明されました。^{[1]ブースのアルゴリズムは}、コンピュータアーキテクチャの研究で興味深いものです。

ブースのアルゴリズムは、最下位ビットの下の暗黙のビットy ₋₁ = 0 を含め、符号付き 2 の補数表現の 'N' ビット乗数 Y の隣接するビットペアを調べます。各ビット y i （ i は 0 から N − 1 まで）について、ビットy iとy i ₋₁が考慮されます。_これら2つ_のビットが等しい場合、積累算器Pは変更されません。y _i = 0 かつ y _{i −1} = 1 の場合、被乗数 x 2 ⁱがPに加算されます。 y _i = 1 かつy _i−1 = 0の場合、被乗数 x 2 ^{i が}Pから減算されます。 Pの最終的な値は、符号付き積です。

被乗数と積の表現は指定されていません。通常、これらは乗数と同様に 2 の補数表現ですが、加算と減算をサポートする任意の数値システムでも機能します。ここで述べたように、手順の順序は決まっていません。通常、i = 0から始めて、LSBからMSBに進みます。次に、 2 ⁱによる乗算は、通常、手順間でPアキュムレータを右に増分シフトすることによって置き換えられます。下位ビットはシフトアウトされ、後続の加算と減算はPの上位Nビットに対してのみ実行できます。^[2]これらの詳細には多くのバリエーションと最適化があります。

このアルゴリズムは、乗数内の 1 の文字列を文字列の末尾の上位の +1 と下位の -1 に変換するとよく説明されます。文字列が MSB を通過すると、上位の +1 はなくなり、最終的な効果は適切な値の負として解釈されます。

ブースのアルゴリズムは、 2 つの所定の値AとSのいずれかを積Pに繰り返し加算し (通常の符号なし 2 進加算を使用) 、次にPに対して右方向の算術シフトを実行することによって実装できます。mとr をそれぞれ被乗数と乗数とし、xとy をmとrのビット数を表します。

1. AとSの値、およびPの初期値を決定します。これらの数値はすべて、長さが ( x  +  y  + 1) に等しくなければなりません。
   1. A: 最上位（左端）ビットをmの値で埋めます。残りの（y  + 1 ）ビットをゼロで埋めます。
   2. S: 最上位ビットに(− m )の値を2の補数表記で入力します。残りの( y  + 1)ビットにはゼロを入力します。
   3. P: 最上位のxビットをゼロで埋めます。その右側にrの値を追加します。最下位 (右端) ビットをゼロで埋めます。
2. Pの最下位（右端）2ビットを決定します。
   1. 01 の場合は、 P  +  Aの値を求めます。オーバーフローは無視します。
   2. 10 の場合は、 P  +  Sの値を求めます。オーバーフローは無視します。
   3. 00 の場合は何もしません。次のステップでP を直接使用します。
   4. 11 の場合は何もしません。次のステップでP を直接使用します。
3. 2 番目の手順で取得した値を 1 桁右に算術シフトします。Pがこの新しい値に等しくなるようにします。
4. 手順 2 と 3 をy回繰り返します。
5. Pから最下位（右端）ビットを削除します。これはmとrの積です。

3 × (−4) を求めます。ここで、m = 3、r = −4、x = 4、y = 4 です。

• m = 0011、-m = 1101、r = 1100
• A = 0011 0000 0
• 1101 0000 0 秒
• 0000 1100 ...
• ループを 4 回実行します。
  1. P = 0000 110 0 0。最後の2ビットは00です。
     • P = 0000 0110 0。算術右シフト。
  2. P = 0000 011 0 0。最後の2ビットは00です。
     • P = 0000 0011 0。算術右シフト。
  3. P = 0000 001 1 0。最後の2ビットは10です。
     • P = 1101 0011 0. P = P + S.
     • P = 1110 1001 1. 算術右シフト。
  4. P = 1110 100 1 1。最後の2ビットは11です。
     • P = 1111 0100 1. 算術右シフト。
• 積は1111 0100で、-12です。

上記の手法は、被乗数が表現できる最大の負の数である場合（たとえば、被乗数が 4 ビットの場合、この値は -8 になります）、不十分です。これは、S を設定するために必要な被乗数の否定 -m を計算するときにオーバーフローが発生するためです。この問題の 1 つの修正方法は、A、S、および P をそれぞれ 1 ビット拡張し、それらが同じ数を表すようにすることです。つまり、以前は -8 は 1000 によって 4 ビットで表現されていましたが、現在は 1 1000 によって 5 ビットで表現されます。これは、A と S のビットを決定する際に変更を加えた、上記の実装に従います。たとえば、元々 A の最初のxビットに割り当てられていたmの値は、 x +1 ビットに拡張され、A の最初のx +1 ビットに割り当てられます。以下では、被乗数と乗数に 4 ビットを使用して -8 を 2 で乗算することにより、改善された手法を示します。

• 1 1000 0000 0
• 0 1000 0000 0
• 0 0000 0010 ...
• ループを 4 回実行します。
  1. P = 0 0000 001 0 0。最後の2ビットは00です。
     • P = 0 0000 0001 0. 右シフト。
  2. P = 0 0000 000 1 0。最後の2ビットは10です。
     • P = 0 1000 0001 0. P = P + S.
     • P = 0 0100 0000 1. 右シフト。
  3. P = 0 0100 000 0 1。最後の2ビットは01です。
     • P = 1 1100 0000 1. P = P + A.
     • P = 1 1110 0000 0. 右シフト。
  4. P = 1 1110 000 0 0。最後の2ビットは00です。
     • P = 1 1111 0000 0。右シフト。
• 積は 11110000 (最初と最後のビットを破棄した後) となり、これは -16 になります。

0に囲まれた1のブロックからなる正の乗数を考えてみましょう。たとえば、00111110です。積は次のように表されます 。ここでMは被乗数です。同じことを書き直すと、演算回数は2回に減ります。 $${\displaystyle M\times \,^{\prime \prime }0\;0\;1\;1\;1\;1\;1\;0\,^{\prime \prime }=M\times (2^{5}+2^{4}+2^{3}+2^{2}+2^{1})=M\times 62}$$$${\displaystyle M\times \,^{\prime \prime }0\;1\;0\;0\;0\;0{\mbox{-1}}\;0\;^{\prime \prime }=M\times (2^{6}-2^{1})=M\times 62.}$$

実際、2 進数の 1 のシーケンスは、2 つの 2 進数の差に分解できることが示されています。

$${\displaystyle (\ldots 0\overbrace {1\ldots 1} ^{n}0\ldots )_{2}\equiv (\ldots 1\overbrace {0\ldots 0} ^{n}0\ldots )_{2}-(\ldots 0\overbrace {0\ldots 1} ^{n}0\ldots )_{2}.}$$

したがって、乗算は、実際には、より単純な操作、つまり乗数を加算し、形成された部分積を適切な位置でシフトし、最後に乗数を減算することで、元の数値の 1 の文字列に置き換えることができます。これは、バイナリ乗数で 0 を扱うときにシフト以外は何もする必要がないという事実を利用しており、99 を掛けるときに 99 = 100 − 1 という数学的特性を使用するのと似ています。

この方式は、乗算器内の任意の数の1のブロック（ブロック内に1が1つだけの場合を含む）に拡張できます。したがって、

$${\displaystyle M\times \,^{\prime \prime }0\;0\;1\;1\;1\;0\;1\;0\,^{\prime \prime }=M\times (2^{5}+2^{4}+2^{3}+2^{1})=M\times 58}$$ $${\displaystyle M\times \,^{\prime \prime }0\;1\;0\;0{\mbox{-1}}\;1{\mbox{-1}}\;0\,^{\prime \prime }=M\times (2^{6}-2^{3}+2^{2}-2^{1})=M\times 58.}$$

ブースのアルゴリズムは、この古い方式に従って、1 のブロックの最初の桁 (0 1) に遭遇したときに加算を実行し、ブロックの末尾 (1 0) に遭遇したときに減算を実行します。これは、負の乗数にも適用されます。乗数の 1 が長いブロックにグループ化されている場合、ブースのアルゴリズムでは、通常の乗算​​アルゴリズムよりも少ない加算と減算が実行されます。

• バイナリ乗算器
• 非隣接形式
• 冗長バイナリ表現
• ウォレスツリー
• ダダ乗数

• コリン、アンドリュー (1993 年春)。「バークベック カレッジのアンドリュー ブースのコンピュータ」。復活(5)。ロンドン:コンピュータ保存協会。
• パターソン、デビッド・アンドリュー、ヘネシー、ジョン・ルロイ(1998)。『コンピュータの構成と設計: ハードウェア/ソフトウェア インターフェイス (第 2 版)』。米国カリフォルニア州サンフランシスコ: Morgan Kaufmann Publishers。ISBN 1-55860-428-6。
• Stallings, William (2000)。コンピュータの構成とアーキテクチャ: パフォーマンスのための設計 (第 5 版)。ニュージャージー: Prentice-Hall, Inc. ISBN 0-13-081294-3。
• Savard, John JG (2018) [2006]. 「Advanced Arithmetic Techniques」. quadibloc . 2018年7月3日時点のオリジナルよりアーカイブ。 2018年7月16日閲覧。

• Radix-4 ブースエンコーディング
• RTL とコンピュータ演算の形式理論における基数 8 のブース符号化
• ブースのアルゴリズム JavaScript シミュレーター
• Pythonでの実装