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'se'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 ' e ' ) and long codes to unlikely letters (like “dash dash dot dot” for z ' z ' ). 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 S0,S1,S2,S3,S4S0,S1,S2,S3,S4. 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 S0'sS0'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 S 4 ) that it uses for a likely symbol (like S 0 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 M source symbols, then a typical composite symbol is S1S0S1S4S2S3S1S2S0S1S0S1S4S2S3S1S2S0. The number of such composite symbols that can be generated is 5 M 5 M . The binary code for these 5 M 5 M composite symbols must contain N 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

Entropy. So far, each ad hoc scheme we have tried has produced an improvement in the average number of bits/symbol. How far can this go? The answer is given by Shannon's source coding theorem, which says that the minimum number of bits/symbol is

where p_i is the probability that symbol S_i is generated and -∑pilog2pi-∑pilog2pi is a fundamental property of the source called entropy. For our five-symbol example, the table of p_i and -logpi-logpi is given in Table 2. The entropy is 1.861, and the bound on bits/symbol is

Code #5#5 comes within 0.039 of this lower bound. As we will see in the next paragraphs, this is as close as we can come without coding composite symbols.

Huffman Codes. In the late 1950s1950s, David Huffman discovered an algorithm for designing variable-length codes that minimize the average number of bits/symbol. Huffman's algorithm uses a principle of optimality that says, “the optimal code for M M letters has imbedded in it the optimal code for the M-1M-1 letters that result from aggregating the two least likely symbols.” When this principle is iterated, then we have an algorithm for generating the binary tree for a Huffman code:

This tree is now labeled with 1's and 0's to obtain the Huffman code. The labeling procedure is to label each right branch with a 1 and each left branch with a 0. The procedure for laying out symbols and constructing Huffman trees and codes is illustrated in the following examples.

Example 1

Consider the source statistics

Symbol S 0 S 1 S 2 S 3 S 4 Probability 0.5 0.2 0.2 0.05 0.05 Symbol S 0 S 1 S 2 S 3 S 4 Probability 0.5 0.2 0.2 0.05 0.05 (9)

for which the Huffman algorithm produces the following binary tree and its corresponding code:

Figure 2

Example 2

The Huffman code for the source statistics

Symbol S 0 S 1 S 2 S 3 S 4 Probability 0.75 0.075 0.075 0.05 0.05 Symbol S 0 S 1 S 2 S 3 S 4 Probability 0.75 0.075 0.075 0.05 0.05 (10)

is illustrated next:

Figure 3

Coding a FAX Machine. Symbols can arise in unusual ways and be defined quite arbitrarily. To illustrate this point, we consider the design of a hypothetical FAX machine. For our design we will assume that a laser scanner reads a page of black and white text or pictures, producing a high voltage for a black spot and a low voltage for a white spot. We will also assume that the laser scanner resolves the page at 1024 lines, with 1024 spots/line. This means that each page is represented by a two-dimensional array, or matrix, of pixels (picture elements), each pixel being 1 or 0. If we simply transmitted these l's and O'sO's, then we would need 1024×1024=1,059,5761024×1024=1,059,576 bits. If these were transmitted over a 9600 baud phone line, then it would take almost 2 minutes to transmit the FAX. This is a long time.

Let's think about a typical scan line for a printed page. It will contain long runs of 0's, corresponding to long runs of white, interrupted by short bursts of l's, corresponding to short runs of black where the scanner encounters a line or a part of a letter. So why not try to define a symbol to be “a run of k k 0's" and code these runs? The resulting code is called a “run length code.” Let's define eight symbols, corresponding to run lengths from 0 to 7 (a run length of 0 is a 1):

If we simply used a simple three-bit binary code for these eight symbols, then for each scan line we would generate anywhere from 3×10243×1024 bits (for a scan line consisting of all 1's) to 3×1024/7≅4003×1024/7≅400 bits (for a scan line consisting of all 0's). But what if we ran an experiment to determine the relative frequency of the run lengths S 0 S 0 through S 7 S 7 and used a Huffman code to “run length encode” the run lengths? The following problem explores this possibility and produces an efficient FAX code.

Exercise 5

An experiment conducted on FAXed documents produces the following statistics for run lengths of white ranging from 0 to 7:

Symbol S 0 S 1 S 2 S 3 S 4 S 5 S 6 S 7 Probability 0.01 0.06 0.1 0.1 0.2 0.15 0.15 0.2 Symbol S 0 S 1 S 2 S 3 S 4 S 5 S 6 S 7 Probability 0.01 0.06 0.1 0.1 0.2 0.15 0.15 0.2 (13)

These statistics indicate that only 1% of a typical page is black. Construct the Huffman code for this source. Use your Huffman code to code and decode these scan lines:

Figure 4

Footer

This work is licensed by Louis Scharf under a Creative Commons Attribution License (CC-BY 3.0), and is an Open Educational Resource.

Last edited by Daniel Williamson on Sep 16, 2009 1:05 pm GMT-5.