1-Entropie-Capacite

7/21/2019 1-Entropie-Capacite

1/11

Dpt. Gnie Electrique Thorie de l information T. Grenier 1

Thorie de linformation

Thomas Grenier


1. Introduction .. D3-7

2. Sources discrtes & Entropie . D8-16

3. Canaux discrets & Capacit .. D17-21

4. Codage de source . D23-39

5. Codage de canal . D41-73

6. Cryptographie . D75-D112

7. Conclusion .. D113

Plan


2/11


1. Introduction

Vue densemble dun systme de communication

indpendante des moyens techniques & physiques

1948 : ShannonThorie de l'information

Rflexion sur les techniques de communication (XIX)

- Mcanique, accoustique- Ondes radio-lectrique- Tlgraphe (code morse)- Tlphone, .

Systme de communication = fonctions physiques ralisablesMauvaise comprhension des perturbations, des dbits


GSM codage de source & canal

TV Num codage de source & canal

Rseaux codage de canal (erreurs)

@business cryptage

Ca ne se rt rien !

1960 / conqute spatiale codage de source

Aujourd'hui


3/11


Paradigme de Shannon = modle sys. com.

Source = je parle

Canal = l'air ambiantPerturbations = bruit sonore

Destinataire = tu coutes


Modle dtaill

Th. Signaux dcrit messages et perturbations

Modulation modifie les signaux pour les propager

Electronique ralise les fonctions

Th. Information propose une mesure quantitative de

l'information et tudie sa reprsentation,sa transmission, sa dgradation


4/11


Source: sige d'vnements alatoires qui constituentle message mis Entropie

Canal: transmet et dgrade le message Capacit

Des messages diffrents portent la mme information, le codagecherche le message avec les meilleures proprits.

Codage de source supprime la redondance, rduit le cot

Codage de canal protge contre les perturbations

Cryptage protge contre les curieux

Deux thormes fondamentaux :

Codage de source Codage de canal


2. Sources discrtes & EntropieSources dbitant des messages sous forme discrte !

Source discrte d'information: suite de variables alatoiresdiscrtes X1, X2, Xn

Mot: succession finie de symboles

Alphabet: totalit des D lettres

[X] = [x1,x2, ., xD]

Symbole ou lettre : lment fondamental irrductiblecontenant une information, cad ralisation particulire de la

source d'information.


5/11


