How the Cooley-Tukey FFT Algorithm Works | Part 3 - The Inner Butterfly

• DFT_FFT
• Tutorials

At the heart of the Cooley-Tukey FFT algorithm sits a butterfly. We're not talking about a real butterfly of course, but a mathematical one. The shape of the data-flow diagram for a 2-Point Discrete Fourier Transform is strangely reminiscent of a butterfly's wings.

In Part 1 of this article, we saw how the FFT takes advantage of multiplications that repeat themselves at different frequencies in the Discrete Fourier Transform. By remembering the result from one multiplication, it saves having to do the same calculation when it comes up again at a different frequency.

In order for the FFT to take advantage of these repeating calculations, the samples first need to be divided into groups according to how often the multiplications they are involved in repeat themselves. The FFT uses the divide-and-conquer approach to recursively break down the signal into pairs of samples, then conquers the problem by calculating a 2-Point DFT (a DFT made up of only 2 samples) on each sample pair. This is very easy to do.

In Part 2 of this article, we saw how a 2-point DFT tests a signal with a cosine and sine wave at 2 different frequencies to find out how much each frequency contributes to the overall signal. A 2-point DFT is so simple that it can calculate the contribution of the first frequency by adding the amplitudes of the two samples together. The contribution of the second frequency can be calculated by subtracting the amplitude of the second sample from the amplitude of the first. 

The Butterfly Diagram

The FFT is a recursive algorithm. This means that the core process of conquering groups of samples that we saw in Part 2 will be repeated many times on larger and larger sample groups. A Butterfly Diagram sometimes referred to as the inner butterfly, provides a simple way of visualizing this core process. As the algorithm advances, a single butterfly (like the one below) will be repeated many times, interleaving with other butterflies as we combine more and more samples in each group.

The diagram is made up of the following symbols:

Using these symbols, we can build butterfly diagrams to conquer each of the four groups of samples we were left with at the end of the "divide stage" in part 2 of this article.

Here is the signal we were analyzing.

Here are the samples as they were grouped at the end of the divide stage.

The butterfly diagram below conquers the first group of samples, x₀, and x₄, from the sample array above.

The sample x₀ enters the butterfly at the top left of the diagram.

The sample x₄ enters the butterfly at the bottom left where it is immediately multiplied by the twiddle factor, W₂⁰. We can disregard the twiddle factor at this stage as it is equal to 1. We’ll find out what a twiddle factor is in Part 4 of this article.

x₀ is added to x₄ at the top right of the butterfly to produce a₀ (the contribution of the first frequency to the signal) as shown in the following equation.

x₄ is multiplied by the twiddle factor, W₂⁰, which is equal to 1, then by -1 and added to x₀ at the bottom right of the butterfly to produce a₄, (the contribution of the second frequency to the signal) as shown below.

The same idea is repeated for all the remaining groups using the butterflies shown below.

Simplicity is all very well, but there is a problem

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.

If we go back to the graphs of the signal and the cosine and sine waves we saw in part 2, it is easy to see why the first butterfly works when calculating frequency components a₀ and a₄ from samples x₀ and x₄. I've reproduced these graphs below.

We are only calculating a 2-point DFT. Therefore, there are only 2 samples at a time that take part in the calculation. The first of these sample pairs was x₀ and x₄. These samples are multiplied by their corresponding points on a cosine wave (the points marked in blue on the graphs above) and a sine wave (the points marked in red) at 2 different frequencies, k=0 and k=1. The results of these multiplications are then added together to produce 2 results, a₀ and a₄, one result for each frequency.

However, not all the samples in the signal above were sampled at the same time. They occupy different positions on the x-axis. x₀ and x₄ may line up with the marked points on the cosine and sine waves, but none of the other samples do. How can the FFT algorithm work if its “one-size-fits-all” approach multiplies each of the sample pairs by the same marked points on the cosine and sine waves? This approach doesn’t correspond to the reality of the signal.

The solution is to apply a twiddle factor to each stage of the calculation. We'll be looking at how twiddle factors fix the problem described above in Part 4 of this article called: "Twiddle Factors".

To find out more about how the Fourier Transform works, please visit my YouTube channel:
https://www.youtube.com/c/MarkNewmanEducation

Sign in