Code linéaire - Définition

Introduction

En mathématiques, plus précisément en théorie des codes, un code linéaire est un code correcteur.

Il est structuré comme un sous-espace vectoriel sur un corps fini. L'espace utilisé est souvent F₂ⁿ le terme usuel est alors celui de code linéaire binaire.

Il est décrit par trois paramètres, [n, k, δ] n décrit la dimension de l'espace qui le contient. Cette grandeur est appelée longueur du code. k représente la dimension du code, correspondant à la taille des mots une fois décodés et δ décrit la distance minimale, au sens de Hamming entre chaque mot du code.

Les codes linéaires représentent l'essentiel des codes correcteurs utilisés dans l'industrie. Cette approche couvre en particulier les codes proposant une simple détection, une nouvelle émission est alors demandée. D'autres codes permettent une correction des altérations à l'aide d'une gestion fine de la redondance.

Rappel: F₂ est l'unique corps à deux éléments et F₂ⁿ est un espace vectoriel de dimension n. Si le corps de base est F_d, le corps contenant d éléments, le terme consacré est code linéaire de base d. La théorie des corps finis assure que d est une puissance d'un nombre premier et qu'il existe un unique corps possédant ce cardinal.

Approche intuitive

Code correcteur

Un code linéaire est un cas particulier de code correcteur. L'objectif est de permettre 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. 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 de longueur k, c’est-à-dire qu'à partir du rang k, toutes les valeurs de la suite sont nulles, et à valeur dans un alphabet. 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 à valeurs dans un alphabet. La fonction φ est appelée encodage, φ(E) est appelé le code, un élément de φ(E) mot du code, k la longueur du code et n la dimension du code.

Pour permettre d'utiliser la puissance des outils mathématiques, il peut être judicieux de d'utiliser des structures algébriques. les alphabets de E et F sont choisis comme un même corps fini. Les éléments de E (resp. F) sont les suites finies de longueur k (resp. n), E et F héritent naturellement d'une structure d'espace vectoriel de dimension finie et d'une base canonique, celle de l'espace des suites finies à valeurs dans un corps. L'application encodage est choisie linéaire.

L'espace F est muni d'une distance appelée distance de Hamming dérivant d'une pseudo-norme, le poids de Hamming. Le poids de Hamming p d'un point de F correspond au nombre de ses coordonnées non nulles. La distance de Hamming entre deux éléments de F est le poids au sens de Hamming de leur différence.

Domaine d'application

Les codes linéaires correspondent à une très large majorité de type de codes correcteurs. Ils sont utilisés pour la détection d'altérations, avec comme méthode de correction associée une demande de retransmission, la technique utilisée la plus usuelle est alors la somme de contrôle. Elles sont utilisés dans une multitude de situations, depuis quelques erreurs isolées à de vastes altérations ou des phénomènes d'effacements.

Si le cadre utilisé est largement employé, il ne répond néanmoins pas à l'intégralité des besoins. On peut citer deux grands sujets, peu traités par la théorie des codes linéaires. Un bon code répond à un critère d'optimalité, il est dit parfait. Le cadre de la théorie des codes linéaires offre des critères pour valider cette optimalité. En revanche, il ne propose pas de méthode pour concevoir ce type de code.

Une méthode générale pour la correction des erreurs est disponible, le décodage par syndrome. Cette méthode consiste à créer une table associant à chaque erreur, sa solution. La table croît exponentiellement avec le nombre de lettres susceptible d'être erronées. Dans le cas d'une large capacité de correction, cette approche n'est plus opérationnelle.

La théorie des codes cycliques, utilisant largement les propriétés des corps finis répond à ces deux besoins. Un code cyclique est un code linéaire possédant une structure algébrique supplémentaire.