[PDF] [PDF] Série dexercices 2 : code de Huffman Problème 1 Problème 2

[PDF] Série dexercices 2 : code de Huffman Problème 1 Problème 2

(a) Calculer l'entropie de la source (b) Trouver le code de Huffman de la source (c) Calculer la longueur moyenne de ce code ( 

[PDF] Cours/TD 3 Codage Huffman

`A chaque étape la somme des poids restera égale `a 1 L'algorithme de Huffman produit un code binaire préfixe optimal Exemple Considérons une source discr`  

[PDF] Corrigé : codage de Huffman Partie I Codage dune suite de

Corrigé : codage de Huffman Partie I a) Commençons par écrire une fonction assoc de type char −> clef −> code telle que assoc u c renvoie le codage du

[PDF] Algorithmique ENS Lyon L3 - TD4 - Corrigé

18 oct 2005 · 1 Exercices Exercice 1 1 Codage de Huffman 2 - Représenter un codage préfixe par un arbre binaire dont les feuilles sont les lettres de

[PDF] Algo L3 Info Travaux dirigés, séance 101 Compression - [Verimag]

Donner la taille du codage de longueur fixe nécessaire pour coder cet alphabet A Pourquoi n'est-ce Construire avec l'algorithme de Huffman un codage de longueur variable pour A Donner l'arbre de (voir les algos du TD correspondant)

[PDF] Sujet avec corrige - Formations en Informatique de Lille

22 déc 2007 · que la fonction applique Exercice 4 Codage de Hu man Le codage de Huffman est un codage binaire fréquemment utilisé en compression 

[PDF] TD 1 ∑ - Raphaël Fournier-Sniehotta

TD 1 TECHNIQUES DE CODAGE ET DE COMPRESSION 1 LANGAGE Le code de Huffman des symboles de source s'obtient par un parcours de la racine  

[PDF] Examen de TP : codage de Huffman - CNRS

Le codage de Huffman est un procédé très utilisé en compression de données Il sert à encoder un texte en binaire, en utilisant pour chaque lettre un nombre de 

[PDF] THEORIE DE LINFORMATION CORRIGES - E-Eisti

TD 1 Corrigé Modélisation mathématique d'une Taille du code de Huffman (en bits) pour cette image : 40 + 56 +26 = 122 bits Taux de compression : 81

[PDF] codage arithmétique pdf

[PDF] codage arithmétique algorithme

[PDF] représentation des nombres signés exercices corrigés

[PDF] exercice de systeme de numeration

[PDF] système binaire informatique

[PDF] calcul nombre binaire

[PDF] cours sur le calcul binaire pdf

[PDF] codage et représentation de l'information exercices corrigés

[PDF] le codage informatique

[PDF] exercice corrigé codage source

[PDF] combien d'information sont représentées par 15 bits

[PDF] virgule fixe et virgule flottant pdf

[PDF] virgule fixe exercices corrigés

[PDF] exercice corrigé codage virgule fixe

[PDF] virgule flottant ieee 754

DĠpartement d͛informatiƋue et de gĠnie logiciel ÓoUameT Haj Taieb

CompreVVion Te TonnéeV LocalJ PLT 2113 IŃT-4003IIŃT-7023 CourrielJ moUameT.Uaj-Waieb.1@ulaval.ca

SĠrie d͛edžercices 2 J coTe Te Huffman

Problème 1

SoiW une source Ƌui gĠnğre des lettres de l͛alphabet A= {a1, a2, a3, a4 ,a5} avec leV probabiliWéV VuivanWeV J P(a1)=0.15, P(a2)=0.04, P(a3)=0.26, P(a4)=0.05, P(a5)=0.5. (a) Calculer l͛entropie de la source. (b) Trouver le coTe Te Huffman Te la Vource. (c) Calculer la longueur moyenne de ce code. (T) Calculer la redondance de ce code. (e) Calculer l͛efficacitĠ de ce code.

Problème 2

SoiW une Vource qui gĠnğre des lettres de l͛alphabet A= {a1, a2, a3, a4 } avec leV probabiliWéV VuivanWeV J P(a1)=0.1, P(a2)=0.3, P(a3)=0.25, P(a4)=0.35. (a) Trouver un coTe Te Huffman Velon la procéTure UabiWuelle. (b) Trouver un coTe Te Huffman avec la procéTure Te variance minimale. (c) Calculer la variance de ces deux codes. (T) Discuter des performances de ces deux codes.

