La matrice de contrôle de parité
Tout code linéaire sur GF(2) — le corps avec seulement 0 & 1, l'arithmétique modulo 2 — a une matrice de contrôle de parité H. Pour le code de Hamming (7,4), H est une matrice 3×7 dont les colonnes sont les représentations binaires de 1 à 7 :
``
H = [ 0 0 0 1 1 1 1 ] ← bit 2 du numéro de position
[ 0 1 1 0 0 1 1 ] ← bit 1 du numéro de position
[ 1 0 1 0 1 0 1 ] ← bit 0 du numéro de position
``
La colonne j de H est la représentation binaire de j. C'est pourquoi le syndrome s = Hr nomme directement la position d'erreur.
L'application H: GF(2)^7 → GF(2)^3 est une application linéaire (multiplication matricielle mod 2). Son noyau ker(H) = { r : Hr = 0 } est exactement l'ensemble des mots de code valides.
Calcul de dimension : dim(ker H) = 7 − rank(H) = 7 − 3 = 4. Il y a donc 2^4 = 16 mots de code. Cela confirme 4 bits de message.
Le code comme un noyau
Un mot c ∈ {0,1}^7 est un mot de code valide si & seulement si Hc = 0 (mod 2). C'est l'équation définissante d'un code linéaire.
Exemple : c = 0011001. Vérifiez Hc mod 2 :
``
Ligne 1: 0·0+0·0+0·1+1·1+1·0+1·0+1·1 = 0+0+0+1+0+0+1 = 2 ≡ 0
Ligne 2: 0·0+1·0+1·1+0·1+0·0+1·0+1·1 = 0+0+1+0+0+0+1 = 2 ≡ 0
Ligne 3: 1·0+0·0+1·1+0·1+1·0+0·0+1·1 = 0+0+1+0+0+0+1 = 2 ≡ 0
``
Hc = 000. Donc 0011001 est un mot de code valide.
Cosets du code
Les mots de code C = ker(H) forment un sous-groupe de GF(2)^7. Chaque autre mot dans GF(2)^7 appartient à exactement un coset de C.
Définition de coset : pour n'importe quel mot e, le coset C + e = { c + e : c ∈ C }.
Deux mots appartiennent au même coset si & seulement si leur différence est un mot de code — de manière équivalente, s'ils ont le même syndrome : H(r₁) = H(r₂) ssi H(r₁ − r₂) = 0 ssi r₁ − r₂ ∈ C.
La carte de syndrome H induit un isomorphisme GF(2)^7 / C ≅ GF(2)^3. Avec |C| = 16 & |GF(2)^7| = 128 : il y a exactement 128/16 = 8 cosets, un pour chaque valeur de syndrome dans GF(2)^3.
Tableau standard : lister un meneur de coset par coset — le mot de poids de Hamming minimum dans ce coset. Pour la correction d'erreur unique, chaque syndrome non nul correspond de manière unique à un motif d'erreur de poids 1 (un seul 1 dans l'une des 7 positions). C'est pourquoi 7 motifs d'erreur + 1 pas d'erreur = 8 cosets = 2^3.
Décodage via les meneurs de cosets
Algorithme de décodage : recevoir r → calculer s = Hr → chercher le meneur de coset e_s (l'erreur canonique pour le syndrome s) → sortie r − e_s = r + e_s (même dans GF(2)).
Pour le code (7,4), les 8 meneurs de coset sont : 0000000 (syndrome 000), 1000000 (syndrome 001), 0100000 (syndrome 010), 0010000 (syndrome 011), 0001000 (syndrome 100), 0000100 (syndrome 101), 0000010 (syndrome 110), 0000001 (syndrome 111).
Pourquoi (7,4) est parfait
Un code C ⊆ GF(2)^n de distance minimale 3 corrige toutes les erreurs uniques. Chaque mot de code c a une boule de Hamming de rayon 1 : le centre c & ses n voisins immédiats (motifs d'erreur de poids 1). Volume de boule = 1 + n.
Pour n = 7 : volume de boule = 8. Avec 16 mots de code : 16 × 8 = 128 = 2^7. Les boules paveent GF(2)^7 parfaitement — aucun point non couvert, aucun point couvert deux fois.
C'est la définition d'un code parfait : M · Vol(n, t) = 2^n. Les codes parfaits de correction d'erreur unique binaire (t=1) existent seulement pour des paramètres spécifiques : (7,4), (15,11), (23,12) (le code de Golay binaire), & trivialement n = 2^r − 1, k = n − r pour tout r ≥ 2.
La géométrie : GF(2)^7 se décompose en exactement 8 orbites sous l'action du code comme partition de coset. Chaque orbite est un coset ; chaque coset a un syndrome unique. La carte de syndrome H est une bijection de cosets à GF(2)^3.
L'argument de comptage
Pour un code parfait binaire de correction d'erreur unique sur n = 2^r − 1 bits avec r bits de contrôle de parité :
- Nombre de mots de code : M = 2^k = 2^(n−r)
- Volume de boule : Vol(n, 1) = 1 + n = 1 + 2^r − 1 = 2^r
- Total couvert : M × Vol = 2^(n−r) × 2^r = 2^n ✓
Le fait que Vol(n,1) = 2^r quand n = 2^r − 1 est ce qui rend les codes parfaits possibles à ces longueurs. À d'autres longueurs, 1 + n n'est pas une puissance de 2, & les codes binaires parfaits de correction d'erreur unique ne peuvent pas exister.
Matrice génératrice & dualité
La matrice de contrôle de parité H définit le code via le noyau. Son dual : une matrice génératrice G dont les lignes forment une base pour ker(H).
Pour le code (7,4) : G est une matrice 4×7. N'importe quel mot de code c = mG pour un vecteur de message m ∈ GF(2)^4. Les lignes de G s'étendent sur le code ; les lignes de H s'étendent sur l'espace nul du code.
Relation clé : HG^T = 0 (mod 2). Chaque ligne de G est dans ker(H) ; chaque ligne de H annule chaque ligne de G.
Code dual : C⊥ = ker(G^T) = image(H^T). Pour le code (7,4), le dual est un code (7,3) — un code [7,3,4] de distance minimale 4.
La géométrie de dualité : C & C⊥ sont des sous-espaces orthogonaux de GF(2)^7. L'espace entier se décompose en le code, ses cosets, & la structure duale que la carte de syndrome encode.