Les grands théorèmes de la

théorie d’information

Azza Ouled Zaid

Institut Supérieur d’Informatique

1ère année Cycle d’Ingénieur

2023-2024
Codage de source
 Rappel, entropies et schéma général de
communication
 Notations et exemples
 Codes préfixes – inégalité de Kraft
 Codes optimaux
 Théorème de Shannon
 Codes de Fano et de Huffman
 Codage arithmétique
 Schéma général de communication

 Codage de source pour profiter de la redondance de la source

et réduire la longueur du message à transmettre

 Codage de canal pour détecter et corriger les erreurs lors de la

transmission sur le canal
 Codage source
 Si les symboles de la source sont indépendants et
distribués selon la même loi de probabilité, utilisant un
alphabet Q_aire alors son entropie est au maximum égale
à logQ

 Si les symboles de la source ne sont pas équiprobables

alors son entropie est inférieure à sa capacité logQ

 Si les symboles de la source ne sont pas indépendants, alors

l’alphabet est mal utilisé dans la mesure ou l’information
fournie par la source est inférieure au maximum
théoriquement atteignable
 Codage source

 La quantité d’information fournie par la source peut être

réduite si les symboles successifs ne sont pas indépendants,
si la source a une mémoire
 La connaissance d’une partie des symboles émis par la source
réduit potentiellement l’entropie des symboles non encore
observés
 Codage source :
 Transformer le message engendré par une source
redondante en un message dont les symboles sont
équiprobables et indépendants
 la transformation est réversible
 Source discrète

1. Définition des paramètres utilisés pour

caractériser une source d’information

2. Problème de codage de source

 Source discrète
 Modèle de la source S : Processus stochastique produisant
séquentiellement des caractères d’un alphabet A.
 Alphabet A={c1,…,cn} : Ensemble fini contenant au moins
deux caractères ci
 Chaîne s : séquence (finie) de caractères c1,…,ck.
 Pi : probabilité indépendante d’émettre ci.

 Exemple de sources :
 Constante c1 : p1=1 et pi=0
 Aléatoire : pi=1/n
 Biaisée (exemple) : p1=1/2 et pi=1/(2(n-1))
Entropie et mesure de l’information
 Mesure de l’information Intuition sur la notion
d’information (C. E. Shannon)

Plus de «surprise», plus d’incertitude, plus d’information, plus de

bits

 Entropie : visions possibles :

 Moyenne de la « surprise », ou incertitude, -log(pi) par
caractère

 Nombre moyen de bits par caractère transmis, si source

aléatoire pour chaque caractère
 Entropie et information

 Information liée à un événement de probabilité p(i)

 1 
log 2  
 pi 

 d’autant plus d’information que l’événement est inattendu

 croissance exponentielle du nombre de combinaisons avec la longueur

du message
Entropie et information

 Entropie = espérance de l’information, c.à.d la

moyenne au sens probabiliste.

 L’entropie d’une source S ergodique d’ordre 0

exprimée en bits :

1
H S    pilog 2   pilog 2 pi
i pi k
Codage de source
 Rappel, entropies et schéma général de
communication
 Notations et exemples
 Codes préfixes – inégalité de Kraft
 Codes optimaux
 Théorème de Shannon
 Codes de Fano et de Huffman
 Codage arithmétique
 Notations
 Un code de source C pour une V.A X est une fonction
C: X  D*

X, l’ensemble des valeurs possibles de X,

D*, l’ensemble des chaînes de symboles d’un alphabet.
 C(x) est le mot code correspondant au symbole x
 nx est la longueur du mot code C(x)
 La longueur moyenne n attendue du code C pour la
variable X caractérisée par une distribution de probabilités
p(x) est
n   p  x .nx
x X
Exemples
Exemple 1:
– X = { rouge, bleu }
– Alphabet 3-aire (q=3) : { A,B,C }
– C(rouge)=AA, C(bleu)=ABC

n   prouge   2  pbleu  3
x X

