Codes Linèaire sur les Anneaux Finis

Projet de fin d’études

Présenté par : Ilham el harrak

Sous la direction du Pr : ABDLKARIM BOUA

24 juin 2025

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 1 / 92

 Plan

1. Préliminaires
I Généralitées
I Anneau de galois
I Modules
[Link]éorie des Codes - Codes Correcteures
I Généralitées
I Code Linèaire
I Paramétres d’un code linèaire
I Codage par Multiplication Matrice-Vecteur

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 2 / 92

 Plan

1. Préliminaires
I Généralitées
I Anneau de galois
I Modules
[Link]éorie des Codes - Codes Correcteures
I Généralitées
I Code Linèaire
I Paramétres d’un code linèaire
I Codage par Multiplication Matrice-Vecteur

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 2 / 92

 Plan

1. Préliminaires
I Généralitées
I Anneau de galois
I Modules
[Link]éorie des Codes - Codes Correcteures
I Généralitées
I Code Linèaire
I Paramétres d’un code linèaire
I Codage par Multiplication Matrice-Vecteur

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 2 / 92

 Plan

I Decodage par Multiplication Matrice-Vecteur

I Exemple d’application
4. Construction d’un Code Linèaire sur un Anneau fini
I Codes Cyclique
I Codes BCH
I Codes Goppa

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 3 / 92

 Plan

I Decodage par Multiplication Matrice-Vecteur

I Exemple d’application
4. Construction d’un Code Linèaire sur un Anneau fini
I Codes Cyclique
I Codes BCH
I Codes Goppa

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 3 / 92

 Préliminaires

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 4 / 92

Généralitées

définition
Un anneau est un ensemble A muni de deux lois de composition internes + et × vérifiant
les conditions suivantes
1 Le couple (A, +) est un groupe abélien, et l’élément neutre est noté 0A .
2 La loi × est associative et distributive à gauche et à droite par rapport à la loi +.
3 La loi × possède un élément neutre noté 1A .

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 5 / 92

Généralitées
Définitions
-Un sous-ensemble I d’un anneau commutatif A est appelé idéal si et seulement si :
1 I est un sous-groupe de (A, +),
2 ∀ϑ ∈ A et ∀x ∈ I, on a ϑx ∈ I.
-Un idéal p ⊂ A est dit premier si pour tout a, b ∈ A, on a :

ab ∈ p =⇒ a ∈ p ou b ∈ p.

-Soit I un idéal principal d’un anneau A telque I = hϑi ;

1 S’il existe un entier n 6= 0 tel que ϑn = 0, alors l’élément ϑ est dit nilpotent.
2 L’ensemble des éléments nilpotents de A est appelé le Nilradical de A et noté
Nil(A).

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 6 / 92

Généralitées
Définitions
-Un sous-ensemble I d’un anneau commutatif A est appelé idéal si et seulement si :
1 I est un sous-groupe de (A, +),
2 ∀ϑ ∈ A et ∀x ∈ I, on a ϑx ∈ I.
-Un idéal p ⊂ A est dit premier si pour tout a, b ∈ A, on a :

ab ∈ p =⇒ a ∈ p ou b ∈ p.

-Soit I un idéal principal d’un anneau A telque I = hϑi ;

1 S’il existe un entier n 6= 0 tel que ϑn = 0, alors l’élément ϑ est dit nilpotent.
2 L’ensemble des éléments nilpotents de A est appelé le Nilradical de A et noté
Nil(A).

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 6 / 92

Généralitées
Définitions
-Un sous-ensemble I d’un anneau commutatif A est appelé idéal si et seulement si :
1 I est un sous-groupe de (A, +),
2 ∀ϑ ∈ A et ∀x ∈ I, on a ϑx ∈ I.
-Un idéal p ⊂ A est dit premier si pour tout a, b ∈ A, on a :

ab ∈ p =⇒ a ∈ p ou b ∈ p.

-Soit I un idéal principal d’un anneau A telque I = hϑi ;

1 S’il existe un entier n 6= 0 tel que ϑn = 0, alors l’élément ϑ est dit nilpotent.
2 L’ensemble des éléments nilpotents de A est appelé le Nilradical de A et noté
Nil(A).

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 6 / 92

Généralitées

Propriété

L’intersection de tous les idéaux premiers de A est le nilradical de A.

Lemme : Tout ensemble

\ non vide inductif admet un élément maximal.
Preuve : Soit x ∈ p, donc x appartient à tous les idéaux premiers de A.
p

Montrons que x est nilpotent.

Supposons par l’absurde que x n’est pas nilpotent, donc ∀n ≥ 1, x n 6= 0.
Considérons l’ensemble

S = {I ⊆ A | I est un idéal et x n ∈
/ I, ∀n ≥ 1}.

Cet ensemble est non vide car (0) ∈ S.

Par le lemme de Zorn, il existe un idéal maximal m dans S.
ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 7 / 92
Généralitées

Propriété

L’intersection de tous les idéaux premiers de A est le nilradical de A.

Lemme : Tout ensemble

\ non vide inductif admet un élément maximal.
Preuve : Soit x ∈ p, donc x appartient à tous les idéaux premiers de A.
p

Montrons que x est nilpotent.

Supposons par l’absurde que x n’est pas nilpotent, donc ∀n ≥ 1, x n 6= 0.
Considérons l’ensemble

S = {I ⊆ A | I est un idéal et x n ∈
/ I, ∀n ≥ 1}.

Cet ensemble est non vide car (0) ∈ S.

Par le lemme de Zorn, il existe un idéal maximal m dans S.
ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 7 / 92
Généralitées
On peut montrer que cet idéal maximal m est un idéal premier ne contenant aucun x n . Cela
contredit le fait que x appartient à tous les idéaux premiers.
Ainsi, x doit être nilpotent, donc
\
p ⊆ Nil(A).
p idéal premier

Inversement, soit x ∈ Nil(A), donc x n = 0 pour un certain n.

Puisque tout idéal premier est un idéal propre, il contient 0, donc x n = 0 ∈ p.
Or, dans un idéal premier, si x n ∈ p, alors x ∈ p.
Donc \
Nil(A) ⊆ p.
p idéal premier

Par conséquent, \
p = Nil(A).
p idéal premier
ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 8 / 92
Généralitées
On peut montrer que cet idéal maximal m est un idéal premier ne contenant aucun x n . Cela
contredit le fait que x appartient à tous les idéaux premiers.
Ainsi, x doit être nilpotent, donc
\
p ⊆ Nil(A).
p idéal premier

Inversement, soit x ∈ Nil(A), donc x n = 0 pour un certain n.

Puisque tout idéal premier est un idéal propre, il contient 0, donc x n = 0 ∈ p.
Or, dans un idéal premier, si x n ∈ p, alors x ∈ p.
Donc \
Nil(A) ⊆ p.
p idéal premier

Par conséquent, \
p = Nil(A).
p idéal premier
ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 8 / 92
Généralitées

Propriété

Un anneau local n’a qu’un seul idéal maximal nilpotent.

Preuve : Soit A un anneau fini, alors il admet un nombre fini d’idéaux premiers
{P1 , P2 , . . . , Ps } donc A/Pi , 1 ≤ i ≤ s sont des anneaux intègres. Or un anneau intègre fini est
un corps, donc les Pi sont des idéaux maximaux pour 1 ≤ i ≤ s. Ce qui conduit à
s
\
Nil(A) = Pi = P.
i=1

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 9 / 92

Généralitées

Propriété

Un anneau local n’a qu’un seul idéal maximal nilpotent.

Preuve : Soit A un anneau fini, alors il admet un nombre fini d’idéaux premiers
{P1 , P2 , . . . , Ps } donc A/Pi , 1 ≤ i ≤ s sont des anneaux intègres. Or un anneau intègre fini est
un corps, donc les Pi sont des idéaux maximaux pour 1 ≤ i ≤ s. Ce qui conduit à
s
\
Nil(A) = Pi = P.
i=1

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 9 / 92

Généralitées

Définition
Un anneau qui posséde un unique idéal maximal est appelé anneau local commutatif.
Cet idéal est alors constitué de l’ensemble des éléments non inversibles.
Par conséquent, les assertions suivantes sont équivalentes :
1 A a exactement un idéal maximal.
2 A est un anneau local.
3 Les diviseurs de zéro de A sont contenus dans un idéal propre.
4 Les diviseurs de zéro de A forment un idéal.
5 Les diviseurs de zéro de A forment un groupe commutatif additif.
6 Pour tout x dans A, l’un des deux éléments de l’ensemble {x , 1 + x } est inversible.

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 10 / 92

Généraltées

Définition - Anneaux quotients

Soit Fq un corps fini à q éléments, et Fq [x ] l’anneau des polynômes à coefficients dans

Fq .
L’anneau quotient Fq [x ]/(x n − 1) est l’ensemble des classes d’équivalence de polynômes
modulo le polynôme x n − 1.
Formellement, pour deux polynômes f (x ), g(x ) ∈ Fq [x ], on dit que f est équivalent à g
modulo x n − 1 si et seulement si :

