42
c. We assume that P(xi) = 1/3, i = 1,2,3.Then P(y1) = 1
31
2+1
3+1
6=1
3and similarly
P(yj) = 1/3, j = 2,3.Hence :
3
X
Problem 6.55
We expect the first channel (with exhibits a certain symmetry) to achieve its capacity through
equiprobable input symbols; the second one not.
a. We assume that P(xi) = 1/2, i = 1,2.Then P(y1) = 1
2(0.6 + 0.1) = 0.35 and similarly
P(y3) = 0.35, . P (y2) = 0.3.Hence :
3
X
b. We assume that P(xi) = 1/2, i = 1,2.Then P(y1) = 1
2(0.6 + 0.3) = 0.45,and similarly
P(y2) = 0.2, P (y3) = 0.35.Hence :
3
X
j=1
But :
3
X
j=1
Since I(x1;Y)6=I(x2;Y) the equiprobable input distribution does not maximize the information
rate through the channel. To determine P(x1), P (x2) that give the channel capacity, we assume
Problem 6.56
Problem 6.57
1. We assume that P(xi) = 1/2, i = 1,2.Then P(y1) = 1
21
2(1 −p) + 1
2p=1
4and similarly
P(yj) = 1/4, j = 2,3,4.Hence :
I(x1;Y) = P4
j=1 P(yj|x1) log P(yj|x1)
P(yj)= 21
2(1 −p) log (1−p)/2
1/4+ 21
2plog p/2
1/4
2. We note that the above capacity is the same to the capacity of the binary symmetric channel.
Problem 6.58
We assume that P(xi) = 1/3, i = 1,2,3.Then P(y1) = 1
3((1 −p) + p) = 1
3and similarly P(yj) =
1/3, j = 2,3.Hence :
I(x1;Y) = P3
j=1 P(yj|x1) log P(yj|x1)
P(yj)= (1 −p) log (1−p)
1/3+plog p
1/3
1. the probability that a codeword transmitted over the BSC is received correctly, is equal to the
2.
3.
ne
X
i=1 R
ipi(1 −p)R−i
4. For R= 5, p = 0.01, ne= 5 :
Problem 6.60
1.
I(X;Y) = P2
i=1 P3
j=1 P(yj|xi)P(xi) log P(yj|xi)
P(yj)
2. The value of a that maximizes I(X;Y) is found from :
dI(X;Y)
da = 0 ⇒log a+a
alog e−log(1 −a)−1−a
1−alog e= 0 ⇒a= 1/2
45
3. I(x;y) = log P(y|x)
P(y).Hence :
I(0; 0) = log 1−p
(1−p)/2= 1
Problem 6.61
1. The capacity of the channel in bits per second is 500 ×1
2log2(1 + P/σ2
2) = 250 log2(1 + P/σ2
2)
2. The channel model in a BSC. Since 500 symbols are transmitted per second, the energy in
each symbol is P/500 and N0/2 = σ2
2)
and the capacity is C= 500(1 −Hb(Q(P/500σ2
12−(1−Hb(Q(P/500σ2
3. When the source is not memoryless, it is more predictable from previous samples, i.e., with
lower rate we can achieve the same distortion, or with the same rate we can achieve lower
Problem 6.62
1. The required channel capacity is equal to the source entropy, i.e., H(X) = Hb(1/3) = 0.9183.
2. From Equation 6.8-32, the cutoff rate for a BSC model is given by
R0= 1 −log2(1 + p4p(1 −p))
3. For a Gaussian source R(D) = 1
Problem 6.63
1. For this source R(D) = Hb(0.1) −Hb(D) = 0.469 −Hb(D), and C= 1 −Hb(0.1) = 0.531,
Problem 6.64
The capacity of the additive white Gaussian channel is :
C=1
2log 1 + P
N0W
Problem 6.65
1. By symmetry the capacity is achieved with a uniform input distriubution resulting in the
2. We have
P(ˆ
X= 0) = P(X < 2) = Z2
0
2e−2xdx = 0.9817
Problem 6.66
Both channels can be viewed as binary symmetric channels with crossover probability the proba-
bility of decoding a bit erroneously. Since :
Pb=
Qhq2Eb
N0iantipodal signalling
QhqEb
N0iorthogonal signalling
the capacity of the channel is :
1−HQhq2Eb
N0i antipodal signalling
48
0
0.1
0.2
0.4
0.5
0.6
0.7
0.8
0.9
1
-10 -8 -6 -4 -2 0 2 4 6 8 10
SNR dB
Capacity C
Antipodal Signalling
Problem 6.67
1. The capacity of the binary symmetric channel with crossover probability ǫis :
where H(ǫ) is the binary entropy function. The rate distortion function of a zero mean Gaussian
source with variance σ2per sample is :
1
2log2σ2
DD≤σ2
Since C > 0, we obtain :
and therefore, the minimum value of the distortion attainable at the output of the channel is :
2. The capacity of the additive Gaussian channel is :
49
The minimum attainable distortion is :
3. Here the source samples are dependent and therefore one sample provides information about the
other samples. This means that we can achieve better results compared to the memoryless case at
Problem 6.68
The overall channel is a binary symmetric channel with crossover probability p. To find pnote that
an error occurs if an odd number of channels produce an error. Thus :
p=X
k=odd
n
k
ǫk(1 −ǫ)n−k
Problem 6.69
1. The capacity of the channel is :
50
2. Let qbe the probability of the input symbol 0, and thus (1 −q) the probability of the input
symbol 1. Then :
H(Y|X) = X
P(x)H(Y|X=x)
The probability mass function of the output symbols is :
P(Y=c) = qP (Y=c|X= 0) + (1 −q)P(Y=c|X= 1)
To find the probability qthat achieves the maximum, we set the derivative of C2with respect to q
equal to 0. Thus,
ϑC2
ϑq = 0 = 1 −[0.5 log2(0.5 + 0.5q) + (0.5 + 0.5q)0.5
0.5 + 0.5q
1
ln 2]
1
3. The transition probability matrix of the third channel can be written as :
Q=1
2Q1+1
2Q2
where Q1,Q2are the transition probability matrices of channel 1 and channel 2 respectively. We
51
convex function in Qwe obtain :
C= max
p
I(X;Y) = max
p
I(p;Q)
Problem 6.70
The capacity of a channel is :
C= max
p(x)I(X;Y) = max
p(x)[H(Y)−H(Y|X)] = max
p(x)[H(X)−H(X|Y)]
Since in general H(X|Y)≥0 and H(Y|X)≥0, we obtain :
C≤min{max[H(Y)],max[H(X)]}
Problem 6.71
1. Let qbe the probability of the input symbol 0, and therefore (1 −q) the probability of the input
symbol 1. Then :
H(Y|X) = X
P(x)H(Y|X=x)
52
The probability mass function of the output symbols is :
P(Y= 0) = qP (Y= 0|X= 0) + (1 −q)P(Y= 0|X= 1)
To find the probability qthat achieves the maximum, we set the derivative of Cwith respect to q
equal to 0. Thus : ϑC
ϑq = 0 = H(ǫ) + ǫlog2(ǫ−qǫ)−ǫlog2(1 −ǫ+qǫ)
Therefore :
ǫ−qǫ
ǫ(ǫ−1)
2. If ǫ→0, then using L’Hospital’s rule we find that
lim
ǫ→0
H(ǫ)
ǫ=∞,lim
ǫ→0
H(ǫ)
ǫ2−H(ǫ)
ǫ= 0
and therefore
3. The following figure shows the topology of the cascade channels. If we start at the input
labeled 0, then the output will be 0. If however we transmit a 1, then the output will be zero with
probability
P(Y= 0|X= 1) = (1 −ǫ) + ǫ(1 −ǫ) + ǫ2(1 −ǫ) + ···
53
✚
✚
✚
1−ǫ1−ǫ1−ǫ
111
0
...
0
Problem 6.72
The SNR is :
SNR = 2P
N02W=P
2W=10
10−9×106= 104
Thus the capacity of the channel is :
Problem 6.73
1. We have
D=E[(X−ˆ
X)]2
But E[(X−ˆ
X)2|no error in channel] = 0.3634 and
E[(X−ˆ
X)2|error) = Z0
−∞
(x−0.798)2f(x)dx +Z∞
0
(x+ 0.7998)2f(x)dx
2. Here we have a binary equiprobable source to be transmitted over a channel with capacity
Problem 6.74
1. By symmetry the capacity is achieved using a uniform input probability mass function. This
results in an output probability mass function given by P(ai) = 1/2nfor 1 ≤i≤nand
P(E) = 1/2, resulting in
1
1
2. The source entropy is equal to 1, hence if n≥4, then C > 1 and the capacity exceeds
source entropy and reliable transmission of the source is possible. If n < 4, then the resulting
Problem 6.75
The plot with the cutoff rate R2for the BSC, when the three different modulation schemes are
employed is given in the following figure:
55
−10 −5 0 5 10 15
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
γc (dB)
bits/dimension
R2 for BSC
Antipodal
Orthogonal
DPSK
As we see, orthogonal signaling is 3 dB worse than antipodal signaling. Also, DPSK is the worst
Problem 6.76
1. The cutoff rate for the binary input, ternary output channel is given by :
R3= max
pj
−log
2
X
i=0
1
X
j=0
PjpP(i|j)
2
To maximize the term inside the brackets we want to minimize the argument Sof the log function
:S=P2
i=0 hP1
j=0 PjpP(i|j)i2.Suppose that P0=x, P1= 1 −x. Then :
By setting : dS
dx = 0,we obtain x= 1/2 which corresponds to a minimum for S, since d2S
dx2|x=1/2>0.
Then :
2. For β= 0.65pN0/2,we have :
p=1
√πN0R∞
57
The distance of equally spaced points around a circle with radius √Ecis dm= 2√Ecsin mπ
M. So
M
X
l=1
The plot of R0for the various levels of M-ary PSK is given in the following figure:
−10 −5 0 5 10 15 20 25
0
0.5
1
1.5
2
2.5
3
3.5
4
γc (dB)
bits/dimension
R0 for M−ary PSK
M=2
M=4
M=8
M=16
Problem 6.78
1. For a binary-input symmetric channel from Equation 6.8-27, R0= 1 −log2(1 + ∆), where by
Equation 6.8-10
∆ = Z∞
−∞ pp(y|x1)p(y|x2)dy
Hence,
∆ = Z∞
√ey−1ey+1 dy +1
√ey−1e−y−1dy +1
√e−y+1e−y−1dy
2. By symmetry the optimal threshold is zero and the channel crossover probability is
3. In this case by Equation 6.8-32,
R0= log2
2
1 + p4p(1 −p)
Problem 6.79
This is a symmetric channel model, hence we can use Equation 6.8-22
R0= 2 log2M−log2
Z X
xipp(y|x)!2
dy
j=1
j6=i
and
M
u
M
59
Hence,
X
xipp(y|x)!2
=
M
X
i=1
pn(yi−√E)
M
Y
j=1
pn(yj)
M
X
M
X
u
u
u
u
M
Y
M
Y
i=1
k=1
k6=iqpn(yi−√E)pn(yi)pn(yk−√E)pn(yk)
l=1
l6=i,l6=k
From above we have
Z X
xipp(y|x)!2
dy=M+
M
X
i=1
M
X
k=1
k6=iZ∞
−∞ Z∞
−∞ qpn(yi−√E)pn(yi)pn(yk−√E)pn(yk)dyidyk
M
X
M
X
Substituting this result into the relation for R0and deleting log2Mgives
For a Gaussian channel, pn(y) = 1
√πN0e−y2
N0and pn(y−√E) = 1
√πN0e−(y−√E)2
N0, therefore,
60