利用利用FPGA乘累加快速算法實現(xiàn)高速FIR數字濾波器的設計

1 引 言

目前FIR濾波器的實現(xiàn)方法主要有3種：利用單片通用數字濾波器集成電路、DSP器件和可編程邏輯器件實現(xiàn)。單片通用數字濾波器使用方便，但由于字長和階數的規(guī)格較少，不能完全滿足實際需要。使用DSP器件實現(xiàn)雖然簡單，但由于程序順序執(zhí)行，執(zhí)行速度必然不快。

FPGA有著規(guī)整的內部邏輯陣列和豐富的連線資源，特別適合于數字信號處理任務，相對于串行運算為主導的通用DSP芯片來說，其并行性和可擴展性更好。但長期以來，F(xiàn)PGA一直被用于系統(tǒng)邏輯或時序控制上，很少有信號處理方面的應用，其原因主要是因為在FPGA中缺乏實現(xiàn)乘法運算的有效結構。本文利用FPGA乘累加的快速算法，可以設計出高速的FIR數字濾波器，使FPGA在數字信號處理方面有了長足的發(fā)展。

2 Matlab設計濾波器參數

利用Matlab為設計FIR濾波器提供的工具箱，選擇濾波器類型為低通FIR，設計方法為窗口法，階數為16，窗口類型為Hamming，Beta為0.5，F(xiàn)s為8.6 kHz，F(xiàn)C為3.4 kHz，導出的濾波器系數如下：

3 快速FIR濾波器算法的基本原理

（1） 分布式算法

分布式算法在完成乘加功能時是通過將各輸入數據每一對應位產生的部分積預先相加形成相應的部分積，然后再對各部分積進行累加得到最終結果。

對于一個N（N為偶數）階線性相位FIR數字濾波器，輸出可由式（1）表示：

（2） 乘法器設計

高性能乘法器是實現(xiàn)高性能的FIR運算的關鍵，分析乘法器的運算過程，可以分解為部分積的產生和部分積的相加兩個步驟。部分積的產生非常簡單，實現(xiàn)速度較快，而部分積相加的過程是多個二進制數相加的加法問題，實現(xiàn)速度通常較慢。解決乘法器速度問題，需要分別從這兩個方面入手，減小部分積的個數，提高部分積相加運算的速度。

3.1 Booth算法

Booth算法針對二進制補碼表示的符號數之間的相乘，即可以同時處理二進制正數／負數的乘法運算。Booth算法乘法器可以減少乘法運算部分積個數，提高乘法運算的速度。

下面討論一個M b×N b乘法器基本單元的設計。設乘數為A，為M比特符號數，2的補碼表示，相應各比特位的值為ai（i=0，1，…，M-2，M-1），用比特串可表示為：

因此，應用改進Booth算法的乘法器運算過程仍然包括Booth編碼過程，即部分積產生過程和部分積相加過程。所不同的是，其產生的部分積個數減少到原來的一半。

3.2 Wallace樹加法

在采用改進Booth算法將部分積數目減少為原來的一半之后，乘法運算的主要問題就是處理多個多比特二進制操作數相加的問題。最直觀的算法是將多個部分積逐一累加，但效率很低，運算時延巨大。

Wallace在1964年提出采用樹形結構減少多個數累加次數的方法，稱為Wallace樹結構加法器。Wallace樹充分利用全加器3-2壓縮的特性，隨時將可利用的所有輸入和中間結果及時并行計算，因而可以將N個部分積的累加次數從N-1次減少到log2N次，大大節(jié)省了計算時延。如圖2所示為Wallace樹結構與CSA結構的對照，其結構的關鍵特征在于利用不規(guī)則的樹形結構對所有準備好輸人數據的運算及時并行處理。

Wallace樹結構一般用于設計高速乘法器，其顯著優(yōu)點是速度快，尤其對處理多個數相加的情況具有相當的優(yōu)越性，缺點是其邏輯結構形式不規(guī)整，在VLSI設計中對布局布線的影響較大。

3.3 進位的快速傳遞

考慮到提高兩個多比特操作數相加運算的速度，關鍵在于解決進位傳遞時延較大的問題。采用以犧牲硬件資源面積換取速度的方式，以獨立的邏輯結構單獨計算各個加法位需要的進位輸入以及產生的進位輸出，提高進位傳遞的速度，從而提高加法運算速度。

3.3.1 四位超前進位加法器的設計

