A Review of Adaptive Algorithms for Acoustic, Echo Cancellation

A Review of Adaptive Algorithms for Acoustic, Echo Cancellation

Priyanka D N

Department of Telecommunication Engineering Siddaganga Institute of Technology

Tumakuru, Karnataka-572 103

Chandrashekar H M

Department of Telecommunication Engineering Siddaganga Institute of Technology

Tumakuru, Karnataka-572 103

Abstract:- Acoustic echo is the major issue involved in telecommunication system, which is actually a delayed and distorted version of sound reflected back to the source. Cancellation of echoes involves the use of acoustic echo cancellers. Echo cancellation is done by using adaptive filters by making use of adaptive filter algorithms. In this review paper, we have studied and discussed few of the previous work done on these algorithms in relation to acoustic echo cancellation. This paper contains the basic review of all such existing algorithms of the acoustic echo cancellation like LMS, LLMS, NLMS, RLS, AAF, and APA. Finally, comparison of above algorithm is given in order to conclude the discussion.

Keywords:- Least Mean Square (LMS), Leaky Least Mean Square Algorithm(LLMS),Normalized Least Mean Square (NLMS), Recursive Least Square (RLS), Average Adaptive Filter(AAF), Affine Projection Algorithm (APA)

1. INTRODUCTION

   Acoustic echo occurs during distorted and delayed version of an original speech signal is reflected back to a source[2]. Echo depends on two parameters: amplitude and time delay of reflected waves. The delay time will be the 1/10th of the time taken by the input speech signal. In general, echoes with appreciable amplitude & larger delay such as 1ms are considered, but if echo generates in such a way that the delay increases more than 20ms then, it becomes increasingly disturbing & objectionable. Thus, echo cancellation is an important aspect in the design of modern telecommunication systems[1]. Mainly there are two types of echoes are generated that is hybrid echo and acoustic echo. The main area of concern in this paper is acoustic echo. Hybrid echo is caused due to the mismatch of impedance in transmission lines whereas, acoustic echo is a kind of noise signal in which, the audio signal is resonated in real environment due to the reflection from surrounding objects, walls, floors or surfaces etc. Here, along with the original required signal the attenuated, time-delayed images of this speech signal is produced which creates disturbance. This type of echo is mainly present in mobile phones.

   For an echo cancellation we use an adaptive filter which iteratively changes its characteristics in order to get a desired output. An adaptive filter, helps to minimize the error function which is the difference between the desired output d(n) and its actual output y(n) by altering its parameters regularly.

   This parameter alteration can be done with the help of various adaptive algorithms discussed in the following sections. The cost function mentioned above is known as the "cost or weight function" of the adaptive algorithm. There are so many algorithms for an adaptive filtering, in this paper we presents a review of adaptive algorithms like Least Mean Square (LMS), Normalized Least Mean Square (NLMS), Leaky Least Mean Square Algorithm (LLMS), Recursive Least Square (RLS), Average Adaptive Filter (AAF), Affine Projection Algorithm (APA).

   An adaptive filter in which it algorithmically changes the parameters in order to decreases a function of the difference between the desired output d(n) and its actual output y(n).This function is termed as the cost function of an adaptive algorithm. This parameter can be changed by using a different adaptive filter algorithms described in the following section. The effectiveness of an echo cancellation is often determined by using the performance of these adaptive filters which is quantified by their convergence rate. The adaptive filter block diagram is as shown in the fig 1. Where x (n) is an input speech signal, d (n) is the echoed signal, e (n) is the error signal and y (n) represents the adaptive filter output. After every iteration e (n) = d (n)-y (n) is produced which is given to the filter as a feedback.

   Adaptive filter

   x(n) y(n) d(n) e(n)

   Fig 1. Block diagram of Adaptive filter

   The rest of the paper is arranged as follows: Section II explains the adaptive filter algorithms. Section III describes the discussion. The conclusion are drawn in section IV

2. OVERVIEW OF ADAPTIE FILTER ALGORITHMS

   1. Least Mean Square Algorithm

      LMS algorithm is initially proposed by Widrow Hoff in 1959. It is used to determine the minimum square estimation and is based on the gradient search technique and steepest descent method. This algorithm is used because of low computational complexity, simplicity and ease of implementation. If x (n) is the input speech signal vector and w (n) is the weight vector of the adaptive filter. Each iterations of the LMS algorithm require these steps in following order:

      1. The adaptive filter output y(n) is given by 1) The adaptive filter output is calculated by

         N 1

         y(n) w(n)x(n i) w(n)T x(n)

         (1)

         N 1

         y(n) w(n)x(n i 0

         • i) w(n)T x(n)

           (7)

           i0

      2. The error signal is given by

      e(n)= d(n) – y(n) (2)

      1. The error signal is given by

         e(n)= d(n) – y(n) (8)

      2. The step size value for the input vector by

      1. The weight vector update equation is given by

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

         (n)

         1

         x(n)T x(n)

         (9)

         Where µ represents the step size and which controls the convergence time. Small value of step size leads to more convergence time and large values of step size which degrades the performance of the adaptive filter and causes an algorithm to diverge.

   2. Leaky Least Mean Square Algorithm

