Adaptive filters and echo cancellation

On a call on speaker, the other person’s voice comes out of your loudspeaker, bounces round the room, and goes straight back into your microphone. Without something to stop it, they’d hear themselves, a few hundred milliseconds late, after the trip through the network and back: a distracting echo that makes it hard to keep talking. Every phone, laptop and video-call app stops it with an echo canceller: a filter that learns, as you talk, exactly what your room does to the sound, and subtracts its prediction from the microphone.

It’s a filter that adjusts itself: an adaptive filter. The same idea, a filter that keeps nudging itself towards less error, is behind noise-cancelling headphones, and also behind the equalisers in modems, which modulation part 2 uses to undo echoes in a channel.

It leans on:

Designing FIR filters: a filter’s taps and its impulse response.
Finding signals below the noise, for correlation, and for measuring a room’s echoes.

1 · A filter that learns

Start small. Somewhere there’s a filter with two taps, which we can’t see: feed it a signal and we can hear what comes out, but not the taps themselves. We want to copy it. So we run our own two-tap filter on the same input, and compare what comes out.

A two-tap filter works one output sample at a time. For output number $n$ , tap 0 multiplies the newest input sample, $x[n]$ , and tap 1 multiplies the one before it, $x[n-1]$ , and the two are added. Over time every tap sees every input sample, but for any one output, each tap has multiplied exactly one input. So for each output sample:

the real filter gives $d[n] = 0.5\,x[n] + 0.3\,x[n-1]$ (we can hear this, but not the 0.5 and 0.3);
ours gives $y[n] = w_0\,x[n] + w_1\,x[n-1]$ ;
the error is one number, $e[n] = d[n] - y[n]$ .

The least mean squares (LMS) rule, from Bernard Widrow and Ted Hoff (1960), says how to adjust our taps after every output sample: nudge each tap by the step size, times the error, times the input that tap multiplied for this output:

\Delta w_0 = \mu \, e[n] \, x[n], \qquad \Delta w_1 = \mu \, e[n] \, x[n-1]

Why that input? If tap 0 had been a little bigger, this output would have been bigger by $x[n]$ times as much. So $x[n]$ measures how much tap 0 could have changed this output: it gets that share of the blame for the error, and that share of the correction. A tap whose input was zero this time contributed nothing, and isn’t moved. The step size $\mu$ keeps the nudges small.

Step through it. The newest input sample arrives, both filters make one output, and the sums for that one sample are shown above, from the error to how far each tap moves. On the first step, the inputs are 0.5 (tap 0’s) and 1.0 (tap 1’s): the real filter gives 0.55, ours (both taps at 0) gives 0, so the error is 0.55. With μ = 0.3, tap 0 moves by 0.3 × 0.55 × 0.5 = 0.0825, and tap 1, whose input was bigger, twice as far. One sample can’t separate the two taps’ blame perfectly: on step 2, tap 1 moves the wrong way. But over many samples the nudges average out in the right direction: Run it, and both taps are within 0.01 of the real filter’s after 29 steps.

Each step is a small step downhill on the mean squared error: how big the error is on average, for a given pair of taps. Picture that error for every possible pair of taps, and it makes a bowl, with the real filter’s taps at the bottom. Each LMS step heads roughly downhill, judged from one sample.

The mean squared error for every pair of tap values is a bowl (its contours, top), with the real filter (0.5, 0.3) at the bottom. Here LMS starts from (−0.7, −0.6), with a random input this time, and walks down it, noisily, one sample at a time: the error falls by 30 dB in 105 steps with white noise. When each input sample is like the one before (as in speech), the bowl is stretched into a long, narrow valley, and LMS zigzags down it more slowly: 139 steps.

2 · How big a step?

The step size is a trade-off. Small steps are slow; big steps are fast, until they’re too big, and each overshoots further than the last: the filter blows up. How big is too big depends on the input’s level and the filter’s length: about $2 / (\text{taps} \times \text{input power})$ . That’s a problem for speech, whose level swings from shouting to silence: a step that’s safe for the loud parts is far too timid for the quiet ones.

Normalised LMS (NLMS) divides each step by the input’s power over the filter’s length, so the step is measured as a share of the way, whatever the level:

\Delta w_k = \frac{\mu}{\sum_j x_j^2} \, e \, x_k, \qquad 0 < \mu < 2

A 10 ms echo path (160 taps) to learn, from white noise or from speech, by LMS and by NLMS. The curves show how far the filter is from the real one (0 dB: no closer than no filter at all). With white noise, LMS is stable below μ = 0.15, and at 0.2 it blows up. With speech, which is quieter on average, LMS crawls: after 4 seconds, it’s only 2 dB closer at μ = 0.025. NLMS at μ = 0.5 gets 6 dB closer within a second, and then stalls (8 dB after 4 seconds). That isn’t NLMS’s fault: this voice has almost nothing above 5 kHz, so nothing in it tells the filter what the echo path does up there. It doesn’t need to know, either: an echo of nothing is nothing. A voice with an “s” in it would fill the gap for a moment, and so does white noise, all the time.

3 · Cancelling the echo

Now the real thing. The far end (the other person’s voice) goes out of the loudspeaker. The microphone picks up the echo: the far end, filtered by the room (the direct path, then reflections off the desk, the walls, the ceiling). The echo canceller has what the real system has: the far end’s sound, which it sent, and the microphone’s. So it runs an adaptive filter on the far end’s sound, learns to predict the echo, and subtracts the prediction. What’s left goes back to the far end.

Why not just play a click?

There’s a quicker way to find out what a filter does: feed it a single click (an impulse), and what comes out is the filter. In section 1’s two-tap filter, a click gives 0.5, then 0.3, and that’s the answer. That’s how rooms are measured: the finding-signals page finds your room’s echoes with a chirp. An echo canceller can’t work that way:

It doesn’t choose what’s played. During a call, the loudspeaker plays the other person’s voice. The canceller can’t stop the conversation to play clicks, and nobody wants clicks in their call.
The echo path keeps changing. You lean back, someone walks past, you pick the laptop up. A measurement taken at the start of the call is out of date within seconds.
A click carries very little sound. One sample’s worth of energy barely rises above a room’s noise. That’s why measurements use long sweeps or noise instead, then undo them with sums that only work for a test signal designed for the job.

LMS gets round all three. It measures the echo path from whatever sound happens to be going out, every sample of the conversation adding a little, keeps measuring as the path changes, and costs a couple of multiplications per tap per sample.

The filter needs as many taps as the echo lasts. A room’s echo can last a few hundred milliseconds, and at 16,000 samples a second (a “wideband” call), that’s thousands of taps. How well it works is measured as echo return loss enhancement (ERLE): how much quieter the echo is after cancelling.

Top: the echo the microphone picks up (from the synthesised far end, in a room whose echo lasts 200 ms), and what’s left after cancelling. Middle: echo removed, as it learns. Bottom: the room’s real echo path and what the filter learned. With 1,024 taps (64 ms), it removes 29 dB of echo by the end; with 128 taps, none (0 dB): less than a third of this room’s echo arrives within its 8 ms, and it can’t model the rest. 2,048 taps reach 37 dB; but 3,200, the whole echo, only 33 dB in the 9 seconds here, because a longer filter has more to learn and learns more slowly. Listen to all three.

4 · Double talk

The filter learns from the error: whatever’s left after subtracting its prediction. That’s fine while only the far end talks. But when you talk too (double talk), your voice is in the microphone, and to the filter it looks like a huge error. It “learns” from it, and walks away from the room’s real echo path, then the echo comes back.

The fix is to notice double talk and stop learning while it lasts. A simple, classic detector (Geigel’s) assumes the echo is always quieter than the far end’s sound was: if the microphone is ever louder than half of the far end’s loudest recent sample, that must be you, so freeze the filter. Real ones are cleverer, but the idea is the same.

You speak from 3.5 to 6.6 seconds (shaded orange), over the far end. Top: how far the filter is from the real echo path. Without detection, it’s thrown off by up to 30 dB during double talk, and afterwards the echo is 4.2 dB louder than with no canceller. With detection (frozen where shaded purple), it holds its course: afterwards, the echo is 11.2 dB quieter. Bottom: the echo, and what’s left of it (your voice taken out).

5 · What breaks it

An echo canceller assumes the echo is the far end’s sound through a fixed filter. Anything else is beyond it:

Distortion. A small loudspeaker pushed hard squashes the peaks of the sound, which no filter of the far end’s sound can predict.
Drifting clocks. The loudspeaker and the microphone may run on different clocks, a few parts per million apart (a Bluetooth headset and a laptop, say). Then the echo slowly slides in time against what the filter learned.
Movement. Someone moves, or picks up the laptop, and the echo path changes; the filter has to learn it again.

So real echo cancellers follow the filter with a residual echo suppressor: when the far end is talking and you’re not, it turns the microphone down a little more, to hide what’s left. It’s why, on some calls, the other person’s voice briefly fades when you both talk at once.

Echo removed while the far end talks, with something wrong (blue), against the same with nothing wrong (grey). A loudspeaker that distorts holds the cancelling to 17 dB instead of 29; clocks 500 parts per million apart, to 13 dB. When the echo path changes at 4.5 s, the cancelling drops, then the filter learns the new path.

When the phone thinks it isn’t needed

