This text, figures, and code snippet are also available in downloadable PDF format

Typical applications of an N-point radix-2 FFT accept N x(n) input time samples and compute N X(m) frequency-domain samples, where indices n and m both range from zero to N–1. However, there are non-standard FFT applications (for example, specialized harmonic analysis, or perhaps using an FFT to implement a bank of filters) where only a subset of the full X(m) results are required.

Consider Figure 1(a) that shows the butterfly operations for an 8-point radix-2 decimation-in-time FFT. Assuming we are only interested in the X(3) and X(7) output samples, rather than compute the entire FFT we perform only the computations indicated by the bold lines in Figure 1(a). In order to compute only X(3) and X(7) we need to know the butterfly twiddle phase angle factors associated with the bold-line computations. Here we show how, and provide a Matlab routine, to compute the twiddle factors of N-point radix-2 FFTs.

Notice that the FFT butterflies in Figure 1(a) are single-complex-multiply butterflies. The numbers associated with the butterflies are phase angle factors, 'A', as shown in Figure 1(b). A butterfly's full twiddle factor is shown in Figure 1(c).

Decimation-in-time FFT Twiddle Factors
For the decimation-in-time (DIT) FFT using the single-complex multiply butterflies,

• The N-point DIT FFT has log₂(N) stages, numbered P = 1, 2, ..., log₂(N).
• Each stage contains N/2 butterflies.
• Not counting the –1 multiply operations, the Pth stage has N/2 twiddle factors, numbered k = 0, 1, 2, ..., N/2–1 as indicated by the upward arrows at the bottom of Figure 1(a).

Given those characteristics, the kth twiddle factor phase angle for the Pth stage is computed using:

      kth DIT twiddle factor angle = [⌊k2^P/N⌋]_bit-rev (1)

where 0 ≤ k ≤ N/2–1. The ⌊q⌋ operation means the integer part of q. The [z]_bit-rev function represents the three-step operation of: convert decimal integer z to a binary number represented by log₂(N)–1 binary bits, perform bit reversal on the binary number as discussed in Section 4.5, and convert the bit reversed number back to a decimal integer.

As an example of using Eq.(1), for the second stage (P = 2) of an N = 8-point DIT FFT, the k = 3 twiddle factor angle is:

The above [1]_bit-rev operation is: take the decimal number 1 and represent it with log₂(N)–1 = 2 bits, i.e., as 01₂. Next, reverse those bits to a binary 10₂ and convert that binary number to our desired decimal result of 2.

Decimation-in-frequency FFT Twiddle Factors
Figure 2(a) shows the butterfly operations for an 16-point radix-2 decimation-in-frequency FFT. As before, notice that the FFT butterflies in Figure 2(a) are single-complex-multiply butterflies. The numbers associated with the butterflies are phase angle factors, 'A', as shown in Figure 2(b). A butterfly's full twiddle factor is shown in Figure 2(c).

For the decimation-in-frequency (DIF) radix-2 FFT using the optimized butterflies,

• The N-point DIF FFT has log₂(N) stages, numbered P = 1, 2, ..., log₂(N).
• Each stage comprises N/2 butterflies.
• Not counting the –1 twiddle factors, the Pth stage has N/2^P unique twiddle factors, numbered k = 0, 1, 2, ..., N/2^P–1 as indicated by the upward arrows at the bottom of Figure 2.

Given those characteristics, the kth unique twiddle factor phase angle for the Pth stage is computed using:

      kth DIF twiddle factor angle = k•2^P/2 (2)

where 0 ≤ k ≤ N/2^P–1. For example, for the second stage (P = 2) of an N = 8-point DIF FFT, the unique twiddle factor angles are:

      k = 0,      angle = 0•2^P/2 = 0•4/2 = 0
      k = 1,      angle = 1•2^P/2 = 1•4/2 = 2.

In Figure 2(a) the final stages's single twiddle factor of zero means multiply by unity, i.e., no operation.

Closing Remarks:
Once you have the following Matlab code running on your computer, at tonight's dinner table you can proudly announce, "Family, ... may I have your attention?" [Wait for your family to stop making noise.] "You will be happy to know that I now have the ability to compute the twiddle factors of decimation-in-frequency fast Fourier transforms." Next, enjoy the loving smiles on the faces of your proud family.

Matlab Code:
Below is the Matlab code to find radix-2 FFT butterfly twiddle factors. The code computes the 'A' phase angle factors that are used in the twiddle factors as shown in Figure 1(c) and Figure 2(c). I suggest you start by running the code for the 8-point DIT FFT in Figure 1(a) and then run the code for the 16-point DIF FFT in Figure 2(a).