失真信源編碼 - 2013年最新信息論與編碼（李梅 李亦農(nóng)）課件

1、第五章：無(wú)失真信源編碼一、信源編碼的相關(guān)概念二、定長(zhǎng)碼及定長(zhǎng)信源編碼定理三、變長(zhǎng)碼及變長(zhǎng)信源編碼定理四、變長(zhǎng)碼的編碼方法五、實(shí)用的無(wú)失真信源編碼方法第五章：無(wú)失真信源編碼 信源編碼的作用： 使信源適合于信道的傳輸，用信道能傳輸?shù)姆?hào)來(lái)代表信源發(fā)出的消息； 在不失真或允許一定失真的條件下，用盡可能少的符號(hào)來(lái)傳遞信源消息，提高信息傳輸率。 以提高通信有效性為目的。通常通過(guò)壓縮信源的冗余度來(lái)實(shí)現(xiàn)。采用的一般方法是壓縮每個(gè)信源符號(hào)的平均碼長(zhǎng)。1. 信源編碼概述一、信源編碼的相關(guān)概念第五章：無(wú)失真信源編碼 信源編碼理論是信息論的一個(gè)重要分支，其理論根底是信源編碼的兩個(gè)定理：無(wú)失真信源編碼定理限失真信源編

2、碼定理 本章主要介紹無(wú)失真信源編碼，它實(shí)質(zhì)上是一種統(tǒng)計(jì)匹配編碼，根據(jù)信源的不同概率分布而選用與之相匹配的碼。 1. 信源編碼概述續(xù)1一、信源編碼的相關(guān)概念第五章：無(wú)失真信源編碼 信源的統(tǒng)計(jì)剩余度主要決定于以下兩個(gè)因素 ：1無(wú)記憶信源中，符號(hào)概率分布的非均勻性；2有記憶信源中，符號(hào)間的相關(guān)性及符號(hào)概率分布的非均勻性。 1. 信源編碼概述續(xù)2怎樣壓縮信源的冗余度？1) 去除碼符號(hào)間的相關(guān)性。2) 使碼符號(hào)等概分布。一、信源編碼的相關(guān)概念第五章：無(wú)失真信源編碼2. 信源編碼器模型信宿信道信源編碼器譯碼器YXSS 信源編碼：將信源符號(hào)序列按一定的數(shù)學(xué)規(guī)律映射成碼符號(hào)序列的過(guò)程。 圖1 信源編碼器模型一

3、、信源編碼的相關(guān)概念第五章：無(wú)失真信源編碼 將信源符號(hào)集中的符號(hào) 或者長(zhǎng)為N的信源符號(hào)序列映射成由碼符號(hào) 組成的長(zhǎng)度為 的一一對(duì)應(yīng)的碼符號(hào)序列 。編碼器碼字2. 信源編碼器模型續(xù)1一、信源編碼的相關(guān)概念信源符號(hào)sip(si)碼1碼2s1p(s1)=1/2000s2p(s2)=1/40101s3p(s3)=1/810001s4p(s4)=1/811111例: 5.1第五章：無(wú)失真信源編碼2. 信源編碼器模型續(xù)2一、信源編碼的相關(guān)概念第五章：無(wú)失真信源編碼3. N次擴(kuò)展碼一、信源編碼的相關(guān)概念第五章：無(wú)失真信源編碼3. N次擴(kuò)展碼續(xù)1二次擴(kuò)展信源符號(hào) 二次擴(kuò)展碼碼字一、信源編碼的相關(guān)概念編碼器輸出

