Introduction à la

Théorie de
l’Information

A. Quidelleur
SRC1 Meaux 2007-2008

Culture Scientifique et Traitement de l’Information

Module M2112 – Représentation de l’information

Théorie de l'Information 1
Plan
 Quantité d’information et entropie d’une source

 Le codage de source

 Introduction au codage de canal

 Introduction à la cryptographie

 Conclusion

Théorie de l'Information 2
« Théorie de l’information » ???
 Dans le langage courant, « information » est utilisé dans divers
contextes
 pour le journaliste : les actualités
 pour le policier : des renseignements
 Dans le domaine des télécommunications, la « théorie de
l'information » se préoccupe des systèmes de communication et de
leur efficacité.

 La théorie de l’information est récente (1948, publication de

l’article Mathematical Theory of Communications de Claude
Shannon). Shannon montre que l’information contenue dans un
message est une grandeur physique mesurable.

 Les domaines de la théorie de l’information

 le codage,
 la compression de données,
 la cryptographie.

Théorie de l'Information 3
Quantité d’information et
entropie d’une source

Théorie de l'Information 4
 Système de communication
bruit

Démodulateur
Modulateur
Source
information
codeur canal décodeur Récepteu

 Source : entité qui génère le message. Exemples :

 Une personne qui parle : message = mots prononcés
 Un ordinateur : message = bits égaux à 0 ou 1

 Canal : le support de la communication. Ex. : Une ligne

téléphonique, une transmission satellite, …

 Codeur : il met en forme le message de la source pour l’adapter au

canal. Ex. : Compression, cryptographie, code correcteur d’erreur…

 Décodeur : il restitue l’information émise par la source à partir de la

sortie du canal

 Modulateur : il met en forme le signal analogique émis sur le canal.

Théorie de l'Information 5
Contenu informatif d’un message
 Avant de coder le message (le transformer en une suite
de 0 et de 1), il est nécessaire de déterminer le contenu
informatif du message.

 Exemple
 La source transmet toujours le même message, la lettre A.
Son contenu informatif est nul, car le récepteur n’apprend
rien en recevant le message.
 La source émet soit oui, soit non. Elle fournit une
information et une seule au récepteur.
 La source émet le temps qu’il fera demain : le contenu
informatif est très riche, dans la mesure où le message de la
source peut prendre des valeurs très diverses.

 Finalement, un message est « riche » en information s’il

apporte une réponse à une situation de grande
incertitude, c’est-à-dire s’il peut prendre beaucoup de
valeurs différentes.
Théorie de l'Information 6
Contenu informatif d’un message et
codage
 Il est important de connaître le contenu informatif d’un
message avant de le coder, i.e. choisir les mots binaires
qui vont représenter le message.
 Or en télécommunication, on veut toujours économiser le
nombre de bits transmis pour
 Gagner du temps (ex. : téléchargement d’une page web sur
Internet : il faut qu’elle s’affiche rapidement)
 Faire passer le plus de messages possibles sur un même
support (par exemple, au cœur des réseaux téléphoniques,
on transmet les conversations de plusieurs utilisateurs sur la
même fibre optique).
 Influence directe sur le coût des transmissions…!
 Ainsi, on souhaiterait coder l’information pertinente du
message et elle seule !
 Mais comment mesurer le contenu informatif d’un
message ? La Théorie de l’Information fournit une unité
de mesure de la quantité d’information.
Théorie de l'Information 7
Entropie d’une source
 Considérons une source pouvant émettre N messages différents.
Notons pi la probabilité d’émission du message m i.
Message m1, probabilité p1
Message m2, probabilité p2
Source Message m3, probabilité
d’information

…
p3

Message mN, probabilité pN

 Par définition, on appelle entropie H(S) de la source S la grandeur,
exprimée en Shannon,

N N
 1
HS   pi log2 pi   pi log2 
 

i1 i1  pi 
L’entropie fournit une mesure de la quantité d’information
associée à la source.

Théorie de l'Information 8
Exemples
 On considère une source émettant des symboles
successifs égaux à 0 ou 1. La probabilité du 1 est 0,3.
Celle du 0 vaut 0,7. Calculez son entropie.
HS   0,7 log2 0,7  0,3 log2 0,3 0,88sh

 La source considérée transmet le résultat d’un lancé de

