T. D. Codes correcteurs d’erreurs.

POLYTECH. 4ième année Enseignants : Alexis Bonnecaze

AIX-MARSEILLE UNIVERSITÉ Odile Papini
Année universitaire 2019/2021

Feuille de T. D. 3 corrigée : Codes cycliques

Exercice 1 : code cyclique

I)
Soit C un code cyclique de longueur 15 sur IF2 de polynôme générateur
g(x) = x4 + x + 1.

1) La dimension du code est n − deg(g(x)) = 15 − 4 = 11.

2) Le polynôme générateur de l’orthogonal du code C est xk h(−1 ) où h(x)

est le polynôme de contrôle, c’est à dire qu’il est tel que x15 − 1 =
g(x).h(x).
La division de x15 − 1 par g(x) donne
h(x) = x11 + x8 + x7 + x5 + x3 + x2 + x + 1 et
x11 h(−1 ) = x11 + x10 + x9 + x8 + x6 + x4 + x3 + 1.

3) La matrice de contrôle du code C est

1 0 0 1 1 0 1 0 1 1 1 1 0 0 0
 
 0 1 0 0 1 1 0 1 0 1 1 1 1 0 0 
H=
 
0 0 1 0 0 1 1 0 1 0 1 1 1 1 0

 
0 0 0 1 0 0 1 1 0 1 0 1 1 1 1

4) La distance minimale du code C est d = 3. Il n’existe pas de mot de

poids 1 car il n’y a pas de colonne nulle dans H. Il n’y a pas de mot de
poids 2 car il n’y a pas deux colonnes égales dans H. En revanche, il y
a des mots de poids 3 il existe des colonnes de H combinaisons linéaires
de 2 colonnes de H. Par exemple, c5 = c1 + c2 .

Exercice 2 : code de Hamming

Nous avons montré (voir feuille de TD 2) que le code de Hamming sur IF2
est un code de longueur 2m − 1, de dimension 2m − 1 − m et de distance min-
imale d = 3, admettant pour matrice de contrôle une matrice dont les 2m − 1

1
colonnes sont tous les m-uplets non nuls de IF2 . Soit α un élément primitif de
m
IF2m alors les éléments du corps IF2m , c’est à dire 1, α, α2 , · · · , α2 −2 peuvent
être représentés par les m-uplets non nuls de IF2 .

1) Montrer qu’un code de Hamming est un code cyclique de polynôme

gérateur g(x) = M (1) (x) où M (1) (x) est le polynôme minimal de α.
m
Soit IFm 2
2 = {0, 1, α, α , · · · , α
2 −2
}, les éléments non nuls de IFm
2 peu-
vent être représentés par des m-uplets distincts non nuls et la matrice
H du code de Hamming peut s’écrire :
 m −2

H= 1 α α2 · · · α2

où chaque m-uplet est remplacé par un élément de IF2m .

Soit c = (c0 , · · · cn−1 ) appartient au code de Hamming si et seulement
si Hct = 0 si et seulement si Σn−1 i
i=0 ci α = 0 si et seulement si c(α) = 0.

Par définition un polynôme minimal de α sur IF2 est tel que c’est un
polynôme de plus petit degré à coefficients dans IF2 tel que M (α) = 0.
Soit c(α) = 0 on a M (x) divise c(x). En effet, c(x) = M (x).a(x) + r(x)
avec deg(r(x)) < deg(M (x)).
c(α) = M (α).a(α) + r(α)
0 = 0 + r(α)
si r(α) = 0, r(x) est un polynôme de degré inférieur au degré de M (x)
ayant α pour racine. Ce qui contredit la définition du polynôme mini-
mal donc r(x) = 0 et donc M (x) divise c(x).

2) Donner une matrice génératrice du code de Hamming sur IF2 est un

code de longueur 2m − 1.
 
M (x) 0 ··· ··· ··· 0
0 xM (x) 0 ··· ··· 0
 
 
0 x2 M (x)
 
