第三章 信源编码 (Source Coding)

1. 信源编码的基本概念

1.1 编码的目的与目标

• 主要目的：减少信源剩余度（冗余），提高传输的有效性。
• 信息传输的两个核心指标：
  1. 有效性（Effectiveness）：对应信源编码，旨在压缩数据。
  2. 可靠性（Reliability）：对应信道编码，旨在抗干扰。

1.2 码的分类

• 分组码（Block Codes）：将信源符号序列划分为固定长度的组进行编码。
• 非分组码：
  • 奇异码（Singular Codes）：存在不同的信源符号对应相同的码字。
  • 非奇异码（Non-singular Codes）：每一个信源符号对应唯一的码字（不能重复）。
    • 唯一可译码（Uniquely Decodable Codes）：任意有限长度的码字序列只能被唯一地分割成一个个码字。
      • 即时码 / 前缀码（Instantaneous / Prefix Codes）：没有任何一个码字是其他码字的前缀。接收端无需参考后续码字即可当场译码。
        • 
      • 非即时码：虽然唯一可译，但可能需要参考后续符号才能确定当前码字。

1.3 重要结论

• 定长非奇异码：一定是唯一可译码。
• 即时码判别准则：没有一个码字是其他任意码字的前缀。

2. 唯一可译码的判别 (判定准则)

对于变长码，判断其是否为唯一可译码通常使用后缀搜索法。

2.1 判别步骤 (SOP)

1. 找前缀：检查码字集合中，是否存在码字 $w_i$ 是另一个码字 $w_j$ 的前缀。

2. 写后缀：如果存在，将 $w_j$ 除去前缀 $w_i$ 后的剩余部分（即后缀）提取出来，存入后缀集合。

3. 迭代更新：将新产生的后缀加入集合，再次检查：

   • 后缀集合与原始码字集合之间是否存在前缀关系。
   • 后缀集合内部是否存在前缀关系。

4. 持续计算：重复上述过程，直到无法产生新的后缀。

5. 判别标准：

   • 非唯一可译：如果在过程中，某个后缀本身就是一个原始码字，则该码是非唯一可译码。
   • 唯一可译：如果所有支路最终都变为空集（即没有后缀是码字），则该码是唯一可译码。

   

3. 编码的性能度量指标

所有指标均基于统计平均意义。

3.1 平均码长 (Average Code Length)

平均每个信源符号所需的码元个数：

$\bar{L} = \sum_{i} P(s_i) L_i$

其中 $P(s_i)$ 是信源符号 $s_i$ 出现的概率，$L_i$ 是对应的码字长度。

3.2 编码后的信息传输率 ($R$)

平均每个码元所承载的信息量：

$R =\frac{\text{平均每条消息的信息量}}{\text{平均每条消息的码长}}= \frac{H(S)}{\bar{L}} \quad (\text{bit/码元})$

3.3 编码效率 ($\eta$)

实际传输率与最大可能传输率之比：

$\eta =\frac{\text{平均每条消息的信息量}}{\text{编码后平均每个码符号能承载的最大信息量}}= \frac{R}{\log_2 r} = \frac{H(S)}{\bar{L} \log_2 r}$

永远记住 $\text{效率}=\frac{\text{实际}}{\text{最优}}$

其中 $r$ 为码元符号的种类数（如二进制编码 $r=2$）。

3.4 码冗余度 ($\xi$)

$\xi = 1 - \eta$

4. 信源扩展编码

当单一符号编码效率不高时，可以采用 $N$ 次扩展信源编码（对符号组进行编码）。

• 结论：信源扩展后，平均每个信源符号的信息量不变。

  $R = \frac{H(S^N)}{\bar{L}_N} = \frac{N \cdot H(S)}{\bar{L}_N} = \frac{H(S)}{\bar{L}_N / N}$

  其中 $\bar{L} = \frac{\bar{L}_N}{N}$ 是平均每个原始信源符号的等效码长。

香农第一定理 (无失真信源编码定理)

只要码长 $N$ 足够长，总能找到一种编码方式，使得平均码长满足：

