Mumbai University > Computer Engineering > sem 4> Computer Organization and Architecture

Marks: 10M

Year: May16

Booth’s algorithm

Booth’s algorithm is a powerful algorithm that is used for signed multiplication. It generates a 2n bit product for two n bit signed numbers.

The flowchart is as shown in Figure 1.

The steps in Booth’s algorithm are as follow:

1) Initialize A,Q−1Q−1 to 0 and count to n

2) Based on the values of Q0 and Q−1Q0 and Q−1 do the following:

a. if Q0,Q−1Q0,Q−1=0,0 then Right shift A,Q,Q−1Q−1 and finally decrement count by 1

b. If Q0,Q−1Q0,Q−1=0,1 then Add A and B store in A, Right shift A,Q,Q−1Q−1 and finally decrement count by 1

c. If Q0,Q−1=1Q0,Q−1=1,0 then Subtract A and B store in A, Right shift A,Q,Q−1Q−1 and finally decrement count by 1

d. If Q0,Q−1=1Q0,Q−1=1,1 then Right shift A,Q,Q−1Q−1 and finally decrement count by 1

3) Repeat step 2 till count does not equal 0.

Using the flowchart, we can solve the given question as follows:

(−5)10(−5)10= 1011(in 2’s complement)

(−2)10(−2)10 =1110(in 2’s complement)

Multiplicand (B) = 1011

Multiplier (Q) =1110

And initially Q-1=0

Count =4

Result =(0001 0100 0)2 This is the required and correct result.