least mean square algorithm

ABSTRACT

Telecommunications is communication between two people from different areas. This communication is transferred as signals through wires. The signals of callers from one area are transmitted to nearest exchange and that is transferred to exchange near receiver by a two wire transmitter. In long distance communication hybrid is used to convert a two wire to four wire transmitter. Due to this change, impedance mismatching occurs. An echo will appear at the receiver end hybrid and it is received back to caller. This will create a problem to the caller and sometimes problem for receiver. This hybrid echo sometimes even cut the lines of the callers.

The technology is increasing day-by-day, but this problem is also increasing day-by-day.
problem is cannot avoided.

To avoid this problem there is one of many solutions. That is, we can use adaptive filters.
These adaptive filters can stop the echo coming from callers end.

The basic principle involved in this process is the ‘LMS Algorithm’.
The ‘Least Mean Square Algorithm’ is used in adaptive filters to create a replica of the echo signal which is added with the speech signal. This replica is transmitted through the wires in the direction opposite to the echo signal. Since the values of both echo signal and replica signal are equal and with opposite sign, they both signals gets cancel and the remaining signal i.e., the speech signal is transmitted to the destination.

Thus we can remove the echo from the hybrid telecommunication network.

INTRODUCTION

In the Electrical Engineering building at Mississippi State University, Simrall, there are three large, four story stairwells. These stairwells are extremely and sustain a low frequency noise for long periods of time (~10 seconds). The reverberation is, in fact, so bothersome that conversations must be suspended while traversing the halls because the conversation quickly deteriorates. The frequencies amplified by the room are mostly at the lower end of the audio spectrum, as would be expected from a large cavernous room. There are several ways that the reverberating action of a large space can be reduced. One option is to install baffles and other types of physical damping to the room. Using physical methods is most appropriate for high frequencies since the size and weight requirements of low frequency baffles tend to outweigh their usefulness. This project focused on echo cancellation, starting with the elimination of a computer-simulated echo.This first stage consisted of the development of versatile echo cancellation code using the least mean square adaptive filtering algorithm described below. Adaptive filtering examines an input, attempts to cancel it, and adjusts the filter coefficients of an FIR filter to compensate for the error. This code was tested by inputting artificial sound files with simple impulse responses, and canceling the echo through adaptive filtering techniques. Upon completion of the simulated echo cancellation phase, the parameters were modified to handle real signals recorded in the Simrall stairwell. These modifications consisted mainly of increasing the tap length and reducing the error correction step size.





TECHNOLOGY TODAY
Hardware/Software:

Since there are many different applications for echo cancellation, there are naturally many different types of hardware and software available to the DSP engineer. Most of the echo cancellation software and hardware developed thus far has been developed primarily for telecommunications. Echo cancellation on the phone lines has been necessary for many years, due to the relatively long signal paths introduced by satellite and long terrestrial connections, to provide quality service. Other uses for echo cancellation technology include new and rising fields such as audio/video conferencing. Texas Instruments (TI) is a major provider of digital signal processors, namely the TMS320 family.

Current Research

In addition to these hardware and software implementations there is still applied research in makingthe algorithms smarter, less memory intensive, and less computationally expensive. There are several ways to reduce the computational complexity of echo cancellation algorithms including block adaptive filters, subband filtering, and frequency domain adaptive filters. Both the subband method and the frequency domain method not only are more computationally efficient but also converge faster than the standard LMS algorithm. The problem with each of these methods is that they both introduce a delay in the processing and that they typically lack the ability to track a changing impulse response. In order to overcome these problems, the fast Newton transversal filter algorithm has been recently proposed. The key to better computational efficiency in this approach is the fact that the prediction part of the filter can be of lower order than the size of the filter. The LMS algorithm has been used extensively in acoustic echo cancellation even though it does not converge very well with speech signals. In cases such as mobile radio where fast convergence is necessary, the FNTF algorithm is better suited. The reason that fast convergence is needed with mobile radio is that the echo path is constantly changing, thus requiring the filter coefficients to be updated continually. However due to the high noise usually encountered in mobile radio environments, the adaptation can only be allowed when there is a high SNR--generally occurring in short bursts. So, a fast converging algorithm will enhance the performance of the echo cancellation.

