乘法是数字信号处理中重要的基本运算。在图像、语音、加密等数字信号处理领域,乘法器扮演着重要的角色,并在很大程度上左右着系统性能。随着实时信号处理的提出和集成电路工艺水平的进步,人们开始致力于高速乘法器设计。
   
     最初,阵列乘法采用移位与求和算法,部分乘积项(Partial Product, PP)数目决定了求和运算的次数,直接影响乘法器的速度。修正布斯算法(Modified Booth Algorithm, MBA)对乘数重新编码,以压缩PP。华莱士树(Wallace Tree, WT)结构改变求和方式,将求和级数从O(N)降为O(logN),提高了运算速度,但是WT存在结构不规整,布线困难的缺点。用4:2压缩器(4: 2 compressor)代替全加器(FA)可以解决这一问题。将MBA算法和WT结构的优点相结合,形成了MBA-WT乘法器。
   
    以下1～4节将分别介绍阵列乘法器、MBA乘法器、WT乘法器、MBA?WT乘法器。最后对四种乘法器的性能进行比较,并总结全文。 
      
1 阵列乘法器    
     阵列乘法器基于移位与求和算法。被乘数与乘数中的某一位相乘,产生一组PP,将该组PP移位,使LSB与乘数对应位对齐;求出全部PP,并相应移位;对所有PP求和,得到乘积。因此,加法阵列结构非常重要。CRA (Carry Ripple Adder)存在进位问题,运算速度慢。CSA  (Carry Save Adder)将本级进位传至下级,求和速度快,且速度与字长无关。阵列乘法器中,CSA把PP阵列缩减至Sum和Carry两项,再用高速加法器求和得积。阵列乘法器结构规范,利于布局布线。
   
    因为乘数和被乘数可正、可负,所以一般用二进制补码表示,以简化加、减运算。补码运算需要符号扩展,符号扩展宽度与加法器结构有关。对于CRA,加数和被加数符号扩展至本级和的最高位;对于CSA,扩展至两数最高位对齐。符号扩展增加了符号位扇出,使电容负载不平衡,影响电路整体速度;需要冗余的加法器,扩大了版图面积。符号扩展问题可用以下算法解决［1］。假设P1=A、P2=B,求A+B: ① 将A符号位扩展一位,对扩展位取反;② 将B符号位取反;③ 在B符号位左边添1;④ 求和。
   
    假设两个6位部分积A、B相加,需扩展一位符号位,如图1(a)所示;采用新算法后,计算式如图1(b)所示;相应6×6乘法器电路如图1(c)所示。
 

2 MBA乘法器    
    求和是乘法运算中最耗时步骤。缩减PP数目是提高乘法运算速度的方法之一。阵列乘法中PP数目与乘数位数相等。MBA算法通过对乘数重新编码,压缩PP数目,以提高运算速度。压缩率取决于编码方法,如果采用三位编码,可压缩一半PP。考虑到编码电路的引入,乘法器速度的提高是有限的。基于MBA的乘法器架构如图2所示。
 
    MBA算法描述如下:假设A为被乘数、B为乘数,均采用二进制补码表示:
 
    按式(3),对乘数B重新编码,编码后B可用式(4)表示。
 
    (n为偶数;若n为奇数,则B符号扩展一位)
     
    如式(5)所示,A×B运算所需加?法次数减少了一半。注意,求和时,Ki+1A相对于KiA需左移两位。

3 WT乘法器    
    树型结构可以减少求和级数,是提高乘法运算速度的另一方法。1961年,Wallace提出的WT结构是其中最著名的一种。它对于16位以上的乘法运算尤其适用。
   
    WT 结构,将全部PP按列分组,每列对应一组加法器,各列同时相加,前列进位传至后列,生成新PP阵列;同法,化简新阵列,直至只剩两行PP;最后用高速加法器求和得积。WT结构优点在于只需做O(logN)次加法,因而运算速度快。6×6 WT乘法器如图3所示。在WT结构基础上,通过对PP划分的优化,可以进一步减少求和级数［2］。
 
    注意到FA不同输入端到同一输出端的路径延时不同,不同端口在时序上应区别对待。例如,两个FA的两种级联方式:最长路径+最长路径、最长路径+最短路径。后者关键路径小于前者,有利于提高速度。在利用FA构建WT时,可以采用一种算法［3］使WT的最长路径最短。缺乏规整性,布线困难,是 WT结构最大的不足。引线的延长导致寄生电容增加,妨碍了电路速度的进一步提高。针对这一问题,Weinberger提出了基于4∶2缩减器的乘法器架构,其最大优点在于电路简单,连线规则。4∶2缩减器可由FA构成,见图4(a);也可进行逻辑优化,见图4(b)。
 
   
4 MBA-WT混合乘法器    
    高速乘法器可同时采用MBA算法和WT结构,如图5所示。首先,MBA算法把乘法运算N×M的PP压缩1／2;然后,WT结构将PP按列分组,并行约减,直至PP阵列只剩余两行;最后由高速加法器求和得积。 
 
    因为WT结构中所有PP同时相加,所以符号位要扩展至M+N位。这将花费大量硬件资源,并且严重影响运算速度。符号扩展问题可由以下方法解决［4］。假设部分积均为负数,可以预求所有扩展符号位之和
 
    如果某一部分积为正数,再进行修正:将部分积的符号位s由0变成1就可以抵消预测的影响。此方法较好的解决了符号扩展问题,提高了运算速度,并且硬件开销很小。 
    
5 性能比较及总结    
    A. J. Al-Kbalili和N. Zaman利用FPGA,分别综合了基于以上四种架构的32×32乘法器,并比较了乘法器在面积、延时和功耗方面的性能参数,如表1所示［5］。
 
    阵列乘法器面积小、功耗小,运算速度慢;WT乘法器和MBA-WT乘法器运算速度快,但功耗较大,WT乘法器面积最大,MBA-WT乘法器面积略大于阵列乘法器;MBA乘法器各项参数介于前三种乘法器之间。不同乘法器架构在性能上都存在优点和缺点。选择乘法器时,必须根据应用场合的要求,在面积、延时和功耗等方面综合考虑。
    
参考文献
    [1] Salomon O, Green J M, and Klar H, General Algorithms for a Simplified Addition of 2’s Complement Numbers. IEEE JSSC, July 1995;30(7):839-844   
    [2] Robinson M E, Swartzlander E. A Reduction Scheme to Optimize the Wallace Multiplier In:Proc ICCD'98, 1998;122-127   
    [3] Oklobdzija V G. A Method for Speed Optimized Partial Product Reduction and Generation of Fast Parallel Multipliers Using an Algorithmic Approach. IEEE Trans Comp, Match 1996;45(3):294-305   
    [4] Ardekani J F. M×N Booth Encoded Multiplier Generator Using OptimizedWallace Trees . IEEE Trans VLSI systems, Jun 1993;1(2):120-125   
    [5] Al?Khalili A J. 32?bit Constant(k) Coefficient Multiplier In:Proc EE Tech, 2001