第4章 信道容量.ppt

1、第三章主要內(nèi)容： 1、變長編碼定理 (Shannon第一定理) 2、三種編碼方法,變長編碼定理 (Shannon第一定理),Shannon第一定理的物理意義在于：對(duì)信源進(jìn)行編碼，使編碼后的碼集中各碼字盡可能等概分布，如果將這碼集看成為一個(gè)新的信源，這時(shí)新信源所含信息量最大。,3,能獲得最佳碼的編碼方法主要有： 香農(nóng)（Shannon）編碼 費(fèi)諾（Fano）編碼 哈夫曼（Huffman）編碼等,4,香農(nóng)（Shannon）編碼 1. 將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列 2. 確定滿足下列不等式的整數(shù)碼長Ki。,5,為了編成唯一可譯碼，計(jì)算第i個(gè)消息的累加概率 將累加概率Pi變換成二進(jìn)制數(shù)。 取

2、Pi二進(jìn)數(shù)的小數(shù)點(diǎn)后Ki位即為該消息符號(hào)的二進(jìn)制碼字。,6,費(fèi)諾編碼方法 費(fèi)諾編碼屬于概率匹配編碼 (1)將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列： (2)將依次排列的信源符號(hào)按概率值分為兩大組，使兩個(gè)組的概率之和近于相同，并對(duì)各組賦予一個(gè)二進(jìn)制碼元“0”和“1”。,7,(3)將每一大組的信源符號(hào)進(jìn)一步再分成兩組，使劃分后的兩個(gè)組的概率之和近于相同，并又賦予兩個(gè)組一個(gè)二進(jìn)制符號(hào)“0”和“1”。 (4)如此重復(fù)，直至每個(gè)組只剩下一個(gè)信源符號(hào)為止。 (5)信源符號(hào)所對(duì)應(yīng)的碼字即為費(fèi)諾碼。,8,哈夫曼編碼方法 (1)將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列， (2)取兩個(gè)概率最小的字母分別配以0和1

3、兩個(gè)碼元，并將這兩個(gè)概率相加作為一個(gè)新字母的概率，與未分配的二進(jìn)符號(hào)的字母重新排隊(duì)。,9,(3)對(duì)重排后的兩個(gè)概率最小符號(hào)重復(fù)步驟(2)的過程。 (4)不斷繼續(xù)上述過程，直到最后兩個(gè)符號(hào)配以0和1為止。 (5)從最后一級(jí)開始，向前返回得到各個(gè)信源符號(hào)所對(duì)應(yīng)的碼元序列，即相應(yīng)的碼字。,例子,X的霍夫曼編碼,香農(nóng)編碼,費(fèi)諾編碼：,第4章 離散信道的信道容量,The eighth week,第4章 離散信道的信道容量,內(nèi)容提要 信道對(duì)于信息率的容納并不是無限制的，它不僅與物理信道本身的特性有關(guān)，還與信道輸入信號(hào)的統(tǒng)計(jì)特性有關(guān)，它有一個(gè)極限值，即信道容量，信道容量是有關(guān)信道的一個(gè)很重要的物理量。這一章

4、研究信道，研究在信道中傳輸?shù)拿總€(gè)符號(hào)所攜帶的信息量，并定義信道容量。,第一節(jié) 信道的數(shù)學(xué)模型及分類,1、信道的分類：,根據(jù)信道用戶的多少，可分為：,（1）單用戶信道：只有一個(gè)輸入端和一個(gè)輸出端,（2）多用戶信道：至少有一端有兩個(gè)以上的用戶，雙向通信,根據(jù)輸入端和輸出端的關(guān)聯(lián)：,（1）無反饋信道：信道輸出端無信號(hào)反饋到輸入端，即輸出端信號(hào)對(duì)輸入端信號(hào)無影響、無作用。,（2）有反饋信道：信道輸出端的信號(hào)反饋到輸入端，對(duì)輸入端的信號(hào)起作用，影響輸入端信號(hào)發(fā)生變化。,第一節(jié) 信道的數(shù)學(xué)模型及分類,根據(jù)信道參數(shù)與時(shí)間的關(guān)系：,（1）固定參數(shù)信道,（2）時(shí)變參數(shù)信道,根據(jù)輸入輸出信號(hào)的特點(diǎn) （1）離散信道