Exemple 2:
– X = { 1,2,3,4 } , alphabet binaire (q=2) : { 0,1 }
– P(x=1) = ½, C(1) = 0
– P(x=2) = ¼, C(2) = 10
– P(x=3) = ? , C(3) = 110
– P(x=4) = ? , C(4) = 111

n   px .nx  1.75  H  X 

x X
 Exemple
 Soit une source X qui produit 2 symboles A et B avec les probabilités
respectives de 4/5 et 1/5 à une cadence de 80 symboles par minute.
 L’entropie de cette source est
H  X     p x .log p x 
x X

 0.2log0.2   0.8 log0.8 

 0.72 bits/symbole
soit 0,72 x 80 /60 = 0,96 bit/sec.

 Soit un canal binaire sans perte qui transmet 2 symboles

0 et 1 à une cadence de 1 symbole par seconde. La
capacité de ce canal est évidemment de 1 bit/sec.
 Exemple (suite)
 Le codage le plus simple qu’on puisse imaginer est:

 La longueur moyenne des mots code, exprimée en

nombre de symboles {0,1} du code C par symbole x de
{A,B} de la source X, est
n  p  x .n x
 
x A ,B

 0. 8  1  0. 2  1  1
Une suite typique de 30 symboles de la source est codé ainsi :

avec ce code, on génère donc 80 symboles/min, ce que le canal ne

peut pas absorber
 Exemple (suite)
 Un meilleur code peut être obtenu en groupant les symboles de la source par
paires:

La longueur moyenne des mots code, en nombre de symboles par

paire de lettres de la source est :
n  px.n
xAA , AB ,BA ,BB
x  0.64  1  0.16  2  0.16  3  0.04  3

soit 1.56 / 2 = 0,78 par lettre de la source

La même suite de 30 symboles de la source est maintenant codée
avec 24 bits:

L’encodeur produit 0,78 x 80 = 62,4 symboles par minute, encore trop haut
pour le canal
 Exemple (suite)
 On peut grouper les symboles de la source 3 par 3 pour arriver au
code suivant :

La longueur moyenne des mots code est 2,184 symboles par 3 lettres
de la source, donc 0,728 par lettre
L’encodeur produit donc 0,728 x 80 = 58,24 symboles par minute,
suffisant pour le canal
 Exemple (suite)
 Une suite typique de 30 symboles de la source est codée ainsi :

La suite de 30 symboles de la source est maintenant codée avec

22 symboles de code, 11 «0 » et 11 « 1 ».

 L’équiprobabilité des 0 et des 1 n’est pas un hasard, la capacité d’un canal à 2

symboles correspond au maximum de l’entropie de la source. Cette entropie est
maximum quand les symboles sont équiprobables

 Cet encodeur doit disposer d’une mémoire et introduire un retard. Trois lettres
de la source doivent être mémorisées avant qu’un mot code soit émis.

 Un mot code à 5 symboles est transmis plus lentement qu’un mot à un seul
symbole et aussi plus lentement que l’arrivée d’un groupe de 3 symboles de la
source primaire.
Codage de source
 Rappel, entropies et schéma général de
communication
 Notations et exemples
 Codes préfixes – inégalité de Kraft
 Codes optimaux
 Théorème de Shannon
 Codes de Fano et de Huffman
 Codage arithmétique
 Propriétés souhaitées des codes
 non singulier (régulier): xi  x j  C xi   C x j 
– permet de décoder un symbole unique, mais pas une suite de
symboles
– pour décoder une suite, il faut introduire un symbole de ponctuation.

 uniquement décodable (déchiffrable) :

– C* est le code étendu tel que C *  x1 , , xn   C x1 C  x2  C xn 
– C est uniquement décodable si C* est non singulier

 instantanément décodable:
– Chaque symbole C peut être décodé sans référence aux symboles
suivants
– Condition préfixe: aucun mot code n’est le préfixe d’un autre mot code
 Condition de préfixe

 Soit une source X générant des symboles xk d’un alphabet Q-aire

(k{1,…,Q} )

 Soit C(xk) le mot-code correspondant au symbole xk de la source

 C(xk), de longueur nk, peut s’écrire C(xk ) = (ck,1, ck,2 …, ck,nk), où ck,i
