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

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

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

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

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

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

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