Symbol Codes

Unique decodability imposes stringent limits on the lengths of our codewords. We can only shorten some codewords at the expense of lengthening others, a balancing act quantified by the following.

The Kraft-McMillan inequality: if \(C\) is a uniquely decodable code for \(X\) then

\[ \sum 2^{-l(x)} [x \in \mathcal{A}_X] \le 1 \]

Moreover, given a set of lengths satisfying this inequality, we can construct a corresponding prefix code.

Proof: Define \(z(X) = \sum 2^{-l(x)} [x \in \mathcal{A}_X]\). We wish to show \(z(X) \le 1\).

Let \(N\) be a constant natural. Consider:

\[ z(X^N) = \sum 2^{-l(x)} [x \in \mathcal{A}_{X^N}] \]

We count this in two different ways. Firstly, by basic combinatorics, \(z(X^N) = z(X)^N\).

Secondly, if \(a(N, k)\) denotes the number of strings of length \(N\) with a \(k\)-bit encoding, then:

\[ z(X^N) = \sum 2^{-k} a(N, k) \]

Since \(C\) is uniquely decodable, \(a(N, k) \le 2^k\) for all \(k\). Furthermore, \(a(N, k) = 0\) for \(k > N l_\max\) where

\[ l_\max = \max \{ l(x) : x \in \mathcal{A}_X \} \]

Thus:

\[ \sum 2^{-k} a(N, k) \le N l_\max \]

Combining the two:

\[ z(X)^N = z(X^N) \le N l_\max \]

The right-hand side grows linearly with \(N\). Hence \(z(X) \le 1\), otherwise the left-hand side grows exponentially with \(N\) and must eventually exceed the right-hand side.

Conversely, suppose we are given lengths satisfying the Kraft inequality.

Sort them in increasing order and group together identical lengths, so that we have \(a_k\) copies of the length \(l_k\) and \(l_0 < …​ < l_n\).

Reset a binary counter of length \(l_0\). Pick its first \(a_0\) values to be codewords.

For \(0 < k \le n\), suppose we have already generated codewords of lengths \(l_i\) for all \(i < k\), and that we have a binary counter showing some value. Increment the counter, append \(l_k - l_{k-1}\) zero bits to the counter, then pick the next \(a_k\) values of the counter to be codewords.

The binary counter ensures our code is prefix, and the Kraft inequality guarantees the binary counter never overflows. For example:

\[ a_0 2^{-l_0} + a_1 2^{-l_1} + …​ + a_n 2^{-l_n} \le 1 \]

Mulitplying both sides by \(2^{l_0}\) yields:

\[ a_0 + a_1 2^{l_0 - l_1} + …​ + a_n 2^{l_0 - l_n} \le 2^{l_0} \]

Thus an \(l_0\)-bit counter will provide enough distinct values to get started. Mulitplying further by \(2^{l_1 - l_0}\):

\[ a_1 + a_2 2^{l_1-l_2} …​ + a_n 2^{l_1 - l_n} \le 2^{l_1} - a_0 2^{l_1 - l_0} \]

which means an \(l_1\)-bit counter can supply enough values for \(a_1\) codewords of length \(l_1\) even after accounting for those values forbidden by the \(a_0\) codewords of length \(l_0\). We induct to show this for all \(k\).

If we have equality then \(C\) is called a complete code.

Given two probability distributions \(P(x), Q(x)\) over the same alphabet \(\mathcal{A}_X\), the relative entropy or Kullback-Leibler divergence between them is:

\[ D_{KL}(P || Q) = \sum P(x) \lg \frac{P(x)}{Q(x)} \]

Relative entropy is not necessarily symmetric. But it does satisfy:

Gibb’s inequality:

\[ D_{KL}(P || Q) \ge 0 \]

with equality if and only if \(P = Q\).

Proof: Apply Jensen’s inequality using the function \(f(x) = - \lg x\).

Jensen’s inequality: Let \(f\) be a convex function. Then \(E[f(X)] \ge f(E[X])\).

Let \(z = \sum 2^{-l(x)} [x \in \mathcal{A}_X]\). The implicit probabilities defined by codelengths are given by \[ Q(x) = 2^{-l(x)} / z \] for all \(x \in \mathcal{A}_X\).

Then:

\[ L(C,X) = \sum P(x) l(x) = \sum -P(x) \lg Q(x) - \lg z \]

By Gibb’s inequality and Kraft’s inequality:

\[ L(C,X) \ge \sum -P(x) \lg P(x) - \lg z \ge H(X) \]

and \(L(C, X) = H(X)\) if and only if \(z = 1\) and \(l(x) = \lg 1/P(x) = h(x)\).

