基于FPGA和符號LMS算法的自適應(yīng)濾波器設(shè)計(jì)*

邱陳輝,李　鋒,徐祖強(qiáng)

(1.浙江大學(xué)生物醫(yī)學(xué)工程教育部重點(diǎn)實(shí)驗(yàn)室,杭州 310027;2.江蘇科技大學(xué)電子信息學(xué)院,江蘇 鎮(zhèn)江 212003)

?

基于FPGA和符號LMS算法的自適應(yīng)濾波器設(shè)計(jì)*

邱陳輝1,李鋒2*,徐祖強(qiáng)2

(1.浙江大學(xué)生物醫(yī)學(xué)工程教育部重點(diǎn)實(shí)驗(yàn)室,杭州 310027;2.江蘇科技大學(xué)電子信息學(xué)院,江蘇 鎮(zhèn)江 212003)

摘要:為了減少實(shí)現(xiàn)基于FPGA和LMS算法的自適應(yīng)濾波器過多消耗硬件資源的問題,提出了符號LMS算法,通過降低乘法運(yùn)算的次數(shù)來提高自適應(yīng)濾波器的運(yùn)行速度,并使用流水線技術(shù)進(jìn)行優(yōu)化。軟件仿真驗(yàn)證了符號LMS算法的可行性,硬件仿真證實(shí)了采用該算法和流水線技術(shù)的自適應(yīng)濾波器的優(yōu)越性。

關(guān)鍵詞:數(shù)字信號處理;自適應(yīng)濾波器;最小均方;符號最小均方;現(xiàn)場可編程門陣列;流水線

自適應(yīng)濾波器在現(xiàn)代數(shù)字信號處理中的應(yīng)用極為廣泛,主要分成系統(tǒng)辨識、逆模型、預(yù)測和干擾消除4大類別[1]。對于實(shí)時性要求很高的場合,往往需要使用硬件設(shè)計(jì)自適應(yīng)濾波器,并且自適應(yīng)算法盡量簡單、易實(shí)現(xiàn)[2]。基于現(xiàn)場可編程門陣列(FPGA)硬件和最小均方(LMS)自適應(yīng)算法的自適應(yīng)濾波器近年來被不斷地研究和改進(jìn)。

由于FPGA中嵌入了較多硬線乘法器和加減器,使用它們很容易實(shí)現(xiàn)乘累加(MAC)運(yùn)算,故通常將采用LMS算法的自適應(yīng)濾波器直接映射到FPGA芯片上。但這樣消耗較多的硬件資源,也不能發(fā)揮FPGA并行處理的優(yōu)勢。故本文提出了利用符號LMS算法和流水線技術(shù)對上述自適應(yīng)濾波器進(jìn)行優(yōu)化,從而減少嵌入式乘法器資源的消耗并且提高運(yùn)行速度。

1　自適應(yīng)濾波器算法

1.1LMS算法

設(shè)x(n)和w(n)分別表示自適應(yīng)濾波器的輸入信號和權(quán)值向量,定義

x(n)=[x(n),x(n-1),…,x(n-L+1)]T

w(n)=[w0(n),w1(n),…,wL-1(n)]T

則LMS算法的基本形式如下

濾波輸出:

(1)

誤差計(jì)算:

e(n)=d(n)-y(n)

(2)

權(quán)值更新:

w(n+1)=w(n)+μe(n)x(n)

(3)

其中y(n)是自適應(yīng)濾波器的輸出信號,d(n)是期望信號,e(n)表示誤差信號,μ是收斂因子,L是自適應(yīng)濾波器的階數(shù)。因?yàn)長MS算法是嚴(yán)格順序執(zhí)行的,所以式(1)～式(3)的次序不能顛倒[3]。其模塊圖如圖1所示。

圖1　LMS算法的模塊圖

