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

1、 若一离散无记忆信源的熵为若一离散无记忆信源的熵为H(U),每个信源符每个信源符号用号用D进制码元进行不等长编码进制码元进行不等长编码,则一定存在则一定存在一种无失真编码方法，其平均码长满足一种无失真编码方法，其平均码长满足 1log)(log)(DUHnDUH不等长编码定理不等长编码定理nDUHlog)(1log)(DUHnReview 对于平均符号熵为对于平均符号熵为HL(U)的离散平稳无记忆信的离散平稳无记忆信源，必存在一种无失真编码方法，使平均码源，必存在一种无失真编码方法，使平均码长满足不等式长满足不等式 1log)U(log)(LDHnDUHLL不等长编码定理不等长编码定理Revi

2、ew第一次第一次 分组分组码字码字010011101101110111100第二次第二次 分组分组第三次第三次分组分组第四次第四次分组分组010011011001信源信源符号符号概率概率 pks1s2s3s4s5s6s70.190.180.170.150.100.010.20Fano编码编码0010Fano编码不能保证编出码字平均码长最短。编码不能保证编出码字平均码长最短。最佳编码？最佳编码？Review最佳不等长编码最佳不等长编码-Huffman编码编码n 1952年Huffman给出一种编码方法，所得到的码是异字头码，其平均长度最短，称作Huffman码。Huffman编码步骤如下：（1）

3、将K个信源符号按概率分布大小以递减次序排列，设（2）用0和1码符号分别分配给概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个新符号，并用这两个最小概率之和作为新符号的概率，从而得到只包含K-1个符号的新信源，称为S信源的缩减信源S1。（3）把缩减信源S1的符号仍按概率分布大小以递减次序排列，再将最后两个概率最小的符号合并成一个新符号，并分别用0和1码符号表示，这样又形成了K-2个符号的缩减信源S2。（4）以此继续下去，直到缩减信源最后只剩下两个符号为止。将这最后两个新符号分别用用0和1码符号表示。最后这两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径由后向前返回，

4、就得到各信源符号所对应的码符号序列，即得对应的码字。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

5、码字码字110000010100110011110s1s2s3s4s5s6s7000000111111从该例编码过程可看出从该例编码过程可看出:1. Huffman码是异字头码；2.概率小的字符对应码字的长度不会小于概率大的字符对应码字的长度；3.概率最小的二个字符对应码字仅最后一位不同；4. Huffman码并非唯一，但平均码长相同（码长方差不同，应减小）。Huffman编码方法是最佳编码方法是最佳 ？Huffman编码最佳性证明编码最佳性证明 对于给定的信源，存在最佳唯一可译二元码，对于给定的信源，存在最佳唯一可译二元码，其最小概率的两个码字的长度最长且相等，它们其最小概率的两个码字的长度

6、最长且相等，它们之间仅最后一位码元取值不同（一个为之间仅最后一位码元取值不同（一个为0，另一，另一个为个为1）。）。【定理定理1 1】u lK最大最大u存在另外一个码字其长度也为存在另外一个码字其长度也为lK，s1, s2,sK-1, sKp1,p2,pK-1, pKc1, c2,cK-1, cKl1, l2,lK-1, lK 并且与并且与cK仅最后一位码元取值不仅最后一位码元取值不同同(一个为一个为0，另一个为，另一个为1)u满足满足 的码字为的码字为cK1lK最大最大KKpppp121skpkcklks1, s2, ., sKp1, p2, .,pKc1, c2, ., cKl1, l2,

7、 ., lK 反证法反证法s1, s2, , sk ,., sKp1, p2, pk ,.,pKc1, c2, , cK, ., ckl1, l2, , lK, ., lk )(KKkkkKKklplplplp)(kKKkllpp0pk pK矛盾矛盾LKKkklplplp11LkKKklplplp11LLlk lK假设假设lk lKpk pKHuffman编码最佳性证明编码最佳性证明 对于给定的信源，存在最佳唯一可译二元码，对于给定的信源，存在最佳唯一可译二元码，其最小概率的两个码字的长度最长且相等，它们其最小概率的两个码字的长度最长且相等，它们之间仅最后一位码元取值不同（一个为之间仅最后一位

8、码元取值不同（一个为0，另一，另一个为个为1）。）。【定理定理1】u lK最大最大u存在另外一个码字其长度也为存在另外一个码字其长度也为lK，并且与并且与cK仅最后一位码元取值不仅最后一位码元取值不同同(一个为一个为0，另一个为，另一个为1)u满足满足 的码字为的码字为cK1并且与并且与cK仅最后一位码元取值不仅最后一位码元取值不同同(一个为一个为0，另一个为，另一个为1)存在另外一个码字其长度也为存在另外一个码字其长度也为lK，s1, s2,sK-1, sKp1,p2,pK-1, pKc1, c2,cK-1, cKl1, l2,lK-1, lK s1s2s3s4s5s600000011111

9、1111s7s7异字头码异字头码唯一可译码唯一可译码(最佳最佳)(最佳最佳)并且与并且与cK仅最后一位码元取值不仅最后一位码元取值不同同(一个为一个为0，另一个为，另一个为1)u存在另外一个码字其长度也为存在另外一个码字其长度也为lK，反证法反证法u不成立不成立假设假设Huffman编码最佳性证明编码最佳性证明 对于给定的信源，存在最佳唯一可译二元码，其最对于给定的信源，存在最佳唯一可译二元码，其最小概率的两个码字的长度最长且相等，它们之间仅最后小概率的两个码字的长度最长且相等，它们之间仅最后一位码元取值不同（一个为一位码元取值不同（一个为0，另一个为，另一个为1）。）。【定理定理1】u lK

10、最大最大u存在另外一个码字其长度也为存在另外一个码字其长度也为lK，并且与并且与cK仅最后一位码元取值不仅最后一位码元取值不同同(一个为一个为0，另一个为，另一个为1)u满足满足 的码字为的码字为cK1满足满足 的码字为的码字为cK1s1, s2,sK-1, sKp1,p2,pK-1, pKc1, c2,cK-1, cKl1, l2,lK-1, lK 回顾回顾Huffman编码过程编码过程KKKKpspsps1111S：S(1)：)1(1)1(1)1(2)1(2)1(1)1(1KKKKpspspsS(K-3)：)3(3)3(3)3(2)3(2)3(1)3(1KKKKKKpspspsS(K-2)

11、：)2(2)2(2)2(1)2(1,KKKKpsps如果如果 对缩减信源对缩减信源为最佳码，则为最佳码，则对原始信源也对原始信源也是最佳码。是最佳码。 最佳最佳最佳最佳最佳最佳最佳最佳【定理定理2】 对缩减信源为最佳码，则对原始信源也是最佳码。对缩减信源为最佳码，则对原始信源也是最佳码。 KKKKpspspsps112211S：LKkkklp121Kkkklp)(111KKKkkkpplp)(1KKppL证明证明: :KKKKlclclclc112211S：112211KKpspsps112211KKlclclc11cc 22cc 22KKcc)0(11KKcc) 1(1KKcc22pp 11

12、KKKppp11pp 22KKpp)(1KKpp常数常数L最小最小L最小最小11ll 111KKll22ll 22KKll11KKll)()(11121KKkKKKkkkpplpplp22pp 11KKKppp11pp 22KKpp11ll 111KKll22ll 22KKll11KKll1Kp) 1(11KKlp) 1(1KKlp111KKll11ll 22ll 22KKll11KKll11KKKppp22pp 11pp 22KKpp【定理定理2】 对缩减信源为最佳码，则对原始信源也是最佳码。对缩减信源为最佳码，则对原始信源也是最佳码。 Huffman编码最佳编码最佳04. 005. 006

13、. 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

14、.381.0001012001122码字码字10111221222010200思考思考: r元元Huffman编码？编码？s902思考思考: r元元Huffman编码？编码？rrq) 1(增加增加0 0概率概率符号符号?Y进行编码进行编码进行编码进行编码N例：例： 设离散无记忆信源设离散无记忆信源1 . 01 . 02 . 02 . 04 . 0,)(54321sssssSPS试对其进行二元试对其进行二元Huffman编码。编码。S p(sk)s1s2s3s4s50.20.20.10.10.40.20.40.6000011111Ss1s2s3s4s50.20.20.10.10.4p(sk)01

15、0.2010.40.61001110100000110010001011011010编法一编法一编法二编法二码字码字码字码字0.2511( )0.4 1 0.2 2 0.2 3 0.1 4 2 2.2kkknps n 平均码长平均码长编法一：编法一：编法二：编法二：521( )0.4 2 0.2 2 2 0.1 3 2 2.2kkknp s n 编码效率相同编码效率相同编法一编法一编法二编法二10100000110010S p(sk)s1s2s3s4s50.20.20.10.10.4001011011010哪种方法更好？哪种方法更好？码字长度的方差码字长度的方差2221() ( )()Kkkk

16、iE nnp snn36. 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) 求

17、对求对U2 （即（即U1U2）的最佳二元码、平均码长和编）的最佳二元码、平均码长和编码效率。码效率。(c) 求对求对U3 （即（即U1U2U3 ）的最佳二元码、平均码长）的最佳二元码、平均码长和编码效率。和编码效率。2 . 03 . 05 . 0321aaaU例例2 . 03 . 05 . 0321aaaU04. 006. 006. 009. 010. 010. 015. 015. 025. 033233222133112211121aaaaaaaaaaaaaaaaaaUUa1a1a1a1a1a2a1a2a1a2a1a1a1a1a3a1a3a1a3a1a1a1a2a2a2a1a20.1250.0750.0750.0750.0500.0500.0500.0450.045a2a2a1a1a2a3a1a3a2a2a1a3a3a1a2a2a3a1a3a2a1a2a2a2a1a3a30.0450.0300.0300.0300.0300.0300.0300.0270.020a3a1a3a3a3a1a2a2a3a2a3a2a3a2a2a2a3a3a3a2a3a3a3a2a3a3a30.0200.0200.0180.0180.0180.0