Approche algébrique des codes correcteurs

 Approche algébrique des codes correcteurs

Codes correcteurs en bloc Considérons le canal de communication  Pour lutter contre le bruit lié au canal, nous allons utiliser des blocs de n symboles pour transmettre k symboles du message. Cet ajout de n − k symboles se fait selon une règle, le codage, connue par l’émetteur et le récepteur. Cette règle est une bijection entre les mots d’information (toutes les suites de k symboles du message que nous voulons transmettre) et les mots du code (certaines suites de n symboles que nous transmettons effectivement).

Le code C est donc un sous ensemble de F n2 , de cardinal 2 k . Il est dit linéaire s’il s’agit d’un espace vectoriel. Dans ce cas, le codage se doit d’être également linéaire. Le code est de dimension k et de longueur n, et ses paramètres sont notés [n, k].

Exemple 2. Le code de Hamming est un code de dimension 4 et de longueur 7. À un mot d’information (x1, x2, x3, x4) ∈ (F2)⁴ est associé le mot du code (x1, x2, x3, x4, x5, x6, x7) ∈ (F2)⁷ , dans lequel x5, x6 et x7 sont définis par :

x5 = x1 + x2 + x4,
x6 = x1 + x3 + x4,
x7 = x2 + x3 + x4.

Une matrice génératrice d’un code linéaire est une matrice G ∈ Mk,n(F2) dont les lignes forment une base de C. Une telle matrice n’est pas unique et chacune fournit une règle de codage. Le choix d’une règle de codage se fait donc par le choix d’une de ces matrices, qui sera appelée la matrice génératrice du code. Le mot du code c s’obtient à partir du mot d’information m par la relation c = m · G.

Un code correcteur est dit systématique si les k premiers coefficients des mots du code sont les k symboles du mot d’information correspondant. Dans ce cas, les k premières colonnes de la matrice génératrice forment la matrice identité.

Exemple 4. Le code de Hamming ainsi défini est systématique.

Distance Le poids de Hamming wH(x) d’un mot x ∈ (Fq) n est le nombre de coordonnées xi non nulles.

wH(x) = #{i : xi 6= 0}

Il permet de définir la distance entre des mots comme le poids de leur différence. En d’autres termes, la distance de Hamming dH(x, y) entre deux mots x ∈ (Fq) n et y ∈ (Fq) n est le nombre de coordonnées distinctes de x et y. dH(x, y) = wH(x − y) = #{i : xi 6= yi}

Enfin, la distance (de Hamming) minimale d d’un code est la plus petite distance entre deux mots distincts du code.

d = min{dH(x, y) : x ∈ C, y ∈ C, x 6= y}

Exemple 5. Le code de Hamming que nous avons défini a pour distance minimale 3.

Si la distance minimale d du code est connue, ses paramètres sont notés [n, k, d] au lieu de [n, k]. Les performances d’un code dépendent directement de cette distance minimale.

Canal à erreur Dans ce type de canal, certains coefficients du mot du code c = m · G peuvent être changés durant la transmission. Cela est modélisé par l’ajout d’une erreur e ∈ Fn2 . Le récepteur obtient alors un mot de la forme y = c + e = m · G + e. Il est ensuite confronté aux problèmes suivants :
— Détection d’erreur : déterminer si le mot y reçu est conforme au mot du code c envoyé ou s’il a subi une erreur.
— Correction d’erreur : à partir du mot reçu y, retrouver le mot du code c envoyé.
— Décodage : à partir du mot reçu y, retrouver le mot d’information m.

La correction d’erreur et le décodage sont théoriquement équivalents, les mots d’information étant en bijection avec les mots du code. Nous pouvons toujours passer du mot décodé au mot corrigé en le re-codant. Le passage en sens inverse dépend du code. Il est immédiat pour les codes systématiques, et requiert la résolution d’un système linéaire dans les autres cas. Dans la plupart des utilisations, les codes correcteurs ont pour but de protéger les symboles d’information. C’est donc le décodage qui sera étudié, plutôt que la correction.

