FFT Algorithm

The FFT has a fairly easy algorithm to implement, and it is shown step by step in the list below. This version of the FFT is the Decimation in Time Method
 
 

  1. Pad input sequence, of N samples, with ZERO's until the number of samples is the nearest power of two.
      2. e.g. 500 samples are padded to 512 (2^9)
  2. Bit reverse the input sequence.
      3. e.g. 3 = 011 goes to 110 = 6
  3. Compute (N / 2) two sample DFT's from the shuffled inputs.
      4. See "Shuffled Inputs"
  4. Compute (N / 4) four sample DFT's from the two sample DFT's.
      5. See "Shuffled Inputs"
  5. Compute (N / 2) eight sample DFT's from the four sample DFT's.
      6. See "Shuffled Inputs"
  6. Until the all the samples combine into one N-sample DFT
      7. FFT decimation.

Shuffled Inputs

The process of decimating the signal in the time domain has caused the INPUT samples to be re-ordered. For an 8 point signal the original order of the samples is

But after decimation the order is At first it may look as if there is no order to this new sequence, BUT if the numbers are represented as binary a patter soon becomes apparent.

 What has happened is that the bit patterns representing the sample number has been reversed. This new sequence is the order that the samples enter the FFT.

 So far we have not mentioned anything about how the samples are recombined to produce the result. This is covered in the next section.

On to FFT Butterfly or back to Mathematics of Time Decimation

 or back to FFT Contents or back to Main Contents