多符號(hào)離散平穩(wěn)信源的熵課件

上一講復(fù)習(xí)

1.信源的分類

連續(xù)信源

信源單符號(hào)無(wú)記憶離散信源離散信源單符號(hào)有記憶離散信源符號(hào)序列無(wú)記憶離散信源符號(hào)序列有記憶離散信源

2.信源的數(shù)學(xué)模型多符號(hào)無(wú)記憶離散信源：用概率空間自信息量信源熵平均互信息量一些關(guān)系式條件自信息量聯(lián)合自信息量前面我們討論的只是最基本的離散信源，即信源每次輸出只是單個(gè)符號(hào)的消息，給出了用信息熵H(X)來(lái)對(duì)基本離散信源進(jìn)行信息測(cè)度，研究了信息熵的基本性質(zhì)。然而信源每次輸出的不是一個(gè)單個(gè)的符號(hào)，而是一個(gè)符號(hào)序列。通常一個(gè)消息序列的每一位出現(xiàn)哪個(gè)符號(hào)都是隨機(jī)的，而且一般前后符號(hào)之間的出現(xiàn)是有統(tǒng)計(jì)依賴關(guān)系的，這種信源稱之為多符號(hào)離散信源。若信源所發(fā)符號(hào)序列的概率分布與時(shí)間的起點(diǎn)無(wú)關(guān)，這種信源我們稱之為多符號(hào)離散平穩(wěn)信源。如中文自然語(yǔ)言文字，離散化平面灰度圖像都是這種離散型平穩(wěn)信源。2.2多符號(hào)離散平穩(wěn)信源通常用隨機(jī)矢量來(lái)描述信源發(fā)出的消息序列，即其中任一變量Xi

都是隨機(jī)變量，它表示t=i時(shí)刻所發(fā)出的符號(hào)。信源在t=i時(shí)刻將要發(fā)出什么樣的符號(hào)決定于以下兩方面：1.

與信源在t=i時(shí)刻隨機(jī)變量Xi的取值的概率分布p(xi)有關(guān)。一般情況下，t不同時(shí)，概率分布也不同，即

2.

與t=i時(shí)刻以前信源發(fā)出的符號(hào)有關(guān)，即與條件概率有關(guān)。同樣在一般情況下，它也是時(shí)間t的函數(shù)，所以以上所敘述的是一般隨機(jī)序列的情況，它比較復(fù)雜。下面只討論離散無(wú)記憶序列信源和兩種比較簡(jiǎn)單的離散有記憶序列信源：平穩(wěn)序列信源齊次遍歷馬氏鏈信源離散有記憶序列信源2.2.1離散無(wú)記憶的N次擴(kuò)展信源的熵如果有一個(gè)離散無(wú)記憶信源X，取值于集合{a1,a2,…,an}，其輸出消息序列可用一組長(zhǎng)度為N的序列來(lái)表示即等效于一個(gè)新的信源。新信源每次輸出的是長(zhǎng)度為N的消息序列，用N維離散隨機(jī)矢量來(lái)描述

Xi(i=1,2,…,N)，其中每個(gè)分量Xi都是隨機(jī)變量，它們都取值于同一集合{a1,a2,…,an}

，且分量之間統(tǒng)計(jì)獨(dú)立，則由隨機(jī)矢量X組成的新信源稱為離散無(wú)記憶信源X的N次擴(kuò)展信源。這種信源在不同時(shí)刻發(fā)出的符號(hào)之間是無(wú)依賴的，彼此統(tǒng)計(jì)獨(dú)立的。例：若X={a1,a2}={0,1}，n=2，則二元無(wú)記憶信源的二次擴(kuò)展信源為：X2={00,01,10,11}，N=2（符號(hào)組的長(zhǎng)度，擴(kuò)展次數(shù)）,q=22=4.二元無(wú)記憶信源的三次擴(kuò)展信源為：X3={000，001，010，011，111，100，110，101}，N=3,q=23=8.二元無(wú)記憶信源的N次擴(kuò)展信源為：新信源具有q=2N個(gè)符號(hào)。n元無(wú)記憶信源的N次擴(kuò)展信源為：新信源具有q=nN個(gè)符號(hào)。理解若單符號(hào)離散信源的數(shù)學(xué)模型為：則信源X的N次擴(kuò)展信源用XN來(lái)表示，該新信源有nN

個(gè)元素（消息序列），其數(shù)學(xué)模型為：其中q=nN

，每個(gè)符號(hào)αi

對(duì)應(yīng)于某個(gè)由N個(gè)xi

組成的序列，而αi的概率p(αi)是對(duì)應(yīng)的N個(gè)ai的概率組成的概率序列，考慮到信源是無(wú)記憶的，故消息序列

的概率為則N次擴(kuò)展信源的熵（消息信息的熵）為：理解因?yàn)槭请x散無(wú)記憶信源符號(hào)序列概率:設(shè)離散信源是由n個(gè)符號(hào)消息組成的集合

