How the Cooley-Tukey FFT Algorithm Works | Part 2 - Divide & Conquer

• DFT_FFT
• Tutorials

In Part 1, we saw how the Fast Fourier Transform takes advantage of calculations that repeat themselves at different frequencies in the Discrete Fourier Transform. This will happen so long as we ensure that the number of samples we are analyzing is equal to a power of 2. By remembering the result from one multiplication, it saves having to do the same calculation when it comes up again at a different frequency. 

For the FFT to take advantage of repeating calculations, the input samples are first divided into groups based on their positions, specifically separating even-indexed and odd-indexed samples. The algorithm repeatedly divides the array into smaller subarrays, eventually isolating pairs of samples. At this smallest level, a simple 2-point DFT is performed on each pair of samples. These results are then combined recursively, using the results of the smaller DFTs, to help calculate the DFT for progressively larger groups. This process continues until the DFT for the entire array is computed. This method is known as divide-and-conquer, originally developed by Carl Friedrich Gauss in 1805.

How divide-and-conquer works

A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem. (Wikipedia)

To demonstrate how "Divide & Conquer" works, I would like to try and solve a much simpler problem than computing a DFT. Then we'll take what we've learned and see how to apply it to the DFT. The task is to sort an array of 8 random numbers like the ones below, in ascending order.

Many algorithms have been proposed over the years, but those that are the most efficient tend to employ the divide-and-conquer method. The sorting algorithm we'll be considering here is called Merge Sort.

The Merge Sort Algorithm

The following video describes how the merge sort algorithm sorts the above array of numbers in ascending order. There are 2 main stages to the algorithm:

1. The divide stage, where the problem is broken down again and again into smaller and smaller sub-problems.
2. The conquer stage, where the sorting actually happens. As each sub-problem is sorted, the results are merged back into bigger and bigger groups until the whole problem has been solved and the array is sorted.

The advantage of the divide-and-conquer method is that by the end of the divide stage, once the problem has been broken down into its smallest possible set of sub-problems, conquering it becomes trivial and each new stage builds on the work done in the previous stage without having to do the same work again.

Divide-and-conquer applied to the FFT

In part 1 of this article, we saw how the results from the calculation of certain groups of samples in the DFT repeat themselves if we ensure that the number of samples is a power of 2. We’re now going to go back to the sampled signal and see how we can group those samples together to take advantage of the repeating nature of the calculations.

Divide Stage

The FFT algorithm repeatedly divides the elements of the input array into smaller and smaller arrays like the Merge sort algorithm. However, unlike Merge sort, it orders them in a slightly different way. Instead of grouping consecutive elements like Merge sort, the FFT groups the even and odd elements together in each stage. The graph above shows the signal on which we’re going to perform the FFT algorithm. It contains 8 samples labelled x₀ to x₇. The amplitudes of these samples are shown in the following array

Notice how all the even-numbered samples, x₀, x₂, x₄, and x₆ are colored in red and all the odd-numbered samples, x₁, x₃, x₅, and x₇ are colored in blue. The following video shows how the samples are divided.

Conquer Stage

Let’s go back to the DFT equation and see how dividing the array of samples up into groups containing only 2 samples per group makes calculating the DFT for each group very easy.

The signal is represented by xₙ in the equation where n is the sample index. Each sample must be multiplied by its corresponding sample on a cosine wave and on an inverted sine wave. The sine wave is inverted on account of the minus sign between the cosine term and the sine term in the equation.

In the following collection of graphs, I’ve drawn the signal in green, the cosine wave in blue and the sine wave in red.

There are only 2 samples in each group, so N=2. At the end of the divide stage, the first group contains the samples x₀, and x₄. These are the green dots which I’ve labelled on each of the graphs above.

In the DFT, the number of frequencies it will test is equal to the number of samples. Therefore, the 2 samples in each group will be tested at 2 frequencies, k = 0 (the graphs on the top row) and k = 1 (the graphs on the bottom row).

At each frequency, the DFT multiplies the signal by a cosine wave (the graphs on the left) and an inverted sine wave (the graphs on the right). It then sums the results of all the multiplications to give the DFT of the signal for each of the frequencies. So the DFT of the signal at frequency k=0 will give X₀ and the DFT of the signal at frequency k=1 will give X₁.

Calculating the DFT for k=0

The DFT, X₀ for the first frequency, k=0, can be calculated as follows:

The first frequency is k=0. This is the red number in the equation above. The index, n, ranges from 0 to 1 and is shown in blue. This equation can be simplified to give:

We can see from the graph above, that it doesn’t matter what the sample index n is, at k=0 the amplitude of the cosine wave, shown by the blue dots, is always 1 and the amplitude of the sine wave, shown by the red dots, is always 0. This can be understood mathematically from the equation for X₀ as cos(0)=1 and -sin(0)=0. So the equation can be further simplified giving us:

Reading off the amplitudes of samples x₀ and x₄, we can use this equation to calculate X₀ for our signal.

Calculating the DFT for k=1

The DFT, X₁ for the second frequency, k=1, can be expressed mathematically as follows:

For this second frequency, k is 1. This is the red number in the equation above. The index, n, ranges from 0 to 1 and is shown in blue. This equation can be simplified to give:

From the left hand graph, we can see that, for x₀, the amplitude of the corresponding sample on the cosine wave is 1. From the right hand graph we can see that the amplitude of the corresponding sample on the sine wave is 0. For x₁, the amplitude of the corresponding sample on the cosine wave is -1 and the amplitude of the corresponding sample on the sine wave is 0. This can be understood mathematically from the equation for X₁ due to the fact that cos(0)=1, -sin(0)=0, cos(𝜋)=-1 and -sin(𝜋)=0. So the equation can be further simplified giving us:

Reading off the amplitudes of samples x₀ and x₄, we can use this equation to calculate X₁ for our signal.

Repeating the process for the other sample groups

Therefore, conquering a 2-point DFT (a DFT with only 2 samples in it) is very easy. All we need to do is add the samples for the first frequency term and subtract them for the second. We can now apply this method to each group of samples from the end of the divide stage.

This process can be represented graphically using a Butterfly Diagram. We'll be looking at what a Butterfly Diagram is and how it works in Part 3 of this article called: The Inner Butterfly.

Click here for Part 3

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

Sign in