Chapitre 2.

Codage de source
Mohamed Lassad AMMARI & Iheb Brini

1
Content
1. Motivation et exemples
2. Codage d'un alphabet discret
3. Codes à longueur fixe
4. Codes à longueur variable
5. Codage entropique

2
Introduction
Le codage de source, aussi appelé compression de données, a pour objectif de représenter les messages
générés par une source d'information sous forme de symboles appartenant à un alphabet D-aire. Cela
consiste à attribuer à chaque message un mot de code spécifique, permettant une représentation
condensée de l’information.

Dans ce chapitre, nous étudions le codage d'une source discrète sans mémoire en une séquence binaire
(D = 2). Ce codage s’effectue en supposant que le canal de communication est non bruité, garantissant
ainsi que le destinataire reçoive une copie exacte de l’information émise par l’encodeur.

Le chapitre met également en lumière l'importance d'un codage efficace, c’est-à-dire d’un codage qui utilise
le nombre minimal de bits pour représenter chaque message, optimisant ainsi l’usage des ressources de
transmission et de stockage.

3
Motivation et Exemples
Lorsque l’information est destinée à la transmission, un codage efficace assure une transmission
rapide. En revanche, pour l’information destinée au stockage, un codage optimisé permet de réduire
l’espace de stockage (disque ou mémoire) requis. Nous distinguons deux principaux types de compression
:

1. Compression sans perte : Elle permet de retrouver exactement le contenu d'origine après décodage.
Elle est couramment utilisée pour compresser des documents, fichiers exécutables ou textes (ex. ZIP).

4
 2. Compression avec perte : Entraînant une perte d'information, les messages décodés diffèrent
légèrement des originaux. Utilisée fréquemment pour des images (JPEG), du son et des vidéos (MPEG).

Dans ce chapitre, nous focaliserons sur la compression sans perte. L'efficacité du codage de source repose
largement sur la fréquence statistique des messages. Pour minimiser le nombre de bits, il est possible
d’attribuer des mots de code courts aux messages les plus courants, formant ainsi des codes à longueur
variable, où les longueurs des mots de code varient.

5
Exemples historiques de codage :

Code Morse (1832, Samuel Morse) : l'un des premiers codes de source, caractérisé par des mots de code
de longueur variable. Par exemple, la lettre “E” (très fréquente) est représentée par “·”, tandis que “Q”
(rare) est codée par “−−·−”. Les lettres les plus fréquentes occupent des positions supérieures dans
l’arbre de codage de Morse, avec l’ajout d’un séparateur pour éviter toute ambiguïté.

Fig 1. Le code morse

6
Fig 2. Arbre de construction du code de Morse

Code ASCII : Chaque caractère est représenté par un code à longueur fixe de 8 bits. Le décodage
s’effectue ainsi sans ambiguïté ni confusion, garantissant une clarté immédiate lors de l'interprétation
des données.

7
Codage d’un Alphabet Discret
Position du Problème
Le codage de source binaire vise à attribuer à chaque message (ou suite de messages) en sortie de source
un mot de code binaire (voir Fig 3). L’objectif est de concevoir un codeur de source efficace répondant aux
critères suivants :

1. Les mots de code doivent être en format binaire.

2. Les mots de code doivent être aussi courts que possible, optimisant l’espace et la transmission.

8
 3. Chaque mot de code doit pouvoir être décodé de manière unique : la séquence émise doit permettre
de reconstruire parfaitement la séquence d’origine.

Fig 3. Codage de source

9
Notations
Considérons une source discrète . Les notations suivantes sont utilisées :

: l’ensemble des “l”-uplets de .

: l’ensemble des séquences finies non vides de .
: l’ensemble des séquences binaires finies.

10
Définition : Code de Source
Un code de source pour est défini comme une fonction , où est un alphabet contenant
D symboles. On note :

: le mot de code associé à un élément .

: la longueur du mot de code .

11
Remarques
Le terme mot de code désigne tout élément .
Dans le cas du codage binaire (objectif principal de ce chapitre), on a .
L’ensemble de tous les mots de code, , est donné par :

12
Exemple :

Pour une source et un alphabet binaire , nous pouvons coder les éléments de
comme suit :

13
Définition (Longueur moyenne) :

Pour une source avec une probabilité et un code de source , la longueur moyenne du code
, notée , représente le nombre moyen de bits utilisés pour coder un symbole de la source :

où est la longueur du mot de code associé à .

14
Définition : Efficacité d'un Code
Pour une source discrète d’entropie et un code de source de longueur moyenne , l’efficacité
du code est définie par :

15
Exemple : Calcul de l’Efficacité d'un Code
Pour une source ayant les probabilités suivantes et les mots de code associés :

, avec
, avec
, avec
, avec

16
Solution
Calculons :

Entropie : bits
Longueur moyenne : bits
Efficacité :

Chaque séquence binaire se décode de manière unique. Par exemple, la séquence se

décode en 134213.

17
Exemple : Codage de Source
Considérons une source avec la distribution de probabilité suivante et les mots de code associés :

, avec
, avec
, avec

18
Solution :

1. Entropie :
bits.

2. Longueur moyenne du code :

bits.

3. Efficacité du code :
.

L'efficacité du code, étant proche de 1, indique que le codage est quasi optimal, bien qu'il soit légèrement
inférieur à l'entropie de la source.

19
Définition : Code binaire étendu
Soit un code de source binaire pour la source . Le code étendu est une fonction qui associe à
chaque séquence de symboles de une séquence binaire obtenue par la concaténation des mots de code
correspondants. Plus précisément :

Ce code est également appelé extension du code .

20
Propriétés souhaitées d’un code
Définition : Code régulier ou non-singulier
Un code est qualifié de régulier si la fonction est injective, c'est-à-dire que des symboles distincts et
sont représentés par des mots de code distincts. Autrement dit :

Cela garantit la première propriété fondamentale d'un code : la capacité à retrouver un symbole à partir
de son mot de code .

21
Exemple
Prenons un alphabet et définissons un code qui associe à chaque symbole un mot de
code binaire :

