200
6 Codes correcteurs
(a) Ensemble des plans sans erreur
(b) Ensemble des plans avec un plan
erron´ e
Fig. 6.4. Les plans du syst` eme (6.12)
Propri´ et´ e 6.20 Pour tout choix 0 ≤ i 0 < i 1 < i 2 < · · · < i k−1 ≤ 2
m
− 2, la matrice
{α
j
i } ci-dessus est inversible.
Ainsi, lorsque le message re¸ cu ne contient aucune erreur, il y a autant de fa¸ cons de
d´ eterminer le message original que de choix de k ´ equations parmi les 2
m
− 1 ´ equations
du syst` eme (6.12), c’est-` a-dire
2
m
− 1
k
=
(2
m
− 1)!
k!(2 m − 1 − k)!
.
Supposons maintenant que s composantes parmi les 2
m
−1 de w soient erron´ ees. Alors
seules (2
m
− s− 1) ´ equations de (6.12) sont justes, et seules
2
m −s−1
k
d´ eterminations de
u parmi les
2
m −1
k
possibilit´ es seront justes. Les autres seront erron´ ees ; il y aura donc
plusieurs d´ eterminations de u, une seule ´ etant la bonne. Soit ¯
u une des valeurs fautives
qu’on obtient en choisissant certaines des ´ equations fausses de (6.12). Combien de fois
peut-on obtenir ¯
u en changeant les ´ equations retenues ? La solution ¯
u est l’intersection
des k plans que repr´ esentent les k ´ equations de (6.12) choisies. Au maximum s + k − 1
plans s’intersectent en ¯
u, car s’il y en avait un seul de plus, il y aurait parmi ceux-ci
k plans d´ ecrits par des ´ equations justes, et alors, ¯
u = u. Il y aura donc au maximum
s+k−1
k
d´ eterminations menant `
a ¯
u. La valeur juste u obtiendra le plus de votes (c’est` a-dire le plus de d´ eterminations) si
2
m
− s − 1
k
>
s + k − 1
k