一种改进的低复杂度变步长LMS算法*

强建龙,蔡灿辉

(华侨大学信息科学与工程学院,福建厦门361021)

一种改进的低复杂度变步长LMS算法*

强建龙,蔡灿辉

(华侨大学信息科学与工程学院,福建厦门361021)

改进型的变步长LMS算法在有效抑制瞬时噪声对经典的变步长LMS算法影响的同时,也增加了算法的计算复杂度,提高了其硬件实现的难度。为降低变步长LMS算法的计算复杂度,提出了一种步长改变因子与前后两个时刻误差的乘积成正比的新的变步长LMS改进算法,在不增加计算复杂度的条件下,有效地抑制了瞬时噪声对迭代步长的影响。仿真结果表明,提出的算法和现有的变步长LMS算法收敛速度相当,但其稳态误差更小,计算复杂度也更低,有利于算法的硬件实现。

最小均方算法 变步长 均方误差 计算复杂度 仿真

0 引 言

最小均方误差(LMS)滤波算法具有简单有效、计算量小、易于实现等优点,因此在工程中得到了广泛的应用。LMS算法中的步长因子μ决定抽头系数向量在每次迭代中的更新幅度,是影响算法收敛速度的关键参数。LMS算法的目的是在更新过程中使得抽头权向量逼近维纳滤波器的抽头权向量,因此,更新过程也称之为学习过程。μ决定了LMS算法的收敛速度,同时直接影响到稳态均方误差。大的学习速率能够提高算法的收敛速度,但会加大稳态误差；反之,如果为了提高稳态性能而采用小的学习速率时,收敛速度就会变慢。兼顾LMS算法的稳态性能和收敛速度最简单而有效的方法就是在不同的迭代时期使用不同的学习速率,也就是采用变步长学习速率。

为此,Kwong和Johnston[1]在1992年提出了标志性的变步长(VSS,Variable Step Size)LMS算法,该算法根据预测误差的平方调节学习速率。在此基础上,Aboulnasr等[2]于1997年提出一种改进的变步长(MVSS,Modified Variable Step Size)LMS算法,利用相邻时刻误差的互相关函数很好地避免了不相关的噪声对迭代步长的影响,但是计算复杂度比VSS-LMS也有所增加。Pazaitis等[3]提出的变步长LMS算法利用误差的峰度控制步长因子,该算法利用了近似高斯信号的特性,对于较低高斯噪声有很好的效果,但该近似在较高的噪声条件下并不准确。Mader等[4]提出了最优变步长LMS算法,该算法的设计是基于每一步迭代中,使得均方权值偏差(MSD,Mean Square Deviation)的下降达到最大,其中MSD被定义为E{(ω(n)-ω0(n))2},即当前滤波器的抽头系数ω(n)与维纳-霍夫方程定义的抽头权向量的最优值ω0(n)之差,然而ω0(n)在迭代过程中是不可知的[5],所以该算法实用性差。Hwang等[6]提出的VSLMS,利用输入信号与误差乘积的范数更新步长因子,但计算复杂度太高,难以实现。为了进一步提高变步长LMS的性能,文中在VSS-LMS和MVSS-LMS算法的基础上,提出了一种新的改进型变步长LMS算法,根据当前时刻与前一时刻误差能量的几何平均自适应调整学习速率,有效地降低了计算复杂度。

1 变步长LMS滤波算法

1.1 LMS自适应滤波算法

LMS自适应滤波就是根据估计误差的大小自动调节FIR滤波器的抽头系数,使其代价函数最小的一种算法。设x(n)是滤波器的输入向量,y(n)是滤波器的输出向量,ω(n)是滤波器的抽头系数,则有

设d(n)是期望信号,则是滤波器的输出信号y(n)与期望信号d(n)的差e(n)可表示为:

最常用的滤波器设计准则是最小均方误差(MMSE)准则,也就是使滤波器实际输出与期望响应之间的均方误差最小,其代价函数定义为:

滤波器的设计就是要找到使J(n)最小的滤波器系数矩阵ω(n)。采用梯度下降法求解,有

式中[7]:

容易验证,瞬时梯度向量是真实梯度向量的无偏估计:

式(7)所示的算法就是Widrow[8]于1960年提出的LMS滤波算法。若μ(n)是常数,则称之为固定步长LMS滤波算法,否则称之为变步长LMS滤波算法。

1.2 变步长LMS滤波算法

从式(7)可知,加大步长可以提高收敛速度,但同时也会加大稳态误差；反之,降低步长能减小稳态误差,但却会降低收敛速度。为了提高LMS算法的性能,Kwong和Johnston于1992年提出了一种具有代表性的变步长LMS(VSS-LMS)滤波算法,即在误差较大时采用大的迭代步长以提高收敛速度,在误差较小时采用小的迭代步长以减小稳态误差。VSS -LMS滤波算法的步长迭代计算表达式如下:

式中,0＜α＜1,γ＞0,μmax≤,μmin=10-5[1], tr(R)是相关矩阵R的迹,根据矩阵代数,我们还知道,一个正方矩阵的迹等于它的对角元素之和。当横向滤波器是空域滤波器时,其M个输入端的输入信号分别是M个传感器的观测数据。此时,空域滤波器的输入信号向量为u(n)=[u1(n),u2(n),…,uM(n)]是输入信号ui(n)的均方值或能量。因此相关矩阵R的迹等于在滤波器M个输入端上测得的总的输入能量,也就是[6]

