Les codes cycliques sont caractérisés par le fait que lorsque tous les symboles d'une combinaison de codes d'un code donné sont réorganisés de manière cyclique, une autre combinaison de codes du même code est formée.

Combinaison de codes cyclique ;

Également une combinaison de code cyclique.

Lorsqu'on considère les codes cycliques, les nombres binaires sont représentés comme un polynôme dont le degré ( P- 1), P.- longueur de la combinaison de codes.

Par exemple, la combinaison 1001111 ( m= 7) sera représenté par un polynôme

Avec cette représentation, les actions sur les combinaisons de codes se réduisent à des actions sur les polynômes. Ces opérations sont effectuées conformément à l'algèbre ordinaire, sauf que la réduction des termes similaires est effectuée modulo 2.

La détection des erreurs à l'aide d'un code cyclique est assurée par le fait que les combinaisons autorisées sont celles qui sont divisibles sans reste par un polynôme présélectionné. g(X). Si la combinaison reçue contient des symboles tronqués, alors division par le polynôme g(X) est réalisé avec le reste. Cela génère un signal indiquant une erreur. Polynôme G(X)appelé générateur.

La construction de combinaisons de codes cycliques est possible en multipliant la combinaison originale UN(X) en un polynôme générateur g(X)avec la réduction des termes similaires modulo 2 :

• si la puissance la plus élevée du produit ne dépasse pas ( P- 1), alors le polynôme résultant représentera la combinaison de codes du code cyclique ;
• si la puissance la plus élevée du produit est supérieure ou égale à P., alors le polynôme produit est divisé par un polynôme présélectionné de degré P. et le résultat de la multiplication est le reste résultant de la division.

Ainsi, tous les polynômes représentant des combinaisons du code cyclique auront un degré inférieur à P..

Souvent, le polynôme par lequel la division est effectuée est considéré comme un polynôme g(X)= +1. Avec cette formation de combinaisons de codes, les positions des symboles d'information et de contrôle ne peuvent pas être déterminées à l'avance.

Le grand avantage des codes cycliques réside dans la facilité de construction de dispositifs de codage et de décodage qui, dans leur structure, représentent des registres à décalage avec rétroaction.

Le nombre de bits de registre est choisi égal au degré du polynôme générateur.

La rétroaction est effectuée depuis la sortie du registre vers certains bits via des additionneurs dont le nombre est choisi inférieur de un au nombre de termes non nuls du polynôme générateur. Des additionneurs sont installés aux entrées des bits de registre qui correspondent aux termes non nuls du polynôme générateur.

La figure 17 montre un schéma d'un registre de codage pour convertir une combinaison de quatre bits en une combinaison de sept bits.

Figure 17 - Schéma du registre de codage

Dans le tableau La figure 4 montre comment, en décalant la combinaison originale 0101, la combinaison de codes cycliques 1010011 est obtenue. m= 7, k=4. Combinaison 0101, clé en position 1. Pendant les quatre premiers cycles d'horloge, le registre sera rempli, puis la clé est déplacée en position 2. Le feedback est fermé. Sous l'influence de sept horloges décalées, un code cyclique de sept bits est formé.

Tableau 4

Propriétés du code cyclique:

1) le code cyclique détecte toutes les erreurs uniques si le polynôme générateur contient plus d'un terme. Si g(X)=x+ 1, alors le code détecte les erreurs simples et toutes les erreurs impaires ;

2) code cyclique avec g(X)= (x+ 1)g(X) détecte toutes les erreurs simples, doubles et triples ;

3) code cyclique avec un polynôme générateur g(X) degrés r = n-k détecte toutes les erreurs de groupe d'une durée de r personnages.

Questions de contrôle

