THE FOLD / LOOT / THE DROP / THE SARDINAS-PATTERSON
THE SARDINAS-PATTERSON
unique decoding with no separators
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Unique decodability asks: can every concatenation of codewords be split back one way only, with no separators? Prefix-free codes (no codeword begins another) are always uniquely decodable — but the converse is false, and telling the two apart needs a real test. The Sardinas–Patterson algorithm decides it: repeatedly form dangling suffixes (what is left when one codeword is a prefix of another string); the code fails to be uniquely decodable exactly when a dangling suffix is itself a codeword. {0, 01, 11} is uniquely decodable yet not prefix-free; {0, 01, 10} is not decodable at all — “010” splits two ways.
LIT verified live: the algorithm confirms {0,01,11} decodable & not prefix-free, flags {0,01,10} and the classic {1,011,01110,1110,10011} as ambiguous, and rules every random prefix-free code decodable (window.__sardinas). FIG no framing; the dangling-suffix construction runs in-browser to a fixed verdict.
LIT verified live: the algorithm confirms {0,01,11} decodable & not prefix-free, flags {0,01,10} and the classic {1,011,01110,1110,10011} as ambiguous, and rules every random prefix-free code decodable (window.__sardinas). FIG no framing; the dangling-suffix construction runs in-browser to a fixed verdict.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) reached this through principle G4 — his monoline alphabet is “uniquely decodable with no separators, 100% at every length.” Seated at the-drop: a stream of glued codewords must drop back into exactly one sequence of items. AVAN (AI) built the instrument: the Sardinas–Patterson dangling-suffix engine, plus a prefix-free test, run on the named codes and thousands of random ones.
Credit as content: August Albert Sardinas & George W. Patterson (1953). The weave: David demands separator-free unique decoding; I give the decision procedure that proves when a code has it — and shows prefix-freedom is sufficient but not necessary.
Credit as content: August Albert Sardinas & George W. Patterson (1953). The weave: David demands separator-free unique decoding; I give the decision procedure that proves when a code has it — and shows prefix-freedom is sufficient but not necessary.
3 ONE DIMENSION
The ambiguous string 010 traced two ways over {0,01,10}: 0·10 and 01·0. Two parses, one stream — not uniquely decodable.
4 TWO DIMENSIONS · INTERACTIVE
Pick a code; watch the dangling suffixes grow. If one becomes a codeword, the code is ambiguous; if the sets close with none, it is uniquely decodable.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a code whose every glued stream has exactly one parse.
AVAN’s addition (the inverse-companion): don’t only build prefix-free codes — test for the property directly, and you find codes that are decodable without being prefix-free. The inverse of ‘avoid prefixes to stay safe’ is ‘chase the dangling suffixes and see if any is a codeword.’ Magenta is the ambiguous split; green is the code that admits only one. No separators, one meaning.
LIT Genuine Sardinas–Patterson algorithm (1953): prefix-free ⇒ uniquely decodable but not conversely; a code is uniquely decodable iff no dangling suffix is a codeword — David's principle G4 ('uniquely decodable with no separators'). Verified live: {0,01,11} UD & not-prefix-free (window.__sardinas.notPFbutUD), {0,01,10} not UD (window.__sardinas.notUD), classic example not UD (window.__sardinas.classic), all 3000 random prefix-free codes UD (window.__sardinas.allPFud).
FIG No framing: the dangling-suffix construction runs in-browser to a fixed verdict on named and random codes. The AVAN inverse is honest — testing for unique decodability directly (chasing the dangling suffixes) rather than only building prefix-free codes is exactly the algorithm's contribution, and it surfaces UD-but-not-prefix-free codes; magenta is an ambiguous split, green a code admitting only one parse. No separators, one meaning.
FIG No framing: the dangling-suffix construction runs in-browser to a fixed verdict on named and random codes. The AVAN inverse is honest — testing for unique decodability directly (chasing the dangling suffixes) rather than only building prefix-free codes is exactly the algorithm's contribution, and it surfaces UD-but-not-prefix-free codes; magenta is an ambiguous split, green a code admitting only one parse. No separators, one meaning.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE DROP · David Lee Wise (ROOT0), with AVAN