Fourier Transform 101 — Part 4: Discrete Fourier Transform
Previously, we finally stepped into Fourier Transform itself. You can take a look at the previous series from below.
Although the “(Continuous) Fourier Transform” we covered last time is great, practically, it is difficult to use it in real life. This is because, in real life, we are usually dealing with “discrete” data that was sampled using some kind of sensors.
Think of any time series data from traffic, weather, stocks, etc. We get the discrete values at each time point (e.g. 1 second, 2 second, 3 second, etc.) and we don’t know what’s in between those samples. We just need to infer. That’s why usually it is better to have a high sampling frequency (e.g. Instead of 1 sample per second, 100 samples per second.) so that you get a more accurate approximation of the real data.
In this discrete case, we need the “discrete” equivalent version of the Fourier Transform. This is where “Discrete Fourier Transform” comes into play.
I’m following the basic derivation from awesome lectures from Dr. Wim van Drongelen. You can see his lectures on YouTube and I’m posting the video that covers the topic that we are going to discuss today here.
Materials covered in this story
- Understanding the context of Discrete Fourier Transform respect to what we already learned
- Derivation of Discrete Fourier Transform (DFT)
- Introducing Discrete Time Fourier Transform (DTFT)
This will be the last story to discuss about the Fourier Transform and we will be moving on to a more advanced topics from the next story such as Fast Fourier Transform (FFT), Spectrogram, Spectral leakage, Multitaper estimation, etc. So make sure you understand the basics covered in these stories from Part 1–4!
I believe understanding the basics is crucial when it comes to learning something more advanced. This is because you would waste your time trying to understand something more advanced just because you are lacking some knowledge in the basics (and you might need to come back to the basics again which will frustrate you). So if you want to make the most out of your time, try to spend some time learning the basics completely and move on step by step. That’s actually the fastest way to learn something.
Understanding the context of Discrete Fourier Transform respect to what we already learned
So far, we learned the following:
- Real and Complex Fourier Series
- (Continuous) Fourier Transform
and today, we are learning Discrete Fourier Transform often abbreviated as DFT.
The question is, why do we have so many different Fourier Transforms?
Make sure you check Part 3 (Previous story) if you haven’t because I explained this in detail comparing Complex Fourier Series and Fourier Transform over there.
Let’s bring the table that I showed you in Part 3, adding the Discrete Fourier Transform. Don’t worry about the formula for now because we are going to cover this in the later part of this story.
If you remember from last time, the above table can be summarize based on if the formula is dealing with either “Continuous” or “Discrete” and the underlying assumption of the signal is either “Periodic” or “Aperiodic”.
If you just take a moment, you could start seeing some patterns over here. But let’s try to make this more obvious.
In this table, you can see how each Fourier Transform changes its property when moving from time domain to frequency domain and coming back to time domain.
Interesting thing is that the Complex Fourier Series (CFS) radically changes its property when converted into different domains. On the other hand, Fourier Transform (FT) and Discrete Fourier Transform (DFT) stays in one place no matter which domain they are in.
One thing to note is although we explained that the (Continuous) Fourier Transform is extended to aperiodic signal, it is no longer the case for Discrete Fourier Transform (DFT). DFT is dealing with periodic signals and this is the method that we usually use for real world data. This periodicity has some pros and cons. The advantage is that we could use this periodicity to optimize the algorithm. It’s called the Fast Fourier Transform (FFT) and I’m going to explain this in the next story. One of a few problems is that this periodicity leads to spectral leakage which I’m going to explain after the FFT. It may sound difficult now, but you will see when you come back to this story again once you go through the FFT and the spectral leakage.
Derivation of Discrete Fourier Transform (DFT)
I hope you got the basic idea of DFT respect to other Fourier Transforms that we already covered. From here on, let’s see how the formula is derived from the (Continous) Fourier Transform.
Compared to the Complex Fourier Series and Fourier Transform we already derived, this time it’s actually quite easy.
The basic idea here is that we are trying to sample over a finite set of samples (making it discrete) from the continuous form of Fourier Transform.
To summarize, now we have our discrete version of the Fourier Transform called “Discrete Fourier Transform” often abbreviated as “DFT”.
Now let’s look at the inverse version of this as usual.
As always, starting from what we already know, we are trying to sample a finite set of samples to make it discrete.
After the above derivations, we get the inverse version of the DFT.
Introduction to Discrete Time Fourier Transform (DTFT)
I’ll leave the derivation of DTFT to the following material I found on the web. It’s the PDF from Dr.Fearing and you could find many if you are interested.
Just to summarize the formulas here, this is the “Discrete Time Fourier Transform” (DTFT). Try to see what changed from the DFT. I will summarize this in the end of this article, but it’s important that you notice the difference.
And the inverse form of the DTFT.
Summary
OK, now we covered all the 4 types of Fourier Transforms so let’s summarize them into a table.
This is the table with the formulas. Try to figure out what’s the difference among different types of FTs.
OK, now let’s focus on the properties.
- Continuous vs Discrete
- Periodic vs Aperiodic
If you try to see its relationships, the table below summarizes everything.
This table tells you that there are two types of Fourier Transforms.
- 1) No matter if you are in time or frequency domain, it stains in one combination of the properties. (FT and DFT)
- 2) If you switch between time and frequency domain, it also switches the combination of the properties. (CFS and DTFT)
I hope this helps! See you next time!
