胡薇++崔晓平++陈鑫

摘 要： 冗余二进制（RB）加法的进位无关特性和规整的压缩结构，可以设计高速冗余二进制乘法器。冗余二进制乘法器由RB部分积产生、RB部分积压缩树和RB?二进制数转换器三个关键模块构成。在此基于基?16 RB Booth编码结构提出了一种由进位跳跃加法器和并行前缀/进位选择混合加法器构成的冗余二进制?二进制数转换器。用Verilog HDL对该转换器进行描述，在Synopsys的VCS平台上进行仿真验证，在SMIC 45 nm的工艺下，通过Design Compiler 对转换器进行综合，比较普通的并行前缀/进位选择转换器，设计的64位转换器在延时、面积和功耗得到有效的改善。

关键词： RB?NB转换器； 并行前缀加法器； 进位跳跃加法器； 冗余二进制乘法器

中图分类号： TN710?34 文献标识码： A 文章编号： 1004?373X（2015）10?0103?04

0 引 言

乘法器作为高速数字信号处理器（DSP）、微处理器、RISC和FIR数字滤波器等各类芯片中的必不可少的运算逻辑单元，其性能的好坏对整个芯片系统有着极其重大的影响。因此，高速、低耗乘法器的设计一直是研究重点。乘法器能被分成3个步骤：

（1） 部分积的产生；

（2） 由部分积压缩树将所有的部分积压缩至二行；

（3） 通过快速的二进制加法器将最终的二行部分积相加得到乘积。

冗余二进制（Redundant Binary，RB）数由Avizients最早提出的一种有符号数的表示方法[1]，利用冗余二进制算法的进位无关特性以及规整的结构，可以设计出高速的RB并行乘法器[2?6]。RB并行乘法器主要由RB部分积产生、RB部分积压缩树和RB?NB转换器3个关键模块构成。与一般二进制（Normal Binary，NB）乘法器相类似，RB乘法器首先采用修正Booth算法（MBE）[7]将部分积的数目减少一半并将两个相邻的二行NB部分积转换为一行RB部分积，然后采用由RB半加器和RB全加器构成的RB部分积压缩树将RB部分积压缩至一行，最终采用RB?NB转换器[8?10]将RB部分积转换成NB乘积。由RB并行乘法器的结构可以看出，RB?NB转换器处于整个RB乘法器的关键路径上，它的性能对于整个乘法器的性能有着至关重要的影响。

RB部分积的产生过程中会产生一行修正字。由MBE算法产生部分积时，当被乘数需要乘以-1或-2时，需要对被乘数取反，然后在部分积的最低位加1，因此产生+1修正值。当两行相邻的NB部分积构成一行RB部分积时，产生[-1]修正值。将修正 Booth编码和RB编码产生的修正值合并成一行修正字，可以一次性完成纠错。对于N位权2字长N=2n的乘法器，共产生[N4]个RB部分积和额外的一行修正字，将[N4+1]个RB部分积，经[log2N4+1=n-2]级压缩后得到一行冗余二进制数[2?6]。因此对于2n位乘法器，额外的一行修正字增加了一级压缩，去除该行修正字可以减少一级压缩，因此可以提高乘法器的速度并减少功耗。

比修正Booth编码（又称之为基?4 Booth编码）更高级的Booth编码可以进一步减少部分积的个数，但是是以增加难倍数的数目为代价[11?13]。一个难倍数是指不是权2的倍数（例如3，5，6，7），因此对应的部分积不能用简单地左移和取补得到。文献[13]提出由2个权2倍数的差来获得难倍数（例如±3M=±（4M-1M），±6M=±（8M-2M）。文献[12]提出了一个新的基-16 RB Booth编码算法用来产生RB部分积，该算法可以避免高级Booth编码的难倍数并且不产生额外的一行修正字。本文提出的64位RB?NB转换器适用于消除修正字的RB Booth编码乘法器。

RB?NB转换器和加法器的硬件电路结构是类似的[8?10，14]，因此定点加法器的结构可以被应用到RB?NB转换器上。在64位基于基-16 RB Booth编码的乘法器设计中，由于RB部分积压缩后生成的RB数是逐级压缩产生的，先产生的16位RB部分积采用结构简单的进位跳跃加法器（Carry?Skip Adder，CSKA）完成转换，最终产生的48位RB数采用并行前缀/进位选择混合加法器的结构，最终得到一种新的进位跳跃、并行前缀/进位选择混合的RB?NB转换器。

