Code correcteur d’erreurs

Les codes correcteurs d’erreurs sont essentiels dans le domaine des communications numériques, notamment pour assurer la fiabilité des transmissions malgré les perturbations. Cet article s’adresse aux étudiants en mathématiques appliquées, informatique ou télécommunications souhaitant comprendre les principes fondamentaux des codes correcteurs, leur fonctionnement et leur utilité dans la détection et la correction d’erreurs.

La question

Le travail s’intéresse à la problématique suivante : comment garantir que les messages transmis entre deux points restent intègres malgré les erreurs pouvant survenir lors de la transmission ? Ces erreurs peuvent être dues à des bruits, des fautes ou des perturbations diverses. L’objectif est donc de concevoir des codes capables de détecter et corriger ces erreurs sans avoir à renvoyer le message complet. Cette question est cruciale dans des domaines où la retransmission est coûteuse ou impossible, comme les communications spatiales.

Concepts de base

Pour comprendre les codes correcteurs, il faut d’abord maîtriser quelques notions clés :

• Alphabet et mots : une lettre est la plus petite unité d’information, ici prise dans l’alphabet binaire Ω = {0, 1}. Un mot est une suite de lettres, donc un vecteur dans l’espace F2^n.
• Poids d’un mot : le poids w(m) d’un mot m est le nombre de ses composantes non nulles (bits à 1).
• Distance de Hamming : la distance d(x, y) entre deux mots x et y est le nombre de positions où ils diffèrent. C’est une vraie distance métrique.
• Boule de Hamming : pour un mot x et un rayon r, la boule BH(x, r) est l’ensemble des mots à distance au plus r de x.
• Code binaire : un code C est un sous-ensemble de F2^n, souvent un sous-espace vectoriel de dimension k, noté (n, k).
• Distance minimale d’un code : la plus petite distance de Hamming entre deux mots distincts du code, notée dC.
• Capacité de correction : eC = (dC - 1) / 2, le nombre maximal d’erreurs que le code peut corriger.
• Taux d’information : rapport k/n, il mesure l’efficacité du code en termes de données utiles par rapport à la longueur totale du mot codé.
• Code linéaire : un code C est linéaire si la somme de deux mots du code appartient aussi au code. C’est un sous-espace vectoriel.
• Matrice génératrice G : matrice permettant de coder un message x par multiplication xG.
• Matrice de contrôle H : matrice telle que Ht m = 0 pour tout mot m du code, utilisée pour détecter les erreurs via le syndrome s = Ht w.
• Code systématique : code où les bits du message apparaissent directement dans le mot codé, facilitant l’encodage et le décodage.
• Code parfait : code dont les boules de Hamming de rayon eC centrées sur chaque mot du code forment une partition complète de l’espace F2^n, optimisant la correction d’erreurs.

Approche

Le travail présente une étude progressive des codes correcteurs, en commençant par les notions fondamentales, puis en explorant des codes spécifiques et efficaces :

• Codes binaires simples : comme le bit de parité ou la répétition, qui permettent de détecter ou corriger un nombre limité d’erreurs mais avec un taux d’information faible.
• Codes linéaires : qui structurent le code comme un sous-espace vectoriel, facilitant le calcul de la distance minimale et la correction d’erreurs via la matrice de contrôle.
• Codes de Hamming : codes parfaits capables de corriger une erreur avec un taux d’information élevé, construits selon une relation entre la longueur n, la dimension k et le nombre de bits de contrôle r.
• Codes cycliques : codes linéaires stables par décalage circulaire, représentés par des polynômes dans l’anneau F2[X] modulo (X^n - 1). Leur structure algébrique permet un codage et décodage efficaces.

Le décodage s’appuie sur le calcul du syndrome, qui identifie la position et la nature des erreurs. Pour les codes cycliques, un algorithme spécifique est présenté, reposant sur la division euclidienne des polynômes et la recherche d’erreurs sous forme de "burst" (erreurs consécutives).

Résultats

Les conclusions principales sont :

• La distance minimale d’un code linéaire correspond au poids minimal d’un mot non nul du code.
• La borne de Singleton établit que dC ≤ n - k + 1, limitant la distance minimale en fonction de la longueur et de la dimension.
• Les codes de Hamming sont des codes parfaits avec dC = 3, capables de corriger une erreur et optimaux dans ce cadre.
• Les codes cycliques sont caractérisés par un polynôme générateur unique g(X) divisant X^n - 1, et leur dimension est n - deg(g(X)).
• Le décodage des codes cycliques peut être réalisé par calcul du syndrome, suivi d’une recherche itérative pour localiser les erreurs.
• Les codes cycliques détectent toutes les erreurs "burst" de longueur inférieure ou égale au degré du polynôme générateur, ce qui les rend particulièrement adaptés à certains types d’erreurs consécutives.

Limitations et questions ouvertes

Le travail souligne certaines limites :

• Les codes simples comme la répétition ont un taux d’information très faible, ce qui limite leur usage pratique.
• L’algorithme de décodage des codes cycliques présenté fonctionne bien lorsque les erreurs sont suffisamment espacées (avec au moins k zéros consécutifs), mais peut échouer dans certains cas où les erreurs sont trop concentrées.
• La correction d’erreurs multiples complexes ou de "burst" plus longs nécessite des codes plus sophistiqués ou des algorithmes plus avancés non détaillés ici.

Glossaire

• Alphabet : ensemble des symboles utilisés pour former les mots (ici {0,1}).
• Poids d’un mot : nombre de bits à 1 dans un mot binaire.
• Distance de Hamming : nombre de positions où deux mots diffèrent.
• Boule de Hamming : ensemble des mots à une distance donnée d’un mot central.
• Code binaire : ensemble de mots binaires utilisés pour coder l’information.
• Code linéaire : code formant un sous-espace vectoriel de F2^n.
• Matrice génératrice (G) : matrice utilisée pour encoder les messages.
• Matrice de contrôle (H) : matrice utilisée pour détecter les erreurs via le syndrome.
• Syndrome : vecteur calculé pour détecter et localiser les erreurs.
• Code parfait : code dont les boules de Hamming couvrent exactement l’espace sans chevauchement.
• Code de Hamming : code parfait capable de corriger une erreur, avec des paramètres spécifiques.
• Code cyclique : code linéaire stable par décalage circulaire, représenté par un polynôme générateur.
• Polynôme générateur : polynôme minimal qui génère un code cyclique.
• Erreur "burst" : erreur affectant plusieurs bits consécutifs.