一种低复杂度的稀疏控制MPNLMS算法

吴斌，侯楚林

1.岳阳职业技术学院，湖南岳阳 414000

2.中国人民解放军91872部队

一种低复杂度的稀疏控制MPNLMS算法

吴斌1，侯楚林2

1.岳阳职业技术学院，湖南岳阳 414000

2.中国人民解放军91872部队

1 引言

在网络回声消除器中，通常回波路径是稀疏的，即冲激响应向量大多数元素接近零[1]，因此让那些活跃的系数有更大的更新速度可以提高系统的收敛速度，而基于NLMS算法的传统自适应回声消除器，并未利用网络中回声路径的稀疏特性。为了克服NLMS算法的这一局限性，Duttweiler[2]引入了比例自适应的思想，在此基础上形成了比例归一化最小均方算法（PNLMS）[2]。PNLMS算法在刚开始时收敛速度快，但在之后会趋于平缓，如果网络回声路径的脉冲响应发生色散，则其收敛速度远低于NLMS算法，为此文献[3]基于最速下降理论的步长控制提出了一种优化的比例步长控制，来加快算法的收敛速度（MPNLMS算法）。MPNLMS算法克服了PNLMS算法收敛到最后时速度下降的缺点，但当回声路径发生色散时，会导致算法收敛性能下降。针对回声路径变化带来的影响，文献[4]根据IPNLMS算法[5]原理，提出了稀疏控制MPNLMS算法（SCMPNLMS算法），改善了MPNLMS算法在色散回声路径的性能。然而，SCMPNLMS算法却导致算法运算量的增加，因此研究其简化算法，以解决快速收敛与计算复杂度之间的矛盾就变得十分必要。文献[6-7]应用集员滤波理论降低了NLMS算法和仿射投影算法（APA）的计算复杂度，在该算法中只有当参数估计误差大于给定的误差门限时滤波器系数才进行迭代更新，这样可以在减少原算法运算量的同时，最大程度地保留原算法的收敛性能。但是，这些方法都是针对传统的NLMS算法或APA算法提出的，不能直接应用于SCMPNLMS算法。为此本文利用最小化干扰原理，得出了基于集员滤波的SCMPNLMS算法。理论分析和仿真结果表明所提算法在降低计算复杂度的同时，保持了原算法同样的回声消除性能。

2 MPNLMS算法

根据文献[8]可得MPNLMS算法描述如下：

其中x(k)=[χ(k)χ(k-1)…χ(k-L+1)]T，μ是整体步长参数，δ是防止被零整除保证稳定的调整参数[9]。增益矩阵Q(k)=diag{q0(k)q1(k)…qL-1(k)}是用于调整滤波器独立步长的对角矩阵[10]，Q(k)的对角元素按照如下递归关系式进行计算[8]：

3 SCMPNLMS算法

在实际应用中，可能会因环境的温度等条件变化而使得回声路径的脉冲响应发生色散[12]，此条件下MPNLMS算法以远低于NLMS的速率收敛。为此文献[4]提出了SCMPNLMS算法。文献[4]中用稀疏性系数δ(k)表征了各权值的大小差异，从而反映出回声路径的稀疏性，稀疏性系数δ(k)的值越小，表明向量的稀疏性越好。参照文献[4，13]，可得到δ(k)的量度公式为：

其中λ为遗忘因子。当回声路径发生色散时，稀疏性系数δ(k)减小，MPNLMS算法中ql(k)表达式分母增大，导致算法步长减小，因此可根据IPNLMS算法原理通过调整增益矩阵中的比例控制因子减小回声路径变化造成的影响，同时为防止δ(k)过大带来的噪声放大问题，依文献[12]可令：

表1 三种算法每次迭代所需计算量比较

4 SM-SCMPNLMS算法

SCMPNLMS算法改善了MPNLMS算法回声抵消性能，但从表1可以看出与MPNLMS算法相比，当有大量系数需要更新时，算法的加法和乘法增加较大。为提高SCMPNLMS的实用性，可采用滤波器系数间歇更新的方法，即集员滤波策略。

在集员滤波中，令S表示所有感兴趣的“输入-期望”数据对(X，d)的集合，用可行集Θ表示(X，d)属于S时，所有使输出误差幅度在门限γ内的系数矢量w∈RN+1构成的集合[14-15]，故Θ可表示为：

