Techniques de détection & de correction des erreurs de

Le code de Hamming est donc un code binaire parfait On peut de la même manière construire un code de Hamming pour toutes les valeurs de k La matrice de contrôle de parité est constituée de tous les 2k – 1 vecteurs non nuls de longueur k On a donc toujours un code 1-correcteur parfait La matrice H est de taille (2k –1) x k

Codes Correcteurs dErreurs Cours 1 + Introduction + Codes

Exemple de code d´etecteur et correcteur d’erreur : le code de r´ep´etition Technique de codage : Pour un bit d’information, 3 bits sont envoy´es (cad cod´es) tels que: 0 → 000 1 → 111 Technique de d´ecodage : Le d´ecodage se fait par vote majoritaire Par exemple, si le mot re¸cu est 001, alors on d´eduit que le bit ´emis

Techniques de détection & de correction des erreurs de

R Kanawati, Cours réseaux, IUT de Villetaneuse, département GTR, 1er année, 2002-2003 Code de Hamming n La distance de Hamming entre deux séquences binaires de même taille est égale au nombre de bits de rang identique par lesquels elles différent n Exemple : d(1100110, 1010110) = 2 n Soit un code composé de N mot valides

TD Réseau Les codes correcteurs et les codes détecteurs

Le code de Hamming (2) Retrouver l’erreur dans un mot de Hamming Si les bits de contrôle de réception C0 2C 0 1C 0 0 valent 0, il n’y a pas d’erreur sinon la valeur des bits de contrôle indique la position de l’erreur entre 1 et 7 Si C0 0 vaut 1, les valeurs possibles de C 0 2C 0 1C 0 0 sont 001, 011, 101, 111, c’est-à-dire 1, 3

Cours : Codes correcteurs

Cours : Codes correcteurs Emily Clement Enseignant : Delphine Boucher Master 1 de Mathématiques Semestre 2 2015-2016

Theorie des codes´ correcteurs d’erreurs I

1 6 Capacité de détection et de correction d'un code 7 1 8 Bornes sur les codes 9 1 9 Codes Parfaits 10 1 10 Exercices 11 Chapitre 2 Codes linéaires 15 2 1 Dé nition 15 2 2 Matrice génératrice 15 2 4 Code dual et matrice de contrôle 16 2 9 Distance minimale 18 2 12 Décodage 21 2 16 Rayon de couverture 24 2 17 Construction de

Le contrôle d’erreur - imag

• Distance de Hamming du code complet (ou distance minimale) h = { Min Disth(x1, x2) ; x1 et x2 ∈ M et x1≠x2} M est l’ensemble des 2 m mots de codes possibles si on admet que les r bits de contrôle sont calculés en fonction des m bits de données Contrôle d’erreur : un modèle d’étude

48 Application des corps ﬁnis aux codes correcteurs d’erreur

4 8 Application des corps ﬁnis aux codes correcteurs d’erreur Cette section se veut une introduction succincte et très partielle à la vaste théorie des codes correcteurs, l’une des applications pratiques les plus célèbres de la théorie des corps

Mot information Mot code

RSE : exercices MRI 20-21 7 La chaîne 1011001 a été reçue par une entité de la couche liaison dont le protocole implique l'utilisation du code de Hamming correcteur d'une erreur Si vous savez qu'au maximum une seule erreur s'est produite, corrigez la chaîne et donneu les bits d'information transmis originalement 8

Techniques de détection & de

correction des erreurs detransmission

Rushed KANAWATI

2 / 15R. Kanawati, Cours réseaux, IUT de Villetaneuse, département GTR, 1er année, 2002-2003Sommaire

nProblématique nPrincipe de détection des erreurs nTechniques de détection des erreurs uCodes de parité uCode polynomiale (CRC) nTechniques de correction des erreurs uCodes auto-correcteurs : code de Hamming uCorrection par demande de retransmission nBibliographie Le plan de ce cours est inspiré du cours fait par B. Cousin, IFSIC, Université de Rennes

3 / 15R. Kanawati, Cours réseaux, IUT de Villetaneuse, département GTR, 1er année, 2002-2003Problématique

1001001Entité A

Entité B1000001Erreur

• Comment B peut détecter l'occurrence d'une erreur ? • Comment B peut localiser une erreur ? • Comment B peut corriger une erreur ?

4 / 15R. Kanawati, Cours réseaux, IUT de Villetaneuse, département GTR, 1er année, 2002-2003Approche naïve : la répétition

nDétection d'erreurs uLe message envoyé est constitué du double du message initial. uEnvoyer 10010011001001 au lieu de 1001001 uLe récepteur détecte une erreur si les exemplaires ne sont pas identiques. nAuto-correction uLe message envoyé est constitué du triple du message initial. uEnvoyer 100100110010011001001 au lieu de 1001001 uLe message correcte correspond aux 2 exemples identiques.

5 / 15R. Kanawati, Cours réseaux, IUT de Villetaneuse, département GTR, 1er année, 2002-2003Quelques remarques

nLa détection et la correction des erreurs nécessitent d'introduire de la redondance dans les messages transmis. nCertaines erreurs ne peuvent pas être détectées uExemple : la même erreur sur les deux exemplaires nCertaines erreurs détectées ne peuvent pas être corrigées uExemple : Une erreur différente sur au moins deux exemplaires. nCertaines erreurs sont mal corrigées uune même erreur sur deux exemplaires simultanément nL'auto-correction nécessite plus de redondance que la simple détection.

6 / 15R. Kanawati, Cours réseaux, IUT de Villetaneuse, département GTR, 1er année, 2002-2003Détection des erreurs :

