摘要： 在利用FPGA實現(xiàn)數(shù)字信號處理方面，分布式算法發(fā)揮著關(guān)鍵作用，與傳統(tǒng)的乘積-積結(jié)構(gòu)相比，具有并行處理的高效性特點。詳細研究了基于FPGA、采用分布式算法實現(xiàn)FIR數(shù)字濾波器的原理和方法，并通過Xilinx ISE在Modelsim下進行了仿真。

關(guān)鍵詞： 分布式算法 DALUT FPGA FIR

數(shù)字濾波器正在迅速地代替?zhèn)鹘y(tǒng)的由R、L、C元件和運算放大器組成的模塊濾波器并且日益成為DSP的一種主要處理環(huán)節(jié)。FPGA也在逐漸取代ASIC和PDSP，用作前端數(shù)字信號處理的運算（如：FIR濾波、CORDIC算法或FFT）。乘累加運算是實現(xiàn)大多數(shù)DSP算法的重要途徑，而分布式算法則能夠大大提高乘累加運算的效能。

1 傳統(tǒng)的乘累加結(jié)構(gòu)FIR數(shù)字濾波器基本理論

FIR濾波器被稱為有限長脈沖響應(yīng)濾波器，與IIR數(shù)字濾波器相對應(yīng)，它的單位脈沖響應(yīng)h(n)只有有限個數(shù)據(jù)點。輸入信號經(jīng)過線性時不變系系統(tǒng)輸出的過程是一個輸入信號與單位脈沖響應(yīng)進行線性卷積的過程，即：

式中，x(n)是輸入信號，y(n)是卷積輸出，h(n)是系統(tǒng)的單位脈沖響應(yīng)?？梢钥闯?，每次采樣y(n)需要進行L次乘法和L-1次加法操作實現(xiàn)乘累加之和，其中L是濾波器單位脈沖響應(yīng)h(n)的長度?？梢园l(fā)現(xiàn)，當(dāng)L很大時，每計算一個點，則需要很長的延遲時間。

2 乘累加運算的位寬分配

DSP算法最主要的就是進行乘累加運算。假設(shè)采樣信號的位寬用N來表示，則N位與N位的乘累結(jié)果需要2N位的寄存器來保存；如果兩個操作數(shù)都是有符號數(shù)，則乘積只有2N-1個有效位，因為產(chǎn)生了兩個符號位。

為了使累加器的結(jié)果不產(chǎn)生溢出，需要對累加器進行冗余設(shè)計，也就是說要在累加器2N的位寬上多設(shè)計出K位，累加器的長度M計算方式如下（L為濾波器的長度）：

對于無符號數(shù)：M=2N+K=2N+log2 L

對于有符號數(shù)：M=2N=K=2N+log2 L-1

3 乘累加運算的分布式算法原理分析

得益于Xilinx FPGA查找表結(jié)構(gòu)的潛能，分布式算法在濾波器設(shè)計方面顯示出了很高的效率，自20世紀(jì)90年代初以來越來越受到人們的重要。分布式算法是基于查找表的一種計算方法，在利用FPGA實現(xiàn)數(shù)字信號處理方面發(fā)揮著重要的作用，可以大大提高信號的處理效率。它主要應(yīng)用于數(shù)字濾波、頻率轉(zhuǎn)換等數(shù)字信號處理的乘累加運算。

分布式算法推導(dǎo)如下：

設(shè)Ak是已知常數(shù)（如濾波器系數(shù)、FFT中的正弦/余弦基本函數(shù)等），xk(n)是變量，可以看作是n時刻的第k個采樣輸入數(shù)據(jù)，y(n)代表n時刻的系統(tǒng)響應(yīng)。那么它們的內(nèi)積為：

其中，xk(n)變量可以寫成下面的格式：

式中，B為數(shù)據(jù)格式的字長,xkb是變量的二進制位，只有“0”和“1”兩種狀態(tài)。將（2）式代入（1）式得：

4 FPGA實現(xiàn)過程中查找表的構(gòu)造方法

