How the Cooley-Tukey FFT Algorithm Works | Part 4 - Twiddle Factors

• DFT_FFT
• Tutorials

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. Not all the samples in the signal were sampled at the same time. They occupy different positions on the x-axis in relation to the cosine and sine waves the Fourier Transform tests the signal with. How can the FFT algorithm work if its “one-size-fits-all” approach doesn’t correspond to the reality of the signal?

In Part 3 of this article, we learned how the inner butterfly of the FFT works by adding two input samples to produce the first frequency term and finding the difference between the two input samples to produce the second frequency term. This works very well for the group of samples we dealt with, but not for any of the others. Let's look at our signal again and what happens in the first stage of the FFT algorithm to try and understand the problem.

The Problem

Here is our signal containing of 8 samples, x₀ to x₇, being divided up into 4 groups, each containing a pair of samples.

At the end of the divide stage, the first group of samples contains x₀ and x₄. Let's isolate those samples and calculate a 2-point DFT for this group.

A 2-point DFT will produce 2 frequency outputs. Let's call them a₀ and a₁. Remember, a₀ and a₁ are complex numbers, meaning they will contain both a cosine component and a sine component. Therefore to calculate them, we need to multiply the signal by a cosine wave at Frequency Index 0 and Frequency Index 1, and then repeat the process with a sine wave.

So let's isolate the samples in the first group and superimpose a cosine wave on the graph with a frequency of 0 (shown in green).

Calculating the real part of a₀ gives us:

But both the samples on the cosine wave c₀ and c₄ are 1, so we can rewrite the real part of a₀ as:

Now let's do the same for the sine component.

Both the samples s₀ and s₄ on the sine graph (shown in green) are 0 at this frequency, so there is no sine component. Therefore:

Now let's calculate a₁ using these samples. Firstly the real part:

This time, although x₀ is still 1, x₄ is now -1. So:

What about the sine component?

Again, both samples on the sine wave, s₀ and s₄ are 0 so there is no sine component at this frequency. So:

So what about the next group of samples x₂ and x₆? They are multiplied by a cosine and sine wave with a frequency of 2 to produce the frequency component a₂ and by a cosine and sine wave with a frequency of 3 to produce a₃. But, on the face of it, we can't treat them like we did the previous group of samples because of their position in the signal. The only reason we could add x₀ and x₄ to produce a₀ was because both c₀ and c₄ were 1 when the frequency of the cosine wave was 0. However, look at the y-axis value of c₂ and c₆ when the frequency is 2.

To calculate a₂ using samples x₂ and x₆ in the same way as we did for a₀ when we used samples x₀ and x₄, the cosine wave would have to be shifted along the x-axis until it looked like this:

The same problem exists for a₃. Here is the unshifted cosine wave at frequency 3:

And here's the shifted cosine wave at frequency 3.

So when the FFT performs the first stage of the calculation on each group of samples, only the first group of samples is in the correct position for the FFT's “one-size-fits-all” approach to work. The samples in all the other groups are misaligned with the cosine and sine waves. This causes a phase distortion in the results of the first stage. If we don't perform a phase correction before proceeding, this distortion will propagate through the subsequent stages, leading to incorrect results.

The Solution

This is what twiddle factors are for. Twiddle factors (sometimes known as phase factors) are complex numbers that, when multiplied by the output from each stage of the algorithm, modify the balance between the cosine and sine components of the results. While we often think of sines and cosines as separate concepts, they are both sinusoids; waves that differ only in phase. A cosine wave has no phase shift, while a sine wave is shifted by 90° along the x-axis. If we add together a cosine wave and a sine wave with the same frequency, they produce a sinusoid with the same frequency but a different amplitude and phase. By adjusting the balance between the amplitude of the sine wave and the amplitude of the cosine wave, twiddle factors shift the phase of the resulting sinusoid without altering its amplitude.

The output from stage 1 of the algorithm provides preliminary estimates of all frequency components in the signal, but these estimates are based on only a subset of the input samples, with incorrect phases due to the FFT's "one-size-fits-all" approach. As it progresses through subsequent stages, the FFT refines these estimates by combining increasingly larger groups of samples, using twiddle factors to correct the phases of the results between stages.

We'll look at this in more detail in Part 5 of this article which will deal with combining butterflies, but for now, I want to look at how to calculate the Twiddle Factors.

Calculating Twiddle Factors

In the butterfly diagram, Twiddle Factors look like this:

The subscript number denotes the order of the Twiddle Factor. It indicates at which stage of the algorithm we're currently at. Twiddle factors in stage 1 of the algorithm will have an order of 2. Twiddle factors in stage 2 of the algorithm will have an order of 4; stage 3, an order of 8, and so on. The order is always 2 raised to the power of which stage we are at.

The superscript number indicates the index of the butterfly in the group. We'll look at this in more detail in Part 5.

So in the example above, the Twiddle Factor has an index, (let's call it I) of 1 and an order (let's call it O) of 4.

The value of the Twiddle Factor is calculated using the following equation:

So the Twiddle Factor: W₄¹ is calculated as follows:

Anything multiplied by Twiddle Factor W₄¹ will therefore be multiplied by -i. A multiplication by -i, is a rotation of -90° (-𝜋/2 radians) into the imaginary dimension. In our terms, that means a -90° phase shift along the x-axis.

For a deeper understanding of complex numbers, the imaginary number i, where it came from and what it has to do with the Fourier Transform, check out my video below.

Conclusion

So Twiddle Factors mitigates FFT's "one-size-fits-all" approach and corrects the phases of the previous stage's output. In the next part of this article, we'll see the Twiddle Factors in action as we combine the 4 groups of 2-point DFTs of stage 1 into the 2 groups of 4-point DFTs of stage 2, and discover how the work we already did in stage 1 is going to save us having to do that work again in stage 2.

I'll post Part 5, Combining Butterflies, next week,

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

Sign in