Série d’exercices 2 : code de Huffman Problème 1
le canal en considérant le code de Huffman obtenu dans le problème 1 Problème 4 Considérons un alphabet composé des 26 lettres minuscules Traer l’arre de Huffman adaptatif après le traitement de la séquene [b b s e w b s l] Mettez à jour le code de chaque lettre après chaque lecture et générer la séquence binaire résultante
ExamendeTP:codagedeHuffman
Une fois l’arbre de Huffman construit, vous pouvez attaquer l’encodage et le décodage d’une chaîne de caractèresviacetarbre 5 3 1Décodage Le décodage est l’opération la plus simple Elle prend en paramètre l’adresse du nœud racine de l’arbre de
Cours/TD 3 Codage Huffman
1 2 Approximation de l’entropie par codage en blocs Limitations du codage de Huffman – Le codage de Huffman impose d’utiliser un nombre entier de bits pour un symbole source ⇒ codage Huffman sur des blocs de n symboles On montre alors qu’on peut s’approcher de facon plus fine de l’entropie
Codage de Huffman - projeteuorg
Le codage de Huffman est une méthode de compression statistique de données qui permet de réduire la longueur du codage d'un alphabet Le code de Huffman (1952) est un code de longueur variable optimal, c'est-à-dire tel que la longueur moyenne d'un texte codé soit minimale On observe ainsi des réductions de taille de l'ordre de 20 à 90
Corrigé : codage de Huffman Partie ICodage d’une suite de
option informatique Corrigé : codage de Huffman Partie I Codage d’une suite de caractères Question 1 a) Commençons par écrire une fonction assoc de type char >clef >code telle que assoc u c renvoie le codage du
CODAGE ET COMPRESSION D IMAGES SANS PERTES
Exercice 1 (Codage de Huffman) Dans cette exercice nous allons appliquer à l’image le codage de Huffman en considérant les couleurs comme l’alphabet de la source Pour toute lecture, l’image sera parcourue "ligne par ligne" en commençant par le coin en haut à gauche 1
Algo L3 Info Travaux dirigés, séance 101 Compression
Codage de longueur variable Construire avec l’algorithme de Huffman un codage de longueur variable pour A Donner l’arbre de codage correspondant et le tableau des codes Calculer la longueur moyenne du co-dage et commenter le résultat en une phrase Réponse 0 : Après avoir fait tourner Huffman (on peut avoir plusieurs solutions) on obtient
APMM TD correction - Fournier-Sniehotta
Ce codage n’est pas complet, car l’ensemble des mots de code est un sous-ensemble du codage complet de taille 5 : {0, 100, 101, 110, 111} Les codages {0, 10, 110, 111} et {00, 01, 10, 11} sont complets donc mieux adaptés 2 CODAGES COMPRESSIFS: SHANNON, FANO-SHANNON ET HUFFMAN
Cours/TD 4 Compression par transform´ee Codage JPEG
Codage JPEG 1 Compression par transform´ee : transform´ee, quanti-fication, codage pr`es de l’entropie 1 1 Transform´ees Bases orthogonales Definition Soit E
Examen Théorie de l’Information
I - Exercice codage de source (25 minutes) Une source binaire génère les symboles s1 et s2 avec les probabilité p(s1)=0,9 et p(s2)=0,1 Les deux symboles sont indépendants a) Calculer l’entropie de cette source binaire Î H(S) = 0,469 bit/symbole b) Calculer l’entropie de la source étendue, constituée de n=3 symboles de la source
[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.caSĠ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.caProblè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 queTe 0V.
NVW-ce que cela veuW il Tire que le coTe Te Huffman eVW inefficace pour laWranVmiVVion 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 laVé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 TeVVouVDĠ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.caProblè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