198
6 Codes correcteurs
Th´ eor` eme 6.18 Si deux corps finis poss` edent le mˆ eme nombre d’´ el´ ements, alors ils
sont isomorphes, c’est-` a-dire qu’il existe un r´ eordonnement des ´ el´ ements du premier
corps tel que les tables d’addition et de multiplication des deux corps co¨ ıncident. Un tel
r´ eordonnement s’appelle un isomorphisme entre les deux corps.
6.6 Les codes de Reed et Solomon
Les codes de Reed et Solomon sont plus complexes que les codes de Hamming.
Nous allons tout d’abord d´ ecrire l’encodage et le d´ ecodage. Puis nous prouverons trois
propri´ et´ es qui caract´ erisent ces codes.
Soient F 2 m le corps ` a 2
m ´ el´ ements et α une racine primitive. Les 2
m
− 1 ´ el´ ements
non nuls de F 2 m sont donc de la forme
{α, α
2 , . . . , α
2
m −1 = 1},
et alors, tous ces ´ el´ ements non nuls satisfont ` a x
2
m −1 = 1.
Les mots ` a encoder seront des mots de k lettres (chacune ´ etant un ´ el´ ement de F 2 m )
o` u k < 2
m
− 2. (Nous expliquerons sous peu comment cet entier k est choisi.) Ainsi,
ce seront des ´ el´ ements (u 0 , u 1 , u 2 , . . . , u k−1 ) ∈ F
k
2 m . `
A chacun de ces mots nous ferons
correspondre le polynˆ ome
p(x) = u 0 + u 1 x + u 2 x
2 + · · · + u k−1 x
k−1
∈ F 2 m [x].
Ces mots seront encod´ es dans un vecteur v = (v 0 , v 1 , v 2 , . . . , v 2 m −2 ) ∈ F
2
m −1
2 m
dont les
composantes seront donn´ ees par
v i = p(α
i ),
i= 0, 1, 2, . . . , 2
m
− 2
o` u α est la racine primitive choisie au d´ epart. Ainsi, l’encodage consiste ` a calculer
v 0 = p(1) = u 0 + u 1 + u 2 + · · · + u k−1 ,
v 1 = p(α) =u 0 + u 1 α + u 2 α
2 + · · · + u k−1 α
k−1 ,
v 2 = p(α
2 ) =u 0 + u 1 α
2 + u 2 α
4 + · · · + u k−1 α
2(k−1) ,
. . . =
. . .
=
. . .
v 2 m −2 = p(α
2
m −2 ) = u 0 + u 1 α
2
m −2 + u 2 α
2(2
m −2) + · · · + u k−1 α
(k−1)(2
m −2) .
(6.12)
Le code de Reed–Solomon C(2
m
− 1, k) est l’ensemble des vecteurs v ∈ F
2
m −1
2 m
ainsi
obtenu. Une des conditions de base de tout encodage est que des mots diff´ erents aient
des formes encod´ ees distinctes. C’est ce qu’assure la propri´ et´ e suivante du code de
Reed–Solomon.
Propri´ et´ e 6.19 L’encodage u → v tel que u ∈ F
k
2 m et v ∈ F
2
m −1
2 m
, est une application
lin´ eaire dont le noyau est nul, c’est-` a-dire ´ egal ` a {0} ⊂ F
k
2 m .
6 Codes correcteurs
Th´ eor` eme 6.18 Si deux corps finis poss` edent le mˆ eme nombre d’´ el´ ements, alors ils
sont isomorphes, c’est-` a-dire qu’il existe un r´ eordonnement des ´ el´ ements du premier
corps tel que les tables d’addition et de multiplication des deux corps co¨ ıncident. Un tel
r´ eordonnement s’appelle un isomorphisme entre les deux corps.
6.6 Les codes de Reed et Solomon
Les codes de Reed et Solomon sont plus complexes que les codes de Hamming.
Nous allons tout d’abord d´ ecrire l’encodage et le d´ ecodage. Puis nous prouverons trois
propri´ et´ es qui caract´ erisent ces codes.
Soient F 2 m le corps ` a 2
m ´ el´ ements et α une racine primitive. Les 2
m
− 1 ´ el´ ements
non nuls de F 2 m sont donc de la forme
{α, α
2 , . . . , α
2
m −1 = 1},
et alors, tous ces ´ el´ ements non nuls satisfont ` a x
2
m −1 = 1.
Les mots ` a encoder seront des mots de k lettres (chacune ´ etant un ´ el´ ement de F 2 m )
o` u k < 2
m
− 2. (Nous expliquerons sous peu comment cet entier k est choisi.) Ainsi,
ce seront des ´ el´ ements (u 0 , u 1 , u 2 , . . . , u k−1 ) ∈ F
k
2 m . `
A chacun de ces mots nous ferons
correspondre le polynˆ ome
p(x) = u 0 + u 1 x + u 2 x
2 + · · · + u k−1 x
k−1
∈ F 2 m [x].
Ces mots seront encod´ es dans un vecteur v = (v 0 , v 1 , v 2 , . . . , v 2 m −2 ) ∈ F
2
m −1
2 m
dont les
composantes seront donn´ ees par
v i = p(α
i ),
i= 0, 1, 2, . . . , 2
m
− 2
o` u α est la racine primitive choisie au d´ epart. Ainsi, l’encodage consiste ` a calculer
v 0 = p(1) = u 0 + u 1 + u 2 + · · · + u k−1 ,
v 1 = p(α) =u 0 + u 1 α + u 2 α
2 + · · · + u k−1 α
k−1 ,
v 2 = p(α
2 ) =u 0 + u 1 α
2 + u 2 α
4 + · · · + u k−1 α
2(k−1) ,
. . . =
. . .
=
. . .
v 2 m −2 = p(α
2
m −2 ) = u 0 + u 1 α
2
m −2 + u 2 α
2(2
m −2) + · · · + u k−1 α
(k−1)(2
m −2) .
(6.12)
Le code de Reed–Solomon C(2
m
− 1, k) est l’ensemble des vecteurs v ∈ F
2
m −1
2 m
ainsi
obtenu. Une des conditions de base de tout encodage est que des mots diff´ erents aient
des formes encod´ ees distinctes. C’est ce qu’assure la propri´ et´ e suivante du code de
Reed–Solomon.
Propri´ et´ e 6.19 L’encodage u → v tel que u ∈ F
k
2 m et v ∈ F
2
m −1
2 m
, est une application
lin´ eaire dont le noyau est nul, c’est-` a-dire ´ egal ` a {0} ⊂ F
k
2 m .