f (x ) ≡ g(x ) (mod x n − 1) ⇐⇒ (f − g)(x ) = h(x )(x n − 1),

avec h(x ) ∈ Fq [x ].
Chaque classe d’équivalence est représentée par un unique polynôme de degré strictement
inférieur à n.

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 11 / 92

Généraltées

lemme : Soit I un idéal dans Fq [x ]/(x n − 1), et soit g(x ) un polynôme unitaire de degré
minimal tel que [g(x )] ∈ I. Pour tout polynôme f (x ) vérifiant [f (x )] ∈ I, alors g(x ) divise f (x ).
Preuve de lemme :
On effectue la division euclidienne de f (x ) par g(x ) dans Fq [x ] :

f (x ) = q(x )g(x ) + r (x ),
où deg(r (x )) < deg(g(x )) ou r (x ) = 0. La minimalité du degré de g(x ) garantit que le reste
r (x ) doit être nul si [f (x )] ∈ I. Ainsi, g(x ) divise f (x ).

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 12 / 92

Généraltées

lemme : Soit I un idéal dans Fq [x ]/(x n − 1), et soit g(x ) un polynôme unitaire de degré
minimal tel que [g(x )] ∈ I. Pour tout polynôme f (x ) vérifiant [f (x )] ∈ I, alors g(x ) divise f (x ).
Preuve de lemme :
On effectue la division euclidienne de f (x ) par g(x ) dans Fq [x ] :

f (x ) = q(x )g(x ) + r (x ),
où deg(r (x )) < deg(g(x )) ou r (x ) = 0. La minimalité du degré de g(x ) garantit que le reste
r (x ) doit être nul si [f (x )] ∈ I. Ainsi, g(x ) divise f (x ).

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 12 / 92

Généralitées

Thérème
Soit I un idéal dans Fq [x ]/(x n − 1). Les affirmations suivantes sont vraies :
1 Il existe un unique polynôme unitaire g(x ) de degré minimal tel que [g(x )] ∈ I.
2 I est un idéal principal engendré par [g(x )].
3 g(x ) divise x n − 1 dans Fq [x ].

Preuve :
1- Supposons qu’il existe un autre polynôme unitaire h(x ) de degré minimal tel que [h(x )] ∈ I.
Par l’Affirmation, g(x ) divise h(x ). Comme g(x ) et h(x ) ont le même degré minimal, cela
implique que h(x ) = cg(x ). De plus, puisque h(x ) et g(x ) sont unitaires, on a nécessairement
h(x ) = g(x ). Ainsi, il existe un unique polynôme unitaire g(x ) de degré minimal tel que
[g(x )] ∈ I.

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 13 / 92

Généralitées

Thérème
Soit I un idéal dans Fq [x ]/(x n − 1). Les affirmations suivantes sont vraies :
1 Il existe un unique polynôme unitaire g(x ) de degré minimal tel que [g(x )] ∈ I.
2 I est un idéal principal engendré par [g(x )].
3 g(x ) divise x n − 1 dans Fq [x ].

Preuve :
1- Supposons qu’il existe un autre polynôme unitaire h(x ) de degré minimal tel que [h(x )] ∈ I.
Par l’Affirmation, g(x ) divise h(x ). Comme g(x ) et h(x ) ont le même degré minimal, cela
implique que h(x ) = cg(x ). De plus, puisque h(x ) et g(x ) sont unitaires, on a nécessairement
h(x ) = g(x ). Ainsi, il existe un unique polynôme unitaire g(x ) de degré minimal tel que
[g(x )] ∈ I.

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 13 / 92

Généralitées

2- Supposons [f (x )] ∈ I, alors par l’affirmation g(x ) divise f (x ). Par conséquent [g(x )] divise
[f (x )], ce qui signifie que [f (x )] = [g(x )][q(x )] pour un certain [q(x )] ∈ Fq [x ]/(x n − 1). On a
donc I ⊆ h[g(x )]i.
Réciproquement, soit [h(x )] ∈ h[g(x )]i. Alors [h(x )] = [g(x )][r (x )] pour un certain
[r (x )] ∈ Fq [x ]/(x n − 1). Comme [g(x )] ∈ I et que I est un idéal, on a [h(x )] ∈ I. Ainsi
h[g(x )]i ⊆ I.
On conclut que A = h[g(x )]i, donc I est un idéal principal engendré par [g(x )].
3- Remarquons que [x n − 1] = 0 ∈ A, donc par l’affirmation, g(x ) doit diviser x n − 1 dans Fq [x ].

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 14 / 92

Anneaux de Galois
Définition
Si A est commutatif, unitaire, et que l’ensemble de ses diviseurs de zéro est de la forme
pA, où p est un nombre premier, alors A est un anneau de Galois.

Remarques :
a. Les corps de Galois peuvent donc être considérés comme des anneaux de Galois ne
contenant aucun diviseur de zéro. L’exemple le plus utilisé en théorie du codage est
A = Zp m , l’anneau des entiers modulo p m .
b. L’ordre additif de l’élément neutre pour la multiplication par un est la caractéristique,
notée car(A).
c. La caractéristique d’un anneau de Galois A est
car(A) = p m , m ∈ N.
d. L’anneau Zp m est un anneau local pour p premier.
Proposition
ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 15 / 92
Anneaux de Galois
Définition
Si A est commutatif, unitaire, et que l’ensemble de ses diviseurs de zéro est de la forme
pA, où p est un nombre premier, alors A est un anneau de Galois.

Remarques :
a. Les corps de Galois peuvent donc être considérés comme des anneaux de Galois ne
contenant aucun diviseur de zéro. L’exemple le plus utilisé en théorie du codage est
A = Zp m , l’anneau des entiers modulo p m .
b. L’ordre additif de l’élément neutre pour la multiplication par un est la caractéristique,
notée car(A).
c. La caractéristique d’un anneau de Galois A est
car(A) = p m , m ∈ N.
d. L’anneau Zp m est un anneau local pour p premier.
Proposition
ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 15 / 92
Anneaux de Galois
Définition
Si A est commutatif, unitaire, et que l’ensemble de ses diviseurs de zéro est de la forme
pA, où p est un nombre premier, alors A est un anneau de Galois.

Remarques :
a. Les corps de Galois peuvent donc être considérés comme des anneaux de Galois ne
contenant aucun diviseur de zéro. L’exemple le plus utilisé en théorie du codage est
A = Zp m , l’anneau des entiers modulo p m .
b. L’ordre additif de l’élément neutre pour la multiplication par un est la caractéristique,
notée car(A).
c. La caractéristique d’un anneau de Galois A est
car(A) = p m , m ∈ N.
d. L’anneau Zp m est un anneau local pour p premier.
Proposition
ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 15 / 92
Modules
Définition
Un A-module (E, +, .) est un ensemble muni d’une loi interne + et d’une loi externe
A × E → E, (α, θ) 7→ αθ, vérifiant :
(I) (E, +) est un groupe abélien.
(II) On a aussi les quatre propriétés suivantes, pour tous τ, ν ∈ A et tous θ, ϑ ∈ E :
1 τ (θ + ϑ) = τ θ + τ ϑ,
2 (τ + ν)ϑ = τ ϑ + νϑ,
3 (τ ν)ϑ = τ (νϑ),
4 1ϑ = ϑ si 1 est l’unité de A.

Définition
Une partie N de E est un sous-module si et seulement si elle contient 0, et si pour tous
κ, ι dans N, et tout τ dans A, on a κ + ι ∈ N et τ κ ∈ N.

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 16 / 92

Modules
Définition
Un A-module (E, +, .) est un ensemble muni d’une loi interne + et d’une loi externe
A × E → E, (α, θ) 7→ αθ, vérifiant :
(I) (E, +) est un groupe abélien.
(II) On a aussi les quatre propriétés suivantes, pour tous τ, ν ∈ A et tous θ, ϑ ∈ E :
1 τ (θ + ϑ) = τ θ + τ ϑ,
2 (τ + ν)ϑ = τ ϑ + νϑ,
3 (τ ν)ϑ = τ (νϑ),
4 1ϑ = ϑ si 1 est l’unité de A.

Définition
Une partie N de E est un sous-module si et seulement si elle contient 0, et si pour tous
κ, ι dans N, et tout τ dans A, on a κ + ι ∈ N et τ κ ∈ N.

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 16 / 92

Modules

RemarqueY : Soit (Mt )t∈I une famille de A-modules où I est un ensemble fini ou non. Alors le
produit Mt est un S-module pour les lois évidentes ; on l’appelle le produit des S-modules
t∈I
Mt .
Définition
Soit
M (Mt )t∈I une famille de A-modules.
Y La somme directe (externe) des Mt , notée
Mt , est le sous-module de Mt constitué des familles presque nulles (Mt )t∈I . Si
t∈I t∈I
I est fini, la somme directe coïncide avec le produit direct.

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 17 / 92

Modules

