Autocorrelation

Introduction

Autocorrelation measures how similar a signal is to a delayed version of itself. It answers the question: "If I shift this signal by $\tau$ seconds, how much does it resemble the original?" This self-similarity measure is fundamental to detecting periodicities, estimating spectral content, and characterizing random processes.

If a signal is periodic with period $T$, its autocorrelation will also be periodic with the same period, showing peaks at delays that are multiples of $T$. If a signal is purely random (white noise), its autocorrelation is an impulse at zero delay — indicating no similarity between different time instants. These behaviors make autocorrelation an indispensable tool for signal analysis.

The power of autocorrelation lies in its ability to reveal hidden structure. Even when a periodic signal is buried deep within noise, the autocorrelation function extracts the periodicity because noise contributions average to zero while periodic components reinforce at specific lags. This principle underlies pitch detection, radar signal processing, and spectral estimation algorithms.

Definition

Energy Signals (Deterministic)

$$R_{xx}(\tau) = \int_{-\infty}^{\infty} x(t) x(t+\tau) dt = x(\tau) * x(-\tau)$$

The second form reveals that autocorrelation can be computed as the convolution of the signal with its time-reversed version. This relationship is both computationally and theoretically significant — it connects correlation to filtering theory.

Power Signals (Deterministic Periodic or Random)

$$R_{xx}(\tau) = \lim_{T\to\infty}\frac{1}{2T}\int_{-T}^{T} x(t)x(t+\tau)dt$$

For periodic signals with period $T_0$, this simplifies to: $$R_{xx}(\tau) = \frac{1}{T_0}\int_0^{T_0} x(t)x(t+\tau)dt$$

Discrete-Time

$$R_{xx}[m] = \sum_{n=-\infty}^{\infty} x[n]x[n+m]$$

The lag parameter $\tau$ (or $m$) represents the time shift applied before computing similarity.

Properties

1. Maximum at origin: $R_{xx}(0) \geq |R_{xx}(\tau)|$ for all $\tau$. The signal is most similar to itself at zero delay. $R_{xx}(0)$ equals the signal's energy (or average power for power signals).

1. Even symmetry: $R_{xx}(\tau) = R_{xx}(-\tau)$. Similarity at positive and negative lags is the same. This means the autocorrelation is always symmetric about the origin.

1. Fourier Transform gives PSD: $S_{xx}(\omega) = \mathcal{F}\{R_{xx}(\tau)\}$ (Wiener-Khinchin theorem). This is the fundamental bridge between time-domain correlation and frequency-domain power distribution.

1. DC value: $R_{xx}(0) = E_x$ (total energy) or $R_{xx}(0) = P_x$ (average power).

1. Periodicity preserved: If $x(t)$ is periodic with period $T$, then $R_{xx}(\tau)$ is also periodic with period $T$.

1. Non-negative definite: The Fourier Transform of $R_{xx}$ is non-negative (since PSD $\geq 0$).

1. Value at infinity: For energy signals, $\lim_{\tau\to\infty} R_{xx}(\tau) = 0$. For power signals, $\lim_{\tau\to\infty} R_{xx}(\tau) = |\text{DC component}|^2$.

Worked Example: Computing Autocorrelation

Find the autocorrelation of $x(t) = e^{-2t}u(t)$.

Solution: Apply the definition for energy signals: $$R_{xx}(\tau) = \int_{-\infty}^{\infty} e^{-2t}u(t) \cdot e^{-2(t+\tau)}u(t+\tau)\,dt$$

Case 1: $\tau \geq 0$. Both $u(t)$ and $u(t+\tau)$ require $t \geq 0$, so: $$R_{xx}(\tau) = \int_0^{\infty} e^{-2t} \cdot e^{-2(t+\tau)}\,dt = e^{-2\tau}\int_0^{\infty}e^{-4t}\,dt = \frac{e^{-2\tau}}{4}$$

Case 2: $\tau < 0$. The constraint is $t \geq -\tau$ (from $u(t+\tau)$) and $t \geq 0$ (from $u(t)$). Since $-\tau > 0$, the lower limit is $-\tau$: $$R_{xx}(\tau) = \int_{-\tau}^{\infty} e^{-2t}e^{-2(t+\tau)}\,dt = e^{-2\tau}\int_{-\tau}^{\infty}e^{-4t}\,dt = e^{-2\tau} \cdot \frac{e^{4\tau}}{4} = \frac{e^{2\tau}}{4}$$

Combining both cases using the even symmetry: $$R_{xx}(\tau) = \frac{1}{4}e^{-2|\tau|}$$