dé truqué : P(1)=P(6) = 0,2 ; P(2)=P(3)=P(4)=P(5) =
0,15.
HS 2 son
Calculez log 0,2  4  0,15log 0,15
0,2 entropie.
2 2
2,571sh

Calculez 1

P1 P2 l’entropie
P3 P4de
Pla 5source
P6 si le dé n’est pas truqué.
6
 1  1  Remarque : L’entropie est
HS 6   log2   2,585sh plus grande quand les
 6  6   de l'Information
Théorie messages sont 9
Cas de messages équiprobables

 Calculons l’entropie d’une source pouvant émettre

N messages équiprobables.
 La probabilité de chacun des messages est 1/N.
 1  1   1  1   1  1 
HS    log2      log2        log2  
 N    N    N    N      N     N
  
N fois
1  1  1
  N  log2    log2  log2 N
N  N  N

 On retiendra cette formule :

HS log2 N pour N messages équiprobables

Théorie de l'Information 10
Exemples

 Exemple 1
On considère une source transmettant toujours le
même message, la lettre A.

 Analyse intuitive
Qu’apprend le récepteur par cette source ? Rien,
puisque le message est toujours le même ! Cette
source ne produit aucune information utile.

 Analyse par la théorie de l’information

Le résultat de l’expérience est toujours le même (lettre
A). Le message peut prendre une seule valeur possible
: N=1
Par définition la quantité d’information (l’entropie)
associée à cette expérience est log2(1) = 0sh
Théorie de l'Information 11
Exemples

 Exemple 2
On considère une source pouvant transmettre deux
valeurs : oui/non. Les résultats sont équiprobables.

 Analyse intuitive
Qu’apprend le récepteur par cette source ? Quand la
source émet un message, le récepteur reçoit une seule
information : soit le résultat est oui, soit il vaut non.

 Analyse par la théorie de l’information

Deux résultats existent : « oui » et « non ». Ces résultats
sont équiprobables.
Par définition la quantité d’information (l’entropie)
associée à cette expérience est log2(2) = 1 sh. Le
récepteur reçoit une unité d’information.
Théorie de l'Information 12
Exemples
 Exemple 3
On considère une source pouvant transmettre trois valeurs
: oui/non/je ne sais pas. Les résultats sont équiprobables.

 Analyse intuitive
Trois résultats différents peuvent se produire. Le message
émis par cette source est « plus riche » en information que la
source de l’exemple 2. On peut dire que la quantité
d’information de cette expérience est supérieure à la
précédente.

 Analyse par la théorie de l’information

Trois résultats existent : « oui » et « non », « je ne sais pas ».
Ces résultats sont équiprobables.
Par définition la quantité d’information associée à cette
expérience est log2(3) = 1,58 sh.
Théorie de l'Information 13
Conclusion

 La théorie de l’information fournit un modèle mathématique

permettant de quantifier l’information émise par la source d’une
communication.

 Constat 1 : Plus les résultats d’une expérience peuvent prendre de

valeurs différentes, plus la quantité d’information mesurée est élevée.

Intuitivement, ce résultat est logique. Une source pouvant transmettre
beaucoup de messages différents fournit plus d’information qu’une source
transmettant une seule valeur.

 Constat 2 : Lorsqu’une source peut produire beaucoup de valeurs

différentes, l’incertitude quant au résultat de l’expérience est élevée.
Or la quantité d’information transmise est d’autant plus grande que le
nombre de résultats possibles est différent.

La quantité d’information reçue est d’autant plus importante que

l’incertitude est grande !

Théorie de l'Information 14
Propriété de l’entropie
 On admettra la propriété suivante, qui découle des constatations précédentes :
L’entropie d’une source S pouvant produire N messages différents est maximale lorsque les messages sont équiprobables.
 Ce qui signifie que la quantité d’information est maximale lorsqu’on a le plus de difficulté à prévoir le résultat.
 Exemple : La source émet deux symboles : A et B

 Cas 1 : La lettre A a « plus de chance » d’être reçue que B. On a moins d’information que dans le cas 2, où on est incapable de prévoir la
lettre reçue.

P(A) P(B) H(S)

