Code lineare sur les anneaux

finis

Projet de Fin d’etudes

Ilham El Harrak

Encadrant : Prof Abdelkarim Boua

 Remerciements

Je tiens à exprimer ma profonde gratitude à Abdelkarim Boua, mon

encadrant, pour son soutien et ses précieuses orientations qui ont joué un
rôle essentiel dans la réalisation de ce travail.
J’aimerais également exprimer ma reconnaissance sincère à tous les
professeurs de mathématiques de la Faculté de Taza, qui ont grandement
contribué à ma formation scientifique et académique. Votre dévouement à
l’enseignement et votre souci constant de nous guider vers une pensée
logique et un raisonnement rigoureux ont été une source précieuse
d’apprentissage.
Que Dieu vous récompense pour vos efforts et vous accorde succès et
prospérité dans votre carrière pédagogique et professionnelle.
Enfin, je tiens à adresser toute ma gratitude et mon estime à ma famille
pour leur soutien matériel et moral inestimable, ainsi que pour leur
encouragement constant, qui a été une véritable source de force tout au
long de mon parcours académique.

Ilham El Harrak
 TABLE DES MATIÈRES

introduction 3

1 Préliminaires 4
1.1 Généralitées . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.1 Idéaux . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Anneaux de Galois . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2 Theorie des codes - Codes correcteurs 8

2.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Code lineaire . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.1 Les paramètres d’un code linéaire sur A . . . . . . 10
2.2.2 Encode d’un code linéaire . . . . . . . . . . . . . . 11
2.2.3 Décoder d’un code linéaire . . . . . . . . . . . . . . 14
2.2.4 Code de Hamming . . . . . . . . . . . . . . . . . . 17

3 Code linear sur les anneaux fini 19

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 19

2
 INTRODUCTION

Introduction
La theorie des codes constitue un pilier fondamentale des télécom-
unication moderne et des systemes de stockage numérique. Cette
discipline mathematique née des travaux poinniers de Claude
Shannon dans les années 1940, a pour objet principale la concep-
tion de méthode efficese de detection et de correction d’erreurs
de la transmition d’information sur des cannaux bruités. Les
codes correcteurs d’erreurs permettent de garantir l’integritée
des donnée malgré les perturbation inévitables lors de leurs trans-
mission a de leur stockage en ajoutant une redondance strecturée
use message originale.
Dans ce cadre,l’étude des codes linéaires sur les anneaux finis
représente une généralisation profonde et fructueuse de la théorie
classique des codes correcteurs d’erreurs. Alors que les codes tra-
ditionnels opèrent dans le cadre des corps finis - dont la théorie
est bien établie depuis les travaux fondateurs de Hamming (1950)
et Golay (1949) - les codes sur anneaux offrent une richesse
algébrique supplémentaire qui permet de résoudre des problèmes
jusque-là inaccessibles.

3
CHAPITRE 1
PRÉLIMINAIRES

Dans ce chapitre, nous allons présenter quelques structures algébriques.

Nous donnerons certaines propriétés que nous utilisons dans cette thèse.
Nous allons définir les anneaux, les idéaux et les modules, qui sont des
outils fondamentaux pour établir les définitions des codes sur anneaux.

1.1 Généralitées
Définition 1. Un anneau est un ensemble A muni de deux lois de compo-
sition 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, commutative, et distributive à gauche et à
droite par rapport à la loi +.
3. La loi × possède un élément neutre noté 1A .

Définition 2. Soit A, +, × un anneau et B un sous-ensemble de A. On

dit que B est un sous-anneau de A lorsque
1. 1A ∈ B,
2. B est stable par + et par ×.
3. Pour tout élément x ∈ B, on a −x ∈ B.

1.1.1 Idéaux
Dans tout la suite A est supposée commutatif.

Définition 3. Un sous-ensemble I d’un anneau A est appelé idéal si et

seulement si :
1. I est un sous-groupe de (A, +),

4
 2. pour tout ϑ ∈ A et tout x ∈ I, on a ϑx ∈ I.

