基于Booth编码和Wallace树的16位有符号数乘法器设计与实现

基于Booth编码和Wallace树的16位有符号数乘法器设计与实现

引用

CSDN

1.

https://blog.csdn.net/LionelZhao/article/details/145244440

本文详细介绍了基于Booth编码和Wallace树的16位有符号数乘法器的设计原理和实现方法。通过Booth编码优化部分积的生成，使用Wallace树压缩累加过程，显著提高了乘法器的性能。文章从理论推导到具体实现，再到仿真验证，完整展示了乘法器的设计流程。

1. 设计功能与要求

基于Booth编码和Wallace树的16位有符号数乘法器的基本思想是逻辑等效，采用Booth编码器等效替代传统二进制乘法计算的部分积产生逻辑；Wallace树采用多个3-2压缩器构成的树形连接等效替代串行阵列加法器。

2. 算法原理

2.1 无符号数二进制乘法

设4位无符号数乘法器的输入被乘数A={A3,A2,A1,A0}、乘数B={B3,B2,B1,B0}，输出乘积S={S7,S6,S5,S4,S3,S2,S1,S0}，则乘法计算过程如下图所示，分为部分积生成、部分积累加两个阶段。

2.2 有符号数二进制乘法

设4位有符号数乘法器的输入被乘数A={A3,A2,A1,A0}、乘数B={B3,B2,B1,B0}，输出乘积S={S7,S6,S5,S4,S3,S2,S1,S0}，其中最高位A3和B3都是符号位。有符号数和无符号数的二进制乘法的区别在于最后一个部分积生成，若B3为1则部分积为被乘数A的补码，B3为0则部分积全为0。

以(-7)×(-7)为例列解有符号数乘法如下图所示，与无符号数乘法区别在于最后一个部分积的产生和累加时的符号位扩展。

2.3 阵列乘法器

在明确2.1和2.2小节二进制乘法运算规则后可得最经典的阵列乘法器结构，4位无符号数的阵列乘法器如下图所示。

从图中可以看到，使用与门实现部分积的生成，然后使用阵列加法器实现部分积的累加。这种乘法器结构虽然简单直接，但是使用较大加法器阵列，延时路径上既有进位延迟，又有求和延迟，可能存在多条延时几乎相同的关键路径，其性能欠佳。

2.4 Booth编码

随着乘法器输入数据位宽的增加，阵列乘法器中所需要的与门和全加器数量也随着剧增，关键路径的延迟也相应增加。Booth编码通过编码表的方式避免按位与操作，节省了电路面积，并能够在一定程度上降低非零部分积的数量。

借助基4-Booth编码，有符号二进制数的乘法可以写为：

A × B = ∑ i = 0 N 2 − 1 A [ 2 i ] × ( − 2 B [ 2 i + 1 ] + B [ 2 i ] + B [ 2 i − 1 ] ) ⋅ 2 2 i

因而部分积的产生可以从以下Booth编码表获得：

编码表中部分积为-A相当于对A求补码、2A相当于对A左移1位、-2A相当于先对A左移1位然后求补。仍然以(-7)×(-7)为例列解有符号数乘法的Booth编码实现，其计算过程如下图所示，首先在最低位右侧加入B[-1]=0，然后每三位取B[2i+1]B[2i]B[2i-1]并通过Booth编码表得到对应的部分积，最后将进行符号位扩展之后的部分积累加就可以得到最终的乘积。

从图中可以看出，采用基4-Booth编码可以有效减少部分积的数量，但是需要注意部分积累加时的偏移由1位变成了2位。

2.5 Wallace树

全加器示意图如下图所示。Wallace树通过多个全加器(又称为3-2压缩器，因为全加器输入三个数据Cin、A、B，输出两个数据Cout、S)所构成的树形连接替代规模庞大的串行阵列加法器，能够缩短累加计算时间。

当输入为16位有符号数时，基4-Booth编码具有8项部分积，因而只需要经历4级压缩就可以得到2行长度为32的部分积，最后可以通过32位超前进位加法器得到最终的32位乘积。Wallace树压缩过程如下图所示。

• Wallace树第一级：使用两组、每组32个全加器将8行部分积压缩为6行部分积；
• Wallace树第二级：使用两组、每组32个全加器将6行部分积压缩为4行部分积；
• Wallace树第三级：使用一组、每组32个全加器将4行部分积压缩为3行部分积；
• Wallace树第四级：使用一组、每组32个全加器将3行部分积压缩为2行部分积；

通过上述描述可知，共需要六组、每组32个全加器组成Wallace树。

2.6 基于Booth编码和Wallace树的16位有符号数乘法器

基于Booth编码和Wallace树的16位有符号数乘法器框架如下图所示，将模块分为Booth编码模块、部分积生成模块、Wallace树模块、超前进位加法器模块，其中Wallace树模块由六组、每组32个全加器组成。

综上所述，我们明确了构建基于Booth编码和Wallace树的16位乘法器所需的所有模块的基本原理，下面将进行RTL实现。

3. RTL实现

3.1 Booth编码器模块

Booth编码器负责接受乘数B每三位信号，根据基4-Booth编码得到输出控制信号zero(部分积为零)、one(被乘数不变)、two(被乘数左移)、neg1(被乘数取反+1)、neg2(被乘数左移取反+1)。根据2.4小节中对基4-Booth编码推导介绍很容易编写Verilog代码。

3.2 部分积生成模块

部分积生成模块负责接受Booth编码器产生的控制信号和被乘数，计算产生相应的部分积，根据2.4小节的介绍可得Verilog代码。

3.3 Wallace树模块

根据2.5小节中的介绍，Wallace树由六组、每组32个全加器组成，其中全加器Verilog代码。

每组由32个全加器组成，其Verilog代码。

最终的Wallace树模块由6组CarrySerialAdder组成，Verilog代码。

3.4 顶层模块

在顶层模块中例化8个Booth编码器模块、8个部分积生成模块、Wallace树模块并进行连接得到顶层模块的Verilog代码。

Vivado RTL analysis结果如下图所示，可以符合设计预期。

可以看出顶层模块连接关系正确。

可以看出Booth编码器模块的正确性。

可以看出部分积生成模块的正确性。

可以看出Wallace树模块的正确性。

4. RTL仿真结果

4.1 测试用例1：输入16’b0110000010000000（十进制24704）和16’b1000000000000001（十进制-32767），输出32’b11001111110000000110000010000000（十进制-809475068）。

4.2 测试用例2：采用$random系统函数随机生成16位乘数和被乘数，并计算预期乘积并与乘法器仿真结果对比。

仿真波形如下：其中right_flag=(product==expected_product)?1’b1:1’b0;用于对比预期输出和乘法器仿真输出。

从波形可以看出本文的基于Booth编码和Wallce树的乘法器设计功能正确。

参考与致谢

1. 《高等数字集成电路分析与设计》第5章PPT，中国科学院大学
   2.【IC设计】【前端到后端全流程】【基于Booth2算法的32位乘法器】3-Booth算法与Booth2算法讲解以及RTL设计
   3.【HDL系列】乘法器(6)——Radix-4 Booth乘法器
   4.【HDL系列】乘法器(4)——图解Wallace树