信息論與編碼張祖平/ZhangZuping電子信息工程系SchoolofInformationScienceandEngineering,CentralSouthUniversity,zpzhang@InformationTheory&Coding第三章多符號(hào)離散信源與信道2013秋季信息111InfTheory&Coding-張祖平本章主要內(nèi)容

(MainContent)3.1離散平穩(wěn)信源的數(shù)學(xué)模型3.2離散平穩(wěn)無(wú)記憶信源的信息熵3.3離散平穩(wěn)有記憶信源的信息熵3.4離散平穩(wěn)有記憶信源的極限熵3.5馬爾柯夫信源的極限熵3.6信源的剩余度與結(jié)構(gòu)信息3.7離散無(wú)記憶信道的數(shù)學(xué)模型3.8離散無(wú)記憶信道的信道容量3.9獨(dú)立并列信道的信道容量2013秋季信息112InfTheory&Coding-張祖平多符號(hào)離散信源與信道

對(duì)于多符號(hào)離散信源來(lái)說(shuō)，若信道的輸入端輸入一個(gè)由多個(gè)信源符號(hào)組成的時(shí)間序列所代表的消息，在信道的輸出端相應(yīng)以一定概率輸出一個(gè)由同樣個(gè)數(shù)的符號(hào)組成的時(shí)間序列代表的消息，則這種信道稱為多符號(hào)離散信道。2013秋季信息113InfTheory&Coding-張祖平3.1離散平穩(wěn)信源的數(shù)學(xué)模型

多符號(hào)離散信源可用隨機(jī)變量組成的時(shí)間序列，即隨機(jī)矢量：

來(lái)表示。如果多符號(hào)離散信源發(fā)出的每一條消息中，每一單位時(shí)間出現(xiàn)的離散符號(hào)都是取自且取遍與信源符號(hào)集，即那么，多符號(hào)離散信源發(fā)出的每一條消息中，每一單位時(shí)間出現(xiàn)的離散符號(hào)，就是信源在這個(gè)單位時(shí)間發(fā)出的信源符號(hào)。這就是說(shuō)，多符號(hào)離散信源發(fā)出的消息，就是單符號(hào)離散信源每單位時(shí)間發(fā)出的離散信源符號(hào)組成的時(shí)間序列。表示多符號(hào)離散信源的隨機(jī)矢量，可看作是表示時(shí)刻的單符號(hào)離散信源的隨機(jī)變量的時(shí)間序列2013秋季信息114InfTheory&Coding-張祖平

在一般情況下，信源的概率分布與時(shí)間有關(guān)，不同時(shí)刻有不同的概率分布。即有

設(shè)為兩任意時(shí)刻，若信源的概率分布與時(shí)間無(wú)關(guān)，即有式（3.4）則我們把信源稱之為維離散平穩(wěn)信源。3.1離散平穩(wěn)信源的數(shù)學(xué)模型2013秋季信息115InfTheory&Coding-張祖平

由于維聯(lián)合概率的平穩(wěn)性，每一組的統(tǒng)計(jì)特性是完全相同的，可以由個(gè)隨機(jī)變量組成的一個(gè)組的統(tǒng)計(jì)特性來(lái)代表。由于任何時(shí)刻隨機(jī)變量發(fā)出的符號(hào)都取自且取遍同一個(gè)信源符號(hào)集，所以在無(wú)限長(zhǎng)的符號(hào)時(shí)間序列中，每個(gè)符號(hào)組成的無(wú)數(shù)個(gè)消息中的不同消息種數(shù)是種，而這種不同消息在長(zhǎng)度為的隨機(jī)變量序列中都可以出現(xiàn)。所以，一個(gè)維離散平穩(wěn)信源，就可由個(gè)隨機(jī)變量組成的隨機(jī)矢量

來(lái)表示。3.1離散平穩(wěn)信源的數(shù)學(xué)模型2013秋季信息116InfTheory&Coding-張祖平

把維離散平穩(wěn)信源稱之為信源 的次擴(kuò)展信源，其信源空間：其中：這就是描述維離散平穩(wěn)信源的一般的數(shù)學(xué)模型。3.1離散平穩(wěn)信源的數(shù)學(xué)模型2013秋季信息117InfTheory&Coding-張祖平3.2離散平穩(wěn)無(wú)記憶信源的信息熵

若維離散平穩(wěn)信源中，各時(shí)刻隨機(jī)變量之間相互統(tǒng)計(jì)獨(dú)立，則我們把信源稱為離散平穩(wěn)無(wú)記憶信源，把稱為維離散平穩(wěn)無(wú)記憶信源。由于維離散平穩(wěn)無(wú)記憶信源中，各時(shí)刻隨機(jī)變量之間統(tǒng)計(jì)獨(dú)立，即有2013秋季信息118InfTheory&Coding-張祖平

又由信源的平穩(wěn)性，有即得（式3.16)其中；這樣，維離散平穩(wěn)無(wú)記憶信源的信源空間可以改寫為其中：且

3.2離散平穩(wěn)無(wú)記憶信源的信息熵2013秋季信息119InfTheory&Coding-張祖平

因?yàn)榉謩e都是信源的概率空間中的概率分量。由，則有而這說(shuō)明，維離散平穩(wěn)無(wú)記憶信源可能發(fā)出的消息數(shù)，已由離散平穩(wěn)無(wú)記憶信源的種擴(kuò)展到種；維離散平穩(wěn)無(wú)記憶信源的概率分布完全可由離散平穩(wěn)無(wú)記憶信源的先驗(yàn)概率分布求得。由此，我們把維離散平穩(wěn)無(wú)記憶信源稱為離散平穩(wěn)無(wú)記憶信源的次擴(kuò)展信源，并記為3.2離散平穩(wěn)無(wú)記憶信源的信息熵2013秋季信息1110InfTheory&Coding-張祖平