représente une lettre aj de l’alphabet q-aire du code (j {1,…,q} ).

 Toute séquence de lettre construite par la partie initiale de C(xk) est

appelée préfixe

 La condition de préfixe stipule que dans un code aucun mot-code n’est

le préfixe d’un autre mot-code
 Condition de préfixe

 Les codes à condition de préfixe sont à décodage

unique

 Tous les codes à décodage unique ne satisfont pas

nécessairement la condition de préfixe

 La condition de préfixe permet de reconnaître la fin

d’un mot-code, donc un décodage sans retard (codes
instantanés)
 Construction d’un code à préfixe

 Un code préfixe q-aire peut être représenté par un

arbre q-aire dont les feuilles sont les mots du code
 Inégalité de Kraft
 Propriété des codes préfixes:
 Pour tout code préfixe de K mots sur un alphabet de q
symboles dont les mots codes ont pour longueur n1, n2, …, nK
, ces entiers satisfont
K

q
k 1
 nk
1

 Inversement, étant donnés des entiers n1, n2, …, nK qui

satisfont cette inégalité, on peut construire un code
préfixe dont les mots code ont ces longueurs
 Inégalité de Kraft : Preuve
 Soit nmax la longueur du mot le plus long du code
 On considère l’arbre q-aire de profondeur nmax , les
feuilles au niveau nmax sont soit
– des mots code (1)
– des descendants de mots code (2)
– aucun des deux (3)
 Un mot code de longueur nk a q nmax  nk descendants.
 La condition de préfixe implique que l’ensemble de ces
descendants doit être disjoint pour tous les mots codes.
 Si l’on considère l’ensemble des feuilles de niveau nmax qui
sont ou descendent d’un mot code, soit (1)+(2), il y en a
donc
 1
nx log 1
 px
 Inégalité de Kraft : Preuve
 Cet ensemble (1)+(2) de feuilles étant ou descendant de
mots-codes est évidemment inclus dans l’ensemble
(1)+(2)+(3) de toutes les feuilles de niveau nmax. On a donc

q
k 1
nmax  nk
q nmax

nmax
 Et en divisant par q , on obtient bien l’inégalité de Kraft

qk 1
 nk
1
 Inégalité de Kraft
 L’inégalité de Kraft constitue un résultat fondamental en
théorie des codes. Elle fournie en effet une condition
nécessaire et suffisante d’existence de codes déchiffrables et
instantanés, exprimée en fonction de la longueur des mots du
codes

 Théorème Mac Millan : Il existe un code à décodage unique

dont les K mots ont pour longueur n1, n2, …, nK
ssi
K

 1
q  nk

k 1
Codage de source
 Rappel, entropies et schéma général de
communication
 Notations et exemples
 Codes préfixes – inégalité de Kraft
 Codes optimaux
 Théorème de Shannon
 Codes de Fano et de Huffman
 Codage arithmétique
 Codage optimal

 Les théorèmes de Kraft et Mac Millan ont un corollaire immédiat :

Corollaire : S’il existe un code à décodage unique dont les k mots

ont pour longueurs n1, n2, …, nk alors il existe un code préfixe
avec les mêmes longueurs

Définition : Un code à décodage unique d’une source X est

optimal s’il n’existe pas de code à décodage unique de X ayant
une longueur moyenne strictement inférieure

Proposition : Pour toute source il existe un code préfixe optimal

 Codage = optimisation
  nx 
La recherche d’un bon code pour J   p x .nx     q 
une source caractérisée par une x  x 
probabilité p(x) peut être vue comme
J
un problème d’optimisation sous  p x   q  nx .logq   0
contrainte: trouver les entiers n1, n2, … nK nx
nx px 
q 
 minimiser n   px .nx  .logq 
px 
x X
1
 sous contrainte de  q  ni

i
1 x q x  .logq    .logq   1
nx

1

logq 
En négligeant la contrainte de longueurs
entières et en assumant l’ égalité pour la
contrainte, on applique la méthode de p x   q  nx
Lagrange:
nx  log q p x 
 Codes optimaux
 Pour les codes optimaux, la longueur moyenne est