Les principales propriétés et le nom même des codes cycliques sont liés au fait que toutes les combinaisons autorisées de symboles binaires dans un message transmis peuvent être obtenues par l'opération d'un décalage cyclique d'un mot source : Généralement, les combinaisons de codes d'un code cyclique sont considéré non pas comme une suite de zéros et de uns, mais comme un polynôme de quelques degrés Tout nombre dans n'importe quel système numérique positionnel peut être représenté sous forme générale comme suit : où x est la base du système numérique ; a - chiffres d'un système numérique donné ; p-1, p-2,... - un indicateur de la puissance à laquelle la base est élevée, et en même temps les numéros de série qui occupent les chiffres. Pour le système binaire, x = 2 et a vaut « O » ou « 1 ». Par exemple, la combinaison binaire 01001 peut être écrite sous la forme d'un polynôme de l'argument x : lors de l'écriture d'une combinaison de codes sous forme de polynôme, l'unité du 1er chiffre est écrite sous la forme d'un terme "x", et le zéro n'est pas du tout écrit. . Représenter des combinaisons de codes sous forme de polynômes permet d'établir une correspondance biunivoque entre eux et de réduire les actions sur les combinaisons à des actions sur les polynômes. Ainsi, l'addition de polynômes binaires se réduit à l'addition modulo 2 de coefficients d'égalité puissances de la variable. Par exemple, la multiplication est effectuée selon la règle habituelle de multiplication des fonctions puissance, mais les coefficients résultants à un degré donné sont ajoutés modulo 2. Par exemple, la division est également effectuée comme division habituelle des polynômes ; dans ce Dans ce cas, l'opération de soustraction est remplacée par une opération d'addition modulo 2 : Comme indiqué ci-dessus, les codes sont appelés cycliques car le décalage cyclique a n ^ a l L,..., a 2, a 1, a d1 a n1 de la combinaison autorisée an (, a n _ 2,..., a 1 et 0 est également une combinaison autorisée. Une telle permutation cyclique, lors de l'utilisation de représentations sous forme de polynômes, est formée en multipliant ce polynôme par x. Si Y(x) = a nL x n1 + a n2 x n " 2 + ... + a ( x + a 0, alors Y(x)x = a n] x n + a n 2 x n "1 +... + a x x 2 + a^x. Pour que le degré du polynôme ne dépasse pas n -1, le terme x" est remplacé par un, donc : Par exemple, on a la combinaison de codes 1101110->x dans +x 5 +x 3 +.x g -1-x. Décalons-la d'un chiffre. On obtient : Ce qui revient à multiplier le polynôme d'origine par x : la théorie de la construction de codes cycliques est basée sur des sections d'algèbre supérieure qui étudient les propriétés des polynômes binaires. Un rôle particulier dans cette théorie est joué par les polynômes dits irréductibles, c'est-à-dire des polynômes qui ne peuvent pas être représentés comme un produit de polynômes de degrés inférieurs. Un tel polynôme membre n'est divisible que par lui-même et par un. L'algèbre supérieure sait que le binôme x"+1 est divisé sans reste par un polynôme irréductible. Dans la théorie du codage, les polynômes irréductibles sont appelés polynômes générateurs, car ils « forment » des combinaisons de codes autorisées (les polynômes irréductibles sont tabulés, voir le tableau 8.4). ) (9). L'idée de construire un code cyclique revient au fait que le polynôme représentant la partie informationnelle de la combinaison de codes doit être transformé en un polynôme de degré pas plus de n-1, qui est divisible sans reste par le polynôme générateur P(x).Il est important que le degré de ce dernier corresponde au nombre de chiffres qui contrôlent la partie de la combinaison de codes. Dans les codes cycliques, toutes les combinaisons autorisées présentées sous forme de polynômes ont une caractéristique : la divisibilité sans reste par le polynôme générateur P(x).La construction d'une combinaison de codes autorisée se réduit à la suivante : 1. Nous présentons la partie informationnelle de la combinaison de codes de longueur k sous la forme d'un polynôme O(x). 3. Divisez le polynôme O(x)x" en un polynôme générateur P(x), dont le degré est égal à r. En multipliant O(x) par xr, le degré de chaque monôme inclus dans O( x) augmente de r. En divisant le produit de x g O[x) par un polynôme générateur de degré r, on obtient le quotient C(x) du même degré que 0(x).Les résultats de ces opérations peuvent être présentés dans le formulaire: (8.28) où R(x) est le reste de la division de 0(x)x r par P(x). Puisque C(x) a le même degré que 0(x), alors C(x) est une combinaison de codes du même code à ¿-bits. Le degré du reste ne peut évidemment pas être supérieur au degré du polynôme générateur, c'est-à-dire que son degré le plus élevé est égal à r-1. Par conséquent, le plus grand nombre de chiffres du reste ne dépasse pas r. En multipliant les deux côtés de (8,28) par P(x), en rampant : (8.29) (le signe de soustraction est remplacé par le signe d'addition modulo 2). Évidemment, F(x) est divisible par P(x) sans reste. Le polynôme F(x) est le modèle de code cyclique autorisé. De (8.29) il résulte que la combinaison de codes autorisée d'un code cyclique peut être obtenue de deux manières : en multipliant la combinaison de codes d'un code simple C(x) par le polynôme générateur P(x) ou en multipliant la combinaison de codes O (x) d'un code simple par un monôme x r en ajoutant à ce produit du reste P(x), obtenu en divisant le produit par le polynôme générateur P(x). Avec la première méthode de codage, les bits d'information et de vérification ne sont pas séparés les uns des autres (le code est indissociable). Cela rend le processus de décodage difficile à mettre en œuvre en pratique. Avec la deuxième méthode, un code séparable est obtenu : les bits d'information occupent les positions les plus élevées, les bits p-c restants sont ceux de vérification. Cette méthode de codage est largement utilisée dans la pratique. Exemple 3. Étant donné la combinaison de codes 0111. Construisons un code cyclique avec d o = 3. Solution. Dans un premier temps, sur la base du d o = 3 requis, nous déterminons la longueur du code l et le nombre d'éléments de contrôle k. Pour ce faire, nous utilisons le tableau 8.6.1. Pour une combinaison de code à quatre chiffres donnée, N-16. Ensuite, pour d = 3 à partir de la relation 16 (tableau 8.3), nous trouvons n - 7, respectivement, k = n - m - = 7 - 4 = 3. Par conséquent, le code (7.4) est nécessaire. En utilisant le tableau de génération de polynômes (Tableau 8.4) pour k = 3, on détermine P(x) = x 3 + x 2 + 1. Ensuite : 1) pour le message 0111 on a O(x) = x 2 + x + 1 ; 2) multiplier 0(x) par x 3 (puisque r = 3) : O(x) x 3 = (x 2 -I- x + 1) x 3 = x 5 + x 4 + x 3 ; 3) diviser (E(x)x 3 par P(x) : 4) on obtient : ^(x) = O (x) x 3 0 R (x) = x 5 + x 4 + x 3 + 1. Ce polynôme correspond à la combinaison de codes : Toutes les opérations ci-dessus peuvent également être effectuées sur des nombres binaires : Tableau 8.4
4) F(0,1) = O(0,l)x 3 (0,l)©R(0 1 l) = 011100000001= 0111 001. Construisons maintenant la combinaison de codes autorisée de la première manière : F( x)=C(x)P(x). Faisons la multiplication en représentant les polynômes sous forme de nombres binaires : On peut voir que dans la combinaison de codes résultante, il est impossible de distinguer les bits d'information et de vérification. La détection des erreurs lors du codage cyclique revient à diviser la combinaison de codes reçue par le même polynôme générateur que celui utilisé lors du codage (son type doit être connu à la réception). S'il n'y a pas d'erreurs dans la combinaison de codes reçue (ou si elles sont telles que la combinaison de codes transmise donnée est convertie en une autre combinaison autorisée), alors la division par le polynôme générateur sera effectuée sans reste. Si la division donne un reste, cela indique la présence d'une erreur. Exemple 4. Comme combinaison de codes autorisée, nous prenons la combinaison de codes obtenue dans l'exemple précédent : P(x) = x 5 + x 4 + x 3 + 1, et P(x) = x 3 + x 2 +1, ou sous forme binaire E(0,1) = 0111001 ; P(0,1) = 1101. Supposons que dans la partie information, une erreur s'est produite dans le chiffre le plus significatif (7ème) (on compte les chiffres de droite à gauche). La combinaison de codes acceptée ressemble à 1111001. Effectuons l'opération de détection d'erreur : La présence d'un résidu de 110 indique une erreur. Les codes cycliques sont largement utilisés dans les systèmes de transmission d'informations. Par exemple, dans le protocole modem largement utilisé \7.42, pour coder les groupes de codes, un polynôme générateur d(X) = X 16 + X "-2 + X 5 + 1 est utilisé, ce qui équivaut au code 1 0001 0000 0010. 0001, ainsi qu'un polynôme générateur d'ordre supérieur d(X) = X 32 + X 26 + X 23 + X 22 + X 16 + X 12 + X 11 + X 10 + X 8 + X 1 + X 5 + X 4 + X 2 + 1. 8.6.

