本記事は情報理論の徹底解説シリーズに含まれます。
初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。
概要
クラフトの不等式は，各符号語の長さが与えられたときに，それらの長さをもつ符号語で構成される符号が瞬時符号を構成可能かどうかを判定する不等式がクラフトの不等式です。
- クラフトの不等式
-
長さが $l_{1},l_{2},\ldots,l_{K}$となる$K$個の符号語を持つ$q$元符号で瞬時符号となるものが存在するための必要十分条件は
\begin{align}
q^{-l_{1}}+q^{-l_{2}}+\cdots+q^{-l_{K}} \leq 1
\end{align}
が満たされることである。
証明
クラフトの不等式は，木構造を用いて符号を表せば直感的に理解することができます。クラフトの不等式は，「根から1Lの水を流していったときに全ての葉に到達した水の総量は最大でも1L」ということを表しています。
そりゃそうですよね。つぎ込んだ水が1Lなのであれば，葉に到達する水が1Lより増えることはありません。ただし，存在する全ての葉が符号語に対応するわけではないので，1Lを下回ることはあります。逆に言えば，全ての葉が符号語に対応している符号では，葉に到達する水の総量は1Lになります。
さて，以下ではクラフトの不等式を数式を使って証明していこうと思います。やや天下り的にはなりますが，クラフトの不等式を証明するには多項式の展開を利用します。改めて，クラフトの不等式を書くと以下のようになります。
\sum_{k=1}^K q^{-l_{k}} \leq 1 \label{eq:クラフトの不等式}
\end{align}
目標は式$(\ref{eq:クラフトの不等式})$を示すことです。多項式の展開を利用するため，式$(\ref{eq:クラフトの不等式})$の左辺を$N$乗したものを考えます。
\left(\sum_{k=1}^{K} q^{-l_{k}}\right)^{N}
&=\left(\sum_{k}^{K} q^{-l_{k_{1}}}\right)\left(\sum_{k=1}^{K} q^{-l_{k_{2}}}\right) \cdots\left(\sum_{k}^{K} q^{-l_{k_{N}}}\right) \\
&=\sum_{k_{1}} \sum_{k_{2}} \cdots \sum_{k_{N}} q^{-\left(l_{k_{1}}+l_{k_{2}}+\cdots+l_{k_{N}}\right)}\label{eq:クラフトの不等式くくる前}
\end{align}
最初の式変形は，一般性を失わないために，$N$個の項それぞれで$l_{k_1}, \ldots, l_{k_N}$の順番を固定しないということを表しています。続いて，式(\ref{eq:クラフトの不等式くくる前})では同じ指数をもつ項が出現する可能性があることを考えると，$\left(l_{k_{1}}+l_{k_{2}}+\cdots+l_{k_{N}}\right)$，つまり指数が同じ項をくくり出すことを考えます。くくり出した後の$q^n$の係数を$C_n$と置けば，くくり出す操作は以下のように表すことができます。
\left(\sum_{k=1}^{K} q^{-l_{k}}\right)^{N}
&=\sum_{n=N\cdot l_{m}}^{N\cdot l_{M}} C_{n} q^{-n}
\end{align}
ただし，$l_k\;(k=1,\ldots, K)$の最小値を$l_{m}$，最大値を$l_{M}$と置きました。このように置くと，$C_n$の下限として$N\cdot l_{m}$，上限として$N\cdot l_{M}$を考えれば十分なことから，シグマの範囲は$N\cdot l_{m}$から$N\cdot l_{M}$になっています。
さて，ここで$C_n$の上限を考えたいと思います。$C_n$というのは$\sum_k q^{-l_k}$を展開して共通項$q^{-n}$でくくり出したときの係数でした。くくり出すときの係数として最大となるのは，$q^{-n}$が$n$個の$q^{-1}$を掛け合わせて生成されたときです。このとき$q^{-1}$の係数としては$q$種類考えられますので，$n$個の$q^{-1}$の積に対する係数$C_n$としては$q^n$種類考えられます。したがって，以下が成り立ちます。
C_n \leq q^n
\end{align}
したがって，以下が成り立ちます。
\left(\sum_{k=1}^{K} 2^{-l_{i}}\right)^{N}
&= \sum_{l=N\cdot l_{m}}^{N\cdot l_{M}} C_{n} q^{-n}\\[0.7em]
&\leq \sum_{l=N\cdot l_{m}}^{N\cdot l_{M}} q^{n} q^{-n}\\[0.7em]
&=\sum_{l=N\cdot l_{m}}^{N\cdot l_{M}} 1\\[0.7em]
&\leq N\cdot l_{M}
\end{align}
これより，
\sum_{k}^{K} q^{-l_{k}} \leq\left(N\cdot l_{M}\right)^{1 / N}
\end{align}
が任意の$N$に対して成り立つことが分かります。この対数を取って$N \rightarrow \infty$ の極限を考えると，
\lim_{N \rightarrow \infty} \log \left(N\cdot l_{M}\right)^{1 / N}
&=\lim_{N \rightarrow \infty} \frac{1}{N} \log \left(N\cdot l_{M}\right)\\[0.7em]
&=\lim_{N \rightarrow \infty} \frac{1}{N} \log N+\lim_{N \rightarrow \infty} \frac{1}{N} \log l_{M}\\[0.7em]
&= 0 + 0 = 0
\end{align}
であるため，
\lim_{N \rightarrow \infty}\left(N\cdot l_{M}\right)^{1 / N}=1
\end{align}
となります。したがって，
\sum_{k=1}^{K} q^{-l_{i}} \leq 1
\end{align}
が成り立ちます。
コメント