雖然LMS算法的推導(dǎo)過程涉及求梯度和微分,但是其最終形式只涉及乘法、加減和迭代3種運(yùn)算,并且乘法運(yùn)算量最多。而利用FPGA實(shí)現(xiàn)基于LMS算法的自適應(yīng)濾波器時,硬件資源的消耗很大一部分來源于乘法運(yùn)算。不管是利用FPGA中的基本邏輯單元LE(Logic Element)還是嵌入式乘法器模塊實(shí)現(xiàn)乘法運(yùn)算,基于硬件的乘法運(yùn)算都將是高成本的,應(yīng)盡可能地減少[4]。

1.2符號LMS算法

式(1)中的乘法是為了計(jì)算自適應(yīng)均衡器的輸出信號,不能刪減。式(3)中的乘法是針對收斂因子μ、誤差信號e(n)和輸入矢量x(n)進(jìn)行的,可以進(jìn)行改進(jìn)。針對一些特殊應(yīng)用,e(n)和x(n)的乘積事實(shí)上無需兩者都以全精度值參與計(jì)算,只取他們的符號進(jìn)行運(yùn)算即可[5]。

第1種方案是對e(n)取符號,利用正負(fù)號符號函數(shù)Signum(·)得 sign[e(n)],而x(n)保持全精度,這樣兩者相乘的結(jié)果就是x(n),要么是對x(n)取負(fù)值。第2種方案是對x(n)中的x(n)、x(n-1)、…、x(n-L+1)取符號,利用Signum(·)得sign[x(n)],此時兩者的乘積要么就是e(n),要么就是對e(n)取負(fù)值。第3種方案是同時對e(n)和x(n)取符號,利用Signum(·)得sign[e(n)]和sign[x(n)],這樣兩者相乘的結(jié)果就是1或-1。這3種符號LMS算法方案的公式表示依次為

w(n+1)=w(n)+μsign[e(n)]x(n)

(4)

w(n+1)=w(n)+μe(n)sign[x(n)]

(5)

w(n+1)=w(n)+μsign[e(n)]sign[x(n)]

(6)

符號LMS算法其實(shí)是對LMS算法的一種改進(jìn),其模塊圖如圖2所示,它可由隨機(jī)梯度法推導(dǎo)而來,以均方誤差E[|e(n)|2]為代價函數(shù)J(n),推導(dǎo)關(guān)鍵是對J(n)求梯度,然后對其權(quán)值w(n)進(jìn)行自適應(yīng)調(diào)整時,只考慮J(n)的梯度方向,忽略具體的梯度值。因此,犧牲輸入信號或誤差信號精度的符號LMS算法并不適用于所有的自適應(yīng)系統(tǒng)[6],利用MATLAB對使用該算法的自適應(yīng)濾波器進(jìn)行前期的驗(yàn)證評估是十分必要的。

圖2　符號LMS算法的模塊圖

假若μ的取值不是2的冪形式,那么第1、第2種方案節(jié)省的乘法器數(shù)量相同,而第3種方案節(jié)省的乘法器數(shù)量是它們的2倍。若將μ值設(shè)置為2的冪形式,與μ相乘可以利用移位運(yùn)算代替[7],那么上述3種方案所節(jié)省的乘法器數(shù)量是相同的。但是針對自適應(yīng)濾波器的具體應(yīng)用場合,3種方案對自適應(yīng)濾波器的穩(wěn)定性、收斂速度的影響會有差異。

由文獻(xiàn)[6]知第3種方案最受青睞,已被用作自適應(yīng)差分脈沖編碼調(diào)制傳輸?shù)膰H電信聯(lián)盟標(biāo)準(zhǔn),所以本文以它為例進(jìn)行對比分析。圖3給出了分別基于LMS算法和符號LMS算法的自適濾波器的均方誤差曲線圖,這里取L=8,μ=2-7。由圖3可知采用符號LMS算法的自適應(yīng)濾波器的均方誤差收斂速度比采用LMS算法更快,并且更加趨近于零。這主要由于在每次迭代更新中,符號LMS算法進(jìn)行的乘法計(jì)算量相對于LMS算法減少了一半。

