Corrigé du DS — Théorie de l’information et
codage
Questions de cours
Question 1
Énoncé
Proposer un schéma permettant de modéliser un système de communication. Donner le rôle de
chaque élément de la chaîne.
Réponse
Le modèle classique de Shannon est :
Source → Codeur source → Codeur canal → Canal → Décodeur canal → Décodeur source → Destinataire
Rôle :
Source : produit les messages.
Codeur source : compresse l’information.
Codeur canal : ajoute de la redondance pour corriger les erreurs.
Canal : support physique de transmission.
Décodeur canal : corrige les erreurs dues au bruit.
Décodeur source : reconstitue le message.
Destinataire : reçoit l’information finale.
—
Question 2
Énoncé
Dans une population :
P (B) = 0.25, P (Y ) = 0.30, P (Y |B) = 0.75
Calculer l’information reçue lorsque l’on apprend que la personne a les yeux bleus, puis l’infor-
mation supplémentaire lorsqu’on apprend qu’elle est blonde.
Réponse
Information obtenue en apprenant que la personne a les yeux bleus :
I(Y ) = − log2 P (Y )
I(Y ) = − log2 (0.30) = 1.737 bits
1
Calcul de la probabilité conjointe :
P (B ∩ Y ) = P (Y |B)P (B)
P (B ∩ Y ) = 0.75 × 0.25 = 0.1875
Probabilité conditionnelle :
0.1875
P (B|Y ) = = 0.625
0.30
Information supplémentaire :
I(B|Y ) = − log2 (0.625)
I(B|Y ) = 0.678 bit
Question 3
Énoncé
On lance une pièce dont les deux faces sont identiques.
Réponse
Il n’y a qu’une seule issue possible.
H(X) = −1 log2 (1) = 0
H = 0 bit
Question 4
Énoncé
Soit une source binaire S d’entropie H(S).
Soit S2 la source étendue composée de deux symboles indépendants.
Calculer H(S2 ).
Réponse
Pour deux variables indépendantes :
H(S2 ) = H(S1 , S2 )
2
H(S2 ) = H(S1 ) + H(S2 )
H(S2 ) = 2H(S)
Coder une source étendue permet d’améliorer l’efficacité du codage et de se rapprocher de la
borne de Shannon.
—
Question 5
Énoncé
La fonction de Kraft d’un code vaut 0.9.
Peut-on conclure qu’il est instantané ?
Réponse
La condition de Kraft est :
X
2−li ≤ 1
Comme
0.9 ≤ 1
il existe un code instantané ayant ces longueurs.
Mais cela ne prouve pas que le code donné est instantané.
—
3
Exercice 1
Source binaire :
P (X = 0) = p
P (X = 1) = 1 − p
Matrice de transition :
Y |X 0 −1 1
0 0.8 0.2 0
1 0 0.2 0.8
—
1) Distribution conjointe
P (X, Y ) = P (X)P (Y |X)
Y = 0 Y = −1 Y =1
X = 0 0.8p 0.2p 0
X=1 0 0.2(1 − p) 0.8(1 − p)
Distribution marginale :
PY (0) = 0.8p
PY (−1) = 0.2
PY (1) = 0.8(1 − p)
2) Entropie
HX (p) = −p log2 p − (1 − p) log2 (1 − p)
4
3) Entropie conditionnelle
Cas Y = 0
H(X|Y = 0) = 0
Cas Y = 1
H(X|Y = 1) = 0
Cas Y = −1
P (X = 0|Y = −1) = p
P (X = 1|Y = −1) = 1 − p
H(X|Y = −1) = HX (p)
Donc
H(X|Y ) = 0.2HX (p)
4) Information mutuelle
I(X; Y ) = H(X) − H(X|Y )
I(X; Y ) = HX (p) − 0.2HX (p)
I(X; Y ) = 0.8HX (p)
Donc
k = 0.8
5
Exercice 2
Alphabet :
{a, b, c, d, e, f }
1) Entropie maximale
Hmax = log2 6
Hmax = 2.585 bits
2) Codage fixe
2n ≥ 6
22 = 4 < 6
23 = 8 ≥ 6
n = 3 bits
3) Codes sans préfixe
Code C1 :
01 est préfixe de 010.
Donc pas sans préfixe.
Code C2 :
aucun mot n’est préfixe d’un autre.
Code C3 :
aucun mot n’est préfixe d’un autre.
Donc
C2 et C3
6
sont sans préfixe.
—
4) Distribution
(1/4, 1/4, 1/8, 1/8, 1/8, 1/8)
H(X) = 2.5 bits
Longueur moyenne :
L(C2 ) = 3
L(C3 ) = 2.75
Donc
C3 est le meilleur
5) Distribution
(0.4, 0.1, 0.1, 0.05, 0.2, 0.15)
H(X) = 2.2815
Longueur moyenne :
L(C2 ) = 2.75
L(C3 ) = 2.8
Donc
C2 est le meilleur code
Efficacité :
H(X)
η=
L
7
2.2815
η=
2.75
η ≈ 0.83
Comparaison avec codage fixe :
L=3
ηf ixe = 0.76
Donc
C2 est plus efficace que le codage fixe