On rallonge les mots du message
de façon qu’après dégradation, on
puisse quand même les reconnaître
Telle est la fonction des codes correcteurs
d’erreurs, dont les premiers ont été conçus
à la même époque que les premiers ordinateurs, il y a plus d’une cinquantaine d’années. Comment font-ils ? Le principe est le
suivant : on allonge les « mots » numériques
qui composent le message, de façon qu’une
partie des bits servent de bits de contrôle.
Par exemple, dans le code ASCII évoqué plus
haut, l’un des huit bits est un bit de contrôle :
il doit valoir 0 si le nombre de « 1 » dans les
7 autres bits est pair, et 1 sinon. Si l’un des
huit bits a inopinément basculé de valeur, la
parité indiquée par le bit de contrôle ne correspond plus et une erreur est alors détectée. La même idée se retrouve dans bien des
numéros que l’on rencontre dans la vie quotidienne. Par exemple, dans les relevés d’identité bancaire, on ajoute une lettre-clé à un
numéro de compte pour pouvoir détecter
une erreur de transmission. De même, les
numéros des billets de banque en euros sont
codés pour éviter les contrefaçons. Autrement
dit, la philosophie des codes correcteurs est
de composer des messages redondants :
chaque mot du message est allongé de façon
à contenir une information sur le message
lui-même !
Un exemple simple et éclairant, mais peu
réaliste, de code correcteur d’erreurs est la
triple répétition : chaque bit du message à
coder est triplé, c’est-à-dire que 0 devient 000
et 1 devient 111. Ce code permet de détecter
et corriger une erreur éventuelle sur un triplet. En effet, si l’on reçoit, mettons, la
séquence 101, on en déduit immédiatement
que la bonne séquence était 111 (on suppose
qu’un seul bit sur les trois reçus est erroné),
et donc que l’information initiale était le bit
1. Le code de triple répétition n’est pas réaliste car il est coûteux : pour chaque bit d’information, il faut en envoyer trois ; on dit que
son taux de rentabilité est 1/3. Ce taux a des
répercussions directes sur la durée nécessaire
à la transmission des messages et sur le coût
des communications.
Un bon code correcteur doit posséder
d’autres qualités en plus d’un taux de rentabilité élevé. Il lui faut également une bonne
capacité de détection et correction d’erreurs,
et la procédure de décodage doit être suffisamment simple et rapide. Tout le problème
de la théorie des codes correcteurs d’erreurs
est là : construire des codes qui détectent et
corrigent le plus possible d’erreurs, tout en
allongeant le moins possible les messages, et
qui soient faciles à décoder.
L’algèbre des corps finis s’applique
naturellement aux codes, car ceux-ci
utilisent un alphabet fini
Les mathématiques interviennent depuis
longtemps dans ces questions. Déjà en 1948,
le mathématicien américain Claude Shannon,
un des pères de la théorie de l’information,
obtenait des résultats théoriques généraux
affirmant qu’il existe des codes ayant des qualités optimales, en un sens technique précis.
Cependant, si le théorème de Shannon établissait l’existence de très bon codes correcteurs, il ne fournissait pas de méthode pratique pour les construire. Par ailleurs, on
disposait de codes correcteurs aux performances modestes, comme les codes de
Hamming, du nom de leur inventeur, le
mathématicien
américain
Richard
Communiquer sans erreurs : les codes correcteurs
85
de façon qu’après dégradation, on
puisse quand même les reconnaître
Telle est la fonction des codes correcteurs
d’erreurs, dont les premiers ont été conçus
à la même époque que les premiers ordinateurs, il y a plus d’une cinquantaine d’années. Comment font-ils ? Le principe est le
suivant : on allonge les « mots » numériques
qui composent le message, de façon qu’une
partie des bits servent de bits de contrôle.
Par exemple, dans le code ASCII évoqué plus
haut, l’un des huit bits est un bit de contrôle :
il doit valoir 0 si le nombre de « 1 » dans les
7 autres bits est pair, et 1 sinon. Si l’un des
huit bits a inopinément basculé de valeur, la
parité indiquée par le bit de contrôle ne correspond plus et une erreur est alors détectée. La même idée se retrouve dans bien des
numéros que l’on rencontre dans la vie quotidienne. Par exemple, dans les relevés d’identité bancaire, on ajoute une lettre-clé à un
numéro de compte pour pouvoir détecter
une erreur de transmission. De même, les
numéros des billets de banque en euros sont
codés pour éviter les contrefaçons. Autrement
dit, la philosophie des codes correcteurs est
de composer des messages redondants :
chaque mot du message est allongé de façon
à contenir une information sur le message
lui-même !
Un exemple simple et éclairant, mais peu
réaliste, de code correcteur d’erreurs est la
triple répétition : chaque bit du message à
coder est triplé, c’est-à-dire que 0 devient 000
et 1 devient 111. Ce code permet de détecter
et corriger une erreur éventuelle sur un triplet. En effet, si l’on reçoit, mettons, la
séquence 101, on en déduit immédiatement
que la bonne séquence était 111 (on suppose
qu’un seul bit sur les trois reçus est erroné),
et donc que l’information initiale était le bit
1. Le code de triple répétition n’est pas réaliste car il est coûteux : pour chaque bit d’information, il faut en envoyer trois ; on dit que
son taux de rentabilité est 1/3. Ce taux a des
répercussions directes sur la durée nécessaire
à la transmission des messages et sur le coût
des communications.
Un bon code correcteur doit posséder
d’autres qualités en plus d’un taux de rentabilité élevé. Il lui faut également une bonne
capacité de détection et correction d’erreurs,
et la procédure de décodage doit être suffisamment simple et rapide. Tout le problème
de la théorie des codes correcteurs d’erreurs
est là : construire des codes qui détectent et
corrigent le plus possible d’erreurs, tout en
allongeant le moins possible les messages, et
qui soient faciles à décoder.
L’algèbre des corps finis s’applique
naturellement aux codes, car ceux-ci
utilisent un alphabet fini
Les mathématiques interviennent depuis
longtemps dans ces questions. Déjà en 1948,
le mathématicien américain Claude Shannon,
un des pères de la théorie de l’information,
obtenait des résultats théoriques généraux
affirmant qu’il existe des codes ayant des qualités optimales, en un sens technique précis.
Cependant, si le théorème de Shannon établissait l’existence de très bon codes correcteurs, il ne fournissait pas de méthode pratique pour les construire. Par ailleurs, on
disposait de codes correcteurs aux performances modestes, comme les codes de
Hamming, du nom de leur inventeur, le
mathématicien
américain
Richard
Communiquer sans erreurs : les codes correcteurs
85