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 – Numerical Example
What frequencies make up the following signal? This signal has 16 samples in it so we are going to run an 16-point FFT to find out the answer.
The 16 samples in the signal have the following values:
| Sample | Amplitude |
|---|---|
| x(0) | 0.5000 |
| x(1) | 0.5845 |
| x(2) | -0.1768 |
| x(3) | -0.4492 |
| x(4) | -0.2500 |
| x(5) | -0.4492 |
| x(6) | -0.1768 |
| x(7) | 0.5845 |
| x(8) | 0.5000 |
| x(9) | 0.1226 |
| x(10) | 0.1768 |
| x(11) | -0.2579 |
| x(12) | -0.7500 |
| x(13) | -0.2579 |
| x(14) | 0.1768 |
| x(15) | 0.1226 |
Firstly we divide and reorder our samples into groups of 2 using the bit reversal method, so sample x(0) gets grouped with sample x(8). Sample x(4) gets grouped with sample x(12) etc.:
| Sample | Amplitude |
|---|---|
| x(0) | 0.5000 |
| x(8) | 0.5000 |
| x(4) | -0.2500 |
| x(12) | -0.7500 |
| x(2) | -0.1768 |
| x(10) | 0.1768 |
| x(6) | -0.1768 |
| x(14) | 0.1768 |
| x(1) | 0.5845 |
| x(9) | 0.1226 |
| x(5) | -0.4492 |
| x(13) | -0.2579 |
| x(3) | -0.4492 |
| x(11) | -0.2579 |
| x(7) | 0.5845 |
| x(15) | 0.1226 |
Now we perform a 2-point DFT on each of the sample pairs. This is very easy as we simply add the samples together for the first term then subtract the for the second so:
…and so on for each of the eight 2-point DFTs.
So the results for all the 2-point DFTs are as follows:
| Frequency | Magnitude |
|---|---|
| a(0) | 1.0000 |
| a(1) | 0.0000 |
| a(2) | -1.0000 |
| a(3) | 0.5000 |
| a(4) | 0.0000 |
| a(5) | -0.3536 |
| a(6) | 0.0000 |
| a(7) | -0.3536 |
| a(8) | 0.7071 |
| a(9) | 0.4619 |
| a(10) | -0.7071 |
| a(11) | -0.1913 |
| a(12) | -0.7071 |
| a(13) | -0.1913 |
| a(14) | 0.7071 |
| a(15) | 0.4619 |
The next stage is to start combining the results of the previous stage into larger and larger DFTs until we arrive back at a 16-point DFT. So the next stage is to combine the eight 2-point DFTs into four 4-point DFTs. We use the output of the previous stage to form the input of the next stage so we can treat it like a 2-point DFT. It is now the twiddle factors begin to come into play so let’s remind ourselves of their values for a 4-point DFT:
Notice that for the first time, in the 4-point DFT we have an imaginary term so there is going to be a Sine component to some of the results as well as a Cosine component. This makes the multiplication by the twiddle factor a little more “complex” as the twiddle factor is a complex number.
Before we begin with the numeric calculation, I want to take a quick look at multiplication with complex numbers. If you already know about multiplication with complex numbers, then click here to skip to the rest of the example.
Multiplication with Complex Numbers
A complex number can be one of three types of numbers:
- A completely real number (a number with the imaginary part equal to zero)
- A completely imaginary number (a number with the real part equal to zero)
- A number with both an real and imaginary component (a number with a non-zero real part and a non-zero imaginary part)
Therefore there can be four types of multiplication:
- A real number multiplied by another real number
- A real number multiplied by an imaginary number
- An imaginary number multiplied by another imaginary number
- A complex number multiplied by another complex number
A real number multiplied by another real number
When we multiply two real numbers together, we never even think complex numbers because any real number multiplied by another real number simply gives us a real number as the result.
To prove this, let’s write a real number in complex form. We do this by simply multiplying the imaginary part of the complex number by zero. So, for example, the number 2 could be written as:
Let’s multiply it by 3, which can be written as:
So if we want to multiply these 2 numbers together:
Because we are multiplying two numbers that are inside brackets, we have to multiply them in four stages using the FOIL method:
Stage 1 – First: We multiply the real number in each of the brackets (the first number in each of the brackets).
Stage 2 – Outside: We multiply the real number in the first bracket by the imaginary number in the second bracket (or the two numbers on the outer side of the 2 brackets).
Stage 3 – Inside: We multiply the imaginary number in the first bracket by the real number in the second bracket (or the two numbers on the inner side of the 2 brackets).
Stage 4 – Last: We multiply the imaginary numbers in each of the brackets (the last number in each of the brackets).
So our calculation is going to look like:
All but the first set of brackets in the above equation contain a multiplication by zero so only the first set of brackets will give a non-zero result. Therefore:
The result of the multiplication is a real number.
A real number multiplied by an imaginary number
What sort of number will we get if we multiply a real number by an imaginary number? Let’s try multiplying 5 (a real number) by i4 (an imaginary number). Firstly we write out our multiplication in complex form:
Using the same FOIL method again will give us:
You can see in the above equation that only the second set of brackets contain the multiplication of terms that are both non-zero, therefore, only the second set of brackets will give a non-zero result:
So the answer to our question is we will get a result that is imaginary if we multiply a real number by an imaginary number.
An imaginary number multiplied by another imaginary number
What sort of number will we get if we multiply an imaginary number by another imaginary number? Let’s try multiplying i2 (an imaginary number) by i4 (another imaginary number). Again, let’s write out our multiplication in complex form:
FOIL will give us:
This time the only set of brackets containing two non-zero terms is the last set. So:
HERE COMES THE COOL BIT: Remember the definition of the imaginary number i:
Which means that:
So:
The answer to our question this time is that an imaginary number multiplied by another imaginary number gives us a real number as the result.
A complex number multiplied by another complex number
What sort of number will we get if we multiply a complex number (that is a number with both a real and imaginary component) by another complex number? Let’s try multiplying 8+i5 by 3+i9 (an imaginary number).
Using FOIL, we’ll write it out in full:
This time there are no zero terms anywhere in the calculation so each of the 4 brackets in the equation above are going to give us a result:
The first set of brackets contain a real number (24). The second and third set of brackets contain an imaginary number so we can add these two brackets together. The final set of brackets contains our old friend i-squared which is equal to -1, so the final set of brackets contain a real number (-45) that can be combined with real number in the first set of brackets (24). So the answer to our problem is:
So a complex number multiplied by another complex number gives us a complex number as the result. However, this is not always true. Depending on the values of the real and complex part of the number the result could also be completely real or completely imaginary too. Just look at the next example.
Complex Conjugates
One way we can make the multiplication of two complex numbers can yield a real result is if the two complex numbers are complex conjugates. A complex conjugate is a pair of complex numbers that look identical, but for their sign. For example:
is the complex conjugate of:
If we were to multiply these two complex numbers together:
Using FOIL, this would expand to:
If we do the multiplications inside each of the 4 brackets we get:
Notice how the second and third brackets cancel each other out leaving a result that is completely real. So:
If two complex conjugates are multiplied together, they give a real result.
Summary of the rules of complex multiplication
Continuing with our numeric example
To help you with the next section, this website might be useful: Complex Number Calculator.
So now we’ve sorted out how to multiply real, imaginary and complex numbers, let’s remind ourselves of the twiddle factors for a 4-point DFT:
So the calculations for the 4-point DFTs will work as follows:
…and so on for each of the four 4-point DFTs.
So the results for all the 4-point DFTs are as follows:
| Frequency | Real (Cosine) | Imaginary (Sine) |
|---|---|---|
| b(0) | 0 | 0 |
| b(1) | 0 | -0.5 |
| b(2) | 2 | 0 |
| b(3) | 0 | 0.5 |
| b(4) | 0 | 0 |
| b(5) | -0.3536 | 0.3536 |
| b(6) | 0 | 0 |
| b(7) | -0.3536 | -0.3536 |
| b(8) | 0 | 0 |
| b(9) | 0.4619 | 0.1913 |
| b(10) | 1.4142 | 0 |
| b(11) | 0.4619 | -0.1913 |
| b(12) | 0 | 0 |
| b(13) | -0.1913 | -0.4619 |
| b(14) | -1.4142 | 0 |
| b(15) | -0.1913 | 0.4619 |
Next we combine the results from the four 4-point DFTs into two 8-point DFTs. We now have 4 twiddle factors to calculate:
Things are starting to get a little bit messy with lots of calculations with real and imaginary parts to them so I’ll walk through one in detail and leave you to apply it to all the others. You can check your answers in the table at the end of the 8-point DFT section.
Let’s take the calculation of the frequency c(5) as an example. From the butterfly diagram we see that c(5) is calculated using the following formula;
We saw above that:
and:
and:
So substituting these numbers into the equation:
Now this all looks very complicated, but all we need to do is break it down. Firstly we’ll multiply out the brackets using the FOIL method. So the multiplication of the brackets looks like:
Using FOIL gives us the result:
So:
So the results for all the 8-point DFTs are as follows:
| Frequency | Real (Cosine) | Imaginary (Sine) |
|---|---|---|
| c(0) | 0.0000 | 0.0000 |
| c(1) | 0.0000 | 0.0001 |
| c(2) | 2.0000 | 0.0000 |
| c(3) | 0.0000 | 1.0001 |
| c(4) | 0.0000 | 0.0000 |
| c(5) | 0.0000 | -1.0001 |
| c(6) | 2.0000 | 0.0000 |
| c(7) | 0.0000 | -0.0001 |
| c(8) | 0.0000 | 0.0000 |
| c(9) | 0.0000 | 0.0000 |
| c(10) | 1.4142 | 1.4142 |
| c(11) | 0.9238 | -0.3826 |
| c(12) | 0.0000 | 0.0000 |
| c(13) | 0.9238 | 0.3826 |
| c(14) | 1.4142 | -1.4142 |
| c(15) | 0.0000 | 0.0000 |
Finally we come to the 16-point DFT:
This time there are 8 twiddle factors to think about. As we saw in the previous post, these are:
Again the method we use to calculate each of the results is identical to the method we used in the 8-point example, so, at the risk of making this post any longer than it needs to be, I’ll skip the working and cut straight to the results which can be seen in the following table:
| Frequency | Real (Cosine) | Imaginary (Sine) |
|---|---|---|
| X(0) | 0.0000 | 0.0000 |
| X(1) | 0.0000 | 0.0000 |
| X(2) | 4.0000 | 0.0000 |
| X(3) | 0.0000 | 0.0002 |
| X(4) | 0.0000 | 0.0000 |
| X(5) | 0.0000 | -2.0000 |
| X(6) | 0.0000 | 0.0000 |
| X(7) | 0.0000 | -0.0001 |
| X(8) | 0.0000 | 0.0000 |
| X(9) | 0.0000 | 0.0001 |
| X(10) | 0.0000 | 0.0000 |
| X(11) | 0.0000 | 2.0000 |
| X(12) | 0.0000 | 0.0000 |
| X(13) | 0.0000 | -0.0002 |
| X(14) | 4.0000 | 0.0000 |
| X(15) | 0.0000 | 0.0000 |
Now you can see that there are lots of zeros going on in the various terms. However, it is a bit difficult to tell what is going on in our signal from these results. We need to use Pythagoras to get a magnitude value for each frequency to tell us what that frequency’s actual contribution is. We do this by combining the Real part for each frequency, ℜ, and the imaginary part, ℑ in the following manner:
This gives us the following results:
| Frequency Index | Magnitude |
|---|---|
| 0 | 0.0000 |
| 1 | 0.0000 |
| 2 | 4.0000 |
| 3 | 0.0002 |
| 4 | 0.0000 |
| 5 | 2.0000 |
| 6 | 0.0000 |
| 7 | 0.0001 |
| 8 | 0.0000 |
| 9 | 0.0001 |
| 10 | 0.0000 |
| 11 | 2.0000 |
| 12 | 0.0000 |
| 3 | 0.0002 |
| 14 | 4.0000 |
| 15 | 0.0000 |
But this would be much clearer in graphical form so let’s look at our answer properly and see which frequencies make up our signal:
So our signal is made up of 2 frequencies (remember all the frequencies above half the sampling rate, 8Hz in this case, are simply reflected frequencies). These frequencies are 2Hz and 5Hz.
So there we have it! That’s how the Fourier Transform works which brings us to the end of the blog.
As mentioned above, work is progressing on the video course based on this blog and I will be posting little video snippets from the course from time to time. You can receive an E-Mail notification when one of these snippets is available by subscribing to the E-Mail list for this blog. Not only will you receive the E-Mail notifications but also a free module from the course when the course goes live. All you need to do is:
As I was working through this numeric example, in order to help me to perform all the calculations necessary, I wrote my own FFT algorithm in Javascript which I’ll post with a full explanation in the next post.
