Polynomial Algebra for Error Correction in Transmission of Binary Data (UMAP)

Error-correcting methods are used when some binary message digits (bits, with values 0 or 1) switch value during transmission. To enable correction of errors, extra check digits are sent with the message digits, expanding the message word to a longer codeword. Polynomial algebra can be applied to do the encoding, error correction, and decoding by associating with a binary sequence a polynomial whose coefficients are the elements of the sequence. These binary coefficients obey modulo-2 arithmetic, in which 1 + 1 = 0. Encoding is effected by multiplying message polynomials by a generator polynomial to obtain code polynomials of higher degree; error correction uses properties of finite fields and the code generator polynomial to find and correct errors. The polynomials form a finite field under multiplication modulo a primitive polynomial, analogous to integer arithmetic modulo a prime number; the modulo product is the remainder of the division of the ordinary product by the primitive polynomial. A consequence is that all products are of smaller degree than the primitive polynomial.

Table of Contents:

INTRODUCTION

BASIC IDEAS

BINARY POLYNOMIALS AND BINARY VECTORS

MODULO ARITHMETIC FOR INTEGERS

FIELDS

MODULO-2 ARITHMETIC FOR BINARY COEFFICIENTS

ARITHMETIC FOR BINARY POLYNOMIALS

MODULO MULTIPLICATION FOR POLYNOMIALS

FINITE FIELDS OR GALOIS FIELDS

GENERATION OF A GALOIS FIELD BY A PRIMITVE ELEMENT

A BRIEF REFLECTION ON POLYNOMIAL ALGEBRA

EXAMPLES OF FINITE BINARY POLYNOMIAL FIELDS
GF(2^1)
GF(2^2)
GF(2^3)
GF(2^4)

APPLICATION OF POLYNOMIAL ALGEBRA TO ERROR CORRECTION

BCH CODES

ERROR CORRECTION WITH BCH CODES

CONCLUSION

REFERENCES

ABOUT THE AUTHOR