Processor: Not Relevant
Submitted by Rick Lyons on Nov 28 2011
Licensed under a Creative Commons Attribution 3.0 Unported License
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,
Given those characteristics, the kth twiddle factor phase angle for the Pth stage is computed using:
kth DIT twiddle factor angle = [⌊k2P/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 log2(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:
|3rd twiddle factor angle||= [⌊3•22/8⌋]bit-rev|
|= [⌊1.5⌋]bit-rev = bit-rev = 2.|
The above bit-rev operation is: take the decimal number 1 and represent it with log2(N)–1 = 2 bits, i.e., as 012. Next, reverse those bits to a binary 102 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,
Given those characteristics, the kth unique twiddle factor phase angle for the Pth stage is computed using:
kth DIF twiddle factor angle = k•2P/2 (2)
where 0 ≤ k ≤ N/2P–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•2P/2 = 0•4/2 = 0
k = 1, angle = 1•2P/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.
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.
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).