Université Mohammed V - Agdal

Faculté des Sciences

Laboratoire de Mathématiques, Informatique et Applications

Master spécialisé Codes, Cryptographie et sécurité de l'information

Théorie des codes

correcteurs d’erreurs I
El Mamoun SOUIDI

Année 2011

- - - - - - - -

- - - -

-
 Table des matières

Chapitre 1. Introduction à la théorie des codes 3

1.1. Introduction 3
1.2. Exemples de codes 3
1.3. Dénitions de codes 6
1.6. Capacité de détection et de correction d'un code 7
1.8. Bornes sur les codes 9
1.9. Codes Parfaits 10
1.10. Exercices 11

Chapitre 2. Codes linéaires 15

2.1. Dénition 15
2.2. Matrice génératrice 15
2.4. Code dual et matrice de contrôle 16
2.9. Distance minimale 18
2.12. Décodage 21
2.16. Rayon de couverture 24
2.17. Construction de codes 25
2.18. Exercices 26

Chapitre 3. Les codes linéaires parfaits 35

3.1. Les codes de Hamming 36
3.4. Unicité des codes de Hamming 39
3.5. Codes de Golay 39
3.8. Exercices 43

Chapitre 4. Codes de Reed-Muller 47

4.1. Dénition récursive 47
4.3. Matrice génératrice 47
4.4. Propriétés 48
4.5. Décodage de RM(1, m) 50
4.8. Fonctions booléennes 51
4.9. Exercices 52

Chapitre 5. Codes cycliques 53

5.1. Dénition 53
1
CHAPTER 0. TABLE DES MATIÈRES 2

5.2. Polynômes générateur et de contrôle 54

5.4. Décodage 58
5.6. Idempotents 62
5.7. Codes quasi-cycliques 62
5.8. Exercices 65

Bibliographie 71

Master C2SI - Théorie des codes I E. M. Souidi

 CHAPITRE 1

1
Introduction à la théorie des codes

1.1. Introduction
Cette théorie, initiée par Shannon en 1948 [5], traite la transmision
de messages au travers d'un canal bruité ainsi que la détection et si
possible la correction d'erreurs qui peuvent apparaître. Ce canal peut
être une ligne téléphonique, une transmission radio, télévision, satelli-
taire, un périphérique d'enregistrement, clé USB, CD-ROM, DVD etc.
Les erreurs peuvent être à cause des conditions climatiques, du matériel
de transmission ou autres.
Un code est une transformation qui convertit la représentation d'une
information en une autre pouvant être transmise à travers d'un canal
de communication. Le codage est l'écriture d'un message au moyen de
symboles d'un code. Le décodage est l'opération inverse, c'est à dire
retrouver le message clair à partir de ces symboles.
Des codes permettent de détecter et/ou corriger des erreurs. Le
principe est d'ajouter des redondances dans le message codé de telle
façon que les erreurs puissent être détectées et corrigées.

1.2. Exemples de codes

1.2.1. Exemple 1 ISNB. Chaque livre est identié par un nu-
méro appelé ISNB (International Standard Number Book) formé de
dix chires et parfois d'un x à la n. Le premier chire représente la
langue (0 pour l'anglais, 2 pour le français, 3 pour l'allemand ...), le
bloc suivant de chire l'éditeur (Springer-Verlag en Allemagne : 540,
aux États-Unis : 387, etc.), le suivant le numéro du livre chez l'éditeur.
Le dixième est choisi de la façon suivante pour détecter les erreurs. Si
x1 x2 · · · x10 est un ISBN, il doit vérier x1 + 2x2 + · · · + 10x10 ≡ 0 mod
11. Si x10 doit être égale à 10, on le note par x. P10
Si au lieu d'écrire xk on écrit xk + e par erreur alors i=1 ixi =
ke 6≡ 0 mod 11. On se rend compte alors qu'il y a erreur.

1. Pr. E. M. SOUIDI - [email protected] - Laboratoire de mathématiques, Infor-

matique et Applications - Cours Master CSI - 2011/12 - Version 0.8 (Brouillon).
3
CHAPTER 1. INTRODUCTION À LA THÉORIE DES CODES 4

Dans le cas de deux erreurs : la formule de vérication est

10
X
1.x1 +· · ·+i(xi +ei )+· · ·+j(xj +ej )+· · ·+10x10 = ixi +iei +jej = iei +jej mod 11
i=1

iei + jej peut être nul par exemple 1.3 + 8.1 = 0 mod 11 Il y a d'autre
possibilités.
P10
Si deux chires sont interverties alors i=1 ixi = (k 0 −k)(xk −xk0 ) 6≡
0. On se rend compte alors qu'il y a erreur aussi.
Supposons que la probabilité de saisir correctement un chire est
p = 0, 98. Alors la probabilité de saisir correctement un ISBN est p9 =
0, 833.
Si on utilise le dixième chire de correction la probabilité de saisir
correctement un ISBN est (éventuellement après détection) ≥ p10 +
10p9 (1 − p) = 0, 983.

1.2.2. Exemple 2. Nous avons à transmettre les réponses oui ou

non au travers d'un canal bruité.
1) Si on code oui par 1 et non par 0. C = {0, 1}. Après transmission
de 0 on peut recevoir 1 et 1 peut être reçu comme 0. Alors il n'y a aucun
moyen de vérier s'il y a erreur.
2) Si on code oui par 11 et non par 00. C = {00, 11} Après trans-
mission de 11, si on reçoit 11 on admet que c'est bon. Si on reçoit 01
ou 10 on constate qu'il y a erreur, car ces mots ne sont pas des mots
de C . 00 est peut probable de le recevoir.
Dorénavant nous supposons que la probabilité de recevoir 0 et 1 en
erreur est p (< 1/2) pour les deux symboles 0 et 1. La probabilité p
est appelée probabilité d'erreur, elle dépend du canal de transmission
et non du code.
3) Si on code oui par 111 et non par 000. C = {000, 111}. Après
transmission de 111, si on reçoit 111 on admet que c'est bon. Si on
reçoit 011, 110 ou 101 on constate qu'il y a erreur ce ne sont pas des
mots de C . 000 est peut probable de le recevoir. Dans ce cas ce code
peut détecter jusqu'à deux erreurs par mot. De plus il peut corriger s'il
y a une seule erreur par mot :
111, 110, 101, 011 sont décodé comme 111.
000, 001, 010, 100 sont décodé comme 000.
S'il y a plus d'une erreur on obtient un résultat faux, mais la pro-
babilité d'avoir plus d'une erreur est minime.
La probabilité de recevoir 111 en tant que 111 est (1 − p)3 , en tant
que 110, 101 ou 011 est (1 − p)2 p. La probabilité de recevoir 111 en
tant que 111, 110, 101 ou 011 est P (C) = (1 − p)3 + 3(1 − p)2 p =
(1 + 2p)(1 − p)2 . Il en est de même pour 000.
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 1. INTRODUCTION À LA THÉORIE DES CODES 5

La probabilité qu'un mot soit décodé faux est Perr (C) = 1 − P (C)
c'est une caractéristique de C et une fonction de p. Perr (C) = (3−2p)p2 .
Si p = 0, 1 (en pratique p est plus petit) on a Perr (C) = (3 −
0, 2)0, 01 = 0, 028 et P (C) = 0, 972.
Si p = 0, 01 on a Perr (C) = 0, 000298 et P (C) = 0, 999702.
Qu'en est-il si on prend C = {0000, 1111} ? Certes Perr (C) diminue
mais ce code est moins ecace : le coût et le temps de transmission
augmentent.
La probabilité d'erreur sur une ligne téléphonique est p = 10−7 , elle
peut attendre 10−4 . Cette contrainte est mise en place au niveau de la
couche 2, du modèle OSI : liaison de données.

1.2.3. Exemple 3. Le numéro de la sécurité sociale en France est

formé de 15 chires, 13 chires d'identication qu'on note K et deux
chires de redondance qu'on note C calculés de telle facon que K + C
soit un multiple de 97.

1.2.4. Code barre EAN. Le code EAN (European Article Num-

bering) est utilisé dans le commerce et l'industrie pour identier de
manière univoque des articles.
Le code EAN de 13 chires se décompose ainsi : Le premier chire
isolé à gauche indique le pays où a été codié l'article (3 pour la France,
4 pour l'Allemagne, 0 pour les USA . . . ) ; Les 5 chires suivants per-
mettent d'identier le fabricant (CNUF, Code national unié fournis-
seur) ; Les 6 chires suivants donne la référence du produit (CIF, Code
interne fournisseur) ; Le dernier chire à droite est la clé de contrôle.

Figure 1. Un code barre

Ce code est composé de 13 chires c12 c11 · · · c1 c0 . Les chires c12 c11 · · · c1
identie le produit et c0 est une redondance calculé de la façon suivante :
P6 P6
on pose a = i=1 c2i et b = i=1 c2i−1 d'où c0 = 10 − (a + 3b) mod 10.
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 1. INTRODUCTION À LA THÉORIE DES CODES 6

Ce code permet de détecter les erreurs mais ne les corrige pas.

1.2.5. Q-Code.

Figure 2. Un lecteur de QR-code ache http ://www.souidi.net

Le QR Code (Quick Response Code) développé par en 1994 by

Denso Wave pour l'industrie automobile au Japon, C'est un code à 2
dimensions qui permet de stocker des informations numériques (textes,
adresses de site web, etc.).

Définition 1.2.1. On appelle taux d'erreur la probabilité qu'un

bit transmi par le canal soit diérent du bit émis. C'est le rapport du
nombre de bits erronés sur le nombre de bit transmis.
1.3. Dénitions de codes
On appelle alphabet de transmission un ensemble A de q (> 1)
éléments qui peuvent être transmis au travers d'un canal de communi-
cation. Pour n > 1, on note les éléments de An , par v1 v2 · · · vn et on les
appelle mots ou vecteurs.

Définition Un code C de longueur n est une partie non vide

1.3.1.
de A . Ses éléments sont appelés mots du code.
n

Si q = 2 (q = 3), C est appelé code binaire (trinaire) respective-

ment. Un code C est trivial si |C| = 1 ou C = An .
Un tel code, est aussi appelé code par bloc puisque tous ses mots
sont de même longueur.
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 1. INTRODUCTION À LA THÉORIE DES CODES 7

Rappelons qu'une distance sur un espace X est une application

d : X → R+ vériant pour tout x, y et z de X :
i) d(x, y) = 0 ⇔ x = y
ii) d(x, y) = d(y, x)
iii) d(x, z) ≤ d(x, y) + d(y, z)

Définition 1.3.2. Soit x = x1 x2 · · · xn et y = y1 y2 · · · yn deux élé-

ments de A . La distance de Hamming entre x et y est dénie par
n

d(x, y) = |{i, / xi 6= yi }|.

Exercise 1.4. Dans A = {0, 1}3 on a d(110, 011) = 2.
Exercise 1.5. Vérier que la distance de Hamming est bien une
distance.
Définition 1.5.1. La distance minimale d'un code C , notée d(C)
est dénie par
d(C) = min {d(x, y) / x, y ∈ C, x 6= y}
Exemple Pour C = {000, 111} on a d(C) = 3 et Pour
1.5.2.
C = {0000, 1110, 0111} on a d(C) = 2.
d(C)
Le taux de correction d'un code C est dénie par n .
Le taux d'information ou rendement d'un code C est R = nk , c'est
le rapport de l'information utile sur l'information totale transmise à
travers le canal.

Définition Deux codes C1 et C2 dans An sont équivalents si

1.5.3.
C2 est obtenu de C1 en appliquant à tous les mots de C1 une permuta-
tion xe de coordonnées et à chaque coordonnées une permutation de
l'alphabet.
Définition Soit σ une permutation de {1, · · · , n} et x =
1.5.4.
(x1, · · · , xn) un mot de An ; on note : σ̄(x) = (xσ(1) , · · · , xσ(n) ) On
dénit ainsi une permutation de An . On dit que deux codes C et C 0
sont équivalents, ssi, il existe une une permutation σ de {1, · · · , n}
telle que : C 0 = σ̄(C).

1.6. Capacité de détection et de correction d'un code

Supposons qu'on transmet un mot x d'un code C et qu' on reçoit
y . Si y ∈ C , fort probablement y = x. Mais si y ∈ / C il y a une ou
plusieurs erreurs. Dans ce cas on décode y comme étant le mot x0 ∈ C
le plus proche de y .
Par [x] on note la partie entière du nombre réel x.
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 1. INTRODUCTION À LA THÉORIE DES CODES 8

Théorème 1.6.1. Soit C un code de distance minimale d et t =

[(d − 1)/2] alors :
i) C peut détecter jusqu'à d − 1 erreurs dans tout mot du code
transmis.
ii) C peut corriger jusqu'à t erreurs dans tout mot du code transmis.
Démonstration. Si un mot x est transmis et y 6= x est reçu alors
d(x, y) est le nombre d'erreurs apparus lors de la transmission.
i) Si le nombre d'erreurs est ≤ d − 1 alors d(x, y) < d d'où y ∈ /C
car d(C) = d. Donc au plus d − 1 erreurs sont détectées. Si d(x, y) ≥ d
alors y peut (ne pas) être un mot du code. Donc il est possible que plus
de d − 1 erreurs ne soient détectées.
ii) Supposons que le nombre d'erreurs est ≤ t. Alors d(x, y) ≤ t. x
est le mot unique tel que d(x, y) ≤ t. Soit x0 ∈ C tel que d(x0 , y) ≤ t
alors d(x, x0 ) ≤ d(x, y) + d(y, x0 ) ≤ 2t ≤ d − 1 d'où d(x, x0 ) < d donc
x = x0 . Donc y est décodé comme étant x. Mais s'il y a plus de t erreurs
alors un mot x0 (6= x) de C peut être plus proche de y , dans ce cas le
décodage est faux. 

Soit C un code de distance

 d−1  minimale d. Par [x] on note la partie
entière de x. L'entier t = 2 s'appelle capacité de correction du code
C.
t est le plus grand entier tel que les sphères Hamming de rayon t
centrées en des mots de C sont disjointes.

Remarque 1.6.2.Si un code est t-erreurs alors sa distance mini-

male est 2t + 1 ou 2t + 2.
Soit un code de longueur n, de distance minimale d et de cardinal
M sur un alphabet à q éléments est noté (n, M, d)-code.
Les propriétés d'un "bon code sont :
- petite longueur n (pour réduire le coût et la vitesse de transmis-
sion)
- M grand (pour pouvoir transmettre tout message)
- grande distance minimale (pour corriger plus de mots)
Ces propriétés sont liées entre elles. Par exemple pour n xe et M
grand, d est forcément petit.
Si on veut agrandir d, M se trouve réduit. Inversement, si on veut
agrandir M , d se trouve réduit.
Le problème principale de la théorie des codes est le suivant : pour
n et d donnés, trouver un code avec M le plus grand possible.
Soit Aq (n, d) la plus grande valeur possible de M tel qu'il existe un
(n, M, d)-code.
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 1. INTRODUCTION À LA THÉORIE DES CODES 9

Un tel code est appelé code optimal si M = Aq (n, d). Il est noté
(n, ∗, d)-code. Tout code optimal est nécessairement maximal. On cherche
une borne supérieure de Aq (n, d).

Exercise 1.7. Montrer que :

Aq (n, 1) = q et Aq (n, n) = q .
n

Si d est pair, alors A2 (n, d) = A2 (n − 1, d − 1).

1.8. Bornes sur les codes

Soit u ∈ An , un entier positif r ≤ n et Br (u) = {v ∈ An | d(u, v) ≤ r}
la boule de centre u et de rayon r . C'est l'ensemble des mots qui dif-
fèrent de x en au plus r positions.

Lemme Soit q le nombre d'éléments de A. Le nombre des

1.8.1.
éléments de Br (u) est
r  
X n
(1) Vq (n, r) = (q − 1)m
m=0
m

Démonstration. Soit u = u1 u2 · · · un et v = v1 v2 · · · vn ∈ An
pour m tel que 0 ≤ m ≤ r on considère {v ∈ An | d(u, v) = m} .
Il y a m indices
i tels que ui 6= vi . Les m composantes peuvent
n
être choisies de m façons. Pour chaque indice i, vi peut être choisi
de
(q − 1) façons. Donc le nombre de mots tels que d(u, v) = m est
n
m
(q − 1)m . Doù le lemme. 

D'après le Lemme 1 Vq (n, r) est indépendant du centre u de la boule

Br (u).
Remarque 1.8.2.Soit C ⊂ An un code de distance minimale d et
t = [(d − 1)/2]. Les boules de rayon t, dont les centres sont des mots de
C , sont disjointes deux à deux. En eet supposons qu'il existe un mot
v ∈ Bt (u) ∩ Bt (u0 ) où u, u0 ∈ C . Alors d(u, u0 ) ≤ d(u, v) + d(v, u0 ) ≤
2t < d absurde car d est la distance minimale. En particulier l'union
de toutes ces boules contient |C| . |Bt (u)| mots.
Théorème Soit q ≥ 2, n, d ∈ N∗ et t = [(d − 1)/2] alors le
1.8.3.
nombre Aq (n, d) de mots du code optimal vérie
qn qn
(2) ≤ Aq (n, d) ≤
Vq (n, d − 1) Vq (n, t)
La première inégalité dans 2 s'appelle borne de Gilbert-Varshamov
et la deuxième s'appelle borne de Hamming.
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 1. INTRODUCTION À LA THÉORIE DES CODES 10

Démonstration. Soit C un (n, M, d)-code optimal. C est alors

maximal. Tout mot de An est de distance ≤ d − 1 d'un certain mot de
C . En eet, (s'il existe un mot de An de distance > d − 1 d'un mot de
C , on peut ajouter ce mot à C , ce qui contredirait que C est maximal).
La réunion des boules de rayon d − 1 centrées en mots de C couvrent
An , d'où M.Vq (n, d − 1) ≥ q n ce qui donne la première inégalité.
D'autre part, on a 2t + 1 ≤ d. Les boules Bt (x) où x ∈ C sont
disjointes d'où M.Vq (n, t) ≥ q n ce qui donne la deuxième inégalité. 

Proposition 1.8.4 (Inégalité de Singleton).

(3) Aq (n, d) ≤ q n−d+1
Démonstration. Il est facile de voir que Aq (n, 1) = q n . Nous
montrons que pour tout n et d > 1 on a Aq (n, d) ≤ Aq (n−1, d−1). Soit
C un (n, M, d)-code sur l'alphabet A de cardinal q . Il existe c, c0 ∈ C tels
que d(c, c0 ) = d, alors il existe un indice i pour lequel les composantes
ci et c0i sont distinctes. A partir du code C on construit le code C 0 formé
de tous les éléments de C auxquels on a supprimé la ieme composante.
Le code C 0 est de longueur n − 1 et de distance minimale d − 1. Si on
considère le code C optimal, on a alors |C| = Aq (n, d) = |C 0 | ≤ Aq (n −
1, d − 1). D'où Aq (n, d) ≤ Aq (n − 1, d − 1) ≤ · · · ≤ Aq (n − d + 1, 1) =
q n−d+1 