由于的概率空間是一個(gè)完備集，則可得的信息熵這說(shuō)明，維離散平穩(wěn)無(wú)記憶信源的信息熵，等于各時(shí)刻隨機(jī)變量的信息熵之和。再考慮到中每一時(shí)刻的隨機(jī)變量的取值，這就是離散平穩(wěn)無(wú)記憶信源的在第時(shí)刻的取值，而的概率分布，就是離散平穩(wěn)無(wú)記憶信源在第時(shí)刻的概率分布。3.2離散平穩(wěn)無(wú)記憶信源的信息熵2013秋季信息1111InfTheory&Coding-張祖平

由（3.4）式所示的平穩(wěn)性，離散平穩(wěn)無(wú)記憶信源的概率分布不隨時(shí)間的推移而變化，時(shí)刻的隨機(jī)變量的概率分布就是離散平穩(wěn)無(wú)記憶信源的概率分布。所以，（3.16）式中時(shí)刻隨機(jī)變量的信息熵均等于離散平穩(wěn)無(wú)記憶信源的信息熵，即繼而，可得這說(shuō)明，離散平穩(wěn)無(wú)記憶信源的次擴(kuò)展信源，即維離散平穩(wěn)無(wú)記憶信源的信息熵，等于離散平穩(wěn)無(wú)記憶信源的信息熵的倍。這意味著，離散平穩(wěn)無(wú)記憶信源的次擴(kuò)展信源每發(fā)一條消息提供的平均信息量，等于離散無(wú)記憶信源每發(fā)一個(gè)符號(hào)提供的平均信息量的倍。3.2離散平穩(wěn)無(wú)記憶信源的信息熵2013秋季信息1112InfTheory&Coding-張祖平例3.1設(shè)離散平穩(wěn)無(wú)記憶信道X的信源空間為

X:a1a2a3[X.P]:{

p(x):???則信源X的二次擴(kuò)展信源=X1×X2的符號(hào)集為

α1=a1×a1

α4=a2×a1

α7=a3×a1

α2=a1×a2

α5=a2×a2

α8=a3×a2

α3=a1×a3

α6=a2×a3

α9=a3×a3信源=X1×X2的概率分布

p(α1)=p(a1a1)=p(a1)p(a1)=1/4×1/4=1/16p(α2)=p(a1a2)=p(a1)p(a2)=1/4×1/2=1/8p(α3)=p(a1a3)=p(a1)p(a3)=1/4×1/4=1/16p(α4)=p(a2a1)=p(a2)p(a1)=1/2×1/4=1/8p(α5)=p(a2a2)=p(a2)p(a2)=1/2×1/2=1/4p(α6)=p(a2a3)=p(a2)p(a3)=1/2×1/4=1/8p(α7)=p(a3a1)=p(a3)p(a1)=1/4×1/4=1/16p(α8)=p(a3a2)=p(a3)p(a2)=1/4×1/2=1/8p(α9)=p(a3a3)=p(a3)p(a3)=1/4×1/4=1/162013秋季信息1113InfTheory&Coding-張祖平這樣，可得=X1×X2的信源空間為

:a1a1a1a2a1a3a2a1a2a2a2a3a3a1a3a2a3a3[.P]:{p():1/161/81/161/81/41/81/161/81/16顯然，信源=X1×X2

的概率空間是完備集，其信息熵

H()=H(X1X2)=H(1/16,1/8,1/16,1/8,1/4,1/8,1/16,1/8,1/16)=3(比特/2信符)或

H()=2H(X)=2×H(1/4,1/2,1/4)=3(比特/2信符)這里要注意的是，H()的單位應(yīng)是信源=X1×X2每發(fā)一條消息提供的平均信息量。因信源X的二次擴(kuò)展信源=X1×X2每一條消息均有兩個(gè)信源符號(hào)組成，所以H()的單位是(比特/2信符)3.2離散平穩(wěn)無(wú)記憶信源的信息熵2013秋季信息1114InfTheory&Coding-張祖平3.3離散平穩(wěn)有記憶信源的信息熵

若離散平穩(wěn)信源在各時(shí)刻發(fā)出的符號(hào)之間并不是統(tǒng)計(jì)獨(dú)立的，是有統(tǒng)計(jì)聯(lián)系的。前一時(shí)刻發(fā)出的符號(hào)，依某種統(tǒng)計(jì)規(guī)律影響到后續(xù)時(shí)刻發(fā)出的符號(hào)的可能性。任一時(shí)刻發(fā)出的符號(hào)對(duì)這一時(shí)刻之前發(fā)出的符號(hào)是“有記憶”的。那么，信源稱為離散平穩(wěn)有記憶信源，由擴(kuò)展而成的多符號(hào)離散平穩(wěn)信源稱之為維離散平穩(wěn)有記憶信源。2013秋季信息1115InfTheory&Coding-張祖平

維離散平穩(wěn)有記憶信源的信源空間可表示為其消息集合是，而其中某一具體消息因?yàn)榫S離散平穩(wěn)有記憶信源的概率分布而個(gè)概率分量的和是3.3離散平穩(wěn)有記憶信源的信息熵2013秋季信息1116InfTheory&Coding-張祖平

因?yàn)榫S離散平穩(wěn)有記憶信源中，任一時(shí)刻的隨機(jī)變量只能取離散平穩(wěn)有記憶信源中的任一符號(hào)，不可能取符號(hào)集以外的任何別的符號(hào)，所以，（3.24）式中各維條件概率的和均為一，有繼而，得這表明，維離散平穩(wěn)有記憶信源的概率空間也是一個(gè)完備集。既然是一個(gè)完備集，那么維離散平穩(wěn)有記憶信源每發(fā)一條消息提供的平均信息量，就是維離散平穩(wěn)有記憶信源的信息熵。3.3離散平穩(wěn)有記憶信源的信息熵2013秋季信息1117InfTheory&Coding-張祖平