X=｛a1

,a2,…,an｝若離散信源所發(fā)出的消息是集合X中N個(gè)符號(hào)組成的符號(hào)序列XN=(a1,a2,…,aq)，其中ai∈{ai1

,ai2,…,ain}，則XN稱為

X

的N次擴(kuò)展，N

稱為符號(hào)序列的長(zhǎng)度。注意：ai1

,ai2,…,ain可以在｛a1,a2,…,an｝中重復(fù)選取。

X的N次擴(kuò)展的不同的符號(hào)序列共有nN個(gè)。【例】X=｛a1,a2

｝

X2=｛a1a1,a1

a2

,a2

a1,a2

a1

｝

X3=｛a1a1

a1,a1

a1

a2

,a1

a1

a2

,a1

a2

a1,…

,x2

a2

a2

｝1o

符號(hào)序列概率

P(XN)=P(a1a2…aq)=P(a1)P(a2/a1)P(a3/a1a2)…P(aq/a1a2

,…,aq-1)

2o當(dāng)信源無(wú)記憶時(shí)

P(XN)=P(a1a2,…,aq)=P(a1)P(a2)P(a3)…P(aq)二、無(wú)記憶信源的序列熵

例:

X=｛a1,a2｝,p(a1)=0.2,p(a2)=0.8

則H(X)=–0.2log20.2–0.8log20.8=0.464+0.258=0.722bit/符號(hào)

X2=｛a1a1,a1

a2

,a2

a1,a2

a1

｝={α1,α2,α3,α4}p(α1)=p(a1a1)=p(a1)p(a1)=0.04p(α2)=p(a1a2)=p(a1)p(a2)=0.16p(α3)=p(a2a1)=p(a2)p(a1)=0.16p(α4)=p(a2

a2)=p(a2)p(a2)=0.64H(X2)=0.186+0.423+0.423+0.412=1.444=2

H(X)或H(X2)=-{p(a1)p(a1)logp(a1)p(a1)+p(a1)p(a2)logp(a1)p(a2)+p(a2)p(a1)logp(a1)p(a2)+p(a2)p(a2)logp(a2)p(a2)}=-{[2p(a1)p(a1)+2p(a1)p(a2)]

logp(a1)

+[2p(a1)p(a2)+2p(a2)p(a2)]logp(a2)}=-2{p(a1)logp(a1)+p(a2)logp(a2)}=2H(X)

因

p(a1)+p(a2)=1p(x1)=0.2,p(x2)=0.8離散無(wú)記憶信源X，其信源熵為H(X)。1.則離散無(wú)記憶信源的序列熵：記為H(XN)

H(XN)=NH(X)序列熵的單位：bit/序列消息或bit/每N個(gè)消息2.序列的平均每個(gè)符號(hào)消息的熵：記為HN(X)【例2.2.1】離散平穩(wěn)無(wú)記憶信源X的N次擴(kuò)展信源的熵為離散信源X的熵的N倍，即H(XN)=NH(X)

證明：∑求和是對(duì)信源XN中所有nN個(gè)元素求和，可以等效成N個(gè)求和,而其中的每一個(gè)又是對(duì)X中的n個(gè)元素求和，所以有：(2.2.6)(2.2.5)共有N項(xiàng)，考察其中第一項(xiàng)因?yàn)橥砥溆喔黜?xiàng)均等于H(X)，故有所以(2.2.8)(2.2.7)

【例2.2.2】一離散平穩(wěn)無(wú)記憶信源解：先求出此離散平穩(wěn)無(wú)記憶信源的二次擴(kuò)展信源。擴(kuò)展信源的每個(gè)元素是信源X的輸出長(zhǎng)度為N=2的消息序列。由于擴(kuò)展信源是無(wú)記憶的，故

X2信源的元素α1α

2α

3α

4α

5α

6α

7α

8α

9對(duì)應(yīng)的消息序列a1a1a1a2a1a3a2a1a2a2a2a3a3a1a3a2a3a3概率p(α

i)1/41/81/81/81/161/161/81/161/16求此信源的二次擴(kuò)展信源的熵。n=3N=2nN=32=9根據(jù)熵的定義，二次擴(kuò)展信源的熵為結(jié)論：計(jì)算（無(wú)記憶）擴(kuò)展信源的熵時(shí)，不必構(gòu)造新的信源，可直接從原信源X的熵導(dǎo)出。即離散平穩(wěn)無(wú)記憶信源X的N次擴(kuò)展信源的熵為離散信源X的熵的N倍。思考：證明二維離散有記憶信源的熵不大于二維平穩(wěn)無(wú)記憶信源的熵？

