信息论与编码第4无失真信源编码.pptVIP

4.3.1编码空间实际上它是一个相对量，是指一个编码占用的可以使用的编码的比例，考虑异前缀编码，显然一个二进制的编码，如果将0作为码字，所有以0开头的编码都不能再用，则有一半的编码将不能继续作为码字，如果是两位，则有四分之一的码字不能使用，对于十进制，一个一位的十进制占用的比例为十分之一，依此，一个n位的k进制占用的编码空间为1/kn，当占用的编码空间小于等于1的时候，异前缀码是可能存在的，如果大于1，则不可能存在。香农第一定理指出，选择每个码字的长度Ki满足下式的整数：0102logmpi≤Ki＜1－logmpi03例4-4设无记忆信源的概率空间为：4.3.2香农码4.3.2香农码以二进制编码为例，香农编码方法如下：将信源消息符号按其出现的概率大小依次排列p(u1)≥p(u2)≥…≥p(un)确定码长Ki(整数)：Mi=[]——取整；Ki=Mi+1,如果Mi是小数；Ki=Mi,如果Mi是整数为了编成唯一可译码，计算第i个消息的累加概率将累加概率Pi变换成二进制数。取pi二进制数的小数点后Ki位即为该消息符号的二进制数。例4-5对信源进行香农编码。4.3.2香农码4.3.2香农码4.3.2香农码以i=3为例，计算各符号的码字长度：K3=[－log0.2]=3累加概率P4=0.7——0.10110…——1014.3.2香农码STEP4STEP3STEP2STEP1香农编码给予你什么启示？香农编码中如何保证编码是异前缀的？香农编码何时可以达到无损压缩的理论极限？考虑有记忆和无记忆信源序列概率（概率和条件概率）分布具有平稳性，对单个符号进行本编码和对序列进行编码，编码的效率相比较如何？4.3.2香农码4.3.3费诺码费诺码属于概率匹配编码，又称为香农-费诺码（Shannon-Fano编码），但它一般也不是最佳的编码方法。编码过程如下： (1)信源符号以概率递减的次序排列起来; (2)将排列好的信源符号按概率值划分成两大组，使每组的概率之和接近于相等，并对每组各赋予一个二元码符号0和1; (3)将每一大组的信源符号再分成两组，使划分后的两个组的概率之和接近于相等，再分别赋予一个二元码符号; (4)依次下去，直至每个小组只剩一个信源符号为止; (5)信源符号所对应的码字即为费诺码。4.3.3费诺码例4-6对信源进行费诺编码表4-2是忽略了排序过程的编码，4-3排序。4.3.3费诺码费诺码具有如下的性质：费诺码的编码方法实际上是一种构造码树的方法，所以费诺码是即时码。01费诺码考虑了信源的统计特性，使概率大的信源符号能对应码长较短的码字，从而有效地提高了编码效率。02费诺码不一定是最佳码。034.3.4哈夫曼码哈夫曼编码的步骤如下：⑴统计信源消息符号的概率，将信源消息符号按其出现的概率大小依次排列p(u1)≥p(u2)≥…≥p(un)⑵取两个概率最小的字母分别配以0和1两码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进符号的字母重新排队，合并后的信源称为缩减信源。⑶对重排后的两个概率最小符号重复步骤⑵的过程。⑷不断继续上述过程，直到最后两个符号配以0和1为止。⑸从最后一级开始，逆向向前返回得到各个信源符号所对应的码元序列，即相应的码字。*前面的章节中，我们对信息问题从理论的角度进行了一些度量和分析。从本章开始，我们将讨论在信息论的基础上进行各种编码。本章主要介绍编码的基本概念，信源编码的基本思路与主要方法，以无失真、统计编码为主，期望通过本章学习能建立起信源压缩编码的基本概念。学习得来终觉浅，绝知此事要自悟第4章无失真信源编码在不失真或允许一定失真条件下，如何提高信息传输速度，这种编码称为信源编码。根据是否允许失真，信源编码又可以分为无失真信源编码（当失真可以逼近于0时，在信息论中也当做无失真编码讨论）和限失真信源编码。在信道受到干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息的有效传输率最大，达到这种目的的编码称为信道编码。它是为了对抗信道中的噪音和衰减，通过增加冗余，如校验码等，来提高抗干扰能力以及纠错能力。第4章编码类型第4章编码类型在可以监听的信道上如何进行安全的通信，使得在信道上监听的人也无法获取消息，需要进行加密。对应的加密转换方法称为加密编码。4.1编码器和相关概念为了分析方便和突出问题的重点，当研究信源编码时，我们把信道编码和译码看成是信道的一部分，从而突出信源编码。同样，在研究信道编码时，可以将信源编码和译码看成是信源和信宿的一部分，从而突出信道编码。对于加密编码