Leaky least mean square is a form of standard least mean square algorithm which differs only in terms of cost function.

When implemented in fixed point operation a leaky factor is added to standard LMS equation to avoid filter coefficients

1. The weight vector update equation is given by w(n+1)=w(n)+µe(n)x(n) (10)

2.4. Recursive Least Square Algorithm

RLS algorithm recursively finds a coefficient of the filter, which reduces a weighted linear least square cost function relating to the input signal. Each iterations of the RLS algorithm require these steps in following order:

1) The adaptive filter output y(n) is given by

divergence. The time varying filter coefficients determines the dynamic range of filter output which is unknown earlier in adaptive filter. The coefficient overflow problem is

N 1

y(n) w(n)x(n i 0

• i) w(n)T x(n)

  (11)

  avoided in LLMS. Each iteration of the LLMS algorithm require these steps in following order:

  1. The adaptive filter output y(n) is given by

  2. The error signal is given by

     e(n)= d(n) – y(n) (12)

  3. The recursive weights are given by

  T

  N 1

  y(n) w(n)x(n i) w(n)

  i 0

  2) The error signal is given by

  x(n)

  (4)

  r(n)=d(n)*x(n) (13)

  4) The gain vector is given by

  1

  e(n)= d(n) – y(n) (5)

  3) The Weight vector update equation is given by

  v(n) d (n) r(n)

  5) The weight vector update equation is given by

  (14)

  w(n 1) (1 ) x(n)e(n)

  2.3. Normalized Least Mean Square Algorithm

  (6)

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

  Firstly, the matrix inversion is essential for the derivation of RLS algorithm, no matrix inversion calculations are required for the implementation, hence reducing the computational complexity of the algorithm. Secondly, unlike

  One of the disadvantages of LMS algorithm is, it contains fixed step size parameters for every iteration. Hence it requires an understanding of statistics of the input speech signal which is rarely obtainable. Therefore to overcome this problem, we make use of an NLMS algorithm. The NLMS algorithm is a continuation of LMS algorithm where it bypasses this issue by finding the maximum step size value. The practical implementation of NLMS algorithm is very much similar to that of the LMS algorithm. Each iterations of the NLMS algorithm require these steps in following order:

  the LMS based algorithms, current variables are updated within the iteration using values from the previous iteration. These two factors must be considered for the implementation of RLS algorithm.

  1. Average Adaptive Filter

     LMS and NLMS is not good choice when convergence rate is at high priority. In order to obtain high convergence rate AAF is used. AAF belongs to stochastic gradient algorithm. Each iterations of the AAF algorithm require these steps in following order:

     1. The adaptive filter output is calculated by 3. DISCUSSION

        N 1

        y(n) w(n)x(n i 0

• i) w(n)T x(n)

  (16)

  This section deals with comparison of different adaptive filter algorithms and the survey of various previous papers

  1. The error signal is given by

     e(n)= d(n) – y(n) (17)

  2. The step size value for the input vector by

     right from the early 90's research work on acoustic echo cancellation has been performed. Table I gives a comparison of various algorithms, N represents the length of the input speech signal and k represents the projection order used in APA algorithm and Table II gives a clear view of various

     (n)

     1

     x(n)T x(n)

     (18)

     successful papers written on various adaptive algorithms used to cancel the acoustic echo. From the computational complexity point of view, we see that LMS, NLMS and APA

  3. The weight vector update equation is given by

  algorithm has less computational speed. So we can say that RLS algorithm is the most computationally complex among

  w(n 1) 1/n

  N

  w(n) 1/n m 1

  x(n)e(n)

  (19)

  the other algorithms. From the convergence point of view, LMS algorithm has weak convergence rate. NLMS, RLS, APA have a better convergence rate.

  In terms of convergence rate AAF is the best algorithm. The

  main drawback is its lesser stability than LMS and NLMS

  1. Affine Projection Algorithm

  The affine projection algorithm is an intermediate algorithm in between two well-known algorithms like NLMS and RLS. In APA, a high projection order leads to a fast convergence rate but a large estimation error. Meanwhile, a low projection order gives rise to a slow convergence rate but a small estimation error. Each iterations of the AAF algorithm require these steps in following order:

  1. The adaptive filter output is calculated by

     Table I. COMPARISON OF DIFFERENT ADAPTIVE ALGORITHMS

     N 1

     y(n) w(n)x(n i 0

• i) w(n)T x(n)