Définition 4. Soit I = ⟨ϑ⟩ ;

1. S’il existe un entier n ̸= 0 tel que ϑn = 0, alors l’élément ϑ d’un

anneau A est dit nilpotent.
2. L’ensemble des éléments nilpotents de A est appelé le Nilradical
de A et noté Nil(A).

Les énoncés suivants démontrent la relation entre Nil(A) et les idéaux

premiers de l’anneau.

Propriété 1. L’intersection de tous les idéaux premiers de A est le nilra-

dical de A.

démonstration 1. Soit x ∈ p p, c’est-à-dire que x appartient à tous les

T

idéaux premiers de A.
Montrons que x est nilpotent.
Supposons par l’absurde que x n’est pas nilpotent, c’est-à-dire que pour
tout n ≥ 1, xn ̸= 0.
Considérons l’ensemble

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

Cet ensemble est non vide car (0) ∈ S sous notre hypothèse.
Par le lemme de Zorn, il existe un idéal maximal m dans S.
On peut montrer que cet idéal maximal m est un idéal premier ne
contenant aucun xn .
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 xn = 0 pour un certain n.

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

Par conséquent, \
p = Nil(A).
p idéal premier

5
Propriété 2. Un anneau local n’a qu’un seul idéal maximal nilpotent.

démonstration 2. 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 à Nil(A) = si=1 Pi = P .
T

Définition 5. Un anneau possédant un unique idéal maximal est un an-

neau 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.

1.2 Anneaux de Galois

Nous introduisons ici les anneaux de Galois, qui sont utilisés dans de
nombreux domaines des mathématiques, en particulier la théorie du codage.

Définition 6. Si A est commutatif, unitaire, et que l’ensemble de ses di-

viseurs de zéro est de la forme pA, où p est un nombre premier, alors A
est un anneau de Galois.

remarque 1. 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 = Zpm , l’anneau des entiers
modulo pm .
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) = pm , m ∈ N.

d. L’anneau Zpm est un anneau local pour p premier.

6
1.3 Modules
Définition 7. Un A-module (E, +, .) est un ensemble muni d’une loi in-
terne + 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 8. 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 .

remarque 2. Soit (Mt )t∈I une famille de A-modules où I est un en-
semble fini ou non. Alors le produit t∈I Mt est un S-module pour les
Q

lois évidentes ; on l’appelle le produit des S-modules Mt .

La définition suivante est analogue à celle qu’on a pour les espaces

vectoriels :

Définition 9. Soit (Mt )t∈I une famille de A-modules. La somme directe

(externe) des Mt , notée t∈I Mt , est le sous-module de t∈I Mt constitué
L Q

des familles presque nulles (Mt )t∈I . Si I est fini, la somme directe coı̈ncide
avec le produit direct.

Définition 10. 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 une famille (xt )t∈I telle que tout élément x de M s’écrit
de manière unique x = t∈I αt xt , avec (αt )t∈I une famille presque nulle
P

d’éléments de A.

7
CHAPITRE 2
THEORIE DES CODES - CODES
CORRECTEURS

2.1 Généralités
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’orthographes, d’une diction trop rapide ou bien de bruits perturbateurs.
Toutefois, il n’est pas toujours nécessaire d’obtenir l’intégralité du mes-
sage pour en deviner 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. Onconstate que le transfert d’infor-
mations 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’infor-
mations soit minimale : c’est là qu’interviennent les codes correcteurs..
Lors de la transmission, C traverse un canal bruité qui peut l’altérer.
Le récepteur reçoit alors une version corrompue Ĉ du mot de code. Le
problème fondamental est que le récepteur ne connaı̂t pas initialement le
message original x.

k symboles n symboles n symboles

source u codeur c canal y décodeu
bruit e

Dans la suite, Soit A un anneaux fini.

Définition 11.
Soit A un Anneaux fini (Alphabet) ; Un code C de langeure ”n” sur A
est un s-ensemble de An
Exemple 1.

8
 1-Code de Parité (ASCII 8 bits)
