Remerciez-le!

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

Td7 codes pdf CODES ET CODAGE DE HUFFMAN Un code est un ensemble de mots E sur un alphabet ? typiquement tel qu ? un mot quelconque 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

CODES ET CODAGE DE HUFFMAN Un code est un ensemble de mots E sur un alphabet ? typiquement tel qu ? un mot quelconque 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 adroite resp de droitea gauche Exercice Codes Parmi les ensembles suivants sur 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 E E E E E E n 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 donnanta 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 pour gauche et pour droite Exemple lettre a b c d occurrences a c d b lettre code a b c d Exercice Encodage On considere le message suivant m tacuitracriatuactaura Quelle sera la taille du codage du message en code ASCII Quelle sera la taille minimale du codage du message en codea longueur ?xe 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 Montrez qu ? on peut obtenir plusieurs codages di ? ?erents mais que la longueur du message une fois cod ?e reste la m eme CExercice d ?ecodage On consid ere le codage de Hu ?man suivant a ? b ? c ? r ? t ? D ?ecodez le message m On suppose qu ? une erreur a ?et ?e commise en transmettant m et que le eme bit a ?et ?e transform ?e en Quel devient le nouveau d ?ecodage du message Exercice Avec des probabilit ?es On consid ere une source qui ?emet continument des avec une probabilit ?e p et des avec une probabilit ?e p On d ?esire utiliser la m ?ethode de Hu ?man pour compresser l ? information re cue Pour cela on regroupe par blocs de bits et On calcule la probabilit ?e que chaque bloc apparaisse et on applique la m ?ethode de Hu ?man Quel est le taux moyen de