In coding theory, a polynomial code is a type of linear code whose set of valid code words consists of those polynomials (usually of some fixed length) that are divisible by a given fixed polynomial (of shorter length, called the generator polynomial).

Definition

Fix a finite field, whose elements we call symbols with the polynomial

, called the generator polynomial. The that are divisible.

Example

. This code consists of the following code words:

Or written explicitly:

, polynomial elements are represented as a modulo-2 sum and the final polynomials are:

Equivalently, expressed as strings of binary digits, the codewords are:

This, as every polynomial code, is indeed a linear code, i.e., linear combinations of code words are again code words. In a case like this where the field is GF(2), linear combinations are found by taking the XOR of the codewords expressed in binary form (e.g. 00111 XOR 10010 = 10101).

Encoding

(the quotient

as the assignment from data words to code words. However, this has the disadvantage that the data word does not appear as part of the code word.

Instead, the following method is often used to create a systematic code:

is then defined to be

Note the following properties:

1. is a valid code word.

2. symbols are called checksum digits or check bits.

Example

, we obtain the following assignment from data words to codewords:

• 000 00000

• 001 00111

• 010 01001

• 011 01110

• 100 10010

• 101 10101

• 110 11011

• 111 11100

Decoding

An erroneous message can be detected in a straightforward way through polynomial division by the generator polynomial resulting in a non-zero remainder.

checksum digits.

If there are errors, then error correction should be performed before decoding. Efficient decoding algorithms exist for specific polynomial codes, such as BCH codes.

Properties of polynomial codes

As for all digital codes, the error detection and correction abilities of polynomial codes are determined by the minimum Hamming distance of the code. Since polynomial codes are linear codes, the minimum Hamming distance is equal to the minimum weight of any non-zero codeword. In the example above, the minimum Hamming distance is 2, since 01001 is a codeword, and there is no nonzero codeword with only one bit set.

More specific properties of a polynomial code often depend on particular algebraic properties of its generator polynomial. Here are some examples of such properties:

• A polynomial code is cyclic.

• If the generator polynomial is primitive.

• In BCH codes, the generator polynomial is chosen to have specific roots in an extension field, in a way that achieves high Hamming distance.

The algebraic nature of polynomial codes, with cleverly chosen generator polynomials, can also often be exploited to find efficient error correction algorithms. This is the case for BCH codes.

Specific families of polynomial codes

• Cyclic codes every cyclic code is also a polynomial code; a popular example is the CRC code.

• BCH codes a family of cyclic codes with high Hamming distance and efficient algebraic error correction algorithms.

• Reed–Solomon codes an important subset of BCH codes with particularly efficient structure.

References

• W.J. Gilbert and W.K. Nicholson: Modern Algebra with Applications, 2nd edition, Wiley, 2004.

• R. Lidl and G. Pilz. Applied Abstract Algebra, 2nd edition. Wiley, 1999.