2.5.1離散平穩信源的數學定義實際情況下，離散信源的輸出是空間或時間的離散符號序列，而且在序列中符號之間有依賴關系.此時可用隨機矢量來描述信源發出的消息，即其中任一變量Xi表示t=i時刻所發出的信號。信源在此時刻將要發出什么信號取決于以下兩點：(1)與信源在t=i時刻隨機變量Xi的取值的概率分布P(Xi)有關。(2)與t=i時刻以前信源發出的符號有關，即與條件概率P(xi|xi-1xi-2…)

有關,一般情況下，它也是時間t=i的函數，第一頁，共50頁。如果信源分布與與時間無關，即時間的推移不引起信源統計特性的變化，設i、j為兩任意時刻，若有離散平穩信源的數學定義(1)具有這樣性質的信源稱為一維平穩信源擲骰子——擲5次后，再擲第6次時，擲出的點數的概率分布與前5次的概率分布相同---------------〉平穩信源第二頁，共50頁。離散平穩信源的數學定義(2)如果一維平穩信源的聯合概率分布P(xixi+1)也與時間起點無關，即（i、j為任意整數且i≠j）則信源稱為二維平穩信源。上述等式表示任何時刻信源連續發出二個符號的聯合概率分布也完全相等。以此類推，如果各維聯合概率分布均與時間起點無關，既當t=i,t=j（i、j為任意整數且i≠j）時有：第三頁，共50頁。離散平穩信源的數學定義(3)

2.5-1那么，信源是完全平穩的。這種各維聯合概率分布均與時間起點無關的完全平穩信源稱為離散平穩信源。因為聯合概率與條件概率有以下關系：第四頁，共50頁。離散平穩信源的數學定義(4)根據2.5-1式可得注意：平穩信源的條件概率與時間起點無關，只與關聯長度N有關。如果某時刻發出什么信號與前發出的N個符號有關，那么任何時刻他們的依賴關系是一樣的。第五頁，共50頁。2.5.2二維平穩信源及其信息熵二維平穩信源滿足以下條件：設有離散一維信源的概率空間為：第六頁，共50頁。二維平穩信源的信息熵(1)由此一維信源組成的二維信源的概率空間為：同時還已知連續兩個信源符號出現的聯合概率分布P(aiaj)(i,j=1,2,…,q),并有：

根據信息熵的定義可求得此信源的信息熵為：第七頁，共50頁。二維平穩信源的信息熵(2)我們把H(X1X2)稱為X1X2的聯合熵。此值表示原來信源X輸出任意一對消息的共熵，即描述信源X輸出長度為2的序列的平均不確定性，或者是信息量。因為信源X發出的符號序列中前后兩個符號之間有依賴性，所以首先可以求得已知前面一個符號X1=ai信源輸出下一個符號的平均不確定性。以下表所示的信源為例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)第八頁，共50頁。二維平穩信源的信息熵(3)所以，已知前面一個符號X1=ai信源輸出下一個符號的平均不確定性，即信息熵為:上式是對下一個符號aj的可能取值進行統計平均。而前一個符號X1取值范圍是｛a1,a2,a3,a4｝中的任一個。對于某一個ai存在一個平均不確定性H(X2|X1=ai)。對所有ai的可能值進行統計平均就得當前面一個符號已知時，再輸出后面一個符號的總的平均不確定性第九頁，共50頁。二維平穩信源的信息熵(4)此值為二維平穩信源的條件熵

根據概率關系展開式，我們可以得到聯合熵與條件熵的關系式第十頁，共50頁。二維平穩信源的信息熵(5)根據概率關系展開式，我們可以得到聯合熵與條件熵的關系式而上式中的第一項可變換為：第十一頁，共50頁。二維平穩信源的信息熵(6)從上面的推導得：

H(X1X2)=H(X1)+H(X2|X1)物理意義：聯合熵等于前一個符號出現的熵加上前一個符號已知時后一個符號出現的條件熵。這就是熵的強可加性。同理可以證明：

H(X1X2)=H(X2)+H(X1|X2)第十二頁，共50頁。二維平穩信源的信息熵(7)條件熵與無條件熵的大小關系

H(X2|X1)≤H(X2)[證明]

在區域[0，1]中，設函數f(x)=-xlogx,它在正區域內是∩型函數，設P(aj|ai)=pij,P(ai)=pi,根據詹森不等式得因其中所以有第十三頁，共50頁。二維平穩信源的信息熵(8)只有當P(aj|ai)=P(aj)時,等式成立。不難看出

H(X1X2)=H(X1)+H(X2|X1)≤H(X1)+H(X2)所以

