《信息论第8讲最佳不等长编码讲解》由会员分享，可在线阅读，更多相关《信息论第8讲最佳不等长编码讲解（35页珍藏版）》请在金锄头文库上搜索。
1、最佳不等长编码,第8讲,若一离散无记忆信源的熵为H(U),每个信源符号用D进制码元进行不等长编码,则一定存在一种无失真编码方法，其平均码长满足,不等长编码定理,对于平均符号熵为HL(U)的离散平稳无记忆信源，必存在一种无失真编码方法，使平均码长满足不等式,不等长编码定理,Fano编码,为使选出平均码长最小，自然想到:从每个节点出发的D种可能的分支出现的概率近于相等，Fano给出一种近于最佳的无失真不等长编码方法。 Fano编码:首先，将信源符号按概率递减的次序排列。将排列好的信源符号划分成D个大组，使每组的概率和近似相等，并各赋予一个D元码符号。然后，将每一大组的信源符号划分成D组，使同一组中
2、的每组的概率和近似相等，并各赋予一个D元码符号。依次下去，直到每个小组只有一个信源符号为止。最后，由码树得到各个信源符号对应的码字。,例：设信源U的9个消息a1，a2，a9的概率分别为1/3，1/9，1/9，1/9，1/9，1/9，1/27，1/27，1/27。,码的平均码长为16/9 方法特点：基于码树，从根节点开始分配码字 fano编码不是最佳编码,Fano编码,第一次 分组,码字,010,011,10,110,1110,1111,00,第二次 分组,第三次 分组,第四次 分组,0,1,0,0,1,1,0,1,1,0,0,1,Fano编码,0,0,1,0,最佳不等长编码 -Huffman编
3、码,Huffman编码,1952年Huffman给出一种编码方法，所得到的码是异字头码，其平均长度最短，是一种最佳码，称作Huffman码。 下面先给出二元Huffman码的编码方法. Huffman编码步骤如下： （1）将K个信源符号按概率分布大小以递减次序排列，设 （2）用0和1码符号分别分配给概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个新符号，并用这两个最小概率之和作为新符号的概率，从而得到只包含K-1个符号的新信源，称为S信源的缩减信源S1。 （3）把缩减信源S1的符号仍按概率分布大小以递减次序排列，再将最后两个概率最小的符号合并成一个新符号，并分别用0和1码符号表示
4、，这样又形成了K-2个符号的缩减信源S2。 （4）以此继续下去，直到缩减信源最后只剩下两个符号为止。将这最后两个新符号分别用用0和1码符号表示。最后这两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径由后向前返回，就得到各信源符号所对应的码符号序列，即得对应的码字。,Huffman编码,码字,11,000,001,010,0110,0111,10,0.11,0.26,0,1,0,1,0.35,0,1,0.39,0.61,0,1,0,1.00,0,1,1,0,1,Huffman编码,1,0.26,信源符号,s1,s2,s3,s4,s5,s6,s7,码字,11,000,001,010
5、,0110,0111,10,s1,s2,s3,s4,s5,s6,s7,0,0,0,0,0,0,1,1,1,1,1,1,从该例编码过程可看出: 1. Huffman码是异字头码； 2.概率小的字符对应码字的长度不会小于概率大的字符对应码字的长度； 3.概率最小的二个字符对应码字仅最后一位不同； 4. Huffman码并非唯一，但平均码长相同（码长方差不同，应减小）。,编码效率比较,Huffman编码,2.72,0.96,H(u)=2.6112 bit,Huffman编码最佳性证明,对于给定的信源，存在最佳唯一可译二元码，其最小概率的两个码字的长度最长且相等，它们之间仅最后一位码元取值不同（一个为
6、0，另一个为1）。,【定理1】,lK最大,存在另外一个码字其长度也为lK，,并且与cK仅最后一位码元取值不同(一个为0，另一个为1),lK最大,sk,pk,ck,lk,pk pK,lk lK,pk pK,Huffman编码最佳性证明,对于给定的信源，存在最佳唯一可译二元码，其最小概率的两个码字的长度最长且相等，它们之间仅最后一位码元取值不同（一个为0，另一个为1）。,【定理1】,lK最大,存在另外一个码字其长度也为lK，,并且与cK仅最后一位码元取值不同(一个为0，另一个为1),并且与cK仅最后一位码元取值不同(一个为0，另一个为1),存在另外一个码字其长度也为lK，,s1,s2,s3,s4,
7、s5,s6,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,s7,s7,(最佳),(最佳),并且与cK仅最后一位码元取值不同(一个为0，另一个为1),存在另外一个码字其长度也为lK，,反证法,Huffman编码最佳性证明,对于给定的信源，存在最佳唯一可译二元码，其最小概率的两个码字的长度最长且相等，它们之间仅最后一位码元取值不同（一个为0，另一个为1）。,【定理1】,lK最大,存在另外一个码字其长度也为lK，,并且与cK仅最后一位码元取值不同(一个为0，另一个为1),满足 的码字为cK1,如果 对缩减信源为最佳码，则对原始信源也是最佳码。,最佳,最佳,最佳,最佳,【定理2】,对缩减
8、信源为最佳码，则对原始信源也是最佳码。,证明:,常数,最小,最小,【定理2】,对缩减信源为最佳码，则对原始信源也是最佳码。,试对下述离散无记忆信源S进行三元Huffman编码。,思考:,信源符号,概率 pk,s1,s2,s3,s4,s5,s6,s7,0.18,0.10,0.10,0.07,0.06,0.05,0.40,s8,0.04,0.15,0.27,0.60,1.00,0,1,0,1,2,0,1,1,2,2,2,思考:,0,最佳?,信源符号,概率pk,s1,s2,s3,s4,s5,s6,s7,0.18,0.10,0.10,0.07,0.06,0.05,0.40,s8,0.04,0.09,0
9、.22,0.38,1.00,0,1,0,1,2,0,0,1,1,2,2,码字,10,11,12,21,22,201,0,200,思考:,r元Huffman编码？,s9,0,2,思考:,r元Huffman编码？,增加0概率符号,?,Y,进行编码,进行编码,N,0.2,0.4,0.6,0,0,0,0,1,1,1,1,0,1,0.2,0,1,0.4,0.6,1,0,0,1,1,1,01,000,0011,0010,00,10,11,011,010,编法一,编法二,码字,码字,0.2,平均码长,编法一：,编法二：,编法一,编法二,1,01,000,0011,0010,00,10,11,011,010,
10、码字长度的方差,编法一：,编法二：,令离散无记忆信源 (a) 求对U（即U1）的最佳二元码、平均码长和编码效率。 (b) 求对U2 （即U1U2）的最佳二元码、平均码长和编码效率。 (c) 求对U3 （即U1U2U3 ）的最佳二元码、平均码长和编码效率。,例,U1U2U3,扩展信源、数据压缩,速率匹配问题,误差扩散问题,概率匹配问题,Huffman编码实际应用中的问题,本节小结,常见不等长编码方法,Huffman编码,Fano编码,（本节内容见课本69-73页）,Shannon、Shannon-Fano-Elias编码,Huffman编码,最佳码,编码方法,（二元编码、r元编码、扩展源编码）,应用,作 业,3.5 3.8 3.9 3.10 3.11,
