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.

The Danielson-Lanczos Lemma

<< Previous Next >>

This is the first key to understanding the FFT. It takes quite a few steps, but I've broken the tutorial down into small digestible steps to make this as smooth as possible.

Here is the Danielson-Lanczos Lemma:

Danielson-Lanczos Lemma

Equation 2

Note it is a DFT broken up into two summations of half the size of the original. The first summation is the "even terms", E, and the second is the "odd terms", O. W is the "twiddle factor", and understanding it is another key to understanding the FFT. Here is the "twiddle factor".

Twiddle Factor

Equation 3

How to Expand the DFT

To expand the DFT into even and odd terms as in the lemma above, you do the following. For the even term you substitute 2k into k, then you create a summation of half the size of the original. For the odd term you substitute 2k + 1 into k, then create a summation of half the size of the original.

Here is a the summation halved:

Reduce Summation by Half

The example below shows the process required for a first level expansion.

D-L Lemma Worked Out

Equation 4

Note the "twiddle factor" above and where it comes from.

And putting the even and odd terms together from above, we get the Danielson Lanczos first level expansion:

D-L Result for first level expansion

Equation 5

The above is a first level break down. You can continue to break each term down into even and odd terms until you run out of samples and only have one value in the summation. Like this:

Unity Summation

Equation 6

This happens because you keep halving the number of values summed on each expansion of the equation. For the FFT we want all summations to be expanded down to 1 term. Here is the pattern of expansion for the Danielson-Lanczos Lemma:

DL Binary Breakdown

As shown in the diagram above, the D-L Lemma breaks down in a binary manner. That is, the number of terms expands as follows 1, 2, 4, 8, 16, 32, etc. In order to get all of the summation to unity, 1, therefore, we must have a power of base 2 number of samples, or N=2^r samples. So, an FFT requires N = 2^r samples.

For a sample size of N=2, a first level expansion will be enough to get the summations to unity. The first level expansion will look like this after plugging into equation 5 above.

DL Lemma for 2 Inputs

Equation 7

The summations are reduced to unity, and all that remains is a twiddle factor and input values, x(0) and x(1). This is the general form used for the Butterfly diagram, shown later in this tutorial.

Next example will be expansion of the D-L Lemma to 4 terms.

<< Previous Next >>