August23信息論導論通信與信息工程學院楊海芬yanghf@July23信息論導論通信與信息工程學院楊海芬1單符號離散信源聯合熵多符號離散信源聯合熵；條件熵離散平穩信源、聯合熵離散平穩無記憶信源、聯合熵馬爾科夫信源及其極限熵冗余度與結構信息單符號離散信源聯合熵2四、馬爾科夫信源及其極限熵安德雷·馬爾可夫(AndreiMarkov1856－1922），俄國數學家。1874年馬爾可夫入圣彼得堡大學，師從切比雪夫，1886年當選為圣彼得堡科學院院士。開創了隨機過程這個新的領域，以他的名字命名的馬爾可夫鏈在現代工程、自然科學和社會科學各個領域都有很廣泛的應用。馬爾可夫性：一個過程的“將來”僅依賴“現在”而不依賴“過去”四、馬爾科夫信源及其極限熵安德雷·馬爾可夫(AndreiM3馬爾可夫鏈的應用排隊理論和統計學中的建模，還可作為信號模型用于熵編碼技術，如算術編碼著名的LZMA數據壓縮算法就使用了馬爾可夫鏈與類似于算術編碼的區間編碼。生物學應用，人口過程，可以幫助模擬生物人口過程的建模。隱蔽馬爾可夫模型還被用于生物信息學，用以編碼區域或基因預測。馬爾可夫鏈最近的應用是在地理統計學（geostatistics）中,被稱為是“馬爾可夫鏈地理統計學”。仍在發展過程中。“基于馬爾可夫鏈的我國城鄉居民收入演進分析”

馬爾可夫鏈的應用“基于馬爾可夫鏈的我國城鄉居民收入演進分析”4四、馬爾科夫信源及其極限熵1、馬爾科夫信源定義N維離散平穩信源符號序列中第N個符號只與前m(≤N-1)個符號相關，該信源為m階馬爾科夫信源。馬爾科夫信源是離散平穩有限記憶信源，其記憶長度為m。*m階馬爾科夫信源符號序列的長度N=m+1。四、馬爾科夫信源及其極限熵1、馬爾科夫信源定義N維離散平穩信5表示表示6狀態轉移圖馬爾科夫鏈表示馬爾科夫信源可以用狀態轉移圖表示嗎？*狀態轉移圖馬爾科夫鏈表示馬爾科夫信源可以用狀態轉移圖表示嗎？7第2章信源熵--馬爾科夫信源及極限熵ppt課件8用狀態表示的m階馬爾科夫信源等效于用狀態轉移圖描述的馬爾科夫鏈。例1狀態轉移圖用狀態表示的m階馬爾科夫信源等效于用狀態轉移圖描述的馬爾科夫9s1s2s3s40.20.80.50.5設狀態s1=00、s2=01、s3=10、s4=11s1s2s3s0.5設狀態s1=00、s10s1s2s3s40.20.80.50.50.50.50.20.8s1s2s3s0.20112、馬爾科夫鏈的遍歷定理馬爾科夫鏈的遍歷從任何一個狀態出發，可以通過有限步到達任何其他狀態，該馬爾科夫鏈是遍歷的。非遍歷的馬爾科夫鏈存在吸收態。非遍歷馬爾科夫鏈的例子s1s2s3s410.50.50.50.512、馬爾科夫鏈的遍歷定理馬爾科夫鏈的遍歷從任何一個狀態出發，12馬爾科夫鏈的遍歷定理3、馬爾科夫信源的極限熵馬爾科夫鏈的遍歷定理3、馬爾科夫信源的極限熵13極限熵定理N→∞時，N維離散平穩信源平均符號熵的極限存在且等于N階條件熵的極限值，稱為N維離散平穩信源的極限熵，用H∞表示。即使N→∞，m階馬爾科夫信源符號序列的有效長度只有m+1。極限熵定理N→∞時，N維離散平穩信源平均符號熵的極限存在且14第2章信源熵--馬爾科夫信源及極限熵ppt課件15強調m階馬爾科夫信源的長度特征，一般其極限熵H∞記為Hm+1例2圖示二元二階馬爾科夫信源的極限熵求極限熵求m階條件熵強調m階馬爾科夫信源的長度特征，一般其極限熵H∞記為Hm+116s1s2s3s40.20.80.50.50.50.50.20.8遍歷定理s1s2s3s0.2017第2章信源熵--馬爾科夫信源及極限熵ppt課件18完備性完備性19第2章信源熵--馬爾科夫信源及極限熵ppt課件20五、冗余度與結構信息1、冗余度冗余壓縮信息論的創始人Shannon提出把數據看作是信息和冗余度（redundancy）的組合。如在一份計算機文件中，某些符號會重復出現、某些符號比其他符號出現得更頻繁、某些字符總是在各數據塊中可預見的位置上出現等，這些冗余部分便可在數據編碼中除去或減少。相鄰的數據之間存在著相關性。如圖片中常常有色彩均勻的背影，電視信號的相鄰兩幀之間可能只有少量的變化影物是不同的，聲音信號有時具有一定的規律性和周期性等等。人們由于耳、目對信號的時間變化和幅度變化的感受能力都有一定的極限信源編碼五、冗余度與結構信息1、冗余度冗余壓縮信息論的創始人Shan21可利用一些編碼的方法刪去它們，從而達到減少冗余壓縮數據的目的。圖像壓縮編碼(1)無損壓縮編碼(2)有損壓縮編碼(3)混合編碼，如H261，JPEG，MPEG等技術標準簡單地說，如果沒有數據壓縮技術，我們就沒法用WinRAR為Email中的附件瘦身；如果沒有數據壓縮技術，市場上的數碼錄音筆就只能記錄不到20分鐘的語音；如果沒有數據壓縮技術，從Internet上下載一部電影也許要花半年的時間衡量一個壓縮編碼方法優劣的重要指標(1)壓縮比要高；(2)算法簡單，硬件實現容易；(3)解壓縮的圖像質量要好。可利用一些編碼的方法刪去它們，從而達到減少冗余壓縮數據的目的22信道前向糾錯編碼（FEC）技術通過在傳輸碼列中加入冗余糾錯碼，在一定條件下，通過解碼可以自動糾正傳輸誤碼，降低接收信號的誤碼率（BER）。衡量FEC糾錯能力的指標稱為“FEC編碼增益”，該增益越強表示糾錯性能越強。漢明碼、奇偶校驗碼、RS碼、Turbo碼、LDPC等糾錯性能、碼率、實現復雜度冗余糾錯信道編碼信道前向糾錯編碼（FEC）技術通過在傳輸碼列中加入冗余糾錯碼23中華人民共和國中國*華人民*和國*國中華人民共和國中國*華人民*和國*國24實際信源抽象為N維離散平穩信源，H∞是其熵率，即從理論上看，只要傳送H∞就可以了。但是這必須掌握信源的全部統計特性，這顯然是不現實的。實際中，只能掌握有限記憶長度m，其熵率用Hm+1近似，即需要傳送Hm+1與理論值相比，多傳送了Hm+1-H∞由于Hm+1>H∞，表現在信息傳輸上存在冗余。抽象描述實際信源抽象為N維離散平穩信源，H∞是其熵率，即從理論上看，25定義信源的m階極限熵Hm+1與N-1階極限熵H∞的相對差為該信源的冗余度，也叫剩余度。表示信源的冗余度表示信源可以被壓縮的程度*定義信源的m階極限熵Hm+1與N-1階極限熵H∞的相對差為該26或者定義正是由于信源存在冗余度，所以存在著進一步壓縮的可能性。冗余度越大，壓縮潛力越大。它是信源編碼、數據壓縮的前提與基礎。H0：相同符號數的最大值或者定義正是由于信源存在冗余度，所以存在著進一步壓縮的可能性27例1英文信源的熵率例1英文信源的熵率28英文信源用m階馬爾可夫信源近似，最大熵及各階極限熵（1）近似為無記憶信源(零階馬爾可夫信源)且字母等概率分布最大熵（2）近似為無記憶信源，字母的概率分布英文信源用m階馬爾可夫信源近似，最大熵及各階極限熵（1）近似29英文字母不等概率分布圖空格英文字母不等概率分布圖空格30英文字母前后存在一定的依賴關系，如t后出現h、r的可能性較大。零階極限熵(無條件熵)一階極限熵（3）近似為一階馬爾可夫信源，考慮字母的一階條件概率分布英文字母前后存在一定的依賴關系，如t后出現h、r的可能性較大31（5）近似為全記憶信源(香農以m=100估計)，N-1階極限熵（4）近似為二階馬爾可夫信源，考慮字母的二階條件概率分布，二階極限熵…實際信源為全記憶信源，熵率為H∞，考慮到可實現性，一般取有限記憶長度m，熵率用Hm+1近似，Hm+1>H∞，在信息傳輸上存在冗余。（5）近似為全記憶信源(香農以m=100估計)，N-1階極限32英文信源近似為無記憶信源且等概時，冗余度英文信源的冗余度的計算信源的冗余度表示信源可以被壓縮的程度英文信源近似為無記憶信源且等概時，冗余度英文信源的冗余度的計33英文信源近似為無記憶信源但概率分布已知時，冗余度英文信源近似為一階馬爾可夫信源，冗余度英文信源近似為無記憶信源但概率分布已知時，冗余度英文信源近似34英文信源近似為二階馬爾可夫信源，冗余度…英文信源近似為二階馬爾可夫信源，冗余度…35第2章信源熵--馬爾科夫信源及極限熵ppt課件362、結構信息定義信源的m階極限熵Hm+1與N-1階極限熵H∞之差為該信源的結構信息。表示2、結構信息定義信源的m階極限熵Hm