信息論與編碼課件(全部課程內(nèi)容)

信息論與編碼通信工程專業(yè)課程簡介任務(wù)：學(xué)習(xí)信息論的基礎(chǔ)知識；掌握信源編碼、信道編碼、加密編碼的原理和方法。學(xué)習(xí)之后，能更深的理解現(xiàn)代通信系統(tǒng)。參考書R.J.McEliece，信息論與編碼理論（第二版）陳運，信息論與編碼姜丹，信息論與編碼教材編排第一章課程的發(fā)展和基本內(nèi)容第二章至第四章信息論基礎(chǔ)知識第五章信源編碼第六章信道編碼第七章加密編碼第一章緒論《信息論與編碼》一、通信系統(tǒng)通信系統(tǒng)模型信源信宿信源編碼加密信源譯碼解密信道編碼信道譯碼信道干擾噪聲信源：消息的來源信道：消息的傳送媒介信宿：消息的目的地通信系統(tǒng)的性能指標有效性——信源編碼，去除冗余可靠性——信道編碼，添加冗余安全性——加密編碼經(jīng)濟性？如何優(yōu)化，使得通信系統(tǒng)的這些指標最佳？二、Shannon信息論的中心問題“信息論”，又稱為“通信的數(shù)學(xué)理論”，是研究信息的傳輸、存儲、處理的科學(xué)。信息論的中心問題：為設(shè)計有效而可靠的通信系統(tǒng)提供理論依據(jù)。問題一：信源消息常常不能夠完全發(fā)送。（否則發(fā)送量巨大，比如：無盡的天空。因此優(yōu)先撿有用的發(fā)送）問題二：信道因干擾而出現(xiàn)差錯，如何進行檢錯和糾錯。三、信息的概念信息一般含義（一）“信息”是作為通信的消息來理解的。在這種意義下，“信息”是人們在通信時所要告訴對方的某種內(nèi)容。（二）“信息”是作為運算的內(nèi)容而明確起來的。在這種意義下，“信息”是人們進行運算和處理所需要的條件、內(nèi)容和結(jié)果，并常常表現(xiàn)為數(shù)字、數(shù)據(jù)、圖表和曲線等形式。（三）“信息”是作為人類感知的來源而存在的。信息的本質(zhì)“信息是關(guān)于事物運動的狀態(tài)和規(guī)律”?；蛘哒f，是關(guān)于事物運動的“知識”。在通信系統(tǒng)中，傳送的本質(zhì)內(nèi)容是信息。信息的基本概念在于它的不確定性。信息與消息、信號比較消息是信息的數(shù)學(xué)載體、信號是信息的物理載體信號：具體的、物理的消息：具體的、非物理的信息：非具體的、非物理的補充閱讀：如何定量描述和度量信息？矩陣［Ｐ］稱為單符號離散信道的信道矩陣；

信道矩陣［Ｐ］中的每一個元素都處于[0，1]區(qū)間；每行元素之和均等于1。即：第一節(jié)單符號離散信道的數(shù)學(xué)模型第二節(jié)信道的交互信息量

信息是消息的不確定性的消除，不確定性又是消息統(tǒng)計特性的函數(shù)，要揭示信道傳輸信息的規(guī)律，勢必首先分析信道傳遞作用對傳遞消息的統(tǒng)計特性的影響和變化規(guī)律。若信源的信源空間為其中給定信道的信道矩陣

一.1.”輸入符號,輸出符號”的聯(lián)合概率其中：是信源:的先驗概率分布；是信道的傳遞概率，即信道矩陣[P]中的元素，亦稱為信道的“前向概率”。2.“輸出符號”的概率

當(dāng)信源的信源空間已知，信道的信道矩陣給定時，個輸出符號概率分布，均等于信源發(fā)符號的先驗概率分布，與信道矩陣中第行、第列元素相乘，然后把從1到的個乘積相加之和。即有3.“輸出符號后，推測輸入符號”的后驗概率當(dāng)信源的信源空間已知，信道的信道矩陣給定后，個后驗概率均可由前三個式求得。

信源發(fā)某符號，由于受噪聲的隨機干擾，在信道的輸出端輸出符號的某種變型。信道所傳送的信息量，即信宿收到后，從中獲取關(guān)于的信息量，這等于信宿收到前、后，對符號的不確定性的消除，即有

