Mumbai University > Electronics Engineering > Sem6 > Computer Organization

Marks: 10M

Year: Dec 2015

Figure below shows implementation of Booth’s algorithm.

Figure 1. Hardware Implementation of Booth’s Algorithm

1) Fig shows implementation of booth’s algorithm. It consists on n-bit adder , shift , add subtract control logic and four registers A,M,Q and Q-1.

2) Multiplier and multiplicand and are loaded into registers Q and M. registers A and Q-1 are initially set to 0.

3) The n-bit adder performs addition of two inputs. One input is the A register and other input Is multiplicand.

Case 1 : In case of addition, add/sub line is 0, therefore, cin=0 and multiplicand is directly applied as second input to the n-bit adder.

Case 2 : In case of subtraction , add/sub line is 1, therefore cin=1 and multiplicand is complemented and then applied to the n-bit adder. As a result the 2’s complement of multiplicand is added in the A register.

Algorithm:-

Examine 2 adjacent bits of multiplier form right to left and generate the recoded Booth’s multiplier as follows:

If moving form

0 to 1 : Subtract multiplicand from partial product & shift (-1)

1 to 0 : Add multiplicand to partial product & shift (+1)

0 to 0 : No addition or subtraction just shift (0)

1 to 1 : No addition or subtraction just shift (0)

Solve (+7)*(-5) using Booth’s Algorithm

M= 0 1 1 1 $\hspace{2 cm}$ +5=0 1 0 1 +7= 0 1 1 1

Q=1 0 1 1 $\hspace{2 cm}$ -5= 1 0 1 1 -7= 1 0 0 1

A=0 0 0 0

Final product result of (+7)*(-5)=(-35) which we get in A and Q register after taking 2’s complement.

2’s complement of 1 1 0 1 1 1 0 1

=-(0 0 1 0 0 0 1 1)

= - 35