一種在FPGA上實(shí)現(xiàn)的FIR濾波器的資源優(yōu)化算法

曲仕茹，彭紀(jì)昌

（西北工業(yè)大學(xué) 自動(dòng)化學(xué)院，陜西 西安 710072）

隨著數(shù)字化通信技術(shù)的快速發(fā)展，高質(zhì)量的信號(hào)處理對(duì)濾波器的性能和資源占有量提出了更高的要求。數(shù)字濾波器是數(shù)字信號(hào)處理中的一個(gè)重要模塊，F(xiàn)IR濾波器作為最常用的濾波器廣泛用在實(shí)時(shí)信號(hào)的處理中。FIR濾波器分為軟件和硬件兩種實(shí)現(xiàn)方式。軟件采用計(jì)算機(jī)的儲(chǔ)存器計(jì)算器把濾波器的運(yùn)算編成程序通過(guò)計(jì)算機(jī)來(lái)執(zhí)行。硬件一般采用時(shí)域卷積的方法實(shí)現(xiàn)[1]。

目前較為常用的FIR濾波器結(jié)構(gòu)主要有，直接結(jié)構(gòu)、轉(zhuǎn)置型結(jié)構(gòu)和分布式算法的結(jié)構(gòu)。直接結(jié)構(gòu)的濾波器設(shè)計(jì)方法是將濾波運(yùn)算轉(zhuǎn)化為乘積的累加；轉(zhuǎn)置結(jié)構(gòu)的濾波器設(shè)計(jì)方法與直接結(jié)構(gòu)的濾波器相比，采用簡(jiǎn)化加法圖（RAG）和流水線技術(shù)；分布式算法（DA）是一種重要的FPGA技術(shù)，廣泛地應(yīng)用在計(jì)算乘積和的過(guò)程中。直接結(jié)構(gòu)的設(shè)計(jì)方法沒(méi)有考慮到系數(shù)之間的關(guān)系，芯片面積較大，計(jì)算速度不高。采用RAG算法的流水線結(jié)構(gòu)的濾波器較采用DA結(jié)構(gòu)的濾波器在邏輯資源消耗上有一定減少，并節(jié)約的芯片的尺寸，不過(guò)在計(jì)算速度上稍慢于DA結(jié)構(gòu)的濾波器，但是其消耗邏輯資源總量/最高速度明顯要優(yōu)于DA結(jié)構(gòu)[2]。因此基于RAG算法結(jié)構(gòu)的濾波器設(shè)計(jì)能較好的滿足設(shè)計(jì)要求。

1 FIR濾波器原理和結(jié)構(gòu)

數(shù)字濾波器通常用于修正或改變時(shí)域或頻域中信號(hào)的屬性。最為普通的數(shù)字濾波器就是線性時(shí)不變（Linear Time-Invariant，LTI）濾波器。LTI數(shù)字濾波器通常分成有限脈沖響應(yīng) （Finite pulse Response，F(xiàn)IR）和 無(wú) 線 脈 沖 響 應(yīng) （Infinite Impulse Response，IIR）兩大類(lèi)。帶有常系數(shù)的FIR濾波器是一種LTI數(shù)字濾波器。L階的FIR輸出對(duì)應(yīng)于輸入時(shí)間序列x[n]的關(guān)系由一種有限卷積和的形式給出：

其中f[0]≠0一直到f[L-1]≠0均是濾波器的L階的系數(shù)，同時(shí)它們也對(duì)應(yīng)于FIR的脈沖響應(yīng)。

FIR濾波器由一個(gè)“抽頭延遲線”加法器和乘法器的集合構(gòu)成，給每個(gè)乘法器提供的其中一個(gè)操作數(shù)就是一個(gè)FIR系數(shù)。FIR濾波器從結(jié)構(gòu)上可以分為直接型和轉(zhuǎn)置型。

圖1 直接型結(jié)構(gòu)Fig.1 Direct structure filter

圖2 轉(zhuǎn)置型結(jié)構(gòu)Fig.2 Transposition structure filter

由于FIR濾波器總是線性相位的，其單位脈沖響應(yīng)是序列是 f（n），且滿足 f（n）=± f（L-1-n）。 線性相位 FIR 的固有對(duì)稱(chēng)屬性可以降低所需要的乘法器數(shù)量，如圖3所示?？梢钥吹健皩?duì)稱(chēng)”體系結(jié)構(gòu)在每個(gè)濾波器周期正好是圖1給出的直接體系結(jié)構(gòu)的一半（L比L/2），而加法器數(shù)量保持不變（L-1）。

圖3 線性相位結(jié)構(gòu)Fig.3 Linear phase structure filter

FIR濾波的過(guò)程就是一個(gè)信號(hào)逐級(jí)延遲的過(guò)程，將各級(jí)延遲的輸出信號(hào)加權(quán)并累加既得FIR濾波器的輸出，這其中最重要的運(yùn)算就是乘累加運(yùn)算。FIR濾波器每完成一次濾波需要進(jìn)行L次的乘法運(yùn)算和L-1次的加法運(yùn)算，F(xiàn)IR濾波器的運(yùn)算量取決于L的大小[3-4]。

2 基于DA算法的FIR濾波器原理

當(dāng)濾波器的階數(shù)較高時(shí)乘累加式結(jié)構(gòu)的濾波器已經(jīng)不能滿足實(shí)時(shí)性的要求并且會(huì)消耗過(guò)高的邏輯資源。這是就需要使用基于分布式算法DA（Distributed Arithmetic）的濾波器結(jié)構(gòu)。分布式算法最初是在1973年Croisier的論文中被提出來(lái)的，后又經(jīng)Peled等人的推廣演繹，但直到FPGA出現(xiàn)并迅速發(fā)展時(shí)，才在應(yīng)用領(lǐng)域得到廣泛應(yīng)用[5]。

一個(gè)L階FIR濾波器表達(dá)式如下：

其中，y（n）表示濾波器的輸出，x（n）表示濾波器的輸入，f（n）表示濾波器的系數(shù)，L表示濾波器的階數(shù)。在FPGA中，數(shù)據(jù)采用二進(jìn)制的補(bǔ)碼表示，所以有符號(hào)的輸入信號(hào)x（n）表達(dá)式如下：

其中，xb[n]表示 x[n]的第 b位，而 x[n]也就是 x的第 n次采樣，而輸出y的表達(dá)式為：

圖4 基于DA算法的濾波器結(jié)構(gòu)Fig.4 DA structure filter

3 改進(jìn)的資源優(yōu)化算法FPGA上的實(shí)現(xiàn)

基于DA算法的FIR濾波器可以提高運(yùn)算速度，但是同時(shí)會(huì)消耗更多的邏輯資源。簡(jiǎn)化加法器圖 （Reduced Adder Graph，RAG）算法在降低濾波器的邏輯資源的同時(shí)也能提高運(yùn)算速度。RGA算法在硬件上只需加法和移位方法實(shí)現(xiàn)乘法，并利用各系數(shù)之間的相關(guān)性，最大程度的減少加法器個(gè)數(shù)和加法次數(shù)，因?yàn)橐莆徊幌馁Y源，所以整個(gè)設(shè)計(jì)的硬件開(kāi)銷(xiāo)只是加法器的個(gè)數(shù)[6]。

如系數(shù)13和45，根據(jù)RAG算法可以表示為5圖。需要3個(gè)加法器和3次移位就可以計(jì)算出常系數(shù)13和45的乘法。

圖5 使用RAG算法實(shí)現(xiàn)常系數(shù)Fig.5 Use RAG algorithm generation constant coefficient

RAG算法的基本步驟：

1）將輸入集合中的所有系數(shù)簡(jiǎn)化成正數(shù)

2）查表計(jì)算每個(gè)系數(shù)的單系數(shù)加法器成本

3）刪除系數(shù)集合中所有2的冪和重復(fù)的系數(shù)

4）找出實(shí)現(xiàn)只需要一個(gè)加法器的系數(shù)

5）檢查是否有一個(gè)系數(shù)可以用一個(gè)加法器和以實(shí)現(xiàn)的系數(shù)實(shí)現(xiàn)

6）重復(fù)步驟5，直到?jīng)]有系數(shù)添加到圖集中為止

7）使用已有的或新的非輸出單元實(shí)現(xiàn)需要兩個(gè)加法器的小系數(shù)

8）重復(fù)步驟5直到?jīng)]有新的系數(shù)加入加法圖

9）使用已有的或者新的非輸出單元實(shí)現(xiàn)需要三個(gè)加法器的小的系數(shù)

10）返回步驟5，直到所有系數(shù)都已合成好[7-10]

FIR濾波器的設(shè)計(jì)利用Matlab中的FDA Tool工具，設(shè)計(jì)一個(gè)16階，F(xiàn)s=48 kHz，F(xiàn)c=10.8 kHz的FIR濾波器。FPGA實(shí)現(xiàn)中采用經(jīng)量化取整的濾 波系數(shù) {-9，3，14，1，-22，-12，46，106，106，46，-12，-22 ，1，14，3，-9}。

圖6 FIR濾波器的幅值和相位響應(yīng)Fig.6 Amplitude and phase response of FIR filter

由于FIR濾波器的系數(shù)具有對(duì)稱(chēng)性，這里只討論C0到C7的RAG實(shí)現(xiàn)過(guò)程。該系數(shù)實(shí)現(xiàn)所有的濾波器系數(shù)只需要6個(gè)加法器以及移位運(yùn)算，節(jié)省了大量的邏輯資源[7]。

如圖7所示RAG結(jié)構(gòu)的濾波器僅需要6個(gè)加法器以及9次移位操作就可以實(shí)現(xiàn)所有的濾波器系數(shù)。節(jié)省了大量的邏輯資源。

圖7 濾波器系數(shù)的RAG實(shí)現(xiàn)Fig.7 Realization of the filter coefficients by RAG algorithm

FIR濾波器的FPGA實(shí)現(xiàn)與仿真，在Quartus II平臺(tái)中進(jìn)行試驗(yàn)，選用 Cyclone II系列的EP2C35F672C6器件，用VerilogHDL語(yǔ)言設(shè)計(jì)RAG算法結(jié)構(gòu)并用SignalTap II對(duì)其進(jìn)行仿真。仿真結(jié)果如圖8所示。clk為時(shí)鐘信號(hào)，d_in為輸入信號(hào)，dout_ly為理論輸出值，dout為濾波器輸出。

圖8 濾波器仿真波形Fig.8 Simulation waveforms of Filter

可以從仿真結(jié)果看出濾波器的濾波效果還是非常理想的并且濾波的速度也相對(duì)較快。工業(yè)界廣泛使用的DSP Builder生成的分布式算法濾波器性能作為濾波器的參考標(biāo)準(zhǔn)[11-12]。本文采用RGA算法實(shí)現(xiàn)的濾波器與同等規(guī)模的DSP Builder生成的濾波器的IP核在相同的FPGA平臺(tái)上實(shí)現(xiàn)后比較的到的結(jié)果如表1所示。可以看到基于RAG算法的濾波器在邏輯資源節(jié)省上有了很大的提升。

表1 濾波器占用資源對(duì)比Tab.1 Filter resource comparison

4 結(jié) 論

