Quête de code

En 1948, le monde était encore un endroit analogique. Candid Camera et Ed Sullivan commençaient tout juste leurs longs passages à la télévision ; L'émission de radio de Jack Benny avait des dizaines de millions d'auditeurs. Mais la mauvaise réception était une réalité. Les interférences électromagnétiques, les obstacles physiques entre une tour de transmission et un récepteur et d'autres sources de ce que les ingénieurs appellent le bruit perturbaient régulièrement les monologues de Benny ou les performances des invités de Sullivan. Dans la plupart des régions, pour au moins certaines stations, les gens se sont résignés à des images enneigées ou à un son saturé d'électricité statique.

Claude Shannon, 1948

La même année, cependant, Claude Shannon, SM '40, PhD '40, a publié un article historique dans lequel il a prouvé mathématiquement que même en présence de beaucoup de bruit, il était possible de transmettre des informations avec pratiquement aucune erreur. C'était un monde analogique, mais la conclusion étonnante de Shannon était le résultat de sa capacité à penser numériquement. Selon Shannon, l'information sur n'importe quel support pourrait être représentée à l'aide de chiffres binaires ou de bits – un mot que son article a présenté au monde. Alors que le bruit dans un canal de communication peut corrompre les bits, a-t-il expliqué, l'ajout de bits supplémentaires liés aux bits d'origine par un algorithme connu - un code de correction d'erreurs - permettra de déduire la séquence d'origine.

Plus le canal est bruyant, plus il faut ajouter d'informations supplémentaires pour permettre la correction d'erreurs. Et plus d'informations supplémentaires sont incluses, plus la transmission sera lente. Shannon a montré comment calculer le plus petit nombre de bits supplémentaires pouvant garantir une erreur minimale et, par conséquent, le taux le plus élevé auquel une transmission de données sans erreur est possible. Mais il ne pouvait pas dire à quoi pourrait ressembler un schéma de codage pratique.

Les chercheurs ont passé 45 ans à en chercher un. Enfin, en 1993, une paire d'ingénieurs français a annoncé un ensemble de codes – des codes turbo – qui ont atteint des débits de données proches de la limite théorique de Shannon. La réaction initiale a été l'incrédulité, mais une enquête ultérieure a validé les affirmations des chercheurs. Il s'est également avéré un fait encore plus surprenant : des codes tout aussi bons que des codes turbo, qui s'appuyaient même sur le même type d'astuce mathématique, avaient été introduits plus de 30 ans plus tôt, dans la thèse de doctorat du MIT de Robert Gallager, SM ' 57, ScD '60. Après des décennies de négligence, les codes de Gallager ont enfin trouvé une application pratique. Ils sont utilisés dans la transmission de la télévision par satellite et des données sans fil, et des puces dédiées à leur décodage peuvent être trouvées dans les téléphones portables commerciaux.

La naissance de la théorie de l'information

Gallager est arrivé au MIT en 1956, la même année où Shannon lui-même est revenu en tant que professeur, après 15 ans passés aux Bell Labs. Mais ce n'est pas la perspective de travailler avec Shannon qui l'a amené à choisir le MIT plutôt que Yale, où il avait également postulé pour des études supérieures. J'étais dans l'armée - pour une mission dénuée de sens - et je détestais vraiment ce que je faisais, dit Gallager, qui a enseigné au MIT pendant plus de 40 ans après avoir obtenu son doctorat et conseille toujours les étudiants diplômés en tant que professeur émérite dans le laboratoire de recherche de Électronique. Le MIT a commencé une semaine plus tôt que Yale. Et j'avais tellement hâte de quitter l'armée que c'était vraiment ma seule raison de venir au MIT.

Gallager n'était même pas sûr de vouloir étudier la théorie de l'information, la nouvelle discipline en plein essor née de l'article de Shannon en 1948. Mais avant de rejoindre l'Army Signal Corps, Gallager avait également travaillé pendant plusieurs années chez Bell Labs, où il passait trois jours par semaine dans une salle de classe à se renseigner sur les dernières avancées en génie électrique. Bien qu'il n'ait jamais rencontré Shannon, cette expérience l'a aidé à reconnaître l'étendue de son accomplissement. Je le considérais juste comme une sorte de dieu, dit Gallager.

En effet, au moment où Shannon a rejoint la faculté du MIT, il était une célébrité mineure. Dès 1953, un article sur la théorie de l'information dans le magazine Fortune avait déclamé : Il n'est peut-être pas exagéré de dire que le progrès de l'homme dans la paix, et la sécurité dans la guerre, dépendent plus des applications fructueuses de la théorie de l'information que de démonstrations physiques, que ce soit dans les bombes ou dans les centrales électriques, c'est la fameuse équation d'Einstein qui fonctionne.

Ce qui a captivé l'imagination du public, c'est l'idée que l'information dans toute sa diversité – texte, audio, vidéo – pouvait être réduite à de simples séquences de 1 et de 0. Les appareils numériques commerciaux n'existaient pas encore, alors cela a époustouflé les gens que 001001010101000101011101 puisse représenter une partie d'une symphonie, ou une partie d'un film, ou une couleur, ou une ligne d'un livre. Mais comme Shannon l'a souligné dans son article, son collègue de Bell Labs, Ralph Hartley, avait fait une suggestion similaire 20 ans plus tôt. L'aspect de l'article qui a captivé – et continue de captiver – les collègues ingénieurs de Shannon était la manière ingénieuse dont il a prouvé qu'il doit y avoir un code capable de produire des transmissions de données sans erreur jusqu'à la capacité d'un canal.

Pour comprendre le fonctionnement d'un code de correction d'erreurs, pensez à quelqu'un qui essaie d'envoyer un message de quatre bits sur un canal bruyant. Si le bruit fait basculer l'un des bits vers son opposé, le récepteur n'a aucun moyen de savoir qu'une erreur s'est produite. La simple répétition du message, de sorte que 0011 devienne 00110011, résout ce problème : maintenant, si un bit bascule vers son opposé, le récepteur sait qu'il y a une erreur, car les deux versions du message ne correspondent pas. Mais il est impossible de dire lequel est correct. Une meilleure façon de coder le message pourrait utiliser les quatre bits supplémentaires pour représenter des informations sur les bits du message : le cinquième bit, par exemple, pourrait vous dire si les deux premiers bits du message ont des valeurs identiques ou différentes ; le sixième bit pourrait faire la même chose pour les bits trois et quatre, le septième pour les bits un et trois et le huitième pour les bits deux et quatre. Si l'un des quatre premiers bits est inversé, les quatre derniers peuvent l'identifier ; si l'un des quatre derniers bits est inversé, les trois autres peuvent véhiculer suffisamment d'informations pour le compenser.

L'article de Shannon, cependant, évite de telles ruminations sur la façon de construire réellement des codes. Au lieu de cela, il aborde le concept de correction d'erreurs en analysant statistiquement les propriétés générales de codes sélectionnés entièrement au hasard. Pour avoir une idée de son approche, il pourrait être utile de voir comment elle pourrait être appliquée à nos séquences hypothétiques de huit bits qui codent des messages de quatre bits.

Il y a 16 messages de quatre bits possibles, et la méthode de Shannon attribuerait à chacun d'eux son propre numéro de série de huit bits sélectionné au hasard - son mot de code. Le récepteur, comme l'expéditeur, aurait un livre de codes corrélant les 16 messages de quatre bits possibles avec les 16 mots de code aléatoires de huit bits. Comme il y a 256 séquences possibles de huit bits, il y en a 240 qui n'apparaissent pas dans le livre de codes. Quelqu'un qui reçoit l'une de ces 240 séquences saura qu'une erreur s'est glissée dans les données. Mais tant que les 16 mots de code autorisés sont suffisamment différents les uns des autres, il y aura probablement un seul qui se rapproche le plus de la séquence corrompue. Par exemple, si 0000001 et 11111110 sont tous deux des mots de code valides mais que 00000011 ne l'est pas, alors quelqu'un qui reçoit la séquence 00000011 peut conclure que le mot de code prévu était beaucoup plus susceptible d'être 0000001 que 11111110.

Dans la vraie vie, bien sûr, personne ne s'inquiète de transmettre des messages de seulement quatre bits. Mais en utilisant l'analyse statistique, Shannon a pu tirer des conclusions sur les messages codés de n'importe quelle longueur, envoyés sur des canaux avec n'importe quelle quantité de bruit. En particulier, il a pu quantifier rigoureusement à la fois le degré de différence entre des mots de code choisis au hasard et la probabilité qu'une séquence corrompue ressemble à un seul d'entre eux. Alors que la probabilité que deux séquences de huit bits soient similaires est relativement élevée, Shannon a montré qu'à mesure que les mots de code s'allongent, les chances de similitude diminuent de façon exponentielle. En fait, l'un de ses résultats les plus surprenants est que pour les messages longs, la plupart des mots de code attribués au hasard seront presque aussi différents les uns des autres que possible. Cela signifie que presque n'importe quel schéma de codage - n'importe quel moyen de générer ces mots - permettrait une transmission sans erreur sur un canal bruyant à un débit proche du maximum.

Il a fallu beaucoup d'intuition pour penser qu'un code parfaitement aléatoire pouvait être un très bon code en moyenne, explique David Forney, SM '63, ScD '65, ancien vice-président de Codex Corporation et de Motorola qui est revenu au MIT en 1996. en tant que professeur adjoint. Il s'avère que cela simplifie considérablement l'analyse, car vous pouvez maintenant effectuer une analyse de cas moyen. Forney s'arrête un instant, puis ajoute : Pour ne pas dire que c'était tout à fait simple : il a dû inventer au moins quelques théorèmes, sinon des branches des mathématiques. Mais Gallager est d'accord. À propos de l'article de Shannon de 1948, il dit : Après l'avoir étudié pendant deux ans, cela semble très simple. Tant de gens vous diront : « C'est vraiment très simple. » Et une fois que vous l'avez compris, c'est le cas.

Un défi irrésistible

La description mathématique de l'information par Shannon avait de nombreuses ramifications. Son article de 1948 a également introduit l'idée de la compression des données, ou représentant la même information avec moins de bits ; la compression est ce qui permet à des programmes comme WinZip ou StuffIt de réduire les fichiers afin qu'ils ne submergent pas les serveurs de messagerie, et elle est utilisée pour économiser de l'espace sur les lecteurs de disque. La théorie de l'information a également mis l'étude de la cryptographie sur une base mathématique plus sûre; en effet, Gallager pense que c'est le travail cryptographique de Shannon en temps de guerre aux Bell Labs qui l'a conduit à sa nouvelle conception de la communication.

Au moment où Shannon est revenu au MIT, cependant, il avait commencé à sentir que l'enthousiasme entourant sa théorie dépassait même ses mérites considérables. Dans un article de 1956 intitulé The Bandwagon, il cite des tentatives d'application de la théorie de l'information à des domaines tels que la biologie, la psychologie, la linguistique, la physique fondamentale, l'économie, la théorie de l'organisation et bien d'autres et s'engage à injecter une note de modération dans cette situation.

Le dégoût de Shannon pour les feux de la rampe frôlait le reclus. Selon Joel West '79, professeur au College of Business de l'Université d'État de San José qui écrit un livre sur le développement de la théorie de l'information, Shannon n'a conseillé que sept étudiants diplômés au cours de ses 22 années au MIT. Il était assez timide et réservé, donc si vous vouliez l'avoir comme superviseur, vous deviez vraiment être assez agressif à ce sujet, dit Gallager. J'étais aussi timide et réservée, et je n'avais même pas assez de confiance en moi pour aller parler au gars.

En tant qu'enseignante, Shannon avait peu de patience pour l'ennui du familier. Il était beaucoup plus intéressé par le nouveau que par l'ancien, dit Elwyn Berlekamp '62, SM '62, PhD '64, professeur émérite de mathématiques à l'Université de Californie à Berkeley, qui (avec Gallager) était co-auteur de Shannon dernier article publié.

Il n'a pas beaucoup enseigné, dit Gallager. Mais quand il enseignait, c'était comme donner des conférences sur la recherche. Je me souviens d'une fois où il a donné un cours, qui comptait environ 25 conférences pendant le trimestre, et chaque conférence était un nouveau résultat de recherche. Il les faisait l'un après l'autre et ne manquait jamais de trouver quelque chose d'intéressant. C'était une période vraiment fantastique.

Shannon était, à mon avis, un peu déplacé dans le milieu universitaire, déclare James L. Massey, SM '60, PhD '62, théoricien de l'information et professeur émérite à l'ETH Zurich. Son vrai genre était d'être un chercheur indépendant et de faire les choses à sa manière très individualiste.

Il se peut aussi que Shannon soit simplement mal à l'aise avec l'adulation. Berlekamp se souvient quand la IEEE Information Theory Society a invité Shannon à donner une conférence et à recevoir son premier prix Shannon en Israël en 1973. Je n'ai jamais vu personne avec plus de papillons que lui, dit-il. Cinq minutes avant le début de la conférence, il est au bar et il est assez déprimé. Il a vraiment peur de monter sur scène et de décevoir tout le monde. Parce que bien sûr, ils attendent Dieu, ce qui est vrai, et il sait qu'il ne peut pas agir comme Dieu.

