Booth’s Algorithm for Multiplication | Computer Architecture

Booth’s Algorithm for Multiplication – In the (Shift and Add Method) for multiplication, the multiplicand is added to the partial product at each bit position where 1 occurs in the multiplier. It means the addition operation is performed equal to the number of 1’s in the multiplier. However, if the multiplier is negative, an additional step is required to invert the sign of both the multiplier and the multiplicand.

Booth’s Algorithm for Multiplication

Booth’s algorithm for multiplication is used to increase the speed of multiplication. This technique reduces the number of addition steps and eliminates the requirement to convert the multiplier to positive

Encoding Technique

In Booth’s multiplication, a string of 0’s in the multiplier requires only shifting of the partial sum, and the string of 1’s can be treated as a number with value (L-R). Here, L is the weight of 0 (zero) before the left-most 1, and R is the weight of the rightmost 1 (one). For example, if the number is 011100, then L=2⁵-32 and R=2²=4. The value of 011100 is 32-4=28. Let us consider some cases to get an understanding of Booth’s encoding for multiplication.

Case I: Let multiplier Q = (00011111)₂. This is a positive number with a single sequence of 1’s. It is encoded as L-R. In this case

L = 2⁵ (weight of left-most 0 before a sequence of 1’s)
R = 2⁰ (weight of right-most 1 after a sequence of 1’s).

Hence Q = L – R = 2⁵ – 2⁰ = 32 – 1 = 31₁₀
which is equal to Q = (00011111)₂ = (2⁴+2³+2²+2¹+2⁰)₁₀ = 31₁₀

This case shows that the multiplication using 2’s complement technique requires five addition operation but Booth’s encoding technique requires only two (addition and subtraction) operations are needed if the multiplier has a sequence of five 1’s.

Case-II: Let multiplier Q = 0111 0110. In this number, there are two sequences of 1’s. Therefore, the multiplier is encoded as (L₁-R₁)+(L₀-R₀).

In this case
L₁ = 2⁷ R₁ = 2⁴
L₀ = 2³ R₀ = 2¹

Hence Q = (L₁ – R₁) + (L₀ – R₀)
= (2⁷ – 2⁴) + (2³ – 2¹)
= 128 – 16 + 8 – 2
= 118

Which is equal to

Q = (0111 0110)₂ = (2⁶+2⁵+2⁴+2²+2¹) =118₁₀

This case shows that using the 2’s complement technique, five addition operations are required, but using Booth’s encoding technique, only four operations are required.

Case-III: Let multiplier Q = 11100000. This is a negative number with a single sequence of 1’s. It is encoded as L-R. In this case

L=0 (There is no leftmost 0 before a sequence of 1’s) and R=2⁵

Hence, Q = L-R
= 0-2⁵ = -32
which is equal to the 2’s complement of
Q=-(00100000)₂=-32₁₀

This case shows that Booth’s encoding technique for multiplication can handle both positive and negative numbers.

Case-IV: Let the multiplier Q=0111 1111. This is a positive number with a single long sequence of 1’s. It is encoded as L-R.

In this case
L=2⁷ and R-2⁰

Hence Q = L – R = R⁷-2⁰ = 128-1 = 127
which is equal to Q =(01111111)₂=2⁶+2⁵ +2⁴ +2³ +2²+2¹+2⁰=127

This is the best case of Booth’s encoding since it has the longest sequence of 1’s.

Case-V: Let the multiplier Q=01010101. This is a positive number with alternating 0’s and 1’s. Since there is no sequence of 1’s, it is encoded as

(L₃ – R₃) + (L₂ – R₂) + (L₁ – R₁) + (L₀ – R₀).
Hence Q = (2⁷ – 2⁶) + (2⁵ – 2⁴) + (2³ – 2²) + (2¹ – 2⁰)
= (128 – 64) + (32 – 16) + (8-4) + (2-1)
= 64 + 16 + 4 + 1
= 85

Which is equal to
Q = (01010101)₂ = 2⁶ + 2⁴ + 2² + 2⁰
= 64 + 16 + 4 + 1
= 85

In this case, Booth’s encoding technique for multiplication requires eight operations, whereas the 2’s complement technique requires only four operations. This is the worst case of Booth’s encoding.

Hardware Implementation

Booth’s multiplication algorithm is based on string manipulation. If there is a long sequence of 1’s, Booth’s algorithm becomes more efficient. Every two adjacent bits of the multiplier determine which operation is to be performed. The table below shows the possible operations.

Qi	Qi-1	Operation
0	0	Shift right
0	1	Add multiplicand and shift right
1	0	Subtract multiplicand and shift right
1	1	Shift right

The hardware implementation for the Booth algorithm is shown in the figure below. The multiplier and multiplicand are stored in register Q and register M, respectively.

Hardware Algorithm

Booth’s algorithm is shown in the figure below. The multiplier and multiplicand are placed in register Q and register M, respectively. There is also a 1-bit register placed logically to the right of the least significant bit (Q₀) of the register Q and designated at Q_-1. The results of multiplication will appear in register A and register Q.

Registers A and Q are initialized to 0. Now, each bit of the multiplier is examined. If the two bits are the same (11 or 00), then all of the bits of the register A, register Q, and Q_-1 are shifted to the right by one bit. If two bits differ, then the multiplicand is added to or subtracted from register A, followed by a right shift in accordance with the table shown above. In either case, the right shift is such that the leftmost bit of register A not only is shifted but also remains in left most bit position. This arithmetic shift right is presented as an ashr micro operation. The final product is stored in registers E, A, and Q.

Example: Show the steps to multiply (8) by (-13) using Booth’s algorithm.

Solution: Let 8 is multiplier, and -13 is multiplicand.

Hence Q = 1000

M = 10011 (2’s complement of 13₁₀) and -M = 01101 (+13).

In this case, there are five bits in the multiplicand, hence n=5. Initially, register A and Q_-1 are 0. Based on the two rightmost bits of register Q, one operation is performed. The table below shows the contents of the E, A, and Q registers at each cycle.

Cycle	E	A	Q	Operation
Initially	0	00000	10000	Initialization
1	0	00000	01000	arithmetic shift right
2	0	00000	00100	arithmetic shift right
3	0	00000	00010	arithmetic shift right
4	0 0	01101 00110	00010 10001	subtract multiplicand (Add M to A) arithmetic shift right
5	1 1	11001 11100	10001 11000	Add multiplicand (Add M to A) arithmetic shift right

The result is (1110011000), which is negative, and its 2’s complement is (0001101000)₂, or (104)₁₀. Hence, the result is -104.