Université Paris 8

A.A. 2021–2022

Introduction à la théorie des codes

Martino Borello

2 septembre 2021
2
Table des matières

Introduction 5

1 Premières notions sur les codes 7

1.1 Exemples historiques . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.1 Le code de parité . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.2 Le code de répétition . . . . . . . . . . . . . . . . . . . . . 8
1.1.3 Le premier code de Hamming : le code « carré » . . . . . 9
1.2 La métrique de Hamming . . . . . . . . . . . . . . . . . . . . . . 10

2 Codes linéaires 13
2.1 Définitions et propriétés de base . . . . . . . . . . . . . . . . . . 13
2.2 Matrice de parité et code dual . . . . . . . . . . . . . . . . . . . . 15
2.3 Borne de Singleton et codes MDS . . . . . . . . . . . . . . . . . . 18
2.4 Distribution des poids . . . . . . . . . . . . . . . . . . . . . . . . 19
2.5 Équivalence de codes . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.6 Décodage par syndrome . . . . . . . . . . . . . . . . . . . . . . . 22
2.7 Extensions des codes . . . . . . . . . . . . . . . . . . . . . . . . . 23

3 Familles de codes linéaires remarquables 25

3.1 Codes de Hamming et codes simplexes . . . . . . . . . . . . . . . 25
3.2 Codes de Reed-Muller . . . . . . . . . . . . . . . . . . . . . . . . 27
3.3 Codes de Golay binaires . . . . . . . . . . . . . . . . . . . . . . . 31

4 Exercices avec correction 33

Bibliographie 45

3
4 TABLE DES MATIÈRES
Introduction

Si quelqu’un nous dit « Il faut canger ! », nous nous rendons immédiatement

compte qu’il y a une erreur dans la phrase, car « canger » ne veut rien dire.
Si nous essayons d’imaginer ce qu’on nous a dit, nous pensons naturellement à
« Il faut manger ! », « Il faut changer ! » ou encore à « Il faut ranger ! ». Aucun
d’entre nous ne pense à quelque chose comme « Il veut penser ! », car c’est
trop loin de ce qu’on a entendu. Notre cerveau recherche donc naturellement
une phrase sensée qui soit la plus proche possible de la phrase que nous avons
entendu, pour corriger l’erreur.
Malheureusement, comme il y a tant de phrases proches de celle que nous
avons entendue, nous restons dans l’incertitude et, pour l’éliminer, nous devons
demander des informations supplémentaires. Une possibilité très naturelle
est de demander à notre interlocuteur de répéter ce qu’il a dit. Nous pouvons
également lui demander « Quoi ? » et si on reçoit comme réponse « La pomme. »,
on peut facilement imaginer que la première partie de la phrase aurait du être
« Il faut manger ! ». En tout état de cause, la correction de l’erreur a un coût,
c’est-à-dire qu’elle nécessite l’ajout d’informations.
Erreur, détection, proximité entre les mots, correction, ajout d’informations,
répétition : ces concepts qui font en quelque sorte partie de notre vie quotidienne
sont à la base de la théorie des codes, comme nous le verrons dans la suite.
Quelle est la cause de l’erreur ? Ce que nous appellerons le bruit. Concrète-
ment, on peut imaginer le bruit comme une interférence dans notre appel télé-
phonique, comme une rayure sur notre CD, comme une tache sur notre livre...
ou vraiment, comme un bruit qui nous empêche d’entendre notre ami qui dis-
cute bien avec nous ! Pour Richard Hamming (1915-1998), l’erreur était un
trou bâclé dans les feuilles qu’il insérait dans l’ordinateur modèle V pendant les
week-ends, dans les Laboratoires Bells aux États-Unis. Chaque fois que l’ordi-
nateur découvrait une erreur dans l’entrée, il abandonnait simplement le travail.

« Deux week-ends de suite, je suis arrivé et j’ai trouvé qu’une erreur était
survenue et rien n’avait été fait. J’était vraiment en colère et agacé parce que
je voulais ces réponses et deux week-ends avaient été perdus. Et alors j’ai dit
« Bon sang, si la machine peut détecter une erreur, pourquoi ne peut-elle pas
localiser la position de l’erreur et la corriger ? ». »

(R. Hamming)

5
6 TABLE DES MATIÈRES

L’objet principal de ce cours seront les codes correcteurs d’erreurs, c’est-

à-dire la solution que R. Hamming a proposé dans les années 40 pour résoudre
son problème avec l’ordinateur. Ils sont encore utilisés aujourd’hui dans toutes
sortes de communications (téléphone, réseaux, clés USB, satellites, sondes spa-
tiales...).
Un autre pionnier dans la domaine (lui aussi aux Laboratoires Bells) a été
Claude Shannon (1916-2001), qui a jeté les bases mathématiques de la théo-
rie des codes et de l’information avec son article A Mathematical Theory of
Communication. Célèbre est maintenant son schéma suivant, présenté dans cet
article, que nous examinerons en détail dans le cours.

Figure 1 –

Enfin, il convient également de rappeler Marcel Golay (1902-1989), un col-

lègue des deux chercheurs mentionnés ci-dessus, qui a contribué à l’élaboration
de la théorie des codes (dont certains portent son nom).
De nombreux autres mathématiciens, ingénieurs et informaticiens continuent
à développer ce domaine de recherche encore aujourd’hui. Ce cours se veut une
introduction à ses concepts fondamentaux.
Chapitre 1

Premières notions sur les

codes

Tout d’abord, on veut mentionner deux type de codage qui existent, c’est-
à-dire le codage convolutif, qui traite l’un après l’autre les symboles d’un
message de n’importe quelle longueur, et le codage par bloc, qui traite « en
bloc » des messages avec un nombre fixe de symboles. Dans ce cours, on va
considérer seulement le deuxième type de codage, qui est plus simple à dévelop-
per. Notons que, dans ce cas, un message de n’importe quelle longueur est coupé
en plusieurs blocs de la même longueur et chaque bloc est traité séparément.

Soit A un ensemble, dit alphabet. Dans le schéma en Figure 1, on a la

situation suivante (qui sera notre configuration de base dorénavant) :
• la source émet une séquence de k éléments u := (u1 , . . . , uk ) ∈ Ak , dit
message ;
• l’encodeur transforme (on verra comment) cette séquence en une sé-
quence de n éléments x := (x1 , . . . , xn ) ∈ An , avec n ≥ k, qui s’appelle
mot de code de longueur n ;
• le bruit transforme ce mot de code en un autre y := (y1 , . . . , yn ) ∈ An ,
de la même longueur, qui est le mot avec erreur ;
• le but (pas toujours possible) du décodeur est de reconstituer x à partir
de y, c’est-à-dire corriger l’erreur. Avec x on peut facilement reconstituer
le message u.
Définition 1.1. L’ensemble des mots de code, c’est-à-dire l’ensemble de sé-
quences qui sortent de l’encodeur, s’appelle justement code. Un code de lon-
gueur n sur A est un sous-ensemble de An .
On a donc qu’un code est un objet, tandis que le codage est la « transfor-
mation » operée par l’encodeur. Ces termes sont souvent confus.
Définition 1.2. Le nombre k/n est dit taux de transmission et l’entier
r = n − k est dit redondance.

7
8 CHAPITRE 1. PREMIÈRES NOTIONS SUR LES CODES

Les deux sont une manière de quantifier l’information qu’on doit ajouter
pour permettre la correction de l’erreur. Idéalement, on voudrait un taux de
transmission grande ou une redondance petite, mais cela - on verra - n’est pas
forcement compatible avec la capacité de corriger l’erreur.
On peut toujours supposer que la transformation opérée par l’encodeur
consiste à ajouter (on verra comment) des éléments à la séquence u émise
par la source (pas forcement après). Donc on peut retrouver u à l’intérieur de
x. Dans ce cas, on appelle bits d’information ceux de u et bits de contrôle
ceux qu’on a ajouté.
Définition 1.3. Un codage est dit systématique (ou lisible) quand les bits de
contrôle sont regroupés à la fin du mot de code, c’est à dire quand x = (u| . . .).

1.1 Exemples historiques

1.1.1 Le code de parité
Soit k un entier positif et A = {0, 1}. La source émet (u1 , . . . , uk ) et l’enco-
deur le transforme en
x := (u1 , . . . , uk , u1 + · · · + uk mod 2),
c’est-à-dire il ajoute un bit de contrôle, dit aussi de parité. De cette manière,
tout mot de code a un nombre pair de 1. Ce codage est systématique.
Le décodeur reçoit le mot y, qui est égal à x avec des éléments éventuellement
changés par le bruit. Si un nombre impair d’éléments a changé, le décodeur peut
détecter l’erreur, car il constate qu’il y a un nombre impair de 1. Autrement, il
ne peut rien dire. Ce code ne peut pas corriger l’erreur, car il n’est pas capable
de le localiser.
Exemple 1.1. La source envoie u = (1, 0, 1, 0, 1) (ici k = 5), l’encodeur le
transforme en x = (1, 0, 1, 0, 1, 1). Le bruit change le quatrième élément, de ma-
nière que y = (1, 0, 1, 1, 1, 1). Le décodeur reçoit y et il constate qu’il y a cinq 1 :
il y a eu une erreur ! Mais en connaissant seulement y, il est impossible de loca-
liser l’erreur produit pas le bruit, car il peut être survenu n’importe où. Notons
que si le bruit change deux éléments, par exemple le quatrième et le cinquième,
de manière que y = (1, 0, 1, 1, 0, 1), le décodeur ne détecte pas l’erreur.
Exercice 1.1. Écrire la liste des éléments du code de parité pour k = 4.
Notons que le taux de transmission de ce code est (k + 1)/k et sa redondance
est égale à 1.

1.1.2 Le code de répétition

Soit n un entier positif et A = {0, 1}. La source émet u ∈ A et l’encodeur le
transforme en
x := (u, u, . . . , u),
| {z }
n fois
1.1. EXEMPLES HISTORIQUES 9

c’est-à-dire il répète n fois l’élément émis. Ce codage est systématique.

Le décodeur reçoit le mot y, qui est égal à x avec des éléments éventuellement
changés par le bruit. Il utilise un décodage « majoritaire », c’est-à-dire il donne
au destinataire la valeur qui apparaît le plus de fois (si le nombre de 1 est égale à
celui des 0, le décodeur ne peut rien faire). Bien évidemment, il n’est pas certain
que l’information reçue par le destinataire soit celle émise par la source. Cela
dépend du nombre d’erreurs : si ce nombre est inférieur à n/2, alors le décodeur
donne la bonne valeur, autrement non.
Exemple 1.2. La source envoie u = 1, l’encodeur le transforme en x =
(1, 1, 1, 1, 1, 1) (ici n = 6). Le bruit change le quatrième élément, de manière
que y = (1, 1, 1, 0, 1, 1). Le décodeur reçoit y et il constate qu’il y a cinq 1 et
un seul 0, donc il donne 1 au destinataire. Notons que si le bruit change trois
éléments le décodeur ne peut rien faire, tandis que si le bruit change plus de
trois éléments, le décodeur donne 0 au destinataire, qui n’est pas l’information
émise par la source.
Exercice 1.2. Écrire la liste des éléments du code de parité pour n = 5.
Notons que le taux de transmission de ce code est 1/n et sa redondance est
égale à n − 1.

