一種低復雜度的稀疏控制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

◎工程與應用◎