若用k个“输入-期望”数据对(xi，来收敛滤波器系数，用H(k)表示k时刻输出误差幅度在门限γ内的所有W的集合：

其中，H(k)称为约束集，其边缘是一个超平面。集员滤波算法中，只有当参数估计误差大于给定的误差门限γ时滤波器系数才进行更新，从而有效地减少了滤波器系数的迭代次数。依照集员滤波和最小化干扰原理，算法的目标应是：从一次迭代到下一次迭代中，自适应滤波器的权向量应当以最小方式改变，而且受到更新的滤波器输出所施加的约束。即求解以下约束优化问题：

根据集员滤波理论可知当误差大于给定的误差门限γ时（即w(k)∉H(k)），则滤波器系数w(k)应演进到H(k)的边界，因此要求新的更新系数满足如下约束条件：

根据约束条件式（11），使用拉格朗日乘子方法解上面的约束优化问题，得到：

式中，λ0为拉格朗日乘子。并令其相对于w(k+1)和λ0的梯度为零，可得到：

代入式（13），并引入防止被零整除保证稳定的调整参数δ，可以得到基于集员滤波的SCMPNLMS算法（SM-SCMPNLMS）系数更新公式为：

可得SM-SCMPNLMS算法系数更新过程如下所示。

比较SM-SCMPNLMS算法和SCMPNLMS算法系数更新过程，可知：相对于SCMPNLMS算法，新算法每次迭代仅增加了1次比较运算和a(k)的计算，由式（18）知计算a(k)仅需1次减法和1次除法。但该算法中只有当参数估计误差大于γ时，滤波器系数才进行更新，从而减少了滤波器系数的迭代次数。令L=512，从表1可以看出，新算法减少1次迭代，相对于SCMPNLMS算法则可减少2 565次加（减）法，4 616次乘（除）法，1 023次比较运算和512次对数运算。在实际应用中减少的迭代次数远大于1，因此本文算法能够有效降低SCMPNLMS算法的计算复杂度。

5 仿真分析

为便于控制路径的稀疏性，回波路径采用文献[4]提出的使用一随机系列模拟生成路径脉冲响应。仿真中输入信号源分别为模拟语音信号，模拟语音信号是计算机生成的一段长为2.5 s，采样频率为8 KHz的随机高斯信号。采用均方误差（MSE）收敛曲线和稳态回波返回损失强度ERLE（Echo Return Loss Enhancement）来评价自适应回声抵消算法性能，并将文献[2]提出的PNLMS算法，文献[3]提出的MPNLMS、SPNLMS算法和文献[4]提出的SCMPNLMS算法在回声路径色散、稀疏和突然改变的情况下的MSE、ERLE进行了对比。仿真中L=512，步长均为μ=0.3，SMSCMPNLMS算法中取γ=0.03。图1给出了五种算法在稀疏和色散两种信道下的MSE性能对比；图2给出了五种算法在稀疏和色散两种信道下的ERLE性能对比；图3给出了回声路径在1×104次迭代时由稀疏突然改变为色散时五种算法的ERLE和MSE性能对比。ERLE和MSE均以dB为单位。ERLE数值越高，MSE的数值越低，表明自适应算法性能越优良[16]。

图1 两种路径下的均方误差学习比较曲线

图2 两种路径下的稳态回波返回损失强度比较

图3 路径突变时性能比较

从图1和图2可以看出，在稀疏回声信道下，SMSCMPNLMS算法比PNLMS、SPNLMS算法具有更快的收敛速度，其收敛速度、稳态性能和ERLE值与MPNLMS、SCMPNLMS算法相当；在色散回声路径下，SM-SCMPNLMS算法与SPNLMS、MPNLMS和SCMPNLMS算法相比，稳态性能稍有下降，但具有更快的收敛速度，尤为重要的是其减少了迭代次数，降低了计算量。从图3可以看出，本文算法在减少了计算量的同时，表现出了与SCMPNLMS算法一样良好的回声路径跟踪性能，并具有更快的初始收敛速度。

6 结论

本文提出的算法综合了SCMPNLMS算法收敛快，稳态失调小的特点，并通过采用集员滤波减少了算法的运算量。仿真结果表明，无论是稀疏还是色散信道，该算法都较PNLMS算法和SPNLMS算法有更好的性能。同时，由于该算法的计算量较小，与SCMPNLMS算法比较，在收敛速度和收敛精度相当的情况下，其计算复杂度大大降低，从而具有更好的实时性。

[1]孙永国，何培宇，邓方.一种混合稀疏置零的自适应声回波对消算法[J].四川大学学报，2006，43（2）：330-333.

[2]Duttweiler D L.Proportionate normalized least-mean-squares adaptation in echo cancellers[J].IEEE Trans on Speech Audio Process，2000，8（5）：508-518.

[3]Deng Hongyang，Doroslovacki M.Improving convergence of the PNLMS algorithm for sparse impulse response identification[J].IEEE Signal Processing Letters，2005，12（3）：181-184.

[4]Loganathan P，Khong A W H，Naylor P A.A class of sparsenesscontrolledalgorithmsforechocancellation[J].IEEESignal Processing Letters，2009，17（8）：1591-1601.

[5]Benesty J，Gay L S.An improved PNLMS algorithm[C]//Proceedings of IEEE ICASSP-02，Orlando，USA，2002：1881-1884.

[6]Lee J E，Choi Y S.A low-complexityL∞-norm adaptive filteringalgorithm[J].IEEETransonCircuitsandSystems，2007，54（12）：1092-1096.

[7]Diniz P S R，Braga R P，Werner S.Set-membership affine projection algorithm for echo cancellation[C]//Proceedings of the IEEE International Symposium on Circuits and Systems，Kos，Greece，2006：405-408.

[8]刘立刚，Fukumoto M，张世永.一种变步长Proportionate NLMS自适应滤波算法及其在网络回声消除中的应用[J].电子学报，2010，38（4）：973-978.

[9]马立新，侯楚林.改进的变步长比例仿射投影算法[J].计算机工程与应用，2011，47（28）：131-134.

[10]Abadi M S E，Kadkhodazadeh S.The novel proportionate normalizedsubbandadaptivefilter algorithms for sparse systemidentification[J].InternationalJournalofComputer and Electrical Engineering，2012（4）：577-581.

[11]李跃明，侯楚林.变步长比例仿射投影算法及在回声消除中的应用[J].计算机工程与应用，2012，48（35）：126-130.

[12]Khong A W H，Naylor P A.Efficient use of sparse adaptive filters[C]//Proceedings of ACSSC’06，2006：1375-1379.

[13]Liao Lei，Khong A W H.Sparseness-controlled affine projection algorithm for echo cancelation[C]//Proceedings of the 2nd APSIPA Annual Summit and Conference，2010：355-361.

[14]孙兰清，葛临东，刘锋.基于集员滤波的双归一化数据重用盲均衡算法[J].计算机工程，2008，34（8）：111-113.

[15]刘世刚，葛临东，巩克现.基于集员滤波和数据重用的CMA盲均衡算法[J].吉林大学学报，2009，39（6）：1677-1682.

[16]刘遵雄，王树成.一种新的基于L0的变步长IPNLMS算法[J].计算机仿真，2012，29（11）：166-169.

WU Bin1,HOU Chulin2

1.Yueyang Vocational Technical College,Yueyang,Hunan 414000,China
2.Unit 91872 of PLA,China

Sparseness-controlled adaptive algorithm estimates the sparseness of an impulse response and allocates a higher weighting to the proportionate term in the gain matrix for a relatively more sparse impulse response compared to one which is less sparse.Such that it improves the convergence speed of traditional algorithm.However,the large number of filter coefficients in echo cancellation applications diminishes the usefulness of this algorithm owing to increased complexity.To deal with this problem and improve the computational efficiency,the novel SM-SCMPNLMS algorithm is presented by combining the Sparseness-Controlled law PNLMS algorithm（SCMPNLMS）and the framework of Set-Membership Filtering（SMF）.In SM-SCMPNLMS algorithm,the filter coefficients are updated such that the magnitude of the output estimation error is less than a pre-determined threshold.As a result,the proposed algorithm reduces overall computation complexity significantly due to sparse time update.Simulation results show the new algorithm has an attractive faster converge and echo return lossless enhancement for three situations of sparse,dispersive and varying channels.Furthermore,it reduces the overall computational complexity due to the data-selective feature of the SMF approach.

Mu-Proportionate Normalized Least Mean Square（MPNLMS）;sparseness controlled;set membership filtering; echo cancellation

稀疏控制算法将稀疏性系数加入到步长控制因子递推计算过程中，加速了传统回声消除算法的收敛速度。但其快速收敛与低复杂度是一对矛盾的需求。针对这一矛盾，提出了一种基于集员滤波的稀疏控制MPNLMS算法（SM-SCMPNLMS）。该算法中只有当参数估计误差大于给定的误差门限时滤波器系数才进行迭代更新，从而有效地减少了滤波器系数的迭代次数。在稀疏、色散路径以及路径突变三种环境下进行了仿真，结果表明新算法在降低计算复杂度的同时，表现出了与稀疏控制MPNLMS算法同样优良的收敛速度和稳态回波返回损失强度。

Mu-比例归一化均方误差算法（MPNLMS）；稀疏控制；集员滤波；回波消除

A

TN911

10.3778/j.issn.1002-8331.1212-0256

WU Bin,HOU Chulin.Low complexity sparseness controlled MPNLMS algorithm.Computer Engineering and Applications,2013,49（19）：227-231.

国家自然科学基金（No.61072092）。

吴斌（1971—），男，讲师，研究方向为计算机应用；侯楚林（1975—），男，博士，研究方向为通信信号处理。E-mail：xiaofeixia7806@163.com

2012-12-24

2013-04-11

1002-8331（2013）19-0227-05

CNKI出版日期：2013-04-26http://www.cnki.net/kcms/detail/11.2127.TP.20130426.1018.004.html

◎工程与应用◎