Theorie Information [PDF]

Zitiervorschau

Théorie de l'Information

1

§  §  §  §  § 

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

§  « 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

Théorie de l'Information

4

codeur

canal

Démodulateur

Source d’information

Modulateur

bruit

décodeur

Récepteur

§  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

§  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

§  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 (téléchargement d’une page web sur Internet…) –  Faire passer le plus de messages possibles sur un même support –  Influence directe sur le coût des transmissions…!

§  _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

§  Considérons une source pouvant émettre N messages différents. Notons pi la probabilité d’émission du message mi. Message m1, probabilité p1 Message m3, probabilité p3

…

Source d’information

Message m2, probabilité p2

Message mN, probabilité pN

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

N

∑ i =1

− pi ⋅ log2 (pi ) =

N

⎛1⎞ pi ⋅ log2 ⎜⎜ ⎟⎟ ⎝ pi ⎠ i =1

∑

§  L’entropie fournit une mesure de la quantité d’information associée à la source. Théorie de l'Information

8

§  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. –  Calculez son entropie.

H(S ) = 2 × [− 0,2 × log2 (0,2)] + 4 × [− 0,15 × log2 (0,15 )] = 2,571sh

–  Calculez l’entropie de la source si le dé n’est pas truqué. P(1) = P(2 ) = P(3) = P(4 ) = P(5 ) = P(6 ) =

1 6

⎡ 1 ⎛ 1 ⎞⎤ H(S ) = 6 × ⎢− × log2 ⎜ ⎟⎥ = 2,585sh ⎝ 6 ⎠⎦ ⎣ 6

§  Remarque : L’entropie est plus grande quand les messages sont équiprobables. Théorie de l'Information

9

§  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

= −N ×

1 ⎛1⎞ ⎛1⎞ ⋅ 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

§  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

§  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

§  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

§  La théorie de l’information fournit un modèle mathématique permettant de quantifier l’information émise par la source d’une communication. §  Remarque –  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. –  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é : –  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 Cas 2

P(A) 0,8 0,5

P(B) 0,2 0,5

H(S) 0,722 1

–  _ 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.

Théorie de l'Information

15

§  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

Théorie de l'Information

17

§  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, –  Intuitivement , 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

§  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. –  En pratique, le débit binaire autorisé sur un canal est limité (influence du bruit, nature du support, etc. …).

§  Le théorème de Shannon –  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! –  Remarque : il ne dit pas comment le trouver !

Théorie de l'Information

19

§  Exemple : –  On considère une source émettant les lettres A, B, C, D et E •  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

§  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 donc pas.

Théorie de l'Information

21

§  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). Groupement Probabilités de lettres AA AB BA BB

0,64 0,16 0,16 0,04

Codage 0 10 110 111

Nombre pondéré de bits 0,64 0,32 0,48 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

§  3ème essai : Codage fractionné –  On regroupe cette fois les lettres 3 par 3. Groupement Probabilités de lettres AAA AAB ABA BAA ABB BAB BBA BBB

51,20% 12,80% 12,80% 12,80% 3,20% 3,20% 3,20% 0,80%

Codage 0 100 101 110 11100 11101 11110 11111

Nombre pondéré de bits 0,512 0,384 0,384 0,384 0,160 0,160 0,160 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

§  Algorithme 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 1.  Attribuer 0 par exemple au premier 2.  Attribuer 1 au second. 3.  Recommencer les subdivisions successivement. –  La méthode de Fano fournit un codage binaire instantané. Elle est proche de la méthode de Huffman, utilisée dans les compressions JPEG et MPEG notamment. –  peu de bits aux messages qui reviennent le plus souvent. Les messages les plus rares sont codés par plus de bits. –  è codage à longueur variable ou RLE (Run Length Encoding) ou code entropique. Théorie de l'Information

24

§  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 messages

probabilités

AAA AAB ABA BAA ABB BAB BBA BBB

51,20% 12,80% 12,80% 12,80% 3,20% 3,20% 3,20% 0,80%

probabilités regroupées 51,20%

48,80%

Théorie de l'Information

1er bit 0 1 1 1 1 1 1 1

25

§  2ème regroupement messages probabilités AAA AAB ABA BAA ABB BAB BBA BBB

51,20% 12,80% 12,80% 12,80% 3,20% 3,20% 3,20% 0,80%

probabilités 2ème 1er bit regroupées bit 0 1 0 24,80% 1 0 1 1 1 1 24,00% 1 1 1 1 1 1

Théorie de l'Information

26

§  3ème regroupement messages

Deux sousregroupements

AAA AAB ABA BAA ABB BAB BBA BBB

