Error Correcting Codes: A Mathematical

Assuming little previous mathematical knowledge, Error Correcting Codes provides a sound introduction to key areas of the subject. Topics have been chosen for their importance and practical significance, which Baylis demonstrates in a rigorous but gentle mathematical style.Coverage includes optimal codes; linear and non-linear codes; general techniques of decoding errors and erasures; error detection; syndrome decoding, and much more. Error Correcting Codes contains not only straight maths, but also exercises on more investigational problem solving. Chapters on number theory and polynomial algebra are included to support linear codes and cyclic codes, and an extensive reminder of relevant topics in linear algebra is given.Exercises are placed within the main body of the text to encourage active participation by the reader, with comprehensive solutions provided.Error Correcting Codes will appeal to undergraduate students in pure and applied mathematical fields, software engineering, communications engineering, computer science and information technology, and to organizations with substantial research and development in those areas.

Preface

xi

1 Setting the scene

1

(10)

1.1 The problem

1

(1)

1.2 The channel -- cause of the problem

2

(1)

1.3 Cunning coding -- solution of the problem

3

(5)

1.4 Exercises for Chapter 1

8

(3)

2 Reducing the price

11

(14)

2.1 Hamming's solution

11

(2)

2.2 Can anything be done if two errors occur?

13

(2)

2.3 An alternative use of Hamming codes -- erasures

15

(1)

2.4 What really makes a code work? -- Hamming distance

16

(6)

2.5 Further reading

22

(1)

2.6 Exercises for Chapter 2

22

(3)

3 Number theory -- arithmetic for codes

25

(24)

3.1 Why number theory?

25

(1)

3.2 Congruence and related ideas

26

(5)

3.3 Solving linear congruences

31

(3)

3.4 A bit of arithmetic folklore

34

(1)

3.5 The special role of primes

35

(3)

3.6 A recreational interlude

38

(4)

3.7 Z(p) and reciprocals

42

(2)

3.8 Further reading

44

(1)

3.9 Exercises for Chapter 3

44

(5)

4 Block codes -- some constraints and some geometry

49

(24)

4.1 The main problem

49

(1)

4.2 Limitations on M

50

(7)

4.3 Equivalent codes

57

(3)

4.4 Distance isomorphic codes

60

(2)

4.5 Geometry and Hamming space

62

(3)

4.6 Perfect codes

65

(3)

4.7 The Plotkin bound

68

(2)

4.8 Exercises for Chapter 4

70

(3)

5 The power of linearity

73

(30)

5.1 The problem

73

(1)

5.2 Linear codes -- their fundamental properties

74

(2)

5.3 Linear algebra reminders

76

(2)

5.4 The generator matrix

78

(1)

5.5 Cosets and the Slepian array

79

(3)

5.6 The dual code and parity check matrix

82

(2)

5.7 Syndrome decoding

84

(5)

5.8 Equivalence of linear codes

89

(3)

5.9 Erasure correction and syndromes

92

(5)

5.10 Exercises for Chapter 5

97

(6)

6 The Hamming family and friends

103

(28)

6.1 Introduction

103

(1)

6.2 Hamming codes

103

(2)

6.3 Decoding Ham(r,q)

105

(1)

6.4 Simplex codes

105

(2)

6.5 Optimal linear codes

107

(7)

6.6 More on the structure of Hamming codes

114

(3)

6.7 The cyclic property of Hamming codes

117

(2)

6.8 Weight distributions

119

(8)

6.9 Exercises for Chapter 6

127

(4)

7 Polynomials for codes

131

(10)

7.1 The first definitions

131

(1)

7.2 Operations in F[X]

132

(2)

7.3 Factorization in Z(p)[X]

134

(2)

7.4 Congruence of polynomials

136

(1)

7.5 Rings and ideals

136

(2)

7.6 Exercises for Chapter 7

138

(3)

8 Cyclic codes

141

(20)

8.1 Introduction

141

(1)

8.2 The choice of modulus

141

(2)

8.3 Generator matrices and generator polynomials

143

(4)

8.4 Encoding by polynomials

147

(1)

8.5 Syndromes and polynomials

148

(2)

8.6 Parity checks and polynomials

150

(2)

8.7 Cyclic codes and double-adjacent errors

152

(1)

8.8 Cyclic golay codes

153

(5)

8.9 Exercises for Chapter 8

158

(3)

9 The Reed-Muller family of codes

161

(16)

9.1 New codes from old

161

(1)

9.2 Plotkin's construction

161

(2)

9.3 The Reed-Muller family

163

(3)

9.4 An alternative description of Reed-Muller codes

166

(6)

9.5 Hamming codes, first order Reed-Muller codes -- some connections

172

(3)

9.6 Exercises for Chapter 9

175

(2)

Appendix. A Solutions, answers, hints

177

(40)

References

217

(1)

Index

218

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

FREE SHIPPING

Rent More, Save More! Use code: BBRENTAL

5% off 1 book, 7% off 2 books, 10% off 3+ books

Error Correcting Codes: A Mathematical Introduction

Summary

Table of Contents

Supplemental Materials