第10讲——最佳不等长编码.ppt

1、最佳不等长编码,第十讲,若一离散无记忆信源的熵为H(U),每个信源符号用D进制码元进行不等长编码,则一定存在一种无失真编码方法,构成唯一可译码，其平均码长满足,不等长编码定理,对于平均符号熵为HL(U)的离散平稳无记忆信源，必存在一种无失真编码方法，使平均码长满足不等式,不等长编码定理,最佳不等长编码,Shannon编码,Shannon编码,累加概率,累加概率对应的二进制数,码字,0.20,0.39,0.57,0.17,0.89,0.99,0,0.0011,0.0110,0.1001,0.1011,0.1110,0.1111110,0.000,码长nk,2.41,2.48,2.56,2.74,

2、3.34,6.66,2.34,3,3,3,3,4,7,3,001,011,100,101,1110,1111110,000,000,3,3,001,s1,s2,Shannon编码,信源符号,s1,s2,s3,s4,s5,s6,s7,码字,001,011,100,101,1110,1111110,000,s1,s2,s3,s4,s5,s6,0,0,0,0,0,0,1,1,1,1,1,1,1,1,s7,第一次 分组,码字,010,011,10,110,1110,1111,00,第二次 分组,第三次 分组,第四次 分组,0,1,0,0,1,1,0,1,1,0,0,1,Fano编码,0,0,1,0,s

3、1,s2,s3,s4,s5,s6,s7,0,0,0,0,0,0,1,1,1,1,1,1,s2,s4,s2,s4,s1,s2,s3,s4,s5,s6,0,0,0,0,0,0,1,1,1,1,1,1,1,1,Shannon码,Fano码,（P2=0.19）,（P4=0.17）,第一次 分组,码字,010,011,10,110,1110,1111,00,第二次 分组,第三次 分组,第四次 分组,0,1,0,0,1,1,0,1,1,0,0,1,Fano编码,码字,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

4、,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,编码效率比较,Huffman编码,2.72,0.96,Huffman编码最佳性证明,对于给定的信源，存在最佳唯一可译二元码，其最小概率的两个码字的长度最长且相等，它们之间仅最后一位码元取值不同（一个为0，另一个为1）。,【定理1】,lK最大,存在另外一个码字其长度也为lK，,并且与cK仅最后一位码元取值不同(一个为0，另一个为1

5、),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,s5,s6,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,s7,s7,(最佳),(最佳),并且与cK仅最后一位码元取

6、值不同(一个为0，另一个为1),存在另外一个码字其长度也为lK，,反证法,Huffman编码最佳性证明,对于给定的信源，存在最佳唯一可译二元码，其最小概率的两个码字的长度最长且相等，它们之间仅最后一位码元取值不同（一个为0，另一个为1）。,【定理1】,lK最大,存在另外一个码字其长度也为lK，,并且与cK仅最后一位码元取值不同(一个为0，另一个为1),满足 的码字为cK1,如果 对缩减信源为最佳码，则对原始信源也是最佳码。,最佳,最佳,最佳,最佳,【定理2】,对缩减信源为最佳码，则对原始信源也是最佳码。,证明:,常数,最小,最小,【定理2】,对缩减信源为最佳码，则对原始信源也是最佳码。,试对下

7、述离散无记忆信源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,思

8、考:,r元Huffman编码？,s9,0,2,思考:,r元Huffman编码？,增加0概率符号,?,Y,进行编码,进行编码,N,Huffman编码实际应用中的问题,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 ）的最佳二元码、平均码长和编码效率。,例,U1U2U3,扩展信源、数据