Fonctionnement d'un ordinateur/Les circuits de correction d'erreur
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. Ils sont calculés à partir des données à transmettre/stocker. 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.
Il existe plusieurs types de codes correcteurs d'erreurs, mais on peut les classer en deux types : les codes par blocs et les codes continus. Dans les premiers, les bits de correction/détection d'erreur sont ajoutés à la fin des données à transmettre. Pour les seconds, les bits de correction/détection d'erreur sont insérés directement dans les données à transmettre, à des emplacements bien précis. Les premiers sont conceptuellement plus simples, ce qui les rend plus simples à comprendre. Aussi, nous allons nous limiter à aux codes par blocs classiques dans ce chapitre.
Le bit de parité modifier
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). Le 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. Il permet de détecter des corruptions qui touchent un nombre impair de bits. Si un nombre pair de bit est modifié, il est impossible de détecter l'erreur avec un bit de parité. 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. Il faut noter que le bit de parité, utilisé seul, ne permet pas de localiser le bit corrompu.
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é.
Le calcul via le poids de Hamming modifier
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 une série d'additionneurs enchainés en arbre.
Un fois la population count du nombre obtenue, il faut 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é.
Les générateurs de parité modifier
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 quel que 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é.
Avec cette logique, on peut créer un générateur de parité sériel, un circuit qui calcule le bit de parité bit par bit. Celui-ci est composé d'un registre à décalage, d'une bascule et d'une porte XOR. Le registre à décalage est initialisé avec le nombre dont on veut calculer la parité. La bascule est initialisée à zéro et son but est de conserver le bit de parité calculé à chaque étape. À chaque cycle, un bit de ce nombre sort du registre à décalage et est envoyé en entrée de la porte XOR. La porte XOR fait un XOR entre ce bit et le bit de parité stocké dans la bascule, ce qui donne un bit de parité temporaire. Ce dernier est mémorisé dans la bascule pour être utilisé au prochain cycle.
Une autre manière de faire, qui ne se base pas sur un registre à décalage, consiste simplement à faire un XOR entre tous les bits du nombre en enchaînant des portes XOR. Effectué naïvement, il suffit d’enchaîner 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. Le résultat est appelé un générateur de parité parallèle.
Les codes de Hamming modifier
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é.
Le code 7-4-3 modifier
.svg)
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é :
| 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 entraîne 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.
Le code 8-4-4 modifier
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é.
.svg)
Autres modifier
É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.
.svg)
Les sommes de contrôle modifier
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. 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.
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. Il est souvent utilisé pour regrouper 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, ce qui fait que les additions et soustractions se résument à des XOR.
Le mot de parité modifier
La technique de l'addition modulaire est de loin la plus simple. On peut la voir comme une extension du bit de parité pour plusieurs nombres, ce qui explique que la somme de contrôle est appelée un mot de parité. Elle découpe les données à coder en plusieurs blocs de taille fixe, la somme XOR de tous les blocs donnant la somme de contrôle. 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 calcule 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é.
- 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.
L'avantage de cette technique est qu'elle permet de reconstituer une donnée manquante. Par exemple, dans l'exemple précédent, si une ligne du calcul disparaissait, on pourrait la retrouver à partir du mot de parité. Pour cela, il faut faire faire XOR entre les données non-manquantes et 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 disparaîtront 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 a été modifié. Mais il existe des solutions dans certains cas particuliers. Si on suppose qu'un seul bit a été modifié lors de la transmission des données, on peut localiser le bit modifié. Pour cela, il suffit de coupler un mot de parité avec plusieurs bits de parité, un par nombre. Détecter le 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.
Le mot de parité est utilisé sur les bus de communication entre composants, sur lesquels on peut envoyer plusieurs nombres à la suite. Il est aussi utilisé dans certaines mémoires qui stockent plusieurs nombres les uns à côté des autres. Mais surtout, c'est cette technique qui est utilisée sur les disques durs montés en RAID 3, 5 6, et autres. Grâce à elle, si un disque dur ne fonctionne plus, on peut quand même reconstituer les données du disque dur manquant.
Le contrôle de Redondance Cyclique modifier
Une autre méthode consiste à diviser les données à envoyer 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. Avec cette méthode, on remplace la division par une opération légèrement différente. L'idée est de faire comme une division, mais dont on aurait remplacé les soustractions par des opérations XOR. Nous appellerons cette opération une pseudo-division dans ce qui suit. Une pseudo-division donne un quotient et un reste, comme le ferait une division normale. Le calcul d'un CRC pseudo-divise les données par un diviseur et on utilise le reste de la pseudo-division comme somme de contrôle. Il existe plusieurs CRC différents et ils se distinguent surtout par le diviseur utilisé, qui est standardisé pour chaque CRC.
La technique peut sembler bizarre, mais cela marche. Cependant, expliquer pourquoi demanderait d'utiliser des concepts mathématiques de haute volée qui n'ont pas leur place dans ce cours, comme la division polynomiale, les codes linéaire ou encore les codes polynomiaux cycliques. Si nous devons omettre ces développements, nous pouvons cependant dire que les CRC sont faciles à calculer en matériel. 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. Le registre en question a la même taille que le mot dont on veut vérifier l'intégrité. Il suffit d'insérer le mot à contrôler bit par bit dans ce registre, et le CRC est calculé au fil de l'eau, le résultat étant obtenu une fois que le mot est totalement inséré dans le registre.
Le registre dépend du CRC à calculer, chaque CRC ayant son propre registre.
