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.

Fourier Transform Explanation as a Cross-Correlation
December 22, 2021

Table of Contents

Introduction

For years I accepted the Fourier transform equation on faith without knowing where it came from or why it worked. Were you in the same situation? Are you there now? In this post I describe how the Fourier transform is the cross correlation between a signal x(t) and a complex exponential e^{j 2 \pi f t }. The Fourier transform explanation begins by reviewing cross correlation and then applies it to a complex exponential derive the continuous time and discrete time Fourier transform.

You might enjoy these other blogs on cross-correlation:

Cross Correlation

Recall that cross correlation is a measure of similarity. The cross correlation of x(t) and y(t) gives a mathematical measure of similarity between the two signals at different relative time delays \tau, also called time lags, which is given by

(1)   \begin{equation*}R_{xy}(\tau) = \int_{-\infty}^{\infty} x(t)y^*(t-\tau) ~ dt.\end{equation*}

Similarly for discrete-time sequences the cross correlation of x[n] and y[n] is given by

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

Continuous Time Fourier Transform Explanation

The Fourier transform X(f) = \mathcal{F}\{ x(t) \} describes the frequency content in x(t) at frequency f. In order to analyze the frequency content in x(t) at frequency f it is correlated with a complex exponential e^{j2\pi ft}. Substituting

(3)   \begin{equation*}y(t) = e^{j2\pi f t},\end{equation*}

the Fourier transform can be written as a correlation (1)

(4)   \begin{equation*}\begin{split}R_{xy}(\tau) & = \int_{-\infty}^{\infty} x(t)y^*(t-\tau) ~ dt \\& = \int_{-\infty}^{\infty} x(t) e^{-j2\pi f (t-\tau)} ~ dt.\end{split}\end{equation*}

The complex exponential (3) is periodic and defined over all time t, therefore computing (4) over multiple time lags does not provide any new information. Therefore, (4) can be evaluated at \tau=0,

(5)   \begin{equation*}R_{xy}(0) = \int_{-\infty}^{\infty} x(t) e^{-j2\pi f t} ~ dt\end{split}\end{equation*}

which is the Fourier transform

(6)   \begin{equation*}X(f) = \mathcal{F} \{ x(t) \} = \int_{-\infty}^{\infty} x(t) e^{-j2\pi f t} ~ dt.\end{split}\end{equation*}

Discrete Time Fourier Transform Explanation

The discrete-time Fourier transform (DTFT) is the discrete-time counterpart to the Fourier transform. Where the Fourier transform operates on continuous time signals the DTFT operates on discrete-time sequences. Similar to the continuous time Fourier transform above, the DTFT can be derived by using the cross correlation in (2) and substituting

(7)   \begin{equation*}y[n] = e^{j\omega n}\end{equation*}

where \omega = 2\pi f/f_s and f_s is the sampling frequency. The cross correlation(2) of time-series x[n] with the complex exponential y[n] (7) is given by

(8)   \begin{equation*}\begin{split}R_{xy}[\tau] & = \sum_{n=-\infty}^{\infty} x[n] b^*[n-\tau] \\& = \sum_{n=-\infty}^{\infty} x[n] e^{-j \omega \left( n-\tau \right) }.\end{split}\end{equation*}

Evaluating (8) at \tau=0,

(9)   \begin{equation*}R_{xy}[0] = \sum_{n=-\infty}^{\infty} x[n] e^{-j\omega n }\end{equation*}

leads to the discrete-time Fourier transform

(10)   \begin{equation*}X(e^{j\omega}) = \sum_{n=-\infty}^{\infty} x[n] e^{-j\omega n }.\end{equation*}

Conclusion

The Fourier transform, both continuous-time and discrete-time, is the cross-correlation with an infinitely long complex exponential. The Fourier transform can be derived by calculating cross-correlation with a complex exponential at the time lag \tau=0.

You might enjoy these other blogs on cross-correlation:

If you liked this post you might like the List of Important Math for DSP!

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