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 & Codage Introduction et Généralités sur la théorie de

Théorie de l’information & Codage Introduction et Généralités sur la théorie de l’information 1: Introduction La première tentative de définition de la “ quantité d’information “ remonte à 1928: l’Américain Hartley suggéra que " l’information" apparaît au cours de la sélection successive de symboles ou de mots d’un vocabulaire d’un alphabet de D symboles distincts, il est possible d’extraire DN mots différents, chaque mot contenant N symboles. La théorie de l’information ou, de façon plus précise, la théorie statistique de la communication, est l’aboutissement des travaux d’un grand nombre de chercheurs (H. Nyquist, R.Hartley, D.Gabor, …) sur l’utilisation optimale des moyens de transmission de l’information 1: Introduction En fait , c’est en 1948 que la théorie de l’information a réellement vu le jour. Il introduisit , à travers ces deux articles, le nouveau concept de quantité d’information de façon mathématique et en déduisit les principales conséquences. Ingénieur aux « Bell Telephone Laboratories » Publia deux articles désormais classiques intitulés A ce moment là les communications qui étaient de type analogique posaient énormément de problèmes à cause du bruit et des affaiblissements subies par le signal En effet, lorsque un signal était transmis, sa qualité (S/B) se dégradait au fur et à mesure que la distance parcourue augmentait la seule solution possible était d’amplifier le signal cette opération d’amplification n’était plus efficace quand le signal était noyé dans le bruit OBJECTIFS DE LA THEORIE DE L’INFORMATION Pour mettre en pratique cette idée il fallait transformer le signal de départ sous forme d’une combinaison de signaux élémentaires les plus basiques possibles (forme Booléenne). A partir de ce constat il fallait chercher un autre type de transmission qui permettrait de régénérer le signal durant sa transmission d’où la notion de bit (binary unit ) introduite par C.Shannon OBJECTIFS DE LA THEORIE DE L’INFORMATION Une fois réalisée cette opération, permettait de régénérer le signal en comparant l’échantillon prélevé du signal à un seuil pour pouvoir remettre en forme le signal reçu OBJECTIFS DE LA THEORIE DE L’INFORMATION Une fois le type de transmission défini , il fallait étudier tous les moyens qui permettraient de : 1. Stocker l’information de façon efficace 2. Transmettre l’information de façon efficace 3. Protéger l’information de façon efficace On est alors conduit à étudier : d’une part l’information proprement dite générée par la source, d’autre part les propriétés des canaux (capacité, etc.) et enfin les relations qui existent entre l’information à transmettre et le canal employé en vue d’une utilisation optimale de celui-ci. Pour répondre à toute ces question Shannon a du bouleverser la manière de penser les télécommunications en proposant un schéma, qui est devenu le schéma de base de toute communication OBJECTIFS DE LA THEORIE DE L’INFORMATION A la question « combien de bits du signal numérisé étaient réellement utiles à la compréhension du message par le récepteur ?» , la réponse était d’autant plus délicate que les canaux de transmission étant bruités (probabilité d’erreur Pe), une partie de cette information serait altérée avant d’atteindre son récepteur … de mettre en œuvre les systèmes de codage / décodage adéquats. On évalue ainsi numériquement : 1. la quantité d’information émise par une source discrète 2. la capacité de transmission d’information d’un canal bruité, c'est-à-dire la quantité d’information maximale (par élément ou pas seconde) qui peut être transmise de manière fiable dans le canal. OBJECTIFS DE LA THEORIE DE L’INFORMATION A titre d’exemples: -une source qui émet le même symbole 1000 fois / seconde n’apporte aucune information. - un canal qui véhicule 1000 symboles par seconde n’achemine pas la même quantité d’information si sa probabilité d’erreur Pe = 10-1 ou Pe =10-6 Ainsi, l’objectif (initial) de la T.I. est de : caractériser de manière probabiliste la source, le canal, et le destinataire afin d’évaluer les limites théoriques de transmission en fonction des divers paramètres, A la question quelle est la quantité d’information que contenait un message la réponse de Shannon était : c’est le nombre « 1 » et de « 0 » nécessaire pour le transmettre Information ??? Question1: l’objet est-il dans la partie droite ou gauche Réponse: droite Information ??? Question2: inférieure ou supérieure Réponse: inférieure Question3: droite ou gauche Réponse: gauche Question4: haut ou bas Réponse: haut Voici un exemple typique pour confirmer cette affirmation: Si on a casier de 16 cases , un objet est caché dans une case. Combien de questions faut-il poser pour arriver à la case contenant l’objet Remarque : à travers la réponse de Shannon, on peut remarquer que l’information n’a pas le même sens que celui qu’on connaissait . Voici quelques extraits de l’article de Shannon sur la question: Donc pour Shannon, quand on veut transmettre de l’information on ne doit pas trop s’intéresser à l’aspect sémantique (sens des messages), mais plutôt à ses aspects physiques observables Pour cela Shannon va imaginer l’information sous un sens purement mathématique L’un des aspect mathématique les plus important dans l’information va être l’aspect statistique Information ??? quantité d’information Modelisation de la source : On se place ainsi dans le cadre d’une expérience aléatoire délivrant un évènement (ou résultat) s parmi un ensemble fini de N évènements élémentaires (résultats) possibles . La quantité d’information d’un message :  est directement liée à sa probabilité  mesure le degré d'imprévisibilité (pour le destinataire) du message émis par la source Exemple: •La source S1 transmet 99 fois le même message (prévisible) •La source S2 transmet 99 messages tous  (imprévisible) EXEMPLE DE SOURCE D’INFORMATION Image à transmettre : 12 lignes et 12 colonnes ( 144 pixels) Un pixel peut prendre l’une des trois couleurs , noir(N) , gris(G) ou blanc(B) Points Noirs N : 18 Points Gris G : 15 Points Blancs B :111 pN=18/144=0.125 pG=15/144=0.104 pB= 111/144=0.771 Donc on a une source d’information qui peut être modélisée par la variable aléatoire S qui peut prendre les valeurs N, G ou B avec les probabilités respectives : pN=0.125 pG=0.104 et pB=0.771 La source dans ce cas prend ses valeurs dans l’ensemble , S={N, G, B} Quantité d’information associée à un événement (message) : définir une quantité d'information notée h(x) comme étant le degré d'imprévisibilité (pour le destinataire) du message émis par la source. La quantité d'information h(x) apportée par la réalisation d'un événement x de probabilité Pr(x) est donc mesurée par une fonction croissante de 1/Pr(x) La fonction f doit satisfaire aux trois propriétés suivantes: 2) f(1) = 0 : événement certain  information nulle. 3) Soient x,y : deux événements indépendants: ENTROPIE D’UNE SOURCE D’INFORMATION Entropie d’une source sans mémoire Différents choix possibles pour les unités : •base b=e => natural unit (nit), : •b=10 => décimal unit (dit) ou Hartley Choix le plus fréquent : •base b = 2 => log binaire : unité Sh (Shannon) ou bien bit EXEMPLE: Image à trois niveaux de gris pN=18/144=0.125 pG=15/144=0.104 pB= 111/144=0.771 Calcul de l’entropie de S : H(S)=- (pN.log(pN )+pG.log(pG )+ pB.log(pB)) =-(0.125log0.125 + 0.104log0.104 + 0.771log0.771) =1bit / msge ENTROPIE D’UNE SOURCE D’INFORMATION Remarque2: L’entropie de l’exemple précédent a été calculée en supposant que les différents éléments de la source étaient indépendants Ce qui n’est pas toujours vraie . Remarque1: L’entropie de l’exemple peut être interprétée comme le nombre minimale moyen de bits nécessaire pour représenter les messages de la source Remarque3: Donc si on arrive à modéliser la source, d’une manière qui permet de prendre en considération cet aspect de dépendance , cette limite inférieure trouvée(H(S) ) pourrait être encore plus petite. SOURCES D’INFORMATION 3.Source de Markov: C’est une source pour laquelle la probabilité de générer un symbole ne dépend que du symbole à l’instant n-1 1.Source sans mémoire Si la production des différents symboles est indépendante des symboles précédemment émis, on parle alors de source discrète sans mémoire. 2.Source à mémoire :La source a une mémoire lorsque la probabilité d'apparition des différents symboles, est conditionné par le ou les symboles précédents. 6.Extension d'une source. on peut supposer que les symboles sont émis par échantillon de taille k. Ceci nous emmène à parler de la kieme extension de la source S, on la note Sk Exemple: La source binaire S{0,1} a pour symboles 0 et 1 avec Pr(0)=p et Pr(1)=1-p=q La deuxième extension de S est S2={a1=00,a2=01,a3=10,a4=11} 5.Source stationnaire Une source stationnaire est une source qui est le siège d'événements répétitifs (pas nécessairement périodiques) obéissant à une loi de probabilité connue et invariante dans le temps. Exemple: statistique sur les chapitres des livres 4.Source ergodique La source est dite ergodique si les différents messages produits par la source ont les mêmes propriétés statistiques Exemple de la statistique sur des textes français: Pr(E) = 0.148 , Pr(S)=0.077, Pr(N)= 0.071, Pr(T)=0.068, Pr(Espace)=0.184, Pr(ON)  4 fois Pr(NO), Q est presque toujours suivi de U, P l'est souvent de H, X ne l'est jamais de Z etc… SOURCES D’INFORMATION RELATIONS ENTRE ENTROPIES Entropie conjointe: H(X,Y) c'est l'entropie relative au couple de variables aléatoires (X,Y). X={x1 ,x2 ,...,xi ,...,xN} et Y={y1 ,y2 ,...,yi ,...,yM} Entropie conditionnelle: H(X/Y) C’est l'entropie de X quand Y est réalisé Soient X uploads/Philosophie/ th-info-introduction.pdf