Huffman codes

Construction

Optimality

The optimality of the Huffman code hinges on the following two properties of optimal prefix-free codes:

Achieving Shannon's limit

Using Huffman codes to encoder every single symbol from ${\mathcal {X}}$ can potentially incur a large penalty since the expected length can be at most 1 D-ary digit away from the entropy bound (using base-$D$ logarithm). If we group symbols together $n$ at a time, we can achieve the Shannon limit to arbitrary precision.

The idea behind achieving Shannon's compression limit is to use a larger source alphabet. If take $n$ symbols at a time and create a Huffman code, we are essentially using the larger input alphabet ${\mathcal {X}}^{n}$. Using the bounds for Huffman code, the expected length $L_{n}$ is given by

$H_{D}(X^{n})\leq L_{n}<H_{D}(X^{n})+1$.

Here, $L_{n}$ accounts for the encoding of $n$ symbols. We can normalize the inequality and obtain a tighter expression:

${\frac {1}{n}}H_{D}(X^{n})\leq L_{n}<{\frac {1}{n}}[H_{D}(X^{n})+1]$.

Since we are encoding $n$ independent and identically distributed symbols at a time, the joint entropy $H(X^{n})=nH(X)$. Hence,

$H_{D}(X)\leq {\frac {1}{n}}L_{n}<H_{D}(X)+{\frac {1}{n}}$,

where the upper bound can be made to approach $H_{D}(X)$ by letting $n$ be sufficiently large.

The proof above is representative of many arguments in information theory that take the blocklength $n$ to arbitrarily large values. In that respect, we can look at $H(X)$ as an asymptotic compression limit. However, it is also important to keep in mind that directly applying the above construction is very impractical. If we take the English alphabet, with 26 letters, and group them five-at-a-time, then the effective alphabet blows up quickly to above 10 million! Fortunately, more modern coding schemes exist that approach the entropy bound without the heavy exponential overhead. The interested student is encouraged to look up "arithmetic coding."