由此可知,tr(R)也就是输入信号的能量,这表明使得该算法收敛的条件也可以写成:

从式(8)可知,噪声的瞬时变化对VSS-LMS滤波算法的迭代步长会产生较大的影响。为此, Aboulnasr在1997年提出了一种改进的变步长LMS滤波算法(MVSS-LMS),在该算法中,步长由平滑后的相邻时刻误差的互相关函数控制,算法描述如下:

其中:

这里,α,β,γ均为常数,且β趋近于1,p(n)是误差自相关估计因子。从式(11)、式(12)可知,与Kwong提出的算法相比,Aboulnasr的算法用误差信号的自相关估计因子p(n)替代误差函数e(n)。由于误差自相关函数的变化能满足期望的迭代步长变化的要求,同时,误差信号的自相关运算使得Aboulnasr的算法能较好地避免了在步长迭代过程中不相关噪声的影响,因此Aboulnasr的算法在不相关噪声背景下具有更好的收敛性能。然而,误差自相关估计因子的计算增加了算法的计算复杂度。

为了强化信号对学习因子的影响,Hwang[6]从另一个角度对VSS-LMS滤波算法进行改进,步长由平滑后的的误差与输入的互相关函数和误差能量的乘积控制,算法描述如下:

这里,‖·‖2代表平方欧式范数操作。该方法通过控制(n),使得步长的变化随输入信号的变化而变化,较好地抑制了不相关噪声对弱信号的影响。然而该方法需要计算范数,大大增加了算法的计算复杂度。

1.3 所提出的变步长LMS滤波算法

为了减少算法的计算复杂度,文中对式(8)进行修改,提出一种简化的相关学习算法,步长因子迭代过程如下所示:

比较式(8)与式(13)不难看出,所提出的算法是用前一时刻的误差能量和当前时刻的误差能量的几何平均代替VSS-LMS算法中的当前时刻误差能量,这样可以在有效抑制不相关噪声的同时,大大降低了计算复杂度。

1.4 计算复杂度分析

表1给出了是文中所提出的简化相关变步长LMS算法迭代步骤,以及所需的乘加次数。其中,N是滤波器的阶数。

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

表2列出了文中所提出的算法和VSS-LMS、MVSS-LMS以及VSLMS-LMS三个典型的变步长算法的计算复杂度比较数据。

表2 典型变步长算法的计算复杂度比较Table 2 Comparison on computational complexity of typical variable step size algorithms

实际应用中通常采用的是8阶滤波器[9],对应的VSS-LMS、MVSS-LMS、VSLMS-LMS和文中算法所需的乘法次数分别为20、23、46和20,即文中算法所需的乘法次数和经典的VSS-LMS算法一样,比MVSS-LMS减少了15%,比VSLMS-LMS减少了130%。上述算法所需的加法次数分别为17、18、32、17,而文中算法和VSS-LMS一样,比MVSS-LMS少约6%,比VSLMS-LMS少88%。

2 仿真分析

为了对文中所提出算法的收敛性能进行更为准确的测试,采用Monte Carlo方法进行仿真,文中采用的是2 000次独立运行结果的统计平均。图1和图2是信噪比分别为0 dB和10 dB时文中算法与几种典型的变步长LMS算法的均方误差曲线的仿真对比图。其中,各算法的参数设置如表3所示。输入x(n)为正弦信号与白噪声的合成,

式中,s(n)为正弦信号序列,j(n)为均值为0、功率为1的高斯白噪声,SNR为信噪比(单位为dB)。通过图1和图2可以看出文中提出的算法具有最小的稳态均方误差。

图1 信噪比为0 dB时均方误差曲线Fig.1 Comparison on MSE of various adaptive algorithms(SNR=0 dB)

图2 信噪比为10 dB时均方误差曲线Fig.2 Comparison on MSE of various adaptivealgorithms(SNR=10 dB)

表3 参数设置Table 3 Parameter settings

3 结 语

文中在分析了现有的变步长LMS算法基础上,提出了一种步长改变因子与前后两个时刻误差的乘积成正比的新的变步长LMS改进算法,能够在不增加计算复杂度的条件下,有效地抑制瞬时噪声对迭代步长的影响。仿真结果表明,和现有算法相比较,文中提出的算法具有稳态误差小、计算复杂度低等优点,有利于在乘法器资源有限的FPGA或者DSP上实现。

[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自适应滤波算法的收敛性能研究与应用[D].哈尔滨:哈尔滨工程大学,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] 张贤达.现代信号处理[M].第2版.北京:清华大学出版社有限公司,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] 刘忠乐,蔡灿辉,强建龙.基于RLS_DGD的查找表更新算法[J].通信技术,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—),男,博士,教授,主要研究方向为图像处理与信息编码。

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

强建龙(1987—),男,硕士研究生,主要研究方向为移动通信；

国家自然科学基金(No.61201264)项目名称:高敏捷性的融合协同及部分中继协同主用户检测研究

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