Mais si Shannon était rarement un mentor direct pour les jeunes étudiants en théorie de l'information, il leur avait lancé un défi irrésistible. Le codage aléatoire ne fonctionnerait jamais dans la pratique : la taille du livre de codes hypothétique de Shannon doublait avec chaque bit supplémentaire dans le message. Le livre de codes pour un seul paquet de données de 1 000 bits circulant sur Internet nécessiterait plus d'entrées qu'il n'y a d'atomes dans l'univers. Mais tout mécanisme de codage plus pratique, comme répéter le message d'origine ou ajouter des bits supplémentaires décrivant les bits du message, était l'équivalent d'un schéma de codage aléatoire, en ce sens qu'il générerait les mêmes mots de code. Et en démontrant que la grande majorité des schémas de codage aléatoire approchait la capacité, Shannon a offert l'espoir que l'un des schémas pratiques l'était également.

Codes insaisissables

Au lieu d'utiliser un livre de codes pour faire correspondre les mots de code et les messages, un schéma de codage pratique fournirait un moyen d'extraire le message des mots de code par calcul. Une série d'opérations mathématiques pourrait, avec une forte probabilité de précision, identifier et corriger des erreurs dans une séquence de bits éventuellement corrompue reçue sur un canal bruyant.

C'est une des particularités des codes correcteurs d'erreurs qu'un bon algorithme d'encodage n'implique pas forcément un bon algorithme de décodage. À l'aide d'analyses statistiques similaires à celles de Shannon, les théoriciens du codage ont pu montrer qu'un code donné était proche de la capacité, c'est-à-dire qu'il maximiserait la différence entre les mots de code. Mais cela ne voulait pas dire qu'ils avaient un moyen efficace de le décoder.

Entre la publication de l'article de Shannon et le début des années 1990, les chercheurs ont proposé de meilleurs codes et aussi de meilleurs algorithmes de décodage. Mais un code pratique approchant les capacités restait insaisissable. Il y avait un dicton parmi les théoriciens du codage, dit Forney, que presque tous les codes sont bons, à l'exception de tous ceux auxquels nous pouvons penser.

Les codes que Gallager a présentés dans sa thèse de doctorat de 1960 étaient une tentative de préserver une partie du caractère aléatoire du système hypothétique de Shannon sans sacrifier l'efficacité du décodage. Comme de nombreux codes antérieurs, Gallager utilisait des bits de parité, qui indiquent si un autre groupe de bits a des sommes paires ou impaires. Mais les codes antérieurs généraient les bits de parité de manière systématique : le premier bit de parité pouvait indiquer si la somme des bits de message un à trois était paire ; le bit de parité suivant peut faire la même chose pour les bits de message deux à quatre, le troisième pour les bits trois à cinq, et ainsi de suite. Dans les codes de Gallager, en revanche, la corrélation entre les bits de parité et les bits de message était aléatoire : le premier bit de parité pouvait décrire, disons, la somme des bits de message 4, 27 et 83 ; le suivant pourrait faire de même pour les bits de message 19, 42 et 65.

Gallager a pu démontrer mathématiquement que pour les longs messages, ses codes pseudo-aléatoires approchaient la capacité. Sauf que nous savions d'autres choses qui approchaient aussi les capacités, dit-il. Il n'a jamais été question de savoir quels codes étaient bons. Il s'agissait toujours de savoir quels types d'algorithmes de décodage vous pouviez concevoir.

C'est là que Gallager a fait sa percée. Ses codes utilisaient un décodage itératif, ce qui signifie que le décodeur traverserait les données plusieurs fois, faisant des suppositions de plus en plus précises sur l'identité de chaque bit. Si, par exemple, les bits de parité décrivaient des triplets de bits, alors des informations fiables sur deux bits quelconques pourraient véhiculer des informations sur un troisième. L'algorithme de décodage itératif de Gallager est le plus couramment utilisé aujourd'hui, non seulement pour décoder ses propres codes mais, fréquemment, pour décoder également les turbocodes. Il a également trouvé une application dans le type de raisonnement statistique utilisé dans de nombreux systèmes d'intelligence artificielle.

Les techniques itératives consistent à faire une première estimation de ce que pourrait être un bit reçu et à lui donner un poids en fonction de sa fiabilité, explique Forney. Ensuite, vous obtenez peut-être plus d'informations à ce sujet car il est impliqué dans des contrôles de parité avec d'autres bits, ce qui vous donne une meilleure estimation de sa fiabilité. En fin de compte, dit Forney, les suppositions devraient converger vers une interprétation cohérente de tous les bits du message.

