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

Definition

Fix a finite field $GF(q)$, whose elements we call symbols. For the purposes of constructing polynomial codes, we identify a string of $n$ symbols $a_{n-1}\ldots a_{0}$ with the polynomial

$a_{n-1}x^{n-1}+\ldots +a_{1}x+a_{0}$.

Fix integers $k\leq n$ and let $g(x)$ be some fixed polynomial of degree $k$, called the generator polynomial. The polynomial code generated by $g(x)$ is the code whose code words are precisely the polynomials of degree less than $n$ that are divisible (without remainder) by $g(x)$.

Example

Consider the polynomial code over $GF(2)=\{0,1\}$ with $n=5$, $k=2$, and generating polynomial $g(x)=x^{2}+x+1$. This code consists of the following code words:

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

Note that this, as every polynomial code, is indeed a linear code, i.e., linear combinations of code words are again code words.

Encoding

In a polynomial code over $GF(q)$ with code length $n$ and generator polynomial $g(x)$ of degree $k$, there will be exactly $q^{n-k}$ 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-k$. Since there are $q^{n-k}$ such quotients available, there is the same number of possible code words. Plain (unencoded) data words should therefore be of length $n-k$

It is tempting to use 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 used: given a data word $m(x)$ of length $n-k$, first multiply $m(x)$ by $x^{k}$, which has the effect of shifting $m(x)$ by $k$ places to the left. In general, $x^{k}m(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 $k$ symbols of $x^{k}m(x)$. To calculate it, compute the remainder of dividing $x^{k}m(x)$ by $g(x)$:

$x^{k}m(x)=g(x)\cdot q(x)+r(x)$,

where $r(x)$ is of degree less than $k$. The code word corresponding to the data word $m(x)$ is then defined to be

$p(x):=x^{k}m(x)-r(x)$.

Note the following properties:

1. $p(x)=g(x)\cdot q(x)$, which is divisible by $g(x)$. In particular, $p(x)$ is a valid code word.
2. Since $r(x)$ is of degree less than $k$, the leftmost $n-k$ symbols of $p(x)$ agree with the corresponding symbols of $x^{k}m(x)$. In other words, the first $n-k$ symbols of the code word are the same as the original data word. The remaining $k$ symbols are sometimes called the check digits.

Example

For the above code with $n=5$, $k=2$, and generating polynomial $g(x)=x^{2}+x+1$, we obtain the following assignment from data words to codewords:

To be continued...

Reference

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