The Danielson-Lanczos Lemma
|
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:
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".
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:
The example below shows the process required for a first level expansion.
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:
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:
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:
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.
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 >> |