Chapter 11

Source Coding and Error

Correction Techniques

11.1 Problem Solutions

Problem 11.1
(a) I (x) = log2 (52) = 5:7004 bits
(b) I (x) = log2 [(52)(52)] = 11:4009 bits
(c) I (x) = log2 [(52)(51)] = 11:3729 bits

Problem 11.2
The information in the message is

I (x) = log2 (0:95) = 0:0740 bits

I (x) = loge (0:95) = 0:0513 nats
I (x) = log10 (0:95) = 0:0223 Hartleys

Problem 11.3
The entropy is

H (x) = 2[0:25 log2 (0:25)] 0:20 log2 (0:20)

3[0:10 log2 (0:10)] = 2:4610 bits/symbol

Problem 11.4

1
2 CHAPTER 11. SOURCE CODING AND ERROR CORRECTION TECHNIQUES

x1 0.7
y1
0.2
0.1

0.2
x2 0.5 y2

0.3

0.1
0.2
x3 y3
0.7

Figure 11.1: Channel diagram for Problem 11.5.

The entropy is

H (x) = 0:35 log2 (0:35) 0:25 log2 (0:25)

0:20 log2 (0:20) 0:15 log2 (0:15)
0:05 log2 (0:05) = 2:1211 bits/symbol

The maximum entropy is

H (x) = log2 5 = 2:3219 bits/symbol

Problem 11.5

(a) The channel diagram is shown in Figure 11.1 (b) The output probabilities are

1 10
p (y1 ) = (0:7 + 0:2 + 0:1) = = 0:3333
3 30
1 9
p (y2 ) = (0:2 + 0:5 + 0:2) = = 0:3000
3 30
1 11
p (y3 ) = (0:1 + 0:3 + 0:7) = = 0:3667
3 30
11.1. PROBLEM SOLUTIONS 3

(c) Since
[P (Y )] = [P (X)] [P (Y jX)]
we can write
1
[P (X)] = [P (Y )] [P (Y jX)]
which is
2 3
1:6111 0:6667 0:0566
[P (X)] = [0:333 0:333 0:333] 4 0:6111 2:6667 1:0566 5
0:0566 0:6667 1:7222

This gives
[P (X)] = [0:3148 0:4444 0:2407]
(d) The joint probability matrix is
2 32 3
0:3148 0 0 0:7 0:2 0:1
[P (X; Y )] = 4 0 0:4444 0 5 4 0:2 0:5 0:3 5
0 0 0:2407 0:1 0:2 0:7

which gives 2 3
0:2204 0:0630 0:0315
[P (X; Y )] = 4 0:0889 0:2222 0:1333 5
0:0241 0:0481 0:1685
Note that the column sum gives the output probabilities [P (Y )], and the row sum gives
the input probabilities [P (X)] :

Problem 11.6
It was shown that the cascade of two BSCs is given has the channel matrix

1 1 (1 ) (1 )+ (1 ) + (1 )
=
1 1 (1 )+ (1 ) + (1 ) (1 )

which is (11.24) modi…ed so that the two channels are symmetric. It is clear that the
cascade of two BSCs is a BSC. Consider now three channels ABC, where A, B, and C are
binary symmetric. We have shown that the cascade of A and B, denoted (AB), is binary
symmetric. Therefore, the cascade of (AB) and C is binary symmetric. Continuing this
process illustrates that, by induction, that the cascade of an arbitrary number of BSCs is a
BSC.

Problem 11.7
4 CHAPTER 11. SOURCE CODING AND ERROR CORRECTION TECHNIQUES

For a noiseless channel, the transition probability matrix is a square matrix with 1s on the
main diagonal and zeros elsewhere. The joint probability matrix is a square matrix with
the input probabilities on the main diagonal and zeros elsewhere. In other words
2 3
p (x1 ) 0 0
6 0 p (x2 ) 0 7
6 7
[P (X; Y )] = 6 . . . . 7
.
4 . .
. . .
. . 5
0 0 p(xn )

Problem 11.8

This problem may be solved by raising the channel matrix

0:995 0:005
A=
0:005 0:995

which corresponds to an error probability of 0:001, to increasing powers n and seeing where
the error probability reaches the critical value of 0:08. Consider the MATLAB program

a = [0.995 0.005; 0.005 0.995]; % channel matrix

n = 1; % initial value
a1 = a; % save a
while a1(1,2)<0.1
n=n+1;
a1=a^n;
end
n-1 % display result

Executing the program yields n 1 = 22. Thus we compute (MATLAB code is given)

a^22
ans =
0.9008 0.0992
0.0922 0.9008
a^23
ans =
0.8968 0.1032
0.1032 0.8968

Thus 22 cascaded channels meets the speci…cation for PE < 0:1. However cascading 23
channels yields PE > 0:1 and the speci…cation is not satis…ed. (Note: This may appear
11.1. PROBLEM SOLUTIONS 5

to be an impractical result since such a large number of cascaded channels are speci…ed.
However, the channel A may represent a lengthly cable with a large number of repeaters.
There are a variety of other practical examples.)

Problem 11.9
For the erasure channel we determine

I(X; Y ) = H(X) H(XjY )

where
2 X
X 3 2 X
X 3
p(yj jxi )p(xi )
H(XjY ) = p(xi ; yj ) log2 p(xi jyj ) = p(yj jxi )p(xi ) log2
p(yj )
i=1 j=1 i=1 j=1

Let p(x1 ) = and p(x2 ) = 1 . This gives

p(y1 ) = (1 p)
p(y2 ) = p + (1 )p = p
p(y3 ) = (1 )(1 p)

Thus
(1 p) p
H(XjY ) = (1 p) log2 p log2
(1 p) p
(1 )p (1 )(1 p)
(1 )p log2 (1 )(1 p) log2
p (1 )(1 p)

This is

H(XjY ) = p log2 ( ) (1 )p log2 (1 )= p [ log2 ( ) + (1 ) log2 (1 )]

Since
H(X) = log2 ( ) (1 ) log2 (1 )
we have
I(X; Y ) = H(X) pH(X) = H(X)(1 p)
Therefore
C=1 p bits/symbol
and capacity is achieved for equally likely inputs.

Problem 11.10
6 CHAPTER 11. SOURCE CODING AND ERROR CORRECTION TECHNIQUES

Note that P (Y ) is given by