1.1.3 Le premier code de Hamming : le code « carré »

Soit A = {0, 1}. La source émet u := (u1 , u2 , u3 , u4 ) et l’encodeur le trans-
forme en
x := (u1 , u2 , u1 + u2 , u3 , u4 , u3 + u4 , u1 + u3 , u2 + u4 , u1 + u2 + u3 + u4 ).
où les sommes sont considérées modulo 2. On peut le visualiser plus facilement
avec un carré :
u1 u2 u1 + u2 mod 2
u3 u4 u3 + u4 mod 2
u1 + u3 mod 2 u2 + u4 mod 2 u1 + u2 + u3 + u4 mod 2
qu’on doit déplier pour obtenir x. Notons qu’on l’encodeur ajoute donc un bit
de parité à toute ligne et toute colonne du carré formé par u. Ce codage (tel
qu’on l’a décrit) n’est pas systématique.
Ce code est capable de corriger une erreur : le décodeur reçoit le mot y, qui
est égal à x avec un seul élément changé par le bruit. En regardant la parité
des 1 sur toute ligne et sur toute colonne, le décodeur trouve la seule ligne et
la seule colonne où il y a un nombre impair de 1. L’élément à changer est donc
celui qui est à la ligne et colonne trouvées.
Exemple 1.3. La source envoie u = (1, 0, 1, 1), l’encodeur utilise le carré pour
ajouter les bits de parité
1 0 1
1 1 0
0 1 1
10 CHAPITRE 1. PREMIÈRES NOTIONS SUR LES CODES

et il déplie le carré pour obtenir x = (1, 0, 1, 1, 1, 0, 0, 1, 1). Le bruit change le

quatrième élément, de manière que y = (1, 0, 1, 0, 1, 0, 0, 1, 1). Le décodeur reçoit
y et il utilise encore une fois le carré, en pliant d’abord y

1 0 1
0 1 0
0 1 1

et en remarquant que dans la deuxième ligne et dans la première colonne il y a

un nombre impair de 1, de manière que l’erreur est à la quatrième position de
y.
Exercice 1.3. Écrire la liste des éléments du « code carré ».
Notons que le taux de transmission de ce code est 4/9 et sa redondance est
égale à 5.
Exercice 1.4. Peut ce code corriger plus d’une erreur ?
Exercice 1.5. En analogie au « code carré », construire un code avec k = 9 et
n = 16. Combien d’erreurs peut-il corriger ? Peut-on généraliser cette construc-
tion ?

1.2 La métrique de Hamming

Dans l’ensemble An on peut définir une métrique.
Définition 1.4. Soient a, b ∈ An . La distance de Hamming de a à b est

d(a, b) := #{i | ai 6= bi }.

Remarque 1.1. Attention : la distance de Hamming n’est pas le nombre des

symboles différents entre deux mots, mais le nombre des positionnes des lettres
où les deux mots diffèrent. Exemple : « range » et « nager » ont globalement
les mêmes symboles, mais leur distance de Hamming est 4, car ils diffèrent à la
première, troisième, quatrième et cinquième position.
Exercice 1.6. Montrer que la distance de Hamming est une distance (c’est-à-
dire elle est positive, symétriques et elle satisfait l’inégalité triangulaire).
Définition 1.5. Soit C un code. La distance minimale de C est

d(C) := min{d(a, b) | a, b ∈ C , a 6= b}.

Exercice 1.7. Quelle est la distance minimale du code composé par les mots
de longueur 5 de la langue française ? Et des trois codes introduits ci-dessus
(parité, répétition et « carré ») ?
La distance minimale d’un code est liée à sa capacité de détection et correc-
tion des erreurs. Pour le comprendre, il nous faut d’abord un lemme technique.
1.2. LA MÉTRIQUE DE HAMMING 11

Lemme 1.1. Soit B(x, t) := {x0 ∈ An | d(x, x0 ) ≤ t} la boule de rayon t centrée

en x. Alors,
 
d(C) − 1
B(x, t) ∩ B(y, t) = ∅ pour tous x, y ∈ C, x 6= y ⇐⇒ t ≤ .
2
Démonstration. Notons d’abord que

B(x, t) ∩ B(y, t) = ∅ ⇐⇒ d(x, y) > 2t.

En effet,
⇐) si ∃z ∈ B(x, t) ∩ B(y, t), alors d(x, y) ≤ d(x, z) + d(z, y) ≤ 2t ;
⇒) si d(x, y) = s ≤ 2t, soit I := {i | xi 6= yi } et J ⊆ I de cardinalité
bs/2c. Soit z ∈ An tel que zi = xi si i ∈ J, et zi = yi autrement. Alors
d(y, z) = #J = bs/2c ≤ t et d(x, z) = #(I \ J) = s − bs/2c ≤ t. Donc
z ∈ B(x, t) ∩ B(y, t). j k
d(C)−1
Ainsi, si par l’absurde t > 2 , soient x, y ∈ C tels que d(x, y) = d(C).
Or, d(C) ≤ 2t, de manière que B(x, t) ∩ B(y, t) 6= ∅.
Vice versa, si par l’absurde il existe x, y ∈ C, x 6= y, tel que {z} ⊆ B(x, t) ∩
B(y, t), alors d(C) ≤ d(x, y) ≤ d(x, z) + d(z, y) ≤ 2t, ce qui donne une contra-
diction.
Soit maintenant x le mot émis de l’encodeur et y le mot modifié par le bruit.
On dit qu’un code C est t-détecteur si B(x, t) ∩ C = {x} pour tout x ∈
C, de manière que le décodeur est capable de détecter jusqu’à t erreurs. En
effet, le décodeur normalement est capable de tester (on verra comment) si un
vecteur appartient ou pas à C. S’il existe x, x0 dans C, avec x 6= x0 tel que
x0 ∈ B(x, t) ∩ C, alors s = d(x, x0 ) ≤ t. Or, si s erreur sur x modifient x en x0 ,
le décodeur ne sera pas capable de détecter l’erreur, car x0 appartient lui aussi
au code C.
On dit qu’un code C est t-correcteur si B(x, t) ∩ B(x0 , t) = ∅ pour tout
x, x0 ∈ C, de manière que le décodeur est capable de corriger jusqu’à t erreurs.
En effet, le décodeur normalement est capable de transformer y dans le mot
le plus proche du code, s’il existe (on verra comment). S’il existe x, x0 dans C,
avec x 6= x0 tel que B(x, t) ∩ B(x0 , t) 6= ∅, alors il existe sûrement un élément
y dans l’intersection dont la distance de x0 est inférieur ou égale à celle de x.
Le décodeur transformera y dans le mot x0 , en se trompant. Cela ne peut pas
arriver si les boules sont disjointes.
Proposition 1.1. Un code C de distance minimale d = d(C) est (d − 1)-
détecteur et d−1
2 -correcteur d’erreurs.
Démonstration. Clairement un code de distance minimale d ne peut pas détecter
d erreur, car si x, x0 ∈ C ont d(x, x0 ) = d, alors {x, x0 } ⊆ B(x, d).
La deuxième affirmation suit directement de la définition et du Lemme 1.1.
La capacité de correction d’un code dépend donc de la possibilité d’avoir des
boules du même rayon (chacune centrée en un mot du code) disjointes. On peut
12 CHAPITRE 1. PREMIÈRES NOTIONS SUR LES CODES

facilement imaginer que cela contraste avec la possibilité d’avoir beaucoup de

boules : si on pense à une boîte qui contient des oranges, plus les oranges sont
grosses, moins elles sont dans la boîte. Cela se traduit avec l’inégalité suivante,
qu’on énonce seulement pour A = {0, 1} (sa généralisation à n’importe quel
alphabet est juste un peu plus technique et elle est laissé par exercice).

Théorème 1.1 (Inégalité

 d−1  de Hamming). Soit C un code dans An , k = log2 (C),
d = d(C) et e = 2 . On a
     
n n n
1+ + + ··· + ≤ 2n−k .
1 2 e

Démonstration. Puisque A = {0, 1}, la distance d’un mot de 0 est simplement

le nombre de 1. Donc
     
n n n
#B(0, e) = 1 + + + ··· + .
1 2 e

Clairement, la cardinalité de toute autre boule de rayon e est la même, par

