Exercices corrigés — Codes correcteurs

$n$ est la longueur (nombre de colonnes), $k$ le rang de $G$.

$\lvert C\rvert=2^{k}$ car $C$ est un sous-espace.

Les mots sont les combinaisons $u_1L_1+u_2L_2$, $u_i\in\{0,1\}$.

Une matrice génératrice $G$ de taille $k\times n$ définit un code $C$ comme l'ensemble des combinaisons linéaires de ses lignes :

Les trois paramètres se lisent directement sur la forme de $G$ :

• $n$ = nombre de colonnes = longueur des mots de code ;
• $k$ = nombre de lignes (si elles sont indépendantes) = dimension ;
• $\lvert C\rvert=q^k$ où $q$ est la taille du corps.

Ici $G$ est $2\times 4$ sur $\mathbb{F}_2$, donc on attend $n=4$, $k=2$, $\lvert C\rvert=4$. Encore faut-il vérifier que les deux lignes sont indépendantes.

$n=4$ : quatre colonnes.

$k=2$ : les deux lignes sont indépendantes. On le voit sans calcul grâce à la partie $I_2$ à gauche — la première ligne commence par $10$, la seconde par $01$, aucune n'est multiple de l'autre. Le rang vaut donc $2$.

On dit que $G$ est sous forme systématique $[\,I_2\mid A\,]$ avec $A=\begin{pmatrix}1&1\\1&0\end{pmatrix}$ : les $k$ premiers bits d'un mot de code sont le message lui-même, les $n-k$ derniers sont les bits de contrôle.

On parcourt les $4$ messages possibles $m=(m_1,m_2)$ et on calcule $mG=m_1L_1+m_2L_2$, où $L_1=1011$ et $L_2=0110$ sont les lignes de $G$. L'addition est modulo $2$ — c'est-à-dire le OU exclusif bit à bit.

Détail du dernier, le seul qui demande un calcul :

colonne par colonne : $1+0=1$ · $0+1=1$ · $1+1=0$ (modulo $2$ !) · $1+0=1$.

Le nombre. On a bien $4=2^2$ mots distincts. Si deux messages avaient donné le même mot, $G$ ne serait pas de rang $2$ et $k$ vaudrait $1$.

La stabilité par addition. Un code linéaire est un sous-espace vectoriel : la somme de deux mots de code est un mot de code. Vérifions sur une paire :

Et le mot nul appartient toujours à un code linéaire (prendre $m=0$) — c'est ce qui rendra possible le raccourci de l'exercice A2.

Regardons les poids (nombre de $1$) des mots non nuls :

La distance minimale est donc $d=2$ (exercice A2), et le code est un $[4,2,2]$.

⚠️ Ce code ne corrige AUCUNE erreur. Il en détecte une seule : si un bit bascule, le mot reçu est à distance $1$ d'un mot de code, donc il n'est plus dans $C$ — on sait qu'il y a eu une erreur, mais on ne peut pas savoir laquelle, car il peut être à distance $1$ de plusieurs mots.

C'est une bonne raison de ne pas confondre détecter et corriger, et cela motive tout le reste du chapitre : pour corriger, il faut $d\geq 3$ — le code $[5,2,3]$ de l'exercice A3, puis Hamming.

$d(x,y)=w(x-y)$ pour la distance de Hamming.

Si $x,y\in C$ alors $x-y\in C$ (sous-espace).

Faire varier la paire $(x,y)$ et le mot $z=x-y$.

La distance minimale est définie comme

où $d_H(x,y)$ est le nombre de positions où $x$ et $y$ diffèrent. Calculée telle quelle, elle demande d'examiner toutes les paires : $\binom{\lvert C\rvert}{2}$ comparaisons.

L'énoncé affirme que pour un code linéaire, il suffit de parcourir les mots un par un :

On passe de $\binom{q^k}{2}$ à $q^k-1$ calculs. Sur Hamming $[7,4]$ : $120$ paires contre $15$ poids. Sur un code de dimension $32$, la différence est celle entre l'impossible et l'immédiat.

L'ingrédient est la linéarité, et rien d'autre : $C$ est un sous-espace, donc stable par différence.