經(jīng)過(guò)推導(dǎo)，得到維離散平穩(wěn)有記憶信源的信息熵這表明，維離散平穩(wěn)信源有記憶信源的信息熵，等于離散平穩(wěn)有記憶信源起始時(shí)刻的信息熵，加上等各維條件熵之和。這就意味著，維離散平穩(wěn)有記憶信源每發(fā)一條消息提供的平均信息量，等于離散平穩(wěn)有記憶信源起始時(shí)刻每發(fā)一個(gè)符號(hào)提供的平均信息量，加上起始時(shí)刻所發(fā)符號(hào)已知的前提下，第三時(shí)刻每發(fā)一個(gè)符號(hào)提供的條件平均信息量，…，最后，再加上第，時(shí)刻所發(fā)符號(hào)已知的前提下，第時(shí)刻每發(fā)一符號(hào)提供的條件平均信息量所得之和。這個(gè)和值與起始時(shí)刻的選擇無(wú)關(guān)，不隨時(shí)間的推移而變化。3.3離散平穩(wěn)有記憶信源的信息熵2013秋季信息1118InfTheory&Coding-張祖平

根據(jù)離散平穩(wěn)有記憶信源條件概率的平穩(wěn)性，有可得這表明，離散平穩(wěn)有記憶信源的“有記憶”特性，使離散平穩(wěn)有記憶信源每發(fā)一個(gè)符號(hào)提供的平均信息量，隨著記憶長(zhǎng)度的增長(zhǎng)而減少。記憶長(zhǎng)度越長(zhǎng)，在某時(shí)刻發(fā)符號(hào)之前的關(guān)于這個(gè)符號(hào)的預(yù)備只是越多，這時(shí)刻發(fā)符號(hào)的平均不確定性越小，提供的平均信息量也就越小。3.3離散平穩(wěn)有記憶信源的信息熵2013秋季信息1119InfTheory&Coding-張祖平

對(duì)于離散平穩(wěn)有記憶信源來(lái)說(shuō)，因?yàn)橛杏洃?，所以在不同時(shí)刻所發(fā)符號(hào)提供的平均信息量是不同的。那么，平均符號(hào)熵就稱為評(píng)估（特別當(dāng)時(shí)）維離散平穩(wěn)有記憶信源，每發(fā)一個(gè)信源符號(hào)提供的平均信息量，也就是提供信息能力的一個(gè)衡量標(biāo)準(zhǔn)。3.3離散平穩(wěn)有記憶信源的信息熵2013秋季信息1120InfTheory&Coding-張祖平例3.2設(shè)離散平穩(wěn)有記憶信道X的信源空間為

X:a1a2a3

