Travaux dirigés du Cours Théorie de l’Information
Série n°2
Prof. Assia EL HADBI
Année universitaire 2024-2025
Exercice 1 :
Appliquer la procédure de décodage pas à pas de la séquence 10110000101010100 avec le
code sans préfixe suivant :
Symbole si a b c d e f g h i j
mi 1111 1110 110 1011 1010 100 011 000 010 001
Exercice 2 :
Vérifier s’il existe un code binaire sans préfixe de longueurs de mots données :
{4, 4, 4, 3, 2, 4, 3, 4, 3, 4}
Exercice 3 :
1. Construire l’arbre binaire associé au code suivant :
Symbole si a b c d e f g h i j
mi 1111 1110 110 1011 1010 100 011 000 010 001
2. Construire un code sans préfixe de longueurs de mots suivantes, à l’aide d’un arbre binaire,
en procédant à l’élagage d’un arbre complet :
Symbole si a b c d e f g h i j
li 4 4 4 3 2 4 3 4 3 4
Exercice 4 :
Soit une source d’alphabet Ω et de distribution de probabilité suivante
Symbole si a b c d e f g h i j
pi 0.2 0.05 0.1 0.05 0.15 0.05 0.1 0.05 0.15 0.1
1
Théorie de l’information : TD2 2024-2025
1. Quelle est la longueur moyenne minimale pour un code binaire de cette source ?
2. Existe-t-il un code absolument optimal ?
3. Construire un code sans préfixe optimal selon la méthode de Huffman.
4. Représenter ce code sous forme d’arbre.
Exercice 5 :
Soit une source S = {s1 , s2 , s3 , s4 } de probabilités p(s1 ) = 1/8, p(s2 ) = 3/8, p(s3 ) = 1/16 et
p(s4 ) = 7/16.
1. Proposer un codage des alphabets en utilisant la méthode de Shannon Fano.
2. Calculer l’entropie de S.
3. Calculer la largeur moyenne des codes.
4. Refaire les mêmes questions en utilisant la méthode de Huffman.
Exercice 6 :
Soit une source S = {s1 , s2 , s3 , s4 , s5 , s6 , s7 , s8 , s9 } de probabilités
p = {2/16, 3/16, 1/16, 3/16, 1/16, 2/16, 1/16, 2/16, 1/16}.
1. Proposer un codage ternaire des alphabets en utilisant la base {=, +, ∗}.
2. Calculer l’entropie de S.
3. Calculer la largeur moyenne des codes.
4. Vérifier l’inégalité de Kraft.
Exercice 7 :
Les probabilités des 8 symboles émis par la source S sont indiquées dans le tableau suivant :
Symbole X1 X2 X3 X4 X5 X6 X7 X8
Probabilité 0.49 0.11 0.26 0.04 0.04 0.03 0.01 0.02
Pénalité 1 1 1 2 1 1 1 1
1. Concevoir des codes de Shannon Fano pour un canal binaire et des codes de Huffman pour
des canaux binaires et ternaires. Calculer la valeur moyenne des codes et leur redondance.
2. Les symboles X5 et X4 ont la même probabilité mais pas forcement la même significa-
tion. On souhaite donc transmettre un symbole plus rapidement que l’autre. Pour tenir
compte de cette
Pdifférence, construire un nouveau code qui minimise la longueur moyenne
8
pondérée L = i=1 pi · ci · li , où les pénalités ci sont indiquées sur le tableau ci-dessus.
Prof. Assia EL HADBI 2 INPT
Théorie de l’information : TD2 2024-2025
Exercice 8 : Le jeu de la fausse pièce
On considère un jeu de n pièces, toutes d’apparence identique. On sait qu’une seule pièce
est fausse. Elle a un poids différent des autres mais on ne sait pas si elle est plus légère ou plus
lourde.
On dispose d’une balance à deux plateaux. A chaque pesée, la balance peut se trouver dans
l’une des trois configurations :
G, elle penche vers la gauche,
D, elle penche vers la droite,
E, elle reste à l’équilibre,
L’objectif est de déterminer avec le moins de pesées possibles la fausse pièce et si elle est
plus légère ou plus lourde.
Soit n = 8 :
1. Combien de réponses possibles il y a dans ce problème ?
2. Combien de possibilités différentes peut-on obtenir avec 2 pesées ? Avec 3 pesées ? ⇒
Conclusion sur la faisabilité de la détermination de la fausse pièce en 2 ou 3 pesées.
3. Est-il intéressant de peser deux lots de 4 pièces chacun ? Pourquoi ? Quelle est la quantité
d’information nous apporterait une telle pesée ?
4. Représenter une stratégie de pesée sous forme d’arbre de décision. Les feuilles de l’arbre
doivent représenter toutes les réponses possibles. La profondeur de l’arbre indique alors
le nombre maximal de pesées.
Exercice 9 :
En utilisant la méthode de Lempel-Ziv, donner la compression et le codage de :
1. ”00000011010100000110101”
2. ”ELLE EST BELLE CETTE ECHELLE ETERNELLE”
3. ”ABBABBABBBAABABA”
Exercice 10 : Lempel-Ziv
En utilisant la méthode de Lempel-Ziv, Coder et décoder le message suivant à envoyer :
”aabaaaabaaaababac”
En considérant ce codage initiale suivant :
Symbole Code Indice
”a” 00 1
”b” 01 2
”c” 10 3
”d” 11 4
Prof. Assia EL HADBI 3 INPT
Théorie de l’information : TD2 2024-2025
Exercice 11 : Codage Sh. Fano & Huffman
Soit une source S = {s1 , s2 , s3 , s4 , s5 , s6 , s7 , s8 } de probabilités p(s1 ) = 0.11, p(s2 ) = 0.1,
p(s3 ) = 0.11, p(s4 ) = 0.25, p(s5 ) = 0.1, p(s6 ) = 0.09, p(s7 ) = 0.19 et p(s8 ) = 0.05.
1. Proposer un codage des alphabets en utilisant la méthode de Shannon Fano.
2. Calculer l’entropie de S.
3. Calculer la largeur moyenne des codes.
4. Refaire les mêmes questions en utilisant la méthode de Huffman.
Prof. Assia EL HADBI 4 INPT
