Notes on Coding Theory

Some basic notes on coding theory.

0. How we arrive at the coding problem

Starting point: represent a stream of symbols (letters, pixels, sensor readings) as a sequence of bits, for storage or transmission.

Naive approach: give every symbol a fixed number of bits (8 bits for a byte, or $\lceil \log_2 N \rceil$ bits for $N$ possible symbols). This treats all symbols as equally likely. Real sources are not uniform: in English text, "e" occurs with frequency around 0.127, "z" around 0.001.

If the probability distribution of symbols is known, fewer bits can be spent on frequent symbols and more on rare ones. Frequent symbols repeat often in a message, so this trade reduces the total/average message length, even though rare symbols individually get longer codewords.

This reframes the question from "how many symbols are there" to "how surprising is each symbol, and how many bits should be paid for that surprise." The quantity $-\log_2 p(x)$ measures this: probability maps to information content maps to ideal codeword length.

Questions this raises, answered in order below:

What is the formal setup, and what does the probability of a symbol have to do with bits? Section 1.
What quantity is minimized across a whole message, and what length function minimizes it? Section 2.
If codewords have variable length, how is decoding ambiguity avoided? Section 3 (prefix-free codes).
How is an optimal prefix-free code constructed? Section 4 (Huffman coding).
Can symbol-by-symbol encoding be avoided altogether? Section 5 (arithmetic coding).
What formal bound governs all of this, and what is left out of sections 1 to 5? Sections 6 to 13.

The progression from ideal, possibly-fractional bit lengths to practical, integer-length, decodable codes is the core structure of source coding.

1. Codes, lengths, and information content

Fix a finite alphabet $\mathcal{X} = \lbrace x_1, \ldots, x_n\rbrace$ and a probability mass function $p$ on it with $p(x) > 0$ for every $x$ , so $n = |\operatorname{supp} p|$ . The source emits $X_1, X_2, \ldots$ drawn i.i.d. from $p$ ; Sections 9 and 12 drop the independence assumption. Everything below also reads with $p$ as the empirical symbol frequency of one fixed message, with expectations over $p$ replaced by averages over positions.

A binary code is a map $C : \mathcal{X} \to \lbrace 0,1\rbrace^*$ , with length function $L(x) = |C(x)|$ . Two facts established in Sections 3 and 8, used here in advance:

every uniquely decodable code satisfies the Kraft inequality $\sum_x 2^{-L(x)} \le 1$
every $L : \mathcal{X} \to \mathbb{N}$ satisfying that inequality is the length function of some prefix-free code

So a code may be identified with its length function, and the admissible set is exactly

$\mathcal{L} = \Big\lbrace L : \mathcal{X} \to \mathbb{N} \Big| \sum_{x \in \mathcal{X}} 2^{-L(x)} \le 1 \Big\rbrace$

The number of codewords, meaning the size of the image $C(\mathcal{X})$ , is not a design variable: it is $n$ , fixed by the support of $p$ , since every symbol needs exactly one codeword and distinct symbols need distinct ones. The only freedom is how the $n$ lengths are chosen inside $\mathcal{L}$ , and the constraint is what makes the choice non-trivial, as shortening one codeword forces another to lengthen.

Information content. For $x \in \mathcal{X}$ , define

$h_p(x) = -\log_2 p(x) \in (0, \infty)$

the information content (or surprisal) of $x$ under $p$ , measured in bits. Three properties:

monotone: rarer symbols have larger $h_p$
halving $p(x)$ adds exactly one bit, so $h_p$ is the number of halvings of the probability scale needed to reach $p(x)$ : a length- $\ell$ codeword occupies a $2^{-\ell}$ share of the code tree, matching probability $2^{-\ell}$
additive on independent draws: if $X \sim p$ and $Y \sim p'$ are independent, the information content of the pair $(x, y)$ under the joint law is $h_p(x) + h_{p'}(y)$ , matching concatenation of codewords, which adds lengths

Note that $h_p$ is a function of the pair $(x, p)$ , not of $x$ alone, and that it is a real number, generally not an admissible length. The claim that it is the ideal length is a statement about the whole function $L$ relative to an objective; Section 2 states and proves it.

Running example, carried through Section 5: $\mathcal{X} = \lbrace A, B, C, D\rbrace$ with

Symbol	$p(x)$	$h_p(x) = -\log_2 p(x)$
A	1/2	1 bit
B	1/4	2 bits
C	1/8	3 bits
D	1/8	3 bits

This $p$ is dyadic, meaning every $p(x)$ is a power of $1/2$ , so here $h_p$ happens to be integer-valued and therefore realizable exactly. That is special: Section 3 takes up the general case.

Reading the example as a tree. Conventions used throughout: circles and pill-shaped nodes are internal nodes, square boxes are symbols, edge labels are the bit (or symbol) taken on that branch. Each internal node here shows the probability mass below it. Every split halves the mass, so a symbol's depth equals $h_p(x)$ :

flowchart TD
    R(["1"]) --> A["A<br/>p = 1/2<br/>depth 1"]
    R --> N1(["1/2"])
    N1 --> B["B<br/>p = 1/4<br/>depth 2"]
    N1 --> N2(["1/4"])
    N2 --> C["C<br/>p = 1/8<br/>depth 3"]
    N2 --> D["D<br/>p = 1/8<br/>depth 3"]

