信息論與編碼信源及信源熵

1、信息論與編碼信源及信源熵第1頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵上一講復(fù)習(xí)互信息量：互信息量與信源熵的關(guān)系：第2頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵連續(xù)信源熵： 它與離散信源熵的差別（差熵） 最大熵：（1）限幅度時(shí)的最大熵 （2）限平均功率時(shí)的最大熵序列信源熵： （1）離散無記憶信源序列熵：第3頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵（2）離散有記憶信源序列熵： （i）平穩(wěn)有記憶序列信源：極限熵：第4頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論

2、與編碼-信源及信源熵二、馬爾可夫信源1.馬爾可夫信源設(shè)一般信源所處的狀態(tài) ，在每一狀態(tài)下可能輸出的符號(hào) 。定義：若信源輸出的符號(hào)序列和信源所處的狀態(tài)滿足以下兩個(gè)條件（1）某一時(shí)刻信源符號(hào)的輸出只與此時(shí)刻信源所處的狀態(tài)有關(guān)，而與以前的狀態(tài)及以前的輸出符號(hào)都無關(guān)，即第5頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵當(dāng)具有齊次性時(shí)，有（2）信源某 時(shí)刻所處的狀態(tài)由當(dāng)前的輸出符號(hào)和前一時(shí)刻 信源的狀態(tài)唯一決定，即則此信源稱為馬爾可夫信源。第6頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵上述定義和描述的是一般的馬爾可夫信源。但常見

3、的是m階馬爾可夫信源，它在任何時(shí)刻 ，符號(hào)發(fā)生的概率只與前面m個(gè)符號(hào)有關(guān)，我們可以把這前面m個(gè)符號(hào)序列看作信源在此 時(shí)刻所處的狀態(tài)。因?yàn)樾旁捶?hào)集共有q個(gè)符號(hào)，則信源可以有 個(gè)不同的狀態(tài)，他們對(duì)應(yīng)于 個(gè)長度為m的不同的符號(hào)序列。第7頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵因此，m階馬爾可夫離散信源的數(shù)學(xué)模型可由一組信源符號(hào)集和一組條件概率確定：并滿足第8頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵M階馬爾可夫信源在任何時(shí)刻 ，符號(hào)發(fā)生的概率只與前m個(gè)符號(hào)有關(guān)，所以可設(shè)狀態(tài) 。由于 均可取可得信源的狀態(tài)集 。這樣一來

4、，條件概率可變換成條件概率 表示任何 時(shí)刻信源處在 狀態(tài)時(shí)，發(fā)出符號(hào) 的概率。而 可任取 之一，所以可以簡(jiǎn)化成 表示。 第9頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵而在 時(shí)刻，信源發(fā)出符號(hào) 后，由符號(hào) 組成了新的信源狀態(tài) ，即信源所處的狀態(tài)也由轉(zhuǎn)移到 ，它們之間的轉(zhuǎn)移概率叫做一步轉(zhuǎn)移概率 ，簡(jiǎn)記為 ，它可由條件概率來確定，表示在 的情況下，經(jīng)一步轉(zhuǎn)移到狀態(tài) 的概率。對(duì)于齊次馬爾可夫鏈，其轉(zhuǎn)移概率具有推移不變性，因此， 可簡(jiǎn)寫為 。第10頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵推廣可得 ，它表示系統(tǒng)在時(shí)刻m處于狀

5、態(tài) ，經(jīng)(n-m)步轉(zhuǎn)移后在時(shí)刻n處于狀態(tài) 的概率。它具有以下性質(zhì)：記k步轉(zhuǎn)移概率為由于有 個(gè)狀態(tài)，所以狀態(tài)轉(zhuǎn)移概率是一個(gè)矩陣，記為：第11頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵矩陣P中第 行元素對(duì)應(yīng)與從某一個(gè)狀態(tài) 轉(zhuǎn)移到所有狀態(tài) 的轉(zhuǎn)移概率，顯然矩陣中每一個(gè)元素都是非負(fù)的，并且每行元素之和均為1； 第 列元素對(duì)應(yīng)與從所有狀態(tài) 轉(zhuǎn)移到同一個(gè)狀態(tài) 的轉(zhuǎn)移概率，列元素之和不一定為1。注意：狀態(tài)轉(zhuǎn)移矩陣與條件概率矩陣是不同的。第12頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵轉(zhuǎn)移概率的切普曼-柯爾莫郭羅夫方程：當(dāng) 時(shí)，

