Auto-correlation, also called series correlation, is the correlation of a given sequence with itself as a function of time lag. Cross-correlation is a more generic term, which gives the correlation between two different sequences as a function of time lag.

Check this ebook : Simulation of Digital Communications using Matlab – by Mathuranathan Viswanathan

Given two sequences \(x\) and \(y\), the cross-correlation at times separated by lag i is given by ( \(*\) denotes complex conjugate operation)

$$ R_{{xy}_i}=Corr(x,y)_i = \sum_{j=-\infty}^{\infty} x_j y^*_{j+i} $$

Auto-correlation is a special case of cross-correlation, where \(x=y\). Once use a brute force method (using for loops implementing the above equation) to compute the auto-correlation sequence. However, other alternatives are also at your disposal.

## Method 1: Auto-correlation using xcorr function

For a N-dimensional given vector \(x\), the Matlab command \(xcorr(x,x)\) or simply \(xcorr(x)\) gives the auto-correlation sequence. For the input sequence \(x=[1,2,3,4]\), the command \(xcorr(x)\) gives the following result.

1 2 3 |
>> x=[1 2 3 4] >> acf=xcorr(x) acf= 4 11 20 30 20 11 4 |

## Method 2: Auto-correlation using Convolution

Auto-correlation sequence can be computed as the convolution between the given sequence and the reversed (flipped) version of the conjugate of the sequence.The conjugate operation is not needed if the input sequence is real.

1 2 3 |
>> x=[1 2 3 4] >> acf=conv(x,fliplr(conj(x))) acf= 4 11 20 30 20 11 4 |

## Method 3: Auto-correlation using Toeplitz matrix

Auto-correlation sequence can be found using Toeplitz matrices. An example for using Toeplitz matrix structure for computing convolution is given here. The same technique is extended here, where one signal is set as input sequence and the other is just the flipped version of its conjugate. The conjugate operation is not needed if the input sequence is real.

1 2 3 |
>> x=[1 2 3 4] >> acf=toeplitz([x zeros(1,length(x)-1)],[x(1) zeros(1,length(conj(x))-1)])*fliplr(x).' acf= 4 11 20 30 20 11 4 |

## Method 4: Auto-correlation using FFT/IFFT

Auto-correlation sequence can be found using FFT/IFFT pairs. An example for using FFT/IFFT for computing convolution is given here. The same technique is extended here, where one signal is set as input sequence and the other is just the flipped version of its conjugate.The conjugate operation is not needed if the input sequence is real.

1 2 3 4 |
>> x=[1 2 3 4] >>L = 2*length(x)-1 >> acf=ifft(fft(x,L).*fft(fliplr(conj(x)),L)) acf= 4 11 20 30 20 11 4 |

Note that in all the above cases, due to the symmetry property of auto-correlation function, the center element represents \(R_{xx}(0)\).

## Construction the Auto-correlation Matrix

Auto-correlation matrix is a special form of matrix constructed from auto-correlation sequence. It takes the following form.

$$

\begin{bmatrix}

R_{xx}(0) & R_{xx}^*(1) & R_{xx}^*(1) & \cdots & R_{xx}^*(N-1) \\

R_{xx}(1) & R_{xx}(0) & R_{xx}^*(1) & \cdots & R_{xx}^*(N-2) \\

R_{xx}(2) & R_{xx}(1) & R_{xx}(0) & \cdots & R_{xx}^*(N-3) \\

\vdots & \vdots & \vdots & \ddots & \vdots \\

R_{xx}(N-1) & R_{xx}(N-2) & R_{xx}(N-3) & \cdots & R_{xx}(0)

\end{bmatrix}

$$

The auto-correlation matrix is easily constructed, once the auto-correlation sequence \(R_{xx}(0), R_{xx}(1),…, R_{xx}(N-1)\) is known. The auto-correlation matrix \(R_x\) is a \(Hermitian\) matrix as well as a \(Toeplitz\) matrix. This property is exploited in the following Matlab code for constructing the Auto-Correlation matrix.

1 2 3 4 |
>> x=[1+j 2+j 3-j] %x is complex >> acf=conv(x,fliplr(conj(x)))% %using Method 2 to compute Auto-correlation sequence >>Rxx=acf(3:end); % R_xx(0) is the center element >>Rx=toeplitz(Rxx,[Rxx(1) conj(Rxx(2:end))]) |

$$

R_x=\begin{bmatrix}

17 & 8+6i & 2+4i \\

8-6i & 17 & 8+6i \\

2-4i & 8-6i & 17 &

\end{bmatrix}

$$

** Rate this article: **

**Articles in this series**

Survey of Methods to Compute Linear Convolution

Polynomials, Convolution and Toeplitz matrices – Connecting the dots

How to Interpret FFT results – complex DFT, frequency bins and FFTShift

How to Interpret FFT results – obtaining Magnitude and Phase information

FFT and Spectral Leakage

How to plot FFT using Matlab – FFT of basic signals : Sine and Cosine waves

Generating Basic signals – Square Wave and Power Spectral Density using FFT

Generating Basic signals – Rectangular Pulse and Power Spectral Density using FFT

Generating Basic Signals – Gaussian Pulse and Power Spectral Density using FFT

Chirp Signal – Frequency Sweeping – FFT and power spectral density

Constructing the Auto Correlation Matrix using FFT (this article)

## References:

[1] Reddi.S.S,”Eigen Vector properties of Toeplitz matrices and their application to spectral analysis of time series, Signal Processing, Vol 7,North-Holland, 1984,pp 46-56

[2] Robert M. Gray,”Toeplitz and circulant matrices – an overview”,Deptartment of Electrical Engineering,Stanford University,Stanford 94305,USA

[3] Matlab documentation help on Toeplitz command