Retrouvez cet article dans : Misc 20

A vulgairement parler, nous vivons actuellement dans ce que d'aucuns nomment la société de l'information, qui nous envahit par tous les pores. Nous sommes à l'avènement de l'ère du tout numérique. Les zéros et les uns sont les seigneurs, circulent de ci de là, et ils repasseront par ici s'il ne sont pas déjà passés par-là, dans les communications filaires, par fibre optique, par ondes radio. Cependant, si l'on pose à la cantonade la question " Qu'appelle-t-on exactement ‘information’ et comment peut-on mesurer l'information ? ", je demeure persuadé que les réponses seront diverses, éloignées les unes des autres et que la convergence des définitions sera très modérée. Pourtant, ces questions ne sont pas si nouvelles. Déjà au cours des années 1920 et 1930, certaines d'entre elles tarabustaient les ingénieurs, les philosophes et les ingénieurs-philosophes, qui travaillaient tant dans le domaine naissant des télécommunications que dans le domaine plus intellectuel du Cercle de Vienne. Cependant, l'on s'intéressait plus à obtenir une sémantique universelle qu'à proprement parler une quantification de l'information... Ce n'est pas l'aspect philosophique qui conduisit Shannon à élaborer sa théorie, mais plutôt des considérations ne relevant que d'une pure ingénierie. Il s'exprime clairement et dit mettre de côté tous les aspects sémantiques des langages pour ne s'intéresser qu'à l'aspect mathématique, mesurable de l'information. D'ailleurs le titre de son mémoire s'intitule Une Théorie Mathématique de la Communication et non pas de l'information. Dans la suite, nous allons voir quelles furent les contributions de Shannon et comment l'impact énorme qu'elles eurent les établit de fait comme La Théorie de l'Information.

1  Les débuts de la quantification de l'information

Le problème était dans l'air dans l'entre-deux-guerres, étant donné l'essor considérable des communications radio et les problèmes de fiabilité des transmissions récurrents qui résultaient de ce canal de transmission particulier. Les ingénieurs cherchaient à modéliser ce qui se passait afin d'être capable de rendre les transmissions plus fiables sans accroître la complexité de la transmission. Un des premiers à avoir tenté de définir et de quantifier l'information est R. V. L. Hartley. Dans les années 20, il publia un article " Transmission of information ". Il y introduisait une mesure simple de l'information, séduisante et pratique. Supposons qu'un émetteur souhaite envoyer un message de n lettres, par exemple en français à une personne située à l'autre bout du récepteur. Comme notre alphabet dispose de 26 lettres, sans compter la ponctuation, les lettres accentuées, ni les espaces, il aurait exactement 26 possibilités pour chaque lettre choisie. Donc, parmi les 26n messages de n lettres possibles, l'émetteur en choisit un dans cet ensemble. A priori, sans connaître le contenu du message, le récepteur considère que les 26n messages possibles sont équiprobables. Le récepteur a donc une incertitude sur le mot qu'il recevra, incertitude levée dès la réception du message. Ainsi, on peut considérer que l'information qu'il reçoit correspond à une réduction de l'incertitude. Ce qu'avait vu Hartley et ce qui sera repris dans la suite par Shannon est que l'information correspond à la réalisation d'un événement particulier parmi un certain nombre d'événements possibles et donc à une réduction de l'incertitude. En termes mathématiques, l'incertitude est caractérisée par ce que l'on nomme des variables aléatoires. Comme mesure de l'information, Hartley proposa la fonction mathématique additive la plus naturelle, à savoir la fonction logarithme. Cela correspond à une certaine logique, puisqu’il semblerait légitime de considérer que l'information apportée par un message de n lettres correspond à la somme des informations apportées individuellement par chacune des lettres composant le message. Chez Hartley, la quantité d'information apportée par un mot de n lettres est définie par la valeur I suivante :

I = log2 26n

Il s'agit de la valeur du logarithme en base 2 du nombre de valeurs possibles du message. En utilisant les propriétés de la fonction logarithme, si l'on considère un message formé de L = m+n lettres, alors on a :

I = log2 26m+n = log2 26m + log2 26n

Pourtant, l'information du message total correspond bien à la somme des informations de bouts qui forment le message. La mesure de Hartley s'avère adaptée à un certain nombre de problèmes. Je reprends un exemple inspiré des notes de cours de James Massey [1]. Supposons que l'on veuille attribuer un numéro d'identification unique à 4 personnes distinctes et de la manière la plus concise possible. Comment peut-on faire ? Quel est le nombre minimum de symboles d'information que l'on va devoir utiliser ? Si l'on en croit Hartley, dans notre cas, l'information vaut log2(4) = 2. Et effectivement, nous pouvons identifier 4 personnes de manière uniques avec 2 symboles 0 et 1, en attribuant :

• 00 à la première personne ;
• 01 à la seconde ;
• 10 à la troisième ;
• 11 à la quatrième.

L'information telle que Hartley l'avait définie semblait donc assez raisonnable dans ce cas précis. Cependant, cette mesure n'était pas satisfaisante sur un grand nombre de points, car elle ne répond pas à certains critères que nous pourrions attendre d'une bonne définition de l'information. Plaçons-nous dans le cas où nous recevrions un message, par exemple un courrier électronique, lettre après lettre.

• En Français, comme dans toute autre langue, il y a des lettres plus fréquentes que d'autres. Par exemple, hormis dans La Disparition de Georges Perec, la lettre " e " est la lettre la plus fréquente, puis le " s " et enfin la lettre " k " est une des moins fréquentes. Donc, si au cours du message nous recevons un " k ", l'information véhiculée par le " k " sera plus importante que celle véhiculée par la lettre " e ". En effet, il y a beaucoup moins de mots en français qui contiennent un " k " que de mots qui contiennent un " e ". Or, avec la mesure de Hartley, chaque lettre vaut la même quantité d'information égale à log2 26 = 4,7. Si l'on considère une autre langue, on peut reprendre la même analyse et on obtiendra des valeurs différentes suivant le nombre de lettres considérés.
• De même, si nous recevons la lettre " q ", alors nous savons qu'il est extrêmement probable que cette lettre soit suivie par la lettre " u ", donc nous pouvons prédire avec une grande probabilité que la lettre suivante sera la lettre " u ". L'information propre véhiculée par la lettre " u " qui suit " q " sera donc plus faible que dans le contexte où la lettre " u " serait reçue, mais précédée de la lettre " o ".
• En dernier ressort, il est clair que la quantité d'information apportée dépend du moment de la réception de cette information. C'est un peu le syndrome du scoop du journaliste pour lequel l'information n'a sa plus grande valeur que s’il est le premier à l'apporter. Une fois divulguée, c'est-à-dire une fois connue, l'information apportée est nulle.

Ces trois points soulèvent de multiples problèmes que la mesure de l'information telle que Hartley la considérait ne peut pas résoudre. En effet, son information est absolue, tandis que l'information est relative, fortement dépendante du contexte. C'est Shannon qui, en 1948, proposa une mesure élégante de l'information permettant de résoudre ces différents problèmes.

2  Shannon et l'avènement de la théorie de l'information