Cas 1 0,8 0,2 0,722
Cas 2 0,5 0,5 1

Théorie de l'Information 15
Système de communication : codage
de source et codage de canal
 Maintenant que nous savons mesurer l’information contenue dans un
message, nous pouvons le coder.

 Le codage de source représente le message sous la forme la plus

économique possible en terme de nombre de bits
 Le codage de canal ajoute des informations permettant au récepteur de
reconstituer le message malgré les erreurs éventuellement apparues à
cause du bruit sur le canal.

Théorie de l'Information 16
Le codage de source

Théorie de l'Information 17
Enjeu du codage de source

 Le but du codage de source est de trouver une

traduction binaire des messages émis par la source
économisant les bits et tenant compte de leur
contenu informatif.

 Par exemple, si la source émet

 la lettre A avec la probabilité 0,8,
 et les lettres B, C, D et E avec la probabilité 0,05,
on sent intuitivement qu’il vaut mieux coder A avec
peu de bits, car cette lettre revient souvent, tandis
que B, C, D et E peuvent être codées sur un plus
grand nombre de bits.

Théorie de l'Information 18
Capacité d’un canal

 En pratique, le débit binaire autorisé sur un canal est

limité (influence du bruit, nature du support, etc. …).

 Le débit le plus élevé auquel on peut transmettre sur un

canal, quel que soit le message produit par la source,
est appelé la capacité C du canal.

Théorie de l'Information 19
Théorème de Shannon

 Le théorème de Shannon montre qu’on peut toujours

trouver un codage de source permettant de transmettre
à la capacité du canal si le débit Ds des symboles émis
par la source et l’entropie de la source vérifient
H(S)Ds  C
Pb : il ne dit pas comment le trouver !

 Exemple : On considère une source émettant les lettres

A, B, C, D et E avec les probabilités pA = 0,8 et pB = pC =
pD = pE = 0,05. Les lettres sont émises au débit Ds =
106 lettres/s. Le canal a une capacité C = 2 Mbit/s.
 Entropie de la source : H(S) = 1,12 sh
 H(S)Ds = 1,12.106 < 2.106
 Donc il existe un code permettant de transmettre ces
lettres sur le canal.
Théorie de l'Information 20
Exemple de recherche d’un codage de
source

 On considère une source mettant 800 lettres par minute

 Des lettres A avec une probabilité pA = 0,8
 Des lettres B avec une probabilité pB = 0,2
 Le canal utilisé présente un débit binaire Db = 10 bit/s

 1er essai : Codage direct

 On choisit par exemple
Lettre A  0 Lettre B  1
 Longueur moyenne des mots du code : Lmoy =
1bit/lettre
 Le débit binaire nécessaire sur le canal est alors
13,33 bit/s.
 Ce code ne convient
Théorie de donc pas.
l'Information 21
Exemple de recherche d’un codage de
source

 2ème essai : Codage fractionné

 On regroupe les lettres 2 par 2 et on code chaque groupe
de lettres par un nombre de bits qui décroît selon la
probabilité d’apparition du groupe de lettres (méthode de
Fano).
Nombre
Groupement
Probabilités Codage pondéré de
de lettres
bits
AA 0,64 0 0,64
AB 0,16 10 0,32
BA 0,16 110 0,48
BB 0,04 111 0,12
1,56

 Lmoy = 0,78 bit/lettre

 Débit nécessaire sur le canal : 13,330,78 = 10,4 bit/s.
 Ce codage ne convient pas. Cependant, il est meilleur que
le précédent. Théorie de l'Information 22
Exemple de recherche d’un codage de
source

 3ème essai : Codage fractionné

 On regroupe cette fois les lettres 3 par 3.
Nombre
Groupement
Probabilités Codage pondéré de
de lettres
bits
AAA 51,20% 0 0,512
AAB 12,80% 100 0,384
ABA 12,80% 101 0,384
BAA 12,80% 110 0,384
ABB 3,20% 11100 0,160
BAB 3,20% 11101 0,160
BBA 3,20% 11110 0,160
BBB 0,80% 11111 0,040
2,184
 Lmoy = 0,728 bit/lettre
 Débit nécessaire sur le canal : 13,330,728 = 9,7 bit/s. Ce