2. What are we actually minimizing?

Three scalar summaries could be attached to a length function $L \in \mathcal{L}$ :

worst case, $\max_x L(x)$
unweighted average over the codebook, $\frac{1}{n}\sum_x L(x)$
source-weighted average, $E_p[L(X)] = \sum_x p(x) L(x)$

Neither of the first two involves $p$ , so both reproduce the naive approach of Section 0. Objective 1 is minimized by the fixed-length assignment $L \equiv \lceil \log_2 n \rceil$ , since Kraft forces some codeword to have length at least $\log_2 n$ . Objective 2 is literally objective 3 with $p$ replaced by the uniform distribution $u$ , so by Theorem 2.1 below its relaxed optimum is the flat $L \equiv \log_2 n$ : adopting it amounts to assuming the source is uniform.

Objective 3 is the one that counts bits actually spent. Encoding $m$ symbols costs $\sum_{i=1}^{m} L(X_i)$ bits, whose expectation is $m E_p[L(X)]$ and whose per-symbol average converges to $E_p[L(X)]$ almost surely. So $E_p[L]$ is the bit rate of the code, in bits per symbol, and the design problem is

$\min_{L \in \mathcal{L}} E_p[L(X)]$

Relaxation. Solve it first over real-valued lengths, dropping integrality but keeping Kraft:

$\mathcal{L}_{\mathbb{R}} = \Big\lbrace L : \mathcal{X} \to \mathbb{R} \Big| \sum_x 2^{-L(x)} \le 1 \Big\rbrace \supset \mathcal{L}$

Theorem 2.1. $E_p[L(X)]$ attains its minimum over $\mathcal{L}_{\mathbb{R}}$ uniquely at $L^\star(x) = h_p(x) = -\log_2 p(x)$ , with optimal value $\sum_x p(x) \log_2 \tfrac{1}{p(x)}$ (named in Section 7).

Proof. The substitution $q(x) = 2^{-L(x)}$ is a bijection from $\mathcal{L}_{\mathbb{R}}$ onto the set of positive sub-probability vectors $\lbrace q > 0 : \sum_x q(x) \le 1\rbrace$ , and turns the objective into the cross entropy

$H(p, q) = -\sum_x p(x) \log_2 q(x)$

For any such $q$ , applying $\log_2 s \ge (\log_2 e)(1 - 1/s)$ at $s = p(x)/q(x)$ ,

$H(p, q) - H(p, p) = \sum_x p(x) \log_2 \frac{p(x)}{q(x)} \ge (\log_2 e) \sum_x p(x)\Big(1 - \frac{q(x)}{p(x)}\Big) = (\log_2 e)\Big(1 - \sum_x q(x)\Big) \ge 0$

The first inequality is strict unless $q = p$ pointwise, so the minimum is at $q^\star = p$ , that is $L^\star = -\log_2 p$ . $\square$

Two consequences.

Corollary 2.2 (mismatch). A code built from a model $q$ rather than from the true $p$ has lengths $-\log_2 q(x)$ and rate $E_p[-\log_2 q(X)] = H(p, q) \ge H(p, p)$ . A code cannot use probabilities it does not have; the excess is named and bounded in Section 7, and shrinking it is what Sections 9 to 11 are for.

Corollary 2.3 (saving over fixed length). Since the fixed-length code is Theorem 2.1 applied to $u$ , its excess rate under the true source is

$E_p[\log_2 n] - E_p[L^\star] = \log_2 n - \sum_x p(x)\log_2\tfrac{1}{p(x)} = D(p \Vert u)$

the relative entropy to the uniform distribution (Section 7). The available saving is exactly how far $p$ is from uniform. Compression exploits skew in $p$ , not the size of the alphabet.

Example continued. For $p = (1/2, 1/4, 1/8, 1/8)$ the optimum is $L^\star = (1, 2, 3, 3)$ , which is integral, hence in $\mathcal{L}$ , hence achievable: the code A=0, B=10, C=110, D=111 constructed in Section 4 realizes it.

$E_p[L^\star] = \tfrac12(1) + \tfrac14(2) + \tfrac18(3) + \tfrac18(3) = 1.75 \text{ bits/symbol}$

against $\log_2 4 = 2$ for fixed length: 1750 bits versus 2000 bits per 1000 symbols, a saving of $D(p \Vert u) = 0.25$ bits/symbol. As trees, $E_p[L]$ is the probability-weighted average leaf depth. The fixed-length code is balanced, every leaf at depth 2 regardless of probability. The optimal tree is deliberately lopsided: the heavy leaf A is pulled up to depth 1, the light leaves C and D pushed down to depth 3.

Fixed-length code, $E_p[L] = 2$ bits/symbol:

flowchart TD
    F0((" ")) -->|0| F1((" "))
    F0 -->|1| F2((" "))
    F1 -->|0| FA["A = 00<br/>p = 1/2"]
    F1 -->|1| FB["B = 01<br/>p = 1/4"]
    F2 -->|0| FC["C = 10<br/>p = 1/8"]
    F2 -->|1| FD["D = 11<br/>p = 1/8"]

Optimal code, $E_p[L] = 1.75$ bits/symbol:

flowchart TD
    V0((" ")) -->|0| VA["A = 0<br/>p = 1/2"]
    V0 -->|1| V1((" "))
    V1 -->|0| VB["B = 10<br/>p = 1/4"]
    V1 -->|1| V2((" "))
    V2 -->|0| VC["C = 110<br/>p = 1/8"]
    V2 -->|1| VD["D = 111<br/>p = 1/8"]

The relaxation works only when $L^\star$ lies in $\mathcal{L}$ , which happens only for dyadic $p$ . In general the integrality dropped above costs something (Section 3), the best integer solution has to be constructed (Section 4, Huffman), and the cost can be avoided altogether by coding whole sequences instead of symbols (Section 5, arithmetic coding).

3. Prefix-free codes and the Kraft inequality

Definition: no codeword is a prefix of another codeword. Equivalent to: every codeword is a leaf on a binary tree.

This property allows unambiguous, immediate left-to-right decoding with no lookahead and no separators.

Not prefix-free:

A = 0
B = 01

Reading 0: this could be A, or the start of B. Ambiguous without extra rules.

In the tree, A sits on an internal node with B below it. After reading 0 the decoder has reached a codeword but cannot stop there, because the path may continue to B:

flowchart TD
    R((" ")) -->|0| A["A = 0<br/>on an internal node"]
    A -->|1| B["B = 01"]
    class A bad
    classDef bad fill:#fde2e2,stroke:#c62828,color:#000

Prefix-free:

A = 0
B = 10
C = 110
D = 111

Bitstream 01101110 decodes uniquely as 0 | 110 | 111 | 0, that is A C D A.

Decoding is a walk on the code tree (the optimal-code tree in Section 2): start at the root, follow one edge per bit, emit the symbol on reaching a leaf, then jump back to the root. Trace for 01101110:

Bits consumed	Path from root	Leaf	Output so far
`0`	0	A	A
`110`	1, 1, 0	C	A C
`111`	1, 1, 1	D	A C D
`0`	0	A	A C D A

At no point does the decoder look at a bit beyond the leaf it is on.

Guarantee mechanism, binary code tree:

Left branch = 0, right branch = 1
Symbols occupy only leaves
A leaf has no children, so no other codeword can extend past it, so the code is automatically prefix-free

Kraft inequality: necessary and sufficient condition for a valid prefix-free binary code with lengths $L(x)$ :

$\sum_x 2^{-L(x)} \le 1$

A length- $n$ codeword consumes a $2^{-n}$ fraction of the tree's leaf space. Total consumption cannot exceed 1.

Leaf-space picture for A=0, B=10, C=110, D=111. Extend the tree to depth 3, which has 8 slots. A codeword at depth $n$ blocks all $2^{3-n}$ slots beneath it, since no other codeword may extend it. The blocked slots (dashed) together with C and D fill all 8, so the Kraft sum is exactly $4/8 + 2/8 + 1/8 + 1/8 = 1$ and no space is unused:

flowchart TD
    R((" ")) -->|0| A["A = 0<br/>blocks 4/8"]
    R -->|1| N1((" "))
    N1 -->|0| B["B = 10<br/>blocks 2/8"]
    N1 -->|1| N2((" "))
    N2 -->|0| C["C = 110<br/>1/8"]
    N2 -->|1| D["D = 111<br/>1/8"]
    A -.-|0| g00((" "))
    A -.-|1| g01((" "))
    g00 -.-|0| s000["000"]
    g00 -.-|1| s001["001"]
    g01 -.-|0| s010["010"]
    g01 -.-|1| s011["011"]
    B -.-|0| s100["100"]
    B -.-|1| s101["101"]
    class g00,g01,s000,s001,s010,s011,s100,s101 ghost
    classDef ghost fill:#f2f2f2,stroke:#9e9e9e,stroke-dasharray:4 3,color:#666

Two ways the sum can differ from 1. Lengths $\lbrace 1, 2, 3\rbrace$ give $1/2 + 1/4 + 1/8 = 7/8 < 1$ : a valid code, but the leaf 111 is wasted (C could be shortened to 11). Lengths $\lbrace 1, 1, 2\rbrace$ give $1/2 + 1/2 + 1/4 = 5/4 > 1$ : once A and B take both depth-1 nodes, nothing is left for C.

Lengths $\lbrace 1, 2, 3\rbrace$ , Kraft sum $7/8$ , valid with slack:

flowchart TD
    S0((" ")) -->|0| SA["A = 0"]
    S0 -->|1| S1((" "))
    S1 -->|0| SB["B = 10"]
    S1 -->|1| S2((" "))
    S2 -->|0| SC["C = 110"]
    S2 -->|1| SU["111<br/>unused"]
    class SU ghost
    classDef ghost fill:#f2f2f2,stroke:#9e9e9e,stroke-dasharray:4 3,color:#666

Lengths $\lbrace 1, 1, 2\rbrace$ , Kraft sum $5/4$ , impossible:

flowchart TD
    X0((" ")) -->|0| XA["A = 0"]
    X0 -->|1| XB["B = 1"]
    XC["C (length 2):<br/>no free node left"]
    class XC bad
    classDef bad fill:#fde2e2,stroke:#c62828,color:#000

Cost of prefix-freeness: codeword lengths must be integers, but ideal lengths $-\log_2 p(x)$ are usually fractional. This mismatch produces overhead.

