信息論基礎(chǔ)理論與應(yīng)用3極限熵及馬科夫信源.ppt

2.5 離散平穩(wěn)信源,2.5.1 離散平穩(wěn)信源的數(shù)學(xué)定義 2.5.2 二維平穩(wěn)信源及其信息熵 2.5.3 離散平穩(wěn)信源的極限熵,2.5.1 離散平穩(wěn)信源的數(shù)學(xué)定義,實(shí)際情況下，離散信源的輸出是空間或時(shí)間的離散符號(hào)序列，而且在序列中符號(hào)之間有依賴關(guān)系.此時(shí)可用隨機(jī)矢量來(lái)描述信源發(fā)出的消息，即,其中任一變量Xi表示t=i時(shí)刻所發(fā)出的信號(hào)。信源在此時(shí)刻將要發(fā)出什么信號(hào)取決于以下兩點(diǎn)： (1) 與信源在t=i時(shí)刻隨機(jī)變量Xi的取值的概率分布P(Xi)有關(guān)。 (2) 與t=i時(shí)刻以前信源發(fā)出的符號(hào)有關(guān)，即與條件概率 P(xi|xi-1xi-2) 有關(guān),一般情況下，它也是時(shí)間t=i的函數(shù)，,如果信源分布與與時(shí)間無(wú)關(guān)，即時(shí)間的推移不引起信源統(tǒng)計(jì)特性的變化，設(shè)i、j為兩任意時(shí)刻，若有,離散平穩(wěn)信源的數(shù)學(xué)定義(1),具有這樣性質(zhì)的信源稱為一維平穩(wěn)信源,擲骰子擲5次后， 再擲第6次時(shí)，擲出的點(diǎn)數(shù)的概率分布與前5次的概率分布相同-平穩(wěn)信源,離散平穩(wěn)信源的數(shù)學(xué)定義(2),如果一維平穩(wěn)信源的聯(lián)合概率分布P(xixi+1)也與時(shí)間起點(diǎn)無(wú)關(guān)，即,（i、j為任意整數(shù)且ij）,則信源稱為二維平穩(wěn)信源。 上述等式表示任何時(shí)刻信源連續(xù)發(fā)出二個(gè)符號(hào)的聯(lián)合概率分布也完全相等。,以此類推，如果各維聯(lián)合概率分布均與時(shí)間起點(diǎn)無(wú)關(guān)，既當(dāng)t=i, t=j（i、j為任意整數(shù)且ij）時(shí)有：,離散平穩(wěn)信源的數(shù)學(xué)定義(3),2.5-1,那么，信源是完全平穩(wěn)的。這種各維聯(lián)合概率分布均與時(shí)間起點(diǎn)無(wú)關(guān)的完全平穩(wěn)信源稱為離散平穩(wěn)信源。,因?yàn)槁?lián)合概率與條件概率有以下關(guān)系：,離散平穩(wěn)信源的數(shù)學(xué)定義(4),根據(jù)2.5-1式可得,注意： 平穩(wěn)信源的條件概率與時(shí)間起點(diǎn)無(wú)關(guān)，只與關(guān)聯(lián)長(zhǎng)度N有關(guān)。如果某時(shí)刻發(fā)出什么信號(hào)與前發(fā)出的N個(gè)符號(hào)有關(guān)，那么任何時(shí)刻他們的依賴關(guān)系是一樣的。,2.5.2 二維平穩(wěn)信源及其信息熵,二維平穩(wěn)信源滿足以下條件：,設(shè)有離散一維信源的概率空間為：,二維平穩(wěn)信源的信息熵(1),由此一維信源組成的二維信源的概率空間為：,同時(shí)還已知連續(xù)兩個(gè)信源符號(hào)出現(xiàn)的聯(lián)合概率分布P(aiaj) (i, j=1,2, q) ,并有：,根據(jù)信息熵的定義可求得此信源的信息熵為：,二維平穩(wěn)信源的信息熵(2),我們把H(X1X2)稱為X1X2的聯(lián)合熵。此值表示原來(lái)信源X輸出任意一對(duì)消息的共熵，即描述信源X輸出長(zhǎng)度為2的序列的平均不確定性，或者是信息量。,因?yàn)樾旁碭發(fā)出的符號(hào)序列中前后兩個(gè)符號(hào)之間有依賴性，所以首先可以求得已知前面一個(gè)符號(hào)X1=ai信源輸出下一個(gè)符號(hào)的平均不確定性。 以下表所示的信源為例,二維平穩(wěn)信源的信息熵(3),所以，已知前面一個(gè)符號(hào)X1=ai信源輸出下一個(gè)符號(hào)的平均不確定性，即信息熵為:,上式是對(duì)下一個(gè)符號(hào)aj的可能取值進(jìn)行統(tǒng)計(jì)平均。而前一個(gè)符號(hào)X1取值范圍是a1,a2,a3,a4中的任一個(gè)。對(duì)于某一個(gè)ai存在一個(gè)平均不確定性H(X2|X1=ai)。對(duì)所有ai的可能值進(jìn)行統(tǒng)計(jì)平均就得當(dāng)前面一個(gè)符號(hào)已知時(shí)，再輸出后面一個(gè)符號(hào)的總的平均不確定性,二維平穩(wěn)信源的信息熵(4),此值為二維平穩(wěn)信源的條件熵,根據(jù)概率關(guān)系展開(kāi)式，我們可以得到聯(lián)合熵與條件熵的關(guān)系式,二維平穩(wěn)信源的信息熵(5),根據(jù)概率關(guān)系展開(kāi)式，我們可以得到聯(lián)合熵與條件熵的關(guān)系式,而上式中的第一項(xiàng)可變換為：,二維平穩(wěn)信源的信息熵(6),從上面的推導(dǎo)得： H(X1X2)=H(X1)+H(X2|X1),物理意義：聯(lián)合熵等于前一個(gè)符號(hào)出現(xiàn)的熵加上前一個(gè)符號(hào)已知時(shí)后一個(gè)符號(hào)出現(xiàn)的條件熵。 這就是熵的強(qiáng)可加性。,同理可以證明： H(X1X2)=H(X2)+H(X1|X2),二維平穩(wěn)信源的信息熵(7),條件熵與無(wú)條件熵的大小關(guān)系 H(X2|X1) H(X2),證明 在區(qū)域0，1中，設(shè)函數(shù)f(x)=-xlogx, 它在正區(qū)域內(nèi)是型函數(shù)， 設(shè)P(aj|ai)=pij,P(ai)=pi, 根據(jù)詹森不等式,得,因其中,所以有,二維平穩(wěn)信源的信息熵(8),只有當(dāng)P(aj|ai)=P(aj)時(shí),等式成立。,不難看出 H(X1X2)=H(X1)+H(X2|X1)H(X1)+H(X2) 所以 H(X1X2)2H(X),物理意義解釋： 因?yàn)楫?dāng)二個(gè)符號(hào)間有依賴關(guān)系時(shí)，就意味著在前一個(gè)符號(hào)發(fā)生的條件下，其后面跟著什么符號(hào)不是不確定的，而是有的符號(hào)發(fā)生的可能性大，有的發(fā)生的可能性小，從而平均不確定性減少。,例2.6 某離散二維平穩(wěn)信源,并設(shè)發(fā)出的符號(hào)只與前一個(gè)符號(hào)有關(guān)，即可用聯(lián)合概率P(aiaj)給出它們的關(guān)聯(lián)程度。如下表所示：,例題講解(1),表2.2 P(aiaj),例如： P(ai=0 ，aj=0 )=1/4， P(ai=0，aj=1)=1/18,例題講解(2),由概率關(guān)系可得,不難求得條件概率P(aj|ai)，把計(jì)算結(jié)果列于表2.3,表2.3 P(aj|ai),例如： P(aj=0|ai=0)=9/11， P(aj=0|ai=1)=1/8,例題講解(3),假設(shè)信源符號(hào)間無(wú)依賴性，計(jì)算得X的信源熵為,在本例中,考慮信源符號(hào)間的依賴性時(shí),計(jì)算得條件熵,或者,例題講解(4),聯(lián)合熵,可見(jiàn) H(X1X2)=H(X1)+H(X2|X1),關(guān)于本例的說(shuō)明： 信源的這個(gè)條件熵比信源無(wú)依賴時(shí)的熵H(X)減少了0.672比特，這正是符號(hào)之間有依賴性所造成的結(jié)果。 聯(lián)合熵H(X1X2)表示平均每二個(gè)信源符號(hào)所攜帶的信息量。那么平均每一個(gè)信源符號(hào)攜帶的信息量近視為 H2(X)= H(X1X2)/2=1.205（比特/符號(hào)） 可見(jiàn) H2(X) H(X),2.5.3 離散平穩(wěn)信源的極限熵,設(shè)離散平穩(wěn)有記憶信源,發(fā)出的符號(hào)序列為(,X1,X2,XN,XN+1,),假設(shè)信源符號(hào)之間的依賴長(zhǎng)度為N，并已知各維概率分布:,并滿足,符號(hào)的相互依賴關(guān)系往往不僅存在于相鄰的兩個(gè)符號(hào)之間，而且存在于更多的符號(hào)之間。所以，對(duì)于一般平穩(wěn)有記憶信源，可以證一些重要結(jié)論。為此，本節(jié)將從一維信源入手，來(lái)探討多維信源的性質(zhì),離散平穩(wěn)信源的極限熵(1),離散平穩(wěn)信源的一系列聯(lián)合熵為：,為了計(jì)算離散平穩(wěn)信源的信息熵，我們定義N長(zhǎng)的信源符號(hào)序列中平均每個(gè)信源符號(hào)所攜帶的信息量為：,此值稱為平均符號(hào)熵。,因信源符號(hào)之間的依賴關(guān)系長(zhǎng)度為N，所以可以求出已知前面N-1個(gè)符號(hào)時(shí)，后面出現(xiàn)一個(gè)符號(hào)的平均不確定性。也就是已知前面N-1個(gè)符號(hào)時(shí)，后面出現(xiàn)一個(gè)符號(hào)所攜帶的信息量，即得一系列條件熵。,離散平穩(wěn)信源的極限熵(2),對(duì)于離散平穩(wěn)信源，當(dāng)H1(X)時(shí)，具有以下幾點(diǎn)性質(zhì)： 條件熵H(XN|X1X2XN-1)隨N的增加是非遞增的 N給定時(shí)，平均符號(hào)熵條件熵 ，即 HN(X)H(XN|X1X2XN-1) 平均符號(hào)熵HN(X) 隨N的增加是非遞增的,4. 存在,且,則稱H為平穩(wěn)信源的極限熵或極限信息量。,離散平穩(wěn)信源的極限熵(3),證明 根據(jù)上文的討論，同理可以證得 H(X3|X1X2)H(X3|X2) 因?yàn)槭瞧椒€(wěn)信源，所以有 H(X3|X2)=H(X2|X1) 故得 H(X3|X1X2)H(X2|X1)H(X1) 由此遞推，對(duì)于平穩(wěn)信源有 H(XN|X1X2XN-1)H(XN-1|X1X2XN-2) H(XN-2|X1X2XN-3) H(X3|X1X2) H(X2|X1) H(X1) 性質(zhì)(1)得證,離散平穩(wěn)信源的極限熵(4),證明,根據(jù)性質(zhì)(1) NHN(X)=H(X1,X2, ,XN)=H(X1)+H(X2|X1)+H(XN|X1X2XN-1) H(XN|X1X2XN-1)+ H(XN|X1X2XN-1)+ + H(XN|X1X2XN-1) =N H(XN|X1X2XN-1) 所以證得性質(zhì)(2),即 HN(X)H(XN|X1X2XN-1),同理 NHN(X)=H(X1X2XN) = H(XN|X1X2XN-1)+ H(X1X2XN-1) = H(XN|X1X2XN-1)+(N-1)HN-1(X) 再利用性質(zhì)(2) NHN(X)HN(X) +(N-1)HN-1(X) 所以 HN(X)HN-1(X) 即平均符號(hào)熵HN(X) 隨N的增加是非遞增的。,離散平穩(wěn)信源的極限熵(5),又因 HN(X) 0 即有 0HN(X)HN-1(X)HN-2(X)H1(X),故,存在，且處于0和H1(X)之間的某一有限值。,現(xiàn)在證明性質(zhì)(4),離散平穩(wěn)信源的極限熵(7),當(dāng)k取足夠大時(shí)(k),固定N，而H(X1X2XN-1)和H(XN|X1X2XN-1)為定值，所以,上式中，再令N，因其極限存在,所以得,H(XN+k|X1X2XNXN+k-1)H(XN|X1X2XN-1) H(XN+k-1|X1X2XNXN+k-2)H(XN|X1X2XN-1) H(XN+k-2|X1X2XNXN+k-3)H(XN|X1X2XN-1) H(XN+1|X1X2XNXN+k-1)H(XN|X1X2XN-1),離散平穩(wěn)信源的極限熵(7),當(dāng)k取足夠大時(shí)(k),固定N，而H(X1X2XN-1)和H(XN|X1X2XN-1)為定值，所以,上式中，再令N，因其極限存在,所以得,離散平穩(wěn)信源的極限熵(8),根據(jù)夾逼定理得,由性質(zhì)(2)，令N，則,HN(X)H(XN|X1X2XN-1),故性質(zhì)(4)得證,2.6 馬科夫信源,2.6.1 馬科夫信源的定義 2.6.2 馬科夫信源的信源熵,馬科夫信源的定義,在非平穩(wěn)信源中，其輸出的符號(hào)系列中符號(hào)之間的依賴關(guān)系是有限的，即任何時(shí)刻信源符號(hào)發(fā)生的概率只與前面已經(jīng)發(fā)出的若干個(gè)符號(hào)有關(guān)。描述這類信源，還需引入狀態(tài)變量Ei。,設(shè)一般信源所處的狀態(tài)SE1，E2,，EJ，在每一狀態(tài)下可能的輸出的符號(hào)XA=a1，a2，aq。 當(dāng)信源發(fā)出一個(gè)符號(hào)后，信源所處的狀態(tài)將發(fā)生轉(zhuǎn)移。信源輸出的隨機(jī)符號(hào)序列為： x1,x2,xL-1,xL, ,對(duì)應(yīng)信源所處的隨機(jī)狀態(tài)序列為 E1，E2，,EL-1，EL， 在第L時(shí)刻，信源處于狀態(tài)Ei時(shí)刻，輸出符號(hào)ak的概率給定為 P(xL=ak|sL=Ei),馬科夫信源的定義,定義2.6.1 若信源符號(hào)輸出的狀態(tài)序列和信源所處的狀態(tài)序列滿足下列兩個(gè)條件：,(2),則此信源稱為馬科夫信源。,馬科夫信源的判定例解,例2.7 設(shè)信源符號(hào)XA=a1，a2，a3，信源所處的狀態(tài)SE1，E2，E3，E4，E5，各狀態(tài)之間的轉(zhuǎn)移情況由圖2.4給出。,圖2.4 狀態(tài)轉(zhuǎn)移圖,E1狀態(tài)下輸出的概率分布為 P(a1|E1)=1/2 P(a2|E1)=1/4 P(a3|E1)=1/4 E2狀態(tài)下輸出的概率分布為 P(a1|E2)=0 P(a2|E2)=1/2 P(a3|E2)=1/2 以此類推得在各狀態(tài)下的輸出概率分布表如下表所示,馬科夫信源的判定例解,可見(jiàn)，它們都符合2.6.1定義中的 (1), 另從圖中可得：,所以符合2.6.1定義中的 (2),馬科夫信源的判定例解,狀態(tài)的一步轉(zhuǎn)移概率：,可見(jiàn)此信源滿足定義2.6.1, 是馬可夫信源,馬科夫信源的極限熵,馬科夫信源的應(yīng)用,例2.7 有一個(gè)二元二階馬可夫信源，其信源符號(hào)集為0，1,條件概率定為： P(0|00)=P(1|11)=0.8 P(1|00)=P(0|11)=0.2 P(0|01)=P(0|10)=P(1|01)=P(1|10)=0.5 可見(jiàn)，此信源任何時(shí)候發(fā)出什么符號(hào)只與前兩個(gè)符號(hào)有關(guān)。那么信源有qm=22=4種可能的狀態(tài)，分別用E1(-00)、E2(-01)、E3(-10) 、E4(-11)，根據(jù)條件概率，不難畫(huà)出此二階馬可夫的信源狀態(tài)圖。,馬科夫信源的應(yīng)用,二階馬科夫信源狀態(tài)圖,狀態(tài)間的轉(zhuǎn)移概率為： P(E1|E1)=P(E4|E4)=0.8 P(E2|E1)=P(E3|E4)=0.2 P(E3|E2)=P(E2|E3) =P(E4|E2)=P(E1|E3)=0.5 除此以外，其他的轉(zhuǎn)移概率都為0，由此可見(jiàn)，狀態(tài)轉(zhuǎn)移概率完全依賴于給定的條件概率。,馬科夫信源的判定例解,二元信源發(fā)出的一串二元序列就可以變換成狀態(tài)序列。如二元序列為,馬科夫信源的信息熵,一般馬科夫信源輸出的消息是非平穩(wěn)的隨機(jī)序列，它們的各維概率分布隨時(shí)間的推移可能會(huì)改變。 根據(jù)馬科夫信源的定義，可計(jì)算得信源處于某狀態(tài)Ei時(shí)，所發(fā)出的一個(gè)信源符號(hào)所攜帶的平均信息量，即在狀態(tài)Ei下，發(fā)一個(gè)符號(hào)的條件熵為：,我們可以計(jì)算馬科夫信源的熵，將其與條件熵聯(lián)系起來(lái),馬科夫信源的信息熵,而對(duì)于m階馬科夫信源,馬科夫信源的信息熵,所以,以例2.7為例，其在各狀態(tài)下的概率為,狀態(tài)E1：P(0|E1)=0.8; P(1|E1)=0.2; H(X|Ei)=H(0.8,0.2),狀態(tài)E2：P(1|E2)=0.5; P(0|E2)=0.5; H(X|E2)=H(0.5,0.5),狀態(tài)E3：P(1|E3)=0.5; P(0|E3)=0.5; H(X|E3)=H(0.5,0.5),狀態(tài)E4：P(0|E4)=0.2; P(1|E4)=0.8; H(X|E4)=H(0.2,0.8),馬科夫信源的信息熵,以例2.7為例，其狀態(tài)轉(zhuǎn)移表為,狀態(tài)E1：P(E1|E1)=0.8; P(E2|E1)=0.2; P(Ei=3,4|E1)=0；H(X|Ei)=H(0.8,0.2),狀態(tài)E2：P(E3|E2)=0.5; P(E4|E2)=0.5; P(Ei=1,2|E2)=0; H(X|E2)=H(0.5,0.5),狀態(tài)E3：P(E1|E3)=0.5; P(E2|E3)=0.5; P(Ei=3,4|E3)=0; H(X|E3)=H(0.5,0.5),狀態(tài)E4：P(E3|E4)=0.2; P(E4|E4)=0.8; P(Ei=1,2|E4)=0; H(X|E4)=H(0.2,0.8),馬科夫信源的信息熵,求p(Ei)，根據(jù)貝耶斯公式,以此類推，并結(jié)合完備集條件，可得,解此方程得 ：,馬科夫信源的信息熵,所以，此馬科夫信源的熵為：,例題講解,設(shè)有一信源，它在開(kāi)始時(shí)以P(a)=0.6,P(b)=0.3,P(c)=0.1的概率發(fā)出X1, 如果X1為a時(shí)，則X2為a、b、c的概率為1/3；如果X1為b時(shí)，則X2為a、b、c的概率為1/3；如果X1為c時(shí)，則X2為a、b的概率為1/2；為c的概率為0。而且后面發(fā)出Xi的概率只與Xi-1有關(guān)，又P(XiXi-1)= P(X2|X1） i3，試用馬爾科夫信源的圖示法畫(huà)出狀態(tài)轉(zhuǎn)移圖，并計(jì)算信息熵,解： 依題意狀態(tài)轉(zhuǎn)移圖如下：,狀態(tài)a：P(a|a)=1/3; P(b|a)=1/3; P(c|a)=1/3；H(X|a)=H(1/3,1/3,1/3),狀態(tài)b：P(a|b)=1/3; P(b|b)=1/3; P(c|b)=0; H(X|b)=H(1/3,1/3,1/3),狀態(tài)c：P(a|c)=1/2; P(b|c)=1/2; P(c|c)=0; H(X|c)=H(1/2,1