$\frac{H(S)}{\log_2 r} \le \bar{L} < \frac{H(S)}{\log_2 r} + \frac{1}{N}$

所以说 Block coding才会出现

像是哈夫曼这样的编码方式，能够使得平均码长无限接近于 信源熵

5. 紧致码：Huffman 编码 (Huffman Coding)

Huffman 编码是一种能使平均码长最小的变长编码算法。

5.1 二进制 Huffman 编码步骤

1. 排序：将信源符号按概率从大到小排列。
2. 合并：将概率最小的两个符号合并为一个新节点，概率为两者之和。
3. 重复：对新序列重新排序，重复合并，直到最后只剩一个概率为 1 的根节点。
4. 赋码：从根节点出发，每个分支分别赋 0 或 1，记录下各路径即为码字。

5.2 $r$ 进制 Huffman 编码

• 每次合并概率最小的 $r$ 个节点。
• 注意：若符号数 $n$ 不满足 $(n-1) \pmod{r-1} = 0$，需要添加概率为 0 的“虚符号”补齐。

6. 游程编码Run-Length Encoding, RLE

1. 核心概念：什么是游程编码？

游程编码的基本思想是：不一个一个地记录字符，而是记录同一个字符连续出现的长度。

• 例子：如果你的数据里有大量的 A，偶尔有一个 B，那么记录“有多少个 A 后面跟着一个 B”会比记录“AAAAAB”更节省空间。
• 规则设置：图片中设定 A 的出现概率为 0.9，B 为 0.1。由于 A 经常连续出现，这里设定了 A 的最大连续长度为 4。

注意，要设计那个经常出现的

2. 数据的切分方式

为了进行编码，源字符串会被切分成以下几种组合：

• B: 直接出现 B
• AB: 1个 A 后跟着 B
• AAB: 2个 A 后跟着 B
• AAAB: 3个 A 后跟着 B
• AAAA: 达到了最大长度 4 个 A（注意：这种情况下后面不一定非要有 B）

示例推演：

字符串 ABBAAAAAAABAAAB 会被切分为：

AB` · `B` · `AAAA` · `AAB` · `AAAB

---

3. 游程哈夫曼编码（图表部分）

图片下方的树状图展示了哈夫曼树。它根据每种组合出现的概率来分配二进制代码：

• AAAA 出现的概率最高 ($0.9^4 = 0.6561$)，所以给它分配最短的代码：0。
• B 出现的概率较低 ($0.1$)，分配的代码较长：111。

组合	概率	编码	长度
AAAA	0.6561	0	1位
AAAB	0.0729	100	3位
AAB	0.081	101	3位
AB	0.09	110	3位
B	0.1	111	3位

---

4. 效率分析（右下角数值）

这部分说明了这种编码方法的性能：

• 平均游程长度 (3.439)：平均每次编码能代表多少个原始字符。
• 平均码长 (1.6878)：平均每个组合转换成二进制后的位数。
• 每个字符的平均码长 (≈0.491)：计算方法是 $1.6878 \div 3.439$。这意味着平均每个 A 或 B 只占用约 0.49 位。
• 对比熵 $H(S)$：该信息源的理论极限（熵）约为 0.469。
• 结论：这种方法的效率非常高，只比理论极限多出了 4.7% 的冗余。

总结

这张图是在解释：当某个字符（如 A）出现概率极高时，通过“打包连读字符”再进行哈夫曼编码，可以极大地提高压缩效率。 这常用于传真机协议或简单的图像压缩中。

7. 算术编码 Arithmetic Coding

这三张图片详细介绍了算术编码（Arithmetic Coding）的原理。它是目前压缩效率最高的方法之一，广泛应用于 JPEG2000、H.264 和 H.265 等压缩标准中。

以下是内容的逻辑拆解：

---

1. 核心思想：整体编码 (图1)

图片 1 展示了算术编码与“通常符号（如哈夫曼编码）”的区别：