Je ne reviendrai pas sur la biographie de Shannon mort en janvier 2001. Pour plus de précisions, on pourra se référer au livre de Jérôme Segal [2]. L'article fondateur de la théorie de l'information actuelle fut un rapport de recherche daté de 1948 et intitulé " A Mathematical Theory of Communication ". Depuis toujours Shannon, ingénieur de formation, s'intéressait aux mathématiques dans un but précis : celui d'élaborer une théorie mathématique de la communication. La Seconde guerre mondiale le mit en relation avec des mathématiciens de grande envergure tels Turing et Von Neumann qui, sans doute, lui apportèrent beaucoup. Puis, vint en 1948 ce fameux article qui fit au départ grand bruit dans la communauté des ingénieurs en communication, puis dans toutes les communautés qui s'intéressaient à la notion d'information. La théorie de Shannon permettait désormais de répondre quantitativement à des problèmes qui, jusqu'alors, se posaient de manière qualitative. Si sa théorie fut si vite adoptée, c'est en partie parce qu'elle battait en brèche un certain nombre d'idées reçues et permettait sur un plan prospectif d'envisager des développements technologiques considérables. L'idée initiale de Shannon que reflète la manière dont il s'est attaqué à la théorie et les outils mathématiques utilisés est la suivante. Je reprends ici une phrase de J. Massey [1] : For Shannon information is what we receive when uncertainty is reduced. Soit : " Pour Shannon, l'information est ce que l'on obtient quand l'incertitude est réduite. " Comme les théories mathématiques mises en jeu sont délicates à introduire, nous nous contenterons de prendre un exemple pour effleurer l'aspect novateur de la conception de Shannon. Supposons qu'un référendum doive avoir lieu dans un certain pays. La question que l'on pose aux électeurs est une question à laquelle ils doivent répondre par " oui " ou bien par " non ". Tant que le vote n'a pas eu lieu, le résultat est incertain. A priori, sans aucune information additionnelle, il y a 50% de chances que le " oui " l'emporte et 50% que le " non " l'emporte. On cherche donc des moyens de réduire l'incertitude a priori, c'est-à-dire avant de connaître le résultat du vote. Un moyen très employé est de commanditer des sondages. Supposons que l'on a accès au dernier sondage pré-électoral qui donne le " non " vainqueur avec 54% des voix par rapport au " oui " qui n'obtiendrait lui qu'un misérable 46%. Ce sondage apporte une certaine quantité d'information additionnelle par rapport au choix de départ qui plaçait les deux issues du scrutin à 50-50. La probabilité que le " non " l'emporte est désormais plus élevée et un renversement de situation est plus improbable. Le sondage m'a donc apporté une quantité d'information me permettant de réduire mon incertitude en fonction du scrutin et permet également à Mme Soleil de pouvoir prédire l'avenir de façon plus fiable. C'est de cette manière que Shannon considère l'information. Celle-ci correspond à une diminution de l'incertitude sur ce que l'on sait a priori. Revenons à la mesure de cette incertitude à savoir, comment la quantifie-t-on ? Il est clair que dans le cas où le " oui " et le " non " sont à 50-50, l'incertitude sur le résultat du scrutin est maximale. En revanche si on a 46-54 après le sondage, le résultat est moins incertain et les partisans du " oui " peuvent par avance aller noyer leur chagrin dans l'alcool. D'un point de vue quantitatif, nous devons donc déterminer une fonction mathématique qui permette de mesurer l'incertitude. À l'issue du scrutin, l'incertitude sur le résultat est nulle puisque celui-ci est désormais connu. Afin de mesurer cette incertitude, nous devons donc définir une fonction mathématique qui vérifie déjà les propriétés suivantes :

• Être maximale quand l'incertitude est maximale.
• Être nulle quand il n'y pas d'incertitude sur le résultat.

Dans le cas qui nous intéresse où il n'y a que deux choix possibles. La grandeur qu'a définie Shannon est la suivante :

H = - p log2 (p) - (1-p) log2(1-p)

où p désigne la probabilité que le " oui " l'emporte et 1-p constitue la probabilité que le " non " l'emporte. Cette mesure est très intéressante, car elle correspond également à une grandeur physique appelée entropie qui mesure la quantité de désordre dans un système physique. C'est ainsi que cette grandeur s'appelle également entropie de l'information. Elle peut également susciter quelques vocations philosophiques sur les relations entre information et désordre... L'unité de la mesure de l'information est définie comme étant le bit. Pour ne pas le confondre avec le 0 ou le 1 de l'ordinateur, on parle en général de bit d'information. En reprenant notre exemple précédent, mesurons dans les divers cas envisagés l'entropie de notre information.

