6.6 Les codes de Reed et Solomon
199
(Les preuves des propri´ et´ es 6.19 et 6.20 sont donn´ ees ` a la fin de la section.)
La transmission peut introduire des erreurs dans le message encod´ e v. Ainsi, le
message re¸ cu w ∈ F
2
m −1
2 m
pourrait diff´ erer de v par une composante ou mˆ eme plus. Le
d´ ecodage consiste ` a remplacer, dans le syst` eme (6.12), les v i par les composantes w i de w
et ` a extraire de ce nouveau syst` eme lin´ eaire les composantes u j du message original et ce,
malgr´ e les erreurs possibles dans w. Pour comprendre comment ceci peut ˆ etre fait, nous
d´ ecrivons d’abord le syst` eme (6.12) g´ eom´ etriquement. Chacune des ´ equations de (6.12)
repr´ esente un plan dans l’espace F
k
2 param´ etris´ e par les coordonn´ ees (u 0 , u 1 , . . . , u k−1 ).
Il y a donc 2
m
−1 plans, plus que k, le nombre d’inconnues u j . Utilisons notre intuition de
R
3 pour dessiner une repr´ esentation g´ eom´ etrique de la situation. La figure 6.4a pr´ esente
cinq plans (plutˆ ot que 2
m
−1) dans R
3 (plutˆ ot que dans F
k
2 ). S’il n’y a aucune erreur lors
de la transmission (et alors, chacune des composantes w i co¨ ıncide avec la composante
correspondante v i ), alors les plans s’intersectent tous en un seul point u qui correspond
au message original. De plus, chaque choix de trois plans parmi les cinq d´ etermine
uniquement la solution u. En d’autres mots, deux des cinq plans sont redondants et,
dans cette transmission sans erreur, il y a plusieurs fa¸ cons de reconstruire le message
original u. Supposons maintenant qu’une des composantes de w soit erron´ ee. L’´ equation
qui la contient sera fausse, et le plan correspondant sera d´ eplac´ e par rapport au plan
original. C’est ce que repr´ esente la figure 6.4b o` u le plan horizontal a ´ et´ e d´ eplac´ e vers
le haut. Mˆ eme si les quatre plans justes (sans erreur) s’intersectent encore en u, un
choix de trois plans qui inclut le plan erron´ e donne une d´ etermination ¯
u erron´ ee. Dans
R
3 , trois plans sont n´ ecessaires pour d´ eterminer u (justement ou erron´ ement). Dans le
syst` eme (6.12), il faut k plans (= ´ equations) pour obtenir une valeur de u. Nous pouvons
donc penser ` a un choix de k plans « votant » pour la valeur u o` u ils s’intersectent. Si
quelques w i sont faux, nous pouvons nous demander sous quelles conditions la valeur
correcte de u obtiendra le plus grand nombre de votes. C’est ` a cette question que nous
allons r´ epondre maintenant. (Exercice : v´ erifier que, pour l’exemple de la figure 6.4b, la
r´ eponse u re¸ coit quatre votes alors que la r´ eponse erron´ ee ¯
u n’en re¸ coit qu’un.)
Supposons qu’une fois le message transmis, nous recevions les 2
m
− 1 lettres de w =
(w 0 , w 1 , w 2 , . . . , w 2 m −2 ) ∈ F
2
m −1
2 m
. Si toutes ces lettres sont exactes, on peut retrouver le
message original u en choisissant dans (6.12) n’importe quel sous-ensemble de k lignes
(= plans) et en r´ esolvant le syst` eme lin´ eaire correspondant. Supposons qu’on choisisse
les lignes i 0 , i 1 , . . . , i k−1 , tels que 0 ≤ i 0 < i 1 < · · · < i k−1 ≤ 2
m
− 2, et que α j d´ enote
α
ij . Alors, le syst` eme lin´ eaire se lit
⎛
⎜
⎜
⎜
⎜
⎜
⎝
w i0
w i1
w i2
. . .
w i k−1
⎞
⎟
⎟
⎟
⎟
⎟
⎠
=
⎛
⎜
⎜
⎜
⎜
⎜
⎝
1
α 0
α
2
0
α
3
0
. . . α
k−1
0
1
α 1
α
2
1
α
3
1
. . . α
k−1
1
1
α 2
α
2
2
α
3
2
. . . α
k−1
2
. . .
. . .
. . .
. . .
. . .
. . .
1 α k−1 α
2
k−1
α
3
k−1
. . . α
k−1
k−1
⎞
⎟
⎟
⎟
⎟
⎟
⎠
⎛
⎜
⎜
⎜
⎜
⎜
⎝
u 0
u 1
u 2
. . .
u k−1
⎞
⎟
⎟
⎟
⎟
⎟
⎠
,
(6.13)
et on peut obtenir le message original u en inversant la matrice {α
j
i } 0≤i,j≤k−1 , pour
autant qu’elle soit inversible.
199
(Les preuves des propri´ et´ es 6.19 et 6.20 sont donn´ ees ` a la fin de la section.)
La transmission peut introduire des erreurs dans le message encod´ e v. Ainsi, le
message re¸ cu w ∈ F
2
m −1
2 m
pourrait diff´ erer de v par une composante ou mˆ eme plus. Le
d´ ecodage consiste ` a remplacer, dans le syst` eme (6.12), les v i par les composantes w i de w
et ` a extraire de ce nouveau syst` eme lin´ eaire les composantes u j du message original et ce,
malgr´ e les erreurs possibles dans w. Pour comprendre comment ceci peut ˆ etre fait, nous
d´ ecrivons d’abord le syst` eme (6.12) g´ eom´ etriquement. Chacune des ´ equations de (6.12)
repr´ esente un plan dans l’espace F
k
2 param´ etris´ e par les coordonn´ ees (u 0 , u 1 , . . . , u k−1 ).
Il y a donc 2
m
−1 plans, plus que k, le nombre d’inconnues u j . Utilisons notre intuition de
R
3 pour dessiner une repr´ esentation g´ eom´ etrique de la situation. La figure 6.4a pr´ esente
cinq plans (plutˆ ot que 2
m
−1) dans R
3 (plutˆ ot que dans F
k
2 ). S’il n’y a aucune erreur lors
de la transmission (et alors, chacune des composantes w i co¨ ıncide avec la composante
correspondante v i ), alors les plans s’intersectent tous en un seul point u qui correspond
au message original. De plus, chaque choix de trois plans parmi les cinq d´ etermine
uniquement la solution u. En d’autres mots, deux des cinq plans sont redondants et,
dans cette transmission sans erreur, il y a plusieurs fa¸ cons de reconstruire le message
original u. Supposons maintenant qu’une des composantes de w soit erron´ ee. L’´ equation
qui la contient sera fausse, et le plan correspondant sera d´ eplac´ e par rapport au plan
original. C’est ce que repr´ esente la figure 6.4b o` u le plan horizontal a ´ et´ e d´ eplac´ e vers
le haut. Mˆ eme si les quatre plans justes (sans erreur) s’intersectent encore en u, un
choix de trois plans qui inclut le plan erron´ e donne une d´ etermination ¯
u erron´ ee. Dans
R
3 , trois plans sont n´ ecessaires pour d´ eterminer u (justement ou erron´ ement). Dans le
syst` eme (6.12), il faut k plans (= ´ equations) pour obtenir une valeur de u. Nous pouvons
donc penser ` a un choix de k plans « votant » pour la valeur u o` u ils s’intersectent. Si
quelques w i sont faux, nous pouvons nous demander sous quelles conditions la valeur
correcte de u obtiendra le plus grand nombre de votes. C’est ` a cette question que nous
allons r´ epondre maintenant. (Exercice : v´ erifier que, pour l’exemple de la figure 6.4b, la
r´ eponse u re¸ coit quatre votes alors que la r´ eponse erron´ ee ¯
u n’en re¸ coit qu’un.)
Supposons qu’une fois le message transmis, nous recevions les 2
m
− 1 lettres de w =
(w 0 , w 1 , w 2 , . . . , w 2 m −2 ) ∈ F
2
m −1
2 m
. Si toutes ces lettres sont exactes, on peut retrouver le
message original u en choisissant dans (6.12) n’importe quel sous-ensemble de k lignes
(= plans) et en r´ esolvant le syst` eme lin´ eaire correspondant. Supposons qu’on choisisse
les lignes i 0 , i 1 , . . . , i k−1 , tels que 0 ≤ i 0 < i 1 < · · · < i k−1 ≤ 2
m
− 2, et que α j d´ enote
α
ij . Alors, le syst` eme lin´ eaire se lit
⎛
⎜
⎜
⎜
⎜
⎜
⎝
w i0
w i1
w i2
. . .
w i k−1
⎞
⎟
⎟
⎟
⎟
⎟
⎠
=
⎛
⎜
⎜
⎜
⎜
⎜
⎝
1
α 0
α
2
0
α
3
0
. . . α
k−1
0
1
α 1
α
2
1
α
3
1
. . . α
k−1
1
1
α 2
α
2
2
α
3
2
. . . α
k−1
2
. . .
. . .
. . .
. . .
. . .
. . .
1 α k−1 α
2
k−1
α
3
k−1
. . . α
k−1
k−1
⎞
⎟
⎟
⎟
⎟
⎟
⎠
⎛
⎜
⎜
⎜
⎜
⎜
⎝
u 0
u 1
u 2
. . .
u k−1
⎞
⎟
⎟
⎟
⎟
⎟
⎠
,
(6.13)
et on peut obtenir le message original u en inversant la matrice {α
j
i } 0≤i,j≤k−1 , pour
autant qu’elle soit inversible.