Matrice de contrôle

Une matrice de contrôle est un concept de théorie des codes utilisé dans le cas des codes correcteurs linéaires.

Elle correspond à la matrice d'une application linéaire ayant pour noyau le code.

La notion de matrice de contrôle possède à la fois un intérêt théorique dans le cadre de l'étude des codes correcteurs, par exemple pour offrir des critères sur la distance minimale du code ou une condition nécessaire et suffisante pour qu'un code soit parfait et un intérêt pratique pour un décodage efficace.

Contexte

Code correcteur

Un code correcteur possède pour objectif la détection ou la correction d'erreurs après la transmission d'un message. Cette correction est permise grâce à l'ajout d'informations redondantes. Le message est plongé dans un ensemble plus grand, la différence de taille contient la redondance, l'image du message par le plongement est transmis. En cas d'altération du message, la redondance est conçue pour détecter ou corriger les erreurs. Un exemple simple est celui du code de répétition, le message est, par exemple, envoyé trois fois, le décodage se fait par vote. Ici, l'ensemble plus grand est de dimension triple à celle du message initial.

Rappelons les éléments de base de la formalisation. Il existe un ensemble E constitué de suites à valeurs dans un alphabet et de longueur k, c’est-à-dire qu'à partir du rang k, toutes les valeurs de la suite sont nulles. Ces éléments sont l'espace des messages que l'on souhaite communiquer. Pour munir le message de la redondance souhaitée, il existe une application φ injective de E à valeurs dans F, l'espace des suites de longueur n et à valeurs dans un alphabet. La fonction φ est appelée encodage, φ(E) aussi noté C est appelé le code, un élément de φ(E) mot du code, k la longueur du code et n la dimension du code. Ces notations sont utilisées dans tout l'article.

Code linéaire

Un code linéaire dispose d'une structure algébrique plus riche que celle du cadre général des codes correcteurs.

Les alphabets A et A' sont identifiés et munis d'une structure de corps fini. Le cas le plus fréquent consiste à choisir le corps F₂ ou l'une de ses extensions finies, on parle alors d'alphabet binaire.

