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 2
Last time we found out that the Discrete Fourier Transform (DFT), although a hugely powerful tool, can be very time consuming to calculate. In 1965 two mathematicians, James Cooley and John Tukey, published a paper which proposed a method that made the calculation of the DFT much more efficient. Their observation, that Cosine and Sine waves repeat every 2π radians, meant that many of the calculations necessary to compute the DFT of a signal repeated themselves too. If the results of the repeated calculations could be stored and used again the next time the calculation occurred, this could vastly reduce the number of calculations required.
In order to take advantage of this repeating property of Sine and Cosine waves, we use a method known as “Divide and Conquer”. We demonstrated how “Divide and Conquer” works and found that there were 4 stages to the process:
- SPLIT – Keep splitting the samples into groups of half the number of samples until you are left with only a pair of samples in each group.
- CALCULATE – Perform your algorithm on each of the sample pairs.
- COMBINE – Use the results from the calculation you just performed to form the input of the next stage of the problem.
- REPEAT – Keep repeating 2 and 3 until you have an overall answer.
Having completed the splitting stage in the last post, we’re now going to look at how we actually begin to calculate a 2-point DFT (that is a DFT with only 2 samples in it). As we’ll soon discover calculating a 2-point DFT is simplicity itself.
2. Calculate
How comes working out a 2-point DFT is so easy? A 2-point DFT is going to give us only 2 frequencies in its result which we’ll call a(0) and a(1).
To calculate these terms we have to do 4 multiply and 2 add operations. These are:
- Multiply the first sample, x(0), by a Cosine and Sine wave at frequency index k=0.
- Multiply the second sample, x(1), by a Cosine and Sine wave at frequency index k=0
- Add the results from 1 and 2 together: This gives us our first frequency term a(0).
- Multiply the first sample, x(0), by a Cosine and Sine wave at frequency index k=1
- Multiply the second sample, x(1), by a Cosine and Sine wave at frequency index k=1
- Add the results from 4 and 5 together: This gives us our second frequency term a(1).
In order to calculate the first term, a(0), if I plot a Cosine and Sine wave with a frequency index of zero (k=0):
You can see that a Cosine wave with a frequency of zero is simply a straight line with a magnitude of 1. Any signal multiplied by 1 remains unchanged. So if my signal at time 0 is x(0) and my signal at time 1 is x(1), after the multiplication with the Cosine wave, these values will remain the same.
A Sine wave with a frequency of 0 is also a straight line, but it has a magnitude of zero. Any signal multiplied by zero is simple zero so the Sine wave does not play any part in the calculation.
Therefore to calculate our first frequency index a(0), we simply add together the 2 samples of our signal x(0) and x(1):
In order to calculate the second frequency term, a(1), if I plot a Cosine and Sine wave with a frequency index of zero (k=1):
You can see that when the index of our sample is zero, the Cosine wave has an amplitude of 1. Therefore we multiply x(0) by 1.
When the index of our sample is 1, the Cosine wave has an amplitude of -1, Therefore we multiply x(1) by -1.
The Sine wave is again zero at both these sample indexes so again it plays no part in the calculation.
So our second term, a(1), is also very easy to calculate:
This multiplication and addition process for a 2-point DFT can be shown on a special diagram known as a butterfly diagram, so called as its form resembles the wings of a butterfly.
Going back to the bottom row of our divide and conquer diagram…
we perform this operation on each group of 2 samples.
Twiddle Factors
Before we can continue to the next stage of the “Divide and Conquer” method, the combining stage, we need to realize that there has been a bit of a twiddle!
What’s a twiddle?
The definition for the word “twiddle” which my dictionary gives is: “to twist, move, or fiddle with”. Something in the previous stage of the calculation has been fiddled with.
To try and explain what twiddle has been done, I’m going to use the Cosine multiplication at a frequency index of 1 as an example.
If we go back to the graph of our original signal which we saw last time, I’m going to look at the signal as if I had sampled it only twice over its duration at a sample index of 0 and a sample index of 8 as this is what our multiplication for the first 2-point DFT for the first sample pair in the bottom row of the split signal looks like.
We know from our butterfly diagram that in a 2-point DFT, at a frequency index of 1, at sample index 0, the Cosine wave must have and amplitude of 1 and at sample index 8, the Cosine wave must have an amplitude of -1. We can see that this is true from the graph. However, what happens when we try to perform a 2-point DFT and the next 2 points in the bottom row of the split signal? Yes, sample indexes 4 and 12! I’m talking about you!!
As you can see from the graph above, at these 2 sample indexes, the Cosine wave’s amplitude is no longer 1 and -1. As it stands, we cannot use the above graph to calculate a 2-point DFT for samples 4 and 12. We need to do something to it before we perform the first multiplication.
What we do is we twiddle it a bit. We change the phase of the Cosine wave, or in other words we push the whole Cosine wave along the x-axis a bit until it is sitting in the correct position over samples 4 and 12 so that the amplitudes of the Cosine at each point are 1 and -1 respectively. To see what I mean, look at the following animation:
The amount by which we have changed the phase of the Cosine wave for this sample pair is π/2 radians. This shift in phase is why twiddle factors are sometimes referred to as phase factors. Why am I telling you this? Because it is going to be very important in the next post when we combine our 8 groups of 2 samples in to 4 groups of 4 samples.
The Fast Fourier Transform Part 3 >>