• 通常符号（哈夫曼）：将信息源切分成一个个小块，每块对应一个码字。
• 算术编码：将整个信息序列压缩成一个单一的代码词。
  • 优点：不需要对每个字符分配整数位，因此可以比哈夫曼编码更接近理论上的压缩极限（熵）。它更适合处理各种复杂的信息源。

---

2. 数学原理：区间与累积概率 (图2)

算术编码的核心是把所有可能的序列映射到 $[0, 1)$ 之间的一个特定子区间。

• 累积概率 $C(b_i)$：

  假设有一组可能的序列（比如所有长度为 $n$ 的 A/B 组合），我们将它们按顺序排列。

  $C(b_i) = \sum_{j=0}^{i-1} P(b_j)$

  其中 $b_i$ 是第 $i$ 个序列，$P(b_i)$ 是该序列发生的概率。

• 编码逻辑：每个序列 $b_i$ 都占据了区间 $[0, 1)$ 中长度为 $P(b_i)$ 的一段。为了代表这个序列，我们只需要在二进制下找到一个最小位数的数字，使其落在该序列对应的区间范围内即可。

---

3. 具体实例演练

一个实际的例子，假设信息源 $S$ 中 $P(A)=0.9, P(B)=0.1$，序列长度为 $3$。

序列 (bi)	概率 P(bi)	累积概率 C(bi)	占据的区间范围	最终编码
AAA	$0.9^3 = 0.729$	0	$[0, 0.729)$	0
AAB	$0.9 \times 0.9 \times 0.1 = 0.081$	0.729	$[0.729, 0.81)$	10
ABA	$0.081$	0.81	$[0.81, 0.891)$	110
…	…	…	…	…
BBB	$0.1^3 = 0.001$	0.999	$[0.999, 1.0)$	1111111

如何理解表格中的编码：

1. AAA 的区间是 $[0, 0.729)$。在二进制小数中，$0.0$ 就在这个范围内，所以编码是 0。
2. AAB 的区间是 $[0.729, 0.81)$。二进制小数 $0.10$（即 $0.5$）不在这里面，但 $0.11$ 会超出，经过计算，在这个范围内能区分出的最短二进制前缀是 10。
3. 概率越大，区间越宽，需要的二进制位数就越少（如 AAA 只有 1 位）；概率越小，区间越窄，需要的位数就越多（如 BBB 需要 7 位）。

---

总结

算术编码的精髓在于：它不为单个字母编码，而是为整个消息找一个“坐标”。

• 消息越长、越符合概率预测，对应的区间就越明确。
• 它能打破哈夫曼编码“每个字符至少占 1 位”的限制（比如在你的例子中，AAA 虽然有 3 个字符，但只用了 1 位来表示，平均每个字符仅 0.33 位）。

这对你研究嵌入式系统或音频识别中的数据压缩非常有用，因为它在有限带宽下能提供极高的性能。

8. 限失真信源编码 (Rate-Distortion Theory)

Rate Distortion Theory

[信息论与编码] 限失真信源编码定理

这里我没有仔细看，如果真的要考，那么优先看上面的这个视频。

在允许一定失真的情况下，进一步压缩数据。

6.1 失真矩阵 (Rate-Distortion Theory)

$D = [d(x_i, y_j)] = \begin{bmatrix} d_{11} & \cdots & d_{1r} \\ \vdots & \ddots & \vdots \\ d_{r1} & \cdots & d_{rr} \end{bmatrix}$

表示输入 $x_i$ 却输出 $y_j$ 时的失真程度。

$R(D)$ 函数是在允许一定失真条件下，平均互信息的最小值。

6.2 最小失真 $D_{min}$ 与最大失真 $D_{max}$

1. 计算 $D_{min}$： 每一行挑选最小的失真值（通常为 0），再与 $P(x_i)$ 加权求和：

   $D_{min} = \sum_i P(x_i) \min_j d(x_i, y_j)$

2. 计算 $D_{max}$： 假设输出与输入完全无关（选择一个最佳的固定输出 $y_j$），计算各列的加权和，挑出其中的最小值：

   $D_{max} = \min_j \sum_i P(x_i) d(x_i, y_j)$

