for m > 5, and they have all been composite. In fact, no more Fermat primes are

known today.

A complete proof of Gauss™s result is beyond the scope of this book, since it

requires more group and ¬eld theory than we have covered (see Stewart [35]).

However, we can prove the following.

Theorem 13.16. If p is a prime for which a regular p-gon is constructible, then

p is a Fermat prime.

Proof. Let ξp = cos(2π/p) + i sin(2π/p), a pth root of unity. If a regular

p-gon can be constructed, cos(2π/p) and sin(2π/p) are constructible numbers

and [Q(cos(2π/p), sin(2π/p)) : Q] = 2r for some integer r. Hence

[Q(cos(2π/p), sin(2π/p), i) : Q] = 2r+1 .

Now Q(ξp ) ⊆ Q(cos(2π/p), sin(2π/p), i) and so, by Theorem 11.6,

[Q(ξp ) : Q] = 2k for some integer k r + 1.

The pth root of unity, ξp , is a root of the cyclotomic polynomial φ(x) =

+ x p’2 + · · · + x + 1 which, by Example 9.31, is irreducible over Q. Hence

p’1

x

[Q(ξp ) : Q] = p ’ 1, and therefore p ’ 1 = 2k .

The number p = 2k + 1 is a prime only if k = 0 or k is a power of 2. Suppose

that k contains an odd factor b > 1 and that k = a · b. Then 2a + 1 divides

(2a )b + 1, since x + 1 divides x b + 1 if b is odd. Hence 2ab + 1 cannot be prime.

The case p = 2 gives rise to the degenerate 2-gon. Otherwise, p is a Fermat

m

prime, 22 + 1, for some integer m 0.

NONCONSTRUCTIBLE NUMBER OF DEGREE 4

This next example shows that Corollary 13.6 does not give a suf¬cient condition

for a number to be constructible.

NONCONSTRUCTIBLE NUMBER OF DEGREE 4 261

Example 13.17. There is a real root ri , of the irreducible polynomial x 4 ’ 4x + 2,

that is not constructible, even though [Q(ri ) : Q] = 22 .

Solution. By Eisenstein™s criterion, x 4 ’ 4x + 2 is irreducible over Q, so that

[Q(ri ) : Q] = 4 for each root ri . However, we can factor this polynomial into

two quadratics over R, say

x 4 ’ 4x + 2 = (x 2 + ax + b)(x 2 + cx + d).

Comparing coef¬cients, and then using equation (i), we have

(i) 0 = a + c c = ’a

and

(ii) 0 = b + d + ac and b + d = a 2

(iii) ’4 = bc + ad ’ 4 = a(d ’ b)

and

(iv) 2 = bd.

Let t = b + d, so that 16 = a 2 {(b + d)2 ’ 4bd} = t (t 2 ’ 8). This number t sat-

is¬es the equation

(v) t 3 ’ 8t ’ 16 = 0.

By Theorem 9.25, this equation (v) has no rational roots; thus t 3 ’ 8t ’ 16 is irre-

ducible over Q. We see from Figure 13.7 that the equation does have a real root ρ

between 3 and 4, and the coef¬cients a, b, c, d can be expressed in terms of ρ.

Either a or c is positive. Without loss of generality suppose that c > 0; thus

√ √

b + d = t = ρ, a = ’c = ’ ρ, and d ’ b = 4/ ρ. Therefore, we have b =

√ √

ρ/2 ’ 2/ ρ and d = ρ/2 + 2/ ρ, and the roots of x 2 + ax + b are

√

’a ± a 2 ’ 4b 1√ 8

= ρ± ’ρ + √ ,

2 2 ρ

which are real, since ρ < 4. These are the roots r1 and r2 in Figure 13.8.

t 3 ’ 8t ’ 16

16

r

’2 t=b+d

0 2 4

’16

Graph of t 3 ’ 8t ’ 16.

Figure 13.7.

262 13 GEOMETRICAL CONSTRUCTIONS

x 4 ’ 4x + 2

3

2

1

r1 r2 x

0 1

’1

Graph of x 4 ’ 4x + 2.

Figure 13.8.

If both these roots of x 4 ’ 4x + 2 are constructible, then (r1 + r2 )2 = ρ is

also constructible. But this is impossible, since ρ is a root of the irreducible

polynomial t 3 ’ 8t ’ 16 and [Q(ρ) : Q] = 3.

Hence x 4 ’ 4x + 2 has a real root that is not constructible.

This example was adapted from the article by Kalmanson [42].

EXERCISES

For Exercises 13.1 to 13.6, which of the numbers are constructible?

√

√

13.1. 4 5 + 2. 13.2. 6 2.

√

2

13.4. (1 ’ 4 7)3 .

√.

13.3.

1 + √7

√

13.5. 1 ’ 5 27. 13.6. 3 7 ’ 5 2.

13.7. Is Q(cos φ) = Q(sin φ) for every angle φ?

13.8. If tan φ is constructible, show how to construct the angle φ.

13.9. Prove that all the constructible numbers are algebraic over Q.

For the values of cos φ given in Exercises 13.10 to 13.13, determine whether you

can trisect the angle φ by straightedge and compass.

13.10. cos φ = 1/4. 13.11. cos φ = ’9/16.

√ √

13.12. cos φ = 1/ 2. 13.13. cos φ = 2/8.

13.14. By writing π/15 in terms of π/5 and π/3, show that it is possible to

trisect π/5 and also possible to construct a regular 15-gon.

13.15. Can π/7 be trisected?

13.16. Construct a regular pentagon using straightedge and compass only.

13.17. Prove that cos(2π/7) is a root of 8x 3 + 4x 2 ’ 4x ’ 1 and that 2 cos(2π/7)

is a root of x 3 + x 2 ’ 2x ’ 1. Hence show that a regular septagon is not

constructible.

EXERCISES 263

13.18. If the regular n-gon is constructible and n = qr, show that the regular

q-gon is also constructible.

13.19. Let ξ = cos(2π/p 2 ) + i sin(2π/p 2 ). Show that ξ is a root of

f (x) = 1 + x p + x 2p + · · · + x (p’1)p .

Prove that f (x) is irreducible over Q by applying Eisenstein™s criterion

to f (1 + x).

13.20. Using Exercises 13.18 and 13.19, prove that if a regular n-gon is

constructible, then n = 2k p1 · · · pr where p1 , . . . , pr are distinct Fermat

primes.

13.21. Prove that a regular 17-gon is constructible.

For Exercises 13.22 to 13.33, can you construct a root of the polynomials?

x 2 ’ 7x ’ 13. x 4 ’ 5.

13.22. 13.23.

x 8 ’ 16. x 3 ’ 10x 2 + 2.

13.24. 13.25.

x 4 + x 3 ’ 12x 2 + 7x ’ 1. x 5 ’ 9x 3 + 3.

13.26. 13.27.

x 6 + x 3 ’ 1. 3x 6 ’ 8x 4 + 1.

13.28. 13.29.

4x 4 ’ x 2 + 2x + 1. x 4 + x ’ 1.

13.30. 13.31.

