978-0072957167 Chapter 8 Part 1

Solutions Manual

for

Digital Communications, 5th Edition

(Chapter 8) 1

Prepared by

Kostas Stamatiou

January 30, 2008

Problem 8.1

(a) The encoder for the (3,1) convolutional code is depicted in the next figure.

✚✙

✛✘

✚✙

✛✘

❅❘❄



✠

✒

❅

❅■

❅❅❅❅



✏✏✏✏

✏✶

3

(b) The state transition diagram for this code is depicted in the next figure.

✍✌

✎☞

.

❥.

✛✲



✒

❅

❅■ 



✠

❅❅

❅❘

1/011

0/100

0/111

1/100

1/000

0/011

1/111

0/000

11

00

(c) In the next figure we draw two frames of the trellis associated with the code. Solid lines indicate

an input equal to 0, whereas dotted lines correspond to an input equal to 1.

✈

✈✈

✈

✈ ✈

✈

............ ......... . . . . . .. . . . . . .

.........

...........

✑

✑✑✑✑

✑

✓✓✓✓✓

✓

✓✓✓✓✓

✓

✑✑✑✑

✑

11

10

01

00

011

100

011

000

111

000

(d) The diagram used to find the transfer function is shown in the next figure.

3

✍✌

✎☞

❄

❅❘ ✲✲

✲D3J

NJ

D2J

D3NJ

D2NJ

Xd

Using the ﬂow graph results, we obtain the system

Xc=D3NJXa′+N JXb

Xb=D2JXc+DJXd

Eliminating Xb,Xcand Xdresults in

To find the free distance of the code we set N=J= 1 in the transfer function, so that

Problem 8.2

The code of Problem 8-1 is a (3,1) convolutional code with K= 3. The length of the received

sequence yis 15. This means that 5 symbols have been transmitted, and since we assume that the

information sequence has been padded by two 0’s, the actual length of the information sequence is

4

00

101 001 011 110 111

2

3

3 5

4

X X

X

Problem 8.3

(a) The encoder for the (3,1) convolutional code is depicted in the next figure.

✐

✲

❅

❅■

✻

✲

✲❄

❄

✲

❄

✻

✲

+

n= 3

k= 1

(b) The state transition diagram for this code is shown below

✒✑

✓✏

✒✑

✓✏

.

❥.

✒

❅❅

1/001

0/011

1/111

0/000

11

00

5

(c) In the next figure we draw two frames of the trellis associated with the code. Solid lines indicate

an input equal to 0, whereas dotted lines correspond to an input equal to 1.

✈

✈✈

✈

✈ ✈

✈

.........

............ ......... . . . . . .. . . . . . .

.........

...........

✑✑✑✑

✑

✓✓✓✓✓

✑

✑✑✑✑

✑

11

10

01

00

001

110

010

101

100

011

111

000

(d) The diagram used to find the transfer function is shown in the next figure.

✍✌

✎☞

❄

❅❅❅❅

✒

DN J

D2J

DN J

D3NJ

D2J

Xd

Using the ﬂow graph results, we obtain the system

Xc=D3NJXa′+DN JXb

Xb=D2JXc+D2JXd

Eliminating Xb,Xcand Xdresults in

T(D, N, J) = Xa′′

Xa′

=D7NJ3

1−DN J −D3N J2

(e) Since there is no self loop corresponding to an input equal to 1 such that the output is the all

zero sequence, the code is not catastrophic.

Problem 8.4

(a) The state transition diagram for this code is depicted in the next figure.

✍✌

✎☞

.

❥.

✛✲



✒

❅

❅■ 



✠

❅❅

❅❘

1/101

0/010

0/011

1/110

1/100

0/001

1/111

0/000

11

00

(b) The diagram used to find the transfer function is shown in the next figure.

✍✌

✎☞

❄

❅❅❅❅

✒

DN J

D2NJ

DJ

Xd

Using the ﬂow graph results, we obtain the system

Xc=D3NJXa′+DN JXb

Xb=DJXc+DJXd

Eliminating Xb,Xcand Xdresults in

(c) To find the free distance of the code we set N=J= 1 in the transfer function, so that

(d) The following figure shows 7 frames of the trellis diagram used by the Viterbi decoder. It is

assumed that the input sequence is padded by two zeros, so that the actual length of the information

7

00

110 110 110 111 010 101 100

2

4

6

3 4

3

4

6

7

X

(e) An upper to the bit error probability of the code is given by

Pb≤dT (D, N, J = 1)

dN 



N=1,D=√4p(1−p)

(1 −2D2)2

Problem 8.5

(a) The state transition diagram for this code is shown below

8

✍✌

✎☞

.

❥.

✒

❅❅

1/001

0/011

1/111

0/000

11

00

(b) The diagram used to find the transfer function is shown in the next figure.

✍✌

✎☞

❄

❅❅❅❅

✒

DN J

D2J

DN J

D3NJ

D2J

Xd

Using the ﬂow graph results, we obtain the system

Xc=D3NJXa′+DN JXb

Xb=D2JXc+D2JXd

(c) To find the free distance of the code we set N=J= 1 in the transfer function, so that

