摘 要： 反向轉(zhuǎn)化已經(jīng)成為制約剩余數(shù)系統(tǒng)發(fā)展的瓶頸問題，尤其對于模集合個數(shù)多于3個的模集合。針對4基數(shù)模集合{2n，22n+1，2n+1，2n-1}，在新中國余數(shù)定理Ⅰ的基礎(chǔ)上，提出了一個新的高效并行轉(zhuǎn)換算法。該算法可同時處理4個模，處理數(shù)的動態(tài)范圍達到5n位，乘法逆元全部采用閉合形式，電路完全基于加法器構(gòu)成，硬件實現(xiàn)容易。理論分析表明，與同類模集合反向轉(zhuǎn)換器相比，大大降低了對硬件電路的要求，明顯減小了轉(zhuǎn)換器的面積和電路延遲，提高了轉(zhuǎn)換效率。

關(guān)鍵詞： 新中國余數(shù)定理； 反向轉(zhuǎn)換； 余數(shù)系統(tǒng)； VLSI

中圖分類號： TN911?34 文獻標(biāo)識碼： A 文章編號： 1004?373X（2016）02?0110?03

Design of reverse convertor for 4?moduli residue number system

Lü Xiaolan， CUI Delong

（College of Computer and Electronic Information， Guangdong University of Petrochemical Technology， Maoming 525000， China）

Abstract： The reverse conversion has become the bottleneck which restricts the development of the residue number system （RNS）， especially for the moduli sets in which the number of the moduli is larger than 3. For the 4?moduli set {2n， 22n+1， 2n+1， 2n-1}， a new efficient parallel conversion algorithm is proposed based on the new Chinese Remainder Theorem I. The proposed algorithm can deal with the four moduli simultaneously， and the dynamic range of the treatment number can reach up to 5n bits. The close form is adopted by the multiplicative inverse of the moduli set， and the circuit is entirely constituted based on the summator， which is easy for hardware implementation. The theoretical analysis indicates that， compared with the congeneric moduli?set reverse converter， the system can greatly reduce the requirements for hardware circuit， obviously decrease the area and circuit delay of the converter， and improve the conversion efficiency.

Keywords： new Chinese Remainder Theorem； reverse conversion； residue number system； VLSI

0 引 言

隨著大規(guī)模集成電路發(fā)展，高集成度，高精度便攜式電子系統(tǒng)的發(fā)展，在信號處理方面，大規(guī)模的并行處理技術(shù)已經(jīng)逐步取代傳統(tǒng)的信號處理技術(shù)?；诖?，剩余數(shù)系統(tǒng)以其特有的無權(quán)重和并行運算特性，成為大規(guī)模并行信號處理技術(shù)的最佳選擇[1?2]。

剩余數(shù)系統(tǒng)應(yīng)用的意義已經(jīng)被證明，尤其在處理密集型加、減、乘、除等運算速度上占有絕對的優(yōu)勢。然而，由于其運算的復(fù)雜性，在剩余數(shù)系統(tǒng)就失去了并行性的優(yōu)勢，這些運算有時不得不將余數(shù)轉(zhuǎn)換成二進制數(shù)后再做運算，所以會浪費大量的電路面積和延遲。為了提高此類運算電路的性能，近年來許多和研究人員開始對此領(lǐng)域進行研究，但是大部分主要針對比較常用的3模集合[3?4]{2n，2n+1，2n-1}。

本文針對4模集合[5]{2n，22n+1，2n+1，2n-1}，在分析模集合特征的基礎(chǔ)上，提出了一個新反向轉(zhuǎn)換算法，并基于加法器實現(xiàn)其VLSI結(jié)構(gòu)。

1 算法描述

定理1 四個兩兩互素的正整數(shù)m1，m2，m3，m4（i=1，2，3，4），M=m1·m2·m3·m4為可處理數(shù)據(jù)的動態(tài)范圍，X模mi所得到的余數(shù)表示為[Xmi=xi]。根據(jù)新中國余數(shù)定理1（New CRT?Ⅰ），其剩余數(shù)表示[x1，x2，x3，x4RNS]對應(yīng)的權(quán)重數(shù)X在0～M區(qū)間具有惟一解[4]，即：