Source discrte sans mmoire : source pour laquelle laprobabilit d'apparition d'un symbole ne dpend pas dessymboles prcdents )(,...),/(

21 nnnn iiii xpxxxp =

Source discrte mmoire: source pour laquelle la probabilitd'apparition d'un symbole dpend du ou des symboles prcdents

Source sationnaire : source pour laquelle les probabilitsd'apparition des diffrents symboles ne dpendent pas del'origine des temps kxpxp

knn ii =

+)()(

Source dbit contrlable : source pouvant gnrer desmessages comme suite une commande externe (Tlgraphe, .)


Source dbit non contrlable : source gnrant desmessages avec un dbit fix, proprit de la source (CD audio)

Source discrte contraintes fixes : source pour laquellecertains symboles ne peuvent tre utiliss qu'en des conditionsdtermines (Morse, )

Source discrte contraintes probabilistes : source mmoire. Dans un tat, la source peut gnrer n'importelequel des symboles avec une probabilit qui dpend dessymboles prcdents (texte )

Source de Markov : source pour laquelle la probabilit degnrer un symbole ne dpend que du symbole l'instant n-1

)/(,...),/(121

=nnnnn iiiii

xxpxxxp


6/11


Quantit d'information & Entropie Quantit d'information propre

Proprit de l'information = imprvisibi l i t

Quantit d'information propre : ))(1()( xpfxh =Avec f croissante & f(1)=0

2 evt. indpendants apportent la somme de leur quantit d'info

)()())(

1()

)(

1()

)().(1()

),(1(),( yhxh

ypf

xpf

ypxpf

yxpfyxh +=+===

f fonction logarithme (Base 2 >> bit)

))(log())(

1log()( xpxp

xh ==


Rgle de Bayes : ),()().()().(),( xypxpxypypyxpyxp ===

)),(

1log(),(yxp

yxh =

))(

1log()(yxp

yxh =

),()()()()(),( xyhxhxyhyhyxhyxh =+=+=

)()( xhyxh = si x et y indpendants

Ex cartes


7/11


Entropie

Hyp : source discrte finie stationnaire sans mmoire

n...,1,2,ipour)( === ii xXpp

Emission = variable alatoire X

11

==

n

i

ip

== ===n

i

ii

n

i

ii ppppXhEXH11

)log(.)1log(.))(()(

Quantit d'information moyenneassocie chaque symbole de la source = entropie


Ex : Source binaire

pp

pp

=

=

1)0(

)1(

=


8/11


Redondance)()(max XHXHR =

)(

)(1

max XH

XH=

Proprits de l entropie

Continuit: l'entropie est une fonction continue de chaquevariable pi.

Additivit: de part la dfinition de l'information propre.

Positive:

Borne:

0),...,,()( 21 = npppHXH

)log()1

,...,1

,1

()( nnnn

HXH =


Entropie & Dbit d information

Le dbit d'information d'une source est donn par le produitde l'entropie de la source (valeur moyenne de l'info /symbole)par le nombre moyen de symboles par seconde soit :

kime

extension : source Skdont l'alphabet Q

kaireest obtenu

en groupant par bloc de k celui de la source S

Source Qaire

Source Qaire: source S dont l'alphabet possde Q lments

symboleund'moyennedureavec).(

)( 1

= sbits

XH

DX


9/11


3. Canaux discrets & CapacitCanal: milieu de transmission de l'information situ entre la sourceet la destination. Le canal opre une transformation entre l'espacedes symboles l'entre et celui de la sortie.

Canal discret: les espaces d'entre et de sortie sont discrets

Canal continu : les espaces d'entre et de sortie sontcontinus

Canal sans mmoire : si la transformation d'un symbole x l'entre en un symbole y en sortie ne dpend pas destransformations antrieures

Canal stationnaire : si les transformations ne dpendent pas del'origine des temps


[ ]

=

mnnn

m

m

yxyxyx

yxyxyx

yxyxyx

YX

...

......

...

.

21

22212

12111

[ ]

=),(...),(),(

......

),(),(),(

),(...),(),(

),(

21

22212

12111

mnnn

m

m

yxpyxpyxp

yxpyxpyxp

yxpyxpyxp

YXP

=

=m

j

jii yxpxp1

),()(

=

=n

i

jij yxpyp1

),()(

Probabilits marginales

))(log(.)()(1

i

n

i

i xpxpXH =

=

))(log(.)()(1

j

m

j

j ypypYH =

=


10/11


)()(),(0)/()/(YHXHYXH

XYHYXH==

==)()(),(

)()/(et)()/(YHXHYXH

YHXYHXHYXH+=

==

Canaux non perturbs

)),(log(.),(),(1 1

ji

n

i

m

j

ji yxpyxpYXH = =

=

Entropie runie ou conjointe

))/(log(.),()/(1 1

ji

n

i

m

j

ji yxpyxpYXH = =

=

Entropie conditionnelle ou quivoque

Canaux trs perturbs


Transinformation & capacit

Information mutuelle

))()(log();( xpyxpyxi = );();( xyiyxi =

Transinformation

))().(

),(log(.),();(

1 1 ji

jin

i

m

j

jiypxp

yxpyxpYXI

= =

=

)/()()/()();(

),()()();(

XYHYHYXHXHYXI

YXHYHXHYXI

==

+=


11/11


Capacit dun canal

Redondance dun canal

Efficacit dun canal

));(( YXIMaxC=

);( YXICRc =

CYXI

c);(=

Ex canal binaire

C

YXIc

);(1=

Documents

1-Entropie-Capacite