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 2011 - 2012 EISTI Guy Almouzni THEORIE DE L’INFORMATIO

Théorie de l’information 2011 - 2012 EISTI Guy Almouzni THEORIE DE L’INFORMATION Théorie de l’information 0. Préambule 0. 1 Table des matières 1. Modélisation mathématique d’une source d’information 1. Représentation mathématique d’une source 2. Information propre 3. Information conditionnelle 4. Information mutuelle 5. Information et incertitude 6. Entropie d’une source 6.1. Interprétations de la fonction d’entropie 6.2. Propriétés générales de la fonction d’entropie 2. Cryptographie 1. Quelques définitions 1.1 Quelques exemples élémentaires 1.1.1 Chiffrement de César (50 av. J.C.) 1.1.2 Substitution polyalphabétique 1.1.3 Chiffrement de Vernam 2. La théorie de C. Shannon sur la sécurité entropique 3. Codage de source 1. Codage 2. Premier théorème fondamental 2.1. Codage de source 2.1.1. Le problème de décodage unique 2.2. Le premier théorème de Shannon 2.2.1. Borne inférieure de longueur moyenne de code 2.2.2. Borne supérieure de longueur moyenne de code 2.2.3. Extension de source et le premier théorème de Shannon 3. Construction de codes optimaux 3.1. Codes binaires instantanés et arbres 3.1.1. Quelques rappels sur les arbres 3.1.2. Représentation de codes instantanés par les arbres 4. Méthode de Huffman de construction de codes optimaux 4. Compression de données 1. Codage et compression 2. Algorithmes de compression statistiques 2.1. Méthode de Shannon-Fano 2.1.1. Exemple 2.2. Algorithme de Huffman 3. Codes à dictionnaire 3.1. LZ78 3.1.1. Codage 3.1.2. Décodage 3.2. LZW 3.3. Remarques 4. Exemple. Compression d’images 4.1. Codage RLE (Run Length Encoding) 4.2. Codage différentiel 4.3. Méthodes mixtes 5. Modélisation mathématique d’un canal 1. Quelques notions utiles de probabilités 2. Définitions et propriétés essentielles 3. Information mutuelle moyenne 4. Description mathématique d’une communication 5. Canal discret stationnaire, sans mémoire. Entropie conjointe - Entropie conditionnelle 5.1. Exemple complet 5.2. Exemples fréquents de canaux 5.2.1. Canal avec entrée et sortie indépendantes 5.2.2. Canal sans pertes 5.2.3. Canal déterministe 5.2.4. Canal sans bruit 5.2.5. Canal inutile 5.2.6. Canal symétrique 6. Capacité d’un canal 6.1. Capacité d’un canal symétrique 6. Codage de canal 1. Second théorème de Shannon 1.1. Codage de canal 1.1.1. Règle de décodage d’un canal avec bruit 1.1.2. Notion de code de canal 1.2. Second théorème de Shannon 2. Codes correcteurs d’erreurs 2.1. Généralités 2.2. Un premier exemple illustratif 2.3. Groupe k G 2.4. Distance de Hamming et décodage du maximum de vraisemblance 2.4.1. Distance de Hamming 2.4.2. Décodage au sens de maximum de vraisemblance 2.5. Codes correcteurs 2.5.1. Détection et correction d’erreurs 2.6. Codes linéaires correcteurs d’erreurs 2.6.1. Matrice de contrôle et décodage d’un code linéaire Théorie de l’information 0. Préambule 0. 2 Bibliographie [0] Anya Désilles. Théorie de l’information. Polycopié de cours, 2010. [1] Robert B. Ash. Information theory. Dover Publications Inc., 1965. [2] David J.C. MacKay. Information Theory, Inference and Learning Algorithms. Cambridge University Press, 2003. Disponible au téléchargement gratuit sur http://www.inference.phy.cam.ac.uk/mackay/itila/book.html. [3] John R. Pierce. An Introduction to Information Theory. Symbols, Signals and noise. Dover Publications Inc, NY 1980. [4] Fazlollah M. Reza. An introduction to information theory. Dover Publications Inc., 1994. [5] Julien Salomon. Traitement numérique du signal. Polycopié de cours, 2009. [6] Olivier Rioul. Théorie de l’information et du codage. Hermes Lavoisier, 2007. Ce polycopié s’inspire de celui d’Anya Désilles [0] que je remercie très chaleureusement. Théorie de l’information 0. Préambule 0. 3 Introduction La théorie de l’information trouve ses origines dans les débuts des communications électriques. Le premier télégraphe élaboré par S. Morse entre 1832 et 1838 a permis de communiquer n’importe quel texte à l’aide de signaux électriques. Dans le code de Morse chaque lettre de l’alphabet est représentée par une séquence de : – points (courant électrique de courte durée); – traits (courant de longue durée); – espaces (absence de courant); On peut remarquer que dans la version définitive du code la lettre ”e”, la plus fréquente dans l’anglais, est représentée par la séquence la plus courte : un seul point. A cette époque, S. Morse n’avait pas fait d’analyse théorique pour arriver à cette conclusion, mais plutôt des observations empiriques. Son but en effet était de concevoir le code tel que la saisie d’un texte par un opérateur soit, en moyenne, la plus rapide possible. Aujourd’hui, la théorie moderne de communication a montré qu’il est possible de gagner à peine 15 % de temps de saisie par rapport au code de Morse. Quelques années plus tard, une première ligne télégraphique est installée entre Washington et Baltimore. En enterrant les câbles, S. Morse rencontre une nouvelle difficulté : le milieu dans lequel ces derniers se trouvent influe sur la qualité de transmission. En particulier, il remarque que si l’opérateur saisit trop vite son code, le signal reçu est indéchiffrable. Les points, les traits, les espaces sont confondus dans un seul signal d’intensité moyenne. Ainsi apparaît le problème de perturbations dues aux conditions physiques de transmission de l’information et, comme condition de bonne réussite, la nécessité de limiter le débit d’émission de symboles. Bien plus tard, dans les années 1940, l’ingénieur et mathématicien C. Shannon et le mathématicien Warren Weaver, ont formalisé le processus de communication et donné les outils mathématiques permettant de répondre aux questions posées empiriquement par les premiers télégraphes. Ils proposent en particulier, une représentation schématique du processus de communication, connue sous le nom de paradigme de Shannon. Figure 1. Paradigme de Shannon Ce modèle est une approximation linéaire de processus de communication qui met l’accent sur les aspects purement techniques de transmission d’un message. On peut résumer ce modèle de la façon suivante : 1. La source d’information choisit un message M parmi un certain nombre de messages possibles. 2. L’émetteur transforme le message en signal S compatible physiquement avec le mode de transmission choisi. On dit qu’il encode le message. 3. Le signal S est alors soumis à l’entrée d’un canal de transmission. 4. Lors de la transmission des perturbations peuvent intervenir et transformer le signal envoyé. On parle alors de bruit de canal B. 5. A la sortie du canal, le signal S ~ éventuellement entaché d’erreurs dues au bruit, est soumis au décodeur qui le transforme en message M ~ lisible par le destinataire. Théorie de l’information 0. Préambule 0. 4 Voici un exemple pour illustrer ce schéma. Imaginez qu’un ami vous envoie une carte postale du lieu de ses vacances. La carte voyage sans incident jusqu’à la ville où vous habitez. Le jour où le facteur doit enfin vous l’apporter, il la fait tomber par mégarde. Malheur ! Il pleut. L’enveloppe a pris l’eau. C’est ainsi que vous retrouvez les quelques lignes écrites par votre ami à moitié illisibles. Allez-vous pouvoir reconstituer le contenu complet du message ? Dans cet exemple, la source d’information est votre ami, et plus précisément, son cerveau. C’est encore lui qui joue ici le rôle de l’émetteur, en transformant ses idées en mots et ensuite en écrivant les mots à l’aide de lettres de l’alphabet. Le canal de transmission est ici représenté par les services postaux. Les dégâts causés par l’eau à la carte postale représentent le bruit de canal. Les questions que l’on pourrait poser dans cette situation sont les suivantes : 1. Y a-t-il un moyen de préparer le message de façon à éviter les désagréments causés par les erreurs de transmission et garantir à l’arrivée la lisibilité du message ? Par exemple, pourrait-on écrire avec une encre indélébile ? C’est le problème de codage de source. 2. Y a-t-il un moyen de transporter le signal dans le canal de manière à limiter les perturbations ? Par exemple, protéger le courrier dans des enveloppes imperméables ? C’est le problème de codage de canal. 3. Comment évaluer l’incertitude que le récepteur a sur le contenu réel du message reçu ? C’est le problème de mesure de l’information. Ce modèle, certes très simplifié, de la communication, a servi de base dans le développement de la théorie de l’information à partir des années 1940. Il s’inscrit dans une description plus générale, donnée par Warren Weaver, des 3 niveaux de problèmes de communication : Niveau 1 : Technique : Avec quelle précision peut-on transmettre les symboles de la communication ? Niveau 2 : Sémantique : Dans quelle mesure les symboles véhiculent-ils la signification ? Niveau 3 : Efficacité : Dans quelle mesure la signification reçue influence-t-elle le comportement et l’action du destinataire ? La théorie de l’information s’intéresse uniquement aux problèmes du 1er niveau de communication. En particulier, le sens des messages traités n’a aucune importance. L’information quantifiable associée à un message donné n’est pas dans son sens sémantique mais dans sa rareté. Un message, même très significatif, connu à l’avance par le récepteur ne lui apporte aucune information au sens technique du terme. Par contre, la réception d’un message très improbable mais démuni de tout sens est dans ce cadre considérée comme événement porteur d’une grande quantité d’information. Les chapitres qui suivent ont pour objectif d’introduire les concepts principaux de la théorie de l’information et les théorèmes fondamentaux. Ces derniers établissant les limites théoriques en matière de codage de l’information et de transmission. Ensuite, des applications seront consacrées à l’étude de quelques algorithmes de base de codage de source. __________ Théorie de l’information 1. uploads/S4/ th-info-poly.pdf