5、：信道的輸入和輸出都是時(shí)間上離散、取值 離散的隨機(jī)序列。離散信道有時(shí)也稱為數(shù)字信道。 （2）連續(xù)信道：信道的輸入和輸出都是時(shí)間上離散、 取值連續(xù)的隨機(jī)序列，又稱為模擬信道。 （3）半離散半連續(xù)信道：輸入序列和輸出序列一個(gè)是離散的，而另一個(gè)是連續(xù)的。 （4）波形信道：信道的輸入和輸出都是時(shí)間上連續(xù)， 并且取值也連續(xù)的隨機(jī)信號(hào)。,以下我們只研究無反饋、固定參數(shù)的單用戶離散信道。,第一節(jié) 信道的數(shù)學(xué)模型及分類,P(y/X),X,Y,根據(jù)這一模型，可對(duì)信道分類如下：,設(shè)離散信道的輸入為一個(gè)隨機(jī)變量X，相應(yīng)的輸出的隨機(jī)變量為Y，如圖所示： 規(guī)定一個(gè)離散信道應(yīng)有三個(gè)參數(shù)： 輸入符號(hào)集：X=x1，x2， 輸

6、出符號(hào)集：Y=y1，y2， 信道轉(zhuǎn)移概率：P(Y/X)=p(y1/x1),p(y2/x1),p( /x1),p(y1/ )p( / ),2、離散信道的數(shù)學(xué)模型,第一節(jié) 信道的數(shù)學(xué)模型及分類,（1）無干擾信道：輸入信號(hào)與輸出信號(hào) 有一一對(duì)應(yīng)關(guān)系,（2）有干擾無記憶信道：輸入與輸出無一一對(duì)應(yīng)關(guān)系，輸出只與當(dāng)前輸入有關(guān)； （3）有干擾有記憶信道：這是最一般的信道。,第一節(jié) 信道的數(shù)學(xué)模型及分類,3、單符號(hào)離散信道的數(shù)學(xué)模型 單符號(hào)離散信道的輸入變量為X，取值于 輸出變量為Y，取值于 。 并有條件概率 條件概率被稱為信道的傳遞概率或轉(zhuǎn)移概率。 一般簡(jiǎn)單的單符號(hào)離散信道的數(shù)學(xué)模型可以用概率空間X,p(y

7、|x),Y來描述。 X Y,第一節(jié) 信道的數(shù)學(xué)模型及分類,表示成矩陣形式：,信道矩陣中每一行之和為1,1.二元對(duì)稱信道(Binary Symmetric Channel，簡(jiǎn)記為BSC) 這是一種很重要的信道，它的輸入符號(hào)x 0 , 1，輸出符號(hào)y 0 , 1，轉(zhuǎn)移概率p (yx )如圖3-3所示信道特性可表示為信道矩陣 ， 其中p稱作信道錯(cuò)誤概率。,下面列舉幾種常見的離散無記憶信道：,圖3-3 二進(jìn)制對(duì)稱信道,圖3-4 無干擾信道,2. 無干擾信道 這是一種最理想的信道，也稱作無噪信道，信道的輸入和輸出符號(hào)間有確定的一一對(duì)應(yīng)關(guān)系， p (yx ) = 如圖3-4三元無干擾信道中，x , y 0

8、 , 1 , 2 ，對(duì)應(yīng)信道矩陣是 單位矩陣,3. 二元?jiǎng)h除信道,對(duì)于接收符號(hào)不能作出肯定或否定判決時(shí)，引入刪除符號(hào)，表示對(duì)該符號(hào)存有疑問，作為有誤或等待得到更多信息時(shí)再作判決。 二元?jiǎng)h除信道如圖3-5所示，輸入符號(hào)x 0 , 1，輸出符號(hào)y 0 , e , 1，轉(zhuǎn)移概率矩陣為,4.二元Z信道,二元Z信道如圖3-6所示，信道輸入符號(hào)x 0 , 1，輸出符號(hào)y 0 , 1轉(zhuǎn)移概率矩陣為,e,圖3-5 二元?jiǎng)h除信道,圖3-6 二元Z信道,由此可見，一般單符號(hào)離散信道的傳遞概率可以用矩陣表示,第一節(jié) 信道的數(shù)學(xué)模型及分類,第一節(jié) 信道的數(shù)學(xué)模型及分類,為了表述簡(jiǎn)便，可以寫成,下面推導(dǎo)幾個(gè)關(guān)系式：,第

