Fonctionnement d'un ordinateur/Les codes de détection/correction d'erreur
Dans le chapitre précédent, nous avons vu comment l'ordinateur faisait pour coder des nombres. Les nombres en question sont mémorisés dans des mémoires plus ou moins complexes. Les mémoires les plus simples sont des registres, qui mémorisent un nombre. D'autres mémoires plus complexes mémorisent plusieurs nombres, un grand nombre. Et ces mémoires ne sont pas des dispositifs parfaits, elles peuvent subir des corruptions. Les corruptions en question se traduisent le plus souvent par l'inversion d'un bit : un bit censé être à 0 passe à 1, ou inversement. 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 : certains codages des nombres permettent de détecter et corriger ces erreurs. Les codes de détection et de correction d'erreur, qui ajoutent tous des bits de correction/détection d'erreur aux données. Les bits en question sont calculés à partir des données à transmettre/stocker et 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. Ils sont peu utilisées dans les ordinateurs grand public, mais elles sont très importantes dans les domaines demandant des ordinateurs fiables, comme dans l'automobile, l'aviation, le spatial, l'industrie, etc. Et ce chapitre va expliquer ce qu'elles sont, et aussi comment les circuits élaborés permettent de s'en protéger.
Dans ce qui suit, nous parlerons parfois de codes ECC, bien que ce soit un abus de langage : ECC est l'abréviation de Error Correction Code, mais certains de ces codes se contentent de détecter qu'une erreur a eu lieu, sans la corriger. Ceci étant dit, les codes ECC sont utilisés sur les mémoires comme les mémoires RAM, parfois sur les disques durs ou les SSDs, afin d'éviter des corruptions de données. Ils sont aussi utilisés quand on doit transmettre des données, que ce soit sur les bus de communication ou sur un support réseau. Par exemple, les données transmises via internet incorporent un code ECC pour détecter les erreurs de transmission, idem pour les transmissions sur un réseau local.
Le bit de parité
modifierNous allons commercer par aborder le bit de parité/imparité. Le bit de parité est un bit ajouté à la donnée à mémoriser/transmettre. Sa valeur est telle que 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 au 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.
Il est maintenant temps de parler de si un bit de parité est efficace ou non. Que ce soit avec un bit de parité ou d'imparité, environ la moitié des valeurs encodées sont invalides. En effet, si on prend un nombre codé sur N bits, bit de parité, inclut, on pourra encoder 2^n valeurs différentes. La moitié d'entre elle aura un bit de parité à 0, l'autre un bit de parité à 1. Et la moitié aura un nombre de bit à 1 qui soit pair, l'autre un nombre impair. En faisant les compte, seules la moitié des valeurs seront valides. Le diagramme ci-contre montre le cas pour trois bits, avec deux bits de données et un bit de parité.
L'octet/mot de parité et ses variantes
modifierL'octet de parité est une extension de la technique du bit de parité, qui s'applique à plusieurs octets. L'idée de base est de calculer un bit de parité par octet, et c'est plus ou moins ce que fait le mot de parité, mais avec quelques subtilités dans les détails.
La technique s'applique en général sur toute donnée qu'on peut découper en blocs d'une taille fixe. Dans les exemples qui vont suivre, les blocs en question seront des octets, pour simplifier les explications, mais il est parfaitement possible de prendre des blocs plus grands, de plusieurs octets. La méthode fonctionne de la même manière. On parle alors de mot de parité et non d'octet de parité.
Le calcul du mot de parité
modifierLe calcul du mot de parité se calcule en disposant chaque octet l'un au-dessus des autres, le tout donnant un tableau dont les lignes sont des octets. 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é.
- 1100 0010 : nombre ;
- 1000 1000 : nombre ;
- 0100 1010 : nombre ;
- 1001 0000 : nombre ;
- 1000 1001 : nombre ;
- 1001 0001 : nombre ;
- 0100 0001 : nombre ;
- 0110 0101 : nombre ;
- ------------------------------------
- 1010 1100 : octet de parité.
Le calcul de l'octet de parité se fait en utilisant des opérations XOR. Pour rappel, une opération XOR est équivalente à une addition binaire dans laquelle on ne tiendrait pas compte des retenues. L'opération prend deux bits et effectue le calcul suivant :
- 0 0 = 0 ;
- 0 1 = 1 ;
- 1 0 = 1 ;
- 1 1 = 0.
En faisant un XOR entre deux octets, on obtient l'octet de parité des deux octets opérandes. Et cela se généralise à N opérandes : il suffit de faire un XOR entre les opérandes pour obtenir l'octet de parité de ces N opérandes. Il suffit de faire un XOR entre les deux premières opérandes, puis de faire un XOR entre le résultat et la troisième opérande, puis de refaire un XOR entre le nouveau résultat et le quatrième opérande, et ainsi de suite. Le calcul du mot de parité se fait aussi avec des opérations XOR, cela marche au-delà de l'octet.
La récupération des données manquantes/effacées
modifierL'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é. Il suffit de déterminer, pour chaque colonne, quel valeur 0/1 est compatible avec la valeur du bit de parité associé. C'est d'ailleurs pour cette raison que le mot de parité est utilisé 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 retirer le disque dur endommagé et reconstituer ses données.
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 savoir deux choses : faire un XOR entre un nombre et lui-même donne 0, faire un XOR entre une opérande et zéro redonne l'opérande comme résultat. 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. Un exemple sera certainement plus parlant.
Prenons le cas où on calcule l'octet de parité de quatre octets nommés O1, O2, O3 et O4, et notant le résultat . On a alors :
Maintenant, imaginons que l'on veuille retrouver la valeur du second octet O2, qui a été corrompu ou perdu. Dans ce cas, on fait un XOR avec O1, O3 et enfin O4 :
On injecte alors l'équation .
On réorganise les termes :
On se rappelle que A XOR A = 0, ce qui simplifie grandement le tout :
On retrouve bien l'octet manquant.
La combinaison d'un mot de parité avec plusieurs bits de parité
modifierAvec un octet/mot de parité, on peut détecter qu'une erreur a eu lieu, mais aussi récupérer un octet/mot effacé. Mais si un bit est modifié, on ne peut pas corriger l'erreur. En effet, on ne sait pas détecter quel octet a été modifié par l'erreur. Maintenant, ajoutons un bit de parité à chaque octet, en plus de l'octet de parité.
| Octets | Bit de parité de chaque octet | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Octet 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
| Octet 2 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 |
| Octet 3 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| Octet 4 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| Octet de parité | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | |
En faisant cela, on peut détecter qu'un bit a été modifié, mais aussi corriger l'erreur assez simplement. En cas d'erreur, deux bits de parité seront faussés : celui associé à l'octet, celui dans l'octet de parité. On peut alors détecter le bit erroné. Une autre méthode est de regarder les bits de parité associés aux octets, pour détecter l'octet erroné. Reste alors à corriger l'erreur, en supprimant l'octet invalide et en récupérant l'octet initial en utilisant le mot de parité.
| Octets | Bit de parité de chaque octet | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Octet 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
| Octet 2 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 |
| Octet 3 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| Octet 4 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| Octet de parité | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | |
Le nombre de bits de parité total est élevé
modifierLe tout demande d'utiliser beaucoup de bits de parité. Pour N octets, il faut un bit de parité par octet et un octet de parité, ce qui donne N + 8 bits de parité. Pour 64 bits, soit 8 octets, cela fait 16 bits de parité nécessaires, soit 25% de bits en plus. Maintenant, prenons le cas général où on n'utilise pas des octets, mais des mots de M bits, plus longs ou plus courts qu'un octet. Dans ce cas, on a N + M bits de parité.
Notons que la technique peut s'appliquer avec des octets ou des nibbles, si on organise les bits correctement. Par exemple, prenons un nibble (4 bits). On peut l'organiser en un carré de deux bits de côté et ajouter : un bit de parité par colonne, un bit de parité par colonne (le mot de parité). Le tout donne 4 bits de parité, pour 4 bits de données : on double la taille de la donnée. Il est aussi possible de faire pareil avec un octet, l'organisant en deux lignes de 4 bits. Le résultat est de 6 bits de parité, ce qui est un petit peu mieux qu'avec un nibble : on passe à 3/4 de bits de plus.
| 0 | 0 | 1 | 1 | 0 |
|---|---|---|---|---|
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 |
Il est possible de faire la même chose pour des données de plusieurs octets. Pour un nombre de 16 bits, l'idéal est de faire 4 lignes de 4 bits chacune, ce qui fait 8 bits de parité au total. Pour 32 bits, on passe à 12 bits de parité, etc. Au total, voici la quantité de bits de parité nécessaires suivant la longueur de la donnée :
| 4 | 8 | 16 | 32 | 64 | 128 | 256 | ... |
|---|---|---|---|---|---|---|---|
| 4 | 6 | 8 | 12 | 16 | 24 | 32 | ... |
Il existe cependant des techniques plus économes, que nous allons voir dans ce qui suit. Par plus économes, il faut comprendre qu'elles utilisent moins de bits de parité, pour une fiabilité identique, voire meilleure. C'est là un défaut de la technique précédente : elle utilise beaucoup de bits de parités pour pas grand chose.
Les capacités de correction de la technique
modifierNotons que cette solution permet de corriger plus d'une erreur. Dans le pire des cas, on peut détecter et corriger une erreur. Si toutes les erreurs sont toutes dans le même mot/octet, alors on peut récupérer l'octet manquant. Le bit de parité permet de détecter un nombre impair d'erreur, soit 1, 3, 5, 7, ... erreurs. Il faut donc que le nombre d'erreurs dans l'octet soit impair.
| Octets | Bit de parité de chaque octet | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Octet 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
| Octet 2 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 |
| Octet 3 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| Octet 4 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| Octet de parité | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | |
Par contre, si le nombre d'erreurs dans un octet est pair, alors le bit de parité associé à l'octet ne remarque pas l'erreur. On sait sur quelles colonnes sont les erreurs, pas la ligne.
| Octets | Bit de parité de chaque octet | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Octet 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
| Octet 2 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 |
| Octet 3 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| Octet 4 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| Octet de parité | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | |
De même, si les erreurs touchent deux octets, alors on ne peut rien corriger. On peut détecter les erreurs, mais pas les corriger.
| Octets | Bit de parité de chaque octet | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Octet 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
| Octet 2 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 |
| Octet 3 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| Octet 4 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| Octet de parité | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | |
Pour résumer, pour des mots de M bits, on peut corriger entre 1 et M/2 erreurs. Pour un octet, cela permet de détecter 1 erreur, 3/5/7 erreurs si elles ont lieu dans le même octet.
La protection des bits de parité
modifierAvec la méthode précédente, les bits de parité ne sont pas protégés : la moindre corruption des bits de parité fait que la méthode ne marche plus. Pour cela, il y a une solution toute simple : calculer un bit de parité qui tient compte de tous les bits de parité. Ainsi, si un bit de parité est corrompu, alors ce super-bit de parité détecterait l'erreur.
Dans les tableaux précédents, cela revient à ajouter un bit de parité dans la case tout en bas à droite. Le bit de parité calculé à partie des autres bits de parité est en rouge dans le tableau suivant. Il peut se calculer de plusieurs manières. La plus simple est calculer le bit de parité des 6 bits de parité, ceux de l'octet de parité et les autres. En faisant ainsi, on ganratit que tous les bits de parités sont protégés.
| 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 |
Avec cette technique, il faut faire la différence entre les bits de parité primaire, qui calculent la parité de tout ou partie des données, et le bit de parité secondaire, qui est calculé à partie des bits de parité primaire. Généralement, les codes correcteurs/détecteurs d'erreur avec des bits de parité secondaires sont assez peu efficaces, que ce soit en termes de fiabilité ou d'économies de bits. Ils utilisent beaucoup de bits et ne protègent que peu contre les erreurs. De plus, les bits de parité secondaires ne font que repousser le problème : le bit de parité secondaire peut être modifié lui aussi ! Les bits de parité secondaires ne protègent que contre la modification des bits de parité primaire, mais pas de leurs modifications propres. Mais qu'on se rassure : on peut protéger les bits de parité primaire sans recourir à des bits de parité secondaires, avec le codage que nous allons voir dans ce qui suit.
Les codes de Hamming
modifierLe code de Hamming se base sur l'usage de plusieurs bits de parité pour un seul nombre. Chaque bit de parité est calculé à partir d'un sous-ensemble des bits. 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 bit 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é. Mais cela est aussi vrai pour la technique précédente. Un point important est que si un bit de parité est corrompu et change de valeur, les autres bits de parité ne le seront pas et c'est ce qui permettra de détecter l'erreur. Si un bit de données est inversé, plusieurs bits de parité sont touchés, systématiquement. Donc si un seul bit de parité est incompatible avec les bits de données, alors on sait qu'il a été inversé et qu'il est l'erreur. Pas besoin de faire comme avec la technique précédente, avec un mot de parité complété avec des bits de parité, avec un bit de parité secondaire.
.svg)
Le code de Hamming le plus connu est certainement le code 7-4-3, un code de Hamming parmi les plus simples à 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, mais aussi des autres bits de parité. 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.
| 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 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)
É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 codes de Hamming sont généralement plus économes que la technique précédente, avec un mot de parité combiné à plusieurs bits de parité. Par exemple, pour 4 bits, le code de Hamming 7-4-3 n'utilise que 3 bits de parité, contre 4 avec l'autre technique. Pour 7 bits, elle n'en utilise que 4, contre 6. Voici un tableau qui donne combien on peut protéger avec N bits de parité en utilisant un code de Hamming. On voit que les codes de Hamming sont bien plus économes que le mot de parité, tout en étant tout aussi puissant (ou presque).
| Bits de parité | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|
| Données | 1 | 4 | 11 | 26 | 57 | 120 | 247 | 502 |
Les sommes de contrôle
modifierLes 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.
La première 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éaires ou encore les codes polynomiaux cycliques.