如何求满足保真度 $D_{min}$ 的实验信道

在错误概率最小处填1，其他填0

香农第三定理 (限失真信源编码定理)

只要码长足够长，一定能找到一种编码，其失真度非常接近给定的失真限制要求。

999. 典型例题解析

例题：二元信源 $\{0.1, 0.9\}$

1. 直接编码：效率极低，$\eta = H(0.1, 0.9) \approx 0.469$。
2. 二次扩展编码：
   • 信源符号变为：$s_1s_1(0.01), s_1s_2(0.09), s_2s_1(0.09), s_2s_2(0.81)$。
   • 进行 Huffman 编码后，计算 $\bar{L}_2$，得出 $\bar{L} = \bar{L}_2 / 2 = 0.645$。
   • 效率 $\eta$ 显著提升。

例题：四元对称信源

• 概率分布：$P_s = [\frac{1}{4}, \frac{1}{4}, \frac{1}{4}, \frac{1}{4}]$。
• 失真矩阵 $D$：主对角线为 0，其余为 1。
• 计算结果：$D_{max} = \frac{3}{4}$, $D_{min} = 0$。

例题：游程编码

假设你正在开发一个基于 ESP32-S3 的嵌入式音频检测系统。由于环境非常安静，传感器采集到的数字信号中，符号 $0$（代表静音/低能耗）出现的概率极高，而符号 $1$（代表突发噪音）偶尔出现。

已知条件：

• 符号概率：$P(0) = 0.8$，$P(1) = 0.2$。
• 编码规则：采用游程编码。我们记录连续出现 $0$ 的个数，直到遇到 $1$ 为止。
• 最大长度限制：为了防止计数器溢出，连续 $0$ 的最大游程长度设定为 $3$。

可能的游程组合及其概率如下：

1. $1$ （直接出现 1）：概率 $P = 0.2$
2. $01$ （1个 0 后跟着 1）：概率 $P = 0.8 \times 0.2 = 0.16$
3. $001$ （2个 0 后跟着 1）：概率 $P = 0.8^2 \times 0.2 = 0.128$
4. $000$ （达到最大长度 3个 0）：概率 $P = 0.8^3 = 0.512$

---

第一部分：序列切分

请将以下原始信号序列按照上述规则（最大长度为 3）进行切分：

0000010100011

第二部分：哈夫曼编码设计

根据给出的四种组合及其概率，请构造一棵哈夫曼树，并为它们分配二进制码字（概率大的分配短码）。

• 提示：这四种组合的概率和为 $0.2 + 0.16 + 0.128 + 0.512 = 1$。

第三部分：效率分析

1. 计算该游程编码的平均游程长度 $L_{avg}$。
   • 公式：$L_{avg} = \sum (\text{组合中原始字符的个数} \times \text{该组合概率})$
2. 计算该游程编码的平均码长 $R_{avg}$。
   • 公式：$R_{avg} = \sum (\text{分配的二进制位数} \times \text{该组合概率})$
3. 计算每个原始字符的平均比特数，并观察它是否比直接用 1 位表示 1 个字符更节省空间。

---

推演过程和最终答案。

---

第一部分：序列切分

原始序列：0 0 0 0 0 1 0 1 0 0 0 1 1

按照“最大长度为 3，或遇到 1 截止”的规则，切分如下：

1. 000（达到最大长度）
2. 001（剩余的两个 0 加上后面的 1）
3. 01
4. 000（达到最大长度）
5. 1（最后剩下的 1）

切分结果： 000 / 001 / 01 / 000 / 1

---

第二部分：哈夫曼编码设计

根据概率从小到大排列：

• 001: 0.128
• 01: 0.16
• 1: 0.2
• 000: 0.512

构造哈夫曼树：

1. 合并最小的两个：0.128 (001) + 0.16 (01) = 0.288
2. 合并次小的两个：0.2 (1) + 0.288 = 0.488
3. 最后合并：0.488 + 0.512 (000) = 1.0

