Aix-Marseille Université

Préparation à l’agrégation: Option C

https://www.i2m.univ-amu.fr/perso/david.kohel/tch/Agreg/

Codes linéaires

Codes correcteurs d’erreurs

La théorie d’information concerne les transformations permettant la transmission effi-
cace, fiable et sécurisée de l’information. Les codages correcteurs d’erreurs sont les trans-
formations avec rédondance qui protègent l’information contre pertes lors d’une trans-
mission sur un canal bruyant. Le canal de transmission peut être l’atmosphère lors d’une
émmission par un antenne radio ou un satellite, le lecteur d’un CD, DVD ou disque dur,
ou le disque ou matériel de stockage de mémoire lui-même — transmettant l’information
à une date ultérieure avec dégradation pendant le temps.
On va s’intéresser particulièrement aux codes linéaires, qui sont des sous-espaces vec-
toriels d’un espace vectoriel Fnq , dont le corps fini Fq est l’alphabet du code.
Représentation de l’information. Avant de présenter les codes linéaires, il faut intro-
duire de la terminologie pour la représentation de l’information.
Définition. Un alphabet A est un ensemble fini. On appelle leurs éléments des lettres (ou
caractères ou symboles). Un mot est une suite finie de lettres d’un alphabet. L’ensemble
de mots de longueur n s’écrit An , et l’union disjointe
[
A∗ = An .
n≥0

Un codage est une application

C : M −→ A∗ ,
d’un ensemble M, permettant d’écrire des éléments de M en mots de l’alphabet A. On
dit que le codage est sans pertes s’il est injectif (terminologie spécifique à la théorie des
codes). Un code est l’image C = C(M) d’un codage, et un mot de code de C est un élément.
Exemples. L’alphabet classique {A, . . . , Z} réduit est souvant utilisé en cryptographie
classique, mais en ajoutant les lettres miniscules, des espaces et pontuation, etc., on arrive
à un alphabet A permettant le codage sans pertes de la plupart des langues européenes
occidentales dans A∗ . L’alphabet binaire {0, 1} des bits est l’alphabet de base pour les
ordinateurs modernes. Les octets {0, 1}8 constitue un autre alphabet. Les codages ASCII
ou ISO-8859-1, permettent d’encoder un alphabet occidental dans les 256 octets. Dans la
théorie des codes correcteurs d’erreurs va s’orienter vers A = Fq , où souvant q = 2.
Remarque 1. Une langue est un sous-ensemble M de A∗ , dont des éléments s’appellent
des messages ou textes, qui peut être équipée d’une fonction de probabilité, ce qui permet
de différencier plusieurs langues dans le même ensemble de mots A∗ . Les messages d’une
langue sont justes les mots avec probabilité non nul. Un message d’une langue, peut être
le codage d’un mot (dans le sens familier), d’une phrase, ou d’un roman tout entier d’une
langue naturelle.
Remarque 2. En cryptographie on dit chiffrement pour un codage qui transforme les
messages en forme dont leur information est cachée. Le domaine d’un chiffrement est
l’espace M de messages ou de textes clairs et le codomaine C l’espace des textes chiffrés
pour l’ensemble des mots de code. L’utilisation du mot espace évoque le fait que M et C,
qui sont de fois égaux en tant qu’ensembles, mais se différencient par la distribution de
leur éléments, portant des structures d’espaces de probabilité.

Exemples des codes correcteurs d’erreurs

Avant d’introduire des codes formellement, on donne quelques exemples de codages

permettant d’ajouter de la redondance lors d’une transmission. Dans ces exemples, tous
linéaires, l’alphabet est binaire : A = F2 . Pour concision, on écrit un vecteur de l’espace
vectoriel Fk2 par x1 x2 . . . xk et son image c = C(x), par c1 c2 . . . cn , au lieu d’un forme de
vecteur (x1 , x2 , . . . , xk ) et (c1 , c2 , . . . , cn ). On note le rendement R = k/n du code

C : Fk2 −→ Fn2 ,

qui est le nombre k de bits d’information par rapport au nombre de bits n utilisés pour
l’écriture d’un mot de code. Dans les exemples suivants on a k = 8, et on donne l’image
d’un message type
m = 01101110 ∈ F82 .
Exemple 1. Un codage de répétition est l’application qui double le nombre de bits par
répétition de chaque bit. La répétition peut être par bit 0011110011111100 ou de l’octet
tout entier 0110111001101110. Le rendement est donc R = 1/2.
Exemple 2. Au lieu de répéter tous les bits on peut garder un rendement plus élévé
en ajoutant un bit de parité (= somme des bits dans F2 ) après chaque couple de bits :
C(01101110) = 011|101|110|101 = 011101110101 ∈ F12
2 . Le rendement est donc R = 2/3.

Exemple 3. On peut construire un codage en combinant un bit de parité (par couple)

avec répétition du deuxième bit :

C(01101110) = 0111|1010|1101|1010 = 0111101011011010 ∈ F16

2 .

Le rendement est de nouveau R = 1/2.

En quel sens peut-on dire qu’on obtient une meilleure séparation des mots de codes ?
Exemple 4. Pour faire mieux, on regarde des blocs de quatre bits, ajoutant un bit de
parité pour la somme de chaque trois sur quatre entre eux :

C(01101110) = 01100110|11101000 = 0110011011101000 ∈ F16

2

Exemple 5. Est-ce qu’on peut faire mieux ? Les paramétres n (longueur), k (dimension)
et d (distance minimum) sont des invariants importants d’un code. Pour des valeurs [n, k]
données on veut maximiser la valeur la distance minimum. On peut montrer que les
paramétres [n, k, d] sont respectivement

1. [16, 8, 2], 2. [16, 12, 2], 3. [16, 8, 2], et 4. [16, 8, 4].

Néanmoins, on peut montrer qu’il existe un code linéaire avec paramétres [16, 8, 5].

Distance de Hamming
Définition. La distance de Hamming est une fonction d : An × An −→ N, définie par

d(x, y) = {i : 1 ≤ i ≤ n, xi 6= yi }

où x = x1 x2 . . . xn et y = y1 y2 . . . yn . La distance minimum d’un codage C : M → An est

d(C) = min ({d(x, y) : x, y ∈ M, x 6= y}) .

et la distance minimum d’un code C ⊆ An est d(C) = min ({d(x, y) : x, y ∈ C, x 6= y}) .

Remarque. Si un codage est sans pertes on a donc d(C) = d(C(M)), sinon d(C) = 0.
Propriétés.

1. La distance de Hamming satisfait l’inégalité triangulaire d(x, y) ≤ d(x, z) + d(z, y)

pour tout x, y, et z ∈ An .
2. Ensemble avec les autres propriétés évidentes : de symétrie (d(x, y) = d(y, x)) et de
séparation (d(x, y) = 0 si et seulement si x = y), la distance de Hamming est, en
effet, une distance sur An .
3. Si A est un anneau (e.g. A = Fq ) alors la distance est linéaire :

d(x + z, y + z) = d(x, y).

Dans ce cas, il existe un élémement distingué 0 de A, et on définit le support d’un

élément x ∈ An d’être les indices des coordonnées non nuls :

Supp(x) = {i : 1 ≤ i ≤ n, xi 6= 0}

et le poids d’étre son cardinal : ||x|| = d(x, 0) = |Supp(x)| où 0 ∈ An est le mot des
zéros de longueur n.
4. Par conséquent de linéarité, si C est un code linéaire (satisfaisant ax + by ∈ C pour
tous a, b ∈ A et x, y ∈ C), on a d(C) = min ({||x|| : x ∈ C}) .

La distance de Hamming permet de définir des boules et sphères comme pour tout
espace métrique.
Définition. La boule de rayon t autour de x ∈ An est

B(x, t) = {y ∈ An : d(x, y) ≤ t},

et la sphère de rayon t est

S(x, t) = {y ∈ An : d(x, y) = t}.

Par conséquent, la boule B(x, t) est l’union disjointe des sphères S(x, i) pour 0 ≤ i ≤ t.
On peut également définir une boule (ou voisinage) de rayon t autour de C ⊂ An :
[
B(C, t) = B(x, t).
x∈C

Attention. Malgré le fait que d(x, y) est une vraie distance, la structure des boules est
potentiellement contre-intuitive : Si A = Fq , l’espace An est un espace vectoriel, dans
lequel la boule B(x, 1) est l’union des droites affines parallèles aux axes de Fnq passant par
x, la boule B(x, 2) est une union de plans, etc.
Exemple. Soit C = {c0 , c1 , c2 , c3 } = {0000, 10110, 01011, 11101} ⊂ F52 . En tabulant les
distances entre mots de code :
d(x, y) c0 c1 c2 c3
c0 0 3 3 4
c1 3 0 4 3
c2 3 4 0 3
c3 4 3 3 0

on trouve que la distance minimum est 3. Or, en vérifiant que le code est linéaire (du fait
que c3 = c1 + c2 ) il suffit de calculer les poids des trois éléments non nuls :


||c1 ||, ||c2 ||, ||c3 || = (3, 3, 4).

Codes linéaires
Si A = Fq , on dit que C ⊆ An = Fnq est un code linéaire si C est un sous-espace
vectoriel. La dimension de C est sa dimension en tant qu’espace vectoriel, déterminée par
la relation |C| = q k . Pour un code en bloc dans An pour le préciser en général il faut
l’énumération des ces éléments, mais un code linéaire est déterminé par une base de k
éléments. La détermination de la distance minimum d’un code coût plus cher, mais on a
vu que l’algorithme naïf se réduit au calcul de |C|(|C| − 1)/2 distances à |C| − 1 poids pour
un code linéaire.
Par un choix de base de C, un code linéaire est donc l’image d’un codage C : Fkq → Fnq .
Une matrice G dont les lignes forment une base s’appelle une matrice génératrice de C.
Le codage est donné par C(x) = x.G.
On peut préciser C comme noyau d’une transformation linéaire : π : Fnq → Fn−kq . La
t
matrice H d’une telle transformation, telle que π(c) = c.H , s’appelle une matrice de
contrôle (ou matrice de parité). Les lignes de H forment une base du code dual C ⊥ de C,
de dimension n − k, tel que hC, C ⊥ i = 0. On a donc une suite exacte
C π
0 −→ Fkq −→ Fnq −→ Fn−k
q −→ 0.
Un élément de l’image de π s’appelle un syndrôme, qui measure l’erreur par rapport à
un mot de code : si r = c + e est un mot de Fnq , avec c ∈ C, le vecteur e est un vecteur
d’erreur par rapport à c et le syndrôme s = π(r) = π(e), ne dépend que de e.
La matrice génératrice G est en forme systématique si G = [ Ik | P ] , pour une matrice
P de k × (n − k), telle que l’application Fkq → Fnq , est donnée par l’identité sur les k
premières coordonnées :

x1 x2 . . . xk 7−→ x1 x2 . . . xk . . . nn .

On peut construire une matrice de contrôle H = [ −P t | In−k ], telle que

G.H t = Ik .(−P ) + P.In−k = −P + P = 0.

Pour un codage linéaire en forme systématique, l’opération de codage comporte le pro-

longement d’un vecteur par l’ajout de caractères nouveaux. Le décodage d’un mot de
code (sans erreur) est particulièrement façile : il suffit de projécter sur les premiers k
caracterères.
Néanmoins, en générale l’inversion du codage (sans pertes) C : M → An , restreint
à son image C, est une application D : C → M bijective, efficace et transparente. Par
décodage, on cherche à prolonger D à un voisinage B(C, t) de C, quitte à le prolonger à
l’espace ambient An entier :
D
An 99K C −→ M.
Comme l’application D est une bijection, on se focalise sur la fonction An 99K C.

Décodage : correction et détection d’erreurs

Soit C ⊂ An un code, c ∈ C un mot transmis lors d’une communication sur un canal
bruyant et soit r ∈ An le mot reçu. On veut dévélopper des conditions pour lesquelles on
peut identifier c comme le mot de code plus proche et conditions pour lesquelles on peut
détecter que r contient trop d’erreurs pour être corrigé.
Supposer que |A| = q et x ∈ An . On note que le cardinal |B(x, t)| ne dépend que de
q, n et t, et on ne note V (q, n, t). En particulier, on a l’égalité
t t  
X X n
V (q, n, t) = |S(x, i)| = (q − 1)i .
i=0 i=0
i

Définition. On dit qu’un code C est s-détecteur si B(c, s) ∩ C = {c} pour tout c ∈ C, et
que C est t-correcteur (d’erreurs) si les boules de rayon t autour de mots distincts de C
sont disjointes.
Remarque. On en déduit qu’un code est s-détecteur si est seulement si d(C) ≥ s + 1, et
que C est t-correcteur d’erreurs, si est seulement si d(C) ≥ 2t + 1, si est seulement si

|B(C, t)| = |C|V (q, n, t).

Cette dernière relation est l’expression que B(C, t) est l’union disjointes des boules B(c, t).
Stratégies de décodage
On suppose que C ⊂ An est un code, d(C) sa distance minimum et s, t ∈ N tels que
d(C) = 2t + s + 1. Il suit que C est t-correcteur.
Stratégie détection maximale. Cette strategie consiste à identifier l’existence d’erreurs
de transmission si le mot reçu r ∈
/ C, sans tentative de correction d’erreurs. En cas d’erreur
détectée, cette stratégie peut être couplé avec une demande de retransmission.
Analyse. On suppose que C est maximal s-détecteur, d(C) = s + 1, avec t = 0. Si
d(c, r) ≤ s, le mot erroné r 6= c est détecté, mais si d(c, r) > s on peut recevoir un mot
erroné r ∈ C différent de c, sans détection d’erreur.
Stratégie correction maximale. On pose t = b(d(C) − 1)/2c, la valeur maximale telle
que C est t-correcteur. On associe l’unique mot de code c0 le plus proche à r, dans une
boule de rayon t, sinon on signale une erreur.
Analyse. On a d(C) = 2t + s + 1 avec s = 0 si d(C) est impair et s = 1 si d(C) est pair.
S’il y a au maximum t erreurs, on corrige r à c0 = c car B(c, t) est la seule boule de rayon
t qui contient r. Si d(C) = 2t + 2, et il y a exactement t + 1 = s + t erreurs, on peut
détecter l’existence d’au moins t + 1 erreurs, mais il peut y avoir plusieurs mots de code
c0 à distance t + 1 de r.
Stratégie t-correction (hybride). S’il existe c0 ∈ C avec d(c0 , r) ≤ t, on retourne c0 .
Sinon, on signale une erreur.
Analyse. On suppose que d(C) = 2t + s + 1 ; si d(c, r) ≤ t, le résultat du décodage est
le mot c0 = c, par l’unicité de la boule B(c, t) qui contient r. Si le nombre d’erreurs est
entre t + 1 et s + t, la transmission erroneé est détectée. Si B(C, s + t) ( An , il existe des
erreurs supplémentaires, avec d(c, r) > s + t, qui peuvent être détectées. Or, en depassant
s + t certains mots reçus r passent dans B(c0 , t) avec c 6= c0 ∈ C.
Remarque. La stratégié hybride permet une interpolation entre la stratégie de détection
maximale et de correction maximale, avec le choix de t satisfaisant d(C) = 2t + s + 1.

Bornes de Singleton et Hamming

On suppose dans la suite que C est un code en bloc dans An , avec q = A, mais sans
hypothèse que A soit un anneau, ni que C soit linéare. Si le code est linéaire, l’invariant
k signifie sa dimension, un entier, sinon on pose k = logq (|C|). L’objectif des bornes sur
les paramétres est de déterminer des contraintes entre les paramétres [n, k, d] dans An .
Théorème (Singleton). Si C ⊆ An est un code avec d = d(C), alors |C| ≤ q n−d+1 .

Définition. Si k = logq (|C|) = n − d + 1, on dit que C est MDS (pour maximum distance
separable en anglais).
Preuve. Soit π : An → An−d+1 la projection π(x1 x2 . . . xn ) = x1 x2 . . . xn−d+1 , sur les
premiers n − d + 1 coordonnées. La restriction à C est injective, car π(x) = π(y) si et
seulement si x = y car d(x, y) ≤ d − 1. Il suit que |C| = |π(C)| ≤ |An−d+1 | = q n−d+1 .
Exemple. Soit C = h1001, 0101, 0011i le code linéaire dans F42 . On observe que tout mot
de code est de poids pair — c’est le code définit par x1 + x2 + x3 + x4 = 0 – donc la
distance minimum d est pair et majoré par 2, donc d = 2. La dimension est k = 3, alors
[n, k, d] = [4, 3, 2]. Il suit que C est MDS car k = n − d + 1 = 3.

On rappelle la forme du cardinal d’une boule autoru de x ∈ An .

t  
X n
V (q, n, t) = |B(x, t)| = (q − 1)i .
i=0
i

Le théorème suivant énonce une majoration impliquée par la couverture disjointes de C

par des boules de rayon t.

Théorème (Hamming). Si C ⊆ An est un code t-correcteur avec d = d(C), alors

|C|V (q, n, t) ≤ q n .

Preuve. Les boules de rayon t sont disjointes, alors

X
q n = |An | ≥ |B(C, t)| = |B(c, t)| = |C|V (q, n, t).
c∈C

Définition. Un code qui satisfait |C| = q n /V (q, n, t) s’appelle parfait.

logq (V (q, n, t))
Corollaire. Le taux de transmission de C est au maximum 1 − ·
n

logq (C) logq (q n /V (q, n, t))

Preuve. Par définition R = ≤ ·
n n

Canal binaire symétrique

Définition. Un canal binaire symétrique est un modèle probabiliste pour un canal discret
de transmission avec bruit. On suppose que le canal transmet des suites de bits (des
0 et 1) avec probabilité ε qu’un bit soit changé – de 0 en 1 ou 1 en 0 avec la même
probabilité (propriété symétrique). On dit que le canal est sans mémoire si le probabilité
de changement est indépendant en position (ou temps) i et j 6= i.
On étudie un exemple de code linéaire C dans Fn2 , en regardant les propriétés de couver-
ture par des boules, et le lien avec la correction et détection d’erreurs après transmission
par un canal binaire symétrique sans mémoire.
Exemple. Soit C le code linéaire de dimension 2 dans F62 :

h101010, 010101i = {000000, 101010, 010101, 111111}.

En regardant les poids des éléments, on détermine que le code est de distance minimum
3, alors 1-correcteur. On a alors
B(C, 1) = 4(1 + 6) = 28 < |F62 | = 64,
et on peut montrer que B(C, 2) = 64.
Supposons qu’on utilise ce code pour transmission sur un canal binaire symétrique
sans mémoire, avec probabilité d’erreur ε. Si c est le mot de code transmis, et r le mot
reçu, on peut tabuler les probabilités des distances d(c, r).
d(c, r) num prob notes
0 1 (1 − ε)6 o
r ∈ B(c, 1)
1 6 6(1 − ε)5 ε1
2 15 15(1 − ε)4 ε2 dont 6 dans B(C, 1)
3 20 20(1 − ε)3 ε3 dont 2 dans C
4 15 15(1 − ε)2 ε4 dont 6 dans B(C, 1)
5 6 6(1 − ε)1 ε5 o
r ∈ B(c + 111111, 1)
6 1 ε6
Total : 64 1

Analyse. Avec une stratégie de 1-correction, la probabilité de transmission correcte est

(1 − ε)6 + 6(1 − ε)5 ε ∼ 1 − 15ε2 .
Or il y a 28 mots dans B(C, 1), dont seulement 7 sont correctement corrigés. Les autres
21 seront corrigés vers le mauvais mot de code, avec probabilité totale
6(1 − ε)4 ε2 + 2(1 − ε)3 ε3 + 6(1 − ε)2 ε4 + 6(1 − ε)1 ε5 + ε6 ∼ 6ε2 .
Les 36 mots restants sont détectables comme erronés, constituant une probabilité totale :
9(1 − ε)4 ε2 + 18(1 − ε)3 ε3 + 9(1 − ε)2 ε4 ∼ 9ε2 .
Les équivalences de la forme f (ε) ∼ g(ε) sont dans le voisinage de ε = 0. On aperçoit
qu’environs 60% des erreurs non corrigés sont des erreurs détectés et et 40% sont mal
corrigés.
Détection seule. Avec une stratégie de détection (0-correction), on obtient les probabi-
lités respectives de bonne correction :
(1 − ε)6 ∼ 1 − 6ε,
de détection :
6(1 − ε)5 ε1 + 15(1 − ε)4 ε2 + 18(1 − ε)3 ε3 + 15(1 − ε)2 ε4 ∼ 6ε,
et de correction erronée :
2(1 − ε)3 ε3 + ε6 ∼ 2ε3 .
En particulier la probabilité d’une correction erronée dévient négligeable, O(ε3 ), par rap-
port à détection O(ε) dans le voisinage de ε = 0.
Codes de Hamming
On rappelle que le code de Hamming de paramétre r ≥ 2 est un code linéaire Hr ⊂ Fn2
de longeur n = 2r − 1 et dimension k = n − r, ayant pour matrice de contrôle une matrice
H(r) de r lignes et n colonnes dont toutes les colonnes sont distinctes et non nulles.
Autrement dit, les lignes de H(r)t parcourrent les éléments non nuls de Fr2 . À équivalence
près, on peut supposer que le i-ième ligne de H(r)t représente l’écriture de l’entier i en
binaire.
Exemple. Les premières matrices de contrôle d’un code de Hamming sont :

1 2 3 4 5 6 7
1 2 3  1 0 1 0 1 0 1
1 0 1
H(2) = et H(3) = 0 1 1 0 0 1 1 ·

0 1 1
0 0 0 1 1 1 1

et on peut contruire les matrices de contrôle d’ordre supérieur de manière récursive de la

forme :  
0
 .. 
H(r + 1) =  H(r) . H(r)  ·

 0 
0 ··· 0 1 1 ··· 1
D’autres présentations des codes de Hamming sont possibles, en écrivant la matrice gé-
nétrice et matrice de contrôle en forme systématique. Or, cette formulation permet un
décodage intuitif par syndrôme (voir la suite).
Les paramétres du code de Hamming sont [n, n − r, 3], où n = 2r − 1, par conséquent
du lemme suivant, les premiers paramétres sont [3, 1, 3], [7, 4, 3], et [15, 11, 3].
Lemme. Un code de Hamming est de distance minimum 3.

Preuve. On note qu’un code binaire avec matrice de contrôle H est l’ensemble de vectors

C = {c ∈ Fn2 : c.H t = 0}.

On fait quelques observations concernant le rapport entre la distance minimum et la

matrice de contrôle.

• Un code C est de distance 1 si et seulement s’il existe une colonne toute nulle dans la
matrice de contrôle, car d(C) = 1 si est seulement un des vecteurs de la base canonique,

ei = 0 · · · 010 · · · 0,

est dans C. Or, ei .H t ∈ Fr2 \{0} est la i-ième ligne de H t .

• Un code C a distance minimum 2 si d(C) 6= 1 et la somme de deux colonnes de H
est nulle, et, sur F2 , si est seulement si deux colonnes sont égaux. On utilise le même
argument : la distance minimum est 2 si est seulement si c = ei + ej ∈ C, et, c.H t est
la sommes des i-ième et j-ième lignes de H t .
• Par la suite, on voit que la distance minimum est au maximum d si et seulement si un
combinaison linéaire (une somme sur F2 ) de d colonnes de H est le vecteur nul.

On rappelle que les lignes de H(r)t parcourrent les vecteurs de Fr2 \{0}. Alors par définition
de H(r), aucune colonne est nulle et aucun pair de colonnes sont égalles. Or, pour tout
pair de colonnes leur somme est encore une colonne de H(r) (par clôture d’addition sur
l’espace vectoriel Frq ). Il suit que la distance minimum est 3.
Les codes de Hamming ont asymptotiquement un très haut rendement (après les pre-
miers petits exemples), R = (n − r)/n où n = 2r − 1, même si les et faible correction,
étant 1-correcteurs. Les paramètres des premiers codes de Hamming sont

r n k d R r n k d R
2 3 1 3 1/3 = 0,3333 . . . 5 31 26 3 26/31 = 0,8387 . . .
3 7 4 3 4/7 = 0,5714 . . . 6 63 57 3 19/21 = 0,9047 . . .
4 15 11 3 11/15 = 0,7333 . . . 7 127 120 3 120/127 = 0,9448 . . .

On peut construire des matrices génératrices pour ces premier codes. La matrice H(2) est
 
1 0 1
H(2) =
0 1 1
 
alors, on trouve une matrice génératrice G(2) = 1 1 1 , engendré par le mot de code de
triple répétition. De même, à partir de la matrice H(3) on trouve une matrice G(3)
 
  1 0 0 0 0 1 1
1 0 1 0 1 0 1 0 1 0 0 1 0 1
H(3) =  0 1 1 0 0 1 1  on trouve G(3) =  0 0 1 0 1 1 0

0 0 0 1 1 1 1
0 0 0 1 1 1 1

une matrice génératrice en forme systématique pour le [7, 4, 3]-code de Hamming.

Finalement, on conclure cette section avec le résultat qui montre un des intérêts prin-
cipaux pour les codes de Hamming, à la fois théorique et pratique.

Théorème. Les codes de Hamming sont parfaits.

Preuve. Le code Hr de Hamming, avec paramétres [n, k, d] = [2r − 1, n − r, 3] est un code

1-correcteur, donc

|B(Hr , 1)| = |Hr |V (q, n, 1) = 2n−r (1 + n) = 2n−r 2r = 2n ,

alors Hr est parfait.

Il suit qu’il y a un algorithme efficace pour décodage An → C, qui permet de calculer le

mot de code unique à distance 1 maximum associé à tout mot reçu r ∈ An .
Décodage par syndrôme
Les codes de Hamming sont particulièrement bien adaptés à l’algorithme de décodage
nommé décodage par syndrôme. Il y a deux étapes : la construction d’une table des
syndrômes associés aux vecteurs d’erreurs de petits poids, et décodage par recherche de
syndrôme dans la table pour trouver le vecteur d’erreur.
Le décodage par syndrôme d’un code linéaire C à paramétres [n, k, d] est une méthode
efficace 1) quand n − k est petit — tel qu’on peut énumérer les q n−k syndrômes de Fqn−k –
ou 2) quand on veut décoder à faible distance t — tel qu’on peut énumérer les V (q, n, t)
éléments de la boule B(0, t). On effectue le décodage en utisant une table précalculée de
couples (s, e) d’un syndrôme s = π(e) avec vector d’erreur e, de poids ||e|| ≤ t dans B(0, t).
On rappelle que le homomorphisme π : Fnq → Fqn−k associe le syndrôme s = π(r) à un
mot reçu r ∈ Fnq , et que π(c) = 0 pour tout mot de code c ∈ C. Si le mot reçu est de la
forme r = c + e, pour un mot trans c ∈ C et erreur e ∈ Fnq , on observe que le syndrôme
π(r) ne dépend que de la classe d’équivalence Fnq /C, et en particulier π(r) = π(e). Un
leader de classe est un mot e de poids minimal dans la class r + C. La correction du mot
reçu est effectuée en mettant c0 = r − e où e est un leader de classe de r + C.
Si 2t+1 ≤ d(C) et ||e|| ≤ t, alors e est un leader de classe. L’idée est donc de précalculer
chaque syndrôme s = π(e) des vecteurs d’erreurs e de poids 1 jusqu’à t, en mettant le
pair (s, e) dans un tableau standard, une dictionnaire de recherche de leader de classe par
syndrôme.
Exemple. Le tableau standard pour le [7, 4, 3]-code H3 de Hamming, est la suivante :
{(001, e1 ), (010, e2 ), (011, e3 ), (010, e4 ), (101, e5 ), (110, e6 ), (111, e7 )},
où ei est le i-ième vecteur de la base canonique de F72 . Par construction de l’ordre des
colonnes de H(r), le syndrôme du vecteur canonique ei est l’écriture d’entier i en binaire.

Exercices
1. Soit C le code engendré par la matrice
 
1 1 1 0 1 1
0 1 0 0 1 1
G= 1 0
.
1 1 0 1
0 1 1 1 0 1
a. Déterminer le nombre de mots de code de C.
b. Calculer une matrice de contrôle.
c. Calculer la distance minimum de C.
d. Déterminer le nombre d’erreurs que C peut détecter/corriger.
2. Soit C le code avec matrice de contrôle
 
1 1 1 0 0
H = 0 1 0 1 0 .
1 0 0 0 1
 a. Donner une matrice génératrice pour C.
b. Décoder par syndrome r = 11101 et r0 = 11011.
3. On appelle code de Hamming de paramètre r ≥ 2 un code binaire de longueur
2r − 1 et dimension 2r − r − 1 ayant pour matrice de contrôle une matrice H(r)
de r lignes et 2r − 1 colonnes dont toutes les colonnes sont distinctes et non nulle.
A équivalence (isomorphisme) près on peut supposer que la i-ème colonne de H(r)
représente l’écriture binaire de l’entier i.
a. Construire H(2) et H(3).
b. Donner une matrice génératrice pour ces codes.
c. Montrer que les codes de Hamming sont de distance 3.
d. Montrer que ce sont des codes parfaits, en particulier l’union des boules de
rayon t = 1 centré sur un mot du code est égale à Fn2 .
e. Montrer qu’un code de Hamming est MDS si et seulement si r = 2.
f. Ces codes sont très faciles à décoder : montrer qu’on peut choisir pour leader
de classe un mot ayant un seul 1 à la place i pour les 2r −1 classes non triviales.
4. Montrer que le code binaire de répétition de longueur n (code linéaire avec G =
[1, 1, . . . , 1]) est un code MDS, et si n = d = 2t + 1, il est parfait.
5. Remplir les valeurs de V (2, n, t) dans le tableau suivant :
t 0 1 2 3 4 5 6 7
V (2, 2, t)
V (2, 3, t)
V (2, 4, t)
V (2, 5, t)
V (2, 6, t)
V (2, 7, t)
Pour quelles valeurs [n, k, d] ci-dessus est-ce qu’il peut exister un codage linéaire en
bloc parfait ?
6. Soit Ci : X → {0, 1}n les codages linéaires avec matrices génératrices
 
    1 0 0 0 1 1 0
110001 110011 0100011
G1 = , G2 =  0 0 1 0 1 1 1 ·
, et G3 =  
001110 001111
0001101
Rappelons que pour chaque x dans An où |A| = q, et entier t, le cardinal de la boule
B(x, t) est
t  
X n
|B(x, t)| = V (q, n, t) = (q − 1)i .
i=0
i
a. Trouver les paramètres [n, k, d] pour chaque code, vérifier les bornes de Single-
ton et Hamming.
b. Pour chaque code Ci et t entre 0 et 2, compter |B(Ci , t)|, le nombre de mots à
distance t d’un mot de code.