《電子技術(shù)應用》
您所在的位置:首頁 > 可編程邏輯 > 設(shè)計應用 > 4模集合余數(shù)系統(tǒng)比例變換
4模集合余數(shù)系統(tǒng)比例變換
2015年電子技術(shù)應用第8期
呂曉蘭,崔得龍
廣東石油化工學院 計算機與電子信息學院,,廣東 茂名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)具有更好的面積和功耗特性,。
中圖分類號: TN47
文獻標識碼: A
DOI:10.16157/j.issn.0258-7998.2015.08.013

中文引用格式: 呂曉蘭,崔得龍. 4模集合余數(shù)系統(tǒng)比例變換[J].電子技術(shù)應用,,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.
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
Abstract: 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 2n scaling 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.
Key words : new Chinese remainder theorem(CRT),;reverse converter;scaling,;VLSI

   

0 引言

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

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

    比例變化是余數(shù)系統(tǒng)研究最重要問題之一,比例變化尤其在防止溢出和內(nèi)部乘積處理方面具有舉足輕重的作用。和反向轉(zhuǎn)換一樣,,比例縮放在剩余數(shù)系統(tǒng)實現(xiàn)也涉及到大的延遲和較高的硬件復雜度,,涉及在每一個剩余數(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é)果,,則:

wdz4-gs1-3.gif

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

wdz4-gs4-9.gif

2 電路實現(xiàn)

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

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

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

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

    wdz4-gs10.gif

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

wdz4-t1.gif

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

wdz4-gs11.gif

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

    wdz4-gs12.gif

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

2.3 y3的硬件實現(xiàn)

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

    wdz4-gs13.gif

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

wdz4-gs14-15.gif

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

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

    wdz4-gs16.gif

    該模通道比例變化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 性能評估和比較

    為了進行定性評估,本文與同樣對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所示,,和其他模集合比例轉(zhuǎn)換器面積和延時對比如表2所示,。從中可以看出,本文所提出的4比例變換器模型,,在動態(tài)范圍大的情況下,,在硬件復雜度方面占有絕對的優(yōu)勢。

wdz4-b1.gif

wdz4-b2.gif

4 結(jié)論

    余數(shù)系統(tǒng)的比例變換是避免在剩余數(shù)系統(tǒng)的中間運算過程中發(fā)生溢出錯誤的主要方法,?;诖耍槍?模集合{2n,,22n+1,,2n+1,2n-1},,在分析反向轉(zhuǎn)換和比例縮放算法的基礎(chǔ)上,,提出了一個新的反向轉(zhuǎn)換和基于2n的比例縮放算法,并基于加法器實現(xiàn)其VLSI結(jié)構(gòu),,使該模集合能夠得到更加廣泛的應用,。理論分析結(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 2n scaling 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 moduliset{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-to-binary 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.

此內(nèi)容為AET網(wǎng)站原創(chuàng),,未經(jīng)授權(quán)禁止轉(zhuǎn)載,。