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).
Contents
Definition
Fix a finite field
Fix integers
Example
Consider the polynomial code over
Or written explicitly:
Since the polynomial code is defined over the Binary Galois Field
Equivalently, expressed as strings of binary digits, the codewords are:
Note that 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
In a polynomial code over
Some authors, such as (Lidl & Pilz, 1999), only discuss the mapping
Instead, the following method is often used to create a systematic code: given a data word
where
Note the following properties:
-
p ( x ) = g ( x ) ⋅ q ( x ) , which is divisible byg ( x ) . In particular,p ( x ) is a valid code word. - Since
r ( x ) is of degree less thanm , the leftmostn − m symbols ofp ( x ) agree with the corresponding symbols ofx m d ( x ) . In other words, the firstn − m symbols of the code word are the same as the original data word. The remainingm symbols are called checksum digits or check bits.
Example
For the above code with
Decoding
An erroneous message can be detected in a straightforward way through polynomial division by the generator polynomial resulting in a non-zero remainder.
Assuming that the code word is free of errors, a systematic code can be decoded simply by stripping away the
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:
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.