Français
Menu

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

On veut construire un code préfixe binaire en attribuant aux quatre symboles A à D des mots de code des longueurs (nombres de bits) suivantes. Quelle combinaison de longueurs de code le permet ?

  1. AA : 1, B : 2, C : 3, D : 3
  2. BA : 1, B : 2, C : 2, D : 3
  3. CA : 1, B : 1, C : 2, D : 3
Afficher la réponse et l'explication

Réponse : A. A : 1, B : 2, C : 3, D : 3

On peut construire un code préfixe de longueurs de code l₁, l₂, … si et seulement si l'inégalité de Kraft Σ 2^(−lᵢ) ≤ 1 est satisfaite. Pour 1, 2, 3, 3, la somme vaut 1/2 + 1/4 + 1/8 + 1/8 = 1 : on peut donc le construire, par exemple avec 0, 10, 110, 111. Pour 1, 2, 2, 3, la somme vaut 1/2 + 1/4 + 1/4 + 1/8 = 9/8, et pour 1, 1, 2, 3, elle vaut 1/2 + 1/2 + 1/4 + 1/8 = 11/8 ; toutes deux dépassent 1, donc aucun de ces deux codes ne peut être construit.

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. On construit un code préfixe binaire dans lequel les mots de code 00 et 01, de longueur 2, sont déjà utilisés. Quel est le nombre maximal de mots de code de longueur 3 que l'on peut ajouter en conservant la condition de préfixe ?
  2. Une source émet les symboles A, B, C et D indépendamment avec les probabilités 0,4 ; 0,3 ; 0,2 et 0,1, et on la code avec un code de Huffman. Quelle est la longueur moyenne de code par symbole ?
  3. Une source émet les symboles A à E indépendamment avec les probabilités 0,3 ; 0,25 ; 0,2 ; 0,15 et 0,1, et on la code avec un code de Huffman. Les mots de code peuvent changer selon celle de deux probabilités égales que l'on choisit en premier, mais pas la longueur moyenne de code. Quelle est la longueur moyenne de code par symbole ?
  4. 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 ?
  5. 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 ?