第五章 无失真信源编码定理

1. 引言

1.1 编码目的与分类

• 信源编码 (Source Coding)：以提高通信有效性为目的的编码。通过压缩信源的冗余度，减少平均码率。

• 信道编码 (Channel Coding)：以提高信息传输可靠性为目的的编码。通过增加信源的冗余度，抵抗信道干扰。

• 密码 (Cryptography)：以提高通信安全性为目的的编码。

1.2 信源编码理论基础

信源编码理论主要基于两个定理：

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$：

1. 可实现几乎无失真编码：只要满足:

   $$
   \frac{l}{N} \ge \frac{H(S)+ \epsilon}{\log_2 r}
   $$

   当 $N \to \infty$ 时，译码错误概率趋近于 0。

2. 不可能实现无失真编码：若满足:

   $$
   \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 唯一可译变长码的判断法 (萨得纳斯-彼特森测试)

1. 将码 $C$ 中所有可能的尾随后缀组成一个集合 $F$。

2. 当且仅当集合 $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$。

---