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.