信息论-第四章·第七节-霍夫曼码与其他编码方法

信息论--第四章·第七节霍夫曼码与其他编码方法高中的第一次考试已经过去一周多了，我一直都觉得我的成绩已经算不错了，毕竟在级部里提升了一百多名，但今晚的一个朋友圈，竟成了一个对我的当头棒喝。发朋友圈的是我爸的一个要好的朋友，他的女儿和我一级，但并不在一个学校。朋友圈的内容是两张荣誉证书。一张是进步之星，一张是书法的一等奖。后面还写着在级部里提升了500多名，看着下面评论区的喝彩与夸赞，再想想中考时我俩只差一分的成绩，我竟还在此之前暗暗骄傲，因这被我打败的一百来人。以前，我或许并不努力与谦虚，但今天的这盆冷水终于把我彻底地浇醒了。我以后，绝不会自欺欺人的把微小的进步当做是我努力的成果。我绝不能把自己的梦想还没开始就扔进深渊，认真起来吧，我这懒惰之徒。信息论--第四章·第七节霍夫曼码与其他编码方法信息论--第四章·第七节霍夫曼码与其他编码方法高中的第一次考试已经过去一周多了，我一直都觉得我的成绩已经算不错了，毕竟在级部里提升了一百多名，但今晚的一个朋友圈，竟成了一个对我的当头棒喝。发朋友圈的是我爸的一个要好的朋友，他的女儿和我一级，但并不在一个学校。朋友圈的内容是两张荣誉证书。一张是进步之星，一张是书法的一等奖。后面还写着在级部里提升了500多名，看着下面评论区的喝彩与夸赞，再想想中考时我俩只差一分的成绩，我竟还在此之前暗暗骄傲，因这被我打败的一百来人。以前，我或许并不努力与谦虚，但今天的这盆冷水终于把我彻底地浇醒了。我以后，绝不会自欺欺人的把微小的进步当做是我努力的成果。我绝不能把自己的梦想还没开始就扔进深渊，认真起来吧，我这懒惰之徒。教学要求了解Shannon编码思想、Shannon-Fano算法、香农-费诺-埃里斯编码算法；掌握Huffman编码方法。教学要求了解Shannon编码思想、Shannon-Fano算法、香农-费诺-埃里斯编码算法；掌握Huffman编码方法。Shannon算法Shannon编码思想：按概率编码它是满足Kraft不等式的一种直接的应用

例：一个离散信源S:{s1,s2,s3,s4}p(S):{1/2,1/4,1/8,1/8}这时有：L1=log2=1;L2=log4=2;L3=L4=log8=3;4.7霍夫曼码和其他编码方法Shannon编码举例利用码树图法可得到其编码这个例子其编码效率为1，即为最佳码。但这种方法对于多数情况下是不能实现最佳码的，而且编码效率比较低。

4.7霍夫曼码和其他编码方法L1=1,L2=2,L3=L4=3;Huffman码将信源符号按概率从大到小的顺序排列，令给两个概率最小的信源符号sn-1和sn各分配一个码元“0”和“1”，并将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含(n－1)个信源符号的新信源。称为信源的第一次缩减信源，用S1表示。将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤2，得到只含(n－2)个符号的缩减信源S2。重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。编码步骤如下：4.7霍夫曼码和其他编码方法01010101Huffman码4.7霍夫曼码和其他编码方法Huffman码离散信源如下:解：编码过程略，Huffman编码结果如下：4.7霍夫曼码和其他编码方法Huffman码平均码长为信源熵为编码效率为4.7霍夫曼码和其他编码方法Huffman码注意：霍夫曼编码后的码字不是惟一的。1）每次对缩减信源两个概率最小的符号分配“0”或“1”码元是任意的,因此编码的结果是不唯一的；但0/1分配的上下顺序在整个编码过程中应保持一致，否则不能构成唯一可译码。2）缩减信源时，若合并后的概率与其他概率相等，这几个概率的次序可任意排列，但得到的码字不相同,对应的码长也不相同,但平均码长也不变。4.7霍夫曼码和其他编码方法Huffman码的特点用概率匹配方法进行编码概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码缩减信源的最后两个码字总是最后一位不同，从而保证了Huffman码是即时码定理4.10

