《信息论与编码》课程笔记——信源编码（2）

目录

1. 信源编码基本概念

1.1 信源编码的定义与目的

1.2 编码示例

1.3 编码分类

1.4 唯一可译码的判断标准

2. 香农第一定理（无失真可变长信源编码定理）

2.1 核心内容

2.2 关键结论

2.3 编码指标

3. 经典信源编码方法

1. Shannon编码

2. Fano编码

3. Huffman编码

---

1. 信源编码基本概念

1.1 信源编码的定义与目的

• 信源编码：将信源输出的消息转换为适合信道传输的信号。
• 目标：
  1. 能够传输：匹配信源与信道，确保可译码。
  2. 有效传输：提高传输效率（减少冗余度）。

1.2 编码示例

• ASCII码：7/8位二进制表示字符（如 ​A→01000001​）。
• Morse码：用点（​·​）和划（​-​）表示字母。
• 汉字电码：每个汉字用4位阿拉伯数字编码。

1.3 编码分类

1. 按输出符号取值

   • 基本源编码：对单个信源符号编码（如字母→二进制）。
   • 扩展源编码：对信源符号序列编码（如单词→二进制）。

2. 按信息是否损失

   • 无失真编码：信息完全保留。
   • 有失真编码：允许部分信息损失（如JPEG压缩）。

3. 按译码情况

   • 唯一可译码：任意码序列唯一对应信源符号（如前缀码）。
   • 非唯一可译码：存在歧义（如 ​{0, 01}​ 可能译码为 ​0|1​ 或 ​01​）。

4. 按码长是否固定

   • 定长编码：所有码字长度相同。
   • 变长编码：码长可变。

1.4 唯一可译码的判断标准

• 等长码：若为非奇异码（码字互不相同），则唯一可译。
• 变长码：需满足前缀条件（如 ​{0, 10, 11}​ 是前缀码）。

---

2. 香农第一定理（无失真可变长信源编码定理）

2.1 核心内容

• 研究对象：离散无记忆信源的扩展信源 SN​。
• 目标：通过编码减少冗余度，提高传输效率。
• 定理表述：
  • ​H(S)​：信源熵
  • ​LN​​：平均码长
  • ​r​：码元符号数

2.2 关键结论

1. 数据压缩本质：通过去除相关性或均匀化概率分布减少冗余。
2. 编码效率：随着扩展长度 N​ 增加，平均码长趋近熵下限 logrH(S)​​。

2.3 编码指标

• 平均码长：（物理意义：每符号分配的码元数）。
• 信息传输率：（比特/码元）。
• 编码效率：。

---

3. 经典信源编码方法

1. Shannon编码

核心思想：基于符号概率分配码长，码长接近自信息长度（−logp(xi​)​），但非最优。
步骤：

1. 概率降序排列。
2. 计算码长。
3. 累加概率二进制化：
   • ​F(x1​)=0​ → 二进制 ​0.0​ → 取前1位 → 码字 ​0​。
   • ​F(x2​)=0.5​ → 二进制 ​0.10​ → 取前2位 → 码字 ​10​。
   • ​F(x3​)=0.8​ → 二进制 ​0.1101...​ → 取前3位 → 码字 ​110​。

例题：

题目：对信源符号 X={x1​,x2​,x3​}​ 概率分布进行Shannon编码。

符号	概率p(xi​)​	自信息−logp(xi​)​	码长li​=⌈−logp(xi​)⌉​	累加概率F(xi​)​	二进制化	码字
​x1​​	0.5	1.0	1	0.0	0.0 →​0​	​​0​
​x2​​	0.3	1.737	2	0.5	0.10 →​10​	​​10​
​x3​​	0.2	2.322	3	0.8	0.1100... →​110​	​​110​

计算结果：

• 平均码长 L=0.5×1+0.3×2+0.2×3=1.7​ 码元/符号
• 熵 H(X)≈1.485​ 比特
• 编码效率 η=LH(X)​≈1.71.485​≈87.4%

---

2. Fano编码

核心思想：递归划分概率接近的子集，分别赋 ​0​/​1​。
步骤（以概率 [0.4,0.3,0.2,0.1]​ 为例）：

1. 第一次划分：{x1​}​（0.4）和 {x2​,x3​,x4​}​（0.6）→ 赋 ​0​ 和 ​1​。
2. 第二次划分：{x2​}​（0.3）和 {x3​,x4​}​（0.3）→ 赋 ​10​ 和 ​11​。
3. 第三次划分：{x3​}​（0.2）和 {x4​}​（0.1）→ 赋 ​110​ 和 ​111​。
   结果：

题目：对信源符号 X={x1​,x2​,x3​,x4​}​ 概率分布 进行Fano编码。

符号	概率p(xi​)​	划分步骤（递归二分）	码字
​x1​​	0.4	第一次划分：​0​	​​0​
​x2​​	0.3	第二次划分：​10​	​​10​
​x3​​	0.2	第三次划分：​110​	​​110​
​x4​​	0.1	第三次划分：​111​	​​111​

计算结果：

• 平均码长 L=0.4×1+0.3×2+0.2×3+0.1×3=1.9​ 码元/符号
• 熵 H(X)≈1.846​ 比特
• 编码效率 η≈1.91.846​≈97.2%​

---

3. Huffman编码

核心思想：自底向上合并最小概率符号，构建最优前缀码。
步骤（以概率 [0.4,0.3,0.2,0.1]​ 为例）：

1. 合并最小概率：x3​​ 和 x4​​（0.2+0.1=0.3）→ 新节点赋 ​0​ 和 ​1​。
2. 合并新节点（0.3）和 x2​​（0.3）→ 新节点（0.6）赋 ​0​ 和 ​1​。
3. 合并根节点（0.6）和 x1​​（0.4）→ 完成。
4. 回溯码字：x1​:1​, x2​:01​, x3​:001​, x4​:000​。

最优性：保证平均码长最短。

题目：对信源符号 X={x1​,x2​,x3​,x4​}​ 概率分布 P={0.4,0.3,0.2,0.1}​ 进行Huffman编码。

编码树构建步骤：

1. 合并 x3​​ 和 x4​​（0.2 + 0.1 = 0.3），赋 ​0​ 和 ​1​。
2. 合并新节点（0.3）和 x2​​（0.3），赋 ​0​ 和 ​1​。
3. 合并新节点（0.6）和 x1​​（0.4），赋 ​1​ 和 ​0​。

符号	概率p(xi​)​	合并路径（从根到叶子）	码字
​x1​​	0.4	根 →​1​	​​1​
​x2​​	0.3	根 →​0​ → ​1​	​​01​
​x3​​	0.2	根 →​0​ → ​0​ → ​0​	​​000​
​x4​​	0.1	根 →​0​ → ​0​ → ​1​	​​001​

计算结果：

• 平均码长 L=0.4×1+0.3×2+0.2×3+0.1×3=1.9​ 码元/符号
• 熵 H(X)≈1.846​ 比特
• 编码效率 η≈97.2%