第11讲信源编码三个基本编码课件

1、第5章：信源编码第5章：信源编码通信系统的性能指标主要是有效性、可靠性、安全性和经济性，除了经济性外，这些指标正是信息论研究的对象。编码的目的是为了优化通信系统，使这些指标达到最佳；按不同的编码目的，编码分为三类：信源编码、信道编码和安全编码/密码。通信系统的性能指标主要是有效性、可靠性、安全性和经济性，除了信源编码的基本途径有两个：使序列中的各个符号尽可能地互相独立，即解除相关性；使编码中各个符号出现的概率尽可能地相等，即概率均匀化。第11讲信源编码三个基本编码课件信源编码的分类：离散信源编码、连续信源编码和相关信源编码三类。离散信源编码：独立信源编码，可做到无失真编码；连续信源编码：独立信

2、源编码，只能做到限失真信源编码；相关信源编码：非独立信源编码。信源编码的分类：离散信源编码、连续信源编码和相关信源编码三类信源编码的基础是信息论中的两个编码定理： 无失真编码定理只适用于离散信源 限失真编码定理 对于连续信源，只能在失真受限制的情况下进行限失真编码信源编码的基础是信息论中的两个编码定理：5.1.4 赫夫曼编码5.1.3 费诺编码5.1.5 游程编码5.1.6 冗余位编码5.1.1 码字唯一可译的条件5.1.2 香农编码5.1 离散信源编码5.1.4 赫夫曼编码5.1.3 费诺编码5.1.5 游程编即时码：如果一个码的任何一个码字都不是其他码字的前缀，则称该码为前缀码、异前置码也

3、称为即时码。ki 称为码字长度或简称码长m为码符号数即时码：如果一个码的任何一个码字都不是其他码字的前缀，则称该判断以下码字是否可分离？例判断以下码字是否可分离？例对离散无记忆信源，消息长度为L，符号熵为H(X),对信源进行m元变长编码，一定存在无失真的信源编码方法，满足：其码字平均长度K满足：其码字平均信息率R对离散无记忆信源，消息长度为L，符号熵为H(X),对信源进行5.1.4 赫夫曼编码5.1.3 费诺编码5.1.5 游程编码5.1.6 冗余位编码5.1.1 码字唯一可译的条件5.1.2 香农编码5.1.4 赫夫曼编码5.1.3 费诺编码5.1.5 游程编例设一单符号离散无记忆信源试对该

4、信源编二进制香农码。5.1.2 香农编码例设一单符号离散无记忆信源试对该信源编二进制香农码。5.1.二进制香农码的编码步骤如下：（1）将信源符号按概率从大到小的顺序排列 p(x1) p(x2) p(xn)（2）令 p(x0)=0，用 pa(xj)，j=i+1 表示第 i 个码字的累加概率，则二进制香农码的编码步骤如下：（2）令 p(x0)=0，用 p （3）确定满足下列不等式的整数 ki ，并令 ki 为第 i 个码字的长度log2 p(xi) ki 1 log2 p(xi) （4）将 pa(xj) 用二进制表示，并取小数点后 ki 位作为符号 xi 的编码。 （3）确定满足下列不等式的整数

5、ki ，并令 ki 为计算出给定信源香农码的平均码长由离散无记忆信源熵定义，可计算出信源熵为：计算出给定信源香农码的平均码长信息率为编码效率为信源熵和信息率之比信息率为5.1.4 赫夫曼编码5.1.3 费诺编码5.1.5 游程编码5.1.6 冗余位编码5.1.1 码字唯一可译的条件5.1.2 香农编码5.1.4 赫夫曼编码5.1.3 费诺编码5.1.5 游程编例:设有一单符号离散信源对该信源编二进制费诺码。例:设有一单符号离散信源 （2）按编码进制数将概率分组，使每组概率尽可能接近或相等。如编二进制码就分成两组，编 m 进制码就分成 m 组。（1）将概率按从大到小的顺序排列 p(x1) p(x

6、2) p(xn) （2）按编码进制数将概率分组，使每组概率尽可能接近或相等。（3）给每一组分配一位码元。（4）将每一分组再按同样原则划分，重复步骤 2 和 3，直至概率不再可分为止。（3）给每一组分配一位码元。该信源的熵为平均码长为对上述信源采用费诺编码的信息率为编码效率为第11讲信源编码三个基本编码课件5.1.4 赫夫曼编码5.1.3 费诺编码5.1.5 游程编码5.1.6 冗余位编码5.1.1 码字唯一可译的条件5.1.2 香农编码5.1.4 赫夫曼编码5.1.3 费诺编码5.1.5 游程编 赫夫曼(Huffman) 编码是一种效率比较高的变长无失真信源编码方法。 5.3.1 二进制哈夫曼

7、编码 5.3.2 m 进制哈夫曼编码(自学） 赫夫曼(Huffman) 编码是一种效率比较高的变长 例：设单符号离散无记忆信源如下，要求对信源编二进制哈夫曼码。(1) 将信源符号按概率从大到小的顺序排列，令p(x1) p(x2) p(xn)5.3.1 二进制哈夫曼编码 例：设单符号离散无记忆信源如下，要求对信源编二进制哈(2) 信源的第一次缩减信源：给两个概率最小的信源符号 p(xn1) 和 p(xn) 各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含 (n1) 个信源符号的新信源，用 S1 表示。(2) 信源的第一次

8、缩减信源：给两个概率最小的信源符号 p(3)将缩减信源 S1 的符号仍按概率从大到小顺序排列，重复步骤 (2)，得到只含 (n2) 个符号的缩减信源 S2。(3)将缩减信源 S1 的符号仍按概率从大到小顺序排列，重复(4) 重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为 1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。(4) 重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩信源熵为平均码长为编码效率为若采用定长编码，码长 K=3，则编码效率编码效率提高了 12.7%。第11讲信源编码三个基本编码课件缩减信源时，若合并后的新符号概

9、率与其他符号概率相等，从编码方法上来说，这几个符号的次序可任意排列，编出的码都是正确的，但得到的码字不相同。不同的编法得到的码字长度 ki 也不尽相同。第11讲信源编码三个基本编码课件 例 ：单符号离散无记忆信源 ， 用两种不同的方法对其编二进制哈夫曼码。方法一：合并后的新符号排在其它相同概率符号的后面。 例 ：单符号离散无记忆信源 方法二：合并后的新符号排在其它相同概率符号的前面。方法二：合并后的新符号排在其它相同概率符号的前面。编法一的平均码长为编法二的平均码长为可见 ，本例两种编法的平均码长相同，所以编码效率相同。编法一的平均码长为讨论：码字长度的方差2：长度 ki 与平均码长 之差的平方的数学期望，即编法一码字长度方差：编法二码字长度方差：讨论：比 较 相同点：香农编码、费诺编码、哈夫曼编码属于无失真信源编码。香农编码、费诺编码、哈夫曼编码主要针对无记忆信源。香农码、费诺码、哈夫曼码都考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现了对信源的压缩；比 较不同点：香农码有系统的、惟一的编码方法，但在很多情况下编码效率不是很高；费诺码和哈夫曼码的编码方法都不惟一；费诺码比较适合于对分组概率相等或接近的