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

信息論--第四章·第七節(jié)霍夫曼碼與其他編碼方法高中的第一次考試已經(jīng)過去一周多了，我一直都覺得我的成績(jī)已經(jīng)算不錯(cuò)了，畢竟在級(jí)部里提升了一百多名，但今晚的一個(gè)朋友圈，竟成了一個(gè)對(duì)我的當(dāng)頭棒喝。發(fā)朋友圈的是我爸的一個(gè)要好的朋友，他的女兒和我一級(jí)，但并不在一個(gè)學(xué)校。朋友圈的內(nèi)容是兩張榮譽(yù)證書。一張是進(jìn)步之星，一張是書法的一等獎(jiǎng)。后面還寫著在級(jí)部里提升了500多名，看著下面評(píng)論區(qū)的喝彩與夸贊，再想想中考時(shí)我倆只差一分的成績(jī)，我竟還在此之前暗暗驕傲，因這被我打敗的一百來人。以前，我或許并不努力與謙虛，但今天的這盆冷水終于把我徹底地澆醒了。我以后，絕不會(huì)自欺欺人的把微小的進(jìn)步當(dāng)做是我努力的成果。我絕不能把自己的夢(mèng)想還沒開始就扔進(jìn)深淵，認(rèn)真起來吧，我這懶惰之徒。信息論--第四章·第七節(jié)霍夫曼碼與其他編碼方法信息論--第四章·第七節(jié)霍夫曼碼與其他編碼方法高中的第一次考試已經(jīng)過去一周多了，我一直都覺得我的成績(jī)已經(jīng)算不錯(cuò)了，畢竟在級(jí)部里提升了一百多名，但今晚的一個(gè)朋友圈，竟成了一個(gè)對(duì)我的當(dāng)頭棒喝。發(fā)朋友圈的是我爸的一個(gè)要好的朋友，他的女兒和我一級(jí)，但并不在一個(gè)學(xué)校。朋友圈的內(nèi)容是兩張榮譽(yù)證書。一張是進(jìn)步之星，一張是書法的一等獎(jiǎng)。后面還寫著在級(jí)部里提升了500多名，看著下面評(píng)論區(qū)的喝彩與夸贊，再想想中考時(shí)我倆只差一分的成績(jī)，我竟還在此之前暗暗驕傲，因這被我打敗的一百來人。以前，我或許并不努力與謙虛，但今天的這盆冷水終于把我徹底地澆醒了。我以后，絕不會(huì)自欺欺人的把微小的進(jìn)步當(dāng)做是我努力的成果。我絕不能把自己的夢(mè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，即為最佳碼。但這種方法對(duì)于多數(shù)情況下是不能實(shí)現(xiàn)最佳碼的，而且編碼效率比較低。

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

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

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

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