Agnes Scott College

Vera Pless

Introduction to the Theory of Error-Correcting Codes
Wiley & Sons, Inc., (1982, 2nd Edition 1989, 3rd Edition 1998)

Pless Cover

Preface

This book arose out of a two-quarter sequence in error-correcting codes that I taught at the University of Illinois Circle Campus. It is intended for undergraduates and graduate students in mathematics, computer science, or electrical engineering. The only requirement is an elementary course in linear algebra. An appendix, which covers some of the linear algebra needed, is provided to supplement such a course. A modern algebra course is not necessary but would probably be helpful. if the algebra course is taken concurrently with the coding course, the latter could provide motivation and many concrete examples. Instructors can determine the pace at which to proceed by the mathematical backgrounds of their students.

The theory of error-correcting codes started as a subject in electrical engineering with Shannon's classic papers in 1948. It has since become a fascinating mathematical topic, and part of the fascination has been the use of many varied mathematical tools to solve the practical problems in coding. This book attempts to demonstrate this process. Understanding how one might go about finding mathematical techniques to solve applied problems is useful to students who might sometime encounter such problems. Because the subject is relatively new, there are many open problem sin coding. Some of these are mentioned in this book. Whenever possible, the most elementary proofs or approaches are used.

Since the first edition was written, practical uses of error-correcting codes have proliferated. In addition to many uses in communication systems, error-correcting codes are widely used in modern memory devices, have many uses in computer systems, and also provide the high fidelity on many compact disc players. Although the technology is changing rapidly, the fundamental principles of coding remain the same.

Contents

  1. Introductory Concepts
    1. Introduction
    2. Basic Definitions
    3. Weight, Minimum Weight, and Maximum-Likelihood Decoding
  2. Useful Background
    1. Syndrome Decoding
    2. Perfect Codes, Hamming Codes, Sphere-Packing Bound
    3. Packing Radius, Covering Radius, MDS Codes, and Some Bounds
    4. Self-Dual Codes, Golay Codes
    5. Reed-Muller Codes
    6. Puncturing, Extending, and Shortening
  3. A Double-Error-Correcting BCH Code and a Finite Field of 16 Elements
    1. The Problem
    2. Polynomials
    3. A Finite Field of 16 Elements
    4. Double-Error-Correcting Bose-Chaudhuri-Hocquenghem (BCH) Code
  4. Finite Fields
    1. Groups
    2. Structure of a Finite Field
    3. Minimal Polynomials
    4. Factoring xn – 1
  5. Cyclic Codes
    1. Origin and Definition of Cyclic Codes
    2. How to Find Cyclic Codes: The Generator Polynomial
    3. Generator Polynomial of the Dual Code
    4. Idempotents and Minimal Ideals for Binary Cyclic Codes
  6. Group of a Code and Quadratic Residue (QR) Codes
    1. Some Cyclic Codes We Know
    2. Permutation Groups
    3. Group of a Code
    4. Definition of Quadratic Residue (QR) Codes
    5. Extended QR Codes, Square Root Bound, and Groups of QR Codes
    6. Permutation Decoding
    7. Decoding the Golay Code
  7. Bose-Chaudhuri-Hocquenghem (BCH) Codes
    1. Cyclic Codes Given in Terms of Roots
    2. Vandermonde Determinants
    3. Definition and Properties of BCH Codes
    4. Reed-Solomon Codes
    5. More on the Minimum Distance
    6. Decoding BCH Codes
  8. Weight Distributions
    1. Preliminary Concepts and a Theorem on Weights in Homogeneous Codes
    2. MacWilliams Equations
    3. Pless Power Moments
    4. Gleason Polynomials
  9. Designs and Games
    1. Designs
    2. Designs and Codes
    3. Assmus-Mattson Theorem and a Design-Decoding Scheme
    4. Symmetry Codes
    5. Games
    6. Games and Codes
    7. Greedy Codes
  10. Some Codes are Unique
    1. The Hamming Code and the Ternary Golay Code are Unique
    2. The Steiner System S(5,8,24) Is Unique and So is a Binary [24,12,8] Code
    3. "Glue"
    4. Residual Codes and the Griesmer Bound
    5. Some Nonlinear Codes
    6. Z4 Codes and Their Gray Images