x=65 : ’C’=(01000001).
x=67 ; ’C’=(01000011).
2- Code de Hamming (7,4)
x=1011
’C’=1011010.
3-Le code ISBN (International Standard Book Number) est utilisé mon-
dialement par les éditeurs pour identifier les propriétés d’un livre.

Code DE Hamming
Les codes de Hamming sont une famille de codes correcteurs d’erreurs
linéaires conçus pour détecter et corriger les erreurs dans les transmissions
de données. Ils ont été inventés par Richard Hamming en 1950 et sont
largement utilisés dans les télécommunications, la mémoire informatique
et d’autres systèmes où des erreurs de transmission peuvent survenir.
Définition 12. :
(a) La distance définie dans la proposition 3.2 ci-dessus s’appelle la distance
de Hamming du code C.
(b) La distance minimale du code est donnée par :
d := min{d(a, b) | a, b ∈ C, a ̸= b}
où d(a, b) représente la distance de Hamming entre deux mots de code.
Pour n, d fixés, on notera le nombre maximum de mots de code de
longueur n et de distance minimale d par Aq (n, d). Des relations existent
entre les paramètres n, d, M , q et Aq (n, d), où :
— q : est le cardinal de l’alphabet (q = 2 pour un alphabet binaire)
— M : est le nombre de mots de code (M = |C|)
Théorème 1.
(a) Pour n ≥ 1,
Aq (n, 1) = q n et Aq (n, n) = q.
(b) Pour n ≥ 2,
Aq (n, d) ≤ qAq (n − 1, d).
(b) Pour n ≥ 2,
Aq (n, d) ≤ qAq (n − 1, d).
(c) Pour un code binaire,
A2 (n, 2t + 1) = A2 (n + 1, 2t + 2).
(d) Borne de Gilbert-Varshamov :
qn
Aq (n, d) ≥ Pd−1 n k
.
k=0 k (q − 1)
9
(e) Borne de Singleton :

Aq (n, d) ≤ q n−d+1 .

(f) Borne d’empilement des sphères : Pour t = ⌊ d−1

2 ⌋,

qn
Aq (n, d) ≤ Pt 
n
 .
k=0 k (q − 1)k
q−1
(g) Borne de Plotkin : Avec θ = q , si d ≥ θn alors

d
Aq (n, d) ≤ .
d − θn

2.2 Code lineaire

Un code général peut n’avoir aucune structure particulière et ne pas ad-
mettre d’autre représentation qu’une énumération exhaustive de tous ses
mots de code. Nous nous concentrons maintenant sur une sous-classe im-
portante de codes possédant une structure algébrique additionnelle : les
codes linéaires. De nombreux codes importants et largement utilisés sont
linéaires.

Définition 13. :
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 2. Soit le code C1 ⊂ Z34 défini par :

C1 = {000, 121, 202, 323}

:
C1 est un sous-module de Z34 car stable par addition :

121 + 202 = 323 ∈ C1

121 + 323 = 444 ≡ 000 ∈ C1
202 + 323 = 525 ≡ 121 ∈ C1

De plus, C1 est stable par multiplication scalaire dans Z4 .

2.2.1 Les paramètres d’un code linéaire sur A

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′ ) ∈
An est le nombre de coordonnées pour lequel c, c′ diffèrent :

10
 d(c, c′ ) = |{i : ci ̸= c′i }|
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′ ) | c, c′ ∈ C, c ̸= c′ }
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 ̸= 0}

2.2.2 Encode d’un code linéaire

Matrices génératrices
La matrice génératrice est l’outil fondamental pour encoder efficacant en
mots de code dans un code linear, tout en assurant la structure algébrique
necessaire à la correction d’erreurs.

Définition 14. :
Une matroce génératrice d’un code linéaire sur un anneaux 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 etre independants sur A.

Exemple 3. 
: 
1 1 0 0
0 1 0 0
La matrice 
 


0 0 1 1

encode (1, 1, 1) comme (1, 1, 1, 1) et (1, 0, 0) comme (1, 0, 0, 0).

