无失真的信源编码.ppt

第8章无失真的信源编码,信源编码主要可分为无失真信源编码和限失真信源编码。无失真信源编码主要适用于离散信源或数字信号，要求进行无失真地数据压缩，要求完全能够无失真地可逆恢复。限失真信源编码主要适用于波形信源或波形信号（即模拟信号），不要求完全可逆地恢复，而是允许在一定限度内可以有失真的压缩。两种信源编码都是为了用较少的码率来传送同样多的信息，增加单位时间内传送的信息量，从而提高通信系统的有效性。,香农信息理论香农第一定理和香农第三定理是信源压缩编码的理论基础，从理论上给出了进行无失真信源压缩和限失真信源压缩的理论极限，还论证与指出了理想最佳信源编码是存在的，但没有给出信源编码实际构造方法和实用码的结构。,本章主要研究无失真信源编码的技术和方法。从第5章香农第一定理已知，信源的信息熵是信源进行无失真编码的理论极限值。总能找到某种合适的编码方法使编码后信源的信息传输率R任意地逼近信源的信息熵而不存在任何失真。在数据压缩技术中无失真信源编码又常被称为熵编码。,从第二章的讨论可知，正是由于信源概率分布的不均匀性，或者信源是有记忆的、具有相关性，使信源中或多或少含有一定的剩余度。只要寻找到去除相关性或者改变概率分布不均匀的方法和手段，就能找到熵编码的具体方法和实用码的结构。,本章首先讨论了典型的霍夫曼编码、游程编码及算术编码的原理和方法。这都是当信源的统计特性已确知时，能达到或接近压缩极限界限的编码方法。前者主要适用于多元独立的信源，后两者主要适用于二元信源及具有一定相关性的有记忆信源。最后讨论了通用编码（又称字典码）的原理和方法。是针对信源的统计特性未确知或不知时所采用的压缩编码方法。本章主要介绍霍夫曼编码。,香农Shannon编码非最佳码,香农码的编码流程：1、将信源符号以概率递减次序排列起来。2、确定满足下列不等式的整数码长3、为编成唯一可译码，计算第i个消息的累加概率：4、将累加概率Pi变换成二进制数。5、取二进制数的小数点后li位即为该消息符号的二进制码字，即为香农码。,8.1霍夫曼（Huffman）码,香农第一定理的证明过程告诉我们一种编码方法，这就是香农编码。但是一般情况下，香农编码的平均码长不是最短，即编出来的不是紧致码（最佳码）。,8.1.1二元霍夫曼码,霍夫曼编码适用于多元独立信源，对于多元独立信源来说它是最佳码。充分利用了信源概率分布的特性进行编码，是一种最佳的逐个符号的编码方法。,二元霍夫曼码的编码步骤,将q个信源符号按概率分布P(si)的大小，以递减次序排列起来，设p1p2p3pq用0和1码符号分别分配给概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个新符号，并用这两个最小概率之和作为新符号的概率，从而得到只包含q-1个符号的新信源，称为S信源的缩减信源S1。,续,把缩减信源S1的符号仍按概率大小以递减次序排列，再将其最后两个概率最小的符号合并成一个新符号，并分别用0和1码符号表示，这样又形成了q-2个符号的缩减信源S2。依次继续下去，直至缩减信源最后只剩下两个符号为止。将这两个符号分别用0和1码符号表示。最后这两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径由后向前返回，就得出个信源符号所对应得码符号序列，即得对应得码字了。,霍夫曼编码的选择,霍夫曼编码方法得到的码并非是唯一的。对于平均码长相等的霍夫曼码可以通过引进码字长度偏离平均长度的方差选择判断。在霍夫曼编码过程中，当缩减信源的概率分布重新排列时，应使合并得来的概率和尽量处于最高的位置，这样可以使得合并的元素重复编码次数减少，使短码得到充分利用。,二元霍夫曼码的特点,霍夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，即pjpk，ljlk，而且短码得到充分利用。每次缩减信源的最后两个码字总是最后一位码元不同，前面各位码元相同（二元编码情况）如表8.1和8.2所示。每次缩减信源的最长两个码字有相同的码长这三个特点保证了所得到的霍夫曼码一定是最佳码。,霍夫曼码的推广和最佳性,二元霍夫曼码的编码方法同样可以推广到r元编码中去。不同的只是每次把r个符号（概率最小的）合并成一个新的信源符号，并分别用0,1,(r-1)等码元表示。霍夫曼码是最佳码（紧致码）。所谓最佳性，就是指对于某个给定信源，在所有可能的唯一可译码中，此码的平均码长为最短。并称此码为最佳码或紧致码。,8.2费诺（Fano）码,费诺编码方法属于概率匹配编码，这种编码方法稍不同于前述的霍夫曼编码法，它不是最佳的编码方法，但有时也可得到最佳码的性能。,二元费诺码的编码步骤,首先，将信源符号以概率递减的次序排列起来，将排列好的信源符号划分成两大组，使每组的概率和近于相同，并各赋予一个二元码符号“0”和“1”。然后，将每一大组的信源符号再分成两组，使同一组的两个小组的概率和近于相同，并又分别赋予一个二元码符号。依次下去，直至每个小组只剩下一个信源符号为止。最后，由前向后（从左向右）读取码符号序列（注意：读取码字与霍夫曼编码不同）。这样，信源符号所对应的码符号序列则为编得的码字。,续,费诺码的编码方法实际上是构造码树的一种方法，所以费诺码是即时码。费诺码也考虑了信源的统计特性，使经常出现的信源符号能对应码长短的码字。费诺码仍然是一种相当好的编码方法。费诺编码方法同样适合于r元编码，只需每次分成r组即可。,三种编码方式的比较,只有霍夫曼码必定是最佳码，霍夫曼码的平均码长最小，信息传输率最大，编码效率最高，但在实际使用时其设备较为复杂。费诺码有时也能达到最佳码的性质。香农码的编码效率较以上两者要差一些。对于以上三种编码有：,8.3香农费诺埃利斯码,香农费诺埃利斯码是采用信源符号的累积分布函数来分配码字虽然香农费诺埃利斯码不是最佳码，但由它拓宽可得到一种算数码。该算数码是一种非分组码，其编码和译码都是计算效率高的码。,本章小结,讨论了基于熵概念的无损压缩编码及其各种压缩编码。这些方法在实际工程技术中得到广泛的应用，如现在所用的各种图像格式，除BMP文件外，都用到这些无损压缩编码算法。又如广为人知的MP3、MP4音乐压缩格式