Exercices sur le codage de source

Exercice 3.5.1
Soit p la probabilité d’un événement, tracer la valeur de la quantité d’information relative à
l’événement en fonction de p pour 0 ≤ p ≤ 1.

Exercice 3.5.2
Une source émet aléatoirement un symbole parmi quatre symboles possibles. Ces quatre sym-
boles ont des probabilités d’occurrence telles que p0 = 0.4, p1 = 0.3, p2 = 0.2 et p3 = 0.1 et sont
statistiquement indépendants.
1. Calculer l’information associée à l’émission de chacun de ces 4 symboles.
2. Calculer l’entropie de la source.

Exercice 3.5.3
Considérons une source sans mémoire (les symboles émis sont statistiquement indépendants)
dont l’alphabet est constitué par K symboles équiprobables.
1. Quelle est le meilleur codage possible pour une telle source, à longueur fixe ou variable ?
Pourquoi ?
2. Quelle condition doit satisfaire K pour que l’efficacité du codage soit maximale ?

Exercice 3.5.4
Considérez les 4 codes listés dans la table suivante :

Symbole Code I Code II Code III Code IV

s0 0 0 0 00
s1 10 01 01 01
s2 110 001 011 10
s3 1110 0010 110 110
s4 1111 0011 111 111

1. Lesquels de ces codes sont à décodage instantanés ?

2. Calculer l’inégalité de Kraft-McMillan pour chacun de ces codes. Discutez les résultats en
fonctions de ceux obtenus en 1).

Exercice 3.5.5
Considérez des lettres d’un alphabet ayant les probabilités d’apparition telles que :

Lettre a i l m n o p y
Probabilité 0.1 0.1 0.2 0.1 0.1 0.2 0.1 0.1

TAB . 3.1 – Table associée à l’exercice 3.5.5

Cours de Télécommunications, FEE 1

 Calculez deux codes différents de Huffman pour cet alphabet. Dans un cas, reportez un symbole
combiné dans l’arbre à la position la plus haute, dans l’autre dans la position la plus basse. Pour
chacun des codes obtenus, calculez la longueur moyenne des mots code ainsi que la variance de la
longueur moyenne des mots code. Lequel de ces deux codages possibles choisirez-vous en pratique ?

Exercice 3.5.6
Une source discrète sans mémoire a un alphabet de 7 symboles dont les probabilités d’apparition
sont décrites dans la table suivante :

Symbole s0 s1 s2 s3 s4 s5 s6
Probabilité 1/4 1/4 1/8 1/8 1/8 1/16 1/16

Calculer le code de Huffman associé ainsi que son rendement.

Exercice 3.5.7
Considérez une source discrète sans mémoire avec un alphabet {s0 , s1 , s2 } dont les probabilités
d’apparition sont respectivement {0.7, 0.15,0.15} . Appliquez le codage d’Huffman à cette source
et montrez que la longueur moyenne du code est 1.3 bits/symbole.

Exercice 3.5.8
En considérant la figure 3.1, donnez les codes associés aux symboles A, B, C, D, E, F, G.

F IG . 3.1 – Figure liée à l’exercice 3.5.8

2 Cours de Télécommunications, FEE

Exercice 3.5.9
Un calculateur exécute 4 instructions qui sont représentées par les mots code (00, 01, 10, 11).
En supposant que ces instructions sont utilisées de manière indépendante avec des probabilités (1/2,
1/8, 1/8, 1/4), calculez le pourcentage d’économie de bits qui pourrait être réalisé avec un codage
de source optimal. Trouver un code de Huffman qui réalise ce codage optimal.

Exercice 3.5.10
Considérez la séquence binaire suivante
011100011100011100011100
Utilisez l’algorithme de Lempel-Ziv pour encoder cette séquence.

Exercice 3.5.11
Une source sans mémoire a un alphabet A tel que

A = {−5, −3, −1, 0, 1, 3, 5}

Les probabilités correspondantes sont

{0.05, 0.1, 0.1, 0.15, 0.05, 0.25, 0.3}

1. Trouver l’entropie de la source.
2. En supposant que la source est quantifiée selon la règle suivante :

Q(−5) = Q(−3) = −4
Q(−1) = Q(0) = Q(1) = 0
Q(3) = Q(5) = 4
trouver l’entropie de la source quantifiée.
3. Proposer un codage optimal de cette source quantifiée.

Exercice 3.5.12
Une source sans mémoire émet des symboles a1 , a2 , a3 , a4 avec des probabilités correspon-
dantes p1 = p2 = 0.3365 et p3 = p4 = 0.1635.
1. Trouver l’entropie de la source.
2. Trouver un code de Huffman pour cette source.
3. Calculer la longueur moyenne du code obtenu.
4. Calculer le rendement du code obtenu.

