Architecture des ordinateurs/Codes détecteurs et correcteurs d'erreurs

Un livre de Wikibooks.

Architecture des ordinateurs

Sommaire

Introduction Représentation des données Codes détecteurs et correcteurs d'erreurs Circuits asynchrones usuels Mémoires et circuits séquentiels

Bibliographie

Lien internes

| Modifier ce modèle

Sections 1 Le cours sur les codes détecteurs et correcteurs d'erreurs 1.1 Les enjeux 1.2 Le bit de parité 1.2.1 Exemple sur le bit de parité 1.2.2 Détection des erreurs avec le bit de parité 1.2.3 Exemple de détection d'erreurs avec le bit de parité 1.2.4 Bilan sur le bit de parité 1.2.5 Exemple d'utilisation 1.3 Le code de Hamming 1.3.1 Principe de base 1.3.2 Vérification et correction du code de Hamming 1.4 Les inconvénients du codage de Hamming et du bit de parité 1.5 Le code CRC 1.5.1 Obtention du code CRC 1.5.1.1 Étape 1 1.5.1.2 Étape 2 1.5.1.3 Étape 3 1.5.1.4 Étape 4 1.5.2 Vérification du code CRC 1.5.2.1 Étape 1 1.5.2.2 Étape 2 1.5.2.3 Étape 3 2 Exercices 2.1 Exercice 1 2.2 Exercice 2 2.3 Exercice 3 2.4 Exercice 4 2.5 Exercice 5 2.6 Exercice 6

[modifier] Le cours sur les codes détecteurs et correcteurs d'erreurs

[modifier] Les enjeux

Un ordinateur transfère en permanence des données entre ces différents éléments : une donnée stokée en RAM peut être transférée sur un disque dur, archivée sur un DVD ou encore envoyée à l'autre bout de la planète via un réseau. Les débits d'une RAM sont extraordinaires : plusieurs milliards de bits par seconde peuvent être échangés. Pour un ordinateur qui fonctionne 24 heures sur 24, cela représente un nombre de bits journaliers extrêmement important.
Certains ordinateurs comme les serveurs jouent un rôle primordial pour une entreprise. Une simple panne peut avoir des conséquences économiques très importantes pouvant aller jusqu'à la paralysie de l'entreprise. Rappelons juste que si 50 personnes dans une entreprise ne peuvent pas travailler à cause d'une panne informatique, le coût indirect pour l'entreprise est égal à la somme des salaires des employés multiplié par la durée de la panne. A ces coûts, il faut rajouter la perte de crédibilité de l'entreprise qui doit dire à ses clients "euh... désolé, nous ne pouvons prendre votre commande car nous sommes en panne d'informatique". L'informatique se doit être fiable à 100 % et constitue un élément vital de beaucoup de sociétés.

Aucune technologie peut être fiable à 100 % ! Aucun procédé industriel non plus. Vu les quantités astronomiques de bits échangés au sein d'un ordinateur même un taux d'erreurs de 1 bits sur 1000 milliards peut apparaître comme étant insuffisant. Il faut donc admettre que les données que manipule notre ordinateur peuvent avoir été corrompues.

Comment améliorer cette situation pour limiter au maximum les conséquences de ces erreurs ? Une première approche consiste à se dire que si une donnée a été corrompue, il faut être capable de détecter a posteriori ces erreurs. Ainsi, si on s'aperçoit qu'un programme exécutable contenu dans un fichier sur un disque dur a été corrompu, alors le programme ne sera pas exécuté par notre ordinateur : on évitera ainsi le crash du système d'exploitation. Il est donc primordial de pouvoir déterminer si une donnée a été corrompue ou non. Nous allons donc étudier dans ce chapitre des techniques permettant de détecter des erreurs sur des données. Certaines techniques sont surprenantes car elles permettent parfois de corriger les erreurs. Ces techniques ne permettent pas d'obtenir une fiabilité de 100 % mais elles améliorent énormément le taux d'erreurs. Ainsi, on limite considérablement le nombre d'erreurs et on améliore la fiabilité de nos ordinateurs pour la rendre acceptable.

