Polynomial code

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).

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). Consider the polynomial code over GF(2)=\{0,1\} with n=5 , m=2 , and generator polynomial g(x)=x^2+x+1 . This code consists of the following code words: 0\cdot g(x),\quad 1\cdot g(x),\quad x\cdot g(x), \quad (x+1) \cdot g(x), x^2 \cdot g(x),\quad (x^2+1)\cdot g(x),\quad (x^2+x)\cdot g(x), \quad (x^2+x+1) \cdot g(x). Or written explicitly: 0,\quad x^2+x+1,\quad x^3+x^2+x,\quad x^3+2x^2+2x+1, x^4+x^3+x^2,\quad x^4+x^3+2x^2+x+1,\quad x^4+2x^3+2x^2+x,\quad x^4+2x^3+3x^2+2x+1. Since the polynomial code is defined over the Binary Galois Field GF(2)=\{0,1\} , polynomial elements are represented as a modulo-2 sum and the final polynomials are: 0,\quad x^2+x+1,\quad x^3+x^2+x,\quad x^3+1, x^4+x^3+x^2,\quad x^4+x^3+x+1,\quad x^4+x,\quad x^4+x^2+1. Equivalently, expressed as strings of binary digits, the codewords are: 00000,\quad 00111,\quad 01110,\quad 01001, 11100,\quad 11011,\quad 10010,\quad 10101. 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). there will be exactly q^{n-m} code words. Indeed, by definition, p(x) is a code word if and only if it is of the form p(x) = g(x)\cdot q(x) , where q(x) (the quotient) is of degree less than n-m . Since there are q^{n-m} such quotients available, there are the same number of possible code words. Plain (unencoded) data words should therefore be of length n-m Some authors, such as (Lidl & Pilz, 1999), only discuss the mapping q(x) \mapsto g(x)\cdot q(x) 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: given a data word d(x) of length n-m , first multiply d(x) by x^m , which has the effect of shifting d(x) by m places to the left. In general, x^md(x) will not be divisible by g(x) , i.e., it will not be a valid code word. However, there is a unique code word that can be obtained by adjusting the rightmost m symbols of x^md(x) . To calculate it, compute the remainder of dividing x^md(x) by g(x) : x^md(x) = g(x)\cdot q(x) + r(x),\, where r(x) is of degree less than m . The code word corresponding to the data word d(x) is then defined to be p(x) := x^md(x) - r(x),\, Note the following properties: p(x) = g(x)\cdot q(x) , which is divisible by g(x) . In particular, p(x) is a valid code word. Since r(x) is of degree less than m , the leftmost n-m symbols of p(x) agree with the corresponding symbols of x^md(x) . In other words, the first n-m symbols of the code word are the same as the original data word. The remaining m symbols are called checksum digits or check bits. For the above code with n=5 , m=2 , and generator polynomial g(x)=x^2+x+1 , 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

Text derived from https://en.wikipedia.org/w/index.php?oldid=1362628414 under CC BY-SA 4.0; modifications have been made.