Exercice 3.5.13
Une source sans mémoire a un alphabet de 5 symboles S1 , S2 , S3 , S4 et S5 . Ces cinq symboles
sont équiprobables. Evaluez le rendement d’un code binaire de longueur constante dans les trois cas
suivants :
1. On code chaque symbole.
2. On code des paires de symboles.
3. On code des successions de trois symboles.

Cours de Télécommunications, FEE 3

Exercice 3.5.14
Une source sans mémoire émet des symboles S1 , S2 , S3 , S4 avec des probabilités p1 = 0.5,
p2 = 0.25, p3 = 0.125 et p4 = 0.125.
1. Coder chaque symbole avec un code de longueur fixe et calculer le rendement du code.
2. Trouver un code à décodage instantané de rendement 100%.

Exercice 3.5.15
Le schéma de la Figure 1 montre un schéma d’automate de Markov. Cet automate produit un
symbole toutes les T s., ce symbole peut être s0 ou s1 . On lit le schéma de la Figure 3.2 de la manière
suivante ; si s0 a été produit à l’instant k.T , la probabilité d’obtenir un nouveau s0 à l’instant (k +
1).T est 1/4, alors que la probabilité d’obtenir s1 à (k + 1).T est alors 3/4. (De tels automates
sont utilisés pour modéliser la production de parole.). On observera qu’une tel automate produit des
données qui sont dépendantes dans le temps. En supposant que l’on code des séquences de deux
symboles consécutifs :
1. Calculer l’entropie de la source constituée par l’automate.
2. Proposer un codage de Huffman des séquences de deux symboles.
3. Calculer l’efficacité du code ainsi créé.

1|4 3|4

3|4
s0 s1
1|4
F IG . 3.2 – Automate de Markov

Exercice 3.5.16
On considère une source S1 sans mémoire délivrant des symboles {s0 , s1 , s2 , s3 } avec des pro-
babilités respectives 1/4, 1/2, 1/16, 3/16. D’autre part on considère une source S2 sans mémoire
délivrant des symboles {t0 , t1 , t2 , t3 } avec des probabilités respectives 1/8, 1/32, 1/64, 53/64.
On considère ensuite une source S3 qui délivre aléatoirement soit un symbole de S1 , soit un symbole
de S2 à chaque coup d’horloge ; la probabilité que S1 soit choisie est de 3/4.
1. Calculer l’entropie de chacune des trois sources S1 , S2 et S3 .
2. Proposer un codage de Huffman des séquences de symboles pour chacune des trois sources.
3. Calculer l’efficacité des trois codes ainsi créés.

Exercice 3.5.17
Soit une source S1 sans mémoire délivrant des symboles {s0 , s1 , s2 , s3 , s4 } avec des pro-
babilités respectives 1/16, 1/16, 1/8, 1/4, 1/2. Sans faire appel à un graphe de type Huffman,
proposer un code à décodage instantané qui ait une efficacité de 100%. Justifier vos choix et expli-
quez bien pourquoi l’efficacité est de 100%.

4 Cours de Télécommunications, FEE

Exercice 3.5.18
On considère la séquence suivante que l’on veut encoder par l’algorithme de Lempel-Ziv.

010110111011110111110111111

On considère que 0 est le premier mot code et que 1 est le second mot code. On considère d’autre
part que les mots code sont numérotés à partir de 1.
1. Calculer la séquence codée par l’algorithme de Lempel-Ziv.
2. Calculer le taux de compression obtenu.
3. Vérifiez que la séquence obtenue est bien juste en procédant au décodage de la séquence.

Cours de Télécommunications, FEE 5

Solution de l’exercice 3.5.1
La quantité d’information liée à un événement E de probabilité p, est par définition :

I(E) = −log2 (p) (bits)

Lorsque p → 0, l’information devient infinie, elle devient nulle lorsque l’événement devient certain,
i.e. lorsque p = 1. L’allure de la quantité d’information associée à l’événement E en fonction de sa
probabilité d’apparition p est donnée à la figure 3.3.

5
Information (bits)

0
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
p

F IG . 3.3 – Figure associée à la solution de l’exercice 3.5.1

Solution de l’exercice 3.5.2

Le tableau suivant donne l’information associée à chacun des quatres symboles.

Symbole s0 s1 s2 s3
Probabilité 0.4 0.3 0.2 0.1
Information 1.3219 bits 1.7370 bits 2.3219 bits 3.3219 bits

L’entropie ou information moyenne s’écrit donc comme

H = −p0 log2 (p0 ) − p1 log2 (p1 ) − p2 log2 (p2 ) − p3 log2 (p3 ) = 1.8464 (bits)

