Fonctionnement d'un ordinateur/Les circuits de correction d'erreur

Un livre de Wikilivres.
Sauter à la navigation Sauter à la recherche

On a vu précédemment que divers composants doivent communiquer entre eux. Pour cela, ils sont reliés entre eux par des fils, qui permettent de transmettre des bits. Ces ensembles de bits sont appelés des bus. La transmission de données sur ces bus est rarement parfaite : des interférences électromagnétiques peuvent à tout moment causer des modifications des bits transmis. Par exemple, les transmissions de données via un réseau local ou internet ne sont pas parfaites, même si les câbles réseaux sont conçus pour limiter les erreurs. De même, les registres et autres formes de mémoire ne sont pas parfaites et des bits peuvent s'inverser à tout moment. Pour donner un exemple, on peut citer l'incident du 18 mai 2003 dans la petite ville belge de Schaerbeek. Lors d'une élection, la machine à voter électronique enregistra un écart de 4096 voix entre le dépouillement traditionnel et le dépouillement électronique. La faute à un rayon cosmique, qui avait modifié l'état d'un bit de la mémoire de la machine à voter.

Mais qu'on se rassure : il existe des techniques pour détecter et corriger les erreurs de transmission, ou les modifications non-prévues de données. Pour cela, divers codes de détection et de correction d'erreur ont vu le jour. Tous les codes correcteurs et détecteurs d'erreur ajoutent tous des bits aux données de base, ces bits étant appelés des bits de correction/détection d'erreur. Ces bits servent à détecter et éventuellement corriger toute erreur de transmission/stockage. Plus le nombre de bits ajoutés est important, plus la fiabilité des données sera importante. Voyons plus en détail comment ceux-ci font.

Bit de parité[modifier | modifier le wikicode]

Nous allons commercer par aborder le bit de parité/imparité, une technique utilisée dans un grand nombre de circuits électroniques, comme certaines mémoires RAM, ou certains bus (RS232, notamment). Il permet de détecter des corruptions qui touchent un nombre impair de bits. Si un nombre pair de bit est modifié, il sera impossible de détecter l'erreur avec un bit de parité. Il faut noter que ce bit de parité, utilisé seul, n permet pas de localiser le bit corrompu. Ce bit de parité est ajouté aux bits à stocker. Avec ce bit de parité, le nombre stocké (bit de parité inclus) contient toujours un nombre pair de bits à 1. Ainsi, le bit de parité vaut 0 si le nombre contient déjà un nombre pair de 1, et 1 si le nombre de 1 est impair. Si un bit s'inverse, quelle qu'en soit la raison, la parité du nombre total de 1 est modifié : ce nombre deviendra impair si un bit est modifié. Et ce qui est valable avec un bit l'est aussi pour 3, 5, 7, et pour tout nombre impair de bits modifiés. Mais tout change si un nombre pair de bit est modifié : la parité ne changera pas. Ainsi, on peut vérifier si un bit (ou un nombre impair) a été modifié : il suffit de vérifier si le nombre de 1 est impair.

Le bit d'imparité est similaire a bit de parité, si ce n'est que le nombre total de bits doit être impair, et non pair comme avec un bit de parité. Sa valeur est l'inverse du bit de parité du nombre : quand le premier vaut 1, le second vaut 0, et réciproquement. Mais celui-ci n'est pas meilleur que le bit de parité : on retrouve l'impossibilité de détecter une erreur qui corrompt un nombre pair de bits.

Reste que ce bit de parité doit être calculé, avec un circuit dédié qui prend un nombre et renvoie sur sa sortie le bit de parité.

Population count[modifier | modifier le wikicode]

Circuit de calcul de population count

