Polynomial code
Incoding theory,apolynomial codeis a type oflinear codewhose set of validcode wordsconsists of thosepolynomials(usually of some fixed length) that aredivisibleby a given fixed polynomial (of shorter length, called thegenerator polynomial).
Definition
[edit]Fix afinite field,whose elements we callsymbols.For the purposes of constructing polynomial codes, we identify a string ofsymbolswith the polynomial
Fix integersand letbe some fixed polynomial of degree,called thegenerator polynomial.Thepolynomial code generated byis the code whose code words are precisely the polynomials of degree less thanthat aredivisible(without remainder) by.
Example
[edit]Consider the polynomial code overwith,,and generator polynomial.This code consists of the following code words:
Or written explicitly:
Since the polynomial code is defined over the Binary Galois Field,polynomial elements are represented as amodulo-2 sum and the final polynomials are:
Equivalently, expressed as strings of binary digits, the codewords are:
This, as every polynomial code, is indeed alinear 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
[edit]In a polynomial code overwith code lengthand generator polynomialof degree, there will be exactlycode words. Indeed, by definition,is a code word if and only if it is of the form,where(thequotient) is of degree less than.Since there aresuch quotients available, there are the same number of possible code words. Plain (unencoded) data words should therefore be of length
Some authors, such as (Lidl & Pilz, 1999), only discuss the mappingas 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 asystematic code:given a data wordof length,first multiplyby,which has the effect of shiftingbyplaces to the left. In general,will not be divisible by,i.e., it will not be a valid code word. However, there is a unique code word that can be obtained by adjusting the rightmostsymbols of. To calculate it, compute the remainder of dividingby:
whereis of degree less than.The code word corresponding to the data wordis then defined to be
Note the following properties:
- ,which is divisible by.In particular,is a valid code word.
- Sinceis of degree less than,the leftmostsymbols ofagree with the corresponding symbols of.In other words, the firstsymbols of the code word are the same as the original data word. The remainingsymbols are calledchecksum digitsorcheck bits.
Example
[edit]For the above code with,,and generator polynomial,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
[edit]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 thechecksum digits.
If there are errors, then error correction should be performed before decoding. Efficient decoding algorithms exist for specific polynomial codes, such asBCH codes.
Properties of polynomial codes
[edit]As for all digital codes, theerror detection and correctionabilities of polynomial codes are determined by the minimumHamming distanceof 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 iscyclicif and only if the generator polynomial divides.
- If the generator polynomial isprimitive,then the resulting code has Hamming distance at least 3, provided that.
- InBCH 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 forBCH codes.
Specific families of polynomial codes
[edit]- Cyclic codes– every cyclic code is also a polynomial code; a popular example is theCRCcode.
- 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
[edit]- 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.