How the FFT algorithm works | Part 4 - Combining Butterflies
The beauty of the FFT algorithm is that it does the same thing over and over again. It treats every stage of the calculation in exactly the same way. However, this causes a problem. Not all the samples in the signal were sampled at the same time. They occupy different positions on the x-axis in relation to the cosine and sine waves the Fourier Transform tests the signal with. How can the FFT algorithm work if its “one-size-fits-all” approach doesn’t correspond to the reality of the signal?
In last week's article, I said that the FFT solves this problem using Twiddle Factors and promised that this week's article would be all about them. However, as I was writing this article, I realized that before we can understand what twiddle factors are and how they solve the problem, we first need to properly understand what the problem is. To do this we need to look at how the FFT combines butterflies at each stage of the calculation to form larger and larger butterflies until the DFT for the entire signal has been calculated.
Having covered the basics of the Fourier Series in my book: "How the Fourier Series Works" (see link below), I'm now busy writing its sequel: "How the Fourier Transform Works".
In this series of articles on the FFT, I give you a sneak preview of one of the sections in my new book, taking you on a visual journey to discover just how the Cooley-Tukey FFT algorithm works.
Review
In part 1 of this series, I introduced the signal (see graph below) on which we are going to perform our FFT. Throughout this series of articles, we've been using this signal to demonstrate how the FFT works.
In part 2, we saw how the signal is split into sample pairs as follows:
In part 3, we constructed a set of four 2-point butterflies. These butterflies calculate two frequency components for each of the above pairs of samples by adding the samples together for the first frequency component and subtracting them for the second as shown in the diagram below.
Links to parts 1-3 can be found at the end of this article.
Now we're going to combine these four groups of 2-point butterflies into two groups of 4-point butterflies (shown below) to calculate two 4-point DFTs for this signal.
How to calculate a 4-point DFT
Method 1: The long way round
A 4-point DFT splits the signal into 4 cosine components and 4 sine components at 4 different frequencies. The signal, cosine, and sine waves for the first group of 4-point DFTs involving samples x?, x?, x?, and x?, are shown in the graphs below.
There are 4 rows of graphs. Each row contains a cosine wave (left-hand graph) and an inverted sine wave (right-hand graph) at one of the frequencies to be tested. Let's demonstrate how to calculate the DFT for one of these frequencies.
The graph above shows the signal, cosine, and sine waves for the frequency k=2. At this frequency, the cosine and sine waves will oscillate twice over the period of the signal. Let's substitute that into the DFT formula below, together with all the other information we have about the signal.
There are 8 samples in the signal. However, we have split the signal into 2 halves, each containing 4 samples, so N=4. Therefore, the sample index, n, ranges from 0 to 4. The first group contains 4 samples x?, x?, x?, and x?, so the index, n, will range from 0 to 4. The "i" between the cosine and sine terms tells us that this is a complex calculation. The sine part is imaginary, so we have to keep the cosine and sine calculations separate. Therefore, let's split the calculation into 2 parts, one for the cosine component (the real part) and one for the sine component (the imaginary part).
Calculating the Cosine (Real) Part
Note: I'm using the curly "R" symbol in the equation below to denote that this is the real (cosine) part of the calculation. X denotes the result of the DFT, and k=2 tells us that the frequency we are testing is 2.
If we calculate the brackets for the above equation we get:
As we see from the cosine graph below, at the 4 sample points:
So the cosine component of the DFT for this frequency simplifies to:
Sine (Imaginary) Component
Note: I'm using the curly "I" symbol in the equation below to denote that this is the imaginary part of the calculation. Again, X denotes the result of the DFT, and k=2 tells us that the frequency we are testing is 2.
If we calculate the brackets for the above equation we get:
As we see from the sine graph below, at the 4 sample points:
So the sine component of the DFT at this frequency simplifies to:
All the samples above are multiplied by zero. Therefore, there is no sine component at this frequency.
领英推荐
Method 2: The Shortcut - Building a 4-Point DFT out of two 2-Point DFTs
Given that the cosine (real) part of the DFT for this frequency is given by:
...and the sine (imaginary) part of the DFT for this frequency is zero, we can say that the DFT for this frequency is entirely made up of the cosine component. So multiplying out the brackets for the cosine (real) part of the DFT for this frequency gives us:
However, if I slightly rearrange the above formula, we get:
If we remember the 2-point DFTs we calculated in part 3 of this series of articles:
We discover that we already did some of the work when we calculated the 2-point DFTs. So we can calculate a 4-point DFT by combining two of the 2-point DFTs we calculated before.
This is what makes the FFT so efficient, as we learned in part 1 of this article. By remembering the result it calculated at one frequency, the FFT can use that result when it occurs again at another frequency, without having to recalculate it.
Representing the combination of 2-point DFTs using a butterfly diagram
This process can be represented graphically by interleaving 2 butterflies:
See how the results a? (1st input to the interleaved butterflies) and a? (3rd input to the interleaved butterflies) from the 2-point DFTs are combined to give the DFT, X, for the frequency k=2 (3rd output from the interleaved butterflies).
So what's the problem? This all seems to be working very well. What are these twiddle factors I promised and why do we need them?
The need for twiddle factors
I purposely chose to calculate one of the even frequencies (k=2) to demonstrate how combining two 2-point DFTs helps us to calculate a 4-point DFT. However, if we try to do the same for one of the odd frequencies, k=1, for example, we hit a problem.
Calculating a 4-Point DFT at frequency k=1
Using the long way round in the same manner as before, we can see that the cosine component doesn't present us with a problem. If we calculate the cosine components of the DFT from the left-hand graph, we end up with:
However, we run into trouble when calculating the sine component as unlike all the 2-point DFTs from before, it is not zero.
But why is this not equal to a?? Because:
We are working out the imaginary or the sine part of the calculation. If we were to write out the whole expression for the k=1 frequency according to the DFT equation we would have to write:
It can be made up from the results from the 2-point DFTs a? and a? as shown below...
...but the multiplication by i does something to a?. It makes it imaginary, in other words, the samples that make up a? have been shifted by 90°. The imaginary number i has twiddled a? into the correct position for the calculation.
Imaginary numbers, phase shifts and twiddle factors
What's going on here? What are imaginary numbers and what are they doing in the Fourier Transform? How has this weird number i become a twiddle factor and shifted the signal by 90°?
WHAT ARE TWIDDLE FACTORS?
We'll find out more about twiddle factors and how they work in part 5 of this article which I'll post next week.
In the meantime, if you need a refresher on imaginary numbers and what they are doing in the Fourier Transform, then take a look at one of my videos on the subject.