probabilités 51,20% 12,80% 12,80% 12,80% 3,20% 3,20% 3,20% 0,80%

probabilités 2ème 3ème 1er bit regroupées bit bit 0 12,80% 1 0 0 12,80% 1 0 1 12,80% 1 1 0 1 1 1 1 1 1 10,40% 1 1 1 1 1 1

Théorie de l'Information

27

§  4ème regroupement messages AAA AAB ABA BAA ABB BAB BBA BBB

probabilités 2ème 3ème 4ème probabilités 1er bit regroupées bit bit bit 51,20% 0 12,80% 1 0 0 12,80% 1 0 1 12,80% 1 1 0 3,20% 1 1 1 0 6,40% 3,20% 1 1 1 0 3,20% 1 1 1 1 4% 0,80% 1 1 1 1

Théorie de l'Information

28

§  5ème regroupement messages AAA AAB ABA BAA ABB BAB BBA BBB

probabilités 51,20% 12,80% 12,80% 12,80% 3,20% 3,20% 3,20% 0,80%

probabilités 2ème 3ème 4ème 5ème 1er bit regroupées bit bit bit bit 0 1 0 0 1 0 1 1 1 0 3,20% 1 1 1 0 0 3,20% 1 1 1 0 1 3% 1 1 1 1 0 0,80% 1 1 1 1 1

Théorie de l'Information

29

Théorie de l'Information

Longueur croissante

Probabilités décroissantes

Code Messages Probabilités 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

30

§  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

31

Théorie de l'Information

32

§  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 reconstitué

0

1

1

0

1

0

Théorie de l'Information

0

1

1

1

33

§  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.

n 

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

34

§  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

35

§  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

36

Théorie de l'Information

37

§  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

38

§  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

39

§  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

40

§ 

« 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

41

42

