Introduction aux codes correcteurs d’erreurs

100

001

<yyyyyyyy

"EEEEEEEE

111

010

correction /

111

111

111

000

000

echec

de la

correction /

000

deux erreur

une erreur

3 erreurs

000

111

3 erreurs

111

000

(erreurs non detectees)

En résumé, le code de répétition pure (1, 3) est tres satisfaisant vis a vis

des points 2 et 3, et satisfaisant vis a vis du point 4, mais inacceptable vis a

vis du point 1. Généralisons maintenant l’algorithme de décodage qu’on a mis

en oeuvre. On est amené à définir proprement cette notion de ”proximité” et

d´”éloignement”.

Définition 2.4 (Poids et distance de Hamming)

Soient m et m0 deux mots de {0, 1}k.

On appelle distance de Hamming entre m et m0, et on note d(m, m0) le

nombre de lettres distinctes de m et m0.

On appelle poids de m, et on note w(n) le nombre de lettres non nulles de m

(donc le nombre de bits de m égux à 1).

Anecdotiquement, on a les deux relations suivantes : d(m, m0) = w(m + m0) et

donc w(m) = d(m, 00...0), ou + désigne l’addition bit a bit (avec 1 + 1 = 0 . . .)

/

/

<

/

/

"

/

/

<

/

/

"

/

/

/

/

/

/

/

/

/

/

<

/

/

"

/

/

<

/

/

"

/

/

/

/

/

/

/

/

6 CHAPITRE 2. LES TROIS PRINCIPAUX PARAM ÈTRES D’UN CODE

Algorithme général de décodage (na¨ıf ) :

Etant donné le mot reçu r, on cherche le mot de code m qui réalise le minimum

de d(r, m), et on décode r par m

Cet algorithme souleve deux problemes :

a) Sa complexité est en O(n.2k). C’est acceptable si k est petit comme dans

le cas du code de répétition pure (1, 3), mais c’est impraticable dès que k est

grand. Or, pour satisfaire le point 1, il est clair que k doit être grand.

b) A priori, rien ne garantit que le mot de code qui réalise le minimum de d(r, m)

soit unique. C’est le cas du code de répétition pure (1, 3), mais les codes ayant

cette propriété (codes parfaits) sont très rares.

Dans les prochains cours, on élaborera donc des stratégies afin d’obtenir des

codes pour lesquels on a des algorithmes de décodage plus rapides.

2.3 Distance minimale d’un code

Définition 2.5

Soit φ un code d’image C.

On appelle capacité de détection de φ le plus grand entier ed tel qu’on soit tou-

jours capable de détecter ed erreurs ou moins.

On appelle capacité de correction de φ le plus grand entier ec tel qu’on soit tou-

jours capable de corriger ec erreurs ou moins.

On appelle distance minimale de φ et on note dφ (ou dC) la plus petite distance

non nulle entre deux mots de code.

On a ec = dφ − 1 et ec = b dφ−1

2 c

Notation :

La distance minimale d’un code quantifie donc sa qualité vis à vis du point 1.

C’est un paramètre important. En abrégé, ”un code de dimension k, de longueur

n et de distance minimale d” se dira ”un code de paramètres (k, n, d)” ou même

”un code (k, n, d)”.

Exemple 2.6 (code de répétition pure (1, 3))

Prenons l’exemple où φ est le code de répétition pure (1, 3).

Son image est C = {000, 111} donc sa distance minimale dφ est d(000, 111) = 3

On retrouve bien ed = dφ − 1 = 2 et ec = b dφ−1

2 c = 1 comme attendu.

2.3. DISTANCE MINIMALE D’UN CODE

7

Exemple 2.7 (code par bit de parité (8, 9))

Prenons maintenant l’exemple où φ est le code par bit de parité (8, 9).

Son image C a 28 = 256 éléments. Il est donc exclu de comparer tous les mots

de code distincts : il nous faudrait faire 9 ∗ C 2

Néanmoins, on peut établir que sa distance minimale dφ est 2.

