DSP Explorables

Finding signals below the noise

A GPS satellite is 20,000 km away and transmits with about the power of a couple of light bulbs. By the time its signal reaches your phone, it’s around 20 dB weaker than the random noise the phone’s own electronics make: a hundred times less power. Yet the phone finds four or more of these signals, times them to within a few billionths of a second, and works out where you are.

The trick is that the receiver knows exactly what it’s looking for. A signal of a known shape can be found far below the noise. This page builds up how, from the obvious approach to the one every radar, sonar, GPS receiver and Wi-Fi chip uses: the matched filter. It ends with a demo that uses your own loudspeaker and microphone to find the echoes in your room.

A few terms first:

Noise here is random, with no pattern at all: each sample is a fresh random number, bell-curve (“Gaussian”) distributed, independent of the last. Its size is measured by its RMS (the square root of its average power), which on this page is always 1.
The SNR (signal-to-noise ratio) of a pulse is its power while it’s on, divided by the noise’s power, in dB. 0 dB means the pulse is as strong as the noise; −20 dB means a hundredth of its power.

Everything runs at 8 kHz, so every signal can be listened to.

1 · Naive: wait for something big

The obvious detector: watch the signal, and say “there’s a pulse” whenever it goes beyond a threshold. There are two ways to be wrong:

a miss: the pulse is there, but never crosses the threshold
a false alarm: the noise crosses the threshold on its own.

250 ms of noise, with a 5 ms pulse (a burst of 1 kHz) at the green stripe. The readouts come from 400 tries, with the pulse at a different place each time. At +6 dB, with the threshold at 4 × the noise’s RMS, the detector finds 98% of the pulses, with 0.4 false alarms a second. At 0 dB it finds only 14%. Lowering the threshold to 3 finds 73%, but now the noise alone crosses it 21 times a second. At −6 dB, a threshold of 4 finds none at all.

Listen at −6 dB: you can probably still hear the pulses. Your ear isn’t a threshold detector. It splits sound into many narrow frequency bands and listens to each, which (as section 4 shows) is a big step towards the right answer.

A threshold is a trade-off: lower it to catch weak pulses and it catches the noise too. The false-alarm rate depends only on the noise and the threshold, not on the pulse at all. Below about 0 dB, there’s no good setting. Each sample on its own just doesn’t hold enough evidence.

2 · Averaging: let the noise cancel itself

If the pulse repeats, and you know when, there’s an easy improvement: add up the repeats, lined up with each other, and divide by how many there are.

Each time, the pulse is the same, so averaging leaves it unchanged. The noise is different each time, so its ups and downs partly cancel. Averaging $N$ repeats leaves the signal’s power alone but divides the noise’s power by $N$ . That means the SNR rises by $10 \log_{10} N$ dB: 3 dB for each doubling of the number of repeats.

A 20 ms pulse that repeats every 50 ms, at −20 dB: invisible in any one repeat (top). Averaging 64 repeats lifts it to −1.7 dB (expected: −1.9 dB), and averaging 1024 to +10.4 dB (expected: +10.1 dB). The rule holds across the whole slider, to within a few tenths of a dB.

Averaging like this is how brain scientists measure the brain’s tiny electrical response to a sound: they play the click hundreds of times and average what the electrodes pick up. The gain from combining many measurements like this is called processing gain. But averaging needs the signal to repeat, and the receiver to know exactly when. For a single pulse at an unknown time, we need something else.

3 · Correlation: compare with the shape you expect

The receiver knows the pulse’s shape. So, at every possible arrival time, compare the received signal with that shape: multiply the two sample by sample, and add up. This is correlation, the multiply-and-add of the Fourier page. It’s also the method of autocorrelation pitch detection, and of the CELP coder’s codebook search.

c[k] = \sum_{j} t[j]\; x[k + j]

Here $t$ is the template, the shape being looked for, and $x$ is what was received. At the right shift $k$ , every sample of the pulse is multiplied by itself. Those products are all positive, so they add up together. The noise’s products are positive and negative at random, so they partly cancel, as in averaging. It’s averaging within the pulse: each of its $N$ samples acts as one repeat. So correlating gains about $10 \log_{10} N$ dB.

Top: half a second of noise, with a 32 ms pulse (256 samples) hidden in it at −10 dB. It’s shown in green here, but the receiver doesn’t know where it is. Middle: the template. Bottom: the correlation at every shift, scaled so that its noise has an RMS of 1. The correlation should peak at $\sqrt{N \times \text{SNR}}$ = 5.1, an SNR of +14.1 dB: the 256 samples have gained 24.1 dB. In this run, the peak at the pulse is 4.8, and the biggest anywhere else is 3.7: found.

Over 200 tries with fresh noise, the biggest peak is at the pulse 197 times at −10 dB, 84 times at −15 dB, and 17 times at −20 dB. A longer pulse helps: at −10 dB, 512 samples should give a peak of 7.2, and 64 samples only 2.5. Try new noise a few times, and lower the SNR until it starts failing.

Notice that the peak’s height depends only on $N \times \text{SNR}$ : the pulse’s total energy (its power × its length) compared with the noise. A longer pulse can be found at a lower SNR. Section 5 makes the most of that.

4 · The matched filter: why correlation is the best possible

Correlating at every shift is the same as running the received signal through an FIR filter whose impulse response is the template reversed in time. That’s the matched filter. (Filtering slides the impulse response along the signal back to front, and reversing it turns the filter’s multiply-and-add back into a correlation. See the FIR page for filters as multiply-and-add.)

Is it the best filter there is? Suppose some filter $h$ is applied to a pulse $s$ in noise of variance $\sigma^2$ . At its best moment, its output SNR is

\text{SNR}_\text{out} = \frac{\left(\sum_j h[j]\, s[-j]\right)^2}{\sigma^2 \sum_j h[j]^2} \;\le\; \frac{\sum_j s[j]^2}{\sigma^2} = \frac{E}{\sigma^2}

The inequality is the Cauchy–Schwarz inequality. A sum of products is largest, for lists of given sizes, when the two lists are in proportion: when they “point the same way”. So:

no filter can do better than $E/\sigma^2$ , the pulse’s energy over the noise’s power
the filter that reaches it is $h[j] \propto s[-j]$ , the pulse reversed: the matched filter.

The best possible SNR depends only on the pulse’s energy, not on its shape. Section 5 makes the most of that.

Top: the output SNR of four filters, for the same pulse in the same noise, compared with the best possible (exact values, no random trials). The matched filter reaches it. A band-pass filter around the pulse’s frequency comes close, 3.2 dB short. A moving average is 39.3 dB short: it passes low frequencies, and a 1 kHz burst has almost none. A template at slightly the wrong pitch (1.1 kHz instead of 1 kHz) is 33.6 dB short. Bottom: the matched filter’s frequency response has the same shape as the pulse’s spectrum.

That last point is the frequency-domain view. The matched filter lets each frequency through in proportion to how much of the pulse is there. White noise is spread evenly over every frequency, so the filter keeps the frequencies where the pulse is strong and turns down the rest. The ear’s narrow frequency bands, from section 1, do roughly the same thing for a tone. (If the noise isn’t white, the best filter first evens out the noise’s spectrum, “whitening” it, and then matches. The idea is the same.)

5 · Pulse compression: long pulses, sharp peaks

A real transmitter, whether radar, sonar or a loudspeaker, has a peak power limit: it can’t go louder, only longer. So to give a pulse more energy, make it longer. But a longer pulse smears in time: two echoes closer together than the pulse is long blur into one. Radar seemed to face a choice between range (energy) and resolution (telling close targets apart).

The way out is in the matched filter’s output. Its width depends not on how long the pulse lasts, but on how wide a range of frequencies it covers, its bandwidth: roughly 1/bandwidth. A long pulse that sweeps across many frequencies, or flips its phase in a pseudo-random pattern, has both lots of energy and a sharp peak. The matched filter “compresses” it back into a short spike: pulse compression.

Top: each shape correlated with itself: the matched filter’s output for a lone echo with no noise (its envelope, in dB). Middle: two echoes (the second at 0.6 × the first, 5 ms later), in noise. Bottom: the matched filter’s output.

Every shape has the same peak level of 1:

Shape	Energy (vs the click)	Peak width	Biggest sidelobe
Short click, 1 ms	0 dB	0.63 ms	−42.2 dB
Long tone, 32 ms	+12.4 dB	20.63 ms	−46.9 dB
Chirp, 500 Hz → 3.5 kHz, 32 ms	+16.0 dB	0.38 ms	−14.2 dB
Barker code, 13 chips, 26 ms	+15.7 dB	2.13 ms	−22.3 dB
Pseudo-random code, 63 chips, 32 ms	+16.6 dB	0.38 ms	−20.4 dB

The long tone has the energy but blurs the two echoes into one hump. The chirp and the code have nearly as much energy and a sharper peak than the click, so the two echoes stand apart. Their price is sidelobes: smaller false peaks beside the true one, which could hide a weak echo. Listen to the chirp: it’s the “whoop” that bats use.

The codes are made of chips, short stretches of a carrier tone, each sent with its sign flipped or not.

Barker codes (up to 13 chips) have the smallest sidelobes possible for their length: never more than one chip’s worth, here 1/13 of the peak (−22.3 dB). A Barker code of 11 chips spread the original Wi-Fi’s signal.
Maximal-length sequences (m-sequences) come from a simple shift register with feedback, and can be made as long as needed. Their correlation is the full length at zero shift and −1 at every other (cyclic) shift.

Radar has used pulse compression since the 1950s.

6 · Spread spectrum: many voices, one channel, below the noise

Pseudo-random codes have one more property that matters a great deal: two different codes hardly correlate at all. So several transmitters can share the same channel, at the same time and on the same frequencies, each using its own code. A receiver correlating with one code picks out its transmitter, and the others look like a little extra noise. This is code-division multiple access.

Each data bit is sent as a whole code, multiplied by +1 or −1: spreading. The receiver multiplies by the code again and adds up the chips, which is despreading: a matched filter for one bit. It gains $10 \log_{10}(\text{chips})$ dB, which for a 1023-chip code is 30.1 dB. But first the receiver has to find where each code starts. It does that by trying every code phase, which is called acquisition.

GPS works exactly like this. Every satellite repeats its own 1023-chip Gold code (a family of codes built from pairs of m-sequences, which correlate weakly with one another) once every millisecond. Here, the codes are the same family, but slowed down to one chip per sample at 8 kHz.

Up to four transmitters, each sending 8 bits with its own Gold code, starting at a random delay, all added together in noise. Top: what’s received, with transmitter 1’s part drawn to scale: tiny. Middle: acquisition: the correlation at every code phase, for each code. Bottom: each bit after despreading.

At −20 dB per chip with 1023-chip codes, every code is found at the right delay. Despreading lifts the SNR to +10.1 dB, and all 24 bits of the three transmitters come through without an error. At −25 dB, one of the 24 is wrong. At −30 dB, acquisition fails. With 127-chip codes (a gain of only 21 dB), −20 dB is already too little: two of the three codes are found at the wrong delay, and 13 bits are wrong.

The real GPS has two more problems to solve:

Doppler shift. Each satellite moves at several kilometres a second, which shifts its signal’s frequency, so acquisition searches frequency as well as code phase.
The data rate. The navigation data comes at only 50 bits a second, 20 code periods per bit, which adds another 13 dB of gain.

The same principle carried 3G mobile phones.

7 · Deciding: thresholds, false alarms, and misses

The matched filter makes the evidence as strong as it can be, but something still has to decide. Look at the filter’s output at the one moment a pulse would be, scaled so that the noise in it has an RMS of 1:

Without the pulse, the output is noise alone: a bell curve centred on 0.
With it, the same bell curve centred on $d = \sqrt{E / \sigma^2}$ , the square root of the best-possible SNR from section 4.

A threshold $T$ splits the two. The chance of a false alarm is the area of the noise curve beyond $T$ . The chance of finding the pulse is the area of the other curve beyond $T$ :

P_\text{false alarm} = Q(T), \qquad P_\text{found} = Q(T - d)

where $Q(x)$ is the chance that a bell-curve value with an RMS of 1 comes out above $x$ .

Sliding the threshold traces out every possible trade-off between the two, a curve called the ROC (receiver operating characteristic; the name comes from wartime radar).

4000 tries without the pulse and 4000 with it, each a 256-sample burst. Top: how the matched filter’s outputs fall in each case. Bottom: the ROC curve from the formulas, and the measured point for this threshold (orange).

At −15 dB, $d$ = 2.85. With the threshold at 3, the pulse is found 44.3% of the time (the formula says 43.9%), with false alarms 0.10% of the time (formula: 0.13%). Raise the SNR and the two curves pull apart, and the ROC curve bends up towards the top-left corner: finding everything, with no false alarms.

Radar usually fixes the false-alarm rate it can live with and sets the threshold from that, adjusting it as the noise changes. Then the only way to find more is a bigger $d$ : more energy, from a longer pulse or more repeats. One more subtlety, which explains section 3’s “biggest elsewhere”: when the time of arrival is unknown, every possible shift is a separate chance for a false alarm, so the threshold has to be higher than for a single, known moment.

8 · Finding your own echo

Matched filters are everywhere a known waveform has to be found:

Radar and sonar: chirps and codes, compressed on reception.
GPS: Gold codes, as above.
Wi-Fi and mobile phones: every packet starts with a known preamble, found by correlation, which tells the receiver that a packet has begun and exactly when.
Medical ultrasound and seismic surveys: seismic surveys often send a long chirp from a vibrating truck, rather than an explosion.
Acoustics: room acoustics are measured with sine sweeps or m-sequences played through a loudspeaker.

The last one you can try now. The figure plays a short chirp (80 ms, 400 Hz → 4 kHz) through your loudspeaker while recording from your microphone. It then finds the chirp in the recording with a matched filter, and shows what arrived after it.

Top: the matched filter’s output over the whole recording: one sharp peak where the chirp arrived. Bottom: a close-up just after it, in dB. Later, smaller peaks are reflections: the same chirp arriving again, off walls, desks and ceilings, each delayed by its extra path (sound travels about 34 cm per millisecond).

Before you record, it shows a made-up room: the chirp heard 20 ms after it was played, and reflections 4.5, 11 and 27 ms later. The peak stands 52 dB above the typical level of the filter’s output. Use loudspeakers, not headphones.

The recording and the chirp are timed by the same clock, the sound card’s own sample count, so the delay is the true round trip. Most of it is usually the computer, not the air. Audio is handled in blocks, so the chirp waits in the computer’s output buffers before it reaches the loudspeaker, and the microphone’s sound waits in input buffers before it is recorded. Together these usually take tens of milliseconds, and an audio interface or Bluetooth can add much more. The air adds about 2.9 ms per metre.

To separate the two, measure the same setup twice. Press Keep this delay as the reference, move the microphone (or the loudspeaker) further away, and measure again. The computer’s delays are the same both times, so they cancel out. The difference is the extra trip through the air, which the figure turns into metres.

A matched filter always has a biggest peak, even when the ping isn’t there at all. So the last readout checks how much the recording at that peak actually resembles the ping: its normalised correlation, where 1 means an exact (scaled) copy. The made-up room scores 0.85, because its reflections overlap the first arrival a little. If the ping never reached the microphone, the score is near 0, and the figure says so.

Summary

A lone threshold fails below about 0 dB: each sample alone holds too little evidence.
Averaging $N$ repeats gains $10 \log_{10} N$ dB, if you know when the signal repeats.
Correlating with the known shape is averaging within the pulse. Done at every shift, it’s the matched filter: the template reversed, used as an FIR filter.
No filter can beat the matched filter’s SNR, $E/\sigma^2$ (Cauchy–Schwarz). It depends only on the pulse’s energy, not its shape.
Pulse compression: chirps and codes have the energy of a long pulse and the sharpness of a short one, because the peak’s width is set by bandwidth, not duration.
Spread spectrum: each transmitter’s own code lets many share one channel, below the noise. Despreading gains $10 \log_{10}(\text{chips})$ dB. This is how GPS works.
Deciding trades false alarms against misses (the ROC curve). Only more energy improves both.