A Comparison of NLMS & PNLMS Algorithms for Echo Cancellation

A Comparison of NLMS & PNLMS Algorithms for Echo Cancellation

Ms. Dhanashri M. Kadakane

M.E. Student

Dept. of Electronics Engineering

Dr. J. J. Magdum College of Engineering Jaysingpur, Kolhapur,India

Prof. Mrs. A. P. Patil

Assistant Professor, M. E. Electronics, Ph.D (Regd.) Dept. of Electronics Engineering

Dr. J. J. Magdum College of Engineering Jaysingpur, Kolhapur,India

Abstract This paper describes the comparison between adaptive filtering algorithms that is Normalized Least Mean Square (NLMS) and Proportionate Normalized least mean square (PNLMS). Here, the behavior of the both the adaptive algorithms is analyzed. To determine the algorithm with best performance in echo cancellers, the comparison between these algorithms based on Echo Return Loss Enhancement (ERLE), Mean Square Error (MSE) and Computational complexity is carried out using MATLAB. Echo is very annoying problem if it occurs it reduces voice quality. It is quite difficult to remove echo completely but it can be minimized. To overcome this problem many echo cancellers are available from that adaptive filters are one of the best solutions. This paper aims for studying the performance of typical sparse algorithms for echo and noise cancellation. When the echo path is sparse, the conventional Normalized Least Mean Square (NLMS) algorithm suffers from slow convergence. Thus, sparse adaptive filtering algorithms such as PNLMS were introduced to overcome the convergence problem of adaptive filters in sparse impulse response. Simulation results using noise, echo and speech input signal shows better performance of proposed algorithms. The comparison between proposed algorithm NLMS and PNLMS gives these improvements. This paper has propose echo and sparse (noise) cancellation that has been tested and verified by MATLAB.

Keywords: Echo Cancellation, Noise, Adaptive Filter, Adaptive Algorithm, MSE, ERLE, AEC,AIR, NPM,SIR.

1. INTRODUCTION

   In the echo cancellation scheme an adaptive filter place very important role to identify echo path and many filtering algorithms are develop to improve performance of a filter. In the context of echo cancellation, it is shown that the level of sparseness in acoustic impulse responses can vary greatly in a mobile environment. When the response is strongly sparse, convergence of conventional approaches is poor [1]. We have presented echo cancellation algorithms to work for sparse responses, to adapt dynamically with the level of sparseness using a new sparseness-controlled approach.

   The echo response in system is typically of length 64 128 ms and is characterized by a bulk delay dependant on network loading, encoding, and jitter buffer delays [1]. This results in an active region in the range of 812 ms duration and consequently, the impulse response is

   dominated by inactive regions where coefficient magnitudes are close to zero, making the impulse response sparse [1]. The echo canceller must be robust to this sparseness.

   Various sparse adaptive algorithms have been developed specifically to address the performance of adaptive filters in sparse system identification.

   Fig. 1. Adaptive echo Cancellation system

   Figure 1. shows a block diagram of the adaptive echo cancellation system. Here the filter H (n) represents the impulse response of the acoustic environment, w(n) represents the adaptive filter used to cancel the echo signal. The adaptive filter aims to equate its output y(n) to the desired output d(n) (the signal reverberated within the acoustic environment). At each iteration the error signal, e

   (n) =d (n)-y (n), is fed back into the filter, where the filter characteristics are altered accordingly. The aim of an adaptive filter is to calculate the difference between the desired signal and the adaptive filter output, e(n). This error signal is fed back into the adaptive filter and its coefficients are changed algorithmically in order to minimize a function of this difference, known as the cost function. In the case of acoustic echo cancellation, the optimal output of the adaptive filter is equal in value to the unwanted echoed signal. When the adaptive filter output is equal to desired signal the error signal goes to zero. As echo affects on a quality of signal similarly sparse also affects on signal. A sparse impulse response has most of its components with zero or small magnitude and can be found in telephone networks [18]

   Fig. 2. Sparse Impulse Response

   Above Fig 2. Shows example of sparse impulse response. Sparse impulse responses are encountered in several applications, such as in acoustic and digital network echo cancellers [18 ]

   Section 2 describes proposed echo and noise cancellation system. Section 3 gives brief introduction of all steps carried out in this procedure. Section 4 gives introduction to the computational of described algorithms and shows results, observations and comparative study based on parameters. Section 5 defines conclusion and future work.

