Codes correcteurs d’erreurs

Codes correcteurs d’erreurs

algebra

Petite fiche résumant ce qu’il faut savoir sur les codes correcteurs d’erreurs pour l’agrégation.

Pour tout le document, on fixe un nombre premier, et deux entiers non nuls et .

Théorie générale

Il s’agit, dans un premier temps, de choisir le corps en fonction de l’information que l’on cherche à coder. Par exemple, le choix de semble le plus naturel pour représenter la manière dont est stockée l’information dans un ordinateur, tandis que serait plus approprié vis-à-vis de l’ADN.

Définition 1. On appelle mot un vecteur à coefficients dans .

Après avoir choisi comme alphabet, il reste à choisir l’ensemble des mots du code. Plus précisément :

Définition 2. On appelle code correcteur (ou simplement code) de taille un sous-ensemble de .

Remarque 3. Le code correcteur est l’ensemble des mots que l’on est en mesure de produire par codage : il ne peut pas occuper l’espace entier, sinon tous les mots seraient valides !

Si l’on reçoit un mot qui n’est pas dans le code, on est donc sûr qu’il y a eu une erreur de transmission. L’opération de codage ajoute une information pour distinguer les mots valides des autres. C’est uniquement lors du décodage que l’on va pouvoir réparer une ou plusieurs erreurs.

Exemple 4 (Bit de parité). Dans un ordinateur, chaque mot est coupé en sous-mots de bits, c’est-à-dire, en vecteurs formés de éléments de . Lors du codage de chaque vecteur, on ajoute un bit dit de parité.

Ainsi, soit une suite de bits. On calcule : Si le nombre de bits égaux à est pair, , sinon, . Ainsi, le mot a toujours un nombre de bits égaux à qui est pair. On peut alors détecter, à la lecteur d’un mot, si une erreur a eu lieu lors de sa réception : il y aura un nombre impair de bits égaux à .

Dans le cadre d’un mot de taille , on peut représenter la situation par un cube. Sur cette illustration, nous voyons en turquoise l’ensemble des mots du code. Une unique erreur correspond à un déplacement sur le cube le long d’une arête. Dans ce cas, le récepteur reçoit un point noir dont la somme de toutes les lettres est un entier impair. En revanche, un tel point est toujours à proximité de trois points turquoise, le récepteur ne dispose donc d’aucun moyen pour une correction automatique.

tikzpicture-1
Mots de de longueur avec un bit de parité.

Ainsi, ce code, a deux inconvénients :

  • il est impossible de détecter où l’erreur a eu lieu, et donc, de la corriger ;

  • si deux erreurs ont lieu, il est impossible de les détecter (car alors, le nombre de bits égaux à reste pair).

L’exemple précédent montre bien qu’il est nécessaire de pouvoir évaluer les propriétés qualitatives d’un code. Ainsi :

Définition 5. Soient et deux mots de de taille .

  • Le poids de , noté , est le nombre de coefficients non nuls dans .

  • La distance de Hamming entre et , notée est définie par

Proposition 6.

  1. correspond aux nombres de coefficients qui diffèrent entre et .

  2. est une distance sur .

Démonstration.

  1. Soient . Par définition, est égal au nombre de coefficients non nuls de , soit au nombre de coefficients qui diffèrent entre et .

  2. Soient .

    1. On a par positivité de et si et seulement s’il y a coefficients qui diffèrent entre et ie. .

    2. Le nombre de coefficients non nuls de est égal au nombre de coefficients non nuls de . Donc,

    3. On note , et les coefficients respectifs de , et . Soient , et . On a, En passant au complémentaire, D’où,

 ◻

La distance permet de quantifier la notion de mot le plus proche. Avec elle, on peut donner la définition suivante.

Définition 7. Soit un code. On appelle distance minimale de , l’entier suivant :

Plus la distance minimale d’un code est grande, plus les mots vont être espacés les uns des autres. En ne prenant en compte que la plus petite des distances, on va pouvoir s’assurer que le code est en mesure de corriger une erreur sous certaines conditions.

Définition 8. Un code est dit -correcteur s’il peut corriger au maximum erreurs.

Remarque 9. Cela signifie que, si désigne un mot codé et le mot réceptionné, alors on est en mesure de retrouver le mot original si .

Proposition 10. Soit un code de distance minimale . On suppose . Alors, est -correcteur.

Démonstration. Soient deux mots distincts du code. Alors, les boules et sont disjointes. Ainsi, soient un mot codé émis et le mot réceptionné. Si , alors et n’appartient pas à une autre boule de centre un mot du code et de rayon inférieur ou égal à : on peut corriger . ◻