H(X1X2)≤2H(X)物理意義解釋：因為當二個符號間有依賴關系時，就意味著在前一個符號發生的條件下，其后面跟著什么符號不是不確定的，而是有的符號發生的可能性大，有的發生的可能性小，從而平均不確定性減少。第十四頁，共50頁。[例2.6]某離散二維平穩信源并設發出的符號只與前一個符號有關，即可用聯合概率P(aiaj)給出它們的關聯程度。如下表所示：例題講解(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第十五頁，共50頁。例題講解(2)由概率關系可得不難求得條件概率P(aj|ai)，把計算結果列于表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第十六頁，共50頁。例題講解(3)假設信源符號間無依賴性，計算得X的信源熵為在本例中,考慮信源符號間的依賴性時,計算得條件熵或者

第十七頁，共50頁。例題講解(4)聯合熵可見

H(X1X2)=H(X1)+H(X2|X1)關于本例的說明：信源的這個條件熵比信源無依賴時的熵H(X)減少了0.672比特，這正是符號之間有依賴性所造成的結果。聯合熵H(X1X2)表示平均每二個信源符號所攜帶的信息量。那么平均每一個信源符號攜帶的信息量近視為H2(X)=H(X1X2)/2=1.205（比特/符號）可見

H2(X)<H(X)第十八頁，共50頁。2.5.3離散平穩信源的極限熵設離散平穩有記憶信源發出的符號序列為(…,X1,X2,…,XN,XN+1,…),假設信源符號之間的依賴長度為N，并已知各維概率分布:

并滿足符號的相互依賴關系往往不僅存在于相鄰的兩個符號之間，而且存在于更多的符號之間。所以，對于一般平穩有記憶信源，可以證一些重要結論。為此，本節將從一維信源入手，來探討多維信源的性質第十九頁，共50頁。離散平穩信源的極限熵(1)離散平穩信源的一系列聯合熵為：為了計算離散平穩信源的信息熵，我們定義N長的信源符號序列中平均每個信源符號所攜帶的信息量為：此值稱為平均符號熵。因信源符號之間的依賴關系長度為N，所以可以求出已知前面N-1個符號時，后面出現一個符號的平均不確定性。也就是已知前面N-1個符號時，后面出現一個符號所攜帶的信息量，即得一系列條件熵。第二十頁，共50頁。離散平穩信源的極限熵(2)對于離散平穩信源，當H1(X)<∞時，具有以下幾點性質：條件熵H(XN|X1X2…XN-1)隨N的增加是非遞增的N給定時，平均符號熵≥條件熵，即HN(X)≥H(XN|X1X2…XN-1)平均符號熵HN(X)隨N的增加是非遞增的4.

存在且則稱H∞為平穩信源的極限熵或極限信息量。第二十一頁，共50頁。離散平穩信源的極限熵(3)[證明]

根據上文的討論，同理可以證得

H(X3|X1X2)≤H(X3|X2)因為是平穩信源，所以有

H(X3|X2)=H(X2|X1)

故得

H(X3|X1X2)≤H(X2|X1)≤H(X1)由此遞推，對于平穩信源有

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)性質(1)得證第二十二頁，共50頁。離散平穩信源的極限熵(4)[證明]根據性質(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)所以證得性質(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)再利用性質(2)

NHN(X)≤HN(X)+(N-1)HN-1(X)所以

HN(X)≤HN-1(X)即平均符號熵HN(X)隨N的增加是非遞增的。第二十三頁，共50頁。離散平穩信源的極限熵(5)又因

HN(X)≥0即有0≤HN(X)≤HN-1(X)≤HN-2(X)≤…≤H1(X)<∞故存在，且處于0和H1(X)之間的某一有限值。現在證明性質(4)第二十四頁，共50頁。離散平穩信源的極限熵(7)當k取足夠大時(k－>∞),固定N，而H(X1X2…XN-1)和H(XN|X1X2…XN-1)為定值，所以上式中，再令N－>∞，因其極限存在所以得

第二十五頁，共50頁。

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)第二十六頁，共50頁。離散平穩信源的極限熵(7)當k取足夠大時(k－>∞),固定N，而H(X1X2…XN-1)和H(XN|X1X2…XN-1)為定值，所以上式中，再令N－>∞，因其極限存在所以得

第二十七頁，共50頁。離散平穩信源的極限熵(8)根據夾逼定理得

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

第二十八頁，共50頁。2.6馬科夫信源2.6.1馬科夫信源的定義2.6.2馬科夫信源的信源熵第二十九頁，共50頁。馬科夫信源的定義在非平穩信源中，其輸出的符號系列中符號之間的依賴關系是有限的，即任何時刻信源符號發生的概率只與前面已經發出的若干個符號有關。描述這類信源，還需引入狀態變量Ei。設一般信源所處的狀態S∈｛E1，E2,…，EJ，在每一狀態下可能的輸出的符號X∈A=｛a1，a2，…，aq｝。當信源發出一個符號后，信源所處的狀態將發生轉移。信源輸出的隨機符號序列為：

