Le contrôle d’erreur

• La détection d’erreur
• Les données peuvent être modifiées (ou perdues) pendant le – Comment se rendre compte de la modification des données à l’arrivée
transport des trames (problème au niveau physique) ?
– Un service primordial pour de nombreuses applications
• Suppression des erreurs, deux techniques :
– Exemple : le transfert de fichier
– Comment corriger à l’arrivée les données erronées ? :
• Modification au niveau physique :
» la correction d’erreur à l’arrivée du paquet
– déformation de l’onde
– Faire en sorte que l’émetteur, renvoie les trames erronées/perdues:
• Perte complète de paquet :
» la récupération d’erreurs par re-émission
– congestion du réseau, saturation des routeurs ou des switch

© P. Sicard - Cours Réseaux Détections et corrections d’erreurs 1 © P. Sicard - Cours Réseaux Détections et corrections d’erreurs 2

Applications La détection/correction d’erreur

• Transfert de donnée sur un réseaux très peu fiable: • Idée: rajouter de l’information aux données permettant de détecter/
– Exemple: correction d’erreur dans l’ADSL (FEC affichées sur les Box) corriger les erreurs à l’arrivée
• Transfert de donnée sur un réseaux peu fiable: • Exemple de détection: Code de répétition
– Code correcteur coûte cher (en terme quantité d’information rajoutée) – On duplique l’information
– On préfère faire de la récupération d’erreur par re-émission (si il n’y a – Par exemple on rajoute un bit identique pour chacun des bits à
pas de contrainte de temps) transmettre
• Méthodes de détection et correction sont aussi utilisées pour le stockage de – Exemple:
donnée » Données: 1 0 0 0 1 1
– Lecture de fichier sur un disque dur » Code: 1 1 0 0 0 0 0 0 1 1 1 1

» Système de correction intégré aux disques (RAID Redundant Arrays • Coût en taille : élevé
of Inexpensive Disks)
• Coût en calcul faible
– Lecture de CD/DVD (problème de rayure)
» Problème légèrement différent : l’information peut aussi ne pas • Qualité de la détection d’erreur ?
exister (et on le sait) – Est-on capable de détecter 1 seul bit erroné ? 2 bits ?...

© P. Sicard - Cours Réseaux Détections et corrections d’erreurs 3 © P. Sicard - Cours Réseaux Détections et corrections d’erreurs 4
 La correction d’erreur La détection d’erreur
• Exemple de correction: Code de répétition • Exemple de détection: Le code de parité
– On triple l’information – On rajoute un bit à 1 ou 0 suivant la parité du nombre de bits à 1 dans les
données Le récepteur vérifie la valeur de ce bit de parité.
– On rajoute deux bits identiques pour chacun des bits à transmettre
– Exemple:
– Exemple:
» Données: 1 0 0 0 1 1 Bit de parité: 1
» Données: 1 0 0 1 1 » Données: 1 0 0 1 1 1 0 1 1 Bit de parité : 0
» Code: 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1
• Très peu couteux en taille
• Coût en taille: très élevé
• Très peu couteux en calcul
• Qualité de la détection d’erreur ? • Qualité de la détection d’erreur ?
– Si il y a une seule erreur on peut la corriger ? – Est-on capable de détecter 1 seul bit erroné ? 2 bits ?...
– Si il y a deux erreurs ?

© P. Sicard - Cours Réseaux Détections et corrections d’erreurs 5 © P. Sicard - Cours Réseaux Détections et corrections d’erreurs 6

Contrôle d’erreur : un modèle d’étude Détection d’erreur

• Propriété:
• Mot de code • Pour détecter (à coup sûr) x erreurs il suffit que la distance minimale
h≥x+1
Si une trame contient m bits de données et r bits de contrôle,
• En effet ainsi s’il y a x erreurs on ne pourra pas “retomber” sur un
on appelle mot du code le mot formé par les m + r bits. code existant (différent forcément de x+1 bits)
On pose n = m + r
• Exemple:

• Distance de Hamming • On suppose que le récepteur possède en mémoire l’ensemble des mots
justes
• Étant donné deux mots de n bits m1 et m2, le nombre de bits dont ils
diffèrent est appelé leur distance de Hamming (notée Disth) • Il compare le mot reçu à chacun de ces mots justes
• m = 2, r =1 : M = {000, 011, 101, 110}
• Distance de Hamming du code complet (ou distance minimale) • h=2
h = { Min Disth(x1, x2) ; x1 et x2 ∈ M et x1≠x2} • Supposons 011 envoyé et 111 reçu (donc une erreur)
• 111 forcément différent des mots justes: encore au moins un bit
M est l’ensemble des 2 m mots de codes possibles si on admet que les r bits de
différent puisque h=2. Le récepteur sait donc qu’il y a une erreur
contrôle sont calculés en fonction des m bits de données.

© P. Sicard - Cours Réseaux Détections et corrections d’erreurs 7 © P. Sicard - Cours Réseaux Détections et corrections d’erreurs 8
 Exemple de code détecteur d’erreur Détection d’erreur par
“checksum”
• Les bits de contrôle sont calculés par l’émetteur, le récepteur
fait un calcul analogue après réception • Données considérées comme n mots de k bits
• Bits de contrôle = complément à 1 de la somme des n mots
• Bit de parité
• A la réception la somme des n mots de données plus le checksum ne
• m = 2, r =1 : M = {000, 011, 101, 110 } doit pas contenir de 0
• h = 2 aucune erreur double mais détecte aussi tous les erreurs dont • h=2 mais aussi détection de certaines erreurs doubles (dans les
le nombre est impair colonnes) et des rafales d’erreur de longueur ≤ k
• Utilisé dans UDP, TCP
• Bit de parité par colonne:
k=8
• Trame considérée comme une matrice n*k bits k=8
0 0 0 1 1 1 0 1
• 1 bit de parité par colonne 1 2 3 4 5 6 7 8 n=3
+ 0 0 0 1 0 0 0 1
• h=2 9 10 ... + 0 0 1 1 0 0 0 0
n
• détection des rafales d’erreurs de longueur ≤ k = 0 1 0 1 1 1 1 0
Complément à 1
Bits de parité
Checksum 1 0 1 0 0 0 0 1

© P. Sicard - Cours Réseaux Détections et corrections d’erreurs 9 © P. Sicard - Cours Réseaux Détections et corrections d’erreurs 10

Détection d’erreur par CRC (Cyclic Principe de calcul d’un CRC

redundancy Code) – Basée sur des calculs de division de polynôme à coefficient dans [0, 1]
– Exemple: 1 0 1 0 1 représente x4+x2+1
– Division de x3+x2+1= (x2+1)* (x + 1) + (x) : Reste =x, Quotient = x+1
• Plus performant que les simples Checksums, surtout pour les
paquets/rafales d’erreurs – Arithmétique polynomiale modulo 2 (sans retenue): soustraction et addition
sont équivalentes à un ou-exclusif bit à bit
• Ne dépend pas de la taille des données – On se donne un polynôme générateur G de degré n qui détermine le nombre
de bits de contrôle
• Peu coûteux en taille
n
• Calcul coûteux mais souvent fait par hard : ou exclusif successifs au T: Données G
000...0
fur et à mesure que la trame arrive Quotient
Reste
– Circuit simple et rapide à base de registre à décalage et de portes
– T= Quotient*G + Reste donc (T+Reste)/G = 0
XOR
– La trame envoyée E= (Données, Reste) est divisible par G, il suffit à
l’arrivée de calculer la division de E par G. Si le reste est non nul il y a une
erreur
© P. Sicard - Cours Réseaux Détections et corrections d’erreurs 11 © P. Sicard - Cours Réseaux Détections et corrections d’erreurs 12
 Exemple calcul de CRC Correction d’erreur
