二維濾波器分布式算法結(jié)構(gòu)的改進與實現(xiàn)?

凌春麗,劉云飛,姜黎黎,李湘云

(南京林業(yè)大學(xué) 信息科學(xué)技術(shù)學(xué)院 ,江蘇 南京 210037)

有限長單位沖激響應(yīng)(FIR)數(shù)字濾波器因其良好的線性相位及穩(wěn)定性被廣泛應(yīng)用于現(xiàn)代電子通信系統(tǒng)中.設(shè)計 FIR濾波器最初采用卷積型、直接型結(jié)構(gòu),需要組合多個加法器、移位器和乘法器來實現(xiàn).由于乘法器占用資源太大,相繼提出了應(yīng)用移位相加單元來替代直接型中的乘法器,然而此種結(jié)構(gòu)對現(xiàn)場可編程門陣列(FPGA)的資源利用率仍然太低.為解決這一問題,研究人員提出了許多解決方案,概括起來主要有以下兩類方法[1]：

一類是利用二進制編碼特性,采用加法器代替乘法器,通過對濾波器系數(shù)進行分解,重復(fù)使用相同系數(shù)因子的簡化加法器圖(RAG)算法;另一類是應(yīng)用預(yù)先存儲或查找表(LUT)方法減少乘法器的使用.此類方法的代表就是分布式(DA)算法.

DA算法因其高效的資源利用率和面積-時間效率得到廣泛應(yīng)用.基于 DA算法的 FIR數(shù)字濾波器設(shè)計得到廣泛應(yīng)用.主要包括對一系列 LUT的訪問和移位累加操作.但隨著濾波器階數(shù)的增加,需要的 LUT存儲器資源成指數(shù)增加,為解決此問題,Wang Sen和 Tang Bin提出了一種應(yīng)用選擇器實現(xiàn)查找表的改進分布式算法[2,3].另外,Meher等人采用對濾波器系數(shù)的 bit序列進行并行處理的方法,設(shè)計出了一維和二維的 DA算法濾波器,進一步提高了資源利用率和運行速率及數(shù)據(jù)的吞吐量[4,5].本文在 Meher等人提出的結(jié)構(gòu)上增加了延時模塊,避免了因時序設(shè)計帶來的混亂,保證了輸出結(jié)果的正確性.同時應(yīng)用二進制位權(quán)乘法(*2n)替代移位相加結(jié)構(gòu),以節(jié)省更多的存儲器資源和邏輯單元(LE).

1 二維分布式算法的改進

1.1 分布式算法

一個 N階的 FIR濾波器的表達式如下：

式中：wn表示濾波器系數(shù);x[n]為輸入數(shù)據(jù).

對于有符號的系統(tǒng),x[n]可用式(2)表示

將式(2)代入式(1),得到 DA算法的表達式

式中：x[n]為輸入信號 x的采樣序列;y[n]為輸出序列;wn為濾波器系數(shù);b表示輸入數(shù)據(jù)的第b個 bit位.

由公式(3)可以看出,分布式算法應(yīng)用了移位相加單元和加法單元實現(xiàn)乘法.具體計算為：對x0[n]到 xB-1[n],依次乘以 20位權(quán)到 2B-1位權(quán);對于符號位 xB[n]乘以 -2B位權(quán).

1.2 二維 DA算法的改進

2008年,Meher設(shè)計出了一維和二維的基于DA算法的 FIR濾波器,其中二維的 DA算法如公式(4)[5]

式中：b為輸入數(shù)據(jù)的第b個比特位;B為輸入數(shù)據(jù)的總比特位;n為第n個數(shù)據(jù);(N+1)/2=P*M(M為查找表的輸入位數(shù);P為每一并串轉(zhuǎn)換下查找表的個數(shù)).

Meher設(shè)計的二維 DA算法 FIR濾波器的結(jié)構(gòu)[3]與圖 1相比缺少了延時模塊.采用全局時鐘時,時序上有缺陷.以 16階 FIR濾波器為例,16個輸入數(shù)據(jù)從移位寄存器同時經(jīng)過并串模塊、查找表模塊和加法模塊.在進入移位相加模塊前,16個數(shù)據(jù)已準備就緒,需在一個周期內(nèi)對 16個數(shù)據(jù)同時處理(避免與下一個周期的數(shù)據(jù)沖突).而 Meher設(shè)計的移位相加是以從下(b=7)向上(b=0)的順序依次執(zhí)行,無法在一個周期內(nèi)對 16個輸入數(shù)據(jù)進行處理.若在移位相加模塊前增加延時模塊,就能保證輸出結(jié)果的正確性.因此,在Meher提出的結(jié)構(gòu)上增加了延時模塊,如圖 1所示.將其稱之為“延時型”結(jié)構(gòu).