invariance par translation. Le Lemme 1.1 nous assure que les boules centrées
dans les mots du code sont disjointes. Ainsi
!       
[ n n n
# B(x, e) = #C · 1 + + + ··· + ≤ #An ,
1 2 e
x∈C

d’où l’inégalité de Hamming.

Définition 1.6. Un code C est dit parfait si on a l’égalité dans l’inégalité de
Hamming.
Exercice 1.8. Est-ce que les codes introduits ci-dessus (parité, répétition et
« carré ») sont parfaits ?

Remarque 1.2. Il y a peu de codes parfaits. On en verra une famille dans ce

cours (les codes de Hamming).
Chapitre 2

Codes linéaires

Comme on a remarqué dans les exercices du chapitre précédent, pour calculer

la distance minimal d’un code C ⊆ An de cardinalité M il faut faire, a priori, M
2
calculs de distances (un complexité O(nM 2 )). On peut les réduire en prenant
un alphabet A tel que (A; +) soit un groupe abélien, et en supposant C un
sous-groupe de An . En effet, sous ces hypothèses, on a que

d(a, b) = d(a − b, 0)

pour tout a, b ∈ C et a − b ∈ C, de manière que

d(C) = min{d(a, b) | a, b ∈ C , a 6= b} = min{d(c, 0) | c ∈ C, c 6= 0}, (2.1)

qui réduit la complexité à O(nM ) (on amélioré le calcul, mais ça reste compliqué
si la cardinalité est grande).
Un autre problème qu’on a c’est le stockage : si on a un « bon code » et veut
l’utiliser, on a besoin de connaître ses mots, qui, a priori, doivent être stockés
dans un tableau qui serait d’une taille nM , déraisonnable et inadaptée à tout
usage pratique. Pour résoudre ce problème, on peut par exemple considérer un
alphabet A qui n’est pas seulement un groupe abélien, mais tel que (A; +, ·)
soit un corps fini, et supposer que C soit un sous-espace vectoriel de An . En
effet, pour décrire un espace vectoriel il suffit de donner une base, et celle-ci a
cardinalité log#A (M ) (pourquoi ? Le montrer par exercice).
Pour ces deux raisons, la théorie des codes a été du début liée à la théorie
des corps finis et à son algorithmique.

2.1 Définitions et propriétés de base

Soit K = Fq un corps fini de cardinalité q, où q est une puissance d’un nombre
premier (pour les généralités sur les corps fini voir par exemple [1, Chapitre 21]),
et n un entier positif.
Le K-espace vectoriel K n est muni de la métrique de Hamming.

13
14 CHAPITRE 2. CODES LINÉAIRES

Définition 2.1. Un code linéaire C est un K-sous-espace de K n . Ses pa-

ramètres sont sa longueur n, sa dimension k = logq (#C) et sa distance
minimale d. Si on connaît la distance minimale d, on dit que le code C est
un [n, k, d]q code (on dit simplement [n, k, d] code, si q = 2, i.e. si le code est
binaire), autrement on dit que le code C est un [n, k]q code (ou simplement
[n, k] code si le code est binaire).
Définition 2.2. Pour c ∈ C, on appelle poids de c le nombre de ses symboles
non nuls, i.e.
wt(c) = #{i | ci 6= 0}.
L’ensemble {i | ci 6= 0} est appelé support de c et indiqué Supp(c), de manière
que wt(c) = #Supp(c).
Notons que wt(c) = d(c, 0). On a donc le résultat suivant.
Proposition 2.1. La distance minimale d’un code linéaire est égale au plus
petit poids non nul de ce code.
Démonstration. Cela suit du fait que wt(c) = d(c, 0) et de (2.1).
Exercice 2.1. Montrer que
• Le code de parité est un [k + 1, k, 2] code.
• Le code de répétition est un [n, 1, n] code.
• Le code « carré » est un [9, 4, 4] code.
On a déjà dit que l’un des avantages de considérer un code linéaire c’est qu’on
peut le décrire avec une base. En théorie des codes, cette base est présentée
toujours en forme de matrice.
Définition 2.3. Une matrice génératrice G d’un [n, k, d]q code C est une
matrice k × n sur K dont les lignes sont les vecteurs d’une base de C.
Remarque 2.1. Avec un abus de langage, on parle souvent de « la » matrice
génératrice d’un code, en sachant que c’est l’une des nombreuses matrices gé-
nératrices.
Exemple 2.1. Le code C ⊆ F44 avec matrice génératrice
 
1 0 1 1
G :=
0 1 α 1

(où α ∈ F4 tel que α2 = α+1), est le code de longueur 4 et dimension 2 engendré

par les vecteurs (1, 0, 1, 1) et (0, 1, α, 1), i.e.

C = {u1 (1, 0, 1, 1) + u2 (0, 1, α, 1) | u1 , u2 ∈ F4 } = (u1 , u2 )G | (u1 , u2 ) ∈ F24 .



Il a donc 42 = 16 mots.
Exercice 2.2. Donner la liste des éléments du code C de l’Exemple 2.1 et
montrer que C est un [4, 2, 3]4 code.
2.2. MATRICE DE PARITÉ ET CODE DUAL 15

Exercice 2.3. Donner une matrice génératrice pour le code de parité, le code
de répétition et le code « carré ».

Si les premières k colonnes d’une matrice génératrice G d’un [n, k, d]q code C
ont rang k, i.e. si la sous-matrice A de G formée par ces colonnes est inversible,
alors
G0 = A−1 G = [Ik | B],

où Ik est la matrice identité de dimension k et B est une matrice k × (n − k) sur

K. Une matrice génératrice de cette forme (identité à gauche) est dite matrice
génératrice en forme systématique.

Remarque 2.2. Étant donnée une matrice génératrice G d’un [n, k, d]q code,
l’encodeur multiplie le vecteur u = (u1 , . . . , uk ) émis par la source par cette
matrice G, en obtenant un mot du code C. Si on change de matrice, on change
de codage, même si le code ne change pas. Notons que le codage est systématique
ssi la matrice génératrice considérée est en forme systématique.

Exercice 2.4. Soit C un [4, 2]4 code avec matrice génératrice

 
1 0 1 1
G := .
1 1 α2 0

• Existe-t-elle une matrice génératrice en forme systématique pour C ? Si

oui, la trouver.
• Combien de mot a-t-il ? En donner la liste.
• Quelle est la distance minimale de C ?
• Si c = (α2 , α, 0, 1) sort de l’encodeur (qui a codé avec la matrice G), qui
est le vecteur u émis par la source ?

2.2 Matrice de parité et code dual

Une autre façon de définir un code linéaire est de donner une application
linéaire dont il est le noyau (ou de manière équivalente un système linéaire
homogène dont il est la solution). La matrice qui représente cette application
est appelée matrice de parité ou matrice de contrôle.

Définition 2.4. Une matrice de parité (ou de contrôle) H d’un [n, k, d]q code
C est une matrice (n − k) × n sur K de rang n − k telle que

C = {v ∈ K n | vH T = (0, . . . , 0)}

Chaque ligne de la matrice H représente une équation de contrôle de

code, i.e. une équation linéaire que les coordonnées d’un mot du code doivent
satisfaire, et le code est l’ensemble des solutions de ces équations de contrôle
(qui sont linéairement indépendantes).
16 CHAPITRE 2. CODES LINÉAIRES

Exemple 2.2. Le code de parité a matrice de parité donnée par H = [1, . . . , 1].
En effet, un vecteur v = (v1 , . . . , vn ) ∈ Fn2 appartient au code de parité ssi

vH T = v1 + · · · + vn = 0

dans F2 , i.e. modulo 2.

Exercice 2.5. Montrer que tout mot c = (c1 , c2 , c3 , c4 ) du code C de l’Exemple
2.1 satisfait les équations

c1 + αc2 + c3 = 0
c1 + c2 + c4 = 0

En déduire qu’un matrice de parité pour C est

 
1 α 1 0
H= .
1 1 0 1

Étant donné un code linéaire C avec matrice génératrice G, comment trouver

une matrice de parité ? Si on réfléchit un instant, ce problème équivaut à trouver
une base du code dont une matrice de parité est égale à G, ce qui équivaut à
résoudre un système de k équations linéaires en n inconnus. Cela est beaucoup
plus simple lorsque la matrice est en forme systématique.
Proposition 2.2. Soit C un [n, k]q code avec matrice génératrice G = [Ik |A].
Alors une matrice de parité de C est H = [AT | − In−k ].
Démonstration. Notons d’abord que H = [AT | − In−k ] est de rang n − k. Donc
il suffit de montrer que chaque ligne de H est une équation de contrôle. Puisque
tout mot est une combinaison linéaire des lignes g1 , . . . , gk de G, il suffit de
montrer que gi H T = 0 pour tout i ∈ {1, . . . , k}. Cela revient à montrer que
GH T = 0. Or,
 
A
GH T = [Ik |A] = Ik A − AIn−k = A − A = 0,
−In−k
où la deuxième égalité est une multiplication de matrices par blocs (exercice).

Exemple 2.3. Une matrice de parité pour le [5, 3]3 code engendré par
 
1 0 0 2 1
G = 0 1 0 0 1
0 0 1 1 2

est égale à  
2 0 1 2 0
H= .
1 1 2 0 2
Donc pour trouver une matrice de parité il vaut mieux trouver d’abord une
matrice génératrice en forme systématique, si possible.
2.2. MATRICE DE PARITÉ ET CODE DUAL 17

Exercice 2.6. Trouver une matrice de parité pour le [5, 2]3 code engendré par
 
2 0 1 2 0
G= .
1 1 2 0 2

Définition 2.5. Soit C un code linéaire dans K n . Le (code) dual de C est

C ⊥ = {v ∈ K n | hv, ci = 0, ∀c ∈ C}
Pn
où hv, ci = i=1 vi ci (produit scalaire standard).
Si C ⊆ C ⊥ le code C est dit auto-orthogonal. Si C = C ⊥ le code C est dit
auto-dual.
Exercice 2.7. Montrer que si C est un [n, k]q code avec matrice génératrice G
et matrice de parité H, alors C ⊥ est un [n, n − k]q code avec matrice génératrice
H et matrice de parité G. En particulier, (C ⊥ )⊥ = C.
Montrer qu’un code auto-dual a forcement dimension n/2, de manière qu’il peux
exister seulement si n est pair.
Exemple 2.4. Le dual du code parité est le code de répétition, et vice versa.
Exercice 2.8. Donner une matrice génératrice du dual du code « carré ».
Si on veut utiliser la Proposition 2.2 mais le [n, k]q code n’est pas en forme
systématique, on peut chercher k colonnes libres, permuter les colonnes avec une
permutation σ ∈ Sn telle que les k colonnes deviennent les premières k colonnes,
multiplier à gauche par la matrice inverse de la matrice carrée formée par ces k
colonnes, appliquer la Proposition 2.2 et finalement permuter les colonnes avec
la permutation σ −1 .
Remarque 2.3. On souligne ici l’interprétation des lignes et des colonnes des
matrices génératrices et de parité d’un [n, k]q code :
• Les lignes g1 , . . . , gk d’une matrice génératrice : elles engendrent
par combinaison linéaire tous les mots du code, i.e. pour tout c ∈ C, il
existe λ1 , . . . , λk ∈ Fq tels que

c = λ1 g1 + · · · + λk gk .

• Les lignes h1 , . . . , hn−k d’une matrice de parité : un vecteur v ∈ Fnq

appartient à C ssi il est orthogonal à toute ligne, i.e. ssi hv, hi i = 0 pour
tout i ∈ {1, . . . , n − k}.
• Les colonnes g (1) , . . . , g (n) d’une matrice génératrice : pour tout
mot c ∈ C, il existe u ∈ Fkq tel que

c = (hu, g (1) i, . . . , hu, g (n) i).

• Les colonnes h(1) , . . . , h(n) d’une matrice de parité : un vecteur

v = (v1 , . . . , vn ) ∈ Fnq appartient à C ssi

v1 h(1) + · · · + vn h(n) = 0.
18 CHAPITRE 2. CODES LINÉAIRES

La dernière partie de la remarque nous indique un lien entre la matrice de

parité et la distance minimale d’un code.
Proposition 2.3. Un code linéaire a distance minimale d ssi toute famille de
d−1 colonnes de sa matrice de parité est libre et il existe d colonnes linéairement
dépendantes.
Démonstration. Soit {h(i) }i∈I un ensemble de w = #I ≥ 1 colonnes de la
matrice de parité telles qu’il existe une combinaison linéaire (avec des coefficients
qui ne sont pas tous égaux à zéro)
X
λi h(i) = 0.
i∈I

Le vecteur v tel que vj = λj si j ∈ I et vj = 0 autrement, est un mot non nul

du code par le dernier point de la Remarque 2.3, et il a poids au plus w. Donc
à tout ensemble de w colonnes liées on peut associer un mot du code de poids
au plus w. Vice versa, si c est un mot de poids w, l’ensemble {h(i) }i∈Supp(c) est
un ensemble de w colonnes liées, toujours par le dernier point de la Remarque
2.3. Cela nous montre que l’ensemble de mots non nuls de poids au plus w est
vide ssi il n’existe pas de famille de w colonnes liées. On conclut graçe à la
Proposition 2.1.
Remarque 2.4. Étant donné un code C et une matrice de parité H de C, on
a en particulier que
• d(C) = 1 ssi une colonne de H est nulle ;
• d(C) = 2 ssi il n’y a pas de colonnes nulles et il y a au moins deux
colonnes liées (i.e. l’une un multiple de l’autre) dans H ;
• d(C) ≥ 3 ssi il n’y a pas de colonnes nulles ni de couple de colonnes liées
dans H.
Notons que donc pour établir si d(C) ≥ 3 il suffit de regarder les colonnes d’une
matrice de parité sans avoir besoin de donner la liste de tous les mots.
Exercice 2.9. Quelle est la distance minimale du dual du code « carré » ?
Exercice 2.10. Soit C le [7, 3]7 code engendré par
 
1 0 0 1 2 3 4
G = 0 1 0 2 4 6 1 .
0 0 1 0 1 1 1

Quelle est la distance minimale de C ? Et de C ⊥ ?

2.3 Borne de Singleton et codes MDS

Soit C un [n, k, d]q code linéaire et H sa matrice de parité. Clairement, elle
a au plus n − k colonnes libres, de manière que n − k + 1 colonnes sont forcement
liées. Donc forcement, par la Proposition 2.3,
d(C) ≤ n − k + 1.
2.4. DISTRIBUTION DES POIDS 19

Cette inégalité est appelée borne de Singleton et elle est vraie même si le
code n’est pas linéaire :

Théorème 2.1 (borne de Singleton). Soit C ⊆ An et k := log#A (#C). Alors

d(C) ≤ n − k + 1.

Démonstration. On peut considérer la projection π : An → An−d(C)+1 sur les

premières n − d(C) + 1 coordonnées. Soient c, c0 ∈ C, c 6= c0 . Puisque d(c, c0 ) ≥
d(C), on a π(c) 6= π(c0 ), de manière que π|C est injective. Donc

#C ≤ (#A)n−d+1 .

Définition 2.6. Un [n, k, d]q code est appelé MDS (Maximum Distance Sepa-
rable) si d = n − k + 1, i.e. si ses paramètres satisfont l’égalité dans la borne de
Singleton. Un code est dit MDS trivial lorsque k ∈ {1, n − 1, n}.

Exemple 2.5. Les codes de répétition et de parité sont des exemples de codes
MDS triviaux binaires. Le code de l’Exemple 2.1 est un code MDS (non trivial).

Exercice 2.11 (∗). Montrer que, si A = F2 , le code de répétition, le code de

parité et l’espace Fn2 sont les seuls codes MDS possibles, de manière qu’il n’existe
pas de codes MDS non triviaux binaires.

Remarque 2.5 (Propriétés des codes MDS). Les codes MDS sont, par défi-
nition, des codes avec la distance minimale la plus large possible étant données
longueur et dimension. Ils sont donc des codes « optimaux » pour la correction
des erreurs. Ils ont d’autres propriétés intéressantes qu’on énonce ici laissant
leur preuve par exercice.
1. Un [n, k]q code est MDS ssi chaque ensemble de n − k colonnes de sa
matrice de parité est de rang n − k.
2. Si C est MDS, alors C ⊥ l’est aussi.
3. Un [n, k]q code est MDS ssi chaque ensemble de k colonnes de sa matrice
de génératrice est de rang k.

Exercice 2.12. Montrer les propriétés 1., 2. et 3. de la Remarque 2.5.

2.4 Distribution des poids

Une propriété combinatoire importante d’un code est sa distribution de
poids, c’est-à-dire le nombre de mots de chaque poids. Plus précisément, la
distribution des poids d’un [n, k]q code est la liste

A0 (C), A1 (C), . . . , An (C)

20 CHAPITRE 2. CODES LINÉAIRES

avec
Ai (C) = #{c ∈ C | wt(c) = i}.
Souvent on écrit seulement les éléments non nuls de cette liste. La distribution
de poids d’un code ne donne pas seulement la capacité de correction des erreurs
du code, mais permet également de calculer la probabilité de détection et de
correction des erreurs.

Remarque 2.6. Tous les Ai (C) sont des entiers non négatifs. En plus, A0 (C) =
1 et A0 (C) + . . . + An (C) = #C pour tous les codes.

Exercice 2.13. Montrer que si C est un [n, k] code binaire et (1, 1, . . . , 1) ∈ C,

alors An−i (C) = Ai (C).

Il est de pratique courante de représenter la distribution des poids par un

polynôme.

Définition 2.7. Le polynôme (énumérateur) des poids d’un code C est le

polynôme homogène

X n
X
wC (x, y) = xn−wt(c) y wt(c) = Ai (C)xn−i y i .
c∈C i=0

Exemple 2.6. On peut facilement calculer les polynômes des poids de nos
exemples historiques (exercice).
• Le polynôme des poids du [n, 1, n] code de répétition C est

wC (x, y) = xn + y n .

• Le polynôme des poids du [n, n − 1, 2] code de parité C est

(x + y)n + (x − y)n
wC (x, y) = .
2
• Le polynôme des poids du [9, 4, 4] code « carré » C est

wC (x, y) = x9 + 9x5 y 4 + 6x3 y 6 .

La distribution des poids d’un code et de son dual sont très liés, comme le
résultat suivant montre.

Théorème 2.2 (identité de MacWilliams). Soit C un code sur Fq et C ⊥ son

dual. Alors
1
wC ⊥ (x, y) = · wC (x + (q − 1)y, x − y).
#C
Démonstration. La démonstration de ce théorème dépasse le cadre de ce cours
introductif. Les personnes intéressées peuvent consulter le livre [2]. Elle utilise
la transformée de Fourier discrète.
2.5. ÉQUIVALENCE DE CODES 21

Exercice 2.14. Montrer (sans calculer la liste de ses éléments) que le polynôme
des poids du dual du code « carré » C ⊥ est

wC ⊥ (x, y) = x9 + 6x6 y 3 + 9x5 y 4 + 9x4 y 5 + 6x3 y 6 + y 9 .

Exercice 2.15 (∗). Montrer que le polynôme des poids d’un [4, 2, 3]q code C
(notons que c’est un code MDS) est

wC (x, y) = x4 + 4(q − 1)xy 3 + (q − 1)(q − 3)y 4 .

2.5 Équivalence de codes

‘ Soit Sn le groupe symétrique de degré n, i.e. le groupe des permutations
de l’ensemble {1, . . . , n}. Pour tout σ ∈ Sn et x = (x1 , . . . , xn ) ∈ Fnq , on définit

xσ = (xσ−1 (1) , . . . , xσ−1 (n) ).

Exemple 2.7. (x1 , x2 . . . , xn )(1 2 ... n) = (xn , x1 , . . . , xn−1 ).

On peut représenter cette « action » de Sn sur Fq (pour plus de détails sur
les actions des groupes sur les ensembles voir [1, Chapitre 18]) à travers des
matrices appelées matrices de permutation :

xσ = xMσ

où Mσ est une matrice dont toutes les coefficients sont nuls à l’exception des
coefficients indexés par (i, σ(i)) qui valent 1.
 
0 1 0 0
0 0 1 0
Exemple 2.8. M(1 2 3 4) =  0 0 0 1. En effet


1 0 0 0

(x1 , x2 , x3 , x4 )(1 2 3 4) = (x4 , x1 , x2 , x3 ) = (x1 , x2 , x3 , x4 )M(1 2 3 4) .

Une matrice de permutation est donc une matrice avec un seul élément non
nul (et égal à 1) sur toute ligne et sur toute colonne. Elle est toujours inversible.
Elle représente la transformation linéaire de Fnq associée à σ.
Remarque 2.7. Une propriété très importante des ces transformations linéaires
est le fait qu’elle ne changent pas le poids du vecteur, i.e., pour tout σ ∈ Sn et
x ∈ Fqn ,
wt(xσ ) = wt(xMσ ) = wt(x).
Elle sont donc des isométries pour la métrique de Hamming. Elle ne sont
pas la forme plus générale d’isométrie qu’on peut considérer : par exemple les
matrices monomiales, i.e. avec un seul élément non nul (mais pas forcement
égal à 1) sur toute ligne et sur toute colonne, représentent des isométries aussi.
Dans la cadre de ce cours, pour simplifier la notation, nous ne considérerons
que les matrices de permutation.
22 CHAPITRE 2. CODES LINÉAIRES

L’« action » de Sn sur Fnq induit une « action » sur les codes dans Fnq , donnée
par
C σ = {cσ | c ∈ C},
pour C ⊆ Fnq et σ ∈ Sn .
Définition 2.8. Soit C un code dans Fnq . Un élément σ ∈ Sn est un automor-
phisme (de permutation) de C si C σ = C.
Exercice 2.16. Montrer que l’ensemble Aut(C) des automorphismes d’un code
C est un sous-groupe de Sn .
Aut(C) est appelé groupe des automorphismes (de permutation) de C.
Exercice 2.17. Soit C un code linéaire. Montrer que Aut(C) = Aut(C ⊥ ).
Définition 2.9. Soient C1 et C2 deux codes dans Fnq . Ils sont équivalents (par
permutation) s’il existe σ ∈ Sn telle que

C2 = C1σ .

Notation : C1 ∼ C2 .
Exercice 2.18. Montrer que ∼ est une relation d’équivalence.
Par la Remarque 2.7, codes équivalents (par permutation) ont les mêmes
paramètres et la même distribution des poids. Attention : le vice versa n’est pas
vrai, comme montré dans l’exemple suivant.
Exemple 2.9. Les deux [4, 2, 3]7 codes C1 et C2 avec matrices génératrices
respectivement  
1 0 1 1
G1 =
0 1 1 2
et  
1 0 1 2
G2 =
0 1 3 4
ont le même polynôme des poids, i.e.

wC1 (x, y) = wC2 (x, y) = x4 + 24xy 3 + 24y 4 ,

mais ils ne sont pas équivalents (on peut par exemple vérifier - avec des longs
calculs - que C2 ne contient aucun mot de poids 3 avec tous les éléments non
nuls égaux, tandis que C1 si).

2.6 Décodage par syndrome

On déjà vu que dans notre configuration de base l’encodeur sort un mot de
code x ∈ C ⊆ K n et que le bruit le transforme en un autre élément y ∈ K n .
Dans le cas des codes linéaires, on peut exprimer l’erreur comme

e = y − x ∈ K n.
2.7. EXTENSIONS DES CODES 23

Soit H une matrice de parité pour C. Le décodeur peut facilement détecter

s’il y a eu une erreur en calculant yH T . En effet, yH T = 0 ssi y ∈ C. Donc,
si wt(e) ≤ d(C) − 1, le décodeur dira (justement) qu’il y a eu une erreur ssi
yH T 6= 0.
Définition 2.10. On appelle yH T le syndrome de y.
Notons que y = x + e et
yH T = (x + e)H T = xH T + eH T = 0 + eH T = eH T ,
de manière que le syndrome de y (que le décodeur peut facilement calculer) est
le même que celui de e (que le décodeur ne connaît pas).
Supposons que le décodeur ait fait un pré-calcul
j des
k tous les syndromes des
erreurs possibles de poids inférieur ou égale à d(C)−1
2 en les mettant dans un
tableau du type
j k
Mots de poids ≤ d(C)−12 syndromes
e eH T

Exercice 2.19. Montrer que tous les syndromes dans le tableau sont différents.
j k
Si wt(e) ≤ d(C)−1
2 , le décodeur reçoit y, il calcule son syndrome yH T et
il le compare avec les syndromes présents dans le tableau. Il obtient donc e, et
ensuite x = y − e.
Remarque 2.8. Ce procédé est particulièrement simple si d(C) est égale à
3 ou 4 (de manière que le code peut corriger une erreur), car les syndromes
sont simplement des multiples des colonnes de la matrice de parité transposées.
Dans le cas binaire, ils sont exactement les colonnes de la matrice de parité
(transposées). Par contre, ce procédé devient inutilisable en pratique dès qu’on
considère de longueur grandes et une capacité de correction plus importante : la
taille du tableau devient trop grande. Toutefois, il est un modèle pour d’autres
types de décodages.
Exercice 2.20. Utiliser le décodage par syndrome pour corriger y = (α, α2 , 1, 0),
pour le [4, 2, 3]4 code de l’Exemple 2.1.

2.7 Extensions des codes

Il existe plusieurs façons d’obtenir de nouveaux codes à partir de familles de
codes déjà construites. L’une d’entre elles est l’extension (pour d’autres façons,
voir [3, Section 1.5]).
Définition 2.11. Soit C un [n, k, d]q code. Son extension est le code
b := {(c1 , . . . , cn+1 ) ∈ Fn+1
C q | (c1 , . . . , cn ) ∈ C et c1 + . . . + cn+1 = 0},
qui est appelé aussi C étendu.
24 CHAPITRE 2. CODES LINÉAIRES

Théorème 2.3. C b est un [n + 1, k]q code et sa distance minimale est d, s’il

existe un mot c dans C de poids d tel que c1 + . . . + cn = 0, et d + 1 autrement.
Démonstration. On a que C b est un code linéaire. En effet, C
b est stable par
combinaison linéaire : soient

c = (c1 , . . . , cn+1 ) et d = (d1 , . . . , dn+1 )

deux mots dans C.

b Alors

λc + µd = (λc1 + µd1 , . . . , λcn+1 + µdn+1 )

appartient à C.
b En effet

(λc1 + µd1 , . . . , λcn + µdn ) ∈ C,

car C est un code linéaire, et

λc1 + µd1 + . . . + λcn+1 + µdn+1 = λ(c1 + . . . + cn+1 ) + µ(d1 + . . . + dn+1 ) = 0

La longueur de C b est n + 1 par définition. À tout mot de C correspond un et

un seul mot de C, de manière que #C
b b = #C. Donc dim C b = k. L’affirmation
sur la distance minimale suit directement de la définition de C.
b

Soit H une matrice de parité pour C. Une matrice de parité pour C

b est
 
0

H .. 

 . 

 0 
1 ... 1 1

car aux équations de contrôle de C on ajoute juste c1 + . . . + cn+1 = 0, qui nous

donne la dernière ligne.
Exercice 2.21. Déterminer les paramètres de l’extension du [5, 3]3 code de
l’Exemple 2.3 et de son dual.
Chapitre 3

Familles de codes linéaires

remarquables

Nous avons vu dans le premier chapitre quelques familles de codes dont

les paramètres n’étaient pas « optimaux ». Dans ce chapitre, nous présentons
quelques familles de codes classiques, très étudiées et à la base d’autres construc-
tions. Pour simplifier la notation on va considérer seulement des codes binaires,
mais les mêmes familles existent aussi sur d’autres corps finis.

3.1 Codes de Hamming et codes simplexes

On définit les codes de Hamming à partir de leur matrice de parité et à
permutation près.

Définition 3.1. Soit m un entier positif. Le code de Hamming Hm est le

[2m − 1 , 2m − m − 1] code binaire dont une matrice de parité Hm est une
matrice m × (2m − 1) dont les colonnes sont les éléments non nuls de l’espace
Fm2 (dans un ordre quelconque).

Si on change l’ordre des colonnes, le code reste un code de Hamming : en

vérité Hm définit une classe de codes équivalents. Il convient souvent de choisir
l’ordre des colonnes de manière d’avoir l’identité à la fin (ou au début), pour
pouvoir appliquer la Proposition 2.2 et trouver une matrice génératrice.

Exemple 3.1. On peut choisir comme matrice de parité de H3 la matrice

 
1 1 0 1 1 0 0
H3 = 1 0 1 1 0 1 0
0 1 1 1 0 0 1

25
26 CHAPITRE 3. FAMILLES DE CODES LINÉAIRES REMARQUABLES

de manière que  
1 0 0 0 1 1 0
0 1 0 0 1 0 1
G3 = 
0

0 1 0 0 1 1
0 0 0 1 1 1 1
est une matrice génératrice de H3 par la Proposition 2.2.

Exercice 3.1. Montrer que la distance minimale de Hm est 3 pour tout m ≥ 3.

Par l’Exercice 3.1, tout code de Hamming est donc 1-correcteur. Ils sont
parfait : en effet
 
n m m
1+ = 1 + n = 2m = 2(2 −1)−(2 −m−1) = 2n−k .
1

Exercice 3.2. Considérons le code H3 avec la matrice génératrice donnée dans

l’Exemple 3.1. Décoder y = (0, 1, 1, 1, 1, 1, 0).
⊥
Définition 3.2. Les duaux des codes de Hamming Sm = Hm sont appelés codes
m
simplexes. Ces sont donc des [2 − 1, m] codes binaires, dont une matrice
génératrice est Hm .

On va déterminer la distribution des poids des codes simplexes et donc des

codes de Hamming (graçe au Théorème 2.2).

Théorème 3.1. Soit n = 2m − 1. Les polynômes des poids des codes simplexes
et des codes de Hamming sont
n−1 n+1
wSm (x, y) = xn + nx 2 y 2

et
1 h n−1 n+1
i
wHm (x, y) = (x + y)n + n(x + y) 2 (x − y) 2 .
n+1
En particulier, les codes simplexes Sm sont des [2m − 1, m, 2m−1 ] codes.

Démonstration. Par définition, Sm = {xHm | x ∈ Fm

2 }. Appellons h
(1)
, . . . , h(n)
les colonnes de Hm . Si x 6= 0, alors

wt(xHm ) = n − #{j | hx, h(j) i = 0}.

Or, l’ensemble des vecteurs orthogonaux à x est un sous-espace vectoriel de Fm

2
de dimension m − 1, qui contient donc 2m−1 − 1 vecteurs non nuls. Ainsi,
n+1
wt(xHm ) = n − (2m−1 − 1) = 2m−1 = 2 2 .

Cela implique donc que tout mot non nul a poids 2m−1 , d’où la forme du po-
lynôme des poids de Sm . La forme du polynôme des poids de Hm descends
directement en appliquant le Théorème 2.2 au polynôme wSm (x, y).
3.2. CODES DE REED-MULLER 27

Exercice 3.3. Vérifier que

wS3 (x, y) = x7 + 7x3 y 4

et que
1
(x + y)8 + 8(x + y)3 (x − y)4 = x7 + 7x4 y 3 + 7x3 y 4 + y 7 .

wH3 (x, y) =
8
Remarque 3.1. Notons que le Théorème 3.1 nous permets de calculer facile-
ment la distribution des poids de codes grandes sans devoir calculer la liste de
ses mots. Par exemple, H5 est un [31, 26, 3] code avec 226 = 67108864 mots avec
polynôme des poids
1 
(x + y)31 + 31(x + y)15 (x − y)16 = x31 + 155x28 y 3 + . . .

wH5 (x, y) =
32
Donc, sans en faire la liste, on sait qu’il y a 155 mots de poids 3 en H5 .

3.2 Codes de Reed-Muller

On peut introduire les codes de Reed-Muller à partir des codes de Hamming,
à travers la construction vue ci-dessus.
Soit Hm une matrice de parité d’un code de Hamming Hm . Considérons le
code Cm engendré par  
0
.. 
 Hm

 . 

 0 
1 ... 1 1
⊥
(i.e. le dual H
d m du code de Hamming).
m m−1 m−1 m
Exercice 3.4. Montrer que wCm (x, y) = x2 + (2m+1 − 2)x2 y2 + y2 .
Exemple 3.2. Pour m = 3 on obtient le [8, 4, 4] code avec matrice génératrice
 
1 1 0 1 1 0 0 0
1 0 1 1 0 1 0 0
G= 0

1 1 1 0 0 1 0
1 1 1 1 1 1 1 1

avec polynôme des poids x8 + 14x4 y 4 + y 8 . On peut montrer que c’est un code
auto-dual (exercice) et il est donc égal à H
c3 .

Regardons la matrice G de l’Exemple 3.2. La première ligne est la première

coordonnée de tous les vecteurs de F32 (dans l’ordre qu’on avait choisi pour H3 ,
plus le vecteur nul à la fin). Si on pense aux vecteurs de F32 comme des vecteurs
[x1 , x2 , x3 ], la première ligne est donc égale au polynôme x1 évalué sur tous les
28 CHAPITRE 3. FAMILLES DE CODES LINÉAIRES REMARQUABLES

vecteurs de F32 . De la même façon, la deuxième ligne est égale au polynôme x2

évalué sur tous les vecteurs de F32 (dans le même ordre), et la troisième ligne est
égale au polynôme x3 évalué sur tous les vecteurs de F32 (dans le même ordre).
Dans la quatrième ligne, tout élément vaut 1 et on peut l’interpréter comme
l’évaluation du polynôme constant 1 sur tous les vecteurs de F32 . Puisqu’un
⊥
mot du code H c3 = H c3 est une combinaison linéaire des lignes de G (avec des
coefficients λ1 , λ2 , λ3 , λ4 , ∈ F2 ), suivant l’interprétation ci-dessus, on peut le voir
comme l’évaluation de

p(x) = λ1 x1 + λ2 x2 + λ3 x3 + λ4

sur tous les vecteurs de F32 . Cela peut être exprimé avec la notation suivante :

(p(v))v∈F32 ,

où il est sous-entendu que l’ordre est librement choisi mais fixe. Notons que p(x)
est un polynôme générique à trois indéterminées de degré au plus 1 sur F2 (pour
simplifier la notation, dans ce cours nous incluons également le polynôme nul
parmi les polynômes de degré au plus r ∈ N). On a donc montré que
⊥
H
c3 = {(p(v))v∈F32 | p(x) ∈ F2 [x1 , x2 , x3 ] de degré au plus 1}.

Il est facile de voir que cela peut être généralisé, i.e. que
⊥
H
d m = {(p(v))v∈Fm
2
| p(x) ∈ F2 [x1 , . . . , xm ] de degré au plus 1}.

Ces codes sont des cas particuliers de codes de Reed-Muller.

Définition 3.3. Soient m, r deux entiers avec 0 ≤ r ≤ m. On appelle code de

Reed-Muller d’ordre r en m le code

RM(r, m) = {(p(v))v∈Fm
2
| p(x) ∈ F2 [x1 , . . . , xm ] de degré au plus r}.

Comme pour les codes de Hamming, si on change l’ordre des colonnes, le

code reste un code de Reed Muller : en vérité, RM(r, m) définit une classe de
codes équivalents.

Exemple 3.3. Si r ≤ 1, on retrouve des codes qu’on connaît :

— RM(0, m) est un code de répétition.
⊥
— RM(1, m) = H dm .

Clairement, tout code RM(r, m) a longueur 2m . On veut comprendre quelle

est la dimension de ces codes.

Définition 3.4. On appelle fonction booléenne sur Fm

2 toute application de
Fm
2 sur F 2 .
3.2. CODES DE REED-MULLER 29

Notons que toute application de Fm 2 sur F2 est polynomiale (on le voit par
exemple en utilisant l’interpolation lagrangienne), mais différents polynômes
peuvent donner la même application (par exemple x21 et x1 donnent les mêmes
valeurs si évalués sur F2 ). Pour obtenir une représentation unique, il faut consi-
dérer les éléments de l’anneau quotient
F2 [x1 , . . . , xm ]/(x21 + x1 , . . . , x2m + xm ),
i.e. des polynômes où chaque indéterminée apparaît au degré au plus 1. Cette
représentation s’appelle forme algébrique normale. Une base pour l’espace
des fonctions booléennes est donnée par l’ensemble des monômes de la forme
Y
xi .
i∈I

Notons que le degré de chaque monôme est donné par #I. Le degré d’une
fonction booléenne est le degré maximal des monômes de sa forme algébrique
normale.
Exemple 3.4. La forme algébrique normale de la fonction
(x1 , x2 , x3 ) 7→ x21 + x1 x2 + x32 x3 + x1 x22 x33
est
(x1 , x2 , x3 ) 7→ x1 + x1 x2 + x2 x3 + x1 x2 x3 ,
d’où on voit que son degré est 3, i.e. le degré de x1 x2 x3 .
Avec ces notions, on peut voir facilement que
RM(r, m) = {(f (v))v∈Fm
2
| f : Fm
2 → F2 de degré au plus r}.

Cela nous permet de trouver facilement la dimension de RM(r, m). Voyons un

exemple.
Exemple 3.5. On a que
RM(2, 3) = {(f (v))v∈F32 | f : F32 → F2 de degré au plus 2}.
Une fonction booléenne de degré au plus 2 est une combinaison linéaire des
monômes
1, x1 , x2 , x3 , x1 x2 , x2 x3 , x1 x3 ,
de manière que, en gardant le même ordre des vecteurs de F32 de l’Exemple 3.2,
une matrice génératrice pour RM(2, 3) est donnée par
 
1 1 1 1 1 1 1 1 1
1 1 0 1 1 0 0 0 x1
 
1 0 1 1 0 1 0 0 x2
 
0 1 1 1 0 0 1 0 x3 .
 
1 0 0 1 0 0 0 0 x1 x2
 
0 0 1 1 0 0 0 0 x2 x3
0 1 0 1 0 0 0 0 x1 x3
30 CHAPITRE 3. FAMILLES DE CODES LINÉAIRES REMARQUABLES

Donc RM(2, 3) est un [8, 7] code. On peut vérifier que c’est le code de parité de
longueur 8.

Exercice 3.5. Montrer que

r  
X m
dim RM(r, m) = .
i=0
i

Notons qu’en particulier RM(m, m) = Fm

2 .

Proposition 3.1. Le dual d’un code de Reed-Muller est un code de Reed-Muller.

En particulier
RM(r, m)⊥ = RM(m − r − 1, m).

Démonstration. Notons d’abord que

r   m−r−1
X  
X m m
dim RM(r, m) + dim RM(m − r − 1, m) = +
i=0
i i=0
i

r   m−r−1
X   X r   m  
X m m m X m
= + = + = 2m
i=0
i i=0
m−i i=0
i j=r+1
j

qui est la longueur, de manière que la dimension de RM(m − r − 1, m) est celle

du dual de RM(r, m). Il suffit donc de montrer que RM(m − r − 1, m) est
contenu dans RM(r, m)⊥ : soit w = (f (v))v∈Fm 2
un mot de RM(m − r − 1, m),
i.e. supposons que f soit de degré au plus m − r − 1. On doit montrer que x est
orthogonal à tout mot de RM(r, m), i.e. à tout c = (g(v))v∈Fm 2
avec g de degré
au plus r. Or
X X
hw, ci = f (v)g(v) = f g(v),
v∈Fm
2 v∈Fm
2

où f g est de degré au Q plus m − 1, i.e. f g est une somme de monômes de degré

inférieur à n. Soit i∈I xi l’un de ces monômes. Puisque #I < m, il existe
j ∈ {1, . . . , m} − I. On a
X Y X X Y X  quelque chose

xi = ... xi = = 0.
qui ne dépend pas de j
v∈Fm
2 i∈I v1 ∈F2 vn ∈F2 i∈I vj ∈F2

Donc hw, ci = 0.

Exercice 3.6. Calculer le polynôme des poids de RM(2, 4). En déduire que
c’est un [16, 11, 4] code.

Proposition 3.2 (voir Chapter 13 of [2]). La distance minimale d’un code

RM(r, m) est 2m−r .
3.3. CODES DE GOLAY BINAIRES 31

3.3 Codes de Golay binaires

On va introduire les codes de Golay binaires avec un approche simple d’Alan
Turing. Soient C1 et C2 des codes avec matrices génératrices respectivement
   
1 1 0 1 0 0 0 1 1 0 1 1 0 0 0 1
0 1 1 0 1 0 0 1 0 1 0 1 1 0 0 1
G1 = 0 0 1 1 0 1 0 1 et G2 = 0 0 1 0 1 1 0 1
  

0 0 0 1 1 0 1 1 0 0 0 1 0 1 1 1

Exercice 3.7. Vérifier que C1 et C2 sont des codes RM(1, 3) de paramètres

[8, 4, 4] et que C1 ∩ C2 est le code de répétition de paramètres [8, 1, 8].
Définition 3.5. Le code de Golay binaire étendu G24 est le code de longueur
24 défini par

G24 = {(a + x | b + x | a + b + x) ∈ F24

2 | a, b ∈ C1 , x ∈ C2 }.

Exercice 3.8. Montrer que G24 est un code linéaire, de dimension 12 et qu’il
est auto-dual.

Théorème 3.2 ([2]). Le code G24 est un [24, 12, 8] code auto-dual et c’est
l’unique code avec ces paramètres, à équivalence près.
Exercice 3.9 (∗). En utilisant le Théorème 2.2, l’Exercice 2.13 et le fait que
dans un code auto-dual binaire tout mot a poids pair (le monter en amont),
montrer que

wG24 (x, y) = x24 + 759x16 x8 + 2576x12 y 12 + 759x8 x16 + y 24 .

(il peut être utile d’utiliser un logiciel de calcul formel).

En enlevant la même coordonnée à tout mot d’un code de Golay étendu
G24 , on obtient un [23, 12, 7], qui est appelé code de Golay G23 . On peut
montrer que si on change la coordonnée enlevée les codes qu’on obtient sont
tous équivalents.
Exercice 3.10. Montrer que G23 est un code parfait.
32 CHAPITRE 3. FAMILLES DE CODES LINÉAIRES REMARQUABLES
Chapitre 4

Exercices avec correction

Exercice 4.1. Soit C le [9, 4, 3] code dont les mots sont de la forme (c1 , c2 , c1 +
c2 , c3 , c4 , c3 + c4 , c1 + c3 , c2 + c4 , c1 + c2 + c3 + c4 ).
a) Est-ce que le mot x := (1, 0, 1, 1, 1, 0, 0, 0, 1) appartient à C ? Justifier.
b) Quel est le mot y du code C le plus proche à x ? Justifier.
c) Est-ce que z := (0, 0, 1, 0, 0, 1, 0, 0, 1) est dans C ⊥ ? Justifier.

