978-0072957167 Chapter 7 Part 2

19

and G= [I P ],

1 0 0 1 1 0



2.

1 1 0 1 0 0



3. No two columns of Hare equal, but columns 2, 4, and 5 are linearly dependent. Therefore the

Problem 7.37

1. Since the rows of Gall have weight four, no linear combination of them can have odd weight.

2. We need to design a LBC with dmin at least three. One example is

1 0 0 0 1 1



3. One suggestion is

0 0 0 0 1 1



Problem 7.38

Since the code is MDS, then dmin =n−k+ 1 and hence any n−kcolumns of H, the parity check

matrix of C, are linearly independent. But His the generator matrix of C⊥. Let us assume that

C⊥is not MDS. Since this is an (n, n −k) code, it must have a codeword of weight less than or

Problem 7.39

1. Since n

i=n

n−i, we have

t

X

i=

n

X

i

2λ(n−t)

t

X

i=0 n

i= 2λ(n−t)

n

X

i=n−tn

i

n

X

i=0

2. From part 1 we have

t

X

i≤(1 + 2λ)n2−λn(1−t/n)

3. Substitution of λ= log2(1 −p)−log2pin the result of part 2 gives

i=0 n

4. First we note that as long as t < n/2, the dominating term in the sum is n

to zero as ntends to infinity. Therefore, for large n,

t

X

i=0 n

i≈n

t

Denoting q= 1 −p, we have t=np and n−t=nq and

1

nlog n

t≈1

n1

2log(2πn) + nlog n−n−1

2log(2πnp)−np log(np) + np−

21

i=0 n

Problem 7.40

1. Since no all-zero column exists in G, for each position 1 ≤i≤nthere exists at least one

codeword that is nonzero at that position, therefore no column of the Cis all-zero. Let

1≤i≤n, and define

Let c∈C1, adding it to each d∈C1gives c+d∈C0, hence |C1| ≤ |C0|. Adding cto each

2. The total weight of the codewords is the weight of C. Since each column has weight 2k−1,

3. There are 2k−1 codewords with weight at least dmin and a single codeword of weight zero.

Problem 7.41

We have already generated an extended (8,4) code from the (7,4) Hamming code in Probl. 8.5.

Since the generator matrix for the (7,4) Hamming code is not unique, in this problem we will

construct the extended code, starting from the generator matrix given in 8-1-7 :





1 0 0 0 1 0 1





1 1 1 0 1 0 0



Then :





1 1 1 0 1 0 0 0

0 1 1 1 0 1 0 0





22

We can bring this parity matrix into systematic form by adding rows 1,2,3 into the fourth row :



1 1 1 0 1 0 0 0

1 0 1 1 0 0 0 1



Then :



1 0 0 0 1 0 1 1

0 0 0 1 0 1 1 1



Problem 7.42

a. The generator polynomial for the (15,11) Hamming code is given as g(p) = p4+p+ 1.We will

p4=g(p) + p+ 1

p5=pg(p) + p2+p

p6=p2g(p) + p3+p2

p12 = (p8+p5+p4+p2+ 1)g(p) + p3+p2+p+ 1

23

row) for the parity matrix Pwe obtain :





100000000001001

010000000001101

001000000001111

000000100000101

000000010001011





Then, the generator polynomial for the dual code is given by :

Problem 7.43

We can determine G, in a systematic form, from the generator polynomial g(p) = p3+p2+ 1:

p6= (p3+p2+p)g(p) + p2+p

p3=g(p) + p2+ 1





1 0 0 0 1 1 0

0 0 0 1 1 0 1





1 0 1 1 1 0 0



Hence, the parity check matrix for the extended code will be (according to 8-1-15) :





1 0 1 1 1 0 0 0

1 1 1 1 1 1 1 1





and in systematic form (we add rows 1,2,3 to the last one) :





1 0 1 1 1 0 0 0

1 1 1 0 0 1 0 0









1 0 0 0 1 1 0 1

0 1 0 0 0 1 1 1





Note that Ges can be obtained from the generator matrix Gfor the initial code, by adding an

overall parity check bit. The code words for the extended systematic code are :

Message XmCodeword Cm

0 0 0 0

0 0 0 1

0 1 0 1

0 1 1 0

0 1 1 1

1 0 1 1

1 1 0 0

1 1 0 1

0 0 0 0 0 0 0 0

0 0 0 1 1 0 1 1

