Théorie de l'information et entropie

Objectifs du chapitre

À la fin de ce chapitre, vous serez capable de:

expliquer pourquoi la quantité d'information d'un événement ne dépend que de sa probabilité, et justifier la forme $- lo g_{2} p$ par l'additivité sur des événements indépendants;
calculer l'entropie de Shannon $H (X)$ d'une source discrète en bits par symbole, y compris lorsque certaines probabilités sont nulles;
démontrer les bornes $0 \leq H (X) \leq lo g_{2} n$ et caractériser les deux cas d'égalité;
reconnaître la fonction d'entropie binaire, son maximum en $1/2$ et sa pente infinie au voisinage de $0$ et de $1$ ;
calculer une entropie conjointe, une entropie conditionnelle et une information mutuelle sur une table de probabilités complète, et vérifier numériquement la règle de chaînage;
mesurer la redondance d'une source et dire à quoi elle sert: le chapitre 7 la supprimera pour comprimer, le chapitre 8 la rajoutera pour corriger.

La question que Shannon a posée

Les cinq premiers chapitres ont demandé combien d'opérations coûte un calcul et ce qu'une machine peut calculer. Les cinq suivants posent la troisième question du cours: combien de bits? Combien faut-il de bits pour stocker un texte, transmettre une photographie, décrire l'état d'un capteur? Et surtout: existe-t-il une limite en dessous de laquelle aucun procédé, si ingénieux soit-il, ne pourra descendre?

Avant 1948, cette question n'avait pas de réponse parce qu'elle n'avait pas de formulation. On savait compter les caractères d'un télégramme et les impulsions d'une ligne, mais on ne savait pas dire ce qu'était la quantité d'information d'un message, et encore moins la comparer d'un message à l'autre. En 1948, dans A Mathematical Theory of Communication, Claude Shannon propose une définition, en tire un théorème sur le codage de source (notre chapitre 7) et un théorème sur le codage de canal (notre chapitre 8), et fonde d'un seul geste une discipline entière.

Le point de départ est un renversement. Notre intuition associe l'information au sens: «la Terre tourne autour du Soleil» nous paraît porter plus d'information que «ojrvkq zlmpt». Shannon écarte délibérément cette intuition. Pour lui, une source d'information est un mécanisme aléatoire qui produit des symboles, et l'information d'un message se mesure à ce que ce message lève d'incertitude sur ce que la source allait produire. Une phrase n'est pas informative parce qu'elle est vraie, belle ou utile: elle est informative parce qu'elle était improbable.

Pourquoi la probabilité et non le sens

Trois arguments justifient ce choix, et il vaut la peine de les distinguer.

Le premier est opératoire. L'ingénieur qui conçoit une ligne, un disque ou un format de fichier ne connaît pas le sens des messages qu'il transportera; il ne connaît que leurs statistiques. Un standard de compression d'images ne sait rien des visages ni des paysages, mais il sait qu'un pixel ressemble à son voisin. Une théorie utilisable doit donc se contenter de ce que l'ingénieur possède: des probabilités.

Le deuxième est mathématique. Le sens n'a pas, à ce jour, de mesure quantitative sur laquelle on puisse démontrer des théorèmes. La probabilité, si. Shannon ne prétend pas que le sens n'existe pas; il constate que son problème — transmettre exactement une suite de symboles — ne le requiert pas. Sa phrase, en 1948, est explicite: les aspects sémantiques de la communication sont sans rapport avec le problème d'ingénierie.

Le troisième est empirique, et c'est le plus fort: la théorie fonctionne. Les bornes qu'elle établit sont atteintes en pratique, à quelques pourcents près, par les algorithmes du chapitre 7; les codes correcteurs du chapitre 8 s'approchent de la capacité qu'elle prédit. Une théorie qui ignore le sens et qui prédit correctement la taille des fichiers a gagné le droit d'ignorer le sens.

Ce que ce choix coûte, honnêtement

Écarter le sens n'est pas gratuit. La théorie de Shannon ne distingue pas un roman d'un fichier de bruit de même statistique: si les deux ont les mêmes fréquences de caractères, ils ont la même entropie d'ordre 0, et pourtant l'un se lit et l'autre pas. Elle ne dit rien de la valeur d'un message, ni de sa vérité, ni de son utilité pour celui qui le reçoit. Elle ne mesure pas non plus la complexité intrinsèque d'un objet individuel: la suite des mille premières décimales de $π$ a une entropie d'ordre 0 quasi maximale alors qu'un programme de quelques lignes la reproduit — c'est la complexité de Kolmogorov qui capture cela, et elle n'est pas calculable (chapitre 5). Retenez donc que l'entropie répond à une question précise — combien de bits pour transmettre sans erreur une source de statistique connue — et à aucune autre.

