Skip to content
Signal Theory

Correlation: autocorrelation, Wiener-Khinchin, radar and GPS

Autocorrelation and its properties with proof, the Wiener-Khinchin theorem, cross-correlation and delay estimation, radar, Barker codes, GPS and the matched filter.

4 min read 0 comments

How similar are two signals? And how similar is a signal to itself shifted in time? Correlation answers these questions, and it is the tool with which a radar measures distance, a GPS receiver computes position, a modem synchronises and a system recognises a known signal buried in noise. In this lesson we cover autocorrelation, its properties, its link with the spectrum and cross-correlation.

Autocorrelation

For an energy signal (real, for simplicity) the autocorrelation is

    \[ R_x(\tau) = \int_{-\infty}^{+\infty} x(t + \tau)\,x(t)\,dt \]

Shift the signal by \tau, multiply it by the original and compute the area: if the two copies overlap well the product is mostly positive and the area is large, otherwise positive and negative contributions cancel.

Properties.

  • R_x(0) = \int x^2\,dt = E: at zero the autocorrelation is the energy;
  • R_x(-\tau) = R_x(\tau): it is even;
  • |R_x(\tau)| \le R_x(0): the maximum is at zero.

Proof of the last one. By the Cauchy-Schwarz inequality for integrals, \left|\int f g\right| \le \sqrt{\int f^2}\sqrt{\int g^2}. With f(t) = x(t + \tau) and g(t) = x(t), both integrals under the roots equal E, because shifting a signal does not change its energy: |R_x(\tau)| \le E = R_x(0). ∎

No shifted copy resembles the signal more than the signal itself. The width of the central peak says how quickly the signal “forgets” itself: narrow for signals that change quickly (wide bandwidth), wide for slow signals.

The link with the spectrum

Theorem (Wiener-Khinchin, for energy signals). The Fourier transform of the autocorrelation is the energy spectral density:

    \[ \mathcal{F}\{R_x\}(f) = |X(f)|^2 \]

Proof. With the change of variable s = -t one sees that R_x(\tau) = \int x(\tau - s)\,x(-s)\,ds, that is the convolution of x(t) with x(-t). The transform of x(-t) is X(-f) = X^*(f) for a real signal, and by the convolution theorem \mathcal{F}\{R_x\} = X(f)\,X^*(f) = |X(f)|^2. ∎

Autocorrelation loses phase information: different signals with the same amplitude spectrum have the same autocorrelation.

Power signals. For periodic and random signals the time average is used, R_x(\tau) = \lim \frac1T\int_{-T/2}^{T/2}x(t + \tau)x(t)\,dt. Then R_x(0) is the power and the transform is the power spectral density. The autocorrelation of a periodic signal is periodic with the same period: it is used to measure the pitch of a musical note (the first peak after zero) even when the signal is noisy.

Cross-correlation

Between two different signals:

    \[ R_{rs}(\tau) = \int r(t + \tau)\,s(t)\,dt \]

If r contains a delayed copy of s, r(t) = a\,s(t - \tau_0) + n(t), the cross-correlation peaks exactly at \tau = \tau_0: the first term gives a R_s(\tau - \tau_0), largest where copy and original line up, while the noise, which does not resemble s, gives a small random contribution.

Estimating a delay with the cross-correlation between a known code and its noisy copy
At the top the transmitted signal, a short code of positive and negative pulses. In the middle the received signal: the same sequence delayed and covered by noise, almost invisible to the eye. At the bottom the cross-correlation: a sharp peak at the delay τ₀.

Radar. A pulse is transmitted and the received echo is correlated with the transmitted pulse: the peak gives the delay \tau_0, and the distance is d = c\tau_0/2 (there and back). The resolution depends on the width of the peak, that is on the bandwidth: a 1 µs pulse separates targets at least about 150 m apart.

Pulse compression. A short pulse gives good resolution but little energy, hence short range. So a long but “coded” signal is transmitted, for example the 13-element Barker code in the figure, whose autocorrelation has a peak of 13 and side lobes of magnitude at most 1: the energy of a long pulse with the resolution of a short one.

GPS. Each satellite transmits a different pseudo-random code, 1023 elements long. The receiver correlates the received signal with local copies of the codes: the peaks say which satellites are visible and with what delay their signals arrive, and the position is computed from the delays. The GPS signal reaches the ground below the noise level, and correlation brings it out.

Correlation and convolution

The two operations are similar: correlation is a convolution with one of the two signals flipped, R_{rs}(\tau) = r(\tau) * s(-\tau). So correlating with s is the same as passing the signal through a filter with impulse response s(-t), or s(T - t) to make it causal. This is the matched filter, which in the lesson on detection we will prove to be the best possible for recognising a known signal in white noise.

Related articles

Subscribe
Notify of
guest
0 Comments
Oldest
Newest Most Voted
0
Would love your thoughts, please comment.x
()
x