# 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).

Source: https://www.mlfoundry.in/learn/fourier-transform  
Section: Deep Learning › Speech and Audio Deep Learning  
Level: core · 8 min read · updated 2026-10-15

**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 $N$ 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)=\int_{-\infty}^{\infty}x(t)\,e^{-j2\pi f t}\,dt
$$

- $X(f)$: complex: $|X(f)|$ is the amplitude, $\angle X(f)$ the phase of frequency $f$

A computer has $N$ samples at rate $f_s$, so it evaluates $N$ frequencies only:

$$
X[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}
$$

- $k$: bin index; bin $k$ correlates the signal with a sinusoid at $k f_s/N$ Hz
- $f_s/N$: bin spacing $=1/T$, the inverse of the analysed duration $T=N/f_s$
- $1/N$: numpy and torch put the $1/N$ on the inverse; a unit sine on a bin gives $|X[k]|=N/2$

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

> Figure: 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 $N$ samples as one period of a periodic signal. If a tone completes a whole number of cycles in $N$, 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]$ 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:

$$
w_{\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.46$: Hamming's coefficients, chosen to cancel the first sidelobe; it does not reach zero at the edges

Window properties (computed numerically; widths in bins of fs/N)

| 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.

> Figure: 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, $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 $N$ could not. **Resolution** is set by the window duration $T=N/f_s$, roughly $2/T$ to $4/T$ Hz for the main lobe.

## The FFT

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

## Worked example: frame length at 16 kHz

Bin spacing, unique bins and where a 450 Hz tone lands, for common frame lengths at fs = 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) |

```python
import numpy as np

fs, N = 16_000, 400                                      # one 25 ms frame
n = np.arange(N)
x = np.sin(2 * np.pi * 450 * n / fs) + 0.001 * np.sin(2 * np.pi * 1_210 * n / fs)   # tone + a -60 dB tone

freqs = np.fft.rfftfreq(N, d=1 / fs)                     # k * fs / N: 0, 40, ..., 8000 Hz
print(len(freqs), freqs[1])                              # 201 40.0

def spectrum_db(x, window):
    X = np.fft.rfft(x * window)                          # N/2 + 1 complex bins
    return 20 * np.log10(np.abs(X) / (window.sum() / 2) + 1e-12)   # 0 dB = unit-amplitude sine

rect = np.ones(N)
hann = 0.5 - 0.5 * np.cos(2 * np.pi * n / N)             # periodic Hann (np.hanning is the symmetric one)
k = round(1_210 / (fs / N))                              # bin of the weak tone (30.25 -> 30)
for name, w in [("rect", rect), ("hann", hann)]:
    d = spectrum_db(x, w)
    print(name, d.argmax(), f"{d.max():.1f} dB", f"at 1210 Hz: {d[k]:.1f} dB")
# rect 11 -0.9 dB at 1210 Hz: -37.6 dB   <- the -60 dB tone is hidden by leakage
# hann 11 -0.4 dB at 1210 Hz: -60.0 dB   <- now it is visible

Xp = np.abs(np.fft.rfft(x * hann, 4 * N))                # zero-pad x4: 10 Hz grid
print(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)

> **Scaling conventions differ:** `np.fft.fft` does not divide by $N$; `ifft` does. A unit sine on a bin therefore reads $N/2$, and after a Hann window $N/4$. Divide by $\sum w/2$ to read amplitudes, or use `norm="ortho"` for an energy-preserving transform. Mixing conventions between training and inference shifts every log-spectrum by a constant.

> **Why phase is usually dropped:** Magnitude changes slowly and maps to what we hear. Phase wraps around $2\pi$ and depends on where the frame starts. Recognisers and classifiers therefore keep $|X|$ only. Generators cannot: a waveform must be rebuilt from a magnitude plus some phase, which is the job of Griffin–Lim or a neural vocoder such as **HiFi-GAN**.

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

- A. 31.25 Hz; bin 32
- B. 62.5 Hz; bin 16
- C. 31.25 Hz; bin 16
- D. 16 Hz; bin 64

**Answer:** A. 31.25 Hz; bin 32 — $\Delta f = 16000/512 = 31.25$ Hz, and $1000/31.25 = 32$ exactly, so 1 kHz sits on bin 32 with no leakage under a rectangular window.

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

- A. Zero-pad the frame to 4096 points
- B. Switch to a rectangular window
- C. Analyse a longer frame, e.g. 200 ms
- D. Use a Hamming window

**Answer:** C. Analyse a longer frame, e.g. 200 ms — Resolution comes from duration: 25 ms gives 40 Hz bins and a 160 Hz Hann main lobe. Zero-padding only interpolates that same lobe, and changing the window changes the lobe by at most 2×. A 200 ms frame gives 5 Hz bins and a 20 Hz main lobe.

**Key points**

- DFT: $X[k]=\sum_n x[n]e^{-j2\pi kn/N}$, bin $k$ at $k f_s/N$, spacing $f_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.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
