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 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:
- complex: is the amplitude, the phase of frequency
A computer has samples at rate , so it evaluates frequencies only:
- bin index; bin correlates the signal with a sinusoid at Hz
- bin spacing , the inverse of the analysed duration
- numpy and torch put the on the inverse; a unit sine on a bin gives
The DFT is a matrix product with . Row is a probe sinusoid. The inverse recovers exactly, so no information is lost: phase is kept alongside magnitude. For real , . Only bins are unique, which is why rfft returns of them. Bins above are the negative frequencies.
Leakage and windows
The DFT treats the samples as one period of a periodic signal. If a tone completes a whole number of cycles in , 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 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:
- Hamming's coefficients, chosen to cancel the first sidelobe; it does not reach zero at the edges
| Window | Main lobe (null to null) | Highest sidelobe | Sidelobe decay | Scalloping loss |
|---|---|---|---|---|
| Rectangular | 2 bins | −13.3 dB | 6 dB/octave | 3.92 dB |
| Hann | 4 bins | −31.5 dB | 18 dB/octave | 1.42 dB |
| Hamming | 4 bins | −42.7 dB | 6 dB/octave | 1.75 dB |
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.
Zero-padding and resolution
Appending zeros before the FFT gives more bins on a finer grid, . 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 could not. Resolution is set by the window duration , roughly to Hz for the main lobe.
The FFT
Split the sum into even and odd . Each half is a DFT of length , and , with . Applying this recursively gives stages of butterflies. For that is 5,120 butterflies instead of 1,048,576 multiply-adds, roughly 200× fewer. Mixed-radix and Bluestein variants handle any (400 included) in .
Worked example: frame length at 16 kHz
| n_fft | Duration | Δf = fs/N | rfft bins | 450 Hz falls at bin | Hann main lobe |
|---|---|---|---|---|---|
| 256 | 16 ms | 62.5 Hz | 129 | 7.2 | 250 Hz |
| 400 | 25 ms | 40 Hz | 201 | 11.25 | 160 Hz |
| 512 | 32 ms | 31.25 Hz | 257 | 14.4 | 125 Hz |
| 400 padded to 2048 | 25 ms | 7.8125 Hz grid | 1025 | 57.6 | 160 Hz (unchanged) |
1import numpy as np23fs, N = 16_000, 400 # one 25 ms frame4n = 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 tone67freqs = np.fft.rfftfreq(N, d=1 / fs) # k * fs / N: 0, 40, ..., 8000 Hz8print(len(freqs), freqs[1]) # 201 40.0910def spectrum_db(x, window):11 X = np.fft.rfft(x * window) # N/2 + 1 complex bins12 return 20 * np.log10(np.abs(X) / (window.sum() / 2) + 1e-12) # 0 dB = unit-amplitude sine1314rect = 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 leakage21# hann 11 -0.4 dB at 1210 Hz: -60.0 dB <- now it is visible2223Xp = np.abs(np.fft.rfft(x * hann, 4 * N)) # zero-pad x4: 10 Hz grid24print(np.fft.rfftfreq(4 * N, 1 / fs)[Xp.argmax()]) # 450.0Check 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: , bin at , spacing ; 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.