Solution de l’exercice 3.5.3

1. Les symboles étant équiprobables, ils portent chacun la même information et doivent être
codés avec le même nombre de bits. Le meilleur codage est donc un codage à longueur fixe.
2. L’efficacité du codage sera maximale si le nombre de symboles K est une puissance de 2.
Si K = 2N , à chaque représentation par un mot binaire de N bits correspondra un symbole.
Si ce n’était pas le cas, certains mots binaires ne seraient pas affectés à des symboles et on
gaspillerait des bits inutilement.

6 Cours de Télécommunications, FEE

Solution de l’exercice 3.5.4
1) Ces codes peuvent être représentés par les arborescences décrites à la Figure 3.4 et à la
Figure 3.5.

F IG . 3.4 – Figure associée à la solution de l’exercice 3.5.4 (Codes I et II)

On voit que les codes I et IV sont des codes instantanés car aucun mot code n’est préfixe du
suivant. Sur l’arbre de décision, cela se traduit par des mots code qui ne sont pas situés sur une
même ligne.
Les codes II et III ne sont pas instantanés.
2) Si l’on applique l’inégalité de Kraft-McMillan, on obtient :

l1 = 2−1 + 2−2 + 2−3 + 2−4 + 2−4 = 0.5 + 0.25 + 0.125 + 0.0625 + 0.0625 = 1

l2 = 2−1 + 2−2 + 2−3 + 2−4 + 2−4 = 0.5 + 0.25 + 0.125 + 0.0625 + 0.0625 = 1

l3 = 2−1 + 2−2 + 2−3 + 2−3 + 2−3 = 0.5 + 0.25 + 0.125 + 0.125 + 0.125 = 1.125

l2 = 2−2 + 2−2 + 2−2 + 2−3 + 2−3 = 0.25 + 0.25 + 0.25 + 0.125 + 0.125 = 1
L’inégalité de Kraft-McMillan appliqué au code III prouve qu’il n’est pas instantané. L’inégalité de
Kraft ne détecte pas le fait que le code II n’est pas instantané. Or le code II a la même structure
que le code I. Rien d’anormal ici. L’inégalité de Kraft porte sur la structure du code mais pas sur la
façon de le réaliser.

Cours de Télécommunications, FEE 7

 F IG . 3.5 – Figure associée à la solution de l’exercice 3.5.4 (codes III et IV)

Solution de l’exercice 3.5.5

Selon les deux options choisies, on compare la probabilité du symbole agrégé avec les proba-
bilités des symboles restants. Dans un cas, (figure 3.6), le symbole agrégé est mis juste au dessus
de tous les symboles ayant même probabilité (si plusieurs symboles ont même probabilité), dans
l’autre cas, (figure 3.7), le symbole agrégé est mis juste au dessous de tous les symboles ayant
même probabilité (si plusieurs symboles ont même probabilité). On constate qu’on aboutit à deux
familles de codes. Dans le cas 1), tous les mots du code ont une longueur 3, la longueur moyenne
est 3. Dans le cas 2), les mots n’ont pas la même longueur, calculons la longueur moyenne du code,
celle-ci s’écrit :

l = 0.2 × 2 + 0.2 × 3 + 0.1 × 3 + 0.1 × 3 + 0.1 × 3 + 0.1 × 3 + 0.1 × 4 + 0.1 × 4 = 3

On sait que le code de Huffman est optimal du point de vue de la longueur moyenne (pour des
symboles indépendants). Bien sûr, ce code n’est pas unique dès que plusieurs symboles ont même
probabilité, toutefois les différentes solutions mènent à la même longueur moyenne.
Imaginons maintenant que l’on ait à coder une suite d’un grand nombre de symboles, par
exemple 100000. Si l’on utilise le code du cas 1) on sait que l’on obtiendra exactement une sé-
quence codée de 300000 bits. Dans le cas 2), on obtiendra un nombre de bits plus grand ou moins
grand que 300000, cela dépendra de la répartition des symboles dans la séquence particulière, on
sait que la longueur de la séquence codée oscillera autour de 300000. Il est donc évident que dans le
cas 1) la variance du code est nulle, alors que dans le cas 2), elle est non nulle. Dans la pratique on
préférera prendre la solution avec variance minimale, c’est-à-dire la première solution. Calculons

8 Cours de Télécommunications, FEE

maintenant la variance du code dans le cas 2), celle-ci s’écrit.

σ2 = 0.2 × (2 − l)2 + 0.2 × (3 − l)2 + 0.1 × (3 − l)2 + 0.1 × (3 − l)2

+0.1 × (3 − l)2 + 0.1 × (3 − l)2 + 0.1 × (4 − l)2 + 0.1 × (4 − l)2