égale à l’entropie de la source:
nx  log q p x 
H X 
n   p  x .nx   p  x log q  p x   H q  X  
x x logq 
Exemple 2 (rappel) :
– X = { 1,2,3,4 } , alphabet binaire: { 0,1 }
– P(x=1) = ½, n1 = -log2(½) = 1 C(1) = 0
– P(x=2) = ¼, n2 = -log2(¼) = 2 C(2) = 10
– P(x=3) = ? , n3 = -log2(? ) = 3 C(3) = 110
– P(x=4) = ? , n4 = -log2(? ) = 3 C(4) = 111

n   p x .nx  1.75  H  X 
x
Codage de source
 Rappel, entropies et schéma général de
communication
 Notations et exemples
 Codes préfixes – inégalité de Kraft
 Codes optimaux
 Théorème de Shannon
 Codes de Fano et de Huffman
 Codage arithmétique
Théorème de Shannon
 En pratique, on ne peut négliger la contrainte nx entier, et
il est donc souvent impossible d’atteindre l’optimum.
Cependant, on peut prouver qu’il est possible de s’en
approcher:

 Si H(X) est l’entropie de la source, alors

H X  H X 
n 1
logq  logq 

 Si les symboles de la source sont groupées L par L avant

le codage, alors
H X  H X  1
n 
logq  logq  L
 Preuve
On a vu précédemment que pour un code optimal, n  H q X 
Pour un code non optimal, on a donc n  H q X 
Pour prouver l’autre inégalité, on construit un code avec des longueurs

  1 
nx  log q  
  p  x  
Ces longueurs permettent de construire un code préfixe, vu qu’elles
  1   1 
  log q    log q  
 px  
satisfont l’inégalité de Kraft q
x

 q
x
 px  

Par ailleurs, on a
 1   
log q    n x  log q  1   1
 p x  
  px  
 

ce qui donne, en moyenne pondérée par les p(x),

Hq  n  Hq 1
 Preuve (suite)
Si cette borne supérieure n’est pas satisfaisante, on peut
l’améliorer en groupant les symboles L par L. On définit un nouveau
code C* pour coder les séquences (X1,X2…XL) avec des mots code
de longueur n*x qui satisfont

H q  X 1 , X 2 , , X L   n *  H q  X 1 , X 2 , , X L   1
L.H q  X   L.n  L.H q  X   1
1
H q X   n  H q X  
L
Exemple 3 (rappel):
– X = { A,B } , p(A)=0.2 , p(B)=0.8 , H(X)=0.72
– 1 symbole à la fois: H(X) = 0.72 ; n = 1 < 1.72 = H(X) + 1
– 2 symboles à la fois: H(X) = 0.72 ; n = 0.78 < 1.22 = H(X) + 1/2
– 3 symboles à la fois: H(X) = 0.72 ; n = 0.728 < 1.05 = H(X) + 1/3
 Codage à longueur variable
 Associer à chaque symbole Si(i=1,…,Q) de la source un mot de
code q-aire, c’est-à-dire une suite mi de ni symboles de
l’alphabet de destination q-aire.

 Le code doit posséder

1. les propriétés qui permettent de reconstruire ( facilement)
les messages envoyés par la source,
2. il doit permettre d’utiliser aux mieux la capacité du canal en
réalisant une adaptation statique
 Exercices d’application
 Exercice 1 : . Utilisez l’inégalité de Kraft pour montrer qu’il est possible de
construire un code préfixe binaire pour les caractères a . . . f avec les longueurs
de code suivants :
 Exercices
Exercice 2 :
Soit une source X d’alphabet ΩX = {a, b, c, d, e, f}
1. Quelle est l’entropie maximale pour une telle source ?
2. Quel est le nombre minimal de bits par caractère nécessaire pour un
codage binaire à longueur fixe de cette source ?
3. On dispose pour cette source de trois codes binaires :

(a) lesquels de ces codes sont sans préfixe ?

