Codage de Source

Transmissions Numériques

Cédric RICHARD
Université Nice Sophia Antipolis
 Codage de source

Digital Communications, B. Sklar, Prentice Hall

1
 Codage de source
Plusieurs conceptions de l’information

La notion d’information diffère selon qu’on se place du côté de la machine ou de

l’individu. La conception analytique en rend compte.

signe signification
(forme) (fond )

Conception analytique de l’information.

2
 Codage de source
Plusieurs conceptions de l’information

signe
conception technique

signifié signifiant
conception sémantique conception pragmatique

Conception systémique de l’information.

3
 Codage de source
Objectifs de la théorie de l’information

Priorités du système informatique

Importance du signe prépondérante dans le traitement, le stockage et la
transmission.

Priorités du système d’information

Aspects sémantiques et pragmatiques privilégiés.

Exemple : la facturation électronique

Remplace ou accompagne la facturation classique ?
Nombre de signes échangés, flux de données ?
La théorie de l’information s’intéresse au signe.

4
 Codage de source
Les origines de la théorie de l’information (1928 – ...)

Travaux de H. Nyquist pour la théorie des communications

⊲ Liens entre bande passante et vitesse d’émission.
⊲ Etude des distorsions inter-symboles.

Travaux de R.V. Hartley

⊲ Une définition de la notion d’information.

Oeuvre de C.E. Shannon

⊲ Performances limites en présence de perturbations.
⊲ Notions de source d’information et de canal de transmission.

5
 Codage de source
Modèle de communication : le paradigme de Shannon

message
source canal destinataire

perturbations

⊲ source : générateur de message.

⊲ message : suite de symboles d’un alphabet donné.
⊲ canal : vecteur de l’information entre source et destinataire.
⊲ perturbations : stochastiques par nature.

6
 Codage de source
Quantité d’information propre d’un événement

Soit A un événement de probabilité P (A) non-nulle.

L’information h(A) apportée par la réalisation de A est d’autant plus grande
qu’elle est improbable. Elle peut s’exprimer ainsi :
 
1
h(A) = f .
P (A)

La fonction f (·) vérifie les contraintes suivantes :

⊲ f (·) est croissante
⊲ info. apportée par 1 événement sûr est nulle : limp→1 f (p) = 0
⊲ info. apportée par 2 événements indépendants : f (p1 · p2 ) = f (p1 ) + f (p2 )
Ceci nous conduit à utiliser la fonction logarithmique pour f (·)

7
 Codage de source
Quantité d’information propre d’un événement

Lemme 1. La fonction f (p) = − logb p est la seule qui soit à la fois positive,
continue sur ]0, 1], et qui vérifie f (p1 · p2) = f (p1) + f (p2).

Preuve. La démonstration comporte les étapes suivantes :

1. f (pn ) = n f (p)
2. f p1/n = n1 f (p) après avoir remplacer p par p1/n

3. f pm/n = m


