“Polynomial code”的意思、由来-开放百科全书

词条

Polynomial code

释义

Definition
Example
Encoding
Example
Decoding
Properties of polynomial codes
Specific families of polynomial codes
References

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

Example

Consider the polynomial code over with , , and generator polynomial . This code consists of the following code words:

Or written explicitly:

Since the polynomial code is defined over the Binary Galois Field , polynomial elements are represented as a modulo-2 sum and the final polynomials are:

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

Encoding

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 are the same number of possible code words.

Plain (unencoded) data words should therefore be of length

Some authors, such as (Lidl & Pilz, 1999), only discuss 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 to create a systematic code: 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 called checksum digits or check bits.

Example

For the above code with , , and generator polynomial , 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

An erroneous message can be detected in a straightforward way through polynomial division by the generator polynomial resulting in a non-zero remainder.

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

If there are errors, then error correction should be performed before decoding. Efficient decoding algorithms exist for specific polynomial codes, such as BCH codes.

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. In the example above, the minimum Hamming distance is 2, since 01001 is a codeword, and there is no nonzero codeword with only one bit set.

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

Cyclic codes – every cyclic code is also a polynomial code; a popular example is the CRC code.
BCH codes – a family of cyclic codes with high Hamming distance and efficient algebraic error correction algorithms.
Reed–Solomon codes – an important subset of BCH codes with particularly efficient structure.

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.

1 : Coding theory

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。