Théorie d’infromation

Mourad NACHAOUI

ENSA de Khouribga

April 3, 2023

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 1/1

 Codage de source

Codage de source

Multiples modèlisations de la source d’un système de communication.

Nous nous concentrons sur les sources discrètes et sans mémoire.
Une telle source produit une séquence de lettres tirées dans un
alphabet fini A = {a1, . . . , ak } selon une distribution (p(ai ))i=1...k .
On suppose également que les tirages de lettre sont indépendants les
uns des autres.
Une source discrète sans mémoire est modélisée par un espace
probabilisé discret (A, p).

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 2/1

 Codage de source

Définition 1
Le codage de source correspond à la transformation de la sortie en une
suite de bits. On souhaite construire des codes efficaces, c’est-à-dire tels
que la taille moyenne des suites de bits produites par le code soit la plus
petite possible.

Exemple 1
dans le code Morse les lettres les plus fréquentes de l’alphabet français
sont codées par un petit nombre de symboles : le ” e ” est codé par ” . ”,
tandis que le ” y ” est codé par ” . ”.

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 3/1

 Codage de source

Encodage d’un alphabet

Soit X un ensemble fini de lettres, un mot x sur X est une séquence de

lettres de X , notée x = x1 |x2 | . . . |xn , ou parfois x1 x2 . . . xn lorsque le
contexte le permet. On note l(x) la longueur du mot x; dans l’exemple
précédent l(x) = n. L’ensemble des mots de longueur finie sur X est noté
X ∗ . On représente par  le mot vide (de longueur 0) et on définit
X + = X ∗ r {}.
Définition 2
Soit A = {a1 , . . . , ak } un alphabet fini. Un code (binaire) de A est une
application C : A → {0, 1}+ . Le codage associé est alors l’application :

C + : A+ 7→ {0, 1}+
x = x1 | . . . |xn 7→ C + (x) = C (x1 )| . . . |C (xn )

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 4/1

 Codage de source

Encodage d’un alphabet

