Codes correcteurs

Cours

• canal de transmission, erreurs, détection et correction

• espace de Hamming, code, erreurs détectables, corrigeables, distance minimale

• codes linéaires, poids, base et matrice génératrice, équations et matrice vérificatrice, code orthogonal

• distance minimale et matrice vérificatrice, syndrome

• bornes de Hamming et de Singleton, taux d’information et de correction

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

Exemples

1. Écrire une fonction VHamming(r) qui calcule une matrice vérificatrice du code de Hamming \([2^r-1,2^r-r-1,3]\) sur \(\F_2\).

   solution xcas ⇲ ⇱ solution xcas

   VHamming(r)=matrix(r,2^r-1,(k,l)->(bitand(l+1,2^k)?1:0));
   

On considère à présent le code de Hamming de paramètre \(r=3\).

1. On reçoit le mot (1,0,0,0,1,0,1). Quel était le mot envoyé, si l’on suppose qu’il y a au plus une erreur ?
2. On reçoit le mot (x,1,0,1,1,y,0), où x est y sont des bits illisibles mais les autres ont été transmis sans erreur. Quel était le mot envoyé ?

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 sage ⇲ ⇱ solution sage

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

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

Décodage

1. Calculer une matrice vérificatrice \(H\) de \(G_{23}\).
2. Combien y a-t-il de mots de poids \(<=3\) ? en faire la liste.
3. Calculer les syndromes correspondants \(y^tH\).
4. Ecrire un algorithme qui décode pour le code \(G_{23}\).

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.

Codes cycliques

1. Écrire une fonction qorbites(n,q) qui calcule la liste des \(q\)-orbites de \(\Z/n\Z\).

   solution sage ⇲ ⇱ solution sage

   def qorbites(n,q):
     d = {}
     res = []
     for i in xrange(n):
       if i in d: continue
       # start orbit
       orb = []
       while i not in d:
         d[i] = 1
         orb.append(i)
         i = (i*q)%n
       res.append(orb)
     return res
   

   solution xcas ⇲ ⇱ solution xcas

   qorbites(n,q) := {
     local zn, res, c, k, orbite, j;
   
     zn := [ seq(1,k=0..n-1) ];
     res := [];
     c := 0; k := 0;
     while(c<n) {
       while(!zn[k]) k++;
       orbite := [k];
       zn[k]:=0; c++;
       j:=irem(k*q, n);
       while(j != k) {
         orbite := append(orbite, j);
         zn[j]:=0; c++;
         j:=irem(k*q, n);
         print(orbite);
       }
       res := append(res, orbite);
       print(res);
     }
     return(res);
   }
   

2. Combien y a-t-il de codes binaires cycliques de longueur 15 ?

   solution sage ⇲ ⇱ solution sage

   >>> qorbites(15,2)
   [[0], [1, 2, 4, 8], [3, 6, 12, 9], [5, 10], [7, 14, 13, 11]]
   

   On a 5 orbites, donc 5 facteurs irréductibles de \(x^{15}-1\), donc \(2^5=32\) codes cycliques.

   solution xcas ⇲ ⇱ solution xcas

   qorbites(15,2) [[0], [1, 2, 4, 8], [3, 6, 12, 9], [5, 10], [7, 14, 13, 11]]

3. Les identifier en factorisant \(X^{15}-1\) sur \(\F_2\).

   solution ⇲ ⇱ solution

   On associe les facteurs aux orbites :

   • [0] correspond à Phi_1(X)=X-1 : c’est le générateur des codes pairs;
   • [5,10] correspond à Phi_3(X)=X^2+X+1 ;
   • [3,6,12,9] correspond à Phi_5(X) (en effet les éléments de l’orbite sont multiples de 3, donc les racines du polynôme sont des racines 5-ièmes de l’unité) ;
   • les deux orbites restantes sont les deux facteurs irréductibles de Phi_{15}(X) (la correspondance dépend du choix de racine 15-ème de l’unité utilisée).

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.

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.