[信宿收到后，從中獲取關(guān)于的信息量]=[信宿收到前，對信源發(fā)的先驗不確定性]-[信宿收到后，對信源發(fā)仍然存在的后驗不確定性]=[信宿收到前、后，對信源發(fā)的不確定性的消除]而信宿收到前，對信源發(fā)符號的先驗不確定性

由于收信者接到后，推測信源發(fā)符號的概率，已由收信者收到前對信源發(fā)的先驗概率，轉(zhuǎn)變?yōu)楹篁灨怕?，所以信宿收到后，對信源發(fā)符號仍然存在的后驗不確定性，應(yīng)該等于信宿收到后推測信源發(fā)的后驗概率的倒數(shù)的對數(shù)，即由此可得：

我們把信宿收到后，從中獲取關(guān)于的信息量稱為輸入符號和輸出符號之間的交互信息，簡稱為互信息。二.互信函數(shù)的三種形式此式稱為符號和之間的互信函數(shù)．我們把信宿收到后，從中獲取關(guān)于的信息量稱為輸入符號和輸出符號之間的交互信息量，簡稱互信息．它表示信道在把輸入符號傳遞為輸出符號的過程中，信道所傳遞的信息量．1.２．

通信前，信道輸入，輸出端同時出現(xiàn)和的先驗不確定性．通信后，信道輸入，輸出端同時出現(xiàn)和仍然存在的后驗不確定性．３．交互信息量有以上三種不同的表達式，這三種表達式的任何一種形式都有一個共同點，即交互信息量等于后驗概率與先驗概率比值的對數(shù)．交互信息量＝log（后驗概率／先驗概率）如把先驗概率看作是先驗可知或事先測定的，那么信息傳遞的交互信息量就只取決于由信道傳遞概率決定的后驗概率．三．后驗概率變化對交互信息量的影響收信者收到輸出符號后，推測信源以概率１發(fā)信號．收信者收到后，推測信源發(fā)信號的后驗概率大于收到前推測信源發(fā)信號的先驗概率．

收信者收到后，推測信源發(fā)信號的后驗概率，與收到前推測信源發(fā)信號的先驗概率相等．收信者收到后，推測信源發(fā)信號的后驗概率，反而小于收到前推測信源發(fā)信號的先驗概率.例2.3表2.1中列出某信源發(fā)出的八種不同消息ai(i=1,2,…,8),相應(yīng)的先驗概率p(ai)(i=1,2,…,8),與消息ai(i=1,2,…,8)一一對應(yīng)的碼字wi(i=1,2,…,8).同時給出輸出第一個碼符號“0”后，再輸出消息a1,a2,a3,a4對應(yīng)碼字w1,w2,w3,w4后面二個碼符號的概率，即輸出第一個碼符號“0”后，再出現(xiàn)消息a1,a2,a3,a4的概率，試計算第一個碼符號“0”對消a1,a2,a3,a4提供的信息量。

表2.1消息a1a2a3a4a5a6a7a8碼字000001010011100101110111消息概率1/41/41/81/81/161/161/161/16輸出“0”后消息概率1/31/31/61/60000接到消息ai(i=1,2,3,4)后，推測第一碼符號為“0”的后驗概率等于1，即有第一個碼符號“0”對消息ai(i=1,2,3,4)提供的信息量，就是從消息ai(i=1,2,3,4)中獲得關(guān)于第一個碼符號“0”的交互信息量

（i=1,2,3,4)其中p(0)是信源發(fā)第一碼符號“0”的先驗概率則得(i=1,2,3,4)這說明，第一碼符號“0”的自信息量既表達第一碼符號“0”對消息ai(i=1,2,3,4)提供的最大信息量，也表示消息ai(i=1,2,3,4)從第一碼符號“0”中獲得的最大信息量。

p(0/ai)=1(i=1,2,3,4)pp(0)=p(a1)+p(a2)+p(a3)+p(a4)=1/4+1/4+1/8+1/8=3/4第三節(jié)條件交互信息量

設(shè)信道的輸入符號集，輸出符號集。信道的輸入號集，輸出符號集。現(xiàn)將信道和信道接成串接信道。若將信源空間為的信源接入串接信道，由于信源的符號集與串接信道的輸入符號集完全一致，信源的各種不同符號均可通過串接信道，在信道Ⅰ的輸出端（信道Ⅱ的輸入端）構(gòu)成隨機變量，信道Ⅱ的輸出（串接信道的輸出）端構(gòu)成隨機變量。假定：信道Ⅰ的傳遞概率信道Ⅱ的傳遞概率ⅠⅡⅠⅡ

