How the Cooley-Tukey FFT Algorithm Works | Part 1 - Repeating Calculations

• DFT_FFT
• Tutorials

The Fourier Transform is everywhere. Few are the days in your life when you don’t pick up a piece of technology that 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 that vastly reduced the number of calculations required. This algorithm became known as the Cooley-Tukey Fast Fourier Transform Algorithm. 

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, each number representing a different sinusoid. The real part of the number gives the amplitude 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."

Click here for Part 2

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

Sign in