Il s'agit d'une sous-classe de codes linéaires qui ont la propriété gem selon laquelle la permutation cyclique des symboles dans un bloc codé produit un autre bloc codé possible du même code. Les codes cycliques sont basés sur l’application d’idées issues de la théorie algébrique des champs de Galois1.

La plupart des codes de systèmes de communication antibruit les plus importants sont

en particulier cyclique, basé sur les structures de l'arithmétique finie

Champs Galois. Champ est l'ensemble des éléments qui ont un corps fini

Les noms des opérations sont entre guillemets car il ne s’agit pas toujours d’opérations arithmétiques courantes. Le champ contient toujours un élément zéro (0), ou zéro, et un élément unité (1), ou un. Si le numéro q les éléments du champ sont limités, alors le champ est appelé champ fini, ou champ de Galois fini, et est noté GF(q)y Où q- ordre des champs. Le plus petit corps de Galois est un corps à deux éléments copine ( 2), constitué de seulement deux éléments 1 et 0. Afin de

1 Evariste Galois (1811 - 1832) - mathématicien français, a posé les bases de l'algèbre moderne.

effectuer des opérations sur des éléments copine ( 2) n'ont pas conduit à dépasser les limites de ce champ, elles sont réalisées modulo 2 (en général cela est déterminé par l'ordre du champ pour champs de Galois simples).

