Codes correcteurs

Sujet proposé par Dominique Perrin

perrin@univ-mlv.fr

Préambule

Les codes correcteurs d'erreurs sont utilisés dans les transmissions de données pour éliminer les effets du bruit. On propose de construire plusieurs schémas simples de codes correcteurs allant du très simple bit de parité au code de Hamming.

Détail du sujet

Un canal de communication peut être schématisé comme sur la Figure 1.

   figure12
Figure 1: Un canal de communication

La transmission est perturbée par un bruit et un système de codage est utilisé pour détecter, ou même corriger les erreurs provoquées par le bruit. C'est ce qu'on appelle un code correcteur d'erreurs. Ce mécanisme est utilisé sur tous les moyens de transmission de données informatiques (cables coaxiaux, fibres optiques, ondes hertziennes, etc.). Le but de ce projet est de construire un schéma simple de code correcteur et de l'utiliser sur une ligne simulée.

Bit de parité

Le mécanisme le plus simple est l'utilisation d'un bit de parité.

   figure22
Figure 2: Le bit de parité

Il consite à ajouter à la fin de chaque bloc de n-1 bits un bit supplémentaire choisi de telle sorte que le nombre total de bits égaux à 1 dans le bloc de n bits soit pair. Si, à la réception, le nombre de bits dans un bloc est impair, on détecte une erreur (et on peut, par exemple envoyer un message demandant la retransmission du bloc).

Code de Hamming

Un procédé plus compliqué permet de corriger une erreur dans un bloc (mais pas deux et le procédé est donc valable pour des taux d'erreurs faibles). Le code utilisé, appelé code de Hamming, est obtenu de la façon suivante. On fixe un entier k et on code chaque bloc de tex2html_wrap_inline196 bits par un bloc de tex2html_wrap_inline198 bits obtenu en ajoutant à certaines positions dans un bloc de m bits (dits bits d'information) un ensemble de k bits de correction (voir Figure 3).

   figure34
Figure 3: Un bloc avec k=n-m bits de correction

Pour calculer les bits de correction, on utilise une matrice de parité H qui est représentée ci-dessous pour k=3.

displaymath184

La colonne d'indice i de H est la représentation en binaire de i. Les n-m bits de correction sont choisis de telle façon que si le bloc a est écrit comme un vecteur colonne, on ait

displaymath185

