剩余數(shù)系統(tǒng){2n+1,2n+1+1,2n}符號檢測設(shè)計與優(yōu)化*

呂曉蘭,肖　明

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

?

剩余數(shù)系統(tǒng){2n+1,2n+1+1,2n}符號檢測設(shè)計與優(yōu)化*

呂曉蘭*,肖明

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

摘要:提出一個新的針對剩余數(shù)模集合{2n+1,2n+1+1,2n},快速的符號檢測算法。該符號檢測系統(tǒng)僅由3個單元組成,一個n位寬度的僅為保留加法器單元,一個n位比較器單元和一個n位前綴加法器單元,其中進位保留加法器和比較器單元是并行的。實驗結(jié)果表明,相比于其他剩余數(shù)符號檢測系統(tǒng),平均速度提高了約36%,面積相對保留約63%。

關(guān)鍵詞:剩余數(shù)系統(tǒng);符號檢測;VLSI;加法器

剩余數(shù)系統(tǒng)(RNS)以其特有無權(quán)重特性在當(dāng)前超大規(guī)模數(shù)字信號處理領(lǐng)域得前所未有的關(guān)注[1]。而符號檢測在剩余數(shù)系統(tǒng)的大小比較,溢出檢測等領(lǐng)域起著不可缺少的作用。剩余數(shù)系統(tǒng)的符號檢測相比權(quán)重數(shù)系統(tǒng)要復(fù)雜得多,剩余數(shù)系統(tǒng)符號檢測近年來已成為剩余數(shù)系統(tǒng)研究的熱點問題。

同其他剩余數(shù)系統(tǒng)研究一樣,基于剩余數(shù)系統(tǒng)的符號檢測電路也同樣經(jīng)歷了從查找表到純組合邏輯電路的實現(xiàn)過程[2-6]。Zenon D Ulman在1983年基于混合基算法首次提出了一種符號檢測電路的算法,并基于查找表實現(xiàn)[2]。2003年,Al-Radadi E和Siy P基于新中國余數(shù)定理2提出一個新的符號檢測算法,但是該方法基于多層轉(zhuǎn)化完成,硬件復(fù)雜[5]。直到2008年,Tomczak T首次基于通用模集合{2n-1,2n,2n+1}提出了一個純邏輯電路構(gòu)成的符號檢測電路,不依賴于查找表,但其不適合于其他的模集合符號檢測實現(xiàn)[6],本文基于模集合{2n+1,2n+1+1,2n},在混合基-中國余數(shù)定理定理(MR-CRT)算法的基礎(chǔ)上,實現(xiàn)該模集合下剩余數(shù)符號檢測,硬件完全基于門級電路實現(xiàn)。

1　算法描述

根據(jù)RNS整數(shù)定義,余數(shù)系統(tǒng)中可唯一表示[0,M)之間定義任意正整數(shù)X,M為該剩余數(shù)系統(tǒng)的動態(tài)范圍。根據(jù)數(shù)值所處的區(qū)間劃分有符號RNS整數(shù),當(dāng)X的在區(qū)間[0,M/2)內(nèi)時,表示正數(shù),符號位為0;當(dāng)X在區(qū)間[M/2,M)內(nèi)時,則表示負數(shù),符號位為1。符號檢測函數(shù)Sgn(X):

(1)

根據(jù)混合基-中國余數(shù)定理[7],權(quán)重數(shù)X表示為:

(2)

其中:mi為兩兩互質(zhì)的模,

對于給定模集合{2n+1,2n+1+1,2n},m1=2n+1,m2=2n+1+1,m3=2n,動態(tài)范圍M=2n(2n+1)(2n+1+1),M/2=2n-1(2n+1)(2n+1+1),根據(jù)余數(shù)系統(tǒng)符號函數(shù)定義:

(3)

則根據(jù)式(2),模集合{2n+1,2n+1+1,2n}表示的權(quán)重數(shù)X為:

X=α2m1m2+α1m1+α0

(4)

其中:α0=x1,α1=|γ1x1+γ2x2|m2;

α2=┕γ1x1+γ2x2+γ3x3/m2」|m3

(5)

當(dāng)X

(6)X

Sgn(x1,x2,x3)=MAX(α2)=

MAX(|┕γ1x1+γ2x2+γ3x3/m2」|m3)

(7)

2　硬件實現(xiàn)

根據(jù)式(7):

(8)

(9)

由于0≤x2≤2n+1,0≤x1≤2n,根據(jù)分析得到:

(10)

令:

(11)

(12)

最終的符號檢測函數(shù):

Sgn(x1,x2,x3)=MAX(α2)=

(13)符號“&”表示并置連接。整個符號檢測系統(tǒng)的硬件實現(xiàn)由3個模塊組成,一個3輸入n位進位保留加法器(CSA)[8],一個n位比較器(w和f實現(xiàn)單元),一個n位前綴加法計算單元(符號位生成單元),進位保留加法器和比較器并行,系統(tǒng)實現(xiàn)結(jié)構(gòu)如圖1所示。

圖1　符號檢測架構(gòu)圖

圖2　基本單元的邏輯實現(xiàn)

圖3　n位比較器結(jié)構(gòu)圖

圖4　w和f邏輯實現(xiàn)

圖5　符號位生成模塊邏輯實現(xiàn)

舉例:設(shè)n=8,則(m1,m2,m3)分別為(257,513,256)。M=33751296,M/2=16875648。

例1:設(shè)X=6875776,其剩余數(shù)表示為(255,37,128),二進制表示為x1=(011111111)2,x2=(0000100101)2,x3=(10000000)2。根據(jù)式(11),w=0,f=0,則根據(jù)式(12),α2=(00110100)2,Sgn(x1,x2,x3)=MAX(α2)=0。

例2:設(shè)X=26875776,其剩余數(shù)表示為(1,0,128),即x1=(000000001)2,x2=(0000000000)2,x3=(10000000)2。根據(jù)式(11),w=0,f=0,根據(jù)式(12),α2=(10000000)2,Sgn(x1,x2,x3)=MAX(α2)=1。

3　性能評估和比較

為了對本文提出的模集合{2n+1,2n+1+1,2n}符號檢測算法進行定性和定量的評估,本文與文獻[5]提出的符號檢測算法進行比較。文獻[5]將模集合{2n+1,2n+1+1,2n}分成X12={2n+1+1,2n+1}和X={(2n+1+1)(2n+1),2n}2級進行處理,根據(jù)文獻[5],Sgn(X)=maxL(X)=max(|x3-x2-Y|2n),其中Y=|2x2-2x1|2n+1+1,該硬件實現(xiàn)模塊包括一個模2n+1+1加法器,一個3輸入CSA和一個n位前綴加法計算單元。均采用Tyagi[9]提出的門單元計算方法作為面積和延時的計算標(biāo)準(zhǔn)。2輸邏輯門(AND,OR,NOT)作為面積和延時上的1個單位計算,2輸入異或門/同或門作為2個單位的面積和延時計算。表1示出了本文和文獻[5]提出的算法針對模集合{2n+1,2n+1+1,2n}的符號檢測在硬件面積和延遲的理論數(shù)據(jù)對比。從中可以看出,在n相同的情況下,無論在延時和硬件消耗方面,本文提出的算法明顯優(yōu)于文獻[5]給出的算法模型。

表1　模2n+1加法器電路的面積和延遲對比

將本文和文獻[5]提出的2種模型利用Verilog語言建模,ModeSim中仿真驗證,并在保持約束條件相同條件下,分別設(shè)n=4,8,16,32,利用SIMC的標(biāo)準(zhǔn)單元庫(0.18μm,1.98V,0 ℃)和SynopsysDesignComplier采用面積迭代優(yōu)化和延時迭代優(yōu)化進行綜合,不同n值下面積優(yōu)化與延時優(yōu)化結(jié)果如表2所示。

