《信息論基礎(chǔ)教程》第二版PPT課件

《信息論基礎(chǔ)教程》第二版PPT課件,信息論基礎(chǔ)教程,信息論,基礎(chǔ)教程,第二,PPT,課件 第五章：無失真信源編碼一、信源編碼的相關(guān)概念一、信源編碼的相關(guān)概念二、定長碼及定長信源編碼定理二、定長碼及定長信源編碼定理三、變長碼及變長信源編碼定理三、變長碼及變長信源編碼定理四、變長碼的編碼方法四、變長碼的編碼方法五、實(shí)用的無失真信源編碼方法五、實(shí)用的無失真信源編碼方法第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼l 信源編碼的作用：信源編碼的作用：使信源適合于信道的傳輸，用信道能傳輸?shù)姆杹泶剐旁催m合于信道的傳輸，用信道能傳輸?shù)姆杹泶硇旁窗l(fā)出的消息；表信源發(fā)出的消息；在不失真或允許一定失真的條件下，用盡可能少的符在不失真或允許一定失真的條件下，用盡可能少的符號來傳遞信源消息，提高信息傳輸率。號來傳遞信源消息，提高信息傳輸率。l 以提高通信有效性為目的以提高通信有效性為目的。通常通過。通常通過壓縮信源的冗余壓縮信源的冗余度度來實(shí)現(xiàn)。采用的一般方法是壓縮每個信源符號的平均來實(shí)現(xiàn)。采用的一般方法是壓縮每個信源符號的平均碼長碼長。1.信源編碼概述一、信源編碼的相關(guān)概念一、信源編碼的相關(guān)概念第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼l 信源編碼理論是信息論的一個重要分支，其理論基礎(chǔ)信源編碼理論是信息論的一個重要分支，其理論基礎(chǔ)是信源編碼的兩個定理：是信源編碼的兩個定理：無失真信源編碼定理無失真信源編碼定理限失真信源編碼定理限失真信源編碼定理l 本章主要介紹本章主要介紹無失真信源編碼無失真信源編碼，它實(shí)質(zhì)上是一種統(tǒng)，它實(shí)質(zhì)上是一種統(tǒng)計匹配編碼，根據(jù)信源的不同概率分布而選用與之相計匹配編碼，根據(jù)信源的不同概率分布而選用與之相匹配的碼。匹配的碼。1.信源編碼概述（續(xù)1）一、信源編碼的相關(guān)概念一、信源編碼的相關(guān)概念第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼l 信源的統(tǒng)計剩余度主要決定于以下兩個因素信源的統(tǒng)計剩余度主要決定于以下兩個因素：1）無記憶信源中，符號概率分布的非均勻性；）無記憶信源中，符號概率分布的非均勻性；2）有記憶信源中，符號間的相關(guān)性及）有記憶信源中，符號間的相關(guān)性及符號概率分布符號概率分布的非均勻性的非均勻性。1.信源編碼概述（續(xù)2）l怎樣壓縮信源的冗余度？怎樣壓縮信源的冗余度？1)去除碼符號間的相關(guān)性。去除碼符號間的相關(guān)性。2)使碼符號等概分布。使碼符號等概分布。一、信源編碼的相關(guān)概念一、信源編碼的相關(guān)概念第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼2.信源編碼器模型信宿信道信源編碼器譯碼器YXSSl 信源編碼：將信源符號序列按一定的數(shù)學(xué)規(guī)律映射成碼符號序列的過程。圖1 信源編碼器模型一、信源編碼的相關(guān)概念一、信源編碼的相關(guān)概念第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼l 將信源符號集中的符號（或者長為N的信源符號序列）映射成由碼符號 組成的長度為 的一一對應(yīng)的碼符號序列 。編碼器碼字2.信源編碼器模型（續(xù)1）一、信源編碼的相關(guān)概念一、信源編碼的相關(guān)概念信源符號sip(si)碼1碼2s1p(s1)=1/2000s2p(s2)=1/40101s3p(s3)=1/810001s4p(s4)=1/811111例例:5.1第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼2.信源編碼器模型（續(xù)2）一、信源編碼的相關(guān)概念一、信源編碼的相關(guān)概念第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼3.N次擴(kuò)展碼一、信源編碼的相關(guān)概念一、信源編碼的相關(guān)概念第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼3.N次擴(kuò)展碼（續(xù)1）二次擴(kuò)展信源符號 二次擴(kuò)展碼碼字一、信源編碼的相關(guān)概念一、信源編碼的相關(guān)概念l編碼器輸出的碼符號序列 稱為碼字碼字；長度 稱為碼字長度，簡稱碼長碼長；全體碼字的集合C稱為碼碼。l若碼符號集合為X=0,1，則所得的碼字都是二元序列，稱為二元碼二元碼。第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼4.關(guān)于編碼的一些術(shù)語一、信源編碼的相關(guān)概念一、信源編碼的相關(guān)概念l將信源符號集中的每個信源符號 固定的映射成某一個碼字 ，這樣的碼稱為分組碼分組碼。l若一個碼中所有碼字的碼長都相等，則稱為定長碼定長碼；否則為變長碼變長碼。第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼5.奇異性若一個碼中所有碼字互不相同，則稱為非奇異碼非奇異碼；否則為奇異碼奇異碼。信源符號si碼1碼2s1s2s3s401100110100001一、信源編碼的相關(guān)概念一、信源編碼的相關(guān)概念第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼6.唯一可譯性l 若任意一串有限長的碼符號序列只能被唯一地譯為對應(yīng)的信源符號序列，則稱此碼為唯一可譯碼唯一可譯碼。信源符號si碼1碼2碼3s1s2s3s401100110100001010110111一、信源編碼的相關(guān)概念一、信源編碼的相關(guān)概念l 唯一可譯碼應(yīng)當(dāng)滿足的條件碼字與信源符號一一對應(yīng)2)不同的信源符號序列對應(yīng)不同的碼字序列1)6.唯一可譯性（續(xù)1）第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼一、信源編碼的相關(guān)概念一、信源編碼的相關(guān)概念第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼6.唯一可譯性（續(xù)2）例1：1)奇異碼11譯碼奇異碼一定不是唯一可譯碼一、信源編碼的相關(guān)概念一、信源編碼的相關(guān)概念第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼6.唯一可譯性（續(xù)3）2)非奇異碼0 1 00 00 1 00 10 00 0 1 0譯碼譯碼一、信源編碼的相關(guān)概念一、信源編碼的相關(guān)概念第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼6.唯一可譯性（續(xù)4）3)等長碼非奇異碼0 0 0 1 1 0 1 1唯一可譯碼譯碼一、信源編碼的相關(guān)概念一、信源編碼的相關(guān)概念第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼6.唯一可譯性（續(xù)5）4)唯一可譯碼1 001為非即時碼1 1 0 1 0 0 1 0 0 0一、信源編碼的相關(guān)概念一、信源編碼的相關(guān)概念第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼6.唯一可譯性（續(xù)6）5)1 0 1 0 0 1 0 0 0 1唯一可譯碼0 1即時為即時碼任何一個碼字不是其它碼字的前綴任何一個碼字不是其它碼字的前綴一、信源編碼的相關(guān)概念一、信源編碼的相關(guān)概念第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼7.即時碼l 若某個唯一可譯碼在接收到一個完整的碼字時無需參考后續(xù)的碼符號就能立即譯碼，則稱此碼為即時碼即時碼。l 問題：1)判斷下面的碼是否即時碼？010110111 2)等長碼是否即時碼？一、信源編碼的相關(guān)概念一、信源編碼的相關(guān)概念第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼7.即時碼（續(xù)1）l 唯一可譯碼成為即時碼的充要條件唯一可譯碼成為即時碼的充要條件：定理定理5.1 一個唯一可譯碼成為即時碼的充要條件是其一個唯一可譯碼成為即時碼的充要條件是其中任何一個碼字都不是其他碼字的前綴。中任何一個碼字都不是其他碼字的前綴。一、信源編碼的相關(guān)概念一、信源編碼的相關(guān)概念信源概率pi 編 碼編 碼編 碼編 碼編 碼s11/2000000s21/401011001s31/810100110011s41/811101111101117.即時碼（續(xù)2）第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼一、信源編碼的相關(guān)概念一、信源編碼的相關(guān)概念消息000010010000010011100001010110001110011010100100011111101111101011011011100010011101101111001101010111111117.即時碼（續(xù)3）第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼一、信源編碼的相關(guān)概念一、信源編碼的相關(guān)概念第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼8.即時碼的構(gòu)造方法l用樹圖法可以方便地構(gòu)造即時碼。樹中每個中間節(jié)點(diǎn)都伸出1至r個樹枝，將所有的碼字都安排在終端將所有的碼字都安排在終端節(jié)點(diǎn)上節(jié)點(diǎn)上就可以得到即時碼。一、信源編碼的相關(guān)概念一、信源編碼的相關(guān)概念8.即時碼的構(gòu)造方法（續(xù)1）0101010100010 011一階節(jié)點(diǎn)二階節(jié)點(diǎn)三階節(jié)點(diǎn)0101100110101111第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼一、信源編碼的相關(guān)概念一、信源編碼的相關(guān)概念第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼8.即時碼的構(gòu)造方法（續(xù)2）一、信源編碼的相關(guān)概念一、信源編碼的相關(guān)概念用樹圖法可以方便地構(gòu)造即時碼。樹中每個中間節(jié)點(diǎn)都伸出1至r個樹枝，將所有的碼字都安排在終端節(jié)點(diǎn)上就可以得到即時碼。每個中間節(jié)點(diǎn)都正好有r個分枝的樹稱為整樹（滿整樹（滿樹）。樹）。所有終端節(jié)點(diǎn)的階數(shù)都相等的樹為完全樹完全樹第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼8.即時碼的構(gòu)造方法（續(xù)3）一、信源編碼的相關(guān)概念一、信源編碼的相關(guān)概念第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼圖2 各類碼之間的關(guān)系8.即時碼的構(gòu)造方法（續(xù)4）一、信源編碼的相關(guān)概念一、信源編碼的相關(guān)概念1.唯一可譯定長碼存在的條件l對于定長碼，非奇異碼一定是唯一可譯碼。l所謂非奇異碼，即信源符號集中的每一個信源符號與碼中的某一個碼字 一一對應(yīng)。l設(shè)信源符號集中共有 個符號，碼符號集中共有 種碼元，定長碼碼長為 ,則要滿足非奇異性必然有該條件是必要條件，而不是充分條件。該條件是必要條件，而不是充分條件。第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼二、定長碼及定長信源編碼定理二、定長碼及定長信源編碼定理1.唯一可譯定長碼存在的條件（續(xù)1）l如果對N次擴(kuò)展信源 進(jìn)行定長編碼，要滿足非奇異性，須滿足條件 其中當(dāng)r=2 時，第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼二、定長碼及定長信源編碼定理二、定長碼及定長信源編碼定理當(dāng)N=1時，1.唯一可譯定長碼存在的條件（續(xù)2）例2：英文字母表中，每一字母用定長編碼轉(zhuǎn)換成二進(jìn)制表示，碼字的最短長度是多少？解：信源符號數(shù)碼符號數(shù)第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼二、定長碼及定長信源編碼定理二、定長碼及定長信源編碼定理 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 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 第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼2.定長信源編碼定理二、定長碼及定長信源編碼定理二、定長碼及定長信源編碼定理l定理5.3.1 設(shè)離散平穩(wěn)無記憶信源的熵為H(S),若對N次擴(kuò)展信源 進(jìn)行定長編碼，則對于任意 0，只要滿足 則當(dāng)N足夠大時，可實(shí)現(xiàn)幾乎無失真編碼，即譯碼錯誤概率 PE 為任意??；反之，則不可能實(shí)現(xiàn)無失真編碼，如果 當(dāng)N足夠大時，譯碼錯誤概率 PE 為1。2.定長信源編碼定理（續(xù)1）第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼l 定長編碼定理同樣也適用于離散平穩(wěn)有記憶信源，差別是要將信源熵 改為極限熵 。二、定長碼及定長信源編碼定理二、定長碼及定長信源編碼定理l可以驗(yàn)證，對定長信源編碼來說，要想實(shí)現(xiàn)無失真信源編碼，N常常要取非常大的值。這在實(shí)際應(yīng)用中很難實(shí)現(xiàn)。2.定長信源編碼定理（續(xù)2）第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼當(dāng)r=2時二、定長碼及定長信源編碼定理二、定長碼及定長信源編碼定理第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼2.定長信源編碼定理（續(xù)3）定義：為編碼信息率編碼信息率 定義：為編碼效率編碼效率。比特/信源符號比特/信源符號比特比特/信源符號信源符號二、定長碼及定長信源編碼定理二、定長碼及定長信源編碼定理第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼2.定長信源編碼定理（續(xù)4）根據(jù)編碼效率的定義，最佳編碼效率為：在已知方差和信源熵的條件下，信源符號序列長度N與最佳編碼效率和允許編碼錯誤概率 之間的關(guān)系為：二、定長碼及定長信源編碼定理二、定長碼及定長信源編碼定理例 5.2如果對信源符號采用定長二元編碼，要求編碼效率=90%，允許錯誤概率 ，求所需信源序列長度N。例5.3 設(shè)離散無記憶信源 ,要求 求N。第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼2.定長信源編碼定理（續(xù)5）二、定長碼及定長信源編碼定理二、定長碼及定長信源編碼定理1.Kraft不等式和McMillan不等式第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼Kraft定理：即時碼存在的充要條件是McMillan定理：唯一可譯碼存在的充要條件是三、變長碼及變長信源編碼定理三、變長碼及變長信源編碼定理1.Kraft不等式和McMillan不等式（續(xù)1）l 任何一個唯一可譯碼均可用一個相同碼長的即時碼來代替。l 上述定理是存在性定理：當(dāng)滿足Kraft（或McMillan）不等式時，必然可以構(gòu)造出即時碼（或唯一可譯碼），否則不能構(gòu)造出即時碼（或唯一可譯碼）。該定理不能作為判斷一種碼是否是即時碼（或唯一可譯碼）的判斷依據(jù)。第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼三、變長碼及變長信源編碼定理三、變長碼及變長信源編碼定理信源符號si符號出現(xiàn)的概率碼1碼2碼3碼4s10011s211101001s30000100001s41101100000011.Kraft不等式和McMillan不等式（續(xù)2）第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼1/21/41/81/8三、變長碼及變長信源編碼定理三、變長碼及變長信源編碼定理2.變長唯一可譯碼判別方法步驟：1.構(gòu)構(gòu)造造F1：考察 C中所有碼字，如果一個碼字是另一個碼字的前綴，則將后綴作為F1 中的元素。2.構(gòu)構(gòu)造造 ：將C 與 比較。如果 C 中有碼字是 中元素的前綴，則將相應(yīng)的后綴放入 中；同樣 中若有元素是 C 中碼字的前綴，也將相應(yīng)的后綴放入 中。3.檢驗(yàn)檢驗(yàn) ：1)如果 是空集，則斷定碼 C 是唯一可譯碼，退出循環(huán)；2)反之，如果 中的某個元素與 C中的某個元素相同，則斷定碼 不是唯一可譯碼，退出循環(huán)。3)如果上述兩個條件都不滿足，則返回步驟2。第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼三、變長碼及變長信源編碼定理三、變長碼及變長信源編碼定理2.變長唯一可譯碼判別方法（續(xù)）C F1 F2 F3 F4 F5a d eb de b adc bb cde bcdeadabbbaddebbbcde例5.4：結(jié)論：F5中包含了C中的元素，因此該變長碼不是唯一可譯碼。第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼問題：判斷 C=1,10,100,1000是否是唯一可譯碼？三、變長碼及變長信源編碼定理三、變長碼及變長信源編碼定理3.緊致碼平均碼長界限定理碼符號/信源符號l 平均碼長l 對于給定的信源和碼符號集，若有一個唯一可譯碼，其平均長度 小于所有其他唯一可譯碼，則稱這種碼為緊致碼緊致碼或最佳碼最佳碼。第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼三、變長碼及變長信源編碼定理三、變長碼及變長信源編碼定理3.緊致碼平均碼長界限定理（續(xù)1）l 緊致碼平均碼長界限定理緊致碼平均碼長界限定理：設(shè)離散無記憶信源的熵為設(shè)離散無記憶信源的熵為H(S)，用，用r 個碼符號進(jìn)行個碼符號進(jìn)行編碼，則總可找到一種無失真信源編碼，構(gòu)成唯一可譯編碼，則總可找到一種無失真信源編碼，構(gòu)成唯一可譯碼，使其平均碼長滿足：碼，使其平均碼長滿足：第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼三、變長碼及變長信源編碼定理三、變長碼及變長信源編碼定理定理定理5.6 緊致碼平均碼長界限定理緊致碼平均碼長界限定理3.緊致碼平均碼長界限定理（續(xù)2）第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼三、變長碼及變長信源編碼定理三、變長碼及變長信源編碼定理3.緊致碼平均碼長界限定理（續(xù)3）第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼平均碼長=下限值時三、變長碼及變長信源編碼定理三、變長碼及變長信源編碼定理3.緊致碼平均碼長界限定理（續(xù)4）第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼三、變長碼及變長信源編碼定理三、變長碼及變長信源編碼定理4.無失真變長信源編碼定理l 香農(nóng)第一定理（變長無失真信源編碼定理）：設(shè)離散無記憶信源的熵為 H(S)，它的N次擴(kuò)展信源為 ，對擴(kuò)展信源 進(jìn)行編碼。總可以找到一種編碼方法，構(gòu)成唯一可譯碼，使平均碼長滿足：l 當(dāng) 時，有第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼三、變長碼及變長信源編碼定理三、變長碼及變長信源編碼定理證明：4.無失真變長信源編碼定理（續(xù)1）第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼三、變長碼及變長信源編碼定理三、變長碼及變長信源編碼定理l 把香農(nóng)第一定理推廣到一般離散信源，有并且4.無失真變長信源編碼定理（續(xù)2）第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼三、變長碼及變長信源編碼定理三、變長碼及變長信源編碼定理bit/信源符號碼符號/信源符號=bit/碼符號信息傳輸率(碼率)r進(jìn)制單位/信源符號碼符號/信源符號4.無失真變長信源編碼定理（續(xù)3）第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼編碼效率三、變長碼及變長信源編碼定理三、變長碼及變長信源編碼定理 例5.5 設(shè)離散無記憶信源 ,求 R、及擴(kuò)展信源的R、。4.無失真變長信源編碼定理（續(xù)4）第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼三、變長碼及變長信源編碼定理三、變長碼及變長信源編碼定理第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼1.香農(nóng)碼編碼步驟如下：編碼步驟如下：1.將信源符號按概率從大到小順序排列，為方便起見，令將信源符號按概率從大到小順序排列，為方便起見，令 2.按下式計算第按下式計算第i個符號對應(yīng)的碼字的碼長（要取整）個符號對應(yīng)的碼字的碼長（要取整）3.計算第計算第i個符號的累加概率個符號的累加概率4.將累加概率變換成二進(jìn)制小數(shù)，取小數(shù)點(diǎn)后將累加概率變換成二進(jìn)制小數(shù)，取小數(shù)點(diǎn)后li位數(shù)作為第位數(shù)作為第i個符號的碼字。個符號的碼字。四、變長碼的編碼方法四、變長碼的編碼方法1.香農(nóng)碼（續(xù)1）例5.6 對如下信源編碼:第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼四、變長碼的編碼方法四、變長碼的編碼方法信源符號符號概率累加概率碼長碼字s10.2002.343000s20.190.22.413001s30.180.392.483011s40.170.572.563100s50.150.742.743101s60.100.593.3441110s70.010.996.66711111101.香農(nóng)碼（續(xù)2）第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼四、變長碼的編碼方法四、變長碼的編碼方法1.香農(nóng)碼（續(xù)3）平均碼長平均碼長信源熵信源熵結(jié)論：結(jié)論：1)2)香農(nóng)碼是即時碼，但冗余度稍大，不是最佳碼。香農(nóng)碼是即時碼，但冗余度稍大，不是最佳碼。編碼效率編碼效率第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼四、變長碼的編碼方法四、變長碼的編碼方法2.香農(nóng)-費(fèi)諾-埃利斯編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼四、變長碼的編碼方法四、變長碼的編碼方法1、不用對信源符號按概率大小排序。2、直接計算修正的累加概率3、計算碼長 2.香農(nóng)-費(fèi)諾-埃利斯編碼（續(xù)1）第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼四、變長碼的編碼方法四、變長碼的編碼方法3.Huffman碼1.將信源符號按概率從大到小的順序排列，令將信源符號按概率從大到小的順序排列，令2.給兩個概率最小的信源符號給兩個概率最小的信源符號sn-1和和sn各分配一個碼元各分配一個碼元“0”和和“1”，并將這，并將這兩個信源符號合并成一個新符號，并用這兩個最小的概率之和作為新符號兩個信源符號合并成一個新符號，并用這兩個最小的概率之和作為新符號的概率，結(jié)果得到一個只包含的概率，結(jié)果得到一個只包含(n1)個信源符號的新信源。稱為個信源符號的新信源。稱為信源的第信源的第一次縮減信源一次縮減信源，用，用S1表示。表示。3.將縮減信源將縮減信源S1的符號仍按概率從大到小順序排列，的符號仍按概率從大到小順序排列，重復(fù)步驟重復(fù)步驟2，得到只含，得到只含(n2)個符號的縮減信源個符號的縮減信源S2。4.重復(fù)上述步驟，直至縮減信源只剩兩個符號為止，此時所剩兩個符號的概重復(fù)上述步驟，直至縮減信源只剩兩個符號為止，此時所剩兩個符號的概率之和必為率之和必為1。然后從最后一級縮減信源開始，依編碼路徑向前返回，就。然后從最后一級縮減信源開始，依編碼路徑向前返回，就得到各信源符號所對應(yīng)的碼字。得到各信源符號所對應(yīng)的碼字。編碼步驟如下：編碼步驟如下：第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼四、變長碼的編碼方法四、變長碼的編碼方法3.Huffman碼（續(xù)1）第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼四、變長碼的編碼方法四、變長碼的編碼方法010101013.Huffman碼（續(xù)2）第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼四、變長碼的編碼方法四、變長碼的編碼方法01010101碼符號/信源符號3.Huffman碼（續(xù)3）第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼四、變長碼的編碼方法四、變長碼的編碼方法01010101碼符號/信源符號3.Huffman碼（續(xù)4）第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼四、變長碼的編碼方法四、變長碼的編碼方法討論：1)兩種方法平均碼長相等。2)計算兩種碼的碼長方差：第二種方法編出的碼碼字長度變化較小，便于實(shí)現(xiàn)。3.Huffman碼（續(xù)5）第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼四、變長碼的編碼方法四、變長碼的編碼方法3.Huffman碼（續(xù)6）離散信源如下:解：編碼過程略，Huffman編碼結(jié)果如下：第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼四、變長碼的編碼方法四、變長碼的編碼方法3.Huffman碼（續(xù)7）l平均碼長為平均碼長為l信源熵為信源熵為l編碼效率為編碼效率為第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼四、變長碼的編碼方法四、變長碼的編碼方法3.Huffman碼（續(xù)8）注意注意：霍夫曼編碼后的碼字不是惟一的。：霍夫曼編碼后的碼字不是惟一的。1 1）每次對縮減信源兩個概率最小的符號）每次對縮減信源兩個概率最小的符號分配分配“0”0”或或“1”1”碼元碼元是任意的是任意的，所以可得到不同的碼字。不同的碼元分配，得到的，所以可得到不同的碼字。不同的碼元分配，得到的具體碼字不同，但碼長具體碼字不同，但碼長li不變，平均碼長也不變，所以沒有本不變，平均碼長也不變，所以沒有本質(zhì)區(qū)別；質(zhì)區(qū)別；2 2）縮減信源時，）縮減信源時，若合并后的概率與其他概率相等，這幾個概率若合并后的概率與其他概率相等，這幾個概率的次序可任意排列的次序可任意排列，但得到的碼字不相同，但得到的碼字不相同,對應(yīng)的碼長也不相對應(yīng)的碼長也不相同同,但平均碼長也不變但平均碼長也不變。第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼四、變長碼的編碼方法四、變長碼的編碼方法定理5.8 霍夫曼碼是緊致碼01010101101000001100013.Huffman碼（續(xù)9）第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼四、變長碼的編碼方法四、變長碼的編碼方法假定縮減后信源為 共有m個元素?？s減后信源為 共有m+1個元素。其中第k個元素碼長 ,概率為最短則縮減前4.r 元霍夫曼碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼四、變長碼的編碼方法四、變長碼的編碼方法0120120124.r 元霍夫曼碼（續(xù)1）第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼四、變長碼的編碼方法四、變長碼的編碼方法4.r 元霍夫曼碼（續(xù)2）第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼四、變長碼的編碼方法四、變長碼的編碼方法5.Fano碼編碼步驟如下：1.將概率按從大到小的順序排列，令2.將依次排列的信源符號按概率分成兩組，使每組概率和盡可能接近或相等。3.給每一組分配一位碼元“0”或“1”。4.將每一分組再按同樣方法劃分，重復(fù)步驟2和3，直至概率不再可分為止。第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼四、變長碼的編碼方法四、變長碼的編碼方法5.Fano碼（續(xù)1）例第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼四、變長碼的編碼方法四、變長碼的編碼方法5.Fano碼（續(xù)2）解：信源符號符號概率第一次分組第一次分組第一次分組第一次分組碼字碼長0.20000020.191001030.18101130.17101020.151011030.1010111040.01111114第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼四、變長碼的編碼方法四、變長碼的編碼方法5.Fano碼（續(xù)3）l平均碼長為平均碼長為l信源熵為信源熵為l編碼效率為編碼效率為第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼四、變長碼的編碼方法四、變長碼的編碼方法5.Fano碼（續(xù)4）四、變長碼的編碼方法四、變長碼的編碼方法香農(nóng)碼、Huffman碼、Fano碼總結(jié)l香農(nóng)碼、費(fèi)諾碼、霍霍夫曼碼都考慮了信源的統(tǒng)計特性，使經(jīng)常出現(xiàn)的信源符號對應(yīng)較短的碼字，使信源的平均碼長縮短，從而實(shí)現(xiàn)了對信源的壓縮。l香農(nóng)碼編碼結(jié)果唯一，但在很多情況下編碼效率不是很高。l費(fèi)諾碼和霍霍夫曼碼的編碼方法都不唯一。l費(fèi)諾碼比較適合于對分組概率相等或接近的信源編碼。l霍霍夫曼碼對信源的統(tǒng)計特性沒有特殊要求，編碼效率比較高，對編碼設(shè)備的要求也比較簡單，因此綜合性能優(yōu)于香農(nóng)碼和費(fèi)諾碼。第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼四、變長碼的編碼方法四、變長碼的編碼方法首先是速率匹配問題其次是差錯擴(kuò)散問題第三是霍霍夫曼碼需要查表來進(jìn)行編譯碼。信源統(tǒng)計特性未知時，怎么辦？可采用所謂通用編碼的方法。Huffman碼編碼應(yīng)用中的一些問題第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼01 00 00 100 10 00 01 0譯碼譯碼四、變長碼的編碼方法四、變長碼的編碼方法第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼五、實(shí)用的無失真信源編碼方法五、實(shí)用的無失真信源編碼方法游程編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼五、實(shí)用的無失真信源編碼方法五、實(shí)用的無失真信源編碼方法游程編碼（續(xù)1）BBBBBBBBBBXXXXXXXXXAAAAAAUUUUUUUUUUUUU 符號碼標(biāo)識碼游程長度編碼：B#10X#9A#6U#13 對于黑、白二值文件:1、黑白游程總是交替出現(xiàn)，可以規(guī)定第一游程為白游程。2、不同游程長度出現(xiàn)的概率不同，對游程長度進(jìn)行編碼采用霍夫曼編碼，概率大的編長碼，概率小的編短碼。第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼五、實(shí)用的無失真信源編碼方法五、實(shí)用的無失真信源編碼方法游程編碼（續(xù)2）第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼五、實(shí)用的無失真信源編碼方法五、實(shí)用的無失真信源編碼方法l73白游程=64+9：1101110100l001101010100101101010110111101100001100110011000000000001 0白1黑15白4黑77白5黑 壓縮比=1728/47=36.7:1 結(jié)尾碼組合基干碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼五、實(shí)用的無失真信源編碼方法五、實(shí)用的無失真信源編碼方法算術(shù)編碼 10001001 第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼五、實(shí)用的無失真信源編碼方法五、實(shí)用的無失真信源編碼方法算術(shù)編碼（續(xù)1）第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼五、實(shí)用的無失真信源編碼方法五、實(shí)用的無失真信源編碼方法算術(shù)編碼（續(xù)2）第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼五、實(shí)用的無失真信源編碼方法五、實(shí)用的無失真信源編碼方法LZW編碼 輸入符號序列：ABCABDABCAAAABBBABCABCA 前綴 尾字符序號0X0000X0410X0FF0X1000X1010X1020X1030X1040X1050X1060X1070X1080X1090X10A0X10B0XFFFQ(FFF)Q(FFF)AQ(FFF)A(041)BB CC AAB DD AAB CCA AA AAA BB BBB AABC A第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼第五章：無失真信源編碼五、實(shí)用的無失真信源編碼方法五、實(shí)用的無失真信源編碼方法LZW編碼（續(xù)1）