Le champ possède un certain nombre de propriétés mathématiques spécifiques. Pour les éléments de champ, des opérations d'addition et de multiplication sont définies, et les résultats de ces opérations doivent appartenir au même ensemble.

Pour les opérations d'addition et de multiplication, les règles mathématiques habituelles d'associativité sont suivies - UN + (b + c) = (une + b)+ c, commutativité - une + b = b + une Et UN b = b UN et distributivité - UN (b+ c) = UN b + UN Avec.

Pour chaque élément de champ UN il doit y avoir un élément inverse à l'addition (-UN) et si UN non égal à zéro, élément inverse de multiplication (th').

Le champ doit contenir unité additive -élément 0 tel que UN + 0 = UN pour tout élément de champ UN.

Le champ doit contenir unité multiplicative -élément 1, tel que aL = une pour tout élément de champ UN.

Par exemple, il existe des champs de nombres réels, de nombres rationnels et de nombres complexes. Ces champs contiennent un nombre infini d'éléments.

En fait, tous les ensembles formés par permutation cyclique d’un mot de code sont également des mots de code. Ainsi, par exemple, les permutations cycliques de la combinaison 1000101 seront également des combinaisons de codes 0001011, 0010110, 0101100, etc. Cette propriété permet de simplifier grandement les dispositifs de codage et de décodage, notamment lors de la détection d'erreurs et de la correction d'une erreur unique. L'attention portée aux codes cycliques est due au fait que leurs propriétés correctives élevées inhérentes sont mises en œuvre sur la base de méthodes algébriques relativement simples. Dans le même temps, pour décoder un code de bloc linéaire arbitraire, on utilise plus souvent des méthodes de table, qui nécessitent une grande quantité de mémoire de décodeur.