Ici, chaque symbole , et a un mot de code distinct. Le code est donc injectif (non-singulier), car :

,
,
.

Aucun symbole distinct n'a le même mot de code, ce qui respecte la condition d'injectivité de la fonction
.

22
Définition : Code uniquement décodable (ou déchiffrable)
Un code est uniquement décodable si son code étendu est injectif. En d'autres termes, pour deux
séquences de symboles distinctes et :

Cela signifie qu'il est possible de distinguer les mots de code dans une séquence et de retrouver sans
ambiguïté les messages .

23
Méthodes pour garantir un code uniquement décodable
Pour s’assurer d’un décodage sans ambiguïté, on peut adopter l’une des trois approches suivantes :

1. Code à longueur fixe (comme le code ASCII).

2. Séparateurs entre les mots de code (ce qui augmente la taille des données).
3. Codes sans préfixes, où aucun mot de code n’est le début d’un autre mot.

Dans le reste de ce chapitre, nous examinerons les propriétés des codes à longueur fixe et des codes à
longueur variable, en démontrant que ces derniers sont plus efficaces en termes de performance de
codage.

24
Codes à longueur fixe
Définition : Codes à longueur fixe
Un code à longueur fixe est un code dans lequel chaque mot de code possède la même longueur.

Théorème
Pour une source discrète avec un alphabet de taille , il existe un code régulier de longueur fixe tel
que :

Aucun code régulier de longueur fixe ne peut avoir une longueur .

25
D'après le Théorème précedente, . Étant donné que et que la longueur
moyenne , on obtient :

Cette égalité n'est atteinte que lorsque les deux conditions suivantes sont remplies :

1. , c’est-à-dire que les symboles sont équiprobables.

2. , c’est-à-dire que est une puissance de 2.

26
Exemple : Code à longueur fixe
Considérons une source avec un alphabet et une probabilité uniforme. Prenons le
code à longueur fixe suivant :

Lettre Mot de code Lettre Mot de code

0 0000 6 0110

1 0001 7 0111

2 0010 8 1000

3 0011 9 1001

4 0100

5 0101

27
Calcul de l’efficacité du code et amélioration
L’efficacité de ce code est :

Cette efficacité étant bien inférieure à 1, elle peut être améliorée en codant par paires de chiffres. Dans ce
cas, l’alphabet devient , avec un cardinal . Comme la source est sans
mémoire, reste uniforme :

28
Pour un alphabet de taille 100, un code de longueur peut être utilisé, et l’efficacité devient :

Le codage par paires, comme dans cet exemple, est une forme de codage par bloc, où les symboles sont
groupés par blocs de pour améliorer l’efficacité.

29
Soit un alphabet de cardinal . De façon générale, soit un code de longueur fixe pour la
l’alphabet . Nous savons que :

Ce code permet d’obtenir une longueur moyenne par symbole :

Ainsi, en augmentant , on obtient , et pour une source uniforme (quand

), l’efficacité peut atteindre 1. Pour les sources non uniformes, cette efficacité n’est pas
possible avec des codes à longueur fixe.

30
Codes de longueur variable
Pour obtenir un code de longueur fixe avec une efficacité égale à 1, il est nécessaire que les symboles
soient équiprobables et que le cardinal de la source soit une puissance de 2. L’extension de la source (ou
codage en bloc) peut améliorer cette efficacité. Cependant, lorsque les symboles ne sont pas
équiprobables, cette technique ne permet pas d’atteindre une efficacité proche de 1. D’où l’idée du codage
à longueur variable. Ce principe consiste à attribuer des mots de code courts aux symboles fréquents et
des mots de code plus longs aux symboles moins utilisés. Contrairement aux codes de longueur fixe, les
codes de longueur variable posent un problème au décodage.

31
Codes sans préfixe
Définition (Codes sans préfixe) :
Soit un code pour la source . est dit un code sans préfixe si aucun mot de code n’est le
début d’un autre mot de code :

Les codes sans préfixe sont aussi appelés codes instantanés ou codes autoponctués. Parfois, ils sont
désignés comme codes préfixes dans certains ouvrages.

32
Exemple
Considérons une source avec l'alphabet et un code binaire qui encode les symboles de
cette source. Un exemple de code sans préfixe pourrait être :

Ici, les mots de code sont :

0 pour le symbole ,
10 pour le symbole ,
11 pour le symbole .

33
Vérification de la propriété de code sans préfixe
Pour vérifier que ce code est sans préfixe, nous devons nous assurer que aucun mot de code n'est le début
d'un autre mot de code.

Le mot 0 (pour ) n'est pas le début de 10 (pour ) ni de 11 (pour ).

Le mot 10 (pour ) n'est pas le début de 11 (pour ).
Le mot 11 (pour ) n'est pas le début de 10 (pour ).

Dans cet exemple, il n'y a pas de mot de code qui commence un autre mot de code, donc ce code respecte la
condition des codes sans préfixe.

34
Importance des codes sans préfixe
Les codes sans préfixe sont utilisés dans des applications où le décodage doit être immédiat et sans
ambiguïté. Un exemple classique est le code de Huffman, qui est un code optimal pour la compression de
données, et qui est toujours un code sans préfixe. Grâce à cette propriété, le décodeur peut simplement lire
un flux de bits et décider de la fin d'un mot de code dès qu'il rencontre un mot complet.

35
Proposition
Tout code sans préfixe est uniquement décodable.

La propriété d'absence de préfixe assure un décodage unique, mais ce n'est pas une condition
indispensable, car certains codes uniques ne sont pas sans préfixe. Les codes sans préfixe permettent un
décodage instantané dès que les mots de code sont disponibles.

36
Exemple (Classification des codes) :
Considérons les codes suivants :

Symboles I B F O

Code 1 01 1 00 1

Code 2 1 00 01 10

Code 3 0 01 011 111

Code 4 0 10 110 111

