Inégalité de Kraft

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

Définition formelle

Soit un alphabet $𝒮=\{s_0,s_1,\dots s_{n-1}\}$ et $𝒞$ un code uniquement décodable de $𝒮$ sur un alphabet $𝒯$ de taille $r$, en notant les longueurs des mots de code ${\ell }_i=|𝒞(s_i)|$, alors

$\sum _{i=0}^{n-1}{r}^{-{\ell }_i}⩽1.$

Réciproquement, soient ${\ell }_0,{\ell }_1,\dots {\ell }_{n-1}$ satisfaisant l’inégalité de Kraft, alors, il existe un code préfixe de taille $n$ sur un alphabet de taille $r$ avec ces longueurs de code.

Cas des codes préfixes

un encodage préfixe de l'alphabet $\{a,b,c,d,e,f\}$ sur l'alphabet $\{0,1,2\}$ sous forme d'arbre, par exemple $d$ est codé 112

En se restreignant aux codes préfixes, on trouve une démonstration simple du sens direct basée sur la bijection entre les arbres $r$-aires et les codes préfixes

L’inégalité de Kraft devient alors :

Pour tout $𝒜$ arbre $r$-aire, avec $ℒ(𝒜)$ l’ensemble de ses feuilles, et $d(\ell )$ la profondeur de la feuille $\ell$:$$\sum _{\ell \in ℒ(𝒜)}{r}^{-d(\ell )}⩽1$$ Modèle:Démonstration

Réciproquement, il suffit de montrer qu’à partir de ${\ell }_0,{\ell }_1,\dots {\ell }_{n-1}$satisfaisant l’inégalité de Kraft, on peut construire un arbre $r$-aire avec $n$ feuilles $f_0,\dots f_{n-1}$ vérifiant $\mathrm{\forall }i,f_i={\ell }_i$.

Cas général

Le cas général a un corollaire intéressant : puisque tout code uniquement décodable obéit à l'inégalité de Kraft, et qu'à partir de cette inégalité, on peut construire un code préfixe, pour tout code uniquement décodable, il existe un code préfixe dont les mots codés sont de même taille. Autrement dit, les codes uniquement décodables ne sont pas plus compacts que les codes préfixe.

Remarquons que la réciproque a déjà été traitée dans le cas des codes préfixes, tout code préfixe étant un code uniquement décodable.