1.9. Codes Parfaits

Un code est dit parfait s'il ne contient aucune redondance inutile.
Les codes parfaits sont utilisés dans la compression de données. Un
code parfait est idéal pour décoder. en eet, tout mot reçu appartient
à une et une seule boule de Hamming B(c, t) c ∈ C et t la capacité de
correction du code C . Donc on peut décoder tout mot reçu aecté d'au
plus t erreurs.

Définition 1.9.1. Soit C un (q, n, M, d)-code. Alors C est parfait

si
t  
X n
(4) M. (q − 1)m = q n
m=0
m
En particulier un (2, n, M, d)-code est parfait si M. = 2n .
Pt n


m=0 m

Dans un code parfait tout mot reçu peut être décodé. En eet
d'après l'équation 1.9.1 il découle que les boules centrées aux éléments
de C et de rayon t sont disjointes deux à deux et forment une partition
de An . Ainsi tout élément reçu y ∈ An est dans une certaine boule
Bx (t) où x ∈ C donc peut être décodé comme x.
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 1. INTRODUCTION À LA THÉORIE DES CODES 11

Dans un code parfait tout mot de An est à une distance ≤ t d'un

mot du code. Il s'en suit que la distance minimale d'un code parfait
doit être un nombre impair.
La distance minimale d'un code parfait est un entier impair. En eet
supposons d(C) = 2t + 2. Soit c ∈ C et y ∈ An tels que d(c, y) = t + 1.
(on peut facilement construire un tel mot y ). Il existe un c0 ∈ C tel
que y ∈ Bc0 (t) puisque C est un code parfait. D'où d(c, c0 ) ≤ d(c, y) +
d(c0 , y) ≤ t + 1 + t = 2t + 1 < d ce qui contredit que d est la distance
minimale de C .
Remarque 1.9.2. Dans le cas d'un code parfait les boules de rayon t
centrées aux éléments de C forment une partition de An . En particulier
tout mot reçu est décodable.
Proposition 1.9.3. Soit C ⊂ A un code de distance minimale
n

d(C) = 2t + 1. Si pour tout mot y ∈ An , il existe x ∈ C tel que

d(x, y) ≤ t alors C est un code parfait.
Démonstration. Les Bt (x) sont disjointes et M.Bt (u) = q n 
1.10. Exercices
Exercice 1. Pour chacun des QR-codes suivants apporter des mo-
dications progressivement et tester sa lecteur à l'aide d'un lecteur
QR-code de votre téléphone portable.

Exercice 2. Un code ISBN (International Standard Book Number )

comporte dix chires x1 x2 · · · x10 structurés en quatre segments A −
B − C − D séparés par un tiret. Les neuf premiers chires A − B − C
identient le livre : A identie la communauté linguistique, B l'éditeur
et C le numéro d'ouvrage chez l'éditeur. La clé de contrôle D = x10 est
un symbole de parité qui est, soit un chire entre 0 et 9, soit la lettre
P10
x qui représente 10. Cette clé x10 est telle que i=1 ixi ≡ 0 mod 11.
(1) Vérier que 0-387-54894-7 (Introduction to Coding Theory de
J. H. van Lint) est un code ISBN valide.
(2) Vérier que 2-84225-007-1 n'est pas un ISBN valide. Peut-on le
corriger ?
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 1. INTRODUCTION À LA THÉORIE DES CODES 12

(3) Montrer que l'on peut détecter un chire inexact, ou l'interver-

sion de deux chires dans un ISBN (en supposant qu'il n'y ait
qu'une seule erreur de ce type).

Exercice 3. Le code de sécurité sociale française est formé de 13

chires contenant les informations suivantes :
- Sexe 1 :Homme, 2 :Femme ;
- Année de naissance sur deux chires ;
- Mois de Naissance sur deux chires ;
- Département de naissance, 99 si étranger ;
- Code INSEE (Institut national de la statistique et des études
économiques) sur 3 chires de la commune ou du pays si étranger ;
- Numéro d'ordre INSEE de la personne sur 3 chires ;
en plus d'une clef de deux chires.
Si N est l'entier de 13 chires et c la clef, la contrainte de vérication
est la relation
N + c ≡ 0 mod 97
(1) Quelle est la clef d'un individu dont le numéro de sécurité sociale
serait 1-71-04-78-646-378 ?
(2) Un numéro de sécurité sociale est 2-xx-07-35-231-584, clé 19,
mais les caractères xx sont illisibles. Pouvez-vous retrouver l'an-
née de naissance de la personne en question ?
(3) Montrer que la clef de contrôle détecte une erreur sur un chire,
ainsi que l'interversion de deux chires consécutifs.
(4) Montrer que 97 est un nombre premier et que n = 96 est le plus
petit entier > 0 tel que 10n ≡ 1 mod 97.
(5) Montrer plus généralement que la clef de contrôle détecte l'in-
terversion de deux chires quelconques.

Exercice 4. 1) Construire un code binaire de 4 mots de longueur 3

et de distance minimale 2.
2) Montrer qu'un code binaire de longueur 3 et de distance minimale
2 possède au plus 4 mots.

Exercice 5. On considère le code binaire C = {00000, 01101, 10110,

11011} (2 bits + bit de parité +répétition des deux premiers bits )
1. Calculer d(C).
2. Quel est le nombre maximum d'erreurs par mot que ce code peut
détecter ? corriger ?
3. Faire la liste des mots binaires que ce code ne peut pas décoder.

Exercice 6. Montrer que A3 (10, 6) ≤ 120.

Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 1. INTRODUCTION À LA THÉORIE DES CODES 13

Exercice 7. Montrer que si C est un q − (3, M, 2)-code alors M ≤ q 2 .

Montrer que Aq (3, 2) = q 2 pour tout q ≥ 2. et qu'un q − (3, q 2 , 2)-code
existe.

Exercice 8. Montrer que A(2n, 2d) ≥ A(n, d).

Exercice 9. Calculer A(n, d) si n = d. Montrer que pour n impaire,

ces codes sont parfaits.

Exercice 10. Montrer que si n est un multiple de 3 et d = 2n/3, alors

A(n, d) = 4.
Exercice 11. Montrer que si d > 2n/3 alors A(n, d) = 2.

Exercice 12. Montrer

(1) Pour n ≥ 2, Aq (n, d) ≥ qAq (n − 1, d).
(2) Pour un code binaire A2 (n, 2t + 1) = A2 (n + 1, 2t + 2).
 d−1 
(3) La borne d'empilement des sphères : pour t = 2
on a Aq (n, d) ≤
n
q
Pt n


k=0 k (q − 1)k
q−1
(4) La borne de Plotkin : On pose θ = q
si d ≥ θn, alors Aq (n, d) ≤
d
d−θn
.
(5) Un code est parfait si l'égalité a lieu dans la formule d'empile-
ment des sphères.

Exercice 13. Montrer qu'un code triaire de longueur 3 et de distance

minimale 2 ne peut avoir plus de 9 mots. Montrer qu'un (3, 9, 2)-code
triaire existe.

Exercice 14. Soit C un code de distance minimale 2t+2. Si un mot v

est à la distance t + 1 d'un mot de C , montrer que v est à une distance
> t de tout mot de C .
Exercice 15. Soit C un code binaire de longueur 16 tel que :
i) tout mot du code est de poids 6 ;
ii) la distance entre deux mots quelconques du code est 8.
Montrer que |C| ≤ 16. Existe-t-il un tel code avec |C| = 16 ?

Exercice 16. Montrer que si il existe un (n, M, d)-code binaire alors

il existe un (n − 1, M 0 , d)-code binaire avec M 0 ≥ M
2
.

Exercice 17. Soit d un nombre entier impaire. Montrer qu'un (n, M, d)-
code binaire existe si et seulement si un (n + 1, M, d + 1)-code binaire
existe.
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 1. INTRODUCTION À LA THÉORIE DES CODES 14

Exercice 18. Montrer que si les codes suivants existent, alors ils sont
parfaits.
- le (4, 9, 3)-code triaire ;
r
- le (2r − 1, 22 −r−1 , 3)-code binaire où r ∈ N∗ ;
- le (23, 212 , 7)-code binaire ;
- le (11, 36 , 5)-code triaire.
- le (90, 278 , 5)-code binaire ;

Exercice 19. Montrer qu'un code C est parfait si pour tout x ∈ An

il existe un unique mot c ∈ C qui réalise le minimum de d(c, x).

Exercice 20. Montrer qu'il existe un (8, 4, 5) code binaire et qu'il est
optimal.

Exercice 21. Soit q = 2. Si x = (x1 , · · · , xn ) et y = (y1 , · · · , yn ) on

note x ∗ y = (x1 y1 , · · · , xn yn ). Montrer que ω(x + y) = ω(x) + ω(y) −
2ω(x ∗ y)
Exercice 22. Soit C un code binaire de longueur 5 et de distance 3
comportant le mot 00000.
1. Montrer que C comporte au plus 1 mot ayant au moins 4 sym-
boles 1.
2. Combien C peut-il comporter de mots ayant exactement 1 ou 2
symboles 1 ?
3. Montrer que C a au plus 2 mots comportant exactement 3 fois
le symbole 1.
4. En déduire que tout code de longueur 5 et de distance 3 a au
plus 4 mots.
5. Construire un code de longueur 5 et de distance 3 ayant 4 mots.
Ce code est-il unique ?

Exercice 23. Soit C = {00 · · · 0, 11 · · · 1} un code binaire de longueur

n impaire. C est parfait. Car tout y ∈ {0, 1}n est à une distance ≤ t =
(n − 1)/2 de 00 · · · 0 ou 11 · · · 1.
Exercice 24. Soit un code C de longueur n sur un alphabet A. On
appelle rayon de recouvrement du code C le plus petit rayon r tel
que l'ensemble des boules de rayon r centrées en chaque mot du code
forment un recouvrement de An . On le note ρ(C).
Montrer qu'un code C est parfait si et seulement si sa capacité de
correction est égal à son rayon de recouvrement.

Master C2SI - Théorie des codes I E. M. Souidi

 CHAPITRE 2

1
Codes linéaires

Dans ce chapitre on note par Fq ou Fq le corps ni à q éléments.

Rappelons que le cardinal d'un corps ni est une puissance d'un nombre
premier. Pour tout entier n, Fn est un F-espace vectoriel de dimension
n.

2.1. Dénition
Définition 2.1.1. Soit F un corps ni et n un entier > 0. Un
code linéaire de longueur n et de dimension k sur F est un sous es-
pace vectoriel de Fn de dimension k. Un tel code est noté [n, k]-code
ou [n, k, d]-code quand on veut spécier sa distance minimale. Si la
distance minimale d'un code est d alors ce code est noté
Exemple 2.1.2. C = {000, 111} est un [3, 1]-code linéaire sur le
corps Z2 .
Le code binaire C = {000, 111, 011} n'est pas linéaire car 111 +
011 = 100 qui n'est pas un mot du code.
Soit C un [n, k]-code linéaire sur un corps Fq . On a |C| = q k . En
eet puisque C est un espace vectoriel de dimension k , on sait que
C ' Fk . En particulier un [n, k]-code binaire a 2k mots.

2.2. Matrice génératrice

C'est une des deux matrices importantes associées à tout code li-
néaire.

Définition 2.2.1. Soit C un [n, k]-code linéaire. On appelle ma-

trice génératrice de C toute matrice k × n dont les lignes forment une
base de C .
Il est facile de voir qu'un [n, k]-code C linéaire sur F est complète-
ment déterminé par une matrice génératrice G de C . En plus
C = v.G | v ∈ Fk

(5)

1. Pr. E. M. SOUIDI - [email protected] - Laboratoire de mathématiques, Infor-

matique et Applications - Cours Master CSI - 2007/08 - Version 0.1 (Brouillon).
15
CHAPTER 2. CODES LINÉAIRES 16
 
1 0 1
Par exemple si G = est une matrice 2 × 3 alors
1 1 1
C = {00.G = 000, 01.G = 111, 10.G = 101, 11.G = 010}
.
La matrice G dénie une bijection de Fk → C par v 7→ vG et ainsi
on représente q k messages distincts par des mots du code C . Chaque
mot de longueur k est codé par un mot de C de longueur n. Le nombre
n − k est appelé redondance du code C .
Une matrice génératrice G d'un code C n'est pas unique. Puisque
les k colonnes de G sont linéairement indépendantes, en eectuant des
opérations élémentaires sur les lignes, G peut être transformée en G∗ =
.
 
I .. A où Ik est la matrice identité d'ordre k et A est une matrice
k
k × (n − k). Les lignes de G et G∗ engendrent le même sous espace C .
G∗ est appelée matrice génératrice canonique de C .
 Si un code linéaire C possède une matrice génératrice de la forme
..
Ik . A , on dit que le code C est systématique.
..
 
Soit C un [n, k]-code linéaire sur un corps F. Si G = Ik . A

est la matrice génératrice canonique de C . Alors C = v.G | v ∈ Fk
.
et v.G = v ..v.A on remarque que le codage ajoute n − k symboles de
redondance pour la détection d'erreurs par v.A.
 
1 1 0
Exercise 2.3. Soit G = une matrice génératrice d'un
1 0 1
code. Les mots de ce code sont 00.G = 000, 01.G = 101, 10.G = 110 ,
11.G = 011

2.4. Code dual et matrice de contrôle

Rappelons que si x = x1 . . . xn , y = y1 · · · yn ∈ Fn alors le produit
scalaire de x et y est x.y = x1 y1 + · · · + xn yn . Les vecteurs x et y sont
orthogonaux si x.y = 0.

Définition Soit C un [n, k]-code linéaire sur un corps F. Le

2.4.1.
code dual de C est déni comme C ⊥ = {y ∈ Fn | x.y = 0 pour tout x ∈ C}.
C ⊥ est aussi l'ensemble des solutions du système GX = 0 où G est
une matrice génératrice de C et X un vecteur inconnu, (car si c ∈ C ,
il existe v ∈ Fk tel que c = vG d'où cX = vGX = 0).

Remarque 2.4.2.
kerG = C ⊥
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 2. CODES LINÉAIRES 17

Si G est de rang k alors C ⊥ est un sous espace vectoriel de Fn de

dimension n − k .
Théorème 2.4.3. Soit C un [n, k]-code linéaire de matrice généra-
trice G. Alors :
1) C ⊥ =
Ker(G) 2) C ⊥ est un [n, n − k]-code linéaire.
3) C ⊥ ⊥ = C .
Démonstration. 1) Soit x ∈ Fn , Gx = 0 si et seulement si x est
orthogonal à chaque lignes de G. Or, les lignes de G forment une base
de C . Donc Gx = 0 si et seulement si x ∈ C ⊥
2) D'après le théorème du rang.
3) Soit x ∈ C , alors si x.y = 0 pour tout y ∈ C ⊥ on déduit que

⊥
x ∈ C ⊥ . Or si C est de dimension k alors C ⊥ est de dimension

⊥
⊥
n − k d'où dim C ⊥ = n − (n − k) = k . On a C ⊂ C ⊥ et sont de
même dimension donc sont égaux. 
Exercise 2.5. Trouver le code dual du code de répétition de lon-
gueur n : {0 · · · 0, 1 · · · 1}.
Définition 2.5.1. Un code C est auto-orthogonale si C ⊂ C .
⊥

Exercise 2.6. Le dual du [4, 1]-code binaire linéaire C = {0000, 1111}

est
C ⊥ = {0000, 1100, 1010, 1001, 0110, 0101, 0011, 1111}
qui est un [4, 3]-code et C ⊂ C ⊥ ie C est auto-orthogonal.
Définition 2.6.1. Soit C un [n, k]-code linéaire, une matrice gé-
nératrice du code dual C ⊥ est appelée matrice de contrôle ou matrice
de parité du code C .
La matrice génératrice d'un code C linéaire est la matrice de contrôle
du code C ⊥ .
Si H est une matrice de contrôle de C , on a x ∈ C ⇔ Hxt = 0
càd C = kerH ce qui veut dire que la matrice de contrôle détermine
complètement le code. D'où :
Théorème 2.6.2. Soit C un [n, k]-code linéaire sur un corps F de
matricegénératrice G et H une matrice de contrôle du code C . On a :
i) C = xG : x ∈ Fk = Im(G).
ii) C = {x ∈ Fn | x.H t = 0} = Ker(H).
iii) GH t = 0 et HGt = 0.
vi) Inversement, si G est une matrice k × n de rang k et H est une
matrice (n − k) × n de rang n − k, tel que GH t = 0. Alors H est
une matrice de contrôle de C si et seulement si G est une matrice
génératrice de C .
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 2. CODES LINÉAIRES 18

Démonstration. i) et ii) sont immédiats.

iii) D'après ii) où on prend en particulier Gi H t = 0 où les Gi sont
les lignes de G.
vi) Supposons que GH t = 0 et H est une matrice de contrôle.
Si on note par Gi les lignes de G alors Gi H t = 0 pour tout i d'où
Gi ∈ C . Puisque le rang de G est k , les Gi , i = 1 · · · k sont linéairement
indépendants, d'où ils forment une base de C donc G est une matrice
génératrice de C .
De même pour l'inverse. 
Exercise 2.7. Trouver le code
 linéaire et binaire C de matrice de
1 0 1 0 1
contrôle. H = 1 1 1 1 0
..
 
Corollaire 2.7.1. Soit C un [n, k]-code linéaire et G = Ik . A
.
.
 
une matrice génératrice canonique de C . Alors H = −A . In−k
t

est une matrice de contrôle de C . Inversement, si H = B ... In−k

 

est une matrice de contrôle de C alors G = Ik ... −B t est une

 

matrice génératrice de C .
Exercise 2.8. On considère le code binaire C = {000, 111}. Une
matice génératrice de C est G = (1, 1, 1). Le code dual de Cest C ⊥ = 
1 1 0
{000, 110, 101, 011} d'où la matrice de contrôle de C est H = .
1 0 1
Définition 2.8.1. Soit C et C 0 deux [n, k]-codes linéaires sur un
corps F. Les codes C et C 0 sont équivalents s'il existe une bijection
f : C → C 0 donnée par f (x1 , · · · , xn ) = α1 xσ(1) , · · · , αn xσ(n) où


α1 , · · · , αn ∈ F∗ et σ est une permutation de l'ensemble {1, · · · , n}.
Théorème 2.8.2. Soit C et C deux [n, k]-codes linéaires sur un
0

corps F de matrices génératrices G et G0 respectivement. Les codes C

et C 0 sont équivalents si l'une des matrices peut être obtenue de l'autre
en eectuant les opérations suivantes :
1) opérations élémentaires sur les lignes
2) permutation de colonnes,
3) multiplication d'une colonne par un scalaire non nul de F.
Preuve : en exercice.

2.9. Distance minimale

Définition 2.9.1. Le poids d'un mot x ∈ F noté ω(x) est déni
n

