Université Badji mokhtar Faculté des technologies département d’Informatique EMD
Codage de l’informationMaser 1 IATI (durée 1H 30mn)
Questions
Répondre par oui ou non (6.5pts)
1. Le système de numération décimal est utilisé par les ordinateurs pour représenter les
données.
2. 8 bits sont nécessaires pour représenter un nombre décimal entre 0 et 255.
3. Le code Unicode est le code standard utilisé pour représenter les caractères
alphanumériques dans les ordinateurs.
4. Le code ASCII standard utilise 7 bits pour représenter les caractères.
5. Le code d’ Hoffman permet de compresser les données en réduisant la redondance.
6. l'entropie est une mesure de la bande passante en théorie de l'information.
7. L'unité de mesure de l'entropie lorsque le logarithme est en base 2 est le watts.
8. L'entropie d'une source binaire équiprobable (par exemple, une pièce de monnaie
équilibrée) est égale à 0.5.
9. La condition nécessaire pour qu'un code soit instantanément décodable est que code doit
utiliser des mots de code de longueur fixe.
10. L’algorithme de tunstall est utilisé pour générer des codes de longueur variable optimaux
en fonction des probabilités des symboles.
11. Un code préfixe est un code où aucun mot de code n'est le préfixe d'un autre.
12. La valeur 0 est l'entropie d'une source certaine (un événement avec une probabilité de 1).
13. L'inégalité de Kraft en théorie des codes est Une condition nécessaire et suffisante pour
l'existence d'un code préfixe.
Exercice 1 (9 pts)
Quelle est l’unité de mesure de l’entropie ? (0.5pt)
Quelle est la signification physique de l'entropie ? (0.5pt)
Expliquez la relation entre l'entropie et l'incertitude. Donnez un exemple concret pour illustrer
cette relation. (1 pt)
Soit la source S={A, B, C, D, E, F} avec les probabilités suivantes P(A)=0.30, P(B)=0.25, P(C)=0.20,
P(D)=0.12 P(E)=0.08 et P(F)=0.05.
1. Appliquer l’algorithme d’ Huffman et donner les mots de code correspondant. (3pts)
2. Calculer l’efficacité du code ( 1.5pts)
3. Que peut-on dire de ce code (1.5 pts)
4. Encoder la séquence suivante A B C D E F. (1 pt)
Exercice 2 (4.5pts)
1est ce que ces codes peuvent être un code d’Hoffman ? Justifier votre réponse (1.5pt)
a. {1, 01, 00}
b. {00,01, 10, 110}
c. {01, 10}
2. Considérez les ensembles de codes suivants. Pour chaque ensemble, déterminez s'il s'agit d'un
code préfixe et s'il est complet.
1. Code 1 : {A:0, B:10, C:110, D:111} (1 pts)
2. Code 2 : {A:0, B:01, C:011, D:111} (1pts)
3. Code 3 : {A:00, B:01, C:10, D:11} (1pts)
Université Badji mokhtar Faculté des technologies département d’Informatique EMD
Codage de l’informationMaser 1 IATI (durée 1H 30mn)
Solution
Questions
Réponses 0.5 par réponse
1. non
2. oui
3. non
4. oui
5. oui
6. non
7. non
8. non
9. non
10. non
11. oui
12. oui
13. oui
Exercice 1 (9pts)
1. Définition de l'entropie :
1. L'entropie mesure l'incertitude ou la quantité d'information d'une source. Elle est
exprimée en bits (si le logarithme est en base 2).
2. Physiquement, elle représente la quantité moyenne d'information nécessaire pour
décrire la source.
2. Relation entre entropie et incertitude :
1. Plus l'entropie est élevée, plus l'incertitude est grande. Par exemple, une pièce de
monnaie équilibrée a une entropie de 1 bit, car il y a une incertitude maximale entre
"pile" et "face".
3. Construction de l'arbre de Huffman
1. Liste initiale :
\{A: 0,30, \ B: 0,25, \ C: 0,20, \ D: 0,12, \ E: 0,08, \ F:
0,05\}{A:0,30, B:0,25, C:0,20, D:0,12, E:0,08, F:0,05}
2. Fusionner les deux symboles les moins probables :
o E (0,08) et F (0,05) → nœud intermédiaire EF (0,13).
o Nouvelle liste :
\{A: 0,30, \ B: 0,25, \ C: 0,20, \ D: 0,12, \ EF: 0,13\}{A:0,30, B:0,25, C:0,20, D:0,12, EF:0,13}
3. Fusionner les deux symboles les moins probables :
o DD (0,12) et EF (0,13) → nœud intermédiaire DEF (0,25).
o Nouvelle liste :
\{A: 0,30, \ B: 0,25, \ C: 0,20, \ DEF: 0,25\}{A:0,30, B:0,25, C:0,20, DEF:0,25}
4. Fusionner les deux symboles les moins probables :
o C (0,20) et B (0,25) → nœud intermédiaire CB (0,45).
o Nouvelle liste :
\{A: 0,30, \ DEF: 0,25, \ CB: 0,45\}{A:0,30, DEF:0,25, CB:0,45}
5. Fusionner les deux symboles les moins probables :
Université Badji mokhtar Faculté des technologies département d’Informatique EMD
Codage de l’informationMaser 1 IATI (durée 1H 30mn)
o A (0,30) et DEF (0,25) → nœud intermédiaire ADEF (0,55).
o Nouvelle liste :
\{CB: 0,45, \ ADEF: 0,55\}{CB:0,45, ADEF:0,55}
6. Fusionner les deux derniers nœuds :
o CB (0,45) et ADEF (0,55) → nœud racine (1,0).
o L'arbre de Huffman est maintenant complet.
Les codes
Symbole Probabilité Code Huffman
A 0,30 11
B 0,25 01
C 0,20 00
D 0,12 100
E 0,08 1011
F 0,05 1010
Pour des codes différents cela signifie que vous avez fait un mauvais regroupement.
Calcul de l'efficacité
1. Longueur moyenne des mots de code :
L=(0,30×2)+(0,25×2)+(0,20×2)+(0,12×3)+(0,08×4)+(0,05×4)L = 0,60 + 0,50 + 0,40 + 0,36 + 0,32 + 0,20
=.L=0,60+0,50+0,40+0,36+0,32+0,20=2,38 bits.
2. Entropie de la source :
H=−0,30log2(0,30)−0,25log2(0,25)−0,20log2(0,20)−0,12log2(0,12)−0,08log2(0,08)−0,05log2(0,05)
H≈2,36 bits/symbole.
3. Efficacité du codage :
Efficacite ≈0,9916.
o Une efficacité de 99,16 % indique que le codage de Huffman est très efficace pour
cette source.
Encodage d'une séquence
Exemple : Encodons la séquence A B C D E F.
1. Séquence encodée :
00 10 11 010 0110 0111.
Exercice2
1. Les code b et c ne sont pas des code d’huffman vue que le code d’huffman est u code a
longueur variable.
2. (0.5pt pour préfix et 0.5 pt pour complet cela fera 1 pt pour chaque cas )
3. Il faut construire l’arbre binaire.
Code 1 : {A:0, B:10, C:110, D:111}
1. Code préfixe :
Université Badji mokhtar Faculté des technologies département d’Informatique EMD
Codage de l’informationMaser 1 IATI (durée 1H 30mn)
o Aucun mot de code n'est le préfixe d'un autre.
o Exemple : 00 n'est pas un préfixe de 1010, 110110 ou 111111.
o Conclusion : C'est un code préfixe.
2. Code complet :
o Tous les mots de code sont des feuilles dans l'arbre de Huffman.
o Aucun mot de code ne peut être étendu sans violer la propriété de préfixe.
o Conclusion : C'est un code complet.
Code 2 : {A:0, B:01, C:011, D:111}
1. Code préfixe :
o 00 est un préfixe de 0101 et 011011.
o Conclusion : Ce n'est pas un code préfixe.
2. Code complet :
o Puisque le code n'est pas préfixe, il ne peut pas être complet.
o Conclusion : Ce n'est pas un code complet.
Code 3 : {A:00, B:01, C:10, D:11}
1. Code préfixe :
o Aucun mot de code n'est le préfixe d'un autre.
o Exemple : 0000 n'est pas un préfixe de 0101, 1010 ou 1111.
o Conclusion : C'est un code préfixe.
2. Code complet :
o Tous les mots de code sont des feuilles dans l'arbre de Huffman.
o Aucun mot de code ne peut être étendu sans violer la propriété de préfixe.
o Conclusion : C'est un code complet.
