- sympy - numpy - matplotlib

Les codes correcteurs d'erreurs

Lorsque les données transistent, celles-ci peuvent-être modifiées en subissant des perturbations. En effet, celles-ci sont transmises sous forme d'un signal (onde) qui, s'il rencontre des obstacles (murs, autre onde, ...), peut être altéré. C'est par exemple ce qu'il se passe lorsque l'on est au téléphone et que l'on entend des grésillements. Il est donc nécessaire de pouvoir détecter et corriger ces erreurs afin de retransmettre le signal original. C'est le rôle des codes correcteurs d'erreurs, et c'est grâce à eux que l'on peut tenir une conversation au téléphone sans entendre de grésillements.

Introduction : petit tour de magie

Pour illustrer comment fonctionne un code correcteur, faisons le petit jeu suivant : choisis un personnage parmi ceux qui se trouvent ci-dessous et réponds aux questions. Tu as le droit de mentir une fois, pas plus (cela introduira donc une erreur que l'on va corriger) !
Lorsque tu as terminé, clique sur le bouton "Fini!". Le programme te diras alors quel est ton personnage.

Jean
Jean
(0)
Martin
Martin
(1)
James
James
(2)
Alain
Alain
(3)
Thierry
Thierry
(4)
Pierre
Pierre
(5)
Paul
Paul
(6)
Jacques
Jacques
(7)
Baptiste
Baptiste
(8)
Lionel
Lionel
(9)
Jenny
Jenny
(10)
Rachel
Rachel
(11)
William
William
(12)
Romain
Romain
(13)
Marvin
Marvin
(14)
Sébastien
Sébastien
(15)










Ton personnage est :

...




Explication

Le but est de retrouver un personnage parmi les $16 = 2^4$. Si on les numérote, cela revient à retrouver un nombre entre 0 et 15...

Notons $n$ ce nombre à trouver. En base 2, il s'écrit : $n = a_3a_2a_1a_0$, avec les $a_i \in \{0, 1\}.$

    Il y a donc 4 "digits" à trouver et seulement 4 questions suffisent si on n'a pas menti (si l'on répond "oui", alors on sait que le digit correspondant vaut 1, 0 sinon) :
  • La première sert à trouver $a_0$ et revient à demander si $n$ est impair (tous les nombres impairs ont des lunettes, les autres non)
  • La seconde sert à trouver $a_1$ et revient à demander si $n$ est congru à 2 ou 3 modulo 4 (2, 3, 6, 7, 10, 11, 14 et 15 : tous ces nombres ont une chemise, les autres non)
  • La troisième sert à trouver $a_2$ et revient à demander si $n$ est congru à 4, 5, 6 ou 7 modulo 8 (4, 5, 6, 7, 12, 13, 14 et 15 : tous ces nombres ont une moustache, les autres non)
  • La quatrième sert à trouver $a_3$ et revient à demander si $n$ est supérieur ou égal à 8 (tous ces nombres ont des cheveux, les autres non)

Les autres questions servent à détecter la présence d'une éventuelle erreur.
    Pour celà, on rajoute 3 caractérisques que l'on répartit sur les personnages de sorte que le nombre minimal de différences entre 2 personnages différents soit 3.
    Ainsi, lorsqu'on ment une fois, on crée un personnage fictif qui :
  • est à une distance de 1 du personnage que l'on a choisi,
  • est à une distance au moins 2 de tous les autres,
    • où la distance désigne ici le nombre de caractérisques qui diffèrent.
  • Il suffit donc de trouver le personnage le plus proche du personnage fictif que l'on a crée.
    En revanche, si on ment 2 fois, on crée un personnage fictif qui :
  • est à une distance de 2 du personnage que l'on a choisi,
  • est à une distance de 1 d'un autre personnage.
  • On ne peut donc pas retrouver le personnage que l'on a choisi au départ si on ment 2 fois, mais on sait que l'on a menti.