x 48 ’ 1. x 4 ’ 4x 3 + 4x 2 ’ 2.

13.32. 13.33.

14

ERROR-CORRECTING CODES

With the increased use of electronic instrumentation and computers, there is a

growing need for methods of transmitting information quickly and accurately

over radio and telephone lines and to and from digital storage devices. In fact,

CDs and DVDs use error-correcting codes.

Over any transmission line, there is liable to be noise, that is, extraneous

signals that can alter the transmitted information. This is not very noticeable in

listening to the radio or even in reading a telegram, because normal English is

about 20% redundant. However, in transmissions from satellites and in computer

link-ups, the redundancy is usually zero; thus we would like to detect, and possi-

bly correct, any errors in the transmitted message. We can do this by putting the

message into a code that will detect and correct most of the errors. (These are

not the sorts of codes useful to a spy. Secret codes are made deliberately hard to

break, whereas error-correcting codes are designed to be easily decoded.)

One familiar code is the parity check digit that is usually attached to each

number inside a computer. A number is written in binary form and a check digit

is added that is the sum modulo 2 of the other digits. The sum of the digits

of any number and its check digit is always even unless an error has occurred.

This check digit will detect any odd number of errors but not an even number

of errors. This is useful if the probability of two errors occurring in the same

word is very small. When a parity check failure occurs in reading words from

a computer memory, the computer automatically rereads the faulty word. If a

parity check failure occurs inside the arithmetic unit, the program usually has to

be rerun.

All the codes we construct are obtained by adding a certain number of check

digits to each block of information. Codes can either be used simply to detect

errors or can be used to correct errors. A code that will detect 2t or fewer errors

can be used to correct t or fewer errors.

Error-detecting codes are used when it is relatively easy to send the original

message again, whenever an error is detected. The single parity check code in a

computer is an example of an error-detecting code.

Modern Algebra with Applications, Second Edition, by William J. Gilbert and W. Keith Nicholson

ISBN 0-471-41451-4 Copyright ™ 2004 John Wiley & Sons, Inc.

264

ERROR-CORRECTING CODES 265

Sometimes it is impossible or too expensive to retransmit the original message

when an error is detected. Error-correcting codes then have to be employed.

These are used, for example, in transmissions from satellites and space probes

(see Figure 14.1). The extra equipment needed to store and retransmit messages

from a satellite would add unnecessary weight to the payload. Error-correcting

codes are also used when transmitting data from computer memories to storage

Figure 14.1. In 1969 the Mariners 6 and 7 space probes sent back over 200 close-up photographs

of Mars. Each photograph was divided into 658,240 pixels and each pixel was given a brightness

level ranging from 1 to 28 . Therefore, each photograph required about 5 million bits of information.

These bits were encoded, using an error-correcting code, and transmitted at a rate of 16,200 bits

per second back to Earth, where they were received and decoded into photographs. (Courtesy of

NASA/JPL/Caltech.)

266 14 ERROR-CORRECTING CODES

devices. If a message containing an error is stored on a device, it may be weeks

before it is read and the error detected; by this time the original data might

be lost.

THE CODING PROBLEM

In most digital computers and many communication systems, information is han-

dled in binary form; that is, messages are formed from the symbols 0 and 1.

Therefore, in this chapter, we discuss only binary codes. However, most of the

results generalize to codes whose symbols come from any ¬nite ¬eld.

We assume that when a message is transmitted over a channel, the probability

of the digit 1 being changed into 0 is the same as that of 0 being changed into 1.

Such channels are called binary symmetric. Figure 14.2 illustrates what might

happen to a message over a noisy channel.

To transmit a message over a noisy channel, we break up the message into

blocks of k digits and we encode each block by attaching n ’ k check digits to

obtain a code word consisting of n digits, as shown in Figure 14.3. Such a code

is referred to as an (n, k)-code.

The code words can now be transmitted over the noisy channel, and after

being received, they can be processed in one of two ways. The code can be used

to detect errors by checking whether or not the received word is a code word.

If the received word is a code word, it is assumed to be the transmitted word. If

1 0 11 0 1 0 10 0

Transmission channel

Transmitter Receiver

e

is

no

Error detector

Encoder or

corrector

Original message Decoded message

Figure 14.2. Block diagram for error detection or correction.

(n, k)“

n ’ k check digits

k information digits k information digits

encoder

Message of k digits Code word of n digits

Figure 14.3. Encoding a block of k digits.

SIMPLE CODES 267

the received word is not a code word, an error must have occurred during trans-

mission, and the receiver can request that the word be retransmitted. However,

the code could also be used to correct errors. In this case, the decoder chooses

the transmitted code word that is most likely to produce each received word.

Whether a code is used as an error-detecting or error-correcting code depends

on each individual situation. More equipment is required to correct errors, and

fewer errors can be corrected than could be detected; on the other hand, when

a code only detects errors, there is the trouble of stopping the decoding process

and requesting retransmission every time an error occurs.

In an (n, k)-code, the original message is k digits long and there are 2k different

possible messages and hence 2k code words. The received words have n digits;

hence there are 2n possible words that could be received, only 2k of which are

code words.

The extra n ’ k check digits that are added to produce the code word are

called redundant digits because they carry no new information but only allow

the existing information to be transmitted more accurately. The ratio R = k/n is

called the code rate or information rate.

For each particular communications channel, it is a major problem to design

a code that will transmit useful information as fast as possible and, at the same

time, as reliably as possible.

It was proved by C. E. Shannon in 1948 that each channel has a de¬nite

capacity C, and for any rate R < C, there exist codes of rate R such that the

probability of erroneous decoding is arbitrarily small. In other words, by increas-

ing the code length n and keeping the code rate R below the channel capacity

C, it is possible to make the probability of erroneous decoding as small as we

please. However, this theory provides no useful method of ¬nding such codes.

For codes to be ef¬cient, they usually have to be very long; they may contain

100

2 messages and many times that number of possible received words. To be

able to encode and decode such long codes effectively, we look at codes that

have a strong algebraic structure.

SIMPLE CODES

We now compare two very simple codes of length 3. The ¬rst is the (3, 2)-code

that attaches a single parity check to a message of length 2. The parity check

is the sum modulo 2 of the digits in the message. Hence a received word is a

code word if and only if it contains an even number of 1™s. The code words are

given in Table 14.1. The second code is the (3, 1)-code that repeats a message,

consisting of a single digit, three times. Its two code words are illustrated in

Table 14.2.

If one error occurs in the (3, 2) parity check code during transmission, say

101 is changed to 100, then this would be detected because there would be an

odd number of 1™s in the received word. However, this code will not correct any

errors; the received word 100 is just as likely to have come from 110 or 000 as

from 101. This code will not detect two errors either. If 101 was the transmitted

268 14 ERROR-CORRECTING CODES

TABLE 14.1. (3, 2) TABLE 14.2. (3, 1)

Parity Check Code Repeating Code

Message Code Word Message Code Word

00 000 0 000

01 101 1 111

10 110

11 011

‘

parity check

code word and errors occurred in the ¬rst two positions, the received word would

