Elements theorie information.pdf

Ecole Nationale Polytechnique dOran

Dpartement de Gnie Mcanique

Automatisation des Moyens de Fabrication

ELEMENTS DE

THEORIE DE LINFORMATION

(Notes de cours)

A. NOUREDDINE

5 anne PEST gnie mcanique 2013/2014

Elments de thorie de linformation 2/22

Cours AMF - 5 anne PEST Gnie Mcanique - ENP Oran - 2013/2014 A. NOUREDDINE

SOMMAIRE

1. Introduction

2. Gnralits

3. Exemples dinformation

4. Notion de quantit dinformation

4.1. Problme

4.2. Hypothses supplmentaires

4.3. Entropie, formule de Shannon

4.4. Exemple

5. Schma gnral de la communication

5.1. Le canal

5.2. Hypothse sur la source

5.3. Sources dinformation

5.4. Codage de l'information

6. Thorie de linformation et automatisation

7. Rappels de probabilits

Quelques rfrences bibliographiques



Elments de thorie de linformation

1. Introduction

En guise dintroduction nous allons considrer le problme suivant :

Dans une usine de fabrication de pices mcaniques, un systme de contrle de qualit plac

lextrmit de la chane de fabrication dun arbre fournit 3 rsultats suivant les valeurs

obtenues pour son diamtre :

B (bon)

D (dfectueux)

V ( vrifier)

dans des proportions de 60% (bon), 10% (dfectueux), et 30% ( vrifier).

Le rsultat de ce contrle est transmis un centre de gestion par une liaison infrarouge

unidirectionnelle, modlise par un canal ayant un dbit de 96 bits/s et une probabilit

derreur de 1%.

La cadence de fabrication (qui tait dune certaine valeur infrieure 180 000 pices/heure)

doit tre augmente 180 000 pices/heure.

Le problme est de dterminer si le systme de transmission entre le contrle et le systme de

gestion ayant donn satisfaction avant laugmentation de la cadence, va supporter cette

augmentation. autrement dit, faut-il changer le systme de transmission ou bien peut-on le

garder tel quel ?

Pour rpondre cette question nous devons bien videmment examiner la capacit du canal

transmettre toutes les informations ncessaires vers le systme de gestion.

Cest la rsolution de ce type de problme que va contribuer une somme de connaissances

regroupes dans une thorie appele Thorie de linformation .

2. Gnralits

La thorie de linformation a t cre par C. E. Shannon dans les annes 40. Il sagit dune

thorie mathmatique qui se proccupe des systmes dinformation, des systmes de

communication et de leur efficacit.

Elle fournit une mesure quantitative de la notion dinformation apporte par un message (ou

une observation).

Les systmes de communication sintressent aux moyens de transmettre une information

depuis la source jusqu un utilisateur travers un canal (figure 1).



La nature de la source peut tre trs varie. Il peut sagir par exemple dune voix, dun signal

lectromagntique ou dune squence de symboles binaires

Le canal peut tre une ligne tlphonique, une liaison radio, un support magntique ou

optique

La transmission de linformation peut se faire dans lespace ou dans le temps.

Le codeur reprsente lensemble des oprations effectues sur la sortie de la source avant la

transmission.

Ces oprations peuvent tre par exemple :

la modulation

la compression

le brouillage

lajout de redondance.

Le dcodeur doit tre capable, partir de la sortie du canal, de restituer de faon acceptable

linformation fournie par la source.

Parmi les aspects importants de la thorie de linformation, on peut citer :

le codage de linformation

la mesure quantitative de redondance dun texte

la compression de donnes

la cryptographie.

Source Codeur

Canal

DcodeurUtilisateur

Bruit

Fig. 1 - Systme de communication

Source : voix, musique, image (fixe ou anime), texte, . . . Canal : radio, fil, fibre optique, support magntique ou optique, . . . Bruit : perturbations lectromagntiques, rayures, . . .



En gnral, les sciences de linformation essaient de dgager le sens des informations en vue

