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

Dans les chapitres précédents, nous avons supposé que les circuits font leur travail et ne commettent pas d'erreurs. Dans les faits, c'est une bonne approximation : il est rare qu'un circuit électronique dysfonctionne soudainement, sauf s'il est assez âgé et qu'il a commencé à se détériorer. Et même quand il y a une erreur, elle passe généralement inaperçue et l'ordinateur continue de fonctionner normalement. Cependant, cela ne signifie pas que les erreurs n'existent pas, et elles sont nombreuses.

Les erreurs 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 : il existe des techniques pour détecter et corriger ces erreurs. Elles nécessitent toutes l'ajout de matériel, et ce sont ces circuits que nous allons voir ici. Elles 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.

La cause des erreurs et défauts d'un circuit électronique

Les erreurs peuvent provenir d'un défaut électrique, d'un fil coupé, d'un transistor défaillant, ou tout autre raison qui cause une erreur permanente. Généralement, elles proviennent de l'usure d'un circuit électronique, de son vieillissement. Mais d'autres erreurs sont des erreurs temporaires provenant de phénomènes physiques externes au circuit. Il faut donc distinguer les erreurs permanentes des erreurs transitoires. Les premières perdurent après qu'elles apparaissent, ce sont des défauts permanents, qu'on ne peut pas corriger. Les secondes surviennent brutalement et cessent peu après leur apparition.

Le vieillissement des circuits électroniques

Interconnexion métallique attaquée par éléctro-migration

Les circuits électroniques vieillissent. Les transistors vieillissent généralement assez bien, ce sont surtout les interconnexions métalliques entre transistors qui s'usent. La raison est que les interconnexions sont parcourues par des courants électriques assez forts, qui attaquent le métal. Quand un métal est parcourt par du courant, les électrons s'entrechoquent avec les atomes du métal, et ces derniers se déplacent progressivement : c'est le phénomène d'électro-migration. Des défauts apparaissent dans le métal : un atome manquant par-ci par-là, puis des défauts plan, des trous dans le métal, etc. Après un certain temps, ces défauts s'accumulent, au point que les interconnexions peuvent se couper en deux : le fil métallique est cassé.

L'électro-migration est d'autant plus forte que le courant est élevé, cela n'a rien d'étonnant. Mais le processus dépend aussi fortement de la température. En première approximation, la durée de vue d'un circuit électronique se calcule approximativement avec cette équation, appelée l'équation de Black :