soit en remplaçant l par sa valeur égale à 3

σ2 = 0.2 × (−1)2 + 0.1 × (1)2 + 0.1 × (1)2

= 0.4

L’influence de cette variance peut-être mieux appréciée en considérant l’exemple de la séquence de

100000 symboles. La figure 3.8 examine la probabilité d’obtenir
√ une séquence de longueur donnée
avec un code de longueur moyenne 3 et d’écart-type σ = 0.4. Pour calculer cette probabilité on
utilise une loi normale telle que

x−l 2
1 −1
p(x) = √ exp 2 σ
σ 2π
√
On calcule la probabilité pour l = 3 et σ = 0.4, ceci correspondant à la probabilité pour symbole,
pour 100000 symboles on dilate l’axe des x en multipliant par 100000.

0.6
(0)
0.4 0.4
(1)
0.4 0.4 (0)

0.2 0.2

(1)
0.2 0.2 (0)

0.2 0.2 0.2

(1)
0.2 0.2 0.2 (0)
L 0.2

0.2 0.2 0.2

O 0.2
(1)
0.1 0.1 (0)
A 0.1
0.1 0.1
I 0.1 L=000
(1) O=001
0.1 (0) A=010
M 0.1 I=011
0.1 M=100
N=101
N 0.1
P=110
(0) (1) Y=111
P 0.1

Y 0.1
(1)

F IG . 3.6 – Figure associée à la solution de l’exercice 3.5.5 -cas 1)

Cours de Télécommunications, FEE 9

 0.6
(0)
0.4 0.4
(1)
0.4 (0)

0.2 0.2 0.2

L 0.2
(1)

0.2 0.2 (0)

O 0.2
0.2 0.2

(1)
0.2 (0)

0.1 (0)
A 0.1
0.2
0.1 (1)
I 0.1
(1)
L=01
O=010
0.1 A=110
0.1 (0)
M I=111
M=100
N=101
0.1 P=0010
N 0.1 Y=0011
(1)

(0)
P 0.1

Y 0.1
(1)

F IG . 3.7 – Figure associée à la solution de l’exercice 3.5.5 -cas 2)

0.7

0.6
Probabilité d avoir une longueur de séquence

0.5

0.4

0.3

0.2

0.1

0
1 1.5 2 2.5 3 3.5 4 4.5 5
Nombre de bits pour 100000 symboles codés avec le code 2) x 10
5

F IG . 3.8 – Figure associée à la solution de l’exercice 3.5.5 -cas 2, probabilité d’obtenir une séquence
de longueur donnée pour 100000 symboles codés)

10 Cours de Télécommunications, FEE

Solution de l’exercice 3.5.6
La figure 3.9 détaille la solution. On peut remarquer que chaque symbole est codé exactement
par un nombre de bits correspondant à sa quantité d’information. Par exemple S0 a une quantité
d’information égale à (− log2 14 ) = 2 et est bien codé sur 2 bits. Le rendement d’un tel code est de
100 %, cela s’explique ici par le fait que le code de Huffman est optimal et que les probabilités des
symboles correspondent à des puissances négatives de 2.

1/2
(0)

1/4 1/4
S0 1/4 (0)

1/2
(1)
1/4 1/4
S1 1/4 (1)

1/4
(0)
1/8
S2 1/8 (0)
1/4
(1)

1/8
S3 1/8 (1)

S0=10
S1=11
1/8 (0)
S4 1/8 S2=010
S3=011
1/8 S4=000
(1) S5=0010
S6=0011

S5 1/16 (0)

S6 1/16 (1)

K   GI     

F IG . 3.9 – Figure associée à la solution de l’exercice 3.5.6

Solution de l’exercice 3.5.7

La solution est donnée à la figure 3.10. La longueur moyenne associée au codage de Huffman
est donc :
l = 0.7 × 1 + 0.15 × 2 + 0.15 × 2 = 1.3 bits
Si l’on considère que l’entropie H de la source, elle vaut

H = 0.7 × (− log2 (0.7)) + 0.15 × (− log2 (0.15)) + 0.15 × (− log2 (0.15)) = 1.1813 bits

Le rendement de ce code est donc η = 1.1813/1.3 = 91%.

Cours de Télécommunications, FEE 11

 $  &     

F IG . 3.10 – Figure associée à la solution de l’exercice 3.5.7

Solution de l’exercice 3.5.8

En considérant la figure 3.1, on code les symboles de la manière suivante :

A = 1
B = 011
C = 010
D = 001
E = 0001
F = 00001
G = 00000

Solution de l’exercice 3.5.9

