Théorie de

l’information et codage

Azza Ouled Zaid

Institut Supérieur d’Informatique
1ére année Cycle d’Ingénieurs
 La théorie de l’information

 La théorie de l’information donne un sens précis à la

notion d’information, de façon à ce quelle devienne
techniquement utilisable

 Fournit des outils de modélisation et d’analyse dans

le domaine de traitement de l’information

 C’est fut conçue par Claude Shannon en 1948 pour

répondre à certaines interrogations fondamentales
dans le domaine des techniques de communication
 Objectif du cours

 2 sujets complémentaires:
 La notion d’information
 fournir les bases nécessaires à la mise en œuvre
d’approches probabilistes
 Les méthodes de codage de l’information
 donner les grands théorèmes de la théorie de
l’information
 donner un aperçu représentatif des divers
techniques de codage
 Plan du cours

 Introduction au systèmes de communication

 Modélisation probabiliste de l’information

 Les grands théorèmes de la théorie de

l’information
 Codage source
 Codage canal
Introduction au systèmes de
communication
 Système de communication

Source d’information destination

message message

signal

source de bruit
émetteur
recepteur
Système de communication
 Information : séquence de signaux, correspondants
à des règles de combinaisons précises, transmises
entre une source et un récepteur par l’intermédiaire
d’un canal

 Message : lot d’information formant un tout

intelligible ou exploitable et transmis en une seule
fois

 Signal : phénomène physique porteur d’une

information et pouvant représenter des données
Système de communication
 Schéma de communication idéal
Phase de codage
Signal codeur de canal
original codeur de source
discret

modulation

Canal continu

démodulation

Phase de décodage

décodeur de canal Signal

discret décodeur de source reçu
Système de communication
 Codeur source : code les messages émis de façon
à éliminer la redondance

 Codeur canal discret : code les message à l’entrée

du canal en introduisant la redondance sous forme
appropriée pour permettre l’utilisation du canal
sans erreurs

 Modulation/Démodulation : conversions physiques

nécessaires à l’utilisation du canal.
Codage source/canal

 Efficacité : Pour faire parvenir une quantité donnée

d'information a l'utilisateur, utiliser le minimum de
ressources.

 Fiabilité : Restituer a l'utilisateur une information

suffisamment fidèle a celle produite par la source.
 Codage de l’information
 La théorie de codage développe des techniques
visant à concevoir des systèmes de stockage et
de transmission de l’information

 Le codage vise à développer des algorithmes de

représentation de l’information
 Atteindre les limites de possible définies par la
théorie de l’information
 Répondre aux préoccupations techniques
(mémoire, vitesse, robustesse)
La théorie de l’information
 Objectif:
 Déterminer les performances limites d’un
système de communication en présence
de perturbation aléatoires

 Résultats fondamentaux:
 Réaliser une transmission d’information
exempte d’erreur, malgré l’existence du
bruit de fond
 La théorie de l’information: discipline
mathématique
 3 questions fondamentales :
1. Quelle est la limite en matière de compression
réversible des données numériques?
2. Quel est le débit maximal de transmission fiable sur
un canal bruité?
3. Sous quelle condition un code de chiffrement est
sûr?

 Fournir des outils mathématiques pour répondre à

ces questions, ainsi que les algorithmes de
codage qui permettent d’atteindre pratiquement
ces limites théoriques
 La théorie de l’information

 Mettre en évidence comment les limites de Shannon

pourraient être réalisées, au moyen de codes
appropriés

 Ne donne pas lieu à des codes pratiquement

réalisables

 Certains codes pratiquement réalisables visent à

s’approcher au mieux des limites de Shannon
 La théorie de l’information

 Donner une définition quantitative à la notion d’information

 Aspects :
 Incertitude (comportement imprévisible)
• mesurable  notion quantitative de l’information
• un message est plus significatif s’il est moins probable

 Interprétation : véracité, valeur,…,

• dépend du contexte et de l’observateur  non mesurable
Calcul des probabilités
La théorie de codage

Codeur source Codeur canal

Comportement aléatoire

Calcul des probabilités

 La théorie d’information
 La théorie d’information traite de phénomènes