• Cas où l'on n'a pas l'information des sondages a priori.

Alors, le " oui " et le " non " sont équiprobables. Dans ce cas p = 1- p = 50/100 = 0,5. On a :

Hpas d'info = - ( 0,5 log2 0,5 + 0,5 log2 0,5) = 1

• Cas où le sondage nous donne " oui " à 46% et " non " à 54%.

Dans ce cas, p= 46/100 = 0,46 et 1-p = 0,54. Alors

Hsondage = - (0,46 log2 0,46 + 0,54 log2 0,54 ) = 0,9915

• Cas où le résultat " non " est connu, après le scrutin.

Il n'y a plus aucune incertitude sur le scrutin. On a alors  p = 0, 1-p = 1, et

Hscrutin = 0

L'incertitude sur le résultat est donc nulle. Cet aspect corrobore donc la logique. Plus on a d'information, moins l'incertitude est grande et c'est bien ce que l'on recherchait. Partant, l'information obtenue correspond à la différence des incertitudes mesurées avant l'apport d'information par rapport à l'incertitude que l'on détient une fois que l'information aura été reçue. En effet, mettons que je n'aie accès à aucun sondage, alors l'information reçue sera mesurée par :

I1 = Hpas d'info - Hscrutin = 1  bit

Si j'ai accès au sondage, alors le résultat du scrutin me fournira légitimement moins d'information puisque je m'attendrai à une victoire du non. Dans ce cas, l'information obtenue sera :

I2 = Hsondage - Hscrutin = 0,9915  bit

La quantité d'information que m'apporte le sondage par rapport à mon hypothèse de départ est donc I1-I2 = 0,0085 bits d'information. On pourrait s'amuser à vérifier que la mesure de Shannon de l'information remplit bien tout ce que l'on attend d'elle, mais ceci requierrait que l'on définisse des outils mathématiques issus de la théorie des probabilités et dépassant de loin le cadre de cet article introductif. Le lecteur intéressé par l'aspect mathématique peut se référer aux notes de cours de J. Massey qui sont très complètes et disponibles en ligne à l'adresse suivante : http://www.isi.ee.ethz.ch/education/public/free_docs.en.html

3  L'impact de la théorie de Shannon

Je me rappelle encore de ce jour de janvier 2001 lorsque, aux informations à la radio entre deux chansons et quelques faits divers, le présentateur dit qu'un certain bonhomme du nom de Claude Shannon était mort et que c'était quelqu'un qui avait fait des découvertes importantes en informatique. Cet encart dura au mieux quelques secondes, puis fut rapidement oublié dans la chanson qui suivit. Il demeure assez étonnant que le nom de Shannon ne soit connu que des initiés tandis que l'impact de sa théorie fut et reste immense, tant dans le domaine de la transmission et de la sauvegarde de l'information que dans le domaine de la protection de l'information. Au-delà même du fait d'avoir défini la notion d'information en termes mathématiques et fourni les moyens de la mesurer, l’œuvre de Shannon démontre la force de la théorie au service de l'ingénierie. Cette force a pu se mesurer dans les développements faramineux de l'information numérique depuis plus de 50 ans. En outre, les résultats de Shannon ont, d'une part, bouleversé des idées reçues et, d'autre part, réorienté la recherche appliquée vers des pans jadis négligés des mathématiques. L'arithmétique et l'algèbre un peu délaissées jusqu'alors ont repris droit de cité aux côtés des autres disciplines mathématiques comme l'analyse et la théorie des probabilités qui sous-tendent les théories de la physique. Dans l'article fondateur de Shannon, les bombes qui firent grand bruit et bousculèrent les préjugés ont pour nom " Théorèmes de Shannon ". En bref, voici ce que cela donne. Une communication entre deux personnes se modélise par un canal de transmission sur lequel on applique des perturbations, que l'on appelle " bruit ". Le canal peut être une fibre optique ou bien tout simplement l'air, pour les ondes radio, ou tout autre support. Ce qui importe est de pouvoir transmettre fidèlement de l'information au travers de ce canal de telle manière que la personne qui reçoit cette information puisse correctement l'interpréter. Chaque signal émis sur le canal correspond à une quantité d'énergie dépensée. Avant Shannon, il était communément admis que, si le récepteur avait des problèmes d'interprétation de l'information à cause d'un bruit trop important, il suffisait d'augmenter l'énergie du signal pour pallier le problème. Shannon a prouvé que cela était faux et que l'on pouvait associer au canal de transmission une grandeur dénommée capacité, spécifiant la quantité maximum d'information que l'on peut transmettre au travers du canal par unité de temps. Il a également démontré qu'il était possible, du moins en théorie, de transmettre l'information à un taux égal à la capacité du canal en l'encodant proprement. De là sont nées deux disciplines désormais bien établies :

