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

軟件與算法

循環(huán)卷積DFT的優(yōu)化算法與仿真*

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

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

DFT；余數(shù)系統(tǒng)；FIR；優(yōu)化；Mode1sim

O 引言

余數(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ù)字信號處理（Programmab1e Digita1 Signa1Processing，PDSP）和特定用途集成電路（APP1ication SPecific Integrated Circuit，ASIC）的構(gòu)建，正處于革命性的數(shù)字信號處理技術(shù)的前沿，在更多系統(tǒ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)范圍在這個同構(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.2 DFT算法

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

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

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

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

x［k］-x［0］的循環(huán)卷積即為：

用矩陣表示為：

1.3 FlR濾波器圖解

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

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

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

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

表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 算法的優(yōu)化與仿真

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

乘法器-加法器圖（MAG）技術(shù)是將系數(shù)拆分成幾個因子，再通過幾條路徑來組合這些不同的因子，DemPster等人給出了所有合成成本為1～4個加法器的所有系數(shù)的可能配置，系數(shù)的MAG圖成本為｛0，2，3，3，3｝，共11個加法器。最優(yōu)簡化加法器圖（RAG）能夠進一步降低總工作量。DemPster和Mac1eod首先提出的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。

表2 RAG優(yōu)化措施

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

圖2 RAG優(yōu)化加法器圖

2.2 N ode lSim仿真

采用Veri1og語言，運用轉(zhuǎn)置FIR濾波器結(jié)構(gòu)共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語言仿真平臺Mode1Sim上進行仿真，可以看到，輸入信號序列x（n）=（10，20，30，40，50），y_rea1和y_imag分別為X（k）的實部和虛部，由仿真結(jié)果可得X（k）=（-25 +j34，-25 +j8，-25 -j9，-25 -j35，150），與手工計算所得結(jié)果完全一致。循環(huán)卷積DFT的Veri1og仿真結(jié)果如圖3。

圖3 循環(huán)卷積DFT的Veri1og仿真結(jié)果

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ù)+1（t=1，2，3，4），長度很有限［9］，對較長序列則需分解為多維短序列來計算。

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

［2］裴定一，祝躍飛.算法數(shù)論［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數(shù)字濾波器設計及其FPGA實現(xiàn)［J］.微型機與應用，2013，32（19）：22-24，28.

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

［7］UweMeyer-Baese.數(shù)字信號處理的FPGA實現(xiàn)［M］.劉凌，譯.北京：清華大學出版社，2003.

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

［9］劉昌進.基于數(shù)論變換的運動估計算法研究［D］.合肥：中國科學技術(shù)大學，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

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

2016-01-06）

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

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