第5章_信源编码讲解

《第5章_信源编码讲解》由会员分享，可在线阅读，更多相关《第5章_信源编码讲解（106页珍藏版）》请在金锄头文库上搜索。

1、第1页,2019/10/18,Department of Electronics and Information, NCUT Song Peng,第五章 信源编码技术,5.1 最佳变长编码 5.2 编码的实现 5.3 编码方法简介 5.7 LZ (Lempel-Ziv ) 码 5.8 LZW 码,第2页,2019/10/18,编码的目的,香农编码定理虽然指出了理想编码器的存在性，但是并没有给出实用码的结构及构造方法； 编码理论是为了解决这一问题而发展起来的科学理论； 编码的目的是为了优化通信系统，使这些指标达到最佳； 通信系统的性能指标主要是有效性、可靠性、安全性和经济性，除了经济性外，这些指

2、标是信息论研究的对象。 按不同的编码目的，编码分为三类：信源编码、信道编码和安全编码（密码）。,引 言,第3页,2019/10/18,编码的目的,信源编码：提高通信有效性为目的的编码。通过压缩信源的冗余度实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。 信道编码：提高信息传输的可靠性为目的的编码。通过增加信源的冗余度实现。采用的一般方法是增大码率（带宽）。与信源编码正好相反。 保密编码：提高通信系统的安全性为目的的编码。通过加密和解密实现。从信息论的观点出发，“加密”可视为增熵的过程，“解密

3、”可视为减熵的过程。,引 言,第4页,2019/10/18,信源编码概述,(1) 信源编码的理论基础 信源编码理论是信息论的一个重要分支，其理论基础是信源编码的两个定理。 无失真信源编码定理：是离散信源/数字信号编码的基础； 限失真信源编码定理：是连续信源/模拟信号编码的基础。,引 言,第5页,2019/10/18,信源编码概述,(2) 信源编码的分类 根据信源特性 离散信源编码：独立信源编码，可做到无失真编码； 连续信源编码：独立信源编码，只能做到限失真信源编码； 相关信源编码：非独立信源编码。 根据压缩的特性 冗余度压缩编码：可逆压缩，经编译码后可以无失真地恢复。 熵压缩编码：不可逆压缩。

4、,引 言,第6页,2019/10/18,信源编码概述,(3) 数据压缩概貌,引 言,第7页,2019/10/18,5.1 最佳变长编码,根据信源编码理论，将能够荷载一定信息量且码字的平均长度最短、可分离的变长码字集合称为最佳变长码。 最佳变长码编码的基本原则是： 概率大的信源符号分配短的码字，概率小的信源符号分配长的码字，从而使平均码长最短。 具有代表性的变长编码方法有香农码、 费诺码和哈夫曼码等。,第8页,2019/10/18,5.1.1 香农编码,设离散无记忆信源： 二进制香农码的编码步骤如下： 将信源符号按概率从大到小的顺序排列，令： p(x1) p(x2) p(xn) 令 P(x1)=

5、0，用 Pa(xj)，j=i+1 表示第 i 个码字的累加概率，则： 确定满足下列不等式的整数 ki ，并令 ki 为第 i 个码字的长度 log2 p(xi) ki 1 log2 p(xi) 将 Pa(xj) 用二进制表示，并取小数点后 ki 位作为符号 xi 的编码。,5.1 最 佳 变 长 编 码,第9页,2019/10/18,5.1.1 香农编码,例5.1.1 ：有一单符号离散无记忆信源： 对信源编二进制香农码。其编码过程如表5.1.1所示。 计算出给定信源香农码的平均码长： 若对上述信源采用等长编码，要做到无失真译码，每个符号至少要用 3 个比特表示。相比较，香农编码对信源进行了压缩

