《信息论第四章第七节霍夫曼码与其他编码方法ppt课件》由会员分享,可在线阅读,更多相关《信息论第四章第七节霍夫曼码与其他编码方法ppt课件(34页珍藏版)》请在金锄头文库上搜索。
1、4.7 霍夫曼码和其他编码方法霍夫曼码和其他编码方法第第4章章 无失真信源编码无失真信源编码教学要求教学要求 了解了解Shannon编码思想、编码思想、Shannon-Fano算法、香农算法、香农-费诺费诺-埃里斯编码算法;埃里斯编码算法;掌握掌握Huffman编码方法。编码方法。 Shannon算法算法 Shannon编码思想编码思想 :按概率编码:按概率编码 它是满足它是满足KraftKraft不等式的一种直接的应用不等式的一种直接的应用 例:一个离散信源例:一个离散信源S:s1,s2,s3,s4 S:s1,s2,s3,s4 p(S):1/2,1/4,1/8,1/8p(S):1/2,1/4
2、,1/8,1/8这时有:这时有:L1=log2=1; L2=log4=2; L1=log2=1; L2=log4=2; L3=L4=log8=3;L3=L4=log8=3;4.74.7霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法Shannon编码举例编码举例利用码树图法可得到其编码利用码树图法可得到其编码这个例子其编码效率为这个例子其编码效率为1,即为最佳码。但这种,即为最佳码。但这种方法对于多数情况下是不能实现最佳码的,而且方法对于多数情况下是不能实现最佳码的,而且编码效率比较低。编码效率比较低。 4.74.7霍夫曼码和其他编码方法霍夫曼码和其他编
3、码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法L1=1, L2=2, L3=L4=3;Huffman码码1.将信源符号按概率从大到小的顺序排列,令将信源符号按概率从大到小的顺序排列,令2.给两个概率最小的信源符号给两个概率最小的信源符号sn-1和和sn各分配一个码元各分配一个码元“0和和“1”,并将,并将这两个信源符号合并成一个新符号,并用这两个最小的概率之和作为新符这两个信源符号合并成一个新符号,并用这两个最小的概率之和作为新符号的概率,结果得到一个只包含号的概率,结果得到一个只包含(n1)个信源符号的新信源。称为信源的个信源符号的新信源。称为信源的第一次缩减信源,用第一次缩减信源,用S
4、1表示。表示。3.将缩减信源将缩减信源S1的符号仍按概率从大到小顺序排列,重复步骤的符号仍按概率从大到小顺序排列,重复步骤2,得到只含,得到只含(n2)个符号的缩减信源个符号的缩减信源S2。4.重复上述步骤,直至缩减信源只剩两个符号为止,此时所剩两个符号的概重复上述步骤,直至缩减信源只剩两个符号为止,此时所剩两个符号的概率之和必为率之和必为1。然后从最后一级缩减信源开始,依编码路径向前返回,就。然后从最后一级缩减信源开始,依编码路径向前返回,就得到各信源符号所对应的码字。得到各信源符号所对应的码字。编码步骤如下:编码步骤如下:4.74.7霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其
5、他编码方法霍夫曼码和其他编码方法01010101Huffman码4.74.7霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法01010101码符号/信源符号Huffman码4.74.7霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法01010101码符号/信源符号Huffman码4.74.7霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法讨论:讨论:1) 两种方法平均码长相等。两种方法平均码长相等。2) 计算两种码的码长方差:计算两种码的码长方差:第二种方法编出的码码字长度变
6、化较小,便于实现。第二种方法编出的码码字长度变化较小,便于实现。Huffman码码4.74.7霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法Huffman码码离散信源如下离散信源如下:解:编码过程略,解:编码过程略,Huffman编码结果如下:编码结果如下:4.74.7霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法Huffman码l平均码长为平均码长为l信源熵为信源熵为l编码效率为编码效率为4.74.7霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法Huffman码留意:
7、霍夫曼编码后的码字不是惟一的。留意:霍夫曼编码后的码字不是惟一的。1每次对缩减信源两个概率最小的符号分配每次对缩减信源两个概率最小的符号分配“0或或“1码元是任意的码元是任意的,因此编码的结果是不唯一的;但因此编码的结果是不唯一的;但0/1分配的上下顺序在整个编码过程中应保持一致,分配的上下顺序在整个编码过程中应保持一致,否则不能构成唯一可译码。否则不能构成唯一可译码。 2缩减信源时,若合并后的概率与其他概率相等,这缩减信源时,若合并后的概率与其他概率相等,这几个概率的次序可任意排列,但得到的码字不相同几个概率的次序可任意排列,但得到的码字不相同,对应的码长也不相同对应的码长也不相同,但平均码
8、长也不变。但平均码长也不变。4.74.7霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法Huffman码的特点码的特点用概率匹配方法进行编码用概率匹配方法进行编码概率大的符号对应于短码,概率小的符号对概率大的符号对应于短码,概率小的符号对应于长码,充分利用了短码应于长码,充分利用了短码缩减信源的最后两个码字总是最后一位不同,缩减信源的最后两个码字总是最后一位不同,从而保证了从而保证了Huffman码是即时码码是即时码定理定理4.10 4.10 霍夫曼码是紧致码霍夫曼码是紧致码r元元Huffman算法算法 r=3,A:0,1,2 可知:平均码长为可知:平均
9、码长为L=2 码元码元/信源符号信源符号 改进方法改进方法 在在6个信源符号的后面再加一个概率为个信源符号的后面再加一个概率为0的的符号,记为符号,记为s7,同时有同时有p(s7)=0,这个符号,这个符号称为虚假符号。将信源按称为虚假符号。将信源按7个符号进行三元个符号进行三元编码编码 012012012改进方法改进方法4.74.7霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法其码树图其码树图计算得平均码长为计算得平均码长为L=1.76 码元码元/信源符号。因信源符号。因此通过增加虚假符号的方法可以提高此通过增加虚假符号的方法可以提高r元元Huffma
10、n编码的编码效率。编码的编码效率。 改进的改进的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, =2 r 元霍夫曼码元霍夫曼码4.74
11、.7霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法r 元霍夫曼码元霍夫曼码4.74.7霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法Fano码编码步骤如下:1.将概率按从大到小的顺序排列,令将概率按从大到小的顺序排列,令2.将依次排列的信源符号按概率分成两组,使每组概率将依次排列的信源符号按概率分成两组,使每组概率和尽可能接近或相等。和尽可能接近或相等。3.给每一组分配一位码元给每一组分配一位码元“0或或“1”。4.将每一分组再按同样方法划分,重复步骤将每一分组再按同样方法划分,重复步骤2和和3,直至,直至概率
12、不再可分为止。概率不再可分为止。4.74.7霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法Fano码例4.74.7霍夫曼码和其他编码方法霍夫曼码和其他编码方法Fano码码解:解:信源信源符号符号符号符号概率概率第一次第一次分组分组第二次第二次分组分组第三次第三次分组分组第四次第四次分组分组码字码字码长码长0.20000020.191001030.18101130.17101020.151011030.1010111040.011111144.74.7霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法Fano码码l平
13、均码长为平均码长为l信源熵为信源熵为l编码效率为编码效率为4.74.7霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法Fano编码举例编码举例4.74.7霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法Fano编码举例编码举例 平均码长为平均码长为L=2.64 信道码元信道码元/信源符号。信源符号。 H(S)=2.55 bit/信源符号。信源符号。 本例中费诺编码有较高的编码效率。费诺码比较适合于每次本例中费诺编码有较高的编码效率。费诺码比较适合于每次分组概率都很接近的信源。特别是对每次分组概率都相等分组概率都很接
14、近的信源。特别是对每次分组概率都相等的信源进行编码时,可达到理想的编码效率。的信源进行编码时,可达到理想的编码效率。如果将信源做如果将信源做n次扩展后再进行编码,可以进一步提高编码次扩展后再进行编码,可以进一步提高编码效率效率4.74.7霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法第五章:无失真信源编码第五章:无失真信源编码第五章:无失真信源编码第五章:无失真信源编码香农香农-费诺费诺-埃利斯编码埃利斯编码编码步骤如下:编码步骤如下:将信源符号按概率从大到小顺序排列,为方便起见,将信源符号按概率从大到小顺序排列,为方便起见,令令 2. 按下式计算第按
15、下式计算第i个符号对应的码字的码长要取整)个符号对应的码字的码长要取整)3. 计算第计算第i个符号的累加概率个符号的累加概率4. 将累加概率变换成二进制小数,取小数点后将累加概率变换成二进制小数,取小数点后li位数作位数作为第为第i个符号的码字。个符号的码字。例例 对如下信源编码对如下信源编码:第五章:无失真信源编码第五章:无失真信源编码第五章:无失真信源编码第五章:无失真信源编码香农香农-费诺费诺-埃利斯编码埃利斯编码信源符号信源符号符号概率符号概率累加概率累加概率码长码长码字码字s10.2002.343000s20.190.22.413001s30.180.392.483011s40.17
16、0.572.563100s50.150.742.743101s60.100.593.3441110s70.010.996.6671111110第五章:无失真信源编码第五章:无失真信源编码第五章:无失真信源编码第五章:无失真信源编码香农香农-费诺费诺-埃利斯编码埃利斯编码 平均码长平均码长信源熵信源熵结论:结论: 1) 2)香农香农-费诺费诺-埃利斯编码是即时码,但冗余度稍大,埃利斯编码是即时码,但冗余度稍大,不是最佳码。不是最佳码。编码效率编码效率第五章:无失真信源编码第五章:无失真信源编码第五章:无失真信源编码第五章:无失真信源编码香农香农-费诺费诺-埃利斯编码埃利斯编码香农码、香农码、Hu
17、ffman码、码、Fano码总结码总结l香农码、费诺码、霍夫曼码都考虑了信源的统计特性,香农码、费诺码、霍夫曼码都考虑了信源的统计特性,使经常出现的信源符号对应较短的码字,使信源的平均使经常出现的信源符号对应较短的码字,使信源的平均码长缩短,从而实现了对信源的压缩。码长缩短,从而实现了对信源的压缩。l香农码编码结果唯一,但在很多情况下编码效率不是香农码编码结果唯一,但在很多情况下编码效率不是很高。很高。l费诺码和霍夫曼码的编码方法都不唯一。费诺码和霍夫曼码的编码方法都不唯一。l费诺码比较适合于对分组概率相等或接近的信源编码。费诺码比较适合于对分组概率相等或接近的信源编码。l霍夫曼码对信源的统计
18、特性没有特殊要求,编码效率霍夫曼码对信源的统计特性没有特殊要求,编码效率比较高,对编码设备的要求也比较简单,因此综合性能比较高,对编码设备的要求也比较简单,因此综合性能优于香农码和费诺码。优于香农码和费诺码。4.74.7霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法首先是速率匹配问题首先是速率匹配问题其次是差错扩散问题其次是差错扩散问题第三是霍夫曼码需要查表来进行编译码。第三是霍夫曼码需要查表来进行编译码。信源统计特性未知时,怎么办?可采用所谓通用编信源统计特性未知时,怎么办?可采用所谓通用编码的方法来解决。码的方法来解决。 Huffman码编码应用中的一些问题码编码应用中的一些问题4.74.7霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法霍夫曼码和其他编码方法小结小结重点:香农重点:香农-费诺费诺-埃里斯编码算法;埃里斯编码算法;Huffman编码。编码。难点:改进的难点:改进的r元元Huffman算法。算法。思考题、作业:思考题、作业:思索:课本思索:课本P188 10题、题、18题、题、21题。题。作业:作业:P188 T4.11,T4.12,T4.17