基于改進的DA算法實現(xiàn)高階FIR濾波器

王哲+周前能

摘 要： 介紹了幾種應(yīng)用于高階FIR濾波器的算法，著重介紹DA算法，該算法主要基于LUT形式，從根本上減少了乘法器資源的消耗，提高了系統(tǒng)的實時性。并以此為基礎(chǔ)介紹了幾種改進的算法，分別是基于LUT分解、基于OBC編碼以及基于雙向選擇器的DA改進算法，這些算法都從不同程度上降低了資源的使用，提高了信號處理速度，降低了系統(tǒng)復(fù)雜性。最后，對FIR濾波器的改進算法進行了全面的分析比較和仿真，仿真結(jié)果均正確并且符合設(shè)計要求。

關(guān)鍵字： DA算法； FIR濾波器； LUT分解； OBC編碼； 雙向選擇器

中圖分類號： TN911?34 文獻標識碼： A 文章編號： 1004?373X（2014）04?0008?05

Realization of high?order FIR filter based on improved DA algorithm

WANG Zhe， ZHOU Qian?neng

（College of Photoelectric engineering， Chongqing University of Posts and Telecommunications， Chongqing 400065， China）

Abstract： Several kinds of algorithms applied to high?order FIR filter are introduced， among which the DA algorithm is emphatically introduced. The algorithm mainly based on the form of LUT reduced the resource consumption of multiplier radically and improved the real?time performance of the system. On this basis， several kinds of improved algorithms are presented in this paper. They are the improved DA algorithms， respectively based on LUT decomposition， OBC coding and two?way selector. They improved the speed of signal processing and reduced the system complexity. The comprehensive analysis， comparison and simulation for the improved DA algorithms applied to FIR filter are carried out. The results of simulation are correct and meet the design requirements.

Keywords： DA algorithm； FIR filter； LUT decomposition； OBC coding； two?way selector

數(shù)字濾波器是很多數(shù)字信號處理系統(tǒng)的基本單元，它們廣泛的應(yīng)用于通信、信號處理、圖像處理、模式識別等很多領(lǐng)域。目前有多種實現(xiàn)FIR濾波器的方法，諸如使用DSP芯片、專用集成電路ASIC以及FPGA等，利用DSP來實現(xiàn)將會受限于運行速度以及較漫長的開發(fā)時間，ASIC將會受限于開發(fā)周期、成本以及通用性等問題，而FPGA的實現(xiàn)將會平衡這些因素，由于其開發(fā)周期短、實現(xiàn)方式容易、通用性強等特點，在很多領(lǐng)域都有著廣泛的應(yīng)用，并且發(fā)展?jié)摿薮蟆?/p>

FIR濾波器的主要的設(shè)計方法就是利用乘累加來實現(xiàn)。這個方法的實現(xiàn)主要有兩種方式，一種是直接乘加的結(jié)構(gòu)，N階的FIR要完成N次乘法和N-1次加法操作，這種結(jié)構(gòu)將會消耗大量的硬件資源和面積；另一種則是利用DA算法來實現(xiàn)，它將乘累加的計算形式轉(zhuǎn)換為對查找表的尋址以及移位求和來實現(xiàn)，這種解決辦法基于FPGA的查找表結(jié)構(gòu)并且可以顯著提高系統(tǒng)的運行效率，但是在減少乘法器使用的同時會增加大量LUT的使用，同樣是一種面積換速度思想的體現(xiàn)[1]。

為了達到更高的運行速度，優(yōu)化系統(tǒng)資源消耗，目前對FIR濾波器算法以及DA算法的改進有很多方法，包括部分串行結(jié)構(gòu)、分割查找表、OBC編碼、多路選擇分解、CSD編碼等。此外對于FIR濾波的運行效率和資源優(yōu)化還可以通過使用流水線、狀態(tài)控制機等方式來滿足。本文分別介紹了DA算法、基于查找表分割的DA算法、基于OBC編碼的DA算法、基于多路選擇的分解算法，并在ISE中進行Verilog硬件代碼的編寫，并編寫Testbench進行波形仿真，最后與傳統(tǒng)的FIR濾波器算法進行了性能、資源以及實時性處理的比較和分析。

1 DA算法簡介