(b) Pour chacun des codes sans préfixe donner sa représentation sous
forme d’arbre binaire
Exercices
4. Supposons que la distribution des probabilités est la suivante :

a) Calculer l’entropie associée à cette distribution de probabilités

b) Quelle est la borne inférieure pour la longueur moyenne des mots de
code pour un binaire pour cette source ? Justifier la réponse.
c) Parmi les trois codes définis ci-dessus (question précédente) lequel est le
meilleur pour cette distribution de probabilités ?
Codage de source
 Rappel, entropies et schéma général de
communication
 Notations et exemples
 Codes préfixes – inégalité de Kraft
 Codes optimaux
 Théorème de Shannon
 Codes de Fano et de Huffman
 Codage arithmétique
 Code de Fano
 1 
 Code binaire respectant nx  log 2 
 p  x  
 Algorithme :
– Ordonner les symboles de la source dans l’ordre des
probabilités
– Grouper en deux ensembles d’égale probabilité, séparés avec 0
et 1
– Diviser chaque ensemble en deux sous-ensemble, séparés avec
0 et 1
– Continuer jusqu’à ce que chaque sous-ensemble ne contienne
qu’un seul symbole de la source

 Exemple :
– source avec 8 symboles A, B, …, H
– P(A) = 0,1, P(B) = 0,18, P(C) = 0,4, P(D) = 0,05, P(E) = 0,06,
P(F) = 0,1,P(G) = 0,07 et P(H) = 0,04.
– L’entropie de cette source sans mémoire est H= 2,55 bits par
symbole
 Exemple :

n   p x nx  2 ,64
x
L’efficacité de codage est 2,55/2,64, soit 96,6%
 Code de Huffman

 Code plus efficace que le code de Fano, décrit ici pour le cas
binaire mais généralisable à d’autres alphabets

 Algorithme :
– Ordonner les symboles de la source dans l’ordre des probabilités
– Isoler les deux symboles les moins probables et les distinguer avec
0 et 1
– Regrouper ces deux symboles en un seul nouveau en additionnant
leurs probabilités
– Recommencer jusqu’à ce que touts les symboles soient regroupés

 Exemple : comme précédemment

 Code de Huffman

n   p x nx  2 ,61
x
L’efficacité de codage est 2,55/2,61, soit 97,8%
 Code de Huffman

 Soit la source discrète X d’alphabet X={a1,…,ak-2,ak-1,ak} munie de la loi p.

Sans perdre de généralité, nous pouvons supposer que p(a1)≥ …≥ p(ak-1)
≥ p(ak) ≥0

 Nous définissons la source Y d’alphabet Y = {a1,…,ak-2,bk-1} munie de la loi

 Q(ai) = p(ai) pour i=1,…,k-2
 Q(bk-1) = p(ak-1) + p(ak)

 Nous voulons construire  un code prefixe de x.

 Si k=2, les mots de codes sont (a0)=0 et (a1)=1
 Si k>2, soit  un code de Huffman de Y
• (ai)= (ai) pour i=1,…,k-2
• (ak-1) = (bk-1)||0
• (ak) = (bk-1)||1
 Code de Huffman

 Propriété : le code d’Huffman est optimal

– On peut prouver qu’il existe un code optimal qui satisfait
» Si p(x) > p(y), alors nx = ny
» Les deux plus longs mots code ont la même longueur
» Les deux plus longs mots code ne diffèrent que par leur
dernier bit et correspondent au deux symboles les moins
probables

– On obtient le code d’Huffman en groupant ces deux

symboles les moins probables et en itérant
 Code de Huffman

Lemme : il existe un code préfixe optimal dans lequel les

2 lettres les moins probables sont codées par des
mots de longueur maximal. Ces 2 mots sont
identiques sauf pour leur dernier symbôle, ils sont de
la forme (m||0) et (m||1)

Lemme : si  est un code optimal de Y alors  est un

code optimal de X
 Erreur sur l’estimation de p(x)
 Dans de nombreux cas pratiques, p(x) n’est connue que par estimation.
 Quel est l’effet de coder une source de probabilité p(x) avec un code
