Also known as: FFTW, Fastest Fourier Transform in the West
FFTW — the Fastest Fourier Transform in the West — is a widely used, portable C library for computing the discrete Fourier transform and its inverse, in one or more dimensions, at near-optimal speed.1 Developed at MIT by Matteo Frigo and Steven G. Johnson, it earned its name and reputation by matching or beating hand-tuned, vendor-specific FFT code while remaining fully portable — it adapts to the machine rather than being rewritten for each one. It is the default high-performance FFT engine in an enormous range of scientific and signal-processing software.
How it works
FFTW’s central idea is to separate planning from execution. Before transforming data, the caller asks FFTW to create a plan for a specific transform — a given size, dimensionality, direction, and data layout. The planner explores many ways to decompose that transform, composing small optimized code fragments called codelets (generated automatically by FFTW’s own code generator) into a full algorithm, and — in its measuring modes — actually times the candidates on the host to find the fastest combination. Once built, the plan is executed repeatedly on real data; the expensive search happens once and the fast path runs on every buffer thereafter.
Several design choices follow from this:
- Machine adaptation, not machine-specific source. FFTW discovers the best algorithm at run time, so a single portable build performs well across CPUs, cache sizes, and SIMD capabilities. Its executor uses SSE/AVX and NEON where present.
- Arbitrary sizes. It is not limited to powers of two; it factors composite lengths and has dedicated algorithms for prime sizes, so real, complex, and multidimensional transforms of almost any length are handled efficiently.
- Wisdom. The result of planning can be exported to disk as wisdom and reloaded later, so a program need not re-measure on every startup — planning cost is paid once and amortized across runs.
The API is a small set of plan, execute, and destroy calls, with variants for
real-to-complex, complex-to-complex, and multidimensional transforms.
Relevance to SDR
The FFT is the workhorse of software radio, so a fast FFT library matters everywhere spectra are computed. FFTW is the engine behind the power spectral density estimates, waterfalls, and spectrograms in countless SDR tools, and behind the frequency-domain filtering (overlap-add / overlap-save) and channelizers that process wideband captures. It also accelerates transforms inside larger DSP libraries such as liquid-dsp, which uses FFTW when it is available. GNU Radio and its ecosystem lean on fast FFTs for exactly these visualization and filtering tasks. When a receiver needs to turn a buffer of IQ samples into a spectrum many times a second, FFTW is the usual reason it can keep up.
GopherTrunk does not link FFTW, because it is a pure-Go program with no C dependencies and ships as one static binary; where it needs an FFT it uses a Go implementation. FFTW remains highly relevant as context, though: it is the reference standard for FFT performance, the benchmark against which other transforms (including Go ones) are judged, and the concrete example of the “plan once, run many” pattern that any real-time spectral pipeline — GopherTrunk’s included — must adopt to avoid recomputing setup work on every buffer.