be 011, and this would be erroneously decoded as 11.

The decoder ¬rst performs a parity check on the received word. If there are

an even number of 1™s in the word, the word passes the parity check, and the

message is the last two digits of the word. If there are an odd number of 1™s in

the received work, it fails the parity check, and the decoder registers an error.

Examples of this decoding are shown in Table 14.3.

The (3, 1) repeating code can be used as an error-detecting code, and it will

detect one or two transmission errors but, of course, not three errors. This same

code can also be used as an error-correcting code. If the received word contains

more 1™s than 0™s, the decoder assumes that the message is 1; otherwise, it

assumes that the message is 0. This will correctly decode messages containing

one error, but will erroneously decode messages containing more than one error.

Examples of this decoding are shown in Table 14.4.

One useful way to discover the error-detecting and error-correcting capabili-

ties of a code is by means of the Hamming distance. The Hamming distance

between two words u and v of the same length is de¬ned to be the number of

positions in which they differ. This distance is denoted by d(u, v). For example,

d(101, 100) = 1, d(101, 010) = 3, and d(010, 010) = 0.

TABLE 14.3. (3, 2) Parity Check Code Used to

Detect Errors

Received Word 101 111 100 000 110

Parity Check Passes Fails Fails Passes Passes

Received Message 01 Error Error 00 10

TABLE 14.4. (3, 1) Repeating Code Used

to Correct Errors

Received Word 111 010 011 000

Decoded Message 1 0 1 0

SIMPLE CODES 269

111

111 011

011

001

001

101

101

110

110 010

010

000 100

000 100

Figure 14.4. The code words of the (3,2) Figure 14.5. The code words of the (3,1)

parity check code are shown as large dots. repeating code are shown as large dots.

The Hamming distance between two words is the number of single errors

needed to change one word into the other. In an (n, k)-code, the 2n received

words can be thought of as placed at the vertices of an n-dimensional cube with

unit sides. The Hamming distance between two words is the shortest distance

between their corresponding vertices along the edges of the n-cube. The 2k code

words form a subset of the 2n vertices, and the code has better error-correcting

and error-detecting capabilities the farther apart these code words are. Figure 14.4

illustrates the (3,2) parity check code whose code words are at Hamming distance

2 apart. Figure 14.5 illustrates the (3,1) repeating code whose code words are at

Hamming distance 3 apart.

Proposition 14.1. A code will detect all sets of t or fewer errors if and only if

the minimum Hamming distance between code words is at least t + 1.

Proof. If r errors occur when the code word u is transmitted, the received

word v is at Hamming distance r from u. These transmission errors will be

detected if and only if v is not another code word. Hence all sets of t or fewer

errors in the code word u will be detected if and only if the Hamming distance

of u from all the other code words is at least t + 1.

Proposition 14.2. A code is capable of correcting all sets of t or fewer errors

if and only if the minimum Hamming distance between code words is at least

2t + 1.

Proof. Suppose that the code contains two code words u1 and u2 at Hamming

distance 2t or closer. Then there exists a received word v that differs from u1

and u2 in t or fewer positions. This received word v could have originated from

u1 or u2 with t or fewer errors and hence would not be correctly decoded in both

these situations.

Conversely, any code whose code words are at least 2t + 1 apart is capable

of correcting up to t errors. This can be achieved in decoding by choosing the

code word that is closest to each received word.

Table 14.5 summarizes these results.

270 14 ERROR-CORRECTING CODES

TABLE 14.5. Detection Capabilities of Various Codes

Minimum Distance Number of Number of

between Errors Errors Information

Code Code Words Detectable Correctable Rate

(3,2) parity check code 2 1 0 2/3

(3,1) repeating code 3 2 1 1/3

d ’1 (d ’ 1)/2

General (n, k) code d k/n

POLYNOMIAL REPRESENTATION

There are various ways that a word of n binary digits can be represented alge-

braically. One convenient way is by means of a polynomial in Z2 [x] of degree

less than n. The word a0 a1 · · · an’1 can be represented by the polynomial

a0 + a1 x + · · · + an’1 x n’1 ∈ Z2 [x].

We now use this representation to show how codes can be constructed.

Let p(x) ∈ Z2 [x] be a polynomial of degree n ’ k. The polynomial code

generated by p(x) is an (n, k)-code whose code words are precisely those poly-

nomials, of degree less than n, which are divisible by p(x).

A message of length k is represented by a polynomial m(x), of degree less

than k. In order that the higher-order coef¬cients in a code polynomial carry the

message digits, we multiply m(x) by x n’k . This has the effect of shifting the

message n ’ k places to the right. To encode the message polynomial m(x), we

divide x n’k m(x) by p(x) and add the remainder, r(x), to x n’k m(x) to form the

code polynomial

v(x) = r(x) + x n’k m(x).

This code polynomial is always a multiple of p(x) because, by the division

algorithm,

x n’k m(x) = q(x) · p(x) + r(x) where deg r(x) < n ’ k r(x) = 0;

or

thus

v(x) = r(x) + x n’k m(x) = ’r(x) + x n’k m(x) = q(x) · p(x).

(Remember r(x) = ’r(x) in Z2 [x].) The polynomial x n’k m(x) has zeros in the

n ’ k lowest-order terms, whereas the polynomial r(x) is of degree less than

n ’ k; hence the k highest-order coef¬cients of the code polynomial v(x) are

the message digits, and the n ’ k lowest-order coef¬cients are the check digits.

These check digits are precisely the coef¬cients of the remainder r(x).

POLYNOMIAL REPRESENTATION 271

For example, let p(x) = 1 + x 2 + x 3 + x 4 be the generator polynomial of a

(7, 3)-code. We encode the message 101 as follows:

message = 1 0 1

m(x) = 1 + x2

x 4 m(x) = x4 + x6

r(x) = 1 + x

v(x) = r(x) + x m(x) = 1 + x + x4 + x6

4

code word = 1 1 00 10 1

message

check digits

x2 + x + 1

x4 + x3 + x2 + 0 + 1 x6 +x 4

x 6 +x 5 +x 4 +x 2

+x 2

x5

x 5 +x 4 +x 3 +x

x 4 +x 3 +x 2 +x

x 4 +x 3 +x 2 +1

x+1

The generator polynomial p(x) = a0 + a1 x + · · · + an’k x n’k is always cho-

sen so that a0 = 1 and an’k = 1, since this avoids wasting check digits. If a0 = 0,

any code polynomial would be divisible by x and the ¬rst digit of the code word

would always be 0; if an’k = 0, the coef¬cient of x n’k’1 in the code polynomial

would always be 0.

Example 14.3. Write down all the code words for the code generated by the

polynomial p(x) = 1 + x + x 3 when the message length k is 3.

Solution. Since deg p(x) = 3, there will be three check digits, and since the

message length k is 3, the code word length n will be 6. The number of messages

is 2k = 8.

x+1

x 3 + 0 + x + 1 x 4 +x 3

+x 2 +x

x4

x 3 +x 2 +x

x3 x+1

+1

x2

Consider the message 110, which is represented by the polynomial m(x) =

