一种规整高效的缩1码模2n+1乘法器的VLSI设计

王文瑞

（昆明市呈贡县95973部队15分队，云南 昆明 650500）

0 引言

近年来，剩余数系统和费马数变换在数字信号处理中得到了广泛的应用[1-4]，而模2n+1乘法器是这二者中最关键的部件[5-12]。通常在数字信号处理算法中，乘加操作是最为密集的计算，迄今为止，基于缩 1码（Dminished-1 Number Representation）[6]的模2n+1运算单元的性能要远高于普通二进制数的模2n+1运算单元[13]，尽管存在缩1码与普通二进制数之间的转换，但是由于数字信号处理算法所涉及的往往都是反复的乘加运算过程，因此，对于一个乘加密集型的运算过程而言，只要这种数制的转换是发生在开始和终止端完成的，它所耗费的资源与采用缩1码带来的乘加运算的节省相比，是可忽略的。

目前，基于缩1码的模2n+1乘法器的框架主要分为两大类，一类是非 Booth编码框架的模乘法器[5,10],另一类是基-4 Booth编码框架的模乘法器[7-9]。相对而言，前者占用面积较少，但速度较慢，后者速度较快，但占用面积较大。现基于基-4 Booth编码框架，设计出统一的编码选择电路，简化了校正项生成电路，从而减少模乘法器的面积，并进一步提高其速度。

1 算法描述

设A是关于模2n+1的余数，则其位数为n+1位，用d[A]表示A的缩1码，则它们满足下列关系式：

显然，d[A]的位数只有n位。在缩1码中，2n用于表示0，由于 0和其他数的运算可以很容易的得出结果，因此当模2n+1的余数用缩1码表示时，可以利用n位的电路单元快速、经济的实现模2n+1的算术运算。缩1码的加减乘运算不同于普通二进制数的加减乘运算，为了后续推导的方便，下面给出缩1码的运算规则[6]。

上式中，⊕表示缩 1码加法。对于乘积 A2k的缩1码，即d[A2k]（k为正整数），是将d[A]执行k次的循环左移，每次左移出来的位要取反后再循环进入最低位。

设被乘数A = (xnxn-1··x0)2和乘数B = (ynyn-1··y0)2分别是模2n+1的余数，它们的缩1码分别用d[A]= (an-1an-2··a0)2和d[B]=(bn-1bn-2··b0)2来表示，则d[B]可以展开为：

式中，b-1=0，K=┌n/2┐，当j≥n，bj=0。

由此，B可以表示为：

式中，b-1=1，K=┌n/2┐，当j≥n，bj=0。

乘积A×B的缩1码为：

将式（6）代入式（7）得：

根据式（7）有：

将式（9）代入式（8）得：

根据式（5），式（10）可以表示为：

当n是偶数时，如果i=K=┌n/2┐, 则2i=n，对于B有：考虑到有：

因为bn+1= bn=0, b-1=1，所以有：

为了编码的统一，将-bn-1+1合并成，将= -bn-1+1与式（12）代入式（7），重复式（8）到式（11）的推导，有：

式（13）中d[A(b2i-1+b2i-2b2i+1)22i]和d[A(bn-1+b0-2b1)22i]被称之为部分积，由此可知，当n是偶数时，部分积的个数可以减少1个，变成n/2个。

(b2i-1+b2i-2b2i+1)可取的值为 0, ±1, ±2，对应的部分积d[A(b2i-1+b2i-2b2i+1)22i]的取值可为 d[0], d[±A22i]和 d[±A22i+1]，在这些取值中，除了d[0]外，其他项的值都可以利用d[A2k]的循环移位的运算规则得出。由于d[0]是0的缩1码，其值是2n，这是一个n+1位的数，为了避免使用n+1位的计算单元，根据性质以及 i ＜ n，将 2n拆分成 22i-1加上-22i，并将22i-1视为部分积，而-22i视为校正项，对于其他非0的部分积而言，其校正项设为0。由此可以得到d[AB]的最终表达式：

