Référence: Wikipedia: Codes correcteurs
Ce document dans d'autres formats: feuille de travail, source RST.
Un expéditeur $A$ transmet un message $m$ à $B$ sur un canal bruité.
Problématique
note
Contrairement à la cryptographie, la problématique n'est pas de se protéger d'un tiers malicieux, mais d'un bruit aléatoire.
Quelles sont les contraintes spécifiques à chacune de ces applications?
Syntaxe: orthographe, grammaire
Anglais: $500000$ mots de longueur moyenne $10$ sur en gros $26^{10}$, soit une proportion de $10^{-9}$.
Exemple: pomme, abrucot, poime (pomme, poire, prime, poème)
Sémantique: sens, contexte, ...
Définitions
Un code $C$ est un sous-ensemble de mots dans $M:=A^{n}$, où
> Typiquement $q=2$ (codes binaires).
Codage: on transforme le message envoyé $m$ en un mot $c$ du code.
Transmission: en passant à travers le canal, $c$ devient $c'$.
Détection d'erreur: on essaye de déterminer si $c=c'$.
Correction d'erreur: on essaye de retrouver $c$ à partir de $c'$.
Décodage: on retrouve le message $m$ à partir de $c$.
Définition
Distance de Hamming entre deux mots: nombre de lettres qui diffèrent.
Stratégie:
Est-ce raisonnable?
Définitions
Formellement:
$$D(C) := \max_{k\in \NN} \quad \forall x\in C \quad \forall y \quad d(x,y)\leq k \Longrightarrow y\not\in C$$$$e(C) := \max_{k\in \NN} \quad \forall x\in C \quad \forall y \quad d(x,y)\leq k \Longrightarrow d(z,y)>k, \forall z\in C, z\ne x$$$$d(C) := \min_{x\ne y\in C} d(x,y)$$
Variante: borner ces quantités par la longueur $n$.
Exercice: En petite dimension:
Proposition
Capacité de détection: $D(C) = d(C) - 1$.
Capacité de correction: $e(C) = \llcorner\frac{d(C)-1}2\lrcorner$.
Problème
Redondance minimale pour une capacité de correction donnée?
Étant donnés un alphabet $A$ avec $q=|A|$, une longueur $n$ et une capacité de correction $e$, trouver un code $C$ ayant le plus grand nombre possible de mots.
Exemples: visualisation des boules de rayon $e$ autour de quelques codes binaires
Chargement de quelques fonctions, et configuration des plots 3D:
%run "codes_correcteurs.py"
from sage.plot.plot3d.base import SHOW_DEFAULTS
SHOW_DEFAULTS['frame'] = False
SHOW_DEFAULTS['aspect_ratio'] = [1,1,1]
Le code de triple répétition sur $\ZZ/2\ZZ$ :
K = GF(2)
V = K^3
C = V.subspace([[1,1,1]])
dessin_boules(C,1)
mais pas sur $\ZZ/3\ZZ$ :
K = GF(3)
V = K^3
C = V.subspace([[1,1,1]])
dessin_boules(C,1)
Le code de Hamming:
V = K^7
C = codes.HammingCode(3, GF(2))
dessin_boules(C, 1, projection=projection_7_3)
Exercice: Borne de Hamming sur $|C|$.
Nombre de points dans une boule $B(x,e):=\{y,d(x,y)\leq e\}$ de $A^{n}$ de centre $x$ et de rayon $e$?
Taille de $A^n$?
Conclusion?
Application numérique: $n=6,q=2,d=3$ : $|C|\leq?$.
Définition: code parfait
Un code $C$ est parfait si $|C| |B(x,e)| = |A^n|$, i.e.
$$|C| \sum_{k=0}^e \binom n k (q-1)^k = q^n$$Exemple
Le premier et le troisième code ci-dessus sont parfaits, mais pas le deuxième.
Problème
Codage? Décodage?
Principe: on rajoute de la structure pour rendre les algorithmes plus efficaces.
Définition
Un code linéaire est un sous-espace vectoriel de $A^n$, où $A$ est un corps fini.
Commençons par un petit échauffement.
Exercice: algèbre linéaire sur $\mathbb{Z}/2\mathbb{Z}$, à la main
Soit $H$ la matrice:
A = GF(2); A
H = matrix(A, [[0,1,1,1, 1,0,0],
[1,0,1,1, 0,1,0],
[1,1,0,1, 0,0,1]]); H
Calculer le noyau de $H$.
Est-ce que les vecteurs $(1,1,0,0,1,1,0)$ et $(1,0,1,1,1,0,1)$ sont dans le sous-espace vectoriel engendré par les lignes de $H$?
Conclusion?
Exemple: bit de parité
Sept bits plus un huitième bit dit de parité tel que le nombre total de bit à $1$ est pair.
Exemple: code de Hamming $H(7,4)$.
Quatre bits $\left(a_{1},a_{2},a_{3},a_{4}\right)$ plus trois bits de redondance $\left(a_{5},a_{6},a_{7}\right)$ définis par:
$$a_{5} = a_{2}+a_{3}+a_{4}\\ a_{6} = a_{1}+a_{3}+a_{4}\\ a_{7} = a_{1}+a_{2}+a_{4}$$Comment tester si un mot appartient au code?
Avec Sage:
A = GF(2); A
n = 7
V = A^7; V
Matrice de contrôle:
H = matrix(A, [[0,1,1,1, 1,0,0],
[1,0,1,1, 0,1,0],
[1,1,0,1, 0,0,1]])
Test d’appartenance au code:
mot_du_code = V([1,0,1,1,0,1,0]);
H * mot_du_code
mot_quelconque = V([1,1,0,1,0,1,1]);
H * mot_quelconque
Refaites le à la main!
Le code lui-même est le noyau de $H$ :
C = H.right_kernel()
mot_du_code in C
mot_quelconque in C
Refaites le à la main!
Est-ce que l'on pourrait trouver $C$ encore plus rapidement?
Oui:
MatrixSpace(A,4,4)(1).augment(H[:,0:4].transpose())
Combien y-a-t’il de mots dans le code de Hamming $H(4,3)$?
Calculer la distance de ce code (indice: se ramener en zéro!)
Quelle est sa capacité de detection? de correction? Est-il parfait?
Correction:
sage: C.cardinality()
def poids(c): return len([i for i in c if i])
poids(V([0,1,0,0,0,0,0]))
poids(V([1,0,1,1,0,1,0]))
min(poids(m) for m in C if m)
Comment coder un mot?
Matrice génératrice:
G = C.matrix(); G
M = A^4
m = M([1,0,1,0])
c = m * G; c
Partir du mot zéro, le coder, et faire alternativement une erreur sur chacun des bits. Noter le résultat après multiplication par la matrice de contrôle.
Prendre un mot à 4 bits de votre choix, le coder, faire une erreur sur un des 7 bits, corriger et décoder. Vérifier le résultat.
Que se passe-t’il s’il y a deux erreurs?
Principe: encore plus de structure pour être encore plus efficace.
Donnons une structure d'anneau quotient à $A^n$ en l'identifiant avec $A[X]/(X^n-1)$.
Définition
Un code est cyclique s'il est stable par rotation des mots.
Remarque
Dans $A[X]/(X^n-1)$, décalage = multiplication par $x$.
Code cyclique = idéal dans $A[X]/(X^n-1)$.
Soit $g$ un diviseur de $X^n-1$, et $h$ tel que $gh=X^n-1$.
Code: idéal engendré par $g$
Codage: $m\mapsto mg$
Détection d'erreur: $c*h=0$
Décodage: division par $g$ modulo $X^n-1$ (par ex. par Euclide étendu)
Codes BCH
On peut construire des codes cycliques de capacité de correction déterminée à l'avance. Pour en savoir plus, voir Wikipedia, Codes BCH.
Exercice (secret partagé)
Un vieux pirate est sur son lit de mort. Dans sa jeunesse il a enfoui un Fabuleux Trésor dans la lagune de l'Ile de la Tortue, quelque part à l'est du Grand Cocotier. Il a réuni ses dix lieutenants préférés pour leur transmettre l'information secrète indispensable: la distance entre le Grand Cocotier et le Trésor. Connaissant bien ses lieutenants, et dans un étonnant dernier sursaut de justice, il ne voudrait pas qu'une conjuration de quelques uns d'entre eux assassine les autres pour empocher seuls le trésor. En tenant cependant compte de la mortalité habituelle du milieu, il souhaite donner une information secrète à chacun de ses lieutenants pour que huit quelconques d'entre eux puissent retrouver ensemble le trésor, mais pas moins. Comment peut-il s'y prendre?
Application au codage: CIRC
Découpage de l'information en blocs, interprétés comme des polynômes $P_1,\dots,P_k$ dans $\GF(q)[X]$.
Points d'évaluation $x_1,\ldots,x_l$.
Premier étage: évaluation et entrelacement.
$$\underbrace{P_1(x_1),P_2(x_1),\ldots,P_k(x_1)}, \underbrace{P_1(x_2),P_2(x_2),\ldots,P_k(x_2)},\ldots \underbrace{P_1(x_l),P_2(x_l),\ldots,P_k(x_l)}$$Deuxième étage: codage de chacun des $l$ blocs avec un code permettant de détecter les erreurs.
Comme d'habitude, choisir à la carte parmi les exercices suivants.
Exercice: théorie des codes et Sage
Explorer les fonctionalités de Sage autour du codage. Un point d'entrée est codes?
ainsi que le tutoriel thématique Coding Theory in Sage.
Exercice: illustrer un cours sur le codage
Mettre au point une illustration sur ordinateur de quelques points du cours. On pourra par exemple:
Pour ces deux derniers points, on pourra considérer des codes:
Exercice: codes cycliques
On oubliera ici que les codes cycliques sont naturellement représentés par des idéaux dans $\ZZ_2[X] / X^n-1$, et on ne fera que de l'algèbre linéaire.
Soit $E$ un espace vectoriel sur un corps fini; typiquement:
F2 = GF(2)
E = F2^7; E
On considère l'opération cycle(v)
qui prend un vecteur et décale ses coordonnées d'un cran vers la droite (modulo $n$). On rappelle qu'un code cyclique est un sous-espace vectoriel de $E$ qui est stable par l'opération cycle
.
cycle
.code_cyclique(v)
qui renvoie une base du plus petit code cyclique $C$ contenant $v$.Exercice: Le tour de magie
Implanter le tour de prestidigitation du texte Codes Correcteurs d'Erreurs, Agreg 2005
Un petit exemple d'utilisation des composants visuels interactifs de Sage. Ils ne fonctionne pas encore dans les feuilles de travail Jupyter:
@interact
def magie(step=slider([1..5])):
return matrix(4,4,[i for i in srange(0,32) if i.digits(base=2,padto=6)[5-step]])