RemarqueY : Soit (Mt )t∈I une famille de A-modules où I est un ensemble fini ou non. Alors le
produit Mt est un S-module pour les lois évidentes ; on l’appelle le produit des S-modules
t∈I
Mt .
Définition
Soit
M (Mt )t∈I une famille de A-modules.
Y La somme directe (externe) des Mt , notée
Mt , est le sous-module de Mt constitué des familles presque nulles (Mt )t∈I . Si
t∈I t∈I
I est fini, la somme directe coïncide avec le produit direct.

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 17 / 92

Modules

Définition
Un S-module M est dit de type fini s’il existe une partie finie G de M telle que M est
engendré par G. Il est libre s’il possède une base, c’est-à-dire
X une famille (xt )t∈I telle que
tout élément x de M s’écrit de manière unique x = αt xt , avec (αt )t∈I une famille
t∈I
presque nulle d’éléments de A.

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 18 / 92

 THEORIE DES CODES - CODES
CORRECTEURS

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 19 / 92

Généraltées

Lors d’une communication, les messages peuvent être altérés par des fautes d’orthographe, une
diction rapide ou des bruits perturbateurs, bien qu’une compréhension partielle reste souvent
possible, comme avec un réarrangement des lettres internes d’un mot. Le transfert
d’informations numériques est crucial, notamment pour les sondes spatiales recevant des
signaux sur de longues distances, rendant essentielle la minimisation des pertes d’information
grâce aux codes correcteurs. Lors de la transmission, un mot de code C peut être corrompu
par un canal bruité, aboutissant à une version altérée Ĉ reçue. Le défi principal est que le
récepteur ne connaît pas initialement le message original x .

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 20 / 92

Généralitées

Mot de Code Mot reçu

Encodage Canal bruité
C Ĉ

Message original Décodage

x et Correction

Estimation du message
original x

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 21 / 92

Généraltées

Dans la suite, Soit A un anneau fini.

Définition
Soit A un anneau fini (Alphabet) ; Un code C de langueur ‘n‘ sur A est un s-ensemble de
An

Exemple :
1-Code de Parité (ASCII 8 bits)

x=65 : ’C’=(01000001).
x=67 ; ’C’=(01000011).

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 22 / 92

Généraltées

Dans la suite, Soit A un anneau fini.

Définition
Soit A un anneau fini (Alphabet) ; Un code C de langueur ‘n‘ sur A est un s-ensemble de
An

Exemple :
1-Code de Parité (ASCII 8 bits)

x=65 : ’C’=(01000001).
x=67 ; ’C’=(01000011).

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 22 / 92

Généralitées
2- Code de Hamming (7,4)
.
x=1011
’C’=1011010.
3-Le code ISBN (International Standard Book Number) est utilisé mondialement par les
éditeurs pour identifier les propriétés d’un livre.
Défintion
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 An , c’est-à-dire que
eC
!
X n
= 2n−k
i=0
i

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 23 / 92

Généralitées
2- Code de Hamming (7,4)
.
x=1011
’C’=1011010.
3-Le code ISBN (International Standard Book Number) est utilisé mondialement par les
éditeurs pour identifier les propriétés d’un livre.
Défintion
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 An , c’est-à-dire que
eC
!
X n
= 2n−k
i=0
i

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 23 / 92

Généralitées

et que pour tout mot r ∈ An , il existe un unique mot m ∈ C qui minimise la distance
d(r , m).
On remarque que la distance minimale dC est forcément impaire et liée à la capacité de
correction eC par la relation
dC = 2eC + 1.

Défintion
Un code répétition de langueur n sur un Alphabet binaire {0,1} est définis par :
1 Chaque bit d’information est répété n foit pour formé un mot codé.
2 Le code est donc de paramètre n, 1, c’est à dire que la dimension est 1 (un seul bit
d’information et de langueur codé est n).

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 24 / 92

Généralitées

et que pour tout mot r ∈ An , il existe un unique mot m ∈ C qui minimise la distance
d(r , m).
On remarque que la distance minimale dC est forcément impaire et liée à la capacité de
correction eC par la relation
dC = 2eC + 1.

Défintion
Un code répétition de langueur n sur un Alphabet binaire {0,1} est définis par :
1 Chaque bit d’information est répété n foit pour formé un mot codé.
2 Le code est donc de paramètre n, 1, c’est à dire que la dimension est 1 (un seul bit
d’information et de langueur codé est n).

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 24 / 92

Généralitées

Exemple : pour n = 3 le bit 0 est codé par 000, et le bit 1 est codé par 111.
Définition
Un code de parité est un code linèaire [n, n − 1, 2] où chaque mot de code
(c0 , c1 , . . . , cn−1 ) vérifie la condition de parité :

c0 + c1 + · · · + cn−1 ≡ 0 (mod 2).

Le bit supplémentaire cn−1 est appelé bit de parité et permet de détecter une erreur
simple.
Le code de parité bidimensionnel applique une parité sur chaque ligne et colonne d’une
matrice de bits, permettant de détecter et parfois corriger des erreurs isolées.

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 25 / 92

Généralitées

Exemple : pour n = 3 le bit 0 est codé par 000, et le bit 1 est codé par 111.
Définition
Un code de parité est un code linèaire [n, n − 1, 2] où chaque mot de code
(c0 , c1 , . . . , cn−1 ) vérifie la condition de parité :

c0 + c1 + · · · + cn−1 ≡ 0 (mod 2).

Le bit supplémentaire cn−1 est appelé bit de parité et permet de détecter une erreur
simple.
Le code de parité bidimensionnel applique une parité sur chaque ligne et colonne d’une
matrice de bits, permettant de détecter et parfois corriger des erreurs isolées.

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 25 / 92

Généralitées
Exemple :
Pour le mot d’information (1, 0, 1, 1), le bit de parité (paire) est 1 car 1 + 0 + 1 + 1 = 3 ≡ 1
(mod 2). Le mot de code complet est donc (1, 0, 1, 1, 1).
Soit la matrice de donnée 3 × 4 suivante :

1 0 1 0
0 1 0 1
1 1 0 0
Étape 1 : Calcul des bits de parité des lignes : On ajoute une colonne à droite pour la
parité paire (somme modulo 2) :

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

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 26 / 92

Généralitées

Étape 2 : Calcul des bits de parité des colonnes : On ajoute une ligne en bas pour la
parité paire :

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

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 27 / 92

 Code Linèaire

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 28 / 92

Généralitées
Définition
Soit A un anneau fini local. Un code linèaire C de longueur n sur A est un sous-module
du A-module An , qui peut être libre ou non. Les vecteurs de C sont appelés les mots du
code C .

Exemple : Soit le code C1 ⊂ Z34 défini par :

C1 = {000, 121, 202, 323},
C1 est un sous-module de Z34 car il est stable par addition :
121 + 202 = 323 ∈ C1
121 + 323 = 444 ≡ 000 ∈ C1
202 + 323 = 525 ≡ 121 ∈ C1
De plus, C1 est stable par la multiplication scalaire dans Z4 .
ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 29 / 92
Généralitées
Définition
Soit A un anneau fini local. Un code linèaire C de longueur n sur A est un sous-module
du A-module An , qui peut être libre ou non. Les vecteurs de C sont appelés les mots du
code C .

Exemple : Soit le code C1 ⊂ Z34 défini par :

C1 = {000, 121, 202, 323},
C1 est un sous-module de Z34 car il est stable par addition :
121 + 202 = 323 ∈ C1
121 + 323 = 444 ≡ 000 ∈ C1
202 + 323 = 525 ≡ 121 ∈ C1
De plus, C1 est stable par la multiplication scalaire dans Z4 .
ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 29 / 92
Paramètres d’un code linèaire
On définit sur un code C de longueur n et de rang k une métrique appelée distance de
Hamming notée d(x , y ) entre deux vecteurs (c, c 0 ) ∈ An est le nombre de coordonnées pour
lequel c, c 0 diffèrent :

d(c, c 0 ) = |{i : ci 6= ci0 }|.

Le poids de Hamming qu’on note wH (c) d’un mot c ∈ An est le nombre de coordonnées non
nulles de c, i.e. :

wH (c) = d(c, 0).

La distance minimale notée dH (C ) d’un code C défini sur An est la plus petite distance
entre les différents mots de code, i.e. :

dH (C ) = min{d(c, c 0 ) | c, c 0 ∈ C , c 6= c 0 }.

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 30 / 92

Paramètres d’un code linèaire
On définit sur un code C de longueur n et de rang k une métrique appelée distance de
Hamming notée d(x , y ) entre deux vecteurs (c, c 0 ) ∈ An est le nombre de coordonnées pour
lequel c, c 0 diffèrent :

d(c, c 0 ) = |{i : ci 6= ci0 }|.

Le poids de Hamming qu’on note wH (c) d’un mot c ∈ An est le nombre de coordonnées non
nulles de c, i.e. :

wH (c) = d(c, 0).

