信息論與編碼-課件第2章-1

1、信源與信息熵第二章12.1 信源的描述和分類2.2 離散信源熵和互信息2.3 離散序列信源的熵2.4 連續(xù)信源的熵和互信息2.5 冗余度2內(nèi)容本章重點信源熵和離散/連續(xù)互信息3本章難點離散序列有記憶信源的熵42.1 信源的描述和分類信源信源產(chǎn)生消息(符號)、消息序列和連續(xù)消息的來源產(chǎn)生隨機變量、隨機序列和隨機過程的源。在通信系統(tǒng)中收信者在未收到消息以前對信源發(fā)出什么消息是不確定的,是隨機的，所以可用隨機變量、隨機序列或隨機過程來描述信源輸出的消息,或者說用一個樣本空間及其概率測度概率空間來描述信源信源的基本特性：具有隨機不確定性。5香農(nóng)信息論的基本點用隨機變量或隨機矢量來表示信源用概率論和隨機

2、過程的理論來研究信息6信源的分類按照信源發(fā)出的消息在時間上和幅度上的分布情況可將信源分成離散信源和連續(xù)信源兩大類 7 信源離散信源: 文字、數(shù)據(jù)、電報隨機序列 連續(xù)信源: 話音、圖像隨機過程 連續(xù)信源指發(fā)出在時間和幅度上都是連續(xù)分布的連續(xù)消息（模擬消息）的信源，如語言、圖像、圖形等都是連續(xù)消息。 信源的分類離散信源指發(fā)出在時間和幅度上都是離散分布的離散消息的信源，如文字、數(shù)字、數(shù)據(jù)等符號都是離散消息。 8離散信源離散無記憶信源離散有記憶信源發(fā)出單個符號的無記憶信源發(fā)出符號序列的無記憶信源發(fā)出符號序列的有記憶信源發(fā)出符號序列的馬爾可夫信源2.1.1 無記憶信源離散無記憶信源所發(fā)出的各個符號是相互

3、獨立的，發(fā)出的符號序列中的各個符號之間沒有統(tǒng)計關聯(lián)性，各個符號的出現(xiàn)概率是它自身的先驗概率。9例如扔骰子，每次試驗結果必然是16點中的某一個面朝上。用一個離散型隨機變量X來描述這個信源輸出的消息。離散無記憶信源發(fā)出單個符號的信源指信源每次只發(fā)出一個符號代表一個消息；發(fā)出符號序列的信源指信源每次發(fā)出一組含二個以上符號的符號序列代表一個消息10信源的描述一個離散信源發(fā)出的各個符號消息的集合為：11它們的概率分別為p(xi): xi的先驗概率單符號離散信源的數(shù)學模型概率空間a,b,c,z離散信源的統(tǒng)計特性離散消息是從有限個符號組成的符號集中選擇排列組成的隨機序列（組成離散消息的信息源的符號個數(shù)是有限

4、的） 在形成消息時，從符號集中選擇各個符號的概率不同 。組成消息的基本符號之間有一定的統(tǒng)計相關特性 。12信源的描述連續(xù)信源：輸出在時間和幅度上都是連續(xù)分布的消息 單符號連續(xù)無記憶信源的概率空間13 隨機取一節(jié)干電池測其電壓值作為輸出符號,符號取值為0,1.5之間的所有實數(shù)。 該信源就是發(fā)出單符號的連續(xù)無記憶信源信源的描述發(fā)出符號序列的信源14設信源輸出的隨機序列為 X =(X1X2XlXL)序列中的變量Xlx1,x2, xn這種由信源X輸出的L長隨機序列X所描述的信源稱為離散無記憶信源X的L次擴展信源 信源的描述隨機序列的概率15當信源無記憶時 2.1.2 有記憶信源一般情況下,信源在不同時

