RndTool.info âš¡

Booth's Multiplication Algorithm Step by Step Calculator






Loading...

Booth's Multiplication Algorithm & Multiplier, including Booth's Recoding and Bit-Pair Recoding Method (aka Modified Booth Algorithm), Step by Step Calculator

Booth's Multiplication Algorithm is a multiplication algorithm that multiplies two signed binary numbers in two's complement notation.

Question Examples:

Question 1: Multiply 3 times -25 using 6-bit numbers


Answer:

310 = 00 00112

-2510 = 10 01112




MultiplierBooth
Multiplier
Bit[i]Bit[i-1]
000
01+1
10-1
110
Booth Multiplier Recoding Table:
Multiplier: 1001110
Booth Recoding: -1  0 +1  0  0 -1
*A red zero is added after the least significant bit (LSB) for the conversion
Click on the zeros in "Booth Recoding" above to view the pair of bit of each conversion!

 000011
  Ã— -10+100-1
111111111101 
000000011 
000000010101 
1111101 
111110110101
Booth MultiplierBit-Pair Recoding Multiplier
Bit[i]Bit[i-1]Bit[i]Bit[i-1]
1-101
-110-1
1002
-100-2
Bit-Pair Recoding Table:
Multiplier: 1001110
Booth Recoding: -1  0 +1  0  0 -1
Bit-Pair Recoding: -2 +2 -1
If the Multiplier is an odd number of bits, a 1/0 bit is added to extent the multiplier to an even number of bits before the most significant bit (MSB) for the Bit-Pair Recoding Method conversion. Since the Multiplier is an even number of bits, we don't add the bit before MSB.
Same as the Booth Recoding above, a red zero is added after the least significant bit (LSB) for the Booth Recoding conversion

 000011
  Ã— 0-20+20-1
1111111111101 
00000000110 
0000000010101 
111111010 
1111110110101



Question 2: Compute C = A × B using the Booth algorithm to multiply the two significands. (Both numbers have to be in 2’s complement form.)

Sa = 01.1000001 (including a sign bit)

Sb = 01.1111011 (including a sign bit)


Answer:

Word Length = 9




Binary's decimal point position = Multiplicand least significant bit (LSB) × Multiplier LSB = 2-7 × 2-7 = 2-7 + -7 = 2-14
(The 15th bit from right to left contains decimal point)


MultiplierBooth
Multiplier
Bit[i]Bit[i-1]
000
01+1
10-1
110
Booth Multiplier Recoding Table:
Multiplier: 01.11110110
Booth Recoding: +1  0.  0  0  0 -1 +1  0 -1
*A red zero is added after the least significant bit (LSB) for the conversion
Click on the zeros in "Booth Recoding" above to view the pair of bit of each conversion!

 01.1000001
  Ã— +10.000-1+10-1
11111111100111111 
000000011000001 
00000001001000011 
11111100111111 
11111110000111011 
001000001 
0010.11110100111011
Booth MultiplierBit-Pair Recoding Multiplier
Bit[i]Bit[i-1]Bit[i]Bit[i-1]
+1-10+1
-1+10-1
+100+2
-100-2
 Same as Booth Recoding:
0-10-1
0+10+1
0000
Bit-Pair Recoding Table:
Multiplier: 00111110110
Booth Recoding
(for Bit-Pair Recoding Method):
  0 +1  0.  0  0  0 -1 +1  0 -1
Bit-Pair: +1 0 0 -1 -1
*A red 1/0 bit is added to extent the multiplier to an even number of bits before the most significant bit (MSB) for the Bit-Pair Recoding Method conversion. Add 1 if the multiplier is negative two's complement, and 0 if it is positive.
Same as the Booth Recoding above, a red zero is added after the least significant bit (LSB) for the Booth Recoding conversion
Click on the zeros in "Booth Recoding" above to view the pair of bit of each conversion!

 01.1000001
  Ã— +10.0000-10-1
1111111111100111111 
11111111100111111 
1111111110000111011 
00001000001 
000010.11110100111011