§  Premières tentatives de définition de mesure de l'information 1920 §  Théorie de l'information : à partir de 1948, travaux de Shannon §  Théorie de l'information : discipline fondamentale qui s'applique dans le domaine des communications. –  déterminer les limites imposées par les lois de la nature lorsqu'on doit stocker ou transmettre le contenu d'une source (d'information), –  proposer des dispositifs permettant d'atteindre ou d'approcher ces limites. –  La théorie de l'information ne cesse de se développer car les exigences actuelles s'orientent vers une augmentation constante de l'information à stocker ou à transmettre.

43

Compression du contenu de la source d'information nécessaire. Peut s'envisager sous deux formes : –  – sans perte d'information; –  avec perte d'information.

44

Représentation du schéma d'une communication Source

Codage source

Codage canal C A N A L

Mots source restitués

Décodage source

Décodage canal

§  Le codage de source consiste à éliminer les redondances de la source • Le codage de source consiste à éliminer les redondances de la source afin d'en réduire le débit binaire. afin d'en réduire le débit binaire. Lecodage codagede decanal canalaa un un rôle rôle de de protection protectioncontre contreles les erreurs erreurs (dues (dues àà • §  Le transmissionsur surlelecanal) canal)qui quiest estassuré assuré en ajoutant de lalatransmission de la la redondance redondance(codes (codes correcteurs correcteurs d'erreurs). d'erreurs). • Les points de vue codage de source et codage de canal sont donc §  fondamentalement Les points de vue différents. codage de source et codage de canal sont donc fondamentalement différents. Florent Dupont

Master Informatique - UCBL

45

57

§  Incertitude d’un événement ou self-information ou quantité d’information. –  Une information est un élément de connaissance qui peut être conservé (mis en mémoire), traité (traitement de l’information) ou transmis. –  La difficulté rencontrée pour définir la quantité d’information relative à un événement est liée au caractère subjectif de l'information effectivement apportée par la réalisation de cet événement. –  La quantité d’information est relative à un contenu statistique, plus grande si on ne s'attend pas à ce que l'évènement se réalise.

46

§  Définition –  Soit un événement E, une probabilité d’apparition p(E), la quantité d’information I(E) liée à l’apparition de E s’exprime : –  I(E) = -log [P(E)]

§  Propriétés : –  –  –  – 

I(E) est d’autant plus grande que P(E) est petite ; Si E est toujours réalisé I(E)=0 ; Si E est très rare, P(E) est proche de 0, I(E) tend vers l’infini ; P(E)≤1 donc I(E)≥0.

§  Logarithme –  népérien pour les signaux continus : –   à base 2 pour les signaux discrets –  (l’unité est le bit, abréviation de binary unit). 47

§  Un événement qui a une chance sur 2 de se produire conduit à une quantité d’information de -log2 (1/2) = 1 bits §  Une source peut délivrer 8 événements équiprobables : Itotal = -8*log2 (1/8) = 24 bits –  a priori, par l'incertitude qui règne sur la réalisation de E; –  a posteriori, par l'information apportée par la réalisation de E.

48

§  L'information apportée par F sur E est la diminution de l'incertitude sur E lorsque F est réalisé. §  Information mutuelle I(E;F)=IFE =I(E)-I(E/F)=IEF –  car E et F jouent le même rôle.

§  Démonstration : IF⁄E = -log[P(E)]+log[P(E/F)] = -log[P(E)]+log[P(E∩F)/P(F)] = -log[P(E∩F)/ P(E)P(F)] = IE⁄F   49

Information mutuelle de 2 évènements • Si E et F sont indépendants, §  • Si E et F sont indépendants, P(F)0.et I(E;F)= 0. alorsalors P (F/E)P= (F/E) P(F) et = I(E;F)= On obtient alors:I(E∩F)=I(E)+I(F)-I(E;F) •§  On obtient alors : I(E F)= I(E )+ I(F)- I(E;F) On peut résumer les relations précédentes précédentes sur un •§  On peut résumer les relations sur un §  diagramme de Venn :  diagramme de Venn : I(E)

I(F) I(E;F)

Florent Dupont

Master Informatique - UCBL

62

50

Entropie • Entropie d'une variable aléatoire discrète – Soit X une variable aléatoire à valeurs dans –  Soit X une variable aléatoire à valeurs dans {x1,x2 ,...,xn} telle que pi {x1,pour x2 ,..., telle que pi = P(X = xi) pour i de 1 à n. =P(X=xi) i de x 1 nà} n. – L'entropie X est notée H(X) des estincertitudes la moyenne des –  L'entropie de X notée de H(X) la moyenne calculée incertitudes calculée sur les événements {X = xi} sur les événements {X = xi}

§  Entropie d'une variable aléatoire discrète

H(X) -

i n

pi log pi

i 1

§  L’entropie d’une source discrète est donc la quantité • L’entropie d’une source discrète estmoyenne donc la quantit d’information par symbole et est exprimée en bits par moyenne d’information par symbole etsymbole. est exprimée e

bits par symbole.

Florent Dupont

Master Informatique - UCBL

51

§  Remarques –  H(X) dépend de la loi de probabilité de X mais n'est pas fonction des valeurs prises par X; –  H(X) correspond à l'espérance mathématique de la variable aléatoire incertitude I(X) définie par I(X) = -log P(X); –  Exprimée en Shannons, H(X) représente le nombre moyen de bits nécessaires à la codification binaire des différentes réalisations de X.

§  Le taux (débit) d’information est le nombre de symboles par unité de temps : T = n H(X) en bits par seconde.

52

§  On extrait au hasard une carte d'un jeu de 32 cartes. §  On a H(X)=-32 x 1/32 x log2 1/32=log2 32=5Sh. §  Pour savoir quelle carte a été extraite, on peut demander si sa couleur est rouge ou noire, s'il s'agit d'un cœur ou d'un carreau, etc. Les réponses à cinq questions peuvent être résumées par cinq bits ('1' pour oui et '0' pour non). §  Une autre façon de modéliser le problème consiste à attribuer un numéro (de 0 à 31) à chaque carte. L'écriture de ces numéros en base deux requiert log2 32 = log2 25 = 5 bits.

53

Exemple • Soit une source à 2 symboles §  L'entropie d'une variable aléatoire X à n binaire valeurs possibles est : X maximum et vaut log(n)H(X)= lorsque loi de– X est uniforme. P -p la log[p] (1-p) log(1-p) –  En effet, l'incertitude sur X est la plus grande si toutes les valeurs p=0 (x2 toujours réalisé) H(x)=0 possibles ont la même probabilité de se réaliser; p=1 (x1 toujours réalisé) H(x)=0 lorsque le nombre de valeurs possibles p=0,5 (x1 et x2 équiprobables) H(x)=1

§  L'entropie augmente augmente. §  Soit une source binaire à 2 symboles : H(X)= -p log[p] – (1-p)log(1-p) Exemple

naire à 2 symboles : X P 1-p) log(1-p)

H(X) 1 bit

x1 x 2 p 1 p

 

alisé) H(x)=0 –  p=0 alisé) H(x)=0 p=1 iprobables) – H(x)=1

X)

(x2 toujours réalisé) H(x)=0 (x1 toujours réalisé) H(x)=0 Florent Dupont –  p=0,5 (x1 et x2 équiprobables)

0

0,5

1

Master Informatique - UCBL

H(x)=1 54

p

