Remerciez-le!

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

SOURCES DISCRETES Marc URO TABLE DES MATIERES ENTROPIE D'UNE SOURCE DISCRETE...

SOURCES DISCRETES Marc URO TABLE DES MATIERES ENTROPIE D'UNE SOURCE DISCRETE................................................................ ...3 CODAGE DE SOURCE ................................................................ ............................... 8 GENERALITES SUR LES CODES ................................................................ ....9 CODAGE D'UNE VARIABLE ALEATOIRE DISCRETE................................14 CODAGE D'UNE SOURCE ................................................................ .............. 16 CODES A LONGUEUR VARIABLE....................................................... 16 CODES BLOC................................................................ .......................... 35 3 SOURCES DISCRÈTES ENTROPIE D'UNE SOURCE DISCRÈTE Exemple On considère les 26 lettres de l'alphabet auxquelles on ajoute le caractère blanc (ou espace) pour séparer les mots. Si on considère les 27 symboles équiprobables et indépendants, on obtient une entropie par lettre de H0 = log2 27 = 4,75 bits. Disposant dans une urne 27 papiers sur chacun desquels est inscrit un des 27 symboles et procédant à des tirages avec remise, on obtiendrait une séquence du type: XFOML RHKHJFFJUJ ZLPWCFWCKCYJFFJEYVKCQSGHYD QPAAMKBZAACIBZLHJQD Dans une telle séquence, seules les lettres nous sont familières (par leur agencement). Un modèle plus fin consiste à estimer les probabilités d'apparition des lettres en effectuant des statistiques à partir des textes écrits. Shannon a réalisé ces statistiques sur des textes anglais et il a obtenu: Lettre Fréquence relative Lettre Fréquence relative Lettre Fréquence relative - 0,182 H 0,043 P 0,016 E 0,107 D 0,031 W 0,013 T 0,086 F 0,028 B 0,012 A 0,067 L 0,024 V 0,007 O 0,065 C 0,023 K 0,003 N 0,058 M 0,021 X 0,001 R 0,056 U 0,020 J 0,001 I 0,052 G 0,016 Q 0,001 S 0,050 Y 0,016 Z 0,001 4 ____________________________________________________________ sources discrètes Le calcul de l'entropie par lettre effectué à partir de ces fréquences relatives d'apparition des lettres (assimilées à des probabilités) conduit à H1 = − pi log2 pi = 4,029 bits i=1 27 ∑ . En effectuant de nouveaux tirages avec remise dans une urne contenant les lettres dans les proportions correspondant aux fréquences relatives du tableau précédent, on obtiendrait une séquence de la forme: OCRO HLI RGWR NMIEL VIS EU LL NBNESEBYA TH EEI ALHENHTTPA OOBTTVA NAH BRL Cette 'phrase' ressemble un peu plus que la précédente à un texte anglais en ce sens que la longueur d'un mot y est voisine de la normale et que la répartition du nombre de voyelles et de consonnes est vraisemblable. Toutefois cette séquence reste relativement éloignée d'un texte anglais. Ceci tient au fait que les lettres successives d'un texte ne sont nullement indépendantes les unes des autres (en anglais la lettre 't' est souvent suivie d'un 'h' tandis qu'elle est rarement suivie d'un 'z' ou d'un 'w'). Pour tenir compte des dépendances entre une lettre et la lettre suivante, il faut effectuer des statistiques sur les couples de lettres qui apparaissent dans un texte sensé. On peut alors assigner à chaque couple de lettres une probabilité d'apparition. Ces nombres permettent le calcul de l'entropie conditionnelle H U2 / U1 ( ) où U1,U2 ( ) représente le couple formé par une lettre et la lettre suivante à l'aide de la relation H U2 / U1 ( )= H U1,U2 ( )−H U1 ( ). La valeur numérique obtenue est H2 = 3,318 bits. Pour simuler l'expérience en prenant en considération la dépendance d'une lettre avec la suivante, on procède comme suit: 27 urnes contiennent chacune les couples de lettres avec la même première lettre et dans des proportions correspondant aux valeurs estimées. On extrait une série de couples de lettres de ces urnes en notant à chaque fois la seconde lettre. À chaque extraction on tire un couple dans l'urne dont la lettre correspond à la seconde lettre du tirage précédent. Pour le premier tirage, on peut déterminer l'urne à partir d'un tirage au sort dans l'urne de l'expérience précédente (qui donne la première lettre). Le résultat est alors de la forme: ON IE ANTSOUTINYS ARE T INCORE ST BE S DEAMY ACHIN D ILONASIVE TUCOOWE AT TEASONARE FUSO TIZIN ANDY TOBE SEACE CTISBE sources discrètes ___________________________________________________________ 5 On note cette fois que non seulement les proportions entre voyelles et consonnes sont convenables, mais qu'en plus les alternances entre voyelles et consonnes se rapprochent de celles rencontrées dans la réalité, ce qui permet de pouvoir 'prononcer' les mots. En considérant les relations probabilistes liant les triplets de lettres, on obtiendrait une entropie conditionnelle H3 = H U3 /U1,U2 ( )= 3,1 bits. Il faudrait maintenant disposer de 27 2 urnes contenant chacune les combinaisons de trois lettres avec les deux premières fixées. En procédant de façon analogue à l'expérience précédente, on obtiendrait: IS NO IST LAT WHEY CRATICT FROURE BIRS GROCID PONDENOME OF DEMONSTRURES OF THE REPTAGIN IS REGOACTIONA OF CRE Des mots complets anglais commencent à apparaître. Notons que la prise en compte de huit lettres consécutives conduit, pour la langue anglaise, à une entropie conditionnelle H8 ≈1,86 bit . Cela signifie qu'en moyenne, dans un texte anglais, l'information apportée par une lettre est de l'ordre de 1,86 bit. Ce nombre est à comparer avec H0 = 4,75 bits. On dit que l'entropie relative est de 1,86 4,75 ≈40%. Concrètement cela se traduit par le fait que, dans le choix des lettres pour écrire un message en anglais sensé, on est 40% aussi libre qu'on le serait si on se contentait de choisir de façon équiprobable et indépendante les lettres les unes après les autres. On dit aussi que la redondance est égale à 1- entropie relative = 60%. En d'autres termes 40% des lettres sont choisies librement, les 60% restant étant imposés par les règles de structure du langage. Revenant à notre exemple, on peut interpréter les nombres H0 = 4,75 bits et H8 =1,86 bit de la façon suivante: la prise en compte des redondances du langage conduit à n'utiliser en moyenne que 1,86 bit pour coder une lettre alors que l'approche plus grossière considérant les lettres équiprobables et indépendantes exige 4,75 bits.. Plus généralement soit U une source discrète, c'est-à-dire un dispositif susceptible de fournir des symboles (ou lettres) issus d'un alphabet. On notera U1,U2,...,Un,... les variables aléatoires correspondant aux valeurs émises par la source U aux instants 1,2,...,n,.... La source est dite stationnaire si sa loi de probabilité ne dépend pas de l'instant considéré ie. ∀k les Uk ont même loi ( ). 6 ____________________________________________________________ sources discrètes Comme on l'a fait pour une variable aléatoire pour laquelle on a défini la notion d'entropie, on souhaiterait caractériser une source par son entropie. La difficulté tient ici à ce que les variables U1,U2,...,Un,... ne sont pas forcément indépendantes et qu'une définition correcte de l'entropie par lettre de la source doit prendre en compte les liens probabilistes unissant U1,U2,...,Un,... . Deux approches sont alors envisageables: - Première approche On définit tout d'abord l'entropie par lettre source dans une séquence (ou un mot) de L lettres par HL U ( ) = 1 L H U1,U2,...,UL ( ), puis l'entropie par lettre de la source par lim L→+∞H L U ( ) . - Deuxième approche On peut aussi se proposer d'évaluer l'entropie par lettre source par la mesure de l'incertitude de la Lième occurence de la source connaissant les L-1 précédentes réalisations lorsque L est grand. Cela revient alors à prendre en compte la quantité: lim L→+∞H U L / U1,U2,...,UL −1 ( ) . En fait on va montrer que les quantités lim L→+∞H L U ( ) et lim L→+∞H U L / U1,U2,...,UL −1 ( ) sont égales. Théorème Soit U une source discrète stationnaire telle que H1 U ( ) < +∞, alors: - H UL /U1,U2,...,U L−1 ( ) est une fonction décroissante de L (1) - HL U ( ) ≥H UL /U1,U2,...,U L−1 ( ) (2) - HL U ( ) est une fonction décroissante de L (3) . - lim L→+∞H L U ( ) = lim L→+∞H U L /U1,U2,...,UL−1 ( ) (4) - En conséquence, on définira l'entropie par lettre de la source U par: H∞U ( ) = lim L→+∞HL U ( ) = lim L→+∞H U L / U1,U2,...,UL −1 ( ) sources discrètes ___________________________________________________________ 7 On a vu que le conditionnement diminue l'entropie ie H X / Y ( )≤H X ( ) ( ), donc: H UL /U1,U2,...,U L−1 ( )≤H UL /U2,...,UL −1 ( ) et par stationnarité: H UL /U2,...,UL −1 ( )= H UL −1 /U1,U2,...,U L−2 ( ), H UL /U1,U2,...,U L−1 ( )≤H UL −1 /U1,...,UL−2 ( ), ce qui montre le (1). Montrons maintenant le (2). De H X,Y ( )= H X ( ) + H Y / X ( ), on déduit: H X,Y, Z ( )= H X,Y ( ) + H Z / X,Y ( ) et plus généralement: H U1,U2,...,UL ( )= H U1 ( )+ H U2 / U1 ( )+ H U3 /U1,U2 ( )+...+H UL / U1,U2,...,UL −1 ( ) soit: HL U ( ) = 1 L H U1,U2,...,UL ( )= 1 L H U1 ( )+ H U2 /U1 ( )+ H U3 /U1,U2 ( )+...+H UL / U1,U2,...,UL −1 ( ) ( ) mais: H UL /U1,U2,...,UL ( ) ≤H UL −1 /U1,U2,...,U L−2 ( )≤...≤H U2 / uploads/S4/ chapter-2.pdf