強(qiáng)建龍,蔡燦輝

(華僑大學(xué)信息科學(xué)與工程學(xué)院,福建廈門361021)

一種改進(jìn)的低復(fù)雜度變步長LMS算法*

強(qiáng)建龍,蔡燦輝

(華僑大學(xué)信息科學(xué)與工程學(xué)院,福建廈門361021)

改進(jìn)型的變步長LMS算法在有效抑制瞬時(shí)噪聲對(duì)經(jīng)典的變步長LMS算法影響的同時(shí),也增加了算法的計(jì)算復(fù)雜度,提高了其硬件實(shí)現(xiàn)的難度。為降低變步長LMS算法的計(jì)算復(fù)雜度,提出了一種步長改變因子與前后兩個(gè)時(shí)刻誤差的乘積成正比的新的變步長LMS改進(jìn)算法,在不增加計(jì)算復(fù)雜度的條件下,有效地抑制了瞬時(shí)噪聲對(duì)迭代步長的影響。仿真結(jié)果表明,提出的算法和現(xiàn)有的變步長LMS算法收斂速度相當(dāng),但其穩(wěn)態(tài)誤差更小,計(jì)算復(fù)雜度也更低,有利于算法的硬件實(shí)現(xiàn)。

最小均方算法 變步長 均方誤差 計(jì)算復(fù)雜度 仿真

0 引 言

最小均方誤差(LMS)濾波算法具有簡單有效、計(jì)算量小、易于實(shí)現(xiàn)等優(yōu)點(diǎn),因此在工程中得到了廣泛的應(yīng)用。LMS算法中的步長因子μ決定抽頭系數(shù)向量在每次迭代中的更新幅度,是影響算法收斂速度的關(guān)鍵參數(shù)。LMS算法的目的是在更新過程中使得抽頭權(quán)向量逼近維納濾波器的抽頭權(quán)向量,因此,更新過程也稱之為學(xué)習(xí)過程。μ決定了LMS算法的收斂速度,同時(shí)直接影響到穩(wěn)態(tài)均方誤差。大的學(xué)習(xí)速率能夠提高算法的收斂速度,但會(huì)加大穩(wěn)態(tài)誤差；反之,如果為了提高穩(wěn)態(tài)性能而采用小的學(xué)習(xí)速率時(shí),收斂速度就會(huì)變慢。兼顧LMS算法的穩(wěn)態(tài)性能和收斂速度最簡單而有效的方法就是在不同的迭代時(shí)期使用不同的學(xué)習(xí)速率,也就是采用變步長學(xué)習(xí)速率。

為此,Kwong和Johnston[1]在1992年提出了標(biāo)志性的變步長(VSS,Variable Step Size)LMS算法,該算法根據(jù)預(yù)測(cè)誤差的平方調(diào)節(jié)學(xué)習(xí)速率。在此基礎(chǔ)上,Aboulnasr等[2]于1997年提出一種改進(jìn)的變步長(MVSS,Modified Variable Step Size)LMS算法,利用相鄰時(shí)刻誤差的互相關(guān)函數(shù)很好地避免了不相關(guān)的噪聲對(duì)迭代步長的影響,但是計(jì)算復(fù)雜度比VSS-LMS也有所增加。Pazaitis等[3]提出的變步長LMS算法利用誤差的峰度控制步長因子,該算法利用了近似高斯信號(hào)的特性,對(duì)于較低高斯噪聲有很好的效果,但該近似在較高的噪聲條件下并不準(zhǔn)確。Mader等[4]提出了最優(yōu)變步長LMS算法,該算法的設(shè)計(jì)是基于每一步迭代中,使得均方權(quán)值偏差(MSD,Mean Square Deviation)的下降達(dá)到最大,其中MSD被定義為E{(ω(n)-ω0(n))2},即當(dāng)前濾波器的抽頭系數(shù)ω(n)與維納-霍夫方程定義的抽頭權(quán)向量的最優(yōu)值ω0(n)之差,然而ω0(n)在迭代過程中是不可知的[5],所以該算法實(shí)用性差。Hwang等[6]提出的VSLMS,利用輸入信號(hào)與誤差乘積的范數(shù)更新步長因子,但計(jì)算復(fù)雜度太高,難以實(shí)現(xiàn)。為了進(jìn)一步提高變步長LMS的性能,文中在VSS-LMS和MVSS-LMS算法的基礎(chǔ)上,提出了一種新的改進(jìn)型變步長LMS算法,根據(jù)當(dāng)前時(shí)刻與前一時(shí)刻誤差能量的幾何平均自適應(yīng)調(diào)整學(xué)習(xí)速率,有效地降低了計(jì)算復(fù)雜度。

