重新发现 Kraft 不等式
Abstract. 今天上信息论课的时候被提问为什么我们在研究平均编码长度时只考虑了前缀无关码，而不考虑非前缀无关但是可以唯一解读的编码。以前以为前者比后者要弱，但今天证了一手发现前缀无关码还真不弱于可唯一解读的编码。在证明过程中重新发现了 Kraft 不等式，特发此傻逼文章。
准备定义
对于给定的字符集 $\Sigma$，一个编码系指一个映射 $C: \Sigma\rightarrow \{0, 1\}^*$。一个字符 $x\in \Sigma$ 的编码长度记作 $\mathscr{l}(x) = |C(x)|$。信息论中常考虑的一个问题是给定一个 $\Sigma$ 上的概率分布 $P$，编码的期望编码长度
$$
\mathscr{L}(C) = \mathbb{E}_{x\sim P(x)}[\mathscr{l}(x)]
$$
众所周知，如果不存在两个字符 $x_1 \ne x_2$ 使得 $C(x_1)$ 是 $C(x_2)$ 的前缀，则这样的编码 $C$ 称作前缀无关码。全体前缀无关码的集合记作 $A$。
另一方面，我们可以将 $C$ 的定义延拓到字符串 $\Sigma^*$ 上：$C(s_1s_2…s_n) = C(s_1)C(s_2)\cdots C(s_n)$。如果不存在两个字符串 $s, t\in \Sigma^*$，$s\ne t$ 但是 $C(s)\ne C(t)$，则称 $C$ 是可唯一解读编码。全体可唯一解读编码的集合记作 $B$。
注意 $A\subsetneq B$。因为显然前缀无关码都是可唯一解读的，并且存在这样一个编码，它并不是前缀无关的，但是是可唯一解读的：
| 字符 | 编码 |
|---|---|
| $\texttt{a}$ | $\texttt{10}$ |
| $\texttt{b}$ | $\texttt{1}$ |
| $\texttt{c}$ | $\texttt{00}$ |
$A$ 上的最优期望编码长度由著名的 Huffman 编码给出，另外配合一些放缩可以得到 Huffman 编码的期望编码长度是信源的信息熵的一个加性近似之类的经典结论，参见 这一篇黑历史。然而以往我们始终回避了讨论 $B\setminus A$ 中的元素。很显然
$$
\min_{C\in B} \mathscr{L}(C) \leq \min_{C\in A}\mathscr{L}(C)
$$
本文将给出上式中不等号取等的证明，从而将（我所知的）经典结论拓展至
定理. 对于任意的信源 $X$，定义 $B$ 为 $X$ 的字符集上所有可唯一解读编码的集合，则
$$
H(X) \leq \min_{C\in B}\mathscr{L}(C) H(X + 1)
$$
证明过程
首先来推导编码可唯一解读的一个必要条件。
设 $\mathscr{S}(L)$ 是编码长度为 $L$ 的字符串总数，即
$$
\mathscr{S}(L) = \mathrm{card}\{s\in \Sigma^* : |C(s)| = L\}
$$
如果存在 $L$ 使得 $\mathscr{S}(L) > 2^L$，那么根据鸽巢原理，必然发生冲突。因此编码可唯一解读的一个必要条件是 $\mathscr{S}(L)\leq 2^L$。现在我们来估计 $\mathscr{S}(L)$。显然它满足如下递推式：
$$
\mathscr{S}(L) = \sum_{c\in \Sigma}\mathscr{S}(L - \ell(c))
$$
其特征方程为
$$
1 = \sum_{c\in \Sigma}x^{-\ell(c)} \label{chareq}
$$
那么 $\mathscr{S}(L)$ 可以用如下式子来估计：
$$
\mathscr{S}(L) = \Omega(\lambda_*^L)
$$
其中 $\lambda_*$ 是该特征方程最大的实根。如果 $\lambda_* > 2$，那么 $\mathscr{S}(L)$ 增长快于 $2^L$，一定存在 $L$ 使得 $\mathscr{S}(L) > 2^L$。因此编码可唯一解读的必要条件是
$$
\sum_{c\in \Sigma} 2^{-\ell(c)}\leq 1 \label{kraft}
$$
否则因为 $\ref{chareq}$ 的右边单调递减趋于 $0$，结合零点存在性，必然有一个大于 $2$ 的零点。
$\ref{kraft}$ 正是 Kraft 不等式。
结论
现在我们知道，不但前缀无关码满足 Kraft 不等式，任意可唯一解读的编码也必须满足 Kraft 不等式。从而，任意可唯一解读的编码可以被 rearrange 成一个前缀无关码，保证每个字符的编码长度不变，这蕴含
$$
\min_{C\in B} \mathscr{L}(C) = \min_{C\in A}\mathscr{L}(C)
$$
重复前缀无关码的相关论证得到
$$
H(X) \leq \min_{C\in B}\mathscr{L}(C) H(X + 1)
$$