Remerciez-le!

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

1 Principes de communications II MIC4240 1 Chapitre 12 Théorie de l’information

1 Principes de communications II MIC4240 1 Chapitre 12 Théorie de l’information et Codage Adapté de A. Quidelleur, SRC1 Meaux 2007-2008 La théorie de la communication de C. Shannon • Quantité d’information d’une source • Codage de source pour TX le moins de bits possibles • Codage de canal pour assurer une réception sans faute • Ingénieur à Bell Labs. • Publie en 1949, avec W. Weaver « Mathematical Theory of Communications » qui étudie trois aspects d’un système de communications: Source émetteur canal récepteur destination message Signal émis Signal reçu message Codage/modulation Démodulation/décodage bruit 2 « Théorie de l’information » ??? • Dans le langage courant, « information » est utilisé dans divers contextes : actualités, renseignements, etc. • Dans le domaine des télécommunications, la notion d’information est reliée à l’efficacité des systèmes de communication • Shannon montre que l’information contenue dans un message est une grandeur mesurable • La théorie de l’information touche plusieurs domaines • le codage, • la compression de données, • la cryptographie. Quantité d’information et entropie d’une source 4 3 Contenu informatif d’un message • Pour un codage efficace d’un message en une suite de 0 et de 1, il est nécessaire de déterminer son contenu informatif • Exemple • La source transmet toujours la même message, consistant en la lettre A : Le contenu informatif de ce message est nul, car le récepteur n’apprend rien en le recevant • La source émet soit oui, soit non : le récepteur reçoit une information binaire. • La source émet le temps qu’il fera demain : le contenu informatif est très riche, et l’information transmise est m‐aire s’il y a m possibilités de temps. • Un message est « riche » en information si sa connaissance mène à un système plus « prévisible » • Cas d’un message qui peut prendre beaucoup de valeurs différentes. 5 Contenu informatif d’un message et codage • En télécommunication, on veut toujours économiser le nombre de bits transmis pour • Gagner du temps (ex. : téléchargement rapide d’une page web sur Internet) • Faire passer le plus de messages possibles sur un même support (ex. : plusieurs utilisateurs sur la même fibre optique). Influence directe sur le coût des transmissions…! • Ainsi, on souhaiterait 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 mesure de la quantité d’information. 6 4 7 Incertitude, Information et Entropie Définitions – Source discrète : système émettant régulièrement des symboles issus d’un alphabet fini. – Alphabet : ensemble fini des symboles de la source. – Source aléatoire : les symboles sont émis aléatoirement suivant les probabilités : – Source sans mémoire : source aléatoire dont les symboles émis sont statistiquement indépendants.   1 avec 1 , , 1 , 0 ; 1 0         K k k k k p K k p s S P    1 1 0 , , ,   K s s s A  8 Définition : la quantité d’information gagnée à l’observation de l’évènement S = sk , de probabilité pk , est définie par : I (sk) = – log pk Propriétés : • I (sk) = 0 pour pk = 1 ; • I (sk) >= 0 pour 0 <= pk <= 1 ; • I (sk) > I (si) pour pk < pi ; • I (sksl) = I (sk) + I (sl) si sk et sl sont statistiquement indépendants. Si pk = 1/2, alors I (sk) = 1 bit Incertitude, Information et Entropie 5 Entropie d’une source • Considérons une source pouvant émettre N messages différents. Notons pi la probabilité d’émission du message mi. • On appelle entropie de la source S l’espérance mathématique de I (sk) prise comme variable aléatoire • L’entropie fournit une mesure de la quantité d’information moyenne par symbole issue de la source, exprimée en bit/symbole. 9 Source d’information Symbole s1, probabilité p1 Symbole s2, probabilité p2 Symbole s3, probabilité p3 Symbole sN, probabilité pN …                    N k k k N k k k p p p p S H 1 2 1 2 1 log log Exemples • 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é. 10      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                        L’entropie est plus grande quand les messages sont équiprobables. 6 Cas de messages équiprobables • Calculons l’entropie d’une source pouvant émettre N messages équiprobables. • La probabilité de chacun des messages est 1/N. • On retiendra cette formule : 11   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  pour N messages équiprobables Exemples • Exemple 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) = 0 12 7 Exemples • Exemple 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. 13 Exemples • Exemple 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. 14 8 Conclusion • La théorie de l’information fournit un modèle mathématique permettant de quantifier l’information émise par la source d’une communication. • Constat 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. • Constat 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 ! 15 Propriété de l’entropie L’entropie d’une uploads/Management/ ch12-th-info-mb.pdf