TIPE : Code correcteur d'erreurs

Melvyn EL KAMELMEYRIGNE

Sous la direction de Benoit Fabrèges

Table des matières
1 Théorie des codes correcteurs 3
1.1 Dénition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Codes binaires . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Codes linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Codage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5 Décodage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.6 Codes parfaits . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2 Code de Hamming 10
3 Codes cycliques 13
3.1 Fonctionnement des codes cycliques . . . . . . . . . . . . . . . 13
3.2 Recherche des codes cycliques . . . . . . . . . . . . . . . . . . 15
3.3 Algorithme de décodage . . . . . . . . . . . . . . . . . . . . . 19

4 Annexes 24
4.1 Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.2 Code SAGE . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

1
Introduction
Lorsque deux personnes communiquent entre elles, il arrive souvent que
le message reçu dière de celui émis ; que ce soit à cause de fautes d'ortho-
graphes, d'une diction trop rapide ou bien de bruits perturbateurs. Toutefois,
il n'est pas toujours nécessaire d'obtenir l'intégralité du message pour en de-
viner le sens. Ainsi, même si on mélange l'ordre des lettres dans un mot
tout en laissant les lettres aux extrémités à leur place, on puet qnaud mmêe
cmopnrde la prshae.
On constate que le transfert d'informations numériques est très important
dans de nombreux domaines, par exemple pour les sondes spatiales qui re-
çoivent des signaux parcourant une énorme distance. Il est donc primordial de
s'assurer que la perte d'informations soit minimale : c'est là qu'interviennent
les codes correcteurs.
L'objectif est de rajouter une couche d'informations au message initial
qui ne rajoute pas de sens mais qui permettront de détecter les erreurs et de
les corriger. Bien évidemment, l'ajout d'informations a un prix : l'ecacité
d'un code sera donc déterminée par la quantité d'informations ajoutée et par
sa capacité à conserver l'information d'un message. Nous allons nous pencher
sur les principaux codes correcteurs binaires et voir comment se déroule le
codage et la correction d'erreurs, notamment pour les codes cycliques.

2
1 Théorie des codes correcteurs
1.1 Dénition
On appellera une lettre la plus petite information transmissible et un mot
comme un ensemble de lettres. L'ensemble des lettres est l'alphabet, noté Ω ;
nous travaillerons avec Ω = {0, 1}.
Ainsi, on considérera qu'un mot m est une suite de lettres appartenant
au corps ni à deux éléments que l'on notera F2 (ou encore 2Z Z
ou GF (2)).
Un mot de longueur n appartient donc à F2 . n

Introduisons quelques dénitions an de pouvoir travailler avec ces mots.

Dénition 1.1.1. On dénit le poids d'un mot m de Fn2 comme le nombre
de composantes non nulles du mot. On le note w(m).
Ainsi, si on note 0 le mot nul et 1 le mot plein (composé uniquement de
1), on a w(0) = 0 et w(1) = n.
Dénition 1.1.2. La distance de Hamming entre deux mots x, y de Fn2 est
le nombre de composantes distinctes de x et y . On la note d(x, y).
Proposition 1.1.3. La distance de Hamming est une distance.
Démonstration. Montrons qu'il s'agit bien d'une distance. Il est clair que
pour tout x, y de Fn2 , on a,

d(x, y) = d(y, x); d(x, y) ≥ 0; d(x, y) = 0 ⇐⇒ x = y.

Vérions l'inégalité triangulaire : Soient x, y , z dans Fn2 ; On note x =

x1 . . . xn , y = y1 . . . yn et z = z1 . . . zn . On dénit les ensembles U , S et T
suivants :

U := {xi 6= zi },
S := {(xi 6= zi ) ∧ (xi = yi )},
T := {(xi =6 zi ) ∧ (xi 6= yi )}.

Ainsi, S ∪T = U et S ∩T = ∅. Donc, d(x, y) = |U | = |T |+|S| et |T | 6 d(x, z)

et |S| 6 d(y, z).
Puisque l'on est dans Fn2 , d(x, y) = w(x − y) = w(x + y).
Dénition 1.1.4. Une boule de Hamming de centre x et de rayon r est
dénie comme,
BH (x, r) = {y ∈ Fn2 | d(x, y) ≤ r}.
On peut maintenant s'intéresser aux codes.

3
1.2 Codes binaires
Dénition 1.2.1. Un code binaire de longueur n et de dimension k est
une partie C de dimension k de Fn2 ; on dit que C est un code de paramètres
(n, k).
En associant à l'action d'encoder une application injective ϕ (l'injectivité
assure que le décodage soit possible), on a C = Im(ϕ).
Un exemple particulièrement simple est le bit de parité : on ajoute à la
n du message un bit correspondant à la parité de la somme des éléments du
message. Si la somme est paire, le bit vaut 0 sinon il vaut 1. Pour un mot de
longueur k , le code associé a donc pour paramètres (k + 1, k). Exemple :

0011010 → 00110101

Lorsqu'il y a au plus une erreur, ce code permet de détecter s'il y a eu

une erreur ou non ; mais il ne permet pas de trouver sa position et donc de
la corriger. De plus, s'il y a un nombre pair d'erreurs, elles se compensent et
sont donc indétectables. On peut pallier partiellement ce dernier problème
en divisant le mot en plusieurs petits mots de longueur 2 que l'on encodera
séparément.
0011010 → 000110101
Ainsi, tant que les erreurs ne se produisent pas sur des bits appartenant
à la même paire, on peut les détecter.
Une autre idée qui pourrait venir à l'esprit serait de répéter plusieurs fois
chaque bit. En répétant n fois chaque bit d'un mot de longueur k , le code
associé a pour paramètres (nk, k). Exemple : On répète deux fois chaque bit,

010 → 000111000

Si une erreur se produit, il est possible de la localiser et de la corriger

facilement :

000111000 → 000111001 (erreur sur la dernière lettre).