4、的碼符號(hào)序列 稱為碼字；長(zhǎng)度 稱為碼字長(zhǎng)度，簡(jiǎn)稱碼長(zhǎng)；全體碼字的集合C稱為碼。假設(shè)碼符號(hào)集合為X=0,1，那么所得的碼字都是二元序列，稱為二元碼。第五章：無(wú)失真信源編碼4. 關(guān)于編碼的一些術(shù)語(yǔ)一、信源編碼的相關(guān)概念將信源符號(hào)集中的每個(gè)信源符號(hào) 固定的映射成某一個(gè)碼字 ，這樣的碼稱為分組碼。 假設(shè)一個(gè)碼中所有碼字的碼長(zhǎng)都相等，那么稱為定長(zhǎng)碼； 否那么為變長(zhǎng)碼。第五章：無(wú)失真信源編碼5. 奇異性假設(shè)一個(gè)碼中所有碼字互不相同，那么稱為非奇異碼；否那么為奇異碼。信源符號(hào)si碼1碼2s1s2s3s401100110100001一、信源編碼的相關(guān)概念第五章：無(wú)失真信源編碼6. 唯一可譯性 假設(shè)任意一串有限

5、長(zhǎng)的碼符號(hào)序列只能被唯一地譯為對(duì)應(yīng)的信源符號(hào)序列，那么稱此碼為唯一可譯碼。信源符號(hào)si碼1碼2碼3s1s2s3s401100110100001010110111一、信源編碼的相關(guān)概念 唯一可譯碼應(yīng)當(dāng)滿足的條件碼字與信源符號(hào)一一對(duì)應(yīng)2) 不同的信源符號(hào)序列對(duì)應(yīng)不同的碼字序列1) 6. 唯一可譯性續(xù)1第五章：無(wú)失真信源編碼一、信源編碼的相關(guān)概念第五章：無(wú)失真信源編碼6. 唯一可譯性續(xù)2例1：1)奇異碼11譯碼奇異碼一定不是唯一可譯碼一、信源編碼的相關(guān)概念第五章：無(wú)失真信源編碼6. 唯一可譯性續(xù)32)非奇異碼01 00 00 100 10 00 01 0譯碼譯碼一、信源編碼的相關(guān)概念第五章：無(wú)失真信

6、源編碼6. 唯一可譯性續(xù)43)等長(zhǎng)碼非奇異碼0 0 0 1 1 0 1 1唯一可譯碼譯碼一、信源編碼的相關(guān)概念第五章：無(wú)失真信源編碼6. 唯一可譯性續(xù)54)唯一可譯碼1 001為非即時(shí)碼1 1 0 1 0 0 1 0 0 0一、信源編碼的相關(guān)概念第五章：無(wú)失真信源編碼6. 唯一可譯性續(xù)65)1 0 1 0 0 1 0 0 0 1唯一可譯碼0 1即時(shí)為即時(shí)碼任何一個(gè)碼字不是其它碼字的前綴一、信源編碼的相關(guān)概念第五章：無(wú)失真信源編碼7. 即時(shí)碼 假設(shè)某個(gè)唯一可譯碼在接收到一個(gè)完整的碼字時(shí)無(wú)需參考后續(xù)的碼符號(hào)就能立即譯碼，那么稱此碼為即時(shí)碼。 問(wèn)題： 1) 判斷下面的碼是否即時(shí)碼？010110111

7、 2) 等長(zhǎng)碼是否即時(shí)碼？一、信源編碼的相關(guān)概念第五章：無(wú)失真信源編碼7. 即時(shí)碼續(xù)1 唯一可譯碼成為即時(shí)碼的充要條件： 定理5.1 一個(gè)唯一可譯碼成為即時(shí)碼的充要條件是其中任何一個(gè)碼字都不是其他碼字的前綴。一、信源編碼的相關(guān)概念信源概率pi 編 碼編碼編碼編碼編碼s11/2000000s21/401011001s31/810100110011s41/811101111101117. 即時(shí)碼續(xù)2第五章：無(wú)失真信源編碼一、信源編碼的相關(guān)概念消息00001001000001001110000101011000111001101010010001111110111110101101101110001