Un code cyclique est un code de bloc linéaire. (n,k)- code caractérisé par la propriété de cyclicité, c'est-à-dire le décalage vers la gauche d'un pas de tout mot de code autorisé donne également un mot de code autorisé appartenant au même code, et pour lequel l'ensemble des mots de code est représenté par un ensemble de polynômes de degré (P.- 1) ou moins, divisible par le polynôme générateur g(x) degrés r = n-k y qui est un facteur du binôme X m+

Dans un code cyclique, les mots de code sont représentés par des polynômes (polynômes)

Où P- longueur du code ; Un je - coefficients du champ de Galois (valeurs de combinaison de codes).

Par exemple, pour la combinaison de codes 101101, l'entrée polynomiale a la forme

Des exemples de codes cycliques sont les codes de vérification paire, les codes de répétition, les codes de Hamming, les codes PC et les codes turbo.

Code de Hamming. La capacité de corriger les erreurs dans le code de Hamming est liée à la distance minimale du code d0. Toutes les erreurs de multiplicité sont corrigées q= cnt (d 0- l)/2 (ici cnt signifie « partie entière ») et les erreurs de multiplicité sont détectées d 0 - 1. Ainsi, lors de la vérification de la parité impaire réQ = 2 et des erreurs uniques sont détectées. En code de Hamming ré 0 = 3. En plus des catégories d'informations, il est introduit L= log 2 Q de bits de contrôle en excès, où Q- nombre de bits d'information. Paramètre L arrondi à la valeur entière supérieure la plus proche. Le code de contrôle des bits L est le résultat inversé de l'addition au niveau du bit (addition modulo 2) des nombres de bits d'information dont les valeurs sont égales à un.

Exemple 7.7

Ayons le code principal 100110, c'est-à-dire Q = 6. Définissons du code supplémentaire.

Solution

Nous trouvons que L= 3 et le code complément est

où P est le symbole de l'opération d'addition au niveau du bit, et après inversion nous avons 000. Le code supplémentaire sera désormais transmis avec le code principal. Au niveau du récepteur, le code supplémentaire est à nouveau calculé et comparé à celui transmis. Le code de comparaison est enregistré, et s'il est différent de zéro, alors sa valeur est le numéro du bit reçu par erreur du code principal. Ainsi, si le code 100010 est accepté, le code supplémentaire calculé est égal à l'inversion de 010Ш10 = 100, soit 011, ce qui signifie une erreur dans le 3ème chiffre.

Une généralisation des codes de Hamming sont les codes BCH cycliques, qui permettent de corriger de multiples erreurs dans la combinaison de codes adoptée.

Codes Reed-Salomon sont basés sur des champs de Galois, ou des zéros finis. Opérations arithmétiques addition, soustraction, multiplication, division, etc. sur les éléments d'un zéro final, on obtient un résultat qui est également un élément de ce zéro. L'encodeur ou le décodeur Reed-Solomon doit obligatoirement effectuer ces opérations. Toutes les opérations de mise en œuvre du code nécessitent du matériel spécial ou des logiciels spécialisés.

