韓芳，陳帥

　　（淮南師范學院 機械與電氣工程學院，安徽 淮南 232038）

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

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

　　0引言

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

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

　　1.1余數系統(tǒng)

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

　　1.2DFT算法

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

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

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

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

　　1.3FIR濾波器圖解

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　2.2ModelSim仿真

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

3結論

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

　　參考文獻

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

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

　　［3］ 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數字濾波器設計及其FPGA實現［J］.微型機與應用,2013,32(19):2224,28.

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

　　［7］ Uwe MeyerBaese. 數字信號處理的FPGA實現［M］.劉凌，譯.北京:清華大學出版社, 2003.

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

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