RESEAU INFORMATIQUE : Les codes correcteurs et les codes détecteurs

Les codes correcteurs et les codes détecteurs d'erreurs sont des méthodes essentielles utilisées dans les communications pour garantir l'intégrité des données transmises. Pourquoi sont-ils nécessaires ? Parce que les canaux de transmission sont rarement parfaits, ce qui signifie que des erreurs peuvent se produire lors de l'échange de données. Par exemple, sur une ligne téléphonique, la probabilité d'erreur est souvent de l'ordre de 10^-4, voire 10^-7. Pour pallier ces erreurs potentielles, nous utilisons des méthodes de détection des erreurs, voire de correction des erreurs.

Ces méthodes sont mises en place au niveau de la couche 2 du modèle OSI, également connue sous le nom de "liaison de données". Le principe général est le suivant : chaque suite de bits (appelée trame) à transmettre est complétée par une autre suite de bits, appelée suite de redondance ou de contrôle. Pour chaque suite de k bits transmis, on ajoute r bits supplémentaires. On parle alors d'un code C(n, k), où n est égal à k plus r.

À la réception, on effectue l'opération inverse, et les bits ajoutés permettent de réaliser des contrôles pour vérifier l'intégrité des données. Il existe deux catégories de codes principaux : les codes détecteurs d'erreurs et les codes correcteurs d'erreurs.

Un exemple célèbre de code correcteur et détecteur d'erreurs est le code de Hamming. Ce code est capable non seulement de détecter les erreurs, mais aussi de les corriger si elles se produisent. Cela le rend particulièrement précieux dans les applications où la fiabilité des données est cruciale.

D'un autre côté, le CRC (Cycle Redundancy Check) est un exemple de code détecteur d'erreurs. Il est utilisé pour vérifier si des erreurs se sont produites lors de la transmission des données, mais il ne peut pas les corriger. Son utilisation est courante dans de nombreuses applications de communication, telles que les protocoles de réseau.

En résumé, les codes correcteurs et détecteurs d'erreurs sont des outils cruciaux pour garantir la fiabilité des communications, en particulier lorsque les canaux de transmission sont sujets à des erreurs. Les codes de Hamming sont un exemple puissant de code capable à la fois de détecter et de corriger des erreurs, tandis que le CRC est un exemple de code utilisé principalement pour la détection des erreurs. Ces techniques sont fondamentales pour assurer l'intégrité des données dans les réseaux de communication modernes.

Cest une technique de codage qui permet à la fois la détection et la correction d'erreurs dans les données transmises. Il fonctionne en ajoutant des bits de parité aux données d'origine, ce qui permet de repérer les erreurs et de les corriger si nécessaire. Dans ce cours, nous allons explorer la structure d'un mot de code de Hamming, comment détecter les erreurs, et comment corriger ces erreurs en utilisant un exemple concret.

Structure d'un mot de code de Hamming :

Un mot de code de Hamming est composé de deux parties : les m bits du message d'origine à transmettre et les n bits de contrôle de parité. La longueur totale du mot de code est donnée par 2^n - 1, tandis que la longueur du message est m = (2^n - 1) - n. On parle donc de code x - y où x = n + m et y = m.

Exemple de code de Hamming :

Prenons quelques exemples pour illustrer cela :

Un mot de code 7 - 4 a un coefficient d'efficacité de 4/7, soit 57%.

Un mot de code 15 - 11 a un coefficient d'efficacité de 11/15, soit 73%.

Un mot de code 31 - 26 a un coefficient d'efficacité de 26/31, soit 83%.

Les bits de contrôle de parité, notés Ci, sont placés en position 2^i pour i = 0, 1, 2, ... Les bits du message, notés Dj, occupent le reste du message.

Détecter et corriger les erreurs :

Pour détecter et corriger les erreurs dans un mot de code de Hamming, nous devons vérifier les bits de contrôle de parité C'2, C'1, et C'0 à la réception.

