黃世洋， 陳奉儀， 姚若河

(華南理工大學(xué)電子與信息學(xué)院，廣州 510640)

一個應(yīng)用混合基算法的余數(shù)系統(tǒng)后置轉(zhuǎn)換電路設(shè)計

黃世洋， 陳奉儀， 姚若河*

(華南理工大學(xué)電子與信息學(xué)院，廣州 510640)

針對傳統(tǒng)的混合基算法在實(shí)現(xiàn)余數(shù)系統(tǒng)到二進(jìn)制系統(tǒng)轉(zhuǎn)換過程中的并行性問題，應(yīng)用改進(jìn)的混合基算法，研究與設(shè)計了一個基于模集合{2n,2n-1,2n+1-1,2n-1-1}的后置轉(zhuǎn)換電路．模2n-1形式的模加法器采用相對簡單的實(shí)現(xiàn)結(jié)構(gòu)，使設(shè)計的電路避免了只讀存儲器及時序電路的引入，整個后置轉(zhuǎn)換電路完全由簡單組合邏輯及加法器級聯(lián)實(shí)現(xiàn)，縮短了關(guān)鍵路徑延時，減小了功率消耗，與已有的相同動態(tài)范圍余數(shù)系統(tǒng)后置轉(zhuǎn)換電路相比，性能優(yōu)勢明顯.

混合基算法； 余數(shù)系統(tǒng)； 模加法器

余數(shù)系統(tǒng)是一個古老的數(shù)值表征系統(tǒng)．一個大整數(shù)X被劃分成幾個獨(dú)立并行運(yùn)算的小整數(shù)，在乘法和加法運(yùn)算中，各并行模塊之間無進(jìn)位傳播，從而減少關(guān)鍵路徑的時延，因此對具有大量運(yùn)算的數(shù)字信號處理系統(tǒng)具有廣泛的應(yīng)用前景．在有大量乘法和加法運(yùn)算的數(shù)字信號處理系統(tǒng)中，余數(shù)系統(tǒng)不僅可以獲得高速的超大規(guī)模集成電路實(shí)現(xiàn)，而且功耗和面積都可相應(yīng)地減少．因此基于余數(shù)系統(tǒng)的數(shù)字信號處理算法可為數(shù)據(jù)通道設(shè)計在高速、低復(fù)雜度、低功耗等方面找到平衡點(diǎn)，對現(xiàn)代移動設(shè)備、機(jī)載和星載設(shè)備等有重要意義．模集合的具體形式是決定其超大規(guī)模集成電路實(shí)現(xiàn)復(fù)雜度的主要因素之一，因?yàn)槟＜系男问經(jīng)Q定了各余數(shù)通道的基本運(yùn)算單元——模加法和模乘法的運(yùn)算復(fù)雜程度．目前，大多數(shù)數(shù)字邏輯運(yùn)算均基于二進(jìn)制邏輯，而模2n±1和模2n加法器具有較簡單的超大規(guī)模集成電路實(shí)現(xiàn)結(jié)構(gòu)，因此多數(shù)余數(shù)系統(tǒng)均基于模2n±1和2n來構(gòu)建模集合．本文針對模集合{2n,2n-1,2n+1-1,2n-1-1}進(jìn)行后置轉(zhuǎn)換電路設(shè)計．該模集合為3模集合{2n-1, 2n, 2n+1, 2n+1-1, 2n-1-1}中剔除模2n+1得到[1-2]．證明當(dāng)n為偶數(shù)時上述的余數(shù)基之間是兩兩互質(zhì)的．該模集合整體動態(tài)范圍利用率接近于1，有較好的并行度和平衡度．本文采用改進(jìn)后的混合基算法對其后置轉(zhuǎn)換電路進(jìn)行設(shè)計，電路采用簡單的流水線實(shí)現(xiàn)方式，有利于各模塊的優(yōu)化．

1　混合基后置轉(zhuǎn)換算法

設(shè)m1,m2,m3,…,mN是兩兩互質(zhì)的正整數(shù)，對于給定的一組余數(shù)基{m1,m2,m3,…,mN}，混合基后置轉(zhuǎn)換算法有：

X=aNmN-1mN-2…m1+…+a3m2m1+a2m1+a1.

(1)

通常的混合基后置轉(zhuǎn)換算法對aNaN-1…a1的求解效率比較低，文獻(xiàn)[3]提出了一種提高并行性的方法．令(x1,x2,x3,…,xN-1,xN)是X在該集合下的模，即xi=(X)mi,則

a1=x1,

(2)

a2=m2(x2-a1),

(3)

a3=m3(m3(x3-a1)-a2)m3,