On constate que le dernier trio de bits n'est pas composé de lettres iden-
tiques, donc l'erreur provient probablement de la lettre diérentes des deux
autres. Malheureusement, ce code reste lui aussi assez limité : s'il y a deux
erreurs dans le même trio de bits, cela donnera lieu à une mauvaise correc-
tion ; s'il y en a 3, on ne peut même pas détecter l'erreur. On constate qu'en
répétant chaque bit n fois, le code permet de retrouver le bon mot tant qu'il
y a au plus b n−12
c erreurs (b·c désignant la partie entière). Cela peut sembler
correct, mais la quantité d'informations ajoutée est particulièrement élevée.

4
Dénition 1.2.2. La distance minimale dC d'un code C est dénie comme,
dC = min{d(x, y)|x ∈ C, y ∈ C, x 6= y}.

Dénition 1.2.3. La capacité de correction eC d'un code est le plus grand

entier tel qu'il soit toujours possible de corriger eC erreurs ou moins.
Un mot erroné peut donc être corrigé s'il existe un unique mot du code le
plus proche ; de ce fait, les boules de Hamming centrées en un mot du code
et de rayon eC sont disjointes. Il en découle que eC = b dC2−1 c (le −1 permet
de lever l'incertitude lorsqu'il y a d2C erreurs).
La capacité de détection d'erreurs d'un code est naturellement plus éle-
vée : on peut détecter toute erreur e vériant w(e) < dC . En eet, si le mot du
code m est perturbé par l'erreur e, m0 = m + e 6∈ C car sinon e = m − m0 ∈ C
ce qui contredit la dénition de dC .

Dénition 1.2.4. Le taux d'information d'un code C de paramètres (n, k)

est le rapport nk .
On veut maximiser ce taux d'informations (qu'il soit le plus proche pos-
sible de 1) an de ne pas rajouter des données inutilement ; le taux d'infor-
mation d'un code de répétition vaut n1 ce qui est loin d'être désirable.
Intéressons nous à un type de code particulier qui ore des algorithmes
de décodage ecaces : les codes linéaires.

1.3 Codes linéaires

Dénition 1.3.1. Un code C de paramètres (n, k) est dit linéaire si pour tout
m, m0 de C , m + m0 est dans C . C est un sous-espace vectoriel de dimension
k de Fn2

Cette nouvelle condition permet d'établir un lien entre le poids et la

distance minimale :

Proposition 1.3.2. Soit C un code linéaire,

dC = min{w(m)|m ∈ C, m 6= 0}.

Démonstration. Soient x, y dans C tels que dC = d(x, y). On sait que

d(x, y) = w(x+y). Comme C est linéaire, il existe m dans C tel que x+y = m
donc w(x + y) = w(m).

5
 Désormais, nous inclurons la distance minimale du code dans ses para-
mètres ; un code C a pour paramètres (n, k, dC ). Comment déterminer la
distance minimale d'un code ? On pourrait calculer le poids de tous les élé-
ments mais ce serait laborieux. Il est possible d'obtenir une majoration de
dC en fonction de n et de k .

Proposition 1.3.3. Soit C un code linéaire de paramètres (n, k, dC ). Alors,

dC ≤ n − k + 1.

C'est la borne de Singleton.

Démonstration. Il sut de montrer qu'il existe un mot du code dont les k −1
dernières composantes sont nulles. Soit E le sous-espace vectoriel de Fn2 dont
les k − 1 dernières composantes sont nulles, on a dim(E) = n − (k − 1) =
n − k + 1. Donc, dim(C) + dim(E) = n + 1 > n donc C ∩ E 6= {∅}. Il existe
bien un mot du code dont les k − 1 dernières composantes sont nulles ce qui
prouve que dC ≤ n − k + 1.

1.4 Codage
Soit C un code linéaire de paramètres (n, k, dC ). Il existe ϕ une appli-
cation linéaire injective de F2k dans F2n telle que Im(ϕ) = C . On peut le
représenter matriciellement par ϕ(x) = xG; G étant la transposée de la ma-
trice représentative de ϕ par rapport aux bases canoniques de F2k et de F2n .
Les mots sont donc considérés comme des vecteurs lignes. On dit que G est
la matrice génératrice de C et que C est le code engendré par G.
 
1 0 0 1
Exemple : x = (101) , G = 0 1 0 1
0 0 1 1
 
1 0 0 1
ϕ(x) = 1 0 1 *0 1 0 1 = (1010)

0 0 1 1
Il s'agit du codage par bit de parité vu précédemment.

Dénition 1.4.1. Un codeC linéaire de paramètres (n, k, dC ) est dit systé-

matique si l'encodage consiste à rajouter n − k bits à la n du mot. Pour
un code linéaire, sa matrice génératrice G est de la forme (Ik |B), Ik étant la
matrice unité à k lignes et k colonnes et B une matrice à k lignes et n − k
colonnes.

6
 Travailler avec un code systématique nous simpliera quelques calculs par
la suite.

1.5 Décodage
Dénition 1.5.1. On appelle matrice de contrôle d'un code linéaire C de
paramètres (n, k, dC ) la matrice H ∈ Mn−k,n à coecients dans F2 telle que
ker(H) = C . Ainsi, ∀m ∈ C, H t m = 0 et H t G = 0.
Proposition 1.5.2. : S'il existe dans C un mot de poids r, il existe r co-
lonnes de H linéairement dépendantes.
Démonstration. Soit m = m0 m1 ...mn−1 un mot du code de poids r, on note
Ci la i-ème colonne de H et mi1 , mi2 , ...mir les composantes non nulles de m.
   
0 0
 ..   .. 
n−1  .  r  .  r
0 = H tm = H mip Cip donc il existe bien r
P P  P
mi  = H mip  =
  
i=0  .  p=1  . 
 ..   ..  p=1

