Discrete Fourier Transform and FFT

Why Does This Exist?

Theory gives spectra as integrals; hardware holds finite samples. The DFT defines the spectrum on $n$ samples as $n$ bins $X_k = \sum_{t=0}^{n-1} x_t e^{-2\pi i k t/n}$, and the naive sum costs $O(n^2)$: a $1$-megapixel image row-by-row would stall. The FFT (Cooley-Tukey, 1965) exploits symmetries of roots of unity to cost $O(n \log n)$, which is why spectral filtering, fast convolution, and spectral solvers run at all. Continuous theory is the parent Fourier page; filtering via bins is the convolution theorem.

The one idea you need first

The $n$th roots of unity $W_n = e^{-2\pi i/n}$ repeat with period $n$ and square to half-size roots ($W_n^2 = W_{n/2}$). The FFT's halving reuses these symmetries: even and odd subsequences share twiddle factors instead of recomputing them.

Think of It Like This

How It Actually Works

Radix-2 decimation in time: $X_k = E_k + W_n^k O_k$ and $X_{k+n/2} = E_k - W_n^k O_k$, where $E, O$ are the half-size DFTs of even and odd samples. One butterfly computes both outputs from $(E_k, O_k)$ with one multiply. Recurse to size $1$; total $n \log_2 n$ operations. Bit-reversal permutes inputs so the recursion runs in place.

Bin $k$ means frequency $k f_s/n$ for sampling rate $f_s$; resolution $f_s/n$. Off-bin tones leak across bins; windowing (Hann: taper edges) localizes leakage at the cost of wider peaks.

Worked example

$n = 1{,}024$ audio samples at $f_s = 8{,}192$ Hz. Naive DFT: $1{,}024^2 \approx 1.05$ million complex multiplies. FFT: $1{,}024 \times 10 = 10{,}240$: ratio above $100$. Resolution $8{,}192/1{,}024 = 8$ Hz per bin: a $440$-Hz tone lands in bin $55$ exactly ($55 \times 8 = 440$), peak height $512 \times$ amplitude. A $443$-Hz tone straddles bins $55$ and $56$ (leakage): Hann windowing concentrates $80\%$ of its energy into $3$ bins instead of smearing over $12$.

Code

1import cmath2
3
4def fft(xs: list[complex]) -> list[complex]:5    n = len(xs)6    if n == 1:7        return xs  # base case8    even = fft(xs[0::2])9    odd = fft(xs[1::2])  # halve: decimation in time10    out: list[complex] = [0j] * n11    for k in range(n // 2):12        tw = cmath.exp(-2j * cmath.pi * k / n) * odd[k]  # twiddle combine13        out[k] = even[k] + tw  # butterfly top14        out[k + n // 2] = even[k] - tw  # butterfly bottom15    return out16
17
18xs = [1.0, 0.0, -1.0, 0.0, 1.0, 0.0, -1.0, 0.0]  # cosine, period 419spec = [round(abs(c), 3) for c in fft([complex(x) for x in xs])]20print(spec)  # -> peaks 4.0 at bins 2 and 6, zeros elsewhere

Bins $2$ and $6$ read $4.0$ (half the $8$ samples times amplitude $1$); all others $0$: exact binning for an on-grid tone.

Watch Out For

The Quick Version

• The DFT bins finite samples; naive cost is $O(n^2)$.
• The FFT halves recursively through butterflies to $O(n \log n)$.
• At $n = 1{,}024$ the FFT needs $10{,}240$ steps versus $1.05$ million: $100$ times faster.
• Bin $k$ means $k f_s/n$ Hz; resolution is $f_s/n$ ($8$ Hz in the example).
• Off-grid tones leak; Hann windows concentrate energy threefold.
• Zero-padding smooths without resolving; longer records resolve.

What to Read Next

• Vectors, Matrices and Tensors
• Linear Systems and Least Squares
• Computational Complexity for ML