comme étant égale au nombre de composantes non nulles de x.

Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 2. CODES LINÉAIRES 19

Si x, y ∈ Fn alors d(x, y) = ω(x − y)

Théorème 2.9.2. Soit C un code linéaire, la distance minimale de

C est
d(C) = min {ω(x) | x ∈ C, x 6= 0} .

Démonstration. Soit d(C) = d. Il existe c, c0 ∈ C tel que d(c, c0 ) =

d. D'où c − c ∈ C et ω(c − c0 ) = d. Soit x ∈ C et x 6= 0 alors
0

ω(x) = ω(x − 0) = d(x, 0) ≥ d . Ce qui prouve que d est le plus petit

poids de tout mot 6= 0 de C .
Soit C un code à m éléments. La distance minimale de C est obte-
nue :
- si C est linéaire on cherche le minimum de m − 1 poids de mots ;
- sinon on cherche le minimum de m(m − 1)/2 distances entre les
diérents éléments de C .
Pour décrire un [n, k]−code linéaire il sut de donner une base de
C.


Théorème Soit H une matrice de contrôle d'un [n, k]-code

2.9.3.
linéaire sur un corps F. Alors d(C) est égale au nombre minimale de
colonnes de H linéairement dépendantes. Par conséquent d(C) ≤ n −
k + 1.

Démonstration. Soit X 1 , · · · , X n les colonnes de H et x ∈ Fn .

x ∈ C ⇔ Hx = x1 X 1 + · · · + xn X n = 0. Soit d(C) = d. Alors
t

ω(x) ≥ d et il existe un c ∈ C tel que ω(c) = d , on note par ci1 , · · · , cid

les composantes non nulles de c. Alors Hct = c1 X 1 + · · · + cn X n =
ci1 X i1 + · · · + cid X id = 0 c'est à dire que H a d vecteurs linéairement
dépendants. Supposons qu'il existe r(< d) vecteurs X i1 , · · · , X ir linéai-
rement dépendants. Alors il existe α1 , · · · , αr non tous nuls tels que
α1 X i1 + · · · + αr X ir = 0. Soit x ∈ Fn dont les composantes i1 , · · · , ir
soient égales à α1 , · · · , αr respectivement et toutes les autres nulles.
Hxt = 0 et x ∈ C mais ω(x) < d contradiction.
d est le nombre minimal de colonnes linéairement dépendantes de
H et c'est une matrice (n − k) × n de rang n − k d'où tous n − k + 1
colonnes de H sont linéairement dépendants donc d ≤ n − k + 1. 

Corollaire 2.9.4. Soit H une matrice de contrôle d'un [n, k]-code

linéaire. La distance minimale est d si et seulement si
i) d colonnes quelconques de H sont linéairement indépendants, et
ii) il existe d colonnes de H linéairement dépendants.

Master C2SI - Théorie des codes I E. M. Souidi

CHAPTER 2. CODES LINÉAIRES 20

Théorème 2.9.5 (Borne de Singleton). La distance minimale d

d'un [n, k]-code linéaire sur Fq est majorée par :
(6) d≤n−k+1
Démonstration. Soit E le sous-espace vectoriel de Fnq formé par
les vecteurs dont les k − 1 dernières composantes sont nulles. On a
dim(E) = n − k + 1 et dim(E) + dim(C) = n + 1 > n. Il existe un
x ∈ E ∪ C non nul. Puisque a ∈ E on a ω(a) ≤ n − k + 1 et puisque
a ∈ C on a d(C) ≤ ω(a) ≤ n − k + 1.
La Borne de Singleton impose à un [n, k]-code linéaire de distance
minimale d d'avoir au moins n − k ≥ d − 1 chires de redandances. 
Définition 2.9.6. Un [n, k]-code linéaire est dit MDS si il atteint
la Borne de Singleton 6 càd d = n − k + 1. MDS (maximum separable
distance) peut se traduire par : plus grande distance minimale.
Exercise 2.10. Quelle est la distance minimale du code binaire
C [n, n − 1]-code linéaire de matrice de contrôle H = 1 · · · 1 ?


Le nombre minimal de vecteurs colonnes linéairement dépendants est
deux, d'où d(C) = 2.
Quelle est la distance minimale du [10, 9]-code linéaire C sur le

corps F11 de matrice de contrôle H = 1 2 3 4 5 6 7 8 9 10 ?
On a d(C) = 2.
Ce code est utilisé dans le traitement des ISBN. Voir chapitre pré-
cédant.
Exercise 2.11.Quelle est la distance minimale du [10, 8]-code C 
1 1 1 1 1 1 1 1 1 1
sur le corps F11 de matrice de contrôle H = 1 2 3 4 5 6 7 8 9 10 ?
On remarque que deux colonnes quelquonques sont linéairement in-
dépendantes. D'où d > 2 et d ≤ n − k + 1 = 3 donc C est un code
correcteur d'une seule erreur.
Proposition 2.11.1 (Borne de Plotkin). Soit C un [n, k]-code li-
néaire sur Fq . Alors la distance minimale d de C vérie
n(q − 1)q k−1
(7) d≤
qk − 1
Démonstration. C contient q k − 1 vecteurs non nuls de poids
minimal d. D'où la somme de leur poids est d(q k − 1). Soit C1 le sous-
espace vectoriel de C dont la première composante de ses vecteurs est 0.
On a C/C1 ≡ Fq , d'où |C1 | = q k−1 . Donc il y a q k − q k−1 vecteurs dont
la première composante est non nulle. En tout il y a n composantes,
donc d(q k − 1) ≤ n(q k − q k−1 ). 
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 2. CODES LINÉAIRES 21

2.12. Décodage
Dans cette section nous traitons le décodage des codes linéraires.
Le principe générale de décodage est de trouver le mot du code le plus
proche du mot reçu. La structure algébrique de ces codes permet de
construire une table à cette n.

2.12.1. Décodage par table standard. Soit C un sous espace

vectoriel de Fn . En particulier C est un sous groupe de Fn . Pour x ∈ Fn
par dénition x + C = {x + c | c ∈ C}. x + C est appelé classe de x.
Deux éléments x et y de Fn sont dans la même classe si x − y ∈ C . Ces
classes forment une partition de Fn .

Théorème Soit C ⊂ Fn un code linéaire et y ∈ Fn . Le mot

2.12.1.
x du code C le plus proche de y est donné par x = y − e où e est le mot
de plus petit poids dans la classe de y.
Démonstration. Pour tout c ∈ C , d(y, x) ≤ d(y, c) ie ω(y − x) ≤
ω(y − c). D'où y − x est le vecteur de poids minimal dans la classe de
y. 
Définition Soit C un code linéaire dans Fn . Un représen-
2.12.2.
tant d'une classe de C est un vecteur de poids minimal de cette classe.
Soit C un [n, k]-code linéaire sur un corps Fq . Puisque Fnq = q n
et chaque classe de C a q k éléments alors il y a N = q n−k classes dans
C . Soit e1 , · · · , eN leurs représentants. Supposons que ω(ei ) ≤ ω(ei+1 )
pour i = 1, · · · , N −1. Soit e1 = 0 le représentant de la classe C +0 = C .
Soit C = {c1 , · · · , cG } où G = q k et c1 = 0. On peut arranger les q k
vecteurs dans une table, appelée table standard, N × G où ei + cj est le
terme dans (i, j). Les termes de la ie ligne sont les éléments de ei + C ,
avec les ei en premier. La première ligne est formée des mots du code
C.
e1 = 0 = c1 c2 ··· cj ··· cG
e2 e 2 + c2 ··· e2 + cj ··· e 2 + cG
.. .. .. .. .. ..
. . . . . .
ei ei + c2 ··· e i + cj ··· ei + cG
.. .. .. .. .. ..
. . . . . .
eN eN + c2 · · · eN + cj · · · eN + cG
Pour décoder le mot reçu y ∈ Fn . On cherche sa position dans la table.
Si y est le terme (i, j) de la table alors y = ei + cj . Puisque ei est de
plus petit poids il s'en suit que le mot du code le plus proche de y est
x = y − ei = cj . Donc le mot reçu y et décodé comme le premier mot
de la colonne où apparait y .
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 2. CODES LINÉAIRES 22

Remarque 2.12.3. Les ei ne sont pas unique car si C = {0000, 1111}

alors la classe de 1100 est {1100, 0011} qui a deux mots de même poids.
Exercise 2.13. Ecrire
 le tableau standard
 du code binaire de ma-
1 0 1 0 1
trice génératrice G = 0 1 0 1 1 et décoder le mot reçu 01111.
Le code généré est C = {00000, 01011, 10101, 11110}. Il y a 23 = 8
classes. Il y a 8 lignes dans le tableau standard. La distance minimale
est 3 et t = 1. Les cinq mots de poids 1 produisent 5 classes. On choisit
2 mots de poids 2 qui ne sont pas apparus dans les lignes précédentes.
00000 10101 01011 11110
10000 00101 11011 01110
01000 11101 00011 10110
00100 10001 01111 11010
00010 10111 01001 11100
00001 10100 01010 11111
11000 01101 10011 00110
10010 00111 11001 01100
Pour décoder le vecteur 01111, on remarque qu'il est dans la 3e
ligne. Il est décodé comme 01011.
Pour n grand, cette méthode n'est pas convenable. On décrit une
autre méthode ci-dessous.

2.13.1. Décodage par syndrome.

Définition 2.13.1. Soit C un [n, k]-code linéaire sur un corps F de
matrice de contrôle H . Pour tout y ∈ Fn , le syndrome de y est dénie
par S(y) = yH t .
D'après 2.6.2 on sait que S(y) = 0 ⇔ y ∈ C . Soit y, y 0 ∈ Fn alors
S(y) = S(y 0 ) ⇔ (y − y 0 )H t = 0 ⇔ y − y 0 ∈ C . D'où deux mots ont
même syndrome si et seulement si ils sont dans la même classe de C . Il
y a une bijection entre les classes de C et les syndromes. On étabit une
table à deux colonnes, et sur chaque ligne un représentant d'une classe
et son syndrome. Pour décoder un mot y reçu, on calcule son syndrome
S(y) et on cherche le représentant e tel que S(y) = S(e). Alors y est
décodé comme x = y − e. Cette procédure est appelée décodage du
syndrome.

Exercise 2.14. Traitons l'exemple précédent à l'aide de cette pro-

cédure.
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 2. CODES LINÉAIRES 23
 
1 0 1 0 0
Une matrice de contrôle est H =  0 1 0 1 0 . On calcule
1 1 0 0 1
eH t pour tout représentant.
représentant syndrome
10000 101
01000 011
00100 100
00010 010
00001 001
11000 110
10010 111
S(y) = yG = 100. On utilisant le tableau, y peut être décodé comme
t

x = y − e = 01011.
2.14.1. Identités de MacWilliams. Soit C ⊂ Fn un code li-
néaire. La distribution de poids de C est le vecteur A(C) = (A0 , A1 , · · · , An )
où
Ai = |{c ∈ C | ω(c) = i}|
c'est à dire que la i me composante de A(C) est le nombre de mots de
e

C de poids i. On note que A0 = 1

La distribution de distance est B(C) = (B0 , B1 , · · · , Bn ) où
1
Bi = |{(c1 , c2 ) ∈ C × C | d(c1 , c2 ) = i}|
|C|
Bi est le nombre moyen de mots du code situé P à la distance i de C
Le polynôme-énumérateur est A(X) = i=0 nA i X n

Exemple 2.14.1. Pour C = Fq on Ai =

n
n


i
(q − 1)i
Remarque 2.14.2. Dans le cas de codes linéaires A(C) et B(C)
coïncident. En général non.
Théorème 2.14.3. Soit C un [n, k]-code linéaire sur Fq de polynôme
énumérateur A(X) = i=0 nAi X n . Le polynôme énumérateur du code
P
dual C ⊥ est  
1−z
(8) B(z) = q −k (1 + (q − 1)X)n A
1 + (q − 1)z
Exercise 2.15. Montrer que pour le code de Hamming binaire Hm
on :
i)  
n
iAi = − Ai−1 − (n − i + 2)Ai−2
i−1
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 2. CODES LINÉAIRES 24

ii) En déduire A0 (z) = (1 + z)n − A(z) − nzA(z) + z 2 A0 (z), A(0) = 1.

Théorème 2.15.1. Soit C un code linéaire de longueur n. On note
B = B(C ) alors
⊥ ⊥
n
1 X
Bj⊥ = Bj Pjn (i)
|C| i=0
où
j   
X
` i n−i
Pjn (i) = (−1)
`=0
` j−`
est le polynôme de Krawtchouk de degré j .
Démonstration. 

2.16. Rayon de couverture

Le rayon de couverture (Covering radius) est un paramètre fon-
damental des codes. Il caractérise la capacité maximale de correction
d'erreur. Les codes de petits rayons de couverture s'appliquent en com-
pression de données.

Définition 2.16.1. Soit C un code dans An , le rayon de couverture

est le plus petit entier ρ tel que pour tout x ∈ An il existe c ∈ C tel que
d(x, c) ≤ ρ c'est à dire
ρ = ρ(C) = maxn d(x, c) = maxn min d(x, c)
x∈A x∈A c∈C

Soit C un code. Le rayon de couverture de C noté ρ = ρ(C) est le

plus petit entier r tel que Fnq est égal à la réunion des sphères centrées
en mots de C et de rayon r . De façon équivalente
ρ(C) = maxx∈Fnq minc∈C d(x, c)
Bien évidemment t ≤ ρ(C) et d ≤ 2ρ + 1. Si t = ρ(C) le corps C est
parfait.
On a
ρ ≥ min{r : Vq (n, r).|C| ≥ q n }
Pr n


où Vq (n, r) = i=0 i
(q − 1)i est le volume de la sphère de Hamming.
Pour les codes linéaires nous avons :

Théorème 2.16.2. Soit C un code linéaire de matrice de contrôle

H . Alors
i) ρ(C) est le poids de l'orbite de C de plus grand poids ;
ii) ρ(C) est le plus petit nombre r tel que le syndrome de tout vecteur
de Fmq est une combinaison d'au plus r colonnes de H .
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 2. CODES LINÉAIRES 25

Le Rayon de couverture ρ du code C est aussi le plus petit entier

tel que l'union des sphères Hamming de rayon ρ centrées en des mots
de C est An .
Théorème 2.16.3. Soit C un [n, k]-code linéaire binaire de matrice
de contrôle H . ρ(C) est le plus petit entier positif tel que tout (n − k)-
uplet peut s'écrire comme somme d'au plus ρ colonnes de H .
Démonstration. Soit x ∈ Fn2 et s = Hxt . Si la somme des co-
lonnes i1 , i2 , · · · , it est égale à s, alors le vecteur obtenu en ajoutant 1
aux coordonnées i1 , i2 , · · · , it dans x appartient à C et inversement. Ce
qui montre que d(x, C) est le plus petit nombre de colonnes de H 
2.17. Construction de codes
La construction suivante introduite dans [1] s'appelle "Codes ma-
trice produit". Elle permet de construire de nouveaux codes.
Définition 2.17.1. Soit C1 , C2 , · · · , CM M codes linéaires de lon-
gueur n sur Fq et A = (aij ) une matrice M × N à coecients dans le
corps Fq . Le code matrice produit noté [C1 · · · CM ].A est l'ensemble de
tous les produits [c1 · · · cM ].A où ci ∈ Ci est un vecteur colonne n × 1
pour i = 1, · · · M .
Les mots du codes [C1 · · · Cm ].A sont les matrices n × N :
c11 a11 + · · · + c1M aM 1 · · · c11 a1N + · · · + c1M aM N
 
.. .. ..
c= . . . 
cn1 a11 + · · · + cnM aM 1 · · · cn1 a1N + · · · + cnM aM N
Le code [C1 · · · Cm ].A est un code de longueur n.N et c = (c1 , · · · , cnN )
PM
où ck = i=1 chi aij , h − 1 = (k − 1)modn et j = 1, · · · , N

Exemple 2.17.2. Pour les codes C1 et C2 et la matrice

 
1 1
A=
0 1
on obtient le code (u|u + v)
Exemple 2.17.3. Pour les codes C1 , C2 et C3 et la matrice
 
1 2 1
A= 1 1 0 
1 0 0
on obtient le code (u + v + w|2u + v)
Exemple 2.17.4. Si A est la matrice identité d'ordre M alors
[C1 · · · CM ].A est la somme direct des codes C1 , C2 , · · · , CM M
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 2. CODES LINÉAIRES 26

Si C1 , C2 , · · · , CM sont des codes linéaires de matrice génératrices

G1 , G2 , · · · , GM respectivement alors [C1 · · · CM ].A a pour matrice gé-
nératrice
G1 a11 ··· G1 a1N
 
.. .. ..
G= . . . 
GM aM 1 · · · GM aM N

2.18. Exercices
Exercice 1. Montrer qu'un code linéaire à 20 mots ne peut exister.

Exercice 2. Soit C le code formé de tous les vecteurs de poids pairs

de Fn2 . Montrer que C est un code linéaire.

Exercice 3. Montrer que dans un code linéaire binaire, soit tous les
mots sont de poids pairs ou exactement la moitié sont de poids pairs.

Exercice 4. Soit n un entier positif. Montrer qu'une condition néces-

saire pour qu'il existe un code linéaire binaire parfait 1-correcteur de
longueur n est que l'entier n soit de la forme n = 2r − 1, où r est un
entier positif.

Exercice 5. Soit C un code linéaire binaire.

1. Montrer que si C est de longueur 17 et de dimension 10, il ne corrige
pas plus d'une erreur.
2. Montrer que si C est de longueur 10 et de distance minimale 3, alors
|C| ≤ 64.
Exercice 6. Soit C et C 0 deux codes linéaires binaires de même lon-
gueur. On déni C + C 0 = {x + x0 /x ∈ C, x ∈ C 0 }. Montrer que C + C 0
est un code linéaire et (C + C 0 )⊥ = C ⊥ + C 0⊥ .

Exercice 7. Montrer si il existe un [n, M, d] code linéaire binaire avec

d paire alors il existe un [n, M, d] code linéaire binaire dont tous les
mots sont sont de poids paire.

Exercice 8. Soit F un corps ni, combien y a-t-il de mots de Fn de

poids i ?

Exercice 9. Donner la distance de Hamming entre les mots 101101100010

et 101101010010 :
i) lorsqu'on les voit dans F12
2
ii) lorsqu'on les voit dans F64 où F4 est représenté par : 0 → 00, 1 → 01,
α → 10, α + 1 → 11.
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 2. CODES LINÉAIRES 27

Exercice 10. Soit C1 et C2 deux codes linéaires dans Fn . Montrer que

C1 ∩ C2 et C1 + C2 = {x1 + x2 / x1 ∈ C1 , x2 ∈ C2 } sont des codes
linéaires.

Exercice 11. Montrer que le code C = {0000, 1010, 0101, 1111} est
linéaire et auto-orthogonal.

Exercice 12. Montrer que le code binaire linéaire C de matrice gé-

nératrice
 
