Bornes, décodage¶
Bornes simples¶
On ne peut pas espérer construire des codes qui transmettent efficacement l’information tout en permettant de corriger un nombre arbitraire d’erreurs.
Les deux bornes élémentaires suivantes donnent des limites précises à ce qu’on peut espérer.
Borne de Singleton
Soit \(C\) un \([n,k,d]\)-code, alors \(d\leq n-k+1\).
Démonstration
Si l’on oublie \(d-1\) coordonnées, on obtient une projection de \(C\) sur \(\F_q^{n-d+1}\) qui est injective (sinon deux mots seraient à distance \(\leq d-1\)), donc la dimension de l’espace de départ vérifie \(k\leq n-d+1\).
On appelle
taux d’information le quotient \(\tau_I = k/n\) (proportion d’un mot codant effectivement l’information, le reste est de la redondance)
taux de correction le quotient \(\tau_C = d/n\).
L’inégalité de Singleton se lit
Par exemple, le code par triple répétition a un taux d’information \(\tau_I=3/6=0.5\), et un taux de correction \(\tau_C=0.5\).
Si vous suivez...
Les taux d’information et de correction du code de Hamming étendu [8,4,4] sont supérieurs à ceux du code de Hamming simple [7,4,3].
vrai
faux
faux, le taux de correction est supérieur, mais le taux d’information est inférieur. On ne gagne pas sur les deux tableaux.
Borne de Hamming
Si \(C\) est un \([n,k]\)-code \(t\)-correcteur sur \(\F_q\), on a
Démonstration
Si \(C\) est \(t\)-correcteur les boules centrées en chaque mot sont disjointes, on évalue leur cardinal.
Si vous suivez...
Combien y a-t-il de mots de longueur \(n\) et de poids 1 sur \(\F_2\) ? et sur \(\F_3\) ?
Définition
Soit \(C\) un \([n,k,d]\) code.
si \(C\) atteint l’égalité de Singleton \(d=n-k+1\), on dit que \(C\) est MDS (maximum distance separable).
si \(C\) atteint l’égalité de Hamming (où \(d=2t+1\)), on dit que \(C\) est (\(t\)-correcteur) parfait.
Si vous suivez...
Le code de Hamming \([7,4,3]\) est-il MDS ? parfait ?
Bons codes¶
Codes parfaits¶
On construira les codes de Hamming \(H_r(q)\), qui sont des \([q^r-1,q^r-r-1,3]\) codes pour \(r\geq2\). Ils ne sont pas MDS pour \(r>2\). En revanche, ils sont parfaits.
On construira aussi les codes de Golay \(G_{11}\), un \([11,6,5]\)-code sur \(\F_3\), et \(G_{23}\), un \([23,12,7]\)-code sur \(\F_2\). Ils sont parfaits, respectivement \(2\) et \(3\)-correcteurs (mais pas MDS).
Mais la recherche de codes parfaits s’avère peu fructueuse
Théorème (Van Lint)
Les seuls codes parfaits sont les codes de Hamming \(H_r(q)\) et les deux codes de Golay \(G_{11}\) et \(G_{23}\).
Codes MDS¶
De ce côté là, il y en a beaucoup.
Mentionnons la construction suivante (codes de Goppa) : on prend \(n\) éléments distincts \(a_1,\dots a_n\in\F_q\), et pour \(k<n\) on considère le morphisme d’évaluation
Il est injectif, et \(C=\im(\phi)\) est un \([n,k]\)-code.
En outre, un polynôme de degré \(<k\) a au plus \(k-1\) racines, donc les mots \(c\in C\) ont un poids \(w(c)\geq n-(k-1)=n-k+1\).
La borne de Singleton donne l’inégalité inverse, donc la distance est exactement \(n-k+1\) et \(C\) est un code MDS.
En pratique, on prend \(n=q\) (le plus grand possible).
Remarque
Si on prend \(n-1\) points les éléments de \(\F_q^\times\), on obtient les codes de Reed-Solomon, que l’on verra aussi comme codes cycliques.
Décodage des codes linéaires¶
Effacements¶
S’il n’y a pas eu d’erreur, et que \(C\) est un code de distance \(d\), on peut décoder un mot en oubliant \(d-1\) coordonnées, par inversion d’un mineur de la matrice génératrice (ils sont en effet tous inversibles tant qu’on sélectionne moins de \(d\) colonnes).
Erreurs: le syndrome¶
Si \(C\) est un \([n,k]\)-code linéaire de matrice vérificatrice \(V\), et si \(x\in\F_q^n\), on appelle syndrome de \(x\) le vecteur
où l’on note \(V_i\) la colonne \(i\) de \(V\).
Proposition
Le syndrome \(s(x)\) est nul si et seulement si \(x\in C\).
Soit \(C\) un \([n,k,d]\)-code, et \(c\in C\) un mot de code émis.
On note \(y=c+e\) le mot reçu, \(e\) étant l’erreur de transmission, que l’on suppose de poids \(w(e)=t<\tfrac d2\).
Proposition
On a \(s(y)=s(e)\), le syndrome ne dépend que de l’erreur.
En outre, \(s(e) = \sum e_i V_i\) est une combinaison de \(t\) colonnes de \(V\),
les indices des colonnes sont les indices des positions erronées
les coefficients des colonnes sont les coefficients du vecteur d’erreur \(e\).
Ainsi, le syndrome permet de retrouver l’erreur de transmission
Si vous suivez...
Soit un code ternaire de matrice vérificatrice
On reçoit le mot \((1,2,0,1,2,0)\). Quelle est l’erreur de transmission ?
(0,2,0,0,0,0)
(1,0,0,1,0,0)
(0,0,0,0,2,0)
on ne peut pas savoir
Remarque
Rappelons que la distance minimale \(d\) de \(C\) est le plus petit nombre de colonnes de \(V\) formant une famille liée. On ne peut avoir \(s(e)=s(e')\) pour \(e\neq e'\) de poids \(\leq t\) tant que \(2t< d\).
On retrouve le fait que \(C\) est \(t\)-correcteur.
Remarque
Toute famille de plus de \(n-k+1\) vecteurs étant liée dans \(\F_q^{n-k}\), on a \(d\leq n-k+1\), c’est la borne de Singleton.
Algorithme¶
Si \(C\) est \(t\)-correcteur, alors le syndrome est injectif sur la boule de rayon \(t\), \(B(0,t)=\set{e\in\F_q^n,w(e)\leq t}\).
Si l’on précalcule une table des syndromes \(s(e)\) pour tous les mots \(e\) de poids \(w(e)\leq t\), alors quel que soit le syndrome \(s(y)\), on trouve \(e\) de poids \(w(e)\leq t\) tel que \(s(y-e)=0 \Leftrightarrow y-e\in C\).
L’algorithme est le suivant
on calcule le syndrome \(s(y)\) ;
on détermine via la table l’erreur \(e\) telle que \(s(e)=s(y)\).
le mot corrigé est \(c=y-e\in C\).
Par rapport à un code quelconque, la linéarité a permis cette phase de précalcul des syndromes, au lieu de devoir parcourir une boule de rayon \(t\) pour chaque mot reçu.