[modifier] Le bit de parité

Le bit de parité est un mécanisme détecteur d'erreurs très simple et peu coûteux. On va découper l'information à manipuler par "tranches de bits", par exemple par tranche de 8 bits, et on va rajouter un bit par tranche. On choisira ce bit de manière à ce qu'il y ait un nombre de bits à 1 pair dans chaque tranche.

[modifier] Exemple sur le bit de parité

On manipule les données suivantes. Rajouter dans chaque cas le bit de parité.
Donnée initiale ==> Donnée finale
0011 0001 ==> 0011 0001 1
0111 1110 ==> 0111 1110 0
0001 0111 ==> 0001 0111 0

[modifier] Détection des erreurs avec le bit de parité

Lorsqu'on récupère la donnée, on va se poser la question : la donnée a-t-elle été altérée ? On va compter le nombre de bits à 1 dans chaque tranche : s'il est pair, on va considérer que la donnée n'a pas été altérée. Par contre s'il est impair, on considèrera que la donnée a été altérée : on aura ainsi détecté une erreur et seulement une (voir ds les codes de hamming).

[modifier] Exemple de détection d'erreurs avec le bit de parité

On a stocké des données en rajouter tous les 8 bits un bit de parité. Indiquez s'il y a eu on non une erreur. S'il n'y a pas eu d'erreur, donnez la donnée initiale sans le bit de parité.
Donnée finale ===> Nombre de 1 ==> Conclusion ==> Si aucune erreur donnée initiale
0000 1111 1 ===> 5 bits à 1 ===> Erreur
1100 1111 0 ===> 6 bits à 1 ===> Pas d'erreur ==> 1100 1111
0111 1111 1 ===> 8 bits à 1 ===> Pas d'erreur ==> 0111 1111
0110 1101 0 ===> 5 bits à 1 ===> Erreur

[modifier] Bilan sur le bit de parité

Le bit de parité est un mécanisme de détection d'erreurs peu coûteux (1 seul bit rajouté), qui est très simple mais son efficacité n'est pas extraordinaire. du fait qu'il peut avoir des messages contenant un nombre d'erreur pair mais qui ne peut être détecté par la technique de contrôle de parité.

Exemple:

message original	10101010	1
message altéré	01010101	1

Ce petit exemple nous montre que bien que le message soit altéré, le contrôle de parité ne le détecte pas, ce qui constitue la limite la plus reprochée de cette technique.

[modifier] Exemple d'utilisation

Dans les années 90, certaines barrettes de mémoire RAM rajoutaient un bit de parité tous les 8 bits (il y avait donc 9 bits stockés), ce qui permettait de diminuer leur taux d'erreurs.

[modifier] Le code de Hamming

Le code de Hamming est un code étonnant : il permet de détecter une erreur et seulement une erreur ce qui fait sa particularité mais aussi de la corriger. En cas de détection d'erreurs, ce code va proposer une correction qui est la plus probable sous certaines hypothèses statistiques.

[modifier] Principe de base

On va découper l'information par tranche de N bits et on va rajouter t bits : t sera le plus petit entier tel que 2^t − 1 > = N + t. On aura donc au total N+t bits.
Les bits rajoutés ne seront pas mis à la fin mais seront entrelacés avec la donnée initiale. Ainsi les N+t bits de la donnée finale seront notés f_N+t f_N+t-1 f_N+t-2 ... f₂f₁. Les t bits rajoutés, appelés bits de contrôle, seront ceux dont l'indice est une puissance de 2. Il y en a exactement t.

Exemple : la donnée initiale est 0110 1110
N vaut donc 8. On cherche la plus petite valeur de t vérifiant 2^t − 1 > = 8 + t. On trouve facilement t=4. Il y a au total 12 bits. Les bits contrôle sont f₁, f₂, f₄ et f₈.

