14.5 Codes de correction d’erreurs

De nos jours, les communications numériques utilisent la transmission de données binaires à travers un canal entaché de bruit. Par exemple, lorsque la sonde spatiale Voyager 2 transmet des images, ces dernières sont encodées à l’aide de bits : 0, 1. Lorsque les informations voyagent de la sonde à la Terre, elles soumises à plusieurs facteurs d’interférence. En conséquence, il est important à pouvoir détecter (et corriger) les erreurs dans les données reçues. Pour permettre la détection et la correction d’erreurs, la sonde doit transmettre des données supplémentaires.

La théorie du codage est l’étude des manières de minimiser cette quantité supplémentaire qui doit être transmise afin d’atteindre un certain niveau d’efficacité pour la détection et la corrections d’erreurs.

Dans cette section, nous allons présenter un avant-goût de ce vaste sujet. Plus particulièrement, nous allons voir comment utiliser les notions d’algèbre linéaire afin de construire des codes de correction d’erreurs.

Supposons que l’on désire transmettre des messages qui ne sont composés que des lettres « A », « G », « N » et « S ». Puisque l’on peut seulement transmettre des 0 et des 1, nous allons devoir encoder chaque lettre à l’aide une chaîne binaire. Par exemple, nous pouvons utiliser le code suivant :

A	00
G	01
N	10
S	11

Les chaînes binaires 00, 01, 10 et 11 sont les mots de code. La collection de tous les mots de codes forme l’ensemble des codes binaires . Pour transmettre le mot « SANG », par exemple, nous remplaçons simplement chaque lettre du mot par la chaîne binaire correspondante. On transmet alors 11001001 au canal de communication.

Si le canal est bruyant, une ou plusieurs des chiffres binaires peut être affectés. Par exemple, on pourrait recevoir 11001011 au lieu du mot envoyé, 11001001. Cette chaîne binaire correspond au message « SANS ». Puisque le message reçu est complètement valide (en tant que terme français), il n’y a aucune façon de savoir si c’est bien le message qui a été envoyé, ou si c’est le résultat d’une erreur.

Afin de détecter de telles erreurs, nous devoir utiliser des mots de codes qui sont suffisamment différents les uns des autres. Pour deux chaînes binaires de même longueur, la distance de Hamming qui les sépare est le nombre de positions où ils sont différent. Par exemple, la distance de Hamming séparant 001 et 100 est de 2.

La distance minimale entre toutes les paires différentes de mots de code limite le nombre d’erreurs pouvant être détectées. Si on ne cherche qu’à détecter une seule erreur, la distance de Hamming minimale doit être d’au moins 2. Pour le code binaire présenté ci-dessus, la distance de Hamming minimale est de 1; nous sommes donc dans l’incapacité de détecter des erreurs. Nous pouvons par contre améliorer la situation en ajoutant un chiffre supplémentaire (le bit de parité) à la fin de chacun de mots de code. Le bit de parité est la somme (dans \(GF(2)\)) des chiffres des mots de code binaires :

A	000
G	011
N	101
S	110

Pour transmettre le message « SANG », on envoie la chaîne binaire 110000101011. Si une erreur se produit, disons à la troisième décimale, on reçoit plutôt 111000101011.

Puisque 111 n’est pas un mot de code, on sait qu’une erreur s’est produite. Malheureusement, suite à cette information seulement, il n’y a aucune façon de savoir si la lettre originale était « G », « N » ou « S » puisque ces trois lettres sont toutes à la même distance de Hamming de 111. Cet exemple illustre qu’une plus grande distance de Hamming est nécessaire à la correction des erreurs.

Une façon commune de générer des mots de codes binaires est d’utiliser l’espace des colonnes d’une matrice \(\mathbf{G} \in GF(2)^{n\times k}\). (Autrement dit, nous représentons les chaînes binaires par des vecteurs dont les éléments se retrouvent dans \(GF(2).\)) La matrice \(\mathbf{G}\) est la matrice génératrice du code et chaque mot de code est dit généré par \(\mathbf{G}\).

Exemple 14.2 L’ensemble des mots de code généré par la matrice génératrice \(\mathbf{G} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{bmatrix}\) est \(\left\{\begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ 1 \\ 0 \\ 1 \\ 1 \end{bmatrix}, \begin{bmatrix} 1 \\ 0 \\ 1 \\ 0 \\ 1 \end{bmatrix}, \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 0 \end{bmatrix} \right\}.\)

Ce choix facilite la détection des erreurs. Soit \(\{\mathbf{u}^1,\ldots, \mathbf{u}^m\}\) une base de \({\operatorname{Ker}({\mathbf{G}})}.\) Alors \(\mathbf{c}\) est un mot de code généré par \(\mathbf{G}\) si et seulement si \[{\mathbf{u}^i}^\mathsf{T}\mathbf{c} = 0\] pour chaque \(i = 1,\ldots, m.\) En posant \(\mathbf{H} = \begin{bmatrix} {\mathbf{u}^1}^\mathsf{T}\\ \vdots \\ {\mathbf{u}^m}^\mathsf{T}\\ \end{bmatrix},\) la condition s’exprime plus simplement par \[\begin{equation} \mathbf{H} \mathbf{c} = \mathbf{0}.\tag{14.1} \end{equation}\] La matrice de contrôle \(\mathbf{H}\) du code généré par \(\mathbf{G}\) permet de déterminer efficacement si une chaîne donnée est un mot de code.

Exemple 14.3 La matrice de contrôle des mots de codes de l’exemple 14.2 est \[\mathbf{H} = \begin{bmatrix} 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1\end{bmatrix}.\] Notons que \(\mathbf{r} = \begin{bmatrix} 0 \\ 1 \\ 1 \\ 1 \\ 0 \end{bmatrix}\) n’est pas un mot de code généré par \(\mathbf{G}.\) On peut aussi le constater en remarquant que \[\mathbf{H} \mathbf{r} = \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix}.\]

 

Terminons cette section avec une importante question : comment obtient-on une matrice génératrice bien adaptée? Nous n’allons pas donner de réponse ici : c’est un domaine de recherche très actif. Notons simplement qu’il y a deux choses très importantes à considérer. La première est le ratio \(\frac{k}{n}\) (taux d’informations) du code. La seconde est la distance de Hamming minimale parmi toutes les pairs de mots de code distincts qui sont générées.

Exercices

1. Soit \(C\) un code binaire généré par \(\mathbf{G}.\) Pour un mot de code \(\mathbf{c}\) non nul, soit \(w(\mathbf{c})\) le nombre de 1 apparaissant dans \(\mathbf{c}.\) Montrez que la distance de Hamming minimale parmi toutes les paires distinctes de mots de code de \(C\) est donnée par \[\min_{\mathbf{c} \in C, \mathbf{c} \neq \mathbf{0}} w(\mathbf{c}).\]

2. Considérons la matrice génératrice \[\mathbf{G} = \begin{bmatrix} 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}\] sur \(GF(2).\)

   1. Donnez une liste de tous les mots de code générés par \(\mathbf{G}.\)

   2. Déterminez la distance de Hamming mininale parmi toutes les pairs de mots de code distincts.

   3. Déterminez une matrice de contrôle pour le code binaire correspondant.

   Remarque. Le code binaire généré par \(\mathbf{G}\) est connu sous le nom de Hamming(7,4).