圖1 延時型結(jié)構(gòu)Fig.1 Structure of time-delaying type

Meher等人提出的二維分布式算法結(jié)構(gòu),對每個系數(shù)的 bit序列進行并行處理.Meher提出的移位相加模塊從 xB[n]開始,先左移一位(乘2,若為符號位則乘 -2),再加上 xB-1[n];接著將其和再左移一位(乘 2),加上 xB-2[n].如此順序運算,從下到上,求得結(jié)果.此移位相加法可以有效地減少存儲器的使用.但由于延時模塊的加入,使用了太多的移位器,抵消了移位相加模塊節(jié)省的存儲器資源.為減少存儲器資源和 LE的消耗,對延時和移位相加模塊進一步優(yōu)化.這里應(yīng)用二進制位權(quán)乘法(*2n)替代圖 1所示的延時和移位相加模塊[6],改進后的結(jié)構(gòu)如圖 2所示.較之“延時型”結(jié)構(gòu),“改進型”結(jié)構(gòu)能節(jié)省更多的LE和存儲器資源.

圖2 改進型結(jié)構(gòu)Fig.2 Structure of improv ement type

2 性能分析

為了能更好地觀察 P(每一并串轉(zhuǎn)換下查找表的個數(shù))及 M(查找表的輸入位數(shù))對 FPGA資源利用率和存儲器的影響,分析兩種結(jié)構(gòu)的優(yōu)缺點,本文設(shè)計了不同階數(shù)的Ⅱ 型 FIR濾波器以比較其性能[7,8].濾波器階數(shù)取為 3,7,15,31,63階,將濾波器系數(shù)乘以 214,取整,濾波器輸入采用了14 bit.分別針對式(4)中的 M=2,4,8的情況進行設(shè)計.表 1記錄了不同階數(shù)、不同查找表位數(shù)下邏輯單元和存儲器的消耗情況及濾波器的工作速度.

從表 1可以得出如下結(jié)論：①應(yīng)用 FPGA實現(xiàn)低階 FIR濾波器時,“改進型”比“延時型”節(jié)約了更多的邏輯單元與存儲器資源.這是由于在低階時“延時型”結(jié)構(gòu)中延時模塊占用資源較多,甚至超出了移位相加模塊所節(jié)省的加法器和乘法器資源;② 增加濾波器的階數(shù),兩種結(jié)構(gòu)的存儲器和 LE資源會非線性地增加.比較發(fā)現(xiàn),“延時型”消耗 LE資源的增速比“改進型”緩慢.產(chǎn)生這種結(jié)果的原因是：當(dāng)濾波器階數(shù)不斷增加,規(guī)模不斷擴大時,延時模塊對 LE消耗的影響越來越小.③濾波器階數(shù)較低時,“延時型”比“改進型”工作速度更快.隨著階數(shù)的增加,“改進型”濾波器比“延時型”濾波器工作速度更加穩(wěn)定,且衰減趨緩.

表1 邏輯單元和存儲器的消耗情況Tab.1 Consumptions of LE and memory(B=8)

3 仿真結(jié)果及硬件實現(xiàn)

3.1 Ⅱ類線性相位FIR濾波器

Ⅱ 型 FIR濾波器的表達式為

從式(5)可以看出,由于Ⅱ 型 FIR濾波器的濾波系數(shù)為偶對稱,一個 N階的Ⅱ 型 FIR濾波器可以用一個(N+1)/2階的濾波器實現(xiàn).相對于非對稱 FIR濾波器,式(5)增加了(N+1)/2的加法器及相應(yīng)的控制邏輯,但是相對于濾波器階數(shù)減少 50%所節(jié)省的資源是值得的[9,10].

3.2 濾波器設(shè)計與實現(xiàn)