0 1 0 1 1 1 0 0

0 1 1 0 1 0 0 1

0 1 1 1 0 0 1 0

1 0 1 1 1 0 0 0

1 1 0 0 1 0 1 0

1 1 0 1 0 0 0 1

An alternative way to obtain the codewords for the extended code is to add an additional check bit

Problem 7.44

a. We have obtained the generator matrix Gfor the (15,11) Hamming code in the solution of

Problem 8.4. The shortened code will have a generator matrix Gsobtained by G, by dropping its

25

first 7 rows and the first 7 columns or :



1 0 0 0 1 0 1 1

0 0 0 1 0 0 1 1



Then the possible messages and the codewords corresponding to them will be :

Message XmCodeword Cm

0 0 0 0

0 0 0 1

0 0 1 0

0 1 1 1

1 0 0 0

1 0 0 1

1 1 0 1

1 1 1 0

1 1 1 1

0 0 0 0 0 0 0 0

0 0 0 1 0 0 1 1

0 0 1 0 0 1 1 0

0 1 1 1 1 0 0 1

1 0 0 0 1 0 1 1

1 0 0 1 1 0 0 0

1 1 0 1 0 1 0 0

1 1 1 0 0 0 0 1

1 1 1 1 0 0 1 0

Problem 7.45

a.

g(p) = (p4+p3+p2+p+ 1)(p4+p+ 1)(p2+p+ 1) = p10 +p8+p5+p4+p2+p+ 1

26

Factoring pl, l = 14, …10,into pl=g(p)Ql(p) + Rl(p) we obtain the generator matrix in systematic

form :

p14 = (p4+p2+ 1)g(p) + p9+p7+p4+p3+p+ 1

p13 = (p3+p)g(p) + p9+p8+p7+p6+p4+p2+p





b.

c. The error-correcting capability of the code is :

e.

g(p) = (p15 + 1)/(p2+p+ 1) = p13 +p12 +p10 +p9+p7+p6+p4+p3+p+ 1

Then :

Hence, the generator matrix is :

101101101101101

27

and the valid codewords :

XmCodeword Cm

0 0

0 1

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 1 1 0 1 1 0 1 1 0 1 1 0 1 1

Problem 7.46

The polynomial p7+ 1 is factors as follows : p7+ 1 = (p+ 1)(p3+p2+ 1)(p3+p+ 1).The generator

polynomials for the matrices G1,G2are : g1(p) = p3+p2+ 1, g2(p) = p3+p+ 1.Hence the parity

Problem 7.47

The generator matrix for the systematic (7,4) cyclic Hamming code is given by (8-1-37) as :



1 0 0 0 1 0 1



28

Then, the correctable error patterns Eiwith the corresponding syndrome Si=EiHTare :

Si

000

001

110

111

Ei

0000000

0000001

0100000

0010000

Problem 7.48

a. Let g(p) = p8+p6+p4+p2+ 1 be the generator polynomial of an (n, k) cyclic code. Then,

n−k= 8 and the rate of the code is

R=k

n= 1 −8

n

The rate Ris minimum when 8

b. In the next table we list the four codewords of the (10,2) cyclic code generated by g(p).

Input X(p) Codeword

00 0 0000000000

29

c. The coding gain of the (10,2) cyclic code in part (a) is

Problem 7.49

a. For every n

pn+ 1 = (p+ 1)(pn−1+pn−2+···+p+ 1)

b. The ith row of the generator matrix has the form

gi= [ 0··· 0 1 0 ··· 0pi,1]





0··· 1|1



c. A vector c= [c1, c2,…,cn] is a codeword of the (n, n −1) cyclic code if it satisfies the condition

cHt= 0. But,





1





Problem 7.50

a. The generator polynomial of degree 4 = n−kshould divide the polynomial p6+ 1. Since the

we find that the shortest possible generator polynomial of degree 4 is

g(p) = p4+p2+ 1

where the 1 corresponds to the i-th column (to give a systematic code) and the pi,1,…,pi,4are

obtained from the relation

p6−i+pi,1p3+pi,2p2pi,3p+pi,4=p6−i( mod p4+p2+ 1)

0 1 



0 1 0 1 

The codewords of the code are

c1= [ 0 0 0 0 0 0 ]

c2= [ 1 0 1 0 1 0 ]

b. The minimum distance of the linear (6,2) cyclic code is dmin =wmin = 3. Therefore, the code

