Multiply $(-2)_{10} \ \ \ and \ \ \ (-5)_{10}$ using Booth’s algorithm

Mumbai University > Computer Engineering > Sem4 > Computer Organization and Architecture

Marks: 10M

Year: Dec 14, May 14

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_{ -1} $ to 0 and count to n

2) Based on the values of $Q_0 \ \ and \ \ Q_{ -1}$ do the following:

$\hspace{1 cm}$ a. if $Q_0 , Q_{ -1}$=0,0 then Right shift A,Q,$Q_{-1}$ and finally decrement count by 1

$\hspace{1 cm}$ b. If $Q_ 0, Q_{ -1}$=0,1 then Add A and B store in A, Right shift A,Q,$Q_{ -1}$ and finally decrement count by 1

$\hspace{1 cm}$ c. If $Q_ 0, Q_{ -1}=1$,0 then Subtract A and B store in A, Right shift A,Q,$Q_{ -1}$ and finally decrement count by 1

$\hspace{1 cm}$ d. If $Q_0, Q_{-1}=1$,1 then Right shift A,Q,$Q_{ -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}$= 1011(in 2’s complement)

$(-2)_{10}$ =1110(in 2’s complement)

Multiplicand (B) = 1011

Multiplier (Q) =1110

And initially Q-1=0

Count =4

Result =$(0000 \ \ 1010)_{10} \ \ or \ \ (10)_{10}$

This is the required and correct result.