DSP Algorithms for RF Systems

Trending

Buy the Book!

DSP for Beginners: Simple Explanations for Complex Numbers! The second edition includes a new chapter on complex sinusoids.

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].

Conclusion

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

For everything there is a season, and a time for every matter under heaven. A time to cast away stones, and a time to gather stones together. A time to embrace, and a time to refrain from embracing. Ecclesiastes 3:1,5
The earth was without form and void, and darkness was over the face of the deep. And the Spirit of God was hovering over the face of the waters. Genesis 1:2
Behold, I am toward God as you are; I too was pinched off from a piece of clay. Job 33:6
Enter His gates with thanksgiving, and His courts with praise! Give thanks to Him; bless His name! Psalm 100:4
Lift up your hands to the holy place and bless the Lord! Psalm 134:2
Blessed is the man who trusts in the Lord, whose trust is the Lord. He is like a tree planted by water, that sends out its roots by the stream, and does not fear when heat comes, for its leaves remain green, and is not anxious in the year of drought, for it does not cease to bear fruit. Jeremiah 17:7-8
He said to him, “You shall love the Lord your God with all your heart and with all your soul and with all your mind. This is the great and first commandment. And a second is like it: You shall love your neighbor as yourself. On these two commandments depend all the Law and the Prophets.” Matthew 22:37-39
Then He said to me, “Prophesy over these bones, and say to them, O dry bones, hear the word of the Lord. Thus says the Lord God to these bones: Behold, I will cause breath to enter you, and you shall live." Ezekiel 37:4-5
Riches do not profit in the day of wrath, but righteousness delivers from death. Proverbs 11:4
The angel of the Lord appeared to him in a flame of fire out of the midst of a bush. He looked, and behold, the bush was burning, yet it was not consumed. And Moses said, “I will turn aside to see this great sight, why the bush is not burned.” When the Lord saw that he turned aside to see, God called to him out of the bush, “Moses, Moses!” And he said, “Here I am.” Exodus 3:2-3
Daniel answered and said: “Blessed be the name of God forever and ever, to whom belong wisdom and might. He changes times and seasons; He removes kings and sets up kings; He gives wisdom to the wise and knowledge to those who have understanding." Daniel 2:20-21
Now the Lord is the Spirit, and where the Spirit of the Lord is, there is freedom. 2 Corinthians 3:17
Previous slide
Next slide

This website participates in the Amazon Associates program. As an Amazon Associate I earn from qualifying purchases.

© 2021-2024 Wave Walker DSP