L’entropie de la source vaut
1 1 1 1 1 1 1 1
H= (− log2 ( )) + (− log2 ( )) + (− log2 ( )) + (− log2 ( ))
2 2 8 8 8 8 16 16
soit
1 1 1 1 3
H= + ×3+ ×3+ × 4 = = 1.5 bits
2 8 8 16 2
Là où l’on utilise 2 bits par symbole, on pourrait en utiliser 1.5, on pourrait donc faire une économie
de 0.5/2 bits par symbole, soit 25% d’économie si l’on codait convenablement, c’est à dire avec
un rendement de 100 %. Ceci est possible ici avec un code de Huffman car les probabilités des
symboles sont en puissances négatives de 2. La solution est donnée à la figure 3.11. Le rendement
obtenu est de 100% puisque chaque symbole est codé avec un nombre de bits égal à sa quantité
d’information.

12 Cours de Télécommunications, FEE

 $      

F IG . 3.11 – Figure associée à la solution de l’exercice 3.5.9

Cours de Télécommunications, FEE 13

Solution de l’exercice 3.5.10
Considérons la séquence
011100011100011100011100
Recherchons dans cette séquence de façon récurrente les séquences les plus courtes différentes de 0
et 1 et différentes des séquences déjà rencontrées :

01 11 00 011 10 001 110 0011 100

Ajoutons maintenant en préambule les deux premiers mots codes 0 et 1 et indexons les mots du
dictionnaire.

M ots code 0 1 01 11 00 011 10 001 110 0011 100

N uméro de mot code 1 2 3 4 5 6 7 8 9 10 11

Chaque mot code va être maintenant divisé en deux parties, d’une part un préfixe qui est un mot
code et un bit d’innovation. Ceci permet une indexation des mots code à partir des précédents. On
note donc le préfixe sous la forme du numéro de mot code.

M ots 0 1 01 11 00 011 10 001 110 0011 100

N uméro 1 2 3 4 5 6 7 8 9 10 11
P réf. − inno. 0 1 01 11 00 01 1 10 00 1 11 0 001 1 10 0
Codage 1−1 2−1 1−0 3−1 2−0 5−1 4−0 8−1 7−0

Pour coder en binaire, il reste donc à vérifier le nombre de bits à transmettre. Les mots code pré-
fixe utilisés sont entre 0 et 8, ils nécessitent 4 bits de codage. Il faut donc cinq bits avec le bit
d’innovation.
Codage 1−1 2−1 1−0 3−1 2−0 5−1 4−0 8−1 7−0
Codage f in. 0001 − 1 0010 − 1 0001 − 0 0011 − 1 0010 − 0 0101 − 1 0100 − 0 1000 − 1 0111 − 0

La séquence codée est donc :

000110010100010001110010001011010001000101110

14 Cours de Télécommunications, FEE

Solution de l’exercice 3.5.11
1. L’entropie de la source est la moyenne de l’information apportée par la source. Désignons par
S 1 , S2 , S3 , S4 , S5 , S6 , S7
les 7 symboles de source de probabilités respectives

{0.05, 0.1, 0.1, 0.15, 0.05, 0.25, 0.3}

L’information apportée par chaque symbole Si pour i = 1 . . . 7 est
I(Si ) = −log2 (p(Si ))
Soit, tous calculs faits pour les 7 symboles
I(S1 ) = 4.3219, I(S2 ) = 3.3219, I(S3 ) = 3.3219, I(S4 ) = 2.7370
I(S5 ) = 4.3219, I(S6 ) = 2, I(S7 ) = 1.7370
La moyenne de l’information ou entropie de la source s’écrit donc
H = I(S1 )×p1 +I(S2 )×p2 +I(S3 )×p3 +I(S4 )×p4 +I(S5 )×p5 +I(S6 )×p6 +I(S7 )×p7
Soit par application numérique :

H = 4.3219×0.05+3.3219×0.1+3.3219×0.1+2.7370×0.15+4.3219×0.05+2×0.25+1.7370×0.3
c’est à dire
H = 2.5282 bits
Ceci veut dire qu’en moyenne, un codage optimum de la source (s’il existe) devrait être
effectué avec 2.5282 bits par symbole.
2. La quantification de la source consiste à agréger des symboles. En sortie de la source quanti-
fiée on n’a plus que 3 symboles maintenant. Convenons d’appeler
T 1 , T2 , T3
ces 3 symboles de niveaux respectifs −4, 0 et +4. On voit que l’apparition du symbole T1 est
liée à l’apparition de S1 ou de S2 à la source avant quantification.
T 1 = S1 ∪ S2
Or la source primaire étant sans mémoire, tous les Si sont indépendants. La probabilité d’une
union d’événements est donc la somme des probabilités des événements. Par conséquent
p(T1 ) = p(S1 ) + p(S2 ) = 0.15
On trouverait de même
p(T2 ) = p(S3 ) + p(S4 ) + p(S5 ) = 0.3
et
p(T3 ) = p(S6 ) + p(S7 ) = 0.55
(Au passage on vérifie que p(T1 ) + p(T2 ) + p(T3 ) = 1.) L’information (en bits) liée à l’ap-
parition de ces 3 symboles est donc
I(T1 ) = −log2 (0.15) = 2.7370, I(T2 ) = −log2 (0.3) = 1.7370, I(T3 ) = −log2 (0.55) = 0.8625
L’entropie de la source quantifiée est donc

