本篇文章讲解如何通过逻辑门的形式来实现补码的乘法操作

A.D.Booth提出了一种补码相乘算法,可以将符号位与数值位合在一起参与运算，直接得出用补码表示的乘积，且正数和负数同等对待。这种算法被称之为Booth (布斯)乘法 下面有两个变量值 X X X、 Y Y Y Y Y Y用二进制表示为 Y = y n − 1 y n − 2 … y 2 y 1 y 0 Y = y_{n-1}y_{n-2}\ldots y_2y_1y_0 Y=yn−1​yn−2​…y2​y1​y0​ 因为Y是用补码表示的，所以Y的值可以通过下面的公式计算： Y = − y n − 1 2 n − 1 + y n − 2 2 n − 2 + … + y 1 2 1 + y 0 2 0 = − y n − 1 2 n − 1 + ∑ i = 0 n − 2 y i 2 i = − y n − 1 2 n − 1 + y n − 2 2 n − 1 − y n − 2 2 n − 2 + … + y 1 2 2 − y 1 2 1 + y 0 2 1 − y 0 = ( y n − 2 − y n − 1 ) 2 n − 1 + ( y n − 3 − y n − 2 ) 2 n − 2 + … + ( y 0 − y 1 ) 2 1 + ( 0 − y 0 ) = ∑ i = 0 n − 1 ( y i − 1 − y i ) 2 i \begin{aligned} Y &= -y_{n-1}2^{n-1} + y_{n-2}2^{n-2} + \ldots+y_12^1+ y_02^0\\ &=-y_{n-1}2^{n-1} + \sum_{i=0}^{n-2}y_i2^i \\ &=-y_{n-1}2^{n-1} + y_{n-2}2^{n-1}-y_{n-2}2^{n-2}+\ldots+y_12^{2}-y_{1}2^{1}+y_02^{1}-y_0\\ &=(y_{n-2}-y_{n-1})2^{n-1}+(y_{n-3}-y_{n-2})2^{n-2}+\ldots+(y_0-y_1)2^1+(0-y_0)\\ &=\sum_{i=0}^{n-1}(y_{i-1}-y_{i})2^{i} \end{aligned} Y​=−yn−1​2n−1+yn−2​2n−2+…+y1​21+y0​20=−yn−1​2n−1+i=0∑n−2​yi​2i=−yn−1​2n−1+yn−2​2n−1−yn−2​2n−2+…+y1​22−y1​21+y0​21−y0​=(yn−2​−yn−1​)2n−1+(yn−3​−yn−2​)2n−2+…+(y0​−y1​)21+(0−y0​)=i=0∑n−1​(yi−1​−yi​)2i​ 因为 X X X、 Y Y Y都是n位数据，所以 X × Y X\times Y X×Y可能占用2n位。 我们先假设 Y Y Y乘以 2 − n 2^{-n} 2−n X × Y × 2 − n = X × ∑ i = 0 n − 1 ( y i − 1 − y i ) 2 i × 2 − n = X × ∑ i = 0 n − 1 ( y i − 1 − y i ) 2 − ( n − i ) = P n \begin{aligned} X\times Y\times2^{-n} &= X\times \sum_{i=0}^{n-1}(y_{i-1}-y_{i})2^{i}\times2^{-n}\\ &=X\times \sum_{i=0}^{n-1}(y_{i-1}-y_{i})2^{-(n-i)}\\ &=P_{n} \end{aligned} X×Y×2−n​=X×i=0∑n−1​(yi−1​−yi​)2i×2−n=X×i=0∑n−1​(yi−1​−yi​)2−(n−i)=Pn​​ 即然我们假设这个值等于 P n P_{n} Pn​了，那么我们可以推测 P n − 1 P_{n-1} Pn−1​的值 P n − 1 = X × ∑ i = 0 n − 2 ( y i − 1 − y i ) 2 − ( n − 1 − i ) P_{n-1} = X\times \sum_{i=0}^{n-2}(y_{i-1}-y_{i})2^{-(n-1-i)} Pn−1​=X×i=0∑n−2​(yi−1​−yi​)2−(n−1−i) 然后我们能得出两个挨着的一般性公式 P i P_{i} Pi​和 P i − 1 P_{i-1} Pi−1​的关系 P i = 2 − 1 ( P i − 1 + ( y i − 2 − y i − 1 ) X ) ， i = 1 , 2 … , n − 1 P_{i} = 2^{-1}(P_{i-1} + (y_{i-2}-y_{i-1})X)，i = 1,2\ldots,n-1 Pi​=2−1(Pi−1​+(yi−2​−yi−1​)X)，i=1,2…,n−1

根据上面的公式，我们发现，可以先计算 P 0 P_{0} P0​，然后通过 P 0 P_{0} P0​计算 P 1 P_{1} P1​，然后通过 P 1 P_{1} P1​计算 P 2 P_{2} P2​，然后就可以依次往后计算出 P n P_{n} Pn​，如果计算 X × Y X\times Y X×Y，我们可以按照下面的步骤进行：

注意：在此之前，其实 P n = X × Y × 2 − n P_n =X\times Y\times2^{-n} Pn​=X×Y×2−n，并且我们发现在上述步骤中结果一直在向右移，所以，我们可以把初始结果放在高n位上，这样向右移动不会丢失数据，并且也相当于乘了 2 n 2^{n} 2n，结果刚好是想要的值。

通过上面的步骤可以看出，乘法被分解成一系列加减和移位操作的顺序集合，我们之前已经实现了串行进位加法器和并行进位加法器，并且实现了一个桶形移位器

下面看一个实际的例子： 假设X = 100，Y = 120； 用二进制表示为X = 01100100，Y= 01111000，即然8位能够放下数据，为了书写方便，我们假设XY都为8位，结果为16位数据，假设结果为R = 0；

计算完成，00101110 11100000 = 12000，与结果相符

我们在前面讲述算法执行过程的时候，把结果数据放在了高n位，这样有两个好处：

并且每一步我们都会从右往左比较Y的位值，相当于我们每步都右移Y，然后比较Y的最低两位，但是第一步的时候我们还有一个 y − 1 = 0 y_{-1}=0 y−1​=0，所以我们可以这么设计：

即然结果数据和Y的值都右移，并且每步骤都右移1位，那么我们可以设计一个通用的电路：

下面给出电路图：

图中表示的是32位的布斯乘法电路图，电路的执行步骤如下：

虽然我们实现了桶形移位器，但是在当前的乘法运算中，有点大材小用，如果我们仅仅实现一个一位的右移操作，电路将变得很简单，我们直接给出C语言描述git地址

最后给出布斯乘法的C语言描述，我们把结果存在两个long类型的数值中，out_1保存高位，out_2保存低位。git地址