Bousmah Chapit2 THInfo STIC F(2)

Thorie de linformation

Universit Chouaib DoukkaliDpartement de Physique

Option STIC smp-5

Prof. M [email protected]

Prof. M BOUSMAH 2

1. Thorie de lInformation 1. Th1. Thorie de lorie de lInformation Information 2. Modlisation dune source2. Mod2. Modlisation dlisation dune sourceune source

Plan du cours

5. Codage de la source5. Codage de la source5. Codage de la source

3. Mesure de linformation3. Mesure de l3. Mesure de linformationinformation

4. Modlisation dun canal4. Mod4. Modlisation dlisation dun canalun canal

Prof. M BOUSMAH 3

La thorie de linformation est une thorie qui sintresse la transmission des messages dune source vers un destinataire travers un canal. Elle a t introduite en 1948 par lingnieur amricain Claude Shannon qui affirmait quen codant linformation correctement, celle-ci peut tre transmise travers un canal parasit sans perte de son contenu la rception. Elle se base sur une mesure quantitative de linformation, cest dire quelle ne sintresse pas au sens du message du point de vue smantique, mais seulement la quantit dinformation que le message vhicule.

1. Th1. Thorie dorie dinformationinformation ccest est quoi?quoi?

Claude SHANNON(avr 1916-mar 2001)

Prof. M BOUSMAH 4

1948 : Shannon Thorie de l'information

Source Discrte Brute

Encodeur de la source

Can

al

Encodeur du canal

Modulateur Numrique

E

Mise en formeRception

Dcodeur de la source

Dcodeur du canal

Dmodulateur Numrique

R

Codage de la source Codage du canal


Prof. M BOUSMAH 5


Prof. M BOUSMAH 6

2. 2. MODELISATION DMODELISATION DUNE UNE SOURCESOURCE

Il est possible de classer les sources en deux catgories selon les signaux ou messages quelles mettent :

Les sources analogiques

Les sources discrtes

Exemple: mic

Exemple: CD

Prof. M BOUSMAH 7

Diffrentes types de sources dinformation discrtes existent:

Une source discrte dispose d'un "alphabet" constitu d'lments ou symboles ou caractres {x1 , x2 , x3,, xn}, n est la longueur de l'alphabet. Ces symboles sont associs pour constituer un message. Emettre un message revient mettre une succession de symboles appartenant une source. Chaque symbole xi de l'alphabet a une probabilit d'utilisation pi.

2. 2. MODELISATION DMODELISATION DUNE UNE SOURCE: Cas de sources discrSOURCE: Cas de sources discrtestes

Prof. M BOUSMAH 8

2. 2. MODELISATION DMODELISATION DUNE UNE SOURCE: Cas de sources discrSOURCE: Cas de sources discrtete

Prof. M BOUSMAH 9

3. 3. MESURE DE L'INFORMATION : MESURE DE L'INFORMATION : QuantitQuantit d'informationd'information

A partir des remarques suivantes: La quantit d'information d'un symbole est d'autant plus grande que

celui-ci est peu probable.

La quantit d'information de deux symboles successifs est la somme de leurs quantits d'information.

La quantit d'information note I est une fonction qui doit ainsi avoir les proprits suivantes:

Prof. M BOUSMAH 10


Une fonction mathmatique remplit les conditions 1, 3 et 4 : log(pk)

Pour obtenir la proprit 2, il suffit de prendre log(1/pk)= log(pk)

La quantit d'information d'un symbole xk de probabilit pk a ainsi tdfinie par Shannon comme :

Prof. M BOUSMAH 11


Pour la suite du cours, log log loglog22

Prof. M BOUSMAH 12


Prof. M BOUSMAH 13


Prof. M BOUSMAH 14

3. 3. MESURE DE L'INFORMATION : MESURE DE L'INFORMATION : Entropie d'une sourceEntropie d'une source

Source S Alphabet: X={X1,X2, ,XK}Entropie :H(X) ou H(S)

Lentropie H(X) mesure quoi?

Prof. M BOUSMAH 15


Prof. M BOUSMAH 16


Prof. M BOUSMAH 17


Cet exemple est un cas particulier d'une source ayant un alphabet de K symboles. On dmontre que son entropie est maximaleentropie est maximale lorsque tous les symboles sont quiprobablesquiprobables : donc pk = 1/Kpk = 1/K et l'entropie devient:

Ce qui montre le thorme suivant sur l'entropie d'une source:

Prof. M BOUSMAH 18

3. 3. MESURE DE L'INFORMATION : MESURE DE L'INFORMATION : Entropie conjointe entre deux sourcesEntropie conjointe entre deux sources