H = 2.7370 × 0.15 + 1.7370 × 0.3 + 0.8625 × 0.55 = 1.4060 bits

Cours de Télécommunications, FEE 15

 3. Un codage optimal de cette source quantifiée est donnée par un codage d’Huffman (Voir
Fig. 3.12). Le code obtenu utilise des mots de 1 bit avec une probabilité 0.55 (symbole T3 ),

$       

F IG . 3.12 – Codage optimal de Huffman pour l’exercice 3.5.11

des mots de 2 bits avec une probabilité 0.3 (symbole T2 ) et des mots de 2 bits aussi avec une
probabilité 0.15 (symbole T1 ), on voit donc au passage que la longueur moyenne du code
obtenu serait

L = 1 × 0.55 + 2 × 0.3 + 2 times0.15 = 1.45 bits

L’efficacité du code est donc 1.4060/1.45 = 97% .

16 Cours de Télécommunications, FEE

Solution de l’exercice 3.5.12
1. L’information (en bits) apportée par les 4 symboles a1 , a2 , a3 , a4 en utilisant la formule de
l’information p(ai ) = −log2 (p(ai )), i = 1 . . . 4 s’écrit

I(a1 ) = 1.5713 , I(a2 ) = 1.5713 , I(a3 ) = 2.6126 , I(a4 ) = 2.6126

L’entropie qui est l’information moyenne s’écrit donc

H = 1.5713×0.3365+1.5713×0.3365+2.6126×0.1635+2.6126×0.1635 = 1.9118 bits

2. Un codage de Huffman possible pour cette source est donnée à la Fig. 3.13.

$        

F IG . 3.13 – Codage optimal de Huffman pour l’exercice 3.5.12

3. On utilise donc des symboles à 1 bit avec une probabilité 0.3365 (a1 ), des symboles à 2 bits
avec une probabilité 0.3365 (a2 ), des symboles à 3 bits avec une probabilité 0.1635 (a3 ), des
symboles à 3 bits avec une probabilité 0.3365 (a2 ). La longueur moyenne s’écrit donc

L = 0.3365 × 1 + 0.3365 × 2 + 0.1635 × 3 + 0.1635 × 3 = 1.9905 bits

4. L’efficacité du code est donc 1.9118/1.9905 = 96%.

Cours de Télécommunications, FEE 17

Solution de l’exercice 3.5.13
Si les 5 symboles sont équiprobables, leurs probabilités sont donc p1 = p2 = p3 = p4 =
p5 = 0.2. L’information apportée par chaque symbole est −log2 (0.2) = 2.3219 bits. L’information
moyenne ou entropie est aussi 2.3219 bits
1. Si l’on code avec un code de longueur constante il faut au moins 3 bits pour coder 5 symboles.
La longueur moyenne du code est donc 3 bits. L’efficacité du code est le rapport de l’entropie
à la longueur moyenne, c’est donc
Ef f. = 2.3219/3 = 77.40%

2. Si l’on regroupe les symboles par paires, il y a 52 = 25 symboles possibles dont la probabilité
est 0.22 = 0.04. Pour coder ces 25 symboles il faut donc 5 bit par symbole. Cela revient à
dire que l’on utilise 2.5 bits par demi-symbole c’est-à dire pour chaque symbole de la source
dont l’entropie vaut 2.3219 bits. L’efficacité du code est donc
Ef f. = 2.3219/2.5 = 92.88%

3. Si l’on regroupe les symboles par triplets, il y a 53 = 125 symboles possibles dont la pro-
babilité est 0.23 = 0.008. Pour coder ces 125 symboles il faut donc 7 bit par symbole. Cela
revient à dire que l’on utilise 7/3 = 2.333 bits par tiers de symbole c’est-à dire pour chaque
symbole de la source dont l’entropie vaut 2.3219 bits. L’efficacité du code est donc
Ef f. = 2.3219/2.333 = 99.51%

Solution de l’exercice 3.5.14

