Code linéaire

En théorie du codage , un code linéaire est un code correcteur d'erreurs pour lequel toute combinaison linéaire de mots de code constitue également un mot de code. Les codes linéaires sont traditionnellement classés en codes par blocs et codes convolutifs , bien que les turbocodes puissent être considérés comme un hybride de ces deux types. Les codes linéaires permettent des algorithmes de codage et de décodage plus efficaces que d'autres codes (cf. décodage par syndrome ).la correction d'erreurs sans voie de retour et sont appliqués dans les méthodes de transmission de symboles (par exemple, des bits ) sur un canal de communication . Ainsi, en cas d'erreurs de communication, certaines peuvent être corrigées ou détectées par le destinataire d'un bloc de message. Les mots de code d'un code linéaire par blocs sont des blocs de symboles codés avec un nombre de symboles supérieur à celui de la valeur originale à transmettre. Un code linéaire de longueur n transmet des blocs contenant n symboles. Par exemple, le code de Hamming [7,4,3] est un code binaire linéaire qui représente des messages de 4 bits à l'aide de mots de code de 7 bits. Deux mots de code distincts diffèrent par au moins trois bits. Par conséquent, jusqu'à deux erreurs par mot de code peuvent être détectées, tandis qu'une seule erreur peut être corrigée. Ce code contient 2⁴ ⁼ 16 mots de code.

En tant que sous-espace vectoriel de , le code C entier (qui peut être très grand) peut être représenté comme l' espace engendré par un ensemble de mots de code (appelé base en algèbre linéaire ). Ces mots de code de base sont souvent regroupés dans les lignes d'une matrice G, appelée matrice génératrice du code C. Lorsque G a la forme de matrice par blocs , où désigne la matrice identité et P une matrice quelconque, alors on dit que G est sous forme standard .

Une matrice H représentant une fonction linéaire dont le noyau est C est appelée matrice de contrôle de C (ou parfois matrice de parité). De manière équivalente, H est une matrice dont le noyau est C. Si C est un code dont la matrice génératrice G est sous forme standard, alors H est une matrice de contrôle pour C. Le code généré par H est appelé le code dual de C. On peut vérifier que G est une matrice, tandis que H est une matrice.

La linéarité garantit que la distance de Hamming _minimale d entre un mot de code c₀ et n'importe quel autre mot de code _c ≠ c₀ est indépendante de _c₀ . Ceci découle du fait que la différence c − c₀ de deux mots de code dans C est également un mot de code (c'est - à _- dire un élément du sous-espace C ), et du fait que d ( c , c₀ ₎ = d ( c − c₀ , ₀ ) . Ces propriétés impliquent que

Autrement dit, pour déterminer la distance minimale entre les mots de code d'un code linéaire, il suffit de considérer les mots de code non nuls. Le mot de code non nul de poids minimal est alors le moins éloigné du mot de code nul et détermine ainsi la distance minimale du code.

La distance d d'un code linéaire C est également égale au nombre minimal de colonnes linéairement dépendantes de la matrice de contrôle H.

Démonstration : Puisque , ce qui est équivalent à , où est la colonne de . Supprimons les éléments avec , ceux avec sont linéairement dépendants. Par conséquent, est au moins le nombre minimal de colonnes linéairement dépendantes. D'autre part, considérons l'ensemble minimal de colonnes linéairement dépendantes où est l'ensemble des indices de colonnes. . Considérons maintenant le vecteur tel que si . Remarquons que puisque . Par conséquent, nous avons , ce qui est le nombre minimal de colonnes linéairement dépendantes dans . La propriété énoncée est donc démontrée.

Le paramètre d est étroitement lié à la capacité de correction d'erreurs du code. L'algorithme suivant illustre ce phénomène (il s'agit de l'algorithme de décodage par plus proche voisin) :

Entrée : Un vecteur reçu v dans

Résultat : Un mot de code le plus proche de , le cas échéant.

• En commençant par , répétez les deux étapes suivantes.
• Énumérer les éléments de la boule de rayon (Hamming) autour du mot reçu , noté .
  • Pour chaque élément de , vérifiez s'il est dans . Si oui, renvoyez comme solution.
• Incrémenter . Échouer uniquement lorsque l'énumération est terminée et qu'aucune solution n'a été trouvée. (d - 1)/2" $(d-1)/2t>(d-1)/2$(d-1)/2

On dit qu'un code linéaire est correcteur d'erreurs s'il existe au plus un mot de code dans , pour chaque dans .

Lemme ( borne Singleton ) : Tout code linéaire [ n , k , d ] C satisfait .

Un code C dont les paramètres satisfont k + d = n + 1 est dit séparable à distance maximale ou MDS . De tels codes, lorsqu'ils existent, sont en un certain sens les meilleurs possibles.

Si C₁ et C₂ sont deux codes de longueur n et s'il existe une permutation p dans le _groupe symétrique Sₙ telle que ( c₁ _{, ...} , cₙ ) ∈ C₁ si et seulement si ( cₚ _{(1) , ... , cₚ} ( n _{) ) ∈ C₂} , alors on dit que _C₁ et C₂ sont équivalents par permutation . Plus généralement, s'il existe une matrice monomiale qui envoie _{C₁ isomorphe} à C₂ _, alors on dit _que C₁ et _{C₂ sont} équivalents .

Lemme : Tout code linéaire est équivalent par permutation à un code sous forme standard.

Un code est dit équidistant si et seulement s'il existe une constante d telle que la distance entre deux mots de code distincts quelconques du code soit égale à d . En 1984, Arrigo Bonisoli a déterminé la structure des codes linéaires à un poids sur les corps finis et a prouvé que tout code linéaire équidistant est une suite de codes de Hamming duaux .

Voici quelques exemples de codes linéaires :