圖3　自適應(yīng)濾波器的均方誤差曲線

2　流水線技術(shù)

廣義上講,流水線技術(shù)就是將一個重復(fù)的過程分解為若干子過程,讓每個子過程可以和其他的子過程同時進(jìn)行,是一種并行處理技術(shù)。就FPGA而言,流水線技術(shù)是指將組合邏輯電路的延時路徑進(jìn)行系統(tǒng)性地分級,并且在各個分級之間插入寄存器來暫存中間數(shù)據(jù)。這樣便縮短了信號在一個周期內(nèi)通過組合邏輯電路的延時路徑長度,從而提高了時鐘頻率。對于應(yīng)用最廣泛的同步時序電路而言,其處理速度就是指它的時鐘頻率。時鐘頻率越快,處理數(shù)據(jù)的時間間隔就越短,在單位時間內(nèi)處理的數(shù)據(jù)量就越大,也就提高了處理速度[8]。

圖4形象說明了流水線技術(shù)的基本原理,假設(shè)圖中的組合邏輯電路具有較大的延時,于是將其分割成具有較小延時的組合邏輯電路1和2,并插入2個同步寄存器。這樣組合邏輯電路1和2在同一時間內(nèi)處理的信號就會不同,因?yàn)榻?jīng)過了寄存器的鎖存。2個組合邏輯電路1和2就可以并行執(zhí)行[9]。該圖也說明了流水線技術(shù)實(shí)際上是以增加硬件資源的消耗來換取更高處理速度的。

圖4　流水線技術(shù)基本原理圖

在FPGA中使用流水線技術(shù),需要的額外成本不多,因?yàn)槊總€LE本身就包含一個寄存器和寄存器鏈邏輯。提升基于FPGA的自適應(yīng)濾波器的運(yùn)行速度關(guān)鍵在于提高乘法器的處理速度。由文獻(xiàn)[6]可知,對于FPGA中的一個N位×N位的乘法器,若想達(dá)到最高處理速度,那么需要的流水線級數(shù)是log2(N)。本文自適應(yīng)濾波器輸入信號的位寬設(shè)置成16位,故采用4級流水線時可以充分發(fā)揮流水線技術(shù)的速度優(yōu)勢。

3　FPGA實(shí)現(xiàn)

FPGA是通過采用可編程的查找表(LUT)結(jié)構(gòu)來實(shí)現(xiàn)可編程邏輯的。LE是Cyclone系列FPGA芯片中最基本的可編程單元,主要由一個4輸入的LUT、一個可編程的寄存器、進(jìn)位鏈邏輯和寄存器鏈邏輯構(gòu)成[10]。因此,我們通常使用 在同一時鐘的驅(qū)動下 某信號通過源寄存器至目的寄存器的最短路徑所消耗的最少時間(Tmin或者Fmax)來表示對信號的處理速度,使用設(shè)計(jì)所需LE的總數(shù)量來表示FPGA硬件資源的消耗情況[11-12]。

為了跟本文1.2節(jié)最后的MATLAB仿真實(shí)驗(yàn)保持一致,基于Altera公司CycloneⅢEP3C10U256C8FPGA芯片的自適應(yīng)濾波器仍然設(shè)為8階,收斂因子仍取2-7,系統(tǒng)時鐘clk的頻率設(shè)成數(shù)據(jù)輸入頻率的6倍,自適應(yīng)算法分別采用LMS算法和符號LMS算法。使用超高速集成電路硬件描述語言(VHDL)進(jìn)行對分別基于2種算法的自適應(yīng)濾波器進(jìn)行編程,主要包括初始化模塊,信號輸入模塊,時鐘分頻模塊,權(quán)值更新模塊,誤差計(jì)算模塊,濾波輸出模塊。接著利用QuartusⅡ和ModelSim軟件對它們分別進(jìn)行編譯、綜合、適配、時序分析。設(shè)定x(n)、d(n)、e(n)和y(n)的二進(jìn)制位寬分別是16位,其中x(n)和d(n)的取值是通過對本文1.2節(jié)利用MATLAB仿真時的x(n)和d(n)數(shù)據(jù)進(jìn)行16位量化得到的。

