Codes correcteurs

Codes correcteurs linéaires : distance de Hamming, matrices G & H, syndrome, code de Hamming et bornes

Idée. Transmettre de l'information sur un canal bruité (CD rayé, paquet réseau corrompu, mémoire RAID) : on ajoute de la redondance pour détecter et corriger les erreurs. Mathématiquement, un code applique l'algèbre linéaire sur un corps fini $\mathbb{F}_q$ — c'est une application directe des chapitres Corps finis, Polynômes et Anneaux.

Note (L2/L3, démonstratif). Certains exercices sont des calculs (matrices, distance, décodage), d'autres des preuves (distance $=$ poids min, bornes). Les énoncés numériques sont vérifiés machine sur des codes concrets (_verif_codes.py).

A. Codes linéaires, distance de Hamming

Un code linéaire $[n,k]$ sur $\mathbb{F}_q$ est un sous-espace vectoriel $C\subseteq\mathbb{F}_q^{\,n}$ de dimension $k$ . Donc $\lvert C\rvert=q^{k}$ . Le rendement est $k/n$ .

Le poids $w(x)$ d'un mot est son nombre de coordonnées non nulles.
La distance de Hamming $d(x,y)=w(x-y)$ compte les positions où $x$ et $y$ diffèrent.
La distance minimale $d=\min_{x\neq y\in C}d(x,y)$ .

\boxed{\ \text{Pour un code LINÉAIRE : } d=\min_{x\in C,\ x\neq 0}w(x)\ }

car $d(x,y)=w(x-y)$ et $x-y$ parcourt $C\setminus\{0\}$ . On note le code $[n,k,d]$ .

Capacité. Un code de distance minimale $d$ :

\boxed{\ \text{détecte } d-1 \text{ erreurs}, \qquad \text{corrige } t=\Big\lfloor\tfrac{d-1}{2}\Big\rfloor \text{ erreurs.}\ }

Les boules de rayon

t

centrées sur les mots de code sont alors disjointes, d'où un décodage par plus proche voisin non ambigu. Exemples : code à répétition

[n,1,n]

, code de parité

[n,n-1,2]

(détecte

1

erreur, n'en corrige aucune).

B. Matrices génératrice & de contrôle, syndrome

Une matrice génératrice $G$ ( $k\times n$ ) a pour lignes une base de $C$ : $C=\{uG:u\in\mathbb{F}_q^{\,k}\}$ . Sous forme systématique $G=[\,I_k\mid A\,]$ (les $k$ premiers symboles sont le message). La matrice de contrôle $H$ ( $(n-k)\times n$ ) vérifie $C=\{x:Hx^{\mathsf T}=0\}$ :

\boxed{\ G=[\,I_k\mid A\,]\ \Longrightarrow\ H=[\,-A^{\mathsf T}\mid I_{n-k}\,],\qquad GH^{\mathsf T}=0.\ }

Le syndrome d'un mot reçu

r

est

s=Hr^{\mathsf T}

s=0\iff r\in C

. Si

r=c+e

(erreur

e

), alors

s=He^{\mathsf T}

ne dépend que de l'erreur.

\boxed{\ d=\text{plus petit nombre de colonnes de } H \text{ linéairement dépendantes.}\ }

Décodage par tableau standard / syndrome. À chaque syndrome on associe le chef de classe (l'erreur de poids minimal de même syndrome) ; il y a $q^{\,n-k}$ syndromes (un par coset). On corrige ainsi toutes les erreurs de poids $\leq t$ . Le code dual $C^{\perp}$ (engendré par $H$ ) est de dimension $n-k$ , et $(C^{\perp})^{\perp}=C$ .

E. Code de Hamming, codes parfaits, bornes

Le code de Hamming $[7,4,3]$ : on prend pour colonnes de $H$ tous les vecteurs non nuls de $\mathbb{F}_2^{\,3}$ (il y en a $7$ ). Alors $n=7$ , $n-k=3$ donc $k=4$ , et $d=3$ (toute paire de colonnes est indépendante, mais trois colonnes peuvent être liées). Il corrige $1$ erreur.

Diagramme du code de Hamming [7,4,3] : à gauche les sept colonnes de la matrice de contrôle (les vecteurs binaires 001 à 111), à droite des boules de Hamming de rayon 1 autour des mots de code qui pavent l'espace sans recouvrement, avec le décompte 16 fois 8 égale 128. — **Code de Hamming $[7,4,3]$ et sphères de correction.** Les colonnes de la matrice de contrôle $H$ sont les $7$ vecteurs non nuls de $\mathbb{F}_2^{\,3}$ . Le code a $2^4=16$ mots ; chaque mot reçu à distance $\leq 1$ d'un mot de code se décode vers lui. Les **boules de rayon $1$** (un centre $+\,7$ voisins $=8$ mots) **pavent** exactement $\mathbb{F}_2^{\,7}$ : $16\times 8=128=2^7$ . C'est un code **parfait**.

Code parfait. Les boules de rayon $t$ pavent exactement $\mathbb{F}_q^{\,n}$ :

\boxed{\ q^{k}\cdot V_q(n,t)=q^{n},\qquad V_q(n,t)=\sum_{i=0}^{t}\binom{n}{i}(q-1)^i.\ }

Hamming

[7,4,3]

2^{4}\cdot V_2(7,1)=16\cdot(1+7)=16\cdot 8=128=2^{7}

— parfait.

Bornes. Deux contraintes universelles :

\boxed{\ \text{Hamming (sphère) : } \lvert C\rvert\leq\dfrac{q^{n}}{V_q(n,t)}\qquad\text{Singleton : } d\leq n-k+1.\ }

Un code atteignant Singleton (

d=n-k+1

) est MDS (répétition et parité le sont ; Hamming

[7,4,3]

ne l'est pas car

n-k+1=4>3