1 + x. Its check digits are the coef¬cients of the remainder r(x) = 1 + x 2 ,

272 14 ERROR-CORRECTING CODES

obtained by dividing x 3 m(x) = x 3 + x 4 by p(x). Hence the code polynomial

is v(x) = r(x) + x 3 m(x) = 1 + x 2 + x 3 + x 4 , and the code word is 101110.

Table 14.6 shows all the code words.

A received message can be checked for errors by testing whether it is divisible

by the generator polynomial p(x). If the remainder is nonzero when the received

polynomial u(x) is divided by p(x), an error must have occurred during trans-

mission. If the remainder is zero, the received polynomial u(x) is a code word,

and either no error has occurred or an undetectable error has occurred.

Example 14.4. If the generator polynomial is p(x) = 1 + x + x 3 , test whether

the following received words contain detectable errors: (i) 100011, (ii) 100110,

(iii) 101000.

Solution. The received polynomials are 1 + x 4 + x 5 , 1 + x 3 + x 4 , and 1 + x 2 ,

respectively. These contain detectable errors if and only if they have nonzero

remainders when divided by p(x) = 1 + x + x 3 .

x2 + x + 1

x+1

x 3 + x + 1 x 5 +x 4 + 0+ 0+0+1

x 3 + x + 1 x 4 +x 3 + 0+0+1

+x +x

5 3 2

x

+x 2 +x

x4

x +x +x +1

4 3 2

x 3 +x 2 +x+1

+x +x

4 2

x

+x+1

x3

+x+1

x3

x2

+x+1

x3

0

0

x3 + x + 1 x 2 +0+1

0

+1

x2

Hence 1 + x 4 + x 5 is divisible by p(x), but 1 + x 3 + x 4 and 1 + x 2 are not.

Therefore, errors have occurred in the latter two words but are unlikely to have

occurred in the ¬rst.

Table 14.6 lists all the code words for this code. Hence, in Example 14.4 we

can tell at a glance whether a word is a code word simply by noting whether it is

on this list. However, in practice, the list of code words is usually so large that

it is easier to calculate the remainder when the received polynomial is divided

by the generator polynomial.

POLYNOMIAL REPRESENTATION 273

TABLE 14.6. (6, 3) Code Generated by 1 + x + x 3

Code Word

Message Check Digits Message Digits

0 0 0 0 0 0 0 0 0

1 0 0 1 1 0 1 0 0

0 1 0 0 1 1 0 1 0

0 0 1 1 1 1 0 0 1

1 1 0 1 0 1 1 1 0

1 0 1 0 0 1 1 0 1

0 1 1 1 0 0 0 1 1

1 1 1 0 1 0 1 1 1

‘ ‘ ‘ ‘ ‘ ‘ ‘ ‘ ‘

x2 x2 x3 x4 x5

1 1

x x

Furthermore, this remainder can easily be computed using shift registers.

Figure 14.6 shows a shift register for dividing by 1 + x + x 3 . The square boxes

represent unit delays, and the circle with a cross inside denotes a modulo 2 adder

(or exclusive OR gate).

The delays are initially zero, and a polynomial u(x) is fed into this shift register

with the high-order coef¬cients ¬rst. When all the coef¬cients of u(x) have been

fed in, the delays contain the remainder of u(x) when divided by 1 + x + x 3 . If

these are all zero, the polynomial u(x) is a code word; otherwise, a detectable

error has occurred. Table 14.7 illustrates this shift register in operation.

The register in Figure 14.6 could be modi¬ed to encode messages, because

the check digits for m(x) are the coef¬cients of the remainder when x 3 m(x)

x3 = 1 + x

u(x)

x0 x1 x2

(high order first)

Shift register for dividing by 1 + x + x 3 .

Figure 14.6.

Message

m(x)

Encoded

message

1

OR

x0 x1 x2 v(x)

2

Encoding circuit for a code generated by 1 + x + x 3 .

Figure 14.7.

274 14 ERROR-CORRECTING CODES

TABLE 14.7. Contents of the Shift Register When

1 + x 3 + x 4 Is Divided by 1 + x + x 3

Received Polynomial Register

Waiting to Enter Contents

Stage Register x0 x1 x2

← register initially zero

0 1 0 0 1 1 0 0 0 0

1 1 0 0 1 1 0 0 0

2 1 0 0 1 1 0 0

3 1 0 0 1 1 0

4 1 0 0 1 1

5 1 1 1 1

← remainder is x 2

6 0 0 1

is divided by 1 + x + x 3 . However, the circuit in Figure 14.7 is more ef¬cient

for encoding. Here the message m(x) is fed simultaneously to the shift register

and the output. While m(x) is being fed in, the switch is in position 1 and the

remainder is calculated by the register. Then the switch is changed to position 2,

and the check digits are let out to immediately follow the message.

This encoding circuit could also be used for error detection. When u(x) is fed

into the encoding circuit with the switch in position 1, the register calculates the

remainder of x 3 u(x) when divided by p(x). However, u(x) is divisible by p(x)

if and only if x 3 u(x) is divisible by p(x), assuming that p(x) does not contain a

factor x.

How is the generator polynomial chosen so that the code has useful properties

without adding too many check digits? We now give some examples.

Proposition 14.5. The polynomial p(x) = 1 + x generates the (n, n ’ 1) parity

check code.

Proof. By Proposition 9.33, a polynomial in Z2 [x] is divisible by 1 + x if and

only if it contains an even number of nonzero coef¬cients. Hence the code words

of a code generated by 1 + x are those words containing an even number of 1™s.

The check digit for the message polynomial m(x) is the remainder when xm(x) is

divided by 1 + x. Therefore, by the remainder theorem, Theorem 9.4, the check

digit is m(1), the parity of the number of 1™s in the message. This code is the

parity check code.

The (3, 1) code that repeats the single message digit three times has code

words 000 and 111, and is generated by the polynomial 1 + x + x 2 .

We now give one method, using primitive polynomials, of ¬nding a generator

for a code that will always detect single, double, or triple errors. Furthermore,

the degree of the generator polynomial will be as small as possible so that the

check digits are reduced to a minimum. Recall (see Proposition 11.29) that an

irreducible polynomial p(x) of degree m over Z2 is primitive if p(x)|(1 + x k )

for k = 2m ’ 1 and for no smaller k.

POLYNOMIAL REPRESENTATION 275

Theorem 14.6. If p(x) is a primitive polynomial of degree m, then the

(n, n ’ m)-code generated by p(x) detects all single and double errors whenever

n 2m ’ 1.

Proof. Let v(x) be a transmitted code word and u(x) = v(x) + e(x) be the

received word. The polynomial e(x) is called the error polynomial. An error is

detectable if and only if p(x) |u(x). Since p(x) does divide the code word v(x),

an error e(x) will be detectable if and only if p(x) |e(x).

If a single error occurs, the error polynomial contains a single term, say x i ,

where 0 i < n. Since p(x) is irreducible, it does not have 0 as a root; therefore,

p(x) |x i , and the error x i is detectable.

If a double error occurs, the error polynomial e(x) is of the form x i + x j