Les bits qui ne sont pas des bits de contrôle s'obtiennent très facilement : il suffit de reporter la donnée initiale. Ainsi sur notre exemple :

f12	f11	f10	f9	f8	f7	f6	f5	f4	f3	f2	f1
0	1	1	0		1	1	1		0

Il nous reste donc à trouver la valeur des bits de contrôle. Pour les trouver nous allons former des ensembles de bits. Pour trouver les ensembles de bits il faut au préalable écrire les entiers de 1 à N+t en base 2 sur t bits. Sur notre exemple, N vaut 8 donc t vaut 4 : il faut donc écrire les entiers de 1 à 12 en base 2 sur 4 bits.

0001 ===> 1
0010 ===> 2
0011 ===> 3
0100 ===> 4
0101 ===> 5
0110 ===> 6
0111 ===> 7
1000 ===> 8
1001 ===> 9
1010 ===> 10
1011 ===> 11
1100 ===> 12

Que nous plaçons dans un tableau, pour plus de clareté avec les explications qui suivront :

   i--3 2 1 0
 j    | | | |
 1 -- 0 0 0 1
 2 -- 0 0 1 0
 3 -- 0 0 1 1
 4 -- 0 1 0 0
 5 -- 0 1 0 1
 6 -- 0 1 1 0
 7 -- 0 1 1 1
 8 -- 1 0 0 0
 9 -- 1 0 0 1
10 -- 1 0 1 0
11 -- 1 0 1 1
12 -- 1 1 0 0

i = rang du bit, j = numéro de ligne

Nous allons maintenant construire t ensembles de bits notés E₁, E₂ ... E_t. Pour construire E_i, on regarde la colonne i à partir de la droite. S'il y a un 1 dans colonne i sur la ligne j alors le bit f_j appartiendra à l'ensemble E_i.
Dans notre exemple, pour contruire E ₁, nous allons regarder la colonne la plus à droite on trouve un 1 sur les lignes 1, 3, 5, 7, 9 et 11. On trouve donc :
E₁ = { f₁ , f₃, f₅, f₇ , f₉, f₁₁ }
De la même manière, on trouve :
E₂ = { f₂ , f₃, f₆, f₇ , f₁₀, f₁₁ }

E₃ = { f₄ , f₅, f₆, f₇ , f₁₂ }
E₄ = { f₈ , f₉, f₁₀, f₁₁ , f₁₂}
Nous allons maintenant reporter dans chaque ensemble les valeurs que nous avions trouvées :
f₁₂=0
f₁₁=1
f₁₀=1
f₉=0
f₇=1
f₆=1
f₅=1
f₃=0

On obtient :
E₁ = { f₁ , 0, 1, 1, 0, 1}
E₂ = { f₂ ,0 , 1, 1, 1, 1 }
E₃ = { f₄ ,1 , 1, 1 , 0 }
E₄ = { f₈ ,0 , 1, 1, 0}

On s'aperçoit que dans chaque ensemble il y a un et un seul bit inconnu. Nous allons déterminer ce bit de manière à ce que dans chaque ensemble de bits le nombre de bits à 1 soit pair. On trouve donc :
f₁=1
f₂=0
f₄=1
f₈=0

f12	f11	f10	f9	f8	f7	f6	f5	f4	f3	f2	f1
0	1	1	0	0	1	1	1	1	0	0	1

Nous connaissons maintenant tous les bits de notre donnée finale qui est donc : 0110 0111 1001

[modifier] Vérification et correction du code de Hamming

Lorsqu'on récupère une donnée obtenue grâce au codage de Hamming, deux questions naturelles vont se poser :

• la donnée a-t-elle été altére ?
• si oui, quelle est la correction proposée par le code de Hamming ?

La méthode pour répondre à ces deux questions est la suivante :

