王文瑞

（昆明市呈貢縣95973部隊15分隊，云南 昆明 650500）

0 引言

近年來，剩余數(shù)系統(tǒng)和費馬數(shù)變換在數(shù)字信號處理中得到了廣泛的應用[1-4]，而模2n+1乘法器是這二者中最關(guān)鍵的部件[5-12]。通常在數(shù)字信號處理算法中，乘加操作是最為密集的計算，迄今為止，基于縮 1碼（Dminished-1 Number Representation）[6]的模2n+1運算單元的性能要遠高于普通二進制數(shù)的模2n+1運算單元[13]，盡管存在縮1碼與普通二進制數(shù)之間的轉(zhuǎn)換，但是由于數(shù)字信號處理算法所涉及的往往都是反復的乘加運算過程，因此，對于一個乘加密集型的運算過程而言，只要這種數(shù)制的轉(zhuǎn)換是發(fā)生在開始和終止端完成的，它所耗費的資源與采用縮1碼帶來的乘加運算的節(jié)省相比，是可忽略的。

目前，基于縮1碼的模2n+1乘法器的框架主要分為兩大類，一類是非 Booth編碼框架的模乘法器[5,10],另一類是基-4 Booth編碼框架的模乘法器[7-9]。相對而言，前者占用面積較少，但速度較慢，后者速度較快，但占用面積較大。現(xiàn)基于基-4 Booth編碼框架，設計出統(tǒng)一的編碼選擇電路，簡化了校正項生成電路，從而減少模乘法器的面積，并進一步提高其速度。

1 算法描述

設A是關(guān)于模2n+1的余數(shù)，則其位數(shù)為n+1位，用d[A]表示A的縮1碼，則它們滿足下列關(guān)系式：

顯然，d[A]的位數(shù)只有n位。在縮1碼中，2n用于表示0，由于 0和其他數(shù)的運算可以很容易的得出結(jié)果，因此當模2n+1的余數(shù)用縮1碼表示時，可以利用n位的電路單元快速、經(jīng)濟的實現(xiàn)模2n+1的算術(shù)運算?？s1碼的加減乘運算不同于普通二進制數(shù)的加減乘運算，為了后續(xù)推導的方便，下面給出縮1碼的運算規(guī)則[6]。

上式中，⊕表示縮 1碼加法。對于乘積 A2k的縮1碼，即d[A2k]（k為正整數(shù)），是將d[A]執(zhí)行k次的循環(huán)左移，每次左移出來的位要取反后再循環(huán)進入最低位。

設被乘數(shù)A = (xnxn-1··x0)2和乘數(shù)B = (ynyn-1··y0)2分別是模2n+1的余數(shù)，它們的縮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）得：

根據(jù)式（7）有：

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

根據(jù)式（5），式（10）可以表示為：

當n是偶數(shù)時，如果i=K=┌n/2┐, 則2i=n，對于B有：考慮到有：

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

為了編碼的統(tǒng)一，將-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是偶數(shù)時，部分積的個數(shù)可以減少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]的循環(huán)移位的運算規(guī)則得出。由于d[0]是0的縮1碼，其值是2n，這是一個n+1位的數(shù)，為了避免使用n+1位的計算單元，根據(jù)性質(zhì)以及 i ＜ n，將 2n拆分成 22i-1加上-22i，并將22i-1視為部分積，而-22i視為校正項，對于其他非0的部分積而言，其校正項設為0。由此可以得到d[AB]的最終表達式：

式中K=┌n/2┐, PPi表示第i個部分積，CTi表示第i個校正項，表4給出了它們的取值。由上述推導可知，當n是偶數(shù)時，i=0時的編碼方案是當n是奇數(shù)，i=0時的編碼方案是1+b0-2b1，因此，表1給出了n為偶數(shù)時的PP0和CT0的取值，表2給出了n為奇數(shù)時PP0和CT0的取值，表3給出了當0＜i＜K時的PPi和CTi的取值。從各表中可以看出，所有的編碼都遵循統(tǒng)一的格式b2i-1+b2i-2b2i+1（基-4 Booth編碼），相比文獻[9]而言，這里給出的編碼選擇電路統(tǒng)一，方便實現(xiàn)。式（14）中的是22i的累加和，而22i具有分布性，因此無須累加計算，它具有(x0··x0x)2形式，其中x = 0或1。相比文獻[9]而言，這里的校正項簡單，電路占用的門數(shù)少。

表1 當n為偶數(shù)，i =0時的部分積和校正項

表2 當n為奇數(shù)，i =0時的部分積和校正項

表3 0＜i＜K時的部分積和校正項

表4 部分積和校正項

2 電路實現(xiàn)

式（15）的所有操作都是縮1碼的加法運算，因此，可以利用一個縮1碼的進位保留加法器樹將式（15）中的K+2個操作數(shù)減少到兩個操作數(shù)，然后用一個基于縮 1碼的模2n+1加法器獲得最終的乘積結(jié)果