where 0 i < j < n. Hence e(x) = x i (1 + x j ’i ), where 0 < j ’ i < n. Now

p(x) |x i , and since p(x) is primitive, p(x) |(1 + x j ’i ) if j ’ i < 2m ’ 1. Since

p(x) is irreducible, p(x) |x i (1 + x j ’i ) whenever n 2m ’ 1, and all double

errors are detectable.

Corollary 14.7. If p1 (x) is a primitive polynomial of degree m, the

(n, n ’ m ’ 1)-code generated by p(x) = (1 + x)p1 (x) detects all double errors

and any odd number of errors whenever n 2m ’ 1.

Proof. The code words in the code generated by p(x) must be divisible by

p1 (x) and by (1 + x). The factor (1 + x) has the effect of adding an overall

parity check digit to the code. By Proposition 9.33, all the code words have an

even number of terms, and the code will detect any odd number of errors. Since

the code words are divisible by the primitive polynomial p1 (x), the code will

detect all double errors if n 2m ’ 1.

Some primitive polynomials of low degree are given in Table 14.8. For

example, by adding 11 check digits to a message of length 1012 or less, using the

generator polynomial (1 + x)(1 + x 3 + x 10 ) = 1 + x + x 3 + x 4 + x 10 + x 11 , we

can detect single, double, triple, and any odd number of errors. Furthermore, the

TABLE 14.8. Short Table of Primitive Polynomials

in Z2 [x ]

2m ’ 1

Primitive Polynomial Degree m

1+x 1 1

1 + x + x2 2 3

1 + x + x3 3 7

1 + x + x4 4 15

1 + x2 + x5 5 31

1 + x + x6 6 63

1 + x3 + x7 7 127

1 + x2 + x3 + x4 + x8 8 255

1 + x4 + x9 9 511

1 + x 3 + x 10 10 1023

276 14 ERROR-CORRECTING CODES

encoding and detecting can be done by a small shift register using only 11 delay

units. The number of different messages of length 1012 is 21012 , an enormous

¬gure! When written out in base 10, it would contain 305 digits.

MATRIX REPRESENTATION

Another natural way to represent a word a1 a2 . . . an of length n is by the element

(a1 , a2 , . . . , an )T of the vector space Zn = Z2 — Z2 — · · · — Z2 of dimension n

2

over Z2 . We denote the elements of our vector spaces as column vectors, and

(a1 , a2 , . . . , an )T denotes the transpose of (a1 , a2 , . . . , an ). In an (n, k)-code, the

2k possible messages of length k are all the elements of the vector space Zk , 2

whereas the 2n possible received words of length n form the vector space Zn . 2

An encoder is an injective function

γ : Zk ’ Zn

2 2

that assigns to each k digit message an n-digit code word.

An (n, k)-code is called a linear code if the encoding function is a linear

transformation from Zk to Zn . Nearly all block codes in use are linear codes, and

2 2

in particular, all polynomial codes are linear.

Proposition 14.8. Let p(x) be a polynomial of degree n ’ k that generates an

(n, k)-code. Then this code is linear.

Proof. Let γ : Zk ’ Zn be the encoding function de¬ned by the generator

2 2

polynomial p(x). Let m1 (x) and m2 (x) be two message polynomials of degree

less than k and let m1 and m2 be the same messages considered as vectors

in Zk . The code vector γ (mi ) corresponds to the code polynomial vi (x) =

2

ri (x) + x n’k mi (x), where ri (x) is the remainder when x n’k mi (x) is divided by

p(x). Now

v1 (x) + v2 (x) = r1 (x) + r2 (x) + x n’k [m1 (x) + m2 (x)],

and r1 (x) + r2 (x) has degree less than n ’ k; therefore, r1 (x) + r2 (x) is the

remainder when x n’k m1 (x) + x n’k m2 (x) is divided by p(x). Hence v1 (x) +

v2 (x) corresponds to the code vector γ (m1 + m2 ) and

γ (m1 + m2 ) = γ (m1 ) + γ (m2 ).

Since the only scalars are 0 and 1, this implies that γ is a linear trans-

formation.

Let {e1 , e2 , . . . , en } be the standard basis of the vector space Zn , that is, ei

2

contains a 1 in the ith position and 0™s elsewhere. Let G be the n — k matrix that

represents, with respect to the standard basis, the transformation γ : Zk ’ Zn ,2 2

de¬ned by an (n, k) linear code. This matrix G is called the generator matrix

or encoding matrix of the code.

MATRIX REPRESENTATION 277

If m is a message vector, its code word is v = Gm. The code vectors are the

vectors in the image of γ , and they form a vector subspace of Zn of dimension k.

2

The columns of G are a basis for this subspace, and therefore, a vector is a code

vector if and only if it is a linear combination of the columns of the generator

matrix G.

(Most coding theorists write the elements of their vector spaces as row vectors

instead of column vectors, as used here. In this case, their generator matrix is

the transpose of ours, and it operates on the right of the message vector.)

In the (3,2) parity check code, a vector m = (m1 , m2 )T is encoded as v =

(c, m1 , m2 )T , where the parity check c = m1 + m2 . Hence the generator matrix is

® ® «

11 11 c

m1

G = ° 1 0 » because ° 1 0 » = m1 .

m2

01 01 m2

If the code word is to contain the message digits in its last k positions, the

P

generator matrix must be of the form G = , where P is an (n ’ k) — k

Ik

matrix and Ik is the k — k identity matrix.

Example 14.9. Find the generator matrix for the (6,3)-code of Example 14.3 that

is generated by the polynomial 1 + x + x 3 .

Solution. The columns of the generator matrix G are the code vectors corre-

sponding to messages consisting of basis elements e1 = (1, 0, 0)T , e2 = (0, 1, 0)T ,

and e3 = (0, 0, 1)T . We see from Table 14.6 that the generator matrix is

®

101

1 1 1

0 1 1

G= .

1 0 0

°0 1 0»

001

Any message vector, m, in the (6,3)-code of Example 14.9 can be encoded by

calculating Gm. However, given any received vector u it is not easy to determine

from the generator matrix G whether or not u is a code vector. The code vectors

form a subspace, Im γ , of dimension k in Zn , generated by the columns of G.

2

We now ¬nd a linear transformation ·: Z2 ’ Z2 , represented by a matrix H ,

n’k

n

whose kernel is precisely Im γ . Hence a vector u will be a code vector if and

only if H u = 0. This proves (ii) in the following theorem.

Theorem 14.10. Let γ : Zk ’ Zn be the encoding function for a linear (n, k)-

2 2

P

code with generator matrix G = , where P is an (n ’ k) — k matrix and Ik

Ik

is the k — k identity matrix. Then the linear transformation

·: Zn ’ Z2

n’k

2

278 14 ERROR-CORRECTING CODES

de¬ned by the (n ’ k) — n matrix H = (In’k |P ) has the following properties:

(i) Ker · = Im γ .

(ii) A received vector u is a code vector if and only if H u = 0.

Proof. The composition · Ž γ : Zk ’ Z2 is the zero transformation because

n’k

2

P

