Understanding 2's complement multiplication using Booth's algorithm

Question

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):

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

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

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.

Answer 1

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

At the start, we have

count = 4
(Q₀ 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
(Q₀ Q₋₁) = (1 1)

note here, when we have (Q₀ Q₋₁) 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
(Q₀ Q₋₁) = (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
(Q₀ Q₋₁) = (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)₂ = (21)₁₀. 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.