8、0011101101111001101010111111117. 即時(shí)碼續(xù)3第五章：無(wú)失真信源編碼一、信源編碼的相關(guān)概念第五章：無(wú)失真信源編碼8. 即時(shí)碼的構(gòu)造方法用樹(shù)圖法可以方便地構(gòu)造即時(shí)碼。樹(shù)中每個(gè)中間節(jié)點(diǎn)都伸出1至r個(gè)樹(shù)枝，將所有的碼字都安排在終端節(jié)點(diǎn)上就可以得到即時(shí)碼。一、信源編碼的相關(guān)概念8. 即時(shí)碼的構(gòu)造方法續(xù)1 0101010100010011一階節(jié)點(diǎn)二階節(jié)點(diǎn)三階節(jié)點(diǎn)0101100110101111第五章：無(wú)失真信源編碼一、信源編碼的相關(guān)概念第五章：無(wú)失真信源編碼8. 即時(shí)碼的構(gòu)造方法續(xù)2一、信源編碼的相關(guān)概念用樹(shù)圖法可以方便地構(gòu)造即時(shí)碼。樹(shù)中每個(gè)中間節(jié)點(diǎn)都伸出1至r個(gè)樹(shù)枝，將所

9、有的碼字都安排在終端節(jié)點(diǎn)上就可以得到即時(shí)碼。每個(gè)中間節(jié)點(diǎn)都正好有r個(gè)分枝的樹(shù)稱為整樹(shù)滿樹(shù)。所有終端節(jié)點(diǎn)的階數(shù)都相等的樹(shù)為完全樹(shù)第五章：無(wú)失真信源編碼8. 即時(shí)碼的構(gòu)造方法續(xù)3一、信源編碼的相關(guān)概念第五章：無(wú)失真信源編碼圖2 各類碼之間的關(guān)系8. 即時(shí)碼的構(gòu)造方法續(xù)4一、信源編碼的相關(guān)概念1. 唯一可譯定長(zhǎng)碼存在的條件對(duì)于定長(zhǎng)碼，非奇異碼一定是唯一可譯碼。所謂非奇異碼，即信源符號(hào)集中的每一個(gè)信源符號(hào)與碼中的某一個(gè)碼字 一一對(duì)應(yīng)。設(shè)信源符號(hào)集中共有 個(gè)符號(hào)， ， 碼符號(hào)集中共有 種碼元， ， 定長(zhǎng)碼碼長(zhǎng)為 , 那么要滿足非奇異性必然有該條件是必要條件，而不是充分條件。第五章：無(wú)失真信源編碼二、定長(zhǎng)

10、碼及定長(zhǎng)信源編碼定理1. 唯一可譯定長(zhǎng)碼存在的條件續(xù)1如果對(duì)N次擴(kuò)展信源 進(jìn)行定長(zhǎng)編碼，要滿足非奇異性，須滿足條件 其中當(dāng)r=2 時(shí)，第五章：無(wú)失真信源編碼二、定長(zhǎng)碼及定長(zhǎng)信源編碼定理當(dāng)N=1時(shí)，1. 唯一可譯定長(zhǎng)碼存在的條件續(xù)2例2：英文字母表中，每一字母用定長(zhǎng)編碼轉(zhuǎn)換成二進(jìn)制表示，碼字的最短長(zhǎng)度是多少？解：信源符號(hào)數(shù)碼符號(hào)數(shù)第五章：無(wú)失真信源編碼二、定長(zhǎng)碼及定長(zhǎng)信源編碼定理 p(sj) I(sj)/N s1= s1 s1 1/4 1s2= s1 s2 1/8 1.5s3= s1 s3 1/16 2s4= s1 s4 1/16 2s5= s2 s1 1/8 1.5s6= s2 s2 1/16

11、 2s7= s2 s3 1/32 2.5s8= s2 s4 1/32 2.5 p(sj) I(sj)/Ns9 = s3 s1 1/16 2s10= s3 s2 1/32 2.5s11= s3 s3 1/64 3s12= s3 s4 1/64 3s13= s4 s1 1/16 2s14= s4 s2 1/32 2.5s15= s4 s3 1/64 3s16= s4 s4 1/64 3N=2 H(S) = 1.75 第五章：無(wú)失真信源編碼2. 定長(zhǎng)信源編碼定理二、定長(zhǎng)碼及定長(zhǎng)信源編碼定理定理5.3.1 設(shè)離散平穩(wěn)無(wú)記憶信源的熵為H(S), 假設(shè)對(duì)N次擴(kuò)展信源 進(jìn)行定長(zhǎng)編碼，那么對(duì)于任意 0，只要滿