0 0
colonnes de H étant linéairement dépendantes.
Proposition 1.5.3. S'il existe r colonnes linéairement dépendantes de H ,
alors il existe un mot du code de poids r0 ≤ r.
r
Démonstration. Il existe r scalaires non tous nuls tels que mip Cip = 0.
P
p
Soit m ∈ F2n dont les composantes de rang i1 , i2 , ...ir sont mi1 , mi2 , ...mir et
les autres sont nulles. On a w(m) ≤ r.
On en déduit que la distance minimale dC (c'est-à-dire le poids minimal)
est égale au nombre minimum de colonnes linéairement dépendantes de H .

Dénition 1.5.4. Soit m ∈ F2n , on appelle syndrome s du mot m le vecteur

s = H t m.
Supposons que w soit un mot erroné, w = m + e avec m un mot du code
e l'erreur. Ainsi, H t w = H t (m + e) = H t e ; le mot erroné et l'erreur ont donc
le même syndrome s. L'ensemble des mots de syndrome s est appelé classe
latérale (ou coset ) de w. Corriger w revient donc à trouver le mot dont le
poids w(m) vérie w(m) ≤ eC dans la classe latérale de w ; cela n'est possible
que si ce mot est unique, on suppose donc qu'il y a moins d'erreurs que la
capacité de correction du code.

7
Proposition 1.5.5. Chaque syndrome s est associé à un unique mot m ∈ F2n
dont le poids w(m) vérie w(m) ≤ eC .
Démonstration. Supposons qu'il existe m0 ∈ F2n tel que w(m0 ) ≤ eC et
H t m = H t m0 donc H t (m − m0 ) = 0 et donc m − m0 est un mot du code.
w(m − m0 ) ≤ w(m) + w(m0 ) ≤2eC ≤ dC − 1. Le seul mot du code x qui vérie
w(x) ≤ dC − 1 est le mot nul donc m − m = 0 et m = m0 .
Il sut maintenant de dresser une liste des syndromes de chaque élément
de F2n pour pouvoir retrouver l'erreur et à fortiori le mot codé.

S'il n'y a qu'une erreur : soit ei le mot contenant un 1 à la i-ème place

et des 0 ailleurs. Alors, il existe i tel que w = m + ei . Le syndrome de ei est
donc la i-ème colonne de H , on peut donc facilement localiser l'erreur.

Proposition 1.5.6. Si C est un code systématique et G = (Ik |B), alors

H = (−t B|In−k ).

Démonstration. H t G =t B −t B = 0.
 
1 0 1 0
Exemple : Prenons G = .
0 1 1 1
 
1 1 1 0
Ainsi, H = .
0 1 0 1  
1 0 1 0
Codons le mot m = (01), w = (01) = (0111).
0 1 1 1
Ajoutons lui d'abord une erreur en troisième position : z = (0101).
 
  0  
1 1 1 0 1
 = 1 .
Calculons le syndrome de z : s = H z =
t
0 1 0 1 0 0
1
Cela correspond à la troisième colonne de H , l'erreur provient donc du
troisième bit.

1.6 Codes parfaits

Intéressons-nous à C en tant qu'espace vectoriel.
r
Proposition 1.6.1. #BH (x, r) = Cni .
P
i=0

8
Démonstration. Pour tout i ∈ {0, 1, ..., r}, il existe Cni mots y ∈ F2n tels que
d(x, y) = i.
ec
Proposition 1.6.2. Inégalité de Hamming : Cni ≤ 2n−k .
P
i=0

Démonstration. Les boules BH (m, eC ) centrées en les mots du codes de rayon

eC sont deux à deux disjointes donc :
eC
#BH (m, eC ) = Cni ≤ |{0, 1}n | = 2n .
P P P
m∈C m∈C i=0

Il y a 2k boules de Hamming dans le code donc :

eC eC
2k Cni ≤ 2n et donc Cni ≤ 2n−k .
P P
i=0 i=0

La situation optimale serait donc que les boules de Hamming forment

une partition de F2n , ce qui est le cas lorsque l'inégalité de Hamming est une
égalité.

Figure 1  Situation où chaque mot est associé à un unique mot du code.

Dénition 1.6.3. Un code C de paramètres (n, k, dC ) est dit parfait lorsque

les boules de Hamming centrées en les mots du code de rayon eC forment une
partition de F2n .
eC
Ainsi, Cni = 2n−k et ∀ m ∈ F2n , il existe m qui minimise d(r, m). On
P
i=0
remarquera que dC est forcément impair.

9
2 Code de Hamming
Créons un code qui satisfait l'égalité de Hamming et qui soit capable
de corriger une erreur ; on prend donc la distance minimale la plus petite
possible, dC = 3.

Posons r = n − k .
1
Cni = 2n−k ⇒ 1 + n = 2k
P
i=0
n = 2r − 1 et k = 2r − r − 1.

Les codes ayant ces paramètres sont appelés codes de Hamming.

Dénition 2.0.1. Un code de Hamming est un code de paramètres (2r −

1, 2r − r − 1, dC ) avec r ≥ 2 ; c'est un code parfait.

Les codes parfaits ayant une capacité de correction 1 sont donc nécessai-
rement des codes de Hamming. Pour r = 2, le code parfait de paramètres
(3, 1, 3) est le code de répétition.

Exemple : Étudions le cas r = 3.

Considérons un code linéaire systématique C(7, 4, 3). Soit x ∈ F42 , x =
d1 d2 d3 d4 et soit ϕ : F24 → F27 telle que ϕ(x) = d1 d2 d3 d4 p1 p2 p3 avec p1 =
d1 + d2 + d4 , p2 = d1 + d3 + d4 et p3 = d2 + d3 + d4 . On obtient la matrice
génératrice
 
1 0 0 0 1 1 0
0 1 0 0 1 0 1
G= 0 0 1 0 0 1 1.


0 0 0 1 1 1 1
Essayons d'encoder un mot, de modier un de ses bits et de le décoder. Pre-
nons m = (1010)
 . 
1 0 0 0 1 1 0
0 1 0 0 1 0 1
mG = (1010) 0 0 1 0 0 1 1 = (1010101).


0 0 0 1 1 1 1
Modions le 4ème bit (1010101) −→ (1011101) Puisque le code est sys-
tématique,
 on peut rapidement
 trouver la matrice de contrôle H .
1 1 0 1 1 0 0
H = 1 0 1 1 0 1 0 On a bien H t G = 0.
0 1 1 1 0 0 1

10
Calculons le syndrome du message  erroné :
1 1 0
1 0 1
 
0 1 1
 = (111).
 
(1011101)t H = (1011101)   1 1 1
1 0 0
 
0 1 0
0 0 1
On obtient trois 1, il y a donc une erreur sur les trois bits de parité ; l'er-
reur provient donc du bit qui intervient dans la construction des trois bits
de parité : le quatrième. On aurait bien sûr reprendre l'algorithme vu précé-
demment et retrouver le même résultat.

Figure 2  Illustration montrant comment repérer facilement la provenance

d'une erreur.

Ainsi, ce code est plus ecace qu'un simple code linéaire. Voilà une com-
paraison en image (avec un taux d'erreur de 0.01) :

Figure 3  Code de Hamming/ Code linéaire généré aléatoirement

Ces codes ont été réalisés sur Cocalc https://cocalc.com/ (ancienne-

11
ment nommé Sage) et sont disponibles dans l'annexe. J'ai utilisé le Jupi-
ter Notebook et le kernel le plus récent (SageMath Dev). Cocalc permet de
travailler facilement avec plusieurs types de codes correcteurs (linéaires, de
Hamming, cycliques) et permet de simuler l'apparition d'erreurs.

12
3 Codes cycliques
3.1 Fonctionnement des codes cycliques
Dénition 3.1.1. Un code linéaire est dit cyclique s'il est stable par déca-
lage circulaire.
Plus formellement, soit C un code de paramètres (n, k, dC ) et m ∈ F2n ,
m = m0 m1 ...mn−1 . On note σ(m) = mn−1 m0 ...mn−2 .
Alors, C est cyclique si ∀m ∈ C, σ(m) ∈ C .
Ainsi, ∀k ∈ N , σ k (m) ∈ C et σ n (m) = m.
Exemple Le code C = {000, 110, 011, 101} est cyclique.
Dénition 3.1.2. Soit m = m0 m1 ...mn−1 un mot, m(X) = m0 + m1 X +
... + mn−1 X n−1 est la représentation polynomiale associée à m. On notera PC
la représentation polynômiale d'un code (on pourra aussi utiliser C s'il n'y a
pas de risque de confusion).
En reprenant le code précédent, on a PC = {0, 1 + X, X + X 2 , 1 + X 2 }.