§  Soient X et Y deux variables aléatoires discrètes à valeurs dans {x1, x2 ,..., xn} et {y1, y2 ,...,ym }. §  Si on désigne par pij =P(X=xi ∩Y=yj) la loi du couple (X, Y), on peut définir les entropies conditionnelles et l'information mutuelle : §  H(X/Y) représente l'incertitude sur X lorsqu'on connaît Y. §  De même l'information mutuelle moyenne entre X et Y peut s'écrire : I(X;Y) = H(X) - H(X / Y) = H(Y) - H(Y/X) §  I(X;Y) correspond à la diminution de l'incertitude sur X (resp. Y) lorsqu'on connaît Y (resp. X).

55

• L'information mutuelle moyenne de X et de Y est toujours positive (ce n'est pas le cas pour l'information mutuelle entre deux événements qui prend des valeurs négatives lorsque la réalisation l'untoujours des événements §  L'information mutuelle moyenne de X et dede Y est positive rend l'autre moins probable); (ce n'est pas le cas pour l'information mutuelle entre deux • Lequi conditionnement En d'autres événements prend des valeurs diminue négatives l'incertitude. lorsque la réalisation de termes cela signifie que H(X) H( X / Y) l'un des événements rend l'autre moins probable); • H(X) + H(Y) = H(X,Y) + I(X;Y) §  Le conditionnement diminue l'incertitude. En d'autres termes cela • H(X,Y) = H(X) + H(Y/X) = H(Y) + H(X/Y) signifie que • Diagramme de Venn : –  H(X) ≥ H( X / Y) H(X) H(X/Y) –  H(X) + H(Y) = H(X,Y) + I(X;Y) –  H(X,Y) = H(X) + H(Y/X) = H(Y) + H(X/Y)

H(Y)

H(Y/X) I(X;Y)

§  Dans le cas particulier où X et Y Diagramme de Venn Florent Dupont on obtient : Master Informatique - UCBL sont indépendantes,

6

–  H(X/(Y=y))=H(X) –  H(X/Y)=H(X) –  I(X;Y)=0 56

Source discrète

Suite de variables aléatoires, ayant chacune un nombre fini de réalisations. Symbole – Lettre Le plus petit élément irréductible contenant une information Alphabet Ensemble des mots possibles avec l'alphabet de la source Mot Suite finie de lettres Vocabulaire Ensemble de lettres que peut délivrer la source Suite finie de lettres Codage Correspondance entre deux vocabulaires Source Source dans laquelle la probabilité d'apparition stationnaire d'un caractère ne dépend pas de ce qui est (ou sans apparu auparavant. La loi de probabilité ne mémoire) dépend pas de l’instant considéré 57

§  Comme pour une variable aléatoire, on souhaite caractériser une source discrète par son entropie. §  Si S est une source sans mémoire (les valeurs Si émises par la source sont indépendantes), alors on appelle H(Si) l’entropie par lettre source Si H(Si) = -p(Si) log (p(Si)).

58

