Basic Concepts of Error Correction in Transmission of Binary Data (UMAP)

Error correction is used in technology such as CD players, cell phone communication, satellite links, computers, and networks to correct errors that occur when data are transmitted from one device to another. In this article, some of the ideas of error correction are explained, from the level of understanding of a physicist who wrote an error-correcting computer program as part of a project to develop a reader of a dot code (a two-dimensional version of a bar code). The brief was to research the theory and write a working program, as a user of mathematics rather than as a mathematician. This is the first, and least mathematical, of three papers on error correction that attempt to explain aspects of error correction from first principles. The second paper treats polynomial algebra, or-to be more precise-the algebra of finite fields of polynomials. The third describes a class of codes known as BCH codes after their discoverers, Bose and Chaudhuri [1960a; 1960b] and Hocquenghem [1959]; these codes are employed in dot codes. The error-correcting methods considered in these papers are block codes, in which data are transmitted as binary sequences of fixed length. The theory of error correction is treated in a number of good texts, such as Lin [1970], Lin and Costello [1983], Pless [1998], Pretzel [1996], and Rhee [1989]. The mathematical ideas are elegant and powerful, and the algebraic structures are remarkable. This article introduces ideas and terminology of error correction for binary data, the use of check digits, the idea of embedding, and the construction of error-correcting codes. We give several examples to illustrate these ideas, including "watchtowers with flashing lights," and transmission of a single bit. We introduce briefly at the end the algebra of binary polynomials and modulo arithmetic. No advanced mathematical background is necessary to understand these basic concepts. The reader should gain from this article an appreciation of the principles of error correction, though the methods used in practice (for multidigit sequences of binary digits) require mathematics that is not treated here.

Table of Contents:

INTRODUCTION

CORRECTION/DETECTION VIA CHECK BITS
Detection of a Single Error
Correction of a Single Error

THE IDEA OF EMBEDDING

CODES FOR SINGLE-BIT MESSAGES

GRAPHICAL ILLUSTRATIONS AND BINARY VECTORS

CODES FOR MULTIDIGIT WORDS

ENCODING WITH A GENERATOR: THE NEED FOR AN ALGEBRA

FINITE SETS OF BINARY POLYNOMIALS

SUMMARY

REFERENCES

ABOUT THE AUTHOR