Lec 2 X
Lec 2 X
Lec 2 X
Lecture 2:
Uniquely Decodable and Instantaneous Codes
Sam Roweis
Lets focus on the lossless data compression problem for now, and
not worry about noisy channel coding for now. In practice these
two problems are handeled separately, i.e. we first design an
efficient code for the source (removing source redundancy) and
then (if necessary) we design a channel code to help us transmit
the source code over the channel (adding redundancy).
Assumptions (for now):
1. the channel is perfectly noiseless
i.e. the receiver sees exactly the encoders output
2. we always require the output of the decoder to exactly match the
original sequence X.
3. X is generated according to a fixed probabilistic model, p(X)
We will measure the quality of our compression scheme (called a
code) by examining the average length of the encoded string Z,
averaged over p(X).
Examples
10
11
111
0
10
110
0
01
011
0
01
11
More Examples
Code E Code F Code G
a
b
c
d
100
101
010
011
0
001
010
100
0
01
011
1110
{w A+
X | uw = v where u C, v Cn1
or u Cn1, v C}
Finally, define
C = C 1 C2 C3
Theorem: the code C is uniquely decodable if and only if
C and C are disjoint.
We wont both much with this theorem,
since as well see it isnt of much practical use.
Existence of Codes
Since we hope to compress data, we would like codes that are
uniquely decodable and whose codewords are short.
Also, wed like to use instantaneous codes where possible since they
are easiest and most efficient to decode.
If we could make all the codewords really short, life would be really
easy. Too easy. Why?
Because there are only a few possible short codewords and we cant
reuse them or else our code wouldnt be decodable.
Instead, making some codewords short will require that other
codewords be long, if the code is to be uniquely decodable.
Question 1: What sets of codeword lengths are possible?
Question 2: Can we always manage to use instantaneous codes?
McMillans Inequality
There is a uniquely decodable binary code with
codewords having lengths l1, . . . , lI if and only if
I
X
1
1
2 li
i=1
Krafts Inequality
There is an instantaneous binary code with
codewords having lengths l1, . . . , lI if and only if
I
X
1
1
2 li
i=1
i=1
NULL
100
10
101
1
11
Our final code can be read from the leaf nodes: {1,00,010,011}.
First check: 21 + 22 + 23 + 23 1.
NULL
000
00
001
0
010
01
011
NULL
100
10
101
00
1
110
11
111
01 0
Short codewords occupy more of the tree. For a binary code, the
fraction of leaves taken by a codeword of length l is 1/2l .
01 1
j1
j1
X
X
1
2 lj
2lj li = 2lj 1
> 0
2 li
i=1
Since
j1
P
1/2li <
i=1
I
P
i=1
1/2li 1, by assumption.
i=1