l'entropie conjointe ou runie des deux sources est alors la quantit d'information moyenne jointe entre deux caractres de la source :

Prof. M BOUSMAH 19


Cas ou les deux sources sont indpendantes:

Les deux sources sont indpendantes :

DDmonstrationmonstration

Prof. M BOUSMAH 20

I( X , Y ) est dfinie comme tant La quantitLa quantit d'information mutuelle d'information mutuelle entre les deux sourcesentre les deux sources ou Transinformation:

Cas ou les deux sources sont dpendantes:


Prof. M BOUSMAH 21


Sachant que:

Alors ce terme est ngatif. En dfinissant la quantit d'information mutuelle I( X , Y ) entre les deux sources comme une quantit positive.

DDmonstrationmonstration

Prof. M BOUSMAH 22

3. 3. MESURE DE L'INFORMATION : MESURE DE L'INFORMATION : Entropie conditionnelleEntropie conditionnelle

Nous pouvons aussi dfinir partir des densits de probabilit conditionnelles une quantit d'information conditionnelle:

puis une entropie conditionnelle :

et enfin une entropie conditionnelle moyenne :

Prof. M BOUSMAH 23


L'entropie conditionnelle permet d'obtenir d'autres formulations de ces quantits en utilisant la loi de Bayes :

Prof. M BOUSMAH 24


Un rsultat semblable peut tre tabli en permutant le rle de x et y d'o les deux expressions quivalentes de la quantit d'information mutuelle:

Ces expressions ajoutent deux nouvelles formulations de l'entropie jointe des deux sources :

Prof. M BOUSMAH 25

3. 3. MESURE DE L'INFORMATION : MESURE DE L'INFORMATION : Etude de casEtude de cas

Lors de la transmission par un canal, nous souhaitons rcuprer l'information sans distorsion, autrement dit, l'alphabet de sortie du canal doit tre le mme que celui de l'entre. Simplifions encore l'exemple un canal qui doit transmettre des messages. Si nous appelons p la probabilit d'erreur nous pouvons schmatiser le fonctionnement du canal par le graphe suivant :

Prof. M BOUSMAH 26


Prof. M BOUSMAH 27


Prof. M BOUSMAH 28


Prof. M BOUSMAH 29


Prof. M BOUSMAH 30


Prof. M BOUSMAH 31


Conclusion

Prof. M BOUSMAH 32

4. 4. ModModlisation dlisation dun canalun canal

Un canal de transmission reoit un message d'entre et restitue un message de sortie. D'un point de vue abstrait nous le considrerons comme une entitqui fait le lien entre deux alphabets : X X YY.Canal discret :Canal discret : Le deux alphabets d'entre et de sortie sont des alphabets

discrets qui comportent un nombre fini de symboles.Canal sans mCanal sans mmoire :moire :

Le symbole courant de sortie ne dpend que du symbole courant d'entre et ne dpend pas des prcdents ni des suivants.

ReprReprsentation graphique :sentation graphique :Le canal effectue donc le couplage entre deux alphabets. La donne essentielle pour comprendre le fonctionnement du canal est ainsi l'ensemble des probabilits conditionnelles.

Prof. M BOUSMAH 33

4. 4. ModModlisation dlisation dun canal:un canal:Graphe de canalGraphe de canal

Le schma complet du fonctionnement du canal est donn par un graphe ou une matrice de canal.

Chaque lien est pondr par la probabilit conditionnelle p( yk / xj ). Si cette probabilit est nulle, nous ne plaons pas de lien.

Prof. M BOUSMAH 34

4. 4. ModModlisation dlisation dun canal:un canal:Matrice de canalMatrice de canal

Matrice de canal :Matrice de canal :Plutt qu'un graphe le canal pet tre modlis par une matrice P des probabilitsconditionnelles ou matrice de canal.

Prof. M BOUSMAH 35

4. 4. ModModlisation dlisation dun canalun canalMatrice de canalMatrice de canal

Prof. M BOUSMAH 36

4. 4. ModModlisation dlisation dun canal:un canal:CapacitCapacit de canalde canal

Un canal lie deux sources d'entre X et de sortie Y. Pour comparer la similitude de ces deux sources, nous avons notre disposition la quantitd'information mutuelle qui est dfinie par :

Les probabilits marginales { p( xj ) } dpendent de la source d'entre et donc du systme de codage de canal utilis. Nous pouvons rechercher un systme de codage qui rende maximal cette quantit, c'est ce qui dfinit la capacit du canal

Prof. M BOUSMAH 37