optimisé pour q(x) ?
 Entropie relative D(p||q)

 D(p||q) : distance de Kullbach Leibler

 C’est une mesure de la distance entre deux

distributions de probabilité p(x) et q(x).

 Si on optimise un code pour p(x) et l’utilise pour q(x),

on aura besoin de H(p) bits pour décrire p mais de
H(p) + D(p||q) bits pour décrire q.

 px  
D p q    px .log  
x  qx  
Problèmes restants
Que reste-t-il à faire ?
 Points positifs
– Bornes théoriques
– Algorithmes pratiques
– Code “optimaux”

 Points négatifs
– Influence entre symboles successifs ignorée
– Inefficace si p(x) est fort différente de q-nx avec nx entier
– Complexe si on doit grouper les symboles par grands
groupes de taille L
– Inefficace si p(x) est mal estimée
Ordre d’une source

 Paramètres d’une source S

n

 Ordre 0 : i pi  1 l’émission de ci est indépendante des

émissions suivantes
 Ordre k : la probabilité dépend des k précédents caractères

 Processus de Markov discret : graphe orienté

étiqueté avec (pij, cij)
 Source de Markov
 Jusqu’à présent, on a considéré une suite de symboles générées
par une source comme des variables aléatoires indépendantes,
identiquement distribuées (i.i.d.), dès lors

p x1 x2  xL   px1 . p x2  p xL 

H X 1 X 2  X L   H X 1   H X 2     H X L 
H X  H X  1
n 
logq  logq  L

 En réalité, on a en général
p x1 x2  xL   p x1 . p x2 x1  p xL x1 x2  xL 1 
H  X 1 X 2  X L   H  X 1   H  X 2 X 1     H  X L X 1 , X 2 , , X L 1 
 Source de Markov
 En pratique, on considère des processus avec une mémoire limitée. Un
processus de Markov d’ordre 1 se définit par

p xn xn 1 xn  2  x1   p xn xn 1 
 Et donc,
p x1 x2  xL   p x1 . p x2 x1 . p x3 x2  p xL xL 1 
 De plus, ce processus est dit invariant si ces probabilités conditionnelles
ne dépendent pas de n
 Si {Xi} est une chaîne de Markov, Xn est appelé l’état au temps n.
 Une chaîne de Markov invariante est entièrement caractérisée par son état
initial et par sa matrice de probabilités de transition

pij  pxn 1  j xn  i 
 Source de Markov
 On peut calculer la distribution de probabilité à un instant à partir de
celle à l’instant précédent via

p  xn 1    p xn Pxn xn1 pij  pxn 1  j xn  i 

xn

 On appelle distribution stationnaire la distribution pour laquelle

p  xn  1   p  xn 
 Exemple :

p 0  
1-    
P  
  1   p 1 
 
 Source de Markov

 La distribution de (pi) est dite stationnaire si on a :

p j   pi pij pour tout j.

i

Posons H j    pij log pij .

j

Si pi est une distributi on stationnai re, le taux d' entropie est

H   pi H j
i

 Le taux d’entropie d’une chaîne de Markov d’ordre 1 est :

H  X    p xn  p xn 1 xn log 2  p  xn 1 xn 
xn xn1
 Exemple
 Si la chaine est donnée par une matrice de transitions P

P 1/ 4 3/ 4
3/ 4 1/ 4
La distribution stationnaire est [1/2 1/2] et

H  X    pxn  pxn1 xn  log2  pxn1 xn 

xn xn1

1 1 1 3  3  1  3 3 1  1 
H  X n 1 / X n     log 2    log 2     log 2    log 2  
2 4 4 4  4  2  4 4 4  4 

3 3
   
Taux d' entropie  H X n 1 / X n  log 4  log 
2 4
 Exercice 1

Une source X génère des symboles à partir d’un alphabet à 8 lettres

(A,B,C,D,E,F,G,H) avec des probabilités

– P(A) = 0.15 P(B) = 0.15

– P(C) = 0.06 P(D) = 0.1
– P(E) = 0.4 P(F) = 0.1
– P(G) = 0.02 P(H) = 0.02