Turbocodes. Les codes redondants peuvent être utilisés soit indépendamment, soit sous la forme d'une combinaison de plusieurs codes, lorsque des ensembles de symboles d'un code redondant sont considérés comme des symboles d'information élémentaires d'un autre code redondant. Cette association a fini par s'appeler en cascade code. Un énorme avantage des codes concaténés est que leur utilisation permet de simplifier le codeur et surtout le décodeur par rapport à des dispositifs similaires de codes non concaténés de même longueur et redondance. Le codage en cascade a conduit à la création de turbocodes. Code turbo appeler une structure de signal parallèle composée de deux ou plusieurs codes systématiques. Le principe de base de leur construction est l’utilisation de plusieurs codeurs composants fonctionnant en parallèle. Comme codes composants, vous pouvez utiliser aussi bien des codes blocs que convolutifs, des codes de Hamming, du code PC, BCH, etc. L'utilisation de la perforation (crevaison) permet d'augmenter la vitesse relative du turbo code en adaptant sa capacité de correction aux caractéristiques statistiques du canal de communication. Le principe de génération du turbo code est le suivant : signal d'entrée X, composé de À bit, alimenté en parallèle à N entrelaceurs. Chacun de ces derniers est un dispositif qui réorganise les éléments dans un bloc de À bits dans un ordre pseudo-aléatoire. Le signal de sortie des entrelaceurs - symboles avec un ordre modifié - est envoyé aux codeurs élémentaires correspondants. Séquences binaires x p je= 1,2,..., JV, à la sortie du codeur se trouvent des symboles de contrôle qui, avec les bits d'information, constituent un seul mot de code. L'utilisation d'un entrelaceur permet d'éviter l'apparition de séquences d'erreurs corrélées lors du décodage des turbocodes, ce qui est important lors de l'utilisation de la méthode de décodage récurrente traditionnelle en traitement. En fonction du choix du code composant, les turbo codes sont divisés en turbo codes convolutifs et en codes produits bloc.

Code cyclique

Les codes cycliques font partie des codes systématiques par blocs dans lesquels chaque combinaison est codée indépendamment (sous forme de bloc) de telle sorte que l'information k et les symboles de contrôle soient toujours les mêmes.

s'habiller à certains endroits. La capacité de détecter et de corriger presque toutes les erreurs avec une redondance relativement faible par rapport à d'autres codes, ainsi que la simplicité de mise en œuvre des circuits des équipements de codage et de décodage, ont rendu ces codes très répandus. La théorie des codes cycliques est basée sur la théorie des groupes et l'algèbre des polynômes sur le corps de Galois.

Un code cyclique est un code dans lequel l'ordre de distribution des combinaisons de codes est effectué de telle manière que lors du passage d'une combinaison à la suivante, à chaque fois la distance du code de Hamming reste constante.

Les codes cycliques sont toute une famille de codes résistants aux erreurs, y compris les codes de Hamming comme l'une de leurs variétés, mais offrant en général une plus grande flexibilité en termes de capacité à mettre en œuvre des codes avec la capacité nécessaire pour détecter et corriger les erreurs qui surviennent lors de la transmission de combinaisons de codes. sur un canal de communication. Un code cyclique fait référence à des codes de blocs systématiques (n, k), dans lesquels les k premiers chiffres représentent une combinaison du code primaire et les chiffres suivants (n ? k) sont des chiffres de contrôle.

La construction de codes cycliques est basée sur l'opération de division de la combinaison de codes transmise par un polynôme irréductible générateur de degré r. Le reste de la division est utilisé pour former les chiffres de contrôle. Dans ce cas, l'opération de division est précédée d'une opération de multiplication, qui décale la combinaison de codes d'informations de k bits vers la gauche de r bits.

Un polynôme (polynôme) qui peut être représenté comme un produit de polynômes de degrés inférieurs est dit réductible (dans un domaine donné), sinon irréductible. Les polynômes irréductibles jouent un rôle similaire à celui des nombres premiers dans la théorie des nombres. Les polynômes irréductibles P(X) peuvent être écrits sous forme de nombres décimaux ou binaires ou sous forme de polynôme algébrique.

Processus de codage cyclique

Le codage cyclique repose sur l'utilisation d'un polynôme irréductible P(X), qui par rapport aux codes cycliques est appelé générateur, générateur ou polynôme générateur (polynôme).

Les combinaisons de code binaire pour toutes les combinaisons sont prises comme symboles d'information k pour la construction de codes cycliques. Dans le cas général, si une combinaison de codes donnée Q(x) est multipliée par un polynôme générateur P(x), le résultat est un code cyclique qui possède certaines propriétés correctives selon le choix de P(x). Cependant, dans ce code, les symboles de commande m seront situés à des endroits très variés dans la combinaison de codes. Un tel code n’est pas systématique, ce qui rend sa mise en œuvre difficile. La situation peut être considérablement simplifiée si des symboles de contrôle sont ajoutés à la fin, c'est-à-dire après les symboles d'information. Pour cela, il est conseillé d'utiliser la méthode suivante :

