The noiseless coding theorem

 

Definitions:

A source is a stream of words from a set W = {w1, w2, . . . , wM}.

Let Xi denote the ith word produced by a source. The source is said to be memoryless if for each word wj Î W, the probability P(Xi =wj) = pj is independent of i, that is, the Xi are independent and identically distributed random variables.

The entropy of a memoryless source is H = −.

A code is a map f from W to A*, the set of all finite strings of elements of A where A is a finite set called the alphabet.

For each source word wj Î W, the string f(wj) is a codeword.

The length of the codeword f(wj ), denoted |f(wj)|, is the number of symbols in the string.

A message is any finite string of source words. If m = v1v2 . . . vr is a message, then its encoding is obtained by concatenation: f(m) = f(v1)f(v2) . . . f(vr).

The average length of a code f is .

A code is uniquely decodable if every string from A*  is the image of at most one message.

A prefix code is a code such that there do not exist distinct words wi and wj such that f(wi) is an initial segment, or prefix, of f(wj ).

Facts:

1. Prefix codes are uniquely decodable.

2. Prefix codes have the advantage of being instantaneous. That is, they can be decoded online without looking at future codewords.

3. Kraft’s inequality: A prefix code f:W → A* with codeword length |f(wi)| = li for i = 1, 2, . . . , M exists if and only if , where n is the size of the alphabet A.

4. Macmillan’s inequality: If a uniquely decodable code f:W → A*  with codeword lengths l1, l2, . . . , lM exists, then , where n is the size of the alphabet A.

5. A uniquely decodable code with prescribed word lengths exists if and only if a prefix code with the same word lengths exists. As a result, attention can be restricted to prefix codes.

6. Shannon’s noiseless coding theorem: For a memoryless source of entropy H, any uniquely decodable code for the source into an alphabet of size n must have average length at least H log2 n. Moreover, there exists such a code having average length less than .

7. For a memoryless source, a prefix code with smallest possible average length can be constructed by the Huffman coding algorithm.

Examples:

1. The code that maps the letters A, B, C, D to 1, 01, 001, 0001, respectively, is a prefix code on this set of four letters.

2. The code that maps the letters A, B, C, D to 11, 111, 11111, 111111, respectively, is not a prefix code since the code for A forms the first part of the code for B (and for the codes for C and D as well). It is also not uniquely decodable since a bit string can correspond to more than one string of the letters A, B, C, D. For example, 11111 corresponds to AB, BA, and C.