分布式算法是一種應(yīng)用廣泛的FIR濾波器設(shè)計方法，主要基于查找表尋址來實現(xiàn)乘累加。分布式算法在完成乘加功能時是通過將各輸入數(shù)據(jù)每一比特位對LUT進行尋址，LUT本質(zhì)上就是一個RAM。目前FPGA中多使用4輸入的LUT，即為四位地址線，所以每一個LUT可以看成一個有4位地址線的16×1的RAM。如表1所示，當用戶通過原理圖或HDL語言描述了一個邏輯電路以后，并計算好邏輯電路所有可能的結(jié)果，并把結(jié)果事先寫入RAM，這樣，每輸入一個信號進行邏輯運算就等于輸入一個地址進行查表，找出地址對應(yīng)的內(nèi)容，然后輸出即可。

圖1 實際邏輯與LUT實現(xiàn)方式對比

因此，LUT中需要預(yù)先存儲FIR所有系數(shù)的所有可能組合之和，單個LUT的結(jié)構(gòu)則需要構(gòu)建[2N，]N為系數(shù)個數(shù)。每一次輸入數(shù)據(jù)得到部分積后，再對各部分積進行累加得到最終結(jié)果。設(shè)[wi]是濾波器設(shè)計的系數(shù)，[xi（n）]是變量，可以看作是n時刻的第i個采樣輸入數(shù)據(jù)，y（n）代表n時刻的系統(tǒng)響應(yīng)。那么它們的內(nèi)積為：

[y（n）=i=0N-1wixi（n）] （1）

用二進制補碼來表示輸入數(shù)據(jù)[xi（n）]：

[xi=-xi，m-1+j=0m-1xi，m-1-j2-j] （2）

式中[xi，m-1]是[xi]的最高位，也就是符號位。將式（2）代入式（1）可得：

[y（n）=i=0N-1wi[-xi，m-1+j=0m-1xi，m-1-j2-j] =i=0N-1j=0m-1wixi，m-1-j2-j-i=0N-1wixi，m-1] （3）

因為[xi，m-1-j]的值只有兩種可能性：1和0，所以[i=0N-1wixi，m-1-j]的計算結(jié)果有[2N]個不同的結(jié)果，單個LUT存儲下所有[i=0N-1wixi，m-1-j]的可能結(jié)果，并且利用來自位移存儲器[xi，m-1-j]作為LUT的地址信號從LUT中取出每一個比特位與系數(shù)的乘積。因此y（n）的值可以通過不斷的移位和累加操作得到[2]。四個系數(shù)的基于LUT的DA算法結(jié)構(gòu)如圖2所示。

圖2 DA算法基本結(jié)構(gòu)

以上簡要介紹了DA算法的基本原理，就是實現(xiàn)方式而言，分布式算法又可以分為并行方式、串行方式和串并結(jié)合的方式。并行方式首先要建立一個n×m的輸入緩沖陣列，將數(shù)據(jù)讀入，并對其進行排列，用所有n個輸入數(shù)據(jù)的相同位對分布式查找表進行尋址，全并行方式實現(xiàn)需要消耗大量的分布式查找表，將會消耗很多的系統(tǒng)資源，但是可以很容易采用流水線方式來實現(xiàn)，所以可以得到很高的運算速度，它是一種資源換取效率的方法[3]。如圖3所示。

圖3 并行方式實現(xiàn)DA算法

串行方式只使用一個分布式查找表，先從最低位開始處理，用所有的n個輸入變量的最低位對分布式查找表進行尋址，得到部分和后右移一位，放入寄存器中，與此同時，n個輸入變量的次低位已經(jīng)開始對分布式查找表進行二次尋址，等得到另一個部分和，并將其同樣右移一位，與前一個部分和相加，重復(fù)以上步驟，直至得到最終的和，并用前面累加的結(jié)果減去符號位的部分和。與全并行方式相比，速度降低了很多，但是消耗的系統(tǒng)資源較少，設(shè)計思想簡單，是一種效率換資源的方法。圖2所示的即為串行形式。串并結(jié)合的方式則是對前面兩種方式的平衡。

2 DA算法的改進

