FIR濾波器的FPGA實現方法

摘 要:為了給實際應用中選擇合適FIR濾波器的FPGA實現結構提供參考，首先從FIR數字濾波器的基本原理出發，分析了FIR濾波器的結構特點，然后分別介紹了基于FPGA的FIR濾波器的串行、并行、轉置型、FFT型和分布式結構型的實現方法，對于各種實現的結構做了分析、比較以及優化處理，特別是對基于FFT的FIR濾波器與傳統卷積結構進行了精確的數值計算比較，最后得出滿足于低階或高階的各種FIR濾波器實現結構的適用范圍及其優缺點，并針對實際工程應用提出了下一步需解決的問題。關鍵詞:FIR濾波器; FPGA; FFT; 分布式算法

中圖分類號:TN710-34文獻標識碼:A

文章編號:1004-373X(2010)22-0064-04

Realization Methods of FIR Filter Based on FPGA

XU Yuan-ze， DAI Li-xin， GAO Xiao-rong， WANG Li， GUO Jian-qiang

(School of Physical Science and Technology， Southwest Jiaotong University， Chengdu 610031， China)

Abstract: In order to provide reference on selecting appropriate structure of FIR filter based on FPGA， the structure characteristics of FIR filter are analyzed from the basic principle of FIR digital filter. The serial structure， parallel structure， transpose structure， FFT structure and distributed structure of realizing FIR filter on FPGA are introduced. Various realization structures are analyzed， compared and optimized， especially the FIR filter based on FFT is compared with traditional convolution structure through the precise numerical calculation. The application areas， merits and defects of the kinds of structures of FIR filter which meet the low-order or high-order are obtained， and some problem which should be resolved is given for practical engineering application.

Keywords: FIR filter; FPGA;FFT; distributed algorithm

收稿日期:2010-06-26

在數字信號處理系統中，有限脈沖響應(finite impulse response， FIR)數字濾波器是一個非常重要的基本單元。近年來，由于FPGA具有高速度、高集成度和高可靠性的特點而得到快速發展。隨著現代數字通信系統對于高精度、高處理速度的需求，越來越多的研究轉向采用FPGA來實現FIR濾波器[1-2]。而對于FIR濾波器要充分考慮其資源與運行速度的合理優化，各種不同的FIR濾波結構各具優缺點，在了解各種結構優缺點后才能更好地選擇合適結構來實現FIR濾波。

1 FIR數字濾波器

FIR數字濾波器由有限個采樣值組成，設計中在滿足幅值特性時，還能保證精確、嚴格的相位特性，因此在信號處理等領域得到廣泛的應用[3]。

對于FIR濾波器，其輸出y(n)表示為如下形式:

y(n)=x(n)h(n)=∑N-1i=0h(i)x(n-i)(1)

式中:N為濾波器的階數(或抽頭數);x(i)表示第i時刻的輸入樣本;h(i)為FIR濾波器的第i級抽頭系數。

由于FIR濾波器的沖擊響應為一個有限序列，其系統函數可表示為:

H(z)=∑N-1i=0h(i)z-i(2)

FIR濾波器的基本結構如圖1所示。FIR濾波器只在原點處存在極點，所以這使得FIR濾波器具有全局穩定性。同時FIR濾波器滿足線性相位條件，其沖擊響應序列為實數且滿足奇對稱或偶對稱條件，即:

h(n)=±h(N-n-1)(3)

圖1 FIR濾波器的結構

2 實現方法

運用FPGA來實現FIR數字濾波器的結構多種多樣，但是主要有以下幾類:串行結構、并行結構、轉置型結構、基于FFT算法結構、分布式結構。其他類型的FIR濾波器結構都可以由以上幾種結構衍生而來。

2.1 串行結構

由表達式(1)可知，FIR濾波器實質是做一個乘累加運算，其濾波器的階數決定了一次乘累加的次數，其串行結構[4]如圖2所示。

圖2 FIR濾波器的串行結構