Code de pariténLa parité peut être paire ou impaire. nPour une parité paire (impair), on protège une séquence de k bits par l'ajout de r bits de sorte que le nombre de bits ayant la valeur 1 soit pair (impair)

Ce code détecte les erreurs en nombre impair.

Pas de correction automatique. Lettre

G T

RCode ASCII

1110001

0100001

0100101(parité paire)

11100010

01000010

01001011(parité impaire)

11100011

01000011

01001010

7 / 15R. Kanawati, Cours réseaux, IUT de Villetaneuse, département GTR, 1er année, 2002-2003Détection des erreurs :

Code polynomial

nA toute séquence de bits on associe un polynôme uU = Û U( x) = u0 +u1 .x+ u2 .x2 +...+ u n .xn u1001001 Û X6 +X3+1 nLes séquences envoyés (codés) doivent être un multiple d'un polynôme g(x) dit polynôme générateur. nLe polynôme g(x) est connu à l'avance par l'émetteur et le récepteur.

8 / 15R. Kanawati, Cours réseaux, IUT de Villetaneuse, département GTR, 1er année, 2002-2003Procédure de codage

nSoit P(X) le polynôme associé à la séquence de bits à protéger. nSoit g(x) le polynôme générateur de degré k . nLes calculs sont faits dans le corps Z/2Z u1+1=0; X+X=0; X=-X nOn calcule P'(X) = P(X).Xk uCeci équivaut à un décalage de P(X), de k positions vers la gauche. nOn divise P'(X) par g(x). uP'(X)=Q(X).g(X)+R(X) nLe message envoyé est : P'(X) +R(X) nP'(X)+R(X) = Q(X).g(X) est multiple de g(X)

9 / 15R. Kanawati, Cours réseaux, IUT de Villetaneuse, département GTR, 1er année, 2002-2003Procédure de décodage

nSoit M(X) le message reçu. nOn divise M(X) par g(X) uSi le reste de division est non nul alors : détection d'une erreur. uSinon (reste de division nul) il y a une forte probabilité que la transmission est correcte.

10 / 15R. Kanawati, Cours réseaux, IUT de Villetaneuse, département GTR, 1er année, 2002-2003Exemple

nSoit la séquence 1101 à envoyer ng(x) = x3+x+1 nP(x)=x3+x2+1 nP '(x)=P(x).x3=x6+x5+x3 x

6+x5+x3x

3+x+1 x

3x6x3x4++

x5+x4+X2 x

5+x3+x2x

4+x3+x2+X+1

4+x2+x x

3+x x

3+x+1R(x)=1Message envoyé : 1101001

11 / 15R. Kanawati, Cours réseaux, IUT de Villetaneuse, département GTR, 1er année, 2002-2003Caractéristique du code

polynomiale nLa qualité de la protection dépend du choix du polynôme générateur g(x). nOn démontre par exemple (voir TD 03) que si : ug(x) comporte au moins 2 termes alors les erreurs simples sont détectables. usi g(x) a un facteur irréductible de trois termes alors les erreurs doubles sont détectables ug(x) est multiple de x+1 alors les erreurs en nombre impair sont détectables.

12 / 15R. Kanawati, Cours réseaux, IUT de Villetaneuse, département GTR, 1er année, 2002-2003Correction des erreurs

nDeux approches : uUtilisation de code auto-correcteurs

FExemple : code de Hamming

uCorrection par retransmission

FSi détection d'une erreur alors demander à

l'émetteur de renvoyer le même message.

13 / 15R. Kanawati, Cours réseaux, IUT de Villetaneuse, département GTR, 1er année, 2002-2003Code de Hamming

nLa distance de Hamming entre deux séquences binaires de même taille est égale au nombre de bits de rang identique par lesquels elles différent. nExemple : d(1100110, 1010110) = 2 nSoit un code composé de N mot valides. nLa distance de Hamming de ce code est définie comme la distance minimale qui sépare deux mots valides du code. nExemple : le code : C= [000000, 001110,010101,011011,100011,101101] a une distance de Hamming = 3 nUn code avec une distance d détecte d-1 erreurs et corrige k erreurs où d=2K+1

14 / 15R. Kanawati, Cours réseaux, IUT de Villetaneuse, département GTR, 1er année, 2002-2003Correction par retransmission

nL'émetteur conserve une copie des données qu'il envoie. nLe récepteur applique une méthode de détection des erreurs. nLe récepteur informe l'émetteur de la bonne (resp. mauvaise) réception en lui retournant un paquet spécifique : acquittement positif (resp. négatif) nDans le cas d'un acquittement négatif, l'émetteur doit renvoi le paquet erroné. nUn temporisateur bornant la durée d'attente des acquittements est nécessaire pour assurer la correction du mécanisme lors des pertes de paquets de données. nL'identification des paquets (de données et d'acquittement) est nécessaire pour assurer la correction du mécanisme lors des pertes d'acquittement.

15 / 15R. Kanawati, Cours réseaux, IUT de Villetaneuse, département GTR, 1er année, 2002-2003Pour en savoir plus

nK. Lahèche, Les codes en informatique : codes détecteurs et correcteurs d'erreurs, Hermès,1995. nR. Dapoigny, Les transmissions dans les réseaux informatiques, Support IUT, gaëtan morin éditeur 1999.

Chapitre 5.

nA. Tanenbaum, Réseaux, InterEditions, 1997.quotesdbs_dbs8.pdfusesText_14

[PDF] Techniques de détection & de correction des erreurs de