La théorie de l’information
Olivier Rioul
To cite this version:
Olivier Rioul. La théorie de l’information. Belin. Traitement de l’Information (La Main à la Pâte),
Belin, pp.7, 2020, Culture et Connaissances. �hal-02287327�
HAL Id: hal-02287327
[Link]
Submitted on 20 Aug 2021
HAL is a multi-disciplinary open access L’archive ouverte pluridisciplinaire HAL, est
archive for the deposit and dissemination of sci- destinée au dépôt et à la diffusion de documents
entific research documents, whether they are pub- scientifiques de niveau recherche, publiés ou non,
lished or not. The documents may come from émanant des établissements d’enseignement et de
teaching and research institutions in France or recherche français ou étrangers, des laboratoires
abroad, or from public or private research centers. publics ou privés.
La théorie de l’information
Olivier R IOUL, professeur à Télécom ParisTech et à l’École Polytechnique
La révolution numérique que nous connaissons aujourd’hui doit énormément à
la théorie de l’information de Shannon. La question à la base de la théorie est
toute naturelle : peut-on mesurer l’information, contenue dans un message ou
transmise dans un canal de communication ? En se basant sur les probabilités et
la notion d’entropie, la théorie décrit rigoureusement cette notion d’information
pour résoudre des problèmes de compression et de transmission de données
numériques et en trouver les limites fondamentales de performances.
Claude S HANNON (1916–2001) est un ticien dont les théorèmes ont rendu pos-
mathématicien et ingénieur américain sible le monde du numérique que nous
haut en couleurs. Adepte du monocycle connaissons aujourd’hui.
et du jonglage, il s’est amusé à construire Décrivons quelques unes de ses contri-
des machines plus ou moins loufoques : butions les plus marquantes :
une souris qui apprend et retrouve son
chemin dans un labyrinthe, une machine Le paradigme de communication.
à jouer aux échecs, à résoudre le Rubik’s Dans le paradigme de la communication
cube, une calculatrice en chiffres romains, selon S HANNON, un message émis par
un robot qui jongle avec trois balles, et une source d’information est transmise
même une « machine inutile » qui, dès dans un canal bruité puis reçu par le
qu’on l’allume, actionne une main pour destinataire (Fig. 1). Si cela peut paraître
s’éteindre elle-même. . . Dans le même aujourd’hui naturel, ça ne l’était pas
temps, il a fait des avancées théoriques à cette époque : pour la première fois,
décisives dans le domaine des circuits lo- on y distingue clairement les rôles de
giques, de la cryptographie, de l’intelli- la source, du canal et du destinataire ;
gence artificielle. . . de l’émetteur et du récepteur ; et du
Mais surtout, S HANNON créé la théorie signal et du bruit. Ce paradigme a eu un
de l’information en 1948, dans un seul ar- impact immense, jusqu’en psychologie,
ticle – A Mathematical Theory of Commu- en linguistique ou en sciences sociales, si
nication – qui rassemble tellement d’avan- bien que dans les années 1950, S HANNON
cées fondamentales et de coups de génie en vient lui-même à mettre en garde ses
que S HANNON est aujourd’hui le héros de contemporains contre les dérives d’une
milliers de chercheurs. C’est le mathéma- telle popularité.
1
SOURCE
ÉMETTEUR CANAL RÉCEPTEUR DESTINATION
D’INFORMATION
- - - -
SIGNAL
SIGNAL
REÇU
6
MESSAGE MESSAGE
SOURCE DE
BRUIT
F IGURE 1 – Le paradigme de S HANNON.
L’aspect probabiliste. Laissant délibéré- de binary digit (chiffre binaire). Mais le
ment l’aspect sémantique de côté, S HAN - l’unité binaire d’information de S HAN -
NON introduit pour la première fois un NON va plus loin que le simple chiffre
modèle probabiliste pour toutes les va- binaire, car il prend en compte l’aspect
riables en jeu dans la communication et probabiliste de l’information. Pour lui,
fonde ainsi sa théorie sur celle des proba- un bit aléatoire peut très bien porter une
bilités, qui avait trouvé sa forme définitive information qui est en fait inférieure
quinze ans plus tôt avec les travaux d’An- à un bit ! Aujourd’hui, l’unité officielle
dreï KOLMOGOROV (1903–1987). KOLMO - de mesure d’information s’appelle... le
GOROV lui-même fut un ardent défenseur Shannon (sh).
de la théorie de l’information, qui selon
lui devait « précéder la théorie des proba-
bilités », et non l’inverse. Les limites de performances. S HAN -
NON énonce et résout le problème théo-
rique de la communication. Il ne pro-
L’unité d’information. S HANNON re- pose quasiment aucune solution pratique,
prend l’idée exposée vingt ans auparavant mais établit des limites de performances,
par Ralph H ARTLEY (1888–1970) d’une ce qui est au moins aussi important. Avant
mesure logarithmique de l’information, S HANNON, des moyens de communica-
en privilégiant l’unité binaire : puisqu’un tion comme le télégraphe ont été dévelop-
chiffre binaire représente 2 symboles (0 et pés pour ainsi dire dans le brouillard, sans
1), deux chiffres 4 symboles, trois chiffres le repère théorique permettant de savoir
8 symboles. . . représenter un message jusqu’où on peut aller. Depuis S HANNON,
parmi N requiert donc log2 N chiffres on sait que pour des ressources données,
binaires, où log2 est le logarithme en base quoique nous fassions, le meilleur sys-
deux. S HANNON popularise à cette occa- tème de communication fiable ne pourra
sion le terme « bit » qu’il attribue à John jamais dépasser une certaine limite sur
T UKEY (1915–2000), comme contraction le débit d’information. C’est comme si
2
S HANNON avait démontré la vitesse de la raconte que c’est John VON N EUMANN
lumière sans dire comment construire la (1903–1957) qui recommande à S HANNON
fusée qui pourrait s’en approcher. Cela a d’utiliser le terme « entropie » car lui dit-il,
énormément stimulé la recherche de solu- « personne ne sait vraiment ce qu’est l’en-
tions pratiques permettant de s’approcher tropie, de sorte qu’en cas de débat vous
des limites de Shannon. aurez toujours l’avantage. »
L’entropie. Un message se modélise
comme une suite de variables aléatoires
X 1 , X 2 , X 3 , . . . correspondant chacune à un
symbole qui peut prendre un nombre Le premier théorème de Shannon. La
fini de valeurs. Si nous supposons que la notion d’entropie permet à S HANNON de
source qui émet ce message est « sans résoudre le problème théorique de la com-
mémoire », ces symboles sont choisis pression d’une source pour un canal sans
indépendamment les uns des autres et bruit. Pour cela, il suffit de ne coder que
avec la même loi de probabilité. En les messages (x 1 , x 2 , . . . , x n ) typiques de
notant p(x) la probabilité qu’un sym- probabilité ≈ 2−nH . En sommant les pro-
bole égale x, la probabilité d’un message babilités de ces N messages, on obtient
donné (x 1 , x 2 , . . . , x n ) est le produit des une probabilité totale très proche de 1 ≈
probabilités individuelles : N · 2−nH , d’où N ≈ 2nH , soit un débit de
Y (log2 N )/n ≈ H bits par symbole. C’est le
p(x 1 ) · p(x 2 ) · · · · · · · · · p(x n ) = p(x)n(x) premier théorème de Shannon qui affirme
x
que H bits par symbole suffisent pour
où n(x) est le nombre de symboles du comprimer fidèlement une source d’in-
message (x 1 , x 2 , . . . , x n ) qui sont égaux à x. formation. L’entropie H apparaît être une
Par la loi des grands nombres, quand la borne inférieure sur le débit nécessaire
longueur n du message tend vers l’infini, pour coder l’information de façon fiable.
le rapport n(x)/n tend vers p(x) si bien
Ce théorème est asymptotique (il n’est
que la probabilité d’un message tiré au
valable que lorsque n tend vers l’infini)
hasard vaut à peu près
et ne donne aucun moyen pratique pour
comprimer un message. Mais S HANNON –
Y
p(x)np(x) = 2−nH
x et, indépendamment, Robert FANO (1917–
2016) – ont l’idée de considérer un code
où à longueur variable où les symboles les
X 1
H= p(x) log2 plus probables sont codés par les codes les
x
p(x)
plus courts, de sorte que le débit moyen
est une quantité positive que S HANNON devient assez proche de H . Quatre ans
appelle l’entropie par analogie avec la plus tard David H UFFMAN (1925–1999) dé-
notion étudiée en thermodynamique et crira l’algorithme optimal de compression
en physique statistique. La petite histoire dans ce contexte.
3
L’information mutuelle. S HANNON être quasi-parfaite ! Ce théorème à lui seul
fonde également sa théorie sur la quantité justifie l’explosion du numérique aujour-
d’hui.
X p(x, y)
I (X ; Y ) = p(x, y) log2 Lorsque le bruit présent dans un canal
x,y
p(x)p(y)
de transmission est modélisé par du bruit
que FANO nomme information mutuelle blanc gaussien qui s’ajoute au signal à la
et qui mesure la quantité moyenne réception, S HANNON trouve l’expression
d’information entre deux variables aléa- exacte et étonnamment simple :
toires X et Y . C’est la première fois que ³ P´
C = W · log2 1 + bit par seconde
le concept – jusque là flou – d’informa- N
tion transmise dans un système trouve où W est la largeur de bande et P /N le rap-
une théorie rigoureuse. port signal à bruit présent dans la trans-
mission. C’est certainement la formule la
Le deuxième théorème de Shannon. plus connue de S HANNON : elle fournit un
La notion d’information mutuelle permet aspect concret de la théorie de l’informa-
à S HANNON de résoudre le problème théo- tion qui a séduit de nombreux ingénieurs
rique de la transmission dans un canal dès sa parution. Pas moins de 7 autres
bruité d’entrée X et de sortie Y . Il s’agit chercheurs publient une formule similaire
cette fois de maximiser le débit d’infor- la même année 1948 !
mation transmis tout en garantissant une
L’héritage de S HANNON en a dérouté
communication arbitrairement fiable du
plus d’un : ses théorèmes prévoient qu’il
message au destinataire. Pour cela S HAN -
existe de bons systèmes de codage pra-
NON démontre que l’on peut choisir un
tiques, mais ne disent pas comment les
code au hasard selon une distribution de
construire. Paradoxalement, ses démons-
probabilité qui rend I (X ; Y ) maximal et
trations suggèrent que des codes choisis
nomme ce maximum
au hasard forment des solutions quasi-
C = max I (X ; Y ), optimales (mais irréalisables en pratique).
p(x)
Il a fallu 50 ans pour que Claude B ER-
la capacité du canal. C’est le deuxième ROU (né en 1951) et Alain G LAVIEUX (1949–
théorème de Shannon qui affirme qu’on 2004) proposent une solution pratique
transmettre l’information de façon fiable (les turbo-codes) qui « imite » le codage
tant que le débit ne dépasse pas la capa- aléatoire et permet de s’approcher de la
cité C du canal. Ce théorème est une véri- capacité.
table révolution qui a changé le monde : Tout ceci n’est qu’un aperçu. La théo-
pour la première fois, on comprend que rie de l’information n’a jamais été aussi
le bruit présent dans le canal ne limite vivante et trouve de nombreuses applica-
pas la qualité de la communication, il tions en réseaux sans fil, en sécurité de
ne limite que le débit de transmission. À systèmes embarqués, en gestion de por-
la condition de ne pas dépasser la capa- tefeuilles, en séquençage génomique, et
cité, la communication numérique peut même en interactions homme-machine.