[X.P]:{

p(x):1/44/911/36二維離散平穩(wěn)有記憶信源X=X1×X2中前后兩個(gè)符號(hào)的關(guān)聯(lián)程度由下一組條件概率表示：

P(X2=a1/X1=a1)=P(a1/a1)=7/9P(X2=a2/X1=a1)=P(a2/a1)=2/9P(X2=a3/X1=a1)=P(a3/a1)=0P(X2=a1/X1=a2)=P(a1/a2)=1/8P(X2=a2/X1=a2)=P(a2/a2)=3/4P(X2=a3/X1=a2)=P(a3/a2)=1/8P(X2=a1/X1=a3)=P(a1/a3)=0P(X2=a2/X1=a3)=P(a2/a3)=2/11P(X2=a3/X1=a3)=P(a3/a3)=7/9離散平穩(wěn)有記憶信源X的信息熵

比特/信符2013秋季信息1121InfTheory&Coding-張祖平由二維離散平穩(wěn)有記憶信源X=X1×X2中X1和X2之間的統(tǒng)計(jì)依賴關(guān)系，得條件熵

比特/消息即有

H(X2/X1)<H(X)條件熵H(X2/X1)比信源X的信息熵H(X)減少了0.672比特/信符，這正是由符號(hào)之間有依賴關(guān)系造成的結(jié)果。二維離散平穩(wěn)有記憶信源X=X1X2每發(fā)一條消息提供的平均信息量

H(X)=H(X1X2)=H(X1)+H(X2/X1)=H(X)+H(X2/X1)=1.542+0.870=2.412比特/消息平均符號(hào)熵

H2(X)=H2(X1X2)=1/2×{H(X2/X1)}=1/2×2.412=1.205比特/消息即有

H2(X1X2)<H(X)這充分證實(shí)，離散平穩(wěn)有記憶信源X每發(fā)一個(gè)符號(hào)提供的平均信息量，小于離散平穩(wěn)有記憶信源X在起始時(shí)刻每發(fā)一個(gè)符號(hào)提供的平均信息量。這是由于符號(hào)之間存在統(tǒng)計(jì)依賴關(guān)系表現(xiàn)出來(lái)的有記憶特性，使離散平穩(wěn)有記憶信源X在起始時(shí)刻和第二時(shí)刻每發(fā)一個(gè)符號(hào)提供的平均信息量不同，且第二時(shí)刻每發(fā)一個(gè)符號(hào)提供的平均信息量，小于起始時(shí)刻每發(fā)一個(gè)符號(hào)提供的平均信息量所引起的。2013秋季信息1122InfTheory&Coding-張祖平3.4離散平穩(wěn)有記憶信源的極限熵

考慮到實(shí)際離散平穩(wěn)有記憶信源在時(shí)間域上連續(xù)不斷發(fā)出符號(hào)，符號(hào)之間的依賴關(guān)系延伸到無(wú)窮這個(gè)重要的實(shí)際因素，顯然應(yīng)該用（3.53-3.85）式的平均符號(hào)熵當(dāng)記憶長(zhǎng)度（即）足夠大時(shí)的極限值作為離散平穩(wěn)有記憶信源每發(fā)一個(gè)符號(hào)提供的平均信息量的測(cè)度函數(shù)，把它當(dāng)作為離散平穩(wěn)有記憶信源提供信息能力的衡量標(biāo)準(zhǔn)。我們把（3.54-3.85）式的極限值稱為離散平穩(wěn)有記憶信源的極限熵。2013秋季信息1123InfTheory&Coding-張祖平

進(jìn)一步剖析平均符號(hào)熵的有關(guān)數(shù)學(xué)特性得：

1.

這表明，維離散平穩(wěn)有記憶信源的平均符號(hào)熵，一定不小于維條件熵。而且由熵的非負(fù)性可直接導(dǎo)致平均符號(hào)熵的非負(fù)性，即3.4離散平穩(wěn)有記憶信源的極限熵2013秋季信息1124InfTheory&Coding-張祖平

2.

這表明，維離散平穩(wěn)有記憶信源的平均符號(hào)熵不僅具有非負(fù)性，而且它的最大值等于離散平穩(wěn)有記憶信源在起始時(shí)刻的信息熵，平均符號(hào)熵是記憶長(zhǎng)度的非遞增函數(shù)，隨記憶長(zhǎng)度的增長(zhǎng)而減小。這就說(shuō)明，當(dāng)記憶長(zhǎng)度足夠大時(shí)，維離散平穩(wěn)有記憶信源的平均符號(hào)熵的極限值，即極限熵是存在的。3.4離散平穩(wěn)有記憶信源的極限熵2013秋季信息1125InfTheory&Coding-張祖平

3.

這表明，對(duì)于記憶長(zhǎng)度足夠長(zhǎng)的離散平穩(wěn)有記憶信源，每發(fā)一個(gè)符號(hào)提供的平均信息量，即極限熵，等于條件熵在時(shí)的極限值。3.4離散平穩(wěn)有記憶信源的極限熵2013秋季信息1126InfTheory&Coding-張祖平3.5馬爾柯夫信源的極限熵

上一節(jié)講到了離散平穩(wěn)有記憶信源的極限熵，公式為：

要求解條件熵在時(shí)的極限值，就相當(dāng)于要測(cè)定離散平穩(wěn)有記憶信源的無(wú)窮多維的條件概率和聯(lián)合概率分布，把信源當(dāng)作無(wú)限記憶長(zhǎng)度的信源來(lái)處理。這在實(shí)際計(jì)算中是比較困難的，所以下面介紹一種比較特殊的離散平穩(wěn)有記憶信源——馬爾柯夫信源，即不須測(cè)定無(wú)窮多維條件概率和聯(lián)合概率，就可求得條件熵的極限值。2013秋季信息1127InfTheory&Coding-張祖平

馬爾柯夫信源的定義：如果隨機(jī)變量序列X中的任一時(shí)刻（m+1）的隨機(jī)變量只依賴于它前面已經(jīng)發(fā)生的m個(gè)隨機(jī)變量與更前面的隨機(jī)變量無(wú)關(guān)，則稱這種信源為m階馬爾柯夫信源（簡(jiǎn)寫為m階M信源）。3.5馬爾柯夫信源的極限熵2013秋季信息1128InfTheory&Coding-張祖平

對(duì)于m階M信源來(lái)說(shuō)，因?yàn)殡S機(jī)變量序列X中的每一時(shí)刻的隨機(jī)變量均取自且取遍于離散平穩(wěn)有記憶信源X的符號(hào)集，所以時(shí)刻1到m的隨機(jī)變量序列的某一具體消息

把看作為某一狀態(tài)。同樣，把時(shí)刻2到（m+1）的m個(gè)隨機(jī)變量的某一具體消息看作為另一狀態(tài)。3.5馬爾柯夫信源的極限熵2013秋季信息1129InfTheory&Coding-張祖平

從數(shù)學(xué)上來(lái)說(shuō)，m個(gè)符號(hào)組成的狀態(tài)就構(gòu)成了一個(gè)有限平穩(wěn)的馬爾柯夫鏈（簡(jiǎn)寫為M鏈）。這就是把這種記憶長(zhǎng)度為m的離散平穩(wěn)有記憶信源稱為m階M信源的原因。

從狀態(tài)發(fā)符號(hào)后，這m個(gè)符號(hào)組成狀態(tài)即從狀態(tài)轉(zhuǎn)移到狀態(tài)。狀態(tài)只依賴于狀態(tài)。3.5馬爾柯夫信源的極限熵2013秋季信息1130InfTheory&Coding-張祖平

采用狀態(tài)隨機(jī)變量和來(lái)表示信源的極限熵，表示式如下：