表2　面積和延時優(yōu)化的實驗結(jié)果

從表2看出,文中提出的符號檢測系統(tǒng)面積消耗平均比文獻[5]的保留63%,運算速度比文獻[5]平均要快36%。

4　結(jié)束語

針對模集合{2n+1,2n+1+1,2n},基于混合基-中國余數(shù)定理,提出了該模集合下剩余數(shù)的符號檢測算法,并且基于組合電路實現(xiàn)了該模集合下剩余數(shù)系統(tǒng)符號檢測電路設(shè)計。理論對比和實驗結(jié)果表明,相比于近年提出的剩余數(shù)符號檢測算法,文中提出的符號檢測系統(tǒng),在硬件消耗和速度方面都占有一定的優(yōu)勢。

參考文獻:

[1]Miroslav D L,Dejan V T,Brian L E.信號處理濾波器設(shè)計——基于MATLAB和Mathematica的設(shè)計方法[M].朱義勝,董輝,等譯.北京:電子工業(yè)出版社,2004:250-256.

[2]Ulman Z D.Sign Detection and Implicit-Explicit Conversion of Numbers in Residue Arithmetic[J]IEEE Trans.Comput.,1983,C-32(6):590-594.

[3]Vu T V.Efficient Implementations of the Chinese Remainder Theorem for Sign Detection and Residue Decoding[J].IEEE Trans Comput,1985,C-34(7):646-651.

[4]Kaushik S.Sign Detection in Residue Code[J].Comput and Elect Engineering,1986,12(1):65-71.

[5]Al-Radadi E,Siy P.RNS Sign Detector Based on Chinese Remainder Theorem Ⅱ(CRT Ⅱ)[J].Comput Math Appl,2003,46(10-11):1559-1570.

[6]Tomczak T.Fast Sign Detection for RNS(2n-1,2n,2n+1)[J].IEEE Trans Circuits Syst I,2008,55(6):1502-1511.

[7]Bi S Q,Gross W J.The Mixed-Radix Chinese Remainder Theorem and Its Applications to Residue Comparison[J].IEEE Trans Comput,2008,57(12):1624-1632.

[8]Piestrak S J.Design of Residue Generators and Multioperand Modular Adders Using Carry-Save Adders[J].IEEE Trans Comput,1994,43(1):68-77.

[9]Tyagi A A.Reduced-Area Scheme for Carry-Select Adders[J].IEEE Trans Comp,1993,42(10):1163-1170.

呂曉蘭(1979-),女,漢族,陜西岐山人,廣東石油化工學(xué)院,實驗師,主要從事VLSI數(shù)字信號處理芯片的設(shè)計研究,jingling220@126.com。

DesignandOptimizationofSignDetectioninResidueNumberSystem{2n+1,2n+1+1,2n}*

LüXiaolan*,XIAOMing

(College of Computer and Electronic Information,Guangdong University of Petrochemical Technology,Maoming Guangdong 525000,China)

Abstract:We propose a fast algorithm for sign-extraction of a number given in the Residue Number System{2n+1,2n+1+1,2n}.The algorithm can be implemented using three units,one n-bit wide carry save adder,one n-bit wide comparator,and one prefix adder unit,two of which can be done in parallel.The experimental results indicate that the proposed circuit offers 63%,and 36% savings on average in terms of area,and delay,respectively,better than the unit based on previous sign detection algorithm.

Key words:RNS(residue number system);sign detection;VLSI;adder

doi:EEACC:257010.3969/j.issn.1005-9490.2014.04.007

中圖分類號:TN47

文獻標(biāo)識碼:A

文章編號:1005-9490(2014)04-0613-04

收稿日期:2014-03-12修改日期:2014-04-28

項目來源:廣東省自然科學(xué)基金重點項目(S2011020002735)