1 0 0 0 1 1 1
M = 0 1 0 1 0 1 1 
0 0 1 1 1 0 1

est auto-orthogonal. Trouvez le code dual de C .

Exercice 13. Trouvez la matrice génératricecanonique du[4, 2]-code

0 1 1 1
ternaire linéaire de matrice de contrôle M = et expli-
1 0 1 2
citez les mots du code.

Exercice 14. On considère le code binaire C dont la matrice généra-

trice est :
 
1 0 0 1 0 0 1
M = 0 1 0 0 1 1 0 
0 0 1 0 1 0 1

1. Donner tous les mots de C.

2. Donner la distance minimale de C , combien d'erreurs peut-on corri-
ger ? Détecter ?

Exercice 15. On considère la matrice génératrice suivante d'un code

C,
 
1 0 0 1 0
 0 1 0 0 1 
0 0 1 1 1

1) Déterminer les mots du code, la distance minimale du code, un

tableau standard, la matrice de contrôle et la liste des syndromes de
C.
2) Corriger et décoder les messages suivants : 01101, 10000.
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 2. CODES LINÉAIRES 28

Exercice 16. On considère le code C dont une matrice génératrice

est  
1 1 0 0 1 0 1

 0 1 1 1 1 0 0 

G=
 0 1 0 1 0 1 1 

 0 0 0 1 1 0 0 
0 0 0 0 1 1 1
1) En utilisant la méthode de Gauss, mettez C sous forme systématique.
En déduire une matrice de contrôle H pour C .
2) Calculer le syndrome du mot 1111000. Pouvez-vous le décoder ?

Exercice 17. Soit C le code linéaire sur F5 de matrice génératrice

 
3 4 1 0
G=
0 3 4 1
1. Donner le nombre de mots de C .
2. Le code C est-il systématique ?
3. Déterminer une matrice de contrôle de C .
4. Calculer la capacité de correction t de C . Le code est-il MDS ?
5. Donner la table de contrôle contenant tous les vecteurs erreurs pos-
sibles de poids ≤ t.
6. Décoder quand c'est possible les mots 3001, 1101 et 2311.

Exercice 18. Soit C le code linéaire sur F3 de matrice génératrice

 
2 1 0 1 2
G=
0 2 1 1 1
1. Montrer que C est systématique et en donner une matrice généra-
trice normalisée G0 .
2. Encoder le message (12) avec G, puis avec G0 .
3. Construire une matrice de contrôle de C et calculer sa distance mi-
nimale. Le code est-il MDS (Maximum Distance Separable) ?
4. On reçoit le message 11102 codé par G. Quel est le message d'ori-
gine ? Le mot 12121 est-il un mot de code ? Le décoder sachant qu'il a
été encodé par G.

Exercice 19. Si C est un code linéaire de type (n, k, d), on dénit le

code étendu C comme le code formé des mots (x1 , · · · , xn+1 ) ∈ F2n tels
que (x1 , · · · , xn ) ∈ C et Σn+1
i=1 xi = 0. Quel est le type de C ?

Exercice 20. Soit un entier r ≥ 2 et Ham(2, r) le code de Hamming

binaire de longueur n = 2r − 1. Montrez que Ham(2, r) est unique,
dans le sens que tout code linéaire de paramètres [2r − 1, 2r − 1 − r, 3]
est équivalent à Ham(2, r).
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 2. CODES LINÉAIRES 29

Exercice 21. Montrez que les matrices M et M 0 sont des matrices

génératrices du même code si et seulement si M = P M 0 où P est une
matrice inversible.

Exercice 22. Soit C le code binaire linéaire de longueur 7 dont une

matrice de contrôle est


H= 10000111010010110010110100011110
1. Combien valent la dimension et la distance de C ? Écrire une matrice
génératrice de C .
2. Décoder les mots reçus r1 = 00001110 et r2 = 00010011, en suppo-
sant qu'il y a eu au plus une erreur de transmission.
3. Parmi les mots t1 =????0000, t2 =?0?0?0000 et t3 =?0?0?0?0 qui ont
subi des eacements, les autres bits ayant été transmis correctement,
lesquels peut-on décoder ?
4. Le code C est-il MDS ? Cyclique ? Parfait ?
5. Montrer que, pour tout mode de code m de C, le mot m + 11111111
appartient à C . En déduire le nombre de mots de C de poids 4.
6. Montrer que C est équivalent au code étendu du code de Hamming
Ham(8).
7. Montrer que C est son propre orthogonal.

Master C2SI - Théorie des codes I E. M. Souidi

CHAPTER 2. CODES LINÉAIRES 30

Exercice 23. On considère le code binaire où on envoie 16 bits pour

9 bits signicatifs de la manière suivante :
- on envoie les trois premiers bits p1 , p2 , p3 suivis d'un bit de parité
(paire) b1 ,
- on envoie les trois bits s1 , s2 , s3 suivants suivis d'un bit de parité
(paire) b2 ,
- on envoie les trois derniers bits d1 , d2 , d3 suivis d'un bit de parité
(paire) b3 ,
- on envoie un paquet de 4 bits de contrôle c1 , c2 , c3 , c4 où c1 =
p1 + s1 + d1 , c2 = p2 + s2 + d2 , c3 = p3 + s3 + d3 et c4 = b1 + b2 + b3 .
1. Montrer que ce code est linéaire, donnez sa matrice génératrice c'est
à dire la matrice dont les lignes sont formées des images des vecteurs
de base de F92 .
2. Coder le mot 100111000.
3. On suppose avoir reçu le mot 0110101101100011. Retrouvez le mot
envoyé.

Exercice 24. Trouvez le code dual du code binaire de répétition de

longueur n.

Exercice 25. Trouez les matrices canoniques

génératrice et de contrôle

1 1 1 0 1 1 0
du code binaire de matrice génératrice M =  1 0 1 1 1 0 1 
1 1 0 0 1 0 1
Exercice 26. On dit que deux codes linéaires de même longueur sont
équivalents si l'un s'obtient à partir de l'autre par une permutation
des coordonnées. Vérier que deux codes équivalents ont même type.
Montrer que tout code est équivalent à un code donné par un codage
systématique.

Exercice 27. On transmet des données par paquet de 16 bits, écrits

dans un tableau 4 x 4, en ajoutant une ligne et une colonne de contrôle
obtenue en associant à chaque ligne et chaque colonne son bit de parité.
a) Que pensez-vous des paquets reçus suivants :
     
1 1 0 1 1 1 1 1 0 1 0 0 1 0 1

 0 0 1 1 0 


 0 1 1 1 1 


 1 0 0 1 0 


 0 1 0 1 0 ,


 0 0 1 0 1 ,


 0 0 1 0 1 

 1 0 0 0 1   1 1 0 0 1   1 1 1 0 1 
0 0 1 1 0 1 0 1 1 0 1 1
b) Quels sont la longueur, la dimension et la distance du code décrit ?
c) Combien repère-t-il d'erreurs ? Combien en corrige-t-il ?
d) Si on ajoute en dernière position le bit de parité de la colonne
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 2. CODES LINÉAIRES 31

de contrôle, que deviennent la longueur, la dimension, la distance, le

nombre d'erreurs repérées, corrigées du code ?

Exercice 28. i) Quel lien existe entre la dimension et la longueur d'un

code 1-correcteur MDS ? i) Que peut-on dire des codes 1-correcteurs
MDS parfaits sur le corps ni Fq ?

Exercice 29. Soit C le code de Hamming binaire de longueur 7.

1. Déterminer une matrice génératrice normalisée de C à l'aide de la
méthode du pivot de Gauss. 2. En déduire une matrice de contrôle de
C.
3. Décoder quand c'est possible les mots 1111111, 1101011, 0110110 et
1111010.

Exercice 30. Soit C le code binaire linéaire de matrice génératrice

 
1 1 0 1 1 0
G= 1 1 0 0 0 1 
0 1 1 1 0 0

1. Le code est-il systématique ?

2. Déterminer une matrice de contrôle et la capacité de correction de
C.
3. Le code est-il MDS ?
4. Décoder si possible les mots 111110 et 111111.

Exercice 31. Soit un code de Hamming déni par la matrice de parité

4x6
 
1 0 0 0 1 h1,6
 1 1 0 0 0 h2,6 
H=
 1

0 1 0 0 h3,6 
0 1 1 1 0 h4,6
(a) Si l'on choisit h1,6 = h2,6 = h3,6 = h4,6 = 1, déterminer la liste
des mots code. Quel est le nombre de bits d'information et de parité ?
Combien d'erreurs ce code corrige-t-il ?
(b) Montrer que les variables h1,6 , h2,6 , h3,6 , h4,6 peuvent être choisies de
manière à ce que le code corrige les erreurs simples, mais aussi détecte
(sans corriger) les erreurs doubles. Déterminer la liste des mots code, et
montrer que la distance minimale du code est égale à 4. (Indication : Si
la distance minimale de Hamming vaut x alors tout ensemble de x − 1
colonnes de H doit être linéairement indépendant).

Exercice 32. Démontrer que la distance minimale d'un code de Ham-

ming est égale à d si et seulement si tous les mots code non nuls ont
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 2. CODES LINÉAIRES 32

au moins d bits égaux à 1, et au moins l'un d'entre eux a exactement

d bits égaux à 1.
Exercice 33. Générateur d'un code de Hamming. On appelle géné-
rateur d'un code binaire (n; k) une matrice k × n dont les lignes sont k
mots code linéairement indépendants. Chacun des 2k mots code peut
alors s'exprimer comme une combinaison linéaire des lignes de G.
(a) Déterminer la matrice de parité du code dont le générateur est
 
1 1 0 0 1 0
 0 0 1 1 0 1 
G1 = 
 0

1 0 1 1 1 
0 1 0 0 0 1
Quelles sont les propriétés de correction et/ou détection d'erreur de ce
code ?
(b) Même question pour le code de générateur


G2 = 1 1 0 0 1 0

Exercice 34. Montrer qu'un code de Hamming corrige jusqu'à t et

détecte (mais ne corrige pas nécessairement) jusqu'à t erreurs si et
seulement si tout ensemble de 2t − 1 colonnes de la matrice de parité
est constitué de colonnes linéairement indépendantes.

Exercice 35. a) Construire un code binaire de 4 mots de longueur 3

et de distance minimum 2.
b) Montrer qu'un code binaire de longueur 3 et de distance mini-
mum 2 possède au plus 4 mots.
c) Quelle est la distance maximale que peut avoir un code linéaire
binaire de 64 éléments de longueur 10 ?

Exercice 36. Soit C le code binaire comportant tous les mots de

longueur 11.
(1) Combien C comporte-t-il de mots ?
(2) Combien C peut-il détecter et corriger d'erreurs ?
On suppose que la transmission se fait à la vitesse de 106
bits par seconde, et que la probabilité qu'un bit soit modié par
le bruit est 10−7 .
(3) Calculer la probabilité qu'un mot soit modié par le bruit.
(4) Combien de mots erronés peut-on s'attendre à recevoir en 24
heures sans pouvoir les détecter ?
Soit C 0 le code binaire obtenu à partir de C en ajoutant à
chaque mot un bit de parité.
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 2. CODES LINÉAIRES 33

(5) Combien C 0 peut-il détecter et corriger d'erreurs ?

(6) Calculer la probabilité qu'au moins 2 erreurs aectent un même
mot.
(7) Combien de mots erronés peut-on s'attendre à recevoir en 24
heures sans pouvoir les détecter ?

Exercice 37. Soit C le code binaire linéaire de matrice génératrice

 
1 1 0 1 1 0
G= 1 1 0 0 0 1 
0 1 1 1 0 0
1. Déterminer une matrice de contrôle et la capacité de correction de
C.
3. Le code est-il MDS ?
4. Décoder si possible les mots 111110 et 111111.

Exercice 38. Soit C1 un [n, k1 , d1 ] code linéaire et C2 un [n, k2 , d2 ]

code linéaire sur le corps ni F. On construit le code C = {(y, x +
y) / x ∈ C1 , y ∈ C2 }.
1) Si G1 et G2 sont des matrices génératrices de C1 et C2 respective-
ment, montrer que C est un [2n, k1 + k2 ] code linéaire sur F de matrice
génératrice  
0 G1
G=
G2 G2
où 0 est la matrice nulle k1 × n.
2) Montrer que d(C) = min(d1 , 2d2 ).
3) On suppose d1 > 2d2 , montrer que tous les mots du code C de poids
minimaux sont de la forme (y, y) où y est de poids minimal dans C2 .

Exercice 39. Formuler et montrer la version appropriée de l'exercice

précédant dans le cas de codes non linéaires

Exercice 40. Soit C un [n, k, d]-code linéaire binaire auto-dual.

a) Montrer que le mot 1 · · · 1 est dans C .
b) Montrer que soit tous les mots de C sont de poids divisibles par 4 ;
ou exactement la moitié de mots de C sont de poids divisibles par 4
tandis que l'autre moitié sont de poids pairs non divisibles par 4.
c) Pour n = 6. Déterminer d.

Exercice 41.
Soit C un [n, k, d] code linéaire sur le corps Fq . On suppose que pour
tout 1 ≤ i ≤ n il existe au moins un mot de C dont la ieme composante
est non nulle.
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 2. CODES LINÉAIRES 34

i) Montrer que la somme des poids de tous les mots du code est
n(q − 1)q k−1 .
ii) Montrer que d ≤ n(q − 1)q k−1 /(q k − 1).
iii) Peut-on construire un [15, 7, d] code binaire linéaire avec d ≥ 8 ?

Exercice 42.
Soit C un code linéaire de distance minimale d, avec d est paire. Montrer
qu'une classe de C contient deux vecteurs de poids t + 1, où t est la
capacité de correction.

Master C2SI - Théorie des codes I E. M. Souidi

 CHAPITRE 3

Les codes linéaires parfaits

Les codes linéaires parfaits sont certains codes triviaux, les codes
de Hamming et deux codes de Golay.
Les codes de Hamming ont été inventés par Richard Hamming aux
Bell Labs, à la n des années 1940. A cette époque, quand les ordi-
nateurs rencontrèrent une erreur, ils s'arrêtaient. Les travaux de Ham-
ming ont porté sur la possibilité que les ordinateurs détectent, corrigent
des erreurs isolées et continuent à fonctionner. Sa solution a consisté
à grouper les informations en groupe de 4 bits et de calculer 3 bits de
contrôle. Ainsi le code de Hamming (7, 4, 3) a été né.
Ce code a été utilisé dans les années 1979-1981 pour la transmission
d'images couleurs de Jupiter et de Saturne vers la Terre par la sonde
américaine Voyager 1 et 2. C'est une généralisation de la construction
des codes de Hamming par Marcel Golay, n des années 1940.
Les codes de Hamming sont parfaits et de distance minimale 3. Y
en a-t-ils d'autres codes parfaits de distance minimale > 3 ? Il y en a
deux, qui ne sont pas de Hamming, ils ont été découvert par Golay.
Trois triplets vérient l'égalité dans la borne de Hamming, sans
être des codes de Hamming, sont (23, 212 , 7), (90, 278 , 5) pour q = 2
et (11, 36 , 5) pour q = 3. Le premier triplet déni le code linéaire bi-
naire [23, 12, 7], le troisième déni le code linéaire trinaire [11, 6, 5] qui
sont appelés code de Golay. On démontre qu'il n'existe pas de code
(90, 278 , 5).
En 1973, Tietävainen,
 a montré
 que tout code parfait non trivial
q r −1
sur Fnq est soit un q−1
, q n−r , 3 -code de Hamming, soit un (23, 212 , 7)-
code binaire de Golay, soit un (11; 36 ; 5)-code trinaire de Golay.
Nous construisons ici le (24, 212 , 8)-code de Golay étendu par une
matice génératrice et nous déduisons le (23, 212 , 7)-code de Golay en
réduisant la longueur du premier d'un seul bit. Il y a d'autres construc-
tions, voir [3, chap 4] pour les constructions de R. J. Turyn et J. H.
Conway.
Le minitel français (Figure 3 ) code ses données avec un code de
Hamming de paramètre (2r − r − 1, 2r − 1) = (120, 128) où r = 7, on
code 15 octet à l'aide d'un octet supplémentaire.

35
CHAPTER 3. LES CODES LINÉAIRES PARFAITS 36

Figure 1. Minitel français

3.1. Les codes de Hamming

Un code de Hamming permet de détecter et de corriger une erreur.
Comment construire des codes qui corrigent une erreur ?
Rappelons qu'un code C est de distance minimale d si et seule-
ment si, il existe d colonnes de sa matrice de contrôle linéairement
dépendantes, tandis que d − 1 colonnes quelconques sont linéairement
indépendantes.
On construit une matrice de contrôle H d'un code de Hamming de
façon est ce que deux colonnes quelconques ne soient pas linéairement
dépendantes : Si r est le nombre de lignes de H , ces colonnes appar-
tiennent à Frq , doivent alors être non nulles, et on doit en choisir au
plus une par droite de Frq . Le nombre maximum de colonnes est donc
(q r − 1)/(q − 1).
3.1.1. Dénition.
Définition 3.1.1. Soit le corps ni Fq , r un entier positif > 1 ,
n = (q − 1)/(q − 1) et M une matrice r × n dont les colonnes sont
r

des vecteurs non nuls de Frq tel que aucun n'est multiple de l'autre. Le
[n, n − r]-code de matrice de contrôle M est appelé code de Hamming
et noté par Ham(r, q).
L'ordre dont sont écrits les colonnes est sans importance, car toutes
ces matrices génèrent des codes équivalents. Donc pour un r donné il
y a (2r − 1)! codes équivalents.
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 3. LES CODES LINÉAIRES PARFAITS 37

Ham(r, q) est un code de longueur n = q r − 1 et de dimension

k = n − r = q r − 1 − r, c'est un [q r − 1, q r − 1 − r]-code. Le paramètre
r = n − k représente la partie redondante du code.
Exemple Pour r = 2, Ham(2, 2) est un [3, 1]-code de ma-
3.1.2
.
1 1 0
trice de contrôle 1 0 1 e2t de matrice génératrice 1 1 1 .

Donc Ham(2, 2) = {000, 111}.

Pour r = 3, Ham(3, 2) est un [7, 4]-code de matrice de contrôle
 
1 0 1 0 1 0 1
 0 1 1 0 0 1 1 
0 0 0 1 1 1 1
Le nombre minimal de vecteur linéairement dépendants est 3 d'où la
distance minimale de Ham(3, 2) est 3. La dimension du code est 4. Le
cardinal de ce code est 24 = 16.
Exercise 3.2. Montrer que les codes Ham(2, 2) et Ham(3, 2) sont
parfaits.
Exemple Pour r = 2 et q = p un nombre premier,
3.2.1.  une
0 1 1 1 ··· 1
matrice de contrôle de Ham(2, p) est 1 0 1 2 · · · p − 1 .

Théorème 3.2.2. Le code de Hamming Ham(r, q) est de distance

