Chapter 35 · Section 35.2 · 85 min

The Fourier transform and the STFT

This section is about the Fourier transform, the tool that turns a list of audio samples into a list of frequencies. It rewrites a short block of samples as a sum of pure tones and reports how strong each tone is. Almost every speech and audio model starts with it, because sounds differ in where their energy sits in frequency, and the raw samples hide that. By the end you will compute the transform by hand and in code, know exactly what it shows and what it smears, and turn a recording into the spectrogram that speech models read.

Here is the problem in one example. Play an A (440 Hz) and the E above it (659.3 Hz) together. The samples form a wiggle that never quite repeats, with no visible trace of either note. A speech recognizer has the same problem with every slice of speech. For each 25 ms of audio it needs to know how much energy sits near 300 Hz, near 1,200 Hz, and near 3,000 Hz, because vowels and consonants differ in exactly that. The Fourier transform pulls those numbers, and the two notes, back out.

A digital recording, as §35.1 built it, is a list of numbers. Each number is the air pressure at the microphone, measured $f_s$ times per second, and speech models use $f_s = 16{,}000$ Hz. This section turns such a list into frequencies in three steps.

The discrete Fourier transform (DFT) rewrites a block of $N$ samples as a combination of $N$ sampled pure tones. Nothing is lost, and the block can be rebuilt exactly.
The fast Fourier transform (FFT) computes the DFT with about $\tfrac N2\log_2 N$ multiplications instead of $N^2$ .
The short-time Fourier transform (STFT) slides a short window along the signal and takes the DFT of each slice. Its squared magnitudes form the spectrogram, a matrix with one row per slice and one column per frequency. This is the first time in the chapter that sound becomes a sequence of vectors.

Two facts come up again and again, and the section explains both exactly. A tone that does not complete a whole number of cycles in the block smears across every frequency. And no window is sharp in both time and frequency at once, which is why speech systems settle on windows of about 25 ms.

Sound is a sum of vibrations, so change basis

A vector can be written in many coordinate systems. Recall from §0.10 that an orthonormal basis is a set of unit vectors $\mathbf{u}_1, \dots, \mathbf{u}_N$ at right angles to one another. The coordinate of a vector $\mathbf{x}$ along $\mathbf{u}_k$ is the inner product $c_k = \mathbf{u}_k^\top\mathbf{x}$ , and $\mathbf{x} = \sum_k c_k\mathbf{u}_k$ . The Fourier transform is that idea and nothing more. The block of samples is a vector $\mathbf{x} \in \R^N$ , and the new basis is a set of $N$ sampled pure tones.

Why that basis? In the usual basis each coordinate is one sample, and a pure tone is spread over all $N$ of them. In a basis of tones, a pure tone is a single coordinate and a chord is a few. Sound is made by things that vibrate, such as strings, air columns, and vocal folds. So most of its energy lands in a few coordinates of the tone basis, and those coordinates are easy to read.

The tones we use are complex, because complex tones turn every proof into a geometric series. Euler's formula, recalled from §5.5, says $e^{\mathrm{i}\alpha} = \cos\alpha + \mathrm{i}\sin\alpha$ , the point at angle $\alpha$ on the unit circle. Multiplying a complex number by $e^{\mathrm{i}\alpha}$ rotates it by $\alpha$ and leaves its length alone. A complex sinusoid at $k$ cycles per block is the sequence

b_k[n] = e^{2\pi\mathrm{i}kn/N} = \cos(2\pi kn/N) + \mathrm{i}\sin(2\pi kn/N), \qquad n = 0, 1, \dots, N-1 .

In plain words, $b_k$ is a point that walks around the unit circle, $k$ full turns in $N$ steps. A real cosine is the average of two such points turning in opposite directions, $\cos\theta = \tfrac12(e^{\mathrm{i}\theta} + e^{-\mathrm{i}\theta})$ . The clockwise one is said to have a negative frequency. That is all a negative frequency is, the mirror half of every real tone.

Complex vectors need one change to the inner product. It conjugates its second argument, $\langle\mathbf{x}, \mathbf{y}\rangle = \sum_n x[n]\,\overline{y[n]}$ , so that $\langle\mathbf{x}, \mathbf{x}\rangle = \sum_n \lvert x[n]\rvert^2$ is a squared length. The inner product of $\mathbf{x}$ with $b_k$ is then $\sum_n x[n]e^{-2\pi\mathrm{i}kn/N}$ . Each $b_k$ has squared length $N$ , not 1, so this inner product is $N$ times the coordinate. The $1/N$ comes back in the inverse below.

That sum has a vivid picture, the one 3Blue1Brown's visual introduction to the Fourier transform is built on. Each term $x[n]e^{-2\pi\mathrm{i}kn/N}$ places sample $n$ on a circle, rotated clockwise by the angle $2\pi kn/N$ . So you wind the signal around a circle at a trial rate of $k$ turns per block. If the signal oscillates at that same rate, its peaks always land on the same side and the sum is large. If not, the points spread around the circle and cancel. The DFT runs this test for every trial rate $k$ at once.

✏️ Two four-point DFTs by hand

Take $N = 4$ . Then $e^{-2\pi\mathrm{i}/4} = -\mathrm{i}$ , so the inner product with $b_k$ is $X[k] = \sum_{n=0}^{3}x[n](-\mathrm{i})^{kn}$ . The powers of $-\mathrm{i}$ cycle through $1, -\mathrm{i}, -1, \mathrm{i}$ .

First, $\mathbf{x} = (1, 0, -1, 0)$ , a cosine that completes one cycle in four samples. Only $n = 0$ and $n = 2$ contribute, so $X[k] = 1 - (-\mathrm{i})^{2k} = 1 - (-1)^k$ , and $X = (0, 2, 0, 2)$ . The energy sits at $k = 1$ , one turn per block counterclockwise, and at $k = 3$ . Bin 3 is the same as $k = -1$ , one turn clockwise. These are the two halves of one real cosine, $\cos(2\pi n/4) = \tfrac12 b_1[n] + \tfrac12 b_3[n]$ . Each half has coordinate $\tfrac12$ , and $X[k]$ is $N = 4$ times that, which is 2.

Second, $\mathbf{x} = (1, 1, 1, 1)$ , a constant. Then $X[0] = 4$ , and $X[k] = \sum_n(-\mathrm{i})^{kn} = 0$ for $k = 1, 2, 3$ , because four equally spaced points on the unit circle sum to zero. All the energy is at frequency zero. Engineers call that coefficient the DC term, after direct current.

The DFT measures every frequency at once

Here is the transform in general. It takes the inner product of the block with each of the $N$ complex sinusoids.

📐 Discrete Fourier transform

The DFT of a block $\mathbf{x} = (x[0], \dots, x[N-1]) \in \mathbb{C}^N$ is the vector $\mathbf{X} \in \mathbb{C}^N$ with

X[k] = \sum_{n=0}^{N-1} x[n]\,e^{-2\pi\mathrm{i}kn/N}, \qquad k = 0, 1, \dots, N-1 .

In matrix form $\mathbf{X} = \mathbf{F}_N\mathbf{x}$ . The DFT matrix $\mathbf{F}_N \in \mathbb{C}^{N\times N}$ has entries $(\mathbf{F}_N)_{kn} = e^{-2\pi\mathrm{i}kn/N}$ , with rows indexed by $k$ and columns by the sample $n$ , both from 0. The inverse DFT is

x[n] = \frac{1}{N}\sum_{k=0}^{N-1} X[k]\,e^{2\pi\mathrm{i}kn/N}, \qquad\text{that is,}\qquad \mathbf{x} = \tfrac{1}{N}\mathbf{F}_N^{*}\mathbf{X},

where $\mathbf{F}_N^{*}$ is the conjugate transpose. Each index $k$ is a bin. Here $N$ is the transform length, never a parameter count, and code calls it n_fft.

In plain words, $X[k]$ measures how much of the vibration " $k$ cycles per block" the block contains. It is a complex number. Its magnitude is the strength of that vibration. Its angle is the phase, where in its cycle the vibration starts. The inverse rebuilds the block by adding up all $N$ vibrations with those strengths and phases.

The DFT has a second reading that we need later, for zero padding and windows. It samples a smooth curve.

📌 The DFT samples the DTFT

§35.1 defined the spectrum of a sampled signal as $X_s(f) = \sum_{n} x[n]\,e^{-2\pi\mathrm{i}fnT_s}$ , where $T_s = 1/f_s$ is the time between samples. It is called the discrete-time Fourier transform (DTFT). It is defined at every real frequency $f$ and repeats with period $f_s$ . Treat a block as a signal that is zero outside $n = 0, \dots, N-1$ , and evaluate its DTFT at $f = kf_s/N$ ,

X_s\Big(\frac{kf_s}{N}\Big) = \sum_{n=0}^{N-1} x[n]\,e^{-2\pi\mathrm{i}(kf_s/N)\,n/f_s} = \sum_{n=0}^{N-1} x[n]\,e^{-2\pi\mathrm{i}kn/N} = X[k].

So the DFT of a block is the block's DTFT sampled at $N$ equally spaced frequencies, $f_s/N$ apart, covering one period. Whatever the curve does between those frequencies is invisible to the DFT.

The factor $1/N$ could sit on either side, and libraries let you choose. NumPy's default, norm="backward", puts it in the inverse, as above. norm="ortho" puts $1/\sqrt N$ on both sides. That makes $\mathbf{F}_N/\sqrt N$ unitary, a complex rotation that preserves lengths. norm="forward" puts $1/N$ in the forward transform. The three differ only by constants, but those constants change every absolute level you compute, so check which one a library uses.