de prendre des dcisions depuis des donnes en sappuyant sur des questions :

de corrlation

dentropie

dapprentissage (voir IA, Data mining).

Alors que les technologies de linformation, soccupent de la faon :

de concevoir,

dimplmenter

de dployer des solutions pour rpondre des besoins identifis.

Remarque

On constate que dans la chane qui mne de la donne laction (prise de dcision, infrence,

dduction,.) :

Donnes Information Connaissance Sens Motivation

seules les deux premires transformations

Donnes Information

sont prises en compte par la thorie de linformation classique



3. Exemples dinformation

La pression, la temprature, le dbit dans une canalisation sont des informations qui renseignent sur l`tat du fluide dans le circuit.

Soit une bibliothque qui possde un grand nombre :

douvrages, de revues, de livres de dictionnaires.

Dans ce fond documentaire, on veut rechercher un cours complet sur la thorie de

linformation.

Tout dabord, remarquons quil est logique que nous ne trouverons pas cet ouvrage dans des

ouvrages darts ou de littrature. Nous venons donc dobtenir une information qui diminuera

le temps de recherche.

Il est prcis de plus que nous voulons aussi un cours complet ; nous ne le trouverons donc ni

dans une revue, ni dans un dictionnaire. Nous avons obtenu une information

supplmentaire (on cherche un livre), qui rduira encore le temps de notre recherche.

Remarquons quune information est porte par un signal qui est une grandeur

physique dont les variations correspondent linformation que cette grandeur vhicule.

4. Notion de quantit dinformation

4.1. Problme

Considrons N botes numrotes de 1 N.

Un individu A a cach au hasard un objet dans une de ces botes.

Un individu B doit trouver le numro de la bote o est cach lobjet.

Pour cela, B a le droit de poser des questions lindividu A et A doit rpondre sans mentir

par OUI ou NON.

Mais chaque question pose reprsente un cot payer par lindividu B.

Un individu C sait dans quelle bote est cach lobjet. Il a la possibilit de vendre cette

information lindividu B.



B nacceptera ce march que si le prix de C est infrieur ou gal au cot moyen que B devrait

dpenser pour trouver la bote en posant des questions A.

Linformation dtenue par C a donc un certain prix.

Ce prix reprsente la quantit dinformation reprsente par la connaissance de la bonne

bote : cest le nombre moyen de questions poser pour identifier cette bote.

Nous noterons I cette quantit dinformation.

Si N = 1, I = 0. Il ny a quune seule bote. Aucune question nest ncessaire.

Si N = 2, I = 1. On demande si la bonne bote est la bote n1. La rponse OUI ou

NON dtermine alors sans ambigut quelle est la bote cherche.

Si N = 4, I = 2. On demande si la bote porte le n1 ou 2. La rponse permet alors

dliminer deux des botes et il suffit dune dernire question pour trouver quelle est la

bonne bote parmi les deux restantes.

Si N = 2k, I = k. On crit les numros des botes en base 2. Les numros ont au plus k

chiffres binaires, et pour chacun des rangs de ces chiffres, on demande si la bote

cherche possde le chiffre 0 ou le chiffre 1.

En k questions, on a dtermin tous les chiffres binaires de la bonne bote. Cela revient

galement poser k questions, chaque question ayant pour but de diviser

successivement le nombre de botes considres par 2 (mthode de dichotomie).

On est donc amen poser I = log2(N), mais cette configuration ne se produit que dans le cas

de N vnements quiprobables.

4.2. Hypothses supplmentaires

On suppose maintenant que les botes sont colores, et quil y a par exemple n botes rouges.

On suppose galement que C sait que la bote o est cach lobjet est rouge ; quel est le prix

de cette information ?

Sans cette information, le prix payer est log(N). Muni de cette information, le prix

payer nest plus que log(n). Le prix de linformation la bote cherche est rouge est

donc :

log(N) log(n) = log(N / n).



On dfinit ainsi la quantit dinformation comme une fonction croissante de N/n avec :

N : le nombre dvnements possibles

n : le cardinal du sous-ensemble dlimit par linformation

Afin de mesurer cette quantit dinformation, on pose :

I = log2 (N/n)

I est exprim en bit (ou logon, unit introduite par Shannon) (ou bien en nat si on utilise le

logarithme naturel la place du logarithme de base 2).

4.3. Entropie, formule de Shannon

Supposons maintenant que les botes soient de diverses couleurs :

n1 botes de couleur C1,

n2 botes de couleur C2,

...,

nk botes de couleurs Ck,

avec n1 + n2 + ... + nk = N.

La personne C sait de quelle couleur est la bote recherche.

Quel est le prix de cette information ?

Linformation la bote est de couleur C1 vaut log N/n1, et cette ventualit a une

probabilit n1/N.

Linformation la bote est de couleur C2 vaut log N/n2, et cette ventualit a une

probabilit n2/N...

Linformation la bote est de couleur Ck vaut log N/n2k, et cette ventualit a une

probabilit nk/N

Le prix moyen de linformation est donc :

n1/N log( N/n1 )+ n2/N log (N/n2 )+ ... + nk/N log (N/nk)

Plus gnralement, si on considre k vnements disjoints de probabilits respectives

p1, p2, ..., pk avec :

p1 + p2 + ... + pk = 1, alors la quantit dinformation correspondant cette distribution de

probabilit est :

p1 log 1/p1 + + pk log 1/pk



Cette quantit sappelle entropie de la distribution de probabilit

Lentropie permet donc de mesurer la quantit dinformation moyenne dun ensemble

dvnements (en particulier de messages) et de mesurer son incertitude. On la note H(I) :

() =

. 2()

avec = la probabilit associe lapparition de lvnement i.

Lentropie de Shannon, est une fonction mathmatique qui correspond la quantit

dinformation contenue ou dlivre par une source dinformation. Cette source peut tre par

exemple un texte crit dans une langue donne, un signal lectrique ou encore un fichier

quelconque (collection doctets).

Du point de vue dun rcepteur, plus la source met dinformations diffrentes, plus

lincertitude sur ce que la source met (entropie) est grande, et vice versa.

Plus le rcepteur reoit dinformations sur le message transmis, plus lentropie (lincertitude)

vis--vis de ce message dcrot, en rapport avec ce gain dinformation.

La dfinition de lentropie dune source selon Shannon est telle que plus la source est

redondante (contient dinformations rptitives), moins elle contient dinformation. En

labsence de contraintes particulires, lentropie est donc maximale pour une source dont tous

les symboles sont quiprobables.

Dans le cas particulier dun systme de tlcommunication, lentropie de la source

dinformation (le transmetteur) indique lincertitude du rcepteur par rapport ce que la

source va transmettre.

4.4. Exemple

Une source rpute envoyer toujours le mme symbole, par exemple la lettre a , a une

entropie nulle, cest--dire minimale.

En effet, un rcepteur qui connait seulement les statistiques de transmission de la source est

assur que le prochain symbole sera un a , sans jamais se tromper. Le rcepteur na pas

besoin de recevoir de signal pour lever lincertitude sur ce qui a t transmis par la source car

celle-ci nengendre pas dala.



Par contre, si la source est rpute envoyer un a la moiti du temps et un b lautre

moiti, le rcepteur est incertain de la prochaine lettre recevoir. Lentropie de la source dans

ce cas est donc non nulle (positive) et reprsente quantitativement lincertitude qui rgne sur

linformation manant de la source.

Du point de vue du rcepteur, lentropie indique la quantit dinformation quil lui faut

obtenir pour lever compltement lincertitude (le doute) sur ce que la source a transmis.

5. Schma gnral de la communication

Sourceinformation Transmetteur Canal Rcepteur Destination

Bruit

X= HELLO

P(x) X=F(x) y Y=G(y)

x=0011010100 Y= CELLOy=0011000100

P(y x)

Le premier rle du transmetteur/rcepteur est de traduire la source en un langage admis

par le canal.

5.1. Le canal

Pour modliser un canal de transmission, il est ncessaire de spcifier lensemble des entres

et lensemble des sorties possibles. Le cas le plus simple est celui du canal discret sans

mmoire. Lentre est une lettre prise dans un alphabet fini A = {a1,...,an} et la sortie est une

lettre prise dans un alphabet fini B = {b1,...,bm}

Canal discret sans mmoire

On dit que le canal est sans mmoire si chaque lettre de la squence reue ne dpend

statistiquement que de la lettre mise de mme position. Ainsi un canal discret sans

mmoire est entirement dcrit par la donne des probabilits conditionnelles p(b|a)

pour toutes les lettres a de lalphabet dentre et toutes les lettres b de lalphabet de

sortie.



Canal continu

Il existe une classe de modles de canaux appels canaux continus, plus proches des

canaux physiques. Lentre et la sortie sont des fonctions continues du temps.

Source Codeurde source

Canalcontinu

Dcodeurde sourceRcepteur

Codeur de canal discret

Dcodeur de canal discret

Modulateur

Dmodulateur

Canal discret

Le codeur du canal discret, transforme une squence binaire en une squence de lettres dun

alphabet fini A = {a1, . . . , an}. La seconde partie du codeur, le modulateur de donnes

digitales, envoie pendant un temps c sur le canal une des fonctions de temps prdfinies s1(t),

. . . , sn(t). La dure c est lintervalle de temps sparant lmission de deux lettres par le

codeur de canal discret.

Lensemble de ces fonctions du temps mises bout bout est converti la sortie du canal par le

dmodulateur de donnes digitales en une squence de lettres dun alphabet de sortie

B = {b1, . . . , bm} au rythme, dune lettre toutes les c secondes.

5.2. Hypothse sur la source

On considre le message produit par la source comme un signal alatoire dont on peut

connatre les probabilits doccurrence des symboles p(X).

Exemple 1 : source binaire quiprobable, 010010111001 ,

p(0) = 1- p(1) = 0.5

Exemple 2 : source binaire biaise, 11011110011111 ,

p(0) = 1- p(1) = 0.2

Exemple 3 : source alphabtique quiprobable, AGRWTCHG ,

p(A) = p(B) = p(C) = p(Z) = 1/26.



Le deuxime rle du transmetteur/rcepteur est de rduire la redondance de la source.

On considre le canal de transmission en termes probabilistes via les probabilits de

transition p(y|x) dobtenir un symbole y en sortie quand le symbole x a t introduit en

entre

Exemple 1 : canal binaire sans bruit,

p(0|0) = p(1|1) = 1

p(1|0) = p(0|1) = 0

Exemple 2 : canal binaire bruit,

p(0|0) = p(1|1) = 1- a ,

p(1|0) = p(0|1) = a

Exemple 3 : machine crire bruite,

p(A|A) = p(B|A) = 0.5 ,

p(B|B) = p(C|B) = 0.5 ,

p(C|C) = p(D|C) = 0.5 ,

Le 3me rle du transmetteur/rcepteur est de grer les erreurs du canal, les dtecter

et/ou les corriger.

5.3. Sources dinformation

Dfinition : Systmes capables de slectionner et dmettre des squences de signes (ou

messages) appartenant un ensemble (ou alphabet) donn.

Sources dinformation discrtes

Une source discrte est un alphabet fini = (a1,, aK) muni dune loi de probabilit PX.

Exemples : Sources dinformation alphanumriques, de symboles binaires, dinformation

numrique (signaux quantifis en amplitude, en frquence ou en phase)

Dbit dinformation

Le dbit dinformation (ou vitesse dinformation) est le produit de lentropie de la source par

le nombre moyen de symboles par seconde.

Si la dure moyenne dun symbole est , alors le dbit dinformation de la source sera

() = () [bit/seconde]



Redondance

Si tous les symboles de la source sont quiprobables, lentropie est maximale ; on dfinit la

redondance comme

= () () et la redondance relative

= 1 ()() o () = log () , n tant le nombre de symboles (de lettres) de lalphabet de la source.

Exemples

Exemple 1 : source binaire equiprobable

X = { 0,1 }, p(0) = p(1) =0.5

H(X) = 1 bit par symbole

Exemple 2 : source binaire biaise

X = { 0,1 } ; p(0) = 1-p(1) = 0,2 = P

H(X) = 0,72 bit par symbole

Exemple 3 :

On considre une suite de symboles. Chaque symbole peut prendre deux valeurs s1 et s2 avec

des probabilits respectivement p1 = 0,8 et p2 = 0,2.

La quantit dinformation contenue dans un symbole est :

p1 log 1/p1 + p2 log 1/p2 0,7219.

Si chaque symbole est indpendant du suivant, alors un message de N symboles contient

en moyenne une quantit dinformation gale 0,72N. Si le symbole s1 est cod 0 et le

symbole s2 est cod 1, alors le message a une longueur de N, ce qui est une perte par

rapport la quantit dinformation quil porte.

5.4. Codage de linformation

Les thormes de Shannon noncent quil est impossible de trouver un code dont la

longueur moyenne soit infrieure 0,72N, mais quil est possible de coder le message de

faon ce que le message cod ait en moyenne une longueur aussi proche que lon veut de

0,72N lorsque N augmente.



Exemple de codage de source :

Soit la source X = (a1,a2, a3 ;,a4) ;

On dispose pour la transmission de deux lois :

Loi 1 : (1/4,1/4,1/4,1/4)

Loi 2 : (1/2,1/4,1/8,1/8)

Et de deux codes :

Code A : a1 00 Code B : a1 0 a2 01 a2 10 a3 10 a3 110 a4 11 a4 111

Longueur moyenne :

pour le Code A, on trouve 2 dans les deux cas

pour le Code B

avec la Loi 1 : (1+2+3+3) x =9/4=2.25

avec la Loi 2 : 1 x1/2+2x1/4+(3+3)*1/8=7/4=1.75

Le meilleur code dpend de la loi dmission de la source.

6. Thorie de linformation et automatisation Les systmes automatiss vhiculent des signaux reprsentant des informations utiles sur le processus, et procdent au traitement de ces signaux pour en dduire les actions entreprendre. Lintermdiaire entre ces systmes est le signal, support de linformation. La notion d'information dpasse le cadre des systmes automatiss car des dispositifs tels que le tlgraphe, le tlphone, la radio, la tlvision, le radar, etc. sont des systmes d`mission et de traitement de linformation. Quelques exemples dinformations utilises dans les systmes automatiss : La pression dans une tuyauterie est une information sur ltat du fluide dans la tuyauterie ; il en est de mme du dbit, de la temprature, etc. Le basculement dun pressostat est un signal portant une information sur l'atteinte d'une limite haute ou basse de la pression.



