Solutions Manual
for
Digital Communications, 5th Edition
(Chapter 7) 1
Prepared by
Kostas Stamatiou
January 11, 2008
2
Problem 7.1
1. Consider the sequence aifor i= 1,2,3,…. Since the group is finite all these elements cannot
3. First we note that Gais closed under multiplication, in fact we obviously have ak.am=al
4. If Ga∩ Gba 6=∅, then for some 1 ≤k, l ≤jwe have b.ak=al, resulting in b=al−kif l > k or
5. If there exits a c /∈ Ga∪ Gba, then we can generate Gac =c.a, c.a2, . . . , c.aj. The elements
of Gac are distinct and Ga∩ Gca 6=∅as shown in part 4. We can also show that Gba ∩ Gca 6=∅
6. Let βbe a nonzero element and let let kdenote the order of β, then βk= 1. But by part 5,
Problem 7.2
Problem 7.3
The Tables are shown below
+ 01234
0 01234
·01234
0 00000
Problem 7.4
There exist nine possible candidates of the form X2+aX +bwhere a, b ∈ {0,1,2}. From these
3
candidates X2, X2+X, X2+ 2Xare obviously irreducible. It is easily verified that X2+ 2 =
·0 1 2 X2X1 + X1 + 2X2 + X2 + 2X
0000000000
1 0 1 2 X2X1 + X1 + 2X2 + X2 + 2X
2 0 2 1 2X X 2 + 2X2 + X1 + 2X1 + X
Problem 7.5
In GF(8) primitive elements are elements of order 7. From Problem 7.1, the order of nonzero
elements are factors of q−1 = 7. From this we note that the order of a nonzero element is either
Problem 7.6
From Table 7.1-6, we note that α10 +α5+ 1 = α2+α+ 1 + α2+α= 1 and α10 ·α5=α15 = 1,
Problem 7.7
Elements of GF(32) are the roots of X32 −X=XX31 −1= 0 and elements of GF(4) are the
roots of XX3−1= 0. Since it can be easily verified that X3−1 does not divide X31 −1, we
Problem 7.8
The primitive polynomial of degree five is X5+X2+ 1 and the table is given below
4
Power Polynomial Vector
— 0 00000
α0=α31 1 00001
α1α00010
α2α200100
α11 α2+α+ 1 00111
α12 α3+α2+α01110
α13 α4+α3+α211100
α14 α4+α3+α2+ 1 11101
α15 α4+α3+α2+α+ 1 11111
α16 α4+α3+α+ 1 11011
α17 α4+α+ 1 10011
α26 α4+α2+α+ 1 10111
α27 α3+α+ 1 01011
α28 α4+α2+α10110
α29 α3+ 1 01001
α30 α4+α10010
5
For β=α3the conjugates are β2, β4, β8, and β16 and
φβ(X) = (X+β)(X+β2)(X+β4)(X+β8)(X+β16)
Problem 7.9
Note that Pp
smallest integer such that Pn
i=1 1 = 0 then nmust be a prime sine if n=kl, then
kl
X
i=1
1 = k
X
i=1
1!
l
X
j=1
1
= 0
resulting in either Pk
i=1 1 = 0 or Pl
j=1 1 = 0 contradicting that nis the smallest integer satisfying
Pn
Problem 7.10
Using the binomial expansion
(α+β)p=αp+
p−1
X
i=1 p
iαp−iβi+βp
Problem 7.11
A binary LBC is a linear subspace of the n-dimensional binary space. Denoting its dimension by
k, we can find a basis of size kfor this subspace of the form {e1,…,ek}. The codewords can be
Problem 7.12
1. If dH(x,y) = 0, then xand yagree at all components, hence x=y, if x=ythen obviously
2. dH(x, bmy) = dH(y,x) is obvious since xdisagrees with yat the same components that y
3. If for some 1 ≤i≤n,xi=yiand yi=zi, then xi=zi, therefore, the contribution of this
component to dH(x,y), dH(y,z), and dH(x,z) is zero. At other components dH(xi, yi) +
Problem 7.13
a. Interchanging the first and third rows, we obtain the systematic form :
1001110
b.
1 0 1 1 0 0 0
1 1 1 0 1 0 0
c. Since we have a (7,3) code, there are 23= 8 valid codewords, and 24possible syndromes. From
Error pattern Syndrome
0 0 0 0 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 1 0
0 0 0 0 1 0 0
0 1 0 0 0 1 0
0 0 0 1 1 0 1
0 0 0 0
0 0 0 1
0 0 1 0
0 1 0 0
0 1 0 1
1 0 1 1
d. We note that there are 3 linearly independent columns in H, hence there is a codeword Cm
Problem 7.15
Problem 7.16
8
1 0 1 1 0 0 0
1 0 0 0 1 0 1
Message XmCma =XmGaCmb =XmGb
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
0 0 0 0 0 0 0
0 0 0 1 0 1 1
0 0 1 0 1 1 0
0 0 1 1 1 0 1
1 0 1 1 0 0 0
1 0 1 0 0 1 1
1 0 0 1 1 1 0
1 0 0 0 1 0 1
0 0 0 0 0 0 0
0 0 0 1 0 1 1
0 0 1 0 1 1 0
0 0 1 1 1 0 1
1 0 0 0 1 0 1
1 0 0 1 1 1 0
1 0 1 0 0 1 1
1 0 1 1 0 0 0
Problem 7.17
The weight distribution of the (7,4) Hamming code is (n= 7) :
A(x) = 1
Problem 7.18
We have s1= (√Ec,0), s2= (0,√Ec) and
Hence
∆ = Zs1
(πN0)2e−1
N0(y2
1+(y1−√Ec)2+y2
2+(y2−√Ec)2)dy1dy2
=Z∞
−∞Z∞
−∞
1
πN0
e−1
2N0(y2
1+(y1−√Ec)2+y2
2+(y2−√Ec)2)dy1dy2
1
2N0(y2+(y−√Ec)2)dy2
=e−Ec
Problem 7.19
To fond the generator matrix we note that
G0=h1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1i
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
10
and
G0
Hence,
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1
0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1
To determine the parity check matrix we need to find 5 independent vectors that are orthogonal to
the rows of the generator matrix. We can verify that the following vectors satisfy this condition
h1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1i
h0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1i
and these are exactly the rows of the generator matrix for a Reed-Muller code of the first order
Problem 7.20
The generator matrix for this code is
G=h1 1 ··· 1i
Problem 7.21
For M-ary FSK detected coherently, the bandwidth expansion factor is :
W
RF SK
=M
2 log 2M
For the Hadamard code : In time T(block transmission time), we want to transmit nbits, so for
Problem 7.22
From (8-1-47) of the text, the correlation coefficient between the all-zero codeword and the l-th
codeword is ρl= 1 −2wl/n, where wlis the weight of the l-th codeword. For the maximum length
for all l. Since the code is linear if follows that ρ=−1/(M−1) between any pair of codewords.
Note : An alternative way to prove the above is to express each codeword in vector form as
where E=nEbis the energy per codeword and note that any one codeword differs from each other
at exactly 2m−1bits and agrees with the other at 2m−1−1 bits. Then the correlation coefficient is
Problem 7.23
1. The columns of the generator matrix are all sequences of length m, except the all-zero se-
quence. The codewords are all combinations of these rows. If the all-zero sequence was also
included, then when adding a number of rows of the matrix at a certain component ithere
2. From part one we have 2m−1 codewords each with weight 2m−1and one codeword with
3. Using MacWilliams identity
A(Z) = 2−(n−k)(1 + Z)nAd1−Z
1 + Z
n+ 1 h(1 + Z)n+n(1 −Z)n+1
Problem 7.24
We know that the (7,4) Huffman code has dmin = 3 and weight distribution (Problem 8.3) : w=0
For hard-decision decoding (8-1-82):
7
X
1
X
13
where p=Q√2Rcγb=Qq8
7γbor (8-1-90) :
Problem 7.25
The number of errors is dand the number of components received with no error is n−d. Therefore,
Problem 7.26
Using a symbolic program, the weight distribution polynomial for the (15,11) code is given by
and for undetected error
Pu(E) = 2−(n−k)B(1 −2p)−(1 −p)n
Plots of these two error probabilities are given below
10−6 10−5 10−4 10−3 10−2 10−1
10−16
10−14
10−12
10−10
10−8
10−6
10−4
10−2
100
p
Uncorrected error
Undetected error
Problem 7.27
Using a symbolic program we obtain the wight distribution function
1 + 651 Z3+ 9765 Z4+ 109368 Z5+ 1057224 Z6+ 8649279 Z7+ 60544953 Z8+ 369776680 Z9
+ 1996794072 Z10 + 9621890019 Z11 + 41694856749 Z12 + 163568562192 Z13 + 584173436400 Z14
+13449656041565856 Z33 +11867343566087520 Z34 +9832942289229633 Z35 +7647844002734159 Z36
+5580858785942664 Z37 +3818482327223928 Z38 +2447745309517725 Z39 +1468647185710635 Z40
Problem 7.29
Let the coset leader of the row of the standard array be e, then the two elements can be denoted
Problem 7.30
1. Assume two elements of the form ei+cjand el+cmare equal. Then
2. Let ei+cjand el+cm, where ei6=elhave the same syndrome, then
Problem 7.31
Since all codewords of the new code have odd parity, the all-zero sequence is not a codeword and
Problem 7.32
1. The generator matrix is
1 0 0 0 1 1 0 1
0 0 0 1 1 1 1 0
2. M= 2k= 16 codewords and any three columns of Hare linearly independent but we can
Problem 7.33
4. The probability of an undetected error is the probability of receiving another codeword. If
111000 is transmitted there exist 9 codewords that are at distance 2 from it and 9 codewords
5. C1must contain all codewords of Cand all linear combinations of them. Since for each
Problem 7.34
1 0 0 1 1 0
1 0 1 1 0 0
Then the standard array is :
000 001 010 011 100 101 110 111
000000 001101 010011 011110 100110 101011 110101 111000
000001 001100 010010 011111 100111 101010 110100 111001
010000 011101 000011 001110 110110 111011 100101 101000
For each column, the first row is the message, the second row is the correct codeword corresponding
to this message, and the rest of the rows correspond to the received words which are the sum of the
EiSi=EiHT
000000
000001
000010
000
001
010
Problem 7.35
17
1 0 0 1 0 1 1
1 1 0 1 0 0 0
Then, the standard array will be :
000
0000000
0000001
0000010
1100000
1010000
1001000
1000100
001
0010111
0010110
0010101
1110111
1000111
1011111
1010011
010
0101110
0101111
0101101
1001110
1111110
1100110
1101010
011
0111001
0111000
0111011
1011001
1101001
1110001
1111101
100
1001011
1001010
1001001
0101011
0011011
0000011
0001111
101
1011100
1011101
1011110
0111100
0001100
0010100
0011000
110
1100101
1100100
1100111
0000101
0110101
0101101
0100001
111
1110010
1110011
1110000
0010010
0100010
0111010
0110110
For each column, the first row is the message, the second row is the correct codeword corresponding
to this message, and the rest of the rows correspond to the received words which are the sum of the
18
are :
EiSi=EiHT
0000000
0000001
1100000
1010000
1001000
0000
0001
0101
11000
0011
Problem 7.36
1. The parity check equations are c1+c2+c4= 0, c2+c3+c5= 0, and c1+c3+c6= 0. These