串行結構的FIR濾波器結構簡單，硬件資源占用少，只需要復用1個乘法器和1個加法器，所以成本較低。但是，這種結構的FIR濾波器要經過多個時鐘周期才有輸出，同時，內部時鐘周期還受到乘法器運算速度的影響，所以該結構的FIR濾波器處理速度慢，只適用于濾波階數較低且處理速度要求低的系統。

2.2 并行結構

將串行結構的FIR濾波器展開就可以得到并行結構的FIR濾波器，并行FIR濾波器結構又稱作直接型FIR濾波器結構，這種結構是直接根據圖1的濾波器結構，用多個乘法器和加法器并行實現。通常考慮到其濾波器系數的對稱性，先對輸入值進行加法運算，再進行乘法運算，最后累加輸出，以此來減少乘法器的個數[5]，其結構如圖3所示。

圖3 系數對稱的FIR濾波器的并行結構

并行結構的FIR濾波器在1個周期內可以完成1次濾波，運行速度快，雖然利用濾波系數對稱性，但仍要占用大量的乘法器和加法器，特別對于濾波階數高的濾波器，其資源占用較多，如對于256階的濾波器，其需要128個乘法器來實現。為提高濾波器速度，常引入流水線結構，即在每次加法或者乘法運算后加入1個寄存器存儲數據，使得濾波器可以運行在更高的頻率上。

2.3 轉置型結構

根據轉置定理，如果將網絡中所有的支路方向倒轉，并將輸入x(n)和輸出y(n)相互交換，則其系統函數H(z)不變。通過轉置定理，將并行結構的FIR濾波器變換就可以得到轉置型FIR濾波器，其結構[6]如圖4所示。

基于并行結構的轉置型FIR濾波器實現了數據的并行輸入，在1個周期內就能完成1次濾波，并且各級結構相同，在每個階段都可以讀出數據，可以對濾波階數進行擴展或者縮減，實現任意階數的濾波器。但是由于基于的是并行結構，便有著并行結構的一些缺點，主要是對于高階的濾波器，其資源占用量是巨大的，設計成本高。雖然這樣，轉置型FIR濾波器仍是應用廣泛的一種濾波器。

圖4 并行結構FIR濾波器轉置型

2.4 基于FFT的結構

應用快速傅里葉變換(fast fourier transform， FFT)實現FIR濾波器是一種快速實現濾波算法的重要途徑。

由式(1)可知，FIR濾波器的輸出y(n)是輸入x(n)與系統沖擊響應序列h(n)的卷積，應用FFT可以快速實現卷積變換。如圖5所示，先將輸入信號x(n)通過FFT變換為它的頻譜采樣值X(k)，然后再與FIR濾波器的頻響采樣值H(k)相乘，H(k)可事先存放在存儲器中，最后再將乘積X(k)H(k)通過快速傅里葉反變換(IFFT)還原為時域序列，即得到輸出y(n)[7]。

圖5 基于FFT的FIR濾波器結構

為實現FFT，根據兩有限長序列的線性卷積可用其循環卷積代替而不發生混疊，必須選擇循環卷積長度N≥N1+N2-1，即將x(n)和h(n)補零至長度為N的序列，即:

x(n)=x(n)，0≤n≤N1-1

0，N1≤n≤N-1

h(n)=h(n)，0≤n≤N2-1

0，N2≤n≤N-1(4)

在基于FFT的FIR濾波器結構中，求X(k)，H(k)以及反傅里葉變換y(n)需要的乘法次數均為N/2log2N，而計算X(k)H(k)需要N次乘法，所以基于FFT的總乘法次數為mf=3/2Nlog2N+N。由于h(n)滿足式(3)條件，所以直接卷積所需的乘法次數為md=1/2N1N2。假設N1=N2，則比較這兩種乘法計算量有:

Km=mdmf=N1N22N(1+32log2N)=

N21(2N1-1)[2+3log2(2N1-1)](5)

表1 不同點時的運算量對比

N1=N2KmN1=N2Km

80.312564.42

160.495128.00

320.821 02414.64

421.012 04826.95

641.404 09649.96

1282.478 19293.10

