Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

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

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 eﬃcacité. § 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 § 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 Source d’information Récepteur codeur canal décodeur bruit Modulateur Démodulateur § 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 diﬀé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 diﬀérents. Notons pi la probabilité d’émission du message mi. § Par définition, on appelle entropie H(S) de la source S la grandeur, exprimée en Shannon, § L’entropie fournit une mesure de la quantité d’information associée à la source. Théorie de l'Information 8 Source d’information Message m1, probabilité p1 Message m2, probabilité p2 Message m3, probabilité p3 Message mN, probabilité pN … ( ) ( ) ∑ ∑ = = ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ⋅ = ⋅ − = N 1 i i 2 i N 1 i i 2 i p 1 log p p log p S H § 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. § 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. – Calculez l’entropie de la source si le dé n’est pas truqué. § Remarque : L’entropie est plus grande quand les messages sont équiprobables. Théorie de l'Information 9 ( ) ( ) ( ) sh 88 , 0 3 , 0 log 3 , 0 7 , 0 log 7 , 0 S H 2 2 = × − × − = ( ) ( ) [ ] ( ) [ ] sh 571 , 2 15 , 0 log 15 , 0 4 2 , 0 log 2 , 0 2 S H 2 2 = × − × + × − × = ( ) ( ) ( ) ( ) ( ) ( ) ( ) sh 585 , 2 6 1 log 6 1 6 S H 6 1 6 P 5 P 4 P 3 P 2 P 1 P 2 = ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ × − × = = = = = = = § Calculons l’entropie d’une source pouvant émettre N messages équiprobables. – La probabilité de chacun des messages est 1/N. – On retiendra cette formule : pour N messages équiprobables Théorie de l'Information 10 ( ) ( ) N log N 1 log N 1 log N 1 N N 1 log N 1 N 1 log N 1 N 1 log N 1 S H 2 2 2 fois N 2 2 2 = ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ − = ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ ⋅ × − = ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ ⋅ − + + ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ ⋅ − + ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ ⋅ − = ! ! ! ! ! ! ! ! ! ! ! " ! ! ! ! ! ! ! ! ! ! ! # $ % ( ) ( ) N log S H 2 = § 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 diﬀé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 diﬀérentes, plus la quantité d’information mesurée est élevée. • Intuitivement, ce résultat est logique. Une source pouvant transmettre beaucoup de messages diﬀérents fournit plus d’information qu’une source transmettant une seule valeur. – 2 . Lorsqu’une source peut produire beaucoup de valeurs diﬀé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 diﬀé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 diﬀérents est maximale lorsque les messages sont équiprobables. – Ce qui signifie que la quantité d’information est maximale lorsqu’on a le plus de diﬃculté à prévoir le résultat. § Exemple : La source émet deux symboles : A et B – _ Cas 1 : La lettre A a « plus de chance » d’être reçue que B. – On a moins d’information que dans le cas 2, où on est incapable de uploads/Philosophie/ theorie-information.pdf