Le point de départ est une identité valable pour tous vecteurs :

Pourquoi : les coordonnées où $x$ et $y$ diffèrent sont exactement celles où $x-y$ est non nul. Compter les unes ou les autres, c'est la même chose.

(Sur $\mathbb{F}_2$, $x-y=x+y$, ce qui simplifie les calculs sans changer l'argument.)

Sens $\leq$. Soit $x\in C$ non nul. Comme $0\in C$ (un sous-espace contient toujours le vecteur nul), le couple $(x,0)$ est un couple de mots de code distincts, donc

Ceci valant pour tout $x$ non nul, on obtient $d\leq \min_{x\neq 0}w(x)$.

Sens $\geq$. Soient $x\neq y$ deux mots de code réalisant la distance minimale. Comme $C$ est un sous-espace, $z=x-y$ est encore un mot de code, et il est non nul puisque $x\neq y$. Donc

Les deux inégalités donnent l'égalité :

Poids des trois mots non nuls :

Le code est donc un $[4,2,2]$.

Contrôle par la définition, sur les $\binom42=6$ paires — c'est ce que le théorème permet justement d'éviter, mais le faire une fois convainc :

Minimum $=2$ ✓. Et l'on voit la mécanique : chaque distance entre deux mots de code est le poids d'un troisième mot de code.

⚠️ L'énoncé est FAUX pour un code non linéaire. Contre-exemple minimal :

Ses deux mots ont poids $2$, donc « le poids minimal » vaudrait $2$. Mais

ici les deux coïncident — prenons plutôt $C''=\{1110,\ 1101\}$ : poids minimal $3$, alors que $d_H(1110,1101)=2$. La distance est strictement plus petite que le poids minimal.

Ce qui casse : $1110-1101=0011$ n'appartient pas à $C''$, donc le raisonnement de l'étape 2 ne s'applique pas.

👉 Vérifier la linéarité avant d'employer le raccourci. C'est l'une des raisons pour lesquelles on travaille presque toujours avec des codes linéaires : ils rendent la distance minimale calculable.

Supposer deux mots $c\neq c'$ et un reçu $y$ avec $d(y,c)\leq t$ et $d(y,c')\leq t$.

Inégalité triangulaire : $d(c,c')\leq d(c,y)+d(y,c')$.