Where Does the Echo Come From?

The echo (also known as electric or hybrid echo) is created by the electrical circuitry connected to the wire lines.

Let us first see a simplified version of a network with two abonents. On the Figure 1 you can see the network using 2-wire lines to connect the abonents’ phones with the switching station. Each of the 2-wire lines between a phone and the switching station carries voice signals in both directions, e.g. from one phone to the other through the station and back. The switching station provides the power supply to feed the microphones and the switching functionality, which is needed if there are more than two abonents. The 2-wire lines are obviously cheaper than the 4-wire lines and this is why the regular phones and switching stations were designed to operate with each other over 2-wire lines. The above network is indeed simple and it can operate very well provided the distance between the abonents is short.

Now, if we want to make calls between very distant abonents, we need to do something about the signals because of their attenuation in the long analog lines. So, we need to amplify the signals. But we can’t just amplify what is being sent and received over the 2-wire line because there are both signals coming in both directions at the same time. The solution to this is amplification of separated send and receives signals from the 2-wire line. Such a separation is performed by a dedicated electrical device, called a hybrid. The hybrid basically provides a conversion between 2-wire and 4-wire lines (the switching stations are now connected with 4- wire lines). If instead of the 4-wire analog lines we use digital channels, we also need to separate the signals so they can be independently digitized and efficiently compressed before transmission. Digital transmission improves the quality of the calls and increases the capacity of the phone networks, which leads to a more efficient use of the network equipment and allows more abonents.

Let us now see a phone network connecting the distant abonents:

Now, the interesting part is the hybrid performance because it is the hybrid where the echo can and, in fact, is created. Ideally, the hybrid should just have a sum of the send and receive signals the 2-wire side and these same signals separated on the there are things like spread of equipment parameters and mismatch of line impedances, which allcontribute to imperfect signal.

So part of the signal being sent to the hybrid on the 4-wire side is returned back as the echo superimposed on the signal being received from the hybrid on the 4-wire side. If, for example, the left hybrid of the Figure 2 has this kind of impairment, then the right talker will be hearing his own voice in the handset as an echo and the more the distance (and thus the signal delay) between the abonents’ phones, the better this echo will be audible. Since the hybrid echo is inherent in the designs involving 2-to-4-wire conversion, we always need to cancel this echo in the switching stations and any other devices having this kind of conversion. Regular phones, which are connected by 2-wire lines with the switching stations, may also have this kind of conversion, but there’s an excuse for not doing full-blown echo cancellation in the regular phones. The delay in the electrical path between the microphone and earpiece (or speaker) in the phone is essentially zero, so a cheap transformer-based attenuator can be used, and hearing your own undelayed voice of low amplitude does not cause much, if any, of the discomfort. Actually, hearing talker’s own voice is desirable as people expect to hear themselves but being not able to do so make them think that the phone is not working. However, using echo cancellation is required in the hands-free phones and all phones, which amplify the signal right before the earpiece or loudspeaker. Not doing echo cancellation in such devices leads not only to very well audible echoes for those who make calls to such phones (acoustic echo cancellation will be treated in the following section), but also to self-excitation of the amplifier. The self-excitation results in from non-ideal signal separation in the phone’s hybrid, e.g. part of the signal from the microphone reflects at the hybrid to the other signal path and gets amplified by the amplifier, so what the microphone is picking can be heard from the speaker. The acoustic feedback between the amplifier’s output and input effectively turns the amplifier to a generator. Therefore, the hands-free and all other amplifying phones (for example, phones for people with hearing impairments, who tend to speak louder) must include line echo cancellers. Unlike the phones, the dialup modems and faxes always employ built-in echo cancellers to combat the local echo, because these digital devices are much more sensitive to the distortions of the received signals than humans. The same echo cancellation may be desirable in the answering machines, which record the voice from the phone line. There are a few peculiar properties of the hybrid echoes. One is that the echo path delays are very short and each hybrid has a single echo path. Another is that the echo paths don’t change or change very slowly over time because of very slow changes of the electrical circuitry parameters and wire lines parameters in the network.