式中K=┌n/2┐, PPi表示第i个部分积，CTi表示第i个校正项，表4给出了它们的取值。由上述推导可知，当n是偶数时，i=0时的编码方案是当n是奇数，i=0时的编码方案是1+b0-2b1，因此，表1给出了n为偶数时的PP0和CT0的取值，表2给出了n为奇数时PP0和CT0的取值，表3给出了当0＜i＜K时的PPi和CTi的取值。从各表中可以看出，所有的编码都遵循统一的格式b2i-1+b2i-2b2i+1（基-4 Booth编码），相比文献[9]而言，这里给出的编码选择电路统一，方便实现。式（14）中的是22i的累加和，而22i具有分布性，因此无须累加计算，它具有(x0··x0x)2形式，其中x = 0或1。相比文献[9]而言，这里的校正项简单，电路占用的门数少。

表1 当n为偶数，i =0时的部分积和校正项

表2 当n为奇数，i =0时的部分积和校正项

表3 0＜i＜K时的部分积和校正项

表4 部分积和校正项

2 电路实现

式（15）的所有操作都是缩1码的加法运算，因此，可以利用一个缩1码的进位保留加法器树将式（15）中的K+2个操作数减少到两个操作数，然后用一个基于缩 1码的模2n+1加法器获得最终的乘积结果

缩1码的进位保留加法器是将三个缩1码的和表示成两个缩1码的和，因此它也是一个缩1码的3：2压缩器，它的硬件实现是将进位保留加法器的最高有效位的进位输出取反后作为进位输出的最低有效位，因此也被称作为取反回转进位加法器。由这种加法器构成的树结构具有很好的规整性，非常适合VLSI的实现。

部分积生成电路（PPG）是Booth编码器（BE）和.Booth选择器（BS）组成，BE根据位组合(b2i+1b2ib2i-1)2输出三个位信号，分别表示符号位，1倍信号位和2倍信号位，BS实际上是一个2选1的多路选择器，它根据BE输出的三个位信号选择输出部分积的1个位。图1示出了BE的电路，其真值表如表5所示，为了能够处理0的缩1码，在所有的BE中都引入了一个位信号时，表明A和B中存在0操作数，则其乘积必为0，相应的缩1码为2n，此时对所有的BE而言，其三个位输出全部为0，从而使所有的部分积都编码生成d[0]，这些部分积相加的结果自然也是d[0]，从而实现了处理0的缩1码的功能。图2示出了BS的电路，其真值表如表6和表7所示。

图1 BE的电路实现

图2 BS的电路实现

表5 RE的真值表

表6 BS的真值表1

表7 BS的真值表2

缩1码的进位保留加法器树可以将K = n/2+2个部分积减少到两个操作数，通常情况下，n位缩1码的进位保留加法器是由n个1位的全加器（FA）构成的，由式（15）可知，在具有(x1x1x··1x)2形式的校正项中有位是常数1，因此这些位上的FA可以减少一半的基本门，这里用FA+表示这些简化的FA，同样，在式（15）中，由于1的缩1码d[1]是（00··00)2，因此这一级的进位保留加法器可以全部简化成半加器（HA）。校正项的x比特位的生成构成了校正项生成电路（CTG），它的实现可以利用和x对应的BE的三个位输出信号的或运算得到，从而简化了校正项电路。

例：基于缩1码的模28+1乘法器。当n =8时, 设A = 154, B= 199 ,则图3给出了计算过程中的部分积和校正项，最终结果为d[63] = (111110)2。

图 3 缩1码模28+1乘法运算过程

3 性能评估和比较

为了定性的评估提出的方案，这里采用Tyagi[15]提出的单一门模型，该模型是以2输入的基本门作为面积和延时上的一个计算单位的,而2输入的异或门和同或门则被等效为两个计算单位。Tyagi模型被大量的数字电路设计文献所采用,为不同设计方案的功能电路提供了一个公平中肯的比较标准。下面给出了n是偶数时的面积和延时的定性分析,n是奇数时的分析与此相类似。

提出的模乘法器占用的面积是由部分积生成电路PPG（包括BE和BS），校正项生成电路，基于缩1码的进位保留加法器树以及缩1码加法器占用的面积构成的。部分积生成电路是由个BS构成的，由图1和图2可知，BE的面积等效为11个单位面积，BS的面积等效为5个单位面积，因此部分积生成电路的面积为：

基于缩1码的进位保留加法器树是由三组不同构造的进位保留加法器构成的。一组是-2个，这些进位保留加法器全部由n个FA组成，另一组是1个，由个FA和个FA+组成，最后一组也是1个，全部由n个HA构成。由于1个FA的面积等效于7个面积单位，1个FA+和1个HA的面积等效于3个面积单元，因此，该树的面积为：

