第五章 无失真信源编码定理
1. 引言
1.1 编码目的与分类
信源编码 (Source Coding)：以提高通信有效性为目的的编码。通过压缩信源的冗余度，减少平均码率。
信道编码 (Channel Coding)：以提高信息传输可靠性为目的的编码。通过增加信源的冗余度，抵抗信道干扰。
密码 (Cryptography)：以提高通信安全性为目的的编码。
1.2 信源编码理论基础
信源编码理论主要基于两个定理：
无失真信源编码定理 (香农第一定理)：离散信源/数字信号编码的基础。
限失真信源编码定理：连续信源/模拟信号编码的基础。
1.3 编码器模型与码长
编码器输入：原始信源符号集 \(S=\{S_1, S_2, \ldots, S_q\}\)。
信道符号集 (码元)：\(X=\{x_1, x_2, \ldots, x_r\}\)。
编码器输出 (码字)：\(C:\{W_1, W_2, \ldots, W_q\}\)。
码长 \(l_i\)：码字 \(W_i\) 所包含的码元个数。
2. 等长码
2.1 等长码定义
若一组码中所有码字长度都相同，称为等长码。
码长是固定的。
2.2 编码所需码长条件
若用 \(r\) 元码对 \(q\) 个信源符号进行等长编码，码长为 \(l\)，必须满足:
\[ q \le r^l \]
若对信源的 \(N\) 次扩展信源进行等长编码，必须满足:
\[ q^N \le r^l \]
- 平均每个信源符号所需的码符号个数 \(\frac{l}{N}\) 必须满足: \[ \frac{l}{N} \ge \frac{\log_r q}{\log_r r} \]
很容易理解，在这里不再赘述。
3. 等长信源编码定理
3.1 核心思想
通过对信源 \(N\) 次扩展，将信源序列划分为高概率集 \(G\) (经常出现) 和低概率集 \(\bar{G}\) (不经常出现)。
只对高概率集 \(G\) 中的序列编码，舍弃低概率集 \(\bar{G}\)，从而减少所需的码长，同时译码错误概率趋近于零。
3.2 定理 5.3 (等长信源编码定理)
一个熵为 \(H(S)\) 的离散无记忆信源 \(S\)，若对其 \(N\) 次扩展信源进行等长 \(r\) 元编码，码长为 \(l\)。对于任意 \(\epsilon > 0\)：
可实现几乎无失真编码：只要满足:
\[ \frac{l}{N} \ge \frac{H(S)+ \epsilon}{\log_2 r} \]
当 \(N \to \infty\) 时，译码错误概率趋近于 0。
不可能实现无失真编码：若满足:
\[ \frac{l}{N} < \frac{H(S)-2 \epsilon}{\log_2 r} \]
当 \(N \to \infty\) 时，译码错误概率接近于 1。
结论: \(\frac{H(S)}{\log_2 r}\) 给出了实现无失真等长编码所需的平均码长（每个信源符号所需的码元数）的极限值。
4. 变长码
4.1 变长码的分类
变长码：所有码字的长度 \(l_i\) 各不相同。
非奇异码：所有码字互不相同。
唯一可译码 (UCD)：码的任意一串序列只能被唯一的译成对应的信源符号序列。
即时码 (Prefix Code)：唯一可译码中的一类，任一码字都不是其他码字的前缀，译码时无需参考后续码字即可判断。
4.2 克拉夫特 (Kraft) 不等式 (定理 5.4/5.5)
对于码符号集为 \(X=\{x_1, \ldots, x_r\}\) 的任意 \(r\) 元即时码或唯一可译码，所对应的码长为 \(l_i\)，则必定满足:
\[ \sum_{i=1}^{q} r^{-l_i} \le 1 \]
定理 5.6：若存在一个码长为 \(l_i\) 的唯一可译码，则一定存在一个同样长度的即时码。这说明在码长方面，唯一可译码不优于即时码，因此只需讨论即时码即可。
4.3 唯一可译变长码的判断法 (萨得纳斯-彼特森测试)
将码 \(C\) 中所有可能的尾随后缀组成一个集合 \(F\)。
当且仅当集合 \(F\) 中没有包含任一码字，则码 \(C\) 为唯一可译码。
5. 变长信源编码定理
5.1 紧致码和平均码长
平均码长 \(\bar{L}\):
\[ \bar{L} = \sum_{i=1}^{q} P(S_i) l_i \]
紧致码 (最佳码)：平均码长 \(\bar{L}\) 最小的唯一可译码。无失真信源编码的基本问题就是寻找紧致码。
5.2 定理 5.8 (无失真变长信源编码定理/香农第一定理)
补充：紧致码满足：\(R=\frac{H(S)}{\bar{L}}\)
离散无记忆信源 \(S\) 的 \(N\) 次扩展信源 \(S^N\)，编码器的码元符号集为 \(X=\{x_1, \ldots, x_r\}\)。总可以找到唯一可译码，使信源 \(S\) 中每个符号所需的平均码长 \(\bar{L} = \sum_{i=1}^q p_il_i\) 满足:
\[ \frac{H(S)}{\log_2 r} \le \frac{\bar{L}}{N} < \frac{H(S)}{\log_2 r} + \frac{1}{N} \]
当 \(N \to \infty\) 时，平均码长可以趋近该极限值 \(\frac{H(S)}{\log_2 r}\)。
- 核心结论: 信源的熵 \(H(S)\) 是无失真信源编码的极限值。要做到无失真编码，信源每个符号所需的平均码元数就是信源的 \(r\) 元熵 \(H_r(S) = \frac{H(S)}{\log_2 r}\)。
5.3 物理意义与编码效率
实质: 无失真信源编码的实质就是对信源进行变换，使变换后新的码符号信源（即信道输入信源）尽可能为等概率分布，从而使信道的信息传输率 \(R\) 达到信道容量 \(C\)，实现信源与信道理想的统计匹配。
编码效率 \(\eta\): 衡量编码效果。
\[ \eta = \frac{H(S)}{\bar{L} \log_2 r} \]
当 \(\bar{L}\) 达到极限值 \(\frac{H(S)}{\log_2 r}\) 时，最佳编码效率 \(\eta_{\max} = 1\)。