2.8無失真信源編碼ppt課件

1、1第二章 基本信息論2.8 無失真信源編碼(二)2.8 無失真信源編碼無失真信源編碼(二二)五、編碼的一般原則五、編碼的一般原則六、范諾六、范諾(Fano)編碼編碼七、霍夫曼七、霍夫曼(Huffman)編碼編碼八、八、N 次擴展編碼次擴展編碼2第二章 基本信息論2.8 無失真信源編碼(二)五、編碼的一般原則五、編碼的一般原則1. 等概化等概化 使編碼后各個碼元出現(xiàn)的概率盡可能地相等。使編碼后各個碼元出現(xiàn)的概率盡可能地相等。2. 減少平均碼長減少平均碼長 將概率大的消息編成短碼，概率小的消息編成長碼。將概率大的消息編成短碼，概率小的消息編成長碼。3. 消息合并消息合并 將兩個或者兩個以上的消息編

2、成一個碼字。將兩個或者兩個以上的消息編成一個碼字。目的目的去相關(guān)性；去相關(guān)性；減少平均碼長。減少平均碼長。 3第二章 基本信息論2.8 無失真信源編碼(二)六、范諾六、范諾(Fano)編碼編碼1. 方法及步驟方法及步驟(1) 將消息符號按其概率從大到小排列。將消息符號按其概率從大到小排列。(2) 將排列好消息符號分為概率盡可能相等的兩組，將排列好消息符號分為概率盡可能相等的兩組，(3) 將每次所分的兩組中前一組編為將每次所分的兩組中前一組編為0，前一組編為，前一組編為1。(4) 按順序?qū)懗龃a字。按順序?qū)懗龃a字。每個組只剩下一個消息符號為止。每個組只剩下一個消息符號為止。對每組對每組直至直至的消

