THE FOLD / GLITCH / OFF BY ONE / THE VITERBI
THE VITERBI
the most likely message through the noise
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Viterbi algorithm decodes a convolutional code by finding the single most likely transmitted sequence given a noisy received one — not by trying all 2L messages, but by a dynamic program over a trellis of encoder states. At each step it keeps only the best surviving path into each state; a traceback then reads off the maximum-likelihood message. It is the decoder in Wi-Fi, GSM, satellite links, and Voyager.
LIT verified live: over 400 noisy trials the Viterbi path metric equals the brute-force minimum Hamming distance to any codeword (it truly finds the nearest), and it corrects a single bit error exactly (window.__viterbi). FIG no framing; exact.
LIT verified live: over 400 noisy trials the Viterbi path metric equals the brute-force minimum Hamming distance to any codeword (it truly finds the nearest), and it corrects a single bit error exactly (window.__viterbi). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at off-by-one — the corrupted bit that a good decoder quietly repairs, finding the intended message one step off the received one. Viterbi is that repair. AVAN (AI) built the instrument: the rate-½ convolutional encoder, the trellis with survivor paths, the traceback, and the brute nearest-codeword cross-check.
Credit as content: Andrew Viterbi (1967). The weave: David names off-by-one; I run the trellis dynamic program, trace back the surviving path, and confirm it equals the true nearest codeword to the noisy input.
Credit as content: Andrew Viterbi (1967). The weave: David names off-by-one; I run the trellis dynamic program, trace back the surviving path, and confirm it equals the true nearest codeword to the noisy input.
3 ONE DIMENSION
The trellis: encoder states over time. Each received pair adds a branch metric (bits that disagree); at every state only the cheapest incoming path survives. The best full path is the decoded message.
4 TWO DIMENSIONS · INTERACTIVE
A message is encoded, noise is injected, and Viterbi recovers it; the survivor metric is checked against the brute nearest-codeword distance.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the maximum-likelihood path through the trellis.
AVAN’s addition (the inverse-companion): recover the most likely sent message from a noisy stream without enumerating all 2L candidates — a trellis dynamic program keeps only the best survivor into each state, then traces back. The inverse of ‘encode a message into a redundant stream’ is ‘decode the stream to the nearest legal codeword — by survivors, not brute force.’ Magenta is the exponential set of paths pruned away; green is the one surviving max-likelihood path. The signal recovered from the noise.
LIT Genuine Viterbi maximum-likelihood decoding of a rate-1/2, K=3 convolutional code (Viterbi 1967). Verified live: over 400 noisy trials the trellis survivor metric equals a brute-force minimum Hamming distance to any codeword (the algorithm finds the true nearest), and it recovers the original message exactly when at most one bit was flipped (window.__viterbi.mlEqualsBrute && .correctsSingle).
FIG No framing: the convolutional encoder, the trellis with per-state survivor paths, the traceback, and the brute nearest-codeword cross-check run in-browser and agree exactly. The AVAN inverse is honest — a trellis dynamic program keeping only the best survivor into each state recovers the maximum-likelihood message without enumerating 2^L candidates; magenta is the exponential set of paths pruned, green the one surviving path. The signal recovered from the noise.
FIG No framing: the convolutional encoder, the trellis with per-state survivor paths, the traceback, and the brute nearest-codeword cross-check run in-browser and agree exactly. The AVAN inverse is honest — a trellis dynamic program keeping only the best survivor into each state recovers the maximum-likelihood message without enumerating 2^L candidates; magenta is the exponential set of paths pruned, green the one surviving path. The signal recovered from the noise.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of OFF BY ONE · David Lee Wise (ROOT0), with AVAN