Correlation

Correlation is a measure of similarity between two sequences or between a sequence and a shifted version of itself. It is a fundamental operation in radar, sonar, communication receivers, and pattern matching. Unlike convolution, correlation does not flip one of the sequences, which is what makes it sensitive to similarity rather than to system response computation.

Core Concept Explanation

Auto-Correlation

The auto-correlation sequence R_xx[l] of a signal x[n] is defined as R_xx[l] = Σ x[n]·x[n−l], where l is the lag variable. It measures how similar a signal is to a shifted version of itself. The value at l = 0 equals the total energy of the signal: R_xx[0] = Σ x²[n]. This is always the maximum value because no shifted version of a signal can correlate more strongly with itself than the zero-shift version. Auto-correlation is an even function: R_xx[−l] = R_xx[l], meaning it is symmetric about the origin.

Cross-Correlation

The cross-correlation sequence R_xy[l] = Σ x[n]·y[n−l] measures the similarity between two different sequences x and y as a function of lag l. When the peak of R_xy[l] occurs at lag l₀, it means y is most similar to x when shifted by l₀ samples. This is directly used in radar and sonar to estimate the time delay of a received echo relative to the transmitted pulse. Unlike convolution, cross-correlation does not flip either sequence; it simply shifts one and computes inner products.

Relation Between Correlation and Convolution

Correlation and convolution are closely related but not identical. The cross-correlation R_xy[l] = x[l] * y[−l], which is the convolution of x[n] with the time-reversed version of y[n]. This is a key identity: to compute cross-correlation using a convolution engine (such as an FFT-based system), one sequence must first be time-reversed. For auto-correlation, R_xx[l] = x[l] * x[−l]. In the frequency domain, the auto-correlation's DTFT equals the power spectral density S_xx(e^jω) = |X(e^jω)|², which is Wiener-Khinchin theorem in discrete time.

Mathematical Expression

For a finite energy sequence of length N, the auto-correlation can be computed efficiently using the DFT. Compute X[k] = DFT{x[n]}, then compute |X[k]|², and finally take the IDFT to obtain R_xx[l]. This FFT-based method reduces the computation from O(N²) to O(N log N). The cross-correlation R_xy[l] can similarly be computed as IDFT{X[k]·Y*[k]}, where Y*[k] is the complex conjugate of Y[k]. These frequency-domain equivalents are central to practical implementations.

Practical Understanding

In communication systems, matched filtering is implemented as cross-correlation between the received signal and a reference template. The filter output peaks at the instant when the received signal best matches the template, which is the optimal detection strategy in white Gaussian noise. In CDMA systems, different users are assigned orthogonal spreading codes, and the receiver correlates the received signal with each code to separate users. Auto-correlation of spreading codes is ideal (close to an impulse) while cross-correlation between different codes is near zero.

Given:
x[n] = {1, 2, 1} for n = 0, 1, 2
Find auto-correlation R_xx[l] for l = 0, 1, 2.

Why this formula applies:
R_xx[l] = Σ x[n]·x[n-l] summed over all valid n

Formula:
R_xx[l] = Σ x[n]·x[n-l]

Substitution:
R_xx[0] = x[0]·x[0] + x[1]·x[1] + x[2]·x[2]
       = 1·1 + 2·2 + 1·1 = 1 + 4 + 1 = 6

R_xx[1] = x[1]·x[0] + x[2]·x[1]
       = 2·1 + 1·2 = 2 + 2 = 4

R_xx[2] = x[2]·x[0]
       = 1·1 = 1

By even symmetry: R_xx[-1] = 4, R_xx[-2] = 1

Calculation:
Full sequence: R_xx = {..., 1, 4, 6, 4, 1, ...} centered at l=0

Final Answer:
R_xx[0] = 6 (total signal energy), R_xx[±1] = 4, R_xx[±2] = 1.

Exam Tip: For GATE, remember R_xx[0] equals total signal energy and is the maximum value of the auto-correlation. The auto-correlation is always even symmetric. Cross-correlation relates to convolution by R_xy[l] = x[l] * y[−l], so flip y before convolving.

Correlation Properties Summary

• R_xx[0] = Σ x²[n] = signal energy, always the maximum of R_xx[l].
• Auto-correlation is even symmetric: R_xx[−l] = R_xx[l].
• Cross-correlation relation: R_xy[l] = R_yx[−l] for real sequences.
• Convolution link: R_xy[l] = x[l] * y[−l]. Flip y[n], then convolve.
• Power Spectral Density: S_xx(e^jω) = DTFT{R_xx[l]} = |X(e^jω)|².

Quick Revision

• Auto-correlation: R_xx[l] = Σ x[n]·x[n−l]. Measures signal self-similarity vs lag.
• R_xx[0] = energy = maximum. R_xx[l] is even symmetric.
• Cross-correlation: R_xy[l] = Σ x[n]·y[n−l]. Peak lag gives time delay estimate.
• Correlation vs convolution: correlation does NOT flip. R_xy[l] = x[l] * y[−l].
• FFT-based auto-correlation: IDFT{|X[k]|²}. Efficient O(N log N) method.
• FFT-based cross-correlation: IDFT{X[k]·Y*[k]}.
• Trap: R_xy[l] ≠ R_yx[l] in general (only R_xy[l] = R_yx[−l] for real sequences).