霍夫曼码是紧致码r元Huffman算法

r=3,A:{0,1,2}可知：平均码长为L=2码元/信源符号改进方法在6个信源符号的后面再加一个概率为0的符号，记为s7’,同时有p(s7’)=0，这个符号称为虚假符号。将信源按7个符号进行三元编码012012012改进方法4.7霍夫曼码和其他编码方法其码树图计算得平均码长为L=1.76码元/信源符号。因此通过增加虚假符号的方法可以提高r元Huffman编码的编码效率。改进的r元Huffman编码对于离散信源S:{s1,s2,…,sq}P(S):{p(s1),p(s2),……p(sq)}A;{a1,a2,…ar};第一次缩减信源S(1)，每次将减少(r-1)个符号，分别形成S(2),S(3)…如果i=r-{q-[r-1]}！＝０,其中表示缩减次数,应当在原始信源中加上m个概率为0的虚假信源符号，然后进行编码，将得到最佳码。上例，q=6,r=3,=2r元霍夫曼码4.7霍夫曼码和其他编码方法r元霍夫曼码4.7霍夫曼码和其他编码方法Fano码编码步骤如下：将概率按从大到小的顺序排列，令将依次排列的信源符号按概率分成两组，使每组概率和尽可能接近或相等。给每一组分配一位码元“0”或“1”。将每一分组再按同样方法划分，重复步骤2和3，直至概率不再可分为止。4.7霍夫曼码和其他编码方法Fano码例4.7霍夫曼码和其他编码方法Fano码解：信源符号符号概率第一次分组第二次分组第三次分组第四次分组码字码长0.20000020.191001030.18101130.17101020.151011030.1010111040.011111144.7霍夫曼码和其他编码方法Fano码平均码长为信源熵为编码效率为4.7霍夫曼码和其他编码方法Fano编码举例4.7霍夫曼码和其他编码方法Fano编码举例平均码长为L=2.64信道码元/信源符号。H(S)=2.55bit/信源符号。

本例中费诺编码有较高的编码效率。费诺码比较适合于每次分组概率都很接近的信源。特别是对每次分组概率都相等的信源进行编码时，可达到理想的编码效率。如果将信源做n次扩展后再进行编码，可以进一步提高编码效率4.7霍夫曼码和其他编码方法第五章：无失真信源编码香农-费诺-埃利斯编码编码步骤如下：将信源符号按概率从大到小顺序排列，为方便起见，令2.按下式计算第i个符号对应的码字的码长（要取整）3.计算第i个符号的累加概率4.将累加概率变换成二进制小数，取小数点后li位数作为第i个符号的码字。例对如下信源编码:第五章：无失真信源编码香农-费诺-埃利斯编码信源符号符号概率累加概率码长码字s10.2002.343000s20.190.22.413001s30.180.392.483011s40.170.572.563100s50.150.742.743101s60.100.593.3441110s70.010.996.6671111110第五章：无失真信源编码香农-费诺-埃利斯编码平均码长信源熵结论：1)2)香农-费诺-埃利斯编码是即时码，但冗余度稍大，不是最佳码。编码效率第五章：无失真信源编码香农-费诺-埃利斯编码香农码、Huffman码、Fano码总结香农码、费诺码、霍夫曼码都考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现了对信源的压缩。香农码编码结果唯一，但在很多情况下编码效率不是很高。费诺码和霍夫曼码的编码方法都不唯一。费诺码比较适合于对分组概率相等或接近的信源编码。霍夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的要求也比较简单，因此综合性能优于香农码和费诺码。4.7霍夫曼码和其他编码方法首先是速率匹配问题其次是差错扩散问题第三是霍夫曼码