Td reseau codes correcteurs et codes detecteurs réseaux inf

Ce document didactique est destiné aux étudiants universitaires désireux de maîtriser les principes des codes correcteurs et détecteurs d'erreurs, essentiels pour la fiabilité des transmissions de données. Il présente les fondements de ces mécanismes.

Le contenu explore en particulier :

L'introduction aux concepts de détection et de correction d'erreurs.
Le fonctionnement détaillé du code de Hamming, incluant sa structure, détection et correction.
Le mécanisme du CRC (Cyclic Redundancy Check), avec sa représentation polynomiale et ses calculs.

Des exemples et exercices pratiques accompagnent chaque section pour une meilleure compréhension.

Réseaux Informatiques : Td reseau codes correcteurs et codes detecteurs réseaux inf

Télécharger PDF

Les Codes Correcteurs et Détecteurs d'Erreurs

Introduction aux Codes Correcteurs et Détecteurs

Des canaux de transmission imparfaits entraînent des erreurs lors des échanges de données. La probabilité d’erreurs sur une ligne téléphonique est P=10^-4 (cela peut même atteindre 10^-7). L’utilisation de méthodes de détection et éventuellement de correction des erreurs est donc essentielle.

Ces méthodes sont mises en place au niveau de la couche 2 OSI ("liaison de données").

Principe Général du Codage

Chaque suite de bits (trame) à transmettre est augmentée par une autre suite de bits, 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 + r.

À la réception, on effectue l’opération inverse et les bits ajoutés permettent d’effectuer des contrôles à l’arrivée.

Catégories de Codes d'Erreurs

Il existe deux catégories de codes :

Les codes détecteurs d’erreurs
Les codes correcteurs d’erreurs

Le code de Hamming est un code détecteur et correcteur d’erreurs, capable de corriger un certain nombre d'erreurs simples.

Le CRC (Cyclic Redundancy Check) est un code principalement détecteur d’erreurs, très efficace pour identifier des erreurs de rafales.

Le Code de Hamming

Le code de Hamming est une méthode populaire pour la détection et la correction d'erreurs dans les transmissions de données binaires.

Structure d'un Code de Hamming

Un code de Hamming se compose de bits de message à transmettre et de bits de contrôle de parité. Si on utilise r bits de contrôle de parité, la longueur totale n d'un mot de code (y compris les bits de contrôle) est de 2^r - 1. La longueur du message original k est alors k = n - r. On caractérise un code de Hamming par (n, k), où n est la longueur totale du mot de code et k la longueur du message.

Exemple de codes de Hamming et leur efficacité :

Un code de Hamming (7, 4) a un taux d'efficacité de 4/7, soit environ 57%. Il peut corriger une erreur simple.
Un code de Hamming (15, 11) a un taux d'efficacité de 11/15, soit environ 73%. Il peut également corriger une erreur simple.
Un code de Hamming (31, 26) a un taux d'efficacité de 26/31, soit environ 83%.

Les bits de contrôle de parité C_i sont en position 2ⁱ pour i=0, 1, 2, ... Les bits du message D_j occupent le reste du message.

Voici un exemple de disposition pour un code (7, 4) où D représente les bits de données et C les bits de contrôle :

D3 D2 D1 C2 D0 C1 C0
7  6  5  4  3  2  1

Détection d'Erreur avec le Code de Hamming