[X=x1+m1k1（x2-x1）+k2m2（x3-x2）+k3m2m3（x4-x3）m2m3m4] （1）

其中：k1，k2，k表示乘法逆元，滿足[k1m1m2m3m4=1，k2m1m2m3m4=1，k3m1m2m3m4=1]。

根據(jù)文獻[4]，對于4基數(shù)模集合{2n，22n+1，2n+1，2n-1}，當(dāng)n為任意整數(shù)時，模之間兩兩互質(zhì)。設(shè)[m1=2n]，[m2=22n+1]，[m3=2n+1]，[m4=2n-1]，此剩余數(shù)（[x1]，[x2]，[x3]，[x4]）RNS對應(yīng)剩余數(shù)的二進制表示為：

[x1=x1，n-1……x1，0n]， [x2=x2，2n……x2，02n+1]，

[x3=x3，n……x3，0n+1]， [x4=x4，n-1……x4，0n]

乘法逆元計算如下所述：

乘法逆元的計算公式：

[k1m1m2m3m4=1?k12n24n-1=1?k1=23n]

證明：

[23n2n24n-1=24n=1]

[k2m1m2m3m4=1?k2=2n-1]

證明：

[2n-12n22n+122n-1=22n-122n-1+22n22n-1=1]

[k3m1m2m3m4=1?k2=2n-2]

證明：

[k32n22n+12n+12n-1=2n2n2n-1=1]

根據(jù)式（1），有：

[X=x1+2nk1（x2-x1）+k222n+1（x3-x2）+ k322n+12n+1（x4-x3）24n-1 =x1+2nY] （2）

其中：

[Y=k1（x2-x1）+k222n+1（x3-x2）+ +k322n+12n+1（x4-x3）24n-1 =23n（x2-x1）+2n-122n+1（x3-x2）+ +2n-222n+12n+1（x4-x3）24n-1 =ω2x2+ω1x1+ω3x3+ω4x424n-1 =α1+α2+α3+α424n-1] （3）

其中：

[α1=ω1x124n-1=-23nx124n-1]，

[α2=ω2x2=23n-1-2n-1x224n-1]，

[α3=ω3x3=23n-2-24n-2-22n-2+2n-2x324n-1，] [α4=ω4x4=2n-223n+22n+2n+1x424n-1]

2 硬件實現(xiàn)

定理2 若0≤v≤2n-2，則v2i模2n-1的結(jié)果相當(dāng)于將n位寬二進制數(shù)v，即vn-1vn-2…v0循環(huán)左移i位。

定理3 若 0≤v≤2n-2，則（-v）2i模2n-1的結(jié)果相當(dāng)于將v乘以2i模2n-1的結(jié)果按位取反。

根據(jù)定理2和定理3，[α1，α2，α3，α4]進一步表示為：

[α1=ω1x124n-1=-23nx124n-1 =x1，n-1…x1，0n1…13n24n-1] （4）

[α2=ω2x2=23n-1-2n-1x224n-1 =x2，n…x2，0n+10…02n-1x2，2n…x2，n+1n+ 1…1nx2，2n…x2，02n+11…1n-124n-1] （5）

式中：符號“”表示拼接。[α1]與[α2]進行合并，由于[2n-12n-1=0]，去掉n位全1項，合并得到[α5]：

[α5=x2，n…x2，0n+10…02n-1x2，2n…x2，n+1n+ x1，n-1…x1，0nx2，2n…x2，02n+11…1n-124n-1 =α51+α5224n-1] （6）

其中：

[α51=x2，n…x2，0n+10…02n-1x2，2n…x2，n+1n24n-1α52=x1，n-1…x1，0nx2，2n…x2，02n+11…1n-124n-1] （7）[α3=ω3x3=23n-2-24n-2-22n-2+2n-2x324n-1 =0x3，n…x3，0n+10…0n-1x3，n…x3，0n+10…0n-2+ x3，1x3，021…1n-1x3，n…x3，0n+11…1n-1x3，n…x3，2n+124n-1 =α31+α32]

