Sign in

Not a member? | Forgot your Password?

Search code

Search tips

Find us on Facebook!





Free PDF Downloads

A Quadrature Signals Tutorial: Complex, But Not Complicated

Understanding the 'Phasing Method' of Single Sideband Demodulation

Complex Digital Signal Processing in Telecommunications

Introduction to Sound Processing

C++ Tutorial

Introduction of C Programming for DSP Applications

Fixed-Point Arithmetic: An Introduction

Cascaded Integrator-Comb (CIC) Filter Introduction

FIR Filter Design Software

See Also

Embedded SystemsFPGA

DSP Code Sharing > Computing FFT Twiddle Factors


Computing FFT Twiddle Factors

Language: Matlab

Processor: Not Relevant

Submitted by Rick Lyons on Nov 28 2011

Licensed under a Creative Commons Attribution 3.0 Unported License

Computing FFT Twiddle Factors


 

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).

Figure 1: (a) 8-point decimation-in-time (DIT) FFT signal flow diagram; (b) single-complex multiply DIT butterfly with angle factor A; (c) DIT butterfly details.

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 log2(N) stages, numbered P = 1, 2, ..., log2(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 = [⌊k2P/N⌋]bit-rev (1)

where 0 ≤ kN/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 = [1]bit-rev = 2.

The above [1]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,

  • The N-point DIF FFT has log2(N) stages, numbered P = 1, 2, ..., log2(N).
  • Each stage comprises N/2 butterflies.
  • Not counting the –1 twiddle factors, the Pth stage has N/2P unique twiddle factors, numbered k = 0, 1, 2, ..., N/2P–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•2P/2 (2)

where 0 ≤ kN/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.





Figure 2: (a) 16-point decimation-in-frequency (DIF) FFT signal flow diagram; (b) single-multiply DIF butterfly with angle factor A; (c) DIF butterfly details.

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).

 
% Filename:  FFT_Twiddles_Find_DSPrelated.m

%  Computes 'Decimation in Frequency' or 'Decimation
%  in Time' Butterfly twiddle factors, for radix-2 FFTs
%  with in-order input indices and scrambled output indices.
%  
%  To use, do two things: (1) define FFT size 'N'; and
%  (2) define the desired 'Structure', near line 17-18,
%  as 'Dec_in_Time' or 'Dec_in_Freq'.
%
%  Author: Richard Lyons, November, 2011
%******************************************

clear, clc

% Define input parameters
N = 8; % FFT size (Must be an integer power of 2)
Structure = 'Dec_in_Time';  % Choose Dec-in-time butterflies
%Structure = 'Dec_in_Freq';  % Choose Dec-in-frequency butterflies

% Start of processing
Num_Stages = log2(N); % Number of stages
StageStart = 1; % First stage to compute
StageStop = Num_Stages; % Last stage to compute
ButterStart = 1; %First butterfly to compute
ButterStop = N/2; %Last butterfly to compute
Pointer = 0; %Init 'results' row pointer
for Stage_Num = StageStart:StageStop
if Structure == 'Dec_in_Time'
          for Butter_Num = ButterStart:ButterStop
            Twid = floor((2^Stage_Num*(Butter_Num-1))/N);
            % Compute bit reversal of Twid
            Twid_Bit_Rev = 0;
            for I = Num_Stages-2:-1:0
                if Twid>=2^I
                  Twid_Bit_Rev = Twid_Bit_Rev + 2^(Num_Stages-I-2);
                  Twid = Twid -2^I;
                else, end
            end %End bit reversal 'I' loop
            A1 = Twid_Bit_Rev; %Angle A1
            A2 = Twid_Bit_Rev + N/2; %Angle A2
            Pointer = Pointer +1;
            Results(Pointer,:) = [Stage_Num,Butter_Num,A1,A2];
          end
     else
          for Twiddle_Num = 1:N/2^Stage_Num
            Twid = (2^Stage_Num*(Twiddle_Num-1))/2; %Compute integer
            Pointer = Pointer +1;
            Results(Pointer,:) = [Stage_Num,Twiddle_Num,Twid];
          end
    end % End 'if'
end % End Stage_Num loop

Results(:,1:3), disp(' Stage#  Twid#   A'), disp(' ')
 
 
Rate this code snippet:
4.65
Rating: 4.65 | Votes: 3
 
   
 
posted by Rick Lyons
Richard (Rick) Lyons is a consulting Systems Engineer and lecturer with Besser Associates in Mountain View, California. He is the author of "Understanding Digital Signal Processing 3/E" (Prentice-Hall, 2011), and Editor of, and contributor to, "Streamlining Digital Signal Processing, A Tricks of the Trade Guidebook" (IEEE Press/Wiley, 2012). He is a past Associate Editor for the IEEE Signal Processing Magazine.


Comments


 

dsss27 wrote:

1/23/2013
 
re:  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.

Yeah, my son will say: "So you figured out how to use your smartphone yet?"
 

hariharnath wrote:

10/10/2013
 
can u provide the code for decimation in frequency also??
 

Rick Lyons wrote:

10/10/2013
 
Hello hariharnath,
  I do not understand the meaning of your question.  What kind of code are you referring to?  The above Matlab code allows you to compute the twiddle factors of a 'decimation in frquency' radix-2 FFT.
[-Rick-]
 

him wrote:

1/21/2014
 
can u plz provide coding for Radix-5 ???
plz sir reply ASAP
 

pramodkachare wrote:

7/22/2014
 
if you just want to find twiddle factor why not use inbuilt command fft
e.g. fft(eye(n))
this gives twiddle factor matrix of  n * n
for other you have to just change input
 

pramodkachare wrote:

7/22/2014
 
One can also go for dftmtx(n) command to get dft matrix
 

Rick Lyons wrote:

7/23/2014
 
Hello pramodkachare,
  I wasn't familiar with the 'dftmtx(n)' command.  Thanks for pointing it out to me.  However, can you tell us how that command helps us find radix-2 FFT twiddle factors?
[-Rick-]

Add a Comment
You need to login before you can post a comment (best way to prevent spam). ( Not a member? )