2. PROPOSED ECHO & NOISE CANCELLATION SYSTEM

   This section describes system which cancels noise and echo present in audio signal. It mainly consists, Audio signal and noise generator, adaptive filter. Each of them is described below,

   subtracted from the combination of echo and noise. This process is repeated until error is reducing to zero. Once the error gets minimized then we get signal from which echo and noise is eliminated at the output side. This signal must have high degree of similarity with original signal.

   Thus we are proposing a class of sparseness- controlled algorithms which will achieve improved convergence compared to normalized least-mean-square algorithm and typical sparse adaptive filtering algorithm such as Proportionate normalized least-mean-square algorithm.

   We are going to incorporate the sparseness measure into sparse adaptive filtering algorithm to achieve fast convergence that is robust to the level of sparseness encountered in the impulse response of the echo path. In the proposed work after comparing algorithms, the algorithm which is robust to variations in the level of sparseness will be selected. Throughout our simulations, algorithm will be tested using a White Gaussian noise and a recorded speech signal as the input.

3. IMPLEMENTATION AND RESULTS

   1. Implementation Steps:

      For both noise and echo cancellation following process is carried out:

      1. Record speech signal (.Wave file) (x(n))

      2. Add Echo signal and corrupt it with the noise signal. (d (n))

      3. Subtract the output signal of adaptive filter y(n) from d(n)

         Where d(n) = Echo signal +Noise signal.

      4. Minimize error signal, it is given by e(n) = d(n)-y(n).

      5. Simulate it in MATLAB and display result in graphical format.

   Data Acquisition

   In this step import is acquired. Input for this filter is nothing but recorded audio signal which can be done by any kind of speech recorder. Or we can use audio signal directly available on internet. This signal is in .wave format. This signal is then processed to add noise and echo.

   Where

   Fig. 3. Block Diagram Of Echo Cancellation

   x(n) is the input recorded signal W0(n) is the echo signal

   x1(n) is the reference input signal

   d(n) = W0(n) +Noise signal y(n) is the filter output e(n) is the error signal. e(n)=d(n)-y(n)

   The system takes record speech is a input signal.

   Fig.4. Graph of input speech signal

   Noise & Echo Addition

   An echo is said to occur when delayed

   This input is passed through cho path so that echo and noise will be added in it. This input signal is also passed through in adaptive filter. The output of filter is then

   and possibly distorted versions of a signal are reflected back to the source of that signal. There are two types of echo:

   1. Acoustic Echo

   2. Hybrid Echo

      Noise is nothing but unwanted undesirable signal which is present in any audio signal. In this step this input audio signal is corrupted with noise and echo. Noise can be added directly in a Matlab program as white Gaussian noise is present in Matlab else recorded or available noise is added in original audio signal. And same procedure is done for echo signal.

      Fig.5. Graph of echo signal and noise signal

      Fig.6. Graph of input signal corrupted with noise and echo

      Error Minimization

      To perform this task error detection is necessary. After error detection it is subtracted from output of second step. This process is repeated until error is minimized.

      The error signal is given by ,

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

      Fig. 7. Graph of detected error

      Filtration Process

      Filtration process is used to remove noise and echo which is present in audio signal. The method used to cancel the echo signal is known as adaptive filtering. Adaptive filter is the most important component of acoustic echo canceller and it plays a key role in acoustic echo cancellation. It performs the work of estimating the echo path of the room for getting a replica of echo signal. It requires an adaptive update to adapt to the environmental change. Another important thing is the convergence rate of the adaptive filter which measures that how fast the filter converges for best estimation of the room acoustic path. For the filtration process sparse

      impulse response is generated. During the conduct of experiments, a sparse impulse response generator is used to provide synthetic sparse impulse response.[1].

      Method of adaptive filtering

      There are number of methods available for adaptive filtering from which NLMS and PNLMS with adaptive filter is referred for this paper.

      NLMS: Normalized Least Mean Square Algorithm

      As the NLMS is an extension of the standard LMS algorithm, the NLMS algorithms practical implementation is very similar to that of the LMS algorithm. It differs in the way of tap weights. This algorithm is used as LMS suffers through noise amplification problem which is overcome by NLMS algorithm. Tap weight is calculated by using Euclidian distance formula.

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

      w(n) is weight vector x(n) is input vector

      µ(n) is step size parameter e(n) is error vector

      PNLMS: Proportionate Normalized Least Mean Square Algorithm

      The PNLMS algorithm have been proposed for sparse system identification. In order to track sparse impulse response faster Proportionate NLMS (PNLMS) was introduced from the NLMS equation. In this algorithm, an adaptive individual step-size is assigned to each filter coefficient. The step-sizes are calculated from the last estimate of the filter coefficients in such a way that a larger coefficient receives a larger increment, thus increasing the convergence rate of that co-efficient [1]. This has the effect that active coefficients are adjusted faster than non-active coefficients.

      Output of NLMS filteration process:

      Output of PNLMS filteration process:

      Fig. 9 . Graph of output signal

      SPARSE IMPULSE RESPONSE GENERATOR

      Sparseness of impulse responses for Network and acoustic echo cancellation can be studied by generating synthetic impulses using random sequences. This can be achieved by first defining an L×1 vector.[1]

      =

      Where the leading zeros with length Lp models the length of the bulk delay and Lu = L Lp is the length of the decaying window which can be controlled by . Smaller the value yields more sparse system.

      Fig.no.8 Examples of SIR for various

      Sparseness Measure:

      Degree of sparseness can be qualitatively referred as a range of strongly dispersive to strongly sparse [1]. Quantitatively, the sparseness of an impulse response can be measured by the following sparseness measure.

      Where 0 (h) 1 and

      L is the length of filter h.

