1. Modified Booth Algorithm Calculator
2. Booth's Algorithm Division
3. Booth's Algorithm Calculator

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.

Multiply (9) and (-7) using Booths Algorithm. Written 3.4 years ago by manasahegde234 ♦ 510: Subject: Computer Organization & Architecture. Topic: Module 4. Sequential, Booth's Algorithm, Modified Booth's Algorithm, Two's Complement Array Multiplier, Fused Multiplier-Adder, Multiplication by a Constant Division Restoring, Non-Restoring, SRT Radix-2, SRT Radix-4, SRT Radix-8, SRT with overalpping stages, By Convergence, By Convergence With Table Lookup, By Reciprocation. Booth’s algorithm is a multiplication algorithm that multiplies two signed binary numbers in 2’s compliment notation. Booth used desk calculators that were faster at shifting than adding and created the algorithm to increase their speed. Booth’s algorithm is of interest in the study of computer architecture.

Question Examples:

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

Answer:

3₁₀ = 00 0011₂

-25₁₀ = 10 0111₂

Multiplier		Booth Multiplier
Bit[i]	Bit[i-1]
0	0	0
0	1	+1
1	0	-1
1	1	0

Booth Multiplier Recoding Table:

Multiplier:	1	0	0	1	1	1	0
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!

0	0	0	0	1	1
×	-1	0	+1	0	0	-1
1	1	1	1	1	1	1	1	1	1	0	1
0	0	0	0	0	0	0	1	1
0	0	0	0	0	0	0	1	0	1	0	1
1	1	1	1	1	0	1
1	1	1	1	1	0	1	1	0	1	0	1

Booth Multiplier		Bit-Pair Recoding Multiplier
Bit[i]	Bit[i-1]	Bit[i]	Bit[i-1]
1	-1	0	1
-1	1	0	-1
1	0	0	2
-1	0	0	-2

Bit-Pair Recoding Table:

Multiplier:	1	0	0	1	1	1	0
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

0	0	0	0	1	1
×	0	-2	0	+2	0	-1
1	1	1	1	1	1	1	1	1	1	1	0	1
0	0	0	0	0	0	0	0	1	1	0
0	0	0	0	0	0	0	0	1	0	1	0	1
1	1	1	1	1	1	0	1	0
1	1	1	1	1	1	0	1	1	0	1	0	1

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.)

S_a = 01.1000001 (including a sign bit)

S_b = 01.1111011 (including a sign bit)

Answer:

Word Length = 9

-7 × 2^-7 = 2^{-7 + -7} = 2^-14
(The 15th bit from right to left contains decimal point)

Multiplier		Booth Multiplier
Bit[i]	Bit[i-1]
0	0	0
0	1	+1
1	0	-1
1	1	0

Booth Multiplier Recoding Table:

Multiplier:	0	1.	1	1	1	1	0	1	1	0
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!

0	1.	1	0	0	0	0	0	1
×	+1	0.	0	0	0	-1	+1	0	-1
1	1	1	1	1	1	1	1	1	1	0	0	1	1	1	1	1	1
0	0	0	0	0	0	0	0	1	1	0	0	0	0	0	1
0	0	0	0	0	0	0	0	1	0	0	1	0	0	0	0	1	1
1	1	1	1	1	1	1	0	0	1	1	1	1	1	1
1	1	1	1	1	1	1	1	0	0	0	0	1	1	1	0	1	1
0	0	1	1	0	0	0	0	0	1
0	0	1	0.	1	1	1	1	0	1	0	0	1	1	1	0	1	1

Booth Multiplier		Bit-Pair Recoding Multiplier
Bit[i]	Bit[i-1]	Bit[i]	Bit[i-1]
+1	-1	0	+1
-1	+1	0	-1
+1	0	0	+2
-1	0	0	-2
Same as Booth Recoding:
0	-1	0	-1
0	+1	0	+1
0	0	0	0

Bit-Pair Recoding Table:

Modified Booth Algorithm Calculator

Multiplier:	0	0	1	1	1	1	1	0	1	1	0
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.

Booth's Algorithm Division

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!

Booth's Algorithm Calculator

0	1.	1	0	0	0	0	0	1
×	+1	0.	0	0	0	0	-1	0	-1
1	1	1	1	1	1	1	1	1	1	1	1	0	0	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1	1	0	0	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1	1	0	0	0	0	1	1	1	0	1	1
0	0	0	0	1	1	0	0	0	0	0	1
0	0	0	0	1	0.	1	1	1	1	0	1	0	0	1	1	1	0	1	1