code convient.
Théorie de l'Information 23
Exemple de codage de source : La
méthode de Fano

 La méthode de Fano fournit un codage binaire

instantané (i.e. décodable à la volée). Elle est
proche de la méthode de Huffman, utilisée dans les
compressions JPEG et MPEG notamment (voir cours
SRC2).

 La méthode de Fano permet d’attribuer peu de bits

aux messages qui reviennent le plus souvent. Les
messages les plus rares sont codés par plus de
bits. On parle de codage à longueur variable ou
RLE (Run Length Encoding) ou code entropique.

Théorie de l'Information 24
Mode opératoire de la méthode de
Fano

1. Classer les messages de la source dans l’ordre des

probabilités décroissantes.

2. Diviser l’ensemble des messages en deux groupes

de probabilités aussi proches que possibles et
 Attribuer 0 par exemple au premier
 Attribuer 1 au second.

3. Recommencer les subdivisions successivement.

Théorie de l'Information 25
Exemple

 On reprend l’exemple précédent. La source émet

les lettres A et B avec les probabilités pA=0,8 et
pB=0,2. On groupe les lettres 3 par 3.
1er regroupement
probabilités
messages probabilités 1er bit
regroupées
AAA 51,20% 51,20% 0
AAB 12,80% 1
ABA 12,80% 1
BAA 12,80% 1
ABB 3,20% 48,80% 1
BAB 3,20% 1
BBA 3,20% 1
BBB 0,80% 1
Théorie de l'Information 26
Exemple

2ème regroupement
probabilités 2ème
messages probabilités 1er bit
regroupées bit
AAA 51,20% 0
AAB 12,80% 1 0
24,80%
ABA 12,80% 1 0
BAA 12,80% 1 1
ABB 3,20% 1 1
BAB 3,20% 24,00% 1 1
BBA 3,20% 1 1
BBB 0,80% 1 1

Théorie de l'Information 27
 Exemple

3ème regroupement
probabilités 2ème 3ème
messages probabilités 1er bit
regroupées bit bit
AAA 51,20% 0
AAB 12,80% 12,80% 1 0 0
Deux sous- ABA 12,80% 12,80% 1 0 1
regroupements BAA 12,80% 12,80% 1 1 0
ABB 3,20% 1 1 1
BAB 3,20% 1 1 1
10,40%
BBA 3,20% 1 1 1
BBB 0,80% 1 1 1

Théorie de l'Information 28
Exemple

4ème regroupement
probabilités 2ème 3ème 4ème
messages probabilités 1er bit
regroupées bit bit bit
AAA 51,20% 0
AAB 12,80% 1 0 0
ABA 12,80% 1 0 1
BAA 12,80% 1 1 0
ABB 3,20% 1 1 1 0
6,40%
BAB 3,20% 1 1 1 0
BBA 3,20% 1 1 1 1
4%
BBB 0,80% 1 1 1 1

Théorie de l'Information 29
 Exemple

5ème regroupement
probabilités 2ème 3ème 4ème 5ème
messages probabilités 1er bit
regroupées bit bit bit bit
AAA 51,20% 0
AAB 12,80% 1 0 0
ABA 12,80% 1 0 1
BAA 12,80% 1 1 0
ABB 3,20% 3,20% 1 1 1 0 0
BAB 3,20% 3,20% 1 1 1 0 1
BBA 3,20% 3% 1 1 1 1 0
BBB 0,80% 0,80% 1 1 1 1 1

Théorie de l'Information 30
Exemple
Probabilités décroissantes

Messages Probabilités Code

Longueur croissante
AAA 51,20% 0
AAB 12,80% 1 0 0
ABA 12,80% 1 0 1
BAA 12,80% 1 1 0
ABB 3,20% 1 1 1 0 0
BAB 3,20% 1 1 1 0 1
BBA 3,20% 1 1 1 1 0
BBB 0,80% 1 1 1 1 1

Théorie de l'Information 31
Intérêt pour le décodage

 Le code de Fano est un code à décodage direct.

 Il n’y a pas d’ambiguïté au décodage car aucun

mot n’est la début d’un autre mot.

Théorie de l'Information 32
Introduction au codage de
canal

Théorie de l'Information 33
 Enjeu du codage de canal

 Le codage de canal rajoute de l’information pour