下面以基于“改進型”結(jié)構(gòu)的 31階 FIR帶通濾波器為例,說明濾波器的設(shè)計與實現(xiàn)[11,12].

3.2.1 設(shè)計指標(biāo)

采樣頻率：50 M Hz;類型：帶通濾波器;通帶范圍：250 k～ 800 kHz;輸入數(shù)據(jù)寬度：14位;輸出數(shù)據(jù)寬度：28位.

根據(jù)設(shè)計指標(biāo),應(yīng)用 MAT LAB軟件中的Toolbox工具箱,選擇 Hann窗設(shè)計符合要求的FIR濾波器系數(shù)[4].應(yīng)用 M ATLAB中的取整函數(shù)對系數(shù)進行量化,即乘以 214,系數(shù)如下：

3.2.2 硬件實現(xiàn)

硬件平臺采用 Altera公司的 DE2開發(fā)板及其配套 AD/DA子板.

軟件仿真平臺采用 QUARTUS II中的SignalTap.值得注意的是,應(yīng)用 SignalTap仿真之前必須將濾波程序下載到 DE2開發(fā)板上.

應(yīng)用“一分二”電視分配器合成一疊加信號,此時分配器原有的兩個輸出端現(xiàn)用作輸入端,原輸入端現(xiàn)用作輸出端.借助兩個函數(shù)信號發(fā)生器產(chǎn)生兩路輸入信號,其中之一為幅度 2 V的500 kHz正弦信號,另一個為幅度 2 V的 3 MHz正弦信號.將此疊加信號用作濾波器的輸入信號.圖 3為示波器顯示的輸入信號.

圖3 輸入信號Fig.3 Input signal

實際測試時,先應(yīng)用 SignalTap觀測仿真效果,如圖 4所示.其中 ADC_ DA 為疊加的輸入信號,DACDA 為基于“改進型”濾波器的濾波結(jié)果.從圖 4中可以看出,濾波后的信號頻率為500 kHz(周期為 2μ s),沒有出現(xiàn)失真,仿真結(jié)果符合設(shè)計要求.

為驗證“改進型”FIR帶通濾波器的實際濾波效果,首先將濾波程序下載到 DE2開發(fā)板的FPGA芯片上,構(gòu)成一硬件濾波器,然后將疊加的輸入信號通過該濾波器,以實現(xiàn)濾波功能.圖 5為疊加信號經(jīng)濾波后在示波器上的輸出,它是一頻率為 500 kHz的帶內(nèi)信號,濾波效果與仿真結(jié)果一致.

圖4 SignalTap仿真圖Fig.4 Simulation result using SignalTap

圖5 濾波后的輸出信號Fig.5 Filtered output sig nal

將幅度 2 V的 500 kHz方波信號與幅度 2 V的 3 MHz方波信號疊加,用作濾波器的輸入信號.濾波結(jié)果如圖 6所示.

圖6 輸入信號為方波時的濾波結(jié)果Fig.6 Filtering result using square wav es as input signal

4 結(jié)束語

文中對 Meher提出的 FIR濾波器結(jié)構(gòu)進行了改進,通過增加延時模塊,克服了 Meher設(shè)計中時序上的缺陷,并應(yīng)用二進制位權(quán)乘法(*2n)替代延時和移位相加結(jié)構(gòu),在低階時節(jié)省了較多的 LE和存儲器資源.

通過測試不同階數(shù)濾波器的 LE及存儲器資源的消耗發(fā)現(xiàn)：“延時型”結(jié)構(gòu)和“改進型”結(jié)構(gòu)的FIR帶通濾波器存儲器資源的消耗并不與查找表位數(shù)成線性關(guān)系,M=4時較之 M=2和 M=8時能節(jié)省更多的存儲器資源;LE消耗與查找表位數(shù)成正比,M越大,LE消耗越多;“改進型”結(jié)構(gòu)的速度雖然不及“延時型”,但隨著階數(shù)的增加,“改進型”結(jié)構(gòu)的濾波速度平穩(wěn)、衰減緩慢.因此,針對具體設(shè)計要具體分析,選擇合適的優(yōu)化結(jié)構(gòu)[14,15].

為驗證“改進型”FIR濾波器的設(shè)計效果,應(yīng)用 Altera DE2開發(fā)板及其配套的 AD/DA子板進行了測試.測試結(jié)果表明：該濾波器完全濾除了通帶外信號,實現(xiàn)了帶通濾波的目標(biāo).

