第8讲最佳不等长编码2014

最佳不等长编码,第8讲,若一离散无记忆信源的熵为H(U),每个信源符号用D进制码元进行不等长编码,则一定存在一种无失真编码方法，其平均码长满足,不等长编码定理,对于平均符号熵为HL(U)的离散平稳无记忆信源，必存在一种无失真编码方法，使平均码长满足不等式,不等长编码定理,第一次分组,码字,010,011,10,110,1110,1111,00,第二次分组,第三次分组,第四次分组,0,1,0,0,1,1,0,1,1,0,0,1,Fano编码,0,0,1,0,Fano编码不能保证编出码字平均码长最短。最佳编码？,最佳不等长编码-Huffman编码,1952年Huffman给出一种编码方法，所得到的码是异字头码，其平均长度最短，称作Huffman码。Huffman编码步骤如下：（1）将K个信源符号按概率分布大小以递减次序排列，设（2）用0和1码符号分别分配给概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个新符号，并用这两个最小概率之和作为新符号的概率，从而得到只包含K-1个符号的新信源，称为S信源的缩减信源S1。（3）把缩减信源S1的符号仍按概率分布大小以递减次序排列，再将最后两个概率最小的符号合并成一个新符号，并分别用0和1码符号表示，这样又形成了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,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编码方法是最佳？,Huffman编码最佳性证明,对于给定的信源，存在最佳唯一可译二元码，其最小概率的两个码字的长度最长且相等，它们之间仅最后一位码元取值不同（一个为0，另一个为1）。,【定理1】,lK最大,存在另外一个码字其长度也为lK，,并且与cK仅最后一位码元取值不同(一个为0，另一个为1),lK最大,sk,pk,ck,lk,pkpK,lklK,pkpK,Huffman编码最佳性证明,对于给定的信源，存在最佳唯一可译二元码，其最小概率的两个码字的长度最长且相等，它们之间仅最后一位码元取值不同（一个为0，另一个为1）。,【定理1】,lK最大,存在另外一个码字其长度也为lK，,并且与cK仅最后一位码元取值不同(一个为0，另一个为1),并且与cK仅最后一位码元取值不同(一个为0，另一个为1),存在另外一个码字其长度也为lK，,s1,s2,s3,s4,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】,对缩减信源为最佳码，则对原始信源也是最佳码。,证明:,常数,最小,最小,【定理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.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,码字长度的方差,编法一：,编法二：,速率匹配问题,误差扩散问题,概率匹配问题,Huffman编码实际应用中的问题,令离散无记忆信源(a)求对U（即U1）的最佳二元码、平均码长和编码效率。(b)求对U2（即U1U2）的最佳二元码、平均码长和编码效率。(c)求对U3（即U1U2U3）的最佳二元码、平均码长和