Un code cyclique est un code linéaire, qui est un ensemble fini fermé par rapport à 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 de destination F. Son décalage cyclique est appelé le vecteur v"= un n-1 à 0 à 1 ... un -2 .

Considérer n espace arithmétique de dimension sur un corps de Galois GF(2). Chaque vecteur un 0 un 1 …un-1 sur GF(2) on peut associer un polynôme bijectif un 0 +un 1 X+…+un -1 xn-1 avec des coefficients de GF(2). La somme de deux vecteurs un 0 un 1 …un-1 et b 0 b 1 …b n-1 correspond à la somme des polynômes qui leur correspondent, au 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) 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 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 . décalage cyclique un" correspond au polynôme de code un"(X) = un -1 +un 0 X+…+un -2 X n -1 , qui peut être exprimé en fonction de l'original :

Puisque le 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é un polynôme générateur d'un code cyclique.

En théorie des codes, le théorème suivant est démontré : si un polynôme g(X) a un diplôme n–k et est un diviseur xn-1, puis 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. Pour construire des codes cycliques, des tables de décomposition de polynômes ont été développées xn-1 pour les polynômes irréductibles, c'est-à-dire pour ceux qui ne sont divisibles que par 1 et lui-même.

Considérons, par exemple, quels codes peuvent être construits sur la base du polynôme X 7–1 sur le terrain GF(2). La décomposition d'un polynôme en facteurs irréductibles a la forme

Puisqu'il est possible de former six diviseurs du polynôme X 7–1, en combinant des diviseurs irréductibles, il existe six codes cycliques binaires. ( n, k)-code est déterminé, premièrement, par la valeur n, et d'autre part, la valeur k = n – s, s est le degré du polynôme diviseur xn-1 définissant le code. Voici les diviseurs du polynôme 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+x 2+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 ordinaire, un code cyclique peut être donné par une matrice génératrice. Par conséquent, la tâche consiste à trouver une telle matrice, c'est-à-dire à trouver k combinaisons de codes linéairement indépendantes qui le composent. Pour cela, on utilise la propriété de la fermeture d'un code cyclique par rapport à l'opération d'un décalage cyclique. Notez qu'un décalage cyclique vers la droite d'un chiffre équivaut à multiplier le polynôme g(X) sur X. Ensuite, la matrice génératrice peut être construite en prenant comme lignes le polynôme générateur et k ses déplacements cycliques :

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

Les codes cycliques sont une sorte de codes de groupe linéaire et appartiennent aux codes systématiques. Ils ont été créés à l'origine pour simplifier la procédure de décodage. Cependant, l'efficacité élevée de détection d'erreurs de tels codes a assuré leur large application dans la pratique. Il est commode de considérer un vecteur binaire d'un code cyclique non pas comme une combinaison de zéros et de uns, mais comme un polynôme d'un certain degré

où x est la base du système numérique, les coefficients appartenant à l'ensemble dans le cas du système numérique binaire.

Exemple. Un vecteur binaire peut être représenté comme un polynôme comme suit :

La représentation des vecteurs binaires sous forme de polynômes permet de réduire l'opération sur les vecteurs à des opérations sur les polynômes. Où:

l'addition des polynômes est réduite à la somme modulo 2 des coefficients à puissances égales de la variable

la multiplication est effectuée selon la règle habituelle de multiplication des fonctions puissances, cependant les coefficients obtenus à un degré donné sont additionnés modulo 2 ;

la division s'effectue selon les règles de division des fonctions puissances, tandis que l'opération de soustraction est remplacée par une sommation modulo 2.

Exemple. Trouver la somme de polynômes

Trouver le produit de polynômes

Effectuer une division polynomiale

La principale propriété des codes cycliques est la suivante : si un vecteur appartient à un code cyclique, alors tout vecteur obtenu à partir de celui considéré à l'aide de décalages cycliques appartient également au code cyclique.

L'idée de construire des codes cycliques repose sur la notion de polynôme irréductible. Un polynôme est dit irréductible s'il n'est divisible que par lui-même et par 1, et n'est divisible par aucun autre polynôme. En d'autres termes, un polynôme irréductible ne peut pas être représenté comme un produit de polynômes de degrés inférieurs. Un polynôme irréductible divise un polynôme sans reste. Les polynômes irréductibles jouent le rôle de polynômes générateurs dans la théorie des codes cycliques. Les types de polynômes irréductibles de divers degrés sont donnés dans