縮1碼的進位保留加法器是將三個縮1碼的和表示成兩個縮1碼的和，因此它也是一個縮1碼的3：2壓縮器，它的硬件實現(xiàn)是將進位保留加法器的最高有效位的進位輸出取反后作為進位輸出的最低有效位，因此也被稱作為取反回轉(zhuǎn)進位加法器。由這種加法器構(gòu)成的樹結(jié)構(gòu)具有很好的規(guī)整性，非常適合VLSI的實現(xiàn)。

部分積生成電路（PPG）是Booth編碼器（BE）和.Booth選擇器（BS）組成，BE根據(jù)位組合(b2i+1b2ib2i-1)2輸出三個位信號，分別表示符號位，1倍信號位和2倍信號位，BS實際上是一個2選1的多路選擇器，它根據(jù)BE輸出的三個位信號選擇輸出部分積的1個位。圖1示出了BE的電路，其真值表如表5所示，為了能夠處理0的縮1碼，在所有的BE中都引入了一個位信號時，表明A和B中存在0操作數(shù)，則其乘積必為0，相應的縮1碼為2n，此時對所有的BE而言，其三個位輸出全部為0，從而使所有的部分積都編碼生成d[0]，這些部分積相加的結(jié)果自然也是d[0]，從而實現(xiàn)了處理0的縮1碼的功能。圖2示出了BS的電路，其真值表如表6和表7所示。

圖1 BE的電路實現(xiàn)

圖2 BS的電路實現(xiàn)

表5 RE的真值表

表6 BS的真值表1

表7 BS的真值表2

縮1碼的進位保留加法器樹可以將K = n/2+2個部分積減少到兩個操作數(shù)，通常情況下，n位縮1碼的進位保留加法器是由n個1位的全加器（FA）構(gòu)成的，由式（15）可知，在具有(x1x1x··1x)2形式的校正項中有位是常數(shù)1，因此這些位上的FA可以減少一半的基本門，這里用FA+表示這些簡化的FA，同樣，在式（15）中，由于1的縮1碼d[1]是（00··00)2，因此這一級的進位保留加法器可以全部簡化成半加器（HA）。校正項的x比特位的生成構(gòu)成了校正項生成電路（CTG），它的實現(xiàn)可以利用和x對應的BE的三個位輸出信號的或運算得到，從而簡化了校正項電路。

例：基于縮1碼的模28+1乘法器。當n =8時, 設A = 154, B= 199 ,則圖3給出了計算過程中的部分積和校正項，最終結(jié)果為d[63] = (111110)2。

圖 3 縮1碼模28+1乘法運算過程

3 性能評估和比較

為了定性的評估提出的方案，這里采用Tyagi[15]提出的單一門模型，該模型是以2輸入的基本門作為面積和延時上的一個計算單位的,而2輸入的異或門和同或門則被等效為兩個計算單位。Tyagi模型被大量的數(shù)字電路設計文獻所采用,為不同設計方案的功能電路提供了一個公平中肯的比較標準。下面給出了n是偶數(shù)時的面積和延時的定性分析,n是奇數(shù)時的分析與此相類似。

提出的模乘法器占用的面積是由部分積生成電路PPG（包括BE和BS），校正項生成電路，基于縮1碼的進位保留加法器樹以及縮1碼加法器占用的面積構(gòu)成的。部分積生成電路是由個BS構(gòu)成的，由圖1和圖2可知，BE的面積等效為11個單位面積，BS的面積等效為5個單位面積，因此部分積生成電路的面積為：

基于縮1碼的進位保留加法器樹是由三組不同構(gòu)造的進位保留加法器構(gòu)成的。一組是-2個，這些進位保留加法器全部由n個FA組成，另一組是1個，由個FA和個FA+組成，最后一組也是1個，全部由n個HA構(gòu)成。由于1個FA的面積等效于7個面積單位，1個FA+和1個HA的面積等效于3個面積單元，因此，該樹的面積為：

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

提出的模乘法器的延時是由3部分組成的，即部分積生成電路延時，基于縮1碼的進位保留加法器樹延時以及縮1碼加法器延時。由于校正項的生成是和其他處理過程并行發(fā)生的，而且延時遠遠小于其他處理過程，因此在總延時中無須考慮。部分積生成電路延時等于BE和BS的延時和，由圖1和圖2可知，BE和BS的延時都等效于4個時間單位，因此部分積生成電路PPG的延時為：TPPG= 8。

最后一級的縮1碼加法器的延時同樣可以從文獻[14]中得到：

將上述延時累加，得到提出的模乘法器的總延時為：

表8和表9分別給出了提出的模乘法器與文獻[9-10]的延時和面積的比較。從中可以看出，提出的模乘法器所占用的面積和延時是最小的。表8中W(k)：k為輸入下的Wallace樹的極數(shù)。

表8 延時比較

表9 面積比較

4 結(jié)語

基于基-4 Booth編碼框架設計出了一個編碼電路統(tǒng)一，校正項簡單，能夠處理操作數(shù)和結(jié)果為0的情況的縮1碼模乘法器，相比近年來見諸文獻的縮1碼模乘法器而言，提出的模乘法器以最少的面積獲得了較快的速度。

[1] 馬上，胡劍浩，張林，等. 一種基為{2n-1, 2n+1, 22n+1}的余數(shù)系統(tǒng)奇偶檢測方法及其應用[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.