分配码字（一种可能的方案）：

• 000：0 （1位）
• 1：10 （2位）
• 01：110 （3位）
• 001：111 （3位）

---

第三部分：效率分析

1. 平均游程长度 $L_{avg}$

计算每个组合包含多少个原始字符：

• 000 (3个), 1 (1个), 01 (2个), 001 (3个)

  $L_{avg} = (3 \times 0.512) + (1 \times 0.2) + (2 \times 0.16) + (3 \times 0.128)$

  $L_{avg} = 1.536 + 0.2 + 0.32 + 0.384 = \mathbf{2.44}$

  （这意味着平均每个码字能代表 2.44 个原始比特）

注意 平均码长 和 平均游程长度分别使用的

前者是编码后的长度

后者是 编码前 的编码对象长度

2. 平均码长 $R_{avg}$

计算编码后的二进制位数：

• 000 (1位), 1 (2位), 01 (3位), 001 (3位)

  $R_{avg} = (1 \times 0.512) + (2 \times 0.2) + (3 \times 0.16) + (3 \times 0.128)$

  $R_{avg} = 0.512 + 0.4 + 0.48 + 0.384 = \mathbf{1.776}$

  （平均每个码字占用 1.776 个比特）

3. 每个原始字符的平均比特数

$\text{效率} = \frac{R_{avg}}{L_{avg}} = \frac{1.776}{2.44} \approx \mathbf{0.728}$

---

结论

• 直接传输：每个字符占 1 bit。
• 游程哈夫曼编码：每个字符平均只需约 0.728 bit。
• 节省空间：约 27.2%。

在这个系统中，由于 0 出现的频率很高（80%），通过把连续的 0 压缩成一个短的码字“0”，我们成功实现了数据的大幅压缩。这和你之前看的图片里的原理是一模一样的。

这个推导过程清楚吗？有没有哪个计算步骤需要再深入讨论的？

游程长度分布（Run-length Distribution）

这类题目属于概率论在信息论中的典型应用，通常出现在分析游程长度分布（Run-length Distribution）的场景中。要解决“在 0 之间提取出的连续 1 的长度为 $k$”的概率问题，核心在于利用条件概率和几何分布的特性。

以下是标准解题步骤：

1. 定义事件

首先要明确题目要求的“被 0 包围的连续 $k$ 个 1”是一个什么样的序列结构。

• 这个结构必须是：0 + 1, 1, ..., 1 ($k$ 个) + 0。
• 在平稳无记忆信源（如 Bernoulli 信源）中，每个符号出现的概率是独立的。设 $P(1) = p$，$P(0) = 1-p$。

2. 构建条件概率模型

题目通常问的是：“已知我们已经提取出了一个由 1 组成的游程（Run），这个游程长度恰好为 $k$ 的概率是多少？”

这本质上是一个条件概率：

$P(\text{length} = k \mid \text{is a run of 1s})$

• 分母（所有游程的可能性）：一个游程的开始标志是从 0 变成 1。一旦开始，它至少会有 1 个“1”。
• 分子（长度恰好为 k）：序列必须表现为：先有 $k$ 个 1，然后紧跟一个 0 结束这个游程。

3. 计算概率

在独立同分布（i.i.d.）序列中，游程长度 $K$ 服从几何分布。

• 发生连续 $k$ 个 1 且以 0 结尾的概率：$P(1)^k \cdot P(0) = p^k(1-p)$。
• 归一化处理：因为我们已经知道这确实是一个“1 的游程”，所以 $k$ 的取值范围是 $1, 2, 3, \dots$。所有可能长度的概率之和为：

$\sum_{i=1}^{\infty} p^i(1-p) = (1-p) \sum_{i=1}^{\infty} p^i = (1-p) \frac{p}{1-p} = p$

因此，长度为 $k$ 的条件概率为：

$P(K=k) = \frac{p^k(1-p)}{p} = p^{k-1}(1-p)$

---

4. 总结做题模板

如果你在考试中遇到这种题，可以按以下逻辑书写：

