Théorie de l’information Ann. Univ.
2016-17
Université Hassan II de Casablanca Licence Informatique, Réseaux et Multimédia
Faculté des Sciences et Techniques Module : Théorie de l’information
Département de Mathématiques
Contrôle
O. KHADIR
Il sera tenu compte de la qualité et des soins apportés à la copie.
Exercice 1. (5 pts)
1. Donner la formule qui définit l’entropie de Shannon H(S) d’une source S dont les
symboles a1 , a2 , . . . , an ont pour fréquences respectivement p1 , p2 , . . . , pn .
1
2. Calculer l’entropie H(S) lorsque toutes les fréquences sont égales à .
n
3. Comparer H(S) avec la moyenne m des longueurs des mots d’un code de compression
quelconque.
4. Application numérique. Calculer H(S) avec les données du tableau suivant :
Symbole a1 a2 a3 a4 a5 a6
Fréquence 0.10 0.10 0.15 0.15 0.25 0.25
5. Interpréter le résultat de la question précédente.
Exercice 2. (4 pts)
Soit une source d’information S qui émet les symboles a, b, c, d, e avec les fréquences
respectives 0.1, 0.1, 0.2, 0.3, 0.3. On code ces symboles à l’aide des feuilles de l’arbre
binaire A.
1. Donner le codage binaire de chaque symbole.
2. Déterminer un code C1 de Huffman pour coder la source S.
3. Donner un code C2 de Shannon Fano pour le même objectif.
4. Comparer l’efficacité des trois codes.
Arbre A
1
Théorie de l’information Ann. Univ. 2016-17
Exercice 3. (6 pts)
L’entrée d’un canal de communication est un mot de 7 bits. La sortie est aussi un mot de
7 bits. Ce canal est bruité. Chaque fois qu’il est utilisé, il change au plus un des 7 bits et
le destinataire ne sait pas lequel.
1. Montrer, en décrivant un codeur et un décodeur, qu’on peut communiquer 4 bits sans
erreur à travers ce canal à chaque transmission de 7 bits. (On peut coder en binaire la
position de l’erreur sur 3 bits).
2. Appliquer la technique aux 4 bits en les complétant pour avoir 7 bits : 1 0 1 1.
3. Corriger le message reçu 1 1 0 1 0 0 0.
4. Calculer, en pourcentage, le rendement du canal.
5. Comment communiquer un méga octet sans erreur à travers ce canal bruité ?
Exercice 4. (5 pts)
Soit C1 = {01, 11, 011} le langage destiné à coder les symboles x, y, z.
1. Décoder le message reçu M1 = 0 1 1 1 1 0 1 0 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1.
2. Montrer que C1 est un code de transmission.
Soit C2 = {101, 0011, 011010, 101011, 0100011} le langage destiné à coder les symboles
a, b, c, d, e.
3. Vérifier que le message suivant est ambigu M2 =1 0 1 0 1 1 0 1 0 0 0 1 1.
4. Retrouver par le test de Sardinas et Patterson que le langage C2 n’est pas un code de
transmission.
5. Utiliser la question précédente pour construire un message ambigu.
• − − − − − • − − − − − • − − − − − • − − − − −•
2
Théorie de l’information Ann. Univ. 2016-17
Corrigé du contrôle
O. KHADIR
Exercice 1.
4. On trouve H(S) = 2.48 .
5. Interprétation : pour coder les 6 symboles on a besoin de 2.48 bits.
Exercice 2.
1.
Symbole a b c d e
codage 1010 1011 100 0 11
2. Voici un code de Huffman :
0.4 0.6
0.2 0.2(c) 0.3(d) 0.3(e)
0.1(a) 0.1(b)
Le codage est donc
Symbole a b c d e
codage 000 001 01 10 11
3. Voici un code de Shannon-Fano :
Symbole fréquence bit 1 bit 2 colonne vide codage
e 0.3 1 1 11
d 0.3 1 0 10
c 0.2 0 1 01
b 0.1 0 0 001
a 0.1 0 0 000
4. La moyenne des longueurs des mots du code arbre est 2.3. Celle des deux autres codes
est 2.2. Donc les 2 derniers sont plus efficaces.
3
Théorie de l’information Ann. Univ. 2016-17
Exercice 3.
2.
a1 a2 a3 a4 a5 a6 a7
0 1 1 0 0 1 1
3. L’erreur se trouve dans la 7ème position.
Exercice 4.
1. Le decodage de M1 donne zyx zxy xyz y.
Avec le test de Sardinas et Patterson : U0 = L, U1 = {1}, U2 = {1} = U1 . Comme 6∈ Ui ,
C1 est un code de transmission.
On peut faire autrement : on regarde le message de la droite. Si c’est un 01 alors on décode
par x. Si c’est un 11 on regarde le bit suivant, si c’est un 0 on décode les 3 bits par z, si
c’est un 1, on décode les 2 bits par y.
3. On trouve que de = acb.
4. Avec le test de Sardinas et Patterson : U0 = L, U1 = {011}, U2 = {010}, U3 = {0011},
U4 = {, . . .}. Comme ∈ U4 , C2 n’est pas un code de transmission.
5. On trouve le message 1 0 1 0 1 1 0 1 0 0 0 1 1.
•−−−−−•−−−−−•−−−−−•−−−−−•
4
Théorie de l’information Ann. Univ. 2016-17
. 0.6
0.3(d) 0.3(e)
Racine
Fils-gauche Sous-Arbre
Sous-Arbre 11
100 101
A
B C
D G
E F