m階M信源的極限熵取決于個(gè)狀態(tài)概率以及個(gè)狀態(tài)一步轉(zhuǎn)移概率m階M信源具有獨(dú)特的Markov性（無(wú)后放性），即“每發(fā)一個(gè)符號(hào)，只與前面已發(fā)的m個(gè)符號(hào)有關(guān)，與更前面的符號(hào)無(wú)關(guān)?！币虼耍x散平穩(wěn)有記憶信源極限熵的計(jì)算有無(wú)限問(wèn)題轉(zhuǎn)為了有限問(wèn)題。3.5馬爾柯夫信源的極限熵2013秋季信息1131InfTheory&Coding-張祖平

要完整描述一個(gè)m階M信源，首先要給定離散平穩(wěn)有記憶信源X的符號(hào)集，同時(shí)要確定M信源的階數(shù)，即有記憶信源X的記憶長(zhǎng)度m。一般m是大于零的正整數(shù)。其次，要給定（或測(cè)定）個(gè)由任一消息（狀態(tài)）到下一時(shí)刻的另一消息（狀態(tài)）的消息（狀態(tài)）一步轉(zhuǎn)移概率，并且滿足一下關(guān)系：3.5馬爾柯夫信源的極限熵2013秋季信息1132InfTheory&Coding-張祖平

按照狀態(tài)一步轉(zhuǎn)移的相應(yīng)關(guān)系，把給定的個(gè)狀態(tài)一步轉(zhuǎn)移概率排成矩陣為：

矩陣[P]稱為m階M信源的狀態(tài)一步轉(zhuǎn)移矩陣，且其中的每一元素處于[0，1]，矩陣[P]中每行元素之和均等于1。3.5馬爾柯夫信源的極限熵2013秋季信息1133InfTheory&Coding-張祖平

m階M信源在某時(shí)刻T由狀態(tài)經(jīng)過(guò)n個(gè)單位（經(jīng)過(guò)n步），在（T+n）時(shí)刻轉(zhuǎn)移為另一狀態(tài)的條件概率稱為m階M信源的狀態(tài)n步轉(zhuǎn)移概率。

應(yīng)用Markov特性和全概率公式，考慮到m階平穩(wěn)M信源的平穩(wěn)性，其實(shí)時(shí)刻T是任意的，可以得到，由m階M信源n步狀態(tài)轉(zhuǎn)移概率組成的狀態(tài)n步轉(zhuǎn)移矩陣[P(n)],等于狀態(tài)一步轉(zhuǎn)移矩陣[P]的n次連乘，即3.5馬爾柯夫信源的極限熵2013秋季信息1134InfTheory&Coding-張祖平

上式是當(dāng)時(shí)的極限值，所以其中的狀態(tài)概率應(yīng)是m階M信源達(dá)到穩(wěn)定時(shí)出現(xiàn)狀態(tài)的概率，我們把這種狀態(tài)概率稱為狀態(tài)極限概率。不是任何m階M信源都存在狀態(tài)極限概率，只有滿足一定條件的m階M信源，才存在狀態(tài)極限概率。3.5馬爾柯夫信源的極限熵2013秋季信息1135InfTheory&Coding-張祖平

若對(duì)于有限平穩(wěn)的m階M信源，由的m個(gè)符號(hào)組成的消息（狀態(tài)）和，存在一個(gè)正整數(shù)，且經(jīng)過(guò)步，從狀態(tài)轉(zhuǎn)移到的步轉(zhuǎn)移概率則這種m階M信源具有各態(tài)歷經(jīng)性。3.5馬爾柯夫信源的極限熵2013秋季信息1136InfTheory&Coding-張祖平

各態(tài)歷經(jīng)定理：對(duì)各態(tài)歷經(jīng)的m階M信源來(lái)說(shuō)，對(duì)每個(gè)都存在不依賴于起始狀態(tài)的狀態(tài)極限概率而且，狀態(tài)極限概率是在約束條件的約束下，方程組的唯一解。3.5馬爾柯夫信源的極限熵2013秋季信息1137InfTheory&Coding-張祖平各態(tài)歷經(jīng)定理的證明，過(guò)程從略。

從這個(gè)證明過(guò)程可以看出：m階M信源具有各態(tài)歷經(jīng)性的關(guān)鍵之所在，是存在一個(gè)正整數(shù)，有。這就是說(shuō)，只有在轉(zhuǎn)移一定步數(shù)后各狀態(tài)之間均可相通的條件下，當(dāng)轉(zhuǎn)移步數(shù)足夠大，m階M信源達(dá)到穩(wěn)定的情況下，各狀態(tài)出現(xiàn)的概率才能穩(wěn)定在某一極限值，存在狀態(tài)極限概率。所謂“各態(tài)歷經(jīng)”，其含義之一，就是各態(tài)相通，均可經(jīng)歷；其含義之二，就是由各態(tài)歷經(jīng)過(guò)程產(chǎn)生的每個(gè)序列，都有同樣的統(tǒng)計(jì)特性，具有統(tǒng)計(jì)均勻性。3.5馬爾柯夫信源的極限熵2013秋季信息1138InfTheory&Coding-張祖平

對(duì)于m階M信源，狀態(tài)一步轉(zhuǎn)移概率可由狀態(tài)一步轉(zhuǎn)移矩陣[P]表示，也可用狀態(tài)一步轉(zhuǎn)移線圖來(lái)表示（如圖3.7所示）。

