Classical and Quantum Information Theory

SOLUTIONS TO EXERCISES

This manual is not available to students, or to those studying the book by themselves.
Instructors receiving the manual must agree not to share the manual's password, to
make any of the solutions publicly accessible, on the web or otherwise, or to make
any of their own solutions to the exercises publicly accessible.

Difficulty scale : B = basic, M = medium, T = tricky

Chapter 9
E9.1(M) : assign a Huffman code to the two-dice roll distribution described in Chapter
1 (as listed in table below), with the results of the roll {2,3,4,..12} being symbolised by
the characters {A, B, C...K } and calculate the coding efficiency.

symbol x probability p(x)

A=2 0,028
B=3 0,056
C=4 0,083
D=5 0,111
E=6 0,139
F=7 0,167
G=8 0,139
H=9 0,111
I=10 0,083
J=11 0,056
K=12 0,028
Σ 1,000

Answer: according to Huffman’s coding tree algorithm, we must proceed from

bottom to top, with the symbols being arranged in increasing order of probability. The
graph below details the code assignment from bottom to top, as broken down into
two parts for page-size purposes:

F 0,167 0.194 0.223

E 0,139 0.139 0.167 0.194
G 0,139 0.139 0.139 0.167
D 0,111 0.112 0.139 0.139 0.139
H 0,111 0.111 0.112 0.139 0.139
C 0,083 0.111 0.111 0.112 0 0.139
I 0,083 0.083 0.111 0 0.111
0.083 1
B 0,056 0.056 0.083 0 1
J 0,056 0.056 0 0.056
1
A 0,028 0 0.056
1
K 0,028 1

0.417 0.584 0
0.223 0.278 0.306
0.223 0.278 0.306 0 0.417 1
0.194
0.167 0.194 0.223 0 0.278
1 1.001
0.139 0.167 0 0.194
1
0.139 0.139 1
0
0.139
1
[Link]/desurvire © Cambridge University Press 2009
 Classical and Quantum Information Theory
SOLUTIONS TO EXERCISES

(Note: the final probabilities at bottom right 0.584 and 0.417 don’t exactly add to
unity, because we have truncated the symbol distribution to three decimal places;
this approximation does not affect the result). The corresponding code assignment is
shown in the following table:

symbol x probability p(x) codeword length l(x) -p(x)*log2p(x) l(x)*p(x)

F 0,167 000 3 0,431 0,500
E 0,139 010 3 0,396 0,417
G 0,139 011 3 0,396 0,417
D 0,111 101 3 0,352 0,333
H 0,111 110 3 0,352 0,333
C 0,083 111 3 0,299 0,250
I 0,083 0010 4 0,299 0,333
B 0,056 1000 4 0,232 0,222
J 0,056 1001 4 0,232 0,222
A 0,028 00110 5 0,144 0,139
K 0,028 00111 5 0,144 0,139
Σ 1,000 3,274 3,306 0,991
H(X) L(X) η

which shows that the coding efficiency is η = 99.1%

E9.2(T) : prove that Huffman coding for uniformly-distributed sources of N = 2

n

symbols ( n integer) yield a mean codeword length of l ( x) = n .

.
Answer: first draw the Huffman diagrams for N = 2 , N = 4 and N = 8 , as illustrated
below :

N =2 N =4
A 1/ 2
A 1/ 4 2/ 4 2/ 4
B 1/ 2
B 1/ 4 1/ 4 2/4

C 1/ 4 1/ 4
D 1/ 4

N =8
A
B
C
D
E
F
G
H
(in the case N = 8 , the probabilities were omitted, for reading clarity). As we know,
each of the right braces, } , determine a 1/0 bit assignment in some place of the
codeword, but not all braces are found in all paths indicated by the arrows. The

[Link]/desurvire © Cambridge University Press 2009

 Classical and Quantum Information Theory
SOLUTIONS TO EXERCISES
number of such braces in cases N = 2 , N = 4 and N = 8 are 1, 3 and 7, respectively.
Formally, each of these numbers does correspond to 2 − 1 with n = 1,2,3 . We then
n

observe that within each of the three graphs, the arrows meet the same number of
braces, namely n = 1,2,3 , in cases N = 2 , N = 4 and N = 8 , respectively. Since each
brace corresponds to an assigned codeword bit, this property establishes that all
codeword lengths must be equal to the number n .

