Contents / Information Theory / Source Coding and the Entropy Bound

Chapter 4

Source Coding and the Entropy Bound

Shannon's source coding theorem in both directions, and Kraft's inequality — why entropy is the floor no lossless code can beat.

Introduction

Shannon's source coding theorem in both directions, and Kraft's inequality — why entropy is the floor no lossless code can beat.

4.1What the Theorem Says

Shannon's source coding theorem — the noiseless coding theorem — is the first of the two pillars of information theory. It converts the counting facts of the previous chapter into a sharp statement about which compression schemes can exist. Its content is that a single number, the entropy rate, is simultaneously an upper and a lower bound on the achievable rate, so that the compressibility of a source is not a matter of ingenuity but of arithmetic.

To state the theorem we must first say precisely what a code is and what its rate means. Vagueness here is what makes the theorem sound paradoxical ("surely a clever enough algorithm...").

Definition 4.1 (Fixed-rate block code and its rate). A block code of length $n$ and rate $R$ for a source with alphabet $\mathcal{X}$ is a pair of maps

f_n : \mathcal{X}^n \to \{1,2,\dots,2^{\lceil nR\rceil}\}, \qquad g_n : \{1,2,\dots,2^{\lceil nR\rceil}\} \to \mathcal{X}^n ,

the encoder and the decoder. Its error probability is

P_e^{(n)} = \Pr\bigl(g_n(f_n(X^n)) \neq X^n\bigr).

The rate $R$ is the number of bits transmitted per source symbol.

The encoder may be any function whatsoever — no structure, locality or computability is required — so a converse proved for this class applies to every conceivable algorithm. That generosity is what makes the negative half of the theorem meaningful.

Definition 4.2 (Achievable rate). A rate $R$ is achievable for the source if there exists a sequence of block codes of rate $R$ with $P_e^{(n)} \to 0$ as $n\to\infty$ .