由該信源相應(yīng)的狀態(tài)一步轉(zhuǎn)移線圖具有以下兩個(gè)特點(diǎn)：不可約性：狀態(tài)空間中的任意兩個(gè)狀態(tài)都存在至少一個(gè)正整數(shù)，使。從一個(gè)狀態(tài)開(kāi)始，總有可能轉(zhuǎn)移到另一個(gè)狀態(tài)，狀態(tài)空間中各狀態(tài)之間相互都能到達(dá)。那么，狀態(tài)空間組成的集合成為不可約閉集?！安豢杉s”的含義就是在集合S中，不存在一個(gè)各狀態(tài)之間都能相互到達(dá)，而由于集合以外的狀態(tài)不相通的集合，即閉集中不能再分出閉集。3.5馬爾柯夫信源的極限熵2013秋季信息1139InfTheory&Coding-張祖平非周期性：如狀態(tài)空間S是一個(gè)不可約閉集，且從每一個(gè)狀態(tài)出發(fā)，經(jīng)過(guò)n步轉(zhuǎn)移回到本狀態(tài)的所有可能的步數(shù)中，即使的所有n中，不存在大于1的公因子，則稱不可約閉集S具有非周期性。3.5馬爾柯夫信源的極限熵2013秋季信息1140InfTheory&Coding-張祖平

判斷m階M信源是否具有各態(tài)歷經(jīng)性，有兩種方法：其一，步狀態(tài)轉(zhuǎn)移矩陣中，不存在“0”元素，則可判斷具有各態(tài)歷經(jīng)性；如n0為任意正整的中，都存在“0”元素，則判斷不具有各態(tài)歷經(jīng)性。其二，狀態(tài)一步轉(zhuǎn)移線圖中的狀態(tài)集合是不可約非周期閉集，則判斷為具有各態(tài)歷經(jīng)性；狀態(tài)轉(zhuǎn)移線圖中的狀態(tài)集合不是不可約非周期閉集，則判斷為不具各態(tài)歷經(jīng)性。3.5馬爾柯夫信源的極限熵2013秋季信息1141InfTheory&Coding-張祖平

最后強(qiáng)調(diào)，我們?cè)谟懻揘維離散平穩(wěn)有記憶信源時(shí)，是把時(shí)間域上有統(tǒng)計(jì)聯(lián)系的無(wú)窮序列，看作是每N各符號(hào)組成的組（消息）的序列，而且組（消息）與組（消息）之間看作統(tǒng)計(jì)獨(dú)立、互不相關(guān)，只在有N個(gè)符號(hào)組成的每一組（消息）內(nèi)，考慮符號(hào)之間的統(tǒng)計(jì)依賴關(guān)系。無(wú)限問(wèn)題→有限問(wèn)題在討論極限熵時(shí)，考慮了符號(hào)之間的依賴關(guān)系延伸到無(wú)窮這一因素，信號(hào)的平均信息量采用N→∞時(shí)平均符號(hào)熵的極限值。由于各態(tài)歷經(jīng)的m階M信源的記憶長(zhǎng)度m是有限值，再加上它具有獨(dú)特的Markov特性，所以各態(tài)歷經(jīng)的m階M信源的極限熵可求。3.5馬爾柯夫信源的極限熵2013秋季信息1142InfTheory&Coding-張祖平3.6信源的剩余度與結(jié)構(gòu)信息

各態(tài)歷經(jīng)的m階M信源的極限熵為這表明，m階M信源的極限熵就是離散平穩(wěn)有記憶信源X的m維條件熵。因?yàn)?，，這表明，信源的記憶長(zhǎng)度越大，信源的極限熵就越小。信源每發(fā)一個(gè)符號(hào)提供的平均信息量隨記憶長(zhǎng)度的增加而減小。只有當(dāng)信源發(fā)出符號(hào)之間相互統(tǒng)計(jì)獨(dú)立，不存在統(tǒng)計(jì)依賴關(guān)系，并等概分布時(shí)，信源信息熵才達(dá)到最大值，每發(fā)一個(gè)符號(hào)提供最大的平均信息量。即信源符號(hào)組成的時(shí)間序列中，符號(hào)之間的依賴關(guān)系越強(qiáng)，信源每發(fā)一個(gè)符號(hào)提供的平均信息量就越小。2013秋季信息1143InfTheory&Coding-張祖平

為了衡量信源符號(hào)間的依賴程度，我們把離散平穩(wěn)有記憶信源的極限熵，與把這個(gè)信源當(dāng)作離散無(wú)記憶等概信源達(dá)到的最大熵值的比值，定義為這個(gè)離散平穩(wěn)有記憶信源的相對(duì)熵率

而把1減去相對(duì)熵率所得之差定義為離散平穩(wěn)有記憶信源的剩余度3.6信源的剩余度與結(jié)構(gòu)信息2013秋季信息1144InfTheory&Coding-張祖平則離散平穩(wěn)有記憶信源X的剩余度為

由公式可見(jiàn)，對(duì)于符號(hào)數(shù)固定為r的離散平穩(wěn)有記憶信源X來(lái)說(shuō)，剩余度ξ越大，表示極限熵越小，信源符號(hào)間的記憶長(zhǎng)度越小，符號(hào)間的依賴程度越大。反之，剩余度ξ越小，表示極限熵越大，信源符號(hào)間的記憶長(zhǎng)度越小，符號(hào)間的依賴程度越小。所以，剩余度ξ是衡量離散平穩(wěn)有記憶信源符號(hào)間依賴程度的大小的尺度。3.6信源的剩余度與結(jié)構(gòu)信息2013秋季信息1145InfTheory&Coding-張祖平信息變差：信源的最大熵值，與實(shí)際的極限熵之間的差值稱為信息變差，也可稱為結(jié)構(gòu)信息。結(jié)構(gòu)信息是語(yǔ)言本身固有的習(xí)慣結(jié)構(gòu)決定的，是不須傳遞或存儲(chǔ)的。要傳遞或存儲(chǔ)的只是寫文章的人（信源）自己選擇符號(hào)表達(dá)自己意思的那一部分信息。這一部分信息就是極限熵。所以從理論上講，由語(yǔ)法結(jié)構(gòu)規(guī)定不得不用的符號(hào)，應(yīng)該有可能被大幅度壓縮。信源的剩余度ξ表示信源可壓縮的程度。

