第一章 绪论
第二章 离散信源及信息测度
第三章 离散信道及其信道容量
第四章 连续信源和波形信道
第五章 无失真信源编码定理
第六章 有噪信道编码
第七章 限失真信源编码
第八章 无失真信源编码
第九章 纠错编码

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

5.1 概述

编码器概论

• 信源编码的作用：

1. 使信源适合于信道的传输，用信道能传输的符号来代表信源发出的消息；
2. 在不失真或允许一定失真的条件下，用尽可能少的符号来传递信源消息。

• 信源编码的目的：提高通信的有效性。

  通常通过他所信源的冗余度来实现，采用的帅抽奖方法使压缩每个信源符号的平均比特数。

信源编码理论使信息论的重要分支，其理论基础使信源编码的两个定理：

• 无失真信源编码定理
• 限失真信源编码定理

本章主要介绍无失真编码原理.

信源编码器模型

• 码字：W_i=x_{i_1}x_{i_2}...x_{i_{l_i}}
• 信源符号集：S=\{s_1,s_2,...,s_q\}
• 码C：\{W_1,W_2,...,W_q\}
• 码符号集：X=\{x_1,x_2,...,x_r\}
• 码元：x_i
• r元码：\{x_1,x_2,...,x_r\}
• 码长：l_i
• 定长码：每个信源符号对应的码字长度相等。
• 变长码：信源符号对应码字的长度不等。
• 奇异码：多个信源符号对应相同的码字相同
• 非奇异码：不同的信源符号对应的码字各不相同。
• N次扩展码：信源符号扩展，对应码字扩展。

5.2 定长码

唯一可译定长码存在的条件

非奇异定长码一定是唯一可译码。

对简单信源S进行定长编码时：

• 设信源符号集中共有q个符号：S=\{s_1,s_2,...,s_q\}

• 码符号中共有r个码元：X=\{x_1,x_2,...,x_r\}

• 定长码的码长为l

• 若满足非奇异性（唯一可译码），则：

  q\le r^l

💡 例如给26个字母用二元码组进行编码，最小的码长为：l\ge\frac{\log q}{\log r}=4.7，l_{\min}=5。

• 如果对N次扩展信源s^N进行定长编码，要满足非奇异性，须满足条件：

  q^N\le r^l

5.3 5.4 定长信源编码定理

设离散平稳无记忆信源的熵为H(S)，若对N次扩展信源S^N进行定长编码，对于任意\epsilon>0，只要满足

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

则当N足够大，可实现几乎无失真编码，即译码错误概率P_E为任意小。

反之，如果

\frac l N\le\frac{H(S)-2\epsilon}{\log r}

则不可能实现无失真编码，当N足够大时，译码错误概率P_E为1。

• 编码信息率R：编码后平均每个码符号载荷的实际信息量。

  R=\frac{H(S)}{l/N}

• 编码效率\eta

  \eta = \frac R{\log r}

5.5 变长码

基本概念

• 分组码：将信源符号集中的每个信源符号S_i固定的映射成一个码字W_i，这样的码称为分组码。

• 唯一可译码：任意一串有限长的码符号序列只能被唯一地译成对应的信源符号序列，此码为唯一可译码。

  唯一可译码的充要条件：编码的任意次扩展均为非奇异码。

• 即时码、非即时码：若某个唯一可译码在接收到一个完整的的码字时无需考虑后面的码符号就能立刻译码，此类码称为即时码。

  唯一可译码成为即时码的充要条件：设W_i是C中任一码字，则要求其他码字W_j，都不是码字W_i的前缀。

• 即时码的构造方法：r叉树。将所有码字安排在终端节点即可得到即时码。

Kraft不等式

设信源符号集为：S=\{s_1,s_2,...,s_q\}，码符号集X=\{x_1,x_2,...,x_r\}，码C=\{W_1,W_2,...,W_q\}，每个码字的码长分别为l_1,l_2,...,l_q。

即时码存在的充要条件是：

\sum\limits^q_{i=1}r^{-l_i}\le1

上式被称为Kraft不等式。

变长唯一可译码的判别方法

将码中所有可能的尾随后缀组成一个集合F,当且仅当集合F中没有包含任一码字，则判断为唯一可译码。

步骤：

1. 初始化：S_0=C；
2. 构造S_1：考察S_0中所有码字，若一个码字是另一个码字的前缀，则将后缀作为S_1中的元素。
3. 构造S_n(n>1)：将S_0和S_{n-1}比较，如果S_0中有码字是S_{n-1}中元素的前缀，则将相应的后缀放入S_n中；同样S_{n-1}中若有元素是码字的前缀，也将相应的后缀放入S_n中。
4. 检验S_n：
   • 若S_n是空集，则断定码C是唯一可译码，退出循环；
   • 反之，如果S_n中的某个元素与S_0中的某个元素相同，则断定码C不是唯一可译码，退出循环。
   • 如果上述两个条件都不满足，则返回步骤3。

• 动态示例

  

  

5.6 变长信源编码定理

码平均长度\overline L：

设信源S编码后的码字为W_1,W_2,...,W_q，码字对应长度l_1,l_2,...,l_q，则码平均长度:

\overline L=\sum\limits^q_{i=1}p(s_i)l_i

• 紧致码/最佳码：该唯一可译码对应的码平均长度小于所有其他的唯一可译码。

编码后信道的信息传输率

R=H(X)=\frac{H(S)}{\overline L}(比特/码符号)

紧致码平均码长界限定理

设离散无记忆信源的熵为H(S)，使用r个码进行编码，则总可以找到一个无失真信源编码，构成唯一可译码，使其平均码长满足：

\frac{H(S)}{\log r}\le \overline L\le\frac{H(S)}{\log r}+1

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

设离散无记忆信源的熵为H(S)，它的N次扩展信源为S^N，对扩展信源S^N进行编码。总可以找到一种编码方法，构成唯一可译码，使平均码长满足：

\frac{H(S)}{\log r}\le \frac{\overline L_N}N\le\frac{H(S)}{\log r}+1

• 当N\rightarrow\infty时，有\lim\limits_{N\rightarrow\infty}\frac{\overline L_N}{N}=H_r(S)；
• 把香农第一定理推广到一般离散信源：\lim\limits_{N\rightarrow\infty}\frac{\overline L_N}{N}=\frac{H_\infty}{\log r}。

编码效率

\eta=\frac{H_r(S)}{\overline L}=\frac{H(S)/\overline L}{\log r}=\frac{H(S)}{\overline L\log r}

习题

判断对错：

1. 无失真信源编码定理的作用是提高通信的可靠性。
2. 编码器的作用是将信源的消息转换为符号，以便在信道上传输。
3. 变长码是指信源符号对应的码字长度都相等。
4. 定长信源编码定理能够实现完全无失真编码。
5. 即时码是指在接收到一个完整的码字后无需考虑后面的码符号就能立刻译码。
6. Kraft不等式是判断某个编码方案是否为唯一可译码的条件之一。
7. 定长信源编码定理是指当编码信息率足够大时可以实现几乎无失真编码。
8. 编码平均长度是指编码后平均每个码符号所携带的信息量。
9. 紧致码/最佳码是指平均码长小于其他所有唯一可译码的编码方案。
10. 香农第一定理只适用于离散平稳无记忆信源。
11. 无失真信源编码定理的目的是减少信源发出的消息的失真程度。
12. 变长码是指信源符号对应的码字长度可以不相等。
13. 定长信源编码定理简单来说就是当编码长度足够大时能实现几乎无失真编码。
14. 即时码是指在接收到一个完整的码字后，需要考虑后面的码符号才能完全译码。
15. Kraft不等式是判断某个编码方案是否为即时码的条件之一。
16. 编码平均长度是指编码后平均每个符号所携带的信息量。
17. 紧致码/最佳码是指平均码长大于其他所有唯一可译码的编码方案。
18. 香农第一定理适用于所有类型的信源，无论是否是离散平稳无记忆信源。
19. 编码效率是指编码后平均每个符号所携带的比特数。
20. 变长无失真信源编码定理是香农第一定理的推广，适用于一般离散信源。

• 答案

  1-错、2-对、3-错、4-错、5-对、6-对、7-对、8-错、9-对、10-对、11-对、12-对、13-对、14-错、15-对、16-错、17-错、18-错、19-对、20-对。