7.
Introduction à la théorie de l'information
Dans ce chapitre, nous étudions les limites fondamentales de la représentation et de la
transmission d'information. C’est-à-dire, nous essayons de déterminer les limites de la
communication.
7.1 Montant d’information et entropie d’une source
Supposons qu’il y a une source d’information X qui produit un message m(n) durant la nième
instant de signalisation. Le message m(n) vient d’un ensemble de messages possibles {m1, m2, …,
mN} où la probabilité que m(n) est mi est p(mi).
Une source d’information où les probabilités p(mi) sont indépendantes de n est une source
sans-mémoire. Une source avec mémoire est une source où l’émission de messages pendant
le nième intervalle de signalisation dépend des messages qui ont été émis dans les instants
de signalisation précédant.
Nous souhaitons mesurer la quantité d'information contenue dans un message. Si l’ensemble des
messages ne contient qu’un message, c’est clair que le message ne contient pas d’information
(car on sait avec certitude le message qui sera émis à chaque instant de signalisation). Si
l’ensemble des messages contient deux messages où un des messages est très probable et l’autre
est émis rarement, le message rare contient plus d’information que le message probable. Donc le
montant d’information dans le message mi, I(mi), est inversement proportionnel à la probabilité
du message.
Pour une source sans-mémoire la probabilité que m(n) = mi et m(n+1) = mj est p(mi)p(mj). Mais
l’information dans le message mi suivi par mj est I(mi)+I(mj). Donc
( ) ( ) ( ( )) (7.1)
( )
On voit du (7.1) que si m(n) = mi et m(n+1) = mj que
( ) ( ( ) ( )) ( ( )) ( ( ))
( ) ( ) (7.2)
Les unités de I(mi) dépendent de la valeur de b. Si b = 2, l’information est mesurée en bits (ou
Shannons), si b = e on mesure l’information en nats, et si b=10 on mesure l’information en
Hartleys. On peut utiliser n’importe quelle valeur pour b. Par exemple si on utilise b = 3 on
mesure l’information en symboles ternaires. Normalement, si ce n’est pas indiqué autrement, on
mesure l’information en bits, donc b = 2.
Si les messages ne sont pas équiprobables, le contenu d’information de chaque message sera
différent. Le montant d’information moyenne à chaque instant de signalisation est nommé
l’entropie de la source, H(X) qui, pour une source sans-mémoire, est donnée par :
( ) ∑ ( ) ( ) (7.3)
Pour b = 2, l’entropie est mesurée en bits/message.
Exemple 7.1
À chaque instant de signalisation, une source X émet un message qui vient de l’ensemble m(n)
{m1, m2, m3, m4, m5} où la probabilité d’émission de chaque message est {0.3, 0.2, 0.24, 0.14,
0.12}. C’est quoi l’entropie de la source en bits/message? C’est quoi le montant d’information
dans le message m3?
Solution
H(X) = -0.3log2(0.3) - 0.2log2(0.2) - 0.24log2(0.24) - 0.14log2(0.14) - 0.12log2(0.12) = 2.444
bits/message.
I(m3) = -log2(p(m3)) = -log2(0.24) = 2.06 bits.
7.2 Le canal discret sans mémoire, information mutuelle et la capacité du canal
Quand on transmet un message de la source au récepteur, parfois il y a des erreurs de détection et
le récepteur obtient, par erreur, le mauvais message. On représente le canal pour un graphique
qui relie le message détecté avec le message originale par la probabilité que le message mj soit
reçu sur la condition que le message mi soit transmis. Cette probabilité conditionnelle est écrite
p(mj|mi) ou p(Y=mj|X=mi), où X indique la source et Y indique le récepteur.
Le canal est discret si ses entrées et ses sorties viennent d’un ensemble discret et de nombre fini.
Le canal est sans-mémoire si les probabilités conditionnelle p(mj|mi) sont indépendantes de
temps. La représentation du canal binaire symétrique est démontrée à la Figure 7.1.
Les probabilités p(X=0) et p(X=1) sont les probabilités que 0 et 1 sont transmis respectivement.
Les probabilités que 0 et 1 sont reçus sont p(Y=0) et p(Y=1) respectivement. Le canal est
symétrique car p(Y=1|X=0) = p(Y=0|X=1) (alors la probabilité d’erreur est indépendant du
symbole transmis). Chaque ligne dans le graphique représente la transition du symbole transmis
au symbole reçu. Chaque ligne est associée à une probabilité conditionnelle, qui indique la
probabilité que le récepteur détecte le symbole j étant donné que le symbole i a été transmis. Si
on transmet le symbole i et on reçoit également ce symbole, la transmission a réussi. Sinon, il y
a eu une erreur de détection au récepteur.
Figure 7.1 : Canal binaire symétrique.
L’entropie conditionnelle est donné par :
( | ) ∑ ∑ ( ) ( | ) (7.4)
où p(xi,yj) = p(X=xi,Y=yj) et p(xi|yj) = p(X=xi|Y=yj).
Exemple 7.2
Considérez le canal binaire symétrique de la Figure 7.1 où p(X=0) = p(X=1) = 0.5 et = 0.1.
Trouvez H(X) et H(X|Y).
Solution
H(X) = -0.5log2(0.5)-0.5log2(0.5) = 1bits/message.
De la Figure 7.1 p(Y=1|X=1) = 0.9. Cependant, on veut p(xi,yj) et p(xi|yj) pour utiliser (7.4).
Donc on doit utiliser le théorème de Bayes.
( ) ( | ) ( ) (7.5)
et
( ) ( | ) ( )
( | ) (7.6)
( ) ( )
où
( ) ∑ ( | ) ( ) (7.7)
Donc
La probabilité p(Y=0) = 0.5(1-)+0.5 = 0.5 et donc p(Y=1) = 0.5 aussi.
Donc p(X=0|Y=0) = p(X=1|Y=1) = 1- et p(X=1|Y=0) = p(X=0|Y=1) = . Les
probabilités p(X=0, Y=0) = p(X=1,Y=1) = 0.5(1-) = 0.45 et les probabilités P(X=1,Y=0) = p(X=0,
Y=1) = 0.5.
Donc H(X|Y) = -0.45log2(0.9)-0.05log2(0.1)-0.05log2(0.1)-0.45log2(0.9) = 0.469 bits/message.
Dans l’exemple 7.2 si = 0, H(X|Y) = 0. Quand e = 0, il n’y a pas d’erreurs de transmission.
Donc H(X|Y) représente l’incertitude en X en sachant Y. (c’est-à-dire, en sachant le symbole
détecté au récepteur, il y a encore une chance qu’on l’a détecté en erreur.)
Exemple 7.3
Répétez l’exemple 7.2 pour p(X=0) = 0.6 et p(X=1) = 0.4.
Solution
H(X) = -0.6log2(0.6)-0.4log2(0.4) = 0.971 bits/message
La probabilité p(Y=0) = p(Y=0|X=0)p(X=0) + p(Y=0|X=1)p(X=1) = (0.9)(0.6)+(0.4)(0.1) = 0.58.
Donc p(Y=1) = 0.42.
p(X=0,Y=0) = p(Y=0|X=0)p(X=0) = (0.9)(0.6) = 0.54.
p(X=0,Y=1) = p(Y=1|X=0)p(X=0) = (0.1)(0.6) = 0.06
p(X=1,Y=0) = p(Y=0|X=1)p(X=1) = (0.1)(0.4) = 0.04
p(X=1,Y=1) = p(Y=1|X=1)p(X=1) = (0.9)(0.4) = 0.36
p(X=0|Y=0) = p(X=0,Y=0)/p(Y=0) = 0.54/0.58 = 0.931.
p(X=1|Y=0) = p(X=1,Y=0)/p(Y=0) = 0.04/0.58 = 0.069.
p(X=0|Y=1) = p(X=0,Y=1)/p(Y=1) = 0.06/0.42 = 0.143.
p(X=1|Y=1) = p(X=1,Y=1)/p(Y=1) = 0.36/0.42 = 0.857.
Donc H(X|Y) = -0.54log2(0.931)-0.06log2(0.143)-0.04log2(0.069)-0.36log2(0.857) = 0.458
bits/message.
L’information mutuelle I(X;Y) est l’information moyenne par message moins l’incertitude, donc
( ) ( ) ( | ) (7.8)
Donc
( | )
( ) ∑ ∑ ( ) (7.9)
( )
Et on peut simplifier (7.9) car p(xi|yj) = p(xi,yj)/p(yj). Donc (7.9) devient
( )
( ) ∑ ∑ ( ) (7.10)
( ) ( )
Exemple 7.3
Trouvez l’information mutuelle pour les exemples 7.1 et 7.2
Solution
Ici on peut utiliser (7.8) donc
Pour l’exemple 7.1, I(X;Y) = 1-0.469 = 0.531 bits/message
Pour l’exemple 7.2, I(X;Y) = 0.971-0.458 = 0.513 bits/message
Exemple 7.4
Considérez le canal de la Figure 7.2. Trouvez l’information mutuelle si p(X=0) = p(X=1) =
p(X=2) = 1/3. Répétez pour p(X=0) = p(X=1) = 0.25 et p(X=2) = 0.5. Ensuite trouvez l’entropie
pour les deux cas ainsi que l’incertitude.
Solution
Ici on utilise (7.10). Pour le cas où les entrées sont équiprobables, on calcul les probabilités de
deux variables, p(xi,yj) ci-dessous :
p(X=0,Y=0) = p(Y=0|X=0)p(X=0) = (0.9)(1/3) = 0.3
p(X=0,Y=1) = p(Y=1|X=0)p(X=0) = (0.08)(1/3) = 0.0267
p(X=0,Y=2) = p(Y=2|X=0)p(X=0) = (0.02)(1/3) = 0.0067
p(X=1,Y=0) = p(Y=0|X=1)p(X=1) = (0.05)(1/3) = 0.0167
p(X=1,Y=1) = p(Y=1|X=1)p(X=1) = (0.9)(1/3) = 0.3
p(X=1,Y=2) = p(Y=2|X=1)p(X=1) = (0.05)(1/3) = 0.0167
p(X=2,Y=0) = p(Y=0|X=0)p(X=2) = (0.02)(1/3) = 0.067
p(X=2,Y=1) = p(Y=1|X=0)p(X=2) = (0.08)(1/3) = 0.0267
p(X=2,Y=2) = p(Y=2|X=0)p(X=2) = (0.9)(1/3) = 0.3
Aussi p(Y=0) = p(X=0,Y=0)+p(X=1,Y=0)+ p(X=2,Y=0) = 1/3
p(Y=1) = p(X=0,Y=1)+p(X=1,Y=1)+ p(X=2,Y=1) = 1/3
et p(Y=2) = p(X=0,Y=2)+p(X=1,Y=2)+ p(X=2,Y=2) = 1/3
Figure 7.2 : Canal discret de l’exemple 7.2
Donc I(X;Y) = 0.3log2(0.3/(1/9)) + 0.0267log2(0.0267/(1/9)) + 0.0067log2(0.0067/(1/9)) +
0.167log2(0.167/(1/9)) + 0.3log2(0.3/(1/9)) + 0.167log2(0.167/(1/9)) + 0.0067log2(0.0067/(1/9))
+ 0.0267log2(0.0267/(1/9)) + 0.3log2(0.3/(1/9)) = 1.322 bits.
Dans le deuxième cas où p(X=0) = p(X=1) = 0.25 et p(X=3) = 0.5,
p(X=0,Y=0) = p(Y=0|X=0)p(X=0) = (0.9)(0.25) = 0.225
p(X=0,Y=1) = p(Y=1|X=0)p(X=0) = (0.08)(0.25) = 0.02
p(X=0,Y=2) = p(Y=2|X=0)p(X=0) = (0.02)(0.25) = 0.005
p(X=1,Y=0) = p(Y=0|X=1)p(X=1) = (0.05)(0.25) = 0.0125
p(X=1,Y=1) = p(Y=1|X=1)p(X=1) = (0.9)(0.25) = 0.225
p(X=1,Y=2) = p(Y=2|X=1)p(X=1) = (0.05)(0.25) = 0.0125
p(X=2,Y=0) = p(Y=0|X=0)p(X=2) = (0.02)(0.5) = 0.01
p(X=2,Y=1) = p(Y=1|X=0)p(X=2) = (0.08)(0.5) = 0.04
p(X=2,Y=2) = p(Y=2|X=0)p(X=2) = (0.9)(0.5) = 0.45
Aussi p(Y=0) = p(X=0,Y=0)+p(X=1,Y=0)+ p(X=2,Y=0) = 0.25
p(Y=1) = p(X=0,Y=1)+p(X=1,Y=1)+ p(X=2,Y=1) = 0.25
et p(Y=2) = p(X=0,Y=2)+p(X=1,Y=2)+ p(X=2,Y=2) = 0.5
Donc I(X;Y) = 0.984 bits.
Dans le premier cas, H(X) =-3×(1/3)log2(1/3) = 1.585 bits donc H(X|Y) = 1.585-1.322 = 0.263
bits.
Dans le deuxième cas H(X) = -2×(0.25)log2(0.25)-0.5log2(0.5) = 1.5 bits. Donc H(X|Y) = 1.5-
0.984 = 0.516 bits.
On voit de l’exemple 7.3 que pour le même canal, si on change les probabilités d’émissions des
messages, on change l’information mutuelle du canal. Alors, la capacité du canal, C, est la
valeur maximum de l’information mutuelle pour ce canal. Alors il faut trouver cette valeur
maximum en variant les valeurs de probabilités de transmission. Alors
( ) ( ) (7.11)
Si le canal est symétrique, l’information mutuelle est maximisée quand les messages sont
équiprobables. Un canal est symétrique si p(yi|xj) = p(yj|xi). La plupart des canaux sont
symétrique.
Exemple 7.4
Trouvez la capacité du canal binaire symétrique de la Figure 7.1 pour = 0.2, 0.05 et 0.01.
Solution
On doit trouver I(X;Y) où p(X=0) = p(Y=0) = 0.5.
p(X=0,Y=0) = p(Y=0|X=0)p(X=0) = 0.5(1-)
p(X=0,Y=1) = p(Y=1|X=0)p(X=0) = 0.5
p(X=1,Y=0) = p(Y=0|X=1)p(X=1) = 0.5
p(X=1,Y=1) = p(Y=1|X=1)p(X=1) = 0.5(1-)
et p(Y=0) = p(Y=1) = 0.5. Donc en utilisant (7.10), l’expression pour la capacité du canal binaire
symétrique est
( ) ( ) (7.12)
Donc pour = 0.2, C = 0.278 bits, = 0.05, C = 0.713 bits, = 0.01, C = 0.919 bits. Ceci
démontre que quand la probabilité d’erreur de détection diminue, la capacité et donc
l’information mutuelle augmente (car la transmission est plus fiable et il y a moins d’incertitude).
7.3 Encodage de Source (Codage Huffmann)
Supposons qu’il y a une source d’information X qui produit un message m(n) durant la nième
instant de signalisation. Le message m(n) vient d’un ensemble de messages possibles {m1, m2, …,
mN} où la probabilité que m(n) est mi est p(mi). L’entropie de la source est H(X) donné par (7.3).
L’objet est de trouver une façon d’encoder les messages par des mots binaire qui minimise le
taux de bits, Rb, à la sortie de l’encodeur. Un exemple est la transmission de vidéo où chaque
message est le couleur d’un pixel d’une image vidéo.
Prenons l’exemple ci-dessous où chaque message vient d’un ensemble de 5 messages avec
probabilités p(m1) = 0.5, p(m2) = 0.3, p(m3) = 0.09, p(m4) = 0.06 et p(m5) = 0.05. L’entropie de
cette source est H(X) = 1.79 bits/message.
Une possibilité d’encodage de cette source est d’accorder L bits/message où L est un entier. Si L
= 2 on ne peut encoder que 4 messages, donc on doit utiliser L = 3. Alors un code possible est
donné par :
Tableau 7.1 : Code de longueur 3 bits
Message p(mi) Mot de code
m1 0.5 000
m2 0.3 001
m3 0.09 010
m4 0.06 011
m5 0.05 100
Cependant, on peut avoir un encodage plus efficace si on utilise un code où la longueur des mots
de codes associés aux messages plus probables est plus courte que la longueur des mots de code
des messages moins probable. Une possibilité d’encodage de cette source est d’accorder L
bits/message où L est un entier. Si L = 2 on ne peut encoder que 4 messages, donc on doit
utiliser L = 3. Alors un autre code possible est donné par :
Tableau 7.2 : Code de longueur variable
Message p(mi) Mot de code
m1 0.5 00
m2 0.3 01
m3 0.09 100
m4 0.06 101
m5 0.05 111
Le code dans le tableau 7.2 a une longueur moyenne
∑ ( ) bits/message
Clairement la longueur moyenne du code du tableau 7.2 est inférieure à la longueur moyenne du
code du tableau 7.1. Mais un code à longueur variable est difficile à décoder. Il faut que le code
soit uniquement décodable. Un code à longueur variable est uniquement décodable s’il est un
code à préfixe conditionné. Un mot de code de N bits à N-1 préfixes de longueur i où i = 1, 2, …
N-1. Le préfixe à longueur i est les i premiers bits du mot de code. La figure 7.3 démontre un
mot de code à 4 bits et ses 3 préfixes.
Figure 7.3 : Les préfixes d’un mot de code.
Un code à préfixe conditionné est un code où aucun mode de code ne se trouve dans le préfixe
d’un autre mot de code. Le code du tableau 7.2 est un code à préfixe conditionné car les mots
de codes de longueur 2 sont 00 et 01 et les mots de code de longueur 3 ont comme préfixes 1, 10
ou 11. Aucun de ces préfixes est un mot de code. Alors si on reçoit 1000000000110000111, la
seule façon de le décoder est m3, m1, m1, m1, m2, m3, m1, m5. Le décodage est démontré à la
Figure 7.4.
Figure 7.4 : Décodage d’un code à préfixe conditionné.
Le code du tableau 7.2 est un code à préfixe conditionné donc le code est uniquement décodable.
Mais est-ce l’encodage le plus efficace? L’algorithme de Huffmann nous permet de trouver le
code à longueur variable qui minimise la longueur moyenne des messages. L’algorithme est
décrit ci-dessous.
1) Ordonner les N message en ordre descendante de probabilité.
2) Additionner les deux plus basses valeurs (probabilités) ensemble
3) Réorganiser la liste des valeurs afin qu'ils soient toujours dans l'ordre décroissant (placer
la nouvelle valeur dans sa propre position dans la liste).
4) S’il y a plus que deux valeurs, retourné à (2)
5) Travaillant en reculons, assigner le 0 à la plus haute valeur et 0 à la plus basse valeur.
6) Si la valeur est le résultat d’une addition, rajouter un 0 en annexe pour une branche et 1
pour l’autre branche.
7) Continuer jusqu’à tous les branches reviennent aux messages de la source.
L’algorithme est démontré à la Figure 7.5.
(a)
(b)
Figure 7.5 Encodage Huffmann (a) Instructions (1) à (4), (b) Instructions (5) à (7).
D’après la Figure 7.5, le code le plus efficace est m1 = 0, m2 = 10, m3 = 111, m4 = 1100 et m5 =
1101. La longueur moyenne est L = (0.5)(1)+(0.3)(2)+(0.09)(3)+(0.06)(4)+(0.05)(4) = 1.81
bits/message.
La théorie d’information nous montre que L ≥H(X). L’efficacité du code Huffmann est
( )
(7.13)
L’entropie de cette source est 1.79 bits/message donc l’efficacité de ce code est = 1.79/1.81 =
0.989.
Exemple 7.5
Créer un code Huffmann pour la source X qui émet les messages {m1, m2, m3, m4, m5, m6} avec
les probabilités {0.2, 0.23, 0.15, 0.17, 0.14, 0.11}. C’est quoi l’efficacité de ce code?
Solution
Les étapes (1) à (4) sont démontrées à la Figure 7.6 ci-dessous et puis l’encodage est fait à la
Figure 7.7.
Figure 7.6 : L’algorithm de Huffmann (étapes (1) à (4)) de l’exemple 7.5.
Figure 7.7 : L’encodage (étapes (5) à (7)) Huffmann.
Pour trouver la longueur moyenne, on remarque qu’il y a deux messages avec mots de code de
longueur 2 et quatre avec longueur 3. La probabilité d’avoir un mot de code de longueur 2 et
(0.23+0.2) = 0.43. Et la probabilité d’avoir un mot de code de longueur 3 est 0.57. Alors la
longueur moyenne est L = (2)(0.43)+3(0.57) = 0.86+1.71 = 2.57 bits/message.
L’entropie de la source est
( ) ( ) ( ) ( )
( ) ( ) ( )
L’efficacité = 2.545/2.57 = 0.99.