根據(jù)以上論述，括號中的每一乘積項代表著輸入變量的某一位與常量的二進制“與”操作，加號代表著算術(shù)和操作，指數(shù)因子對括號中的值加權(quán)。如果事先構(gòu)造一個查找表，該表存儲著括號中所有可能的組合值，就可以通過所有輸入變量相對應(yīng)位的組合向量（XNb,X(N-1)b,...x1b）對該表進行尋址，該查找表稱為DALUT。DALUT的構(gòu)造規(guī)則如表1所示。

5 采用分布式算法實現(xiàn)FIR數(shù)字濾波器

為了說明問題，以一個三個系數(shù)的FIR數(shù)字濾波器為例設(shè)計分布式算法，字寬也設(shè)置為三位。設(shè)FIR數(shù)字濾波器系數(shù)為：h(0)=5,h(1)=2,h(2)=3。

在進行FPGA設(shè)計時，該表以組件Component形式構(gòu)建，設(shè)置為ROM結(jié)構(gòu)，提供輸入尋址端口table_in[2..0],輸出端口table_out[3..0]。FPGA算法的結(jié)構(gòu)圖如圖2所示。

算法實現(xiàn)中的幾個關(guān)鍵問題為：

（1）采用狀態(tài)機實現(xiàn)分布式算法的狀態(tài)轉(zhuǎn)移

狀態(tài)機的實現(xiàn)如圖3所示，設(shè)置三個狀態(tài)s0、s1、s2 。狀態(tài)s0完成數(shù)據(jù)的裝入，數(shù)據(jù)寄存器需要成對出現(xiàn)，一個完成數(shù)據(jù)的延遲，另一個完成數(shù)據(jù)的移位，并將狀態(tài)轉(zhuǎn)移到s1；狀態(tài)s1完成查找表功能、數(shù)據(jù)移位和分布式算法的乘累加運算，數(shù)據(jù)移位一個數(shù)據(jù)寬帶后將狀態(tài)轉(zhuǎn)移到s2;狀態(tài)s2完成數(shù)據(jù)的輸出，并將狀態(tài)轉(zhuǎn)移到s0。利用狀態(tài)機可以條理清楚地簡化計算過程，在算法實現(xiàn)時發(fā)揮著關(guān)鍵的作用。

（2）系統(tǒng)時鐘與數(shù)據(jù)輸入時鐘的關(guān)系

根據(jù)上述的狀態(tài)轉(zhuǎn)移關(guān)系，可以得出：每輸入一個數(shù)據(jù)，在下一次數(shù)據(jù)輸入之前，需要在狀態(tài)s1停留一個數(shù)據(jù)寬帶（三位）的時鐘時間，在s2停留一個時鐘的數(shù)據(jù)輸出時間。也就是說，系統(tǒng)時鐘頻率應(yīng)是數(shù)據(jù)輸入頻率的5倍，即fclkock=5fxin。

（3）分布式算法中的乘累加式公推導(dǎo)及核心代表實現(xiàn)

設(shè)B是數(shù)據(jù)的字寬，Pn是分布式算法第n位的結(jié)果，則有：

有了該關(guān)系式，就可以通過for...loop循環(huán)，使用一條語句完成分布式乘累加算法。具體如下：

for n in 0 to B-1 loop

P:=p/2+tableout(n)*2B-1;

End loop;

6 算法仿真驗證與結(jié)論

本文實現(xiàn)的FIR濾波器在Xilinx的集成開發(fā)環(huán)境ISE下利用ModelSim進行了仿真。當(dāng)輸入數(shù)據(jù)為7，3，1...時，仿真輸出依次為35,29,32,16...,與乘累加方式FIR濾波算法得出的結(jié)果完全一致。假設(shè)查找表和PDSP的通用乘法器延時時間相同，分布式算法的等待時間是Br,通用乘法器的等待時間是N1。可見，對于位寬較小的數(shù)據(jù)來說，分布式算法的執(zhí)行速度遠高于乘累加運算?？梢?，利用FPGA實現(xiàn)分布式計算大大提高了計算的速度，在高速信號處理中發(fā)揮著重要作用。