クラフトの不等式
一意に復号可能な符号の典型的な特殊例として接頭符号がある。上述の定理を接頭符号の場合に対して証明する。
よく知られているように、接頭符号は次のような r {\displaystyle r} -分木で表す事ができる:各頂点には r {\displaystyle r} 個のアルファベットのうち1つが割り振られ、各符号語は根から葉までの経路で表される。
この木の各頂点に以下のルールで0以上1以下のラベルを再帰的に割り振る:
根には1を割り振る。
頂点iにxが割り振られているとき、iの各々の子にx/rを割り振る。
各頂点はr個以下の子しか持たないので、頂点iの子に割り振られたラベルの総和は頂点iに割り振られたラベル以下である。この事実を葉から根に向かって再帰的に適応する事で次の事実が分かる:
葉に割り振られたラベルの総和は根に割り振られたラベル(=1)以下である。
前述したように、各符号語は根から葉までの経路に対応している。今グラフは木であるから、根から葉までの経路は、経路の終点である葉と一対一対応している。従って各符号語は木の葉と自然に対応付けられる。
ラベルの定義より、深さ l i {\displaystyle \ell _{i}} の頂点のラベルは 1 / r l i {\displaystyle 1/r^{\ell _{i}}} である。木の作り方より符号語の長さは葉の深さに一致しているので、長さ l i {\displaystyle \ell _{i}} の符号語に対応する葉のラベルは 1 / r l i {\displaystyle 1/r^{\ell _{i}}} である。