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

Formal 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 $\langle a_{n-1},\ldots ,a_{0}\rangle$ 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-1$. 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 by $g(x)$. The polynomial $g(x)$ is called the generator polynomial of the code.

Example

Consider $GF(2)=\{0,1\}$. Let $n=5$, $k=3$, and $g(x)=x^{2}+x+1$. The polynomial code generated by $g(x)$ 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

By definition, a polynomial $p(x)$ of degree less than $n$ is divisible by the generator polynomial $g(x)$ of degree $k-1$ if and only if there exists a polynomial $q(x)$ (the quotient) of degree $n-k$ such that $p(x)=g(x)\cdot q(x)$.

To be continued...

Reference

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