Codes correcteurs

Cours

• 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, codes parfaits ; de Singleton, code MDS ; 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.

  Note

  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 \(α\) une racine nième de l’unité ; si \(g(x)\) s’annule en \(r\) puissances consécutives \(α^{i+1},\dots α^{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\)).

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

2. On pose V:=VHamming(4). Donner une matrice génératrice du code (utiliser xcas plutôt que la formule).

   solution xcas ⇲ ⇱ solution xcas

   Le code est le noyau de V. Comme xcas fonctionne en colonne, pas besoin de transposer V.

   V:=VHamming(4)
   G:=ker(V)
   (G%2)%0
   

3. Décoder le mot reçu y:=[1,1,0,1,0,0,1,0,0,0,0,1,0,0,1].

   solution xcas ⇲ ⇱ solution xcas

   On calcule le syndrome

   y:=[1,1,0,1,0,0,1,0,0,0,0,1,0,0,1]
   ((V*y)%2)%0
   

   Les bits forment le nombre 3, c’est la 3è colonne de la vérificatrice, il y a une erreur sur le 3e bit.

Code de Golay \(G_{23}\)

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

   solution xcas ⇲ ⇱ solution xcas

   qorbites(23,2)

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

   solution xcas ⇲ ⇱ solution xcas

   factor(x^23-1%2)

   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}\)

   solution xcas ⇲ ⇱ solution xcas

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

4. 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}\).

5. 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\)).

   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

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

   solution xcas ⇲ ⇱ solution xcas

   GE * transpose(GE)

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

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

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

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}\).

Codes cycliques

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

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

    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 :math:`x^{15}-1`,
   donc :math:`2^5=32` codes cycliques.
   

1. Essayer de rechercher de bons paramètres BCH pour des codes ternaires.

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.

   solution xcas ⇲ ⇱ solution xcas

   Comme on l’a fait pour construire les codes de Hamming binaires, il suffit de parcourir les entiers et de regarder leur décomposition binaire. On peut aussi procéder de manière récursive.

   Une fonction qui passe d’un entier \(k\) à son écriture binaire sur \(n\) bits. À la main

   bdigits(k,n):= {
     local L,j; L:=[];
     for(j:=0;j<n;j++) {
       L:=prepend(L,irem(k,2));
       k:=iquo(k,2);
       }
     L;
     }
   

   ou bien en cherchant dans l’aide xcas on trouve convert( ,base,2), on ruse juste un peu en ajoutant et retranchant \(2^n\) pour avoir le résultat sur \(n\) bits.

   bdigits(k,n):=convert(k+2^n,base,2)[1..n]
   

   bouclef2(n):={
     for(k:=0;k<2^n;k++) {
       m := bdigits(k,n);
       }
   }
   

   On peut encore procéder de manière récursive, mais je ne comprends rien au comportement d’xcas pour la concaténation de listes de listes, et c’est vite lourd en mémoire.

   vecteursf2(n):={
     if(n==0) return [[]];
     else {
       L := vecteursf2(n-1);
       return concat([apply(l->append(l,0),L)], [apply(l->append(l,1),L)])[0];
     }
   }
   

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.

   solution xcas ⇲ ⇱ solution xcas

   on écrit la distance de Hamming

   hamming(x,y) := sum(x[k]!=y[k],k,0,min(length(x),length(y))-1);
   

   et on écrit l’algorithme

   codeglouton(d,n) := {
     local C,c,nc,k,m;
     C := [ ]; nc := 0;
     for(k:=0;k<2^n;k++) {
       m := bdigits(k,n);
       for(c:=0;c<nc;c++) {
         if(hamming(m,c)<d) break;
         }
       if(c==nc) {
         C := append(C, m); nc++;
         }
       }
     C;
   }