Solution :
a) Non. En effet c2 + c4 = 1 6= 0.
b) C’est y = (1, 0, 1, 1, 1, 0, 0, 1, 1) (on peut le trouver en remarquant que
C est le code « carré » et utilisant la méthode de décodage vue pour ce
code). En effet, puisque d(x, y) = 1 et la distance minimal de C est 3, il
n’existe pas un autre mot y 0 du code C avec distance plus petite ou égale
à 1 de x, car sinon d(y, y 0 ) ≤ d(y, x) + d(x, y 0 ) ≤ 2.
c) Oui. En effet,

hc, zi = (c1 + c2 ) + (c3 + c3 ) + (c1 + c2 + c3 + c4 ) =

= 0c1 + 0c2 + 0c3 + 0c4 = 0

pour tout c ∈ C.

Exercice 4.2. Montrer qu’un [n, n − 1, 2] code est forcement le code de parité
de longueur n.

Solution : Soit C un [n, n − 1, 2] code. Alors C ⊥ a longueur n, dimension

n − (n − 1) = 1. De plus, sa matrice génératrice est forcement

H := [1 · · · 1],

car sinon, par la Proposition 2.3, C n’aurait pas distance minimale 2, en ayant
des colonnes nulles. Ainsi, par la Proposition 2.2, on a qu’une matrice génératrice