當濾波器階數(shù)較小的時候，DA算法的查找表規(guī)模對資源的消耗可以接受，但是隨著濾波器階數(shù)的增加，查找表的規(guī)模會隨著濾波器階數(shù)的增大而呈指數(shù)增長，如果還是使用傳統(tǒng)的DA算法來實現(xiàn)FIR，其資源將會消耗巨大，所以在高階濾波器的設(shè)計中必須對DA算法進行改進。

為了縮小LUT，對LUT的地址線的數(shù)量進行分割，可以將規(guī)模較大的LUT分割為一些規(guī)模較小的LUT，由于FIR濾波器是線性濾波器，因此低階濾波器的輸出可以相加，并且由此實現(xiàn)一個高階濾波器的輸出。如果再額外的加上流水線寄存器，這一結(jié)構(gòu)的改變不僅不會降低運行速度，而且可以極大的減小設(shè)計規(guī)模。

如圖4所示，實現(xiàn)一個4N的DA設(shè)計需要3個輔助的加法器，LUT表格的規(guī)模從1個[B×24N]的查找表減低到4個[B×2N]的查找表，查找表規(guī)模[4]減小到了原來的[14]。圖4即為對查找表的分割，每一級加法器前還可以加流水線，縮短延時路徑，提高時鐘頻率和數(shù)據(jù)吞吐率。

圖4 基于查找表分割的DA算法

OBC編碼即偏移二進制編碼，基本原理即在分布算法中，將輸入數(shù)據(jù)通過OBC編碼由{0，1}映射到{1，-1}，使得ROM表的上下兩部分具有鏡像對稱性關(guān)系，利用這種對稱性可以將ROM表的大小從原來的壓[2N]縮到[2N-1]，即壓縮一半[5]。下面來推導(dǎo)基于OBC編碼的DA算法：輸入數(shù)據(jù)可以表示為 ：

[xi=12[xi-（-xi）]] （4）

式中：[-xi]可以表示為式（5）：

[-x1，m-1+j=0m-1x1，m-1-j2-j+2-（m-1）] （5）

將式（5）和式（2）代入式（4）可得：[xi=12[xi-（-xi）] =12[-xi，m-1+j=0m-1xi，m-1-j2-j+xi，m-1-j=0m-1xi，m-1-j2-j-2-（m-1）] =12[-（xi，m-1-xi，m-1）+j=0m-1（xi，m-1-j-xi，m-1-j）2-j-2-（m-1）]] （6）

為了讓式子更簡潔，將兩部分整合為一個式子，定義[di，j]，其取值范圍為[-1，1]。

[di，j=xi，j-xi，j， j≠m-1-（xi，m-1-xi，m-1）， j=m-1] （7）

所以得到：

[xi=12j=0m-1di，m-1-j2-j+2-（m-1）] （8）

所以：

[y=j=0m-1i=0N-112widi，m-1-j2-j-12i=0N-1wi2-（m-1）] （9）

為了讓式子更簡潔，再次定義[Cj=i=0N-112widi，j]，[Cex=i=0N-112wi]，所以輸出數(shù)據(jù)可以寫成：

[y=j=0m-1Cj2-j-Cex2-（m-1）] （10）

基于OBC查找表的LUT表如圖5所示，優(yōu)化后的OBC查找表如圖6所示。

圖5 基于OBC查找表的LUT表

圖6 優(yōu)化后的OBC查找表

可以觀察到LUT的系數(shù)組合成鏡像，可以通過對[x0j]的控制來減小LUT的規(guī)模，當[x0j]=0時，其他階數(shù)相同比特位上的數(shù)據(jù)與其異或后的值不變；當[x0j=1]時，其他階數(shù)相同比特位上的數(shù)據(jù)異或后的值將取反[6]。S1為最高位標志位，當S1=1時，LUT的輸出取反，當S1=0時，LUT表的值不變。所以LUT表的最終輸出由[x0j]和S1共同決定；S2雙向選擇器控制著輸入移位寄存器的方向和[Cex]。上述原理結(jié)構(gòu)如圖7所示。

最后要介紹的方法的核心思想就是使用多個雙向選擇器，利用系數(shù)的對稱性逐步代替掉LUT。該結(jié)構(gòu)的推導(dǎo)如式（11）所示：

