Détection et correction d'erreurs.

 Le taux d'erreurs de transmission est de l'ordre de 10^-5 sur une ligne téléphonique, de 10^-7 à 10^-8 sur un coaxial et de 10^-10 à 10^-12 sur une fibre optique. À ce niveau-là il ne s'agit pas d'assurer la correction globale d'un échange, mais de détecter et d'éventuellement corriger des erreurs de transmissions dans un bloc de bits acheminé par le support physique. En effet, puisque la couche 2 ne connaît pas le propriétaire des paquets qu'elle manipule, elle ne peut pas se substituer aux couches de niveau supérieur.

Les techniques employées ici reposent sur l'utilisation de codes correcteurs ou codes détecteurs d'erreurs qui chacun transforme la suite de bits à envoyer en lui ajoutant de l'information à base de bits de redondance ou bits de contrôle . Le récepteur se sert de cette information ajoutée pour déterminer si une erreur s'est produite et pour la corriger si la technique employée le permet.

• la parité ajoute à chaque bloc de i bits (i=7 ou 8) émis un bit de parité de telle sorte que parmi les i+1 bits émis le nombre de bits à 1 soit toujours pair (ou impair). Par exemple, pour une parité paire si le bloc initial est de 7 bits et est égal à 1000001 le bloc de 8 bits émis est 10000010, pour envoyer 0110100 le bloc 01101001 est émis. À la réception, le décodeur calcule le nombre de bits à 1 et dans le cas d'une parité paire si ce nombre de bits est pair on suppose qu'il n'y a pas eu d'erreur. Sinon, on sait alors qu'il y a eu une erreur de transmission mais on ne sait pas la localiser et il faut alors demander la réémission du bloc. La technique de parité est simple à mettre en uvre cependant elle ne permet pas de détecter 2n erreurs dans le même bloc de bits transmis, car dans ce cas la parité ne sera pas changée.
• les codes à redondance cyclique (CRC) ajoutent des bits qui sont des combinaisons linéaires des bits de l'information à transmettre. La suite de bits à transmettre $u_1,u_2,\ldots,u_k$ est considérée comme un polynôme $M(x)= u_1 x^{k-1} + u_2 x^{k-2}+\ldots+u_k$.Par exemple 1101011011 est représenté par x⁹+x⁸+x⁶+x⁴+x³+x+1 . À l'émission, on calcule la division du polynôme M multiplié par x^r par le polynôme générateur G de degré r. On appelle Q le polynôme quotient et R le polynôme reste de cette division, on a donc : x^rM(x)=Q(x).G(x)+R(x) .

  La suite de bits correspondant au polynôme R constitue le CRC qui est ajouté à l'information à transmettre, le polynôme total émis est donc E(x)=x^rM(x)+R(x) Par exemple, à l'aide du polynôme générateur G(x)=x⁴+x+1, la suite 1101011011 sera transmise accompagnée du CRC 1110 car

  À la réception, on divise le polynôme M' correspondant à la suite totale de bits reçus (information+CRC) par le polynôme générateur. Si le reste calculé est non nul, c'est qu'une erreur s'est produite dans la transmission. Si le reste est nul, on est à peu près sûr (99,975% avec le polynôme générateur x¹⁶+x¹²+x⁵+1 de la norme V41 du ITU-T) que la transmission s'est faite sans erreur.

  Pourquoi cela fonctionne-t-il ? Il est évident que x^rM(x)-R(x) est divisible par G(x), mais en arithmétique modulo 2 addition et soustraction sont équivalentes (ce sont des OU exclusifs en fait) donc on a également E(x)=x^rM(x)+R(x)=G(x)Q(x) montrant que E est un polynôme multiple de G. Si lors de la transmission des erreurs se sont produites, cela se traduit par le fait que le polynôme reçu M'(x)=E(x)+T(x), T étant le polynôme correspondant aux erreurs (T(x)=xⁱ si le ibit a été inversé). À la réception le décodeur calcule le reste de qui est en fait le reste de puisque E est un multiple de G. Si ce résultat est non nul, c'est que T est non nul et que des erreurs se sont produites. Évidemment, le résultat est également nul si T est un multiple de G ce qui masque des erreurs, mais le choix judicieux de G permet de minimiser ces erreurs non détectées. Enfin, il faut aussi remarquer un inconvénient de cette méthode qui signale des erreurs de transmission même si celles-ci ont eu lieu dans le CRC et non dans l'information à transmettre initialement. Dans ce cas il ne devrait pas être nécessaire de retransmettre l'information, or c'est ce qui est fait puisque globalement le transfert (info+CRC) a subi des perturbations.

• le code de Hamming est un code correcteur d'erreurs basé sur la notion de distance de Hamming . Soit un alphabet composé de 4 caractères (00,01,10,11). Si une erreur se produit alors le caractère émis est transformé en un autre caractère et il n'y a pas moyen de retrouver le caractère original. Par contre, en ajoutant de l'information de telle sorte que les caractères soient très différents les uns des autres cela devient possible.
  

   

  caractère initial 00 01 10 11

  caractère émis 00000 01111 10110 11001

  00001 01110 10111 11000

  caractères 00010 01101 10100 11011

  erronés 00100 01011 10010 11101

  possibles 01000 00111 11110 10001

  10000 11111 00110 01001

   

  
  Par exemple, on peut coder les 4 caractères de la manière illustrée dans la table 1.1. Ainsi si un bit (parmi les 5 émis) est erroné on sait quand même déterminer quel caractère a été émis, car comme on peut le voir dans la table 1.1 la modification d'un bit ne peut pas faire passer d'un caractère initial à l'autre. On a des ensembles <<d'erreurs possibles>> totalement disjoints. Par contre la modification de 2 bits dans cet exemple peut amener à des confusions et à l'impossibilité de corriger les erreurs.

  Soit x et y deux caractères d'un alphabet $\mathcal{A}$ et soit N la longueur du codage des mots de cet alphabet, x_i et y_i désignent respectivement le ibit de x et y. On peut alors définir la distance qui permet de compter le nombre de bits qui diffèrent entre x et y. On définit alors la distance de Hamming par . Dans l'exemple choisi ci-dessus, d_H=1 dans le premier codage sur 2 bits et d_H=3 dans le codage sur 5 bits. Chaque erreur sur un bit d'un caractère x donne un caractère x' tel que d(x,x')=1, donc pour pouvoir détecter et corriger une seule erreur il faut que $d_h\geq3$ et pour corriger 2 erreurs il faut que $d_h\geq5$.D'une manière générale on détecte et corrige n erreurs quand la distance de Hamming est 2n+1.
  

    

  Figure 1.14: Distance de Hamming.

  
  
  

  On peut voir ceci dans la figure 1.14 où sont représentés x et y (2 caractères parmi les plus proches de l'alphabet), x_i et y_i des <<déformations>> de x et y après une erreur et x₁' et y₁' des <<déformations>> après deux erreurs. Ainsi, quand on reçoit un caractère x (erroné ou non on ne peut pas le savoir à l'avance) il suffit de chercher le caractère $c\in \mathcal{A}$ le plus proche de x selon la distance d pour obtenir le caractère émis.

  Un exemple de code de Hamming est donné par la technique suivante où l'on veut envoyer des caractères codés sur 4 bits de données ABCD. Pour cela on va émettre la suite ABCP₂DP₁P₀ dans laquelle les bits de contrôle P_i sont placés sur les bits de rang 2ⁱ et sont définis par

  $$\left\lbrace \begin{array} {lll} P_0 & = & A \oplus C \opl... ...\oplus D \\ P_2 & = & A \oplus B \oplus C \end{array}\right.$$

  Les P_i sont des bits de parité définis à l'aide des bits de données de rang k tels que la décomposition de k en somme de puissances de 2 contienne 2ⁱ. Par exemple, A est un bit de donnée de rang 7=2⁰+2¹+2² donc A sert au calcul de P₀, P₁ et P₂. De même, le rang de D est 3=2⁰+2¹ donc il sert au calcul de P₀ et P₁.

  À la réception on calcule

  $$\left\lbrace \begin{array} {lll} P'_0 & = & P_0 \oplus A \... ... P'_2 & = & P_2 \oplus A \oplus B \oplus C \end{array}\right.$$

  si on obtient P'₂ = P'₁ = P'₀ = 0 alors c'est que la transmission s'est passée sans problème. Sinon, la valeur binaire de P'₂P'₁P'₀ donne la place de l'erreur dans les bits reçus (en commençant par la droite). On corrige alors l'erreur et on recalcule les P'_i, s'ils sont devenus tous nuls l'erreur a été corrigée, sinon il y avait eu au moins deux erreurs et on peut rejeter la suite de bits mais pas la corriger.

  Par exemple, si l'on veut envoyer les 4 bits 0010, on va finalement émettre 0011001. Si l'on reçoit 0010001, on trouve P'₂P'₁P'₀=100 c'est-à-dire 4, donc l'erreur était en 4place. On corrige, pour obtenir 0011001 et un nouveau calcul donne P'₂ = P'₁ = P'₀ = 0 assurant que l'on a corrigé l'erreur. On peut remarquer qu'en fait on a corrigé une erreur qui n'était pas sur les données initiales mais sur les bits de parité rajoutés.