韓芳，陳帥

　　（淮南師范學(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)化，最后在ModelSim仿真平臺(tái)上，用Verilog語(yǔ)言實(shí)現(xiàn)該算法，并進(jìn)行了仿真結(jié)果分析和工作量分析。RAG優(yōu)化后減少了加法器數(shù)量，降低了路徑延遲。

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

　　0引言

　余數(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)處理（Programmable Digital Signal Processing, PDSP）和特定用途集成電路 (Application 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)范圍M，M=Ll=1ml，在這個(gè)同構(gòu)計(jì)算環(huán)內(nèi)，定義：ZMZm1×Zm2×…×ZmL，其中ZM=Z/(M)與整數(shù)模M的計(jì)算環(huán)相關(guān)，被稱為余數(shù)類模mod M［2］。通過xl=X mod ml定義數(shù)組X（x1，x2，…,xL），其中l(wèi)=1,2,…,L，這種模映射可實(shí)現(xiàn)代數(shù)運(yùn)算。

　　1.2DFT算法

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

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

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

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

　　1.3FIR濾波器圖解

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

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

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

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

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

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

　　基于系統(tǒng)的轉(zhuǎn)置結(jié)構(gòu)，有WkN=WN－kN，k∈［1,N－12］。表1中的系數(shù)具有對(duì)稱性，經(jīng)非負(fù)化處理，需要實(shí)現(xiàn)的系數(shù)為：{256,79,243,207,150}，可見工作量可以降低一半。

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

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

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

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

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

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

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

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

　　2.2ModelSim仿真

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

3結(jié)論

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

　　參考文獻(xiàn)

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

　　［2］ 裴定一,祝躍飛.算法數(shù)論［M］.北京:科學(xué)出版社, 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數(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］ Uwe MeyerBaese. 數(shù)字信號(hào)處理的FPGA實(shí)現(xiàn)［M］.劉凌，譯.北京:清華大學(xué)出版社, 2003.

　　［8］ 呂晨陽(yáng),王建.基于System Generator的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.