黃世洋， 陳奉儀， 姚若河

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

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

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

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

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

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

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

(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)

當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位的二進制數(shù)，在二進制數(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.

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

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

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

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

-v2n-1=2n-1.

(21)

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

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

(22)

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

圖1　a2, a3及Y的硬件實現(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的硬件實現(xiàn)

由于W1、W2、W3、W4都是3n位的補碼表示，所以W的運算只需要一個4輸入的3n位補碼加法器．該加法器由2級3n位進位保留加法器(CSA)及一個3n位的并行前綴加法器來實現(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最終硬件實現(xiàn)模塊

上述后置轉(zhuǎn)換電路實現(xiàn)結(jié)構(gòu)都是基于門器件，由門器件構(gòu)成的重復(fù)單元電路多是FA，2輸入模加法器及并行前綴加法器．在模2n-1加法器的選擇上，采用端回進位前綴結(jié)構(gòu)[3]．雖然基于混合基算法的R/B電路是一種串行算法，但由于本文模集合的特殊形式，電路采用簡單的實現(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)，采用改進后的混合基算法設(shè)計其后置轉(zhuǎn)換電路．該后置轉(zhuǎn)換電路僅由加法器組成的組合邏輯電路來實現(xiàn)，避免了ROM及時序電路的引入，減少了關(guān)鍵路徑的延時．

[1]徐明鶴.余數(shù)系統(tǒng)后置轉(zhuǎn)換和符號檢測電路的設(shè)計[D].廣州：華南理工大學,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].北京：科學出版社，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.

【中文責編：莊曉瓊英文責編：肖菁】

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《華南師范大學學報(自然科學版)》網(wǎng)址：http://journal.scnu.edu.cn/n

國家自然科學基金項目(61274085);華南理工大學中央高校基本科研學生項目(10561201435)

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

TP399

A

1000-5463(2015)05-0159-04