(4)

…

aN=mNmN{…mN×

(5)

2　電路設(shè)計與實(shí)現(xiàn)

本文針對模集合{2n,2n-1,2n+1-1,2n-1-1}(n為偶數(shù))設(shè)計其后置轉(zhuǎn)換電路．由式(1)可得X=a42n(2n-1)(2n+1-1)+a32n(2n-1)+a22n+a1.

(6)

由式(2)～(5)可得：

a1=x1,

(7)

a2=(2n)-12n-1(x2-a1)2n-1,

(8)

a3=(2n-1)-12n+1-1((2n)-12n+1-1×

(x3-a1)-a2)2n+1-1,

(9)a4=(2n+1-1)-12n-1-1((2n-1)-12n-1-1×

(10)

除式(7)外，式(8)～(10)均包含了乘法逆元項(xiàng)，計算可得各乘法逆元:

(2n)-12n-1=1,

(11)

(2n)-12n+1-1=2,

(12)

(2n-1)-12n+1-1=-2,

(13)

(2n)-12n-1-1=2n-2,

(14)

(2n-1)-12n-1-1=1,

(15)

.

(16)

當(dāng)n為偶數(shù)時，式(16)中(2n-1)/3是一個正整數(shù)，有

(17)

將式(11)～(17)中的各乘法逆元值代入式(8)～(10)可得

a2=x2-x12n-1,

(18)

a3=4(x1-x3)+2a22n+1-1,

(19)

a4=2n-1-1.

(20)

由于x1、x2、x3、x4分別是n位、n位、n+1位、n-1位的二進(jìn)制數(shù)，在二進(jìn)制數(shù)系統(tǒng)下，它們可以表示為：

x1=(x1,n-1x1,n-2…x1,0)2,

x2=(x2,n-1x2,n-2…x2,0)2,

x3=(x3,nx3,n-1…x3,0)2,

x4=(x4,n-2x4,n-3…x4,0)2.

為進(jìn)一步推導(dǎo)a1、a2、a3、a4在二進(jìn)制數(shù)下的表達(dá)式，應(yīng)用如下運(yùn)算與引理：

(1)xk(m)表示xk的低m位所表示的二進(jìn)制數(shù)，若xk是小于m位的二進(jìn)制數(shù)，則其多出來的高位補(bǔ)0；

(2)x?k或x?k分別表示二進(jìn)制數(shù)x循環(huán)左移或右移k位；

引理1在模2n-1運(yùn)算中，余數(shù)v的負(fù)數(shù)-v可以用v的反碼形式表示，其中0≤v≤2n-1,即：

-v2n-1=2n-1.

(21)

引理2在模2n-1運(yùn)算中，當(dāng)余數(shù)v與權(quán)重為2的數(shù)2k做模運(yùn)算時，只需對v做k位的循環(huán)左移操作，即

2k·v2n-1=(v?k)2n-1.

(22)

根據(jù)式(21)與式(22)進(jìn)一步化簡式(18)～(20)，得

a2=2n-1，

(23)

a3=2n+1-1，

(24)

a4=

(25)

(26)

則a4=U+(U? 2)+(U? 4)+…+(U?n-2)2n-1-1.

(27)

對于n≥5,a2可以通過一個模2n-1加法器來實(shí)現(xiàn)．a(chǎn)3的實(shí)現(xiàn)結(jié)構(gòu)是一個(3,2n+1-1)MOMA(Multi Operand Mode Adder,多操作數(shù)的模加法器),由一個n+1位回旋進(jìn)位保留加法器與模2n-1加法器實(shí)現(xiàn)．圖1給出了a2、a3及Y的實(shí)現(xiàn)結(jié)構(gòu)．對于a4,先求U，其實(shí)現(xiàn)結(jié)構(gòu)是一個(5,2n-1-1)MOMA．求得U后，通過一個(n/2,2n-1-1)MOMA即可得到a4,如圖2所示．

圖1　a2, a3及Y的硬件實(shí)現(xiàn)

最后通過式(6)可得到X=a42n(2n-1)(2n+1-1)+a32n(2n-1)+a22n+x1=

[a4(2n-1)(2n+1-1)+a3(2n-1)+a2]2n+x1=[a4(22n+1-2n-2n+1+1)+a3(2n-1)+a2]2n+x1.

圖2　U和a4的硬件實(shí)現(xiàn)

由于W1、W2、W3、W4都是3n位的補(bǔ)碼表示，所以W的運(yùn)算只需要一個4輸入的3n位補(bǔ)碼加法器．該加法器由2級3n位進(jìn)位保留加法器(CSA)及一個3n位的并行前綴加法器來實(shí)現(xiàn)(圖3).由于W1、W2、W3、W4分別包含n位的1以及2n+1位的0、2n+1位的1，在圖3的2級CSA中，總共有4n+2個FA(全加器)被替換為更節(jié)省資源的2n對XNOR/OR門，n+1對XOR/AND門和n個非門,以節(jié)省硬件資源．

圖3　X最終硬件實(shí)現(xiàn)模塊

上述后置轉(zhuǎn)換電路實(shí)現(xiàn)結(jié)構(gòu)都是基于門器件，由門器件構(gòu)成的重復(fù)單元電路多是FA，2輸入模加法器及并行前綴加法器．在模2n-1加法器的選擇上，采用端回進(jìn)位前綴結(jié)構(gòu)[3]．雖然基于混合基算法的R/B電路是一種串行算法，但由于本文模集合的特殊形式，電路采用簡單的實(shí)現(xiàn)方式因而縮短了延時路徑．

與近年報道的一些具有近似相同動態(tài)范圍的模集合后置轉(zhuǎn)換電路相比[4-6]，在n>8時，本文所設(shè)計的后置轉(zhuǎn)換電路，其性能有明顯的優(yōu)勢．

3　結(jié)語

針對模集合為{2n,2n-1,2n+1-1,2n-1-1}的余數(shù)系統(tǒng)，采用改進(jìn)后的混合基算法設(shè)計其后置轉(zhuǎn)換電路．該后置轉(zhuǎn)換電路僅由加法器組成的組合邏輯電路來實(shí)現(xiàn)，避免了ROM及時序電路的引入，減少了關(guān)鍵路徑的延時．

[1]徐明鶴.余數(shù)系統(tǒng)后置轉(zhuǎn)換和符號檢測電路的設(shè)計[D].廣州：華南理工大學(xué),2012.

Xu M H.Design on reverse converter and sign detection circuit for residue number system[D].Guangzhou: South China University of Technology,2012.

[2]Cao B, Chang C H, Srikanthan T. A residue-to-binary converter for a new five-moduli set[J]. IEEE Transactions on Circuits and Systems- I, 2007, 54(5): 1041-1049.

[3]胡劍浩，馬上.余數(shù)系統(tǒng)原理與在高速數(shù)字信號處理中的應(yīng)用[M].北京：科學(xué)出版社，2012.

[4]Mohan P V A, Premkumar A B. RNS-to-binary converters for two four-moduli sets {2n-1, 2n, 2n+1, 2n+1-1} and {2n-1, 2n, 2n+1, 2n+1+1}[J]. IEEE Transactions on Circuits and Systems-I, 2007, 54(6): 1245-1254.

[5]Mohan P V A. New reverse converters for the moduli set {2n-3, 2n-1, 2n+1, 2n+3}[J]. Aeu-International Journal of Electronics and Communications, 2008, 62(9): 643-658.

[6]Skavantzos A, Abdallah M, Stouraitis T. Large dynamic range RNS systems and their residue to binary converters[J]. Journal of Circuits Systems and Computers, 2007, 16(2): 267-286.

【中文責(zé)編：莊曉瓊英文責(zé)編：肖菁】

A Circuit Design of Residue to Binary Converter Using the Mixed Radix Algorithm

Huang Shiyang, Chen Fenyi, Yao Ruohe*

(School of Electronic and Information Engineering, South China University of Technology, Guangzhou 510640, China)

The conversion of residue number system to binary system using traditional mixed radix conversion lacks of parallelism. An improved mixed radix conversion is proposed. A residue to binary(R/B) conversion circuits based on moduli {2n,2n-1,2n+1-1,2n-1-1} is studied and designed. The modulo 2n-1 adder has a relatively simple implementation, in which the design of the circuit is to avoid the introduction of read-only memory and time sequence circuit, and the R/B conversion circuit is implemented by a simple combination of logic and adder cascade. The analysis results show that the reverse converter shortens the delay of critical path and decreases the power dissipation efficiently. Compared to those R/B converters with same dynamic range designed in recent years, the circuit designed in this paper has a better performance advantage apparently.

mixed radix conversion； residue number system； modulo adder

2015-01-06《華南師范大學(xué)學(xué)報(自然科學(xué)版)》網(wǎng)址：http://journal.scnu.edu.cn/n

國家自然科學(xué)基金項(xiàng)目(61274085);華南理工大學(xué)中央高?；究蒲袑W(xué)生項(xiàng)目(10561201435)

姚若河，教授，Email:phrhyao@scut.edu.cn.

TP399

A

1000-5463(2015)05-0159-04