9、一節(jié) 信道的數(shù)學(xué)模型及分類,（1）聯(lián)合概率,其中,稱為前向概率，描述信道的噪聲特性,稱為后向概率，,有時(shí)也把 稱為先驗(yàn),概率，把 稱為后驗(yàn)概率,（2）輸出符號(hào)的概率,（3）后驗(yàn)概率,表明輸出端收到任一符號(hào)，必定是輸入端某一符號(hào)輸入所致,為什么？,第二節(jié) 平均互信息,1、信道疑義度,這是收到 后關(guān)于X的后驗(yàn)熵，表示收到 后關(guān)于輸入符號(hào)的信息測(cè)度,這個(gè)條件熵稱為信道疑義度（損失熵），表示輸出端在收到一個(gè)符號(hào)后，對(duì)輸入符號(hào)尚存的不確定性，這是由信道干擾造成的，如果沒有干擾，H(X/Y)=0,一般情括下H(X/Y)小于H(X)，說明經(jīng)過信道傳輸，總能消除一些信源的不確定性，從而獲得一些信息。,第二節(jié)

10、平均互信息,I(X;Y)=H(X)-H(X/Y),2、平均互信息,因?yàn)镠(X),表示傳輸前信源的不確定性，而H(X/Y)表示收到一個(gè)符號(hào)后，對(duì)信源尚存的不確定性，所以二者之差信道傳遞的信息量。,下面我們討論一下互信息與其他的熵之間的關(guān)系,I(X;Y)=H(X)-H(X/Y) =H(X)+H(Y)-H(XY) =H(Y)-H(Y/X) (3.34),第二節(jié) 平均互信息,也可以得到：H(XY)=H(X)+H(Y/X)=H(Y)+H(X/Y),由3.34也可以看出，互信息I(X;Y)也表示輸出端H(Y)的不確定性和已知X的條件下關(guān)于Y的不確定性之差，也等于發(fā)送前后關(guān)于Y的不確定性之差。,H(X/Y)

11、即信道疑義度，也表示通過有噪信道造成的損失，故也稱為損失熵，因此信源的熵等于收到的信息量加上損失的熵；而H(Y/X)表示已知輸入的情況下，對(duì)輸出端還殘留的不確定性，這個(gè)不確定性是由噪聲引起的，故也稱之為噪聲熵。,互信息與各類熵之間的關(guān)系可以用下圖表示：,第二節(jié) 平均互信息,H(X,Y),H(X/Y) H(Y/X),H(X) H(Y) I(X,Y),可以看出，聯(lián)合熵等于兩圓之和減去第三部分，也等于一個(gè)圓加上另外一部分,下面討論兩種極端情況：,圖1,第二節(jié) 平均互信息,（1）無噪一一對(duì)應(yīng)信道,此時(shí)可以計(jì)算得：H(X/Y)=H(Y/X)=0在圖一中表示就是兩圓重合。,(2)輸入輸出完全統(tǒng)計(jì)獨(dú)立 此時(shí)

12、I(X;Y)=0 H(X/Y)=H(X) H(Y/X)=H(Y),第三節(jié) 平均互信息的特性,1、平均互信息的非負(fù)性,I(X;Y)=0,該性質(zhì)表明，通過一個(gè)信道總能傳遞一些信息，最差的條件下，輸入輸出完全獨(dú)立，不傳遞任何信息，互信息等于0，但決不會(huì)失去已知的信息。 2、平均互信息的極值性 I(X;Y)=H(X) 一般來說，信道疑義度總是大于0，所以互信息總是小于信源的熵，只有當(dāng)信道是無損信道時(shí)，信道疑義度（損失熵）等于0，互信息等于信源的熵。,第三節(jié) 平均互信息的特性,3、平均互信息量的交互性 I(X;Y)=I(Y;X) I(Y;X)表示從X中提取關(guān)于的Y的信息量，實(shí)際上I(X,Y)和I(Y,X

13、)只是觀察者的立足點(diǎn)不同，對(duì)信道的輸入X和輸出Y的總體測(cè)度的兩種表達(dá)形式,4、平均互信息的凸?fàn)钚?第三節(jié) 平均互信息的特性,定理3.1 平均互信息I(X;Y)是信源概率分布P(X)的 型凸函數(shù),這就是說，對(duì)于一定的信道轉(zhuǎn)移概率分布，總可以找到某一個(gè)先驗(yàn)概率分布的信源X，使平均交互信息量達(dá)到相應(yīng)的最大值Imax，這時(shí)稱這個(gè)信源為該信道的匹配信源?？梢哉f不同的信道轉(zhuǎn)移概率對(duì)應(yīng)不同的Imax。,第三節(jié) 平均互信息的特性,例：對(duì)于二元對(duì)稱信道,0 1-p 0,p,p,1 1-p 1,如果信源分布X=w,1-w，則,I(X;Y),w,1/2,1-H(P),第三節(jié) 平均互信息的特性,而：,所以：,當(dāng)信道固