256 = 293760 comparaisons !

Démonstration :

· 000000000 et 000000011 appartiennent à C (ce sont les deux premiers mots de

code) donc la distance minimale dφ vérifie dφ ≤ d(000000000, 000000011) = 2.

· Prenons deux mots de code distincts. Ils s’écrivent a1...a8p et a0

8p0 avec

p = a1 + ... + a8 et p0 = a0

– ou bien d(a1...a8, a0

– ou bien d(a1...a8, a0

8. Alors de deux choses l’une :

8p0) ≥ 2

8) ≥ 2 et alors a fortiori d(a1...a8p, a0

8) = 1, c’est à dire qu’il y a exactement une lettre

8, et donc que p = a1 +...+a8 6=

8p0) = 2

1...a0

de différence entre les mots a1...a8 eta0

1 + ... + a0

a0

8 = p0 ; il s’ensuit alors que d(a1...a8p, a0

1 + ... + a0

1...a0

1...a0

Cette analyse montre que dans tous les cas on a d(a1...a8p, a0

donc que la distance minimale dφ vérifie dφ ≥ 2.

· En conclusion, dφ = 2.

On retouve alors comme prévu ed = dφ − 1 = 1 et ec = b dφ−1

8p0) ≥ 2, et

1...a0

1...a0

1...a0

1...a0

2 c = 0

8 CHAPITRE 2. LES TROIS PRINCIPAUX PARAM ÈTRES D’UN CODE

Chapitre 3

Généralités sur les codes

linéaires

3.1 Définitions d’un code linéaire

Définition 3.1 (code linéaire)

Un code φ de paramètres (k, n) est dit linéaire s’il existe une matrice G ∈

Mn,k(F2) (c’est a dire avec n lignes, k colonnes, a coefficients dans {0, 1}), de

rang k, telle que ∀m ∈ {0, 1}k, φ(m) = G × m.

La multiplication matricielle est a comprendre dans F2 (c’est a dire modulo

2) et le mot m est ici considéré comme un vecteur colonne. La condition sur le

rang traduit l’injectivité de φ.

La matrice G est appelée matrice génératrice de φ.

Enfin, dire que le code φ est systématique, c’est dire que la matrice G est le

la forme

, où Ik est la matrice identité d’ordre k.

(cid:19)

(cid:18) Ik

G0

Exemple 3.2

a) Considérons φ, code linéaire de matrice génératrice









1

0

1

1









0

1

0

1

C’est un code de dimension 2, de longueur 4, donné par le tableau :

φ(x)

x

00 0000

01 0101

10 1011

11 1110

b) Tous les codes rencontrés jusqu’à présent, exception faite du code du td 1,

exercice 3, sont linéaires.

9

(cid:19)

I8

1 . . . 1





1

1

1

10

CHAPITRE 3. G ÉN ÉRALIT ÉS SUR LES CODES LIN ÉAIRES

(cid:5) Pour le code de bit de parité (8, 9), la matrice génératrice est

(cid:18)

(cid:5) Pour le code de répétition pure (1, 3), la matrice génératrice est





(cid:5) Pour le code du td 1, exercice 4, la matrice génératrice est

0

0

1

0

1

1

Le caractère systématique de ces codes se lit sur la matrice génératrice.















1

0

0

1

0

1

0

1

0

1

1

0



















c) Un code de Hamming systématique de paramètres (4, 7) est le code

linéaire a1a2a3a4 7→ a1a2a3a4b5b6b7 avec b5 = a1 + a2 + a3, b6 = a1 + a2 + a4,

b4 = a1 + a3 + a4. Comme on le verra par la suite, il y a d’autres codes de Ham-

ming systématiques de parametres (4, 7) : un tel code consite en fait a rajouter à

a1a2a3a4 trois bits de parité correspondant à trois choix distincts de 3 éléments

parmi a1, a2, a3, a4. La matrice génératrice de celui-ci est :























1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1

1 1 1 0

1 1 0 1

1 0 1 1



