【例2.2.3】將二維離散平穩(wěn)有記憶信源推廣到N維情況，可證明證明：則表明：多符號(hào)離散平穩(wěn)有記憶信源X的熵H(X)是X中起始時(shí)刻隨機(jī)變量X1的熵與各階條件熵之和?？偨Y(jié)：多符號(hào)離散平穩(wěn)信源實(shí)際上就是原始信源在不斷地發(fā)出符號(hào)，符號(hào)之間的統(tǒng)計(jì)關(guān)聯(lián)關(guān)系也并不限于長(zhǎng)度N之內(nèi)，而是伸向無(wú)窮遠(yuǎn)。所以要研究實(shí)際信源，必須求出信源的極限熵，才能確切地表達(dá)多符號(hào)離散平穩(wěn)有記憶信源平均每發(fā)一個(gè)符號(hào)提供的信息量。問(wèn)題的關(guān)鍵在于極限熵是否存在？當(dāng)離散有記憶信源是平穩(wěn)信源時(shí)，從數(shù)學(xué)上可以證明，極限熵是存在的，且等于關(guān)聯(lián)長(zhǎng)度N→∞時(shí)，條件熵H(XN/X1X2…XN-1)的極限值。極限熵代表了一般離散平穩(wěn)有記憶信源平均每發(fā)一個(gè)符號(hào)提供的信息。一般情況下有下式成立（2.2.30）

一般情況下，信源在不同時(shí)刻發(fā)出的符號(hào)之間是相互依賴的。也就是信源輸出的平穩(wěn)隨機(jī)序列X中，各隨機(jī)變量Xi之間是有依賴的。如在漢字組成的中文序列中，只有根據(jù)中文的語(yǔ)法、習(xí)慣用語(yǔ)、修辭制約和表達(dá)實(shí)際意義的制約所構(gòu)成的中文序列才是有意義的中文句子或文章。所以，在漢字序列中前后文字的出現(xiàn)是有依賴的，不能認(rèn)為是彼此不相關(guān)的。其他如英文，德文等自然語(yǔ)言都是如此。這種信源稱為有記憶信源。我們需在N維隨機(jī)矢量的聯(lián)合概率分布中，引入條件概率分布來(lái)說(shuō)明它們之間的關(guān)聯(lián)。2.2.2離散平穩(wěn)(有記憶)信源的數(shù)學(xué)模型平穩(wěn)隨機(jī)序列：是序列的統(tǒng)計(jì)性質(zhì)與時(shí)間的推移無(wú)關(guān)，即信源所發(fā)符號(hào)序列的概率分布與時(shí)間起點(diǎn)無(wú)關(guān)。若任意兩個(gè)不同時(shí)刻i和j，信源發(fā)出消息的概率完全相同，則稱這種信源為一維平穩(wěn)信源。即在任何時(shí)刻信源發(fā)出符號(hào)的概率完全相同。除上述條件外，如果聯(lián)合概率分布也與時(shí)間起點(diǎn)無(wú)關(guān)，則稱信源為二維平穩(wěn)信源。這種信源在任何時(shí)刻發(fā)出兩個(gè)符號(hào)的概率完全相同，即各維聯(lián)合概率均與時(shí)間起點(diǎn)無(wú)關(guān)的完全平穩(wěn)信源稱為離散平穩(wěn)信源。2.2.3離散平穩(wěn)信源的信源熵和極限熵離散平穩(wěn)信源一般是指有記憶的信源，即發(fā)出的各個(gè)符號(hào)之間具有統(tǒng)計(jì)關(guān)聯(lián)關(guān)系的一類信源。這種統(tǒng)計(jì)關(guān)聯(lián)性可用兩種方式表示：用信源發(fā)出的一個(gè)符號(hào)序列的整體概率，即N個(gè)符號(hào)的聯(lián)合概率來(lái)反映有記憶信源的特征，這種信源是發(fā)出符號(hào)序列的有記憶信源。用信源發(fā)出符號(hào)序列中各個(gè)符號(hào)之間的條件概率來(lái)反映記憶特征，這是發(fā)出符號(hào)序列的馬爾可夫信源。一、有記憶二維平穩(wěn)信源的信息熵二維平穩(wěn)信源是所發(fā)出的隨機(jī)序列中只有兩相鄰符號(hào)之間有依賴關(guān)系的信源。所以只需給出隨機(jī)序列的一維和二維概率分布就能很好地從數(shù)學(xué)上描述離散二維平穩(wěn)信源。1.二維平穩(wěn)信源的數(shù)學(xué)模型

假定，則矢量相應(yīng)的概率分布為得X的數(shù)學(xué)模型為并且即新的信源也滿足概率的歸一性。2.二維平穩(wěn)有記憶信源的熵根據(jù)信源熵的定義有（2.2.20）其中

由（2.2.20）式得到這樣一個(gè)結(jié)論：兩個(gè)有相互依賴關(guān)系的隨機(jī)變量X1和X2所組成的隨機(jī)矢量X=X1X2的聯(lián)合熵H(X)，等于第一個(gè)隨機(jī)變量的熵H(X1)與第一個(gè)隨機(jī)變量X1已知的前提下，第二個(gè)隨機(jī)變量X2的條件熵之和H(X2/X1)