14、定時(shí)，平均互信息時(shí)信源分布的 型凸函數(shù)，最大只為1-H(P),第三節(jié) 平均互信息的特性,定理3.2 平均互信息I(X;Y)信道傳遞概率分布P(Y/X)的U型凸函數(shù),這就是說，對(duì)于一個(gè)已知先驗(yàn)概率為P(X)的離散信源，總可以找到某一個(gè)轉(zhuǎn)移概率分布的信道，使平均互信息量達(dá)到相應(yīng)的最小值Imin?？梢哉f不同的信源先驗(yàn)概率對(duì)應(yīng)不同的Imin?；蛘哒fImin是P(X)的函數(shù)。即平均互信息量的最小值體現(xiàn)了信源本身的特性。,例：對(duì)于二元對(duì)稱信道,0 1-p 0,p,p,1 1-p 1,如果信源分布X=w,1-w，則 由此可得,I(X;Y),p,1/2,第四節(jié) 信道容量及其一般計(jì)算方法,第四節(jié) 信道容量及其一

15、般計(jì)算方法,我們先定義信息傳輸率： R=I(X;Y)=H(X)-H(X/Y)=H(Y)-H(Y/X) bit/符號(hào),由定理3.1可知，對(duì)于每一個(gè)確定信道，都有一個(gè)信源分布，使得信息傳輸率達(dá)到最大值，我們把這個(gè)最大值稱為該信道的信道容量。,信道容量與與信源無關(guān)，它是信道的特征參數(shù)，反映的是信道的最大的信息傳輸能力。 對(duì)于二元對(duì)稱信道，由圖可以看出信道容量等于 1-H(P),利用前面41頁結(jié)果,第四節(jié) 信道容量及其一般計(jì)算方法,（1）無噪無損信道（無噪一一對(duì)應(yīng)信道） 具有一一對(duì)應(yīng)關(guān)系的無噪無損信道,x1 y1 x2 y2 x3 y3,此時(shí)由于信道的損失熵和噪聲熵都等于0，所以 I(X;Y)=H(X

16、)=H(Y) C=logr=logs,只有當(dāng)輸入信源為等概率分布時(shí)，此類噪聲的信息傳輸率才達(dá)到極大值。,r個(gè)輸入，s個(gè)輸出,第四節(jié) 信道容量及其一般計(jì)算方法,(2)有噪無損信道,x1,x2,y1,y2,y3,y4,y5,此時(shí)信道損失熵為0，而信道噪聲熵不為0，從而 C=maxI(X;Y)=maxH(X)-H(X/Y)=maxH(X)=logr,可見，信道矩陣中每一列有且只有一個(gè)非零元素時(shí)，這個(gè)信道一定是有噪無損信道,輸入信源X的符號(hào)共有r個(gè)符號(hào)，并且僅當(dāng)輸入信源等概率分布時(shí)信息熵H（X）最大。,x3,y6,講稿給出了損失熵為零的證明,第四節(jié) 信道容量及其一般計(jì)算方法,(3)無噪有損信道：一個(gè)輸