1 變步長LMS濾波算法

1.1 LMS自適應(yīng)濾波算法

LMS自適應(yīng)濾波就是根據(jù)估計(jì)誤差的大小自動(dòng)調(diào)節(jié)FIR濾波器的抽頭系數(shù),使其代價(jià)函數(shù)最小的一種算法。設(shè)x(n)是濾波器的輸入向量,y(n)是濾波器的輸出向量,ω(n)是濾波器的抽頭系數(shù),則有

設(shè)d(n)是期望信號(hào),則是濾波器的輸出信號(hào)y(n)與期望信號(hào)d(n)的差e(n)可表示為:

最常用的濾波器設(shè)計(jì)準(zhǔn)則是最小均方誤差(MMSE)準(zhǔn)則,也就是使濾波器實(shí)際輸出與期望響應(yīng)之間的均方誤差最小,其代價(jià)函數(shù)定義為:

濾波器的設(shè)計(jì)就是要找到使J(n)最小的濾波器系數(shù)矩陣ω(n)。采用梯度下降法求解,有

式中[7]:

容易驗(yàn)證,瞬時(shí)梯度向量是真實(shí)梯度向量的無偏估計(jì):

式(7)所示的算法就是Widrow[8]于1960年提出的LMS濾波算法。若μ(n)是常數(shù),則稱之為固定步長LMS濾波算法,否則稱之為變步長LMS濾波算法。

1.2 變步長LMS濾波算法

從式(7)可知,加大步長可以提高收斂速度,但同時(shí)也會(huì)加大穩(wěn)態(tài)誤差；反之,降低步長能減小穩(wěn)態(tài)誤差,但卻會(huì)降低收斂速度。為了提高LMS算法的性能,Kwong和Johnston于1992年提出了一種具有代表性的變步長LMS(VSS-LMS)濾波算法,即在誤差較大時(shí)采用大的迭代步長以提高收斂速度,在誤差較小時(shí)采用小的迭代步長以減小穩(wěn)態(tài)誤差。VSS -LMS濾波算法的步長迭代計(jì)算表達(dá)式如下:

式中,0＜α＜1,γ＞0,μmax≤,μmin=10-5[1], tr(R)是相關(guān)矩陣R的跡,根據(jù)矩陣代數(shù),我們還知道,一個(gè)正方矩陣的跡等于它的對(duì)角元素之和。當(dāng)橫向?yàn)V波器是空域?yàn)V波器時(shí),其M個(gè)輸入端的輸入信號(hào)分別是M個(gè)傳感器的觀測(cè)數(shù)據(jù)。此時(shí),空域?yàn)V波器的輸入信號(hào)向量為u(n)=[u1(n),u2(n),…,uM(n)]是輸入信號(hào)ui(n)的均方值或能量。因此相關(guān)矩陣R的跡等于在濾波器M個(gè)輸入端上測(cè)得的總的輸入能量,也就是[6]

由此可知,tr(R)也就是輸入信號(hào)的能量,這表明使得該算法收斂的條件也可以寫成:

從式(8)可知,噪聲的瞬時(shí)變化對(duì)VSS-LMS濾波算法的迭代步長會(huì)產(chǎn)生較大的影響。為此, Aboulnasr在1997年提出了一種改進(jìn)的變步長LMS濾波算法(MVSS-LMS),在該算法中,步長由平滑后的相鄰時(shí)刻誤差的互相關(guān)函數(shù)控制,算法描述如下:

其中:

這里,α,β,γ均為常數(shù),且β趨近于1,p(n)是誤差自相關(guān)估計(jì)因子。從式(11)、式(12)可知,與Kwong提出的算法相比,Aboulnasr的算法用誤差信號(hào)的自相關(guān)估計(jì)因子p(n)替代誤差函數(shù)e(n)。由于誤差自相關(guān)函數(shù)的變化能滿足期望的迭代步長變化的要求,同時(shí),誤差信號(hào)的自相關(guān)運(yùn)算使得Aboulnasr的算法能較好地避免了在步長迭代過程中不相關(guān)噪聲的影響,因此Aboulnasr的算法在不相關(guān)噪聲背景下具有更好的收斂性能。然而,誤差自相關(guān)估計(jì)因子的計(jì)算增加了算法的計(jì)算復(fù)雜度。