Si C'0 vaut 1, les valeurs possibles de C'2C'1C'0 sont 001, 011, 101, 111, ce qui correspond aux positions 1, 3, 5, 7.

Si C'1 vaut 1, les valeurs possibles de C'2C'1C'0 sont 010, 011, 110, 111, ce qui correspond aux positions 2, 3, 6, 7.

Si C'2 vaut 1, les valeurs possibles de C'2C'1C'0 sont 100, 101, 110, 111, ce qui correspond aux positions 4, 5, 6, 7.

Exercice : Déterminons s'il y a une erreur dans le mot suivant : 1 0 1 0 1 1 0

Correction de l'exercice :

C'2 vaut 1 + 0 + 1 + 0 = 0 (bits d'indice 7, 6, 5 et 4).

C'1 vaut 1 + 0 + 1 + 1 = 1 (bits d'indice 7, 6, 3 et 2).

C'0 vaut 1 + 1 + 1 + 0 = 1 (bits d'indice 7, 5, 3 et 1).

C'2C'1C'0 vaut 011, soit 3 en base 10. Il y a donc une erreur à l'indice 3 du mot. Le mot correct est donc 1 0 0 0 1 1 0.

Le code de Hamming est un moyen efficace de détecter et de corriger les erreurs de transmission dans les données. Il est basé sur l'ajout de bits de parité aux données d'origine et permet de localiser et de résoudre les erreurs, ce qui en fait une technique précieuse dans les communications modernes.

Nous continuons notre exploration du code de Hamming en examinant un exemple pratique où nous souhaitons émettre un message et générer le mot de Hamming correspondant, puis vérifier si le message reçu correspond au message transmis.

Émission pour un contrôle de parité pair :

Lorsque nous émettons un message avec un contrôle de parité pair, nous devons calculer les bits de parité C2, C1 et C0 en fonction des bits de message. Voici comment cela fonctionne :

C2 est calculé par rapport aux bits d'indice 7, 6, 5, et sa valeur est 4.

C1 est calculé par rapport aux bits d'indice 7, 6, 3, 2, et sa valeur est 1.

C0 est calculé par rapport aux bits d'indice 7, 5, 3, 1, et sa valeur est 0.

Maintenant, supposons que nous souhaitons envoyer le message 1010. Complétons le mot de Hamming correspondant :

Message d'origine : 1 0 1 0 Mot de Hamming : 1 0 1 _ 0 _ _

C2 vaut 0 pour rendre pair 1 + 0 + 1 (les bits d'indices 7, 6, 5).

C1 vaut 1 pour rendre pair 1 + 0 + 0 (les bits d'indices 7, 6, 3).

C0 vaut 0 pour rendre pair 1 + 1 + 0 (les bits d'indice 7, 5, 3).

Le mot de Hamming complet est donc : 1 0 1 0 0 1 0.

Vérification de l'erreur dans un message reçu :

Supposons maintenant que le message reçu soit le suivant : 1 0 1 0 0 1 1.

Pour détecter et corriger d'éventuelles erreurs, nous vérifions les bits de contrôle de réception C'3, C'2, C'1, et C'0.

C'3 vaut 1 + 0 + 1 + 1 + 1 + 0 + 1 + 1 = 0.

C'2 vaut 1 + 0 + 0 + 1 + 1 + 0 + 0 + 1 = 0.

C'1 vaut 1 + 1 + 0 + 1 + 1 + 1 + 0 + 1 = 0.

C'0 vaut 1 + 1 + 1 + 0 + 1 + 1 + 0 + 1 = 0.

Ainsi, C'3C'2C'1C'0 vaut 0000. Il n'y a donc pas d'erreur dans le message reçu. Le message reçu correspond au message transmis.

Le code de Hamming est un puissant outil pour détecter et corriger les erreurs de transmission dans les données. Il est basé sur l'ajout de bits de parité aux données d'origine, ce qui permet une détection précise des erreurs et, dans certains cas, leur correction. Cette technique est largement utilisée dans les communications pour assurer la fiabilité des données transmises.

Le CRC (Cyclic Redundancy Check) : Détection d'Erreurs en Détail

Le CRC est un mécanisme puissant de détection d'erreurs largement utilisé dans les communications pour garantir l'intégrité des données transmises sur un canal sujet à des perturbations. Ce mécanisme repose sur des calculs polynomiaux et des polynômes générateurs spécifiques. Dans ce cours, nous allons explorer en détail le fonctionnement du CRC en utilisant la méthode de division binaire.

Représentation Polynomiale :

Tout d'abord, pour comprendre le CRC, nous représentons un message binaire M comme un polynôme I(x), où chaque bit mi du message est associé à un coefficient du polynôme. Par exemple, le message 11000101 est représenté par le polynôme :

I(x) = x^6 + x^5 + 0x^4 + 0x^3 + x^2 + 0x + 1 = x^6 + x^5 + x^2 + 1

Polynômes Générateurs :

Le CRC utilise des polynômes générateurs spécifiques qui possèdent des propriétés mathématiques particulières. Par exemple, le polynôme générateur x^4 + x^2 + x est représenté en binaire comme 10110.

En Émission :

Lorsque nous souhaitons émettre un message avec CRC, nous ajoutons au message le CRC calculé de manière à ce que le polynôme correspondant au message plus le code de contrôle soit divisible par le polynôme générateur.

En Réception :

À la réception, le message reçu, contenant les données et le CRC, doit être divisible par le polynôme générateur. Cela signifie que lors de la division binaire, le reste de la division doit être nul pour que le message soit considéré comme correct.

Émission d'un Mot :

Choisir un polynôme générateur.

Transformer le polynôme générateur en un mot binaire. Par exemple, pour le polynôme générateur x^4 + x^2 + x, nous obtenons 10110.

Ajouter m zéros au mot binaire à transmettre, où m est le degré du polynôme générateur. Par exemple, si le polynôme générateur est de degré 4, nous ajoutons 4 zéros. Le message complet est maintenant prêt à être émis.

Division Binaire pour la Détection :

Pour vérifier si le message reçu est correct, nous utilisons la division binaire. Voici comment cela fonctionne :

Exemple de Division : On utilisera le polynôme générateur x4 + x2 + x.
1. On souhaite transmettre le message suivant :1111011101, quel sera le
CRC à ajouter ?
2. Même question avec le mot 1100010101.
3. Je viens de recevoir les messages suivants : 1111000101010,
11000101010110, sont-ils corrects ?

Corrections :

Correction : quel CRC à ajouter avant d’émettre le message 1111011101 ?

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

Correction : quel CRC à ajouter avant d’émettre le message 1100010101 ?

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

Correction : le message reçu 1111000101010 est-il correct ?

Le reste est nul ⇒ il n’y a pas d’erreur dans le mot transmis.

Correction : le message reçu 11000101010110 est-il correct ?

Le reste est 1110 ⇒ il y a une erreur dans le mot transmis.

Conclusion :

Le CRC est une méthode puissante de détection d'erreurs basée sur des calculs polynomiaux et l'utilisation de polynômes générateurs spécifiques. Il garantit l'intégrité des données dans les communications en vérifiant que le reste de la division entre le message reçu et le polynôme générateur est nul. Cette technique est essentielle pour assurer la fiabilité des données transmises sur des canaux de communication sujets à des perturbations.

Le contrôle polynomial, souvent appelé CRC (Cyclic Redundancy Check), est une méthode couramment utilisée dans les protocoles de communication pour détecter les erreurs sur plusieurs bits lors de la transmission de données. Voici comment fonctionne le processus de contrôle polynomial :

Représentation des données sous forme de polynômes : Les données à transmettre sont considérées comme un groupe de bits, et chaque bit correspond à un coefficient dans un polynôme P(x), où le coefficient de degré i correspond à la valeur du i-ème bit.

Calculs modulo 2 sur les polynômes : Les calculs sont effectués modulo 2 sur les polynômes. Cela signifie que les opérations de somme et de multiplication sont effectuées en utilisant une logique XOR. Par exemple, (x^7 + x^3) + (x^3 + x) est équivalent à x^7 + x.

Choix d'un polynôme générateur : Un polynôme G(x) de degré r est choisi comme polynôme générateur. Ce polynôme est caractéristique du contrôle CRC.

Calcul du reste R(x) : À l'émission, on multiplie le polynôme P(x) par x^r, puis on divise le polynôme obtenu par G(x) en effectuant une division euclidienne. Le reste de cette division, noté R(x), est de degré strictement inférieur à r. R(x) est ajouté à la fin de la trame de données comme code de contrôle. La relation est la suivante : xr*P(x) = G(x)*Q(x) + R(x).

Formation du polynôme de transmission T(x) : Le polynôme de transmission T(x) est formé en combinant le polynôme initial P(x) et le reste R(x) calculé précédemment. T(x) est donné par l'équation : T(x) = xr*P(x) + R(x).

Transmission du message : Le polynôme T(x) est transmis en tant que trame de données, comprenant à la fois les données d'origine et les bits de contrôle CRC.

Réception et vérification : À la réception, la trame de données est divisée par le même polynôme générateur G(x). Si le reste de cette division, noté R1(x), est nul, on considère que les données reçues correspondent à celles émises. Sinon, si R1(x) n'est pas nul, cela signifie que des erreurs ont été introduites, et l'information reçue doit être ignorée.

Dans votre exemple, le polynôme associé aux données d'origine est P(x) = x^15 + x^9 + x^8 + x^7 + x^2, et le polynôme générateur est G(x) = x^12 + x^11 + x^3 + x^2 + x + 1. La division de x^12*P(x) par G(x) donne un reste R(x) = x^11 + x^9 + x^8 + x^7 + x^6 + x^4 + 1.

La trame de données transmise est ainsi constituée du polynôme x^12*P(x) suivi du reste R(x).

Les codes correcteurs et les codes détecteurs, tels que le code de Hamming et le CRC (Cyclic Redundancy Check), jouent un rôle essentiel dans la garantie de l'intégrité des données lors des transmissions sur des canaux de communication sujets à des erreurs. Voici quelques points clés à retenir :

Les canaux de transmission peuvent être sujets à des erreurs, que ce soit en raison du bruit, des interférences, ou d'autres facteurs. La probabilité d'erreur peut varier en fonction du canal, mais même des probabilités d'erreur très faibles nécessitent des mécanismes de détection et de correction.

Les codes correcteurs et détecteurs sont mis en place au niveau de la couche 2 du modèle OSI, également connue sous le nom de "liaison de données". Ces codes permettent d'ajouter des bits de redondance ou de contrôle aux données à transmettre.

Le code de Hamming est un exemple de code à la fois détecteur et correcteur d'erreurs. Il permet de détecter et de corriger des erreurs simples dans les données transmises en ajoutant des bits de parité.

Le CRC (Cyclic Redundancy Check) est un code principalement utilisé pour la détection d'erreurs. Il repose sur la représentation polynomiale des données et l'utilisation de polynômes générateurs spécifiques.

En émission, un message est préparé en ajoutant les bits de redondance ou de contrôle calculés en fonction du code utilisé. Ces bits permettent de détecter ou de corriger des erreurs lors de la réception.

En réception, le message reçu est vérifié en effectuant des calculs basés sur le code utilisé. Si le message est correct, il est accepté. Sinon, des mesures correctives peuvent être prises, comme une demande de renvoi des données.

Les codes correcteurs et détecteurs sont essentiels dans de nombreuses applications, notamment les communications sans fil, les réseaux informatiques, les systèmes de stockage de données, et bien d'autres. Ils contribuent à garantir la fiabilité des données et à minimiser les erreurs de transmission.

En somme, ces techniques jouent un rôle crucial dans la transmission fiable des données à travers des canaux imparfaits, assurant ainsi la qualité et l'intégrité des informations échangées dans notre monde interconnecté.