Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Contrôle d’erreurs Contrôle de parité Code de Hamming Codes polynomiaux Réseaux

Contrôle d’erreurs Contrôle de parité Code de Hamming Codes polynomiaux Réseaux (couches basses) Lucie Galand Université Paris Dauphine L3 MIDO Année 2012-2013 1/36 Contrôle d’erreurs Contrôle de parité Code de Hamming Codes polynomiaux Protection contre les erreurs 2/36 Contrôle d’erreurs Contrôle de parité Code de Hamming Codes polynomiaux Plan du cours Contrôle d’erreurs Codes de contrôle de parité Code de Hamming Codes polynomiaux 3/36 Contrôle d’erreurs Contrôle de parité Code de Hamming Codes polynomiaux Plan du cours Contrôle d’erreurs Codes de contrôle de parité Code de Hamming Codes polynomiaux 4/36 Contrôle d’erreurs Contrôle de parité Code de Hamming Codes polynomiaux Problématique Transmission des données signal peut être déformé signal peut être altéré par du bruit = ⇒Erreur d’interprétation à la réception Erreur signal représentant le bit "1" interprété comme un "0" signal représentant le bit "0" interprété comme un "1" 5/36 Contrôle d’erreurs Contrôle de parité Code de Hamming Codes polynomiaux Principe général Détection d’erreurs inclusion de suﬃsamment de redondance dans les données à transmettre pour que le récepteur puisse détecter les erreurs et demander alors la retransmission des trames erronnées • codes détecteurs d’erreurs Correction d’erreurs inclusion de suﬃsamment de redondance dans les données à transmettre pour que le récepteur puisse reconstituer les données originales à partir des données reçues • codes correcteurs d’erreurs 6/36 Contrôle d’erreurs Contrôle de parité Code de Hamming Codes polynomiaux Exemples Détection par répétition : message codé = double exemplaire du message initial message à transmettre : 001 message codé : 000011 message reçu : • 000011 − →aucune erreur détectée • 010011 − →une erreur détectée • 110011 − →aucune erreur détectée ! 7/36 Contrôle d’erreurs Contrôle de parité Code de Hamming Codes polynomiaux Exemples Correction par répétition : message codé = triple exemplaire du message initial message à transmettre : 001 message codé : 000000111 message reçu : • 000000111 − →001 : aucune erreur détectée • 010000111 − →001 : une erreur corrigée (majorité) • 011000101 − →101 : une erreur corrigée mais une autre détectée et mal corrigée ! 8/36 Contrôle d’erreurs Contrôle de parité Code de Hamming Codes polynomiaux Déﬁnitions Codes (détecteurs ou correcteurs) : enrichissement de la séquence de bits à transmettre par ajout d’information à base de bits de redondance mot de code : • m bits de données • r bits de redondance • séquence de n = m + r bits nb mots de codes légaux ≤nb mots de code possibles Taux d’erreurs : nb moyen de bits transmis en erreur / nb total bits transmis 9/36 Contrôle d’erreurs Contrôle de parité Code de Hamming Codes polynomiaux Distance de Hamming Poids de Hamming d’un mot : nombre de bits à "1" qu’il contient Distance de Hamming entre deux mots de même longueur : nombre de positions binaires qui diﬀèrent entre les 2 mots poids de Hamming de la somme binaire des 2 mots Distance de Hamming d’un code : distance minimum entre tous les mots du code Exemple : poids de Hamming de 10110101001 : 6 distance de Hamming entre 10110101001 et 00110110001 : 3 • 10110101001 - 00110110001 • 10110101001 XOR 00110110001 = 10000011000 10/36 Contrôle d’erreurs Contrôle de parité Code de Hamming Codes polynomiaux Propriété d’un code Capacité de détection (correction) d’un code : conﬁgurations erronnées qu’il est capable de détecter (corriger) une erreur simple (resp. double ou d’ordre p) aﬀecte une seule (resp. 2 ou p) position(s) binaire(s) d’un mot si la distance de Hamming entre deux mots de code est d, alors il faut d erreurs simples pour transformer un mot en l’autre • ex. : 10001001 et 10110001 pour détecter des erreurs d’ordre d, la distance de Hamming du code doit être d’au moins d+1 pour corriger des erreurs d’ordre d, la distance de Hamming du code doit être d’au moins 2d+1 11/36 Contrôle d’erreurs Contrôle de parité Code de Hamming Codes polynomiaux Propriété d’un code Exemple : code C comprenant uniquement les mots : 0000000000, 0000011111, 1111100000 et 1111111111 distance de Hamming du code : 5 transmission de 0000000000 réception de 0010000000 − →erreur détectée et corrigée réception de 1101000000 − →erreurs détectées mais non corrigées réception de 0000011111 − →erreurs ni détectées ni corrigées 12/36 Contrôle d’erreurs Contrôle de parité Code de Hamming Codes polynomiaux Plan du cours Contrôle d’erreurs Codes de contrôle de parité Code de Hamming Codes polynomiaux 13/36 Contrôle d’erreurs Contrôle de parité Code de Hamming Codes polynomiaux Contrôle de parité Code de contrôle de parité paire : le nombre de bits à 1 du code est pair (somme booléenne nulle) introduction d’un bit supplémentaire (bit de parité) pour assurer la parité Exemple : transmission de caractères du code ASCII sur 7 bits 0 = 1001111 1 S = 1010011 0 I = 1000011 1 Remarques : code capable de détecter toutes les erreurs en nombre impair, mais aucune en nombre pair ! code de contrôle de parité impaire déﬁni de la même manière 14/36 Contrôle d’erreurs Contrôle de parité Code de Hamming Codes polynomiaux Bit de parité Remarques : l’International Standard Book Number (ISBN) permet d’identiﬁer des livres : le dernier des dix chiﬀres est un bit de parité le numéro de sécurité sociale comporte une clé qui permet de détecter une erreur les cartes de crédit utilisent des bits de parité 15/36 Contrôle d’erreurs Contrôle de parité Code de Hamming Codes polynomiaux Parité longitudinale et transversale Association d’un double codage de la parité : vertical : VRC (Vertical Redundancy Checking) longitudinal : LRC (Longitudinal Redundancy checking) Blocs de k × n bits : bloc de données de taille (k −1) × (n −1) parité appliquée sur chaque ligne et chaque colonne du bloc de données matrice résultante de taille k × n Exemple : transmission de caractères du code ASCII sur 7 bits 0 = 1001111 1 S = 1010011 0 I = 1000011 1 1011111 0 16/36 Contrôle d’erreurs Contrôle de parité Code de Hamming Codes polynomiaux Parité longitudinale et transversale Une erreur simple peut-elle être détectée ? une erreur simple modiﬁe simultanément la parité d’une ligne et d’une colonne Correction : inverser le bit situé à l’intersection de la ligne et de la colonne ayant une parité incorrecte Exemple : Bloc transmis : 0 = 1001111 1 S = 1010011 0 I = 1000011 1 1011111 0 Bloc reçu : 0 = 1001111 1 S = 1010011 0 I = 1001011 1 1011111 0 17/36 Contrôle d’erreurs Contrôle de parité Code de Hamming Codes polynomiaux Parité longitudinale et transversale Une erreur double peut-elle être détectée ? une erreur double modiﬁe la parité de 2 ou 4 lignes/colonnes Exemples : Bloc transmis : 0 = 1001111 1 S = 1010011 0 I = 1000011 1 1011111 0 Bloc reçu : 0 = 1101111 1 S = 1010011 0 I = 1001011 1 1011111 0 Autre bloc reçu : 0 = 1001111 1 S = 1000111 0 I = 1000011 1 1011111 0 18/36 Contrôle d’erreurs Contrôle de parité Code de Hamming Codes polynomiaux Parité longitudinale et transversale Une erreur triple peut-elle être détectée ? une erreur triple modiﬁe la parité de 2, 4 ou 6 lignes/colonnes Exemples : Bloc transmis : 0 = 1001111 1 S = 1010011 0 I = 1000011 1 1011111 0 Bloc reçu : 0 = 1101111 1 S = 1010001 0 I = 1001011 1 1011111 0 Autre bloc reçu : 0 = 1001111 1 S = 1000110 0 I = 1000011 1 1011111 0 19/36 Contrôle d’erreurs Contrôle de parité Code de Hamming Codes polynomiaux Parité longitudinale et transversale Une erreur triple peut-elle être détectée ? une erreur triple modiﬁe la parité de 2, 4 ou 6 lignes/colonnes Attention : une erreur triple peut faire croire à une erreur simple (correction inadaptée) Bloc transmis : 0 = 1001111 1 S = 1010011 0 I = 1000011 1 1011111 0 Bloc reçu : 0 = 1101101 1 S = 1010011 0 I = 1100011 1 1011111 0 20/36 Contrôle d’erreurs Contrôle de parité Code de Hamming Codes polynomiaux Parité longitudinale et transversale Bilan le contrôle de parité LRC et VRC permet de détecter 1, 2 ou 3 erreurs simples s’il y a une erreur simple, on peut la corriger Plus de 3 erreurs ? Bloc transmis : 0 = 1001111 1 S = 1010011 0 I = 1000011 1 1011111 0 Bloc reçu : 0 = 1101101 1 S = 1010011 0 I = 1100001 1 1011111 0 = ⇒erreurs non détectées 21/36 Contrôle d’erreurs Contrôle de parité Code de Hamming Codes polynomiaux Plan du cours Contrôle d’erreurs Codes de contrôle de parité Code de Hamming Codes polynomiaux 22/36 Contrôle d’erreurs Contrôle de parité Code de Hamming Codes polynomiaux Code de Hamming Principe : bits de uploads/S4/ c3-erreurs.pdf