Codes linéaires

Le corps de galois (ou corps fini) comprenant $q$ éléments est est noté $GF(q)$, par exemple $GF(2)$. Un code linéaire est un sous espace de l'espace vectoriel à $n$ composantes. Ces composantes appartiennent à $GF(q)$. On peut y appliquer les opérations sur un espace vectoriel, typiquement les produits d'une matrice par un vecteur. Un code linéaire sera engendré par une ``matrice génératrice'' $G$. Par exemple, sur le corps fini $GF(2)$, un mot du code $y$ comportant $n$ composantes s'obtiendra à partir d'un mot à coder $x$ comportant $k$ composantes

$$y=G.x$$ (47)

Si

$$G=\left[\begin{array}{ccc} 1&0&0\\ 0&1&0\\ 0&0&1\\ 1&0&1\\ 0&1&1 \end{array}\right]$$ (48)

et si par exemple

$$x=\left[\begin{array}{c}0\\ 1\\ 1\end{array}\right]$$ (49)

$$y=G.x=\left[\begin{array}{ccc} 1&0&0\\ 0&1&0\\ 0&0&1\\ 1&0... ...ht]=\left[\begin{array}{c}0\\ 1\\ 1\\ 1\\ 0\end{array}\right]$$ (50)

Si les $k$ premières composantes de $y$ sont les composantes de $x$, on dit que le code est systématique (les $k$ premières lignes de $G$ forment une matrice carrée qui est la matrice identité). Dans ce cas les $(n-k)$ dernières composantes de $y$ sont des symboles de parité. La matrice $G$ engendre tous les vecteurs du sous-espace qui forment le code. Ce sous-espace comporte un sous-espace complémentaire, composé des vecteurs orthogonaux à ceux du code. Ces vecteurs constituent le code dual du premier. Soit $H$ la matrice permettant d'engendrer les mots du code dual (une base du sous-espace complémentaire du sous-espace engendré par $G$). Alors tout vecteur $y$ du code $G$ est orthogonal à tout vecteur du code $H$. Dans l'exemple précédent

$$H=\left[\begin{array}{cc} 1&0\\ 0&1\\ 1&1\\ 1&0\\ 0&1 \end{array}\right]$$ (51)

On a

$$H^T.G=0$$ (52)

et pour tout vecteur $y$ du code

$$H^T.y=0$$ (53)

$H$ est la matrice de contrôle ou de test de parité de $G$. Cette matrice permet de vérifier que $y$ appartient bien au code (qu'il n'y a pas eu d'erreur de transmission décelable). Lorsque

$$H^T.y\ne 0$$ (54)

il y a une erreur de transmission. Corriger l'erreur de transmission revient à chercher le mot appartenant au code le plus proche (au sens de la distance de Hamming) du mot reçu.