兩個加數分別為A3A2A1A0，B3B2BB1B0，C-1為低位進位。令兩個輔助變量分別為G3G2G1G0和P3P2P1P0：Gi=Ai&Bi，Pi=Ai+Bi。G和P可用與門、或門實現(xiàn)。

一位全加器的邏輯表達式可化為：

由式（7）可以看出每一個進位的計算都直接依賴于整個加法器的最初輸入，而不需要等待相鄰低位的進位傳遞。理論上，每一個進位的計算都只需要3個門延遲時間，即同時產生G［ i］，P［ i］的與門以及或門，輸入為G［ i］，P［ i］，C-1的與門，以及最終的或門。同樣道理，理論上最終結果sum的得到只需要5個門延遲時間。

實際上，當加數位數較大時，輸入需要驅動的門數較多，其VLSI實現(xiàn)的輸出時延增加很多，考慮互聯(lián)線延時的情況將會更加糟糕。因此，通常在芯片實現(xiàn)中設計位數較少的超前進位加法器結構，而后以此為基本結構構造位數較大的加法器。

3.3.2 進位選擇加法器結構

實際上，超前進位加法器只是提高了進位傳遞的速度，其計算過程與行波進位加法器同樣需要等待進位傳遞的完成。借鑒并行計算的思想，人們提出了進位選擇加法器結構，其算法的實質是增加硬件面積換取速度性能的提高。利用二進制加法的特點，進位或者為邏輯1，或者為邏輯0，二者必居其一。將進位鏈較長的加法器分為M塊分別進行加法計算，對除去包含最低位計算的M-1塊加法結構復制兩份，其進位輸入分別預定為邏輯1和邏輯0，于是M塊加法器可以同時并行進行各自的加法運算，然后根據各自相鄰低位加法運算結果產生的進位輸出，選擇正確的加法結果輸出。

4 基于FPGA設計FIR數字濾波器

clk2為FIR數字濾波器的工作時鐘，clk2頻率遠大于clk1頻率。其工作過程：clk1時鐘的上升沿啟動一次計算過程，控制器輸出reset信號使觸發(fā)器1清0；其后每個clk2周期計算一個h（i）［x（i）+x（N-i-1）］并進行累加，共需N／2個clk2周期完成計算，完成計算后控制器輸出OE信號將結果輸出。

（1） 對沖激響應系數h的處理：由Matlab設計FIR濾波器系數是一系列的浮點數，而FPGA不支持浮點數的運算，因此浮點數需轉換成定點數，設計可采用Q值量化法，把系數擴大了27=128倍，然后轉化為8位二進制數補碼。最終結果再右移7位就可等到真正結果。

（2） 本設計對于有符號數采用補碼表示的方法，在設計中多次出現(xiàn)加法運算，可能會產生溢出，所以應進行符號位擴展。將符號位擴展到輸出統(tǒng)一的最高位，才能夠保證計算結果的正確性。

擴展方法為：

P9P8P7P6P5P4P3P2P1P0

=P9P9P9P9P9P8P7P6P5P4P3P2P1P0

其中：P9為補碼的符號位。

（3） Booth編碼處理由于存在求“-x”的運算，需進行求反加1。如果每1次調用Booth編碼都進行加1運算，不僅使資源大大浪費，而且由于位數較長，也會大大影響乘法器的速度。而本設計將加1放在Wallace樹中計算，盡管多了1級Wallace樹，但速度和資源上都大大提高了。

（4） 由于FIR是線性相位，h（i）=h（15-i），可以將乘法運算由16次減少到8次；再通過對h（i）進行Booth編碼可以將部分積減少到4個；最終利用Wallace樹以及超快速加法器將4個部分積的相加，得到8*8乘法器的結果。由于將Booth編碼中的加1放在Wallace樹中，經過分析需要3級Wallace樹。

5 FIR濾波器的頻率特性分析

利用Matlab中rand（）和round（）函數產生-128～128之間中100個整隨機數。

再將100個數通過FIR濾波器，求輸出幅頻響應

比較輸入x與輸出y的幅頻特性，可以看出FIR濾波器為低通濾波，指標符合設計要求。

6 用ISE綜合分析FIR濾波器的性能分析

分析設計框圖可以看出，占用時間最長的路徑為8位加法器——乘法器——累加器，這是影響工作頻率最主要的部分。設計中采用流水線技術，在這條路徑中增加寄存器，將最長路徑拆分成較短路徑，可以取得比較好的效果，提高系統(tǒng)的工作頻率。

FIR濾波器的最高工作頻率如下：

可以看出最高工作頻率可以達到154.84 MHz，實現(xiàn)了高速FIR數字濾波器的設計。