信息論-第四章·第七節(jié)-霍夫曼碼與其他編碼方法

信息論--第四章·第七節(jié)霍夫曼碼與其他編碼方法高中的第一次考試已經(jīng)過去一周多了，我一直都覺得我的成績已經(jīng)算不錯了，畢竟在級部里提升了一百多名，但今晚的一個朋友圈，竟成了一個對我的當頭棒喝。發(fā)朋友圈的是我爸的一個要好的朋友，他的女兒和我一級，但并不在一個學校。朋友圈的內(nèi)容是兩張榮譽證書。一張是進步之星，一張是書法的一等獎。后面還寫著在級部里提升了500多名，看著下面評論區(qū)的喝彩與夸贊，再想想中考時我倆只差一分的成績，我竟還在此之前暗暗驕傲，因這被我打敗的一百來人。以前，我或許并不努力與謙虛，但今天的這盆冷水終于把我徹底地澆醒了。我以后，絕不會自欺欺人的把微小的進步當做是我努力的成果。我絕不能把自己的夢想還沒開始就扔進深淵，認真起來吧，我這懶惰之徒。信息論--第四章·第七節(jié)霍夫曼碼與其他編碼方法信息論--第四章·第七節(jié)霍夫曼碼與其他編碼方法高中的第一次考試已經(jīng)過去一周多了，我一直都覺得我的成績已經(jīng)算不錯了，畢竟在級部里提升了一百多名，但今晚的一個朋友圈，竟成了一個對我的當頭棒喝。發(fā)朋友圈的是我爸的一個要好的朋友，他的女兒和我一級，但并不在一個學校。朋友圈的內(nèi)容是兩張榮譽證書。一張是進步之星，一張是書法的一等獎。后面還寫著在級部里提升了500多名，看著下面評論區(qū)的喝彩與夸贊，再想想中考時我倆只差一分的成績，我竟還在此之前暗暗驕傲，因這被我打敗的一百來人。以前，我或許并不努力與謙虛，但今天的這盆冷水終于把我徹底地澆醒了。我以后，絕不會自欺欺人的把微小的進步當做是我努力的成果。我絕不能把自己的夢想還沒開始就扔進深淵，認真起來吧，我這懶惰之徒。教學要求了解Shannon編碼思想、Shannon-Fano算法、香農(nóng)-費諾-埃里斯編碼算法；掌握Huffman編碼方法。教學要求了解Shannon編碼思想、Shannon-Fano算法、香農(nóng)-費諾-埃里斯編碼算法；掌握Huffman編碼方法。Shannon算法Shannon編碼思想：按概率編碼它是滿足Kraft不等式的一種直接的應用

例：一個離散信源S:{s1,s2,s3,s4}p(S):{1/2,1/4,1/8,1/8}這時有：L1=log2=1;L2=log4=2;L3=L4=log8=3;4.7霍夫曼碼和其他編碼方法Shannon編碼舉例利用碼樹圖法可得到其編碼這個例子其編碼效率為1，即為最佳碼。但這種方法對于多數(shù)情況下是不能實現(xiàn)最佳碼的，而且編碼效率比較低。

4.7霍夫曼碼和其他編碼方法L1=1,L2=2,L3=L4=3;Huffman碼將信源符號按概率從大到小的順序排列，令給兩個概率最小的信源符號sn-1和sn各分配一個碼元“0”和“1”，并將這兩個信源符號合并成一個新符號，并用這兩個最小的概率之和作為新符號的概率，結(jié)果得到一個只包含(n－1)個信源符號的新信源。稱為信源的第一次縮減信源，用S1表示。將縮減信源S1的符號仍按概率從大到小順序排列，重復步驟2，得到只含(n－2)個符號的縮減信源S2。重復上述步驟，直至縮減信源只剩兩個符號為止，此時所剩兩個符號的概率之和必為1。然后從最后一級縮減信源開始，依編碼路徑向前返回，就得到各信源符號所對應的碼字。編碼步驟如下：4.7霍夫曼碼和其他編碼方法01010101Huffman碼4.7霍夫曼碼和其他編碼方法Huffman碼離散信源如下:解：編碼過程略，Huffman編碼結(jié)果如下：4.7霍夫曼碼和其他編碼方法Huffman碼平均碼長為信源熵為編碼效率為4.7霍夫曼碼和其他編碼方法Huffman碼注意：霍夫曼編碼后的碼字不是惟一的。1）每次對縮減信源兩個概率最小的符號分配“0”或“1”碼元是任意的,因此編碼的結(jié)果是不唯一的；但0/1分配的上下順序在整個編碼過程中應保持一致，否則不能構(gòu)成唯一可譯碼。2）縮減信源時，若合并后的概率與其他概率相等，這幾個概率的次序可任意排列，但得到的碼字不相同,對應的碼長也不相同,但平均碼長也不變。4.7霍夫曼碼和其他編碼方法Huffman碼的特點用概率匹配方法進行編碼概率大的符號對應于短碼，概率小的符號對應于長碼，充分利用了短碼縮減信源的最后兩個碼字總是最后一位不同，從而保證了Huffman碼是即時碼定理4.10