用Verilog HDL对该转换器进行描述，在Synopsys的VCS平台上进行仿真验证，在SMIC 45 nm的工艺下，通过Design Compiler 对转换器进行综合。比较普通的并行前缀/进位选择转换器，建议的64位RB?NB转换器在延时、面积和功耗得到有效的改善。

1 RB?NB转换器与加法器

下面介绍一种RB?NB转换器与加法器之间的映射关系，并且以此类推出所有加法器的硬件结构可以被应用到RB?NB转换器上。

假设两个n位二进制数A、B组成一行RB数（A?B），其中[A=i=0n-1ai2i， B=i=0n-1bi2i， ai，bi∈{1，0} ；]设第i位的RB数 [ri=ai-bi]，可以得到式（1）：

[A-B =i=0n-1（ai-bi）2i =i=0n-1ri2i， ri∈{-1，0，1}] （1）

可以得到RB?NB转换方式。

同理，假设两个n位正二进制数A、B相加（A+B），其中[A=i=0n-1ai2i， B=i=0n-1bi2i， ai，bi∈{1，0} ；]设[ni=ai+bi]，可以得到式（2）：

[A+B =i=0n-1（ai+bi）2i =i=0n-1ni2i， ni∈{0，1，2}] （2）

可以得到两个正NB数相加的编码方式。

RB?NB转换方式以及正NB数相加编码方式如表1所示，ni和ri之间存在箭头方向所示的映射关系：ni=1-ri。由ni和ri之间映射关系对ni和ri查找编码表可以反推得到两种编码之间的映射关系为：x+位不变，x-位取反，如表2所示。由此可知，二进制加法器中的所有结构都可以用于构成RB?NB转换器，由RB?NB转换器到加法器的映射关系，其他位不变，x-位取反，即在整个转换设计中，反相器是惟一需要添加的硬件，也就是说，加法器的硬件结构都可以被应用到RB?NB转换器上来。endprint

表1 编码表

表2 映射关系表

第i位RB?NB转换真值表[7]如表3所示。

表3 RB?NB转换真值表

根据表3，可以得到[si]和[ci+1]的逻辑表达式如式（3）和式（4）所示：

[si=ci⊕x-i⊕x+i ] （3）

[ci+1=x-i+x+i+x-ix+i ?ci] （4）

从逻辑表达式（4）可以得出，加法器的电路结构可以用于RB?NB转换器的设计中，其进位产生信号是[Gi=x-i+x+i]，进位传递信号是[Pi=x-i?x+i]。

2 经典加法器的原理

加法器是最通用的算术运算，是计算机中最基本的运算单元，有着极其广泛的应用。在计算速度要求的推动下，各种高性能的加法运算不断被推出。经典的加法器结构包括行波进位加法器（Carry?Ripple Adder，CRA）、进位跳跃加法器（Carry?Skip Adder，CSKA）、进位选择加法器（Carry Select Adder）、超前进位加法器（Carry Look?ahead Adder，CLA）和并行前缀加法器（Parallel Prefix Adder，PPA）等[15?20]。其中最简单的加法器是CRA，其速度也是最慢的，CLA能够有效的提高进位传播的速度，进位跳跃加法器和进位选择加法器的进位传播的速度居于两者中间，他们的结构相较于CLA来说相对简单，PPA可以看成是CLA的改进结构。下面分别对进位跳跃加法器和并行前缀加法器做具体的分析。

假设两个n位二进制数A和B相加，其第i位的被加数和加数分别为ai和bi，ci是低位的进位输入，则该位的进位产生信号gi、进位传递信号pi、和和位si以及向高位的进位输出信号ci+1由式（5）表示：

[gi =aibi pi =ai+bi si =ai⊕bi⊕ci ci+1=gi+pici ] （5）

4位进位跳跃加法器的进位输出可以由式（6）表示如下：

[ci+4=gi+3+pi+3ci+3 =gi+3+pi+3gi+2+pi+3pi+2gi+1 +pi+3pi+2pi+1gi+pi+3pi+2pi+1pici =Gi+3：i+Pi+3：ici] （6）

式中：Gi+3：i是4位加法器的方块进位产生信号；Pi+3：i是4位加法器的方块进位传递信号。4位进位跳跃加法器的结构如图1所示，它由一个4位CRA模块外加一个4输入的与门和一个二选一的数据选择器组成。与门用来产生i～i+3位的方块进位传递信号Pi+3：i=pi+3pi+2pi+1pi，当ci=0，初始化的方块进位输出值ci+4′=Gi+3：i。当进位输入信号产生时且方块的初始化进位输出信号稳定后，进位输出信号ci+4较进位输入信号有一个二选一数据选择器的延时时间。将多个4位进位跳跃加法器级联起来可以以低的复杂度获得较快的加法运算[19]。