12、足 那么當(dāng)N足夠大時(shí)，可實(shí)現(xiàn)幾乎無(wú)失真編碼，即譯碼錯(cuò)誤概率 PE 為任意??；反之，那么不可能實(shí)現(xiàn)無(wú)失真編碼， 如果 當(dāng)N足夠大時(shí)，譯碼錯(cuò)誤概率 PE 為1。2. 定長(zhǎng)信源編碼定理續(xù)1第五章：無(wú)失真信源編碼 定長(zhǎng)編碼定理同樣也適用于離散平穩(wěn)有記憶信源，差異是要將信源熵 改為極限熵 。二、定長(zhǎng)碼及定長(zhǎng)信源編碼定理可以驗(yàn)證，對(duì)定長(zhǎng)信源編碼來(lái)說(shuō)，要想實(shí)現(xiàn)無(wú)失真信源編碼，N常常要取非常大的值。這在實(shí)際應(yīng)用中很難實(shí)現(xiàn)。2. 定長(zhǎng)信源編碼定理續(xù)2第五章：無(wú)失真信源編碼當(dāng)r=2時(shí)二、定長(zhǎng)碼及定長(zhǎng)信源編碼定理第五章：無(wú)失真信源編碼2. 定長(zhǎng)信源編碼定理續(xù)3定義： 為編碼信息率 定義： 為編碼效率。 比特/信源符

13、號(hào)比特/信源符號(hào)比特/信源符號(hào)二、定長(zhǎng)碼及定長(zhǎng)信源編碼定理第五章：無(wú)失真信源編碼2. 定長(zhǎng)信源編碼定理續(xù)4根據(jù)編碼效率的定義，最正確編碼效率為：在方差和信源熵的條件下，信源符號(hào)序列長(zhǎng)度N與最正確編碼效率和允許編碼錯(cuò)誤概率 之間的關(guān)系為：二、定長(zhǎng)碼及定長(zhǎng)信源編碼定理例 5.2如果對(duì)信源符號(hào)采用定長(zhǎng)二元編碼，要求編碼效率=90%，允許錯(cuò)誤概率 ，求所需信源序列長(zhǎng)度N。 例5.3 設(shè)離散無(wú)記憶信源 , 要求 求N。 第五章：無(wú)失真信源編碼2. 定長(zhǎng)信源編碼定理續(xù)5二、定長(zhǎng)碼及定長(zhǎng)信源編碼定理1. Kraft不等式和McMillan不等式第五章：無(wú)失真信源編碼Kraft定理：即時(shí)碼存在的充要條件是Mc

14、Millan定理：唯一可譯碼存在的充要條件是三、變長(zhǎng)碼及變長(zhǎng)信源編碼定理1. Kraft不等式和McMillan不等式續(xù)1 任何一個(gè)唯一可譯碼均可用一個(gè)相同碼長(zhǎng)的即時(shí)碼來(lái)代替。 上述定理是存在性定理： 當(dāng)滿足Kraft或McMillan不等式時(shí)，必然可以構(gòu)造出即時(shí)碼或唯一可譯碼，否那么不能構(gòu)造出即時(shí)碼或唯一可譯碼。 該定理不能作為判斷一種碼是否是即時(shí)碼或唯一可譯碼的判斷依據(jù)。第五章：無(wú)失真信源編碼三、變長(zhǎng)碼及變長(zhǎng)信源編碼定理信源符號(hào)si符號(hào)出現(xiàn)的概率碼1碼2碼3碼4s10011s211101001s30000100001s41101100000011. Kraft不等式和McMillan不等式

