Skip to main content

Détection et résolution d'erreurs

Maintenant que l'on sait représenter des nombre et des caractères en binaire, on peut maintenant voir comment faire dans les cas où il pourrait y avoir des erreurs.

Que ce soit dans la mémoire ou lors de communication, ce n'est pas infaillible et 1 seul bit qui change pourrait changer complètement l'information.

Le bit de parité (code auto-verificateur)

Supposons que notre code est le suivant : 01001000 pour calculer la parité paire, il suffit de compter le nombre de 1. Dans ce cas il y a 2 fois 1. Donc le bit de parité est 0.

Si on compte un nombre impair de 1, alors le bit de parité est 1. En bref, il faut que le nombre total de 1 (en comptant à la fois le message et le bit de parité) soit pair.

Et pour la parité impaire, il suffit de faire l'inverse. On s'assure donc que le nombre total de 1 (en comptant message + bit de partité) soit impair.

Ainsi maintenant on peut vérifier un code et savoir si il a été altéré ou non. En revanche cette méthode est limitée, car si il y a un nombre pair d'erreurs, alors le bit de parité ne dédectera rien d'anormal. Aussi, on n'a aucune idée de où se trouve l'erreur.

La double parité (code auto-correcteur)

Maintenant imaginons que l'on a un message plus long. Comme SHUMI par exemple. On va donc le transcrire en binaire (avec le code UTF-8)

Carb7b6b5b4b3b2b1b0
S01010011
H01001000
U01010101
M01001101
I01001001

Maintenant on va faire une parité paire horizontalement et une parité impaire verticalement comme vu précédemment..

Carb7b6b5b4b3b2b1b0PP
S010100110
H010010000
U010101010
M010011010
I010010011
PI10110101

Maintenant en vérifiant tous les bits de parités on peut retrouver une erreur facilement et la corriger

Carb7b6b5b4b3b2b1b0PP
S010100110
H010010000
E010001010
M010011010
I010010011
PI10110101

On peut voir ici qu'il y a eu une erreur au niveau du bit 4 sur le 3e caractère car la parité paire de la ligne et la parité impaire de la colonne ne sont plus correct. A cause de ça notre U est devenu un E.

Mais on sait donc précisément quel bit est la cause de l'erreur et comment le résoudre. En revanche cette méthode nécessite beaucoup de bits de vérification.

Le code de Hamming

Ici on se concentre sur le code de Hamming qui permet de corriger 1 bit en erreur, il existe des variantes plus complexes mais que l'on apprend pas ici.

Création du code de Hamming

Disons que l'on veut stoquer le code S, soit 1010011 en binaire.

Tout d'abord on va faire un tableau pour contenir notre code, mais qui va être un peu plus long pour contenir nos bits de parités

1110987654321

Maintenant on va bloquer tous les emplacements qui sont des puissances de 2 (qui sont nos bits de parités)

1110987654321
k4k3k2k1

Ensuite on peut écrire le message à coder dans les bits restants :

1110987654321
101k4001k31k2k1

Maintenant on liste tous les numéros de bits qui valent 1 dans le tableau et on les convertis en binaire

11 → 1011
9  → 1001
5  → 0101
3  → 0011

Ensuite pour chaque colonne en binaire on va faire une parité de la colonne. Chaque bit de parité trouvé corresponds aux bits de parités dans le tableau.

11 → 1011
9  → 1001
5  → 0101
3  → 0011
     ----
     0100 (k4 = 0, k3 = 1, k2 = 0, k1 = 0)

On peut donc remplacer ces derniers dans le tableau

1110987654321
10100011100

Notre code de Hamming est donc : 10100011100

Vérification et correction dans un code de Hamming

Maintenant quand on veut vérifier un code reçu, voici comment faire. On va partir du code 10101011100 et on va le vérifier (et si besoin corriger)

Tout d'abord on va placer tout ceci dans un tableau avec les bits numérotés :

1110987654321
10101011100

Maintenant on liste tous les bits qui sont a 1 et on convertis leur position en binaire :

11 → 1011
9  → 1001
7  → 0111
5  → 0101
4  → 0100
3  → 0011

Ensuite, on va faire la parité de chaque colonne. Le résultat corresponds à la position du bit en erreur en binaire. Si le résultat done 0 partout, alors il n'y a pas d'erreur détectée.

11 → 1011
9  → 1001
7  → 0111
5  → 0101
4  → 0100
3  → 0011
     ----
     0111 → 7 (le bit 7 doit donc être inversé)

Nous pouvons donc corriger notre code :

1110987654321
10100011100

Pour obtenir le message d'origine il suffit de retirer tous les bits qui sont à des positions qui correspondent à des puissances de 2

1110987654321
1010011

Ce qui nous donne donc le message suivant : 1010011 soit S en ASCII. Nous retrouvons donc le même résultat que le message encodé au départ 🎉