3=4 1=4 0
P (Y ) = [ p(x1 p(x2 ) ] = [ 0:75p(x1 ) 0:25p(x1 ) p(x2 ) ]
0 0 1

For this problem note that H (XjY ) = 0 (each Y results from only one X) so that I (X; Y ) =
H (X). It therefore follows that
C = 1 bit/symbol
and that the capacity is achieved for
1
p (x1 ) = p (x2 ) =
2
Note that cascading this channel with a channel with 3 inputs and 2 outputs de…ned by
2 3
1 0
4 1 0 5
0 1

gives a channel with 2 inputs and 2 outputs having the channel matrix
2 3
1 0
3=4 1=4 0 4 1 0
1 0 5=
0 0 1 0 1
0 1

which is a noiseless channel having a capacity of 1 bit/symbol.

Problem 11.11
The cascade of the two channels has the channel matrix
1 p1 p1 1 p2 p 2 0
P (Y jX) =
p1 1 p1 0 p 2 1 p2

This gives

(1 p1 ) (1 p2 ) (1 p1 ) p2 + p1 p2 p1 (1 p2 )
P (Y jX) =
p1 (1 p2 ) p1 p2 + (1 p1 ) p2 (1 p1 ) (1 p2 )

which can be written

(1 p1 ) (1 p2 ) p2 p1 (1 p2 )
P (Y jX) =
p1 (1 p2 ) p2 (1 p1 ) (1 p2 )

The output probability for y2 is

p(y2 ) = p2
11.1. PROBLEM SOLUTIONS 7

Thus, the probability of y2 is independent of the input so that the cascade is a more general
erasure channel in that p(y1 jx2 ) and p(y3 jx1 ) are not zero. We will encounter a channel like
this when feedback channels are encountered in Section 11.6.3.

Problem 11.12
To show (10.30), write p (xi ; yj ) in (10.29) as p (xi jyj ) p (yj ) and recall that

log2 p (xi ; yj ) = log2 p (xi jyj ) + log2 p (yj )

Evaluating the resulting sum yields (10.30). The same method is used to show (10.31)
except that p (xi ; yj ) is written p (yj jxi ) p (xi ) :Problem 11.13

The capacity of the channel described by the transition probability matrix

2 3
p q 0 0
6 q p 0 0 7
6 7
4 0 0 p q 5
0 0 q p

is easily computed by maximizing

I (X; Y ) = H (Y ) H (Y jX)

The conditional entropy H (Y jX) can be written

XX X
H (Y jX) = p (xi ) p (yj jxi ) log2 p (yj jxi ) = p (xi ) H (Y jxi )
i j i

where X
H (Y jxi ) = p (yj jxi ) log2 p (yj jxi )
j

For the given channel

H (Y jxi ) = p log2 p q log2 q = K
so that H (Y jxi ) is a constant independent of i. This results since each row of the matrix
contains the same set of probabilities although the terms are not in the same order. For
such a channel X
H (Y jX) = p (xi ) K = K
i
and
I (X; Y ) = H (Y ) K
We see that capacity is achieved when each channel output occurs with equal probability.
8 CHAPTER 11. SOURCE CODING AND ERROR CORRECTION TECHNIQUES

C
2

p
0 1/2 1

Figure 11.2: Figure for Problem 11.13.

We now show that equally likely outputs result if the inputs are equally likely. Assume
that p (xi ) = 41 for all i. Then
X
p (yj ) = p (xi ) p (yj jxi )
i

For each j
1X 1 1 1
p (yj ) = p (yj jxi ) = (p + q) = [p + (1 p)] =
4 4 4 4
i

so that
1
p (yj ) = ; all j
4
1
Since p (yj ) = 4 for all j, H (Y ) = 2, and the channel capacity is

C = 2 + p log2 p + (1 p) log2 (1 p)

or
C=2 H (p)
This is shown in Figure 11.2.
This channel is modeled as a pair of binary symmetric channels as shown. If p = 1 or
p = 0, each input uniquely determines the output and the channel reduces to a noiseless
channel with four inputs and four outputs. This gives a capacity of log2 4 = 2 bits/symbol.
If p = q = 12 , then each of the two subchannels (Channel 1 and Channel 2) have zero
capacity. However, x1 and x2 can be viewed as a single input and x3 and x4 can be viewed
11.1. PROBLEM SOLUTIONS 9

p
x
1 y
1
q
qq
Channel 1
x
2
p q y
2

x
3
p
q y
3

Channel 2 qq

p q
x
4 y
4

Figure 11.3: Additional illustration for Problem 11.13.

as a single input as shown in Figure 11.3. The result is equivalent to a noiseless channel
with two inputs and two outputs. This gives a capacity of log2 2 = 1 bit/symbol.
Note that this channel is an example of a general symmetric channel. The capacity of
such channels are easily computed. See Gallager (Information Theory and Reliable Com-
munications, Wiley, 1968, pages 91-94) for a discussion of these channels.

Problem 11.14
The entropy is maximized when each quantizing region occurs with probability 0:25. Thus
Z x1
1
ae ax dx = 1 e ax1 =
0 4

which gives
ax1 3
e =
4
or
1 4
x1 = ln = 0:2877=a
a 3
In a similar manner
Z x2
ax ax1 ax2 3 ax2 1
ae dx = e e = e =
x1 4 4

which gives
ax2 1
e =
2
10 CHAPTER 11. SOURCE CODING AND ERROR CORRECTION TECHNIQUES

or
1
x2 = ln (2) = 0:6931=a
a
Also Z x3
ax 1
ae dx =
x2 4
gives
x3 = 1:3863=a

Problem 11.15
The thresholds are now parameterized in terms of . We have
Z x1
r r2 =2 2 2 2 1
2
e dx = 1 e x1 = =
0 4
which gives
x21 3
2
= ln = ln(4=3)
4
Thus p
x1 = log(4=3) = 0:5364
For x2 we have
Z x2
r r 2 =2 2 x21 = 2 x22 = 2 3 x22 = 2 1
2
e dx = e e = e =
x1 4 2

so that p
x2 = ln(2) = 0:6931
Finally, for x3 we have
Z x3
r r2 =2 2 x22 = 2 x23 = 2 x22 = 2 3 1 1
2
e dx = e e =e = =
x2 4 4 2

so that p
x3 = ln(2) = 1:1774
As a check we compute
Z 1
r r2 =2 2 x23 = 2 (1:1774)2 1
2
e dx = e 0=e =
x3 4

which is the correct result.

11.1. PROBLEM SOLUTIONS 11

Problem 11.16
First we compute the probabilities of the six messages. Using the Gaussian Q function
Z 1 Z 1
1 2 2 1 2 x
p e y =2 dy = p e y =2 dy = Q
2 x 2 x=
gives
Z Z 1
1 y 2 =2 2 1 1 y 2 =2
p (m3 ) = p e dy = p e dy = Q(0) Q (1) = 0:3413
2 0 2 2 = =1
Z 2
1 y 2 =2 2
p (m4 ) = p e dy = Q (1) Q (2) = 0:1359
2
Z 1
1 y 2 =2 2
p (m5 ) = p e dy = Q (2) Q(1) = Q(2) = 0:0214
2 2

By symmetry

p (m0 ) = p (m5 ) = 0:0228

p (m1 ) = p (m4 ) = 0:1359
p (m2 ) = p (m3 ) = 0:3413

the entropy at the quantizer output is

H (X) = 2 [0:3413 log2 0:3413 + 0:1359 log2 0:1359 + 0:0228 log2 0:0228]
= 2:09 bits/symbol

Since the symbol (sample) rate is 500 samples/s, the information rate is

r = 500 H (X) = 1045 symbols/s

Problem 10.17 p
For BPSK, the error probability is Q 2z . From the data given
q
Uplink error probability = Q 2 108=10 = 0:000191
q
Downlink error probability = Q 2 105=10 = 0:0060

Using the techniques of the previous problem

p11 p12 0:999809 0:000191 0:9940 0:0060 0:9938 0:0062
= =
p21 p22 0:000191 0:999809 0:0060 0:9940 0:0062 0:9938
12 CHAPTER 11. SOURCE CODING AND ERROR CORRECTION TECHNIQUES

PE = 0:0062
Note that for all practical purposes the performance of the overall system is established by
the downlink performance.

Problem 11.18
The transition probabilities for the cascade of Channel 1 and Channel 2 are

p11 p12 0:9 0:1 0:75 0:25 0:7 0:3

= =
p21 p22 0:1 0:9 0:25 0:75 0:3 0:7

Therefore, the capacity of the overall channel is

C = 1 + 0:7 log2 0:7 + 0:3 log2 0:3 = 0:1187 bits/symbol

The capacity of Channel 1 is

C = 1 + 0:9 log2 0:9 + 0:1 log2 0:1 = 0:5310 bits/symbol

and the capacity of Channel 2 is

C = 1 + 0:75 log2 0:75 + 0:25 log2 0:25 = 0:1887 bits/symbol

It can be seen that the capacity of the cascade channel is less than the capacity of either
channel taken alone, which is to be expected since each channel causes errors and the error
probability on the cascade channel is greater than the error probability of either of the
individual channels.

Problem 11.19
Five thresholds are needed to de…ne the six quantization regions. The …ve thresholds are
k2 , k1 , 0, k1 , and k2 . The thresholds are selected so that the six quantization regions
are equally likely. For k1 we have
Z k1 Z 1
1 1 y 2 =2 2 1 1 y 2 =2 2 1 k1
=p e dy = p e dy = Q
6 2 0 2 2 k1 2

so that
k1 1 1 1
Q = =
2 6 3
inding the inverse Q-function yields

1 1 k1
Q = 0:4307 =
3
11.1. PROBLEM SOLUTIONS 13

For k2 we have Z 1
1 1 y 2 =2 2 k2
=p e dy = Q
6 2 k2
Taking the inverse Q function

1 1 k2
Q = 0:9674 =
6
and
k1 = 0:4307 and k2 = 0:9674
This gives the quantizing rule

Quantizer Input Quantizer Output

1 < X < 0:9674 m0
0:9674 < X < 0:4307 m1
0:4307 < X < 0 m2
0 < X < 0:4307 m3
0:4307 < X < 0:9674 m4
0:9674 < X < 1 m5

Problem 11.20

The source entropy is

3 3 1 1
H (X) = log2 log2 = 0:8113
4 4 4 4
and the entropy of the fourth-order extension is

H X 4 = 4H (X) = 4 (0:3113) = 3:2451

The second way to determine the entropy of the fourth-order extension, is to determine the
probability distribution of the extended source. We have
81
1 symbol with probability
256
27
4 symbols with probability
256
9
6 symbols with probability
256
3
4 symbols with probability
256
1
1 symbol with probability
256
14 CHAPTER 11. SOURCE CODING AND ERROR CORRECTION TECHNIQUES

Thus
81 81 27 27 9 9
H X4 = log2 4 log2 6 log2
256 256 256 256 256 256
3 3 1 1
4 log2 log2
256 256 256 256
= 3:2451 bits/symbol

Problem 11.21
For the fourth-order extension we have
Source Symbol P () Codeword
AAAA 0.6561 0
BAAA 0.0729 100
ABAA 0.0729 101
AABA 0.0729 110
AAAB 0.0729 1110
AABB 0.0081 111100
ABAB 0.0081 1111010
BAAB 0.0081 1111011
ABBA 0.0081 1111100
BABA 0.0081 1111101
BBAA 0.0081 1111110
ABBB 0.0009 111111100
BABB 0.0009 111111101
BBAB 0.0009 111111110
BBBA 0.0009 1111111110
BBBB 0.0001 1111111111

The average wordlength: L = 1:9702 which is L=4 = 1:9702=4 = 0:4926. The e¢ ciencies
are given in the following table:

n L H (X n ) E¢ ciency
1 1 0.4690 46.90%
2 1.29 0.9380 72.71%
3 1.598 1.4070 88.05%
4 1.9702 1.8760 95.22%

Problem 11.22
11.1. PROBLEM SOLUTIONS 15

The entropy is

H (X) = 0:85 log2 0:85 0:15 log2 0:15

= 0:60984 bits/symbol

We know that
L
lim r 300
n!1 n
and that
L
lim = H (X)
n!1 n
Therefore, for n large
rH (X) 300
or
300 300
r =
H (X) 0:60984
which gives
r 491:932 symbols/s
Problem 11.23

The codewords for the Shannon-Fano and Hu¤man codes are summarized in the following
table:
Codewords
Source Symbol P ( ) Shannon-Fano Hu¤man
m1 0.40 00 1
m2 0.19 01 000
m3 0.16 10 001
m4 0.15 110 010
m5 0.10 111 011
The average wordlengths are:

L = 2:25 (Shannon-Fano code)

L = 2:22 (Hu¤man code)

Note that the Hu¤man code gives the shorter average wordlength and therefore the higher
e¢ ciency.

Problem 11.24
16 CHAPTER 11. SOURCE CODING AND ERROR CORRECTION TECHNIQUES

For the Shannon-Fano code we have

Source Symbol P () Codeword

m1 0.2 00
m2 0.2 01
m3 0.2 10
m4 0.2 110
m5 0.2 111

The entropy is

H (X) = 5 (0:2 log2 0:2) = 2:3219

The average wordlength is

I = (0:2) (2 + 2 + 2 + 3 + 3) = 2:4

The e¢ ciency is therefore given by

H (X) 2:319
= = 0:9675 = 96:75%
L 2:4

The diagram for determining the Hu¤man code is illustrated in Figure 11.4. This diagram
yields the codewords
m1 01
m2 10
m3 11
m4 000
m5 001

The average wordlength is

L = 0:2 (2 + 2 + 2 + 3 + 3) = 2:4

Since the average wordlength is the same as for the Shannon-Fano code, the e¢ ciency is
also the same.Problem 11.25
11.1. PROBLEM SOLUTIONS 17

0.6
0
1
0.4 0.4
0.4 0
m
1
1
m 0.2 0.2
m
12

0.2
0
m
1
m3
1
m 0.2
m
41
0.2
0
m
1
m
5
1
0.2

Figure 11.4: Hu¤man coding procedure for Problem 11.24.

The Shannon-Fano and Hu¤man codes are as follows. (Note that the codes are not unique.)

Codewords
Source Symbol Shannon-Fano Hu¤man
m1 000 001
m2 001 010
m3 010 011
m4 011 100
m5 100 101
m6 101 110
m7 110 111
m8 1110 0000
m9 1111 0001

In both cases, there are seven codewords of length three and two codewords of length
four. Thus, both codes have the same average wordlengths and therefore have the same
e¢ ciencies. The average wordlength is

1 29
L= [7 (3) + 2 (4)] = = 3:2222
9 9
18 CHAPTER 11. SOURCE CODING AND ERROR CORRECTION TECHNIQUES

Since the source entropy is

H (X) = log2 9 = 3:1699

the e¢ ciency is
H (X)
E= = 98:38%
L

Problem 11.26
For the Shannon-Fano code we have

Source Symbol P () Codeword

m1 1/12 000
m2 1/12 0010
m3 1/12 0011
m4 1/12 010
m5 1/12 0110
m6 1/12 0111
m7 1/12 100
m8 1/12 1010
m9 1/12 1011
m10 1/12 110
m11 1/12 1110
m12 1/12 1111

The average wordlength is

1 44
L= [4 (3) + 8 (4)] = = 3:6667
12 12

and the entropy of the source is

H (X) = log2 12 = 3:5850

This gives the e¢ ciency

H (X)
E= = 0:9777 = 97:77%
L
The diagram for determining the Hu¤man code is illustrated in Figure 11.5. This yields
11.1. PROBLEM SOLUTIONS 19

2/3 0
m
1

m
12
1/12 0
1/6 0
m
3 1/12 1
1/3 1/3 1
m
1
1/12 0
1m 4
1/6 1
m
5 1/12 1
m
16m
1/12 0
1/6 0
m
17 1/12 1
1/3 0
m
8 1/12 0
1/6 1
m
9
1/12 1
m
10
1/12 0
1/6 0
1/12 1
m
11
1/3 1
1/12 0
m
12
1/6 1
1/12 1

Figure 11.5: Hu¤man procedure for Problem 11.26.

the codewords:
Source Symbol Codeword
m1 100
m2 101
m3 110
m4 111
m5 0000
m6 0001
m7 0010
m8 0011
m9 0100
m10 0101
m11 0110
m12 0111
As in the case of the Shannon-Fano code, we have four codewords of length three and eight
20 CHAPTER 11. SOURCE CODING AND ERROR CORRECTION TECHNIQUES

codewords of length four. The average wordlength is therefore 3:6667 and the e¢ ciency is
97:77%.

Problem 11.27
The source entropy is

H (X) = 0:35 log2 0:35 0:3 log2 0:3 0:2 log2 0:2 0:15 log2 0:15
= 1:9261 bits/source symbol

and the entropy of the second-order extension of the source is

H X 2 = 2H (X) = 3:8522

The second-order extension source symbols are shown in the following table along with the
Shannon-Fano code.
Source Symbol P () Codeword
m1 m1 0.1225 000
m1 m2 0.1050 001
m2 m1 0.1050 010
m2 m2 0.0900 0110
m1 m3 0.0700 0111
m3 m1 0.0700 1000
m2 m3 0.0600 1001
m3 m2 0.0600 1010
m4 m1 0.0525 1011
m1 m4 0.0525 1100
m4 m2 0.0450 1101
m2 m4 0.0450 11100
m2 m2 0.0400 11101
m3 m4 0.0300 111100
m4 m3 0.0300 111101
m4 m4 0.0225 111110

The average wordlength of the extended source is

L = 3(0:1225 + 0:105 + 0:105)

+4 (0:09 + 0:07 + 0:07 + 0:06 + 0:06 + 0:0525 + 0:0525 + 0:045)
+5 (0:045 + 0:04)
+6(0:03 + 0:03 + 0:0225)
= 3:9175
11.1. PROBLEM SOLUTIONS 21

Thus the e¢ ciency is

H X2 3:8522
E= = = 98:33%
L 3:9175
We have demonstrated the Hu¤man code previously. For the second-order extension of
the given source we have

100 010 001 1111 1100 1011 1010 0111

for the …rst 8 codewords, and

0110 0001 11101 11100 11011 11010 00001 00000

for the last eight codewords. The average wordlength is 3.88000 and the e¢ ciency is

H X2 3:8522
E= = = 99:28%
L 3:88
which is a small improvement over the Shannon-Fano code.

Problem 11.28
The probability of message mk is
Z 0:1k
P (mk ) = 2x dx = 0:01 (2k 1)
0:1(k 1)

A Hu¤man code yields the codewords in the following table:

Source Symbol P () Codeword

m10 0.19 11
m9 0.17 000
m8 0.15 010
m7 0.13 011
m6 0.11 100
m5 0.09 101
m4 0.07 0011
m3 0.05 00100
m2 0.03 001010
m1 0.01 001011

The source entropy is given by

H (X) = 3:0488 bits/source symbol

22 CHAPTER 11. SOURCE CODING AND ERROR CORRECTION TECHNIQUES

and the average wordlength is

L = 3:1000 binary symbols/source symbol

A source symbol rate of 250 symbols (samples) per second yields a binary symbol rate of

rL = 250(3:1000) = 775 binary symbols/second

and a source information rate of

Rs = rH (X) = 250(3:0488) = 75:2 bits/second

Problem 11.29

The source entropy is

H (X) = 0:35 log2 0:35 0:3 log2 0:3 0:2 log2 0:2 0:15 log2 0:15
= 1:9261 bits/source symbol

and the entropy of the second-order extension of the source is

H X 2 = 2H (X) = 3:8522

The second-order extension source symbols are shown in the following table. For a D = 3
alphabet we partition into sets of 3. The set of code symbols is (0; 1; 2).

Source Symbol P () Codeword

m1 m1 0.1225 00
m1 m2 0.1050 01
m2 m1 0.1050 02
m2 m2 0.0900 10
m1 m3 0.0700 110
m3 m1 0.0700 111
m2 m3 0.0600 120
m3 m2 0.0600 121
m4 m1 0.0525 200
m1 m4 0.0525 201
m4 m2 0.0450 210
m2 m4 0.0450 211
m2 m2 0.0400 2200
m3 m4 0.0300 2201
m4 m3 0.0300 2210
m4 m4 0.0225 2211
11.1. PROBLEM SOLUTIONS 23

The average wordlength of the extended source is

L = 2(0:1225 + 0:105 + 0:105 + 0:09) +

+3 (0:07 + 0:07 + 0:06 + 0:06 + 0:0525 + 0:0525 + 0:045 + 0:045)
+4 (0:04 + 0:03 + 0:03 + 0:0225)
= 2:70

Thus the e¢ ciency is

H X2 3:8522
E= = = 90:02%
L log2 D (2:70) log2 3

Problem 11.30
The set of wordlengths from Table 10.3 is f1; 3; 3; 3; 5; 5; 5; 5g. The Kraft inequality gives
8
X 1 3 4
2li = 2 1
+3 2 3
+4 2 5
= + + =1
2 8 32
i=1

Thus the Kraft inequality is satis…ed.

Problem 11.31
The Shannon-Hartley law with S = 50 and N = 10 5B gives
!
S 50 105
Cc = B log2 1+ = B log2 1+
N B

This is illustrated in the following …gure. It can be seen that as B ! 1 the capacity
approaches a …nite constant. For su¢ ciently small x, ln(1 + x) x. Therefore

50(105 )
lim Cc = = 7:2135 106
B!1 ln(2)

as we see from Figure 11.6

Problem 11.32
We now determine
!
4 P 105
Cc = 10 log2 1+ = 104 log2 (1 + 10P )
104
24 CHAPTER 11. SOURCE CODING AND ERROR CORRECTION TECHNIQUES

6
x 10
8

5
Capacity

0
2 4 6 8 10
10 10 10 10 10
Bandwidth - Hz

Figure 11.6: Capacity as a function of bandwidth for Problem 11.31.

11.1. PROBLEM SOLUTIONS 25

4
x 10
10

7
Capacity - bits/s

0
0 10 20 30 40 50 60 70 80 90 100
Signal Power - Watts

Figure 11.7: Capacity as a function of bandwidth for Problem 11.32.

26 CHAPTER 11. SOURCE CODING AND ERROR CORRECTION TECHNIQUES

The plot is given in Figure 11.7. For su¢ ciently large P ,

Cc 105 log2 (P )

and, therefore, Cc ! 1 as P ! 1.

Problem 11.33
For a rate 71 repetition code we have, assuming an error probability of q on a single trans-
mission,
7 4 7 5 7 6 7 7
PE = q (1 q)3 + q (1 q)2 + q (1 q) + q
4 5 6 7
which is
PE = 35q 4 (1 q)3 + 21q 5 (1 q)2 + 7q 6 (1 q) + q 7
1
For a rate 3 code we have the corresopnding result

PE = 3q 2 (1 q) + q 3

The results, generated by the MATLAB code,

q = 0:0.01:0.1;
p7 = 35*(q.^4).*((1-q).^3)+21*(q.^5).*((1-q).^2)+7*(q.^6).*(1-q)+(q.^7);
p3 = 3*(1-q).*(q.^2)+(q.^3);
plot(q,p3,q,p7)
xlabel(’Error probability - q’)
ylabel(’Word error probability’)

are illustrated in Figure ??. The top curve (poorest performance) is for the rate 31 code and
the bottom curve is for the rate 17 repetition code. Note that these results are not typically
compariable since the values of p and q change as the code rate changes.

Problem 11.34
For a (8,7) parity-check code an odd number of errors can be detected but not corrected.
We therefore must compute the probablity of 1, 3, 5, or 7 errors in an 8-symbol sequence.
This is
8 8 3 8 5 8 7
PE = q (1 p)7 + q (1 q)5 + q (1 q)3 + q (1 q)
1 3 5 7

where q is the coded symbol error probability. This gives

PE = 40320q (1 p)7 + 56q 3 (1 q)5 + 56q 5 (1 q)3 + 8q 7 (1 q)

11.1. PROBLEM SOLUTIONS 27

0.03

0.025

0.02
Word error probability

0.015

0.01

0.005

0
0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1
Error probability - q

Figure 11.8: Performance curves for rate 1/7 and rate 1/3 repetition codes.
28 CHAPTER 11. SOURCE CODING AND ERROR CORRECTION TECHNIQUES

Problem 11.35

Consider the ratio of the error probability of the coded system to the error probability of
the uncoded system for high SNR. Since we are considering z 1 we use the asympotic
approximation for the Gaussian Q function. Therefore, for the coded system

r ! r
2z 1 1 p n 1
( 2z=n)2 2z=n
qc = Q p p e = p e
n 2z=n 2 2z 2

For the uncoded system we simply let n = 1. Thus

s
qc 2z exp ( 2z=n) p 1
= = n exp 2z 1
qu 2z=n exp ( 2z) n

p
Note that for large n the ratio becomes nK, where K is a constant de…ned by exp(2z).
For …xed n, the loss in symbol error probability is therefore exponential with respect to the
SNR z, which is a greater loss than can be compensated by the error-correcting capability
p
of the repetition code. Note that for …xed z, the corresponding losss is proportional to n.

Problem 11.36
The parity-check matrix will have 15 11 = 4 rows and 15 columns. Since rows may be
permuted, the parity-check matrix is not unique. One possible selection is

2 3
0 0 0 0 1 1 1 1 1 1 1 1 0 0 0
6 0 1 1 1 0 0 0 1 1 1 1 0 1 0 0 7
[H] = 6
4 1
7
0 1 1 0 1 1 0 0 1 1 0 0 1 0 5
1 1 0 1 1 0 1 0 1 0 1 0 0 0 1
11.1. PROBLEM SOLUTIONS 29

The corresponding generator matrix is

2 3
1 0 0 0 0 0 0 0 0 0 0
6 0 1 0 0 0 0 0 0 0 0 0 7
6 7
6 0 0 1 0 0 0 0 0 0 0 0 7
6 7
6 0 0 0 1 0 0 0 0 0 0 0 7
6 7
6 0 0 0 0 1 0 0 0 0 0 0 7
6 7
6 0 0 0 0 0 1 0 0 0 0 0 7
6 7
6 7
6 0 0 0 0 0 0 1 0 0 0 0 7
6 7 I11
[G] = 6 0 0 0 0 0 0 0 1 0 0 0 7=
6 7 H11
6 0 0 0 0 0 0 0 0 1 0 0 7
6 7
6 0 0 0 0 0 0 0 0 0 1 0 7
6 7
6 0 0 0 0 0 0 0 0 0 0 1 7
6 7
6 0 0 0 0 1 1 1 1 1 1 1 7
6 7
6 0 1 1 1 0 0 0 1 1 1 1 7
6 7
4 1 0 1 1 0 1 1 0 0 1 1 5
1 1 0 1 1 0 1 0 1 0 1

where I11 is the 11 11 identity matrix and H11 represents the …rst 11 columns of the parity-
check matrix. From the structure of the parity-check matrix, we see that each parity symbol
is the sum of 7 information symbols. Since 7 is odd, the all-ones information sequence yields
the parity sequence 1111. This gives the codeword

[T ]t = [111111111111111]

A single error in the third position yields a syndrome which is the third column of the
parity-check matrix. Thus, for the assumed parity-check matrix, the syndrome is
2 3
0
6 1 7
[S] = 6
4 1 5
7

Problem 11.37
A possible parity-check matrix for a (15,11) Hamming code, which has 4 parity symbols, is
2 3
0 0 0 0 1 1 1 1 1 1 1 1 0 0 0
6 0 1 1 1 0 0 0 1 1 1 1 0 1 0 0 7
[H] = 6
4 1
7
0 1 1 0 1 1 0 0 1 1 0 0 1 0 5
1 1 0 1 1 0 1 0 1 0 1 0 0 0 1
30 CHAPTER 11. SOURCE CODING AND ERROR CORRECTION TECHNIQUES

Since columns of the parity-check matrix can be permuted, it is not unique, The form shown
is a systemantic code. Since each column is distinct, and there is no all-zeros column, there
are 15 distinct non-zero syndromes (columns) with each syndrome corresponding to a single
error in the position of that column. Thus, all single errors can be corrected and the code
is a distance 3 code.

Problem 11.38
The generrator matrix corresponding to the given parity-check matrix is
2 3
1 0 0 0
6 0 1 0 0 7
6 7
6 0 0 1 0 7
6 7
[G] = 6
6 0 0 0 1 7
7
6 0 1 1 1 7
6 7
4 1 0 1 1 5
1 1 0 1

The code words are of the form a1 a2 a3 a4 c1 c2 c3 where

2 3
c1 = a2 a3 a4
4 c2 = a1 a3 a4 5
c3 = a1 a2 a4

Thus, the 24 = 16 code words are (read veritcally)

a1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
a2 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
a3 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
a4 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

c1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1
c2 0 1 1 0 0 1 0 0 1 0 0 0 0 0 0 1
c3 0 1 1 1 1 0 1 0 1 0 1 0 0 1 0 1

Problem 11.39
We …rst determine [Ti ] = [G] [Ai ] for i = 1; 2. The generator matrix for the previous problem
11.1. PROBLEM SOLUTIONS 31

is used. For [A1 ] we have

2 3
0
3 6
2 1 7
0 6 7
6 1 7
6 1 7 6 7
[G] [A1 ] = [G] 6 7 6
4 1 5=6 1 7 = [T1 ]
7
6 1 7
1 6 7
4 0 5
0

and for [A2 ] we have

2 3
1
3 6
2 0 7
1 6 7
6 1 7
6 0 7 6 7
[G] [A2 ] = [G] 4 5 = 6
6 7
6 0 7 = [T2 ]
7
1 6 7
6 1 7
0 4 5
0
1
We note that 3
2
1
6 1 7
[A1 ] [A2 ] = 6 7
4 0 5
1
and 2 3
1
3 6
2 1 7
1 6 7
6 0 7
6 1 7 6 7
[G] f[A1 ] [A2 ]g = [G] 4 5 = 6
6 7
6 1 7
7
0 6 7
6 0 7
1 4 5
0
1
which is [T1 ] [T2 ].

Problem 11.40
For a Hamming code with r = n k parity check symbols, the wordlength n is

n = 2r 1

and
k = 2r r 1
32 CHAPTER 11. SOURCE CODING AND ERROR CORRECTION TECHNIQUES

The rate is
k 2r r 1
R= =
n 2r 1
If n is large, r is large. As r ! 1 both k and n approach 2r . Thus

2r
lim R = lim R = =1
n!1 r!1 2r

Problem 11.41
For a rate 13 repetition code
2
3
1
[G] = 4 1 5
1
1
and for a rate 5 repetition code
2 3
1
6 1 7
6 7
[G] = 6
6 1 7
7
4 1 5
1
1
The generator matrix for a rate n repetition code has one column and n rows. All elements
are unity.

Problem 11.42
The codeword is of the form (a1 a2 a3 a4 c1 c2 c3 ) where

c1 = a1 a2 a3
c2 = a2 a3 a4
c3 = a1 a2 a4

This gives the generator matrix

2 3
1 0 0 0
6 0 1 0 0 7
6 7
6 0 0 1 0 7
6 7
[G] = 6
6 0 0 0 1 7
7
6 1 1 1 0 7
6 7
4 0 1 1 1 5
1 1 0 1
11.1. PROBLEM SOLUTIONS 33

α
1 α
5

α
2 α
3 α
12 α
9 α
15 α
14 α
6

α
4 α
8 α
7 α
11 α
13 α
16 α
10

Figure 11.9: Illustration of cyclic property.

Using the generator matrix, we can determine the codewords. The codewords are (read
vertically)
a1 0 1 1 1 1 0 0 0 1 1 1 0 0 0 0 1
a2 0 0 1 1 1 0 0 1 0 1 0 1 1 0 1 0
a3 0 0 0 1 1 0 1 1 1 0 0 1 0 1 0 1
a4 0 0 0 0 1 1 1 1 1 1 1 0 0 0 1 0

c1 0 1 0 1 1 0 1 0 0 0 1 0 1 1 1 0
c2 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1
c3 0 1 0 0 1 1 1 0 0 1 0 1 1 0 0 1
Let i denote the i-th code word and let i ! j indicate that a cyclic shift of i yields
j The cyclic shifts are illustrated in Figure 11.9.
.

Problem 11.43
The parity-check matrix for the coder in the previous problem is
2 3
1 1 1 0 1 0 0
[H] = 4 0 1 1 1 0 1 0 5
1 1 0 1 0 0 1
For the received sequence
[R]t = [1101001]
the syndrome is 3 2
0
[S] = [H] [R] = 4 0 5
0
34 CHAPTER 11. SOURCE CODING AND ERROR CORRECTION TECHNIQUES

This indicates no errors, which is in agreement with Figure 11.15. For the received sequence

[R]t = [1101011]

the syndrome is 32
0
[S] = [H] [R] = 4 1 5
0
This syndrome indicates an error in the 6th position. Thus the assumed transmitted code-
word is
[T ]t = [1101001]
which is also in agreement with Figure 11.15.

Problem 11.44
The parity-check matrix for a (7; 4) Hamming code, as we have de…ned a Hamming code, is
a code in which the ith column of the parity matrix is the binary representation of i. This
gives 2 3
0 0 0 1 1 1 1
[H] = 4 0 1 1 0 0 1 1 5
1 0 1 0 1 0 1
The parity checks are in positions 1,2, and 4. Moving the parity checks to positions 5, 6,
and 7 yields a systematic code with the generator matrix
2 3
1 0 0 0
6 0 1 0 0 7
6 7
6 0 0 1 0 7
6 7
[G] = 6
6 0 0 0 1 7
7
6 0 1 1 1 7
6 7
4 1 0 1 1 5
1 1 0 1

which has the partity-check matrix

2 3
0 1 1 1 1 0 0
[H] = 4 1 0 1 1 0 1 0 5
1 1 0 1 0 0 1

Note that all columns of [H] are still distinct and therefore all single errors are corrected.
Thus, the distance three property is preserved. Since the …rst four columns of [H] can be
in any order, there are 4! = 24 di¤erent (7; 4) systematic codes. If the code is not required
11.1. PROBLEM SOLUTIONS 35

to be systematic, there are 7! = 5040 di¤erent codes, all of which will have equivalent
performance in an AWGN channel.

Problem 11.45
The probability of two errors in a 7 symbol codeword is
7
P f2 errorsg = (1 qc )5 qc2 = 21qc2 (1 qc )5
2
and the probability of three errors in a 7 symbol codeword is
7
P f3 errorsg = (1 qc )4 qc3 = 35qc3 (1 qc )4
3
The ratio of P f3 errorsg to P f2 errorsg is

Pr f3 errorsg 35qc3 (1 qc )4 5 qc
R= = 5 = 3 1
Pr f2 errorsg 21qc2 (1 qc ) qc

We now determine the coded error probability qc . Since BPSK modulation is used
r !
2z
qc = Q
7

where z is STw =N0 . This gives us the following table

errorsg
z qc R = Prf3
Prf2 errorsg
8 dB 0:0897 0:1642
9 dB 0:0660 0:1177
10 dB 0:0455 0:0794
11 dB 0:0290 0:0497
12 dB 0:0167 0:0278
13 dB 0:0085 0:0141
14 dB 0:0037 0:0062

It is clear that as the SNR, z, increases, the value of R becomes negligible.

Problem 11.46
For the convolutional coder shown in Figure 11.24 we have the three outputs

v1 = s1 s2 s3
v2 = s1
v2 = s1 s2
36 CHAPTER 11. SOURCE CODING AND ERROR CORRECTION TECHNIQUES

Shifting in a 0 gives, in terms of the initial shift register contents

v1 = 0 s1 s2 = 0 a
v2 = 0
v3 = 0 s1

and shifting in a binary 1 gives

v1 = 1 s1 s2 = 1 a
v2 = 1
v3 = 1 s1

where a = s1 s2 . Clearly v1 = 0 a or v1 = 1 a are complements for a = 0 or 1. The

output v2 for a 0 or 1 input are obviously complements. Also v1 = 0 s1 or v1 = 1 s1 are
complements for s1 = 0 or 1

Problem 11.47
For the convolutional coder shown in Figure 11.24 we have the three outputs

v1 = s1 s2 s3 s4
v2 = s1 s2 s4

Shifting in a 0 gives, in terms of the initial shift register contents

v1 = 0 s1 s2 s3 = 0 a
v2 = 0 s1 s3 = 0 b

and shifting in a binary 1 gives

v1 = 1 s1 s2 s3 = 1 a
v2 = 1 s1 s3 = 1 b

where a = s1 s2 s3 and b = s1 s3 . Clearly v1 = 0 a or v1 = 1 a are complements

for a = 0 or 1. In the same manner v2 = 0 b or v2 = 1 b are complements for b = 0 or 1.

Problem 11.48
For the encoder shown, the constraint span is k = 4. We …rst need to compute the states
for the encoder. The output is v1 v2 where v1 = s1 s2 s3 s4 and v2 = s1 s2 s4 .
11.1. PROBLEM SOLUTIONS 37

We now compute the state transitions and the output using the state diagram shown in
Figure 11.10. This gives the following table.
Previous Current
State s1 s2 s2 Input s1 s2 s3 s4 State Output
A 000 0 0000 A 00
1 1000 E 11
B 001 0 0001 A 11
1 1001 E 00
C 010 0 0010 B 10
1 1010 F 01
D 011 0 0011 B 01
1 1011 F 10
E 100 0 0100 C 11
1 1100 G 00
F 101 0 0101 C 00
1 1101 G 11
G 110 0 0110 D 01
1 1110 H 10
H 111 0 0111 D 10
1 1111 H 01

Problem 11.49
For the encoder shown, we have v1 = s1 s2 s3 and v2 = s1 s3 . The trellis diagram
is illustrated in Figure 11.11. The state transitions, and the output corresponding to each
transition appears in the following table.
State s1 s2 Input s1 s2 s3 State Output
A 00 0 000 A 00
1 100 C 11
B 01 0 001 A 11
1 101 C 00
C 10 0 010 B 10
1 110 D 01
D 11 0 011 B 01
1 111 D 10

Problem 11.50
The source rate is rs = 5000 symbols/second. The channel symbol rate is
n n
rc = rs = 5000
k k
38 CHAPTER 11. SOURCE CODING AND ERROR CORRECTION TECHNIQUES

(0 0)

(1 1)
(1 1)
(1 0)
C
B (0 1) (1 1)

(0 0) E
(0 1)

(0 0) (0 0)
D (0 1)
(1 0)
(1 1)
G
F
(1 0)
(1 0)
H
(0 1)

Figure 11.10: State diagram for Problem 11.48.

If the burst duration is Tb , then

n n
r c T b = rs T b
= 5000Tb
k k
channel symbols can be a¤ected. Assuming that Tb = 0:2 s, the burst length, expressed in
symbols, is
n n
m = rc Tb = (5000) (0:2) = 1000
k k
symbols a¤ected by the burst. The interleaving array contains m rows with each row
representing a (n; k) codeword. We now must now determine n and k.
Since n > k, it is clear that the burst a¤ects more than 1000 code symbols. We also
know that the rate of a Hamming code approaches 1 as n gets large, so that for large n;.m
/
11.1. PROBLEM SOLUTIONS 39

(00) (00) (00) (00) (00)

(11) (11) (11)

(11) (11) (11)

(00)
(10) (10)
(10)

(01) (01) (01)

(01)

(10)

Steady-State Termination
Transitions

Figure 11.11: Trellis diagram for Problem 11.49.

will exceed 1000 by only a small amount. We therefore try a (1023,1013) Hamming code
having n k = 10 parity symbols. (See problem 10.41.) The number of symbols a¤ected
by the burst is
1023
m = 1000 = 1009:9
1013
Since m must be an integer lower bounded by 1009.9, we let m = 1010. The full interleaving
array contains mn symbols, since m may be received in error (worst case) m(n 1) must
be received correctly. Since the symbol rate on the channel is 5000n=k this gives a required
error-free span of
m(n 1) 1010 1022
= = 204:43 s
5000n=k 5000 1023=1013
This is probably not very practical but it illustrates the process and the problem of using
long codes with low error-correcting capabilities for interleaving.

Problem 11.51
40 CHAPTER 11. SOURCE CODING AND ERROR CORRECTION TECHNIQUES

The source rate is rs = 5000 symbols/second. The channel symbol rate is

n 23
rc = rs = 5000
k 12

since we have a (23,12) code. If the burst duration is Tb , then

n 23
rc T b = rs T b = 5000Tb
k 12
channel symbols can be a¤ected by the burst. The burst can a¤ect 3 columns, containing
3m symbols, of the interleaving table. Assuming that Tb = 0:2 s, the burst length, expressed
in symbols, is
23
3m = rc Tb = (5000) (0:2) = 1916:7 symbols
12
Thus
1916:7
m= = 638:89
3
We therefore set m = 639, which gives an interleaving array with 639 rows and 23 columns.
Since 3 columns can contain errors we must have 20 error-free columns representing 20(639)
symbols. This represents an error-free span of
20m 20(639)
= = 1:3336 s
rc 5000(23=12)
We see that the more powerful code results in a much shorter required error-free span and
a smaller interleaving array.

Problem 11.52
The probability of n transmissions is the probability of n 1 retransmissions. This is P2n 1
.
The expected value of N is therefore
(1 )
X
n 1
E nP2
n=1

From
1
X 1
xn = ; jxj < 1
1 x
n=0
we can obtain, by di¤erentiating both sides of the above wrt x,
1
X 1
nxn 1
=
(1 x)2
n=1
11.2. COMPUTER EXERCISES 41

Figure 11.12: Detection gain characteristice for Problem 11.53.

There the expected value of N is

1
E fN g =
(1 P2 )2

Problem 11.53
The required plot is shown in Figure 11.12.

11.2 Computer Exercises

Computer Exercise 11.1
42 CHAPTER 11. SOURCE CODING AND ERROR CORRECTION TECHNIQUES

For two messages the problem is easy since there is only a single independent probability.
The MATLAB program follows

% File: ce11_1a.m
a = 0.001:0.001:0.999;
b =1-a;
lna = length(a);
H = zeros(1,lna);
H=-(a.*log(a)+b.*log(b))/log(2);
plot(a,H);
xlabel(’a’)
ylabel(’Entropy’)

The plot is illustrated in Figure ??.

For three source messages we have two independent probabilities. Two of them will be
speci…ed and the remaining probability can then be determined. The resulting MATLAB
code follows:

% File: ce11_1b.m
n = 50; % number of points in vector
nn = n+1; % increment for zero
H = zeros(nn,nn); % initialize entropy array
z = (0:n)/n; % probability vector
z(1) = eps; % prevent problems with log(0)
for i=1:nn
for j=1:nn
c = 1-z(i)-z(j); % calculate third probability
if c>0
xx = [z(i) z(j) c];
H(i,j)= -xx*log(xx)’/log(2); % compute entropy
end
end
end
colormap([0 0 0]) % b&w colormap for mesh
mesh(z,z,H); % plot entropy
view(-45,30); % set view angle
xlabel(’Probability of message a’)
ylabel(’Probability of message b’)
zlabel(’Entropy’)
figure % new figure
11.2. COMPUTER EXERCISES 43

contour(z,z,H,10) % plot contour map

xlabel(’Probability of message a’)
ylabel(’Probability of message b’)

The resulting plot is illustrated in Figure ??. One should experiment with various viewing
locations.
Next we draw a countour map with 10 countour lines. The result is illustrated in Figure
10.17. Note the peak at 0.33, 0.33, indicating that the maximum entropy occurs when all
three source messages occur with equal probability

Computer Exercise 11.2

The solution of this computer example is, in large part, taken from the book by Proakis,
Salehi, and Bauch (Comtemporary Communication Systems using MATLAB, Thomson-
Brooks/Cole, 2004, ISBN 0-534-40617-3).1 Modi…cations made to the ortiginally published
program include changing the program from a function to a script, allowing the user to
determine probability distributions and source codes for extended sources, allowing the user
to enter the source distribution and desired extension order interactively and, in addition,
the entropy of the source, the entropy of the extended source, the average word length, and
the e¢ ciency are displayed as the program is executed. This was done since a typical use of
source coding is to continue incrementing the source extension until the e¢ ciency reaches
a point where transmission can be accomplished. The resulting MATLAB code follows.

% File: ce11_2.m
clear all
msgprobs = input(’Enter message probabilities as a vector, ...
e.g., [0.5 0.25 0.25] > ’);
ext = input(’Enter desired extension (1 if no extension is desired) > ’);
entp = -sum(msgprobs.*log(msgprobs))/log(2); % original source entropy
dispa = [’The source entropy is ’, ...
num2str(entp,’%15.5f’),’ bits/symbol.’]; disp(dispa)
%
% Determine probabilities and entropy of extended source.
%
if ext>1
1
This book is highly recommended as a supplemental text in basic communications courses. We have
found it useful as a resource for in-class demonstrations and for homework assignments extending material
covered in class.
This particular computer example, as originally developed by Proakis, Salehi, and Bauch, provides an
excellent example of several MATLAB programming techniques. It has been said that a key to understanding
e¢ cient MATLAB programming techniques is to understand the use of the colon and the find command.
This program makes e¢ cient use of both.
44 CHAPTER 11. SOURCE CODING AND ERROR CORRECTION TECHNIQUES

b = msgprobs; % working array

for k=2:ext
b = kron(b,msgprobs); % Kronecker tensor product
end
msgprobs = b; % probabilities for extended source
entp = -sum(msgprobs.*log(msgprobs)) ...
/log(2); % entropy of extended source
dispaa = [’The extended source entropy is ’, ...
um2str(entp,’%15.5f’),’ bits/symbol.’]; disp(dispaa)
end
%
% Continue
%
n = length(msgprobs); % length of source (or extended source)
q = msgprobs; % copy of msgprobs
m = zeros(n-1,n); % initialize
for i=1:n-1
[q,l] = sort(q); % order message probabilities
m(i,:) = [l(1:n-i+1),zeros(1,i-1)];
q = [q(1)+q(2),q(3:n),1]; % combine messages in column vector
end
%
% Code words are estabilished in the c array.
%
for i = 1:n-1
c(i,:) = blanks(n*n); % initialize character array
end
c(n-1,n) = ’0’; c(n-1,2*n) = ’1’;
for i=2:n-1
c(n-i,1:n-1) = c(n-i+1,n*(find(m(n-i+1,:)==1)) ...
(n-2):n*(find(m(n-i+1,:)==1)));
c(n-i,n) = ’0’;
c(n-i,n+1:2*n-1) = c(n-i,1:n-1);
c(n-i,2*n) = ’1’;
for j=1:i-1
c(n-i,(j+1)*n+1:(j+2)*n) = ...
c(n-i+1,n*(find(m(n-i+1,:)==j+1)-1)+1:n*find(m(n-i+1,:)==j+1));
end
end
%
11.2. COMPUTER EXERCISES 45

% Establish code words, average word length, and entropy.

%
for i=1:n % determine codewords and wordlengths
codewords(i,1:n) = c(1,n*(find(m(1,:)==i)-1)+1:find(m(1,:)==i)*n);
wrdlengths(i) = length(find(abs(codewords(i,:))~=32));
end
avewl = sum(msgprobs.*wrdlengths); % average word length
codewords % display code words
disp3 = [’The average wordlength is ’, ...
num2str(avewl,’%15.5f’),’ symbols.’]; disp(disp3)
disp4 = [’The efficiency is ’, ...
num2str(entp*100/avewl,’%15.5f’),’ %.’]; disp(disp4)
% End of function file.

We will use the preceding MATLAB program to work Problem 11.28. The MATLAB
dialog follows.

» ce11_2.m
Enter message probabilities as a vector, ...
e.g., [0.5 0.25 0.25] > [0.35 0.3 0.2 0.15]
The source entropy is 1.92612 bits/symbol.
Enter desired extension (1 if no extension is desired) > 2
The extended source entropy is 3.85224 bits/symbol.
codewords =
100
001
1011
0001
010
1111
0111
11100
1100
1010
11011
00001
0110
11101
11010
00000
46 CHAPTER 11. SOURCE CODING AND ERROR CORRECTION TECHNIQUES

The average wordlength is 3.88000 symbols.

The efficiency is 99.28457 %.

Computer Exercise 10.3

The MATLAB code for generating the performance curves illustrated in Figure 11.18 in the
text follows.

% File: ce11_3.m
zdB = 0:30;
z = 10.^(zdB/10);
qa = 0.5*exp(-0.5*z);
qa3 = 0.5*exp(-0.5*z/3);
qa7 = 0.5*exp(-0.5*z/7);
pa7 = 35*((1-qa7).^3).*(qa7.^4)+21*((1-qa7).^2).*(qa7.^5)...
+7*(1-qa7).*(qa7.^6)+(qa7.^7);
pa3 = 3*(1-qa3).*(qa3.^2)+(qa3.^3);
qr = 0.5./(1+z/2);
qr3 = 0.5./(1+z/(2*3));
qr7 = 0.5./(1+z/(2*7));
pr7 = 35*((1-qr7).^3).*(qr7.^4)+21*((1-qr7).^2).*(qr7.^5)...
+7*(1-qr7).*(qr7.^6)+(qr7.^7);
pr3 = 3*(1-qr3).*(qr3.^2)+(qr3.^3);
semilogy(zdB,qr,zdB,pr3,zdB,pr7,zdB,qa,zdB,pa3,zdB,pa7)
axis([0 30 0.0001 1])
xlabel(’Signal-to-Noise Ratio, z - dB’)
ylabel(’Probability ’)

Executing the code yields the results illustrated in Figure ?? in the text. The curves can
be identi…ed from Figure 10.18 in the text.

Computer Exercise 11.4

For the rate 0.5 BCH codes, we use the following MATLAB program.

% File: ce11_4a.m
zdB = 0:0.5:10; % set Eb/No in dB
z = 10.^(zdB/10); % convert to linear scale
ber1 = q(sqrt(4*2*z/7)); % SER for (7,4) BCH code
ber2 = q(sqrt(7*2*z/15)); % SER for (15,7) BCH code
ber3 = q(sqrt(16*2*z/31)); % SER for (31,16) BCH code
ber4 = q(sqrt(30*2*z/63)); % SER for (63,30) BCH code
11.2. COMPUTER EXERCISES 47

berbch1 = ser2ber(2,7,3,1,ber1); % BER for (7,4) BCH code

berbch2 = ser2ber(2,15,5,2,ber2); % BER for (15,7) BCH code
berbch3 = ser2ber(2,31,7,3,ber3); % BER for (31,16) BCH code
berbch4 = ser2ber(2,64,13,6,ber4); % BER for (63,30) BCH code
semilogy(zdB,berbch1,’k’,zdB,berbch2,’k’,zdB,berbch3,’k’,zdB,berbch4,’k’)
xlabel(’E_b/N_o in dB’) % label x axis
ylabel(’Bit Error Probability’) % label y axis
% End of script file.

Executing the code for the rate 0.5 code yields the results shown in Figure 11.13. For SNRs
exceeding 5 dB, the order of the plots is in order of word length n, with n = being the top
curve (least error correcting capability) and n = 63 being the bottom curve (greatest error
correcting capability).

For the rate 0.75 BCH codes, we use the following MATLAB program.

% File: ce11_4b.m
zdB = 0:0.5:10; % set Eb/No in dB
z = 10.^(zdB/10); % convert to linear scale
ber1 = q(sqrt(11*2*z/15)); % SER for (15,11) BCH code
ber2 = q(sqrt(21*2*z/31)); % SER for (31,21) BCH code
ber3 = q(sqrt(45*2*z/63)); % SER for (63,45) BCH code
ber4 = q(sqrt(99*2*z/127)); % SER for (127,99) BCH code
berbch1 = ser2ber(2,15,3,1,ber1); % BER for (15,11) BCH code
berbch2 = ser2ber(2,31,5,2,ber2); % BER for (31,21) BCH code
berbch3 = ser2ber(2,63,7,3,ber3); % BER for (63,45) BCH code
berbch4 = ser2ber(2,127,9,4,ber4); % BER for (127,99) BCH code
semilogy(zdB,berbch1,zdB,berbch2,zdB,berbch3,zdB,berbch4)
xlabel(’E_b/N_o in dB’) % label x axis
ylabel(’Bit Error Probability’) % label y axis
% End of script file.

Executing the code for the rate 0.75 code yields the results shown in Figure 11.14. For SNRs
exceeding 5 dB, the order of the plots is in order of word length n, with n = 15 being the
top curve (least error correcting capability) and n = 127 being the bottom curve (greatest
error correcting capability).

Computer Exercise 11.5

In order to illustrate the problems associated with using nchoosek with large arguments
we compute
48 CHAPTER 11. SOURCE CODING AND ERROR CORRECTION TECHNIQUES

0
10

-2
10

-4
10
Bit Error Probability

-6
10

-8
10

-10
10

-12
10

-14
10
0 1 2 3 4 5 6 7 8 9 10
Eb/No in dB

Figure 11.13: Rate 1/2 BCH code results for Computer Exercise 11.4.
11.2. COMPUTER EXERCISES 49

0
10

-5
10
Bit Error Probability

-10
10

-15
10
0 1 2 3 4 5 6 7 8 9 10
Eb/No in dB

Figure 11.14: Rate 3/4 BCH code results for Computer Exercise 11.4.
50 CHAPTER 11. SOURCE CODING AND ERROR CORRECTION TECHNIQUES

» nchoosek(1000,500)
Warning: Result may not be exact.
> In C:nMATLABR11ntoolboxnmatlabnspecfunnnchoosek.m at line 50
ans =
2.7029e+299

The warning indicates a possible with numerical percision. A possible way to mitigate this
is to perform the calculation using logarithms as illustrated in the function below.

%File: nkchoose.m
Function out=nkchoose(n,k)
% Computes n!/k!/(n-k)!
a = sum(log(1:n)); % ln of n!
b = sum(log(1:k)); % ln of k!
c = sum(log(1:(n-k))); % ln of (n-k)!
out = round(exp(a-b-c)); % result
% End of function file.

The main program for evaluating the performance of the (511,385) BCH code is shown
below.

% File: ce11_5.m
zdB = 0:0.5:10; % set Eb/No in dB
z = 10.^(zdB/10); % convert to linear scale
ber1 = q(sqrt(z)); % FSK result
ber2 = q(sqrt(385*z/511)); % SER for (511,385) BCH code
ber3 = q(sqrt(768*z/1023)); % SER for (1023,768) BCH code
berbch1 = ser2ber1(2,511,29,14,ber2); % BER for (511,385) BCH code
berbch2 = ser2ber1(2,1023,53,26,ber3); % BER for (1023,768) BCH code
semilogy(zdB,ber1,’k-’,zdB,berbch1,’k--’,zdB,berbch2,’k-.’)
xlabel(’E_b/N_o in dB’) % label x axis
ylabel(’Bit Error Probability’) % label y axis
legend(’Uncoded’,’(511,385) BCH code’,’(1023,768) BCH code’,3)
% End of script file.

Note that this program calls ser2ber1 rather than ser2ber. In order to evaluate the
performance of the (1023,768) BCH code, it is necessay to modify the routine for mapping
the code symbol error rate so that the calculation is performed using logarithms as the
following MATLAB code indicates.

% File: ser2ber1.m
11.2. COMPUTER EXERCISES 51

function [ber] = ser2ber(q,n,d,t,ps)

lnps = length(ps); % length of error vector
ber = zeros(1,lnps); % initialize output vector
for k=1:lnps % iterate error vector
ser = ps(k); % channel symbol error rate
sum1 = 0; sum2 = 0; % initialize sums
for i=(t+1):d
lnterm = log(nkchoose(n,i))+(i*log(ser))+(n-i)*log((1-ser));
term = exp(lnterm);
sum1 = sum1+term;
end
for i=(d+1):n
lnterm = log(i)+log(nkchoose(n,i))+(i*log(ser))+(n-i)*log((1-ser));
term = exp(lnterm);
sum2 = sum2+term;
end
ber(k) = (q/(2*(q-1)))*((d/n)*sum1+(1/n)*sum2);
end
% End of function file.

Executing the program yields the results shown in Figure 11.15.

Computer Exercise 11.6

In order to work this computer exercise we write a MATLAB program to determine the
outputs for each of the 16 tree branches illustrated in Figure 11.25. The inputs for each
tree branch are illustrated in the right-hand column of Figure 11.25. The outputs for the
portion of the tree are generated by inputting the appropriate binary vector corresponding
the portion of the tree of interest. The MATLAB code follows.

% File: ce11_6.m
clear all
invector = input(’Enter input sequence as a vector (in brackets with spaces)
> ’);
d = [’The input sequence is ’,num2str(invector),’.’];
disp(d)
sr = [0 0 0];
for k=1:4
sr = [invector(1,k) sr(1,1) sr(1,2)];
v1 = dec2bin(rem(sr(1,1)+sr(1,2)+sr(1,3),2));
52 CHAPTER 11. SOURCE CODING AND ERROR CORRECTION TECHNIQUES

0
10

-5
10
Bit Error Probability

-10
10

-15
10

Uncoded
(511,385) BCH code
(1023,768) BCH code
-20
10
0 1 2 3 4 5 6 7 8 9 10
Eb/No in dB

Figure 11.15: Performance results for Computer Exercise 11.5.

11.2. COMPUTER EXERCISES 53

v2 = dec2bin(sr(1,1));
v3 = dec2bin(rem(sr(1,1)+sr(1,2),2));
c = [v1 v2 v3];
out(1,k) = bin2dec(c);
end
out = dec2bin(out)
% End of script file.

The program is illustrated by generating the outputs for the path labeled ’A’ in Figure
11.25., for which the input bit stream is 1010. The MATLAB dialog is as follows:

» ce11_6
Enter input sequence as a vector (in brackets with spaces) > [1 0 1 0]
The input sequence is 1 0 1 0.
out =
111
101
011
101

The four outputs are represented as the rows following ‘out’in the preceding dialog. This
corresponds to the sequence 111 101 011 101, which is Path A as shown in Figure 11.25 in
the text. (Note: If all outputs are 0, the sequence 000 is represented by a single 0.)

Computer Exercise 11.7

This Computer Exercise is worked by modifying the MATLAB code in the text (c11ce6.m)
to allow the calculation of results for = 0:1 and = 0:3 and plotting the results together
so that they are easily compared. The revised MATLAB code follows.

% File: ce11_7.m
g = [0.1 0.3]; % gamma
zdB = 0:0.1:10; % z in dB
z = 10.^(zdB/10); % vector of z values
qt = Q(sqrt(2*z)); % gamma=0 case
for k=1:2
q1 = Q((1-g(k))*sqrt(2*z));
q2 = Q((1+g(k))*sqrt(2*z));
p2 = q1-q2; % P2
p1 = q2; % P1
pe(k,:) = p1./(1-p2); % probability of error
54 CHAPTER 11. SOURCE CODING AND ERROR CORRECTION TECHNIQUES

N(k,:) = 1./((1-p2).*(1-p2));
end
subplot(2,2,1)
semilogy(zdB,pe(1,:),zdB,qt)
title(’gamma = 0.1’)
xlabel(’z - dB’); ylabel(’Error Probability’); grid
subplot(2,2,2)
semilogy(zdB,pe(2,:),zdB,qt)
title(’gamma = 0.3’)
xlabel(’z - dB’); ylabel(’Error Probability’); grid
subplot(2,2,3)
plot(zdB,N(1,:))
xlabel(’z - dB’); ylabel(’Ave. Transmissions/Symbol’);
axis([0 10 1 1.4]); grid
subplot(2,2,4)
plot(zdB,N(2,:))
xlabel(’z - dB’); ylabel(’Ave. Transmissions/Symbol’);
axis([0 10 1 1.4]); grid
% End of script file.

Executing the program gives the results shown in Figure 11.16. As expected, as is in-
creased, the error probability deceases at the cost of an increase in the average number
of transmissions. The key, however, is that increased performance is achieved with only a
moderate increase in the rate of retransmissions. This is especially true at higher SNRs.
11.2. COMPUTER EXERCISES 55

0
gamma = 0.1 0
gamma = 0.3
10 10
Error Probability

Error Probability
-5 -5
10 10

-10 -10
10 10
0 5 10 0 5 10
z - dB z - dB
Ave. Transmissions/Symbol

Ave. Transmissions/Symbol

1.4 1.4

1.3 1.3

1.2 1.2

1.1 1.1

1 1
0 5 10 0 5 10
z - dB z - dB

Figure 11.16: Performance results for feedback channel.