基于改进的Booth编码和Wallace树的乘法器优化设计

石　敏　王　耿　易清明

(暨南大学信息科学技术学院　广东 广州 510632)



基于改进的Booth编码和Wallace树的乘法器优化设计

石敏王耿易清明

(暨南大学信息科学技术学院广东 广州 510632)

摘要针对当前乘法器设计难于兼顾路径延时和版图面积的问题，设计一种新型的32位有符号数乘法器结构。其特点是：采用改进的Booth编码，生成排列规则的部分积阵列，所产生的电路相比于传统的方法减小了延时与面积；采用由改进的4-2压缩器和3-2压缩器相结合的新型Wallace树压缩结构，将17个部分积压缩为2个部分积只需经过10级异或门延时，有效地提高了乘法运算的速度。设计使用FPGA开发板进行测试，并采用基于SMIC 0.18 μm的标准单元工艺进行综合，综合结果显示芯片面积为0.1127 mm2，关键路径延时为3.4 ns。实验结果表明，改进后的乘法器既减少了关键路径延时，又缩小了版图面积。

关键词乘法器Booth编码部分积阵列Wallace树

0引言

乘法器是进行数字信号处理的核心，同时也是微处理器中进行数据处理的关键部件。其运行速度基本决定了微处理器的速度，故乘法器速度和面积的优化对于整个CPU的性能来说是非常重要的。乘法器的设计过程中，最关键的就是部分积的产生和部分积的压缩，与其相关的技术为Booth编码和Wallace树型结构[1]。

目前，许多研究针对Booth编码和部分积的压缩提出了改进措施[2-6]。例如，文献[3]通过采用选择器结构来替换传统的与或门，提高了部分积电路的性能；文献[4]为了减少信号翻转率，重新设计了Booth编码电路，降低了功耗；文献[5]通过简化部分积产生电路，减小了版图面积。以上分别就电路结构对部分积生成电路进行了改进，改进后的电路优化了版图面积，但是也增加了不必要的门延时。文献[6]将部分积分拆重组，改进后的重组模块有利于部分积的快速压缩，但也因此增加了版图面积。乘法器的设计一直以来都是在面积和速度中去权衡，往往很难两者兼顾。本文为了设计面积速度优化的乘法器，针对传统的Booth算法进行了改进，通过调整扩展位的位置，设计出排列规则的部分积阵列结构，并提出了新型的Wallace树型结构，既优化了版图面积又缩短了关键路径延时。

1乘法器结构

该乘法器用作两个32位符号数的乘法运算，主要包括三部分：部分积产生模块、部分积压缩模块、最后两组部分积的快速求和模块。乘法器的结构如图1所示。

图1　乘法器的整体结构

为了得到有利于进行树型结构压缩的部分积阵列，本文对Booth编码进行改进，两个32位的二进制数送入部分积产生模块中，会产生一个由17个部分积组成的排列紧凑规则的阵列。对此部分积阵列进行快速压缩的是新型的Wallace树结构，该结构根据部分积的数量，将优化的4-2压缩器[7]和3-2压缩器重新排列，组成的压缩结构资源消耗少而且关键延时小。

2改进的Booth编码算法

本文设计的Booth编码电路相较于传统的方法会多产生一个部分积，虽然增加了部分积的个数，但却简化了每个部分积的符号扩展位。最终生成的部分积阵列主要由两部分组成：一部分是32位的部分积PP；另外一部分是部分积的扩展补充位：符号扩展位S，求补时需要的加1位C。其排列方式使部分积阵列更加紧凑规则。

2.1部分积的生成

基4的Booth编码算法对乘数重新编码，并且产生四个相应的控制信号，如表1所示。对于32位的乘数，在最低位补一个0后变为33位数，按照每三位作为一组，每两组重叠一位的方式进行分组，将乘数分成了16组。对每组按表1的方式重新编码，表中X表示乘数，Y表示被乘数，NEG、Z、B1、B2表示控制信号[8]。

表1　基4的Booth编码