17、出對(duì)應(yīng)多個(gè)輸入,x1,x2,x3,x4,x5,y1,y2,此時(shí)信道損失熵不為0，而信道噪聲熵為0，從而 C=maxI(X;Y)=maxH(Y)-H(Y/X)=maxH(Y)=logs,輸出信源Y的符號(hào)集有s個(gè)符號(hào)，其等概率分布時(shí)H（Y）最大，而且一定能找到一種最佳輸入分布使輸出符號(hào)Y達(dá)到等概率分布。,綜合上述三種情況，若嚴(yán)格區(qū)分的話，凡損失熵等于零的信道稱為無損信道；凡噪聲熵等于零的信道稱為無噪信道；而一一對(duì)應(yīng)的無噪信道則為無噪無損信道。求這三類信道的信道容量C的問題，已經(jīng)從互信息I(X;Y)的極值問題退化為求信息熵H(X)和H(Y)的極值問題。,復(fù)習(xí)上一次課的主要內(nèi)容,一、信道的分類 二、信

18、道的數(shù)學(xué)模型 三、信道容量定義,一、信道的分類,1、信道的分類：,根據(jù)信道用戶的多少，可分為：,（1）單用戶信道：只有一個(gè)輸入端和一個(gè)輸出端,（2）多用戶信道：至少有一端有兩個(gè)以上的用戶，雙向通信,根據(jù)輸入端和輸出端的關(guān)聯(lián)：,（1）無反饋信道：信道輸出端無信號(hào)反饋到輸入端，即輸出端信號(hào)對(duì)輸入端信號(hào)無影響、無作用。,（2）有反饋信道：信道輸出端的信號(hào)反饋到輸入端，對(duì)輸入端的信號(hào)起作用，影響輸入端信號(hào)發(fā)生變化。,第一節(jié) 信道的數(shù)學(xué)模型及分類,根據(jù)信道參數(shù)與時(shí)間的關(guān)系：,（1）固定參數(shù)信道,（2）時(shí)變參數(shù)信道,根據(jù)輸入輸出信號(hào)的特點(diǎn) （1）離散信道：信道的輸入和輸出都是時(shí)間上離散、取值 離散的隨機(jī)序

19、列。離散信道有時(shí)也稱為數(shù)字信道。 （2）連續(xù)信道：信道的輸入和輸出都是時(shí)間上離散、 取值連續(xù)的隨機(jī)序列，又稱為模擬信道。 （3）半離散半連續(xù)信道：輸入序列和輸出序列一個(gè)是離散的，而另一個(gè)是連續(xù)的。 （4）波形信道：信道的輸入和輸出都是時(shí)間上連續(xù)， 并且取值也連續(xù)的隨機(jī)信號(hào)。,單符號(hào)離散信道的數(shù)學(xué)模型 單符號(hào)離散信道的輸入變量為X，取值于 輸出變量為Y，取值于 。 并有條件概率 條件概率被稱為信道的傳遞概率或轉(zhuǎn)移概率。 一般簡(jiǎn)單的單符號(hào)離散信道的數(shù)學(xué)模型可以用概率空間X,p(y|x),Y來描述。 X Y,二、單符號(hào)離散信道的數(shù)學(xué)模型,第一節(jié) 信道的數(shù)學(xué)模型及分類,表示成矩陣形式：,信道矩陣中每一

20、行之和為1,三、信道容量定義,我們先定義信息傳輸率： R=I(X;Y)=H(X)-H(X/Y)=H(Y)-H(Y/X) bit/符號(hào),由定理3.1可知，對(duì)于每一個(gè)確定信道，都有一個(gè)信源分布，使得信息傳輸率達(dá)到最大值，我們把這個(gè)最大值稱為該信道的信道容量。,信道容量與與信源無關(guān)，它是信道的特征參數(shù)，反映的是信道的最大的信息傳輸能力。,第四節(jié) 信道容量及其一般計(jì)算方法,2、對(duì)稱離散信道的信道容量,離散信道中有一類特殊的信道，其特點(diǎn)是信道矩陣具有行對(duì)稱性，利 用這個(gè)對(duì)稱性我們可以簡(jiǎn)化信道容量的計(jì)算。 定義4.1 若信道矩陣中，每行都是第一行元素的不同排列，則稱此 類信道為行對(duì)稱信道。 書上的例子P8