Une première méthode est tout simplement de commencer par calculer le nombre de 1 dans le nombre, avant de calculer sa parité et d'en déduire le bit de parité. Le calcul du nombre de 1 dans un nombre est une opération tellement courante qu'elle porte un nom : on l'appelle la population count, ou encore poids de Hamming. Son calcul est assez simple : si on découpe un nombre en deux parties, la population count du nombre est la somme des population count de chaque partie. Il est possible d'appliquer ce raisonnement de manière récursive sur chaque morceau, jusqu'à réduire chaque morceau 1 bit. Or, la population count d'un bit est égale au bit lui-même, par définition. On en déduit donc comment construire le circuit : il suffit d'utiliser un série d'additionneurs enchainés en arbre.

Un fois la population count du nombre obtenue, il fut en déduire la parité. Ce qui est très simple : la parité d'un nombre est tout simplement égal au bit des unités, le bit de poids faible ! Le nombre est impair si ce bit est à 1, tandis que le nombre est pair si ce bit vaut 0. Cette parité étant égale au bit de parité, on sait calculer le bit de parité : il faut utiliser le circuit de population count, et prendre le bit le plus à droite : ce bit est le bit de parité.

Circuit de calcul direct[modifier | modifier le wikicode]

Il est cependant possible d'obtenir un circuit plus simple, qui utilise nettement moins de portes logiques et qui est plus rapide. Pour comprendre comment créer ce circuit, nous allons commencer avec un cas simple : le calcul à partir d'un nombre de 2 bits. Le circuit étant simple, il suffit d'utiliser les techniques vues précédemment, avec le tables de vérité. En écrivant la table de vérité du circuit, on remarque rapidement que la table de vérité donne la table de vérité d'une porte XOR.

Bit 1 Bit 2 Bit de parité
0 0 0
0 1 1
1 0 1
1 1 0

Pour la suite, nous allons partir d'un nombre de trois bits. On pourrait tenter de créer ce circuit à partir d'une table de vérité, mais nous allons utiliser une autre méthode, qui nous donnera un indice important. Ce nombre de 3 bits est composé d'un nombre de 2 bits auquel on a jouté un troisième bit. L'ajout de ce troisième bit modifie naturellement le bit de parité du nombre précédent. Dans ce qui va suivre, nous allons créer un circuit qui calcule le bit de parité final, à partir : du bit de parité du nombre de 2 bits, et du bit ajouté. On voit alors que la table de vérité est celle d'une porte XOR.

Bit de parité précédent Bit ajouté Bit de parité final
0 0 0
0 1 1
1 0 1
1 1 0

Chose assez intéressante, ce mécanisme fonctionne quelque soit le nombre de bits du nombre auquel on ajoute un bit. Ajouter un bit à un nombre modifie sa parité, celle-ci état alors égale à : bit ajouté XOR bit-parité du nombre. L’explication est relativement simple : ajouter n 0 ne modifie pas le nombre de 1, et donc le bit de parité, tandis qu'ajouter un 1 inverse le bit de parité. Ainsi, on déduit que le bit de parité peut se calculer simplement : il suffit de faire un XOR entre tous les bits du nombre. Effectué naïvement, il suffit d'enchainer des portes XOR les unes à la suite des autres. Mais en réfléchissant, on peut faire autrement. Prenons deux nombres et concaténons-les. On peut déduire facilement le bit de parité de la concaténation à partir des bits de parité de chaque nombre : il suffit de faire un XOR entre ces deux bits de parité. On peut donc utiliser un circuit organisé en arbre, comme pour les multiplieurs.

Circuit de parité

Code de Hamming[modifier | modifier le wikicode]

Le code de Hamming se base sur l'usage de plusieurs bits de parité pour un seul nombre. Chaque bit de parité n'est cependant pas calculé en prenant en compte la totalité des bits du nombre : seul un sous-ensemble de ces bits est utilisé pour calculer chaque bit de parité. Chaque bit de parité a son propre sous-ensemble, tous étant différents, mais pouvant avoir des bits en commun. Le but étant que deux sous-ensembles partagent un bit : si ce bit est modifié, cela modifiera les deux bits de parité associés. Et la modification de ce bits est la seule possibilité pour que ces deux bits soient modifiés en même temps : si ces deux bits de parité sont modifiés en même temps, on sait que le bit partagé a été modifié. Pour résumer, un code de Hamming utilise plusieurs bits de parité, calculés chacun à partir de bits différents, souvent partagés entre bits de parité.

