Théorie de l'information - 1
mardi 15 avril 2014
16:29
Entropie: H= −1𝑛𝑃𝑖∗log2𝑃𝑖
L'entropie représente l'incertitude.
Log2(x) = log(x)/log(2)
TD1 p.14:
Exercice 1: Calcul de l'entropie d'une source.
X une source d'alphabet [1,2,3,4,5].
Ici n = 5.
H = -0.1 log2(0.1) -0.2 log2(0.2) - 0.3log2(0.3) - 0.15log2(0.15) -0.25log2(0.25) = 2.23 bits/symbole
H = -4* 0.05*log2(0.05) -0.8log2(0.8) = 1.12193 bits/symbole
H = log2(n) = log2(5) = 2,32 bits/symbole
Exercice 2
L'alphabet de la source est [pile] de taille 1.       H = log2(1) = 0 
Alphabet: [pair,impair] de taille 2.    H = log2(2) = 1 bit/symbole
Xi
Pique
Cœurs
Carreau
Pi
3/10
4/10
2/10
1/10
H = -0.3*log2(0.3)-0.4*log2(0.4)-0.2*log2(0.2)-0.1*log2(0.1) = 1.85 bits/symbole.
Exercice 3
H(X) = -0.1log2(0.1) - 0.2log2(0.2) -0.3log2(0.3) - 0.15log2(0.15) -0.25log2(0.25) = 2.23 bits/symbole
p=P(A) = 0.1+0.3+0.25 = 0.65
q=P(B)= 1-p = 0.35 
===> H(p,q) = -0.65log2(0.65)-0.35log2(0.35) = 0.93 bits/symbole
Ha? Hb?
A: 
X
1
3
5
Pa(X)
0.1/0.65
0.3/0.65
0.25/0.65
Ha = 1.46 bit/symbole
Hb = 0.98 bit/symbole
Vérification propriété de groupe: H(X) = H(p,q) +pHa + qHb?
2.23 = 0.93 + 0.65*1.46 + 0.35*0.98
OK.
Exercice 4
Non car elle ne partage pas Omega en 2 sous-ensembles A et B équiprobables pour ainsi maximiser l'entropie.
H(X) = -0.1*log2(0.1)-0.2log2(0.2)-0.3log2(0.3)-0.15log2(0.15)-0.25log2(0.25)
= 0.23 bits/s
Propriété de groupe: H(X) = H(p,q) +pHa+qHb
Max H(p,q) = log2(p) = 1bit/symbole (p=0.5)
Meilleure question: Est-ce que le symbole X appartient à A={2,3}? Car p(X appartient à A) = p(X=2)+p(X=3) =0.2=0.3=0.5
Arbre:
Table de code:
X
1
2
3
4
5
mi(mot-code)
001
11
10
000
01
li (longueur)
3
2
2
3
2
Nombre moyen de questions:
      = 2.25 questions
X=2.3?
X=2?
X=5?
X=2                    X=3
X=5
X=1?
X=1          X=4
B:
X
2
4
Pb(X)
0.2/0.35
0.15/0.35