Définition 3
Soit X = (X , pX ) une source discrète sans mémoire et C un code de X .
On note X
¯ ) = E(`(C )) =
`(C `(C (x))pX (x)
x∈X

la longueur moyenne du code. L’efficacité du code est alors

H(X )
E (C ) = ¯
`(C )

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 5/1

 Codage de source

Caractérisation d’un codage

Vocabulaire

Régularité. Un code est dit régulier, ou encore non-singulier si tous

les mots de code sont distincts.
Déchiffrabilité. Un code régulier est dit déchiffrable, ou encore à
décodage unique, si toute suite de mots de code ne peut être
interprétée que de manière unique.
Longueur fixe. Avec des mots de longueur fixe, on peut décoder
tout message sans ambiguı̈té.
Séparateur. On consacre un symbole de l’alphabet de destination
comme séparateur de mot.
Sans préfixe. On évite qu’un mot du code soit identique au début
d’un autre mot. Un tel code est qualifié de code instantané.

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 6/1

 Codage de source Codes à longueur fixe

Codes à longueur fixe

Un code de longueur fixe est un code dont tous les mots de code ont
la même longueur.
On peut alors parler de la longueur du code.
Lorsque les éléments encodés sont de même longueur n, le décodage
est simple : on découpe le message codé en mots de taille n, puis on
applique la fonction réciproque de C sur chaque mot.
Pour des raisons d’efficacité, on souhaite construire des codes dont la
longueur est petite.
Néanmoins, il existe une limite théorique à cette longueur, en fonction
de la taille de l’alphabet à coder.

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 7/1

 Codage de source Codes à longueur fixe

Proposition 1
Soit un alphabet X de cardinal K . Il existe un code régulier de X de
longueur n telle que

log2 (K ) ≤ n < 1 + log2 (K ).

De plus, il n’existe aucun code régulier de longueur n < log2 (K ).

Proposition 2
L’efficacité d’un code C de longueur fixe sur X vérifie E (C ) ≤ 1. De plus,
si E (C ) = 1 alors :
|X | est une puissance de 2, et
la loi pX de tirage des lettres est la loi uniforme sur X .

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 8/1

 Codage de source Codes à longueur fixe

Démonstration :
Notons n la longueur de C . On a E (C ) = H(X )/n ≤ log2 (|X |)/n. Comme
n ≥ log2 (|X |) d’après la Proposition 1, on obtient E (C ) ≤ 1. Par ailleurs,
on observe que si E (C ) = 1, alors nécessairement H(X ) = log2 (|X |) et
n = log2 (|X |). La première condition implique que X suit une loi
uniforme, tandis que la seconde impose que |X | soit une puissance de 2.

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 9/1

 Codage de source Codes à longueur fixe

Exemple 2
Soit une source dont l’alphabet est A = {0, 1, . . . , 9} munie de la loi de
probabilité uniforme. On code cette source par une code en longueur fixe
de longueur 4. Par exemple, on peut prendre

L’efficacité du code est H(A)/4 = (log2 (10))/4 ≈ 0.83. Ce code n’est pas
optimal. Il est cependant possible d’améliorer son efficacité en considérant
non plus des chiffres isolés mais des paires de chiffre. Ceci revient à
changer la source A en A2 = {00, 01, ..., 99}. Son cardinal est 100. Cette
nouvelle source reste munie d’une loi de probabilité uniforme et son
entropie vaut H(A2 ) = log2 (100) = 2H(A).

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 10 / 1

 Codage de source Codes à longueur fixe

La puissance de 2 immédiatement supérieure à 100 est 27 = 128. Il existe

donc un code de longueur 7 pour coder cette source. Son efficacité est
cette fois H(A2 )/7 = (2 log2 (10))/7 ≈ 0.95, ce qui est meilleur. En
considérant la source A3 , on obtiendra une efficacité de 0.996. On
améliore ainsi l’efficacité. D’une façon générale, il est possible de
considérer la source A` munie de la loi de probabilité produit, pour ` entier
positif. On a alors H(A` ) = `H(A).

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 11 / 1

 Codage de source Codes à longueur fixe

Proposition 3
Soit A une source cardinal n. Soit A` la source des `-uplets de lettres de
A. Il existe un code de longueur constante m` pour A` tel que
m` 1
log2 n ≤ < + log2 (n).
` `

Démonstration:
D’après la Proposition 1 il existe un code de longueur m` pour A` qui
vérifie
log2 n` ≤ m` < 1 + log2 n` ,
d’où le résultat.

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 12 / 1

 Codage de source Codes à longueur variable

Codes à longueur variable

Contrairement aux codes à longueur fixe, les codes à longueur variable

permettent d’obtenir des codes très efficaces pour une source de
distribution arbitraire. Néanmoins, le décodage d’un code à longueur
variable semble moins aisé : comment découper une séquence de lettres
codées pour ensuite être capable de décoder chaque lettre séparément ?

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 13 / 1

 Codage de source Codes à longueur variable

Définition 4
On dit qu’un code C est uniquement décodable (u.d.) si son codage
associé est injectif.

Définition 5
Un code vérifie la condition du préfixe si aucun mot de code n’est le début
d’un autre mot de code. Autrement dit, si c1 = c2 |x où c1 et c2 sont deux
mots de code, alors c1 = c2 . On dit alors que le code est préfixe.

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 14 / 1

 Codage de source Codes à longueur variable

Proposition 4
Tout code préfixe est uniquement décodable.

Démonstration :
Soit C un code préfixe et considérons x, y ∈ X + tels que C + (x) = C + (y ).
Il faut montrer que x = y . On peut écrire

C + (x) = C (x1 )| . . . |C (xn ) et C + (y ) = C (y1 )| . . . |C (ym )

où x = x1 | . . . |xn et y = y1 | . . . |ym . Supposons, par exemple, que C (x1 )

est plus long que C (y1 ). Alors, C (y1 ) est un préfixe de C (x1 ), donc
C (x1 ) = C (y1 ), ce qui implique que x1 = y1 . En procédent itérativement,
on montre alors que n = m et xi = yi pour tout i ∈ {1, . . . , n}.

La réciproque est fausse : tout code uniquement décodable n’est pas

préfixe. Par exemple, le code sur {a, b} défini par a 7→ 1 et b 7→ 10 est
uniquement décodable (on coupe avant chaque 1), mais il n’est pas préfixe.
Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 15 / 1
 Codage de source Codes à longueur variable

Arbre binaire d’un code.

À tout code binaire préfixe, on peut associer un arbre binaire. Dans cet
arbre, toute feuille porte l’étiquette d’un message, et le mot de code
associé se lit sur l’unique chemin qui mène de la racine à la feuille.

Exemple 5
Reprenons le code de l’Exemple 4. Sa représentation sous forme d’arbre
binaire est la suivante :
Pour décoder un mot de code x1 | . . . |xn , on part de
la racine et à chaque noeud interne, on choisit le de-
scendant suivant la valeur de xi . Par exemple, pour le
mot 001, on part d’abord sur la gauche, de nouveau
sur la gauche, puis sur la droite, pour aboutir à la
lettre d codée par C (d) = 001

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 16 / 1

 Codage de source Codes à longueur variable

Il est clair que la profondeur de l’arbre binaire d’un code correspond à la

longueur maximale d’un mot du code.
Dans le cas des codes de longueur fixe, on a démontré une borne simple
sur la longueur minimale d’un code (Proposition 1). Pour des codes à
longueur variable, on peut également se questionner sur les séquences de
longueurs qui sont admissibles. L’inégalité de Kraft fournit une premier
critère, dans le cas particulier des codes préfixes.
Theorème 1 (Inégalité de Kraft)
Soient n1 , . . . , nk des entiers positifs. Les deux assertions suivantes sont
équivalentes.
1 Il existe un code préfixe à k mots de longueurs respectives n1 , . . . , nk .
2 Les entiers n1 , . . . , nk vérifient
k
X
2−ni ≤ 1.
i=1

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 17 / 1

 Codage de source Codes à longueur variable

Pour démontrer ce théorème, on utilise un résultat auxiliaire portant sur

les longueurs des chemins dans un arbre binaire. D’abord, définissons un
arbre parfait comme un arbre binaire dont toutes les feuilles sont à
distance égale à la racine. Il est clair qu’un arbre parfait dont les feuilles
sont à distance d de la racine possède 2d feuilles.
Lemme 1
Soit T un arbre binaire, dont on note d1 , . . . , dk les longueurs des chemins
menant de la racine aux feuilles. Soit d = max{d1 , . . . , dk } la hauteur de
l’arbre. Alors 2d .
Xk
2d ≥ 2d−di ,
i=1

avec égalité si et seulement si tous les noeuds internes de l’arbre ont 2

descendants (on dit que l’arbre est localement complet).

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 18 / 1

 Codage de source Codes à longueur variable

Démonstration
Construisons un nouvel arbre à partir de T . Pour chaque feuille de T , on
remplace la feuille par un sous-arbre parfait de hauteur d − di (notons que
si d = di , cette modification est inerte). Alors le nombre de feuilles du
nouvel arbre est la somme du nombre de feuilles des k sous-arbres parfaits
ajoutés, c’est-à-dire ki=1 2d−di . Par ailleurs, ce nouvel arbre est de
P
hauteur d, donc contient moins de feuilles que l’arbre parfait de même
hauteur. On obtient donc
k
X
2d ≥ 2d−di .
i=1

Remarquons qu’il y a égalité dans l’équation précédente si et seulement si

l’arbre construit est parfait. Un arbre parfait a des noeuds internes à 2
descendants, et le procédé de construction n’élimine pas les noeuds à 1
descendant. Ainsi, le cas d’égalité se produit si et seulement si l’arbre
d’origine n’a aucun noeud à 1 descendant.

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 19 / 1

 Codage de source Codes à longueur variable

Démonstration de l’inégalité de Kraft

(1 ⇒ 2) Posons n = max{n1 , ..., nk } et considérons l’arbre binaire

associé au code. D’après le lemmePk précédent, si un code est préfixe,
alors ses longueurs vérifient i=1 2n−ni ≤ 2n , et l’on obtient
l’inégalité escomptée en divisant de part et d’autres par 2n .
(2 ⇐ 1) Pour la réciproque, on construit les mots itérativement, par
ordre croissant de longueur. Il est facile de construire le premier (0 . .
. 0 de longueur n1 ). Supposons qu’on ait construit i − 1 mots
c1 , ..., ci−1 de longueurs n1 ≤ . . . ≤ ni−1 vérifiant la condition du
préfixe, et considérons l’arbre binaire associé à ces mots. Pour
construire le i-ème mot, on montre qu’il existe un noeud interne de
l’arbre ayant exactement 1 descendant. Si ce n’était pas le cas, l’arbre
serait localement complet, et d’après le Lemme 1, on aurait alors
2ni−1 = i−1 ni−1 −nj . En multipliant de part et d’autre par 2n−ni−1
P
j=1 2
(où n P = max{n1 , ...,Pnk }), on observe alors une contradiction, car
2n ≥ kj=1 2n−nj > j=1 i−1 n−nj
2 .
Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 20 / 1
 Codage de source Codes à longueur variable

Theorème 2 (Théorème de MacMillan)

Soient n1 , ..., nk des entiers positifs. Les deux assertions suivantes sont
équivalentes.
1 Il existe un code uniquement décodable à k mots de longueurs
respectives n1 , ..., nk .
Les entiers n1 , ..., nk vérifient ki=1 2−ni ≤ 1.
P
2

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 21 / 1

 Codage de source Codes à longueur variable

Démonstration :

Le sens (2 ⇒ 1) est un corollaire du Théorème 1, car un code préfixe

est uniquement décodable. Il reste donc à établir le sens (1 ⇐ 2).
Considérons un code uniquement décodable C de longueurs
n1 ≤ . . . ≤ nk , et pour un entier m ≥ 1, notons

C m := {c = (c1 | . . . |cm ) tel que ci ∈ C }

l’ensemble des séquences binaires obtenues par concaténation

d’exactement m mots de code quelconques. Alors, comme le code est
uniquement décodable, à chaque élément de C m on peut associer un
unique m-uplet de mots de C , donc
k
!m
X X
2−ni = 2−`(c)
i=1 c∈C m

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 22 / 1

 Codage de source Codes à longueur variable

Démonstration :

Par ailleurs, les mots de C m ont pour longueur maximale m · nk , et

pour chaque i ∈ {1, ..., m · nk }, on sait qu’il existe au plus 2i mots de
longueurPi. Par conséquent,
Pm·nen regroupant la somme par longueur on
obtient c∈C m 2 −`(c) ≤ i=1k 2i 2−i = m · nk . Puis :

k
X
2−ni ≤ (m · nk )1/m , m≥1
i=1

En passant à la limite pour m → ∞, on trouve l’inégalité escomptée.

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 23 / 1

 Codage de source Codes à longueur variable

Définition 6
Pk −ni
Un code est complet si la longueur de ses mots vérifie i=1 2 = 1.

Exemple
Le code défini sur X = {a, b, c} par C (a) = 00, C (b) = 01 et C (c) = 1
est complet (2−2 + 2−2 + 2−1 = 1).

Remarquons que, dans la preuve de l’inégalité de Kraft, nous avons établi

le résultat suivant.
Corollaire 1
Un code préfixe est complet si et seulement si les noeuds de son arbre
binaire ont 0 ou 2 descendants.
Après avoir déterminé quelles séquences de longueurs sont possibles pour
un code uniquement décodable, on peut ensuite chercher à borner sa
longueur moyenne.

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 24 / 1

 Codage de source Codes à longueur variable

Proposition 5
Soit X une variable aléatoire sur X . Soit C un code sur X uniquement
décodable. Alors, la longueur moyenne de C vérifie:

H(X ) ≤ E(`(C ))

Démonstration: Pour X = {x1 , . . . , xk }, notons ci = C (xi ) et ni = ` (ci )

pour tout i ∈ {1, . . . , k}. Notons également p = (p1 , . . . , pk ) la
distribution de probabilité de X . L’idée est de construire une autre
distribution
Pde probabilité en fonction des longueurs des mots de codes.
k
Soit Q = i=1 2−ni , on pose alors
2−ni
qi :=
Q
La divergence-KL entre les distributions p et q est positive ou nulle, donc
on obtient
k
X pi
pi log2 ≥0
qi
i=1
Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 25 / 1
 Codage de source Codes à longueur variable

En développant les calculs, on aboutit alors à

k k k k
X X X X 1
H(X ) = − pi log2 pi ≤ − pi log2 qi = pi ni − pi log2 = E(`(C
Q
i=1 i=1 i=1 i=1

car Q ≤ 1 grâce au théorème de MacMillan.

Proposition 6
Soit X une variable aléatoire sur X . Il existe un code sur X uniquement
décodable de longueur moyenne:

E(`(C )) < H(X ) + 1

Démonstration: Soit X = {x1 , . . . , xk } et notons p = (p1 , . . . , pk ). Grâce

à l’inégalité de Kraft, il suffit de construire une séquence de longueurs
n1 , . . . , nk qui vérifient
k k k
X X X 1
2−ni ≤ 1 et pi ni < 1 + pi log2
pi
i=1 i=1 i=1

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 26 / 1

 Codage de source Codes à longueur variable

Notons que les valeurs log2 p14 pourraient satisfaire ces contraintes, mais
elles ne sont pas nécessairement entières. On peut essayer de choisir pour
ni un entier suffisamment proche de log2 p14 pour ne pas contredire la
seconde contrainte, et légèrement supérieur à celui-ci afin de satisfaire la
première. On pose donc  
1
ni := log2 ,
pi
1 1
de telle sorte que log2 pt ≤ ni < log2 p4 + 1. Il s’ensuit que

k
X k
X
2−ni ≤ 2log2 pi = 1
i=1 i=1

et
k k   k k
X X 1 X X 1
pi ni < pi 1 + log2 = pi + pi log2 = 1 + H(X )
pi pi
i=1 i=1 i=1 i=1

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 27 / 1

 Codage de source Codes à longueur variable

Remarque
La preuve de la Proposition 6 fait intervenir l’inégalité de Kraft, dans
laquelle on construit explicitement un code préfixe à partir de sa séquence
de longueurs. Le code obtenu à partir des longueurs ni = d− log2 pi e est
appelé code de Shannon-Fano.

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 28 / 1

 Code de Huffman

L’inégalité de Kraft et le théorème de MacMillan nous donnent un critère

pour évaluer l’existence de codes préfixes et/ou uniquement décodables, en
fonction des longueurs présupposées des mots du code. Si l’on se donne
une distribution de probabilité sur l’apparition des lettres à coder, on peut
alors s’intéresser à la construction du code dont la longueur moyenne des
mots est la plus faible possible.
Définition 7
Étant donnée une source X , on dit qu’un code C est optimal pour X si,
pour tout code C 0 , on a
`(C ) ≤ `(C 0 ).

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 29 / 1

 Code de Huffman

La méthode donnée en preuve de la Proposition 6 construit un code dont

la longueur moyenne est distante d’au plus 1 de la longueur minimale.
Présentons maintenant l’algorithme de Huffman qui permet de construire
un code préfixe optimal. Il prend en entrée la distribution de probabilité
p = (p1 , ..., pk ) et se décrit comme suit.

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 30 / 1

 Code de Huffman

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 31 / 1

 Code de Huffman

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 32 / 1

 Code de Huffman

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 33 / 1

 Code de Huffman

Theorème 3
Le code de Huffman est préfixe et optimal, c’est-à-dire que pour toute
source discrète sans mémoire X , le code de Huffman C associé à X est de
longueur moyenne minimale parmi tous les codes uniquement décodables
sur X .
Pour établir ce théorème, on démontre une série de lemmes intermédiaires.
Lemme 2
Si A est un code préfixe optimal pour X , alors l’arbre binaire de A est
localement complet.

Démonstration : Supposons que l’arbre de A ne soit pas localement

complet. Alors il existe un noeud interne i de cet arbre qui n’a qu’un seul
descendant. Considérons le sous-arbre T dont la racine est l’unique
descendant de T . Si l’on remplace i par Ti , on obtient l’arbre d’un code
sur X . De plus, ce code a une longueur moyenne strictement plus petite
que celle de A, puisque qu’on a raccourci les longueurs de tous les mots
représentés par des feuilles de T . C’est en contradiction avec l’optimalité
de A.
Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 34 / 1
 Code de Huffman

Lemme 3
Si A est un code optimal, alors les symboles les moins fréquents codés par
A sont de longueur maximale parmi les mots de A.

Démonstration : Supposons qu’il existe deux mots A(x) et A(y ) tels que
`(A(x)) > `(A(y )) et p(x) > p(y ). Alors, le code A0 tel que
A0 (x) = A(y ), A0 (y ) = A(x) et A0 (z) = A(z) pour tout autre symbole z, a
une longueur moyenne strictement plus petite que celle de A, ce qui en
contredit l’optimalité.
Lemme 4
Si T est l’arbre binaire d’un code préfixe, alors échanger des feuilles de
même niveau sur l’arbre ne modifie pas la longueur moyenne de l’arbre.

Démonstration : C’est clair.

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 35 / 1

 Code de Huffman

Lemme 5
Considerons deux sources X et X 0 , definies respectivement sur
X = {x1 · · · , xm } et X 0 = X ∪ {xm+1 }. On suppose que la loi p 0 de X 0
satisfait p 0 (x1 ) ≥ p(x2 ) ≥ · · · ≥ p 0 (xm+1 ),et que la loi p vérifier
p 0 (xi ) = p(xi ) pour tout i ∈ {1, · · · , m − 1} et p 0 (xm ) + p 0 (xm+1 ) vérifie
p 0 (xi ) = p(xi ) pour tout i ∈ {1, · · · , m − 1} et
p 0 (xm ) + p 0 (xm+1 ) = p(xm ). où X 0 est obtenu à partir de C par le procede
suivant : C 0 (xi = C (xi ) si i ≤ m − 1, C 0 (xm ) = C (xm )|0, et
C 0 (xm+1 ) = C (xm )|1, est de longueur moyenne minimale pour X 0 .

Démonstration: Supposons qu’il existe un code A0 tel que `(A0 ) < `(C 0 ).
On peut d’abord supposer que A0 est préfixe, car d’après l’inégalité de
Kraft et le théorème de MacMillan, pour tout code il existe un code préfixe
partageant la même séquence de longueur. On peut également supposer
que dans A0 , les encodages des deux symboles les moins fréquents de X 0
diffèrent seulement sur leur dernier bit, d’après les Lemmes 2, 3 et 4. On
peut donc écrire A0 (xm ) = a|0 et A0 (xm+1 ) = a|1, pour un certain mot a.
Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 36 / 1
 Code de Huffman

Construisons alors le code A sur X à partir de A0 par le procédé inverse de

celui qui mène de C 0 à C :

A(xi ) = A0 (xi ) pour i 6 m − 1 et A(xm ) = a.

Notons alors que les longueurs moyennes de C et C 0 different de

m+1
X m
X
¯ 0 ) − `(C ) =
`(C p 0 (xi )`(C 0 (xi )) − p(xi )`(C (xi ))
i=1 i=1
= p 0 (xm )`(C 0 (xm )) + p 0 (xm+1 )(C 0 (xm+1 )) − p(xm )`(C (xm ))
= (p 0 (xm ) + p 0 (xm+1 ))(1 + `(C (xm ))) − p(xm )`(C (xm ))
= p(xm )

¯ 0 ) − `(A) = p(xm ).Par consequent,

De manière similaire, on a aussi `(A
0 0
`(A) = `(A ) + `(C ) − `(C ) < `(C ) ce qui contredit I’optimalite de C .

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 37 / 1

 Code de Huffman

Demonstration du Theoreme 3:
Le résultat se montre par récurrence sur le nombre de symboles de la
source. Il est clair que pour k = 2 éléments, le code obtenu par
l’algorithme d’Huffman est optimal. Fixons maintenant k ≥ 3, ainsi qu’une
source X 0 à k éléments, et supposons que l’alorithme d’Huffman produit un
code optimal pour toute source à moins de k − 1 élements. On remarque
que, si p est la distribution de X 0 , alors l’algorithme d’Huffman construit
q, la distribution de probabilité de la source X donnée dans l’énoncé du
Lemme 5. Par hypothèse de récurrence, l’appel Huffman(q, k − 1)
construit un code optimal C pour la source X . Grâce au Lemme 5, on
déduit que la dernière étape de l’algorithme préserve l’optimalité du
nouveau code ainsi construit sur X 0 . Ceci conclut la preuve par récurrence.

Mourad NACHAOUI (ENSA de Khouribga) Théorie d’infromation April 3, 2023 38 / 1