Filming is currently underway on a special online course based on this blog which will include videos, animations and work-throughs to illustrate, in a visual way, how the Fourier Transform works, what all the math is all about and how it is applied in the real world.
Click here to reserve your free module
The module will be emailed to you the moment the course goes live.
Before I show you my special FFT Calculator which I wrote based on all the things we have covered in this blog, let me keep you in suspense a little longer while we review what we’ve learned in the blog. (…or I could just cut the c#@p and you can click here to go straight to the calculator)
Review of the Fourier Transform Blog
Over the course of this Blog series we’ve taken a detailed look into the workings of the Fourier Transform. I’ve been looking at the Fourier Transform through the eyes of a sound engineer, using it to analyze sound signals. However, the Fourier Transform is more versatile than that. It is used to analyze all manner of signals such as pictures and even video.
In Part 1, we looked at the motivation behind the Fourier Transform, as a tool used to give us information about our signal.
In Part 2, we saw that any signal can be seen as a collection of sine waves and we considered how we might modify those sine waves, playing with their properties of Frequency and Amplitude and adding them together to make more complex, richer sounds.
In Part 3, we added phase to the list properties we can play with, shifting the waves in time.
In Part 4, we looked at Complex Numbers, the language used to describe the Fourier Transform algorithm.
In Part 5, we looked at Convolution, the way that we can measure the phase, amplitude and frequency of the different sine waves present in a signal by testing it with Cosine and Sine waves at known frequencies.
In Part 6, we looked at the Fourier Transform equation itself and understood via the language of Complex Numbers what exactly it was doing.
In Part 7, we noticed that there was a problem with the Fourier Transform as it stands in that it makes a number of inconvenient assumptions about our ability to deal with infinities. Therefore we modified the Fourier Transform equation a little to make it more Discrete.
In Part 8, we found that making the Fourier Transform discrete presented us with a new problem of spectral leakage as the Fourier Transform assumes that signals go on forever, something that is not true in our real world of finite things. Therefore we saw how Windowing helped reduce the problem.
In Parts 9 – 12, we began to look at how we would implement the Fourier Transform on a computer and noticed that there was a problem in that it required a very large number of complex computations to calculate. However, to our rescue came Cooley and Tukey who noticed that there were are large number of computations that were repeating themselves within the Fourier Transform. This discovery enabled them to develop a special algorithm called the Fast Fourier Transform which remembered the repeating computations meaning they could be reused in later stages of the calculation.
In Part 13, we did a numerical example and worked our way through a 16-point FFT.
In Part 14, we wrote our own implementation of the FFT in JavaScript.
And now, in Part 15, the final post in the series (yes I know I’ve said that before), we’re going to actually run the algorithm on a signal and look at the different stages of the FFT calculation.
I used the code from Part 14 to write an implementation in JavaScript that should hopefully (if I’ve got all the bugs out) run in your browser. This is an FFT calculator which lets you take a peek at the different stages of the computation.
The FFT Calculator
There are 6 different screens in the calculator:
In the first screen, you plug in the values of the sample you want to analyze. Each line should contain a numeric value representing the amplitude of that sample. REMEMBER: Your signal must contain a number of samples that is a power of 2 (e.g. 2, 4, 8, 16, 32, 64, … etc.) Alternatively, you can use one of the 7 test signals I’ve prepared for you. Just select the test signal you want to use from the select box on the first screen. If your signal contains a valid number of samples, a “Next” button will appear at the top of the calculator. Click it to proceed to the next screen.
In the second screen, you will see a graph of your signal. This is a time domain graph and shows you the amplitude of each sample you entered. Click “Next” to continue. Alternatively you can click “Previous” to go back to the previous screen.
In the third screen, you will see a summary of the FFT that is about to be performed on your signal. The summary details how many samples there are in your signal, how many stages there will be to the FFT calculation, how many groups of butterflies there are in each stage and how many butterflies there are in each group. You can then select which specific butterfly in which group and in which stage of the calculation you would like to see by pressing on the “Show Butterfly” button. If you are a little confused as to what a stage, group of butterfly is, just scroll down the page to see an example of a butterfly diagram for a 16-point FFT. Once you have seen all the butterflies you want, click “Next”. Alternatively you can click “Previous” to go back to the previous screen.
In the fourth screen, you will see a table containing all the result of the final stage of the FFT calculation. For each frequency index, you will see the Cosine contribution and the Sine contribution. Next to that, you will see the magnitude of that frequency calculated using Pythagoras’ Theorem, and the phase (in degrees) of that frequency calculated using the inverse tangent rule. Click “Next” to go to the next screen or click “Previous” to go back to the previous screen.
In the fifth screen, you will see a frequency domain graph of the Magnitude of each frequency. Click “Next” to go to the next screen or click “Previous” to go back to the previous screen.
In the sixth screen, you will see a frequency domain graph of the Phase of each frequency. This is the final screen in the calculator. Click “Back to Start” to go to back to the first screen and try out a new signal or click “Previous” to go back to the previous screen.