Example: $p(A)=0.7, p(B)=0.2, p(C)=0.1$

Ideal lengths: 0.51, 2.32, 3.32 bits (fractional, not realizable directly)
Actual code (A=0, B=10, C=11): average = 1.3 bits/symbol
Entropy $H(X) \approx 1.157$ bits/symbol
Overhead: 1.3 - 1.157 = 0.143 bits/symbol

Overhead at each leaf:

flowchart TD
    R((" ")) -->|0| A["A = 0<br/>p = 0.7<br/>ideal 0.51<br/>actual 1"]
    R -->|1| N((" "))
    N -->|0| B["B = 10<br/>p = 0.2<br/>ideal 2.32<br/>actual 2"]
    N -->|1| C["C = 11<br/>p = 0.1<br/>ideal 3.32<br/>actual 2"]

Rounding does not only go up. A is lengthened by about 0.49 bits, while B and C end up shorter than their ideal lengths (by 0.32 and 1.32 bits). The net overhead is positive because A occurs 70% of the time: $0.7(0.485) - 0.2(0.322) - 0.1(1.322) \approx 0.143$ .

4. Huffman coding, the best integer-length code

Algorithm: repeatedly merge the two lowest-probability nodes into a combined node until one root remains. Codeword equals path from root.

Example (A=0.5, B=0.25, C=0.125, D=0.125):

Merge C+D to 0.25
Merge B+(CD) to 0.5
Merge A+(BCD) to 1.0

Resulting code: A=0, B=10, C=110, D=111.

Tree view. Internal nodes are labeled with the merge step that created them and their combined probability. Reading steps 1 to 3 bottom-up replays the algorithm; reading edges top-down gives the codewords. Convention: at each merge the higher-probability child gets 0 (on a tie, the single symbol first). Any consistent choice works, since it changes the bit labels but not the lengths.

flowchart TD
    M3(["step 3<br/>1.0"]) -->|0| A["A = 0<br/>0.5"]
    M3 -->|1| M2(["step 2<br/>0.5"])
    M2 -->|0| B["B = 10<br/>0.25"]
    M2 -->|1| M1(["step 1<br/>0.25"])
    M1 -->|0| C["C = 110<br/>0.125"]
    M1 -->|1| D["D = 111<br/>0.125"]

A non-dyadic example with five symbols: A=0.35, B=0.25, C=0.20, D=0.12, E=0.08. Queue contents at each step, in ascending order:

Step	Queue before merging	Merge	New node
1	E 0.08, D 0.12, C 0.20, B 0.25, A 0.35	D + E	DE 0.20
2	C 0.20, DE 0.20, B 0.25, A 0.35	C + DE	CDE 0.40
3	B 0.25, A 0.35, CDE 0.40	A + B	AB 0.60
4	CDE 0.40, AB 0.60	AB + CDE	root 1.00

flowchart TD
    R(["step 4<br/>1.00"]) -->|0| AB(["step 3<br/>0.60"])
    R -->|1| CDE(["step 2<br/>0.40"])
    AB -->|0| A["A = 00<br/>0.35"]
    AB -->|1| B["B = 01<br/>0.25"]
    CDE -->|0| C["C = 10<br/>0.20"]
    CDE -->|1| DE(["step 1<br/>0.20"])
    DE -->|0| D["D = 110<br/>0.12"]
    DE -->|1| E["E = 111<br/>0.08"]

Resulting code: A=00, B=01, C=10, D=110, E=111. $E[L] = 2(0.35 + 0.25 + 0.20) + 3(0.12 + 0.08) = 2.2$ bits/symbol, against $H(X) \approx 2.153$ , inside the bound below. Two differences from the first example. The final merge joins two merged subtrees (AB and CDE), so the tree is bushy rather than a single chain. And the lengths no longer equal the ideal lengths (1.51, 2.00, 2.32, 3.06, 3.64): for instance A gets 2 bits instead of about 1.5.

Running the algorithm on Section 3's distribution (0.7, 0.2, 0.1) merges B + C = 0.3, then A + (BC) = 1.0, which produces exactly the code A=0, B=10, C=11 used there.

Huffman coding is optimal among prefix-free, symbol-by-symbol codes.

Bound: $H(X) \le L_{\text{Huffman}} < H(X) + 1$

Limitation: codeword lengths per symbol remain integers. If one symbol has $p=0.9$ , ideal length is approximately 0.152 bits, but Huffman assigns it at least 1 bit. This inefficiency scales with how far the distribution is from powers of $1/2$ .

5. Arithmetic coding, or how to spend fractional bits

Instead of assigning a discrete codeword per symbol, the entire message is encoded as a single number within a shrinking sub-interval of $[0,1)$ .

Procedure:

Start with $[0,1)$ , partitioned according to symbol probabilities.
For each symbol observed, narrow the interval to that symbol's proportional sub-range.
Repeat, recursively subdividing within the current interval.
Any number inside the final interval uniquely represents the whole sequence.

Example: A=[0,0.5), B=[0.5,0.75), C=[0.75,1). Message "AB":

After A: interval = [0, 0.5)
Subdivide by the same proportions within [0,0.5); B's sub-range = [0.25, 0.375)
Final interval [0.25, 0.375): for example 0.3 encodes "AB"

