Remerciez-le!

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

CODES ET CODAGE DE HUFFMAN Un code est un ensemble de mots E sur un alphabet Σ

CODES ET CODAGE DE HUFFMAN Un code est un ensemble de mots E sur un alphabet Σ (typiquement {0, 1}) tel qu’un mot quel- conque u ∈Σ∗peut ˆ etre d´ ecompos´ e d’une seule fa¸ con au plus. Un code est pr´ eﬁxe (respectivement suﬃxe) si aucun mot de E n’est pr´ eﬁxe (resp. suﬃxe) d’un autre, ce qui fait qu’on peut trouver la s´ eparation en lisant simplement de gauche ` a droite (resp. de droite ` a gauche). Exercice 1. Codes. Parmi les ensembles suivants sur {0, 1}, lesquels sont des codes, des codes pr´ eﬁxes, des codes suﬃxes? Pour ceux qui sont des codes, permettent-ils d’´ ecrire tous les mots? (1) E1 = {0, 10} (2) E2 = {0, 11, 100, 101} (3) E3 = {001, 100, 101} (4) E4 = {01, 10, 101} (5) E5 = {0, 011, 10} (6) E6 = {0n1 | n ∈N} Le principe du codage de Huﬀman ` a deux lettres est de r´ eduire la taille n´ ecessaire pour enregistrer (ou transmettre) un mot en donnant ` a chaque lettre un nouveau code. L’algorithme est le suivant : on dispose de chaque lettre munie de son nombre d’occurrences dans le mot. On consid` ere une lettre comme un arbre (constitu´ e d’une seule feuille), et on les range dans une liste dans par ordre croissant d’occurrences. tant que la liste contient plus d’un arbre : fusionner les premiers deux arbres, leur associer la somme des occurrences, ranger ce nouvel arbre dans la liste. On obtient ﬁnalement un arbre binaire : on lit ensuite le codage de chaque lettre en prenant 0 pour gauche et 1 pour droite. Exemple : lettre occurrences a 23 b 5 c 8 d 4 40 17 c,8 9 d,4 b,5 a,23 lettre code a 1 b 011 c 00 d 010 Exercice 2. Encodage. . . On consid` ere le message suivant : m = tacuitracriatuactaura (1) Quelle sera la taille du codage du message en code ASCII? (2) Quelle sera la taille minimale du codage du message en code ` a longueur ﬁxe? (3) Appliquez le proc´ ed´ e de Huﬀman et proposez un code pour repr´ esenter le message. Ecrivez le codage associ´ e au message. Quelle est sa taille? (4) Montrez qu’on peut obtenir plusieurs codages diﬀ´ erents mais que la longueur du message une fois cod´ e reste la mˆ eme. Exercice 3. . . . d´ ecodage. On consid` ere le codage de Huﬀman suivant : a 7→1 b 7→011 c 7→000 r 7→010 t 7→001 (1) D´ ecodez le message m = 011101000110111000. (2) On suppose qu’une erreur a ´ et´ e commise en transmettant m et que le 4eme bit a ´ et´ e transform´ e en 0. Quel devient le nouveau d´ ecodage du message? Exercice 4. Avec des probabilit´ es. On consid` ere une source qui ´ emet continument des 0 avec une probabilit´ e p0 = 1 4 et des 1 avec une probabilit´ e p1 = 3 4. On d´ esire utiliser la m´ ethode de Huﬀman pour compresser l’information re¸ cue. Pour cela on regroupe par blocs de 2 bits 00, 01, 10 et 11. On calcule la probabilit´ e que chaque bloc apparaisse et on applique la m´ ethode de Huﬀman. (1) Quel est le taux moyen de compression (taille moyenne du message compress´ e/bit de la source)? (2) On regroupe maintenant les bits 3 par 3. Quel est le taux moyen de compression? Exercice 5. Le mot des premiers. On rappelle que les nombres premiers plus petits que 100 sont : 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 et 97. On considere le mot u, de longueur 100, sur l’alphabet binaire B = {0, 1} dont les lettres sont u1u2 · · · u100, avec ui = 1 si i est un nombre premier et 0 sinon (il n’est pas n´ ecessaire d’´ ecrire le mot en entier pour r´ epondre aux questions suivantes). On d´ ecoupe le mot en blocs de taille 2, de la forme u2n−1u2n, pour n ≥1. (1) Indiquez le nombre d’occurrences de chacun de ces blocs dans u (attention au d´ ebut du mot avec la particularit´ e de 2). (2) Construisez un arbre de Huﬀman sur les blocs de longueur 2. (3) Quelle sera la taille du message une fois compress´ e par la m´ ethode d’Huﬀman? uploads/S4/ td7-codes-pdf.pdf