La quantité d'information d'un événement

Trois exigences

Commençons par un événement unique. Un capteur vient de signaler quelque chose; l'événement observé avait la probabilité $p$ . Quelle quantité d'information $I (p)$ lui attribuer? Plutôt que de deviner une formule, imposons trois exigences raisonnables et regardons ce qu'elles laissent subsister.

$I$ ne dépend que de $p$ . Deux événements de même probabilité apportent la même information, quel que soit leur contenu. C'est exactement le renoncement au sens décrit plus haut.
$I$ est décroissante et continue. Un événement plus improbable est plus informatif; un événement certain ( $p = 1$ ) n'apprend rien, donc $I (1) = 0$ . Une petite variation de probabilité ne doit pas produire un saut d'information.
$I$ est additive sur des événements indépendants. Si $A$ et $B$ sont indépendants, apprendre « et » doit coûter autant qu'apprendre puis apprendre . Comme , cela s'écrit

I (pq) = I (p) + I (q) pour tous p, q \in] 0, 1] . (6.1)

L'exigence 3 est la plus contraignante, et c'est elle qui fait apparaître le logarithme. Elle est aussi la plus naturelle: si vous recevez le résultat de deux lancers de pièce indépendants, vous voulez que l'information reçue soit le double de celle d'un lancer.

Démonstration. Posons $f (x) = I (e^{- x})$ pour $x \geq 0$ . La fonction $f$ est continue, croissante (car $x \mapsto e^{- x}$ décroît et $I$ décroît), et . La relation (6.1) devient, avec et ,

f (x + y) = f (x) + f (y) pour tous x, y \geq 0.

C'est l'équation fonctionnelle de Cauchy. Par récurrence, $f (n x) = n f (x)$ pour tout entier $n \geq 1$ ; en appliquant cela à $x = m / n$ on obtient $n f (m / n) = f (m) = m f (1)$ , donc pour tout rationnel positif . Les rationnels sont denses dans et est continue, donc pour tout , avec . En revenant à : . La constante est strictement positive, sinon serait identiquement nulle et l'exigence de décroissance stricte tomberait.

La démonstration montre bien d'où vient le logarithme: il est la seule façon continue de transformer un produit de probabilités en une somme d'informations. Ce n'est pas un choix de commodité, c'est une conséquence.

Le choix de la base 2

Reste à fixer $C$ , c'est-à-dire l'unité. La convention de Shannon est de donner un à l'événement le plus simple qui ne soit pas certain: le résultat d'un tirage équiprobable entre deux possibilités. On impose donc $I (1/2) = 1$ , ce qui donne $C = 1$ en base 2 et

I (p) = - lo g_{2} p = lo g_{2} \frac{1}{p} bits . (6.2)

Le mot «bit» porte ici deux sens qu'il faut tenir séparés, et le cours les distinguera systématiquement: le bit physique, qui est une case mémoire valant $0$ ou $1$ , et le bit d'information, qui est une unité de mesure comme le mètre ou le joule et qui peut parfaitement valoir $2, 0404$ . Un symbole d'ABRACADABRA occupe 3 bits physiques dans un codage à longueur fixe mais ne porte que 2,0404 bits d'information: tout le chapitre 7 vit dans cet écart.

D'autres bases sont en usage: la base $e$ donne le nat ( $1$ nat $= 1/ ln 2 \approx 1, 4427$ bits), commode en analyse parce que la dérivée de $ln$ est simple; la base 10 donne le dit ou hartley. Dans tout ce cours, la base est 2 et elle est écrite explicitement: $lo g_{2}$ .

Exemple 6.1 · Quelques surprises chiffrées

Toutes les valeurs ci-dessous sont calculées, arrondies à quatre décimales.

Événement	Probabilité $p$	$I (p) = - lo g_{2} p$
Une pièce équilibrée tombe sur face	$1/2$	1 bit
Deux pièces tombent sur face	$1/4$

Question 6.1

Un tirage donne un événement de probabilité $1/8$ . Quelle est sa quantité d'information?

L'entropie de Shannon