37
1. Code 1 : Code non régulier.
2. Code 2 : Code régulier mais non uniquement décodable. Par exemple, le mot "BOF" peut être codé par
001001, ce qui peut être interprété comme "BIBI".
3. Code 3 : Code uniquement décodable mais non instantané. Prenons la séquence 01111011. Si l'on
commence par interpréter les 4 premiers bits comme "0 111", les bits suivants peuvent être interprétés
comme "1", "10" ou "101", mais ces interprétations sont incohérentes. Il faut revenir en arrière pour
corriger l'interprétation et obtenir le message correct, ce qui montre que ce code n'est pas instantané.
4. Code 4 : Code sans préfixe (instantané).

38
Proposition
Pour tout code sans préfixe, il existe un arbre de codage dont les mots de code correspondent aux feuilles
de l'arbre. Cette condition est nécessaire et suffisante.

Les caractéristiques de cet arbre sont les suivantes :

Chaque branche de l'arbre porte l'attribut 0 ou 1 (avec 0 indiquant un déplacement à gauche et 1

un déplacement à droite, ou l'inverse).
Deux branches partant d'un même nœud doivent avoir des attributs différents.
Chaque nœud est étiqueté par la concaténation des bits qui le relient à la racine.
L'ordre d'une feuille ou d'un nœud est défini comme le nombre de branches le séparant de la racine.

39
Exemple (Représentation des codes sans préfixe par des arbres) :
La Fig. suivante présente un exemple de code sans préfixe représenté par un arbre de codage.

Fig 5. Arbre de codage

40
Proposition
À chaque niveau n, le nombre maximal de mots de code est .

Lemme
Le nombre de séquences binaires distinctes de longueur inférieure ou égale à n est donné par :

Ce lemme donne le nombre total de séquences binaires distinctes de longueur allant de 1 à . Chaque
séquence binaire est un mot de code composé de bits.

Pour les séquences de longueur 1, il y a possibilités (les mots 0 et 1).

Pour les séquences de longueur 2, il y a possibilités.
Pour les séquences de longueur 3, il y a possibilités.
Et ainsi de suite jusqu'à la longueur .

Le nombre total de séquences distinctes de longueur est donc la somme de ,

ce qui peut être exprimé comme une somme géométrique :

41
Exemple :
Pour , le nombre total de séquences binaires distinctes de longueur est :

Cela signifie qu'il y a 14 séquences binaires distinctes de longueur .

42
Lemme
Dans un arbre binaire, le nombre de descendants d'un nœud situé au niveau m pour est .

Dans un arbre binaire, chaque nœud peut avoir deux descendants. La fonction descendants fait référence à
tous les nœuds qui se trouvent sous un nœud donné à un certain niveau .

Si vous avez un nœud à un certain niveau dans l'arbre et que vous voulez savoir combien de nœuds
se trouvent sous lui, la réponse dépend de la profondeur de l'arbre.
À partir d'un nœud situé au niveau , le nombre de descendants est car chaque niveau de l'arbre
binaire double le nombre de nœuds descendants.

43
Exemple :
Si et que le nœud se trouve au niveau , le nombre de descendants est .
Si et que le nœud se trouve au niveau , le nombre de descendants est .

44
Lemme
Dans un arbre binaire représentant un code , si n'est pas un préfixe de , alors les descendants
de et sont disjoints.

Ce lemme repose sur la propriété des codes sans préfixe (ou codes instantanés), où aucun mot de code ne
peut être le début d'un autre mot de code.

Dans un arbre binaire de codage, chaque mot de code correspond à un chemin dans l'arbre. Le préfixe
d'un mot de code est simplement le début du mot, et un mot de code est un préfixe d'un autre si le
premier mot est une séquence initiale du second.
Si n'est pas un préfixe de , cela signifie que les chemins menant à et dans l'arbre sont
distincts. Par conséquent, leurs descendants (les nœuds situés sous et ) sont disjoints, c'est-à-dire
qu'il n'y a pas de partage de nœuds entre les deux chemins.

45
Exemple :
Si et , alors est un préfixe de , et les descendants de et se croiseraient.
Si et , alors et ne sont pas des préfixes l'un de l'autre, et leurs descendants sont
disjoints.

46
Théorèmes de Kraft et de McMillan
Théorème (Inégalité de Kraft)
Soit une source discrète et un code sans préfixe binaire (ou code instantané) pour . Les
longueurs des mots de code doivent satisfaire l'inégalité de Kraft suivante :

Réciproquement, si un ensemble de mots de code vérifie cette inégalité, il est possible de construire un code
instantané à partir de ces mots.

47
Interprétation :

: la longueur du mot de code pour le symbole ,

: la probabilité associée au mot de code (dans un certain sens),
La somme représente la "charge" totale des mots de code dans l'ensemble.

L'inégalité de Kraft nous donne une condition nécessaire pour qu'un ensemble de mots de code forme un
code sans préfixe. Si cette inégalité est vérifiée, il existe toujours un arbre binaire dans lequel chaque mot
de code correspond à un chemin dans l'arbre. Cela garantit qu'il n'y a pas de mots de code qui soient les
préfixes d'autres mots de code.

La réciproque de cette condition est également vraie : si un ensemble de mots de code satisfait cette
inégalité, il est possible de construire un code sans préfixe. En d'autres termes, l'inégalité de Kraft est
une condition caractéristique pour l'existence d'un code instantané.

48
Exemple de l'Inégalité de Kraft

Considérons un ensemble de mots de code pour un alphabet , et supposons que les

longueurs des mots de code soient données par , , et . Nous avons donc les mots de
code :

(longueur ),
(longueur ),
(longueur ).

49
Vérification de l'inégalité de Kraft :

Calculons la somme suivante pour vérifier si l'inégalité de Kraft est satisfaite :

Comme , l'inégalité de Kraft est satisfaite.

Cela signifie qu'il est possible de construire un code sans préfixe pour ces mots de code, et que ce code est
décodable de manière unique.

Conclusion :

L'inégalité de Kraft est un résultat fondamental en théorie du codage. Elle fournit une condition
nécessaire et suffisante pour l'existence de codes sans préfixe.

50
Théorème (Inégalité de McMillan)
Soit une source discrète et un code binaire uniquement décodable pour , les longueurs
des mots de code doivent satisfaire l'inégalité de McMillan suivante :

Réciproquement, étant donné un ensemble de mots de code qui vérifient cette inégalité, il est possible de
construire un code binaire uniquement décodable à partir de ces mots de code.

51
Interprétation de l'Inégalité de McMillan

Cette inégalité impose une condition sur la somme des inverses des puissances de 2 des longueurs des
mots de code. Contrairement à l'inégalité de Kraft, qui est plus strictement associée aux codes sans préfixe,
l'inégalité de McMillan s'applique à un plus large éventail de codes, y compris ceux qui peuvent avoir des
préfixes. Cependant, pour qu'un code soit uniquement décodable, il doit tout de même satisfaire cette
condition. Cette inégalité garantit qu'il existe suffisamment de "place" dans l'espace binaire pour que chaque
séquence de mots de code soit décodée de manière unique.

52
Réciproque

Réciproquement, étant donné un ensemble de mots de code qui vérifient l'inégalité de McMillan, il est
possible de construire un code binaire uniquement décodable à partir de ces mots de code. Autrement dit,
si les longueurs des mots de code vérifient cette condition, il existe un algorithme (comme l'algorithme de
decodage par arbre binaire) permettant de décoder les messages de manière unique, même si les mots de
code peuvent avoir des préfixes.

53
Exemple de l'Inégalité de McMillan

Prenons un ensemble de symboles avec les mots de code suivants et leurs longueurs
respectives :

(longueur ),
(longueur ),
(longueur ),
(longueur ).

54
Vérification de l'Inégalité de McMillan

Les longueurs des mots de code sont , , , et . Calculons la somme de :

Cela donne :

L'inégalité de McMillan est vérifiée puisque :

55
Remarques :

Les théorèmes de Kraft et de McMillan ne sont pas constructifs. Ils garantissent que, pour des
longueurs de mots de code vérifiant l'inégalité, il est possible de construire des codes instantanés (ou
uniquement décodables), mais ils ne fournissent pas la méthode de construction concrète.
Les théorèmes de Kraft et de McMillan peuvent être généralisés au cas non binaire, c'est-à-dire dans le
cadre d'un codage utilisant symboles (par exemple, en binaire ):