表1中+1与+2分别表示被乘数的1倍和2倍，-1与-2分别表示减去1倍的被乘数和2倍的被乘数，即被乘数1倍求反加1和被乘数2倍求反加1。根据真值表得到各控制信号的表达式为：

(1)

根据以上控制信号可以通过译码电路得到部分积PPj，参照文献[2]提出的部分积产生电路，可以得到其表达式为：

(2)

通过以上表达式可以得到16个32位部分积的高31位，部分积的最低位可由以下式子得到：

PP0=Y0·(X2i⊕X2i-1)

(3)

本文将32位的部分积分成两个部分，一部分是高31位，另一部分是最低位第0位。相比于部分积都由同一个Booth编码电路得到的方法，将部分积的最低位通过单独、更简单的电路得到的方法更节省资源。

2.2改进的部分积阵列

生成的部分积为了便于树型结构的压缩，往往会排成阵列的形式，越是占用面积少的部分积阵列，越能节省资源的消耗，同时排列规则的部分积也有利于下一步的快速压缩。而部分积的排列往往会受其他扩充位的影响，例如符号位和求补时的取反加1位。

在Booth编码中对被乘数的-2×Y和-1×Y的操作，是采取对被乘数的所有位数取反加1这种方法。其中的加1操作如果在被乘数取反之后立即执行，就会增加部分积生成的延时，从而影响整个乘法的运算速度。对于这个加1操作，文献[6]采取的方法是把这个加1位保留至与本部分积最低位对齐的下一行部分积中去，相当于给下一行的部分积同时增加了低两位。这种方法可以减小部分积生成过程中的延迟，但是并未使部分积的排列最紧凑、最节省资源。

为了避免这一缺陷，本文将部分积求补时的加1位C置于紧挨下一行部分积的第0位处，形成该部分积新的最低位，按此方法排列的部分积如图2所示。

图2　部分积的排列方式

相比于文献[6]，这样做的好处是减少了每个部分积的位数，从而缩小了部分积阵列的面积。移位后的求反加1位C不再仅仅与乘数有关，还和被乘数Y的最低位有关，其取值由图3的电路得到。

图3　部分积求补加1位的生成电路

由于基于Booth编码的乘法器处理的是有符号数的乘法运算，因此部分积中的数据均为补码形式。在部分积的加法运算中，扩展的符号位要消耗相当大的硬件资源，以图2中的第一行部分积为例，这个32位的部分积需要从[31∶0]扩展到[63∶0]，[63∶32]全部为该部分积原来的最高位PP[31]。如果再把所有的这些符号扩展位相加，将会消耗大量资源，所以有必要对部分积的符号扩展位进行处理。

假设所有部分积都为负，即部分积的符号扩展位全为1，把这些扩展位按照图2所示的对齐方式进行相加，得到总和为一个32位的二进制数：10101010101010101010101010101011。此32位数位于部分积阵列的最后一行，作为第17个部分积[9]。此时文献[9]对每个部分积的符号扩展位S的操作是将部分积最高位取反作为S的值，S的值取决于部分积的值，只有得到了部分积才能求得S，这样会增加部分积阵列生成的延时。

本文提出一种新的方法来求得部分积的符号扩展位S，其电路图如图4所示。

图4　部分积符号扩展位的生成电路

采用此方法的符号扩展位S的值只依赖于被乘数的最高位和乘数，能与部分积同时求得，节省了部分积阵列生成的时间，能够尽快进入乘法运算的下一个步骤——部分积的压缩。

3改进的Wallace树压缩结构

Wallace树型压缩结构的核心是压缩器，常见的有3-2压缩器，即进位保留加法器CSA(Carry Save Adder)，和压缩比为二比一的4-2压缩器[10]。若仅采用CSA模块作为压缩结构的基本单元，则会增加压缩电路的路径延时；若仅采用4-2压缩器作为压缩结构的基本单元，则会增加资源的消耗。为了兼顾两种压缩器的优点，本文采用CSA与4-2压缩器相混合的树型压缩结构。