Code 7-4-3[modifier | modifier le wikicode]

Le code de Hamming le plus connu est certainement le code 7-4-3, un code de Hamming parmi les plus simple à comprendre. Celui-ci prend des données sur 4 bits, et leur ajoute 3 bits de parité, ce qui fait en tout 7 bits : c'est de là que vient le nom de 7-4-3 du code. Chaque bit de parité se calcule à partir de 3 bits du nombre. Pour poursuivre, nous allons noter les bits de parité p1, p2 et p3, tandis que les bits de données seront notés d1, d2, d3 et d4. Voici à partir de quels bits de données sont calculés chaque bit de parité :

Hamming(7,4)
Bits de parité incorrects Bit modifié
Les trois bits de parité : p1, p2 et p3 Bit d4
p1 et p2 d1
p2 et p3 d3
p1 et p3 d2

Il faut préciser que toute modification d'un bit de donnée entraine la modification de plusieurs bits de parité. Si un seul bit de parité est incorrect, il est possible que ce bit de parité a été corrompu et que les données sont correctes. Ou alors, il se peut que deux bits de données ont été modifiés, sans qu'on sache lesquels.

Code 8-4-4[modifier | modifier le wikicode]

Le code 8-4-4 est un code 7-4-3 auquel on a ajouté un bit de parité supplémentaire. Celui-ci est calculé à partir de tous les bits, bits de parités ajoutés par le code 7-4-3 inclus. Ainsi, on permet de se prémunir contre une corruption de plusieurs bits de parité.

Hamming(8,4)

Autres[modifier | modifier le wikicode]

Évidemment, il est possible de créer des codes de Hamming sur un nombre plus grand que bits. Le cas le plus classique est le code 11-7-4.

Hamming(11,7)

Sommes de contrôle[modifier | modifier le wikicode]

Les sommes de contrôle sont des techniques de correction d'erreur, où les bits de correction d'erreur sont ajoutés à la suite des données. Les bits de correction d'erreur, ajoutés à la fin du nombre à coder, sont appelés la somme de contrôle. Techniquement, les techniques précédentes font partie des sommes de contrôle au sens large. Mais il existe un sens plus restreint pour le terme de somme de contrôle. Ce terme est souvent utilisé pour des techniques telle l'addition modulaire, le CRC, et quelques autres. Toutes ont en commun de traiter les données à coder comme un gros nombre entier, sur lequel on effectue des opérations arithmétiques pour calculer les bits de correction d'erreur. La seule différence est que l'arithmétique utilisée est quelque peu différente de l'arithmétique binaire usuelle. Dans les calculs de CRC, on utilise une arithmétique où les retenues ne sont pas propagées. Le calcul des additions et soustractions est alors extrêmement simple : elles se résument à des XOR.

Mot de parité[modifier | modifier le wikicode]

La technique de l'addition modulaire est de loin la plus simple. Elle découpe les données à coder en plusieurs blocs de taille fixe. Ce faisant, elle additionne tous les blocs entre eux, en utilisant les règles de l'arithmétique modulaire (souvenez-vous du chapitre sur le complémente à deux). La somme de tous les blocs correspond à la somme de contrôle. La vérification d'une erreur de transmission est assez simple : on calcule la somme de contrôle à partir des données transmises et on vérifie qu'elle est identique à celle envoyée avec les données. Si ce n'est pas le cas, il y a eu une erreur de transmission.

