184
6 Codes correcteurs
code C ⊂ F
4
2 ne contiendra donc que 16 mots ou ´ el´ ements. Plutˆ ot que de transmettre
ces quatre lettres, nous transmettrons les sept lettres suivantes :
v 1 = u 1 ,
v 2 = u 2 ,
v 3 = u 3 ,
v 4 = u 4 ,
v 5 = u 1 + u 2 + u 4 ,
v 6 = u 1 + u 3 + u 4 ,
v 7 = u 2 + u 3 + u 4 .
Ainsi, pour transmettre le mot (1, 0, 1, 1), nous enverrons le message
(v 1 , v 2 , v 3 , v 4 , v 5 , v 6 , v 7 ) = (1, 0, 1, 1, 0, 1, 0)
puisque
v 5 =u 1 + u 2 + u 4 =1 + 0 + 1 = 0,
v 6 =u 1 + u 3 + u 4 =1 + 1 + 1 = 1,
v 7 =u 2 + u 3 + u 4 =0 + 1 + 1 = 0.
(Attention : « + » est l’addition dans F 2 .)
Puisque les quatre premi` eres composantes de (v 1 , v 2 , . . . , v 7 ) sont pr´ ecis´ ement les
quatre lettres du mot ` a transmettre, `
a quoi peuvent bien servir les trois autres lettres ?
Ces lettres sont redondantes et permettent de corriger une lettre erron´ ee, quelle qu’elle
soit. Comment ce « miracle » peut-il ˆ etre accompli ?
En voici un exemple. Le r´ ecepteur re¸ coit les sept lettres (w 1 , w 2 , . . . , w 7 ) = (1, 1, 1,
1, 1, 0, 0). Nous distinguons les v i des w i , car, lors de la transmission, une des lettres,
disons v j , peut avoir ´ et´ e corrompue. Alors v j = w j . `
A cause de la qualit´ e de son canal de
transmission, le r´ ecepteur peut, avec une bonne assurance, faire l’hypoth` ese qu’aucune
ou au plus une lettre est erron´ ee. Le r´ ecepteur calcule donc
W 5 = w 1 + w 2 + w 4 ,
W 6 = w 1 + w 3 + w 4 ,
W 7 = w 2 + w 3 + w 4 ,
et les compare avec les w 5 , w 6 et w 7 qu’il a re¸ cus. S’il n’y a pas eu d’erreur lors de
la transmission, W 5 , W 6 , W 7 devraient co¨ ıncider avec w 5 , w 6 , w 7 . Voici ce calcul pour
l’exemple pr´ esent :
W 5 = w 1 + w 2 + w 4 = 1 + 1 + 1 = 1 = w 5 ,
W 6 = w 1 + w 3 + w 4 = 1 + 1 + 1 = 1 = w 6 ,
(6.2)
W 7 = w 2 + w 3 + w 4 = 1 + 1 + 1 = 1 = w 7 .
6 Codes correcteurs
code C ⊂ F
4
2 ne contiendra donc que 16 mots ou ´ el´ ements. Plutˆ ot que de transmettre
ces quatre lettres, nous transmettrons les sept lettres suivantes :
v 1 = u 1 ,
v 2 = u 2 ,
v 3 = u 3 ,
v 4 = u 4 ,
v 5 = u 1 + u 2 + u 4 ,
v 6 = u 1 + u 3 + u 4 ,
v 7 = u 2 + u 3 + u 4 .
Ainsi, pour transmettre le mot (1, 0, 1, 1), nous enverrons le message
(v 1 , v 2 , v 3 , v 4 , v 5 , v 6 , v 7 ) = (1, 0, 1, 1, 0, 1, 0)
puisque
v 5 =u 1 + u 2 + u 4 =1 + 0 + 1 = 0,
v 6 =u 1 + u 3 + u 4 =1 + 1 + 1 = 1,
v 7 =u 2 + u 3 + u 4 =0 + 1 + 1 = 0.
(Attention : « + » est l’addition dans F 2 .)
Puisque les quatre premi` eres composantes de (v 1 , v 2 , . . . , v 7 ) sont pr´ ecis´ ement les
quatre lettres du mot ` a transmettre, `
a quoi peuvent bien servir les trois autres lettres ?
Ces lettres sont redondantes et permettent de corriger une lettre erron´ ee, quelle qu’elle
soit. Comment ce « miracle » peut-il ˆ etre accompli ?
En voici un exemple. Le r´ ecepteur re¸ coit les sept lettres (w 1 , w 2 , . . . , w 7 ) = (1, 1, 1,
1, 1, 0, 0). Nous distinguons les v i des w i , car, lors de la transmission, une des lettres,
disons v j , peut avoir ´ et´ e corrompue. Alors v j = w j . `
A cause de la qualit´ e de son canal de
transmission, le r´ ecepteur peut, avec une bonne assurance, faire l’hypoth` ese qu’aucune
ou au plus une lettre est erron´ ee. Le r´ ecepteur calcule donc
W 5 = w 1 + w 2 + w 4 ,
W 6 = w 1 + w 3 + w 4 ,
W 7 = w 2 + w 3 + w 4 ,
et les compare avec les w 5 , w 6 et w 7 qu’il a re¸ cus. S’il n’y a pas eu d’erreur lors de
la transmission, W 5 , W 6 , W 7 devraient co¨ ıncider avec w 5 , w 6 , w 7 . Voici ce calcul pour
l’exemple pr´ esent :
W 5 = w 1 + w 2 + w 4 = 1 + 1 + 1 = 1 = w 5 ,
W 6 = w 1 + w 3 + w 4 = 1 + 1 + 1 = 1 = w 6 ,
(6.2)
W 7 = w 2 + w 3 + w 4 = 1 + 1 + 1 = 1 = w 7 .