クラフトの不等式
φ : S ∗ → T ∗ {\displaystyle \phi :S^{*}\to T^{*}} を符号化関数とし、 φ ( s i ) ∈ T ∗ {\displaystyle \phi (s_{i})\in T^{*}} の文字数を l i {\displaystyle \ell _{i}} とする。
このとき、φが一意に復号可能なら、
∑ i = 1 n r − l i ≤ 1 {\displaystyle \sum _{i=1}^{n}r^{-\ell _{i}}\leq 1}
が成立する。この不等式をクラフトの不等式と呼ぶ。
(なおクラフトの不等式において等号が成立する必要十分条件は、φが完全な符号である事である。)
逆に自然数 l 1 , l 2 , ... , l n {\displaystyle \ell _{1},\ell _{2},\ldots ,\ell _{n}\,} がクラフトの不等式を満たすなら、ある一意に復号可能な符号化関数 φ : S ∗ ↦ T ∗ {\displaystyle \phi :S^{*}\mapsto T^{*}} が存在し、任意のiに対し φ ( s i ) ∈ T ∗ {\displaystyle \phi (s_{i})\in T^{*}} の文字数が l i {\displaystyle \ell _{i}} となる。