<< стр. 11(всего 13)СОДЕРЖАНИЕ >>
that 22 + 1 is divisible by 641. Computers have checked many of these numbers
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 ).
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

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 .

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
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
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
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
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
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-

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
(6,3) Code

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
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 ).
 << стр. 11(всего 13)СОДЕРЖАНИЕ >>