How the FFT algorithm works | Part 2 - Divide-and-Conquer
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'll be giving 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.
In part 1, we saw how the FFT takes advantage of multiplications which 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. If you missed part 1, there is a link at the end of this article.
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. Therefore it repeatedly divides an array of samples into smaller and smaller groups until it is left with only a pair of samples in each group. It then conquers the problem by performing a simple 2-point DFT (a DFT performed on 2 samples) on each pair of samples before combining the results recursively, repeatedly performing 2-point DFTs on each new group as it goes, until the DFT for the entire array of samples has been calculated. This method is known as divide-and-conquer.
What is divide-and-conquer?
Let's take a closer look at how the divide-and-conquer algorithm 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)
I want to demonstrate divide-and-conquer by tackling a simple problem. Then we'll take what we've learned and apply it to the FFT. 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:
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. In 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 to 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" which I'll post next week.