où les opérations sont faites en binaire avec la règle 1+1=0 (c'est le corps noté Z/2 des entiers modulo 2). Les bits de correction sont ceux situés aux indices puissance de 2. On aura par exemple la session de transmission suivante :

displaymath186

Le message a=[1110] est codé par le bloc tex2html_wrap_inline226 obtenu en ajoutant trois bits de correction tex2html_wrap_inline228 (en gras) définis par les équations

displaymath187

Le deuxième bit a été modifié par une erreur et on reçoit le bloc c=b+e avec e=[0100000]. Elle est corrigée au décodage de la façon suivante. On calcule le vecteur s=Hc. On obtient ainsi le vecteur He qui est la deuxième colonne de H et on change donc le deuxième bit de c de 1 en 0.

Le code de Hamming permet de corriger une erreur car toutes les colonnes de la matrice H sont différentes et que deux blocs codés diffèrent au moins sur trois bits. Il ne permet pas de corriger ni même de détecter deux erreurs. En effet, si deux erreurs se produisent aux indices i et j, le résulat est le même que si une erreur s'était produite (dans un autre bloc) à l'indice k tel que la colonne k de la matrice H soit la somme binaire de colonnes i et j.

On peut, à la fin des blocs du code de Hamming, ajouter un bit de parité. On obtient ainsi des blocs de longueur tex2html_wrap_inline262 avec k+1 bits de correction. Pour k=3, la matrice de parité devient alors

displaymath188

Un tel code, appelé code de Hamming étendu, permet toujours de corriger une erreur mais devient capable d'en détecter deux (puisque deux blocs codés diffèrent au moins de 4 bits).

Code de Hamming cyclique

Une variante de la méthode ci-dessus consiste à considérer un vecteur binaire tex2html_wrap_inline278 comme un polynome tex2html_wrap_inline280 à coefficients dans Z/2. On utilise un polynome p(x) de degré k qui est primitif, c'est à dire tel que les puissances tex2html_wrap_inline288 prises modulo p parcourent l'ensemble de tous les tex2html_wrap_inline198 polynomes non nuls de degré au plus k et à coefficients dans Z/2 une fois et une seule. Par exemple, si on prend tex2html_wrap_inline298 , on obtient, en écrivant les vecteurs tex2html_wrap_inline300 en colonnes dans la base tex2html_wrap_inline302 , la matrice

displaymath274

Le polynome p est donc primitif. C'est la matrice H ci-dessus que l'on prend comme matrice de parité.

On écrit la donnée sous la forme d'un bloc tex2html_wrap_inline308 avec k=n-m bits en tête destinés à la correction. Le calcul des bits de correction consiste donc cette fois tout simplement à calculer le polynome b(x)=a(x)+r(x) où r(x) est le reste de la division de a(x) par p(x). On aura bien ainsi Hb=0 puisque Hb(x) est par construction le reste de b(x) modulo p(x). Cette observation est utile pour le calcul de r(x) que l'on obtient très simplement en calculant Ha. Le décodage consiste à calculer comme précédemment le vecteur s=Hc. Si s=0, on garde c. Sinon, on modifie la composante i de c telle que tex2html_wrap_inline342 . On aura par exemple en partant du message [1110] la transmission

displaymath275

finalement décodée correctement [1110] malgré l'erreur survenue au bit 5.

Correction de 2 erreurs

La méthode ci-dessus se généralise au traitement de plusieurs erreurs. Pour corriger 2 erreurs, on procède ainsi. On choisit comme précédemment un polynome p(x) primitif de degré k. Le quotient de l'anneau des polynomes à coefficients dans Z/2 modulo p(x) est un corps K ayant tex2html_wrap_inline362 éléments. On prend comme matrice de parité la matrice

displaymath348

dont les colonnes sont obtenues en plaçant au dessous des puissances de x les puissances correspondantes de tex2html_wrap_inline366 (le tout modulo p(x) comme précédemment). Par exemple, pour k=4, en utilisant le polynome tex2html_wrap_inline372 , la matrice s'écrit

displaymath349

Le codage d'un bloc tex2html_wrap_inline374 avec m=n-2k, se fait comme précédemment sous la forme du polynome b(x)=a(x)+r(x) avec r=Ha. On peut corriger jusqu'à deux erreurs de la façon suivante. Supposons que le vecteur reçu est b=a+e+fHa=0 et où e,f sont des vecteurs ayant un seul bit 1 en position i et j. Le vecteur Hb est alors de la forme tex2html_wrap_inline394 et le problème se ramène donc à calculer deux éléments tex2html_wrap_inline396 du corps K des polynomes modulo p(x) connaissant leur somme et la somme de leurs cubes.

Travail demandé

On demande de réaliser une simulation d'une ligne de communication avec protection contre le bruit. Le message pourra être entré au clavier sous forme d'une suite de caractères. Il sera ensuite converti en une suite de bits (qui peuvent être obtenus en calculant pour chaque caractère c la représentation binaire sur 7 bits de l'entier ord(c) associé en Pascal au caractère c). L'utilisateur pourra ensuite choisir l'une des méthodes de codage :

  1. Bit de parité. On pourra grouper la suite de bits par blocs de longueur 7 et ajouter un bit de parité.
  2. Code de Hamming binaire. On réalisera cette méthode pour un entier k à choisir. On pourra aussi réaliser le code de Hamming étendu.
  3. Code de Hamming cyclique. On réalisera le codage pour k=8 avec le polynome tex2html_wrap_inline406 .
  4. Correction de 2 erreurs (facultatif). On implémentera la méthode de correction de 2 erreurs pour k=4.
On introduira dans la suite binaire codée un bruit aléatoire que l'on pourra, soit détecter, soit tenter de corriger suivant la méthode de codage utilisée. On affichera la suite de caractères affectée du bruit avant correction et après.

Références

1
J. H. van Lint, Introduction to Coding Theory, Springer, 1982


Mon Dec 9 16:25:00 MET 1996