Codes correcteurs d’erreurs

algebra

Petite fiche résumant ce qu’il faut savoir sur les codes correcteurs d’erreurs pour l’agrégation.

Pour tout le document, on fixe $p$ un nombre premier, $k$ et $n$ deux entiers non nuls et $q = p^{k}$ .

Théorie générale

Il s’agit, dans un premier temps, de choisir le corps $F_{q}$ en fonction de l’information que l’on cherche à coder. Par exemple, le choix de $F_{2}$ semble le plus naturel pour représenter la manière dont est stockée l’information dans un ordinateur, tandis que $F_{4}$ serait plus approprié vis-à-vis de l’ADN.

Définition 1. On appelle mot un vecteur à coefficients dans $F_{q}$ .

Après avoir choisi $F_{q}$ comme alphabet, il reste à choisir l’ensemble des mots $C$ du code. Plus précisément :

Définition 2. On appelle code correcteur (ou simplement code) de taille $n$ un sous-ensemble de $F_{q}^{n}$ .

Remarque 3. Le code correcteur $C$ est l’ensemble des mots que l’on est en mesure de produire par codage : il ne peut pas occuper l’espace $F_{q}^{n}$ entier, sinon tous les mots seraient valides !

Si l’on reçoit un mot qui n’est pas dans le code, on est donc sûr qu’il y a eu une erreur de transmission. L’opération de codage ajoute une information pour distinguer les mots valides des autres. C’est uniquement lors du décodage que l’on va pouvoir réparer une ou plusieurs erreurs. Le procédé général étant le suivant :

