Codes linéaires¶
Remarque
On peut se passer de linéarité pour beaucoup d’énoncés, mais tous nos codes seront linéaires.
Premiers exemples¶
code de parité (claviers) : soit \((x_1,\dots x_7)\in\F_2^7\), on ajoute un 8è bit de sorte que \(\sum x_i=0\). On peut détecter une erreur.
code par triple vérification : à \((x_1,x_2,x_3)\) on ajoute les bits \((x_2+x_3, x_1+x_3,x_1+x_2)\). On peut à présent corriger une erreur.
Si vous suivez...
On considère le code par triple vérification.
Si on reçoit le mot 101011, et que l’on sait
qu’il contient au plus un bit erroné, le mot correct
est ?
101101
100011
010101
001011
101 devrait être complété par 101,
donc il y a au moins une erreur. Une erreur
sur le 3è bit donne le mot 100011 qui convient.
Définition¶
On considère l’alphabet \(\F_q\), et on se place dans l’espace vectoriel \(\F_q^n\) des mots de longueur \(n\).
Définition
Un code linéaire \(C\) de longueur \(n\) est un sous-espace vectoriel de \(\F_q^n\). Si \(C\) est de dimension \(k\), on dit que \(C\) est un \([n,k]\)-code.
Exemple
le code \(C_1=\set{(x_1,\dots x_7,x_8),\sum x_i=0}\in\F_2^8\) est un \([8,7]\)-code.
le code \(C_2=\set{(x_1,x_2,x_3,x_2+x_3,x_1+x_3,x_1+x_2)}\in\F_2^6\) est un \([6,3]\)-code.
Si vous suivez...
Combien y a-t-il d’éléments dans le code \(C_2\) ?
6
64
16
8
Distance¶
Définition
Pour \(x,y\in\F_q^n\), on pose
le nombre de composantes par lesquelles \(x\) et \(y\) diffèrent. C’est une distance sur \(\F_q^n\), appelée distance de Hamming.
Si vous suivez...
Sur \(\F_2\), les octets 00100101 et 01000110 sont à
distance
2
3
4
5
4
On corrige au plus proche voisin pour la distance de Hamming.
Soit \(c\in C\) un mot de code transmis, et \(y\) le mot reçu. On note \(c'\in C\) le mot de code distinct de \(c\) le plus proche de \(y\). Alors
si \(d(c',y)>0\), on peut détecter l’erreur (il y a nécessairement eu une erreur puisqu’on n’obtient pas un mot de code)
si \(d(c',y)>d(c,y)\), la correction au plus proche est correcte (on retourne vers \(c\) et non pas vers un autre mot \(c'\)).
Si vous suivez...
On transmet un mot de code \(c\) dont le plus proche voisin est à distance \(8\). Quel est le nombre maximum d’erreurs que l’on est sûr de pouvoir corriger ?
7
4
3
2
3
Définition
On appelle distance minimale de \(C\) l’entier
Si vous suivez...
La distance minimale du code par triple vérification est
4
3
2
1
3. Cela découlera bientôt de la théorie générale. Notons simplement que si l’on change un des trois premier bits, on en change aussi deux des trois suivants (et réciproquement). Si l’on change deux des trois premiers, on en change un des trois suivants (et réciproquement). Ainsi, on change au moins 3 bits.
En particulier, on a le lien suivant entre distance minimale et capacité de correction.
Proposition
Si \(d(C)\geq t+1\), on peut détecter jusqu’à \(t\) erreurs
Si \(d(C)\geq 2t+1\), on peut corriger jusqu’à \(t\) erreurs.
Démonstration
Par inégalité triangulaire, \(d(c',y)\geq d(c,c')-d(c,y)\), or \(d(c,c')\geq d(C)\) et \(d(c,y)\leq t\).
Dans le premier cas on a bien \(d(c',y)\geq d(C)-t>0\).
Dans le second, \(d(c',y)-d(c,y)\geq d(C)-2t>0\).
Un code de longueur \(n\), dimension \(k\) et distance minimale \(d\) est appelé un \([n,k,d]\)-code.
Exemple
\(C_1\) est un \([8,7,2]\)-code.
\(C_2\) est un \([6,3,3]\)-code.
Poids¶
Pour \(x\in\F_q^n\), on définit le poids de \(x\)
alors pour tous \(x\neq y\) on a
En particulier, si \(C\) est un code linéaire, il est stable par différence donc
Si vous suivez...
Quel est le poids du mot 21012 de \(\F_5^5\) ?
4
6
1
2