On peut déjà remarquer que les codes linéaires se comportent de façon satis-

faisante (mais sans plus) vis à vis du point 3 : l’algorithme de codage est en

effet une multiplication matricielle, dont le coût est en O(n × k), et même en

O((n − k) × k) dans le cas d’un code systématique.

3.2 Distance minimale d’un code linéaire

Les codes linéaires sont également intéressants car on dispose d’informations

sur leur distance minimale. Tout d’abord, par définition, dire qu’un code φ de

paramêtres (k, n) est linéaire, c’est exactement dire que φ est une application

linéaire injective de {0, 1}k dans {0, 1}n. D’où la propriété suivante :

Remarque 3.3

Soit φ un code linéaire. Alors son image C est un sous-espace vectoriel de {0, 1}n

Autrement dit

−→

0 ∈ C et ∀m, m0 ∈ C, m + m0 ∈ C.

On en déduit le sympatique corollaire suivant :

3.3. MATRICE DE CONT ÔLE D’UN CODE LIN ÉAIRE

11

Proposition 3.4 (distance minimale d’un code lináire)

Soit φ un code linéaire d’image C.

Alors la distance minimale de φ dφ est égale au plus petit poids non nul d’un

mot de C.

Démonstration : La distance minimale est le plus petit élément non nul de

l’ensemble des distances entre deux mots de code. Il suffit donc de montrer que

cet ensemble co¨ıncide avec l’ensemble des poids des mots de code. Tout d’abord,

tout poids est une distance car w(m) = d(m, 0...0). Ensuite, toute distance est

un poids car d(m, m0) = w(m + m0) et si m, m0 ∈ C on a aussi m + m0 ∈ C.

Dans le cas d’un code de dimension 3 ou 4, ce critère permet de calculer beau-

coup plus facilement la distance minimale. Par exemple, on peut voir que le

code de Hamming proposé précédemment est de distance minimale 3, donc 1-

correcteur. Mais ce calcul reste coûteux en général.

On dispose d’autres critères sur la distance minimale des codes linéaires. Celui

qui suit donne la limite de ce qu’on peut espérer :

Définition 3.5 (borne de Singleton)

La distance minimale d d’un code linéaire de dimension k et de longueur n

vérifie d ≤ n + 1 − k.

Un code pour lequel on a égalité est dit MDS (Maximum Distance Separable).

Démonstration : (un peu technique, n’est pas à comprendre)

D’après 3.4, il suffit d’exhiber dans C un vecteur non nul de poids inférieur ou

égal à n + 1 − k. Par exemple, s’il existe dans C un mot non nul dont les k − 1

dernières composantes sont nulles, le résultat est acquis.

Mais justement ! Considérons l’ensemble E des mots dont les k − 1 dernières

composantes sont nulles : c’est un sous-espace vectoriel de dimension n − k − 1

de {0, 1}n. Pour sa part, C est un sous-espace vectoriel de dimension k. On a

donc dim(C) + dim(E) = n + 1 > n et donc C ∩ E contient au moins un élément

non nul.

On peut encore avoir un autre critère sur la distance minimale d’un code

linéaire : il est donné par la matrice de contrôle du code.

3.3 Matrice de contôle d’un code linéaire

L’intérêt principal de ne considérer que des codes linéaires est qu’ils disposent de

meilleurs algorithmes de décodage. On utilise pour cela les matrices de contrôle.

12

CHAPITRE 3. G ÉN ÉRALIT ÉS SUR LES CODES LIN ÉAIRES

Définition 3.6 (Matrice de contrôle)

Soit φ un code linéaire (k, n) de matrice génératrice G.

On appelle matrice de contrôle de φ toute matrice H ∈ Mn−k,n (c’est à dire

avec n colonnes et n − k lignes) telle que H.m =

−→

0 ⇔ m ∈ C.

L’existence de matrices de contrôle pour n’importe quel code linéaire φ n’étonnera

pas les spécialistes de l’algèbre linéaire : H n’est rien d’autre qu’une matrice dont

