Kraft 不等式的证明

这其实是一个引理
引出最优信源符号编码定理与编码方法( Huffman，Shannon-Fano )。

( Kraft不等式 ) 给定正整数 $s_1$，$s_2$，$\dots$，$s_m$，存在一个可译码 $f: I\rightarrow J^{\star}$，码字长度是 $s_1$，$s_2$，$\dots$，$s_m$，当且仅当

$$\tag{1}\label{kraft_disequal} \sum_{i = 1} ^m q ^{-s_i} \le 1$$

而且，在式 ($\ref{kraft_disequal}$) 下，存在一个长度为 $s_1$，$s_2$，$\dots$，$s_m$ 的无前缀编码。

证明：

充分性( $\Rightarrow$ )：

^[1]中的方法：

把所有可能的码字列出来构成一个码树，所示如下：

由于是前缀码，一旦大的被选择了，后面小的就不能被选了，蓝色的加在一起的高度不能超过 1。每一个被选择的块的高度为$q^{-s_i}$，加在一起就可以得到 Kraft 不等式了。

^[2]中的方法：
难点就是从大到小对码长排序依次放缩。

必要性( $\Leftarrow$ )：

^[1][2]中的方法：

利用不同的码字组合在一起得到的序列也是不同的这个性质既可以得到。

---

1. 1.MacKay, Davidj. C. Information theory, inference, and learning algorithms[M]. Cambridge University Press, 2003. ↩
2. 2.Kelbert M, Suhov Y. Information Theory and Coding by Example[M]. Cambridge University Press, 2013. ↩