minimale 3 et il est parfait.
Preuve : Soit M une matrice de contrôle de Ham(r, q). Des colonnes
de M sont multiples de
1 0 1
   
 0  1  1 
 0 , 0 , 0 
   
 .  .  . 
 ..   ..   .. 
0 0 0
qui sont linéairement dépendants. Par le Théorème 2.9.3 Ham(r, q)
est de distance minimale 3. Ce qui implique que c'est un code correcteur
d'une seule erreur.
Pour montrer que ce code est parfait on utilise la dénition 1.9.1 .
On a |Ham(r, q)| = q n−r où n = (q r − 1)/(q − 1). De plus t = 1. D'où
t  
X n
M (q − 1)m = q n−r (1 + n(q − 1)) = q n
m=0
m
Donc Ham(r, q) est parfait.
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 3. LES CODES LINÉAIRES PARFAITS 38

Proposition Le code dual Ham(r, q)⊥ est un code simplexe,

3.2.3.
c'est-à-dire tous ses mots non nuls sont de même poids. La valeur com-
mune de leur poids est qr−1 .
Preuve en exercice.

3.2.1. Décodage des codes de Hamming. La procédure de dé-

codage des codes de Hamming est simple. On n'a pas besoin de calcu-
ler la table des syndromes et les représentants de classes. Car pour les
[q r − 1, q r − 1 − r, 3]-codes de Hamming les représentants de classes sont
les q r vecteurs de poids au plus 1. Soit Hr la matrice de contrôle dont
les colonnes sont les nombres 1, 2, · · · , 2r − 1 écrit en binaire et com-
pété de 0 au début (par exemple pour r = 3, 7 s'écrit (1,1,1), 3 s'écrit
(0,1,1), 2 s'écrit (0,1,0)). Puisque le syndrome du n-uplet de poids un
dont le seul 1 est dans la ie position esl r-tuplet représentant en bi-
naire le nombre i. L'algorithme de décodage par syndrome des codes
de Hamming est :
Soit y ∈ Fnq Pour trouver le mot x ∈ Ham(r, q) le plus proche de y ,
il sut de :
- calculer S(y) = Hy t .
- si S(y) = 0, alors y = x ∈ C .
- si S(y) 6= 0, on cherche l'indice i tel que S(y) = λci , où les ci sont les
colonnes de H car tous les vecteurs non nuls de Frq sont des colonnes
de H .
- Remplacer yi par yi − λ, et retourner x = y .
Preuve : Notons ei le mot dont les coordonnées sont toutes nulles
sauf la i-ème qui vaut 1. Clairement, on a
Hy t = H(λei )t = H(y − λri )t = Hy t − λHeti = 0
Donc x = y − λei ∈ H(r, q) et est à distance 1 de y .
Cet algorithme est facilement adaptable aux codes de Hamming sur
un corps quelconque Fq .

Exercise 3.3. Considérer le code de Hamming Ham(3, 2) et déco-

der le mot reçu y = 0000001
3.3.1. Codes de Hamming étendus. Un code étendu peut aug-
menter la capacité de correction ou de détection d'erreurs.

Définition 3.3.1. Soit un code de Hamming Ham(r, 2), on ajoute

à chaque mot du code Ham(r, 2) un 0 ou un 1 de manière à ce que le
poids de ce mot soit pair. On note Ham(r, 2)∗ le code ainsi obtenu.
Proposition 3.3.2. Le code Ham(r, 2) est un [2 , 2 − 1 − r]-code
∗ r r

linéaire de distance minimale 4.

Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 3. LES CODES LINÉAIRES PARFAITS 39

Preuve : Soient c∗1 , c∗2 ∈ Ham(r, 2)∗ tel que c1 et c2 sont les mots du
code correspondant dans Ham(r). c∗1 + c∗2 et c1 + c2 ont les 2r − 1 pre-
mières composantes identiques. Clairement Ham(r, 2)∗ est un espace
vectoriel. Puisque Ham(r, 2)∗ et Ham(r, 2) ont même nombre d'élé-
ments, donc même dimension. D'où Ham(r, 2)∗ est un [2r , 2r − 1 − r]-
code linéaire.

3.4. Unicité des codes de Hamming

Théorème 3.4.1. 1) Ils existent des codes sur Fq parfaits corrigeant
une et une seule erreur qui sont non linéaires et tous ces codes ront
même paramètres que les codes de Hamming : de longueur n = qq−1 −1
,
nombres de mots q et de distance minimale 3.
n−r

2) Tout code linéaire parfait sur Fq corrigeant une et une seule

erreur est un code de Hamming.

3.5. Codes de Golay

3.5.1. Code de Golay étendu.  
M1 I t
3.5.1.1. Dénition. Soit M la matrice 12 × 12 : M =
I 0
où I = (1 · · · 1) et M1 est la matrice dont la première ligne est (11011100010)
et les autres sont les permutations circulaires de cette ligne. M est sy-
métrique et s'écrit :

 
1 1 0 1 1 1 0 0 0 1 0 1
 1 0 1 1 1 0 0 0 1 0 1 1 
0 1 1 1 0 0 0 1 0 1 1 1
 
 
1 1 1 0 0 0 1 0 1 1 0 1
 
 
1 1 0 0 0 1 0 1 1 0 1 1
 
 
1 0 0 0 1 0 1 1 0 1 1 1
 
M =
 
0 0 0 1 0 1 1 0 1 1 1 1

 

 0 0 1 0 1 1 0 1 1 1 0 1 


 0 1 0 1 1 0 1 1 1 0 0 1 


 1 0 1 1 0 1 1 1 0 0 0 1 

 0 1 1 0 1 1 1 0 0 0 1 1 
1 1 1 1 1 1 1 1 1 1 1 0
Définition 3.5.1
 . Le 
code de Golay étendu est déni par la matrice
..
génératrice G = Id12 .M et est noté G24 .

Master C2SI - Théorie des codes I E. M. Souidi

CHAPTER 3. LES CODES LINÉAIRES PARFAITS 40

3.5.1.2. Propriétés du code de Golay étendu. 1) Le code G24 est de

longueur 24, de dimension 12 et formé de 212 = 4096 mots.
M t


2) Une matrice de contrôle de G24 est la matrice 24 × 12 : Id12
.
3) Une matrice génératrice de G24 est la matrice 12 × 24 : (M ..Id12 )
4) Le code G24 est auto-dual
5) la distance minimale de G24 est 8.
6) Le code G24 corrige jusqu'à 3 erreurs.
Preuve : Les propriétés 1, 2 et 3 sont videntes.
. .
4) G = (Id ..M ) et H t = (M t ..Id ) or M = M t car elle est symé-
12 12
trique. D'où G24 est auto-dual.
5) Cette démonstration se fait en trois étapes :
i) Tout mot de G24 est de poids divisible par 4, en eet : les lignes
de G = (Id12 , M ) sont toutes de poids 8 ou 12. Soit un mot c ∈ G24 .
Supposons que c est somme de deux lignes ri + rj . Les lignes de M
sont orthogonales d'où les lignes de G sont aussi orthogonales. D'où `i
et `j ont un nombre paire de 1 en commun. Disons 2x. D'où ω(c) =
ω(`i ) + ω(`j ) − 2(2x) est un multiple de 4.
Supposons maintenant que c est somme de trois lignes `i + `j + `k .
Si on note m1 = `i + `j alors c1 .`k = 0 car G24 est auto-dual. D'où c1
et `1 ont un nombre paire de 1 en commun. Disons 2y . D'où ω(c) =
ω(c1 ) + ω(`k ) − 2(2y) est un multiple de 4. Ainsi on montre que tout
mot de G24 est de poids multiple de 4.
ii) Les 11 premières lignes de G sont des mots du code G24 de poids
8. Ainsi la distance minimale de G24 est soit 4 soit 8.
iii) Aucun mot de G24 n'est de poids 4. Le code G24 est auto-dual.
t ..
(M .Id ) est aussi une matrice génératrice de ce code. Si (a, b) ∈ G
12 24
alors il en est de même pour (b, a) où a, b ∈ F122 . Supposons que (a, b)
est de poids 4 et ω(a) ≤ ω(b).
Si ω(a) = 0 alors a = 0 et donc b = 0 aussi, ce qui est impossible.
Si ω(a) = 1 alors (a, b) est une ligne de G24 , ce qui est impossible. Si
ω(a) = 2 alors (a, b) est une somme de 2 lignes de G. Mais en faisant la
somme de 2 lignes quelconques, on ne trouve aucune somme de poids
4.
Théorème 3.5.2. Si C est un code binaire de longueur 24, |C| =
212 , de distance minimale 8 et 0 ∈ C , alors C est équivalent à G24 .
Preuve voir [3, Chap 4].

3.5.2. Code de Golay.

Lemme 3.5.3. Si un q − (n, M, d)-code existe, alors il existe un
q − (n − 1, M, d − 1)-code.
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 3. LES CODES LINÉAIRES PARFAITS 41

Preuve : Soient x et y deux mots du q − (n, M, d)-code tels que

d(x, y) = d on choisit une composante de x et y où ils dièrent et on
supprime cette composante de tous les mots de ce code. Le résultat est
un q − (n − 1, M, d − 1)-code.

Théorème Soit d un nombre pair. Un (n, M, d)-code binaire

3.5.4.
existe si seulement si (n − 1, M, d − 1)-code binaire existe .
Preuve : ⇒) D'après le lemme.
⇐) Soit C un (n−1, M, d−1)-code binaire. Pour x ∈ C on note ω(x) le
poids de x. Soit C 0 le code obtenu en ajoutant à x ∈ C , ω(x) mod 2.
Tous les mots de C 0 ainsi obtenus sont de poids pair. Or d(x, y) =
ω(x) + ω(y) − 2ω(x + y) doit être pair pour tout x, y ∈ C 0 d'où d(C 0 )
est pair et d − 1 ≤ d(C 0 ) ≤ d mais d − 1 est impair, d'où d(C 0 ) = d.
Donc C 0 est un (n, M, d)-code.

Remarque 3.5.5. Ayant construit le [24, 12, 8]-code de Golay étendu

G24 , on déduit d'après le théorème précédant le [23, 12, 7]-code de Golay
qui est parfait.
3.5.2.1. [11, 6, 5]-code de Golay trinaire. Matrice génératrice du [11, 6, 5]-
code de Golay trinaire et parfait :
1 0 0 0 0 0 1 1 1 1 1
 
 0 1 0 0 0 0 0 1 2 2 1 
0 0 1 0 0 0 1 0 1 2 2
 
G11 =
 
0 0 0 1 0 0 2 1 0 1 2

 
 0 0 0 0 1 0 2 2 1 0 1 
0 0 0 0 0 1 1 2 2 1 0
Exercise 3.6. Montrer que le [11, 6]-code linéaire trinaire de Golay
engendré par les 11 premières colonnes de la matrice G12 ci-dessous est
de distance minimale 5.
1 0 0 0 0 0 0 1 1 1 1 1
 
 0 1 0 0 0 0 1 0 1 2 2 1 
0 0 1 0 0 0 1 1 0 1 2 2
 
G12 =
 
0 0 0 1 0 0 1 2 1 0 1 2

 
 0 0 0 0 1 0 1 2 2 1 0 1 
0 0 0 0 0 1 1 1 2 2 1 0
Exercise Montrer que pour q = 2, le triplet (90, 278 , 5) vérie
3.7.
l'inégalité de Hamming.
Théorème 3.7.1. Il n'existe pas de code binaire de paramètres
(90, 278 , 5).
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 3. LES CODES LINÉAIRES PARFAITS 42

Preuve : Supposons qu'un tel code C existe, parfait et de distance

minimale 5. On peut supposer que 0 ∈ C . Soit Y l'ensemble des x ∈ F90
2
commençant par deux 1 et de poids 3. On a |Y | = 88. Puisque C est
parfait pour tout y ∈ Y il existe un unique x ∈ C tel que d(x, y) = 2.
on a
2 = d(C) − ω(y) ≤ ω(x) − ω(y) ≤ ω(x − y) ≤ 2
d'où ω(x) = 5 puisque ω(y) = 3 et d(x, y) = ω(x − y) = 2. Ce qui
veut dire que x doit avoir un 1 là où y en a. Soit X l'ensemble des
x ∈ C commençant par deux 1 et ω(x) = 5. On sait que pour tout
y ∈ Y il existe un unique x ∈ X tel que d(x, y) = 2. Dans {(x, y) ∈
X × Y |d(x, y) = 2} il y a |Y | = 88 éléments. Mais chaque x ∈ X
contient exactement trois 1 après les deux premières positions. D'où
pour chaque x ∈ X il y a trois vecteurs y ∈ Y tel que d(x, y) = 2. D'où
3|X| = 88 ce qui est impossible car |X| est un entier.

3.7.1. Unicité des codes de Golay.

Théorème 3.7.2 (Tietavainen et Van Lint, 1971.). Tout code par-
fait C corrigeant jusqu'à t-erreurs, de longueur n sur Fq satisfait une
des condition suivantes :
1) |C| = 1, t = n ;
2) |C| = qn , t = 0 ;
3) |C| = 2, q = 2, n = 2t + 1 ;
4) |C| = 36 , q = 3, t = 2, n = 11 ;
5) |C| = 212 , q = 2, t = 3, n = 23 ;
6) |C| = qn−r , t = 1, n = (qr − 1)/(q − 1), pour tout r > 1.
Dans ce théorème on ne fait aucune hypothèse de linéarité. Les
codes de 1) et 2) sont parfaits et triviaux. Le code 3) est un code
de répitition. 4) et 5) sont les codes de Golay. 6) sont les codes de
Hamming.
Best et Hong ont montré que ce théorème est valable pour tout
alphabet ni, et non seulement pour Fq , si t ≥ 3.

Corollaire 3.7.3. 1) Tout code non-trivial, parfait, corrigeant

plusieurs erreurs a même longueur, même nombre de mots et même
distance minimale que le [23, 12, 7]-code binaire ou le [11, 6, 5]-code
trinaire de Golay.
2)Tout code binaire (respectivement, trinaire) linéaire ou non ayant
2 (respectivement, 36 ) mots, contenant 0, de longueur 23 (respecti-
12

vely, 11) et de distance minimale 7 (respectivement, 5) est équivalent

au [23, 12, 7]-code binaire (respectivement, [11, 6, 5]-code trinaire) de
Golay.
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 3. LES CODES LINÉAIRES PARFAITS 43

3.7.2. Décodage. On cherche à corriger des erreurs de poids ≤ 3.

On note e = (e1 , e2 ) où ei est de longueur 12. Puisque ω(e) ≤
3 on
Id
a soit ω(e1 ) ≤ 1 ou ω(e2 ) ≤ 1. Soit y = x + e et H = M on a
t

s1 = yH t = (e1 , e2 )H t = e1 + e2 M .
Si ω(e2 ) ≤ 1 alors s1 est un mot de poids ≤ 3 si ω(e2 ) = 0 sinon
c'est une ligne de G dont au plus 2 bits
ont été changés.
M
De même si ω(e1 ) ≤ 1, s2 = y I = e1 M + e2 .
Dans tous les cas si ω(e) ≤ 3 on a s1 = e1 + e2 M = yH t et
s2 = e1 G + e2 = (e1 + e2 G)G = s1 G.
Algorithme :
1) calculer s = yH t ;
2) si ω(e) ≤ 3, e = (s, 0) ;
3) si ω(s + bi ) ≤ 2 pour une ligne bi de M , alors e = (s + bi , ei ) ;
4) calculer sM ;
5) si ω(sM ) ≤ 3 alors = (0, sG) ;
6) si ω(sG + bi ) ≤ 2 pour une ligne bi de G, alors e = (ei , sM + bi ) où
ei = (0, · · · , 1, 0, · · · , 0) ;
7) si e est non déterminé, demander rediusion.
Cet algorithme nécessite au plus 26 calculs de poids pour décoder.
Exemple 3.7.4.Le code de Gloay (23, 12, 7) est cyclique de po-
lynôme générateur g1 (x) = 1 + x2 + x4 + x5 + x6 + x10 + x11 ou
g2 (x) = 1 + x + x5 + x6 + x7 + x9 + x11 . Les polynômes g1 (x) et g2 (x)
sont des facteurs de x23 + 1 en fait : x23 + 1 = (1 + x)g1 (x)g2 (x).
Le code de Gloay (11, 6, 5) est cyclique de polynôme générateur
g(x) = x5 + x4 − x3 + x2 − 1 et si h(x) = x6 − x5 − x4 − x3 + x2 + 1
alors x11 − 1 = g(x)h(x)
2 0 1 2 1 1 0 0 0 0 0
 
 0 2 0 1 2 1 1 0 0 0 0 
0 0 2 0 1 2 1 1 0 0 0
 
G=
 
0 0 0 2 0 1 2 1 1 0 0

 
 0 0 0 0 2 0 1 2 1 1 0 
0 0 0 0 0 2 0 1 2 1 1
3.8. Exercices
Exercice 1. Montrer l'Inégalité de Singleton suivante :
Aq (n, d) ≤ q n−d+1

Exercice 2. Soit C un code linéaire binaire. Montrer que tous les

mots de C sont de poids paire ou exactement la moitié d'entre eux
sont de poids paire.
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 3. LES CODES LINÉAIRES PARFAITS 44

Exercice 3. On transmet des données par paquet de 16 bits, écrits

dans un tableau 4 x 4, en ajoutant une ligne et une colonne de contrôle
obtenue en associant à chaque ligne et chaque colonne son bit de parité.
a) Que pensez-vous des paquets reçus suivants :

     
1 1 0 1 1 1 1 1 0 1 0 0 1 0 1

 0 0 1 1 0 


 0 1 1 1 1 


 1 0 0 1 0 


 0 1 0 1 0 ,


 0 0 1 0 1 ,


 0 0 1 0 1 

 1 0 0 0 1   1 1 0 0 1   1 1 1 0 1 
0 0 1 1 0 1 0 1 1 0 1 1

b) Quelles sont la longueur, la dimension et la distance du code décrit ?

c) Combien repère-t-il d'erreurs ? Combien en corrige-t-il ?
d) Si on ajoute en dernière position le bit de parité de la colonne
de contrôle, que deviennent la longueur, la dimension, la distance, le
nombre d'erreurs repérées, corrigées du code ?

Exercice 4. 1) Écrivez une matrice de contrôle et une matrice géné-

ratrice canaonique du code
- binaire de Hamming Ham(4, 2).
- trinaire de Hamming Ham(2, 3). Décoder y = 11000
- trinaire de Hamming Ham(3, 3).

Exercice 5. Écrivez la table de syndrome du code binaire de Ham-

ming Ham(3, 2). Décodez les mots suivants : 1001011, 1100110, 1111001.

Exercice 6. On appelle code MDS un code de paramètres (k, n, d)

avec d = n + 1 − k . Montrer que le code de Hamming de longueur 7
n'est pas MDS.

Exercice 7. Construire la matrice de contrôle de Ham(4, 2) dont les