33
34 CHAPITRE 4. EXERCICES AVEC CORRECTION

de C est  
1 0 ··· 0 1
0 1 ··· 0 1
G :=  . . .. ..  ,
 
 .. .. ..
. . .
0 0 ··· 1 1
ce qui implique que tout mot (c1 , c2 , . . . , cn ) est tel que
n−1
X
cn = ci .
i=1

On a appelé cela code de parité.

Exercice 4.3. Soit C ⊆ F62 un code avec matrice génératrice

 
1 0 0 0 1 1
G := 0 1 0 1 0 1
0 0 1 1 1 0

a) Donner une matrice génératrice, la dimension et la distance minimale de

C ⊥ . Justifier.
b) Montrer que la distance minimale de C est 3.
c) Est-ce que C = C ⊥ ? Justifier.
d) Est-ce que C est un code parfait ? Justifier.
Solution :
a) Une matrice génératrice de C ⊥ est, par la Proposition 2.2,
 
0 1 1 1 0 0
H := 1 0 1 0 1 0 .
1 1 0 0 0 1

La dimension de C ⊥ est 3 = 6 − 3 et sa distance minimale est 3, car dans

G il n’y a pas de colonnes nulles ni deux colonnes idéntiques, de manière
que la distance minimal est au moins 3, et il y a 3 colonnes linéairment
dépendantes (par exemple les 3 dernières).
b) On observe que G est égale à H à une permutation de colonnes près.
Donc C a la même distance minimale de C ⊥ .
c) Non. Par exemple c := (1, 0, 0, 0, 1, 1) ∈ C mais hc, ci = 0, de manière
que c n’est pas dans C ⊥ .
d) Non. Dans ce cas, e = 1, n = 6, k = 3. On a donc

