ブース アルゴリズムは、2 つの符号付き 2 進整数をそれぞれ 2 の補数で乗算できる乗算アルゴリズムです。また、乗算プロセスのパフォーマンスを高速化するためにも使用されます。非常に効率的でもあります。これは、乗算器の文字列ビット 0 に対して動作します。追加ビットは必要ありません。右端の文字列ビットと乗算器のビット重み 2 の 1 の文字列をシフトするだけです。k重量2までメートルそれは次のように考えられます 2k+1- 2メートル 。
以下は、ブースのアルゴリズムを図で表したものです。
上記のフローチャートでは、最初に、 交流 そして Qn+1 ビットは 0 に設定され、 SC セットされた合計ビットを表すシーケンス カウンターです。 ん、 これは乗算器のビット数に等しくなります。がある BR を表す 被乗数ビット、 QR は 乗数ビット 。その後、Q として乗数の 2 ビットに遭遇しました。nそしてQn+1ここで、Qn は QR の最後のビットを表し、Qn+1は、Qn の 1 ずつインクリメントされたビットを表します。乗数の 2 ビットが 10 に等しいと仮定します。これは、アキュムレータ AC の部分積から乗数を減算し、算術シフト演算 (ashr) を実行する必要があることを意味します。 2 つの乗数が 01 に等しい場合、アキュムレータ AC の部分積に被乗数を加算してから算術シフト演算を実行する必要があることを意味します ( アシュル ）、 含む Qn+1 。算術シフト演算はブースのアルゴリズムで使用され、AC ビットと QR ビットを右に 1 つシフトし、AC の符号ビットは変更されません。そして、シーケンス カウンタは、計算ループがビット数 (n) に等しく繰り返されるまで継続的にデクリメントされます。
ブースアルゴリズムの開発
- 被乗数と乗数のバイナリ ビットをそれぞれ M と Q に設定します。
- 最初に、AC と Q を設定します。n+1値を 0 に登録します。
- SC は乗算ビット数 (Q) を表し、ビット数 (n) に等しくなるか 0 に達するまで継続的にデクリメントされるシーケンス カウンタです。
- A Qn は Q の最後のビットを表し、Qn+1Qn のビットを 1 ずつインクリメントしたものを示します。
- ブースアルゴリズムの各サイクルで、QnそしてQn+1ビットは次のようにパラメータでチェックされます。
- 2ビットQの場合nそしてQn+1が 00 または 11 の場合、部分積 AC に対して算術右シフト演算 (ashr) を実行するだけです。そしてQnとQのビットn+11ビットずつインクリメントされます。
- Q のビットがnそしてQn+1が 01 に表示されると、被乗数ビット (M) が AC (アキュムレータ レジスタ) に追加されます。その後、AC ビットと QR ビットに 1 ずつ右シフト演算を実行します。
- Q のビットがnそしてQn+1が 10 に示されると、被乗数ビット (M) が AC (アキュムレータ レジスタ) から減算されます。その後、AC ビットと QR ビットに 1 ずつ右シフト演算を実行します。
- この操作は、ブース アルゴリズムが n - 1 ビットに達するまで継続的に動作します。
- 乗算のバイナリ ビットの結果は、AC レジスタと QR レジスタに格納されます。
Booth のアルゴリズムでは 2 つの方法が使用されます。
キャット・ティンプの体重はどれくらいですか
1. RSC (右シフト循環)
2 進数の右端のビットをシフトし、2 進数のビットの先頭に追加します。
2. RSA (右シフト演算)
2 つのバイナリ ビットを加算し、結果を 1 ビット位置だけ右にシフトします。
パワーシェルとバッシュの比較
例 : 0100 + 0110 => 1010、2 進数を加算した後、各ビットを右に 1 シフトし、結果の最初のビットを新しいビットの先頭に置きます。
例: Booth の乗算アルゴリズムを使用して、2 つの数値 7 と 3 を乗算します。
年 。ここには 7 と 3 という 2 つの数値があります。まず、7 と 3 を 7 = (0111) や 3 = (0011) のような 2 進数に変換する必要があります。次に、被乗数 (M) として 7 (バイナリ 0111) を設定し、乗数 (Q) として 3 (バイナリ 0011) を設定します。 SC (Sequence Count) はビット数を表します。ここでは 4 ビットなので、SC = 4 に設定します。また、これはブースのアルゴリズムの反復サイクル数を示し、サイクルは SC = SC - 1 回実行されます。
| Qn | Qn+1 | M = (0111) M' + 1 = (1001) & 演算 | 交流 | Q | Qn+1 | SC |
|---|---|---|---|---|---|---|
| 1 | 0 | イニシャル | 0000 | 0011 | 0 | 4 |
| 減算 (M' + 1) | 1001 | |||||
| 1001 | ||||||
| 算術右シフト演算の実行 (ashr) | 1100 | 1001 | 1 | 3 | ||
| 1 | 1 | 算術右シフト演算の実行 (ashr) | 1110 | 0100 | 1 | 2 |
| 0 | 1 | 加算(A+M) | 0111 | |||
| 0101 | 0100 | |||||
| 算術右シフト演算を実行する | 0010 | 1010 | 0 | 1 | ||
| 0 | 0 | 算術右シフト演算を実行する | 0001 | 0101 | 0 | 0 |
ブースの乗算アルゴリズムの数値例は 7 x 3 = 21 で、21 の 2 進数表現は 10101 です。ここでは、結果を 2 進数で 00010101 として取得します。次に、これを (000010101) のように 10 進数に変換します。10= 2*4 + 2*3 + 2*2 + 2*1 + 2*0 => 21.
私のライブクリケット。
例: Booth の乗算アルゴリズムを使用して、2 つの数値 23 と -9 を乗算します。
ここで、M = 23 = (010111) および Q = -9 = (110111)
| QnQn+1 | M = 0 1 0 1 1 1 M' + 1 = 1 0 1 0 0 1 | 交流 | Q | Qn+1SC |
|---|---|---|---|---|
| 最初は | 000000 | 110111 | 0 6 | |
| 1 0 | M を引く | 101001 | ||
| 101001 | ||||
| 算術右シフト演算を実行する | 110100 | 111011 | 15 | |
| 十一 | 算術右シフト演算を実行する | 111010 | 011101 | 1 4 |
| 十一 | 算術右シフト演算を実行する | 111101 | 001110 | 1 3 |
| 0 1 | 加算(A+M) | 010111 | ||
| 010100 | ||||
| 算術右シフト演算を実行する | 001010 | 000111 | 0 2 | |
| 1 0 | M を引く | 101001 | ||
| 110011 | ||||
| 算術右シフト演算を実行する | 111001 | 100011 | 十一 | |
| 十一 | 算術右シフト演算を実行する | 111100 | 110001 | 1 0 |
Qn+1 = 1、出力が負であることを意味します。
したがって、23 * -9 = 111100110001 の 2 の補数 => (00001100111)