colonnes sont les nombres binaires 1, 2, ..., 15 dans cet ordre. Dé-
coder les mots suivants et vérier que les mots obtenus sont bien
des mots du code Ham(4, 2). 001000001100100, 101001110101100 et
000100100011000.

Exercice 8. Montrer que pour tout entier r ≥ 2, on a A2 (2r − 1, 3) =

2r −1−r
2 .

Exercice 9. Montrer que les triplets (23; 212 ; 7), (90; 278 ; 5) pour q =
2, et (11; 36 ; 5) pour q = 3 satisfont l'égalité dans la borne de Hamming.
Exercice 10. Montrer qu'il n'existe pas de code binaire de paramètres
(90, 2 , 5).
78

Master C2SI - Théorie des codes I E. M. Souidi

CHAPTER 3. LES CODES LINÉAIRES PARFAITS 45

Exercice 11. Montrer que le [11, 6]-code triaire engendré par les 11
premières colonnes de la matrice G12 ci-dessous est de distance mini-
male 5.
1 0 0 0 0 0 0 1 1 1 1 1
 
 0 1 0 0 0 0 1 0 1 2 2 1 
0 0 1 0 0 0 1 1 0 1 2 2
 
G12 =
 
0 0 0 1 0 0 1 2 1 0 1 2

 
 0 0 0 0 1 0 1 2 2 1 0 1 
0 0 0 0 0 1 1 1 2 2 1 0

Exercice 12. Montrer qu'un [n, M, 7]-code binaire parfait vérie n =

7 ou n = 23.
Exercice 13. Montrer que la distance minimale d'un code parfait est
impaire.

Exercice 14. Montrer que le code binaire de répétition de longueur

n impaire est parfait. Combien d'erreurs corrige-t-il ?
Exercice 15. Le code de Hamming étendu de longueur 8 a pour ma-
trice de parité
 
1 0 0 0 0 1 1 1
 0 1 0 0 1 0 1 1 
H=
 0

0 1 0 1 1 0 1 
0 0 0 1 1 1 1 0
C'est un code de paramètres [8, 4, 4].
1. Combien d'eacements corrige-t-il correctement ?
2. Corrigez les eacements suivants :
00 ? ? ?011, ?01100 ? ?, ? ?100 ?01, ?1 ?0 ?001, 1111 ? ? ?1, 1 ?1 ?1 ?11

Exercice 16. Montrer que le code dual Ham(r, q)⊥ d'un code de
Hamming Ham(r, q) est un code simplexe, et la valeur commune des
poids (non nulle) est q r−1 .

Exercice 17. Montrer que le code de Hamming Ham(r, 2) est équi-

valent à un code cyclique.

Exercice 18. Soit C le [7, 4]-code de Hamming de polynôme généra-

teur g(x) = 1 + x + x3 . Décoder le mot reçu 0101111.

Exercice 19.
Soit C le [7, 4]-code binaire de Hamming. Décoder le mot reçu 0101110
si possible.
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 3. LES CODES LINÉAIRES PARFAITS 46

Exercice 20.
Montrer que le code dual Ham(r, q)⊥ est un code simplexe, c'est-à-dire
tous ses mots non nuls sont de même poids, et la valeur commune de
leur poids est q r−1 .

Master C2SI - Théorie des codes I E. M. Souidi

 CHAPITRE 4

Codes de Reed-Muller

Les codes de Reed-Muller ont été introduits séparément par I.S.

Reed et D.E. Muller en 1954. Ils forment une classe de codes généra-
lisant les codes de Hamming et ils sont dénis récursivement. Ils sont
utiles pour la transmission sur des canaux très bruités. De plus ils sont
faciles à implèmenter et à décoder. En particulier, RM(1, m) a une
distance minimale égale à la moitié de sa longueur. RM(1, 5) a été
utilisé entre 1969 et 1973 par le satellite Mariner 9 et Viking du NASA
pour la transmission d'images en noir et blanc de Mars vers la Terre.
Ce code a 26 = 64 mots de longueur 25 = 32, de distance minimale
24 = 16 et peut corriger jusqu'à 7 erreurs dans chaque mot transmi.
Chaque mot du code correspond à un niveau de gris, soit 64 niveaux.

4.1. Dénition récursive

Définition 4.1.1. Le code de Reed-Muler d'ordre r noté RM(r, m)
et de longueur 2m où 0 ≤ r ≤ m est :
RM(0, m) = {00 · · · 0, 11 · · · 1} chaque mot est de longueur 2m . RM(m, m) =
{0, 1}2 = F22 .
m m

et pour 0 < r < m : RM(r, m) = {(x, x + y) | x ∈ RM(r, m − 1), y ∈ RM(r − 1, m − 1)}

Exemple 4.1.2. RM(0, 0) = {0, 1}.
RM(0, 1) = {00, 11}.
RM(1, 1) = {0, 1}2 = {00, 01, 10, 11}.
RM(0, 2) = {0000, 1111}.
RM(2, 2) = {0, 1}4 .
RM(1, 2) = {(x, x + y) | x ∈ {00, 01, 10, 11} , y ∈ {00, 11}}
= {0000, 0101, 1001, 1010, 0110, 0011, 1100, 1111}
Exercise 4.2. Donnez les mots du code RM(1, 3).

4.3. Matrice génératrice

Proposition 4.3.1. G(r, m) est une matrice génératrice de RM(r, m)
où on pose
47
CHAPTER 4. CODES DE REED-MULLER 48

G(0, m) = (11 · · · 1), G(m, m) = G(m−1,m) et pour 0 < r < m on a

0···01
 
G(r, m − 1) G(r, m − 1)
G(r, m) =
0 G(r − 1, m − 1)

 Exemple
 4.3.2. G(0, 1) = (11), G(0, 2) = (11 · · · 1), G(1, 1) =
1 1
0 1
,
 
  1 1 1 1
G(1, 1) G(1, 1)
G(1, 2) = = 0 1 0 1 
0 G(0, 1)
0 0 1 1
 
  1 1 1 1
G(1, 2)  0 1 0 1 
G(2, 2) = = 
0 · · · 01  0 0 1 1 
0 0 0 1
 
  1 1 1 1 1 1 1 1
G(1, 2) G(1, 2)  0 1 0 1 0 1 0 1 
G(1, 3) = = 
0 G(0, 2)  0 0 1 1 0 0 1 1 
0 0 0 0 1 1 1 1

1 1 1 1 1 1 1 1
 
 0 1 0 1 0 1 0 1 
0 0 1 1 0 0 1 1
   
G(2, 2) G(2, 2)
 
G(2, 3) = = 0 0 0 1 0 0 0 1
 
0 G(1, 2)

0 0 0 0 1 1 1 1
 
 
 0 0 0 0 0 1 0 1 
0 0 0 0 0 0 1 1

4.4. Propriétés
Théorème 4.4.1. Le code de Reed-Muler RM(r, m) a les proprié-
tés suivantes :
1) il est de longueur 2m ;
2) RM(r − 1, m) ⊂ RM(r,
Pr mm)
pour r > 0 ;
3) de dimension k = i=0 i ;
4) de distance minimale 2m−r ;
5) son code dual est RM(m − r − 1, m) pour r < m.
6) RM(m − 2, m) est le [n, n − m − 1]-code de Hammimg étendu.
Preuve :
1) Par dénition des codes de Reed-Muller.
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 4. CODES DE REED-MULLER 49

2) Pour m = 1 on a RM(0, 1) = {00, 11} ⊂ RM(1, 1) = {0, 1}2 .

On démontre par récurrence sur m.
Supposons que pour 0 < r < m on a RM(r − 1, m − 1) ⊂
RM(r, m − 1).
RM(r − 1, m) = {(x, x + y) | x ∈ RM(r − 1, m − 1), y ∈ RM(r − 2, m − 1)}
⊂ {(x, x + y) | x ∈ RM(r, m − 1), y ∈ RM(r − 1, m − 1)}
= RM(r, m).
3) Par dénition de G(r, m), on a
dimRM(r, m) = dimRM(r, m − 1) + dimRM(r − 1, m − 1)
r   X r−1  
X m−1 m−1
= +
i=0
i i=0
i
  X r    
m−1 m−1 m−1
= + + .
0 i=1
i i − 1
m m


m
m−1

m−1

m−1

m


Or n−i = i , i = + et que = = 1, d'où
Pr m
i i−1 0 0
dim RM(r, m) = i=0 i .
4) On montre par récurrence sur m. Pour m = 1 on a RM(0, 1) =
{00, 11} de distance minimale 2 = 21−0 , et RM(1, 1) = {00, 01, 10, 11}
de distance minimale 1 = 21−1 . On suppose que la distance minimale
de RM(r, m − 1) = 2m−1−r pour 0 ≤ r ≤ m − 1 On sait que
RM(r, m) = {(x, x + y) | x ∈ RM(r, m − 1), y ∈ RM(r − 1, m − 1)}
et RM(r−1, m−1) ⊂ RM(r, m−1) d'après 2) càd x+y ∈ RM(r, m−
1) et par hypothèse de récurrence on a pour x 6= y , ω(x + y) ≥ 2m−1−r .
De plus ω(x) ≥ 2m−1−r . D'où ω(x, x+y) = ω(x+y)+ω(x) ≥ 2.2m−1−r =
2m−r . Si x = y , alors (x, x + y) = (y, 0) mais y ∈ RM(r − 1, m − 1).
Donc ω(y, 0) = ω(y) ≥ 2m−1−(r−1) = 2m−r .
5) Rappelons que
RM(r, m) = {(x, x + y) | x ∈ RM(r, m − 1), y ∈ RM(r − 1, m − 1)}

RM(m − r − 1, m) =
0 0 0 0 0
{(x , x + y ) | x ∈ RM(m − r − 1, m − 1), y ∈ RM(m − r − 2, m − 1)}
Par récurrence sur m. RM(0, 2) = {0000, 1111} et RM(1, 2) =
{0000, 0101, 1010, 1111, 0011, 0110, 1001, 1100} sont orthogonaux puisque
tous les vecteurs sont de poids paire.
Le dual de RM(r, m − 1) est RM(m − r − 2, m − 1) et le dual de
RM(r − 1, m − 1) est RM(m − r − 1, m − 1) d'où x.y 0 = 0 et x0 .y = 0.
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 4. CODES DE REED-MULLER 50

Or d'après 2) RM(r − 1, m − 1) ⊂ RM(r, m − 1) d'où y.y 0 = 0. Donc

(x, x + y).(x0 , x0 + y 0 ) = x.x0 + (x + y).(x0 + y 0 )

= 2x.x0 + x.y 0 + yx0 + y.y 0

ce qui veut dire que tout vecteur de RM(r, m) est orthogonal à tout
vecteur de RM(m − r − 1, m) De plus on a

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

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

dimRM(r, m) + dimRM(m − r − 1, m) = 2m .

Donc RM(m − r − 1, m) est le dual de RM(r, m).

4.5. Décodage de RM(1, m)

On présente un algorithme de décodage rapide des codes RM(1, m).
La dénition récursive de ce code suggère un décodage récursive aussi.
On commence par dénir le produit de Kronecher de deux  matrices
1 1
A = (aij ) et B par A × B = (aij B). Par exemple : si H =
1 −1
 
1 0
et I2 = alors
0 1
   
1 1 0 0 1 0 1 0
 1 −1 0 0   0 1 0 1 
I2 × H =   et H × I2 =  
 0 0 1 1   1 0 −1 0 
0 0 1 −1 0 1 0 −1
 
1 1
Définition 4.5.1. Soit H = . On déni i
Hm = I2m−i ×
1 −1
H × I2i−1 .

Exercise 4.6. Calculer H31 , H32 et H33 .

Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 4. CODES DE REED-MULLER 51

Algorithme de décodage. Soit G(1, m) une matrice génératrice de

RM(1, m). Soit y un mot reçu et x le mot du code le plus proche de
y.
1) soit ŷ le mot obtenu en remplaçant les 0 par des -1 dans y ,
2) on calcule y1 = ŷHm 1
et yi = yi−1 Hm
i
pour i = 2, 3, · · · , m,
3) trouver la position j de la plus grande composante en valeur absolue
de ym . (la première position est 0).
Soit B(j) ∈ Fm 2 la représentation binaire de j (les unités d'ordre
petit d'abord). Si la composante j de ym est positive alors x = (1, B(j)),
si elle est négative alors x = (0, B(j)).
Exercise 4.7. Pour m = 3 et y = 10101011 montrer que x = 1100.
4.8. Fonctions booléennes
4.8.1. Dénition.
Définition 4.8.1. Une fonction booléenne à m variables est une

2 −→ F2 .
fonction f : Fm
Notons par xi l'application qui à y ∈ Fm 2 associe sa i-eme compo-
sante yi . Les expressions xi + xj , xi xj , et de façon plus générale, toute
expression polynomiale en les xi , dénissent une fonction booléenne.
Remarquons que x2i = xi dans F2 , donc il est inutile d'introduireQ des ex-
posants plus grands que 1. Pour I ⊂ {1, · · · , m}, notons xI = i∈I xi .
Proposition 4.8.2. L'espace Fm des fonctions booléennes à m va-
riables est un F2 - espace vectoriel de dimension n = 2m . Toute fonction
booléenne f ∈ Fm a une écriture unique sous la forme
X X
f= aI x I = ai1 ,··· ,is xi1 · · · xis
I⊂{1,··· ,m} 1≤i1 <i2 <···<is ≤m

Le plus grand I pour lequel aI 6= 0 s'appellele degré de f .

1 si x = y
Preuve : Soit la fonction booléenne δy (x) = dénit
0 si x 6= y
sur Fm
2 . Les δy où y ∈ F2 forment une base de Fm qui est donc de
m

dimension 2 . D'autre part, on peut exprimer les fonctions δy algébri-

m

quement en fonction des xi :

m
Y
δy = (xi + yi + 1)
i=1
Donc les monômes 1 ·
· · xis engendrent bien l'espace F comme il y en
Pm xim
a exactement s=0 s = 2 ils forment une base de Fm .
m

Pour n = 2m , on considère la bijection de {0, · · · , n − 1} dans

F2 : k −→ 2m−1 k1 + 2m−2 k2 + · · · + 2km−1 + km (l'écriture binaire
m

Master C2SI - Théorie des codes I E. M. Souidi

CHAPTER 4. CODES DE REED-MULLER 52

de i). qu'on identie avec u = (k1 , k2 , · · · , km−1 , km ). Posons F2m =

2 est iden-
{α0 , α1 , · · · , α2m −1 }. Tout élément u = (u1 , · · · , u2m −1 ) ∈ Fm
tié à un élément αi de F2 (dans un ordre quelconque mais xe, par
m

exemple αi s'identie à l'écriture binaire de i) qu'on identie encore

avec la fonction booléenne f en m variables déni par u = (f (α0 ), · · · , f (α2m −1 )).

4.8.2. Codes de Reed-Muller.

Définition 4.8.3. Le code de Reed-Muller RM(r, m) est le code

2 associés aux fonctions boo-

binaire engendré par les éléments de Fm
léennes : xI telles que |I| ≤ r.
Autrement dit :

RM(r, m) = {(f (α0 ), · · · , f (α2m −1 )) : f ∈ Fm et deg(f ) ≤ r}

Le code RM(1, 3) est engendré par les lignes ci-dessous :
F32 : 000 100 010 110 001 101 011 111
1 1 1 1 1 1 1 1 1
x1 0 1 0 1 0 1 0 1
x2 0 0 1 1 0 0 1 1
x3 0 0 0 0 1 1 1 1
Le code RM(2, 3) est engendré par les lignes ci-dessous :
F32 : 000 100 010 110 001 101 011 111
1 1 1 1 1 1 1 1 1
x1 0 1 0 1 0 1 0 1
x2 0 0 1 1 0 0 1 1
x3 0 0 0 0 1 1 1 1
x1 x2 0 0 0 1 0 0 0 1
x1 x3 0 0 0 0 0 1 0 1
x2 x3 0 0 0 0 0 0 1 1
4.9. Exercices
Exercice 1. Montrer que pour r < m le code de Reed-Muler RM(r, m)
a pour code ducoloral RM(m − r − 1, m).

Exercice 2. Implémenter à l'aide de Python 3.x l'algorithme de dé-

codage des codes de Reed Muller.

Master C2SI - Théorie des codes I E. M. Souidi

 CHAPITRE 5

Codes cycliques

Les codes cycliques forment une classe de codes linéaires très impor-
tante, dont le codage et le décodage sont faciles à implémenter à l'aide
des registres à décalage à rétroaction linéaire. Leur étude a commencé
en 1957. Plusieurs des codes vus précédemment, codes de Hamming,
codes Golay, codes de Reed-Muller sont des codes cycliques ou des
codes cycliques étendus.

5.1. Dénition
Soit F un corps ni et n ∈ N∗ Par σ on note l'application linéaire
de Fn → Fn dénie par
σ(x1 , x2 , · · · , xn ) = (xn , x1 , x2 , · · · , xn−1 ).
Définition 5.1.1.Un code linéaire C ⊂ Fn est appelé code cyclique
si σ(x) ∈ C pour tout x ∈ C .
Exemple 5.1.2. C = {000, 110, 011, 101} est un code binaire cy-
clique.
Théorème 5.1.3. Soit G une matrice génératrice d'un code linéaire
C . Alors C est un code cyclique si et seulement si σ(Li ) ∈ C pour
chaque ligne Li de G .
Démonstration 1. Si C est cyclique alors σ(x) ∈ C pour tout
x ∈ C en particulier σ(Li ) ∈ C pour chaque ligne Li de G . Inversement,
supposons que σ(Li ) ∈ C pour chaque ligne L de G . Soit x ∈ C , x =
Pk i
où les d'où
Pk Pk
α L
i=1 i i α i ∈ F σ(x) = σ( i=1 αi Li ) = i=1 αi σ(Li ) ∈
C . Donc C est cyclique.
On considère p(x) un polynôme de l'anneau F[x], (p(x)) l'idéal en-
gendré par p(x) et l'anneau quotient
F[x]/p(x) = a0 + a1 t + · · · + an−1 tn−1 | a0 , a1 , · · · , an−1 ∈ F


où t est la classe x + (p(x)) , i.e. p(t) = 0.

Pour p(x) = xn −1. On note Fn = F[x]/(xn −1) c'est un anneau, où
le produit est obtenu en posant xn = 1, xn+1 = x etc, dans le produit
usuel de polynômes. L'addition est l'addition des polynômes usuelle
53
CHAPTER 5. CODES CYCLIQUES 54

notée +. Fn est aussi un F-espace vectoriel, il est isomorphe à l'espace

vectoriel Fn , en identiant tout polynôme a0 + a1 x + · · · + an−1 xn−1 de
Fn avec le vecteur (a0 , a1 , · · · , an−1 ) de Fn .
Soit C ⊂ Fn un code linéaire. Un élément de C peut être vu comme
mot a0 a1 · · · an−1 ou comme polynôme p(x) = a0 +a1 x+· · ·+an−1 xn−1 .
x.p(x) = an−1 + a0 x + · · · + an−2 xn−1 = an−1 a0 a1 · · · an−2
ce qui veur dire qu'un code C linéaire est cyclique si et seulement si
xp(x) ∈ C pour tout p(x) ∈ C .
Théorème 5.1.4. Une partie C ⊂ Fn est un code cyclique si et
seulement si C est un idéal de l'anneau Fn .
Démonstration 2. Soit C un code cyclique et p(x) , q(x) dans C .
Alors p(x) − q(x) ∈ C , λp(x) ∈ C et xp(x) ∈ C . D'où x2 p(x) ∈ C etc.
Donc pour tout r(x) = r0 + r1 x + · · · + rn−1 xn−1 ∈ Fn on a r(x).p(x) =
r0 p(x) + r1 xp(x) + · · · + rn−1 xn−1 p(x) ∈ C c'est à dire C est un idéal
dans Fn .
Inversement : Supposons que C soit un idéal et p(x), q(x) dans C et
λ ∈ F alors p(x) − q(x) ∈ C et λp(x) ∈ C donc C est un code linéaire.
De plus r(x)p(x) ∈ C pour tout r(x) ∈ C en particulier xp(x) ∈ C .
Donc C est cyclique.
5.2. Polynômes générateur et de contrôle
Théorème 5.2.1. Soit C un idéal non nul de Fn alors :
i) il existe un unique polynôme unitaire g(x) dans C de degré mi-
nimal ;
ii) g(x) divise xn − 1 dans F[x] ;
iii) pour tout p(x) ∈ C , g(x) divise p(x) dans F[x] ;
iv) Inversement supposons C = (p(x)) où p(x) ∈ Fn . Alors p(x)
est de degré minimal dans C si et seulement si p(x) divise xn − 1 dans
F[x].
Preuve : i) Supposons que f (x) et g(x) sont deux polynômes dis-
tincts, unitaires et de degré minimal k . On pose h(x) = f (x) − g(x) ∈
C . Il est de degré < k . Si λ est le coecient du plus haut monôme alors
λ−1 h(x) est unitaire de degré < k . Contradiction.
ii) En faisant la division euclidienne : xn − 1 = q(x)g(x) + r(x) où
q(x), r(x) ∈ F[x] et deg(r(x)) < deg(g(x)) ou r(x) = 0. En passant aux
classes on a dans Fn : r(x) = −q(x)g(x) ∈ C . Mais puisque g(x) est de
degré minimal on a r(x) = 0 et donc g(x) divise xn − 1 dans F [x].
iii) Soit p(x) ∈ C . On a p(x) = q(x)g(x) + r(x) où q(x), r(x) ∈ F[x]
et deg(r(x)) < deg(g(x)) ou r(x) = 0. Puisque deg(p(x)) < n alors en
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 5. CODES CYCLIQUES 55

