- Polynomial code
coding theory, a polynomial code is a type of linear codewhose set of valid code wordsconsists of those polynomials(usually of some fixed length) that are divisible by a given fixed polynomial (of shorter length, called the "generator polynomial").
finite field, whose elements we call "symbols". For the purposes of constructing polynomial codes, we identify a string of symbols with the polynomial
Fix integers and let be some fixed polynomial of degree , called the "generator polynomial". The "polynomial code generated by " is the code whose code words are precisely the polynomials of degree less than that are divisible (without remainder) by .
Consider the polynomial code over with , , and generator polynomial . This code consists of the following code words:
Equivalently, expressed as strings of binary digits, the codewords are:
Note that this, as every polynomial code, is indeed a
linear code, i.e., linear combinations of code words are again code words.
In a polynomial code over with code length and generator polynomial of degree , there will be exactly code words. Indeed, by definition, is a code word if and only if it is of the form , where (the "quotient") is of degree less than . Since there are such quotients available, there is the same number of possible code words.Plain (unencoded) data words should therefore be of length
Some authors, such as (Lidl & Pilz, 1999), use the mapping 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 of length , first multiply by , which has the effect of shifting by places 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 rightmost symbols of .To calculate it, compute the remainder of dividing by :
where is of degree less than . The code word corresponding to the data word is then defined to be
Note the following properties:
# , which is divisible by . In particular, is a valid code word.
# Since is of degree less than , the leftmost symbols of agree with the corresponding symbols of . In other words, the first symbols of the code word are the same as the original data word. The remaining symbols are sometimes called the "checksum digits".
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
Assuming that the code word is free of errors, it can be decoded simply by stripping away the 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 correctionabilities of polynomial codes are determined by the minimum Hamming distanceof 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 .
* If the generator polynomial is primitive, then the resulting code has Hamming distance at least 3, provided that .
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
Specific families of polynomial codes
BCH codes are a family of polynomial codes with high Hamming distance and efficient algebraic error correction algorithms.
* 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