CODE HAMMMING
A+
TD Réseau Les codes correcteurs et les codes détecteurs Claude Duvallet Matrise Informatique Ann ee 2003-2004 Ann 2003-2004 p. l/22 Présentation (1) Pourquoi ? Des canaux de transmission imparfait entraînant des erreurs lors des échanges de donnée probabilité d’erreur s peut même atteindre 10 org Snipe to vieu e : (cela Utilisation de méthodes de d tection des erreurs et éventuellement de correction des erreurs. Méthodes mises en place au niveau de la couche 2 OSI (« liaison de données »). rlncipe général : Chaque suite de bits (trame) à transmettre est augmentée par ne autre suite de bit dite de redondance ou de contrôle. Pour chaque suite de k bits transmis, on ajoute r bits. On dit alors que l’on utilise un code C(n, k) avec n -k + . Ann ee 2003-2004 – p. 2/22 Hamming : un code détecteur et correcteur d’erreurs. Le CRC (Cycle Redundancy Check) : un code détecteur d’erreurs. Ann ee 2003-2004 – p. 3/22 Le code de Hamming (1) Structure d’un mode de code de Hamming les m bits du message à transmettre et les n bits de contrôle de parité. ongueur totale : 2n — 1 longueur du messages : m = (2n — 1) — n n parle de code x —y où x = n + m et y = m. Exemple de code de Hamming un mot de code 7 – 4 a un coefficient d’efficacité de 4/7 = 57 %, un mot de code 15 un mot de code 31 11 a un coefficient d’efficacité de 11/15 73 — 26 a un coefficient d’efficacité de 26/31 83 Les bits de contrôle de parité Ci sont en position 2i pour ,2,… Les bits du message Dj occupe le reste du message. Dl DO CO sont 001, Oli, 101, 111, cest-à-dire l, 3, 5, 7. • Si Cl vaut 1, les valeurs possibles de C2 Cl CO sont 010, 01 1, 10, 11, c’est-à-dire 2,3, 6, 7. ??? Si C2 vaut 1, les valeurs possibles de C2 Cl CO sont 100, 101, 110, 111, c’est-à-dire 4, 5, 6, 7. Exercice : y a-t-il une erreur dans le mot suivant ? Ann ‘ ee 2003-2004 – p. 5/22 Le code de Hamming (3) Exercice (Correction) p. 7/22 Le code de Hamming (5) C2 vaut O pour pouvoir rendre pair 1 + 0+ 1 (les bits d’indices 7, 6, 5) 10100 Cl vaut 1 pour pouvoir rendre pair 1 + 0+ O (les bits d’indices 7, 6, 3) 101001 CO vaut O pour pouvoir rendre pair 1 + 1 + O (les bits d’indice 7, 5, 3) 1010010 Ann ‘ ee 2003-2004 – p. 8/22 Le code de Hamming (6)
Soit un mot de Hamming de longueur 15 0011, 0101, 0111, 1001, 1011, 1101, 111) soit (1, 3, 5, 7, 9, 11, 13, 15). Si Cl vaut 1, les valeurs possibles sont (0010, 0011, 0110, 0111 1001, 1010, 1011, 111) soit (2, 3, 6,7, 10, 11, 14, 15). Si C2 vaut 1, les valeurs possibles sont (01 00, 0101, 0110, 0111, 1100, 1101, 1110, Si vaut 1, les valeurs possibles sont (1000, 1001, 1010, 1011, 111) soit (8, 9, 10, 11, 12, 13, 14, 15). Ann ee 2003-2004 – p. 10/22 Le code de Hamming (8) Dans le message considéré on a : CO = I + 0+1+ C3 C2 Cl CO vaut 0000.
Il n’y a donc pas d’erreur dans le message reçu. Ann ee 2003-2004 – p. 11/22 Le CRC (1) Représentation sous forme polynomiale des suites de bits à transmettre : M -ml m2 … mn représentée par le polynôme l(x) = mn + mn—l x + xn—l Exemple : La suite 11 000101 est représentée ar le polynôme X6 + X5 + 0x4 + 0x3 + X2 + 54×2+1 polynômes générateurs possédant des propriétés mathématiques particulières : CRC-12=x12+x11+x3+x2+x+1 CRC-16 = X16+ XI 5 +1 CRC-CCITT = XIE X12 + xs + 1 CRC-32 = x32 + x26 12 10 7 4 Ann 2003-2004 – p. 12/22 Le CRC (2)
En émission on ajoute au message à émettre un code contrôle tel le polynôme correspondant au message plus le code de contrôle soit divisible par le polynôme générateur. En réception : le message reçu qui contient les données et le CRC doit être divisible par le polynôme générateur. On vérifie donc par une division euclidienne en base 2 que le reste de la division est nulle. Ann ee 2003-2004 – p. 13 ajouter itérativement à ce mot, le mot correspondant au polynôme générateur jusqu’à ce que le mot obtenu soit inférieur polynôme générateur.
Ce mot obtenu correspond au CRC ? ajouter au mot avant de l’émettre. On effectue donc une division euclidienne dans laquelle on ne tient pas compte du quotient. Ann ‘ ee 2003-2004 – p. 14/22 Le CRC (4) Exemple d’émission d’un mot : souhaite transmettre le message suivant 1 11011101, quel sera CRC à ajouter ? 2. Même question avec le mot 1100010101. 3. Je viens de recevoir les messages suivants : 11 1 1 000101010, 11000101010110, sont-ils corrects ? Ann ee 2003-2004 – p. 17/22 Le CRC (7) Correction : quel CRC à ajouter avant d’émettre le 1100010101 ?