Une source ne produit pas un événement isolé: elle produit des symboles, encore et encore. Ce qui intéresse l'ingénieur est le coût moyen par symbole, donc l'espérance de la quantité d'information.

Trois remarques sur cette définition, chacune importante.

L'unité. $H$ s'exprime en bits par symbole. Multipliée par le nombre de symboles d'un message, elle donne un nombre de bits. Si la source émet à $1000$ symboles par seconde, $1000 H$ est un débit en bits par seconde. Ne confondez jamais l'entropie d'une source (par symbole) avec l'information totale d'un message (le produit des deux).

La convention $0 lo g_{2} 0 = 0$ . Elle n'est pas arbitraire: c'est la seule valeur qui rende la fonction $x \mapsto x lo g_{2} x$ continue en $0$ . En effet, en posant $x = 2^{- t}$ ,

x \to 0^{+} lim x lo g_{2} x = t \to + \infty lim - t 2^{- t} = 0,

car l'exponentielle l'emporte sur toute puissance. La lecture est limpide: un symbole qui n'arrive jamais a une surprise infinie, mais il contribue à l'entropie avec un poids nul, et le produit $0 \times \infty$ se tranche par la limite, qui vaut zéro. Conséquence pratique: ajouter à un alphabet des symboles de probabilité nulle ne change pas l'entropie. C'est indispensable pour comparer deux sources sur des alphabets de tailles différentes.

Le signe. Chaque $p_{i}$ est dans $[0, 1]$ , donc $lo g_{2} p_{i} \leq 0$ , donc chaque terme $- p_{i} lo g_{2} p_{i}$ est positif ou nul: toujours. L'entropie est une moyenne de surprises, et les surprises sont positives.

Exemple 6.2 · L'entropie de six sources, toutes calculées

Chaque ligne a été recalculée; la somme des probabilités vaut $1$ dans chaque cas.

Source	Distribution	$H$ (bits/symbole)
Pièce équilibrée	$(1/2, 1/2)$	1,0000
Pièce biaisée	$(0, 9; 0, 1)$	0,4690
Pièce truquée à l'extrême	$(1; 0)$	0,0000

Question 6.2

Une source émet quatre symboles avec les probabilités $0, 4$ , $0, 3$ , $0, 2$ et $0, 1$ . Quelle est son entropie, en bits par symbole?

Les propriétés fondamentales de l'entropie

Toutes les propriétés qui suivent découlent d'une seule inégalité, qu'il vaut donc la peine d'isoler.

Démonstration. L'ingrédient est l'inégalité élémentaire $ln t \leq t - 1$ pour tout $t > 0$ , avec égalité si et seulement si $t = 1$ : la fonction $g (t) = t - 1 - ln t$ vérifie , donc décroît sur , croît sur et atteint son minimum .

Notons $S = {i : p_{i} > 0}$ le support de $p$ . La différence des deux membres de (6.4) s'écrit

i \in S \sum p_{i} lo g_{2} \frac{q _{i}}{p _{i}} = \frac{1}{ln 2} i \in S \sum p_{i} ln \frac{q _{i}}{p _{i}} \leq \frac{1}{ln 2} i \in S \sum p_{i} (\frac{q _{i}}{p _{i}} - 1) = \frac{1}{ln 2} (i \in S \sum q_{i} - 1) \leq 0,

puisque $\sum_{i \in S} q_{i} \leq \sum_{i} q_{i} = 1$ . L'égalité exige simultanément pour tout et , c'est-à-dire .

La quantité $\sum_{i} p_{i} lo g_{2} (p_{i} / q_{i})$ , positive d'après (6.4), s'appelle la ; elle mesure ce que l'on perd à coder une source de loi avec un code optimisé pour la loi . Le chapitre 7 en donnera l'interprétation exacte en bits gaspillés. Retenez qu'elle n'est symétrique en et , et n'est donc pas une distance.

Démonstration. Borne inférieure. Chaque terme $- p_{i} lo g_{2} p_{i}$ est positif ou nul, donc $H \geq 0$ . Une somme de termes positifs est nulle si et seulement si tous les termes le sont; or $- p lo g_{2} p = 0$ n'a lieu que pour ou . Toutes les probabilités sont donc dans , et comme elles somment à , exactement une vaut : la source est déterministe. Réciproquement, une source déterministe a bien par la convention .