A phone runs its echo canceller only when it expects an echo: on speaker, or through its own earpiece and microphone. Connected to something else, such as a headset or a car, it usually leaves the job to that device: a headset does its own, or its earpieces are sealed from its microphone. Connect a phone’s audio to an audio interface (to hear calls through better speakers, say), and the phone may assume the same. Then, if the far end’s voice can get back into the microphone path (through the speakers and the air, or electrically, if the interface mixes what it plays into what it sends back), nothing cancels it, and the far end hears themselves.

Broadcasters, who put callers on air through mixing desks, fix this with a mix-minus: the caller gets a mix of everything except their own voice. On an audio interface, that usually means making sure the phone’s own return isn’t in the mix sent back to it (for example, turning off any “loopback” for that channel).

6 · In your room

Here’s the echo canceller in your own room. The page plays the far end through your loudspeaker, with a second’s pause between its phrases, and records your microphone. Then it finds the delay through your computer, and runs the canceller (2,048 taps, 128 ms, with double-talk detection) on what it recorded.

Give it a fair chance, as a real call does:

Somewhere quiet. To the canceller, anything in the microphone that isn’t the far end’s echo, a TV or a conversation in the room, looks like error: it learns more slowly, and the double-talk detector keeps freezing it.
Let it learn first. For the first two phrases, just listen. Real conversations take turns, and by the time you answer, a canceller has usually settled.
Then talk in the pauses, as you would on a call. Or talk over it, to try double talk: it’s harder, and you’ll hear why.

The double-talk detector needs to know how loud the echo can get, and in a real room that depends on your loudspeaker’s volume and your microphone’s gain: a laptop’s microphone, next to its own loudspeaker, can hear the echo louder than the far end’s own level. So the page measures the echo during the first two phrases, while only the far end is playing, and sets the detector from that.

Then it runs the canceller a second time on the same recording, starting from what it learned the first time, as a canceller would be a minute into a call, and taking smaller steps, as settled cancellers do: small steps still follow slow changes in the room, but a voice that slips past the double-talk detector does far less harm. In a simulated room, with someone answering in the pause after the third phrase and talking on over the fourth, that takes the echo left after the first two phrases from 15.1 dB quieter to 19.6 dB quieter; with no one talking, from 27.7 dB to 31.8 dB.

Use the loudspeaker, not headphones (headphones give no echo to cancel), somewhere quiet.

Top: your room’s echo path, as the filter learned it: the direct sound from the loudspeaker first, then reflections. Bottom: echo removed while only the far end talks (the moments the detector thought you were talking are shaded, and left out), learning from scratch and already learned. Listen to what your microphone heard, and what’s left after cancelling, both ways. While a canceller is still learning, its prediction of the echo is a little wrong, and subtracting it can leave your own voice sounding slightly warbly; once it has learned, that goes. A laptop’s loudspeaker and microphone sit close together, so the echo is loud, and how much can be taken out depends on how much the loudspeaker distorts, and on your room.

7 · Noise-cancelling headphones

Noise-cancelling headphones play anti-noise: the noise outside, upside down, so the two cancel at your ear. A microphone on the outside hears the noise coming; one inside, by your ear, hears what’s left, and an adaptive filter (the same LMS idea, adjusted for the headphone’s own speaker and ear in the way) keeps the cancelling tuned.

But the anti-noise has to arrive at exactly the right moment, at exactly the right level. A little late, or a little off in level, and it doesn’t cancel: at high frequencies, a few tens of microseconds is a large part of a cycle. That’s why they quieten the low drone of an engine or an air conditioner, and do little for voices or clatter: those are left to the ear cushions.

How much quieter the noise gets, at each frequency, when the anti-noise is a little late and a little off in level. 50 µs late (the time sound takes to travel 17 mm) and 10% off still cancels at least 10 dB up to 910 Hz; 20 µs and 5% reach 2.4 kHz. Above that, it can even make the noise louder.

Summary

An adaptive filter adjusts its own taps to make its error smaller. LMS nudges each tap by step × error × that tap’s input: a noisy walk down the error bowl.
Too big a step and it blows up; the safe step depends on the input’s level. NLMS divides by the input’s power, so speech, loud and quiet, is learned at one rate.
An echo canceller learns the room’s echo path from the far end’s sound and the microphone’s, and subtracts its prediction. It needs as many taps as the echo lasts, and the more taps, the longer it takes to learn.
Double talk throws the filter off; a double-talk detector freezes it while you speak.
Distortion, drifting clocks and movement limit it; a residual echo suppressor cleans up after it. Connected to other equipment, a phone may switch its canceller off, and a mix-minus keeps the echo path from forming.
Noise-cancelling headphones play anti-noise, and work best at low frequencies, where a few microseconds out matters least.