• construire les t ensembles de bits E_i.
• calculer t bits selon la règle suivante e_i=0 si le nombre de bits à 1 dans E_i est pair sinon e_i=1. Si aucune erreur ne s'est produite tous les bits e_i doivent être nuls.
• calculer E=(e_t ...e₁)₂.
• Si E est nul alors on en déduit qu'il n'y a pas eu d'erreur.
• si E n'est pas nul, une erreur s'est produite et le code de Hamming propose la correction suivante : inverser la valeur du bit f_E.
• on récupère ensuite aisément la valeur de la donnée initiale en supprimant les bits de contrôle.

Exemple : on récupère la donnée 0111 0111 1001, le bit en rouge signalant l'erreur.

On a donc :

f12	f11	f10	f9	f8	f7	f6	f5	f4	f3	f2	f1
0	1	1	1	0	1	1	1	1	0	0	1

On construit les ensembles de bits :
E₁ = { f₁ , f₃, f₅, f₇ , f₉, f₁₁ } ={ 1 , 0, 1, 1, 1, 1} ==> le nombre de 1 (5) est impair ==> e₁=1
E₂ = { f₂ , f₃, f₆, f₇ , f₁₀, f₁₁ } = { 0 ,0 , 1, 1, 1, 1 } ==> le nombre de 1 (4) est pair ==> e₂=0
E₃ = { f₄ , f₅, f₆, f₇ , f₁₂ } = { 1 ,1 , 1, 1 , 0 } ==> le nombre de 1 (4) est pair ==> e₃=0
E₄ = { f₈ , f₉, f₁₀, f₁₁ , f₁₂} ={ 0 ,1 , 1, 1, 0} ==> le nombre de 1 (5) est impair ==> e₄=1

E s'écrit donc en base 2 (e₄e₃e₂e₁) soit (1001). E vaut donc 9. Il y a donc eu une erreur : la correction propose d'inverser la valeur de bit f₉. f₉ valait 1 : nous allons donc changer sa valeur en 0.

La donnée corrigée est donc :

f12	f11	f10	f9	f8	f7	f6	f5	f4	f3	f2	f1
0	1	1	0	0	1	1	1	1	0	0	1

En enlevant les bits f₈, f₄, f₂ et f₁, on obtient donc la donnée initiale après correction soit 0110 1110

[modifier] Les inconvénients du codage de Hamming et du bit de parité

Ces deux codages sont intéressants mais ne sont pas adaptés à tous les types de situation : lorsqu'il n'y a que peu d'erreurs et que ces erreurs sont statistiquement isolées, ces codes peuvent être intéressants. Mais dès qu'il y a un grand nombre d'erreurs et que ces erreurs arrivent groupées, alors ces codages deviennent de moins en moins performants. On s'aperçoit ainsi que l'efficacité d'un mécanisme de détection d'erreurs dépend en fait des hypothèses sur la répartition statistique des erreurs.

[modifier] Le code CRC

Le codage CRC est un mécanisme très efficace pour détecter des erreurs groupées. Il faut dans un premier temps se fixer une fois pour toute un polynôme référence : par exemple, nous allons choisir X³+X+1. Dans la réalité, les polynômes références sont des polynômes de degré élevé, 16 ou 32 par exemple. Pour des raisons de simplicité de présentation, nous choisirons un polynôme de degré 3 dans cette présentation.
On se donne une suite de bits quelconque par exemple 0111 1100 1110. On veut rajouter les bits de contrôle CRC à la fin de cette donnée.

[modifier] Obtention du code CRC

[modifier] Étape 1

On commence par construire un polynôme à partir de la suite de bits. On va construire le polynôme dont les coefficients correspondent à la suite de bits fixées. Ainsi à partir de la suite de bits 0111 1100 1110, on va obtenir le polynôme :
0.X¹¹ + 1.X¹⁰ + 1X⁹ + 1.X⁸ + 1.X⁷ + 1.X⁶ + 1.X³ + 1X² + 1.X + 0
soit X¹⁰ + X⁹ + X⁸ + X⁷ + X⁶ + X³ + X² + X

[modifier] Étape 2