Exemples de polynômes irréductibles :

Les vecteurs de code cycliques sont construits selon les règles suivantes. Soit n'importe quel vecteur binaire d'un code naturel ; - monôme de degré polynôme de degré irréductible Alors tout vecteur d'un code cyclique est formé à l'aide de la relation

où est le reste de la division

Ainsi, tout vecteur d'un code cyclique peut être formé en multipliant un vecteur de naturel code binaire par un monôme de degré avec l'ajout du reste de la division au produit résultant.Lors de la construction de codes cycliques de cette manière, l'emplacement des bits d'information dans chaque vecteur de code est strictement ordonné - ils occupent les bits les plus élevés du vecteur de code, et les bits restants sont des bits de contrôle.

Exemple. Le vecteur de code binaire naturel a la forme

Représentons le vecteur sous la forme d'un polynôme

En divisant un polynôme par un polynôme, on obtient le reste. C'est pourquoi

Un code cyclique, comme tout code systématique, peut être commodément spécifié sous forme matricielle à l'aide d'une matrice génératrice de la forme

où est l'unité yatrix transposée du format - la matrice de chiffres de contrôle formée par le reste de la division

Fixons la matrice génératrice du code cyclique avec la longueur des bits d'information et le polynôme générateur .

Évidemment, le blanc de la matrice génératrice a la forme

Pour trouver les lignes de bits de contrôle de la matrice, on calcule et on écrit sous forme de polynôme chaque vecteur de la matrice identité

La longueur du vecteur de code cyclique est donc

(voir scan)

On obtient ainsi la matrice génératrice C :

Tout vecteur d'un code cyclique est obtenu comme une somme modulo les vecteurs de sa matrice génératrice. Le code cyclique étant un code de groupe, le vecteur zéro est toujours affecté au code cyclique comme élément d'identité du groupe.

Tableau 13.5

Exemple. Construire tous les vecteurs du code cyclique donné par la matrice génératrice

Le code est présenté dans le tableau. 13.5.

Il convient de noter que chaque code cyclique donné par une certaine matrice génératrice peut être représenté en plusieurs versions, différant les unes des autres par la longueur et le nombre de bits d'information (avec les mêmes capacités de détection). Ces versions des codes cycliques dits raccourcis sont obtenues en supprimant les dernières lignes et le même nombre de colonnes à gauche dans la matrice génératrice du code cyclique. Dans ce cas, le nombre de chiffres de contrôle reste inchangé, et la longueur du code et le nombre de ses chiffres d'information sont réduits, respectivement, d'une quantité égale au nombre de lignes et de colonnes barrées de la matrice génératrice.

Exemple, Un code cyclique est donné par sa matrice génératrice

Barrons les six dernières lignes et les six premières colonnes à partir de la gauche. On obtient la matrice génératrice

Les caractéristiques (en termes de détection d'erreur) du code résultant sont les mêmes que celles du code cyclique représenté par la matrice génératrice

Construction de codes cycliques avec paramètres donnés est liée au choix du générateur du polynôme irréductible. Le polynôme générateur est sélectionné en fonction de la condition suivante : le degré du polynôme doit être égal au nombre de bits de contrôle du code cyclique.

En pratique, il se pose souvent le problème de construire un code cyclique d'une puissance donnée et d'une capacité de détection et de correction donnée.

1. La puissance du code cyclique étant donnée, le nombre de ses bits d'information est déterminé selon la formule

2. Le nombre optimal de chiffres de contrôle du code cyclique est déterminé par des tables spéciales.

3. D'après les répertoires, tous les polynômes irréductibles de degré se trouvent

4. Pour l'un des polynômes non conducteurs (il faut choisir un polynôme avec le nombre maximum de termes) de degré, on construit une matrice génératrice d'un code cyclique. Chaque vecteur de code est calculé par la formule

où est le polynôme du vecteur d'information de la matrice génératrice ; - monôme de degré - reste de division

5. La matrice génératrice construite est vérifiée pour les conditions suivantes :

a) le poids au sens de Hamming de tout vecteur de la matrice génératrice doit satisfaire la relation où est la distance minimale, au sens de Hamming, du code cyclique considéré ;