本文通過(guò)使用RAG算法設(shè)計(jì)了線性相位的低通濾波器。通過(guò)仿真驗(yàn)證了該濾波器的可行性，滿足設(shè)計(jì)要求?；谄浣Y(jié)構(gòu)的特征，在硬件實(shí)現(xiàn)上采用了轉(zhuǎn)置結(jié)構(gòu)設(shè)計(jì)該濾波器，使用RAG算法實(shí)現(xiàn)所有系數(shù)乘積綜合，最大程度的減少加法器的數(shù)量，使用移位運(yùn)算代替乘法器結(jié)構(gòu)，并使用流水線的技術(shù)提高運(yùn)行速度。仿真實(shí)驗(yàn)表明基于RAG算法了濾波器比DA算法要節(jié)省大量的邏輯資源，滿足高速處理要求。以設(shè)計(jì)一個(gè)16階濾波器為例，在Altera公司QuartusⅡ的環(huán)境下采用VerilogHDL硬件描述語(yǔ)言進(jìn)行設(shè)計(jì)實(shí)現(xiàn)并采用SignalTap II進(jìn)行仿真驗(yàn)證，在此基礎(chǔ)上進(jìn)行性能分析，實(shí)驗(yàn)結(jié)果證實(shí)了此種設(shè)計(jì)方法在解決速度和面積矛盾方面的優(yōu)勢(shì)。

[1]U.Meyer-Baese Digital Signal Processing with Field Programmable Gate Arrays[M].3rd ed.New York:Springer Berlin Heidelberg，2007.

[2]Tan L，Jiang J.Adaptive volterra filters for active control of nonlinear noise processes[J].IEEE Transactions on Signal Processing，2001，49（8）:1667-1676.

[3]Mirzaei S，Hosangadi A，Kastner R.FPGA implementation of high speed FIR filters using add and shift method[C].International Conference on Computer Design.Las Vegas，Nevada， USA，2006.

[4]DENG Tian-Bo.Design and parallel implementation of FIR digital filters with simultaneously variable magnitude and non-integer phase-delay[J].IEEE Analog and Digital Signal Processing，2003，50（40）:243-250.

[5]Zhu W，Zhang G M，Zhang Z M.Design of FIR filter based on distributed algorithm with parallel structure[J].Journal of Electronic Measurement and Instrument，2007（21）:87-92.

[6]李瑩，路衛(wèi)軍，于敦山，等.一種在FPGA上實(shí)現(xiàn)FIR數(shù)字濾波器的資源優(yōu)化算法[J].北京大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，45（2）:222-226.LI Ying，LU Wei-jun.A resource optimizing algorithm in FPGA based high speed FIR digital filters[J].Acta Scientiarum Naturalium Universitatis Pekinensis，2009，45（2）:222-226.

[7]夏宇聞.Verilog數(shù)字系統(tǒng)設(shè)計(jì)教程[M].北京:北京航空航天大學(xué)出版社，2008.

[8]XIE Jia-feng，HE Jian-jun，TAN Guan-zheng.FPGA realization of FIR filters for high-speed and medium-speed by using modifieddistributedarithmeticarchitectures[J].Microelectronics Journal，2010（41）：365-370.

[9]MEYER U.Digital signal processing with field programmable gate arrays[M].3rd ed.New York:Springer Berlin Heidelberg，2007.

[10]HAN Jeong-Ho，PARK In-Cheol.Digital Filter Synthesis Considering Multiple Adder Graphs for a Coefficient[C]//IEEE Computer Design，ICCD 2008:315-320.

[11]吳偉，唐斌.可變帶寬FIR數(shù)字濾波器的高效加權(quán)最小二乘設(shè)計(jì)及實(shí)現(xiàn)[J].儀器儀表學(xué)報(bào)，2008，29（3）:550-555.WU Wei，TANG Bin.Efficient weighted-least-square design and realization of FIR digital filters with variable bandwidth[J].ChineseJournalofScientificInstrument，2008，29（3）:550-555.

[12]Wirthlin M J.Constant coefficient multiplication using look-up tables[J].Journal of VLSI Signal Processing，2004，36（1）:7-15.