[α4=ω4x4=2n-223n+22n+2n+1x424n-1=x4，1x4，02x4，n-1…x4，0nx4，n-1…x4，0n x4，n-1…x4，0nx4，n-1…x4，2n-224n-1] （9）

最終，[α51，α52，α31，α32，α4]這5個數(shù)通過3級進位保留加法器（CSA），最終形成2個4n位寬的S，C；S和C通過模[24n-1]加法器得到4n位模加法器的結(jié)果Y，[Y]x1連接，直接形成整數(shù)X；整體結(jié)構(gòu)圖如圖1所示。

圖1 模集合{2n，22n+1，2n+1，2n-1}反向轉(zhuǎn)換

3 性能評估和比較

為了進行定性比較，本文與文獻[4]的算法模型進行對比，采用1位全加器（FA）的面積和延遲作為所有模型基本計算單位進行比較。本研究和文獻[4]全部采用目前效率最高的具有惟一表示的快速并行前綴模2n-1加法器[6]。根據(jù)文獻[6]，其面積按照nAFA，延時為2ntFA計算。同時，在進位保留加法器階段，4n位進位保留其硬件按4nAFA，延時 [7]為tFA。硬件消耗和延時的理論對比數(shù)據(jù)如表1所示。從表中可以看出，在延時相同的情況下，本文所提出的剩余數(shù)至二進制轉(zhuǎn)化算法模型在硬件消耗方面遠遠優(yōu)于參考文獻[4]給出的轉(zhuǎn)換器算法模型。

表1 余數(shù)至二進制轉(zhuǎn)換面積和延時的理論數(shù)據(jù)比較

4 結(jié) 語

文中給出4基數(shù)模集合{2n-1，2n+1，2n，22n-1-1}的剩余數(shù)至二進制數(shù)轉(zhuǎn)換的優(yōu)化算法，該模集合可同時4通道并行處理數(shù)據(jù)，可處理數(shù)據(jù)動態(tài)范圍達5n-1位，乘法逆元全部屬于閉合形式，電路基于加法器實現(xiàn)。理論分析結(jié)果表明，本研究的轉(zhuǎn)換器算法優(yōu)化，硬件實現(xiàn)容易，整體性能變現(xiàn)優(yōu)異。

參考文獻

[1] SZABO N S， TANAKA R I. Residue arithmetic and its applications to computer technology [M]. New York： McGraw?Hill， 1967： 1?20.

[2] MIROSLAV D L， DEJAN V T， BRIAN L E. 信號處理濾波器設(shè)計：基于Matlab和Mathematica的設(shè)計方法[M].朱義勝，董輝，譯.北京：電子工業(yè)出版社，2004：250?256.

[3] WANG Y， SONG X， ABOULHAMID M， et al. Adder based residue to binary number converters for （2n-1， 2n， 2n+1） [J]. IEEE Transactions on Signal Processing， 2002， 50（7）： 1772?1779.

[4] WANG Yuke. Residue?to?binary converters based on new Chinese remainder theorems [J]. IEEE Transactions on Circuits and Systems?II， 2000， 47（3）： 197?205.

[5] CAO B， CHANG C H， SRIKANTHAN T. An efficient reverse converter for the 4?moduli set {2n-1， 2n， 2n+1， 22n+1} based on the new Chinese Remainder Theorem [J]. IEEE Transactions on Circuits and Systems I， 2003， 50（10）： 1296?1303.

[6] PATEL R A， BENAISSA M， BOUSSAKTA S. Fast parallel?prefix architectures for modulo 2n?1 addition with a single representation of zero [J]. IEEE Transactions on Computers， 2007， 56（11）： 1484?1492.

[7] PIESTRAK S J. Design of residue generators and multi?operand modular adders using carry?save adders [J]. IEEE Transactions on Computers， 1994， 43（1）： 68?77.