le noyau est l’image de G. Il est clair que de telles matrices existent toujours.

Au passage, comme le noyau de H est C, H contient assez d’information pour

reconstituer φ a équivalence pres.

En revanche, on remarque que H n’est pas unique en général (par exemple, en

permutant deux lignes d’une matrice de contrôle, on obtient encore une matrice

de contrôle).

Etant donné la matrice génératrice G d’un code φ, se donner une matrice de

contrôle H, c’est se donner une base de l’orthogonal de C dans {0, 1}n, ce qui

n’est pas évident.

L’opération inverse est plus facile : étant donné une matrice de contrôle H,

se donner la matrice génératrice G d’un code φ correspondant revient à se don-

ner une base du noyau de H.

Le théoreme suivant donne un critere très simple pour déterminer une ma-

trice de contrôle d’un code systématique.

Théorème 3.7 (matrice de contrôle d’un code systématique)

Soit φ un code systématique de matrice génératrice

Alors la matrice H = (cid:0) G0

In−k

(cid:1) est une matrice de contrôle de G.

(cid:18) Ik

G0

(cid:19)

.

Exemple 3.8

a) Une matrice de contrôle du code de bit de parité (8, 9) est (cid:0) 1

b) Une matrice de contrôle du code de répétition pure (1, 3) est

1

1

1

1 (cid:1).

1

1

(cid:18) 1

0

1

0

1

1

1

1

(cid:19)



a la premiere section est

c) Une matrice de contrôle du code du code de Hamming systématique présenté

0

1

1

cette matrice consiste simplement à écrire en colonne tous les mots de 3 bits.

Une autre énumétation aurait correspondu à un autre code de Hamming (7, 4).

. On pourra remarquer que

0

1

0

1

1

1

1

0

1

0

0

1

1

0

0

1

1

0





3.4. D ÉCODAGE D’UN CODE LIN ÉAIRE

13

Proposition 3.9 (distance minimale et matrice de contrôle)

Soit φ un code linéaire de matrice de contrôle H.

Alors dφ est le nombre minimal de colonnes de H linéairement dépendantes.

Par exemple :

– Si H a une colonne nulle, on a dφ = 1

– Sinon, et si H a deux colonnes identiques, on a dφ = 2

– Sinon, et si une colonne de H est égale à la somme de deux autres, on a

dφ = 3, etc.

Démonstration : Il suffit de se rappeler que les colonnes de H forment une

base de son image, donc de ker(G) = C, et d’invoquer 3.4.

Remarquons qu’avec ce lemme on peut retrouver que le code de Hamming

présenté plus haut a bien pour distance minimale 3.

3.4 Décodage d’un code linéaire

Définition 3.10 (Mot erreur et syndrome)

Soit φ un code de paramètres (k, n), de matrice génératrice G et de matrice de

contrôle H. On se fixe un mot de source X (mot de longueur k). Le mot de

code correspondant sera φ(X) = Y . Il y a éventuellement des erreurs durant la

transmission et on reçoit le mot Z.

On appelle mot erreur associé à Z le mot E = Z + Y .

On appelle syndrome de Z le mot H × Z.

On note Ei le mot ne contenant que des 0, sauf en position i.

Quelques commentaires sur cette définition :

Comme E = Y + Z, on a Z = Y + E, et donc E quantifie bien les erreurs surve-

nues sur Y : par exemple, w(E) est le nombre d’erreurs survenues. Le problème

du décodage peut se reformuler : ”trouver E”, car alors on déduit Y .

Bien sûr, ce ”trouver E” est à comprendre dans le sens ”trouver E le plus pro-

bable”, c’est à dire ”trouver E de poids minimal”.

Dire que le syndrome de Z est nul, c’est dire que Z est un mot du code : dans

ce cas le mot erreur le plus probable est le mot nul.

Remarque 3.11

Soit Z un mot de syndrome S.

Alors E est aussi de syndrome S car H × E = H × (Z + Y ) = H × Z + H × Y

