一般の場合の証明

ウィキペディア小見出し辞書

一般の場合の証明

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2012/05/01 12:28 UTC 版)

「クラフトの不等式」の記事における「一般の場合の証明」の解説

接頭符号とは限らない一般の符号に対してクラフトの不等式を示す。なお、定理の逆は、既に接頭符号が構成できる事を示しているので、証明の必要がない。 さて、を符号化関数とし、以下の母関数を考える： ただしここで、はのビット数を表す。 m を任意の自然数とするとき、 が成立する。 右辺を次数毎にまとめたものを と書くと、φの単射性より、は長さの符号語の数に等しい。長さの語は個しかないので、 が成立する。 さて、の中で最も短い語の長さをmin、最も長い語の長さをmaxとする。すると の定義より、多項式の最低次の項の次数はm minであり、最高次の項の次数はm maxである。 以上の議論より、 が成立する。 mは任意だったので上の不等式は任意のmに対して成立する。mを無限大に飛ばしたとき、左辺は指数関数的に変化するのに対し、右辺は線形にしか増加しない。従って任意のmに対して上の不等式が成立する事から が成立する。 とすれば、 の定義より、 が成立する。すなわち、クラフトの不等式が証明された。