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^[1]. 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 ${\mathcal {S}}=\{s_{0},s_{1},\dots s_{n-1}\}$ et ${\mathcal {C}}$ un code uniquement décodable de ${\mathcal {S}}$ sur un alphabet ${\mathcal {T}}$ de taille $r$ , en notant les longueurs des mots de code $\ell _{i}=|{\mathcal {C}}(s_{i})|$ , alors

$\sum _{i=0}^{n-1}r^{-\ell _{i}}\leqslant 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

{\displaystyle \{a,b,c,d,e,f\}} — 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 ${\mathcal {A}}$ arbre $r$ -aire, avec ${\mathcal {L}}({\mathcal {A}})$ l’ensemble de ses feuilles, et $d(\ell )$ la profondeur de la feuille $\ell$ : $\sum _{\ell \in {\mathcal {L}}({\mathcal {A}})}r^{-d(\ell )}\leqslant 1$

Démonstration

Par induction structurelle sur l’arbre : évident si ${\mathcal {A}}$ est une feuille ou vide.

Si ${\mathcal {A}}={\mathcal {N}}({\mathcal {A}}_{0},{\mathcal {A}}_{1},\dots ,{\mathcal {A}}_{r-1})$ , tel que ${\mathcal {A}}_{i}$ vérifie l'inégalité de Kraft pour tout $i$ , notons $d'(\ell )$ la profondeur de la feuille $\ell$ dans le sous-arbre de ${\mathcal {A}}$ auquel elle appartient. On a alors :

$\sum _{\ell \in {\mathcal {L}}({\mathcal {A}})}r^{-d(\ell )}=\sum _{i=0}^{r-1}\sum _{\ell \in {\mathcal {L}}({\mathcal {A}}_{i})}r^{-d(\ell )}=\sum _{i=0}^{r-1}\sum _{\ell \in {\mathcal {L}}({\mathcal {A}}_{i})}r^{-d'(\ell )-1}=r^{-1}\sum _{i=0}^{r-1}\sum _{\ell \in {\mathcal {L}}({\mathcal {A}}_{i})}r^{-d'(\ell )}$

En appliquant l’hypothèse de récurrence, on a $\sum _{\ell \in {\mathcal {L}}({\mathcal {A}})}r^{-d(\ell )}\leqslant r^{-1}\sum _{i=0}^{r-1}1=1$

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 $\forall i,~f_{i}=\ell _{i}$ .

Démonstration

Sans perte de généralité, supposons $\ell _{0}\leqslant \ell _{1}\leqslant \dots \ell _{n-1}$ On propose de construire cet arbre avec l’algorithme suivant :

programme arbre(n, r, [l_0, l_1, ... l_{n-1}])
    A <- Arbre r-aire complet de profondeur l_{n-1}
    pour i de 0 à n-1
        choisir un noeud n de A non-marqué de profondeur l_i
        en faire une feuille i.e. supprimer tous ses descendants
        le marquer
    retourner A

Pour justifier de la correction de l'algorithme, on a besoin de deux éléments :

On ne supprime jamais un nœud marqué par l’algorithme : lorsqu'on construit une feuille de profondeur $\ell _{i}$ , on ne supprime que des nœuds de profondeur strictement supérieure à $\ell _{i}$ . Or, comme les profondeurs sont triées par ordre croissant, toutes les feuilles marquées sont de profondeur au plus $\ell _{i}$ .
À l'étape $i$ , il existe un nœud de profondeur $\ell _{i}$ qui n’a pas été marqué : il suffit de remarquer qu'à l'étape $j$ l’algorithme supprime ou marque $r^{\ell _{n-1}-\ell _{j}}$ nœud(s) de profondeur $\ell _{n-1}$ . Avant l'étape $i$ on a donc supprimé ou marqué $\sum _{j=0}^{i-1}r^{\ell _{n-1}-\ell _{j}}\leqslant r^{\ell _{n-1}}\sum _{j=0}^{n-1}r^{-\ell _{j}}\leqslant r^{\ell _{n-1}}$ , par inégalité de Kraft. Il existe donc un nœud de profondeur $\ell _{n-1}$ qui n'a été ni marqué, ni supprimé, prenons son ancêtre de profondeur $\ell _{i}$ , ce nœud n’a pas encore été marqué, ce qui conclut la preuve de l'algorithme.

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.

Démonstration

Notons $\ell (a)$ la longueur du code d'un mot $a$ sur ${\mathcal {S}}$ et $\ell _{M}=\max\{\ell (s),s\in {\mathcal {S}}\}$ , et considérons $N_{m,p}$ le nombre de mots de taille $m$ dont le code est de taille $p$ : $N_{m,p}=|\{a\in {\mathcal {S}}^{m},\ell (a)=p\}|$ . comme ${\mathcal {C}}$ est uniquement décodable, on a $N_{m,p}\leqslant |{\mathcal {T}}^{p}|=r^{p}$ .

On a alors

$\sum _{a\in {\mathcal {S}}^{m}}r^{-\ell (a)}=\sum _{p=1}^{m\ell _{M}}\sum _{a\in {\mathcal {S}}^{m},\ell (a)=p}r^{-\ell (a)}=\sum _{p=1}^{m\ell _{M}}N_{m,p}r^{-p}\leqslant \sum _{p=1}^{m\ell _{M}}r^{p}r^{-p}=m\ell _{M}$

Mais un simple développement nous donne : $\left(\sum _{s\in {\mathcal {S}}}r^{-\ell (s)}\right)^{m}=\sum _{a\in {\mathcal {S}}^{m}}r^{-\ell (a)}$ , ce qui nous amène à $\sum _{s\in {\mathcal {S}}}r^{-\ell (s)}\leqslant (m\ell _{M})^{1/m}$ . Ceci étant vrai pour tout $m$ , comme $(m\ell _{M})^{1/m}\longrightarrow 1$ , on retrouve l'inégalité voulue.

Notes et références

↑ (en) Leon Gordon Kraft, « A device for quantizing, grouping, and coding amplitude-modulated pulses », Massachusetts Institute of Technology (Thèse),‎ 1949 (lire en ligne, consulté le 18 juillet 2019)