1 5.2.3 最佳变长编码

5.2.3最佳变长编码最佳码：对于某一信源和某一码符号集来说,若有一唯一可译码,其平均码长小于所有其他唯一可译码的平均长度。最佳变长编码:凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合称为最佳变长码。紧致码香农（Shannon）费诺（Fano）哈夫曼（Huffman）香农编码香农第一定理指出了平均码长与信源之间的关系,同时也指出了可以通过编码使平均码长达到极限值,这是一个很重要的极限定理。香农第一定理指出,选择每个码字的长度Ki满足下式：或:－log2p(xi)≤Ki<1－log2p(xi)就可以得到这种码。这种编码方法称为香农编码取整二进制香农码的编码步骤如下：⑴将信源符号按概率从大到小的顺序排列,　　　　p(a1)≥p(a2)≥…≥p(an)⑵确定满足下列不等式的整数Ki,－log2p(ai)≤Ki<1－log2p(ai)⑶令P(a1)=0,用Pi 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示第i个码字的累加概率，香农编码⑷将Pi用二进制表示,并取小数点后Ki位作为符号ai的编码。例有一单符号离散无记忆信源对该信源编二进制香农码。其编码过程如表所示以i=3为例:码字长度：K3=[－log0.2]=3累加概率Pi=0.70→0.10110…00011011110011101这些码字没有占满所有树叶,所以是非最佳码信源符号xi符号概率p(xi)累加概率Pi-logp(xi)码长码字x10.401.32200x20.30.41.73201x30.20.72.323101x40.050.94.3511100x50.050.954.3511101香农码的平均码长熵编码效率为提高编码效率,首先应达到满树;如把x4x5换成前面的节点,可减小平均码长。不应先 规定 关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定 码长,而是由码树来规定码字,可得更好的结果。x1x2x5x3x4费诺编码费诺编码属于概率匹配编码。编码步骤如下：将概率按从大到小的顺序排列,令p(x1)≥p(x2)≥…≥p(xn)按编码进制数将概率分组,使每组概率尽可能接近或相等。如编二进制码就分成两组,编m进制码就分成m组。给每一组分配一位码元。将每一分组再按同样原则划分,重复步骤2和3,直至概率不再可分为止。信源符号xi符号概率p(xi)第1次分组第2次分组第3次分组码字码长x10.400002x40.05100103x50.0510113x20.310102x30.21112例设有一单符号离散信源对该信源编二进制费诺码。信源符号xi符号概率p(xi)第1分组第2分组第3分组第4分组码字码长x10.4001x20.310102x30.2101103x40.051011104x50.05111114平均码长：K=2.1编码效率:η=93%平均码长：K=2.0编码效率:η=97.5%平均码长编码效率费诺码比较适合于每次分组概率都很接近的信源特别是对每次分组概率都相等的信源进行编码时,可达到理想的编码效率。例有一单符号离散无记忆信源对该信源编二进制费诺码,编码过程如表:信源熵为H(X)=2.75(比特/符号)平均码长为编码效率为η=1之所以如此,因为每次所分两组的概率恰好相等。哈夫曼编码哈夫曼编码也是用码树来分配各符号的码字。费诺码是从树根开始,把各节点分给某子集,若子集已是单点集,它就是一片树叶而作为码字。哈夫曼编码是先给每一符号一片树叶,逐步合并成节点直到树根。哈夫曼(Huffman)编码是一种效率比较高的变长无失真信源编码方法。哈夫曼编码的步骤如下：⑴将信源消息符号按其出现的概率大小依次排列p(x1)≥p(x2)≥…≥p(xn)⑵取两个概率最小的字母分别配以0和1两码元,并将这两个概率相加作为一个新字母的概率,与未分配的二进符号的字母重新排队。⑶对重排后的两个概率最小符号重复步骤⑵的过程。⑷不断继续上述过程,直到最后两个符号配以0和1为止。⑸从最后一级开始,向前返回得到各个信源符号所对应的码元序列,即相应的码字。例5-7设单符号离散无记忆信源如下,要求对信源编二进制哈夫曼码。编码过程如下表信源符号xi符号概率p(xi)编码过程x10.20x20.19x30.18x40.17x50.15x60.10x70.01010.200.190.180.170.150.11010.260.200.190.180.17010.350.260.200.19010.390.350.26010.610.3901码字101100000101001100111在图中读取码字的时候,要从后向前读,此时编出来的码字是可分离的异前置码。熵平均码长为编码效率哈夫曼的编法并不唯一。每次对缩减信源两个概率最小的符号分配“0”和“1”码元是任意的,所以可得到不同的码字。只要在各次缩减信源中保持码元分配的一致性,即能得到可分离码字。不同的码元分配,得到的具体码字不同,但码长Ki不变,平均码长也不变,所以没有本质区别；缩减信源时,若合并后的新符号概率与其他符号概率相等,从编码方法上来说,这几个符号的次序可任意排列,编出的码都是正确的,但得到的码字不相同。不同的编法得到的码字长度Ki也不尽相同。哈夫曼编码例5-8单符号离散无记忆信源信源符号xi符号概率p(xi)编码过程x10.4x20.2x30.2x40.1x50.1010.40.20.20.2010.40.40.2010.60.401码字10100000100011码字001011010011单符号信源编二进制哈夫曼码,编码效率主要决定于信源熵和平均码长之比。对相同的信源编码,其熵是一样的,采用不同的编法,得到的平均码长可能不同。平均码长越短,编码效率就越高。编法一的平均码长为编法二的平均码长为两种编法的平均码长相同,所以编码效率相同。讨论：哪种方法更好？定义码字长度的方差σ2：第二种编码方法的码长方差要小许多。第二种编码方法的码长变化较小,比较接近于平均码长。哈夫曼编码哈夫曼编码第一种方法编出的5个码字有4种不同的码长；第二种方法编出的码长只有两种不同的码长；第二种编码方法更简单、更容易实现,所以更好。结论：在哈夫曼编码过程中,对缩减信源符号按概率由大到小的顺序重新排列时,应使合并后的新符号尽可能排在靠前的位置,这样可使合并后的新符号重复编码次数减少,使短码得到充分利用。哈夫曼码是用概率匹配方法进行信源编码。哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码；缩减信源的最后二个码字总是最后一位不同，从而保证了哈夫曼码是即时码。r进制哈夫曼编码在编r进制哈夫曼码时为了使平均码长最短,必须使最后一步缩减信源有r个信源符号。对于r进制编码,若所有码字构成全树,可分离的码字数必为:m=r＋k(r－l)非全树时,有s个码字不用：s=m-n第一次对最小概率符号分配码元时只取(r－s)个,分别配以0,1,…,r-s-1,把这些符号的概率相加作为一个新符号的概率,与其它符号一起重新排列以后每次取r个符号,分别配以0,1,…,r-1；如此下去,直至所有概率相加得1为止,即得到各符号的r进制码字。例:对如下单符号离散无记忆信源编三进制哈夫曼码这里：r=3，n=8令k=3，r+k(r－1)=9，则s=9－n=9－8=1所以第一次取r－s=2个符号进行编码。3进制哈夫曼编码信源符号xi符号概率p(xi)编码过程x10.40x20.18x30.10x40.10x50.07x60.06x70.05x80.04010120.400.180.100.100.090.070.060.400.220.180.100.100120.400.380.22012码字01011122122200201结论香农码、费诺码、哈夫曼码都考虑了信源的统计特性,使经常出现的信源符号对应较短的码字,使信源的平均码长缩短,从而实现了对信源的压缩；香农码有系统的、唯一的编码方法,但在很多情况下编码效率不是很高；费诺码和哈夫曼码的编码方法都不唯一；费诺码比较适合于对分组概率相等或接近的信源编码,费诺码也可以编r进制码,但r越大,信源的符号数越多,可能的编码 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 就越多,编码过程就越复杂,有时短码未必能得到充分利用；哈夫曼码对信源的统计特性没有特殊要求,编码效率比较高,对编码设备的要求也比较简单,因此综合性能优于香农码和费诺码。