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

信息論與編碼信源及信源熵第1頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵上一講復(fù)習(xí)互信息量：互信息量與信源熵的關(guān)系：第2頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵連續(xù)信源熵：它與離散信源熵的差別（差熵）最大熵：（1）限幅度時的最大熵（2）限平均功率時的最大熵序列信源熵：（1）離散無記憶信源序列熵：第3頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵（2）離散有記憶信源序列熵：（i）平穩(wěn)有記憶序列信源：極限熵：第4頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵二、馬爾可夫信源1.馬爾可夫信源設(shè)一般信源所處的狀態(tài)，在每一狀態(tài)下可能輸出的符號。定義：若信源輸出的符號序列和信源所處的狀態(tài)滿足以下兩個條件（1）某一時刻信源符號的輸出只與此時刻信源所處的狀態(tài)有關(guān)，而與以前的狀態(tài)及以前的輸出符號都無關(guān)，即第5頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵當(dāng)具有齊次性時，有（2）信源某時刻所處的狀態(tài)由當(dāng)前的輸出符號和前一時刻信源的狀態(tài)唯一決定，即則此信源稱為馬爾可夫信源。第6頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵上述定義和描述的是一般的馬爾可夫信源。但常見的是m階馬爾可夫信源，它在任何時刻，符號發(fā)生的概率只與前面m個符號有關(guān)，我們可以把這前面m個符號序列看作信源在此時刻所處的狀態(tài)。因?yàn)樾旁捶柤灿衠個符號，則信源可以有個不同的狀態(tài)，他們對應(yīng)于個長度為m的不同的符號序列。第7頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵因此，m階馬爾可夫離散信源的數(shù)學(xué)模型可由一組信源符號集和一組條件概率確定：并滿足第8頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵M階馬爾可夫信源在任何時刻，符號發(fā)生的概率只與前m個符號有關(guān)，所以可設(shè)狀態(tài)。由于均可取可得信源的狀態(tài)集。這樣一來，條件概率可變換成條件概率表示任何時刻信源處在狀態(tài)時，發(fā)出符號的概率。而可任取之一，所以可以簡化成表示。第9頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵而在時刻，信源發(fā)出符號后，由符號組成了新的信源狀態(tài)，即信源所處的狀態(tài)也由轉(zhuǎn)移到，它們之間的轉(zhuǎn)移概率叫做一步轉(zhuǎn)移概率，簡記為，它可由條件概率來確定，表示在的情況下，經(jīng)一步轉(zhuǎn)移到狀態(tài)的概率。對于齊次馬爾可夫鏈，其轉(zhuǎn)移概率具有推移不變性，因此，可簡寫為。第10頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵推廣可得，它表示系統(tǒng)在時刻m處于狀態(tài)，經(jīng)(n-m)步轉(zhuǎn)移后在時刻n處于狀態(tài)的概率。它具有以下性質(zhì)：記k步轉(zhuǎn)移概率為由于有個狀態(tài)，所以狀態(tài)轉(zhuǎn)移概率是一個矩陣，記為：第11頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵矩陣P中第行元素對應(yīng)與從某一個狀態(tài)轉(zhuǎn)移到所有狀態(tài)的轉(zhuǎn)移概率，顯然矩陣中每一個元素都是非負(fù)的，并且每行元素之和均為1；第列元素對應(yīng)與從所有狀態(tài)轉(zhuǎn)移到同一個狀態(tài)的轉(zhuǎn)移概率，列元素之和不一定為1。注意：狀態(tài)轉(zhuǎn)移矩陣與條件概率矩陣是不同的。第12頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵轉(zhuǎn)移概率的切普曼-柯爾莫郭羅夫方程：當(dāng)時，有用矩陣表示，就是第13頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵從上述的遞推關(guān)系可知，對于齊次馬爾可夫鏈來說，一步轉(zhuǎn)移概率完全決定了k步轉(zhuǎn)移概率。無條件狀態(tài)概率的計(jì)算：就是從初始狀態(tài)經(jīng)k步轉(zhuǎn)移后，停留在某一個狀態(tài)的概率。為了計(jì)算這個概率，需要知道初始狀態(tài)概率，即這時，第14頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵第15頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵轉(zhuǎn)移概率的平穩(wěn)分布：兩個問題：（1）此極限是否存在；（2）如果存在，其值是多少。（1）存在問題：p23（2）求法：如果存在，且等于一個與起始狀態(tài)無關(guān)的被稱為平穩(wěn)分布的，則不論起始狀態(tài)是什么，此馬氏鏈可以達(dá)到最后的穩(wěn)定，即所有狀態(tài)的概率分布均不變。在這種情況下，就可以用（P）這一矩陣來充分描述穩(wěn)定的馬氏鏈，起始狀態(tài)只使前面有限個變量的分布改變，如同電路中的暫態(tài)一樣。第16頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵穩(wěn)態(tài)分布概率的求法：要求只要它存在，則上式中，與均為穩(wěn)態(tài)分布概率。再加上約束條件，兩式聯(lián)立求解，就可以求出穩(wěn)態(tài)分布概率。第17頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵例題1:有一個二階馬氏鏈，其符號概率如表1，狀態(tài)變量，求其狀態(tài)轉(zhuǎn)移概率表，畫出其狀態(tài)轉(zhuǎn)移圖，求出各狀態(tài)的平穩(wěn)分布概率。

