Les ordinateurs fonctionnent à l’aide de transistors que l’on peut modéliser simplement comme des interrupteurs qui ont deux positions : ouvert et fermé, que l’on peut représenter par 0 et 1, d’où l’idée de coder l’information en utilisant des bits.
Il arrive que des bits soient corrompus lors du transfert de l’information. Pour obtenir le bon message on utilise un code correcteur d’erreurs. Le principe d’un tel code est d’ajouter de l’information redondante. Ainsi, si une partie de l’information est perdue, on peut la récupérer ailleurs.
Prenons un exemple. On veut envoyer quatre bits : 0010. On pourrait choisir de répéter chaque bit deux fois : 00 00 11 00. Ainsi, si on reçoit 00 10 11 00, on détecte qu’il y a eu une erreur. Par contre, on ne peut corriger. En effet, le mot envoyé aurait pu être 00 00 11 00, ou encore 00 11 11 00. Un tel code est un code détecteur d’erreurs.
Un correcteur d’erreurs ne permet de récupérer le mot initial que si un nombre pas trop grand d’erreurs se sont produites. Sinon, l’information est perdue. On se propose d’utiliser un code correcteur d’erreur capable de corriger un mot à condition qu’il ne comporte qu’une seule erreur.
Le code de Hamming C(7, 4)
Ce code transforme les mots de 4 bits en mots de 7 bits et corrige une erreur. Pour cela, on va introduire une addition sur les bits donnée par la table suivante :
Cette addition donne 1 sur les deux bits sont différents et 0 sinon.
Prenons un mot de quatre bits : u1u2u3u4 que allons coder en un mot de 7 bits v1v2v3v4v5v6v7 de la manière suivante :
v1 = u1
v2 = u2
v3 = u3
v4 = u4
v5 = u1 + u2 + u4
v6 = u1 + u3 + u4
v7 = u2 + u3 + u4
On transmet le mot v1v2v3v4v5v6v7 composé des 4 bits de notre mot auquel nous ajoutons les 3 bits de contrôle. Notre destinataire reçoit le mot w1w2w3w4w5w6w7. Il va décoder le mot reçu de la façon suivante :
W5 = w1 + w2 + w4
W6 = w1 + w3 + w4
W7 = w2 + w3 + w4
Si la transmission a été réalisée sans erreur, alors W5=w5, W6=w6 et W7=w7.
Regardons maintenant ce qui se passe si une erreur s’est produite :
On voit que les incompatibilités sont toutes différentes. On peut donc corriger l’erreur selon les incompatibilités observées. Ainsi, si on veut envoyer 0010, on l’encode en
0010011.
Si on reçoit 0011011, on voit que W5 = 1 ≠ w5 = 0, W6 = 0 ≠ w6 = 1 et W7 = 0 ≠ w7 = 1. On conclut qu’il y a eu erreur car il y a des incompatibilités, et que, si exactement une erreur s’est produite, alors elle s’est produite en w4. On change w4 pour récupérer notre bon mot de départ.
Voici un programme python qui code et décode.
def opp(x):
# Renvoie le contraire de l'entrée
if x == '1':
return '0'
else:
return '1'
def add(x,y):
# Ou exclusif
if x == y:
return '0'
else:
return '1'
def valide(mot,longueur):
# Vérifie la syntaxe du mot
if len(mot) != longueur:
print("Longueur du mot incorrect")
return False
for lettre in mot:
if lettre not in "01":
print("Utilisez uniquement des 0 et des 1")
return False
return True
def controle(mot):
# Renvoie les codes de contrôle
c4 = add(add(mot[0],mot[1]),mot[3])
c5 = add(add(mot[0],mot[2]),mot[3])
c6 = add(add(mot[1],mot[2]),mot[3])
return c4,c5,c6
def code(mot):
## Codage en Hamming C(7,4)
if valide(mot,4):
c4,c5,c6 = controle(mot)
return(mot + c4 + c5 + c6)
def decode(mot):
## Décodage en Hamming C(7,4)
if valide(mot,7):
c4,c5,c6 = controle(mot[0:4])
if c4 + c5 != mot[4] + mot[5] and c6 == mot[6]:
reponse = opp(mot[0])
print("Erreur")
else:
reponse = mot[0]
if c4 + c6 != mot[4] + mot[6] and c5 == mot[5]:
reponse = reponse + opp(mot[1])
print("Erreur")
else:
reponse = reponse + mot[1]
if c5 + c6 != mot[5] + mot[6] and c4 == mot[4]:
reponse = reponse + opp(mot[2])
print("Erreur")
else:
reponse = reponse + mot[2]
if c4 + c5 + c6 != mot[4] + mot[5] + mot[6]:
reponse = reponse + opp(mot[3])
print("Erreur")
else:
reponse = reponse + mot[3]
return(reponse)