et Y est un mot du code.

L’ensemble des mots de syndrome S est appellé classe lattérale de Z.

Le problème de décodage se reformule donc : ”trouver le mot de plus petit poids

dans la classe lattérale de Z”.

... s’il existe !

14

CHAPITRE 3. G ÉN ÉRALIT ÉS SUR LES CODES LIN ÉAIRES

Par exemple :

(cid:5) Dire que le mot nul est dans la classe lattérale de Z, c’est dire que le syn-

drome S = H × Z est nul. Dans ce cas, le mot de poids minimal dans la classe

lattérale de Z est le mot nul, il faudra donc corriger Z par φ−1(Z).

(cid:5) Supposons donc que le syndrome de S = H × Z est non nul. Dire qu’il existe

un mot de poids 1 dans la classe lattérale de Z, c’est dire que le syndrome S

est égal à une colonne Ci de H. Dans ce cas, s’il existe une seule colonne Ci de

H égale au syndrome, le mot de poids minimal dans la classe lattérale de Z est

Ei, il faudra donc corriger Z par φ−1(Z + Ei), où Ei est le mot ne contenant

que des zéros, sauf en position i.

(cid:5) Supposons donc que le syndrome de S = H × Z est non nul, et distinct

de toutes les colonnes de H. Dire qu’il existe un mot de poids 2 dans la classe

lattérale de Z, c’est dire que le syndrome de Z est égal à la somme de deux

colonnes Ci1 + Ci2 de H. Dans ce cas, et si c’est la seule façon d’obtenir le syn-

drome comme somme de deux colonnes de H, le mot de poids minimal dans la

classe lattérale de Z est Ei1 + Ei2, il faudra donc corriger Z par φ−1(Ei1 + Ei2).

... un algorithme prend forme !

Dans ce qui précède, le point délicat est l’unicité ”du” mot de poids minimal

dans la classe lattérale de Z. Par exemple, si deux colonnes Ci et Cj de H sont

égales a S = H ×Z, on ne sait pas corriger. Pour commencer, faisons l’hypothese

que ce cas de figure ne se produira jamais. Il suffit pour cela de renoncer à corri-

ger au delà de la capacité de correction, car un mot de poids p ≤ ec peut s’écrire

au plus d’une seule façon comme somme de colonnes de H.

Algorithme de décodage des codes linéaires, 1ere version :

C’est un algorithme de décodage en deçà de la capacité de correction,

donc non optimal (sauf si le code est parfait).

Etape 1) : on calcule S = H × Z

Etape 2) : si S =

−→

0 , on décode Z par φ−1(Z), sinon, on initialise p à 1

Etape 3) : (cid:5) Si il existe p colonnes de H Ci1, Ci1,

Ci1 + Ci1 + . . . + Cip, on décode par φ−1(Z + Ei1 + Ei1 + . . . + Eip)

(cid:5) Sinon, et qu’on a p < ec, on incrémente p et on recommence l’étape 3)

(cid:5) Sinon, et donc qu’on a p = ec, on passe à l’étape 4)

. . . , Cip telles que S =

Etape 4) : échec du décodage

3.4. D ÉCODAGE D’UN CODE LIN ÉAIRE

15

Remarque : Les étapes 2) et 3) peuvent fusionner (on initialise p à 0).

L’étape 1) a un coût en O(n × (n − k)).

L’étape 2) a un coût en O(n).

A p fixé, l’étape 3) a un coût en O(C n

p ×p×(n−k)), donc en O(p×(n−k)×np).

Finalement, la complexité de cet algorithme est en O(ec × nec+1 × (n − k)),

ce qui est loin d’être terrible, même si c’est déjà beaucoup mieux que la com-

plexité exponentielle de l’algorithme na¨ıf (si k est grand).

Comment souvent, on peut faire mieux en convertissant une partie de la com-

plexité temporelle en complexité spatiale. En effet, on peut une bonne fois pour

toutes calculer, pour tout p ≤ ec, toutes les sommes possibles de p colonnes de