x1,x2,…,xL-1,xL,…對應信源所處的隨機狀態序列為

E1，E2，…,EL-1，EL，…在第L時刻，信源處于狀態Ei時刻，輸出符號ak的概率給定為

P(xL=ak|sL=Ei)第三十頁，共50頁。馬科夫信源的定義若信源符號輸出的狀態序列和信源所處的狀態序列滿足下列兩個條件：(2)則此信源稱為馬科夫信源。第三十一頁，共50頁。馬科夫信源的判定例解[例2.7]設信源符號X∈A=｛a1，a2，a3｝，信源所處的狀態S∈｛E1，E2，E3，E4，E5｝，各狀態之間的轉移情況由圖2.4給出。圖2.4狀態轉移圖E1狀態下輸出的概率分布為

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

E2狀態下輸出的概率分布為

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

第三十二頁，共50頁。馬科夫信源的判定例解可見，它們都符合2.6.1定義中的(1),另從圖中可得：所以符合2.6.1定義中的(2)第三十三頁，共50頁。馬科夫信源的判定例解狀態的一步轉移概率：

可見此信源滿足定義2.6.1,是馬可夫信源第三十四頁，共50頁。馬科夫信源的極限熵第三十五頁，共50頁。馬科夫信源的應用[例2.7]有一個二元二階馬可夫信源，其信源符號集為[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可見，此信源任何時候發出什么符號只與前兩個符號有關。那么信源有qm=22=4種可能的狀態，分別用E1(-—00)、E2(-—01)、E3(—-10)、E4(-—11)，根據條件概率，不難畫出此二階馬可夫的信源狀態圖。第三十六頁，共50頁。馬科夫信源的應用二階馬科夫信源狀態圖狀態間的轉移概率為：

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除此以外，其他的轉移概率都為0，由此可見，狀態轉移概率完全依賴于給定的條件概率。第三十七頁，共50頁。馬科夫信源的判定例解二元信源發出的一串二元序列就可以變換成狀態序列。如二元序列為第三十八頁，共50頁。馬科夫信源的信息熵

一般馬科夫信源輸出的消息是非平穩的隨機序列，它們的各維概率分布隨時間的推移可能會改變。

根據馬科夫信源的定義，可計算得信源處于某狀態Ei時，所發出的一個信源符號所攜帶的平均信息量，即在狀態Ei下，發一個符號的條件熵為：我們可以計算馬科夫信源的熵，將其與條件熵聯系起來第三十九頁，共50頁。馬科夫信源的信息熵而對于m階馬科夫信源第四十頁，共50頁。馬科夫信源的信息熵所以以例2.7為例，其在各狀態下的概率為狀態E1：P(0|E1)=0.8;P(1|E1)=0.2;H(X|Ei)=H(0.8,0.2)狀態E2：P(1|E2)=0.5;P(0|E2)=0.5;H(X|E2)=H(0.5,0.5)狀態E3：P(1|E3)=0.5;P(0|E3)=0.5;H(X|E3)=H(0.5,0.5)狀態E4：P(0|E4)=0.2;P(1|E4)=0.8;H(X|E4)=H(0.2,0.8)第四十一頁，共50頁。馬科夫信源的信息熵以例2.7為例，其狀態轉移表為狀態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)狀態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)狀態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)狀態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)第四十二頁，共50頁。馬科夫信源的信息熵求p(Ei)，根據貝耶斯公式以此類推，并結合完備集條件，可得解此方程得：第四十三頁，共50頁。馬科夫信源的信息熵所以，此馬科夫信源的熵為：

第四十四頁，共50頁。例題講解設有一信源，它在開始時以P(a)=0.6,P(b)=0.3,P(c)=0.1的概率發出X1,如果X1為a時，則X2為a、b、c的概率為1/3；如果X1為b時，則X2為a、b、c的概率為1/3；；如果X1為c時，則X2為a、b的概率為1/2；為c的概率為0。而且后面發出Xi的概率只與Xi-1有關，又P(Xi︱Xi-1)=P(X2|X1）i≥3，試用馬爾科夫信源的圖示法畫出狀態轉移圖，并計算信息熵[解]：依題意狀態轉移圖如下：狀態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)狀態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)狀態c：P(a|c)=1/2;P(b|c)=1/2;P(c|c)=0;

H(X|c)=H(1/2,1/2,0)第四十五頁，共50頁。例題講解根據貝葉斯可得：P(a)=P(a)P(a|a)+P(b)P(a|b)+P(c)P(a|c)P(b)=P(a)P(b|a)+P(b)P(b|b)+P(c)P(b|c)P(c)=P(a)P(c|a)+P(b)P(c|b)+P(c)P(c|c)