6、有用矩陣表示，就是第13頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵從上述的遞推關(guān)系可知，對(duì)于齊次馬爾可夫鏈來說，一步轉(zhuǎn)移概率完全決定了k步轉(zhuǎn)移概率。無條件狀態(tài)概率 的計(jì)算： 就是從初始狀態(tài)經(jīng)k步轉(zhuǎn)移后，停留在某一個(gè)狀態(tài) 的概率。為了計(jì)算這個(gè)概率，需要知道初始狀態(tài)概率，即 這時(shí)，第14頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵第15頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵轉(zhuǎn)移概率 的平穩(wěn)分布 ：兩個(gè)問題：（1）此極限是否存在；（2）如果存在，其值是多少。（1）存在問題：p23

7、（2）求法：如果存在，且等于一個(gè)與起始狀態(tài) 無關(guān)的被稱為平穩(wěn)分布的 ，則不論起始狀態(tài)是什么，此馬氏鏈可以達(dá)到最后的穩(wěn)定，即所有狀態(tài)的概率分布均不變。在這種情況下，就可以用（P）這一矩陣來充分描述穩(wěn)定的馬氏鏈，起始狀態(tài)只使前面有限個(gè)變量的分布改變，如同電路中的暫態(tài)一樣。第16頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵穩(wěn)態(tài)分布概率的求法：要求只要它存在，則上式中， 與 均為穩(wěn)態(tài)分布概率。再加上約束條件 ，兩式聯(lián)立求解，就可以求出穩(wěn)態(tài)分布概率 。第17頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵例題1:有一個(gè)二階馬氏鏈 ，

8、其符號(hào)概率如表1，狀態(tài)變量 ，求其狀態(tài)轉(zhuǎn)移概率表，畫出其狀態(tài)轉(zhuǎn)移圖，求出各狀態(tài)的平穩(wěn)分布概率。 表1 符號(hào)條件概率表 表2 狀態(tài)轉(zhuǎn)移概率表起始狀態(tài) 符 號(hào) 0 1 00 1/2 1/2 01 1/2 2/3 10 1/4 3/4 11 1/5 4/5起始狀態(tài) 終 止 狀 態(tài) (00) (01) (10) (11) 00 1/2 1/2 0 0 01 0 0 1/3 2/3 10 1/4 3/4 0 0 11 0 0 1/5 4/5第18頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵求出的狀態(tài)轉(zhuǎn)移表如表2所示。方法是：比如在狀態(tài)01時(shí)，出現(xiàn)符號(hào)0，則將0加到狀

9、態(tài)01后，再將第一位符號(hào)0擠出，轉(zhuǎn)移到狀態(tài)10，概率為1/3。依此類推。狀態(tài)轉(zhuǎn)移圖如下圖所示：第19頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵狀態(tài)轉(zhuǎn)移圖：01001011(1)1/2(0)1/4(1)2/3(0)1/5(0)1/3(1)3/4(0)1/2(1)4/5第20頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵求狀態(tài)平穩(wěn)分布概率：由得：第21頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵解之得：由例子可以看出，狀態(tài)轉(zhuǎn)移矩陣與條件概率矩陣是不同的。例題2：三態(tài)馬爾柯夫信源的狀態(tài)轉(zhuǎn)

10、移矩陣為第22頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵狀態(tài)轉(zhuǎn)移矩陣為畫出其香農(nóng)線圖，求其穩(wěn)態(tài)狀態(tài)概率分布和符號(hào)概率分布。解：香農(nóng)線圖為第23頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵穩(wěn)態(tài)狀態(tài)概率分布：解得：第24頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵 3.馬爾可夫信源的信息熵在馬爾柯夫信源輸出的符號(hào)序列中，符號(hào)之間是有依賴關(guān)系的，信源所處的起始狀態(tài)不同，信源發(fā)出的符號(hào)序列也不相同。對(duì)m階馬爾柯夫信源，能夠提供的平均信息量，即信源的極限熵 ，就等于 。 對(duì)于齊次、遍歷的馬