[ LUT（bk-1，bk-2，…，b1，b0）=LUT（bk-2，…，b1，b0）+wk-1，0= LUT（bk-3，...，b1，b0）+wk-1，0+wk-2，0=…= wk-1，0+wk-2，0+…+w0，0]

從式（11）可以看出，該算法就是把寄存器的輸出的最高位不斷反復(fù)的從LUT分離出來，由一個雙向選擇器和一個全加器來代替這部分LUT，從而達到減小LUT的目的，如圖8所示；然后再次通過使用選擇開關(guān)逐步替換掉次高位，再次減小LUT的容量，在對LUT進行反復(fù)的簡化之后，原來LUT結(jié)構(gòu)被雙向選擇器和加法器完全代替掉，最后得到不包含LUT的DA算法結(jié)構(gòu)[7]，如圖9所示。

圖7 基于OBC編碼的DA算法的實現(xiàn)

圖8 最高位被替換掉的LUT

3 各算法實現(xiàn)比較和性能分析

根據(jù)項目需求，該濾波器主要應(yīng)用于基站中頻處理模塊中，F(xiàn)IR濾波器放置于低采樣率的一端，并完成多個窄帶子載波的整形濾波，用于補償前端濾波器濾波特性的不足，同時完成一定倍數(shù)的插值（抽?。V波。由于該濾波器設(shè)計抽取插值倍數(shù)很高，通帶頻率也只有十幾kHz，此外，該模塊用于多個子載波的處理，因此對資源占用的要求也非?？量?。綜上所述，為了滿足通帶的性能指標以及盡量減少資源消耗的要求，本文需要設(shè)計一個基于DA算法的120階FIR濾波器才能滿足參數(shù)要求。首先使用FDATool導(dǎo)出120階，定點數(shù)據(jù)類型為（16，-2，18）的FIR濾波器系數(shù)，并全部轉(zhuǎn)換為16進制數(shù)，使用Verilog進行代碼編寫，在ISE環(huán)境下分別綜合仿真以上幾種算法。

圖9 改進的最終DA結(jié)構(gòu)

得到資源消耗如表1所示。

表1 各算法資源消耗對比

從表1的資源分析可以看出，并行FIR濾波器主要通過大量乘法器來并行處理數(shù)據(jù)，消耗大量邏輯資源，但是處理速度最快；串行FIR濾波器復(fù)用單個乘法器來完成120次乘法運算，輸入一個數(shù)據(jù)需要8個時鐘周期，輸出一個數(shù)據(jù)需要120個時鐘周期，快慢時鐘相差120倍，但是滿足了15倍下采樣的時鐘需求，處理速度最慢但消耗LUT資源最少；部分串行結(jié)構(gòu)平衡了二者的利弊，通過對時序的控制復(fù)用了8個乘法器，但是依然需要消耗乘法器資源；DA算法完全不在使用乘法器資源，但是會消耗大量的LUT資源，處理速度處于中等水平；LUT分解將大規(guī)模的查找表分割為了多個小規(guī)模的查找表，增加了流水線，處理速度要快于傳統(tǒng)的DA算法，而且還減少了LUT的資源消耗；基于雙向選擇器的改進算法進一步減小了查找表消耗，但是卻增加了寄存器的使用，處理速度趨于傳統(tǒng)的DA算法和LUT分解改進算法之間。如圖10～圖13所示。

在有相同控制信號的Testbench的仿真下，對比各波形傳輸延遲可以看出，各算法的處理速度大致相互關(guān)系為：

全并行>DA改進（LUT分解）≥DA分解（雙向選擇器）>傳統(tǒng)DA算法>全串行。

圖10 并行FIR濾波器

圖11 串行FIR濾波器

圖12 DA算法的FIR濾波器

圖13 改進的DA算法的FIR濾波器

4 結(jié) 論

