Outline For Learning About The DFT and FFT
Here is an outline of the steps used to explain both the DFT and FFT.
- First the DFT will be explained. This is the vital first step, since an FFT is a DFT and there are, therefore, basic concepts in common with both. Learning this first will make understanding the FFT easier.
- Once you understand the basic concepts of a DFT, the FFT will be explained. This is broken into several steps.
- The "Danielson-Lanczos Lemma"
will be explained, which is the first step to understanding the FFT.
- The "twiddle factor" will be explained, which is another key to understanding the FFT.
- The "Butterfly Diagram" will be explained. The Butterfly is an FFT in diagram form. It's the final step of this tutorial and builds on the prior concepts.
- Several examples will be given along with the basic concepts above.