5、刻發(fā)出的符號之間是相互依賴的，也就是信源輸出的平穩(wěn)隨機序列X中，各隨機變量Xl之間是有依賴的。如在漢字序列中前后文字的出現(xiàn)是有依賴的，不能認為是彼此不相關的。表述有記憶信源要比表述無記憶信源困難得多離散有記憶信源所發(fā)出的各個符號的概率是有關聯(lián)的。發(fā)出符號序列的有記憶信源發(fā)出符號序列的馬爾可夫信源16用信源發(fā)出的一個符號序列的整體概率(即聯(lián)合概率)反映有記憶信源的特征一個符號出現(xiàn)的概率只與前面一個或有限個符號有關,而不依賴更前面的那些符號概率論基礎無條件概率、條件概率、聯(lián)合概率的性質(zhì)和關系17概率論基礎無條件概率、條件概率、聯(lián)合概率的性質(zhì)和關系182.1.3 馬爾可夫信源馬爾可夫信源一類相對簡單

6、的離散平穩(wěn)信源該信源在某一時刻發(fā)出字母的概率除與該字母有關外,只與此前發(fā)出的有限個字母有關m階馬爾可夫信源：信源輸出某一符號的概率僅與以前的m個符號有關，而與更前面的符號無關。條件概率19馬氏鏈的基本概念 一階馬爾可夫信源：20若把有限個字母記作一個狀態(tài)S，則信源發(fā)出某一字母的概率除與該字母有關外，只與該時刻信源所處的狀態(tài)有關。信源將來的狀態(tài)及其送出的字母將只與信源現(xiàn)在的狀態(tài)有關，而與信源過去的狀態(tài)無關。馬氏鏈的基本概念 令si = (xi1, xi2, xim) xi1,xi2, xim (a1, a2, an)狀態(tài)集S = s1,s2,sQ Q = nm信源輸出的隨機符號序列為：x1, x

7、2,x i-1, x i信源所處的隨機狀態(tài)序列為：s1,s2,si-1 ,si,例：二元序列為01011100考慮m = 2，Q = nm =22= 4s1 = 00 s2 = 01 s3 = 10 s4 = 11變換成對應的狀態(tài)序列為 s2 s3 s2 s4 s4 s3 s121馬爾可夫信源設信源在時刻m處于si狀態(tài),它在下一時刻(m+1)狀態(tài)轉(zhuǎn)移到sj的轉(zhuǎn)移概率為： pij(m) = pSm+1=sj| Sm= si=psj | sipij(m)：基本轉(zhuǎn)移概率（一步轉(zhuǎn)移概率）若pij(m)與m 的取值無關,則稱為齊次馬爾可夫鏈 pij= pSm+1=sj| Sm= si= pS2=sj|

8、S1= sipij具有下列性質(zhì)： pij022若信源處于某一狀態(tài)si ,當它發(fā)出一個符號后,所處狀態(tài)就變了,任何時候信源處于什么狀態(tài)完全由前一時刻的狀態(tài)和發(fā)出符號決定。 系統(tǒng)在任一時刻可處于狀態(tài)空間S = s1,s2,sQ中的任意一個狀態(tài),狀態(tài)轉(zhuǎn)移時,轉(zhuǎn)移概率矩陣23符號條件概率矩陣例2-1，如圖所示是一個相對碼編碼器,輸入的碼Xr(r=1,2,)是相互獨立的，取值0或1，且已知P(X=0)=p, P(X=1)=1p=q，輸出的碼是Yr，顯然24TXrYrYr-1+Yr是一個馬氏鏈,Yr確定后,Yr+1概率分布只與Yr有關,與Yr-1 、Yr-2 等無關,且知Yr序列的條件概率p00= P(Y

9、2=0/Y1=0)= P(X=0)= p p01= P(Y2=1/Y1=0)= P(X=1)= q p10= P(Y2=0/Y1=1)= P(X=1)= q p11= P(Y2=1/Y1=1)= P(X=0)= p 25sos1pqqp馬爾可夫信源狀態(tài)轉(zhuǎn)移圖齊次馬爾可夫鏈可以用其狀態(tài)轉(zhuǎn)移圖(香農(nóng)線圖)表示每個圓圈代表一種狀態(tài) 狀態(tài)之間的有向線代表某一狀態(tài)向另一狀態(tài)的轉(zhuǎn)移有向線一側的符號和數(shù)字分別代表發(fā)出的符號和條件概率26sos11/0.60/0.30/0.4s21/0.20/0.81/0.727s3s2s4s5s1s6周期性的：在常返態(tài)中,有些狀態(tài)僅當k能被某整數(shù)d1整除時才有pij(k)0

