第8講——最佳不等長編碼2014

1、 若一離散無記憶信源的熵為若一離散無記憶信源的熵為H(U),每個信源符每個信源符號用號用D進制碼元進行不等長編碼進制碼元進行不等長編碼,則一定存在則一定存在一種無失真編碼方法，其平均碼長滿足一種無失真編碼方法，其平均碼長滿足 1log)(log)(DUHnDUH不等長編碼定理不等長編碼定理nDUHlog)(1log)(DUHnReview 對于平均符號熵為對于平均符號熵為HL(U)的離散平穩(wěn)無記憶信的離散平穩(wěn)無記憶信源，必存在一種無失真編碼方法，使平均碼源，必存在一種無失真編碼方法，使平均碼長滿足不等式長滿足不等式 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個信源符號按概率分布大小以遞減次序排列，設(shè)（2）用0和1碼符號分別分配給概率最小的兩個信源符號，并將這兩個概率最小的信源符號合并成一個新符號，并用這兩個最小概率之和作為新符號的概率，從而得到只包含K-1個符號的新信源，稱為S信源的縮減信源S1。（3）把縮減信源S1的符號仍按概率分布大小以遞減次序排列，再將最后兩個概率最小的符號合并成一個新符號，并分別用0和1碼符號表示，這樣又形成了K-2個符號的縮減信源S2。（4）以此繼續(xù)下去，直到縮減信源最后只剩下兩個符號為止。將這最后兩個新符號分別用用0和1碼符號表示。最后這兩個符號的概率之和必為1。然后從最后一級縮減信源開始，依編碼路徑由后向前返回，

4、就得到各信源符號所對應(yīng)的碼符號序列，即得對應(yīng)的碼字。12Kppp例：例： 設(shè)離散無記憶信源設(shè)離散無記憶信源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.概率小的字符對應(yīng)碼字的長度不會小于概率大的字符對應(yīng)碼字的長度；3.概率最小的二個字符對應(yīng)碼字僅最后一位不同；4. Huffman碼并非唯一，但平均碼長相同（碼長方差不同，應(yīng)減小）。Huffman編碼方法是最佳編碼方法是最佳 ？Huffman編碼最佳性證明編碼最佳性證明 對于給定的信源，存在最佳唯一可譯二元碼，對于給定的信源，存在最佳唯一可譯二元碼，其最小概率的兩個碼字的長度最長且相等，它們其最小概率的兩個碼字的長度

6、最長且相等，它們之間僅最后一位碼元取值不同（一個為之間僅最后一位碼元取值不同（一個為0，另一，另一個為個為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假設(shè)假設(shè)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不成立不成立假設(shè)假設(shè)Huffman編碼最佳性證明編碼最佳性證明 對于給定的信源，存在最佳唯一可譯二元碼，其最對于給定的信源，存在最佳唯一可譯二元碼，其最小概率的兩個碼字的長度最長且相等，它們之間僅最后小概率的兩個碼字的長度最長且相等，它們之間僅最后一位碼元取值不同（一個為一位碼元取值不同（一個為0，另一個為，另一個為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常數(shù)常數(shù)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例：例： 設(shè)離散無記憶信源設(shè)離散無記憶信源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編碼實際應(yīng)用中的問題編碼實際應(yīng)用中的問題令離散無記憶信源令離散無記憶信源(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