In other words, the expected length of any code is bounded below by \(H(X)\). We attain \(H(X)\) when \(P(x) = Q(x)\) for all \(x\).

Theorem: For any random variable \(X\) there exists a prefix code \(C\) such that:

\[ H(X) \le L(C,X) < H(X) + 1 \]

Proof: Set \(l(x) = \lceil h(x) \rceil\). Then

\[ \sum 2^{-l(x)} \le \sum 2^{-h(x)} = \sum P(x) = 1\]

Since the Kraft inequality is satisfied, a prefix code with these lengths exists. Also:

\[ L(C,X) = \sum P(x) \lceil h(x) \rceil < \sum P(x) (h(x) + 1) = H(X) + 1 \]

We’ve seen that for lossy compression, we can achieve \(H(X)\) bits per symbol and no better. Lossless compression turns out to be similar: we can do no better than \(H(X)\) bits per symbol, and we can always do better than \(H(X) + 1\) bits per symbol.

Unlikely lossy compression, these bounds aren’t just theory. this algorithm, due to Shannon, is practical. However, it may not be optimal. For example, suppose the symbols A, B, C each have a 1/3 chance of occurring. Since \(\lceil \lg 3 \rceil = 2\), we’d assign a 2-bit codeword to each symbol, but we can easily do better by changing one of them to a 1-bit codeword. See also Fano’s method, which suffers from a similar affliction.]

Happily there is a better algorithm that always produces an optimal symbol code.

What can we say about an optimal prefix code for \(X\)? Namely, a prefix code \(C\) that minimizes \(L(C,X)\)?

If there is only one symbol then finding an optimal code is trivial, so assume at least two symbols. Take the least probable symbol \(x_0\), breaking any ties arbitrarily. To minimize \(L(C,X)\), we must give \(x_0\) one of the longest codewords, that is, the codeword \(c\) for \(x_0\) must have length:

\[ l_\max = \max \{ l(x) : x \in \mathcal{A}_X \} \]

If we remove the last bit of \(c\), we must have the prefix of some other codeword of \(C\), otherwise we could do without the last bit to get a better code than \(C\); a contradiction. Since \(c\) has length \(l_\max\), this other codeword must be \(c\) with its last bit flipped.

Label these two codewords \(c_0, c_1\), and let \(c'\) be their common prefix. Take the second least probable symbol \(x_1\), again breaking any ties arbitrarily. If \(x_0, x_1\) do not already correspond to \(c_0, c_1\), we swap codewords so they do. This preserves \(L(C,X)\) because \(C\) is optimal; all such swaps must involve codewords of length \(l_\max\).

Consider the random variable \(X'\) that is identical to \(X\) except that instead of the symbols \(x_0\) and \(x_1\) with probabilities \(p_0\) and \(p_1\), we have a single symbol \(x'\) with probability \(p_0 + p_1\). We may encode \(X'\) with a code \(C'\) that is identical to \(C\) except we use \(c'\) to encode \(x'\). Then \(L(C,X) = L(C',X') + p_0 + p_1\).

The code \(C'\) is also optimal. For suppose \(L(D',X') < L(C',X')\) for some code \(D'\). Then let \(d'\) be the encoding of \(x'\) under \(D'\). If we map \(x_0\) and \(x_1\) to \(d'\) followed by one bit, we have a code \(D\) for \(X\) satisfying:

\[ L(D,X) = L(D',X') + p_0 + p_1 < L(C',X') + p_0 + p_1 = L(C,X) \]

which is impossible since \(C\) is optimal.

These observations lead to Huffman coding: an algorithm that produces an optimal coding. Starting with the symbols of \(X\), repeatedly take the two most improbable symbols, breaking ties arbitrarily, label them 0 and 1, then treat them as a single symbol with their combined probability.

Eventually, only one symbol remains. The codeword for a symbol of \(X\) can be recovered by reading the labels as we retrace our footsteps. This algorithm is usually described as a bottom-up construction of a binary tree, which is reflected in our Haskell.

If we insist that all codewords have the same length, then the Latin alphabet needs 5 bits per symbol; see the Baudot code and Bacon’s cipher. For the english distribution, both Shannon and Huffman codes have less than 5 expected bits per symbol, though Huffman gets much closer to the entropy, which is the theoretical limit.

Symbol codes fare poorly on lopsided distributions like the following. The expected length is about 90 times larger than the entropy!

Schemes like run-length encoding would perform well here, but are forbidden when each symbol must be encoded individually.

Nonetheless, Huffman coding is easy to implement and often effective in practice. We demonstrate on some randomly generated english strings: