问题

无前缀(prefix-free)编码是无歧义(decodable)编码的真子集，但是一个不那么显然的结论是，无歧义编码在平均码长的意义下并不优于无前缀编码。

命题

任何无歧义的二进制编码方式均可找到一个等价的prefix-free编码，使得平均码长不增加

证明

假设code words为$c_1,c_2,\dots,c_n,$ 码长为 $l_i=|c_i|,i=1,2,\dots,n$

引理1：若$\sum_{i=1}^n2^{-l_i}\le1$，则存在码长为 $l_i$ 的prefix-free编码$\tilde c_1,\tilde c_2,\dots,\tilde c_n$

证明：利用二叉树表示可见

引理2：若$c_1,c_2,\dots,c_n$是无歧义编码，则码长 $l_i$ 满足$\sum_{i=1}^n2^{-l_i}\le1$

证明：定义$A(s)$表示二进制串s在上述编码方式下的合法解码种数，则由无歧义性可知，$A(s)\in\{0,1\}$.

定义:

$$a_m=\mathbb{E}_{s\in\{0,1\}^m}A(s)$$

表示长度为n的串平均解码种数，其中s在$\{0,1\}^m$中均匀分布；

对s开头的code word进行讨论可得，

$$A(s)=\sum_{s=c_iw}A(w)$$

两边取期望得，

$$\mathbb{E}_{s\in\{0,1\}^m}A(s)=\sum_{i=1}^n\mathbb{E}_wA(w)\cdot P(s=c_iw)$$

其中$P(s=c_iw)$ 表示s以$c_i$为前缀的概率，显然是$2^{-l_i}$，因此得到：

$$a_m = \sum_{i=1}^na_{m-l_i}\cdot2^{-l_i}$$

倘若$\sum_{i=1}^n2^{-l_i}>1$，容易得到$a_m$以指数增长到无穷，但是由于$A(s)\in\{0,1\}$，所以$a_m\le1$对任意m成立，因此产生矛盾！

利用上面两个引理，命题得证.