Theorem 4.3 (Shannon's source coding theorem). Let $\{X_i\}$ be a stationary ergodic source with entropy rate $h$ .

Achievability. Every rate $R > h$ is achievable: there are block codes of rate $R$ with $P_e^{(n)} \to 0$ .
Converse. No rate $R < h$ is achievable. In fact every sequence of block codes of rate $R < h$ has $P_e^{(n)} \to 1$ .

Consequently the infimum of achievable rates equals $h$ exactly.

The two halves squeeze the answer from opposite sides. Achievability is a construction; the converse is a counting argument. Neither alone would be worth much: without the converse, $h$ would merely be a rate someone once attained; without achievability, it would be a bound nobody could reach.

Remark (Where the error probability went). The typical-set code of the previous part was lossless with a variable length; this theorem concerns fixed-length codes that may fail. The two formulations are equivalent in the limit, and we will meet both: fixed length with vanishing error here, variable length with zero error in the discussion of Kraft's inequality. What cannot be had is fixed length, zero error, and rate below $\log|\mathcal{X}|$ — that combination is forbidden by the pigeonhole principle at every $n$ .

Intuition. Entropy is the irreducible size of the data, in the way a suitcase has an irreducible volume. Good compression gets close to it; nothing gets past it, however the packing is organised.

If someone advertises a compressor that beats the entropy rate of your source on average and never errs, they are advertising a bijection from a set into a strictly smaller set.

Example 4.4 (Reading the theorem off a four-letter source). A memoryless source emits $a,b,c,d$ with probabilities $0.5, 0.25, 0.125, 0.125$ . What does the theorem promise, and what does it forbid?

Solution. The entropy is

H = 0.5(1) + 0.25(2) + 0.125(3) + 0.125(3) = 1.75 \text{ bits/symbol,}

using $-\log 0.5 = 1$ , $-\log 0.25 = 2$ , $-\log 0.125 = 3$ .

Promised. Any rate above $1.75$ , say $1.76$ , is achievable: for large $n$ there are codes using $1.76n$ bits per block whose failure probability is as small as desired. A file of $10^{6}$ symbols fits in about $1.75$ Mbit.

Forbidden. No scheme of rate $1.74$ can work: its error probability tends to $1$ , not merely away from $0$ .

Baseline. The naive fixed-length code uses $\log 4 = 2$ bits per symbol, so the available saving is $2 - 1.75 = 0.25$ bits per symbol, a $12.5\%$ reduction.

Sanity check: the probabilities are all powers of $1/2$ , so a symbol code should hit $1.75$ exactly. Assigning $a \mapsto 0$ , $b \mapsto 10$ , $c \mapsto 110$ , $d \mapsto 111$ gives expected length $0.5(1)+0.25(2)+0.125(3)+0.125(3) = 1.75$ — the entropy on the nose, with no block coding at all. Dyadic sources are the easy case; the theorem's asymptotics are what rescue the general one.□

Exercises for §4.1 →

4.2Achievability: Codes That Reach the Entropy

The achievability half is the typical-set code of the previous part, adapted from variable length to fixed length. The adaptation is where the error probability enters: with a fixed budget of $nR$ bits and no flag bit to spend, atypical strings cannot be encoded at all, so they are declared errors.

Theorem 4.5 (Achievability). Let the source be i.i.d. with entropy $H$ , and let $R > H$ . Then there is a sequence of block codes of rate $R$ with $P_e^{(n)} \to 0$ . Moreover the error probability can be made to decay exponentially in $n$ .

Proof. Choose $\varepsilon = (R-H)/2 > 0$ , so that $H + \varepsilon < R$ . Let $A_\varepsilon^{(n)}$ be the typical set. By clause (2) of the typical-set properties,

\bigl|A_\varepsilon^{(n)}\bigr| \;\le\; 2^{n(H+\varepsilon)} \;<\; 2^{nR} \;\le\; 2^{\lceil nR\rceil},

so for every $n$ there are strictly more codewords available than typical strings. Define $f_n$ to map the typical strings injectively onto distinct indices (possible by the count just made) and every atypical string to index $1$ ; define $g_n$ to invert $f_n$ on the image of the typical set.

Every typical string is then reconstructed exactly, so

P_e^{(n)} \;\le\; \Pr\bigl(X^n \notin A_\varepsilon^{(n)}\bigr) \;\longrightarrow\; 0

by clause (1). This proves achievability.

For the exponential refinement, note that $X^n \notin A_\varepsilon^{(n)}$ is the event that the average of the i.i.d. bounded variables $Y_i = -\log p(X_i)$ deviates from its mean by at least $\varepsilon$ . Hoeffding's inequality bounds this probability by $2\exp(-2n\varepsilon^{2}/c^{2})$ , where $c$ is the range of $Y_i$ ; hence $P_e^{(n)}$ decays exponentially in $n$ , at a rate controlled by $\varepsilon = (R-H)/2$ .∎

Corollary 4.6 (The infimum of achievable rates is at most the entropy). Every $R>h$ is achievable, so $\inf\{R : R \text{ achievable}\} \le h$ .

Intuition. You do not need a codeword for every string, only for the strings that actually show up. Reserve one index for "something weird happened" and spend the rest of the codebook on ordinary strings.

Since there are only about $2^{nH}$ ordinary strings, a codebook of $2^{nR}$ entries with $R>H$ is roomy — exponentially roomy, which is why the failure probability collapses so fast.

Example 4.7 (Sizing a codebook). A source has $H = 2.3$ bits/symbol on an eight-letter alphabet. For $n = 1000$ and $R = 2.4$ , how many typical strings are there, how many codewords, and how much slack is there?

Solution. With $\varepsilon = (R-H)/2 = 0.05$ , the typical set has at most $2^{n(H+\varepsilon)} = 2^{1000(2.35)} = 2^{2350}$ members.

The codebook has $2^{nR} = 2^{2400}$ entries.

The slack is a factor of $2^{2400-2350} = 2^{50} \approx 1.1\times 10^{15}$ : the codebook is a quadrillion times larger than it needs to be.

Sanity check: compare with the raw alternative. A fixed-length code with no modelling needs $\log 8 = 3$ bits per symbol, i.e. $2^{3000}$ codewords. The typical-set code uses $2^{2400}$ , saving $600$ bits per block — precisely $n(3 - 2.4)$ . The saving comes from the gap between $\log|\mathcal{X}| = 3$ and $H = 2.3$ , which is the source's redundancy.□

Pitfall (Achievability does not make the code practical). The proof exhibits a code by listing a set of size $2^{2350}$ . It says nothing about computing $f_n$ without that list. Every practical coder in this chapter — Huffman, arithmetic, Lempel–Ziv — exists because the achievability proof is useless as an implementation, and each attains the same asymptotic rate with resources that fit in a machine.

Exercises for §4.2 →

4.3The Converse: Why Entropy Cannot Be Beaten

The converse says that if you insist on a rate below $h$ , the decoder must fail, and fail almost always. It is proved by counting: a codebook of $2^{nR}$ entries cannot address $2^{nH}$ typical strings when $R<H$ .

Lemma 4.8 (Fano's inequality). Let $X$ be a random variable on a finite set $\mathcal{X}$ , let $Y$ be any other random variable, and let $\hat X = g(Y)$ be an estimate of $X$ from $Y$ . Put $P_e = \Pr(\hat X \neq X)$ . Then

H(P_e) + P_e \log\bigl(|\mathcal{X}|-1\bigr) \;\ge\; H(X\mid Y),

where $H(P_e) = -P_e\log P_e - (1-P_e)\log(1-P_e)$ is the binary entropy. In particular

P_e \;\ge\; \frac{H(X\mid Y) - 1}{\log|\mathcal{X}|} .

Proof. Let $E = \mathbf{1}\{\hat X \neq X\}$ be the error indicator. Expand $H(E, X \mid Y)$ by the chain rule in two ways:

H(E,X\mid Y) = H(X\mid Y) + H(E\mid X,Y) = H(E\mid Y) + H(X\mid E,Y).

Here $H(E\mid X,Y) = 0$ , because $\hat X$ is a function of $Y$ , so knowing $X$ and $Y$ determines $E$ . Also $H(E\mid Y) \le H(E) = H(P_e)$ , since conditioning cannot increase entropy. Finally

H(X\mid E,Y) = \Pr(E=0)\,H(X \mid Y, E=0) + \Pr(E=1)\,H(X\mid Y, E=1) \le 0 + P_e \log\bigl(|\mathcal{X}|-1\bigr),

because given $E=0$ we have $X = g(Y)$ exactly (zero entropy), while given $E=1$ the variable $X$ ranges over at most $|\mathcal{X}|-1$ values, whose entropy is at most $\log(|\mathcal{X}|-1)$ . Combining the three bounds with the chain-rule identity gives the inequality; the weaker form follows from $H(P_e)\le 1$ and $\log(|\mathcal{X}|-1) \le \log|\mathcal{X}|$ .∎

Fano's inequality is the formal version of "if uncertainty about $X$ remains after seeing $Y$ , any guess must sometimes be wrong". It is the standard engine of converses throughout information theory; here we use a sharper, purely combinatorial argument that yields $P_e \to 1$ rather than merely $P_e \not\to 0$ .

Theorem 4.9 (Converse to the source coding theorem). Let the source be i.i.d. with entropy $H$ , and let $R < H$ . Then every sequence of block codes of rate $R$ satisfies $P_e^{(n)} \to 1$ .

Proof. Fix such a sequence and let

B_n = \bigl\{ x^n \in \mathcal{X}^n : g_n(f_n(x^n)) = x^n \bigr\}

be the set of strings the code reconstructs correctly. Since $g_n$ is a function of an index taking at most $2^{\lceil nR\rceil}$ values, and distinct elements of $B_n$ must receive distinct indices, we have the crucial count

|B_n| \;\le\; 2^{\lceil nR\rceil} \;\le\; 2^{nR+1}.

Now choose $\varepsilon>0$ with $\varepsilon < (H-R)/2$ and split the success probability across the typical set:

1 - P_e^{(n)} = \Pr(B_n) = \Pr\bigl(B_n \cap A_\varepsilon^{(n)}\bigr) + \Pr\bigl(B_n \cap \overline{A_\varepsilon^{(n)}}\bigr).

For the first term, every typical string has $p(x^n) \le 2^{-n(H-\varepsilon)}$ , so

\Pr\bigl(B_n\cap A_\varepsilon^{(n)}\bigr) \;\le\; |B_n| \, 2^{-n(H-\varepsilon)} \;\le\; 2^{nR+1-n(H-\varepsilon)} \;=\; 2\cdot 2^{-n(H-R-\varepsilon)} .

Since $H - R - \varepsilon > \varepsilon > 0$ , this tends to $0$ exponentially fast. The second term is at most $\Pr\bigl(\overline{A_\varepsilon^{(n)}}\bigr)$ , which tends to $0$ by the AEP. Hence $1 - P_e^{(n)} \to 0$ , i.e. $P_e^{(n)}\to 1$ .∎

Corollary 4.10 (Entropy is exactly the compression limit). Combining achievability and the converse, the infimum of achievable rates for an i.i.d. source equals $H(X)$ ; for a stationary ergodic source it equals the entropy rate $h$ .

Intuition. A codebook with $2^{nR}$ entries has $2^{nR}$ pigeonholes. There are $2^{nH}$ typical strings — the ones that actually arrive. If $R<H$ , almost every arriving string shares its pigeonhole with others, and the decoder, seeing only the pigeonhole, cannot tell which one was sent.

The error tends to $1$ rather than to some middling value because the mismatch is exponential: the shortfall is a factor $2^{n(H-R)}$ , so the fraction of strings with a private pigeonhole is exponentially small.

Example 4.11 (Auditing a compression claim). A vendor claims a lossless compressor that maps every $1000$ -bit file from a fair-coin source to at most $900$ bits. Refute it, and quantify how often it must fail.

Solution. For a fair coin $H = 1$ bit/symbol, so the claimed rate is $R = 0.9 < 1 = H$ .

Counting. Outputs have length at most $900$ , so there are at most $2^{901}-1 < 2^{901}$ distinct outputs against $2^{1000}$ equally likely inputs. At most $2^{901}$ inputs can be recovered, a fraction

\frac{2^{901}}{2^{1000}} = 2^{-99} \approx 1.6\times 10^{-30}.

Failure rate. The failure probability is therefore at least $1 - 2^{-99}$ , indistinguishable from certainty.

Sanity check against the theorem. The converse predicts a success probability of at most $2\cdot 2^{-n(H-R-\varepsilon)}$ plus the atypical term, and with $H-R = 0.1$ and $n=1000$ that is about $2^{-99}$ — matching the direct count. Note also that the claim is refuted without the AEP: for a fair coin every string is typical, and plain pigeonhole suffices.□

Pitfall (Compressing one file is not compressing a source). It is entirely possible to map one particular $1000$ -bit file to $10$ bits. What is impossible is to do so for all of them at once: any injective map into shorter strings must lengthen at least as many files as it shortens. Claims of universal compression always trade on this confusion between a single input and a distribution over inputs.

Exercises for §4.3 →

4.4Lossless and Lossy Compression

Definition 4.12 (Lossless and lossy compression). A compression scheme is a pair of maps $(\text{enc}, \text{dec})$ . It is lossless on a set $S$ of inputs if $\text{dec}(\text{enc}(x)) = x$ for every $x\in S$ — the encoder is injective on $S$ and the decoder inverts it. It is lossy if the reconstruction is allowed to differ from the input, the discrepancy being measured by a distortion function $d(x,\hat x)$ whose expectation is held below a budget $D$ .

Lossless compression (gzip, PNG, FLAC, ZIP) is required for text, executables and scientific data, where a single flipped bit is a defect. Lossy compression (JPEG, MP3, H.264, Opus) discards information judged perceptually irrelevant and thereby escapes the entropy bound entirely — at the price of an irreversible change to the data.

The distinction is not a matter of degree: it is the difference between an injective map and a non-injective one. And injectivity alone forbids the thing amateurs most often claim.

Theorem 4.13 (No lossless code compresses everything). Let $C$ be any injective map from binary strings to binary strings. Then for every $n$ and every $k \ge 1$ , the fraction of strings $x$ of length $n$ with $|C(x)| \le n-k$ is less than $2^{-k+1}$ .

In particular no lossless compressor can shorten even half of the $n$ -bit inputs by as much as $2$ bits, and any compressor that shortens some inputs must lengthen others.

Proof. The strings of length at most $n-k$ number

\sum_{j=0}^{n-k} 2^{j} = 2^{n-k+1}-1 \;<\; 2^{n-k+1}.

Because $C$ is injective, distinct inputs of length $n$ receive distinct outputs, so at most $2^{n-k+1}-1$ of the $2^n$ inputs can have an output that short. The fraction is therefore less than $2^{n-k+1}/2^n = 2^{-k+1}$ .

For the final claim, take $k=0$ : the number of strings of length $< n$ is $2^n - 1 < 2^n$ , so at least one string of length $n$ must map to an output of length $\ge n$ . Iterating over all $n$ shows that a compressor that strictly shortens some inputs strictly lengthens others.∎

Intuition. Lossless compression is vacuum-packing: the suitcase shrinks, and everything is still inside when you open it. Lossy compression is deciding which souvenirs to leave behind — the case shrinks much more, and the decision is permanent.

The no-free-lunch theorem is just the observation that you cannot put $2^n$ distinct objects into fewer than $2^n$ distinct boxes. Compressors "work" because real files are not uniformly distributed over all bit strings; they are concentrated on a typical set.

Example 4.14 (Quantifying the no-free-lunch bound). Of all $1{,}000$ -bit files, what fraction can a lossless compressor possibly shrink to $990$ bits or fewer? To $500$ bits or fewer?

Solution. Apply the theorem with $n = 1000$ .

For $k = 10$ : the fraction is less than $2^{-9} = 1/512 \approx 0.2\%$ .

For $k = 500$ : the fraction is less than $2^{-499} \approx 6\times10^{-151}$ .

Sanity check: the numbers are consistent with everyday experience. gzip shrinks text by 60–70% not because the theorem is false but because text files are a vanishingly small, highly structured subset of all bit strings — exactly the typical set of a low-entropy source. Feed gzip the output of a good random number generator and the file grows by a few bytes, as the theorem requires.□

Remark (The lossy analogue). For lossy compression the entropy bound is replaced by the rate–distortion function $R(D) = \min I(X;\hat X)$ , the minimum over all conditional distributions $p(\hat x \mid x)$ meeting $E[d(X,\hat X)] \le D$ . It satisfies $R(0) = H(X)$ for discrete sources, so lossless compression is the $D=0$ endpoint of the lossy theory. Rate–distortion theory is developed in its own chapter; here we only note that all rates below $H$ are purchased with distortion.

Exercises for §4.4 →

4.5Redundancy, Models, and the Cost of Being Wrong

Every compressor is a probability model in disguise. Given a model $q$ over strings, the ideal codelength for $x$ is $\log(1/q(x))$ bits; given a coder, the lengths it produces define an implicit model $q(x) \approx 2^{-\ell(x)}$ . Compression performance is therefore entirely a question of how close the model is to the truth, and information theory measures that distance exactly.

Definition 4.15 (Redundancy). For a source with entropy $H$ coded at expected length $L$ , the absolute redundancy is $L - H$ bits per symbol and the relative redundancy is $(L-H)/L$ . For a fixed-length code over $\mathcal{X}$ the redundancy relative to the naive baseline is $\log|\mathcal{X}| - H$ , the part of each symbol that a perfect model would have predicted.

Definition 4.16 (Relative entropy). The relative entropy (Kullback–Leibler divergence) between mass functions $p$ and $q$ on $\mathcal{X}$ is

D(p\,\|\,q) = \sum_{x\in\mathcal{X}} p(x)\log\frac{p(x)}{q(x)},

with the conventions $0\log\frac0q = 0$ and $p\log\frac p0 = \infty$ .

Lemma 4.17 (Gibbs' inequality). $D(p\,\|\,q) \ge 0$ for all $p,q$ , with equality if and only if $p = q$ .

Proof. Let $S = \{x : p(x) > 0\}$ . Using $\log t = \ln t / \ln 2$ and Jensen's inequality for the concave function $\ln$ ,

-D(p\,\|\,q) = \sum_{x\in S} p(x)\log\frac{q(x)}{p(x)} \;\le\; \log\left(\sum_{x\in S} p(x)\frac{q(x)}{p(x)}\right) = \log\left(\sum_{x \in S} q(x)\right) \le \log 1 = 0 .

Hence $D(p\|q)\ge 0$ . Jensen's inequality is strict for the strictly concave $\log$ unless $q(x)/p(x)$ is constant on $S$ , and the final inequality is strict unless $q$ puts no mass outside $S$ ; both hold simultaneously exactly when $q = p$ .∎

Theorem 4.18 (The cost of the wrong model). Suppose a coder is designed for the model $q$ but the data are drawn from $p$ . Using the ideal codelengths $\ell(x) = \log\frac{1}{q(x)}$ , the expected length is

E_p[\ell(X)] = H(p) + D(p\,\|\,q) \;\ge\; H(p),

so the penalty for modelling $p$ as $q$ is exactly $D(p\|q)$ bits per symbol, and it is zero only if the model is right.

Proof. Expand the expectation and add and subtract $\log p(x)$ :

E_p\!\left[\log\frac1{q(X)}\right] = \sum_x p(x)\log\frac{1}{q(x)} = \sum_x p(x)\log\frac{1}{p(x)} + \sum_x p(x)\log\frac{p(x)}{q(x)} = H(p) + D(p\,\|\,q).

Non-negativity of the second term is Gibbs' inequality.∎

This is the single most useful formula in practical compression: it says that model error is measured in bits, on the same scale as the data, and that the two contributions — the source's own entropy and the modeller's mistake — simply add.

Intuition. Redundancy is "what you already knew". In aaaaaaa the next a is predictable, so sending it explicitly wastes the bits you spend on it.

A compressor is a predictor with a bill attached: every time it is surprised it pays $\log(1/q)$ bits. Being surprised is unavoidable at rate $H$ ; being surprised because your model is wrong costs an extra $D(p\|q)$ , and you pay it on every symbol.

Example 4.19 (Paying for a mismatched model). A binary source has $p(1) = 0.9$ . A compressor assumes a fair coin, $q(1) = q(0) = 0.5$ . What does it cost?

Solution. The true entropy is $H(p) = 0.469$ bits/symbol (computed earlier).

The divergence is

D(p\|q) = 0.9\log\frac{0.9}{0.5} + 0.1\log\frac{0.1}{0.5} = 0.9(0.8480) + 0.1(-2.3219) = 0.7632 - 0.2322 = 0.5310 \text{ bits.}

So the expected codelength is $0.469 + 0.531 = 1.000$ bits/symbol.

Sanity check: a coder built for a fair coin spends exactly $\log(1/0.5) = 1$ bit on every symbol regardless of what it sees, so its expected length is exactly $1$ — matching the theorem to the digit. The mismatched model throws away the entire $0.531$ bits per symbol of available compression.□

Example 4.20 (Redundancy of a source with memory). A binary source alternates deterministically: $ababab\dots$ of length $1000$ . What is its entropy rate, and how many bits does an ideal description need?

Solution. Conditioned on the previous symbol the next one is certain, so $H(X_n \mid X_{n-1}) = 0$ and the entropy rate is $h = 0$ .

An explicit description needs only the starting symbol ( $1$ bit) and the length ( $\lceil \log 1000\rceil = 10$ bits): about $11$ bits in total.

The per-symbol rate is $11/1000 = 0.011$ bits, which tends to $0 = h$ as the string lengthens.

Sanity check: a memoryless model of this source would see $p(a) = p(b) = 0.5$ and report a marginal entropy of $1$ bit per symbol, demanding $1000$ bits — a factor of $90$ worse. The gap is exactly the redundancy that the first-order model captures and the zeroth-order model misses, and it is why "entropy rate, not marginal entropy" is the operative phrase.□

Pitfall (Redundancy is relative to a model class). There is no model-free measure of how compressible a particular file is (that is the province of Kolmogorov complexity, which is uncomputable). A file with zero redundancy under a memoryless model may be extremely redundant under a Markov model — the digits of $\pi$ pass every statistical test a compressor applies and are nonetheless generated by a short program.

Exercises for §4.5 →

4.6Prefix Codes, Kraft's Inequality and the Entropy Bound

The theory so far speaks of blocks of length $n\to\infty$ and codebooks of astronomical size. Real compressors read a file once, symbol by symbol, and emit bits as they go. This part makes the transition: from block codes to symbol codes, where the combinatorial constraint is not a pigeonhole count but Kraft's inequality, and where the asymptotic bound $L \to H$ is replaced by the sharp finite bound $H \le L < H+1$ .

We now leave block codes behind. A symbol code assigns a binary string to each letter and codes a message by concatenation. The whole theory of such codes rests on one inequality.

Definition 4.21 (Symbol codes: non-singular, uniquely decodable, prefix). A symbol code is a map $C : \mathcal{X} \to \{0,1\}^{*}$ ; the string $C(x)$ is the codeword of $x$ and $\ell(x) = |C(x)|$ its length. The code is

non-singular if $x \neq x' \Rightarrow C(x) \neq C(x')$ ;
uniquely decodable if its extension to strings, $C(x_1\cdots x_n) = C(x_1)C(x_2)\cdots C(x_n)$ , is non-singular — no two distinct messages have the same concatenation;
prefix-free (or instantaneous) if no codeword is a prefix of another.

Every prefix code is uniquely decodable, and every uniquely decodable code is non-singular; both inclusions are strict.

Prefix codes are the ones worth building: they can be decoded left to right with no lookahead, each codeword being recognised the moment its last bit arrives. Geometrically, a prefix code is a set of leaves in a binary tree, one leaf per symbol, and no leaf on the path to another.

Theorem 4.22 (Kraft's inequality). If a binary prefix code has codeword lengths $\ell_1,\dots,\ell_m$ , then

\sum_{i=1}^{m} 2^{-\ell_i} \;\le\; 1 .

Conversely, given positive integers $\ell_1,\dots,\ell_m$ satisfying this inequality, there exists a binary prefix code with exactly those lengths.

Proof. Necessity. Associate with each codeword $c$ of length $\ell$ the dyadic interval

I(c) = \bigl[\,0.c,\; 0.c + 2^{-\ell}\,\bigr) \subseteq [0,1),

where $0.c$ is the binary fraction whose digits are the bits of $c$ . The interval has length exactly $2^{-\ell}$ . If $c$ is not a prefix of $c'$ and $c'$ is not a prefix of $c$ , then the two binary expansions differ at some position before both end, and $I(c) \cap I(c') = \varnothing$ : the intervals of a prefix code are pairwise disjoint. Being disjoint subintervals of $[0,1)$ , their total length is at most $1$ , which is the inequality.

Sufficiency. Order the lengths $\ell_1 \le \ell_2 \le \cdots \le \ell_m$ and define the cumulative sums

w_i = \sum_{j<i} 2^{-\ell_j} \in [0,1),

taking $w_1 = 0$ . Let $C(i)$ be the first $\ell_i$ bits of the binary expansion of $w_i$ , so that $I(C(i)) = [w_i, w_i + 2^{-\ell_i})$ — this is legitimate because $w_i$ is a multiple of $2^{-\ell_i}$ , each earlier term $2^{-\ell_j}$ with $\ell_j \le \ell_i$ being such a multiple. The Kraft sum being at most $1$ guarantees $w_i + 2^{-\ell_i} \le 1$ , so all these intervals fit inside $[0,1)$ , and by construction they are consecutive and disjoint. Disjointness of $I(C(i))$ and $I(C(j))$ forces neither codeword to be a prefix of the other, since a prefix relation would make one interval contain the other. Hence $C$ is a prefix code with the prescribed lengths.∎

Theorem 4.23 (Kraft–McMillan: unique decodability buys nothing). Every uniquely decodable code satisfies $\sum_i 2^{-\ell_i} \le 1$ .

Consequently the set of achievable length vectors is the same for uniquely decodable codes as for prefix codes: nothing is lost by insisting on instantaneous decoding.

Proof. Let $S = \sum_{i=1}^m 2^{-\ell_i}$ and let $L = \max_i \ell_i$ . For any integer $k \ge 1$ , expand the $k$ -th power:

S^k = \left(\sum_{x \in \mathcal{X}} 2^{-\ell(x)}\right)^{k} = \sum_{x_1,\dots,x_k \in \mathcal{X}} 2^{-\bigl(\ell(x_1)+\cdots+\ell(x_k)\bigr)} = \sum_{m=k}^{kL} a(m)\,2^{-m},

where $a(m)$ is the number of source strings of length $k$ whose concatenated encoding has exactly $m$ bits. Unique decodability means distinct length- $k$ strings give distinct binary strings, so $a(m)$ is at most the number of binary strings of length $m$ , namely $2^m$ . Therefore

S^k \;\le\; \sum_{m=k}^{kL} 2^{m}2^{-m} \;=\; kL - k + 1 \;\le\; kL .

Thus $S \le (kL)^{1/k}$ for every $k$ . Since $(kL)^{1/k} \to 1$ as $k\to\infty$ , we conclude $S \le 1$ .∎

That $k$ -th power trick is due to Karush, and it is the reason the rest of the chapter can talk about prefix codes without loss of generality. Kraft's inequality now converts the coding problem into a constrained optimisation: choose lengths $\ell_i$ minimising $\sum p_i \ell_i$ subject to $\sum 2^{-\ell_i} \le 1$ . Relaxing $\ell_i$ to real numbers, the solution is immediate.

Theorem 4.24 (Entropy is a lower bound on expected length). For any uniquely decodable binary code for a source with mass function $p$ , the expected codeword length $L = \sum_i p_i \ell_i$ satisfies

L \;\ge\; H(p),

with equality if and only if $p_i = 2^{-\ell_i}$ for every $i$ — that is, if and only if all probabilities are dyadic (integer powers of $1/2$ ).

Proof. By Kraft–McMillan, $c = \sum_i 2^{-\ell_i} \le 1$ . Define the probability mass function $r_i = 2^{-\ell_i}/c$ . Then

L - H(p) = \sum_i p_i \ell_i + \sum_i p_i \log p_i = \sum_i p_i \log \frac{p_i}{2^{-\ell_i}} = \sum_i p_i\log\frac{p_i}{c\,r_i} = D(p\,\|\,r) + \log\frac1c .

Both terms are non-negative: the first by Gibbs' inequality, the second because $c \le 1$ . Hence $L \ge H(p)$ . Equality requires $D(p\|r) = 0$ and $c=1$ , i.e. $p = r$ and $r_i = 2^{-\ell_i}$ , which is exactly $p_i = 2^{-\ell_i}$ .∎

Definition 4.25 (Shannon code). The Shannon code for $p$ assigns to symbol $i$ the length

\ell_i = \left\lceil \log \frac{1}{p_i} \right\rceil .

Theorem 4.26 (The fundamental bound $H \le L < H+1$ ). The Shannon lengths satisfy Kraft's inequality, so a prefix code with those lengths exists, and its expected length obeys

H(p) \;\le\; L \;<\; H(p) + 1 .

Hence the optimal expected length $L^{*}$ of any prefix code satisfies the same bounds.

Proof. Kraft. Since $\ell_i \ge \log(1/p_i)$ , we have $2^{-\ell_i} \le p_i$ , so $\sum_i 2^{-\ell_i} \le \sum_i p_i = 1$ . By the converse half of Kraft's inequality a prefix code with these lengths exists.

Upper bound. Since $\lceil t\rceil < t+1$ ,

L = \sum_i p_i\left\lceil \log\frac1{p_i}\right\rceil \;<\; \sum_i p_i\left(\log\frac1{p_i} + 1\right) = H(p) + 1 .

Lower bound. Immediate from Theorem Entropy is a lower bound on expected length, since the Shannon code is a prefix code.

Finally, the optimal code has $L^{*} \le L < H+1$ because the Shannon code is one candidate, and $L^{*} \ge H$ because Theorem Entropy is a lower bound on expected length applies to every uniquely decodable code.∎

Corollary 4.27 (Blocking removes the overhead). Apply an optimal prefix code to blocks of $n$ i.i.d. symbols. Writing $L_n^{*}$ for the optimal expected length per block,

H(X) \;\le\; \frac{L_n^{*}}{n} \;<\; H(X) + \frac1n ,

so the per-symbol length converges to the entropy. For a stationary source the same argument with $H(X_1,\dots,X_n)$ in place of $nH(X)$ gives $L_n^{*}/n \to h$ .

Proof. The block $X^n$ is a single random variable over the alphabet $\mathcal{X}^n$ with entropy $H(X_1,\dots,X_n) = nH(X)$ by independence. Applying the theorem to it gives $nH(X) \le L_n^{*} < nH(X)+1$ ; dividing by $n$ gives the claim. In the stationary case divide $H(X_1,\dots,X_n) \le L_n^{*} < H(X_1,\dots,X_n)+1$ by $n$ and use the definition of the entropy rate.∎

Intuition. Kraft's inequality is a budget. Every codeword of length $\ell$ costs $2^{-\ell}$ of a total budget of $1$ : short codewords are expensive, long ones cheap. Spending the whole budget optimally means buying a codeword of length $\log(1/p_i)$ for symbol $i$ — the more likely the symbol, the more you are willing to pay for a short name.

The " $+1$ " in $L < H+1$ is the rounding loss: codeword lengths are integers, but $\log(1/p_i)$ generally is not. Coding blocks of $n$ symbols amortises one rounding error over $n$ symbols, which is why the overhead is $1/n$ .

Example 4.28 (Kraft: which length vectors are legal?). Decide whether a binary prefix code exists with lengths (a) $\{1,2,3,3\}$ , (b) $\{1,2,2,3\}$ , (c) $\{2,2,2,2,2\}$ .

Solution. (a) $2^{-1}+2^{-2}+2^{-3}+2^{-3} = 0.5+0.25+0.125+0.125 = 1$ . Legal, and the budget is exactly exhausted — the code is complete (its tree has no unused leaves). Example: $0,10,110,111$ .

(b) $0.5 + 0.25+0.25+0.125 = 1.125 > 1$ . Illegal: no prefix code, and by Kraft–McMillan not even a uniquely decodable one.

(c) $5 \times 2^{-2} = 1.25 > 1$ . Illegal — with $2$ -bit codewords there are only $4$ leaves available for $5$ symbols.

Sanity check: in (c), replacing one length by $3$ gives $4(0.25) + 0.125 = 1.125$ , still illegal; lengths $\{2,2,2,3,3\}$ give $0.75+0.25 = 1$ , legal. The budget interpretation predicts exactly this: five symbols need at least $\lceil\log 5\rceil = 3$ bits in the worst case.□

Figure 4.29. Kraft's inequality made visible: the codewords

0,10,110,111

own disjoint dyadic intervals of lengths

\tfrac12,\tfrac14,\tfrac18,\tfrac18

, which exactly fill

[0,1)

Example 4.30 (Shannon code and its overhead). Build the Shannon code for $p = (0.45, 0.30, 0.15, 0.10)$ and compare $L$ to $H$ .

Solution. Compute $\log(1/p_i)$ and round up:

symbol	$p_i$	$\log(1/p_i)$	$\ell_i$
$a$	$0.45$	$1.152$	$2$
$b$	$0.30$	$1.737$	$2$
$c$	$0.15$	$2.737$	$3$
$d$	$0.10$	$3.322$	$4$

Kraft: $0.25+0.25+0.125+0.0625 = 0.6875 \le 1$ ✓, so the code exists; e.g. $a=00$ , $b=01$ , $c=100$ , $d=1010$ .

Expected length: $L = 0.45(2)+0.30(2)+0.15(3)+0.10(4) = 0.9+0.6+0.45+0.4 = 2.35$ bits.

Entropy: $H = 0.45(1.152)+0.30(1.737)+0.15(2.737)+0.10(3.322) = 0.518+0.521+0.411+0.332 = 1.782$ bits.

Sanity check: $1.782 \le 2.35 < 2.782$ ✓ — the bound holds, though with $0.57$ bits of slack. The Kraft sum is well under $1$ , which signals waste: the code is incomplete, so some codeword could be shortened. Huffman, in the next part, will find $L = 1.85$ for this same distribution, and no prefix code does better.□

Pitfall ( $L < H+1$ does not mean "within one bit of optimal"). The bound compares $L$ to the entropy, not to the best code. A code can satisfy $L<H+1$ and still be beaten by another code, as the example above shows ( $2.35$ versus Huffman's $1.85$ ). Only the Huffman code is guaranteed to be optimal, and even it can sit almost a full bit above $H$ when one symbol is very probable.

Exercises for §4.6 →

Common Mistakes

Reading the theorem as a statement about single messages. It is asymptotic in block length and probabilistic in the source. Individual short messages can beat $H$ or fall far short of it.
Confusing the source coding theorem with the channel coding theorem. Source coding removes redundancy to approach $h$ ; channel coding adds redundancy to approach capacity. They are dual, not the same.
**Using $H(X)$ for a source with memory.** The limit is the entropy *rate* $h = \lim H(X_n \mid X^{n-1})$ , which can be far below the marginal entropy: English has a marginal letter entropy above $4$ bits but an entropy rate near $1.3$ bits.
Forgetting the vanishing-error qualifier in the achievability half. Fixed-rate codes below $\log|\mathcal{X}|$ must sometimes fail; the theorem promises only that the failure probability tends to zero.
Believing the converse follows from Fano's inequality alone. Fano gives $P_e$ bounded away from zero; the exponential counting argument is what gives $P_e \to 1$ .
Assuming a smarter codebook could beat the count. The converse quantifies over *all* functions $f_n$ , computable or not. There is no algorithmic escape from a pigeonhole.
Expecting a compressor to shrink random or already-compressed data. The no-free-lunch theorem forbids it; the output of gzip run twice is slightly larger than run once.
Confusing non-singular with uniquely decodable. $\{0,1,01\}$ is non-singular but not uniquely decodable: `01` could be one symbol or two.
Believing unique decodability allows shorter codes than the prefix property. Kraft–McMillan says the achievable length vectors are identical; instantaneous decoding is free.
Reading Kraft's inequality as a statement about a particular code. It constrains the *multiset of lengths*. Any length vector satisfying it can be realised, and no code can violate it.
Ignoring model cost for small files. The $D(p\|q)$ penalty assumes a known model; if the model must be transmitted, its description length is charged to the file, which is why compression shines on large inputs.
**Comparing $L$ against $\log|\mathcal{X}|$ instead of $H$ . ** The naive baseline measures the saving; the entropy measures how much saving was left on the table.

About the practice questions. They check that you can carry out this chapter's computations correctly, and each one is graded on a single answer. They are not proof exercises: working through them confirms the mechanics, not that you could prove the results yourself. For that, re-read the statements above and try to reconstruct their proofs with the page closed.

← Entropy Rates and the AEP Huffman and Shannon–Fano Codes →

Helpful?