15、續(xù)2第五章：無(wú)失真信源編碼1/21/41/81/8三、變長(zhǎng)碼及變長(zhǎng)信源編碼定理2. 變長(zhǎng)唯一可譯碼判別方法步驟：1.構(gòu)造F1 ：考察 C中所有碼字，如果一個(gè)碼字是另一個(gè)碼字的前綴，那么將后綴作為F1 中的元素。2.構(gòu)造 ：將C 與 比較。如果 C 中有碼字是 中元素的前綴，那么將相應(yīng)的后綴放入 中；同樣 中假設(shè)有元素是 C 中碼字的前綴，也將相應(yīng)的后綴放入 中。3.檢驗(yàn) ： 1)如果 是空集，那么斷定碼 C 是唯一可譯碼，退出循環(huán)； 2)反之，如果 中的某個(gè)元素與 C中的某個(gè)元素相同，那么斷定碼 不是唯一可譯碼，退出循環(huán)。 3)如果上述兩個(gè)條件都不滿足，那么返回步驟2。 第五章：無(wú)失真信源編碼

16、三、變長(zhǎng)碼及變長(zhǎng)信源編碼定理2. 變長(zhǎng)唯一可譯碼判別方法續(xù)C F1 F2 F3 F4 F5a d eb de b adc bb cde bcdeadabbbaddebbbcde例5.4 ：結(jié)論：F5中包含了C中的元素，因此該變長(zhǎng)碼不是唯一可譯碼。第五章：無(wú)失真信源編碼問(wèn)題： 判斷 C=1,10,100,1000是否是唯一可譯碼？三、變長(zhǎng)碼及變長(zhǎng)信源編碼定理3.緊致碼平均碼長(zhǎng)界限定理碼符號(hào)/信源符號(hào) 平均碼長(zhǎng) 對(duì)于給定的信源和碼符號(hào)集，假設(shè)有一個(gè)唯一可譯碼，其平均長(zhǎng)度 小于所有其他唯一可譯碼，那么稱這種碼為緊致碼或最正確碼。 第五章：無(wú)失真信源編碼三、變長(zhǎng)碼及變長(zhǎng)信源編碼定理3.緊致碼平均碼長(zhǎng)界

17、限定理續(xù)1 緊致碼平均碼長(zhǎng)界限定理： 設(shè)離散無(wú)記憶信源的熵為H(S)，用r 個(gè)碼符號(hào)進(jìn)行編碼，那么總可找到一種無(wú)失真信源編碼，構(gòu)成唯一可譯碼，使其平均碼長(zhǎng)滿足： 第五章：無(wú)失真信源編碼三、變長(zhǎng)碼及變長(zhǎng)信源編碼定理定理5.6 緊致碼平均碼長(zhǎng)界限定理3.緊致碼平均碼長(zhǎng)界限定理續(xù)2第五章：無(wú)失真信源編碼三、變長(zhǎng)碼及變長(zhǎng)信源編碼定理3.緊致碼平均碼長(zhǎng)界限定理續(xù)3第五章：無(wú)失真信源編碼平均碼長(zhǎng)=下限值時(shí)三、變長(zhǎng)碼及變長(zhǎng)信源編碼定理3.緊致碼平均碼長(zhǎng)界限定理續(xù)4第五章：無(wú)失真信源編碼三、變長(zhǎng)碼及變長(zhǎng)信源編碼定理4.無(wú)失真變長(zhǎng)信源編碼定理 香農(nóng)第一定理變長(zhǎng)無(wú)失真信源編碼定理： 設(shè)離散無(wú)記憶信源的熵為 H(S

18、) ，它的N次擴(kuò)展信源為 ，對(duì)擴(kuò)展信源 進(jìn)行編碼。總可以找到一種編碼方法，構(gòu)成唯一可譯碼，使平均碼長(zhǎng)滿足： 當(dāng) 時(shí)，有第五章：無(wú)失真信源編碼三、變長(zhǎng)碼及變長(zhǎng)信源編碼定理證明：4.無(wú)失真變長(zhǎng)信源編碼定理續(xù)1第五章：無(wú)失真信源編碼三、變長(zhǎng)碼及變長(zhǎng)信源編碼定理 把香農(nóng)第一定理推廣到一般離散信源，有并且4.無(wú)失真變長(zhǎng)信源編碼定理續(xù)2第五章：無(wú)失真信源編碼三、變長(zhǎng)碼及變長(zhǎng)信源編碼定理bit/信源符號(hào)碼符號(hào)/信源符號(hào)= bit/碼符號(hào)信息傳輸率(碼率)r進(jìn)制單位/信源符號(hào)碼符號(hào)/信源符號(hào)4.無(wú)失真變長(zhǎng)信源編碼定理續(xù)3第五章：無(wú)失真信源編碼編碼效率三、變長(zhǎng)碼及變長(zhǎng)信源編碼定理 例5.5 設(shè)離散無(wú)記憶信源 ,

