Communiquer sans erreurs : les codes correcteurs

Nous sommes en pleine ère numérique. Qu'est-ce que cela veut dire ? Tout simplement qu'une partie énorme des informations échangées à travers la planète est matériellement représentée sous la forme de nombres.

La surface d'un CD est fragile, mais un code correcteur est utilisé lors de sa gravure.

Messages électroniques, téléphonie mobile, transactions bancaires, téléguidage de satellites, télétransmission d'images, disques CD ou DVD, etc. : dans tous ces exemples, l'information est traduite - on dit codée (à ne pas confondre avec cryptée) - en suites de nombres entiers, correspondant physiquement à des signaux électriques ou autres. Plus précisément même, l'information est généralement codée sous forme de suites de chiffres binaires - des 0 ou des 1, appelés aussi bits. Par exemple, dans le code ASCII (American Standard Code for Information Interchange) utilisé par les micro-ordinateurs, le A majuscule est codé par l'octet (séquence de 8 bits) 01000001, le B majuscule par 01000010, etc.

Un problème majeur de la transmission de l'information est celui des erreurs. Il suffit d'une petite rayure sur un disque, d'une perturbation de l'appareillage, ou d'un quelconque phénomène parasite pour que le message transmis comporte des erreurs, c'est-à-dire des « 0 » qui ont malencontreusement été changés en « 1 », ou inversement. Or l'un des nombreux atouts du numérique est la possibilité de détecter, et même de corriger, de telles erreurs.

On allonge 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.

En plus d'un taux de rentabilité élevé, un bon code correcteur doit posséder d'autres qualités. 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 d'erreurs possible, 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.

Exemple de code de Hamming. Si l'animation ne s'affiche pas correctement

Exemple de code de Hamming. Si l'animation ne s'affiche pas correctement

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 W. Hamming (1915-1998), dans les années 1950 (dans ces codes, qui ont été beaucoup utilisés, les bits de contrôle sont déterminés en fonction des bits d'information par des équations linéaires simples).

Les spécialistes se sont alors mis à étudier de manière systématique les codes correcteurs et leurs propriétés, dans le but d'obtenir concrètement des codes aussi performants ou presque que le prédisaient les résultats théoriques de Shannon. Pour ce faire, ils ont utilisé les ressources de l'algèbre. Si le codage de l'information se fait directement dans l'« alphabet » binaire 0 et 1, l'algèbre sous-jacente est celle du pair et de l'impair, connue déjà de Platon (pair + pair = pair, pair + impair = impair, pair x pair = pair, impair x impair = impair, etc.). En fait, il s'avère plus intéressant de considérer des « alphabets » de codage ayant plus de deux chiffres, et de traduire seulement à la fin de la procédure le résultat en suites binaires de 0 et 1. Comme un alphabet comporte un nombre fini de symboles, et que l'on souhaite effectuer des calculs sur ces symboles, l'algèbre sous-jacente est l'objet de la théorie des corps finis, créée au début du XIX^e siècle par le jeune mathématicien français Évariste Galois, en étudiant la résolution des équations algébriques (un corps fini est un ensemble d'éléments en nombre fini qui peuvent s'additionner, se multiplier et se diviser de manière analogue aux nombres ordinaires, le résultat des opérations restant à l'intérieur de cet ensemble. L'ensemble constitué par 0 et 1, avec les règles arithmétiques du pair et de l'impair, est le corps fini à deux éléments ; c'est le corps fini le plus simple).

Ainsi, c'est à l'aide d'algèbre abstraite et élaborée, en liaison avec la théorie des corps finis, qu'ont été construits des codes correcteurs d'erreurs très efficaces, adaptés à tel ou tel type de transmission d'information. Deux exemples parmi une multitude d'autres sont le code employé pour la gravure des disques audionumériques (il permet de corriger jusqu'à environ 4000 bits erronés consécutifs, l'équivalent d'une rayure sur plus de 2 millimètres de piste), et celui qu'a utilisé la sonde spatiale Mariner 9 pour nous envoyer ses images de la planète Mars.

De nouvelles familles de codes

L'algèbre abstraite n'est pas le seul instrument dont disposent les spécialistes des codes correcteurs. Il y a aussi la géométrie algébrique. Celle-ci, très vaste partie des mathématiques actuelles, a pour point de départ l'étude des objets géométriques - courbes, surfaces, etc. - définis par des équations algébriques. Tout lycéen sait par exemple qu'une parabole peut être représentée par une équation algébrique, de type y=ax²+bx+c, où x et y sont les coordonnées des points de la parabole. On peut aussi étudier des courbes définies sur des corps finis, c'est-à-dire que dans les équations algébriques qui les représentent, les grandeurs comme x et y ne sont pas n'importe quels nombres, mais uniquement des éléments d'un certain corps fini. En utilisant de telles courbes et l'algèbre associée aux coordonnées de leurs points (qui sont en nombre fini), on a inauguré, il y a environ vingt ans, une nouvelle famille de codes correcteurs : les codes géométriques. Cela a permis récemment d'obtenir de nouveaux résultats concernant les codes binaires, et de construire des codes encore plus performants que ceux prédits par les travaux de Shannon. En contrepartie, l'analyse des codes géométriques a conduit les mathématiciens à examiner de plus près le nombre de points d'une courbe algébrique définie sur un corps fini. On a là un bel exemple de la rétroaction positive qu'un domaine d'application peut exercer sur la discipline théorique dont il se sert.

Autre famille récente de codes très performants : les turbocodes . Mis au point dans les années 1990, ils permettent aujourd'hui de s’approcher à quelques centièmes de la limite théorique prévue par Shannon. Ils sont utilisés dans des réseaux de télécommunication - réseau de téléphonie mobile UMTS et ADSL2 - aussi bien que pour les transmissions effectuées par des sondes spatiales de l'Agence spatiale européenne et de la NASA. Concrètement, un turbocode combine deux codes, aussi bien pour le codage que pour le décodage. En s'échangeant leur information, les deux codes se révèlent bien plus efficaces qu'un seul code de grande taille.

Pour en savoir plus sur ce sujet, nous vous proposons quelques références .

Une première version de ce texte est parue dans la brochure « L'explosion des mathématiques » éditée par la SMF et la SMAI .