Regardons à quoi correspond un décalage circulaire vers la droite en

termes de polynôme.

σ(m)(X) = mn−1 + m0 X + ... + mn−2 X n−1

= Xm(X) + mn−1 (1 − X n ).

Donc, σ(m)(X) = X(m)X (mod X n − 1).

C'est ce qui nous motive à travailler dans l'anneau des polynômes à coe-
F2 [X]
cients dans F2 modulo (X n − 1) : X n −1 .

Rappelons la dénition d'un idéal :

Dénition 3.1.3. Un sous-ensemble non-vide I d'un anneau commutatif A

est un idéal si ∀a, b ∈ I, a + b ∈ I et ∀x ∈ A, x · a ∈ I.
Proposition 3.1.4. C est un code cyclique si PC est un idéal de F2 [X]
X n −1
.

Démonstration. Si PC est un idéal de F2 [X]

X n −1
alors ∀m ∈ C, Xm(X) ∈ PC
etXm(X) = σ(m)(X) ⇒ σ(m) ∈ C .
Inversement, si C est un code cyclique, σ k (m) ∈ C∀k ∈ N donc X k m(X) ∈
PC . Puisque C est un code linéaire, P (X)m(X) ∈ PC ∀P [X] ∈ XF2n[X]
−1
donc
PC est un idéal.

13
Dénition 3.1.5. Le polynôme générateur g(X) d'un code cyclique C est
le polynôme non nul unitaire de plus bas degré de C .
Proposition 3.1.6. Le polynôme générateur est unique.
Démonstration. Supposons que g1 et g2 soient deux polynômes générateurs
distincts et diérents de 0 de C . Alors, g1 - g2 est un polynôme de C de degré
strictement inférieur à celui de g1 et g2 , ce qui entraîne une contradiction.
Proposition 3.1.7. Tout mot du code est un multiple de g.
Démonstration. Soit m ∈ C . Par division euclidienne, on a :
m(X) = q(X)g(X)+r(X) avec q(X), r(X) ∈ F2 [X] et deg(r(X)) < deg(g(X)).
r(X) = q(X)g(X) − m(X) donc r est un mot du code d'après les proprié-
tés précédentes (multiple de g(X) et linéarité). Si r(X) 6= 0, cela contre-
dit l'hypothèse que g(X) soit le polynôme générateur. Donc, r(X) = 0 et
m(X) = q(X)g(X).
Proposition 3.1.8. g(X) divise X n − 1.
Démonstration. On sait que X k g(X) = g k (X) où g k (X) est le polynôme
obtenu en décalant les composantes de g(X)k fois vers la droite, c'est donc un
mot du code. Ce qui implique qu'il existe a(X) tel que X k g(X) = a(X)g(X)
et donc (X k + a(X))g(X) = X n − 1.
Dénition 3.1.9. Un idéal I de A est dit principal s'il existe i ∈ I tel que
I = {i ∗ a|a ∈ A}.
F 2 [X ] F2 [X]
C est donc un idéal principal de Xn −1 et C = {m(X)g(X)|m(X) ∈ Xn −1 }.

Proposition 3.1.10. dim(C) = n−deg(g(X)) et (g(X), Xg(X), ..., X n−1−deg(g(X)) g(X))

est une base de C .
Démonstration. Soit m ∈ C, deg(m(X)) ≤ n − 1 par dénition. Sim(X) =
q(X)g(X) alors deg(q(X)) ≤ n − 1 − deg(g(X)). Cela montre que m(X) est
une combinaison linéaire des polynômes g(X), Xg(X), ..., X n−1−deg(g(X)) g(X)).
Donc, dim(C) = n − deg(g(X)) et comme chaque combinaison linéaire
est de degré au plus n − 1, ces polynômes forment une famille libre de
F2 [X]
X n −1
.(X, Xg(X), ..., X n−1−deg(g(X)) ) est bien une base de C .
Dece fait, on en déduit que la matrice génératrice
 G liée à C est de la