H, les trier par ordre lexicographique et leur associer le mot erreur E corres-

pondant. Le calcul de toutes les sommes dans l’étape 3) est alors remplacé par

une recherche dichotomique, de coût O(p).

Algorithme de décodage des codes linéaires, 2eme version :

Le même, mais avec un prétraitement consitant à calculer pour tout p ≤ ec

toutes les sommes possibles de p colonnes de H, à les trier par ordre lexicogra-

phique et leur associer le mot erreur E correspondant (par exemple à la somme

de C1 et C3 est associé E = 10100...).

Le coût du prétraitement est en O(ec × nec+1 × (n − k)).

L’algorithme a de plus une complexité en espace en O(ec × nec+1 × (n − k))

La complexité temporelle de l’algorithme lui-même est en O(n × (n − k))

Le défaut non réglé est le caractère non optimal de ces algorithmes. Une

troisieme version, dont la complexité en espace est en O(2n−k), regle ce problème.

16

CHAPITRE 3. G ÉN ÉRALIT ÉS SUR LES CODES LIN ÉAIRES

Algorithme de décodage des codes linéaires, 3eme version :

Précalcul : pour tous les syndromes possibles (les 2n−k mots de longueur n − k),

on calcule le mot de poids minimal de la classe lattérale associée, ce qui nous

donne un tableau de taille (2n−k) (le ie élément est le mot de poids minimal

de la classe lattérale dont le syndrome est i écrit en base 2, s’il existe ; et un

symbole d’échec sinon).

Etape 1) : on calcule S = H × Z et i dont S est l’écriture en base 2

Etape 2) : on selectionne le ie élément E du tableau

Etape 4) : on corrige par φ−1(Z + E)

Le coût de cet algorithme est en O(n × (n − k)), mais la complexité en espace

est très importante, et surtout le précalcul n’est pas réalisable si n est vraiment

grand, car il est en O(n.2n).

Cet algorithme peut être optimisé, en proposant par exemple que s’il y a

plusieurs mots de poids minimal dans une classe lattérale, on choisisse celui, s’il

existe, pour lequel les erreurs sont le mieux groupées.

Chapitre 4

Codes parfaits

4.1 Plusieurs définitions équivalentes

Définition 4.1 (Sphères, boules)

Soit m ∈ {0, 1}n et k ∈ N.

On appelle sphère de centre m et de rayon k, et on note S(m, k), l’ensemble

des mots de {0, 1}n à distance k de m : S(m, k) := {r ∈ {0, 1}n, d(r, m) = k}.

On appelle boule de centre m et de rayon k, et on note B(m, k), l’ensemble

des mots de {0, 1}n a distance inférieure ou égale a k de m :

B(m, k) := {r ∈ {0, 1}n, d(r, m) ≤ k}.

Proposition 4.2 (Cardinal d’une sphère, d’une boule)

Le nombre d’éléments d’une sphère et d’une boule sont donnés par les formules

|S(m, k)| = C k

n

et

|B(m, k)| =

k

X

i=0

C i

n

Remarque : Soit φ un code de capacité de correction ec

(cid:5) Les boules centrées en les mots du code, de rayon ec, sont disjointes

(cid:5) ec est par définition le plus grand entier tel que les boules centrées en les mots

du code de rayon ec soient disjointes, ou autrement dit : des boules centrées en

les mots du code de rayon k sont disjointes si et seulement si k ≤ ec.

Proposition 4.3 (Inégalité de Hamming)

Soit φ un code de paramètres (k, n), d’image C, de capacité de correction ec.

Alors on a :

ecX

C i

n ≤ 2n−k

i=0

17

18

CHAPITRE 4. CODES PARFAITS

Et on appelle cette propriété l’inégalité de Hamming.

Démonstration : On utilise la remarque précédente. L’union des boules de rayon

ec centrées en des mots de code est incluse dans {0, 1}n , et cette réunion

est disjointe, d’où P

m∈C |B(m, ec)| ≤ |{0, 1}n|, enfin, toutes les 2k boules on