HG = (In’k |P ) = (In’k P + P Ik ) = P + P = 0

Ik

using block multiplication of matrices over the ¬eld Z2 . Hence Im γ ⊆ Ker ·.

Since the ¬rst n ’ k columns of H consist of the standard basis vectors in

Z2 , Im · spans Z2 and contains 2n’k elements. By the morphism theorem

n’k n’k

for groups,

|Zn | 2n

|Ker ·| = = n’k = 2k .

2

|Im ·| 2

But Im γ also contains 2k elements, and therefore Im γ must equal Ker ·.

The (n ’ k) — n matrix H in Theorem 14.10 is called the parity check matrix

of the (n, k)-code.

The parity check matrix of the (3, 2) parity check code is the 1 — 3 matrix

H = 1 1 1 . A received vector u = (u1 , u2 , u3 )T is a code vector if and

only if ®

u1

H u = 1 1 1 ° u2 » = u1 + u2 + u3 = 0.

u3

The parity check matrix of the (3, 1)-code that repeats the message three

101

times is the 2 — 3 matrix H = . A received vector u = (u1 , u2 , u3 )T

011

is a code vector if and only if H u = 0, that is, if and only if u1 + u3 = 0 and

u2 + u3 = 0. In Z2 , this is equivalent to u1 = u2 = u3 .

The parity check matrix for the (6, 3)-code of Examples 14.3 and 14.9 is

®

1 0010 1

H = °0 1».

1011

0 0101 1

The received vector u = (u1 , . . . , u6 )T is a code vector if and only if

+ + = 0

u1 u4 u6

+ + + = 0

u2 u4 u5 u6

+ + = 0.

u3 u5 u6

MATRIX REPRESENTATION 279

That is, if and only if

= +

u1 u4 u6

= + +

u2 u4 u5 u6

= +

u3 u5 u6 .

In this code, the three digits on the right, u4 , u5 , and u6 , are the message

digits, whereas u1 , u2 , and u3 are the check digits. For each code vector u, the

equation H u = 0 expresses each check digit in terms of the message digits. This

is why H is called the parity check matrix.

Example 14.11. Find the generator matrix and parity check matrix for the

(9, 4)-code generated by p(x) = (1 + x)(1 + x + x 4 ) = 1 + x 2 + x 4 + x 5 . Then

use the parity check matrix to determine whether the word 110110111 is a

code word.

Solution. The check digits attached to a message polynomial m(x) are the

coef¬cients of the remainder when x 5 m(x) is divided by p(x). The message

polynomials are linear combinations of 1, x, x 2 , and x 3 . We can calculate the

remainders when x 5 , x 6 , x 7 , and x 8 are divided by p(x) as follows. [This is just

like the action of a shift register that divides by p(x).]

x 5 ≡ 1 + x 2 + x 4 mod p(x)

x 6 ≡ x + x 3 + x 5 ≡ 1 + x + x 2 + x 3 + x 4 mod p(x)

x 7 ≡ x + x 2 + x 3 + x 4 + x 5 ≡ 1 + x + x 3 mod p(x)

x 8 ≡ x + x 2 + x 4 mod p(x).

Therefore, every code polynomial is a linear combination of the following basis

polynomials:

+ + +

x2 x4 x5

1

1+ + + + + x6

x2 x3 x4

x

+ + +

x3 x7

1 x

+ + +

x2 x4 x8.

x

The generator matrix G is obtained from the coef¬cients of the polynomials

above, and the parity check matrix H is obtained from G. Hence

®

1110

0 1 1 1

®

1 1 0 1 1000011 1 0

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

1

G = 1 1 0 1 and H = 0 0 1 0 0 1 1 1.

0

°0 0 0 1 0 0 1 0»

1 0 0 0 1

0 1 0 0

0000111 0 1

°0 0 1 0»

0001

280 14 ERROR-CORRECTING CODES

If the received vector is u = ( 1 1 0 1 1 0 1 1 1 )T , H u =

( 1 0 0 1 1 )T and hence u is not a code vector.

P

Summing up, if G = is the generator matrix of an (n, k)-code, then

Ik

H = (In’k |P ) is the parity check matrix. We encode a message m by calculating

Gm, and we can detect errors in a received vector u by calculating H u. A linear

code is determined by either giving its generator matrix or by giving its parity

check matrix.

ERROR CORRECTING AND DECODING

We would like to ¬nd an ef¬cient method for correcting errors and decoding. One

crude method would be to calculate the Hamming distance between a received

word and each code word. The code word closest to the received word would

be assumed to be the most likely transmitted word. However, the magnitude of

this task becomes enormous as soon as the message length is quite large.

Consider an (n, k) linear code with encoding function γ : Zk ’ Zn . Let V =

2 2

Im γ be the subspace of code vectors. If the code vector v ∈ V is sent through a

channel and an error e ∈ Zn occurs during transmission, the received vector will

2

be u = v + e. The decoder receives the vector u and has to determine the most

likely transmitted code vector v by ¬nding the most likely error pattern e. This

error is e = ’v + u = v + u. The decoder does not know what the code vector

v is, but knows that the error e lies in the coset V + u.

The most likely error pattern in each coset of Zn by V is called the

2

coset leader.

The coset leader will usually be the element of the coset containing the smallest

number of 1™s. If two or more error patterns are equally likely, one is chosen

arbitrarily. In many transmission channels, errors such as those caused by a

stroke of lightning tend to come in bursts that affect several adjacent digits. In

these cases, the coset leaders are chosen so that the 1™s in each error pattern are

bunched together as much as possible.

The cosets of Zn by the subspace V can be characterized by means of the parity

2

check matrix H . The subspace V is the kernel of the transformation ·: Zn ’ 2

Z2 ; therefore, by the morphism theorem, the set of cosets Zn /V is isomorphic

n’k

2

to Im ·, where the isomorphism sends the coset V + u to ·(u) = H u. Hence the

coset V + u is characterized by the vector H u.

If H is an (n ’ k) — n parity check matrix and u ∈ Zn , then the (n ’ k)-

2

dimensional vector H u is called the syndrome of u. (Syndrome is a medical

term meaning a pattern of symptoms that characterizes a condition or disease.)

Every element of Z2 is a syndrome; thus there are 2n’k different cosets and

n’k

2n’k different syndromes.

Theorem 14.12. Two vectors are in the same coset of Zn by V if and only if

2

they have the same syndrome.

ERROR CORRECTING AND DECODING 281

Proof. If u1 , u2 ∈ Zn , then the following statements are equivalent:

2

(i) V + u1 = V + u2 , (ii) u1 ’ u2 ∈ V ,

(iii) H (u1 ’ u2 ) = 0, (iv) H u1 = H u2 .

We can decode received words to correct errors by using the

following procedure:

1. Calculate the syndrome of the received word.

2. Find the coset leader in the coset corresponding to this syndrome.

3. Subtract the coset leader from the received word to obtain the most likely

transmitted word.

4. Drop the check digits to obtain the most likely message.

For a polynomial code generated by p(x), the syndrome of a received poly-

nomial u(x) is the remainder obtained by dividing u(x) by p(x). This is because

