董时华;乔庐峰
【摘 要】针对16位乘法器运算速度慢、硬件逻辑资源消耗大的问题,采用华莱士树压缩结构,通过对二阶布思算法、4-2压缩器和保留进位加法器的优化组合使用及对符号数采用合理的添、补、删策略,实现16位符号数快速乘法器的优化设计.该乘法器采用SMIC 0.18 μm工艺标准数字单元库,使用Synopsys Design Compiler综合实现,在1.8 V, 25℃条件下,芯片最大路径延时为3.16 ns,内核面积为 50 452.75 μm2,功耗为5.17 mW. 【期刊名称】《计算机工程》
【年(卷),期】2010(036)009
【总页数】3页(P252-254)
【关键词】安卓系统加速布思算法;4-2压缩器;保留进位加法器;跳跃进位加法器;华莱士树型结构
【作 者】董时华;乔庐峰
【作者单位】解放军理工大学通信工程学院,南京,210007;解放军理工大学通信工程学院,南京,210007
【正文语种】中 文
【中图分类】TN911.72
1 概述
在高速数字信号处理领域，高速乘法器扮演着越来越重要的角，在追求高速度、低功耗和面积最小化的集成电路设计中更显示出高性能乘法器的重要性。
二进制乘法器的设计实现可归结为3个步骤：(1)将二进制的被乘数与乘数的每一位相乘得到与乘数位数相同的部分积；(2)将部分积按权值相加，进行部分积压缩；(3)求和，将最终压缩得到的2个部分积求和，得到乘法运算结果。本文设计的16位快速符号数乘法器分别从这3个步骤入手，采用二阶布思算法使部分积个数减少一半，然后组合使用 4-2压缩器和保留进位加法器，压缩级数与文献[1]相比由5级缩小到3级，而与文献[2]中全用4-2压缩器相比，压缩级数虽都为3级，但使用的加法器的个数少了很多。在优化压缩结构上，立足于
整体考虑，使各级压缩器加法器个数和面积均有了进一步优化，同时在实现时，三级压缩结构间使用流水线结构，从而达到了高速度和低功耗的设计要求。
2 乘法器结构来电显示电话机
本乘法器提供16位二进制有符号与无符号乘法运算，为区分有符号与无符号，将乘数与被乘数均增加一个扩展位，若为有符号数则进行符号位扩展，若为无符号数则扩展为0。在乘法运算中，首先将被乘数符号位扩展，然后用改进的二阶布思算法对乘数进行编码同时生成部分积；在部分积的压缩中，因为各个部分积的权值不一样，必须根据需要进行符号位的扩展，同时还需在末尾做相应的补0操作，最后运用跳跃进位加法器求得位宽为32的乘法结果。
2.1 二阶布思算法
布思算法是乘法器中产生部分积最简单有效的编码方法，其编码优点主要有2点：(1)对符号数和无符号数采用统一的编码方式，只须做相应的符号位扩展即可；(2)可以使部分积数目大大缩减，直接减少华莱士树压缩的级数，从而提高乘法器的计算速度。在实际运用中
二阶布思算法实现简单方便，虽然三阶布思算法生成的部分积更少，理论上速度更快，但因其编码时会产生3倍的部分积，通过简单的移位已不能解决，需要引入加法器，复杂度大大增加，所以本文选用二阶布思算法。
二阶布思算法只能对偶数位乘数编码，所以编码前若乘数为奇数位则须将乘数扩展为偶数位。一个n位二进制符号数乘法的补码形式计算式可表示为：(先将n扩展为偶数位N，N不小于n)。X由每3位一组的相邻数据x2i+1,x2i,x2i-1进行重新编码，编码值为E＜i＞。除去相邻组间的重叠位，相当于由一阶布思算法中每位数据产生一个部分积优化为每2个数据产生1个部分积，直接将部分积数目减半。本文实际编码前需将最低位补0(即x-1=0)，最高位补2个符号位，编码值E＜i＞取值为0,1,2,-1,-2，E＜i＞的绝对值决定部分积的大小，可以通过移位实现，而E＜i＞的符号则决定生成部分积的符号，可以通过值取反再加1来实现，本文设计的16位乘法器的部分积经过二阶布思算法后由原来的16个减少为9个。
2.2 华莱士树型结构和压缩器
作为乘法器的另一个核心组成，部分积的压缩一直是设计的关键所在。树型乘法器的基本概念是由Wallace提出的，利用进位保留加法器(Carry Save Adder,CSA)通过并行地对部分
积进行按列压缩达到快速得出最终结果的目的。
Wallace最早提出的方案如下：
(1)将每3个部分积分为1组，每组通过使用全加器构成的CSA部件将加数的数目减少。
自动飞镖发射器防身(2)对前一步产生的结果仍按每3位1组的方式将同权的伪和与局部进位信号再通过CSA部件进行压缩处理，再次减少加数的数目，直至只有2个输出为止。
(3)对最终的伪和与局部进位通过进位传递加法器相加得出最终的乘法运算结果。在这种处理方式中，每列中求伪和的操作是并行完成的，采用CSA作为加法部件，每次能将3个操作数压缩为2个，这样操作数的数目减少了1/3。
对一位保留进位加法器，输入3 个数据：A,B和Ci；输出2个一位数据：D,Co。其中，Co的权值为2；A,B,Ci和D的权值为1。
其逻辑表达式如下：
疑难件近年来这种采用列压缩的树型乘法器有了很多的发展和改进。4-2压缩器构成的乘法器在总
体性能上较优，它能将4个输入压缩为 2个输出，并且低位的进位与向高位的进位间无延迟影响，压缩器间并行完成，所以，现在的乘法器大多采用4-2压缩器作为树型加法器的基本单元。
对于 4-2压缩器，输入 5个数 I0,I1,I2,I3,Ci；输出3个数D,Co,C，其逻辑表达式为
投饵机其中，C比D的权值高一位；Co的权值与C相同，为向高位的进位输出。
本设计根据部分积的个数合理地利用2种压缩器，从而使资源利用率最大。华莱士树结构如图1所示。布思算法生成的部分积只有9项，但用布思算法会产生一个伪进位。当编码值为-1或-2时，需将编码值取反后加 1，这里所加的1就是伪进位，而当编码值为0,1,2时该伪进位值是0。图1所示华莱士树中的P即为生成最高位部分积I8时所产生的伪进位值。这个伪进位值在实际中不能忽略，它直接会影响华莱士树结构。如图1所示的华莱士树结构组合使用 CSA和4-2压缩器只用了三级便将9个部分积压缩为2个值。当然，该华莱士树也可以全由4-2压缩器构成，同样只需三级结构，但实现时会发现相比上述结构耗用的全加器的位宽大了许多，所用加法器的个数明显增加，没有达到资源的最优化。
图1 华莱士数型结构
2.3 部分积压缩结构优化
在部分积压缩[3]时，全加器的位宽直接影响到加法的速度和最终实现时的面积，采用二阶布思算法后的部分积权值均不同，相邻部分积间的最低项和最高项间均相差2位，于是存在高位符号位填充和末尾位补0的需要，必要时还需要删除部分多余位，此时添、补和删便是位宽优化和面积优化最关键的地方。本设计主要用3种方法来优化加法器的位数，从而实现计算速度和面积的最优化。
(1)添加最少的符号位。在用4-2压缩器或是CSA进行部分积压缩时，尽量将权值相近的加数就近相加，这样可以有效地减少错位，从而能尽量减少添加的符号位数，也同时能减少尾部添加的0的位数。根据文献[3]，可以证明有符号的加数只需扩展一位符号位就能实现加法的正确运算，多余的符号位添加只会带来位宽的浪费。符号位填充优化示意图如图2所示，左边的阴影部分为符号位填充，右边的格状阴影部分为0填充。
感温元件图2 符号位填充优化示意图
(2)推迟部分末尾位的加法，减少末尾0填充。通过减少高位符号位的填充后，加法器的位
宽明显减少了，但发现末尾错位导致的添0位随着权值的差额增大也在增加，所以要想进一步减少位宽，还须尽量减少添0的个数，在画压缩树时发现，因为华莱士树中各级之间权值的差异较大，最大存在16位的错位，所以有些部分积的末尾项完全可以根据需要补在下面任何一级压缩的末尾计算，这样就省去了前一级末尾数的补 0带来的位宽的增加。压缩树最后一级的位宽是32位，所以在优化压缩结构时，完全可以将上面2级压缩中最后留下的个别部分积末尾未加的位补在最后一级来运算。
(3)删除多余高位。通过布思算法后的部分积，最高可以达到34位。每经过一级压缩后，和值D和进位值Co都会比原值再增加一位，到最后一级 4-2压缩器时，最高位会远远超过32位，而16×16位的乘法得到的乘积最高为32位，因此，部分积中超过 32位的位数完全可以删除。其实，高于32位的位项是上面一级符号位填充后再累加的结果，因此，随着华莱士树级数的增加多余的高位也随之增加，删除多余高位也是优化加法器位宽的重要方法。通过删除多余的高位，既减少了中间加法位数，加快了乘积运算，同时也减少了面积。图3为全局优化后的结构示意图，其中后面2个加法器左边斜线阴影部分即为删除的高于32位的高位。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议