a0 a1 · · · an−k 0 0 ··· 0
 0 a0 a1 · · · an−k 0 · · · 0 
forme  ..  ∈ Mk,n (F2 ), deg(g(X)) =
 
 . 
0 ··· ··· 0 a0 a1 · · · an−k

14
n − k.

Proposition 3.1.11. Soit C un code cyclique et g(X) son polynôme géné-

rateur de degré r, g(X) = a0 + a1 X + ...ar−1 X r−1 + X r . Alors, a0 = 1.
Démonstration. Supposons que a0 = 0.
g(X) = a1 X + ...an−1 X n−1 + X r
g(X) = X(a1 + ...an−1 X n−2 + X r−1 )
Si on décale g(X)n − 1 fois vers la droite (ou 1 fois vers la gauche), on obtient
le polynôme ci-dessus de degré < r ce qui génère une contradiction.

Dénition 3.1.12. On appelle polynôme de contrôle le polynôme h(X)

qui vérie g(X)h(X) = X n − 1.
Son existence est garantie par g(X) | X n − 1.
En outre, si m ∈ C et m(X) = q(X)g(X),

h(X)m(X) = h(X)g(X)q(X)
= (X n − 1)q(X)
F 2 [X ]
= 0 dans X n
−1
.
h(X) remplit bien un rôle similaire à celui de la matrice de contrôle ; on
considérera d'ailleurs
 la matrice de contrôle H associée. Si h(X) = b0 +b1 X +
hk hk−1 · · · h0 0 · · · 0
0 hk · · · h1 h0 · · · 0 
... + bk X , H =  ..
k
..  ∈ Mn−k,n (F2 ).
 
. .
0 0 · · · 0 hk · · · h0
On a bien H t G = 0.

3.2 Recherche des codes cycliques

Soit C un code cyclique. Puisque le polynôme générateur divise X n − 1,
rechercher les polynômes générateurs possibles pour un code de longueur n
revient à trouver les facteurs de X n − 1 à coecients dans F2 .
n−1
Soit α une racine primitive n-ième de l'unité, on a X n − 1 = (X − αi )
Q
i=0
dans C[X].

15
 Si g(X) est un polynôme générateur, il est de la forme g(X) = (X −αi )
Q
i∈Σ
où Σ est une partie convenable de Fn .

Proposition 3.2.1. Les coecients de g(X) = (X − αi ) sont dans F2 ssi

Q
i∈Σ
Σ est stable par multiplication par 2 modulo n.

Démonstration. Si g est à coecients dans F2 , chaque coecient de g est

stable par élévation au carré. Comme cette opération respecte aussi l'addi-
tion, on voit que g(X 2 ) = (g(X))2 . Ainsi, l'ensemble des racines de g est
stable par élévation au carré, ce qui signie que Σ est stable par multiplica-
tion par 2. Inversement, si Σ est stable par multiplication par 2 :

g(X 2 ) = (X 2 − αi )= (X 2 − α2i ) = (X − αi )2 = (g(X))2

Q Q Q
i∈Σ i∈Σ i∈Σ
et donc les coecients de g sont dans F2 .
La recherche de polynômes générateurs revient donc à trouver les parties
stables par multiplication par 2 de Fn . Soit j ∈ Fn , on note Σj la plus petite
partie stable contenant j. Alors, il existe un plus petit entier s > 0 tel que
2s j ≡ j[n], on peut ainsi prendre Σj ={j, 2j, ..., 2s−1 j} qui est bien stable par
multiplication par 2 modulo n.

Dénition 3.2.2. La classe cyclotomique de j (relative à 2 modulo n) est

Σj ={j2k mod n|k ∈ N}.

Le degré du polynôme irréductible associé gj = (X − αi ) est égal à

Q
i∈Σj
card(Σj ) = s.
Cherchons les codes cycliques de longueur 7 an d'illustrer tout cela.

Exemple : 2s j ≡ j[7]. Pour j = 1, s = 3 convient.

Σ1 = {1, 2, 4}. De même, pour j = 3, s = 3 convient à nouveau : Σ3 =
{3, 5, 6}
Enn pour j = 0, Σ0 = {0}.

X 7 − 1 peut donc être décomposé comme produit de 3 facteurs irréduc-

tibles :

 g0 = X − 1
g1 = (X − α)(X − α2 )(X − α4 )
g3 = (X − α3 )(X − α5 )(X − α6 )


16
 α étant une racine primitive 7-ième de l'unité.

On peut tester manuellement les polynômes de degré 3 se terminant par 1

(sinon 0 est une racine) à coecients dans F2 qui conviennent : X 3 +X 2 + 1 ;
X 3 + X + 1 ; X 3 + 1 et X 3 +X 2 + X + 1.
Les deux derniers admettent une racine en 1 et X 3 +1 = (X −1)(X 2 +X +1)
et X 3 + X 2 + X + 1 = (X − 1)3 , il n'y a donc que deux choix possibles.
Supposons que α soit racine primitive de P (X) = X 3 + X + 1, on obtient
plusieurs informations concernant α :
α3 = α + 1
α4 = α2 + α
α5 = α4 + 1
α6 = α2 + 1

g1 = (X − α)(X − α2 )(X − α4 )
= X 3 +X 2 ( α+α2 +α4 )+X(α3 +α5 +α6 )
= X 3 + X + 1.

De même, on trouve que g3 = X 3 + X 2 + 1 et X 7 − 1 = (X − 1)(X 3 +

X + 1)(X 3 + X 2 + 1).
On obtient ainsi 23 = 8 codes cycliques diérents :

Code nul.


 C0 = hX 7 + 1i
C1 = hX + 1i




C2 = hX 3 + X + 1i




C3 = hX 3 + X 2 + 1i


 C4 = h(X 3 + X + 1)(X + 1)i = hX 4 + X 3 + X 2 + 1i
C5 = h(X 3 + X 2 + 1)(X + 1)i = hX 4 + X 2 + X + 1i