Problem 7.51

1. In general Cmax is not a cyclic code. The codewords of C1are of the form a(X)g1(X) and the

2. Cmin is in general a cyclic code. Let g(X) = GCD{g1(X), g2(X)}since both g1(X) and g2(X)

divide each codeword of Cmin,g(X) also divides each codewords of Cmin. Since g1(X) and

Problem 7.52

2. We have

X10 + 1 = (X+ 1)2(X4+X3+X2+X+ 1)2

3. There are only four codewords in this code. The nonzero codewords are obtained by multi-

5. We use the bound given by Equation 7.5-17. The resulting code has two codewords of weight



Z=√4p(1−p)

Problem 7.53

32

The possible generator polynomials (including the degenerate ones) are

g0(X) = 1

g1(X) = X+ 1

Problem 7.54

We have e(X) = a(X)g(X) + s(X) and e(1)(X) = Xe(X) + en−1(Xn+ 1). From these relations

Problem 7.55

The statement is false. Consider the (8,5) code with g(X) = X3+X2+X+ 1. The codeword

Problem 7.56

From Problem 7.8, φα(X) = X5+X2+ 1 and φα3(X) = X5+X4+X3+X2+ 1. Therefore,

Problem 7.57

We have r(X) = 1 + X3+X6+X9+X10 and

S1=r(α) = 1 + α3+α6+α9+α10 =α3

S2=r(α2) = 1 + α6+α12 +α18 +α20 =α6

33

µ σ(µ)(X)dµlµµ−lµ

−1 1 1 0 −1

0 1 α30 0

Hence, σ(X) = 1 + α3X+α13X2. This polynomial has two roots, α23 and α26 which are the

Problem 7.58

Here r(X) = 1 + X3+X5+X6+X8+X9+X10 +X28 +X29 +X30. We have

S1= 1 + α3+α5+α6+α8+α9+α10 +α28 +α29 +α30 =α8

and we have the following table

µ σ(µ)(X)dµlµµ−lµ

−1 1 1 0 −1

0 1 α80 0

Problem 7.59

34

the generator matrix of the shortened code is obtained by removing the first three rows of G, we

perform the above calculations for l= 4,5,6,7,only :

p11 = (p3+p2+ 1)g(p) + p4+p3+p2+ 1

p10 = (p2+p)g(p) + p7+p6+p5+p2+p

Hence :





1 0 0 0 0 0 0 1 1 1 0 1





Problem 7.60

Since N= 2m−1 = 7, we have a code over GF(8). The generator polynomial is given by

g(X) = (X+α)(X+α2)(X+α3)(X+α4) = X4+α3X3+X2+αX +α3

Problem 7.61

With N= 63 = 2m−1 we have m= 6 and the code is over GF(26). The primitive polynomial

generating this field is obtained from Table 7.1-5 to be X6+X+ 1, based on which we have to

generate the field table. If αis a primitive element in this field we have

g(X) = (X+α)(X+α2)(X+α3)(X+α4)(X+α5)(X+α6)

Problem 7.62

From Equation 7.11-4 we have

Ai=N

iN

i−Dmin

X

j=0

(−1)ji−1

j(N+ 1)i−j−Dmin ,for Dmin ≤i≤N

35

Problem 7.63

Let the n2×n1matrix of Figure 7.13-1 be denoted by C. Then cij =uij for 1 ≤i≤k2and

1≤j≤k1, where uij denotes the information sequence. Let G1and G2denote the generator

matrices of the row and column codes, respectively, then

For 1 ≤i≤k2and k1+ 1 ≤j≤n1, using the row code generator matrix we have

k1

X

l=1

and for k2+ 1 ≤i≤n2and 1 ≤j≤k1using the column code we have

k2

X

m=1

For k2+ 1 ≤i≤n2and k1≤j≤n1, if we use the row code we have

k1

X

l=1

k1

X

l=1

k2

X

m=1

and if we use the column code we obtain

k2

X

k2

X

k1

X

Problem 7.64

We first prove that there exists no nonzero code word with weight less than d1d2and then show

that there exists at leas one codeword with weight d1d2. Let cbe a nonzero codeword, and let

36

with weight d1d2. Let the bmc(1) be a codeword of length n1and weight d1for the row code and

c(2) be a codeword of length n2and weight d2for the column code. Assume we pick d2copies of