G= 
 0 0 ··· 0 


 0 0 0 ··· ··· 0 

n−m−1
0 0 0 ··· 0 x M (x)

2
 3) Lorsque m = 3 vérifier que les lignes de H sont orthogonales aux lignes
de G.
IF32 = {0, 1, α, α2 , α3 , α4 , α5 , α6 } et M (x) = x3 + x + 1.

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

Exercice 3 : corps fini

On souhaite décomposer x8 − 1 sur IF3 .

1) On considère le corps IF3 , le corps à trois éléments. Construire les

tables d’addition et de multiplication de ce corps.
+ 0 1 2 × 0 1 2
0 0 1 2 0 0 0 0
1 1 2 0 1 0 1 2
2 2 0 1 2 0 2 1

2) Le sur-corps de décomposition de x8 − 1 sur IF3 est tel que m est le

plus petit entier tel que n divise 3m − 1. Donc m = 2 et le corps de
décomposition est F32 = F9 .
F9 = {0, 1, α, α2 , α3 , α4 , α5 , α6 , α7 }.
Le corps F9 est engendré par le polynôme primitif x2 + x + 2 et
α2 = 2α + 1
α3 = 2α + 2
α4 = 2
α5 = 2α
α6 = α + 2
α7 = α + 1.

3) Décomposer x8 − 1 sur IF3 .

On cherche les classes cyclotomiques i, i.3, i.32 , · · · (mod8)

3
 classe de 0 : → 0 (x − β 0 )
classe de 1 : → 1, 3 (x − β 1 )(x − β 3 )
classe de 2 : → 2, 6 (x − β 2 )(x − β 6 )
classe de 4 : → 4 (x − β 4 )
classe de 5 : → 5, 7 (x − β 5 )(x − β 7 )
On cherche ensuite à quel élément de F9 correspond β, il est tel que
m
β 3 −1 = αns , ns divise 3m − 1, ici n = 1 et β = α.
(x − β 0 ) = (x − 1)

(x − β 1 )(x − β 3 ) = (x − α1 )(x − α3 ) en faisant les calculs dans F9 , on

trouve x2 − 2x + 2.

(x − β 2 )(x − β 6 ) = (x − α2 )(x − α6 ) en faisant les calculs dans F9 , on

trouve x2 + 1.

(x − β 4 ) = (x − α4 ) en faisant les calculs dans F9 , on trouve x − 2.

(x − β 5 )(x − β 7 ) = (x − α5 )(x − α7 ) en faisant les calculs dans F9 , on
trouve x2 − x + 2.

Donc x8 − 1 = (x − 1)(x2 − 2x + 2)(x2 + 1)(x − 2)(x2 − x + 2).

4) Quels sont les codes cycliques de longueur 8 sur IF3 ?

Les polynômes générateurs des codes cycliques de longueur 8 sur IF3 sont
classés par degré dans les tables ci-dessous.

1 2 3 4
(x − 1) (x2 − 2x + 2) (x − 1)(x2 − 2x + 2) (x − 2)(x − 1)(x2 − 2x + 2)
(x − 2) (x2 − x + 2) (x − 1)(x2 − x + 2) (x − 2)(x − 1)(x2 − x + 2)
(x2 + 1) (x − 1)(x2 + 1) (x − 2)(x − 1)(x2 + 1)
(x − 1)(x − 2) (x − 2)(x − 2x + 2) (x2 − 2x + 2)(x2 − x + 2)
2

(x − 2)(x2 − x + 2) (x2 − 2x + 2)(x2 + 1)

(x − 1)(x2 + 1) (x2 − x + 2)(x2 + 1)

4
 5 6
2 2
(x − 1)(x − 2x + 2)(x − x + 2) (x − 2x + 2)(x − x + 2)(x2 + 1)
2 2

(x − 1)(x2 − 2x + 2)(x2 + 1) (x2 − 2x + 2)(x2 − x + 2)(x − 1)(x − 2)