on transforme un message $m$ en un mot $c$ du code (c’est le processus de codage) ;
pendant la transmission, $c$ est altéré en $c^{'}$ (c’est le processus de transmission) ;
on essaye de déterminer si $c^{'}$ est un mot du code (c’est le processus de détection d’erreur) ;
on essaye de retrouver $c$ à partir de $c^{'}$ (c’est le processus de correction d’erreur) ;
on retrouve le message $m$ à partir de $c$ (c’est le processus de décodage).

Exemple 4 (Bit de parité). Dans un ordinateur, chaque mot est coupé en sous-mots de $7$ bits, c’est-à-dire, en vecteurs formés de $7$ éléments de $F_{2}$ . Lors du codage de chaque vecteur, on ajoute un bit dit de parité.

Ainsi, soit $b_{1}, \dots, b_{7}$ une suite de $7$ bits. On calcule : $b_{8} = b_{1} + \dots + b_{7} mod 2$ Si le nombre de bits égaux à $1$ est pair, $b_{8} = 0$ , sinon, $b_{8} = 1$ . Ainsi, le mot $(b_{1}, \dots, b_{8})$ a toujours un nombre de bits égaux à $1$ qui est pair. On peut alors détecter, à la lecteur d’un mot, si une erreur a eu lieu lors de sa réception : il y aura un nombre impair de bits égaux à $1$ .

Dans le cadre d’un mot de taille $2$ , on peut représenter la situation par un cube. Sur cette illustration, nous voyons en turquoise l’ensemble des mots $C$ du code. Une unique erreur correspond à un déplacement sur le cube le long d’une arête. Dans ce cas, le récepteur reçoit un point noir dont la somme de toutes les lettres est un entier impair. En revanche, un tel point est toujours à proximité de trois points turquoise, le récepteur ne dispose donc d’aucun moyen pour une correction automatique.

tikzpicture-1 — Mots de $F_{2}$ de longueur $2$ avec un bit de parité.

Ainsi, ce code, a deux inconvénients :

il est impossible de détecter où l’erreur a eu lieu, et donc, de la corriger ;
si deux erreurs ont lieu, il est impossible de les détecter (car alors, le nombre de bits égaux à $1$ reste pair).

L’exemple précédent montre bien qu’il est nécessaire de pouvoir évaluer les propriétés qualitatives d’un code. Ainsi :

Définition 5. Soient $x$ et $y$ deux mots de $F_{q}$ de taille $n$ .

Le poids de $x$ , noté $ω (x)$ , est le nombre de coefficients non nuls dans $x$ .
La distance de Hamming entre $x$ et $y$ , notée $d_{H} (x, y)$ est définie par $d_{H} (x, y) = ω (x - y)$

Proposition 6.

$d_{H}$ correspond aux nombres de coefficients qui diffèrent entre $x$ et $y$ .
$d_{H}$ est une distance sur $F_{q}^{n}$ .

Démonstration.

Soient $x, y \in F_{q}^{n}$ . Par définition, $ω (x - y)$ est égal au nombre de coefficients non nuls de $x - y$ , soit au nombre de coefficients qui diffèrent entre $x$ et $y$ .
Soient $x, y, z \in F_{q}^{n}$ .
1. On a $d_{H} (x, y) \geq 0$ par positivité de $ω$ et $d_{H} (x, y) = 0$ si et seulement s’il y a $0$ coefficients qui diffèrent entre $x$ et $y$ ie. $x = y$ .
2. Le nombre de coefficients non nuls de $x - y$ est égal au nombre de coefficients non nuls de $y - x$ . Donc, $d_{H} (x, y) = ω (x - y) = ω (y - x) = d_{H} (y, x)$
3. On note $(x_{i})_{i \in [[1, n]]}$ , $(y_{i})_{i \in [[1, n]]}$ et $(z_{i})_{i \in [[1, n]]}$ les coefficients respectifs de $x$ , $y$ et $z$ . Soient $A = {k \in [[1, n]] ∣ x_{k} = y_{k}}$ , $B = {k \in [[1, n]] ∣ y_{k} = z_{k}}$ et $C = {k \in [[1, n]] ∣ x_{k} = z_{k}}$ . On a, $(A \cap B) \subseteq C$ En passant au complémentaire, $(^{c} C \subseteq (^{c} (A \cap B) = (^{c} A \cup (^{c} B$ D’où, $∣ (^{c} C ∣ d (x, z) \leq ∣ (^{c} A ∣ d (x, y) + ∣ (^{c} B ∣ d (y, z)$

◻

La distance $d_{H}$ permet de quantifier la notion de mot le plus proche. Avec elle, on peut donner la définition suivante.

Définition 7. Soit $C$ un code. On appelle distance minimale de $C$ , l’entier suivant : $x, y \in C min {d_{H} (x, y) ∣ x \neq = y}$

Plus la distance minimale d’un code est grande, plus les mots vont être espacés les uns des autres. En ne prenant en compte que la plus petite des distances, on va pouvoir s’assurer que le code est en mesure de corriger une erreur sous certaines conditions.

Définition 8. Un code $C$ est dit $t$ -correcteur s’il peut corriger au maximum $t$ erreurs.

Remarque 9. Cela signifie que, si $x \in C$ désigne un mot codé et $x^{'} \in F_{q}^{n}$ le mot réceptionné, alors on est en mesure de retrouver le mot $x$ original si $d (x, x^{'}) \leq t$ .

Proposition 10. Soit $C$ un code de distance minimale $d$ . On suppose $d \geq 2 t + 1$ . Alors, $C$ est $t$ -correcteur.

Démonstration. Soient $x, y \in C$ deux mots distincts du code. Alors, $d_{H} (x, y) \geq 2 t + 1$ les boules $B (x, t)$ et $B (y, t)$ sont disjointes. Ainsi, soient $a \in C$ un mot codé émis et $a^{'} \in F_{q}^{n}$ le mot réceptionné. Si $d (a, a^{'}) \leq t$ , alors $a^{'} \in B (a, t)$ et n’appartient pas à une autre boule de centre un mot du code et de rayon inférieur ou égal à $t$ : on peut corriger $a^{'}$ . ◻

Remarque 11. Notons qu’alors $t \leq \frac{d - 1}{2} ⟹ t = ⌊ \frac{d - 1}{2} ⌋$

Codes linéaires

Nous allons maintenant observer ce qui se passe en imposant une structure sur le code.

Définition 12. Un code linéaire $C$ de taille $n$ et de dimension $m$ sur $F_{q}$ est un sous-espace vectoriel de dimension $m$ de $F_{q}^{n}$ .

Soit alors une base de $C$ . On considère $G$ une matrice dont les colonnes sont les vecteurs de cette base. On dit que $G$ est une matrice génératrice de $C$ .

Proposition 13. Soit $C$ un code linéaire de taille $n$ et de dimension $m$ sur $F_{q}$ . Soit $G$ une matrice génératrice de $C$ . On a, $C = {G x ∣ x \in F_{q}^{n}}$

Démonstration. Soit $(v_{1}, \dots, v_{m})$ une base de $C$ . On considère la matrice génératrice de $C$ associée, que l’on note $G$ .

Alors, $\forall i \in [[1, m]]$ , en notant $e_{i}$ le $i$ -ième vecteur de la base canonique de $F_{q}^{n}$ , on a $M e_{i} = v_{i}$ . Donc, par linéarité, ${G x ∣ x \in F_{q}^{n}} \subseteq C$ . Et comme $v_{i} = M e_{i}$ , on a bien l’inclusion réciproque. ◻

Remarque 14. Dans le cadre d’un code linéaire $C$ , la distance minimale $d$ s’exprime alors $d = x, y \in C min {d_{H} (x, y) ∣ x \neq = y} = x \in C min {ω (x) ∣ x \neq = 0}$

Proposition 15. Soit $C$ un code linéaire de taille $n$ et de dimension $m$ sur $F_{q}$ . Il existe une matrice $H \in M_{n - m, n} (F_{q})$ telle que $\forall x \in F_{q}^{n}, x \in C ⟺ H x = 0$

Démonstration. On considère le produit scalaire canonique sur $F_{q}^{n}$ : $⟨ ., . ⟩ : ((x_{1}, \dots, x_{n}), (y_{1}, \dots, y_{n})) \mapsto i = 1 \sum n x_{i} y_{i}$ et $C^{⊥}$ l’orthogonal de $C$ pour ce produit scalaire. $C^{⊥}$ est un sous-espace vectoriel de $F_{q}^{n}$ de dimension $n - m$ , dont on note $(v_{1}, \dots, v_{n - m})$ une base. Définissons $H$ comme étant la matrice dont la $i$ -ième ligne est $v_{i}$ pour tout $i \in [[1, n - m]]$ . Soit $x \in F_{q}^{n}$ . Alors, on a $H x = 0 ⟺ \forall i \in [[1, n - m]], ⟨ v_{i}, x ⟩ = 0 ⟺ x \in (C^{⊥})^{⊥} ⟺ x \in C$ On aurait aussi pu se contenter de considérer le noyau à gauche de la matrice génératrice (c’est une caractérisation plus commode à implémenter en algorithmique). ◻

Définition 16. En reprenant les notations précédentes, $H$ est appelée matrice de contrôle du code $C$ .

Il s’agit là d’un critère extrêmement pratique pour permettre de tester l’appartenance d’un mot au code.

Exemple 17 (Code de répétition). On se place sur le corps $F_{2}$ . L’idée est d’envoyer plusieurs copies de chaque bit à être transmis. Ainsi, sur $F_{2}^{4}$ , le code $C$ est composé de deux mots : $(0, 0, 0, 0) et (1, 1, 1, 1)$ Des matrices génératrices $G$ et de contrôle $H$ sont données par $G = 1111 et H = 111100010001$ On corrige en remplaçant un message reçu reconnu erroné par le message émis potentiel le plus proche (c’est-à-dire avec le moins de bits différents). Par conséquent, le codage par répétition permet de corriger correctement une erreur portant sur un seul bit mais ne permet pas de corriger correctement une erreur portant sur deux bits.

Proposition 18 (Borne de Singleton). Soit $C$ un code linéaire de taille $n$ , de dimension $m$ et de distance minimale $d$ sur $F_{q}$ . Alors, $d \leq n - m + 1$

Démonstration. Pour prouver ceci, exhibons un mot $x$ de $C$ de poids inférieur ou égal à $n - m + 1$ (car alors, on aura $d \leq ω (x) \leq n - m + 1$ ). Soit $F$ , le sous-espace vectoriel de $F_{q}^{n}$ constitué des vecteurs dont les $m - 1$ dernières coordonnées sont nulles. C’est un espace de dimension $n - m + 1$ , et la formule de Grassmann donne : $dim (C \cap F) = dim (C) + dim (F) - dim (C + F) = m + n - m + 1 - dim (C + F) = n + 1 - dim (C + F) \geq n + 1 - n = 1$ Il existe donc $x \neq = 0$ dans $C \cap F$ , et ce mot a un poids inférieur ou égal à $n - m + 1$ . ◻

Ce dernier résultat illustre le choix à faire entre capacité de correction, et redondance de l’information transmise.

Terminons cette sous-section par la méthode pratique permettant de corriger un mot reçu. Pour cela, on a besoin d’une dernière définition.

Définition 19. Soit $C$ un code linéaire de taille $n$ et de dimension $m$ sur $F_{q}$ . Soit $H$ une matrice de contrôle de $C$ . On appelle syndrome d’un mot $x \in F_{q}^{m}$ le vecteur $H x$ .

Imaginons maintenant que l’on réceptionne un mot $a^{'} \in F_{q}^{m}$ . On calcule son syndrome via une matrice de contrôle $H$ et on a deux cas :

Le syndrome est nul : $a^{'} \in C$ : on considère alors qu’il n’y a pas d’erreur.
Le syndrome est non nul : il existe $a \in C$ (le mot d’origine) et $e \in F_{q}^{n}$ (l’erreur) tels que $a^{'} = a + e$ . Alors, $H a^{'} = H (a + e) = H a + He = He$ En notant $h_{j}$ le $j$ -ième vecteur colonne de $H$ et $e_{j}$ la $j$ -ième coordonnée de $e$ : $H a^{'} = j tel que e_{j} \neq = 0 \sum h_{j} e_{j} (*)$ On en déduit $e$ en résolvant le système $(*)$ . Il est possible que ce système n’ait pas de solution, s’il y a trop d’erreurs par exemple. S’il y a une solution, elle est unique et on peut effectuer la correction : $a = a^{'} - e$ .

Codes cycliques

Nous avons vu dans la section précédente qu’imposer une structure d’espace vectoriel sur un code rendait le codage de l’information beaucoup plus simple via les matrices génératrices. Renforçons davantage la structure de notre code et observons les conséquences.

Définition 20. Soit $C$ un code linéaire de taille $n$ et de dimension $m$ sur $F_{q}$ . $C$ est dit cyclique s’il est stable par décalage circulaire, ie. $(a_{0}, a_{1}, \dots, a_{m - 1}) \in C ⟹ (a_{1}, \dots, a_{m - 1}, a_{0}) \in C$

Notons maintenant $φ : F_{q}^{n} (a_{0}, \dots, a_{n - 1}) \to \mapsto F_{q} [X] / (X^{n} - 1) \overline{\sum_{i = 0}^{n - 1} a_{i} X^{i}}$

Lemme 21. $φ$ est un isomorphisme d’espaces vectoriels.

Démonstration. On sait (par la théorie des corps), que $F_{q} [X] / (X^{n} - 1)$ est un espace vectoriel sur $F_{q}$ de dimension $n$ . En effet, en notant $\overline{X}$ la classe de $X$ dans $F_{q} [X] / (X^{n} - 1)$ :

La famille $(\overline{1}, \dots, \overline{X}^{n - 1})$ est libre. Soient $λ_{0}, \dots, λ_{n - 1} \in K$ tels que $i = 0 \sum n - 1 λ_{i} \overline{X}^{i} = \overline{i = 0 \sum n - 1 λ_{i} X^{i}} = 0$ Alors, le polynôme $\sum_{i = 0}^{n - 1} λ_{i} X^{i}$ est dans l’idéal $(X^{n} - 1)$ , mais est de degré strictement inférieur à $n$ . Donc ses coefficients sont nuls : on a $\forall i \in [[1, n]]$ , $λ_{i} = 0$ .
La famille $(\overline{1}, \dots, \overline{X}^{n - 1})$ est génératrice. Soit $\overline{P} \in F_{q} [X] / (X^{n} - 1)$ . On fait la division euclidienne de $P$ par $X^{n} - 1$ dans $F_{q} [X]$ : $\exists (Q, R) \in F_{q} [X] tel que P = Q (X^{n} - 1) + R avec de g (R) < n ou R = 0$ En repassant modulo $(X^{n} - 1)$ , on a bien $\overline{P} = \overline{R}$ de degré inférieur à $n$ , donc appartenant à l’espace vectoriel engendré par $(\overline{1}, \dots, \overline{X}^{n - 1})$ .

Ainsi, $F_{q}^{n}$ et $F_{q} [X] / (X^{n} - 1)$ sont isomorphes en tant qu’espaces vectoriels de même dimension sur $F_{q}$ . L’application $φ$ étant surjective et linéaire (par définition), on a bien un isomorphisme. ◻

À l’aide de cet isomorphisme, nous allons pouvoir identifier un code linéaire de taille $n$ sur $F_{q}$ à un sous-espace vectoriel $C = φ (C)$ de $F_{q} [X] / (X^{n} - 1)$ . Ce raisonnement va nous permettre de caractériser les codes cycliques.

Proposition 22. Soit $C$ un code linéaire de taille $n$ . Alors, $C$ est cyclique si et seulement si $C = φ (C)$ est un idéal de $F_{q} [X] / (X^{n} - 1)$ .

Démonstration. Soient $a = (a_{0}, a_{1}, \dots, a_{n - 1}) \in C$ et $a^{'} = (a_{n - 1}, a_{0}, \dots, a_{n - 2})$ . Remarquons que, $φ (a^{'}) = \overline{a_{n - 1} + i = 0 \sum n - 2 a_{i} X^{i + 1}} = a_{n - 1} (\overline{1} - \overline{1} + \overline{X}^{n}) + i = 0 \sum n - 2 a_{i} \overline{X}^{i + 1} = i = 0 \sum n - 1 a_{i} \overline{X}^{i + 1} = \overline{X} i = 0 \sum n - 1 a_{i} \overline{X}^{i} = \overline{X} φ (a)$

Supposons $C$ cyclique. Alors, par ce qu’on vient de dire, $C$ est stable par multiplication par $X$ . Mais $C$ est un sous-espace vectoriel de $F_{q} [X] / (X^{n} - 1)$ , donc il est aussi stable par addition et par multiplication par un scalaire. Finalement, $C$ est bien un idéal de $F_{q} [X] / (X^{n} - 1)$ .
Supposons $C$ idéal de $F_{q} [X] / (X^{n} - 1)$ . Alors, $C$ est stable par multiplication par $X$ . Donc par le raisonnement précédent, $C$ est clairement cyclique.

◻

Nous arrivons au théorème suivant qui nous indique que, pour fabriquer un code cyclique de dimension $m$ , il suffit de savoir factoriser $X^{m} - 1$ dans $F_{q} [X]$ (ce qui peut se faire par l’algorithme de Berlekamp).

Théorème 23 (Structure des codes cycliques). Soit $m \in [[0, n]]$ .

Soit $P = \sum_{i = 0}^{n - m} a_{i} X^{i}$ un diviseur unitaire de $X^{n} - 1$ dans $F_{q} [X]$ . Soit $a = φ^{- 1} (\overline{P})$ le mot correspondant à $P$ . Alors, en notant $σ : F_{q}^{n} \to F_{q}^{n}$ l’application de permutation circulaire, $C = Vect (σ^{i} (a))_{i \in [[0, m - 1]]} (*)$ forme un code cyclique de dimension $m$ .
Réciproquement, si $C$ est un code cyclique de dimension $m$ sur $F_{q}^{n}$ , il existe un polynôme $P \in F_{q} [X]$ diviseur de $X^{n} - 1$ vérifiant $(*)$ pour $C$ .

Démonstration.

Clairement, $C = Vect (σ^{i} (x))_{i \in [[0, m - 1]]}$ est un sous-espace vectoriel de $F_{q}^{n} [X]$ de dimension $m$ : c’est un code linéaire. Reste à montrer qu’il est cyclique. Soit $b = \sum_{i = 0}^{m - 1} b_{i} σ^{i} (a)$ un mot de $C$ . Il s’agit de montrer que $σ (b) \in C$ . Or, $σ (b) = i = 0 \sum m - 1 b_{i} σ^{i + 1} (a) = b_{m - 1} σ^{m} (a) + i = 1 \sum m - 1 b_{i - 1} σ^{i} (m)$ et, d’après la base choisie pour $C$ , $\sum_{i = 1}^{m - 1} b_{i - 1} σ^{i} (m) \in C$ . Reste à montrer que $b_{m - 1} σ^{m} (a) \in C$ . On a, $φ (b_{m - 1} σ^{m} (a)) = b_{m - 1} \overline{X}^{m} φ (a) = b_{m - 1} \overline{X}^{m} \overline{P}$ Or, $P$ est de degré $n - m$ , unitaire et divise $X^{n} - 1$ , donc il existe $Q \in F_{q} [X]$ unitaire de degré $m$ tel que $X^{n} - 1 = PQ$ . D’où, $φ (b_{m - 1} σ^{m} (a)) = b_{m - 1} (\overline{X}^{m} - \overline{Q}) \overline{P} + b_{m - 1} \overline{Q} \overline{P} = b_{m - 1} (\overline{X}^{m} - \overline{Q}) \overline{P}$ Comme $b_{m - 1} (X^{m} - Q)$ est de degré au plus $m - 1$ , on peut l’écrire $\sum_{i = 0}^{m - 1} c_{i} X^{i}$ . Ainsi, $φ (b_{m - 1} σ^{m} (a)) = i = 0 \sum m - 1 c_{i} \overline{X}^{i} \overline{P} = i = 0 \sum m - 1 c_{i} φ (σ^{i} (a)) = φ (i = 0 \sum m - 1 c_{i} σ^{i} (a)) \in φ (C)$ D’où $b_{m - 1} σ^{m} (a) \in C$ : on a bien ce qu’on voulait.
Soient $C$ un code cyclique de dimension $m$ sur $F_{q}^{n}$ et $π = π_{(X^{n} - 1)}$ la projection de $F_{q} [X]$ sur le quotient $F_{q} [X] / (X^{n} - 1)$ . Alors, d’après la Proposition 22, $φ (C) = C$ est un idéal de $F_{q} [X] / (X^{n} - 1)$ , donc $π^{- 1} (C)$ est un idéal de $F_{q} [X]$ , qui est principal par principalité de $F_{q} [X]$ . On peut noter $P$ le générateur unitaire. Montrons que $P ∣ X^{n} - 1$ .

$C$ est un idéal de $F_{q} [X] / (X^{n} - 1)$ , donc $\overline{0} \in C$ , donc $X^{n} - 1 \in π^{- 1} (C)$ : il existe $Q \in F_{q} [X]$ tel que $X^{n} - 1 = QP$ . On a bien $P ∣ X^{n} - 1$ .

Il s’agit maintenant de montrer que $P$ est bien de degré $n - m$ . Notons $k = de g (P)$ . Soit $E = {h \in F_{q} [X] ∣ de g (h) \in [[0, n - k - 1}$ On a, $π (P \cdot E) = {\overline{P} \overline{h} \in F_{q} [X] / (X^{n} - 1) ∣ de g (h) \in [[0, n - k - 1}$ et $P \cdot E \subseteq π^{- 1} (C) ⟹ π (P \cdot E) \subseteq C$ .

Soit $R \in π^{- 1} (C)$ . Par définition de $P$ , il existe $S \in F_{q} [X]$ tel que $R = PS$ . On effectue la division euclidienne de $S$ par $Q$ : $\exists (T, U) \in F_{q} [X] tel que S = QT + U avec de g (U) < n - k ou U = 0$ d’où : $R ⟹ π (R) = P (QT + U) = T (X^{n} - 1) + P U = π (P U) \in π (P \cdot E)$ Ainsi, on a $C \subseteq π (P \cdot E)$ . On a alors montré que $C = π (P \cdot E)$ . Or, $∣ π (P \cdot E) ∣ = q^{n - k}$ et $C$ est un sous-espace vectoriel de $F_{q}^{n}$ de dimension $m$ . Par isomorphisme, on a donc : $∣ C ∣ = q^{m} = ∣ C ∣$ ce qui permet de conclure que $m = n - k$ .

Pour terminer, on écrit $P = \sum_{i = 0}^{n - m} a_{i} X^{i}$ et on considère $a = (a_{0}, \dots, a_{m - 1}) \in F_{q}^{m}$ . Comme $C$ est un idéal de $F_{q} [X] / (X^{n} - 1)$ , $\forall i \in [[0, m - 1]], \overline{X}^{i} \overline{P} \in C ⟹ \forall i \in [[0, m - 1]], σ (a)^{i} \in C$ Et $(σ^{i} (a))_{i \in [[0, m - 1]]}$ est une famille libre de cardinal $m$ , donc est bien une base de $C$ .

◻

Étude d’un code de Hamming

D’après Wikipédia, un code de Hamming est un code correcteur linéaire. Il permet la détection et la correction automatique d’une erreur si elle ne porte que sur une lettre du message. Un code de Hamming est parfait : pour une longueur de code donnée il n’existe pas d’autre code plus compact ayant la même capacité de correction. En ce sens son rendement est maximal. Il existe une famille de codes de Hamming ; le plus célèbre et le plus simple après le code de répétition binaire de dimension $3$ et de longueur $1$ est sans doute le code binaire de longueur $7$ , de dimension $4$ et de distance minimale $3$ : ça tombe bien, il est au programme de l’option C de modélisation !

Définition 24. Le code Hamming $C_{H}$ de longueur $7$ permet de coder un mot de longueur $4$ en un mot de code de longueur $7$ . C’est un code linéaire, dont une matrice génératrice est $G_{H} = 1101000011010000110100001101 \in M_{7, 4} (F_{2})$

Exemple 25. On souhaite coder le mot $(1, 0, 0, 1)$ . On calcule : $G_{H} 1001 = 1100101$ Le mot codé est donc $(1, 1, 0, 0, 1, 0, 1)$ .

On peut en fait expliciter les mots de ce code : il y en a $2^{4} = 16$ .

Mot	Mot codé	Poids	Mot	Mot codé	Poids
$(0, 0, 0, 0)$	$(0, 0, 0, 0, 0, 0, 0)$	$0$	$(1, 0, 0, 0)$	$(1, 1, 0, 1, 0, 0, 0)$	$3$
$(0, 0, 0, 1)$	$(0, 0, 0, 1, 1, 0, 1)$	$3$	$(1, 0, 0, 1)$	$(1, 1, 0, 0, 1, 0, 1)$	$4$
$(0, 0, 1, 0)$	$(0, 0, 1, 1, 0, 1, 0)$	$3$	$(1, 0, 1, 0)$	$(1, 1, 1, 0, 0, 1, 0)$	$4$
$(0, 0, 1, 1)$	$(0, 0, 1, 0, 1, 1, 1)$	$4$	$(1, 0, 1, 1)$	$(1, 1, 1, 1, 1, 1, 1)$	$7$
$(0, 1, 0, 0)$	$(0, 1, 1, 0, 1, 0, 0)$	$3$	$(1, 1, 0, 0)$	$(1, 0, 1, 1, 1, 0, 0)$	$4$
$(0, 1, 0, 1)$	$(0, 1, 1, 1, 0, 0, 1)$	$4$	$(1, 1, 0, 1)$	$(1, 0, 1, 0, 0, 0, 1)$	$3$
$(0, 1, 1, 0)$	$(0, 1, 0, 1, 1, 1, 0)$	$4$	$(1, 1, 1, 0)$	$(1, 0, 0, 0, 1, 1, 0)$	$3$
$(0, 1, 1, 1)$	$(0, 1, 0, 0, 0, 1, 1)$	$3$	$(1, 1, 1, 1)$	$(1, 0, 0, 1, 0, 1, 1)$	$4$

Proposition 26.

$C_{H}$ a une distance minimale de $3$ .
$C_{H}$ est $1$ -correcteur.
$H = 100010001110011111101$ est une matrice de contrôle de ce code.

Démonstration.

Le minimum des poids est bien $3$ d’après le tableau précédent.
D’après la Remarque 11, la capacité de correction du code est égale à $⌊ \frac{3 - 1}{2} ⌋ = 1$
Soit $x \in F_{2}^{7}$ . On note $(v_{0}, \dots, v_{3})$ la base de $C_{H}$ associée à $G_{H}$ . Alors, $x \in C^{⊥} ⟺ \forall i \in [[0, 3]], ⟨ x, v_{i} ⟩ = 0 ⟺ x = a h_{1} + b h_{2} + c h_{3} pour a, b, c \in F_{2}$ où $h_{1} = (1, 0, 0, 1, 0, 1, 1)$ , $h_{2} = (0, 1, 0, 1, 1, 1, 0)$ et $h_{3} = (0, 0, 1, 0, 1, 1, 1)$ . Donc $(h_{1}, h_{2}, h_{3})$ est une base de $C^{⊥}$ , ce qui mène au résultat voulu.

◻

Proposition 27. Le code de Hamming est cyclique, engendré par $P = X^{3} + X + 1$ .

Démonstration. Les $4$ vecteurs colonnes de la matrice $G_{H}$ se déduisent les uns des autres par permutation circulaire. Par conséquent, l’ensemble du code est invariant par permutation circulaire : $C_{H}$ est bien cyclique. Et le polynôme $P$ correspond au mot $(1, 1, 0, 1, 0, 0, 0)$ qui est le premier vecteur colonne de la matrice $G_{H}$ . ◻

En pratique, le code de Hamming se manipule de la manière suivante :

On a un mot $x \in F_{2}^{4}$ . On calcule $a = G_{H} x$ et on envoie $a$ .
Le receveur reçoit $a^{'}$ . Il calcule le syndrome $s = H a^{'}$ . Si $s$ est nul, il pose $a = a^{'}$ . Sinon, il pose $a = a^{'} + e_{j}$ où pour $j \in [[1, 7]]$ , $s = H e_{j}$ .
Le receveur résout $G_{H} x = a$ .