Verification: $R_{xx}(0) = 1/4 = \int_0^{\infty}e^{-4t}dt = E_x$ ✓

Autocorrelation of Common Signals

Sinusoid $x(t) = A\cos(\omega_0 t)$: $$R_{xx}(\tau) = \frac{A^2}{2}\cos(\omega_0 \tau)$$ The autocorrelation retains the frequency information but loses phase information. This is why autocorrelation-based methods detect frequency but not phase.

White noise with PSD $N_0/2$: $$R_{nn}(\tau) = \frac{N_0}{2}\delta(\tau)$$ Zero correlation at any non-zero lag — each sample is independent of every other sample.

Exponentially decaying $x(t) = e^{-a|t|}$: $$R_{xx}(\tau) = \frac{1}{2a}e^{-a|\tau|}$$ Correlation decays exponentially with lag, indicating the signal has a "memory" that fades over time.

Sum of sinusoids $x(t) = A_1\cos(\omega_1 t) + A_2\cos(\omega_2 t)$: $$R_{xx}(\tau) = \frac{A_1^2}{2}\cos(\omega_1\tau) + \frac{A_2^2}{2}\cos(\omega_2\tau)$$ Each frequency component contributes independently. Cross terms vanish because uncorrelated sinusoids of different frequencies are orthogonal over infinite time.

Cross-Correlation

While autocorrelation measures self-similarity, cross-correlation measures similarity between two different signals: $$R_{xy}(\tau) = \int_{-\infty}^{\infty}x(t)y(t+\tau)\,dt$$

Cross-correlation is NOT symmetric: $R_{xy}(\tau) = R_{yx}(-\tau)$.

Application: In radar, the received signal is cross-correlated with the transmitted waveform. The peak of the cross-correlation indicates the round-trip delay, from which target range is computed: $d = c\tau_{peak}/2$.

Applications

Periodicity Detection

Autocorrelation is the standard method for detecting hidden periodicities in noisy signals. Even when a periodic signal is buried in noise, the autocorrelation will show peaks at the period $T$ and its multiples. This works because noise autocorrelation decays rapidly, while the periodic signal's autocorrelation persists at all lags.

Example: Pitch detection in speech. The fundamental frequency of a speaker's voice creates peaks in the autocorrelation of the speech signal, enabling robust pitch estimation even in noisy environments. If a peak occurs at lag $\tau_0 = 5$ ms, the fundamental frequency is $f_0 = 1/\tau_0 = 200$ Hz.

PSD Estimation

By the Wiener-Khinchin theorem, the PSD can be estimated by:

1. Computing the autocorrelation estimate $\hat{R}_{xx}[m]$
2. Taking its Fourier Transform

This correlogram method is an alternative to the periodogram for spectral estimation. It naturally produces a smooth estimate and allows windowing to control spectral leakage.

Radar and Sonar

The autocorrelation of the transmitted waveform determines the range resolution of a radar system. Waveforms with impulsive autocorrelation (like chirps after matched filtering) provide fine range resolution. The narrower the main lobe of the autocorrelation, the better you can distinguish two closely spaced targets.

Communication Systems

Autocorrelation of spreading codes in CDMA determines the ability to separate users. Codes with impulsive autocorrelation (good codes) allow clean separation of signals. Gold codes and m-sequences are designed specifically to have low autocorrelation sidelobes.

Computational Considerations

In practice, autocorrelation is computed efficiently using the FFT via the relationship $R_{xx} = \mathcal{F}^{-1}\{|X(\omega)|^2\}$:

1. Compute FFT of $x[n]$: $X[k] = \text{FFT}\{x[n]\}$
2. Compute power spectrum: $|X[k]|^2$
3. Inverse FFT: $R_{xx}[m] = \text{IFFT}\{|X[k]|^2\}$

This has complexity $O(N\log N)$ compared to $O(N^2)$ for direct computation — a significant advantage for long signals.

Key Takeaways

• Autocorrelation measures self-similarity at lag $\tau$: $R_{xx}(\tau) = \int x(t)x(t+\tau)dt$
• Maximum always at $\tau = 0$ (signal is most similar to itself); $R_{xx}(0) =$ energy or power
• Even function: $R_{xx}(-\tau) = R_{xx}(\tau)$
• Fourier Transform of autocorrelation = PSD (Wiener-Khinchin theorem)
• Periodic signals have periodic autocorrelation (preserves frequency, loses phase)
• White noise has impulsive autocorrelation (zero correlation at any non-zero lag)
• Efficient computation via FFT: $R_{xx} = \text{IFFT}\{|X|^2\}$
• Primary applications: periodicity detection, spectral estimation, radar waveform design, pitch detection