[信息與通信]信源編碼ppt課件

1、 信源編碼信源編碼第二部分第三章第二部分第三章Efficiency vs. Reliability Efficiency Average code length as small as possible Reliability The ability to recover from errors in the transmissionCodingDecodingInformation sourceSourcecodingChannelcodingInformationchannelChanneldecodingSourcedecodingDestination 提要提要 1 根本概念根本概念

2、2 根本定理：變長編碼定理根本定理：變長編碼定理 3 即時碼非續(xù)長碼即時碼非續(xù)長碼 4 仙農(nóng)仙農(nóng)-費諾費諾Shannon-Fano法法 5 霍夫曼霍夫曼Huffman法法 * 6 數(shù)據(jù)壓縮的分類與國際標準簡介數(shù)據(jù)壓縮的分類與國際標準簡介 1 根本概念根本概念1編碼：編碼：利用編碼符號集對消息符號集進展的某種變換。 例例 漢字電報 漢字符號標準電碼五單元電碼， 即漢字 0，1，2，9 0，15位0、1表示一個數(shù)字 0 01101，1 01011，2 11001，4 11010， 8 01110，9 10011 中0022 國0948 01101 01101 1101 1101 01101 100

3、11 11010 01110 2 信源編碼：信源編碼：又稱數(shù)據(jù)語音、圖象、文本壓縮數(shù)據(jù)語音、圖象、文本壓縮，目的在于減少數(shù)字信息中的冗余度，進步通信或存儲的有效性 連續(xù)信源編碼： AA/D轉換不討論； B去冗余度。離散信源的統(tǒng)計特性： 離散消息-在有限符號集中選取假設干個符號組成的隨機序列； 形成消息時，各符號出現(xiàn)的概率不同； 組成消息的符號之間有一定的相關性。信源的最正確編碼：信源的最正確編碼：在保證信息量不變或在允許一定的失真度條件下，使各碼字的平均長度最短，即每個碼元所含的平均信息量最大。 2 無干擾離散信道的信源編碼定理無干擾離散信道的信源編碼定理 仙農(nóng)第一定理，仙農(nóng)無失真信源編碼定理

4、傳輸效率：傳輸效率：實際傳信率R與信道容量之比，即信道容量 的利用率。 =R/C 對于無干擾無噪聲信道， =實際信源熵實際信源熵/最大信源熵最大信源熵= H0X/max HX1 問：問： 能到達多大？2 仙農(nóng)第一定理仙農(nóng)第一定理：設離散無記憶：設離散無記憶信源熵為信源熵為HX，經(jīng)容量，經(jīng)容量為為Cbit/符號的無干擾信道傳輸，那么總可以找到某種編符號的無干擾信道傳輸，那么總可以找到某種編碼方法對信源的輸出進展編碼，使其在信道中的傳信率任意碼方法對信源的輸出進展編碼，使其在信道中的傳信率任意地接近于信道容量地接近于信道容量C正定理。正定理。證明略逆定理：不存在任何編碼方法，使傳信率逆定理：不存在

5、任何編碼方法，使傳信率R大于等于大于等于C。 3 信源編碼器的作用：信源編碼器的作用：改造信源，使HX最大化，從而使 1， 1的過程就是使信源最正確化的過程。 信源編碼又稱為使信源與信道匹配信源與信道匹配的最正確編碼。類比： 信源信源又分為有記憶信源有記憶信源與無記憶信源無記憶信源：有記憶信源有記憶信源-信源發(fā)出的符號前后有關連，一個符號的出現(xiàn)會影響另一個符號的出現(xiàn)。無記憶信源無記憶信源-符號之間是獨立的，一個符號出現(xiàn)的概率與前面出現(xiàn)的符號有關。 HX最大化包含兩個步驟：1符號獨立化，除符號之間的相關性；2各符號概率均勻化。 本章只考慮無記憶離散信源的編碼，不考慮步驟1。 3 編碼效率及變長編