Les probabilits marginales { p( xj ) } dpendent de la source d'entre et donc du systme de codage de canal utilis.Nous pouvons rechercher un systme de codage qui rende maximal cette quantit, c'est ce qui dfinit la capacit du canal :

La capacit s'exprime en bits/utilisateur de canal.Si la cadence d'utilisation du canal est d'un symbole toute les Tc secondes, le dbit maximum du canal sera C/Tc bits/s.


Prof. M BOUSMAH 38


Relation de Shannon-Hartley

Remarque:Remarque: Un canal est caractUn canal est caractrisris aussi par son Daussi par son Dbit binaire bit binaire D = R logD = R log22(V) (bit/s)(V) (bit/s)R: RapiditR: Rapidit (Baud) V: valence ((Baud) V: valence (nbrenbre ddtats distincts prtats distincts prsents sur le signal)sents sur le signal)

( Capacit( Capacit maximale dmaximale dun canal )un canal )maxmax

maxmax

canal

Prof. M BOUSMAH 39

4. 4. ModModlisation dlisation dun canal:un canal:PropriProprittss

Prof. M BOUSMAH 40


I(X,Y)H(X/Y

)H(X)

H(Y/X)

H(Y)

Equivoque, Incertitude, PerteEquivoque, Incertitude, Perte

Bruit, InsignifiantBruit, Insignifiant

Prof. M BOUSMAH 41


I(X,Y)H(X) H(Y)

Pas de perturbations: Pas de perturbations: H(X/Y)=0 H(Y/X)=0 I(X,Y)=H(X)=H(Y)H(X/Y)=0 H(Y/X)=0 I(X,Y)=H(X)=H(Y)

Prof. M BOUSMAH 42


H(X/Y)

H(Y/X) H(Y)

Equivoque, Incertitude, PerteEquivoque, Incertitude, Perte

Bruit, InsignifiantBruit, Insignifiant

H(X)

Perturbation Forte: Perturbation Forte: I(X,Y)=0 H(X)= H(X/Y) H(Y)=H(Y/X)I(X,Y)=0 H(X)= H(X/Y) H(Y)=H(Y/X)

Prof. M BOUSMAH 43

4. 4. ModModlisation dlisation dun canal:un canal:Cas dCas dun canal binaire symun canal binaire symtriquetrique

Prof. M BOUSMAH 44


Prof. M BOUSMAH 45


Prof. M BOUSMAH 46


Prof. M BOUSMAH 47


Nous retrouvons les conclusions de l'illustration de la notion de quantit d'information mutuelle : lorsque la probabilit d'erreur est de 50%, la capacit du canal est nulle, lorsqu'elle est gale 0% ou 100% la capacit du canal est maximale (une erreur de 100% correspond une simple inversion des bits "0" et "1" par le canal).

ConclusionConclusion

Prof. M BOUSMAH 48

4. 4. ModModlisation dlisation dun canal:un canal:Redondance et EfficacitRedondance et Efficacit

La redondance du canal sera dfinie par :

RRcc=C =C -- I(X,Y) I(X,Y)

La redondance relative du canal sera dfinie par :

cc=1 =1 I(X,Y)/C I(X,Y)/C

Lefficacit du canal sera dfinie par :

cc=I(X,Y)/C =I(X,Y)/C 11

Prof. M BOUSMAH 49

5. 5. Codage de la source:Codage de la source:Codage avec mots de longueur fixeCodage avec mots de longueur fixe

Nous prendrons par la suite le cas d'un codage binaire.

L'galit a lieu lorsque tous les symboles de la source sont quiprobables et lorsque K est une puissance de 2.

Prof. M BOUSMAH 50


Un codage est dit d'autant plus efficaceplus efficace que le nombre de codes possibles inutiliss est faible. L'efficacit dpend aussi de la quantit d'information moyenne de la source. L'efficacit d'un codage sera ainsi dfinie par :

8

Prof. M BOUSMAH 51


Thorme du codage de source, 1er thorme de Shannon :

Prof. M BOUSMAH 52

5. 5. Codage de la source:Codage de la source:Codage, mots de longueur variableCodage, mots de longueur variable

Lorsque tous les symboles de l'alphabet ne sont pas quiprobables, l'extension de source ne permettra pas d'augmenter jusqu' 100% l'efficacit.

Le codage avec mots de longueur variable consiste utiliser un codage plus "long" pour les symboles peu utiliss (de probabilit faible) et un codage "court" pour les symboles les plus utiliss (de probabilit leve).

Prof. M BOUSMAH 53


111111101/8I011110011/8C0110001/4T0011/2S

Code3Code2Code1ProbabilitSourceVoici un exemple:

Supposons que nous cherchions transmettre le message TIC