permettre au récepteur de détecter ou corriger les
erreurs éventuellement apparues.
 Comment le récepteur lit-il les données reçues ?
 Il échantillonne le signal physique reçu à intervalle
de temps fixe, au milieu du bit. Suivant le niveau de
tension lu, il déduit la valeur du bit : 0 ou 1.

Horloge

Signal électrique
5V
reçu 0V

Message 0 1 1 0 1 0 0 1 1 1
reconstitué
Théorie de l'Information 34
 Enjeu du codage de canal

 D’où viennent les erreurs ?

Le signal est déformé sur le
canal : l’échantillonnage peut
se faire sur une perturbation.

Pic de bruit

A l’échantillonnage, le
récepteur interprète le niveau
de tension comme un 0.

 Conclusion : Puisque le récepteur ne peut se fier au

signal électrique reçu, on va rajouter des bits dans les
messages qui permettront de repérer les erreurs.
Théorie de l'Information 35
Détection/correction d’erreur

 Certains codes permettent de détecter des erreurs,

d’autres de détecter et corriger les erreurs.

 La correction d’erreur contraint à ajouter plus de

bits que la détection d’erreur.

 Par conséquent, on adopte un code correcteur

d’erreur quand on ne peut pas retransmettre les
messages :
 Transmission dans un seul sens (émission TV)
 Transmission satellite (la retransmission prend trop
de temps)
 Transmission en temps réel.
Théorie de l'Information 36
Conclusion
 Les techniques de détection et correction d’erreurs seront étudiées
dans le cours sur la transmission en bande de base (semestre 2).

 Ce qu’il faut retenir

 Le codage de source a pour but de transmettre le contenu informatif du
message en économisant les bits.
 Le codage de canal rajoute au message des bits qui seront utilisés par
un algorithme de réception pour déterminer s’il y a des erreurs et les
corriger éventuellement.
 Paradoxalement, le codage de canal ajoute de la redondance, alors que
le codage de source a pour tâche de l’éliminer !
 C’est le prix à payer pour garantir la qualité de la communication.
 La solution est de bien connaître le canal, afin de déterminer la
probabilité d’erreur et de ne rajouter que les bits strictement
nécessaires.

Théorie de l'Information 37
Introduction à la
cryptographie

Théorie de l'Information 38
Codage  cryptographie

 Le codage sert à mettre en forme le signal binaire pour

l’adapter au canal : économie de bits / détection –
correction d’erreurs.

 La cryptographie consiste à chiffrer le message émis

dans le but d’assurer :
 La confidentialité du message : seul son destinataire peut
le lire
 L’authenticité du message : le destinataire est sûr que le
message a été émis par la bonne personne
 L’intégrité du message : une tierce personne n’a pas pu
modifier le contenu du message en cours de transmission

Théorie de l'Information 39
La cryptographie

 La cryptographie repose sur des algorithmes de

chiffrement utilisant une ou deux clés de chiffrement.
 Exemple : Chiffrement de César : décaler les lettres de
l’alphabet de n rangs. n est la clé.

 Les clés sont des nombres binaires très grands (jusqu’à

plusieurs centaines de bits). Plus la clé est grande, plus
l’algorithme est difficile à « casser ».

 La cryptographie sera étudiée dans le cours de sécurité

des réseaux (module Administration et Sécurité des
Réseaux, semestre 2).

Théorie de l'Information 40
Conclusion du chapitre

Théorie de l'Information 41
De la théorie de l’information à la
transmission du signal

 Nous nous sommes intéressés au contenu du

signal.

 Maintenant il s’agit de voir comment transporter le

signal sur un support physique (électrique,
lumineux, ou ondes).

 Dans le prochain chapitre, nous verrons comment

représenter physiquement un message binaire. On
ne s’intéressera plus au contenu informatif du
message, mais à sa forme physique.

Théorie de l'Information 42
Bibliographie

« Théorie de l’Information », R. Beauvillain, ENSEA,

support de cours, 1998.
 http://encyclopedie.snyke.com/
 « Théorie de l’Information et Codage », M. P. Béal
(université de Marne La Vallée) & Nicolas Sendrier
(INRIA), mars 2004

Théorie de l'Information 43