19、 求 R、及擴(kuò)展信源的R、 。 4.無(wú)失真變長(zhǎng)信源編碼定理續(xù)4第五章：無(wú)失真信源編碼三、變長(zhǎng)碼及變長(zhǎng)信源編碼定理第五章：無(wú)失真信源編碼1. 香農(nóng)碼編碼步驟如下：將信源符號(hào)按概率從大到小順序排列，為方便起見(jiàn)，令 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)的碼字。四、變長(zhǎng)碼的編碼方法1. 香農(nóng)碼續(xù)1例5.6 對(duì)如下信源編碼:第五章：無(wú)失真信源編碼四、變長(zhǎng)碼的編碼方法信源符號(hào)符號(hào)概率累加概率碼長(zhǎng)碼字s10.2002.343000s20.190.22.413001s30.180.392.483011s

20、40.170.572.563100s50.150.742.743101s60.100.593.3441110s70.010.996.66711111101. 香農(nóng)碼續(xù)2第五章：無(wú)失真信源編碼四、變長(zhǎng)碼的編碼方法1. 香農(nóng)碼續(xù)3 平均碼長(zhǎng)信源熵結(jié)論： 1) 2) 香農(nóng)碼是即時(shí)碼，但冗余度稍大，不是最正確碼。編碼效率第五章：無(wú)失真信源編碼四、變長(zhǎng)碼的編碼方法2. 香農(nóng)-費(fèi)諾-埃利斯編碼第五章：無(wú)失真信源編碼四、變長(zhǎng)碼的編碼方法1、不用對(duì)信源符號(hào)按概率大小排序。2、直接計(jì)算修正的累加概率3、計(jì)算碼長(zhǎng) 2. 香農(nóng)-費(fèi)諾-埃利斯編碼續(xù)1第五章：無(wú)失真信源編碼四、變長(zhǎng)碼的編碼方法3. Huffman碼將信

21、源符號(hào)按概率從大到小的順序排列，令給兩個(gè)概率最小的信源符號(hào)sn-1和sn各分配一個(gè)碼元“0和“1，并將這兩個(gè)信源符號(hào)合并成一個(gè)新符號(hào)，并用這兩個(gè)最小的概率之和作為新符號(hào)的概率，結(jié)果得到一個(gè)只包含(n1)個(gè)信源符號(hào)的新信源。稱為信源的第一次縮減信源，用S1表示。將縮減信源S1的符號(hào)仍按概率從大到小順序排列，重復(fù)步驟2，得到只含(n2)個(gè)符號(hào)的縮減信源S2。重復(fù)上述步驟，直至縮減信源只剩兩個(gè)符號(hào)為止，此時(shí)所剩兩個(gè)符號(hào)的概率之和必為1。然后從最后一級(jí)縮減信源開(kāi)始，依編碼路徑向前返回，就得到各信源符號(hào)所對(duì)應(yīng)的碼字。編碼步驟如下：第五章：無(wú)失真信源編碼四、變長(zhǎng)碼的編碼方法3. Huffman碼續(xù)1第五章

