韓芳，陳帥

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

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

　　關鍵詞：DFT；余數系統；FIR；優化；Modelsim

　　0引言

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

1循環卷積DFT算法

　　1.1余數系統

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

　　1.2DFT算法

　　素數因子循環卷積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}。

　　可以看到該式的右側是一個循環卷積，即：

　　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系數，也稱作“抽頭權重”。循環卷積DFT與FIR濾波器是等價的，圖1給出了式(6)相應的采用FIR濾波器的圖形化解釋。其中系數Wk5是復數，8位量化值如表1所示。　

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

2算法的優化與仿真

　　2.1系數的RAG優化

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

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

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

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

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

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

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

　　根據此原則，RAG算法優化措施如表2。表2RAG優化措施需要實現的系數措施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］。“STAGES”進程是一個區分3個狀態：START、LEAD和RUN的狀態機。“STRUCTURE”進程則定義了兩個FIR濾波器通路，分別計算實部和虛部。“COEFF”進程為乘法器系數模塊，而“RAG”進程實現優化的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)，與手工計算所得結果完全一致。循環卷積DFT的Verilog仿真結果如圖3。

3結論

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

　　參考文獻

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

　　［2］ 裴定一,祝躍飛.算法數論［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.

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

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

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

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