CSC 310, Spring 2004 — Assignment #1 Solutions

Question 1 (15 marks):

a) Explain why the code with codewords {0, 0010, 0001100} is uniquely decodable. A
convincing informal explanation is OK.
This code can be decoded by looking for ocurrences of the substrings 010 and 0110. The
first can occur only as part of the codeword 0010, the second only as part of the codeword
0001100. After finding these substrings, mark the bits that make up the corresponding
codewords. (Note that the occurrences of 010 and 0110 cannot overlap, since clearly two
consecutive 1s will be separated by at least three 0s in a string produced by this code.)
The remaining unmarked bits will all be 0s, and each of those bits is an instance of the
first codeword, 0.

b) Is the code in part (a) instantaneous? Show why or why not.

No, since the codeword 0 is a prefix of the codeword 0010 (and also of the codeword
0001100).

c) Show that the code with codewords {0, 0010, 000100} is not uniquely decodable, by
giving an example of a string of bits that can be decoded in more than one way.
The string 000100 can be decoded as the single codeword 000100 or as the three codewords
0, 0010, and 0.

d) Does the code in part (c) satisfy the Kraft-McMillan inequality?

Yes, since 1/21 + 1/24 + 1/26 = 37/64, which is less than or equal to one. Note: The fact
that a code satisfies the Kraft-McMillian inequality does not guarantee that it is uniquely
decodable.

Question 2 (25 marks): Consider a source with source alphabet {a1 , a2 , a3 , a4 , a5 , a6 } in

which the symbols probabilities are as follows:

p1 = 0.27, p2 = 0.09, p3 = 0.23, p4 = 0.11, p5 = 0.15, p6 = 0.15

a) Compute the entropy of this source.

The entropy is

0.27 log2 (1/0.27) + 0.09 log2 (1/0.09) + 0.23 log2 (1/0.23)

+ 0.11 log(1/0.11) + 0.15 log(1/0.15) + 0.15 log(1/0.15) = 2.4817

Note that log2 (x) = loge (x)/ loge (2).

b) Find a Huffman code for this source. Show your work.

The two least probable symbols are a2 and a4 . They will be merged to a new combined
symbol with probability 0.20. The next two least probable symbols are a5 and a6 . They
will be merged to a new combined symbol with probability 0.30. The first of these merged
symbols will then be merged with a3 and the second of the merged symbols will be merged
with a1 , and finally these two new merged symbols will be merged with each other.
 One possible Hufman code, obtained if the first symbol mentioned above for each merge
is assigned to the 0 bit and the second to the 1 bit, is

a1 : 11
a2 : 000
a3 : 01
a4 : 001
a5 : 100
a6 : 101

c) Compute the expected codeword length for the Huffman code you found in part (b).
0.27 × 2 + 0.09 × 3 + 0.23 × 2 + 0.11 × 3 + 0.15 × 3 + 0.15 × 3 = 2.5

d) Find an optimal instantaneous code for this source that is not a Huffman code. (Your
code should not just be different from the Huffman code you found in part (b); it must
also be different from any other Huffman code that could be obtained by changing the
way arbitrary choices are made in the Huffman code algorithm.)
We can get another optimal code from this Huffman code by swapping the assignment of
codewords to symbols for two symbols whose codewords are of equal length. For example,
swapping the codewords for a4 and a5 produces the following code, which is uniquely
decodable and also has minimum expected codeword length:

a1 : 11
a2 : 000
a3 : 01
a4 : 100
a5 : 001
a6 : 101

It is uniquely decodable because the set of codewords is identical to the Huffman code
above. It is optimal because every symbol has a codeword of the same length as the
Huffman code. But it cannot be a Huffman code, because the two symbols with smallest
probability, a2 and a4 , have codewords that differ in more than the last bit (whereas in
any Huffman code, these codewords will be “siblings” in the tree).

Question 3 (30 marks): Let C be a uniquely-decodable binary code for a source with
symbol probabilities p1 , . . . , pI in which the codewords for these symbols have lengths l1 , . . . , lI .
Suppose that for some distinct i, j, and k, li = lj = lk . Prove that if C is optimal (ie, has
minimal expected codeword length), then pi ≤ pj +pk . Caution: C is not necessarily a Huffman
code; it might not even be instantaneous.
First proof: We will suppose that pi > pj +pk and derive a contradiction. Since C is uniquely
decodable, it satisfies the Kraft-McMillan inequality, which can be written as
1 1 1 X 1
l
+ lj + l + ≤ 1
2i 2 2k h∈{i,j,k}
/
2lh

From the fact that li = lj = lk , we can conclude that

