Fourier transform

The DFT writes N samples as N complex sinusoids at k·fs/N, so bins are fs/N apart; windows (Hann, Hamming) trade main-lobe width for lower leakage, zero-padding only interpolates, and the FFT computes it all in O(N log N).

8 min read726 wordscore0 viewsupdated 2026-10-15

Definition

Fourier transform expresses a signal as a sum of complex sinusoids, giving the amplitude and phase of each frequency. Fourier introduced the idea in Théorie analytique de la chaleur (1822). Audio work uses the discrete Fourier transform (DFT) of NN samples, computed by the fast Fourier transform (FFT) of Cooley and Tukey, "An Algorithm for the Machine Calculation of Complex Fourier Series" (Mathematics of Computation, 1965). Gauss had used the same idea around 1805, unpublished in his lifetime.

A waveform shows pressure against time. Pitch, vowel formants and the timbre of an instrument are patterns in frequency, which a waveform hides. A 1 kHz tone and a 1.1 kHz tone look almost the same over a few milliseconds, but they are two separate lines in a spectrum. Every spectrogram, mel feature and MFCC in this module starts from the DFT.

From the integral to N bins

For a continuous signal the transform is an integral over all time:

X(f)=∫−∞∞x(t) e−j2πft dtX(f)=\int_{-\infty}^{\infty}x(t)\,e^{-j2\pi f t}\,dt
X(f)X(f)
complex: ∣X(f)∣|X(f)| is the amplitude, ∠X(f)\angle X(f) the phase of frequency ff

A computer has NN samples at rate fsf_s, so it evaluates NN frequencies only:

X[k]=∑n=0N−1x[n] e−j2πkn/N,x[n]=1N∑k=0N−1X[k] e j2πkn/N,fk=k fsNX[k]=\sum_{n=0}^{N-1}x[n]\,e^{-j2\pi kn/N},\qquad x[n]=\frac{1}{N}\sum_{k=0}^{N-1}X[k]\,e^{\,j2\pi kn/N},\qquad f_k=\frac{k\,f_s}{N}
kk
bin index; bin kk correlates the signal with a sinusoid at kfs/Nk f_s/N Hz
fs/Nf_s/N
bin spacing =1/T=1/T, the inverse of the analysed duration T=N/fsT=N/f_s
1/N1/N
numpy and torch put the 1/N1/N on the inverse; a unit sine on a bin gives ∣X[k]∣=N/2|X[k]|=N/2

The DFT is a matrix product X=FxX=Fx with Fkn=e−j2πkn/NF_{kn}=e^{-j2\pi kn/N}. Row kk is a probe sinusoid. The inverse recovers xx exactly, so no information is lost: phase is kept alongside magnitude. For real xx, X[N−k]=X[k]‾X[N-k]=\overline{X[k]}. Only bins 0…N/20\ldots N/2 are unique, which is why rfft returns N/2+1N/2+1 of them. Bins above N/2N/2 are the negative frequencies.

DFT as a matrix product · N = 8 samples at fs = 8 kHz → bin spacing fs/N = 1 kHzx[n], n = 0…7cos 1 kHz + ½ cos 2 kHz8 ms, real-valuedF[k, n] = e^(−j2πkn/N)k=07real partrow k: aprobe atk·fs/N HzN² = 64mult-adds|X[k]|0041122233445−326−247−1shaded: unique bins 0…N/2 (N/2 + 1 = 5) · grey: mirror X[N−k] = X*[k] · 2nd row: k·fs/N kHzradix-2 FFT (Cooley–Tukey 1965), N = 8x[0]x[4]x[2]x[6]x[1]x[5]x[3]x[7]X[0]X[1]X[2]X[3]X[4]X[5]X[6]X[7]2-point4-point8-pointinputs in bit-reversed order (4 = 100₂ → 001₂ = 1)split n into even / odd:E[k] = DFT_N/2 of x[0,2,4,6]O[k] = DFT_N/2 of x[1,3,5,7]X[k] = E[k] + W^k·O[k]X[k+N/2] = E[k] − W^k·O[k]W = e^(−j2π/N), k < N/2recurse: log₂ N = 3 stages× N/2 = 4 butterflies eachN = 8: 12 butterflies vs 64N = 1024: 5,120 vs 1,048,576cost O(N log N) vs O(N²)
fig.Top: 8 samples of cos(1 kHz) + ½ cos(2 kHz) at fs = 8 kHz are multiplied by the 8 × 8 DFT matrix (real part shown; row k probes k·fs/N). The magnitudes are 4 and 2 (N·A/2) at bins 1 and 2, mirrored at bins 7 and 6; the 5 shaded bins are unique. Bottom: the radix-2 FFT splits even and odd samples recursively, so 3 stages of 4 butterflies (12) replace the 64 multiply-adds of the matrix.

