《Introduction to the theory of error-correcting codes Part I》

Chapter 1.Linear codes1

1.Linear codes1

2.Properties of a linear code5

3.At the receiving end7

4.More about decoding a linear code15

5.Error probability18

6.Shannon’s theorem on the existence of good codes22

7.Hamming codes23

8.The dual code26

9.Construction of new codes from old （Ⅱ）27

10.Some general properties of a linear code32

11.Summary of Chapter 134

Notes on Chapter 134

Chapter 2.Nonlinear codes， Hadamard matrices， designs and the Golay code38

1.Nonlinear codes38

2.The Plotkin bound41

3.Hadamard matrices and Hadamard codes44

4.Conferences matrices55

5.t-designs58

6.An introduction to the binary Golay code64

7.The Steiner system S（5， 6， 12）， and nonlinear single-error cor-recting codes70

8.An introduction to the Nordstrom-Robinson code73

9.Construction of new codes from old （Ⅲ）76

Notes on Chapter 278

Chapter 3.An introduction to BCH codes and finite fields80

1.Double-error-correcting BCH codes （Ⅰ）80

2.Construction of the field GF（16）82

3.Double-error-correcting BCH codes （Ⅱ）86

4.Computing in a finite field88

Notes on Chapter 392

Chapter 4.Finite fields93

1.Introduction93

2.Finite fields： the basic theory95

3.Minimal polynomials99

4.How to find irreducible polynomials107

5.Tables of small fields109

6.The automorphism group of GF（pm）112

7.The number of irreducible polynomials114

8.Bases of GF（pm） over GF（p）115

9.Linearized polynomials and normal bases118

Notes on Chapter 4124

Chapter 5.Dual codes and their weight distribution125

1.Introduction125

2.Weight distribution of the dual of a binary linear code125

3.The group algebra132

4.Characters134

5.MacWilliams theorem for nonlinear codes135

6.Generalized MacWilliams theorems for linear codes141

7.Properties of Krawtchouk polynomials150

Notes on Chapter 5153

Chapter 6.Codes， designs and perfect codes155

1.Introduction155

2.Four fundamental parameters of a code156

3.An explicit formula for the weight and distance distribution158

4.Designs from codes when s ≤ d’160

5.The dual code also gives designs164

6.Weight distribution of translates of a code166

7.Designs from nonlinear codes when s’< d174

8.Perfect codes175

9.Codes over GF（q）176

10.There are no more perfect codes179

Notes on Chapter 6186

Chapter 7.Cyclic codes188

1.Introduction188

2.Definition of a cyclic code188

3.Generator polynomial190

4.The check polynomial194

5.Factors of xn - 1196

6.t-error-correcting BCH codes201

7.Using a matrix over GF（qn） to define a code over GF（q）207

8.Encoding cyclic codes209

Notes on Chapter 7214

Chapter 8.Cyclic codes （contd.）： Idempotents and Mattson-Solomon polynomials216

1.Introduction216

2.Idempotents217

3.Minimal ideals， irreducible codes， and primitive idempotents219

4.Weight distribution of minimal codes227

5.The automorphism group of a code229

6.The Mattson-Solomon polynomial239

7.Some weight distributions251

Notes on Chapter 8255

Chapter 9.BCH codes257

1.Introduction257

2.The true minimum distance of a BCH code259

3.The number of information symbols in BCH codes262

4.A table of BCH codes266

5.Long BCH codes are bad269

6.Decoding BCH codes270

7.Quadratic equations over GF（2m）277

8.Double-error-correcting BCH codes are quasi-perfect279

9.The Carlitz-Uchiyama bound280

10.Some weight distributions are asymptotically normal282

Notes on Chapter 9291

Chapter 10.Reed-Solomon and Justesen codes294

1.Introduction294

2.Reed-Solomon codes294

3.Extended RS codes296

4.Idempotents of RS codes296

5.Mapping GF（2m） codes into binary codes298

6.Burst error correction301

7.Encoding Reed-Solomon codes301

8.Generalized Reed-Solomon codes303

9.Redundant residue codes305

10.Decoding RS codes306

11.Justesen codes and concatenated codes306

Notes on Chapter 10315

Chapter 11.MDS codes317

1.Introduction317

2.Generator and parity check matrices318

3.The weight distribution of an MDS code319

4.Matrices with every square submatrix nonsingular321

5.MDS codes from RS codes323

6.n-arcs326

7.The kncwn results327

8.Orthogonal arrays328

Notes on Chapter 11329

Chapter 12.Alternant， Goppa and other generalized BCH codes332

1.Introduction332

2.Alternant codes333

3.Goppa codes338

4.Further properties of Goppa codes346

5.Extended double-error-correcting Goppa codes are cyclic350

6.Generalized Srivastava codes357

7.Chien-Choy generalized BCH codes360

8.The Euclidean algorithm362

9.Decoding alternant codes365

Notes on Chapter 12368

Chapter 13.Reed-Muller codes370

Chapter 14.First-order Reed-Muller codes406

Chapter 15.Second-order Reed-Muller， Kerdock and Preparata codes433

Chapter 16.Quadratic-residue codes480

Chapter 17.Bounds on the size of a code523

Chapter 18.Methods for combining codes567

Chapter 19.Self-dual codes and invariant theory596

Chapter 20.The Golay codes634

Chapter 21.Association schemes651

Appendix A.Tables of the best codes known673

Appendix B.Finite geometries692

Bibliography703

Index757