DĠpartement d͛informatiƋue et de gĠnie logiciel ÓoUameT Haj Taieb

CompreVVion Te TonnéeV LocalJ PLT 2113 IŃT-4003IIŃT-7023 CourrielJ moUameT.Uaj-Waieb.1@ulaval.ca

Problème 3

Dans les systèmes de communications, il est préférable que le nombre de 1s et le nombre Te 0V WranVmiV à WraverV le canal VoienW procUeV. CepenTanW Vi on examine le coTe Te Huffman Tu problème 1 par exemple on Wrouve pluV Te 1V que

Te 0V.

NVW-ce que cela veuW il Tire que le coTe Te Huffman eVW inefficace pour la

WranVmiVVion canal?

Pour réponTre à ceWWe queVWion Wrouver la probabiliWé que 0 VoiW WranVmiV à WraverV le canal en conViTéranW le coTe Te Huffman obWenu TanV le problème 1.

Problème 4

Considérons un alphabet composé des 26 lettres minuscules. Tracer l͛arbre de Huffman adaptatif aprğs le traitement de la sĠƋuence [b b V e w b V l]. ÓeWWeY à jour le coTe Te cUaque leWWre aprèV cUaque lecWure eW générer la

Véquence binaire réVulWanWe.

Problème 5

Référez-ǀous ă l͛edžemple 3.3.1 du manuel du cours ou encore l͛edžemple sur le code ternaire traiter en classe. Il est demandĠ de gĠnĠrer un code de Huffman ternaire pour une source d͛un alphabet composé de 6 lettres tel que J P(a1)=0.2, P(a2)=0.05, P(a3)=0.2, P(a4)=0.2,

P(a5)=0.25, P(a6)=0.1.

La généraWion Te ce coTe eVW fournie TanV la figure ci TeVVouV

DĠpartement d͛informatiƋue et de gĠnie logiciel ÓoUameT Haj Taieb

CompreVVion Te TonnéeV LocalJ PLT 2113 IŃT-4003IIŃT-7023 CourrielJ moUameT.Uaj-Waieb.1@ulaval.ca (a) Calculer l͛efficacitĠ de ce code. (b) Générer un autre code ternaire en combinanW 3 leWWreV à la première éWape eW en combinanW 2 leWWreV à la Teuxième éWape. (c) Calculer l͛efficacitĠ de ce nouǀeau code. (T) Comparer entre ces 2 codes.

DĠpartement d͛informatiƋue et de gĠnie logiciel ÓoUameT Haj Taieb

CompreVVion Te TonnéeV LocalJ PLT 2113 IŃT-4003IIŃT-7023 CourrielJ moUameT.Uaj-Waieb.1@ulaval.ca

Problème 6

La ǀariance de la longueur d͛un code est un critğre important lors du choidž entre 2 codes de Huffman pour optimiser le fonctionnement de la mémoire de VWockage. Cependant ce n͛est pas le seul critğre de choidž. En effet il faut aussi considĠrer la capacité du code à faire face aux erreurV Tu canal eW Te combaWWre le pUénomène de propagation d͛erreurs.

ParWie 1

Considérons le code de Huffman Tonné par le Wableau ci TeVVouV. (a) Encoder la séquence b a c b a b. (b) Supposez maintenant que le canal de transmission à engendrer une erreur TanV le premier biW (récepWion Te 0 au lieu Te 1). MécoTer leV biWV reçuV. (c) Comparer la séquence décodée et la séquence originale.

DĠpartement d͛informatiƋue et de gĠnie logiciel ÓoUameT Haj Taieb

CompreVVion Te TonnéeV LocalJ PLT 2113 IŃT-4003IIŃT-7023 CourrielJ moUameT.Uaj-Waieb.1@ulaval.ca

ParWie 2

Considérons maintenant le code de Huffman donné par le tableau ci dessous. (a) Encoder la séquence b a c b a b. (b) Supposez maintenant que le canal de transmission à engendrer une erreur TanV le premier biW (récepWion Te 0 au lieu Te 1). MécoTer leV biWV reçuV. (c) Comparer la séquence décodée et la séquence originale.

Partie 3

Répéter les parties 1 et 2 en considérant une erreur au troisième bit.quotesdbs_dbs2.pdfusesText_3