imprévisibles
 Calcul de probabilités

 La modélisation probabiliste de l’information

fournie une introduction aux mesures
d’information et aux divers aspects de
raisonnement probabiliste.
 Notion de probabilités
 Le calcul des probabilités est un outil
mathématique qui permet de représenter et de
manipuler des situations dont l’issue est aléatoire
(incertain)

 Une expérience est aléatoire si on ne peut pas

prévoir par avance son résultat

 Le calcul des probabilités permet de modéliser et

analyser les expériences aléatoires
 Notion de probabilités
 Pour étudier une expérience aléatoire on s’intéresse à

  : l’univers de tous les résultat possibles,

• défini en fonction des objectifs visés
  : un événement particulier parmi ceux possibles
• un événement est une assertion logique vérifiable,
relative aux résultats d’une expérience
 Notion de probabilités

 A tout événement correspond une assertion logique à

laquelle on peut faire correspondre un sous-ensemble
de .

 A tout    on peut associer un événement

élémentaire correspondant au singleton {},

 La probabilité associé à un événement un nombre

positif entre 0 et 1 qui représente le degré de certitude
qu’on peut associer à celui-ci à priori
 si p()=1   est un événement certain
 si p()=0   est un événement impossible
 Notion de probabilités
 Un espace probabilisé est défini par le triplet (, , p()) où:
  : l’ensemble de résultats possibles d’une expérience

  : un -algébre d’assertions logiques relatives aux résultats

de l’expérience

 p(.) : une loi de probabilité qui associe à chaque assertion logique A

de  un nombre p .   0 ;1 

Un -algébre est un ensemble de parties de  qui correspondent à toutes

les assertions logiques dont on se donne le droit de discuter dans le cadre
d’un problème
Espace des réalisations et
d’événement
 L'espace des réalisations est l'ensemble de tous
les résultats possibles d'une expérience aléatoire,
et sera représenté par .

 Chaque résultat distinct possible est appelé

événement simple, ou élémentaire, ou on dira
encore qu'il est un élément de l'espace des
réalisations.
 Espace des réalisations et
d’événement
 Chaque fois que l'on effectue une expérience,
un et un seul événement élémentaire peut se
produire.

 Les événements élémentaires peuvent, être

combinés pour constituer des événements
composés, qui correspondent, de cette façon,
à un ensemble événements élémentaires qui
possèdent une certaine propriété commune.
 -algébre: définition
 Un -algébre  d’événements défini sur un univers 
est une partie de 2 qui vérifie les propriétés
suivantes:
 
 A    -A  
  A1 A2,,..,    Ai  

 Une partie A={A1,,.., An}   forme un système complet

d’événements si:
  i  j , Ai  Aj = 
 Ai =  (ils couvrent )
 Un système complet correspond à une variable aléatoire
discrète
Système stochastique

P(z)
perturbations

observations Système : observations

en entrée en sortie
relation probabiliste P(y)
P(x) p(y/x,z)
 Exemple: diagnostique médical

 Expérimentateur : médecin particulier

 L’expérience : le premier diagnostique de l’année (2
janvier 2020)
  : L’ensemble de tous les patients que le médecin est
susceptible de diagnostiquer

 Le médecin ne peut pas prévoir le patient qui va se

présenter devant lui
Exemple
Les deux premiers bébés qui seront nés demain à Tunis.
 ={FF,FG,GF,GG} où F et G représentent fille et garçon,
respectivement.

 L’événement "naissance d'une seule fille" est un

événement composé A qui regroupe deux
événements élémentaires: A={FG,GF}.
 Exemple: réseaux informatique

 Plaçons nous à un nœud particulier du réseau Internet

et observons les messages qui est transit pendant une
journée donnée

 Un résultat particulier est la suite de messages qui

transite pendant la période d’observation

  : est l’ensemble de toutes les suites de messages

possibles pouvons transiter durant une journée
 Exemple: système source canal

 Résultat de l’expérience :
• L’observation d’un message émis par la source et déformé par
le canal et réception du message déformé par le récepteur

 L’univers est l’ensemble des couples (message émis,

message reçu)  utilisation du canal
 Un événement (assertion logique) est défini par