為了強(qiáng)化信號(hào)對(duì)學(xué)習(xí)因子的影響,Hwang[6]從另一個(gè)角度對(duì)VSS-LMS濾波算法進(jìn)行改進(jìn),步長由平滑后的的誤差與輸入的互相關(guān)函數(shù)和誤差能量的乘積控制,算法描述如下:

這里,‖·‖2代表平方歐式范數(shù)操作。該方法通過控制(n),使得步長的變化隨輸入信號(hào)的變化而變化,較好地抑制了不相關(guān)噪聲對(duì)弱信號(hào)的影響。然而該方法需要計(jì)算范數(shù),大大增加了算法的計(jì)算復(fù)雜度。

1.3 所提出的變步長LMS濾波算法

為了減少算法的計(jì)算復(fù)雜度,文中對(duì)式(8)進(jìn)行修改,提出一種簡化的相關(guān)學(xué)習(xí)算法,步長因子迭代過程如下所示:

比較式(8)與式(13)不難看出,所提出的算法是用前一時(shí)刻的誤差能量和當(dāng)前時(shí)刻的誤差能量的幾何平均代替VSS-LMS算法中的當(dāng)前時(shí)刻誤差能量,這樣可以在有效抑制不相關(guān)噪聲的同時(shí),大大降低了計(jì)算復(fù)雜度。

1.4 計(jì)算復(fù)雜度分析

表1給出了是文中所提出的簡化相關(guān)變步長LMS算法迭代步驟,以及所需的乘加次數(shù)。其中,N是濾波器的階數(shù)。

表1 所提出算法迭代步驟Table 1 Iteration steps of the proposed algorithm

表2列出了文中所提出的算法和VSS-LMS、MVSS-LMS以及VSLMS-LMS三個(gè)典型的變步長算法的計(jì)算復(fù)雜度比較數(shù)據(jù)。

表2 典型變步長算法的計(jì)算復(fù)雜度比較Table 2 Comparison on computational complexity of typical variable step size algorithms

實(shí)際應(yīng)用中通常采用的是8階濾波器[9],對(duì)應(yīng)的VSS-LMS、MVSS-LMS、VSLMS-LMS和文中算法所需的乘法次數(shù)分別為20、23、46和20,即文中算法所需的乘法次數(shù)和經(jīng)典的VSS-LMS算法一樣,比MVSS-LMS減少了15%,比VSLMS-LMS減少了130%。上述算法所需的加法次數(shù)分別為17、18、32、17,而文中算法和VSS-LMS一樣,比MVSS-LMS少約6%,比VSLMS-LMS少88%。

2 仿真分析

為了對(duì)文中所提出算法的收斂性能進(jìn)行更為準(zhǔn)確的測(cè)試,采用Monte Carlo方法進(jìn)行仿真,文中采用的是2 000次獨(dú)立運(yùn)行結(jié)果的統(tǒng)計(jì)平均。圖1和圖2是信噪比分別為0 dB和10 dB時(shí)文中算法與幾種典型的變步長LMS算法的均方誤差曲線的仿真對(duì)比圖。其中,各算法的參數(shù)設(shè)置如表3所示。輸入x(n)為正弦信號(hào)與白噪聲的合成,

式中,s(n)為正弦信號(hào)序列,j(n)為均值為0、功率為1的高斯白噪聲,SNR為信噪比(單位為dB)。通過圖1和圖2可以看出文中提出的算法具有最小的穩(wěn)態(tài)均方誤差。

圖1 信噪比為0 dB時(shí)均方誤差曲線Fig.1 Comparison on MSE of various adaptive algorithms(SNR=0 dB)

圖2 信噪比為10 dB時(shí)均方誤差曲線Fig.2 Comparison on MSE of various adaptivealgorithms(SNR=10 dB)

表3 參數(shù)設(shè)置Table 3 Parameter settings

3 結(jié) 語