Remarquez que uG est une combinaison linéaire des lignes de la matrice
génératrice, donc C est l’espace des lignes de G.

11
 .

Soit A un anneau à chaı̂ne fini d’idéal maximal ⟨γ⟩, et e l’indice de

nilpotence de γ, de corps résiduel Fq = Fpr où p est un nombre premier et
gcd(n, p) = 1.
Théorème 2. .
Soit C un code linéaire sur A,à une permutation des coordonnées prés C
admet une matrice génératrice G sous la forme standard suivante :

Ik A0,1 A0,2 · · · A0,e−1 A0,e

 
 0
 0 γIk γA1,2 · · · γA1,e−1 γA1,e 

 1 
G= 0 0 γ 2 Ik2 · · · γ 2 A2,e−1 γ 2 A2,e 
 
 . .. .. ... .. ..
 
 ..

 . . . . 

0 0 0 · · · γ e−1 Ike−1 γ e−1 Ae−1,e

Où les Ai,j sont des matrices de taille ki × kj à coefficients dans A,

et Iki est la matrice identité de taille ki , et tous les éléments dans γ i Aij
(0 ≤ i ≤ e − 1, 1 ≤ j ≤ e) sont dans (γ i ).

On dit que C est de type {k0 , k1 , . . . , ke−1 }. Ce qui implique que son
cardinal est :
Pe−1 Pe−1 Pe−1
ki ki ki
|C| = |A/⟨γ⟩| i=0 = |Fq | i=0 =q i=0 .
Pe−1
On définit ke = n − i=0 ki .
‘
Définition 15. 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).
remarque 3. Sur Z4 , il existe un code auto-dual de longueur n sur A si et
seulement si n est pair. Si n est pair, il existe un code auto-dual de longueur
n appelé le code auto-dual trivial donné par sa matrice génératrice :

G = γ e/2 In ,

où In est la matrice identité d’ordre n et γ engendre l’idéal maximal.

Le rang libre de C est défini comme le plus grand rang des sous-
modules de C. Un code linéaire est dit libre si son rang libre est égal à son

12
rang. Dans ce cas, le code est un A-sous-module libre isomorphe à Ak(C) ,
et possède une base à k(C) éléments.
Par conséquent, dans ce cas, une matrice génératrice de C sous forme
standard est donnée par :
 
G = Ik M ,

pour une certaine matrice M de taille appropriée.

Code dual d’un code linéaire

Définition 16. On munit An du produit suivant : v · w = vi wi . Le code
P

dual C ⊥ de C est défini par

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

Exemple 4. Soit le code

C = {0000, 1111}.

Le code dual C ⊥ est donné par

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

Propriété 3. 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.

Définition 17. 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 4. 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 }.

13
2.2.3 Décoder d’un code linéaire
Matrice de controle
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.
Autrement dit, 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 dimen-
sion 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,

HGT = 0 =⇒ GH T = 0
(où (·)T désigne la transposition). De plus,

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

Par conséquent, les lignes de H engendrent ker(G). Ainsi, une matrice
de contrôle d’un code linéaire peut être calculée en trouvant une base du
noyau d’une matrice génératrice du code.
Dans le cas particulier où G est une matrice systématique ( I | M ), on
peut prendre la matrice H = (M T | I ) de taille (n−k) × n comme matrice
de contrôle.
Exemple 5. 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
14
 On vérifie que HGT = 0 et que dim ker(H) = 7 − rang(H) = 4 =
rang(G). On peut vérifier par un calcul exhaustif que le poids de Hamming
minimal de tout mot de code non nul est égal à 3. □

Définition 18. 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é,

w = m + e,

avec m un mot du code et e le vecteur d’erreur. Ainsi,

HwT = H(m + e)T = HmT + HeT = HeT ,

car m appartient au code, donc HmT = 0.

Le mot erroné et l’erreur ont donc le même syndrome. L’ensemble des
mots associés à un syndrome donné est appelé classe latérale (ou coset) de
W.
Corriger w revient donc à trouver le mot d’erreur e de poids minimal
vérifiant w = m + e avec m ∈ C dans la classe latérale de w. 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.

