Français
Menu

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

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 ?

  1. AEnviron 0,72 bit
  2. B0,78 bit
  3. C1 bit
Afficher la réponse et l'explication

Réponse : B. 0,78 bit

Les quatre couples ont pour probabilités 0,64 (00), 0,16 (01), 0,16 (10) et 0,04 (11). On fusionne 0,04 et 0,16 en 0,2, puis 0,2 et 0,16 en 0,36, et enfin ce nœud avec 0,64 : les longueurs de code sont donc de 1, 2, 3 et 3 bits, et la moyenne par couple vaut 0,64 × 1 + 0,16 × 2 + 0,16 × 3 + 0,04 × 3 = 1,56 bit. Par symbole d'origine, cela fait 1,56 ÷ 2 = 0,78 bit. Coder un symbole à la fois ne permet que d'attribuer 1 bit à 0 et 1 bit à 1, mais coder les symboles par groupes rapproche la longueur de l'entropie, d'environ 0,72 bit.

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. Quelle description de la relation entre la compression sans perte et l'entropie d'une source est correcte ?
  2. 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 ?
  3. Quelles données le codage par plages a-t-il le plus de chances de rendre les plus petites ?
  4. Quelle description de l'idée de la méthode LZ77, utilisée dans ZIP, gzip et des outils similaires, est correcte ?
  5. On veut restaurer des données compressées par la méthode LZ77. Les données se composent, dans cet ordre, de « caractère A », « caractère B » et « (distance 2, longueur 5) ». (distance d, longueur L) signifie répéter L fois, un caractère à la fois, l'opération « copier à la fin de la chaîne restaurée le caractère situé d caractères avant sa fin ». Quelle est la chaîne restaurée ?