Remarque 11. Notons qu’alors

Codes linéaires

Nous allons maintenant observer ce qui se passe en imposant une structure sur le code.

Définition 12. Un code linéaire de taille et de dimension sur est un sous-espace vectoriel de dimension de .

Soit alors une base de . On considère une matrice dont les colonnes sont les vecteurs de cette base. On dit que est une matrice génératrice de .

Proposition 13. Soit un code linéaire de taille et de dimension sur . Soit une matrice génératrice de . On a,

Démonstration. Soit une base de . On considère la matrice génératrice de associée, que l’on note .

Alors, , en notant le -ième vecteur de la base canonique de , on a . Donc, par linéarité, . Et comme , on a bien l’inclusion réciproque. ◻

Remarque 14. Dans le cadre d’un code linéaire , la distance minimale s’exprime alors

Proposition 15. Soit un code linéaire de taille et de dimension sur . Il existe une matrice telle que

Démonstration. On considère le produit scalaire canonique sur : et l’orthogonal de pour ce produit scalaire. est un sous-espace vectoriel de de dimension , dont on note une base. Définissons comme étant la matrice dont la -ième ligne est pour tout . Soit . Alors, on a  ◻

Définition 16. En reprenant les notations précédentes, est appelée matrice de contrôle du code .

Il s’agit là d’un critère extrêmement pratique pour permettre de tester l’appartenance d’un mot au code.

Exemple 17 (Code de répétition). On se place sur le corps . L’idée est d’envoyer plusieurs copies de chaque bit à être transmis. Ainsi, sur , le code est composé de deux mots : Des matrices génératrices et de contrôle sont données par On corrige en remplaçant un message reçu reconnu erroné par le message émis potentiel le plus proche (c’est-à-dire avec le moins de bits différents). Par conséquent, le codage par répétition permet de corriger correctement une erreur portant sur un seul bit mais ne permet pas de corriger correctement une erreur portant sur deux bits.

Proposition 18 (Borne de Singleton). Soit un code linéaire de taille , de dimension et de distance minimale sur . Alors,

Démonstration. Pour prouver ceci, exhibons un mot de de poids inférieur ou égal à (car alors, on aura ). Soit , le sous-espace vectoriel de constitué des vecteurs dont les dernières coordonnées sont nulles. C’est un espace de dimension , et la formule de Grassmann donne : Il existe donc dans , et ce mot a un poids inférieur ou égal à . ◻

Ce dernier résultat illustre le choix à faire entre capacité de correction, et redondance de l’information transmise.

Terminons cette sous-section par la méthode pratique permettant de corriger un mot reçu. Pour cela, on a besoin d’une dernière définition.

Définition 19. Soit un code linéaire de taille et de dimension sur . Soit une matrice de contrôle de . On appelle syndrome d’un mot le vecteur .

Imaginons maintenant que l’on réceptionne un mot . On calcule son syndrome via une matrice de contrôle et on a deux cas :

  • Le syndrome est nul : : on considère alors qu’il n’y a pas d’erreur.

  • Le syndrome est non nul : il existe (le mot d’origine) et (l’erreur) tels que . Alors, En notant le -ième vecteur colonne de et la -ième coordonnée de : On en déduit en résolvant le système . Il est possible que ce système n’ait pas de solution, s’il y a trop d’erreurs par exemple. S’il y a une solution, elle est unique et on peut effectuer la correction : .

Codes cycliques

Nous avons vu dans la section précédente qu’imposer une structure d’espace vectoriel sur un code rendait le codage de l’information beaucoup plus simple via les matrices génératrices. Renforçons davantage la structure de notre code et observons les conséquences.

Définition 20. Soit un code linéaire de taille et de dimension sur . est dit cyclique s’il est stable par décalage circulaire, ie.

Notons maintenant

Lemme 21. est un isomorphisme d’espaces vectoriels.

Démonstration. On sait (par la théorie des corps), que est un espace vectoriel sur de dimension . En effet, en notant la classe de dans :

  • La famille est libre. Soient tels que Alors, le polynôme est dans l’idéal , mais est de degré strictement inférieur à . Donc ses coefficients sont nuls : on a , .

  • La famille est génératrice. Soit . On fait la division euclidienne de par dans : En repassant modulo , on a bien de degré inférieur à , donc appartenant à l’espace vectoriel engendré par .

Ainsi, et sont isomorphes en tant qu’espaces vectoriels de même dimension sur . L’application étant surjective et linéaire (par définition), on a bien un isomorphisme. ◻