4. PERFORMANCE MEASURES

   The choice of one algorithm over the wide variety of others needs to be addressed to differentiate it from the rest, so that one can pick a right algorithm for his particular application. The following three measures deal with different concepts in applications akin to echo cancellation.

   1. Mean Square Error (MSE)

      MSE is one of the ways to define an objective unction that satisfies the optimality and non-negativity properties [16]. It is the expected value of the square of the error and can be seen from following equation that the lower MSE value is favorable.

      MSE(n) = E{e2(n)}

   2. Echo Return Lossless Enhancement (ERLE)

   It measures the attenuation of the echo signals in an Acoustic Echo Cancellation system. It can be witnessed from following equation that a higher ERLE corresponds to higher reduction in echo.

   ERLE(n)=10*log10 y2(n)/ e2(n) dB

   . Computational Complexity

   It is also necessary to examine the computational complexity of a algorithm. Although many factors contribute to the complexity of an algorithm, the relative complexity of the four algorithms in terms of the total number of additions, multiplications, divisions and logarithms per iteration is assessed.

   The comparison between two numbers takes one subtraction. In this content, subtraction is counted as addition. It can be noticed that the overall computational complexity is increased or stayed same when the improvement is made.

5. SIMULATION RESULTS & COMPUTATIONAL COMPLEXITY

   1. Mean Square Error (MSE)

      Fig.no.10 Combined View of MSE for Both Algorithm

      The above graph shows the mean square error of NLMS & PNLMS algorithm. MSE states that the lower MSE value is favorable. The graph of PNLMS is smoother than NLMS also MSE of PNLMS is lower than NLMS. So PNLMS shows good response for error reduction in signal.

   2. Echo Return Lossless Enhancement (ERLE)

      With the performance measure it is also necessary to examine computational complexity. As we can see from the table that the increase in complexity is compromised by the algorithms performance.The relative complexity of NLMS and PNLMS in terms of the total number of additions (A), multiplications (M), logarithm (Log) and comparisons (C) per iteration is done and that is shown in above table[17]. The above computational Complexity shows the improvements in algorithm. Higher complexity more improvements in results. It can be noticed that the overall computational complexity is increased or stayed same when the improvement is made. Here the computational Complexity of PNLMS is more than NLMS.

      Fig.no.11 Combined View of ERLE for Both Algorithm

      It measures the attenuation of the echo signals in echo cancellation system. It state that a higher ERLE corresponds to higher reduction in echo. Here the graph PNLMS is smoother than NLMS. Here the value of ERLE of PNLMS is higher than value of ERLE of NLMS. That is PNLMS gives the higher reduction of echo signal.

   3. Generated Sparse Impulse Impulse Response

   Fig no.12 Generated Sparse Impulse Response

   The above graph shows generated SIR for =8. It shows for smaller more sparse and vice versa.

   1. omputational Complexity

      	NLMS	PNLMS
      Addition	L+3	2L +5
      Multiplication	2L +3	6L+2
      Division	1	2L+2
      Logarithm	0	0

      Table No.6.1. Computational Complexity of NLMS & PNLMS

6. CONCLUSION and Future Work

   The NLMS algorithm achieves good convergence in dispersive AIRs and for non sparse system. Its response time is less but in case of system containing sparse it shows low convergence. Thus, PNLMS gives the best performance in terms of the measures MSE and ERLE as compared to NLMS adaptive filtering algorithms but at the cost of increased computational complexity PNLMS performs well in sparse impulse response system than NLMS. As we can see from the table that the increase in complexity is compromised by the algorithms performance. Here the computational Complexity of PNLMS is more than NLMS.

   One thing is that NLMS and PNLMS takes more time for execution so this system can be further develop to work in real time environment. Our work done is in offline mode thus it is necessary to implement in real communication world. Some advanced algorithms such as MPNLMS, IPNLMS can be implemented to achieve better convergence for the system containing sparse.