Propriété 4. Chaque syndrome est associé à un unique mot m ∈ Fn2 dont

le poids w(m) vérifie w(m) ≤ w(e) avec e ∈ C.

démonstration 3. Supposons qu’il existe m, m′ ∈ Fn2 tels que w(m), w(m′ ) ≤

w(e), m, m′ ∈
/ C et
HmT = Hm′T .
Alors,
H(m − m′ )T = HmT − Hm′T = 0,
ce qui implique que m − m′ ∈ C, car le noyau de H est le code C.
Or,
w(m − m′ ) ≤ w(m) + w(m′ ) ≤ 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 − m′ = 0 =⇒ m = m′ .

On peut maintenant dresser une liste des syndromes de chaque élément

de Fn2 pour pouvoir retrouver l’erreur et, à fortiori, le mot codé.

15
 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 w = m + ei .
Le syndrome de ei est donc la i-ème colonne de H, ce qui permet de
localiser facilement l’erreur.

Propriété 5. 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).

démonstration 4. On vérifie que

 
I
 k  = −B T I + I
HGT = −B T In−k T T
 
k n−k B = −B + B = 0.
B

Ainsi, HGT = 0, ce qui montre que les lignes de H sont orthogonales

aux lignes de G, et que H est bien une matrice de contrôle du code.

Exemple 6. Prenons  
1 0 1 0
G= .
0 1 1 1
Ainsi,  
1 1 1 0
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 = Hz T =   = .
0 1 0 1  0
 0
1
Cela correspond à la troisième colonne de H, l’erreur provient donc du
troisième bit.

Théorème 3. Soit C un code.

— Si d ≥ s + 1, alors C peut détecter au plus s erreurs.

— Lorsque s = 2t, on en déduit que C peut corriger au plus t erreurs.

16
Définition 19. 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 n
= 2n−k
X
 
i=0 i

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.

2.2.4 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 n
= 2n−k =⇒ 1 + n = 2r
X
 
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 20. 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.

Exemple 7. É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 , soit p : F42 → F32 telle que p1 = d1 + d2 + d4 , p2 = d1 + d3 + d4 ,
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

17
 Essayons d’encoder un mot, de modifier un de ses bits et de le décoder.
Prenons m = (1010)
 

1 0 0 0 1 1 0
0 1 0 0 1 0 1
mG = (1010) 
0
 = (1010101)

0 1 0 0 1 1

 
0 0 0 1 1 1 1

Modifions le 4ème bit (1010101) → (1011101). 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

On a bien H(1011101)T = (0 0 1)T . Calculons le syndrome du message

erroné :
 
1 1 0 1 1 0 0
T
1 0 1 1 0 1 0 = (111).
(1011101) H = (1011101) 
 


0 1 1 1 0 0 1

On obtient trois 1, il y a donc une erreur sur les trois bits de parité ;
l’erreur 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.

18
CHAPITRE 3
CODE LINEAR SUR LES ANNEAUX
FINI

3.1 Introduction
Les codes linéaires sur les anneaux finis unitaires ont récemment suscité
un intérêt croissant, tant pour leur nouveau rôle en théorie algébrique des
codes que pour leur application réussie dans les systèmes combinant codage
et modulation. Dans cet article, nous abordons la construction de nouveaux
codes cycliques, BCH, alternants, Goppa et Srivastava sur des anneaux
commutatifs locaux finis unitaires. Bien que similaires aux constructions
sur les corps finis, elles nécessitent de travailler avec des extensions galoi-
siennes d’anneaux où certaines propriétés des extensions de corps sont per-
dues. Ces développements répondent aux exigences de fiabilité des systèmes
numériques modernes à haut débit, où le codage correcteur est devenu in-
contournable dans la conception des systèmes de communication et des
ordinateurs. Nous montrons également que les codes sur des alphabets finis
moins structurés que les corps finis (comme les anneaux finis) peuvent être
plus adaptés aux communications entre machines.
[einstein1921] [turing1936]

19