À l’aide de cet isomorphisme, nous allons pouvoir identifier un code linéaire de taille sur à un sous-espace vectoriel de . Ce raisonnement va nous permettre de caractériser les codes cycliques.

Proposition 22. Soit un code linéaire de taille . Alors, est cyclique si et seulement si est un idéal de .

Démonstration. Soient et . Remarquons que,

  • Supposons cyclique. Alors, par ce qu’on vient de dire, est stable par multiplication par . Mais est un sous-espace vectoriel de , donc il est aussi stable par addition et par multiplication par un scalaire. Finalement, est bien un idéal de .

  • Supposons idéal de . Alors, est stable par multiplication par . Donc par le raisonnement précédent, est clairement cyclique.

 ◻

Nous arrivons au théorème suivant qui nous indique que, pour fabriquer un code cyclique de dimension , il suffit de savoir factoriser dans (ce qui peut se faire par l’algorithme de Berlekamp).

Théorème 23 (Structure des codes cycliques). Soit .

  1. Soit un diviseur unitaire de dans . Soit le mot correspondant à . Alors, en notant l’application de permutation circulaire, forme un code cyclique de dimension .

  2. Réciproquement, si est un code cyclique de dimension sur , il existe un polynôme diviseur de vérifiant pour .

Démonstration.

  1. Clairement, est un sous-espace vectoriel de de dimension : c’est un code linéaire. Reste à montrer qu’il est cyclique. Soit un mot de . Il s’agit de montrer que . Or, et, d’après la base choisie pour , . Reste à montrer que . On a, Or, est de degré , unitaire et divise , donc il existe unitaire de degré tel que . D’où, Comme est de degré au plus , on peut l’écrire . Ainsi, D’où : on a bien ce qu’on voulait.

  2. Soient un code cyclique de dimension sur et la projection de sur le quotient . Alors, d’après la Proposition 22, est un idéal de , donc est un idéal de , qui est principal par principalité de . On peut noter le générateur unitaire. Montrons que .

    est un idéal de , donc , donc : il existe tel que . On a bien .

    Il s’agit maintenant de montrer que est bien de degré . Notons . Soit On a, et .

    Soit . Par définition de , il existe tel que . On effectue la division euclidienne de par : d’où : Ainsi, on a . On a alors montré que . Or, et est un sous-espace vectoriel de de dimension . Par isomorphisme, on a donc : ce qui permet de conclure que .

    Pour terminer, on écrit et on considère . Comme est un idéal de , Et est une famille libre de cardinal , donc est bien une base de .

 ◻

Étude d’un code de Hamming

D’après Wikipédia, un code de Hamming est un code correcteur linéaire. Il permet la détection et la correction automatique d’une erreur si elle ne porte que sur une lettre du message. Un code de Hamming est parfait : pour une longueur de code donnée il n’existe pas d’autre code plus compact ayant la même capacité de correction. En ce sens son rendement est maximal. Il existe une famille de codes de Hamming ; le plus célèbre et le plus simple après le code de répétition binaire de dimension et de longueur est sans doute le code binaire de longueur , de dimension et de distance minimale : ça tombe bien, il est au programme de l’option C de modélisation !

Définition 24. Le code Hamming de longueur permet de coder un mot de longueur en un mot de code de longueur . C’est un code linéaire, dont une matrice génératrice est

Exemple 25. On souhaite coder le mot . On calcule : Le mot codé est donc .

On peut en fait expliciter les mots de ce code : il y en a .

Mot Mot codé Poids Mot Mot codé Poids

Proposition 26.

  1. a une distance minimale de .

  2. est -correcteur.

  3. est une matrice de contrôle de ce code.

Démonstration.

  1. Le minimum des poids est bien d’après le tableau précédent.

  2. D’après la Remarque 11, la capacité de correction du code est égale à

  3. Soit . On note la base de associée à . Alors, , et . Donc est une base de , ce qui mène au résultat voulu.

 ◻

Proposition 27. Le code de Hamming est cyclique, engendré par .

Démonstration. Les vecteurs colonnes de la matrice se déduisent les uns des autres par permutation circulaire. Par conséquent, l’ensemble du code est invariant par permutation circulaire : est bien cyclique. Et le polynôme correspond au mot qui est le premier vecteur colonne de la matrice . ◻

En pratique, le code de Hamming se manipule de la manière suivante :

  1. On a un mot . On calcule et on envoie .

  2. Le receveur reçoit . Il calcule le syndrome . Si est nul, il pose . Sinon, il pose où pour , .

  3. Le receveur résout .