6.3 Le code de Hamming C(7, 4)
185
Le r´ ecepteur constate qu’une erreur a dˆ u se produire, car deux des trois lettres re¸ cues,
w 5 , w 6 et w 7 , ne reproduisent pas celles qu’il calcule, c’est-` a-dire W 5 , W 6 , W 7 . Mais
o` u est l’erreur ? Touche-t-elle une des quatre premi` eres lettres du message original ou
une des trois lettres ajout´ ees ? Il est facile d’exclure la possibilit´ e que w 5 ou w 6 ou w 7
soit erron´ ee. Si nous changeons une seule de ces trois lettres, au moins une des trois
´ egalit´ es (6.2) ne sera pas satisfaite. Il faut donc que la lettre erron´ ee soit une des quatre
premi` eres. Quelle lettre, parmi w 1 , w 2 , w 3 et w 4 , peut-on changer de fa¸ con ` a corriger
simultan´ ement les deux derni` eres ´ egalit´ es fausses de (6.2) tout en pr´ eservant la premi` ere
qui est juste ? La r´ eponse est simple : la lettre `
a corriger est w 3 . En effet, la premi` ere
somme ne contient pas w 3 et ne sera pas affect´ ee par le changement de cette lettre. Les
deux autres changeront et seront donc « corrig´ ees ». Ainsi, mˆ eme si les quatre premi` eres
lettres re¸ cues par le r´ ecepteur sont (w 1 , w 2 , w 3 , w 4 ) = (1, 1, 1, 1), le message original
(correct) devait ˆ etre (v 1 , v 2 , v 3 , v 4 ) = (1, 1, 0, 1).
Dressons maintenant la liste de toutes les possibilit´ es. Supposons que le r´ ecepteur
re¸ coive les lettres (w 1 , w 2 , . . . , w 7 ). La seule chose dont ce r´ ecepteur est assur´ e est que ces
sept lettres w i , i = 1, . . . , 7 co¨ ıncident avec les lettres v i = i, . . . , 7, `
a l’exception, peutˆ etre, d’une seule lettre (qu’il ne connaˆ ıt cependant pas). Huit possibilit´ es se pr´ esentent
au r´ ecepteur. Les voici :
(0) il n’y a aucune lettre erron´ ee ;
(1) w 1 est erron´ ee ;
(2) w 2 est erron´ ee ;
(3) w 3 est erron´ ee ;
(4) w 4 est erron´ ee ;
(5) w 5 est erron´ ee ;
(6) w 6 est erron´ ee ;
(7) w 7 est erron´ ee.
`
A l’aide des lettres redondantes, le r´ ecepteur peut d´ eterminer laquelle est juste. En effet,
en calculant W 5 , W 6 et W 7 comme ci-dessus, il pourra diagnostiquer lequel des huit cas
(i), i = 0, . . . , 7, est le bon `
a l’aide du tableau suivant :
(0) si w 5 = W 5 et w 6 = W 6 et w 7 = W 7 ;
(1) si w 5 = W 5 et w 6 = W 6 ;
(2) si w 5 = W 5 et w 7 = W 7 ;
(3) si w 6 = W 6 et w 7 = W 7 ;
(4) si w 5 = W 5 et w 6 = W 6 et w 7 = W 7 ;
(5) si w 5 = W 5 ;
(6) si w 6 = W 6 ;
(7) si w 7 = W 7 .
185
Le r´ ecepteur constate qu’une erreur a dˆ u se produire, car deux des trois lettres re¸ cues,
w 5 , w 6 et w 7 , ne reproduisent pas celles qu’il calcule, c’est-` a-dire W 5 , W 6 , W 7 . Mais
o` u est l’erreur ? Touche-t-elle une des quatre premi` eres lettres du message original ou
une des trois lettres ajout´ ees ? Il est facile d’exclure la possibilit´ e que w 5 ou w 6 ou w 7
soit erron´ ee. Si nous changeons une seule de ces trois lettres, au moins une des trois
´ egalit´ es (6.2) ne sera pas satisfaite. Il faut donc que la lettre erron´ ee soit une des quatre
premi` eres. Quelle lettre, parmi w 1 , w 2 , w 3 et w 4 , peut-on changer de fa¸ con ` a corriger
simultan´ ement les deux derni` eres ´ egalit´ es fausses de (6.2) tout en pr´ eservant la premi` ere
qui est juste ? La r´ eponse est simple : la lettre `
a corriger est w 3 . En effet, la premi` ere
somme ne contient pas w 3 et ne sera pas affect´ ee par le changement de cette lettre. Les
deux autres changeront et seront donc « corrig´ ees ». Ainsi, mˆ eme si les quatre premi` eres
lettres re¸ cues par le r´ ecepteur sont (w 1 , w 2 , w 3 , w 4 ) = (1, 1, 1, 1), le message original
(correct) devait ˆ etre (v 1 , v 2 , v 3 , v 4 ) = (1, 1, 0, 1).
Dressons maintenant la liste de toutes les possibilit´ es. Supposons que le r´ ecepteur
re¸ coive les lettres (w 1 , w 2 , . . . , w 7 ). La seule chose dont ce r´ ecepteur est assur´ e est que ces
sept lettres w i , i = 1, . . . , 7 co¨ ıncident avec les lettres v i = i, . . . , 7, `
a l’exception, peutˆ etre, d’une seule lettre (qu’il ne connaˆ ıt cependant pas). Huit possibilit´ es se pr´ esentent
au r´ ecepteur. Les voici :
(0) il n’y a aucune lettre erron´ ee ;
(1) w 1 est erron´ ee ;
(2) w 2 est erron´ ee ;
(3) w 3 est erron´ ee ;
(4) w 4 est erron´ ee ;
(5) w 5 est erron´ ee ;
(6) w 6 est erron´ ee ;
(7) w 7 est erron´ ee.
`
A l’aide des lettres redondantes, le r´ ecepteur peut d´ eterminer laquelle est juste. En effet,
en calculant W 5 , W 6 et W 7 comme ci-dessus, il pourra diagnostiquer lequel des huit cas
(i), i = 0, . . . , 7, est le bon `
a l’aide du tableau suivant :
(0) si w 5 = W 5 et w 6 = W 6 et w 7 = W 7 ;
(1) si w 5 = W 5 et w 6 = W 6 ;
(2) si w 5 = W 5 et w 7 = W 7 ;
(3) si w 6 = W 6 et w 7 = W 7 ;
(4) si w 5 = W 5 et w 6 = W 6 et w 7 = W 7 ;
(5) si w 5 = W 5 ;
(6) si w 6 = W 6 ;
(7) si w 7 = W 7 .