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

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 ?

Afficher la réponse et l'explication

Réponse : A. 4

Il existe 2³ = 8 suites de bits de longueur 3, mais les quatre qui commencent par 00 ou 01 (000, 001, 010 et 011) ne peuvent pas être utilisées. Les quatre restantes, 100, 101, 110 et 111, ne sont en relation de préfixe ni avec 00 ni avec 01 : on peut donc toutes les ajouter. L'inégalité de Kraft donne le même résultat : 2/4 + n/8 ≤ 1, d'où n ≤ 4.

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

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 ?
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 ?
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 ?
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 ?
Quelle description de la relation entre la compression sans perte et l'entropie d'une source est correcte ?