韓芳，陳帥

　?。ɑ茨蠋煼秾W(xué)院 機(jī)械與電氣工程學(xué)院,，安徽 淮南 232038）

       摘要：根據(jù)余數(shù)系統(tǒng)中模映射法則以及數(shù)論變換,，將素數(shù)N點的DFT運算轉(zhuǎn)換為N-1點的循環(huán)卷積運算,，建立了算法模型，給出了此算法的FIR濾波器圖解,，并對加法器系數(shù)進(jìn)行RAG優(yōu)化,，最后在ModelSim仿真平臺上,，用Verilog語言實現(xiàn)該算法，并進(jìn)行了仿真結(jié)果分析和工作量分析,。RAG優(yōu)化后減少了加法器數(shù)量,，降低了路徑延遲。

　　關(guān)鍵詞：DFT,；余數(shù)系統(tǒng),；FIR；優(yōu)化,；Modelsim

　　0引言

　余數(shù)系統(tǒng)（Residue Number System, RNS）將傳統(tǒng)的二進(jìn)制數(shù)值表征系統(tǒng)中多位寬運算轉(zhuǎn)換成多個并行且獨立的短位寬運算,，能夠提高運算速度以及降低運算單元的功耗，從而提升并行處理單元的性能,。離散傅里葉變換（Discrete Fourier Transform, DFT）是一種應(yīng)用極為廣泛的信號處理方法,，與RNS相結(jié)合，因其成本和速度上的優(yōu)勢,，在大量乘加運算的數(shù)字信號處理系統(tǒng)中得到廣泛應(yīng)用和研究,。當(dāng)前可編程數(shù)字信號處理（Programmable Digital Signal Processing, PDSP）和特定用途集成電路 (Application Specific Integrated Circuit, ASIC)的構(gòu)建，正處于革命性的數(shù)字信號處理技術(shù)的前沿,，在更多系統(tǒng)前端（如傳感器,、濾波器的應(yīng)用等）正在逐漸替代DSP［1］。DFT在可編程器件上的快速實現(xiàn)算法和結(jié)構(gòu)值得深入研究,。

1循環(huán)卷積DFT算法

　　1.1余數(shù)系統(tǒng)

　　余數(shù)系統(tǒng)（Residue Number System,，RNS）是一種古老的非權(quán)重數(shù)值表征系統(tǒng)，基于RNS可以實現(xiàn)加法,、減法,、乘法等整數(shù)運算。在相對素數(shù)的正整數(shù)基{m1,，m2,，…，mL}下定義動態(tài)范圍M,，M=Ll=1ml,，在這個同構(gòu)計算環(huán)內(nèi)，定義：ZMZm1×Zm2×…×ZmL,，其中ZM=Z/(M)與整數(shù)模M的計算環(huán)相關(guān),，被稱為余數(shù)類模mod M［2］。通過xl=X mod ml定義數(shù)組X（x1,，x2,，…,xL），其中l(wèi)=1,2,…,L，這種模映射可實現(xiàn)代數(shù)運算,。

　　1.2DFT算法

　　素數(shù)因子循環(huán)卷積DFT算法也叫Rader算法［3］,，定義素數(shù)長度N的DFT如下：

　　其直流組成部分：X［0］=∑N－1n=0x［n］。由于N是素數(shù),，根據(jù)數(shù)論變換理論可知：存在一個本原元素,，一個生成元g，也就是a=gαmodp,，該公式可以生成Zp域內(nèi)除零之外的所有元素即(Zp/{0}),，即在Zp/{0}中的整數(shù)a和Zp-1域中的指數(shù)之間存在一一對應(yīng)的映射［4］。通過一個本原元素和一個生成元g產(chǎn)生元素n和k,，用gn模N映射n,，得到以下的模映射：

　　其中k∈{1,2,3,…,N－1}。

　　可以看到該式的右側(cè)是一個循環(huán)卷積,，即：

　　1.3FIR濾波器圖解

　　有限常系數(shù)的FIR濾波器是一種線性時間不變（Linear Time Invariant,，LTI）數(shù)字濾波器［5］。N階FIR的輸出對應(yīng)于輸入時間序列x［n］,，是一種有限卷積形式,，具體形式如下：

　　y［n］=x［n］f［n］=∑L－1k=0x［k］f［n－k］(7)

　　直接FIR濾波器是一種“抽頭延遲”結(jié)構(gòu)，由加法器和乘法器的集合構(gòu)成,。每個乘法器的操作數(shù)就是一個FIR系數(shù),，也稱作“抽頭權(quán)重”。循環(huán)卷積DFT與FIR濾波器是等價的,，圖1給出了式(6)相應(yīng)的采用FIR濾波器的圖形化解釋,。其中系數(shù)Wk5是復(fù)數(shù)，8位量化值如表1所示,?！?/p>

　　在獨立系數(shù)直接形式的模型中，通常把常數(shù)系數(shù)乘法器所需加法器的數(shù)量稱為成本,，圖1的成本為22,。這種直接形式的FIR體系僅在自適應(yīng)濾波器等少數(shù)場合，通過DSP的RSIC結(jié)構(gòu)的硬件開發(fā) ［6］,。通過系數(shù)的RAG優(yōu)化,，可以降低硬件成本，構(gòu)造更為有效的PDSP實現(xiàn),。

2算法的優(yōu)化與仿真

　　2.1系數(shù)的RAG優(yōu)化

