0.13 Coding  (Page 15/22)

Since the entropy defines the smallest number of bits that can be used to encode a source, it can be used to definethe efficiency of a code

Thus the efficiency of the naive code [link] is $1.75/2=0.875$ while the efficiency of the variable rate code [link] is 1. Shannon's source coding theorem says that ifan independent source has entropy $H$ , then there exists a prefix code in which the averagenumber of bits per symbol is between $H$ and $H+1$ . Moreover, there is no uniquely decodable codethat has smaller average length. Thus, if $N$ symbols (each with entropy $H$ ) are compressed into less than $NH$ bits, information is lost, while information need not be lost if $N(H+1)$ bits are used. Shannon has defined the goal towardswhich all codes aspire, but provides no way of finding good codes for any particular case.

Fortunately, D. A. Huffman proposed an organized procedure to build variable-length codes that are as efficient as possible.Given a set of symbols and their probabilities, the procedure is as follows:

1. List the symbols in order of decreasing probability. These are the original “nodes.”
2. Find the two nodes with the smallest probabilities, and combine them into one new node, with probability equalto the sum of the two. Connect the new nodes to the old ones with “branches” (lines).
3. Continue combining the pairs of nodes with the smallest probabilities. (If there are ties, pick anyof the tied symbols).
4. Place a 0 or a 1 along each branch. The path from the rightmost node to the original symbol defines a binary list,which is the code word for that symbol.

This procedure is probably easiest to understand by working through an example. Consider again the $N=4$ code from Example [link] (a) in which the symbols have probabilities $p\left(x_1\right)=0.5$ , $p\left(x_2\right)=0.25$ , and $p\left(x_3\right)=p\left(x_4\right)=0.125$ . Following the foregoing procedure leads to the chart shown in [link] . In the first step, $x_3$ and $x_4$ are combined to form a new node with probability equal to $0.25$ (the sum $p\left(x_3\right)+p\left(x_4\right)$ ). Then this new node is combined with $x_2$ to form a new node with probability $0.5$ . Finally, this is combined with $x_1$ to form the rightmost node. Each branch is now labelled. The convention used in [link] is to place a 1 on the top and a 0 on the bottom (assigning the binary digits in another order justrelabels the code). The Huffman code for this source can be read from the chart. Reading from the right-hand side, $x_1$ corresponds to 1, $x_2$ corresponds 01, $x_3$ to 001 and $x_4$ to 000. This is the same code as in [link] .

The Huffman procedure with a consistent branch labelling convention always leads to a prefix code because all the symbols end the same (except for the maximal length symbol $x_4$ ). More importantly, it always leads to a code that has average lengthvery near the optimal.