一、Booth乘法器原理

Booth算法可以减少乘法运算中加法/减法次数，是二进制乘法补码运算的高效算法。

我们已经很熟悉，在乘法运算中包含2部分：（1）：生成部分和；（2）部分和累积

而Booth算法可以减少部分和个数和加速累积，在连续比特“0”或“1”将产生更少的部分和。

在介绍Booth算法前，我们来重新回忆下往期中数的表示：

N比特数B，将其展开，其中B-1=0：

将A与B相乘，则：

对于B的第n位和第n-1位，从上式可以发现，B可以通过相邻比特的减法和2的n次方相乘而得。

如果AB两数相乘，从B的-1和0位逐次向高位检查，累积A*B的结果的话：

当Bn=Bn-1,则可以省去B与A相乘和加法，只需要进行移位即可。

如果Bn=1，Bn-1=0，则为-A*2的n次；

如果Bn=0，Bn-1=1，则为+A*2的n次。

 

通过以上A*B两数的认识，结合以上原理，我们来看Booth算法的基本过程，下文的A为累积寄存器，与上文示例不同。

Booth算法的基本过程为：

1. 被乘数和乘数分别存入M和Q寄存器；

2. 中间结果存入A和Q寄存器；

3. A和Q-1寄存器初始为0；Q-1为1比特寄存器，索引为“-1”；

4. Q-1寄存器放置于Q寄存器最低比特Q0比特的右方；

5. 在每个周期，检查Q0和Q-1：

    5.1. 如果Q0Q-1 = 00 或 11， {A，Q，Q-1}将直接右移1比特。

    5.2. 如果Q0Q-1 = 01,则被乘数M与A相加，{A，Q，Q-1}右移1比特。

    5.3. 如果Q0Q-1 = 10,则A减去M，{A，Q，Q-1}右移1比特。

 

Booth算法的流程图如下，其中M为被乘数，Q为乘数，N为M和Q的M的比特位数，A为与M位宽相等的寄存器：

 

以上是Radix-2 Booth算法，姑且翻译为基2布什算法，以下是一个例子：

7*（-5）= -35 ；

如果设计一个面积小，性能要求不高的乘法器，可以采用迭代的方法，根据流程图描述即可。

因在实际中基2 Booth算法使用较少，此处不特别展示基2 Booth算法的功能性Verilog设计，下期Radix-4 Booth再见。

 

原创不易，如果对您有帮助，记得点赞关注哦。欢迎批评指正，谢谢鼓励！

一起“纸上谈芯”，共同学习: