Autocorrelation is the cross-correlation of a signal with a delayed copy of itself, producing a function that measures how similar the signal is to itself as a function of lag (time or sample offset). It reveals periodic structure, dominant frequencies, and noise characteristics in a signal without requiring a full spectral decomposition.
In practice
In embedded signal processing, autocorrelation is used to detect periodicity in sampled signals, estimate the fundamental frequency of a waveform, and characterize noise. A classic application is pitch detection in audio: the autocorrelation of a voiced speech or musical signal shows a strong peak at the lag corresponding to the fundamental period, even when harmonics dominate the spectrum and the fundamental frequency component itself is weak or absent. The EmbeddedRelated post "Autocorrelation and the case of the missing fundamental" covers exactly this phenomenon.
Autocorrelation is also used in synchronization and ranging. Spread-spectrum systems exploit the sharp autocorrelation peak of pseudorandom sequences (e.g., Gold codes, m-sequences) to time-align a receiver or measure round-trip delay. In these contexts, computing the autocorrelation via FFT (multiply the spectrum by its complex conjugate, then inverse-FFT) is often more efficient than a direct lag-by-lag sum when the sequence length is large. The EmbeddedRelated post "Delay estimation by FFT" discusses this FFT-based approach.
On resource-constrained MCUs, direct computation of the autocorrelation at L lags over a block of N samples costs O(N·L) multiply-accumulate operations. For short lag ranges and modest block sizes this is tractable in fixed-point arithmetic on DSP-capable cores (e.g., Cortex-M4/M7 with SIMD, DSP56xxx, C2000). For longer transforms, the FFT route reduces complexity to O(N log N) but requires complex arithmetic and sufficient RAM for the frequency-domain buffer.
A common pitfall is interpreting the raw autocorrelation sequence without accounting for the triangular amplitude taper that arises from the finite observation window: lags near ±N have fewer contributing sample pairs and therefore lower energy even for a purely periodic signal. Normalizing by the zero-lag value (R[0], which equals the signal power) converts the result to the normalized autocorrelation, bounded in [-1, 1], which is easier to threshold. Another pitfall noted in "Correlation without pre-whitening is often misleading" is that a signal with strong low-frequency content or a large DC offset can produce a broad, slowly decaying autocorrelation that masks finer periodic structure; high-pass filtering or mean removal before computing autocorrelation often improves the result.
Discussed on DSPRelated
Frequently asked
What is the relationship between autocorrelation and the power spectral density (PSD)?
The Wiener-Khinchin theorem states that the
PSD of a wide-sense stationary signal is the
Fourier transform of its autocorrelation sequence (and vice versa). This means you can estimate the PSD by computing the autocorrelation and then taking its
DFT, or equivalently by squaring the magnitude of the signal's DFT. The two approaches are mathematically equivalent for stationary signals, though they differ in numerical conditioning and windowing behavior in practice.
Why does the autocorrelation always have its maximum at lag zero?
The zero-lag value R[0] equals the mean squared value (power) of the signal. By the Cauchy-Schwarz inequality, |R[k]| <= R[0] for all lags k, so the zero-lag peak is a mathematical guarantee, not a coincidence. A normalized autocorrelation therefore always starts at 1.0 and stays within [-1, 1].
How is autocorrelation used to detect a fundamental frequency when the fundamental is missing from the spectrum?
A periodic signal with fundamental period T produces autocorrelation peaks at lags 0, T, 2T, 3T, ... regardless of which
harmonics are present. Even if the fundamental frequency component has low or zero amplitude (a phenomenon called the missing fundamental), the periodicity at lag T survives because the harmonics collectively reinforce at every integer multiple of T. Pitch detectors based on autocorrelation (such as the YIN algorithm) exploit this property and are more robust to missing fundamentals than peak-picking directly on the magnitude spectrum.
When should I use the FFT-based autocorrelation instead of a direct (lag-by-lag) computation?
The
FFT-based approach -- zero-pad the block to length 2N, compute the
DFT, multiply each bin by its complex conjugate to get the
power spectrum, then inverse-DFT -- is generally faster when you need all N lags and N is large enough that O(N log N) beats O(N^2). The crossover point depends on the processor, but on most MCUs with a hardware FFT or DSP MAC unit, the FFT route wins for N above roughly 64-256. For short lag ranges (e.g., only the first 10-20 lags), the direct sum is usually simpler and cheaper. See also 'Delay estimation by FFT' on EmbeddedRelated.
Does removing the DC offset matter before computing autocorrelation?
Yes, in most practical cases it does. A nonzero mean adds a constant offset of mean^2 to every lag of the autocorrelation, which appears as a broad, non-decaying bias across all lags. This can dwarf the periodic peaks you are trying to detect. Subtracting the sample mean from the block before computing autocorrelation (producing the biased estimate of the autocovariance) is standard practice and usually costs very little extra computation.
Differentiators vs similar concepts
Autocorrelation is often confused with
cross-correlation. Cross-correlation measures the similarity between two *different* signals as a function of lag and is used for tasks like time-of-arrival estimation between a transmitted and received signal. Autocorrelation is the special case where both signals are the same, making it useful for periodicity detection and
PSD estimation rather than inter-signal alignment. Autocorrelation is also distinct from the
DFT magnitude spectrum: the magnitude spectrum shows amplitude per frequency bin, while the autocorrelation shows time-domain self-similarity per lag. They carry equivalent information for stationary signals (via the Wiener-Khinchin theorem) but differ in how that information is presented and computed.
