呂曉蘭，崔得龍

(廣東石油化工學(xué)院 計算機(jī)與電子信息學(xué)院，廣東 茂名 525000)

4模集合余數(shù)系統(tǒng)比例變換*

呂曉蘭，崔得龍

(廣東石油化工學(xué)院 計算機(jī)與電子信息學(xué)院，廣東 茂名 525000)

數(shù)值縮放(scaling)和奇偶檢測等的高效 VLSI實現(xiàn)已經(jīng)成為剩余數(shù)系統(tǒng)(RNS)研究的瓶頸問題。該文基于4模集合{2n，22n+1，2n+1，2n-1}，在新中國余數(shù)定理的基礎(chǔ)上，提出了該模集合優(yōu)化的 2n比例變換優(yōu)化算法，并基于VLSI實現(xiàn)其硬件結(jié)構(gòu)。分析結(jié)果表明，該 2n比例變換的VLSI實現(xiàn)具有更好的面積和功耗特性。

新中國余數(shù)定理;反向轉(zhuǎn)換;數(shù)值縮放;VLSI

0 引言

在大規(guī)模集成電路發(fā)展的今天，隨著高精度、便攜式電子器件的進(jìn)一步發(fā)展，傳統(tǒng)的信號處理技術(shù)已經(jīng)逐步被大規(guī)模的并行處理技術(shù)所取代。剩余數(shù)系統(tǒng)以其特有的進(jìn)位自由和并行運(yùn)算特性，近年來已經(jīng)成為高速、大規(guī)模數(shù)字信號處理的最好選擇。

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

比例變化是余數(shù)系統(tǒng)研究最重要問題之一，比例變化尤其在防止溢出和內(nèi)部乘積處理方面具有舉足輕重的作用。和反向轉(zhuǎn)換一樣，比例縮放在剩余數(shù)系統(tǒng)實現(xiàn)也涉及到大的延遲和較高的硬件復(fù)雜度，涉及在每一個剩余數(shù)計算階段。本文針對4模集合{2n，22n+1，2n+1，2n-1}，在分析反向轉(zhuǎn)換和比例縮放算法的基礎(chǔ)上，提出了一個新的基于2n的比例縮放算法，并基于加法器實現(xiàn)其VLSI結(jié)構(gòu)。

1 算法描述

基于剩余數(shù)系統(tǒng)模集合{m1，m2，…，mn}的整數(shù)X，通過一個比例因子k做比例變化，設(shè)Y為比例變化的結(jié)果，則：

對上式兩邊做模mi運(yùn)算，即得到該剩余數(shù)系統(tǒng)內(nèi)部各個模通道的縮放結(jié)果 yi。

定理1:根據(jù)新中國余數(shù)定理1(New CRT-Ⅰ)，余數(shù)(x1，x2，x3，x4)RNS表示權(quán)重數(shù) X具有 0至 M 區(qū)間有唯一解[4]，即：

ki表示乘法逆元。

對于模集合針對 4模集合{m1，m2，m3，m4}其對應(yīng)于{2n，22n+1，2n+1，2n-1}，根據(jù)式(3)：

其中 k1=23n，k2=2n-1，k3=2n-2。Y進(jìn)一步表示為：

取比例因子K=2n，設(shè)，i=1，2，3，4。對于的結(jié)果不存在。不能用式(2)直接計算y1，必須采用其他的方法解決。對于K與mi互質(zhì)，直接計算得到結(jié)果。將 m2，m3，m4帶入，K=2n。則：

關(guān)于 m1通道，由于不存在，不能用式(2)直接計算。將X=x1+2nY直接帶入式(1)：

2 電路實現(xiàn)

2.1 y1的硬件實現(xiàn)

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

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

由前面的分析可知，對于模通道22n進(jìn)行2n比例變化結(jié)果y1，直接取Y的低n位即可實現(xiàn)。應(yīng)用定理1和2，通過進(jìn)一步合并化簡，Y最終轉(zhuǎn)換為5個4n位操作數(shù)相加的形式，即：

通過3級進(jìn)位保留加法器(CSA)，最終形成兩個4n位寬的S、C，S和 C通過模24n-1加法器得到4n位模加法器的結(jié)果Y，如圖1所示。

圖1 文中提出的比例變換結(jié)構(gòu)圖

2.2 y2的硬件實現(xiàn)

對于模通道 m2=22n+1進(jìn)行 2n比例變化，根據(jù)式(6)，為了進(jìn)一步減少硬件復(fù)雜度，采用縮一碼模 22n+1加法器，y2進(jìn)一步表示為：

操作數(shù)在進(jìn)入縮一碼模22n+1加法器之前必須分別減1，而縮一碼模22n+1加法器在輸出以后必須加1才能得到真正的結(jié)果。兩者合并，只要將進(jìn)位加法器的輸出減1即可。同時，根據(jù)定理4，進(jìn)位保留加法器的最高有效位的進(jìn)位輸出將被直接取反加到下一級進(jìn)位保留加法器的最低有效位的同時，需要加上一個補(bǔ)償常數(shù)因子 2n。聯(lián)合前面縮一碼模 22n+1加法器的校正因子-1，總的校正項Cj為：

最終y2表示為：

直接將上面的三項輸入法進(jìn)位反轉(zhuǎn)的回轉(zhuǎn)進(jìn)位保留加法器，得到進(jìn)位2n位C和2n位和位S，將C和S直接輸入到縮一碼模2n+1加法器，該縮一碼模2n+1加法器的輸出即為實際的比例變換結(jié)果。

2.3 y3的硬件實現(xiàn)y3的實現(xiàn)和y2相似，同樣通過進(jìn)位保留加法器樹和一個縮一碼模 22n+1加法器實現(xiàn)。通過化簡式(7)：