• Quelle est l’entropie de cette source ?

• Générez le code de Fano pour cette source. Quelle est son efficacité?
• Générez le code de Huffman pour cette source. Quelle est son efficacité ?
• Comment faire pour trouver un code plus efficace encore ?
 Exercice 2

Parmi ces 4 codes, lesquels satisfont la condition de préfixe ?

C3 uniquement
Parmi ces 4 codes, lesquels sont à décodage unique ?
C3 et C4
Lequel est le plus efficace ?
C3, qui est optimal car nx=- log p(x)
Codage de source
 Rappel, entropies et schéma général de
communication
 Notations et exemples
 Codes préfixes – inégalité de Kraft
 Codes optimaux
 Théorème de Shannon
 Codes de Fano et de Huffman
 Codage arithmétique
 Codage arithmétique
 On a vu que le code de Huffman était optimal
 Mais il n'est efficace que si on s'approche de

1
nx  log
px 

 En pratique, cela requiert de grouper de nombreux symboles

ensembles.
 Cela pose un problème majeur : il n'y a pas de manière simple
de trouver le code de Huffman pour une suite de L+1 symboles
à partir de celui pour une suite de L symboles.
 Le code arithmétique résout ce problème.
 Code de Shannon-Fano-Elias
 On considère une source à m symboles
{1,2,...,m}. On définit fonction de distribution
cumulée modifiée
1
F  x    p a   p x 
a x 2
 On a évidemment F(a) != F(b) ssi a != b , et
donc au lieu de transmettre x, on peut
à la place transmettre le nombre réel F(x).

 Question: avec quelle précision doit-on

transmettre F(x) pour assurer un décodage
sans perte?
 Code de Shannon-Fano-Elias
Si on quantifie F(x) avec nx bits, il faut que la différence entre F(x) et sa
version quantifiée reste inférieure à la moitié de l'intervalle de hauteur p(x).

On choisit  1 
nx  log  1
 p x  
1 px 
F  x   F  x nx  nx 
2 2
Ce code a une longueur moyenne de

 1  
n   p x nx   p x  log
   1  H  X   2
x x  px  
 Exemple
 Source X = {1,2,3,4}, probabilités ¼,½,? ,?

Notons que ce code n’est pas particulièrement efficace, puisque n=2.75

alors que H(X)=1.75.
 Codage arithmétique
 Codage arithmétique = codage de Shannon-Fano-Elias sur des séquences de L
symboles successifs de la source. On note ces séquences

L 1
x  x1 x2  xL  x
L
xL
 On code F(xL) avec une précision
 1 
nx L  log 1
  
L 
px 
 Pour cela, il faut être capable de calculer efficacement p(xL) et F(xL).
On le fait de manière itérative. Pour p(xL), on a

   
p x L  p x L 1 p xL  symboles indépendants
p x   p x  p x
L L 1
L xL 1  Markov de mémoire 1
 Codage arithmétique
 Pour le calcul de F(xL), on suppose connu p(xL-1), p(xL), et
F x  L 1
 1
  p b   p x L 1
2
 
b  x L 1

 Dès lors,  
F xL   pa  
1
2
p xL  
a x L

 pb   px   
L 1 1
 c  p xL
b  x L1 c  xL 2

F x   L 1 1
 px
2
L 1
  1
  p x c  p xL
L 1
2
   
c  xL

 1 
F x   px 
L 1 L 1     pc x L 1   1 p x L
 2 c x  2
 
 L 
Où la dernière ligne est valable que pour les processus Markoviens. On
note que l’on est passé d’une somme sur a<xL qui peut avoir jusqu’à qL-1
termes, à une somme sur c<xL qui a au plus q-1 termes.
 Codage arithmétique
 Le résultat du codage arithmétique est un très long nombre réel. Mais
en pratique, tous les calculs peuvent se faire avec des nombres entiers.
C’est le schéma de transmission incrémental

 Tous comme pour le codage de Huffman, on doit connaitre la

distribution p(x). Il y a trois approches possibles
– Modèle fixe: on utilise un p(x) supposé connu