Décodage efficace Les problèmes abordés (détection, corrections, décodages) peuvent se résoudre par recherche exhaustive. De tels algorithmes consistent à parcourir tous les mots du code.
— Détection : rendre « correct » si le mot reçu est dans la liste des mots du code, « erroné » sinon.
— Correction d’effacements : pour chaque mot du code, supprimer les coefficients adéquats. Si le poids de l’effacement est inférieur ou égal à d − 1, un seul correspondra au mot reçu.
— Correction d’erreur : pour chaque mot du code, calculer sa distance au mot reçu. Si le poids de l’erreur est inférieur ou égal à d−1/2 , un seul mot du code minimise cette distance.
— Décodage (erreur ou effacement) : comme pour les algorithmes de correction, mais dans ce cas, nous parcourons l’ensemble des mots d’information et nous calculons le mot du code correspondant .

Ces algorithmes sont valables pour tous les codes correcteurs, mais ne sont utilisables que sur des codes ayant peu de mots. En effet, le décodage demande en moyenne q k/2 fois plus de calculs que le codage, pour une complexité en O(q kn ω), ω étant le coût de l’algèbre linéaire. Il faut donc trouver des algorithmes plus efficaces. Le problème de détection est résolu efficacement par le calcul du syndrome. Celui-ci est nul si et seulement si le mot reçu est un mot du code, et son calcul requiert O(n2 (n − k)) opérations. Les positions effacées étant connues du récepteur, le décodage des effacements se ramène à la résolution d’un système linéaire. Le problème le plus délicat est le décodage d’erreur. Il existe des algorithmes de décodage efficaces, mais ces derniers ne concernent qu’une famille restreinte de codes. Ainsi, il existe une méthode de décodage propre aux codes de Hamming, plusieurs algorithmes pouvant décoder les codes de Reed-Solomon, …

Table des matières

1 Introduction
1.1 Approche probabiliste des codes correcteurs
1.2 Approche algébrique des codes correcteurs
1.3 Quelques autres aspects des codes correcteurs
1.4 Transmissions MIMO
1.4.1 Modulation
1.4.2 Le canal SISO
1.4.3 Le canal MIMO
2 θ-polynômes et métriques basées sur le rang
2.1 θ-polynômes
2.1.1 Définition
2.1.2 Racines et espace des racines
2.1.3 Polynômes annulateurs et interpolateurs
2.2 Métriques basées sur le rang
2.2.1 Métriques sur des matrices
2.2.2 Métrique rang sur Ln
2.3 Autour de l’hypothèse Hdim
2.3.1 Exemples
2.3.2 Conditions équivalentes à Hdim
2.3.3 Quelques extensions cycliques
3 Codes de Gabidulin généralisés
3.1 Définition
3.2 Décodage et reconstruction (modèle d’erreur seule)
3.3 Premier modèle d’effacement
3.4 Second modèle d’effacement
4 Un algorithme de reconstruction de type Welch-Berlekamp
4.1 Algorithme de type Welch-Berlekamp
4.2 Preuve
4.3 Complexité
4.3.1 Complexité des opérations sur les θ-polynômes
4.3.2 Complexité de l’algorithme de Reconstruction
4.3.3 Complexité des algorithmes de décodage
4.4 Améliorations
4.4.1 Une version sans division
4.4.2 Polynômes de plus bas degré
4.4.3 Mise à jour des défauts
5 Codes de Gabidulin généralisés et finis
5.1 Problématique : explosion des coefficients
5.2 Idéaux maximaux
5.2.1 Cas des corps de nombres
5.2.2 Cas des corps de fonctions
5.2.3 Quotients et groupes de Galois
5.3 Réduction d’un code de Gabidulin
5.3.1 Codes à coefficients dans OL
5.3.2 Quotient d’un code de Gabidulin généralisé
5.3.3 Décodage d’un code de Gabidulin généralisé via une réduction
6 Conclusion

Télécharger le rapport complet