The subdivisions form a tree over messages rather than over symbols. Branches split in proportion to probability instead of in half, and each level adds one symbol. The width of a node's interval equals the probability of the message so far, here $p(\text{AB}) = 0.5 \times 0.25 = 0.125$ :

flowchart TD
    R["[0, 1)"] -->|A| A["A: [0, 0.5)<br/>width 0.5"]
    R -->|B| B["B: [0.5, 0.75)"]
    R -->|C| C["C: [0.75, 1)"]
    A -->|A| AA["AA: [0, 0.25)"]
    A -->|B| AB["AB: [0.25, 0.375)<br/>width 0.125"]
    A -->|C| AC["AC: [0.375, 0.5)"]
    class R,A,AB hit
    classDef hit fill:#e3f0fd,stroke:#1565c0,color:#000

Specifying an interval of width $w$ takes about $-\log_2 w$ bits plus a small constant (here $-\log_2 0.125 = 3$ ). Over a whole message this is $-\log_2 p(\text{message}) = \sum_i -\log_2 p(x_i)$ : the information content of Section 1, summed over the message before any rounding. Rounding happens once per message instead of once per symbol, which is the source of the gain over Huffman. Unlike a Huffman tree, this tree is never stored; encoder and decoder only compute the single path they need.

Comparison on a skewed distribution: $p(A)=0.9, p(B)=0.1$ , so $H(X) \approx 0.469$ bits/symbol.

Huffman: forced to 1 bit/symbol (2 symbols, minimum 1 bit each).
Arithmetic coding: approaches 0.469 bits/symbol over long sequences, since fractional bit costs are amortized across the whole message rather than rounded per symbol.

6. Huffman or arithmetic?

Aspect	Huffman	Arithmetic
Unit of encoding	Per-symbol codeword	Entire sequence as interval/number
Codeword form	Explicit bit strings	Single number (interval)
Fractional bit lengths	Not possible per symbol	Effectively yes, amortized
Prefix-free tree	Yes	Not applicable, different construction
Bound relative to entropy	$H(X) \le L < H(X)+1$	Approaches $H(X)$ for long messages
Implementation cost	Low	Higher (finite-precision arithmetic, see Section 9)

Three levels, summarizing sections 1 to 5:

Theoretical ideal: $L(x) = -\log_2 p(x)$ , may be fractional.
Practical constraint: integer-length, prefix-free codes (Kraft inequality).
Huffman coding: optimal solution under that constraint. Arithmetic coding: removes the integer-length constraint by coding the whole sequence at once.

7. Entropy, and why no code can beat it

Theorem 2.1 showed that $-\log_2 p(x)$ minimizes the rate among real-valued length functions satisfying Kraft, and left the optimal value unnamed. That value is the entropy, and the same argument extends from that one relaxed symbol code to every uniquely decodable code.

Definition, for a discrete random variable $X$ with distribution $p$ :

$H(X) = -\sum_x p(x) \log_2 p(x)$

$H(X)$ is the probability-weighted average of the information content of Section 1: $H(X) = E_p[h_p(X)] = E_p[-\log_2 p(X)]$ . It is written $H(p)$ when the distribution has to be named explicitly.

Shannon's source coding theorem: for a source with entropy $H(X)$ , the average code length $L$ of any uniquely decodable code satisfies

$L \ge H(X)$

and there exists a code (not necessarily achievable with integer lengths per symbol, but achievable in the limit by block coding or arithmetic coding) with

$$L < H(X) + 1$

Two consequences:

$H(X)$ is not just a descriptive statistic. It is the hard floor for average code length, for any code, under any coding scheme, given the assumption that symbols are drawn independently from a fixed distribution $p$ .
The Huffman bound in Section 4 ( $H(X) \le L_{\text{Huffman}} < H(X)+1$ ) is a special case of this theorem, restricted to prefix-free symbol-by-symbol codes.

Proof of the bound, and decomposition of the gap. Alongside the cross entropy $H(p, q) = -\sum_x p(x)\log_2 q(x)$ of Section 2, define the relative entropy (Kullback-Leibler divergence)

$D(p \Vert q) = \sum_x p(x) \log_2 \frac{p(x)}{q(x)}$

