Codes correcteurs

Cours

• espace de Hamming, code, détection, correction, distance minimale

• matrice génératrice, code orthogonal, matrice vérificatrice

• codes de Hamming

• 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}\) 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 BCH (distance prévue)

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 ?
3. Les identifier en factorisant \(X^{15}-1\) sur \(\F_2\).

Code de Golay \(G_{23}\)

1. \(G_{23}\) est un \([23,12]\) code cyclique binaire. Montrer son existence, et que \(d(G_{23})\geq 5\).

   solution ⇲ ⇱ solution

   >>> qorbites(23,2)
   [[0], [1, 2, 4, 8, 16, 9, 18, 13, 3, 6, 12], [5, 10, 20, 17, 11, 22, 21,
   19, 15, 7, 14]]
   

   On a deux diviseurs de degré 11 qui sont les facteurs de \(\Phi_{23}\), d’où l’existence de \(G_{23}\). Ces orbites contiennent une liste de 4 éléments consécutifs (respectivement 1-2-3-4 et 19-20-21-22), d’où une distance \(\geq 5\) d’après le lemme BCH.

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

   solution ⇲ ⇱ solution

   >>> 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.

3. Écrire une matrice génératrice \(G\) de \(G_{23}\), ainsi qu’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 ⇲ ⇱ solution

   >>> 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é.

   >>> 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()
   

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

   solution ⇲ ⇱ solution

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

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

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

7. 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, et son unicité à isomorphisme près.
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.