Codes correcteurs

Rappels de cours

• distance minimale, matrice génératrice, vérificatrice

• bornes de Hamming et de Singleton, codes parfaits, MDS

• 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]\).

  Si \(q\wedge n=1\) et \(\alpha\) est une racine \(n\)-ième primitive de l’unité, \(x^n-1=\prod_{i\in\Z/n\Z}(x-\alpha^i)\) se factorise sur \(\F_q\) en \(\prod_I f_I(x)\) où \(I\) parcourt les \(q\)-orbites de \(\Z/n\Z\) et \(f_I(x)=\prod_{i\in I}(x-\alpha^i)\).

• codes de Reed-Solomon pour \(n\mid q-1\), ils sont MDS.

• codes BCH (distance prévue)

  Note

  Soit \(\alpha\) une racine nième de l’unité ; si \(g(x)\) s’annule en \(r\) puissances consécutives \(\alpha^{i+1},\dots \alpha^{i+r}\), alors le code est de distance minimale \(\geq r+1\) (Ecrire la matrice de Vandermonde codant l’annulation d’un polynôme de poids \(r\)).

Code de Golay \(G_{23}\)

1. Factoriser \(x^{23}-1\) sur \(\F_2\).

2. \(G_{23}\) est un \([23,12]\) code cyclique binaire. Montrer qu’il existe deux tels codes.

   solution xcas ⇲ ⇱ solution xcas

   factor(x^23-1 % 2)

3. Calculer un polynôme générateur de \(G_{23}\).

   solution xcas ⇲ ⇱ solution xcas

   Le polynôme

   g := x^11 + x^9 + x^7 + x^6 + x^5 + x + 1
   

   convient.

   solution sage ⇲ ⇱ solution sage

   >>> factor(x^23-1)
   (x + 1) * (x^11 + x^9 + x^7 + x^6 + x^5 + x + 1) * (x^11 + x^10 + x^6 +
   x^5 + x^4 + x^2 + 1)
   

   Le polynôme

   >>> g = x^11 + x^9 + x^7 + x^6 + x^5 + x + 1
   

   convient.

4. Écrire une matrice génératrice \(G\) de \(G_{23}\)

   solution xcas ⇲ ⇱ solution xcas

   G := matrix(12, 23, (l,c)->coeff(g*x^l,c))
   

   solution sage ⇲ ⇱ solution sage

   >>> G = matrix(11,23) ## pb
   >>> G = pari("matrix(12,23)")
   >>> for i in range(12):
   ...   gi = g * x^i % (x^23-1)
   ...   for j in range(23)
   ...     G[i,j] = gi[j]
   >>> G.lift()
   

   Le code étendu consiste à rajouter le bit de parité, ou à partir du polynôme \((x-1)g(x)\)

   >>> Gb = pari("matrix(12,24)")
   >>> for i in range(12):
   ...   b = 0
   ...   for j in range(23):
   ...     Gb[i,j] = G[i,j]
   ...     b += G[i,j]
   ...   Gb[i,23] = b
   >>> Gb.lift()
   

Distance minimale

1. Montrer que \(d(G_{23})\geq 5\) (utiliser la borne BCH).

   solution xcas ⇲ ⇱ solution xcas

   On veut déterminer les racines de \(g\). En notant \(x\mod g\) une racine, on voit que les autres sont les \(x^j\) pour \(j\in\set{1, 2, 4, 8, 16, 9, 18, 13, 3, 6, 12}\).

2. Calculer une matrice génératrice \(\overline G\) du code étendu \(\overline{G_{23}}\), obtenu en ajoutant un bit de parité (\(\sum x_i=0\)).

   solution xcas ⇲ ⇱ solution xcas

   Le code étendu consiste à rajouter le bit de parité, ou à partir du polynôme \((x-1)g(x)\)

   GE := matrix(12, 24, (l,c)->coeff(rem(g*(x-1%2)*x^l,x^23-1),c))%0
   

3. Vérifier que \(\overline{G_{23}}\) est auto-orthogonal.

   solution sage ⇲ ⇱ solution sage

   >>> lift( Gb * GB.mattranspose() )
   

   solution xcas ⇲ ⇱ solution xcas

   GE * transpose(GE)

4. Montrer que les mots de \(\overline{G_{23}}\) ont un poids divisible par \(4\).

   solution xcas ⇲ ⇱ solution xcas

   C’est vrai sur chacun des vecteurs de base

5. Montrer que \(\overline{G_{23}}\) est de distance \(8\).

6. Montrer que \(G_{23}\) est un code parfait.

Code de Golay \(G_{11}\)

Le code de Golay ternaire \(G_{11}\) est un code cyclique de dimension \(k=6\) et de longueur \(n=11\).

1. montrer l’existence d’un tel code.
2. factoriser \(x^{11}-1\), et donner un polynôme générateur de \(G_{11}\).
3. montrer que \(4\leq d(G_{11})\leq 5\)
4. 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\).
5. donner un générateur de l’orthogonal de ce sous-code pair : le reconnaître.
6. montrer que \(G_{11} = G^0 \oplus \F_3\cdot\Phi_{11}\)
7. 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}\)
8. montrer que \(G_{11}\) est un code parfait
9. 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.