Auto-correlation and Cross-correlation | DSP-101

Measuring Similarity in Signals

How similar is a signal to a slightly delayed copy of itself? How well do two different signals match up when one is shifted in time? These questions are at the heart of correlation, one of the most powerful operations in digital signal processing. Correlation quantifies the relationship between signals across time shifts, and it underlies everything from finding an echo in an audio recording to locking onto a GPS satellite orbiting 20,000 km above you.

Correlation comes in two flavors: auto-correlation, which compares a signal to a shifted version of itself, and cross-correlation, which compares two different signals. Both operations produce a function of the time shift — and the shape of that function reveals structure that would be invisible in the original signals.

Core Idea

Correlation measures how much two signals overlap as one is slid past the other. A large positive peak at lag τ means the signals are very similar when one is shifted by τ. A peak at zero lag in the auto-correlation reveals the signal’s own periodicity.

Auto-correlation: A Signal Looking at Itself

The auto-correlation of a discrete-time signal x[n] is defined as the inner product of the signal with a shifted version of itself, summed across all time:

Auto-correlation

R_{xx}[l] = \sum_{n=-\infty}^{\infty} x[n]\, x[n - l]

R_xx[l] is the auto-correlation at lag l. The sum runs over all sample indices n, multiplying the signal with a copy delayed by l samples.

At lag l = 0, every sample multiplies itself, so R_xx[0] equals the total signal energy. This is always the maximum value of the auto-correlation — no shifted version of a signal can correlate with it more strongly than the signal correlates with itself at zero delay.

The auto-correlation function is always symmetric: R_xx[l] = R_xx[−l]. This even symmetry makes sense intuitively — delaying by l or by −l gives the same degree of self-similarity.

Detecting Periodicity

If x[n] is periodic with period N, its auto-correlation has peaks at lags 0, ±N, ±2N, … . This makes the auto-correlation an excellent tool for finding hidden periodicities in noisy signals — even when the periodicity is invisible in the time-domain waveform.

Cross-correlation: Comparing Two Signals

When we ask “do these two signals share common structure?” or “how much does one signal look like another, shifted in time?” we compute the cross-correlation. For signals x[n] and y[n]:

Cross-correlation

R_{xy}[l] = \sum_{n=-\infty}^{\infty} x[n]\, y[n - l]

R_xy[l] is the cross-correlation of x and y at lag l. Unlike auto-correlation, cross-correlation is generally not symmetric: R_xy[l] ≠ R_xy[−l].

The cross-correlation peaks at the lag where the two signals best align. If y[n] is simply x[n] delayed by d samples — as in an echo or multipath reflection — then R_xy[l] will have a sharp peak at l = d. This is the key to time-delay estimation.

GPS

Cross-correlates PRN codes to find satellite delay

SONAR

Finds range by cross-correlating transmitted & received pulse

Audio

Estimates room acoustics via auto-correlation of reflections

Correlation vs. Convolution

Correlation and convolution are closely related but not identical. Convolution flips one signal and slides it over the other — it is the fundamental tool for computing the output of an LTI system. Correlation does not flip — it slides one signal over the other as-is, measuring overlap at each position.

Correlation via Convolution

R_{xy}[l] = x[l] * y[-l]

Cross-correlation of x and y equals the convolution of x with the time-reversed version of y. This relationship enables efficient computation using FFT-based convolution.

This relationship is practically important: it means you can compute any correlation efficiently using the Fast Fourier Transform. The convolution theorem states that convolution in time equals multiplication in frequency, so: compute the FFTs of x and the time-reversed y, multiply them pointwise, and take the inverse FFT. The result is the cross-correlation, in O(N log N) operations instead of O(N²).

Normalized Correlation Coefficient

The raw correlation value depends on signal amplitudes — a loud signal will produce larger correlation values simply because its samples are larger, not because it is more self-similar. To compare correlation across different signals and contexts, we normalize the result.

Normalized Cross-correlation

\rho_{xy}[l] = \frac{R_{xy}[l]}{\sqrt{R_{xx}[0]\, R_{yy}[0]}}

The normalized cross-correlation ρ_xy[l] always lies in [−1, +1]. A value of +1 means perfect positive correlation; −1 means perfect negative correlation; 0 means no correlation at that lag.

Normalized correlation is the preferred metric when you need to know whether two signals are similar in shape regardless of amplitude. It appears throughout pattern recognition, template matching in image processing, and digital communications where a receiver compares a noisy received signal to a known waveform library.

Key Properties

Several properties make correlation a reliable analytical tool. Peak at zero lag: the auto-correlation always achieves its maximum at l = 0, so R_xx[0] ≥ |R_xx[l]| for all l. Symmetry: R_xx[l] = R_xx[−l] for auto-correlation; R_xy[l] = R_yx[−l] for cross-correlation. Linearity: if y = αx, then the cross-correlation scales by α. Spectral relationship: by the Wiener–Khinchin theorem, the Fourier transform of the auto-correlation equals the power spectral density of the signal — a deep link between time-domain structure and frequency content.

Wiener–Khinchin

S_{xx}(e^{j\omega}) = \sum_{l=-\infty}^{\infty} R_{xx}[l]\, e^{-j\omega l}

Auto-correlation ↔ Power Spectral Density via DTFT.

Peak Bound

R_{xx}[0] = \sum_{n} x^2[n] = E_x

The auto-correlation at zero lag equals total signal energy.

Applications

Time-delay estimation: In a stereo microphone array, sound arrives at each microphone at slightly different times. Cross-correlating the two microphone signals gives a peak at the lag corresponding to the inter-microphone delay, from which the direction of the sound source can be computed. This is the basis of beamforming.

Radar and sonar: A radar transmits a known pulse and records the return echo. Cross-correlating the transmitted waveform with the received signal gives a peak at the lag equal to twice the target range divided by the speed of light. The height of the peak indicates target reflectivity; the sharpness indicates range resolution. Using long pulse-compression waveforms allows high energy transmission while maintaining fine range resolution — all via correlation.

GPS acquisition: Each GPS satellite broadcasts a unique pseudo-random noise (PRN) code that repeats every millisecond. A GPS receiver generates a local replica of the expected PRN code and cross-correlates it with the received signal, sliding through all possible time offsets. When the peak appears, the receiver knows the signal’s arrival time and thus the satellite-to-receiver distance. Four such measurements from different satellites yield a position fix. Without fast correlation, GPS as we know it would be computationally impossible.

Speech processing: Auto-correlation is used in pitch estimation algorithms (like AMDF and YIN). The fundamental frequency of a voiced speech sound produces a strong auto-correlation peak at the pitch period. Detecting this peak is far more robust than trying to identify pitch directly from the noisy waveform.

Next lesson: Signal Detection in Noise — how to decide whether a signal is present at all, and the statistical tools (Neyman–Pearson, ROC curves) that govern that decision.

Key Takeaways

Auto-correlation measures a signal’s similarity to a time-shifted version of itself; it is always symmetric and peaks at lag zero (equal to total signal energy).
Cross-correlation measures similarity between two different signals across lags; a peak at lag l indicates the signals align best when one is shifted by l samples.
Cross-correlation equals convolution with the time-reversed second signal, enabling O(N log N) computation via the FFT.
Normalizing by signal energies yields a dimensionless coefficient in [−1, +1] that measures pure shape similarity regardless of amplitude.
The Wiener–Khinchin theorem links auto-correlation to power spectral density, connecting time-domain structure to frequency content.
Correlation underlies GPS acquisition, radar pulse compression, time-delay estimation in microphone arrays, and pitch detection in speech processing.