Wave Walker DSP

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: Explaining Time Lags
January 12, 2022

Table of Contents

Introduction

Cross correlation is a mathematical measure of similarity between two signals. The time lag \tau is used to measure the similarity between two signals as they are shifted in time relative to one another by \tau samples. In this blog post examples will be given which explain why time lags are used in the cross correlation equation.

More posts in the cross correlation series:

Cross Correlation Review

The blog post Cross Correlation Explained With Real Signals described how cross correlation compares the similarity of two signals. The examples used signals which:

  • are the same length,
  • and have no relative time delay.

Under these conditions the cross correlation can be simplified to

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

However when the sequences x[n] and y[n] are of unequal length the time lag \tau is needed to time align them and measure their similarity at multiple time delays.

The cross correlation for discrete-time sequences is defined as

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

The time lag \tau is used to apply a relative time shift the two sequences so their similarity can be compared over time. The following section demonstrates an example on calculating cross correlation over multiple values of \tau.

Comparing Different Sequence Lengths

The sequence x[n] is defined according to

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

which has length of 5 samples. Now consider a signal y[n] which has a length of 4 samples,

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

The sequences x[n] and y[n] are plotted in the time domain in Figure 1.

Figure 1: The sequences x[n] and y[n] in the time domain.
Figure 1: The sequences x[n] and y[n] in the time domain.

How can the similarity be compared between x[n], which 4 samples long, and y[n], which is 5 samples long? Since x[n] is shorter than y[n] the first step would be to compare the first 4 samples of x[n] with y[n]. The cross correlation between x[n] and y[n] with no relative time delay (\tau=0) is

(5)   \begin{equation*}\begin{split}R_{xy}[0] & = \sum_{n} x[n] y^*[n] \\& = \sum_{n=0}^{4} x[n] y^*[n] \\& = x[0]y^*[0] + x[1]y^*[1] + x[2]y^*[2] + x[3]y^*[3] + x[4]y^*[4] \\& = (1\cdot 1) + (1\cdot 1) + (1\cdot -1) + (-1\cdot -1) + (0\cdot 1) \\& = 2.\end{split}\end{equation*}

The second step to compare the signals would be to compare the last 4 samples of x[n] with y[n], or equivalently compare x[n] with y[n-1]. The sequences x[n] and y[n-1] are shown in Figure 2.

Figure 2: The time domain sequences for x[n] and y[n-1].
Figure 2: The time domain sequences for x[n] and y[n-1].

The cross correlation between x[n] and y[n] with a \tau=1 sample relative delay is the same as delaying y[n] by 1 sample, y[n-1], and then multiplying it against x[n] and summing the result. The cross correlation at \tau=1 is calculated by

(6)   \begin{equation*}\begin{split}R_{xy}[1] & = \sum_{n} x[n] y^*[n-1] \\& = \sum_{n=0}^{5} x[n] y^*[n-1] \\& = x[0]y^*[-1] + x[1]y^*[0] + x[2]y^*[1] + x[3]y^*[2] + x[4]y^*[3] \\& = (1\cdot 0) + (1\cdot 1) + (-1\cdot 1) + (-1\cdot 1) + (1\cdot -1) \\& = -2.\end{split}\end{equation*}

Question: Does (5) or (6) better represent the cross-correlation between x[n] and y[n]? Which demonstrates the similarity of the two sequences better?

Answer: Both (5) and (6) represent a portion of the cross-correlation between x[n] and y[n]. Neither of the two cross-correlation values is more important or carries more information, they are measuring the similarity at different time delays.

While this example only compared the sequences for two values of \tau, cross correlation is used over much longer sequences and more values of \tau to fully characterize the similarity between two sequences. One way this characterization is applied is by searching for a known sequence.

Cross Correlation for Sequence Detection

Cross correlation can be used to locate a known sequence c[n] within a longer sequence y[n]. The cross correlation is defined by

(7)   \begin{equation*}R_{yc}[\tau] = \sum_{n} y[n] c^*[n-\tau].\end{equation*}

The cross correlation (7) slides the sequence c[n] through y[n] through multiple time delays c[n-\tau].

Comparing the similarity between the two sequences at multiple time lags \tau is a gauge as to the most likely location of the known sequence. The time lag T is defined when the location of the known sequence when |R_{yc}[\tau]| is the maximum value. Mathematically this is stated by:

(8)   \begin{equation*}T = \arg \max_{\tau} |R_{yc}[\tau]|\end{equation*}

where T is the starting sample of the sequence c[n] within y[n].

The following example shows how to use cross correlation to find a known sequence, a Barker code, in the middle of a series of random and noisy symbols.

The length 13 Barker code is defined as

(9)   \begin{equation*}c[n] = \begin{cases}1, & n = 0 \\1, & n = 1\\1, & n = 2\\1, & n = 3\\1, & n = 4\\-1, & n = 5\\-1, & n = 6\\1, & n = 7\\1, & n = 8\\-1, & n = 9\\1, & n = 10\\-1, & n = 11\\1, & n = 12\\\end{cases}.\end{equation*}

The longer sequence y[n] is a series of 32 random samples from +1 and -1, followed by the same Barker code, followed by 32 more random +1 and -1 samples, with white Gaussian noise added to all of the samples. The Barker code c[n] is plotted in Figure 3 and the noisy sequence y[n] is plotted in Figure 4.

Figure 3: The length 13 Barker code sequence c[n].
Figure 3: The length 13 Barker code sequence c[n].
Figure 4: The noisy sequence y[n] is 32 random samples of +1 and -1, followed by the Barker code c[n], followed by another 32 random samples of +1 and -1, all with additive white Gaussian noise (AWGN).
Figure 4: The noisy sequence y[n] is 32 random samples of +1 and -1, followed by the Barker code c[n], followed by another 32 random samples of +1 and -1, all with additive white Gaussian noise (AWGN).

The cross correlation R_{yc}[\tau] is plotted in Figure 5. The cross correlation has both positive and negative values which just indicate the polarity of the similarity between the two sequences (see previous post). However, the magnitude of the cross correlation removes the positive or negative sign and the maximum value of the cross correlation can be found from |R_{yc}[\tau], plotted in Figure 6.

Figure 5: The cross correlation between c[n] and y[n], Ryc[tau].
Figure 5: The cross correlation between c[n] and y[n], Ryc[tau].
Figure 6: The magnitude of the cross correlation between c[n] and y[n], |Ryc[tau]|.
Figure 6: The magnitude of the cross correlation between c[n] and y[n], |Ryc[tau]|.

The location of the maximum sample can be found in Python with NumPy’s argmax() function:

import numpy as np
Ryc = np.correlate(y,c,mode='full')
T = np.argmax(Ryc)

where T = 44. The time index be validated by knowing the length of the correlating sequence c[n] (13 samples) and the time offset of c[n] into y[n] (32 samples), such that

(10)   \begin{equation*}T = 13 + 32 -1 = 44\end{equation*}

where the -1 is needed for zero-based indexing.

Conclusion

Cross correlation is calculated over multiple time lags \tau because it provides information about the similarity of two sequences as they are delayed in time with one another. Cross correlation can also be used to find a known sequence within a longer noisy sequence by finding the time index T of the maximum of the absolute value of the cross correlation |R_{yc}[\tau]|.

More posts in the cross correlation series:

Leave a Reply

God, the Lord, is my strength; He makes my feet like the deer's; He makes me tread on my high places. Habakkuk 3:19
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
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