Borne supérieure. Appliquons l'inégalité de Gibbs (6.4) avec la distribution uniforme $q_{i} = 1/ n$ :

H (X) \leq - i = 1 \sum n p_{i} lo g_{2} \frac{1}{n} = lo g_{2} n i = 1 \sum n p_{i} = lo g_{2} n .

Le cas d'égalité de (6.4) donne immédiatement $p_{i} = 1/ n$ pour tout $i$ . $□$

La lecture de (6.5) est celle qu'il faut garder: l'incertitude est maximale quand rien ne permet de parier, et nulle quand tout est prévisible. Entre les deux, $lo g_{2} n$ borne ce que l'on peut espérer: une source sur cinq symboles ne dépassera jamais $lo g_{2} 5 = 2, 3219$ bits par symbole, quelles que soient ses probabilités.

Regrouper ou scinder des symboles

Que devient l'entropie quand on cesse de distinguer deux symboles, par exemple parce qu'un capteur ne sait plus les séparer? La réponse est exacte et très utile.

Démonstration. Seuls les deux premiers termes diffèrent. Écrivons $p_{1} = p α$ et $p_{2} = p (1 - α)$ avec $α = p_{1} / p$ . Alors

- p_{1} lo g_{2} p_{1} - p_{2} lo g_{2} p_{2} = - p α lo g_{2} (p α) - p (1 - α) lo g_{2} (p (1 - α)) .

En développant $lo g_{2} (p α) = lo g_{2} p + lo g_{2} α$ et de même pour l'autre terme, la partie en $lo g_{2} p$ se regroupe en (puisque ) et la partie restante vaut .

Deux conséquences immédiates. Fusionner deux symboles fait toujours baisser l'entropie (le terme ajouté est positif): perdre la capacité de distinguer, c'est perdre de l'information. Et scinder un symbole en deux fait toujours monter l'entropie, d'une quantité qui vaut au plus $p$ bit (le maximum de l'entropie binaire est $1$ ), atteinte quand la scission est équitable.

Question 6.3

Classez ces quatre sources de la plus petite à la plus grande entropie.

Glissez les éléments pour les mettre dans le bon ordre

une source à quatre symboles de probabilités

(0, 97; 0, 01; 0, 01; 0, 01)

un dé équilibré à six faces

une source binaire équiprobable

une source à deux symboles de probabilités

(0, 99; 0, 01)

Explorateur 6.1 · Explorateur d'entropie d'une source à quatre symboles

Les quatre curseurs fixent des poids relatifs; ils sont renormalisés pour que les probabilités somment toujours à 1. L'entropie H est recalculée à chaque mouvement, ainsi que la redondance 1 − H/log₂4. Rendez les quatre poids égaux: H atteint son maximum log₂ 4 = 2 bits/symbole et la redondance s'annule. Mettez au contraire tout le poids sur un seul symbole: H tombe à 0 et la redondance vaut 1.

Poids du symbole a4,0

Poids du symbole b3,0

Poids du symbole c2,0

Poids du symbole d1,0

Entropie H

1,8464bits/symbole

Maximum log₂ 4

2,0000bits/symbole

Redondance 1 − H/log₂ 4

0,0768

État

non équiprobable

Prenez le temps de manipuler l'explorateur de la figure 6.1, car il rend visibles les deux théorèmes qui précèdent. Amenez les quatre curseurs à la même valeur: la jauge se remplit exactement jusqu'à $2$ et la redondance tombe à $0$ — c'est le cas d'égalité du théorème 6.3. Poussez au contraire tout le poids sur un seul symbole: $H$ tombe à $0$ et la redondance vaut $1$ . Essayez enfin de faire monter $H$ au-dessus de $2$ : c'est impossible, la borne tient. Une dernière expérience, plus subtile: partez de $(4; 3; 2; 1)$ , notez $H = 1, 8464$ , puis transférez du poids du symbole vers le symbole . L'entropie tant que la distribution s'égalise et redescend dès qu'on la déséquilibre dans l'autre sens.

L'entropie binaire

Le cas de deux symboles mérite un traitement séparé: il apparaît dans tous les problèmes de canal du chapitre 8, et sa courbe est l'une des plus utiles du cours.

Quatre propriétés se lisent sur la figure 6.2 et se démontrent en deux lignes.

Symétrie. $H (p) = H (1 - p)$ : la définition est symétrique en échangeant les deux symboles. Rien ne distingue «pile avec probabilité $0, 9$ » de «face avec probabilité $0, 1$ ».

Maximum. Par le théorème 6.3 avec $n = 2$ , $H (p) \leq lo g_{2} 2 = 1$ avec égalité si et seulement si $p = 1/2$ . C'est le point le plus haut de la courbe.

Concavité. En dérivant (6.7),

H^{'} (p) = lo g_{2} \frac{1 - p}{p}, H^{''} (p) = - \frac{1}{p ( 1 - p ) ln 2} < 0 sur] 0, 1 [,

donc $H$ est strictement concave: la courbe est en cloche, sans plateau ni point d'inflexion. La dérivée s'annule en $p = 1/2$ , ce qui redonne le maximum.

Pente infinie aux bords. $H^{'} (p) \to + \infty$ quand $p \to 0^{+}$ et $H^{'} (p) \to - \infty$ quand $p \to 1^{-}$ . La courbe quitte à la verticale. La conséquence est contre-intuitive et importante: . Un canal qui se trompe une fois sur cent a une entropie d'erreur bit par bit transmis — huit fois plus que la probabilité d'erreur elle-même. Quelques valeurs, toutes calculées:

$p$	0,001	0,01	0,05	0,10	0,11	0,25	0,50
$H (p)$	0,0114	0,0808	0,2864	0,4690	0,4999	0,8113	1,0000

Retenez le repère $H (0, 11) \approx 0, 5$ : il faut déjà onze pour cent d'erreurs pour détruire la moitié d'un bit. Cette lenteur est ce qui rend possibles les codes correcteurs du chapitre 8.

Entropie conjointe, entropie conditionnelle, information mutuelle

Jusqu'ici une seule source. Mais toute la communication met en jeu deux variables: ce qui a été émis et ce qui a été reçu, l'état d'un système et la mesure qu'on en fait, le passé d'un texte et sa lettre suivante. Il faut donc mesurer ce que l'une dit de l'autre.

Attention à la dissymétrie de la notation: $H (X ∣ Y)$ est bien un nombre unique, pas une fonction de $y$ . C'est l'incertitude qui reste sur $X$ une fois $Y$ connu, en moyenne sur les valeurs possibles de $Y$ . Et $H (X ∣ Y) \neq = H (Y ∣ X)$ en général: savoir la date de naissance de quelqu'un vous dit son âge, l'inverse est faux.

Démonstration. Partons de la définition de $H (X, Y)$ et utilisons $p (x, y) = p (x) p (y ∣ x)$ , donc $lo g_{2} p (x, y) = lo g_{2} p (x) + lo g_{2} p (y ∣ x)$ (les termes où ne contribuent pas, par la convention ):

H (X, Y) = - x, y \sum p (x, y) lo g_{2} p (x) - x, y \sum p (x, y) lo g_{2} p (y ∣ x) .

Dans la première somme, $\sum_{y} p (x, y) = p (x)$ , donc elle vaut $- \sum_{x} p (x) lo g_{2} p (x) = H (X)$ . La seconde est exactement par (6.8). La seconde égalité de (6.9) s'obtient en échangeant les rôles de et de .

La lecture est celle du bon sens: décrire le couple coûte le prix de $X$ , plus ce qu'il reste à dire de $Y$ une fois $X$ connu. Et l'on peut commencer par l'un ou par l'autre, le total est le même.

Démonstration. En développant (6.10) avec les définitions,

I (X; Y) = x, y \sum p (x, y) lo g_{2} \frac{p ( x , y )}{p ( x ) p ( y )} = D (p (x, y) ∥ p (x) p (y)) .

C'est la divergence de la loi conjointe par rapport au produit des marginales: appliquons l'inégalité de Gibbs (6.4) sur l'alphabet des couples $(x, y)$ , avec $p_{i} = p (x, y)$ et $q_{i} = p (x) p (y)$ — ce dernier est bien une loi de probabilité, car . Le théorème 6.2 donne et l'égalité si et seulement si pour tout couple, c'est-à-dire l'indépendance.

Une table conjointe entièrement travaillée

Le modèle qui servira de fil au chapitre 8: une station émet un bit $X$ , le canal binaire symétrique le retourne avec la probabilité $p = 0, 10$ indépendamment de la valeur émise, et $Y$ est le bit reçu. La source n'est pas équiprobable: $P (X = 0) = 0, 30$ et $P (X = 1) = 0, 70$ (c'est un capteur qui signale une anomalie trois fois sur dix). La loi conjointe s'obtient par .

