Coding and Entropy §

Step 1 — what decoding requires. The decoder receives one long bit string with no separators and must split it into codewords, left to right. The split must be unique for every possible string, otherwise the message is ambiguous.

Step 2 — what goes wrong without prefix-freeness. Take the code A = 0, B = 1, C = 01. The bit string 01 has two valid readings:

• a single symbol C,
• the symbol A followed by the symbol B.

The decoder cannot tell which one was sent. The problem is that 0 (a codeword for A) is a prefix of 01 (a codeword for C): after reading 0, the decoder cannot know whether the codeword is already complete.

Step 3 — why prefix-freeness fixes it. If no codeword is a prefix of another, the decoder can read bits left to right and stop at the first codeword that matches. That first match is the only possible one, because no longer codeword can start with those same bits. Decoding is then a simple greedy scan — no separators, no length fields, no backtracking.

Step 4 — the tree picture. A binary code is a binary tree: each edge is a bit (left = 0, right = 1), and each codeword is the path from the root to a node. Prefix-freeness means exactly that all symbols sit on leaves: a codeword that is a prefix of another would be an internal node with children, which is impossible if every symbol is a leaf.

Here A = 0, B = 10, C = 110, D = 111. Every symbol is a leaf, so the code is prefix-free and the greedy scan decodes any bit string uniquely.

Properties:

• $H(X) = 0$ iff $X$ is deterministic.
• $H(X) \leq \log_2 |\mathcal{X}|$, with equality iff $X$ is uniform.
• $H(X, Y) = H(X) + H(Y|X)$ (chain rule).
• $H(X, Y) \leq H(X) + H(Y)$ (subadditivity).

Mutual information: $I(X; Y) = H(X) - H(X|Y) = \sum_{x,y} p(x,y) \log_2 \frac{p(x,y)}{p(x)p(y)} \geq 0$. It measures how much knowing $Y$ reduces uncertainty about $X$.

Conditional entropy: $H(X|Y) = \sum_y p(y) H(X|Y=y)$. The number of bits still needed to describe $X$ after observing $Y$.

All logarithms in this page are base 2, so all quantities are in bits.

Example: English text has entropy $\approx 0.6$–$1.3$ bits/character over a 27-character alphabet (26 letters + space), versus $\log_2 27 \approx 4.75$ bits for a uniform distribution. The achievable compression ratio is therefore $0.6/4.75 \approx 13$ to $1.3/4.75 \approx 27$ of the original size. Shannon’s 1951 estimate in Prediction and Entropy of Printed English gives the 0.6–1.3 range.

For English text (27-character alphabet, $H \approx 1.0$ bits/char as a midpoint): $R \approx 1 - 1.0/4.75 \approx 79$. This means roughly 79% of the 4.75 bits per character are “wasted” because the distribution is far from uniform. Redundancy is what lossless compression exploits: by using a variable-length code, the compressor removes this waste and approaches the entropy bound.

Redundancy is also the quantity that error-correcting codes introduce deliberately (see Communication): a small amount of added redundancy makes the code robust to channel noise.

Intuition: each codeword of length $l_i$ occupies a subtree of size $2^{-l_i}$ of the full binary tree. The Kraft inequality says these subtrees must be disjoint (total area $\leq 1$). Equality holds when the tree is full (every internal node has two children).

The picture below shows the code space as a unit square: each codeword of length $l$ claims a rectangle of area $2^{-l}$. For the prefix-free code A = 0, B = 10, C = 110, D = 111, the four rectangles exactly tile the square (Kraft sum = 1, a full tree). A code whose rectangles did not fill the square would leave unused code space; rectangles that overlapped would correspond to a prefix violation, which is impossible.

Necessity: in any prefix-free code, the leaves are disjoint subtrees, so their total area is at most 1.

Sufficiency: if the inequality holds, one can construct a prefix-free code with exactly those lengths by filling a binary tree level by level (a greedy leaf-placement algorithm).

The Kraft inequality is the constraint under which Huffman coding optimizes the expected length, and it is the tool used in the proof of the source coding theorem.

Lower bound ($L \geq H(X)$):

Let $l_i$ be the codeword length for symbol $x_i$ with probability $p_i$. By the Kraft inequality, $\sum_i 2^{-l_i} \leq 1$. Define $q_i = 2^{-l_i}$; then $\sum_i q_i \leq 1$. Extend to a proper distribution by adding a dummy symbol with probability $1 - \sum_i q_i$.