3.6信源的剩余度與結(jié)構(gòu)信息2013秋季信息1146InfTheory&Coding-張祖平剩余度的意義：剩余度是信息論中的一個(gè)具有核心意義的重要概念。從提高信息傳輸有效性的觀點(diǎn)出發(fā)，應(yīng)該減少或去掉信源的剩余度。從提高通信的可靠性角度來(lái)看，應(yīng)該增加或保留必要的、有用的剩余度，剩余度大的消息具有較強(qiáng)的抗干擾能力。信源編碼就是討論如何減小或消除信源的剩余度，提高通信的有效性；信道編碼就是討論如何增加信源有用的剩余度，提高通信的可靠性。3.6信源的剩余度與結(jié)構(gòu)信息2013秋季信息1147InfTheory&Coding-張祖平3.7離散無(wú)記憶信道的數(shù)學(xué)模型

離散無(wú)記憶信道↑多符號(hào)離散信道↑信道2013秋季信息1148InfTheory&Coding-張祖平設(shè)單符號(hào)離散信道的輸入符集x:{},輸出符號(hào)集Ｙ：｛｝傳遞概率：又設(shè)多符號(hào)離散平穩(wěn)信源每一時(shí)刻的隨機(jī)變量均取自且取遍于信道的輸入符號(hào)集則信源共有種不同的消息．而相對(duì)于在信道的輸出端，有一個(gè)Ｎ維的隨機(jī)變量序列與之相對(duì)應(yīng)，輸出隨機(jī)矢量共有種不同的消息.在信道傳輸時(shí)：在任意Ｎ時(shí)刻，在發(fā)送隨機(jī)變量的某個(gè)符號(hào)的時(shí)，在輸出端都有隨機(jī)變量中的某一個(gè)符號(hào)與之相對(duì)應(yīng)．3.7離散無(wú)記憶信道的數(shù)學(xué)模型2013秋季信息1149InfTheory&Coding-張祖平

這種信道的輸入消息和輸出消息都是多個(gè)符號(hào)組成的，所以我們稱這種信道為多符號(hào)離散信道．同時(shí)，我們也可把這種信道稱之為單符號(hào)離散信道的Ｎ次擴(kuò)展信道．顯然，與單符號(hào)離散信道相比，Ｎ次擴(kuò)展信道的輸入符號(hào)數(shù)由種擴(kuò)展為種；輸出符號(hào)數(shù)由種擴(kuò)展為種．3.7離散無(wú)記憶信道的數(shù)學(xué)模型2013秋季信息1150InfTheory&Coding-張祖平信道的條件概率為信道的傳遞概率為同樣可以把這個(gè)傳遞概率,按輸入輸出的對(duì)應(yīng)關(guān)系,構(gòu)成次擴(kuò)展信道的傳遞矩陣:3.7離散無(wú)記憶信道的數(shù)學(xué)模型2013秋季信息1151InfTheory&Coding-張祖平傳遞概率的兩個(gè)性質(zhì):

1:

2:3.7離散無(wú)記憶信道的數(shù)學(xué)模型2013秋季信息1152InfTheory&Coding-張祖平離散無(wú)記憶信道的定義:若次擴(kuò)展信道的傳遞概率等于個(gè)時(shí)刻單符號(hào)離散信道的傳遞概率的連乘:即3.7離散無(wú)記憶信道的數(shù)學(xué)模型2013秋季信息1153InfTheory&Coding-張祖平則單符號(hào)離散信道成為離散無(wú)記憶信道,相應(yīng)的次擴(kuò)展信道成為離散無(wú)記憶信道的次擴(kuò)展信道.

所以離散無(wú)記憶信道的次擴(kuò)展信道的傳遞概率可由單符號(hào)離散無(wú)記憶信道的傳遞概率直接求得.3.7離散無(wú)記憶信道的數(shù)學(xué)模型2013秋季信息1154InfTheory&Coding-張祖平多符號(hào)離散信道的兩個(gè)新問(wèn)題:1:某時(shí)刻的輸出隨機(jī)變量,在時(shí)刻之前的輸入隨機(jī)變量序列,以及時(shí)刻之前的輸出隨機(jī)變量序列應(yīng)存在一定程度的統(tǒng)計(jì)聯(lián)系.(記憶性)2:時(shí)刻之前的輸出隨機(jī)變量序列與下一時(shí)刻的輸入隨機(jī)變量也存在某種程度的統(tǒng)計(jì)聯(lián)系.(預(yù)感性)3.7離散無(wú)記憶信道的數(shù)學(xué)模型2013秋季信息1155InfTheory&Coding-張祖平離散無(wú)記憶信道無(wú)記憶,無(wú)預(yù)感先證充分性:1:證無(wú)記憶性證無(wú)記憶性需要考察離散無(wú)記憶信道的條件概率,經(jīng)過(guò)公式推導(dǎo)得:這表明,次擴(kuò)展離散無(wú)記憶信道在時(shí)刻的輸出隨機(jī)變量,只與該時(shí)刻的輸入隨機(jī)變量有關(guān),與時(shí)刻之前的輸入變量序列和輸出變量序列無(wú)關(guān).這就是離散無(wú)記憶信道的”無(wú)記憶性”.

