Français
Menu

Bases de la théorie de l'information et du codage

Une source émet les symboles A, B et C indépendamment avec les probabilités 0,6 ; 0,3 et 0,1, et son entropie vaut environ 1,30 bit. Quelle valeur est la plus proche de l'efficacité (entropie ÷ longueur moyenne de code) lorsque cette source est codée avec un code de Huffman ?

  1. AEnviron 65 %
  2. B70 %
  3. CEnviron 93 %
Afficher la réponse et l'explication

Réponse : C. Environ 93 %

Le code de Huffman fusionne 0,1 et 0,3 en 0,4, puis 0,4 et 0,6 : les longueurs de code sont donc de 1 bit pour A et de 2 bits pour B et C. La longueur moyenne de code vaut 0,6 × 1 + 0,3 × 2 + 0,1 × 2 = 1,4 bit, et l'efficacité vaut 1,30 ÷ 1,4 ≈ 0,93, soit environ 93 %. Les quelque 7 % restants sont un gaspillage dû au fait que les longueurs de code sont limitées à des nombres entiers de bits.

S'entraîner sur ce thème Retour au thème

Autres questions sur Bases de la théorie de l'information et du codage

  1. Une source binaire émet 0 avec la probabilité 0,8 et 1 avec la probabilité 0,2, indépendamment. On regroupe les symboles deux par deux, on traite chacun des quatre couples 00, 01, 10 et 11 comme un seul symbole, et on les code avec un code de Huffman. Quelle est la longueur moyenne de code par symbole d'origine ?
  2. Quelle description de la relation entre la compression sans perte et l'entropie d'une source est correcte ?
  3. La chaîne de 40 caractères AAAAAAAAAAAABBBBCCCCCCCCCCCCCCCCCCCCDDDD (12 A, 4 B, 20 C et 4 D) est compressée avec le codage par plages, qui représente chaque suite d'un même caractère par un couple « caractère (1 octet) et nombre (1 octet) ». La chaîne d'origine utilise 1 octet par caractère. Si l'on définit le taux de compression comme « taille après compression ÷ taille avant compression », quel est le taux de compression ?
  4. Quelles données le codage par plages a-t-il le plus de chances de rendre les plus petites ?
  5. Quelle description de l'idée de la méthode LZ77, utilisée dans ZIP, gzip et des outils similaires, est correcte ?