The Need for Echo Cancellation

People have been using phones as a means of distant voice communication for more than a century now. Using phones has become sort of a usual thing. We use the phones almost every day and just about everywhere: at home, at work, outside, in our cars and so on. A big thanks goes to the cellular phones, which set us free from wires! Although we all enjoy this remarkable possibility to talk on the phone, there’s always something we’d like to be better. This something is the speech quality in the phone conversations. The speech quality has always been an issue for both the phone network service providers and their subscribers. There are several reasons for the undesirable quality degradation and the appearance of audible echoes is one of them. This kind of quality degradation is inherent in the network equipment and the end-user phone devices. Today it is easy to implement echo cancellation on DSPs and this is what engineers are doing in their devices. However, many of them face certain difficulties with achieving echo cancellation because of incomplete understanding of the echo cancellation principles and not meeting the requirements imposed by the echo cancellers. The purpose of this article is to demystify the topic
Of the echo cancellation by explaining its basics and providing useful information for those engineers, who need to implement the echo cancellation in their devices. We shall see where the echoes come from, how to fight them and what the known problems with the echo cancellation.

The LMS Algorithm

The LMS adaptive algorithm is well documented in various literature [1-4], hence only a basic introduction to the algorithm is given here--including all changes and important reference notes. The Algorithm is a simple gradient search algorithm that reduces some cost function, in this case the error between the original signal and the received signal (with the echo). The algorithm is designed to search for the best FIR filter coefficients that represent the echoes in the test space (room, stairwell, etc...). An example of the filter coefficients that are determined by the algorithm and resulting frequency response of the filter are shown in Figure 1.1. To determine the coefficients, the original reference signal is convolved with the FIR filter, and the result is an estimate of the echoes present in the recorded signal. The difference between the recorded signal and the original signal plus the estimate of the echo is used to determine how the coefficients will be updated the convolution indicated is not as computationally expensive as it appears. Since time is performing the shift operations, only one set of multiply/adds is needed to determine the echo estimate at the current time. Another time saving shortcut is to limit the number of coefficients updated. For example, if the echo must lag the signal by seconds, then a straight delay can be implemented without computing the coefficients over the time period where no echoes can exist. To further decrease the computational complexity and increase the convergence speed of the algorithm, subsampling could be used. Subsampling is simply splitting the input signal and the output signal into adjacent frequency subbands using analysis filter banks. The impulse response is the system impulse response filtered by the appropriate subband filter. When this approach is used with the LMS algorithm, the convergence speed is increased because the adaptation step size can be set in each subband filter so that it is matched to the energy of the input signal in that particular frequency band.

Approaching Echo Cancellation

As the exact network and room echo paths (and their impulse responses) are generally unknown, there’s no other simple means to remove the echo but an adaptive system. Let’s look at how in general the echo cancellation can be done for one direction of transmission.


