2025-11-10 11:02:47 星期一
5.1 关于编码的例子
首先给出定义
定义 关于随机变量 \(X\) 的信源编码 \(C\) 是从 \(X\) 的取值空间 \(\mathcal{X}\) 到 \(\mathcal{D}^*\) 的一个映射，其中 \(\mathcal{D}^*\) 表示 \(D\) 元字母表 \(D\) 上有限长度的字符串构成的集合。用 \(C(x)\) 表示 \(x\) 的码字并用 \(l(x)\) 表示 \(C(x)\) 的长度。
例题 \(C(\text{红})=00\)，\(C(\text{蓝})=11\) 是 \(\mathcal{X}=\{\text{红}, \text{蓝}\}\) 关于字母表 \(D=\{0,1\}\) 的一个信源编码。
定义 设随机变量 \(X\) 的概率密度函数为 \(p(x)\)，定义信源编码 \(C(x)\) 的期望长度 \(L(C)\) (expected length) 为
其中 \(l(x)\) 表示对应于 \(x\) 的码字长度。
不失一般性，可假定 \(D\) 元字母表为 \(D=\{0,1,\cdots,D-1\}\)。
下面我们逐步对编码的定义条件作进一步的限制。
定义 如果编码将 \(X\) 的取值空间中的每个元素映射成 \(\mathcal{D}^*\) 中不同的字符串，即
则称这个编码是非奇异的(nonsingular)。
注：上面的所谓非奇异，用数学的话术就是"单射"。并且非奇异不能保证可译性。
为此我们引入：
定义 编码 \(C\) 的扩展 (extension) \(C^*\) 是从 \(\mathcal{X}\) 上的有限长字符串到 \(\mathcal{D}\) 上的有限长字符串的映射，定义为
其中 \(C(x_1)C(x_2)\cdots C(x_n)\) 表示相应码字的串联。
例 5.1.4 若 \(C(x_1)=00\), \(C(x_2)=11\)，则 \(C(x_1,x_2)=0011\)。
定义 如果一个编码的扩展编码是非奇异的，则称该编码是唯一可译的 (uniquely decodable)。
换言之，惟一可译码的任一编码字符串只来源于惟一可能的信源字符串。尽管如此，仍然可能需要通过整个编码字符串，才能最终确定信源字符串。甚至有时对于确定字符串中的第一个字符，我们也必须这样。
定义 若码中无任何码字是其他码字的前缀，则称该编码为前缀码 (prefix code) 或即时码 (instantaneous code)。
例子：考虑A=0 B=10 C=110 D=1110, 在这个编码里面，没有任何码字是其他码字的前缀，这就是前缀码
关系：非奇异不一定唯一可译，唯一可译但不一定是即时码
5.2 Kraft不等式
定理 5.2.1（Kraft不等式，前缀码存在定理）：对于 \(D\) 元字母表，存在码字长度为 \(l_1, l_2, \ldots, l_m\) 的前缀码的充要条件是这些码字长度满足 Kraft 不等式：
证明：
必要性。我们构建一个D叉树，设码字的最大长度为 \(l_{\text{max}}\)，那么作为D叉树而言，树的最底层最多有 \(D^{l_{\text{max}}}\) 个元素。现在选取码长为 \(l_i\) 的码字，由于是前缀码，不能是别的码字的"前缀"，所以该码字的节点以后就没有分叉了，该码字独占了子树，若没有独占，那么该子树延伸到最底层的时候，应该有 \(D^{l_{\text{max}}-l_i\) 个元素，那么我们对 \(i\) 求和，就得到了 \(\sum_i D^{l_{\text{max}}-l_i} \le D^{l_{\text{max}}}\)，同时除掉 \(D^{l_{\text{max}}}\) 就得到了该不等式。
充分性。首先我们将码字长度按照从小到大排序，从一个空的D叉树开始，第一个深度为 \(l_1\) 的节点记为第一个码字1（由必要性部分的证明，这样会去掉最底层的 \(D^{l_{\text{max}}}-D^{l_1}\) 个节点），在剩余的节点中，寻找第一个深度为 \(l_2\) 的节点，记为第二个码字2，这样会去掉最底层的 \(D^{l_{\text{max}}}-D^{l_2}\) 个节点，以此类推。
这个算法可以进行下去的原因就在于Kraft不等式。我们从归纳法的角度考虑，在我们准备分配第 \(k\) 个码字的时候，我们已经分好了前面 \(k-1\) 个码字，此时我们已经在底层 \(D^{l_{\text{max}}}\) 个节点里面去掉了 \(\sum_{i=1}^{k-1} D^{l_{\text{max}} - l_i}\) 个节点，由Kraft不等式，\(\sum_{i=1}^{m} D^{-l_i} \leq 1\)，对于前面 \(k-1\) 个码字而言，显然 \(\sum_{i=1}^{k-1} D^{-l_i} < \sum_{i=1}^{m} D^{-l_i} \leq 1\)，同时乘 \(D^{l_{\text{max}}}\)，\(\sum_{i=1}^{k-1} D^{l_{\text{max}} - l_i} < D^{l_{\text{max}}}\)，这个不等式告诉我们，即使我们移除了前 \((k-1)\) 个码字的所有后代，底层仍然有节点剩余。既然底层还有节点剩余，那么在树的第 \(l_k\) 层，必然存在节点，其通往底层的整条路径都还没有被之前的码字阻断。
综上，前缀码的存在性就证明了。
例题：现有码字 00, 01, 11, 100, 10100, 10101, 10110, 10111，验证 Kraft 不等式。
解：这些码字对应的码长分别为：
- 00, 01, 11：长度 2
- 100：长度 3
- 10100, 10101, 10110, 10111：长度 5
使用二进制字母表 (\(D=2\))，计算 Kraft 和：
由于 Kraft 和等于 1，满足 Kraft 不等式，因此存在具有这些码长的前缀码。