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

  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 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^r)?1:0));
   

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

   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
   

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

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

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.

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.