《The Theory of Error-Correcting Codes》

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

1. Introduction370

2. Boolean functions370

3. Reed-Muller Codes373

4. RM codes and geometries377

5. The minimum weight vectors generate the code381

6. Encoding and decoding (Ⅰ)385

7. Encoding and decoding (Ⅱ)388

8. Other geometrical codes397

9. Automorphism groups of the RM codes398

10. Mattson-Solomon polynomials of RM codes401

11. The action of the general affine group on Mattson-Solomon polynomials402

Notes on Chapter 13403

Chapter 14. First-order Reed-Muller codes406

1. Introduction406

2. Pseudo-noise sequences406

3. Cosets of the first-order Reed-Muller code412

4. Encoding and decoding R(1, m)419

5. Bent functions426

Notes on Chapter 14431

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

1. Introduction433

2. Weight distribution of second-order Reed-Muller codes434

3. Weight distribution of arbitrary Reed-Muller codes445

4. Subcodes of dimension 2m of R(2, m) and R(2, m)448

5. The Kerdock code and generalizations453

6. The Preparata code466

7. Goethals' generalization of the Preparata codes476

Notes on Chapter 15477

Chapter 16. Quadratic-residue codes480

1. Introduction480

2. Definition of quadratic-residue codes481

3. Idempotents of quadratic-residue codes484

4. Extended quadratic-residue codes488

5. The automorphism group of QR codes491

6. Binary quadratic residue codes494

7. Double circulant and quasi-cyclic codes505

8. Quadratic-residue and symmetry codes over GF(3)510

9. Decoding of cyclic codes and others512

Notes on Chapter 16518

Chapter 17. Bounds on the size of a code523

1. Introduction523

2. Bounds on A(n, d,w)524

3. Bounds on A(n, d)531

4. Linear programming bounds535

5. The Griesmer bound546

6. Constructing linear codes; anticodes547

7. Asymptotic bounds556

Notes on Chapter 17566

Chapter 18. Methods for combining codes567

1. Introduction567

Part Ⅰ: Product codes and generalizations568

2. Direct product codes568

3. Not all cyclic codes are direct products of cyclic codes571

4. Another way of factoring irreducible cyclic codes573

5. Concatenated codes: the construction575

6. A general decomposition for cyclic codes578

Part Ⅱ: Other methods of combining codes581

7. Methods which increase the length581

7.1 Construction X: adding tails to the codewords581

7.2 Construction X4: combining four codes584

7.3 Single- and double-error-correcting codes586

7.4 The |a + x|b + x|a + b+x construction587

7.5 Piret's construction588

8. Constructions related to concatenated codes589

8.1 A method for improving concatenated codes589

8.2 Zinov'ev's generalized concatenated codes590

9. Methods for shortening a code592

9.1 Constructions Y1-Y4592

9.2 A construction of Helgert and Stinaff593

Notes on Chapter 18594

Chapter 19. Self-dual codes and invariant theory596

1. Introduction596

2. An introduction to invariant theory598

3. The basic theorems of invariant theory607

4. Generalizations of Gleason's theorems617

5. The nonexistence of certain very good codes624

6. Good self-dual codes exist629

Notes on Chapter 19633

Chapter 20. The Golay codes634

1. Introduction634

2. The Mathieu group M24636

3. M24 is five-fold transitive637

4. The order of M24 is 24.23.22.21.20.48638

5. The Steiner system S(5,8,24) is unique641

6. The Golay codes g23 and g24 are unique646

7. The automorphism groups of the ternary Golay codes647

8. The Golay codes g11 and g12 are unique648

Notes on Chapter 20649

Chapter 21. Association schemes651

1. Introduction651

2. Association schemes651

3. The Hamming association scheme656

4. Metric schemes659

5. Symplectic forms661

6. The Johnson scheme665

7. Subsets of association schemes666

8. Subsets of symplectic forms667

9. f-designs and orthogonal arrays670

Notes on Chapter 21671

Appendix A. Tables of the best codes known673

1. Introduction673

2. Figure 1, a small table of A(n,d)683

3. Figure 2, an extended table of the best codes known690

4. Figure 3, a table of A(n, d,w)691

Appendix B. Finite geometries692

1. Introduction692

2. Finite geometries, PG(w, q) and EG(m, q)692

3. Properties of PG(w,q) and EG(m,q)697

4. Projective and affine planes701

Notes on Appendix B702

Bibliography703

Index757