On multiplie ensuite par X^d où d est le degré du polynôme référence, ici par X³.

X¹³ + X¹² + X¹¹ + X¹⁰ + X⁹ + X⁶ + X⁵ + X⁴

[modifier] Étape 3

On divise le polynôme obtenu par le polynôme référence. Attention, on effectue la division de polynôme dans Z/2Z c'est-à-dire que tout coefficient pair sera remplacé par 0 et tout coefficient impair (notamment -1) sera remplacé par 1.

X¹³ + X¹² + X¹¹ + X¹⁰ + X⁹ + X⁶ + X⁵ + X⁴ divisé par X³ + X + 1

− X¹⁴ − X¹² − X¹¹ X¹¹ + X¹⁰ + X⁸ + X⁶ + X⁵ + X³ + X²

==>X¹³ + X¹⁰ + X⁷ + X⁶ + X⁴

− X¹³ − X¹¹ − X¹⁰

==> − X¹¹ + X⁷ + X⁶ + X⁴ ==>X¹¹ + X⁷ + X⁶ + X⁴

− X¹¹ − X⁹ − X⁸

==> − X⁹ − X⁸ + X⁷ + X⁶ + X⁴ ==>X⁹ + X⁸ + X⁷ + X⁶ + X⁴

− X⁹ − X⁷ − X⁶

==>X⁸ + X⁴

− X⁸ − X⁶ − X⁵

==> − X⁶ − X⁵ + X⁴ ==>X⁶ + X⁵ + X⁴

− X⁶ − X⁴ − X³

==>X⁵ − X³ ==>X⁵ + X³

− X⁵ − X³ − X²

==> − X² ==>X²

On s'arrête lorsque le degré du reste est strictement inférieur à d.

[modifier] Étape 4

On écrit ensuite le reste en écrivant tous les coefficients de X^d-1 à X⁰.

0.X³ + 1.X² + 0.X¹ + 0.X⁰

Le code CRC est la suite de d bits obtenues à partir des coefficients de ce polynôme.
Le CRC est donc ici 0100. On rajoute le CRC à la fin de la donnée initiale. On obtient donc comme donnée finale :
0111 1100 1110 0100

[modifier] Vérification du code CRC

Pour vérifier un code CRC lorsqu'on se donne une suite de bits contenant à la fin le code CRC, il faut suivre les étapes suivantes :

[modifier] Étape 1

Obtenir le polynôme à partir de la suite de bits.

[modifier] Étape 2

Diviser le polynôme obtenu par le polynôme référence (sans avoir multiplié le polynôme par X^d).

[modifier] Étape 3

Si le reste obtenu est nul, on en déduit qu'il n'y a eu aucune erreur de transmission. Dans le cas contraire une erreur s'est produite.

[modifier] Exercices

[modifier] Exercice 1

Rajoutez le bit de parité (à la fin) aux données suivantes :
1010 1110
0011 0011
0000 0001

[modifier] Exercice 2

Voici des données auxquelles on a rajouté à la fin un bit de parité. Ces données ont-elles été altérées. 1100 1111 0
0011 1110 1
1111 1111 1

[modifier] Exercice 3

Représentez en utilisant le code de Hamming les données initiales suivantes :
0011 1100
1110 0111 1100
1111 0111 1111 1011

[modifier] Exercice 4

Voici 2 données codées en utilisant la codage de Hamming
1111 1110 1101
1011 1110 1100
Pour chacune de ces valeurs :
a) La donnée a-t-elle été altérée ?
b) Quelle était la donnée initiale ?

[modifier] Exercice 5

Calculer le code CRC obtenu à partir des données initiales suivantes. Le polynôme référence est X³ + X + 1.
1100 1100 1001
0010 0110 1001
1000 0100 0111

[modifier] Exercice 6

Voici des données contenant à la fin un code CRC. Le polynôme référence est X³ + X + 1. La donnée a-t-elle été altérée ?
1101 1110 1111 1010
1101 1110 1111 1010