第2章信源熵--馬爾科夫信源及極限熵

1、2021年8月 信息論導論信息論導論 通信與信息工程學院通信與信息工程學院 楊海芬楊海芬 信源熵 o 單符號離散信源聯(lián)合熵單符號離散信源聯(lián)合熵 o 多符號離散信源聯(lián)合熵；條件熵多符號離散信源聯(lián)合熵；條件熵 o 離散平穩(wěn)信源、聯(lián)合熵離散平穩(wěn)信源、聯(lián)合熵 o 離散平穩(wěn)無記憶信源、聯(lián)合熵離散平穩(wěn)無記憶信源、聯(lián)合熵 o 馬爾科夫信源及其極限熵馬爾科夫信源及其極限熵 o 冗余度與結(jié)構(gòu)信息冗余度與結(jié)構(gòu)信息 信源熵 四、馬爾科夫信源及其極限熵 o 安德雷安德雷馬爾可夫馬爾可夫(Andrei Markov 1856(Andrei Markov 185619221922），俄國），俄國 數(shù)學家。數(shù)學家。 n 1

2、8741874年馬爾可夫入年馬爾可夫入圣彼得堡大學圣彼得堡大學，師從切比雪夫，師從切比雪夫， 18861886年當選為圣彼得堡科學院院士。年當選為圣彼得堡科學院院士。 n 開創(chuàng)了隨機過程這個新的領(lǐng)域，以他的名字命名的開創(chuàng)了隨機過程這個新的領(lǐng)域，以他的名字命名的馬馬 爾可夫鏈爾可夫鏈在現(xiàn)代工程、自然科學和社會科學各個領(lǐng)域在現(xiàn)代工程、自然科學和社會科學各個領(lǐng)域 都有很廣泛的應(yīng)用。都有很廣泛的應(yīng)用。 o 馬爾可夫性：一個過程的馬爾可夫性：一個過程的“將來將來”僅依賴僅依賴“現(xiàn)在現(xiàn)在”而不依而不依 賴賴“過去過去” ” 信源熵 o 馬爾可夫鏈的應(yīng)用馬爾可夫鏈的應(yīng)用 n 排隊理論和統(tǒng)計學中的建模，還可作

3、為信號模型用排隊理論和統(tǒng)計學中的建模，還可作為信號模型用 于于熵編碼熵編碼技術(shù)，如技術(shù)，如算術(shù)編碼算術(shù)編碼 o 著名的著名的LZMALZMA數(shù)據(jù)壓縮算法就使用了馬爾可夫鏈與數(shù)據(jù)壓縮算法就使用了馬爾可夫鏈與 類似于算術(shù)編碼的區(qū)間編碼。類似于算術(shù)編碼的區(qū)間編碼。 n 生物學應(yīng)用，生物學應(yīng)用， o 人口過程人口過程，可以幫助模擬生物人口過程的建模。，可以幫助模擬生物人口過程的建模。 o 隱蔽馬爾可夫模型還被用于隱蔽馬爾可夫模型還被用于生物信息學生物信息學，用以編，用以編 碼區(qū)域或基因預測。碼區(qū)域或基因預測。 n 馬爾可夫鏈最近的應(yīng)用是在地理統(tǒng)計學馬爾可夫鏈最近的應(yīng)用是在地理統(tǒng)計學 （geostati

4、sticsgeostatistics）中）中, ,被稱為是被稱為是“馬爾可夫鏈地理馬爾可夫鏈地理 統(tǒng)計學統(tǒng)計學”。仍在發(fā)展過程中。仍在發(fā)展過程中。 “基于馬爾可夫鏈的我國城鄉(xiāng)居民收入演進分析基于馬爾可夫鏈的我國城鄉(xiāng)居民收入演進分析” 信源熵 四、馬爾科夫信源及其極限熵四、馬爾科夫信源及其極限熵 1、馬爾科夫信源、馬爾科夫信源 定義定義 N維離散平穩(wěn)信源符號序列中第維離散平穩(wěn)信源符號序列中第N個符號只與前個符號只與前m (N-1)個符號相關(guān)，該信源為個符號相關(guān)，該信源為m階馬爾科夫信源。階馬爾科夫信源。 馬爾科夫信源是離散平穩(wěn)馬爾科夫信源是離散平穩(wěn)有限記憶有限記憶信源，其記憶信源，其記憶 長度為

5、長度為m 。* m階馬爾科夫信源符號序列的長度階馬爾科夫信源符號序列的長度N=m+1。 信源熵 表示表示 )a (P)a (P)a (P aaa )XXX/X(P XXX/X 1m 1m n 21 n 21 m211m m211m n , 2 , 1i ,i , in , 2 , 1ixxx/xa 1m21 1m iiiii m211m 其中， 1)xxx/x(P)a (P0 m211m iiiii 1)xxx/x(P n 1i iiii 1m m211m 且 信源熵 狀態(tài)轉(zhuǎn)移圖狀態(tài)轉(zhuǎn)移圖 馬爾科夫鏈馬爾科夫鏈 表示表示 馬爾科夫信源可以用狀態(tài)轉(zhuǎn)移圖表示嗎？馬爾科夫信源可以用狀態(tài)轉(zhuǎn)移圖表示嗎？

6、* 信源熵 S引入狀態(tài) n, 2 , 1i ,i ,in, 2 , 1ixxxs s ,s ,sS m21 m iiii n 21 m21 m 取值于集合過態(tài) n, 2 , 1j ,j , jn, 2 , 1j xxxxxxs s ,s ,sS m21 m iiijjjj n 21 1m32m21 m 取值于集合現(xiàn)態(tài) 信源熵 )s /s (P)xxx/xxx(P )xxx/xxx(P)xxx/x(P)a (P ijiiijjj iiiiiiiiiii m21m21 m211m32m211m 用狀態(tài)表示的用狀態(tài)表示的m階馬爾科夫信源等效于用狀態(tài)轉(zhuǎn)移階馬爾科夫信源等效于用狀態(tài)轉(zhuǎn)移 圖描述的馬爾科夫

7、鏈。圖描述的馬爾科夫鏈。 例例1 8 . 02 . 05 . 05 . 0 11/ 111/ 010/ 110/ 0 5 . 05 . 02 . 08 . 0 01/ 101/ 000/ 100/ 0 )XX/X(P XX/X 213 213 狀態(tài)轉(zhuǎn)移圖狀態(tài)轉(zhuǎn)移圖 信源熵 2 . 0)s /s (P )00/01(P)00/1 (P 12 5 . 0)s /s (P )01/10(P)01/0(P 23 5 . 0)s /s (P )01/11(P)01/1 (P 24 8 . 0)s /s (P )00/00(P)00/0(P 11 s1 s2s3 s4 0.2 0.8 0.5 0.5 設(shè)狀

8、態(tài)設(shè)狀態(tài)s1=00、s2=01、s3=10、s4=11 信源熵 s1 s2s3 s4 0.2 0.8 0.5 0.5 5 . 0)s /s (P )10/01(P)10/ 1 (P 32 2 . 0)s /s (P )11/10(P)11/0(P 43 8 . 0)s /s (P )11/11(P)11/1 (P 44 5 . 0)s /s (P )10/00(P)10/0(P 31 0.5 0.5 0.2 0.8 信源熵 2、馬爾科夫鏈的遍歷定理、馬爾科夫鏈的遍歷定理 馬爾科夫鏈的遍歷馬爾科夫鏈的遍歷 從任何一個狀態(tài)出發(fā)，可以通過有限步到達任何從任何一個狀態(tài)出發(fā)，可以通過有限步到達任何 其他

9、狀態(tài)，該馬爾科夫鏈是遍歷的。其他狀態(tài)，該馬爾科夫鏈是遍歷的。 非遍歷的馬爾科夫鏈存在吸收態(tài)。非遍歷的馬爾科夫鏈存在吸收態(tài)。 非遍歷馬爾科夫鏈的例子非遍歷馬爾科夫鏈的例子 s1 s2s3 s4 1 0.5 0.5 0.5 0.5 1 信源熵 馬爾科夫鏈的遍歷定理馬爾科夫鏈的遍歷定理 m ij n 1i ij n, 2 , 1j)s /s (P)s (P)s (P m 1)s (P1)s (P0 m n 1j jj ，且 3、馬爾科夫信源的極限熵、馬爾科夫信源的極限熵 信源熵 極限熵定理極限熵定理 N時，時， N維離散平穩(wěn)信源平均符號熵的極限存維離散平穩(wěn)信源平均符號熵的極限存 在且等于在且等于N階

10、條件熵的極限值，稱為階條件熵的極限值，稱為N維離散平穩(wěn)維離散平穩(wěn) 信源的極限熵，用信源的極限熵，用H表示。表示。 )XXX/X(Hlim)XXX(HlimH 1N21N N N21N N 即使即使N，m階馬爾科夫信源符號序列的有效長階馬爾科夫信源符號序列的有效長 度只有度只有m+1。 )XXX/X(H)XXX/X(HlimH m211m1N21N N 信源熵 )XXX/X(H)XXX/X(HlimH m211m1N21N N n 1i n 1i n 1i iiiiiii 121m m211m1m21 )xxx/x(Plog)xxx(P )xxx/x(Plog)xxx/x(P)xxx(P m21

11、1m 121m m211mm21 iiii n 1i n 1i n 1i iiiiiii )s /s (P)xxx/xxx(P )xxx/xxx(P)xxx/x(P )s (P)xxx(P ijiiijjj iiiiiiiiii iiii m21m21 m211m32m211m m21 其中 信源熵 強調(diào)強調(diào)m階馬爾科夫信源的長度特征，一般其極限熵階馬爾科夫信源的長度特征，一般其極限熵 H記為記為Hm+1 mm n 1i n 1j ijiji1m )s /s (Plog)s /s (P)s (PHH 例例2 圖示二元二階馬爾科夫信源的極限熵圖示二元二階馬爾科夫信源的極限熵 求極限熵求極限熵 求

12、求m階條件熵階條件熵 信源熵 s1 s2s3 s4 0.2 0.8 0.5 0.5 0.5 0.5 0.2 0.8 遍歷定理遍歷定理 )s (P5 . 0)s (P8 . 0 )s /s (P)s (P)s /s (P)s (P )s /s (P)s (P)s /s (P)s (P)s (P 31 414313 2121111 )s (P5 . 0)s (P2 . 0 )s /s (P)s (P)s /s (P)s (P )s /s (P)s (P)s /s (P)s (P)s (P 31 424323 2221212 信源熵 )s (P2 . 0)s (P5 . 0 )s /s (P)s (

13、P)s /s (P)s (P )s /s (P)s (P)s /s (P)s (P)s (P 42 434333 2321313 )s (P8 . 0)s (P5 . 0 )s /s (P)s (P)s /s (P)s (P )s /s (P)s (P)s /s (P)s (P)s (P 42 444343 2421414 信源熵 0)s (P2 . 0)s (P5 . 0 0)s (P2 . 0)s (P)s (P5 . 0 0)s (P5 . 0)s (P)s (P2 . 0 0)s (P5 . 0)s (P2 . 0 42 432 321 31 完備性完備性 1)s (P)s (P)s

14、(P)s (P 4321 14 2 )s (P)s (P 14 5 )s (P)s (P 32 41 信源熵 4 1i 4 1j ijiji312 )s /s (Plog)s /s (P)s (PHHH )8 . 0log8 . 02 . 0log2 . 0( 14 5 ) 5 . 0log5 . 05 . 0log5 . 0( 14 2 ) 5 . 0log5 . 05 . 0log5 . 0( 14 2 ) 2 . 0log2 . 08 . 0log8 . 0( 14 5 )symbol/bit( 8 . 0 信源熵 五、冗余度與結(jié)構(gòu)信息 1、冗余度 冗余 壓縮 o信息論的創(chuàng)始人Shann

15、on提出把數(shù)據(jù)看作是信息和冗余度 （redundancy）的組合。 n如在一份計算機文件中，某些符號會重復出現(xiàn)、某些符號比其他 符號出現(xiàn)得更頻繁、某些字符總是在各數(shù)據(jù)塊中可預見的位置上 出現(xiàn)等，這些冗余部分便可在數(shù)據(jù)編碼中除去或減少。 n相鄰的數(shù)據(jù)之間存在著相關(guān)性。如圖片中常常有色彩均勻的背影， 電視信號的相鄰兩幀之間可能只有少量的變化影物是不同的，聲 音信號有時具有一定的規(guī)律性和周期性等等。 n人們由于耳、目對信號的時間變化和幅度變化的感受能力都有一 定的極限 信源編碼 信源熵 o 可利用一些編碼的方法刪去它們，從而達到減少冗余壓 縮數(shù)據(jù)的目的。 o 圖像壓縮編碼 (1)無損壓縮編碼 (2)

16、有損壓縮編碼 (3) 混合編碼，如 H261，JPEG，MPEG等技術(shù)標準 o 簡單地說，如果沒有數(shù)據(jù)壓縮技術(shù)，我們就沒法用 WinRAR 為 Email 中的附件瘦身；如果沒有數(shù)據(jù)壓縮 技術(shù)，市場上的數(shù)碼錄音筆就只能記錄不到 20 分鐘的 語音；如果沒有數(shù)據(jù)壓縮技術(shù)，從 Internet 上下載一 部電影也許要花半年的時間 o 衡量一個壓縮編碼方法優(yōu)劣的重要指標 (1)壓縮比要高； (2) 算法簡單，硬件實現(xiàn)容易； (3)解壓縮的圖像質(zhì)量 要好。 信源熵 o 信道前向糾錯編碼信道前向糾錯編碼（FEC）技術(shù)通過在傳輸碼列中技術(shù)通過在傳輸碼列中 加入冗余糾錯碼，在一定條件下，通過解碼可以加入冗余

17、糾錯碼，在一定條件下，通過解碼可以 自動糾正傳輸誤碼，降低接收信號的誤碼率自動糾正傳輸誤碼，降低接收信號的誤碼率 （BER）。衡量。衡量FEC糾錯能力的指標稱為糾錯能力的指標稱為“FEC編編 碼增益碼增益”，該增益越強表示糾錯性能越強。，該增益越強表示糾錯性能越強。 o 漢明碼、漢明碼、奇偶校驗碼、奇偶校驗碼、RS碼、碼、Turbo碼、碼、LDPC等等 o 糾錯性能、碼率、實現(xiàn)復雜度糾錯性能、碼率、實現(xiàn)復雜度 冗余冗余 糾錯糾錯 信道編碼信道編碼 信源熵 中華人民共和國中華人民共和國中國中國 *華人民華人民*和國和國 *國國 信源熵 實際信源抽象為實際信源抽象為N維離散平穩(wěn)信源，維離散平穩(wěn)信源

18、，H是其熵率，是其熵率， 即從理論上看，只要傳送即從理論上看，只要傳送H就可以了。就可以了。 但是這必須掌握信源的全部統(tǒng)計特性，這顯然是但是這必須掌握信源的全部統(tǒng)計特性，這顯然是 不現(xiàn)實的。實際中，只能掌握有限記憶長度不現(xiàn)實的。實際中，只能掌握有限記憶長度m， 其熵率用其熵率用Hm+1近似，即需要傳送近似，即需要傳送Hm+1 與理論值相比，多傳送了與理論值相比，多傳送了Hm+1-H 由于由于Hm+1H，表現(xiàn)在信息傳輸上存在冗余。，表現(xiàn)在信息傳輸上存在冗余。 抽象描述抽象描述 信源熵 定義定義 信源的信源的m階極限熵階極限熵Hm+1與與N-1階極限熵階極限熵H的相對差的相對差 為該信源的冗余度，

19、也叫剩余度。為該信源的冗余度，也叫剩余度。 表示表示 1m 1m H HH 信源的冗余度表示信源可以被壓縮信源的冗余度表示信源可以被壓縮 的程度的程度 * 信源熵 o 或者定義或者定義 0 0 H HH o 正是由于信源存在冗余度，所以存在著進一步壓縮正是由于信源存在冗余度，所以存在著進一步壓縮 的可能性。冗余度越大，壓縮潛力越大。它是信源的可能性。冗余度越大，壓縮潛力越大。它是信源 編碼、數(shù)據(jù)壓縮的前提與基礎(chǔ)。編碼、數(shù)據(jù)壓縮的前提與基礎(chǔ)。 H0：相同符號數(shù)的最大值：相同符號數(shù)的最大值 信源熵 例例1 英文信源的熵率英文信源的熵率 信源熵 英文信源用英文信源用m階馬爾可夫信源近似，最大熵及各階

20、馬爾可夫信源近似，最大熵及各 階極限熵階極限熵 （1）近似為無記憶信源）近似為無記憶信源(零階馬爾可夫信源零階馬爾可夫信源)且字且字 母等概率分布母等概率分布 )symbolbit(76. 427logH0 最大熵最大熵 （2）近似為無記憶信源，字母的概率分布）近似為無記憶信源，字母的概率分布 信源熵 英文字母不等概率分布圖英文字母不等概率分布圖 空格空格 信源熵 )symbolbit(03. 4H1 )symbolbit(32. 3H2 英文字母前后存在一定的依賴關(guān)系，如英文字母前后存在一定的依賴關(guān)系，如t后出現(xiàn)后出現(xiàn)h、 r的可能性較大。的可能性較大。 零階極限熵零階極限熵(無條件熵無條件

21、熵) 一階極限熵一階極限熵 （3）近似為一階馬爾可夫信源，考慮字母的一階）近似為一階馬爾可夫信源，考慮字母的一階 條件概率分布條件概率分布 信源熵 )symbolbit(40. 1H （5）近似為全記憶信源）近似為全記憶信源(香農(nóng)香農(nóng)以以m=100估計估計)，N-1 階極限熵階極限熵 )symbolbit(10. 3H3 （4）近似為二階馬爾可夫信源，考慮字母的二階）近似為二階馬爾可夫信源，考慮字母的二階 條件概率分布，二階極限熵條件概率分布，二階極限熵 實際信源為全記憶信源，熵率為實際信源為全記憶信源，熵率為H，考慮到可實，考慮到可實 現(xiàn)性，一般取有限記憶長度現(xiàn)性，一般取有限記憶長度m，熵率用，熵率用Hm+1近似，近似， Hm+1H，在信息傳輸上存在，在信息傳輸上存在冗余冗余。 信源熵 英文信源近似為無記憶信源且等概時，冗余度英文信源近似為無記憶信源且等概時，冗余度 英文信源的冗余度的計算英文信源的冗余度的計算 71. 0 76. 4 40. 176. 4 H HH 0 0 信源的冗余度表