表1符號條件概率表表2狀態(tài)轉(zhuǎn)移概率表起始狀態(tài)符號01001/21/2011/22/3101/43/4111/54/5起始狀態(tài)終止?fàn)顟B(tài)(00)(01)(10)(11)001/21/20001001/32/3101/43/40011001/54/5第18頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵求出的狀態(tài)轉(zhuǎn)移表如表2所示。方法是：比如在狀態(tài)01時，出現(xiàn)符號0，則將0加到狀態(tài)01后，再將第一位符號0擠出，轉(zhuǎn)移到狀態(tài)10，概率為1/3。依此類推。狀態(tài)轉(zhuǎn)移圖如下圖所示：第19頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵狀態(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頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵求狀態(tài)平穩(wěn)分布概率：由得：第21頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵解之得：由例子可以看出，狀態(tài)轉(zhuǎn)移矩陣與條件概率矩陣是不同的。例題2：三態(tài)馬爾柯夫信源的狀態(tài)轉(zhuǎn)移矩陣為第22頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵狀態(tài)轉(zhuǎn)移矩陣為畫出其香農(nóng)線圖，求其穩(wěn)態(tài)狀態(tài)概率分布和符號概率分布。解：香農(nóng)線圖為第23頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵穩(wěn)態(tài)狀態(tài)概率分布：解得：第24頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵3.馬爾可夫信源的信息熵在馬爾柯夫信源輸出的符號序列中，符號之間是有依賴關(guān)系的，信源所處的起始狀態(tài)不同，信源發(fā)出的符號序列也不相同。對m階馬爾柯夫信源，能夠提供的平均信息量，即信源的極限熵，就等于。對于齊次、遍歷的馬爾可夫鏈，其狀態(tài)由唯一決定，因此有第25頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵而第26頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵即第27頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵即式中，是馬爾可夫鏈的平穩(wěn)分布概率，熵函數(shù)表示信源處于某一狀態(tài)時發(fā)出一個符號的平均不確定性，也就是說，馬爾可夫信源的平均符號熵是信源處于某一個狀態(tài)時發(fā)出一個符號的平均符號熵，在全部狀態(tài)空間的統(tǒng)計(jì)平均值。第28頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵例題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頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵穩(wěn)態(tài)概率分布：解得條件熵第30頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵因此第31頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵§2.5冗余度前幾節(jié)我們討論了各類離散信源及其信息熵。實(shí)際的離散信源可能是非平穩(wěn)的，對于非平穩(wěn)信源來說，其不一定存在，但可以假定它是平穩(wěn)的，用平穩(wěn)信源的來近似。然而，對于一般平穩(wěn)的離散信源，求值也是極其困難的。那么，進(jìn)一步可以假設(shè)它是m階馬爾可夫信源，用m階馬爾可夫信源的平均信息熵來近似。如再進(jìn)一步簡化信源，即可假設(shè)信源是無記憶信源，而信源符號有一定的概率分布。這時，可用信源的平均自信息量來近似。第32頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵最后，可以假定是等概分布的無記憶離散信源，用最大熵來近似。由此可見，由于信源符號間的依賴關(guān)系使信源的熵減小。它們的前后依賴關(guān)系越長，信源的熵越小。當(dāng)信源符號間彼此無依賴、等概率分布時，信源的熵才達(dá)到最大。也就是說，信源符號之間依賴關(guān)系越強(qiáng)，每個符號提供的信息量就越小。每個符號提供的平均自信息量隨著符號間的依賴關(guān)系長度的增加而減少。為此，我們引進(jìn)信源的冗余度（也叫剩余度或多余度）來衡量信源的相關(guān)性程度。第33頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵對于一般平穩(wěn)信源來說，極限熵為，這就是說，如果我們要傳送這一信源的信息，理論上來說只需要有傳送的手段即可。但實(shí)際上我們對它的概率分布不能完全掌握，如果把它近似成m階馬爾可夫信源，則可以用能傳送的手段去傳送具有的信源，當(dāng)然這里面就不太經(jīng)濟(jì)。我們定義信息效率為：第34頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵定義為信源的冗余度。由冗余度的定義可見，信源的冗余度能夠很好地反映信源輸出的符號序列中符號之間依賴關(guān)系的強(qiáng)弱。冗余度越大，表示信源的實(shí)際熵越小，表明信源符號之間的依賴關(guān)系越強(qiáng)，即符號之間的記憶長度越長；反之，冗余度越小，表明信源符號之間的依賴關(guān)系越弱，即符號第35頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵之間的記憶長度越短。當(dāng)冗余度等于零時，信源的熵就等于極大熵，表明信源符號之間不但統(tǒng)計(jì)獨(dú)立無記憶，而且各符號還是等概分布。因此，冗余度可以用來衡量信源輸出的符號序列中各符號之間的依賴程度。例：以符號是英文字母的信源為例，英文字母加上空格共有27個，則最大熵為第36頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵但實(shí)際上，用英文字母組成單詞，再由單詞組成句子時，英文字母并不是等概率出現(xiàn)，比如我們知道在英語中E出現(xiàn)的概率大于Q出現(xiàn)的概率。對在英文書中各符號的概率加以統(tǒng)計(jì)，可以得出各個字母出現(xiàn)的概率，由此得出第一級近似為無記憶信源的熵：第37頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵再考察英語的結(jié)構(gòu)得知，要組成有意義的單詞，英文字母的前后出現(xiàn)是有依賴關(guān)系的，當(dāng)前面某個字母出現(xiàn)后，后面將出現(xiàn)什么字母，并不是完全不確定的，而是有一定的概率分布。例如字母T后面出現(xiàn)H、R的可能性較大，出現(xiàn)J、K、L、M、N的可能性極小，而根本不會出現(xiàn)Q、F、X。考慮到字母之間的依賴性，可以把英語信源做進(jìn)一步精確的近似，看作一階或二階馬爾可夫信源，這樣可以求得：第38頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵因此可知，在信源所輸出的序列中依賴關(guān)系越復(fù)雜，信息熵就越小。實(shí)際上，英文信源的信息熵比還要小得多，一般認(rèn)為，。因此，信息效率和冗余度為第39頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵這說明用英文字母寫成文章時，有71%是由語言結(jié)構(gòu)、實(shí)際意義等確定，而剩下只有29%是寫文字的人可以自由選擇的。這也就意味著在傳遞或存儲英語信息時，只需要傳送或存儲那些必要的信息，而有關(guān)聯(lián)的則可以大幅度地壓縮。例如100頁的英文書，大約只要存儲29頁就可以了，其中的71頁可以壓縮掉，這壓縮掉的文字完全可以根據(jù)英文的統(tǒng)計(jì)特性來恢復(fù)。信源的冗余度正是表示這種信源可壓縮的程度的。第40頁，共44頁，2023年，2月20日，星期日信息論與編碼-信源及信源熵從提高傳輸信息效率的觀點(diǎn)出發(fā)，總是希望減少或去掉冗余度。如發(fā)中文電報時，為