12. Codes and the Kraft inequality¶
Where this fits
Prerequisites: Chapter 1 (probability, events, disjoint events, independence), Chapter 3 (bits, nats, \(\log_2\), \(\ln\), surprisal, the 8,192-bit kilobyte), and the idea of a prior from Chapter 11. Used later by: Chapter 13 (Kolmogorov complexity and the Solomonoff prior), Chapter 14 (compressed size as complexity), Chapter 22 (arithmetic coding) and Chapter 24 (Algorithm 1). Purpose: show why a model that compresses to \(C\) bits may receive a prior weight of about \(2^{-C}\), and where the paper's extra "\(2\log C\)" comes from (the paper writes a bare "log"; it is \(2\log_2 C\) bits, or \(2\ln C\) nats).
The problem this chapter solves¶
Everything in this section is MY EXPLANATION unless tagged.
The bound at the heart of the paper (Eq. 1, built in Chapter 11) needs a prior. A quick reminder: a hypothesis \(h\) is one fully specified model, and a prior gives every hypothesis a weight \(P(h) \ge 0\). The weights are fixed before any training data are seen, and together they must add up to at most 1.
The bound gets looser as \(\ln\frac{1}{P(h)}\) grows. So we want the model we end up training to have a large prior weight.
PAPER §4.1, p. 4 The paper weights a model by how briefly it can be written down. It bounds \(\ln\frac{1}{P(h)}\) by \(C(h)\ln 2 + 2\ln C(h)\), where \(C(h)\) is the number of bits needed to represent \(h\) with a coding scheme chosen in advance. (The paper writes a bare "log"; we show below that it must mean \(\ln\) here.)
Read in bits, this says: a model that compresses to \(C\) bits gets a prior weight of roughly \(2^{-C}\). Every extra bit of description halves the weight.
There is a catch. Not every way of turning models into bits gives weights that add up to at most 1.
Here is an example. A compressor is a program that turns a file into a string of bits, together with a matching decompressor that turns the bits back into exactly the same file. Suppose our compressor can output any bit string with 1 to 20 bits. Give each output of length \(c\) the weight \(2^{-c}\). There are \(2^c\) strings of length \(c\), so each length contributes \(2^c \times 2^{-c} = 1\). The total weight is 20 (script output, block [5]). That is not a prior. It hands out twenty times more probability than exists.
This chapter answers three questions.
- Which sets of bit strings have weights \(2^{-\text{length}}\) that add up to at most 1? Answer: prefix-free codes. This is the Kraft inequality.
- How can any compressor's output be turned into such a code? Answer: put a short header in front that says how long the message is.
- What does the header cost? Answer: about \(2\log_2 C\) bits. That is the paper's "\(+2\log C(h)\)" (bare "log" in the paper; erratum E02 below sorts out the base).
Intuition (and where the analogy breaks)¶
Everything in this section is MY EXPLANATION.
Phone numbers. To call abroad you dial a country code and then the local number, with no separator between them. The phone network still knows where the country code ends. The reason is that no country code is the beginning of another one. The United States and Canada share code 1, so no other country code starts with the digit 1. The United Kingdom has 44, so no country has the code 4. The network reads digits until they form a complete country code. At that moment it knows the code is over.
That property — no codeword is the beginning of another — is called prefix-free. It lets a reader find the end of each codeword from the codeword itself.
A budget of coin flips. Imagine flipping a fair coin again and again, writing 0 for tails and 1 for heads. Each codeword "claims" all the flip sequences that begin with it. Half of all sequences begin with 0. A quarter begin with 10. In general, a codeword of length \(\ell\) claims a \(2^{-\ell}\) share of all sequences.
In a prefix-free code no flip sequence is claimed twice. So the shares cannot add up to more than the whole:
That is the Kraft inequality. The figure draws the same picture as a tree. Each codeword sits at the end of a path of 0/1 branches, and it owns the slice of the interval \([0,1)\) directly beneath it.
Where it breaks.
- A phone network can also use timing: if you stop dialing, the number ends. A stream of bits has no pauses. The code alone must mark where each codeword ends.
- In the budget picture, part of the budget can stay unclaimed. Code D in the figure leaves 0.125 of it unused. For a prior that is allowed: the weights then add up to less than 1, and the bound only needs "at most 1". Unused budget is wasted, not forbidden.
- Country codes were handed out for a known list of countries. Our code must be fixed before training, and it must cover every model we might possibly end up with.
Precise definition¶
Everything in this section is MY EXPLANATION (standard definitions from information theory) unless tagged.
Strings¶
- An alphabet is a finite set of symbols. In this chapter it is always the binary alphabet \(\{0, 1\}\).
- A binary string is a finite sequence of 0s and 1s, such as 0110. The empty string, with no symbols at all, also counts.
- The length of a string \(s\), written \(|s|\), is the number of symbols in it. For example, \(|0110| = 4\). There are exactly \(2^\ell\) binary strings of length \(\ell\), because each of the \(\ell\) positions has 2 choices.
- The concatenation \(st\) of two strings is \(s\) followed by \(t\). Its length is \(|s| + |t|\).
- A string \(s\) is a prefix of a string \(t\) if \(t\) begins with \(s\), that is, if \(t = su\) for some string \(u\). For example, 01 is a prefix of 0110. Every string counts as a prefix of itself.
Codes¶
- A code is a fixed rule \(E\) that gives every object \(x\) of some set a binary string \(E(x)\). Different objects get different strings. The objects can be letters, whole numbers, or trained models.
- The string \(E(x)\) is the codeword of \(x\).
- The code length of \(x\) is \(\ell(x) = |E(x)|\), measured in bits.
- A code is uniquely decodable if every concatenation of codewords \(E(x_1)E(x_2)\cdots E(x_k)\) can be split back into codewords in only one way.
- A code is a prefix-free code if no codeword is a prefix of a different codeword. Prefix-free codes are also called instantaneous (the decoder can name each object the moment its last bit arrives) and self-delimiting (each codeword marks its own end).
Every prefix-free code is uniquely decodable (proof in the first Going-deeper block). The reverse is false. The code \(\{x{:}\ 0,\ y{:}\ 01\}\) is uniquely decodable but not prefix-free. After reading a 0, its decoder must wait for the next bit before it knows whether it saw \(x\) or the start of \(y\).
The Kraft inequality and its two companions¶
Kraft inequality. If a code is prefix-free, its code lengths satisfy
The sum runs over all objects \(x\) that have a codeword. There may be finitely many or infinitely many of them. The left-hand side is called the Kraft sum of the code.
Converse of the Kraft inequality. If whole numbers \(\ell_1, \ell_2, \ldots \ge 1\) satisfy \(\sum_i 2^{-\ell_i} \le 1\), then there is a prefix-free code whose codewords have exactly these lengths. A recipe that builds one, the canonical code, is in the Going-deeper section.
McMillan's theorem. The Kraft inequality holds for every uniquely decodable code, not only for prefix-free ones. Together with the converse, this means that giving up prefix-freeness (while keeping unique decodability) never buys shorter codewords.
From a code to a prior¶
Code → prior. Take a prefix-free code \(E\) on the set of hypotheses, fixed before any data are seen. Define
Each weight is positive, and by the Kraft inequality the weights add up to at most 1. So \(P\) is a legal prior. Its complexity term is
In words: the code length of \(h\) in bits equals the surprisal of \(h\) under this prior (Chapter 3). Codes and priors are two views of the same object.
If the Kraft sum \(Z\) is below 1, the weights add up to less than 1. That is allowed; such weights are sometimes called a sub-probability. One may also divide by \(Z\): the prior \(P(h) = 2^{-\ell(h)}/Z\) has every weight larger and a total of exactly 1.
PAPER App. C, p. 15 The paper's appendix writes its prior in this form, \(P(h) = 2^{-K(h)}/Z\), with the prefix Kolmogorov complexity \(K(h)\) in place of a code length.
MY EXPLANATION \(K(h)\) is the length of the shortest self-delimiting program that prints \(h\); Chapter 13 defines it properly. The word "prefix" in its name is this chapter's prefix-free property. The main text of §4.1 writes the prior as \(P(h) \le 2^{-K(h|\mathcal A)}\), an inequality that points the wrong way for what follows (erratum E01, discussed in Chapter 13).
The code must be fixed in advance. The prior must not depend on the training data, so the code must not either. In the paper's setting, the code consists of the decompression program plus everything it is allowed to know: the architecture (the model's blueprint), the random seeds that regenerate the starting weights, the rounding scheme for the weights (quantization, Chapter 21) and the list of hyperparameter values that will be tried. All of these are fixed before training. Any fixed code gives a valid prior. It does not have to be the best code; a better code only makes the bound tighter.
Making any message self-delimiting¶
A compressor produces a string of \(C\) bits, and \(C\) changes from model to model. The set of all possible outputs is usually not prefix-free: nothing stops a compressor from producing both 0 and 01. The standard fix is to send the length first, written in a prefix-free code for whole numbers. Here are three such codes.
- Unary code. The number \(n \ge 1\) becomes \(n-1\) zeros followed by a 1. Example: unary(5) = 00001. Its length is \(n\) bits, far too long for big numbers.
- Elias gamma code. Write \(n\) in binary. It starts with a 1 and has \(\lfloor \log_2 n \rfloor + 1\) digits. Put \(\lfloor \log_2 n\rfloor\) zeros in front. The length is \(2\lfloor \log_2 n \rfloor + 1\) bits. Example: 13 is 1101 in binary (4 digits), so its codeword is 000 followed by 1101, that is 0001101 (7 bits). To decode, count the zeros before the first 1 (here 3). Then read that 1 and 3 more bits.
- Elias delta code. Like gamma, but the number of binary digits is itself sent in gamma code instead of as a run of zeros. Its length is \(\lfloor\log_2 n\rfloor + 2\lfloor \log_2(\lfloor\log_2 n\rfloor + 1)\rfloor + 1\) bits, roughly \(\log_2 n + 2\log_2\log_2 n\). Example: delta(13) = 00100101 (8 bits). For large \(n\) it is shorter than gamma.
Self-delimiting message. Let \(m(h)\) be the compressor's output for model \(h\), with \(C(h) = |m(h)|\) bits. Send the Elias gamma codeword of \(C(h)\) first, then \(m(h)\) itself. Writing \(\gamma(n)\) for the gamma codeword of \(n\):
The decoder reads the header, learns \(C(h)\), and then reads exactly \(C(h)\) more bits. The code \(E\) is prefix-free whatever compressor produced \(m\) (proof in the Going-deeper section). By the code → prior rule, \(P(h) = 2^{-|E(h)|}\) is a legal prior.
The "+2 log2 C" term. The paper approximates the header by \(2\log_2 C\) bits, so the description of \(h\) costs \(C + 2\log_2 C\) bits. To convert bits to nats, multiply by \(\ln 2\) (Chapter 3):
where the last step uses \(\log_2 C = \ln C / \ln 2\). This is exactly the right-hand side of the paper's §4.1 bound, provided the paper's "log" means \(\ln\).
Paper erratum E02: which logarithm?
PAPER §4.1, p. 4; App. C, Algorithm 1 line 20, p. 15 Section 4.1 writes \(C(h)\log 2 + 2\log C(h)\). Algorithm 1 line 20 returns message_size plus 2 × log(message_size). Neither says which logarithm.
MY EXPLANATION The two lines need different bases. Section 4.1 is measured in nats (it feeds Eq. 1, whose logarithms are natural), so there "log" must be \(\ln\). Then \(C\ln 2 + 2\ln C\) is \((C + 2\log_2 C)\) bits converted to nats. Algorithm 1 adds the header to a message size counted in bits, so there "log" must be \(\log_2\).
SOURCE: authors' code, sublora_bounds_bound_utils.py The public code computes the message length plus
2 * np.log2(message_len) in bits, and multiplies the total by np.log(2) before it enters the bound. This
matches the reading above.
Paper erratum E12: the header term is approximate
PAPER §4.1, p. 4 The paper charges \(2\log C(h)\) for making the message self-delimiting, without saying which code achieves it.
MY EXPLANATION With the Elias gamma code the header costs \(2\lfloor\log_2 C\rfloor + 1\) bits. This differs from \(2\log_2 C\) by more than \(-1\) bit and at most \(+1\) bit (proof in the Going-deeper section). One bit is \(\ln 2 = 0.6931\) nats, so the effect on the bound is negligible. For a 20 KB model the exact header is 35 bits against the paper's 34.6439 bits, a difference of 0.2469 nats. The other half of E12 (a dropped constant in the step from \(K\) to \(C\)) is discussed in Chapters 13 and 14.
Addendum (now part of erratum E12). The paper's exact term can also be justified directly, with no rounding at all. Give each possible message length \(c \ge 2\) the weight \(1/c^2\) and share it equally among the \(2^c\) messages of that length. These weights add up to \(\sum_{c\ge2} 1/c^2 = 0.644934 < 1\), and the resulting prior has \(\ln\frac1{P(h)} = C\ln2 + 2\ln C\) exactly (see "weights on lengths" in the Going-deeper section). It needs \(C \ge 2\): if 1-bit messages were included, the sum would be \(\pi^2/6 = 1.644934 > 1\). Real models are many thousands of bits long, so this restriction never matters in practice.
SOURCE: Lotfi et al. 2022, §3, footnote 2 The predecessor paper describes its prior as using the length weight \(2^{-2\log_2 l(h)}\), which is this \(1/c^2\) weight.
Worked example with real numbers¶
Every number in this section is printed by ch12_kraft.py (full output at the end of the chapter). Everything here
is MY EXPLANATION.
Four small codes¶
| Code | Codewords | Prefix-free? | Uniquely decodable? | Kraft sum |
|---|---|---|---|---|
| A | a: 0, b: 10, c: 110, d: 111 | yes | yes | 1.000 |
| B | a: 0, b: 1, c: 01 | no | no | 1.250 |
| C | x: 0, y: 01 | no | yes | 0.750 |
| D | a: 0, b: 10, c: 110 | yes | yes | 0.875 |
The script decides the "uniquely decodable" column exactly, with the Sardinas–Patterson test (a standard algorithm that follows the "dangling" leftover bits when one codeword is a prefix of another).
Code A is prefix-free. Only the codeword 0 starts with 0. The codewords starting with 1 are 10, 110 and 111. The codeword 10 is not the start of 110 or 111, because their second bit is 1. And 110 and 111 differ in their last bit. The Kraft sum is \(\tfrac12 + \tfrac14 + \tfrac18 + \tfrac18 = 1\).
Decoding with A. Take the string 110010111. Read bits until they form a codeword. The bits 1, 1, 0 give 110, which is c. Next, 0 is a. Next, 1, 0 gives b. Last, 1, 1, 1 gives d. The message is c a b d, and the script confirms that there is no other way to split the string.
The prior from code A. \(P(a) = 0.5000\), \(P(b) = 0.2500\), \(P(c) = P(d) = 0.1250\). In nats, \(\ln\frac1{P}\) is 0.6931, 1.3863, 2.0794 and 2.0794. Each is the code length times \(\ln 2\).
Code B breaks. The codeword 0 is a prefix of 01. A received 01 could mean "a, then b" or it could mean "c". The Kraft sum is \(\tfrac12 + \tfrac12 + \tfrac14 = 1.25\). Turning B into weights \(P = 2^{-\text{length}}\) would hand out 1.25 units of probability, which no prior may do.
Code C is the in-between case. It is not prefix-free, yet it is uniquely decodable: every 1 must be the end of a \(y\). Its Kraft sum is 0.75, below 1, as McMillan's theorem demands.
Building a code from a list of lengths¶
The canonical construction (proved in the Going-deeper section) turns a list of lengths into codewords:
| Lengths | Kraft sum | Codewords |
|---|---|---|
| 1, 2, 3, 3 | 1.0000 | 0, 10, 110, 111 (this is code A) |
| 2, 3, 3, 5, 5, 6 (drawn at random) | 0.5781 | 00, 010, 011, 10000, 10001, 100100 |
| 1, 2, 2, 3 | 1.1250 | 0, 10, 11, then the construction fails |
For the lengths 1, 2, 2, 3 the fourth codeword would need the value 8 written with 3 bits, but 3 bits reach only 7. No cleverness can rescue it. The Kraft sum is above 1, so by the Kraft inequality no prefix-free code with these lengths exists.
The coin-flip picture, simulated¶
The script flips 3 fair coins, 100,000 times (seed 0), and records which codeword of code D each run begins with.
| Run begins with | Simulated fraction | Exact share |
|---|---|---|
| 0 | 0.5019 | 0.5000 |
| 10 | 0.2490 | 0.2500 |
| 110 | 0.1259 | 0.1250 |
| no codeword | 0.1231 | 0.1250 |
No run began with two different codewords, so the events never overlap. The last row is the unused budget.
Elias gamma in action¶
The gamma codeword of 13 is 0001101 (7 bits). The script then writes 10,000 random whole numbers between 1 and \(2^{31}-1\) back to back, with no separators, into one stream of 309,782 bits. Reading the stream with the decoding rule gives back every number exactly. That is what "self-delimiting" buys.
It also sends two messages, of 37 and 1000 bits, each as gamma(length) followed by the message, back to back (1067 bits in all). Both come back exactly.
A 20 KB model¶
Use the 8,192-bit kilobyte from Chapter 3. A model that compresses to 20 KB has:
- \(C = 20 \times 8192 = 163{,}840\) bits;
- \(\lfloor \log_2 C\rfloor = 17\), because \(2^{17} = 131{,}072 \le C < 2^{18} = 262{,}144\);
- an Elias gamma header of \(2 \times 17 + 1 = 35\) bits, giving a self-delimiting description of 163,875 bits. The header is 0.0214 % of the message;
- a header term in the paper's formula of \(2\log_2 C = 34.6439\) bits.
In nats, \(C\ln 2 = 113{,}565.23\) and \(2\ln C = 24.0133\). So the paper's formula gives
With the exact gamma header, \((C + 35)\ln 2 = 113{,}589.49\) nats, larger by 0.2469 nats. With an Elias delta header (26 bits) it would be 113,583.26 nats. The three differ by a few nats out of more than 113,000. The cost lives in the message, not in the header.
Header cost across model sizes¶
Here 1 MB means 1024 KB.
| Model size | \(C\) (bits) | Elias gamma header (bits) | Paper's \(2\log_2 C\) (bits) | Gamma minus paper (bits) | Elias delta header (bits) |
|---|---|---|---|---|---|
| 1 KB | 8,192 | 27 | 26.0000 | +1.0000 | 20 |
| 10 KB | 81,920 | 33 | 32.6439 | +0.3561 | 25 |
| 20 KB | 163,840 | 35 | 34.6439 | +0.3561 | 26 |
| 100 KB | 819,200 | 39 | 39.2877 | −0.2877 | 28 |
| 1 MB | 8,388,608 | 47 | 46.0000 | +1.0000 | 32 |
| 10 MB | 83,886,080 | 53 | 52.6439 | +0.3561 | 35 |
| 100 MB | 838,860,800 | 59 | 59.2877 | −0.2877 | 38 |
The gamma header and the paper's term never differ by more than 1 bit. The full +1 bit occurs at sizes that are exact powers of two (1 KB and 1 MB here). Even a 100 MB model needs a header of under 60 bits.
Going deeper¶
All proofs in this section are MY EXPLANATION (standard results, written out in full) unless tagged. The blocks are ordered so that each one uses only the blocks before it.
Going deeper: prefix-free codes decode uniquely and instantly
Lemma (two prefixes of one string). If \(s\) and \(s'\) are both prefixes of the same string \(t\) and \(|s| \le |s'|\), then \(s\) is a prefix of \(s'\). If moreover \(|s| = |s'|\), then \(s = s'\).
Proof. \(s\) is the first \(|s|\) symbols of \(t\), and \(s'\) is the first \(|s'|\) symbols of \(t\). So the first \(|s|\) symbols of \(s'\) are the first \(|s|\) symbols of \(t\), which is \(s\). If the lengths are equal, \(s\) is all of \(s'\). ∎
Claim. A prefix-free code is uniquely decodable.
Proof. First, if the code has at least two codewords, none of them is empty: the empty string is a prefix of every string, which prefix-freeness forbids. (A code with a single object may use the empty codeword; then there is nothing to decode.)
Suppose a string \(t\) has two splits into codewords, \(t = E(x_1)E(x_2)\cdots E(x_k) = E(y_1)E(y_2)\cdots E(y_r)\). Both \(E(x_1)\) and \(E(y_1)\) are prefixes of \(t\). By the lemma, the shorter is a prefix of the longer. In a prefix-free code, one codeword can be a prefix of another only if they are the same codeword. So \(E(x_1) = E(y_1)\), and \(x_1 = y_1\) because different objects have different codewords.
Remove this codeword from the front of both splits and repeat the argument on what is left. If one split ran out before the other (say \(k < r\)), then after \(k\) steps the left side would be the empty string while the right side would still contain the non-empty codewords \(E(y_{k+1})\cdots E(y_r)\), which is impossible. So \(k = r\) and \(x_i = y_i\) for every \(i\). ∎
Instantaneous decoding. Read the bits one at a time into a buffer. As soon as the buffer equals a codeword, output its object and empty the buffer. This is correct. The true first codeword \(E(x_1)\) is a prefix of the stream, so the buffer equals \(E(x_1)\) once \(|E(x_1)|\) bits have been read. Could the buffer match some other codeword earlier? That codeword would be a proper prefix of \(E(x_1)\), which is forbidden. So the first match is always the right one, and no look-ahead is needed.
A uniquely decodable code that is not instantaneous. Code C \(= \{x{:}\ 0,\ y{:}\ 01\}\). Every 1 in a concatenation must be the second bit of a \(y\), so each split is forced and the code is uniquely decodable. But after reading a 0 the decoder cannot yet tell \(x\) from the start of \(y\); it has to look at the next bit.
Going deeper: proof of the Kraft inequality (coin flips)
Setting. Take a prefix-free code with finitely many codewords, and let \(\ell_{\max}\) be the longest codeword length. (Infinitely many codewords are handled at the end.)
The experiment. Flip a fair coin \(\ell_{\max}\) times, independently, and write 1 for heads and 0 for tails. The outcome is a string \(F\) of length \(\ell_{\max}\). What is random: the flips. What is fixed: the code. For each codeword \(s\) define the event
Step 1: each event has probability \(2^{-|s|}\). Each of the first \(|s|\) flips must equal one specified bit. Each such match has probability \(\tfrac12\), and the flips are independent, so
Step 2: the events are disjoint. Suppose two different codewords \(s \ne t\) had \(A_s\) and \(A_t\) happen together. Then \(s\) and \(t\) would both be prefixes of \(F\). By the lemma of the previous block, the shorter one would be a prefix of the longer one (and if they had equal length they would be equal, contradicting \(s \ne t\)). That contradicts prefix-freeness. So no outcome lies in two of the events.
Step 3: add up. For disjoint events, the probability of "one of them happens" is the sum of their probabilities (additivity, Chapter 1), and any probability is at most 1:
This is the Kraft inequality. ∎
The unused budget. The gap \(1 - \sum_s 2^{-|s|}\) is the probability that the flips begin with no codeword at all. For code D it is 0.1250; the simulation found 0.1231.
Infinitely many codewords. Any finite part of a prefix-free code is still prefix-free, so the Kraft sum of every finite part is at most 1. An infinite sum of positive terms is the limit of its finite partial sums. Every partial sum is at most 1, so the limit is at most 1 too. ∎
Going deeper: the same proof as counting leaves of a tree
Draw all binary strings of length at most \(\ell_{\max}\) as a tree: the root is the empty string, and each node has a child for "append 0" and a child for "append 1". The strings of length exactly \(\ell_{\max}\) are the \(2^{\ell_{\max}}\) leaves on the bottom row.
A codeword \(s\) of length \(\ell\) sits at depth \(\ell\). It is a prefix of exactly \(2^{\ell_{\max} - \ell}\) leaves, because the remaining \(\ell_{\max} - \ell\) positions are free. In a prefix-free code, no leaf lies below two codewords (that would make one codeword a prefix of the other, by the lemma). So the sets of leaves below different codewords do not overlap, and together they contain at most all the leaves:
Dividing both sides by \(2^{\ell_{\max}}\) gives the Kraft inequality. ∎
This is the coin-flip proof with counting in place of probability: each leaf is one equally likely outcome of \(\ell_{\max}\) flips. In the first figure, the slice of \([0,1)\) under each codeword is exactly its share of leaves.
Going deeper: the converse of Kraft (the canonical code)
Theorem. Let \(\ell_1 \le \ell_2 \le \cdots \le \ell_n\) be whole numbers \(\ge 1\), sorted, with \(\sum_{i=1}^n 2^{-\ell_i} \le 1\). Then there are binary strings \(c_1, \ldots, c_n\) with \(|c_i| = \ell_i\), none of which is a prefix of another.
Construction. Let \(S_i\) be the sum of the shares of all earlier lengths,
let \(k_i = S_i \cdot 2^{\ell_i}\), and let \(c_i\) be \(k_i\) written in binary with exactly \(\ell_i\) digits (leading zeros allowed).
Step 1: \(k_i\) is a whole number. For \(j < i\) we have \(\ell_j \le \ell_i\), so each term \(2^{-\ell_j}\cdot 2^{\ell_i} = 2^{\ell_i - \ell_j}\) is a whole number, and \(k_i\) is a sum of whole numbers.
Step 2: \(k_i\) fits in \(\ell_i\) digits. This is the one place where the Kraft condition is used:
Multiplying by \(2^{\ell_i}\) gives \(k_i + 1 \le 2^{\ell_i}\), so \(0 \le k_i \le 2^{\ell_i} - 1\), the range of an \(\ell_i\)-digit binary number.
Step 3: strings as intervals. For a string \(c\) of length \(\ell\) whose value as a binary number is \(k\), define the interval \(I(c) = [\,k\,2^{-\ell},\ (k+1)\,2^{-\ell}\,)\), a piece of \([0,1)\) of width \(2^{-\ell}\). Key fact: if \(c\) is a prefix of \(c'\), then \(I(c') \subseteq I(c)\). To see this, write \(c' = cu\) with \(|u| = \ell' - \ell\). The value of \(c'\) is \(k\,2^{\ell'-\ell} + v\), where \(v\) is the value of \(u\) and \(0 \le v \le 2^{\ell'-\ell} - 1\). Dividing by \(2^{\ell'}\), the left end of \(I(c')\) is \(k\,2^{-\ell} + v\,2^{-\ell'} \ge k\,2^{-\ell}\), and the right end is \(k\,2^{-\ell} + (v+1)\,2^{-\ell'} \le k\,2^{-\ell} + 2^{\ell'-\ell}\,2^{-\ell'} = (k+1)\,2^{-\ell}\).
Step 4: the intervals of the code do not overlap. By construction \(I(c_i) = [\,S_i,\ S_i + 2^{-\ell_i}\,) = [\,S_i,\ S_{i+1}\,)\), where \(S_{n+1}\) is the full sum. The intervals are laid end to end along \([0,1)\), each one starting where the previous one stopped.
Step 5: the code is prefix-free. Suppose \(c_i\) were a prefix of \(c_j\) for some \(i \ne j\). By Step 3, \(I(c_j) \subseteq I(c_i)\). Since \(I(c_j)\) has positive width, \(I(c_i)\) and \(I(c_j)\) would overlap, contradicting Step 4. ∎
The integer recursion used by the script. From \(S_{i+1} = S_i + 2^{-\ell_i} = (k_i + 1)\,2^{-\ell_i}\), multiplying by \(2^{\ell_{i+1}}\) gives
For the lengths 1, 2, 2, 3 this gives \(k = 0, 2, 3\) (codewords 0, 10, 11) and then \(k_4 = (3+1)\cdot 2 = 8\), which does not fit in 3 bits. That is Step 2 failing, as it must when the Kraft sum (here 1.1250) exceeds 1.
Infinitely many lengths. At most \(2^\ell\) of the lengths can equal \(\ell\) (otherwise those alone would contribute more than 1 to the sum). So the lengths can still be sorted into an increasing list, and the construction runs forever, one codeword at a time; each step only uses the inequality of Step 2.
Going deeper: McMillan's theorem (uniquely decodable codes obey Kraft too)
Theorem. Let a uniquely decodable code have finitely many codewords \(c_1, \ldots, c_n\) with lengths \(\ell_1, \ldots, \ell_n\), and let \(\ell_{\max}\) be the largest length. Then \(S := \sum_{i=1}^n 2^{-\ell_i} \le 1\).
Proof. Fix a whole number \(k \ge 1\) and multiply out the \(k\)-th power of \(S\):
The last sum runs over all \(n^k\) ordered lists \((i_1, \ldots, i_k)\), that is, over all sequences of \(k\) codewords. The exponent \(\ell_{i_1} + \cdots + \ell_{i_k}\) is the length of the concatenation \(c_{i_1} c_{i_2} \cdots c_{i_k}\). It lies between \(k\) (each codeword has at least 1 bit; an empty codeword would already break unique decodability, since it could be inserted anywhere) and \(k\ell_{\max}\).
Group the lists by this total length \(j\). Let \(N_k(j)\) be the number of lists of \(k\) codewords whose concatenation has length \(j\). Then
Now use unique decodability. Two different lists cannot produce the same string, because that string would then have two different splits. So the \(N_k(j)\) lists produce \(N_k(j)\) different strings of length \(j\). There are only \(2^j\) strings of length \(j\), hence \(N_k(j) \le 2^j\), and
So \(S \le (k\ell_{\max})^{1/k}\) for every \(k\). Take \(\ln\) of both sides: \(\ln S \le \ln(k\ell_{\max})/k\). To see that the right side goes to 0, use \(\ln x \le x - 1 < x\) (Chapter 3) with \(x = \sqrt{k\ell_{\max}}\):
Hence \(\ln S \le 0\), that is, \(S \le 1\). ∎
Why a Kraft sum above 1 is fatal. If \(S > 1\), then \(S^k\) grows exponentially in \(k\) while \(k\ell_{\max}\) grows only linearly, so the inequality must fail for some \(k\). For code B (\(S = 1.25\), \(\ell_{\max} = 2\)) the script finds the first failure at \(k = 16\): \(S^{16} = 35.53 > 32\). So B cannot be uniquely decodable, which matches the explicit ambiguity of the string 01.
Infinitely many codewords. Any finite part of a uniquely decodable code is uniquely decodable, so every partial Kraft sum is at most 1, and so is their limit.
Consequence. Given any uniquely decodable code, its lengths satisfy Kraft (McMillan), so the canonical construction builds a prefix-free code with the same lengths. Nothing is lost by insisting on prefix-free codes.
Going deeper: Elias gamma is prefix-free, wastes nothing, and costs 2 log2 n plus or minus 1 bit
Encoding. For \(n \ge 1\) let \(N = \lfloor \log_2 n\rfloor\), so that \(2^N \le n < 2^{N+1}\). Then \(n\) in binary has exactly \(N+1\) digits and its first digit is 1. The codeword is \(N\) zeros followed by these \(N+1\) digits, a total of \(2N + 1\) bits.
Decoding. Count the zeros before the first 1; that count is \(N\). The 1 and the next \(N\) bits are \(n\) in binary.
Prefix-free. Suppose \(\gamma(n)\) is a prefix of \(\gamma(n')\). The string \(\gamma(n)\) begins with exactly \(N\) zeros followed by a 1. Since it is a prefix of \(\gamma(n')\), the string \(\gamma(n')\) also begins with exactly \(N\) zeros followed by a 1, so \(N' = N\). Then both codewords have length \(2N+1\), and a prefix of equal length is the whole string (lemma of the first block). So \(\gamma(n) = \gamma(n')\) and \(n = n'\). ∎
Kraft sum exactly 1. For each \(N \ge 0\) there are \(2^N\) numbers with \(\lfloor\log_2 n\rfloor = N\) (namely \(2^N, \ldots, 2^{N+1} - 1\)), each with a codeword of \(2N+1\) bits. So
No code space is wasted. The script's partial sum over \(n = 1, \ldots, 2^{20}-1\) is \(1 - 2^{-20} = 0.99999905\).
Comparison with the paper's \(2\log_2 n\). From \(N \le \log_2 n < N + 1\) we get \(2\log_2 n - 2 < 2N \le 2\log_2 n\), and adding 1 throughout:
So the gamma length differs from \(2\log_2 n\) by more than \(-1\) and at most \(+1\) bit, with \(+1\) exactly at powers of two. Over its 10,000 random integers the script finds differences from \(-0.9995\) to \(+1.0000\) bits.
The prior hidden inside. As a prior on whole numbers, gamma gives \(P(n) = 2^{-(2\lfloor\log_2 n\rfloor+1)}\). The display above turns into \(\tfrac{1}{2n^2} \le P(n) < \tfrac{2}{n^2}\): a weight that falls off like \(1/n^2\).
Elias delta, for comparison. Delta sends the digit count \(N+1\) in gamma code, which costs \(2\lfloor\log_2(N+1)\rfloor + 1\) bits, and then the \(N\) digits of \(n\) after the leading 1. It is prefix-free by the same argument (the gamma part fixes \(N\), and then the length is known). Its cost grows like \(\log_2 n + 2\log_2\log_2 n\), so for a 20 KB message the delta header is 26 bits instead of 35.
Going deeper: a length header turns any compressor into a valid prior
Setting. The compressor (and its decompressor) is fixed before the data. It maps each hypothesis \(h\) to a message \(m(h)\) of \(C(h) \ge 1\) bits, and different hypotheses get different messages (the decompressor recovers \(h\)). The set of messages need not be prefix-free. Define \(E(h) = \gamma(C(h))\, m(h)\).
Claim 1: \(E\) is prefix-free. Suppose \(E(h)\) is a prefix of \(E(h')\). The header \(\gamma(C(h))\) is a prefix of \(E(h)\), hence of \(E(h')\); and \(\gamma(C(h'))\) is a prefix of \(E(h')\) too. By the lemma, the shorter header is a prefix of the longer one, and since gamma is prefix-free the two headers are equal: \(C(h) = C(h')\). Then \(E(h)\) and \(E(h')\) have the same length, so the prefix is the whole string: \(E(h) = E(h')\), hence \(m(h) = m(h')\) and \(h = h'\). ∎
Claim 2: the weights \(2^{-|E(h)|}\) add up to at most 1. This follows from Claim 1 and Kraft, but a direct count shows where the header's budget goes. Group the hypotheses by message length \(c\). At most \(2^c\) hypotheses have \(C(h) = c\), because their messages are different strings of length \(c\). Write \(g(c) = 2\lfloor\log_2 c\rfloor + 1\) for the header length. Then
The message bits pay for choosing one message among the \(2^c\) of its length. The header bits pay for choosing the length. Without the header, the last sum would be \(\sum_c 1\), which is how the script's raw total reached 20 for lengths 1 to 20. With the header, the same 20 lengths have total weight 485/512 = 0.947265625.
What the decoder must know. Everything that is not in \(E(h)\): the decompression program, the architecture, the random seeds and the hyperparameter grid. All of these are fixed in advance, so they are part of the code, not of the message. This is what the paper means by giving the architecture "as input" (\(K(h|\mathcal A)\) in §4.1; Chapter 13).
Going deeper: weights on lengths, and the paper's exact 2 ln C
A prior does not have to come from a code with whole-number lengths. Here is a general recipe that contains the header construction as a special case.
Recipe. Fix, before the data, weights \(Q(c) \ge 0\) on the possible message lengths \(c = 1, 2, 3, \ldots\) with \(\sum_c Q(c) \le 1\). With the compressor as in the previous block, set
Claim: \(\sum_h P(h) \le 1\). Exactly as in Claim 2 of the previous block, \(\sum_h P(h) \le \sum_c Q(c)\, 2^{-c}\, 2^{c} = \sum_c Q(c) \le 1\). The complexity term is
Three choices of Q.
- \(Q(c) = 2^{-(2\lfloor\log_2 c\rfloor + 1)}\): this is the Elias gamma header, with \(\sum_c Q(c) = 1\).
- \(Q(c) = 1/c^2\) for \(c \ge 2\) and \(Q(1) = 0\). Then \(\ln\frac{1}{Q(C)} = 2\ln C\) and \(\ln\frac{1}{P(h)} = C\ln 2 + 2\ln C\), exactly the paper's formula. It remains to check \(\sum_{c\ge2} 1/c^2 \le 1\). For \(c \ge 2\), \(\frac{1}{c^2} < \frac{1}{c(c-1)} = \frac{1}{c-1} - \frac{1}{c}\), so the partial sums telescope: \(\sum_{c=2}^{M} \frac{1}{c^2} < 1 - \frac{1}{M} < 1\). (The exact value is \(\pi^2/6 - 1 = 0.644934\), a classical result of Euler that we do not need.) Including \(c = 1\) would add 1 and give \(\pi^2/6 = 1.644934 > 1\), which is why 1-bit messages get weight 0.
- \(Q\) from the Elias delta code: a header of about \(\log_2 c + 2\log_2\log_2 c\) bits. For the 20 KB model, \(\ln\frac1{P(h)}\) becomes 113,583.26 nats instead of 113,589.49 with gamma.
SOURCE: Lotfi et al. 2022, §3, footnote 2 The predecessor paper describes its universal prior as using the length weight \(2^{-2\log_2 l(h)}\), where \(l(h)\) is the program length without the delimiter. That is choice 2.
What this shows about E12. The paper's \(2\ln C(h)\) is not merely an approximation of the gamma header. With choice 2 it is exact, provided \(C(h) \ge 2\). The only imperfection is that the length weights add up to 0.644934 rather than 1, so part of the budget is left unused. That makes the bound slightly looser than it could be, never invalid.
Going deeper: joining codes (hyperparameter bits plus header plus message)
Lemma. If \(E_1\) and \(E_2\) are prefix-free codes, then the joined code \(E(x, y) = E_1(x)\,E_2(y)\) on pairs is prefix-free, with length \(\ell_1(x) + \ell_2(y)\).
Proof. Suppose \(E_1(x)E_2(y)\) is a prefix of \(E_1(x')E_2(y')\). Then \(E_1(x)\) and \(E_1(x')\) are both prefixes of the longer string, so by the lemma of the first block the shorter is a prefix of the longer; prefix-freeness gives \(E_1(x) = E_1(x')\) and \(x = x'\). Remove this common front part from both strings: \(E_2(y)\) is a prefix of \(E_2(y')\), so \(y = y'\). ∎
Because lengths add, the weights multiply: \(2^{-(\ell_1 + \ell_2)} = 2^{-\ell_1}\cdot 2^{-\ell_2}\). Complexity terms in nats add: \(\ln\frac{1}{P(x,y)} = (\ell_1(x) + \ell_2(y))\ln 2\).
Fixed-length codes are prefix-free. Give each of \(N\) objects a different string of \(\lceil\log_2 N\rceil\) bits (Chapter 3). Two different strings of the same length cannot be prefixes of each other, so the code is prefix-free. Its Kraft sum is \(N\cdot 2^{-\lceil\log_2 N\rceil} \le 1\). As a prior, one can even use the exact weight \(1/N\) for each object, which costs \(\log_2 N\) bits, not necessarily a whole number.
PAPER App. C, p. 15 The paper extends the hypothesis to include its hyperparameters, \(h = (\theta, d, r)\). It pays \(\log_2 N\) bits for a hyperparameter chosen from \(N\) values fixed in advance, and notes that this is the same as paying for a union bound over the choices.
MY EXPLANATION In code terms the full description is: the index of the hyperparameter setting (a fixed-length code), then the length header, then the message. By the joining lemma this is prefix-free, and the bit counts of the three parts add.
PAPER App. C, Algorithm 1 lines 19–20, p. 15 The pseudo-code adds the hyperparameter bits to the message size first and then adds the header term computed from that total. SOURCE: authors' code, sublora_sublora_pipeline.py The public code adds the header to the arithmetic-coded message length first and adds the hyperparameter bits afterwards. MY EXPLANATION Either order describes a code fixed in advance, so both are valid; for messages of thousands of bits the two totals differ by a tiny fraction of a bit.
Going deeper: why the code must be fixed before the data
A cheating code. Train a model \(h^\ast\) first. Then define a new code: \(E'(h^\ast) = 0\), and \(E'(h) = 1\,E(h)\) for every other hypothesis \(h\), where \(E\) is any prefix-free code. \(E'\) is prefix-free (0 is not a prefix of anything that starts with 1, and the strings \(1E(h)\) inherit prefix-freeness from \(E\)). Its Kraft sum is \(\tfrac12 + \tfrac12\sum_{h \ne h^\ast} 2^{-\ell(h)} \le 1\). Yet it gives \(\ln\frac{1}{P(h^\ast)} = \ln 2 = 0.6931\) nats, whatever \(h^\ast\) is: a billion-parameter memorizer would pay almost nothing.
What went wrong. The bound of Chapter 11 controls a probability over the random draw of the training data, with the prior held fixed. Its proof adds up failure probabilities \(P(h)\,\delta\) over all hypotheses. If the prior itself changes with the data, each dataset gets its own prior, and that sum no longer describes one fixed bet. The guarantee is lost.
What is allowed. The code is fixed first. Which hypothesis training then produces depends on the data, and that is fine: the hypothesis is random, but the length its codeword would have was decided in advance for every hypothesis. Information independent of the training data (the architecture, the seeds, the hyperparameter grid) may be built into the decoder. A code built after looking at the training data may not.
Common misconceptions¶
Everything in this section is MY EXPLANATION.
- Misconception: "Any compressor gives a prior: set \(P(h) = 2^{-C(h)}\)." — Actually: the outputs of an ordinary compressor are not prefix-free, and their weights can add up to far more than 1 (20 for all strings of 1 to 20 bits). A length header, or a weight on lengths, is needed. It costs about \(2\log_2 C\) bits.
- Misconception: "The \(2\log_2 C\) header term is a large penalty." — Actually: for a 20 KB model it is 35 bits on top of 163,840, which is 0.0214 % of the message. The bound is dominated by \(C\) itself.
- Misconception: "A valid prior must add up to exactly 1, so the Kraft sum must equal 1." — Actually: the bound only needs a total of at most 1. Unused code space makes the bound slightly looser, never invalid.
- Misconception: "The bound needs the best possible code, the true Kolmogorov complexity." — Actually: any code fixed before seeing the data works. A better code only gives a tighter bound. That is why the incomputable \(K\) never has to be computed.
- Misconception: "We may choose the code after training, so that the trained model gets a short codeword." — Actually: a code chosen after seeing the data makes the prior data-dependent, and the bound's proof breaks (last Going-deeper block).
- Misconception: "A uniquely decodable code that is not prefix-free could have shorter codewords." — Actually: McMillan's theorem says it obeys the same Kraft inequality, and the converse of Kraft then gives a prefix-free code with exactly the same lengths.
Self-test¶
Q1. (numeric) Take the lengths 1, 2, 3, 4, 4. Compute the Kraft sum, build a prefix-free code with these lengths, and decide whether a prefix-free code could have one more codeword, of any length.
Answer
The Kraft sum is \(\tfrac12 + \tfrac14 + \tfrac18 + \tfrac1{16} + \tfrac1{16} = 1\) (the script prints 1.0000). The canonical construction gives 0, 10, 110, 1110, 1111 (script block [3]). No extra codeword is possible: any codeword of length \(\ell\) would add \(2^{-\ell} > 0\) to a sum that is already 1, and the Kraft inequality forbids a total above 1. By McMillan's theorem, not even a uniquely decodable code could have the extra codeword.
Q2. (numeric) Decode the Elias gamma stream 00001010000011011. How many bits does each codeword use?
Answer
Count zeros: there are 4 before the first 1, so read that 1 and 4 more bits: 10100, which is 20. That codeword is 000010100 (9 bits \(= 2\times4+1\)). Next, 3 zeros, then 1101, which is 13 (0001101, 7 bits). Last, no zeros, then 1, which is 1 (a single bit). The stream holds 20, 13, 1, with no separators needed (script block [6]).
Q3. (conceptual) A colleague says: "Our model zips to \(C\) bits, so we put \(P(h) = 2^{-C}\) into Eq. (1)." What is wrong, and what is the smallest fix? May the colleague also pick the zip settings after seeing which settings make this model smallest?
Answer
Zip outputs are not prefix-free. Over all possible outputs the weights \(2^{-C}\) can add up to far more than 1 (the script's example reaches 20), so they are not a prior, and the bound's prior-weighted union bound fails. The fix is to prepend a self-delimiting length header, \(P(h) = 2^{-(C + 2\lfloor\log_2 C\rfloor + 1)}\), or to use the length weight \(1/C^2\) (for \(C \ge 2\)), which gives exactly \(\ln\frac1{P(h)} = C\ln 2 + 2\ln C\). Either costs about \(2\log_2 C\) extra bits.
The settings may not be picked freely after the fact: that makes the code depend on the data. It is fine if the choice is paid for: fix a list of \(N\) candidate settings in advance and add \(\log_2 N\) bits for the index of the chosen one, as the paper does for hyperparameters (App. C).
Code for this chapter¶
Run it from the project root:
.venv/Scripts/python explainer/code/ch12_kraft.py
Source: ch12_kraft.py
"""Chapter 12 demo: codes, prefix-freeness and the Kraft inequality.
What this script reproduces or illustrates (all numbers quoted in Chapter 12 come from here):
1. Kraft sums (sum over codewords of 2^-length) of four small example codes; a code whose
Kraft sum exceeds 1 is ambiguous (checked with the Sardinas-Patterson test).
2. The coin-flip proof of the Kraft inequality, checked by simulation (seed 0).
3. The converse of Kraft: a canonical prefix-free code built from a list of lengths, and the
construction failing when the Kraft sum of the lengths exceeds 1.
4. McMillan's growth argument, numerically: S^k eventually exceeds k * l_max when S > 1.
5. Raw compressor outputs are NOT a valid prior (sum of 2^-length = 20 for all strings of
length 1..20); adding an Elias-gamma length header brings the sum below 1.
6. Elias gamma / delta encoders and decoders; 10,000 random integers concatenated in one bit
stream and decoded back exactly (self-delimiting), plus two self-delimiting "messages".
7. Paper section 4.1 / Algorithm 1 line 20: the header term 2 log2 C versus the exact Elias-gamma
cost 2 floor(log2 C) + 1 (erratum E12), for C = 1 KB ... 100 MB (1 KB = 8192 bits).
8. The 20 KB example: ln 1/P(h) = C ln 2 + 2 ln C (pacbound) and the identity
2 log2(C) ln 2 = 2 ln C (erratum E02).
9. The length prior Q(c) = 1/c^2 behind the paper's exact "2 log C" term: its sum over c >= 2 is
pi^2/6 - 1 < 1 (valid), over c >= 1 it is pi^2/6 > 1 (invalid).
Figures: docs/assets/fig/ch12_kraft_tree.png, docs/assets/fig/ch12_header.png
Output: code/outputs/ch12_kraft.txt
"""
from __future__ import annotations
import math
import sys
from fractions import Fraction
from pathlib import Path
import numpy as np
import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt # noqa: E402
HERE = Path(__file__).resolve().parent
sys.path.insert(0, str(HERE))
import pacbound as pb # noqa: E402
OUT_TXT = HERE / "outputs" / "ch12_kraft.txt"
FIG_DIR = HERE.parent / "docs" / "assets" / "fig"
OUT_TXT.parent.mkdir(parents=True, exist_ok=True)
FIG_DIR.mkdir(parents=True, exist_ok=True)
LINES: list[str] = []
def say(s: str = "") -> None:
print(s)
LINES.append(s)
# ---------------------------------------------------------------------------
# Basic code utilities (codewords are Python strings of '0'/'1')
# ---------------------------------------------------------------------------
def kraft_sum(words) -> Fraction:
"""Exact Kraft sum: sum of 2^-len(w) over the codewords (dimensionless)."""
return sum((Fraction(1, 2 ** len(w)) for w in words), Fraction(0))
def is_prefix_free(words) -> bool:
"""True if no codeword is a prefix of a different codeword (duplicates also fail)."""
for i, s in enumerate(words):
for j, t in enumerate(words):
if i != j and t.startswith(s):
return False
return True
def is_uniquely_decodable(words) -> bool:
"""Sardinas-Patterson test: an exact decision procedure for unique decodability."""
if len(set(words)) < len(words):
return False
code = set(words)
def dangling(A, B):
# nonempty w such that a + w = b for some a in A, b in B
return {b[len(a):] for a in A for b in B if len(b) > len(a) and b.startswith(a)}
S = dangling(code, code)
seen = set()
while S:
if S & code:
return False
key = frozenset(S)
if key in seen:
return True
seen.add(key)
S = dangling(S, code) | dangling(code, S)
return True
def all_parses(s: str, code: dict) -> list:
"""All ways to split bit string s into codewords; returns lists of symbols."""
if s == "":
return [[]]
out = []
for sym, w in code.items():
if s.startswith(w):
out += [[sym] + rest for rest in all_parses(s[len(w):], code)]
return out
def greedy_decode(s: str, code: dict) -> list:
"""Instantaneous decoding of a prefix-free code: emit a symbol as soon as the buffer is a codeword."""
inv = {w: sym for sym, w in code.items()}
out, buf = [], ""
for bit in s:
buf += bit
if buf in inv:
out.append(inv[buf])
buf = ""
assert buf == "", "leftover bits"
return out
def canonical_code(lengths):
"""Converse of Kraft: assign codewords to sorted lengths l_1 <= l_2 <= ... .
Codeword i is the l_i-bit binary form of k_i, with k_1 = 0 and k_{i+1} = (k_i + 1) * 2^(l_{i+1} - l_i).
Returns (words, None) on success or (words_so_far, (i, k, l)) if k_i does not fit in l_i bits."""
ls = sorted(lengths)
words, k = [], 0
for i, l in enumerate(ls):
if i > 0:
k = (k + 1) << (l - ls[i - 1])
if k >= 2 ** l:
return words, (i + 1, k, l)
words.append(format(k, f"0{l}b"))
return words, None
# ---------------------------------------------------------------------------
# Elias codes
# ---------------------------------------------------------------------------
def unary_encode(n: int) -> str:
"""Unary code of n >= 1: (n-1) zeros then a 1 (length n bits)."""
return "0" * (n - 1) + "1"
def gamma_encode(n: int) -> str:
"""Elias gamma of n >= 1: floor(log2 n) zeros, then n in binary (which starts with 1)."""
if n < 1:
raise ValueError("n must be >= 1")
b = bin(n)[2:]
return "0" * (len(b) - 1) + b
def gamma_decode_at(bits: str, pos: int):
"""Decode one Elias gamma codeword starting at bits[pos]; return (n, next position)."""
z = 0
while bits[pos + z] == "0":
z += 1
n = int(bits[pos + z: pos + 2 * z + 1], 2)
return n, pos + 2 * z + 1
def delta_encode(n: int) -> str:
"""Elias delta: gamma(number of binary digits of n), then the binary digits of n after the leading 1."""
b = bin(n)[2:]
return gamma_encode(len(b)) + b[1:]
def delta_decode_at(bits: str, pos: int):
nd, pos = gamma_decode_at(bits, pos)
n = int("1" + bits[pos: pos + nd - 1], 2)
return n, pos + nd - 1
def delta_length(n: int) -> int:
"""Length of Elias delta: floor(log2 n) + 2 floor(log2(floor(log2 n)+1)) + 1 bits."""
N = n.bit_length() - 1
return N + pb.elias_gamma_length(N + 1)
# ---------------------------------------------------------------------------
# Figures
# ---------------------------------------------------------------------------
BLUE, ORANGE, GREEN, PINK, YELLOW, SKY = "#0072B2", "#D55E00", "#009E73", "#CC79A7", "#E69F00", "#56B4E9"
SYM_COLORS = [BLUE, ORANGE, GREEN, PINK]
def draw_code_tree(ax, code: dict, title: str) -> None:
"""Binary code tree; each node's horizontal span equals its share of [0, 1)."""
words = list(code.values())
depth = max(len(w) for w in words)
inv = {w: s for s, w in code.items()}
prefixes = {w[:k] for w in words for k in range(len(w))} # internal nodes (incl. root '')
def xy(p):
k = len(p)
x = 0.5 if k == 0 else (int(p, 2) + 0.5) / 2 ** k
return x, -k
unused = []
for p in sorted(prefixes, key=len):
x0, y0 = xy(p)
for bit in "01":
c = p + bit
x1, y1 = xy(c)
is_node = c in prefixes or c in inv
ax.plot([x0, x1], [y0, y1], color="0.35" if is_node else "0.75",
lw=1.6 if is_node else 1.0, ls="-" if is_node else "--", zorder=1)
ax.text((x0 + x1) / 2 + (-0.025 if bit == "0" else 0.025), (y0 + y1) / 2 + 0.05, bit,
ha="center", va="center", fontsize=10, color="0.25")
if not is_node:
unused.append(c)
ax.scatter([x0], [y0], s=70, color="white", edgecolor="0.3", zorder=2)
for i, (sym, w) in enumerate(code.items()):
x, y = xy(w)
col = SYM_COLORS[i % len(SYM_COLORS)]
ax.scatter([x], [y], s=260, color=col, edgecolor="black", zorder=3)
ax.text(x, y, sym, ha="center", va="center", fontsize=11, color="white", weight="bold", zorder=4)
ax.text(x, y - 0.33, f'"{w}"', ha="center", va="top", fontsize=9.5)
for c in unused:
x, y = xy(c)
ax.scatter([x], [y], s=200, facecolor="white", edgecolor="0.6", ls="--", zorder=3)
ax.text(x, y - 0.33, f'"{c}"\nunused', ha="center", va="top", fontsize=8.5, color="0.4")
# interval bar: each codeword owns [k 2^-l, (k+1) 2^-l)
ybar = -(depth + 1.35)
for i, (sym, w) in enumerate(code.items()):
l = len(w)
a = int(w, 2) / 2 ** l
ax.add_patch(plt.Rectangle((a, ybar - 0.22), 2 ** -l, 0.44, facecolor=SYM_COLORS[i % 4],
edgecolor="black", alpha=0.85))
ax.text(a + 2 ** -l / 2, ybar, f"{sym}: 1/{2 ** l}", ha="center", va="center", fontsize=9,
color="white", weight="bold")
for c in unused:
l = len(c)
a = int(c, 2) / 2 ** l
ax.add_patch(plt.Rectangle((a, ybar - 0.22), 2 ** -l, 0.44, facecolor="white",
edgecolor="0.5", hatch="///"))
ks = kraft_sum(words)
ax.text(0.5, ybar - 0.55, f"Kraft sum = {float(ks):.3f} (shares of [0, 1) claimed by codewords)",
ha="center", va="top", fontsize=9.5)
ax.set_xlim(-0.02, 1.02)
ax.set_ylim(ybar - 1.0, 0.45)
ax.set_title(title, fontsize=11)
ax.axis("off")
# ---------------------------------------------------------------------------
# Main
# ---------------------------------------------------------------------------
def main() -> None:
rng = np.random.default_rng(0)
say("Chapter 12 demo: codes and the Kraft inequality (lengths in bits; Kraft sum = sum of 2^-length)")
# 1. Example codes --------------------------------------------------------
say("[1] Example codes")
A = {"a": "0", "b": "10", "c": "110", "d": "111"}
B = {"a": "0", "b": "1", "c": "01"}
Cc = {"x": "0", "y": "01"}
Dd = {"a": "0", "b": "10", "c": "110"}
say(f" {'code':<28} {'prefix-free':<12} {'uniq. decodable':<16} Kraft sum")
for name, code in [("A", A), ("B", B), ("C", Cc), ("D", Dd)]:
w = list(code.values())
desc = name + " {" + ", ".join(f"{s}:{c}" for s, c in code.items()) + "}"
say(f" {desc:<28} {str(is_prefix_free(w)):<12} {str(is_uniquely_decodable(w)):<16}"
f" {float(kraft_sum(w)):.3f}")
assert kraft_sum(A.values()) == 1 and kraft_sum(B.values()) == Fraction(5, 4)
assert kraft_sum(Cc.values()) == Fraction(3, 4) and kraft_sum(Dd.values()) == Fraction(7, 8)
p = all_parses("01", B)
say(f" code B: the string 01 splits as {[''.join(x) for x in p]} -> ambiguous")
msg = "110010111"
dec = greedy_decode(msg, A)
assert all_parses(msg, A) == [dec]
say(f" code A: 110010111 decodes (bit by bit, no look-ahead) to {' '.join(dec)}; number of parses = 1")
say(" prior from code A, P = 2^-length: " + " ".join(f"{s} {2.0 ** -len(c):.4f}" for s, c in A.items()))
say(" ln 1/P = length * ln 2 (nats): " + " ".join(f"{s} {len(c) * pb.LN2:.4f}" for s, c in A.items()))
# 2. Coin-flip proof check ---------------------------------------------------
n_runs = 100_000
flips = rng.integers(0, 2, size=(n_runs, 3))
runs = ["".join(map(str, r)) for r in flips]
counts = {c: 0 for c in Dd.values()}
max_hits = 0
for r in runs:
hits = [c for c in Dd.values() if r.startswith(c)]
max_hits = max(max_hits, len(hits))
for c in hits:
counts[c] += 1
none = n_runs - sum(counts.values())
say(f"[2] Coin-flip check of Kraft, code D, {n_runs:,} runs of 3 fair flips (seed 0)")
say(" fraction of runs starting with " + " ".join(
f"{c}: {counts[c] / n_runs:.4f} ({2.0 ** -len(c):.4f})" for c in Dd.values())
+ " (exact)")
say(f" starting with no codeword: {none / n_runs:.4f} ({1 - float(kraft_sum(Dd.values())):.4f});"
f" most codewords matched by one run: {max_hits}")
assert max_hits == 1
# 3. Converse of Kraft: canonical construction -------------------------------
say("[3] Converse of Kraft: canonical prefix code from a list of lengths")
while True:
rl = sorted(int(x) for x in rng.integers(1, 7, size=6))
if kraft_sum(["0" * l for l in rl]) <= 1:
break
for ls in ([1, 2, 3, 3], [1, 2, 3, 4, 4], rl, [1, 2, 2, 3]):
ks = kraft_sum(["0" * l for l in ls])
words, fail = canonical_code(ls)
if fail is None:
assert is_prefix_free(words) and [len(w) for w in words] == sorted(ls)
say(f" lengths {str(ls):<19} sum {float(ks):.4f} -> {' '.join(words)} (prefix-free)")
else:
i, k, l = fail
say(f" lengths {str(ls):<19} sum {float(ks):.4f} -> {' '.join(words)} then FAILS:"
f" codeword {i} needs {k} in {l} bits (max {2 ** l - 1})")
assert ks > 1
# 4. McMillan, numerically ------------------------------------------------
S = kraft_sum(B.values())
lmax = max(len(w) for w in B.values())
k = 1
while S ** k <= k * lmax:
k += 1
say(f"[4] McMillan, code B (S = {float(S):.2f}, l_max = {lmax}): unique decodability needs S^k <= k*l_max"
f" for all k;")
say(f" first failure at k = {k}: S^k = {float(S ** k):.2f} > {k * lmax} -> B cannot be uniquely decodable")
# 5. Raw compressor outputs -----------------------------------------------
cmax = 20
raw = sum((2 ** c * Fraction(1, 2 ** c) for c in range(1, cmax + 1)), Fraction(0))
hdr = sum((2 ** c * Fraction(1, 2 ** (c + pb.elias_gamma_length(c))) for c in range(1, cmax + 1)), Fraction(0))
say(f"[5] All bit strings of length 1..{cmax} used as 'compressor outputs':")
say(f" sum of 2^-length = {float(raw):.6f}; with Elias-gamma length header = {float(hdr):.9f} (= {hdr})")
assert raw == cmax and hdr <= 1
# 6. Elias codes ------------------------------------------------------------
say("[6] Unary and Elias codes")
say(f" unary(5) = {unary_encode(5)}; gamma(13) = {gamma_encode(13)} ({len(gamma_encode(13))} bits);"
f" gamma(20) = {gamma_encode(20)} ({len(gamma_encode(20))} bits)")
say(f" delta(13) = {delta_encode(13)} ({len(delta_encode(13))} bits)")
q_stream = "00001010000011011" # self-test Q2
q_dec, pos = [], 0
while pos < len(q_stream):
start = pos
n, pos = gamma_decode_at(q_stream, pos)
q_dec.append(f"{q_stream[start:pos]} -> {n}")
say(f" self-test stream {q_stream} decodes as: " + ", ".join(q_dec))
assert gamma_encode(13) == "0001101"
top = 2 ** 20 - 1
gk = sum((Fraction(2 ** N, 2 ** (2 * N + 1)) for N in range(20)), Fraction(0))
say(f" Kraft sum of gamma over n = 1..2^20-1: {float(gk):.8f} (= 1 - 2^-20 = {1 - 2 ** -20:.8f})")
ks_ = rng.integers(0, 31, size=10_000)
ns = [int(2 ** int(e) + int(rng.integers(0, 2 ** int(e)))) for e in ks_]
stream = "".join(gamma_encode(n) for n in ns)
for n in ns[:2000]:
assert len(gamma_encode(n)) == pb.elias_gamma_length(n)
assert len(delta_encode(n)) == delta_length(n)
dec, pos = [], 0
while pos < len(stream):
n, pos = gamma_decode_at(stream, pos)
dec.append(n)
ok = dec == ns
dstream = "".join(delta_encode(n) for n in ns)
ddec, pos = [], 0
while pos < len(dstream):
n, pos = delta_decode_at(dstream, pos)
ddec.append(n)
assert ok and ddec == ns
diffs = [pb.elias_gamma_length(n) - 2 * math.log2(n) for n in ns]
say(f" round trip: {len(ns):,} random integers in 1..2^31-1 written back to back, no separators")
say(f" gamma stream {len(stream):,} bits, decoded exactly: {ok};"
f" delta stream {len(dstream):,} bits, decoded exactly: {ddec == ns}")
say(f" gamma length - 2 log2 n over these integers: min {min(diffs):+.4f}, max {max(diffs):+.4f} bits"
" (theory: in (-1, +1])")
assert -1 < min(diffs) and max(diffs) <= 1
m1 = "".join(map(str, rng.integers(0, 2, size=37)))
m2 = "".join(map(str, rng.integers(0, 2, size=1000)))
packed = gamma_encode(len(m1)) + m1 + gamma_encode(len(m2)) + m2
l1, pos = gamma_decode_at(packed, 0)
r1, pos = packed[pos:pos + l1], pos + l1
l2, pos = gamma_decode_at(packed, pos)
r2 = packed[pos:pos + l2]
say(f" messages of 37 and 1000 bits sent as gamma(length)+message, back to back ({len(packed)} bits):"
f" recovered: {r1 == m1 and r2 == m2}")
assert r1 == m1 and r2 == m2
# 7. Header cost table ------------------------------------------------------
KB = 8192 # bits [SOURCE: Lotfi et al. 2022, App. A]; 1 MB = 1024 KB here
sizes = [("1 KB", KB), ("10 KB", 10 * KB), ("20 KB", 20 * KB), ("100 KB", 100 * KB),
("1 MB", 1024 * KB), ("10 MB", 10240 * KB), ("100 MB", 102400 * KB)]
say("[7] Header that makes a C-bit message self-delimiting (1 KB = 8192 bits, 1 MB = 1024 KB)")
say(" gamma = 2 floor(log2 C) + 1 (exact Elias-gamma header); paper = 2 log2 C; units: bits")
say(f" {'size':>6} {'C':>13} {'gamma':>6} {'paper':>9} {'gamma-paper':>12} {'delta':>6} {'gamma/C':>9}")
for lab, C in sizes:
g = pb.elias_gamma_length(C)
p2 = 2 * math.log2(C)
say(f" {lab:>6} {C:>13,} {g:>6} {p2:>9.4f} {g - p2:>+12.4f} {delta_length(C):>6} {g / C:>9.2e}")
# 8. 20 KB worked example ---------------------------------------------------
C = 20 * KB
g = pb.elias_gamma_length(C)
p2 = 2 * math.log2(C)
nats_paper = pb.log_inv_prior_nats_from_bits(C) # (C + 2 log2 C) ln 2 = C ln 2 + 2 ln C
nats_gamma = (C + g) * pb.LN2
N = C.bit_length() - 1
say(f"[8] 20 KB model: C = 20 x 8192 = {C:,} bits; floor(log2 C) = {N} since 2^{N} = {2 ** N:,} <= C"
f" < 2^{N + 1} = {2 ** (N + 1):,}")
say(f" gamma header {g} bits -> self-delimiting description C + {g} = {C + g:,} bits"
f" (header = {100 * g / C:.4f} % of C)")
say(f" C ln 2 = {C * pb.LN2:,.2f} nats; 2 ln C = {2 * math.log(C):.4f} nats")
rows8 = [("paper's C ln 2 + 2 ln C", nats_paper, ""),
(f"exact gamma header (C + {g}) ln 2", nats_gamma, f" (difference {nats_gamma - nats_paper:.4f} nats)"),
(f"Elias-delta header (C + {delta_length(C)}) ln 2", (C + delta_length(C)) * pb.LN2, "")]
for lab, val, extra in rows8:
say(f" ln 1/P(h), {lab:<34} = {val:,.2f} nats{extra}")
test_C = [2, 3, 1000, C, 10 ** 9]
rel = max(abs(2 * math.log2(c) * pb.LN2 - 2 * math.log(c)) / (2 * math.log(c)) for c in test_C)
say(f" check 2 log2(C) ln 2 = 2 ln C for C in {test_C}: max relative error {rel:.1e}")
assert rel < 1e-12
assert abs(nats_paper - (C * pb.LN2 + 2 * math.log(C))) < 1e-6
# 9. Length prior 1/c^2 -------------------------------------------------------
part = math.fsum(1.0 / c ** 2 for c in range(2, 10 ** 6 + 1))
say(f"[9] Length prior Q(c) = 1/c^2: sum over c >= 2 = pi^2/6 - 1 = {math.pi ** 2 / 6 - 1:.6f}"
f" (partial sum to 10^6: {part:.6f})")
say(f" sum over c >= 1 = pi^2/6 = {math.pi ** 2 / 6:.6f} > 1 (so 1-bit messages must be excluded)")
assert part < 1 < math.pi ** 2 / 6
OUT_TXT.write_text("\n".join(LINES) + "\n", encoding="utf-8")
# Figures ---------------------------------------------------------------------
fig, axes = plt.subplots(1, 2, figsize=(11.5, 5.0))
draw_code_tree(axes[0], A, 'Code A = {a:"0", b:"10", c:"110", d:"111"}')
draw_code_tree(axes[1], Dd, 'Code D = {a:"0", b:"10", c:"110"}')
fig.suptitle(r"Each codeword of length $\ell$ owns a $2^{-\ell}$ share of [0, 1); "
"prefix-free means the shares never overlap", fontsize=11.5)
fig.tight_layout()
fig.savefig(FIG_DIR / "ch12_kraft_tree.png", dpi=130)
plt.close(fig)
cs = np.unique(np.round(np.logspace(np.log10(2), np.log10(2.0 ** 30), 6000)).astype(np.int64))
fig, ax = plt.subplots(figsize=(8.2, 4.6))
ax.plot(cs, [pb.elias_gamma_length(int(c)) for c in cs], color=BLUE, lw=1.8, drawstyle="steps-post",
label="Elias gamma header: 2 floor(log2 C) + 1")
ax.plot(cs, 2 * np.log2(cs), color=ORANGE, lw=1.6, ls="--", label="paper's term: 2 log2 C")
ax.plot(cs, [delta_length(int(c)) for c in cs], color=GREEN, lw=1.6, drawstyle="steps-post",
label="Elias delta header")
ax.scatter([C], [g], color="black", zorder=5)
ax.annotate(f"20 KB model: C = {C:,} bits\ngamma {g} bits, 2 log2 C = {p2:.2f} bits", (C, g),
xytext=(C * 0.02, g + 12), fontsize=9, arrowprops=dict(arrowstyle="->", color="0.3"))
ax.set_xscale("log")
ax.set_xlabel("compressed message length C (bits, log scale)")
ax.set_ylabel("length header (bits)")
ax.set_title("Cost of making a C-bit message self-delimiting")
ax.grid(alpha=0.3)
ax.legend(fontsize=9, loc="upper left")
fig.tight_layout()
fig.savefig(FIG_DIR / "ch12_header.png", dpi=130)
plt.close(fig)
if __name__ == "__main__":
main()
Output:
Chapter 12 demo: codes and the Kraft inequality (lengths in bits; Kraft sum = sum of 2^-length)
[1] Example codes
code prefix-free uniq. decodable Kraft sum
A {a:0, b:10, c:110, d:111} True True 1.000
B {a:0, b:1, c:01} False False 1.250
C {x:0, y:01} False True 0.750
D {a:0, b:10, c:110} True True 0.875
code B: the string 01 splits as ['ab', 'c'] -> ambiguous
code A: 110010111 decodes (bit by bit, no look-ahead) to c a b d; number of parses = 1
prior from code A, P = 2^-length: a 0.5000 b 0.2500 c 0.1250 d 0.1250
ln 1/P = length * ln 2 (nats): a 0.6931 b 1.3863 c 2.0794 d 2.0794
[2] Coin-flip check of Kraft, code D, 100,000 runs of 3 fair flips (seed 0)
fraction of runs starting with 0: 0.5019 (0.5000) 10: 0.2490 (0.2500) 110: 0.1259 (0.1250) (exact)
starting with no codeword: 0.1231 (0.1250); most codewords matched by one run: 1
[3] Converse of Kraft: canonical prefix code from a list of lengths
lengths [1, 2, 3, 3] sum 1.0000 -> 0 10 110 111 (prefix-free)
lengths [1, 2, 3, 4, 4] sum 1.0000 -> 0 10 110 1110 1111 (prefix-free)
lengths [2, 3, 3, 5, 5, 6] sum 0.5781 -> 00 010 011 10000 10001 100100 (prefix-free)
lengths [1, 2, 2, 3] sum 1.1250 -> 0 10 11 then FAILS: codeword 4 needs 8 in 3 bits (max 7)
[4] McMillan, code B (S = 1.25, l_max = 2): unique decodability needs S^k <= k*l_max for all k;
first failure at k = 16: S^k = 35.53 > 32 -> B cannot be uniquely decodable
[5] All bit strings of length 1..20 used as 'compressor outputs':
sum of 2^-length = 20.000000; with Elias-gamma length header = 0.947265625 (= 485/512)
[6] Unary and Elias codes
unary(5) = 00001; gamma(13) = 0001101 (7 bits); gamma(20) = 000010100 (9 bits)
delta(13) = 00100101 (8 bits)
self-test stream 00001010000011011 decodes as: 000010100 -> 20, 0001101 -> 13, 1 -> 1
Kraft sum of gamma over n = 1..2^20-1: 0.99999905 (= 1 - 2^-20 = 0.99999905)
round trip: 10,000 random integers in 1..2^31-1 written back to back, no separators
gamma stream 309,782 bits, decoded exactly: True; delta stream 223,353 bits, decoded exactly: True
gamma length - 2 log2 n over these integers: min -0.9995, max +1.0000 bits (theory: in (-1, +1])
messages of 37 and 1000 bits sent as gamma(length)+message, back to back (1067 bits): recovered: True
[7] Header that makes a C-bit message self-delimiting (1 KB = 8192 bits, 1 MB = 1024 KB)
gamma = 2 floor(log2 C) + 1 (exact Elias-gamma header); paper = 2 log2 C; units: bits
size C gamma paper gamma-paper delta gamma/C
1 KB 8,192 27 26.0000 +1.0000 20 3.30e-03
10 KB 81,920 33 32.6439 +0.3561 25 4.03e-04
20 KB 163,840 35 34.6439 +0.3561 26 2.14e-04
100 KB 819,200 39 39.2877 -0.2877 28 4.76e-05
1 MB 8,388,608 47 46.0000 +1.0000 32 5.60e-06
10 MB 83,886,080 53 52.6439 +0.3561 35 6.32e-07
100 MB 838,860,800 59 59.2877 -0.2877 38 7.03e-08
[8] 20 KB model: C = 20 x 8192 = 163,840 bits; floor(log2 C) = 17 since 2^17 = 131,072 <= C < 2^18 = 262,144
gamma header 35 bits -> self-delimiting description C + 35 = 163,875 bits (header = 0.0214 % of C)
C ln 2 = 113,565.23 nats; 2 ln C = 24.0133 nats
ln 1/P(h), paper's C ln 2 + 2 ln C = 113,589.25 nats
ln 1/P(h), exact gamma header (C + 35) ln 2 = 113,589.49 nats (difference 0.2469 nats)
ln 1/P(h), Elias-delta header (C + 26) ln 2 = 113,583.26 nats
check 2 log2(C) ln 2 = 2 ln C for C in [2, 3, 1000, 163840, 1000000000]: max relative error 2.0e-16
[9] Length prior Q(c) = 1/c^2: sum over c >= 2 = pi^2/6 - 1 = 0.644934 (partial sum to 10^6: 0.644933)
sum over c >= 1 = pi^2/6 = 1.644934 > 1 (so 1-bit messages must be excluded)