Discrete Fourier Transform Lab
From samples to spectrum
The Fourier Series lab builds shapes out of spinning circles. This lab runs the idea in reverse on real, sampled data: the discrete Fourier transform (DFT) takes N samples and reports how much of each frequency they contain. Explore what the spectrum reveals — and what sampling hides — then see why windows matter, how a square-wave basis (Walsh–Hadamard) compares, and why convolution turns into simple multiplication once you are in the frequency domain.Mix two sine tones (plus optional noise) and sample them 64 times across one window. Frequencies are counted in cycles per window, so a tone that completes 5 cycles lands on bin 5. Push a tone past 32 cycles — the Nyquist limit, half the sample count — and watch what the samples do.
Spectrum analyzer
Top: the analog signal and the 64 samples the DFT actually sees. Bottom: the spectrum those samples produce.
Experiments to try
The mirror
Every peak has a twin on the right half. For a real signal the DFT is symmetric — bins above 32 repeat the bins below, so only the left half carries information.
Fall between the bins
Set Tone B to 12.5 cycles. The single bar becomes a smear across neighbouring bins — spectral leakage, the subject of the next tab.
Break Nyquist
Drag Tone A to 40 cycles. It reappears at bin 24: with only 64 samples, 40 cycles and 24 cycles leave identical dots. That impostor is aliasing.
The DFT quietly assumes the window repeats forever. When a tone doesn't complete a whole number of cycles, the copies don't line up and the jump at the seam sprays energy across the spectrum. A window fades the signal in and out so there is no jump. Here a loud tone sits beside a quiet one — pick a window and see whether the quiet tone survives the loud one's leakage.
Window explorer
The spectrum is in decibels so small things stay visible: −40 dB is 1/100 of the loud tone's amplitude.
What to look for
With the rectangular window the dots between the two tones sit far above the floor — that skirt is leakage, and at −40 dB it swallows the quiet tone. Hann and Blackman pull the skirt down so the quiet tone pops out, but the loud tone's peak grows wider: every window trades resolution (telling close tones apart) for dynamic range (seeing quiet tones next to loud ones). Set the loud tone to exactly 10.0 cycles and leakage vanishes for every window — the copies line up perfectly.
A transform is a choice of basis: a set of reference waves that every signal is rebuilt from. The DFT uses sines and cosines. The Walsh–Hadamard transform (WHT) uses square waves that only ever take the values +1 and −1. Give both the same budget of numbers and see which one rebuilds each signal better — the answer depends entirely on the signal.
Basis explorer
Keep only the strongest coefficients that fit the budget, rebuild the signal from them, and measure what was lost.
What to look for
Compare the two bases on each signal at a budget of 4: the smooth signal is a DFT win, the square wave and
blocky steps are Walsh wins, and the spike defeats both. In the matrix view, each row is one basis wave:
smooth cosine stripes for the DFT, the self-similar ±1 quilt for Walsh–Hadamard, built by
tiling four copies of the half-size matrix with one sign-flipped. The butterfly view shows why both are
fast: the same log₂N stages of pairwise sums and differences — the FFT just adds
a complex rotation (a twiddle factor) on one branch. For six families raced side by side — wavelets, polynomials and ReLU hinges included — see the Basis Functions lab.
The Convolution lab slid a 5-tap kernel across a noisy signal. Here is the same signal and the same kernels, computed two ways: the sliding sum on the left, and on the right — transform both, multiply the spectra bin by bin, transform back. The dashed trace is the second route laid over the first.
Two routes, one answer
Left column: time domain. Right column: frequency domain.
Why this matters
The kernel's spectrum |H[k]| is the filter's frequency response: it says, frequency
by frequency, how much passes through. "Smoothing" becomes "low-pass"; "edge detection" becomes
"blocks DC". The two routes agree to within rounding error The two routes agree to rounding error (around 10−15).mdash; the readout shows how tiny the gap is. One honest detail:
the DFT treats the signal as repeating, so this is circular convolution — the last few
samples wrap around to meet the first ones. Real systems pad with zeros to avoid that, and with the FFT
the frequency route becomes far cheaper than sliding for long kernels.
The DFT is the bridge between the signal you record and the frequencies inside it. Five ideas carry most of its weight in signal processing and in AI.
1. The formula is the unit circle, sampled
For N samples $x[0], \dots, x[N-1]$, the DFT produces N complex numbers: $$X[k] = \sum_{n=0}^{N-1} x[n]\, e^{-2\pi i\, kn/N}, \qquad k = 0, \dots, N-1$$ Each $e^{-2\pi i\, kn/N}$ is a point on the unit circle, stepping k notches per sample. $X[k]$ measures how strongly the signal lines up with that rotation: its magnitude is how much of frequency k is present, its angle is the phase. It is the discrete, finite cousin of the Fourier series — the same idea, applied to data you can actually store.
2. Sampling sets hard limits
With N samples per window you can only resolve frequencies up to $N/2$ cycles (the Nyquist limit); anything faster aliases onto a slower frequency that fits the same samples. That is why audio is recorded at 44.1 kHz — just over twice the ~20 kHz limit of hearing — and why anti-aliasing filters sit in front of every analog-to-digital converter.
3. The DFT is a matrix, and the FFT is a shortcut
Collect the rotations into an $N\times N$ matrix $F_{kn} = e^{-2\pi i\,kn/N}$ and the DFT is just $X = Fx$ — a change of basis, exactly the kind of matrix transformation covered earlier. Done directly that costs $O(N^2)$ operations. The fast Fourier transform (FFT) exploits the matrix's repeating structure to do it in $O(N\log N)$ through $\log_2 N$ stages of butterflies; for a million samples that is the difference between minutes and milliseconds. (The FFT diagram in the lab draws the wiring in the same order as the Walsh–Hadamard network; a real FFT also reorders its inputs, but the stage structure is the same.)
4. Walsh–Hadamard: the same idea with square waves
A Hadamard matrix contains only $+1$s and $-1$s with mutually orthogonal rows, $H_N H_N^\mathsf{T} = NI$, and every power-of-two size grows from $H_1=[1]$ by one rule: $$H_{2N} = \begin{pmatrix} H_N & H_N \\ H_N & -H_N \end{pmatrix}$$ Each row is a square wave; the number of sign changes is its sequency, the WHT's stand-in for frequency, which is why the lab sorts the coefficient bars by it. Energy still adds up, $\Vert x \Vert^2 = N\sum_k c_k^2$, and the fast version is a butterfly network that needs only additions and subtractions. That cheapness puts the WHT in some image and video codecs, in the spreading codes of CDMA radio, in Reed–Muller error-correcting codes, and in quantum computing, where the Hadamard gate applied to $n$ qubits is exactly $H_{2^n}$. It also appears in modern AI: several schemes for compressing large language models (QuIP#, QuaRot) multiply weights by a randomized Hadamard matrix before quantizing, which spreads out the few extreme values that would otherwise wreck low-precision storage.
The honest limit: the DFT turns ordinary convolution into multiplication; the WHT does not. It diagonalizes a different, XOR-indexed "dyadic" convolution, and sequency is a combinatorial notion tied to binary structure, not a physical pitch. Treat the two as "both are orthogonal bases," not as interchangeable.
5. Where the DFT shows up in AI
- Speech and audio models. Recognizers such as Whisper don't read raw waveforms; they read a log-mel spectrogram — short, Hann-windowed DFTs taken every few milliseconds, exactly the windowing trade-off from tab 2.
- Positional encodings. The original Transformer marks token positions with sines and cosines at geometrically spaced frequencies, and rotary encodings (RoPE) rotate query and key vectors around the unit circle by position — see the Attention lab for what those vectors do.
- FFT-powered layers. FNet replaces attention with a plain 2-D Fourier transform, and long-convolution models (such as Hyena) use the FFT route from tab 4 to apply very long kernels cheaply.
- Reading CNN filters. Early convolutional layers tend to learn edge and texture detectors; in frequency terms they are band-pass filters, and the frequency response is often the clearest way to see what a learned kernel does.
Self check
Answer every question before checking.