通過對FIR濾波器傳統(tǒng)算法、DA算法及其改進的算法進行比較，當FPGA乘法器資源充足的情況下及濾波器階數(shù)較低的情況下，使用傳統(tǒng)算法比較理想，實現(xiàn)起來也較為容易；而本文提到的三種改進的DA算法很適用于在高階FIR濾波器的設(shè)計情況，基于OBC編碼的DA算法可以減少一半的LUT使用；在濾波器階數(shù)較大時（16階以上），LUT規(guī)模將會呈指數(shù)增加，基于查找表分解的改進算法可以從很大程度上減小LUT的規(guī)模，對而基于選擇器的DA算法可以完全不再占用更多的LUT和乘法器，可以節(jié)省LUT的資源到達50%以上，顯著降低了系統(tǒng)的復(fù)雜程度并提高了運行的速度。三種算法在資源緊缺和濾波器階數(shù)很高的情況下還可以結(jié)合使用，再加上流水線寄存器，可以在保證資源消耗不多的情況下，整合資源利用效率，提高整個信號處理的速度，減少傳輸延遲，減小系統(tǒng)復(fù)雜度，因此改進后的算法將會優(yōu)于傳統(tǒng)算法。目前，改進DA算法的FIR濾波器已經(jīng)應(yīng)用于系統(tǒng)設(shè)計中。

參考文獻

[1] 田耕.無線通信FPGA設(shè)計[M].北京：電子工業(yè)出版社，2007.

[2] 程佩青.數(shù)字信號處理教程[M].北京：清華大學(xué)出版社，2010.

[3] 劉朋全.基于FPGA的FIR數(shù)字濾波器的設(shè)計與實現(xiàn)[D].西安：西北工業(yè)大學(xué)，2006.

[4] 孫友軍.基于FPGA的FIR數(shù)字濾波器算法研究與設(shè)計實現(xiàn)[D].北京：冶金自動化研究設(shè)計院，2010.

[5] 顧文奕.FIR數(shù)字濾波器的優(yōu)化與驗證[J].電子測量技術(shù)，2008（5）：183?189.

[6] GUO Rui， DEBRUNNER L S. A novel adaptive filter implementation scheme using distributed arithmetic [C]// Proceedings of the Forty Fifth Asilomar Conference on Signals， Systems and Computers. Pacific Grove， CA： [s.n.]， 2011： 160?164.

[7] YOO Heejong， ANDERSIN D V. Hardware?efficient distributed arithmetic architecture for high?order digital filters [C]// Proceedings of IEEE International Conference on Acoustics， Speech， and Signal Processing. [S.l.]： IEEE. 2005：125?128.

可以觀察到LUT的系數(shù)組合成鏡像，可以通過對[x0j]的控制來減小LUT的規(guī)模，當[x0j]=0時，其他階數(shù)相同比特位上的數(shù)據(jù)與其異或后的值不變；當[x0j=1]時，其他階數(shù)相同比特位上的數(shù)據(jù)異或后的值將取反[6]。S1為最高位標志位，當S1=1時，LUT的輸出取反，當S1=0時，LUT表的值不變。所以LUT表的最終輸出由[x0j]和S1共同決定；S2雙向選擇器控制著輸入移位寄存器的方向和[Cex]。上述原理結(jié)構(gòu)如圖7所示。

最后要介紹的方法的核心思想就是使用多個雙向選擇器，利用系數(shù)的對稱性逐步代替掉LUT。該結(jié)構(gòu)的推導(dǎo)如式（11）所示：

[ LUT（bk-1，bk-2，…，b1，b0）=LUT（bk-2，…，b1，b0）+wk-1，0= LUT（bk-3，...，b1，b0）+wk-1，0+wk-2，0=…= wk-1，0+wk-2，0+…+w0，0]

從式（11）可以看出，該算法就是把寄存器的輸出的最高位不斷反復(fù)的從LUT分離出來，由一個雙向選擇器和一個全加器來代替這部分LUT，從而達到減小LUT的目的，如圖8所示；然后再次通過使用選擇開關(guān)逐步替換掉次高位，再次減小LUT的容量，在對LUT進行反復(fù)的簡化之后，原來LUT結(jié)構(gòu)被雙向選擇器和加法器完全代替掉，最后得到不包含LUT的DA算法結(jié)構(gòu)[7]，如圖9所示。

圖7 基于OBC編碼的DA算法的實現(xiàn)

圖8 最高位被替換掉的LUT

3 各算法實現(xiàn)比較和性能分析

