Agnes Scott College

F. J. MacWilliams and N. J. A. Sloane

The Theory of Error-Correcting Codes
North-Holland Mathematical Library, Volume 16, 1977 (11th reprint, 2003)

Theory of Error-Correcting Codes

Preface

Coding theory began in the late 1940's with the work of Golay, Hamming and Shannon. Although it has its origins in an engineering problem, the subject has developed by using more and more sophisticated mathematical techniques. It is our goal to present the theory of error-correcting codes in a simple, easily understandable manner, and yet also to cover all the important aspects of the subject. Thus the reader will find both the simpler families of codes – for example, Hamming, BCH, cyclic and Reed-Muller codes – discussed in some detail, together with encoding and decoding methods, as well as more advanced topics such as quadratic residue, Golay, Goppa, alternant, Kerdock, Preparata, and self-dual codes and association schemes.

Our treatment of bounds on the size of a code is similarly thorough. We discuss both the simpler results – the sphere-packing, Plotkin, Elias and Gaschamov bounds – as well as the very powerful linear programming method and the McEliece-Rodemich-Rumsey-Welch bound. Therefore this book can be used both by the beginner and by the expert, as an introductory textbook and as a reference book, and both by the engineer and the mathematician. Of course, this has not resulted in a thin book, and so we suggest the following menus:

[Sequence of chapters for an elementary first course on coding theory for mathematicians, a second course for mathematicians, an elementary first course on coding theory for engineers, and a second course for engineers.]

[List of principal codes discussed, encoding methods given, and decoding methods given.]

When reading the book, keep in mind this piece of advice, which should be given in every preface: if you get stuck on a section, skip it, but keep reading! Don't hesitate to skip the proof of a theorem: we often do. Starred sections are difficult or dull, and can be omitted on the first (or even second) reading.

The book ends with an extensive bibliography. Because coding theory overlaps with so many other subjects (computers, digital systems, group theory, number theory, the design of experiments, etc.) relevant papers may be found almost anywhere in the scientific literature. Unfortunately this means that the usual indexing and reviewing journals are not always helpful. We have therefore felt an obligation to give a fairly comprehensive bibliography. The notes at the ends of the chapters give sources for the theorems, problems and tables, as well as small bibliographies for some of the topics covered (or not covered) in the chapter.

Only block codes for correcting random errors are discussed; we say little about codes for correcting other kinds of errors (burst or transpositions) or about variable length codes, convolutional codes or source codes (see the Notes to Ch. 1). Furthermore we have often considered only binary codes, which makes the theory a lot simpler. Most writers take the opposite point of view; they think in binary but publish their results over arbitrary fields.

[List of omitted topics.]

Table of Content
  1. Linear Codes
  2. Nonlinear Codes, Hadamard Matrices, Designs and the Golay Code
  3. An Introduction to BCH Codes and Finite Fields
  4. Finite Fields
  5. Dual Codes and Their Weight Distribution
  6. Codes, Designs and Perfect Codes
  7. Cyclic Codes
  8. Cyclic Codes: Idempotents and Mattson-Solomon Polynomials
  9. BCH Codes
  10. Reed-Solomon and Justesen Codes
  11. MDS Codes
  12. Alternant, Goppa and Other Generalized BCH Codes
  13. Reed-Muller Codes
  14. First-Order Reed-Muller Codes
  15. Second-Order Reed-Muller, Kerdock and Preparata Codes
  16. Quadratic-Residue Codes
  17. Bounds on the Size of a Code
  18. Methods for Combining Codes
  19. Self-dual Codes and Invariant Theory
  20. The Golay Codes
  21. Association Schemes
    Appendix A: Tables of the Best Codes Known
    Appendix B: Finite Geometries
    Bibliography
    Index