1 + 6 < 26−3 = 8.

Exercice 4.4. Soit C le code de longueur 4 sur F3 dont les mots sont de la
forme (c1 , c2 , c1 + c2 , c1 − c2 ).
 35

a) Écrire une matrice génératrice pour C.

b) Combien y a-t-il de mots dans C ? Justifier.
c) Quel sont les paramètres de C ? Justifier.
d) Est-ce que C est auto-dual ? Justifier.
e) Est-ce que C est MDS ? Justifier.
f) Est-ce que v = (1, 1, 2, 1) appartient à C ? Si non, le corriger (c’est-à
dire, trouver le mot du code le plus proche à v).

Solution :
a) (c1 , c2 , c1 + c2 , c1 − c2 ) = c1 (1, 0, 1, 1) + c2 (0, 1, 1, 2), et les deux vecteurs
sont linéairement indépendentes, de manière qu’une matrice génératrice
pour C est  
1 0 1 1
G=
0 1 1 2
b) Tout mot est une combinaisons linéaire des deux vecteurs d’une base avec
coefficients dans F3 . Ainsi il y a 32 = 9 mots.
c) La longueur est 4 et la dimension est 2. Une matrice de parité pour C
est (par la Proposition 2.2)
 
1 1 2 0
H= ,
1 2 0 2

