Concepts mathématiques sur les codes correcteurs d’erreurs

Les codes correcteurs

Les codes correcteurs ont été introduits pour corriger les erreurs de transmission ou de lecture de données numériques, ou les erreurs survenant au cours de leur inscription sur un Support physique (bande, CD) ou encore lorsque les données subissent une altération sur le Support de stockage. Voici quelques domaines où ils sont appliques : • Transmissions spatiales • Minitel 19 • Codes-barres • Disque compact et DVD • Communications par internet. Le schéma suivant illustre la chaîne d’actions qui permet à une source de transmettre de l’information à un destinataire[46] Figure 3.2 – Exemple Source: [47] 

Codes et distance de Hamming

Les messages transmis sont supposés découpes en blocs (ou mots) de longueur n écrits avec l’alphabet {0,1}. Un code (binaire) est un sous-ensemble C de l’ensemble {0, 1} n de tous les mots possibles. On dit que n est la longueur de C. La distance de Hamming entre deux mots x = (x1,. . . ., xn) et y = (y1,. . . ., yn), que l’on notera d(x,y), est le nombre d’indices i tels que xi = yi. C’est bien une distance sur {0, 1} n . La distance minimal du code C’est le minimum des d(x,y) pour x et y des mots différents de C (on suppose que C a au moins 2 mots !). On la notera toujours d. Exemple . Considère C = c0, c1, c2, c3 avec c0 = (00000) ; c1 = (10110) ; c2 = (01011) ; c3 = (11101) : C’est un code de longueur 5 et de distance d = 3. Le mot c ∈ C est émis et, après d’éventuelles erreurs de transmission, le mot r ∈ {0, 1} n est reçu.On décode le mot r selon le principe du maximum de vraisemblance, c.-à-d. qu’on le décode comme un mot de C à distance minimum de r. On dit que C est t-correcteur (ou corrige t erreurs) quand toute erreur portant sur au plus t bits est corrigée correctement. On voit donc que le code C est t-correcteur si et seulement si les boules fermées (dans {0, 1} n muni de la distance de Hamming) de centres les éléments de C et de rayon t sont disjointes, ou encore si et seulement si la distance minimum d de C vérifie d ≥ 2t + 1 . Il est souvent difficile de calculer la distance minimale et plus encore de décoder un mot sans structure additionnel c’est pourquoi on préfère travailler avec des codes linéaires[48].

Les codes linéaires

Les codes correcteurs pour lesquels la redondance dépend linéairement de l’information peuvent être définis par une matrice génératrice G de taille k × n[47] : Figure 3.3 – Exemple Source: [47] 

Définition

Un code binaire C est linéaire si la somme de deux mots quelconques du code est encore un mot du code : w1, w2 ∈ C, w1 + w2 ∈ C Un code linéaire est donc un sous-espace vectoriel de Z/pZ. En particulier le nombre de mots du code est 2p, ou p est la dimension de C. Remarque : dans un code linéaire, le mot 0n est toujours un mot du code : En effet si x est un mot du code quelconque, alors x + x = 0n est aussi un mot du code[49].

Représentations matricielles

La détermination du mot de code associé à un bloc, telle que nous venons de la décrire, se ramène à un produit de matrices ; voyons comment. Un mot binaire peut être représenté par une matrice ligne dont les coefficients sont les bits de ce mot. Pour économiser les notations, nous donnerons le même nom à la matrice ligne et au mot binaire qu’elle représente. Exemple . Le mot binaire b=01001 est représenté par matrice ligne : b= (0 1 0 0 1) On appelle matrice génératrice du codage et on note G, la matrice à k lignes et n colonnes obtenue en écrivant l’un au-dessous de l’autre et dans l’ordre, les mots de code des blocs bi de la base canonique. Parce que le codage est systématique, les k bits d’information sont écrits en premier, sans en changer l’ordre, et les bits de contrôle viennent ensuite.