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

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

中圖分類號(hào)： TN911?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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ā)展，在信號(hào)處理方面，大規(guī)模的并行處理技術(shù)已經(jīng)逐步取代傳統(tǒng)的信號(hào)處理技術(shù)?；诖?，剩余數(shù)系統(tǒng)以其特有的無權(quán)重和并行運(yùn)算特性，成為大規(guī)模并行信號(hào)處理技術(shù)的最佳選擇[1?2]。

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

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

1 算法描述

定理1 四個(gè)兩兩互素的正整數(shù)m1，m2，m3，m4（i=1，2，3，4），M=m1·m2·m3·m4為可處理數(shù)據(jù)的動(dòng)態(tài)范圍，X模mi所得到的余數(shù)表示為[Xmi=xi]。根據(jù)新中國余數(shù)定理1（New CRT?Ⅰ），其剩余數(shù)表示[x1，x2，x3，x4RNS]對(duì)應(yīng)的權(quán)重?cái)?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ù)文獻(xiàn)[4]，對(duì)于4基數(shù)模集合{2n，22n+1，2n+1，2n-1}，當(dāng)n為任意整數(shù)時(shí)，模之間兩兩互質(zhì)。設(shè)[m1=2n]，[m2=22n+1]，[m3=2n+1]，[m4=2n-1]，此剩余數(shù)（[x1]，[x2]，[x3]，[x4]）RNS對(duì)應(yīng)剩余數(shù)的二進(jìn)制表示為：

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

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

乘法逆元計(jì)算如下所述：

乘法逆元的計(jì)算公式：

[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 硬件實(shí)現(xiàn)

定理2 若0≤v≤2n-2，則v2i模2n-1的結(jié)果相當(dāng)于將n位寬二進(jì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]進(jìn)一步表示為：

[α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）

式中：符號(hào)“”表示拼接。[α1]與[α2]進(jìn)行合并，由于[2n-12n-1=0]，去掉n位全1項(xiàng)，合并得到[α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個(gè)數(shù)通過3級(jí)進(jìn)位保留加法器（CSA），最終形成2個(gè)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 性能評(píng)估和比較

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

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

4 結(jié) 語

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

參考文獻(xiàn)

[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. 信號(hào)處理濾波器設(shè)計(jì)：基于Matlab和Mathematica的設(shè)計(jì)方法[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.