11、爾可夫鏈，其狀態(tài) 由 唯一決定，因此有第25頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵而第26頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵即第27頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵即式中， 是馬爾可夫鏈的平穩(wěn)分布概率，熵函數(shù) 表示信源處于某一狀態(tài) 時(shí)發(fā)出一個(gè)符號(hào)的平均不確定性，也就是說，馬爾可夫信源的平均符號(hào)熵 是信源處于某一個(gè)狀態(tài) 時(shí)發(fā)出一個(gè)符號(hào)的平均符號(hào)熵 ，在全部狀態(tài)空間的統(tǒng)計(jì)平均值。第28頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源

12、及信源熵例題3：如圖所示三態(tài)馬爾可夫信源，寫出其狀態(tài)轉(zhuǎn)移矩陣，畫出其狀態(tài)轉(zhuǎn)移圖，求出穩(wěn)態(tài)概率分布，并求其極限熵。解：由圖可以寫出其 狀態(tài)轉(zhuǎn)移矩陣為1/0.10/0.91/0.50/0.51/0.20/0.8第29頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵穩(wěn)態(tài)概率分布：解得條件熵第30頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵因此第31頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵 2.5 冗余度前幾節(jié)我們討論了各類離散信源及其信息熵。實(shí)際的離散信源可能是非平穩(wěn)的，對(duì)于非平穩(wěn)信源來

13、說，其 不一定存在，但可以假定它是平穩(wěn)的，用平穩(wěn)信源的 來近似。然而，對(duì)于一般平穩(wěn)的離散信源，求 值也是極其困難的。那么，進(jìn)一步可以假設(shè)它是m階馬爾可夫信源，用m階馬爾可夫信源的平均信息熵 來近似。如再進(jìn)一步簡(jiǎn)化信源，即可假設(shè)信源是無記憶信源，而信源符號(hào)有一定的概率分布。這時(shí)，可用信源的平均自信息量 來近似。第32頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵最后，可以假定是等概分布的無記憶離散信源，用最大熵 來近似。由此可見，由于信源符號(hào)間的依賴關(guān)系使信源的熵減小。它們的前后依賴關(guān)系越長，信源的熵越小。當(dāng)信源符號(hào)間彼此無依賴、等概率分布時(shí)，信源的熵才達(dá)到最

14、大。也就是說，信源符號(hào)之間依賴關(guān)系越強(qiáng)，每個(gè)符號(hào)提供的信息量就越小。每個(gè)符號(hào)提供的平均自信息量隨著符號(hào)間的依賴關(guān)系長度的增加而減少。為此，我們引進(jìn)信源的冗余度（也叫剩余度或多余度）來衡量信源的相關(guān)性程度。第33頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵對(duì)于一般平穩(wěn)信源來說，極限熵為 ，這就是說，如果我們要傳送這一信源的信息，理論上來說只需要有傳送 的手段即可。但實(shí)際上我們對(duì)它的概率分布不能完全掌握，如果把它近似成m階馬爾可夫信源，則可以用能傳送 的手段去傳送具有 的信源，當(dāng)然這里面就不太經(jīng)濟(jì)。我們定義信息效率為：第34頁，共44頁，2022年，5月20日

15、，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵定義為信源的冗余度。由冗余度的定義可見，信源的冗余度能夠很好地反映信源輸出的符號(hào)序列中符號(hào)之間依賴關(guān)系的強(qiáng)弱。冗余度 越大，表示信源的實(shí)際熵 越小，表明信源符號(hào)之間的依賴關(guān)系越強(qiáng)，即符號(hào)之間的記憶長度越長；反之，冗余度越小，表明信源符號(hào)之間的依賴關(guān)系越弱，即符號(hào)第35頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵之間的記憶長度越短。當(dāng)冗余度等于零時(shí)，信源的熵就等于極大熵 ，表明信源符號(hào)之間不但統(tǒng)計(jì)獨(dú)立無記憶，而且各符號(hào)還是等概分布。因此，冗余度可以用來衡量信源輸出的符號(hào)序列中各符號(hào)之間的依賴程度。例：以符號(hào)是英文

