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

信息論基礎(chǔ)理論與應(yīng)用極限熵及馬科夫信源第1頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月2.5.1離散平穩(wěn)信源的數(shù)學(xué)定義實(shí)際情況下，離散信源的輸出是空間或時(shí)間的離散符號(hào)序列，而且在序列中符號(hào)之間有依賴(lài)關(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ù)，第2頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月如果信源分布與與時(shí)間無(wú)關(guān)，即時(shí)間的推移不引起信源統(tǒng)計(jì)特性的變化，設(shè)i、j為兩任意時(shí)刻，若有離散平穩(wěn)信源的數(shù)學(xué)定義(1)具有這樣性質(zhì)的信源稱(chēng)為一維平穩(wěn)信源擲骰子——擲5次后，再擲第6次時(shí)，擲出的點(diǎn)數(shù)的概率分布與前5次的概率分布相同---------------〉平穩(wěn)信源第3頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月離散平穩(wěn)信源的數(shù)學(xué)定義(2)

如果一維平穩(wěn)信源的聯(lián)合概率分布P(xixi+1)也與時(shí)間起點(diǎn)無(wú)關(guān)，即（i、j為任意整數(shù)且i≠j）

則信源稱(chēng)為二維平穩(wěn)信源。上述等式表示任何時(shí)刻信源連續(xù)發(fā)出二個(gè)符號(hào)的聯(lián)合概率分布也完全相等。以此類(lèi)推，如果各維聯(lián)合概率分布均與時(shí)間起點(diǎn)無(wú)關(guān)，既當(dāng)t=i,t=j（i、j為任意整數(shù)且i≠j）時(shí)有：第4頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月離散平穩(wěn)信源的數(shù)學(xué)定義(3)

2.5-1那么，信源是完全平穩(wěn)的。這種各維聯(lián)合概率分布均與時(shí)間起點(diǎn)無(wú)關(guān)的完全平穩(wěn)信源稱(chēng)為離散平穩(wěn)信源。因?yàn)槁?lián)合概率與條件概率有以下關(guān)系：第5頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月離散平穩(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í)刻他們的依賴(lài)關(guān)系是一樣的。第6頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月2.5.2二維平穩(wěn)信源及其信息熵二維平穩(wěn)信源滿(mǎn)足以下條件：設(shè)有離散一維信源的概率空間為：第7頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月二維平穩(wěn)信源的信息熵(1)由此一維信源組成的二維信源的概率空間為：同時(shí)還已知連續(xù)兩個(gè)信源符號(hào)出現(xiàn)的聯(lián)合概率分布P(aiaj)(i,j=1,2,…,q),并有：

根據(jù)信息熵的定義可求得此信源的信息熵為：第8頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月二維平穩(wěn)信源的信息熵(2)

我們把H(X1X2)稱(chēng)為X1X2的聯(lián)合熵。此值表示原來(lái)信源X輸出任意一對(duì)消息的共熵，即描述信源X輸出長(zhǎng)度為2的序列的平均不確定性，或者是信息量。

因?yàn)樾旁碭發(fā)出的符號(hào)序列中前后兩個(gè)符號(hào)之間有依賴(lài)性，所以首先可以求得已知前面一個(gè)符號(hào)X1=ai信源輸出下一個(gè)符號(hào)的平均不確定性。以下表所示的信源為例Xi Xi+1a1a2a3a4a1P(a1/a1)P(a2/a1)P(a3/a1)P(a4/a1)a2P(a1/a2)P(a2/a2)P(a3/a2)P(a4/a2)a3P(a1/a3)P(a2/a3)P(a3/a3)P(a4/a3)a4P(a1/a4)P(a2/a4)P(a3/a4)P(a4/a4)第9頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月二維平穩(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)的總的平均不確定性第10頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月二維平穩(wěn)信源的信息熵(4)此值為二維平穩(wěn)信源的條件熵