E9.3(T) : show that for dyadic sources, the Huffman code is 100% efficient. Clue: prove
this first using 2-elements and 3-elements sources, then conclude in the general case.

−n( x)
Answer: the distribution of a dyadic source is defined according to p ( x ) = 2
where n(x ) is an integer. The smallest (2-elements) dyadic source is defined by the
{ }
uniform distribution p ( x ) = 1 / 2, 1 / 2 . It is clear that in this case the Huffman

algorithm assigns the codewords “0” and “1” to each of the corresponding symbols,
which gives for the codeword length l ( x ) = 1 , and L( X ) = 1 ≡ H ( X ) . Thus the
coding efficiency is η = H ( X ) / L( X ) = 1 ≡ 100% , which proves the point. Next we
check that this property also applies to a 3-elements dyadic source X = {A, B, C } .
{ }
The only possible distribution is p ( x) = 1 / 2, 1 / 4, 1 / 4 . The graph below details the

corresponding code assignment.

0
A 0.5 0.5 A 1
0 1
B 0.25 0. 5 B 00
1
C 0.25 C 01
The mean codeword length is
1 2 2 3
L( X ) = p ( A)l ( A) + p ( B)l ( B ) + p (C )l (C ) = + + =
2 4 4 2
The source entropy is
H ( X ) = −{p ( A) log p( A) + p ( B) log p( B) + p (C ) log p (C )}
⎧1 1 1 1 1 1⎫ 1 2 2 3
= − ⎨ log + log + log ⎬ = + + = ≡ L( X )
⎩2 2 4 4 4 4⎭ 2 4 4 2
Again, the coding efficiency is η = H ( X ) / L( X ) = 1 ≡ 100% . We also observe that for
the 2-elements and 3-elements sources, the Huffman code assigns codewords of
length l ( x ) = − log p ( x) = n( x ) .

We must now generalize the conclusion to dyadic sources of any size. Let transform
our 3-elements, dyadic source into a 4-elements one, as illustrated below. At left,
we have our initial 3-element (or three leaves) coding tree, with the assigned
Huffman code. To increase the source’s size, we can split the event symbol A into
two equiprobable event symbols A1, A2 , shown at top right, along with the new code
assignment. Call it transformation 1. Alternatively, we can split the event symbol C
into two equiprobable event symbols C1, C 2 , shown at bottom right, along with the
new code assignment. Call it transformation 2. A third remaining possibility is to
split the symbol event B into two equiprobable event symbols B1, B 2 , but this is

[Link]/desurvire © Cambridge University Press 2009

 Classical and Quantum Information Theory
SOLUTIONS TO EXERCISES

equivalent to the previous transformation 1. As we can observe, transformation 1

increase the codeword length by one unit for symbols related to the initial A branch
of the tree, and the same applies to transformation 2 regarding symbols related to
the initial C branch of the tree. This is consistent with the rule according to which
the codeword length is l ( x) = − log p ( x) = n( x) ; thus dividing p ( x) by a factor of
two increases the initial codeword length n( x ) by one unit.

trans.1 1/ 4 11 A1
1 1/ 4
1 A 1/ 2 10 A2
1 1/ 2
1/ 4 01 C
1/ 2 0
1/ 4
00 B
1/ 2 trans.2
1/ 4 01 C 1 A
1
0 1/ 2

1/ 4 1 / 2 1/8
011 C1
00 B 1/ 4
1/8
0 010 C2
1/ 4
00 B