3.1压缩器的分析与优化

CSA即带进位的一位全加器，其关键路径上有2个XOR门的延时。通常4-2压缩器由两个3-2压缩器实现[11]，其逻辑表达式为：

Sum=A⊕B⊕C⊕D⊕Cin

(4)

Carry=(A⊕B⊕C)D+(A⊕B⊕C)Cin+DCin

(5)

Cout=AB+AC+BC

(6)

由两个3-2压缩器组成的4-2压缩器在关键路径上需要4个XOR门的延时，而且输入的信号不是同时参与运算，累加过程容易产生问题。基于对传统的4-2压缩器逻辑表达式的研究，可以对其电路进行化简，得到以下简化的逻辑表达式：

(7)

(8)

优化后的4-2压缩器如图5所示，通过此4-2压缩器得到Sum的关键路径延时为3个XOR门延时，比传统4-2压缩器少了1个XOR门的延时[12]。

图5　优化后的4-2压缩器逻辑电路图

3.2树型结构的分析比较

由于该乘法器中总共有17个部分积，如果完全采用3-2压缩器对部分积进行相加，则需要通过6级CSA才能将17个部分积压缩成两个部分积；如果完全采用4-2压缩器对部分积进行相加，则需要通过4级4-2压缩器压缩得到两个部分积。最后将压缩得到的两个部分积通过超前进位加法器进行相加，就可以得到最终的结果。

文献[3,5]采用的是基于CSA和4-2压缩器相混合的Wallace树结构。第一级采用6个CSA压缩得到8个部分积，第二级采用3个4-2压缩器将8个部分积压缩成6个，第三级采用2个CSA将6个部分积压缩成4个，第四级采用1个4-2压缩器压缩4个部分积至最终的2个。此结构将17个部分积压缩成2个部分积经过了2级CSA延时和2级4-2压缩器的延时，相比于单独使用3-2压缩器或4-2压缩器构成的Wallace树结构，节约了两级异或门的延迟。

为了进一步节省资源的消耗，本文设计出新的Wallace树结构如图6所示，P0～P16为经过改进的Booth编码电路产生的17个部分积。

图6　本文提出的Wallace树压缩结构

此结构与文献[3,5]的树结构在压缩部分积时具有相同的延迟。但是相比于后者，本文提出的Wallace树结构比后者多一个CSA模块，少一个4-2压缩器模块。由于全加器的结构比4-2压缩器简单的多，需要的逻辑资源少于4-2压缩器，所以总体上本文的树结构更节省资源。综合比较这四种不同的Wallace树结构，其需要消耗的压缩单元数量及关键延时如表2所示。

表2　四种树型结构的比较

虽然表2中四种树结构采用的是相同的CSA单元和4-2压缩单元，但其关键延时和消耗资源情况各不相同。通过表2列出的数据可以清楚地看到，本文提出的Wallace树结构关键延时和消耗的压缩单元都是最少的。

4实验结果及性能分析

本文设计的乘法器采用Verilog HDL语言进行描述，并通过Modelsim软件进行功能仿真。通过编写测试激励文件，使用随机数函数产生32位符号数的测试数据，其取值范围为-2 147 483 648～2 147 483 647。将测试数据a和b输入到本文设计的乘法器和Altera的乘法器IP核中，对比两组乘法运算的结果，若不一致则输出错误信号error为1。对300万组测试数据的仿真结果显示两者得到的乘积完全一致，图7为部分仿真的对比结果，每个时钟上升沿产生前一组数据的乘积。

图7　功能仿真图

设计采用Altera公司的EP4CE30F23C7为目标芯片，综合结果显示使用了2426个逻辑单元，相较于传统乘法器减少了逻辑单元的消耗。采用基于SMIC的0.18 μm标准库，使用Synopsys的Design Compiler进行综合，将综合结果与其他的设计方法进行比较，结果如表3所示。

表3　乘法器性能比较

