i i

“mathL3” — 2009/5/13 — 2:36 — page i — #1

i

Table des matières

1 Introduction à la théorie algébrique des codes correcteurs d’erreurs 1

I Théorie élémentaire des codes correcteurs . . . . . . . . . . . . . . . . . . . . . . 3
I.1 Formalisation mathématique . . . . . . . . . . . . . . . . . . . . . . . . . 3
I.2 Encodage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
I.3 Distance de Hamming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
I.4 Décodage par maximum de vraisemblance . . . . . . . . . . . . . . . . . . 8
I.5 Décodage par syndrome . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
II Constructions élémentaires de codes et bornes . . . . . . . . . . . . . . . . . . . . 11
II.1 Constructions génériques à partir de codes donnés . . . . . . . . . . . . . 11
II.2 Constructions de familles de codes classiques . . . . . . . . . . . . . . . . 13
II.3 Bornes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
III Quelques rappels sur les corps finis . . . . . . . . . . . . . . . . . . . . . . . . . . 20
IV Codes cycliques et codes BCH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
IV.1 Théorie élémentaire des codes cycliques . . . . . . . . . . . . . . . . . . . 22
IV.2 Borne BCH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
IV.3 Codes BCH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
IV.4 Codes de Reed-Solomon cycliques . . . . . . . . . . . . . . . . . . . . . . . 27
V Décodage des codes BCH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
V.1 Algorithme de Peterson . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
V.2 Décodage par l’algorithme d’Euclide étendu . . . . . . . . . . . . . . . . . 31
VI Codes de Reed-Solomon, codes alternants et codes de Goppa . . . . . . . . . . . 32
VI.1 Codes de Reed-Solomon et algorithme de Welch-Berlekamp . . . . . . . . 32
VI.2 Codes alternants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
VI.3 Codes de Goppa binaires . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
VII Décodage en liste des codes de Reed-Solomon . . . . . . . . . . . . . . . . . . . . 39
VII.1 Introduction au décodage en liste . . . . . . . . . . . . . . . . . . . . . . . 39
VII.2 Algorithme de Sudan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
VIII Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

Partie I Solutions des tests 44

Partie II Solutions des tests 45

Partie III Solutions des exercices 47

Partie IV Solutions des exercices 48

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page ii — #2

i

ii
Table des matières

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 1 — #3

i

Chapitre 1
I NTRODUCTION À LA TH ÉORIE ALG ÉBRIQUE DES CODES
CORRECTEURS D ’ ERREURS

a théorie des codes correcteurs d’erreurs a été introduite dans les années 1940 par Richard

L Hamming qui a proposé la notion de codes correcteurs d’erreurs, puis par Claude Shannon
qui a formalisé mathématiquement la théorie de l’information.
La théorie des codes a pour but, lors d’un envoi d’informations sur un canal sous forme
digitale (une suite de bits), de protéger cette information contre des dégradations extérieures
liées au canal. Plus précisément, si lors d’une transmission des bits sont modifiés, on souhaite
être capable de les retrouver et de les corriger, cette dernière opération étant appelée décodage.
Les applications sont très nombreuses puisque les codes correcteurs sont présents dans toute
utilisation nécessitant la sécurisation d’informations contre une dégradation extérieure ; on peut
citer par exemple les communications satellites, les modems, les CD ou DVD (rayures), la
télévision haute définition, etc. Mais les codes correcteurs sont aussi liés à d’autres parties des
mathématiques comme la combinatoire, la théorie des groupes ou la théorie des réseaux. Ainsi
il s’agit d’un champs disciplinaire ayant beaucoup de connexions avec des domaines très variés,
allant du plus théorique au plus pratique.
Concrètement, on procède par le schéma général (simplifié) suivant :

*&++,-&) *&++,-&) *&++,-&)

*&++,-&) !"#$%&'() &"#$%.)
/,",0) (&1')
2.#$%&'() %.#$%.)

Une information (un message M) est considérée comme une suite de k bits {0, 1} à laquelle
on va ajouter une redondance de r bits (encodage) pour former un mot du code. L’idée est que
l’ajout de redondance permet de pallier des erreur (des bits à 1 qui 2.#$%&'()
se transforment en 0 ou
!"#$%&'()
34343) lors de
inversement) du !"
34343
l’envoi du mot /,",0)
code sur le canal.33!433) 5%.6&#6&' !((&'()
*&++,-&) *&++,-&) *&++,-&)
Un exemple !"#$%&'()
*&++,-&) simple de code détecteur
&"#$%.)
/,",0)
d’erreurs est le code
(&1')de 2.#$%&'()
()%7&((&'(8)
parité : à une séquence de bits,
%.#$%.)
on ajoute un bit de redondance de sorte que la somme soit paire. De cette façon, si un bit est
modifié, on est capable de le voir puisque la somme des bits n’est plus paire. On dit qu’il s’agit
d’un code 1-détecteur d’erreurs car33333) 3"33") simplement 1 erreur au plus :
on est capable de détecter
343) !"#$%&'() 44444) /,",0) 444!4) 2.#$%&'() 343)
33333" 33"33"
2.#$%&'()
34343) !"#$%&'() 34343!" /,",0) 3!3433) 5%.6&#6&'() !((&'()
4)3)!) 4)3)3)
43) %7&((&'(8) 43)
!"#$%&'() 3)3)#) /,",0) 3)"#4) 2.#$%&'() 33)
33) 3)4)4))))))))))))"
!)#)4))))))))))))"
Dans ce cas, on est capable de deviner qu’il y a une erreur dans le message reçu, mais on ne
33333) 3"33")
peut pas 343)
savoir à quel!"#$%&'()
endroit. Il est44444)
possible, comme /,",0) on va le voir, de2.#$%&'()
444!4) faire mieux et de
343)corriger
les erreurs. 33333" 33"33"
Il existe divers types de canaux sur lesquels on peut envoyer une information. En fonction
du contexte et du canal, on pourra modéliser
4)3)!) le type d’erreurs
4)3)3) de manière différente. Le canal le
plus simple 43)est le canal binaire symétrique, où l’on considère 43)
p fixe de
!"#$%&'() 3)3)#) /,",0) 3)"#4)une probabilité
2.#$%&'()d’erreur33)
33) donc" 1 − p la probabilité "
3)4)4))))))))))))qu’un
transformation de 0 en 1 ou de 1 en 0, !)#et
)4)))))))))))) bit ne soit pas modifié.
On considère toujours une probabilité d’erreur p < 0, 5.
En pratique, p sera petit et le taux d’erreur que l’on voudra corriger dépendra des applications
considérées. Par exemple, pour la transmission de la voix humaine, on tolérera un taux d’erreur

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 2 — #4

i

de 10−4 (une erreur tous les 10 000 bits). Pour beaucoup d’applications, on demande un taux
d’erreurs de l’ordre de 10−6 , mais cela peut descendre à 10−9 ou moins pour des applications
très précises : par exemple, si l’on envoie un texte chiffré, on veut que la probabilité d’erreur soit
Partie . TABLE DES MATIÈRES

très faible pour être capable de le déchiffrer. Inversement, dans des contextes liés à des attaques
cryptographiques, on peut chercher à décoder des taux d’erreurs proches de 0, 5.
Remarque. En pratique, le canal binaire est rarement utilisé car il est peu réaliste. On utilise
souvent une modélisation dite canal à bruit blanc additif gaussien (BBAG) (avec le même type de
codes), dont l’exposition dépasse ce cours. Il existe aussi d’autres types de canaux correspondant
à diverses modélisations comme le canal à effacement, qui modélise le fait que, sur Internet, il
arrive que des paquets se perdent et donc que l’on obtienne des mots non plus avec des erreurs,
mais avec des effacements (les parties manquantes), ou encore le canal à évanouissement, où les
*&++,-&)
erreurs sur une coordonnée sont liées aux coordonnées adjacentes.
*&++,-&) *&++,-&) *&++,-&)
7) !"#$%&'() .$%/)
.,",0) 1(,"+23+)
4/#$%&'() 5&6')
8(,"+2&9(&)
Exemple 1.1. Supposons une probabilité d’erreur de 0, 1 sur un canal binaire symétrique ; la
probabilité d’envoyer 4 bits sans erreur est alors 0, 94 ≈ 0, 65, ce qui montre que la probabilité
de ne pas avoir d’erreur sur un message décroît rapidement.

On peut remarquer que le problème de la correction d’erreurs peut être très facilement résolu
:;:;:)
par la répétition !"#$%&'()
: ainsi d’un!"message
chaque bit :;:;: .,",0)
va être::!;::) 4/#$%&'()
répété k fois !((&'()un bit en
et l’on décodera
prenant simplement la valeur qui apparaît le plus souvent (décodage à la majorité) :

:::::) :"::")
:;:) !"#$%&'() ;;;;;) .,",0) ;;;!;) 4/#$%&'() :;:)
:::::" ::"::"

*&++,-&)
*&++,-&) *&++,-&) *&++,-&)
De cette 7) manière,!"#$%&'()
quitte à augmenter .,",0) répétitions, 4/#$%&'()
.$%/) le nombre de1(,"+23+) on peut arriver5&6')
à gérer to-
8(,"+2&9(&)
talement l’erreur. Mais cette solution est désavantageuse en termes de coût de communication
(nombre de bits à envoyer pour un message donné). Soient m le nombre de bits du message et
r la taille de la redondance en bits. La longueur du mot de code envoyé est alors n = k + r.

La théorie des codes consiste alors à trouver des codes tels que le nombre d’erreurs qui peut
être corrigé !"#$%&'()
:;:;:)est le plus !" à .,",0)
:;:;:avec
grand possible la fois un::!;::) 4/#$%&'() k/n !((&'()
taux de transmission le plus élevé
possible.

Voyons comment généraliser le principe du code de parité de façon à obtenir un code correc-
:::::) :"::")
teur. On suppose que l’on a 4 bits ;;;;;)
à envoyer auxquels on va ajouter 4 bits de parité (deux en
:;:) !"#$%&'() .,",0) ;;;!;) 4/#$%&'() :;:)
horizontal et deux en vertical) : :::::" ::"::"

;):)!) ;):):)
;:) ;:)
!"#$%&'() :):)#) .,",0) :)"#;) 4/#$%&'() ::)
::) :););))))))))))))"
!)#);))))))))))))"

S’il y a une erreur (et une seule) dans la transmission, on peut retrouver sa position en
calculant les bits de parité horizontaux et verticaux du message transmis. Ici, on mesure une
erreur sur le second bit de parité horizontal et sur le second bit de parité vertical ; on en déduit
que c’est (probablement) le quatrième bit du message originel qui a été transmis avec une erreur,
et on le corrige donc.
On obtient ainsi un code de longueur 8 qui est capable de corriger une erreur. Pour ce code, on
k
a k = 4, r = 4 et un taux de transmission de k+r = 1/2.

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 3 — #5

i

Test 1.1. de parité, que pour le code précédent, on est ca-

pable de corriger une erreur sur n’importe lequel
Montrer, en généralisant le point de vue du code des 8 bits.

Chapitre 1. Introduction à la théorie algébrique des codes correcteurs d’erreurs

k
Le taux de transmission du code précédent est k+r = 1/2. En fait, il est possible d’améliorer
ce taux à 4/7 tout en conservant la capacité à corriger une erreur.
Premier code de Hamming. Le code suivant a été introduit par R. Hamming en 1940. Il permet
de corriger une erreur pour 4 bits d’information, mais a seulement une redondance de 3 au lieu
de 4.

d3
p1 p2
d4
d2 d1

p3

Fig. 1.1. Premier code de Hamming.

Supposons que l’information soit représentée par les bits d1 , d2 , d3 , d4 ; on ajoute les bits de
parité p1 , p2 , p3 tels que les sommes p1 + d2 + d3 + d4 , d1 + p2 + d3 + d4 et d1 + d2 + p3 + d4
soient paires.

Test 1.2.
Montrer que ce code peut corriger une erreur.

I. Théorie élémentaire des codes correcteurs

I.1. Formalisation mathématique

L’outil de base de la théorie des codes est la notion de corps finis. On pourra consulter le
chapitre 4 du tome Mathématiques L2, Pearson Education, 2007, pour une introduction aux
corps finis et le tome Algèbre L3 chez le même éditeur, pour des approfondissements ; nous
proposons un résumé dans la section III page 20.
Dans ce qui suit, on notera Fq un corps fini à q éléments, où q = pr est une puissance d’un
nombre premier p.
Définition 1.2. (Code correcteur) Un code correcteur C sur Fq de longueur n est un sous-
ensemble de Fn
q . Les éléments de C sont appelés des mots.

Définition 1.3. (Code linéaire) Un code linéaire C sur Fq de longueur n et de dimension k

est un sous-espace vectoriel de Fn
q de dimension k. Un tel code est noté [n, k]q .

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 4 — #6

i

Dans ce qui suit, le terme espace ambiant désignera Fn

q . La longueur du code est la dimension
de l’espace ambiant.
Partie . TABLE DES MATIÈRES

Définition 1.4. (Matrice génératrice) Une matrice génératrice d’un code linéaire C est une
matrice dont les vecteurs lignes forment une base de l’espace vectoriel C.
Bien entendu, un code admet autant de matrices génératrices que de bases.
Remarque.
1. En théorie des codes, les vecteurs générateurs de la base sont notés en ligne (et non en
colonne).
2. Pour les codes binaires (c’est-à-dire définis sur F2 ), on note simplement [n, k], plutôt que
[n, k]2 , un code de longueur n et de dimension k.

I.2. Encodage
Soit C un code [n, k]q . Un message x est considéré comme un élément de Fkq . L’encodage est
donné par une application linéaire de Fkq dans Fn
q . L’image de x par cette application est un mot
du code C, l’encodage de x.
Étant donné une matrice génératrice G du code C, l’encodage de x est donné par le produit
matrice-vecteur x.G (où x est noté en ligne et, par construction, les lignes de G forment une
base de C).
L’encodage de x dépend du choix de la matrice génératrice utilisée. Nous verrons plus loin
comment l’on peut toujours faire en sorte que les k premières colonnes de la matrice génératrice
G forment la matrice identité k × k.
Exemple 1.5. Le code de parité binaire de longueur n est l’ensemble des mots de Fn 2 de
somme paire, donc comportant un nombre pair de 1. On vérifie aisément que c’est bien un
espace vectoriel.
En longueur 3, ce code a pour dimension 2. En effet, on connaît deux mots, linéairement
indépendants, ayant un nombre pair de 1 : 110 et 011. Ils engendrent un code contenu dans le
code de parité ; mais comme ce dernier ne peut être de dimension 3 (il n’est pas égal à F32 ), nos
deux mots forment une base du code de parité. Cela dit, le code de parité peut avoir d’autres
matrices génératrices comme
» – » –
1 1 0 0 1 1
ou .
1 0 1 1 1 0

Test 1.3. binaire de longueur n a pour dimension n − 1 et

est un code [n, n − 1].
Montrer que, généralement, le code de parité

Exemple 1.6. Soit C1 le code de matrice génératrice

2 3 0 1
1 0 0 1 0 c1
G = 4 0 1 0 1 1 5 = @ c2 A .
0 0 1 0 1 c3
X3
Le code C1 est composé de 23 mots : C1 = { ai ci | ai ∈ F2 }.
i=1

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 5 — #7

i

Test 1.4. haut est un code linéaire [7, 4]. Donner une ma-
trice génératrice de ce code.
Montrer que le code de Hamming défini plus

Chapitre 1. Introduction à la théorie algébrique des codes correcteurs d’erreurs

Définition 1.7. (Produit sur Fn q ) Par analogie avec le produit scalaire euclidien usuel, on
définit un produit sur Fn n
q . Pour x, y ∈ Fq , on a

X
n
x.y = xi yi .
i=1

Définition 1.8. (Code dual) Soit C un code [n, k]q . On définit le dual C ⊥ de C par

C ⊥ = {y ∈ Fn
q |x.y = 0, ∀x ∈ C}.

Le code C ⊥ est un code [n, n − k]q .

Définition 1.9. (Code autodual) Un code C est dit auto-orthogonal quand C ⊂ C ⊥ ; il est dit
autodual quand C = C⊥ .

Définition 1.10. (Matrice de parité) Soit C un code [n, k]q de matrice génératrice G. On
dit qu’une matrice H est une matrice de parité (ou matrice de contrôle de parité, ou matrice
duale) de C si H est une matrice génératrice du dual C ⊥ .
Comme le code dual est un espace vectoriel, il peut bien sûr avoir plusieurs matrices généra-
trices. Pour trouver le code dual, il suffit de résoudre le système G.xt = 0 pour x = (x1 , · · · , xn ).
L’ensemble des x solutions forme le code dual.

Test 1.5. Test 1.6.

Trouver une matrice génératrice pour le dual du
Montrer que x ∈ C ⇔ H.xt = 0.
code de matrice génératrice
2 3
0 1 0 0 1 1
G=4 1 1 0 0 1 0 5·
0 0 1 1 0 1

Pour encoder un message, il peut être très intéressant d’avoir une forme particulière pour la
matrice génératrice.
Définition 1.11. (Matrice génératrice sous forme systématique) On dit qu’une matrice
génératrice G d’un code est sous forme systématique quand G = [Ik , A], où Ik désigne la matrice
identité k × k et A est une matrice k × n − k.
Par abus de langage, on dit qu’un code est mis sous forme systématique s’il est donné par une
matrice génératrice qui est sous forme systématique.

Proposition 1.12. Quitte à permuter des colonnes, tout code C peut être mis sous forme
systématique.

Preuve. Une matrice génératrice d’un code [n, k] étant une base du code, en tant qu’espace
vectoriel, il existe nécessairement une sous-matrice k×k inversible dans cette matrice génératrice.
Puisque des combinaisons linéaires des lignes de la matrice génératrice ne modifient pas le code,
il existe donc une matrice génératrice du code comportant une sous-matrice identité k × k. On
peut alors se ramener à une forme systématique par permutation des colonnes. n

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 6 — #8

i

Proposition 1.13. Si C est un code [n, k]q de matrice génératrice G = [Ik , A], alors sa
matrice de parité est H = [−At , In−k ].
Partie . TABLE DES MATIÈRES

Preuve. On vérifie que G.t H = 0 et que H a la dimension voulue. n

I.3. Distance de Hamming

Définition 1.14. (Poids de Hamming) Le poids de Hamming d’un mot x de Fnq est le nombre
de coordonnées non nulles de x. On le note wH (x) (ou simplement w(x)).

Pour x, y ∈ Fn
2 , on définit le produit terme à terme par

déf
x ∗ y = (x1 y1 , · · · , xn yn ).

Par exemple, si x = (101001) et y = (110101), alors x ∗ y = (100001).

Lemme 1.15. Pour x, y ∈ Fn

2 , le poids de Hamming de la somme x + y est donné par

w(x + y) = w(x) + w(y) − 2w(x ∗ y),

où x ∗ y désigne le produit terme à terme.

Test 1.7. mots binaires x et y de poids multiples de 4 et

tels que le produit de x et y est nul, le poids de
Démontrer ce lemme. En déduire que, pour des x + y est aussi un multiple de 4.

Définition 1.16. (Polynôme énumérateur de poids) Pour un code C de longueur n, on

X
n
appelle polynôme énumérateur de poids le polynôme WC (x, y) = Ai xn−i yi , où Ai désigne le
i=0
nombre de mots de poids i du code.

Définition 1.17. (Distance de Hamming) La distance de Hamming entre deux mots x et y

est le nombre de lettres qui diffèrent entre x et y, c’est-à-dire

dH (x, y) = wH (x − y).

Théorème 1.18. La distance de Hamming dH définit une distance sur Fn

q.

Preuve. Vérifions les trois axiomes des distances. Pour x, y ∈ Fn

q , il est clair que dH (x, y) =
dH (y, x). Si dH (x, y) = 0, alors toutes les coordonnées sont identiques et donc x = y. Soient
x, y, z ∈ Fn
q ; montrons que dH (x, z) ≤ dH (x, y) + dH (y, z). La distance entre deux mots corres-
pond au nombre de coordonnées distinctes. Considérons la i-ième coordonnée ( 1 ≤ i ≤ n) ; si xi
et zi sont égaux, la contribution est nulle sur la i-ième coordonnée et la contribution de dH (x, y)
et dH (x, y) sur cette coordonnée est nécessairement plus grande. Maintenant si xi 6= zi , alors
xi 6= yi ou yi 6= zi (voire les deux) et donc la contribution de dH (x, y) + dH (y, z) sur la i-ième
coordonnée est au moins 1, ce qui prouve le résultat. n

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 7 — #9