On multiplie la combinaison de codes G(x) qui doit être codée par un monôme X m ayant le même degré que le polynôme générateur P(x) ;

On divise le produit G(x)Х m par le polynôme générateur Р(х m) :

où Q(x) est le quotient de division ; R(x) - reste.

En multipliant l'expression (2.1) par P(x) et en transférant R(x) à l'autre partie de l'égalité sans inverser le signe, on obtient :

Ainsi, selon l'égalité (2.2), un code cyclique, c'est-à-dire un message codé F(x), peut être formé de deux manières :

Multiplication d'une combinaison de codes d'un code binaire par toutes les combinaisons par un polynôme générateur P(x) ;

En multipliant une combinaison de codes donnée G(x) par un seul polynôme X m ayant le même degré que le polynôme générateur P(x), en ajoutant le reste R(x) obtenu après division du produit G(x)X m par le polynôme générateur polynôme P( X).

Encodage des messages

Il est nécessaire de coder la combinaison de codes 1100, qui correspond à G(x)=x 3 +x 2 en utilisant P(x)=x 3 +x+1.

On multiplie G(x) par X m, qui a la troisième puissance, on obtient :

En divisant le produit G(x)Х m par le polynôme générateur Р(х m), selon (2.1) on obtient :

ou en équivalent binaire :

Ainsi, on obtient le quotient Q(x) du même degré que G(x) :

Q(x)=x 3 +x 2 +x>1110

et le reste :

En conséquence, la combinaison de code binaire codée avec un code cyclique, selon (2.2), prendra la forme :

F(x)=1110 1011=1100010

Puisque chaque combinaison de codes cycliques autorisée représente toutes les sommes possibles du polynôme générateur G(x), elles doivent être divisibles par P(x) sans reste. Par conséquent, vérifier l'exactitude de la combinaison de codes acceptée revient à identifier le reste en le divisant par le polynôme générateur.

La réception d'un solde indique la présence d'une erreur. Le reste de la division en codes cycliques joue le rôle d'un syndrome.

Par exemple, la combinaison de codes transmise F(x)=1100010, construite à l'aide du polynôme générateur P(x)=1011. Sous l'influence d'interférences, la combinaison de codes s'est transformée en la combinaison F"(x)=1000010

On divise la combinaison acceptée par un polynôme générateur

La présence du reste R(x)=001 indique une erreur. Cependant, cela n’indique pas directement l’emplacement de l’erreur dans la combinaison. Pour déterminer l'erreur, il existe plusieurs méthodes basées sur l'analyse du syndrome.

Déterminons l'emplacement de l'erreur ; pour ce faire, divisons un avec un nombre arbitraire de zéros par P(x) = 1011.

Une erreur s'est produite dans le numéro d'élément :

Nombre de résidus -2>4-2=2

Autrement dit, l'erreur réside dans le deuxième élément.

Un code cyclique est un code linéaire, qui est un ensemble fini fermé sous l'opération de décalage cyclique des vecteurs de code qui le composent. Qu'il soit donné n vecteur dimensionnel v = un 0 un 1 …un-1 avec les coordonnées du champ final F. Son déplacement cyclique est appelé vecteur v"= un n-1 une 0 une 1 … un -2 .

Considérons n-espace arithmétique dimensionnel sur un corps de Galois Petite amie(2). Chaque vecteur un 0 un 1 …un-1 de Petite amie(2) on peut comparer le polynôme un à un un 0 +un 1 X+…+un -1 xn-1 avec une cote de Petite amie(2). La somme de deux vecteurs un 0 un 1 …un-1 et b 0 b 1 …bn-1 est mis en correspondance avec la somme des polynômes qui leur correspondent, le produit des éléments du champ par le vecteur - le produit du polynôme correspondant à ce vecteur par l'élément.

