Understanding Modified Baugh-Wooley multiplication

问题:

For Modified Baugh-Wooley multiplication algorithm , why is it !(A0*B5) instead of just (A0*B5) ?

Same questions for !(A1*B5), !(A2*B5), !(A3*B5), !(A4*B5), !(A5*B4), !(A5*3), !(A5*B2), !(A5*B1) and !(A5*B0)

Besides, why there are two extra '1' ?

回答1:

In signed 6-bit 2s complement notation, the place values of the bits are:

-32  16   8   4   2   1

Notice that the top bit has a negative value. When addition, subtraction, and multiplication are performed mod 64, however, that minus sign makes absolutely no difference to how those operations work, because 32 = -32 mod 64.

Your multiplication is not being performed mod 64, though, so that sign must be taken into account.

One way to think of your multiplication is that the 6-bit numbers are extended to 12 bits, and multiplication is then performed mod 4096. When extending a signed number, the top bit is replicated, so -32 becomes -2048 + 1024 + 512 ... +32, which all together has the same value of -32. So extend the signed numbers and multiply. I'll do it with 3 bits, multiplying mod 64:

Given:         Sign-extended:
A2 A1 A0       A2 A2 A2 A2 A1 A0
B2 B1 B0       B2 B2 B2 B2 B1 B0

Multiply:
A0B2    A0B2    A0B2    A0B2    A0B1   A0B0
A1B2    A1B2    A1B2    A1B1    A1B0        
A2B2    A2B2    A2B1    A2B0
A2B2    A2B1    A2B0
A2B1    A2B0
A2B0

Since we replicated the same bits in multiple positions, you'll see the same bit products at multiple positions.

A0B2 appears 4 times with with total place value 60 or 15<<2, and so on. Let write the multipliers in:

                        A0B2*15 A0B1   A0B0
                A1B2*7  A1B1    A1B0        
        A2B2*5  A2B1*7  A2B0*15

Again, because of modular arithmetic, the *15s and *7s are the same as *-1, and the *5 is the same as *1:

                       -A0B2    A0B1   A0B0
               -A1B2    A1B1    A1B0        
        A2B2   -A2B1   -A2B0

That pattern is starting to look familiar. Now, of course -1 is not a bit value, but ~A0B2 = 1-A0B2, so we can translate -A0B2 into ~A0B2 and then subtract the extra 1 we added. If we do this for all the subtracted products:

                       ~A0B2    A0B1   A0B0
               ~A1B2    A1B1    A1B0        
        A2B2   ~A2B1   ~A2B0
                 -2       -2

If we add up the place values of those -2s and expand them into the equivalent bits, we discover the source of the additional 1s in your diagram:

                       ~A0B2    A0B1   A0B0
               ~A1B2    A1B1    A1B0        
        A2B2   ~A2B1   ~A2B0
   1              1

回答2:

why two extra '1'?

See some previous explanation in Matt Timmermans's answer

Note : '-2' in two complement is 110, and this contributes to the carries, thus two extra '1'

why flipping the values of some of the partial product bits.

It is due to signed bit in the MSB (A5 and B5).

Besides, please see below the Countermeasure for modified baugh-wooley algorithm in the case of A_WIDTH != B_WIDTH with the help of others.

I have written a hardware verilog code for this algorithm Hopefully, this post helps some readers.

回答3:

The short answer is that's because how 2's-complement representation works: the top bit is effectively a sign bit so 1 there means -. In other words you have to subtract

A5*(B4 B3 B2 B1 B0) << 5

and

B5*(A4 A3 A2 A1 A0) << 5

from the sum (note that A5*B5 is added again because both have the same - sign). And those two 1 is the result of substituting those two subtractions with additions of -X.

If you need more details, then you probably just need to re-read how 2's-complement work and then the whole math behind the Baugh-Wooley multiplication algorithm. It is not that complicated.