DSP Tricks: Computing Fast Fourier Transform Twiddle Factors - Embedded.com

DSP Tricks: Computing Fast Fourier Transform Twiddle Factors

Typical applications using an N-point radix-2 FFT accept N input timesamples, x(n), and compute N frequency-domain samples X(m).

However, there are non-standard FFT applications (for example, specialized harmonicanalysis, or perhaps using an FFT to implement a bank of filters )where only a subset of the X(m) results are required.

Consider Figure 13″39 below showing a 16-point radix-2 decimation in time FFT, and assume we onlyneed to compute the X(1), X(5), X(9) and X(13) output samples. In thiscase, rather than compute the entire FFT we only need perform thecomputations indicated by the heavy lines.

Figure13″39 16-point radix-2 FFT signal flow diagram.

Reduced-computation FFTs are often called pruned FFTs. (for simplicity the butterflies in Figure 13″39 above only show thetwiddle phase angle factors and not the entire twiddle phase angles. )

To implement pruned FFTs, we need to know the twiddle phase anglesassociated with each necessary butterfly computation as shown in Figure 13″40(a) below.

Here we give an interesting algorithm for computing the (2 pi x A1 )/Nand (2 pi x A2 )/N twiddle phase angles for an arbitrary-sizeFFT. The algorithm draws upon the following characteristics of aradix-2 decimation-in-time FFT:

A general FFT butterfly is that shown in Figure 13-40(a) .
The A1 and A2 angle factors are the integervalues shown in Figure 13-39.
An N-point radix-2 FFT has M stages (shownat the top of Figure 13″39) where M = log2 (N ).
Each stage comprises N/2 butterflies.

The A1 phase angle factor of an arbitrary butterfly is

where S is the index ofthe M stages over the range 1 S M. Similarly, B serves as the index for the N/2butterflies in each stage, where 1 B N/2.

Figure13″40 Two forms of a radix-2 butterfly.

B = 1 means the topbutterfly within a stage. The [q] operation is a function that returnsthe smallest integer q.

Brev [z] represents the three-step operation of: convertdecimal integer z to a binary number represented by M”1 binary bits,perform bit reversal on the binary number, and convert the bit reversednumber back to a decimal integer yielding angle factor A1 .Angle factor A2 , in Figure13″40(a) above , is then computed using

The algorithm can also be used to compute the single twiddle anglefactor of the optimized butterfly shown in Figure 13″40(b) . Below is a codelisting, in MATLAB, implementing our twiddle angle factor computationalalgorithm.

The variables in the code with start and stop in their names allowcomputation of a subset of the of all the twiddle angle factors in anN-point FFT.

For example, to compute the twiddle angle factors for the fifth andsixth butterflies in the third stage of a 32-point FFT, we can assign N= 32, Sstart = 3, Sstop = 3, Bstart = 5, and Bstop = 6, and run the code.

Usedwith the permission of the publisher, Prentice Hall, this on-goingseries of articles on Embedded.com is based on copyrighted materialfrom “UnderstandingDigital Signal Processing, Second Edition” by Richard G. Lyons. Thebook can be purchased on line.

Richard Lyons is a consultingsystems engineer and lecturer with Besser Associates. As alecturer with Besser and an instructor for the University of CaliforniaSanta Cruz Extension, Lyons has delivered digitasl signal processingseminars and training course at technical conferences as well atcompanies such as Motorola, Freescale, Lockheed Martin, TexasInstruments, Conexant, Northrop Grumman, Lucent, Nokia, Qualcomm,Honeywell, National Semiconductor, General Dynamics and Infinion.

1 thought on “DSP Tricks: Computing Fast Fourier Transform Twiddle Factors

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.