21、5 定義4.2 若信道矩陣中，每列都是第一列元素的不同排列，則稱此 類信道為列對(duì)稱信道。書上的例子P85 定義4.3 如果信道矩陣共有m行，n列(一般mn)，若信道矩陣中每一行都是第一行元素的不同排列，而且信道矩陣中每一列也是第一列元素的重新排列，則稱為對(duì)稱信道。,如： 下面的兩個(gè)信道矩陣為對(duì)稱信道。,定義4.4 若信道矩陣中，每行都是第一行元素的不同排列，每列并不都是第一列元素的不同排列，但是可以按照信道矩陣的列將信道矩陣劃分成若干對(duì)稱的子矩陣，則稱這類信道為準(zhǔn)對(duì)稱信道。書上的例子P85 定義4.5 若對(duì)稱信道中輸入符號(hào)和輸出符號(hào)個(gè)數(shù)相同，且信道中總 的錯(cuò)誤概率為p，對(duì)稱地平均分配給r-1個(gè)

22、輸出符號(hào)，r為輸入輸出符號(hào)的個(gè)數(shù)，即信道矩陣為 則稱此信道為強(qiáng)對(duì)稱信道或均勻信道,它是對(duì)稱離散信道的一種特例。該信道的各列之和也為1。,第四節(jié) 信道容量及其一般計(jì)算方法,下面我們來計(jì)算對(duì)稱離散信道的信道容量,I(X;Y)=H(Y)-H(Y/X) 而,H(Y/X=x)是固定X=x時(shí)對(duì)Y求和，即對(duì)信道矩陣的行求和，而由于對(duì)稱信道定義，我們知道，此值是一個(gè)與x無關(guān)的一個(gè)常數(shù)，即,因此,可以看出，當(dāng)輸出等概分布時(shí)，即H(Y)=logs時(shí)信道容量達(dá)到。,為對(duì)稱信道中行矢量,第四節(jié) 信道容量及其一般計(jì)算方法,那么，在什么樣的信源輸出情況下，信道輸出能等概分布呢？可以證明，輸入等概分布時(shí)，輸出也等概分布,信

23、道矩陣中每列元素之和,由于信道是離散對(duì)稱的，則每一列元素都是由相同的元素的不同排列構(gòu)成的，所以每一列元素的和是相等的。如果設(shè)為A，則有：,(j=1,2,s),可以得出：在離散對(duì)稱信道中輸入等概率分布可以得到輸出等概率分布。,既輸入等概率時(shí)，可以得到信道的信道容量：,例3-6 一信道的轉(zhuǎn)移概率矩陣為:,求信道容量和達(dá)到容量時(shí)的輸出概率。,解：設(shè)信道矩陣每列元素為p1,p2,p3，由于信道為離散對(duì)稱信道，故當(dāng)輸入等概率時(shí)達(dá)到容量C，此時(shí)輸出也等概率。所以:,=0.126比特/符號(hào),第四節(jié) 信道容量及其一般計(jì)算方法,例：,對(duì)于二元對(duì)稱信道,這個(gè)式子很重要。,第四節(jié) 信道容量及其一般計(jì)算方法,例：對(duì)于

24、強(qiáng)對(duì)稱信道，其信道容量為：,第四節(jié) 信道容量及其一般計(jì)算方法,3、準(zhǔn)對(duì)稱信道的信道容量計(jì)算： 若信道的列可以劃分成若干個(gè)互不相交的子集，每一個(gè)子集都是對(duì)稱信道，則稱該信道為準(zhǔn)對(duì)稱信道，如：,可劃分為：,第四節(jié) 信道容量及其一般計(jì)算方法,又如：,可分成：,第四節(jié) 信道容量及其一般計(jì)算方法,可以證明達(dá)到信道容量的輸入分布是等概分布，也可計(jì)算準(zhǔn)對(duì)稱信道的信道容量為：,其中r是輸入符號(hào)集的個(gè)數(shù)， 為矩陣中的行元素,是第k個(gè)子矩陣中的行元素之和， 是第k個(gè)子矩陣的列元素之和,書上的有問題,N1=3/8,M1=3/8;N2=1/2,M2=1;N3=1/8,M3=1/4,第四節(jié) 信道容量及其一般計(jì)算方法,例