。特例：當(dāng)X1和X2相互統(tǒng)計(jì)獨(dú)立時(shí)，則由概率的性質(zhì)有當(dāng)X1和X2相互統(tǒng)計(jì)獨(dú)立時(shí)，二維離散平穩(wěn)無(wú)記憶信源X=X1X2的聯(lián)合熵H(X)，等于第一個(gè)隨機(jī)變量的熵H(X1)與第二個(gè)隨機(jī)變量的熵H(X2)之和。其中二、N維離散平穩(wěn)有記憶信源的熵離散平穩(wěn)信源有記憶信源的聯(lián)合熵H(X1X2…XN)表示平均每發(fā)一個(gè)消息序列(由N個(gè)符號(hào)組成)所提供的信息量。從數(shù)學(xué)角度出發(fā)，信源平均發(fā)一個(gè)符號(hào)序列所提供的信息量應(yīng)為稱HN(X)為平均符號(hào)熵，當(dāng)N→∞時(shí)，平均符號(hào)熵取極限值，稱為極限熵或極限信息量，即極限熵是否存在？如何計(jì)算？對(duì)于離散平穩(wěn)信源，當(dāng)H1(X)<∞時(shí)，具有以下性質(zhì)：條件熵H(XN/X1X2…XN-1)

隨N的增加是非遞增的；N給定時(shí)，平均符號(hào)熵≥條件熵，即HN(X)≥

H(XN/X1X2…XN-1)平均符號(hào)熵HN(X)

隨N增加是非遞增的。說(shuō)明：條件較多的熵必小于或等于條件較少的熵，而條件熵必小于等于無(wú)條件熵；對(duì)于離散平穩(wěn)信源，當(dāng)考慮依賴關(guān)系為無(wú)限長(zhǎng)時(shí)，平均符號(hào)熵和條件熵都非遞增地一致趨于平穩(wěn)信源的信息熵（極限熵）?？捎脳l件熵或平均符號(hào)熵來(lái)作為平穩(wěn)信源極限熵的近似值?！纠?.2-4】已知離散有記憶信源中各符號(hào)的概率空間為現(xiàn)信源發(fā)出二重符號(hào)序列消息(aiaj)，這兩個(gè)符號(hào)的關(guān)聯(lián)性用條件概率p(aj/ai)表示，并由下表給出。求信源的序列熵和平均符號(hào)熵。X1

X2

a0a1a2a09/112/110a11/83/41/8a202/97/9p(aj/ai)條件熵為單符號(hào)信源熵為X1

X2

a0a1a2a09/112/110a11/83/41/8a202/97/9p(aj/ai)解：發(fā)二重符號(hào)序列的熵為平均符號(hào)熵為比較上述結(jié)果可知：H2(X)<H1(X)，即二重序列的符號(hào)熵值較單符號(hào)熵變小了，也就是不確定度減小了，這是由于符號(hào)之間存在相關(guān)性造成的。H1(X)=1.543bit/signH(X2/X1)=0.872bit/sign對(duì)離散平穩(wěn)信源，其聯(lián)合概率具有時(shí)間推移不變性，此時(shí)有如下結(jié)論：（1）H(XN/XN-1)是N的單調(diào)非增函數(shù)。（2）HN

(X)≥H(XN/XN-1).（3）HN

(X)是N的單調(diào)非增函數(shù)。（4）當(dāng)N→∞時(shí)，

H∞(X)稱為極限熵，又稱為極限信息量。于是有：式中，H0(X)為等概率無(wú)記憶信源單個(gè)符號(hào)的熵，H1(X)為一般無(wú)記憶信源單個(gè)符號(hào)的熵，H2(X)為兩個(gè)符號(hào)組成的序列平均符號(hào)熵，依此類推。結(jié)論：公式（2.2.30）從理論上定義了平穩(wěn)離散有記憶信源的極限熵，對(duì)于一般的離散平穩(wěn)信源，實(shí)際上求此極限值是相當(dāng)困難的。但對(duì)于一般的離散平穩(wěn)信源，由于N值不是很大，所以可用非常接近H∞

(X)的H(XN/X1X2

…XN-1)的極限值來(lái)代替。因此，可用條件熵H(XN/X1X2

…XN-1)或者平均符號(hào)熵HN(X)取極限時(shí)作為平穩(wěn)信源極限熵的近似值。2.2.4馬爾可夫信源馬爾可夫信源的概念馬爾可夫信源的轉(zhuǎn)移概率m階馬爾可夫信源的數(shù)學(xué)模型m階馬爾可夫信源的極限熵等于m階條件熵。m階馬爾可夫信源與消息長(zhǎng)度為m的有記憶信源的區(qū)別。如果信源符號(hào)表中的數(shù)目為n，則由前面出現(xiàn)的m個(gè)符號(hào)所組成的序列si共有J＝nm種,將這些序列看作是狀態(tài)集S={s1,s2,…,sJ},則信源在某一時(shí)刻出現(xiàn)符號(hào)aj的概率就與信源此時(shí)所處的狀態(tài)si有關(guān)，用條件概率表示為p(aj/si)，i=1,2,...,J；j=l,2,…,n。所有的狀態(tài)構(gòu)成狀態(tài)空間，每種狀態(tài)以一定的概率發(fā)生，其數(shù)學(xué)模型為1.馬爾可夫信源顯然當(dāng)信源符號(hào)aj出現(xiàn)后，信源所處的狀態(tài)將發(fā)生變化，并轉(zhuǎn)入一個(gè)新的狀態(tài)。用轉(zhuǎn)移概率p{sj/si}表示，si,sj∈S狀態(tài)轉(zhuǎn)移概率p(sj/si)由信源符號(hào)條件概率p(aj/si)確定。

