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

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

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.

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

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

Exemple de détection d'erreurs avec le bit de parité

On a stocké des données en rajoutant tous les 8 bits un bit de parité. Indiquez s'il y a eu ou 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 ==> 11001111
0111 1111 1 ===> 8 bits à 1 ===> Pas d'erreur ==> 0111 1111
0110 1101 0 ===> 5 bits à 1 ===> Erreur

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.

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.

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é, et il permet également 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.

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

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éré ?
• 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

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.

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.

Obtention du code CRC

É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^{11}+1.X^{10}+1.X^{9}+1.X^{8}+1.X^{7}+1.X^{6}+1.X^{3}+1X^{2}+1.X+0$

soit $X^{10}+X^{9}+X^{8}+X^{7}+X^{6}+X^{3}+X^{2}+X$

Étape 2

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

$X^{13}+X^{12}+X^{11}+X^{10}+X^{9}+X^{6}+X^{5}+X^{4}$

É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^{13}+X^{12}+X^{11}+X^{10}+X^{9}+X^{6}+X^{5}+X^{4}$ divisé par $X^{3}+X+1$

$-X^{14}-X^{12}-X^{11}$ $X^{11}+X^{10}+X^{8}+X^{6}+X^{5}+X^{3}+X^{2}$

==>$X^{13}+X^{10}+X^{7}+X^{6}+X^{4}$

$-X^{13}-X^{11}-X^{10}$

==>$-X^{11}+X^{7}+X^{6}+X^{4}$ ==>$X^{11}+X^{7}+X^{6}+X^{4}$

$-X^{11}-X^{9}-X^{8}$

==>$-X^{9}-X^{8}+X^{7}+X^{6}+X^{4}$ ==>$X^{9}+X^{8}+X^{7}+X^{6}+X^{4}$

$-X^{9}-X^{7}-X^{6}$

==>$X^{8}+X^{4}$

$-X^{8}-X^{6}-X^{5}$

==>$-X^{6}-X^{5}+X^{4}$ ==>$X^{6}+X^{5}+X^{4}$

$-X^{6}-X^{4}-X^{3}$

==>$X^{5}-X^{3}$ ==>$X^{5}+X^{3}$

$-X^{5}-X^{3}-X^{2}$

==>$-X^{2}$ ==>$X^{2}$

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

Étape 4

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

$0.X^{3}+1.X^{2}+0.X^{1}+0.X^{0}$

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

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 :

Étape 1

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

Étape 2

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

Étape 3

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

Exercices

Exercice 1

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

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

Exercice 3

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

Exercice 4

Voici 2 données codées en utilisant le 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 ?

Exercice 5

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

Exercice 6

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

Codes