$p (x, y)$	$Y = 0$	$Y = 1$	marge $p (x)$
$X = 0$	0,27	0,03	0,30
$X = 1$

Contrôle des marges. $0, 27 + 0, 03 = 0, 30$ et $0, 07 + 0, 63 = 0, 70$ : les lignes redonnent bien la loi de $X$ . $0, 27 + 0, 07 = 0, 34$ et : les colonnes redonnent bien la loi de . Le total des quatre cases vaut . Ce contrôle n'est pas une formalité: une table conjointe dont les marges ne se recollent pas rend faux tout ce qui suit.

Le diagramme de la figure 6.3 est un aide-mémoire remarquablement fidèle: chaque identité du chapitre s'y lit comme une addition d'aires.

$H (X) = H (X ∣ Y) + I (X; Y)$ , soit $0, 4255 + 0, 4558 = 0, 8813$ : le disque de gauche est la somme de son croissant et de la lentille.
$H (Y) = H (Y ∣ X) + I (X; Y)$ , soit .

Question 6.4

Dans la table conjointe de l'exemple 6.4, supposons que le récepteur observe $Y = 1$ . Quelle entropie conditionnelle $H (X ∣ Y = 1)$ reste-t-il sur le bit émis, en bits?

La redondance d'une source

Nous disposons maintenant des deux nombres qu'il faut comparer: ce qu'une source coûte au maximum, et ce qu'elle porte réellement.

Lorsqu'un codage à longueur fixe est déjà imposé, avec $ℓ$ bits par symbole, on compare plutôt à $ℓ$ : la redondance du codage est $1 - H (X) / ℓ$ . Les deux notions se confondent quand $n$ est une puissance de 2 et que le codage est optimal en longueur fixe; elles diffèrent sinon, et il faut dire laquelle on utilise. Nous le ferons chaque fois.

La redondance est le concept qui articule toute la seconde moitié du cours, et il vaut la peine de l'écrire en toutes lettres:

le chapitre 7 (compression) supprime la redondance. Un texte français a une redondance élevée: certaines lettres sont fréquentes, certaines suites sont impossibles. Coder chaque lettre sur le même nombre de bits gaspille cette structure. Huffman, le codage arithmétique et Lempel-Ziv la récupèrent, et le théorème du codage de source dira exactement jusqu'où: pas en dessous de $H$ ;
le chapitre 8 (codes correcteurs) réintroduit de la redondance, délibérément. Un code de Hamming $(7, 4)$ ajoute trois bits de parité à quatre bits utiles: sa redondance est de $3/7$ , et c'est elle qui permet de localiser une erreur. Rien n'est gratuit — le canal doit transporter $7$ bits pour $4$ bits utiles;
entre les deux, la même grandeur change de signe pédagogique: ce que la compression tient pour du gaspillage, la correction d'erreurs le paie volontairement. La chaîne complète d'une transmission moderne comprime d'abord puis recode ensuite, et ce n'est pas absurde: la redondance retirée était celle du langage, non maîtrisée; celle qui est ajoutée est construite pour que le décodeur sache exactement quoi en faire.

Question 6.5

Une source de quatre symboles a pour probabilités $(1/2, 1/4, 1/8, 1/8)$ . Quelle est sa redondance relative?

La source du cours: ABRACADABRA

Le fil rouge des chapitres 6 et 7 est le message ABRACADABRA, onze symboles sur l'alphabet ${A, B, C, D, R}$ . Comptons: A apparaît cinq fois (positions 1, 4, 6, 8, 11), B deux fois, R deux fois, C une fois, D une fois. Total $5 + 2 + 2 + 1 + 1 = 11$ : le compte est bon.

Nous adoptons le modèle d'ordre 0: la source est supposée émettre chaque symbole indépendamment des précédents, avec les probabilités égales aux fréquences observées. C'est une hypothèse, et la section suivante montrera à quel point elle est fausse pour ce message précis; elle est néanmoins le point de départ de tout codeur simple.

Symbole	Occurrences	$p$	$- lo g_{2} p$ (bits)	$p \times (- lo g_{2} p)$
A	5	$5/11 = 0, 4545$

La colonne des probabilités somme à $1$ exactement ( $5 + 2 + 2 + 1 + 1 = 11$ sur $11$ ), et la dernière colonne donne l'entropie:

H = - \frac{5}{11} lo g_{2} \frac{5}{11} - 2 \cdot \frac{2}{11} lo g_{2} \frac{2}{11} - 2 \cdot \frac{1}{11} lo g_{2} \frac{1}{11} = 2, 0404 bits/symbole . (6.12)

La figure 6.4 rend visible le compromis de l'entropie. Le A est large et bas: fréquent, donc peu surprenant, mais sa fréquence lui donne quand même la plus grosse aire ( $0, 5170$ bit de contribution). Les C et D sont étroits et hauts: chacun vaut $3, 4594$ bits de surprise, mais ils n'arrivent qu'une fois sur onze et ne contribuent que $0, 3145$ bit chacun. La ligne horizontale à $2, 0404$ est la hauteur moyenne pondérée: c'est exactement l'entropie, et l'aire totale sous les barres vaut $H$ .

Ce que l'entropie n'est pas

Il vaut la peine de fermer explicitement quatre portes, parce que chacune a été franchie par erreur dans des textes sérieux.

L'entropie n'est pas une mesure de sens. «Le chat dort» et «Lej lhbu qsvy» peuvent avoir la même entropie d'ordre 0. La théorie mesure l'imprévisibilité de la source, pas l'intelligibilité du message. Un générateur de caractères aléatoires produit l'entropie maximale et ne dit rien.

L'entropie n'est pas une mesure de valeur ni d'utilité. Le message «votre vol est annulé» a une valeur considérable pour vous et une entropie dérisoire s'il était probable. Inversement, le résultat d'un tirage au sort auquel vous ne participez pas a une entropie maximale et une utilité nulle. Toute phrase qui traite l'entropie comme une richesse est une confusion.

L'entropie n'est pas une mesure de vérité. Une affirmation fausse et une affirmation vraie de même probabilité a priori portent la même quantité d'information. La théorie suppose le canal fidèle à une source; elle ne certifie pas la source.

L'entropie n'est pas la complexité d'un objet individuel. Les mille premières décimales de $π$ ont une entropie d'ordre 0 proche de $lo g_{2} 10 = 3, 3219$ bits par chiffre, mais un programme de quelques lignes les engendre. La grandeur qui capture cela est la complexité de Kolmogorov, la longueur du plus court programme produisant l'objet — et le chapitre 5 nous a appris qu'elle n'est pas calculable, par un argument voisin de celui du problème de l'arrêt. L'entropie de Shannon est calculable parce qu'elle est une propriété de la loi, pas de l'objet.

Et la thermodynamique?

La formule de Shannon a la même forme que l'entropie statistique de Boltzmann et Gibbs, $S = - k_{B} \sum_{i} p_{i} ln p_{i}$ , à la constante et à la base du logarithme près. Que faut-il en penser?

Il faut le dire aussi précisément que possible, parce que ce point est le lieu de beaucoup de littérature vague. Ce n'est pas une simple métaphore: la parenté est mathématique et réelle. Les deux grandeurs mesurent la même chose formelle — le logarithme du nombre d'états compatibles avec ce que l'on sait — et la mécanique statistique est, lue ainsi, un exercice d'inférence sur des états microscopiques. Le lien a aussi une conséquence physique mesurable: le principe de Landauer affirme qu'effacer irréversiblement un bit d'information dissipe au moins $k_{B} T ln 2$ joules, soit environ $3 \cdot 1 0^{- 21}$ J à température ambiante — une quantité minuscule, très inférieure à ce que consomme un transistor réel, mais non nulle et expérimentalement approchée depuis les années 2010 par plusieurs équipes.

Mais ce n'est pas une identité non plus. L'entropie de Shannon se mesure en bits et porte sur une loi de probabilité choisie par le modélisateur; l'entropie thermodynamique se mesure en joules par kelvin et porte sur l'état macroscopique d'un système physique. La première change si vous changez de modèle; la seconde est une fonction d'état. Confondre les deux conduit à des énoncés qui sonnent profonds et ne prédisent rien. La formulation honnête: une analogie formelle avec une parenté mathématique réelle et une conséquence physique vérifiée, mais deux grandeurs distinctes. Nous nous en tiendrons là; ce cours n'a pas besoin de plus.

Synthèse

