6 Lossless Source Coding
章节目录
- 章节目录
- 6-1 信源编码基础 Fundamentals of Source Coding
- 6-2 定长信源编码 Fixed-Length Source Coding
- 6-3 变长码与前缀码 Variable-Length and Prefix Codes
- 6-4 经典无失真编码 Classic Lossless Coding Schemes
6-1 信源编码基础 Fundamentals of Source Coding
6-1-1 通信系统里的编码位置 Coding in Communication System
一个通信系统可以被如下框图描述：
在这条链路里，三类编码的目标不同：
| 编码 Coding | 主要目标 Main Goal | 熵的变化 |
|---|---|---|
| 信源编码 Source Coding | 减少冗余，用更低速率传输同样信息 | 压缩冗余，接近信源熵 |
| 信道编码 Channel Coding | 增加冗余，提高抗噪声能力 | 主动加入冗余 |
| 加密编码 Cryptogram | 提高传输安全性 | 加密增加不确定性，解密恢复可读信息 |
信源编码讨论的是信息被送入信道之前的压缩问题。
6-1-2 信源编码与无失真要求 Source Coding and Lossless Requirement
信源编码 Source Coding
信源编码 Source Coding 指使用更适合传输或存储的码序列 Code Sequence 表示信源产生的原始消息。
这一步由 编码器 Encoder 完成。
设离散信源产生长度为
信源编码把它映射成长度为
其中
无失真编码 Lossless Coding
无失真编码 Lossless Coding 要求信源产生的每个消息都能映射到唯一的码字，且每个码字也只能被译码成唯一的原消息。
从熵的角度看，无失真对应：
给定码字
6-1-3 唯一可译码 Unique Decodability
唯一可译码 Unique Decodability
若任意一串信源符号
经过编码后得到的码串，与任意另一串信源符号的编码结果都不同，则该编码是唯一可译码 Unique Decodable 的。
唯一可译码比“每个单独符号码字不同”更强。码字拼接后仍不能产生歧义。
例如：
则：
译码器看到
6-2 定长信源编码 Fixed-Length Source Coding
6-2-1 消息、码元与信息率 Message, Code Element and Rate
消息 Message 是信源产生的抽象符号，例如字母、标点、天气状态或设备状态。
码元 Code Element 是通信系统可以识别的编码基本单位，例如二进制码中的
对长度为
当
定长码和变长码的区别在于
| 类型 Type | 码字长度 Codeword Length | 目标 |
|---|---|---|
| 定长码 Fixed-Length Code | 每个码字长度固定 | 找到能低错误译码的最小固定长度 |
| 变长码 Variable-Length Code | 不同消息可用不同长度 | 最小化平均码长 |
6-2-2 定长编码定理 Fixed-Length Coding Theorem
设
定长无失真信源编码定理 Fixed-Length Lossless Source Coding Theorem
该定理又称香农第一定理 Shannon's First Theorem。
对任意
若
则当
若
则当
这个定理给出的是极限结论。只要允许把足够长的符号序列作为整体编码，定长编码的效率可以任意接近
实际中不可能真的取
理想定长编码器的思路是：
- 给定
和 ，估计需要一起编码的序列长度 ； - 列出所有长度为
的可能符号序列； - 按发送概率从大到小排序；
- 只给高概率集合
分配码字，使
其中常用的长度估计式为：
PROBLEM IT6-E1
设平稳无记忆信源
用二进制定长码分别编码单符号消息和二符号消息，讨论编码效率与错误概率。
SOLUTION
信源熵为：
若对每个单符号使用二进制定长码，需要：
编码效率为：
此时四个单符号都能被编码，译码错误率为
若把两个符号作为一个消息，则共有
二符号信源熵为：
而
因此未被覆盖的概率约为：
这里效率高于
6-3 变长码与前缀码 Variable-Length and Prefix Codes
6-3-1 变长编码定理 Variable-Length Coding Theorem
变长码的基本原则是：
- 高频消息用短码字；
- 低频消息用长码字；
- 最终降低平均码长。
设离散无记忆信源
若每次把长度为
对应的平均信息率为：
因此：
当
6-3-2 编码效率与同步问题 Coding Efficiency and Synchronisation
变长码编码效率定义为：
由上一节的不等式可得下界：
对二进制码，若某信源熵为：
要求
代入可得：
因此取：
变长码的代价是译码复杂度更高。译码器需要判断一个码字何时结束，这涉及同步译码 Synchronous Decoding 和译码延迟 Decoding Delay。
6-3-3 前缀码与 Kraft 不等式 Prefix Code and Kraft Inequality
前缀码 Prefix Code
若任意一个码字都不是另一个码字的前缀，则该编码称为前缀码 Prefix Code。
前缀码也称为即时码 Instantaneous Code，因为译码器读到一个完整码字后可以立刻译码，不需要等待后续码元。
前缀码一定是唯一可译码，但唯一可译码不一定是前缀码。
前缀码可以用树图表示：
定长码对应满树，变长码对应非满树。每个叶节点是一个码字，内部节点不能作为码字，否则会成为其他码字的前缀。
Kraft 不等式 Kraft Inequality
存在一个
若对每个消息
则：
于是：
因此这种码长分配满足 Kraft 不等式，可以构造前缀码。
6-4 经典无失真编码 Classic Lossless Coding Schemes
6-4-1 Shannon 编码 Shannon Code
Shannon 编码 Shannon Code 直接按照消息概率确定码长，再用累积概率生成码字。
二进制 Shannon 编码步骤：
- 按概率从大到小排列信源符号；
- 计算第
个符号之前的累积概率
- 取码长
- 将
写成二进制小数，取小数点后 位作为 的码字。
PROBLEM IT6-E2
对如下单符号信源进行二进制 Shannon 编码：
SOLUTION
| 符号 | Shannon 码字 | |||
|---|---|---|---|---|
平均码长为：
信源熵为：
编码效率为：
6-4-2 Fano 编码 Fano Code
Fano 编码 Fano Code 通过反复分组构造码字。
- 按概率从大到小排列信源符号；
- 将符号分成
组，使各组概率和尽量接近； - 给每组分配一个码元；
- 对每组继续递归分组，直到每组只剩一个符号。
对 6-4-1 中的同一信源，一种二进制 Fano 编码为：
| 符号 | Fano 码字 | |
|---|---|---|
平均码长为：
编码效率为：
Fano 编码的分组通常不唯一。若某次分组概率和比较接近，编码效果会很好；若分组不理想，平均码长会被拉高。
6-4-3 Huffman 编码 Huffman Code
Huffman 编码 Huffman Code 每次合并最低概率的符号，最终从合并树回溯得到码字。
二进制 Huffman 编码步骤：
- 按概率从大到小排列信源符号；
- 取概率最低的两个符号，分别赋码元
和 ； - 合并这两个符号，合并后概率为二者概率之和；
- 对新的缩减信源重复上述过程，直到只剩两个符号；
- 沿合并路径回溯，得到原符号的码字。
对 6-4-1 中的同一信源，一种二进制 Huffman 编码为：
| 符号 | Huffman 码字 | |
|---|---|---|
平均码长同样为：
编码效率为：
Huffman 编码不一定唯一。若缩减信源中出现相同概率，合并后的新符号可以排在相同概率符号之前或之后。不同排法可能得到相同平均码长，但码长方差不同。
对
则需要加入若干零概率虚符号，或在第一轮合并时少合并几个真实符号。
6-4-4 三种编码方法对比 Comparison
三种编码方法都利用信源统计特性：概率大的符号分配短码字，概率小的符号分配长码字。
| 方法 | 是否唯一 | 主要特点 | 适用情况 |
|---|---|---|---|
| Shannon Code | 通常唯一 | 由累积概率直接生成，步骤固定 | 计算简单，但效率不一定高 |
| Fano Code | 不唯一 | 递归分组，依赖分组质量 | 分组后概率和接近时效果较好 |
| Huffman Code | 不唯一 | 每次合并最低概率符号 | 平均码长通常最优，工程上最常用 |