La distance minimale notée dH (C ) d’un code C défini sur An est la plus petite distance
entre les différents mots de code, i.e. :

dH (C ) = min{d(c, c 0 ) | c, c 0 ∈ C , c 6= c 0 }.

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 30 / 92

Paramètres d’un code linèaire
On définit sur un code C de longueur n et de rang k une métrique appelée distance de
Hamming notée d(x , y ) entre deux vecteurs (c, c 0 ) ∈ An est le nombre de coordonnées pour
lequel c, c 0 diffèrent :

d(c, c 0 ) = |{i : ci 6= ci0 }|.

Le poids de Hamming qu’on note wH (c) d’un mot c ∈ An est le nombre de coordonnées non
nulles de c, i.e. :

wH (c) = d(c, 0).

La distance minimale notée dH (C ) d’un code C défini sur An est la plus petite distance
entre les différents mots de code, i.e. :

dH (C ) = min{d(c, c 0 ) | c, c 0 ∈ C , c 6= c 0 }.

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 30 / 92

Paramètres d’un code linèaire

Le poids minimal d’un code C est le minimum des poids non nuls du code, i.e. :

w (C ) = min{wH (c) | c ∈ C , c 6= 0}.

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 31 / 92

Codage par multiplication matrice-vecteur
Définition - La Matrice Génératrice
Une matrice génératrice d’un code linèaire sur un anneau fini A est une matrice G de taille
k ∗ n dont les lignes forment un systéme générateur du code C , i.e C = {G.x | x ∈ An }.

k n

n =

G x C

Les lignes de G doivent être independants dans A.

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 32 / 92
Codage par multiplication matrice-vecteur

Exemple :  
1 1 0 0
La matrice : G = 0 1 0 0
 
0 0 1 1
encode (1, 1, 1) comme (1, 0, 1, 1) et (1, 0, 0) comme (1, 1, 0, 0).
On Remarque que uG est une combinaison linèaire des lignes de la matrice génératrice, donc
C est l’espace des lignes de G.

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 33 / 92

Codage par multiplication matrice-vecteur

Théorème
Soit C un code linèaire sur A à une permutation des coordonnées prés C admet une
matrice génératrice G sur sous la forme standard suivante :
 
Ik0 A0,1 A0,2 ··· A0,e−1 A0,e
0
 γIk1 γA1,2 ··· γA1,e−1 γA1,e 

0 0 γ 2 Ik2 ··· γ 2 A2,e−1 γ 2 A2,e
 
G = .
 .. .. .. .. .. ..
 
 . . . . . .


0 0 0 ··· γ e−1 Ike−1 γ e−1 Ae−1,e

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 34 / 92

Codage par multiplication matrice-vecteur

Définition
Un code linèaire de paramètres (n, k, d) est dit systématique si l’encodage consiste à
rajouter n − k bits à la fin du mot. Pour un code linèaire, sa matrice génératrice G est
de la forme

G = Ik | B ,
où Ik est la matrice identité de taille k × k et B une matrice de taille k × (n − k).

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 35 / 92

Code dual d’un code linèaire
Définition

vi wi . Le code dual C ⊥ de C est défini par :

X
On munit An du produit suivant : v · w =

C ⊥ = {v ∈ An | v · w = 0 pour tout w ∈ C }.

Exemple : Soit le code C = {0000, 1111}.

Le code dual C ⊥ est donné par :

C ⊥ := {0000, 1100, 1010, 1001, 0110, 0101, 0011, 1111}.

Propriété

Si C ⊆ C ⊥ , on dit que le code C est auto-orthogonal, et si C = C ⊥ on dit que le code C

est auto-dual.

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 36 / 92

Code dual d’un code linèaire
Définition

vi wi . Le code dual C ⊥ de C est défini par :

X
On munit An du produit suivant : v · w =

C ⊥ = {v ∈ An | v · w = 0 pour tout w ∈ C }.

Exemple : Soit le code C = {0000, 1111}.

Le code dual C ⊥ est donné par :

C ⊥ := {0000, 1100, 1010, 1001, 0110, 0101, 0011, 1111}.

Propriété

Si C ⊆ C ⊥ , on dit que le code C est auto-orthogonal, et si C = C ⊥ on dit que le code C

est auto-dual.

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 36 / 92

Code dual d’un code linèaire

Définition
Le rang de C est défini par :
e−1
X
k(C ) = ki .
i=0

Il est clair que k(C ) est le nombre minimum de vecteurs d’une famille génératrice de C . De
plus nous avons une relation entre C et son dual C ⊥ :

|C ||C ⊥ | = q 2(n−ke +ke ) = q 2n = |A|n , et (C ⊥ )⊥ = C .

Remarque : Soit C un code linèaire de type {k0 , k1 , . . . , ke−1 } sur Z4 . Alors son code dual C ⊥
est de type {ke , ke−1 , . . . , k1 }.

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 37 / 92

Décodage par multiplication matrice-vecteur

k k

n = x

H C

où x c’est notre message, H la matrice de contrôle, C le code de x .

Définition
Soit C un code linèaire sur A. Une matrice de contrôle (ou matrice de parité) de C est
une matrice H de taille r × n sur A telle que pour tout c ∈ An ,

c∈C ⇐⇒ HcT = 0.

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 38 / 92

Propriétés

Soit C un code linèaire sur A. le code C est le noyau (à droite), ker(H), de H dans F n ,
i.e
C = ker(H) = {x ∈ An | Hx = 0} .
D’après la relation bien connue entre le rang d’une matrice et la dimension de son noyau,
on a

rang(H) = n − dim ker(H) = n − k.

Ainsi, dans le cas (le plus courant) où les lignes de H sont linéairement indépendantes,
on a r = n − k.
Soit G une matrice génératrice k × n de C. Les lignes de G engendrent ker(H) et, en
particulier,

HG T = 0 =⇒ GH T = 0

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 39 / 92

Décodage par multiplication matrice-vecteur

Exemple : Le code linèaire de Hamming [7, 4, 3] sur F = GF(2) est défini par la matrice de
contrôle  
0 0 0 1 1 1 1
H = 0 1 1 0 0 1 1 ,
 
1 0 1 0 1 0 1

dont les colonnes parcourent tous les vecteurs non nuls de F 3 .

Une matrice génératrice correspondante est donnée par
 
1 1 1 1 0 0 0
0 0 1 1 1 1 0
G = .
 
0 1 0 1 0 1 1
1 0 0 1 1 0 1

On vérifie que HG T = 0 et que dim ker(H) = 7 − rang(H) = 4 = rang(G).

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 40 / 92
Décodage par multiplication matrice-vecteur

Propriétés

Soit un code systématique dont la matrice génératrice est de la forme

G = Ik | B ,

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

Alors, une matrice de contrôle H associée est donnée par
 
H = −B T In−k ,

où In−k est la matrice identité (n − k) × (n − k).

Preuve : Trivial. (HG T = 0)

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 41 / 92

Décodage par multiplication matrice-vecteur

Théorème
Soit C un code.

Si d ≥ s + 1, alors C peut détecter au plus s erreurs, tq s est la capasitée de

décodage.
Lorsque s = 2t, on en déduit que C peut corriger au plus t erreurs, tq t est la
capasitée de la correction.

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 42 / 92

Syndrome

Définition
Soit Fn2 l’espace vectoriel sur le corps fini à deux éléments. On appelle syndrome du mot
m le vecteur s = HmT , où H est la matrice de contrôle du code.
Supposons que w soit un mot erroné, r = m + e, avec m un mot du code et e le vecteur
d’erreur. Ainsi,
Hr T = H(m + e)T = HmT + He T = He T ,
car m appartient au code, donc HmT = 0.
Le mot erroné et l’erreur ont le même syndrome. L’ensemble des mots associés à un
syndrome donné est appelé classe latérale (ou coset) de W .
Corriger r revient donc à trouver le mot d’erreur e de poids minimal vérifiant r = m + e
avec m ∈ C dans la classe latérale de r . Cela n’est possible que si ce mot d’erreur est
unique, ce qui suppose qu’il y ait moins d’erreurs que la capacité de correction du code.

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 43 / 92

Syndrome

Pour e = 1 on donne l’algorithme suivant :

Algorithme simple de correction d’une erreur :
T
1: Calculer le syndrome S ← Hr
2: if S = 0 then
3: Pas d’erreur : m̂ ← r
4: else
5: Chercher la colonne hi de H telle que hi = S
6: if une telle colonne existe then
7: Corriger l’erreur en position i : m̂ ← r + ei
8: else
9: Échec du décodage (plus d’une erreur)
10: end if
11: end if

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 44 / 92

 Propriété

Chaque syndrome est associé à un unique mot m ∈ Fn2 dont le poids w (m) vérifie w (m) ≤
w (e) avec e ∈ C .

Preuve : Supposons qu’il existe m, m0 ∈ Fn2 tels que w (m), w (m0 ) ≤ w (e), m, m0 ∈
/ C et

HmT = Hm0T .

