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 et du Codage Objectifs du Cours Etude de la mesure de

Théorie de l’information et du Codage Objectifs du Cours Etude de la mesure de l’Information selon les théories de Claude Shannon et ses applications dans deux domaines : - Détection et correction d’erreurs - Compression de données Sommaire • Introduction, historique et principe de la THI (1) • Principes des systèmes de communications (1) • Mesures de la quantité d’information et Entropie (3) • Codage de la source (discrète sans mémoire ) (5) – Codes et Codage (codage optimale,prefixe , Huffman, 1ier Théorème de Shanon) – Redondance et compression (Lampel Ziv, Shannon,…) • Codage du canal (Discret symétrique ) (5) – Codage du canal – Capacité d’un canal (2ième Théorème de Shanon) – Correction et codes correcteurs (Représentation, Hamming, Linéaire, Polynomiaux,…) Ce dont on va parler dans ce cours . . . • Notions mathématiques : entropie, information mutuelle • Codage et décodage : codes, déchiffrabilité, efficacité d'un code • Transmission de l'information: comment transmettre correctement une information en présence d'erreurs de transmission • Compressiondes données : essentiellement, compression sans pertes (conservative) • Le langage mathématique est celui de la théorie des probabilités : variables aléatoires et processus discrets (élémentaires) Chapitre 1: Introduction, historique et principes de la THI Introduction • La théorie de l’information donne des bases formelles et quantitatives à la notion d’information, de façon à ce que celle-ci devienne techniquement utilisable dans un certain nombre de disciplines qui traitent de l’information. • La théorie de l’information fournit essentiellement des outils de modélisation et d’analyse dans le domaine du traitement de l’information. • C’est une théorie probabiliste permettant de quantifier le contenu moyen en information d'un ensemble de messages, dont le codage informatique satisfait une distribution statistique précise. • Elle fournit une mesure quantitative de la notion d'information apportée par un message (ou une observation). • Dans un sens plus général, une théorie de l'information est une théorie visant à quantifier et qualifier la notion de contenu en information présent dans un ensemble de donnée. Parmi les objectifs importantes de la THI, on peut citer : • le codage de l'information, • la mesure quantitative de redondance d'un texte, • Evaluation et minimisation des coûts de – Transmission – Stockage (Compression) • Contrôle des erreurs de transmission – Détection – Correction • Cryptologie – Cryptographie – Cryptanalyse Objectifs • Informatique – Compression, codage, cryptologie – Reconnaissance des formes (I.A.) • Physique – Modèles quantiques – Théorie des trous noirs et du « big bang » • Biologie moléculaire – A.D.N. • Sociologie – Communication Applications • Compression - Code MORSE, - Huffman, - Lampel-Ziv, -RLE.... • Contrôle des erreurs de transmission - Codes de parité, - Codes à répétition,- Hamming, -Reed Solomon.... • Cryptologie - Crypte de CÆSAR, - DES, - AES,- RSA..... Applications Relations… Historique • Cette théorie fut conçue par Claude E. Shannon peu après la seconde guerre mondiale pour répondre à certaines interrogations fondamentales dans le domaine des techniques de communication. • Comme le suggère l’intitulé de l’article fondateur de Shannon (The mathematical theory of communication, 1948), cette théorie peut être vue comme une discipline mathématique. • L'information est un concept physique nouveau qui a surgi dans un champ technologique. • Le concept théorique d'information a été introduit à partir de recherches théoriques sur les systèmes de télécommunication. • L'origine de ces recherches remonte aux études entreprises dès la fin du 19e siècle, en physique et en mathématique par Boltzmann, et Markov sur la notion de probabilité d'un événement et les possibilités de mesure de cette probabilité. Historique • Plus récemment, après la Seconde Guerre mondiale, les contributions les plus importantes sont dues à la collaboration des mathématiciens (Von Numan, Turing,…) et des ingénieurs des télécommunications (Shanon,…), qui ont été amenés à envisager les propriétés théoriques de tout système de signaux utilisé par les êtres, vivants ou techniques, à des fins de communication. Historique • Rudolf Clausius (1822-1888) : définit l'entropie comme une mesure du désordre d'un système • Ludwig Boltzmann (1844-1906) : l'entropie d'un état macroscopique est proportionnelle au logarithme du nombre d'états microscopiquescorrespondants • Ronald Fisher (1890-1962) : utilise le mot information dans un contextemathématique • Harry Nyquist (1889-1976) (bruit, fréquence d'échantillonnage), Ralph Hartley (1888-1970) • Claude Shannon (1916-2001), premiers théorèmes sur l'information en théorie de la communication Historique • Les trois principales questions auxquelles elle apporte une réponse sont les suivantes : 1. Quelle est la limite ultime en matière de compression des données digitales réversible (Codage d’une source de transmission); 2. Quel est le débit maximal de transmission fiable de ce type d’information sur un canal bruité (la capacité C d’un canal de transmission); 3. Sous quelles conditions un code de chiffrement est-il sûr (Cryptologie) Historique • Cette théorie est née de préoccupations technologiquespratiques. • La société Bell cherche à transmettre les messages de la façon à la fois la plus économique et la plus fiable. • Le cadre originel de la théorie est celui d'un système de communications où un émetteur transmet un message à un récepteur à travers un canal donné. • Émetteur et récepteur ont par hypothèse un répertoire commun, un code qui contient les catégories de signaux utilisables. • Ainsi le message codé est transmis, de l'émetteur au récepteur à travers le canal, sous forme de signes ou signaux portés par de le Canal. • Ainsi, le concept d'information a été l'objet d'une théorie, appelée "théorie de l'information". • Elle a été élaborée plus spécialement par Claude Shannon, ingénieur à la Compagnie des Téléphones Bell et reste jusqu'à nos jours la base du concept dit scientifique d'information. • Dans sa conception originale, la théorie de l'information s'est limitée à analyser les moyens et les techniques de télécommunication pour transmettre l'information le plus rapidement possible et avec le maximum de sécurité. • Elle s'est donc efforcée de développer des méthodes susceptibles de minimiser la probabilité d'erreur dans la reconnaissance du message. • Une notion fondamentale sera nécessaire pour développer ces méthodes : la mesure de l'information, au sens mathématique du terme. Notion d’information • Considérons le problème de la communication entre une source et un récepteur : la source émet un message que le récepteur lit. • On voudrait quantifier l'« information » que contient chaque message émis. Par exemple, il est clair que si l'émetteur dit toujours la même chose, la quantité d'information apportée par une répétition supplémentaire est nulle. Source Récepteur Canal de transmission Données Emises Données Reçus Notion d’information Le cas le plus simple est le suivant : le récepteur attend une information de type oui/non, le oui et le non étant a priori aussi vraisemblables l'un que l'autre. Lorsque la source transmet soit un oui soit un non, on considère que le récepteur reçoit une unité d'information (un bit). Autrement dit : une unité d'information, c'est quand on a a priori un ensemble de deux possibilités, et que l'une d'elles se réalise. Notion d’information :Exemple Une information désigne, parmi un ensemble d'événements, un ou plusieurs événements possibles. En théorie, l'information diminue l'incertitude. En théorie de la décision, on considère même qu'il ne faut appeler information que ce qui est susceptible d'avoir un effet sur nos décisions. En pratique, l'excès d'information, tel qu'il se présente dans les systèmes de messagerie électronique, peut aboutir à une saturation, et empêcher la prise de décision. Notion d’information :Exemple Premier exemple Soit une source pouvant produire des tensions entières de 1 à 10 volts et un récepteur qui va mesurer cette tension. Avant l'envoi du courant électrique par la source, le récepteur n'a aucune idée de la tension qui sera délivrée par la source. En revanche, une fois le courant émis et réceptionné, l'incertitude sur le courant émis diminue. La théorie de l'information considère que le récepteur possède une incertitude de 10 états Notion d’information :Exemple Second exemple • Problème: • Une bibliothèque possède un grand nombre: § d'ouvrages, § des revues, § des livres § et des dictionnaires. • Nous cherchons un cours complet sur la théorie de l'information. • Tout d'abord, il est logique que nous ne trouverons pas ce dossier dans des ouvrages d'arts ou de littérature; nous venons donc d'obtenir une information qui diminuera notre temps de recherche. • Il est précisé que nous voulions aussi un cours complet, nous ne le trouverons donc ni dans une revue, ni dans un dictionnaire. • nous avons obtenu une information supplémentaire (nous cherchons un livre), qui réduira encore le temps de notre recherche. Notion d’information :Exemple Notion de quantité d’information Problème Considérons N boîtes numérotéesde 1 à N. • Un individu « A » a caché au hasard un objet dans une de ces boîtes. • Un individu « B » doit trouver le numéro de la boîte où est caché l'objet. • Pour cela, « B » a le droit de poser des questions à l'individu « A » • « A » doit répondre sans mentir par OUI ou NON. • Mais chaque question posée représente un coût à payer par l'individu « B » (par exemple un euro). • Un individu « C » uploads/S4/ theorie-de-l-x27-information-et-du-codage.pdf