b) le poids au sens de Hamming du vecteur de contrôle, qui est la somme modulo 2 de deux vecteurs de contrôle quelconques de la matrice génératrice, doit satisfaire la relation

6. Si la matrice génératrice du code cyclique satisfait toutes les conditions ci-dessus, alors tous les vecteurs du code cyclique sont écrits et déterminés conformément aux règles connues pour les codes de groupe linéaires. Si le code ne répond pas aux exigences, alors un autre polynôme générateur du même degré est choisi et la procédure de génération d'un code cyclique est répétée pour un nouveau polynôme.

Construisons un code cyclique de puissance 16 et un code correctif de capacité

Pour déterminer la valeur par

3 "D'après les ouvrages de référence, nous trouvons tous les polynômes irréductibles de degré. Il existe deux polynômes de ce type :

4. On choisit comme polynôme générateur Le blanc de la matrice génératrice du code cyclique a la forme

Chaque vecteur d'information de la matrice est représenté par un polynôme

Nous déterminons complètement tous les vecteurs de la matrice génératrice en utilisant la formule

Puisque la longueur du vecteur de code cyclique (voir le format de la matrice génératrice, alors

De même, on retrouve tous les autres vecteurs de la matrice génératrice

Tableau 13.6

Le résultat est une matrice génératrice C? code cyclique

5. La matrice génératrice résultante satisfait toutes les conditions nécessaires. Par conséquent, nous construisons complètement un code cyclique (tableau 13.6). Comme il ressort du tableau, le code a, c'est-à-dire satisfait aux exigences de la tâche.

Remarques. En utilisant un polynôme irréductible comme générateur, on obtient un code qui satisfait également aux exigences du problème. Sa matrice génératrice a la forme

La détection d'erreurs à l'aide de codes cycliques s'effectue comme suit. Tout vecteur d'un code cyclique est divisible par un polynôme générateur sans reste. Ainsi, le critère de présence d'erreur dans le vecteur de code cyclique est l'apparition d'un reste non nul de la division du vecteur de code cyclique par le polynôme générateur. Le reste non nul est l'identité de l'erreur dans le vecteur de code cyclique, mais son apparence n'indique pas l'emplacement de l'erreur dans le vecteur de code. La correction d'erreur est basée sur l'algorithme suivant :

1. Divisez le vecteur de code reçu en un polynôme générateur.

Si le nombre d'unités ne dépasse pas la capacité corrective du code, alors ajoutez le vecteur reçu modulo 2 avec le reste résultant. Le résultat de la sommation donnera le vecteur de code corrigé. Si le nombre d'unités du reste est supérieur à la capacité correctrice du code, alors effectuer un décalage cyclique du vecteur déformé vers la gauche d'un bit, puis diviser par un polynôme générateur. Si le reste reçu ne contient pas plus d'unités que la capacité corrective du code cyclique, alors additionnez le vecteur décalé cycliquement avec le reste. Le résultat de la sommation est décalé cycliquement d'un chiffre vers la droite. Le vecteur résultant ne contient plus d'erreurs et est un vecteur de code cyclique.

3. Si, après le premier décalage cyclique et la division suivante, le reste contient plus d'unités que la capacité corrective du code, répétez la procédure de l'algorithme jusqu'à ce qu'un reste avec un nombre d'unités ne dépassant pas la capacité corrective du code soit obtenu. Dans ce cas, le résultat du dernier décalage cyclique est additionné avec le reste et le vecteur résultant est décalé cycliquement d'autant de bits vers la droite que le vecteur original reçu avec une erreur a été décalé vers la gauche. Le résultat est un vecteur de code corrigé.

Soit le code cyclique donné par sa matrice génératrice С et son polynôme générateur , où

Le code vaut 3, c'est-à-dire qu'il corrige les erreurs de multiplicité, prenons le vecteur 0011101 à la place du vecteur 0001101. Pour corriger l'erreur, nous effectuons les actions suivantes. On écrit le vecteur reçu sous la forme d'un polynôme : puis on divise par

Le reste obtenu à la suite de la division contient trois unités, ce qui est supérieur à la capacité corrective du code. Par conséquent, nous effectuons un décalage cyclique vers la gauche d'un bit du vecteur de code reçu. En conséquence, nous avons

On divise par

Le reste résultant contient deux unités, ce qui est supérieur à la capacité corrective du code. Par conséquent, nous effectuons un décalage cyclique supplémentaire vers la gauche d'un bit du vecteur de code reçu. En conséquence, nous avons

On divise par

Le reste résultant contient à nouveau deux unités, nous effectuons donc un décalage cyclique supplémentaire vers la gauche d'un bit et nous obtenons Diviser par

Une classe de codes linéaires, appelés codes chinois. Le nom vient de la propriété principale de ces codes : si une combinaison de codes appartient à un code cyclique, alors la combinaison obtenue par permutation cyclique de la combinaison d'origine (décalage cyclique) appartient également à ce code :

La deuxième propriété de toutes les combinaisons autorisées de codes cycliques est leur divisibilité sans reste par un polynôme sélectionné, appelé le générateur.

Ces propriétés sont utilisées dans la construction de codes d'encodeur et de décodeur, ainsi que dans la détection et la correction d'erreurs.

Les codes cycliques sont toute une famille de codes correcteurs d'erreurs (dont l'une des variétés sont les codes de Hamming), ce qui offre une grande flexibilité en termes de possibilité d'implémenter des codes avec la capacité nécessaire pour détecter et corriger les erreurs qui se produisent lors de la transmission de combinaisons de codes. sur un canal de communication. Le code cyclique fait référence aux codes systématiques en bloc (n, &), dans lesquels Pour les premiers bits sont une combinaison du code primaire, et le suivant (l - Pour) les chiffres sont testés.