从表3中可以看出，本文设计的乘法器相较于文献[7,11]，速度分别提高了19%和5%，面积分别缩小了30%和16%，关键路径延时和面积都得到了极大的优化和提升。

5结语

本文通过对传统Booth编码和Wallace树型结构的深入研究，设计了一种32位有符号数的乘法器。对各级电路结构进行了优化改进，提出了改进的Booth编码算法，得到排列规则版图整齐的部分积阵列，减少了部分积产生的延时，并且用一种新颖的Wallace树压缩结构节省了资源的消耗。最后通过实验表明了本设计的优越性，相比于其他文献中的方法，总体上减少了乘法器的延时与面积，使乘法器的性能得到了优化。

参考文献

[1] 赵忠民.64位高性能嵌入式CPU中乘法器单元的设计与实现[D].同济大学,2007.

[2] Yeh Wenchang,Jen Cheinwei.High-speed Booth encoded parallel multiplier design[J].Computers,IEEE Transactions on,2000,49(7):692-701.

[3] 李康,林钰凯,马佩军,等.基于部分积优化的高速并行乘法器实现[J].微电子学与计算机,2011,28(1):61-63,68.

[4] 何军,朱英.一种64位Booth乘法器的设计与优化[J].计算机工程,2012,38(16):253-254.

[5] 翟召岳,韩志刚.基于Booth算法的32位流水线型乘法器设计[J].微电子学与计算机,2014,31(3):146-149.

[6] 陈海民,李峥,谢铁顿.基于Radix-4Booth编码的乘法器优化设计[J]. 计算机工程,2012,38(1):233-235.

[7] 朱鑫标,施隆照.一种高压缩Wallace树的快速乘法器设计[J].微电子学与计算机,2013,30(2):46-49.

[8] Muralidharan R,Chang Chiphong.Radix-4 and radix-8 Booth encoded multi-modulus multipliers[J].Circuits and Systems I: Regular Papers,IEEE Transactions on,2013,60(11):2940-2952.

[9] 曾宪恺,郑丹丹,严晓浪,等.基于标准单元库扩展的快速乘法器设计[J].计算机应用研究,2012,29(5):1778-1780,1814.

[10] 管幸福,余宁梅,路伟.一种wallace树压缩器硬件结构的实现[J].计算机工程与应用,2011,47(23):76-78,83.

[11] 李飞雄,蒋林.一种结构新颖的流水线Booth乘法器设计[J].电子科技,2013,26(8):46-48,67.

[12] 王仁平,何明华,魏榕山,等.32×32高性能乘法器的全定制设计[J].福州大学学报:自然科学版,2012,40(5):602-608.

AN OPTIMISED DESIGN OF MULTIPLIER BASED ON IMPROVED BOOTH ENCODING AND WALLACE TREE

Shi MinWang GengYi Qingming

(SchoolofInformationScienceandTechnology,JinanUniversity,Guangzhou510632,Guangdong,China)

AbstractAccording to the problem that multiplier can’t take into account both the path delay and layout area, we proposed a novel structure of 32 bit signed multiplier. Its characteristics are: the multiplier uses the improved Booth encoding to generate a partial product array ranging regularly, and the circuit it brought forth reduces the delay and area compared with traditional method; it employs the improved novel Wallace tree compressing structure which is the combination of 4-2 compressor and 3-2 compressor, and to compress 17 partial products into 2 ones only needs 10 XOR-delays, thus speeds up multiplication computation considerably. The whole design was verified on FPGA, and synthesised with SMIC 0.18 μm-based standard unit process. Synthesis results showed that the chip area was 0.1127 mm2, and the key path delay was 3.4 ns. Experimental results also showed that the improved multiplier reduced both the key path delay and the layout area.

KeywordsMultiplierBooth encodingPartial product arrayWallace tree

收稿日期：2014-11-28。广东省工程技术研究中心项目(2012gczx A003)。石敏，副教授，主研领域：图像处理，SoC设计。王耿，硕士生。易清明，教授。

中图分类号TP332

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.05.004