178
6 Codes correcteurs
un mot en rempla¸ cant chaque lettre par un mot dont la premi` ere lettre co¨ ıncidait avec
la lettre ` a ´ epeler. Ainsi, pour transmettre le mot « erreur », l’interlocuteur aurait dit
les mots « ´
Echo, Rom´ eo, Rom´ eo, ´
Echo, Uniforme, Rom´ eo ». Les arm´ ees am´ ericaine et
britannique avaient de tels « alphabets » d` es la Premi` ere Guerre mondiale. Ce code
pour am´ eliorer la transmission d’un message multiplie l’information ; on esp` ere que
le r´ ecepteur puisse extraire du message cod´ e ( ´
Echo, Rom´ eo, Rom´ eo, ´
Echo, Uniforme,
Rom´ eo) le message original (« erreur »), et ce, avec plus de constance et de pr´ ecision
que si le mot « erreur » avait ´ et´ e simplement dit ou ´ epel´ e. Cette « multiplication de
l’information » ou redondance est la cl´ e de tout code d´ etecteur et correcteur.
Notre second exemple sera celui d’un code d´ etecteur : il permet de diagnostiquer
qu’une erreur a ´ et´ e commise lors de la transmission, mais pas de corriger cette erreur.
En informatique, il est usuel de remplacer les caract` eres de notre alphabet ´ etendu (a,
b, c, . . . , A, B, C, . . . , 0, 1, 2, . . . , +, −, :, ;, . . . ) par un chiffre entre 0 et 127. En
repr´ esentation binaire, il faut sept caract` eres 0 ou 1 (chacun appel´ e bit, une contraction
de binary digit) pour ´ etiqueter ces 2
7 = 128 caract` eres. Par exemple, supposons que la
lettre a corresponde au nombre 97. Puisque 97 = 64 + 32 + 1 = 1 · 2
6 + 1 · 2
5 + 1 · 2
0 ,
la lettre a est encod´ ee comme 1100001. Ainsi, une correspondance possible est donn´ ee
par le tableau suivant.
d´ ecimal binaire parit´ e+binaire
A
65
1000001
01000001
B
66
1000010
01000010
C
67
1000011
11000011
. . .
. . .
. . .
. . .
a
97
1100001
11100001
b
98
1100010
11100010
c
99
1100011
01100011
. . .
. . .
. . .
. . .
Pour d´ etecter une erreur, on ajoute au code de sept bits un huiti` eme bit, dit bit de parit´ e.
Il est plac´ e ` a gauche des sept bits initiaux. Ce huiti` eme bit est choisi de fa¸ con ` a ce que
la somme des huit bits du code soit paire. Par exemple, la somme des sept bits de « A »
est 1 + 0 + 0 + 0 + 0 + 0 + 1 = 2, le bit de parit´ e sera alors 0, et « A » sera repr´ esent´ e par
01000001. Cependant, la somme des sept bits de « a » est 1 + 1 + 0 + 0 + 0 + 0 + 1 = 3, et
« a » sera repr´ esent´ e par les huit bits 11100001. Ce bit de parit´ e est un code de d´ etection.
Il permet de d´ etecter qu’une erreur a ´ et´ e commise lors de la transmission, mais il ne
permet pas de la corriger, car le r´ ecepteur ne sait pas lequel des huit bits est le bit fautif.
Le r´ ecepteur, constatant l’erreur, peut cependant demander `
a ce que le caract` ere lui soit
retransmis. Notons que ce code d´ etecteur repose sur l’hypoth` ese qu’au maximum un bit
6 Codes correcteurs
un mot en rempla¸ cant chaque lettre par un mot dont la premi` ere lettre co¨ ıncidait avec
la lettre ` a ´ epeler. Ainsi, pour transmettre le mot « erreur », l’interlocuteur aurait dit
les mots « ´
Echo, Rom´ eo, Rom´ eo, ´
Echo, Uniforme, Rom´ eo ». Les arm´ ees am´ ericaine et
britannique avaient de tels « alphabets » d` es la Premi` ere Guerre mondiale. Ce code
pour am´ eliorer la transmission d’un message multiplie l’information ; on esp` ere que
le r´ ecepteur puisse extraire du message cod´ e ( ´
Echo, Rom´ eo, Rom´ eo, ´
Echo, Uniforme,
Rom´ eo) le message original (« erreur »), et ce, avec plus de constance et de pr´ ecision
que si le mot « erreur » avait ´ et´ e simplement dit ou ´ epel´ e. Cette « multiplication de
l’information » ou redondance est la cl´ e de tout code d´ etecteur et correcteur.
Notre second exemple sera celui d’un code d´ etecteur : il permet de diagnostiquer
qu’une erreur a ´ et´ e commise lors de la transmission, mais pas de corriger cette erreur.
En informatique, il est usuel de remplacer les caract` eres de notre alphabet ´ etendu (a,
b, c, . . . , A, B, C, . . . , 0, 1, 2, . . . , +, −, :, ;, . . . ) par un chiffre entre 0 et 127. En
repr´ esentation binaire, il faut sept caract` eres 0 ou 1 (chacun appel´ e bit, une contraction
de binary digit) pour ´ etiqueter ces 2
7 = 128 caract` eres. Par exemple, supposons que la
lettre a corresponde au nombre 97. Puisque 97 = 64 + 32 + 1 = 1 · 2
6 + 1 · 2
5 + 1 · 2
0 ,
la lettre a est encod´ ee comme 1100001. Ainsi, une correspondance possible est donn´ ee
par le tableau suivant.
d´ ecimal binaire parit´ e+binaire
A
65
1000001
01000001
B
66
1000010
01000010
C
67
1000011
11000011
. . .
. . .
. . .
. . .
a
97
1100001
11100001
b
98
1100010
11100010
c
99
1100011
01100011
. . .
. . .
. . .
. . .
Pour d´ etecter une erreur, on ajoute au code de sept bits un huiti` eme bit, dit bit de parit´ e.
Il est plac´ e ` a gauche des sept bits initiaux. Ce huiti` eme bit est choisi de fa¸ con ` a ce que
la somme des huit bits du code soit paire. Par exemple, la somme des sept bits de « A »
est 1 + 0 + 0 + 0 + 0 + 0 + 1 = 2, le bit de parit´ e sera alors 0, et « A » sera repr´ esent´ e par
01000001. Cependant, la somme des sept bits de « a » est 1 + 1 + 0 + 0 + 0 + 0 + 1 = 3, et
« a » sera repr´ esent´ e par les huit bits 11100001. Ce bit de parit´ e est un code de d´ etection.
Il permet de d´ etecter qu’une erreur a ´ et´ e commise lors de la transmission, mais il ne
permet pas de la corriger, car le r´ ecepteur ne sait pas lequel des huit bits est le bit fautif.
Le r´ ecepteur, constatant l’erreur, peut cependant demander `
a ce que le caract` ere lui soit
retransmis. Notons que ce code d´ etecteur repose sur l’hypoth` ese qu’au maximum un bit