定义一种运算，其运算符为“[?]”。运算规则为：

[（gi，pi）?（gi-1，pi-1）=（gi+pigi-1 ， pi-1pi）] （7）

则：

[（Gi：0，Pi：0）=（gi，pi）?（gi-1，pi-1）?????（g1，p1）?（g0，p0）] （8）

由式（5）可得第i位的进位输出信号为：

[ci+1=gi+pi·ci=gi+pi·（gi-1+pi-1·（gi-2+ pi-2·（gi-3+pi-3·（…+p0·cin）））） =gi+pi·gi-1+pi·pi-1·（gi-2+pi-2·（gi-3+pi-3· （…+p0·cin））） =Gi：0+Pi：0·cin] （9）

由式（8），式（9）可以看出，（Gi：0，Pi：0）可以由若干个式（7）所示的“[?]”运算级联得到。这就是并行前缀结构的运算原理，“[?]”运算被称为并行前缀运算。

图1 4位进位跳跃加法器方块

并行前缀加法器（PPA）可以看成是超前进位加法器的改进版，它通过前缀运算单元进行运算，每个前缀运算单元产生两个信号：进位产生信号和进位传递信号。将每个前缀运算单元以递归的方式连接起来，产生的进位信号与被加数和加数一起异或运算求和即可构成并行前缀加法器。运算时间方面，并行前缀结构最快只需要log2 n级前缀运算即可完成进位输出。从实现的角度看，并行前缀加法器将许多相同的前缀运算单元采用树形结构连接而成，因此有着规整的结构，易于VLSI设计。

3 64位RB?NB转换器的优化设计

采用基?16 RB Booth编码，32位冗余二进制乘法器产生8个RB部分积，经3级压缩（8→4→2→1）后得到一个冗余二进制数，最后通过64位RB?NB转换器得到二进制数的乘积。为了提高转换器的性能，64位RB?NB转换器采用进位跳跃、并行前缀/进位选择混合的二进制加法器进行设计。该转换器由16位进位跳跃加法器和48位并行前缀/进位选择混合加法器构成。

RB部分积产生模块由基?16 RB Booth编码电路和解码电路构成，最终一行RB部分积的0～3位由Booth 解码电路直接输出，4～7位由第一级压缩得到，8～15位由第二级压缩得到，其余的48位RB部分积由第三级部分积压缩的输出得到。根据先产生先求和的原则，低16位RB数首先逐级进行转换，如果在高48位RB部分积产生之前，0～15位RB部分积已转换完成，则转换器的延时时间仅仅取决于高48位RB部分积的转换时间。

16位进位跳跃加法器的结构图如图2所示，由于RB部分积的0～3 位由Booth 解码电路直接输出，它仅需1个4位CRA和3个4位CSKA模块级联即可。初始的一级为1个4位CRA，如果Δg表示进位产生信号的延时时间，Δp表示gi+pici（或一级前缀运算）的延时时间。则4位CRA进位输出信号的延时时间为Δg+3Δp，每多出一个4位CSKA模块则增加一个二选一数据选择器的延时，因此16位进位跳跃加法器的进位输出信号的延时时间为Δg+6Δp。为了加快该加法器的速度，每个4位行波进位加法器内部采用由与或非和或与非门构成互补的进位输出。

图2 4个4位进位跳跃加法器级联

在加法器的众多树形结构中，Kogge?Stone （KS）树是理论上最快的树形结构，对于一个n位的加法，最终进位信号只需要log2 n级延时即可产生。如图3所示，高48位转换器选取基于KS优化结构的并行前缀/进位选择混合加法器结构。

图3 设计的RB?NB转换器结构图

与普通的并行前缀/进位选择混合加法器构成的RB?NB转换器相比，建议的 RB?NB转换器的低16位采用改进的进位跳跃加法器，其复杂度和延时得到有效的改善。为了得到建议的64位RB?NB转换器和并行前缀/进位选择混合加法器的延时、面积和功耗，使用Verilog HDL语言对其进行描述并在VCS平台上进行仿真验证。在SMIC 45 nm CMOS标准工艺库下，通过Synopsys公司综合工具DC进行综合，最终得到64位RB?NB转换器的综合结果如表4 所示，优化过的转换器比普通的并行前缀/进位选择转换器在延时、功耗、面积方面分别优化了23.9%，13.0%，12.6%。

表4 64位RB?NB转换器综合结果

4 结 语

