Comment un CD rayé ou une sonde lointaine corrigent-ils des erreurs que personne n'a vues ?
Un CD peut perdre une bande de 2,5 mm de données à cause d'une rayure et jouer quand même parfaitement, grâce à une astuce à base de polynômes datant de 1960.
▶ Lancer l'histoireIls envoient des données en plus, calculées si habilement qu'on peut reconstruire les morceaux manquants ou faux. Tout système de correction d'erreurs ajoute de la redondance. Le plus simple, un bit de parité, sait dire que quelque chose cloche, mais pas où : il faut alors tout renvoyer. Les codes de Reed-Solomon, inventés par Irving Reed et Gustave Solomon en 1960, savent trouver et réparer les dégâts sur place, sans rien redemander à l'expéditeur.
L'astuce, c'est de transformer le message en courbe. Imagine un message de deux nombres comme une droite : deux nombres suffisent à fixer une droite. Au lieu d'envoyer seulement ces deux nombres, tu envoies quatre points de cette droite. Si deux points se perdent, les deux autres fixent toujours la même droite. Si un point arrive faux, il détonne : les trois autres restent alignés, et l'intrus peut être corrigé. Les vrais codes de Reed-Solomon font pareil avec des polynômes, des cousins plus courbes des droites, sur beaucoup de points.
La règle est précise. Ajoute t symboles de contrôle et le code peut réparer jusqu'à t symboles s'il sait où sont les dégâts, ou t/2 s'il doit aussi les trouver. C'est pour ça qu'un lecteur de QR code traite une zone illisible comme un trou repéré : les trous repérés coûtent deux fois moins cher à combler.
Étape 1: Le message est une droite
Deux nombres suffisent à définir une droite.
Étape 2: Envoyer des points en plus
Envoie quatre points de la droite au lieu de deux.
Étape 3: Deux perdus ? Pas grave
Deux points survivants définissent toujours la même droite.
Étape 4: Un faux ? Repère-le
Trois points restent alignés ; l'intrus est l'erreur.
Un CD empile deux codes de ce type et mélange les données pour qu'une rayure soit étalée finement sur beaucoup de blocs. Résultat : il corrige entièrement des salves allant jusqu'à 4 000 bits, environ 2,5 mm de disque. La même idée a protégé les images envoyées par les sondes Voyager à partir de 1977.
Quiz
0/3
Récap
Ajoute t symboles de contrôle : tu combles t trous que tu vois, ou tu corriges t/2 erreurs qu'il faut trouver.
Le fait surprenant · La correction d'erreurs est née de l'agacement de Richard Hamming face à un ordinateur qui abandonnait ses calculs chaque week-end.
Sources (5)
Pas de source, pas d'affirmation. Chacun des 29 faits de cette leçon renvoie à au moins une de ces sources.