Le fait de rajouter de l'information et de les répartir pour que chacun des "mots du code" (ici les personnages) soient à une distance minimale fixée (aient un nombre mininal de différences fixé) est typique des codes correcteurs d'erreurs. Le code décrit plus haut s'appelle le code de Hamming. Il a une distance minimale de 3, il peut donc détecter 2 erreurs (mensonges : c'est à dire que l'on peut savoir si l'on a menti une ou deux fois), et peut en corriger une seule (on ne retrouve le personnage d'origine que si l'on ment une fois, pas plus).



Et les maths dans tout ça ?

Avant d'expliquer concrètement comment fonctionne le code de Hamming, remarquons que si l'on ne ment pas, on cherche à trouver un nombre $n = a_3a_2a_1a_0$ en base 2, c'est à dire un vecteur $(a_0, a_1, a_2, a_3) \in GF(2)^4$, où $GF(2)$ désigne le corps à 2 éléments, c'est à dire ${\mathbb{Z}/{2\mathbb{Z}}}$, ou encore plus simplement, l'ensemble $\{0, 1\}.$
On souhaite donc, au départ, envoyer à notre interlocuteur un message $v$ qui est en fait un vecteur $(a_0, a_1, a_2, a_3) \in GF(2)^4$. Pour pouvoir corriger les éventuelles erreurs, on va donc rajouter de la redondance et envoyer un mot de code $m$ obtenu à partir de $v$. $m$ est en fait un vecteur $GF(2)^7$. Avant d'aller plus loin, donnons quelques définitions.

    Un code (noté $C$) est un sous ensemble de $GF(2)^n$ de même cardinal que $GF(2)^k$ (c'est à dire $2^k$). Ainsi, il existe une bijection $f : GF(2)^k \rightarrow C$ qui à un message $v$, associe le mot de code correspondant $m$.
    On appelle :
  • message : le vecteur $v$ de $GF(2)^k$ que l'on veut envoyer. Ici, $k = 4$ et un message est un personnage qui a 4 caractéristiques (celles correspondant aux 4 premières questions).
  • mot du code : le vecteur $m$ de $GF(2)^n$ que l'on envoie. Ici, $n = 7$ et un mot du code est un personnage à 7 caractéristiques.
  • mot : un vecteur $u$ de $GF(2)^n$.
    • L'entier $k$ est appelé la dimension du code et $n$ sa longueur.

Avec ces définitions, on envoie un mot de code $m$ et notre interlocuteur reçoit un mot $m'$. Celui-ci peut avoir subi des perturbations et contenir des erreurs. Le but pour le destinataire est donc de retrouver à partir du mot $m'$ reçu, le mot de code $m$ que l'on a voulu envoyer, et donc le message d'origine $v$ que l'on a voulu envoyer (lorsque l'on a $m$ c'est facile car $v = f^{-1}(m)$).
    Il y a donc un double enjeu ici :
  • comment corriger les erreurs c'est à dire comment retrouver le mot de code $m$ à partir du mot $m'$ reçu ?
  • comment générer les mots de code pour qu'ils permettent de facilement corriger les erreurs ? Autrement dit, comment trouver $f$ ?
    On appelle :
  • distance de Hamming : l'application $w : GF(2)^n \times GF(2)^n \rightarrow GF(2)^n$, qui à tout couple de vecteurs $(u, u')$, associe le nombre de coordonnées deux à deux distinctes de $u$ et $u'$. Plus formellement, $w(u, u') = {Card} \{ 1 \leqslant j \leqslant n \;|\; u_j \neq u_j' \}.
  • distance minimale du code $C$ (notée $d$): la plus petite distance de Hamming entre deux éléments distincts de $C$.
Dans l'exemple ci-dessus, $k=4$, $n=7$ et $d = 3$.
    On remarque qu'un code $C$ de distance minimale $d$ peut détecter $d-1$ erreurs (mensonges) et corriger au plus $\frac{d-1}{2}$ erreurs.

Comment générer le code de Hamming ?

    Un code $C$ est dit linéaire si c'est un sous-espace vectoriel de $GF(2)^n$. L'application $f$ décrite plus haut est donc une application linéaire bijective et on peut trouver une base $(e_1, ..., e_k)$ du $GF(2)^n$-espace vectoriel $C$ en prenant les images par $f$ des vecteurs de la base canonique de $GF(2)^k$.
    La matrice $G = (e_1, ..., e_k)$ s'appelle la matrice génératrice de code $C$.
    Si $d$ est la distance minimale d'un code linéaire $C$, on dit que c'est un code de type $(n, k, d)$.
Le code de Hamming $C$ décrit plus haut est un $(7, 4, 3)$-code linéraire généré par la matrice :
$G = \left( \begin{array}{c c c c} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0\\ 0 & 1 & 1 & 1\\ 1 & 1 & 0 & 1\\ \end{array} \right)$

Cette matrice nous permet donc de répartir les 3 dernières caractérisques de façon à ce que les personnages soient à une distance au moins 3.
Par exemple, supposons que l'on veuille envoyer le numéro 10 (qui s'écrit 1010 en base 2), c'est à dire que l'on veuille au départ envoyer le vecteur $v = (0, 1, 0, 1)$.
Alors, le mot de code $m$ correspondant que l'on va devoir envoyer est $ G \cdot v = G \cdot \left( \begin{array}{c} 0 \\ 1 \\ 0 \\ 1 \\ \end{array} \right) = \left( \begin{array}{c} 0 \\ 1 \\ 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ \end{array} \right) $ (on voit des 0 apparaître car tous les calculs sont fait modulo 2),
c'est pourquoi on a bien rajouté des yeux bleux, mais pas de barbe ni de "dents" à Jenny.

