中南大學信息論與編碼課件Inf-T-C-33N

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

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

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

多符號離散信源可用隨機變量組成的時間序列，即隨機矢量：

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

在一般情況下，信源的概率分布與時間有關，不同時刻有不同的概率分布。即有

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

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

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

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

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

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

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

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

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

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

X:a1a2a3[X.P]:{

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

α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()的單位應是信源=X1×X2每發(fā)一條消息提供的平均信息量。因信源X的二次擴展信源=X1×X2每一條消息均有兩個信源符號組成，所以H()的單位是(比特/2信符)3.2離散平穩(wěn)無記憶信源的信息熵2013秋季信息1114InfTheory&Coding-張祖平3.3離散平穩(wěn)有記憶信源的信息熵

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

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

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

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

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

對于離散平穩(wěn)有記憶信源來說，因為有記憶，所以在不同時刻所發(fā)符號提供的平均信息量是不同的。那么，平均符號熵就稱為評估（特別當時）維離散平穩(wěn)有記憶信源，每發(fā)一個信源符號提供的平均信息量，也就是提供信息能力的一個衡量標準。3.3離散平穩(wěn)有記憶信源的信息熵2013秋季信息1120InfTheory&Coding-張祖平例3.2設離散平穩(wěn)有記憶信道X的信源空間為

X:a1a2a3

[X.P]:{

p(x):1/44/911/36二維離散平穩(wěn)有記憶信源X=X1×X2中前后兩個符號的關聯(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)計依賴關系，得條件熵

比特/消息即有

H(X2/X1)<H(X)條件熵H(X2/X1)比信源X的信息熵H(X)減少了0.672比特/信符，這正是由符號之間有依賴關系造成的結果。二維離散平穩(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比特/消息平均符號熵

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

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

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

進一步剖析平均符號熵的有關數(shù)學特性得：

1.

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

2.

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

3.

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

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

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

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

對于m階M信源來說，因為隨機變量序列X中的每一時刻的隨機變量均取自且取遍于離散平穩(wěn)有記憶信源X的符號集，所以時刻1到m的隨機變量序列的某一具體消息

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

從數(shù)學上來說，m個符號組成的狀態(tài)就構成了一個有限平穩(wěn)的馬爾柯夫鏈（簡寫為M鏈）。這就是把這種記憶長度為m的離散平穩(wěn)有記憶信源稱為m階M信源的原因。

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

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

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

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

按照狀態(tài)一步轉移的相應關系，把給定的個狀態(tài)一步轉移概率排成矩陣為：

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

m階M信源在某時刻T由狀態(tài)經過n個單位（經過n步），在（T+n）時刻轉移為另一狀態(tài)的條件概率稱為m階M信源的狀態(tài)n步轉移概率。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1:

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

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

3.7離散無記憶信道的數(shù)學模型2013秋季信息1156InfTheory&Coding-張祖平2:證無預感性經推導得:

這表明,次擴展離散無記憶信道在時刻的輸出隨機變量序列只與時刻的輸入隨機變量有關,與下一時刻的輸入隨機變量無關這就是離散無記憶信道的”無預感性”.

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

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

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

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

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

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

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

步驟二:個隨機變量單獨通過離散無記憶信道的平均交互信息量之和:3.8離散無記憶信道的信道容量2013秋季信息1164InfTheory&Coding-張祖平

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

步驟三:作差因為:3.8離散無記憶信道的信道容量2013秋季信息1166InfTheory&Coding-張祖平

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

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

綜述:離散無記憶信道的次擴展信道的總體平均交互信息量,一般不會超過信源中個隨機變量在單位時間內相繼單獨通過離散無記憶信道的平均交互信息量的總和,只有信源是維離散平穩(wěn)無記憶信源時,又因為平均交互信息量都等于離散無記憶信道傳遞離散無記憶信源的平均交互信息量,即3.8離散無記憶信道的信道容量2013秋季信息1169InfTheory&Coding-張祖平

可得:

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

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

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