根據(jù)項目需求，該濾波器主要應(yīng)用于基站中頻處理模塊中，F(xiàn)IR濾波器放置于低采樣率的一端，并完成多個窄帶子載波的整形濾波，用于補償前端濾波器濾波特性的不足，同時完成一定倍數(shù)的插值（抽取）濾波。由于該濾波器設(shè)計抽取插值倍數(shù)很高，通帶頻率也只有十幾kHz，此外，該模塊用于多個子載波的處理，因此對資源占用的要求也非?？量獭＞C上所述，為了滿足通帶的性能指標以及盡量減少資源消耗的要求，本文需要設(shè)計一個基于DA算法的120階FIR濾波器才能滿足參數(shù)要求。首先使用FDATool導(dǎo)出120階，定點數(shù)據(jù)類型為（16，-2，18）的FIR濾波器系數(shù)，并全部轉(zhuǎn)換為16進制數(shù)，使用Verilog進行代碼編寫，在ISE環(huán)境下分別綜合仿真以上幾種算法。

圖9 改進的最終DA結(jié)構(gòu)

得到資源消耗如表1所示。

表1 各算法資源消耗對比

從表1的資源分析可以看出，并行FIR濾波器主要通過大量乘法器來并行處理數(shù)據(jù)，消耗大量邏輯資源，但是處理速度最快；串行FIR濾波器復(fù)用單個乘法器來完成120次乘法運算，輸入一個數(shù)據(jù)需要8個時鐘周期，輸出一個數(shù)據(jù)需要120個時鐘周期，快慢時鐘相差120倍，但是滿足了15倍下采樣的時鐘需求，處理速度最慢但消耗LUT資源最少；部分串行結(jié)構(gòu)平衡了二者的利弊，通過對時序的控制復(fù)用了8個乘法器，但是依然需要消耗乘法器資源；DA算法完全不在使用乘法器資源，但是會消耗大量的LUT資源，處理速度處于中等水平；LUT分解將大規(guī)模的查找表分割為了多個小規(guī)模的查找表，增加了流水線，處理速度要快于傳統(tǒng)的DA算法，而且還減少了LUT的資源消耗；基于雙向選擇器的改進算法進一步減小了查找表消耗，但是卻增加了寄存器的使用，處理速度趨于傳統(tǒng)的DA算法和LUT分解改進算法之間。如圖10～圖13所示。

在有相同控制信號的Testbench的仿真下，對比各波形傳輸延遲可以看出，各算法的處理速度大致相互關(guān)系為：

全并行>DA改進（LUT分解）≥DA分解（雙向選擇器）>傳統(tǒng)DA算法>全串行。

圖10 并行FIR濾波器

圖11 串行FIR濾波器

圖12 DA算法的FIR濾波器

圖13 改進的DA算法的FIR濾波器

4 結(jié) 論

通過對FIR濾波器傳統(tǒng)算法、DA算法及其改進的算法進行比較，當FPGA乘法器資源充足的情況下及濾波器階數(shù)較低的情況下，使用傳統(tǒng)算法比較理想，實現(xiàn)起來也較為容易；而本文提到的三種改進的DA算法很適用于在高階FIR濾波器的設(shè)計情況，基于OBC編碼的DA算法可以減少一半的LUT使用；在濾波器階數(shù)較大時（16階以上），LUT規(guī)模將會呈指數(shù)增加，基于查找表分解的改進算法可以從很大程度上減小LUT的規(guī)模，對而基于選擇器的DA算法可以完全不再占用更多的LUT和乘法器，可以節(jié)省LUT的資源到達50%以上，顯著降低了系統(tǒng)的復(fù)雜程度并提高了運行的速度。三種算法在資源緊缺和濾波器階數(shù)很高的情況下還可以結(jié)合使用，再加上流水線寄存器，可以在保證資源消耗不多的情況下，整合資源利用效率，提高整個信號處理的速度，減少傳輸延遲，減小系統(tǒng)復(fù)雜度，因此改進后的算法將會優(yōu)于傳統(tǒng)算法。目前，改進DA算法的FIR濾波器已經(jīng)應(yīng)用于系統(tǒng)設(shè)計中。

參考文獻

[1] 田耕.無線通信FPGA設(shè)計[M].北京：電子工業(yè)出版社，2007.

[2] 程佩青.數(shù)字信號處理教程[M].北京：清華大學(xué)出版社，2010.

