Chapitre 3: Liaison de Données - Controle d'erreur PDF

Chapitre 2 La couche liaison de données 1 Sous couche LLC Contrôle d’erreurs 2  Erreurs de transmission Des erreurs sont dues aux canaux de transmission. Un ou plusieurs bits d’information ( trame ) peuvent être changés en même temps durant la transmissi...

Chapitre 2 La couche liaison de données 1 Sous couche LLC Contrôle d’erreurs 2  Erreurs de transmission Des erreurs sont dues aux canaux de transmission. Un ou plusieurs bits d’information ( trame ) peuvent être changés en même temps durant la transmission. Les trames peuvent être corrompues ou perdues Les erreurs sont causées par – L’interférence (Bruit) – L’atténuation 3  Comment prévenir les erreurs Pour réduire les interférences – Blinder les fils – S’assurer que les câbles sont loin des sources d’interférence (Bruit) Pour réduire l’atténuation – Ajuster l’équipement de transmission et améliorer la qualité de la connexion – Utiliser des amplificateurs et des répéteurs – Utiliser du câble de meilleur qualité Mais le risque d’erreurs existe toujours  il doit pas dépasser un certain seuil 10-8 à 10-10 4  Contrôle d’erreurs Il faut pouvoir détecter et corriger les erreurs. De façon générale pour transmettre k bits , on ajoute r bits dites bits de contrôle. Au total on transmis n= k + r bits On parle de code(n, k). Les bits de contrôle sont calculés en fonction des bits de l’information À la réception les bits de contrôles seront recalculés afin de s’assure si l’information est bien reçus ou non Le rendement d’un code est définit R= k/n 5  Techniques de contrôle d’erreurs Il existe plusieurs méthodes de contrôle d’erreurs : Détection ( code détecteur ) Ce type de code permet de détecter le changement de un ou plusieurs bits. Mais il na pas la possibilité de corriger ces erreurs. Détection et correction ( code correcteur ) Ce type de code permet de détecter le changement de un ou plusieurs bits. En plus il possède la capacité de corriger ces erreurs. 6  Détection d’erreurs Les techniques les plus utilisées pour la détection sont : VRC ( Vertical Redundancy Check ) : Parité vertical LRC ( Longitudunal Redundancy Check ) : parité longitudinale CRC ( Cyclic Redundancy Check) : Vérification polynomiale 7  Parité : VRC( Vertical Redundancy Check ) Le plus vieux mécanisme Calculer la parité est rajouter un bit à l’information envoyé – Parité paire : si le nombre de 1 dans l’information est paire alors le bit de parité est égale à 1 , sinon 0 – Parité impaire : si le nombre de 1 dans l’information est impaire alors le bit de parité est égale à 1 , sinon 0 Exemple : si on utilise une parité impaire pour l’information 1100100 on rajoute 1. l’information a envoyé 11001001 8  Détection des erreurs grâce au code VRC La détection d'erreur avec le VRC consiste a : – recalculer le bit de parité a la réception et le comparer avec le bit de parité reçu Exemple : l’information reçues 1100100 1 le bit de parité qui correspond à l’information : 1100100 est égal à 1 donc l’information reçues est correcte Capacité de détection : si un seule bit change alors la parité change  on détecte l’erreur mais on peut pas savoir quel est le bit qui a changé. Si le nombre de de bits qui change est pair  impossible de détecter l’erreur 1100100  1110000 9  Parité longitudinale : LRC Appliquer le principe de la parité ( paire ou impaire )aux colonnes d’un bloc de données Exemple le message DATA: Caractère Code ASCII D 1000100 A 1000001 T 1010100 A 1000001 LRC 1101111 10  C’est un code meilleur que le VRC Impossible de détecter l’erreur si deux bits sont changés en même temps sur la même colonnes Pour plus d’efficacité Rajouter un contrôle sur les lignes Caractère ASCII Bit de D 1000100 parité A 1000001 1 T 1010100 1 A 1000001 0 LRC 1101111 1 1 11  Vérification polynomiale CRC ( Cyclic Redundancy Check) Utilisation d’un polynôme générateur ayant des caractéristiques mathématique particulières. Effectuer la division de l’information sur ce polynôme. Le reste de la division est utilisé pour le contrôle. 12  Remarques L'arithmétique est faite modulo 2 : Il n'y a pas de retenue dans l'addition et la soustraction L'addition et la soustraction sont équivalentes à un OU EXCLUSIF 1+1 = 0 1-1 =0 1+0 = 1 1-0 =1 0+0 = 0 0+0 =0 0+1 = 1 0-1 =1 13  Vérification polynomiale Rappel : Une information en binaire peut être écrite sous la forme polynomiale suivant les puissances de 2 (1110)2 1* 23  1* 2 2  1* 21  0 * 2 0 Dans le cas général : (uk uk  1...........u1u0 ) 2 uk. X k  uk  1. X k  1 ...........  u1. X 1  u0. X 0 avec u i  [0,1]. Exemple : La suite 1100101 est représentée par le polynôme 1100101 1. X 6  1. X 5  0. X 4  0. X 3  1. X 2  0. X 1  1. X 0  X 6  X 5  X 2 1 14  Calcul du CRC ( Cyclic Redundancy Check) On choisit un polynôme appelé polynôme générateur G(X) de degré n Exemple : polynôme générateur X4+X2+X de degré 4 Soit une information sur m bits représentée sous la forme d’un polynôme M(X) de dégrée (m-1) 15  Calcul du CRC Pour calculer le CRC : – multiplier le polynôme M(X) par X n ( n est le degré du polynôme générateur ) – effectuer une division de Xn.M(X) par G(x) , – on obtient le Quotient Q(X) et le reste R(X) XnM(X)=Q(X).G(X)+R(X) – Le CRC correspond au reste de la division R(X) Donc l’information envoyée est égale à : XnM(X)+R(X) 16  Exemple Soit l’information 11100111 et le polynôme générateur X4+X2+X G(X)= X4+X2+X M(X)= X 7  X 6  X 5  X 2  X1  1 Multiplier M(X) par X4 X 4.M(X)  X11  X10  X 9  X 6  X 5  X 4 111001110000 17 X11  X10  X 9  X 6  X 5  X 4 X4+X2+X X11  X 9  X 8 X7 + X6 + X3 +X2 + 1 X10  X 8  X 6  X 5  X 4 X10  X 8  X 7 X7  X6  X5  X 4 X7  X5  X 4 R(X) X  X  X 11103 2 X6 L’information à envoyer : X6  X 4  X3 11 10 9 6 5 4 3 2 X 4  X3 X X X X X X X X X X4  X2  X 11100111 1110 X3  X 2  X 18 1110 0 1 11 0000 10110 10110 11001101 010101 10110 111 L’information à envoyer : 00000 11100111 1110 1111 00000 Remarque : 11110 Toutes les opérations se font 10110 en binaire modulo2 010000 1+1 =0 10110 1+0 = 1 11000 0+0 =0 10110 Effectuer des ou exclusifs 01110 19  Détection des erreurs A la réception de l’information : Diviser XnM(X)+R(X) sur G(X) Si le reste de la division est nul alors l’information est correcte Si non il y une erreur Remarque : XnM(X)=Q(X).G(X)+R(X)  XnM(X) + R(X ) =Q(X).G(X) XnM(X) + R(X ) est divisible par G(X) 20  11 10 9 6 5 4 3 2 X X X X X X X X X X4+X2+X 11 9 8 X X X X7 + X6 + X3 +X2 + 1 10 8 6 5 4 3 2 X X X X X X X X 10 8 7 X X X 7 6 5 4 3 2 X X X X X X X 7 5 4 3 2 X X X X X X 6 3 2 X X X X 6 4 3 X X X 4 2 X X X 4 2 X X X 0 L’information est correcte 21  1110 0 111 1110 10110 10110 11001101 10101 10110 111 00000 1111 00000 11111 10110 010011 10110 10110 10110 L’information est correcte 00000 22  Correction d’erreur par retransmission La méthode la plus simple pour corriger une erreur c’est de demander une retransmission Un récepteur qui détecte une erreur demande une retransmission jusqu’à ce qu’il n’y est plus d’erreur. 23  Remarque Un code polynômial permet de détecter toutes les erreurs d'ordre inferieur au degré du polynôme générateur. Le polynôme doit avoir deux termes ou plus. Le polynôme ne doit pas diviser 1+XR 24  Normalisation des polynômes générateurs Le CCITT a recommandé un certain nombre de polynômes : CRC - 12 x12  x11  x 3  x 2  x  1 CRC - 16 x16  x15  x 2  1 CRC - CCITT x16  x12  x 5  1 CRC - 32 x 32  x 26  x 23  x 22  x16  x12  x11  x10  x 8  x 7  x 5  x 4  x 1 25 Calcul du CRC par des additions successives Le CRC est calculé pour chaque trame émise ou reçue. Pour accélérer le traitement , cette opération est effectuée par un circuit. Pour le calcul du CRC  Effectuer des additions successives. Le Circuit est à base d’un registre à décalage et des portes XOR 26  Calcul du CRC par des additions successives Soit G(X) un polynôme générateur de degré n. On le transforme en un mot binaire. Exemple : Avec le polynôme générateur X4+X2+X, on obtient 10110. On ajoute n zéros au mot binaire à transmettre où n est le degré du polynôme générateur. Exemple : On souhaite transmettre le mot 11100111 en utilisant le polynôme générateur X4+X2+X, on obtient alors 11100111 0000. On va additionner itérativement à ce mot, le mot correspondant au polynôme générateur. Ce mot obtenu correspond au CRC à ajouter au mot avant de l’émettre. 27  111001110000 10110 010101110000 10110 000011110000 10110 000001000000 10110 000000011000 10110 000000001110 code CRC = 1110 donc l’information a transmettre 10011 1110 28  la réception , refaire la même opération. i le résultat est nul alors l’information est correcte. 11100111 1110 10110 01010111 1110 10110 000011111110 10110 000001001110 10110 000000010110 10110 000000000000 ste de la division est nul donc l’information est corre 29 Exercice 1 : Soit le polynôme générateur G(X)= X4+X2+X Calculer le CRC pour les deux informations suivantes : 1111011101 1100010101 Peut-on détecter l’erreur si deux bits de l’information sont inversés ? 30  Exercice 2 : On désire transmettre le message 101001. Pour le contrôle d’erreurs utiliser le polynôme générateur g(x) = x+1. Calculer le CRC et donner la trame envoyée. Peut-on détecter l’erreur si deux bits de l’information sont inversés ? 31 Exercice 1 : G(X)= X4+X2+X 1111011101 = X9+X8+X7+X6+X4+X3+X2+1 M(X)*X4= X13+X12+X11+X10+X8+X7+X6+X4 32 X13+X12+X11+X10+X8+X7+X6+X4 X4+X2+X 33