Remerciez-le!

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

Laurent BOUILLAUT Théorie de l’Information – Chapitre 2 – Sources Discrètes 1 1

Laurent BOUILLAUT Théorie de l’Information – Chapitre 2 – Sources Discrètes 1 1. Entropie d’une Source discrète 1.1 Exemple Introductif On considère les 26 lettres de l’alphabet + « Blanc » : 27 symboles équiprobables. L’entropie pour chaque lettre est de : H0= log 2 27 = 4.75 bits. On effectue un tirage (avec remise) : XFOML RHKHJFFJUJ ZLPWCFWCKCYJFFJEYVKCQSGHYD QPAAMKBZAACIBZLHJQD OCRO HLI RGWR NMIEL VIS EU LL NBNESEBYA TH EEI ALHENHTTPA OOBTTVA NAH BRL Si on tient compte des fréquences d’apparition de chaque symbole (à partir d’un apprentissage) : 27 1 2 1 log 4.029 i i i H p p bits = = − = ∑ Laurent BOUILLAUT Théorie de l’Information – Chapitre 2 – Sources Discrètes 2 1. Entropie d’une Source discrète 1.1 Exemple Introductif (suite) Si on tient maintenant compte de la dépendance entre les lettres successives (en anglais, on a souvent un ‘h’ après un ‘t’ et rarement un ‘w’ après un ‘z’…) Recherche de statistiques sur les couples de lettres à partir de l’ensemble d’apprentissage. On peut alors calculer l’entropie conditionnelle pour chaque couple de lettres : H (U2 / U1) = H (U1 ; U2) – H (U1) H2 = 3.318 bits 27 urnes contenant, chacune, les couples de lettres avec la même première lettre et dans des proportions correspondant aux valeurs estimées. On tire un couple, on note les deux lettre, on tire un autre couple dans l’urne correspondant à la dernière lettre écrite. On note la dernière lettre du couple… ON IE ANTSOUTINYS ARE T INCORE ST BE S DEALY ACHIN D ILONASIVE TUCOOWE AT TEASONARE FUSO TIZIN ANDY TOBE SEACE CTISBE En considérant maintenant les fréquences d’apparition de lettres par triplets : H3 = 3. 1 bits Il faut maintenant 272 urnes… IS NO IST LAT WHEY CRATICT FROURE BIRS GROCID PONDENOME OF DEMONSTRURES OF THE RETAGIN IS REGOACIONA OF CRE Laurent BOUILLAUT Théorie de l’Information – Chapitre 2 – Sources Discrètes 3 1. Entropie d’une Source discrète 1.1 Exemple Introductif (suite) Si on tenait compte de 8 lettres successives : H8 ~ 1.86 bits En moyenne, en anglais, l’information apportée par une lettre est de l’ordre de 1.86 bits L’entropie relative (H8 / H0) est de l’ordre de 40%. La redondance est de l’ordre de 60% 1.2 Généralisation Soit U une source discrète (un dispositif susceptible de fournir des symboles issu d’un alphabet. U1, U2, …,Un, … les VA correspondant aux valeurs émises par U aux instants 1, 2 …, n, … U est dite Stationnaire si : La loi de probabilité de U ne dépend pas de l’instant considéré. (ie. ∀k, les Uk suivent la même loi). Entropie d’une source : La difficulté tient à ce que les VA Ui ne sont pas forcément indépendantes et une définition correcte de l’Entropie par lettre de la source doit prendre en compte les liens probabilistes entre les Ui. Laurent BOUILLAUT Théorie de l’Information – Chapitre 2 – Sources Discrètes 4 - est une fonction décroissante de L. (1) - . (2) - HL(U ) est une fonction décroissante de L. (3) - . (4) 1. Entropie d’une Source discrète 1.2 Généralisation (suite) 9 Première approche : On définit d’abord l’Entropie par lettre source dans une séquence de L lettres par : 9 Seconde approche : On évalue l’entropie par lettre source par la mesure de l’incertitude de la Lième occurrence de la source connaissant les L-1 précédentes réalisation (avec L grand). Soit : ( ) ( ) 1 2 1 , ,..., L L H U H U U U L = Puis, l’entropie par lettre de la source par : ( ) lim L L H U →+∞ ( ) 1 2 1 lim / , ,..., L L L H U U U U − →+∞ Ces deux approches sont en fait équivalentes Ces deux approches sont en fait équivalentes Théorème : Soit U une source discrète stationnaire telle que H1(U)<+∞, alors : ( ) 1 2 1 / , ,..., L L H U U U U − ( ) ( ) 1 2 1 / , ,..., L L L H U H U U U U − ≥ ( ) ( ) 1 2 1 lim lim / , ,..., L L L L L H U H U U U U − →+∞ →+∞ = Laurent BOUILLAUT Théorie de l’Information – Chapitre 2 – Sources Discrètes 5 ( ) ( ) 1 2 1 lim lim / , ,..., L L L L L H U H U U U U − →+∞ →+∞ = 1. Entropie d’une Source discrète 1.2 Généralisation (suite) Entropie par lettre de la source U : H∞(U )= Remarque : Si U est une source sans mémoire (les Uk sont indépendants), alors : H∞(U )=H (U1 ) . Si U est une chaîne de Markov homogène d’ordre 1, alors : H∞(U )=H (U2 / U1 ) . Laurent BOUILLAUT Théorie de l’Information – Chapitre 2 – Sources Discrètes 6 2. Codage de source 2.0. Définitions L’objectif du codage de source est de supprimer les parties redondantes de l’information délivrée par la source. Deux types de codes peuvent être utilisés : Code à longueur fixe : Tous les mots ont la même longueur (même nombre de symboles). Code à longueur variable : La longueur des mots varie en fonction de leur fréquence d’apparition. Un mot sera d’autant plus long que sa probabilité d’apparition sera petite. Compaction des données (ou compression sans perte d’information) : Opération consistant à réduire (à l’aide d’un codage adéquat) le débit binaire d’une source tout en conservant l’information fournie par celle-ci. 2.1 Généralités sur les codes Soit B, un alphabet de référence (généralement binaire, B={0,1}). Des mots sont obtenus par concaténation des lettres de B. Un code C est un ensemble de mots. Ex : C={00,01,10,11} est un code de longueur fixe 2. Un code est uniquement déchiffrable si toute suite de mots code peut être interprétée (décodée) d’une seule manière Ex : D={0,11,010} est uniquement déchiffrable. E={0,1,101} ne l’est pas (101 peut être interprété comme ‘101’ ou ‘1’’0’’1’. Laurent BOUILLAUT Théorie de l’Information – Chapitre 2 – Sources Discrètes 7 2. Codage de source 2.1 Généralités sur les codes (suite) Théorème de Kraft Un code C peut être transformé (en permutant certaines lettres dans les mots) en un code préfixe équivalent (ie. un code fabriqué à partir du même alphabet de référence et possédant la même distribution de longueur de mots). avec b : nombre de lettres dans l’alphabet. c : mot code n(c) : longueur du mot c ⇔ ( ) 1 n c c C b − ∈ ≤ ∑ Un code préfixe est un code pour lequel aucun mot n’est le débit d’un autre mot (un code préfixe est donc toujours uniquement déchiffrable). Un moyen simple de construire un code préfixe est d’utiliser un arbre : chaque branche représente une lettre de l’alphabet. On choisit les mots codes tels que leur chemin ne contienne pas celui d’un autre mot code… {0,10,110,111} est un code préfixe. {0,11,110,111} ne l’est pas. Laurent BOUILLAUT Théorie de l’Information – Chapitre 2 – Sources Discrètes 8 Avec : M (nombre de mots code), pi (fréquence relative d’apparition du ième mot code) et n(i) (longueur du ième mot code). Théorème de Mac-Millan Un code C uniquement déchiffrable vérifie : (tout code uniquement déchiffrable admet donc un code préfixe équivalent) 2. Codage de source 2.1 Généralités sur les codes (suite) 2.2 Codage d’une VA discrète On s’intéresse tout d’abord au codage ‘plus simple’ d’une VA (avant de s’intéresser à celui d’une source U, concernant plusieurs VA U1, U2, …, Un, … ). On cherche à minimiser la longueur moyenne des mots code : ( ) log H X n b ≤ 1 ( ) M i i n p n i = = ∑ Proposition 1 Pour tout codage d’une VA X par un code uniquement déchiffrable (sur un alphabet à b lettres), la longueur moyenne des mots code vérifie : où la base du logarithme coïncide avec celle de la mesure de l’entropie de X. Proposition 2 Pour toute VA X, il existe un code préfixe tel que : ( ) log log n b H X b ≤ + ( ) 1 ≤ ∑ ∈ − C c c n b Laurent BOUILLAUT Théorie de l’Information – Chapitre 2 – Sources Discrètes 9 2. Codage de source 2.3 Codage d’une source : Codes à longueur variable Théorème du codage de source : Soient U une source stationnaire, HL(U) l’entropie par lettre source pour un mot de longueur L et b la taille de l’alphabet utilisé pour construire le code. Alors, il est possible de trouver un code préfixe pour encoder les mots de L lettres source avec un nombre moyen de lettres code par lettre source de telle sorte que : Où, la base du logarithme est celle utilisée pour l’entropie par lettre. Et donc : ( ) ( ) L b U H n b U H uploads/Philosophie/ chapitre2-sources-discretes.pdf