循環卷積DFT的優化算法與仿真*

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

軟件與算法

循環卷積DFT的優化算法與仿真*

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

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

DFT；余數系統；FIR；優化；Mode1sim

O 引言

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

1 循環卷積DFT算法

1.1 余數系統

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

1.2 DFT算法

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

其中k∈｛1，2，3，…，N-1｝。

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

以N=5為例，取本元g =3，其模映射如下：

x［k］-x［0］的循環卷積即為：

用矩陣表示為：

1.3 FlR濾波器圖解

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

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

圖1 五階DFT的FIR濾波器圖解

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

表1的8位量化

表1的8位量化

k 0　 1　 2　 3　 4 Re｛256·Wk5｝256　 79 -207 -207 79 1m｛256·Wk5｝0　 -243 -150 150 243

2 算法的優化與仿真

2.1 系數的RAG優化

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

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

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

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

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

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

根據此原則，RAG算法優化措施如表2。

表2 RAG優化措施

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

圖2 RAG優化加法器圖

2.2 N ode lSim仿真

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

圖3 循環卷積DFT的Veri1og仿真結果

3 結論

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

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

［2］裴定一，祝躍飛.算法數論［M］.北京：科學出版社，2002.

［3］RADERCM.DiscreteFourier-transform when thenumberof datasamP1eisPrime［J］.ProcIEEE，1968，56（6）：1107-1108.

［4］LIU Y，LAIEMK.Design and imP1ementation ofan RNS -based 2-DDWTProcessor［J］.IEEETran-saction on ConsumerE1ectronics，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］UweMeyer-Baese.數字信號處理的FPGA實現［M］.劉凌，譯.北京：清華大學出版社，2003.

［8］呂晨陽，王建.基于SystemGenerator的Rife算法的FPGA實現［J］.電子技術應用，2014，40（4）：42-44.

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

The oPtimization and simu1ation of circu1ar convo1ution DFT

Han Fang，Chen Shuai
（Schoo1of Mechanica1and E1ectric Engineering，Huainan Norma1University，Huainan 232038，China）

In this PaPer，according to the theorem ofmo1d maPPing ru1e in Residue Number System（RNS）and number theoretic transform，the Prime number N-Point Discrete Fourier Transform（DFT）is converted to N-1 Point circu1ar convo1ution oPeration.And a1gorithm mode1 is estab1ished，corresPonding Finite ImPu1se ResPonse（FIR）fi1ter i11ustrated is given by using RAG oPtimized coefficients.Fina11y the a1gorithm is imP1emented by using Veri1og in Mode1Sim simu1ation P1atform and the simu1ating resu1t and ana1ysis are given.It conc1uded that the number of adders and Path de1ay is reduced.

DFT；RNS；FIR；oPtimization；Mode1sim

安徽高等學校省級自然科學研究重點項目（KJ2014A239）

TN911

A

10.19358 /j.issn.1674-7720.2016.09.004

韓芳，陳帥.循環卷積DFT的優化算法與仿真［J］.微型機與應用，2016，35（9）：12-14.

2016-01-06）

韓芳（1980 -），女，碩士，講師，主要研究方向：信息處理、測控系統。

陳帥（1969 -），男，教授，碩士生導師，主要研究方向：傳感器網絡，嵌入式系統。