C = h(X 3 + X + 1)(X 3 + X 2 + 1)i = hX 6 + X 5 + X 4 + X 3 + X 2 + X + 1i

 6


Ne change pas le mot.

C7 = h1i

Les code C2 et C3 ont pour paramètres (7, 4, 1), ce sont des codes de
Hamming. Le code C6 correspond au bit de répétition.

On peut déterminer les polynômes générateurs d'une autre façon :

Dénition 3.2.3. On appelle polynôme cyclotomique le polynôme Φn

n
déni par Φn (X) = (X − exp( 2kiπ )).
Q
n
k=1
k∧n=1
Proposition 3.2.4. X − 1 =
n
Φd (X).
Q
d|n

17
 n−1
Démonstration. On sait que X n − 1 = (X − αi ). De plus, {1, ...n} =
Q
i=0
{k ∈ {1, ...n}|k ∧ n = d}.
F
d|n
n
n d
n k
(X − αkd )
Q Q Q Q
X −1= (X − α ) =
d|n k=1 d|n k=1
k∧n=1 k∧( n
d
)=1
d nk
=
Q Q Q
(X − α d ) = Φd (X).
d|n k=1 d|n
k∧d=1

La dernière égalité venant du fait que si α est une racine primitive n-ième
n
de l'unité, α d est une racine primitive d-ième de l'unité.

Proposition 3.2.5. Les polynômes cyclotomiques sont à coecients dans Z.
Démonstration. On montre qu'ils sont à coecients entier par récurrence.
C'est vrai pour φ1 (X) = Q
X − 1. On suppose que c'est vrai jusqu'au rang
n − 1. On a X − 1 =
n
φd (X) = φn (X)h(X) dans C[X] où h(X) est
d|n
un polynôme à coecients entier par hypothèse de récurrence. En faisant
la division euclidienne dans Z[X] de X n − 1 par h(X) on a : X n − 1 =
g(X)h(X) + r(X) avec deg(r) < deg(h) et g(X) dans Z[X]. Par unicité de
la division euclidienne dans C[X], on a φn = g et donc φn est à coecient
entier.
Le calcul des polynômes cyclotomiques permet donc aussi de retrouver
les polynômes générateurs.

Nous allons désormais introduire une minoration de la distance minimale

d'un code cyclique.

Proposition 3.2.6. S'il existe des entiers a et s > 0 tels que contienne
P
a + 1, a + 2, ..., a + s, la distance minimale du code construit est ≥ s + 1.
Démonstration. Il faut montrer qu'un polynôme R ∈ F2 [X] de degré < n qui
a au plus s coecients non nuls (et donc de poids < s + 1) est identiquement
nul. Cela revient donc à montrer le lemme suivant :
Lemme Soient d1 , ...ds des entiers avec 0 P
≤ d1 < · · · < ds < n, et
λ1 , ..., λs des éléments de F2 . Posons R(X) = dj i
λj X . Si R(α ) = 0 pour
i = a + 1,...,a + s, alors tous les λj sont nuls.

18
Démonstration. Le déterminant des αidj est un déterminant de Vandermonde.
Mais comme α est une racine primitive n-ième de l'unité, les αdj sont deux
à deux distincts.

Pour le code cyclique de longueur 7 vu précédemment, contient {1, 2}

P
(ou {5, 6}), la distance minimale de ce code est donc ≥3.

Les diérents codes cycliques désormais déterminés, on peut passer à

l'étape du codage : il sut de multiplier la représentation polynomiale d'un
mot par le polynôme générateur modulo X n − 1.

Exemple : On prend g(X) = X 3 + X + 1 et m(X) = 1 + X + X 2 .

g(X)m(X) = (X 3 + X + 1)(1 + X + X 2 ) = 1 + X + X 5 .

3.3 Algorithme de décodage

De façon analogue aux codes linéaires, le décodage se fait par la détermi-
nation du syndrome.

Dénition 3.3.1. Le syndrome d'un mot S(m)(X) est le reste de la division

euclidienne de ce mot par le polynôme générateur modulo X n − 1.
Cette dénition vérie bien que si un mot appartient au code, son syn-
drome est nul.

Proposition 3.3.2. Soit C un code cyclique de longueur n et de dimension

k . Soit w(X) = q(X)g(X) + s(X), s(X) étant le syndrome de w(X). Alors,
le syndrome de Xw(X) est :
Xs(X) si deg(s(X)) < n − k − 1.
Xs(X) − g(X) si deg(s(X)) = n − k − 1.

Démonstration. Si deg(s(X)) < n − k − 1 alors deg(Xs(X)) < n − k =

deg(g(X)) et on a bien Xw(X) = Xq(X)g(X) + Xs(X) par unicité de la
division euclidienne.
Si deg(s(X)) = n − k − 1, s(X) = s0 + s1 X + ... + X n−k−1 . On note sb(X)=s0 +
s1 X + ... + X n−k−2 . De même, g(X) = g0 + g1 X + ... + X n−k et gb(X) =
g0 + g1 X + ... + X n−k−1 .

s(X)+X n−k = Xs(X)+g(X)− gb(X) = g(X)+(Xb

Xs(X) = Xb s(X)− gb(X))

19
et deg(Xbs(X) − gb(X)) < n − k − 1. Comme Xbs(X) = X(X) − X n−k et
gb(X) = g(X) − X , le syndrome de w(X) vaut bien Xs(X) − g(X).
n−k

Soit C un code cyclique de paramètres(n, k, dC ), g (X) son polynôme gé-

nérateur et w un mot erroné. Ainsi, w(X) = m(X) + e(X ) où m est un mot
du code et e l'erreur associée à w. On rappelle que le mot peut être corrigé si
w(e) ≤ eC = b dC2−1 c, w désignant le poids du mot (le nombre de composantes
non nulles). L'objectif du décodage est donc de déterminer le polynôme e(X).

Déterminons la forme de l'erreur. Soit e0 = (t s,0) où 0 désigne le vecteur