• Propriété:
• 6 bits de données: 110101 , Polynôme générateur 101 : x2 +1
• Pour corriger x erreurs il suffit que la distance minimale h ≥ 2x + 1
101
• En effet s’ il y a x erreurs, le code erroné reste ainsi «le plus proche» du
11010100
code juste, on peut donc le retrouver. Les autres ont encore au moins x+1
101
0111
111011 différences.
101
0100 • Exemple de code correcteur
101
00110
m = 2, r = 3
101 M = {00111, 01100, 10000, 11011}, h = 3, on corrige une erreur
0110
101 On envoie 01100, il arrive 11100 : une erreur
Reste= 0 1 1 Le récepteur compare le mot arrivé aux 4 mots du code possible:
• On envoie E= 110101 11
00111 et 11100 : 4 différences
• On peut avec n=16 détecter toutes les erreurs simples et doubles, toutes les
erreurs comportant un nombre impair de bits et tous les paquets d'erreur de 01100 et 11100 : 1 différence
longueur ≤ 16 et, avec une très bonne probabilité, les paquets d’erreurs de 10000 et 11100 : 2 différences
longueur supérieure.
11011 et 11100 : 3 différences
• Exemple: Ethernet utilise un champs CRC à 32 bits, Compression ZIP
utilise un CRC à 16 ou 32 bits Seul 01100 possède une seule différence, c’est le mot envoyé, le
récepteur peut corriger
© P. Sicard - Cours Réseaux Détections et corrections d’erreurs 13 © P. Sicard - Cours Réseaux Détections et corrections d’erreurs
14

• Problème :
Le code correcteur de Hamming
• Quelle est la valeur minimale de r permettant de corriger les
erreurs simples dans des trames de m bits de données et r de • Propriété : nécessite le nombre minimal de bit de contrôle pour
contrôle ? corriger une erreur
• On a 2m mots du code possibles (toutes les combinaisons • m=1 , r=2
possibles des données)
• jusqu’à m=4 , r= 3
• 1 mot juste peut aboutir à n=m+r mots différents de 1 bit
(chacun des n bits peut être erroné: n erreurs possibles) • jusqu’à m=11 r=4 ....
• Il faut que nombre de mots possibles sur n bits soit supérieur • Utilisable pour n’importe quelle taille de donnée
au nombre de mots justes plus le nombre de mots faux (avec • Les bits de contrôle sont les bits de numéro égal à une puissance de 2
1 erreur).
• En effet, pour pouvoir corriger une erreur, il faut que chacun des Bits de contrôle
mots justes ou faux puissent être tous différents. Sinon on ne
pourra pas retrouver le mot juste.
• Il faut donc que 2m+n*2m ≤ 2n , soit (n+1)2m ≤ 2(m+r), 1 2 3 4 5 6 7 8 9 10 11 12
• soit (m + r + 1) ≤ 2 r

• Les codes correcteurs d’erreur “coûtent” chers

© P. Sicard - Cours Réseaux Détections et corrections d’erreurs 15 © P. Sicard - Cours Réseaux Détections et corrections d’erreurs 16
 Le code correcteur de Hamming Le code correcteur de Hamming
• Les bits de données qui servent au calcul d’un bit de contrôle de • Exemple: Bit de contrôle 1
numéro X sont ceux tel que X apparaît dans la décomposition en – Trame envoyée:
1 2 3 4 5 6 7 8 9 10 11 12
puissance de 2 de leur numéro.
0 0 1 1 0 0 0 1 1
• Exemple: 7 = 1 + 2+ 4 donc 7 apparaît dans le calcul de 1, de 2 et
de 4 Bit de contrôle 2
1 2 3 4 5 6 7 8 9 10 11 12
1 calculé de telle façon que (1, 3, 5, 7, 9, 11, …) parité paire 0 0 0 1 1 0 0 0 1 1
2 calculé de telle façon que (2, 3, 6, 7, 10, 11,…) parité paire
Bit de contrôle 3
4 calculé de telle façon que (4, 5, 6, 7, 12, …) parité paire
... 1 2 3 4 5 6 7 8 9 10 11 12

