9.5 Fast Fourier transform

Source: Ideas from Computational Physics (Landau, Páez, Bordeianu), §9.5. Rewritten in original wording — no textbook code dumps. Continues 9.4c. Next: 9.5b.

Why $N^2$ hurts

The DFT

$$Y_n=\frac{1}{\sqrt{2\pi}}\sum_{k=0}^{N-1} Z^{nk} y_k,\qquad Z=e^{-2\pi i/N}$$

needs a complex multiply for each $(n,k)$ pair — about $N^2$ work. At $N\sim10^3$ that is the difference between a coffee break and an overnight job. Cooley–Tukey (and earlier rediscoveries) reuse the periodicity of $Z^{nk}$ to cut the cost to roughly $N\log_2 N$.

Divide, butterfly, conquer

Split the data into halves, transform each half, combine. Each stage of length $N$ costs $O(N)$ butterflies; $\log_2 N$ stages $\Rightarrow O(N\log N)$. Pick the butterfly map $(y_p,y_q)\mapsto(y_p\pm Z y_q)$ and the bit-reversal consequence among lookalikes.

For $N=8$, powers of $Z$ collapse to four independent values ($Z^0..Z^3$ and sign flips). Grouping $y_p\pm y_q$ before multiplying by $Z$ removes redundant work — 24 complex multiplies in a staged butterfly network versus 64 in the naive sum.

Bit reversal

With $b=\log_2 N$ bits, reverse the bits of each index $0..N-1$ (table below for $N=8$).

dec	bits ($N=8$)	reversed	dec′
0	000	000	0
1	001	100	4
2	010	010	2
3	011	110	6
4	100	001	1
5	101	101	5
6	110	011	3
7	111	111	7

Same idea with 4 bits for $N=16$ (first half of reversed indices are even). Production FFTs hide this shuffle; you should still know it exists when comparing hand butterflies to library fft.

Practice stance

Prefer a trusted FFT for production spectra. Implement a tiny radix-2 butterfly / bit-reverse once so the $N\log N$ story is visceral — then call libraries. Pair with §9.4 filters: FFT → multiply by $H(\omega)$ → iFFT is the fast convolution route.

Quiz

FFT

1 / 4

Naive DFT cost scales as…

Pick an answer to see if you are right.

Next: 9.5b FFT labs.