补码的乘法-布斯乘法

前言

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

布斯乘法

A.D.Booth提出了一种补码相乘算法,可以将符号位与数值位合在一起参与运算，直接得出用补码表示的乘积，且正数和负数同等对待。这种算法被称之为Booth (布斯)乘法
下面有两个变量值$X$、$Y$
$Y$用二进制表示为
$Y=y_{n-1}{y}_{n-2}\dots y_2{y}_1{y}_0$
因为Y是用补码表示的，所以Y的值可以通过下面的公式计算：
$$\begin{array}{rl}Y& =-y_{n-1}{2}^{n-1}+y_{n-2}{2}^{n-2}+\dots +y_1{2}^1+y_0{2}^0\\ & =-y_{n-1}{2}^{n-1}+\sum _{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}+\dots +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}+\dots +(y_0-y_1)2^1+(0-y_0)\\ & =\sum _{i=0}^{n-1}(y_{i-1}-y_i)2^i\end{array}$$
因为$X$、$Y$都是n位数据，所以$X\times Y$可能占用2n位。
我们先假设$Y$乘以$2^{-n}$
$$\begin{array}{rl}X\times Y\times 2^{-n}& =X\times \sum _{i=0}^{n-1}(y_{i-1}-y_i)2^i\times 2^{-n}\\ & =X\times \sum _{i=0}^{n-1}(y_{i-1}-y_i)2^{-(n-i)}\\ & =P_n\end{array}$$
即然我们假设这个值等于$P_n$了，那么我们可以推测$P_{n-1}$的值
$$P_{n-1}=X\times \sum _{i=0}^{n-2}(y_{i-1}-y_i)2^{-(n-1-i)}$$
然后我们能得出两个挨着的一般性公式$P_i$和$P_{i-1}$的关系
$$P_i=2^{-1}(P_{i-1}+(y_{i-2}-y_{i-1})X)，i=1,2\dots ,n-1$$

根据上面的公式，我们发现，可以先计算$P_0$，然后通过$P_0$计算$P_1$，然后通过$P_1$计算$P_2$，然后就可以依次往后计算出$P_n$，如果计算$X\times Y$，我们可以按照下面的步骤进行：

1. 假设$P_0=0$，假设$y_{-1}=0$
2. 从y的最右侧位开始，先比较$y_0$和$y_{-1}$
3. 如果$y_0{y}_{-1}==00$，$P_0$右移一位
4. 如果$y_0{y}_{-1}==01$，$P_0+X$然后，右移一位
5. 如果$y_0{y}_{-1}==10$，$P_0-X$然后，右移一位
6. 如果$y_0{y}_{-1}==11$，$P_0$右移一位
7. 右移后得到$P_1$，比较位向左移动一位，如果没有超过最大位，跳转到2
8. 如果超过最高位了，$P_n$就是结果

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

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

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

1. 比较$y_0$与$y_{-1}$,$y_0{y}_{-1}=00$，R=00000000 00000000，右移后值不变
2. 比较$y_1$与$y_0$,$y_1{y}_0=00$，R=00000000 00000000，右移后值不变
3. 比较$y_2$与$y_1$,$y_2{y}_1=00$，R=00000000 00000000，右移后值不变
4. 比较$y_3$与$y_2$,$y_3{y}_2=10$，R=00000000 00000000，R-X后右移
   R-X = R(高位) + (~X) + 1= 10011100 00000000，右移后为11001110 00000000
   注意：是在R的高位上操作，并且右移为算数右移，补符号位
5. 比较$y_4$与$y_3$,$y_4{y}_3=11$，R=11001110 00000000，右移后为11100111 00000000
6. 比较$y_5$与$y_4$,$y_5{y}_4=11$，R=11100111 00000000，右移后为11110011 10000000
7. 比较$y_6$与$y_5$,$y_6{y}_5=11$，R=11110011 10000000，右移后为11111001 11000000
8. 比较$y_7$与$y_6$,$y_7{y}_6=01$，R=11111001 11000000，R+X后右移，R+X = 01011101 11000000， 右移后为00101110 11100000

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

布斯乘法在电路的实现

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

• 正好抵消了之前公式中乘的$2^{-n}$
• 在算法执行过程中结果数据总要右移，把结果数据放在高位，右移的时候不会丢失数据

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

• 假设Y有n位，我们设计的电路有n+1根线，Y的值放在$n～1$位，$y_{-1}$的值放在0位
• 这样，每一步的比较操作我们只需要右移电路一位，然后比较最低的两位值即可

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

• 假设Y有n位，我们设计的电路有2n+1位，数据结果保存到$2n～n+1$位，Y的值放在$n～1$位，$y_{-1}$的值放在0位
• 最终的结果就是高2n位的数据

下面给出电路图：

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

• 我们假设乘积寄存器P+乘数寄存器Y+最右边保存$y_{-1}$的值统称为R。
• 默认乘积寄存器P的值为0，最右边保存$y_{-1}$的值为0，乘数寄存器Y的值和被乘数寄存器X的值被输入，计数器为0，时钟用来增加计数器的值
• 每一步时钟，检查R的第两位，根据值的不同执行不同的电路逻辑
  • 00或者11，R右移，执行下一步
  • 01，执行加法操作，结果保存到乘积寄存器P，R右移，执行下一步
  • 10，执行减法操作，结果保存到乘积寄存器P，R右移，执行下一步
• 计数器等于32，输出结果乘积寄存器P+乘数寄存器Y，结束

算术一位右移

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

/*** 单位右移操作，为了实现布斯乘法专门定义的右移电路，支持129位* in_1：128～65位，用于存放乘积寄存器P* in_2：64～1位，用于存放乘数寄存器Y* in_1：0位，用于存放临时比较的值* isLogic：是否是逻辑右移*/
extern void alu_shift_right_1(long* in_1,long*  in_2,long*  in_3,long isLogic);void alu_shift_right_1(long* in_1,long* in_2,long*  in_3,long isLogic)
{// 先赋值最低位*in_3 = (*in_2)&1;// in_1的最低位给in_2的最高位unsigned long a = *in_2;*in_2 = (a>>1)| ((*in_1)&1)<<(sizeof(long)*8-1);// in_1右移1位if(isLogic){unsigned long b = *in_1;*in_1 = b>>1;}else{*in_1 = (*in_1)>>1;}
}

布斯乘法的C语言描述

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

/*** 使用布斯乘法算法计算两个数相乘* in_1：输入1* in_2：输入2* out_1：输出高位* out_2：输出低位*/
extern void alu_booth_times(long in_1, long in_2,long* out_1, long* out_2);void alu_booth_times(long in_1, long in_2,long* out_1, long* out_2)
{// y-1位,默认为0long lastBit = 0;// 保存结果的高位*out_1 = 0;long c = 0;// 计数器for(int i = 0; i<sizeof(long)*8;i++){long temp = in_2&1;if(temp == lastBit)// 直接右移{alu_shift_right_1(out_1,&in_2,&lastBit,0);}else if(lastBit==1)// 01,相加，然后右移{c = 0;*out_1 = alu_add_bcla_64(*out_1,in_1,sizeof(long)*8,&c);alu_shift_right_1(out_1,&in_2,&lastBit,0);}else// 10,相减，然后右移{*out_1 = alu_sub_bcla_64(*out_1,in_1,sizeof(long)*8);alu_shift_right_1(out_1,&in_2,&lastBit,0);}}*out_2 = in_2;
}