Calcul de parité 0 0 0 1 1 1 0 0 0 1 1
• Exemple :
Bit de contrôle 4
1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 4 5 6 7 8 9 10 11 12 0 0 0 1 1 1 0 0 0 0 1 1
0 0 1 1 0 0 0 1 1
• A destination on recalcule les bits de contrôle...
© P. Sicard - Cours Réseaux Détections et corrections d’erreurs 17 © P. Sicard - Cours Réseaux Détections et corrections d’erreurs 18

A la réception
Trame reçue Le code correcteur de Hamming
1 2 3 4 5 6 7 8 9 10 11 12
0 0 0 1 1 01 0 0 0 0 1 1

J
F
F
• Quelle est la distance de Hamming de ce code correcteur ?
J
– Si on change un bit de donnée, forcément au moins deux bits de
• Calcul de 1 (1, 3, 5, 7, 9 , 11): 2 bits à 1: pair donc juste contrôle change aussi, donc h=3
• Calcul de 2 (2, 3, 6, 7, 10, 11): 1 bit à 1 : impair donc faux
• Calcul de 4 (4, 5, 6, 7, 12) : 3 bits à 1 : impair donc faux • Que se passe-t il si c’est un bit de contrôle qui est erroné ?
• Calcul de 8 (9,10, 11, 12) : 2 bits à 1: pair donc juste – Seul une erreur apparait pour ce bit de contrôle, cela ne sert à rien
• La somme des numéros des bits de contrôle erronés donne le mais on peut le corriger
numéro du bit qui porte l’erreur

• 2 + 4 = 6 , le 6ème bit est faux, on peut le corriger

© P. Sicard - Cours Réseaux Détections et corrections d’erreurs 19 © P. Sicard - Cours Réseaux Détections et corrections d’erreurs 20
 Le code correcteur de Hamming Le code correcteur de Hamming
généralisé
• Que se passe-t il si deux bits sont erronés ?
• Exemple • On rajoute un bit de contrôle supplémentaire
Trame envoyée • Bit de parité sur l’ensemble de la trame
1 2 3 4 5 6 7 8 9 10 11 12 Trame envoyée
1 2 3 4 5 6 7 8 9 10 11 12
0 0 0 1 1 1 0 0 0 0 1 1
0 0 0 1 1 1 0 0 0 0 1 1 1

Trame reçue Trame reçue

1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 4 5 6 7 8 9 10 11 12
0 0 1 1 1 0 0 0 0 0 1 1 1
0 0 1 1 1 0 0 0 0 0 1 1

• On trouve impairs pour un 1et 4,

• On trouve impairs pour un 1et 4, • Le bit de parité supplémentaire est juste, il devrait être faux si le
• On corrige le bit 5, on rajoute une troisième erreur !!! bit 5 seulement était faux
• On ne peut pas corriger mais on a détecté au moins 2 erreurs
© P. Sicard - Cours Réseaux Détections et corrections d’erreurs 21 © P. Sicard - Cours Réseaux Détections et corrections d’erreurs 22

Correction de rafale d’erreur Autres exemple de codes

• On peut utiliser la correction d’erreur de Hamming en calculant les correcteur utilisés
bits de contrôle sur les colonnes des bits de données

• Code de Reed-Salomon: utilisé pour l’ADSL et les DVDs/CDs

Bits de contrôle •Permet de corriger de grosses rafales d’erreur (rayure sur un CD)
si il est de plus lié à des techniques d’entrelacement (dispersion
des erreurs consécutives)

© P. Sicard - Cours Réseaux Détections et corrections d’erreurs 23 © P. Sicard - Cours Réseaux Détections et corrections d’erreurs 24
 Exercice

• Pour détecter les erreurs on transmet les données par blocs de n lignes
de k bits. On rajoute un bit de parité par ligne et un par colonne.
• Quelle est la distance de Hamming de ce code ?
• Quels types d’erreur peut on détecter ?
• Peut on corriger des erreurs ? Si oui comment ?

© P. Sicard - Cours Réseaux Détections et corrections d’erreurs 25