La quantité d'information d'un événement de probabilité $p$ vaut $- lo g_{2} p$ bits. Le logarithme n'est pas un choix de commodité: c'est la seule fonction continue et décroissante qui rende l'information additive sur des événements indépendants, et la base 2 fixe l'unité en donnant $1$ bit au tirage équiprobable entre deux possibilités.
L'entropie $H (X) = - \sum_{i} p_{i} lo g_{2} p_{i}$ est l'information moyenne par symbole, en bits/symbole, avec la convention qui est la seule limite continue. Elle vérifie , la borne basse caractérisant les sources déterministes et la borne haute les sources équiprobables; les deux se déduisent de l'inégalité de Gibbs.

Série d'exercices du chapitre 6Exercice 1 sur 5

Question 6.6

Laquelle de ces affirmations sur l'entropie est vraie?

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

Exercice 6.1 · Quatre entropies et leurs redondances

Calculez l'entropie, en bits par symbole, de chacune des sources suivantes, puis sa redondance relative par rapport à $lo g_{2} n$ .

$(1/2, 1/4, 1/4)$ ;
$(0, 4; 0, 3; 0, 2; 0, 1)$ ;

Exercice 6.2 · La fonction d'entropie binaire

Démontrez que $H (p) = H (1 - p)$ pour tout $p \in [0, 1]$ .
Calculez $H^{'} (p)$ et sur ; déduisez-en la concavité et la position du maximum.

Exercice 6.3 · Une table conjointe complète

Une station météo enregistre chaque soir l'état du ciel $Y$ (couvert ou dégagé) et note le lendemain s'il a plu, variable $X$ (pluie ou sec). Sur un long historique, la loi conjointe est estimée à:

$p (x, y)$	couvert	dégagé
pluie	0,35	0,05
sec	0,10	0,50

Calculez les deux lois marginales et vérifiez que le total vaut $1$ .
Calculez $H (X)$ , $H (Y)$ et .

Exercice 6.4 · Le plancher d'ABRACADABRA, et ce qui le déplace

Recalculez $H$ pour la source ABRACADABRA et retrouvez $22, 44$ bits pour les onze symboles.
Un codage à longueur fixe coûte $33$ bits. Quelle est la redondance de ce codage? Quelle est celle de la source par rapport à $lo g_{2} 5$ ?
On ajoute au message un douzième symbole E, de fréquence $0$ . L'entropie change-t-elle? Justifiez par la convention et par l'intuition.
On modifie le message pour qu'il compte six A au lieu de cinq, en remplaçant le D par un A (le message devient ABRACAAABRA, toujours onze symboles). Recalculez et commentez le sens de la variation.

Exercice 6.5 · Positivité, indépendance et une fausse évidence

Démontrez que $H (X ∣ Y) \leq H (X)$ , avec égalité si et seulement si $X$ et $Y$ sont indépendantes.
Démontrez que $H (X, Y) \geq max (H (X), H (Y))$ et interprétez.

Références

Shannon, C. E., A Mathematical Theory of Communication, Bell System Technical Journal, vol. 27, 1948 — l'article fondateur; les sections 1 à 7 sont lisibles avec ce chapitre en main.
Cover, T. M. et Thomas, J. A., Elements of Information Theory, 2e éd., Wiley, Hoboken, chap. 2 (entropie, entropie relative et information mutuelle).
MacKay, D. J. C., Information Theory, Inference and Learning Algorithms, Cambridge University Press, chap. 2 et 4 (librement disponible en ligne).
Abelson, H., Ledeen, K. et Lewis, H., Blown to Bits, Addison-Wesley, Boston, chap. 3 (ce que les bits n'expriment pas).
Landauer, R., Irreversibility and Heat Generation in the Computing Process, IBM Journal of Research and Development, vol. 5, 1961 — pour le lien avec la thermodynamique.
Polycopiés du cours ICC de l'EPFL, partie «Information et codage».

Objectifs du chapitre

La question que Shannon a posée

Pourquoi la probabilité et non le sens

La quantité d'information d'un événement

Trois exigences

Le choix de la base 2

L'entropie de Shannon

Les propriétés fondamentales de l'entropie

Regrouper ou scinder des symboles

L'entropie binaire

Entropie conjointe, entropie conditionnelle, information mutuelle

Une table conjointe entièrement travaillée

La redondance d'une source

La source du cours: ABRACADABRA

Ce que l'entropie n'est pas

Et la thermodynamique?

Synthèse

Exercices

Références

L'entropie de la source

La redondance

Le plancher pour une heure d'enregistrement

Le capteur redevient bavard