(20)

1. The error signal is given by

   e(n)= d(n) – y(n) (21)

2. The weight vector update equation is given by

   w(n) w(n 1) x(n)(x T (n)x(n) I)1e(n)

   (22)

   Where is small constant, is taken in the range of 0<

   2. This equation is a generalization of the NLMS and the RLS algorithms. If N=1 the algorithm becomes NLMS algorithm where n

   is the number of samples, N is the adaptive filter length and if N=n it is equivalent to the RLS algorithm. One of the ways in which LMS and APA algorithms can be compared is that, LMS algorithm calculates the error, as the performance of the last updated echo estimate vector based on current input vector, whereas APA algorithm calculates the error as the performance of the last updated echo estimate vector based on the previous N input vectors.

   Table II. ANAL YSIS OF SIGNIFICANT RESEARCH WORKS ON AEC ALGORITHMS

   Sl no. Paper title Proposed Model Results Remarks

   1. Echo Cancellation

Using LMS

Algorithm[1]

2.

Adaptive Echo Canceller Using a Modified LMS Algorithm [16]

3.

An Approach for Echo cancellation System

1. Based on improved NLMS Algorithm [17]

   5.

   An Improved Proportionate NLMS Algorithm Based On The

   10 Norm [18]

   6.

   RLS Algorithm For

   Acoustic Echo cancellation [5]

   Robust fast affine projection algorithm for acoustic echo cancellation[6]

   LMS algorithm is developed to

   reduce echo and a hardware real

   time implementation of the algorithm is done

   An echo canceller is presented,

   using an adaptive filter with a

   modified LMS algorithm, where

   this modification is achieved

   coding error on conventional

   LMS algorithm

   A novel

   implementation method

   for NLMS adaptive filter is presented based on sliding window structure and algorithm

   delay control technique.

   IPNLMS algorithm based on the

   10 norm is developed, which represents a better measure of sparseness than the II norm.

   An RLS algorithm to reduce

   unwanted echo, is proposed

   which increases communication quality.

   The FAP algorithm provides significant computational savings, so that it requires only slightly more computational power than the NLMS. It uses a

   Sliding-window fast

   RLS method

   The LMS algorithm provides good numerical stability and its hardware requirements are low, therefore being the best choice on the available hardware

   platform. A

   disadvantage of this algorithm is its weak convergence

   The CE-LMS

   algorithm lets an easy digital design due to reduction of floating point operations, because input and error signals are integer numbers. The simulation results show that Mean Square Error of Coded Error LMS(CE-LMS)

   is less than LMS.ERLE analysis for LMS & NLMS shows that CELMS provides better echo loss than LMS.

   Test result shows that the processing time needed for one frame by the sliding widow BNLMS adaptive filter is 9ms, while 35ms by the conventional NLMS adaptive filter. Computational complexity of NLMS adaptive filter is reduced significantly by this new method without performance degrading.

   IPNLMS- 10

   algorithms shows better performance than the normal lPNLMS for both sparse and quasi- sparse impulse responses, the input signal being a white Gaussian noise. The tracking capabilities of the algorithm is also very good.

   The RLS algorithm directly considers the values of previous error estimations. RLS algorithms are known for excellent performance when working in time

   varying environments and converge much faster than the LMS algorithm in stationary environment

   Robust FAP algorithm was formulated, which is supposed to be robust even if implemented in

   fixed-point arithmetic and Furthermore, it is an computationally very efficient.

   This paper mainly focused on the

   LMS algorithm &its use to cancel

   Echo

   This paper focused on the modified LMS algorithm using Coding Error which does not affect the filter structure and is compatible with the existent digital adaptive filters.

   This paper gave importance on

   increasing the processing efficiency of real time systems

   by proposing the BNLMS algorithm.

   IP-NLMS algorithm uses the 10 norm to exploit the sparseness of the system that needs to be identified.

   This paper focuses on the least square values of the error. It has the greatest attenuation of any algorithm, and converges much faster

   than the LMS algorithm. But then this performance comes

   at the cost of computational complexity.

   This paper tells an algorithm that has a better convergence rate than the NLMS algorithm and would still be economical and robust to implement, i.e., the algorithm is

   computationally efficient and not have fixed-point instability problems.

   1. CONCLUSION

      In this paper we have presented the review of different approaches for an acoustic echo canceller design methods using adaptive filter algorithms. Acoustic echo cancellation has its wide range of applications such as in mobile phone, speakerphones, hand free car fits, Bluetooth accessories, hearing heads and multi-channel teleconferencing systems due to advancement in technology.

      The main aim of adaptive algorithm is to lower the mean square error at the cost of higher convergence rate and lesser computational complexity. LMS algorithms is ease for implementation but lesser convergence speed,in NLMS algorithm it has lesser stability and higher convergence speed, in RLS algorithm complexity increases with minimum square estimation and in APA echo return losses is more and has an more convergence speed. We also conclude that each algorithm has its own pros and cons, so they should be applied according to the demand of the situation.

   2. REFERENCES

