Claude Elwood Shannon, le jongleur de codes

21/12/2016
Auteurs : Marc Leconte
Publication REE REE 2016-5
OAI : oai:www.see.asso.fr:1301:2016-5:17763
contenu protégé  Document accessible sous conditions - vous devez vous connecter ou vous enregistrer pour accéder à ou acquérir ce document.
Prix : 10,00 € TVA 20,0% comprise (8,33 € hors TVA) - Accès libre pour les ayants-droit
 

Résumé

Claude Elwood Shannon,  le jongleur de codes

Métriques

19
9
796.6 Ko
 application/pdf
bitcache://324ddcc1429aa859915436e9cc09729d54796d7b

Licence

Creative Commons Aucune (Tous droits réservés)
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/1301:2016-5/17763</identifier><creators><creator><creatorName>Marc Leconte</creatorName></creator></creators><titles>
            <title>Claude Elwood Shannon,  le jongleur de codes</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2016</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Wed 21 Dec 2016</date>
	    <date dateType="Updated">Thu 26 Jan 2017</date>
            <date dateType="Submitted">Tue 15 May 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">324ddcc1429aa859915436e9cc09729d54796d7b</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>30389</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

REE N°5/2015 143 RETOUR SUR ❱❱❱❱❱❱❱❱❱ Marc Leconte Membre émérite de la SEE Le centenaire de la naissance de Claude Shannon a donné lieu à un grand nombre de manifestations scientifiques autour de ses travaux. Mais la simple énumération de ces travaux montre de manière évi- dente qu’il est difficile de les classer : mathématiques, physique ou électronique ? Ce qui est sûr, c’est que quelques-uns des travaux de Claude Shannon ont acquis très rapidement une renommée internationale qui a largement dépassé les seuls milieux scienti- fiques. On peut dire que Shannon a été le père des sciences de la com- munication et qu’il a oscillé entre les travaux théoriques et les applications pratiques qui ont marqué le début de l’informatique et de la numérisation des communications. En suivant le fil de sa biographie, nous allons voir comment se sont articulés tous ces éléments. L’enfance et les études Claude Elwood Shannon est né à Petoskey dans l’état du Michigan, le 30 avril, 1916. Son père, Claude, descendant des pre- miers colons du New Jersey, était un homme d’affaires et, pendant un certain temps, le juge des probations. Sa mère, Mabel Loup Shannon, fille d’immigrants alle- mands, était professeur de langue et principale de la Gaylord High School, à Gaylord. Claude Shannon a passé les 16 premières années de sa vie à Gaylord, où il a fréquenté l’école publique et a été diplômé de la Gaylord High School en 1932. A l’instar de la plu- part des garçons, Shannon montra un goût particulier pour la mécanique. Ses matières préférées à l’école étaient les sciences et les mathématiques, et chez lui il construisait des modèles réduits d’avions. Fait pré- monitoire, il mit au point un système télégraphique avec un ami qui habitait à un kilomètre de chez lui. Le télégraphe en question consistait à utiliser du fil de fer barbelé qu’il avait récupéré autour d’un pâturage à proximité. Il tapait des messages en morse et aimait l’idée de coder les mots avec des symboles qu’on pouvait convertir en grandeurs électriques. Sa sœur ainée étudiait les mathématiques et s’amusait à lui poser des énigmes. Shannon lisait des livres et en particulier aima beaucoup le « Scarabée d’or » d’Ed- gard Poe dont le héros trouvait un trésor en déchif- frant un cryptogramme. Il gagnait quelque argent en livrant des télégrammes pour le bureau local de la Western Union et en réparant des postes de radios pour un magasin local. Son héros d’enfance était Edison dont il apprit qu’il était un cousin éloi- gné. Plus tard, la liste de ses héros, sans éliminer Edison, s’élargit à des sa- vants tels que Newton, Darwin, Eins- tein et Von Neumann. En 1932, il entra à l’université du Michigan, à la suite de sa sœur Catherine, qui venait de réussir la maîtrise de mathématiques. En 1936, il obtint le Bachelor1 degree en génie électrique et en mathéma- tiques. Il a poursuivi tout au long de sa carrière ce double intérêt pour les mathématiques et l’ingénierie. Du MIT aux Bell Labs En 1936, Claude Shannon occupe le poste d’assis- tant de recherche au département de génie électrique au Massachusetts Institute of Technology (MIT). Ce poste lui permet de continuer ses études supérieures tout en travaillant à temps partiel pour le départe- ment. Il avait en effet découvert une annonce pour un travail d’été qui lui avait semblé parfaitement adapté à ses intérêts et ses capacités. Vannevar Bush, doyen de l’école d’ingénieur du MIT, cherchait un assistant de recherche pour manipuler (on dirait aujourd’hui programmer) et faire fonctionner l’analyseur différen- tiel, la machine à calculer la plus avancée de cette 1 Equivalent d’une licence. Claude Elwood Shannon, le jongleur de codes Claude Shannon. 144 REE N°5/2016 ❱❱❱❱❱❱❱❱❱❱❱ RETOUR SUR époque, qui permettait de résoudre par des moyens analo- giques des équations différentielles allant jusqu’au sixième ordre. Le travail consistait à traduire les équations différen- tielles en mouvements mécaniques puis à effectuer la mise en place de la machine et en cours d’exécution à trouver les solutions pour les différentes valeurs initiales. Il fallait parfois quatre assistants pour actionner les leviers tout en suivant les courbes pendant l’évolution de la machine vers la solution. Un circuit complexe de relais associés à l’analyseur différen- tiel contrôlait son fonctionnement et impliquait plus d’une centaine de relais. En étudiant ces circuits, Shannon s’intéressa à la théorie et à la conception des circuits de relais et de commutation. Il avait étudié la logique symbolique et l’algèbre de Boole dans les cours de mathématiques à l’université du Michigan et il réalisa que c’étaient les mathématiques appropriées pour l’étude de ces systèmes à deux valeurs. Il développa ces idées au cours de l’été 1937 qu’il passa aux Bell Telephone Laboratories célèbres sous le nom de Bell Labs à New York. A son retour au MIT, dans son mémoire de maitrise, il montra comment l’algèbre de Boole pourrait être utilisée dans l’ana- lyse et la synthèse de circuits informatiques. Son mémoire de maîtrise ainsi que son premier article [4], synthèse de son mémoire, suscita un intérêt considérable quand il fut publié en 1938 dans les Transactions de AIEE. En 1940, pour cet article, il fut récompensé par le Prix Alfred Noble des sociétés d’ingénierie des États-Unis, un prix décerné chaque année à une personne de moins de 30 ans pour un article publié dans une des revues des sociétés participantes (à ne pas confondre avec le prix Nobel). Par la suite il écrira plusieurs études à la fois théorique et pratique sur l’analyseur différen- tiel. Avec d’autres études sur les circuits, il pose les jalons de la conception des circuits logiques qui seront les briques de base des calculateurs, des ordinateurs et de l’électronique. Pendant l’été 1938, il retourna au MIT pour faire un tra- vail de recherche sur la conception du sélecteur rapide de la machine de Vannevar Bush et il fut principalement impli- qué dans les circuits à tubes sous vide utilisés dans ce dis- positif. En septembre 1938, à la suite d’une suggestion de Vannevar Bush, Shannon passa du département de génie électrique au département de mathématiques. Il devenait assistant d’enseignement tout en travaillant à un doctorat en mathématiques. Bush venait d’être nommé président de la Carnegie Institution à Washington, dont l’une des branches, à Cold Spring Harbor, NY, traitait de la science de la génétique. Vannevar Bush suggéra à Shannon que l’algèbre pourrait être aussi utile dans la compréhension de la connaissance génétique et présentait des analogies avec la commutation. Shannon décida de se pencher sur cette question et en fit le sujet de sa thèse de doctorat en mathématiques. Il passa l’été 1939 à Cold Spring Harbor travaillant sous la direction du généticien Barbara Burks. Il explora la possibilité d’élaborer une théorie algébrique de la génétique et développa sa thèse sous le titre « Une algèbre pour la génétique théorique ». Son superviseur pour le doctorat au MIT était le professeur Frank L. Hitchcock, un algébriste. La lettre à Vannevar Bush Le 16 février 1939, Shannon écrivit à Vannevar Bush une longue lettre programme déposée aujourd’hui à la Biblio- thèque des archives du Congrès [5]. Dans cette lettre Shannon développe une idée qui lui tient à cœur. Il vient de terminer sa thèse sur la génétique et Il indique qu’il a travaillé à la fois dans le cadre de son travail mais aussi « en off » sur quelques- unes des propriétés générales des systèmes de transmission de l’intelligence, incluant la téléphonie, la radio, la télévision et la télégraphie. Il faut noter ici l’utilisation par Shannon du mot anglais « intelligence » qui signifie renseignement ou donnée mais qui sera remplacé plus tard par communication. Shannon propose pour les systèmes de transmission un schéma de la forme suivante : T étant la transmission et R la réception, le signal (ou l’in- telligence) à transmettre et la sortie finale. Shannon indique que les systèmes réels sont affectés d’une distorsion dont il va donner une formulation mathématique. A ce stade, il ne s’agit pas de théorie mais il suggère un théorème fonda- mental qui indique qu’une identité du signal d’entrée à celui de sortie nécessite une bande passante infinie. Dès cette époque, il semble influencé par les travaux de Hartley et Nyquist publiés une dizaine d’années auparavant ; nous reviendrons sur ce point plus loin. Shannon évoque égale- Vannevar Bush penché sur l’analyseur différentiel du MIT. Source : MIT Museum. REE N°5/2016 145 Claude Elwood Shannon, le jongleur de codes ment le produit largeur de bande et temps de transmission qui sont le sujet de l’article de Hartley mais sans spécification mathématiques. Il avance une formule qui calcule la distor- sion entre l’entrée et la sortie et qui permet dans certains cas de calculer un pourcentage de bruit aléatoire. Il incor- pore donc le problème du bruit dans sa réflexion. Tout Shan- non est déjà en filigrane dans ce schéma qui préfigure celui que l’on trouve dans son papier majeur « A mathematical Theory of Communication » dont nous parlerons plus loin. Cette lettre montre que dès cette époque la communication est son sujet de réflexion principale et il propose à Vannevar Bush d’ap- profondir ce sujet en utilisant les méthodes mathématiques qu’il maîtrise parfaitement. Au printemps 1940, Shannon a passé tous les examens intermédiaires pour obte- nir à la fois une maîtrise en génie électrique et un doctorat en mathématiques mais il lui reste à passer des partiels en langue qui sont toujours ses matières les plus faibles. Il fait le forcing dans les derniers mois en embau- chant un tuteur français et allemand. Il passe finalement les examens de langue et, au printemps de 1940, il reçoit le diplôme “mas- ter degree” en génie électrique et le titre de docteur en mathématiques. Près de 40 ans plus tard, le généticien James F. Crow écrivait que Shannon dans sa thèse avait découvert des principes qui ont été redécouverts plus tard et il regrettait que cette étude n’ait pas été plus largement diffusée car il pensait qu’il aurait modifié de manière substantielle l’his- toire de la génétique. Shannon est retourné au cours de l’été 1940 aux Bell Labs afin de poursuivre d’autres recherches sur les circuits de commutation. Il y a développé une nouvelle méthode de conception des circuits qui réduisait considé- rablement le nombre de contacts nécessaires pour synthétiser les fonctions de commutation complexes à partir des réalisations antérieures. Ces études furent publiées plus tard dans un article sur la synthèse de circuits à deux bornes de commutation. Une année postdoctorale à Princeton Shannon consacre l’année scolaire 1940-1941 à une bourse de recherche nationale postdoctorale à l’Institute for Advanced Study à Princeton sous la direction d’Hermann Weyl. Ce fut durant cette période que Shannon commença à travailler sérieusement sur ses idées relatives à la théorie de l’information et des systèmes de communication. L’institut de Princeton avait été créé en 1933 et ses premiers membres étaient Albert Einstein, John Von Neumann et, à partir de 1938, Kurt Gödel. Son tuteur était Herman Weyl mais ce der- nier était un physicien théoricien et il ne s’intéressa pas à la thèse de Shannon sur la génétique qu’il qualifiait de pro- blèmes bio-mathématiques. Malgré l’environnement pres- tigieux, Shannon ne se plaisait pas beaucoup à Princeton. Le fait que Shannon ne se soit pas épa- noui à Princeton donne un éclairage sur sa personnalité et ses capacités. Shannon était déjà un mathématicien de premier ordre mais était aussi un expérimentateur. L’institut des études avancées de Princeton était un repaire de théoriciens dont la seule liste des membres suffisait à déterminer le niveau. Herman Weyl avait pensé que Shan- non pouvait trouver un terrain d’entente avec John Von Neumann mais cela ne se fit pas. Shannon restait la plupart du temps seul dans sa chambre et un peu déprimé. L’approche de la guerre devait tout changer, il quitta l’institut pour retourner aux Bell Labs où il devait donner la pleine mesure de son talent. Les Bell Labs : la fabrique d’innovations Qu’étaient donc les Bell Labs ? L’invention du téléphone avait révolutionné les com- munications de la fin du XIXe siècle. Dans les années 20, la compagnie AT&T (Ameri- can Telephone and Telegraph) succédait à la Bell Telephone Company et consoli- dait son monopole. En 1925, un groupe de recherche sur la téléphonie fut créé par AT&T pour devenir les Bell Telephone Labo- ratories afin de faire face à l’extraordinaire expansion du réseau téléphonique. Les ingénieurs faisaient leur possible pour réduire le temps de recherche des lignes et l'interconnexion des échanges imposait la composition automatique des numéros. Pour relever ce défi, les Bell Labs, comme on les appelait, avaient besoin de mathématiciens et d’ingénieurs. En effet, pour résoudre les problèmes posés, il fallait allier la rigueur des mathématiques à l’expérimentation pratique. Les uns avaient besoin des autres, les mathémati- ciens appliquaient la théorie des files d’attentes aux conflits de priorité et les ingénieurs en électricité travaillaient à la Ralph Vinton Hartley. Source : Wikipedia. Harry Nyquist - Source : Wikipedia. 146 REE N°5/2016 ❱❱❱❱❱❱❱❱❱❱❱ RETOUR SUR transmission des signaux dans les réseaux. Bientôt ces travaux se heurtèrent à un paramètre qui jusqu’alors n’avait pas paru important ni dimensionnant, le bruit. Les sifflements et les interférences se mélangeant avec la voix devenaient gênants. Les ingénieurs radio s’étaient également heurtés à ce pro- blème. On connaissait l’agitation microscopique et Einstein, dans l’un de ses articles fameux de 1905, avait formalisé ce qu’on appelait le mouvement brownien comme étant une agi- tation, conséquence de l’énergie thermique des molécules. Il montra que cette agitation affectait également les électrons libres des corps conducteurs. Les physiciens ne furent guère intéressés par l’article d’Einstein et il fallut attendre le milieu des années 20 pour que quelques chercheurs des Bell Labs, sensibles au pro- blème, s’y consacrent. Deux chercheurs suédois mesurèrent le bruit intrinsèque dans les circuits puis Harry Nyquist mit en équation les fluctuations du courant et de la tension. Il s’inté- ressa aussi à la quantité de données de télégraphie qu’ils pouvaient transmettre ainsi qu’à la vitesse de transmission. Il calcula une formule pour la vitesse de transmission des données. Pour transmettre à une certaine vitesse, un canal nécessite une certaine largeur de bande. Ralf Hartley était un collègue de Nyquist. Spécialiste des récepteurs radio, il continua les travaux de Nyquist en montrant que la quantité d’information transmise dépend du temps de transmission et de la largeur de bande du canal. Il utilisait pour la pre- mière fois le terme information. Les articles de Nyquist [6] et Hartley [7] n’attirèrent pas l’attention, on était en 1927, et ne furent pas publiés dans les revues prestigieuses de physique. Tout naturellement la revue The Bell Systems Technical Jour- nal les publia. C’est dans cette revue que Shannon prit connaissance de ces travaux. En parallèle à sa thèse sur la génétique, Shan- non développait également des idées sur les calculateurs et les systèmes de communication. Dans sa lettre à Bush de 1939, il avait fait part de ses idées sur les relations entre le temps, la bande passante, le bruit et la distorsion dans les systèmes de communication, et aussi sur la conception d’un calculateur pour des opérations mathématiques symboliques (voir paragraphe précédent). Les sujets qu’il découvrait chez Hartley et Nyquist l’intéressèrent d’emblée mais la guerre ap- prochait et il allait être réquisitionné pour d’autres tâches. Le 27 juin 1940, F. D. Roosevelt créa le National Defense Research Commitee (NDRC) afin de fédérer les travaux menés dans les structures civiles en dehors de l'aéronautique et la direction en fut confiée à Vannevar Bush. Les Bell Labs entraient dans l’ef- fort de guerre bien avant Pearl Harbour fin 1941. Bush affecta Shannon au projet 7, les mathématiques des mécanismes de commande de tir pour les canons antiaériens. La cryptologie En 1940, les Etats-Unis sont donc en train d’engager un important effort dans l’armement en raison de la menace d’extension de la guerre européenne. Thornton C. Fry, chef du département de mathématiques des Bell Labs, en charge du comité sur les systèmes de contrôle de tir antiaérien pro- pose à Shannon de se joindre à ses travaux. Il s’agissait de développer des dispositifs permettant d’observer les avions ennemis ou les missiles et de calculer le pointage de contre- missiles. Il fallait appliquer à la commande des canons les corrections d’erreurs nécessaires pour que l’obus frappe la cible avec une précision suffisante. Les avions avaient remis en cause toutes les mathématiques utilisées en balistique car, fait nouveau, les cibles se déplaçaient à des vitesses à peine inférieures à celles des projectiles. Ce problème était devenu essentiel avec le développement et l’utilisation des fusées V1 et V2 allemandes. Intercepter un avion rapide de- mandait une grande quantité de calcul. L’analyseur différentiel avait préparé Shannon à la réso- lution de tels problèmes. Un canon antiaérien se compor- tait comme un système dynamique avec ses instabilités. Les paramètres nouveaux par rapport aux expériences de laboratoire de l’analyseur étaient que les données d’entrée issues des premiers radars étaient bruitées, ce qui introdui- sait des perturbations et des erreurs. L’idée d’éliminer ou plutôt de traiter le bruit remonte sans doute pour Shannon à cette période. Sans les systèmes anti-avions américains, les destructions en Angleterre auraient été considérable- ment plus élevées. Mais bientôt, ayant contribué à l’avance- ment des méthodes de calcul d’interception antiaérienne, Shannon est affecté en 1942 aux groupes spécialisés dans les communications secrètes, ce qui correspondait davan- tage à ses souhaits. En fait, recruter Shannon dans le contexte de la guerre pour travailler sur des codes, consistait à le payer pour exer- cer son activité favorite. Shannon travailla sur le système X utilisé pour crypter les communications entre Roosevelt et Churchill. Ce projet, l’un des plus secrets avec la bombe ato- mique, était un système de transmission numérique de la parole. Il fonctionnait en échantillonnant à 50 Hz le signal analogique et en le masquant avec une clé aléatoire ce qui le faisait ressembler à du bruit de fond que connaissaient bien les radios amateurs et les ingénieurs. Shannon n’avait pas conçu ce système mais il avait l’objectif de l’analyser théoriquement ce qu’il fit. Il faisait partie d’une équipe dans laquelle on trouvait également Hartley et Nyquist. Shannon devait vérifier que le système était inviolable et était depuis 1942 consultant du Signal Intelligence Service, ancêtre de la NSA. Alan Turing, aux Bell Labs de janvier à mars 1943, REE N°5/2016 147 Claude Elwood Shannon, le jongleur de codes avait le même objectif d’analyser le système X. Turing avait avec succès décrypté la machine Enigma en Angleterre. En 1943 dans les bâtiments des Bell Labs, et plus précisément à la cafétéria, Shannon retrouvait Alan Turing autour d’un thé mais, racontera plus tard Shannon, ils ne parlèrent jamais de leur travail qui était top secret. Mais ils discutaient d’autres choses sur lesquelles nous reviendrons. Théorie des systèmes secrets A la fin de la guerre, en se rapportant aux travaux effectués durant celle-ci, Shannon écrit une étude devenue depuis un classique “A Mathematical Theory of Crypto- graphy”. C’est en fait un rapport confidentiel rédigé pour la Signal Security Agency, daté du 1er septembre 1945, qui sera déclassifié et publié en 1949 sous le titre “Communica- tion Theory of Secrecy Systems” [8]. C’est la première théorie mathématique de la cryp- tologie qui est en même temps probabiliste et algébrique. Dans l’introduction, Shannon précise qu’il n’est question que d’informations discrètes dans lesquelles le signal à chiffrer consiste en une séquence de symboles discrets faisant partie d’un ensemble fini. Ensuite le mémoire est divisé en trois parties : Fondations et structure algébrique des systèmes secrets, Théorie du secret et Pratique du secret, elles-mêmes divi- sées en près de 40 chapitres. Tout au long de cet ouvrage, Shannon revient sur les thèmes qui lui paraissent importants comme l’utilisation de l’algèbre et introduit la redondance et l’équivocation, dont nous verrons plus loin la signification. La redondance, dans le langage courant, est une aide à la com- préhension mais c’est une faiblesse de la cryptanalyse. En français par exemple, il est probable que le u suive la lettre q. Shannon remarque que chaque langue a une certaine struc- ture statistique ce qui implique une certaine redondance. Pour lui, l’anglais a une redondance d’environ 50 %, ce qui signifie que des passages peuvent être réduits de moitié sans perte de sens. Tous les systèmes secrets utilisent une clé extérieure au message lui-même. Shannon développe l’idée que les signaux comprennent un nombre fini de messages possibles transformés par un nombre fini de clés, associés à une probabilité. Il exprimait cette idée par un diagramme (figure 1). Avec ce mémoire Shannon établissait un édifice de méthodes algébriques et probabi- listes qui donnait aux cryptologues un outil dont ils n’avaient pas disposé auparavant à savoir principalement une façon rigoureuse d’évaluer la sécurité de tout système secret. Il établissait ainsi les principes scientifiques de la cryptographie, il définissait aussi les limites démontrant que, pour obtenir un code parfait c’est-à-dire inviolable, les clés doivent être également probables dans un flux aléatoire de caractères, qu'elles ne doivent être utilisées qu’une seule fois et être aussi longues que le message. Pour quantifier l’incertitude de la réalisation d’un évènement par- mi n possibles ayant des probabilités pi , Shannon donne une expression des choix possibles avec la formule suivante : Alan Turing. Source : www.biography.com. Figure 1 : Schéma d’un système de chiffrement selon Shannon (traduction du schéma original). 148 REE N°5/2016 ❱❱❱❱❱❱❱❱❱❱❱ RETOUR SUR Shannon justifie cette expression par un certain nombre de propriétés vérifiées par cette formulation. Par exemple H = 0 si et seulement si tous les pi sont nuls ou égaux à 1, H est additive pour deux choix différents grâce au logarithme et enfin H est maximum quand tous les pi sont égaux c’est- à-dire quand on a une équiprobabilité dans la constitution du message. Dans ce cas l’ennemi est dans une incertitude maximale. Shannon avec cette expression utilise la notion d’entropie qui était une notion introduite par la mécanique statistique selon Gibbs et Boltzmann. L’entropie condition- nelle a été appelée « équivocation » et mesure l’incertitude du signal chiffré par une clé statistiquement choisie. Shannon se réfère également à la théorie des jeux de Von Neumann et Morgenstern. Les méthodes mathématiques de ce mémoire et le schéma explicatif montrent de manière évidente le pa- rallèle voire l’identité que Shannon fait entre la cryptographie et la communication. Dans une interview donnée en 1984, Shannon indiquera qu’il travaillait seul chez lui sur une théo- rie de la communication et la cryptographie était un moyen de légitimer ce travail. La théorie de la communication Avec ses travaux, d’abord pour les commandes de tir puis pour la cryptographie, Shannon avait élaboré en parallèle un système de pensée centré sur la communication de signaux qu’il avait appelé « information ». Il en publie une première synthèse en octobre 1948 dans le journal des Bell Labs sous le titre “A Mathematical Theory of Communication” [9]. L’étude de 80 pages reprenait quelques points essentiels du mémoire sur la cryptographie et introduisait de nouvelles notions proches des télécommunications. Dès l’introduc- tion, Shannon cite comme référence principale les papiers de Hartley et de Nyquist et définit un schéma général des transmissions. Avec ce schéma, Shannon pose clairement les éléments du problème de la communication avec identification de la source, des fonctions de transmission et de réception et de source de bruit. Le but était de retrouver à la destination ce qui existait dans la source. Cette figure a connu une destinée extraordinaire sur laquelle nous reviendrons. Cette étude se décline en trois parties divisées en chapitres et Shannon va énoncer 23 théorèmes au fil de son étude qui traite de la transmission d’information en distinguant le caractère conti- nu ou discontinu de la source d’information et la présence ou non de bruit. Très vite (théorème n° 2) Shannon introduit un concept mathématique dans le cas discret qu’il appelle quantité d’information avec l’expression : Pi étant les probabilités de sélection et K une constante quelconque qui détermine l’unité d’information. Cette for- mule très proche de celle du mémoire de cryptologie renvoie là aussi au théorème H de Boltzmann définissant l’entropie. Cela permet de prendre en compte mathématiquement la redondance des messages. Shannon effectue ensuite le calcul de l’entropie associée à une langue suivant que l’on considère les probabilités de sélection des lettres, des couples de lettres ou d’autres associations jusqu’aux mots (il avait déjà fait cette étude avec la cryptologie). Le choix de la base deux du logarithme détermine les unités qui sont des chiffres binaires en abrégé bits (Binary Digits), mot qui sera suggéré par J .W. Tukey. Cette nouvelle unité, le bit, universel- lement utilisée, a reçu un nom qui est aujourd’hui inutilisé, le shannon dont le symbole est Sh2 . 2 https://fr.wikipedia.org/wiki/Shannon_(unit%C3%A9) Figure 2 : Schéma des systèmes de communication proposé par Shannon repris universellement. REE N°5/2016 149 Claude Elwood Shannon, le jongleur de codes Sans évoquer aucune application pratique, Shannon, au fil des théorèmes, enchaîne des raisonnements mathématiques pour résoudre un problème purement théorique sur les limites fondamentales de la communication. Ayant traité de l’unité d’information, Shannon introduit ensuite le bruit et la largeur de bande pour arriver à la limite de la capacité d’une voie de transmission et aux solutions éventuelles de compression du signal d’entrée. La capacité C est définie en posant N(T) le nombre de signaux de longueur totale T que l’on peut trans- mettre. Le taux d’émission en symboles par seconde est alors donné par C/H où H est la quantité d’information de la source. Le théorème fondamental de la voie sans bruit énonce qu’il est possible de coder les données de telle manière que l’on peut se rapprocher autant qu’on veut de la valeur limite. Il est nécessaire d’avoir un nombre de bits par symbole égal à l’en- tropie pour comprimer l’information et ce résultat est connu comme étant le premier théorème de Shannon. L’entropie ap- paraît alors comme une borne inférieure sur le taux de codage pour une compression fiable (figure 3). Si dans le cas général la voie est bruitée et si la capacité de la voie est au moins égale à l’entropie de la source, il est alors possible de coder les signaux de façon à réduire le taux d’erreur de transmission à une valeur aussi petite que l’on veut, c’est la limite de Shannon (appelé deuxième théo- rème de Shannon) qui prend la forme, après avoir effectué les approximations mathématiques et calculé les limites dues aux grands nombres : où C est la capacité maximum, P le signal, N le bruit et W la largeur de bande. Sa théorie se présente donc comme un programme de recherche sur la détermination de codes optimaux car les for- mules qu’il propose sont des théorèmes asymptotiques. En fait, cela signifie qu’il sera toujours possible de mettre au point des modèles de correction d’erreur qui surmonteront n’im- porte quel niveau de bruit. Shannon ne montre pas comment concevoir de tels modèles mais il montre que c’est possible. L’ensemble de l’étude constituait une révolution considérable dans les transmissions qui ouvrait la voie aux télécommunica- tions et à l’informatique. De nombreuses tentatives d’appro- cher la limite de Shannon ont été faites depuis, nous citerons simplement les travaux français de Claude Berrou qui, avec les turbocodes, s’approchent de la limite de Shannon. L’accueil de la théorie En 1948, Shannon n’est pas le seul à proposer le calcul de la capacité maximum d’un système de transmission. Plu- sieurs chercheurs arrivent à des formules similaires. Wiener dans son livre propose la même formule ainsi que Tuller (juin 1948), Stanford Goldman (mai 1948) et aussi André Clavier3 (décembre 1948). En France, indépendamment des travaux menés aux Etats-Unis, un ingénieur de la CFTH, Jacques La- plume, propose en 1948 quelques mois avant la publication de Shannon une formule équivalente (Cf. encadré). Si on pose le problème de l’antériorité, il faut alors mettre en avant un papier de Shannon “Communication in the Presence of Noise” [10] présenté dans les Proceedings de l’IRE (deve- nus Proceedings of IEEE) en 1948. La formule de la capacité maximum est démontrée et énoncée par le théorème 2 du papier. Mais ce qui est plus surprenant est la date de récep- tion du manuscrit qui est du 23 juillet 1940, ce qui est très tôt et date de l’époque où Shannon est encore à Princeton. Dans les interviews faites beaucoup plus tard et en réponse à la question, Shannon avance une faute de frappe pour ce 3 Clavier est un chercheur français travaillant aux Etats-Unis. Figure 3 : Schéma de transmission incorporant un correcteur d’erreur. 150 REE N°5/2016 ❱❱❱❱❱❱❱❱❱❱❱ RETOUR SUR document et indique qu’il s’agit probablement de l’année 1946. Mais même en 1946, personne n’a encore publié une telle formule, on peut donc conclure à l’antériorité de Shan- non sur ce point. La théorie fut publiée en 1949 sous forme de livre avec Waren Weaver, chef mathématicien des Bell Labs, avec un titre légèrement modifié dans la forme mais lourd de signi- fication puisque le titre avait légèrement changé et était devenu “The Mathematical Theory of Communication” [11]. En moins d’une année une théorie proposée par Shannon devenait la théorie de la communication qui deviendra bien vite la théorie de l’information qui aura un retentissement considérable. Pourtant les mathématiciens accueillirent avec réserve son travail mais peu à peu les idées présentées de- vaient s’imposer. Le résultat du canal bruité prit graduelle- ment de l’importance. Au cours des années 50, les travaux sur les méthodes de correction d’erreur devaient irriguer les sciences informatiques et les télécommunications. La notion d’information assimilée à l’entropie devait également susciter de nom- breux travaux y compris dans les sciences humaines. Des Bell Labs au MIT Shannon travaille 15 ans aux Bell Labs dans une association qui se révèle très fructueuse. Beaucoup de mathématiciens de premier ordre et de scientifiques sont alors aux Bell Labs. Durant cette période, Shannon travaille dans de nombreux autres domaines que la théorie de l’information, même si ce travail sur la communication est généralement considéré comme sa plus importante contribu- tion scientifique. En 1956, Le MIT propose à Shannon un poste de pro- fesseur invité et, en 1957-58, il devient membre du Centre pour l’étude des sciences du comportement à Palo Alto, en Californie. L’année suivante, il devient membre permanent du MIT en tant que “Donner Professor” de sciences, et continue la recherche dans divers domaines de la théorie de la com- munication. Parmi ceux-ci figurent des systèmes de commu- nication avec rétroaction et une étude de la vitesse à laquelle il est possible d’approcher du codage idéal en fonction du retard. Il poursuit son affiliation avec les Bell Labs jusqu’au 1er Juillet 1972. En 1993, l’IEEE a publié un épais volume “Shannon Collec- ted Paper” [12] qui rassemble des éléments biographiques, une interview et surtout une grande partie de ses 127 articles publiés et recensés dans diverses publications. La liste des travaux est divisée en trois parties inégales, la théorie de l’information et la cryptologie (30 papiers), les calculateurs, les circuits et les jeux (35 papiers et 10 résumés) et enfin un unique papier avec la théorie algébrique de la génétique, sa thèse de mathématiques. Les deux corpus principaux sont à peu près de taille équivalente et montre l’extraordinaire ca- pacité de Shannon à exceller dans la théorie mathématique avec ses deux papiers majeurs sur la théorie de l’informa- tion et sur les systèmes secrets, mais aussi dans le domaine des circuits avec son premier papier daté du 1er mars 1938 pour lequel il a reçu le prix Alfed Noble. Les études de circuit ouvrent la voie aux circuits logiques qui seront utilisés par la suite à la fois dans les ordinateurs mais aussi dans tous les circuits de l’électronique. Autres travaux Un autre problème que Shannon avait étudié conjointe- ment avec E.F. Moore, fut celui d’augmenter la fiabilité des circuits à relais par l’utilisation de contacts redondants, chacun d’entre eux pouvant ne pas être fiable. Là encore, c’était un problème lié à la transmission dans des canaux bruités. Shannon a également appliqué ces concepts au problème des stratégies de placement optimales en bourse. Le signal bruité est le marché boursier ainsi que des séries chronologiques connexes, le problème est de maxi- miser une fonction de gain, par choix et ajustement d’un portefeuille approprié. Nous l’avons dit, Shannon ne pouvait discuter de code avec Turing mais ils discutaient de savoir si une machine pouvait penser. Un jour Shannon arriva au Bell Labs avec un robot minuscule qui se déplaçait dans un labyrinthe. Il ne faisait rien d’autre que se déplacer dans un labyrinthe mais il trouvait son chemin. Le groupe cybernétique de Norbert Wiener appela ce robot la « souris de Shannon ». Cet auto- mate avait la particularité de trouver son chemin en tâtonnant mais si on refaisait l’expérience, elle ne tâtonnait plus car elle avait en mémoire le chemin précédent (photo ci-dessus). Dans le domaine de l’intelligence artificielle, il publia quelques études qui étaient probablement inspirées en partie par les dis- cussions qu’il avait entretenues avec Turing durant la guerre. Dans le domaine des ordinateurs et de l’intelligence artifi- cielle, Shannon publia un document [13] sur le problème de savoir comment programmer une machine pour la faire jouer aux échecs. Shannon démontrait que les calculateurs ne pou- vant théoriquement que calculer, pouvaient aussi jouer une Shannon essaye sa souris mécanique dans un labyrinthe. REE N°5/2016 151 Claude Elwood Shannon, le jongleur de codes partie d’échec complète. La stratégie développée s’appuyait sur les probabilités qui déterminaient une stratégie de jeux. A cette époque, les ordinateurs étaient lents et très difficiles à programmer. Depuis lors, de nombreux programmes de jeu d’échecs ont été écrits et la plupart d’entre eux empruntent la voie décrite dans ce document. Shannon était un joueur et il aimait créer des objets qui selon son expression ne servaient à rien, pour le seul plai- sir de la réflexion qu’il avait menée pour les concevoir. C’est dans cette catégorie que l’on peut classer une machine à calculer en chiffres romains qu’il a appelé Throbac. Shannon aimait jongler, il avait construit une machine à jongler (photo ci-contre) et publié des études [14]. Lui-même déclarait dans ses dernières interviews qu’il savait jongler de manière stable avec trois balles, à partir de quatre, cela devenait instable. Il avait conçu une machine pour résoudre les problèmes combinatoires posés par le Rubik Cube, c’est l’objet de son dernier article publié en 1982 dans le Scientific American. Conclusion Rétrospectivement l’année 1948 apparaît comme une année miraculeuse pour la science et pas uniquement pour la science de l’information. Dans ces année-là, à quelques bureaux de celui de Shannon, un de ses collègues, William Shockley, montra un jour à Shannon un petit objet qui, lui dit-il, allait remplacer les tubes électroniques. Un vote des scientifiques pencha pour l’appeler transistor. Les inventeurs du transistor se verront attribuer le prix Nobel de physique mais il n’y avait pas de prix pour les travaux de Shannon dans la communication, un manque dans les domaines du No- bel ? La révolution numérique que nous vivons aujourd’hui trouve sa source à la fois dans le transistor et dans les tra- vaux de Claude Shannon sur la théorie de l’information et dans l’électronique numérique. Si Shannon reste méconnu du grand public, il est devenu une icône dans les milieux scientifiques et techniques et il est resté longtemps le lea- der de son domaine en posant les bases d’une multitude de domaines d’études à venir. Il avait fallu la conjonction de la guerre et de l’après-guerre, ainsi que l’extraordinaire fabrique d’innovations scientifiques et techniques que représentaient les Bell Labs, pour qu’émerge cette révolution. Shannon vé- cut jusqu’en 2001, il avait forgé la technique de la deuxième partie du XXe siècle avec les télécommunications et l’informa- tique, l’existence du cyberespace dont il était l’un des fonda- teurs viendra trop tard pour lui. Claude Shannon est décédé le 24 Février 2001, à l’âge de 84 ans, après une longue lutte avec la maladie d’Alzheimer. Références [1] L’information : L’histoire - La théorie - Le déluge ; de James Gleick édition Cassini 2015. [2] Le Zéro et le Un – Histoire de la notion scientifique d’in- formation ; de Jérome Segal Edition Syllepse 2003. [3] Shannon, Claude. “Collected papers.” (1993) IEEE Infor- mation Theory Society. [4) Shannon, Claude E. “A symbolic analysis of relay and switching circuits.” Transactions of the American Institute of Electrical Engineers 57.12 (1938): 713-723. [5] Shannon, Claude E. “Letter to Vannevar Bush.” Reprinted in (1939). [6] Nyquist, Harry. “Certain Factors Affecting Telegraph Speed.” Shannon jongleur – © Stanley Rowin. Marc Leconte est secrétaire du club 2SR de la SEE, membre du comité de rédaction de la REE, membre émérite SEE et mé- daillé Ampère. Au sein de Dassault Électronique, il a passé une quinzaine d’années (1976-1991) à l’étude, au développement et aux essais en vol du radar RDI du Mirage 2000. Ensuite pendant trois ans il a participé à l’étude d’un démonstrateur Laser franco- britannique CLARA en travaillant sur les algorithmes de suivi de terrain et sur la conception assistée par ordinateur du récepteur numérique. A partir de 1995, il a élargi son activité aux domaines des études concurrentielles et stratégiques dans les domaines des radars aéroportés et de la guerre électronique. Il exerce les mêmes activités dans la division aéronautique de Thales après la fusion de Dassault Électronique et de Thomson-CSF. A partir des années 90 et en parallèle, il s’est intéressé à l’histoire des sciences et des techniques et a publié plusieurs articles s’y rap- portant. L'AUTEUR 152 REE N°5/2016 ❱❱❱❱❱❱❱❱❱❱❱ RETOUR SUR Bell System technical journal 3.2 (1924): 324-346. [7] Hartley, Ralph VL. “Transmission of information1.” Bell System technical journal 7.3 (1928): 535-563. [8] Shannon, Claude E. “Communication theory of secrecy sys- tems.” Bell system technical journal 28.4 (1949): 656-715. [9] Shannon, Claude Elwood. “A mathematical theory of communication.” Bell Systems Technical journal Vol. 27 (july and October 1948). [10] Shannon, Claude Elwood. “Communication in the presence of noise.” Proceedings of the IRE 37.1 (1949): 10-21. [11] Shannon, C. E., & Weaver, W. (1949). The mathematical theory of communication. University of Illinois press. [12] Shannon, Claude. “Collected papers.” (1993). [13] Shannon, Claude E. “Programming a computer for playing chess. National IRE convention, 1949. [14] Shannon, Claude E. “Scientific aspects of juggling.” Claude Elwood Shannon-Collected Papers (1993): 850-864. 4 http://www.academie-sciences.fr/fr/Evolution-des-disciplines-et-histoire-des-decouvertes/laplume-sous-le-masque-patrick-flandrin- et-olivier-rioul.html Quelques mois avant la publication par Shannon de son étude “A Mathematical Theory of Commu- nication”, un ingénieur français travaillant à la CFTH (Compagnie française Thomson-Houston) publie en avril 1948 une note dans les publications de l’Aca- démie des sciences sur « Le nombre de signaux discernables en présence de bruit erratique dans un système de transmission à bande passante limitée ». Jacques Laplume est alors employé comme ingénieur radioélectricien au labo- ratoire hyperfréquence de la CFTH, annexe Lecourbe, dans le 15e ar- rondissement de Paris. L’originalité de son approche tient au fait qu’il a mené ses développements de fa- çon isolée, indépendamment des autres travaux contemporains, en particulier de ce qui se faisait aux Etats-Unis avec Shannon. Laplume publie un peu plus tard un article dans la revue ancêtre de la REE, l’Onde électrique, qui développe la note à l’Académie qui pouvait être considérée comme trop concise et sans doute un peu difficile d’accès. C’est une approche qui intègre complètement l’aspect probabiliste en utilisant les notions de bruit spectral et de densité spectrale de puissance ainsi que de bande passante de circuit. C’est donc une approche très pratique du problème. Laplume utilise la notion d’incertitude en définis- sant des rectangles d’incertitude de fréquences et il utilise les résultats de l’analyse combinatoire des probabilités pour arriver à la même formule que Shannon. La note qu’il a ainsi publiée est restée igno- rée et éclipsée par les travaux de Shannon et sans doute aussi par la toute puissance de la recherche américaine d’après-guerre face au reste du monde et à la France de la quatrième République en parti- culier. Redécouvert en 1997 dans la thèse de Jérome Ségal, une note de l’Académie de sciences publiée dans « L’évolution des disciplines et histoire des découvertes » lui est consacrée4 . Jacques Laplume est diplômé de l’ESPCI et débute à la Société de force et lumière électrique (FORCLUM). Il décroche un emploi pour cinq ans à la CSF en tant qu’ingénieur de recherche en optique électronique et radiocom- munications. Il écrit à cette époque un livre sur le calcul symbolique. Après la guerre il entre à la compagnie fran- çaise Thomson Houston (CFTH) dans le laboratoire de recherche en hyper- fréquence qui deviendra le département Radar hyperfré- quence. En 1958, il est affecté au département d’études nucléaires pour l’expérimentation de la première bombe atomique française. En 1966 il est directeur des études d’une filiale ingénierie de la CFTH, la SODETEG. Il exerce son activité dans de nombreux domaines des transports et de l’environnement. Il part en retraite en 1981. Il s’est éteint le 22 mai 2008 à 87 ans. Un Français contemporain de Shannon : Jacques Laplume > Une exposition sur Claude Shannon est organisée au musée des Arts et Métiers du 13 décembre 2016 au 12 mars 2017 http://shannon100.com/ Jacques Laplume en 1945.