Codes détecteurs et correcteurs d’erreurs de transmission

 Schéma fonctionnel, pour être acheminée, toute information doit être mise sous la forme d’une suite structurée de symboles. La signification de ces symboles est une affaire de pure convention et est définie par une loi de correspondance. La protection contre les erreurs de transmission est réalisée grâce à un « surcodage » de chaque symbole de l’information à transmettre. A la réception, le contrôleur de communication peut, suivant les performances de ce « surcodage », détecter et corriger la majorité des erreurs dues aux imperfections du canal de transmission.  la correction des erreurs est possible si A’ ne peut être obtenu qu’à partir du bloc du code A. L’implication est alors bidirectionnelle et le récepteur peut décider que le bloc transmis est A, alors qu’il a reçu A’. Cette implication bidirectionnelle n’est possible que si le nombre d’erreurs est limité. En effet, avec beaucoup d’erreurs, le bloc peut se transformer en bloc A1′ à la réception, et le récepteur décidera que c’est A1 qui a été transmis, ce qui est faux. La correction est mise en défaut.   la détection des erreurs reste possible tant que le nombre d’erreurs ne transforme pas le bloc transmis en un autre bloc du code (on transmet A et on reçoit A1, le récepteur ne peut pas détecter l’erreur).

L’opérateur  signifie « Ou exclusif bit à bit » Le vecteur d’erreur E comporte autant de bits que les blocs A et R. Les positions des bits de E à « 1 » indiquent les positions des bits en erreur dans R. La fonction du décodeur à la réception est de calculer la valeur la plus probable de E en fonction de R pour en déduire le bloc corrigé : Rcorrigé = R  E. Cette opération inverse l’état des bits en erreur et réalise ainsi la correction du bloc reçu. Exemple : l’émetteur transmet A = (0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0) le récepteur reçoit R = (0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0) il calcule alors E = (0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0) s’il est capable de corriger 2

I.8.2 ) Poids de Hamming Le poids de Hamming d’un bloc du code est le nombre d’états « 1 » dans ce bloc. I.8.3 ) Distance de Hamming La distance de Hamming entre 2 blocs du code est le nombre de bits différents entre ces 2 blocs. La distance de Hamming minimum (notée dmin) est la plus petite distance de Hamming de toutes les paires de blocs du code possibles. I.8.4 ) Notion de voisinage La notion de voisinage définit les règles élémentaires de détection et de correction des erreurs de transmission.

Le bloc A appartient au sous-ensemble de codage Cun. Le voisinage de ce bloc est constitué des blocs de l’ensemble Cn ayant une distance de Hamming par rapport à A inférieure ou égale à d. Les voisinages représentés ci-dessus sont définis à la distance de Hamming minimum dmin. Lorsqu’ils se croisent, il existe des blocs communs aux 2 voisinages. La correction est impossible. En effet, si le récepteur reçoit le bloc C’, il est incapable de décider quel est le bloc transmis, A ou B, car C’ appartient aux 2 voisinages. Par contre, si les voisinages des blocs A et B sont distincts, comme représentés ci-dessous, la correction devient possible. Les voisinages représentés ci-dessus sont définis par la distance de Hamming tmin.

Exemple Les symboles à transmettre ont une longueur k = 1 bit. Les blocs du code de protection associés ont une longueur n de 4 bits et sont (0,0,0,0) pour le symbole « 0 » et (1,1,1,1) pour le symbole « 1 ». La distance de Hamming minimum vaut donc dmin = 4. On en déduit tmin = 1. Ce codage est donc capable de : I.10 ) Capacités de la détection et de la correction des erreurs Notation : le code de protection (n, k) produit des blocs de n bits à partir de symboles de k bits en ajoutant (n-k) bits de contrôle. I.10.1 ) Capacité de détection La fonction de détection est mise en défaut si, au cours de la transmission, un bloc du code se transforme en un autre bloc du code. La probabilité que cela se produit est : PD = pdmin  qn-dmin  pdmin En effet, dmin représente le nombre minimum de bits différents entre 2 blocs du code. Donc si dmin bits sont altérés au cours de la transmission, le bloc reçu peut faire partie du code. Exemple : code de Hamming (7,4). Il est caractérisé par dmin = 3 et tmin = 1.