霍夫曼碼是緊致碼r元Huffman算法

r=3,A:{0,1,2}可知：平均碼長為L=2碼元/信源符號改進方法在6個信源符號的后面再加一個概率為0的符號，記為s7’,同時有p(s7’)=0，這個符號稱為虛假符號。將信源按7個符號進行三元編碼012012012改進方法4.7霍夫曼碼和其他編碼方法其碼樹圖計算得平均碼長為L=1.76碼元/信源符號。因此通過增加虛假符號的方法可以提高r元Huffman編碼的編碼效率。改進的r元Huffman編碼對于離散信源S:{s1,s2,…,sq}P(S):{p(s1),p(s2),……p(sq)}A;{a1,a2,…ar};第一次縮減信源S(1)，每次將減少(r-1)個符號，分別形成S(2),S(3)…如果i=r-{q-[r-1]}?。剑?其中表示縮減次數(shù),應當在原始信源中加上m個概率為0的虛假信源符號，然后進行編碼，將得到最佳碼。上例，q=6,r=3,=2r元霍夫曼碼4.7霍夫曼碼和其他編碼方法r元霍夫曼碼4.7霍夫曼碼和其他編碼方法Fano碼編碼步驟如下：將概率按從大到小的順序排列，令將依次排列的信源符號按概率分成兩組，使每組概率和盡可能接近或相等。給每一組分配一位碼元“0”或“1”。將每一分組再按同樣方法劃分，重復步驟2和3，直至概率不再可分為止。4.7霍夫曼碼和其他編碼方法Fano碼例4.7霍夫曼碼和其他編碼方法Fano碼解：信源符號符號概率第一次分組第二次分組第三次分組第四次分組碼字碼長0.20000020.191001030.18101130.17101020.151011030.1010111040.011111144.7霍夫曼碼和其他編碼方法Fano碼平均碼長為信源熵為編碼效率為4.7霍夫曼碼和其他編碼方法Fano編碼舉例4.7霍夫曼碼和其他編碼方法Fano編碼舉例平均碼長為L=2.64信道碼元/信源符號。H(S)=2.55bit/信源符號。

本例中費諾編碼有較高的編碼效率。費諾碼比較適合于每次分組概率都很接近的信源。特別是對每次分組概率都相等的信源進行編碼時，可達到理想的編碼效率。如果將信源做n次擴展后再進行編碼，可以進一步提高編碼效率4.7霍夫曼碼和其他編碼方法第五章：無失真信源編碼香農(nóng)-費諾-埃利斯編碼編碼步驟如下：將信源符號按概率從大到小順序排列，為方便起見，令2.按下式計算第i個符號對應的碼字的碼長（要取整）3.計算第i個符號的累加概率4.將累加概率變換成二進制小數(shù)，取小數(shù)點后li位數(shù)作為第i個符號的碼字。例對如下信源編碼:第五章：無失真信源編碼香農(nóng)-費諾-埃利斯編碼信源符號符號概率累加概率碼長碼字s10.2002.343000s20.190.22.413001s30.180.392.483011s40.170.572.563100s50.150.742.743101s60.100.593.3441110s70.010.996.6671111110第五章：無失真信源編碼香農(nóng)-費諾-埃利斯編碼平均碼長信源熵結(jié)論：1)2)香農(nóng)-費諾-埃利斯編碼是即時碼，但冗余度稍大，不是最佳碼。編碼效率第五章：無失真信源編碼香農(nóng)-費諾-埃利斯編碼香農(nóng)碼、Huffman碼、Fano碼總結(jié)香農(nóng)碼、費諾碼、霍夫曼碼都考慮了信源的統(tǒng)計特性，使經(jīng)常出現(xiàn)的信源符號對應較短的碼字，使信源的平均碼長縮短，從而實現(xiàn)了對信源的壓縮。香農(nóng)碼編碼結(jié)果唯一，但在很多情況下編碼效率不是很高。費諾碼和霍夫曼碼的編碼方法都不唯一。費諾碼比較適合于對分組概率相等或接近的信源編碼。霍夫曼碼對信源的統(tǒng)計特性沒有特殊要求，編碼效率比較高，對編碼設(shè)備的要求也比較簡單，因此綜合性能優(yōu)于香農(nóng)碼和費諾碼。4.7霍夫曼碼和其他編碼方法首先是速率匹配問題其次是差錯擴散問題第三是霍夫曼碼