2.8无失真信源编码.ppt
2.8 无失真信源编码(二),五、编码的一般原则,1.等概化,使编码后各个码元出现的概率尽可能地相等。,2.减少平均码长,将概率大的消息编成短码，概率小的消息编成长码。,3.消息合并,将两个或者两个以上的消息编成一个码字。,目的,去相关性；,减少平均码长。,六、范诺(Fano)编码,1.方法及步骤,(1)将消息符号按其概率从大到小排列。,(2)将排列好消息符号分为概率尽可能相等的两组，,(3)将每次所分的两组中前一组编为0，前一组编为1。,(4)按顺序写出码字。,每个组只剩下一个消息符号为止。,对每组,直至,码字,00111111,01001111,010011,0101,解,编码效率,平均码长,熵,(bi t),解,码树图生成过程,码字,001111,010111,011,01,解,编码效率,平均码长,解,码树图生成过程,码字,00011111,01101111,010111,011,熵,解,编码效率,平均码长,范诺编码有时会出现,概率相对较小的消息,其码长反而较短。,01,2.分组问题的探讨,六、范诺(Fano)编码,通常情况下，不能保证使所分的两组的概率完全相等，,此时就会出现两种不同的分组方案。,下面通过几个例子来探讨一下范诺编码分组问题，,从而能发现范诺编码的主要不足之处。,码字,00111111,01001111,010111,011,熵,解一,编码效率,平均码长,01,0.56,0.44,解一,0.055,H,ABCDEFGH,2816121111115.55.5,p(x),码字,00011111,01100111,0101011,01,X,0.16,B,0.12,C,0.11,D,0.28,A,0.11,E,0.11,p(x),F,X,求其范诺编码及编码效率。,解二,例,设消息的概率分布如下，,0.055,G,熵,编码效率,平均码长,码字,0001111,0110011,010101,熵,解一,编码效率,平均码长,解一,0.58,ABCDEFG,2218181414104,p(x),码字,0011111,0100111,01011,01,X,熵,编码效率,平均码长,解二,0.42,熵,编码效率,平均码长,(1)在构造码树时，从根节点开始到端节点结束。,(2)编出的码字不是唯一的。,(3)有时出现概率较小的消息其码长反而较短。,3.范诺编码的特点小结,六、范诺(Fano)编码,(4)如何“恰当”分组是范诺编码的主要问题。,都只能保证当前步的概率尽可能均匀化(局部最优)，,但不能保证总体最优。,每一步分组,七、霍夫曼(Huffman)编码,思想就是使各符号的概率均匀化，即概率大的消息符号编成,短码，概率小的消息符号编成长码。,当时霍夫曼还只是麻省理工学院(M I T)的一名研究生。,他从来没有为他的工作申请专利，他所得到的补偿仅是不必,参加信息论课程的考试。,了大量的美元。,霍夫曼编码已经广泛地应用于计算机科学、数据通讯等,提出的一种变长编码方法，它是一种最佳编码方法。,许多科学与应用领域中。,其基本,而其他人已经借助霍夫曼编码赚到,七、霍夫曼(Huffman)编码,(2)把概率最小的两个消息分别编成“1”和“0”码元，,(3)把上述概率和作为一个新消息的概率，再与剩余的其它,1.方法及步骤,(1)将消息符号按概率从大到小排列。,到最右边,将遇到的二元数字依次由最低位写到最高位，,所得到的二元数字序列即为各个消息的最佳二元编码。,它们的概率和。,消息按概率从大到小重新排列。,(5)从最左边开始，沿着以每个消息为出发点的路线一直走,(4)重复步骤(2)与(3)，直到所有概率都处理完为止。,并求,解,ABCDEFGH,212016151486,212016151414,2821201615,31282120,413128,5941,100,熵,平均码长,编码效率,码字,A B C D E F G H,10 11 000 001 010 0110 01110 01111,0.20,B,0.16,C,0.15,D,0.21,A,0.14,E,0.08,p(x),F,X,求其霍夫曼编码及编码效率。,例,设消息的概率分布如下，,0.03,G,0.03,H,解,码树图生成过程,解,4422211,442222,44422,4444,844,88,16,熵,平均码长,编码效率,码字,A B C D E F G H,10 11 010 011 0000 0001 0010 0011,解,码树图生成过程,4,B,2,C,2,D,4,A,1,E,1,p(x),F,X,求其霍夫曼编码及编码效率。,例,设消息的概率分布如下，,1,G,1,H,七、霍夫曼(Huffman)编码,2.码方差较小原则,在每次对两个最小的概率求和后，把这个新概率列入,其它尚未处理过的概率中重新由大到小排序时，,可以排在相同概率的后面，,前者编出来的码字中个别码字会相对较长；,减少了码树的深度(或级数)，因此编出来的码字中各码字,的码长会相对均匀，,新概率既,也可以排在相同概率的前面。,后者由于,从而能可获得较小的码方差。,解,熵,平均码长,编码效率,码字,4222,442,64,10,码方差,方法一,10,熵,平均码长,编码效率,码字,4222,442,64,码方差,方法二,码树图对比,方法一,方法二,七、霍夫曼(Huffman)编码,(1)在构造码树时，从端节点开始到根节点结束。,3.霍夫曼编码的特点小结,(2)编出的码字不是唯一的。,(3)能保证概率较小的消息其码长较长。,(4)在每次对两个最小的概率求和后，新的概率一般要排在,相同概率的前面，从而能可获得较小的码方差。,八、消息合并编码,消息对应到一个码字，,为合并法或延长法。,求出每对消息出现的概率，,设每对消息编码后的平均码长为,编码效率,其中,即每 N 个,此方法称为 N 次扩展，,也称,并对其进行编码。,则,平均码长,编码效率,信源熵,解,(2)采用两次扩展的范诺编码,码字,0111,011,01,每对消息的平均码长,编码效率,单个消息的平均码长,解,(3)采用三次扩展的范诺编码,0101,码字,01111111,0011111,0101111,0011,单个消息的平均码长,编码效率,每三个消息的平均码长,无条件熵,可得实际熵(即条件熵)为,解,平均码长,(1)对单个消息直接进行编码,编码效率,码字,011,01,(2)采用两次扩展的范诺编码,先求出每对消息出现的概率：,(2)采用两次扩展的范诺编码,每对消息的平均码长,单个消息的平均码长,码字,0001111,0110111,01011,01,解,编码效率,变长码的平均码长比等长码短，故编码效率较高，,差异有时还会非常大。,等长码虽然编码效率较差，但是它能保证消息符号的,输入、编码以及输出同步进行。,其中某些符号的码长肯定会比等长码长；码字之间的长度,码字长度的差异。,但,因此需要有大量的存储设备来缓冲,从 1 到 10 不等。,例如，设每秒钟输入一个信源符号，输出码字的长度,若希望平均每秒输出 个码元，就,出，从而使输出和输入保持平衡。,当存储器容量容量不够大时，可能有时取空，有时又,溢出。,由于具有较小的码方差的码字集合中各个码字的码长,会相对均匀，因而使该问题变得相对容易一些。,必须每次先把若干个编好的码字存储起来，再按速率 输,较关键的一个问题。,(解码播放与此类似),因此如何对所需存储器的容量进行适当估计，成为,