根據(jù)概率關(guān)系展開(kāi)式，我們可以得到聯(lián)合熵與條件熵的關(guān)系式第11頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月二維平穩(wěn)信源的信息熵(5)根據(jù)概率關(guān)系展開(kāi)式，我們可以得到聯(lián)合熵與條件熵的關(guān)系式而上式中的第一項(xiàng)可變換為：第12頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月二維平穩(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)第13頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月二維平穩(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ù)詹森不等式得因其中所以有第14頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月二維平穩(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)物理意義解釋?zhuān)阂驗(yàn)楫?dāng)二個(gè)符號(hào)間有依賴(lài)關(guān)系時(shí)，就意味著在前一個(gè)符號(hào)發(fā)生的條件下，其后面跟著什么符號(hào)不是不確定的，而是有的符號(hào)發(fā)生的可能性大，有的發(fā)生的可能性小，從而平均不確定性減少。第15頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月[例2.6]某離散二維平穩(wěn)信源并設(shè)發(fā)出的符號(hào)只與前一個(gè)符號(hào)有關(guān)，即可用聯(lián)合概率P(aiaj)給出它們的關(guān)聯(lián)程度。如下表所示：例題講解(1)表2.2P(aiaj)ajai01201／41／18011／181／31／18201／187／36例如：P(ai=0，aj=0)=1/4，P(ai=0，aj=1)=1/18第16頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月例題講解(2)由概率關(guān)系可得不難求得條件概率P(aj|ai)，把計(jì)算結(jié)果列于表2.3ajai01209／111／8012／113／42／9201／87／9表2.3P(aj|ai)例如：P(aj=0|ai=0)=9/11，P(aj=0|ai=1)=1/8第17頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月例題講解(3)假設(shè)信源符號(hào)間無(wú)依賴(lài)性，計(jì)算得X的信源熵為在本例中,考慮信源符號(hào)間的依賴(lài)性時(shí),計(jì)算得條件熵或者

第18頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月例題講解(4)聯(lián)合熵可見(jiàn)

H(X1X2)=H(X1)+H(X2|X1)關(guān)于本例的說(shuō)明：信源的這個(gè)條件熵比信源無(wú)依賴(lài)時(shí)的熵H(X)減少了0.672比特，這正是符號(hào)之間有依賴(lài)性所造成的結(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)第19頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月2.5.3離散平穩(wěn)信源的極限熵設(shè)離散平穩(wěn)有記憶信源發(fā)出的符號(hào)序列為(…,X1,X2,…,XN,XN+1,…),假設(shè)信源符號(hào)之間的依賴(lài)長(zhǎng)度為N，并已知各維概率分布:

并滿(mǎn)足符號(hào)的相互依賴(lài)關(guān)系往往不僅存在于相鄰的兩個(gè)符號(hào)之間，而且存在于更多的符號(hào)之間。所以，對(duì)于一般平穩(wěn)有記憶信源，可以證一些重要結(jié)論。為此，本節(jié)將從一維信源入手，來(lái)探討多維信源的性質(zhì)第20頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月離散平穩(wěn)信源的極限熵(1)離散平穩(wěn)信源的一系列聯(lián)合熵為：為了計(jì)算離散平穩(wěn)信源的信息熵，我們定義N長(zhǎng)的信源符號(hào)序列中平均每個(gè)信源符號(hào)所攜帶的信息量為：此值稱(chēng)為平均符號(hào)熵。因信源符號(hào)之間的依賴(lài)關(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)所攜帶的信息量，即得一系列條件熵。第21頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月離散平穩(wěn)信源的極限熵(2)對(duì)于離散平穩(wěn)信源，當(dāng)H1(X)<∞時(shí)，具有以下幾點(diǎn)性質(zhì)：條件熵H(XN|X1X2…XN-1)隨N的增加是非遞增的N給定時(shí)，平均符號(hào)熵≥條件熵，即HN(X)≥H(XN|X1X2…XN-1)平均符號(hào)熵HN(X)

隨N的增加是非遞增的4.

存在且則稱(chēng)H∞為平穩(wěn)信源的極限熵或極限信息量。第22頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月離散平穩(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|X1X2…XN-1)≤H(XN-1|X1X2…XN-2)≤H(XN-2|X1X2…XN-3)≤…≤H(X3|X1X2)≤H(X2|X1)≤H(X1)性質(zhì)(1)得證第23頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月離散平穩(wěn)信源的極限熵(4)[證明]根據(jù)性質(zhì)(1)NHN(X)=H(X1,X2,‥,XN)=H(X1)+H(X2|X1)+‥+H(XN|X1X2‥XN-1)≥H(XN|X1X2…XN-1)+H(XN|X1X2…XN-1)+

…+H(XN|X1X2…XN-1)=NH(XN|X1X2…XN-1)所以證得性質(zhì)(2),即

HN(X)≥H(XN|X1X2…XN-1)同理