56
Différences entre le théorème de Kraft et le théorème de McMillan :

1. Type de code :
Kraft : S'applique aux codes sans préfixe (codes instantanés), où aucun mot de code n'est le préfixe
d'un autre.
McMillan : S'applique aux codes binaires uniquement décodables, qui peuvent contenir des
préfixes, mais doivent être décodables de manière univoque.

57
2. Condition d'inégalité :

Les deux théorèmes utilisent une somme de puissances de 2 des longueurs de mots de code,
mais la Kraft est plus stricte, car elle ne permet pas de préfixes, tandis que McMillan autorise les
préfixes tant que l'ensemble reste décodable.

3. Réciproque :

Si l'inégalité de Kraft est vérifiée, il est possible de construire un code sans préfixe.
Si l'inégalité de McMillan est vérifiée, il est possible de construire un code uniquement décodable,
même avec des préfixes.

58
Corollaire :
Si un code à décodage unique existe avec mots de code de longueurs , alors il existe
également un code sans préfixe avec les mêmes longueurs .

59
Le corollaire que vous mentionnez découle des théorèmes de Kraft et de McMillan, et il fait référence à
l'idée que si un code est uniquement décodable (même s'il a des préfixes), il est toujours possible de
construire un code sans préfixe avec les mêmes longueurs de mots de code.

L'idée principale de ce corollaire est la suivante :

Si vous avez un code à décodage unique avec des mots de code de longueurs , cela
signifie que la condition de McMillan est vérifiée.
Le corollaire vous dit qu'il est possible de construire un code sans préfixe avec exactement les mêmes
longueurs de mots de code. Cela est possible grâce à l'inégalité de Kraft, qui est plus stricte que celle de
McMillan, mais qui garantit aussi l'existence d'un code sans préfixe si la condition de McMillan est
satisfaite.

60
Exemple :

Prenons un alphabet et considérons les longueurs des mots de code suivantes : ,

, et .

Supposons que ces mots de code soient donnés comme suit :

(longueur ),
(longueur ),
(longueur ).

61
Vérification de l'unicité du décodage :
Les mots de code sont distincts et respectent l'inégalité de McMillan, car :

Ce code est donc uniquement décodable, ce qui signifie qu'il est possible de reconstruire un message à
partir de cette séquence de mots de code de manière univoque, sans ambiguïté.

62
Définition (Code complet) :
Soit une source discrète et un code binaire pour . Le code est dit complet si et
seulement si les longueurs des mots de code vérifient l'égalité suivante :

63
Lemme :
Soit une source discrète avec la loi de probabilité . Il existe un code sans
préfixe dont les longueurs des mots de code sont données par :

où représente la partie entière supérieure de , c'est-à-dire le plus petit entier tel que .

64
Cela signifie que pour chaque symbole de la source, le mot de code associé a une longueur qui est
proportionnelle à l'inverse du logarithme de sa probabilité. Plus la probabilité d'un symbole est élevée, plus
le mot de code associé est court.

Démonstration du Lemme :

Il s'agit de vérifier que les longueurs de mots de code données par satisfont l'inégalité
de Kraft pour un code sans préfixe.

Nous devons vérifier que :

65
1. Expression des longueurs de code :
Selon la définition, , ce qui signifie que :

Donc, pour chaque , on a :

66
2. Vérification de l'inégalité de Kraft :
Nous devons vérifier que :

Comme , nous avons :

67
Par conséquent, la somme des termes est au plus égale à la somme des probabilités :

Cela montre que l'inégalité de Kraft est satisfaite, ce qui prouve qu'il existe un code sans préfixe dont les
longueurs des mots de code sont données par .

