The DFT and the FFT

Finding the frequencies in a list of numbers

An interactive lesson with 6 steps, about 5 minutes: you predict, drag and solve, with instant feedback on every answer. It runs in your browser and needs JavaScript.

What you’ll learn

• The DFT measures each frequency by comparing the signal with test waves.
• Mismatched frequencies cancel; the list of strengths is the spectrum.
• The FFT cuts the work from $N^2$ to $N\log_2 N$ by splitting into halves.

Steps

1. Hidden notes
2. Probe for tones
3. The discrete Fourier transform
4. Too slow?
5. The Fast Fourier Transform
6. How much faster?