Code de Hamming
1. Objectif du code de Hamming
Le code de Hamming est un code correcteur d’erreurs qui permet de détecter
jusqu’à deux erreurs et de corriger automatiquement une seule erreur (1 bit) dans
un mot binaire transmis sur un canal bruité.
Dans le cas du code Hamming (7,4) :
• On envoie 7 bits au total.
• Parmi ces 7 bits, 4 sont des bits de données (d1, d2, d3, d4).
• Les 3 autres bits sont des bits de parité (p1, p2, p4) utilisés pour la
détection/correction.
2. Paramètres du code Hamming (7,4)
Les paramètres principaux du code Hamming (7,4) sont :
• Longueur du mot : n = 7 bits.
• Nombre de bits de données : k = 4 bits.
• Nombre de bits de parité : r = 3 bits.
• Distance minimale : d = 3 (ce qui permet de corriger 1 erreur).
3. Organisation des bits dans Hamming (7,4)
On numérote les positions de 1 à 7. Les positions qui sont des puissances de 2 (1, 2
et 4) sont réservées aux bits de parité. Les autres positions sont utilisées pour les
bits de données.
1 2 3 4 5 6 7
p1 p2 d1 p4 d2 d3 d4
Structure générale du mot Hamming (7,4) : [p1, p2, d1, p4, d2, d3, d4]
4. Scénario 1 : Transmission sans erreur
4.1 Choix des bits de données
On choisit un exemple simple de 4 bits de données à transmettre :
d1 d2 d3 d4 = 1 0 1 1
On place ces bits dans le mot de 7 bits aux positions prévues :
1 2 3 4 5 6 7
p1 p2 1 p4 0 1 1
4.2 Calcul du bit de parité p1
Le bit de parité p1 (position 1) contrôle toutes les positions dont le bit de poids
faible du numéro de position est égal à 1. Avec la numérotation binaire, p1
contrôle les positions : 1, 3, 5, 7.
Bits concernés (sans compter p1 au départ) :
• Position 3 : d1 = 1
• Position 5 : d2 = 0
• Position 7 : d4 = 1
On utilise une parité paire : le nombre total de 1 dans le groupe doit être pair.
Actuellement, il y a 2 bits à 1 (positions 3 et 7), donc déjà pair. Pour garder la
parité paire, on choisit p1 = 0.
4.3 Calcul du bit de parité p2
Le bit de parité p2 (position 2) contrôle toutes les positions dont le deuxième bit
binaire du numéro de position est égal à 1. Il contrôle les positions : 2, 3, 6, 7.
Bits concernés (sans compter p2 au départ) :
• Position 3 : d1 = 1
• Position 6 : d3 = 1
• Position 7 : d4 = 1
Il y a 3 bits à 1, ce qui est impair. Pour obtenir une parité paire, on doit
ajouter un 1 supplémentaire, donc on choisit p2 = 1.
4.4 Calcul du bit de parité p4
Le bit de parité p4 (position 4) contrôle les positions dont le troisième bit binaire
du numéro de position est égal à 1. Il contrôle les positions : 4, 5, 6, 7.
Bits concernés (sans compter p4 au départ) :
• Position 5 : d2 = 0
• Position 6 : d3 = 1
• Position 7 : d4 = 1
Il y a 2 bits à 1, ce qui est pair. Pour garder la parité paire, on choisit p4 = 0.
4.5 Mot Hamming final émis
On remplace p1, p2 et p4 par leurs valeurs dans le mot :
• p1 = 0
• p2 = 1
• p4 = 0
1 2 3 4 5 6 7
0 1 1 0 0 1 1
Mot Hamming transmis : 0 1 1 0 0 1 1
4.6 Vérification côté réception (aucune erreur)
Côté réception, le récepteur recalcule les trois bits de parité à partir des 7 bits
reçus. Si le mot a été transmis sans erreur, les parités recalculées seront correctes
pour chaque groupe :
• Le groupe de p1 aura une parité paire.
• Le groupe de p2 aura une parité paire.
• Le groupe de p4 aura une parité paire.
Dans ce scénario, aucune erreur n’est détectée et les 4 bits de données (d1, d2, d3,
d4) sont récupérés correctement.
5. Scénario 2 : Transmission avec une erreur sur un bit
5.1 Mot Hamming émis
On reprend le mot Hamming émis dans le scénario 1 :
0110011
5.2 Apparition d’une erreur pendant la transmission
Supposons maintenant qu’une erreur se produise sur le bit en position 3 (d1). Au
lieu de 1, ce bit est reçu comme 0.
Mot reçu : 0 1 0 0 0 1 1
5.3 Recalcul des parités côté réception
Le récepteur recalcule les parités p1, p2 et p4 à partir du mot reçu, en utilisant les
mêmes groupes que précédemment.
• Vérification du groupe de p1 (positions 1, 3, 5, 7) :
- Position 1 : 0
- Position 3 : 0 (au lieu de 1)
- Position 5 : 0
- Position 7 : 1
→ Il y a 1 seul bit à 1, la parité est donc impaire : le groupe de p1 est en erreur.
• Vérification du groupe de p2 (positions 2, 3, 6, 7) :
- Position 2 : 1
- Position 3 : 0
- Position 6 : 1
- Position 7 : 1
→ Il y a 3 bits à 1, la parité est impaire : le groupe de p2 est en erreur.
• Vérification du groupe de p4 (positions 4, 5, 6, 7) :
- Position 4 : 0
- Position 5 : 0
- Position 6 : 1
- Position 7 : 1
→ Il y a 2 bits à 1, la parité est paire : le groupe de p4 est correct.
5.4 Calcul du syndrome (position de l’erreur)
On associe à chaque parité recalculée un bit de syndrome :
• C1 = 1 si le groupe de p1 est en erreur, sinon 0.
• C2 = 1 si le groupe de p2 est en erreur, sinon 0.
• C4 = 1 si le groupe de p4 est en erreur, sinon 0.
Dans notre exemple :
• C1 = 1 (p1 en erreur)
• C2 = 1 (p2 en erreur)
• C4 = 0 (p4 correct)
On forme alors le nombre binaire C4 C2 C1 = 0 1 1, ce qui est égal à 3 en décimal.
→ L’erreur se trouve donc à la position 3.
5.5 Correction de l’erreur
On corrige l’erreur en inversant le bit à la position 3 :
• Bit reçu à la position 3 : 0
• Bit corrigé à la position 3 : 1
Mot corrigé : 0 1 1 0 0 1 1
Ce mot corrigé est identique au mot Hamming initialement émis. Les 4 bits de
données (d1, d2, d3, d4) sont donc récupérés correctement malgré l’erreur sur le
canal.
5.6 Récapitulatif du scénario avec erreur
Résumé du fonctionnement du code Hamming (7,4) en présence d’une seule
erreur :
1. Les bits de parité sont recalculés côté réception.
2. Les groupes dont la parité est incorrecte indiquent qu’il y a une erreur.
3. Le syndrome C4 C2 C1 donne directement la position du bit erroné.
4. Le récepteur inverse ce bit pour corriger l’erreur.
6. Synthèse générale sur le code Hamming (7,4)
Le code Hamming (7,4) permet de :
• Transmettre 4 bits de données sous forme d’un mot de 7 bits.
• Détecter jusqu’à deux erreurs de bit.
• Corriger automatiquement une erreur de bit.
L’idée clé est l’utilisation de bits de parité placés à des positions bien choisies et de
la notion de syndrome, qui indique directement la position du bit à corriger
lorsqu’une erreur unique se produit.