x(t) = Σ Aₖ · sin(2πfₖt + φₖ) is any recording, price history or pixel row. The Fourier transform listens to the chord and tells you which notes are playing.
A recording, a price history, a row of pixels — each is a number per point in time or space. The Fourier transform re-describes the very same data as how much of each frequency is present, and the original is not lost: the inverse transform rebuilds it exactly.
x[n] ⇄ X[k] · a change of basisFor every frequency k, multiply the signal by a phasor spinning k times per window, then add. When the signal contains that frequency the products reinforce; when it does not they cancel. The sum is X[k], a complex number holding amplitude and phase.
X[k] = Σ x[n]·e^(−2πikn/N)Filtering a signal by sliding a kernel is convolution — the operation CNN layers perform. The convolution theorem says transform both, multiply point by point, and transform back. The same answer, with O(N log N) work instead of N·M.
x ∗ h = IFFT(FFT(x) · FFT(h))A signal is a recipe in the time domain: one number after another. The Fourier transform rewrites that recipe as how much of each frequency is present — same information, different coordinates, and patterns invisible in the first view (a weekly cycle, a tone buried in noise) become obvious in the second.
By the end you will be able to read a spectrum coefficient, explain why the FFT is fast, filter by multiplying spectra, spot aliasing when the sampling rate is too low, tell leakage from resolution, and see the Fourier transform hiding inside audio models, CNNs and positional encodings.
An audio clip, a price history, a row of pixels: all are values over an index. Almost every fact about them has a second, hidden description as a stack of sine waves.
A sine wave is completely described by three numbers: its amplitude A (how tall it gets), its frequency f (how many cycles fit in one second), and its phase φ (where in the cycle it starts). In symbols, x(t) = A·sin(2πft + φ). Every quantity is a plain number except t, the time.
Numeric check: take A = 2, f = 3 Hz, φ = π/2, and evaluate at t = 0.25 s. The phase angle is 2π·3·0.25 + π/2 = 2π, and sin(2π) = 0, so x = 2·0 = 0. The wave started a quarter cycle early, and at a quarter second it is back where it started — the arithmetic says so.
The interesting claim is that any signal — however jagged — can be written as a sum of such sines with different dials. A square wave is a loud fundamental plus a third harmonic at one-third the amplitude, a fifth at one-fifth, and so on. Nothing about the square wave looks sinusoidal, yet those sines rebuild its corners. The Fourier transform is the machine that reads the dials back out.
Stack up to three sine waves. The bars below are the DFT of the sum — integer frequencies land on one bin, fractional ones smear.
A full-amplitude integer tone gives |X[k]| = N/2 = 64 with no window; Hann roughly halves that and widens the peak, but kills the smear. Set tone 3 to 4.5 with no window to watch leakage appear.
The slow creep is the price of a sharp corner: a jump needs infinitely many harmonics, and truncating the sum leaves ripples near the edge (the Gibbs overshoot). Smooth signals need only a few terms — which is exactly why real audio and images compress so well in the frequency domain.
Which three numbers fully describe a single sine wave?
The Discrete Fourier Transform is one formula. Read it as N correlations: for each frequency, multiply the signal by a spinning arrow and add up the products.
Given N samples x[0], x[1], …, x[N−1], the DFT produces N complex coefficients:
X[k] = Σₙ₌₀ᴺ⁻¹ x[n] · e^(−2πikn/N) k = 0 … N−1
In plain English: e^(−2πikn/N) is a point spinning at frequency k (it completes k full turns as n runs through the window). At every sample you multiply the signal by the spinning point and add the result. If the signal contains that frequency, the products line up and reinforce; if it does not, they cancel. This is a correlation, the same dot product similarity you met in Lesson 01 — now with complex arrows from Lesson 19.
Each coefficient carries exactly the three dials from chapter 01:
The squared magnitude P[k] = |X[k]|² is the power spectrum: how much energy sits at frequency k. The angle ∠X[k] is the phase spectrum: where that frequency’s sine starts. Most analysis tasks keep the power and throw the phase away — for [1, 2, 3, 4], P = [100, 8, 4, 8], and the Parseval check below shows those four numbers add up to the signal energy.
Exact example, N = 4. Take x = [1, 0, 0, 0]. Every phasor equals 1 at n = 0 and the other three samples are zero, so X[k] = 1 for all k: DFT([1, 0, 0, 0]) = [1, 1, 1, 1]. A spike contains every frequency in equal measure. Flip it around: x = [1, 1, 1, 1] gives X[0] = 4, and at k = 1 the four phasor values 1, −i, −1, i sum to zero (likewise for k = 2, 3), so DFT([1, 1, 1, 1]) = [4, 0, 0, 0] — a constant has energy only at DC. One more: x = [0, 1, 0, 0] makes X[k] = e^(−2πik/4), so DFT([0, 1, 0, 0]) = [1, −i, −1, i]; moving the spike by one sample rotated every coefficient by a quarter turn, and X[3] is the conjugate mirror of X[1].
Edit the eight samples, or click a bar, and see exactly which sine wave that frequency bin stands for.
Set the signal to the impulse [1, 0, 0, 0, 0, 0, 0, 0]: every bin reads exactly 1, because a spike contains every frequency equally.
The transform is a change of basis, not a lossy step: N numbers in, N numbers out, and the inverse reconstructs the original bit for bit. The phasors are perpendicular axes for N-sample signals, the same way the unit vectors of Lesson 01 were for arrows.
Total energy is identical in both domains — the transform rotates the information into new coordinates without shrinking it. That is also why the inverse needs only the 1/N: no energy is created or destroyed.
For a real-valued signal of length N, what is X[0]?
The definition costs N² operations. Cooley and Tukey noticed that half the work is redundant — split the samples, solve two small problems, and stitch them with one multiply.
The DFT as written does N multiply-adds for each of N outputs: N². For N = 1,000,000 that is 10¹² operations — minutes to hours in Python. The Fast Fourier Transform computes the same N coefficients in N log₂N steps: about 2×10⁷, a speed-up of roughly fifty thousand times. This single algorithm is why frequency analysis is practical at all, and why it won a Nobel-adjacent place in computing history.
The idea. Split the samples into even indices and odd indices. Each half is a smaller DFT problem of size N/2. Then combine the two half-answers with one multiply per output — the twiddle factor W = e^(−2πik/N). One multiplication serves two outputs, because the second half is the same expression with the sign flipped:
X[k] = E[k] + W·O[k] k = 0 … N/2 − 1 X[k + N/2] = E[k] − W·O[k]
Each level of recursion does O(N) work, and halving N reaches 1 in log₂N levels. That product is the whole complexity: O(N log N). The catch is that the splitting needs N to be a power of two; otherwise pad the signal with zeros up to the next power.
Pick a signal length. The direct DFT does N² multiply-adds; the FFT does about N·log₂N complex multiplies. The gap is the whole story.
FFT lengths must be powers of two (or zero-padded to one). The table below fixes the exponent at idiomatic sizes.
| N | N² (DFT) | N log₂N (FFT) | speed-up |
|---|---|---|---|
| 2^3 = 8 | 64 | 24 | 3× |
| 2^6 = 64 | 4,096 | 384 | 11× |
| 2^10 = 1,024 | 1,048,576 | 10,240 | 102× |
| 2^16 = 65,536 | 4,294,967,296 | 1,048,576 | 4,096× |
| 2^20 = 1,048,576 | 1,099,511,627,776 | 20,971,520 | 52,429× |
| 2^24 = 16,777,216 | 281,474,976,710,656 | 402,653,184 | 699,051× |
Notice there is no approximation anywhere: the butterfly is exact algebra. Fast Fourier transforms differ only in how they shuffle and group the samples; the coefficients they produce are the same ones the slow definition would give, up to floating-point rounding.
Filtering a signal — blur, echo, moving average — is convolution. The convolution theorem says you can do it in the frequency domain with one pointwise product, and that single fact powers CNNs and FNet.
Convolution slides one signal past another and multiplies at every offset: y[n] = Σₘ x[m] · h[n−m]. Flip h, slide it along x, and at each position add up the overlapping products. A kernel h = [1/3, 1/3, 1/3] is a moving average; h = [1, 0, 0.4] adds an echo. The output is longer than the input: N samples with an M-tap kernel gives N + M − 1 values.
Doing it that way costs N·M multiply-adds. The convolution theorem offers a shortcut:
x ∗ h = IFFT( FFT(x) · FFT(h) )
Transform both signals, multiply the spectra pointwise (one product per frequency), transform back. Two FFTs and one inverse cost about 3·N log₂N — dramatically less than N·M once the kernel gets large. This is not a different result: multiplying spectra produces exactly the convolution, and small kernels lose only to constant factors.
One catch: the DFT treats the signal as repeating, so it computes circular convolution — the tail wraps around to the front. To get ordinary linear convolution, zero-pad both signals to at least N + M − 1 before transforming. The wrap is not a bug, it is the DFT’s periodic worldview showing through.
Edit two short signals. The animated slide builds the convolution; the crosses on the same stems are the FFT route, and the bars are the product of the two spectra.
Multiplying spectra multiplies magnitudes and adds angles, so the slow slide becomes L log L work — the reason large kernels and FNet use FFTs.
Check one product by hand: X[1]·H[1] = (−2+2i)(−i) = 2i − 2i² = 2 + 2i, which is exactly Y[1] above. Multiplying complex numbers multiplies their magnitudes and adds their angles — the frequency-domain image of dragging one signal across another.
If the first and last samples do not match, the seam looks like a jump and energy splashes into every frequency. A window smooths the ends, trading a wider peak for a far cleaner floor.
The DFT has a built-in assumption: the N samples are one period of a signal that repeats forever. If x[0] differs from the value the signal would have just after x[N−1], the periodic copy creates a discontinuity at every seam. A jump is made of every frequency at once, so its energy appears in bins that were supposed to be empty. This is spectral leakage: the smear around a peak that is not exactly periodic in the window.
A window function multiplies the signal by a taper that falls to (near) zero at both ends before the DFT is taken: X = DFT(x · w). The seam disappears, so the side lobes collapse. The price is a wider main peak: multiplying by a window convolves the ideal sharp spectrum with the window’s own spectrum, and a narrow-in-time taper is wide in frequency. That is the same time–frequency trade you will meet again in the spectrogram.
Same 64-sample window, transformed. The rectangular window (blue) has the narrowest peak and −13 dB sidelobes; Hann (orange) doubles the peak width and drops the sidelobes to −31 dB. Fainter, cleaner, wider — pick two. The spectra are zero-padded fourfold before transforming so the sidelobes between the 64-point bins become visible; that interpolation is exactly what the derivation below warns not to confuse with resolution.
The same identity holds for any N: Σw = (N−1)/2 for Hann, so the coherent gain approaches 0.5 as N grows. That factor is why a windowed amplitude spectrum must be doubled to compare with an unwindowed one — a detail that quietly breaks many measurement scripts.
True resolution is set by how long you observed, T = N/fs, never by how finely you sample the spectrum afterward. Padding makes a prettier curve; patience makes a better measurement.
Your two tones 0.5 Hz apart still look like one peak. What actually fixes it?
Sampling turns a continuous wave into a list of numbers. If the list is too sparse, fast waves and slow waves produce identical numbers — and no later processing can tell which one was real.
Recording a signal means reading its value every 1/fs seconds: x[n] = x(n/fs) for n = 0, 1, …, N−1. Two numbers fix what the DFT can see. The bin spacing, or frequency resolution, is Δf = fs/N, so bin k sits at f_k = k·fs/N hertz. The highest frequency is fs/2 — the Nyquist frequency. A sine needs at least two samples per cycle to show its shape (one crest, one trough); anything faster is sampled too sparsely to exist in the data.
What happens to a frequency above fs/2? It does not vanish — it folds. A 90 Hz tone sampled at 100 Hz produces exactly the same samples as a 10 Hz tone, so the spectrum shows a 10 Hz peak. The information was destroyed at the moment of sampling, not by the transform; no filter, no algorithm, and no amount of staring at the numbers can recover the original 90 Hz.
This is why every audio interface filters its input with an anti-aliasing low-pass before the analog-to-digital converter, and why downsampling a feature map in a neural network without blurring first produces moiré-like artifacts: decimation is sampling, and the feature map has high frequencies too.
Slide the tone and the sampling rate. Once the tone passes fs/2 it folds back and the dots spell a lower frequency that is not there.
At exactly fs/2 the samples can land on zero crossings and the tone disappears — the edge case is genuinely ambiguous.
The general rule is that sampling keeps only the fractional part of f/fs: everything above fs/2 reflects like a folded ruler, and each reflection flips the sign of the wave. Frequencies exactly at multiples of fs land on 0 Hz — the sampling points sit on identical phase, so a fast tone masquerades as DC.
A 90 Hz tone is sampled at 100 Hz. What does the spectrum show?
A single spectrum erases time: a rising chirp and a chord can share the same magnitude bars. The Short-Time Fourier Transform wins the when back by transforming overlapping windows.
The Short-Time Fourier Transform (STFT) cuts the signal into overlapping windows — say 1024 samples with a hop of 256 — applies a Hann or Hamming taper to each, runs an FFT, and stores the magnitude spectrum as one column of a picture. Stack the columns and you get a spectrogram: time on one axis, frequency on the other, brightness for energy. A chirp draws a rising diagonal; a chord draws a few horizontal lines; speech draws wavy bands called formants.
The window length is a genuine choice, not a detail. Short windows localize when something happened but blur which frequency it was; long windows do the opposite. The product of the two resolutions is fixed, so you can trade but never beat it — the same trade-off that the DFT’s frequency resolution and the spectrogram’s time resolution express from two directions.
A chirp sweeps from 20 Hz to the end frequency. The moving playhead picks one window; its spectrum is drawn below. Shorten the window and watch time sharpen while frequency blurs.
A narrow window separates when something happens; a wide window separates which frequency it was. No window setting escapes the product.
High-frequency dimensions change quickly and pin position precisely; low-frequency dimensions move slowly and separate distant regions. Together they give every position a unique fingerprint, and the distance-only dot product is what lets attention learn relative positions. The encoding is a Fourier basis in disguise, which is why it belongs in this lesson.
Answer before you look. The complexity, aliasing and zero-padding questions are exactly the ones that come up in real signal and ML work.
0 / 5 answered · 0 correct
01What does the Fourier transform do to a signal?
02What is the time complexity of the Fast Fourier Transform compared to the direct DFT?
03What does the convolution theorem state?
04Why does zero-padding a signal before the FFT NOT increase the true frequency resolution?
05In the original Transformer's sinusoidal positional encodings, why are the dimension pairs assigned geometrically spaced frequencies?
Click a card to swap the lazy description for what it actually means.
Four short problems with full worked answers. Exercise 5 — positional encodings — is derived step by step in chapter 07.
With fs = 128 Hz and N = 128 samples, bin k sits at k·fs/N = k Hz, so the peak bin index is the frequency in Hz. A 30 Hz tone x[n] = sin(2π·30n/128) has an exact DFT with X[30] = −64i, X[98] = +64i, and zeros elsewhere; |X[30]| = N/2 = 64. Check: the tone is integer-periodic in the window, so only bins 30 and its mirror 98 light up. Noise spreads instead of clustering. For white noise of standard deviation σ, each coefficient has expected |X[k]|² = Nσ² = 128 × 0.25 = 32, so the noise floor sits near √32 ≈ 5.7 — the 64 peak is more than ten times above it and trivially identified. Adding a Hann window before the DFT lowers the tone peak to 32 (coherent gain 0.5) but pushes the noise smeared around the peak much lower, which is the standard trade when the tone is weak.
A random signal has no special structure, so both algorithms must produce every coefficient. The agreement test is np.allclose(dft(x), fft(x), atol=1e-10): the two sums are mathematically identical, just evaluated in different orders; floating-point round-off differs at roughly 1e-14. Operation counts (N² vs N log₂N): 256 → 65,536 vs 2,048 (32×); 512 → 262,144 vs 4,608 (57×); 1024 → 1,048,576 vs 10,240 (102×); 2048 → 4,194,304 vs 22,528 (186×). The ratio grows like N/log₂N, so doubling N roughly doubles the advantage. In wall-clock time the Python loop is far slower than the compiled FFT, so the measured ratio is even larger; the asymptotics are what matter at scale.
Treat both as length-8 arrays. The linear convolution has support 4 + 3 − 1 = 6 samples, which already fits inside length 8, so the 8-point circular convolution does not wrap: it reads [1, 3, 6, 9, 7, 4, 0, 0]. The FFT route confirms it: X = [10, −0.414 − 7.243i, −2 + 2i, 2.414 − 1.243i, −2, 2.414 + 1.243i, −2 − 2i, −0.414 + 7.243i] and H = [3, 1.707 − 1.707i, −i, 0.293 + 0.293i, 1, 0.293 − 0.293i, i, 1.707 + 1.707i]; multiply pointwise to get Y = [30, −13.071 − 11.657i, 2 + 2i, 1.071 + 0.343i, −2, 1.071 − 0.343i, 2 − 2i, −13.071 + 11.657i], and the inverse transform returns exactly [1, 3, 6, 9, 7, 4, 0, 0]. To see wrap-around, shrink the DFT to length 4 — the same direct formula then gives [8, 7, 6, 9], because the tail y[4] = 7 folds onto y[0] = 1 + 7 = 8 and y[5] = 4 folds onto y[1] = 3 + 4 = 7. Zero-padding both signals to length 6 (or anything ≥ 6) removes the wrap. Every version conserves the same total of 30 = (1+2+3+4)·(1+1+1).
N = 128 at fs = 128 Hz gives bins every 1 Hz, and both 10 Hz and 12 Hz are integer-periodic in the window, so even the rectangular DFT shows two clean spikes at bins 10 and 12 — leakage from an exactly periodic tone lands only on other integer bins and cancels there. The windows matter when a tone is not integer-periodic (try 10.5 Hz) or when one tone is weak next to a strong neighbor: the rectangular window has sinc sidelobes only 13 dB down, so a strong tone's skirt can bury a quiet one; Hann suppresses sidelobes to about −31 dB and Hamming to −42 dB. The price is a wider main lobe (two adjacent bins dominate instead of one) and a lower peak — Hann's coherent gain is about 0.5, so a full-scale tone drops from |X| = 64 to about 32, and Hamming's is 0.536, giving 34.3. For two tones of similar strength 2 Hz apart, all three windows work; for a weak tone near a strong one, Hamming's low sidelobes win, which is why it is a default in speech processing.
You do not need to master these here. Each one gets a proper treatment in its own lesson; the one-line meaning is enough to keep reading. Orange dotted underlines in the prose point back to this list.
This lesson is a port of an open course. Everything here traces back to it — and the next step is running the code yourself.
Lesson text adapted from AI Engineering from Scratch (Phase 01, Lesson 20) and the Math Foundations Notebook reference build. The wave builder, DFT explorer, aliasing lab, convolution lab, spectrogram lab and FFT cost calculator are original to this page, as are the exact DFT examples ([1,0,0,0] → [1,1,1,1] and friends), the N = 4 butterfly and convolution arithmetic, the N = 8 Hann check, the Parseval and positional-encoding worked numbers, and the JPEG/DCT connection. Every displayed number is computed in your browser from the values shown. All labs run in your browser.