3、息符號再分為概率盡可能相等的兩組，的消息符號再分為概率盡可能相等的兩組，4第二章 基本信息論2.8 無失真信源編碼(二)碼字碼字00111111010011110100110101碼長碼長22334444ABCDEFGHX44221111p(x)16/解解1/4B1/8C1/8D1/4A1/16E1/16p(x)FX求其范諾編碼及編碼效率。求其范諾編碼及編碼效率。例例 設消息的概率分布如下，設消息的概率分布如下，1/16G1/16H編碼效率編碼效率.%100)( LXH 平均碼長平均碼長 81iiilpL熵熵 81log)(iiippXH,75. 2 75. 2 ( bi t ),( bi t

4、 ),5第二章 基本信息論2.8 無失真信源編碼(二)解解碼樹圖生成過程碼樹圖生成過程GHABXBA,HCDC,HEFE,HG,CDEF01010101010 10 1從從 上上 到到 下下 生生 成成1/4B1/8C1/8D1/4A1/16E1/16p(x)FX求其范諾編碼及編碼效率。求其范諾編碼及編碼效率。例例 設消息的概率分布如下，設消息的概率分布如下，1/16G1/16H6第二章 基本信息論2.8 無失真信源編碼(二)碼字碼字00111101011101101碼長碼長222344ABCDEFX3222181684p(x)100/解解0.22B0.18C0.16D0.32A0.08E0.

5、04p(x)FX求其范諾編碼及編碼效率。求其范諾編碼及編碼效率。例例 設消息的概率分布如下，設消息的概率分布如下，編碼效率編碼效率.%01.98 平均碼長平均碼長,4 . 2 L熵熵3522. 2)( XH( bi t ),( bi t ),7第二章 基本信息論2.8 無失真信源編碼(二)解解碼樹圖生成過程碼樹圖生成過程EFABXBA,FCFDFE,010101010 1從從 上上 到到 下下 生生 成成0.22B0.18C0.16D0.32A0.08E0.04p(x)FX求其范諾編碼及編碼效率。求其范諾編碼及編碼效率。例例 設消息的概率分布如下，設消息的概率分布如下，CD8第二章 基本信息論

6、2.8 無失真信源編碼(二)碼字碼字0001111101101111010111011碼長碼長23323455ABCDEFGHX熵熵,7629. 2)( XH解解編碼效率編碼效率.%3 .97 平均碼長平均碼長,84. 2 L 范諾編碼有時會出現(xiàn)范諾編碼有時會出現(xiàn)0.20B0.16C0.15D0.21A0.14E0.08p(x)FX求其范諾編碼及編碼效率。求其范諾編碼及編碼效率。例例 設消息的概率分布如下，設消息的概率分布如下，0.03G0.03H概率相對較小的消息概率相對較小的消息其碼長反而較短。其碼長反而較短。2120161514833p(x)100/019第二章 基本信息論2.8 無失真

7、信源編碼(二)2. 分組問題的探討分組問題的探討六、范諾六、范諾(Fano)編碼編碼通常情況下，不能保證使所分的兩組的概率完全相等，通常情況下，不能保證使所分的兩組的概率完全相等，此時就會出現(xiàn)兩種不同的分組方案。此時就會出現(xiàn)兩種不同的分組方案。比如：比如：A B C D E F G H5 . 0 p5 . 0 p5 . 0 p5 . 0 p 下面通過幾個例子來探討一下范諾編碼分組問題，下面通過幾個例子來探討一下范諾編碼分組問題，從而能發(fā)現(xiàn)范諾編碼的主要不足之處。從而能發(fā)現(xiàn)范諾編碼的主要不足之處。10第二章 基本信息論2.8 無失真信源編碼(二)碼字碼字001111110100111101011

8、1011碼長碼長22333455ABCDEFGHX2816121111115.55.5p(x)100/熵熵.8155. 2)( XH解一解一0.055H0.16B0.12C0.11D0.28A0.11E0.11p(x)FX求其范諾編碼及編碼效率。求其范諾編碼及編碼效率。例例 設消息的概率分布如下，設消息的概率分布如下，0.055G編碼效率編碼效率.%42.97 平均碼長平均碼長,89. 2 L0.440.560111第二章 基本信息論2.8 無失真信源編碼(二)0.560.44解一解一0.055HABCDEFGH2816121111115.55.5p(x)碼字碼字000111110110011

9、1010101101碼長碼長23333344X0.16B0.12C0.11D0.28A0.11E0.11p(x)FX求其范諾編碼及編碼效率。求其范諾編碼及編碼效率。解二解二例例 設消息的概率分布如下，設消息的概率分布如下，0.055G熵熵編碼效率編碼效率平均碼長平均碼長.8155. 2)( XH.%42.97 ,89. 2 L0.560.44熵熵.8155. 2)( XH編碼效率編碼效率.%49.99 平均碼長平均碼長,83. 2 L100/12第二章 基本信息論2.8 無失真信源編碼(二)0.58碼字碼字00011110110011010101 碼長碼長2333333ABCDEFGX熵熵.6

10、834. 2)( XH解一解一0.18B0.18C0.14D0.22A0.14E0.10p(x)FX求其范諾編碼及編碼效率。求其范諾編碼及編碼效率。例例 設消息的概率分布如下，設消息的概率分布如下，0.04G編碼效率編碼效率.%53.96 平均碼長平均碼長,78. 2 L0.422218181414104p(x)100/13第二章 基本信息論2.8 無失真信源編碼(二)解一解一0.58ABCDEFG2218181414104p(x)碼字碼字001111101001110101101碼長碼長2233344X熵熵編碼效率編碼效率平均碼長平均碼長.6834. 2)( XH解二解二0.18B0.18C

11、0.14D0.22A0.14E0.10p(x)FX求其范諾編碼及編碼效率。求其范諾編碼及編碼效率。例例 設消息的概率分布如下，設消息的概率分布如下，0.04G.%53.96 ,78. 2 L0.420.400.60熵熵.6834. 2)( XH編碼效率編碼效率.%93.97 平均碼長平均碼長,74. 2 L100/14第二章 基本信息論2.8 無失真信源編碼(二)(1) 在構(gòu)造碼樹時，從根節(jié)點開始到端節(jié)點結(jié)束。在構(gòu)造碼樹時，從根節(jié)點開始到端節(jié)點結(jié)束。(2) 編出的碼字不是唯一的。編出的碼字不是唯一的。(3) 有時出現(xiàn)概率較小的消息其碼長反而較短。有時出現(xiàn)概率較小的消息其碼長反而較短。3. 范諾

12、編碼的特點小結(jié)范諾編碼的特點小結(jié)六、范諾六、范諾(Fano)編碼編碼(4) 如何如何“恰當分組是范諾編碼的主要問題。恰當分組是范諾編碼的主要問題。都只能保證當前步的概率盡可能均勻化都只能保證當前步的概率盡可能均勻化(局部最優(yōu)局部最優(yōu))，但不能保證總體最優(yōu)。但不能保證總體最優(yōu)。每一步分組每一步分組15第二章 基本信息論2.8 無失真信源編碼(二)七、霍夫曼七、霍夫曼(Huffman)編碼編碼思想就是使各符號的概率均勻化，即概率大的消息符號編成思想就是使各符號的概率均勻化，即概率大的消息符號編成短碼，概率小的消息符號編成長碼。短碼，概率小的消息符號編成長碼。當時霍夫曼還只是麻省理工學院當時霍夫曼還

13、只是麻省理工學院( M I T )的一名研究生。的一名研究生?；舴蚵幋a是戴維霍夫曼編碼是戴維 霍夫曼霍夫曼 (David Huffman) 在在 1952 年年. 他從來沒有為他的工作申請專利，他所得到的補償僅是不必他從來沒有為他的工作申請專利，他所得到的補償僅是不必參加信息論課程的考試。參加信息論課程的考試。了大量的美元。了大量的美元?；舴蚵幋a已經(jīng)廣泛地應用于計算機科學、數(shù)據(jù)通訊等霍夫曼編碼已經(jīng)廣泛地應用于計算機科學、數(shù)據(jù)通訊等提出的一種變長編碼方法，它是一種最佳編碼方法。提出的一種變長編碼方法，它是一種最佳編碼方法。許多科學與應用領(lǐng)域中。許多科學與應用領(lǐng)域中。其基本其基本而其他人已經(jīng)借

14、助霍夫曼編碼賺到而其他人已經(jīng)借助霍夫曼編碼賺到16第二章 基本信息論2.8 無失真信源編碼(二)七、霍夫曼七、霍夫曼(Huffman)編碼編碼(2) 把概率最小的兩個消息分別編成把概率最小的兩個消息分別編成 “1” 和和 “0” 碼元，碼元，(3) 把上述概率和作為一個新消息的概率，再與剩余的其它把上述概率和作為一個新消息的概率，再與剩余的其它1. 方法及步驟方法及步驟(1) 將消息符號按概率從大到小排列。將消息符號按概率從大到小排列。到最右邊到最右邊 , 將遇到的二元數(shù)字依次由最低位寫到最高位，將遇到的二元數(shù)字依次由最低位寫到最高位，所得到的二元數(shù)字序列即為各個消息的最佳二元編碼。所得到的二

15、元數(shù)字序列即為各個消息的最佳二元編碼。它們的概率和。它們的概率和。消息按概率從大到小重新排列。消息按概率從大到小重新排列。(5) 從最左邊開始，沿著以每個消息為出發(fā)點的路線一直走從最左邊開始，沿著以每個消息為出發(fā)點的路線一直走(4) 重復步驟重復步驟(2)與與(3)，直到所有概率都處理完為止。，直到所有概率都處理完為止。并求并求17第二章 基本信息論2.8 無失真信源編碼(二)0.20B0.16C0.15D0.21A0.14E0.08p(x)FX求其霍夫曼編碼及編碼效率。求其霍夫曼編碼及編碼效率。例例 設消息的概率分布如下，設消息的概率分布如下，0.03G0.03H解解ABCDEFGH2120

16、161514833p100/212016151486012120161514142821201615013128212001413128015941011000101熵熵,763. 2 H平均碼長平均碼長,79. 2 L編碼效率編碼效率.%99 碼字碼字A B C D E F G H 10 11 000 001 010 0110 01110 0111118第二章 基本信息論2.8 無失真信源編碼(二)0.0610.140.410.280.590.310.20B0.16C0.15D0.21A0.14E0.08p(x)FX求其霍夫曼編碼及編碼效率。求其霍夫曼編碼及編碼效率。例例 設消息的概率分布如

17、下，設消息的概率分布如下，0.03G0.03H解解碼樹圖生成過程碼樹圖生成過程從從 下下 到到 上上 生生 成成F0.08E0.14D0.15H0.03B0.20C0.16G0.03A0.210100000011111119第二章 基本信息論2.8 無失真信源編碼(二)解解4422211ABCDEFGH44221111p16/014422224442201444401844018801160101熵熵,75. 2 H平均碼長平均碼長,75. 2 L編碼效率編碼效率.%100 碼字碼字A B C D E F G H 10 11 010 011 0000 0001 0010 00114B2C2D4

18、A1E1p(x)FX求其霍夫曼編碼及編碼效率。求其霍夫曼編碼及編碼效率。例例 設消息的概率分布如下，設消息的概率分布如下，1G1H16/20第二章 基本信息論2.8 無失真信源編碼(二)解解碼樹圖生成過程碼樹圖生成過程E1F1G1H1從從 下下 到到 上上 生生 成成4B2C2D4A1E1p(x)FX求其霍夫曼編碼及編碼效率。求其霍夫曼編碼及編碼效率。例例 設消息的概率分布如下，設消息的概率分布如下，1G1H16/000101010 10 1112168A484B42C2D2421第二章 基本信息論2.8 無失真信源編碼(二)七、霍夫曼七、霍夫曼(Huffman)編碼編碼2. 碼方差較小原則碼

19、方差較小原則在每次對兩個最小的概率求和后，把這個新概率列入在每次對兩個最小的概率求和后，把這個新概率列入其它尚未處理過的概率中重新由大到小排序時，其它尚未處理過的概率中重新由大到小排序時，可以排在相同概率的后面，可以排在相同概率的后面，前者編出來的碼字中個別碼字會相對較長；前者編出來的碼字中個別碼字會相對較長；減少了碼樹的深度減少了碼樹的深度(或級數(shù)或級數(shù))，因此編出來的碼字中各碼字，因此編出來的碼字中各碼字的碼長會相對均勻，的碼長會相對均勻，新概率既新概率既也可以排在相同概率的前面。也可以排在相同概率的前面。后者由于后者由于從而能可獲得較小的碼方差。從而能可獲得較小的碼方差。22第二章 基本

20、信息論2.8 無失真信源編碼(二)解解0.2B0.2C0.1D0.4A0.1Ep(x)X求其霍夫曼編碼及編碼效率。求其霍夫曼編碼及編碼效率。例例 設消息的概率分布如下，設消息的概率分布如下，熵熵,123. 2 H平均碼長平均碼長,2 . 2 L編碼效率編碼效率.%5 .96 碼字碼字A B C D E1 01 000 0010 00114222ABCDE42211p10/014426401100101碼長碼長 1 2 3 4 4 5122)(iiiLlp 碼方差碼方差.36. 1 方法一方法一23第二章 基本信息論2.8 無失真信源編碼(二)100.2B0.2C0.1D0.4A0.1Ep(x)

21、X求其霍夫曼編碼及編碼效率。求其霍夫曼編碼及編碼效率。解解例例 設消息的概率分布如下，設消息的概率分布如下，熵熵,123. 2 H平均碼長平均碼長,2 . 2 L編碼效率編碼效率.%5 .96 碼字碼字A B C D E00 10 11 010 01142220144264010101碼長碼長2 2 2 3 3 5122)(iiiLlp 碼方差碼方差.16. 0 方法二方法二ABCDE42211p10/24第二章 基本信息論2.8 無失真信源編碼(二)0.41.00.20.6E0.1A0.4C0.2B0.2D0.10.1DE0.1C0.2A0.4B0.20.21.00.40.6碼樹圖對比碼樹圖

22、對比0.2B0.2C0.1D0.4A0.1Ep(x)X求其霍夫曼編碼及編碼效率。求其霍夫曼編碼及編碼效率。解解例例 設消息的概率分布如下，設消息的概率分布如下，方法一方法一方法二方法二001110011110000125第二章 基本信息論2.8 無失真信源編碼(二)七、霍夫曼七、霍夫曼(Huffman)編碼編碼(1) 在構(gòu)造碼樹時，從端節(jié)點開始到根節(jié)點結(jié)束。在構(gòu)造碼樹時，從端節(jié)點開始到根節(jié)點結(jié)束。3. 霍夫曼編碼的特點小結(jié)霍夫曼編碼的特點小結(jié)(2) 編出的碼字不是唯一的。編出的碼字不是唯一的。(3) 能保證概率較小的消息其碼長較長。能保證概率較小的消息其碼長較長。(4) 在每次對兩個最小的概率

23、求和后，新的概率一般要排在在每次對兩個最小的概率求和后，新的概率一般要排在相同概率的前面，從而能可獲得較小的碼方差。相同概率的前面，從而能可獲得較小的碼方差。26第二章 基本信息論2.8 無失真信源編碼(二)八、消息合并編碼八、消息合并編碼方法方法將將 N 個消息組合成一個消息后，再編碼，個消息組合成一個消息后，再編碼，消息對應到一個碼字，消息對應到一個碼字，為合并法或延長法。為合并法或延長法。例如例如( (僅以兩次擴展為例僅以兩次擴展為例) )設信源空間為設信源空間為, ,21NxxxX 11xxNxx1j ip11p21pNp112xxNxx2NNxxNp2NNp求出每對消息出現(xiàn)的概率，求

24、出每對消息出現(xiàn)的概率，設每對消息編碼后的平均碼長為設每對消息編碼后的平均碼長為,2L，實實LXH/ )( 編碼效率編碼效率.2/2LL 其中其中即每即每 N 個個此方法稱為此方法稱為 N 次擴展，次擴展，也稱也稱并對其進行編碼。并對其進行編碼。那么那么27第二章 基本信息論2.8 無失真信源編碼(二)某信源產(chǎn)生某信源產(chǎn)生 A , B 兩個獨立消息兩個獨立消息, 其概率分別為其概率分別為 4/5 和和 1/5 , 例例設計一種二元編碼方案設計一種二元編碼方案, 使編碼效率達使編碼效率達 99% 以上。以上。 平均碼長平均碼長,1 L解解(1) 對單個消息直接進行編碼對單個消息直接進行編碼.%2

25、.72)( LXH 編碼效率編碼效率, 1, 0BA.722. 051log5154log54)( XH信源熵信源熵28第二章 基本信息論2.8 無失真信源編碼(二)AAABBABB音訊音訊碼長碼長1233解解(2) 采用兩次擴展的范諾編碼采用兩次擴展的范諾編碼碼字碼字0111011011644125/概率概率,56. 12 L每對消息的平均碼長每對消息的平均碼長.%6 .92/ )( LXH 編碼效率編碼效率,78. 02/2 LL單個消息的平均碼長單個消息的平均碼長某信源產(chǎn)生某信源產(chǎn)生 A , B 兩個獨立消息兩個獨立消息, 其概率分別為其概率分別為 4/5 和和 1/5 , 例例設計一種

26、二元編碼方案設計一種二元編碼方案, 使編碼效率達使編碼效率達 99% 以上。以上。 29第二章 基本信息論2.8 無失真信源編碼(二)解解(3) 采用三次擴展的范諾編碼采用三次擴展的范諾編碼0101碼字碼字01111111001111101011110011碼長碼長13335555AAAAABABABAAABBBABBBABBB音訊音訊125/641616164441概率概率,728. 03/3 LL單個消息的平均碼長單個消息的平均碼長編碼效率編碼效率.%2 .99/ )( LXH 每三個消息的平均碼長每三個消息的平均碼長,184. 23 L某信源產(chǎn)生某信源產(chǎn)生 A , B 兩個獨立消息兩個獨

27、立消息, 其概率分別為其概率分別為 4/5 和和 1/5 , 例例設計一種二元編碼方案設計一種二元編碼方案, 使編碼效率達使編碼效率達 99% 以上。以上。 30第二章 基本信息論2.8 無失真信源編碼(二)ABCA B C 0 3/16 1/163/16 1/8 3/161/16 3/16 0ij),(jip前一個消息前一個消息后一個后一個音訊音訊例例P78 例例某信源可輸出三個消息，某信源可輸出三個消息，其概率分布如表所示。其概率分布如表所示。試設計一種二元編碼方案試設計一種二元編碼方案,使編碼效率達使編碼效率達 85% 以上。以上。 A B C 1/4 1/2 1/4X)(xpABC A

28、 B C 0 3/8 1/43/4 1/4 3/41/4 3/8 0ij)/(ijp前一個消息前一個消息后一個后一個音訊音訊 jiijpjipijH,)/(log),()/(.186. 1bit 無條件熵無條件熵 )(log)()(ipipXH.5 . 1bit 可得實際熵可得實際熵(即條件熵即條件熵)為為解解求出聯(lián)合概率如右表所示，求出聯(lián)合概率如右表所示，31第二章 基本信息論2.8 無失真信源編碼(二)解解平均碼長平均碼長,5 . 1 L(1) 對單個消息直接進行編碼對單個消息直接進行編碼LijH)/( 編碼效率編碼效率碼字碼字01101碼長碼長122BAC音訊音訊2114/概率概率.%1 .79 (2) 采用兩次擴展的范諾編碼采用兩次擴展的范諾編碼先求出每對消息出現(xiàn)的概率：先求出每對消息出現(xiàn)的概率：3/16AB1/16AC3/16BA0AA1/8BB3/16p(x)BCX1/16CA3/16CB0CC32第二章 基本信息論2.8 無失真信源編碼(二)(2) 采用兩次擴展的范諾編碼采用兩次擴展