BCH Codes for Error Correction in Transmission of Binary Data (UMAP)

When binary data are transmitted electronically, in telecommunications, computers, and CD players, errors may occur in the binary digits (bits). To correct them, extra check digits are sent along with the information digits, so message sequences are encoded to longer codeword sequences. Codewords with errors may be corrected to the original codeword for a small number of errors and then decoded to the original message sequence. BCH codes are a family of error-correcting codes discovered by Bose and Ray-Chaudhuri [1960a; 1960b] and independently by Hocquenghem [1959]. They constitute an extremely important application of the algebra of finite polynomial fields; for example, audio CD players use cross-interleaved Reed- Solomon (CIRC) [1960] codes, which are like BCH codes but with nonbinary coefficients. To apply a BCH code, a binary message sequence is treated as a list of coefficients of a polynomial; the coefficients are binary digits 0 and 1 under modulo 2 arithmetic. The polynomials form finite fields under modulo polynomial arithmetic. Encoding is done by multiplying message polynomials by a generator polynomial. A BCH code is linear and cyclic and prescribes a way of constructing the generator polynomial. In this article, we describe BCH codes for the case of binary polynomials but do not delve into Reed-Solomon codes and their polynomials with nonbinary coefficients. This is the third in a sequence of three articles on error correction, written from the point of view of a physicist who wrote an error-correcting program for an industrial application [Matthews 2000; 2001].

Table of Contents:

ABSTRACT

INTRODUCTION

BASIC CONCEPTS

ALGEBRA OF FINITE POLYNOMIAL FIELDS
Fields
Finite Fields
Fields of Binary Polynomials
Primitive Elements in a Field

INTRODUCTION TO BCH CODES

LINEAR CODES

CYCLIC CODES

THE GENERATOR POLYNOMIAL OF A LINEAR CYCLIC CODE

MINIMAL POLYNOMIALS

FACTORISATION OF x^n + 1

THE GENERATOR POLYNOMIAL OF A BCH CODE

ENCODING OF A CYCLIC CODE IN SYSTEMATIC FORM

DECODING OF BCH CODES
Correction of a Single Error
Correction of Two Errors

CONCLUSION

REFERENCES

ABOUT THE AUTHOR