The proof of Theorem 2.1 is exactly the statement $D(p \Vert q) \ge 0$ for sub-probability $q$ (Gibbs' inequality), with equality only if $q = p$ . Splitting the cross entropy,

$H(p, q) = H(p) + D(p \Vert q)$

so Corollary 2.2's mismatch penalty is $D(p \Vert q)$ bits per symbol.

Now take any uniquely decodable code with lengths $L$ . By Kraft-McMillan (Section 8), $Z = \sum_x 2^{-L(x)} \le 1$ , so $q_L(x) = 2^{-L(x)} / Z$ is a genuine distribution: the coding distribution the code implicitly assumes, in the sense of Corollary 2.2. Since $L(x) = -\log_2 q_L(x) - \log_2 Z$ ,

$E_p[L(X)] = H(p) + D(p \Vert q_L) + \left(-\log_2 Z\right) \ge H(p)$

Both added terms are non-negative, and they name the two distinct ways a code wastes bits: $D(p \Vert q_L)$ is the penalty for coding with the wrong distribution, and $-\log_2 Z$ is unused leaf space (Section 3's slack case). Equality requires $q_L = p$ and $Z = 1$ , that is, lengths exactly $-\log_2 p(x)$ , which is realizable with integer lengths only when every $p(x)$ is a power of $1/2$ . This extends Theorem 2.1 from relaxed symbol codes to every uniquely decodable code, and it identifies $D(p \Vert q)$ as the per-symbol price of a model mismatch, which is what the adaptive and context models of Section 9 exist to reduce.

Almost sure version. The bound above concerns $E_p[L]$ , but the guarantee is not restricted to the average. For $X_1, \ldots, X_n$ drawn i.i.d. from $p$ ,

$-\tfrac{1}{n} \log_2 p(X_1, \ldots, X_n) \longrightarrow H(X) \quad \text{almost surely}$

(the asymptotic equipartition property; the Shannon-McMillan-Breiman theorem extends it to stationary ergodic sources). So a code with lengths $-\log_2 p$ spends close to $n H(X)$ bits on essentially every sequence it actually encounters, not merely in expectation over a hypothetical ensemble. Equivalently, the probability mass concentrates on a typical set of roughly $2^{n H(X)}$ sequences of near-equal probability, and $n H(X)$ bits suffice to index it.

Worked check against Section 3's example: $p(A)=0.7, p(B)=0.2, p(C)=0.1$ .

$H(X) = -(0.7 \log_2 0.7 + 0.2 \log_2 0.2 + 0.1 \log_2 0.1) \approx 1.157 \text{ bits/symbol}$

This matches the value used in Section 3 without derivation. The prefix-free code there achieved 1.3 bits/symbol, consistent with $H(X) \le L$ .

Entropy also measures uniformity: it is maximized (at $\log_2 N$ for $N$ symbols) when the distribution is uniform, and decreases as the distribution becomes more skewed. A skewed distribution is more predictable, hence more compressible, hence lower entropy.

8. Does dropping the prefix property help? (Kraft-McMillan)

Section 3 stated the Kraft inequality for prefix-free codes:

$\sum_x 2^{-L(x)} \le 1$

A broader class of codes exists: uniquely decodable codes. A code is uniquely decodable if every valid bitstream corresponds to exactly one sequence of symbols, without requiring that decoding proceed strictly left to right without lookahead. Prefix-free codes are uniquely decodable, but not every uniquely decodable code is prefix-free (some require reading ahead before resolving a symbol).

The McMillan theorem extends the Kraft inequality to this larger class: any uniquely decodable code, prefix-free or not, must satisfy the same inequality:

$\sum_x 2^{-L(x)} \le 1$ $

Combined with Section 3's result (any length assignment satisfying the Kraft inequality can be realized by a prefix-free code), this means: for any set of codeword lengths achievable by a uniquely decodable code, a prefix-free code with the same lengths also exists.

Practical implication: prefix-free codes lose nothing relative to the larger class of uniquely decodable codes. There is no reason to design a non-prefix-free uniquely decodable code, since a prefix-free code with identical length distribution (and identical average length) is always available, and it has the added benefit of immediate, lookahead-free decoding described in Section 3.

Example with the non-prefix-free code from Section 3, A=0, B=01. It is uniquely decodable: every 1 in a valid stream must end a B, so a 0 followed by 1 is B, and a 0 followed by 0 (or by the end of the stream) is A. Decoding is unambiguous but needs one bit of lookahead. Its Kraft sum is $1/2 + 1/4 = 3/4 \le 1$ , as McMillan requires, so a prefix-free code with the same lengths exists: move B from below A to the free leaf 10.

Uniquely decodable but not prefix-free, A=0, B=01:

flowchart TD
    U0((" ")) -->|0| UA["A = 0"]
    UA -->|1| UB["B = 01"]
    class UA bad
    classDef bad fill:#fde2e2,stroke:#c62828,color:#000

Prefix-free version with the same lengths, A=0, B=10:

flowchart TD
    P0((" ")) -->|0| PA["A = 0"]
    P0 -->|1| P1((" "))
    P1 -->|0| PB["B = 10"]

9. What if we do not know the distribution?

Sections 1 to 8 assume the distribution $p(x)$ is fixed and known to both encoder and decoder in advance. Two ways this assumption fails in practice:

The distribution is not known in advance. Example: compressing an arbitrary text file without a precomputed frequency table.

The distribution changes across the message. Example: in English text, the probability of the next character depends heavily on the preceding characters ("q" is almost always followed by "u").

Adaptive Huffman coding addresses the first problem: the encoder and decoder both start with a default (for example, uniform) distribution, then update symbol counts and rebuild the Huffman tree as symbols are processed, using the same update rule on both ends so the tree stays synchronized without transmitting it separately.

Example: both sides start from a count of 1 for each of A, B, C, D, which gives a balanced tree. After A A A A B has been coded, both sides hold counts A=5, B=2, C=1, D=1, and the rebuilt tree gives A a 1-bit codeword. The decoder can make the identical update because it only uses symbols it has already decoded. (Practical versions, the FGK and Vitter algorithms, adjust the tree incrementally after each symbol instead of rebuilding it.)

Start, counts A=1, B=1, C=1, D=1:

flowchart TD
    a0((" ")) -->|0| a1((" "))
    a0 -->|1| a2((" "))
    a1 -->|0| aA["A = 00"]
    a1 -->|1| aB["B = 01"]
    a2 -->|0| aC["C = 10"]
    a2 -->|1| aD["D = 11"]

After A A A A B, counts A=5, B=2, C=1, D=1:

flowchart TD
    b0((" ")) -->|0| bA["A = 0"]
    b0 -->|1| b1((" "))
    b1 -->|0| bB["B = 10"]
    b1 -->|1| b2((" "))
    b2 -->|0| bC["C = 110"]
    b2 -->|1| bD["D = 111"]

Context models address the second problem: rather than a single distribution $p(x)$ , use a conditional distribution $p(x \mid \text{context})$ , where the context is the preceding $k$ symbols (an order- $k$ model). Order-0 corresponds to the fixed-distribution assumption used in sections 1 to 6. Higher orders capture local structure such as common letter pairs or triples.

Cost: the context model itself must be known to (or learned identically by) both encoder and decoder, and either transmitted or built adaptively. Larger $k$ captures more structure but requires more data to estimate the conditional probabilities reliably, and more memory to store them.

Arithmetic coding (Section 5) composes naturally with context models: at each step, the interval is subdivided using the distribution conditioned on the context so far, rather than a fixed distribution. This combination (context modeling plus arithmetic coding) is the basis of most modern general-purpose compressors that operate at close to the entropy of the true, context-dependent source.

10. Compressing repetition rather than frequency (LZ77, LZ78, LZW)

Sections 1 to 9 all encode based on symbol probability, whether fixed (Huffman, Section 4) or context-dependent (Section 9). Dictionary methods use a different mechanism: exploiting repeated substrings rather than symbol frequency.

LZ77: maintains a sliding window over recently seen data. When the upcoming text matches a substring already present in the window, output a reference (offset, length) pointing back to that earlier occurrence, instead of the literal symbols. Example: encoding "...information theory... more information theory here" can replace the second "information theory" with a pointer to the first, plus a length.

LZ78: builds an explicit dictionary of substrings seen so far, incrementally, and outputs indices into that dictionary rather than window offsets. LZW is a common variant that initializes the dictionary with all single symbols and grows it as the input is processed, without needing to transmit the dictionary explicitly (the decoder reconstructs it using the same rule).

Example, LZ78 on ABAABABAABAB. At each step, find the longest dictionary entry matching the upcoming input, output (its index, the next symbol), and add the extended phrase as a new entry. Index 0 is the empty phrase.

Step	Longest match (index)	Next symbol	Token	New entry
1	empty (0)	A	(0, A)	1: A
2	empty (0)	B	(0, B)	2: B
3	A (1)	A	(1, A)	3: AA
4	B (2)	A	(2, A)	4: BA
5	BA (4)	A	(4, A)	5: BAA
6	BA (4)	B	(4, B)	6: BAB

The input parses as A | B | AA | BA | BAA | BAB. The dictionary is a trie: each entry is an existing entry plus one symbol, which is exactly what a token records, so each token adds one child node.

flowchart TD
    R["0: empty"] -->|A| N1["1: A"]
    R -->|B| N2["2: B"]
    N1 -->|A| N3["3: AA"]
    N2 -->|A| N4["4: BA"]
    N4 -->|A| N5["5: BAA"]
    N4 -->|B| N6["6: BAB"]

Finding the longest match is a walk down this trie following the input, stopping when the next symbol has no edge. Two contrasts with the code trees of Sections 3 and 4: symbols label edges rather than leaves, and every node (internal ones included) is a usable entry, since each phrase is by construction a prefix of later phrases. On an input this short, 6 tokens cost more bits than the 12 raw symbols; the gain appears on long inputs, where the trie deepens and later tokens cover longer and longer phrases.

Where this fits in the framework of sections 1 to 9: LZ methods do not directly assign $-\log_2 p(x)$ style lengths to individual symbols. Instead, they transform the input into a shorter sequence of (symbol, pointer) tokens, exploiting redundancy across positions (repeated phrases) rather than redundancy within the marginal symbol distribution. The token stream that results is often then entropy-coded (Huffman or arithmetic coding) as a second stage. gzip and DEFLATE combine LZ77 with Huffman coding in exactly this two-stage structure.

Relation to entropy: LZ77 and LZ78 can be shown to asymptotically approach the entropy rate of a stationary ergodic source (a source whose statistics do not change over time and whose long-run behavior is representative of any given sample) as the window or dictionary size grows, without requiring the encoder to know the source distribution in advance. This is a different route to the same entropy limit described in Section 7, arrived at without explicit probability estimation.

11. Arithmetic coding in finite precision (range coding)

Section 5 described arithmetic coding using real-number intervals within $[0,1)$ . Real hardware and software use fixed-precision arithmetic (32-bit or 64-bit integers), not arbitrary-precision real numbers.

Range coding is the practical implementation strategy: it performs the same interval-narrowing operation as Section 5, but represents the current interval using a fixed number of bits, renormalizing (shifting out bits that are already determined and rescaling) as the interval shrinks below the precision limit, instead of tracking an ever more precise real number.

Two practical differences from the idealized version in Section 5:

Precision is bounded. Care is required in the renormalization step to avoid a carry (a small addition affecting more digits than the currently tracked range) propagating beyond the tracked precision.
The underlying base is often not restricted to binary subdivision; some range coders subdivide using byte-aligned ranges (base 256) for speed, rather than bit-by-bit as in Section 5's binary framing.

Range coding is used in place of "textbook" arithmetic coding in most production compressors (for example, in modern image and video codecs, and in general-purpose compressors such as those using PAQ-family or CM-family entropy stages), because it achieves the same near-entropy performance described in Section 5 without requiring arbitrary-precision arithmetic.

12. Entropy with more than one variable

Section 7 defined entropy $H(X)$ for a single random variable. Section 9 introduced context models informally, using $p(x \mid \text{context})$ . This section gives the formal quantities underlying that move.

Joint entropy, for two random variables $X, Y$ with joint distribution $p(x,y)$ :

$H(X,Y) = -\sum_{x,y} p(x,y) \log_2 p(x,y)$

Conditional entropy, the average uncertainty remaining in $Y$ once $X$ is known:

$H(Y \mid X) = -\sum_{x,y} p(x,y) \log_2 p(y \mid x)$

Chain rule: $H(X,Y) = H(X) + H(Y \mid X)$ .

Mutual information, the reduction in uncertainty about $Y$ from knowing $X$ :

$I(X;Y) = H(Y) - H(Y \mid X) = H(X) + H(Y) - H(X,Y)$

$I(X;Y) \ge 0$ , with equality only if $X$ and $Y$ are independent.

Equivalently, $I(X;Y) = D\big(p(x,y) \Vert p(x)p(y)\big)$ in the notation of Section 7: mutual information is the relative entropy between the joint distribution and the product of the marginals, so its non-negativity is the same Gibbs inequality used there.

Connection to Section 9: an order- $k$ context model is an attempt to exploit $H(X_{n} \mid X_{n-1}, \ldots, X_{n-k}) < H(X_n)$ , that is, the entropy of the next symbol given the preceding $k$ symbols is lower than its unconditional entropy, whenever consecutive symbols are correlated. The gap $H(X_n) - H(X_n \mid \text{context})$ is exactly the mutual information between the next symbol and its context, and it quantifies the maximum additional compression available by using that context, beyond what an order-0 model (Sections 1 to 6) can achieve.

13. Sending bits over a noisy channel (channel coding)

Sections 1 to 12 address source coding: representing data compactly, under the assumption that the encoded bits are transmitted or stored without alteration. Channel coding addresses the complementary problem: transmitting bits reliably over a channel that introduces errors (noise, interference, bit flips).

Channel capacity $C$ : the maximum rate, in bits per channel use, at which information can be transmitted over a given noisy channel with an error probability that can be made arbitrarily small, given a suitable code. For a binary symmetric channel with bit-flip probability $\epsilon$ :

$C = 1 - H_2(\epsilon), \quad H_2(\epsilon) = -\epsilon \log_2 \epsilon - (1-\epsilon)\log_2(1-\epsilon)$

Noisy-channel coding theorem (Shannon): for any transmission rate $R < C$ , there exists a code achieving arbitrarily low error probability. For $R > C$ , no code achieves arbitrarily low error probability.

Error-correcting codes are the practical realizations of this theorem: adding structured redundancy to a message so the receiver can detect and correct a bounded number of errors. Examples include Hamming codes, Reed-Solomon codes, and LDPC codes.

Relation to source coding, sections 1 to 12: source coding minimizes redundancy (compress toward $H(X)$ , Section 7), channel coding adds redundancy back in a structured way to survive noise. Shannon's separation theorem states that, for point-to-point communication, source coding and channel coding can be designed separately (compress optimally, then add error correction optimally) without loss of overall efficiency compared to a jointly designed scheme. This justifies treating them as two separate topics, as done here.

14. What if some error is acceptable? (rate-distortion)

Sections 1 to 13 assume lossless reconstruction: the decoder recovers the exact original sequence. Rate-distortion theory addresses lossy coding: how few bits are needed if some reconstruction error is acceptable.

Distortion measure $d(x, \hat{x})$ : a chosen function quantifying the cost of reconstructing symbol $x$ as $\hat{x} \neq x$ (for example, squared error for continuous-valued sources).

Rate-distortion function $R(D)$ : the minimum bit rate (bits per symbol) required to achieve average distortion no greater than $D$ , over all encoding schemes:

$R(D) = \min_{p(\hat{x}\mid x): E[d(x,\hat{x})] \le D} I(X; \hat{X})$

using the mutual information defined in Section 12, now between the source $X$ and its reconstruction $\hat{X}$ .

At $D=0$ (no distortion allowed), $R(D)$ reduces to $H(X)$ for a discrete source, recovering the lossless bound from Section 7. As the allowed distortion $D$ increases, $R(D)$ decreases: less precision is needed if some error is tolerated.

Practical lossy compressors (JPEG for images, MP3 and Opus for audio, most video codecs) operate by first applying a transform intended to concentrate distortion where it is least perceptible (for example, a frequency-domain transform paired with a model of human perceptual sensitivity), then discarding or coarsely quantizing the least perceptually important components, then applying lossless entropy coding (Huffman or arithmetic coding, Sections 4 to 5, often with context modeling, Section 9) to the remaining quantized data. The rate-distortion function gives the theoretical bound these systems are measured against.