21
Problem 6.28
1. We have H(X) = −Pi=1 52−ilog22−i−1
32 log21
32 = 31/16 = 1.9375 and H(Y) = log26 =
2. For Xthe Huffman tree is
✉
✉
✉
❡❡❡
1/2
0
0
0
0
10
and for Y
✉
✉
✉
✉
✉
0
00
01
100
101
❅
❅
❅
❅
1/3
1/3
0
0
1
❡❡❡
✓
0
0
3. The first source has no room for improvement. Therefore we observe an improvement for Y.
4. From elementary probability we know that the PDF of the sum of two independent random
22
to be
5. We note that X+Yis a function of Xand Yand by problem 6.7, H(X+Y)≤H(X, Y )≤
H(X)+H(Y). For equality we must have 1) (X, Y ) be a deterministic function of X+Y, i.e.,
we must be able to uniquely determine both Xand Yfrom their sum. This means that no
Problem 6.29
concave.
2. We have
x
resulting in
3. Assume that Xis equal to x1and x2with probabilities λand 1 −λwhere 0 < λ < 1, then
4. The proof is by induction. We assume that g(E[X]) ≤E[g(X)] for all random variables with
23
We have
g(E[X]) = g n+1
X
i=1
pixi!
=g (1 −pn+1) n
X
pi
1−pn+1
xi!+pn+1xn+1!
X
pi
i=1
where in the first inequality we have applied the inequality for a variable with two values
and in the second inequality we have applied it to the case with npoints. The proof for a
5. This is a direct consequence of Jensen’s inequality and the convexity of Q(x) for positive
arguments.
Problem 6.30
Parsing the sequence by the rules of the Lempel-Ziv coding scheme we obtain the phrases
0, 00, 1, 001, 000, 0001, 10, 00010, 0000, 0010, 00000, 101, 00001,
24
Dictionary Dictionary Codeword
Location Contents
1 00001 0 00000 0
2 00010 00 00001 0
3 00011 1 00000 1
4 00100 001 00010 1
15 01111 11 00011 1
16 10000 01 00001 1
17 10001 0000000 01110 0
18 10010 110 01111 0
Problem 6.31
2. For a discrete source R=H(ˆ
X) is the minimum rate. We have to find the probabilities of
ˆ
X. We have
P(ˆ
X= 0.5) = Z0
11
2e−x
2dx =h−e−x
2i01 = 1 −e−1
2= 0.3935
25
and
H(ˆ
X) = −0.3935 ×log20.3935 −0.2387 ×log20.2387 −0.1447 ×log20.1447
3. Note that having ˜
Xwe know the isuch that i≤X < i + 1, and therefore we know ˆ
X. But
having ˆ
Xwe do not always know ˜
X, for instance when ˆ
X= 6. This shows that the uncertainty
H(ˆ
X, ˜
X) = H(ˆ
X) + H(˜
X)> H(ˆ
X)
4. From part 3, knowledge of ˜
Xuniquely determines ˆ
Xand hence it also uniquely determines
Y. Also note that Yuniquely determines isuch that i≤X < i + 1, since for different values
Problem 6.32
1.
H(X) = −Z∞
0
1
λe−x
λln( 1
λe−x
λ)dx
=−ln( 1
1
λdx +Z∞
1
λx
2.
H(X) = −Z∞
−∞
1
2λe−|x|
λln( 1
2λe−|x|
λ)dx
=−ln( 1
1
λdx +1
λdx
3.
H(X) = −Z0
−λ
x+λ
λ2ln x+λ
λ2dx −Zλ
0
−x+λ
λ2ln −x+λ
λ2dx
=−ln 1
λ2Z0
−λ
x+λ
λ2dx +Zλ
0
−x+λ
λ2dx
x+λ
−x+λ
Problem 6.33
2. The following figure depicts R(D) for λ= 0.1, .2 and .3. As it is observed from the figure, an
27
0
1
2
3
4
5
6
7
l=.1 l=.2
l=.3
R(D)
Problem 6.34
3. P(Z < 0) = .4 and P(Z > 0) = .6. Since the quantizer is uniform, there are four levels less
than zero and four levels higher than zero, for the levels less than zero, p=.4/4 = .1 and for
Problem 6.35
1. For a Gaussian random variable of zero mean and variance σ2the rate-distortion function is
28
2. The differential entropy of a Laplacian source with parameter λis H(X) = 1 + ln(2λ). The
variance of the Laplacian distribution is
-1
0
1
2
3
4
5
Upper Bound
Lower Bound
R(D)
Laplacian Distribution, unit variance
3. The variance of the triangular distribution is given by
σ2=Z0
0
λ
Hence, with σ2= 1, we obtain λ=√6 and H(X) = ln(6)−ln(√6)+1/2 = 1.7925 bits /source output.
Problem 6.36
29
-0.5
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
Upper Bound
Lower Bound
R(D)
Triangular distribution, unit variance
Codeword ProbabilityLetter
x1
x2
x3
0.25
0.20
0.15
2
00
01
0
2
0
1
0.47
¯
Problem 6.37
30
p(X) = 1
(2π)n/2|M|1/2e−1
2X′M−1X
H(X) = −Z∞
−∞
… Z∞
−∞
p(X) log p(X)dX
Problem 6.38
PROPRIETARY MATERIAL. c
The McGraw-Hill Companies, Inc. All rights reserved. No part of this Manual may be displayed,
reproduced or distributed in any form or by any means, without the prior written permission of the publisher, or used beyond the
31
Problem 6.39
dW(X,˜
X) = (X−˜
X)′W(X−˜
X)
Problem 6.40
1. The Huffman tree is shown below
✉
✉
0.8
0.1
❆❆❆
0
0
0
10
The average codeword length is ¯
R= 0.8×1+ 2×0.1+ 3×0.05+ 4(0.01+0.04) = 1.35 and the
32
1. Solving 1
2log2σ2
D= 1 −Hb(ǫ) we obtain
2. Here we have to solve 1
2log2σ2
D=1
2log2(1 + P/σ2
n) resulting in
Problem 6.42
1.
H(X|G) = −Z∞
−∞ Z∞
−∞
p(x, g) log p(x|g)dxdg
2.
I(X;Y) = H(Y)−H(Y|X)
Since Y is the sum of two independent, zero-mean Gaussian r.v’s , it is also a zero-mean Gaussian
r.v. with variance : σ2
y=σ2
x+σ2
n.Hence : H(Y) = 1
2log 2πe σ2
x+σ2
n.Also, since y=x+g:
2σ2
33
Hence :
H(Y|X) = −Z∞
−∞ Z∞
−∞
p(x, y) log p(y|x)dxdy
2log 2πeσ2
where we have used the fact that : R∞
−∞ pg(y−x)dy = 1,R∞
−∞(y−x)2pg(y−x)dy =EG2=σ2
n.
From H(Y), H(Y|X) :
x
Problem 6.43
By symmetry of the inputs B and C, their probabilities have to be equal. Therefore we assume
p. Therefore,
C= max
straightforward differentiation results in
Problem 6.44
1. The Huffman tree is shown below
✉
✉
✉
0.25
0.2
0.15
❙❙❙❙
❚❚❚❚❚❚❚❚❚
❅❅❅❅
❅
✪
✪
✪
0.58 0
0
0
0
00
10
010
2. The minimum required channel capacity is equal to the entropy, i.e., C= 2.8155. Since the
Problem 6.45
For channel A, by symmetry of A and B inputs, we need to assume P(X=A) = P(X=B) = p
and P(X=C) = 1 −2p, for 0 ≤p≤0.5, and regardless of the value of pwe will have H(Y) = 1.
Problem 6.46
1. To have a distortion of 1 we have to maintain a rate of at least R(D) = 1
2log2σ2/D when
2. For BPSK with hard decision decoding the channel model reduces to a BSC channel with
Problem 6.47
1. We have
C= max
p(x)I(X;Y)
2. The input probability that achieves this must be a uniform probability and must satisfy
H(X|Y) = 0, i.e., Xmust be a deterministic function of Yis known. For instance the
0 0 1 0
3. The minimum achievable distortion is the solution of 1
Problem 6.48
1. The entropy of the source is :
H(X) = H(0.3) = 0.8813
and the capacity of the channel :
If the source is directly connected to the channel, then the probability of error at the destination
is :
2. Since H(X)> C, some distortion at the output of the channel is inevitable. To find the
minimum distortion, we set R(D) = C. For a Bernoulli type of source :
H(p)−H(D) 0 ≤D≤min(p, 1−p)
3. For reliable transmission we must have : H(X) = C= 1 −H(ǫ). Hence, with H(X) = 0.8813
Problem 6.49
1. We have H(S1) = −Pi=1 52−ilog22−i−1
32 log21
32 = 31/16 = 1.9375 and H(S2) = log26 =
2. For Xthe Huffman tree is
37
✉
✉
✉
❡❡❡
1/2
0
0
0
0
10
and for Y
✉
✉
✉
✉
00
01
100
❅
❅
❅
❅
1/3
1/3
0
0
1
❡❡❡
0
0
3. The first source has no room for improvement. Therefore we observe an improvement for S2.
Problem 6.50
From 6.5-30, it is suffcient to show that
38
We have
Z∞
−∞
p(y|A) log2
p(y|A)
p(y)dy =Z∞
−∞
1
√2πσ2e−(y−A)2
2σ2log2
2e−(y−A)2
2σ2
dy
1
2
Problem 6.51
2. For symmetric binary input channels from Equation 6.8-27, we have R0= 1 −log2(1 + ∆),
where
∆ = X
ypp(y|x1)p(y|x2)
Problem 6.52
I(xj;Y) = XQ−1
i=0 P(yi|xj) log P(yi|xj)
P(yi)
39
we have :
I(X;Y) = Pq−1
j=0 P(xj)I(xj;Y) = PP(xj)6=0 CP (xj)
j=0
and use the Lagrange multiplier method to maximize C(X).The partial derivative of C(X) with
respect to all P(Xj) is :
∂C(X)
∂P (xk)=∂
∂P (xk)hPq−1
j=0 P(xj)I(xj;Y)−λPq−1
j=0 P(xj) + λi
But :
Pq−1
j=0 P(xj)∂
∂P (xk)I(xj;Y) = −log ePq−1
j=0 P(xj)PQ−1
i=0 P(yi|xj)P(yi)
P(yi|xj)
P(yi|xj)
−[P(yi)]2
∂P (yi)
∂P (xk)
P(xj)P(yi|xj)
Therefore:
I(xk;Y) +
q−1
X
j=0
P(xj)∂
∂P (xk)I(xj;Y)−λ= 0 ⇒I(xk;Y) = λ+ log e, ∀xk
40
(ii) If the set {P(xk)}does not satisfy 0 ≤P(xk)≤1, k = 0,1, …, q −1,since I(X;Y) is a
convex function of P(xk),necessary and suffcient conditions on P(xk) for maximizing I(X;Y) are
Hence :
Problem 6.53
a. For a set of equally probable inputs with probability 1/M, we have :
I(xk;Y) = PM−1
i=0 P(yi|xk) log P(yi|xk)
P(yi)
But ∀i:
P(yi) =
M−1
X
j=0
P(yi|xj) = 1
MP(yi|xi) + 1
MX
j6=i
P(yi|xj) = 1
M1−p+ (M−1) p
M−1=1
M
b. From part (a) :
C= log M+ (1 −p) log(1 −p) + plog p
M−1
A plot of the capacity is given in the following figure. We note that the capacity of the channel is