On the above figure we see the switching station with an echo canceling system integrated on the 4-wire side between points A, B, C and D. The signals (all shown as functions of the sample number, i) are as follows: x(i) is the signal from the abonent connected by a 2-wire line to the switching station (near-end talker signal), y(i) and u(i) are the signals from and to the other abonent (far-end talker), which come through the 4-wire line.
The idea of an echo canceller is simple. The signal from the far-end talker, y (i), when passing through the hybrid’s echo path (between points B and A) is affected by the echo path’s impulse response and is transformed to the signal r(i), which is the undesired echo. The signal from the near-end talker, x (i), is added to r(i) at point A. The adaptive filter (normally, FIR) used in the system mimics the impulse response of the hybrid’s echo path and produces a replica, r’ (i), of the echo signal r(i). If r(i) and r’(i) are the same, then they will cancel each other in the summer connected between points A and C and the filter’s output. If r(i) and r’(i) aren’t the same, the farend talker will be hearing not only the near-end talker’s x(i) signal, but also the difference of r(i) and r’(i), which is called the residual echo error signal. The residual echo error, e (i) = r (i) – r’ (i), is used to adapt the filter’s coefficients. That is, the echo canceller is a tracking system with the residual echo error signal used as the feedback and the purpose if this system is to minimize this error.
Obviously, since the echo path’s impulse response is unknown, some time is needed for the echo Canceller to minimize the residual echo error signal below a required level. This time is called the convergence time. Note that while the far-end talker’s signal y (i) is equal to zero, the echo canceller is not able to converge, because both r(i) and r’(i) are zero, thus the feedback is also zero and there’s no adaptation possible. This is why the reference signal y(i) should be present in the beginning of the conversation; grabbing the handset and just saying “hello” should be more than enough for the adaptation to proceed. Note that the adaptation is possible to do when the near-end talker’s signal x(i) is close to or is zero, otherwise this signal x(i) will effectively be an additive noise in the feedback, causing the system to become unstable, diverge and stop working.

The hybrid echo path delay is known to be short. The time span, over which its impulse response is significant, is typically 2 to 4 milliseconds, but usually when canceling the hybrid echo, the number of filter coefficients is chosen to cover hybrid echo path delays up to 16 milliseconds, which is usually the upper bound of the hybrid echo path delay. The 16 ms path needs 128 coefficients at the sampling rate of 8 KHz. The length of the acoustic echo path, as has already been pointed out, depends on the size of the room, where it exists. So, without going into room measurements, for acoustic echo path delays of up to 256 ms we will have to have 2048 coefficients at the sampling rate of 8 KHz.

Echo Canceller Performance

The NLMS-based echo cancellers for both hybrid and acoustic echo canceling do exist and perform well, however, acoustic echo cancellation is more complex due to the specifics of the acoustic echo paths and the need for the acoustic echo cancellers to operate in the presence of noise in the echo path (examples: noise in the car, noise in a crowded room). For these reasons a number of enhancements has been proposed and implemented in the acoustic echo cancellers (AECs) by researchers. There are certain improvements possible when employing a frequency- domain AEC. As you should have already realized, the NLMS algorithm presented earlier entirely operates in the time domain, no work is done there on the spectrum. The first problem with time-domain AECs is their resource requirements, MIPs. Normally, the AECs need to have many filter coefficients to efficiently cancel the acoustic echo. But doing long convolutions to generate the replica of the echo signal is expensive when doing them directly in the time domain. It is possible to modify the initial NLMS algorithm so that the filter coefficients are updated once per a block of samples y (i)…y (i+N) instead of doing that each new sample y(i). The NLMS algorithm such modified is called the block NLMS (or BNLMS) algorithm. The Fast Fourier Transform (FFT) is a very efficient DFT implementation and it is known to have a computational cost proportional to N*log2 (N). So it is more efficient to use convolution by FFT for big Ns. The disadvantage of using BNLMS is that it has slower convergence because of rare adaptations. Also, such an echo canceller introduces a processing delay. This kind of sub-band processing in echo finally, it is important how the echo canceller behaves in the double-talk situations, when both talkers talk simultaneously. Obviously, the parties prefer to hear each other throughout the entire conversation and hear little or no echo during double-talks. Therefore, the echo canceller’s double-talk performance should also be addressed when designing and testing echo cancellers or simply choosing which one to integrate to the phone. Frequency-domain echo cancellers are very effective in canceling acoustic echoes.

Failing to Achieve Echo Cancellation

