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

呂曉蘭，崔得龍

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

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

呂曉蘭，崔得龍

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

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

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

0 引言

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

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

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

1 算法描述

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

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

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

ki表示乘法逆元。

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

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

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

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

2 電路實現(xiàn)

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

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

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

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

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

圖1 文中提出的比例變換結構圖

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

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

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

最終y2表示為：

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

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

設校正項為 Cj，同理，總的校正因子Cj為：

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

最終，y3表示為：

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

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

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

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

3 性能評估和比較

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

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

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

4 結論

余數(shù)系統(tǒng)的比例變換是避免在剩余數(shù)系統(tǒng)的中間運算過程中發(fā)生溢出錯誤的主要方法?；诖?，針對4模集合{2n，22n+1，2n+1，2n-1}，在分析反向轉換和比例縮放算法的基礎上，提出了一個新的反向轉換和基于2n的比例縮放算法，并基于加法器實現(xiàn)其VLSI結構，使該模集合能夠得到更加廣泛的應用。理論分析結果表明，在具有相同模通道數(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].電子技術應用，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ù)字信號處理芯片的設計研究。

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