– Modèle semi-adaptatif: on fait deux passages sur la source, un pour

estimer les statistiques, l’autre pour coder. Il faut alors également
transmettre la table des probabilités

– Modèle adaptatif: on adapte les probabilités p(x) grâce aux symboles

déjà transmis.
Codage arithmétique
 Le premier avantage du codage arithmétique est que chaque
caractère peut être codé sur un nombre non-entier de bits.

 L'algorithme ne code pas les fichiers caractère par caractère

mais par chaînes de caractères, plus ou moins longues
suivant la capacité de la machine à coder des réels plus ou
moins grands.

 Un autre avantage du codage arithmétique est qu'il est un

codage adaptatif pour le cas général d'une source avec
mémoire.

 Le codage arithmétique est optimal dans le cas général des

sources avec mémoire.
 Codage arithmétique
 Proposition : Soit une source avec/sans mémoire, produisant N
symboles a0 a1 …, aN-1 selon la distribution de probabilité P(p0 p1 …,
pN-1)
2
H  p  n  H  p 
N
 Soit une séquence à coder x0 x1 …, xM de M symboles. La distribution
de probabilité des symboles de source vérifie la relation :
N 1

p
i 0
i 1

 On peut donc construire une partition du segment [0;1[ (de longueur 1)

en intervalles contigus I0 I1 …, IM, où chaque Ii est de longueur p(xi)
 L'idée du codage arithmétique est d'itérer la procédure d'Elias au fur
et à mesure du temps, afin de coder plusieurs symboles de source
successifs
 Algorithme de codage arithmétique

1. On initialise un premier intervalle avec deux bornes : la borne

inférieure Lc = 0 et la borne supérieure Hc = 1 (correspondant à la
probabilité de choisir un premier symbole x0 parmi tous les symboles
de la source). La taille de l'intervalle : taille=Hc- Lc

2. Cet intervalle est partitionné en N sous-intervalles [Lk;Hk[ en fonction

des probabilités de chaque symbole ak de la source. Ce sont les
partitions initiales avec longueur Hk - Lk =pk, Nous avons :
k 1 k
Lk  Lc  taille   p  xi  et H k  Lc  taille   p xi 
i 1 i 1

3. On choisit le sous-intervalle correspondant au prochain symbole xk

qui apparait dans la séquence. On redéfinit alors l'intervalle initial
[Lc, Hc[

Lc  Lc  taille  Lk et H c  Lc  taille  H k
 Exemple de codage arithmétique
Exemple : Soit la source discrète sur l'alphabet -2, -1, 0, 1, 2 qui définit une série
de 5 symboles. La probabilité de production de la source est p= (0.1; 0.2; 0.4;
0.2; 0.1). Coder la séquence de symboles (0, -1, 0, 2)
 Pour coder 0, -1, 0, 2, on divise l'intervalle [0, 1[ en 5 partitions initiales, puis
on se place sur le sous-intervalle correspondant au premier symbole (de
valeur 0), c.a.d. [0.3, 0.7[. taille(1)=0.4
 Pour le prochain symbole de la séquence, le symbole1, on subdivise la
partition initiale du premier symbole 0 en autant d'intervalles qu'il y'a de
symboles possibles.
 On procede recursivement pour tous les symboles de la

 sequence. Nous avons taille(2)=0.08, taille(3)=0.032, taille(4)=0.0032. Des

lors, on peut coder
 la sequence (0, -1, 0, 2) par tout nombre réel appartenant a l'intervalle [0,3928
; 0,396[.
 Le nombre 0,3945 code cette séquence. On le code avec 8 bits :

 0.3945 = 0 x2-1 + 2-2 + 2-3 + 0x2-4 + 0x2-5 + 2-6 + 0x 2-7 + 2-8 (01100101). Nous
utilisons donc 8/5 = 1,6 bits/symbole
Subdivision Codage Arithmétique
X={2, -1, 0, 1, 2} , p= (0.1; 0.2; 0.4; 0.2; 0.1). Séquence à coder (0, -1, 0, 2)