Cross-Correlation Function

Introduction

While auto-correlation measures a signal's similarity to itself at different time lags, cross-correlation measures the similarity between two DIFFERENT signals as one is shifted relative to the other. This is incredibly useful in practice: finding where a known pattern appears in a longer signal (template matching), measuring the time delay between two sensors receiving the same signal (localization), detecting a known signal buried in noise (matched filtering), and synchronizing transmitter and receiver in communications.

For B.Tech students, cross-correlation connects directly to the matched filter — the optimal detector for known signals in noise — making it essential for understanding radar, sonar, and digital communications.

Definition

For Energy Signals

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

This slides $y$ across $x$ and computes their overlap at each lag $\\tau$.

For Power Signals

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

Discrete-Time

$$R_{xy}[m] = \\sum_{n=-\\infty}^{\\infty} x[n] y^*[n-m]$$

Properties

1. Not necessarily even: $R_{xy}(\\tau) \\neq R_{xy}(-\\tau)$ in general. Instead: $R_{xy}(-\\tau) = R_{yx}^*(\\tau)$

2. Bounded by auto-correlations: $|R_{xy}(\\tau)|^2 \\leq R_{xx}(0) \\cdot R_{yy}(0)$ (Cauchy-Schwarz inequality)

3. Relationship to convolution: $R_{xy}(\\tau) = x(\\tau) * y^*(-\\tau)$

4. Fourier transform: $\\mathcal{F}\\{R_{xy}(\\tau)\\} = X(\\omega)Y^*(\\omega) = S_{xy}(\\omega)$ (cross-spectral density)

5. If $y(t) = x(t-d)$ (delayed copy): $R_{xy}(\\tau)$ peaks at $\\tau = d$, revealing the delay

Cross-Correlation vs Convolution

$$R_{xy}(\\tau) = x(\\tau) * y^*(-\\tau)$$

Correlation is convolution with one signal time-reversed (and conjugated). The key difference:

• Convolution: flip AND slide (used for system output calculation)
• Correlation: slide without flipping (used for similarity measurement)

In the frequency domain: Correlation gives $X(\\omega)Y^*(\\omega)$ while convolution gives $X(\\omega)Y(\\omega)$.

Time Delay Estimation

If $y(t) = x(t - d) + n(t)$ (signal $x$ arrives with delay $d$, corrupted by noise):

$$R_{xy}(\\tau) = R_{xx}(\\tau - d) + R_{xn}(\\tau)$$

If noise is uncorrelated with the signal ($R_{xn} \\approx 0$), the cross-correlation peaks at $\\tau = d$, directly revealing the time delay. This principle is used in:

• Sonar: Measuring distance to underwater objects
• GPS: Measuring satellite-to-receiver propagation time
• Microphone arrays: Estimating direction of arrival from inter-mic delays
• Seismology: Locating earthquake epicenters

The Matched Filter as Cross-Correlator

The matched filter for detecting signal $s(t)$ in noise has impulse response $h(t) = s^*(T-t)$ (time-reversed conjugate of the expected signal). Its output is:

$$y(t) = r(t) * h(t) = \\int r(\\tau) s^*(\\tau - (t-T)) d\\tau = R_{rs}(t-T)$$

The matched filter output IS the cross-correlation (evaluated at a specific time). This maximizes the output SNR at the decision instant — it's the optimal detector.

Worked Examples

Example 1: Find $R_{xy}(\\tau)$ for $x(t) = e^{-t}u(t)$ and $y(t) = e^{-2t}u(t)$.

$$R_{xy}(\\tau) = \\int_{-\\infty}^{\\infty}x(t)y(t-\\tau)dt$$

For $\\tau \\geq 0$: $R_{xy}(\\tau) = \\int_{\\tau}^{\\infty}e^{-t}e^{-2(t-\\tau)}dt = e^{2\\tau}\\int_{\\tau}^{\\infty}e^{-3t}dt = \\frac{e^{-\\tau}}{3}$

For $\\tau < 0$: $R_{xy}(\\tau) = \\int_0^{\\infty}e^{-t}e^{-2(t-\\tau)}dt = e^{2\\tau}\\int_0^{\\infty}e^{-3t}dt = \\frac{e^{2\\tau}}{3}$

$$R_{xy}(\\tau) = \\begin{cases} \\frac{1}{3}e^{-\\tau} & \\tau \\geq 0 \\\\ \\frac{1}{3}e^{2\\tau} & \\tau < 0 \\end{cases}$$

Example 2: Two microphones are 1 meter apart. A sound arrives and the cross-correlation peaks at $\\tau = 2$ ms. Find the angle of arrival.

Time difference: $\\Delta t = 2$ ms. Speed of sound: $c = 340$ m/s.

Path difference: $d = c \\cdot \\Delta t = 340 \\times 0.002 = 0.68$ m

Angle: $\\sin\\theta = d/D = 0.68/1.0$, so $\\theta = \\arcsin(0.68) \\approx 42.8°$

Normalized Cross-Correlation

The normalized cross-correlation coefficient at lag $\\tau$:

$$\\rho_{xy}(\\tau) = \\frac{R_{xy}(\\tau)}{\\sqrt{R_{xx}(0) \\cdot R_{yy}(0)}}$$

This ranges from -1 to +1:

• $\\rho = +1$: Signals are identical (possibly scaled) at that lag
• $\\rho = 0$: Signals are uncorrelated at that lag
• $\\rho = -1$: Signals are anti-correlated (one is the negative of the other)

Applications

• Template matching: Find where a known pattern occurs in data
• Time delay estimation: Peak of $R_{xy}$ reveals propagation delay
• Radar/Sonar: Cross-correlate received echo with transmitted waveform
• Communications: Synchronization and code acquisition in CDMA/GPS
• Image registration: Align two images by finding the shift that maximizes correlation
• Direction of arrival: Estimate sound/RF source direction from multi-sensor delays

Key Takeaways

• Cross-correlation measures similarity between two signals as a function of time lag
• Related to convolution: $R_{xy}(\\tau) = x(\\tau) * y^*(-\\tau)$ (correlation = convolution with time reversal)
• Peak location reveals time delay between signals — basis for localization and ranging
• The matched filter output is the cross-correlation — optimal for signal detection in noise
• FT of cross-correlation gives cross-spectral density: $S_{xy}(\\omega) = X(\\omega)Y^*(\\omega)$
• Not symmetric in general: $R_{xy}(\\tau) \\neq R_{yx}(\\tau)$ unless $x = y$