En déduire $d(c,c')\leq 2t\leq d-1<d$, contradiction.

Un code de distance minimale $d$ corrige $t=\lfloor(d-1)/2\rfloor$ erreurs. La preuve tient dans une image géométrique, qu'il faut avoir en tête pour tout ce chapitre.

Autour de chaque mot de code $c$, on trace la boule de Hamming de rayon $t$ :

c'est-à-dire tous les mots qu'on peut obtenir en changeant au plus $t$ bits de $c$.

Si ces boules ne se chevauchent pas, alors un mot reçu avec au plus $t$ erreurs tombe dans une seule boule — celle de son émetteur — et le décodage « au plus proche voisin » retrouve le bon mot, sans ambiguïté.

Tout se ramène donc à : quand les boules sont-elles disjointes ?

Raisonnons par l'absurde. Supposons qu'un mot $x$ appartienne à deux boules, autour de deux mots de code distincts $c_1\neq c_2$ :

L'inégalité triangulaire — vraie pour la distance de Hamming comme pour toute distance — donne alors

Or $c_1$ et $c_2$ sont deux mots de code distincts, donc $d_H(c_1,c_2)\geq d$. D'où

Mais par définition $t=\lfloor(d-1)/2\rfloor$, donc $2t\leq d-1<d$ — contradiction.

Les boules de rayon $t$ sont donc deux à deux disjointes.

Soit $c$ le mot émis et $r=c+e$ le mot reçu, avec $w(e)\leq t$ erreurs.

Alors $d_H(r,c)=w(e)\leq t$, donc $r\in B(c,t)$. Et par l'étape 1, $r$ n'est dans aucune autre boule. Le décodeur qui cherche le mot de code le plus proche de $r$ trouve donc $c$, et lui seul :

Pourquoi la partie entière. Il faut $2t<d$, soit $t<d/2$, soit $t\leq\lceil d/2\rceil-1$, ce qui s'écrit $t=\lfloor(d-1)/2\rfloor$. Concrètement :

Noter que $d=3$ et $d=4$ corrigent autant : c'est le passage à $d$ impair qui fait gagner.

Énumérons les $2^2=4$ mots, comme en A1 :

(pour $m=11$ : $10110+01011=11101$, en additionnant modulo $2$ colonne par colonne.)

Par l'exercice A2, $d=\min(3,3,4)=3$, donc

Ce code $[5,2,3]$ corrige une erreur, là où le $[4,2,2]$ de A1 n'en corrigeait aucune. Un bit de plus a suffi à faire passer $d$ de $2$ à $3$.

Comptons le volume occupé. Chaque boule de rayon $1$ dans $\mathbb{F}_2^{\,5}$ contient

et il y a $4$ mots de code, donc les boules couvrent $4\times 6=24$ mots sur les $2^5=32$ possibles.

Il reste $8$ mots hors de toute boule : reçus, ils sont détectés comme erronés mais ne se décodent pas de façon fiable. Le code n'est donc pas parfait.

👉 La question naturelle : existe-t-il des codes dont les boules pavent exactement l'espace, sans trou ni chevauchement ? Oui — c'est le code de Hamming (exercice E2), où $16\times 8=128=2^7$ tombe juste. C'est le fil qui mène à la borne de Hamming (E3).

Répétition : un seul bit d'information répété $n$ fois.

Parité : $G=[I_3\mid \mathbf{1}]$, la dernière colonne est la somme des $3$ premières.

$d$ = poids minimal d'un mot non nul.

Ces deux familles sont les bornes du compromis entre protection et efficacité, et tout le chapitre se situe entre elles.

• Le code à répétition protège au maximum et transmet le minimum : il envoie le même bit $n$ fois.
• Le code de parité transmet presque tout et protège au minimum : il ajoute un seul bit de contrôle.

On mesure l'efficacité par le rendement $R=k/n$ : la proportion de bits utiles.

$n=5$ : les mots ont cinq bits.

$k=1$ : il y a $2$ mots, et $2=2^1$. On peut le voir sur la génératrice, qui n'a qu'une ligne :

$d=5$ : le seul mot non nul est $11111$, de poids $5$ (exercice A2).

Il corrige deux erreurs, par vote majoritaire : sur cinq bits reçus, on décode par la valeur qui apparaît le plus souvent. Avec au plus deux erreurs, la majorité reste du bon côté.

Rendement : $R=1/5=20\,\%$ — quatre bits sur cinq sont de la redondance pure.

On part de $3$ bits d'information $(m_1,m_2,m_3)$ et on ajoute un quatrième bit égal à leur somme modulo $2$ :

$n=4$, $k=3$, donc $\lvert C\rvert=2^3=8$ mots.

$d=2$ : tout mot de code a un poids pair. En effet le dernier bit vaut $m_1+m_2+m_3$, donc la somme des quatre bits vaut $2(m_1+m_2+m_3)\equiv 0$. Le plus petit poids non nul possible est donc $2$, et il est atteint (par exemple $1001$, obtenu avec $m=100$).

Il détecte une erreur (la parité devient impaire) et n'en corrige aucune. Rendement : $R=3/4=75\,\%$.

La tension est structurelle : augmenter $d$ oblige à écarter les mots de code, donc à en avoir moins, donc à baisser $k$. C'est ce que quantifient les deux bornes du chapitre — Hamming (E3) et Singleton (E4).

La parité est utilisée partout où l'on peut redemander la donnée (bus série, mémoire avec retransmission) : détecter suffit. La répétition est réservée aux canaux où redemander coûte trop cher.

La borne de Singleton (exercice E4) affirme $d\leq n-k+1$. Vérifions :

Les deux atteignent la borne : ce sont des codes MDS (maximum distance separable), c'est-à-dire optimaux au sens de Singleton.

⚠️ Cela ne veut pas dire qu'ils sont bons en pratique. Être MDS signifie « meilleure distance possible pour ce couple $(n,k)$ » ; ça ne dit rien sur le fait que le couple $(n,k)$ soit un bon choix. La répétition est MDS et de rendement catastrophique.

Contraste utile : Hamming $[7,4,3]$ n'est pas MDS ($3<4$, exercice E5), et c'est pourtant un bien meilleur code que la répétition pour un canal ordinaire.

Reprendre les $4$ mots de code et compter leurs poids.

$A_0=1$ (le mot nul).

$d$ est le plus petit indice $i>0$ avec $A_i>0$.

La distribution des poids d'un code est la suite $(A_0,A_1,\dots,A_n)$ où $A_i$ compte les mots de code de poids exactement $i$.

C'est un résumé bien plus riche que le seul $d$ : il dit combien de mots sont à chaque distance, ce qui permet d'estimer la probabilité d'erreur après décodage, et non seulement de savoir si elle est nulle.

On l'écrit souvent sous forme polynomiale — l'énumérateur —

et c'est sous cette forme que l'identité de MacWilliams relie $W_C$ à $W_{C^\perp}$.

Le code de l'exercice A1 :

Poids un par un :

La somme. Chaque mot de code est compté exactement une fois, donc

C'est le contrôle à faire systématiquement : un total qui ne tombe pas sur $q^k$ signale un mot oublié ou compté deux fois.

La distance minimale. Par l'exercice A2, $d$ est le plus petit poids non nul, donc le plus petit indice $i\geq 1$ avec $A_i>0$ :

Un troisième contrôle, gratuit : $A_0=1$ toujours, pour un code linéaire — le mot nul y est, et il est le seul de poids $0$.

Comparons deux codes qui auraient tous deux $d=2$ :

(pour la parité : les mots de poids pair sur $4$ bits sont $\binom42=6$ de poids $2$, et $1$ de poids $4$, plus le nul.)

Même $d$, distributions très différentes. Le second a six mots à distance $2$ du mot nul, le premier un seul : à bruit égal, les confusions ne sont pas aussi probables.

👉 En pratique, la probabilité qu'une erreur de transmission passe inaperçue vaut $\sum_{i\geq d}A_i\,p^{\,i}(1-p)^{\,n-i}$ où $p$ est la probabilité d'erreur par bit, et celle qu'un décodeur se trompe se majore, elle aussi, par une somme pondérée par les $A_i$. C'est la distribution entière qui entre dans le calcul, pas seulement son premier terme non nul.

Certains codes ont tous leurs mots non nuls de même poids : on les dit à poids constant. C'est le cas du code simplexe $[7,3]$ (exercice E6), dual du code de Hamming :

Ses $7$ mots non nuls sont tous de poids $4$. La distribution tient en deux nombres, et l'on lit immédiatement $d^\perp=4$.

Contrôle : $1+7=8=2^3$ ✓.

Le code de Hamming lui-même a pour distribution

avec $\sum A_i=16=2^4$ ✓. Le $A_7=1$ est le mot $1111111$ — le complément du mot nul, toujours dans le code de Hamming.

$\lvert C\rvert=q^k=3^2$.

$d$ = poids minimal d'un mot non nul (linéarité, valable sur tout $\mathbb{F}_q$).

Examiner par exemple la ligne $L_1=(1,0,1,2)$ et les combinaisons.

Presque tout le chapitre se passe sur $\mathbb{F}_2$, où les calculs sont des OU exclusifs. Cet exercice montre que rien dans la théorie ne dépend de $q=2$ : la définition d'un code linéaire, la distance de Hamming, le lien distance-poids valent sur tout corps fini.

Ce qui change, ce sont les calculs : sur $\mathbb{F}_3$, les coefficients sont $0,1,2$, et $2$ joue le rôle de $-1$ puisque $2\equiv-1\pmod 3$.

L'enjeu pratique est réel : les codes de Reed-Solomon (exercices D1 à D3), qui protègent les CD, les QR-codes et les transmissions spatiales, vivent sur des corps à $256$ éléments.

$n=4$ colonnes, $k=2$ lignes indépendantes (partie $I_2$ à gauche), donc

⚠️ Le passage de $2^k$ à $q^k$ est la seule chose à adapter — et c'est là qu'on se trompe si l'on raisonne par habitude binaire.

On calcule $mG=m_1L_1+m_2L_2$ avec $L_1=1012$, $L_2=0121$, tout modulo $3$ :

Détail du mot de poids minimal, $m=11$ :

car $3\equiv 0\pmod 3$. C'est là que le calcul diffère du binaire : deux coordonnées s'annulent d'un coup.

Contrôle : $m=22$ donne $2\times(1100)=2200$ — cohérent, puisque $C$ est stable par multiplication scalaire.

Par l'exercice A2, valable sur tout corps :

Le code est un $[4,2,2]_3$, avec

Il détecte une erreur, n'en corrige aucune — comme le $[4,2,2]$ binaire de A1.

Contrôle de la distribution : $(A_0,A_1,A_2,A_3,A_4)=(1,0,2,4,2)$, de somme $1+0+2+4+2=9=3^2$ ✓.

⚠️ Les deux pièges sont dans la seconde table. Le volume de boule : changer une coordonnée offre $q-1$ valeurs possibles, pas une seule — sur $\mathbb{F}_3$, $V_3(4,1)=1+4\times 2=9$ et non $5$. Et le signe de $-A^{\mathsf T}$ (exercice B1), invisible sur $\mathbb{F}_2$ où $-1=1$, devient indispensable dès $q\geq 3$.

Calculer $GH^{\mathsf T}=I_k(-A)+A\,I_{n-k}$ par blocs.

$\operatorname{rg}H=n-k$ car $H$ contient le bloc identité $I_{n-k}$.

Sur $\mathbb{F}_2$, $-A=A$.

Un code linéaire se décrit de deux façons complémentaires :

• par ce qu'il contient — la génératrice $G$ : $C=\{mG\}$ ;
• par ce qu'il vérifie — la matrice de contrôle $H$ : $C=\{x:\ Hx^{\mathsf T}=0\}$.

La seconde est celle qui sert au décodage : tester si un mot reçu appartient au code coûte un produit matriciel, alors qu'avec $G$ il faudrait chercher un antécédent.

Quand $G$ est systématique, $G=[\,I_k\mid A\,]$, on passe de l'une à l'autre sans aucun calcul :

⚠️ Le signe $-$ est invisible sur $\mathbb{F}_2$ (où $-1=1$) mais indispensable dès $q\geq 3$.

Calculons le produit par blocs :

Ce que ça signifie : chaque ligne de $G$ — donc chaque générateur du code — annule $H$. Par linéarité, tout mot de code $x=mG$ vérifie

Donc $C\subset\ker H$.

$H$ contient le bloc $I_{n-k}$ à droite : ses $n-k$ lignes sont donc indépendantes (aucune combinaison non triviale ne peut annuler la partie identité), d'où

Par le théorème du rang, $\dim\ker H=n-(n-k)=k$.

Or on a montré $C\subset\ker H$, et $\dim C=k=\dim\ker H$. Une inclusion entre espaces de même dimension finie est une égalité :

$H$ est donc bien une matrice de contrôle : elle ne se contente pas d'annuler le code, elle le caractérise.

Transposer (échanger lignes et colonnes) :

Sur $\mathbb{F}_2$, $-A^{\mathsf T}=A^{\mathsf T}$. En accolant $I_3$ :

Et la génératrice correspondante :

Vérifions $GH^{\mathsf T}=0$ sur la première ligne de $G$, soit $g_1=100110$. Il faut $Hg_1^{\mathsf T}=0$, c'est-à-dire, ligne de $H$ par ligne de $H$ :

Les trois s'annulent ✓ (le calcul complet donne bien la matrice nulle $3\times 3$).

Ce que $H$ va servir à faire, dans les trois exercices suivants :

• lire $d$ sur ses colonnes (B2) ;
• calculer un syndrome pour localiser une erreur (B3) ;
• engendrer le code dual (B6).

Réciproquement, on passe de $H=[\,B\mid I_{n-k}\,]$ à $G=[\,I_k\mid -B^{\mathsf T}\,]$ : la construction est symétrique.