What is the Fourier transform?
Previous article: 1. Fourier transform for confused engineers
What is the Fourier transform, really?
For some, it is the magic of seeing everything as waves. For others, it is like holding a prism in a beam of sunlight and seeing what it contains, a rainbow of colors. For some others, it is a tool to visualize what a piece of sound recording contains and adjusting it to make it sound better.
One can even take the romanticism out of the concept and say, it converts a bunch of given numbers into another bunch. It is through doing this that many important uses of Fourier transform can be realized. And this is precisely where many miss the woods for the trees. I hope to bridge both sides of this amazing idea. Let us begin!
When we have a clearly defined function, as shown in the plot below, everything is straightforward.
This means that we have a known expression for how the function depends on the variable x
:
All the nice definitions of the Fourier transform become useful and if the integral is not monstrous, we would have a good looking expression for the Fourier transform of the function. Life is tricky and usually we only have some values of the function at hand. Like:
Most of the time, we just have the data points as shown by the red dots. You can imagine a function passing through the data like the blue line. But it does not matter. Now, it is just us and the red dots. The entire business of discrete Fourier transform (DFT) is to take the Fourier transform of such a bunch of data points. Before I throw some formulas at you, there are some ground rules to cover.
-
The universe plays the game strict and fair. If you have
values in the data set, you will only get back number of values from the DFT. If you are getting anything more than values, then some of them are definitely redundant. -
The most common data points are spaced (sampled) uniformly as equi-distant points in
. This is usually the case since most of the digital systems sample signals at a given rate. We shall always assume this to be true in our discussions. If your samples are non-uniformly spaced, you might want to look elsewhere. -
The DFT models the data (and the underlying function - the blue line) using sines and cosines. Not just any sines and cosines. Some that are chosen particularly for the current dataset.
-
Euler’s identity is the key to everything and never lose sight of it:
With all this preamble aside, let us look at how DFT is defined for a given set of
And it is also given that these points are spaced at intervals
Now, we shall use a trick to tell the DFT that our set of points is periodic, even though they are actually not. Imagine that the given set of points are repeated infinitely on both sides, like:
This would make the graph look like:
We have got the function looking like a periodic function. But what is the period of our function (the repeated pattern in the plot above)? How long does a single period span in
But we usually do not include the last point
Now that we got that clarified, the DFT for our data points is given by the strange looking formula:
We need to understand what this formula says in all its glory.
P.S.: Have you noticed that the period
Next article: (In preparation)
Previous article: 1. Fourier transform for confused engineers