6.6 Les codes de Reed et Solomon
201
ou, de fa¸ con ´ equivalente si
2
m
− s − 1 > s + k − 1.
On en d´ eduit que
2
m
− k > 2s.
Puisque le nombre d’erreurs s est un entier, cette in´ egalit´ e peut ´ egalement ˆ etre ´ ecrite
2
m
− k − 1 ≥ 2s.
En d’autres termes, tant que le nombre d’erreurs s est plus petit ou ´ egal ` a
1
2 (2
m
− k − 1),
la valeur juste u obtiendra le plus grand nombre de d´ eterminations, et nous venons de
prouver la derni` ere propri´ et´ e.
Propri´ et´ e 6.21 Le code de Reed–Solomon peut corriger [
1
2 (2
m
− k − 1)] erreurs o` u la
notation [x] signifie la partie enti` ere de x.
Le d´ ecodage de w consiste donc ` a choisir, parmi toutes les d´ eterminations de u ` a l’aide
de (6.12), celle qui obtient le plus de votes.
Nous terminons cette section en prouvant les propri´ et´ es 6.19 et 6.20.
Preuve de la propri´ et´ e 6.19 Remarquons que chacune des composantes v j de
v, j = 0, 1, . . . , 2
m
− 2, d´ epend lin´ eairement des composantes u i . Ainsi, l’encodage u → v
est une application lin´ eaire de F
k
2 m dans F
2
m −1
2 m
.
Pour montrer que le noyau de cette application est trivial, il suffit de se convaincre
que seul le polynˆ ome nul sera envoy´ e dans 0 ∈ F
2
m −1
2 m
. Si p est un polynˆ ome non nul de
degr´ e k − 1 ou inf´ erieur, il ne peut pas s’annuler pour plus de k − 1 valeurs. Les v i sont
les ´ evaluations du polynˆ ome p pour les puissances α
i , i = 0, 1, 2, . . . , 2
m
− 2. Puisque α
est une racine primitive, toutes les 2
m
− 1 valeurs α
i sont distinctes. Et puisque p n’a
pas plus de k − 1 racines distinctes, seules k − 1 des 2
m
− 1 valeurs v i = p(α
i ) peuvent
ˆ etre nulles. Ainsi, tout polynˆ ome p non nul est envoy´ e sur un vecteur v non nul.
La propri´ et´ e 6.20 d´ ecoule du lemme suivant que nous d´ emontrerons tout d’abord.
Lemme 6.22 (d´ eterminant de Vandermonde) Soient x 1 , x 2 , . . . , x n des ´ el´ ements
quelconques d’un corps F. Alors
1 x 1 x
2
1
. . . x
n−1
1
1 x 2 x
2
2
. . . x
n−1
2
1 x 3 x
2
3
. . . x
n−1
3
. . .
. . .
. . .
. . .
. . .
1 x n x
2
n
. . . x
n−1
n
=
1≤i
201
ou, de fa¸ con ´ equivalente si
2
m
− s − 1 > s + k − 1.
On en d´ eduit que
2
m
− k > 2s.
Puisque le nombre d’erreurs s est un entier, cette in´ egalit´ e peut ´ egalement ˆ etre ´ ecrite
2
m
− k − 1 ≥ 2s.
En d’autres termes, tant que le nombre d’erreurs s est plus petit ou ´ egal ` a
1
2 (2
m
− k − 1),
la valeur juste u obtiendra le plus grand nombre de d´ eterminations, et nous venons de
prouver la derni` ere propri´ et´ e.
Propri´ et´ e 6.21 Le code de Reed–Solomon peut corriger [
1
2 (2
m
− k − 1)] erreurs o` u la
notation [x] signifie la partie enti` ere de x.
Le d´ ecodage de w consiste donc ` a choisir, parmi toutes les d´ eterminations de u ` a l’aide
de (6.12), celle qui obtient le plus de votes.
Nous terminons cette section en prouvant les propri´ et´ es 6.19 et 6.20.
Preuve de la propri´ et´ e 6.19 Remarquons que chacune des composantes v j de
v, j = 0, 1, . . . , 2
m
− 2, d´ epend lin´ eairement des composantes u i . Ainsi, l’encodage u → v
est une application lin´ eaire de F
k
2 m dans F
2
m −1
2 m
.
Pour montrer que le noyau de cette application est trivial, il suffit de se convaincre
que seul le polynˆ ome nul sera envoy´ e dans 0 ∈ F
2
m −1
2 m
. Si p est un polynˆ ome non nul de
degr´ e k − 1 ou inf´ erieur, il ne peut pas s’annuler pour plus de k − 1 valeurs. Les v i sont
les ´ evaluations du polynˆ ome p pour les puissances α
i , i = 0, 1, 2, . . . , 2
m
− 2. Puisque α
est une racine primitive, toutes les 2
m
− 1 valeurs α
i sont distinctes. Et puisque p n’a
pas plus de k − 1 racines distinctes, seules k − 1 des 2
m
− 1 valeurs v i = p(α
i ) peuvent
ˆ etre nulles. Ainsi, tout polynˆ ome p non nul est envoy´ e sur un vecteur v non nul.
La propri´ et´ e 6.20 d´ ecoule du lemme suivant que nous d´ emontrerons tout d’abord.
Lemme 6.22 (d´ eterminant de Vandermonde) Soient x 1 , x 2 , . . . , x n des ´ el´ ements
quelconques d’un corps F. Alors
1 x 1 x
2
1
. . . x
n−1
1
1 x 2 x
2
2
. . . x
n−1
2
1 x 3 x
2
3
. . . x
n−1
3
. . .
. . .
. . .
. . .
. . .
1 x n x
2
n
. . . x
n−1
n
=
1≤i