Wave Walker DSP

DSP Algorithms for RF Systems

New Posts Wednesday!

Most Popular

Cross Correlation Explained With Real Signals
December 1, 2021

Table of Contents

Introduction

Cross correlation mathematically measures the similarity of signals. Consider an example where you have a set of data samples represented by x[n] and y[n]. Cross correlation is used to measure on a sample by sample basis how similar x[n] is to y[n]. Simple examples with plots will demonstrate different combinations of positive, negative, strong and weak correlations.

You might enjoy these other posts:

Correlation Function

Correlation for DSP engineers, referred to as cross-correlation, is slightly different than the equation used by statisticians and mathematicians but they share the same underlying principles. The cross-correlation of sequences x[n] and y[n] is given by [gardner1988, p.212]

(1)   \begin{equation*}R_{xy}[\tau] = \sum_{n} x[n] y^*[n-\tau].\end{equation*}

The term \tau is referred to as the “time-lag” and controls the relative time delay between the two sequences. The cross-correlation (1) at \tau=0 calculates the similarity when there is no relative time delay,

(2)   \begin{equation*}R_{xy}[0] = \sum_{n} x[n] y^*[n].\end{equation*}

A special case of the cross-correlation is when x[n] = y[n] is referred to as autocorrelation,

(3)   \begin{equation*}R_{x}[\tau] = \sum_{n} x[n] x^*[n-\tau].\end{equation*}

A large correlation value means the sequences x[n] and y[n] are similar while a large negative correlation means the sequences are similar but have opposite polarity. Small correlation values means the sequences have weak similarity while a correlation of 0 means the sequences have no similarity.

Strong Positive Correlation

Consider a sequence

(4)   \begin{equation*}x_{0}[n] = \begin{cases}1, & n = 0 \\-1, & n = 1 \\1, & n = 2 \\-1, & n = 3 \\0, & \text{otherwise.}\end{cases}\end{equation*}

The sequence x_{0}[n] autocorrelates at \tau=0 (2) according to

(5)   \begin{equation*}\begin{split}R_{x_{0}}[0] & = \sum_{n} x_{0}[n] x_{0}^*[n] \\& = \left( 1 \cdot 1 ) + (-1 \cdot -1) + (1 \cdot 1 ) + (-1 \cdot -1) \\& = 4.\end{split}\end{equation*}

Figure 1 shows that the two sequences are identical at \tau = 0 (no relative time delay) and therefore they should have the maximum correlation value, which in this case is 4. The larger the correlation, the larger the similarity.

Figure 1: The two sequences for the autocorrelation of x0[n] and x0[n].
Figure 1: The two sequences for the autocorrelation of x0[n] and x0[n].

Strong Negative Correlation

Consider a sequence which is the negative of x_{0}[n],

(6)   \begin{equation*}x_{1}[n] = -x_{0}[n]\end{equation*}

such that

(7)   \begin{equation*}x_{1}[n] = \begin{cases}-1, & n = 0 \\1, & n = 1 \\-1, & n = 2 \\1, & n = 3 \\0, & \text{otherwise.}\end{cases}\end{equation*}

The cross-correlation between x_{0}[n] and x_{1}[n] at \tau=0 from (2) is

(8)   \begin{equation*}\begin{split}R_{x_{0}x_{1}}[0] & = \sum_{n} x_{0}[n] x_{1}^*[n] \\& = \left( 1 \cdot -1 ) + (-1 \cdot 1) + (1 \cdot -1 ) + (-1 \cdot 1) \\& = -4.\end{split}\end{equation*}

A negative correlation value means that the two sequences are similar at \tau = 0 (no relative time delay) but have opposite polarity. Figure 2 shows that the two sequences are the same with opposite polarity which is why the cross-correlation in (8) is the maximum negative value, -4.

Figure 2: The two sequences for the cross correlation of x0[n] and x1[n].
Figure 2: The two sequences for the cross correlation of x0[n] and x1[n].

Weak Positive Correlation

Consider a sequence x_{2}[n] which has 1 data point in difference from x_{0}[n] such that

(9)   \begin{equation*}x_{2}[n] =\begin{cases}-1, & n = 0 \\-1, & n = 1 \\1, & n = 2 \\-1, & n = 3 \\0, & \text{otherwise.}\end{cases}\end{equation*}

The cross-correlation between x_{0}[n] and x_{2}[n] at \tau=0 from (2) is

(10)   \begin{equation*}\begin{split}R_{x_{0}x_{2}}[0] & = \sum_{n} x_{0}[n] x_{2}^*[n] \\& = \left( 1 \cdot -1 ) + (-1 \cdot -1) + (1 \cdot 1 ) + (-1 \cdot -1) \\& = 2.\end{split}\end{equation*}

A weak correlation value of 2 in (10) as compared to 4 in (5) means that the two sequences share some similarity at \tau = 0 but are not the exact same. Figure 3 shows that the two sequences are similar but with a single difference at n=0 which is why the cross-correlation in (10) is only 2.

Figure 3: The two sequences for the cross correlation of x0[n] and x2[n].
Figure 3: The two sequences for the cross correlation of x0[n] and x2[n].

Weak Negative Correlation

Consider a sequence x_{3}[n] which has 1 data point the same as x_{0}[n] but the other 3 are opposite polarity such that

(11)   \begin{equation*}x_{3}[n] =\begin{cases}-1, & n = 0 \\1, & n = 1 \\-1, & n = 2 \\-1, & n = 3 \\0, & \text{otherwise.}\end{cases}\end{equation*}

The cross-correlation between x_{0}[n] and x_{3}[n] at \tau=0 from (2) is

(12)   \begin{equation*}\begin{split}R_{x_{0}x_{3}}[0] & = \sum_{n} x_{0}[n] x_{3}^*[n] \\& = \left( 1 \cdot -1 ) + (-1 \cdot 1) + (1 \cdot -1 ) + (-1 \cdot -1) \\& = -2.\end{split}\end{equation*}

A weak negative correlation value of -2 means that the two sequences share some similarity at \tau = 0 with opposite polarity but are not the exact same. Figure 4 shows that the two sequences are similar but with a single sample at n=3 in common, while the other three samples at n=0, 1, 2 are the opposite polarity which is why the cross-correlation in (12) is only -2.

Figure 4: The two sequences for the cross correlation of x0[n] and x3[n].
Figure 4: The two sequences for the cross correlation of x0[n] and x3[n].

Takeaway

Correlation is a way to mathematically measure similarity of two sequences. A large positive correlation means the two sequences are similar whereas a large negative correlation means the two sequences are similar but have opposite polarity. A small correlation value, positive or negative, means the two sequences share few similarities. A correlation value of zero means the two sequences do not share any similarities.

This post covered a subset of the cross-correlation, only for \tau=0, in order to simplify the examples in this introduction. A future blog post will describe why the cross-correlation is computed over all time lags \tau and how cross-correlation is applied in DSP algorithms.

You might enjoy these other posts:

I hope you enjoyed this post explaining correlation, please check out others in the DSP Math series!

Leave a Reply