n, ce qui donne 2k Pec

le même nombre d’éléments Pec

n ≤ 2n, d’où

l’inégalité cherchée.

i=0 C i

i=0 C i

Définition 4.4 (Codes parfaits)

Soit φ un code de paramètres (k, n), de capacité de correction ec. On dit que φ

est un code parfait s’il vérifie une des trois caractérisations équivalentes sui-

vantes :

(cid:5) Les boules de rayon ec de centre les mots du code forment une partition de

{0, 1}n

(cid:5) φ vérifie le cas d’égalité de l’inégalité de Hamming Pec

que φ vérifie l’égalité de Hamming)

(cid:5) Pour tout mot r ∈ {0, 1}n, il existe un unique mot de code m qui réalise le

minimum de d(r, m)

n = 2n−k (on dit

i=0 C i

4.2 Caractérisation des codes parfaits linéaires

Comme promis, montrons que les codes parfaits sont rares.

Commençons par un exemple.

Définition 4.5 (Codes de Hamming)

Soit m ≤ 2 un entier.

Un code de Hamming est un code de paramètres (2m − m − 1, 2m − 1) dont

une matrice de contrôle est obtenu par n’importe quelle énumération en colonne

de tous les mots de m bits non nuls.

Je sais que vous allez rigoler, mais le minitel (vous savez, ce vieux truc qu’utili-

saient nos trisa¨ıeuls) code ses données avec un code de Hamming étendu par bit

de parité de paramètres (27 − 7 − 1, 27 − 1 + 1) = (120, 128) (on code 15 octets

a l’aide d’un octet supplementaire).

Proposition 4.6 (Distance minimale d’une code de Hamming)

Un code de Hamming a toujours pour distance minimale 3.

Démonstration : Par définition, la matrice de contrôle d’un tel code n’a pas de

colonne nulle donc d ≥ 2 et n’a pas deux colonnes identiques donc d ≥ 3 ; enfin

en faisant la somme de deux colonnes contenant exactement un seul 1 on obtient

un vecteur contenant exactement deux 1, donc une autre colonne, d’où d = 3

4.2. CARACT ÉRISATION DES CODES PARFAITS LIN ÉAIRES

19

Remarque : Un code linéaire de paramètres (2m − 1, 2m − m − 1, 3) est

nécessairement un code de Hamming. En effet, une matrice de contrôle H d’un

tel code doit avoir 2m lignes et m − 1 colonnes, donc contient en colonne des

vecteurs de Fm

2 . Comme d > 1, aucun vecteur colonne de H n’est nul, comme

d > 2, aucun vecteur colonne n’apparaˆıt deux fois. Finalement, il nous faut

placer en colonne m − 1 vecteurs non nuls et distincts de Fm

2 . Comme il y en a

précisément m − 1, il faut tous les mettre et le code considéré est un code de

Hamming.

Posons-nous maintenant la question de trouver tous les codes parfaits de

capacité de correction 1.

Comme les codes parfaits vérifient l’égalité de Hamming, les paramètres d’un

code parfait de capacité de correction 1 doivent vérifier P1

n = 2n−k c’est à

dire 1 + n = 2n−k. Posons m := n − k, on a alors 1 + n = 2m, donc n = 2m − 1

et k = n − m = 2m − m − 1.

i=0 C i

En définitive un code parfait de capacité de correction 1 a nécessairement

les paramètres d’un code de Hamming ; et un code parfait linéaire de capacité

de correction 1 est toujours un code de Hamming (selon la remarque).

Terminons enfin ce chapitre avec un théoreme (a admettre...) qui clos le

débat sur les codes parfaits.

Théorème 4.7 (Codes parfaits linéaires)

Les seuls codes parfaits linéaires (binaires) sont :

– les codes de répétition pure (1, 2ec + 1)

– les codes de Hamming

– le code de Golay G23

Le code de Golay est un code de paramètres (12, 23, 7) sur lequel nous re-

viendrons.

(Véridique : il est tombé à l’examen).

20

CHAPITRE 4. CODES PARFAITS

Chapitre 5

Généralités sur les codes

cycliques

5.1 (R)appels sur les polynômes

Définition 5.1 (Polynômes à coefficients dans F2)

Un polynôme à coefficients dans F2 est une fonction de la forme P (X) =

a0 + a1X + a2X 2 + ... + anX n avec ∀i ∈ {0, ..n}, ai ∈ F2

Si an 6= 0, l’entier n est appelé le degré du polynôme P et noté deg(P ) ; les

entiers ai sont appelés les coefficients de P ; par convention le polynôme nul est

considéré comme étant de degré −∞.

Remarque : (identité remarquable des maternelles)

Le fait de travailler dans F2 nous simplifie grandement la vie.

Par exemple, on a toujours (a + b)2 = a2 + b2

Proposition 5.2

Soit P un polynôme à coefficients dans F2.

Alors P (X 2) = P (X)2

Définition 5.3 (racines)

Soit P un polynôme à coefficients dans F2 et a ∈ F2.

On dit que a est une racine de P lorsque P (a) = 0

Exemple 5.4

(cid:5) Le polynôme X 2 + X a pour racines 0 et 1

(cid:5) Le polynôme X 8 + 1 a pour racine 1 et peut se réécrire (X + 1)8

(cid:5) Le polynôme X 2 + X + 1 n’a pas de racine dans F2. Si l’on veut à tout prix

qu’il ait des racines, il faudra ”imaginer” de nouveaux éléments qui ne sont pas

21

22

CHAPITRE 5. G ÉN ÉRALIT ÉS SUR LES CODES CYCLIQUES

dans F2, de la même façon qu’on construit le corps des nombres complexes en

”imaginant” un nouveau nombre i tel que i2 = −1

Définition 5.5 (factorisation, irreductibilité)

Soit P un polynôme à coefficients dans F2.

(cid:5) S’il existe deux polynômes P1 et P2 tels que P = P1P2, on dira que P1 et P2

divisent P , ou encore que P1 et P2 sont des diviseurs de P . Dans ce cas on

a nécessairement deg(P1) + deg(P2) = deg(P )

(cid:5) S’il existe deux polynômes P1 et P2 tels que deg(P1) ≥ 1, deg(P2) ≥ 1 et

P = P1P2 alors on dit que P1P2 est une factorisation de P .

(cid:5) Si P n’a pas de factorisation, P est dit irréductible

Proposition 5.6 (division euclidienne)

Soient P1 et P2 deux polynômes à coefficients dans F2.

Alors il existe deux polynômes à coefficients dans F2 Q et R, uniques, tels que

P1 = P2 × Q + R et deg(R) < deg(P2)

Q est appelé le qutient de la division euclidienne de P1 par P2 et R le reste.

5.2 Définitions d’un code cyclique

Attention ! A partir de maintenant, les codes considérés ne seront plus nécessairement

systématiques (même si on s’efforcera de repérer et d’étudier ceux qui le sont).

De plus, on considerera désormais les codes ”a équivalence pres”, c’est a dire

qu’on identifiera deux codes qui ont la même image, c’est à dire qu’on identifiera

un code à son image.

Définition 5.7 (code cyclique)

Soit C l’image d’un code de paramètres (k, n).

Le code est dit cyclique si l’ensemble des mots du code est stable par décalage

circulaire.

En d’autres termes, notons σ(m1m2...mn−2mn−1mn) = mnm1m2...mn−2mn−1.

Un code (d’image) C est cyclique si ∀m ∈ C, σ(m) ∈ C.

Exemple 5.8 (Fort heureusement...)

La plupart des principaux codes étudiés jusqu’à présent sont cycliques.

Explicitement :

(cid:5) Les codes de répétition pure (k, n) sont cycliques.

(cid:5) Le code par bit de parité est cyclique.

(cid:5) Le code de Hamming systématique (7, 4) du chapitre 3 est cyclique.

(cid:5...