6、。 由离散无记忆信源熵定义，可计算出信源上熵为：,5.1 最 佳 变 长 编 码,第10页,2019/10/18,5.1.1 香农编码,例5.1.1 ： 对信源采用香农编码的信息率为： 编码效率为信源熵和信息率之比。则： 编码效率并不是很高。,5.1 最 佳 变 长 编 码,第11页,2019/10/18,5.1.2 费诺编码,将概率按从大到小的顺序排列，令： p(x1) p(x2) p(xn) 按编码进制数将概率分组，使每组概率尽可能接近或相等。如编二进制码就分成两组，编 m 进制码就分成 m 组。 给每一组分配一位码元。 将每一分组再按同样原则划分，重复步骤 2 和 3，直至概率不再可分为

7、止。,5.1 最 佳 变 长 编 码,第12页,2019/10/18,5.1.2 费诺编码,例5.1.2A：设有一单符号离散信源 对信源编二进制费诺码。编码过程如表5.1.2A。 信源的熵为：,5.1 最 佳 变 长 编 码,第13页,2019/10/18,例5.1.2A 平均码长为： 对信源采用费诺编码的信息率为： 编码效率为： 本例中费诺编码有较高的编码效率。费诺码比较适合于每次分组概率都很接近的信源。特别是对每次分组概率都相等的信源进行编码时，可达到理想的编码效率。,5.1.2 费诺编码,5.1 最 佳 变 长 编 码,第14页,2019/10/18,5.1.2 费诺编码,例5.1.2B

8、：有一单符号离散无记忆信源 对该信源编二进制费诺码，编码过程如表5.1.2B。 信源熵为：H(X)=2.75(比特/符号) 平均码长为： 编码效率为=1。之所以如此，因为每次所分两组的概率恰好相等。,5.1 最 佳 变 长 编 码,第15页,2019/10/18,5.1.3 哈夫曼编码,(1) 将信源符号按概率从大到小的顺序排列，令： p(x1) p(x2) p(xn) (2) 信源的第一次缩减：给两个概率最小的信源符号 p(xn1) 和 p(xn) 各分配一个码元“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含 (n1) 个信源符

9、号的新信源，用 S1 表示。 (3) 将缩减信源 S1 的符号仍按概率从大到小顺序排列，重复步骤 (2)，得到只含 (n2) 个符号的缩减信源 S2。 (4) 重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为 1。然后从最后一级缩减信源开始，依编码路径向前返回，可得各信源符号所对应的码字。,编码步骤：,5.1 最 佳 变 长 编 码,第16页,2019/10/18,1. 二进制哈夫曼编码,例5.1.3 对以下信源进行哈夫曼编码 。,在读取码字时，一定要从后向前读，此时编出来的码字才是可分离的异前置码。若从前向后读取码字，则码字不可分离。,5.1 最 佳 变 长 编 码

10、,第17页,2019/10/18,1. 二进制哈夫曼编码,例5.1.3 对以下信源进行哈夫曼编码 。,5.1 最 佳 变 长 编 码,第18页,2019/10/18,1. 二进制哈夫曼编码,例5.1.3A 设单符号离散无记忆信源如下，要求对信源编二进制哈夫曼码。,在读取码字时，一定要从后向前读，此时编出来的码字才是可分离的异前置码。若从前向后读取码字，则码字不可分离。,5.1 最 佳 变 长 编 码,第19页,2019/10/18,1. 二进制哈夫曼编码,例5.1.3A 信源熵为： 平均码长为： 编码效率为： 若采用定长编码，码长 K=3，则编码效率： 哈夫曼的编码效率提高了 12.7%。,5

11、.1 最 佳 变 长 编 码,第20页,2019/10/18,1. 二进制哈夫曼编码,注意：哈夫曼的编法并不惟一。 每次对缩减信源两个概率最小的符号分配“0”和“1”码元是任意的，所以可得到不同的码字。只要在各次缩减信源中保持码元分配的一致性，即能得到可分离码字。 不同的码元分配，得到的具体码字不同，但码长 ki 不变，平均码长也不变，所以没有本质区别； 缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方法上来说，这几个符号的次序可任意排列，编出的码都是正确的，但得到的码字不相同。不同的编法得到的码字长度 ki 也不尽相同。,5.1 最 佳 变 长 编 码,第21页,2019/10/