Du point de vue technologique, linformation est porte par un signal. Le signal est une grandeur physique (le plus souvent lectrique ou pneumatique) dont les variations correspondent linformation qu'elle porte. La relation entre linformation et le signal sappelle le code. Exemple : Transmetteur de pression Supposons que la pression dùn fluide dans une conduite puisse varier de 0 150 bars. On utilise un transmetteur de pression standard 0,2 1 bar. La correspondance entre la grandeur mesure et le signal dlivr par le capteur est :

Grandeur Signal physique 0 0.2 150 1

la relation entre la grandeur mesure et le signal dlivr est de plus linaire. Si nous appelons P la pression (grandeur mesure ou information) et p le signal, on a la relation

P/150 = (p - 02)/0,8 P = l87,5 p 37,5 ; cette formule dfinit ainsi le code utilis.

Quantit d'information Il est important de savoir dfinir la quantit dinformation porte par un signal. Cela permet entre autre de comparer les performances des systmes de transmission. Plus un message est improbable, plus il apporte dinformations. Par exemple, si dans un bac lalarme de niveau haut a une chance sur cent mille de se produire (niveau haut improbable), le signal de niveau normal nàpporte que peu dìnformation ; par contre le signal de niveau haut apporte beaucoup dinformation. Information mise La figure ci-dessous reprsente une transmission d'information. La source met des informations sous forme de message. La liste des diffrents messages possibles sappelle lalphabet de la source.