3.7離散無(wú)記憶信道的數(shù)學(xué)模型2013秋季信息1156InfTheory&Coding-張祖平2:證無(wú)預(yù)感性經(jīng)推導(dǎo)得:

這表明,次擴(kuò)展離散無(wú)記憶信道在時(shí)刻的輸出隨機(jī)變量序列只與時(shí)刻的輸入隨機(jī)變量有關(guān),與下一時(shí)刻的輸入隨機(jī)變量無(wú)關(guān)這就是離散無(wú)記憶信道的”無(wú)預(yù)感性”.

3.7離散無(wú)記憶信道的數(shù)學(xué)模型2013秋季信息1157InfTheory&Coding-張祖平再證必要性:無(wú)記憶性:無(wú)預(yù)感性:

3.7離散無(wú)記憶信道的數(shù)學(xué)模型2013秋季信息1158InfTheory&Coding-張祖平

所以,滿足無(wú)記憶性和無(wú)預(yù)感性條件的必是離散無(wú)記憶信道.3.7離散無(wú)記憶信道的數(shù)學(xué)模型2013秋季信息1159InfTheory&Coding-張祖平3.8離散無(wú)記憶信道的信道容量

分析思路:由于我們對(duì)于單符號(hào)信道已經(jīng)有了一定的研究基礎(chǔ),而且多符號(hào)信道也可看成是信源在同一信道中經(jīng)一定的時(shí)間間隔不斷發(fā)送符號(hào).所以,我們希望找出離散無(wú)記憶的次擴(kuò)展信道的平均交互信息量與各個(gè)時(shí)刻輸入變量單獨(dú)經(jīng)過(guò)信道后的平均信息量之和之間的關(guān)系.2013秋季信息1160InfTheory&Coding-張祖平

首先，重申傳遞概率為的多符號(hào)離散信道相聯(lián)系的輸入隨機(jī)矢量與輸出隨機(jī)矢量之間存在的統(tǒng)計(jì)依賴關(guān)系。（1）輸入某消息，輸出某消息的聯(lián)合概率。3.8離散無(wú)記憶信道的信道容量2013秋季信息1161InfTheory&Coding-張祖平（2）輸出某消息的概率。（3）收到的前提下，推測(cè)輸入的后驗(yàn)概率。

3.8離散無(wú)記憶信道的信道容量2013秋季信息1162InfTheory&Coding-張祖平

步驟一:求出輸入隨機(jī)矢量與輸出隨機(jī)矢量之間的平均交互信息量3.8離散無(wú)記憶信道的信道容量2013秋季信息1163InfTheory&Coding-張祖平

步驟二:個(gè)隨機(jī)變量單獨(dú)通過(guò)離散無(wú)記憶信道的平均交互信息量之和:3.8離散無(wú)記憶信道的信道容量2013秋季信息1164InfTheory&Coding-張祖平

3.8離散無(wú)記憶信道的信道容量2013秋季信息1165InfTheory&Coding-張祖平

步驟三:作差因?yàn)?3.8離散無(wú)記憶信道的信道容量2013秋季信息1166InfTheory&Coding-張祖平

3.8離散無(wú)記憶信道的信道容量即2013秋季信息1167InfTheory&Coding-張祖平

當(dāng)且僅當(dāng)信源是維離散平穩(wěn)無(wú)記憶信源時(shí),即才有即輸出隨機(jī)矢量中各時(shí)刻的隨機(jī)變量之間統(tǒng)計(jì)獨(dú)立,即3.8離散無(wú)記憶信道的信道容量2013秋季信息1168InfTheory&Coding-張祖平

綜述:離散無(wú)記憶信道的次擴(kuò)展信道的總體平均交互信息量,一般不會(huì)超過(guò)信源中個(gè)隨機(jī)變量在單位時(shí)間內(nèi)相繼單獨(dú)通過(guò)離散無(wú)記憶信道的平均交互信息量的總和,只有信源是維離散平穩(wěn)無(wú)記憶信源時(shí),又因?yàn)槠骄换バ畔⒘慷嫉扔陔x散無(wú)記憶信道傳遞離散無(wú)記憶信源的平均交互信息量,即3.8離散無(wú)記憶信道的信道容量2013秋季信息1169InfTheory&Coding-張祖平

可得:

所以,離散無(wú)記憶信道的次擴(kuò)展信道的總體平均交互信息量一定不會(huì)超過(guò)離散無(wú)記憶信道傳遞離散無(wú)記憶信源的平均交互信息量的倍.即3.8離散無(wú)記憶信道的信道容量2013秋季信息1170InfTheory&Coding-張祖平

當(dāng)離散平穩(wěn)無(wú)記憶信源是當(dāng)離散無(wú)記憶信道的匹配信源時(shí),離散無(wú)記憶信道的平均交互信息量達(dá)到最大時(shí),即信道容量C時(shí):令表示離散無(wú)記憶信道的N次擴(kuò)展信道的信道容量,則有3.8離散無(wú)記憶信道的信道容量2013秋季信息1171InfTheory&Coding-張祖平

綜上所述,離散無(wú)記憶信道的次擴(kuò)展信道的總體平均交互信息量,一般不會(huì)超過(guò)維離散平穩(wěn)信源在各個(gè)時(shí)刻隨機(jī)變量在每單位時(shí)間相繼單獨(dú)通過(guò)離散無(wú)記憶信道的平均交互信息量的總和