Comment détecter les erreurs ?

On va construire une application linéaire $s$ sur $GF(2)^n$, que l'on appelle syndrôme, dont le code $C$ est le noyau. Pour ce faire, nous utilisons la matrice géneratrice $G$ du code $C$, et il suffit de résoudre le système linéaire $HG = 0$, où $H$ désigne la matrice de l'application $s$ dans la base canonique de $GF(2)^n$ (les inconnues étant les coefficients de $H$). Ainsi, on aura que $m$ est un mot du code $C$ si et seulement si le produit $H \cdot m = 0$, ce qui nous permettra de détecter les erreurs. $H$ est appellée la matrice de parité ou encore matrice de contrôle du code $C$.
Une autre façon de voir $H$ est de considérer $C^{\bot}$ l'orthogonal de C par la forme bilinéaire symétrique non dégénérée définie par :
$< u, u'> = \sum_{j = 1}^{n}{m_j \cdot m_j'}$.
En notant $(H_1, ... H_{n-k})$ une base de $C^{\bot}$, alors $H$ est donnée par
$H = \left( \begin{array}{c} {}^{t}H_1 \\ \cdot \\ \cdot \\ {}^{t}H_{n-k}\\ \end{array} \right)$

Pour revenir au code de Hamming, en résolvant le système $HG = 0$ (calcul du noyau), on obtient la matrice de contrôle suivante :
$H = \left(\begin{array}{ccccccc} 1 & 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 1 & 1 & 1 & 0 & 1 & 0\\ 1 & 1 & 0 & 1 & 0 & 0 & 1\\ \end{array}\right).$
    Soit $u$ le mot reçu. On calcule son syndrôme $s(u) = Hu$ et on a deux cas :
  • $s(u) = 0$ : le mot $u$ est un mot du code et il n'y a pas d'erreur donc $m = u$
  • $s(u) \neq 0$ : le mot $u$ a été perturbé et on peut retrouver le mot de code de départ $m$ seulement s'il a subi moins de $t = \frac{d-1}{2}$ erreurs (c'est à dire si $w(u, m) \leqslant t$). En notant $e$ cette erreur, on a $u = m + e$ et, par linéarité de $s$, on a que $s(u) = s(m) + s(e) = s(e) = \sum_{j = 1}^{n}{e_j h_j}$, où $h_j$ désigne le $j$-ième vecteur colonne de $H$. On retrouve donc facilement $e$ et donc $m = v - e$.