Source Transmetteur Canal Rcepteur Destination

Bruit

Message mis : x Signal transmisSignal cod Message reu : y

1 2 3 4



A chaque message x, correspond une probabilit d'tre mis p(x). Exemple : une temprature peut varier de 0 400, mais elle nest connue qu'avec une

prcision de 0,5% c'est--dire 0,5400100

= 2.

Les diffrents messages possibles sont alors : 0 ; 2 ; 4 ; 6 ; ; 398 ; 400. Cette srie de messages possibles est lalphabet de la source. Si toutes les valeurs sont quiprobables, on aura :

p(0) = p(2) = ............... = p(398) = p(400) = p mais comme () = 1

cest--dire p(0) + p(2) + .............. + p(400) = l ou p + p + .... = 1 ou encore 201. p = 1 et donc p = 1/201. Le transmetteur a pour rle de coder les messages de la source pour obtenir un message utilisable et transmissible. Dans certains cas, le mot modulation est employ au lieu de codage ; la modulation est en gnral une opration de codage sur un signal en vue de faciliter sa transmission. Le canal sert de vhicule pour le transport du signal. Le canal utilis en automatisation est gnralement un cble pneumatique pour signal 0,2 - l bar ou la paire pour signal 4 - 20 mA. Le rcepteur est un organe de dcodage qui restitue un message y pour le destinataire. Les diffrents y possibles forment lalphabet du destinataire (qui nest pas ncessairement le mme que celui de la source). La quantit dinformation mise par la source est dfinie, pour des messages indpendants, par I(x) = log 1p(x) = log p(x) Si on prend le log de base 2, lunit d`information est appele bit . Elle correspond en effet linformation mise par une source binaire quand les deux signaux de la source sont quiprobables. On dsigne ces deux signaux classiquement par 0 et l et nous supposons donc

(0) = (1) = 12 et par suite I = log2 11

2

= log2 2 = 1 bit



Remarques :

- linformation est dàutant plus grande que p(x) est petit do le terme 1p(x)

- linformation de deux messages est la somme des informations de chaque message ; en effet soit I1 = log p(x1) et I2 = log p(x2) alors I1 + I2 = log p(x1). p(x2)

Mais comme nous supposons x1 et x2 indpendants, on aura p(x1) . p(x2) = p(x1, x2)

Si les messages ntaient pas indpendants, le rsultat serait le mme condition de dfinir linformation mise par une probabilit conditionnelle. Exemple : x1 ayant t mis suivi de x2 linformation donne par x2 serait: I2 = log p(x2|x1) et lòn retrouverait la loi I1 + I2 = Itotal en vertu de la relation p(x1, x2) = p(x1). p(x2|x1) Information reue La source ayant mis le message x, le destinataire va recevoir le message y. Si la transmission nest pas perturbe par des parasites appels bruits dune faon gnrale, alors la rception de y permet de connatre avec certitude le x mis par la source et linformation reue est gale l'information mise, soit log p(x) . Cependant, en pratique, le signal transmis est souvent accompagn dun bruit de sorte quen recevant y on n'est pas sr que x ait t mis. On ne peut que connatre la probabilit conditionnelle de x connaissant y, soit p(x2|x1) et linformation est dautant plus faible que cette probabilit est faible. Linformation reue sera donc dnie par : I(x, y) = log p(x|y)p(x) Elle sera mesure en bits si l'on prend les log de base 2. I(x,y) est en fait symtrique en x et y, en effet : I(x, y) = log p(x, y)p(x)p(y) daprs la relation p(x , y) = p(y). p(x|y), I(x,y) s'appelle information mutuelle de x et y.

La perte dìnformation est donne par : I(x) I(x, y) = log 1p(x) log p(x|y)p(x) = log p(x|y) Mais comme p(x|y) est infrieur l en prsence de bruit, alors log p(x|y) est positif, autrement dit linformation reue en prsence de bruit est infrieure linformation mise, ce qui correspond bien la ralit.



Dautre part, linformation maximum pouvant tre reue est I(x). Exemple : Soit un transmetteur de dbit permettant de mesurer un dbit de gaz compris entre 0 et 200 m3/h. Supposons le transmetteur linaire et ayant une prcision de 2%. Cela veut dire quentre 0 et 100% on peut distinguer 50 valeurs du dbit. Supposons toutes les valeurs du dbit galement probables (cette hypothse est prise ici pour simplifier, mais comme on le sait elle est rarement vrifie). Dans ce cas, la probabilit p(x) d'une valeur dùn dbit x est p = 1/50 = 0,02. Supposons de plus que la transmission soit able 99%, c'est--dire p2 = p(y|x) = 0,99. La quantit dinformation reue chaque mesure sera : I = log2 p2p = log2 0,990,02 = 5,63 bits Remarque : On peut considrer Lensemble source / transmetteur, canal, rcepteur, comme une bote noire mettant des messages y. Cette boite noire devient elle-mme une source qui met la quantit dinformation I(y) = log p(y) chaque message. Entropie Nous avons jusqu' prsent parl de linformation mise ou reue chaque message. Cette information est diffrente chaque message si les diffrents messages ne sont pas quiprobables. Ce qui est important en fait, pour comparer les performances des systmes de transmission, c'est la valeur moyenne de linformation mise ou reue. Les valeurs moyennes des quantits dìnformation sont appeles entropies et sont dsignes par la lettre H. Entropie de la source H(X) = p(x). log p(x)x o X dsigne l'ensemble des x, c'est--dire lalphabet de la source, reprsente la quantit moyenne dìnformation mise par message. Elle est mesure en bits/message (si on prend les log de base 2). Exemple de la source binaire : L'alphabet de la source est constitu par les messages 1 et 0. Soit p la probabilit du 1 et (1-p) la probabilit du zro (puisque la somme des deux probabilits est gale 1).

L'entropie de la source est donc H = [p. log p + (1 p). log(1 p)] = log pp . (1 p)1p C'est une fonction de p reprsente sur la gure ci-aprs.



On voit que 1'entropie est nulle pour p = 0 ou p = 1. En effet, dans ces deux cas, on est sr d'avance que la source n'met respectivement que des 0 (puisque la probabilit du l est nulle) ou des l (puisque la probabilit du 1 est gale 1). Dans ces deux cas, la source nmet videmment aucune information. L'entropie est maximum et gale l bit/message pour p = 1 - p = 0,5 . Ce dernier rsultat est gnral. L'entropie dune source est maximum quand tous les messages de son alphabet sont quiprobables. Entropie reue C'est la valeur moyenne de linformation reue. Cette moyenne est prendre sur les alphabets X et Y : H(X, Y) = p(x, y). I(x, y) = p(x, y). log p(x|y)p(x)

x,yx,y Comme I(x,y) , cette entropie est symtrique en x et y et sappelle aussi entropie mutuelle.

0

1

0 0,5 1

Entr

opie

H e

n bi

ts

probabilit p

Entropie d'une source digitale



On peut transformer cette expression comme suit : H(X, Y) = p(x, y). log p(x|y) p(x, y). log p(x)x,yx,y H(X, Y) = p(y). p(x|y). log p(x|y) p(x). log p(x)

xx,y (en utilisant les relations entre probabilits) et finalement H(X, Y) = H(X) H(X|Y)

en posant H(X|Y) = p(y). p(x|y). log p(x|y)x,y Cette dernire entropie est appele quivocation de la transmission. Elle reprsente la diffrence entre les informations moyennes mises et reues. Elle est toujours positive. On peut remarquer que lquivocation scrit H(X|Y) = p(y)

y

p(x|y). log p(x|y)x

Or, nous avons vu que la perte dinformation pour un message x est log p(x, y) ; donc la quantit H(X|y) = p(x|y). log p(x|y)x reprsente la perte moyenne dune information pour y donne, et H(X|Y) la perte moyenne dinformation pour lensemble des x et des y. Cette perte dinformation est due au bruit. On voit facilement qu`on peut aussi crire H(X; Y) = H(X) + H(Y) H(X, Y) H(X, Y) tant lentropie jointe de x et y, dfinie par H(X, Y) = p(x, y). log p(x, y)x,y et par symtrie on peut aussi crire H(X; Y) = H(Y; X) = H(Y) H(Y|X) H(Y)et H(Y|X) tant dfinies comme pour X. Fiabilit de la transmission La perte dinformation pour un message x tant I(x) I(x, y) = log p(x|y) , la probabilit conditionnelle p(x|y) (probabilit de x si y) reprsente la fiabilit de la transmission. Si par exemple un message est transmis avec une perte dinformation de 0,2 bit, la transmission est fiable 87% .