à k 0 et s le syndrome de w. Le degré de e0 (X) étant strictement inférieur
à celui du polynôme générateur par dénition, son syndrome est le même
que celui de e. De plus, si on suppose que w(s) ≤ eC alors w(e0 ) ≤ eC cela
implique que e0 = e car il n'existe qu'un seul vecteur de poids ≤ eC associé
à chaque syndrome. L'erreur est donc de la forme (t s,0).

On veut maintenant se ramener au cas où w(s) ≤ eC an de pouvoir

déterminer l'erreur. Supposons que e possède k 0 à la suite et que w(e) ≤ eC .
Alors, il existe i ∈ {0, 1, .., n − 1} tel que les k 0 de σ i (e) soient situés à la
n du mot. Ainsi, σ i (e) est de la forme(β ,0), β étant un vecteur de longueur
n-k ; donc deg(β (X))≤ n − k − 1 =deg(g(X)) − 1. Le syndrome de β(X)
est donc β(X) lui-même. Comme w(β(X)) ≤ eC , w(si (X)) ≤ eC où si (X)
est le syndrome de X i e(X) modulo X n − 1. D'après l'argument précédent,
e(X)X i = (t si ,0) donc e(X) = X n−i (t si ,0).

On peut donc expliciter l'algorithme de décodage :

1. On détermine le syndrome de w(X) par division euclidienne.

2. On prend i = 0 et si w(si (X)) ≤ eC , e(X) = X n−i (si ,0) et
m(X) = w(X) − e(X).
3. Sinon, i = i + 1 et on calcule si (X) ;on recommence jusqu'à ce que i = n.

Si i = n la correction est impossible.

Exemple Soit C un code cyclique de paramètres (15, 7, 5) de polynôme

générateur g(X) = X 8 + X 7 + X 6 + X 4 + 1 ; sa capacité de correction est
donc de 2.
Prenons m(X) = 1 + X + X 3 et w(X) = m(X)g(X).
w(X) = (1 + X + X 3 )(1 + X 4 + X 6 + X 7 + X 8 ) = 1 + X + X 3 + X 4 + X 5 +
X 6 + X 7 + X 10 + X 11 .

20
 Modions deux de ses composantes, disons la quatrième et la huitième et
notons ce nouveau polynôme z(X) = 1 + X + X 3 + X 5 + X 6 + X 7 + X 8 +
X 10 + X 11 .
Par division euclidienne, on obtient z(X) = (X 3 + X)(1 + X 4 + X 6 + X 7 +
X 8 ) + X 7 + X 6 + 1.
Le syndrome est donc s(X) = X 7 + X 6 + 1 de poids 3 > 2.

deg(s(X)) = 7 = deg(g(X)) − 1 donc s1 (X) = Xs(X) − g(X).

s1 (X) = X 8 + X 7 + X − (X 8 + X 7 + X 6 + X 4 + 1) = X 6 + X 4 + X + 1.
s2 (X) = X(X 6 + X 4 + X + 1) = X 7 + X 5 + X 2 + X .
s3 (X) = X 8 +X 6 +X 3 +X 2 −(X 8 +X 7 +X 6 +X 4 +1) = X 7 +X 4 +X 3 +X 2 +1.
..
.
..
.
s10 (X) = X 7 + X 6 + X 5 .
s11 (X) = X 8 + X 7 + X 6 − (X 8 + X 7 + X 6 + X 4 + 1) = X 4 + 1.

w(s11 (X)) = 2 , c'est ce que l'on recherchait.

e(X) = X n−11 s11 (X) = X 4 (X 4 + 1) = X 8 + X 4 .

Les erreurs sont bien en position 4 et 8, là où on les avait placées. Il sut

ensuite de diviser le mot obtenu par le polynôme générateur an de
retrouver le mot initial.
Toutefois, l'algorithme de décodage n'aurait pas fonctionné si e(X) ne
comportait pas au moins k zéros à la suite (ce qui arrive forcément pour un
code de longueur 15 et de dimension 7 lorsqu'il n'y a que deux erreurs).

Dénition 3.3.3. Un "burst" de longueur λ est un mot de Fn2 dont les

composantes non nulles sont connées dans λ positions consécutives.

Exemple m = (00100110000) est un "burst"de longueur 5 dans F11

2 .

Un code est dit λ-burst-correcteur s'il peut corriger toutes les erreurs de
burst< λ.

Proposition 3.3.4. Tout code cyclique peut détecter les erreurs "burst" de
longueur ≤ deg(g(X)).
Démonstration. Montrons qu'il n'existe pas d'erreur "burst" de longueur ≤
deg(g(X)) appartenant au code.

21
Par dénition, ce "burst" est de la forme e(X) = X i β(X) avec deg(β(X)) ≤
deg(g(X)) et β(X) 6= 0. Le coecient constant de g(X) est 1 donc g(X) - X i .
Si e(X) est un mot du code alors g(X) - X i β(X) donc g(X) | β(X) mais
deg(β(X)) ≤ deg(g(X)) d'où la contradiction.

Les codes cycliques permettent donc non seulement de corriger eC er-

reurs mais aussi d'en détecter deg(g(X)) pour peu qu'elles apparaissent au
bon endroit ; c'est ce qui explique leur popularité ; ils sont notamment utilisés
dans certains codes barres, dans les disques durs an de corriger les erreurs
provoquées par les rayures ou bien encore lors du vol spatial de Voyager 1 et 2

22
Conclusion
Nous avons pu voir quels étaient les mécanismes qui régissaient le codage
et le décodage d'informations binaires, mais ce n'était qu'un bref aperçu
du monde des codes correcteurs d'erreurs : les codes BCH , Reed-Solomon,
de Golay sont tous d'autres codes fréquemment utilisés. De plus, nous ne
sommes pas penchés sur le cas de l'eacement d'un bit qui aurait ajouté une
nouvelle dimension à notre sujet.
La protection de l'information reste un secteur en pleine expansion dont
l'avancement ore des possibilités insoupçonnées dans de multiples domaines
et qui continue de donner naissance à de nouvelles théories.