Le message reçu est différent du message émis

 Le calcul de probabilité  déterminer la fiabilité et l’efficacité du

système de communication en fonction du système de codage
utilisé
assertion : sous ensemble des utilisations possibles du canal
 Espace de probabilités (, , p(.))

(Kolmogoroff, 1933)
 Un espace de probabilités formel consiste dans la
définition de trois entités: (, , p) où
(i)  est l'espace des réalisations;
(ii)  est une famille d’événements en  , telle que:
• (a) A, B    A  B  
• (b) A    A.  
(iii) P est une mesure de probabilité définie sur les
éléments de , qui satisfait les axiomes suivants:
(a) P( ) = 1
(b) P( A)  0

(c) A  B =   P ( A  B ) = P ( A ) + P ( B )
Axiomes de kolmogorov
 On appelle probabilité sur (,  ), ou loi de
probabilité, la fonction p(.) définie sur  tel que:
1. P(A) [0,1],  A   ,
2. P()=1,
3.  A1 A2,,..,   incompatibles : p i Ai   i p  Ai 

 Propriétés
1. p()=0
2. p(-A)=1 - p(A)
3. A  B  p(A)  p(B)
4. P(AB) = p(A) + p(B) – p(AB)
5.  Ai pi Ai   i p Ai 
 Théorème des probabilités totales

 Soit B={B1,…, Bn} un système complet

d’événements, alors
n
A   , p A   p A  Bi 
i 1

 Le théorème des probabilités totales permet de

décomposer le problème en sous problèmes
 Exemple
 Dans le cadre d’un schéma de communication on peut
définir 26 événements
 A : l’ensemble de réalisations dont le message source
commence par la lettre a
 B : l’ensemble de réalisations dont le message source
commence par la lettre b
:
 Z : l’ensemble de réalisations dont le message source
commence par la lettre z

Peut on dire que l’ensemble des messages source forme un

système complet d’événements?
 Exemple

 Soit {A, B,…,Z} le système complet d’événements et soit E’

l’événement qui désigne les réalisations correspondant à
une erreur de transmission (message reçu différent du
message émis)

    
p E'  p E'  A    p E'  Z 
Éléments de base du calcul
de probabilités
Loi de probabilité conditionnelle
 Si B est de probabilité non nulle,

p A  B 
p A B  
p B 

Si B  A  p A B   1

 La réciproque n’est pas vraie

Propriétés
A, B    A  B   et p A  B  est défini sur 
 p A B   0
 p / B   1

 A  B  B  p  A  B   p B   p  A B   1

p i Ai   B  pi  Ai  B 
 p i Ai B   
p B  p B 
p Ai  B 
    p Ai B 
i p B  i
 Notion d’indépendance
d’événements
 Définition 1 : événements indépendants
 A est indépendant de B si p(A/B)=p(A). Le fait de savoir que B est
réalisé ne change en rien la probabilité de A

A B
 Définition 2 : indépendance conditionnelle
 Soient A, B, C trois événements et p(C)0. On dit que A
est indépendant de B conditionnellement à C

A  B C si pA B  C   p A C 
p A  B C 
Montrer que pA B  C 
p B C 
 Exercice: Un espace de réalisations est constitué
de quatre événements élémentaires S= e1 , e2 , e3 , e4 
équiprobables. Soient les événements A  e1 ,e2 , B  e2 , e3 
et C  e , e  .
1 3

 Montrer que P ( A, B )  P ( A, C )  P ( B , C )  1 / 4
et, donc, que pris deux à deux, les événements
sont tous statistiquement indépendants. Vérifier
aussi que 0  P ( A , B , C )  P ( A ) P ( B ) P ( C )  1 / 8 et
que, donc, si on considère les trois simultanément,
ils ne sont pas indépendants.
Notion d’indépendance
p(A), p(A)0,1 :
1.  est indépendant de tout autre événement
2. Un événement de probabilité nulle est indépendant de
tout autre événement
3. Tout événement est indépendant de 
4. Tout événement est indépendant de tout événement
certain
5. A est indépendant de B  p(AB)=p(A).p(B)
6. A est indépendant de B 
B est indépendant de A
-A est indépendant de B
A est indépendant de –B
-A est indépendant de -B
 Indépendance mutuelle

 Soient n événements, on dit que A1,…, An sont mutuellement