圖5是基于FPGA和LMS算法的自適應(yīng)濾波器的ModelSim時序驗(yàn)證圖,對該自適應(yīng)濾波器進(jìn)行VHDL編程時,沒有使用流水線技術(shù)進(jìn)行優(yōu)化,系統(tǒng)時鐘的最高頻率是76.75MHz,總共消耗了32個嵌入式乘法器。詳細(xì)的資源消耗情況如表1所示。圖5中誤差信號e的波形開始時抖動幅度較大,之后慢慢平緩,該設(shè)計(jì)達(dá)到了預(yù)期效果。

圖5　基于LMS算法的自適應(yīng)濾波器的時序波形圖

圖6是基于FPGA和符號LMS算法的自適應(yīng)濾波器的ModelSim時序驗(yàn)證圖,在VHDL編程時添加了4級流水線對該自適應(yīng)濾波器進(jìn)行優(yōu)化,圖6中誤差信號el的波形開始時抖動幅度很大,隨后漸趨平緩。和圖5中的e波形相比,圖6中el波形的抖動更小,這跟1.2節(jié)中的MATLAB仿真結(jié)果是完全一致的,因此本設(shè)計(jì)是正確的。表1也給出了該自適應(yīng)濾波器的資源消耗情況和處理速度。

圖6　基于LMS算法的自適應(yīng)濾波器的時序波形圖

表1基于2種算法的自適應(yīng)濾波器的資源消耗和速度比較

算法LEsRegistersEmbeddedmultiplierFmax/MHzLMS141213213276．75符號LMS103793916123．93

由表1可知,基于LMS算法的自適應(yīng)濾波器所消耗的LE和寄存器數(shù)量分別比基于符號LMS算法的多了375個和382個,并且前者所消耗的嵌入式乘法器數(shù)量是后者的2倍,但是前者的處理速度卻比后者慢很多。足見基于符號LMS算法的自適應(yīng)濾波器在使用流水線技術(shù)優(yōu)化后的優(yōu)越性,并且這種優(yōu)越性隨著自適應(yīng)濾波器階數(shù)的升高、輸入位寬的增大將更加明顯。

事實(shí)上如果不使用流水線技術(shù)對基于符號LMS算法的自適應(yīng)濾波器進(jìn)行優(yōu)化,那么它所消耗的LE和寄存器數(shù)量分別只有576個和412個,嵌入式乘法器的數(shù)量依然是16個,但此時自適應(yīng)濾波器的處理速度明顯降低。這恰恰印證了本文第2節(jié)中流水線技術(shù)是以面積換取速度的論斷。

4　結(jié)束語

本文首先闡述了自適應(yīng)濾波器常用的LMS算法和改進(jìn)后的符號LMS算法,并且使用MATLAB作了前期對比分析,然后簡述流水線技術(shù),最后將基于LMS算法和符號LMS算法的自適應(yīng)濾波器在FPGA硬件上實(shí)現(xiàn),并且使用流水線技術(shù)對基于符號LMS算法的自適應(yīng)濾波器進(jìn)行了優(yōu)化。QuartusⅡ驗(yàn)證得到了各種資源消耗情況和最高時鐘頻率,ModelSim仿真得到了基于2種算法的自適應(yīng)濾波器的時序波形圖。將實(shí)驗(yàn)數(shù)據(jù)進(jìn)行對比分析,本文采用符號LMS算法和流水線技術(shù)的自適應(yīng)濾波器在資源消耗和運(yùn)行速度方面的確更具優(yōu)勢。

參考文獻(xiàn):

[1]Simon Haykin.自適應(yīng)濾波器原理[M].鄭寶玉,譯.北京:電子工業(yè)出版社,2010:159-238.

[2]高亞軍.基于FPGA的數(shù)字信號處理[M].北京:電子工業(yè)出版社,2012:79-104.