由已知信源的先驗概率分布和以上兩式可得

并設(shè)

由隨機變量的聯(lián)合概率分布，即可得隨機變量各自概率分布、任意兩個隨機變量的聯(lián)合概率分布以及各種條件概率分布．

即有

在隨機變量出現(xiàn)的前提下，從隨機變量的某符號中獲取關(guān)于信源的某符號的條件交互信息量,等于隨即變量出現(xiàn)前后，對信源發(fā)某符號的條件不確定性的消除．

在隨機變量出現(xiàn)某符號的前提條件下，信源的某符號與隨機變量中的某符號之間的的條件交互信息量,同樣也等于在隨機變量出現(xiàn)某符號的前提條件下，Ⅰ信道通信前后，輸入輸出端同時出現(xiàn)和的條件不確定性的消除．

信源出現(xiàn)符號前后，對隨機變量出現(xiàn)符號的條件不確定性的消除，等于隨機變量出現(xiàn)某符號的前提條件下，從信源的某符號中，獲取關(guān)于隨機變量的某符號的條件交互信息量．４．重要結(jié)論例2.4表2.2中列出了無失真信源編碼信源信息，消息的先驗概率以及每一個消息所對應(yīng)的碼字

表2.2我們?nèi)i=a4,且以bj，cl，dk，分別表示碼字“011”中的第一個碼字符號“0”；第二個碼字符號“1”；第三個碼字符號“1”。根據(jù)相關(guān)交互信息量的理論(2.43),(2.45)式可有信源消息a1a2a3a4a5a6a7a8碼字000001010011100101110111消息概率1/41/41/81/81/161/161/161/16其中：(1)而p(a4/0)=p(11/0)=p(011)/p(0);p(011)=p(a4)=1/8;p(0)=p(000)+p(001)+p(010)+p(011)=1/4+1/4+1/8+1/8=3/4所以p(a4/0)=1/6則得比特(2)而p(a4/01)=p(1/01)=p(011)/p(01);因為p(01)=p(010)+p(011)=p(a3)+p(a4)=1/8+1/8=1/4所以p(a4/01)=1/2則得

(3)而p(a4/011)=1所以

以上三項計算結(jié)果表明，在消息a4相對應(yīng)的碼字“011”中：第一個碼符號“0”提供關(guān)于消息a4的信息量I(0;a4)=I(a4;0)=log4/3(比特)；在收到了第一個碼符號“0”的條件下，第二個碼符號“1”提供關(guān)于消息a4的條件交互信息量I(0;a4/0)=I(a4;1/0)=log3(比特)；在收到“01”序列的條件下，第三個碼符號“1”提供關(guān)于消息a4的條件交互信息量I(0;a4/01)=I(a4;1/0)=1(比特)。所以，從碼字“011”中的三個碼符號總共提供關(guān)于消息a4的相關(guān)交互信息量

比特另一方面，消息a4自信息量

比特這從信息測量角度證實了由于a4與相應(yīng)碼字“011”是一一對應(yīng)的確定關(guān)系，相關(guān)交互信息量I(a4;011)就是消息a4的自信息量I(a4).第四節(jié)平均交互信息量平均交互信息量有三種不同的表達形式：上式表示從獲取關(guān)于的平均交互信息量，等于收到前后，關(guān)于的平均不確定性的消除．其中表示收到隨機變量后，對隨機變量仍然存在的平均不確定性，也稱其為疑義度．

上式表明，信源通過傳遞概率為的信道輸出隨機變量,信道傳遞的平均交互信息量,等于通信前后，隨機變量和同時出現(xiàn)的平均不確定性的消除．其中，表示隨機變量，通過信道傳遞輸出隨機變量后，信道兩端同時出現(xiàn)和的后驗平均不確定性，也稱為共熵．