1 1 1 1 1 1
+ lj + l = l −1 + lj +1 + l +1
2li 2 2k 2i 2 2k
It follows that
1 1 1 X 1
+ + + ≤ 1
2li −1 2lj +1 2lk +1 h∈{i,j,k}
/
2lh
from which we can conclude that there exists a uniquely-decodable code, C 0 , in which symbol ai
has a codeword of length li0 = li − 1, symbols aj and ak have codewords of lengths lj0 = lj + 1
and lk0 = lk + 1, and all other symbols have codewords that are the same lengths as in C.
The expected codeword length for C 0 is
X
pi (li −1) + pj (lj +1) + pk (lk +1) + ph l h
h∈{i,j,k}
/
X
= p i l i + p j l j + pk l k + ph lh − (pi − pj − pk )
h∈{i,j,k}
/
X
< p i l i + p j l j + pk l k + ph l h
h∈{i,j,k}
/

The last inequality comes about because pi − pj − pk is positive, since we have assumed that
pi > pj + pk . The right side of this inequality is the expected codeword length for the original
code, C. But if C 0 has smaller expected codeword length than C, C cannot be an optimal code.
So we see that assuming pi > pj + pk leads to a contradiction. This assumption must therefore
be wrong, and hence pi ≤ pj + pk .
Second proof: We will suppose that pi > pj + pk and derive a contradiction. Since C is
uniquely decodable, the lengths of its codewords must satisfy the Kraft-McMillan inequality.
Since these lengths satisfy the Kraft-McMillan inequality, there exists an instantaneous code
with these same codeword lengths. Let C 0 be such an instantaneous code.
Since C 0 is instantaneous, it can be represented as a tree, with codewords at the leaves. Consider
the leaves corresponding to the codewords for symbols ai , aj , and ak , all of which will be at the
same level in the tree. If the codewords for aj and ak are not siblings, swap the codeword for
aj and the subtree that is the sibling of ak to produce another instantaneous code, C 00 , with the
same codeword lengths as C 0 (and C), but in which the codewords for aj and ak are siblings.
The codeword for ai in C 00 can be written as xb, where x is some string of bits and b is a single
bit. The codewords for aj and ak will have the forms y0 and y1, where y is some string of bits,
which will be the same length as x. We now create a new code, C 000 , in which the codeword
for ai is y, and the codewords for aj and ak are xb0 and xb1, with the codewords for all other
symbols being the same as in C 00 . (This change is most easily visualized by drawing the code
trees.) It is easy to see that C 000 is an instantaneous code. Since C 000 encodes a1 using one less
bit than C 00 , and a2 and a3 using one more bit than C 00 , the difference of the expected codeword
length of C 000 and that of C 00 is −p1 + pj + pk . If p1 > pj + pk , this difference is negative,
which is impossible if C 00 is optimal. Since assuming pi > pj + pk leads to a contradiction, this
assumption must be wrong, and hence pi ≤ pj + pk .

Question 4 (30 marks total): Suppose a source produces independent symbols from the
alphabet {a1 , a2 , a3 }, with probabilities p1 = 0.4999999, p2 = 0.4999999, and p3 = 0.0000002.

a) Compute the entropy of this source.

The entropy is
−0.4999999 log2 (0.4999999) − 0.4999999 log2 (0.4999999) − 0.0000002 log2 (0.0000002)
= 1.000004539
b) Find an optimal code for this source, and compute its expected codeword length.
One optimal code is the following:

a1 : 0
a2 : 10
a3 : 11

Its expected codeword length is

0.4999999 × 1 + 0.4999999 × 2 + 0.0000002 × 2 = 1.5000001

c) Find an optimal code for the second extension of this source (ie, for blocks of two sym-
bols), and compute its expected codeword length, and the expected codeword length
divided by two.
Here is one optimal code:

(a1 , a1 ) : 00
(a1 , a2 ) : 01
(a2 , a1 ) : 10
(a2 , a2 ) : 110
(a1 , a3 ) : 11100
(a2 , a3 ) : 11101
(a3 , a1 ) : 11110
(a3 , a2 ) : 111110
(a3 , a3 ) : 111111

Its expected codeword length is approximately 2.2500012, which divided by two is approx-
imately 1.1250006.

d) Prove (without any tedious calculations) that in order to compress to within 1% of the
entropy by encoding blocks of size N from this source, N will have to be at least 5.
When N is less than 5, the 2N blocks in which all symbols are either a1 or a2 will be much
more probable than all other blocks. An optimal code for the N -th extension will assign
codewords of length N to all but one of these high-probability blocks, and a codeword of
length N + 1 to the remaining high-probability block. (Other blocks will have codewords
of length greater than N + 1. The expected codeword length for such a code will be greater
than

N ×(2N −1)×0.4999999N +(N +1)×0.4999999N = N ×2N ×0.4999999N +0.4999999N

The expected codeword length divided by N will be greater than 2N × 0.4999999N +

0.4999999N /N . For N = 1, N = 2, N = 3, and N = 4, the values of this expression are
1.4999997, 1.1249996, 1.0416660, and 1.0156242. The entropy plus 1% is 1.0100046.
Since the expected codeword length divided by N is greater than this for N < 5, a block
size of at least five will be needed to compress to within 1% of the entropy.