Matrice de contrôle - Définition

Introduction

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ébriques 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.

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 :

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 :

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 :

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 :