Qu'est-ce que Inégalité de Kraft ?

L'inégalité Σ 2^(−lᵢ) ≤ 1, condition nécessaire et suffisante pour qu'il existe un code préfixe binaire de longueurs de code l₁, l₂, …, lₙ. On la comprend facilement en remarquant qu'utiliser un mot de code de longueur l exclut toutes les suites de bits qui commencent par lui, ce qui occupe 2^(−l) de l'ensemble. Par exemple, les longueurs 1, 2, 3, 3 donnent une somme exactement égale à 1 et peuvent être réalisées par 0, 10, 110, 111. Tout code décodable de manière unique satisfait cette inégalité (théorème de McMillan) : pour choisir des longueurs de code, il suffit donc de chercher parmi les codes préfixes.

Nom japonais: クラフトの不等式

« Inégalité de Kraft » apparaît dans 2 questions d'entraînement réparties sur 1 thèmes, dont Bases de la théorie de l'information et du codage.

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

S'entraîner : questions sur Inégalité de Kraft

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 ?

AA : 1, B : 2, C : 3, D : 3
BA : 1, B : 2, C : 2, D : 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.

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.

« Inégalité de Kraft » dans les explications

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.
On veut construire un code préfixe binaire en attribuant au…
L'inégalité de Kraft donne le même résultat : 2/4 + n/8 ≤ 1, d'où n ≤ 4.
On construit un code préfixe binaire dans lequel les mots d…

Questions mentionnant « Inégalité de Kraft » (2)

Termes associés

Code préfixe Bit de parité Canal binaire symétrique Codage de Huffman Codage par plages (RLE) Code de Hamming Compression avec perte Compression sans perte Correction d'erreurs directe (FEC) Distance de Hamming

Retour au glossaire