无失真的信源编码.pps

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