7. Rappels de probabilits Rappelons ci-dessous quelques notions lmentaires sur la thorie des probabilits. Etant donn deux variables alatoires x et y (alatoire voulant dire dont on ne peut prvoir davance la valeur), on considre les probabilits suivantes : - Probabilit doccurrence de la valeur x : p(x) (appele probabilit a priori) - Probabilit doccurrence de la valeur y : p(y) (probabilit priori) - Probabilit doccurrence de x et y : p(x,y) (appele probabilit jointe) - Probabilit doccurrence de x connaissant y : p(x/y) (lire p de x si y) (appele probabilit conditionnelle - Probabilit doccurrence de y connaissant x : p(y/x) (probabilit conditionnelle) Remarques

Rappelons que les variables alatoires ne sont pas forcment des nombres alors que les probabilits sont des nombres compris entre 0 et 1.

Entre ces probabilits existent les relations suivantes (dont on trouvera la dmonstration dans tout ouvrage traitant des probabilits).

p(x)x = p(y) = p(x, y)x,y = p(x|y)x = p(y|x) = 1yy (1)

Le symbole p(x)x par exemple dsigne la somme des probabilits des diverses valeurs de x pour tous les x possibles. (Dans le cas o les variables varient de faon continue, il suffit de remplacer les sommes par des intgrales). p(x) = p(x, y)y et p(y) = p(y, x)x (2)

p(x, y) = p(x). p(y|x) = p(y). p(x|y) (3) Les relations (l) expriment que la somme des probabilits de toutes valeurs possibles d'une variable est gale l, ce qui veut dire en clair quune variable prend obligatoirement une de ses valeurs possibles. Les relations (2) expriment que la probabilit a priori dune variable est la somme des probabilits jointes pour toutes les valeurs de làutre variable. Les relations (3) expriment que la probabilit jointe que x et y se produisent est gale la probabilit priori dune des variables multiplie par la probabilit conditionnelle de làutre. Si les variables x et y sont indpendantes, on a de plus les relations suivantes : p((x|y) = p(x) et p((y|x) = p(y) (4)

Dò p(x, y) = p(x). p(y)

La probabilit jointe se rduit alors au produit des probabilits priori.



Quelques Rfrences Bibliographiques

A Mathematical Theory of Communication , C.E. SHANNON The Bell System Technical Journal, Vol.27, 1948. Thorie de linformation et du codage , Louis WEHENKEL Facult des Sciences Appliques , Universit de Lige, 2003. Thorie de linformation et codage , Marie-PierreBal et NicolasSendrier INRIA, 2008. Thorie de l'information , Florent Dupont UCB Lyon1. Instrumentation Industrielle , Michel CERR Lavoisier, 1990. Fondements de la thorie de la transmission de linformation , Alexandru SPTARU Presses Polytechniques Romandes, 1987. Thorie de linformation , F.KHOUKHI Acadmie Internationale de laviation Civile.

Documents

Elements theorie information.pdf