[3] 劉朋全.基于FPGA的FIR數(shù)字濾波器的設(shè)計與實現(xiàn)[D].西安：西北工業(yè)大學(xué)，2006.

[4] 孫友軍.基于FPGA的FIR數(shù)字濾波器算法研究與設(shè)計實現(xiàn)[D].北京：冶金自動化研究設(shè)計院，2010.

[5] 顧文奕.FIR數(shù)字濾波器的優(yōu)化與驗證[J].電子測量技術(shù)，2008（5）：183?189.

[6] GUO Rui， DEBRUNNER L S. A novel adaptive filter implementation scheme using distributed arithmetic [C]// Proceedings of the Forty Fifth Asilomar Conference on Signals， Systems and Computers. Pacific Grove， CA： [s.n.]， 2011： 160?164.

[7] YOO Heejong， ANDERSIN D V. Hardware?efficient distributed arithmetic architecture for high?order digital filters [C]// Proceedings of IEEE International Conference on Acoustics， Speech， and Signal Processing. [S.l.]： IEEE. 2005：125?128.

可以觀察到LUT的系數(shù)組合成鏡像，可以通過對[x0j]的控制來減小LUT的規(guī)模，當[x0j]=0時，其他階數(shù)相同比特位上的數(shù)據(jù)與其異或后的值不變；當[x0j=1]時，其他階數(shù)相同比特位上的數(shù)據(jù)異或后的值將取反[6]。S1為最高位標志位，當S1=1時，LUT的輸出取反，當S1=0時，LUT表的值不變。所以LUT表的最終輸出由[x0j]和S1共同決定；S2雙向選擇器控制著輸入移位寄存器的方向和[Cex]。上述原理結(jié)構(gòu)如圖7所示。

最后要介紹的方法的核心思想就是使用多個雙向選擇器，利用系數(shù)的對稱性逐步代替掉LUT。該結(jié)構(gòu)的推導(dǎo)如式（11）所示：

[ LUT（bk-1，bk-2，…，b1，b0）=LUT（bk-2，…，b1，b0）+wk-1，0= LUT（bk-3，...，b1，b0）+wk-1，0+wk-2，0=…= wk-1，0+wk-2，0+…+w0，0]

從式（11）可以看出，該算法就是把寄存器的輸出的最高位不斷反復(fù)的從LUT分離出來，由一個雙向選擇器和一個全加器來代替這部分LUT，從而達到減小LUT的目的，如圖8所示；然后再次通過使用選擇開關(guān)逐步替換掉次高位，再次減小LUT的容量，在對LUT進行反復(fù)的簡化之后，原來LUT結(jié)構(gòu)被雙向選擇器和加法器完全代替掉，最后得到不包含LUT的DA算法結(jié)構(gòu)[7]，如圖9所示。

圖7 基于OBC編碼的DA算法的實現(xiàn)

圖8 最高位被替換掉的LUT

3 各算法實現(xiàn)比較和性能分析

根據(jù)項目需求，該濾波器主要應(yīng)用于基站中頻處理模塊中，F(xiàn)IR濾波器放置于低采樣率的一端，并完成多個窄帶子載波的整形濾波，用于補償前端濾波器濾波特性的不足，同時完成一定倍數(shù)的插值（抽?。V波。由于該濾波器設(shè)計抽取插值倍數(shù)很高，通帶頻率也只有十幾kHz，此外，該模塊用于多個子載波的處理，因此對資源占用的要求也非?？量?。綜上所述，為了滿足通帶的性能指標以及盡量減少資源消耗的要求，本文需要設(shè)計一個基于DA算法的120階FIR濾波器才能滿足參數(shù)要求。首先使用FDATool導(dǎo)出120階，定點數(shù)據(jù)類型為（16，-2，18）的FIR濾波器系數(shù)，并全部轉(zhuǎn)換為16進制數(shù)，使用Verilog進行代碼編寫，在ISE環(huán)境下分別綜合仿真以上幾種算法。

圖9 改進的最終DA結(jié)構(gòu)

得到資源消耗如表1所示。

表1 各算法資源消耗對比

