Overlap-Add STFT

Audio is a river of numbers — typically 44 100 samples every second. A single global FFT tells you which frequencies are present across the whole recording, but it cannot tell you when a note starts, fades, or changes pitch. For that you need a view that moves through time.

The Short-Time Fourier Transform (STFT) gives you exactly that. It slides a short analysis window across the signal, computes a regular FFT on each windowed chunk, and stacks the results into a two-dimensional picture called a spectrogram — time on one axis, frequency on the other, brightness for amplitude.

But a spectrogram is also a gateway to editing. If you modify the frequency content of each frame and then reconstruct the signal, you get the overlap-add (OLA) method: the fundamental engine behind every equalizer, noise canceller, pitch shifter, and audio codec you have ever used.

The key insight is that the windowing step introduces a distortion — each sample is multiplied by the window twice (once on analysis, once on synthesis). The overlap-add trick cancels that distortion perfectly, provided the frames overlap enough. With a Hann window and 50 % overlap, adjacent windows satisfy the COLA condition ($w[n] + w[n+H] = 1$) — so every sample is recovered without error.

The canvas below shows a live scrolling spectrogram. A synthetic tone glides continuously from a low frequency up to a high one and back, and the STFT paints each new column as the tone sweeps through it.

<!-- {{c_html_intro}} -->
<div class="controls">
  <label>{{lbl_window}} <select id="winSize">
    <option value="64">64</option>
    <option value="128" selected>128</option>
    <option value="256">256</option>
    <option value="512">512</option>
  </select></label>
  <label>{{lbl_overlap}} <select id="hopFrac">
    <option value="0.25">25 %</option>
    <option value="0.5" selected>50 %</option>
    <option value="0.75">75 %</option>
  </select></label>
  <button id="btnReset" type="button">{{btn_reset}}</button>
</div>
<canvas id="spec" width="560" height="320" title="{{canvas_title}}"></canvas>
<div class="info" id="info">{{msg_running}}</div>

/* {{c_css_layout}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; background: #0d1117; color: #c9d1d9; }
.controls { display: flex; gap: .6rem; flex-wrap: wrap; align-items: center; padding: .5rem 0 .4rem; }
label { font-size: .85rem; color: #8b949e; display: flex; align-items: center; gap: .35rem; }
select { font-size: .85rem; padding: .2rem .4rem; border-radius: 5px;
         border: 1px solid #30363d; background: #161b22; color: #c9d1d9; cursor: pointer; }
button { font: 600 .82rem system-ui, sans-serif; padding: .25rem .75rem;
         border: 1px solid #58a6ff; background: transparent; color: #58a6ff;
         border-radius: 6px; cursor: pointer; }
button:hover { background: #58a6ff22; }
canvas { display: block; width: 100%; max-width: 560px; border-radius: 6px;
         border: 1px solid #21262d; image-rendering: pixelated; }
.info { font-size: .78rem; color: #8b949e; margin-top: .35rem; min-height: 1.2em; }

// Code not found

Use the controls to change the window size (more samples per frame = sharper frequency resolution but blurrier time edges) and the overlap (more overlap = smoother scrolling but heavier computation). Notice how a large window resolves the glide into a clean arc, while a tiny window smears the frequency but captures abrupt onsets crisply.

Let $x[n]$ be your audio signal and $w[n]$ a window of length $N$ (we will use the Hann window: $w[n] = \tfrac{1}{2}\!\left(1 - \cos\!\tfrac{2\pi n}{N-1}\right)$). The STFT at hop $m$ is simply the FFT of the windowed frame:

$$X_m[k] = \sum_{n=0}^{N-1} x[n + m \cdot H]\, w[n]\, e^{-j 2\pi k n / N}$$

where $H$ is the hop size (samples between successive frames) and $k$ indexes the $N$ frequency bins.

Why overlapping frames? Each FFT takes $\mathcal{O}(N \log N)$ time. With hop $H$ and a signal of $L$ samples the total cost is $\mathcal{O}(\tfrac{L}{H} \cdot N \log N)$. Smaller hops mean more frames — and smoother time resolution — but proportionally more work. There is no free lunch: halving $H$ doubles the computation.

Time–frequency trade-off. The window length $N$ controls two things at once:

• Frequency resolution is $\tfrac{f_s}{N}$ Hz per bin. Wider window $\Rightarrow$ finer frequency grid.
• Time resolution is roughly $\tfrac{N}{f_s}$ seconds per frame. Wider window $\Rightarrow$ coarser time grid.

You cannot improve both simultaneously — this is the audio analogue of the Heisenberg uncertainty principle.

Overlap-add reconstruction. Given modified frames $\hat{X}_m[k]$, apply the inverse FFT to each, multiply by $w[n]$ again (synthesis window), and add the overlapping contributions at each sample position $n$:

$$\hat{x}[n] = \sum_{m} \left(\text{IFFT}\{\hat{X}_m\}[n - m H]\right) \cdot w[n - m H]$$

For a Hann window with 50 % overlap ($H = N/2$), adjacent windows satisfy $w[n] + w[n + H] = 1$ everywhere (the COLA condition — Constant Overlap-Add) — which means the overlap-add sum is exactly constant. Dividing by that constant gives back the original signal perfectly (modulo numerical precision), even after you have changed the spectrum of every frame.

The overlap-add STFT is the invisible engine inside almost every piece of audio software:

• Equalization and filtering: multiply each frequency bin by a gain factor, then reconstruct — a perfect linear filter with no ringing artifacts from circular convolution.
• Pitch shifting and time stretching: modify the phase of each bin to shift pitch without changing duration (phase vocoder), or stretch duration without changing pitch.
• Noise cancellation and de-reverberation: estimate a noise spectrum from a quiet frame, subtract it from every subsequent frame in the STFT domain, and reconstruct clean speech. Every pair of active noise-cancelling headphones runs a variant of this in real time.
• Audio codecs (MP3, AAC, Opus): the modified discrete cosine transform (MDCT) used in these codecs is essentially an overlap-add filter bank — a close cousin of the STFT.
• Music information retrieval: chroma features, onset detection, and beat tracking all start from the magnitude spectrogram produced by the STFT.
• Speech recognition: mel-frequency cepstral coefficients (MFCCs), the classic feature for ASR, are computed from the log-mel spectrogram — itself derived from the STFT.

The same windowed FFT idea also underpins radar and sonar processing, where "range-Doppler" maps are exactly spectrograms of the reflected pulse.

The STFT's central bargain is simple: accept that you cannot know frequency and time with perfect precision at once, choose a window length that balances the two for your task, and let the FFT do the heavy lifting frame by frame.

The overlap-add step closes the loop. By overlapping adjacent windows enough that they sum to a constant, you can modify every frame in the frequency domain — pitch-shifting, filtering, denoising — and stitch the result back together without a single audible seam.

Every time you slide the bass knob on a streaming app, activate noise cancellation on your headphones, or let a codec compress your voice call, you are riding on that elegant trade-off between time and frequency — a trade-off baked into the mathematics of the Fourier transform itself.