§  Soit S une source discrète à N valeurs possibles et d'entropie H (S)< log2 N . L'entropie relative Hr(S) =H(S)/log2 N étant < 1, la redondance r = 1 - Hr(S) est différente de zéro. §  Codage source = élimination de la partie redondante de l'information délivrée par la source = réduction du débit binaire de la source tout en conservant l'information (compression sans perte d'information) §  Deux types de codes peuvent être utilisés : –  Codes à longueur fixe. Tous les mots ont même longueur (même nombre de symboles) –  Codes à longueur variable. La longueur des mots varie en fonction de leur fréquence d'apparition. Un mot sera d'autant plus long que sa probabilité d'apparition sera petite. 59

§  Soit B un alphabet de référence (un ensemble de lettres), en général B est l'alphabet binaire B = {0,1}. §  En concaténant des lettres de l'alphabet B,on forme des mots dont la longueur correspond au nombre de lettres utilisées. Un code C est un ensemble de mots. §  Exemples : –  B={0,1}est un code de longueur fixe=1 –  C={00,01,10,11}est un code de longueur fixe=2

§  On dira qu'un code est uniquement déchiffrable (ou à décodage unique) si toute suite de mots code ne peut être interprétée (décodée) que d'une seule manière. §  Exemples : –  {0,11,010} est uniquement déchiffrable. –  {0,1,101}n'est pas uniquement déchiffrable car 101 peut être interprété comme 1-0-1 ou 101. 60

§  Un code préfixe est un code pour lequel aucun mot n'est le début d'un autre mot. Ce code est uniquement déchiffrable et est dit à décodage instantané. §  Construction d'un code préfixe : utiliser un arbre dont chaque branche représente une lettre de l'alphabet élémentaire (alphabet de référence). Il faut alors choisir les mots de telle sorte que pour tout couple de mots, le chemin permettant de conduire à l'un des mots ne soit pas inclus dans le chemin menant à l'autre mot. §  Exemples : –  {0,10,110,111} est un code préfixe. –  {0,11,110,111} n'est pas un code préfixe car le chemin menant à 11 est inclus dans les chemins menant à 110 et 111.

61

Codage d'une variable aléatoire discrète • Longueur moyenne descode mots §  Longueur moyenne des mots : code :

n

M i 1

§ 

pin(i)

avec : avec : • M = nombre de mots code; – • pi M==fréquence nombre de motsd'code; relative apparition du mot code n° i; longueur du mot code n° i. – • n(i) pi ==fréquence relative d' apparition du mot code n°

i;

–  n(i) = longueur du mot code n° i.

Florent Dupont

Master Informatique - UCBL

77

62

§  Théorème 1 –  Pour tout codage d'une variable aléatoire X par un code uniquement déchiffrable (sur un alphabet de référence à b lettres), la longueur moyenne des mots code vérifie: H(X) ≤ nlog(b) où la base du logarithme coïncide avec celle utilisée pour la mesure de H(X) (entropie de X).

§  Théorème 2 –  Pour toute variable aléatoire X, il existe un code préfixe tel que : nlog(b) < H(X) + log(b)

63

§  Finalement, on déduit que pour tout codage d'une variable aléatoire X, il existe un code uniquement déchiffrable qui vérifie: §  H(X)/log(b) ≤n< H(X)/log(b) +1 §  La limite inférieure ne peut être dépassée par aucun code.

64

65

§  = code ternaire : point, trait et pause §  A chaque lettre une succession d'émissions de courants brefs (points) et longs (traits) séparés par des pauses courtes. §  Entre chaque lettre est insérée une pause plus longue §  Les mots sont séparés par une pause deux fois plus longue que celle disposée entre les lettres. §  Aux lettres les plus fréquentes sont affectées les mots code les plus courts

66

Code Morse Lettre A B C D E F G H I J K L M ESP

Fréq. 0,0642 0,0127 0,0218 0,0317 0,1031 0,0208 0,0152 0,0467 0,0575 0,0008 0,0049 0,0321 0,0198 0,1859

Code ._ _... _._. _.. . .._. __. .... .. .___ _._ ._.. __

Durée Lettre 9 N 13 O 15 P 11 Q 5 R 13 S 13 T 11 U 7 V 17 W 13 X 13 Y 11 Z 6

Fréq. 0,0574 0,0632 0,0152 0,0008 0,0484 0,0514 0,0796 0,0228 0,0083 0,0175 0,0013 0,0164 0,0005

Code _. ___ .__. __._ ._. ... _ .._ ..._ .__ _.._ _.__ __..

Durée 9 15 15 17 11 9 7 11 13 13 15 17 15 67

Durée du point avec pause courte = 2, durée du trait avec pause courte = 4,

§  1er code utilisé pour exploiter la redondance d'une source (années 50) §  Algorithme –  1. Classer les différents symboles à coder suivant l'ordre décroissant de leur probabilité –  2. Divisercessymbolesendeuxsous-groupesdetellesortequeles probabilités cumulées de ces deux sous-groupes soient aussi proches que possible l'une de l'autre. –  3. Affecter le chiffre binaire "0" au 1er sous-groupe et "1" au 2ème sous groupe. –  Les mots code du premier sous-groupe commenceront tous par "0" tandis que ceux du second commenceront par "1". –  4. Recommencerà1jusqu'àcequelessous-groupesnecontiennent qu'un élément.

§  Tous les symboles source ont alors un mot code. 68

Code de Shannon-Fano - Exemple • Exemple §  Exemple: : –  Soit une source cinqsymboles symboles A,A, B, B, C, D, Soit une source avecavec cinq C,ED, E Symbole

Fréquence Première d'apparition division

Deuxième division

Troisième division

Quatrième division

Code binaire

A

15/39

0

0

00

B

7/39

0

1

01

C

6/39

1

0

D

6/39

1

1

0

110

E

5/39

1

1

1

111

§ 

10

La longueur moyenne d'un mot code est : –  La longueur moyenne d'un mot code est : 2x15/39 2x7/39 2x6/39 3x6/39 3x5/39 2,28 bits –  2x15/39+ 2x7/39+ 2x6/39+ 3x6/39+ 3x5/39 = 2,28 bits Meilleur qu'un code binaire simple à longueur fixe: 3 bits i n –  Meilleur qu'un code binaire simple à longueur fixe: 3 bits Entropie de la source (limite) H(X) - pi log2 pi 2 18 Sh –  Entropie de la source (limite) H(X) = - i∑pi 1 log2 pi = 2,18 Sh Florent Dupont

Master Informatique - UCBL

83

69

§  La construction de l'arbre permettant d'affecter aux n lettres source un mot code s'effectue de façon ascendante (contrairement au code de Shannon-Fano). §  1. Classer les lettres source suivant l'ordre décroissant de leur probabilité. §  2. Créer un nouveau symbole à partir des deux lettres source de probabilités les plus faibles. On lui affecte une probabilité égale à la somme des probabilités des deux lettres source. §  3. Considérantlesn-1lettressourcerestantes,reveniràla première étape jusqu’à ce qu'il ne reste plus que 2 lettres source. §  4. Affecter "0" au 1er sous-groupe et "1" au 2ème sous groupe à chaque étape.

70

Code de Huffman- Exemple

§  Exemple

–  Même source que l'exemple précédent • Même source que l'exemple précédent 1

2 8

A 15/39

3 7

1

A

15/39

1

4

5

6 A

15/39

1

B

7/39

000

D E

11/39

01

BC 13/39

00

C

6/39

001

B

7/39

000

DE 11/39

01

D

6/39

010

C

6/39

001

E

5/39

011

La § longueur moyenne d'un mot code est : La longueur moyenne d'un mot code est : 1x15/39 +3x +3x (1 -15/39) = =2,23 1x15/39 (1 -15/39) 2,23bits bits

BCDE 24/39 A

15/39

Toujours Shannon-Fano (2,28 bits) de la §  Toujoursmeilleur meilleur que que Shannon-Fano (2,28 bits) Entropie source (2,18 = limite Entropie de laSh) source (2,18 Sh) = limite 71

0 1

§  • Le codage de Huffman (comme celui de Shannon-Fano) nécessite la connaissance des probabilités a priori des lettres source. §  Sinon estimation en mesurant les fréquences d'apparition dans le message à transmettre --> transmettre l'arbre des codes pour que le décodage soit possible. §  • Pour améliorer les performances, élever l'ordre d'extension de la source (ordre n = prendre n symboles à la fois pour les coder). Inconvénient : l'arbre des codes à transmettre plus long. §  Exemple : si la source émet des symboles du code ASCII étendu, il y a 256 caractères. extension d'ordre 2 = d'une table de probabilités de 2562 = 65536 nombres! §  gain obtenu par la compression inutile pour des messages courts. §  Pour pallier cet inconvénient, on a introduit le code de Huffman adaptatif dont le principe repose sur la mise à jour des statistiques sur les symboles au fur et à mesure de la lecture du message. 72

Codage arithmétique

cipe : affecter à l'ensemble du message un seul §  • Principe : affecter à l'ensemble du message un seul nombre en bre en virgule virguleflottante flottante mple : §  BALLE • Exemple : BALLE Symbole

A

B

E

L

abilités Pi 1/5 1/5 1/5 2/5 valles [0,2;0,4[ [0,4;0,6[ [0,6;1[ Intervalle [0;0,2[ > [0,2;0,4[ §  B --> [0,2;0,4[ -> [0,2+0,2*0; 0,2+0,2*0,2[ = [0,2; 0,24[ §  BA --> [0,2+0,2*0; 0,2+0,2*0,2[ = [0,2; 0,24[ --> [0,2+0,04*0,6; 0,2+0,04*1[ = [0,224; 0,24[ §  BAL --> [0,2+0,04*0,6; 0,2+0,04*1[ = [0,224; 0,24[ aleur soulignée = longueur de l'intervalle précédent) §  ... (valeur soulignée = longueur de l'intervalle précédent) orne inférieure code le message : 0,23616

Dupont

§  La borne inférieure code le message : 0,23616 Master Informatique - UCBL

87

73

cipe : affecter à l'ensemble du message un seul bre en virgule flottante mple : BALLE Symbole

A

B

E

L

abilités Pi 1/5 1/5 1/5 2/5 valles [0,2;0,4[ [0,4;0,6[ [0,6;1[ Intervalle [0;0,2[ > [0,2;0,4[ -> [0,2+0,2*0;•  0,2+0,2*0,2[ = [0,2; 0,24[- 0,2)/0,2 = 0,1808 0,23616 --> B (0,23616 •  0,1808 --> A = (0,1808 - 0)/0,2 = 0,904 --> [0,2+0,04*0,6; 0,2+0,04*1[ [0,224; 0,24[ •  0,904 (0,904 – 0,6)/0,4 = 0,76 aleur soulignée = longueur--> deLl'intervalle précédent) •  0,76 --> L (0,76 – 0,6)/0,4 = 0,4 orne inférieure code le message : 0,23616

Dupont

•  0,4

--> E

§  Le décodeur doit connaître les intervalles associés aux lettres Master Informatique - UCBL

87

74

§  • Aprèsavoircaractériséuncanaldupointdevue de la théorie de l'information en introduisant sa capacité, nous allons maintenant nous intéresser à la qualité de la transmission en termes de probabilité d'erreur. §  • 2 théorèmes fondamentaux: §  – Le 2ème théorème de Shannon qui énonce une condition d'adéquation entre la source et le canal pour obtenir un taux d'erreur aussi faible que souhaité. §  – Le théorème réciproque du deuxième théorème de Shannon qui fournira un minorant de la probabilité d'erreur lorsque la condition d'adéquation source canal n'est pas satisfaite.

75

§  • L'incertitude qui subsiste sur X lorsque Y est connue peut être divisée en deux termes : §  – un premier terme qui correspond à l'incertitude liée à la question de savoir si oui ou non une erreur a été commise ; §  – un second terme relatif à l'incertitude sur le symbole qui a été effectivement émis lorsque l'on commet une erreur (cette incertitude concerne les m-1 symboles autres que celui reçu et ceci avec la probabilité pe). §  • On obtient donc l'inégalité de Fano : H(X/Y) ≤ H2(pe)+ pe log2 (m-1)

76

§  Codage de canal • 2ème théorème de Shannon §  Soient un canal discret sans mémoire de capacité C et une source discrète stationnaire d'entropie R. §  Alors si R < C, ∀ є > 0 il existe un code de longueur n tel que la probabilité d'erreur pe après le décodeur soit §  inférieure à є si le code est utilisé sur le canal.

77

§  • Ce théorème donne tout son sens à la notion de capacité que l'on peut interpréter comme la quantité maximum d'information qui peut être transmise sans erreur. §  • Le résultat énoncé par ce théorème est surprenant, en ce sens qu'a priori, on ne pouvait envisager d'effectuer une transmission sur un canal bruité, avec un taux d'erreur aussi faible que souhaité. §  • Contrairement au théorème de codage de source, le 2ème théorème de Shannon n'indique pas comment construire le code bloc optimum.

78

peut interpréter comme la quantité maximum d'information qui pe être transmise sans erreur. • Le résultat énoncé par ce théorème est surprenant, en ce sens qu'a priori, on ne pouvait envisager d'effectuer une transmission sur un canal bruité, avec un taux d'erreur aussi faible que souhaité. §  Les codes correcteurs d'erreurs permettent de réduire la probabilité • Contrairement au théorème de codage de source, le 2ème théorème d'erreur sur unn'indique canal. Cette obtenue ajoutant de la Shannon pas réduction comment sera construire le en code bloc optimum. Les codes d'erreurs permettent de réduire la probabi redondance aux correcteurs messages à transmettre. d'erreur sur un canal. Cette réduction sera obtenue en ajoutant de l §  • En redondance pratique, il faut la condition Entropie < Capacité soit aux que messages à transmettre. vérifiée un même laps delatemps. • En sur pratique, il faut que condition Entropie < Capacité soit vérifiée un même laps de temps. §  Si le sur débit source Ds = 1/Ts (resp. le débit canal Dc = 1/Tc), on Si le débit source Ds = 1/Ts (resp. le débit canal Dc = 1/Tc), on devra devravérifier vérifier: : entropie unité de temps Florent Dupont

capacité unité de temps

H( X) Ts

C Tc

Master Informatique - UCBL

79

§  Le nombre d’erreurs de transmission est très variable : Probabilité d’erreur de 10-3 (RTC de mauvaise qualité) §  à 10-12 / 10-15 §  3 opérations peuvent être mises en place : –  la détection d’une erreur, –  sa localisation –  et sa correction.

§  La protection peut s’appliquer à deux niveaux : –  au niveau bit ou caractère (bit de parité) ; –  au niveau de la trame (CRC) ou du paquet réseau.

80

Un codeur est introduit avant la transmission sur canal décodeur est placé sur enlesortie § leUn codeuret estun introduit avant la transmission canal etdu un canal. décodeur est placé en sortie du canal. Perturbations

X

Codeur

Décodeur

Y

Canal de transmission et récepteur

§  Codeur : introduit de la redondance : C(n,k) = r n : bits à transmettre, k : redondance §  • Il existe différentes classes de codes: –  En bloc : les r bits rajoutés ne dépendent que des k bits d’information. •  Détection d’erreur : parité, codes polynomiaux, codes cycliques. •  Correction d’erreur : codes de Hamming, codes BCH). Florent Dupont Master Informatique - UCBL 119 –  Conventionnels (ou récurrents). –  Turbo-codes 81

§  Parité simple : à chaque caractère, un bit est ajouté. §  Exemple : –  0011010 0 parite impaire –  0011010 1 parite paire –  Dans ce cas, on est capable de détecter une erreur de parité, mais pas de la localiser.

§  Parite double : à chaque bloc de caractère, on ajoute un champ de contrôle supplémentaire (LRC : Longitudinal Redondancy Check, VRC : Vertical Redondancy Check)

82

§  Exemple : §  pour les données 0011010 1100101 0101010 §  00110101 11001010 parite LRC et VRC paire 01010101 §  10101010 §  La suite 00110101 11001010 01010101 10101010 est émise. §  La combinaison de LRC et VRC permet de détecter 2 erreurs dans un seul mot ou de corriger 1 erreur.

83

§  Détection d’erreur par code cyclique §  • Un mot de code est représenté sous forme polynomiale dans laquelle la suite de bits à transmettre M=m1m2...mn est représentée par M(x) = u1+u2x+...+unxn-1 §  • Par exemple 1100101 est représenté par 1x6+1x5+0x4+0x3+1x2+0x +1 c’est à dire x6+x5+x2+1

84

§  Principe de détection : §  • On utilise le reste R(x) de la division polynomiale M(x) par un polynôme diviseur G(x) qui donne un quotient Q(x). R(x) est calculé par l’émetteur puis transmis au récepteur. Le récepteur fait le même calcul R’(x) en divisant M(x)+R(x) (message + contrôle). §  Si R’=0 alors pas d’erreur, si R’≠0 alors erreur. • M(x) – R(x) est divisible par G(x) et est équivalent à §  M(x) + R(x) modulo 2. §  • Cette méthode fonctionne bien car la table de vérité de l’addition (en modulo 2) équivaut au ou exclusif (XOR).

85

§  Exemple de polynôme générateur : • Suivant l’avis V41 du CCITT : G(x) = x16+x12+x5+1 §  • Autreexemple:calculdeLRCensérie §  Transmission de 2 octets §  01001101 01101111 00100010 = LRC §  • LRCsur1octetestuncodecycliquedepolynôme générateur x8+1

86

§  § • § • § •

Codes détecteurs d’erreur Codes détecteurs d’erreur

•22octets octetsprécédents précédents :: 01001101 01001101 01101111 01101111 == x14x14+x11+x10+x8+x6+x5+x3+x2+x+1 +x11+x10+x8+x6+x5+x3+x2+x+1 •M(x) M(x) 8 M(x ) = x22+x19+x18+x16+x14+x13+x11+x10+x9+ x8 (on multiplie par x8 x • x8 M(x ) = x22+x19+x18+x16+x14+x13+x11+x10+x9+ x8 (on pour faciliter la division) par x8 =pour faciliter la division) 8+1) • multiplie x8 M(x ) / (x §  •x22+x19+x18+x16+x14+x13+x11+x10+x9+ x8 x8+1 §  § • § •

-x5-x ou +x5+x

x14+x11+x10+x8+x5+x

R(x)=x5+x 00100010 on trouve comme précédemment ! ! 5+x On transmet donc : 01001101 01101111 00100010 R(x)=x 00100010 on trouve comme précédemment ! ! : 01001101 00100010 •On Letransmet récepteurdonc divise le message01101111 reçu par x8+1 pour vérifier qu’il n’y a pas d’erreur. • Le récepteur divise le message reçu par x8+1 pour vérifier qu’il n’y a §  Pour fabriquer ces codes à la volée, on utilise un registre à décalage pas d’erreur. ainsi que un ou plusieurs ou exclusif. Pour fabriquer ces codes à la volée, on utilise un registre à décalage ainsi que un ou plusieurs ou exclusif. 87

§  • La capacité de correction est d'autant meilleure que les "mots" du code diffèrent beaucoup entre eux. §  • "distance" minimale entre deux mots, la distance étant le nombre de symboles qui diffèrent ; §  • Exemple, la distance dite "de Hamming" – « nombre de différences » entre 10100111 et 10111111 vaut 2, tandis que celle entre 10100111 et 11000001 vaut 4. §  • Plus la distance minimale est élevée, plus le code peut corriger d'erreurs. §  • On peut augmenter la distance minimale entre mots en rajoutant des bits. Mais rallonger le message accroît la durée et le coût des communications. §  Objectif : trouver des algorithmes de codage performants, qui permettent de détecter et de corriger le maximum d'erreurs, tout en allongeant le moins possible les mots. De plus, les procédures de 88 codage et de décodage doivent être suffisamment simples.