Bien que Gallager n'ait pas eu le courage de demander à Shannon d'être son conseiller, il dit qu'il a parlé à Shannon trois ou quatre fois lors de la rédaction de sa thèse. Sauf que parler à Claude trois ou quatre fois, c'était comme parler à la plupart des gens 50 fois, dit-il. C'était quelqu'un qui a vraiment compris les idées très, très vite. Il n'était pas génial du tout les détails techniques. Mais pour voir la structure de quelque chose, pour voir pourquoi cela devrait fonctionner et pour voir ce qui pourrait l'améliorer, eh bien, il était certainement la personne la plus intelligente que j'aie jamais rencontrée.

Pourtant, Shannon n'avait pas prévu le succès des codes de Gallager. Si je me souviens bien, il pensait qu'ils étaient intéressants, mais je n'avais pas l'impression qu'il était excité par eux, dit Gallager. Il comprend pourquoi. Les codes de Gallager se sont approchés de la capacité des canaux à mesure qu'ils s'allongeaient ; mais à mesure qu'ils s'allongeaient, le processus de décodage devenait également plus complexe, bien trop complexe pour les ordinateurs de l'époque. Les chercheurs en codage savaient, bien sûr, que les ordinateurs s'amélioreraient. Mais personne ne savait quels codes ces améliorations favoriseraient.

Néanmoins, le MIT a immédiatement embauché Gallager en tant que membre du corps professoral sur la base de sa thèse. Dans les années qui ont suivi, alors que son propre schéma de codage languissait dans l'obscurité, il a enseigné et encadré une vague d'étudiants brillants - dont Massey, Forney et Berlekamp - dont les contributions à la théorie du codage ont eu des implications pratiques plus immédiates que les siennes.

Gallager, cependant, semble aussi imperturbable par la longue négligence de ses codes que par leur récent renouveau, peut-être parce qu'il a toujours eu une vision à long terme. Il a le don d'inventer des choses qui dorment pendant des dizaines d'années jusqu'à ce que les gens réalisent soudain que c'est de très bonnes choses, déclare Vincent Chan '71, MS '71, EE '72, PhD '74, un professeur d'ingénierie électrique qui affiche toujours par son bureau la plaque de porte du bureau qu'il partageait autrefois avec Shannon. Chan se souvient d'une récente visite dans les laboratoires d'une grande entreprise de logiciels, où un chercheur se vantait d'une nouvelle technique de compression qui permettrait aux fichiers vidéo d'occuper seulement un centième de mémoire comme ils le font maintenant. Chan s'est senti obligé de souligner que Gallager avait introduit la technique en 1974. Beaucoup de ces idées prennent un peu de temps à réfléchir, dit-il, et au moment où vous les réfléchissez, il y a beaucoup, beaucoup d'options . Et vous devez vraiment réfléchir très attentivement et peut-être sur une longue période de temps avant de déterminer lequel est le bon. Bob fait ça souvent.

Muriel Médard '89, '90, MS '91, ScD '95, théoricienne de l'information au Laboratoire de recherche en électronique, est d'accord. Bob n'essayait pas de publier et de s'assurer qu'il ne se faisait pas ramasser, dit-elle. Par exemple, Médard se souvient d'une conversation entre Gallager et un éminent jeune théoricien de l'information, qui, en décrivant son propre travail, a cité un théorème récemment prouvé sur lequel il s'appuyait. Bob se met à fouiller dans les trucs, comme il le fait, dit Médard. Finalement, il a produit une copie en lambeaux d'un de ses propres papiers. Il avait cette petite preuve minuscule, dit Médard. Et c'était comme une note de bas de page. Une note de bas de page épaisse, mais une note de bas de page. ‘Ils ont nommé ça ?’ ‘Ouais, Bob, c’est un théorème majeur maintenant.’

Aujourd'hui, les codes de Gallager sous-tendent les approches qui se rapprochent le plus du débit de données maximal pour un canal de communication donné, plus proches encore que les turbocodes. En plus de leurs applications dans les télécommunications, ils commencent à remplacer les anciens codes utilisés pour protéger les données dans les lecteurs de disque et autres périphériques de stockage.

Pour des gens comme Forney, qui étaient au MIT pendant ce qu'il appelle l'âge d'or de la théorie du codage, le fait que le défi lancé par l'article de Shannon de 1948 ait été relevé est quelque peu aigre-doux. Ceux d'entre nous qui connaissent et aiment le codage hésitent à dire que le problème a été complètement résolu, dit Forney. Mais il est vrai que la plupart des gens sont passés à autre chose.

De 1950 à 1965, le MIT a été le foyer de la théorie de l'information, explique Joel West. C'était vraiment un âge d'or.

cacher