Considérons un polynôme g(X) à partir de l'espace linéaire décrit. L'ensemble de tous les polynômes de ce sous-espace qui sont divisibles sans reste par g(X), forme un sous-espace linéaire. Un sous-espace linéaire définit un code linéaire.

Code linéaire formé par une classe de polynômes C(g(X)), multiples de certains polynômes g(X), appelé polynôme générateur, est appelé polynôme.

Montrons comment les codes polynomiaux sont liés C(g(X)) et les codes cycliques. Laisser un = un 0 …un-1 est un mot de code et le polynôme de code correspondant un(X) = un 0 +...+un -1 xn-1 . Changement cyclique un" correspond au polynôme code un"(X) = un -1 +un 0 X+…+un -2 X n -1 , qui peut être exprimé en fonction de l'original :

Puisqu'un code polynomial doit être divisible par g(X), alors pour qu'il soit cyclique, le polynôme un"(X) doit être divisible par g(X). A partir de cette considération, nous pouvons formuler le théorème suivant. Un code polynomial est cyclique si et seulement si le polynôme g(X) est un diviseur du polynôme xn-1. Dans ce cas le polynôme g(X) est appelé polynôme générateur du code cyclique.

En théorie du codage, le théorème suivant est prouvé : si un polynôme g(X) est titulaire d'un diplôme n–k et est un diviseur xn–1, alors C(g(X)) est cyclique linéaire ( n, k)-code.

Polynôme xn–1 factoriser xn–1 = (X–1)(xn -1 +xn-1 +…+1). Par conséquent, des codes cycliques existent pour tout n. Nombre de cycliques n-bit codes est égal au nombre de diviseurs du polynôme xn-1. Des tables d'expansion polynomiales ont été développées pour construire des codes cycliques xn–1 en polynômes irréductibles, c'est-à-dire en ceux qui ne sont divisibles que par l'unité et par lui-même.

Considérons, par exemple, quels codes peuvent être construits sur la base du polynôme X 7-1 sur le terrain Petite amie(2). Le développement du polynôme en facteurs irréductibles a la forme

Puisqu'il est possible de former six diviseurs d'un polynôme X 7-1, combinant des diviseurs irréductibles, il existe six codes cycliques binaires. ( n, k)-code est déterminé, en premier lieu, par la valeur n, et deuxièmement, la valeur k = n – s, s– degré du polynôme diviseur xn–1, qui définit le code. Vous trouverez ci-dessous les diviseurs polynomiaux et leurs valeurs correspondantes k:

X – 1, s=1, k=6;

X 3 +x 2 +1, s=3, k=4;

X 3 +x+1, s=3, k=4;

(X–1)(X 3 +x 2 +1)=X 4 +x2 +x+1, s=4, k=3;

(X–1)(X 3 +x+1)=X 4 +x3 +x2 +1, s=4, k=3;

(X 3 +x 2 +1)(X 3 +x+1)=X 6 +X 5 +X 4 +X 3 +X 2 +X, s=6, k=1.

Le code (7, 6) n'a qu'un seul symbole de contrôle et le code (7, 1) n'a qu'un seul symbole d'information. Il s'agit respectivement d'un code de contrôle de parité et d'un code de répétition.

Comme un code linéaire régulier, un code cyclique peut être spécifié par une matrice génératrice. Par conséquent, la tâche est de trouver une telle matrice, c'est-à-dire de trouver k combinaisons de codes linéairement indépendantes qui le composent. Pour cela, nous utilisons la propriété du code cyclique étant fermé par rapport à l'opération de décalage cyclique. Notez qu'un déplacement cyclique d'une place vers la droite équivaut à multiplier le polynôme g(X) sur X. Ensuite, la matrice génératrice peut être construite en prenant le polynôme générateur et k ses changements cycliques :

Voyons maintenant comment, en utilisant le polynôme générateur g(X) = 1+X+X L'encodage 3 s'effectue avec un code (7, 4). Prenons par exemple un mot de 4 bits (0101), qui correspond à un polynôme F(X) = X + X 3. Multiplier ces deux polynômes.