将上述的面积相加，可以得到本方案的模乘法器所占用的面积大小为：

提出的模乘法器的延时是由3部分组成的，即部分积生成电路延时，基于缩1码的进位保留加法器树延时以及缩1码加法器延时。由于校正项的生成是和其他处理过程并行发生的，而且延时远远小于其他处理过程，因此在总延时中无须考虑。部分积生成电路延时等于BE和BS的延时和，由图1和图2可知，BE和BS的延时都等效于4个时间单位，因此部分积生成电路PPG的延时为：TPPG= 8。

最后一级的缩1码加法器的延时同样可以从文献[14]中得到：

将上述延时累加，得到提出的模乘法器的总延时为：

表8和表9分别给出了提出的模乘法器与文献[9-10]的延时和面积的比较。从中可以看出，提出的模乘法器所占用的面积和延时是最小的。表8中W(k)：k为输入下的Wallace树的极数。

表8 延时比较

表9 面积比较

4 结语

基于基-4 Booth编码框架设计出了一个编码电路统一，校正项简单，能够处理操作数和结果为0的情况的缩1码模乘法器，相比近年来见诸文献的缩1码模乘法器而言，提出的模乘法器以最少的面积获得了较快的速度。

[1] 马上，胡剑浩，张林，等. 一种基为{2n-1, 2n+1, 22n+1}的余数系统奇偶检测方法及其应用[J]. 中国科学 E辑：信息科学, 2008,38(04)：647-656.

[2] CONWAY R, NELSON J. Improved RNS FIR Filter Architectures[J].IEEE Trans. Circuits Syst. II, Exp. Briefs, 2004,51(01)：26-28.

[3] Liu Y, Edmund M K L.Moduli Set Selection and Cost Estimation for RNS-based FIR Filter and Filter Bank Design’[J]. Design Automation for Embedded Systems, 2004(09)：123-139.

[4] ZIMMERMANN R, CURIGER A, BONNENBERG H, et al. A 177 Mb/s VLSI Implementation of the International Data Encryption Algorithm’[J]. IEEE J. Solid-State Circuits,1994,29(03)：303-307.

[5] WANC Z, JULLIEN C A,MILLER, W C. An Efficient Tree Architecture for Modulo (2n+1) Multiplication’[J]. J VLSI Signal Prucess.Syst., 1996,14(03)：241-248.

[6] LEIBOWITZ L. A Simplified Binary Arithmetic for the Fermat Number Transform’[J]. IEEE Trans. Acoust., Speech, Signal Process., 1976,ASSP-24(05)：356-359.

[7] MA Y.A Simplified Architecture for Modulo(2n+1) Multiplication[J].IEEE Trans. Comput., 1998, 41,(03)：333-337.

[8] ZIMMERMANN R.Efficient VLSI Implementation of Modulo (2n±1)Addition and Multiplication[C]//IEEE. Proc. IEEE Symp. on Computer Arithmetic. USA：IEEE, 1999：158-167.

[9] SOUSA L, CHAVES R. A Universal Architecture for Designing Efficient Modulo 2n+1 Multipliers[J]. IEEE Trans. Circuits and Systems-I. 2005,52(06)：1166-1178.

[10] EFSTATHIOU C, VERGOS H T, DIMITRAKOPOULOS G,et al. Efficient Diminished-1 Modulo 2n+1 Multipliers[J]. IEEE Trans. Comput.,2005(54)：491-496.

[11] CURIGER A, BONNENBERG H, KAESLIN H.Regular VLSI Architectures for Multiplication Modulo (2n+1)[J]. IEEE J. Solid-State Circuits,1991,26,(07)：990-994.

[12] HIASSAT A.New Memoryless Mod (2n±1) Residue Multiplier[J].Electron. Lett., Jan. 1992, 28(03)：314-315.

[13] VERGOS H T, EFSTATHIOU C. A Unifying Approach for Weighted and Diminished-1 Modulo 2n+1 Addition[J]. IEEE Trans. Circuits& System II, Oct. 2008, 55(10)：1041-1045.

[14] VERGOS H T, EFSTATHIOU C, NIKOLOS D.Diminished-one Modulo(2n+1) Adder Design[J]. IEEE Trans. Comput., 1994(43)：68-77.[15] TYAGI A. A Reduced-area Scheme for Carry-select Adders[J].IEEE Trans. Comp., 1993, 42(10)：1163-1170.