1. Avec un code de longueur fixe, il faut 2 bits par symbole pour coder les 4 symboles. L’in-
formation liée à chaque symbole vaut I(S1 ) = 1, I(S2 ) = 2, I(S3 ) = 3, I(S4 ) = 3.
L’information moyenne ou entropie vaut donc

H = 1 × 0.5 + 2 × 0.25 + 3 × 0.125 + 3 × 0.125 = 1.75 bits

Comme la longueur moyenne du code est 2, l’efficacité du code est
Ef f. = 1.75/2 = 87.5%

2. Le code de rendement 100% serait un code qui code chaque symbole avec le même nombre
de bits que l’information apportée par chaque symbole. On pourrait le trouver avec un code de
Huffman, toutefois dans un cas aussi simple on peut trouver facilement un tel code instantané.
Par exemple codons S1 → 0, (1 seul bit), puis S2 → 10 (2 bits), puis S3 → 110 (3 bits) et
S4 → 111 (3 bits). Ce code a une efficacité de 100%, de plus, il est instantané car aucun des
mots codes n’est préfixe des autres.

Solution de l’exercice 3.5.15

1. Supposons que α désigne la probabilité à une itération n de l’automate d’avoir émis un sym-
bole S0 , la probabilité que l’automate ait émis S1 est alors 1 − α puisqu’il n’y a que deux
états. Maintenant quelle est la probabilité d’émettre S0 à l’itération n + 1, cette probabilité
s’écrit :
P (S0 , n + 1) = P (S0 , n + 1|S0 , n).P (S0 , n) + P (S0 , n + 1|S1 , n).P (S1 , n)
= P (S0 , n + 1|S0 , n).α + P (S0 , n + 1|S1 , n).(1 − α)
= 14 .α + 14 .(1 − α)
= 14

18 Cours de Télécommunications, FEE

 On voit donc ici un résultat remarquable, on a bien un phénomène sans mémoire, puisque
quel que soit l’état initial, la probabilité d’émettre S0 ne dépend pas de α, c’est à dire de
la probabilité de l’état précédent. Comme la probabilité d’émettre S0 est 14 , la probabilité
d’émettre S1 à l’itération n + 1 est 34 . L’entropie de la source est donc aisée à calculer :

1 1 3 3
H= × (−log2 ( )) + × (−log2 ( )) = 0.8113 [bits]
4 4 4 4
(On rappelle la signification de l’entropie ; c’est le débit moyen d’information. Si on était
capable de coder avec une efficacité de 100 %, cela voudrait dire que 10000 symboles consé-
cutifs générés par l’automate pourraient être codés avec 8113 bits). Si l’on codait symbole par
symbole, c’est-à-dire S0 avec 0 et S1 avec 1, on utiliserait un bit par symbole et l’efficacité
du code serait de 81.13 %.
2. Si l’on code deux symboles consécutifs au lieu d’un, il faut considérer les quatre paires pos-
sibles de symboles [S0 , S0 ], [S0, S1 ], [S1 , S0 ] et [S1 , S1 ]. Ces quatre paires de symboles
ont des probabilités respectives 14 × 14 = 1/16, 14 × 34 = 3/16, 34 × 14 = 3/16, 34 × 34 = 9/16.
On trouvera à la figure 2 le codage de Huffman associé.

$ $     

F IG . 3.14 – Codage de Huffman associé à l’exercice 3.5.15

3. On remarque que le nombre moyen de bits pour coder deux symboles est

9 3 3 1 27
1× +2× +3× +3× = bits
16 16 16 16 16
Pour coder un seul symbole on utilise donc la moitié de ces bits, soit 12.5/16 = 0.8438.
L’efficacité est donc de 0.8113/0.8438 = 96.15%.

Solution de l’exercice 3.5.16

1.
1
H(S1) = 4 × (−log2 ( 14 )) + 1
2 × (−log2 ( 12 )) + 1
16
1
× (−log2 ( 16 )) + 3
16
3
× (−log2 ( 16 ))
= 1.7028 bits

H(S2) = 18 × (−log2 ( 18 )) + 1
32
1
× (−log2 ( 32 )) + 1
64
1
× (−log2 ( 64 )) + 53
64 × (−log2 ( 53
64 ))
= 0.8503 bits

Cours de Télécommunications, FEE 19

 La troisième source S3 est constituée des symboles s0 , s1 , s2 , s3 , t1 , t2 , t3 , t4 avec des
probabilités respectives 3/16, 3/8, 3/64, 9/64, 1/32, 1/128, 1/256, 53/256. Après cal-
culs, on trouve
H(S3) = 2.3010 bits
2. Codage de Huffman des trois sources. Ce codage est représenté à la figure 3.
3. La longueur moyenne du code de Huffman de S1 est
1 1 3 1 28
1× +2× +3× +3× = = 1.75 bits
2 4 16 16 16
L’efficacité du codage de S1 est donc