Unfortunately, it is not uncommon for engineers, integrating echo cancellers in their devices, to make mistakes, which cause LECs and AECs to cease work. In this chapter we will describe the most typical design and integration mistakes that lead to failures in achieving echo cancellation. That is, it can be not just a question of achieving good echo cancellation, but instead it can be a question of achieving the echo cancellation at all!
It is very important to understand and meet the requirements of the echo cancellers or they will just not work. To the engineers developing applications with echo cancellers it means that they will need to redesign their product and change the integration of the echo canceller. Speaking in business terms, this will incur higher product costs and longer time to market. And all of this can and should be avoided at best!

Nonlinear Distortions in Hardware

The first thing, which can lead to echo canceller performing very poorly, is the nonlinear distortions in the echo path of the hardware of your device. The echo cancellers perform poorly or don’t work at all in systems with the net nonlinear distortions in the echo path higher than –16 dB (typical value). The smaller are distortions, the better. The nonlinear distortions exist everywhere. Certain nonlinearity is inherent in the hybrids, microphones, speakers, amplifiers and DAC/ADCs (known as codecs). It is not recommended to make the design with parts, which are highly nonlinear such that the net nonlinear distortions of the device in the echo path are prohibitively high. If there’s some preliminary design available, already in a form of a working device, it is a good practice to measure the level of the nonlinear distortions in it. The sooner such measurements are done, the better.


Microphone and Speaker Placement

As it has already been mentioned, the acoustic echo exists between the loudspeaker and the microphone in hands-free phones inside their cases. The echo can be transmitted by both the air inside the case and by the case itself in a form of mechanical waves (vibrations) in the case parts. To reduce this form of the echo, there should be a good acoustic decoupling between the loudspeaker and the microphone. The microphone should be acoustically and mechanically insulated by a soft material, absorbing the case vibrations and sound coming out of the speaker. The microphone should not be directed to the speaker. It can be useful to have a directional microphone, so it can be directed away from the speaker.

Input and Output Signal Requirements

Besides the main hardware questions like the nonlinear distortions, there are also certain requirements on the signals, which are fed as samples to the echo cancellers. The first requirements are that signal delays in software be as short as possible. In general, there should be no signal processing done between the codec and the echo canceller. And there must be no sample accumulation without any good reason for it. Excessive buffering will increase the effective signal delay in the echo path and therefore the utilization of the filter coefficients will be ineffective (some of the coefficients will have to cover the additional delays yet they will be zeroes). Obviously, the reference signal, y(i), delay in software must be smaller than or equal to the software delay for the signal with echo, x(i)+r(i). If this is not true, the echo canceller will not be able to converge and cancel the echo since it doesn’t have the reference signal, which is to be subtracted.
.
Incorrect Codec Synchronization

The last but not least problem with echo canceller integration can be again due to the hardware or software design mistakes. What is the problem of incorrect codec synchronization? Well, the problem is easy to understand and relatively easy to solve, provided we know the right solution to it. Suppose we have a device, which has several different signal sources, each clocked at a different rate, and the signals from one must go through the device to the other. Where is this possible? This is possible in hands-free phones, which have a pair codecs. One of the codecs is used to interface to the phone line and the other one is used to interface to the loudspeaker and microphone. he problem here is that if both codecs are clocked at different rates (say both have sampling rate at about 8 KHz but they’re not exactly equal because they’re clocked from different quartz oscillators), then we can’t just take each sample from one codec, somehow process it and pass to the other codec. Eventually, the sampling rate difference will lead to either sample accumulation somewhere in the sample buffers or sample depletion, e.g. there will be nothing to take out of a buffer when a sample is needed.

Requirements Summary

Now that we have analyzed the typical problems with echo cancellation and pointed out several design and integration mistakes, we can summarize the requirements imposed by an echo canceller:
1. The nonlinear distortions in the hardware (microphones, speakers, amplifiers and codecs) must be sufficiently low, typically less than –16 dB.
2. The microphone and loudspeaker placement and echo insulation in the hands-free phones should be done carefully so as to reduce the phone’s internal echo from the speaker to the microphone and be less sensitive to the echo path change outside the phone case.
3. The signal delays in the software must be fixed throughout the entire call session and they must be minimal, so the entire echo path delay is minimal and constant too.