68
Premier théorème fondamental de Shannon
Théorème (Borne inférieure de la longueur moyenne des codes instantanés)
Soit une source discrète sans mémoire avec une entropie , et une loi de
probabilité pour chaque symbole . Si est un code sans préfixe (ou code instantané)
pour , alors la longueur moyenne du code vérifie l'inégalité suivante :

avec égalité si et seulement si , où est la longueur du mot de code .

69
Démonstration :
La démonstration repose sur la comparaison entre la longueur moyenne du code et l'entropie
. On commence par exprimer la différence .

1. Définition de l'entropie et de la longueur moyenne :

L'entropie est donnée par :

La longueur moyenne du code est :

où est la longueur du mot de code associé au symbole .

70
2. Calcul de la différence :
Nous calculons maintenant la différence entre et :

En réécrivant comme , nous obtenons :

71
3. Simplification de l'expression :
Nous pouvons regrouper les termes et utiliser les propriétés du logarithme :

72
 4. Inégalité de Kraft et conclusion :
En utilisant l'inégalité de Kraft (qui garantit que la somme des termes pour un code sans préfixe est
inférieure ou égale à 1), nous obtenons :

Cela montre que , et que l'égalité est atteinte si et seulement si , c'est-à-dire que la
longueur du mot de code est exactement déterminée par la probabilité du symbole selon la relation
.

73
Remarque :
Le théorème reste valable pour les codes uniquement décodables (d'après l'inégalité de McMillan), ce qui
signifie que la borne inférieure sur la longueur moyenne du code s'applique également à ces codes.

74
Théorème (Borne supérieure de la longueur moyenne des codes instantanés)
Soit une source discrète sans mémoire avec une entropie . Il existe un
code sans préfixe dont la longueur moyenne du code vérifie la borne supérieure suivante :

75
Démonstration :
Pour démontrer ce théorème, nous allons montrer qu'il existe un code dont la longueur moyenne respecte
l'inégalité donnée.

1. Longueur moyenne du code par rapport au lemme :

D'après le Lemme, la longueur du mot de code pour chaque symbole est donnée par :

Cela donne une longueur moyenne du code égale à :

76
2. Estimation de la somme :

En utilisant la propriété de la fonction (partie entière supérieure), on peut estimer :

Ainsi, la longueur moyenne du code devient :

77
Le premier terme est l'entropie de la source , et le deuxième terme est égal à 1 (car la somme des
probabilités est 1). Par conséquent :

Cela prouve que la longueur moyenne du code est inférieure à .

78
 3. Conclusion :

Nous avons donc montré que :

Ce qui établit la borne supérieure pour la longueur moyenne des codes instantanés.

Remarque :
Le théorème est aussi valide pour les codes uniquement décodables (d'après l'inégalité de McMillan).

79
Conclusion générale des bornes :

D'après le théorème de la borne inférieure et le théorème de la borne supérieure, nous pouvons

conclure qu'il est possible de construire un code sans préfixe (ou uniquement décodable) dont la longueur
moyenne est bornée par :

Cela implique que l'efficacité de ce code, définie comme le ratio entre l'entropie et la longueur
moyenne, est bornée par :

Cela montre que l'efficacité est toujours inférieure à 1, mais il n'est pas garanti que l'efficacité atteigne 1.
Toutefois, pour obtenir une efficacité proche de 1, il est nécessaire d'utiliser des codes par blocs, comme
dans le cas des codes à longueur fixe.

80
Théorème (Premier théorème fondamental de Shannon)
Pour toute source discrète sans mémoire, il existe un code en bloc uniquement décodable dont
l’efficacité est arbitrairement proche de 1.

Autrement dit, pour toute source discrète sans mémoire , et pour tout , il existe un codage en bloc
uniquement décodable, tel que l’efficacité soit strictement supérieure à , ce qui revient à
dire :

où est la longueur moyenne du code en bloc, et est l'entropie de la source.

81
Démonstration :
1. Définition du codage en bloc :
Considérons des blocs de taille de symboles issus de la source (où est l'alphabet de la
source). Ce sont des séquences de symboles, et nous appliquons un code en bloc uniquement
décodable à ces blocs. Pour une source sans mémoire, les symboles sont i.i.d. (indépendants et
identiquement distribués).

2. Entropie d'un bloc de symboles :

L'entropie d'une source sans mémoire est la quantité d'information moyenne par symbole. Pour
un bloc de symboles, l'entropie totale du bloc est simplement fois l'entropie d'un symbole
individuel, soit :

82
3. Application des bornes sur la longueur moyenne du code :
D'après les théorèmes des bornes pour les codes uniquement décodables (comme dans le cas des
codes de Huffman ou d'autres méthodes optimales), on sait que la longueur moyenne du code
pour un bloc de symboles satisfait :

Cela signifie que la longueur moyenne du code pour un bloc de symboles est proche de l'entropie du
bloc, à savoir , avec une petite erreur d'au plus 1 bit.

83
4. Longueur moyenne par symbole :
En divisant la longueur moyenne par le nombre de symboles , on obtient la longueur
moyenne par symbole pour le code en bloc :

En appliquant la borne ci-dessus, on a :

Cela montre que la longueur moyenne par symbole est inférieure à .

84
5. Efficacité du code en bloc :
L'efficacité d'un code est définie comme le ratio entre l'entropie de la source et la longueur
moyenne par symbole du code :

D'après la borne sur , nous avons :

85
En simplifiant cette expression, on obtient :

En choisissant un suffisamment grand, nous pouvons rendre aussi petit que nous le
souhaitons. Ainsi, pour tout , il existe un suffisamment grand tel que :

86
6. Conclusion :
Nous avons ainsi montré qu'il est possible de construire un code en bloc uniquement décodable
dont l'efficacité est strictement supérieure à , ce qui implique que la longueur moyenne de ce
code satisfait :

Cela prouve le Premier théorème fondamental de Shannon.

