AlwaysLearn

A DFT and FFT TUTORIAL

A DFT is a "Discrete Fourier Transform". An FFT is a "Fast Fourier Transform". An FFT is a DFT, but is much faster for calculations. The whole point of the FFT is speed in calculating a DFT.

DFT and FFT

FFT

Overview of The FFT

<< Previous Next >>

This is a "decimation in time" FFT, because the input value to the FFT is the time wave, x(t). The time wave could be a sound wave, for example.

Speed!

The only reason to learn the FFT is for speed. An FFT is a very efficient DFT calculating algorithm.

How fast is an FFT versus a "straight" DFT?

FFT N Log(N) Operations

Equation 1

This means that a 1024 sample FFT is 102.4 times faster than the "straight" DFT. For larger numbers of samples the speed advantage improves. For example, for 4096 samples the FFT is over 340 times faster.

x(k) is the time wave that is converted to a frequency spectrum by the DFT.

Learning the FFT is a bit of a challenge, but I'm hoping this tutorial will make it relatively easy to learn. Here is a basic outline of the tutorial:

  1. First, you'll need to learn the "Danielson-Lanczos Lemma" (D-L Lemma). This will require long equation writing, but it's a vital component of the FFT. I'll give several examples.
  2. You'll need to understand the "twiddle factor" -- W_N^n. This was discussed a little during the DFT tutorial. It along with the "D-L Lemma" are essential to understanding how an FFT works.
  3. Then the "Butterfly Diagram" will be explained. This builds on the first two concepts above. The Butterfly diagram is a diagrammatic representation of an FFT algorithm.
  4. You'll also learn about the "reverse bit pattern" for data input and the reason for it.
    << Previous Next >>