THE FOLD / LOOT / THE DROP / THE KRAFT INEQUALITY
THE KRAFT INEQUALITY
when a set of codeword-lengths can be a prefix code
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Kraft inequality is the budget law of prefix codes. A prefix code (no codeword is the start of another, so a stream decodes without markers) with codeword lengths ℓ1, ℓ2, … exists if and only if Σ 2−ℓi ≤ 1. Each length-ℓ codeword spends a share 2−ℓ of a unit budget; short codewords are expensive. The bound is tight both ways: any prefix code obeys it, and any set of lengths obeying it can be realised as a prefix code. Equality means the code is complete — a full binary tree with no room to spare.
LIT verified live: every random prefix code satisfies Σ 2−ℓ ≤ 1, any length multiset with Σ 2−ℓ ≤ 1 is constructed into an actual prefix code, and complete codes hit Σ = 1 (window.__kraft). FIG no framing; prefix-freeness checked and codes built explicitly.
LIT verified live: every random prefix code satisfies Σ 2−ℓ ≤ 1, any length multiset with Σ 2−ℓ ≤ 1 is constructed into an actual prefix code, and complete codes hit Σ = 1 (window.__kraft). FIG no framing; prefix-freeness checked and codes built explicitly.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-drop — every codeword you claim spends a slice 2−ℓ of a single unit; you can spend up to all of it and no more. That budget is the drop. AVAN (AI) built the instrument: the prefix-free test, the Σ 2−ℓ sum, the greedy code-builder from a length multiset, and the complete-code equality.
Credit as content: Leon G. Kraft (1949); the converse for uniquely-decodable codes is Brockway McMillan (1956). The weave: David names the-drop; I check that no codeword prefixes another, add up their 2−ℓ shares, and confirm the sum never exceeds one — and that any lengths within budget can be dealt out as real codewords.
Credit as content: Leon G. Kraft (1949); the converse for uniquely-decodable codes is Brockway McMillan (1956). The weave: David names the-drop; I check that no codeword prefixes another, add up their 2−ℓ shares, and confirm the sum never exceeds one — and that any lengths within budget can be dealt out as real codewords.
3 ONE DIMENSION
{0, 10, 11}: lengths 1, 2, 2 → 1/2 + 1/4 + 1/4 = 1 (complete). {0, 10, 110} → 1/2 + 1/4 + 1/8 = 7/8 ≤ 1 (room to spare). A length-1 codeword costs half the whole budget.
4 TWO DIMENSIONS · INTERACTIVE
A code on the binary tree, its Kraft sum against the unit budget; whether it is prefix-free and complete; checked.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: codeword lengths that fit a unit budget.
AVAN’s addition (the inverse-companion): don’t design a code and hope it decodes — pick the lengths first, check they fit the budget Σ 2−ℓ ≤ 1, and a prefix code is guaranteed to exist. The inverse of ‘build a prefix code’ is ‘the lengths alone decide whether one can.’ Magenta is an over-budget length set (no code); green is a within-budget set realised as a code. Lengths, not letters, decide.
LIT Genuine Kraft inequality (Leon G. Kraft, 1949; the uniquely-decodable converse is Brockway McMillan, 1956). Verified live: over 1500 random prefix codes, Σ 2^(−ℓ) ≤ 1 always holds (window.__kraft.forward); any length multiset with Σ 2^(−ℓ) ≤ 1 is built into an actual prefix-free code by greedy assignment (window.__kraft.constructible); and complete codes like {0,10,11} hit Σ = 1 (window.__kraft.complete).
FIG No framing: the prefix-free test, the Σ 2^(−ℓ) sum, the greedy code-builder, and the complete-code equality all run in-browser with exact arithmetic. The AVAN inverse is honest — deciding whether a code exists from the lengths alone (Σ 2^(−ℓ) ≤ 1) rather than designing one is exactly Kraft's content; magenta is an over-budget length set, green a within-budget set realised as a code. Lengths, not letters, decide.
FIG No framing: the prefix-free test, the Σ 2^(−ℓ) sum, the greedy code-builder, and the complete-code equality all run in-browser with exact arithmetic. The AVAN inverse is honest — deciding whether a code exists from the lengths alone (Σ 2^(−ℓ) ≤ 1) rather than designing one is exactly Kraft's content; magenta is an over-budget length set, green a within-budget set realised as a code. Lengths, not letters, decide.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE DROP · David Lee Wise (ROOT0), with AVAN