設(shè)校正項為 Cj，同理，總的校正因子Cj為：

上面得到的校正項與式(13)的第3項合并：

最終，y3表示為：

2.4 y4的硬件實現(xiàn)

對于模通道m(xù)4=2n-1進(jìn)行 2n比例變化結(jié)果 y4，根據(jù)式(8)，應(yīng)用定理2，進(jìn)一步表示為：

該模通道比例變化y4的實現(xiàn)只需要將上面的兩個n位操作數(shù)直接通過一個0唯一表示的模2n-1加法器，即可實現(xiàn)。

整個基于 4模集合{2n，22n+1，2n+1，2n-1}的反向轉(zhuǎn)換以及比例轉(zhuǎn)化的硬件結(jié)構(gòu)圖如圖1所示。

3 性能評估和比較

為了進(jìn)行定性評估，本文與同樣對4模集合2n比例變換文獻(xiàn)[4]的理論模型進(jìn)行對比。采用文獻(xiàn)[4]提出的門單位計算方法，用近似門單位模型方法計算其硬件以及信號處理延時，即 2輸入異或門(XOR)或者同或門(XNOR)的面積和延遲按照2個單位計算，一個全加器(FA)等同于7個單位的面積和4個單位的延遲，非門(NOT)的面積和延遲都以 0計算，其他基本的二輸入邏輯門面積和延遲按照1個單元計算。為了更加公平的對比，本研究和文獻(xiàn)[4]所有的模 2n-1加法器均采用目前最優(yōu)化的 0唯一表示的并行前綴模 2n-1加法器[6]，縮一碼模2n+1加法器采用文獻(xiàn)[7]提出的模加法器模型。提出的新的比例變換模型各個通道面積理論數(shù)據(jù)如表1所示，和其他模集合比例轉(zhuǎn)換器面積和延時對比如表2所示。從中可以看出，本文所提出的4比例變換器模型，在動態(tài)范圍大的情況下，在硬件復(fù)雜度方面占有絕對的優(yōu)勢。

表1 4個比例轉(zhuǎn)換通道面積理論數(shù)據(jù)

表2 面積和延時的理論數(shù)據(jù)比較

4 結(jié)論

余數(shù)系統(tǒng)的比例變換是避免在剩余數(shù)系統(tǒng)的中間運(yùn)算過程中發(fā)生溢出錯誤的主要方法。基于此，針對4模集合{2n，22n+1，2n+1，2n-1}，在分析反向轉(zhuǎn)換和比例縮放算法的基礎(chǔ)上，提出了一個新的反向轉(zhuǎn)換和基于2n的比例縮放算法，并基于加法器實現(xiàn)其VLSI結(jié)構(gòu)，使該模集合能夠得到更加廣泛的應(yīng)用。理論分析結(jié)果表明，在具有相同模通道數(shù)的同類比例變換器中，本研究的算法更加優(yōu)化，硬件性能表現(xiàn)更加優(yōu)異。

[1]ANTONIO G，ANTONIO L.A look-up scheme for scaling in the RNS[J].IEEE Transactions on Computers，1999，48 (7)：748-751.

[2]TAY T，CHANG C H，LOW J.Efficient VLSI implementation of 2nscaling of signed integer in RNS{2n-1，2n，2n+1，}[J]. IEEE Transactions on Very Large Scale Integration(VLSI) Systems，2013，21(10)：1936-1940.

[3]YE Y，MA S，HU J.An efficient 2n RNS scaler for moduli set{2n-1，2n，2n+1，}[C].IEEE Symp.Inf.Sci.Eng.(ISISE)，Shanghai，China，2008.12：511-515.

[4]SOUSA L.2n RNS Scalers for Extended 4-Moduli Sets[J]. IEEE Transactions on Computers，2015，62(12)：1-14.

[5]CAO B，CHANG C H，SRIKANTHAN T.A residue-tobinary converter for a new five-moduli set[J].IEEE Transactions on Circuits and Systems-I，2007，54(5)：1041-1049.

[6]PATEL R A，BENAISSA M，BOUSSAKTA S.Fast parallelprefix architectures for modulo 2n-1 Addition with a single representation of zero[J].IEEE Transactions on Computers，2007，56(11)：1484-1492.

[7]VERGOS H，EFSTATHIOU C，NIKOLOS D.Diminished-one modulo 2n+1 adder design[J].IEEE Transactions on Computers，2002，51(12)：1389-1399.

[8]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.

RNS scaler for the 4-moduli set RNS

Lv Xiaolan，Cui Delong
(College of Computer and Electronic Information，Guangdong University of Petrochemical Technology，Maoming 525000，China)

Scaling and parity check in RNS has always been conceived as a performance bottleneck similar to the residue system. In this paper，a simple and fast 2nscaling scheme for the four-moduli set{2n，22n+1，2n+1，2n-1}RNS is proposed baesd on the new Chinese remainder theorem.The analysis result shows that the proposed scaler has higher area and power consumption performances compared with the cascaded scaling scheme.

new Chinese remainder theorem(CRT);reverse converter;scaling;VLSI

TN47

A

10.16157/j.issn.0258-7998.2015.08.013

呂曉蘭，崔得龍.4模集合余數(shù)系統(tǒng)比例變換[J].電子技術(shù)應(yīng)用，2015，41(8)：47-49.

英文引用格式:Lv Xiaolan，Cui Delong.RNS scaler for the 4-moduli set RNS[J].Application of Electronic Technique，2015，41 (8)：47-49.

2015-05-04)

呂曉蘭(1979-)，女，實驗師，主要研究方向：VLSI數(shù)字信號處理芯片的設(shè)計研究。

國家自然科學(xué)基金面上項目(61473331)