6、碼定理編碼效率及變長編碼定理最小平均碼長與編碼效率最小平均碼長與編碼效率1平均碼長平均碼長: iimiinxpn)(1可以證明，碼字的平均長度DXHn2log)(1最小平均碼長最小平均碼長DXHn2minlog)(假設D=2，那么)(minXHn2編碼效率：編碼效率：DnXHnn2minlog)(3編碼剩余度：編碼剩余度： 1yR例例 一個離散信源輸出為4個長度均為1的符號，每個符號出現(xiàn)的概率分別為1/2，1/4，1/8。1/8，求平均碼長與編碼效率。81,81,41,21,432,1xxxxX解解:)(bit/ 75. 1log)(41符號iiippXH1)(1iimiinxpn875. 0

7、4log75. 1log)(22minDnXHnn125.01yR 信源編碼的必要性信源編碼的必要性: 實際信源往往含有大量冗余, 比方,英文字母表含空格符共27個符號, 假設等概出現(xiàn),那么每個符號的信息量為4.76bit, 而在無記憶情況下實際信源熵只有4.076bit/符號, 假設考慮兩個字母之間的相關性，那么實際熵只有3.32bit/符號;假設考慮100個字母之間的相關性,那么實際信源熵只有1bit/符號,此時編碼剩余度為79%!如何編碼才能使平均碼長最短？如何編碼才能使平均碼長最短？ 一般離散信源各符號出現(xiàn)的概率并不相等, 由可知, 概率大的符號編短碼概率大的符號編短碼,概率小的編長碼

8、概率小的編長碼, 就可以使平均碼長最短. Morse電報就采用這種方法.iimiinxpn)(1 - - 0.00063 Z- - 0.00099 Q- - - 0.00108 J .- 0.0668 A- 0.0856 T 0.1073 EMorse 碼字母ip編碼方法編碼方法例例 一個離散信源由4個符號S1, S2, S3, S4組成,其出現(xiàn)的概率分別為0.6, 0.2, 0.2, 0.1和0.1, 試用不同的方法編碼,并加以比較.碼碼1：假設發(fā)S4S1=110，接收時既可譯成11，0=S4S1， 也可譯成110=S3， 不唯一可譯；碼碼2：等長碼，唯一可譯，效率較低；碼碼3：每碼字均以0

9、結尾，稱為逗點碼，唯一可譯，且可隨收隨譯；碼碼4：以0開頭，須等待下一個0到來時才能開場譯；碼碼5：立即可譯。編碼的一般原那么編碼的一般原那么:須唯一可譯;2 概率大的用短碼, 概率小的用長碼;3 碼字之間不用空格符就能區(qū)分;4 須立即可譯.變長編碼定理變長編碼定理:假設離散信源的熵為假設離散信源的熵為HX,每個信源符號用每個信源符號用D進制符號進制符號進展編碼進展編碼,那么存在某種編碼方法那么存在某種編碼方法, 其碼字平均長度滿足其碼字平均長度滿足DXHDXHn22log)(log)(1對于二進制編碼二進制編碼D=2, 那么有)()(1XHXHn2 對于對于L次擴展信源次擴展信源, 那么有以

10、下關系那么有以下關系DXHLDXHLDXHnn2L22log)(lim , ,log)(1log)(時當可見注注:1 該定理只是一個極限定理，必須在L為無窮時才能到達理論情況； 2某些信源如語音、圖象等在實際應用中往往允許一定的失真不研究。21ii21212 1,)/( 1pn 1S 0,S:) 1 (bit/ 811. 034log434log41log)( :.1 0, 1/4,3/4 ,SSS iiiinppSH信源符號二進符號令單符號編碼符號解進行編碼試用和其概率分別為組成由兩個符號已知信源例)( 98.5% :)3()3(%1 .96842.0811.0lognH(S)842.021

11、n 1627)( 111 110 10 0 16141 163 1634143 SS :2)(L(2)18.9%-1 R%,1 .81lognH(S) 222 224123 2121112y)()43( 2過程略三次擴展編碼的一個符號展信源的兩個符號構成二次擴由二次擴展LDnpnnSSaSSaSSaSSaDii 4 即時碼非續(xù)長碼、非延長碼即時碼非續(xù)長碼、非延長碼 1 唯一可譯碼單義碼與即時碼唯一可譯碼單義碼與即時碼 編碼編碼-等長碼，變長碼 等長碼：效率低，簡單、方便 變長碼：效率高，但碼字區(qū)分困難 要求：要求： 唯一可譯； 即時性-可邊收邊譯，不必等待。1唯一可譯碼單義碼：唯一可譯碼單義碼

12、：只能譯出一種結果例例 C1=1，01，00 接收序列10001101唯一譯成1，00，01，10，1 唯一可譯碼，單義碼C2=0，10，01接收序列01001既可譯成01，0，01 也可譯成0，10，01 不唯一可譯，非單義碼2即時碼非續(xù)長碼：即時碼非續(xù)長碼：收到一個碼字就能譯出，不必等待與觀察后面接收的是什么符號。例例 1C1=S1，S2，S3，S4=0，01，011，111 接收序列：0111101101 假設邊收邊譯：0，111，1 譯不下去了 假設收完后再譯從后往前：01，111，011，01 唯一可譯，但需要等待 2C2=S1，S2，S3， S4，S5=00，01，10，110，1

13、11 接收序列：110101110100 110，10，111，01，00 唯一可譯碼3即時碼與唯一可譯碼單義碼之間的關系：即時碼與唯一可譯碼單義碼之間的關系： 即時碼一定是唯一可譯碼單義碼，但唯一可譯碼單義碼不一定是即時碼。即時碼存在的充要條件即時碼存在的充要條件1即時碼存在的充要條件從構造上：即時碼存在的充要條件從構造上：即時碼中任何任何一個碼字都不能是另一個碼字的開頭前綴一個碼字都不能是另一個碼字的開頭前綴，或者說任任何一個碼字都不能是另一個碼字的延續(xù)延長何一個碼字都不能是另一個碼字的延續(xù)延長，因此這種碼又稱為非續(xù)長碼非續(xù)長碼。2即時碼存在的充要條件從碼長上：即時碼存在的充要條件從碼長上

14、：存在N個碼長為nii=1,2,n的即時碼的充要條件是2 111NinDiD是編碼符號集中符號的數(shù)目，即編碼采用的進制例例 ：信源：信源X=x1,x2,x7，采用，采用2進編碼，編出的碼長分進編碼，編出的碼長分 別為，別為， ni=2,2,3,3,3,4,5, 試判斷是否存在這樣的即時碼。試判斷是否存在這樣的即時碼。解：解：存在即時碼196875.02121232221543271ini例例 設設wi表示碼長為表示碼長為i的碼字數(shù)目的碼字數(shù)目, 且且w1=0, w2=3, w3=0, w4=5, 求：能編成即時碼的求：能編成即時碼的D的最小值。的最小值。解：解：.3D ,05.2 192872

15、.4 ,102093 ,0135 ,15322242時可編成即時碼故取即即得令DDxxxDxDD即時碼的編譯碼即時碼的編譯碼 編碼器的描繪編碼器的描繪1即時碼的編碼碼樹法即時碼的編碼碼樹法例例 設A=0，1，將X=x1,x2,x3,x4編成碼長分別為1，2，3，3的即時碼。解：解：D=2存在這樣的即時碼 122212132原那么：任何一個碼字不能作為另一個碼字的開頭用碼樹圖編碼的步驟：用碼樹圖編碼的步驟： 從頂點樹根出發(fā)，畫出兩條D=2分枝，一條代表“0，另一條代表“1。選取其中的一個終點作為碼字，如w1=0; 從未被選用的終點再畫出兩枝，選其中的一個終點作為碼字w2; 繼續(xù)下去，直至W中所有

16、的碼字都有一個終點來表示為止； 從樹根出發(fā)到各個終點，依次讀出各枝代表的符號0，1，便得到相應的碼字。w1=0W2=10W3=110W4=1112即時碼的譯碼即時碼的譯碼例例 在上例中，假設收到一串碼字100110010，試用碼樹進展譯碼。解：解：譯碼方法：譯碼方法：順著碼樹走，遇到一個終點便得到一個碼字，然后再回到樹根，從頭開場走，直至全部碼序列都譯完為止。譯碼結果：W2 W1 W3 W1 W2，即10，0，110，0，10緊致即時碼：緊致即時碼：平均碼長剛好等于信源熵的即時碼，其編碼效率為100%。 1963年Abramson 發(fā)現(xiàn)，假設符號出現(xiàn)的概率為，取碼字長度為ni, 便能編出緊致即

17、時碼。例例 設信源源不斷個符號出現(xiàn)的概率分別為1/2，1/4，1/8，1/8，試編成緊致即時碼，并將其平均碼長與信源熵進展比較。解：解：由)(21inip )(21inip 知，4個碼字的長度分別選為1，2，3，3，編碼后得到的碼字分別為0，10，110，111。. )(n 431n431log)(4141因而是即時碼XHpnppXHiiiiii 5 仙農(nóng)仙農(nóng)-費諾費諾Shannon-Fano編碼法編碼法 最正確編碼最正確編碼-按概率匹配的原那么，概率大的編短碼，概率小的編長碼，使在給定信息量的條件下，平均碼長最短。 兩種最正確編碼法：兩種最正確編碼法：仙農(nóng)費諾法，霍夫曼Huffman法.仙農(nóng)

18、仙農(nóng)-費諾編碼法費諾編碼法符號解編碼制試對下列信源進行二進按照概率匹配的原則例/ 75. 2)(log)()( 1 , 0 0625. 0 ,0625. 0 ,125. 0 ,25. 0 ,0625. 0 ,0625. 0 ,25. 0 ,125. 0)( , , , , , , ,X : , 8187654321bitxpxpXHDxpxxxxxxxxiii%100log75.2)( 81DnH(X)nxpniii仙農(nóng)仙農(nóng)-費諾法的編碼步驟：費諾法的編碼步驟： 1將信源符號按概率由大到小排列； 2將全部信源符號分成概率和大致相等的兩個D=2組，分別賦予“0，“1； 3再按2的方法對各組進展處

19、理，直至每個符號被分割出來為止； 4 按編碼過程順序讀出各符號相應的碼元，便得到對應的碼字。例例 用仙農(nóng)-費諾法將下述消息編成三進制碼，D=0，1，261,81,81,83,121,81)( , , , , , 654321MpmmmmmmM%94log388.2 ,625.1)( 81DnH(X)H(X)nxpniii 6 霍夫曼霍夫曼Huffman編碼法編碼法問題：問題：仙農(nóng)-費諾法的優(yōu)缺點是什么？如何改進？Huffman編碼法編碼法例例 對以下信源進展二進制編碼：16. 0 ,18. 0 ,08. 0 ,04. 0 ,32. 0 ,22. 0)( , , , , , 654321MpmmmmmmM解：解：符號/ 352. 2)(log)()(61bitmpmpMHiii 先將符號按概率由大到小排列，再從概率最小的符號開場編碼%984.2352.2