Short-time_Fourier_transform

# Short-time Fourier transform The **short-time Fourier transform** (STFT) is the [[Fourier_transform]] of a [[Signal|signal]] seen through a sliding [[Window_function|window]]: the signal is multiplied by a short window centred at time τ, the product is transformed, and the window is moved on, so that the result `X(τ, ω)` describes which frequencies are present near each instant rather than over the whole record. A plain transform reports what frequencies a signal contains but not when they occur; the STFT recovers the when at the cost of blurring the what, because every window of duration Δt smears frequency by about 1/Δt. Plotted as squared magnitude over time and frequency the STFT becomes the [[Spectrogram|spectrogram]], the standard picture of speech, music, [[Radar]] returns and radio bands, and drawn as a stack of spectra it is the [[Waterfall_plot|waterfall plot]] of a receiver display. In digital practice the STFT is a sequence of windowed [[Discrete_Fourier_transform|discrete Fourier transforms]] of length L taken every H samples, almost always computed by a [[Fast_Fourier_transform|fast Fourier transform]], with time resolution L/fs, frequency resolution fs/L and a product of the two that is fixed at one. That fixed product is the transform's whole character, and it is the reason the [[Wavelet_transform|wavelet transform]], which lets the window shrink as frequency rises, was invented as an alternative. The primary microsim on this page, *Short-time Fourier transform*, computes the STFT of a rising chirp [[Sampling_(signal_processing)|sampled]] at 2,000 Hz and paints it column by column as a spectrogram: the reader drags the window length between 32 and 512 samples and the overlap between 0 and 87.5 %, adds a steady tone or noise, and reads the time and frequency resolution, the hop and the frame count from a diagnostics panel while a box on the waveform shows exactly which samples the current column sees. ## Forward STFT ### Continuous-time STFT For a continuous signal x(t) and a [[Window_function|window]] w(t) that is non-zero only near t = 0, the transform is `X(τ, ω) = ∫ x(t) w(t − τ) e^{−jωt} dt`, a function of two variables: the window position τ, which plays the role of time, and the frequency ω. At each τ it is the ordinary [[Fourier_transform|Fourier transform]] of the windowed signal x(t) w(t − τ), and since multiplication in time is [[Convolution|convolution]] in frequency, it is also the true spectrum near τ convolved with the transform of the window.[^tm96] A rectangular window of duration T has the transform `W(f) = T sinc(Tf)`, with zeros at multiples of 1/T; a cosine of amplitude A seen through it appears as `(AT/2)[sinc(T(f + f₀)) + sinc(T(f − f₀))]`, two main lobes 2/T wide flanked by side lobes.[^tm98] Every column of a [[Spectrogram|spectrogram]] is one such windowed spectrum, and the width of every feature in it is the width of the window's main lobe. ### Discrete-time STFT For [[Sampling_(signal_processing)|samples]] x[n] taken at fs, the window becomes a sequence w[n] of L samples, the position τ becomes a frame index m advancing by a hop of H samples, and the integral becomes a [[Discrete_Fourier_transform|DFT]] of the windowed slice: `X[m, k] = Σ_{n=0}^{L−1} x[n + mH] w[n] e^{−j2πkn/L}`, which is the equation the sketch prints in its title bar and evaluates for every column. Frame m is centred H·m/fs seconds into the record and bin k sits at k·fs/L hertz, so the time axis of the spectrogram has a step of H/fs and the frequency axis a spacing of fs/L. The sketch's diagnostics panel prints both for the current settings; at the default L = 128 and 50 % overlap they are a hop of 64 samples, a time step of 32.0 ms and a bin spacing of 15.6 Hz, giving 31 frames and 65 bins from a 2,048-sample record. The window in the sketch is a Hann window, `w[n] = 0.5 − 0.5 cos(2πn/(L − 1))`, whose tapered ends stop the hard edges of a slice from spraying [[Spectral_leakage|leakage]] across every bin; its main lobe is twice as wide as a rectangular window's and its side lobes are far lower.[^tm101] Overlap matters because a window that tapers to zero ignores the samples at its edges: with 50 % overlap every sample is weighted heavily by at least one frame, and at 87.5 % the sketch computes 121 frames from the same record instead of 31, a smoother image with no gain in resolution. #### Sliding DFT When the hop is a single sample and the window is rectangular, the DFT of frame m + 1 can be updated from that of frame m rather than recomputed: the sample that leaves the window is subtracted, the one that enters is added, and the whole bin is rotated by one twiddle, `X_k[m + 1] = e^{j2πk/L} (X_k[m] + x[m + L] − x[m])`. This sliding DFT costs one complex multiply-add per bin per sample, independent of L, and is the discrete counterpart of the recursive method described under Implementation; its price is that it works only for a rectangular window and that the rotation, a pole exactly on the unit circle, lets round-off accumulate unless the recursion is periodically reset. ## Inverse STFT ### Continuous-time STFT The STFT contains the signal many times over, once per window position, and can be inverted in several ways. Fixing τ and inverting the ordinary transform gives back the windowed signal, `x(t) w(t − τ) = (1/2π) ∫ X(τ, ω) e^{jωt} dω`; integrating both sides over τ and dividing by the area of the window, `∫ w(τ) dτ`, gives x(t) itself, provided the window has non-zero area. Alternatively any single τ suffices wherever w(t − τ) is non-zero, since x(t) is then the windowed signal divided by the window. The discrete version is overlap-add: each frame is inverse-transformed, multiplied by a synthesis window and added into the output at its hop position, and the result equals the signal wherever the sum of the overlapping products of analysis and synthesis windows is constant. A Hann window at 50 % overlap satisfies this "constant overlap-add" condition, in its periodic form exactly and in the symmetric form the sketch uses to within a small ripple, which is why the sketch's default pairing of window and overlap is the one most [[Audio_signal_processing|audio software]] uses when it must modify a [[Spectrogram|spectrogram]] and turn it back into sound. If the magnitude alone has been kept, the phase must be estimated before resynthesis, and the reconstruction is then only approximate. ## Resolution issues ### Examples The sketch's test [[Signal|signal]] is a linear chirp rising from 60 to 760 Hz across a 1.024 s record, a rate of about 684 Hz per second. With the window length at 32 samples, 16.0 ms, the diagnostics read a bin spacing of 62.5 Hz and the chirp appears as a fat diagonal band with sharp edges in time: the frequency of the tone within any one window is known only to a couple of bins, but the moment it passes any frequency is known to within one hop of 8.0 ms. With the window at 512 samples, 256.0 ms, the bin spacing falls to 3.9 Hz but the record holds only seven frames at 50 % overlap, and the diagonal becomes a staircase of wide steps. Within a single 256 ms window the chirp itself moves through about 175 Hz, so its streak is broad in frequency for a different reason: the signal is not stationary over the window. The verdict line in the panel reads "short window, sharp in time, blurry in frequency" at L ≤ 64 and "long window, sharp in frequency, blurry in time" at L ≥ 256. The *Steady tone* button adds a 250 Hz [[Sine_wave|sinusoid]] of amplitude 0.8 and makes the frequency side of the trade visible without the chirp's complication. The tone is a horizontal line whose thickness is the window's main lobe: two to four bins of 62.5 Hz at L = 32, an unmistakable band, and two to four bins of 3.9 Hz at L = 512, a hairline. The textbook's two-tone example gives the same law in numbers: two cosines observed for T = 1 s merge into one peak when they are 1 Hz apart, begin to separate at 1.5 Hz, and are resolved, though their peaks are biased, at 2 and 2.5 Hz; and a second tone of a quarter the amplitude is masked entirely at 1 Hz, visible but biased at 2 Hz and clear at 2.5 Hz.[^tm98] Because the record is finite, the same blur affects every method of spectral estimation, including a spectrum of a 0.01 s segment of [[Audio_signal_processing|audio]] at 44.1 kHz, 441 samples, which resolves frequency only to 100 Hz.[^d70] ### Explanation Nothing in the arithmetic is lost; the blur is a property of windows. A window of duration Δt has a transform whose main lobe is about 1/Δt wide, so the product of time resolution and frequency resolution is fixed: the sketch computes Δt = L/fs and Δf = fs/L and prints their product, which is exactly 1.00 at every setting because the two are reciprocals by definition. The [[Uncertainty_principle|uncertainty principle]] of [[Fourier_analysis|Fourier analysis]] states the same thing for root-mean-square widths, `σ_t σ_ω ≥ 1/2`, with equality only for a Gaussian window, so the sketch's product of window length and bin spacing is a coarser but equivalent measure of the same bound. Choosing a window length is therefore choosing where to spend a fixed budget, and no window is the best for every job.[^tm103] A signal whose frequency drifts within the window, like the chirp, adds a second smearing of its own, equal to the drift over the window duration, and the sharpest picture of such a signal comes from the window for which the two smearings are equal, here in the region of 64 to 128 samples. ## Rayleigh frequency The smallest frequency separation an analysis of duration T can resolve is about 1/T, the Rayleigh frequency, by analogy with the resolving power of a telescope aperture. It is the bin spacing of a [[Discrete_Fourier_transform|DFT]] of the record, fs/L = 1/(L/fs), and it appears in the sketch as the Δf line of the diagnostics: 62.5 Hz for a 16 ms window, 15.6 Hz for 64 ms and 3.9 Hz for 256 ms. Two [[Sine_wave|tones]] closer than the Rayleigh frequency fall within one main lobe of each other and cannot be told apart; the textbook's cosines at 1 Hz separation with T = 1 s are exactly at the limit and appear as one broad peak.[^tm98] Zero-padding the window before the transform draws the spectrum at finer intervals but leaves the Rayleigh frequency unchanged, because the observation is unchanged.[^tm144] Only a longer window lowers it, which is the trade-off of the previous section once more. ## Application Spectrograms are the working display of every field of [[Signal_processing|signal processing]] that studies signals whose content changes. In [[Audio_signal_processing|audio]] they show the formants and pitch contour of speech, the notes and harmonics of music and the calls of animals; the time resolution of a few milliseconds and frequency resolution of tens of hertz that speech needs is met by windows of 20 to 30 ms, and the textbook's chirp recording, a pitch gliding from about 500 to 300 Hz over 1.4 s, is analysed with a segment length chosen so that the glide within one segment stays small, since a long segment blurs a gliding pitch.[^d68][^d70] In radio the waterfall display of a software-defined receiver is an STFT of the whole received band, one row per frame, with signals appearing as vertical traces and their [[Signal_modulation|modulation]] as texture. In [[Sonar]] and radar the STFT follows the Doppler shift of a target through time, and in vibration monitoring it follows the harmonics of a machine as its speed changes. The STFT is a uniform [[Filter_bank|filter bank]], and it is also the analysis stage of most audio coders and of the phase vocoder, which alters the timing or pitch of a recording by modifying the spectrogram and resynthesising by overlap-add. ## Implementation ### Direct implementation The sum can be evaluated literally, one bin at a time, as the sketch does in its column routine: for each of the L/2 + 1 bins a running phasor is rotated by e^{−j2πk/L} at each sample and the windowed sample is accumulated against it, so that no trigonometric function is called inside the loop. The cost is L complex multiply-adds per bin, or about L²/2 per column: 8,320 at L = 128 and 131,584 at L = 512 in the sketch, which computes up to eight columns per animation frame so that the image fills in visibly. Direct evaluation is simple, works for any L and lets the bins be chosen freely, but its cost grows with the square of the window. #### Constraints The quadratic cost limits direct evaluation to short windows or to a handful of bins. Generating the twiddle by repeated rotation is exact only up to the accumulated round-off of L multiplications, negligible for L ≤ 512 in double precision but in need of periodic correction in longer windows or fixed-point arithmetic. ### FFT-based method Replacing each column's DFT by a fast Fourier transform reduces the cost from about L² to L log₂ L operations, a factor of 341 at a window of 4,096 samples,[^tm133] and produces all L bins at once. Every production spectrogram is computed this way: window the slice, transform it, take the squared magnitude in [[Decibel|decibels]], advance by the hop and repeat, a sequence of independent transforms that parallelises trivially. #### Constraint The FFT computes every bin whether or not it is wanted, so when only a few frequencies matter a direct or recursive method can be cheaper. Its length is most efficient at powers of two, which is why the sketch's window choices run from 32 to 512, and the bins are fixed at multiples of fs/L unless the slice is zero-padded, which interpolates the spectrum without improving its resolution.[^tm144] ### Recursive method The sliding DFT above, and its single-bin relative the Goertzel algorithm, compute a bin as the output of a [[Infinite_impulse_response|recursive filter]], `y(m) = W^k y(m − 1) + x(N − m)` with y(0) = 0, so that the bin is y(N) after N steps. The work per new sample is constant per bin, which suits real-time detection of a few known frequencies, such as telephone dialling tones, where the transform must be updated at every sample. #### Constraint The recursion has a pole on the unit circle and is only marginally stable, so round-off accumulates without bound unless the state is reset, and the first-order form needs about as many multiply-adds per bin as the direct sum, saving only the trigonometric evaluations. The window is necessarily rectangular, since a tapered window cannot be updated by adding and subtracting single samples. ### Chirp Z transform The chirp-z, or Bluestein, [[Algorithm|algorithm]] evaluates the transform at frequencies spaced arbitrarily, not only at multiples of fs/L, by writing the exponent as `nk = (n² − (k − n)² + k²)/2`, which turns the sum into a convolution with a chirp that is computed by an FFT of length at least 2L − 1, in practice the next power of two. For the STFT it allows a zoomed spectrogram, a narrow band of frequencies drawn at fine spacing from a short window, and it removes the power-of-two restriction on the window length. #### Constraint The chirp-z transform costs about three FFTs of a length at least 2L − 1 per column, several times the cost of a single FFT, and like zero-padding it draws the spectrum at finer points without narrowing the main lobe, so the Rayleigh frequency of the window still governs what can be told apart.[^tm144] ### Implementation comparison | Method | Operations per column, all L/2 + 1 bins | Window | Best suited to | |---|---|---|---| | Direct sum | about L²/2 complex multiply-adds | any | few bins, small L, teaching | | FFT | about (L/2) log₂ L butterflies | any | every bin of every column | | Sliding DFT or Goertzel | about L per new sample, or N per bin | rectangular only | a few bins updated every sample | | Chirp-z | about three FFTs of length ≥ 2L − 1 | any | zoomed or arbitrarily spaced bins | At the sketch's largest window, L = 512, the direct sum needs 131,584 complex multiply-adds per column against about 2,304 butterflies for a radix-2 FFT of the same length. ## Microsims The *Short-time Fourier transform* sketch shows three panels and a diagnostics strip. The top panel plots the 2,048-sample test record, a linear chirp from 60 to 760 Hz [[Sampling_(signal_processing)|sampled]] at 2,000 Hz, with an amber box marking the L samples that the current column's DFT sees and the Hann [[Window_function|window]]'s shape drawn inside it. The middle panel is the [[Spectrogram|spectrogram]] |X[m, k]| in [[Decibel|decibels]] over a fixed 70 dB range, frequency from 0 to the 1,000 Hz [[Nyquist_frequency|Nyquist]] limit upward and time from 0 to 1.02 s across, painted eight columns per frame so that a change of settings can be watched filling in, with a playhead that ties each column to the box above. The *Window length L* slider steps through 32, 64, 128, 256 and 512 samples (16.0 to 256.0 ms, default 128) and the *Overlap* slider through 0, 50, 75 and 87.5 % (default 50 %); *Steady tone* adds a 250 Hz sinusoid, *Noise* adds broadband hiss and *Play/Pause* stops the playhead. The diagnostics list the sample rate, the Nyquist frequency, L, the hop H, the overlap, the number of frames and bins, Δt = L/fs, Δf = fs/L, the time step H/fs and the product Δt·Δf, which is 1.00 by construction, followed by a one-line verdict on the trade-off. A three.js companion on this page renders the same trade in depth, the blur swapping axes as the window length changes. *Try:* Switch *Steady tone* on, then drag *Window length L* from 32 to 512 and watch the 250 Hz line thin from a band to a hairline as Δf falls from 62.5 Hz to 3.9 Hz, while the chirp's diagonal breaks into seven wide steps and the frame count drops from 127 to 7; then raise *Overlap* to 87.5 % and watch the frames climb to 25 with no change in Δf.  **Microsim — three.js (Wikitube framework), pending deploy:** *Short-time Fourier transform: the window trades time for frequency* will play here once `https://wikitube-3d-microsims.netlify.app/signal/Short-time_Fourier_transform.html` is live.  *Built from `MICROSIM_GUIDE/specs/sims/Short-time_Fourier_transform.json`; part of the [[Signal_processing]] set ([[PORTAL_Signal_Processing]]).*  ## Wikipedia : Wikitube **Strict pair:** [Wikipedia](https://en.wikipedia.org/wiki/Short-time_Fourier_transform) : [Wikitube](https://en.wikitube.io/wiki/Short-time_Fourier_transform) Skeleton mirrored at revision 1361573503. Prose, emphasis and the microsims are Wikitube's own. ## See also - [[Spectrogram]] - [[Wavelet_transform]] - [[Fast_Fourier_transform]] - [[Window_function]] - [[Waterfall_plot]] - [[Discrete_Fourier_transform]] - [[Spectral_leakage]] - [[Uncertainty_principle]] - [[PORTAL_Signal_Processing]] ## References [^tm96]: Tiberius, C.; Mulder, M. *Engineering Signal Analysis: From Fourier to filtering: Theory*. 2026, pp. 96–97 (PDF pages): the rectangular window x_w = w·x with X_w = W ∗ X, W(f) = T sinc(Tf) with zeros at k/T, Eqs. 8.1–8.2, and the complex transform of a causal window on [0, T]. Open Textbook Library: https://open.umn.edu/opentextbooks/textbooks/engineering-signal-analysis-from-fourier-to-filtering-theory . CC BY. [^tm98]: Tiberius, C.; Mulder, M. *Engineering Signal Analysis: From Fourier to filtering: Theory*. 2026, pp. 98–100 (PDF pages): the windowed cosine (AT/2)[sinc(T(f + f₀)) + sinc(T(f − f₀))], Eq. 8.3, two tones at f₁ = 10 Hz with T = 1 s at separations of 1, 1.5, 2 and 2.5 Hz, and the masking of a tone of relative amplitude 0.25. Open Textbook Library: https://open.umn.edu/opentextbooks/textbooks/engineering-signal-analysis-from-fourier-to-filtering-theory . CC BY. [^tm101]: Tiberius, C.; Mulder, M. *Engineering Signal Analysis: From Fourier to filtering: Theory*. 2026, pp. 101–102 (PDF pages): the Hann window w(t) = Π(t/T)(1/2 + (1/2)cos(2πt/T)) and its transform, Eqs. 8.5–8.6, with a main lobe twice as wide and much lower side lobes. Open Textbook Library: https://open.umn.edu/opentextbooks/textbooks/engineering-signal-analysis-from-fourier-to-filtering-theory . CC BY. [^tm103]: Tiberius, C.; Mulder, M. *Engineering Signal Analysis: From Fourier to filtering: Theory*. 2026, p. 103 (PDF page): no window is best for every purpose. Open Textbook Library: https://open.umn.edu/opentextbooks/textbooks/engineering-signal-analysis-from-fourier-to-filtering-theory . CC BY. [^tm133]: Tiberius, C.; Mulder, M. *Engineering Signal Analysis: From Fourier to filtering: Theory*. 2026, p. 133 (PDF page): N² operations for the DFT against m·2^m for the FFT, 16,777,216 against 49,152 at N = 4,096. Open Textbook Library: https://open.umn.edu/opentextbooks/textbooks/engineering-signal-analysis-from-fourier-to-filtering-theory . CC BY. [^tm144]: Tiberius, C.; Mulder, M. *Engineering Signal Analysis: From Fourier to filtering: Theory*. 2026, pp. 144–146 (PDF pages): zero-padding shrinks the bin spacing to 1/T_x but adds no information, Example 12.6. Open Textbook Library: https://open.umn.edu/opentextbooks/textbooks/engineering-signal-analysis-from-fourier-to-filtering-theory . CC BY. [^d68]: Downey, A. *Think DSP: Digital Signal Processing in Python*. 2012, p. 68 (PDF page): a recorded chirp whose pitch glides from about 500 to 300 Hz over about 1.4 s. Open Textbook Library: https://open.umn.edu/opentextbooks/textbooks/think-dsp-digital-signal-processing-in-python . CC BY-NC. [^d70]: Downey, A. *Think DSP: Digital Signal Processing in Python*. 2012, p. 70 (PDF page): a 0.01 s segment at 44.1 kHz is 441 samples and resolves frequency to 100 Hz; spectral resolution is the frame rate divided by the segment length, and longer segments blur a gliding pitch. Open Textbook Library: https://open.umn.edu/opentextbooks/textbooks/think-dsp-digital-signal-processing-in-python . CC BY-NC. ## External links - Short-time Fourier transform, live p5.js sketch: https://editor.p5js.org/sciencenibber/full/FD33qCDN9 - Short-time Fourier transform, fork the sketch in the p5.js editor: https://editor.p5js.org/sciencenibber/sketches/FD33qCDN9