1. Sheng Zhang, Jiashu Zhang, and Hongyu Robust variable step size decorrelation normalized least-mean-square and its application to acoustic echo cancellation IEEE Signal Process. Mag., Vol. 29 No 4PP. 6180, Jul. 2012.

2. Fabián R. Jiménez L., Camilo E. Pardo B.,and Edgar A. Gutiérrez

   C. Analysis Performance of Adaptive Filters for System Identification implemented over TMS320C6713 DSP Platformpresented at IEEE International Conf.on Digital Signal Processing, Vol.978, PP.4673- 9461,Jan2015.

3. Sanjay K.Nagendra and Vinay Kumar.S.B Echo Cancellation in Audio Signal using LMS Algorithm National Conference on,Recent Trends in Engineering & Technology13-14 May 2011.

4. Fredric Lindstrom ,Christian Sch uldtand and Ingvar Claesson Efficient Multichannel NLMS Implementation for Acoustic Echo Cancellation EURASIP Journal on Audio Processing 2007.

5. Leonardo Rey Vega, Hernán Rey, Jacob Benesty, and Sara Tressens A Fast Robust Recursive Least-Squares Algorithm IEEE Transactions On Signal Processing, Vol. 57, No. 3, March 2009.

6. Rajul Goyal Dr. Girish Parmar and Pankaj Shukla Application of Affine Projection Algorithm in Adaptive Noise Cancellation International Journal of Engineering Research & Technology (IJERT) Vol. 3 Issue 1, January 2014.

7. Sahar Mobeen, Iram Baig,and Anum Rafique Comparison Analysis Of Multi-Channel Echo Cancellation Using Adaptive Filters IEEE International Conference on Open Source Systems and Technologies (ICOSST) 2015.

8. WU Chao, JIANG Kaiyu, WANG Xiaofei, GUO Yanmeng, FU Qiang and YAN Yonghong A Robust Step-Size Control Technique Based on Proportionate Constraints on Filter Update for Acoustic Echo Cancellation Chinese Journal of ElectronicsVol.25, No.4, July 2016.

9. Rajeshwar Dass, Sandeep Performance Analysis of Acoustic Echo Cancellation Techniques Int. Journal of Engineering Research and Applications2248-9622, Vol. 4, Issue 7 July 2014.

10. Nitika Gulbadhar ,Shalini Bahel and Harmeet Kaur Acoustic Echo Cancellation using LMS Algorithm International Journal of Electronics,Electrical and Computational System 2348-117X Volume 5, Issue 5 May 2016

11. Shadab Ahmad, Tazeem Ahmad Shadab Ahmad, Tazeem Ahmad International Journal of Scientific Engineering and Technology Volume No.1, Issue No.4, pg : 46-48 Oct. 2012 Vladimir M. Matic and Srdan N. Abadzic, "Acoustic and line echo cancellation using adaptive filters", 15th Telecommunications forum TELFOR. pp.322-325, November 2007.

12. S. Theodoridis, "Adaptive filtering algorithms", in Proc. iEEE IMTC, vol. 3, pp. 1497-1501, May 2001.

13. Farhang-Boroujeny, Adaptive Filters. Theory and Applications, John Wiley and Sons, New York, 1999.

14. Amit Munjal, Vibha Agarwal, Gurpal Singh, " RLS Algorithm for Acoustic Echo Cancellation", Proceedings of 2nd National Conference on Challenges & Opportunities in information Technology, pp.299-303, March 2008.

15. Srinivasaprasath Ragavendran, "Implementation of Acoustic Echo Canceller Using Matlab", Master's Thesis, University Of South Florida, Oct.2003.

16. J. Velazquez Lopez, Juan Carlos Sanchez and Hector Perez Meana, "Adaptive Echo Canceller Using a Modified LMS Algorithm", 2nd international Conference on Electrical and Electronics Engineering, pp.93-96, September 2005.

17. Kun Shi, Xiaoli Ma, and G. Tong Zhou, "Acoustic Echo Cancellation Using a Pseudo coherence Function in the Presence of Memory less Nonlinearity", IEEE Transactions On Circuits And Systems-I: Regular Papers, vol. 55, no. 9, pp. 2639-2649, October 2008.

18. Ted,S.Wada,and Biing-Hwang Juang, "Enhancement of Residual Echo for Robust Acoustic Echo Cancellation", iEEE Transactions On Audio, Speech, And Language Processing, vol. 20, no. I, pp.175-189, January 2012.