1
$\begingroup$

I was referring Booth's algorithm for 2's complement multiplication from William Stallings book. It was explained as follows (please ignore two starting words "As before", it still makes complete sense):

enter image description here enter image description here

The author then gives following example for $7\times 3$, which I am able to understand:

enter image description here

Next author gives examples for all combinations of +ve and -ve combination of multiplication:

enter image description here

Doubt

I am not able to get how example in figure 9.13 maps to same example but more compact approach illustrated in figure 9.14(a). I mean how those entries are made in fig 9.14 (a)

PS: Wanted to add tags "booths-algorithm" and "2s-complement-multiplication", but wasnt able to create those due to low reputations.

$\endgroup$
1
$\begingroup$

So, it goes like this, we have Q = 0011 and Q-1 = 0 in the beginning.

At the start, we have

count = 4
(Q0 Q-1) = (1 0)

so we perform the A←(A-M) operation, according to the figure each time when we perform any operation in register A, we assume that its value is 00000000 for +M and 11111111 for −M. Performing A←(A-M) yields the first partial product

A = 11111111+00001001 = 11111001

Now, we have

count = 3
(Q0 Q−1) = (1 1)

note here, when we have (Q0 Q−1) as (1 1) or (0 0), we'll just skip and put all 0s in the partial product by shifting it by 1 bit to the left (as we do in multiplication) as it's done in the book, which is the 2nd partial product

A = 00000000+00000000 = 00000000
shifting it left by 1 bit, 00000000

Now, we have

count = 2
(Q0 Q−1) = (0 1)

so we perform the (A←A+M) operation, which gives us the 3rd partial product

A = 00000000+00000111 = 00000111
shifting it left by 2 bits, 00011100

Now, we have

count = 1
(Q0 Q−1) = (0 0)

as mentioned above, we'll just skip and put all 0s as the 4th partial product

A = 00000000+00000000 = 00000000
shifting it left by 3 bits, 00000000
(this isn't illustrated in the figure 9.14(a))

after this operation count = 0 and then we'll sum up all the partial products as

   11111001 (1st partial product)
   00000000 (2nd partial product)
   00011100 (3rd partial product)
 + 00000000 (4th partial product)
-------------------
   00010101 (final product)

As we all know (00010101)2 = (21)10. That's what done in the figure 9.14(a), but shown in a different (or COMPACT) way as

   11111001
   0000000
 + 000111
-------------------
   00010101

Well, you can make it more compact like this:-

   11111001
 + 000111
-------------------
   00010101

But all of 'em will give you the binary representation of 21.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.