クラフトの不等式
接頭符号とは限らない一般の符号に対してクラフトの不等式を示す。なお、定理の逆は、既に接頭符号が構成できる事を示しているので、証明の必要がない。
さて、 φ : S ∗ → T ∗ {\displaystyle \phi :S^{*}\to T^{*}} を符号化関数とし、以下の母関数を考える:
F ( X ) = ∑ i = 1 n X − | φ ( s i ) | {\displaystyle F(X)=\sum _{i=1}^{n}X^{-|\phi (s_{i})|}}
ただしここで、 | φ ( s i ) | {\displaystyle |\phi (s_{i})|} は φ ( s i ) {\displaystyle \phi (s_{i})} のビット数を表す。
m を任意の自然数とするとき、
( F ( X ) ) m = ( ∑ i = 1 n X − | φ ( s i ) | ) m = ∑ i 1 = 1 n ∑ i 2 = 1 n ⋯ ∑ i m = 1 n X − ( | φ ( s i 1 ) | + | φ ( s i 2 ) | + ⋯ + | φ ( s i m ) | ) = ∑ i 1 = 1 n ∑ i 2 = 1 n ⋯ ∑ i m = 1 n X − | φ ( s i 1 ⋯ s i 2 s i m ) | {\displaystyle {\begin{alignedat}{2}\left(F(X)\right)^{m}&=\left(\sum _{i=1}^{n}X^{-|\phi (s_{i})|}\right)^{m}=\sum _{i_{1}=1}^{n}\sum _{i_{2}=1}^{n}\cdots \sum _{i_{m}=1}^{n}X^{-\left(|\phi (s_{i_{1}})|+|\phi (s_{i_{2}})|+\cdots +|\phi (s_{i_{m}})|\right)}\\&=\sum _{i_{1}=1}^{n}\sum _{i_{2}=1}^{n}\cdots \sum _{i_{m}=1}^{n}X^{-|\phi (s_{i_{1}}\cdots s_{i_{2}}s_{i_{m}})|}\end{alignedat}}} が成立する。