23
4 Annexes
4.1 Bibliographie
Ce travail se base principalement sur le livre de Michel Demazure, Cassini,
Cours d'algèbre. Primalité. Divisibilité. Codes.
Et quelques cours disponibles en ligne :
1. Massoud Malek , Linear Cyclic Codes, http://www.mcs.csueastbay.
edu/~malek/Class/Cyclic.pdf
2. A.A. Pantchichkine, Mathématiques des codes correcteurs d'erreurs
https://www-fourier.ujf-grenoble.fr/~panchish/04cc
3. Pierre Abbrugati, Introduction aux codes correcteurs d'erreurs, http:
//www.lirmm.fr/~chaumont/download/cours/codescorrecteur/Cours_
Pierre_Abbrugiati.pdf
4. Pierre Wassef, Cours d'arithmétique http://www.edu.upmc.fr/maths/
wassef_LM220/documents/arithmetique.pdf

24
4.2 Code SAGE
Hamming :

In [1]: from PIL import Image, ImageFilter;

import scipy.ndimage
import matplotlib.image
import matplotlib.pyplot
import numpy as np

In [3]: im = Image.open('Mario.png')

In [5]: data = list(im.getdata());

In [6]: data3 = np.array(data, dtype=np.uint8

In [7]: data[4]=[0]*90000

In [8]: data4=np.unpackbits(data3)

In [10]: data5=list(data4)

In [26]: len(data5)

Out[26]: 2160000

La première étape consiste à extraire l'information contenue dans l'image

(de taille 300*300) qui est sous la forme de triplet de nombres compris entre
0 et 255, chaque triplet correspondant à la couleur d'un pixel. Il faut ensuite
la convertir dans un format où elle pourra être encodée par un code binaire,
chaque valeur est donc convertie en un vecteur de 8 bits. On obtient donc
8*3*300*300=2160000 éléments à coder que l'on place dans une liste

In [2]: C=codes.HammingCode(GF(2),7); C

Out[2]: [127, 120] Hamming Code over GF(2)

In [12]: Z=GF(2)^120
Y=GF(2)^127

In [11]: datac=[0]*2160000*7

25
 Ensuite, on crée un code de Hamming de paramètres (120,127) à l'aide du
logiciel ; on encodera donc les bits par groupe de 120 (2160000/120=18000) et
on obtiendra des mots de longueur 127. On prépare un tableau qui contiendra
des vecteurs à 127 éléments qui appartiennent à F2 .

In [13]: p=0.01;
Chan=channels.QarySymmetricChannel(GF(2)^127,p);

On introduit 1% d'erreurs, ce qui est considérablement élevé mais met

bien en évidence la diérence d'ecacité entre les deux codes.

In [14]: for i in range(0,17999):

P=Z(data5[120*i:120*(i+1)])
X=C.encode(P)
datac[127*i:127*(i+1)]=X

On peut maintenant passer à l'encodage des vecteurs.

In [15]: datae=[0]*2160000*7

In [16]: for i in range(0,17999):

U=Y(datac[127*i:127*(i+1)])
K=Chan.transmit(U)
datae[127*i:127*(i+1)]=K

On ajoute des erreurs sur chaque mot de longueur 127.

In [17]: datam=[0]*2160000

In [18]: for i in range(0,17999):

P=Y(datae[127*i:127*(i+1)])
X=C.decode_to_message(P)
datam[120*i:120*(i+1)]=X

La fonction de décodage présente dans le logiciel permet de retrouver nos

vecteurs à 120 éléments pour peu qu'ils n'aient pas été trop modiés.

In [19]: datap=np.array(datam,dtype=np.uint8)

In [20]: datar=np.packbits(datap)

In [21]: datar=datar.reshape(90000,3)

26
In [22]: datah=tuple(map(tuple,datar))

On reconvertit chaque vecteur de 8 éléments en un nombre entre 0 et 255

et on regroupe ces nombres par triplet (il y a donc 90000 triplets de nombres).
On remet enn tous ces triplets dans une liste.

In [23]: imf = Image.new("RGB",(300,300),"white")

In [24]: imf.putdata(datah)

On crée une image vierge et l'on y insère les données obtenues.

In [25]: imf

Out[25]:

On obtient une image quelque peu diérente de la version originale mais

parfaitement reconnaissable.

27
 Code linéaire aléatoire :

In [1]: from PIL import Image, ImageFilter;

import scipy.ndimage
import matplotlib.image
import matplotlib.pyplot
import numpy as np

In [2]: C=codes.random_linear_code(GF(2),127,120); C

On utilise cette fois un code linéaire généré aléatoirement

Out[2]: [127, 120] linear code over GF(2)

In [3]: im = Image.open('Mario.png')

In [4]: data = list(im.getdata());

In [5]: data3 = np.array(data, dtype=np.uint8)

In [6]: data[4]=[0]*90000
data4=np.unpackbits(data3)

In [7]: data5=list(data4)
datac=[0]*2160000*7
datae=[0]*2160000*7
datam=[0]*2160000

In [8]: Z=GF(2)^120
Y=GF(2)^127

In [9]: p=0.01;
Chan=channels.QarySymmetricChannel(GF(2)^127,p);
Chan

Out[9]: q-ary symmetric channel with error probability 0.0100000000000000, of inp

In [10]: for i in range(0,17999):

P=Z(data5[120*i:120*(i+1)])
X=C.encode(P)
datac[127*i:127*(i+1)]=X

28
In [11]: for i in range(0,17999):
U=Y(datac[127*i:127*(i+1)])
K=Chan.transmit(U)
datae[127*i:127*(i+1)]=K
In [12]: for i in range(0,17999):
P=Y(datae[127*i:127*(i+1)])
X=C.decode_to_message(P)
datam[120*i:120*(i+1)]=X
In [13]: datap=np.array(datam,dtype=np.uint8)
datar=np.packbits(datap)
datar=datar.reshape(90000,3)
In [ ]: datah=tuple(map(tuple,datar))
In [15]: imf = Image.new("RGB",(300,300),"white")
imf.putdata(datah)
In [16]: imf
Out[16]:

29
 On obtient une image qui bien que reconnaissable est d'une très mauvaise
qualité.

30