Polynomial code


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} + cdots + a_1x + a_0.,

Fix integers m leq n and let g(x) be some fixed polynomial of degree m, 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, m=2, and generator 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 m, 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 is 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), 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 often used: 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 sometimes called the "checksum digits".

Example

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 mapsto 00000
* 001 mapsto 00111
* 010 mapsto 01001
* 011 mapsto 01110
* 100 mapsto 10010
* 101 mapsto 10101
* 110 mapsto 11011
* 111 mapsto 11100

Decoding

Assuming that the code word is free of errors, it can be decoded simply by stripping away the m checksum digits.

If there are errors, then error correction should be performed before decoding.

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.

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 is cyclic if and only if the generator polynomial divides x^n-1.
* If the generator polynomial is primitive, then the resulting code has Hamming distance at least 3, provided that nleq 2^m-1.
* In BCH 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 for BCH codes.

Specific families of polynomial codes

* BCH codes are a family of polynomial codes with high Hamming distance and efficient algebraic error correction algorithms.

References

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


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Code RSA — Rivest Shamir Adleman Pour les articles homonymes, voir RSA. Rivest Shamir Adleman ou RSA est un algorithme asymétrique de cryptographie à clé publique, très utilisé dans le commerce électronique, et plus généralement pour échanger des données… …   Wikipédia en Français

  • BCH code — In coding theory the BCH codes form a class of parameterised error correcting codes which have been the subject of much academic attention in the last fifty years. BCH codes were invented in 1959 by Hocquenghem, and independently in 1960 by Bose… …   Wikipedia

  • Cyclic code — In coding theory, cyclic codes are linear block error correcting codes that have convenient algebraic structures for efficient error detection and correction. Contents 1 Definition 2 Algebraic structure 3 Examples …   Wikipedia

  • Chromatic polynomial — All nonisomorphic graphs on 3 vertices and their chromatic polynomials, clockwise from the top. The independent 3 set: k3. An edge and a single vertex: k2(k − 1). The 3 path: k(k − 1)2. The 3 clique …   Wikipedia

  • Group code recording — In computer science, group code recording (GCR) refers to several distinct but related encoding methods for magnetic media. The first, used in 6250 cpi magnetic tape, is an error correcting code combined with a run length limited encoding scheme …   Wikipedia

  • Linear code — In mathematics and information theory, a linear code is an important type of block code used in error correction and detection schemes. Linear codes allow for more efficient encoding and decoding algorithms than other codes (cf. syndrome… …   Wikipedia

  • Concatenated error correction code — In coding theory, concatenated codes form a class of error correcting codes that are derived by combining an inner code and an outer code. They were conceived in 1966 by Dave Forney as a solution to the problem of finding a code that has both… …   Wikipedia

  • Erasure code — In information theory, an erasure code is a forward error correction (FEC) code for the binary erasure channel, which transforms a message of k symbols into a longer message (code word) with n symbols such that the original message can be… …   Wikipedia

  • Tutte polynomial — This article is about the Tutte polynomial of a graph. For the Tutte polynomial of a matroid, see Matroid. The polynomial x4 + x3 + x2y is the Tutte polynomial of the Bull graph. The red line shows the intersection with the plane …   Wikipedia

  • Enumerator polynomial — In coding theory, the weight enumerator polynomial of a binary linear code specifies the number of words of each possible Hamming weight. Let be a binary linear code length n. The weight distribution is the sequence of numbers giving the number… …   Wikipedia