La construction des codes cycliques est basée sur l'opération de division de la combinaison de codes transmise par le polynôme irréductible générateur de degré G. Le reste de la division est utilisé dans la formation des bits de contrôle. Dans ce cas, l'opération de division est précédée de l'opération de multiplication, qui décale la combinaison de code d'information ^-bit vers la gauche de g décharges.

Lors du décodage de la combinaison de codes à n bits reçue, la division en un polynôme de génération (production, formation) est à nouveau effectuée.

Le syndrome d'erreur dans ces codes est la présence du reste de la division de la combinaison de codes reçue par le polynôme générateur. Si le syndrome est nul, on considère qu'il n'y a pas d'erreurs. Sinon, en utilisant le syndrome reçu, vous pouvez déterminer le numéro de bit de la combinaison de codes reçue dans laquelle une erreur s'est produite et la corriger.

Cependant, la possibilité d'erreurs multiples dans les combinaisons de codes n'est pas exclue, ce qui peut entraîner de fausses corrections et (ou) une incapacité à détecter les erreurs lors de la transformation d'une combinaison autorisée en une autre.

Soit i le nombre total de bits dans le bloc, dont informations utiles porter J bits, puis en cas d'erreur il est possible de corriger j bits. Dépendance 5 sur P Et J pour les codes peuvent être déterminés à partir du tableau. 2.6.

Tableau 2.6

Dépendance du nombre total de chiffres des combinaisons sur le nombre d'informations et de chiffres corrigeables

Augmenter la différence (NT), il est possible non seulement d'augmenter le nombre de bits corrigés s, mais aussi pour détecter les erreurs multiples. Les pourcentages d'erreurs multiples détectées sont indiqués dans le tableau. 2.7.

Tableau 2.7

Pourcentage d'erreurs multiples détectées

Il est commode de décrire des codes cycliques et de les construire à l'aide de polynômes (ou polynômes). L'enregistrement de combinaison sous forme de polynôme permet de visualiser de manière formalisée l'opération de décalage cyclique de la combinaison de code d'origine. Ainsi, le mot de code "-element peut être décrit par le polynôme (P- 1) degré :

Oùa„_j =(0, 1), etun „_, =0 correspond à des éléments nuls de la combinaison, d„_, = 1 - non nul ;je- le numéro du chiffre de la combinaison de code.

Présentons des polynômes pour des combinaisons spécifiques à 4 éléments :

Les opérations d'addition et de soustraction sont équivalentes et associatives et sont effectuées modulo 2 :

Exemples d'opérations :

L'opération de division est la division habituelle des polynômes, mais au lieu de la soustraction, l'addition modulo 2 est utilisée :

Le décalage cyclique d'une combinaison de codes est le mouvement de ses éléments de droite à gauche sans perturber leur ordre, de sorte que l'élément le plus à gauche prend la place de celui qui est le plus à droite.

