Skip to content

Correlation and Matched Filtering

Copy this iframe to your website:

1
<iframe src="https://dmccreary.github.io/signal-processing/sims/correlation-and-matched-filtering/main.html" width="100%" height="617px" scrolling="no"></iframe>

Run MicroSim in Fullscreen

Edit in the p5.js Editor

Description

A receiver knows the shape of the signal it is looking for, the template \(s[n]\) of length \(L\), but not when it arrives. The MicroSim hides one to five copies of a template in white Gaussian noise at unknown delays \(d_i\), so the received signal is

\[r[n] = \sum_i s[n - d_i] + w[n]\]

The plots, from top to bottom:

  • Received signal \(r[n]\) (600 samples). With True delays ticked, green bands show where the templates really are.
  • Template \(s[n]\) and the matched filter \(h[n] = s[L-1-n]\), the template reversed in time.
  • Normalized cross-correlation \(R_{rs}[m] = \sum_k r[k]\,s[k-m]\), divided by the template energy \(E_s = \sum_n s^2[n]\) so that a clean, isolated template gives a peak of exactly 1 at lag \(m = d_i\). It is computed only for lags \(0 \le m \le 600 - L\), where the whole template fits inside the record; the grey strip at the right marks the lags that have no full overlap.

A peak is declared wherever the correlation is a local maximum above the dashed Threshold. Each detected peak carries its lag \(m\) and its measured peak SNR. The summary box compares the measured SNR with the expected value \(\text{input SNR} + 10\log_{10}L\) and, with True delays ticked, reports how many signals were found, how many peaks are false alarms, and the largest timing error. Tick Moving average to overlay an \(L\)-sample averager scaled to the same output noise level and see why matching the template shape matters.

This MicroSim supports Chapter 4: Convolution and Correlation.

How to Use

  1. Choose a Template.
  2. Lower the Input SNR until you can no longer see the templates in the received signal. Check whether the correlation peaks still stand out.
  3. Set the Number of signals from 1 to 5. Delays are random and at least 1.5 template lengths apart.
  4. Adjust the Threshold and watch the trade-off between missed signals and false alarms in the summary box.
  5. Press New Noise for a new noise record and new delays.
  6. Untick True delays to hide the answers and try to locate the signals from the correlation alone.

Mathematical Concepts

Filtering \(r[n]\) with the matched filter gives the same numbers as the cross-correlation, delayed by \(L - 1\) samples: \((r * h)[m + L - 1] = R_{rs}[m]\). Correlation and matched filtering are the same operation.

Define the input SNR as the average template power divided by the noise variance, \((E_s/L)/\sigma^2\). The peak SNR at the matched filter output is \(E_s/\sigma^2\), which is \(L\) times larger. In decibels the gain is \(10\log_{10}L\): 16.8 dB for the 48-sample templates and 17.2 dB for the 52-sample Barker code. No other linear filter does better in white noise. The noise in the normalized correlation has standard deviation \(\sigma_c = \sigma/\sqrt{E_s} = 1/\sqrt{L \cdot \text{SNR}}\), so \(\sigma_c = 0.14\) at 0 dB, 0.20 at \(-3\) dB and 0.46 at \(-10\) dB for \(L = 48\). The measured SNR printed beside each peak is \(20\log_{10}(\text{peak}/\sigma_c)\).

A plain \(L\)-sample moving average is the matched filter only for a rectangular pulse. For a template that changes sign it adds up positive and negative parts, so its peak is much smaller than the matched filter's 1.00: 0.11 for the sine burst, 0.16 for the chirp and 0.38 for the Barker code.

Template Samples Correlation peak shape (noise-free)
Rectangular pulse 48 Triangle, 47 lags above 0.5, so noise easily shifts the maximum by several samples
Sine burst (4 cycles) 48 Narrow main lobe but side peaks of 0.75 at \(\pm 12\) samples (one period) and negative lobes of \(-0.88\) at \(\pm 6\)
Chirp, 0.02 to 0.25 cycles per sample 48 Single narrow peak (pulse compression); largest side lobe has magnitude 0.33
Barker-13 code, 4 samples per chip 52 Narrow peak; every side lobe is no larger than 1/13 = 0.077

Lesson Plan

Learning Objectives

By the end of this activity, students will be able to:

  1. Explain how cross-correlation locates a known pattern inside a longer signal.
  2. Relate the matched filter to the time-reversed template and to cross-correlation.
  3. Calculate the expected peak SNR from the input SNR and the template length.
  4. Analyze how input SNR, template length and threshold affect missed detections and false alarms.
  5. Compare templates by the sharpness of their correlation peaks and the resulting timing accuracy.

Target Audience

Undergraduate students in signals and systems or communications courses. Plan 20 to 30 minutes.

Prerequisites

  • Discrete convolution and correlation
  • Signal energy and power, decibels
  • Basic idea of random noise and standard deviation

Activities

Activity 1: Find the signals blind (5 min). Load the page and leave Chirp, Number of signals 3, Input SNR 0 dB and Threshold 0.50, but untick True delays. Can you find the three signals by eye in the top plot? Then read the lags of the three correlation peaks and tick True delays. On the first load the peaks are at lags 112, 358 and 476 with measured SNRs of 16.9, 15.8 and 17.4 dB, close to the expected \(0 + 16.8 = 16.8\) dB, and the summary reads "Detected 3 of 3 signals, 0 false alarms".

Activity 2: The threshold trade-off (10 min). Set Input SNR to \(-3\) dB (expected peak SNR \(-3 + 16.8 = 13.8\) dB). For each threshold below, press New Noise ten times and tally missed signals and false alarms in the summary box. Averaged over 500 noise records the chirp gives:

Threshold Signals missed False alarms per record
0.35 about 1% about 2.9
0.50 about 1% about 1.3
0.70 about 6.5% about 0.07
0.90 about 31.5% about 0.01

Your ten records will vary around these values. Explain why no threshold gives zero misses and zero false alarms at the same time.

Activity 3: Below the noise floor (5 min). Lower Input SNR to \(-10\) dB. The expected peak SNR is only \(-10 + 16.8 = 6.8\) dB, and \(\sigma_c = 0.46\), so noise peaks in the correlation are as tall as the signal peaks. Over 500 records the chirp misses about 45% of the signals and gives about 4.4 false alarms per record at every threshold from 0.20 to 0.70. Check this by changing the threshold between 0.20 and 0.70 over ten records, then raise it to 1.00. To get a usable detector at this noise level, would you rather lengthen the template or raise the input SNR? Answer with \(10\log_{10}L\).

Activity 4: Template shape and the moving average (10 min). Set Input SNR to 0 dB and Number of signals to 3.

  • Select Rectangular pulse and press New Noise ten times, reading the largest timing error in the summary box each time. Repeat with the Chirp. The pulse typically shows 1 to 6 samples (median 2 over 500 records); the chirp shows 0 in nearly every record.
  • Select Sine burst, set Input SNR to 20 dB and tick Moving average. The correlation peaks reach 1.0 while the dashed average stays below about 0.11, because four complete cycles sum to zero.
  • Select Rectangular pulse with Moving average ticked. The dashed curve lies exactly on the correlation, because the averager is the matched filter for a rectangle.

Assessment

  1. A 52-sample Barker template arrives at an input SNR of 3 dB. What peak SNR do you expect at the matched filter output? \(3 + 10\log_{10}52 = 3 + 17.2 = 20.2\) dB.
  2. Why is \(h[n] = s[L-1-n]\) called the matched filter, and how is its output related to the cross-correlation? Convolving \(r[n]\) with the time-reversed template gives \(\sum_k r[k]\,s[k-(n-L+1)] = R_{rs}[n-L+1]\), the cross-correlation delayed by \(L-1\) samples.
  3. At 0 dB the chirp usually shows 0 samples of timing error but the rectangular pulse shows several. Why? The chirp's correlation falls from 1 to 0.62 in one sample, so noise cannot move its maximum far; the pulse's correlation is a triangle 47 lags wide above half height, so a small noise bump moves the maximum several samples.
  4. At \(-3\) dB, raising the threshold from 0.35 to 0.70 removes almost all false alarms but misses about 6.5% of the signals. Why can you not have both zero misses and zero false alarms? Signal peaks sit at \(1 \pm 0.20\) and noise peaks of 0.35 to 0.70 also occur, so the two distributions overlap and any threshold trades one error for the other.
  5. With the sine burst and Moving average ticked, why is the averager output nearly flat where the signals are? Four complete cycles sum to zero, so an averager window covering the whole burst outputs about zero; its largest value is 0.11, against 1.00 for the matched filter.

Common Misconceptions

  • "Any smoothing filter detects as well as a matched filter." Tick Moving average with the chirp, sine burst or Barker template: the averager peak is 0.16, 0.11 or 0.38 of the matched filter's peak. Only the rectangular pulse is matched by an averager.
  • "A signal below the noise level cannot be detected." At \(-3\) dB the noise power is twice the template power and the received trace shows no obvious pattern, yet with the threshold at 0.70 about 93.5% of the signals are found with almost no false alarms.

References

  1. Matched filter - Wikipedia - definition of the matched filter and its SNR optimality
  2. Cross-correlation - Wikipedia - definition, properties and use in pattern detection
  3. Barker code - Wikipedia - binary codes with side lobes no larger than 1/N
  4. Pulse compression - Wikipedia - why a chirp gives a long pulse and a narrow correlation peak
  5. The Scientist and Engineer's Guide to Digital Signal Processing - Steven W. Smith - free online textbook with chapters on convolution and correlation
  6. Turin, G. L. (1960). An introduction to matched filters. IRE Transactions on Information Theory, 6(3), 311-329. - the classic tutorial paper
  7. Oppenheim, A. V., & Schafer, R. W. (2010). Discrete-Time Signal Processing (3rd ed.). Pearson. - standard textbook treatment of convolution and correlation