上式表明，對于“反向信道”來說，從輸出隨機變量中，獲取關(guān)于輸入隨機變量的平均交互信息量,等于通信前后，對于的平均不確定性的消除．其中，表示輸出隨機變量的前提下，對輸入隨機變量仍然存在的平均不確定性，這個反向疑義度一般叫做噪聲熵．以上三種表達式都說明，平均交互信息量就是通信前后，平均不確定性的消除．例2.5設(shè)信源X的符號集X：{a1,a2},先驗概率分布為p(a1)=w(0<w<1);p(a2)=1-w。信道的輸入符號集X：{a1,a2}，輸出符號集Y：{a1,a2}，傳遞概率P(Y/X)：{p(aj/ai)=pij(i=1,2;j=1,2}?，F(xiàn)將信源X與信道相接(圖2.11)，試求信道的平均交互信息量I(X：Y)。p11p22p21p12a1a2a1a2XYP(a1)=wP(a2)=1-w圖2.11根據(jù)書中(2.5)式得各聯(lián)合概率：根據(jù)書中(2.6)式得隨機變量Y的概率分布：(3)由PY(a1),PY(a2)求得隨機變量Y的熵P(a1a1)=p(a1)p(a1/a1)=wp11P(a1a2)=p(a1)p(a2/a1)=wp12P(a2a1)=p(a2)p(a1/a2)=(1-w)p21P(a2a2)=p(a2)p(a2/a2)=(1=w)p22PY(a1)=p(a1a1)+p(a2a1)=wp11+(1-w)p21PY(a2)=p(a1a2)+p(a2a2)=wp12+(1-w)p22由p(aj/ai)=pij(i=1,2；j=1,2)求得條件熵由H(Y)和H(Y/X)求得平均交互信息量第五節(jié)平均交互信息量的非負性

由于考慮到，以及“底”大于1的對數(shù)是型凸函數(shù)可得當(dāng)且僅當(dāng)對一切都有即當(dāng)信源和信宿統(tǒng)計獨立時，等式才能成立，即有

平均交互信息量的非負性表明，雖然對于信源和信宿的兩個特定具體符號和之間的交互信息量來說，有可能出現(xiàn)負值，但從平均意義上來說，信道每傳遞一個符號，總能傳遞一定的信息量，至少等于零，絕不會出現(xiàn)負值。由平均交互信息量的非負性可得

僅當(dāng)和統(tǒng)計獨立時，上式的等號才成立。

是“正向信道”的后驗熵；是“反向信道”的后驗熵；是通信后和同時出現(xiàn)的后驗共熵。

上頁三式指明，后驗熵絕不會超過先驗熵，最多等于先驗熵。熵總是向減少的方向發(fā)展，最多維持不變，絕不會向增加的方向發(fā)展。熵減少的過程，就是信道傳遞信息的過程。我們把這種特性稱之為“后熵不增性”原理。第六節(jié)平均交互信息量的極值性

根據(jù)和，剖析平均交互信息量的極值性以及能使平均交互信息量達到最大值的相應(yīng)信道的特性。

1.因為后驗概率和聯(lián)合概率都具有一般概率的秉性，即

所以對“底”大于1的對數(shù)來說有

可得

所以

只有當(dāng)

時，等式才能成立，即有進而這表明，對于給定信源來說，只有接上一個后驗概率要么等于1，要么等于零（疑義度）的信道，才能使平均交互信息量達到最大值，從中獲取關(guān)于的全部信息量。這樣的信道稱為離散無噪信道。2.因為前向概率和聯(lián)合概率都具有一般概率的秉性，即

所以，對“底”大于1的對數(shù)有則得到進而得到

只有當(dāng)時等式才能成立，即有進而推出這表明，只有當(dāng)信道的傳遞概率要么等于1，要么等于零，即當(dāng)信道的噪聲熵（反向疑義度）時，從信源中才能獲取關(guān)于信宿的全部信息量，信道的平均交互信息量達到最大值。這樣的信道亦稱為離散無噪信道。第七節(jié)平均交互信息量的不增性

下面，我們從從四個方面剖析串接信道中平均交互信息量之間的關(guān)系。

1.從隨機變量中獲取關(guān)于隨機變量的平均交互信息量，一般不會超過從中獲取關(guān)于聯(lián)合隨機變量的平均交互信息量，只有當(dāng)隨機變量序列是Markov鏈時，兩者才能相等，即當(dāng)且僅當(dāng)時等式才能成立，即有2.從隨機變量中獲取關(guān)于隨機變量的平均交互信息量，一般不會超過從中獲取關(guān)于聯(lián)合隨機變量的平均交互信息量，只有當(dāng)隨機變量序列是Markov鏈時，兩者才能相等，即當(dāng)且僅當(dāng)時，等式才能成立，即3.當(dāng)隨機變量序列是Markov鏈時，從隨機變量中獲取關(guān)于隨機變量的平均交互信息量，只有當(dāng)隨機變量序列亦是Markov鏈時，兩者才能相等，即當(dāng)隨機變量序列是Markov鏈時，有當(dāng)且僅當(dāng)時，等式才能成立，即4.當(dāng)隨機變量序列是Markov鏈時，從隨機變量中獲取關(guān)于隨機變量的信息量，一般不會超過從隨機變量中獲取關(guān)于隨機變量的信息量。只有當(dāng)隨機變量序列亦是Markov鏈時，兩者才能相等。即當(dāng)隨機變量序列是Markov鏈時，有當(dāng)且僅當(dāng)時，等式才能成立，即第八節(jié)平均交互信息量的上凸性

平均交互信息量都可表示為給定信道的傳遞概率和輸入信源的概率分布的函數(shù)：由于給定信道的傳遞概率固定不變，所以，對于給定信道來說，平均交互信息量只是輸入信源的概率分布的函數(shù)：所以輸入信源的概率分布不同，就有不同的平均交互信息量。

設(shè)有信源，其概率分布。若把信源輸入給定信道，則其平均交互信息量可以寫為：

另設(shè)有信源，其概率分布。若把信源輸入給定信道，則其平均交互信息量可以寫為：

再有信源，其概率分布設(shè)計成和的內(nèi)插值，即其中：。若把信源輸入給定信道，則其平均交互信息量可以寫為：

由（2.140）、（2.141）、（2.142）式可得

上式表明，對于傳遞概率固定為的給定信道，其平均交互信息量是輸入信源的概率分布的函數(shù)，且函數(shù)的平均值小于或等于平均值的函數(shù)。這說明，平均交互信息量是信源概率分布的型凸函數(shù)。這就是平均交互信息量的上凸性。第九節(jié)信道容量及其一般算法信道容量的定義：

信道容量

表示傳遞函數(shù)固定為的給定信道所能傳遞的平均交互信息量的最大值。信道的信道容量，即信道的最大的信息率。信道容量也可以定義為信道的最大的信息速率，記為。信道容量是信道本身特征參數(shù)的函數(shù)，反映信道本身的信息特征。從數(shù)學(xué)上來說，信道容量就是平均交互信息量對

取極大值。因為任何信源分布都必須遵守約束條件為此，作輔助函數(shù)其中為待定常數(shù)。輔助函數(shù)對分別取偏導(dǎo)，并置之為零，得個穩(wěn)定點方程，并與約束方程聯(lián)立，得到方程組后，求解以后，即可得到信道容量。

由前面的分析知道，對于傳遞函數(shù)固定的給定信道來說，當(dāng)輸入信源為其匹配信源時，從平均的意義上來說，從信道每一輸出符號中獲取關(guān)于信源的任何一種符號的平均交互信息量都是相等的，其值就等于信道容量。

由此可導(dǎo)出關(guān)于信道容量解的重要結(jié)論：一般單信號離散信道，其平均互信息量達到其信道容量的充要條件是，其匹配信源的概率分布滿足對的所有i

對的所有i式中：

上述結(jié)論的充分性與必要性都得到了證明。通過這個結(jié)論我們可以得知，若信道平均交互信息量達到信息容量，則匹配信源的符號集中，除了概率為零的符合以外的每一個符合，對輸出的隨即變量提供的平均信息量相等，其值等于信道容量。這表明，信道容量取得的過程，亦是信源符號概率分布自我調(diào)整的過程。

在這里，需要注意的是，信道容量解的充要條件只提出信道達到容量時，輸入信源符號的概率分布應(yīng)滿足的條件，并沒有給出輸入信源符號概率分布的具體數(shù)值，因而也不可能給出信道容量的具體數(shù)值。另外，信道容量解的充要條件還指明，達到信道容量的匹配信源不一定是唯一的，凡滿足書上式（2.166）的概率分布的信源，都是匹配信源。例2.8設(shè)信道的輸入符號集X：{0，1，2}，輸出符號集Y：{0，1}，其傳遞特性如圖2.29所示

圖2.29若輸入信道X的信源空間為X：012[X．P]：{P(X)：0.500.5

11/21/2101201XY則信源符號“0”對輸出隨機變量Y提供的平均信息量

比特/符號(2.187)則信源符號“2”對輸出隨機變量Y提供的平均信息量

比特/符號(2.188)概率為零的信源符號“1”對輸出隨機變量Y提供的平均信息量

比特/符號(2.189)由(2.187),(2.188),(2.189)式可得p(ai)≠0p(ai)=0即滿足(2.165)式，因此，求得圖2.29給定信道的信道容量C=I(ai;Y)=1比特/符號(p(ai)≠0)而所設(shè)輸入信源X的概率分布P{X=0}=0.5；P(X=1}=0；P{X=2}=0.5就是使圖2.29給定信道達到信道容量的概率分布，即所設(shè)信源[X。P]就是這個信道的匹配信源

我們再來討論另一給定信道的信道容量，如給定信道的輸入符號集X：{a1,a2,a3,a4,a5}輸出符號集Y：{b1，b2}，其傳遞特性如圖2.30所示。

圖2.30若輸入信源的信源空間為X：a1

a2

a3

a4

a5

[X．P]：{

P(X)：1/41/401/41/4

a1a2a3a4a5b1b211110.50.5XY則用(2.187),(2.188),(2.189)式相同方法，可得I(ai;Y)=log2=1比特/符號(i=1,2,4,5)I(aj;Y)=0<1比特/符號(j=3)由(2.166)式得信道容量C=I(ai;Y)=1比特/符號達到信道容量的信源概率分布為P(X=a1)=P(X=a2)=P(X=a4)=P(X=a5)=1/4;P(X=a3)=0(2.190)若輸入信源X的信源空間為X：a1

a2

a3

a4

a5

[X．P]：{

P(X)：0.50000.5則相當(dāng)于一個二元等概信源與一個一一對應(yīng)具有確定關(guān)系的無噪信道相接，即有I(ai;Y)=log2=1比特/符號(i=1,5)I(aj;Y)=0<1比特/符號(j=2,3,4)由(2.166)式得信道容量C=I(ai;Y)=1比特/符號達到信道容量的信源概率分布為P(X=a1)=0.5P(X=a2)=P(X=a3)=P(X=a4)=0;P(X=a5)=0.5(2.191)(2.190),(2.191)式是同一給定信道達到信道容量的兩種不同的信源概率分布。這證實了達到信道容量的信源概率分布不一定是唯一的。

第十節(jié)幾種無噪信道的信道容量

單符號離散無噪信道是一種最簡單最基本的特殊信道。我們知道，無噪信道的信息傳輸問題，就是信源的信息熵問題。在前面討論的基礎(chǔ)之上，簡化了計算過程和方法，直接導(dǎo)出以下的三種無噪信道的容量。1.具有一一對應(yīng)確定關(guān)系的無噪信道。這一無噪信道的信道矩陣為

由于具有一一對應(yīng)確定關(guān)系的無噪信道的信道矩陣中，每列只有一個非零元素1，有式（2.76）和（2.77）可知，這種信道的疑義度一定等于零，即有這種無噪信道的信道容量：

這表明，具有一一對應(yīng)確定關(guān)系的無噪信道的信道容量。只取決于信道的輸入符號集的符號數(shù)，是信道本身的特征參量。只有當(dāng)輸入信源X是符號數(shù)為r的等概信源時，具有一一對應(yīng)確定關(guān)系的無噪信道才能達到信道容量。信道的容量，就是信源熵的最大值。2.具有擴散性能的無噪信道。這一無噪信道的信道矩陣是這種無噪信道就是我們前面討論過的發(fā)散性無噪信道。同樣由于信道矩陣，每列只有一個非零元素。由式（2.76）和（2.77）可知，這種發(fā)散性無噪信道的疑義度一定等于零，即有所以，這種發(fā)散性無噪信道的信道容量為3.具有歸并性能的無噪信道。這一無噪信道的信道矩陣是

這種無噪信道就是我們前面討論過的歸并性無噪信道。因為歸并性無噪信道的信道矩陣中的所有元素都是“1”或“0”。由式（2.80）可知，歸并性無噪信道的噪聲熵一定等于零，即有所以，這種歸并性無噪信道的信道容量為

這表明，歸并性無噪信道的信道容量，只取決于信道的輸出符號集的符號數(shù)，是信道本身的特征參量。只有當(dāng)輸入信源是符號數(shù)為的等概信源時，具有一一對應(yīng)確定關(guān)系的無噪信道才能達到信道容量。這1.強對稱離散信道的信道容量第十一節(jié)幾種對稱信道的信道容量

若單符號離散信道的輸入符號集，輸出符號集。每一輸入符號的正確傳輸概率均為，總的錯誤傳輸概率均勻分布在其他個錯誤傳輸?shù)母怕噬?，即個錯誤傳輸概率均為則信道的傳遞特性可表示為其信道矩陣是階對稱矩陣則該信道稱之為強對稱離散信道。令輸入信源的概率分布為，運用熵函數(shù)的對稱性，可對這種對稱信道的噪聲熵進行簡化，即

上式表明，強對稱離散信道的噪聲熵等于信道矩陣中任一行元素組成的熵函數(shù)，其值取決于信道總的錯誤傳遞函數(shù)概率和輸入（輸出）符號數(shù)。可得強對稱信道的信道容量輸出隨機變量的熵的最大值，一定是當(dāng)隨機變量等概分布時達到的最大熵值，所以可以得出強對稱信道的信道容量強對稱信道的幾點特性（1）當(dāng)輸入信源等概分布時，其輸出隨機變量同時呈等概分布。當(dāng)輸入信源達到最大熵值時，即有（2）當(dāng)輸入信源等概分布時，其后驗概率（3）當(dāng)輸入信源等概分布時，特別地當(dāng)強對稱離散信道的傳輸錯誤概率時，有（4）當(dāng)輸入信源等概分布時，信源中的任一符號對隨機變量提供的平均信息量2.對稱離散信道的信道容量

若離散信道的信道矩陣中的每一行都是由同一符號集諸元素的不同排列組成，每一列也都是由同一集合諸元素的不同排列組成，則這種信道稱之為對稱離散信道。例如

對稱離散信道與強對稱離散信道的區(qū)別有以下四點：（1）強對稱離散信道的輸入符號數(shù)與輸出符號數(shù)相等，即，信道矩陣一定是階方陣。而對稱離散信道的輸入符號數(shù)與輸入符號數(shù)不一定相等，其信道矩陣也不一定是方陣。（2）強對稱離散信道的信道矩陣中，行元素集合與列元素集合是同一集合，即。對稱離散信道的信道矩陣的行元素集合與列元素集合不一定是同一集合。（3）強對稱離散信道的信道矩陣的每列之和與每行之和一樣，均為1.對稱離散信道的信道矩陣的每列之和不一定為1.（4）強對稱離散信道的信道矩陣

是一個對稱矩陣，對角線上的元素均是正確傳遞概率，除此之外的所有元素均是錯誤傳遞概率。對稱離散信道的信道矩陣

不一定是對稱矩陣。對稱離散信道的信道容量3.準對稱離散信道的信道容量

若信道矩陣的列可被劃分成若干個互不相交的子集，且每個子集所組成的子陣是行列排列陣，則稱此類信道稱為準對稱離散信道。例如

由于，的行和列都具有可排列性，所有用它們作為子矩陣構(gòu)成的信道矩陣所代表的信道為準對稱離散信道。準對稱離散信道的信道容量當(dāng)輸入信源等概分布時，這個階矩陣對應(yīng)的準對稱信道達到信道容量，其容量值第十二節(jié)可逆矩陣信道的信息容量

若單符號離散信道的輸入符號集，輸出符號集，信道的轉(zhuǎn)移概率為且其信道轉(zhuǎn)移矩陣存在逆矩陣，則該信道稱為可逆矩陣信道。

其交互信息量是輸入信源的概率分布的型凸函數(shù)

通過計算，求解平均交互信息量的極大值，可得到可逆矩陣信道的信道容量

顯然，只有當(dāng)可逆矩陣信道的輸出隨機變量的概率分布等于書中式（2.260）時，信道才能達到上式中所示的信道容量。第十三節(jié)信道容量的迭代計算

由于是信源的概率分布和后驗概率的函數(shù)，即：

而先驗概率和后驗概率不是兩個獨立的變量，其中一個變量發(fā)生變化，另一個變量按

發(fā)生相應(yīng)的變化。

我們可暫且把其中后驗概率當(dāng)作自變量，而把本來要按上式隨之發(fā)生相應(yīng)變化的應(yīng)變量近似地看作固定不變的量。在這種近似處理的情況下，由于和都是固定不變，可得：由于“底”大于1的對數(shù)是型凸函數(shù)，所以具有上凸性。因此，我們就可以在條件的約束下，對變量求型凸函數(shù)的條件極大值，即平均交互信息量的最大值，以及達到最大值的。

為此，做輔助函數(shù)

可得上式表明，當(dāng)變動后驗概率、固定先驗概率時，使平均交互信息量達到最大，即達到信道容量的后驗概率，這就是信源的概率分布為時，給定信道的一般意義下的后驗概率。

由上式可知，當(dāng)變動后驗概率，而固定信源的概率分布時，信道容量為：

在近似處理的情況下，由于和都固定不變，則平均交互信息量就可以看作是先驗概率的函數(shù)：

已知平均交互信息量是信源的概率分布的型凸函數(shù)，可在條件的約束下，對變量求函數(shù)的極大值，即平均交互信息量的最大值，以及達到最大值的。

為此，作輔助函數(shù)得信道容量為（2.283）和（2.295）式分別表示的是，在先驗概率和后驗概率分別在固定不變的假設(shè)前提條件下，分別變動后驗概率和先驗概率的情況下，傳遞概率固定為的給定信道的平均交互信息量達到的最大值，即信道容量。由（2.274）可知，對于傳遞概率固定為的給定信道，在變動后驗概率時，先驗概率不可能固定不變；在變動先驗概率時，后驗概率也不可能不變。迭代算法就是用單獨變動和的方法，逼近和同時變動的實際情況，求得平均交互信息量的最大值，即信道容量的近似值。

當(dāng)n此迭代和n+1此迭代的計算值的差，已經(jīng)小到可以允許的程度，或者已在計算機精度范圍內(nèi)無法顯示時，就可以認為達到了所求容量值。

現(xiàn)在，來證明這種迭代計算的逐級逼近是收斂的。當(dāng)?shù)螖?shù)n足夠大時，有第三章多符號離散信源與信道

對于多符號離散信源來說，若信道的輸入端輸入一個由多個信源符號組成的時間序列所代表的消息，在信道的輸出端相應(yīng)以一定概率輸出一個由同樣個數(shù)的符號組成的時間序列代表的消息，則這種信道稱為多符號離散信道。第一節(jié)離散平穩(wěn)信源的數(shù)學(xué)模型

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

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

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

設(shè)為兩任意時刻，若信源的概率分布與時間無關(guān)，即有則我們把信源稱之為維離散平穩(wěn)信源。

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

來表示。

把維離散平穩(wěn)信源稱之為信源的次擴展信源，其信源空間：其中：這就是描述維離散平穩(wěn)信源的一般的數(shù)學(xué)模型。第二節(jié)離散平穩(wěn)無記憶信源的信息熵

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

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

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

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

由（3.4）式所示的平穩(wěn)性，離散平穩(wěn)無記憶信源的概率分布不隨時間的推移而變化，時刻的隨機變量的概率分布就是離散平穩(wěn)無記憶信源的概率分布。所以，（3.16）式中時刻隨機變量的信息熵均等于離散平穩(wěn)無記憶信源的信息熵，即繼而，可得這說明，離散平穩(wěn)無記憶信源的次擴展信源，即維離散平穩(wěn)無記憶信源的信息熵，等于離散平穩(wěn)無記憶信源的信息熵的倍。這意味著，離散平穩(wěn)無記憶信源的次擴展信源每發(fā)一條消息提供的平均信息量，等于離散無記憶信源每發(fā)一個符號提供的平均信息量的倍。例3.1設(shè)離散平穩(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/16

這樣，可得=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的二次擴展信源=X1×X2每一條消息均有兩個信源符號組成，所以H()的單位是(比特/2信符)第三節(jié)離散平穩(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)有記憶信源。

維離散平穩(wěn)有記憶信源的信源空間可表示為其消息集合是，而其中某一具體消息因為維離散平穩(wěn)有記憶信源的概率分布而個概率分量的和是

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

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

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

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

[X.P]:{p(x):1/44/911/36二維離散平穩(wěn)有記憶信源X=X1×X2中前后兩個符號的關(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的信息熵

比特/信符由二維離散平穩(wěn)有記憶信源X=X1×X2中X1和X2之間的統(tǒng)計依賴關(guān)系，得條件熵

比特/消息即有H(X2/X1)<H(X)條件熵H(X2/X1)比信源X的信息熵H(X)減少了0.672比特/信符，這正是由符號之間有依賴關(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比特/消息平均符號熵H2(X)=H2(X1