Inégalité de Kraft

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En théorie des codes, l'inégalité de Kraft donne, étant donné un ensemble de longueurs de mots de code, une condition suffisante pour l'existence d'un code préfixe et une condition nécessaire pour l'existence d'un code uniquement décodable.

Si les longueurs des mots de code sont l_1, l_2, ..., l_n et que l'alphabet des mots de code est de taille r, l'inégalité s'écrit \sum_{i=1}^{n} \left( \frac{1}{r} \right)^{\ell_i} \leq 1.

L'inégalité de Kraft est nommée d'après Leon Kraft.