王文瑞

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

0 引言

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

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

1 算法描述

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

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

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

設(shè)被乘數(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┐，當(dāng)j≥n，bj=0。

由此，B可以表示為：

式中，b-1=1，K=┌n/2┐，當(dāng)j≥n，bj=0。

乘積A×B的縮1碼為：

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

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

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

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

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

因?yàn)閎n+1= bn=0, b-1=1，所以有：

為了編碼的統(tǒng)一，將-bn-1+1合并成，將= -bn-1+1與式（12）代入式（7），重復(fù)式（8）到式（11）的推導(dǎo)，有：

式（13）中d[A(b2i-1+b2i-2b2i+1)22i]和d[A(bn-1+b0-2b1)22i]被稱之為部分積，由此可知，當(dāng)n是偶數(shù)時(shí)，部分積的個(gè)數(shù)可以減少1個(gè)，變成n/2個(gè)。

(b2i-1+b2i-2b2i+1)可取的值為 0, ±1, ±2，對應(yīng)的部分積d[A(b2i-1+b2i-2b2i+1)22i]的取值可為 d[0], d[±A22i]和 d[±A22i+1]，在這些取值中，除了d[0]外，其他項(xiàng)的值都可以利用d[A2k]的循環(huán)移位的運(yùn)算規(guī)則得出。由于d[0]是0的縮1碼，其值是2n，這是一個(gè)n+1位的數(shù)，為了避免使用n+1位的計(jì)算單元，根據(jù)性質(zhì)以及 i ＜ n，將 2n拆分成 22i-1加上-22i，并將22i-1視為部分積，而-22i視為校正項(xiàng)，對于其他非0的部分積而言，其校正項(xiàng)設(shè)為0。由此可以得到d[AB]的最終表達(dá)式：

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

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

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

表3 0＜i＜K時(shí)的部分積和校正項(xiàng)

表4 部分積和校正項(xiàng)

2 電路實(shí)現(xiàn)

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

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

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

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

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

表5 RE的真值表

表6 BS的真值表1

表7 BS的真值表2

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

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

圖 3 縮1碼模28+1乘法運(yùn)算過程

3 性能評估和比較

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

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

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

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

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

最后一級的縮1碼加法器的延時(shí)同樣可以從文獻(xiàn)[14]中得到：

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

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

表8 延時(shí)比較

表9 面積比較

4 結(jié)語

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

[1] 馬上，胡劍浩，張林，等. 一種基為{2n-1, 2n+1, 22n+1}的余數(shù)系統(tǒng)奇偶檢測方法及其應(yīng)用[J]. 中國科學(xué) E輯：信息科學(xué), 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.