25、：,可分成：,第四節(jié) 信道容量及其一般計(jì)算方法,4、一般離散信道的信道容量思路,利用拉格朗日可以對(duì)輸入分布求極值，得到,而：,具體的推導(dǎo)可以參考書P89,定理3.3 一般離散信道達(dá)到信道容量的充要條件是輸入概率分布Pi滿足,該定理說明，當(dāng)平均互信息達(dá)到信道容量時(shí)，信源每一個(gè)符號(hào)都對(duì)輸出端輸出相同的互信息。,第四節(jié) 信道容量及其一般計(jì)算方法,第四節(jié) 信道容量及其一般計(jì)算方法,可以利用該定理對(duì)一些特殊信道求得它的信道容量,例：輸入符號(hào)集為:0,1,2，輸出符號(hào)集0,1，信道傳遞矩陣為,假設(shè)P(0)=P(2)=1/2，P(1)=0，則：,利用,求出,第四節(jié) 信道容量及其一般計(jì)算方法,所以：,滿足充要

26、條件,第四節(jié) 信道容量及其一般計(jì)算方法,對(duì)于一般信道的求解方法，就是求解方程組,移項(xiàng)得：,令,則,若r=s，此方程有解，可以解出s個(gè)未知數(shù) ，再根據(jù),得,從而,第四節(jié) 信道容量及其一般計(jì)算方法,例：,可列方程組：,第四節(jié) 信道容量及其一般計(jì)算方法,解之得：,可以求出最佳輸入分布為,上述求得的P(ai)(i=1,2,3,4)都大于零，故求得的結(jié)果是正確的,圖49 兩個(gè)信道,4.3 組合信道的容量,考慮有兩個(gè)信道。信道1 信道2：,下面介紹下面三種不同組合情況下的信道容量。,4.3.1 獨(dú)立并行信道,在這種情況下，二個(gè)信道作為一個(gè)信道使用，傳送符號(hào) ，接收符號(hào) ，根據(jù)定理2.4，對(duì)于離散無記憶信道

27、，下式成立 （4-22）,對(duì)上面不等式兩邊取最大值，得 C C 1 + C2 （4-23）,推廣到N個(gè)信道的并行組合，當(dāng)N個(gè)信道并行獨(dú)立使用時(shí)，記Ck (k = 1, 2, , N )為第k個(gè)信道的信道容量，C為組合信道的總?cè)萘?，則有 （4-24）,等號(hào)成立的條件，都要求信源離散無記憶，即要求信道獨(dú)立使用且輸入獨(dú)立。,4.3.2 和信道,兩個(gè)信道輪流使用（不能同時(shí)），使用概率分別為p1, p2，且p1+p2 = 1，記概率分布P =（p1, p2），和信道的平均互信息計(jì)算如下 I（P）= I（p1, p2） = p1I（X;Y）+ p 2 I（X /;Y /）+ H 2（P） 式中：H 2（P

28、）= - p1 log p1 - p2 log p2,根據(jù)定義有 （4-26）,求使式(4-26)取極大值的P 令 ，對(duì)數(shù)以2為底，注意到p2 = 1- p1， 得 記 C1 - log p1 = C2 - log p2 = （為待定常數(shù)） （4-27）,從式（4-27）中解出： （4-28）,將式(4-28)代入條件p1+p2 = 1，得 （4-29）,式（4-28）中的p1, p2就是使平均互信息量I（p1, p2）達(dá)到最大的取值，將其代入式（4-26），得：,= （p1+p2）=,將式（4-29）代入式（4-30）得：,推廣到N個(gè)信道輪流使用的情況, 當(dāng)N個(gè)信道以不同概率輪流使用時(shí)，記C

29、k (k = 1, 2, , N )為第k個(gè)信道的信道容量，C為組合信道的總?cè)萘?，則有 （4-31）,4.3.3 串行信道,將兩個(gè)信道級(jí)聯(lián)，有X / = Y，如圖4-10所示 。,X,Y /,Y =X /,圖4-10 串行信道,串行信道的信道轉(zhuǎn)移概率 用矩陣表示為： （4-32）,串行級(jí)聯(lián)信道的信道轉(zhuǎn)移概率趨向于兩個(gè)獨(dú)立信道轉(zhuǎn)移概率的均值。若將N個(gè)轉(zhuǎn)移概率相同的信道級(jí)聯(lián)，當(dāng)N 時(shí)，其總信道容量將趨于零。,信道1：P1 = p (yx) ，信道2：P2 = p (yx ) ，信道1和信道2是獨(dú)立的，信道2的輸出Z只與其輸入Y及信道轉(zhuǎn)移概率P2 = p (yx )有關(guān)，而與X無關(guān)。因此信道1和信道