i

Définition 1.19. (Distance minimale) La distance minimale d d’un code C est définie par

d(C) = minx,y∈C,x6=y dH (x, y).

Chapitre 1. Introduction à la théorie algébrique des codes correcteurs d’erreurs

Lemme 1.20. Pour un code linéaire C, la distance minimale d(C) est égale au plus petit
poids d’un mot (non nul) du code :

d(C) = minx∈C,x6=0 wH (x).

Test 1.8. ming H7 de matrice génératrice

1 0 0 0 0 1 1
2 3
Démontrer ce lemme.
6 0 1 0 0 1 0 1 7
G=4 .
Test 1.9. 0 0 1 0 1 1 0 5
0 0 0 1 1 1 1
Calculer la distance minimale du code de Ham-

Définition 1.21. On appelle code [n, k, d]q un code C de longueur n, de dimension k et de

distance minimale d sur Fq .

La notion de distance de Hamming est la notion fondamentale associée aux codes correcteurs ;
c’est elle qui dote l’espace ambiant d’une structure d’espace métrique.
Au-delà de la simple égalité de deux codes, on peut se poser la question de transformations qui
conservent cette notion de distance entre deux mots de l’espace. Remarquant que la permutation
de coordonnées est une telle transformation, on peut introduire une notion d’équivalence liée aux
permutations sur les n coordonnées d’un code. Cette notion d’équivalence est bien sûr moins
fine que l’égalité entre deux codes, mais elle est pertinente dans la mesure où elle conserve
globalement la distance entre deux mots de l’espace, et donc donne les mêmes capacités de
décodage pour un code donné.
Définition 1.22. (Codes équivalents) Deux codes binaires C1 et C2 sont dits équivalents
quand il existe une permutation P des coordonnées telle que tout mot de C1 permuté par P est
un mot de C2 .
Comme la permutation des coordonnées d’un mot ne change pas son poids de Hamming, et
que le polynôme énumérateur d’un code ne dépend que du poids des mots, on en déduit que deux
codes équivalents ont le même polynôme énumérateur des poids. En revanche, la réciproque est
fausse : deux codes peuvent avoir le même énumérateur des poids, mais être non équivalents.
Tout code est équivalent à un code qui peut être mis sous forme systématique. La notion
d’équivalence peut être généralisée en ajoutant le fait de pouvoir multiplier les colonnes d’un
code par un élément de Fq non nul.
Définition 1.23. On appelle permutations monomiales l’ensemble des transformations obtenues
en permutant les colonnes du code puis en multipliant les colonnes par des éléments non nuls du
corps.
Deux codes C1 et C2 sont dits monomialement équivalents quand il existe une permutation
monomiale permettant de transformer C1 en C2 .
Définition 1.24. Le groupe d’automorphismes monomiaux d’un code C est l’ensemble des per-
mutations monomiales laissant le code invariant.
Dans le cas d’un code binaire, on parle simplement de groupe d’automorphismes et l’ensemble
des permutations monomiales se limite aux permutations.

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 8 — #10

i

8
» –
Test 1.10. 0 1 1 0
sont distincts mais équiva-
1 0 0 1
Montrer que les
» codes de matrices généra- lents. Montrer que le groupe d’automorphismes
Partie . TABLE DES MATIÈRES

–
1 1 0 0 de C1 est le groupe de permutations engendré par
trices C1 = et C2 =
0 0 1 1 les trois permutations (1, 2), (3, 4) et (1, 3)(2, 4).

I.4. Décodage par maximum de vraisemblance

On se pose maintenant la question du décodage. Soit x un mot d’un code [n, k, d]q ; ce mot
est envoyé sur un canal. Lors de la transmission, des erreurs peuvent apparaître et on va recevoir
y = x + e, où e représente le vecteur d’erreurs reçu. Tous les mots du code sont à une certaine
distance de y (au plus n bien sûr). La question se pose de savoir, à partir de y (qui est un mot
de l’espace ambiant), à quel mot du code transmis il peut correspondre. Si l’on suppose que
l’erreur est a priori faible, il est naturel de postuler que le mot duquel on est parti est le mot du
code C le plus proche de y.

Définition 1.25. (Décodage au maximum de vraisemblance) Étant donné un code C de

longueur n et un mot y ∈ Fn q , on appelle décodage au maximum de vraisemblance de y le fait
d’associer à y un mot du code C le plus proche, pour la distance de Hamming, de y.

Decode(y, C) = x tel que dH (x, y) = minc∈C dH (c, y).

Dans le cas où plusieurs mots du code sont à la même distance, on en retourne un quelconque
dans cet ensemble.

Théorème 1.26. Soit C un code [n, k, d]q ; il permet de corriger, par décodage à maximum
de vraisemblance, au plus t = b d−1
2
c erreurs de manière univoque.


 
   
  





Fig. 1.2. Décodage jusqu’à t = b d−1

2
c erreurs.

Preuve. On considère les boules de rayon t = b d−1

2
c centrées sur les mots du code C (les anglo-
saxons parlent de sphères). Ce t est le plus grand rayon tel que ces boules ne s’intersectent pas.
Ainsi, à tout mot de l’espace inclus dans une des boules, on peut associer de manière univoque un
mot du code : le centre de la boule. Ces mots de l’espace correspondent par définition exactement
à tous les mots du code avec au plus t erreurs. n

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 9 — #11

i

Test 1.11. Montrer que ce résultat est aussi vrai pour des
codes non linéaires.

Chapitre 1. Introduction à la théorie algébrique des codes correcteurs d’erreurs

I.5. Décodage par syndrome
On va maintenant présenter une méthode générique de décodage des codes linéaires. Cette
méthode, appelée décodage par syndrome, est optimale en ce sens qu’elle décode tout mot au
maximum de vraisemblance : à tout mot de l’espace, on associe un mot de code le plus proche
au sens de la distance de Hamming. Néammoins, elle a une complexité exponentielle et donc ne
peut s’utiliser en pratique au-delà de codes de petites dimensions.
Définition 1.27. (Syndrome) Soit C un code [n, k, d]q de matrice de parité H. Le syndrome
d’un mot x de Fn t n−k
q est le produit H.x ∈ Fq .
Notons que si x ∈ C, alors son syndrome est nul (voir la définition 1.10 de la matrice de parité).
Définition 1.28. Soient C un code [n, k, d]q et a ∈ Fn
q . On définit le translaté de a par C
comme étant l’ensemble des mots {a + c|c ∈ C}.
Rappelons que l’on définit la relation ∼C d’équivalence modulo un espace vectoriel C par
x ∼C y ⇐⇒ x − y ∈ C.
Le translaté de a par C est sa classe d’équivalence modulo C, ce qui induit les propriétés suivantes.

Proposition 1.29.
1. Deux mots sont dans le même translaté si et seulement si ils ont le même syndrome.
2. Tous les translatés d’un code C ont le même nombre d’éléments |C|.
3. Deux translatés sont soit disjoints soit égaux.

Preuve. On a x ∼C y si et seulement si x−y ∈ C ; mais cela est équivalent à avoir H.(x+y)t = 0,

c’est-à-dire que x et y ont même syndrome. Les deux propriétés suivantes viennent du fait que
les translatés modulo C sont des classes d’équivalence pour ∼C . n

Les translatés de C forment une partition de Fn

q . L’ensemble des translatés est l’ensemble
q / ∼C , parfois noté aussi Fq /C.
quotient Fn n

Définition 1.30. (Représentant principal) À tout translaté, on peut associer un mot de plus
petit poids contenu dans le translaté. Ce mot est appelé représentant principal. Lorsqu’il existe
plusieurs choix pour ce mot, on en prend un quelconque parmi les mots de même poids possibles.
On peut alors créer une table de syndromes qui associe à chaque syndrome possible de Fn−k
q
un représentant principal pour le translaté correspondant.
Exemple 1.31. Par exemple, si l’on prend le code C de matrice génératrice
» –
1 0 1 1 1
G=
0 1 0 0 1
et de matrice de parité 2 3
1 0 1 0 0
H=4 1 0 0 1 0 5,
1 1 0 0 1
on peut construire la table de décodage par syndrome

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 10 — #12

i

10

syndrome représentant principal mots du translaté - associés au représentant principal

(000)t 00000 10111,01001,11110
(111)t
Partie . TABLE DES MATIÈRES

10000 00111,11001,01110
(001)t 01000 11111,00001,10110
(100)t 00100 10011,01101,11010
(110)t 11000 01111,10001,00110
(011)t 10100 00011,11101,01010
(101)t 01100 11011,00101,10010
(010)t 00010 10101,01011,11100

Méthode Décodage par syndrome

Pour un code de matrice de parité H, le décodage par syndrome consiste à décoder tout
mot reçu y en y − cl(y), où cl(y) désigne le représentant principal associé au syndrome
Hyt de y.

Théorème 1.32. Le décodage par syndrome est un décodage à maximum de vraisemblance.

Preuve. Un tel décodage décode y en un mot de C le plus proche de y. En effet, soit c =
y − cl(y) ∈ C obtenu par décodage par syndrome de y et soit c1 ∈ C, alors dH (y, c) ≤ dH (y, c1 )
car dH (y, c) = wH (y − c) = wH (cl(y)) ≤ wH (y − c1 ) = dH (y, c1 ) puisque y − c et y − c1
appartiennent au même translaté. n

Lemme 1.33. Le code C peut corriger jusqu’à t erreurs si et seulement si tous les mots de
poids au plus t sont des représentants principaux. En particulier, si C est un code [n, k, d]q , le
décodage par syndrome permet de décoder au maximum de vraisemblance de manière univoque
jusqu’à t = b d−1
2
c erreurs.

Preuve. Dans ce cas, le décodage par syndrome permet de retrouver de manière univoque tout
mot du code auquel on ajoute une erreur de poids au plus t. Le cas où plusieurs représentants
principaux (de même poids donc) sont possibles correspond au cas où l’on ne peut pas décoder
de manière univoque et donc où l’on ne décode pas. On a vu précédemment que si t ≤ b d−1 2
c,
il existait un mot de code unique le plus proche à distance t et donc un unique représentant
principal pour ce translaté. n

Exemple 1.34. Reprenons le code de l’exemple précédent pour lequel on a construit une
table des syndromes. Si l’on reçoit le mot y = 00111, on calcule le syndrome s = (111)t ; on va
voir dans la table le représentant principal (10000) et l’on décode y en y + (10000) = 10111.
Dans ce cas, on décode de manière univoque car il n’y a qu’un seul représentant principal
possible. Si, par exemple, on avait obtenu comme syndrome (011)t , il y aurait eu deux repré-
sentants principaux possibles et l’on aurait pu mal décoder. On remarque que pour ce code, la
distance minimale est 2 et donc que le code ne décode pas nécessairement de manière univoque
une erreur. Le théorème précédent montre en fait que dans le cas où le nombre d’erreurs à
corriger est inférieur ou égal à b d−1
2
c, il n’y a qu’un seul représentant principal pour les trans-
latés correspondant aux erreurs de poids inférieur ou égal à b d−1 2
c. Pour le cas où le nombre
d’erreurs est strictement plus grand que b d−1 2
c, il peut y avoir un ou plusieurs représentants
principaux.

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 11 — #13

i

11

Test 1.12. tel mot, le décodage est univoque. Montrer que

le mot (10010) a deux chances sur trois d’être
Reprendre la matrice précédente H. Décoder par mal décodé avec cette table de syndromes.

Chapitre 1. Introduction à la théorie algébrique des codes correcteurs d’erreurs

syndrome le mot (11010). Montrer que pour un

Le décodage par syndrome est donc un algorithme qui permet de décoder au maximum de
vraisemblance et de manière univoque jusqu’à t = b d−1 2
c erreurs. Cette méthode donne une
solution au problème du décodage, mais elle nécessite un nombre exponentiel d’opérations (de
l’ordre de O(2n )) : il faut écrire la table des syndromes, ce qui est lourd dès que les paramètres
grandissent.
La problématique de la théorie des codes correcteurs peut finalement être résumée à ce qui
suit.

Synthèse Problématique des codes correcteurs d’erreurs

1. Construire de bons codes : des codes tels qu’à la fois le taux k/n et d soient les plus
grands possibles. Avoir k/n grand assure une redondance relativement faible ; avoir d
grand assure un pouvoir de correction important.
Mais ces deux conditions sont antinomiques, car un taux k/n très grand correspond
intuitivement à un distance petite (ainsi pour k = n, on obtient d = 1 qui ne corrige
rien). Inversement, si l’on veut un code avec un d très grand, on peut prendre le code
à répétition [111111...1] qui effectivement corrige très bien, mais correspond à une
redondance trop importante.
2. Être capable de les décoder efficacement : idéalement en temps polynomial en n (la
longueur du code) et pas simplement par décodage par syndrome qui est exponentiel
en n.

Le reste de ce chapitre permettra de donner des exemples de tels codes.

II. Constructions élémentaires de codes et bornes

II.1. Constructions génériques à partir de codes donnés

II.1.1. Codes poinçonnés
Soit C un code [n, k, d]q donné par une matrice génératrice G. Le code poinçonné de C pour
la i-ième colonne est obtenu à partir de C en enlevant la colonne {i} à la matrice G.
Supposons que d ≥ 2. Le code poinçonné sur la i-ième colonne est un code [n − 1, k − 1, d 0 ]q ,
où la distance minimale d 0 vérifie d 0 = d − 1 s’il existe un mot de C de poids d avec une
coordonnée non nulle sur la i-ième colonne, et d 0 = d sinon.

II.1.2. Extension de codes

Il existe plusieurs façons d’étendre un code en ajoutant une colonne aléatoire, mais une
manière de procéder particulièrement intéressante consiste à ajouter à une matrice génératrice
une colonne de parité, de telle sorte que chaque nouvelle ligne ainsi obtenue ait une somme nulle.
Définition 1.35. Soit C un code [n, k, d]q . Le code étendu C^ est défini par

déf
X
n+1
C^ = {(x1 , · · · , xn , xn+1 ) | (x1 , · · · , xn ) ∈ C et xi = 0}.
i=1

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 12 — #14

i

12

Dans le cas binaire, si d est impair, le code étendu a pour distance minimale d + 1.
Partie . TABLE DES MATIÈRES

Test 1.13. donne comme code étendu un code H8 [8, 4, 4].

Donner l’énumérateur des poids du code étendu.
Montrer que le code de Hamming H7 [7, 4, 3]

II.1.3. Somme directe

On définit la somme directe de deux codes C1 [n1 , k1 , d1 ]q et C2 [n2 , k2 , d2 ]q par

déf
C1 ⊕ C2 = {(c1 |c2 ) | c1 ∈ C1 , c2 ∈ C2 },

où (c1 |c2 ) désigne la concaténation des deux mots c1 et c2 . Ce nouveau code est de longueur
n1 + n2 . Il est engendré (comme espace vectoriel) par les mots de la forme (b|0), b ∈ C1 et
(0| b), b ∈ C2 , et il est donc de dimension k1 + k2 .
Une matrice génératrice de la somme directe des codes est la somme directe de deux matrices
génératrices Gi des Ci , c’est-à-dire une matrice (n1 + n2 ) × (n1 + n2 ) diagonale par blocs avec
les Gi sur la diagonale.
La somme directe de deux codes satisfait la propriété intéressante suivante.

Lemme 1.36. Le polynôme énumérateur des poids d’une somme directe de codes C1 ⊕ C2
vérifie
WC1 ⊕C2 (x, y) = WC1 (x, y) ∗ WC2 (x, y).

Test 1.14.
Démontrer ce lemme.

II.1.4. Construction de Plotkin (ou construction (u|u + v))

Étant donné deux codes C1 et C2 de même longueur, la construction de Plotkin est le code
donné par
C = {(u|u + v)|u ∈ C1 , v ∈ C2 }.
En raisonnant comme pour la somme directe, on voit qu’il admet pour matrice génératrice
» –
G1 G1
.
0 G2

Cette construction est particulièrement intéressante pour le cas d’un code binaire. On peut
montrer par exemple que si C1 est le code de parité (vu dans la sous-section I.2) de longueur 4
(encore noté 14 ⊥ ) et C2 le mot tout à un de longueur 4, alors le code obtenu par cette construc-
tion est équivalent au premier code de Hamming étendu binaire [8, 4, 4] vu dans l’introduction.
Plus généralement, on a le résultat suivant pour les codes binaires.

Proposition 1.37. Soient C1 [n, k1 , d1 ] et C2 [n, k2 , d2 ] deux codes binaires de même lon-
gueur. La construction de Plotkin produit un code C[2n, k1 + k2 , min(2d1 , d2 )].

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 13 — #15

i

13

Preuve. La longueur du code et la dimension découlent directement de la matrice génératrice

du code construit.
Soit d la distance minimale du code. Comme il existe des mots de poids 2d1 et d2 , on a

Chapitre 1. Introduction à la théorie algébrique des codes correcteurs d’erreurs

d ≤ min(2d1 , d2 ). Soit c ∈ C un mot non nul s’écrivant c = (c1 |c1 + c2 ) pour ci ∈ Ci . Le poids
de Hamming de c vérifie

wH (c) = wH (c1 ) + wH (c1 + c2 ) = wH (c1 ) + wH (c1 ) + wH (c2 ) − 2wH (c1 ∗ c2 ),

d’après le lemme 1.15, soit

wH (c) = 2(wH (c1 ) − wH (c1 ∗ c2 )) + wH (c2 ) ≥ wH (c2 )

puisque wH (c1 ) − wH (c1 ∗ c2 ) ≥ 0. Donc, pour tout c ∈ C non nul, wH (c) ≥ wH (c2 ) ≥
min(2d1 , d2 ) et donc d ≥ min(2d1 , d2 ), ce qui montre le résultat. n

II.2. Constructions de familles de codes classiques

II.2.1. Codes de Hamming
On peut généraliser la construction simple de Hamming que nous avions vue, en petite
longueur, page 3. On commence par prouver le lemme suivant.

Lemme 1.38. Un code linéaire C a une distance minimale d si et seulement si sa matrice de

parité H a d colonnes dépendantes et aucun ensemble d’au plus d − 1 colonnes indépendantes,
et aucun sous-ensemble d’au plus d − 1 colonnes qui soient linéairement dépendantes.

Preuve. Si C a une distance minimale d, alors il existe un mot c de poids d tel que Hct = 0,
que l’on peut aussi voir comme une relation de dépendance entre d colonnes de H puisque c est
de poids d.
Réciproquement, s’il n’existe aucun ensemble d’au plus d − 1 colonnes indépendantes, il n’existe
pas de vecteur x de poids au plus d − 1 tel que Hxt = 0 et donc, de fait, pas de mot de poids
inférieur ou égal à d − 1 dans le code. n

Le code de Hamming se définit à partir de sa matrice de parité.

Définition 1.39. (Code de Hamming) Pour un entier r positif non nul, on construit une
matrice Hr à 2r − 1 lignes et r colonnes, dont les lignes sont les éléments non nuls de Fr2 .
On appelle code de Hamming binaire d’ordre r le code admettant Hr pour matrice de parité.

Lemme 1.40. Un code de Hamming binaire d’ordre r a pour paramètres [2r − 1, 2r − r − 1, 3].

Preuve. La longueur et la dimension du code dérivent des paramètres de Hr . Maintenant, par

construction, on ne peut trouver de relation de dépendance entre deux colonnes de Hr (comme
nous travaillons sur F2 , cela signifierait l’égalité de deux colonnes), et donc d’après le lemme
précédent, le code a pour distance minimale au moins 3. Comme on peut construire facilement
une relation de dépendance entre deux colonnes, par exemple (10..0) + (01..0) = (110..0), le code
a exactement 3 pour distance minimale. n

La famille des codes de Hamming constitue le premier exemple de famille infinie pouvant
corriger une erreur puisque d = 3 implique [(3 − 1)/2] = 1 d’après le théorème 1.26.

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 14 — #16

i

14

Test 1.15. tous les mots non nuls de F2 3 , on prend tous les
mots non nuls, mais à une constante multiplica-
Essayons de généraliser la construction de Ham- tive près. Par exemple, pour (10) et (20), on ne
Partie . TABLE DES MATIÈRES

ming sur F3 . On considère le corps F3 et m = 2. prendra qu’un seul représentant. Montrer que
Plutôt que de prendre comme colonnes du code l’on obtient alors un code [4, 2, 3]3 .

II.2.2. Codes de Golay

