Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Polynomial code
Résumé
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).
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 .
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:
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).
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.