30、2串連就構(gòu)成了一個(gè)馬爾可夫鏈，對(duì)于馬爾可夫鏈有如下定理：,圖411 馬爾可夫鏈,定理4.4 若隨機(jī)變量X、Y、Z組成一個(gè)馬爾可夫鏈，如圖4-11所示，則有 I（X; Z） I（X; Y） （4-33） I（X; Z） I（Y; Z） （4-34）,證明式（4-33） I（X；Z）- I（X；Y） = H（X）- H（XZ） - H（X）- H（XY） = H（XY）- H（XZ） H（XY）- H（XYZ） （條件熵小于等于無條件熵） = H（XY）- H（XY） （因?yàn)閄、Y、Z為馬爾可夫鏈） = 0 I（X；Z） I（X；Y） 證畢,數(shù)據(jù)處理定理：無論經(jīng)過何種數(shù)據(jù)處理，都不會(huì)使信息量增加。

31、,式（4-34）可類似證得.,從上面證明過程可看出，若滿足H（XZ）= H（XY），即滿足p (xz) = p (xy) 時(shí)，式(4-33)中的等號(hào)成立，即有I (X; Z) = I (X; Y)，說明這種情況下串聯(lián)傳輸不會(huì)增加信息的損失。,第五節(jié) 離散無記憶擴(kuò)展信道及其信道容量,離散無記憶信道為：,則它的N次擴(kuò)展信道為：,第五節(jié) 離散無記憶擴(kuò)展信道及其信道容量,為N次擴(kuò)展信源中的一個(gè)符號(hào),為N次擴(kuò)展接收符號(hào)集中的一個(gè)符號(hào),第五節(jié) 離散無記憶擴(kuò)展信道及其信道容量,我們首先從一個(gè)例子開始 例：二元無記憶對(duì)稱信道得二次擴(kuò)展信道 二元記憶對(duì)稱信道為,可以將信道的擴(kuò)展和信源的擴(kuò)展聯(lián)系起來看，當(dāng)信源擴(kuò)展

32、以后，信道也就稱為了擴(kuò)展信道。,第五節(jié) 離散無記憶擴(kuò)展信道及其信道容量,則它的二次擴(kuò)展信道為：,第五節(jié) 離散無記憶擴(kuò)展信道及其信道容量,根據(jù)互信息的定義,定理3.5 如果信道是無記憶的，即信道傳遞概率滿足,則：,定理3.6 如果信道的輸入信源是無記憶的,則：,第五節(jié) 離散無記憶擴(kuò)展信道及其信道容量,因此，如果信源、信道都是無記憶的,這就是離散無記憶擴(kuò)展信道的信道容量，該信道容量在信源是無記憶信源且每一個(gè)輸入變量Xi達(dá)到最佳分布時(shí)達(dá)到。,本章例子,先定義信息傳輸率： R=I(X,Y)=H(X)-H(X/Y)=H(Y)-H(Y/X) bit/符號(hào),由定理3.1可知，對(duì)于每一個(gè)確定信道，都有一個(gè)信源

33、分布，使得信息傳輸率達(dá)到最大值，我們把這個(gè)最大值稱為該信道的信道容量。,信道容量與與信源無關(guān)，它是信道的特征參數(shù)，反映的是信道的最大的信息傳輸能力。,本章小結(jié) 一、本章主要給出了信道容量的定義,二、討論了信道容量的計(jì)算方法。,(1)無噪無損信道 (2)有噪無損信道,此時(shí)由于信道的損失熵和噪聲熵都等于0，所以 I(X;Y)=H(X)=H(Y) C=logr=logs,此時(shí)信道損失熵為0，而信道噪聲熵不為0，從而 C=maxI(X;Y)=maxH(X)-H(X/Y)=maxH(X)=logr,(3)無噪有損信道： (4)對(duì)稱離散信道的信道容量,此時(shí)信道損失熵不為0，而信道噪聲熵為0，從而 C=maxI(X;Y)=maxH(Y)-H(Y/X)=maxH(Y)=log