Les ensembles E et F sont naturellement munis d'une structure d'espace vectoriel de dimension respectives k et n. Si F_d désigne le corps fini (cf l'article corps fini) de cardinal d où d est une puissance d'un nombre premier p, alors l'espace vectoriel F est généralement identifié à F_dⁿ.

F est muni d'une distance qui dérive du poids de Hamming. La distance entre deux points de F correspond au nombre de coordonnées non nulles de la différence entre les deux points, dans la base canonique. Un code se décrit par trois paramètres, noté [n, k, δ], n est la dimension du code, k la longueur du code et δ la distance minimale entre deux mots du code. Ces notations sont utilisées dans le reste de l'article.

Enfin, l'application d'encodage φ est choisie linéaire, le code est donc un sous-espace vectoriel.

Définitions

L'objectif d'un code correcteur est la détection ou la correction d'altérations possibles dans la transmission . Dans le cas d'un code linéaire, cette opération est grandement simplifiée. Le code est un sous-espace vectoriel de dimension k, il suffit donc de vérifier l'appartenance à ce sous-espace pour déterminer si des altérations se sont produites. Tout espace vectoriel se définit par l'intersection d'autant d'hyperplans que la codimension du sous-espace. Or un hyperplan est le noyau d'une forme linéaire. En conséquence, si F^* désigne l'espace dual, on obtient :

$\exists (e_{i}^{*})\in {F^{*}}^{n-k}\quad /\quad x\in \varphi (E)\Leftrightarrow \forall i\in [1,n-k]\quad e_{i}^{*}(x)=0$

Ce qui s'écrit encore sous forme d'un système d'équations linéaires :

$x=(x_{1}\cdots x_{n})\in \varphi (E)\Leftrightarrow \left\{{\begin{matrix}a_{11}.x_{1}+\cdots +a_{1n}.x_{n}=0\\a_{21}.x_{1}+\cdots +a_{2n}.x_{n}=0\\\vdots \\a_{n-k1}.x_{1}+\cdots +a_{n-kn}.x_{n}=0\end{matrix}}\right.$

Ce qui amène à la définition suivante :

• Une matrice de contrôle d'un code φ(E) est une matrice H de dimension nx(n - k) tel que :

$x\in \varphi (E)\Leftrightarrow H.^{t}x=0$

Ce qui s'exprime encore de la manière suivante :

• Une matrice de contrôle d'un code φ(E) est une matrice d'une application linéaire surjective de F dans un espace vectoriel ayant pour noyau le code.

On remarque que, comme l'application linéaire est surjective et vérifie l'égalité dim Imφ + dim Kerφ = dim F, l'ensemble d'arrivée de l'application linéaire associée à la matrice de contrôle est un espace vectoriel de dimension n - k.

Exemples

Somme de contrôle binaire

La somme de contrôle binaire de longueur k correspond à un code de paramètre [k + 1, k, 2], à un message est associé le mot du code égal au message concaténé avec le bit de parité de la somme de toutes les lettres du message (qui vaut un si la somme est impair et zéro sinon). Il a pour matrice génératrice G_s et, si I_k désigne la matrice unité d'ordre k :

$G_{s}={I_{k} \choose C}\quad avec\quad C=(1,\cdots ,1)$

On remarque que, pour un code binaire, 1 est égal à -1.

Le code est un hyperplan de F, la matrice de contrôle est donc de dimension 1xk, elle correspond à la matrice d'une forme linéaire. Un point de F est un mot du code si et seulement si la somme de ses lettres est paire. Ce qui montre que sa matrice de contrôle H_s possède la forme suivante :

$H_{s}=(1,\cdots ,1)$

Code de Hamming (7,4)

Description du code de Hamming binaire de paramètre [7,4,3]

Le code de Hamming (7,4) est un code binaire de paramètre [7,4,3]. La figure de droite est une représentation graphique de ce code. Le message est le mot d₁d₂d₃d₄. Le mot du code est constitué des quatre lettres du mot du message, puis de trois sommes de contrôles p₁p₂p₃. La valeur de p_i est égal à zéro si la somme des trois lettres du message incluses dans son cercle sur la figure est paire et un sinon.

Il possède donc la matrice génératrice G_h suivante :

$G_{h}={\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\\1&1&0&1\\1&0&1&1\\0&1&1&1\end{pmatrix}}$

L'objectif est de trouver trois vecteurs e₁^*, e₂^* et e₃^* de l'espace dual F^* libres, qui annulent les quatre vecteurs images de la base de E par φ. Ceci revient, si F^* est identifié à F en considérant la base canonique comme une base orthogonale à trouver trois vecteurs orthogonaux aux vecteurs colonnes de la matrice G_h. On obtient par exemple, si H_h désigne une matrice de contrôle :

$H_{h}={\begin{pmatrix}1&1&0&1&1&0&0\\1&0&1&1&0&1&0\\0&1&1&1&0&0&1\end{pmatrix}}$

Propriétés

Code systématique

Il existe une forme particulièrement simple pour la matrice génératrice, donné par le code systématique. Dans ce cas, la matrice génératrice prend la forme suivante :

$G={I_{k} \choose C}$

Ou I_k désigne la matrice identité d'ordre k et C une matrice de dimension n-kxk correspondant aux contrôles de redondance.

• Dans le cas d'un code systématique, et avec les notations précédentes alors l'expression suivante est celle d'une matrice de contrôle :

$\forall c\in C\quad (-C\;I_{n-k})\,^{t}c=0$

En effet :

$(-C\;I_{n-k})\,{I_{k} \choose C}\,^{t}x=-C\,^{t}x+C\,^{t}x=0$

Cette technique a été appliquée pour déterminer une matrice de contrôle du code de Hamming cité en exemple.

Code parfait

La distance minimale δ correspond à la plus petite distance entre deux mots du code, c'est aussi le rayon de la plus grande boule de centre le vecteur nul et ne contenant pas d'autre mot du code que le vecteur nul. Cette distance est importante car elle permet de calculer la valeur t du nombre maximal d'erreurs assurément corrigibles, t est égal au plus grand entier strictement inférieur à δ/2. Elle correspond à la plus grande valeur tel que les boules fermées de centre les points du code et de rayon t ont toutes une intersection vide deux à deux. La matrice de contrôle possède une propriété intéressante, s'exprimant de la manière suivante si la matrice H est identifiée à son application linéaire :

• La restriction de H à la boule fermée de centre un mot du code et de rayon t est injective.

En effet, considérons deux éléments de la boule, c + e₁ et c + e₂ où c est un mot du code et e₁ et e₂ deux vecteurs de poids inférieur ou égal à t. S'ils ont même image par H alors leur différence est élément du code car le code est le noyau de H, donc e₁ - e₂ est un élément du code. Il est à une distance strictement inférieure à δ du vecteur nul, la boule de centre le vecteur nul et de rayon δ ne rencontre le code qu'au point nul, donc e₁ et e₂ sont égaux.

Il existe un cas particulier important, celui où les boules fermées de centre les mots du code et de rayon t forment une partition de F, on parle alors de code parfait. La proposition précédente prend la forme suivante :

• Si le code est parfait, la restriction de H à la boule fermée de centre un mot du code et de rayon t est bijective.

En, effet, Soit h un élément de l'ensemble d'arrivé de H, il admet un antécédent car H est surjective. Cet antécédent est élément d'une boule de la partition. Soit c + e avec c un mot du code et e un élément de F de poids inférieur ou égal à t cet antécédent. H^te admet pour image h car H^tc est le vecteur nul (tout mot du code est élément du noyau de H). La restriction de H est donc surjective, elle est injective d'après la proposition précédente.

En plus de permettre le décodage, la matrice de contrôle offre une méthode de calcul de la distance minimale δ :

• La distance minimale δ d'un code linéaire est égale à la dimension du plus petit sous-espace vectoriel S de F généré par des éléments de la base canonique et tel que la restriction de la matrice de contrôle à S soit non injective.

En effet, soit d la dimension du sous-espace vectoriel S de l'énoncé. Si un mot non nul est de poids strictement inférieur à d, son image par la matrice de contrôle ne peut, par définition de d être nulle, δ est donc supérieure ou égale à d. Réciproquement, il existe un code inclus dans S tel que son image par la matrice est nulle car la matrice de contrôle n'est pas injective sur S. La distance minimale δ est donc inférieure ou égale à d, ce qui termine la démonstration.

Correction d'erreurs

La connaissance des images par H de la boule fermée de centre le vecteur nul et de rayon t permet de corriger les erreurs du message. Si x élément de F est transmis au récepteur, le mot de code le plus proche est x - e où e est l'unique antécédent de H^tx dans la boule. Ce qui donne lieu à la définition suivante :

• Un élément H^tx de l'ensemble d'arrivé de H est appelé syndrome.

Si le code est parfait, alors tout vecteur de F s'exprime comme la somme d'un mot du code et d'un vecteur de poids inférieur ou égal à t. Il suffit donc de calculer les images par H de la boule fermée de centre le vecteur nul et de rayon t pour corriger un message contenant t ou moins de t erreurs. Si un message x est reçu, le message corrigé est x - e où e désigne l'antécédent de H^tx dans la boule.

Dans le cas où le code n'est pas parfait, une approche similaire est néanmoins possible. Il est nécessaire pour cela de considérer s le plus petit entier tel que les boules fermées de centre les points du code et de rayon s forment un recouvrement de F.

• La restriction de H à la boule fermée de centre un mot du code et de rayon 's est une surjection.

La démonstration est analogue à la précédente. Dans le cas général la connaissance des antécédents de H dans la boule permet encore le décodage, seulement certains antécédents, (ceux de poids strictement supérieurs à t) ne sont pas uniques, il est alors nécessaire d'en choisir un aléatoirement, le risque de laisser une erreur au décodage voir d'en créer une nouvelle est important.

Voir aussi

Bibliographie

• (en) Jessie MacWilliams et Neil Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977 (ISBN 978-0-44485009-6)
• A. Spătaru, Fondements de la théorie de la transmission de l'information, PPUR, 1987 (ISBN 978-2-88074133-4)
• Michel Demazure, Cours d'algèbre : primalité, divisibilité, codes [détail des éditions]
• B. Martin, Codage, cryptologie et applications, PPUR, 2004 (ISBN 978-2-88074569-1)

Liens externes

• Code correcteur C.I.R.C par J.P. Zanotti, université de Toulon
• L'algèbre et la correction des erreurs par Dany-Jack Mercier, université Antilles-Guyane
• Code Linéaire par G. Zemor, université Bordeaux I
• Cours de code par Christine Bachoc, université Bordeaux I
• Code correcteur par M. Coste, A. Paugam, R. Quarez, université de Rennes