Alors, H(m − m0 )T = HmT − Hm0T = 0, Donc m − m0 ∈ C , car le noyau de H est le code C .

Or, w (m − m0 ) ≤ w (m) + w (m0 ) ≤ 2w (e) < dC , où dC est la distance minimale du code.
Le seul mot du code dont le poids est strictement inférieur à dC est le mot nul, donc

m − m0 = 0 =⇒ m = m0 .

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 45 / 92

 Propriété

Chaque syndrome est associé à un unique mot m ∈ Fn2 dont le poids w (m) vérifie w (m) ≤
w (e) avec e ∈ C .

Preuve : Supposons qu’il existe m, m0 ∈ Fn2 tels que w (m), w (m0 ) ≤ w (e), m, m0 ∈
/ C et

HmT = Hm0T .

Alors, H(m − m0 )T = HmT − Hm0T = 0, Donc m − m0 ∈ C , car le noyau de H est le code C .

Or, w (m − m0 ) ≤ w (m) + w (m0 ) ≤ 2w (e) < dC , où dC est la distance minimale du code.
Le seul mot du code dont le poids est strictement inférieur à dC est le mot nul, donc

m − m0 = 0 =⇒ m = m0 .

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 45 / 92

 Exemple d’Application

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 46 / 92

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
!
X n
= 2n−k =⇒ 1 + n = 2r
i=0
i
n = 2r − 1 et k = 2r − r − 1.
Les codes ayant ces paramètres sont appelés codes de Hamming.
Définition
Un code de Hamming est un code de paramètres (2r − 1, 2r − r − 1, 3) avec r ≥ 2 ; c’est
un code parfait.
Les codes parfaits ayant une capacité de correction 1 sont donc nécessairement des codes
de Hamming. Pour r = 2, le code parfait de paramètres (3, 1, 3) est le code de répétition.
ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 47 / 92
Exemple

Étudions le cas r = 3.
Considérons un code C (7, 4, 3) de Hamming binaire de matrice génératrice suivante :
 
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 modifier un de ses bits et de le décoder. Prenons m = (1010),

donc :  
1 0 0 0 1 1 0
0 1 0 0 1 0 1
mG = (1010)   = (1010101).
 
0 0 1 0 0 1 1
0 0 0 1 1 1 1

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 48 / 92

Modifions le 6ème bit (1010101) → (1010111). Puisque le code est systématique, il est facile
de retrouver la matrice de contrôle H.
 
1 1 0 1 1 0 0
H = 1 0 1 1 0 1 0 .
 
0 1 1 1 0 0 1
Calcule de syndrome :
Calculons
S = H ×rT (mod 2)
 
1
0
 
    
1 1 0 1 1 0 0  1 0
 
S = 1 0 1 1 0 1 0 0 = 1 .
 
  
0 1 1 1 0 0 1 1
 0
1
 
1
ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 49 / 92
Liste des syndromes et correspand avec la position d’erreur :

Position Colonne de H Syndrome

1 (1,1,0) 110
2 (1,0,1) 101
3 (0,1,1) 011
4 (1,1,1) 111
5 (1,0,0) 100
6 (0,1,0) 010
7 (0,0,1) 001
Table: Correspondance entre position d’erreur, colonne de H et syndrome pour le code de Hamming
(7,4).

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 50 / 92

Correction de l’erreur :
L’erreur est détéctée en 6ème position. On corrige r en inversant le 6ème bit :
r = (1010111) → C = (1010101)
Décodage :
m = H ∗C ;  
1
0
   
  1
1 1 0 1 1 0 0  1
 
  0
m = 1 0 1 1 0 1 0  0 =  .
    
1
0 1 1 1 0 0 1 1  
0
0
 
1

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 51 / 92

 CONSTRUCTION DES CODES
LINEAIRES SUR UN ANNEAU FINI

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 52 / 92

Introduction

Les codes linéaires définis sur des anneaux finis offrent une structure plus riche que les codes
classiques sur corps finis, permettant de modéliser des alphabets complexes adaptés aux
architectures modernes et d’élargir la gamme de codes, notamment cycliques, BCH et Goppa,
ainsi que leur usage en cryptographie avancée. Ces anneaux fournissent un cadre naturel pour
concevoir des codes performants et flexibles, répondant aux besoins des systèmes de
communication à haut débit et des protocoles de sécurité.

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 53 / 92

 Codes cyclique

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 54 / 92

Codes cyclique

Définition
Soit un code linèaire C ⊆ An . On dit que C est cyclique si et seulement si il est stable
par l’opérateur de décalage cyclique σ, c’est-à-dire :

∀c ∈ C , σ(c) ∈ C ,
où l’opérateur σ est défini par

σ(c0 , c1 , . . . , cn−1 ) = (cn−1 , c0 , c1 , . . . , cn−2 ).

Autrement dit, le décalage cyclique d’un mot de code appartient toujours au code.

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 55 / 92

Codes cyclique

Exemple : Le code de parité (n, n − 1) est un code cyclique. En effet, si c = (c0 , . . . , cn−1 ) est
un mot de code, alors
n−2
X
cn−1 = ci mod 2.
i=0

Mais on a alors aussi

n−3
X
cn−2 = cn−1 + ci mod 2;
i=0

ainsi, σ(c) = (cn−1 , c0 , . . . , cn−2 ) est aussi un mot de code.

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 56 / 92

Caractérisation
Polynome générateur
Tout élément C = (c0 , . . . , cn−1 ) de An peut être représenté par le polynôme de degré n − 1 de
A[X ]
n−1
X
C (X ) = ci X i .
i=0

Comme X − 1 est un polynôme de degré n, A est isomorphe à A[X ]/(X n − 1). Dans
n n

A[X ]/(X n − 1), on a alors

σ(C ) = X · C (X ) = cn−1 · (X n − 1) + X · C (X ) mod (X n − 1)

Autrement dit, l’opération de décalage d’un vecteur revient à multiplier son polynôme associé
par X dans A[X ]/(X n − 1).
Cette propriété est à la base du théorème suivant qui donne une caractérisation algébrique du
code cyclique.
ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 57 / 92
Caractéristique

