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.
The Fast Fourier Transform – Part 4
So now we finally come to the end of our journey through the Fourier Transform in general and the Fast Fourier Transform in particular. We’ve divided, we’ve calculated and at the end of the last post, we were in the middle of combining our smaller DFTs into larger ones. We’d got as far as a 4-point DFT. We’re now going to combine the four 4-point DFTs into two 8-point DFTs and finally into one 16-point DFT to get the Fourier Transform for our 16 sample signal.
The way we combine the 4-point DFTs into and 8-point DFT is almost identical to the way we combined the 2-point DFTs into 4-point DFTs, the only things that change are the twiddle factors. Below is the butterfly diagram for combining the four 4-point DFTs into two 8-point DFTs.
Starting from the left hand side of the diagram we see the four 4-point FFTs which produce the results b(0) to b(15). These results are then fed into the two 8-point DFTs. Taking the upper 8-point DFT as an example, we see that just as the first 2 terms going into the 4-point DFTs were unaffected by twiddle factors, for an 8-point DFT, it is the first 4 terms that are unaffected by twiddle factors. The next 4 terms however have been twiddled as in order to perform the second 4-point DFT, the Cosine and Sine waves had to be shifted similar to the shifted waves in the 2-point DFTs we spoke about in the last 2 posts. It is the twiddle factors that now shift these waves back to where they should be for the 8-point DFT.
How are these twiddle factors calculated?
Again we see the “W” notation we met last time. The number to the right and above the W indicates the sample index of the 4-point DFT being fed into the input and the the number to the right and below the W indicates the order of DFT we are now calculating. Unsurprisingly, the number is 8 for an 8-point DFT. So the 4 twiddle factors are:
Disregarding the number in blue, we see that each of the twiddle factors has shifted the Cosine and Sine waves by 2π/8 or π/4 radians (or 45° for those who prefer degrees).
Finally, having computed the two 8-point DFTs, we combine everything together into one 16-point DFT. Here is the whole process in a butterfly diagram from the initial samples x(0) to x(15) all the way to the final frequency domain results X(0) to X(15):
This time we see that the first 8 terms, c(0) to c(7), going into the 16-point DFT are unaffected by twiddle factors whereas the second 8 terms, c(8) to c(15) are multiplied by twiddle factors as follows:
Disregarding the number in blue, we see that each of the twiddle factors has shifted the Cosine and Sine waves by 2π/16 or π/8 radians (or 22.5° for those who prefer degrees).
This Divide and Conquer method can extend to any size of FFT, so long the number of samples being fed into the FFT is a power of 2. (2, 4, 8, 16, 32, 64, 128, 256 etc…)
So now we have a method for computing a 16-point FFT, In the next post, I’m going to finally put some numbers to all the theory we have been learning throughout this blog and try and calculate the FFT for a real signal.
