12. Codes correcteurs

12.1. Cours

• rappels sur les corps finis
• codes cycliques = idéaux de \(\F_q[x]/x^n-1\), polynôme générateur, vérificateur. Générateur de l’orthogonal.
• factorisation de \(x^n-1\) dans \(\F_q[x]\).
• codes BCH (distance prévue)

12.2. Codes cycliques

1. Écrire une fonction qorbites(n,q) qui calcule la liste des \(q\)-orbites de \(\Z/n\Z\).
2. Combien y a-t-il de codes binaires cycliques de longueur 15 ?

12.2.1. Code de Golay

1. On considère un code \(G_{11}\) ternaire cyclique de dimension \(k=6\) et de longueur \(n=11\).
   • montrer l’existence de \(G_{11}\).
   • calculer la factorisation de \(x^11-1\), et donner un polynôme générateur de \(G_{11}\).
   • montrer que \(4\leq d(G_{11})\leq 5\)
   • donner un générateur du sous-code pair \(G^0\) formé des mots de \(G_{11}\) qui sont dans le noyau de la forme \(c\mapsto \sum c_i\).
   • donner un générateur de l’orthogonal de ce sous-code pair : le reconnaître.
   • montrer que \(G_{11} = G^0 \oplus \F_3\dot\Phi_11\)
   • en remarquant que le poids d’un mot vérifie \(w(c)\equiv \langle c,c\rangle\bmod 3\), calculer la distance de \(G_{11}\)
   • montrer que c’est un code parfait
2. Générer la liste des polynômes de \(\F_3[x]\) degré inférieur à \(5\), et vérifier le résultat par énumération des mots de code.

12.3. Codes de Reed et Solomon

Soit \(q=p^m\), et \(t<\floor{\frac{q-1}2}\). Le code de Reed-Solomon \(t\)-correcteur sur \(\F_q\) est un code BCH de longueur \(n=q-1\), de distance prévue \(2t+1\), qui est MDS.

1. Montrer l’existence et l’unicité (à équivalence près) d’un tel code.

2. Soit \(c(x)\) un mot de code, et \(e(x)\) l’erreur de transmission, où l’on suppose que l’on peut écrire \(e(x)=\sum_{i\in T} e_i x^i\) avecs \(\card T\leq t\).

   On introduit le polynôme syndrome

   \[S(x) = \sum_{l=1}^{2t} y(\alpha^l)x^{l-1}\]

   et le polynôme localisateur d’erreur

   \[E(x) = \prod_{i\in T}(1-\alpha^ix).\]

   Calculer \(R(x)=S(x)E(x)\bmod x^{2t}\). En déduire un algorithme de décodage.

12.4. Codes gloutons

1. Donner un algorithme de parcours de \(\F_2^n\) par ordre lexicographique, et le programmer.

On considère la construction de code gloutonne suivante :

• on part du code nul \(C=\set{0}\)
• on parcourt les éléments de \(\F_2^n\) par ordre lexicographique, en ajoutant à \(C\) chaque élément à distance \(\geq d\) de tous les éléments déjà contenus.

1. Construire de la sorte un code binaire de longueur \(23\) et de distance \(7\) qui soit parfait. Montrer que c’est un code linéaire.