• Document: TD 3 Codage Huffman
  • Size: 143.13 KB
  • Uploaded: 2019-02-13 15:30:13
  • Status: Successfully converted


Some snippets from your converted document:

Cours/TD 3 Codage Huffman 1.1 Codage Huffman Definition. Soit une source discrete et sans mémoire produisant N symboles d’un alphabet a0 , a1 , ·, aN −1 selon la distribution de probabilité p = (p0 , p1 , . . . , pN −1 ) . Un code binaire préfixe C est optimal ⇐⇒ La longueur moyenne l = p0 l0 + p1 l1 + · · · + pN −1 lN −1 de ses mots est minimale dans l’ensemble de tous les codes binaires préfixes associés à la source et à la distribution de probabilité considérées. Algorithme de Huffman Initialisation Liste des noeuds candidats : chaque symbole à coder est un nœud pondéré dont le poids est sa probabilité. Tant que nous avons au moins deux nœuds dans la liste des noeuds candidats – On identifie deux nœuds de poids le plus faible de la liste actuelle noeuds candidats. Nous les remplaçons dans la liste par un père dont le poids sera la somme des poids de ses successeurs. L’algorithme de Huffman construit récursivement un arbre binaire pondéré avec la somme des poids égale à 1, appelé arbre avec des probabilités. À chaque étape, on trouve un nœud antécédent (un père) à deux nœuds (les fils) pris d’une liste de candidats. À chaque étape la somme des poids restera égale à 1. L’algorithme de Huffman produit un code binaire préfixe optimal Exemple. Considérons une source discrète sans mémoire qui a produit ”aabbbcddef” sur l’alphabet {a, b, c, d, e, f }. 2 Après une analysé des fréquences nous avons p = ( p0 , p1 , · · · , p7 ) avec pa = pd = 10 , 3 1 pb = 10 , pc = pe = pf = 10 . On a donc : 1 b 3/10 a 2/10 d 2/10 Initialisation c 1/10 e 1/10 f 1/10 Étape 2 On choisit ’e’ et ’f’ parmi les symboles de plus faible poids. La liste misé à jour est : b 3/10 a 2/10 d 2/10 c 1/10 (ef ) 2/10 Étape 3 On prend ’c’ et on choisit ’(e,f)’ parmi les symboles de plus faible poids. La liste misé à jour est : b 3/10 a 2/10 d 2/10 ((ef )c) 3/10 Étape 4 On prend ’a’ et ’d’ en tant que symboles de plus faible poids. La liste misé à jour est : b 3/10 (ad) 4/10 ((ef )c) 3/10 Étape 5 On prend ’b’ and ’(c (e f))’ en tant que symboles de plus faible poids. La liste misé à jour est : (b((ef )c)) 6/10 (ad) 4/10 Étape 6 ((b ((e f) c)) (a d)) L’arbre binaire construit est dans la figure 1.1. Notre codage : 0 0 b 3/10 00 0 0 a 2/10 10 0 0 d 2/10 11 0 0 c 1/10 011 0 0 e 1/10 0100 0 0 f 1/10 0101 Exemple. Considérons une source discrète sans mémoire qui produit des symboles avec la loi de probabilité p = ( p0 , p1 , · · · , p6 ) = {0.4, 0.2, 0.15, 0.1, 0.05, 0.05, 0.05} sur l’alphabet {a, b, c, d, e, f, g}. 2 Racine 0 1 0 1 0 1 b a d 0 1 c 0 1 e f Fig. 1.1 – Arbre binaire 1. Calculez H(p). 2. Trouvez le code de Huffman associé 3. Calculez l, la longueur moyenne des mots code, et comparer-la à H(p). Le codage idéal donné par l’entropie sera H(p) = p0 I0 + p1 I1 + . . . + p6 I6 = −p0 log2 p0 − p1 log2 p1 − . . . − p6 log2 p6 = 2.38. (Rappel : log2 p = ln p ln 2 ) Pour un codage sans statistiques supposant le cas équiprobable, chacune des sept lettres serait codée en log2 N = log2 7 = 2.8 bits. a 0 b 100 c 101 d 110 e 1110 f 11110 g 11111

Recently converted files (publicly available):