　　基于系統(tǒng)的轉(zhuǎn)置結(jié)構(gòu),，有WkN=WN－kN，k∈［1,N－12］,。表1中的系數(shù)具有對稱性,，經(jīng)非負(fù)化處理，需要實現(xiàn)的系數(shù)為：{256,79,243,207,150},，可見工作量可以降低一半,。

　　乘法器-加法器圖（MAG）技術(shù)是將系數(shù)拆分成幾個因子,，再通過幾條路徑來組合這些不同的因子,，Dempster等人給出了所有合成成本為1～4個加法器的所有系數(shù)的可能配置,， 系數(shù)的MAG圖成本為{0,2,3,3,3},，共11個加法器。最優(yōu)簡化加法器圖（RAG）能夠進(jìn)一步降低總工作量,。Dempster和Macleod首先提出的RAG算法規(guī)則［7］如下：

　　(1)去除系數(shù)的符號,，因為符號可以通過濾波器的抽頭延遲線上的減法來實現(xiàn)；

　　(2)輸入集合中2的冪的值通過硬連線的數(shù)據(jù)移位來實現(xiàn),，可以直接去除；

　　(3)創(chuàng)建一個能用一個加法器構(gòu)造的系數(shù)的圖集,；

　　(4)用已知圖集構(gòu)造更高值的乘法器；

　　(5)必要時添加最小非輸出基數(shù)（NOF）作為輔助系數(shù),。

　　根據(jù)此原則，RAG算法優(yōu)化措施如表2,。表2RAG優(yōu)化措施需要實現(xiàn)的系數(shù)措施256, 79,243,207,15028，26+15,，24×15+3，26×3+15，2×7515,3,7524-1,22-1,，79-4

　　此時加法器的數(shù)量可降低到最小值6,，所有的系數(shù)都是由3個加法器和3個減法器實現(xiàn)的,。加法器路徑延遲也從3降低到2,。圖2給出了最終的已簡化的加法器圖,。

　　2.2ModelSim仿真

　　采用Verilog語言,，運用轉(zhuǎn)置FIR濾波器結(jié)構(gòu)共4個進(jìn)程來實現(xiàn)以上設(shè)計［8］?！癝TAGES”進(jìn)程是一個區(qū)分3個狀態(tài)：START,、LEAD和RUN的狀態(tài)機(jī)?！癝TRUCTURE”進(jìn)程則定義了兩個FIR濾波器通路,，分別計算實部和虛部,。“COEFF”進(jìn)程為乘法器系數(shù)模塊,，而“RAG”進(jìn)程實現(xiàn)優(yōu)化的NOF因子,。在Mentor公司的HDL語言仿真平臺ModelSim上進(jìn)行仿真,，可以看到，輸入信號序列x(n)=(10, 20, 30, 40, 50) ,，y_real 和 y_imag 分別為X(k)的實部和虛部,，由仿真結(jié)果可得X(k)=(-25+j34,-25+j8,-25-j9,-25-j35,150)，與手工計算所得結(jié)果完全一致,。循環(huán)卷積DFT的Verilog仿真結(jié)果如圖3。

3結(jié)論

　　利用RNS可將DFT的輸入和輸出序列重新排序,， DFT運算轉(zhuǎn)換成循環(huán)卷積算法,，再用數(shù)論變換來計算卷積，采用RAG優(yōu)化了系數(shù),，當(dāng)N（濾波器階數(shù)）為5時，所用加法器數(shù)量與直接FIR體系相比減少了73%,；與MAG圖相比減少了45% 。特別對于高階濾波器,，因為RAG通過已合成的系數(shù)生成了高密度小系數(shù)柵格,，只要用很少的代價就可以實現(xiàn)新系數(shù),，工作量趨向于N,，大大減少了加法器數(shù)量,，降低了路徑延遲,。該算法的缺陷是要求N-1為高復(fù)合數(shù),，而N又是素數(shù),，因此可供選擇的N只有費馬數(shù)22t+1（t=1,2, 3, 4），長度很有限［9］,，對較長序列則需分解為多維短序列來計算。

　　參考文獻(xiàn)

　?。?］ 馬上.基于余數(shù)系統(tǒng)的數(shù)字信號處理VLSI實現(xiàn)關(guān)鍵技術(shù)研究［D］.成都：電子科技大學(xué), 2009.

　?。?］ 裴定一,祝躍飛.算法數(shù)論［M］.北京:科學(xué)出版社, 2002.

　?。?］ RADER C M. Discrete Fouriertransform when the number of data sample is prime［J］.Proc IEEE, 1968, 56(6):11071108.［4］ LIU Y, LAI EMK. Design and implementation of an RNS based 2D DWT processor［J］. IEEE Transaction on Consumer Electronics,2004, 50(1):376385.

　?。?］ 郝小江,黃昆.FIR數(shù)字濾波器設(shè)計及其FPGA實現(xiàn)［J］.微型機(jī)與應(yīng)用,2013,32(19):2224,28.

　?。?］ 馬維華,謝虎城,梁赫西,，等.基于FPGA的FIR濾波器設(shè)計與實現(xiàn)［J］.微型機(jī)與應(yīng)用,2013,32(23):1315,19.

　?。?］ Uwe MeyerBaese. 數(shù)字信號處理的FPGA實現(xiàn)［M］.劉凌,，譯.北京:清華大學(xué)出版社, 2003.

　　［8］ 呂晨陽,王建.基于System Generator的Rife算法的FPGA實現(xiàn)［J］.電子技術(shù)應(yīng)用,2014,40(4): 4244.

　?。?］ 劉昌進(jìn).基于數(shù)論變換的運動估計算法研究［D］.合肥：中國科學(xué)技術(shù)大學(xué),2005.