Théorème
Soit C (X ) l’ensemble des polynômes associés aux mots du code cyclique C . Alors C (X )
est un idéal de A[X ]/(X n −1).(Comme A[X ]/(X n −1) est principal alore C (X ) est engen-
dré par un unique polynôme unitaire g(x ) divisant x n − 1, appelé polynôme générateur
du code. Ainsi, le code cyclique s’écrit C = hg(x )i = {g(x )q(x ) | q(x ) ∈ Rn }.

Preuve
Soit A un anneau commutatif unitaire et

Rn = A[X ]/(X n − 1)

l’anneau quotient des polynômes modulo X n − 1.

Soit C ⊆ An un code cyclique, c’est-à-dire un sous-espace vectoriel stable par décalage
cyclique. On identifie chaque mot c = (c0 , c1 , . . . , cn−1 ) ∈ An au polynôme
ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 58 / 92
Caractérisation

c(X ) = c0 + c1 X + · · · + cn−1 X n−1 ∈ Rn .

On définit
C (X ) = {c(X ) ∈ Rn | c ∈ C }.

C (X ) est un sous-groupe additif de Rn .

C (X ) est stable par multiplication par X .
C (X ) est un idéal de Rn .
Puisque Rn est engendré par X comme anneau, la stabilité par multiplication par X et la
fermeture additive impliquent que pour tout q(X ) ∈ Rn et c(X ) ∈ C (X ),

q(X ) · c(X ) ∈ C (X ).

Ainsi, C (X ) est un idéal de Rn .

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 59 / 92
Théorème
Pour un code cyclique de longueur n avec polynôme générateur g(X ), sa dimension est :

k = n − deg(g(X ))

Théorème

Soit g(X ) = c0 + c1 X 1 + . . . + ct X t le générateur d’un code cyclique C de longueur n sur

A. La matrice G à k lignes et n colonnes suivante, où t = deg(g(X )) = n − k est une
matrice génératrice du code C . On a
 
c0 c1 c2 · · · ct 0 ··· ··· 0 0
0 c
 0 c1 c2 · · · ct 0 ··· 0 0 
. . .. .. . .. . .. .. .. 
 ..
G = .. . . .. . .. . . .
 0 0 ··· 0 c0 c1 c2 ··· ct 0
 

0 0 0 ··· 0 c0 c1 c2 ··· ct
ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 60 / 92
Opération de codage
Soit C un code cyclique de polynôme générateur g ; soit G une matrice génératrice de C
construite à partir de g comme dans le théorème 6. Soit m = [m0 , . . . , mk−1 ] ∈ Ak un mot
source et
k−1
X
m(X ) = mi X i
i=0
son polynôme associé. Le mot de code associé à m est φ(m) = mG de polynôme associé C .
Par l’écriture de G à partir des coefficients de g(X ) (théorème 6), on a :

k−1
X
C (X ) = ai (X i g(X )) mod X n − 1
i=0
k−1
" !#
X
i
= g(X ) mi X mod X n − 1
i=0
= [g(X ) · m(X )] mod X n − 1.
ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 61 / 92
Algorithmes pour codage et decodage des codes cyclique avec détéction et
corréction des erreurs
Algorithme de Codage (Forme Systématique)
1-Entrées/Sorties
Entrée : Message m = (m0 , m1 , . . . , mk−1 ) (k bits)
Sortie : Mot de code c = (c0 , c1 , . . . , cn−1 ) (n bits)
Polynôme générateur : g(x ) de degré n − k
2-Algorithme
k−1
X
1: Représenter le message comme polynôme : m(x ) = mi x i
i=0
2: Multiplier par x n−k : x n−k · m(x )
n−k
3: Calculer le reste : r (x ) = (x · m(x )) mod g(x )
n−k
4: Construire le mot de code : c(x ) = x · m(x ) − r (x )
5: return c = coefficients de c(x )
ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 62 / 92
Algorithmes pour codage et decodage des codes cyclique avec détéction et
corréction des erreurs

Exemple : Pour n = 7, k = 4, g(x ) = x 3 + x + 1, m = (1, 0, 1, 1) :

x 3 · m(x ) = x 3 + x 5 + x 6
r (x ) = x
c(x ) = x 6 + x 5 + x 3 + x
c = (0, 1, 0, 1, 0, 1, 1)

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 63 / 92

Algorithmes pour codage et decodage des codes cyclique avec détéction et
corréction des erreurs

Détection d’Erreurs
1: Calculer le syndrome : s(x ) = r (x ) mod g(x )
2: if s(x ) 6= 0 then
3: return "Erreur détectée"
4: else
5: return "Pas d’erreur"
6: end if

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 64 / 92

AlgorithmeS pour codage et decodage des codes cyclique avec détéction
et corréction des erreurs

Correction d’1 Erreur

1-Table des Syndromes
Syndrome s(x ) Position erreur
1 0
x 1
x2 2
.. ..
. .

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 65 / 92

AlgorithmeS pour codage et decodage des codes cyclique avec détéction
et corréction des erreurs

2-Algorithme
1: Calculer s(x ) = r (x ) mod g(x )
2: if s(x ) 6= 0 then
3: Trouver position i dans la table
4: ri ← ri ⊕ 1 (correction)
5: end if
6: return r

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 66 / 92

Exemple d’Application
Paramètres du Code
Longueur (n) : 7
Dimension (k) : 4
Polynôme générateur : g(x ) = x 3 + x + 1
Message à coder : m = (1, 0, 1, 1)
Codage du Message
Étape 1 : Représentation polynomiale
m(x ) = 1 + x 2 + x 3
Étape 2 : Multiplication par x n−k
x 3 · m(x ) = x 3 (1 + x 2 + x 3 ) = x 3 + x 5 + x 6
Étape 3 : Calcul du reste

r (x ) = (x 3 + x 5 + x 6 ) mod (x 3 + x + 1)
=x (par divisions successives)
ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 67 / 92
Exemple d’Application
Étape 4 : Construction du mot de code

c(x ) = x 3 · m(x ) − r (x )
= x6 + x5 + x3 + x
⇒ c = (0, 1, 0, 1, 0, 1, 1)
Détection d’Erreur
1- l’erreur
Erreur en position 2 : r = (0, 1, 1, 1, 0, 1, 1)
r (x ) = x + x 2 + x 3 + x 5 + x 6
2-Calcul du syndrome

s(x ) = r (x ) mod g(x )

= x 2 6= 0 erreur détectée
ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 68 / 92
Exemple d’Application
Correction d’Erreur
1-Table des syndromes

Syndrome s(x ) Position erreur

1 0
x 1
x2 2
x +1 3
x2 + x 4
2
x +x +1 5
x2 + 1 6

2-Correction
Pour s(x ) = x 2 erreur en position 2
Mot corrigé : (0, 1, 0, 1, 0, 1, 1)
ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 69 / 92
 Codes BCH

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 70 / 92

Introduction
Les codes BCH (Bose-Chaudhuri-Hocquenghem), inventés à la fin des années 1950, sont une
famille clé de codes cycliques correcteurs d’erreurs, largement utilisés en communications
numériques et en stockage de données pour leur capacité à corriger plusieurs erreurs.
Dans cette analyse, on considère un anneau local fini, commutatif et unitaire A, avec M
comme idéal maximal et
K = A/M ∼ = GF(p m ).
L’anneau des polynômes A[X ] est défini, avec une réduction
ϕ : A[X ] → K [X ]
modulo M. Si f (X ) ∈ A[X ] est un polynôme de degré h tel que ϕ(f (X )) est irréductible dans
K [X ], alors f (X ) est irréductible dans A[X ].
L’anneau quotient
R = A[X ]/(f (X ))
est un anneau de Galois sur A, local, unitaire et fini, de degré h.
On définit
ILHAM EL HARRAK ( F.P.T .taza ) K = A/ϕ(M
Projet de fin ∼
= GF(p mh ),
) d’étude today 71 / 92
Frame Title

Définition
Un code BCH raccourci C(n, η) de longueur n ≤ s est un code sur A dont la matrice de
contrôle de parité est
 
α1 α2 · · · αn
 2 2 2
 1 α2 · · · αn 
α
H = .
 .. . . . 
 .. . . .. 
r r r
α1 α2 · · · αn
pour un certain r ≥ 1, où η = (α1 , α2 , . . . , αn ) = (αk1 , αk2 , . . . , αkn ) est le vecteur locali-
sateur, constitué d’éléments distincts de Gs . Le code C(n, η), avec n = s, est appelé un
code BCH. Dans ce cas, η est unique à permutation des coordonnées.

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 72 / 92

Codes BCH

Lemme Soit α un élément de Gs d’ordre s. Alors les différences αl1 − αl2 sont inversibles dans
R si 0 ≤ l1 6= l2 ≤ s − 1.
Preuve Notons que αl1 − αl2 peut s’écrire comme −αl2 (1 − αl1 −l2 ), où 1 désigne l’unité de R.
Le premier terme du produit, à savoir −αl2 , est une unité. Le second terme peut s’écrire 1 − αj
pour un certain entier j dans l’intervalle [1, s − 1]. Supposons que pour un certain j, 1 − αj ne
soit pas une unité dans R, c’est-à-dire 1 − αj ∈ M1 . Alors, pour tout j < s, (µ0 (α))j = µ0 (1), ce
qui est une contradiction. Ainsi, 1 − αj ∈ R ∗ , 1 ≤ j ≤ s − 1.
Théorème
La distance de Hamming minimale d’un code BCH C(n, η) vérifie d ≥ r + 1.

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 73 / 92

Codes BCH

Lemme Soit α un élément de Gs d’ordre s. Alors les différences αl1 − αl2 sont inversibles dans
R si 0 ≤ l1 6= l2 ≤ s − 1.
Preuve Notons que αl1 − αl2 peut s’écrire comme −αl2 (1 − αl1 −l2 ), où 1 désigne l’unité de R.
Le premier terme du produit, à savoir −αl2 , est une unité. Le second terme peut s’écrire 1 − αj
pour un certain entier j dans l’intervalle [1, s − 1]. Supposons que pour un certain j, 1 − αj ne
soit pas une unité dans R, c’est-à-dire 1 − αj ∈ M1 . Alors, pour tout j < s, (µ0 (α))j = µ0 (1), ce
qui est une contradiction. Ainsi, 1 − αj ∈ R ∗ , 1 ≤ j ≤ s − 1.
Théorème
La distance de Hamming minimale d’un code BCH C(n, η) vérifie d ≥ r + 1.

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 73 / 92

Codes BCH

Lemme Soit α un élément de Gs d’ordre s. Alors les différences αl1 − αl2 sont inversibles dans
R si 0 ≤ l1 6= l2 ≤ s − 1.
Preuve Notons que αl1 − αl2 peut s’écrire comme −αl2 (1 − αl1 −l2 ), où 1 désigne l’unité de R.
Le premier terme du produit, à savoir −αl2 , est une unité. Le second terme peut s’écrire 1 − αj
pour un certain entier j dans l’intervalle [1, s − 1]. Supposons que pour un certain j, 1 − αj ne
soit pas une unité dans R, c’est-à-dire 1 − αj ∈ M1 . Alors, pour tout j < s, (µ0 (α))j = µ0 (1), ce
qui est une contradiction. Ainsi, 1 − αj ∈ R ∗ , 1 ≤ j ≤ s − 1.
Théorème
La distance de Hamming minimale d’un code BCH C(n, η) vérifie d ≥ r + 1.

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 73 / 92

Frame Title
Preuve : Supposons que c est un mot de code non nul dans C(n, η) tel que wH (c) ≤ 2t. Alors
cH T = 0. En supprimant les n − 2t colonnes de la matrice H correspondant aux zéros du mot
de code, il s’ensuit que la nouvelle matrice H 0 est Vandermonde. D’après le Lemme 3, le
déterminant est une unité dans R. Ainsi, la seule possibilité pour c est le mot de code
entièrement nul.
Exemple : Le polynôme f (x ) = x 3 + x + 1 est irréductible sur GF (2) et sur A = GF (2)[i], où
A[X ]
i 2 = −1. Ainsi, l’anneau R est R = . On a que si α est une racine de f (x ), alors α
hf (x )i
engendre un groupe cyclique Gs d’ordre s = 23 − 1 = 7. Soit η = (α5 , α, 1, α4 , α2 , α6 ) le vecteur
localisateur. Si r = 2, alors la matrice suivante
" #
α5 α 1 α4 α2
H=
α6 α5 1 1 α4
est la matrice de contrôle de parité d’un code BCH C(6, η) de longueur 6 et de distance de
Hamming minimale au moins 3.
ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 74 / 92
Frame Title
Preuve : Supposons que c est un mot de code non nul dans C(n, η) tel que wH (c) ≤ 2t. Alors
cH T = 0. En supprimant les n − 2t colonnes de la matrice H correspondant aux zéros du mot
de code, il s’ensuit que la nouvelle matrice H 0 est Vandermonde. D’après le Lemme 3, le
déterminant est une unité dans R. Ainsi, la seule possibilité pour c est le mot de code
entièrement nul.
Exemple : Le polynôme f (x ) = x 3 + x + 1 est irréductible sur GF (2) et sur A = GF (2)[i], où
A[X ]
i 2 = −1. Ainsi, l’anneau R est R = . On a que si α est une racine de f (x ), alors α
hf (x )i
engendre un groupe cyclique Gs d’ordre s = 23 − 1 = 7. Soit η = (α5 , α, 1, α4 , α2 , α6 ) le vecteur
localisateur. Si r = 2, alors la matrice suivante
" #
α5 α 1 α4 α2
H=
α6 α5 1 1 α4
est la matrice de contrôle de parité d’un code BCH C(6, η) de longueur 6 et de distance de
Hamming minimale au moins 3.
ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 74 / 92
 Codes Goppa

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 75 / 92

Définition
Soit R = A[X ]/f (X ) :
- On défini le polynôme de Goppa g(X ) ∈ R[X ], souvent irréductible de degré r, et un
ensemble L = {a1 , a2 , . . . , an } ⊂ A de points distincts tels que g(ai ) inversble pour tout i.

- Le code de Goppa associé à g(X ) et à L est noté :

n
( )
X ci
Γ(L, g) = c = (c1 , . . . , cn ) ∈ Fnq ≡0 mod g(X ) .
i=1
X − ai

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 76 / 92

Définition
Soit C(L, g) un code de Goppa.
Si g(z) est irréductible, alors C(L, g) est appelé un code de Goppa irréductible.
Si c = (c1 , c2 , . . . , cn ) ∈ C(L, g) et c 0 = (cn , cn−1 , . . . , c1 ) ∈ C(L, g), alors C(L, g) est
appelé un code de Goppa réversible.
Si g(z) = (z − α)r , alors C(L, g) est appelé un code de Goppa cumulatif.
Si g(z) n’a pas de racines multiples, alors C(L, g) est appelé un code de Goppa
séparable.

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 76 / 92

Code Goppa
Définition
Soit C(L, g) un code de Goppa.
Si g(z) est irréductible, alors C(L, g) est appelé un code de Goppa irréductible.
Si c = (c1 , c2 , . . . , cn ) ∈ C(L, g) et c 0 = (cn , cn−1 , . . . , c1 ) ∈ C(L, g), alors C(L, g) est
appelé un code de Goppa réversible.
Si g(z) = (z − α)r , alors C(L, g) est appelé un code de Goppa cumulatif.
Si g(z) n’a pas de racines multiples, alors C(L, g) est appelé un code de Goppa
séparable.

Remarque : Soit C(L, g) un code de Goppa.

On a que C(L, g) est un code linéaire.
Une matrice de contrôle de parité à coefficients dans A est obtenue en remplaçant chaque
entrée de H par le vecteur colonne correspondant de longueur h issu de A.
ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 76 / 92
Code Goppa
Définition
Soit C(L, g) un code de Goppa.
Si g(z) est irréductible, alors C(L, g) est appelé un code de Goppa irréductible.
Si c = (c1 , c2 , . . . , cn ) ∈ C(L, g) et c 0 = (cn , cn−1 , . . . , c1 ) ∈ C(L, g), alors C(L, g) est
appelé un code de Goppa réversible.
Si g(z) = (z − α)r , alors C(L, g) est appelé un code de Goppa cumulatif.
Si g(z) n’a pas de racines multiples, alors C(L, g) est appelé un code de Goppa
séparable.

Remarque : Soit C(L, g) un code de Goppa.

On a que C(L, g) est un code linéaire.
Une matrice de contrôle de parité à coefficients dans A est obtenue en remplaçant chaque
entrée de H par le vecteur colonne correspondant de longueur h issu de A.
ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 76 / 92
Code Goppa

(α1 − β1 )−r (α2 − β1 )−r (αn − β1 )−r

 
···

 α1 (α1 − β1 )−r α2 (α2 − β1 )−r ··· αn (αn − β1 )−r 

H1 =  .. .. .. .. 

 . . . .


α1r −1 (α1 − β1 )−r α2r −1 (α2 − β1 )−r ··· αnr −1 (αn − β1 )−r
qui est équivalente par lignes à

(α1 − β1 )−r (α2 − β1 )−r (αn − β1 )−r

 
···
−r +1
(α1 − β1 )

(α2 − β1 )−r +1 · · · (αn − β1 )−r +1 

H1 = 
 .. .. .. .. 
 . . . .


−1 −1 −1
(α1 − β1 ) (α2 − β1 ) · · · (αn − β1 )

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 77 / 92

 k
Y k
Y
r
Par conséquent, si g(y ) = (x − βl ) = gl (x ), alors le code de Goppa est l’intersection des
l=1 l=1
codes associés aux gl (x ) = (x − βl )r , pour l = 1, 2, . . . , k, et sa matrice de contrôle de parité
est donnée par
 
H1
 H2 
 
H =
 .. 

 . 
Hk

Les codes BCH sont un cas particulier des codes de Goppa. Pour cela, on choisit g(x ) = x r et
L = {α1 , α2 , . . . , αn }, où chaque αi ∈ Gs pour i = 1, 2, . . . , n. Alors, d’après l’équation (4.1) :

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 78 / 92

Code Goppa
 −r
α2−r · · · αn−r

α1
 1−r
α1 α21−r · · · αn1−r 

H =
 .. .. .. .. 
 . . . . 


α1−1 α2−1 · · · αn−1

qui devient la matrice de contrôle de parité d’un code BCH, matrice (3.2), lorsque αi−1 est
remplacé par βi , i = 1, 2, . . . , n.
Théorème
Le code de Goppa C(L, g) a une distance de Hamming minimale d ≥ r + 1.

preuve : Nous avons que C(L, g) est un code alternant C(n, η, w) avec η = (α1 , α2 , · · · , αn ) et
w = (g(α1 )−1 , g(α2 )−1 , · · · , g(αn )−1 ). Par conséquent, d’après le Théorème 3.2, nous avons
que C(L, g) possède une distance minimale d ≥ r + 1.
ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 79 / 92
Code Goppa
 −r
α2−r · · · αn−r

α1
 1−r
α1 α21−r · · · αn1−r 

H =
 .. .. .. .. 
 . . . . 


α1−1 α2−1 · · · αn−1

qui devient la matrice de contrôle de parité d’un code BCH, matrice (3.2), lorsque αi−1 est
remplacé par βi , i = 1, 2, . . . , n.
Théorème
Le code de Goppa C(L, g) a une distance de Hamming minimale d ≥ r + 1.

preuve : Nous avons que C(L, g) est un code alternant C(n, η, w) avec η = (α1 , α2 , · · · , αn ) et
w = (g(α1 )−1 , g(α2 )−1 , · · · , g(αn )−1 ). Par conséquent, d’après le Théorème 3.2, nous avons
que C(L, g) possède une distance minimale d ≥ r + 1.
ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 79 / 92
Code Goppa
 −r
α2−r · · · αn−r

α1
 1−r
α1 α21−r · · · αn1−r 

H =
 .. .. .. .. 
 . . . . 


α1−1 α2−1 · · · αn−1

qui devient la matrice de contrôle de parité d’un code BCH, matrice (3.2), lorsque αi−1 est
remplacé par βi , i = 1, 2, . . . , n.
Théorème
Le code de Goppa C(L, g) a une distance de Hamming minimale d ≥ r + 1.

preuve : Nous avons que C(L, g) est un code alternant C(n, η, w) avec η = (α1 , α2 , · · · , αn ) et
w = (g(α1 )−1 , g(α2 )−1 , · · · , g(αn )−1 ). Par conséquent, d’après le Théorème 3.2, nous avons
que C(L, g) possède une distance minimale d ≥ r + 1.
ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 79 / 92
Exemple :
A[x ]
Soit A = GF (2)[i] et R = , où f (x ) = x 4 + x + 1 est irréductible sur A. Ainsi
(x 4 + x + 1)
s = 15 et G15 est engendré par α, où α4 = α + 1. Soit g(z) = z 4 + z 3 + 1,
L = {1, α, α2 , α7 , α5 , α4 , α7 , α5 , α8 , α9 } et w = (1, α12 , α11 , α7 , α3 , α11 , α6 , α5 , α4 , α13 ). La
matrice

1 α12 α10 α7 α3 α11 α6 α9 α5 α14 α13

 
 1 α14 1 α4 α11 α2 α7 α13 1 α8 α 
H =
 
5 4 8 9 2 10 2
 1 α α α α α α α α α α4 


1 α3 α10 α13 α12 α14 α9 α6 α5 α11 α7

. La matrice de contrôle H est fournie, et nous cherchons à déterminer sa matrice génératrice
G;
-On transforme la matrice de contrôle H par des opérations élémentaires sur les lignes et les
colonnes pour obtenir la forme systématique suivante :
 
H = P | I4
Comme suite
ILHAM EL : ( F.P.T .taza )
HARRAK Projet de fin d’étude today 80 / 92
Encodage avec code Goppa

Soit Γ(L, g(z)) un code de Goppa, où g(z) est un polynôme primitif avec deg(g(z)) = t et
|L| = n. Soit dimFq (Γ(L, g(z))) = k, et soit G une matrice génératrice de taille k × n associée
au code de Goppa ; alors le codage d’un vecteur-message m de longueur k sur Fq est donné
par mG.

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 81 / 92

Décodage avec code Goppa
Soit le vecteur y = (y1 , y2 , . . . , yn ) reçu avec r erreurs, où 2r + 1 ≤ d 0 (nombre maximum de
corrections d’erreurs). Soit L = {α1 , α2 , . . . , αn },
y = (y1 , y2 , . . . , yn ) = (c1 , c2 , . . . , cn ) + (e1 , e2 , . . . , en )
| {z } | {z }
mot de code vecteur d’erreur
avec ei 6= 0 exactement à r positions. Nous avons besoin de : - localiser les positions des
erreurs (disons B = {i : 1 ≤ i ≤ n et ei 6= 0}), - trouver les valeurs correspondantes des erreurs
(ei pour i ∈ B).
Pour cela, nous définissons deux polynômes :
Définition
Y
Polynôme localisateur σ(z) et polynôme évaluateur w (z) : - σ(z) = (z − αi ) (ceci est
X Y i∈B
un polynôme de degré r ), - w (z) = ei (z − αj ) (ceci est un polynôme de degré
i∈B j∈B,j6=i
r − 1).
ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 82 / 92
Décodage avec code Goppa

Définition
Le syndrome du vecteur reçu y est défini par S(y ) où :
n
X yi
S(y ) :=
i=1
z − αi

n
X ci X ei
= +
i=1
z − αi i∈B z − αi
X ei
= mod g(z).
i∈B
z − αi

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 83 / 92

Décodage avec code Goppa

Proposition :  0
d
Soit e le vecteur d’erreur de poids r : r ≤ . Soit σ(z), w (z) et S(y ) comme décrits
2
ci-dessus. Alors les propriétés suivantes sont vérifiées :
1 deg(σ(z)) = r ;
2 deg(w (z)) ≤ r − 1 ;
3 gcd(σ(z), w (z)) = 1 ;
w (αk )
4 ek = 0 , où k ∈ B et σ 0 représente la dérivée de σ ;
σ (αk )
5 σ(z)S(y ) ≡ w (z) (mod g(z)).
d
 
Correction des erreurs : Algorithme pour corriger r ≤ :
2

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 84 / 92

Décodage avec code Goppa

Proposition :  0
d
Soit e le vecteur d’erreur de poids r : r ≤ . Soit σ(z), w (z) et S(y ) comme décrits
2
ci-dessus. Alors les propriétés suivantes sont vérifiées :
1 deg(σ(z)) = r ;
2 deg(w (z)) ≤ r − 1 ;
3 gcd(σ(z), w (z)) = 1 ;
w (αk )
4 ek = 0 , où k ∈ B et σ 0 représente la dérivée de σ ;
σ (αk )
5 σ(z)S(y ) ≡ w (z) (mod g(z)).
d
 
Correction des erreurs : Algorithme pour corriger r ≤ :
2

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 84 / 92

Étape (i) : Calculer le syndrome
n
X yi
S(y ) = ,
i=1
z − αi
Étape (ii) : Résoudre l’équation clé
σ(z)S(y ) ≡ w (z) (mod g(z)),
en écrivant
σ(z) = σ0 + σ1 z + · · · + σr −1 z r −1 + z r ,
w (z) = w0 + w1 z + · · · + wr −1 z r −1 ,
et résoudre t équations avec 2r inconnues.
Si le code est binaire, prendre w (z) = σ 0 (z),
Étape (iii) : Déterminer l’ensemble des positions d’erreur B = {i | 1 ≤ i ≤ n et σ(αi ) = 0},
w (αi )
Étape (iv) : Calculer les valeurs d’erreur ei = 0 pour tous i ∈ B,
σ (αi )
Étape (v) : Le vecteur d’erreur e = (e1 , e2 , . . . , en ) est défini par ei pour i ∈ B et des zéros
ailleurs,
ÉtapeILHAM(vi) : Le (mot
EL HARRAK de )code envoyé est calculé
F.P.T .taza Projet de fincomme
d’étude c = y − e. today 85 / 92
Exemple d’Application
Soit F3 le corps correspondant au polynôme primitif x 2 − x − 1 sur le corps de base F3 et soit
α une de ses racines. Alors nous avons :

0 = (0, 0)T ;
1 = (1, 0)T ;
α = α = (0, 1)T ;
α2 = 1 + α = (1, 1)T ;
α3 = −1 − α = (−1, 0)T ;
α4 = −1 = (−1, −1)T ;
α5 = −1 − α = (−1, −1)T ;
α6 = −1 + α = (−1, 1)T ;
α7 = −1 + α = (−1, 1)T .

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 86 / 92

Code Goppa
Considérons le code de Goppa Γ(L, g(z)) défini par :
g(z) = z(z − α7 ) = z 2 + α7 z,
L = {αi : 0 ≤ i ≤ 6}
La matrice de contrôle :
 1 1 1 
 g(α ) g(α1 )
0
···
g(α6 ) 
H =  α0 α1 α6  .

···
g(α0 ) g(α1 ) g(α6 )
Alors la matrice de contrôle sur F3 (α) sera :

!
2+a 1+a a 2+a a a
H=
1 2 2 1 + 2a 2 + 2a 2 + a
ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 87 / 92
Code Goppa

Équivalentement, la matrice de contrôle sur F3 sera :

 
1 2 1 0 2 0 0
1 1 1 2 1 1 0
H7,3 = 
 
1 1 2 2 1 2 1


1 0 0 0 2 2 1
Cela donne la matrice génératrice comme :
 
1 1 1 1 1 0 0
G = −1 1 −1 1 0 1 0 .
 
1 −1 1 −1 0 0 1

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 88 / 92

Code Goppa
Les paramètres de ce code sont [7, 3, ≥ 3]. Maintenant, supposons que le message m = (0, 0, 0)
soit envoyé. L’encodage de ce vecteur donnera c = mG = (0, 0, 0, 0, 0, 0, 0). Supposons que le
vecteur reçu y = (0, 0, 0, 0, 0, 0, −1) contienne une erreur. Notre objectif est de trouver le
vecteur d’erreur.
Étape (i) : Calculer le syndrome S(y )
Le syndrome est défini par :
n
X yi
S(y )(z) = .
i=1
z − αi
Pour y = (0, 0, 0, 0, 0, 0, −1), seul y7 = −1 est non nul. Donc :
−1
S(y )(z) = .
z − α6
On réduit modulo g(z) = z 2 + α7 z :
−1 A + Bz
≡ (division polynomiale).
z − α6 g(z)
ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 89 / 92
Code Goppa
En multipliant par (z − α6 ) et évaluant à z = α6 :
−1 = A + Bα6 ⇒ A = −1 − Bα6 .
En résolvant, on trouve :
−1 − α6 z
S(y )(z) ≡ .
g(z)

Étape (ii) : Résoudre l’équation clé

On cherche σ(z) (polynôme localisateur) et w (z) (polynôme évaluateur) tels que :
σ(z)S(y )(z) ≡ w (z) (mod g(z)).
Avec deg(σ) ≤ 1 (car 1 erreur) et deg(w ) = 0 :
σ(z) = σ0 + z, w (z) = w0 .
En substituant S(y )(z) :
!
ILHAM EL HARRAK ( F.P.T .taza )
α6 zde fin d’étude
−1 −Projet today 90 / 92
Code Goppa

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 91 / 92

Code Goppa

ILHAM EL HARRAK ( F.P.T .taza ) Projet de fin d’étude today 92 / 92