passant à Fn on a r(x) = p(x) − q(x)g(x) ∈ C , or g(x) est de degré

minimal d'où r(x) = 0 et donc g(x) divise p(x) dans F[x].
iv) ⇒) par ii) et ⇐) évident.
Exemple 5.2.2. On cherche les idéaux non triviaux de F3 [x] et
on déduit tous les codes cycliques de longueur 3. On a x3 − 1 = (x −
1)(x2 +x+1) ces facteurs sont irréductibles sur F2 . D'où C1 = (x−1) =
{0, 1 + x, x + x2 , 1 + x2 } et C2 = (x2 + x + 1) = {0, 1 + x + x2 } ou
C1 = {000, 110, 011, 101}et C2 = {000, 111}.
Définition 5.2.3. Soit un idéal non nul C ⊂ Fn et g(x) l'unique
polynôme minimal unitaire de C . Alors g(x) est appelé polynôme géné-
rateur du code cyclique C .
Remarque 5.2.4. Soit C = (p(x)). Alors p(x) est le polynôme
générateur de C si et seulement si p(x) est unitaire et divise xn − 1.
Le polynôme générateur d'un code cyclique détermine, une matrice
génératrice et une matrice de contrôle.
Théorème Soit C ⊂ Fn un code cyclique de polynôme géné-
5.2.5.
rateur g(x) = g0 + g1 x + · · · + gr−1 xr−1 + gr xr . Alors C est de dimension
n − r. De plus la matrice (n − r) × n
g(x) g0 g1 g2 · · · gr 0 0 ··· 0
   
xg(x)   0 g0 g1 · · · gr−1 gr 0 ···
.. = . . . .. 
 
G=   .. .. ..
 . . 
xn−r−1 g(x) 0 0 0 g0 g1 ··· gr
est une matrice génératrice de C .
Preuve : Par le Théorème 5.2.1, il existe h(x) tel que g(x)h(x) =
x − 1. D'où g0 6= 0. Les lignes de G sont linéairement indépendantes.
n

En les écrivant comme polynômes les lignes de G sont : g(x), xg(x), · · · ,

xk−1 g(x). Soit p(x) ∈ C , d'après le Théorème 5.2.1 p(x) = q(x)g(x) où
q(x) est un polynômes tel que deg(q(x)) < n−r puisque deg(p(x)) < n.
D'où q(x) est de la forme q(x) = q0 + q1 x + · · · + qn−r−1 xn−r−1 et
p(x) = q0 g(x)+q1 xg(x)+· · ·+qn−r−1 xn−r−1 g(x) et p(x) est combinaison
linéaire des lignes de G. Donc G est une matrice génératrice de C .
On sait que si G est une matrice génératrice d'un code C alors un
mot x ∈ Fk est codé comme xG ∈ C .
Si C est un code cyclique de polynôme générateur g(x) alors r =
deg(g(x)) = n − k et les lignes de G sont g(x), xg(x), · · · , xk−1 g(x).
Soit u = u0 u1 · · · uk−1 , u(x) = u0 + u1 x + · · · + uk−1 xk−1 Alors
uG = u0 g(x) + u1 xg(x) + · · · + uk−1 xk−1 g(x) = u(x)g(x)
Donc un message polynômial u(x) est codé comme u(x)g(x).
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 5. CODES CYCLIQUES 56

Définition 5.2.6. Soit g(x) le polynôme générateur d'un code cy-

clique C ⊂ Fn . Le polynôme h(x) tel que xn − 1 = g(x)h(x) est appelé
polynôme de contrôle de C .
Si C est un [n, k]-code cyclique, alors son polynôme générateur g(x)
est de degré n − k et son polynôme de contrôle est de degré k .

Théorème 5.2.7. Soit C ⊂ Fn un code cyclique de polynôme

de contrôle h(x) et p(x) ∈ Fn . Alors p(x) ∈ C si et seulement si
p(x)h(x) = 0.
Preuve : Soit g(x) le polynôme générateur de C alors g(x)h(x) =
x − 1 d'où g(x)h(x) = 0 dans Fn . Soit p(x) ∈ C , par le Théorème
n

5.2.1 on a p(x) = q(x)g(x) et p(x)h(x) = q(x)g(x)h(x) = 0 dans Fn .

Inversement si p(x) ∈ Fn tel que p(x)h(x) = 0, alors p(x)h(x) =
f (x)(xn − 1). D'où p(x)h(x) = f (x)g(x)h(x). Donc p(x) = f (x)g(x)
d'où p(x) ∈ C .

Théorème 5.2.8. Soit C un [n, k]-code de polynôme de contrôle

h(x) = h0 + h1 x + · · · + hk−1 xk−1 + hk xk . Alors
1) la matrice (n − k) × n
hk hk−1 hk−2 · · · h0 0 0 · · · 0
 
 0 hk hk−1 · · · h1 h0 0 · · · 0 
 ...
H= ..
.
..
.
.. 
. 
0 0 ··· 0 hk hk−1 ··· h0
est une matrice de contrôle du code C .
2) Le code dual est cyclique et de polynôme générateur
h(x) = hk + hk−1 x + · · · + h0 xk = xk h(1/x).
Preuve : Les lignes de H sont linéairement indépendantes. On montre
que chaque ligne est orthogonale à C , donc dans C ⊥ . Soit p(x) =
a0 + a1 x + · · · + an−1 xn−1 ∈ C . On a p(x)h(x) = 0 d'où ai−k hk +
ai−k+1 hk−1 + · · · + ai h0 = 0 pour i = k, k + 1, · · · , n − 1. D'où
a0 0
  
 a1   0 
 ...  = 
H .. 
 
. 
an−1 0
d'où les lignes de H sont n − k vecteurs linéairement indépendants
dans l'espace dual C ⊥ . Donc H est une matrice génératrice de C ⊥ et
par conséquent une matrice de contrôle de C .
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 5. CODES CYCLIQUES 57

Exemple 5.2.9. Écrivez les matrices génératrice et de contrôle du

code cyclique de Hamming Ham(3, 2). Écrivez le code complet.
On a montré que g(x) = x3 + x + 1 est le polynôme générateur de
Ham(3, 2) par l'exemple 5.2.12
 
1 1 0 1 0 0 0
 0 1 1 0 1 0 0 
G=
 0

0 1 1 0 1 0 
0 0 0 1 1 0 1
le polynôme de contrôle est h(x) = (x7 −1)/(x3 +x+1) = x4 +x2 +x+1
par le Théorème .
 
1 0 1 1 1 0 0
H= 0 1 0 1 1 1 0 
0 0 1 0 1 1 1
est une matrice de contrôle de C .
Théorème Le code binaire de Hamming Ham(r, 2) est équi-
5.2.10.
valent à un code cyclique.
Preuve : Soit p(x) un polynôme irréductible dans F2 [x]. On sait que
r
F2 [x]/(p(x)) est un corps dont les éléments s'écrivent {0, α0 , α1 , α2 , · · · , α2 −2 }
où α est un élément primitif. On associe chaque élément a0 + a1 x +
a2 x2 + · · · + ar−1 xr−1 ∈ F2 [x]/(p(x)) avec le vecteur colonne
 
a0
 a1 
 
 ··· 
ar−1
Soit n = 2r − 1. La matrice r × n
H = [1, α, α2 , · · · , αn−1 ]
est une matrice de contrôle de C = Ham(r, 2) puisque ses colonnes
sont les éléments non nuls de F2r . On a
C = {c(x) ∈ Fn : c(α) = 0}
et C est cyclique.
Exercice : Quel est le polynôme générateur de Ham(r, 2) ?

Corollaire Tout polynôme primitif dans F2r est un poly-

5.2.11.
nôme générateur du code cyclique de Hamming Ham(r, 2).
Soit α un élément primitif de F2r et p(x) son polynôme minimal.
Alors Ham(r, 2) = (p(x)).
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 5. CODES CYCLIQUES 58

Exemple 5.2.12. Trouvez le polynôme générateur du code cyclique

Ham(3, 2).
Le polynôme p(x) = x3 +x+1 sur F2 est irréductible. Le sous-groupe
multiplicatif du corps F32 est d'ordre 7, dont tout élément non nul est
primitif. D'après le théorème (x3 + x + 1) = Ham(3, 2).
Exercise 5.3. Ecrivez les matrices génératrice et de contrôle ca-
noniques du code cyclique de Hamming Ham(3, 2).
Théorème 5.3.1. Soit C un [n, k]-code sur un corps F de polynôme
générateur g(x) et A une matrice k × (n − k) dont la ieme ligne est le
reste de la division de xn−k+i−1 par g(x), i = 1, · · · , k. Les matrices
.
génératrice et de contrôle canoniques de C sont G = (Ik .. − A) et H =
.
(At ..In−k ) respectivement.
Preuve : Par resg(x) (f (x)) on note le reste de la division euclidienne
du polynôme f (x) par g(x).
On sait que deg(g(x)) = n − k . D'où resg(x) (xj ) = xj pour j <
n − k . Puisque g(x) divise xn − 1 on a resg(x) (xn+j ) = resg(x) (xj )
pour tout j ≥ 0. Il sut alors de calculer resg(x) (xj ) seulement pour
j = n − k, · · · , n − 1.
On pose Gi (x) = xi−1 − xk resg(x) (xn−k+i−1 ) pour i = 1, · · · , k . On a
deg(Gi (x)) < n d'où Gi (x) ∈ Fn . De plus xn−k+i−1 −resg(x) (xn−k+i−1 ) ∈
C d'où Gi (x) = xk (xn−k+i−1 − resg(x) (xn−k+i−1 )) ∈ C .
Soit G la matrice k × n dont la ie ligne est Gi (x) (écrite comme
vecteur) i = 1, · · · , k , alors
.
G = (Ik .. − A)
où A est une matrice k×(n−k) dont la ie ligne est resg(x) (xn−k+i−1 ). Les
lignes de G sont des éléments de C et sont linéairement indépendantes.
Donc G est la matrice canonique de C . D'où la matrice de contrôle
.
canonique de C est H = (At ..I ).
n−k

5.4. Décodage
Le théorème suivant montre qu'on n'a pas besoin d'avoir une ma-
trice de contrôle d'un code linéaire cyclique pour calculer le syndrome.
Théorème 5.4.1.Soit C un [n, k]-code cyclique sur un corps F de
polynôme générateur g(x). Alors pour tout a ∈ Fn , le syndrôme S(a)
est égale au reste de la division de xn−k a(x) par g(x).
A


Preuve : On sait par le Théorème 5.3.1 que H t = In−k
où A
est une matrice k × (n − k) dont la ieme ligne est resg(x) (x n−k+i−1
)
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 5. CODES CYCLIQUES 59

, i = 1, · · · , k . La ieme ligne de In−k est xj−1 , j = 1, · · · , n − k . En

utilisant la relation resg(x) (xn+j ) = resg(x) (xj ) on déduit que la ieme
ligne de H t est resg(x) (xn−k+i−1 ), i = 1, · · · , n.
Soit a = a0 a1 · · · an−1 et a(x) = a0 + a1 x + · · · + an−1 xn−1 ∈ Fn

S(a) = (a0 a1 · · · an−1 )H t

Xn
= ai−1 resg(x) (xn−k+i−1 )
i=1
n
!
X
= resg(x) ai−1 xn−k+i−1
i=1
n−k
= resg(x) (x a(x))

Remarque 5.4.2.Si C est un code cyclique de polynôme généra-

teur g(x), deux polynômes a(x) et b(x) sont dans la même classe si
et seulement si g(x) divise a(x) − b(x) ce qui veut dire resg(x) (a(x)) =
resg(x) (b(x)), donc on peut aussi dénir le syndrome de a(x) par S(a) =
resg(x) (a(x))

Exercise Soit C un code cyclique de polynôme générateur g(x)

5.5.
et H la matrice dont les lignes sont resg(x) (xj−1 ) pour j = 1, · · · , n.
Montrer que H est une matrice de contrôle de C .
Remarque 5.5.1. Dans le cas des codes cycliques, le polynôme gé-
nérateur joue un rôle principale, contrairement aux matrice de généra-
trice et de contrôle.
Lemme Soit C ⊂ Fqn un code linéaire de distance minimale
5.5.2.
d. Montrer qu'un mot xinFqn est l'unique représentant de la classe x+C
si ω(x) ≤ (d − 1)/2.
Corollaire Soit C un code cyclique de polynôme généra-
5.5.3.
teur g(x). Soit y un mot reçu de syndrome S(y). Si deg(S(y)) =≤
[(d(C) − 1)/2] alors y(x) est décodé comme y(x) − S(x).

On a y et S(y) sont dans la même classe de plus S(y) est un repré-

sentant puisque ω(x) ≤ (d − 1)/2.

Lemme Soit C un [n, k]-code cyclique de polynôme générateur

5.5.4.
g(x) et s(x) = i=0 si xi le syndrome de c(x). Le syndrome de
Pn−k−1

(9) S(xc(x)) = xS(x) − sn−k−1 g(x)

Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 5. CODES CYCLIQUES 60

Preuve : On divise c(x) par g(x) on obtient c(x) = q(x)g(x) + S(x)

d'où

(10) xc(x) = xq(x)g(x) + xS(x)

(11) = (xq(x) + sn−k−1 )g(x) + (xS(x) − sn−k−1 g(x)).

Puisque deg(xs(x) − sn−k−1 g(x)) < n − k = deg(g(x)). on déduit le

résultat.

Exemple Soit le [7, 4]-code de polynôme générateur g(x) =

5.5.5.
1 + x + x . Le mot w = 0110110, s'écrit w(x) = x + x2 + x4 + x5 =
2 3

x + x2 g(x). Donc S(w(x)) = x s'écrit 010. Les syndromes de xw(x) et

x2 w(x) sont xx = x2 et xx2 − g(x) = 1 + x2 , respectivement.

Soit x un n-tuple. Un cycle de 0 de longueur ` est une succession de

` zéro consécutifs. Par exemple (0, 0, 3, 2, 0, 0, 0, 1, 0, 0) a un cycle de 0
de longueur 4.

Algorithme de décodage. Soit C un [n, k, d]-code cyclique de

polynôme générateur g(x). y(x) un mot reçu, e(x) l'erreur telle que
ω(e(x)) ≤ (d − 1)/2 avec un cycle de 0 de longueur ≤ k . Le but est de
déterminer e(x). On note t = [(d − 1)/2].
Étape 1 : calculer les syndromes de S(xi y(x)) et on note si (x) =
S(xi y(x)) mod g(x), pour i = 0, 1, 2, · · · ;
Étape 2 : trouver m tel que le ω(sm (x)) ≤ t.
Étape 3 : calculer e(x) = xn−m sm (x) mod (xn − 1). Décoder y(x)
par y(x) − e(x).
Preuve : On montre l'existence de m de l'étape 2. y(x) = c(x)+e(x)
en multipliant y(x) par xm , on peut ramener le cycle de 0 de longueur
≤ k de e(x) à la n et les composantes non nulles dans les n − k pre-
mières composantes. Soit r(x) := ((xm y(x) (modxn −1)) (mod g(x))) =
(xm y(x) (mod g(x))). on a ω(r(x)) = ω(e(x)) ≤ t. D'où l'existence de
m.
On pose p(x) := (xn−m sm (x) (mod xn − 1))

xm (y(x) − p(x)) ≡ xm (y(x) − xn−m sm (x))

≡ xm y(x) − xn sm (x)
≡ sm (x) − xn sm (x)
≡ (1 − xn )sm (x)
≡ 0 modg(x)
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 5. CODES CYCLIQUES 61

Puisque xm et g(x) sont premiers entre eux, y(x) − p(x) est divisible
par g(x), p(x) et e(x) sont dans la même classe, d'où
e(x) = p(x) = (xn−m sm (x) (mod xn − 1))
par le Lemme 5.5.2.
i si (x)
0 1 + x + x2
1 1+x
2 x + x2
3 1
Exemple 5.5.6. Déterminons tous les codes binaires cycliques de
longueur 7. On a :
x7 −1 = (x−1)(x3 +x+1)(x3 +x2 +1) = (x+1)(x3 +x+1)(x3 +x2 +1).
Comme il y a trois facteurs, il y a 23 = 8 codes cycliques y compris 0
et F72 .
i) 1 = 1, engendre F72
ii) x + 1 = x + 1, engendre le code de parité
iii) x3 + x + 1 = x3 + x + 1, engendre le code [7, 4] de Hamming
iv) x3 + x2 + 1 = x3 + x2 + 1, engendre le code [7, 4] de Hamming
v) (x + 1)(x3 + x + 1) = x4 + x3 + x2 + 1, engendre le code [7, 3]
vi) (x + 1)(x3 + x2 + 1) = x4 + x2 + x + 1, engendre le code [7, 3]
vii) (x3 + x + 1)(x3 + x2 + 1) = x6 + x5 + x4 + x3 + x2 + x + 1, engendre
le code de répitition
viii) (x + 1)(x3 + x + 1)(x3 + x2 + 1) = x7 + 1, engendre le code 0.