Pour retrouver l’erreur dans un mot de Hamming, on calcule de nouveaux bits de contrôle, appelés bits de syndrome (souvent notés C'i). Si la concaténation des bits de syndrome C'2C'1C'0 vaut 0 (000 en binaire), il n’y a pas d’erreur détectée. Sinon, la valeur binaire des bits de syndrome indique la position de l’erreur, entre 1 et la longueur totale du mot.

Pour un code (7,4), les bits de syndrome sont calculés en vérifiant la parité des groupes de bits suivants :

Si C'0 vaut 1, cela signifie une erreur dans les positions 1, 3, 5 ou 7 (toutes les positions dont le bit de poids faible est 1).
Si C'1 vaut 1, cela signifie une erreur dans les positions 2, 3, 6 ou 7 (toutes les positions dont le deuxième bit de poids faible est 1).
Si C'2 vaut 1, cela signifie une erreur dans les positions 4, 5, 6 ou 7 (toutes les positions dont le troisième bit de poids faible est 1).

Exercice : Y a-t-il une erreur dans le mot suivant ? 1010110

Correction de l'Exercice de Détection

Pour le mot 1010110, en utilisant la parité paire pour le calcul des bits de syndrome (somme XOR des bits concernés) :

C'2 est le résultat de l'opération XOR des bits aux positions 7, 6, 5, 4 (1 XOR 0 XOR 1 XOR 0 = 0).
C'1 est le résultat de l'opération XOR des bits aux positions 7, 6, 3, 2 (1 XOR 0 XOR 1 XOR 1 = 1).
C'0 est le résultat de l'opération XOR des bits aux positions 7, 5, 3, 1 (1 XOR 1 XOR 1 XOR 0 = 1).

La concaténation des bits de syndrome C'2C'1C'0 vaut 011, ce qui représente la valeur 3 en base 10. Cela indique qu'il y a une erreur à la troisième position (indice 3) du mot. Pour corriger l'erreur, il faudrait inverser le bit à cette position.

Émission avec le Code de Hamming (Parité Paire)

Les bits de contrôle sont calculés pour assurer une parité paire sur des groupes spécifiques de bits. Chaque bit de contrôle est placé à une position correspondant à une puissance de 2 (1, 2, 4, etc.). Un bit de contrôle situé à la position 2ⁱ vérifie tous les bits du mot de code (y compris lui-même) dont la représentation binaire de leur position a le i-ème bit (en partant de la droite, indice 0) défini à 1.

C0 (position 1) vérifie les bits 1, 3, 5, 7, etc. (toutes les positions dont le bit de poids faible est 1).
C1 (position 2) vérifie les bits 2, 3, 6, 7, etc. (toutes les positions dont le deuxième bit de poids faible est 1).
C2 (position 4) vérifie les bits 4, 5, 6, 7, etc. (toutes les positions dont le troisième bit de poids faible est 1).

On souhaite envoyer le message 1010. Pour un code (7,4), le mot de Hamming aura la structure D3 D2 D1 C2 D0 C1 C0. Après insertion des données, le mot initial est 101_0__ (les underscores représentent les positions des bits de contrôle).

Calcul des Bits de Parité

Pour le message 1010, les bits de parité sont calculés comme suit, en plaçant les bits de message aux positions appropriées (D3=1, D2=0, D1=1, D0=0) :

Pour le mot initial (avec les positions des bits de contrôle vides) 1(D3) 0(D2) 1(D1) _ (C2) 0(D0) _ (C1) _ (C0) :
- C2 (position 4) est calculé pour que la parité (somme XOR) des bits aux indices 4, 5, 6, 7 soit paire. Bits de données concernés : D1 (pos 5)=1, D2 (pos 6)=0, D3 (pos 7)=1. Donc C2 XOR D1 XOR D2 XOR D3 = 0. C2 XOR 1 XOR 0 XOR 1 = 0, ce qui donne C2 = 0. Le mot partiel est 10100__.
- C1 (position 2) est calculé pour que la parité (somme XOR) des bits aux indices 2, 3, 6, 7 soit paire. Bits de données concernés : D0 (pos 3)=0, D2 (pos 6)=0, D3 (pos 7)=1. Donc C1 XOR D0 XOR D2 XOR D3 = 0. C1 XOR 0 XOR 0 XOR 1 = 0, ce qui donne C1 = 1. Le mot partiel est 101001_.
- C0 (position 1) est calculé pour que la parité (somme XOR) des bits aux indices 1, 3, 5, 7 soit paire. Bits de données concernés : D0 (pos 3)=0, D1 (pos 5)=1, D3 (pos 7)=1. Donc C0 XOR D0 XOR D1 XOR D3 = 0. C0 XOR 0 XOR 1 XOR 1 = 0, ce qui donne C0 = 0. Le mot final à transmettre est 1010010.

Exercice avec un Code de Hamming de Longueur 15

Soit un mot de Hamming de longueur 15 : 101101111011011

Quels sont les bits de contrôle de parité et le message reçu ?
Est-ce que le mot reçu est correct ?
Quel a été le message transmis (si le mot est correct) ?

Correction de l'Exercice (Hamming 15 bits)

Les bits de contrôle de parité (C0, C1, C2, C3) sont en position 2ⁱ (1, 2, 4, 8).

Pour le mot reçu 101101111011011 (les positions sont numérotées de 1 à 15, de droite à gauche) :

Les bits de contrôle du mot reçu sont : C0 (pos 1)=1, C1 (pos 2)=1, C2 (pos 4)=1, C3 (pos 8)=1. Soit la séquence 1111.
Le message reçu (les bits aux positions non-puissances de 2) est : 10110111010 (bits aux positions 15, 14, 13, 12, 11, 10, 9, 7, 6, 5, 3 dans l'ordre de lecture).

Les bits de syndrome de réception (syndrome) vont être calculés C'3C'2C'1C'0. Chaque C'i est la somme XOR de tous les bits du mot reçu dont la position a le i-ème bit de son écriture binaire à 1 (en partant de la droite pour l'indice 0).

Si C'0 vaut 1, les positions concernées sont (1, 3, 5, 7, 9, 11, 13, 15).
Si C'1 vaut 1, les positions concernées sont (2, 3, 6, 7, 10, 11, 14, 15).
Si C'2 vaut 1, les positions concernées sont (4, 5, 6, 7, 12, 13, 14, 15).
Si C'3 vaut 1, les positions concernées sont (8, 9, 10, 11, 12, 13, 14, 15).

Vérification du Message Reçu (Hamming 15 bits)

En reprenant le mot 101101111011011 (bit 15 à gauche, bit 1 à droite) et en calculant la parité (somme XOR) des groupes de bits correspondants :

C'0 (positions 1, 3, 5, 7, 9, 11, 13, 15) = 1 (pos1) XOR 0 (pos3) XOR 1 (pos5) XOR 1 (pos7) XOR 1 (pos9) XOR 0 (pos11) XOR 1 (pos13) XOR 1 (pos15) = 0 (parité paire).
C'1 (positions 2, 3, 6, 7, 10, 11, 14, 15) = 1 (pos2) XOR 0 (pos3) XOR 0 (pos6) XOR 1 (pos7) XOR 1 (pos10) XOR 0 (pos11) XOR 0 (pos14) XOR 1 (pos15) = 0 (parité paire).
C'2 (positions 4, 5, 6, 7, 12, 13, 14, 15) = 1 (pos4) XOR 1 (pos5) XOR 0 (pos6) XOR 1 (pos7) XOR 1 (pos12) XOR 1 (pos13) XOR 0 (pos14) XOR 1 (pos15) = 0 (parité paire).
C'3 (positions 8, 9, 10, 11, 12, 13, 14, 15) = 1 (pos8) XOR 1 (pos9) XOR 1 (pos10) XOR 0 (pos11) XOR 1 (pos12) XOR 1 (pos13) XOR 0 (pos14) XOR 1 (pos15) = 0 (parité paire).

Le syndrome C'3C'2C'1C'0 vaut 0000. Il n’y a donc pas d’erreur détectée dans le mot reçu.

Puisqu'il n'y a pas d'erreur, le message transmis est identique au message reçu (les bits de données) : 10110111010.

Le CRC (Cyclic Redundancy Check)

Le CRC est une méthode de détection d'erreurs très répandue, utilisée notamment dans les réseaux et le stockage de données, basée sur la division polynomiale.

Représentation Polynomiale des Suites de Bits

Une séquence de bits M = m₁m₂...m_n est représentée par le polynôme I(x) = m_n + m_n-1x + ... + m₁x^n-1. Chaque bit correspond au coefficient d'une puissance de x.

Exemple : La suite 11000101 est représentée par le polynôme 1x⁷ + 1x⁶ + 0x⁵ + 0x⁴ + 0x³ + 1x² + 0x¹ + 1x⁰ = x⁷ + x⁶ + x² + 1. (Notez que la conversion peut varier selon la convention, ici m1 est le coefficient de la plus haute puissance).

Polynômes Générateurs CRC Courants

Le CRC utilise des polynômes générateurs possédant des propriétés mathématiques particulières, optimisées pour la détection d'erreurs :

CRC-12 = x¹² + x¹¹ + x³ + x² + x + 1
CRC-16 = x¹⁶ + x¹⁵ + x² + 1
CRC-CCITT = x¹⁶ + x¹² + x⁵ + 1
CRC-32 = x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x + 1

Principe du CRC en Émission et Réception

En émission, on ajoute au message original un code de contrôle (le CRC) de sorte que le polynôme correspondant au message complet (données + CRC) soit divisible par un polynôme générateur prédéfini.

En réception, le message reçu (qui contient les données et le CRC) est divisé par le même polynôme générateur. On vérifie que le reste de cette division euclidienne en base 2 est nul. Si le reste est non nul, une erreur est détectée.

Calcul du CRC en Émission

1. On choisit un polynôme générateur (G(x)), puis on le représente par une séquence binaire (ses coefficients).

Exemple : Avec le polynôme générateur x⁴ + x² + x, on obtient la séquence binaire 10110 (car 1x^4 + 0x^3 + 1x^2 + 1x^1 + 0x^0).

2. On ajoute m zéros à la séquence binaire du message à transmettre, où m est le degré du polynôme générateur (la plus haute puissance de x).

Exemple : Si l'on souhaite transmettre le mot 11100111 en utilisant le polynôme générateur x⁴ + x² + x (degré m=4), on ajoute 4 zéros, ce qui donne 111001110000.

3. On effectue ensuite une division euclidienne binaire (en utilisant l'opération XOR pour les soustractions) de la séquence ainsi complétée par la séquence binaire du polynôme générateur. Le reste de cette division correspond au CRC à ajouter au message d'origine avant de l’émettre. Dans cette opération, on ne tient pas compte du quotient.

Exemple Détaillé d'Émission CRC

Division binaire de 111001110000 par 10110 :

  111001110000 (Dividende M(x)x^m)
  10110        (Diviseur G(x))
  -----
  010101110000 (Reste)
   10110       (G(x) décalé)
   -----
   00011110000 (Reste)
      10110    (G(x) décalé)
      -----
      00100000 (Reste)
       10110   (G(x) décalé)
       -----
       00010100 (Reste)
         10110  (G(x) décalé)
         -----
         0001110 (Reste final)

Le reste (CRC) est donc 1110 (les quatre derniers bits significatifs) et le mot à transmettre, incluant le CRC, est 111001111110.

Vérification d'un Mot Reçu avec CRC

Le récepteur effectue la même division du message complet (données + CRC) par le polynôme générateur. Si le reste est nul, aucune erreur n'a été détectée.

Exemple de réception : Vérification du mot 111001111110 avec 10110 :

  111001111110 (Mot reçu)
  10110        (Diviseur G(x))
  -----
  010101111110 (Reste)
   10110       (G(x) décalé)
   -----
   00011111110 (Reste)
      10110    (G(x) décalé)
      -----
      00100110 (Reste)
       10110   (G(x) décalé)
       -----
       0001001 (Reste)
         10110  (G(x) décalé)
         -----
         00000 (Reste final)

Le reste de la division est nul, il n’y a donc pas d’erreur détectée.

Exercices sur le CRC

On utilisera le polynôme générateur x⁴ + x² + x (séquence binaire : 10110).

On souhaite transmettre le message suivant : 1111011101. Quel sera le CRC à ajouter ?
Même question avec le mot 1100010101.
Je viens de recevoir les messages suivants : 1111000101010 et 11000101010110. Sont-ils corrects ?

Correction : Calcul du CRC pour le Message 1111011101

Division binaire de 11110111010000 par 10110 :

  11110111010000
  10110
  -----
  01000111010000
   10110
   -----
   00111111010000
     10110
     -----
     010011010000
      10110
      -----
      00101010000
        10110
        -----
        000110000
          10110
          -----
          0001100 (Reste final)

Le CRC est donc 1100 et le mot à transmettre est 11110111011100.

Correction : Calcul du CRC pour le Message 1100010101

Division binaire de 11000101010000 par 10110 :

  11000101010000
  10110
  -----
  01110101010000
   10110
   -----
   010111010000
    10110
    -----
    0010110000
      10110
      -----
      000010000 (Reste final)

Le CRC est donc 1000 et le mot à transmettre est 11000101011000.

Correction : Vérification du Message 1111000101010

Division binaire de 1111000101010 par 10110 :

  1111000101010
  10110
  -----
  0100000101010
   10110
   -----
   001100101010
     10110
     -----
     0111101010
      10110
      -----
      01000010
       10110
       -----
       001100
         10110
         -----
         00000 (Reste final)

Le reste est nul, il n’y a donc pas d’erreur détectée dans le mot transmis.

Correction : Vérification du Message 11000101010110

Division binaire de 11000101010110 par 10110 :

  11000101010110
  10110
  -----
  01110101010110
   10110
   -----
   010111010110
    10110
    -----
    0010110110
      10110
      -----
      00001110 (Reste final)

Le reste est 1110, il est non nul. Il y a donc une erreur détectée dans le mot transmis.

Foire Aux Questions (FAQ)

Qu'est-ce que la couche 2 OSI ?

La couche 2 du modèle OSI, aussi appelée couche de liaison de données, est responsable de la fiabilité du transfert de données entre deux nœuds directement connectés. C'est à ce niveau que les codes de détection et de correction d'erreurs sont généralement implémentés pour gérer les erreurs physiques de transmission, en organisant les données en trames et en assurant leur intégrité.

Quelle est la différence principale entre un code détecteur et un code correcteur d'erreurs ?

Un code détecteur d'erreurs (comme le CRC) peut identifier qu'une erreur s'est produite lors de la transmission, mais il ne peut pas la corriger. En cas d'erreur détectée, une retransmission des données est généralement nécessaire. Un code correcteur d'erreurs (comme le code de Hamming) peut non seulement détecter la présence d'une ou plusieurs erreurs, mais aussi identifier leur position et les corriger automatiquement, sans nécessiter de retransmission. Cela est particulièrement utile dans les systèmes où la retransmission est coûteuse ou impossible.

Comment fonctionne la division euclidienne en base 2 pour le CRC ?

La division euclidienne en base 2 pour le CRC est une opération similaire à la division longue décimale, mais elle utilise l'opération XOR (ou addition/soustraction sans retenue) au lieu de l'addition/soustraction standard. Le dividende est le message à vérifier (les données originales suivies du CRC) et le diviseur est le polynôme générateur. À chaque étape, si le bit le plus à gauche du dividende partiel est un 1, on effectue un XOR avec le diviseur (décalé pour l'aligner). Le processus se poursuit jusqu'à obtenir un reste dont la longueur est inférieure à celle du diviseur. Si ce reste est nul, le message est considéré comme sans erreur selon le CRC. Sinon, une erreur est détectée.