n f (p) en combinant le deux égalités précédentes
4. f (pq ) = q f (p) où q désigne un nombre rationnel positif quelconque
5. f (pr ) = limn→+∞ f (pqn ) = limn→+∞ qn f (p) = r f (p)
Soient p et q appartenant à ]0, 1[. On peut écrire p = q logq p , ce qui entraîne
f (p) = f q logq p = f (q) logq p.

On aboutit finalement au résultat escompté, soit

f (p) = − logb p

8
 Codage de source
Quantité d’information propre d’un événement

Définition 1. Soit A un événement de probabilité P (A) non-nulle. On associe à la

réalisation de A la quantité d’information propre :

h(A) = − log P (A).

Unités. L’unité dépend de la base choisie pour le logarithme.

⊲ log2 : Shannon, bit (binary unit)
⊲ loge : logon, nat (natural unit)
⊲ log10 : Hartley, decit (decimal unit)

Vocabulaire. h(·) est désigné par incertitude ou encore quantité d’information.

9
 Codage de source
Quantité d’information propre d’un événement

Quantité d’information propre ou incertitude : h(A) = − logb P (A)

h(A)

P (A)
0
0 1/b 0.5 1

10
 Codage de source
Entropie d’une source

Soit une source S d’information sans mémoire sélectionnant aléatoirement un

symbole parmi les n éléments d’un alphabet S = {s1 , . . . , sn }. Soit pi la probabilité
d’apparition de si . La quantité d’information moyenne associée à l’apparition de
chaque symbole possible est donnée par :
n
X
H(S) = E{h(s)} = − pi log pi .
i=1

L’entropie est une quantité d’information moyenne.

11
 Codage de source
Exemple : entropie d’une source binaire

L’entropie d’une source binaire est donnée par :

H(S) = −p log p − (1 − p) log(1 − p) , H2 (p).

entropie H2 (Sh/symb) 1

0.5

0
0 0.5 1
probabilité p

12
 Codage de source
Entropie : notation et propriété préalables

Lemme 2 (Inégalité de Gibbs). Etant donné 2 distributions de probabilité

discrètes (p1 , . . . , pn ) et (q1 , . . . , qn ) sur un même univers fini, on a :
n
X qi
pi log ≤ 0,
i=1
pi

l’égalité étant obtenue lorsque ∀i : pi = qi .

Preuve. On effectue la démonstration dans le cas du logarithme népérien et on

note que ln x ≤ x − 1, l’égalité étant obtenue pour x = 1. On pose x = pqii et on a
n n
X qi X qi
pi ln ≤ pi ( − 1) = 1 − 1 = 0.
i=1
pi i=1
pi

13
 Codage de source
Entropie : notation et propriété préalables

Vérification graphique de l’inégalité ln x ≤ x − 1

y
y =x−1
2

1
y = ln x
0
0.5 1 1.5 2 2.5
x
−1

−2

−3

−4

14
 Codage de source
Quelques propriétés de l’entropie

Propriété 1. L’entropie vérifie l’inégalité suivante

Hn (p1 , . . . , pn ) ≤ log n,
1
l’égalité étant réalisée dans le cas d’une loi uniforme, c’est-à-dire ∀i : pi = n.

Preuve. A partir de l’inégalité de Gibbs, on pose qi = n1 . L’incertitude sur le

résultat d’une expérience est d’autant plus grande que tous les résultats possibles
sont équiprobables.

15
 Codage de source
Entropie conjointe

Définition 2. Soient S et T deux sources d’alphabets {s1 , . . . , sn } et {t1 , . . . , tm }.

L’entropie conjointe de S et T est donnée :
n X
X m
H(S, T ) , − P (S = si , T = tj ) log P (S = si , T = tj ).
i=1 j=1

⊲ l’entropie conjointe est une grandeur symétrique : H(S, T ) = H(T, S)

Exemple. Cas de sources indépendantes.

16
 Codage de source
Adaptation d’une source à un canal non-bruité

On associe à chacun des Q états si d’une source S ∈ {si , . . . , sQ } un mot approprié,

c’est-à-dire une suite de ni symboles d’un alphabet q-aire. Ceux-ci constituent un
code source que l’on désigne par C ∈ {c1 , . . . , cq }.

source codeur canal

S −→ C

S ∈ {s1 , . . . , sQ } C ∈ {c1 , . . . , cq }

Exemple. Le code Morse

⊲ code quaternaire (point, trait, espace long, espace court)
⊲ code de longueur variable
⊲ la séquence la plus courte associée à "E"

17
 Codage de source
Adaptation d’une source à un canal non-bruité

Soit S une source caractérisée par un débit Ds (symbole Q-aire/seconde). Soit un

canal non-bruité de débit maximal Dc (symbole q-aire/seconde). On définit
- taux d’émission de la source : T , Ds H(S)
- capacité du canal : C , Dc log q

Si T > C : le canal ne peut écouler l’information

Si T ≤ C : le canal peut en théorie écouler l’information

Si on dispose d’un code q-aire dont la longueur moyenne n des mots est
telle n Ds ≤ Dc , alors celui-ci peut être utilisé pour la transmission.
Dans le cas contraire, comment coder les états de la source pour rendre
leur transmission possible puisque rien ne s’y oppose en théorie ?

Le codage de source vise à éliminer la redondance d’information

SANS PERTE ! ! !

18
 Codage de source
Modèle général de source

Une source discrète est définie par un alphabet S = {s1 , . . . , sQ } et un mécanisme

d’émission. Il s’agit d’un processus aléatoire en temps discret

S1 , . . . , Si−1 , Si , Si+1 , . . .

caractérisé par les lois conjointes :

P (S1 , . . . , Sn ), ∀n ∈ IN∗

⊲ modèle trop général pour donner lieu à des développements simples

19
 Codage de source
Hypothèses complémentaires

Par simplification, on fait des hypothèses sur le modèle de source.

Propriété 2 (Processus stationnaire). Un processus aléatoire Si est dit

stationnaire si les lois de probabilité qui le régissent sont indépendantes de l’origine
des temps, c’est-à-dire

P (S1 = si1 , . . . , Sn = sin ) = P (Sn0 +1 = si1 , . . . , Sn0 +n = sin ),

pour tous n0 et n positifs.

Exemple. Une source sans mémoire est caractérisée par des Si indépendants et
identiquement distribués. Il s’agit d’un processus stationnaire.

P (S1 = si1 , . . . , Sn = sin ) = P (S = si1 ) . . . P (S = sin ).

20
 Codage de source
Source markovienne

Une source quelconque émet un symbole selon une loi qui peut dépendre des
symboles qui l’ont précédé.

Définition 3 (Source markovienne). Une source S est dite markovienne si elle

décrit une chaîne de Markov, soit

P (Sn+1 = sin+1 |Sn = sin , . . . , S1 = si1 ) = P (Sn+1 = sin+1 |Sn = sin )

pour tous symboles si1 , . . . , sin+1 issus de S.

Il en résulte directement que

P (S1 , . . . , Sn ) = P (S1 ) P (S2 |S1 ) . . . P (Sn |Sn−1 )

21
 Codage de source
Source markovienne

Définition 4 (Invariance dans le temps). Une source markovienne S est dite

invariante dans le temps si, pour tout n ∈ {1, 2, . . .}, on a

P (Sn+1 |Sn ) = P (S2 |S1 )

Une telle source est entièrement définie par un vecteur p|t=0 de probabilités
initiales et la matrice de transition Π dont les éléments sont

Π(i, j) = P (S2 = sj |S1 = si )

Pq
évidemment, on a j=1 Π(i, j) = 1 et Π(i, j) ≥ 0.

22
 Codage de source
Exemple de source markovienne

On considère la source markovienne suivante :

0.2

s3
0.3 0.5
0.8
s1 s2
0.5

0.7

La matrice de transition de celle-ci s’écrit ainsi :

 
0 0.7 0.3
 
Π=  0.5 0 0.5 
0 0.8 0.2

23
 Codage de source
Entropie d’une source stationnaire

Définition 5. L’entropie d’une source S stationnaire est définie par :

H(S1 , . . . , Sn )
H0 , lim .
n→+∞ n

Exemple 1. Dans le cas d’une source sans mémoire, caractérisée par des Si
indépendants et distribués selon une même loi, on a :

H0 = H(S1 ).

Exemple 2. Si S désigne une source markovienne invariante dans le temps,

l’entropie de celle-ci est donnée par :

H0 = H(S2 |S1 ).

24
 Codage de source
Caractérisation d’un code : vocabulaire par l’exemple

Le codage de source consiste à associer à chaque symbole si d’une source une

séquence d’éléments de l’alphabet q-aire de destination, appelée mot du code.
Exemple 1. Codes ASCII (7 bits) et ASCII étendu (8 bits), code Morse, etc.

Exemple 2.

code A code B code C code D code E code F code G

s1 1 0 00 0 0 0 0
s2 1 10 11 10 01 10 10
s3 0 01 10 11 011 110 110
s4 0 11 01 110 0111 1110 111

25
 Codage de source
Caractérisation d’un code

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é.

Exercice. Caractériser les codes A à G.

26
 Codage de source
Inégalité de Kraft

On se propose de construire des codes déchiffrables, et plus particulièrement

instantanés, aussi économiques que possible. L’inégalité de Kraft fournit une
condition nécessaire et suffisante d’existence de codes instantanés.

Théorème 1 (Inégalité de Kraft). On note n1 , . . . , nQ les longueurs des mots

candidats pour coder les Q états d’une source dans un alphabet q-aire. Une
condition nécessaire et suffisante d’existence d’un code instantané ayant ces
longueurs de mots est donnée par :
Q
X
q −ni ≤ 1.
i=1

Remarque. La même condition nécessaire et suffisante a été établie par McMillan

pour les codes déchiffrables, antérieurement à l’inégalité de Kraft.

27
 Codage de source
Code complet

Définition 6 (Code complet). Un code est dit complet s’il vérifie la relation
Q
X
q −ni = 1.
i=1

28
 Codage de source
Inégalité de McMillan

A titre d’exemple, on applique l’inégalité de McMillan à différents codes.

code A code B code C

s1 00 0 0
s2 01 100 10
s3 10 110 110
s4 11 111 11
P4
i=1 2−ni 1 7/8 9/8

Les codes A et B sont déchiffrables, le premier étant complet. Le code C n’est pas
déchiffrable.

29
 Codage de source
Vers le premier théorème de Shannon

Soit S une source sans mémoire à Q états. Soit pi la probabilité d’apparition de si ,

auquel est associé un mot de code déchiffrable q-aire de longueur ni . En posant
q −ni
qi = PQ ,
j=1 q −nj

puis en appliquant l’inégalité de Gibbs à pi et qi , on obtient alors

Q Q Q
X 1 X X
pi log + pi log q −ni ≤ log q −ni .
i=1
pi i=1 i=1

En appliquant le théorème de McMillan au dernier membre de l’inégalité, il en

résulte finalement
Q
X
H(S) − n log q ≤ log q −ni ≤ 0,
i=1
PQ
où n = i=1 pi ni représente la longueur moyenne des mots du code.

30
 Codage de source
Vers le premier théorème de Shannon

Théorème 2. La longueur moyenne n des mots de tout code déchiffrable est

bornée inférieurement selon
H(S)
≤ n.
log q

Condition d’égalité. L’inégalité ci-dessus se transforme en égalité à condition que

PQ −ni
i=1 q = 1, c’est-à-dire si pi = q −ni . Ceci signifie que
1
log pi
ni = .
log q

1
log pi
Définition 7. Un code dont la longueur de chaque mot est telle que ni = log q est
dit absolument optimum.

31
 Codage de source
Vers le premier théorème de Shannon

La condition d’égalité précédente n’est généralement pas vérifiée. Il est cependant

possible de constituer un code tel que
log p1i log p1i
≤ ni < + 1.
log q log q
En multipliant par pi et en sommant sur i, ceci signifie que
H(S) H(S)
≤n< + 1.
log q log q

Définition 8 (Codes compact et de Shannon). Un code dont la longueur moyenne

des mots vérifie la double inégalité présentée ci-dessus est dit compact. Plus
particulièrement, on parle de code de Shannon lorsque
& 1
'
log pi
ni = .
log q

32
 Codage de source
Premier théorème de Shannon

Les bornes qui viennent d’être établies vont nous permettre de démontrer le
premier théorème de Shannon, qui s’énonce ainsi :

Théorème 3. Pour toute source stationnaire, il existe un procédé de codage

déchiffrable où la longueur moyenne des mots est aussi voisine que l’on veut de sa
borne inférieure.

Preuve pour une source sans mémoire. On considère la k ème extension de la

source S. Dans le cas d’une source sans mémoire
kH(S) kH(S)
≤ nk < + 1.
log q log q
Dans cette expression, nk désigne la longueur moyenne des mots de code utilisés
dans le cadre de la k ème extension de S. On divise par k et on passe à la limite.

33
 Codage de source
Premier théorème de Shannon

Preuve pour une source stationnaire. On considère la k ème extension de la

source S. Dans le cas d’une source sans mémoire
H(S1 , . . . , Sk ) nk H(S1 , . . . , Sk ) 1
≤ < + .
k log q k k log q k
Dans cette expression, nk désigne la longueur moyenne des mots de code utilisés
dans le cadre de la k ème extension de S.
Dans le cas d’une source stationnaire, on sait que limk→∞ H(S1 , . . . , Sk ) existe. En
reprenant la notation conventionnelle H0 de cette limite, on aboutit à
nk H0
lim = .
k→∞ k log q

Remarque. D’un point de vue pratique, l’intérêt du Premier Théorème de

Shannon est limité.

34
 Codage de source
Techniques de codage binaire : méthode directe

Le premier théorème de Shannon exprime une propriété asymptotique du langage,

mais ne fournit aucune méthode pratique pour y parvenir.
Une technique de codage directe consiste à associer à chaque état de la source un
nombre de symboles ni tel que
& 1
'
log pi
ni = .
log q

Remarque. Le code obtenu est un code de Shannon.

35
 Codage de source
Code de Shannon

On considère un système à 5 états {s1 , . . . , s5 } définis par les probabilités :

p1 = 0.35 − log2 p1 = 1.51 −→ n1 = 2

p2 = 0.22 − log2 p2 = 2.18 −→ n2 = 3
p3 = 0.18 − log2 p3 = 2.47 −→ n3 = 3
p4 = 0.15 − log2 p4 = 2.73 −→ n4 = 3
p5 = 0.10 − log2 p5 = 3.32 −→ n5 = 4.

Il est aisé d’obtenir un code instantané vérifiant la condition précédente sur les ni à
l’aide d’un arbre. On obtient par exemple :
s1 : 00 s2 : 010 s3 : 011 s4 : 100 s5 : 1010.
On aboutit à n = 2.75, à comparer à H(S) = 2.19 Sh/symb.

36
 Codage de source
Code de Shannon-Fano

Le code de Shannon-Fano est le premier code à avoir exploité la redondance d’une

source. On en expose à présent le principe.

1. Ranger les états du système par probabilités décroissantes.

2. Subdiviser les états du système en 2 groupes G0 et G1 de probabilités
voisines, sans modifier l’ordre dans lequel ils ont été rangés en 1.
3. Chaque groupe Gi est subdivisé en 2 sous-groupes Gi0 et Gi1 de probabilités
aussi voisines que possibles, une fois encore sans modifier l’ordre des états.
4. La procédure s’arrête lorsque chaque sous-groupe est constitué d’un unique
élément. L’indice du groupe donne le mot de code.

37
 Codage de source
Code de Shannon-Fano

Pour élaborer un code de Shannon-Fano, on procède ainsi :

état pi étape 1 étape 2 étape 3 code

s1 0.35 0 0 00
s2 0.22 0 1 01
s3 0.18 1 0 10
s4 0.15 1 1 0 110
s5 0.10 1 1 1 111

On aboutit à n = 2.25, à comparer à H(S) = 2.19 Sh/symb.

38
 Codage de source
Code de Huffman

La méthode de Huffman fournit un code instantané compact de longueur moyenne

minimale. Pour y parvenir, elle exploite la propriété suivante.

Lemme 3. Pour toute source, il existe un code instantané de longueur moyenne

minimale satisfaisant les propriétés suivantes.
1. Si P (S = si ) > P (S = sj ), alors ni ≤ nj .
2. Les deux mots les plus longs, donc associés aux états les moins probables,
ont même longueur et ne diffèrent que d’un bit.

La méthode de Huffman consiste à regrouper les deux états les moins probables,
puis à les traiter comme un seul en sommant leur probabilité. Cette technique est
alors réitérée sur les états restants, jusqu’à ce qu’il n’en reste que deux.

39
 Codage de source
Code de Huffman

On construit un arbre en partant des feuilles les plus profondes, qui représentent les
états de la source.

1. A chaque étape, on fusionne les feuilles les moins probables en une seule.
2. La procédure s’arrête lorsque on aboutit à une feuille unique constituée de
tous les symboles.
3. Le parcours inverse de l’arbre fournit les mots du code.

40
 Codage de source
Code de Huffman

0 0
0.35 0.35 0.35 0.60

0 1
0.22 0.22 0.40 0.40

1
0.18 0.18

0 1
0.15 0.25 0.25

1
0.10

Finalement, le parcours inverse de l’arbre fournit le résultat suivant :

s1 : 00 s2 : 10 s3 : 11 s4 : 010 s5 : 011.
On aboutit à n = 2.25, à comparer à H(S) = 2.19 Sh/symb.

41