(x − 1)(x2 − 2x + 2)(x2 + 1) (x2 − 2x + 2)(x2 + 1)(x − 1)(x − 2)
(x − 2)(x2 − 2x + 2)(x2 − x + 2) (x2 − x + 2)(x2 + 1)(x − 1)(x − 2)
2 2
(x − 2)(x − 2x + 2)(x + 1)
(x − 2)(x2 − 2x + 2)(x2 + 1)

7
(x − 2x + 2)(x − x + 2)(x2 + 1)(x − 1)
2 2

(x2 − 2x + 2)(x2 − x + 2)(x2 + 1)(x − 2)

Exercice 4 : code BCH

Soit le polynôme sur IF2 , g(x) = x8 + x7 + x6 + x4 + 1.

1) g(x) est un polynôme générateur d’un code cyclique C de longueur 15

car g(x) divise x15 − 1, x15 − 1 = (x8 + x7 + x6 + x4 + 1)(x7 + x6 + x4 + 1).

2) Quelle est la dimension de C ?

dim(C) = n − deg(g(x)) = 7

3) Montrer que C est un code BCH.

g(x) = x8 + x7 + x6 + x4 + 1 = (x4 + x + 1)(x4 + x3 + x2 + x + 1),
(1)
or x4 + x + 1 est le polynôme minimal de α, noté M(x) , α ∈ F16 , et
(3)
x4 + x3 + x2 + x + 1 est le polynôme minimal de α3 , noté M(x) , α3 ∈ F16 .
(1)
M(x) a pour racines : α, α2 , α4 , α8 .
(3)
M(x) a pour racines : α3 , α6 , α9 , α12 .
Il y a 4 racines dont les exposants sont des entiers consécutifs, donc
δ − 1 = 4, c’est un code BCH de distance construite δ = 5.

4) Quelle la distance construite de C ?

δ = 5.

5
 5) Quelle la distance minimale de C ? Quelle est sa capacité de correc-
tion ?
δ = d = 5 car g(x) = x8 + x7 + x6 + x4 + 1 permet de construire un
mot de poids 5.
La capacité de correction de C est e = b(d − 1)/2c.

Exercice 5 : code Reed-Solomon

Le but de cet exercice est de construire un code de Reed-Solomon de longueur
7 et de distance minimale 5, noté C.

1) Les paramètres d’un code de Reed-Solomon sont n = 2m − 1, k =

2m − 1 − r, d = r + 1.

n = 7 donc m = 3 et C est un code de Reed-Solomon sur IF8 engendré

par le polynôme primitif f (x) = x3 + x + 1.
x7 − 1 = (x − 1)(x − α)(x − α2 )(x − α3 )(x − α4 )(x − α5 )(x − α6 ) sur
IF8 .

On souhaite un code de Reed-Solomon avec d = 5 donc r = 4 et

k = 7 − 4 = 3 donc deg(g(x) = n − k = 4 donc lepolynôme générateur
du code C estg(x) = (x − α)(x − α2 )(x − α3 )(x − α4 ) et g(x) = x4 +
α3 x3 + x2 + αx + α3 .

2) La matrice génératrice du code C.

α3 α 1 α3 1 0 0
 

G =  0 α3 α 1 α3 1 0 


0 0 α3 α 1 α3 1

3) Les paramètres du code, noté IC, qui est l’image binaire du code C.
Pour l’image binaire : 0 est remplacé par 000, 1 est remplacé par 100,
α est remplacé par 010, · · ·.
La longueur de IC est n = 21, la dimension de IC est k = 9.

4) Le nombre de mots du code IC est 29 .

6
 PS: A toutes fins utiles on rappelle que le corps IF9 est engendré par le
polynôme primitif f (x) = x2 + x + 2 et que le corps IF16 est engendré par le
polynôme primitif f (x) = x4 + x + 1.