[3]Bernard Widrow,Samuel D Stearns.自適應(yīng)信號處理[M].王永德,龍憲惠,譯.北京:機(jī)械工業(yè)出版社,2008:68-76.

[4]吳高奎.數(shù)字信號處理算法的FPGA高速實(shí)現(xiàn)研究[D].成都:電子科技大學(xué),2011:7-21.

[5]祝燕華,劉建業(yè),賴際舟,等.FOG信號的變步長符號LMS自適應(yīng)消噪方法[J].成都:光電工程.2008,35(11):122-127.

[6]Uwe Meyer-Baese.數(shù)字信號處理的FPGA實(shí)現(xiàn)[M].劉凌,譯.北京:清華大學(xué)出版社,2011:425-468.

[7]Rui Guo,DeBrunner L S.A Novel Adaptive Filter Implementation Scheme Using Distributed Arithmetic[J].IEEE Signals,Systems and Computers,2011(11):160-164.

[8]Pramod Kumar Meher,Sang Yoon Park.High Throughput Pipelined Realization of Adaptive FIR Filter Based on Distributed Arithmetic[J].IEEE Transactions on VLSI and System-on-Chip,2013,60(6):346-350.

[9]潘松,黃繼業(yè),潘明.EDA技術(shù)實(shí)用教程-Verilog HDL[M].北京:科學(xué)出版社,2010:232-236.

[10]楊海鋼,孫嘉斌,王慰.FPGA器件設(shè)計(jì)技術(shù)發(fā)展綜述[J].北京:電子與信息學(xué)報,2010(3):714-723.

[11]張春生,蘇開友.FPGA數(shù)字信號處理與工程應(yīng)用實(shí)踐[M].北京:中國鐵道出版社,2013:149-156.

[12]Stephen Brown,Zvonko Vranesic.數(shù)字邏輯基礎(chǔ)與VHDL設(shè)計(jì)[M].伍微,譯.北京:清華大學(xué)出版社,2011:230-248.

邱陳輝(1988-)男,漢族,江蘇南通人,博士研究生,研究方向?yàn)榛贔PGA的數(shù)字信號處理生物醫(yī)學(xué)信號處理,qch19881114@126.com;

李鋒(1970-)男,漢族,陜西商洛人,博士,副教授,碩士生導(dǎo)師,研究方向?yàn)楣怆娦畔⑻幚?lifengsl@126.com;

徐祖強(qiáng)(1988-)男,漢族,江西贛州人,碩士研究生,研究方向?yàn)閿?shù)字信號處理及其FPGA實(shí)現(xiàn),930233502@qq.com。

DesignofAdaptiveFilterBasedonFPGAandSignum-LMSAlgorithm*

QIUChenhui1,LIFeng2*,XUZuqiang2

(1.The Key Lab of Biomedical Engineering of Ministry of Education,Zhejiang University,Hangzhou 310027,China;2.College of Electronics and Information,Jiangsu University of Science and Technology,Zhenjiang Jiangsu 212003,China)

Abstract:To decrease the consumption of hardware resource of adaptive filter based on FPGA and LMS algorithm,signum-LMS algorithm is proposed.The processing speed of adaptive filter is increased by reducing the number of multiplications and optimized by pipelining technology.Software simulation verifies the feasibility of signum-LMS algorithm.Hardware simulation proves the superiorities of the adaptive filter using the proposed algorithm and pipelining technology.

Key words:digital signal processing;adaptive filter;least mean square(LMS);signum-least mean square(SLMS);field programmable gate array(FPGA);pipelining

doi:EEACC:127010.3969/j.issn.1005-9490.2014.05.023

中圖分類號:TN911.72

文獻(xiàn)標(biāo)識碼:A

文章編號:1005-9490(2014)05-0904-04

收稿日期:2013-10-20修改日期:2013-11-13

項(xiàng)目來源:國家自然科學(xué)基金項(xiàng)目(11204109);國家自然科學(xué)基金項(xiàng)目(51307074)