The Fourier transform, the FFT and the DFT

That title sounds like the beginning of a joke; “… was out for a stroll in the park. Then …” but of course it’s not.

For varius reasons, none of which are interesting to others right now, I recently felt a deep need to refresh my university knowledge on the Fourier transform (decomposition of a signal into its constituent frequencies), the DFT (discretization of a Fourier transform) and the FFT (swift computation of the DFT).

I found a, simply stated, fantastic visual set of explanations of what all of this is actually about, for those that doesn’t settle with numbers alone:

• Wikipedia on the Fourier transform (the theory behind the visuals below)
• Understanding the Fourier transform (loads of good comments follows the blog post)
• Animations for DFT (linked from the comments mentioned above)
• fftvisualize (linked from the comments mentioned above)