Le code de Golay binaire a été introduit par M. J. E. Golay en 1949 sous forme de séquence
pour les radars ; il peut être produit par de multiples constructions. Nous présentons ici une
méthode simple, due à V. Pless, qui permet aussi de prouver la distance minimale du code à la
main. On montrera ultérieurement que ce code est très bon.
Soit A une matrice de taille 11 × 11 construite de la façon suivante : on indice les colonnes
de 0 à 10 pour que les coordonnées xi (0 ≤ i ≤ 10) de la première ligne valent 1 si i est un carré
modulo 11 et 0.
On déduit les 10 lignes suivantes par permutations circulaires vers la gauche. On considère
alors la matrice 12 × 12 bordée à construite à partir de A, en ajoutant une colonne à gauche
de 1 et une ligne en haut de 1, sauf dans le coin supérieur gauche, où l’on met 0. On obtient
comme matrice
2 3
011111111111
6 111011100010 7
6
6 110111000101 7
7
6 101110001011 7
111100010110
6 7
6 7
6 111000101101 7
à = 6
6 110001011011
7.
7
100010110111
6 7
6 7
6
6 100101101110 7
7
6 101011011100 7
110110111000
4 5
101101110001

Définition 1.41. (Code de Golay G24 ) Soit à la matrice définie ci-dessus. Le code G24 de
déf
matrice génératrice G = [I24 |Ã] est appelé code de Golay binaire étendu G24 .

Théorème 1.42. Le code de Golay binaire étendu G24 a pour paramètres [24, 12, 8].
On obtient le code de Golay [23, 12, 7] en poinçonnant une colonne du code précédent.

Preuve. La preuve se déroule en plusieurs étapes. Tout d’abord, on vérifie facilement que le
code G24 est autodual. En effet, on commence par remarquer que le produit de la première ligne
de G avec une ligne quelconque de G est nul, puis que le produit de la seconde ligne de G avec
toutes les autres est nul et donc que, par cyclicité, le produit de deux lignes quelconques de G
est nul. La remarque précédente montre que le code G24 est inclus dans son dual. Comme la
dimension de G24 est 12 et que la dimension du dual est n − k = 24 − 12 = 12, le code est bien
égal à son dual, donc il est autodual.
Maintenant, comme le poids de chaque ligne de G est un multiple de 4 et que le code est au-
todual, on en déduit par le test 1.7 que tous les mots de G24 ont un poids multiple de 4. Étant
donné qu’il existe un mot de poids 8 (par exemple la deuxième ligne de G), la distance minimale
du code est soit 4 soit 8.
déf
La matrice à est symétrique donc, par la proposition 1.13, le code dual de G24 admet G 0 =
[Ã|I24 ] pour matrice génératrice. Ainsi, comme G24 est autodual, il peut s’écrire avec les deux
matrices génératrices G ou G 0 . On va maintenant montrer que le code ne peut contenir de mot

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 15 — #17

i

15

de poids 4 et donc qu’il a bien 8 pour distance minimale.

Soit c un mot du code de poids 4. On peut écrire c = (a, b), où a et b sont deux vecteurs de
longueur 12. Les possibilités pour wH (a) et wH (b) sont donc (0, 4), (1, 3), (2, 2), (3, 1) ou (4, 0).

Chapitre 1. Introduction à la théorie algébrique des codes correcteurs d’erreurs

Par symétrie entre G et G 0 (et donc entre a et b), on a uniquement à considérer les trois pre-
mières possibilités. Le cas wH (a) = 0 n’est pas possible car on obtiendrait le vecteur nul ; le
cas wH (a) = 1 correspond à la matrice G et donc on vérifie qu’il n’y a pas de mot de poids 4.
Maintenant pour le cas wH (a) = 2, obtenu par somme de deux lignes de G, on peut vérifier en
sommant la première ligne de G à toutes les autres que le poids du mot obtenu est au moins
8. On vérifie aussi que la somme de la seconde ligne avec toutes les autres a pour poids 8. La
cyclicité de A assure alors que, plus généralement, la somme de deux lignes de G a pour poids
8 et donc que le cas wH (a) = 2 n’est pas possible, ce qui assure que d = 8 pour ce code.

Si l’on poinçonne G24 sur une colonne quelconque, les matrices génératrices G et G 0 montrent
que nécessairement on va amputer une coordonnée non nulle d’un mot de poids 8 et que l’on va
obtenir un code [23, 12, 7]. n

Le code [23, 12, 7] construit ci-dessus est appelé code de Golay binaire.

Test 1.16. chaque ligne est obtenue à partir de la précé-

dente par permutation circulaire sur la gauche.
Soit a = (a0 , · · · , an−1 ). On construit la ma- Montrer que A est symétrique.
trice A = (aij )i,j=0...n−1 de taille n × n où

II.2.3. L’hexacode

Soit le corps à 4 éléments F4 = {0, 1, ω, ω2 } tel que ω3 = 1 et 1 + ω + ω2 = 0.

On appelle hexacode le code H6 de matrice génératrice

2 3
1 0 0 1 1 1
2 5
4 0 1 0 1 ω ω .
0 0 1 1 ω2 ω

Test 1.17.
Montrer que H6 est un code [6, 3, 4]4 .

II.2.4. Codes de Reed-Muller

Les codes de Reed-Muller ont été introduits à l’origine par D. E. Muller en 1954, puis Irving
S. Reed a donné une méthode de décodage la même année. Ces codes, de longueurs une puissance
de deux, ont été la première famille de codes pour lesquels on a pu décoder un nombre infini
d’erreurs. Ils ont été utilisé pour la sonde Mariner entre 1969 et 1973 pour transmettre des
photos de la planète Mars. Là encore, plusieurs constructions sont possibles. Nous donnons ici
une construction matricielle simple basée sur la construction de Plotkin vue ci-dessus.
Soit m un entier positif. Les codes de Reed-Muller sont des codes binaires de longueur 2m ,
indicés par un paramètre 0 ≤ r ≤ m. On note R(r, m) le code de Reed-Muller de longueur 2m
et d’indice r.

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 16 — #18

i

16

Définition 1.43. (Codes de Reed-Muller) Les codes de Reed-Muller R(r, m) sont définis
par récurrence comme
Partie . TABLE DES MATIÈRES

R(r, m) = {(u|u + v)|u ∈ R(r, m − 1), v ∈ R(r − 1, m − 1)},

m
où R(0, m) = (11 · · · 1), le code associé au mot tout à 1 de longueur 2m , et R(m, m) = F22 , de
matrice génératrice la matrice identité de dimension 2m .
Soit G(r, m) une matrice génératrice de R(r, m). On a alors
» –
G(r,m-1) G(r,m-1)
G(r, m) = .
0 G(r-1,m-1)

Exemple 1.44. Le code R(1,»2) construit

– à partir des codes R(0, 1) et R(1, 1) de matrices
1 0
génératrices respectives [11] et a pour matrice génératrice
0 1
2 3
1 0 1 0
4 0 1 0 1 5
0 0 1 1

et est un code [4, 3, 2].

Test 1.18.
Montrer que le code R(1, 3) est un code [8, 4, 4].

Théorème 1.45. Soient m et r deux entiers positifs, avec 0 ≤ r ≤ m.

1. Pour 0 ≤ i ≤ j ≤ m, on a R(i, m) ⊂ R(j, m).
Xr
!
m
(où m désigne le coefficient binomial Cim ).
` ´
2. La dimension de R(r, m) est i
i=0
i
3. La distance minimale de R(r, m) est 2m−r .

Preuve. Le premier point se montre par une récurrence immédiate à partir de la construction.
Le point 2) s’obtient aussi par récurrence à partir ´de la
`nconstruction et de la propriété sur les
coefficients binomiaux du triangle de Pascal : n+1
` ´ ` n ´
k+1
= k
+ k+1
.
Pour le point 3), on utilise le résultat sur la distance liée à la construction de Plotkin (proposition
1.37). La propriété est vraie pour m = 1. Supposons qu’elle soit vraie jusqu’à m − 1 pour tout r.
Soit le code R(r, m) ; ce code est obtenu par la construction de Plotkin à partir de deux codes
R(r, m − 1) et R(r − 1, m − 1) de distance minimale respective 2m−1−r et 2m−1−(r−1) = 2m−r
par hypothèse de récurrence. Nous avons vu à la proposition 1.37 que la distance minimale du
nouveau code était min(2.2m−1−r , 2m−r ) = 2m−r , ce qui montre le résultat.
n

Test 1.19. Écrire une matrice génératrice du code R(1, 4).

Montrer que c’est un code [16, 5, 8].

Remarque. Pour la sonde Mariner, c’est le code R(1, 5) [32, 6, 16] qui corrige 7 erreurs qui a
été utilisé.

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 17 — #19

i

17

II.3. Bornes
Il existe plusieurs type de bornes pour les codes ; nous présentons ici les bornes principales.

Chapitre 1. Introduction à la théorie algébrique des codes correcteurs d’erreurs

II.3.1. Borne de Hamming

Théorème 1.46. (Borne de Hamming) Soient n et d deux entiers positifs et t = b d−1 2

c.
Soit Aq (n, d) (respectivement Bq (n, d)) le nombre maximum de mots que peut contenir un
code (respectivement un code linéaire) de longueur n et de distance minimale d, alors
qn
Bq (n, d) ≤ Aq (n, d) ≤ ·
X
t
!
n i
(q − 1)
i=0
i

Preuve. Soit un code C de longueur n et de distance d avec Aq (n, d) mots. Les boules B(c, t)
centrées sur les mots c du code et de rayon t sont disjointes (car sinon il existerait deux mots à
distance strictement inférieure à d) et donc la réunion de toutes les boules disjointes B(c, t) est
un ensemble d’éléments de l’espace contenu dans Fn q . Les éléments d’une boule sont composés
des mots à distance 0 du centre, ainsi que des mots à distance 1, jusqu’à la distance ` ´ t. Le
nombre de mots à distance 0 est 1, le nombre de mots à distance 1 est n(q − 1) = n 1
(q − 1).
Plus généralement, le nombre de mots à distance i vaut ni (q − 1)i , le nombre de choix pour
` ´

l’emplacement de l’erreur fois le nombre de possibilités pour l’erreur en une coordonnée donnée.
On obtient donc! Aq (n, d) boules disjointes avec le même nombre d’éléments, ce qui donne
Xt
n
Aq (n, d) (q − 1)i ≤ qn . De plus, on a trivialement Bq (n, d) ≤ Aq (n, d), ce qui donne
i=0
i
le résultat. n

Définition 1.47. (Code parfait) Un code qui vérifie l’égalité dans le théorème précédent est
appelé un code parfait.
Le fait qu’un code soit parfait correspond au fait que, pour un tel code, tous les mots de
l’espace sont décodables de manière univoque, c’est-à-dire que tous les mots de l’espace sont
contenus dans la réunion des boules de rayon t = b d−1
2
c centrées sur les mots du code (ce qui
n’est pas du tout le cas en général).
27
Exemple 1.48. Le code de Hamming binaire [7, 4, 3] est parfait car 24 = . On en
1+(7
1)
déduit que A2 (7, 3) = 16 car il y a une borne sur le nombre de mots maximum et un code qui
l’atteint.

Test 1.20. Test 1.21.

Montrer que tous les codes de Hamming sont Un code de distance minimale paire 2r peut-il
parfaits. être parfait ?

Plus généralement, on appelle rayon d’empilement rp (C) d’un code C le plus grand rayon
tel que toutes les boules de rayon rp (C) centrées sur des mots de codes sont disjointes. Pour un
code linéaire [n, k, d]q , on a rp = b d−1
2
c.
On peut alors aussi définir naturellement le problème dual.
Définition 1.49. (Rayon de recouvrement) Le rayon de recouvrement rc (C) d’un code est
le plus petit rayon r tel que la réunion des boules B(c, r) (pour c parcourant tous les mots du
code) recouvre tout l’espace.

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 18 — #20

i

18

Test 1.22. Montrer que re (C) ≤ rc (C). Quand sont-ils

égaux ?
Partie . TABLE DES MATIÈRES

II.3.2. Borne de Singleton

Théorème 1.50. (Borne de Singleton) Soit C un code [n, k, d]q . La distance minimale d
du code C vérifie la majoration d ≤ n − k + 1.

Preuve. À permutation près, le code C peut s’écrire sous la forme systématique G = [Ik |A],
où A est une matrice k × n − k. En notant a1 la première ligne de A, le poids de la première
ligne de G est donc 1 + wH (a1 ) ≤ 1 + (n − k). Par définition, on a d ≤ wH (c) pour tout mot
du code, d’où le résultat. n

Définition 1.51. (Codes MDS) Les codes satisfaisant l’égalité dans le théorème précédent
sont dits codes à distance maximum séparable (MDS).

On peut citer comme exemple non trivial, l’hexacode [6, 3, 4]4 sur F4 vu dans la section
précédente. Un autre exemple de codes MDS est la famille des codes de Reed-Solomon que l’on
verra plus tard.

II.3.3. Borne de Gilbert-Varshamov

Les bornes vues précédemment sont des bornes supérieures. Nous montrons ici la borne de
Gilbert-Varshamov introduite en 1952, dans des contextes différents et séparément par Gilbert
et Varshamov.
On aura besoin du lemme suivant. Rappelons que l’on note Aq (n, d) le nombre maximal
possible de mots pour un code sur Fq de longueur n et de distance minimale d.

Lemme 1.52. Soit C un code linéaire de longueur n, de distance minimale d et tel que C
contient Aq (n, d) mots. Le rayon de recouvrement de C est alors au plus d − 1.

Preuve. Supposons que rc (C) ≥ d, alors il existe un mot x de l’espace Fq − C dont la distance
à chaque mots de C est au moins d (sinon on aurait rc (C) < d). On peut alors construire le code
C 0 = C ∪ x}. Ce code a une distance minimale au moins de d en raison de la condition sur le
rayon de recouvrement et contient |C| = Aq (n, d) + 1 mots. Or, comme Aq (n, d) est maximal,
ce n’est pas possible, donc on a rc (C) ≤ d − 1. n

Nous pouvons maintenant établir la borne de Gilbert-Varshamov.

Théorème 1.53. (Borne de Gilbert-Varshamov) Soit C un code de longueur n et de

distance minimale d. On a alors
qn
≤ Aq (n, d).
X
d−1
!
n i
(q − 1)
i=0
i

Preuve. Soit C un code de longueur n et de distance minimale d contenant Aq (n, d) mots.

Par définition du rayon de recouvrement, la réunion des boules de rayon rc , centrées sur les

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 19 — #21

i

19

mots du code, recouvre tout l’espace Fn

q.D’après le lemme précédent, le rayon de recouvrement
de C est au plus d − 1 et donc la réunion des B(c, d − 1) recouvre l’espace Fn
q , soit

Chapitre 1. Introduction à la théorie algébrique des codes correcteurs d’erreurs

qn
Aq (n, d) ≥ .
X
d−1
!
n i
(q − 1)
i=0
i

Ce théorème n’est pas constructif. En pratique, les meilleurs codes connus dans le cas binaire
sont des codes réalisent, à peu de chose près, l’égalité pour cette borne. En particulier, on peut
prouver, mais cela dépasse l’objet de ce cours, que des codes aléatoires binaires (des codes définis
par une matrice génératrice dont tous les coefficients sont pris soit à 0 soit à 1 avec la même
probabilité 1/2) satisfont cette borne inférieure, asymptotiquement, presque tout le temps.

Test 1.23. milaire au cas Aq (n, d), prouver que B2 (n, d)

vérifie la même inégalité que A2 (n, d) dans la
Montrer que l’on peut, par une preuve très si- borne de Gilbert-Varshamov.