22、：無(wú)失真信源編碼四、變長(zhǎng)碼的編碼方法010101013. Huffman碼續(xù)2第五章：無(wú)失真信源編碼四、變長(zhǎng)碼的編碼方法01010101碼符號(hào)/信源符號(hào)3. Huffman碼續(xù)3第五章：無(wú)失真信源編碼四、變長(zhǎng)碼的編碼方法01010101碼符號(hào)/信源符號(hào)3. Huffman碼續(xù)4第五章：無(wú)失真信源編碼四、變長(zhǎng)碼的編碼方法討論：1) 兩種方法平均碼長(zhǎng)相等。2) 計(jì)算兩種碼的碼長(zhǎng)方差：第二種方法編出的碼碼字長(zhǎng)度變化較小，便于實(shí)現(xiàn)。3. Huffman碼續(xù)5第五章：無(wú)失真信源編碼四、變長(zhǎng)碼的編碼方法3. Huffman碼續(xù)6離散信源如下:解：編碼過(guò)程略，Huffman編碼結(jié)果如下：第五章：無(wú)失真信源編

23、碼四、變長(zhǎng)碼的編碼方法3. Huffman碼續(xù)7平均碼長(zhǎng)為信源熵為編碼效率為第五章：無(wú)失真信源編碼四、變長(zhǎng)碼的編碼方法3. Huffman碼續(xù)8注意：霍夫曼編碼后的碼字不是惟一的。1每次對(duì)縮減信源兩個(gè)概率最小的符號(hào)分配“0或“1碼元是任意的，所以可得到不同的碼字。不同的碼元分配，得到的具體碼字不同，但碼長(zhǎng)li不變，平均碼長(zhǎng)也不變，所以沒(méi)有本質(zhì)區(qū)別；2縮減信源時(shí)，假設(shè)合并后的概率與其他概率相等，這幾個(gè)概率的次序可任意排列，但得到的碼字不相同,對(duì)應(yīng)的碼長(zhǎng)也不相同,但平均碼長(zhǎng)也不變。第五章：無(wú)失真信源編碼四、變長(zhǎng)碼的編碼方法定理5.8 霍夫曼碼是緊致碼01010101101000001100013.

24、 Huffman碼續(xù)9第五章：無(wú)失真信源編碼四、變長(zhǎng)碼的編碼方法假定縮減后信源為 共有m個(gè)元素。 縮減后信源為 共有m+1個(gè)元素。其中第k個(gè)元素碼長(zhǎng) ,概率為最短那么縮減前4. r 元霍夫曼碼第五章：無(wú)失真信源編碼四、變長(zhǎng)碼的編碼方法0120120124. r 元霍夫曼碼續(xù)1第五章：無(wú)失真信源編碼四、變長(zhǎng)碼的編碼方法4. r 元霍夫曼碼續(xù)2第五章：無(wú)失真信源編碼四、變長(zhǎng)碼的編碼方法5. Fano碼編碼步驟如下：將概率按從大到小的順序排列，令將依次排列的信源符號(hào)按概率分成兩組，使每組概率和盡可能接近或相等。給每一組分配一位碼元“0或“1。將每一分組再按同樣方法劃分，重復(fù)步驟2和3，直至概率不再可

25、分為止。第五章：無(wú)失真信源編碼四、變長(zhǎng)碼的編碼方法5. Fano碼續(xù)1例第五章：無(wú)失真信源編碼四、變長(zhǎng)碼的編碼方法5. Fano碼續(xù)2解：信源符號(hào)符號(hào)概率第一次分組第一次分組第一次分組第一次分組碼字碼長(zhǎng)0.20000020.191001030.18101130.17101020.151011030.1010111040.01111114第五章：無(wú)失真信源編碼四、變長(zhǎng)碼的編碼方法5. Fano碼續(xù)3平均碼長(zhǎng)為信源熵為編碼效率為第五章：無(wú)失真信源編碼四、變長(zhǎng)碼的編碼方法5. Fano碼續(xù)4四、變長(zhǎng)碼的編碼方法香農(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ì)特性沒(méi)有特殊要求，編碼效率比較高，對(duì)編碼設(shè)備的要求也比較簡(jiǎn)單，因此綜合性能優(yōu)于香農(nóng)碼和費(fèi)諾碼。第五章：無(wú)失真信源編碼四、變長(zhǎng)碼的編碼方