1. 确认独立性：说明由于信源无记忆，符号出现是相互独立的。
2. 写出序列概率：长度为 $k$ 的 1 游程（紧跟 0）的联合概率是 $P(0 \cdot \underbrace{1\dots1}_{k} \cdot 0)$。但在考虑“提取出的游程”时，通常只看从第一个 1 开始到游程结束的条件概率。：
3. 应用几何分布：直接套用 $P(K=k) = p^{k-1}(1-p)$，其中 $p$ 是该符号自身的概率。

注意点：

• 如果题目问的是“在整个输出序列中，任意位置出现长度为 $k$ 的 1 游程的概率”，那是联合概率。
• 如果题目问的是“提取出的游程长度为 $k$”，那一定是条件概率，结果应符合几何分布且 $\sum P = 1$。

这种概率分布的理解对于你研究算术编码中区间的划分 以及游程编码中平均长度的计算 非常关键，因为它决定了你为不同长度的游程分配多少码长。

马尔科夫信源求游程长度分布

如果是马尔可夫信源（Markov Source），情况会变得稍微复杂一些，因为符号的出现不再是独立同分布（i.i.d.），而是依赖于前一个状态。

在马尔可夫链中，游程长度的分布依然遵循某种形式的几何分布，但其参数由状态转移概率决定。

---

1. 核心逻辑：转移概率

假设我们有一个二阶状态（0 和 1）的马尔可夫过程，其转移概率矩阵为 $P$：

• $P_{00}$：当前是 0，下一个还是 0 的概率。
• $P_{01}$：当前是 0，下一个变成 1 的概率（游程开始）。
• $P_{11}$：当前是 1，下一个还是 1 的概率（游程持续）。
• $P_{10}$：当前是 1，下一个变成 0 的概率（游程结束）。

2. 计算 1 游程长度为 $k$ 的概率

当我们讨论“提取出一个由 0 包围的 1 游程”时，我们关注的是进入状态 1 之后的行为：

1. 起始点：我们已经知道当前状态是 1（且前一个状态是 0）。
2. 持续过程：为了让长度达到 $k$，它必须在接下来的 $k-1$ 次转移中都保持在状态 1。

• 概率为：$(P_{11})^{k-1}$。

3. 终点：在第 $k$ 次转移时，它必须跳回状态 0。

• 概率为：$P_{10}$。

3. 概率公式

对于马尔可夫信源，提取出的 1 游程长度 $K=k$ 的概率为：

$P(K=k) = (P_{11})^{k-1} \cdot P_{10}$

由于在任何状态下 $P_{11} + P_{10} = 1$，我们可以将公式写为：

$P(K=k) = (P_{11})^{k-1} \cdot (1 - P_{11})$

---

4. 马尔可夫信源 vs 独立信源的区别

• 独立信源：$P(K=k) = p^{k-1}(1-p)$。这里的 $p$ 是符号 1 的绝对概率。
• 马尔可夫信源：$P(K=k) = (P_{11})^{k-1}(1-P_{11})$。这里的 $P_{11}$ 是条件概率 $P(1|1)$。

举个直观的例子： 如果一个系统有“惯性”（比如信号平滑），即使 1 的总比例不高，但只要出现一个 1，后面就很容易跟着出现 1（$P_{11}$ 很高）。在这种情况下，马尔可夫模型预测的长游程概率会比独立模型高得多。

5. 总结做题要点

如果题目指明是马尔可夫信源：

1. 找转移矩阵：确定 $P(1|1)$ 和 $P(0|1)$ 的值。
2. 忽略前导 0：因为题目说“提取出 1 游程”，这意味着我们已经处于状态 1 的起始点，不需要计算进入状态 1 的概率 $P_{01}$。
3. 套用公式：直接使用几何分布公式，但一定要用自转移概率 $P_{11}$ 作为参数。

这种处理方式在语音识别和视频压缩（如 H.264 中的 CABAC 编码）中非常关键，因为现实中的数据往往具有很强的时空相关性，表现出明显的马尔可夫特性。