第8讲――最佳不等长编码2014

最佳不等长编码第8讲若一离散无记忆信源的熵为H(U),每个信源符号用D进制码元进行不等长编码,则一定存在一种无失真编码方法，其平均码长满足1log)(log)(DUHnDUH不等长编码定理nDUHlog)(1log)(DUHnReview对于平均符号熵为HL(U)的离散平稳无记忆信源，必存在一种无失真编码方法，使平均码长满足不等式1log)U(log)(LDHnDUHLL不等长编码定理Review第一次分组码字010011101101110111100第二次分组第三次分组第四次分组010011011001信源符号概率pks1s2s3s4s5s6s70.190.180.170.150.100.010.20Fano编码0010Fano编码不能保证编出码字平均码长最短。最佳编码？Review最佳不等长编码-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。然后从最后一级缩减信源开始，依编码路径由后向前返回，就得到各信源符号所对应的码符号序列，即得对应的码字。12Kppp例：设离散无记忆信源01.010.015.017.018.019.020.07654321ssssssspSi试对其进行二元Huffman编码。Huffman编码码字1100000101001100111100.110.2601010.35010.390.610101.00011信源符号概率pks1s2s3s4s5s6s70.190.180.170.150.100.010.2001Huffman编码10.26信源符号s1s2s3s4s5s6s7码字110000010100110011110s1s2s3s4s5s6s7000000111111从该例编码过程可看出:1.Huffman码是异字头码；2.概率小的字符对应码字的长度不会小于概率大的字符对应码字的长度；3.概率最小的二个字符对应码字仅最后一位不同；4.Huffman码并非唯一，但平均码长相同（码长方差不同，应减小）。Huffman编码方法是最佳？Huffman编码最佳性证明对于给定的信源，存在最佳唯一可译二元码，其最小概率的两个码字的长度最长且相等，它们之间仅最后一位码元取值不同（一个为0，另一个为1）。【定理1】lK最大存在另外一个码字其长度也为lK，s1,s2,…,sK-1,sKp1,p2,…,pK-1,pKc1,c2,…,cK-1,cKl1,l2,…,lK-1,lK并且与cK仅最后一位码元取值不同(一个为0，另一个为1)满足的码字为cK－1lK最大KKpppp121skpkcklks1,s2,…….,sKp1,p2,…….,pKc1,c2,…….,cKl1,l2,…….,lK反证法s1,s2,…,sk,….,sKp1,p2,…,pk,….,pKc1,c2,…,cK,….,ckl1,l2,…,lK,….,lk)(KKkkkKKklplplplp))((kKKkllpp0pkpK矛盾LKKkklplplp11'LkKKklplplp11L'LlklK假设lklKpkpKHuffman编码最佳性证明对于给定的信源，存在最佳唯一可译二元码，其最小概率的两个码字的长度最长且相等，它们之间仅最后一位码元取值不同（一个为0，另一个为1）。【定理1】lK最大存在另外一个码字其长度也为lK，并且与cK仅最后一位码元取值不同(一个为0，另一个为1)满足的码字为cK－1并且与cK仅最后一位码元取值不同(一个为0，另一个为1)存在另外一个码字其长度也为lK，s1,s2,…,sK-1,sKp1,p2,…,pK-1,pKc1,c2,…,cK-1,cKl1,l2,…,lK-1,lKs1s2s3s4s5s6000000111111111s7s7异字头码唯一可译码(最佳)(最佳)并且与cK仅最后一位码元取值不同(一个为0，另一个为1)存在另外一个码字其长度也为lK，反证法不成立假设Huffman编码最佳性证明对于给定的信源，存在最佳唯一可译二元码，其最小概率的两个码字的长度最长且相等，它们之间仅最后一位码元取值不同（一个为0，另一个为1）。【定理1】lK最大存在另外一个码字其长度也为lK，并且与cK仅最后一位码元取值不同(一个为0，另一个为1)满足的码字为cK－1满足的码字为cK－1s1,s2,…,sK-1,sKp1,p2,…,pK-1,pKc1,c2,…,cK-1,cKl1,l2,…,lK-1,lK回顾Huffman编码过程KKKKpspsps1111S：S(1)：)1(1)1(1)1(2)1(2)1(1)1(1KKKKpspspsS(K-3)：)3(3)3(3)3(2)3(2)3(1)3(1KKKKKKpspspsS(K-2)：)2(2)2(2)2(1)2(1,,KKKKpsps如果对缩减信源为最佳码，则对原始信源也是最佳码。最佳最佳最佳最佳【定理2】对缩减信源为最佳码，则对原始信源也是最佳码。KKKKpspspsps112211S：LKkkklp121''Kkkklp)(111''KKKkkkpplp)(1'KKppL证明:KKKKlclclclc112211S’：'1'1'2'2'1'1KKpspsps'1'1'2'2'1'1KKlclclc'11cc'22cc……'22KKcc)0('11KKcc)1('1KKcc2'2pp1'1KKKppp1'1pp……2'2KKpp)(1KKpp常数'L最小L最小'11ll1'11KKll'22ll'22KKll……1'1KKll)()(1'1121''KKkKKKkkkpplpplp2'2pp1'1KKKppp1'1pp……2'2KKpp'11ll1'11KKll'22ll'22KKll……1'1KKll'1Kp)1('11KKlp)1('1KKlp1'11KKll'11ll'22ll'22KKll……1'1KKll1'1KKKppp2'2pp1'1pp……2'2KKpp【定理2】对缩减信源为最佳码，则对原始信源也是最佳码。Huffman编码最佳04.005.006.007.01.01.018.04.0,,,,,87654321sssssssspSi试对下述离散无记忆信源S进行三元Huffman编码。思考:信源符号概率pks1s2s3s4s5s6s70.180.100.100.070.060.050.40s80.040.150.270.601.0001012011222思考:0增加1个概率为0的信源符号【提示】最佳?信源符号概率pks1s2s3s4s5s6s70.180.100.100.070.060.050.40s80.040.090.220.381.0001012001122码字10111221222010200思考:r元Huffman编码？s902思考:r元Huffman编码？rrq)1(增加0概率符号?Y进行编码进行编码N例：设离散无记忆信源1.01.02.02.04.0,,,,)(54321sssssSPS试对其进行二元Huffman编码。Sp(sk)s1s2s3s4s50.20.20.10.10.40.20.40.6000011111Ss1s2s3s4s50.20.20.10.10.4p(sk)010.2010.40.61001110100000110010001011011010编法一编法二码字码字0.2511()0.410.220.230.1422.2kkknpsn平均码长编法一：编法二：521()0.420.2220.1322.2kkknpsn编码效率相同编法一编法二10100000110010Sp(sk)s1s2s3s4s50.20.20.10.10.4001011011010哪种方法更好？码字长度的方差2221[()]()()KkkkiEnnpsnn36.12)2.24(1.0)2.23(2.0)2.22(2.0)2.21(4.0222221编法一：编法二：16.02)2.23(1.02)2.22(2.0)2.22(4.022222速率匹配问题误差扩散问题概率匹配问题Huffman编码实际应用中的问题令离散无记忆信源(a)求对U（即U1）的最佳二元码、平均码长和编码效率。(b)求对U2（即U1U2）的最佳二元码、平均码长和编码效率。(c)求对U3（即U1U2U3）的最佳二元码、平均码长和编码效率。2.03.05.0~321aaaU例2.03.05.0~321aaaU04.006.006.009.010.010.015.015.025.0~33233222133112211121aaaaaaaaaaaaaaaaaaUUa1a1a1a1a1a2a1a2a1a2a1a1a1a1a3a1a3a1a3a1a1a1a2a2a2a1a20.1250.0750.0750.0750.0500.0500.0500.0450.045a2a2a1a1a2a3a1a3a2a2a1a3a3a1a2a2a3a1a3a2a1a2a2a2a1a3a30.0450.0300.0300.0300.0300.0300.0300.0270.020a3a1a3a3a3a1a2a2a3a2a3a2a3a2a2a2a3a3a3a2a3a3a3a2a3a3a30.0200.0200.0180.0180.0180.0120.0120.0120.008U1U2U399002.05.148503.1)()(2RUHU99289.04956666.148503.1)()(3RUHU99002.05.148503.1)()(RUHU扩展信源、数据压缩本节小结常见不等长编码方法Huffman编码–Fano编码–Shannon编码–Huffman编码–最佳码–编码方法（二元编码、r元编码、扩展源编码）–应用作业3.53.83.93.103.11