Leakage and windows

The DFT treats the NN samples as one period of a periodic signal. If a tone completes a whole number of cycles in NN, it lands on one bin. Otherwise the periodic copy has a jump at the frame edge. The energy then leaks into every bin, and a weak tone nearby can drown in it. The tone's peak also reads low when it falls between bins (scalloping loss).

Multiplying the frame by a window w[n]w[n] that tapers to zero removes the jump. In frequency, this convolves the spectrum with the window's transform: a main lobe and sidelobes. Analysis uses the periodic form, which matches torch.hann_window and scipy's spectral defaults:

wHann[n]=0.5−0.5cos⁡2πnN,wHamming[n]=0.54−0.46cos⁡2πnNw_{\text{Hann}}[n]=0.5-0.5\cos\frac{2\pi n}{N},\qquad w_{\text{Hamming}}[n]=0.54-0.46\cos\frac{2\pi n}{N}
0.54, 0.460.54,\,0.46
Hamming's coefficients, chosen to cancel the first sidelobe; it does not reach zero at the edges
WindowMain lobe (null to null)Highest sidelobeSidelobe decayScalloping loss
Rectangular2 bins−13.3 dB6 dB/octave3.92 dB
Hann4 bins−31.5 dB18 dB/octave1.42 dB
Hamming4 bins−42.7 dB6 dB/octave1.75 dB
Window properties (computed numerically; widths in bins of fs/N)

Hann is the default for audio features. Its sidelobes fall fast, so leakage far from a strong tone is tiny. Hamming has the lowest near sidelobe but a flat far floor. Both pay with a main lobe twice as wide as the rectangle's. No window separates two tones much closer than one bin, /T$ Hz.

|X[k]| dB · fs 8 kHz · N = 64 (8.0 ms) · Δf = fs/N = 125.0 Hz · pad ×1tone A: 0 dB at 1062.5 Hz = bin 8.50 · tone B: -50 dB at 2500 Hz · window: rect0-20-40-60-80-1000100020003000fs/2 = 4000 HzBA: highest raw bin k = 8 (1000.0 Hz) at -3.7 dB · scalloping = how far below 0 dBB's bin: A alone -33.2 dB · A + B -33.1 dB → B is buried in A's leakageA is 0.50 bins off the bin grid: its energy leaks into every bin via the sidelobesdots: N/2 + 1 = 33 unique bins (real signal)
window
Nzero-pad
fig.An FFT of N samples at 8 kHz of a 0 dB tone A plus a −50 dB tone B at 2500 Hz. Default (rectangular, N = 64, A at 1062.5 Hz = bin 8.5): the best bin reads −3.7 dB, and leakage at B's bin is −33.2 dB, so B is buried. Switch to Hann: the peak reads −1.4 dB and the leakage falls to −73.9 dB, so B shows at −50.0 dB. With Hamming the floor at B is −50.2 dB, and B reads −47.1 dB, only 3.1 dB above it. With N = 128, A sits exactly on bin 17 and even the rectangle shows no leakage. Zero-pad ×8 and the curve peaks at 1062.5 Hz and 0.0 dB, but the main lobe is no narrower.

Zero-padding and resolution

Appending zeros before the FFT gives more bins on a finer grid, fs/(PN)f_s/(PN). They sample the same windowed spectrum more densely. This is useful for locating a peak, and it is free when the FFT wants a power of two (n_fft=512 for a 400-sample window). It cannot separate two tones that the original NN could not. Resolution is set by the window duration T=N/fsT=N/f_s, roughly 2/T2/T to 4/T4/T Hz for the main lobe.

The FFT