By the Gibbs inequality (relative entropy is non-negative):

Since $q_i = 2^{-l_i}$, the right side is $\sum_i p_i l_i = L$. The left side is $H(X)$. Hence $H(X) \leq L$.

Upper bound ($L < H(X) + 1$):

Choose codeword lengths $l_i = \lceil -\log_2 p_i \rceil$. Then $l_i < -\log_2 p_i + 1$, so:

It remains to verify the Kraft inequality. Since $l_i = \lceil -\log_2 p_i \rceil$ by definition, the first sum is exactly:

where the single inequality uses $\lceil y \rceil \geq y$, hence $2^{-\lceil y \rceil} \leq 2^{-y}$. So the lengths are realizable, and a prefix-free code with expected length $< H(X) + 1$ exists.

Typical-set intuition: the theorem has a purely combinatorial reading. For a sequence of $n$ i.i.d. symbols, the law of large numbers concentrates almost all probability mass on the typical set: roughly $2^{nH(X)}$ sequences, each with probability close to $2^{-nH(X)}$. Indexing one typical sequence therefore takes about $\log_2 2^{nH(X)} = nH(X)$ bits, i.e. $H(X)$ bits per symbol. The atypical sequences outside this set are exponentially rare, so giving them long codewords costs almost nothing in expectation. This counting argument is the heart of the theorem, and it explains why encoding blocks of $n$ symbols shrinks the gap to $1/n$ per symbol.

Why greedy works: the two least-probable symbols are always siblings at the deepest level of the optimal tree (exchange argument). Merging them reduces the problem to $n-1$ symbols, and the greedy choice is locally optimal at every step.

Example: probabilities $(0.5, 0.25, 0.125, 0.125)$ (the distribution animated in the diagram above).

• Merge 0.125 + 0.125 → 0.25
• Merge 0.25 + 0.25 → 0.5
• Merge 0.5 + 0.5 → 1.0
• Codewords: 0, 10, 110, 111. Expected length = 1.75 = $H$ (exact, because all probabilities are powers of 2, so every $-\log_2 p_i$ is an integer and no codeword needs rounding up).

Shannon–Fano coding: the other classical way to build a prefix-free code. It works top-down: sort the symbols by decreasing probability, recursively split the ordered list into two groups of approximately equal total probability, and assign bit 0 to one group and bit 1 to the other. This contrasts with Huffman’s bottom-up greedy merge. Shannon–Fano is simple and often close to optimal, but its split can waste code space, so it does not always reach the Huffman optimum; Huffman’s construction is the one with the optimality guarantee above.

Practical use: Huffman coding is the entropy-coding stage in DEFLATE (gzip, PNG, ZIP), JPEG, and MP3. See Compression for how it is combined with other techniques.

The shared principle: prefix-freeness. For UTF-8, the leading-bit pattern (0 for 1 byte, 110 for 2, 1110 for 3, 11110 for 4, with continuation bytes 10xxxxxx) makes the set of encodings prefix-free: no code point’s byte sequence is a prefix of another’s. A decoder that hits a corrupt or resyncs mid-stream can determine the length of the next code point from the first byte alone, without any external length field — the same greedy first-match decoding as the binary prefix tree in the first section.

The contrast: fixed-length, zero-redundancy codes. Base-32 and Base-64 do not exploit any source distribution: every character carries exactly 5 or 6 bits, all $2^5$ or $2^6$ codewords are used, and the Kraft sum is exactly 1. Their redundancy with respect to their own alphabet is zero; the only “loss” is the mapping itself, which inflates the data by $8/5 = 1.6$ (Base-32) or $8/6 \approx 1.33$ (Base-64) plus padding, because 8-bit bytes do not align with 5- or 6-bit groups. They exist to carry binary data through channels that only safely transmit a restricted printable alphabet (email, URLs, JSON), not to compress.

Where the entropy idea does apply: UTF-8’s expected length on real text is close to 1 byte per character precisely because ASCII-range code points dominate — a skewed distribution exploited by a variable-length code, the same mechanism Huffman formalizes. ASCII, being fixed-length, cannot do this: its 7 bits per character are spent uniformly whether the text is full of e or of z.

Base-64 in practice: used in MIME email attachments, JWT tokens, and data URIs.

Problem: A source emits 4 symbols with probabilities $(0.4, 0.3, 0.2, 0.1)$. Compute the entropy, build the Huffman code, compute its expected length, and compare it with the entropy bound.