7. REFERENCES

1. J. Radecki, Z. Zilic, and K. Radecka, Echo cancellation in IP networks, in Proc. 45th Midwest Symp. Circuits Syst., 2002, vol. 2, pp. 219222.

2. D. L. Duttweiler, Proportionate normalized least mean square adaptation in echo cancellers, IEEE Trans. Speech Audio Process., vol. 8, no. 5, pp. 508518, Sep. 2000.

3. W. H. Khong, J. Benesty, and P. A. Naylor, stereophonic acoustic echo cancellation: Analysis of the misalignment in the frequency domain, IEEE Signal Process. Lett., vol. 13, no. 1, pp. 3336, Jan. 2006.

4. H. Deng and M. Doroslovacki, Wavelet-based MPNLMS adaptive algorithm for network echo cancellation, EURASIP

   J. Audio, Speech, Music Process. 2007.

5. R. H. Kwong and E. Johnston, A variable step size LMS algorithm, IEEE Trans. Signal Process., vol. 40, no. 7, pp. 16331642, Jul. 1992.

6. Rusu and F. N. Cowan, The convex variable step size (CVSS) algorithm, IEEE Signal Process. Lett., vol.7, no. 9, pp. 256258, Sep.2000.

7. J. Sanubari, A new variable step size method for the LMS adaptive filter, in Proc. IEEE Asia-Pacific Conf. Circuits Syst., 2004, pp. 501504.

8. Schnaufer and W. K. Jenkins, New data-reusing LMS algorithms for improved convergence, in Proc. 27th Asilomar Conf. Signals, Syst., Comput., 1993, pp. 15841588.

9. K. A. G. Robert, A. Soni, and W. K. Jenkins, Low- complexity data reusing methods in adaptive filtering, IEEE Trans. Signal Process., vol. 52, no. 2, pp. 394405, Feb. 2004.

10. W. H. Khong and P. A. Naylor, Selective-tap adaptive algorithms in the solution of the non-uniqueness problem for stereophonic acoustic echo cancellation, IEEE Signal Processing Lett., vol. 12, no. 4, pp. 269272, Apr. 2005.

11. J. Benesty and S. L. Gay, An improved PNLMS algorithm, in Proc. IEEE Int. Conf. Acoustics Speech Signal Processing, vol. 2, 2002, pp. 18811884.

12. G. Egelmeers, P. Sommen, and J. de Boer, Realization of an acoustic echo canceller on a single DSP, in Proc. Eur. Signal Processing Conf. (EUSIPCO96), Trieste, Italy, pp. 3336, Sept. 1996.

13. Deshpande and S. L. Grant, A new multi-algorithm approach to sparse system adaptation, in Proc. Eur. Signal Process. Conf., 2005.

14. Andy W.H. Khong and Patrick A. Naylor Efficient Use Of Sparse Adaptive Filters Department of Electrical and Electronic Engineering, Imperial College London.

15. Radhika Chinaboina, D.S.Ramkiran, Habibulla Khan, M.Usha, B.T.P.Madhav, K.Phani Srinivas & G.V.Ganesh , Adaptive Algorithms For Acoustic Echo Cancellation In Speech processingVol7Issue1/ IJRRAS_7_1_05

16. S. Haykin, Adaptive Filter Theory, 4th edition, Information and System Sciences series. Prentice Hall, 2002.

17. P. Loganathan, A. W. H. Khong, and P. A. Naylor, A Class of sparseness controlled algorithm for echo cancellation, in Proc. Eur. Signal Process. Conf. (EUSIPCO), Lausanne, Switzerland, NOV.2009.

18. Meenal Mahajan, Ranjit Kaur, A Comparative Study of Acoustic Echo Cancellation Algorithms in Sparse Impulse Response, Int. Journal of Engineering Research and Applications ISSN : 2248-9622, Vol. 5, Issue 1, ( Part -6) January 2015, pp.60-63

    Ms. Kadakane Dhanashri M. received B.E.in Electronics in 2010 from TKIET college of engineering,Warana,Kolhapur,Indi

    1. She is a student of M.E. Electronics at Dr.J.J.Magdum College Of Engineering

Jaysingpur ,Kolhapur,India.

.

Prof. Mrs. A. P. Patil received M.E. degree in Electronics and pursuing Ph.D. Degree. Her area of interest is Signal processing. Prof.Patil is currently working as a Assistant Professor at Dr.J.J.Magdum College Of Engineering,Jaysingpur Kolhapur, India. She has published papers in many major journals and conferences.