Les propriétés principales et le nom des codes cycliques sont liés au fait que toutes les combinaisons de bits autorisées dans le message transmis (mots de code) peuvent être obtenues par l'opération d'un décalage cyclique d'un mot de code source.

Supposons que la combinaison de code initiale et le polynôme correspondant soient donnés :

multiplions Oh) sur X:

Depuis le degré maximum X dans une combinaison de codes de longueur P ne dépasse pas (n - 1), alors du côté droit de l'expression résultante pour obtenir le polynôme d'origine, il faut soustraire Oh"- 1). Soustraction Oh"- 1) s'appelle prendre le reste modulo (xp - 1).

Le décalage de la combinaison originale de / mesures peut être représenté comme suit : hache)? U- Oh"- 1), c'est-à-dire multiplication Oh) nah" et en prenant le reste modulo (x" - 1). Prendre le reste est nécessaire lors de l'obtention d'un polynôme de degré supérieur ou égal à P

L'idée de construire des codes cycliques repose sur l'utilisation polynômes irréductibles. Un polynôme irréductible est un polynôme qui ne peut pas être représenté comme un produit de polynômes de degrés inférieurs, c'est-à-dire n'est divisible que par lui-même ou par 1 et n'est divisible par aucun autre polynôme. Un binôme (x" + 1) est divisible par un tel polynôme sans reste. Les polynômes irréductibles dans la théorie des codes cycliques jouent le rôle de polynômes générateurs.

Revenant à la définition d'un code cyclique et compte tenu de la notation des opérations de décalage cyclique des combinaisons de codes, on peut écrire la matrice génératrice d'un code cyclique sous la forme suivante :

OùP(x)- la combinaison de codes d'origine, sur la base de laquelle tous les autres sont obtenus(T- 1) combinaisons de base ;

C, = 0 ouCj =1 ("O" si le degré résultant du polynômeP(x)-x‘ne dépasse pas (l - 1), ou "1" - s'il dépasse).

Combinaison P(x) est appelée une combinaison génératrice (génératrice). Pour construire un code cyclique, il suffit de choisir correctement P(x). Ensuite, toutes les autres combinaisons de codes sont les mêmes que dans le code de groupe.

Le polynôme générateur doit satisfaire aux exigences suivantes :

• P(x) doit être différent de zéro ;
• lester P(x) ne doit pas être inférieure à la distance de code minimale : V(P(x)) > dmm ;
• P(x) doit avoir degré maximal k (k - le nombre d'éléments redondants dans le code) ;
• P(x) doit être un diviseur du polynôme (x" - 1).

La satisfaction de la dernière condition conduit au fait que toutes les combinaisons de code de travail du code cyclique acquièrent la propriété de divisibilité par P(x) sans laisser de trace. Dans cet esprit, une autre définition d'un code cyclique peut être donnée : un code cyclique est un code dont toutes les combinaisons de travail sont divisibles par un polynôme générateur sans reste.

Pour déterminer le degré du polynôme générateur, vous pouvez utiliser l'expression r > log 2 (et + 1), où P- la taille du paquet transmis à la fois, c'est-à-dire la longueur du code cyclique en cours de construction.

Des exemples de polynômes générateurs sont donnés dans le tableau. 2.8.

Tableau 2.8

Exemples de génération de polynômes

L'algorithme pour obtenir une combinaison de code autorisée d'un code cyclique à partir d'une combinaison d'un code simple est le suivant.

Soit le polynôme donné P (x) \u003d une g _ ( X g + une g _ 2 x r ~ 1 + ... + 1, qui détermine la capacité corrective du code, et le nombre de chiffres de contrôle Pour, ainsi que la combinaison originale d'un simple code à partir de l'élément et de bits d'information sous la forme d'un polynôme A t (x).

Il est nécessaire de déterminer la combinaison de codes autorisée du code cyclique (et, Pour).

• 1. Nous représentons la combinaison de codes d'origine sous la forme d'un polynôme A t (x). Nous multiplions le polynôme de la combinaison de code d'origine par x z : A t (x) x g. Degré du polynôme générateur gégale à la valeur du chiffre le plus significatif de la combinaison de codes d'origine.
• 2. Nous déterminons les bits de contrôle qui complètent la combinaison d'informations d'origine avec celle autorisée, comme le reste de la division du produit obtenu au paragraphe précédent par la génération

polynôme:

Le reste de la division est noté R(x).

3. Le mot de code finalement autorisé du cyclique

code est défini comme = Et t(x) ? x r + R(x).

Pour déterminer les erreurs dans la combinaison de code reçue, il suffit de la diviser en un polynôme générateur. Si la combinaison acceptée est autorisée, le reste de la division sera égal à zéro. Un reste non nul indique que la combinaison reçue contient des erreurs. Selon le type de résidu (syndrome), dans certains cas, il est également possible de tirer une conclusion sur la nature de l'erreur et sa localisation et de corriger l'erreur.

L'algorithme de détection d'erreur est le suivant.

Soit "-combinaisons d'éléments ( n = k + t).

• 1. Nous révélons le fait de la présence d'une erreur. Nous obtenons le reste en divisant la combinaison acceptée Un n - (x) au polynôme générateur P(x) : A(X)
• --- = Rq(x). Présence d'un solde R0(x)à (L 0 (x) f 0) témoigne P(x)

à propos d'une erreur.

2. Diviser le polynôme résultant # (x) \u003d L„_,(X) 0 Rq (x) sur la génératrice Rg(h): W-1 = R(x), Où R(x)- Solde actuel.

3. Comparer LDx) et R(x). S'ils sont égaux, l'erreur s'est produite dans le bit le plus significatif. Sinon, augmentez le degré du polynôme accepté de x et divisez à nouveau :

4. Comparez le reste résultant avec Rq(x). S'ils sont égaux, l'erreur s'est produite dans le deuxième bit. S'ils ne sont pas égaux, multipliez Wx) x 2 et répétez ces opérations jusqu'à obtenir

R(x) = enfer.

L'erreur sera dans la catégorie correspondant au nombre par lequel le degré est augmenté Wh), plus 1. Par exemple, en cas d'égalité R(x) et LDh)

Le code cyclique c le plus simple permet de détecter les erreurs uniques et les erreurs de multiplicité impaire. Le polynôme générateur de ce code a la forme Parmi les polynômes irréductibles entrant dans la décomposition, ce polynôme est le polynôme du plus petit degré Ainsi, pour un nombre quelconque de bits d'information, un seul bit de contrôle est nécessaire. La valeur de symbole de ce bit assure la parité du nombre de uns dans tout mot de code autorisé. Le code de parité cyclique résultant est capable de détecter non seulement des erreurs sur un seul bit, mais également des erreurs sur n'importe quel nombre impair de bits.

Exemple. Construire un code cyclique pour Puisque le polynôme générateur est un polynôme du 1er degré, le nombre de chiffres de contrôle Donc, Pour construire un code cyclique, on construit une matrice génératrice

Pour construire une matrice supplémentaire, on trouve les restes de la division de la dernière ligne de la matrice transposée unitaire, bourrée de zéros, par le polynôme sélectionné :

Ainsi, la matrice supplémentaire C, k a la forme

Construisons maintenant la matrice génératrice

Les lignes de cette matrice sont les trois premières combinaisons du code. Le reste des combinaisons autorisées peut être obtenu par sommation modulo 2 de toutes les combinaisons possibles de lignes de la matrice. Les combinaisons de code détruites résultantes sont données dans le tableau. 39.

Tableau 39 (voir scan)

D'intérêt bien connu est la considération du code le plus simple suivant formé à l'aide d'un polynôme irréductible du second degré

La vue générale de la matrice génératrice du code cyclique formé par le polynôme diffère par la structure de la matrice supplémentaire à deux colonnes.

Il est facile de voir que, lors de la division par un polynôme générateur donné, les monômes exprimant les chaînes

matrice d'identité (pour trouver une matrice supplémentaire, trois types de résidus sont formés : 11, 01 et 10. Par conséquent, le poids de chaque combinaison du -code résultant sera d'au moins deux. La distance de code minimale entre deux combinaisons est également égal à deux.Mais le code le plus simple avec un contrôle de parité formé par un binôme du premier degré Cependant, la capacité corrective des deux codes n'est pas la même.Le code considéré a une grande redondance et vous permet de détecter non seulement d'éventuelles erreurs de multiplicité impaire, mais aussi toutes les erreurs adjacentes appariées, ainsi que toutes les erreurs séparées par un élément non déformé.

6. Correction des erreurs avec des codes cycliques

Dans la section 3, il a été montré que pour décoder un mot de code correctement reçu, c'est-à-dire pour trouver le mot d'information correspondant, il suffit de diviser le polynôme correspondant au mot de code reçu par le polynôme générateur du code. Cependant, si des erreurs se produisent pendant la transmission, ces erreurs doivent être corrigées pendant le processus de décodage.

Comme les codes cycliques sont linéaires, le processus de détection et de correction d'erreurs est lié à la recherche du syndrome du vecteur reçu. Rappelons que le syndrome vectoriel tu est calculé comme le produit du vecteur et de la matrice de contrôle transposée du code, c'est-à-dire tu es= euh T. Dans le cas d'un code cyclique, le syndrome est égal au reste de la division du polynôme correspondant par le polynôme générateur du code, si la matrice de contrôle est construite d'une certaine manière. Autrement dit, si g(X) est un polynôme de code générateur, alors le syndrome vectoriel tuégal au reste de la division tu(X) sur g(X). S'il n'y avait pas d'erreurs, alors le reste, et donc le syndrome du vecteur reçu, est 0.

Afin de corriger les erreurs, nous devons construire un tableau dans lequel, dans une colonne, il y aura tous les vecteurs d'erreur possibles qui code donné peut corriger, et dans la deuxième colonne - les syndromes qui leur correspondent. La correction d'erreur commune à tous les codes de ligne sera la suivante :

1. Pour le mot reçu, on trouve le syndrome polynomial correspondant au mot reçu.

2. Si le syndrome n'est pas égal à 0, alors par le syndrome obtenu (reste de la division) on trouve dans le tableau le vecteur d'erreur correspondant.

3. Nous corrigeons le mot reçu en ajoutant modulo 2 au vecteur d'erreur calculé.

La première étape, qui s'effectue en multipliant le mot reçu par la matrice de contrôle transposée, est très simple pour les codes cycliques si la matrice H est la matrice de contrôle du code systématique. Dans ce cas, j-ème ligne de la matrice transposée HJ correspond au reste de la division du polynôme xn -1- j par le polynôme générateur du code, et le syndrome est égal au reste de la division du polynôme correspondant au mot reçu par le polynôme générateur du code.

Exemple: Considérons le code (7,1) cyclique généré par le polynôme g(X) = X 6 + X 5 + X 4 + X 3 + X 2 + X+1. Le code se compose de deux mots 0000000 et 1111111 et corrige toutes les combinaisons de 3 erreurs ou moins. Les générateurs sont tous des vecteurs booléens de longueur 7 de poids 0, 1, 2 et 3. La matrice de contrôle est construite à l'aide du quotient ( X+1) de la division X 7 +1 sur X 6 + X 5 + X 4 + X 3 + X 2 + X+1 et ressemble à

Acceptons le mot 11101101 qui correspond au polynôme X 6 + X 5 + X 4 + X 2 + 1. Le reste après avoir divisé ce polynôme par le polynôme de code générateur est X 3 + X. Par vérification directe, on peut s'assurer qu'en multipliant le vecteur tu= 1110101 par matrice transposée HJ, ainsi qu'en multipliant le vecteur 0001010 par HJ on obtient le vecteur 0001010 qui correspond au polynôme X 3 + X. Le vecteur correspondant au polynôme X 3 + X, a un poids de 2, c'est-à-dire est un générateur du coset. En additionnant le vecteur reçu 11101101 avec le générateur 0001010, on obtient le mot de code 1111111, c'est-à-dire que l'erreur sera corrigée.

Pour les codes linéaires, le nombre de syndromes différents est de 2 n - k, Où n-k- nombre de caractères de contrôle. Par conséquent, pour les codes avec une grande longueur de mot de code, c'est-à-dire avec suffisamment un grand nombre vérifier les symboles, la table des syndromes s'avère très volumineuse et il faudra beaucoup de temps pour trouver le vecteur d'erreur. Pour réduire le nombre de lignes dans ce tableau pour les codes cycliques, vous pouvez utiliser la structure mathématique stricte de ces codes. Le théorème principal est le théorème de Megitt, qui établit une connexion entre les décalages cycliques d'un vecteur et leurs restes après division par le polynôme générateur du code.

Théorème 6.1. (Meggit). Laisser s- syndrome vectoriel tu longueur n. Syndrome de décalage vectoriel cyclique tu coïncide avec le syndrome du vecteur correspondant au polynôme xs(X).

Exemple: Considérons le code de Hamming (7,4), qui est le code cyclique généré par le polynôme g(X) = X 3 + X+ 1. Le vecteur binaire 1011000 est un mot de code, puisque le polynôme correspondant X 6 + X 4 + X 3 est divisible par g(X). Supposons que lors de la transmission de ce mot de code il y ait eu une erreur sur le bit correspondant à X 4, et le mot est accepté tu= 1001000. Syndrome s du vecteur reçu est 110, ce qui correspond au polynôme X 2 + X.

Considérons un décalage cyclique 0010001 du vecteur tu. Il correspond au polynôme X 4 + 1. Par vérification directe, on peut vérifier que le reste de la division du polynôme X 4 + 1 par polynôme X 3 + X+ 1 égal X 2 + X+ 1, soit le syndrome du vecteur 0010001 est 111. Le reste de la division du polynôme xs(X) = X 3 + X 2 sur X 3 + X+ 1 est aussi égal X 2 + X + 1.

En utilisant le théorème de Megitt, seuls les syndromes de vecteur d'erreur correspondant aux erreurs dans le bit le plus significatif peuvent être stockés dans la table de syndrome. La procédure de correction d'erreur contient les étapes suivantes :

1. On trouve le syndrome du vecteur reçu en divisant le polynôme correspondant par le polynôme du code générateur. Si le reste de la division contenu dans le registre est 0, alors il n'y a pas eu d'erreurs, et le quotient de la division est le mot d'information requis. Sinon, on compare le reste de la division avec tous les syndromes contenus dans le tableau.

2. Si le reste coïncide avec l'un des syndromes du tableau, alors on ajoute le vecteur d'erreur correspondant au mot reçu, on divise le mot résultant par le polynôme générateur du code; le quotient de la division est le mot d'information souhaité. Si le reste xs(X) ne correspond à aucun des syndromes du tableau, multipliez s(X) sur X et diviser le polynôme xs(X) au polynôme générateur du code.

3. Effectuez l'étape 2 jusqu'à ce que p le reste des étapes ne correspond pas à l'un des syndromes du tableau. Après cela, nous décalons cycliquement le vecteur d'erreur correspondant p fois, ajouter le vecteur résultant au mot reçu, diviser le mot résultant par le polynôme générateur du code ; le quotient de la division est le mot d'information souhaité.

Exemple: Considérons le code de Hamming cyclique (7,4) généré par le polynôme g(X) = X 3 + X+ 1. La table de décodage correspondante avec les syndromes est la suivante.

et supposons qu'une erreur se soit produite dans le mot de code transmis 0001011, c'est-à-dire que le mot 0101011 est reçu, par exemple, auquel correspond le polynôme X 5 + X 3 + X+ 1. Le reste de la division du polynôme X 5 + X 3 + X+ 1 par polynôme de code générateur g(X) = X 3 + X+ 1 égal X 2 + X+ 1, c'est-à-dire que le syndrome du vecteur reçu est différent de 0 et égal à 111. Il n'y a pas un tel syndrome dans la table, et par conséquent, il n'y a pas d'erreurs dans le bit le plus significatif. Multiplication d'un polynôme X 2 + X+ 1, correspondant au syndrome 111, sur X et diviser le polynôme résultant X 3 + X 2 + X sur g(X). Reste de la division d'un polynôme X 3 + X 2 + X sur X 3 + X+ 1 égal X 2 + 1, c'est-à-dire que le syndrome 101, correspondant au reste, correspond au syndrome dans la table de décodage réduite. En conséquence, le générateur 100000 de la classe adjacente est décalé d'un bit vers la gauche et le vecteur reçu 0100000 est ajouté au vecteur reçu 0101011. En conséquence, le mot 0001011 est obtenu, qui est le mot de code transmis, c'est-à-dire l'erreur sera corrigé.

Il est possible de simplifier ce décodeur. En particulier, lorsqu'un mot reçu est mis en rotation, de nombreux modèles d'erreurs corrigibles peuvent se produire plusieurs fois. Si l'un de ces syndromes est supprimé, alors avec le décalage cyclique correspondant, l'erreur sera toujours trouvée. Par conséquent, pour chacune de ces paires, il suffit de mémoriser un seul syndrome.