設(shè)一般信源所處的狀態(tài)S∈{s1,s2,…,sJ}，在每一狀態(tài)下可能輸出的符號(hào)為其中ak1ak2…akm為符號(hào)序列.定義：若信源輸出的符號(hào)序列和信源所處的狀態(tài)滿足以下兩個(gè)條件：(1)在某一時(shí)刻l，信源符號(hào)的輸出只與此時(shí)刻信源所處的狀態(tài)有關(guān)，而與以前的狀態(tài)及以前的輸出符號(hào)都無(wú)關(guān)，這時(shí)描述符號(hào)之間依賴關(guān)系的條件概率為如果條件概率與時(shí)間起點(diǎn)無(wú)關(guān)，即信源輸出的消息可看成為齊次（時(shí)齊）馬爾可夫鏈，則此信源稱為齊次馬爾可夫信源。當(dāng)具有齊次性時(shí)，有（2）信源l時(shí)刻所處的狀態(tài)由當(dāng)前的輸出符號(hào)和前一時(shí)刻l-1信源的狀態(tài)唯一決定，即則此信源稱為馬爾可夫信源。式（2.2.39）中，成立時(shí)取1，不成立取0。條件(2)表明，若信源處于某一狀態(tài)si

，當(dāng)它發(fā)出一個(gè)符號(hào)后，所處的狀態(tài)就變了，一定從狀態(tài)si轉(zhuǎn)移到另一狀態(tài)。顯然，狀態(tài)的轉(zhuǎn)移依賴于發(fā)出的信源符號(hào)，因此任何時(shí)刻信源處在什么狀態(tài)完全由前一時(shí)刻的狀態(tài)和當(dāng)前發(fā)出的符號(hào)決定。又因條件概率p(ak/si)已給定，所以狀態(tài)之間的轉(zhuǎn)移有一定的概率分布，并可求得狀態(tài)的一步轉(zhuǎn)移概率p(sj/si)?？梢杂民R爾可夫鏈的狀態(tài)轉(zhuǎn)移圖來(lái)描述信源。在狀態(tài)轉(zhuǎn)移圖上，把J個(gè)可能的狀態(tài)中每一個(gè)狀態(tài)用圓圈表示，然后它們之間用有向線連接，以此表示信源發(fā)出某符號(hào)后由某一狀態(tài)轉(zhuǎn)移到另一狀態(tài)。并把發(fā)出的某符號(hào)xk及條件概率p(ak/si)標(biāo)注在有向線的一側(cè).對(duì)于一階馬爾可夫信源，它的狀態(tài)轉(zhuǎn)移概率與信源輸出符號(hào)的條件概率p(ak/si)或符號(hào)轉(zhuǎn)移概率相同。上述定義和描述的是一般的馬爾可夫信源。但常見(jiàn)的是m階馬爾可夫信源，它在任何時(shí)刻l

，符號(hào)發(fā)生的概率只與前面m個(gè)符號(hào)有關(guān)，可以把這前面m個(gè)符號(hào)序列看作信源在此l時(shí)刻所處的狀態(tài)。因?yàn)樾旁捶?hào)集共有n個(gè)符號(hào)，則信源可以有nm個(gè)不同的狀態(tài)，它們對(duì)應(yīng)于nm個(gè)長(zhǎng)度為m的不同的符號(hào)序列。2.m階馬爾可夫離散信源的數(shù)學(xué)模型m階馬爾可夫信源在任何時(shí)刻l，符號(hào)發(fā)生的概率只與前面m個(gè)符號(hào)有關(guān)，所以可設(shè)狀態(tài)si=(ak1,ak2,…,akm)。由于k1,k2,…,km

均可取1,2,…,n

，可得信源的狀態(tài)集S={s1,s2,…,sJ}，J=nm。這樣一來(lái)，條件概率可變換成條件概率p(ak+1/si

)表示任何時(shí)刻l信源處在si

狀態(tài)時(shí)，發(fā)出符號(hào)ak+1

的概率。而ak+1可任取a1,a2,…,an

中之一，所以可以簡(jiǎn)化成ak

表示。