qui n’a pas ni de colonnes nulles ni de colonnes qui sont l’une un multiple
de l’autre. Donc, par la Proposition 2.3, la distance minimale est au moins
3. Puisque dans le code il y a de mots de poids 3 (par exemple les lignes
de G), la distance minimale est 3.
d) Soient h1 et h2 les deux lignes de H. On a que −h1 − h2 est égale à la
première ligne de G et h2 − h1 est égale à la deuxième ligne de G, de
manière que le code engendré par H est C, qui est donc auto-dual.
e) Oui, parce que 3 = 4 − 2 + 1.
f) Le vecteur v = (1, 1, 2, 1) n’appartient pas à C. En effet, v4 = 1 6= 0 =
v1 − v2 . Le mot c = (1, 1, 2, 0) a distance 1 de v et il est donc le plus
proche (car la distance minimale est 3). Pour le trouver, on aurait pu
utiliser la méthode de décodage par syndrome aussi.

Exercice 4.5. Soit C un [n, k, d] code avec matrice génératrice G = [Ik |A], où
Ik est la matrice identité de taille k × k sur F2 . Supposons k ≥ 3.
a) Montrer que d ≥ 3 si et seulement si toute ligne de G a poids au moins
3 et toutes les lignes de A sont différentes.
b) Soit A = U + Ik , où U est la matrice de taille k × k sur F2 avec toute
entrée égale à 1. Est-ce que le mot

v = (1, 0, . . . , 0 , 1)
| {z }
2k−2 fois

appartient au code C ?
36 CHAPITRE 4. EXERCICES AVEC CORRECTION

c) Soit A = U + Ik comme dans le point b). Le mot recu

u = (0, . . . , 0, 1, . . . , 1)
| {z } | {z }
k−1 fois k+1 fois

n’appartient pas au code C. Le corriger (c’est-à dire, trouver le mot du

code le plus proche à u).

Solution :
a) Puisque G est en forme systématique, H = [AT |In−k ], par la Proposi-
tion 2.2. Par la Proposition 2.3, on a aussi que d ≥ 3 si et seulement si
toute colonne de H est non nulle et il n’y a pas de colonnes égales. Cette
dernière condition équivaut au fait que les colonnes de AT (qui sont les
lignes de A) aient poids au moins 2 (pour être non nulles et différentes
de celles de In−k ) et qu’elles soient différentes, ce qui est équivalent au
fait que toute ligne de G a poids au moins 3 et toutes les lignes de A sont
différentes.
b) Toutes les lignes de A = U + Ik sont différentes et toute ligne de G a
poids k = 1 + (k − 1). Donc la distance minimale de C est 3 par a). Ainsi
v, qui a poids 2, n’appartient pas à C.
c) Puisque AT = A, on a que H = [A|Ik ]. Ainsi HuT , qui est la somme des
k + 1 dernières colonnes de H, est égale à
 
0
 .. 
HuT =  .  .
 
0
1

Cela est la dernière colonne de H, c’est-à-dire le syndrome de

e = (0, 0, . . . , 0, 1),

de manière que la correction de u est

c = u − e = (0, . . . , 0, 1, . . . , 1, 0)
| {z } | {z }
k−1 fois k fois

Exercice 4.6. Soit C le code linéaire de longueur 5 sur F5 dont une matrice
génératrice est  
1 0 0 1 1
G = 0 1 0 1 2 .
0 0 1 1 3
a) Donner la définition de code linéaire et des ses paramètres. Quel sont les
paramètres de C ? Justifier.
b) Combien y a-t-il de mots dans C ? Justifier.
 37

c) Donner une matrice de parité pour C et calculer le syndrome de

v = (0, 1, 2, 3, 4).

Est-ce que v appartient à C ? Si non, le corriger.

Solution :
a) Un code linéaire C de longueur n sur un corps fini K est un sous-espace
de l’espace vectoriel K n . Ses paramètres sont sa longueur n, sa dimension
k et sa distance minimale, i.e.

d = d(C) = min d(c, c0 ).

c,c0 ∈C,c6=c0

Puisque une matrice génératrice est une matrice dont les lignes forment
une base de C, on a que la longueur de C est 5 et sa dimension est 3.
Pour calculer sa distance minimale, on calcule d’abord une matrice de
parité : par la Proposition 2.2, on a que
 
1 1 1 4 0
H=
1 2 3 0 4

est une matrice de parité pour C. Cette matrice n’a pas de colonnes
nulles, ni de couples de colonnes liés, donc la distance minimale est au
moins 3 par la Proposition 2.3. Mais toute ligne de la matrice génératrice
a poids 3, de manière que la distance minimale est exactement 3.
b) Dans C il y a 125 = 53 mots.
c) Au point a) on a calculé une matrice de parité H. On peut donc calculer
le syndrome de v avec H :

vH T = (0, 4).

Il est diffént du vecteur nul. Donc v n’appartient pas à C. On peut

remarquer facilement qu’il est égal à la dernière colonne de H. Ainsi

(0, 0, 0, 0, 1)H T = vH T .

Par conséquent, le mot corrigé est

v − (0, 0, 0, 0, 1) = (0, 1, 2, 3, 3).

Exercice 4.7. Soit C un [n, k, d] code sur F2 tel que C ⊆ C ⊥ (code auto-
orthogonal).
a) Montrer tout mot de C a poids pair.
b) Montrer que 1 = (1, 1, . . . , 1) ∈ C ⊥ .
c) Montrer que dim C ≤ n/2.
d) Montrer que si G est une matrice génératrice pour C, alors GGT est
égale à la matrice nulle k × k.
38 CHAPITRE 4. EXERCICES AVEC CORRECTION

e) En sachant que tout le mot non nul d’un code simplexe Sm a poids 2m−1 ,
montrer que, pour m ≥ 3, Sm ⊆ Hm (Hm est un code de Hamming).
Solution :
a) Tout mot c doit être orthogonal à soi même. Or, sur F2 on a 1 · 1 = 1, de
manière que wt(c) ≡ hc, ci mod 2. Ainsi, forcement le poids de c est pair.
b) Pour tout mot c ∈ C on a

hc, 1i ≡ wt(c) mod 2

et donc hc, 1i = 0 par le point a). Ainsi, par la définition du code dual,
1 ∈ C ⊥.
c) dim C ≤ C ⊥ = n − dim C. Ainsi 2 dim C ≤ n.
d) Le coefficient (i, j) de GGT est égale au produit scalaire de la i-ème ligne
de G fois la j-ème ligne de G. Puisque le code est auto-orthogonal, ce
produit est nul.
e) Puisque Hm est le dual d’un code simplexe, on doit juste montrer que Sm
est auto-orthogonal. Pour le faire, il suffit (par définition de code dual)
de montrer que si x, y sont deux mots de Sm , alors hx, yi = 0. Sur F2 on
a que hx, yi ≡ #{i|xi = 1 et yi = 1} mod 2. En plus

wt(x + y) = wt(x) + wt(y) − 2#{i|xi = 1 et yi = 1}.

Puisque wt(x+y), wt(x) et wt(y) sont divisibles par 4, on a que #{i|xi =

1 et yi = 1} est pair, de manière que hx, yi ≡ 0 mod 2.

Exercice 4.8. Soit C ⊆ F52 un code linéaire et soit

wC (x, y) := x5 + 2x4 y + x3 y 2 + x2 y 3 + 2xy 4 + y 5 = (x2 − xy + y 2 )(x + y)3

son polynôme énumérateur des poids.

a) Quels sont les paramètres de C ? Justifier.
b) Déterminer le polynôme énumérateur des poids de C ⊥ (justifier). Quelle
est donc la distance minimale de C ⊥ ?
c) Donner une matrice génératrice possible de C.
Solution :
a) La longueur de C est 5, qui est le degré de wC (x, y).
On a #C = 1 + 2 + 1 + 1 + 2 + 1 = 8 = 2dim C , de manière que dim C = 3.
On a A1 (C) = 2 6= 0, de manière que d(C) = 1.
Donc C est un [5, 3, 1] code
b) Par le Théorème 2.2 on a que
1
wC ⊥ (x, y) = · wC (x + y, x − y)
#C
1
= ((x + y)2 + (x + y)(x − y) + (x − y)2 )(2x)3 = x5 + 3x3 y 2 .
8
Donc A1 (C ⊥ ) = 0 et A2 (C ⊥ ) = 3 6= 0, de manière que d(C ⊥ ) = 2.
 39

c) On a que (1, 1, 1, 1, 1) ∈ C, car A5 (C) = 1. De plus A1 (C) = 2 et on peut

supposer que, à une permutation près, on a (1, 0, 0, 0, 0), (0, 1, 0, 0, 0) ∈ C.
Ce trois vecteurs sont linéairement indépendants, de manière que
 
1 0 0 0 0
G :=  0 1 0 0 0 
1 1 1 1 1

est une matrice génératrice possible de C.

Exercice 4.9. Soit n ≥ 3 un entier et soit C un [n, k, n − k + 1] code (i.e. C

est un code MDS binaire).
a) Montrer que C admet une matrice génératrice G0 en forme systématique.
b) Montrer que le poids de toute ligne de G0 est n − k + 1.
c) En déduire que k ∈ {1, n − 1, n} (i.e. C est MDS trivial).

Solution :
a) Soit G = [A|B] une matrice génératrice de C, où A est une matrice k×k et
B une matrice k×(n−k). On sait, par la Remarque 2.5, que rang(A) = k,
de manière que A est inversible. Soit G0 = A−1 G. Multiplier à gauche
pour une matrice inversible est équivalent à un changement de base de
C, donc G0 est une matrice génératrice de C. De plus, G0 = [Ik |A−1 B]
est en forme systématique.
b) Toute ligne l de G0 a au moins k − 1 zéros, de manière que wt(l) ≤
n − (k − 1). Or, l 6= 0 (en effet l est un vecteur d’une base de C) de
manière que wt(l) ≥ d(C) = n − k + 1. Donc wt(l) = n − k + 1.
c) Soit k ≥ 2 et soient l1 et l2 les deux premières lignes de G0 . On a donc

l1 = (1, 0, . . . , 0, 1, . . . , 1) et l1 = (0, 1, 0, . . . , 0, 1, . . . , 1).

