Remerciez-le!

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

Probabilités 2007–2008 TD n ˚10 Entropie de Shannon et codage Exercice 1 Entrop

Probabilités 2007–2008 TD n ˚10 Entropie de Shannon et codage Exercice 1 Entropie de Shannon et codage Soit A = {α1, ..., αD} un alphabet et M = {x1, ..., xk} un ensemble d’objets appelés messages. Un codage est une application de M dans A∗qui à un message xi associe son code ci de longueur li. Un codage est dit préﬁxe s’il ne contient pas deux mots dont l’un est préﬁxe de l’autre. ▷1. (Inégalité de Kraft) Montrer que si le codage h est préﬁxe alors k X i=1 D−li ⩽1 ▷2. Supposons l’inégalité précédente satisfaite. Montrer que pour tout alphabet A de D lettres et tout ensemble de k messages il existe un codage h préﬁxe et dont les codes sont de longueurs (li). ▷3. (Borne de Shannon sur la longueur moyenne d’un code préﬁxe) Supposons maintenant que les messages proviennent d’une source aléatoire, le message xi ayant la probabilité pi. La longueur moyenne de codage est alors déﬁnie par : L(h) = k X i=1 pili Soit Linf la plus petite de ces longueurs pour un code préﬁxe. Nous allons estimer Linf. Shannon déﬁnit l’entropie d’un événement comme la quantité de surprise −log pi qu’aurait un observateur lorsqu’il découvre la réalisation de cet événement. Plus cet événement est improbable plus l’observateur sera surpris. Si on fait la moyenne sur tous les événements possibles on obtiendra l’entropie du système : HD(p) = − k X i=1 pi logD pi C’est la quantité d’information relative à la distribution p = (p1, ..., pk). Montrer que H ⩽Linf ⩽H + 1 Solution ▷1. a a baa a bab b bac c a bb b b c c On peut représenter un codage préﬁxe sur un alphabet à D lettres par un arbre D- aire (pas nécessairement complet). L’ensemble de mots est l’ensemble des étiquettes d’un chemin de la racine à une feuille. À chaque feuille correspond donc un mot du code. Les profondeurs des feuilles sont les longueurs des codes. On montre par induction sur un tel arbre que l’inégalité de Kraft est vériﬁée : – le cas de base (une feuille) est trivial. – Considérons un arbre ﬁni où l’inégalité est vériﬁée pour les ﬁls de la racine : ∀j, kj X i=1 D−li,j ⩽1. Dans l’arbre de départ, les profondeurs sont augmentées de 1 : k X i,j D−li,j−1 ⩽1 D D X j=1 1 = 1. ▷2. Pour établir la réciproque, soit L := max i ℓi, et considérons un arbre D-aire complet de profondeur L. On prend les ℓi un par et pour chacun, – on choisit arbitrairement un nœud à profondeur ℓi et le mot étiquetant le chemin de la racine à ce nœud – on supprime tous les ﬁls de ce nœud, ce qui supprime une proportion D−ℓi des nœuds de l’arbre de départ. Par hypothèse, on supprime une proportion au plus P D−ℓi ⩽1 des nœuds de l’arbre de départ, c’est-à-dire qu’il reste toujours au moins un nœud tant que l’on n’a pas traité tous les ℓi. Correction par Martin Delacourt, relue par J.-B. Rouquier Probabilités 2007–2008 TD n ˚10 ▷3. On utilise l’inégalité de convexité (si P i pi = 1, et f convexe, alors P i pif(xi) ⩾f (P i pixi)) avec la fonction x 7→Dx qui est convexe. Les xi sont les −logD pi −li. On obtient alors DHD(p)−L(h) ⩽P i piD−logD pi−li = P i pi D−li pi ⩽1. Donc, en prenant le log des deux côtés, on obtient, HD(p) −L(h) ⩽0. Pour la deuxième partie de l’inégalité, on va poser : ∀i, l′ i = ⌈−logD pi⌉. On commence par vériﬁer que ce sont des candidats possibles pour les longueurs d’un code. En eﬀet, P i D−⌈−logD pi⌉⩽P i DlogD pi ⩽1. On a alors P i pil′ i −HD(p) = P i pi (⌈−logD pi⌉+ logD pi) ⩽1. Or Linf ⩽P i pil′ i, donc Linf ⩽HD(p) + 1 Exercice 2 L’algorithme de Shannon On ﬁxe D = 2 et on suppose p1 ⩾p2 ⩾... ⩾pk. On pose qs = Ps−1 i=1 pi. La méthode de Shannon consiste à écrire pour chaque i un développement dyadique de qi : qi = a1(i) 21 + a2(i) 22 + a3(i) 23 + · · · et à prendre pour code de xi : a1(i)...ali(i) avec li = ⌈−log2 pi⌉. En d’autres termes, xi est l’écriture en base 2 de qi, tronquée à li chiﬀres. ▷1. Donner le code obtenu pour p1 p2 p3 p4 p5 p6 0,27 0,23 0,2 0,15 0,1 0,05 . Calculer L et la comparer à l’entropie. ▷2. Montrer que ce code est préﬁxe. ▷3. Montrer que la longueur moyenne L vériﬁe H2(p) ⩽L ⩽H2(p) + 1. ▷4. Ce codage est-il optimal ? Solution Ce tableau est complété au fur et à mesure des questions : i pi li qi Shannon Fano mystère 1 0,27 2 0 00 00 10 2 0,23 3 0,27 010 01 00 3 0,2 3 0,5 100 100 01 4 0,15 3 0,7 101 101 110 5 0,1 4 0,85 1101 110 1110 6 0,05 5 0,95 11110 111 1111 L = 2,93 2,5 2,42 ▷1. L’entropie est 1,68. ▷2. Les écritures des codes sont croissantes, donc si xi est préﬁxe de xj pour j > i, alors il est aussi préﬁxe de xi+1. On va montrer que ce n’est pas le cas. On regarde donc la diﬀérence entre qi et qi+1 : ⌈−log(qi+1 −qi)⌉= ⌈−log pi⌉= li. Donc la diﬀérence d’écriture se fait sur le liebit. Comme les deux codes sont de longueurs au moins li, ils sont distincts. ▷3. Évident grâce à la déﬁnition des li. ▷4. On verra un meilleur codage avec l’exercice suivant. Exercice 3 L’algorithme de Fano Fixons D = 2 et supposons p1 ⩾p2 ⩾... ⩾pk. On regroupe les u premiers objets où u est le plus petit entier tel que p1 + ... + pu ⩾1 2 Nous obtenons ainsi une partition M de l’ensemble des objets en deux sous-ensemble M0 et M1. Soient π0 et π1 les probabilités respectives de ces ensembles. Nous appliquons à M0 l’algorithme de dichotomie pour obtenir une partition M0 = M00 + M01 où M00 = {x1, ..., xv} et v est le plus petit entier tel que p1 + ...pv ⩽π0/2. On applique à M1 ce même algorithme et on obtient la partition M1 = M10 + M11. On continue l’algorithme ainsi de suite jusqu’à ce qu’on ne puisse plus appliquer la dichotomie, ce qui se produit quand un ensemble Ma ne comporte plus qu’un élément et a est alors le code de cet élément. ▷1. Reprendre les questions 2.1, 2.2 et 2.4. Correction par Martin Delacourt, relue par J.-B. Rouquier Probabilités 2007–2008 TD n ˚10 Solution ▷1. L = 2,5 ▷2. Le code est préﬁxe par construction, en eﬀet, les codes sont les feuilles d’un arbre binaire, donc aucun code ne peut être préﬁxe d’un autre. ▷4. On verra un meilleur codage avec l’exercice suivant. Exercice 4 L’algorithme mystère ▷1. Donner un algorithme pour obtenir un codage préﬁxe optimal. Le faire tourner sur l’exemple de la question 2.1 et comparer la longueur moyenne L obtenue avec l’entropie de la distribution. Solution ▷1. On utilise l’algorithme de Huﬀman : – A chaque étape, on prend les deux lettres les moins fréquentes, et on les place comme sœurs dans l’arbre associé au codage. – On réunit ces deux lettres en une seule de probabilité la somme des deux, qui sera le père des deux. – On ajoute cette nouvelle lettre aux autres, et on recommence. Ce codage est optimal. En eﬀet, le nombre d’arbre binaires à k éléments est ﬁni, il existe donc un arbre optimal. Considérons la lettre la moins fréquente, on peut l’échanger avec une feuille de profondeur maximale et diminuant (au sens large) la longueur moyenne de codage. Donc il existe un codage optimal où la lettre la moins fréquente est à la profondeur maximale. Par un raisonnement analogue, on montre qu’il existe un codage optimal ou la deuxième lettre moins fréquente est sœur de la précédente. On peut alors fusionner ces deux lettre en une nouvelle, de fréquence somme des fréquences des deux lettres, et poursuoivre l’algorithme. Correction par Martin Delacourt, relue par J.-B. Rouquier uploads/S4/ td10-reponses.pdf