[1]Huang W,Anderson D V.Modified sliding-block distributed arithmetic with offset binary coding for adaptive filters[J].Journal of SignalProcessing Systems,2011,63(1)：153-163.

[2]田豐,牟衛(wèi)華 ,陳華明,等.基于分布式算法的線性相位 FIR濾波器設(shè)計 [J].艦船電子工程 ,2010(2)：57-60.Tian Feng,Mou Weihu,ChengHuaming,et al.Design oflinear FIR filter based on distributed arithmetic[J]. Ships Electronic Engineering,2010(2)：57-60.(in Chinese)

[3]閆永鵬,于海勛.一種基于 LUT的改進 FIR濾波器的設(shè)計 [J].微電子學(xué),2010,40(5)：693-696.Yan Yongpeng,Yu Haixun.An improvement design ofLU T-based FIR filter[J].Micro Electronics,2010,40(5)：693-696.(in Chinese)

[4]李書華,曾以成.基于分布式算法的高階 FIR濾波器及其 FPGA實現(xiàn) [J].計算機工程與應(yīng)用,2010,46(12)：136-138.Li Shuhua,Zeng Yicheng.Implementation of highorder filterbased on FIR filteron FPGA[J].Computer Engineering and Applications,2010,46(12)：136-138.(in Chinese)

[5]M eher P K.New approach to LUT implementation and accumulation formemory-based multiplication[C].Proc.IEEE Int.Symp.Cire.and Syst.,2009：453-456.

[6]MeherP K. FPGA realization ofFIR filters by efficient and flexible systolization using distributed arithermetic[J]. IEEE Transactionson Signal Processing,2008,56(7)：3009-3017.

[7]薛嚴冰,韓雪,邵遠.基于分布式算法的 FIR數(shù)字濾波器的 FPGA實現(xiàn) [J].大連交通大學(xué)學(xué)報,2009(4)：84-87.Xue Yanbing,Han Xue,Shao Yuan.Implementation of digital FIR filter on FPGA based on distributed arithmetic[J].Journal of Dalian Jiao-tong University,2009(4)：84-87.(in Chinese)

[8]王法棟,劉宇.高階數(shù)字濾波器分布式算法結(jié)構(gòu)比較[J].聲學(xué)技術(shù),2009(3)：307-311.WangFadong,Liu Yu.Comparison of high-order digital filter based on distributed arithmetic[J].Acoustic Technology, 2009(3)：307-311.(in Chinese)

[9]Lo H J,Yoo H J,Anderson D V.A reusable distributed arithmetic architecture for FIR Filtering[J].IEEE,2008：233-236.

[10]Wang Sen,Tang Bin,Zhou Jun.Distributed arithmetic for FIR filterdesign on FPGA [J].International Conference on Communications,Circuits and Systems,2007(10)：620-623.

[11]李林.利用 DA算法實現(xiàn)大規(guī)模 FIR濾波器 [J].實驗科學(xué)與技術(shù) ,2006(2)：7-9.Li Lin.Implementation of large-scale FIR filter using distributed arithmetic[J].Experimental Science and Technology,2006(2)：7-9.(in Chinese)

[12]Rawski M.Efficient implementation of digital filters with use of advanced msynthesis methods targeted FPGA architectures[C].Proceedings of the20058th Euromicro Confenrence on Digital System Design,2005.

[13]張慶玲,楊勇.FPGA原理與實踐[M].北京：北京航空航天大學(xué)出版社,2006.

[14]劉圓,黃晨靈,高佩君.基于分段查找表的高速 FIR濾波器的設(shè)計實現(xiàn) [J].微電子學(xué),2006,36(5)：674-678.Liu Yuan,Huang Chenling,Gao Peijun.Re-alization of high-speed filter based on sub-LU T[J].Micro Electronics,2006,36(5)：674-678.(in Chinese)

[15]丁丹.FIR濾波器的 FPGA高效實現(xiàn)和巧妙驗證[J].電子科技 ,2005(9)：29-32,Ding Dan. Efficientimplementation and clever verification of FIR filter on FPGA[J].Electronic Technology,2005(9)：29-32.(in Chinese)