the j th column of H is the remainder obtained by dividing x j ’1 by p(x). Hence

the syndrome of elements in a polynomial code can easily be calculated by means

of a shift register that divides by the generator polynomial.

Example 14.13. Write out the cosets and syndromes for the (6,3)-code with

parity check matrix ®

10 0101

H = °0 1 0 1 1 1».

00 1011

Solution. Each of the rows in Table 14.9 forms a coset with its corresponding

syndrome. The top row is the set of code words.

The element in each coset that is most likely to occur as an error pattern is

chosen as coset leader and placed at the front of each row. In the top row 000000

is clearly the most likely error pattern to occur. This means that any received

word in this row is assumed to contain no errors. In each of the next six rows,

TABLE 14.9. Syndromes and All Words of a (6,3) Code

Coset

Syndrome Leader Words

000 000000 110100 011010 111001 101110 001101 100011 010111

100 100000 010100 111010 011001 001110 101101 000011 110111

010 010000 100100 001010 101001 111110 011101 110011 000111

001 001000 111100 010010 110001 100110 000101 101011 011111

110 000100 110000 011110 111101 101010 001001 100111 010011

011 000010 110110 011000 111011 101100 001111 100001 010101

111 000001 110101 011011 111000 101111 001100 100010 010110

101 000110 110010 011100 111111 101000 001011 100101 010001

282 14 ERROR-CORRECTING CODES

there is one element containing precisely one nonzero digit; these are chosen as

coset leaders. Any received word in one of these rows is assumed to have one

error corresponding to the nonzero digit in its coset leader. In the last row, every

word contains at least two nonzero digits. We choose 000110 as coset leader.

We could have chosen 101000 or 010001, since these also contain two nonzero

digits; however, if the errors occur in bursts, then 000110 is a more likely error

pattern. Any received word in this last row must contain at least two errors. In

decoding with 000110 as coset leader, we are assuming that the two errors occur

in the fourth and ¬fth digits.

Each word in Table 14.9 can be constructed by adding its coset leader to the

code word at the top of its column.

A word could be decoded by looking it up in the table and taking the code

word at the top of the column in which it appears. When the code is large, this

decoding table is enormous, and it would be impossible to store it in a computer.

However, in order to decode, all we really need is the parity check matrix to

calculate the syndromes, and the coset leaders corresponding to each syndrome.

Example 14.14. Decode 111001, 011100, 000001, 100011, and 101011 using

Table 14.10, which contains the syndromes and coset leaders. The parity check

®

matrix is

100101

H = °0 1 0 1 1 1».

001011

Solution. Table 14.11 shows the calculation of the syndromes and the decod-

ing of the received words.

Example 14.15. Calculate the table of coset leaders and syndromes for the (9,4)

polynomial code of Example 14.11, which is generated by p(x) = 1 + x 2 +

x4 + x5.

TABLE 14.10. Syndromes

and Coset Leaders for a

(6,3) Code

Syndrome Coset Leader

000 000000

100 100000

010 010000

001 001000

110 000100

011 000010

111 000001

101 000110

ERROR CORRECTING AND DECODING 283

TABLE 14.11. Decoding Using Syndromes and Coset Leaders

Word received u 111001 011100 000001 100011 101011

Syndrome H u 000 101 111 000 001

Coset leader e 000000 000110 000001 000000 001000

Code word u + e 111001 011010 000000 100011 100011

Message 001 010 000 011 011

Solution. There is no simple algorithm for ¬nding all the coset leaders. One

method of ¬nding them is as follows.

We write down, in Table 14.12, the 25 possible syndromes and try to ¬nd their

corresponding coset leaders. We start ¬lling in the table by ¬rst entering the error

patterns, with zero or one errors, next to their syndromes. These will be the most

likely errors to occur. The error pattern with one error in the j th position is the j th

standard basis vector in Z9 and its syndrome is the j th column of the parity check

2

matrix H , given in Example 14.11. So, for instance, H (000000001) = 01101, the

last column of H .

The next most likely errors to occur are those with two adjacent errors. We

enter all these in the table. For example,

H (000000011) = H (000000010) + H (000000001)

= 11010 + 01101, the last two columns of H

= 10111.

This still does not ¬ll the table. We now look at each syndrome without a

coset leader and ¬nd the simplest way the syndrome can be constructed from the

columns of H . Most of them come from adding two columns, but some have to

be obtained by adding three columns.

TABLE 14.12. Syndromes and Their Coset Leaders for a (9,4) Code

Syndrome Coset Leader Syndrome Coset Leader Syndrome Coset Leader

00000 000000000 01011 000011100 10110 000111000

00001 000010000 01100 011000000 10111 000000011

00010 000100000 01101 000000001 11000 110000000

00011 000110000 01110 011100000 11001 110010000

00100 001000000 01111 000001010 11010 000000010

00101 000000110 10000 100000000 11011 000010010

00110 001100000 10001 001001000 11100 111000000

00111 001110000 10010 000000101 11101 000100100

01000 010000000 10011 001101000 11110 000010100

01001 010010000 10100 000011000 11111 000000100

01010 000001100 10101 000001000

284 14 ERROR-CORRECTING CODES

TABLE 14.13. Decoding Using Syndromes and Coset Leaders

Word received u 100110010 100100101 111101100 000111110

Syndrome Hu 01000 00000 10111 10011

Coset leader e 010000000 000000000 000000011 001101000

Code word u + e 110110010 100100101 111101111 001010110

Message 0010 0101 1111 0110

The (9,4)-code in Example 14.15 will, by Corollary 14.7, detect single, dou-

ble, and triple errors. Hence it will correct any single error. It will not detect all

errors involving four digits or correct all double errors, because 000000000 and

100001110 are two code words of Hamming distance 4 apart. For example, if

the received word is 100001000, whose syndrome is 00101, Table 14.12 would

decode this as 100001110 rather than 000000000; both these code words differ

from the received word by a double error.

Example 14.16. Decode 100110010, 100100101, 111101100, and 000111110

using the parity check matrix in Example 14.11 and the coset leaders in

Table 14.12.

Solution. Table 14.13 illustrates the decoding process.

BCH CODES

The most powerful class of error-correcting codes known to date were

discovered around 1960 by Hocquenghem and independently by Bose and

Chaudhuri. For any positive integers m and t, with t < 2m’1 , there exists a

Bose“Chaudhuri“Hocquenghem (BCH) code of length n = 2m ’ 1 that will

correct any combination of t or fewer errors. These codes are polynomial codes

with a generator p(x) of degree mt and have message length at least n ’ mt.

A t-error-correcting BCH code of length n = 2m ’ 1 has a generator poly-

nomial p(x) that is constructed as follows. Take a primitive element ± in the

Galois ¬eld GF(2m ). Let pi (x) ∈ Z2 [x] be the irreducible polynomial with ± i as

a root, and de¬ne

p(x) = lcm(p1 (x), p2 (x), . . . , p2t (x)).

It is clear that ±, ± 2 , ± 3 , . . . , ± 2t are all roots of p(x). By Exercise 11.56,