16、字母的信源為例，英文字母加上空格共有27個(gè)，則最大熵為第36頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵但實(shí)際上，用英文字母組成單詞，再由單詞組成句子時(shí)，英文字母并不是等概率出現(xiàn)，比如我們知道在英語中E出現(xiàn)的概率大于Q出現(xiàn)的概率。對(duì)在英文書中各符號(hào)的概率加以統(tǒng)計(jì)，可以得出各個(gè)字母出現(xiàn)的概率，由此得出第一級(jí)近似為無記憶信源的熵：第37頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵再考察英語的結(jié)構(gòu)得知，要組成有意義的單詞，英文字母的前后出現(xiàn)是有依賴關(guān)系的，當(dāng)前面某個(gè)字母出現(xiàn)后，后面將出現(xiàn)什么字母，并不是完全不確定的，而是有一

17、定的概率分布。例如字母T后面出現(xiàn)H、R的可能性較大，出現(xiàn)J、K、L、M、N的可能性極小，而根本不會(huì)出現(xiàn)Q、F、X?？紤]到字母之間的依賴性，可以把英語信源做進(jìn)一步精確的近似，看作一階或二階馬爾可夫信源，這樣可以求得：第38頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵因此可知，在信源所輸出的序列中依賴關(guān)系越復(fù)雜，信息熵就越小。實(shí)際上，英文信源的信息熵比還要小得多，一般認(rèn)為， 。因此，信息效率和冗余度為第39頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵這說明用英文字母寫成文章時(shí)，有71%是由語言結(jié)構(gòu)、實(shí)際意義等確定，而剩下只

18、有29%是寫文字的人可以自由選擇的。這也就意味著在傳遞或存儲(chǔ)英語信息時(shí)，只需要傳送或存儲(chǔ)那些必要的信息，而有關(guān)聯(lián)的則可以大幅度地壓縮。例如100頁的英文書，大約只要存儲(chǔ)29頁就可以了，其中的71頁可以壓縮掉，這壓縮掉的文字完全可以根據(jù)英文的統(tǒng)計(jì)特性來恢復(fù)。信源的冗余度正是表示這種信源可壓縮的程度的。第40頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵從提高傳輸信息效率的觀點(diǎn)出發(fā)，總是希望減少或去掉冗余度。如發(fā)中文電報(bào)時(shí)，為了經(jīng)濟(jì)和節(jié)省時(shí)間，總希望在原意不變的情況下，盡可能地把電文寫得簡(jiǎn)潔些。也就是說，實(shí)際的通信系統(tǒng)中，為了提高傳輸效率，往往需要把信源的大量冗余進(jìn)行壓縮，這就是所謂的信源編碼。但是，冗余度也有它的用處，因?yàn)槿哂喽却蟮南⒕哂袕?qiáng)的抗干擾能力。當(dāng)干擾使消息在傳輸過程中出現(xiàn)錯(cuò)誤時(shí)，我們能從上下關(guān)聯(lián)中糾正錯(cuò)誤。例如我們收到“中X人民X和國”時(shí)，我們很容易把它糾正為“中華人民共和國”。但若我們收到的是壓縮后的“中國”，而出現(xiàn)第41頁，共44頁，2022年，5月20日，1點(diǎn)13分，星期一信息論與編碼-信源及信源熵 了錯(cuò)誤變成了“X國”，就很難肯定發(fā)出的是“中國”、“美國”，由此將會(huì)造成很大的錯(cuò)誤。所以，從提高抗干擾能力的角度來看，總是希望增加或者保留信源的冗余度，或者是傳輸之前在信源編碼后去除冗余的符號(hào)序列里加入某些特殊的