indépendants si on a

pi Ai    i p  Ai 
 Formules de Bayes
 Les formules de Bayes permettent d’écrire p(A) et p(B/A) en
fonction de p(A) et p(B/A)

1ère formule de Bayes

P A B PB 
p  B A 
p  A

Théorème des probabilités totales

si B ={B1,…, Bn} est un système complet d’événements, le théorème
des probabilités totales peut s’écrire comme suite:

p A   P A Bi PBi 
i
 Variables aléatoires
 Une variable aléatoire est un codage de l'espace des
réalisations, qui fait correspondre à chaque événement
élémentaire une valeur numérique (réelle). On associe ainsi à
chaque résultat possible   d'une certaine expérience
aléatoire un nombre réel x  X  .
 De cette façon, on peut oublier la nature particulière de
l'espace des réalisations et dire, au lieu que l’événement 
s'est produit, que la valeur x de la variable aléatoire s'est
produite.
 Les variables aléatoires héritent les caractéristiques de
l'espace des réalisations original, et seront discrètes ou
continues selon que  est discret ou continu.
 Une v.a. (variable aléatoire) discrète X  x1 ,, x2 , x3 ,..... est
caractérisée par la définition de la probabilité P ( xi ) de chaque
valeur possible de la variable.
Variables aléatoires
 Définition:
Soient un espace probabilisé (, , p()) de départ et un
univers ’ de destination muni d’un algèbre
d’événement ’, une fonction f(.) de  dans ’ est une
variable aléatoire si elle possède la propriété suivante

 
A'   ' , f 1 A'   ,
f 1 A  désigne    , f   A 
' '

Si cette propriété est vérifiée alors f induit une loi de probabilité sur
(’ , ’ ) définie de la manière suivante :

    
p f A'  p f -1 A'
 Variables aléatoires
 f (.) est définie sur un espace probabilisé qui est compatible avec
les algèbres des événements définis dans son espace d’origine
et de destination et qui induit une loi de probabilité sur l’espace
de destination à partir de loi de probabilité définie sur l’espace de
départ
 La v.a offre une information dense sur l’expérience
 Variables aléatoires
 Soit une v.a X à valeur dans ’ défini par une fonction f (.),
et une certaine fonction (.) définie sur ’ et à valeur dans
’’. Alors si (.) a le statut d’une v.a sur ’ . La fonction
composée o f (.)= (f()) définit également une v.a sur 
 Variables aléatoires discrètes
 Une v.a est discrète si l’ensemble de ses valeurs possibles est fini
 X={x1,…,xk} désigne l’ensemble des valeurs possibles de la v.a
 La v.a est désignée par X(.) ou X.
 p(xi) est la probabilité de { , X() =xi}
 p(X)pX
Couple de VA et conditionnement
 Soient les couples de v.a (X,Y) tels que X et Y
prennent leurs valeurs dans un ensemble fini
désigné respectivement par X={X1,…,Xk} et
Y={Y1,…,Yl} munis de leur -algébre maximal.

 Le couple prend ses valeurs dans XxY munis de -

algébre produit, qui est également maximal
 Couple de VA et conditionnement
 Loi conjointe : la loi de probabilité du couple Px,y est
déterminée complètement par la connaissance des kl
nombres

 
pi , j  p X  X i   Y  Y j   p X i ,Y j ,i  1, , k ,j  1, ,l
 p
i j
i,j 1

Table de contingence
Lois marginales
 La loi marginale de X est
l
pi ,.  p X  X i    pi , j
j 1

 La loi marginale de Y est

p., j  p Y  Y j    pi , j
k

i 1
Lois conditionnelles
 La loi conditionnelle de X connaissant Y est :

pX i
/ Yj  
 p X  X i Y  Yj 
pi , j
p., j

 La loi conditionnelle de Y connaissant X est :

pY j / X i  p Y  Y j X  X i  
pi , j
pi ,.
Mesure quantitative de
l’information
Quantité d’information d’un
message
 Exemple: source binaire avec symboles indépendants
