Adaptive Filter Algorithm For Acoustic Echo Cancellation Computer Science Essay
Adaptive Filters are generally implemented in the time domain which works well in most scenarios however in many applications the impulse response becomes too long, increasing the complexity of the filter beyond a level where it can no longer be implemented efficiently in the time domain. An example of where this can happen would be in acoustic echo cancellation applications in hands free telephony. However there exists an alternative solution and that is to implement the filters in the frequency domain. The Discrete Fourier Transform or more specifically the Fast Fourier Transform (FFT) allows the conversion of signals from the time domain to the frequency domain in an efficient manner. Acoustic echo cancellation of the frequency domain adaptive filter is compared with time domain adaptive filter. Again results are compared for both frequency domain and time domain adaptive filters with different step sizes.
Keywords-Adaptive Filter, Acoustic signal, echo canceller, FFT, LMS algorithm, Frequency domain adaptive filters.
An adaptive filter is a digital filter that can adjust its coefficients to give the best match to a given desired signal. When an adaptive filter operates in a changeable environment the filter coefficients can adapt in response to changes in the applied input signals. The job of the adaptive filter is to estimate the characteristics of the echo path, generating the echo and compensate for it. To do this the echo path is viewed as an unknown system with some impulse response and the adaptive filter must mimic this response. Adaptive filters have been used in various aspects of signal processing in recent years. Among the possible applications is the Acoustic Echo Cancellation.
For this purpose an adaptive filter may be used in combination with an FFT. Acoustic echo cancellation is important for audio teleconferencing when simultaneous communication (or full-duplex transmission) of speech is necessary. In acoustic echo cancellation, a measured microphone signal d(n) contains two signals: - the near-end speech signal v(n) - the far-end echoed speech signal dhat(n) The goal is to remove the far-end echoed speech signal from the microphone signal so that only the near-end speech signal is transmitted.
The objective of this paper is the implementation of adaptive filtering algorithms in the frequency domain, with emphasis on their use in "Acoustic Echo Cancellation" problems. It will be necessary to develop simulations of adaptive filtering algorithms in the time and frequency domains and compare them from the point of view of performance and implementation complexity.
The paper is organized as follows. In Section II, the Acoustic echo cancellation concept is outlined and various causes of Acoustic echo along with working of echo cancellation is discussed to some depth. Section III considers the design of time domain adaptive filtering algorithm and some weaknesses of LMS algorithm. Section IV, gives frequency domain adaptive filtering algorithm. For implementation of Fast block LMS algorithm, FFT method is discussed. In Section V the final results for echo cancellation are discussed for both LMS and Frequency domain adaptive filtering algorithms. Finally, Section VI concludes the paper and discusses about the future work.
II. ACOUSTIC ECHO CANCELLATION
Acoustic echo cancellation (AEC) is the technology that makes it possible for remotely located groups to interact via audio link as if they were in the same room.
Figure.1: General setup of AEC
AEC is needed whenever an unhampered, full-duplex conversation is desired between different rooms and the conferencing microphone is able to pick up the audio signal coming from the loudspeaker(s).
A . Cause of Acoustical Echo
In a typical conferencing scenario (Figure 2), audio from room B travels across the phone line or other audio network, through room A, and back across the audio network. Listeners in room B hear their own speech that has been delayed by the round trip across the audio network and through room A. Trying to talk while hearing an echo of one's own voice is very distracting and makes it difficult to have a natural conversation.
ROOM A ROOM B
Figure 2: Typical conferencing scenario.
Removal of the echo is important for effective communications.
AEC has become the standard method of providing full-duplex audio in a conferencing system. AEC is the process of preventing audio that came from a distant site from returning to that site by cancelling it, or removing it from the audio signal picked up by the local microphones. The removal of this audio is done with digital signal processing.
B. Working of Echo Cancellation
While echo cancellation is technically very complex, we can begin by looking at a simplified description of the process:
1. Audio from room B is received by the audio conferencing system in room A.
2. The audio is sampled. The sample is called the echo
3. The audio is then sent to the loudspeakers in room A and the Acoustic Echo Cancellers.
4. Room B audio is picked up by room A microphones along with room A audio.
5. The audio is then sent to the Acoustic Echo Cancellers, which compares the signal to the original sample and removes the room B audio. Only room A audio will be sent to room B, resulting in echo-free audio.
The effectiveness of an echo canceller is measured as Echo Return Loss Enhancement (ERLE). ERLE is a decibel (dB) measurement of the echo canceller and non-linear processing performance. This measures how much loss the echo canceller (or NLP) adds to the transmitted signal to remove echo from the microphone audio. This should measure as a negative dB value.
Echo Return Loss (ERL) is a measurement in dB of acoustic echo loss through decay and absorption as the audio travels from the speaker system to microphone either directly or through reflection. This measurement is affected by the levels at the output to the speakers and
the microphone input sensitivity. Echo cancellation performance is enhanced when there is a measured dB loss of echo at this stage. ERL is affected by the amount of gain at the amplifier powering the PA system as well as by room acoustics, microphone and speaker placement and proximity, and ambient room noise. Higher levels will mean less ERL, which can require the AEC to work harder to try and eliminate the acoustic echo. High microphone gains also can affect ERL.
"Total Echo Reduction" is ERL plus ERLE, and it provides a measure of the overall performance on the particular echo cancellation channel.
III. TIME DOMAIN ADAPTIVE FILTERING
The general set up of adaptive filtering environment is shown in Fig. III.1, where k is the iteration number, x(k) denotes the input signal, y(k) is the adaptive filter output, and d(k) defines the desired signal. The error signal e(k) is calculated as d(k)-y(k). The error is then used to form a performance function or objective function that is required by the adaptation algorithm in order to determine the appropriate updating of the filter coefficients. The minimization of the objective function implies that the adaptive filter output signal is matching the desired signal in some sense.
Figure 3 : General Setup of Adaptive Filters
Adaptive filters are useful 
when the characteristics of a given filter must be variable
when the spectrum of a given signal overlaps with the noise spectrum
if the frequency band occupied by noise is unknown or may vary with time.
In most real world scenarios adaptive filters are realized using Finite Impulse Response (FIR) filters, since they are guaranteed to be stable and are simple to use.
A. Time Domain Adaptive Filtering Algorithm
There are many algorithms used to adjust the coefficients of the digital filter in order to match the desired response as well as possible. The LMS Algorithm is the more successful of the algorithms because it is the most efficient in terms of both storage requirement and indeed computational complexity. The basic LMS algorithm updates the filter coefficients after every sample.
Figure 4: The LMS Algorithm
The simplicity of the LMS algorithm and ease of implementation means that it is the best choice for many real-time systems .
The implementation steps for the LMS algorithm:
Define the desired response. Set each coefficient weight to zero.
For each sampling instant (k) carry out steps (2) to (4):
Move all the samples in the input array one position to the right, now load the current data sample k into the first position in the array. Calculate the output of the adaptive filter by multiplying each element in the array of filter coefficients by the corresponding element in the input array and all the results are summed to give the output corresponding to that data that was earlier loaded into the input array.
Before the filter coefficients can be updated the error must be calculated, simply find the difference between the desired response and the output of the adaptive filter.
To update the filter coefficients multiply the error by Âµ, the learning rate parameter and then multiply the result by the filter input and add this result to the values of the previous filter coefficients.
IV. FREQUENCY DOMAIN ADAPTIVE
It is often the case that signals are represented in the frequency domain to enable the use of discrete transforms that reduce the processing required in signal processing applications for example convolution. Although there are a few transforms between the two domains, the Fourier Transform is the most widespread. The advantages of the Fourier Transform over other transforms include :
The efficiency of the Fast Fourier transform
Adequate representations of data for even short data lengths
More faithful representation of data
Components are sinusoidal and are not distorted when transmitted over linear systems
A high degree of familiarity and thus a lot of development.
Frequency Domain Adaptive LMS Filtering The implementation of the LMS filter in the
frequency domain can be accomplished simply by taking Discrete Fourier Transform(DFT) of both the input data x(n) and the desired signal d(n). The advantage of doing this is due to the fast processing of the signal using Fast Fourier Transform algorithm. However this procedure requires a block-processing strategy, which results in storing a number of incoming data in buffers, and thus some delay is unavoidable .
The simplest approach is as shown in Figure 4.1. The signals are processed by block-by-block format, that is x(n) and d(n) are sequenced into blocks of length M so that
The values of ith block of signals and are Fourier transformed using the DFT to find and where
Figure 5: Frequency Domain Adaptive Filter
During the ith block processing the output in each frequency bin of the adaptive filter is computed by
Where is the kth frequency bin corresponding to the ith update. The error in the frequency domain is
The system output is given by
To update the filter coefficients we use, by analogy to LMS recursion the following recursion:
B. The Fast Block-LMS Algorithm
As regards updating the filter coefficients the Fast LMS algorithm has its basis in its time domain equivalent. One significant difference is that the Fast LMS operates on blocks, introducing some latency to the system. As in the Overlap-Save algorithm N is the length of the impulse response of the unknown system.
Figure 6: Block Diagram for the Fast LMS algorithm
Blocks of size 2N will be taken from the input at a time with 50% overlap as before. W will denote the filter coefficients, which will be initialized to zero and updated after each block. The desired output is obtained. The desired response of the adaptive filter is now known and it will be used to update its coefficients correctly. Similar to the Overlap-Save Algorithm we add N zeros to the start of the input array to ensure correct convolution results.
An input block of size 2N is taken from the input array, U; the FFT of this block is calculated.
Now the Filter output can be computed by multiplying the FFT of the input block, U(k) by the Filter coefficients as updated by the previous iteration of the algorithm.
This is transformed to the time domain by computing the IFFT of the above result.
Due to circular convolution the first half of this result is simply discarded and the second half forms the output of the adaptive filter for the given input block.
The error signal is computed next by means of simple subtraction to calculate the difference between the desired and the actual response.
The error is brought into the frequency domain by adding N zeros to the start of e(n) and by computing a 2N point FFT and the result is called E(k).
The Gradient Constraint
The conjugate of U(k),U'(k) is found and this is multiplied by E(k) and the IFFT of the result is calculated. The second half of this result can be dropped due to circular convolution.
N zeros are now added to the end of what we are left with and the 2N point FFT of the resulting sequence is calculated and the result is multiplied by Î¼ (the step size parameter)
followed by N zeros
This is the filter coefficient update factor, W1(k) and is added to W(k) and this is how the update of the coefficients is conducted.
This newly updated W(k+1) will now be used as the filter coefficients for the next block of input. An error may exist, however as W(k) is updated more often this error will diminish as is indicated in Figure 4.3 which shows the convergence of the filter coefficients to near optimum performance.
The teleconferencing system's user is typically located near the system's microphone which is called here as near end speech signal. Here is what a male speech sounds like at the microphone. A male voice travels out the loudspeaker, bounces around in the room, and then is picked up by the system's microphone; this speech signal is called as far end speech signal. The signal at the microphone contains both the near-end speech and the far-end speech that has been echoed throughout the room. The goal of the acoustic echo canceller is to cancel out the far-end speech, such that only the near-end speech is transmitted back to the far-end listener.
Figure 7: Input signals
Output of Acoustic echo canceller is observed by using time domain adaptive filtering method as well as frequency domain adaptive filtering method as shown in figure 5.2. We can observe that echo can be cancelled in a better way in case of FDAF as compared with LMS filtering
Figure 8: Outputs of LMS and FDAF acoustic echo canceller
Output of Acoustic echo canceller is observed for various values of step size and compared. For LMS with Âµ= 0.025 some echo is still present in the output but if mu is increased to Âµ = 0.3 then it is observed that we can remove echo more. Similarly for FDAF with Âµ = 0.025
We can remove more echo from signal than any other values of Âµ as shown in figure.
Figure 9: Output of LMS acoustic echo canceller for various Âµ.
Figure 10 : Output of FDAF Acoustic echo canceller for various mu.
Since we have access to both the near-end and far-end speech signals, we can compute the echo return loss enhancement (ERLE), which is a smoothed measure of the amount (in dB) that the echo has been attenuated. From figure 5.5, we see that we have achieved about a 30 dB ERLE at the end of the convergence period using FDAF, where as we have achieved about a 10dB ERLE at the end of convergence period using LMS filter.
Figure 11: ERLE for LMS and FDAF
With a larger step size, the ERLE performance is not as good due to the misadjustment introduced by the near-end speech. To deal with this performance difficulty, acoustic echo cancellers include a detection scheme to tell when near-end speech is present and lower the step size value over these periods. Without such detection schemes, the performance of the system with the larger step size is not as good as the former, as can be seen from figure 5.6 ERLE plots.
Figure 12: FDAF ERLE comparison for various Âµ
Figure 13: LMS ERLE comparison for various values of Âµ
Comparison between step size and ERLE for LMS and FDAF:
Step size in LMS
Max ERLE in dB
Step size in FDAF
Max ERLE in dB
From the above table it is clear that for step size of 0.025 ERLE for LMS filter is 14.675 dB where as for FDAF it is 43.8 dB that is we can attenuate more echo using frequency domain adaptive filtering but if we increase step size upto 0.3 then with LMS filtering we can attenuate echo upto 37.5 dB. For LMS algorithm 0.3 is the highest step size for which we can attenuate as large as possible echo, whereas for FDAF 0.025 is the highest step size for which we can attenuate as large as possible echo.
FFT algorithm provides a powerful tool for performing fast convolution and fast correlation. These observations point to a frequency domain method for efficient implementation of the block LMS algorithm. Specifically rather than performing the adaptation in the time domain, the filter parameters are actually adapted in the frequency domain by using the FFT algorithm. In particular the use of overlap-save method is not only responsible for reducing the computational complexity of the implementation, but also it provides a practical basis for improving the convergence rate of the fast block LMS algorithm.
In certain applications such as Acoustic echo cancellation in teleconferencing the adaptive filter is required to have a long impulse response (i.e long memory) to cope with equally long echo duration. When the LMS algorithm is adapted in the time domain, we find that requirement of a long memory results in a significant increase in the computational complexity of the algorithm. FDAF provide a possible solution to the computation complexity problem.
 P. Vaidyanathan, Multirate Systems and Filter Banks,
Prentice Hall, Englewood Cliffs, New Jersey, 1993
 Simon Haykin , Communication Systems" 4th Edition,Wiley
 E.Ifeachor and B.Jervis, "Digital Signal Processing: A
practical Approach" 2nd edition, Prentice Hall.
 Simon Haykin "Adaptive Filter Theory", LPE
 Alexander D. Poularikas and Zayed M. Ramadan.
"Adaptive Filtering Primer with MATLAB",
 IEEE Transactions on Signal Processing, Vol. 39,No.
10, October 1991, On the Complexity of Frequency
Domain Adaptive Filtering, Neil K. Jablon
 M. A. Iqbal and S. L. Grant, "Novel variable step size
NLMS algorithms for echo cancellation," Proc.
ICASSP, pp. 241-244, Mar. 2008.