Shannon’s noiseless coding theorem

We are working with messages written in an alphabet of symbols x_{1}, …, x_{n} which occur with probabilities p_{1}, …, p_{n}. We have defined the entropy E of this set of probabilities to be

E = − ∑_{i=1}^{n} p_{i} log_{2} p_{i}.

These pages give a proof of an important special case of Shannon’s theorem, which holds for any uniquely decipherable code. We will prove it for prefix codes, which are defined as follows:

Definition: A (binary) prefix code is an assignment of binary strings (strings of 0s and 1s, “code words”) to symbols in the source alphabet so that no code word occurs as the beginning of another code word.

Note that message written in a prefix code can be unambiguously decoded by “slicing off” code words as they occur.

Theorem: For any binary prefix code encoding x_{1}, …, x_{n} the average length of a word must be greater than E. More explicitly, setting ℓ_{i} as the length of the code word for x_{i},

∑_{i=1}^{n} p_{i}ℓ_{i} ≥ E.

Our proof of this theorem will involve two lemmas.

Lemma 1: (Gibbs’ inequality). Suppose p_{1}, …, p_{n} is a probability distribution (i.e. each p_{i} ≥ 0 and ∑_{i} p_{i} = 1). Then for any other probability distribution q_{1}, …, q_{n} with the same number of elements,

∑_{i=1}^{n} p_{i} log_{2} p_{i} ≥ ∑_{i=1}^{n} p_{i} log_{2} q_{i}.

(Note: the inequality is usually stated

− ∑_{i=1}^{n} p_{i} log_{2} p_{i} ≤ − ∑_{i=1}^{n} p_{i} log_{2} q_{i}.

Our formulation avoids many minus signs, even though the numbers involved are both negative. For a heuristic motivation consider the case where all the p_{i} are equal. Each p_{i} = \frac{1}{n} and

∑_{i=1}^{n} p_{i} log_{2} p_{i} = ∑_{i=1}^{n} log_{2} p_{i} = log_{2}(p_{1} · p_{2} · . . . · p_{n}).

Substituting q_{1}, … q_{n} for p_{1}, … p_{n} gives log_{2}(q_{1} · q_{2} · . . . · q_{n}). And we know that when the sum of the side-lengths is fixed, the maximum volume of a rectangular solid is obtained when all the sides are equal.)

Proof: (from http : //en.wikipedia.org/wiki/Gibbs%27 inequality)

Since log_{2} p_{i} = \frac{ln p_{i}}{ln 2} and ln 2 > 0 it is enough to prove the inequality with log_{2} replaced by ln wherever it occurs.

We use the following property of the natural logarithm:

ln x ≤ x − 1 for all x > 0, and ln x = x − 1 only when x = 1.

In order to avoid zero denominators in the following calculation, we set I = {i|p_{i} > 0}, the set of indices for which p_{i} is non-zero. Then we write

∑_{i∈I} p_{i} ln \frac{q_{i}}{p_{i}} ≤ ∑_{i∈I} p_{i}(\frac{q_{i}}{p_{i}} − 1) = ∑_{i∈I} q_{i} + ∑_{i∈I} p_{i} = ∑_{i∈I} q_{i} + 1 ≤ 0.

Since ln \frac{q_{i}}{p_{i}} = ln q_{i} − ln p_{i}, this chain of inequalities gives

∑_{i∈I} p_{i} ln q_{i} ≤ ∑_{i∈I} p_{i} ln p_{i}.

Now ∑_{i∈I} p_{i} ln p_{i} = ∑_{i=1}^{n} p_{i} ln p_{i} since the new terms all have p_{i} = 0; and ∑_{i∈I} p_{i} ln q_{i} ≥ ∑_{i=1}^{n} p_{i} ln q_{i} since new terms are ≤ 0. I.e.

∑_{i=1}^{n} p_{i} ln q_{i} ≤ ∑_{i∈I} p_{i} ln q_{i} ≤ ∑_{i∈I} p_{i} ln p_{i} = ∑_{i=1}^{n} p_{i} ln p_{i}

yielding Gibbs’ inequality.

Lemma 2: (Kraft’s inequality for binary prefix codes) Let x_{1}, …, x_{n} be the symbols in our alphabet, and suppose we have encoded them as binary words using a prefix code. Let ℓ_{1}, …, ℓ_{n} be the lengths of the words corresponding to x_{1}, …, x_{n}. Then

∑_{i=1}^{n} 2−ℓ^{i} ≤ 1.

Proof: Note that a (binary) prefix code can always be represented as a binary tree: as a word is read, the tree branches right or left according as the next bit is 0 or 1. Each word occurs at the end of a unique “branch.”

Set L = max_{i} ℓ_{i}. Then the tree corresponding to our prefix code can be extended to a tree where every branch has length L, and there are 2^{L} branches. A code word of length ℓ_{i} corresponds to pruning off from this tree all the possible extensions of the corresponding branch. There are 2^{L−ℓ_{i}} of these. The total number of deleted branches is then ∑_{i} 2^{L−ℓ_{i}}; since this sum must be smaller than the total number of branches, we have

∑_{i=1}^{n} 2L − ℓ^{i} = 2L ∑_{i=1}^{n} 2−ℓ^{i} ≤ 2L,

so ∑_{i=1}^{n} 2−ℓ^{i} ≤ 1, Kraft’s inequality.

Proof of Shannon’s theorem: Take x_{1}, …, x_{n} and p_{1}, …, p_{n} as in the statement, suppose the x_{i} have been encoded in a binary prefix code, and let ℓ_{i} be the length of the code word for x_{i}. Then by Kraft’s inequality ∑_{i} 2^{−ℓ_{i}} ≤ 1. Call this number 1/C, so that C2^{−ℓ_{1}}, …, C2^{−ℓ_{n}} is a probability distribution, and can play the role of {q_{i}} in Gibbs’ inequality, which then tells us

∑_{i=1}^{n} p_{i} log_{2} p_{i} ≥ ∑_{i=1}^{n} p_{i} log_{2}(C2^{−ℓ_{i}}) = ∑_{i=1}^{n} p_{i}(log_{2} C − ℓ_{i}) = log_{2} C − ∑_{i=1}^{n} p_{i}ℓ_{i}.

Now put back the minus signs and remember that since 1/C ≤ 1 we have C ≥ 1 and log_{2} C ≥ 0. We get

∑_{i=1}^{n} p_{i}ℓ_{i} ≥ − ∑_{i=1}^{n} p_{i} log_{2} p_{i} + log_{2} C ≥ − ∑_{i=1}^{n} p_{i} log_{2} p_{i},

as required.