DFT & FFT

Computers hold N samples, not infinite integrals. The Discrete Fourier Transform asks N frequency questions of N samples — and the Fast Fourier Transform answers all N so cheaply that frequency analysis became free. The FFT may be the most-run nontrivial algorithm on earth.

Build the intuition

The DFT: N samples in, N bins out

Probe the samples with N harmonic phasors (k whole cycles across the frame, k = 0…N−1); each inner product yields one complex bin X[k]: the strength and phase of that frequency. It's lesson 1's projection, finite and exact — your 4-sample hand computation was a genuine DFT.

X[k] = \sum_{n=0}^{N-1} x[n]\, e^{-i 2\pi k n / N}

The fine print: bins and frames

N inputs give N bins — frequency resolution is sample-rate ÷ N. Want finer frequency detail? Record longer. And the DFT silently assumes your frame repeats forever — an assumption with consequences (spectral leakage) that lesson 7 confronts head-on.

FFT: divide and conquer, again

Computed naively, N bins × N samples = N² multiplications — a million-point spectrum would cost 10¹² operations. The FFT splits the DFT into even and odd halves, recursively, reusing shared work: N log N instead. For a million points that's ~50,000× faster — the difference between “impossible” and “real-time on a phone.” It's the discrete-math halving trick (merge sort's logic) applied to transforms.

See it move

InteractiveSpectral leakage & the window cure

frequency bin

Cycles in frame5

Apply a Hann window (fade the frame's edges)

5 cycles fit the 64-sample frame exactly — one clean spike. The DFT silently assumes your snippet repeats forever, and right now that assumption is true.

An actual 64-point DFT computed live: integer cycles land in one bin. (The smearing at non-integer cycles is lesson 7's story — feel free to preview it.)

A worked example

Size a real spectrum

Audio at 44,100 samples/s, FFT frame N = 1,024.
Bin spacing: 44,100 / 1,024 ≈ 43 Hz — bins at 0, 43, 86, 129 Hz…
Cost: N log₂N ≈ 1,024 × 10 ≈ 10,000 multiplies — microseconds on any phone, ~43 spectra per second of audio, live.
These two numbers — resolution and cost — are the first calculation of every real DSP design.

Out in the world

Wi-Fi transmits inside an FFT

OFDM — the scheme inside Wi-Fi, 4G/5G, and DVB — encodes data on hundreds of orthogonal sub-frequencies simultaneously, using an inverse FFT to build each transmitted symbol and an FFT to unpack it. Your video call is FFTs in both directions, thousands per second.

Common confusion, cleared

“The FFT is a different transform than the DFT.”

Same outputs exactly — the FFT is a fast algorithm for the DFT, exploiting symmetry to skip redundant work. “We took an FFT” means “we computed the DFT, cleverly.”

“More FFT points always mean a better spectrum.”

Zero-padding adds bins but no new information — resolution comes from recording longer, not from interpolating prettier plots. The data you took bounds what any algorithm can reveal.

Check yourself

PracticeQuick check

1,000 samples at 1,000 Hz are FFT'd. Bin spacing is…

Recap

DFT: N projections onto whole-cycle phasors — exact, finite, computable.
Resolution = sample rate / N: longer frames see finer frequencies.
FFT computes it in N log N — the speedup that made DSP ubiquitous.

Progress saves in this browser.