${\text{durée de vie d'un circuit}}\propto {\frac {1}{I^{n}}}\times \exp {\left({\frac {A}{k_{B}T}}\right)}$

En clair, elle est d'autant plus faible que le courant est élevé, et que la température l'est aussi. La dépendance au courant est une loi de puissance, elle est donc plus faible que celle avec la température qui est exponentielle. Réduire la température de fonctionnement d'un ordinateur augmente donc drastiquement sa durée de vie. Et vu que plus un ordinateur est utilisé, plus il chauffe, cela explique pourquoi les ordinateurs beaucoup utilisés pour jouer à des jeux vidéos ne durent pas autant que ceux utilisés seulement pour de la bureautique.

Un autre facteur est la taille des interconnexions métalliques, en largeur. Plus un fil est épais, large, plus il sera difficile à couper à grand coup d'électro-migration. Et plus les processeurs se miniaturisent plus ces interconnexions sont petites, fines, faciles à casser. Autant cela ne posait pas de problème quand les interconnexions faisaient quelques centaines de micro-mètres, autant les interconnexions modernes de quelques microns se cassent rapidement.

Les erreurs temporaires

D'autres erreurs sont cependant temporaires et ont des origines totalement différentes. La plupart proviennent de rayons cosmiques, de perturbations électromagnétiques, de radiations proches, peu importe. Les causes les plus communes sont les rayons cosmiques, des particules à haute énergie produites dans la haute atmosphère et qui traversent celle-ci à haute vitesse. Il arrive qu'elles soient interceptées par le semi-conducteur d'un transistor, ce qui le fait dysfonctionner temporairement. La seconde raison est celle des rayons alpha, provenant de la radioactivité naturelle qu'on trouve un peu partout. Et, ironie du sort, ces rayons alpha proviennent souvent du métal présent dans la puce elle-même !

La cause la plus commune est cependant la température. Plus un processeur ou une mémoire chauffe, moins ses transistors sont fiables. Les erreurs sont d'autant plus communes que la température est élevée. Et une autre raison est que la résistance des fils métalliques augmente avec la température : si un processeur chauffe trop, certains fils deviennent tellement résistifs qu'ils ne font plus passer le courant, ce qui fait que tout se passe comme si le fil était coupé ! C'est pour cela que les ordinateurs tendent à planter quand le processeur ou la mémoire chauffent trop, et vous en avez certainement déjà fait l'expérience. Les erreurs en question peuvent survenir à trois endroits différents : dans les circuits combinatoires, dans les mémoires et registres, lors de la transmission des données dans les interconnexions.

La redondance des circuits

Les erreurs peuvent survenir à des endroits très différents dans un ordinateur : dans le processeur, sa mémoire, dans un périphérique, dans le BIOS, etc. Dans ce qui va suivre, nous allons distinguer trois localisations : dans les circuits combinatoires, dans les mémoires et registres, dans les interconnexions entre circuits. Nous allons d'abord voir les techniques utilisées sur les circuits combinatoires, et nous prendrons l'exemple d'une unité de calcul pour simplifier les explications. Puis, nous allons voir ce qu'il en est pour les mémoires, registres, et bus de transmission. La raison est que les techniques utilisées pour les ALU et les mémoires/bus sont différentes en pratique, pour des raisons que nous expliquerons.

Pour les circuits combinatoires, les solutions sont diverses, mais on peut les classer en deux types : la redondance temporelle, et la redondance physique.

La redondance temporelle consiste à exécuter un calcul plusieurs fois, pour vérifier si le résultat est le même à chaque exécution. Typiquement, on exécute la même opération deux fois dans l'ALU, et on ne fait rien si les deux résultats sont identiques. Mais si les deux résultats sont différents, alors une erreur a eu lieu. Pour corriger l'erreur, l'idée est d'exécuter le calcul une troisième fois, voire plus, et de garder le résultat majoritaire.

La redondance physique, beaucoup plus simple, duplique le circuit et fait fonctionner les circuits dupliqués en parallèle, en leur envoyant les mêmes données au même moment. Les deux circuits sont censés fournir le même résultat si tout va bien. Mais en cas d'erreur de fonctionnement, les deux circuits fourniront un résultat différent, d'au moins un bit. Par exemple, on peut imaginer ce que cela donnerait avec des unités de calcul redondantes : toutes les unités de calcul recevraient les opérandes en même temps, feraient leurs calculs indépendamment les unes des autres, et fourniraient leur résultat à un système qui corrigerait d'éventuelles erreurs de calcul ou pannes.

Les deux solutions correspondent à des compromis différents. La redondance temporelle double ou triple les temps de calcul, mais ne duplique pas les circuits. À l'inverse, la redondance physique ne change pas beaucoup les temps de calcul, mais duplique les circuits et augmente le nombre de portes logiques/transistors utilisées. La redondance physique est plus utilisée que la redondance temporelle pour une raison simple : elle capture plus d'erreurs. Une erreur permanente, comme un circuit défectueux, est détectée par la redondance physique, mais pas par la redondance temporelle. La redondance temporelle ne détecte que les erreurs transitoires, celles liées à la température et/ou à des radiations.

La détection d'erreur par comparaison de deux résultats

La méthode de détection d'erreur la plus simple consiste à effectuer un calcul deux fois, et à vérifier que les deux opérations donnent le même résultat. Si les deux exécutions du calcul donnent le même résultat, alors on considère qu'il n'y a pas eu d'erreurs. Par contre, si les deux résultats sont différents, alors on sait qu'une erreur a eu lieu. Par contre, une fois l'erreur détectée, on ne peut pas la corriger. Pour connaitre le bon résultat, on est obligé de refaire les calculs, ou d'utiliser d'autres méthodes pour corriger l'erreur.

Pour faire les deux calculs, on peut utiliser la redondance temporelle ou la redondance physique. La méthode la plus simple est la redondance physique, qui se contente de dupliquer le circuit, et d'ajouter un comparateur qui vérifie si les deux circuits donnent le même résultat. Le premier processeur à utiliser cette méthode était l'EDVAC, dans les années 1950. Il comprenait deux unités de calcul, et continuait d’exécuter son programme tant que les deux unités de calcul donnaient des résultats identiques. En cas de non-agrément entre les deux unités de calcul, le processeur ré-exécutait l'instruction fautive.

Il faut noter que les deux unités de calcul ne sont pas forcément identiques. Un cas classique est celui des circuits multiplieurs : le multiplieur redondant ne fournit par le résultat complet, mais un résultat partiel. Prenons la multiplication A * B = C, la même multiplication mais modulo N fonctionnera aussi : (A mod N) * (B mod N) = (C mod N). L'idée est donc que le second multiplieur fait le calcul modulo N, N choisit de manière à réduire fortement le cout en circuits. Évidemment, cette solution n'est pas aussi puissante que simplement dupliquer le multiplieur : un calcul erroné peut coller parfaitement au résultat mod N adéquat du second multiplieur. Plus N est petit, plus la chance que cela arrive est forte.

Duplication avec comparaison

Une autre solution utilise la redondance temporelle. Le calcul est fait deux fois de suite par la même ALU, on met en attente les deux résultats dans deux registres, et on les compare. Là encore, il y a un coût en circuits : il faut ajouter un comparateur et des registres. Elle n'est pas très utilisée, car son compromis en circuits et en performance ne vaut pas le coup. On double le temps de calcul, mais le coût en circuits n'est pas négligeable. On ajoute une seconde ALU d'un côté, deux registres de l'autre, le cout en circuits est significatif dans les deux solutions.

La redondance temporelle ne permet pas de détecter une erreur permanente, du moins, dans sa version la plus simple. Mais une version améliorée permet de corriger ce défaut. L'idée est que l'on n’exécute pas deux fois le même calcul, mais que l'on effectue deux calculs liés. On exécute un premier calcul avec les opérandes normaux, puis le même calcul avec les mêmes opérandes décalées de quelques rangs. Le résultat des deux opérations devrait être identique, si ce n'est que le second est décalé de quelques rangs. Dans ce cas, il est possible que les deux résultats ne concordent pas, ce qui permet de détecter une erreur.

La raison est qu'une erreur permanente fait que qu'exécuter plusieurs fois la même opération avec les mêmes opérandes donne le même résultat, mais que le calcul ne donne pas le bon résultat. Par contre, l'erreur tombe généralement sur un bit précis du résultat, un bit d'un poids bien précis. En décalant les opérandes, on peut capter l'erreur.

La correction d'erreur avec redondance physique

Après avoir vu comment détecter es erreurs, passons maintenant à la correction des erreurs. Pour corriger une erreur, il faut cependant aller plus loin que simplement doubler les circuits ou exécuter un calcul deux fois. Il faut le faire trois fois ! En clair, avoir trois copies d'un même circuit, ou exécuter un calcul trois fois. L'idée est que l'on dispose de trois résultats. S'ils sont identiques, on considère qu'il n'y a pas eu d'erreurs, le cas où les trois résultats sont erronés sont très rares. Mais si ce n'est pas le cas, alors une erreur a survenu, peut-être deux. Dans ce cas, on suppose que sur les trois résultats, l'erreur est le résultat qui diffère des deux autres. L'idée est que si une erreur a lieu, elle ne touche généralement qu'un seul circuit, le cas où deux circuits sont touchés par une erreur simultanée étant assez rare.

La méthode se généralise à plus de trois composants, il faut juste que le nombre soit impair. Par exemple, prenons le cas avec 5 circuits. Si un circuit tombe en panne, les quatre autres donneront un résultat correct. Avec 4 sorties contre une, c'est le résultat correct qui l'emportera. Tant que plus de la moitié des composants n'a pas de panne, le vote à majorité donne systématiquement le bon résultat. Par exemple, utiliser 5 composants permet de résister à une panne de 2 composants, en utiliser 7 permet de résister à 3 composants en panne, etc.

Vote à majorité simple

En clair, on choisit le résultat majoritaire. D'où le fait que la méthode s'appelle le vote à majorité. Reste à voir comment l'implémenter avec un circuit électronique. L'idée est simplement que les circuits dupliqués sont suivis par un circuit de correction d'erreur, qui choisit le résultat majoritaire. On peut aussi avoir d'autres circuits, mais ce n'est pas systématique.

Tolérance aux pannes matérielle passive

La solution la plus simple ne choisit pas la valeur majoritaire, mais applique le vote à majorité au niveau des bits. Pour le dire autrement, le vote à majorité s’effectue alors sur des bits de même poids, de la même colonne, comme illustré ci-dessous. Par exemple, si deux bits sont à 1 et le dernier à 0, alors le bit majoritaire est à 1.

Vote à majorité bit à bit

En clair, pour chaque colonne, on regarde les bits de même poids, et on détermine quel est le bit majoritaire. Il existe des portes logiques spécifiquement conçues pour faire ce calcul, les portes à majorité. Nous avions vu de telles portes il y a quelques chapitres, nous ne reviendrons pas dessus. Nous allons juste montrer le circuit équivalent à une telle porte, pour 3 entrées :

Porte à majorité à trois bits d'entrée.

On voit que le circuit de vote à majorité est donc très simple ! Il suffit de rajouter deux couches de portes logiques en sortie des circuits dupliqués. Le cout en circuit et en performance est donc très bas ! Pas inexistant, d'où son absence dans les processeurs grand public, mais très faible. C'est pour cela que cette méthode est presque toujours utilisée au lieu de l'usage d'un multiplexeur. Un autre avantage est qu'il n'y a pas besoin de circuit pour détecter l'erreur : elle est corrigée automatiquement par le circuit de vote à majorité, sans vraiment qu'il y ait détection de l'erreur en tant que telle.

Les codes de détection et de correction d'erreur

Pour les circuits combinatoires, on vient de voir que détecter et corriger des erreurs demande d'ajouter de la redondance, de dupliquer des circuits. Mais pour les mémoires et les bus de transmission, d'autres solutions plus pratiques sont possibles, qui ne nécessitent pas de dupliquer la mémoire et les bus de transmission. Les solutions en question sont 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.

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.

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é

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 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.

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é.

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. Une 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 égale 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é.

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 la table 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.

Générateur de parité sériel

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.

Circuit de parité

Les codes de Hamming

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 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é.

Hamming(7,4)

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. 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 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)

É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)

Les sommes de contrôle

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é

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

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éaires 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.

Circuit de calcul d'un CRC-8, en fonctionnement. Le diviseur choisi est égal à 100000111.

Le registre dépend du CRC à calculer, chaque CRC ayant son propre registre.

Circuit de vérification du CRC-8 précédent, en fonctionnement.