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

韓 芳，陳 帥（淮南師范學(xué)院機(jī)械與電氣工程學(xué)院，安徽淮南232038）

軟件與算法

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

韓 芳，陳 帥
（淮南師范學(xué)院機(jī)械與電氣工程學(xué)院，安徽淮南232038）

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

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

O 引言

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

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

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

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

1.2 DFT算法

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

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

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

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

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

用矩陣表示為：

1.3 FlR濾波器圖解

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

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

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

在獨(dú)立系數(shù)直接形式的模型中，通常把常數(shù)系數(shù)乘法器所需加法器的數(shù)量稱(chēng)為成本，圖1的成本為22。這種直接形式的FIR體系僅在自適應(yīng)濾波器等少數(shù)場(chǎng)合，通過(guò)DSP的RSIC結(jié)構(gòu)的硬件開(kāi)發(fā)［6］。通過(guò)系數(shù)的RAG優(yōu)化，可以降低硬件成本，構(gòu)造更為有效的PDSP實(shí)現(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ù)拆分成幾個(gè)因子，再通過(guò)幾條路徑來(lái)組合這些不同的因子，DemPster等人給出了所有合成成本為1～4個(gè)加法器的所有系數(shù)的可能配置，系數(shù)的MAG圖成本為｛0，2，3，3，3｝，共11個(gè)加法器。最優(yōu)簡(jiǎn)化加法器圖（RAG）能夠進(jìn)一步降低總工作量。DemPster和Mac1eod首先提出的RAG算法規(guī)則［7］如下：

（1）去除系數(shù)的符號(hào)，因?yàn)榉?hào)可以通過(guò)濾波器的抽頭延遲線上的減法來(lái)實(shí)現(xiàn)；

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

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

（4）用已知圖集構(gòu)造更高值的乘法器；

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

根據(jù)此原則，RAG算法優(yōu)化措施如表2。

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

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

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

2.2 N ode lSim仿真

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

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

3 結(jié)論

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

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

［2］裴定一，祝躍飛.算法數(shù)論［M］.北京：科學(xué)出版社，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ù)字濾波器設(shè)計(jì)及其FPGA實(shí)現(xiàn)［J］.微型機(jī)與應(yīng)用，2013，32（19）：22-24，28.

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

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

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

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

安徽高等學(xué)校省級(jí)自然科學(xué)研究重點(diǎn)項(xiàng)目（KJ2014A239）

TN911

A

10.19358 /j.issn.1674-7720.2016.09.004

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

2016-01-06）

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

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