P
la ´formule de Stirling et le fait que dans la somme d−1
`n´
Remarque. En utilisant
` n i=0 i
le terme
dominant correspond à d−1 , on peut obtenir une bonne approximation asymptotique de la
P
somme d−1
`n´
i=0 i
en
!
n d
≈ nH2 ( n ) ,
d

pour H2 (x) = −xlog2 (x) − (1 − x)log2 (1 − x). Cette approximation permet d’avoir une idée des
paramètres d’un code binaire linéaire [n, k, d] satisfaisant la borne de Gilbert-Varshamov. Pour
un tel code C, on a

{Nombre de mots d’une boule de rayon d − 1} × 2k ≈ 2n ,

ce qui donne, en utilisant l’approximation pour la somme de coefficients binomiaux,

d
nH2 ( n ) .2k ≈ 2n

et donc
k
d ≈ nH−1
2 ( ).
n
Cela montre donc que, pour un taux k/n fixé, les codes satisfaisant la borne de Gilbert-
Varshamov (dont on sait qu’il en existe, même si la borne n’est pas constructive) ont une
distance qui augmente linéairement avec n. Par exemple, pour un code de taux 1/2, la borne
prouve l’existence de codes binaires [n, n/2, δn] avec δ = H−1
2 (1/2) ≈ 0, 11.
Plus généralement, on dit qu’une famille de codes dont les paramètres sont de la forme [n, Rn, δn],
pour n tendant vers l’infini, est asymptotiquement bonne. Cela signifie que, pour un taux k/n
fixé, la distance croîtlinéairement par rapport à la longueur, ce qui est le mieux que l’on puisse
obtenir.

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 20 — #22

i

20

III. Quelques rappels sur les corps finis

Partie . TABLE DES MATIÈRES

Dans cette section, nous rappelons des notions sur les corps finis nécessaires pour considérer
les codes cycliques que l’on verra à la section suivante. On pourra consulter le chapitre 4 du
tome Mathématiques L2 pour une introduction aux corps finis et le tome Algèbre L3, chez le
même éditeur, pour des approfondissements et les preuves de ce que nous présentons ci-dessous.
Il existe deux types de corps finis : les corps avec p éléments où p est premier (ces corps sont
construits en considérant le quotient Z/pZ), et les corps sur des extensions qui sont construits
comme quotients Fq [x]/(f(x)) de Fq [x] par (l’idéal engendré par) un polynôme f(x) irréductible
de degré r de Fq [x]. Ici, Fq désigne un corps fini donné, qui peut être de la forme Fp (pour p
premier) ou bien construit lui-même en tant qu’extension de Fp . Dans tous les cas, le cardinal
q du corps est une puissance d’un nombre premier p.
Par exemple, si l’on prend F2 le corps à deux éléments {0, 1} et x2 + x + 1 irréductible de degré 2
déf
sur F2 [x], le corps F4 = {0, 1, w, w2 } peut s’obtenir comme F2 [x]/(x2 +x+1) ; on peut identifier
x à w, où la somme et la multiplication se font modulo x2 + x + 1. Tout élément de F4 peut
s’écrire comme un polynôme α + βw de degré 1 avec α et β dans F2 . Ainsi, modulo x2 + x + 1,
on obtient w2 = 1 + w et w.(1 + w) = w + w2 = 1.

Théorème 1.54. Tout corps fini Fq admet un élément primitif β, c’est à dire un élément β
tel que
Fq = {0, 1 = β0 , β, β2 , · · · , βq−2 }.

Une notion importante pour un élément α de Fq est la notion de polynôme minimal mα (x),
c’est-à-dire le polynôme unitaire de plus petit degré dont α est racine. On a le théorème suivant.

Théorème 1.55. Soient Fqr un corps fini et α un élément de ce corps de polynôme minimal
mα (x) ∈ Fq [x] sur Fq , alors :
1. mα (x) est irréductible dans Fq [x] ;
2. si α est une racine d’un polynôme g(x) de Fq [x], alors mα (x) divise g(x) ;
r
3. mα (x) divise xq − x ;
4. le degré de mα (x) est au plus r.

Une autre notion utilisée pour la suite est la notion de classe cyclotomique. On remarque
tout d’abord que si α est une racine d’un polynôme f(x) sur Fqr , puisque (x + y)q = xq + yq ,
alors f(αq ) = f(α)q = 0. Plus généralement, si α est un zéro d’un polynôme f(x) à coefficients
2
dans Fq , alors {αq , αq , . . .} sont aussi des zéros de f(x).

Définition 1.56. (Classe cyclotomique) Soient q une puissance d’un premier p et a ∈

{0, · · · , qr − 1} un entier.
On appelle q-classe cyclotomique de a modulo qr − 1 l’ensemble
déf
Ca = {a, aq, aq2 , · · · , aqm−1 },

où m est la plus petite valeur non nulle telle que a ≡ aqm (mod qr − 1).
Soit β un élément primitif du corps Fqr . Une classe cyclotomique Ca rassemble tous les éléments
βj , pour j ∈ Ca , ayant le même polynôme minimal sur Fq .

Lemme 1.57. Pour un corps Fqr , le cardinal d’une classe cyclotomique Ca divise r.

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 21 — #23

i

21

Preuve. À toute classe cyclotomique Ca de n éléments, on peut associer un polynôme minimal

Q
mα (x) associé à un élément α de Fqr en prenant mα (x) = j∈Ca (x − αj ) ; par construction
de la classe cyclotomique, on a mα (x) ∈ Fq [x]. On peut alors construire un sous-corps de Fqr

Chapitre 1. Introduction à la théorie algébrique des codes correcteurs d’erreurs

en prenant Fq [x]/(mα (x)). Comme mα (x) a pour degré n, ce corps est isomorphe à Fqn et est
inclus dans Fqr . Or Fqn sous-corps de Fqr implique que n divise r. n

Exemple 1.58. Sur F24 , les 2-classes cyclotomiques modulo 15 sont C0 = {0}, C1 =
{1, 2, 4, 8}, C3 = {3, 6, 12, 9}, C5 = {5, 10} et C7 = {7, 14, 13, 11}.
On vérifie que le cardinal de chaque classe cyclotomique (1, 2 ou 4) divise 4.

Rappel Racine n-ième de l’unité

Soient Fqr un corps et α un élément de ce corps. On dit que α est une racine n-ième de
l’unité si la plus petite valeur de m telle que αm = 1 est n.

Voyons comment construire, pour tout corps fini Fq , une extension de ce corps qui contient
une racine n-ième.
Définition 1.59. Soient Fq un corps et 1 ≤ n ≤ q − 1. On appelle ordre de n sur q, noté
ordq (n), la plus petite valeur de m telle que n divise qm − 1.
La définition précédente assure que pour n fixé et un corps Fq fixé, on peut trouver une ex-
tension Fqordq (n) qui admet une racine n-ième. Précisément, si l’on note β une racine primitive
qordq (n) −1
de Fqordq (n) , α = β n est une racine n-ième dans cette extension.
Nous avons construit la notion de q-classe cyclotomique modulo qr − 1 ; voyons comment
généraliser cette construction modulo des n quelconques. Une q-classe cyclotomique Ca modulo
n est l’ensemble Ca = {a, aq, aq2 , · · · , aqm−1 }, où m est la plus petite valeur non nulle telle
que aqm ≡ a (mod n).
On a alors le théorème suivant qui sera largement utilisé dans le chapitre suivant.

Théorème 1.60. Soient α une racine n-ième de l’unité avec α ∈ Fqordq (n) et mαi (x) le
polynôme minimal associé à αi , alors

xn − 1 = Πi∈I mαi (x),

où I est un ensemble de représentants des q-classes cyclotomiques modulo n.

Exemple 1.61. Soient n = 13 et q = 3, alors les 3-classes cyclotomiques modulo 13 sont

C0 = {0}, C1 = {1, 3, 9}, C2 = {2, 6, 5}, C4 = {4, 12, 10} et C7 = {7, 8, 11}. Cette décomposition
implique que x13 −1 se décompose dans Fq [x] comme le produit de x−1 et de quatre polynômes
de degrés 3.

Définition 1.62. Soient α une racine n-ième de l’unité dans une extension Fqordq (n) de Fq
et g(x) ∈ Fq [x] un polynôme qui divise xn − 1. L’ensemble Z des zéros de g(x) est l’ensemble
des i tels que αi est racine de g(x).
L’ensemble des zéros correspond à {αi } pour i dans la réunion des q-classes cyclotomiques
associées à la décomposition de g(x) dans le théorème précédent.

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 22 — #24

i

22

Test 1.24. miques modulo 9. Factoriser x9 − 1 sur F2 .

Test 1.26.
Calculer les 2-classes cyclotomiques modulo 15.
Partie . TABLE DES MATIÈRES

Test 1.25.
Construire le corps F8 comme une extension de
F2 de degré 3.
Calculer ord2 (9). Calculer les 2-classes cycloto-

IV. Codes cycliques et codes BCH

IV.1. Théorie élémentaire des codes cycliques

De la même façon qu’ajouter de la structure aux codes non linéaires permet d’obtenir des
codes linéaires, plus faciles à manipuler de par leur matrice d’encodage, on peut se poser la
question d’ajouter de la structure aux codes linéaires. C’est l’idée des codes linéaires cycliques
qui sont encore plus structurés que les codes linéaires.

Définition 1.63. (Code cyclique) Un code C est dit cyclique si, pour tout mot c =
(c0 , c1 , · · · , cn−1 ) de C, le mot c 0 = (cn−1 , c0 , c1 , · · · , cn−2 ) appartient aussi au code C.

Bien qu’il soit possible qu’un code soit cyclique et non linéaire, on ne considère dans la suite
que le cas des codes cycliques linéaires.
Si l’on prend un mot quelconque et que l’on regarde le code linéaire engendré par ses permu-
tations circulaires, on obtient en général tout l’espace ou le code des mots de poids pair, dans le
cas d’un mot binaire de poids pair ; mais, dans certains cas, on obtient des codes de dimensions
bien plus petites. Par exemple, le code linéaire engendré par les permutations circulaires du mot
(1, 1, 0, 1, 0, 0, 0) est un code linéaire cyclique de dimension strictement inférieure à 7.

Test 1.27. tions circulaires de (1, 1, 0, 1, 0, 0, 0). Quels sont

les paramètres du code ainsi construits ?
Construire le code engendré par les permuta-

On peut mieux appréhender les codes cycliques en se plaçant d’un point de vue polynomial.
On associe au mot a = (a0 , a1 , · · · , an−1 ) de longueur n sur Fq le polynôme a(x) = a0 + a1 x +
· · · + an−1 xn−1 ; dans la suite, on identifiera un mot a à sa représentation polynomiale a(x).
Dans ce contexte, on peut exprimer le fait qu’un code soit cyclique par le fait que, représenté
polynomialement, il soit stable par multiplication par x dans l’anneau quotient Fq [x]/(xn − 1) ;
en effet, si c = (c0 , c1 , · · · , cn−1 ) = c(x) = c0 + c1 x + · · · + cn−1 xn−1 , alors
déf
c̃ = (cn−1 , c0 , c1 , · · · , cn−2 ) = cn−1 + c0 x + c1 x2 + · · · + cn−2 xn−1 = xc(x) − cn−1 (xn − 1).

En d’autres termes, les codes cycliques linéaires sont des idéaux de Fq [x]/(xn − 1). On a alors
le théorème suivant.

Théorème 1.64. Soit C un code cyclique linéaire de longueur n et de dimension k sur Fq ,

déf
où les mots de C sont considérés comme des polynômes, éléments de Fq [x] = Fq [X]/(Xn −1).
Il existe dans C un unique polynôme unitaire g(x), non nul de plus petit degré. Il vérifie :
1. g(x) divise tout mot c(x) de C ;
2. g(x) divise Xn − 1 dans Fq [X] ;
3. deg (g(x)) = n − k.

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 23 — #25

i

23

Le polynôme g ainsi défini est appelé polynôme générateur du code C.

Preuve. Il existe au moins un polynôme unitaire de plus petit degré de C puisque les degrés

Chapitre 1. Introduction à la théorie algébrique des codes correcteurs d’erreurs

possibles sont entiers et bornés par 1. Supposons qu’il existe deux tels polynômes unitaires g1
et g2 ; alors on peut toujours construire un polynôme unitaire de la forme a(g1 − g2 ) (pour
a ∈ Fq ) qui appartient au code et qui est de degré strictement inférieur à deg (g1 ). Mais puisque
deg (g1 ) = deg (g2 ) est le plus petit degré possible, on obtient une contradiction et donc g(x)
est unique. Pour 1), soit c(x) un mot non nul du code, alors si l’on fait la division euclidienne de
c(x) par g(x), on obtient c(x) = g(x)q(x)+r(x) avec deg (r(x)) < deg (g(x)) ou r(x) = 0. Comme
le code est cyclique et que g(x) ∈ C, la multiplication de g(x) par xj pour j ≤ n − 1 − deg (g(x))
est toujours un mot du code et donc g(x)q(x) ∈ C qui donne r(x) ∈ C. Mais comme g(x) est
de degré minimal, r(x) est nécessairement nul, ce qui prouve le résultat. Soit maintenant c un
mot du code tel que cn−1 = 1, alors comme g(x) divise c(x) et son décalé de une coordonnée
c 0 (x) = xc(x) − cn−1 (xn − 1), g(x) divise xn − 1 ce qui prouve 2). Tout mot du code peut être
vu comme un polynôme de degré au plus n − 1, multiple d’un polynôme de degré deg (g(x)) ;
ces polynômes peuvent donc s’écrire sous la forme g(x)h(x) pour deg (h) ≤ n − 1 − deg(g(x)).
Il y a donc exactement qn−deg(g(x)) mots possibles qui, par construction, sont tous distincts et
donc la dimension du code est k = n − deg(g(x)), ce qui donne 3) et achève la preuve de ce
théorème. n

Le théorème précédent montre que le bon contexte pour étudier les codes cycliques est
l’anneau Fq [x]/(xn − 1), comme le montre la proposition suivante.

Proposition 1.65. Les codes cycliques sont exactement les idéaux de l’anneau Fq [x]/(xn −1).

Preuve. Dans l’anneau Fq [x] = Fq [x]/(xn − 1), la permutation circulaire, à droite, d’un mot
du code est égale à la multiplication par x. En effet, le théorème précédent montre qu’un code
cyclique est un idéal de Fq [x]/(xn − 1). Réciproquement, les idéaux de Fq [x]/(xn − 1) sont
engendrés par les diviseurs de (xn − 1) et chacun des diviseurs de (xn − 1) engendre un code
cyclique. n

En d’autres termes, l’étude des codes cycliques se ramène à l’étude des diviseurs de xn −1 qui
sont en bijection avec l’ensemble des codes cycliques. Pour éviter le cas des diviseurs multiples,
on se place par la suite dans le cas où la caractéristique du corps et la longueur du code sont
premiers entre eux.

Exemple 1.66. Prenons n = 7. Sur F2 , les diviseurs irréductibles de x7 − 1 sont x + 1, x3 +

x2 + 1, x3 + x + 1. Les 23 diviseurs de x7 − 1 peuvent se déduire de ces polynômes ; il y a
donc 8 codes cycliques de longueurs 7 sur F2 . En particulier, le code cyclique engendré par le
polynôme générateur x3 + x + 1 donne un code [7, 4] qui a une distance minimale de 3 et se
trouve être le code de Hamming [7, 4, 3].

Test 1.28. 7 sur F2 : donner leur polynôme générateur, leur

dimension et leur distance minimale. Faire de
Construire tous les codes cycliques de longueur même pour les codes cycliques de longueur 9.

On déduit du théorème précédent le corollaire suivant.

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 24 — #26

i

24

Corollaire 1.67. Soit C un code cyclique sur Fq de longueur n et de polynôme géné-

X
n−k
Partie . TABLE DES MATIÈRES

rateur g(x) = gi xi de degré n − k, alors, l’ensemble des mots de C est l’ensemble

i=0
{g(x)a(x)|deg(a(x)) ≤ k − 1}. Le code C a pour dimension k et a pour matrice génératrice la
matrice
2 3
g0 g1 · · · gn−k 0 0 ··· 0
6 0
6 g 0 g1 · · · gn−k 0 ··· 0 7
7.
4 ··· ··· ··· 5
0 0 0 ··· 0 g0 ··· gn−k

Une autre façon de caractériser les codes cycliques peut se faire à partir des zéros du polynôme
générateur, que l’on peut aussi définir à partir de l’ensemble de définition.
Définition 1.68. (Ensemble de définition) Pour α une racine n-ième de l’unité dans une
extension Fqordq (n) de Fq et g(x) un polynôme générateur d’un code cyclique C (donc qui divise
xn − 1), l’ensemble de définition T du code C est l’ensemble des i tels que αi est une racine de
g(x).
L’ensemble T correspond à la réunion des q-classes cyclotomiques associées à la décomposi-
tion de g(x) dans le théorème 1.64.
Le code dual est lui aussi cyclique.

Proposition 1.69. Si C est un code cyclique de longueur n sur Fq , alors le code dual C ⊥ est
aussi cyclique.

Preuve. Dire que C est cyclique équivaut à dire que le groupe d’automorphisme de C contient
la permutation circulaire (1, 2, 3, · · · , n). En notant H une matrice de parité de C, on a, pour
tout c ∈ C, H.ct = 0. Puisque le code est cyclique, pour toute permutation circulaire P, on a
H.(c.P)t = 0 = H.Pt .ct = H.P−1 .ct et donc tout élément de C est orthogonal à HP−1 . Mais
comme P−1 est aussi une permutation circulaire, le code engendré par HP−1 est égal à C ⊥ . Le
code dual C ⊥ étant stable par P−1 , il est bien cyclique. n

Pour tout g(x) = g0 + g1 x + · · · + gn−k−1 xn−k−1 + xn−k polynôme générateur d’un code
cyclique C de longueur n, il existe h(x) = h0 +h1 x+· · ·+hk−1 xk−1 +xk tel que g(x)h(x) = xn −1.
Si l’on se place dans Fq [x] = Fq [x]/(xn − 1), on obtient g(x)h(x) = 0 et donc, en écrivant le
fait que chacun des coefficients pour un degré donné est nul dans g(x)h(x) (ainsi que pour les
produits de g(x) avec les permutés circulaires de h(x)), on obtient le théorème suivant.

Théorème 1.70. Si C[n, k]q est un code cyclique de polynôme générateur g(x), alors C ⊥ est
−1
xn −1
aussi un code cyclique de polynôme générateur g⊥ (x) = xn−k h(xh0 )
, où h(x) = g(x)
.

Preuve. Le résultat est obtenu directment à partir du calcul de g(x)h(x) = 0 dans Fq [x] =
Fq [x]/(Xn − 1) en notant que les coefficients de g⊥ (x) sont exactement ceux de h(x), mais en
sens inverse. n

Remarque. Lorsque l’on choisit une racine n-ième de l’unité pour un code cyclique de longueur
n, il peut y avoir plusieurs choix possibles. En effet, à partir d’une telle racine α, tous les αi avec
pgcd(i, n) = 1 sont aussi des racines n-ièmes. Le fait de prendre des racines n-ièmes différentes
peut mener à des codes distincts, mais toujours équivalents. Deux codes équivalents ayant les

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 25 — #27

i

25

mêmes propriétés en termes de distance de Hamming, on ne précise pas en général la racine

utilisée lorsque l’on regarde les propriétés générales du code. Bien sûr, quand on le construit
concrètement, on doit le faire.

Chapitre 1. Introduction à la théorie algébrique des codes correcteurs d’erreurs

Test 1.29. Quel est le dual du code cyclique binaire de
longueur 7 de polynôme générateur x3 + x + 1 ?
Justifier la remarque précédente. Quel est son ensemble de définition ? Quel est
Test 1.30. celui de son dual ?

IV.2. Borne BCH

La borne BCH est par la suite utilisée pour la définition des codes BCH qui ont été introduits
a peu près simultanément par Hocquenghem d’un côté et Bose et Chauduri de l’autre en 1959.
Nous commençons par rappeler la notion de matrice de Vandermonde, vue au chapitre 2
dans le cadre de l’interpolation.

Rappel Matrice de Vandermonde

Soient x1 , x2 , · · · , xn des éléments d’un anneau. Leur matrice de Vandermonde V est définie
par
2 3
1 1 ··· 1
6 x1
6 x2 ··· xn 7
2 2 2
7
V = 6 x1
6 x2 ··· xn 7.
7
4 ··· 5
xn−1
1 xn−1
2 · · · xn−1
n

Son déterminant vaut det(V) = Π1≤i<j≤n (xi − xj ).

En particulier, cela signifie que det(V) est non nul si et seulement si les xi sont tous distincts.
Soit C un code cyclique ; on rappelle que l’on nomme ensemble de définition T du code
C l’ensemble des i tels que αi est un zéro de C. On dira que T contient un ensemble de s
éléments consécutifs s’il existe un ensemble {b, b + 1, · · · , b + s − 1} d’entiers consécutifs tels que
{b, b + 1, · · · , b + s − 1} (mod n) ⊂ T.

Théorème 1.71. Soit C un code cyclique de longueur n sur Fq avec un ensemble de définition
T . Si l’on note d la distance minimale du code C et si T contient δ − 1 éléments consécutifs,
alors δ 6 d.
Preuve. Par hypothèse, il existe b tel que les éléments αb , · · · , αb+δ−2 sont des zéros du
code C. Soit c(x) un mot non nul du code de poids w 6 δ − 1. Le mot c(x) est non nul sur w
Xw
coordonnées et s’écrit c(x) = cij xij . Supposons que w < δ. Comme c(αi ) = 0 pour tout
j=1
b ≤ i ≤ b + δ − 2, on a alors M.ut = 0 pour
αi1 b αi2 b αiw b
2 3
···
6 αi1 (b+1) αi2 (b+1)
··· αiw (b+1) 7
M=6 7,
4 ··· ··· 5
αi1 (b+w−1) αi2 (b+w−1) ··· αiw (b+w−1)

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 26 — #28

i

26

avec u = (ci1 , · · · , ciw ). Mais, comme w 6 δ − 1, on peut écrire det(M) = αb(i1 +···+iw ) det(V),
où V est la matrice de Vandermonde
Partie . TABLE DES MATIÈRES

2 3
1 1 ··· 1
i1 i2
6 α α ··· αiw 7
V =6 7
4 ··· ··· 5
αi1 w−1) αi2 (w−1) ··· αiw (w−1)
de déterminant non nul, puisque les αik sont distincts pour 1 6 k 6 w. On en déduit que la
matrice M est inversible et donc que la solution de M.ut = 0 est u = 0 ; or u 6= 0, soit une
contradiction et donc w > δ. n

Remarque. On parle pour δ de distance construite du code. La valeur δ constitue une minora-
tion de la vraie distance minimale d du code. En pratique, il y a souvent très peu de différence
entre d et δ.

Test 1.31. minimale vaut 3. Et si l’on ajoute 0 à l’ensemble

de définition ? Soit le code binaire cyclique en
Soit le code de Hamming ayant pour ensemble longueur 23 d’ensemble de définition T = C1 ,
de définition T = C1 = {1, 2, 4}. Montrer en la 2-classe cyclotomique de 1 modulo 23 ; que
utilisant la borne précédente que sa distance donne alors la borne ?

IV.3. Codes BCH

Définition 1.72. (Codes BCH) Soient n et q deux entiers premiers entre eux, et soit α une
ord (q)
racine n-ième de 1 sur Fq n . Soit δ un entier avec 2 ≤ δ ≤ n. Un code BCH sur Fq de
longueur n et de distance construite δ est un code cyclique avec pour ensemble de définition

T = Cb ∪ Cb+1 ∪ · · · ∪ Cb+δ−2 ,

où Ci désigne la q-classe cyclotomique modulo n contenant i.

Pour différents b, on obtient des codes différents. Pour b = 1, on parle de code BCH au sens
strict. Si de plus n est de la forme qt − 1 avec t quelconque, on parle de code BCH primitif.

Théorème 1.73. Soit C un code BCH [n, k]q , de distance construite δ, alors :
1. k ≥ n − ordq (n).(δ − 1) ;
2. si q = 2 et si C est un code BCH au sens strict, alors on peut restreindre δ au cas où δ
est impair ; de plus, si l’on écrit δ = 2w + 1, alors k ≥ n − ordq (n).w.

Preuve. L’ensemble de définition de C est la réunion de δ − 1 classes cyclotomiques. Comme

chaque classe contient au plus ordq (n) éléments, l’ensemble de définition du code contient au
plus ordq (n).(δ − 1) éléments et la dimension du code est au moins n − ordq (n).(δ − 1). Pour
le cas binaire, avec δ impair écrit sous la forme δ = 2w + 1 et pour un code BCH au sens strict,
on remarque que l’ensemble de définition T = ∪2w w
i=1 Ci est contenu dans la réunion ∪i=1 C2i−1 ,
puisque C2a = Ca pour a quelconque, ce qui donne 2). n

Exemple 1.74.
Prenons en longueur 15 sur F2 , des codes BCH au sens strict qui sont primitifs.
- δ = 3 donne T = C1 ∪ C2 = C1 = {1, 2, 4, 8}, soit [15, 11, d ≥ 3] ;

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 27 — #29

i

27

- δ = 4 donne T = C1 ∪ C2 ∪ C3 = C1 ∪ C3 = {1, 2, 3, 4, 6, 8, 9, 12}, soit [15, 7, d ≥ 5] ;

- δ = 5 n’ajoute rien par rapport au cas δ = 4.
- δ = 6 et δ = 7 donnent T = C1 ∪ C3 ∪ C5 , soit [15, 5, d ≥ 7] ;

Chapitre 1. Introduction à la théorie algébrique des codes correcteurs d’erreurs

- δ = 8 et plus donne [15, 1, 15] car il n’y plus de classe cyclotomique à ajouter (à part 0).
Un calcul des polynômes générateur et le fait de construire un mot de poids précisement
égal à d dans chaque cas montre qu’en fait ces distances sont exactes. Par exemple, pour
δ = 4, on trouve, en prenant x4 + x + 1 pour polynôme de construction de l’extension, que
g(x) = x8 + x7 + x6 + x4 + 1.

IV.4. Codes de Reed-Solomon cycliques

Les codes de Reed-Solomon ont été introduits originellement par I. S. Reed et G. Solomon
en 1959 par une construction n’utilisant pas de cyclicité, comme on le verra plus loin, mais les
codes de Reed-Solomon peuvent aussi s’interpréter comme des codes BCH particuliers (et donc
cycliques). Ils ont longtemps été présentés sous cette forme car ils étaient aussi décodés en tant
que codes BCH particuliers.
Définition 1.75. (Codes de Reed-Solomon cycliques) On appelle codes de Reed-Solomon
cycliques sur Fq les codes BCH de longueur n = q − 1.
Dans ce cas, ordq (n) = 1 et donc tous les facteurs irréductibles de xn − 1 sont de degré un.
On a alors le théorème suivant.

Théorème 1.76. Soit C un code de Reed-Solomon cyclique sur Fq de longueur n = q − 1 et

de distance construite δ, alors
1. C a pour ensemble de définition T = {b, b + 1, · · · , b + δ − 2} ;
2. C a une distance minimale d = δ et une dimension k = n − d + 1 ;
3. C réalisent l’égalité dans la borne de Singleton et est MDS.

Preuve. Pour un tel code, on a ordq (n) = 1 et donc T = {b, b + 1, · · · , b + δ − 2} = ∪b+δ−2

i=b Ci .
La taille de l’ensemble de définition est exactement δ − 1, soit k = n − (δ − 1) = n − δ + 1. Mais,
comme δ 6 d et comme la borne de Singleton assure que k 6 n − d + 1, on a alors d = δ, soit
k = n − δ + 1 = n − d + 1. Pour le point 3), on remarque qu’un code est MDS si précisément il
vérifie l’égalité k = n − d + 1. n

Test 1.32. Si l’on prend F7 , construire un code de distance

minimale 4. Quels sont les paramètres du code ?

V. Décodage des codes BCH

Un premier algorithme de décodage a été proposé en 1960 par G. Peterson pour les BCH
binaires, puis généralisé par G. Peterson, D. Gorenstein et N. Zierler la même année. En 1968,
E. Berlekamp et J. Massey ont proposé un algorithme qui a permis d’améliorer les algorithmes
précédents sur la partie de l’obtention du polynôme localisateur d’erreurs, que l’on verra par la
suite et qui est une étape importante du décodage. Enfin, en 1974, a été proposé un décodage par
l’algorithme d’Euclide étendu, d’une complexité asymptotique similaire à celle de Berlekamp-
Massey, mais conceptuellement plus simple. C’est ce dernier algorithme que nous présentons
dans cette section.

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 28 — #30

i

28

V.1. Algorithme de Peterson

Soit C un code BCH sur Fq de longueur n et de distance construite δ. On va décoder jusqu’à
Partie . TABLE DES MATIÈRES

au plus t = b δ−1 2
c erreurs. On suppose que l’ensemble de définition T du code contient un
ensemble de δ − 1 zéros consécutifs et que, sans perte de généralité, on peut prendre un code au
sens strict, c’est-à-dire que {1, 2, · · · , δ − 1} ⊂ T . On considère une racine primitive α d’ordre n
de Fqm avec m = ordq (n).
On reçoit le vecteur r(x) = c(x) + e(x) avec e un vecteur d’erreurs de poids wH (e) ≤ t et
où c(x) correspond au vecteur envoyé. On note e(x) = ek1 xk1 + · · · + ekν xkν ; le problème du
décodage est de retrouver e(x). Puisque c(x) ∈ C, on a c(αi ) = 0, ∀i ∈ T . En particulier, on a

r(αi ) = c(αi ) + e(αi ) = e(αi ), ∀i ∈ T.

On peut remarquer que [1, ..., 2t] ⊂ T , puisque 2t ≤ δ − 1.

On note Si = r(αi ) pour 1 ≤ i ≤ 2t l’ensemble des syndromes associés au mot reçu v.
On note maintenant
αn−1
2 3
1 α ···
6 1 α2 · · · α2(n−1) 7
H=6 7.
4 ··· ··· 5
1 αt ··· αt(n−1)
Soient v = (v0 , · · · , vn−1 ) = v0 + v1 x + · · · + vn−1 xn−1 et S = (S1 , · · · , St ), alors on a
H.vt = St . Pour ekj la valeur de l’erreur et kj l’emplacement de l’erreur, on note Ej = ekj et
Xj = αkj , les valeurs des emplacements de l’erreur. On obtient alors
X
ν
Si = r(αi ) = Ej Xij pour 1 ≤ i ≤ 2t.
j=1

Ceci nous donne le système



 E1 X1 + · · · + Eν Xν = S1


 E1 X21 + · · · + Eν X2ν = S2
(S1 ) : E1 X31 + · · · + Eν X3ν = S2 .



 ···

E1 X2t 2t
1 + · · · + Eν Xν = S2t

Dans ce système, les Ei et les Xi sont des inconnues, seuls les Si sont connus ; le système est
donc non linéaire et est compliqué à résoudre directement. On va alors introduire un polynôme
localisateur d’erreurs qui permettra de trouver les Xi et ainsi de se ramener à la résolution d’un
système linéaire en les Ei .
Définition 1.77. (Polynôme localisateur d’erreurs) Pour Xj , 1 ≤ j ≤ ν, les emplacements
des erreurs pour le mot reçu v, on appelle polynôme localisateur d’erreurs le polynôme σ(x) défini
par
déf
X
ν
σ(x) = (1 − xX1 )(1 − xX2 ) · · · (1 − xXν ) = 1 + σi xi ,
i=1

où les racines de σ(x) sont les inverses des emplacements d’erreurs Xj .

On obtient alors :

σ(X−1 −1
j ) = 1 + σ1 Xj + · · · + σν X−ν
j = 0 pour 1 ≤ j ≤ ν.
En multipliant les équations précédentes par Ej Xi+ν
j , il vient

Ej Xi+ν
j + σ1 Ej Xji+ν−1 + · · · + σν Ej Xij = 0, pour tout i.

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 29 — #31

i

29

Si l’on somme alors sur j (1 6 j 6 ν), on obtient

Chapitre 1. Introduction à la théorie algébrique des codes correcteurs d’erreurs

X
ν X
ν X
ν
Ej Xi+ν
j + σ1 Ej Xji+ν−1 + · · · + σν Ej Xij = 0.
j=1 j=1 j=1

Pour 1 ≤ i et i + ν ≤ 2t, ces sommes correspondent aux syndromes Si ; comme ν ≤ t, cela

nous donne le système d’équations suivant :

Si+ν + σ1 Si+ν−1 + · · · + σν Si = 0, pour 1 ≤ i ≤ ν.

Les coefficients du polynôme localisateur d’erreurs sont solutions du système
0 10 1 0 1
S1 S2 ··· Sν σν −Sν+1
B S2
B S3 ··· Sν+1 C C B σν−1 C = B −Sν+2 C .
B C B C
@ ··· ··· ··· ··· A @ ··· A @ ··· A
Sν Sν+1 ··· S2ν−1 σ1 −S2ν
Le système précédent peut se récrire sous la forme du système système linéaire (S2 ) suivant :
0 1
0 1 σν 0 1
S1 S2 ··· Sν Sν+1 B σν−1 C 0
B S2
B S3 ··· Sν+1 Sν+2 CCB ··· C = B 0 C.
B C B C
@ ··· ··· ··· ··· AB C @ ··· A
@ σ1 A
Sν Sν+1 · · · S2ν−1 S2ν 0
1
On peut donc retrouver les coefficients de σ(x) en résolvant le système (S2 ), qui permet
de retrouver le polynôme localisateur d’erreurs σ(x). On peut alors déduire les emplacements
d’erreurs Xj en factorisant σ(x). On retrouve les valeurs des coefficients des erreurs Ej , en
remplaçant dans le système (S1 ) les Xj par leurs valeurs. On obtient alors un système linéaire
en les Ej , que l’on peut résoudre.
Dans tout ce que l’on a considéré, la valeur de ν n’est pas connue et la question se pose de
connaître le nombre exact d’erreurs ν. Ce problème est résolu par la proposition suivante.

Proposition 1.78. Soit µ ≤ 2t et soit

0 1
S1 S2 ··· Sµ
B S2 S3 ··· Sµ+1 C
Sµ = B
@ ···
C,
··· ··· ··· A
Sµ Sµ+1 ··· S2µ−1
alors la matrice Sµ est inversible si µ = ν et non inversible si µ > ν, où ν désigne le nombre
d’erreurs.
Preuve. Soit Vµ la matrice de Vandermonde définie pour les emplacements d’erreurs X1 , X2 , . . . , Xµ
avec Xj = 0 pour j > ν. En utilisant les valeurs des coefficients Ej pour 1 6 j 6 ν et Ej = 0 pour
j > ν, on peut vérifier que Sµ = Vµ Dµ Vµt avec
0 1
E1 X1 0 ··· 0
B 0 E2 X2 · · · 0 C
Dµ = B@ ···
C.
··· ··· ··· A
0 0 ··· Eµ Xµ
La matrice Dµ est inversible si et seulement si µ ≤ ν (pour µ > ν, il existe au moins un
terme de la diagonale de Dµ nul) ; comme la matrice Vµ est inversible en tant que matrice de
Vandermonde, la matrice Sµ est inversible si et seulement si µ ≤ ν. n

On peut alors synthétiser l’algorithme :

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 30 — #32

i

30

Méthode Algorithme de Peterson

Partie . TABLE DES MATIÈRES

1. Calculer des syndromes Si = r(αi ) pour 1 ≤ i ≤ 2t ;

2. À partir de µ = t, µ = t − 1, . . ., trouver le premier µ tel que Sµ est inversible, ce qui
donne la valeur de ν ;
3. Résoudre le système (S2 ) en les σi ;
4. Calculer les emplacements d’erreurs à partir de σ(x) par la recherche des racines de
σ(x) ;
5. Résoudre le système linéaire (S1 ) pour retrouver les valeurs des erreurs Ej .

Remarque. Dans le cas d’un code binaire, l’étape 5 n’est pas nécessaire.

La complexité de ce dernier algorithme est O(n3 ) puisque les points 3 et 5 nécessitent la

résolution d’un système d’équations linéaires (voir le chapitre 5 du tome Mathématiques L2). En
fait, il est possible d’améliorer certaines de ces étapes. Par exemple, la résolution de la partie
3 peut se faire en temps quadratique en n par l’algorithme de Berlekamp-Massey ou par celui
d’Euclide étendu que nous détaillons dans la section suivante (voir aussi les chapitres 4 et 5 du
tome Mathématiques L2).

Exemple 1.79. Considérons un code BCH au sens strict primitif de longueur 15 et de

distance construite δ = 5 en prenant, pour définir F16 , le polynôme x4 + x + 1 (soit α4 = α + 1).
Le code est un code [15, 7, 5] de polynôme générateur g(x) = 1 + x4 + x6 + x7 + x8 . Supposons
que l’on reçoive le mot r(x) = 1 + x + x5 + x6 + x9 + x10 . On commence par calculer les
syndromes S1 = α2 , S2 = α4 , S3 = α11 et S4 = α8 .
Pour la deuxième étape, on calcule le déterminant de
« „ 2
α4
„ «
S1 S2 α
M2 = =
S2 S3 α4 α11
qui est non nul. Il y a donc 2 erreurs. On doit maintenant résoudre le système
„ «„ « „ «
S1 S2 σ2 −S3
= ,
S2 S3 σ1 −S4
soit

α2 α4 α11
„ «„ « „ «
σ2
= .
α4 α11 σ1 α8
La solution est σ1 = α2 et σ2 = α14 et l’on obtient, pour le polynôme localisateur d’erreurs,
σ(x) = 1 + α2 x + α14 x2 , qui s’annule pour α11 et α5 , d’où X1 = α4 et X2 = α10 . Et donc le
mot transmis est c(x) = r(x) + x4 + x10 = 1 + x + x4 + x5 + x6 + x9 .

Test 1.33. l’exemple précédent. Quel est le polynôme

générateur de C ? Corriger le vecteur reçu
Soit C le code BCH au sens strict binaire pri- r(x) = x2 + x5 + x6 + x9 + x10 + x11 + x12 + x13 .
mitif [15, 5, 7] avec F16 défini comme dans

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 31 — #33

i

31

V.2. Décodage par l’algorithme d’Euclide étendu

On suppose que C est un code cyclique sur Fq dont le polynôme générateur a un ensemble de

Chapitre 1. Introduction à la théorie algébrique des codes correcteurs d’erreurs

zéros contenant les éléments α, α2 , . . . , α2t , où α désigne une racine n-ième de l’unité dans une
extension Fqm . On reçoit le mot r (sous forme polynomiale) et les syndromes associés sont les
Si = r(αi ). On a vu lors de l’algorithme précédent que les coefficients du polynôme localisateur
d’erreurs σt , σt−1 , · · · , σ1 , σ0 avec σ0 = 1, étaient solutions du système (S2 ), mais dans l’ordre
X2t
décroissant des coefficients. Si l’on définit S(x) = Si x2t−i et σ 0 (x) = xt σ(x−1 ) le polynôme
i=1
réciproque de σ(x) (où l’ordre des coefficients est inversé), et que l’on calcule S(x)σ 0 (x), alors le
système (S2 ) implique que les termes de degrés t, t + 1, · · · , 2t − 1 de S(x)σ(x) sont tous nuls
et donc que deg (S(x)σ 0 (x)) (mod x2t )) < t. D’autre part, si σ 0 (x) (avec deg (σ 0 (x)) ≤ t) vérifie
deg (S(x)σ 0 (x) (mod x2t )) < t, alors on a une solution de (S2 ).

Rappel Algorithme d’Euclide étendu

Étant donné deux polynômes a(x) et b(x) de Fq [x], l’algorithme d’Euclide étendu calcule
leur PGCD d(x) et deux polynômes f(x) et g(x) réalisant l’identité de Bézout

a(x)f(x) + b(x)g(x) = d(x),

avec deg (g(x)) < deg (a(x)) et deg (f(x)) < deg (b(x)).
L’algorithme procède par itérations successives de divisions euclidiennes. L’initialisation
se fait par r−1 (x) = a(x), f−1 (x) = 1, g−1 (x) = 0, r0 (x) = b(x), f0 (x) = 0, g0 (x) = 1,
puis pour i ≥ 1, on effectue la division euclidienne ri−2 (x) = qi (x)ri−1 (x) + ri (x) avec
deg (ri (x)) < deg(ri−1 (x)). On met à jour fi (x) = fi−2 (x) − qi (x)fi−1 (x) et gi (x) =
gi−2 (x) − qi (x)gi−1 (x).
On a les résultats suivants à chaque étape :
1. pgcd(ri−1 (x), ri (x)) = pgcd(ri (x), ri+1 (x)) ;
2. fi (x)a(x) + gi (x)b(x) = ri (x) ;
3. deg (gi (x)) + deg(ri−1 (x)) = deg(a(x)) ;

Théorème 1.80. Si l’on utilise l’algorithme d’Euclide étendu en prenant comme polynômes
de départ S(x) et x2t , et en s’arrêtant dès que le reste ri (x) est tel que deg (ri−i (x)) ≥ t et
deg (ri (x)) < t, alors on obtient le polynôme σ 0 (x) (et donc σ(x)) par la relation σ 0 (x) =
gi (x), en prenant gi (x) monique.

Preuve. Si l’on arrête l’algorithme d’Euclide étendu à l’endroit précisé dans le théorème, on
obtient, d’après le rappel sur l’algorithme d’Euclide étendu, deg (gj (x)) = 2t − deg(rj−1 (x)) ≤ t
et fj (x)x2t + gj (x)s(x) = rj (x). Le polynôme gj (x) est un polynôme de degré au plus t tel que
deg (S(x)gj (x)) (mod x2t )) = deg (rj (x) < t, ce qui implique, d’après ce que l’on a vu plus haut,
en tenant compte du fait que σt = 1, que σ 0 (x) = gj (x) (pris sous forme monique). n

La complexité de l’algorithme d’Euclide étendu est en O(n2 ) (voire O(n log(n)) avec des
méthodes avancées), ce qui est plus efficace pour trouver σ(x) que l’algorithme classique d’in-
version de matrice en O(n3 ). Il existe aussi des méthodes pour accélérer le calcul des Ej que
nous ne décrivons pas ici.

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 32 — #34

i

32

Exemple 1.81. On considère à nouveau l’exemple 1.79 pour lequel on va appliquer l’al-
gorithme d’Euclide étendu pour retrouver σ(x). On a dans ce cas 2t = 4 et S(x) =
S1 x3 +S2 x2 +S3 x+S4 , soit, en reprenant les données précédentes S(x) = α2 x3 +α4 x2 +α11 x+α8 .
Partie . TABLE DES MATIÈRES

On applique alors l’algorithme d’Euclide étendu entre S(x) et x4 . On initialise l’algorithme

par f−1 (x) = 1, g−1 (x) = 0, r−1 (x) = x4 et f0 (x) = 0, g0 (x) = 1 et enfin r0 (x) =
S(x) = α2 x3 + α4 x2 + α11 x + α8 . On effectue la division euclidienne de r−1 (x) = x4 par
r0 (x) = S(x) = α2 x3 + α4 x2 + α11 x + α8 , soit r−1 (x) = (α13 x + 1)r0 (x) + α14 x2 + αx + α8 ,
qui donne r1 = α14 x2 + αx + α8 et q1 (x) = α13 x + 1. On peut, alors, calculer f1 (x) = 1
et g1 (x) = q1 (x). Comme deg (r1 ) > t, on refait une itération de division euclidienne :
r0 (x) = (α3 x)r1 (x) + αx + α8 , soit r2 (x) = αx + α8 et q2 (x) = α3 x. Comme cette fois
deg (r2 ) < t, on arrête l’algorithme et on calcule σ 0 (x) = g2 (x) = g0 (x) − q2 (x)g1 (x) =
1 − (α3 x)(α13 x + 1) = αx2 + α3 x + 1. On obtient alors g2 (x) = αx2 + α3 x + 1 qui, sous forme
monique, donne σ 0 (x) = x2 + α2 x + α14 , soit σ(x) = α14 x2 + α2 x + 1, comme dans l’exemple
précédent 1.79.

Test 1.34. Test 1.35.

Montrer qu’on peut retrouver les emplacements En reprenant l’énoncé du test 1.33, montrer que
d’erreurs directement à partir du polynôme gj (x) le mot reçu conduit à une erreur de poids 2.
obtenu par l’algorithme d’Euclide étendu sans Appliquer l’algorithme d’Euclide étendu avec
passer par σ(x). t = 2 pour retrouver le polynôme localisateur
d’erreurs.

VI. Codes de Reed-Solomon, codes alternants et codes de Goppa

VI.1. Codes de Reed-Solomon et algorithme de Welch-Berlekamp

Les codes de Reed-Solomon ont été introduits par I. S. Reed et G. Solomon en 1959. En raison
de leurs paramètres optimaux et de leur facilité de décodage, ces codes ont été très utilisés dans
l’industrie, par exemple pour les CD et DVD ainsi que pour les communications satellites. On
a vu à la section IV comment ces codes pouvaient aussi être introduits en tant que codes BCH
particuliers. La définition que nous donnons maintenant correspond à la définition originelle de
ces codes, qui n’utilise pas la notion de cyclicité. On renvoie à l’exercice 1.13 pour la preuve que
les codes de Reed-Solomon cycliques sont un cas particulier de la famille des codes que nous
présentons maintenant.
Définition 1.82. (Code de Reed-Solomon) Soit Fq un corps et soient x1 , · · · , xn , n élé-
ments distincts de F∗q . Pour k ≤ n, on considère l’ensemble Pk des polynômes de Fq [x] de
degré au plus k − 1. Un code de Reed-Solomon est composé de l’ensemble des mots c(f) =
(f(x1 ), · · · , f(xn )) pour f ∈ Pk .
On parlera de code RS(n, k)q pour désigner un code de Reed-Solomon de longueur n sur Fq et
de paramètre k.
On a alors le théorème suivant.

Théorème 1.83. Les codes de Reed-Solomon RS(n, k)q sont des codes [n, k, n − k + 1]q .

Preuve. Par définition, les codes RS(n, k)q sont des codes de longueur n ; la linéarité des
codes découle de la linéarité de l’addition de polynômes dans Pk . Le nombre de mots d’un code
RS est inférieur ou égal au nombre de polynômes de Pk , c’est-à-dire qk . Supposons que deux

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 33 — #35

i

33

polynômes f et g de Pk donnent le même mot du code c(f) = c(g) ; alors, on a (f − g)(x) = 0

pour tout x ∈ x1 , · · · , xn . Le polynôme f − g est de degré au plus k − 1 et s’annule alors en n
points. Comme n > k − 1 ≤ deg(f − g), on en déduit que f − g = 0 et donc que f = g, ce qui

Chapitre 1. Introduction à la théorie algébrique des codes correcteurs d’erreurs

montre que la dimension du code est précisément k.
Montrons maintenant que la distance minimale est n − k + 1. Soit c(f) un mot du code non
nul (i.e. f 6= 0), alors c(f) = (f(x1 ), · · · , f(xn )) pour deg (f) ≤ k − 1. Si f s’annule en un nombre
de points strictement supérieur à deg (f), alors f est nécessairement le polynôme nul ; comme
deg (f) ≤ k − 1 et que f 6= 0, f peut donc s’annuler en k − 1 points au plus. On en déduit que
wH (c(f)) ≥ n − (k − 1) = n − k + 1, soit d > n − k + 1. Maintenant, la borne de Singleton assure
que d 6 n − k + 1 ; on a donc exactement d = n − k + 1. n

Remarque. Comme les codes de Reed-Solomon satisfont l’égalité dans la borne de Singleton,
ils sont MDS.

Nous présentons ici un algorithme de décodage élémentaire de ces codes.

Soit r = c + e un mot reçu tel que wH (e) ≤ t avec t = b d−1 2
c. Le décodage utilise un
polynôme bivarié particulier Q(x, y) de la forme Q(x, y) = Q0 (x) + yQ1 (y), tel que
1. Q(xi , ri ) = 0, i ∈ {1, · · · , n} ;
2. deg(Q0 ) ≤ n − 1 − t ;
3. deg(Q1 ) ≤ n − 1 − t − (k − 1) ;
Ce polynôme est en fait un polynôme d’interpolation (voir le chapitre 2) bivarié sur les points
(xi , ri ).

Proposition 1.84. Il existe au moins un polynôme Q(x, y) non nul vérifiant les conditions
précédentes.

Preuve. Le polynôme Q(x, y) peut être décrit à partir de ses degrés en Q0 (x) et Q1 (x) en
prenant pour inconnues les coefficients de Q0 et Q1 . On va simplement compter le nombre de
contraintes et le nombre de degrés de liberté. La condition 1 donne n contraintes linéaires ; les
conditions 2 et 3 fixent les degrés de Q0 et Q1 , ce qui donne deg (Q0 )+1+deg(Q1 )+1 degrés de
libertés (les coefficients des monômes de Q0 et Q1 ). Il y a donc n−1−t+1+n−1−t−(k−1)+1 =
n − k − 2t + 1 + n + 1 inconnues. Mais, comme t = b(n − k + 1)/2c, le nombre de degrés de liberté
est supérieur ou égal à n + 1. Comme le nombre n + 1 d’inconnues est supérieur au nombre
n de contraintes, on est sûr qu’il existe au moins un tel polynôme Q(x, y) non nul obtenu en
résolvant un système à n équations et n + 1 inconnues. n

On peut alors en déduire comment décoder les codes de Reed-Solomon.

Théorème 1.85. Soit c = c(f), un mot d’un code RS( n, k)q , construit à partir de f(x)
avec deg (f) ≤ k − 1. Soit maintenant un mot reçu r = c + e avec une erreur e de poids
wH (e) 6 t = b d−1
2
c. Si l’on construit le polynôme Q(x, y) = Q0 (x) + yQ1 (y), le polynôme
d’interpolation bivarié défini précédemment à partir du mot reçu r, alors on peut retrouver le
polynôme f(x) associé à c(f) par f(x) = −Q 0 (x)
Q1 (x)
.

Preuve. Soient c(f) = (f(x1 ), · · · , f(xn )) et r = c + e pour wH (e) ≤ t = b d−1

2
c. Par définition,
on a Q(xi , ri ) = 0 pour tout i ∈ [1, .., n], mais ri = f(xi ) + ei et donc ri = f(xi ) lorsque
ei = 0, ce qui se produit en au moins n − t coordonnées. Ainsi le polynôme univarié Q(x, f(x))
a au moins n − t zéros distincts. Mais, comme deg (Q0 (x)) ≤ n − 1 − t et deg (f(x)Q1 (x)) ≤
(k − 1) + n − 1 − t − (k − 1) = n − 1 − t, on a deg (Q(x, f(x)) ≤ n − 1 − t. Le polynôme Q(x, f(x))

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 34 — #36

i

34

est de degré au plus n − t − 1 et s’annule en au moins n − t valeurs. C’est donc le polynôme nul,
d’où Q(x, f(x)) = 0 et donc Q0 (x) + f(x)Q1 (x) = 0, ce qui implique que f(x) = − Q 0 (x)
Q1 (x)
. n
Partie . TABLE DES MATIÈRES

On en déduit l’algorithme de décodage suivant

Méthode Algorithme de Welch-Berlekamp

1. Pour un mot reçu r, construire le polynôme interpolé Q(x, y) = Q0 (x) + yQ1 (x).
2. Décoder par division de Q0 (x) par Q1 (x).

Ce décodage est polynomial en n puisque ces deux étapes peuvent s’effectuer en temps
polynomial en n ; plus précisément, la première étape (la plus coûteuse) peut se faire dans le
pire des cas par inversion d’une matrice n × n, soit en O(n3 ) opérations. En fait, il existe des
méthodes (que nous ne décrivons pas ici) qui permettent de le faire en O(n2 ).
Exemple 1.86. On considère un code de Reed-Solomon [6, 4, 3]7 défini par les points
x1 , .., x6 , avec xi = 3i−1 . Une matrice génératrice G s’obtient en évaluant les xi pour les
polynômes 1, x, x2 et x3 , soit
2 3
1 1 1 1 1 1
6 1 3 2 6 4 5 7
G=64 1 2 4 1 2 4 5.
7

1 6 1 6 1 6

Comme d = 3, on peut décoder au plus une erreur. On veut maintenant décoder le mot reçu
r = (r1 , r2 , ..., r6 ) = (3, 1, 1, 6, 3, 3) avec l’algorithme de Welch-Berlekamp.
Dans ce cas, le polynôme Q0 (x) a degré au plus n − 1 − t = 6 − 1 − 1 = 4 et le polynôme
Q1 (x) a degré n − 1 − t − (k − 1) = 1. On cherche donc un polynôme, non nul, Q(x, y) =
a0 + a1 x + a2 x2 + a3 x3 + a4 x4 + y(b0 + b1 x), tel que Q(xi , ri ) = 0 pour 1 6 i 6 6. En
remplaçant les xi par 3i−1 et les ri par leur valeur dans Q(x, y), pour 1 6 i 6 6, on obtient un
système avec 6 équations et 7 inconnues : a0 , a1 , ..., a4 , b0 , b1 . La résolution du système donne
Q0 (x)
Q0 (x) = 3x + 3x2 + 6x3 et Q1 (x) = 2 + x, soit f(x) = − Q 1 (x)
= x2 + x. En évaluant f sur
(x1 , x2 , x3 , x4 , x5 , x6 ) = (1, 3, 2, 6, 4, 5), on obtient comme mot décodé c(f) = (3, 1, 1, 6, 3, 0) et
comme erreur (0, 0, 0, 0, 0, 3).

Test 1.36. xi = 3i−1 . Donner une matrice génératrice du

code. Décoder le mot reçu r = (6, 6, 5, 2, 1, 2)
On considère le code de Reed-Solomon [6, 3, 4]7 , par l’algorithme de Welch-Berlekamp.
défini sur F7 par les points x1 , .., x6 avec

VI.2. Codes alternants

Les codes alternants sont reliés aux codes de Reed-Solomon par le biais des codes de Reed-
Solomon généralisés (RSG).
Définition 1.87. (Codes de Reed-Solomon généralisés) Un code de Reed-Solomon gé-
néralisé RSk (α, v) sur Fq de longueur n 6 q − 1 et de dimension k est défini par un vecteur
v = (v1 , · · · , vn ) d’éléments non nuls de Fq et un ensemble α = (α1 , · · · , αn ) d’éléments dis-
tincts non nuls de Fq . Alors,

RS(α, v) = {(v1 f(α1 ), · · · , vn f(αn ) | f ∈ Fq [x], deg(f) < k}.

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 35 — #37

i

35

Les codes de Reed-Solomon généralisés correspondent donc à un code de Reed-Solomon dont

on multiplie les colonnes par des éléments non nuls de Fq . La multiplication d’une colonne par
un élément non nul ne modifiant pas la distance minimale, les codes de Reed-Solomon généralisés

Chapitre 1. Introduction à la théorie algébrique des codes correcteurs d’erreurs

ont les mêmes paramètres que les codes de Reed-Solomon et sont MDS.

Définition 1.88. (Codes alternants) On note RSn−r (α, v) un code de Reed-Solomon géné-
ralisé [n, n − r, r + 1]qm construit sur une extension Fqm de Fq .
Un code alternant Ak (α, v) est défini comme l’ensemble des mots d’un code de Reed-Solomon
généralisé RSn−r (α, v), dont les coordonnées sont à coefficients dans le sous-corps Fq .

Proposition 1.89. Soit RSn−r (α, v) un code de Reed-Solomon généralisé [n, n − r, r + 1]qm
construit sur une extension Fqm de Fq . Le code alternant Ak (α, v) correspondant (sur Fq )
est un code [n, k, d]q avec n − mr ≤ k ≤ n − r et r + 1 ≤ d.

Preuve.
Le code alternant est un code linéaire puisque la somme de mots du sous-code sur Fq est
stable par addition et multiplication externe. Le sous-code a une distance minimale au moins
égale à celle du code. Soit H = {Hij }1≤i≤n−r,1≤j≤n une matrice de contrôle de parité du code
RSn−r (α, v) de paramètres [n, n − r, r + 1]qm . On considère une base {e1 , · · · , em } de Fqm sur
Xm
Fq . Chacun des Hij peut s’écrire comme Hij = Hijk ek . On peut alors définir une matrice
k=1
H 0 rm × n à partir de H, en écrivant chacun des Hij en colonne dans la base {b1 , . . . , bm }.
Comme, par définition, les mots du code alternant Ak (α, v) sont les mots de Fn
q contenus dans
RSn−r (α, v), on a pour c ∈ Fn
q

c ∈ Ak (α, v) ⇔ Hct = 0.

Mais comme c ∈ Fn q , l’équivalence précédente reste vraie lorsque l’on développe Fqm sur une
base de Fq , soit pour c ∈ Fnq

Hct = 0 ⇔ H 0 ct = 0.

La matrice H 0 engendre donc une matrice duale de Ak (α, v) ; comme elle a rm lignes, elle
a pour rang au plus rm et donc la dimension du code alternant est supérieure à n − rm et
inférieure à n − r (la dimension du code sur l’extension). n

En pratique, la dimension des codes alternants reste proche de n − rm. La classe générale des
codes alternants peut se décoder en tant que sous-code d’un code de Reed-Solomon généralisé,
qui se décode à partir des codes de Reed-Solomon (en multipliant par v−1 = (v−1 −1
1 , · · · , vn )).
La classe des codes alternants contient un grand nombre de sous-classes avec des paramètres et
des décodages spécifiques.

VI.3. Codes de Goppa binaires

Les codes de Goppa ont été introduits par V. D. Goppa en 1970. Ils forment une classe
particulière des codes alternants et peuvent être vus comme une généralisation des codes BCH.
Ils sont en particulier très bons en caractéristique 2, où ils ont le même type de paramètres
que les codes BCH, mais sont beaucoup plus nombreux pour des paramètres donnés. Cette
dernière propriété en fait des codes très intéressants pour une utilisation en cryptographie dans
le cryptosystème de chiffrement à clé publique de R. McEliece (voir le chapitre suivant).

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 36 — #38

i

36

VI.3.1. Une autre construction pour les codes BCH au sens strict
Soit t = ordq (n) et soit α une racine n-ième de l’unité dans Fqt . Soit maintenant δ > 1 la
Partie . TABLE DES MATIÈRES

distance construite pour un code BCH au sens strict C. On voit alors, en reprenant la section
IV.3 sur les codes BCH, que c(x) = c0 + c1 x + · · · + cn−1 xn−1 est dans C si et seulement si
c(αi ) = 0 pour tout 1 ≤ i ≤ δ − 1. On remarque que l’on peut écrire

X
n−1
ci X n−1
n−1 X k −i n−1−k n−1
X k n−1
X
(xn − 1) = c i x (α ) = x ci (αk+1 )i . (1.1)
i=0
x − α−i i=0 k=0 k=0 i=0

X
n−1
Comme c(αi ) = 0 pour 1 ≤ i ≤ δ − 1, la somme ci (αk+1 )i est nulle pour 0 ≤ k ≤ δ − 2, et
i=0
donc le dernier membre de l’égalité précédente peut s’écrire comme un certain polynôme q(x)
fois xδ−1 . La dernière égalité devient donc

X
n−1
ci xδ−1 q(x)
−i
= , (1.2)
i=0
x−α xn − 1
que l’on peut aussi voir comme vérifiant l’égalité
X
n−1
ci
≡0 (mod xδ−1 ), (1.3)
i=0
x − α−i

où le modulo est considéré pour le polynôme a(x) lorsque l’on écrit le membre gauche de l’égalité
1.2 sous forme de fraction rationnelle a(x)
b(x)
(avec a(x) et b(x) premiers entre eux).
L’égalité 1.3 (dérivée de l’égalité 1.1) montre que les mots de Fq qui la vérifient sont exac-
tement les mots c(x) dont les coefficients sont tels que c(αi ) = 0 pour 1 6 i 6 δ − 1. Et donc le
code est le code BCH au sens strict de distance construite δ.
Cette égalité peut être généralisée en prenant un autre polynôme que le polynôme xδ−1 . Ce
point de vue permet d’introduire les codes de Goppa.

VI.3.2. Construction des codes de Goppa

Les codes de Goppa Γ (L, G) de longueur n sur Fq sont définis à partir d’un polynôme G(x)
de degré r, à coefficients dans une extension Fqm de Fq pour un m quelconque, ainsi que d’un
ensemble L = {α1 , α2 , · · · , αn } de n éléments de Fqm qui sont tels que G(αi ) 6= 0 pour αi ∈ L.
En géneral, on prend pour L l’ensemble de tous les éléments de Fqm qui ne sont pas racines de
G. Le polynôme G est appelé polynôme de Goppa.
Définition 1.90. (Code de Goppa) Avec les notations ci-dessus, le code de Goppa Γ (L, G)
est composé de tous les mots c(c1 , c2 , · · · , cn ) ∈ Fq vérifiant

déf
X
n
ci
Rc (x) = ≡0 (mod G(x)).
i=1
x − αi

Lorsque le polynôme G(x) est irréductible, on dit que le code est un code de Goppa irréductible.
L’égalité modulo G(x) est considérée comme précédemment en termes de fraction rationnelle
par rapport à a(x) pour Rc (x) = a(x)
b(x)
et a(x) et b(x) premiers entre eux.

Théorème 1.91. Le code de Goppa Γ (L, G) de longueur n sur Fq , défini à partir d’un
polynôme G(x) de degré r, à coefficients dans une extension Fqm de Fq pour un m quelconque,
est un code linéaire de longueur n, de dimension k ≥ n−mr et de distance minimale d ≥ r+1.
Dans le cas binaire (q = 2), si G(x) n’a pas de racine multiple, alors d ≥ 2r + 1.

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 37 — #39

i

37

Preuve. Le code Γ (L, G) est clairement linéaire : si c ∈ Γ (L, G), alors on a γc ∈ Γ (L, G) et
si c1 , c2 ∈ Γ (L, G), alors on a c1 + c2 ∈ Γ (L, G) d’après les propriétés de somme modulo G(x)
intervenant pour le calcul de Rc (x). On va maintenant calculer le dual de Γ (L, G). On remarque

Chapitre 1. Introduction à la théorie algébrique des codes correcteurs d’erreurs

tout d’abord que
1 (G(x) − G(αi ))
≡ −G(αi )−1 (mod G(x)),
x − αi x − αi
puisque −G(αi )−1 (G(x) − G(αi )) = 1 − G(αi )G(x) ≡ 1 (mod G(x)). On obtient donc

X
n
(G(x) − G(αi ))
c∈Γ ⇔ ci G(αi )−1 ≡ 0 (mod G(x)). (1.4)
i=1
x − αi

X
r
Si l’on écrit G(x) = gi xi avec gi ∈ Fqm et gr 6= 0, alors
i=0

(G(x) − G(αi ))
G(αi )−1 = gr (xr−1 + xr−2 αi + · · · + αr−1
i )
x − αi
+gr−1 (xr−2 + xr−3 αi + · · · + αr−2
i ) + · · · + g2 (x + αi ) + g1 .

En mettant les coefficients de xi à zéro dans 1.4, on obtient que c ∈ Γ si et seulement si

H.ct = 0 avec

gr G(α1 )−1 gr G(αn )−1

0 1
...
B (gr−1 + α1 gr )G(α1 )−1 ··· (gr−1 + αn gr )G(αn )−1 C
H=B C.
@ ... A
(g1 + α1 g2 + αr−1
1 gr )G(α1 )−1 ... (g1 + α1 g2 + αr−1
1 gr )G(αn )−1

Mais on peut décomposer H sous la forme

0 1 0 1
gr 0 0 ··· 0 1 1 ··· 1
B
B gr−1 gr 0 ··· 0 C B
C B α1 α2 ··· αn C
α21 α22 α2n
C
H=B
B gr−2 gr−1 gr ··· 0 C.B
C B ··· C
C
@ ··· ··· A @ ··· ··· A
g1 g2 g3 ··· gr αr−1
1 αr−1
2 ··· αr−1
n

G(α1 )−1
0 1
0 ··· 0
B 0 G(α2 )−1 ··· 0 C
.B C.
@ 0 0 ··· 0 A
0 0 ··· G(αn )−1

Comme la première des trois matrices est une matrice carrée inversible (puisque gr 6= 0), on en
déduit qu’une matrice de contrôle de parité H peut aussi s’écrire comme le produit des deux
dernières matrices qui peut s’écrire sous la forme

G(α1 )−1 G(αn )−1

0 1
···
B α1 G(α1 )−1 ··· αn G(αn )−1 C
H=B C.
@ ··· ··· A
r−1 −1 r−1 −1
α1 G(α1 ) ··· αn G(αn )
Cette dernière écriture montre que le code de Goppa Γ (L, G) est un code alternant avec un
ensemble de points α = (α1 , . . . , αn ) et y = (G(α1 )−1 , . . . , G(αn )−1 )). On peut donc en déduire
d’après les résultats sur les codes alternants que le code Γ (L, G) a pour dimension k ≥ n − rm
et d ≥ r + 1.

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 38 — #40

i

38

De manière similaire au cas des codes BCH binaires qui sont relativement meilleurs que
les codes BCH généraux, on peut aussi faire mieux avec des codes de Goppa binaires. Soit
Γ (L, G) un code de Gopa binaire et soit c(c1 , . . . , cn ) un mot du code, non nul, de poids w avec
Partie . TABLE DES MATIÈRES

cl1 = · · · = clw = 1. On introduit

déf
fc (x) = Πw
i=1 (x − αli ).

Si l’on dérive par rapport à x, on obtient

X
w
fc0 (x) = Πj6=i (x − αlj )
i=1

et
X
w
1 f 0 (x)
Rc (x) = = c .
i=1
x − αli fc (x)
Par définition du code, les αi sont distincts et donc fc0 (x) et fc (x) n’ont pas de facteurs communs ;
de plus, comme les αi ne sont pas racines de G(x), les polynômes fc (x) et G(x) n’ont pas de
facteur commun et sont premiers entre eux. On obtient donc

Rc (x) ≡ 0 (mod G(x)) si et seulement si G(x)|fc0 (x).

Comme on travaille sur une extension de F2 , fc0 (x) ne contient que des puissances paires et
peut s’écrire sous la forme d’un carré parfait fc0 (x) 2
Pl= p(x)2i, d’un certain polynôme p(x). En
0 0
effet, fc (x) est un polynôme de la forme fc (x) = i=0 ai x avec ai ∈ F2m et, comme on est
élément ai de F2m peut s’écrire sous la forme d’un carré ai = b2i
sur une extension de F2 , tout P
pour bi ∈ F2m , d’où fc (x) = ( li=0 bi xi )2 .
0

Comme fc0 (x) est un carré parfait et que G(x) divise fc0 (x), alors, fc0 (x) est aussi divisible par
le polynôme de plus petit degré, qui est à la fois un carré parfait et est divisible par G(x). Dans
le cas où G(x) n’a pas de racine multiple, le plus petit polynôme qui est un carré parfait divisible
par G(x) est G(x)2 . Donc, G(x)2 | fc0 (x) et, comme deg (fc0 (x)) = w − 1 et deg (G(x)2 ) = 2r, il
vient w − 1 ≥ 2r pour tout mot c du code non nul. Dans le cas d’un code de Goppa binaire avec
G(x) sans racine multiple, on en déduit que d ≥ 2r + 1. n

Les codes de Goppa non binaires peuvent se décoder en tant que codes alternants. Pour le
cas binaire, il existe un algorithme spécifique de N. J. Patterson que nous ne décrivons pas ici.
Toujours pour le cas binaire, si l’on prend un polynôme G(x) irréductible sur Fqm (et il y en a
beaucoup !), on obtient un polynôme sans racine multiple.

Exemple 1.92. Soit le corps F8 construit comme extension de F2 par le polynôme x3 +x+1.
Soit α une racine primitive de F8 . On veut construire le code de Goppa binaire avec pour L,
l’ensemble des éléments de F8 , pris dans l’ordre {α, α2 , ..., α6 , 1, 0} (avec α7 = 1) et pour
polynôme G(x) = 1 + αx + x2 . On vérifie tout d’abord que G(x) ne s’annule pas sur F8 . On
construit alors la matrice H du dual sur F8 du code alternant induit par le polynôme de Goppa,
donnée par

G(α)−1 G(α2 )−1 G(α6 )−1 G(1)−1 G(0)−1

„ «
...
H= −1 2 2 −1 6 6 −1 −1 −1 ,
αG(α) α G(α ) . . . α G(α ) 1.G(1) 0.G(0)

soit
α5 α6 α5 α2 α2 α6
„ «
1 1
H= .
α 1 α2 α2 1 α α6 0
Pour obtenir le sous-code sur le sous corps, on choisit une base de F8 sur F2 , comme par
exemple {1, α, α2 }, et on écrit les éléments de H représentés en binaire et en colonne dans cette

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 39 — #41

i

39

base. On obtient dans cette base α3 = 1 + α, α4 = α + α2 , α5 = 1 + α + α2 et α6 = 1 + α2 , ce

qui donne, pour la matrice du dual binaire

Chapitre 1. Introduction à la théorie algébrique des codes correcteurs d’erreurs

0 1
1 1 1 1 0 0 1 1
B 0 1 0 1 0 0 0 0 C
B C
B 0 1 1 1 1 1 1 0 C
H2 = BB 0 1 0 0 1 0 1
C.
B 0 C
C
@ 1 0 0 0 0 1 0 0 A
0 0 1 1 0 0 1 0

Par exemple l’avant-dernière colonne correspond bien à α6 , écrit deux fois en colonne dans la
base {1, α, α2 }. Le code a pour dimension k ≥ 8 − 3.2 = 2 ; comme le polynôme G(x) n’a pas de
zéro multiple, on doit trouver d ≥ 2 ∗ 2 + 1 = 5. Le calcul du code donne un code de dimension
2 engendré par les mots (1, 0, 1, 0, 1, 1, 1, 1) et (0, 1, 1, 1, 1, 0, 0, 1), soit un code binaire [8, 2, 5].

Test 1.37. l’exemple, construire le code de Goppa binaire

de polynôme G(x) = 1 + x + x2 .
En reprenant le même corps F8 que dans

VII. Décodage en liste des codes de Reed-Solomon

VII.1. Introduction au décodage en liste

On a vu dans la section II que, pour un code [n, k, d]q , on pouvait décoder de manière
univoque jusqu’à la distance t = b d−1
2
c. Mais que se passe-t-il pour une erreur e de poids τ plus
grande que t ? Prenons par exemple le code C [5, 2, 2] de matrice génératrice
„ «
1 1 1 0 0
G= .
0 0 0 1 1
Comme d = 2, on a t = b(2 − 1)/2c = 0 et il n’y a pas de décodage univoque pour une erreur
quelconque de poids 1 (en fait pour aucun poids d’erreur donné) (voir le théorème 1.26)
Considérons le mot reçu 11000 ; ce mot peut se décoder de manière univoque en 11100 avec
une erreur de poids 1. Prenons maintenant le mot 00010 ; ce mot peut se décoder en 00000
ou 00011 avec une erreur de poids 1. On voit donc qu’au-delà de t, plusieurs cas peuvent se
produire : certains mots auront un décodage univoque et d’autres non.
Considérons un mot y de l’espace à distance τ d’un mot d’un code [n, k, d]q . Si τ ≤ t =
b d−1
2
c, le nombre de mots du code à distance inférieure ou égale à τ sera 1. Si maintenant l’on
prend τ tendant vers n, le nombre de mots du code à distance inférieure à τ tendra vers tous
les mots du code, soit un nombre exponentiel qk . Entre ces deux zones, τ ≤ t et τ de l’ordre de
n, il existe une zone dans laquelle le nombre de mots du code à distance inférieure à τ ne sera
ni fixe ni exponentiel. En fait, on peut montrer qu’il existe une zone dans laquelle le nombre de
mots est polynomial en n.
Le décodage en liste introduit par P. Elias en 1957 consiste, pour un mot de l’espace, à
renvoyer une liste de tous les mots du code à distance inférieure ou égale à τ. La longueur de la
liste peut être variable, mais a priori elle n’est pas trop grande.
En pratique, surtout pour les codes avec une grande distance minimale, cela permet souvent
de décoder pour des erreurs de poids plus important que b(d − 1)/2c : la probabilité de mal
décoder existe, mais elle est très faible pour τ proche de b(d − 1)/2c et elle grandit avec τ.
Par exemple, prenons le code de Reed-Muller R(1, 10) de paramètre [1024, 11, 512]. Si l’on s’en

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 40 — #42

i

40

tient au décodage classique, on peut décoder de manière univoque jusqu’à w(e) = t = b(512 −
1)/2c = 255. Pourtant, en pratique, si l’on calcule de manière combinatoire la probabilité qu’un
mot avec une erreur de poids donné τ soit décodable de manière univoque, on trouve que la
Partie . TABLE DES MATIÈRES

probabilité qu’un mot avec une erreur aléatoire de poids 410 soit décodable de manière univoque
est de l’ordre de 10−9 !
Lorsque l’on fait du décodage à distance bornée, on est sûr de décoder l’erreur si son poids est
inférieur à une distance donnée (en général b d−1
2
c). Maintenant, si l’on est prêt à admettre une
probabilité d’erreur dans le décodage pour une erreur de poids fixé, il est possible de décoder
beaucoup plus loin.
La première famille de codes pour laquelle il a été possible de trouver un décodage en liste
avec une complexité polynomiale a été la famille des codes de Reed-Solomon pour laquelle M.
Sudan a proposé un algorithme en 1996. Sa méthode a été généralisée avec de meilleurs résultats
par V. Guruswami et M. Sudan en 1999. Par la suite, des algorithmes ont aussi été proposés
pour les codes de Reed-Muller et certains codes alternants. Dans ce qui suit, nous présentons le
premier algorithme de Sudan.

VII.2. Algorithme de Sudan

L’algorithme de Sudan peut être vu comme une généralisation de de l’algorithme de Welch-
Berlekamp décrit dans la section V. On reprend les notations du code de Reed-Solomon de la
section précédente. On considère un code de Reed-Solomon sur Fq , [n, k, d]q avec d = n − k + 1.
Soient c = (c1 , . . . , cn ) = (f(x1 ), . . . , f(xn )) le mot émis et r = (r1 , . . . , rn ) = c + e le mot reçu
avec e qui est un vecteur d’erreurs de poids au plus τ.
L’algorithme utilise à nouveau un polynôme bivarié, mais de degré plus élevé en y. On cherche
ici un polynôme bivarié Q(x, y) = Q0 (x) + Q1 (x)y + Q2 (x)y2 + . . . + Ql (x)yl , où l est un entier,
vérifiant :
1. Q(xi , ri ) = 0, ∀i ∈ {1 . . . n} ;
2. deg (Qj (x)) ≤ n − τ − 1 − j(k − 1), ∀j ∈ {0, 1, · · · l} ;
3. Q(x, y) 6= 0.
Dans l’algorithme, l est la taille de la liste renvoyée, c’est-à-dire le nombre de mots poten-
tiellement solutions au problème de décodage. Le problème de trouver Q(x, y) est un problème
d’interpolation.

l
Proposition 1.93. Si τ < n l+1 − 2l (k − 1) et n − τ − 1 − l(k − 1) ≥ 0, alors un tel polynôme
Q(x, y) existe.

Preuve. La première condition sur Q(x, y) donne n contraintes. La deuxième condition donne
des degrés de liberté qui correspondent aux différents coefficients des polynômes Qi . Le polynôme
Q(x, y) peut s’obtenir en résolvant un système en les coefficients des Qj (x). Plus précisément,
chaque polynôme Qj a degré au plus n − τ − 1 − j(k − 1), ce qui donne 1 + n − τ − 1 − j(k − 1)
degrés de libertés. Un tel polynôme Q(x, y) non nul existera donc si le nombre de degrés de
liberté est strictement supérieur au nombre de contraintes, soit si
X
l
(1 + n − τ − 1 − j(k − 1)) > n.
j=0

Le premier membre de l’inégalité peut se simplifier en

X
l Xl Xl
1
(1 + n − τ − 1 − j(k − 1)) = (n − τ) − j(k − 1) = (l + 1)(n − τ) − l(l + 1)(k − 1).
j=0 j=0 j=0
2

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 41 — #43

i

41

On peut donc trouver un tel polynôme si

Chapitre 1. Introduction à la théorie algébrique des codes correcteurs d’erreurs

1
(l + 1)(n − τ) − l(l + 1)(k − 1) > n,
2
soit
l n l
(l + 1)(n − τ) > n + (l + 1)(k − 1) ⇔ n − τ > + (k − 1)
2 l+1 2
qui devient
n − n(l + 1) l l l
τ<− − (k − 1) ⇔ τ < n − (k − 1),
l+1 2 l+1 2
ce qui est bien la première inégalité recherchée ; la deuxième inégalité vient du fait que le degré
de Ql (x) ne doit pas être négatif. n

Une fois un tel polynôme Q(x, y) construit, on peut décoder à partir de la proposition
suivante.

Théorème 1.94. Si Q(x, y) vérifie les contraintes précédentes et si le mot de code envoyé
est c(f) = (f(x1 ), f(x2 ), · · · , f(xn )) avec deg (f(x)) < k, alors

(y − f(x)) | Q(x, y).

Preuve. Pour un polynôme Q(x, y) vérifiant les conditions précédentes, on considère le poly-
nôme univarié Q(x, f(x)). D’après les conditions sur les degrés des Qj (x), chacun des polynômes
f(x)j Qj (x) est de degré n − τ − 1 et donc le polynôme Q(x, f(x)) est de degré au plus n − τ − 1.
Maintenant, par hypothèse, on a Q(xi , ri ) = 0 pour tout i dans {1, 2, · · · , n}, et comme
f(xi ) = ri pour au moins n − τ valeurs de i (l’erreur étant de poids τ), on a finalement
Q(xi , f(xi )) = 0 pour au moins n − τ valeurs de i. Le polynôme Q(x, f(x)) est donc un po-
lynôme de degré ≤ n − τ − 1, ayant au moins n − τ racines. C’est donc le polynôme nul.
Montrons qu’alors (y − f(x)) | Q(x, y). Le polynôme Q(x, y) s’écrit

Q(x, y) = Q0 (x) + Q1 (x)y + Q2 (x)y2 + · · · + Ql (x)yl .

Comme Q(x, f(x)) = 0, il vient

0 = Q0 (x) + Q1 (x)f(x) + Q2 (x)f(x)2 + · · · + Ql (x)yl ,

soit
Q0 (x) = −(Q1 (x)f(x) + Q2 (x)f(x)2 + · · · + Ql (x)yl ).
En remplaçant cette dernière expression de Q0 (x) dans l’expression de Q(x, y), on obtient

Q(x, y) = −(Q1 (x)f(x) + · · · + Ql (x)f(x)l ) + Q1 (x)y + · · · + Ql (x)yl

= Q1 (x)(y − f(x)) + Q2 (x)(y2 − f(x)2 ) + . . . + Ql (x)(yl − f(x)l )

X
l X
j−1
= (y − f(x)) (Qj (x) yp f(x)j−1−p )
j=1 p=0

et Q(x, y) est bien divisible par (y − f(x)). n

On en déduit l’algorithme de décodage en liste suivant.

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 42 — #44

i

42

Méthode Décodage en liste de Sudan des codes de Reed-Solomon

Partie . TABLE DES MATIÈRES

1. Pour un mot reçu r avec une erreur de poids τ, construire le polynôme interpolé Q(x, y) =
Q0 (x) + Q1 (x)y + Q2 (x)y2 + . . . + Ql (x)yl .
2. Trouver les facteurs de la forme (y − f(x)) avec deg (f(x)) < k qui divisent Q(x, y). Si
l
τ < n l+1 − 2l (k − 1), alors le mot émis fait partie de cette liste.

Il existe plusieurs méthodes possibles pour chacune de ces étapes. L’étape la plus coûteuse
est l’étape 1 : il est toujours possible de trouver le polynôme Q(x, y) en résolvant un système
linéaire, mais les méthodes de type interpolation multivariée donnent les meilleurs résultats en
termes de complexité calculatoire.
Une analyse détaillée des paramètres de l’algorithme permet de montrer que cet algorithme
améliore le décodage en b(d − 1)/2c pour un taux k/n < 1/3. On peut aussi montrer qu’asymp-
√
totiquement pour k/n petit, et k et n grands l’algorithme
q permet de décoder jusqu’à n − 2nk
erreurs, soit un taux d’erreurs décodables en 1 − 2kn
, qui tend vers 1 lorsque k/n tend vers
zéro. Ce résultat est à comparer au décodade classique qui ne décode que jusqu’à un taux de
1/2 lorsque k/n tend vers zéro.
Remarque. L’algorithme de décodage de Guruswami-Sudan améliore ce dernier algorithme
en introduisant plus de contraintes sur le polynôme Q(x, y). À la différence de l’algorithme de
Sudan, il améliore le décodage classique des codes de √
Reed-Solomon pour des taux quelconques
et, pour k/n petit, il permet de décoder jusqu’à n − nk erreurs.

Exemple 1.95. On considère le code de Reed-Solomon [10, 2, 9]11 défini pour xi = 2i−1 .
Par décodage classique, on peut décoder jusqu’á t = (9 − 1)/2 = 4 erreurs. Prenons l = 2
dans la définition du polynôme interpolé Q(x, y), alors on peut décoder jusqu’à une erreur de
l
poids τ < n 1+l − 2l (k − 1) = 10.2/3 − 1, soit jusqu’à τ = 5. Considérons le mot à décoder
r = (7, 6, 5, 3, 8, 7, 9, 0, 2, 5). On cherche un polynôme Q(x, y) = Q0 (x) + Q1 (x)y + Q2 (x)y2
avec Q0 (x) = a0 + a1 x + a2 x2 + a3 x3 + a4 x4 , Q1 (x) = b0 + b1 x + b2 x2 + b3 x3 et Q2 (x) =
d0 +d1 x+d2 x2 , tel que Q(xi , ri ) = 0 pour 1 6 i 6 10. En écrivant les contraintes sur Q(x, y), on
obtient un système linéaire de 10 équations et 12 inconnues, les a0 , ..., a4 , b0 , ..., b3 , d0 , d1 , d2 .
Une résolution du système amène un espace solution de dimension 2, engendré par les deux
vecteurs (1, 0, 0, 2, 2, 4, 6, 0, 7, 1, 10, 6) et (0, 1, 10, 3, 1, 2, 7, 10, 2, 5, 2, 9). Prenons par exemple le
premier vecteur. On peut retrouver un exemple de polynôme Q(x, y) en écrivant Q0 (x), Q1 (x)
et Q2 (x) à partir des coordonnées de ce vecteur, comme défini précd́emment. Ce qui amène
Q(x, y) = 1 + 2x3 + 2x4 + y(4 + 6x + 7x3 ) + y2 (1 + 10x + 6x2 ), qui se factorise en Q(x, y) =
7(y − (4x + 3))(x3 + 2x2 y + 7x2 + 7xy + 9x + 4y + 10). Il existe un facteur de la forme
(y − f(x)) qui divise Q(x, y). On en déduit que le mot décodé correspond à f(x) = 4x + 3, soit
c(f) = (7, 10, 5, 6, 8, 1, 9, 3, 2, 0). On vérifie de plus que l’erreur (0, 7, 0, 8, 0, 6, 0, 8, 0, 5) a poids
5.

Test 1.38. décoder le mot (7, 1, 0, 9, 5, 9, 5, 8, 3, 4) pour

τ = 5. Qu’observe-t-on ?
En reprenant le même code que dans l’exemple,

VIII. Exercices

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 43 — #45

i

43

1.1. O Montrer que pour un code cyclique binaire, ajou-

ter {0} à l’ensemble de définition du code revient
1) Montrer que si C est un code auto-orthogonal à prendre le sous-code des mots de poids pair du

Chapitre 1. Introduction à la théorie algébrique des codes correcteurs d’erreurs

dont la matrice génératrice est composée de mots code.
de poids multiples de 4, alors tous les mots du
code ont un poids multiple de 4. 1.9. O

2) Montrer que si C est auto-orthogonal sur F3

alors, pour tout x ∈ C, wH (x) ≡ 0 (mod 3). Combien y-a-t-il de codes cycliques binaires pos-
sibles en longueur 23 ? Idem sur F3 en longueur
1.2. O 11 ? Quels sont-ils ? (On ne cherchera pas à
trouver la distance minimale).
Montrer à partir de la table des syndromes du
code de Hamming [7, 4, 3] que le code décode de 1.10. O

manière univoque toutes les erreurs de poids 1.

Trouver les codes BCH et leurs paramètres pour
1.3. Construction des codes de Hamming q = 3 et n = 13.
sur Fq O
1.11. BCH non binaires OO

On veut généraliser la construction des codes de

En utilisant le même type de raisonnement
Hamming sur Fq . Pour m fixé, montrer qu’en
que pour les codes BCH binaires, montrer qu’il
prenant pour colonnes du code des droites vec-
existe des codes BCH ternaires de paramètres
torielles (on prend une colonne à une constante
[3m − 1, k ≥ 3m − 1 − 2mt, d ≥ 3t + 1]3 . Géné-
multiplicative non nulle près) plutôt que tous
raliser cette construction au cas q-aire.
les éléments non nuls de Fm q , on obtient plus
généralement par cette construction des codes 1.12. O
r r
de paramètres [ qq−1−1 q −1
, q−1 − r, 3]q .
On considère un code de Reed-Solomon [7, 3, 5]8 .
1.4. Construction du code de Golay ter- On encode xi = αi−1 pour α un élément pri-
naire OO mitif. Prendre un mot du code, ajouter deux
erreurs et le décoder. Peut-on savoir directe-
On repart de la construction du code de Golay ment à partir des syndromes s’il y a une ou deux
binaire. Considérer pour A une matrice 5 × 5 erreurs ?
dont les colonnes sont indicées de 0 à 4. La pre-
mière ligne de A est construite en prenant 0 pour 1.13. Codes de Reed-Solomon cycliques
OOO
la première coordonnée puis 1 pour un indice de
colonne qui est un carré modulo 5 et −1 sinon.
Montrer que la construction précédente, avec Soit α un élément primitif de Fq . Soit RSk
cette nouvelle matrice A, permet de construire le code de Reed-Solomon, de longueur n =
un code [12, 6, 6]3 , appelé code de Golay étendu q − 1 et de dimension k, défini sur un en-
ternaire et le code de Golay ternaire [11, 6, 5]3 . semble xi = αi−1 pour i = 1, . . . , q − 1 par
c(f) = (f(x1 ), f(x2 ), · · · , f(xq−1 )) pour f ∈ Pk
1.5. O avec Pk = {f ∈ Fq [x]|deg(f) < k}. Montrer que
RSk est un code cyclique de longueur n, de di-
Montrer que les deux codes de Golay [23, 12, 7] mension k sur Fq et de polynôme générateur
et [11, 6, 5]3 sont parfaits. g(x) = (x − α)(x − α2 ) · · · (x − αn−k ).
1.6. O 1.14. Codes BCH binaires et codes de
Reed-Solomon OO
Montrer qu’il ne peut pas exister de code binaire
[12, 7, 5]. Soit C un code BCH binaire primitif au sens
strict, de longueur n = 2m − 1 et de distance
1.7. OO construite δ. Montrer que C est exactement le
sous-code binaire sur le sous-corps du code de
Montrer que la famille infinie des codes de Reed-Solomon cyclique RSn−δ−1 , comme défini
Reed-Muller R(m, m−1 2
) pour m impair quel- à l’exercice précédent.
conque est une famille de codes de taux fixe 1/2.
Cette famille de codes est-elle asymptotiquement 1.15. OO
bonne ?
Pour l = 1 ou l = 2, quand est-ce que le dé-
1.8. O codage en liste de Sudan améliore le décodage
classique ?

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 44 — #46

i

44

Première partie
Solutions des tests

Solutions des tests

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 45 — #47

i

Deuxième partie
Solutions des tests
0.1.S’il y a une erreur dans un des quatre bits d’information, il y aura deux erreurs sur une ligne et une colonne
différente. Si l’erreur n’est pas sur un des quatre bits d’information, il y aura, soit une ligne, soit une colonne
avec une erreur, et donc l’erreur sera dans la ligne ou colonne extérieure.
0.2.On suppose qu’il y a exactement 1 erreur. Il y a plusieurs cas possibles : si l’erreur est sur p1 , p2 ou p3 ,
deux des cercles auront une somme paire et le troisième correspondant à l’un des pi aura une somme impaire.
Si l’erreur est en d1 , d2 ou d3 , deux des cercles auront une somme incorrecte et l’erreur sera à l’intersection
de ces deux cercles (mais pas d4 ). Enfin, si les trois cercles ont une somme incorrecte, l’erreur sera d4 .
0.3.Si l’on part d’une matrice identité avec des 1 sur la diagonale, cette matrice engendre tout l’espace. On
considère les vecteurs ei de longueur n valant 0 partout sauf sur la coordonnée i où ils valent 1. Les ei sont
0 0
indépendants et engendrent Fn 2 . Considérons maintenant ei = ei + en pour 1 6 i 6 n − 1. Les ei sont
indépendants, et comme la somme de deux mots avec un nombre pair de 1 a aussi un nombre pair de 1, on en
déduit que le code engendré par les ei0 est contenu dans le code de parité. Ce code a pour dimension n − 1.
Comme le code de parité ne peut avoir dimension n car sinon il contiendrait e1 , ce qui n’est pas possible, alors
ce code est exactement le code de parité de dimension n − 1.
0.4.Les mots du code sont les mots (d1 , d2 , d3 , d4 , p1 , p2 , p3 ) satisfaisant les conditions de parité pour les
trois cercles. Si deux mots appartiennent au code alors, d’après les propriétés de parité, ces conditions seront
aussi vérifiées pour la somme des coordonnées de ces mots. Le code est donc linéaire.
Pour trouver une matrice génératrice du code, par linéarité il suffit de regarder les valeurs des redondances
p1 , p2 et p3 pour de l’information fixée. On peut par exemple regarder la valeur des pi pour des valeurs
(d1 , d2 , d3 , d4 ) valant respectivement (1000), (0100), (0010) et (0001) qui forment des vecteurs indépen-
dants. On trouve donc comme matrice génératrice

1 0 0 0 0 1 1
0 1
B 0 1 0 0 1 0 1 C
@ 0 .
0 1 0 1 1 0 A
0 0 0 1 1 1 1

0.5. 0 1
0 0 1 1 0 0
H=@ 0 1 0 0 1 0 A·
1 1 1 0 0 1

0.6.C’est la définition du dual.

0.7.Sur F2 , lorsque l’on fait la somme des mots, la somme de deux 1 s’annule : ceci donne le résultat. Si
x.y = 0 alors le nombre de 1 en commun sur une même coordonnée est pair et donc, le poids de x ∗ y est pair,
ce qui implique que 2w(x ∗ y) est multiple de 4.
0.8.Cela vient directement de la linéarité : d(x, y) = w(x − y) et x − y ∈ C par linéarité.
0.9.Si l’on calcule tous les mots possibles, on trouve d = 3.
0.10.Ces codes sont distincts puisque l’on peut trouver un mot dans l’un qui n’est pas dans l’autre. Si l’on
permute les colonnes 2 et 4 pour un code, on obtient l’autre.
0.11.On n’utilise jamais la notion de linéarité dans la preuve.
0.12.Le syndrome vaut (100)t avec un représentant principal unique : (00100). Le mot se décode en (11110).
Pour le second mot, le syndrome est (101)t . Dans ce cas (voir la table des syndromes), il y a trois représentants
principaux potentiels (il y a trois mots de poids 2 dans le translaté associé) ; un seul a été choisi pour la table,
mais le mot d’origine peut aussi correspondre à l’un des deux autres.
0.13.La distance minimale vient de la remarque précédente. L’énumérateur des poids est WH8 (x, y) = x8 +
14x4 y4 + y8 .
0.14.On a vu que C1 ⊕ C2 = {{(c1 |c2 ) c1 ∈ C1 } c2 ∈ C2 }. D’après la définition du polynôme énumérateur,
si l’on a par exemple c1 = (00101) et c2 = (1110), on leur associe respectivement les monômes x3 y2
et x1 y3 et pour la concaténation de c1 et c2 , on obtient (001011110) de monôme x4 y5 , exactement le
produit des deux monômes associés à c1 et c2 . Soit WC1 (x, y) l’énumérateur des poids de C1 . Par définition,
C1 ⊕ C2 = {{(c1 |c2 ) c1 ∈ C1 } c2 ∈ C2 }. D’après ce que l’on vient de voir, la contribution de {(c1 |c2 ) c1 ∈ C1 }
sera le monôme associé à c2 fois WC1 (x, y) et le résultat en découle en faisant varier c2 .

0.15.C’est une simple généralisation du cas binaire ; on prend tous les vecteurs de Fm
q à une constante près. Par
exemple, sur F3 avec m = 2, on a comme colonnes (10)t , (01)t , (11)t et (12)t ; on considère que la colonne
(20) est associée à (10)t . On obtient un code [4, 2, 3]3 .

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 46 — #48

i

46

0.16.Il suffit d’écrire les aij en fonction des ai .

Solutions des tests

0.17.Il suffit de calculer tous les mots possibles, modulo un facteur non nul. Par exemple, (100111) est dans
le code, donc ω(100111) et ω2 (100111), aussi, avec le même poids. Soit, en tout, simplement vingt et une
possibilités ((64 − 1)/3) en ne comptant pas le mot nul tout à 0.
0.18.Le code R(1, 2) est un code [4, 3, 2], le code R(0, 2) est le code engendré par le mot (1111). On applique
ensuite la construction de Plotkin.
0.19.C’est une application directe du théorème.
0.20.Faire le calcul.
0.21.Non, car il existe des mots de l’espace qui sont à distance r de deux mots du codes (par exemple le mot
nul et un mot de poids 2r). Il n’y a donc pas de décodage univoque pour ces éléments et le code n’est pas
parfait.
0.22.Les boules de rayon re (C) ne s’intersectent pas, alors que les boules de rayon rc (C) recouvrent tout
l’espace par définition, donc re (C) ≤ rc (C). Ces deux rayons sont égaux uniquement pour des codes parfaits.
0.23.En reprenant la même idée que dans le lemme 1.52, on peut montrer que, si le rayon de recouvrement
d’un code linéaire C avec B2 (n, d) mots, est supérieur ou égal à d, alors on peut construire un code linéaire,
C 0 = C ∪ x + C, de distance minimale d, pour un x choisi comme dans le lemme, ce qui montre que le rayon
de recouvrement de C est au plus d − 1. Le reste de la démonstration est identique à la preuve de la borne de
Gilbert-Varshamov.
0.24.C0 = {0}, C1 = {1, 2, 4, 8}, C3 = {3, 6, 12, 9}, C5 = {5, 10}, C7 = {7, 14, 13, 11}.
0.25.ord2 (9) = 6, 26 −1 = 9×7, C0 = {0}, C1 = {1, 2, 4, 8, 7, 5}, C3 = {3, 6}, x9 −1 s’écrit donc sous la forme
x9 − 1 = (x − 1).p1 (x).p2 (x) où deg (p1 (x)) = 6 et deg (p2 (x)) = 2. Comme il n’y a qu’un seul polynôme
irréductible de degré 2 sur F2 : x2 + x + 1, on a p2 (x) = x2 + x + 1 et p1 (x) = (x9 − 1)/((x − 1).(x2 + x + 1)) =
x6 + x3 + 1.
0.26.On peut partir du polynôme irréductible de degré 3 :x3 + x + 1. On peut prendre comme élément primitif
α = x. Dans ce cas par exemple α6 = x6 (mod x3 + x + 1) = x2 + 1 = (1 + x)2 = (α3 )2 .
0.27.On obtient un code [7, 4, 3] (le code de Hamming).
0.28.On connaît la factorisation de x7 − 1 = (x + 1)(x3 + x2 + 1)(x3 + x + 1) = g1 (x).g2 (x).g3 (x). On calcule
les différents cas possibles (23 = 8). Par exemple, pour le polynôme générateur g2 (x).g1 (x), la dimension est
7 − 4 = 3 et la distance minimale 4.
0.29.Prendre αi au lieu de α revient à permuter les colonnes du code par l’application qui envoie la colonne
j sur la colonne ij (mod n). Cette opération est bien une permutation puisque pgcd(i, n) = 1.

0.30.h(x) = x4 + x3 + x2 + 1. Si l’on définit F32 à partir du polynôme x3 + x + 1, on a T = {1, 2, 4} pour le

code et T = {0, 1, 2, 4} pour le dual.
0.31.T = C1 = {1, 2, 4}. Il y a 2 éléments consécutifs 1 et 2 donc la distance est au moins 3. En calculant le
polynôme générateur, on trouve un mot de poids 3, donc la distance est exactement 3. Si l’on ajoute 0 à T , on
trouve d = 4. Pour la longueur 23, le code est un code [23, 12, d] ; on trouve d ≥ 5 car il y a quatre éléments
qui se suivent dans C1 : {1, 2, 3, 4}. En fait, ce code est le code de Hamming binaire, d = 7 et la borne n’est
pas optimale.
0.32.Prenons par exemple α = 3 comme racine primitive de F7 . On obtient g(x) = (x − α)(x − α2 )(x − α3 ) =
x3 + 3x2 + x − 1. Le code est un code [6, 3, 4]7 .

0.33.g(x) = x10 + x8 + x5 + x4 + x2 + x + 1, l’erreur est e(x) = x8 + x9 .

0.34.Les zéros de σ(x) sont les inverses des emplacements des erreurs. Comme σ 0 (x) = xt σ(x−1 ), les zéros
de σ 0 (x) sont les inverses des zéros de σ(x), soit les emplacements d’erreurs. Comme gj (x) est multiple de
σ 0 (x), à une constante non nulle près, les racines de gj (x) sont exactement les emplacements d’erreurs.

0.35.σ(x) = α2 x2 + α12 x + 1.
0.36.Une matrice génératrice reprend les trois premières lignes de la matrice de l’exemple précédent. Le mot
envoyé correspond à f(x) = 1 + 2x + 3x2 et l’erreur vaut (0, 0, 2, 0, 0, 0).
0.37.On obtient à nouveau un code [8, 2, 5].
0.38.Il y a deux mots du code possibles et l’algorithme renvoie une liste. Les mots à distance 5 sont (7, 1, 0, 9, 5, 8, 3, 4, 6, 10)
et (6, 10, 7, 1, 0, 9, 5, 8, 3, 4).

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 47 — #49

i

Troisième partie
Solutions des exercices

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 48 — #50

i

Quatrième partie
Solutions des exercices
0.39.1) Pour un code auto-orthogonal, le produit x ∗ y est pair et donc, pour le calcul du poids de la somme,
2w(x ∗ y) ≡ 0 (mod 4) ce qui donne le résultat.
2) Sur F3 , on a 12 = (−1)2 = 1. De plus, si le code est auto-orthogonal, alors x.x = 0, ce qui implique que le
nombre de coordonnées non nulles est un multiple de 3.
0.40.On peut faire la table des syndromes, sinon cela vient directement du théorème 1.26.
0.41.Puisque l’on choisit les colonnes à une constante non nulle près, le nombre de colonnes (la longueur du
code) est (qm − 1)/(q − 1). Le nombre de lignes dans le dual est toujours m. Maintenant, deux colonnes du
dual ainsi construit sont toujours indépendantes par construction et donc la distance minimale est plus grande
que 3 (et exactement 3 en exhibant une relation entre 3 colonnes).
0.42.On montre d’abord, comme pour le cas binaire, que le code associé à la matrice est un code autodual sur
F3 et que tout mot de poids 6 s’écrit (a|b) mais que, par symétrie, on a aussi (b|a). Comme x.x = 0 pour tout
x du code, le poids de chaque mot est un multiple de 3. Pour montrer que le code a pour distance minimale 6,
il suffit donc de vérifier qu’il n’a pas de mots de poids 3.
0.43.Faire le calcul.
0.44.Les paramètres de tout code doivent vérifier la borne de Hamming. Ce n’est pas le cas pour un code avec
ces paramètres, donc il ne peut exister.
0.45.Dans le cas m impair, la symétrie des coefficients binomiaux assure que la dimension est exactement
m−1 m+1 √
2m /2. Pour ces codes, la distance vaut 2m− 2 = 2 2 qui est de l’ordre de 2m avec n = 2m pour ces
codes. Cette famille n’est donc pas asymptotiquement bonne. En fait, elle est même plutôt mauvaise si l’on
considère uniquement le critère de la distance, puisque la distance croît en racine carrée et non linéairement
par rapport à la longueur.
0.46.Dire que {0} fait partie de l’ensemble de définition signifie que, pour tout mot du code c(x), α0 = 1 est
solution donc c(1) = 0 pour tout c ∈ C. Cela signifie que c a un nombre pair de coordonnées non nulles.

0.47.À chaque fois, il y en a 23 . Il s’agit des codes de Golay quand la dimension correspond.
0.48.On trouve des codes [13, 10, 3]3 , [13, 7, 4]3 , [13, 4, 7]3 et [13, 1, 13]3 .
0.49.On recherche un tel code sous la forme d’un code BCH ternaire primitif au sens strict de longueur
n = 3m − 1. La taille des 3-classes cyclotomiques est un diviseur de m. Pour avoir une distance construite
supérieure à 3t + 1, il suffit d’avoir une séquence {1, 2, . . . , 3t} de 3t valeurs consécutives dans l’ensemble de
définition du code.
Considérons le code d’ensemble de définition T = C1 ∪ C2 ∪ ... ∪ C3t . Par construction, ce code a bien une
distance minimale d ≥ 3t+1. Dans le cas ternaire, Ci = C3i donc T s’écrit aussi simplement comme la réunion
des classes Ci pour 1 ≤ i ≤ 3t et i non divisible par 3. L’ensemble T peut donc s’écrire comme réunion de 2t
classes cyclotomiques, chacune ayant au plus m éléments. Le code obtenu a donc une dimension k supérieure
ou égale à n − 2tm et une distance minimale construite de 3t + 1.
Dans le cas q-aire, on obtient des codes [qm − 1, k ≥ qm − 1 − (q − 1)mt, d ≥ qt + 1]q . Cette construction
s’avère être particulièrement intéressante pour des alphabets de petite taille comme q = 2, q = 3 ou q = 4.
0.50.Pour le décodage, on peut suivre la méthode de Welch-Berlekamp. On peut connaître le nombre d’erreurs
en calculant le rang de la matrice des syndromes.
0.51.Le code est cyclique car si c(f) = (f(x1 ), f(x2 , · · · , f(xn )) = (f(α0 ), f(α), · · · , f(αn−1 )) est un mot du
code pour deg(f) < k, alors le mot décalé de une position c 0 = (f(αn−1 ), f(α0 ), f(α), · · · , f(αn−2 )) est aussi
un mot du code. En effet, on peut remarquer que c 0 = (f1 (α0 ), f1 (α), · · · , f1 (αn−1 )) pour f1 (x) = f(α−1 x)
car αn = 1. Comme f est de degré k, f1 est aussi de degré k et donc c 0 appartient au code, qui est donc
X
n−1
j i
cyclique. Maintenant, on peut remarquer que, pour tout 1 6 j 6 n − 1, la somme S = (α ) vérifie
i=0
S = 0 car αj S − S = (αj )n − 1 = 0 et 1 − αj 6= 0. Le code RSk est engendré par les vecteurs de la forme
el = (αl , (α2 )l , · · · , (αn−1 )l ) pour 0 6 l 6 k − 1. En utilisant le fait que la somme S est nulle pour
1 6 j 6 n − 1, on peut alors en déduire que, pour la matrice H définie par
αn−1
2 3
1 α ...
6 1 2 2(n−1)
α . . . α 7
H=6 7,
4 ... ... 5
1 αn−k ... α(n−k)(n−1)
le produit H.utl = 0 pour tout 0 6 l 6 k − 1. Cela montre que H est contenue dans le dual de RSk . De plus,
elle est de rang n − k car on peut en extraire une sous-matrice (n − k) × (n − k) inversible sous forme de

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 49 — #51

i

49

matrice de Vandermonde. C’est donc exactement une matrice du dual de RSk . En reprenant la démonstration
de la borne BCH, on en déduit que si c(x) = (c1 , · · · , cn ) est un mot du code, alors H.ct = 0 implique

Solutions des exercices

c(αi ) = 0 pour 1 6 i 6 n − k. Comme RSk a pour dimension k, cela montre que RSk est un code cyclique de
zéros α, α2 , · · · , αn−k et donc de polynôme générateur g(x) = (x − α)(x − α2 ) · · · (x − αn−k ).
0.52.Le sous-code sur le sous corps binaire de RSn−δ−1 est linéaire et cyclique puisque le code RSn−δ−1
est cyclique. D’après l’exercice précédent, ce code a dans l’ensemble de ses zéros α, α2 , ..., αδ−1 . Soit un
ensemble de définition T qui contient au moins {1, 2, ..., δ − 1}. Comme le code est binaire cyclique, l’ensemble
de définition contient aussi tous les éléments des 2-classes cyclotomiques modulo n associées aux éléments de
l’ensemble de définition, donc C1 ∪ ... ∪ Cδ−1 ⊂ T . Réciproquement, tout mot de code binaire ayant pour
zéros α, α2 , ..., αδ−1 (soit le code BCH binaire avec les mêmes zéros) est contenu dans le sous-code sur le
sous-corps. On peut donc en déduire que le sous-code sur le sous-corps de RSn−δ−1 est le code BCH binaire
au sens strict de distance construite δ.
n l
0.53.Si l = 1, le décodage en liste peut décoder jusqu’à τ < 2 − 2 (k − 1) erreurs, ce qui correspond au
cas du décodage classique, il n’y a pas d’amélioration. Si l = 2, alors, pour avoir τ > (n − k + 1)/2, il faut
2
3 n − k + 1 > (n − k + 1)/2, soit après simplification, k/n ≤ 1/3 + 1/n.

i i
 i i

“mathL3” — 2009/5/13 — 2:36 — page 50 — #52

i

Index
Code
code linéaire, 3
construction de Plotkin, 12
cyclique, 22
de Golay, 14
de Reed-Muller, 15
distance minimale, 7
dual d’un, 5
matrice génératrice, 4
mots de, 3
Syndrome, 9
Code correcteur, 3

Hamming
distance de, 6
borne de, 17
premier code de, 3

Reed-Solomon
code de, 32

Singleton
borne de, 18

i i