• Le codage de source : Le principe consiste à mesurer la quantité d'information véhiculée par un médium – message, fichier, image, son numérisé ou autre. Cette mesure permet d'élaborer des algorithmes de compression efficaces comme par exemple le codage entropique, codage de Huffman et plus généralement n'importe quel type d'algorithme de compression de texte, d'image ou bien de son. Ainsi, on réduit l'encombrement du médium en transmission ou bien en stockage.

• Le codage de canal : Le principe du codage de canal consiste à préserver l'intégrité du médium transmis à travers un canal, en présence de bruit. On rajoute à l'information ce que l'on appelle de la redondance. Il faut en rajouter un minimum, mais suffisamment tout de même pour que le récepteur puisse retrouver de manière fiable le médium envoyé, malgré les perturbations liées au bruit. La quantité de redondance minimale à ajouter est définie par la capacité du canal. Bien que Shannon eût montré qu'il était possible en théorie d'atteindre ce minimum, en pratique, construire de tels codes optimaux reste un problème ouvert. On peut tenter néanmoins d'approcher ce minimum. Pour ce faire, on utilise des objets algébriques appelés codes correcteurs d'erreurs, qui permettent comme leur nom l'indique de corriger des erreurs ajoutées. Les exemples les plus classiques sont les codes de Hamming utilisés dans la mémoire ECC et qui corrigent une erreur, les codes de Reed-Muller utilisés par les premières transmissions satellites, les codes de Reed-Solomon que l'on retrouve dans les CD-ROM et qui font en sorte qu'un CD reste lisible malgré des griffures à sa surface et puis les codes convolutifs que l'on trouve dans les téléphones portables et puis...

En 1949, Shannon publia également un article sur les systèmes de chiffrement à clé secrète. Il avait travaillé sur ce sujet pendant la guerre. Encore une fois, les principes qu'il établit restent d'actualité. Il a en particulier montré que l'on pouvait modéliser un système cryptographique de chiffrement comme un canal de transmission bruité par un adversaire. Attaquer le système revient donc à pouvoir corriger les erreurs. De là, il introduisit les concepts de confusion et de diffusion, concepts qui trouvent leur application dans la construction de systèmes de chiffrement à clé secrète tels les LFSR ou bien les systèmes de chiffrement par bloc. Comme conclusion, nous pouvons dire sans trop nous tromper que nous sommes dans l'ère de Shannon et que cela risque de durer longtemps. Références :

• [1] Massey (J.) , Applied digital information theory. http://www.isi.ee.ethz.ch/education/public/Free_docs.en.html
• [2] Segal (J. ), Le Zéro et le Un : Histoire de la notion scientifique d'information au 20ème siècle, 2003.

  Retrouvez cet article dans : Misc 20