因此，m階馬爾可夫離散信源的數(shù)學(xué)模型可由一組信源符號(hào)集和一組條件概率確定：并滿足當(dāng)m=1時(shí)，任何時(shí)刻信源符號(hào)發(fā)生的概率只與前面一個(gè)符號(hào)有關(guān)，稱為一階馬爾可夫信源。信源發(fā)出符號(hào)aj

后，由符號(hào)(aj,aj-1

,…,aj-m+1)組成了新的信源狀態(tài)sj=(aj,aj-1

,…,aj-m+1)∈S，這時(shí)信源所處的狀態(tài)也由si轉(zhuǎn)移到sj

，它們之間的轉(zhuǎn)移概率叫做一步轉(zhuǎn)移概率，簡(jiǎn)記為pij(m)，它可由狀態(tài)概率p(sj

/si)來(lái)確定，表示m時(shí)刻系統(tǒng)處于狀態(tài)si

的條件下，經(jīng)一步轉(zhuǎn)移到狀態(tài)sj

的概率。對(duì)于齊次馬爾可夫鏈，其轉(zhuǎn)移概率具有推移不變性，因此pij(m)可簡(jiǎn)寫(xiě)為pij

。3.馬爾可夫信源的狀態(tài)轉(zhuǎn)移概率p(sj/si)馬爾可夫信源的狀態(tài)空間：

或它是一個(gè)具有J2個(gè)元素的方陣，表示共有J2個(gè)可能的轉(zhuǎn)移概率數(shù)目，它的每行元素代表同一個(gè)起始狀態(tài)到J個(gè)不同的終止?fàn)顟B(tài)的轉(zhuǎn)移概率，每列代表J個(gè)不同的起始狀態(tài)到同一個(gè)終止?fàn)顟B(tài)的轉(zhuǎn)移概率。矩陣P中第i

行元素對(duì)應(yīng)于從某一個(gè)狀態(tài)s

轉(zhuǎn)移到所有狀態(tài)sj的轉(zhuǎn)移概率，顯然矩陣中每一個(gè)元素都是非負(fù)的，并且每行元素之和均為1。第j

列元素對(duì)應(yīng)于從所有狀態(tài)si

轉(zhuǎn)移到同一個(gè)狀態(tài)sj

的轉(zhuǎn)移概率，列元素之和不一定為1。注意：狀態(tài)轉(zhuǎn)移矩陣與符號(hào)條件概率矩陣是不同的。

在馬爾柯夫信源輸出的符號(hào)序列中，符號(hào)之間是有依賴關(guān)系的，信源所處的起始狀態(tài)不同，信源發(fā)出的符號(hào)序列也不相同。對(duì)m階馬爾柯夫信源，能夠提供的平均信息量，即信源的極限熵H∞，就等于Hm+1

。4.馬爾可夫信源的熵對(duì)于齊次、遍歷的馬爾可夫鏈，其狀態(tài)si由唯一決定，因此有而

即式中：p(si)是馬爾可夫鏈的狀態(tài)極限概率，熵函數(shù)H(X/si)表示信源處于某一狀態(tài)si時(shí)發(fā)出一個(gè)符號(hào)的平均不確定性，即也就是說(shuō)，馬爾可夫信源的m階條件熵Hm+1是信源處于某一個(gè)狀態(tài)si

時(shí)發(fā)出一個(gè)符號(hào)的平均符號(hào)熵H(X/si)在全部狀態(tài)空間的統(tǒng)計(jì)平均值。即表明m階馬爾可夫信源的極限熵H∞就等于m階條件熵Hm+1.其中p(si)是m階馬爾可夫信源穩(wěn)定后的狀態(tài)極限概率。

由（2.2.30）式可得m階馬爾可夫信源的極限熵（2.2.35）（2.2.30）稱這種馬爾可夫鏈?zhǔn)歉鲬B(tài)歷經(jīng)的。其極限概率是方程組滿足條件的惟一解。這就是有限齊次馬爾可夫鏈的各態(tài)歷經(jīng)定理。定理：對(duì)于有限齊次馬爾可夫鏈，若存在一個(gè)正整數(shù)l0≥1，對(duì)一切i，j=1,2,…，nm都有，則對(duì)每一個(gè)j都存在不依賴于i的極限(2.2.36)先求出一步狀態(tài)轉(zhuǎn)移概率p(sj/si)；再利用

和約束條件求出狀態(tài)極限概率p(sj)。（2.2.36）狀態(tài)極限概率p(sj)的求法：根據(jù)題意畫(huà)出狀態(tài)轉(zhuǎn)移圖，判斷是否為時(shí)齊遍歷馬爾可夫信源。根據(jù)狀態(tài)轉(zhuǎn)移圖，寫(xiě)出一步轉(zhuǎn)移概率矩陣，計(jì)算信源所處狀態(tài)的極限概率。根據(jù)一步轉(zhuǎn)移概率矩陣和極限概率計(jì)算信源的熵。馬爾可夫信源熵的求解步驟：【例2.2.2】有一個(gè)二階馬氏鏈X∈{0,1}，其符號(hào)概率如表1，狀態(tài)變量S∈(00,01,10,11)，求其狀態(tài)轉(zhuǎn)移概率表，畫(huà)出其狀態(tài)轉(zhuǎn)移圖，求狀態(tài)極限概率。起始狀態(tài)符號(hào)