12、18,1. 二进制哈夫曼编码,例5.1.3B ：单符号离散无记忆信源 用两种不同的方法对其编二进制哈夫曼码。 方法一：合并后的新符号排在其它相同概率符号的后面。,5.1 最 佳 变 长 编 码,第22页,2019/10/18,1. 二进制哈夫曼编码,例5.1.3B ：单符号离散无记忆信源 用两种不同的方法对其编二进制哈夫曼码。 方法二：合并后的新符号排在其它相同概率符号的前面。,5.1 最 佳 变 长 编 码,第23页,2019/10/18,1. 二进制哈夫曼编码,例5.1.3B ： 单符号信源编二进制哈夫曼码，编码效率主要决定于信源熵和平均码长之比。对相同的信源编码，其熵是一样的，采用不同的

13、方法，得到的平均码长可能不同。平均码长越短，编码效率就越高。 方法一的平均码长为： 方法二的平均码长为： 可见 ，本例两种方法的平均码长相同，所以编码效率相同。,5.1 最 佳 变 长 编 码,第24页,2019/10/18,1. 二进制哈夫曼编码,讨论： 码字长度的方差2：长度 ki 与平均码长 之差的平方的数学期望，即： 方法一码字长度方差： 方法二码字长度方差：,哪种方 法更好？,5.1 最 佳 变 长 编 码,第25页,2019/10/18,1. 二进制哈夫曼编码,比较：第二种编码方法的码长方差要小许多。第二种编码方法的码长变化较小，比较接近于平均码长。 第一种方法编出的 5 个码字有

14、 4 种不同的码长； 第二种方法编出的码长只有两种不同的码长； 第二种编码方法更简单、更容易实现，所以更好。 结论：在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。,哈夫曼码是用概率匹配方法进行信源编码。 哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码； 缩减信源的最后二个码字总是最后一位不同，从而保证了哈夫曼码是即时码。,5.1 最 佳 变 长 编 码,第26页,2019/10/18,2. m 进制哈夫曼编码,(1) “全树”概念 定义

15、：码树图中每个中间节点后续的枝数为 m 时称为全树；若有些节点的后续枝数不足 m，就称为非全树。 二进制码不存在非全树的情况，因为后续枝数是 1 时，这个枝就可以去掉使码字长度缩短。 m 进制编码：若所有码字构成全树，可分离的码字数（信源个数）必为 n=m+q(m1)。q为信源缩减次数。 若信源所含的符号数 n 不能构成 m 进制全树，必须增加 s 个不用的码字形成全树。显然 sm1，若 s=m1，意味着某个中间节点之后只有一个分枝，为了节约码长，这一分枝可以省略。,5.1 最 佳 变 长 编 码,第27页,2019/10/18,2. m 进制哈夫曼编码,(1) “全树”概念 在编 m 进制哈

16、夫曼码时为了使平均码长最短，必须使最后一步缩减信源有 m 个信源符号。非全树时，有 s 个码字不用： 第一次对最小概率符号分配码元时就只取 (ms) 个，分别配以 0,1,m-s-1，把这些符号的概率相加作为一个新符号的概率，与其它符号一起重新排列。 以后每次就可以取 m 个符号，分别配以 0,1,m-1；如此下去，直至所有概率相加得 1 为止，即得到各符号的 m 进制码字。,5.1 最 佳 变 长 编 码,第28页,2019/10/18,2. m 进制哈夫曼编码,(2) 举例 对如下单符号离散无记忆信源编三进制哈夫曼码。 已知：m=3，n=8 n=m+q(m1)=8，令 q=3，则 s=9n=98=1 所以第一次取 ms=2 个符号进行编码。,5.1 最 佳 变 长 编 码,第29页,2019/10/18,2. m 进制哈夫曼编码,(2) 举例,5.1 最 佳 变 长 编 码,第30页,