[pi (x)]2 = pi (x 2 ) and hence ± 2i is a root of pi (x). Therefore,

p(x) = lcm(p1 (x), p3 (x), . . . , p2t’1 (x)).

Since GF(2m ) is a vector space of degree m over Z2 , for any β = ± i , the

elements 1, β, β 2 , . . . , β m are linearly dependent. Hence β satis¬es a polynomial

of degree at most m in Z2 [x], and the irreducible polynomial pi (x) must also

BCH CODES 285

have degree at most m. Therefore,

deg p1 (x) · deg p3 (x) · · · deg p2t’1 (x)

deg p(x) mt.

Example 14.17. Find the generator polynomials of the t-error-correcting BCH

codes of length n = 15 for each value of t less than 8.

Solution. Let ± be a primitive element of GF (16), where ± 4 + ± + 1 = 0.

We repeatedly refer back to the elements of GF (16) given in Table 11.4 when

performing arithmetic operations in GF(16) = Z2 (±).

We ¬rst calculate the irreducible polynomials pi (x) that have ± i as roots. We

only need to look at the odd powers of ±. The element ± itself is the root of

x 4 + x + 1. Therefore, p1 (x) = x 4 + x + 1.

If the polynomial p3 (x) contains ± 3 as a root, it also contains

(± 3 )2 = ± 6 , (± 6 )2 = ± 12 , (± 12 )2 = ± 24 = ± 9 , (± 9 )2 = ± 18 = ± 3 .

and

Hence

p3 (x) = (x ’ ± 3 )(x ’ ± 6 )(x ’ ± 12 )(x ’ ± 9 )

= (x 2 + (± 3 + ± 6 )x + ± 9 )(x 2 + (± 12 + ± 9 )x + ± 21 )

= (x 2 + ± 2 x + ± 9 )(x 2 + ± 8 x + ± 6 )

= x 4 + (± 2 + ± 8 )x 3 + (± 9 + ± 10 + ± 6 )x 2 + (± 17 + ± 8 )x + ± 15

= x 4 + x 3 + x 2 + x + 1.

The polynomial p5 (x) has roots ± 5 , ± 10 , and ± 20 = ± 5 . Hence

p5 (x) = (x ’ ± 5 )(x ’ ± 10 )

= x 2 + x + 1.

The polynomial p7 (x) has roots ± 7 , ± 14 , ± 28 = ± 13 , ± 26 = ± 11 , and ± 22 = ± 7 .

Hence

p7 (x) = (x ’ ± 7 )(x ’ ± 14 )(x ’ ± 13 )(x ’ ± 11 )

= (x 2 + ±x + ± 6 )(x 2 + ± 4 x + ± 9 )

= x 4 + x 3 + 1.

Now every power of ± is a root of one of the polynomials p1 (x), p3 (x), p5 (x),

or p7 (x). For example, p9 (x) contains ± 9 as a root, and therefore, p9 (x) = p3 (x).

The BCH code that corrects one error is generated by p(x) = p1 (x) = x 4 +

x + 1.

The BCH code that corrects two errors is generated by

p(x) = lcm(p1 (x), p3 (x)) = (x 4 + x + 1)(x 4 + x 3 + x 2 + x + 1).

286 14 ERROR-CORRECTING CODES

This least common multiple is the product because p1 (x) and p3 (x) are different

irreducible polynomials. Hence p(x) = x 8 + x 7 + x 6 + x 4 + 1.

The BCH code that corrects three errors is generated by

p(x) = lcm(p1 (x), p3 (x), p5 (x))

= (x 4 + x + 1)(x 4 + x 3 + x 2 + x + 1)(x 2 + x + 1)

= x 10 + x 8 + x 5 + x 4 + x 2 + x + 1.

The BCH code that corrects four errors is generated by

p(x) = lcm(p1 (x), p3 (x), p5 (x), p7 (x))

= p1 (x) · p3 (x) · p5 (x) · p7 (x)

14

x 15 + 1

= = xi .

x+1 i=0

This polynomial contains all the elements of GF (16) as roots, except for 0 and 1.

Since p9 (x) = p3 (x), the ¬ve-error-correcting BCH code is generated by

p(x) = lcm(p1 (x), p3 (x), p5 (x), p7 (x), p9 (x))

= (x 15 + 1)/(x + 1),

and this is also the generator of the six- and seven-error-correcting BCH codes.

These results are summarized in Table 14.14.

For example, the two-error-correcting BCH code is a (15, 7)-code with gen-

erator polynomial x 8 + x 7 + x 6 + x 4 + 1. It contains seven message digits and

eight check digits.

The seven-error-correcting code generated by (x 15 + 1)/(x + 1) has message

length 1, and the two code words are the sequence of 15 zeros and the sequence

of 15 ones. Each received word can be decoded by majority rule to give the

TABLE 14.14. Construction of t-Error-Correcting BCH Codes of Length 15

Roots of Degree, Message

Degp(x) = 15 ’ k Length, k

t p2t’1 (x) p2t’1 (x) p(x)

±, ± 2 , ± 4 , ± 8

1 4 4 11

p1 (x)

± 3 , ± 6 , ± 12 , ± 9

2 4 8 7

p1 (x)p3 (x)

± 5 , ± 10

3 2 10 5

p1 (x)p3 (x)p5 (x)

(x 15 + 1)/(x + 1)

± 7 , ± 14 , ± 13 , ± 11

4 4 14 1

(x 15 + 1)/(x + 1)

± 9 , ± 3 , ± 6 , ± 12

5 4 14 1

(x 15 + 1)/(x + 1)

± 11 , ± 7 , ± 14 , ± 13

6 4 14 1

(x 15 + 1)/(x + 1)

± 13 , ± 11 , ± 7 , ± 14

7 4 14 1

BCH CODES 287

message 1, if the word contains more 1™s than 0™s, and to give the message 0

otherwise. It is clear that this will correct up to seven errors.

We now show that the BCH code given at the beginning of this section does

indeed correct t errors.

Lemma 14.18. The minimum Hamming distance between code words of a linear

code is the minimum number of ones in the nonzero code words.

Proof. If v1 and v2 are code words, then, since the code is linear, v1 ’ v2

is also a code word. The Hamming distance between v1 and v2 is equal to the

number of 1™s in v1 ’ v2 . The result now follows because the zero word is always

a code word, and its Hamming distance from any other word is the number of

1™s in that word.

Theorem 14.19. If t < 2m’1 , the minimum distance between code words in the

BCH code given in at the beginning of this section is at least 2t + 1, and hence

this code corrects t or fewer errors.

Proof. Suppose that the code contains a code polynomial with fewer than

2t + 1 nonzero terms,

v(x) = v1 x r1 + · · · + v2t x r2t where r1 < · · · < r2t .

This code polynomial is divisible by the generator polynomial p(x) and hence

has roots ±, ± 2 , ± 3 , . . . , ± 2t . Therefore, if 1 i 2t,

v(± i ) = v1 ± ir1 + · · · + v2t ± ir2t

= ± ir1 (v1 + · · · + v2t ± ir2t ’ir1 ).