《无失真信源编码》PPT课件.ppt

《《无失真信源编码》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§2.8无失真信源编码(二)五、编码的一般原则六、范诺(Fano)编码七、霍夫曼(Huffman)编码八、N次扩展编码五、编码的一般原则1.等概化使编码后各个码元出现的概率尽可能地相等。2.减少平均码长将概率大的消息编成短码，概率小的消息编成长码。3.消息合并将两个或者两个以上的消息编成一个码字。目的去相关性；减少平均码长。六、范诺(Fano)编码1.方法及步骤(1)将消息符号按其概率从大到小排列。(2)将排列好消息符号分为概率尽可能相等的两组，(3)将每次所分的两组中前一组编为0，前一组编为1。(4)按顺序写出码字。每个组只剩下一个消息符号为止。对每组直至的消息符

2、号再分为概率尽可能相等的两组，……，码字00111111010011110100110101码长22334444ABCDEFGHX44221111p(x)解1/4B1/8C1/8D1/4A1/16E1/16p(x)FX求其范诺编码及编码效率。例设消息的概率分布如下，1/16G1/16H编码效率平均码长熵(bit),解码树图生成过程GHABCDEF01010101010101从上到下生成1/4B1/8C1/8D1/4A1/16E1/16p(x)FX求其范诺编码及编码效率。例设消息的概率分布如下，1/16G1/16H码字00111101011101101码长222344

3、ABCDEFX3222181684p(x)解0.22B0.18C0.16D0.32A0.08E0.04p(x)FX求其范诺编码及编码效率。例设消息的概率分布如下，编码效率平均码长熵(bit),解码树图生成过程EFAB0101010101从上到下生成0.22B0.18C0.16D0.32A0.08E0.04p(x)FX求其范诺编码及编码效率。例设消息的概率分布如下，CD码字0001111101101111010111011码长23323455ABCDEFGHX熵解编码效率平均码长范诺编码有时会出现0.20B0.16C0.15D0.21A0.14E0.08p(x)FX求

4、其范诺编码及编码效率。例设消息的概率分布如下，0.03G0.03H概率相对较小的消息其码长反而较短。2120161514833p(x)012.分组问题的探讨六、范诺(Fano)编码通常情况下，不能保证使所分的两组的概率完全相等，此时就会出现两种不同的分组方案。比如：ABCDEFGH下面通过几个例子来探讨一下范诺编码分组问题，从而能发现范诺编码的主要不足之处。码字0011111101001111010111011码长22333455ABCDEFGHX2816121111115.55.5p(x)熵解一0.055H0.16B0.12C0.11D0.28A0.11E0.11

5、p(x)FX求其范诺编码及编码效率。例设消息的概率分布如下，0.055G编码效率平均码长0.440.56010.560.44解一0.055HABCDEFGH2816121111115.55.5p(x)码字0001111101100111010101101码长23333344X0.16B0.12C0.11D0.28A0.11E0.11p(x)FX求其范诺编码及编码效率。解二例设消息的概率分布如下，0.055G熵编码效率平均码长0.560.44熵编码效率平均码长0.58码字00011110110011010101码长2333333ABCDEFGX熵解一0.18B0.18

6、C0.14D0.22A0.14E0.10p(x)FX求其范诺编码及编码效率。例设消息的概率分布如下，0.04G编码效率平均码长0.422218181414104p(x)解一0.58ABCDEFG2218181414104p(x)码字001111101001110101101码长2233344X熵编码效率平均码长解二0.18B0.18C0.14D0.22A0.14E0.10p(x)FX求其范诺编码及编码效率。例设消息的概率分布如下，0.04G0.420.400.60熵编码效率平均码长(1)在构造码树时，从根节点开始到端节点结束。(2)编出的码字不是唯一的。(3)有时出

7、现概率较小的消息其码长反而较短。3.范诺编码的特点小结六、范诺(Fano)编码(4)如何“恰当”分组是范诺编码的主要问题。都只能保证当前步的概率尽可能均匀化(局部最优)，但不能保证总体最优。每一步分组七、霍夫曼(Huffman)编码思想就是使各符号的概率均匀化，即概率大的消息符号编成短码，概率小的消息符号编成长码。当时霍夫曼还只是麻省理工学院(MIT)的一名研究生。霍夫曼编码是戴维霍夫曼(DavidHuffman)在1952年.他从来没有为他的工作申请专利，他所得到的补偿仅是不必参加信息论课程的考试。了大量的美元。霍夫曼编码已经广泛地应用于计算机科学、数据通讯等