FIR數字濾波器分散式演算法的原理及FPGA實現論文

FIR數字濾波器分散式演算法的原理及FPGA實現論文

　　摘要：在利用FPGA實現數字訊號處理方面，分散式演算法發揮著關鍵作用，與傳統的乘積-積結構相比，具有並行處理的高效性特點。詳細研究了基於FPGA、採用分散式演算法實現FIR數字濾波器的原理和方法，並透過XilinxISE在Modelsim下進行了模擬。

　　關鍵詞：分散式演算法DALUTFPGAFIR

　　數字濾波器正在迅速地代替傳統的由R、L、C元件和運算放大器組成的模組濾波器並且日益成為DSP的一種主要處理環節。FPGA也在逐漸取代ASIC和PDSP，用作前端數字訊號處理的運算（如：FIR濾波、CORDIC演算法或FFT）。乘累加運算是實現大多數DSP演算法的重要途徑，而分散式演算法則能夠大大提高乘累加運算的效能。

　　1傳統的乘累加結構FIR數字濾波器基本理論

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

　　式中，x(n)是輸入訊號，y(n)是卷積輸出，h(n)是系統的單位脈衝響應。可以看出，每次取樣y(n)需要進行L次乘法和L-1次加法操作實現乘累加之和，其中L是濾波器單位脈衝響應h(n)的'長度。可以發現，當L很大時，每計算一個點，則需要很長的延遲時間。

　　2乘累加運算的位寬分配

　　DSP演算法最主要的就是進行乘累加運算。假設取樣訊號的位寬用N來表示，則N位與N位的乘累結果需要2N位的暫存器來儲存；如果兩個運算元都是有符號數，則乘積只有2N-1個有效位，因為產生了兩個符號位。

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

　　對於無符號數：M=2N+K=2N+log2L

　　對於有符號數：M=2N=K=2N+log2L-1

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

　　得益於XilinxFPGA查詢表結構的潛能，分散式演算法在濾波器設計方面顯示出了很高的效率，自20世紀90年代初以來越來越受到人們的重要。分散式演算法是基於查詢表的一種計算方法，在利用FPGA實現數字訊號處理方面發揮著重要的作用，可以大大提高訊號的處理效率。它主要應用於數字濾波、頻率轉換等數字訊號處理的乘累加運算。

　　分散式演算法推導如下：

　　設Ak是已知常數（如濾波器係數、FFT中的正弦/餘弦基本函式等），xk(n)是變數，可以看作是n時刻的第k個取樣輸入資料，y(n)代表n時刻的系統響應。那麼它們的內積為：

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

　　式中，B為資料格式的字長,xkb是變數的二進位制位，只有“0”和“1”兩種狀態。將（2）式代入（1）式得：

　　4FPGA實現過程中查詢表的構造方法

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

　　5採用分散式演算法實現FIR數字濾波器

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

　　在進行FPGA設計時，該表以元件Component形式構建，設定為ROM結構，提供輸入定址埠table_in,輸出埠table_out。FPGA演算法的結構圖如圖2所示。

　　演算法實現中的幾個關鍵問題為：

　　（1）採用狀態機實現分散式演算法的狀態轉移

　　狀態機的實現如圖3所示，設定三個狀態s0、s1、s2。狀態s0完成資料的裝入，資料暫存器需要成對出現，一個完成資料的延遲，另一個完成資料的移位，並將狀態轉移到s1；狀態s1完成查詢表功能、資料移位和分散式演算法的乘累加運算，資料移位一個數據寬頻後將狀態轉移到s2;狀態s2完成資料的輸出，並將狀態轉移到s0。利用狀態機可以條理清楚地簡化計算過程，在演算法實現時發揮著關鍵的作用。

　　（2）系統時鐘與資料輸入時鐘的關係

　　根據上述的狀態轉移關係，可以得出：每輸入一個數據，在下一次資料輸入之前，需要在狀態s1停留一個數據寬頻（三位）的時鐘時間，在s2停留一個時鐘的資料輸出時間。也就是說，系統時鐘頻率應是資料輸入頻率的5倍，即fclkock=5fxin。

　　（3）分散式演算法中的乘累加式公推導及核心代表實現

　　設B是資料的字寬，Pn是分散式演算法第n位的結果，則有：

　　有了該關係式，就可以透過for...loop迴圈，使用一條語句完成

　　分散式乘累加演算法。具體如下：

　　fornin0toB-1loop

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

　　Endloop;

　　6演算法模擬驗證與結論

　　本文實現的FIR濾波器在Xilinx的整合開發環境ISE下利用ModelSim進行了模擬。當輸入資料為7，3，1...時，模擬輸出依次為35,29,32,16...,與乘累加方式FIR濾波演算法得出的結果完全一致。假設查詢表和PDSP的通用乘法器延時時間相同，分散式演算法的等待時間是Br,通用乘法器的等待時間是N1。可見，對於位寬較小的資料來說，分散式演算法的執行速度遠高於乘累加運算。可見，利用FPGA實現分散式計算大大提高了計算的速度，在高速訊號處理中發揮著重要作用。