從表1的資源分析可以看出，并行FIR濾波器主要通過大量乘法器來并行處理數(shù)據(jù)，消耗大量邏輯資源，但是處理速度最快；串行FIR濾波器復(fù)用單個乘法器來完成120次乘法運算，輸入一個數(shù)據(jù)需要8個時鐘周期，輸出一個數(shù)據(jù)需要120個時鐘周期，快慢時鐘相差120倍，但是滿足了15倍下采樣的時鐘需求，處理速度最慢但消耗LUT資源最少；部分串行結(jié)構(gòu)平衡了二者的利弊，通過對時序的控制復(fù)用了8個乘法器，但是依然需要消耗乘法器資源；DA算法完全不在使用乘法器資源，但是會消耗大量的LUT資源，處理速度處于中等水平；LUT分解將大規(guī)模的查找表分割為了多個小規(guī)模的查找表，增加了流水線，處理速度要快于傳統(tǒng)的DA算法，而且還減少了LUT的資源消耗；基于雙向選擇器的改進算法進一步減小了查找表消耗，但是卻增加了寄存器的使用，處理速度趨于傳統(tǒng)的DA算法和LUT分解改進算法之間。如圖10～圖13所示。

在有相同控制信號的Testbench的仿真下，對比各波形傳輸延遲可以看出，各算法的處理速度大致相互關(guān)系為：

全并行>DA改進（LUT分解）≥DA分解（雙向選擇器）>傳統(tǒng)DA算法>全串行。

圖10 并行FIR濾波器

圖11 串行FIR濾波器

圖12 DA算法的FIR濾波器

圖13 改進的DA算法的FIR濾波器

4 結(jié) 論

通過對FIR濾波器傳統(tǒng)算法、DA算法及其改進的算法進行比較，當FPGA乘法器資源充足的情況下及濾波器階數(shù)較低的情況下，使用傳統(tǒng)算法比較理想，實現(xiàn)起來也較為容易；而本文提到的三種改進的DA算法很適用于在高階FIR濾波器的設(shè)計情況，基于OBC編碼的DA算法可以減少一半的LUT使用；在濾波器階數(shù)較大時（16階以上），LUT規(guī)模將會呈指數(shù)增加，基于查找表分解的改進算法可以從很大程度上減小LUT的規(guī)模，對而基于選擇器的DA算法可以完全不再占用更多的LUT和乘法器，可以節(jié)省LUT的資源到達50%以上，顯著降低了系統(tǒng)的復(fù)雜程度并提高了運行的速度。三種算法在資源緊缺和濾波器階數(shù)很高的情況下還可以結(jié)合使用，再加上流水線寄存器，可以在保證資源消耗不多的情況下，整合資源利用效率，提高整個信號處理的速度，減少傳輸延遲，減小系統(tǒng)復(fù)雜度，因此改進后的算法將會優(yōu)于傳統(tǒng)算法。目前，改進DA算法的FIR濾波器已經(jīng)應(yīng)用于系統(tǒng)設(shè)計中。

參考文獻

[1] 田耕.無線通信FPGA設(shè)計[M].北京：電子工業(yè)出版社，2007.

[2] 程佩青.數(shù)字信號處理教程[M].北京：清華大學(xué)出版社，2010.

[3] 劉朋全.基于FPGA的FIR數(shù)字濾波器的設(shè)計與實現(xiàn)[D].西安：西北工業(yè)大學(xué)，2006.

[4] 孫友軍.基于FPGA的FIR數(shù)字濾波器算法研究與設(shè)計實現(xiàn)[D].北京：冶金自動化研究設(shè)計院，2010.

[5] 顧文奕.FIR數(shù)字濾波器的優(yōu)化與驗證[J].電子測量技術(shù)，2008（5）：183?189.

[6] GUO Rui， DEBRUNNER L S. A novel adaptive filter implementation scheme using distributed arithmetic [C]// Proceedings of the Forty Fifth Asilomar Conference on Signals， Systems and Computers. Pacific Grove， CA： [s.n.]， 2011： 160?164.

[7] YOO Heejong， ANDERSIN D V. Hardware?efficient distributed arithmetic architecture for high?order digital filters [C]// Proceedings of IEEE International Conference on Acoustics， Speech， and Signal Processing. [S.l.]： IEEE. 2005：125?128.