韓芳，陳帥

　?。ɑ茨蠋煼秾W院 機械與電氣工程學院，安徽 淮南 232038）

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

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

　　0引言

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

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

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

　　余數(shù)系統(tǒng)（Residue Number System，RNS）是一種古老的非權重數(shù)值表征系統(tǒng)，基于RNS可以實現(xiàn)加法、減法、乘法等整數(shù)運算。在相對素數(shù)的正整數(shù)基{m1，m2，…，mL}下定義動態(tài)范圍M，M=Ll=1ml，在這個同構計算環(huán)內(nèi)，定義：ZMZm1×Zm2×…×ZmL，其中ZM=Z/(M)與整數(shù)模M的計算環(huá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ù)之間存在一一對應的映射［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的輸出對應于輸入時間序列x［n］，是一種有限卷積形式，具體形式如下：

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

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

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

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

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

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

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

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

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

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

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

　　(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é)構共4個進程來實現(xiàn)以上設計［8］?！癝TAGES”進程是一個區(qū)分3個狀態(tài)：START、LEAD和RUN的狀態(tài)機?！癝TRUCTURE”進程則定義了兩個FIR濾波器通路，分別計算實部和虛部?！癈OEFF”進程為乘法器系數(shù)模塊，而“RAG”進程實現(xiàn)優(yōu)化的NOF因子。在Mentor公司的HDL語言仿真平臺ModelSim上進行仿真，可以看到，輸入信號序列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ù)，當N（濾波器階數(shù)）為5時，所用加法器數(shù)量與直接FIR體系相比減少了73%；與MAG圖相比減少了45% 。特別對于高階濾波器，因為RAG通過已合成的系數(shù)生成了高密度小系數(shù)柵格，只要用很少的代價就可以實現(xiàn)新系數(shù)，工作量趨向于N，大大減少了加法器數(shù)量，降低了路徑延遲。該算法的缺陷是要求N-1為高復合數(shù)，而N又是素數(shù)，因此可供選擇的N只有費馬數(shù)22t+1（t=1,2, 3, 4），長度很有限［9］，對較長序列則需分解為多維短序列來計算。

　　參考文獻

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

　?。?］ 裴定一,祝躍飛.算法數(shù)論［M］.北京:科學出版社, 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.

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

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

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

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

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