Master C2SI - Théorie des codes I E. M. Souidi

CHAPTER 5. CODES CYCLIQUES 62

5.6. Idempotents
En plus du polynôme générateur d'un code cyclique qui détermine
ce dernier, il y a le polynôme idempotent.
Un élément e d'un anneau est appelé idempotent si e2 = e.
Théorème 5.6.1. Soit C un code cyclique dans Fn . Alors :
i) il existe un unique idempotent e(x) ∈ C tel que C = (e(x)),
ii) si e(x) est un idempotent non nul de C , alors C = (e(x)) si et
seulement si e(x) est un unité de C .
Preuve :
Théorème Soit C un code cyclique sur Fq de polynôme
5.6.2.
idempotent e(x). Alors le polynôme générateur de C est g(x) = pgcd(e(x), xn −
1) dans Fq [x].
Preuve :
. Soit C un [n, k]-code cyclique de polynôme idem-
Théorème
P5.6.3
potent e(x) = i=0 i x . Alors la matrice k × n matrix
n−1
e i
 
e0 e1 e2 · · · en−2 en−1

 en−1 e0 e1 · · · en−3 en−2  
 ··· 
en−k+1 en−k+2 en−k+3 · · · en−k−1 en−k
est une matrice génératrice de C .
Preuve :
Exercice : Combien y a t-il de codes cycliques triaires de longueur
4 ? Pour chacun déterminer un polynôme générateur et une matrice
génératrice.
Exercice : Combien y a t-il de codes cycliques de longueur 8 sur
F3 ? Donnez un polynôme générateur pour chacun.
Puisque (1 + x2n ) = (1 + xn )2 , on a besoin de trouver seulement
les facteurs de 1 + xn , où n est impair.

5.7. Codes quasi-cycliques

Définition 1. Un code C de longueur n est quasi-cyclique d'ordre
s où s est un diviseur de n si on a σ s (x) ∈ C pour tout x ∈ C où σ est
la permutation circulaire.
Un code cyclique est un code quasi-cyclique d'ordre s = 1.
Si C est un code de longueur n alors C est quasi-cyclique d'ordre s
pour tout s qui divise n.
Si C est un code quasi-cyclique d'ordre s alors le code dual C ⊥ est
quasi-cyclique d'ordre s.
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 5. CODES CYCLIQUES 63

n factorisation de (xn − 1) dans Z2

(1 + x2n ) = (1 + xn )2
1 (1 + x)
3 (1 + x)(1 + x + x2 )
5 (1 + x)(1 + x + x2 + x3 + x4 )
7 (1 + x)(1 + x + x3 )(1 + x2 + x3 )
9 (1 + x)(1 + x + x2 )(1 + x3 + x6 )
11 (1 + x)(1 + x + · · · + x9 + x10 )
13 (1 + x)(1 + x + · · · + x11 + x12 )
15 (1 + x)(1 + x + x2 )(1 + x + x4 )(1 + x + x2 + x3 + x4 )(1 + x3 + x4 )
17 (1 + x)(1 + x + x2 + x4 + x6 + x7 + x8 )(1 + x3 + x4 + x5 + x8 )
19 (1 + x)(1 + x · · · + x17 + x18 )
21 (1 + x)(1 + x + x2 )(1 + x2 + x3 )(1 + x + x3 )
(1 + x2 + x4 + x5 + x6 )(1 + x + x2 + x4 + x6 )
23 (1 + x)(1 + x + x5 + x6 + x7 + x9 + x11 )
(1 + x2 + x4 + x5 + x6 + x10 + x11 )
25 (1 + x)(1 + x + x2 + x3 + x4 )(1 + x5 + x10 + x15 + x20 )
27 (1 + x)(1 + x + x2 )(1 + x3 + x6 )(1 + x9 + x18 )
29 (1 + x)(1 + x + · · · + x27 + x28 )
31 (1 + x)(1 + x2 + x5 )(1 + x3 + x5 )(1 + x + x2 + x3 + x5 )
(1 + x + x2 + x4 + x5 )(1 + x + x3 + x4 + x5 )(1 + x2 + x3 + x4 + x5 )
Table 1. Factorisation de (x − 1) dans Z2
n

Proposition 5.7.1. Soit C est un [n, k]-code quasi-cyclique d'ordre

s avec n = rs alors il existe une matrice k 0 × n (où k 0 × k ) génératrice
G de a forme :

A1 A2 A3 · · · Ar
 
 Ar A1 A2 · · · Ar−1 
 ...
G= .. .. ..
. . .
.. 
. 
A2 A3 A4 · · · A1

où les Ai sont des matrice k0

r
× s.

Preuve : Par récurrence. Soit G0 une matrice 1 × n nulle et un mot

aléatoire c = (c1 , · · · , cn ) de C . Partageons c en r = n/s parties égales :
(c1 , · · · , cs ), (cs+1 , · · · , c2s ), · · · ,(cn−s+1 , · · · , cn ) . On construit les ma-
trices 1 × s A1i = (cs(i−1)+1 , · · · , csi ) , 1 ≤ i ≤ r obtenus par r shifs
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 5. CODES CYCLIQUES 64

cycliques. On considère alors la matrice

A11 A12 A13 · · · A1r

 
 A1r A11 A12 · · · A1r−1 
 ...
G= ..
.
..
.
..
.
.. 
. 
A12 A13 A14 · · · A11
elle engendre un code C1 , si C1 = C alors on arrête sinon on considère
un mot c2 de C qui n'est pas dans C1 . On partage c2 en s parties égales
on ajoute la deuxième ligne à la matrice A1i pour obtenir la matrice
A2i . On considère alors les matrices G2 , G3 ,· · · , Gj ,
Puisque le rang de matrice Gj crois strictement avec j , ça va s ?arrêter
pour un certain j0 vériant k 0 = j0 .r ≥ k puisque Gj0 engendre C . Re-
marquons que j0 varie et dépend des élements aléatoires c1 , c2 , · · ·

Remarque 5.7.2. 1) Vu la forme de la matrice génératrice, il sut

de connaitre les matrices A1 ,· · · An pour déduire la matrice G.
2) La matrice G engendre le code C mais elle n'est pas nécessaire-
ment une matrice génératrice de C puisque k0 peut être plus grand que
k.
Dans ce qui suit nous montrons comment construire des sous-codes
quasi-cycliques d'ordre s à partir d'un code quasi-cyclique d'ordre s.

Théorème 1.Soit C un [n, k]-code quasi-cyclique d'ordre s et n =

rs. Alors il existe un sous-code quasi-cyclique d'ordre s strictement
inclue dans C et de dimension ≥ k − r = k − ns .
Si C est quasi-cyclique d'ordre s alors le dual C ⊥ de C est quasi-
cyclique d'ordre s. Soit x un mot aléatoire de F2n − C ⊥ et considérons
la matrice génératrice obtenue en ajoutant x et ses r − 1 s-shift à une
matrice génératrice de C ⊥ . Le code Cx engendré par Gx est quasi-
cyclique par construction d'ordre s et de dimension n − k + r . Le dual
de Cx⊥ est quasi-cyclique d'ordre s de dimension ≥ k − r = k − ns .

Proposition 5.7.3. Soit C un [n, k]-code quasi-cyclique d'ordre

s. Alors au moins 2k−r codes distincts peuvent être construit par le
théorème précédant.
Preuve : Le nombre de sous codes distinct est égale au nombre
de duaux de ces codes distincts. Le code dual est dimension au plus
n − k + r. L'union de tous les duaux possibles doit être l'espace en
entier, puisque chaque code est de dimension au plus n − k + r alors il
y a au moins 2n−(n−k+r) = 2k−r sous-codes quasi-cycliques distincts.
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 5. CODES CYCLIQUES 65

5.8. Exercices
Exercice 3. Déterminer tous les codes cycliques binaires de longueur
7.

Exercice 4. Trouvez tous les codes binaires cycliques de longueur 4.

Ainsi que ses matrices génératrice et de contrôle. De même pour 5, 6
et 7.

Exercice 5. Montrez que le code Ham(2, 3) n'est pas cyclique.

Exercice 6. Trouvez tous les codes triaires cycliques de longueur 4.

Écrire une matrice de contrôle pour chacun d'entre eux.

Exercice 7. Montrer que le code {0000, 1001, 0110, 1111} est équi-
valent à un code cyclique.

Exercice 8. Combien y a t-il de codes cycliques binaires de longueur

10.
Exercice 9. Soit C le code de longueur 7 sur F2 et de polynôme
générateur g(x) = x3 + x + 1.
1) Déterminer le polynôme de contrôle de C .
2) Déterminer une matrice génératrice et une matrice de contrôle de
C.
3) C est-il un code de Hamming ?

Exercice 10. i) Montrer que le code binaire de Hamming Ham(r, 2)

est équivalent à un code cyclique.
ii) Quel est le polynôme générateur de Ham(r, 2) ?

Exercice 11. Soient C1 et C2 deux codes cycliques de polynômes

générateurs g1 (x) et g2 (x) respectivement . Montrer que C1 ⊂ C2 si
seulement si g2 (x) divise g1 (x).

Exercice 12. 1) Trouvez tous les codes linéaires cycliques trinaires de

longueur 4.
2) Écrire une matrice de contrôle pour chacun des codes de la question
1).
3) Montrer que le code Ham(2, 3) n'est pas cyclique.

Exercice 13. Soit C1 et C2 deux codes cycliques sur F de longueur

n et de polynômes générateurs g1 (x) et g2 (x) respectivement. Montrer
que les ensembles suivants sont des codes cycliques sur F de longueur
n et déterminer leur polynômes générateurs.
1) C1 ∩ C2 ;

Master C2SI - Théorie des codes I E. M. Souidi

CHAPTER 5. CODES CYCLIQUES 66

2) C1 + C2 ;
3) {c(x) ∈ Fn : c(x) ≡ g2 (x)c1 (x) mod(xn − 1), c1 (x) ∈ C1 }
(Indication : considérer d'abord le cas pgcd(g1 (x), g2 (x)) = 1).

Exercice 14. Soit m un mot non nul de Fnq et soit Cm le sous-espace

vectoriel de Fnq engendré par la famille

{σ i (m) | i = 0, 1, · · · , n − 1}.

1. Montrer que
(a) Cm est un code cyclique de longueur n.
(b) Cm est le plus petit code cyclique de longueur n sur Fq contenant
le mot m.
(c) Le polynôme générateur du code Cm est le pgcd des polynômes
X n − 1 et m(X).
2. Déterminer le polynôme générateur de Cm lorsque q = 3, n = 9 et
m = 022011000.

Exercice 15. Dans F2 , (1 + x) divise (xn − 1). Soit C le codes binaire

cyclique de polynôme de polynôme générateur 1 + x et de longueur n.
Soit C1 un code quelconque binaire cyclique de polynôme générateur
g(x) et de longueur n.
a) Quelle est la dimension de C ?
b) Montrer que C est l'ensemble des vecteurs de Fn2 de poids pair.
c) Si C1 a seulement des mots de poids pair, quelle relation y a-t-il
entre 1 + x et g(x) ?
d) Si C1 a certains mots de poids impair, quelle relation y a-t-il entre
1 + x et g(x) ?
Exercice 16. 1. Montrer, sans eectuer de division euclidienne, que
dans F3 [X], le polynôme g(x) = (X − 1)5 divise le polynôme (X 9 − 1).
2. Soit C le code cyclique de longueur 9 sur F3 , engendré par le poly-
nôme g .
a) Quelle est la dimension de C ?
b) Quel est le nombre de mots de C ?
3. Développer le polynôme g dans F3 [X], en détaillant et justiant les
calculs.
4. Pourquoi la matrice
 
2 2 2 1 1 1 0 0 0
 0 2 2 2 1 1 1 0 0 
G=
 0

0 2 2 2 1 1 1 0 
0 0 0 2 2 2 1 1 1
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 5. CODES CYCLIQUES 67

est-elle une matrice génératrice du code C ?

5. Montrer que C contient un mot de poids 3.
6. Montrer que le polynôme de contrôle de C est le polynôme h(x) =
X 4 + 2X 3 + 2X + 1. 7. Déterminer une matrice de contrôle de C .
8. Déterminer la distance minimale du code C et le nombre d'erreurs
que C peut corriger.
9. Le mot m = 121102210 est reçu.
a) Sous l'hypothèse d'au plus une erreur, quel est le mot de code
émis ?
b) Quel est le message envoyé, sachant qu'il est encodé par la ma-
trice G ?

Exercice 17. Code ternaire de Golay.

(1) Montrer que le polynôme cyclotomique Φ11 a pour facteurs irré-
ductibles sur F3 polynômes P (X) = X 5 + X 4 − X 3 + X 2 − 1 et
Q(X) = X 5 − X 3 + X 2 − X − 1 sur F3 .
(2) On considère le code G11 engendré par P (X). Donner sa lon-
gueur, sa dimension et montrer que sa distance minimale est 4
ou 5.
(3) Donner un générateur du sous-code pair de G11 .
(4) Montrer que G11 est la somme directe de son sous-code pair et
du code engendré par Φ11 .
(5) On introduit la forme bilinéaire symétrique hx, yi sur F3 [X]/(X 11 −
1) pour laquelle {1, X, X 2 , · · · , X 10 } est une base orthonormale.
Montrer que pour tout x ∈ F3 [X]/(X 11 − 1), on a ω(x) ≡
hx, xi mod 3 où ω(x) désigne le poids de x.
(6) Vérier que G11 est orthogonal a son sous-code pair et calculer
le poids de Φ11 .
(7) En déduire que, pour tout x ∈ G11 , ω(x) ≡ 0 ou 2 mod 3 et que
la distance minimale de G11 est 5.
(8) Montrer que le code G11 est parfait.
Le code G11 s'appelle code ternaire de Golay

Exercice 18. Soit C le code binaire linéaire de longueur 7 dont une

matrice de contrôle est


H= 10000111010010110010110100011110
1. Combien valent la dimension et la distance de C ? Écrire une matrice
génératrice de C .
2. Décoder les mots reçus r1 = 00001110 et r2 = 00010011, en suppo-
sant qu'il y a eu au plus une erreur de transmission.
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 5. CODES CYCLIQUES 68

3. Parmi les mots t1 =????0000, t2 =?0?0?0000 et t3 =?0?0?0?0 qui ont

subi des eacements, les autres bits ayant été transmis correctement,
lesquels peut-on décoder ?
4. Le code C est-il MDS ? Cyclique ? Parfait ?
5. Montrer que, pour tout mode de code m de C, le mot m + 11111111
appartient à C . En déduire le nombre de mots de C de poids 4.
6. Montrer que C est équivalent au code étendu du code de Hamming
Ham(8).
7. Montrer que C est son propre orthogonal.

Exercice 19. Soit g(x) le polynôme générateur d'un code cyclique

binaire C .
a) Montrer que si x + 1 divise g(x) alors C ne contient aucun mot de
poids impair.
b) Montrer que si n est impair et x + 1 ne divise pas g(x) alors C
contient le mot 1 · · · 1.
c) Montrer que si n est le plus petit entier tel que g(x) divise xn + 1
alors la distance minimale de C est au moins 3.
d) On suppose que C contient des mots de poids pairs et impaires. Soit
A(z) le polynôme énumérateur de poids de C . Montrer que le polynôme
(x+1)g(x) engendre un code cyclique binaire de polynôme énumérateur
de poids A1 (z) = 12 [A(z) + A(−z)].
Pn
Rappel ; le polynôme énumérateur de poids A(X) = i=0 Ai x où
n

Ai = |{c ∈ C | ω(c) = i}|

Exercice 20.
1. Montrer, sans eectuer de division euclidienne, que dans F3 [X], le
polynôme g(x) = (X − 1)5 divise le polynôme (X 9 − 1).
2. Soit C le code cyclique de longueur 9 sur F3 , engendré par le poly-
nôme g .
a) Quelle est la dimension de C ?
b) Quel est le nombre de mots de C ?
3. Développer le polynôme g dans F3 [X], en détaillant et justiant les
calculs.
4. Pourquoi la matrice
 
2 2 2 1 1 1 0 0 0
 0 2 2 2 1 1 1 0 0 
G=
 0

0 2 2 2 1 1 1 0 
0 0 0 2 2 2 1 1 1
est-elle une matrice génératrice du code C ?
5. Montrer que C contient un mot de poids 3.
6. Montrer que le polynôme de contrôle de C est le polynôme h(x) =
Master C2SI - Théorie des codes I E. M. Souidi
CHAPTER 5. CODES CYCLIQUES 69

X 4 + 2X 3 + 2X + 1. 7. Déterminer une matrice de contrôle de C .

8. Déterminer la distance minimale du code C et le nombre d'erreurs
que C peut corriger.
9. Le mot m = 121102210 est reçu.
a) Sous l'hypothèse d'au plus une erreur, quel est le mot de code
émis ?
b) Quel est le message envoyé, sachant qu'il est encodé par la ma-
trice G ?

Master C2SI - Théorie des codes I E. M. Souidi

 Bibliographie

[1] Blackmore, T., Norton, G.H. : Matrix-product codes over Fq . Appl. Algebra
Eng. Comm. Comput. 12(6), 477-500 (2001).
[2] W. Cary Human et Vera Pless, Fundamentals of Error-Correcting Codes,
Cambridge University Press, 2003.
[3] J. H. van Lint, Introduction to Coding Theory, Springer.
[4] D. G. Homan, D. A. Leonard, Coding Theory the essentials, Marcel Dekker.
[5] C. E. Shannon, A mathematical theory of communication. Bell Syst. Tech. J.,
27, pp. 379-423, 623-656 (1948).
[6] Tietävïnen A. : On the nonexistence of perfect codes over nite elds, SIAM
J. Appl. Math. 24, 88-96 (1973).
[7] Matthieu Finiasz : Nouvelles constructions utilisant des codes correcteurs d'er-
reurs en cryptographie. Thèse doctorat, École Polytechnique.
[8] M. Van Der Vlugt, The True Dimension of Certain Binary Goppa Codes IEEE
Trans. Inform. Theory 31, no. 2, pp 397-398, 1990.
[9] Reed, I. S. and Solomon, G., Polynomial Codes Over Certain Finite Fields,
SIAM Journal of Applied Math., vol. 8, 1960, pp. 300-304.

71