Split the sum into even and odd nn. Each half is a DFT of length N/2N/2, and X[k]=E[k]+WkO[k]X[k]=E[k]+W^kO[k], X[k+N/2]=E[k]−WkO[k]X[k+N/2]=E[k]-W^kO[k] with W=e−j2π/NW=e^{-j2\pi/N}. Applying this recursively gives log⁡2N\log_2 N stages of N/2N/2 butterflies. For N=1024N=1024 that is 5,120 butterflies instead of 1,048,576 multiply-adds, roughly 200× fewer. Mixed-radix and Bluestein variants handle any NN (400 included) in O(Nlog⁡N)O(N\log N).

Worked example: frame length at 16 kHz

n_fftDurationΔf = fs/Nrfft bins450 Hz falls at binHann main lobe
25616 ms62.5 Hz1297.2250 Hz
40025 ms40 Hz20111.25160 Hz
51232 ms31.25 Hz25714.4125 Hz
400 padded to 204825 ms7.8125 Hz grid102557.6160 Hz (unchanged)
Bin spacing, unique bins and where a 450 Hz tone lands, for common frame lengths at fs = 16 kHz
python
1import numpy as np
2
3fs, N = 16_000, 400 # one 25 ms frame
4n = np.arange(N)
5x = np.sin(2 * np.pi * 450 * n / fs) + 0.001 * np.sin(2 * np.pi * 1_210 * n / fs) # tone + a -60 dB tone
6
7freqs = np.fft.rfftfreq(N, d=1 / fs) # k * fs / N: 0, 40, ..., 8000 Hz
8print(len(freqs), freqs[1]) # 201 40.0
9
10def spectrum_db(x, window):
11 X = np.fft.rfft(x * window) # N/2 + 1 complex bins
12 return 20 * np.log10(np.abs(X) / (window.sum() / 2) + 1e-12) # 0 dB = unit-amplitude sine
13
14rect = np.ones(N)
15hann = 0.5 - 0.5 * np.cos(2 * np.pi * n / N) # periodic Hann (np.hanning is the symmetric one)
16k = round(1_210 / (fs / N)) # bin of the weak tone (30.25 -> 30)
17for name, w in [("rect", rect), ("hann", hann)]:
18 d = spectrum_db(x, w)
19 print(name, d.argmax(), f"{d.max():.1f} dB", f"at 1210 Hz: {d[k]:.1f} dB")
20# rect 11 -0.9 dB at 1210 Hz: -37.6 dB <- the -60 dB tone is hidden by leakage
21# hann 11 -0.4 dB at 1210 Hz: -60.0 dB <- now it is visible
22
23Xp = np.abs(np.fft.rfft(x * hann, 4 * N)) # zero-pad x4: 10 Hz grid
24print(np.fft.rfftfreq(4 * N, 1 / fs)[Xp.argmax()]) # 450.0
Leakage, windowing and zero-padding with numpy.fft (runs as is; printed values in comments)

Check yourself

At fs = 16 kHz with n_fft = 512, what is the bin spacing, and which bin is closest to 1 kHz?

Check yourself

Two tones 30 Hz apart are merged in a Hann-windowed 25 ms frame at 16 kHz. What separates them?

Remember

  • ✓DFT: X[k]=∑nx[n]e−j2πkn/NX[k]=\sum_n x[n]e^{-j2\pi kn/N}, bin kk at kfs/Nk f_s/N, spacing fs/N=1/Tf_s/N = 1/T; exactly invertible.
  • ✓Real input: X[N−k] = conj(X[k]), so N/2 + 1 unique bins (rfft); bins above N/2 are negative frequencies.
  • ✓Off-bin tones leak; windows trade main-lobe width (rect 2 bins, Hann/Hamming 4) for sidelobes (−13 / −31 / −43 dB).
  • ✓Hann's sidelobes fall at 18 dB/octave, which makes it the audio default; scalloping is 3.9 dB for rect, 1.4 dB for Hann.
  • ✓Zero-padding refines the grid but not the resolution; only a longer window resolves closer tones.
  • ✓FFT (Cooley–Tukey 1965): log₂N stages of N/2 butterflies, O(N log N): 5,120 butterflies vs ~10⁶ operations at N = 1024.
← back to Deep Learning roadmap