8.3 Binary codes: huffman codes for source coding

In 1838, Samuel Morse was struggling with the problem of designing an efficient code for transmitting information over telegraph lines. He reasoned that an efficient code would use short code words for common letters and long code words for uncommon letters. (Can you see the profit motive at work?) In order to turn this reasoned principle into workable practice, Morse rummaged around in the composition trays for typeface in a printshop. He discovered that typesetters use many more $e^{\text{'}}s$ than s's. He then formed a table that showed the relative frequency with which each letter was used. His ingenious, variable-length Morse code assigned short codes to likely letters (like “dot” for $e^{\text{'}}$ ) and long codes to unlikely letters (like “dash dash dot dot” for $z^{\text{'}}$ ). We now know that Morse came within about 15% of the theoretical minimum for the average code word length for English language text.

A Variation on Morse's Experiment. In order to set the stage for our study of efficient source codes, let's run a variation on Morse's experiment to see if we can independently arrive at a way of designing codes. Instead of giving ourselves a composition tray, let's start with a communication source that generates five symbols or letters $S_0,S_1,S_2,S_3,S_4$ . We run the source for 100 transmissions and observe the following numbers of transmissions for each symbol:

We will assume that these “source statistics” are typical, meaning that 1000 transmissions would yield 500 $S_0^{\text{'}}s$ and so on.

The most primitive binary code we could build for our source would use three bits for each symbol:

This code is inefficient in two ways. First, it leaves three illegal code words that correspond to no source symbol. Second, it uses the same code word length for an unlikely symbol (like $S_4$ ) that it uses for a likely symbol (like $S_0$ ). The first defect we can correct by concatenating consecutive symbols into symbol blocks, or composite symbols. If we form a composite symbol consisting of $M$ source symbols, then a typical composite symbol is $S_1{S}_0{S}_1{S}_4{S}_2{S}_3{S}_1{S}_2{S}_0$ . The number of such composite symbols that can be generated is $5^M$ . The binary code for these $5^M$ composite symbols must contain $N$ binary digits where

The number of bits per source symbol is

This scheme improves on the best variable length code of Table 2 from "Binary Codes: From Symbols to Binary Codes" by 0.08 bits/symbol.

Now let's reason, as Morse did, that an efficient code would use short codes for likely symbols and long codes for unlikely symbols. Let's pick code#5 from Table 2 from "Binary Codes: From Symbols to Binary Codes" for this purpose:

This is a variable-length code. If we use this code on the 100 symbols that generated our source statistic, the average number of bits/symbol is