從表1可知，當N1<42時，FFT法的運算量小于直接卷積的運算量，當N1=42時，FFT法的運算量與直接卷積的運算量相當，當N1>42時，FFT法的運算量大于直接卷積的運算量，并且隨著N1增加，FFT法的運算速度越來越快，特別是N1=8 192時，FFT法的運算速度與直接卷積相比快上將近100倍。

2.5 分布式結構

2.5.1 分布式算法原理

分布式算法(distributed arithmetic，DA)于1973年就由Croisier提出[8]，但是直到FPGA出現，才廣泛的被應用于FPGA中計算乘累積和。

對于有符號數x(n)可以用下式的補碼形式表示:

x(n)=-2BxB(n)+∑B-1b=0xb(n)×2b(6)

式中:xb(n)代表x(n)的第b位數字，取0或者1;xB(n)代表x(n)的最高位即符號位，當x(n)>0時，xB(n)取0，當x(n)<0時，xB(n)取1。

將式(6)代入式(1)得:

y(n)=-2B∑N-1i=0xB(n-i)h(i)+∑B-1b=02b∑N-1i=0h(i)xb(n-i)(7)

對于式(7)中的h(i)xb(n-i)代表著輸入數據x(n-i)的第i位與抽頭系數h(i)的乘積，對于FIR濾波器，其系數h(i)是常數，所以可以事先構造一個查找表。該查找表存儲所有h(i)xb(n-i)的乘積值，通過輸入(xb(N-1)，xb(N-2)，…，xb(0))對該表尋址，然后將查得的值乘上2b后移位累加便得到濾波器輸出y(n)。該查找表構造規則如表2所示。

2.5.2 基于分布式算法的FIR濾波器結構

基于分布式算法的FIR濾波器主要有3種結構類型。

(1) 第一種結構為串行分布式結構。串行分布式FIR濾波器的原理為，首先用所有N個輸入量的最低位對DA查找表進行尋址查值，得到一個部分積，將部分積右移一位即相當于除以2后放到寄存器中暫存。同時，N個輸入量的次低位開始對DA查找表進行尋址查值，得到另一個部分積，把該部分積與上一個儲存在寄存器中的值進行相加，相加后的值再右移一位放到寄存器中。以此重復循環累加，直到所有位數都尋址完成，注意最高位尋址后的部分積是相減，最后所得到的值就是所需要的結果。

表2 構造規則

xb(N-1)xb(N-2)…xb(1)xb(0)查找表中值的設置

00…00h(0)0+h(1)0+

…+h(N-2)0+

h(N-1)0=0

00…01h(0)1+h(1)0+

…+h(N-2)0+

h(N-1)0=h(0)

     

bN-1bN-2…b1b0h(0)b0+h(1)b1+

…+h(N-2)bN-1

+h(N-1)bN-1

     

11…11h(0)+h(1)+…

+h(N-2)+

h(N-1)

當N過大，即FIR濾波器的濾波階數很高時，采用一個查找表來實現將使得存儲查找表的ROM變得十分龐大。為此可采用部分表結構，即將查找表劃分為多個部分[9]，N個輸入量的同一位對應不同的部分表尋址。圖6所示即為基于4輸入部分表結構的串行DA結構。

圖6 串行分布式結構

(2) 第二種結構為并行分布式結構。并行分布式結構就是將N個輸入量的不同位進行同時查表，而相同位送入同一個ROM尋址，不同位有不同的ROM。其結構如圖7所示[10]。

第三種結構為串并結合分布式結構。它是一種折中方案，既要求速度不太高又要求資源占用少。對于串行分布式算法，是一次一位(one bit-at-a-time，1BAAT)查找表，而并行分布式算法是一次B位(B bits-at-a-time)。所以串并結合分布式算法采用一次多位，如2BAAT，3BAAT。圖8所示為4BAAT查找表結構圖。

圖7 并行分布式結構

圖8 串并結合的分布式結構

圖8中位數B是4的倍數，SRL為移位寄存器。SRL中第1行從右邊數第1列為數據的0位，第2列為數據的1位，第3列為數據的2位，第4列為數據的3位。類似地，第2行右數第1列為數據的4位，第2列為數據的5位，第3列為數據的6位，第4列為數據的7位。以后各行按相似的數位順序排列。在第一個時鐘周期，數據的0，4，…，B-4位同時進入查找表ROM中，查出所要的數據，第二個時鐘周期，1，5，…，B-3位同時進入ROM中，查出所要的數據，所查得的數據傳遞給下一級累加器進行累加，這樣依次對剩下的各數據位進行同樣的操作[4]。由于每個塊之間相差4位，即16倍，為了對應位相加，所以乘16。

FIR濾波器的分布式算法結構比單獨用乘法器實現的速度快，特別是濾波階數越高，其優勢更加明顯。分布式結構中，串行結構是1次查詢1位，所以對B位的數據在不算上移位寄存等的時間，完成1次濾波需要B個時鐘周期;而并行結構只需要1個時鐘周期便完成濾波，所以并行結構是速度最優的結構，但是并行結構需要B個DA查找表，需要大量的ROM來儲存，加大了硬件資源的消耗，特別是階數越高，硬件規模將十分膨大;串并結構綜合兩種結構優勢，實現在速度和規模上的協調。實際應用中，需根據系統的要求來選擇合適的結構。

3 結 語

本文定性地分析了各種FIR濾波器的FPGA實現方法。對于低階的FIR濾波器可采用串行結構、并行結構以及轉置型結構來實現，而并行結構和轉置型結構的FIR濾波器以犧牲資源損耗來實現了速度上優勢;對于高階的FIR濾波器，基于乘法器結構的串行結構、并行結構及轉置型結構在速度上難以達到高速處理的要求，而分布式算法將乘法轉換為查表和累加的結構，使得分布式結構的FIR濾波器在速度上得到了提高，但三種不同形式的分布式結構要在綜合考慮資源以及速度的基礎上進行合理選擇;同樣采用FFT實現的FIR濾波器以減少運算量來獲得了速度上的提高，特別是濾波階數越高其速度提升越明顯。

現代工程技術領域對濾波系統的帶寬、高速、信號的實時性處理等方面要求越來越高，在運用FPGA來實現FIR濾波中，基于乘法器結構的FIR濾波器無法滿足以上要求，而分布式結構的FIR濾波器巧妙地運用ROM查找表來實現固定系數的乘累加運算，避免了乘法運算，并且在隨后的每級加法運算中引入流水線結構，提高了速度。因此采用分布式算法實現FIR濾波器是目前研究的熱點，同時無論哪種分布式算法都要使用ROM來做查找表，但是隨著濾波階數的增加，ROM的數量將會增加，在進一步提高速度的情況下如何減少ROM的數量是今后亟待解決的問題。

參考文獻

[1]KUMAR Pramod Meher， CHANDRASEKARAN Shrutisagar， AMIRA Abbes. FPGA realization of FIR filters by efficient and flexible systolization using distributed arithmetic [J]. IEEE Transactions on Signal Processing， 2008， 56(7): 3009-3017.

[2]劉在爽，盧瑩瑩.高階FIR濾波器面向 FPGA的多種實現方法[J].中國有線電視，2008(2):164-168.

[3]黃曉紅，蔡江利.基于FPGA的改進型FIR濾波器的實現[J].電子技術應用，2009(5):32-38.

[4]李文剛.基于FPGA的高速高階FIR濾波器設計[D].成都:電子科技大學，2005.

[5]田耘，徐文波，張延偉，等.無線通信FPGA設計[M].北京:電子工業出版社，2008.

[6]李彬.FIR數字濾波器的FPGA實現技術研究[D].成都:西南交通大學，2007.

[7]張燕君，王海寶，陳澤貴，等.基于FPGA的FIR濾波器FFT與DA算法的比較[J].電子測量技術，2008，31(10):173-176.

[8]BAESE Uwe Meyer. Digital signal processing with filed programmable gate arrays [M].北京:清華大學出版社，2003.

[9]戴敬，王超.基于FPGA多級分布式算法的FIR數字濾波器的設計[J].沈陽建筑大學學報，2010，26(1):196-200.

[10]夏瀑.基于分布式算法的FIR濾波器設計及FPGA實現[D].大連:大連海事大學，2008.