Code non dcodable de manire instantaneTIC01111011Code3

Code dcodable de manire uniqueTIC10111110Code2

Code non dcodable de manire uniqueTSTS ou TIC001001Code1

ObservationDcodageCodage

Prof. M BOUSMAH 54


Un code prfixe est, par dfinition, un code dont aucun code n'est le prfixe d'un autre.

Un code prfixe est dcodable de manire unique et instantane.

Code prCode prfixefixe

Exemple: code 2

Prof. M BOUSMAH 55


Arbre dArbre dun codeun codeUn codage binaire peut tre reprsent de manire graphique par un arbre. Les arbres sont aussi des reprsentations commodes pour crire les algorithmes de codage et de dcodage. Voici les rgles:

Pour les trois codages prcdents nous obtenons :

Un dplacement gauche correspond un "0". Un dplacement droite correspond un "1". Chaque dplacement cre un nud de l'arbre. Chaque nud un pre (vers le haut) et peut avoir deux fils (vers le bas). Le lien entre deux nuds est une branche. Un nud qui n'a pas de fils est une feuille.

Prof. M BOUSMAH 56

101/8I011/8C001/4T11/2S

Code1ProbabilitSource

Arbre de code 1Arbre de code 1

TT CC II

SS


Prof. M BOUSMAH 57



1111/8I1101/8C101/4T01/2S


SS

TT

CC IIUn code prfixe est un code dont les symboles cods sont des feuilles.

Prof. M BOUSMAH 58



1111/8I0111/8C011/4T01/2S


SSTT

CC II

Prof. M BOUSMAH 59


Longueur moyenne de code :

Pour une source X d'alphabet { Xk } de probabilits associes { Pk }, la longueur moyenne du code sera dfinie par :

o nk est la longueur du code associ au symbole Xk

Prof. M BOUSMAH 60

5. 5. Codage de la source:Codage de la source:Codage de Codage de HuffmanHuffman

Le codage de Huffman est un algorithme de compression de donnes sans perte labor par David Albert Huffman, lors de sa thse de doctorat au MIT. L'algorithme a t publi en 1952 dans l'article: A Method for the Construction of Minimum-Redundancy Codes .

Le codage de Huffman utilise un code longueur variable pour reprsenter un symbole de la source (par exemple un caractre dans un fichier).

Un code de Huffman est optimal pour un codage par symbole, et une distribution de probabilit connue.

Prof. M BOUSMAH 61


Prof. M BOUSMAH 62


Exemple: code 2Exemple: code 2

SSTT

CCII

SS 00 TT1010 II111111 CC110110

Remarque :Remarque : Lors du classement des nuds par probabilits dcroissantes, il se peut que deux nuds aient mmes probabilits. Leur classement est alors arbitraire. Lors de l'implantation des algorithmes, le choix le plus simple au niveau programmation est d'attribuer, en cas d'quiprobabilit, la place la plus leve au dernier nud cr.

Prof. M BOUSMAH 63

5. 5. Codage de la source:Codage de la source:Codage de ShannonCodage de Shannon--FanoFano

Le codage de Shannon-Fano est un algorithme de compression de donnes sans perte labor par Robert Fano partir d'une ide de Claude Shannon.Il s'agit d'un codage entropique produisant un code prfixe trs similaire un code de Huffman, bien que non-optimal, contrairement ce dernier.

Prof. M BOUSMAH 64


1re tapeOn classe les symboles source (par exemple sur une colonne) par ordre de probabilit dcroissante (par exemple de haut en bas),

2me tapeOn divise l'ensemble des symboles en deux sous-ensembles de telle sorte que les probabilits cumules des lments constituant chacun des deux sous-ensembles soient les plus proches. On attribue l'lment binaire "1" (resp. "0") aux lments du sous-ensemble situ en haut (resp. en bas),

3me tapeOn procde comme la premire tape sur tous les sous-ensembles comportant au moins deux lments. On s'arrte lorsque tous les sous-ensembles ne comportent plus qu'un lment.

Algorithme

Prof. M BOUSMAH 65

Merci de votre attention

Prof. M BOUSMAH 66

RRffrencesrences

G.BINET. "THEORIE DE LINFORMATION", Universit de Caen

Richard G. TERRAT. "Thorie de linformation". Universit Montpellier II, Facult des Sciences, Dpartement Informatique, Master

T. Grenier. "Thorie de linformation". INSA de Lyon

RIOUL Olivier. "Thorie de l'information et du codage". Hermes Science - Lavoisier

Thomas M. Cover (Author), Joy A. Thomas. "Elements of Information Theory"

Documents

Bousmah Chapit2 THInfo STIC F(2)