NHN(X)=H(X1X2…XN)=H(XN|X1X2…XN-1)+H(X1X2…XN-1)=H(XN|X1X2…XN-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的增加是非遞增的。第24頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月離散平穩(wěn)信源的極限熵(5)又因

HN(X)≥0即有

0≤HN(X)≤HN-1(X)≤HN-2(X)≤…≤H1(X)<∞故存在，且處于0和H1(X)之間的某一有限值。現(xiàn)在證明性質(zhì)(4)第25頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月離散平穩(wěn)信源的極限熵(7)當(dāng)k取足夠大時(shí)(k－>∞),固定N，而H(X1X2…XN-1)和H(XN|X1X2…XN-1)為定值，所以上式中，再令N－>∞，因其極限存在所以得

第26頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月

H(XN+k|X1X2‥XN‥XN+k-1)≤H(XN|X1X2…XN-1)H(XN+k-1|X1X2‥XN‥XN+k-2)≤H(XN|X1X2…XN-1)H(XN+k-2|X1X2‥XN‥XN+k-3)≤H(XN|X1X2…XN-1)﹕H(XN+1|X1X2‥XN‥XN+k-1)≤H(XN|X1X2…XN-1)第27頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月離散平穩(wěn)信源的極限熵(7)當(dāng)k取足夠大時(shí)(k－>∞),固定N，而H(X1X2…XN-1)和H(XN|X1X2…XN-1)為定值，所以上式中，再令N－>∞，因其極限存在所以得

第28頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月離散平穩(wěn)信源的極限熵(8)根據(jù)夾逼定理得

由性質(zhì)(2)，令N－>∞，則HN(X)≥H(XN|X1X2…XN-1)故性質(zhì)(4)得證

第29頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月2.6馬科夫信源2.6.1馬科夫信源的定義

2.6.2馬科夫信源的信源熵第30頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月馬科夫信源的定義

在非平穩(wěn)信源中，其輸出的符號(hào)系列中符號(hào)之間的依賴(lài)關(guān)系是有限的，即任何時(shí)刻信源符號(hào)發(fā)生的概率只與前面已經(jīng)發(fā)出的若干個(gè)符號(hào)有關(guān)。描述這類(lèi)信源，還需引入狀態(tài)變量Ei。

設(shè)一般信源所處的狀態(tài)S∈｛E1，E2,…，EJ，在每一狀態(tài)下可能的輸出的符號(hào)X∈A=｛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)第31頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月馬科夫信源的定義定義2.6.1

若信源符號(hào)輸出的狀態(tài)序列和信源所處的狀態(tài)序列滿(mǎn)足下列兩個(gè)條件：(2)則此信源稱(chēng)為馬科夫信源。第32頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月馬科夫信源的判定例解[例2.7]設(shè)信源符號(hào)X∈A=｛a1，a2，a3｝，信源所處的狀態(tài)S∈｛E1，E2，E3，E4，E5｝，各狀態(tài)之間的轉(zhuǎn)移情況由圖2.4給出。圖2.4狀態(tài)轉(zhuǎn)移圖E1狀態(tài)下輸出的概率分布為

P(a1|E1)=1/2P(a2|E1)=1/4P(a3|E1)=1/4

E2狀態(tài)下輸出的概率分布為

P(a1|E2)=0P(a2|E2)=1/2P(a3|E2)=1/2以此類(lèi)推得在各狀態(tài)下的輸出概率分布表如下表所示

第33頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月馬科夫信源的判定例解可見(jiàn)，它們都符合2.6.1定義中的(1),另從圖中可得：所以符合2.6.1定義中的(2)第34頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月馬科夫信源的判定例解狀態(tài)的一步轉(zhuǎn)移概率：

可見(jiàn)此信源滿(mǎn)足定義2.6.1,是馬可夫信源第35頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月馬科夫信源的極限熵第36頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月馬科夫信源的應(yīng)用[例2.7]有一個(gè)二元二階馬可夫信源，其信源符號(hào)集為[0，1],條件概率定為：

P(0|00)=P(1|11)=0.8P(1|00)=P(0|11)=0.2P(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)圖。第37頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月馬科夫信源的應(yīng)用二階馬科夫信源狀態(tài)圖狀態(tài)間的轉(zhuǎn)移概率為：

P(E1|E1)=P(E4|E4)=0.8P(E2|E1)=P(E3|E4)=0.2P(E3|E2)=P(E2|E3)=P(E4|E2)=P(E1|E3)=0.5除此以外，其他的轉(zhuǎn)移概率都為0，由此可見(jiàn)，狀態(tài)轉(zhuǎn)移概率完全依賴(lài)于給定的條件概率。第38頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月馬科夫信源的判定例解二元信源發(fā)出的一串二元序列就可以變換成狀態(tài)序列。如二元序列為第39頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月馬科夫信源的信息熵

一般馬科夫信源輸出的消息是非平穩(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)第40頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月馬科夫信源的信息熵而對(duì)于m階馬科夫信源第41頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月馬科夫信源的信息熵所以以例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)第42頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月馬科夫信源的信息熵以例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)第43頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月馬科夫信源的信息熵求p(Ei)，根據(jù)貝耶斯公式以此類(lèi)推，并結(jié)合完備集條件，可得解此方程得：第44頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月馬科夫信源的信息熵所以，此馬科夫信源的熵為：

第45頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月例題講解設(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(Xi︱Xi-1)=P(X2|X1）i≥3，試用馬爾科夫信源的圖示法畫(huà)出狀態(tài)轉(zhuǎn)移圖，并計(jì)算信息熵[解