01

00s11/21/201s21/32/310s31/43/411s41/54/5表1符號(hào)條件概率表解：求出的狀態(tài)轉(zhuǎn)移概率如表2所示。方法是：如在狀態(tài)01時(shí)，出現(xiàn)符號(hào)0，則將0加到狀態(tài)01后，再將第一位符號(hào)0擠出，轉(zhuǎn)移到狀態(tài)10，概率為1/3。依此類推。起始狀態(tài)符號(hào)

01

00s11/21/201s21/3

2/310s31/43/411s41/54/5起始狀態(tài)

終止?fàn)顟B(tài)

00s1

01s2

10s3

11s4

00s11/21/20001s200

1/3

2/310s31/43/40011s400

1/54/5表2狀態(tài)轉(zhuǎn)移概率表1符號(hào)條件概率表狀態(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/5s1,s2,s3,s4是四種狀態(tài)，箭頭是指從一個(gè)狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)，旁邊的數(shù)字代表轉(zhuǎn)移概率。這就是香農(nóng)提出的馬爾可夫狀態(tài)圖，也叫香農(nóng)線圖。s1s2s3s4起始狀態(tài)

終止?fàn)顟B(tài)

00s1

01s2

10s3

11s4

00s11/21/20001s200

1/3

2/310s31/43/40011s400

1/54/5求狀態(tài)極限概率：起始狀態(tài)

終止?fàn)顟B(tài)00s101s210s3

11s4

00s11/21/20001s200

1/32/310s31/43/40011s400

1/54/5P(s1)=P(s1)/2+P(s3)/4P(s2)=P(s1)/2+3P(s3)/4P(s3)=P(s2)/3+

P(s4)/5P(s4)=2P(s2)/3+4P(s4)/5P(s1)+P(s2)+

P(s3)+

P(s4)=1得解之得：P(s1)=3/35P(s2)=6/35P(s3)=6/35P(s4)=4/7由例子可以看出，狀態(tài)轉(zhuǎn)移矩陣與條件概率矩陣是不同的。【例2.2.3】設(shè)有一馬氏鏈,初始概率分布為p(s1)=0.6，p(s2)=0.3，p(s3)=0.1，p(s1/s1)=p(s2/s1)=p(s3/s1)=1/3，p(s1/s2)=p(s2/s2)=p(s3/s2)=1/3,p(s1/s3)=p(s2/s3)=1/2，p(s3/s3)=0.（1）寫(xiě)出該信源的狀態(tài)轉(zhuǎn)移概率矩陣；（2）畫(huà)出狀態(tài)轉(zhuǎn)移圖；（3）求信源的平穩(wěn)狀態(tài)分布；（4）計(jì)算平穩(wěn)信源的熵H∞

。

解：s1P=s2s3s1s2s3(1)該信源的狀態(tài)轉(zhuǎn)移概率矩陣為（2）畫(huà)出狀態(tài)轉(zhuǎn)移圖s1s3s2s1P=s2s3s1s2s3（3）求信源的平穩(wěn)狀態(tài)分布=[p(s1)p(s2)p(s3)][p(s1)p(s2)p(s3)]（4）計(jì)算平穩(wěn)信源的熵H∞或畫(huà)出其香農(nóng)線圖，求其狀態(tài)極限概率分布和符號(hào)概率分布。解：香農(nóng)線圖為【例2.2.4】三態(tài)馬爾可夫信源的狀態(tài)轉(zhuǎn)移矩陣為s1s2s3s1s2s3穩(wěn)態(tài)狀態(tài)概率分布：符號(hào)概率分布：解得：解：由圖可以寫(xiě)出其狀態(tài)轉(zhuǎn)移矩陣為1/0.10/0.91/0.50/0.51/0.20/0.8【例2.2.5】如圖所示三態(tài)馬爾可夫信源，寫(xiě)出其狀態(tài)轉(zhuǎn)移矩陣，畫(huà)出其狀態(tài)轉(zhuǎn)移圖，求出穩(wěn)態(tài)概率分布，并求其極限熵。狀態(tài)極限概率分布：解得條件熵因此或直接由公式計(jì)算問(wèn)題：冗余度產(chǎn)生的原因？最大信源熵熵的相對(duì)率（信息效率）的定義？

冗余度的定義？2.2.5冗余度一、冗余度產(chǎn)生的原因

冗余度（多余度、剩余度）：表示給定信源在實(shí)際發(fā)出消息時(shí)所包含的多余信息。

冗余度來(lái)自兩個(gè)方面:

一是信源符號(hào)間的相關(guān)性。由于信源輸出符號(hào)間的依賴關(guān)系使得信源熵減小，這就是信源的相關(guān)性。相關(guān)程度越大，信源的實(shí)際熵就越小，趨于極限熵H(X)；反之相關(guān)程度減小，信源實(shí)際熵就增大。通常希望信源熵盡量的大，即它對(duì)外提供的平均信息量越大越好。另一個(gè)方面是信源符號(hào)分布的不均勻性。當(dāng)?shù)雀怕史植紩r(shí)信源熵最大。而實(shí)際應(yīng)用中大多是不均勻分布，使得實(shí)際熵減小。當(dāng)信源輸出符號(hào)間彼此不存在依賴關(guān)系且為等概率分布時(shí)，信源實(shí)際熵趨于最大H0(X)。

前幾節(jié)我們討論了各類離散信源及其信息熵。實(shí)際的離散信源可能是非平穩(wěn)的，對(duì)于非平穩(wěn)信源來(lái)說(shuō)，其H∞不一定存在，但可以假定它是平穩(wěn)的，用平穩(wěn)信源的H∞來(lái)近似。然而，對(duì)于一般平穩(wěn)的離散信源，求H∞值也是極其困難的。那么，進(jìn)一步可以假設(shè)它是m階馬爾可夫信源，用m階馬爾可夫信源的平均信息熵Hm+1

來(lái)近似。如再進(jìn)一步簡(jiǎn)化信源，即可假設(shè)信源是無(wú)記憶信源，而信源符號(hào)有一定的概率分布。這時(shí)，可用信源的平均自信息量H1=H(X)來(lái)近似。二、最大信源熵由數(shù)據(jù)處理定理及離散熵的性質(zhì)有表明信源的記憶長(zhǎng)度越長(zhǎng)，熵就越小；即信源符號(hào)的相關(guān)性越強(qiáng)，所提供的平均信息量就越小。由此可見(jiàn)，由于信源符號(hào)間的依賴關(guān)系使信源的熵減小。它們的前后依賴關(guān)系越長(zhǎng)，信源的熵越小。當(dāng)信源符號(hào)間彼此無(wú)依賴、等概率分布時(shí)，信源的熵才達(dá)到最大log2n。也就是說(shuō)，信源符號(hào)之間依賴關(guān)系越強(qiáng)，每個(gè)符號(hào)提供的信息量就越小。

每個(gè)符號(hào)提供的平均自信息量隨著符號(hào)間的依賴關(guān)系長(zhǎng)度的增加而減少。對(duì)于一般平穩(wěn)信源來(lái)說(shuō)，極限熵為H∞，這就是說(shuō)，如果要傳送這一信源的信息，理論上來(lái)說(shuō)只需要有傳送H∞的手段即可。但實(shí)際上我們對(duì)它的概率分布不能完全掌握，如果把它近似成m階馬爾可夫信源，則可以用能傳送Hm

的手段去傳送具有H∞的信源，當(dāng)然這里面就不太經(jīng)濟(jì)。

引進(jìn)信源的冗余度（也叫剩余度或多余度）來(lái)衡量信源的相關(guān)性程度.四、冗余度（相對(duì)剩余）

一個(gè)信源實(shí)際的信息熵與具有同樣符號(hào)集的最大熵的比值稱為相對(duì)率，即其中H∞是信源的實(shí)際熵，三、熵的相對(duì)率（信息效率）是最大熵.表示不肯定的程度因?yàn)榭隙ㄐ圆缓行畔⒘?，因此是冗余的。表示肯定性的程度由冗余度的定義可見(jiàn)，信源的冗余度能夠很好地反映信源輸出的符號(hào)序列中符號(hào)之間依賴關(guān)系的強(qiáng)弱。冗余度ξ越大，表示信源的實(shí)際熵H∞

越小，表明信源符號(hào)之間的依賴關(guān)系越強(qiáng)，即符號(hào)之間的記憶長(zhǎng)度越長(zhǎng)；冗余度越小，表明信源符號(hào)之間的依賴關(guān)系越弱，即符號(hào)之間的記憶長(zhǎng)度越短。當(dāng)冗余度等于零時(shí)，信源的熵就等于極大熵H0，表明信源符號(hào)之間不但統(tǒng)計(jì)獨(dú)立無(wú)記憶，而且各符號(hào)還是等概分布。因此，冗余度可以用來(lái)衡量信源輸出的符號(hào)序列中各符號(hào)之間的依賴程度。正由于信源存在著冗余度，即存在著不必要傳送的信息，因此信源也就存在進(jìn)一步壓縮信息率的可能性。冗余度越大，壓縮潛力也就越大?？梢?jiàn)它是信源編碼，數(shù)據(jù)壓縮的前提與理論基礎(chǔ)。信息變差冗余度的公式表明：信源的符號(hào)數(shù)一定，符號(hào)間的記憶長(zhǎng)度越長(zhǎng)，極限熵就越小，差值就越大。稱為信息變差?？偨Y(jié)：通信的效率和可靠性問(wèn)