How the FFT algorithm works | Part 1 - Repeating Calculations

The Fourier Transform is everywhere. Few are the days in your life when you don’t pick up a piece of technology which implements it. However, this wouldn’t be the case if a way hadn’t been found to make it easier to calculate.

Enter James Cooley and John Tukey, two American mathematicians who published a paper in 1965 in which they proposed a recursive algorithm which vastly reduced the number of calculations required. This algorithm became known as the Cooley-Tukey Fast Fourier Transform.?

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.

The Fast Fourier Transform is a more efficient version of the Discrete Fourier Transform. The DFT is a Fourier Transform for sampled signals.

Interestingly, Cooley and Tukey weren’t the first to come up with a more efficient way of calculating the Discrete Fourier Transform. A recursive algorithm was invented 160 years earlier by Carl Friedrich Gauss, the German mathematician and physicist famous for his work in statistics. However, Gauss was a little ahead of his time. In the 1960s, the invention of the silicon transistor was about to revolutionize the world of computing. Cooley and Tukey’s rediscovery of Gauss’ work came at just the right time, the world was ready to listen, and their names became forever associated with the FFT.

Repeating Calculations

The key to the FFT's efficiency lies in the fact that if you sample your signal a number of times that is a power of 2, then certain calculations repeat themselves. Remembering the results of these calculations saves having to repeat the same calculation again. What is more, if the samples are ordered in a certain way, the result from one set of calculations can form the starting point of the next.

To understand exactly how the FFT works, we first need to understand the DFT which is defined by the following equation.

We can understand this equation as a list of mathematical operations as follows:

1. Multiply each sample, x?, of a signal by the corresponding sample on a cosine wave with a frequency k where k=0.
2. Add all the results of stage 1 together.
3. The result of stage 2 gives the amplitude of the cosine component at the frequency k=0.
4. Multiply each sample, x?, of a signal by the corresponding sample on an inverted sine wave with a frequency k where k=0.
5. Add all the results of stage 4 together.
6. The result of stage 5 gives the amplitude of the sine component at the frequency k=0.
7. Repeat all the above stages for frequencies k=1, k=2, k=3, up to k=(N-1), where N is the number of samples in your signal.

You end up with a list of complex numbers. The real part of the number gives the amplitudes of the cosine component at each frequency, and the imaginary part gives the amplitudes of the sine component at each frequency.

For example, the signal shown below has been sampled 8 times. The individual samples are marked with blue dots and labeled x? to x?. The DFT multiplies the signal by 8 cosine waves and 8 sine waves at 8 different frequencies, adding together the results of the multiplications for each frequency as it goes.

If we sample a cosine or sine wave a number of times that is a power of 2, then as the frequency of the wave increases, the amplitudes of certain sample combinations remain constant for different frequencies. This means that the multiplication of the signal by the cosine or sine wave at these points will yield the same result, even though the frequency has changed.

Repeating amplitudes on a Cosine Wave

In the series of graphs below, I have marked samples 0 and 4 on the cosine wave, which correspond to samples x? and x? on the signal. Notice how, even though the frequency of the cosine wave in each successive figure increases by 2 Hz each time, the amplitudes of the marked samples do not change.

If this is true, then when we multiply x? or x? by their corresponding points on the cosine wave, it doesn't matter which of the 4 frequencies we test, the answer will always be the same.

Repeating amplitudes on a Sine Wave

The same is true when we multiply these points on the signal by a sine wave as shown below.

Different combinations of samples also repeat

This phenomenon of repeating amplitudes is true for other sample combinations too, the only difference being the number of frequencies for which the same amplitudes repeat. For example, samples 2 and 6 repeat only twice out of the 8 test frequencies as shown below.

The same is true for a sine wave at these frequencies too.

Sorting the samples

So if the algorithm can find some way of remembering the result of the multiplication of these samples at one frequency, it won't have to repeat the same calculation again when it reoccurs at another. In order for it to do this, the samples need to be sorted by how often the multiplications they are involved in repeat themselves. We'll be looking at how this is done in Part 2 of this article called: "Divide and Conquer."

Next part of this article