Le résultat de cette opération est ce qu'on appelle un mot de parité, une extension du bit de parité pour plusieurs nombres. On peut le voir comme l'équivalent d'un bit de parité pour un paquet de nombre. Cela sert sur les bus de communication entre composants, sur lesquels on peut envoyer plusieurs nombres à la suite, ou dans les mémoires qui stockent plusieurs nombres les uns à côté des autres. Il faut noter que le bit de parité peut être vu comme une spécialisation de la technique du mot de parité, où les blocs font tous 1 bit. Le calcul du mot de parité se calcule en disposant chaque nombre/bloc l'un au-dessus des autres, le tout donnant un tableau dont les lignes sont des nombres Le mot de parité se calcul en calculant le bit de parité de chaque colonne du tableau, et en le plaçant en bas de la colonne. Le résultat obtenu sur la dernière ligne est un octet de parité. Pour comprendre le principe, supposons que nous disposions de 8 entiers de 8 bits. Voici comment effectuer le calcul du mot de parité :

  • 11000010 : nombre ;
  • 10001000 : nombre ;
  • 01001010 : nombre ;
  • 10010000 : nombre ;
  • 10001001 : nombre ;
  • 10010001 : nombre ;
  • 01000001 : nombre ;
  • 01100101 : nombre ;
  • ------------------------------------
  • 10101100 : mot de parité.

L'avantage de cette technique est qu'elle permet de reconstituer un octet manquant. C'est cette technique qui est utilisée sur les disques durs montés en RAID 3, 5 6, et autres : si un disque dur ne fonctionne plus, on peut quand même reconstituer les données du disque dur manquant. Retrouver la donnée manquante est assez simple : il faut calculer la parité des nombres restants, et de faire un XOR avec le mot de parité. Pour comprendre pourquoi cela fonctionne, il faut se souvenir que faire un XOR entre un nombre et lui-même donne 0. De plus, le mot de parité est égal au XOR de tous les nombres. Si on XOR un nombre avec le mot de parité, cela va annuler la présence de ce nombre (son XOR) dans le mot de parité : le résultat correspondra au mot de parité des nombres, nombre xoré exclu. Ce faisant, en faisant un XOR avec tous les nombres connus, ceux-ci disparaitrons du mot de parité, ne laissant que le nombre manquant.

On a vu que le bit de parité ne permet pas de savoir quel bit d'un nombre a été modifié. Mais il existe une solution pour que cela devienne possible, dans le cas où plusieurs nombres sont envoyés. Si on suppose qu'un seul bit a été modifié lors de la transmission du paquet de nombre, on peut détecter quel bit exact a été modifié. Pour cela, il suffit de coupler un mot de parité avec plusieurs bits de parité, un par nombre. Détecter l bit modifié est simple. Pour comprendre comment, il faut se souvenir que les nombres sont organisés en tableau, avec un nombre par ligne. Le bit modifié est situé à l'intersection d'une ligne et d'une colonne. Sa modification entraînera la modification du bit de parité de la ligne et de la colonne qui correspondent, respectivement un bit de parité sur la verticale, et un bit de parité dans le mot de parité. Les deux bits fautifs indiquent alors respectivement la ligne et la colonne fautive, le bit erroné est situé à l'intersection. Cette technique peut s'adapter non pas avec une disposition en lignes et colonnes, mais aussi avec des dimensions en plus où les nombres sont disposés en cube, en hyper-cube, etc.

Contrôle de Redondance Cyclique[modifier | modifier le wikicode]

Une autre méthode consiste à prendre les données à envoyer, à les diviser par un nombre entier arbitraire, et à utiliser le reste de la division euclidienne comme somme de contrôle. Cette méthode, qui n'a pas de nom, est similaire à celle utilisée dans les Codes de Redondance Cyclique. Effectuer une division dans l'arithmétique utilisée est alors très simple : il suffit d’effectuer la division comme en décimal, en remplaçant les soustractions par des XOR. C'est ainsi que sont calculés les CRC : on divise les données par un diviseur standardisé pour chaque CRC, dans l'arithmétique mentionnée précédemment, et on utilise le reste de la division comme somme de contrôle. L'avantage de ces CRC est qu'ils sont faciles à calculer en matériel. Le remplacement des soustractions entières par des XOR facilite fortement les calculs et leur implémentation. Les circuits de calcul de CRC sont ainsi très simples à concevoir : ce sont souvent de simples registres à décalage à rétroaction linéaire améliorés.