We are now ready to generalize the proof. Assume that we effect the above type of
transformation from any initial tree of codewords l ( x ) corresponding to a dyadic
source X = {x}, verifying L( X ) = H ( X ) (or η = 100% ). The transformation into a
new dyadic source X ' is made by splitting a given symbol event x , of probability
p(x) , into two events x1 , x 2 , for which the probabilities are
p ' ( x1 ) = p ' ( x 2 ) = p ( x) / 2 . We know for a fact that the corresponding codeword
lengths verify l ( x1 ) = l ( x 2 ) = l ( x) + 1 . The changes in entropy and mean codeword
length are the following:
ΔH = H ( X ' ) − H ( X ) = [ p ( x1 ) log p( x1 ) + p( x 2 ) log p( x 2 )] + p( x) log p( x)
⎡ p ( x) p( x) p( x) p( x) ⎤
= −⎢ log + log + p( x) log p( x) +
⎣ 2 2 2 2 ⎥⎦
p ( x)
= − p( x) log + p ( x) log p( x) ≡ p( x)
2
ΔL = L( X ' ) − L( X ) = [ p( x1 )l ( x1 ) + p ( x 2 )l ( x 2 )] − p( x)l ( x)
⎧ p ( x)
=⎨ [l ( x) + 1] + p( x) [l ( x) + 1]⎫⎬ − p( x)l ( x)
⎩ 2 2 ⎭
= p ( x)[l ( x) + 1] − p( x)l ( x) ≡ p( x)
Thus the new coding efficiency is
H ( X ' ) H ( X ) + ΔH H ( X ) + p( x) H ( X ) + p ( x)
η= = = = =1
L( X ' ) L( X ) + ΔL L( X ) + p ( x) H ( X ) + p ( x )

[Link]/desurvire © Cambridge University Press 2009

 Classical and Quantum Information Theory
SOLUTIONS TO EXERCISES

which proves that the codeword assignment for the new dyadic source X ' is 100%
efficient.

E9.4(M) : find a block code to describe the outcome of five successive coin tosses,
and determine the corresponding coding efficiency.

Answer: this exercise is quite similar to that of the roulette-game example described in
text. The two events associated with a single tossing are “heads” (H) and “tails” (T),
which corresponds to the source X = {H , T } . Assuming a perfect coin (and perfect
tossing!), the associated event probability is p ( H ) = p(T ) = 0.5 ≡ p , corresponding to
the source entropy H ( X ) = 1 bit/symbol. A succession of five tosses corresponds to
with entropy H ( X ) = 5 H ( X ) = 5 bits/symbol. The
( 5) ( 5)
the extended source X
resulting events sequences are of six types, each type having various numbers of
equi-probable possibilities, as summarised in the table below

Type Possibilities Probability

A = HHHHH C =10
5 C p (1 − p) 0 ≡ C 50 p 5
0
5
5

B = HHHHT C 51 = 5 C 51 p 4 (1 − p)1 ≡ C 51 p 5
C = HHHTT C 52 = 10 C 52 p 3 (1 − p ) 2 ≡ C 52 p 5
D = HHTTT C 53 = 10 C 53 p 2 (1 − p) 3 ≡ C 53 p 5
E = HTTTT C 54 = 5 C 54 p 1 (1 − p) 4 ≡ C 54 p 5
F = TTTTT C 55 = 1 C 55 p 0 (1 − p) 5 ≡ C 55 p 5

For instance, there is a unique possibility for the sequences A = HHHHH and
F = TTTTT , but five possibilities for B = HHHHT (namely
HHHHT , HHHTH , HHTHH , HTHHH , THHHH ), and so on. We note that each
sequence type has the same probability ( p = 1 / 2 ) to occur.
5 5

We then construct a block code with a uniquely-decodable header defining the

sequence type (A to F) and a trailer defining which possibility is concerned within the
sequence type. The block code assignment is summarised in the following:

Type Trailer Header Header Block length Probability

Possibilities l(x)*p(x)
x bits TB code bits HB l(x)=HB+TB p(x)
A 1 0 1 1 1 0,031 0,031
B 5 3 0 2 5 0,156 0,781
C 10 4 001 3 7 0,313 2,188
D 10 4 0001 4 8 0,313 2,500
E 5 3 00001 5 8 0,156 1,250
F 1 0 00000 5 5 0,031 0,156
Σ 1,000 6,906
L=<l(x)>

As the table indicates, the block length varies from l ( A) = 1 to l ( D ) = l ( E ) = 8 . The

resulting code is seen to have a mean codeword length of L = 6.906 bit/block. With

[Link]/desurvire © Cambridge University Press 2009

 Classical and Quantum Information Theory
SOLUTIONS TO EXERCISES

the extended source entropy of H ( X

(5)
) = 5 bits/symbol, the code efficiency is
η = H / L = 5 / 6.906 = 72.4% . We observe that with a mean length of
L = 6.906 bit/block, and assuming an original coding of 5 bits per event sequence
(i.e. H ="1" , T ="0" , giving for instance HTTHT ≡ 10010 ), the proposed block code
does not achieve any compression.

[Link]/desurvire © Cambridge University Press 2009