Testing Echo Cancellers

It is a good practice for the customer to ask the echo canceller algorithm supplier how well their echo canceller conforms to the appropriate ITU-T recommendations (which are de-facto standards) and provide these figures alone with the resource requirements so a right decision can be made when choosing an echo canceller. It is beneficial for the customer to understand the basics of the echo cancellation and maybe even be familiar with the listed recommendations, however, it always makes sense to make a few tests of the echo canceller of interest. If a live test is possible, which is very desirable for AECs, it is good to make it. The echo canceller suppliers should provide a test or demo suit and a few test waveforms (the reference signal y(i) and the signal with the echo, x(i)+r(i) ), on which the echo canceller can be tested. Such a test can be carried out on either a PC or the customer’s target hardware, whichever is arranged. This ensures the echo canceller operation and the suit can also be used to test the echo canceller performance on specific waveforms if the customer has any concerns about particular cases. It’s also a good thing to test double-talk performance of the echo canceller to make sure the quality is delivered to the end users. By the time the echo canceller integration is about to start, the hardware of the target device must have a sufficiently low level of nonlinear distortions. Only after having fixed all of the hardware problems, the echo canceller integration should begin. As soon as the echo canceller integration is finished, the echo canceller test can be repeated in full real-time with true I/O instead of file processing. Should there be any quality problems, the hardware and software must be checked against possible violations of the requirements imposed by the echo canceller, which have been stated earlier.

Conclusion

As we have seen in the preceding sections of this article, there are many possible problems, which can arise when designing and implementing a system with an echo canceller. But there is no black art or any other magic behind the failures. The reasons for them are well known and perfectly consistent with the echo canceller internal organization and requirements. To prevent delays in the development and reduce the costs, consider designing the system to meet the requirements at the very beginning. Redesigning the whole system at the middle or last stage because of not meeting the requirements will be expensive. Solid understanding of the basics of he echo cancellation and meeting the general requirements imposed by echo cancellers will void of the echo canceller problems and therefore shorten the development time and product costs, which is always desirable. The engineers at SPIRIT Corp hope that this little investment in the form of an article will make a good service to all parties interested in canceling echoes in their products.

REFERENCES

1. .Murano, Kazuo; Unagami, Shigeyuki; Amano, Fumio; “Echo Cancellation and Applications,” in IEEE Communications Magazine, v. 28 pp. 49-55, January ‘90.
2. Petillon, Thierry; Gilloire, Andre; Theodoridis, Sergios; “The Fast Newton Transversal Filter: An Efficient Scheme for Acoustic Echo Cancellation in Mobile Radio,” in IEEE Transactions on Signal Processing, v. 42 pp. 2134-44 May ‘94.
3. Gilloire, Andre; Vetterli, Martin; “Adaptive Filtering in Subbands with Critical Sampling: Analysis, Experiments, and Application to Acoustic Echo Cancellation,” IEEE Transactions on Signal Processing, v. 40 pp. 1862-75, August ‘92.
4. van de Kerkhof, Leon M.; Kitzen,Wil J.W.; “Tracking of a Time-Varying Acoustic Impulse Responsibly an Adaptive Filter,” in IEEE Transactions on Signal Processing, v. 40 pp. 1285-94, June ‘92.
5. Clark, Robert; “Active Damping on Enclosed Sound Fields Through Direct Rate Feedback Control,” in Acoustical Society of America, pp. 1710-16, March 1995.
6. Gingell, M.J.; Hay, B.G.; Humphrey, L.D. “A Block Mode Update Echo Canceller Using Custom LSI,”GLOBECOM Conference Record, v. 3, 1394-97 (November 1983).
7. Kates, James M.; “Feedback Cancellation in Hearing Aids: Results from a Computer Simulation,” in IEEE Transactions on Signal Processing, v 39 pp. 553-62, March ‘91.