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 et que l'alphabet des mots de code est de taille , l'inégalité s'écrit .

L'inégalité de Kraft est nommée d'après Leon Kraft. Elle est publiée par Kraft en 1949. Toutefois, l'article de Kraft traite uniquement des codes de préfixe, et attribue l'analyse menant à l'inégalité à Raymond Redheffer.