Les codes 161
Dans les années 1970
Le chiffrement à clé publique est
développé.
1950
Richard Hamming publie un
article crucial sur les codes
permettant de détecter et
corriger les erreurs.
Dans les années 1920
La machine Enigma est mise au
point.
par un trait, le récepteur qui recevrait • • – • / • / – – • • ne s’apercevrait de rien et
traduirait le message par « FEZ ».
On pourrait examiner le système de codage bien plus élémentaire constitué des
deux signes 0 et 1 où 0 représente un mot et 1 un autre mot. Supposons qu’un commandant d’armée doive transmettre à ses troupes un message du type « envahissez »
ou « n’envahissez pas ». L’instruction « envahissez » est codée par 1 et « n’envahissez pas » par 0. Si un 1 ou un 0 a été retransmis incorrectement, le récepteur
ne le saura jamais et transmettra la mauvaise instruction avec les conséquences
désastreuses qui s’ensuivront.
On peut améliorer les choses en utilisant des mots de code de longueur 2. Si cette
fois on chiffre « envahissez » par 11 et « n’envahissez pas » par 00, une erreur de
chiffre donnerait 01 ou 10. Comme seuls 11 ou 00 sont des mots de code légitimes,
le récepteur sait avec certitude qu’une erreur s’est produite. L’avantage de ce système
est qu’une erreur est décelable, mais on ne sait toujours pas la corriger. Si l’on reçoit
01, comment savoir si c’est 00 ou 11 qui aurait dû être envoyé ?
La solution pour améliorer le système est de construire le message avec des mots de
code plus longs. Si l’on chiffre l’instruction « envahissez » par 111 et « n’envahissez
pas » par 000, on peut sûrement détecter une erreur dans un chiffre, comme auparavant. Si l’on sait qu’une erreur tout au plus a pu être commise (supposition raisonnable puisque le risque de commettre deux erreurs dans un mot code est faible),
le récepteur est en mesure de la corriger. Si l’on reçoit par exemple 110, le message
correct est alors 111. Grâce à ces règles, on sait que le message ne peut pas être 000
puisque ce mot de code supposerait deux erreurs. Dans ce système, il y deux mots
de code seulement, 000 et 111, mais ils sont suffisamment éloignés pour que soient
possibles la détection d’une erreur et sa correction.
Le même principe est utilisé lorsque le traitement de texte est en correction automatique. Si l’on tape « animul », le traitement de texte détecte l’erreur et la corrige
en prenant le mot le plus proche, à savoir « animal ». La langue anglaise ne peut
cependant pas être totalement soumise à cette correction automatique parce que si
l’on tape « lomp » par exemple, plusieurs mots seront voisins : les mots lamp, limp,
lump, pomp, et romp ne diffèrent tous de « lomp » que par une seule lettre.
Un code binaire moderne consiste en mots de code constitués d’une série de 0 et de
1. En choisissant des mots de code suffisamment éloignés, la détection et la correction sont toutes deux possibles. Les mots de code du Morse sont trop proches mais
les systèmes modernes utilisés pour transmettre des données depuis des satellites
peuvent toujours être mis en mode correction automatique. Avec les mots de code
Dans les années 1970
Le chiffrement à clé publique est
développé.
1950
Richard Hamming publie un
article crucial sur les codes
permettant de détecter et
corriger les erreurs.
Dans les années 1920
La machine Enigma est mise au
point.
par un trait, le récepteur qui recevrait • • – • / • / – – • • ne s’apercevrait de rien et
traduirait le message par « FEZ ».
On pourrait examiner le système de codage bien plus élémentaire constitué des
deux signes 0 et 1 où 0 représente un mot et 1 un autre mot. Supposons qu’un commandant d’armée doive transmettre à ses troupes un message du type « envahissez »
ou « n’envahissez pas ». L’instruction « envahissez » est codée par 1 et « n’envahissez pas » par 0. Si un 1 ou un 0 a été retransmis incorrectement, le récepteur
ne le saura jamais et transmettra la mauvaise instruction avec les conséquences
désastreuses qui s’ensuivront.
On peut améliorer les choses en utilisant des mots de code de longueur 2. Si cette
fois on chiffre « envahissez » par 11 et « n’envahissez pas » par 00, une erreur de
chiffre donnerait 01 ou 10. Comme seuls 11 ou 00 sont des mots de code légitimes,
le récepteur sait avec certitude qu’une erreur s’est produite. L’avantage de ce système
est qu’une erreur est décelable, mais on ne sait toujours pas la corriger. Si l’on reçoit
01, comment savoir si c’est 00 ou 11 qui aurait dû être envoyé ?
La solution pour améliorer le système est de construire le message avec des mots de
code plus longs. Si l’on chiffre l’instruction « envahissez » par 111 et « n’envahissez
pas » par 000, on peut sûrement détecter une erreur dans un chiffre, comme auparavant. Si l’on sait qu’une erreur tout au plus a pu être commise (supposition raisonnable puisque le risque de commettre deux erreurs dans un mot code est faible),
le récepteur est en mesure de la corriger. Si l’on reçoit par exemple 110, le message
correct est alors 111. Grâce à ces règles, on sait que le message ne peut pas être 000
puisque ce mot de code supposerait deux erreurs. Dans ce système, il y deux mots
de code seulement, 000 et 111, mais ils sont suffisamment éloignés pour que soient
possibles la détection d’une erreur et sa correction.
Le même principe est utilisé lorsque le traitement de texte est en correction automatique. Si l’on tape « animul », le traitement de texte détecte l’erreur et la corrige
en prenant le mot le plus proche, à savoir « animal ». La langue anglaise ne peut
cependant pas être totalement soumise à cette correction automatique parce que si
l’on tape « lomp » par exemple, plusieurs mots seront voisins : les mots lamp, limp,
lump, pomp, et romp ne diffèrent tous de « lomp » que par une seule lettre.
Un code binaire moderne consiste en mots de code constitués d’une série de 0 et de
1. En choisissant des mots de code suffisamment éloignés, la détection et la correction sont toutes deux possibles. Les mots de code du Morse sont trop proches mais
les systèmes modernes utilisés pour transmettre des données depuis des satellites
peuvent toujours être mis en mode correction automatique. Avec les mots de code