The basis is orthogonal, so the inverse comes for free

The inverse looks the way it does because the sampled sinusoids are orthogonal, and each has squared length $\sum_n\lvert b_k[n]\rvert^2 = N$ . In an orthogonal basis, you undo "take inner products" by adding up the basis vectors with those weights, each divided by its squared length. That division is the $1/N$ .

∴ Orthogonality of the DFT basis and the inverse DFT

For integers $k, k'$ ,

\sum_{n=0}^{N-1} e^{2\pi\mathrm{i}(k - k')n/N} = \begin{cases} N & \text{if } k \equiv k' \pmod N, \\ 0 & \text{otherwise.}\end{cases}

Hence $\mathbf{F}_N^{*}\mathbf{F}_N = N\mathbf{I}$ , so $\mathbf{F}_N^{-1} = \tfrac1N\mathbf{F}_N^{*}$ , and the inverse formula recovers $\mathbf{x}$ exactly.

Proof. Let $r = e^{2\pi\mathrm{i}(k-k')/N}$ . If $k \equiv k' \pmod N$ , then $r = 1$ , every term is 1, and the sum is $N$ . Otherwise $r \neq 1$ and the sum is a geometric series,

\sum_{n=0}^{N-1} r^n = \frac{1 - r^N}{1 - r} = \frac{1 - e^{2\pi\mathrm{i}(k-k')}}{1 - r} = \frac{1 - 1}{1 - r} = 0,

because $k - k'$ is an integer. Entry $(k', k)$ of $\mathbf{F}_N^{*}\mathbf{F}_N$ is the inner product of columns $k$ and $k'$ of $\mathbf{F}_N$ , which is $\sum_n e^{2\pi\mathrm{i}(k'-k)n/N}$ . For $0 \le k, k' \le N - 1$ , congruence means equality, so the entry is $N$ when $k' = k$ and 0 otherwise. ∎

In plain words, $N$ points equally spaced around a circle sum to zero, unless they are all the same point. Two different trial frequencies wind against each other a whole number of times per block, so they cancel exactly.

In plain words, the energy is the same in both coordinate systems, up to the factor $N$ of the unnormalized convention. This is what lets us speak of "the energy at 1 kHz" and have the energies of all the bins add up to the energy of the signal. With norm="ortho" the factor disappears, because $\mathbf{F}_N/\sqrt N$ is a rotation. An interviewer who asks why the inverse DFT has a $1/N$ wants these two theorems.

The next cell builds $\mathbf{F}_4$ and reproduces the two hand computations. Then it checks orthogonality, the inverse, and Parseval for a random block of 64 samples.

Python · cell 1

Warm-up

The DFT as a matrix

Write dft_matrix(N), which returns the complex $N\times N$ matrix whose entry $(k, n)$ is $e^{-2\pi\mathrm{i}kn/N}$ . Then write dft(x), which applies that matrix along the last axis of an array of any shape. A batch of shape (B, N) comes back as (B, N), and so does any other leading shape. The result must equal np.fft.fft(x, axis=-1), but do not call np.fft or scipy.fft.

import numpy as np

def dft_matrix(N):
    raise NotImplementedError

def dft(x):
    raise NotImplementedError

Tests, hints, verified solutions, and AI help, with Pro at $7.99 a month.

Each bin is a frequency in hertz

The bin index $k$ counts cycles per block. A block of $N$ samples at rate $f_s$ lasts $N/f_s$ seconds, so $k$ cycles per block is a frequency in hertz,

f_k = \frac{k f_s}{N} \text{ Hz}, \qquad \Delta f = \frac{f_s}{N} \text{ between neighboring bins.}

Here is a real example. Whisper, OpenAI's speech recognizer (Radford et al. 2022), transforms blocks of $N = 400$ samples at $f_s = 16{,}000$ Hz, which is 25 ms of audio. Its bins are $\Delta f = 16{,}000/400 = 40$ Hz apart, so a 1 kHz tone sits exactly at bin $k = 1000/40 = 25$ .

The bins above $N/2$ are negative frequencies. For integer $n$ , $e^{-2\pi\mathrm{i}kn/N} = e^{-2\pi\mathrm{i}(k - N)n/N}$ , so bin $k$ and bin $k - N$ are the same basis vector. Bins $N/2 + 1, \dots, N - 1$ are therefore the frequencies $-(N/2 - 1)f_s/N, \dots, -f_s/N$ . This is the aliasing of §35.1 seen from the other side. Sampled tones whose frequencies differ by exactly $f_s$ produce identical samples. So a DFT can tell apart only the frequencies in a band of width $f_s$ , and the natural band is $[-f_s/2, f_s/2)$ . Its edge, $f_s/2$ , is the Nyquist frequency, the highest frequency the samples can represent.

For a real signal, the negative half carries no new information.

∴ Conjugate symmetry of the DFT of a real signal

If every $x[n]$ is real, then $X[N - k] = \overline{X[k]}$ for all $k$ . In particular $X[0]$ is real, and so is $X[N/2]$ when $N$ is even. The magnitudes are symmetric, $\lvert X[N-k]\rvert = \lvert X[k]\rvert$ , so the $\lfloor N/2\rfloor + 1$ bins $k = 0, \dots, \lfloor N/2\rfloor$ determine all the rest.

Proof. $X[N-k] = \sum_n x[n]e^{-2\pi\mathrm{i}(N-k)n/N} = \sum_n x[n]e^{2\pi\mathrm{i}kn/N}$ , since $e^{-2\pi\mathrm{i}n} = 1$ . For real $x[n]$ this is the complex conjugate of $\sum_n x[n]e^{-2\pi\mathrm{i}kn/N} = X[k]$ . Setting $k = 0$ , or $k = N/2$ for even $N$ , gives $X[k] = \overline{X[k]}$ , so those bins are real. ∎

This is why np.fft.rfft, the transform for real input, returns only $N/2 + 1$ bins for even $N$ . For Whisper's $N = 400$ that is 201 bins, from 0 Hz up to the Nyquist frequency of 8,000 Hz.

One consequence is easy to get wrong. Suppose you turn a one-sided spectrum into power and want the powers to add up to the signal's energy, as Parseval promises. Then each bin strictly between 0 and $N/2$ counts twice, once for itself and once for its negative twin. Bins 0 and $N/2$ count once.

The next cell puts a 1,000 Hz tone and a 1,010 Hz tone through Whisper's transform size. It asks how much of the energy lands in the peak bin.

Python · cell 2

The 1,000 Hz tone is perfect. All its one-sided energy sits in bin 25. Now move it by 10 Hz, a quarter of a bin. The peak bin keeps only 81 percent of the energy, and 16 bins sit within 30 dB of the peak. (A decibel, recall from §35.1, is $10\log_{10}$ of a power ratio, so 30 dB is a factor of 1,000 in power.) Nothing about the tone changed except that it no longer completes a whole number of cycles in the block. This smearing is called leakage, and the next part explains it exactly and then reduces it.

A tone between bins leaks into every bin

Every tone takes the same shape in the DFT, and that shape explains why the 1,010 Hz tone smeared. To see it, take the cleanest case, a complex tone $x[n] = e^{2\pi\mathrm{i}k_0n/N}$ . Its frequency $k_0$ is measured in bins and may be fractional. Its DFT is

X[k] = \sum_{n=0}^{N-1} e^{2\pi\mathrm{i}k_0n/N}e^{-2\pi\mathrm{i}kn/N} = \sum_{n=0}^{N-1}e^{-2\pi\mathrm{i}(k - k_0)n/N} = D_N(k - k_0),

where $D_N(\nu) = \sum_{n=0}^{N-1}e^{-2\pi\mathrm{i}\nu n/N}$ for any real $\nu$ , a frequency offset measured in bins. In plain words, the DFT of a tone always has the same shape, $D_N$ , centered on the tone's true frequency and read off at the whole-number bins.

∴ The Dirichlet kernel

For real $\nu$ that is not a multiple of $N$ ,

D_N(\nu) = \sum_{n=0}^{N-1}e^{-2\pi\mathrm{i}\nu n/N} = e^{-\mathrm{i}\pi\nu(N-1)/N}\,\frac{\sin(\pi\nu)}{\sin(\pi\nu/N)},

and $D_N(0) = N$ . Its magnitude has four features.

It is zero at every nonzero integer $\nu$ in $(-N, N)$ .
At $\nu = \tfrac12$ it equals $1/\sin(\pi/(2N)) \approx 2N/\pi$ , which is 3.92 dB below the peak.
Its largest sidelobe, the biggest bump outside the central peak, sits near $\nu \approx 1.43$ , about 13.26 dB below the peak.
For $\lvert\nu\rvert \ll N$ , $\lvert D_N(\nu)\rvert \approx N\lvert\sin(\pi\nu)\rvert/(\pi\lvert\nu\rvert)$ , so the sidelobes fall off only like $1/\lvert\nu\rvert$ , which is 6 dB each time the distance doubles.

∂ Proof of the Dirichlet kernel formula

With $r = e^{-2\pi\mathrm{i}\nu/N} \ne 1$ , the geometric series gives $D_N(\nu) = (1 - r^N)/(1 - r) = (1 - e^{-2\pi\mathrm{i}\nu})/(1 - e^{-2\pi\mathrm{i}\nu/N})$ . Use the identity $1 - e^{-2\mathrm{i}\theta} = e^{-\mathrm{i}\theta}(e^{\mathrm{i}\theta} - e^{-\mathrm{i}\theta}) = 2\mathrm{i}\,e^{-\mathrm{i}\theta}\sin\theta$ , with $\theta = \pi\nu$ on top and $\theta = \pi\nu/N$ below. The $2\mathrm{i}$ cancels, and the phases combine to $e^{-\mathrm{i}\pi\nu + \mathrm{i}\pi\nu/N} = e^{-\mathrm{i}\pi\nu(N-1)/N}$ .

The zeros come from $\sin(\pi\nu) = 0$ at the integers, while the denominator stays nonzero for $0 < \lvert\nu\rvert < N$ . At $\nu = \tfrac12$ the numerator is 1, so $\lvert D_N(\tfrac12)\rvert/N = 1/\big(N\sin(\pi/(2N))\big)$ . Since $N\sin(\pi/(2N)) \to \pi/2$ , the level is $-20\log_{10}\big(N\sin(\pi/(2N))\big) \to 20\log_{10}(2/\pi) = -3.92$ dB. The small- $\nu$ form uses $\sin(\pi\nu/N) \approx \pi\nu/N$ . The sidelobe level is computed numerically in the window cell below. ∎

In plain words, a tone that completes a whole number of cycles in the block lands on one bin and on a zero of every other bin. That is why the 1,000 Hz tone looked perfect. A tone that does not is read off between the zeros, so every bin picks up some of it, and the amount falls off only slowly with distance. This is spectral leakage.

Leakage is not a numerical error. The DFT treats the block as one period of a signal that repeats forever. A tone with a fractional number of cycles then has a jump where the end of the block meets its start, and a jump contains every frequency.

Windows trade a wider peak for much lower sidelobes

The fix is to remove the jump. Multiply the block by a window $w[n]$ , a curve that tapers smoothly to zero at both ends, before transforming. The same computation as above shows that the DFT of a windowed tone is the window's own spectrum shifted to $k_0$ ,

X[k] = \sum_n w[n]\,e^{2\pi\mathrm{i}k_0n/N}e^{-2\pi\mathrm{i}kn/N} = W(k - k_0), \qquad W(\nu) = \sum_{n=0}^{N-1} w[n]\,e^{-2\pi\mathrm{i}\nu n/N}.

In plain words, choosing a window means choosing the shape every tone is drawn with. The rectangular window $w[n] = 1$ , which is no window at all, gives $W = D_N$ . $W(\nu)$ is the window's DTFT with frequency measured in bins, and the DFT shows it only at the points $\nu = k - k_0$ for whole numbers $k$ .

The most common taper is the periodic Hann window, $w[n] = \tfrac12 - \tfrac12\cos(2\pi n/N)$ , one period of a raised cosine. Its spectrum is three Dirichlet kernels,

W_{\text{Hann}}(\nu) = \tfrac12 D_N(\nu) - \tfrac14 D_N(\nu - 1) - \tfrac14 D_N(\nu + 1).

The reason is that the cosine is a sum of two complex sinusoids one bin away, and multiplying by $e^{\pm 2\pi\mathrm{i}n/N}$ shifts the kernel by one bin. Away from the peak, the sidelobes of the three kernels nearly cancel. What is left falls off like $1/\lvert\nu\rvert^3$ , 18 dB each time the distance doubles, against 6 dB for the rectangle. The price is a main lobe, the central peak, twice as wide, with its first zero at $\pm2$ bins instead of $\pm1$ .

∂ Why the Hann sidelobes fall off as the cube of the distance

For $\lvert\nu\rvert \ll N$ , use the small- $\nu$ form $D_N(\nu) \approx e^{-\mathrm{i}\pi\nu}N\sin(\pi\nu)/(\pi\nu)$ for each of the three kernels. For the shifted kernels, the phase factors $e^{-\mathrm{i}\pi(\nu\pm1)}$ and the signs of $\sin(\pi(\nu\pm1))$ both flip, so the flips cancel. Then

W_{\text{Hann}}(\nu) \approx \frac{e^{-\mathrm{i}\pi\nu}N\sin(\pi\nu)}{\pi}\Big(\frac{1}{2\nu} - \frac{1}{4(\nu-1)} - \frac{1}{4(\nu+1)}\Big) = -\frac{D_N(\nu)}{2(\nu^2 - 1)} .

The extra factor $1/(\nu^2 - 1)$ turns the $1/\lvert\nu\rvert$ fall-off of $D_N$ into $1/\lvert\nu\rvert^3$ . It also cancels the zeros of $D_N$ at $\nu = \pm1$ , which is why the first zero of Hann moves out to $\pm2$ bins.

That trade holds for every window. A narrow main lobe separates two tones close in frequency. Low sidelobes let you see a quiet tone next to a loud one. No window has both, and five standard numbers describe where a window sits.

📐 Window figures of merit

For a window $w[n]$ of length $N$ with spectrum $W(\nu)$ , frequencies in bins,

the main-lobe half-width is the first $\nu > 0$ where $\lvert W(\nu)\rvert$ has a null, a zero or a minimum (1 bin for the rectangle, 2 for Hann),
the highest sidelobe is $\max_{\nu \text{ beyond the first null}} 20\log_{10}\lvert W(\nu)/W(0)\rvert$ , in dB,
the coherent gain is $W(0)/N = \tfrac1N\sum_n w[n]$ , the factor by which the window scales a tone's peak,
the equivalent noise bandwidth is $\mathrm{ENBW} = N\sum_n w[n]^2/\big(\sum_n w[n]\big)^2$ bins, the width of a rectangular filter with the same peak gain that would pass the same white-noise power,
the scalloping loss is $-20\log_{10}\lvert W(\tfrac12)/W(0)\rvert$ dB, how much a tone halfway between two bins drops.

The cell below measures all five for four standard windows. Besides the rectangle and Hann, it uses the Hamming window $0.54 - 0.46\cos(2\pi n/N)$ and the Blackman window $0.42 - 0.5\cos(2\pi n/N) + 0.08\cos(4\pi n/N)$ . It zero pads each window 64 times, which draws $\lvert W(\nu)\rvert$ on a grid of 1/64 bin (the box after the widget explains why that works).

Python · cell 3

📌 Window cheat sheet (periodic windows, N = 64)

window	first null	highest sidelobe	sidelobe fall-off	ENBW	coherent gain	scalloping loss
rectangular	1 bin	$-13.3$ dB	6 dB per octave	1.00 bins	1.00	3.92 dB
Hann	2 bins	$-31.5$ dB	18 dB per octave	1.50 bins	0.50	1.42 dB
Hamming (0.54, 0.46)	2 bins	$-42.4$ dB	6 dB per octave	1.36 bins	0.54	1.75 dB
Blackman (0.42, 0.5, 0.08)	3 bins	$-58.1$ dB	18 dB per octave	1.73 bins	0.42	1.10 dB

An octave is a doubling, here of the distance from the peak. A wider main lobe buys lower sidelobes. The Hamming window tunes its two coefficients to cancel the first sidelobe, which gives it a lower highest sidelobe ( $-42.7$ dB as $N$ grows). It keeps a small step at its ends, though, so its far sidelobes fall slowly. Hann reaches zero smoothly at both ends, which gives it the fast fall-off. Harris (1978) tabulates these and many more.

The coherent gain explains a puzzle that bites everyone once. The same tone reads 6 dB lower through a Hann window than through a rectangle, because $20\log_{10}0.5 \approx -6$ . Absolute levels therefore depend on the window. Libraries that report calibrated spectra divide by $\sum_n w[n]$ . SciPy's scipy.signal.stft does, and torch.stft does not.

In the widget, a complex tone sits at bin $k_0$ of a 64-sample block, and the slider moves it in steps of 0.05 bin. The thin curve is the window's spectrum $W(\nu - k_0)$ , and the dots are the DFT bins that sample it.

The last question has a definite answer, and interviewers ask it often.

Now the two sides of the trade, measured.

Python · cell 4

The quiet tone is a question of sidelobes. With the rectangular window, the loud tone's leakage at bin 46 is $-24.4$ dB, 16 dB above the quiet tone, which is buried. Hann leaks only $-54$ dB there and Blackman $-63$ dB, so both show the quiet tone at its true $-40$ dB.

The equal pair goes the other way, because it is a question of main-lobe width. The rectangle's narrow main lobe shows a clear 7.9 dB dip between the two tones. Hann barely separates them, with a 0.4 dB dip. Blackman's wide main lobe merges them into one bump, whose midpoint is 0.15 dB higher than the tones. (These numbers are for two cosines that start together. The depth of a dip also depends on the tones' relative phase.)

So the right window depends on the question. To find weak components next to strong ones, you want low sidelobes. To separate close components of similar strength, you want a narrow main lobe. When you need both, the only real fix is a longer window, which the last part of this section takes up. "Which window would you use, and why?" is a standard interview question, and this trade is the answer.

A parabola finds a frequency between bins

At Whisper's settings a bin is 40 Hz wide, but pitch trackers and tuners need accuracy of a few hertz. You do not need a longer FFT to get there. Near its peak, the log magnitude of a window's main lobe is close to a parabola. For an untruncated Gaussian window it is exactly a parabola, since the transform of a Gaussian is again a Gaussian, as Smith's Spectral Audio Signal Processing notes. So fit a parabola through the three log magnitudes around the peak and read off its top.

In plain words, if the left neighbor is louder than the right one, the true peak lies left of $k^\star$ . How far left depends on how lopsided the three values are, compared with how sharply they curve.

∂ Where the formula for p comes from

Write the parabola as $y(u) = a(u - p)^2 + b$ , with $u$ measured in bins from $k^\star$ . Plugging in $u = -1, 0, 1$ gives $\alpha = a(1 + p)^2 + b$ , $\beta = ap^2 + b$ , and $\gamma = a(1 - p)^2 + b$ . Subtracting, $\alpha - \gamma = 4ap$ and $\alpha - 2\beta + \gamma = 2a$ . Dividing the first by twice the second gives $p$ . Because $\beta$ is the largest of the three, $\lvert\alpha - \gamma\rvert \le \lvert\alpha - 2\beta + \gamma\rvert$ , so $\lvert p\rvert \le \tfrac12$ .

Research

Find a frequency between bins

Write estimate_frequency(x, fs, window). The input x is a real block of length $N$ = len(window) that holds one dominant sinusoid, away from 0 Hz and from the Nyquist frequency.

Window the block and take np.fft.rfft.
Find the peak bin $k^\star$ among bins 1 to $N/2 - 1$ .
Fit a parabola through the natural log magnitudes of bins $k^\star - 1$ , $k^\star$ , $k^\star + 1$ , and return the interpolated frequency in hertz.

Over a sweep of fractional frequencies, the tests demand an error below 1 percent of a bin with a Blackman window and below 2 percent with Hann.

import numpy as np

def estimate_frequency(x, fs, window):
    raise NotImplementedError

Tests, hints, verified solutions, and AI help, with Pro at $7.99 a month.

Convolution in time is multiplication in frequency

Before the STFT, we need two tools that every audio pipeline uses. The convolution theorem turns filtering into multiplication, and the FFT makes every transform cheap. This part takes the first.

A convolution slides one sequence along another, reversed, and sums the products at each shift. A convolutional layer (§0.8) computes the same sliding sum without the reversal. Convolution is also how any linear filter that does not change over time acts on a signal. Such a filter is described completely by its impulse response $h$ , its output when the input is a single 1 followed by zeros. For any other input $x$ , the output is the convolution $(x * h)[n] = \sum_m x[m]\,h[n - m]$ . Microphones, rooms, and equalizers all work this way.

The DFT turns convolution into elementwise multiplication, the most useful single fact in signal processing. Because the DFT works on blocks, it pairs exactly with a convolution that wraps around the end of the block.

Start with numbers. Take $\mathbf{x} = (1, 2, 3)$ and $\mathbf{h} = (1, 1)$ , a filter that adds each sample to the one before it. The ordinary convolution is $(1, 3, 5, 3)$ , four samples long. Now force the answer into three samples by wrapping the overhanging last sample, the 3, back onto the start. That gives $(1 + 3, 3, 5) = (4, 3, 5)$ . This wrapped version is the circular convolution.

Check the definition on the example. Pad $\mathbf{h}$ to $(1, 1, 0)$ . For $n = 0$ the sum is $x[0]h[0] + x[1]h[2] + x[2]h[1] = 1 + 0 + 3 = 4$ , the wrapped first sample. The theorem below says the DFT turns this wrapped sum into a product, one bin at a time. Bin 0 of a DFT is the plain sum of the samples, so at bin 0 the check is one line. The inputs sum to 6 and 2, and $6\times 2 = 12 = 4 + 3 + 5$ .

∂ Proof of the circular convolution theorem

Substitute the definition and swap the sums,

\sum_{n}\Big(\sum_m x[m]\,h[(n-m)\bmod N]\Big)e^{-2\pi\mathrm{i}kn/N} = \sum_m x[m]\,e^{-2\pi\mathrm{i}km/N}\sum_n h[(n-m)\bmod N]\,e^{-2\pi\mathrm{i}k(n-m)/N}.

Fix $m$ . As $n$ runs over $0, \dots, N-1$ , the index $j = (n - m)\bmod N$ also runs over $0, \dots, N-1$ , once each. Also $e^{-2\pi\mathrm{i}k(n-m)/N} = e^{-2\pi\mathrm{i}kj/N}$ , because the two exponents differ by a multiple of $2\pi\mathrm{i}$ . So the inner sum is $\sum_j h[j]e^{-2\pi\mathrm{i}kj/N} = H[k]$ , the same for every $m$ , and the outer sum is $X[k]$ . ∎

In plain words, convolving in time multiplies in frequency. A sinusoid passes through a filter with its shape unchanged. It only gets scaled, and shifted in phase, by the complex number $H[k]$ , because a delayed sinusoid is the same sinusoid times a phase.

Most of the time we want the ordinary, linear convolution. That is what np.convolve computes, and for inputs of lengths $N_x$ and $N_h$ it has length $N_x + N_h - 1$ . Zero padding gets it from the circular one. Pad both inputs with zeros to any length $N \ge N_x + N_h - 1$ , and nothing can wrap around. Here is why. Whenever $n - m$ is negative, the wrapped index is $(n - m) \bmod N = N + n - m \ge N - (N_x - 1) \ge N_h$ . That points at one of the zeros appended to $\mathbf{h}$ , so every wrapped term vanishes, and the circular sum equals the linear one.

So a linear convolution is three FFTs of length at least $N_x + N_h - 1$ , two forward and one inverse. That costs $O(N\log N)$ against $O(N_xN_h)$ for the direct sum, a large win once the kernel is long. This is how the state-space models of §21.3 apply a convolution kernel as long as the whole sequence. An interviewer who asks where the FFT speeds up a model wants this answer.

The cell below repeats the hand example, checks the theorem, and shows the wrap-around.

Python · cell 5

The last line shows the wrap-around directly. With $N = 8$ , the two samples of the linear result that fall past the end, at indices 8 and 9, are added onto the first two.

A room is a convolution

A room acts on sound as a filter. Its room impulse response (RIR) $h[n]$ is what a microphone in the room records when the source emits a single click. It holds a spike for the direct path, the sound that travels straight from the source to the microphone. Then come early reflections from the nearest walls, and then a dense tail that decays roughly exponentially. Sound waves add linearly, and the room does not change during an utterance. So take a dry source $x$ , recorded close to the mouth with no room in it. A distant microphone records $x * h$ plus noise. Ko et al. 2017 model far-field speech exactly this way.

That makes reverberation a standard data augmentation, a change to training inputs that keeps their labels. It is used for far-field speech recognition and for speaker embeddings, the fixed-length vectors that identify a voice (§35.6). Clean training speech is convolved with recorded or simulated RIRs, so the model learns to ignore the room. Two numbers describe a room's response.

Offices and living rooms have an $\mathrm{RT}_{60}$ of a few tenths of a second, and concert halls about two seconds. The DRR falls as the talker walks away from the microphone. It is positive close up and negative across a large room.

🔬 Measuring the reverberation time from a recorded response

A recorded RIR is noisy sample by sample, so $\mathrm{RT}_{60}$ is read from a smoothed curve. The backward energy integral of Schroeder (1965), $E[n] = \sum_{m \ge n} h[m]^2$ , is the energy still to arrive after sample $n$ . It decays smoothly even where $h[n]^2$ jumps around. The standard estimate, which the room-acoustics standard ISO 3382-1 calls $T_{20}$ , fits a least-squares line to $10\log_{10}E$ between $-5$ and $-25$ dB. It reports three times the time that line takes to fall 20 dB, since 20 dB is a third of 60. The cell below uses the simpler first-crossing times of $-5$ and $-25$ dB, which agree with the fit for a clean exponential decay.

Now the arithmetic at real scale. It uses one number from the FFT part that follows. A length- $L$ FFT, with $L$ a power of two, takes $\tfrac L2\log_2 L$ butterflies, small steps of one complex multiplication and two complex additions each.

✏️ Reverberation is a long convolution

Take 10 s of 16 kHz speech, $N_x = 160{,}000$ samples, and a 0.5 s RIR, $N_h = 8{,}000$ taps. The direct sum costs $N_xN_h = 1.28\times10^9$ multiply-adds, about $2.6\times10^9$ floating-point operations.

Through the FFT, the result has $N_x + N_h - 1 = 167{,}999$ samples, so one transform length $L = 2^{18} = 262{,}144$ suffices. Three FFTs of that length take $3\cdot\tfrac L2\log_2 L \approx 7.1\times10^6$ butterflies. At about ten floating-point operations per butterfly that is $7\times10^7$ operations, about 36 times less work. Transforms for real input (rfft) halve it again.

Augmentation then makes two adjustments that matter for training. First, it cuts the output to start at the RIR's direct-path peak and keeps $N_x$ samples. The reverberant copy is then not delayed, so every label, word timestamp, and frame alignment of the dry clip still holds. Second, it rescales the output to the dry clip's power, so reverberation does not also change loudness. The wav-reverberate tool of the Kaldi speech toolkit does both by default, through its --shift-output and --normalize-output options, and convolves in FFT blocks.

The next cell builds a synthetic RIR with $\mathrm{RT}_{60} = 0.4$ s. It is Gaussian noise under an exponential envelope that loses 60 dB of energy, a factor of 1,000 in amplitude, every 0.4 s. The cell measures the reverberation time back with Schroeder's integral, then reverberates 10 s of noise standing in for speech.

Python · cell 6

Schroeder's integral gives back 0.41 s for the designed 0.4 s. The DRR of about $-8$ dB says most of the energy arrives as reverberation, as it does for a distant talker. Your timings will differ, but the FFT handles ten times as much audio in less time than the direct sum takes for one second. After alignment, the reverberant copy lines up with the dry clip at lag 0.

Long signals are convolved in blocks

One FFT of the whole clip has to wait for the whole clip, and it needs $2^{18}$ points of memory per clip. A streaming system, or a data loader that reverberates thousands of hours, cuts the input into blocks instead.

Let the block length be $N_{\text{b}}$ . Block $j$ is $x_j[n] = x[jN_{\text{b}} + n]$ for $0 \le n < N_{\text{b}}$ , and zero elsewhere, so that $x[n] = \sum_j x_j[n - jN_{\text{b}}]$ . Convolution is linear and commutes with shifts, so

(x * h)[n] = \sum_j (x_j * h)[n - jN_{\text{b}}].

In plain words, convolve each block on its own and add the results back at the block's position. Each piece $x_j * h$ has $N_{\text{b}} + N_h - 1$ samples, so it spills $N_h - 1$ samples past its block into the next one. An FFT of any length $L \ge N_{\text{b}} + N_h - 1$ computes each piece exactly, and $H$ , the FFT of $h$ , is computed once and reused. The spilled tails overlap and are added into place, hence the name overlap-add. The price is latency, since a block produces nothing until it is full. Interviewers ask how to pick $N_{\text{b}}$ , and the box below gives the trade.

🔬 How to choose the block length, and overlap-save

Each block costs one forward and one inverse FFT and yields $N_{\text{b}} = L - N_h + 1$ new outputs. The work per output sample is therefore about $2\cdot\tfrac L2\log_2 L/(L - N_h + 1)$ butterflies. For the 0.5 s RIR this is 27 butterflies per sample at $L = 16{,}384$ and 20 at $L = 32{,}768$ . It bottoms out near 18 at $L = 65{,}536$ to $131{,}072$ and then rises slowly, so an $L$ a few times $N_h$ is the usual choice.

At $L = 32{,}768$ the 10 s clip takes 7 blocks, 14 transforms plus one for $H$ , about $3.7\times10^6$ butterflies in all. That is about half the 7.1 million of the single long FFT, for three reasons. Each transform is shorter, so its $\log_2 L$ factor is 15 instead of 18. The single FFT pads 167,999 samples up to 262,144. And it spends one of its three long transforms on $h$ , while the blocks transform $h$ once at the short length.

The twin method, overlap-save, overlaps the input blocks instead. It computes each block's circular convolution and throws away the $N_h - 1$ outputs that wrapped around.

The inverse STFT later in this section puts overlapping frames back together in the same way.

Interview

Reverberation augmentation by overlap-add

Write reverb_augment(x, rir, block=4096), the augmentation step of a far-field training pipeline. Both x, the clip, and rir, the room impulse response, are real 1-D arrays. The function does three things.

It computes the full linear convolution of x and rir by overlap-add. Cut x into consecutive blocks of block samples, where the last block may be shorter. Convolve each block with rir through np.fft.rfft and np.fft.irfft at one fixed length $L$ of at least block + len(rir) - 1, such as the smallest power of two that is. Transform rir only once. Add each block's result into place at the block's offset.
It aligns the output to the direct path. Let $d$ be the index of the largest $\lvert h[n]\rvert$ . Keep samples $d$ through $d$ + len(x) - 1, so the output has exactly len(x) samples and no delay.
It rescales the output so its RMS (root mean square) equals that of x. An all-zero clip returns zeros.

Do not call np.convolve, and do not take one FFT of the whole clip. The tests switch off np.convolve and watch the transform lengths. Interviewers follow up by asking how to choose the block size and what it does to latency.

import numpy as np

def reverb_augment(x, rir, block=4096):
    raise NotImplementedError

Tests, hints, verified solutions, and AI help, with Pro at $7.99 a month.

The FFT computes the DFT in N log N steps

Multiplying by $\mathbf{F}_N$ costs $N^2$ complex multiplications. For a 1,024-point transform that is over a million per frame, and a speech model transforms 100 frames for every second of audio it reads. The FFT gets the same answer with about $\tfrac N2\log_2 N$ multiplications, 5,120 for $N = 1024$ . The idea is divide and conquer, and it comes from one line of algebra.

Let $N$ be even. Split the sum that defines $X[k]$ into even samples $n = 2m$ and odd samples $n = 2m + 1$ , for $m = 0, \dots, N/2 - 1$ ,

X[k] = \sum_{m=0}^{N/2-1} x[2m]\,e^{-2\pi\mathrm{i}k(2m)/N} + \sum_{m=0}^{N/2-1} x[2m+1]\,e^{-2\pi\mathrm{i}k(2m+1)/N}.

Since $e^{-2\pi\mathrm{i}k(2m)/N} = e^{-2\pi\mathrm{i}km/(N/2)}$ , the first sum is the $N/2$ -point DFT of the even samples. Call it $E[k]$ . After pulling out the factor $e^{-2\pi\mathrm{i}k/N}$ , the second sum is the $N/2$ -point DFT of the odd samples, $O[k]$ . So

X[k] = E[k] + e^{-2\pi\mathrm{i}k/N}\,O[k].

Now the saving. The two half-size DFTs repeat with period $N/2$ in $k$ , so $E[k + N/2] = E[k]$ and $O[k + N/2] = O[k]$ . The factor in front only flips sign, $e^{-2\pi\mathrm{i}(k + N/2)/N} = e^{-\pi\mathrm{i}}e^{-2\pi\mathrm{i}k/N} = -e^{-2\pi\mathrm{i}k/N}$ . So for $k = 0, \dots, N/2 - 1$ ,

X[k] = E[k] + t_k, \qquad X[k + N/2] = E[k] - t_k, \qquad t_k = e^{-2\pi\mathrm{i}k/N}\,O[k].

This pair of equations is the butterfly. One complex multiplication, by the twiddle factor $e^{-2\pi\mathrm{i}k/N}$ , and two additions produce two outputs. Apply the same split to $E$ and $O$ , and again, until the blocks have length 1. The DFT of one sample is the sample itself. This is the radix-2 decimation-in-time algorithm of Cooley and Tukey (1965). "Radix 2" means it halves at each step, and "decimation in time" means it splits the samples rather than the bins.

∴ Cost of the radix-2 FFT

For $N = 2^p$ , the radix-2 FFT computes the DFT with $\tfrac N2\log_2 N$ butterflies. That is at most $\tfrac N2\log_2 N$ complex multiplications and $N\log_2 N$ complex additions, which is $\Theta(N\log N)$ .

Proof. Let $C(N)$ be the number of butterflies. A length- $N$ transform does two length- $N/2$ transforms and then $N/2$ butterflies, so $C(N) = 2C(N/2) + N/2$ with $C(1) = 0$ . Divide by $N$ to get $C(N)/N = C(N/2)/(N/2) + \tfrac12$ . Each halving adds $\tfrac12$ , and there are $p = \log_2 N$ halvings from $N$ down to 1, so $C(N)/N = p/2$ and $C(N) = \tfrac N2\log_2 N$ . Each butterfly does one multiplication and two additions. ∎

For $N = 1024$ , that is $512\cdot 10 = 5{,}120$ multiplications against $1{,}048{,}576$ , a saving of about 205 times. The ratio, $2N/\log_2 N$ , keeps growing with $N$ . A few twiddles are trivial, such as $1$ or $-\mathrm{i}$ , so real implementations do slightly fewer.

Whisper's $N = 400$ is not a power of two, and that is fine. The same split works for any factor. Since $400 = 2^4\cdot 5^2$ , a mixed-radix FFT splits by 2 four times and by 5 twice. Libraries such as pocketfft, which sits behind np.fft, and NVIDIA's cuFFT handle any length this way. Powers of two are still the fastest, which is one reason music front ends often choose 1,024 or 2,048.

The cell below implements the recursion in a few lines, checks it against NumPy, and times three ways of computing a 1,024-point DFT.

Python · cell 7

Your timings will differ, and they teach a second lesson. The Python recursion makes $2N - 1$ function calls, and the interpreter's overhead on each call costs far more than a multiplication. So at $N = 1024$ it can lose to the matrix product, which runs in compiled linear-algebra code. np.fft is both compiled and $O(N\log N)$ , and it beats both. Operation counts predict speed only when the constant factors are comparable. That theme returns in the GPU chapter's roofline model and in every chapter on kernels and hardware.

Interview

A radix-2 FFT from scratch

Write fft_radix2(x) for a 1-D array whose length is a power of two (1, 2, 4, ...). It returns the DFT as a complex array of the same length, computed recursively or iteratively. Raise ValueError for any other length, including 0. Do not use np.fft, which the tests switch off while your function runs. The tests also count the exponentials, sines, and cosines you evaluate, so an $N\times N$ DFT matrix fails. This is a classic whiteboard question. The follow-ups are always the cost recurrence and why $X[k + N/2]$ needs no extra multiplications.

import numpy as np

def fft_radix2(x):
    raise NotImplementedError

Tests, hints, verified solutions, and AI help, with Pro at $7.99 a month.

The STFT slides a window along the signal

A DFT of a whole recording would say which frequencies occur somewhere in it, but not when, and speech is all about when. So we cut the signal into short overlapping slices called frames, window each one, and transform each one. The hop is the number of samples from the start of one frame to the start of the next. Stacking the frames' spectra gives a matrix with one row per frame, a picture of frequency content over time.

A tiny count first. Take 1 s of 16 kHz audio, 16,000 samples, with 400-sample frames that start every 160 samples. Without padding, the last frame must end inside the signal, so the frames start at $0, 160, \dots, 15{,}520$ . That is $1 + \lfloor(16{,}000 - 400)/160\rfloor = 98$ frames. The general rule is in the definition.

📐 Short-time Fourier transform

Given a signal $x[n]$ , an analysis window $w[n]$ of length $N_w$ , a hop $R$ , and an FFT length $N \ge N_w$ , the STFT is

X[t, k] = \sum_{n=0}^{N_w-1} x[tR + n]\,w[n]\,e^{-2\pi\mathrm{i}kn/N}, \qquad t = 0, 1, \dots, T-1, \quad k = 0, \dots, N/2 .

The frames $t$ are the sequence positions and the bins $k$ are the features, so $\mathbf{X} \in \mathbb{C}^{T\times(N/2+1)}$ for a real signal. The power spectrogram is $\lvert X[t,k]\rvert^2$ . For a signal of $n_{\text{samples}}$ samples, the number of frames is

T = 1 + \left\lfloor\frac{n_{\text{samples}} - N_w}{R}\right\rfloor \ \text{(no padding)}, \qquad T = 1 + \left\lfloor\frac{n_{\text{samples}}}{R}\right\rfloor \ \text{(centered, } N \text{ even)}.

Centered means the signal is first padded with $\lfloor N_w/2\rfloor$ samples on each side, with $N_w = N$ , so that frame $t$ is centered on sample $tR$ . For odd $N$ the centered count is $1 + \lfloor(n_{\text{samples}} - 1)/R\rfloor$ .

In plain words, slide a window along the signal in steps of $R$ samples, and take the DFT of what you see each time. Each row of $\mathbf{X}$ is one frame's spectrum, and frame $t$ describes the audio around time $tR/f_s$ .

The centered count follows from the uncentered one. For even $N$ , padding adds $2\lfloor N/2\rfloor = N$ samples, and $1 + \lfloor(n_{\text{samples}} + N - N)/R\rfloor = 1 + \lfloor n_{\text{samples}}/R\rfloor$ . In the 1 s example, centering gives $1 + 16{,}000/160 = 101$ frames instead of 98.

Centering is the default in both torch.stft and librosa.stft, but they pad differently. PyTorch mirrors the signal at its edges (pad_mode="reflect", so the padding before $x[0]$ is $x[N/2], \dots, x[1]$ ). librosa has padded with zeros by default since version 0.9. The first and last frames therefore differ between the two libraries, which matters when you port a model.

✏️ Whisper's spectrogram, counted

Whisper reads 30 s of 16 kHz audio, so $n_{\text{samples}} = 480{,}000$ . It uses a 400-sample periodic Hann window (25 ms), a hop of $R = 160$ samples (10 ms), and the centered, reflect-padded framing of torch.stft. That gives $T = 1 + \lfloor 480{,}000/160\rfloor = 3{,}001$ frames of $400/2 + 1 = 201$ bins, 40 Hz apart.

Whisper's audio.py then drops the last frame (stft[..., :-1]), leaving exactly 3,000 frames, 100 per second. They become the 3,000 log-mel frames of §35.3. Without centering it would have been $1 + \lfloor 479{,}600/160\rfloor = 2{,}998$ frames.

Off-by-one errors in frame counts are among the most common bugs in audio pipelines. The answer "3,000 or 3,001, depending on centering and Whisper's trim" is the kind of precision interviewers listen for.

The STFT is also a layer you already know. Fix a bin $k$ and define the complex filter $g_k[n] = w[n]e^{-2\pi\mathrm{i}kn/N}$ of length $N_w$ . Then $X[t, k] = \sum_n x[tR + n]\,g_k[n]$ , a sliding dot product evaluated every $R$ samples. That is a 1-D convolution layer in the deep-learning sense of §0.8, which slides its kernel without flipping it. Its kernel size is $N_w$ , its stride is $R$ , and it has no bias. It has $N/2 + 1$ complex output channels, or $N + 2$ real ones for the real and imaginary parts. The layer's output-size formula with no padding reproduces the uncentered frame count.

Each filter $g_k$ is a band-pass filter, one that passes a narrow band of frequencies and blocks the rest. A tone at bin $\nu$ comes out of it with magnitude $\lvert W(\nu - k)\rvert$ , the window's spectrum centered on bin $k$ . So the STFT is a bank of $N/2 + 1$ evenly spaced band-pass filters, with outputs taken every $R$ samples. §35.4 replaces this whole front end with a stack of seven learned strided convolutions over the raw waveform, which learn their own filters in place of these fixed ones. §35.3 meets front ends that learn filterbanks with only a few parameters per filter.

The next cell builds the STFT from a strided view of the signal and checks both frame-count formulas on 30 s of audio.

Python · cell 8

Count what the STFT produces. Whisper's frames hold 201 complex bins every 160 samples, about 2.5 real numbers per input sample. The complex STFT is redundant, and that redundancy is what makes inversion stable. The power spectrogram keeps 201 real numbers per 160 samples, and the phase is gone.

Interview

An STFT with the framing conventions right

Write stft(x, n_fft, hop, window, center=True) for a real 1-D signal, where window is an array of length n_fft and n_fft is even. With center=True, first reflect-pad n_fft // 2 samples on each side, as torch.stft does. Return the complex array of shape (T, n_fft // 2 + 1), frames as rows, with $T$ given by the formulas above. Avoid a Python loop over frames, and use sliding_window_view or fancy indexing instead. The reference in the tests uses an explicit loop, so you can compare.

import numpy as np

def stft(x, n_fft, hop, window, center=True):
    raise NotImplementedError

Tests, hints, verified solutions, and AI help, with Pro at $7.99 a month.

Overlap-add inverts the STFT exactly

Each frame's inverse DFT gives back the windowed slice $w[n]\,x[tR + n]$ . The slices overlap, so every sample appears in several of them, each time multiplied by a different part of the window. The cleanest way to undo this has three steps. Multiply each slice by the window once more. Add the slices into place, which is overlap-add again. Then divide each sample by the total weight the window gave it.

∴ Perfect reconstruction by weighted overlap-add

Let $y_t[n]$ , $n = 0, \dots, N_w - 1$ , be the inverse DFT of frame $t$ of an STFT with $N = N_w$ , and define

\hat x[m] = \frac{\sum_t w[m - tR]\,y_t[m - tR]}{\sum_t w[m - tR]^2},

where both sums run over the frames that contain sample $m$ .

If the STFT came from a signal $x$ , then $\hat x[m] = x[m]$ at every $m$ where the denominator is positive, for any hop $R$ .
For any array $Y$ , such as a modified STFT that may come from no signal at all, $\hat x$ is the signal whose STFT is closest to $Y$ in squared error, $\hat x = \arg\min_x\sum_{t}\sum_{k=0}^{N-1}\lvert X[t,k] - Y[t,k]\rvert^2$ , where $X$ is the STFT of $x$ .

For a real signal, a one-sided array is first extended to all $N$ bins by conjugate symmetry, which is what irfft assumes, and then each $y_t$ is real.

∂ Proof of perfect reconstruction and of the least-squares property

If $Y$ is the STFT of $x$ , then $y_t[n] = w[n]\,x[tR + n]$ . The numerator becomes $\sum_t w[m - tR]^2\,x[m]$ , and dividing by the denominator leaves $x[m]$ .

For the general claim, apply Parseval to each frame, $\sum_k\lvert X[t,k] - Y[t,k]\rvert^2 = N\sum_n\lvert w[n]x[tR+n] - y_t[n]\rvert^2$ . The objective is then $N\sum_t\sum_n\lvert w[n]x[tR + n] - y_t[n]\rvert^2$ , a sum of squares in which sample $x[m]$ appears once in each frame that contains it, with coefficient $w[m - tR]$ . Setting the derivative with respect to $x[m]$ to zero gives $\sum_t w[m - tR]\big(w[m - tR]\,x[m] - y_t[m - tR]\big) = 0$ , which is the formula. ∎

In plain words, applying the window a second time and dividing by the sum of squared windows undoes the analysis exactly, whatever the hop. The only requirement is that every sample is seen through a nonzero part of some window. When the spectrogram has been edited, as in speech enhancement, the same formula gives the best signal available.

Python · cell 9

All three hops reconstruct to about $10^{-15}$ , which is machine precision, even though only hop 100 has a constant $\sum_t w^2$ .

Core

Invert the STFT

Write istft(X, n_fft, hop, window, length). The input X is a complex array of shape (T, n_fft // 2 + 1) from a centered STFT, with reflect padding of n_fft // 2 as in Exercise 35.2e. n_fft is even, and the hop is at most n_fft // 2, so the frames cover every sample.

Invert each frame with np.fft.irfft and apply the synthesis window.
Overlap-add the frames, and divide by the sum of squared windows wherever it is positive.
Remove the n_fft // 2 samples of centering and return a real signal of exactly length samples.

One test uses a modified STFT that no signal produces. There only the recipe above matches the reference. Leaving out the synthesis window and dividing by the sum of window does not.

import numpy as np

def istft(X, n_fft, hop, window, length):
    raise NotImplementedError

Tests, hints, verified solutions, and AI help, with Pro at $7.99 a month.

Recovering a signal when only the magnitude survives

Models almost never keep the phase. Recognizers read the power spectrogram $\lvert X[t,k]\rvert^2$ . Text-to-speech systems predict magnitudes, as mel spectrograms, because phase is erratic and hard to predict. Going back to a waveform then means inventing a phase. Magnitudes alone do not determine the signal, since flipping its sign changes no magnitude at all. But the overlap between frames constrains the phase a great deal, because neighboring frames see the same samples.

Griffin and Lim (1984) turned that constraint into an algorithm. Start from the target magnitudes $A[t,k]$ and any phase. Then repeat two steps.

Build the least-squares signal $x_i$ for the current complex array, with the overlap-add formula above.
Take the STFT of $x_i$ , keep its phase, and replace its magnitude by $A$ . Call the result $Y_i$ , and feed it back into step 1.

∂ Proof that the error never increases

For any complex array $Z$ , the array with magnitude $A$ that is closest to $Z$ in squared error keeps $Z$ 's phase, and its distance is $\sum\lvert\,\lvert Z\rvert - A\rvert^2$ . So $d_i = \lVert X_i - Y_i\rVert^2$ , with $Y_i$ the magnitude- $A$ array built from $X_i$ 's phase.

Step one makes $x_{i+1}$ the signal whose STFT is closest to $Y_i$ , so $\lVert X_{i+1} - Y_i\rVert^2 \le \lVert X_i - Y_i\rVert^2 = d_i$ . Step two picks $Y_{i+1}$ , the closest magnitude- $A$ array to $X_{i+1}$ , so $d_{i+1} = \lVert X_{i+1} - Y_{i+1}\rVert^2 \le \lVert X_{i+1} - Y_i\rVert^2$ . Chain the two inequalities. ∎

The proof is exact for the uncentered STFT. The centered one in the cell below behaves the same way, and the cell checks that the error fell at every iteration.

The theorem guarantees steady progress, not the best possible phase. In practice Griffin-Lim stalls at a phase that sounds metallic. The cell below runs it on a half-second chirp, a tone whose pitch rises from 300 Hz to 1,800 Hz.

Python · cell 10

The spectral convergence, the relative error of the magnitudes, falls from 0.61 to 0.08 in 100 iterations, so the magnitudes nearly match. Yet the waveform's signal-to-noise ratio against the original (the SNR of §35.1) is negative. That shows magnitudes alone do not pin down the waveform, and a different phase is not in itself a defect. The defect is what remains, the 8 percent magnitude error at the end, which you hear as a metallic, phasey sound.

Neural vocoders, networks that learn to generate waveforms from mel spectrograms, replaced Griffin-Lim in text-to-speech because they produce plausible phase without that sound (§37.2). §37.1 starts from the mel targets they consume. An interviewer who asks "can you invert a magnitude spectrogram?" wants both halves, Griffin-Lim and why vocoders replaced it.

No window is sharp in both time and frequency

Every choice so far left one number open, the window length $N_w$ . A long window gives fine frequency resolution, with bins $f_s/N_w$ apart and a narrow main lobe, but it smears anything that changes during the window. A short window pins events down in time but blurs frequency.

Here are numbers. At 16 kHz, a 25 ms window (400 samples) has bins 40 Hz apart. A 10 ms window has bins 100 Hz apart, too coarse to separate the harmonics of a low voice, but it can place a click within 10 ms. Bin spacing times duration is $(f_s/N_w)(N_w/f_s) = 1$ for every length. The theorem below says that this trade is a law, not a defect of the DFT.

To state it we need two facts about continuous time. The continuous Fourier transform from §35.1 is $X(f) = \int x(t)e^{-2\pi\mathrm{i}ft}\,\mathrm{d}t$ , and the DFT is its sampled, finite version. In this part $t$ is continuous time in seconds and $f$ is frequency in hertz. Plancherel's theorem, the continuous form of Parseval, says $\int\lvert X(f)\rvert^2\,\mathrm{d}f = \int\lvert x(t)\rvert^2\,\mathrm{d}t$ .

📐 Time spread and frequency spread

Let $x(t)$ have finite energy $\lVert x\rVert^2 = \int\lvert x(t)\rvert^2\,\mathrm{d}t$ . Treat $\lvert x(t)\rvert^2/\lVert x\rVert^2$ and $\lvert X(f)\rvert^2/\lVert x\rVert^2$ as probability densities, which both integrate to 1 by Plancherel. The time spread $\sigma_t$ and the frequency spread $\sigma_f$ are their standard deviations,

\sigma_t^2 = \frac{\int(t - \mu_t)^2\lvert x(t)\rvert^2\,\mathrm{d}t}{\lVert x\rVert^2}, \qquad \sigma_f^2 = \frac{\int(f - \mu_f)^2\lvert X(f)\rvert^2\,\mathrm{d}f}{\lVert x\rVert^2},

where $\mu_t$ and $\mu_f$ are the corresponding means.

For a sense of scale, take Whisper's 25 ms Hann window. Its tapered ends carry little energy, so its time spread is only about 3.54 ms, half that of a rectangle of the same length, as a cell below measures. Its frequency spread is about 23.1 Hz. The theorem below says that no window with a time spread of 3.54 ms can have a frequency spread below $1/(4\pi\times 3.54\ \text{ms}) \approx 22.5$ Hz, so Hann sits close to the limit.

∂ Proof of the uncertainty inequality

Assume $x$ is smooth and decays fast enough that $t\lvert x(t)\rvert^2 \to 0$ as $\lvert t\rvert\to\infty$ . The general case follows by approximation. Two reductions come first. Replacing $x(t)$ by $x(t + \mu_t)e^{-2\pi\mathrm{i}\mu_f t}$ shifts the time density by $\mu_t$ and the frequency density by $\mu_f$ without changing their shapes, so we may assume $\mu_t = \mu_f = 0$ . Scaling $x$ changes neither spread, so we may assume $\lVert x\rVert = 1$ .

Next, the derivative rule. The transform of $x'(t)$ is $2\pi\mathrm{i}f\,X(f)$ , by integrating by parts, $\int x'(t)e^{-2\pi\mathrm{i}ft}\,\mathrm{d}t = \big[x\,e^{-2\pi\mathrm{i}ft}\big]_{-\infty}^{\infty} + 2\pi\mathrm{i}f\int x(t)e^{-2\pi\mathrm{i}ft}\,\mathrm{d}t$ , where the boundary term vanishes. With Plancherel this gives

\int\lvert x'(t)\rvert^2\,\mathrm{d}t = \int\lvert 2\pi\mathrm{i}f X(f)\rvert^2\,\mathrm{d}f = 4\pi^2\sigma_f^2 .

Now write the unit energy as an integral and integrate by parts, using $\tfrac{\mathrm{d}}{\mathrm{d}t}\lvert x\rvert^2 = \overline{x}\,x' + \overline{x'}\,x = 2\operatorname{Re}(\overline{x}\,x')$ ,

1 = \int\lvert x(t)\rvert^2\,\mathrm{d}t = \Big[t\lvert x(t)\rvert^2\Big]_{-\infty}^{\infty} - \int t\,\frac{\mathrm{d}}{\mathrm{d}t}\lvert x(t)\rvert^2\,\mathrm{d}t = -2\int t\operatorname{Re}\big(\overline{x(t)}\,x'(t)\big)\,\mathrm{d}t .

Bound the right side by its absolute value. Then apply the Cauchy-Schwarz inequality, $\int\lvert fg\rvert \le (\int\lvert f\rvert^2)^{1/2}(\int\lvert g\rvert^2)^{1/2}$ , to the functions $t\,x(t)$ and $x'(t)$ ,

1 \le 2\int\lvert t\,x(t)\rvert\,\lvert x'(t)\rvert\,\mathrm{d}t \le 2\Big(\int t^2\lvert x(t)\rvert^2\,\mathrm{d}t\Big)^{1/2}\Big(\int\lvert x'(t)\rvert^2\,\mathrm{d}t\Big)^{1/2} = 2\,\sigma_t\cdot 2\pi\sigma_f .

Hence $\sigma_t\sigma_f \ge 1/(4\pi)$ . Equality in Cauchy-Schwarz needs $x'(t) = -\lambda\,t\,x(t)$ for a constant $\lambda$ . Equality in the first step needs $\operatorname{Re}(\overline{x}\,x')\,t$ to have one sign, which forces $\lambda$ to be real and positive. The solution of $x' = -\lambda t x$ is $x(t) = c\,e^{-\lambda t^2/2}$ , a Gaussian, and undoing the two reductions gives the family in the theorem. ∎

In plain words, a pulse cannot be both short and pure in pitch. Squeeze a pulse to half its duration and its spectrum doubles in width. A window is a pulse, so whatever window you choose, the product of its time spread and its frequency spread is at least $1/(4\pi) \approx 0.0796$ . Only the Gaussian reaches the bound.

Sampled windows of a few hundred samples obey the same bound. The next cell measures how close four windows of Whisper's length come to it. It computes the spreads from $w[n]^2$ in samples and from $\lvert W\rvert^2$ in cycles per sample, so their product has no units.

Python · cell 11

The Gaussian sits on the bound to four decimals. Blackman is within half a percent and Hann within 3 percent. The rectangle is 19 times worse, because its sharp edges spread its spectrum. (In continuous time its $\sigma_f$ would be infinite, and here the sampling band caps it.) The Hann row gives the 3.54 ms and 23.1 Hz quoted above, and the rectangle row the 7.2 ms of a window with no taper.

The widget computes a spectrogram of 0.6 s of synthetic audio at 8 kHz while you drag the window length. Its three presets are two close tones followed by two close clicks, a rising chirp, and a vowel whose pitch glides.

Speech uses 25 ms windows for three reasons

So the window length is a choice of which structure you want to see. Speech front ends settle on a standard answer.

There are three reasons for those numbers.

Stationarity. The vocal tract changes shape from sound to sound, but speech scientists treat it as roughly fixed over 20 to 30 ms. A frame of that length sees one steady spectrum. Much longer frames blur the transitions between phones, the individual speech sounds.
Harmonics. A voice with a 100 Hz pitch has harmonics 100 Hz apart, which is 2.5 bins at 40 Hz per bin. Hann's 6 dB main-lobe width, the width of its peak at 6 dB below the top, is 2 bins. The harmonics are farther apart than that, so neighboring ones show a dip between them and are resolved. A higher voice has wider spacing and is easier.
Rate. A 10 ms hop gives 100 frames per second, several frames per phone. That is enough for recognition and keeps sequences short. The Audio Spectrogram Transformer (Gong et al. 2021) and the speaker-embedding network ECAPA-TDNN (Desplanques et al. 2020) use the same 25 ms window and 10 ms hop, the first with a Hamming window.

Music is different. Notes last longer and their pitches sit closer together. A semitone near 110 Hz is about 6.5 Hz. So music analysis typically uses 2,048-sample windows, 46 ms at 44.1 kHz or 93 ms at librosa's default rate of 22,050 Hz. Even so, a 2,048-point bin is 10.8 Hz wide at 22,050 Hz, wider than that semitone, which is one reason music also uses the constant-Q transform below. Percussive onsets want the opposite, since a 2,048-sample window at 22,050 Hz smears a drum hit over 93 ms. An interviewer who asks "what window would you use for music?" wants this contrast with speech.

The same STFT in PyTorch

torch.stft is what Whisper and most training pipelines call. It returns frames on the last axis, (batch, bins, frames), the transpose of our (T, K). It uses no window at all unless you pass one.

🔥 In PyTorchfor a machine with PyTorch

The libraries agree on the mathematics and disagree on almost every default. Check these whenever you move a model between them.

	`torch.stft`	`librosa.stft`	`scipy.signal.stft`	Whisper's `audio.py`
output layout	`(..., K, T)`	`(..., K, T)`	`(K, T)`, plus arrays of the frequencies and times	`(n_mels, 3000)` after its mel step
default window	none (all ones)	periodic Hann	periodic Hann	`torch.hann_window(400)`
default hop	`n_fft // 4`	`win_length // 4`	half the segment	160
centering	`center=True`, reflect	`center=True`, zeros (since 0.9)	zero padding at both ends	torch defaults, then drops the last frame
scaling	none	none	divides by the window sum	none

The front end is cheap at real scale

The STFT costs little next to the model that reads it. One hour of 16 kHz audio at a 10 ms hop is 360,000 frames. With a 512-point FFT each frame costs $\tfrac{512}{2}\log_2 512 = 2{,}304$ butterflies, about $8.3\times10^8$ for the hour. At about ten floating-point operations per butterfly, that is roughly $10^{10}$ operations.

A Transformer encoder costs about 2 floating-point operations per parameter per frame (§5.6). Even a small encoder of 100 million parameters, reading 50 frames per second, spends $2\cdot10^8\cdot 50\cdot 3600 \approx 3.6\times10^{13}$ operations on the same hour. That is thousands of times more. The front end is never the bottleneck, which is why it can afford to be fixed and exact.

Here are the representations this section offers, side by side.

representation	resolution	what it keeps	where it is used
waveform	exact in time, none in frequency	everything	self-supervised speech encoders (§35.4), neural codecs (§37.3)
one DFT of the whole signal	exact in frequency, none in time	everything (with phase)	tuning, measuring a steady tone, FFT convolution
complex STFT	$f_s/N_w$ in frequency, about $N_w/f_s$ in time, fixed	everything, redundantly	source separation, enhancement, invertible pipelines
power spectrogram	the same	magnitudes only, phase lost	input to mel features (§35.3)
constant-Q or wavelet transform	finer frequency at low notes, finer time at high	depends on the variant	music transcription, pitch analysis
learned filterbank (strided convolution)	learned	whatever the loss rewards	raw-waveform encoders, learnable front ends

⚠️ Five ways to get a spectrogram subtly wrong

A symmetric window. np.hanning(N) and scipy.signal.windows.hann(N, sym=True) divide by $N - 1$ , not $N$ . Such a window is not exactly COLA at hop $N/2$ and does not match torch.hann_window, which is periodic. Use scipy.signal.get_window("hann", N) or build the periodic formula yourself.
No window in PyTorch. torch.stft(x, 400, 160) without window= uses a rectangle and leaks badly. PyTorch prints a warning, which is easy to miss inside a data loader.
Padding mismatch. Torch reflects, librosa pads zeros, and SciPy pads zeros and scales. The first and last frames differ, and so do the frame counts if you forget centering.
Layout. Every library puts frames last, while sequence models want them first. A transposed spectrogram fed to a Transformer trains without errors and learns nothing sensible about time.
One-sided power. When converting rfft bins to power that must add up to the signal energy, double the bins strictly between 0 and $N/2$ . Forgetting this halves every level except DC and Nyquist.

🧭 What to remember

The DFT is a change of basis onto $N$ sampled complex sinusoids. Their orthogonality, a geometric series that sums to zero, gives the inverse $\mathbf{F}_N^{-1} = \tfrac1N\mathbf{F}_N^{*}$ and Parseval's energy identity. Bin $k$ is $kf_s/N$ Hz, and a real signal needs only the $N/2 + 1$ bins up to the Nyquist frequency (201 for $N = 400$ ).
A tone that does not fit the block leaks into every bin through the Dirichlet kernel, whose sidelobes peak at $-13.3$ dB. Windows trade main-lobe width for sidelobe level, and zero padding only interpolates the spectrum.
Convolution in time is multiplication in frequency, exactly for circular convolution and for linear convolution after zero padding to $N_x + N_h - 1$ . Reverberating 10 s of speech with a 0.5 s room impulse response is about 36 times cheaper by FFT. Overlap-add does it in fixed blocks for streaming, and augmentation aligns the result to the direct-path peak and restores the clip's power.
The radix-2 FFT splits even and odd samples and recombines them with $\tfrac N2\log_2 N$ butterflies, so it costs $\Theta(N\log N)$ . Mixed-radix FFTs handle lengths such as 400.
The STFT windows overlapping frames and transforms each one, giving a $T\times(N/2 + 1)$ matrix with frames as rows. Centered framing gives $T = 1 + \lfloor n_{\text{samples}}/R\rfloor$ , which is 3,001 frames for 30 s at hop 160, and Whisper keeps 3,000. Weighted overlap-add divided by $\sum_t w^2$ inverts it exactly for any hop that leaves no sample outside every window. It is also the least-squares inverse of a modified STFT, which Griffin-Lim iterates when the phase is missing.
No window beats $\sigma_t\sigma_f \ge 1/(4\pi)$ , and only Gaussians reach it. Speech uses about 25 ms windows and 10 ms hops to balance a steady vocal tract against resolved harmonics.
Next, §35.3 starts from these 201-bin power spectra, asks why nobody feeds them to a model directly, and compresses each frame the way the ear does, with mel pooling and a logarithm.

Julius O. Smith III. Mathematics of the Discrete Fourier Transform (DFT), with Audio Applications. A free online book that carefully derives everything in the first half of this section, with audio in mind.
Julius O. Smith III. Spectral Audio Signal Processing. The companion book, on windows, the STFT, and overlap-add, including the chapters on spectrum analysis windows, overlap-add STFT processing, and quadratic interpolation of spectral peaks.
Harris (1978). On the Use of Windows for Harmonic Analysis with the Discrete Fourier Transform. The classic survey of windows and their figures of merit, still the reference everyone quotes.
Cooley and Tukey (1965). An Algorithm for the Machine Calculation of Complex Fourier Series. Five pages that changed computing.
Heideman, Johnson, and Burrus (1984). Gauss and the History of the Fast Fourier Transform. How the FFT was discovered, forgotten, and rediscovered several times since 1805.
Ko, Peddinti, Povey, Seltzer, and Khudanpur (2017). A Study on Data Augmentation of Reverberant Speech for Robust Speech Recognition. Far-field speech simulated by convolving with real and simulated room impulse responses, the RIR set behind Kaldi's recipes and many speaker models.
Griffin and Lim (1984). Signal Estimation from Modified Short-Time Fourier Transform. The least-squares inverse STFT and the phase-reconstruction algorithm that bears their names.
Gabor (1946). Theory of Communication. Part 1: The Analysis of Information. The paper that brought the uncertainty principle to signals and proposed Gaussian-windowed analysis, the ancestor of the STFT.
PyTorch documentation. torch.stft. The exact framing, padding, window, and normalization conventions behind most audio pipelines, including Whisper's.

Made for larger screens

The Fourier transform and the STFT

Sound is a sum of vibrations, so change basis

The DFT measures every frequency at once

The basis is orthogonal, so the inverse comes for free

The DFT as a matrix

Each bin is a frequency in hertz

A tone between bins leaks into every bin

Windows trade a wider peak for much lower sidelobes

A parabola finds a frequency between bins

Find a frequency between bins

Convolution in time is multiplication in frequency

A room is a convolution

Long signals are convolved in blocks

Reverberation augmentation by overlap-add

The FFT computes the DFT in N log N steps

A radix-2 FFT from scratch

The STFT slides a window along the signal

An STFT with the framing conventions right

Overlap-add inverts the STFT exactly

Invert the STFT

Recovering a signal when only the magnitude survives

No window is sharp in both time and frequency

Speech uses 25 ms windows for three reasons

The same STFT in PyTorch

The front end is cheap at real scale

Read more

Watch next