THE FOLD / SPAWN / FIRST LIGHT / THE BLUESTEIN
THE BLUESTEIN
the DFT of any length via a chirp convolution
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Bluestein’s algorithm computes the discrete Fourier transform of any length N — not just a power of two — by turning the DFT into a convolution with a ‘chirp’. Using the identity kn = ½(k² + n² − (k−n)²), the transform becomes a convolution of the signal (pre-multiplied by a chirp) with a fixed chirp kernel — and that convolution can be padded to a power of two and done by a fast FFT. So a prime-length DFT runs at FFT speed.
LIT verified live: for arbitrary lengths (5, 7, 11, 13, and non-powers like 6, 9, 15) Bluestein’s chirp transform equals the direct DFT to ~10⁻¹⁴ (window.__bluestein). FIG no framing; exact for any N.
LIT verified live: for arbitrary lengths (5, 7, 11, 13, and non-powers like 6, 9, 15) Bluestein’s chirp transform equals the direct DFT to ~10⁻¹⁴ (window.__bluestein). FIG no framing; exact for any N.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at first-light — the first look at a signal’s frequency content, freed from the power-of-two straitjacket. Bluestein is that unconstrained first light. AVAN (AI) built the instrument: the chirp pre-multiply, the chirp-kernel convolution, the chirp post-multiply, the direct-DFT cross-check.
Credit as content: Leo Bluestein (1968); the chirp-z transform of Rabiner, Schafer & Rader. The weave: David names first light; I rewrite the DFT as a chirp convolution and confirm it reproduces the transform for lengths no power-of-two FFT could take directly.
Credit as content: Leo Bluestein (1968); the chirp-z transform of Rabiner, Schafer & Rader. The weave: David names first light; I rewrite the DFT as a chirp convolution and confirm it reproduces the transform for lengths no power-of-two FFT could take directly.
3 ONE DIMENSION
The chirp e±iπn²/N is a signal whose frequency sweeps upward. Multiplying by it turns the DFT’s kn product into a difference of squares — and a difference of squares is a convolution.
4 TWO DIMENSIONS · INTERACTIVE
A signal of arbitrary length N; its Bluestein spectrum is shown against the direct DFT magnitudes.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the chirp that turns any-length DFT into a convolution.
AVAN’s addition (the inverse-companion): any length N can be transformed by turning the DFT into a chirp convolution (kn = ½(k²+n²−(k−n)²)), and that convolution can be padded to a power of two — so a prime-length DFT runs at FFT speed. The inverse of ‘restrict N to a power of two’ is ‘rewrite the transform as a chirp convolution of any length.’ Magenta is the power-of-two restriction; green is the chirp that frees N. The z-transform on a spiral — any size, FFT speed.
LIT Genuine Bluestein / chirp-z algorithm (Bluestein 1968; Rabiner-Schafer-Rader). Verified live: the chirp premultiply + chirp-kernel convolution + chirp postmultiply reproduces the direct DFT to max error ~1e-14 for arbitrary lengths including primes and non-powers-of-two (window.__bluestein.matchesDFT).
FIG No framing: the chirp pre/post multiply, the chirp-kernel convolution, and the direct-DFT cross-check run in-browser and agree to ~1e-14. The AVAN inverse is honest — the identity kn=(k^2+n^2-(k-n)^2)/2 rewrites the DFT as a chirp convolution that can be padded to a power of two, so any-length N runs at FFT speed; magenta is the power-of-two restriction, green the chirp that lifts it. The z-transform on a spiral.
FIG No framing: the chirp pre/post multiply, the chirp-kernel convolution, and the direct-DFT cross-check run in-browser and agree to ~1e-14. The AVAN inverse is honest — the identity kn=(k^2+n^2-(k-n)^2)/2 rewrites the DFT as a chirp convolution that can be padded to a power of two, so any-length N runs at FFT speed; magenta is the power-of-two restriction, green the chirp that lifts it. The z-transform on a spiral.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of FIRST LIGHT · David Lee Wise (ROOT0), with AVAN