Par exemple, supposons que l'on reçoive le mot $u = \left( \begin{array}{c} 1 \\ 1 \\ 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ \end{array} \right), $ alors le syndôme $s(u)$ vaut $H\cdot u = \left( \begin{array}{c} 1 \\0 \\1 \\ \end{array} \right), $ et c'est exactement la première colonne de $H$, c'est à dire qu'une erreur est apparue en position 1 et donc que le mot de code envoyé était le vecteur $m = {}^t \left( \begin{array}{ccccccc} 0 && 1 && 0 && 1 && 1 && 0 && 0 \\ \end{array} \right), $ et qui correspond au personnage de Jenny (numéro 10).

Trouver $f$ (ou $G$) : de la magie ?

Je ne vous ai pas dit comment a été construite la matrice génératrice $G$ du code de Hamming. En fait, il existe plusieurs moyens de construire des codes linéaires et nous ne les présenterons pas ici.
Pour les plus curieux d'entre vous, vous pourrez vous intéresser aux codes linéaires cycliques de longueur $n$ et à la façon de générer de tels codes. Un thérorème explique qu'un code cyclique linéaire est généré par un polynome unitaire divisant $X^n -1$ dans $GF(2)[X]$.
Dans notre cas, $n=7$ et $X^7-1 = (X+1)(X^3 + X + 1)(X^3 + X^2+1)$ et, le code de Hamming est généré par le polynôme $g(X) = X^3 + X + 1$, ce qui donne la matrice génératrice :
$G' = \left( \begin{array}{c c c c} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0\\ \end{array} \right)$
En réordonnant les vecteurs de base, nous obtenons la matrice $G$ décrite plus haut.

import sympy as sp G = sp.Matrix([[1, 0, 0, 0, 1, 0, 1], [0, 1, 0, 0, 1, 1, 1], [0, 0, 1, 0, 1, 1, 0], [0, 0, 0, 1, 0, 1, 1],]) def matrice_controle(G): res = [] for i in G.nullspace(): res.append(list(i % 2)) return sp.Matrix(res) H = matrice_controle(G) names = ["Jean", "Martin", "James", "Alain", "Thierry", "Pierre", "Paul", "Jacques", "Baptiste", "Lionel", "Jenny", "Rachel", "William", "Romain", "Marvin", "Sébastien"] ques = ["A-t-il des lunettes ?", "A-t-il une chemise ?", "A-t-il une moustache ?", "A-t-il des cheveux ?", \ "A-t-il yeux bleus ?", "A-t-il une barbe ?", "Voit-on ses dents ?",] def trouve_col(H, err): col = 0 while col < 7: lcol = list(H[:, col]) if list(err) == lcol: return col col += 1 def decode(G, H, v): erreur = list((H * sp.Matrix(v)) % 2) res = [v[k] for k in range(7)] if erreur == [0, 0, 0]: return 0, res, res[0] + res[1] * 2 + res[2] * 4 + res[3] * 8 + 1 col = trouve_col(H, erreur) res[col] = (res[col] + 1) % 2 return col + 1, res, res[0] + res[1] * 2 + res[2] * 4 + res[3] * 8 + 1 def values(event): questions = ["glasses", "chemise", "moustache", "hair", "blue", "barbe", "dents"] vecteur = [0, 0, 0, 0, 0, 0, 0] for k in range(7): vecteur[k] = int(Element(questions[k]).element.value); col, res, num = decode(G, H, vecteur) reponse = f"{names[num-1]} !" pyscript.write('content', reponse) exp = "" if col == 0: exp += "Tu n'as pas menti ou alors tu as menti au moins trois fois..." else: exp += f"Tu as menti à la question : {ques[col - 1]} ou alors tu as au moins deux fois et je ne peux pas retrouver ton personnage." pyscript.write('content2', exp)