87
Remarque :
Ce théorème montre que, bien que l'efficacité des codes instantanés (codes sans préfixe) soit bornée par
, il est possible d'obtenir des codes en bloc avec une efficacité qui peut être arbitrairement
proche de 1, ce qui signifie que l'on peut construire des codes dont la longueur moyenne par symbole est
très proche de l'entropie de la source.

Ce résultat est fondamental en théorie du codage, car il montre que la compression optimale (en termes de
longueur moyenne de code) est atteignable avec des codes en bloc, bien que la construction pratique de tels
codes nécessite des méthodes spécifiques (comme les codes de Shannon-Fano, Huffman, ou
Arithmétique).

88
Codage Entropique
Le codage entropique est une méthode de compression qui exploite les propriétés statistiques d'une
source pour que la longueur moyenne du code se rapproche de l'entropie de la source. Cette technique
repose sur l'analyse préalable des données pour attribuer à chaque symbole un code dont la longueur varie
en fonction de sa probabilité d'occurrence. Un symbole ayant une probabilité élevée reçoit un code court,
tandis qu'un symbole peu probable reçoit un code plus long.

Dans cette section, nous présentons deux techniques de codage entropique populaires : le codage de
Shannon-Fano et le codage de Huffman.

89
Définition : Code optimal
Un code uniquement décodable (c'est-à-dire un code dans lequel aucun code ne peut être interprété
comme un préfixe d'un autre code) d'une source est dit optimal si et seulement si il n'existe aucun autre
code uniquement décodable dont la longueur moyenne soit strictement inférieure à la longueur
moyenne du code optimal.

90
Codage de Shannon-Fano
Le codage de Shannon-Fano est une méthode simple de codage entropique qui consiste à attribuer des
codes binaires aux symboles en fonction de leurs probabilités. L'algorithme suit les étapes suivantes :

91
Algorithme de Shannon-Fano :
1. Trier les symboles de la source par probabilité décroissante.

2. Diviser les symboles en deux sous-groupes ayant des probabilités cumulées aussi proches que
possible.

3. Affecter les bits : Attribuer le symbole binaire "0" au groupe de symboles ayant la probabilité cumulée
la plus élevée, et le symbole binaire "1" au groupe ayant la probabilité cumulée la plus faible.

4. Répéter le processus pour chaque sous-groupe afin d'attribuer les bits suivants, jusqu'à ce que tous les
symboles de la source aient été codés.

Ce processus génère un code à longueur variable où les symboles les plus probables sont associés à des
codes plus courts, tandis que les symboles moins fréquents ont des codes plus longs.

92
Exemple (Codage de Shannon-Fano)
Considérons la source avec les probabilités suivantes :

93
1. Trier les symboles par probabilité décroissante :

94
2. Diviser en deux sous-groupes :
Premier groupe : avec une probabilité cumulée de .
Deuxième groupe : avec une probabilité cumulée de
.

95
3. Attribuer les premiers bits :

reçoivent le bit "0".

reçoivent le bit "1".

4. Répéter pour chaque sous-groupe :

Pour le groupe , nous avons , . On divise encore en deux sous-groupes :

(probabilité ), et (probabilité ).
Pour le groupe , nous avons , , , . On divise
aussi en deux sous-groupes :
(probabilité ), et (probabilité ).

96
Fig 7. Example de Shannon-Feno
97
5. Continuer jusqu'à ce que tous les symboles soient codés. À la fin, chaque symbole sera associé à
un mot binaire.

Symbole Probabilité Étape 1 Étape 2 Étape 3 Code

0.3 0 0 00

0.25 0 1 01

0.2 1 0 11

0.12 1 1 0 100

0.08 1 1 1 1010

0.05 1 1 1 1011

98
Résultat du codage :
Après avoir appliqué l'algorithme de Shannon-Fano, les codes binaires pour chaque symbole peuvent
ressembler à ceci :

99
Analyse de l'exemple :

Entropie bits par symbole.

Longueur moyenne du code bits par symbole.
Efficacité du code .

Cela montre que le codage de Shannon-Fano est assez efficace, bien que le code ne soit pas
nécessairement optimal par rapport à d'autres techniques, comme le codage de Huffman.

100
Codage de Huffman
Le codage de Huffman est un algorithme optimal de codage entropique, introduit en 1952. Contrairement
au codage de Shannon-Fano, il garantit une longueur moyenne minimale du code. En effet, il n'existe aucun
autre code uniquement décodable qui ait une longueur moyenne inférieure à celle obtenue avec
l'algorithme de Huffman.

L'algorithme de Huffman fonctionne en construisant progressivement un arbre binaire où les symboles les
moins probables sont combinés de manière optimale pour réduire la longueur moyenne du code.

101
Principe de l'algorithme de Huffman
L'algorithme fonctionne de manière itérative pour créer un arbre de Huffman. Voici les étapes principales :

1. Trier les symboles par probabilité : Commencez par ordonner tous les symboles de la source par ordre
décroissant de leurs probabilités.
2. Associer les deux symboles de probabilité la plus faible : Les deux symboles ayant les plus petites
probabilités sont associés pour former un nouveau nœud interne. La probabilité de ce nœud est la
somme des probabilités des deux symboles associés.
3. Reprendre l'opération : Le nouvel arbre (ensemble de nœuds) a un élément de moins, car les deux
symboles sont remplacés par leur nœud père. On répète l'étape 2 avec les nouveaux nœuds jusqu'à ce
qu'il n'en reste plus qu'un, qui sera la racine de l'arbre de Huffman.

102
Exemple (Codage de Huffman)
Soit la source avec les probabilités :

1. Trier les symboles par probabilité

On commence par trier les symboles en fonction de leur probabilité, du plus grand au plus petit :

103
2. Associer les deux symboles avec les plus faibles probabilités
On commence par associer les deux symboles ayant les plus faibles probabilités :

Combinez et pour créer un nœud avec une probabilité de .

Le tableau devient maintenant :

104
3. Répéter l'association des symboles avec les plus faibles probabilités
Ensuite, on associe les deux probabilités les plus faibles :

Combinez et pour créer un nœud avec une probabilité de .

Le tableau devient :

105
4. Continuer le processus
Maintenant, on associe les deux symboles ou nœuds avec les probabilités les plus faibles :

Combinez et pour créer un nœud avec une probabilité de

.

Le tableau devient :

puis combiner:

106
5. Finaliser l'arbre
Enfin, on associe les deux nœuds restants :

Combinez et pour créer un nœud avec une probabilité de

, qui devient la racine de l'arbre.

Le processus est terminé et l'arbre est complet.

107
Tableau de Codage de Huffman

Symboles Probabilités Code binaire attribué

0.3 00

0.25 01

0.2 11

0.12 101

0.08 1000

0.05 1001

108
Arbre final de Huffman :

109
Proposition : Le code de Huffman est optimal
Le code de Huffman est optimal en ce sens qu'il minimise la longueur moyenne du code parmi tous les
codes uniquement décodables. Il garantit que la longueur moyenne du code est aussi petite que possible, ce
qui maximise l'efficacité du codage pour une source donnée.

110
Conclusion
Le codage de Huffman est un algorithme fondamental pour les codes à longueur variable. Il assure une
longueur moyenne optimale, ce qui le rend particulièrement utile pour le codage de sources avec des
probabilités variables. Contrairement au codage de Shannon-Fano, qui est basé sur une approche de
séparation des symboles en deux groupes à chaque étape, l'algorithme de Huffman garantit un code plus
efficace et optimal, ce qui le rend préféré dans de nombreux cas pratiques.

111
Exercices:

Implementer les algorithmes de Shannon-Feno et Huffman en Java.

112
Shannon-Feno

class Node {
char character;
int frequency;

Node(char character, int frequency) {

[Link] = character;
[Link] = frequency;
}
}

But : La classe Node représente un caractère et sa fréquence dans la chaîne d'entrée. Chaque objet
Node contient :
Un char représentant le caractère.
Un int représentant la fréquence d'apparition du caractère dans la chaîne.

113
private static List<List<Node>> splitList(List<Node> nodes) {
int totalFrequency = [Link]().mapToInt(n -> [Link]).sum();
int halfFrequency = totalFrequency / 2;
int runningSum = 0;

List<Node> left = new ArrayList<>();

List<Node> right = new ArrayList<>();

for (Node node : nodes) {

if (runningSum < halfFrequency) {
[Link](node);
runningSum += [Link];
} else {
[Link](node);
}
}

return [Link](left, right);

}

114
But : La fonction splitList divise une liste de Node en deux sous-listes dont la somme des fréquences
est aussi proche que possible.
Elle commence par calculer la somme totale des fréquences, puis divise les éléments de manière à
ce que les sous-listes aient une somme de fréquences proche de la moitié de la somme totale.

115
private static void buildShannonFanoCodes(List<Node> nodes, Map<Character, String> codes) {
Queue<List<Node>> queue = new LinkedList<>();
[Link](nodes);

Map<List<Node>, String> currentCodes = new HashMap<>();

[Link](nodes, "");

while (![Link]()) {
List<Node> currentNodes = [Link]();
String currentCode = [Link](currentNodes);

if ([Link]() == 1) {
[Link]([Link](0).character, currentCode);
} else {
List<List<Node>> splitParts = splitList(currentNodes);

[Link]([Link](0));
[Link]([Link](1));

[Link]([Link](0), currentCode + "0");

[Link]([Link](1), currentCode + "1");
}
}
}

116
But : Cette fonction génère les codes Shannon-Fano pour une liste de Node en appliquant l'algorithme
de manière itérative.
Une queue (file d'attente) est utilisée pour gérer les sous-listes de nœuds à traiter. Chaque fois
qu'une sous-liste a plus d'un élément, elle est divisée en deux sous-listes avec des fréquences
approximativement égales. À chaque division, on ajoute un préfixe binaire ("0" ou "1") à la chaîne de
code actuelle.

117
public static Map<Character, String> getShannonFanoCodes(String input) {
Map<Character, Integer> frequencyMap = new HashMap<>();
for (char c : [Link]()) {
[Link](c, [Link](c, 0) + 1);
}

List<Node> nodes = new ArrayList<>();

for ([Link]<Character, Integer> entry : [Link]()) {
[Link](new Node([Link](), [Link]()));
}

[Link]((a, b) -> [Link]([Link], [Link]));

Map<Character, String> codes = new HashMap<>();

buildShannonFanoCodes(nodes, codes);

return codes;
}

118
But : Cette fonction génère les codes Shannon-Fano pour une chaîne donnée.
Calcul des fréquences : On calcule la fréquence d'apparition de chaque caractère dans la chaîne
d'entrée.
Création des Node : Chaque entrée du Map de fréquences est convertie en un objet Node (un
caractère et sa fréquence).
Tri des nœuds : Les nœuds sont triés par fréquence de manière décroissante (les caractères les plus
fréquents apparaissent en premier).
Construction des codes : La fonction buildShannonFanoCodes est ensuite appelée pour générer les
codes binaires pour chaque caractère.

119
public static String encode(String input, Map<Character, String> codes) {
StringBuilder encodedString = new StringBuilder();
for (char c : [Link]()) {
[Link]([Link](c));
}
return [Link]();
}

But : Cette fonction encode la chaîne d'entrée en utilisant les codes Shannon-Fano générés.
On parcourt chaque caractère de la chaîne et on utilise la carte codes pour récupérer le code
binaire associé.
Le code binaire est ajouté à un StringBuilder , qui est ensuite renvoyé sous forme de chaîne.

120
public static void main(String[] args) {
String input = "shannonfano";

Map<Character, String> codes = getShannonFanoCodes(input);

[Link]("Shannon-Fano Codes:");
for ([Link]<Character, String> entry : [Link]()) {
[Link]([Link]() + ": " + [Link]());
}

String encoded = encode(input, codes);

[Link]("\nEncoded String: " + encoded);
}

But : La méthode main montre comment utiliser l'ensemble du processus.

Générer les codes Shannon-Fano pour la chaîne "shannonfano" .
Afficher les codes générés pour chaque caractère.
Encoder la chaîne en utilisant ces codes et afficher la chaîne encodée.

121
Exemple :

Shannon-Fano Codes:
a: 00
f: 010
o: 011
s: 1
n: 001
h: 000

Encoded String: 001101001010011011000101000

122
Huffman

// La classe HuffmanNode est la structure de base pour chaque nœud de l'arbre de Huffman.
class HuffmanNode {

int data; // La fréquence du caractère (poids du nœud)

char c; // Le caractère dans le nœud

HuffmanNode left; // Référence au sous-arbre gauche

HuffmanNode right; // Référence au sous-arbre droit
}

But : La classe HuffmanNode représente un nœud dans l'arbre de Huffman. Chaque nœud contient :
data : La fréquence d'apparition du caractère dans l'ensemble des données.

c : Le caractère associé au nœud. Si ce nœud n'est pas une feuille, c sera égal à '-' .

left et right : Références aux sous-arbres gauche et droit, respectivement.

123
// La classe MyComparator permet de comparer les nœuds de l'arbre de Huffman.
// Elle est utilisée pour construire une file de priorité (min-heap) basée sur les fréquences des nœuds.
class MyComparator implements Comparator<HuffmanNode> {
public int compare(HuffmanNode x, HuffmanNode y) {
return [Link] - [Link]; // Compare les nœuds selon la fréquence (data)
}
}

But : La classe MyComparator permet de comparer deux nœuds de type HuffmanNode en fonction de
leur fréquence ( data ). Cela est essentiel pour utiliser une file de priorité (min-heap) qui extrait
toujours le nœud avec la plus petite fréquence.

124
// Fonction récursive pour imprimer les codes Huffman en effectuant une traversée de l'arbre.
public static void printCode(HuffmanNode root, String s) {

// Cas de base : si le nœud est une feuille (pas de fils gauche ou droit)
// et qu'il contient un caractère (c'est une feuille)
if ([Link] == null && [Link] == null && [Link](root.c)) {
[Link](root.c + ":" + s); // Imprimer le code Huffman pour le caractère
return;
}

// Si on va à gauche, ajouter "0" au code, et si on va à droite, ajouter "1".

printCode([Link], s + "0"); // Appel récursif pour le sous-arbre gauche
printCode([Link], s + "1"); // Appel récursif pour le sous-arbre droit
}

125
But : Cette fonction parcourt récursivement l'arbre de Huffman et génère un code binaire pour chaque
caractère en fonction de son emplacement dans l'arbre.
Si le nœud est une feuille (pas de fils gauche ni droit) et contient un caractère, elle imprime le
caractère suivi du code binaire généré.
Si le nœud n'est pas une feuille, la fonction appelle récursivement les sous-arbres gauche et droit,
en ajoutant respectivement "0" et "1" au code.

126
public static void main(String[] args) {

Scanner s = new Scanner([Link]);

// Fréquences et caractères à encoder

int n = 6; // Nombre de caractères
char[] charArray = { 'a', 'b', 'c', 'd', 'e', 'f' };
int[] charfreq = { 5, 9, 12, 13, 16, 45 };

// Créer une file de priorité (min-heap) pour les nœuds de Huffman

PriorityQueue<HuffmanNode> q = new PriorityQueue<HuffmanNode>(n, new MyComparator());

for (int i = 0; i < n; i++) {

HuffmanNode hn = new HuffmanNode();
hn.c = charArray[i]; // Caractère
[Link] = charfreq[i]; // Fréquence
[Link] = null; // Pas de sous-arbre gauche pour le moment
[Link] = null; // Pas de sous-arbre droit pour le moment
[Link](hn); // Ajouter le nœud à la file de priorité
}

HuffmanNode root = null; // Le nœud racine de l'arbre de Huffman

// Extraire les deux nœuds ayant les fréquences les plus faibles,
// créer un nouveau nœud avec ces deux nœuds comme enfants, et ajouter ce nœud à la file de priorité.
while ([Link]() > 1) {
HuffmanNode x = [Link](); // Extraire le nœud avec la fréquence minimale
[Link]();

HuffmanNode y = [Link](); // Extraire le nœud avec la deuxième fréquence minimale

[Link]();

HuffmanNode f = new HuffmanNode(); // Créer un nouveau nœud

[Link] = [Link] + [Link]; // La fréquence est la somme des fréquences des deux nœuds
f.c = '-'; // Ce nœud ne représente pas un caractère, donc son champ 'c' est '-'
[Link] = x; // Le premier nœud extrait devient le sous-arbre gauche
[Link] = y; // Le deuxième nœud extrait devient le sous-arbre droit

root = f; // Le nœud créé devient la nouvelle racine de l'arbre de Huffman

[Link](f); // Ajouter le nouveau nœud à la file de priorité

}

// Imprimer les codes en traversant l'arbre de Huffman

printCode(root, "");
}

127
But : La méthode main met en œuvre l'algorithme de Huffman.
On commence par définir les caractères et leurs fréquences dans les tableaux charArray et
charfreq .

Ensuite, on crée une file de priorité (min-heap) pour gérer les nœuds de Huffman.
On crée un nœud pour chaque caractère, en le stockant dans la file de priorité.
Puis, on construit l'arbre de Huffman en extrayant les deux nœuds ayant les fréquences les plus
faibles, en les combinant pour former un nouveau nœud, et en ajoutant ce nœud à la file de
priorité.
Le processus se répète jusqu'à ce qu'il ne reste qu'un seul nœud dans la file, qui devient la racine de
l'arbre.
Enfin, on appelle la fonction printCode pour afficher les codes Huffman de chaque caractère.

128
Exemple

a: 000
b: 001
c: 01
d: 10
e: 11
f: 1

Dans cet exemple, les codes Huffman sont attribués aux caractères en fonction de leur fréquence. Les
caractères plus fréquents (comme f et e ) reçoivent des codes plus courts, tandis que les caractères
moins fréquents (comme a , b et c ) reçoivent des codes plus longs.

129