T1(D) = T(D, N, J)|N=J=1 =D7

1−D−D3=D7+D8+D9+···

(d) The following figure shows 6 frames of the trellis diagram used by the Viterbi algorithm to

decode the sequence {111,111,111,111,111,111}. The numbers on the nodes indicate the Hamming

9

Viterbi algorithm have been marked with an X. In the case of a tie of two merging paths, we delete

the upper path.

00

111 111 111 111 111 111

3

6

2 4

X

x

2

6

4

x

5

x

4

x

Problem 8.6

(a) The state transition diagram and the ﬂow diagram used to find the transfer function for this

code are depicted in the next figure.

✒✑

✓✏

.

❥.

0/00

00

Xd=NJXc+DN JXd

Xa′′ =DJXb

10

and by eliminating Xb,Xcand Xd, we obtain

To find the transfer function of the code in the form T(D, N ), we set J= 1 in T(D, N, J). Hence,

(b) To find the free distance of the code we set N= 1 in the transfer function T(D, N ), so that

(c) An upper bound on the bit error probability, when hard decision decoding is used, is given by

(see (8-2-34))

Pb≤1

k

dT (D, N )

dN 



N=1,D=√4p(1−p)

Since

(1 −(D+D3))2

D=√4p(1−p)

Problem 8.7

(a)

g1= [10], g2= [11],states : (a) = [0],(b) = [1]

The tree diagram, trellis diagram and state diagram are given in the following figures :

11

a

b

11

00

00 00 00

State

(a)

11

11 11

a b

00

11

10

(b) Redrawing the state diagram :

Xb=JN D2Xa+JNDXb⇒Xb=JN D2

1−JN D Xa

Hence :

Problem 8.8

(a)

g1= [111], g2= [101],states : (a) = [00],(b) = [01],(c) = [10],(d) = [11]

The tree diagram, trellis diagram and state diagram are given in the following figures :

0

a

b

d

c

b

c00

00

11

10

01

00

13

State

a

00 00 00 00

11

11 11

11

00 10

(b) Redrawing the state diagram :

d

JND

14







Xc=JN D2Xa+JNXb

Xb=JDXc+JDXd







⇒Xb=J2ND3

Problem 8.9

1. The state transition diagram is shown below

01

10

0/11

2. The transition diagram is shown below

YZ

and the Equations are

Xc=Y ZXa+Y ZXb

Xb=Xc+Z2Xd

15

Eliminating Xb,Xc, and Xd, we obtain

5. We use Equations 8.2-16–8.2-19 to find a bound on the bit error probability. First we note

that T(Y, Z) = Y Z3+Y2Z4+Y3Z5+…, hence a3=a4=a5= 1 and

P2(3) =

3

X

kpk(1 −p)3−k≈3p2

4

X

Problem 8.10

1. The state transition diagram is shown below

01

10

0/10

0/01

2. Non catastrophic since in the state transition diagram there are no loops of wight zero corre-

3. The transition diagram is shown below

16

YZ

Y

Z

Z 2



and the Equations are

Xc=Y ZXa+Y Xb

Xb=Z2Xc+ZXd

Eliminating Xb,Xc, and Xd, we obtain

4. Expanding T(Y, Z), we have

T(Y, Z) = Y Z4+Y2Z4+ 3Y3Z6+Y4Z6+…

5. We use Equations 8.2-16–8.2-19 to find a bound on the bit error probability. First we note

that T(Z) = 2Z4+ 4Z6+…, hence a4= 2, a6= 3 and

4

X

Problem 8.11

1. We have

p(r|s) = p(n=r−s)∝e−Pj|rj−cj|

2. Since soft decision decoding is employed, we use the bound given by Equation 8.2.15 with ∆

given by Equation 8.2.10. From 8.2.10 we have

∆ = Z∞

−∞ qp(r|c=pEc)p(r|c=−pEc)dr

=Z∞

The transfer function for this convolutional code was derived in the solution to Problem 8.10

and is given by

T(Y, Z) = T(Y, Z) = Y Z4+Y2Z4+ 3Y3Z6+Y4Z6+…

Therefore,

Pb≤3∆4+ 13∆6+…

3. Since the length of the received sequence is 12 and n= 2, we need a trellis of depth 6 which

is shown below

18

00 00 00 00 00 00

01 01 01 01

(-1,-1) (1.5,2) (0.7,-0.5) (-0.8,-3) (3,0.2) (0,1) 

0

5.5

6.7 8.9 11.1 14.1



###

#

5.3

Note that on the trellis each 0 corresponds to −√Ec=−1 and each 1 corresponds to √Ec= 1.

The accumulated metrics are shown in red on each node. The # denotes a path that is not

4. After hard decision decoding we have

The trellis and the metrics for hard decision decoding are shown below

00 00 00 00 00 00

01 01 01 01

(0,0) (1,1) (1,0) (0,0) (1,1) (0,1) 

0

2

3 3 3 2



##

2

5. For hard decision decoding we have

p=P(r > 0|c=−1)

1

and from Equation 8.2-14 we have ∆ = p4p(1 −p) = 0.775. If we use this new ∆ in the

error bound expression of part 3 we obtain

Problem 8.12