《無失真信源編碼》PPT課件.ppt

《《無失真信源編碼》PPT課件.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、§2.8無失真信源編碼(二)五、編碼的一般原則六、范諾(Fano)編碼七、霍夫曼(Huffman)編碼八、N次擴展編碼五、編碼的一般原則1.等概化使編碼后各個碼元出現(xiàn)的概率盡可能地相等。2.減少平均碼長將概率大的消息編成短碼，概率小的消息編成長碼。3.消息合并將兩個或者兩個以上的消息編成一個碼字。目的去相關(guān)性；減少平均碼長。六、范諾(Fano)編碼1.方法及步驟(1)將消息符號按其概率從大到小排列。(2)將排列好消息符號分為概率盡可能相等的兩組，(3)將每次所分的兩組中前一組編為0，前一組編為1。(4)按順序?qū)懗龃a字。每個組只剩下一個消息符號為止。對每組直至的消息符

2、號再分為概率盡可能相等的兩組，……，碼字00111111010011110100110101碼長22334444ABCDEFGHX44221111p(x)解1/4B1/8C1/8D1/4A1/16E1/16p(x)FX求其范諾編碼及編碼效率。例設(shè)消息的概率分布如下，1/16G1/16H編碼效率平均碼長熵(bit),解碼樹圖生成過程GHABCDEF01010101010101從上到下生成1/4B1/8C1/8D1/4A1/16E1/16p(x)FX求其范諾編碼及編碼效率。例設(shè)消息的概率分布如下，1/16G1/16H碼字00111101011101101碼長222344

3、ABCDEFX3222181684p(x)解0.22B0.18C0.16D0.32A0.08E0.04p(x)FX求其范諾編碼及編碼效率。例設(shè)消息的概率分布如下，編碼效率平均碼長熵(bit),解碼樹圖生成過程EFAB0101010101從上到下生成0.22B0.18C0.16D0.32A0.08E0.04p(x)FX求其范諾編碼及編碼效率。例設(shè)消息的概率分布如下，CD碼字0001111101101111010111011碼長23323455ABCDEFGHX熵解編碼效率平均碼長范諾編碼有時會出現(xiàn)0.20B0.16C0.15D0.21A0.14E0.08p(x)FX求

4、其范諾編碼及編碼效率。例設(shè)消息的概率分布如下，0.03G0.03H概率相對較小的消息其碼長反而較短。2120161514833p(x)012.分組問題的探討六、范諾(Fano)編碼通常情況下，不能保證使所分的兩組的概率完全相等，此時就會出現(xiàn)兩種不同的分組方案。比如：ABCDEFGH下面通過幾個例子來探討一下范諾編碼分組問題，從而能發(fā)現(xiàn)范諾編碼的主要不足之處。碼字0011111101001111010111011碼長22333455ABCDEFGHX2816121111115.55.5p(x)熵解一0.055H0.16B0.12C0.11D0.28A0.11E0.11

5、p(x)FX求其范諾編碼及編碼效率。例設(shè)消息的概率分布如下，0.055G編碼效率平均碼長0.440.56010.560.44解一0.055HABCDEFGH2816121111115.55.5p(x)碼字0001111101100111010101101碼長23333344X0.16B0.12C0.11D0.28A0.11E0.11p(x)FX求其范諾編碼及編碼效率。解二例設(shè)消息的概率分布如下，0.055G熵編碼效率平均碼長0.560.44熵編碼效率平均碼長0.58碼字00011110110011010101碼長2333333ABCDEFGX熵解一0.18B0.18

6、C0.14D0.22A0.14E0.10p(x)FX求其范諾編碼及編碼效率。例設(shè)消息的概率分布如下，0.04G編碼效率平均碼長0.422218181414104p(x)解一0.58ABCDEFG2218181414104p(x)碼字001111101001110101101碼長2233344X熵編碼效率平均碼長解二0.18B0.18C0.14D0.22A0.14E0.10p(x)FX求其范諾編碼及編碼效率。例設(shè)消息的概率分布如下，0.04G0.420.400.60熵編碼效率平均碼長(1)在構(gòu)造碼樹時，從根節(jié)點開始到端節(jié)點結(jié)束。(2)編出的碼字不是唯一的。(3)有時出

7、現(xiàn)概率較小的消息其碼長反而較短。3.范諾編碼的特點小結(jié)六、范諾(Fano)編碼(4)如何“恰當(dāng)”分組是范諾編碼的主要問題。都只能保證當(dāng)前步的概率盡可能均勻化(局部最優(yōu))，但不能保證總體最優(yōu)。每一步分組七、霍夫曼(Huffman)編碼思想就是使各符號的概率均勻化，即概率大的消息符號編成短碼，概率小的消息符號編成長碼。當(dāng)時霍夫曼還只是麻省理工學(xué)院(MIT)的一名研究生。霍夫曼編碼是戴維霍夫曼(DavidHuffman)在1952年.他從來沒有為他的工作申請專利，他所得到的補償僅是不必參加信息論課程的考試。了大量的美元。霍夫曼編碼已經(jīng)廣泛地應(yīng)用于計算機科學(xué)、數(shù)據(jù)通訊等