了解改进的 Baugh-Wooley 乘法算法

Question

对于改进的 Baugh-Wooley 乘法算法，为什么是 !(A0*B5) 而不是 (A0*B5)？

同样的问题!(A1*B5), !(A2*B5), !(A3*B5), !(A4*B5), !(A5*B4), !(A5*3), !(A5*B2)、!(A5*B1) 和 !(A5*B0)

另外，为什么多了两个'1'？

Answer 1

简短的回答是因为 2's-complement 表示的工作原理：最高位实际上是一个符号位，所以 1 意味着 -。换句话说，你必须减去

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

和

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

来自总和（注意A5*B5被再次添加，因为两者具有相同的-符号）。而那两个1就是用-X的加法代替这两个减法的结果。

如果您需要更多详细信息，那么您可能只需要重新阅读 2 的补码是如何工作的，然后再阅读 Baugh-Wooley 乘法算法背后的整个数学。没那么复杂。

Answer 2

有符号的6位2s补码中，位的位值为：

-32  16   8   4   2   1

注意最高位是负值。但是，当执行加法、减法和乘法时 mod 64，减号对这些运算的工作方式完全没有影响，因为 32 = -32 mod 64.

你的乘法不是 mod 64，所以必须考虑这个符号。

考虑乘法的一种方法是将 6 位数字扩展为 12 位，然后执行乘法 mod 4096。扩展有符号数时，复制最高位，因此-32 变成 -2048 + 1024 + 512 ... +32，它们加在一起的值都是 -32。所以扩展带符号的数字并相乘。我会用 3 位来做，乘以 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

由于我们在多个位置复制了相同的位，您将在多个位置看到相同的位产品。

A0B2出现4次，总位值为60或15<<2，以此类推。让乘数写在：

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

同样，由于mod元运算，*15s和*7s与*-1相同，*5与*1相同：

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

这个模式开始看起来很眼熟。现在，当然 -1 不是位值，而是 ~A0B2 = 1-A0B2，所以我们可以将 -A0B2 翻译成 ~A0B2 然后减去我们添加的额外 1。如果我们对所有减去的产品执行此操作：

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

如果我们将那些 -2 的位值相加并将它们扩展为等效位，我们会发现您图中额外 1 的来源：

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

Answer 3

why two extra '1'?

请参阅 Matt Timmermans 的回答中的一些先前解释

注意：两个补码中的'-2'是110，这有助于进位，因此两个额外的'1'

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

这是由于 MSB（A5 和 B5）中的符号位。

此外，请看下面借助others.

修改baugh-wooley算法在A_WIDTH != B_WIDTH情况下的对策

这个算法我写了一个hardware verilog code 希望这篇 post 对一些读者有所帮助。

了解改进的 Baugh-Wooley 乘法算法

Understanding Modified Baugh-Wooley multiplication algorithm

algorithm

math

binary

logic

multiplication