# MATHEMATICS

The 16 codewords in this code C can be found by taking all possible sums of the rows of G. We leave this as an exercise at the end of the chapter.

To show that the Hamming codes are perfect codes we first need to establish two lemmas.

Lemma 5 A Hamming code of order r contains 2n−r codewords where n = 2r − 1. Proof: The parity check matrix of the Hamming code is an r × n matrix. It follows that the generator matrix for this code is a (n − r) × n matrix. Recall that the codewords are the linear combinations of the rows. As the reader can show, no two linear combinations of the rows are the same. Since there are 2n−r different linear combinations of row, there are 2n−r different codewords in a Hamming code of order r.

Lemma 6 The minimum distance of a Hamming code of order r is 3 when- ever r is a positive integer.

Proof: The parity check matrix Hr has columns which are all nonzero and no two of which are the same. Hence, from our earlier discussion, a Hamming code of order r can correct single errors. By Theorem 3 we conclude that the minimum distance of this code is at least 3. Among the columns of Hr are the

90 Applications of Discrete Mathematics

following three columns:

c1 =

⎛ ⎜⎜⎜⎜⎝

1 1 0 … 0

⎞ ⎟⎟⎟⎟⎠ , c2 =

⎛ ⎜⎜⎜⎜⎝

1 0 0 … 0

⎞ ⎟⎟⎟⎟⎠ , c3 =

⎛ ⎜⎜⎜⎜⎝

0 1 0 … 0

⎞ ⎟⎟⎟⎟⎠ .

Note that c1 + c2 + c3 = 0. Let x be the bit string with 1 in the positions of these columns and zero elsewhere. Then Hxt = 0, since it is c1 + c2 + c3. It follows that x is a codeword. Since w(x) = 3, by Theorem 6 it follows that the minimum distance is no more than 3. We conclude that the minimum distance of a Hamming code of order r is 3.

Theorem 7 The Hamming code of order r is a perfect code.

Proof: Let n = 2r −1. By Lemma 5 a Hamming code of order r contains 2n−r codewords, each of which is an n-tuple. By Lemma 6 the minimum distance of the Hamming code of order r is 3. We see that this code achieves the maximum number of codewords allowed by the sphere packing bound. To see this, note that

2n−r(1 + C(n, 1)) = 2n−r(1 + n) = 2n−r(1 + 2r − 1) = 2n. This is the upper bound of the sphere-packing bound. hence a Hamming code of order r is perfect.

By Theorem 7 we see that the Hamming codes are examples of perfect codes. The study of perfect codes has been one of the most important areas of research in coding theory and has lead to the development of many important results. See the references at the end of the chapter to learn about what is known about perfect codes.

Summary In this chapter we have studied how codes can be used for error detection and error correction. We have introduced an important class of codes known as the Hamming codes. However, we have only touched the surface of a fascinating and important subject that has become extremely important for modern computing and communications. The interested reader can consult the references listed at the end of this chapter to learn about many other classes of codes that have practical applications.

Chapter 5 Coding Theory 91

For example, pictures of the planets taken by space probes have been en- coded using powerful codes, such as a code known as the Reed-Muller code (see [5] for details). This code has been used to encode the bit string of length 6 representing the brightness of each pixel of an image by a bit string of length 32. This Reed-Muller code consists of 64 codewords, each a bit string of length 32, with minimum distance 16. Another interesting example is the use of a family of codes known as Reed-Solomon codes used in digital audio recording (see [5] for details). Finally, many concepts and techniques from both linear algebra and abstract algebra are used in coding theory. Studying coding theory may con- vince the skeptical reader about the applicability of some of the more abstract areas of mathematics.

Suggested Readings

1. E. Berlekamp, editor, Key Papers in the Development of Coding Theory , IEEE Press, New York, 1974.

2. R. Hamming, Coding and Information Theory, 2nd Edition, Prentice Hall, Upper Saddle River, N.J., 1986.

3. R. Hill, A First Course in Coding Theory, Oxford University Press, Oxford, 1990.

4. V. Pless, Introduction to the Theory of Error-Correcting Codes, 3rd Edi- tion, John Wiley & Sons, Hoboken, N.J., 1998.

5. S. Vanstone and P. van Oorschot, An Introduction to Error Correcting Codes with Applications, Springer, New York. 1989.

Exercises

1. Could the following bit strings have been received correctly if the last bit is a parity bit?

a) 1000011 b) 111111000 c) 10101010101 d) 110111011100

2. Find the Hamming distance between each of the following pairs of bit strings.

92 Applications of Discrete Mathematics

a) 00000,11111 b) 1010101,0011100 c) 000000001,111000000 d) 1111111111,0100100011

3. Suppose the bit string 01011 is sent using a binary symmetric channel where the probability a bit is received incorrectly is 0.01. What is the probability that

a) 01011, the bit string sent, is received? b) 11011 is received? c) 01101 is received? d) 10111 is received? e) no more than one error is present in the bit string received?

4. How many errors can each of the following binary codes detect and how many can it correct?

a) {0000000, 1111111} b) {00000, 00111, 10101, 11011} c) {00000000, 11111000, 01100111, 100101101}

5. Suppose that the probability of a bit error in transmission over a binary symmetric channel is 0.001. What is the probability that when a codeword with eight bits is sent from a code with minimum distance five, the bit string received is decoded as the codeword sent (when nearest neighbor decoding is used)?

�6. Show that if the minimum distance between codewords is four it is possible to correct an error in a single bit and to detect two bit errors without correction.

7. Use the sphere packing bound to give an upper bound on the number of codewords in a binary code where codewords are bit strings of length nine and the minimum distance between codewords is five.

8. Show that whenever n is an odd positive integer, the binary code consisting of the two bit strings of length n containing all 0s or all 1s is a perfect code.

9. Suppose that x and y are bit strings of length n and m is the number of positions where both x and y have 1s. Show that w(x+y) = w(x)+w(y)− 2m.

10. Find the parity check matrix associated with the code formed by adding a parity check bit to a bit string of length 4.

11. Find the parity check matrix associated with the triple repetition code for bit strings of length 3.

Chapter 5 Coding Theory 93

12. Suppose that the generator matrix for a binary code is

⎛ ⎜⎝

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

⎞ ⎟⎠ .

What is the parity check matrix H for this code?

13. Suppose that the parity check matrix for a binary code is⎛ ⎝ 1 0 1 0 01 1 0 1 0

0 1 0 0 1

⎞ ⎠ .

What is the generator matrix G for this code?

14. Find the 16 codewords in the Hamming code of order 3 described in Ex- ample 18.

�15. Sometimes, instead of errors, bits are erased during the transmission of a message or from a tape or other storage medium. The position, but not the value, of an erased bit is known. We say that a code C can correct r erasures if a message received with no errors and with no more than r erasures can be corrected to a unique codeword that agrees with the message received in all the positions that were not erased.

a) Show that a binary code of minimum distance d can correct d − 1 erasures.

b) Show that a binary code of minimum distance d can correct t errors and r erasures if d = 2t + r + 1.

Computer Projects

1. Given a binary code, determine the number of errors that it can detect and the number of errors that it can correct.

2. Given a binary code with minimum distance k, where k is a positive integer, write a program that will detect errors in codewords in as many as k − 1 positions and correct errors in as many as �(k − 1)/2� positions.