10、,圖中的周期為2；x5:1非周期性的：對于pij(k)0的所有k值，其最大公約數(shù)為1。 常返態(tài)：經(jīng)有限步后遲早要返回的狀態(tài)，x4:1x3:1/2x2:1/2x3:1/2x2:1/2x2:1/2x4:1/4x1:1/4x6:1x6:1/4馬爾可夫信源遍歷狀態(tài)：非周期的、常返的狀態(tài),如圖中的狀態(tài)s2和s3閉集：狀態(tài)空間中的某一子集中的任何一狀態(tài)都不能到達子集以外的任何狀態(tài)不可約的：閉集中除自身全體外再沒有其他閉集的閉集28馬爾可夫信源一個不可約的、非周期的、狀態(tài)有限的馬爾可夫鏈其k步轉(zhuǎn)移概率pij(k)在k時趨于一個和初始狀態(tài)無關的極限概率Wj，它是滿足方程組 的唯一解；Wj ：馬爾可夫鏈的一個平

11、穩(wěn)分布， Wj p(sj)就是系統(tǒng)此時處于狀態(tài)sj的概率。29例30sos11/0.60/0.30/0.4s21/0.20/0.81/0.7例2-2：有一個二元二階馬爾可夫信源,其信源符號集為0，1，已知符號條件概率： p(0|00) = 1/2 p(1|00)=1/2 p(0|01) = 1/3 p(1|01)=2/3 p(0|10) = 1/4 p(1|10)=3/4 p(0|11) = 1/5 p(1|11)=4/5求：信源全部狀態(tài)及狀態(tài)轉(zhuǎn)移概率畫出完整的二階馬爾可夫信源狀態(tài)轉(zhuǎn)移圖。 求平穩(wěn)分布概率 3132狀態(tài)轉(zhuǎn)移概率矩陣符號條件概率矩陣(1)1/2(0)1/2(0)1/3(1)2/3

12、00011110s2s1s4s3(1)3/4(0)1/4(0)1/5(1)4/533穩(wěn)態(tài)分布概率穩(wěn)態(tài)后的符號概率分布例 一個二元二階馬爾可夫信源,其信源符號集為0,1信源開始時：p(0) = p(1) = 0.5發(fā)出隨機變量X1。 下一單位時間：輸出隨機變量X2與X1有依賴關系x2x10100.30.410.70.634p(x2|x1)再下一單位時間：輸出隨機變量X3與X2X1有依賴關系x3x1 x20001101100.40.20.30.410.60.80.70.6p(x3|x1x2)從第四單位時間開始，隨機變量Xi只與前面二個單位時間的隨機變量Xi-2Xi-1有依賴關系: p(xi| xi

13、-1 xi-2x2 x1) = p(xi| xi-1 xi-2) (i3) 且 p(xi| xi-1 xi-2) = p(x3| x2x1) (i3) 35解:設信源開始處于s0狀態(tài),并以等概率發(fā)出符號0和1,分別到達狀態(tài)s1和s2 :若處于s1 ,以0.3和0.7的概率發(fā)出0和1到達s3和s4若處于s2,以0.4和0.6的概率發(fā)出0和1到達s5和s600011011(0)0.5(1)0.5(0)0.3(0)0.4(1)0.7(1)0.6s1s2s0s6s5s4s3信源發(fā)完第2個符號后再發(fā)第3個及以后的符號。從第3單位時間以后信源必處在s3 s4 s5 s6四種狀態(tài)之一。在i3后,信源的狀態(tài)轉(zhuǎn)移可用下圖表示:3610110100(0)0.3(0)0.4(1)0.7(0)0.2(1)0.8(1)0.6(0)0.4(1)0.6狀態(tài)s1和s5功能是完全相同 狀態(tài)s2和s6功能是完全相同可將二圖合并成s3s4s5s6s0(0)0.5(1)0.5s0是過渡狀態(tài)s3 s