i{0,1}
 p(1) : probabilité pour que le prochain symbole soit égale à 1
 p(0)=1-p(1) : probabilité pour que le prochain symbole soit égale à 0
 Désignons par h() l’information apportée par un symbole 

 1 
alors  h   f   avec f . croissante
 p  
lim x1 f  x   0 (information nulle si l' évenement est certain)
d' autre part, si les événements sont indépendants,
pour deux symboles successifs 1 ,2 nous devons avoir h1 ,2   h1   h2 
   
mais : h1 ,2   f 
1 1
  f  
 p1 ,2    p1  p2  
 f  x , y   f  x   f  y   f .log.
Quantité d’information d’un
message
Définition
Soit , un ensemble fini de messages possibles, la quantité
d’information d’un messagei

hi   log 2  pi 

 La fonction h(.) définit une variable aléatoire sur .

 L’observation d’un message i apporte une information propre
égale à h(i) .
Quantité d’information d’un
message

A   un événement de probabilité p(A), la

quantité d’information reçue par l’observateur qui
est informé par la réalisation de cet événement
vaut :
h A  log 2  p A

 h(A) est d’autant plus grande que l’événement

était à priori improbable % à l’observateur
 si un événement est à priori très probable,
l’information qui lui est associé sera faible
h A  0 , pA   0 : h A  
 Information conditionnelle
h A  B   log 2  p A  B   log 2  p  A p B A
                log 2  p A  log 2  p B A

Si A et B sont indépendants, pB A  p B 

 h A  B   h A  hB 

la quantité d’information conditionnelle de B sachant que

A est réalisé par: hB A   log 2 pB A 
hB A  0
h A  B   hB   h A B   h A  hB A
En particulier : A  B : h A  B   h A  hB 
d' où : h A  B   maxh A, hB 
 Information mutuelle entre 2
événements
Définition : i  A; B   h A  h A B 
p A B  p A  B 
Ainsi : i  A; B   log 2  log 2  i  B; A 
p  A p  A p B 
 l' information mutuelle est symétrique

Discussion
h A B  peut être supérieur  ou  égale à h A
l' information mutuelle peut être positive     ou    nulle
l' information mutuelle est nulle si les événements sont indépendan ts
Cas particuliers :
si  A  B,  p A B   1  h A B   0  i  A; B   h A
si  A  B  hB   h A
Peut on dire que le contraire est vrai
 Entropie d’une source stationnaire sans
mémoire

Source : émet à des instants successifs ti{t1, t2, …,tn}

des symboles successifs s(t) faisant partie d’un alphabet fini S={s1,
…,sn}
Supposition : les symboles successifs sont indépendants et émis
selon une même distribution de probabilité (indépendants de t)
pi=p(s(t)=si)  la source est dite stationnaire sans mémoire

 stationnaire: la distribution de probabilité qui caractérise l’émission

d’un symbole ne dépend pas du temps.

 sans mémoire : un symbole est statiquement indépendant

des symboles émis précédemment
 Entropie d’une source sans
mémoire
 L’entropie ou la quantité d’information moyenne associée à
chaque symbole de la source sans mémoire est définie
comme l’espérance mathématique (E{.}) de l’information
propre fourni par l’observation de chacun des symboles
possibles S={s1, …,sn}

H S   Ehs     p log i 2 pi
i 1,, n

 La source est stationnaire sans mémoire, il s’agit alors

de l’information moyenne par symbole
 Entropie d’une source sans
mémoire

 Si F désigne la fréquence d’une observation de la

source, alors F.H(S) mesure l’information moyenne
par unité du temps: Shannon/seconde

 L’information par symbole fournie par un long

message produit par la source converge presque
sûrement vers H(S)
 Cas particulier (n=2)
 Dans le cas d’une source binaire, X={x1,x2}, on a :
H  X    plog 2 p  1  p log 2 1  p   H 2  p , 

avec p, la probabilité de l’une des deux variables de X

Propriétés de H 2  p ,
H 2  p   H 2 1  p ,
H 2 0   H 2 1  0
H 2 0 ,5   1 et H 2  p   0 ,

 On note que H(p) est maximum pour p = 0.5, c.à.d quand les
symboles de la source sont équiprobables
Entropie conjointe

 Au lieu d’une seule variable aléatoire X, considérons deux

variables aléatoires X et Y. En terme de probabilités, on a

p A, B   P A.PB A  PB .P A B 

 L’entropie jointe H(X,Y) est l’entropie que l’on obtient en

considérant (X,Y) comme une seule variable aléatoire
vectorielle.
 Entropie conjointe
Entropie conjointe de deux v.a
 Soient X={x1,…,xn} et Y={y1,…,ym} deux v.a discrètes définies
sur un même univers , alors l’entropie conjointe de X et Y
est définie par :

H  X , Y    p xi , y j log 2 p xi , y j 

n m

i 1 j 1

                H  X , Y   H Y , X 

Entropie conjointe de plusieurs v.a

   
n1 nm
H  X 1 , X 2  , X m      p x1,i1 ,  , xm,im log 2 p x1,i1 ,  , xm ,im
i1 1 im 1
 Entropie conditionnelle
 On peut définir l’entropie conditionnelle comme
l’espérance des entropies des distributions conditionnelles
p(x|Y=y)
 L’entropie conditionnelle moyenne de X connaissant Y par :

H  X / Y    p xi , y j log 2 p xi y j 

n m

i 1 j 1

H  X ,Y   H  X   H Y X   H Y   H  X Y 
• L’information combinée des variables X et Y vaut l’information
de X plus l’information restant dans Y une fois X connu
Information mutuelle moyenne
 L’information mutuelle moyenne associée à un couple de
v.a est définie par :

 p xi , y j  
I  X , Y    p xi , y j log 2 
n m

 px  py  
i 1 j 1  i j 

I  X ,Y   I Y , X 
 Information mutuelle moyenne

I  X ,Y   H  X   H  X / Y   H Y   H Y / X 
 H  X   H Y   H  X ,Y 

 En terme de paradigme de Shannon, et on supposant que

X le message émis par la source et Y le message reçu par
le destinataire, cette décomposition revient à dire que
l’information mutuelle moyenne est égale à
 l’information émise diminuée de l’indétermination, quant au
symbole émis, qui subsiste quand le symbole reçu est connu
 Symétriquement : à l’information reçue diminuée de
l’indétermination, quant au symbole reçu, qui subsiste quand
le symbole émis est connu
 Information mutuelle moyenne
 Relations entre I(X,Y) et H(X),H(Y),H(Y|X),H(X|Y),
H(X,Y)

I  X ,Y   H  X   H  X / Y 
I  X ,Y   H Y   H Y / X 
I  X ,Y   H  X   H Y   H  X ,Y 
I  X ,Y   I Y , X 
I X , X   H X 
Exercice
 Soit la table de contingences
Y1 Y2
X1 1/3 1/3
X2 0 1/3
 Calculer (logarithmes en base 2)
H  X , H Y 
H  X Y , H Y X 
H  X ,Y , H Y , X 
H Y   H Y X 
I  X ,Y 
 Propriétés

H  X   0 et H  X ,Y   0 et H  X Y   0

H  X ,Y   maxH  X , H Y 

H  X ,Y   H  X   H Y 
2  H  X ,Y   H  X   H Y 

H  X ,Y   H  X   H Y   2H  X ,Y 
Propriétés de la fonction Hn(…)
n
 Notation : H n  p1 ,  , pn    pilog 2 pi
i 1 n
pi une loi de probabilité discrète  pi  0 ,1 et  pi  1
i 1

 Positivité :H n  p1 , , pn   0
1
 Maximum :  pi  i
n
 Concavité : soient (p1,…,pn) et (q1,…,qn) deux lois de
probabilité discrètes et [0,1] alors

H n p1  1   q1 , , pn  1   qn 


H n  p1 , , pn   1   H n q1 , , qn 
Maximum de la fonction entropie
 Lemme: inégalité de Gibbs
soient (p1,…,pn) et (q1,…,qn) deux lois de probabilité discrètes
sur un même univers fini A, on a
n
qi
 pilog 2
i 1 pi
0

L’égalité ait lieu ssi  i : qi=pi

 Théorème :
H n  p1 ,  , pn   log 2 n 

L’égalité ait lieu ssi  i : pi=1/ni