| {z } | {z } | {z } | {z }
k−1 fois n−k fois k−2 fois n−k fois

Ainsi l1 + l2 = (1, 1, 0, . . . , 0) ∈ C.
| {z }
n−2 fois
Donc
d(C) = n − k + 1 ≤ 2 ⇔ k ≥ n − 1.

Exercice 4.10. Soit C ⊆ F16

2 un code avec matrice génératrice
 
1 0 0 0 1 1 1 1 0 1 1 0 0 1 0 0
 0 1 0 0 1 1 1 0 1 1 0 0 1 0 1 0 
 
 0 0
G :=  1 0 1 1 0 1 1 0 0 1 1 1 0 0 .

 0 0 0 1 1 0 1 1 1 0 1 1 0 0 1 0 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

a) Quels sont les paramètres de C ? Justifier.

b) Quels sont les paramètres de C ⊥ ? Justifier.
40 CHAPITRE 4. EXERCICES AVEC CORRECTION

c) Est-ce que le mot x := (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0) appartient à

C ? Justifier.
d) Quel est le mot y du code C le plus proche à x ? Justifier.

Solution :
a) La longueur de C est 16 et sa dimension est 5 (nombre de colonnes
 et de
H4 0
lignes de G réspectivement). On observe que G = , de manière
1 1
que C est un code RM(1, 4). Sa distance minimale est donc 8. Ainsi C
est un [16, 5, 8] code.
b) Par la Proposition 3.1, on a que C ⊥ est un code RM(2, 4), de manière
que C ⊥ est un [16, 11, 4] code.
c) Soit l5 la dernière ligne de G. On a que d(l5 , x) = 1 < 8 = d(C). Donc x
n’appartient pas à C, par définition de distance minimale.
d) On a déjà observé que l5 a distance 1 de x. S’il existait un autre y ∈ C
avec d(y, x) ≤ 1, alors on aurait d(y, l5 ) ≤ 1 + 1 = 2, ce qui donne une
contradiction. Donc l5 est le mot le plus proche à x.

Exercice 4.11. Soit C le code sur F7 dont une matrice génératrice est
 
1 0 0 0 6 2
0 1 0 0 2 2
G := 0
.
0 1 0 2 5
0 0 0 1 5 6

a) Quelle est la longueur de C ? Et sa dimension ? Combien y a-t-il de mots

dans C ? Justifier les réponses.
b) Montrer que la distance minimale de C est égale à 3.
c) Montrer que la distance minimale de C ⊥ est égale à 5.
d) Est-ce que v = (0, 6, 1, 0, 0, 4) appartient à C ? Si non, le corriger (c’est-à
dire, trouver le mot du code le plus proche à v).

Solution :
a) La longueur de C est 6, qui est le nombre de colonnes de G, sa dimension
est 4, qui est le nombre de lignes de G. Dans C il y a 74 = 2401 mots,
car la dimension est 4 et le corps est F7 .
b) Une matrice de parité pour C est (par la Proposition 2.2)
 
6 2 2 5 6 0
H := .
2 2 5 6 0 6

On remarque qu’il n’y a pas de colonnes nulles, donc la distance minimale

est au moins 2. On doit montrer qu’il n’existe pas deux colonnes linéai-
rement dépendantes. Appellons h1 , . . . , h6 les colonnes de H. Clairement
les couples hi , h6 , pour i ∈ {1, . . . , 5}, et hi , h5 , pour i ∈ {1, . . . , 4}, sont
linéairement indépendantes. Les couples hi , h2 , pour i ∈ {1, 3, 4} le sont
aussi, car tout multiple de h2 a les coefficients identiques. Finalement,
 41

on vérifie que le déterminant de [h1 , h3 ], [h1 , h4 et [h3 , h4 ] est différent de

0 dans F7 . Donc la distance minimale est au moins 3 par la Proposition
2.3. On cherche un mot de poids 3. N’importe quelle ligne de G (par
exemple) a poids 3, donc la distance minimale est 3.
c) Puisque 3 = 6 − 4 + 1, le code C est MDS. Par la Remarque 2.5, C ⊥ l’est
aussi. Donc sa distance minimale est égale à 6 − 2 + 1 = 5.
d) Le syndrome de v est s = Hv T = (0, 6)T 6= (0, 0)T , donc v n’appartient
pas à C. On remarque que s est la dernière colonne de H, de manière
que s = H(0, 0, 0, 0, 0, 1)T . Ainsi, le mot du code le plus proche à v est
(0, 6, 1, 0, 0, 3) = (0, 6, 1, 0, 0, 4) − (0, 0, 0, 0, 0, 1).

Exercice 4.12. Soit C un code linéaire sur F2 dont le polynôme énumerateur

des poids est
wC (x, y) = x8 + 14x4 y 4 + y 8 .
a) Combien y a-t-il de mots dans C ? Justifier.
b) Quel sont les paramètres de C ? Justifier.
c) Trouver une matrice génératrice pour C (justifier). En déduire que C est
forcement équivalent à RM(1, 3).
d) Trouver le polynôme énumerateur des poids de C ⊥ . Quelle est la distance
minimale de C ⊥ ?
e) Est-ce que v = (1, 1, 1, 0, 1, 1, 1, 1) appartient à C ? Si non, le corriger
(c’est-à dire, trouver le mot du code le plus proche à v).

Solution :
a) Le nombre de mots dans C est la somme des coefficients de wC (x, y), par
définition de polynôme de poids. Donc C a 16 mots.
b) Par définition de wC (x, y), la longueur de C est le degré de wC (x, y), i.e.
8. Soit k la dimension de C. On sait que 2k = 16, de manière que k = 4.
Finalement, on a que A1 (C) = A2 (C) = A3 (C) = 0 et A4 (C) = 14 6= 0,
de manière que la distance minimale de C est 4. Donc C est un [8, 4, 4]
code.
c) Soient c1 , c2 ∈ C de poids 4, c1 6= c2 . Le poids de c1 + c2 est forcement 4
ou 8. Dans le premier cas,

#(supp(c1 ) ∩ supp(c2 )) = 2 (4.1)

où supp(c) = {i | ci 6= 0}. Dans le deuxième cas, c1 + c2 = u = (1, . . . , 1),

qui est le seul mot de poids 8 (dans ce cas, c1 , c2 , u sont linéairement dé-
pendantes). Sans perte de généralité, on cherche une matrice génératrice
du code dont la dernière ligne est u. Donc les autres lignes ont poids 4
et elles doient satisfaire (4.1). Ainsi, à près d’équivalence, on a
 
1 1 1 1 0 0 0 0
0 0 1 1 1 1 0 0
G := 1 0 1 0 1 0 1 0 .


1 1 1 1 1 1 1 1
42 CHAPITRE 4. EXERCICES AVEC CORRECTION

On peut observer qu’une telle matrice est de la forme

H3 0T
 
.
1 1

qui est une matrice génératrice d’un code RM(1, 3).

d) On sait que RM(1, 3) est auto-dual. Ainsi wC ⊥ (x, y) = wC (x, y) et la
distance minimale de C ⊥ est 4.
e) Le mot v a poids 7, donc il n’appartient pas à C. La distance entre v et
u (défini ci-dessus) est 1, donc u est le mot du code le plus proche à v,
car la distance minimale est 4.

Exercice 4.13. Soit C le code linéaire sur F3 dont une matrice génératrice est
 
1 0 0 0 1 1
0 1 0 0 1 2
G= 0 0 1 0 2 2 .


0 0 0 1 2 1

a) Quel sont les paramètres de C ? Justifier.

b) Combien y a-t-il de mots dans C ? Justifier.
c) Trouver le polynôme des poids wC (x, y) de C. Justifier.
d) En sachant que le coefficient de x4 y 2 dans wC (x, y) est 4, trouver les
mots de poids minimal (non nuls) de C. Justifier.
Solution :
a) La longueur de C est 6 (nombre de colonnes) et sa dimension est 4
(nombre de lignes). La matrice de parité de C est, par la Proposition
2.2,  
1 1 2 2 2 0
H= .
1 2 2 1 0 2
On utilise le résultat de la Proposition 2.3 : il n’y a pas de colonnes
nulles, donc la distance minimale est au moins 2. On remarque que la
troisième colonne est 2 fois la première (et la quatrième colonne est 2 fois
la deuxième). Donc il y a (au moins) deux colonnes liées, de manière que
la distance minimale est 2.
b) Dans C il y a 34 = 81 mots, car 4 est la dimension de l’espace vectoriel
et 3 la cardinalité du corps.
c) Puisque #C = 81 est trop grande, nous pouvons plus facilement déter-
miner le polynôme des poids de C ⊥ et après utiliser le Théorème 2.2.
Puisque H (déterminée dans le point a)) est la matrice génératrice de
C ⊥ , on a que les mots de C ⊥ sont

c1 = (0, 0)G = (0, 0, 0, 0, 0, 0)

c2 = (0, 1)G = (1, 2, 2, 1, 0, 2)

c3 = (0, 2)G = (2, 1, 1, 2, 0, 1)
 43

c4 = (1, 0)G = (1, 1, 2, 2, 2, 0)

c5 = (1, 1)G = (2, 0, 1, 0, 2, 2)
c6 = (1, 2)G = (0, 2, 0, 1, 2, 1)
c7 = (2, 0)G = (2, 2, 1, 1, 1, 0)
c8 = (2, 1)G = (0, 1, 0, 2, 1, 2)
c9 = (2, 2)G = (1, 0, 2, 0, 1, 1)
On a wt(c1 ) = 0, wt(c5 ) = wt(c6 ) = wt(c8 ) = wt(c9 ) = 4 et wt(c2 ) =
wt(c3 ) = wt(c4 ) = wt(c7 ) = 5, de manière que

wC ⊥ (x, y) = x6 + 4x2 y 4 + 4xy 5 .

Ainsi, par le Théorème 2.2 (on utilise le fait que (C ⊥ )⊥ = C), on a que
1
wC (x, y) = w ⊥ (x + 2y, x − y) =
#C ⊥ C
1
= ((x + 2y)6 + 4(x + 2y)2 (x − y)4 + 4(x + 2y)(x − y)5 ).
9
d) Le coefficient de x4 y 2 dans wC (x, y) est 4, de manière qu’il y a 4 mots
de poids 2, qui est le poids minimal pour le point a). Déjà dans le point
a) on a observé deux couples de colonnes liées, ce qui nous donne les 4
mots de poids minimal :

(1, 0, 1, 0, 0, 0), (2, 0, 2, 0, 0, 0)

(0, 1, 0, 1, 0, 0), (0, 2, 0, 2, 0, 0).

44 CHAPITRE 4. EXERCICES AVEC CORRECTION
Bibliographie

[1] J. P. Escofier. Toute l’algèbre de la Licence. 2éme édition. Dunod, 2006.

[2] F. J. MacWilliams et N. J. A. Sloane. The theory of error-correcting codes.
Elsevier, 1977.
[3] W. C. Huffman et V. Pless. Fundamentals of error-correcting codes. Cam-
bridge University Press, 2010.

45