RB?NB转换器处于RB乘法器的关键路径上，它的性能对乘法器有着至关重要的影响。根据最终RB部分积生成的先后顺序，对先生成的低16位数采取复杂度比较低的电路结构以降低功耗，针对后生成的48位数据采用逻辑级数最少的KS结构的并行前缀加法器以减少延时，双管齐下，提高整个转换器的性能。在SMIC 45 nm CMOS标准工艺库下，通过Synopsys公司综合工具Design Compiler进行综合，64位RB?NB转换器的延时可达0.80 ns，功耗为327 μW，面积是1 639 μm2，与普通的并行前缀/进位选择转换器相比，这些指标分别优化了23.9%，13.0%，12.6%。

参考文献

[1] AVIZIENIS A. Signed?digit number representations for fast parallel arithmetic [J]. IRE Transactions on Electronic Computers， 1961， EC?10：389?400.

[2] TAKAGI N， YASUURA H， YAJIMA S. High?speed VLSI multiplication algorithm with a redundant binary addition tree [J]. IEEE Transactions on Computers， 1985， 100（9）： 789?796.

[3] EDAMATSU H， TANIGUCHI T， NISHIYAMA T， et al. A 33 MFLOPS floating point processor using redundant binary representation [C]// Proceedings of 1988 IEEE International Solid?State Circuits Conference. [S.l.]： IEEE， 1988： 152?159.

[4] MAKINO H， NAKASE Y， SUZUKI H， et al. An 8.8?ns 54×54?bit multiplier with high speed redundant binary architecture [J]. IEEE Journal of Solid?State Circuits， 1996， 31（6）： 773?783.

[5] KIM Y， SONG B S， GROSSPIETSCH J， et al. A carry?free 54b×54b multiplier using equivalent bit conversion algorithm [J]. IEEE Journal of Solid?State Circuits， 2001， 36（10）： 1538?1545.

[6] 崔晓平，高鹏辉，尹洁珺，等.54位高速冗余二进制乘法器的设计[J].微电子学与计算机，2014（4）：140?143.

[7] MACSORLEY O L. High?speed arithmetic in binary computers [J]. Proceedings of the IRE， 1961， 49（1）： 67?91.

[8] HE Y， CHANG C H. A power?delay efficient hybrid carry?lookahead/carry?select based redundant binary to two's complement converter [J]. IEEE Transactions on Circuits and Systems I： Regular Papers， 2008， 55（1）： 336?346.

[9] WANG G， TULL M P. A new redundant binary number to 2's?complement number converter [C]// Proceedings of 2004 Region 5 Conference： Annual Technical and Leadership Workshop. [S.l.]： IEEE， 2004： 141?143.

[10] YEN S M， LAIH C S， CHEN C H， et al. An efficient redundant?binary number to binary number converter [J]. IEEE Journal of Solid?State Circuits， 1992， 27（1）： 109?112.

[11] LYU C N， MATULA D W. Redundant binary booth recoding [C]// Proceedings of 1995 the 12th Symposium on Computer Arithmetic. [S.l.]： IEEE， 1995： 50?57.

[12] HE Y， CHANG C H， GU J， et al. A novel covalent redundant binary Booth encoder [C]// Proceedings of 2005 IEEE International Symposium on Circuits and Systems. [S.l.]： IEEE， 2005： 69?72.

[13] BESLI N， DESHMUKH R G. A novel redundant binary signed?digit （RBSD） Booth's encoding [C]// Proceedings of 2002 IEEE Southeast Conference. [S.l.]： IEEE， 2002： 426?431.

[14] BLAIR G M. The equivalence of twos?complement addition and the conversion of redundant?binary to twos?complement numbers [J]. IEEE Transactions on Circuits and Systems Part 1： Fundamental Theory and Applications， 1998， 45： 669?671.

[15] SKLANSKY J. Conditional?sum addition logic [J]. IRE Transactions on Electronic Computers， 1960 （2）： 226?231.

[16] KOGGE P M， STONE H S. A parallel algorithm for the efficient solution of a general class of recurrence equations [J]. IEEE Transactions on Computers， 1973， 100（8）： 786?793.

[17] BRENT R P， KUNG H T. A regular layout for parallel adders [J]. EEE Transactions on Computers 1982， 31： 34?41.

[18] DIMITRAKOPOULOS G， NIKOLOS D. High?speed parallel?prefix VLSI ling adders [J]. IEEE Transactions on Computers， 2005， 54（2）： 225?231.

[19] 崔晓平，王成华.二级进位跳跃加法器的优化方块分配[J].北京航空航天大学学报，2007，33（4）：495?499.endprint