1.7028/1.75 = 97.3 %

La longueur moyenne du code de Huffman de S2 est

53 8 2 1 78
1× +2× +3× +3× = = 1.2188 bits
64 64 64 64 64
L’efficacité du codage de S2 est donc

0.8503/1.2188 = 69.77 %

La longueur moyenne du code de Huffman de S3 est

96 53 48 36 12 8 2 1 619
1. + 2. + 3. + 4. + 5. + 6. + 7. + 7. = = 2.4180 bits
256 256 256 256 256 256 256 256 256
L’efficacité du codage de S3 est donc

2.3010/2.4180 = 95.16 %

20 Cours de Télécommunications, FEE

 Codage de S1
1/2
S1 S1 --> 0
(0)
S0 --> 10
1/4 (0) S3 --> 110
S0 S2 --> 111
1/2
(1)

3/16
(0) (1)
S3 1/4

1/16
S2
(1)
Codage de S2
53/64
t3 (0)
t3 --> 0
1/8 (0) t0 --> 10
t0 t1 --> 110
11/64
(1) t2 --> 111

1/32
(0) (1)
t1
3/64

1/64
t2
(1)
Codage de S3 (0)

s1, 3/8 (1)

(0)
S1 --> 1
t3, 53/256 t3 --> 01
(1) s0 --> 001
(0)
s3 --> 0000
s2 --> 00010
s0, 3/16 t0 --> 000110
(0) (1) t1 --> 0001110
s3, 9/64
(0) t2 --> 0001111
s2, 3/64
(0)
t0, 1/32
(1)
t1, 1/128 (0)
(1)
t2, 1/256 (1)
(1)
E G IL  GI    

F IG . 3.15 – Codages de Huffman associé à l’exercice 3.5.16

Cours de Télécommunications, FEE 21

Solution de l’exercice 3.5.17
Les probabilités des symboles étant des puissances exactes de 2, les quantités d’information sont
des nombres entiers, i.e.

I(s0 ) = −log2 (1/16) = −log2 (2−4 ) = 4

I(s1 ) = −log2 (1/16) = −log2 (2−4 ) = 4

I(s2 ) = −log2 (1/8) = −log2 (2−3 ) = 3
I(s3 ) = −log2 (1/4) = −log2 (2−2 ) = 2
I(s4 ) = −log2 (1/2) = −log2 (2−1 ) = 1
Si l’on veut coder avec une efficacité de 100%, il suffit de coder chaque symbole avec un nombre
de bits égal à la quantité d’information apportée par le symbole. Il faut bien sûr que le code soit à
décodage instantané, et donc que chaque mot-code ne soit pas préfixe d’un autre mot-code.
Par exemple, s4 → 0, s3 → 10, s2 → 110, s1 → 1110, s1 → 1111 est un code instantané à
efficacité 100%.

Solution de l’exercice 3.5.18

1. Soit la séquence
010110111011110111110111111
0 et 1 étant les mots-code numéro 1 et 2 qui sont dans le dictionnaire, trouvons la séquence
de mots-codes les plus courts qui ne sont pas déjà dans le dictionnaire. La séquence est main-
tenant divisée de la manière suivante

01|011|0111|01111|011111|0111111|

Position du mot dans le dictionnaire 1 2 3 4 5 6 7 8

Mot du dictionnaire 0 1 01 011 0111 01111 011111 0111111
Numéro du préfixe - bit d’innovation 1-1 3-1 4-1 5-1 6-1 7-1
Mots codés 001-1 011-1 100-1 101-1 110-1 111-1

TAB . 3.2 – Constitution de la séquence codée

La séquence codée est donc

0011|0111|1001|1011|1101|1111

2. La séquence codée compte 24 bits contre 27 pour la séquence originale. Le taux de compres-
sion est donc de 3/27 = 11.11%.
3. On suppose que le décodeur connaît la longueur des mots, en l’occurence 4. Le décodeur
identifie le mot-codé 0011 comme étant formé de 001 − 1, c’est-à dire de l’adresse du premier
mot code et du bit d’innovation 1. Le premier mot du dictionnaire étant 0, on décode donc 01
comme étant le troisième mot du dictionnaire. Le mot-codé suivant est 011 − 1, c’est-à-dire
pointant vers le troisième code et suivi du bit d’innovation 1, on décode alors 011 comme
étant le quatrième mot-code. Le mot-code suivant étant 100 − 1, soit le pointeur du quatrième
mot-code suivi du bit d’innovation 1, on décode 0111 comme étant le cinquième mot-code,
etc.

22 Cours de Télécommunications, FEE