文中在分析了現(xiàn)有的變步長LMS算法基礎(chǔ)上,提出了一種步長改變因子與前后兩個(gè)時(shí)刻誤差的乘積成正比的新的變步長LMS改進(jìn)算法,能夠在不增加計(jì)算復(fù)雜度的條件下,有效地抑制瞬時(shí)噪聲對(duì)迭代步長的影響。仿真結(jié)果表明,和現(xiàn)有算法相比較,文中提出的算法具有穩(wěn)態(tài)誤差小、計(jì)算復(fù)雜度低等優(yōu)點(diǎn),有利于在乘法器資源有限的FPGA或者DSP上實(shí)現(xiàn)。

[1] KWONG R H,JOHNSTON E W.A Variable Step Size LMS Algorithm[J].Signal Processing,IEEE Transactions on,1992,40(07):1633-1642.

[2] ABOULNASR T,MAYYAS K.A Robust Variable Stepsize LMS-type Algorithm:Analysis and Simulations[J]. Signal Processing,IEEE Transactions on,1997,45(03): 631-639.

[3] PAZAITIS D I,CONSTANTINIDES A G.A Novel Kurtosis Driven Variable Step-size Adaptive Algorithm[J]. Signal Processing,IEEE Transactions on,1999,47(03): 864-872.

[4] MADER A,PUDER H,SCHMIDT G U.Step-size Control for Acoustic Echo Cancellation Filters-an Overview [J].Signal Processing,2000,80(09):1697-1719.

[5] 李寧.LMS自適應(yīng)濾波算法的收斂性能研究與應(yīng)用[D].哈爾濱:哈爾濱工程大學(xué),2009.

LI Ning.Convergence Performance Analysis and Applications of the Adaptive lease Mean Square(LMS)Algorithm [D].Harbin:Harbin Engineering University,2009.

[6] HWANG J K,LI Y P.Variable Step-Size LMS Algorithm with a Gradient-based Weighted Average[J].Signal Processing Letters,IEEE,2009,16(12):1043-1046.

[7] 張賢達(dá).現(xiàn)代信號(hào)處理[M].第2版.北京:清華大學(xué)出版社有限公司,2002:188-199.

ZHANG Xian-da.Modern Signal Processing[M].Second Edition.Beijing:Tsinghua University Publishing Company,2002:188-199.

[8] WIDROW B.Adaptive Signal Processing[M].STEARNS S D.Englewood Cliffs,NJ:Prentice-Hall,1985:75-87.

[9] 劉忠樂,蔡燦輝,強(qiáng)建龍.基于RLS_DGD的查找表更新算法[J].通信技術(shù),2013,46(05):111-114.

LIU Zhong-le,CAI Can-hui,QIANG Jian-long.Lookup Table Update Algorithm based on RLS_DCD[J]. Communications Technology,2013,46(05):111-114.

QIANG Jian-long(1987-),male,graduate student,majoring in mobile communication.

蔡燦輝(1954—),男,博士,教授,主要研究方向?yàn)閳D像處理與信息編碼。

CAI Can-hui(1954-),male,Ph.D.,professor,mainly engaged in image processing and information coding.

An Improved Low Computational Complexity Variable Step Size LMS Algorithm

QIANG Jian-long,CAI Can-hui
(College of Information Science and Technology,Huaqiao University,Xiamen Fujian 361021,China)

Although the modified variable step size LMS algorithm can effectively suppress the instant noise interferences on the step size,its computational complexity is increased.Consequently,the difficulty for the hardware realization is increased.In order to reduce the complexity of the variable step size LMS algorithm,a novel modified variable step size algorithm with step variation proportional to the product of current error and previous error is proposed in this paper.The proposed algorithm can well restrain the instant noise interferences without increasing the computational complexity.The simulation results indicate that compared with the existing variable step size of LMS algorithms,the convergence speed of the proposed algorithm is about the same,but its steady-state error is much smaller.Meanwhile,its computational complexity is lower,and favorable to hardware realization.

LMS(Least Mean Square)algorithm；variable step size；mean squared error；computational complexity；simulation

TN929.5

A

1002-0802(2014)03-0258-04

10.3969/j.issn.1002-0802.2014.03.005

強(qiáng)建龍(1987—),男,碩士研究生,主要研究方向?yàn)橐苿?dòng)通信；

國家自然科學(xué)基金(No.61201264)項(xiàng)目名稱:高敏捷性的融合協(xié)同及部分中繼協(xié)同主用戶檢測(cè)研究

Foundation Item:The key technology of mobile broadband wireless access system research and industrialization(No.61201264)