TD2 : Exercices sur le codage entropique
Exercice 1:
Une source émet des symboles de l'alphabet S = { a, b, c, d, e } avec
les probabilités suivantes:
P(a) = 0.15, P(b) = 0.04, P(c) = 0.25, P(d) = 0.08 et P(e) = 0.48
1. Calculer l'entropie de S.
2. Trouver un code de Huffman pour cette source S.
3. Calculer la longueur moyenne du code trouvé.
4. Calculer son efficacité et sa redondance.
5. Ce code est il optimal ? Pourquoi ?
Rque : le logarithme est de base 2 : pour la conversion on peut utiliser la formule :
Exercice 2:
On considère une source qui va transmettre sur un canal bruité de
bande passante 100 KHz.
Les symboles à transmettre sont les suivants :
X= { 2.5 1 -1.5 0.7 0.7 1 -1 2 2 1}
Le signal reçu est :
Y= { 2 1 -1 0.7 1 1 -1 1.5 2 1.5 }
1. Calculer le rapport signal-bruit.
2. En déduire la capacité de ce canal.
3. Quel est alors le débit minimal de la ligne pour pouvoir transmettre
l’information.
Exercice 3:
Soit l’alphabet suivant donné par sa probabilité d’occurrence :
Etat Probabilité
E 0.48
A 0.21
S 0.12
T 0.08
U 0.06
Y 0.05
1) Calculer La longueur optimale de cet alphabet
2) Peut-on utiliser un codage à longueur fixe pour coder les 6 états de ce système
Justifier votre réponse.
3) Construire l’arbre et le code d’Huffman de ce système.
4) En déduire son efficacité et sa redondance.
5) Ce code est-il déchiffrable ? est-il optimal ?
Solution :
1) H=1,92 bit
2) Non : car avec 6 états, il nous faut 3 bits et non 2
3)
Occurrenc Code
e
E 0
A 10
S 110
T 1110
U 11111
Y 11110
4) Efficacité = H/ Lmoy = 1,92/2,13 = 0,9 soit 90%
H= 1,94 bit
La longueur moyenne du code est de :
Lmoy =0 . 48⋅1+0 . 21⋅2+0 . 12⋅3+0 . 08⋅4 +0 . 06⋅5+0. 05⋅5=2 .13
Redondance = 1 –eff = 0,1 soit 10%.
5) Pour verifier la déchiffrabilité du code il faut vérifier l’inégalité de Kraft <=1
(0.5)1 + (0.5)2 +(0.5)3 + (0.5)4 + 2 (0.5)5 = 0.5+0.25+0.125 + 0.125=1
Optimalité ( à un chiffre près ) ce code possède une efficacité de 90%
Lmoy = 2,1 bits et H=1,9 bits ce code est acceptable mais il n’est pas forcément le plus
optimal.
ANNEXE
Métriques de mesure des performances du codage entropique
a) Longueur moyenne :
On définit la longueur moyenne d’un code par :
Où l(x) définit la longueur en bits de (x)
p(x) est la probabilité d’occurrence de (x)
b) Efficacité
H (x )
L. log (Q)
H : est l'entropie de la source x
L : longueur moyenne du code
Q : valence ( égal à 2 en binaire )
Plus l’efficacité est proche de 1, plus le code est optimal.
c) Redondance
R=1-
d) Capacité d'un canal C
C = W. log2 ( 1 + SNR )
W : bande passante du canal
SNR : rapport signal sur bruit
Capacité d'un canal téléphonique avec W = 3, 7 kHz.
e) Inégalité de Kraft
L'inégalité de Kraft donne une condition nécessaire et suffisante pour qu'un code soit
déchiffrable. Pour un code défini sur un alphabet de taille , ( en binaire D=2), cette inégalité
s’écrit :
Où est l’espace des événements
