《信息論與編碼》課件1第4章

第4章信道與信道容量

4.1信道的描述和分類

4.2信道容量的定義

4.3離散信道的信道容量

4.4離散無記憶信道容量的迭代算法

4.5連續(xù)信道的信道容量

習(xí)題4由前面的討論我們已經(jīng)知道，在一般的信息傳遞過程中，信宿對(duì)信源的了解(即獲取信源發(fā)出的信息）是通過對(duì)信道的輸出Y進(jìn)行觀測(cè)而實(shí)現(xiàn)的。因此，信道是信息傳輸系統(tǒng)的重要部分。在一般的信息傳輸、處理系統(tǒng)的研究中，對(duì)于信道所具有的功能和所包括范圍的理解應(yīng)當(dāng)注意下面兩點(diǎn)。（1）信道承擔(dān)了信息的傳輸、存儲(chǔ)和處理等任務(wù)。通常我們認(rèn)為信道是傳輸信息的物理媒介。但是對(duì)于一般信息系統(tǒng)，在發(fā)出信息的信源與接收信息的信宿之間所進(jìn)行的各種變換與處理，都可以看做此信息系統(tǒng)中信道所具有的功能。例如，地球資源衛(wèi)星遙感信息獲取與處理系統(tǒng)，放置在資源衛(wèi)星上的多光譜掃描設(shè)備采集地球表面地物的反射、輻射電磁波信號(hào)，得到遙感影像數(shù)據(jù)并以無線通信方式傳送，地面接收站接收遙感影像數(shù)據(jù)并記錄在存儲(chǔ)介質(zhì)中，根據(jù)應(yīng)用要求進(jìn)行濾波、增強(qiáng)、分類、識(shí)別，提取各類目標(biāo)信息。如果將反射、輻射電磁波的地球（信息源）與研究人員（信宿）之間看做信道，則此信道中不僅進(jìn)行著信息的傳遞，還包含著對(duì)信息的存儲(chǔ)和處理。因此，在一般的信息系統(tǒng)中，信道除了具有在某種物理媒介中傳遞信號(hào)的功能之外，還應(yīng)當(dāng)包括對(duì)信息的采集、編碼表示、存儲(chǔ)、重建、提取、識(shí)別等多種信息處理功能。（2）信道所包括的范圍可以根據(jù)研究對(duì)象和應(yīng)用條件的不同而確定。在對(duì)信息傳輸系統(tǒng)進(jìn)行分析和研究時(shí)，針對(duì)系統(tǒng)中不同的處理要求和處理方法，往往在分析研究的具體對(duì)象、信號(hào)特征等方面有較大差異。為了使分析更加簡(jiǎn)明，更有針對(duì)性，常將信道在信息系統(tǒng)中所包括的范圍加以適當(dāng)?shù)南薅?。例如，?duì)于一個(gè)多媒體數(shù)據(jù)光盤的刻錄、播放系統(tǒng)，信道的范圍可包括：視頻和音頻數(shù)據(jù)的采集、壓縮編碼，激光盤片刻錄，讀盤、解壓縮恢復(fù)視頻和音頻數(shù)據(jù)，顯示還原圖像、聲音信息的全過程。如果僅考慮播放過程，則信源指數(shù)字媒體作品光盤，信宿為觀看者。因此信道的范圍為：數(shù)據(jù)讀取、解壓縮并按照一定格式重建視頻、音頻信號(hào)等處理過程。顯然，根據(jù)不同的應(yīng)用要求和研究對(duì)象明確信道所包括的范圍，這是我們明確信息系統(tǒng)設(shè)計(jì)的任務(wù)，從而可有針對(duì)性地開展研究與分析工作。在信息理論基礎(chǔ)研究中，信道的主要任務(wù)是以符號(hào)的形式傳輸信息和存儲(chǔ)信息，對(duì)于信道進(jìn)行研究的主要問題是信道中能夠傳送或存儲(chǔ)的最大信息量，即信道容量問題。這一章我們將從信道的統(tǒng)計(jì)特性分析入手，給出信道容量的定義并對(duì)常見信道討論其信道容量的計(jì)算方法。4.1信道的描述和分類

信道是傳輸載荷信息的消息（信號(hào)）的物理媒介或通道。信道的輸入（即信源輸出的消息）是隨機(jī)變量，加之通信系統(tǒng)中存在著隨機(jī)性的噪聲或干擾，因此信道的輸出也是一個(gè)隨機(jī)變量。更一般地講，信源的輸出是廣義的時(shí)間連續(xù)的隨機(jī)信號(hào)或隨機(jī)變量序列，常用隨機(jī)過程來描述，因而信道的輸出也是連續(xù)的隨機(jī)信號(hào)或隨機(jī)變量序列，也要用隨機(jī)過程加以描述。因此，信道的描述和分類都需要從統(tǒng)計(jì)的觀點(diǎn)出發(fā)，用統(tǒng)計(jì)的方法加以分析和表述。4.1.1信道的描述

在前面的討論中，我們已經(jīng)給出了最簡(jiǎn)單的信道，即單符號(hào)的離散信道的數(shù)學(xué)模型。如果信道的輸入是有r種取值可能的隨機(jī)變量X，輸出是有s種取值可能的隨機(jī)變量Y，則信道輸入、輸出之間的統(tǒng)計(jì)關(guān)系可以由轉(zhuǎn)移概率：P(yj|xi)i=1,2,…,r;j=1,2,…,s

(4.1)表示。然而，在實(shí)際的信息傳輸系統(tǒng)中，信源的輸出為一個(gè)隨機(jī)變量序列X=(X1X2…XN)，在信道的輸出端相應(yīng)地為輸出隨機(jī)變量序列Y=(Y1Y2…YN)。如果Xi有r種取值，則X的樣矢量有rN種;如果Yi有s種取值，則Y的樣矢量有sN種。因此信道的數(shù)學(xué)模型應(yīng)當(dāng)由輸入隨機(jī)矢量X和輸出隨機(jī)矢量Y的轉(zhuǎn)移概率關(guān)系P(y|x)來描述。這組rN×sN個(gè)條件概率反映出了輸入隨機(jī)變量與輸出隨機(jī)變量每一對(duì)樣值之間的統(tǒng)計(jì)依賴關(guān)系，反映出了一般信道所具有的最基本的統(tǒng)計(jì)特性。4.1.2信道的分類

根據(jù)信道的輸入、輸出隨機(jī)變量或隨機(jī)矢量的取值類型、它們的相互關(guān)系以及在某些方面的特點(diǎn)，信道可以劃分為不同的類型。

1.按隨機(jī)變量的取值類型劃分

(1)離散信道:信道的輸入、輸出隨機(jī)變量的取值均為離散事件的集合。離散信道有時(shí)也稱做數(shù)字信道。

(2)連續(xù)信道：信道的輸入、輸出隨機(jī)變量X和Y都是連續(xù)事件。這類信道也常稱為模擬信道。

(3)半離散半連續(xù)信道:信道的輸入和輸出隨機(jī)變量空間一個(gè)是離散集，另一個(gè)是連續(xù)集。例如，模/數(shù)轉(zhuǎn)換系統(tǒng)的輸入是連續(xù)的隨機(jī)變量，輸出是離散隨機(jī)變量，稱為輸入連續(xù)、輸出離散的信道。反之，數(shù)/模轉(zhuǎn)換系統(tǒng)是輸入離散、輸出連續(xù)的信道。

2.按信道的輸入、輸出的個(gè)數(shù)劃分

(1)單用戶信道：只有一個(gè)輸入信號(hào)和一個(gè)輸出信號(hào)構(gòu)成的信道。

(2)多用戶信道：信道的輸入或輸出中至少有一個(gè)或兩個(gè)以上事件構(gòu)成的集合。

3.按輸入隨機(jī)變量和輸出隨機(jī)變量的統(tǒng)計(jì)關(guān)系的特點(diǎn)劃分

條件概率P(y|x)具有不同的特點(diǎn)時(shí)，信道的輸入、輸出具有不同的概率轉(zhuǎn)移關(guān)系，信息的傳遞也具有不同的特性。對(duì)于離散信道，根據(jù)條件概率的特點(diǎn)，可分為以下三種情況。

1）無干擾信道無干擾信道中沒有隨機(jī)性的干擾，輸出矢量Y與輸入矢量X之間有確定的對(duì)應(yīng)關(guān)系。這種確定關(guān)系可以是下面三種形式的某一種。（1）無噪無損信道。此時(shí)Y是X的一一對(duì)應(yīng)的函數(shù)，如圖4-1所示，有y=f(x)，即(4.2)信道轉(zhuǎn)移概率呈0、1分布，X、Y之間的互信息為I(X;

Y)=H(X)=H(Y)

(4.3)由于這樣的信道中無隨機(jī)性干擾，因此由Y所得到的關(guān)于X的信息與X或Y的熵相同，即在這樣的信道中不會(huì)損失信息。圖4-1無噪無損信道示例（2）有噪無損信道。此類信道的Y也是X的確定函數(shù)，但是對(duì)于某一個(gè)輸入隨機(jī)矢量X可能會(huì)有多個(gè)輸出隨機(jī)矢量，而相應(yīng)的輸出隨機(jī)矢量只有確定的一個(gè)X與之對(duì)應(yīng)，如圖4-2所示（圖中α+β+γ=1）。圖4-2有噪無損信道示例在有噪無損信道中，由某一個(gè)輸入隨機(jī)矢量xi并不能唯一地確定信道的輸出，表明信道中存在著干擾。但是由于yj與xi有唯一的確定關(guān)系，xi載荷的信息可以由yj全部表示，因此信道中仍然沒有產(chǎn)生信息的損失，即I(X;Y)=H(X)≤H(Y)

(4.4)maxI(X;Y)→maxH(X)

(4.5)

（3）無噪有損信道。此時(shí)Y是X的確定函數(shù)，但是不同的輸入X可能會(huì)有同樣的輸出Y，如圖4-3所示。圖4-3無噪有損信道示例對(duì)于無噪有損信道，由于每一種信道輸入xi只有唯一的一種輸出，因此信道中無隨機(jī)性干擾。但是由于多個(gè)信道輸入xi對(duì)應(yīng)于同一種輸出隨機(jī)矢量yj，因此系統(tǒng)傳輸?shù)男畔?huì)產(chǎn)生損失,即(4.6)

2）有干擾無記憶信道通常，實(shí)際信道的輸入隨機(jī)矢量X與輸出隨機(jī)矢量Y之間并沒有確定的對(duì)應(yīng)關(guān)系，而是某種概率轉(zhuǎn)移關(guān)系。因此，實(shí)際信道中常存在著隨機(jī)性的干擾。如果信道在某一時(shí)刻輸出的隨機(jī)變量?jī)H統(tǒng)計(jì)依賴于即時(shí)的輸入隨機(jī)變量X，與前面時(shí)刻信道的輸入、輸出隨機(jī)變量無關(guān)，則稱這樣的信道為有干擾無記憶信道。滿足離散無記憶信道的充要條件為(4.7)因此有干擾無記憶信道的特性可以由轉(zhuǎn)移概率矩陣［P(y|x)］給出。

3）有干擾有記憶信道有干擾有記憶信道是最一般的信道，信道在某時(shí)刻的輸出隨機(jī)變量不僅與信道即時(shí)的輸入隨機(jī)變量有關(guān)，而且可能與前面時(shí)刻信道的輸入、輸出隨機(jī)變量有關(guān)，即表現(xiàn)為信道的輸出是有記憶的。這時(shí)信道的條件概率不再滿足式(4.7)。處理這類有記憶信道時(shí)，最直觀的方法是把記憶較強(qiáng)的N個(gè)符號(hào)當(dāng)作一個(gè)矢量符號(hào)來處理，而各矢量符號(hào)之間認(rèn)為是無記憶的，這樣就轉(zhuǎn)化成無記憶信道的問題。當(dāng)然，這樣處理一般會(huì)引入誤差，因?yàn)閷?shí)際上第一個(gè)矢量的最后幾個(gè)符號(hào)與第二個(gè)矢量的最前面幾個(gè)符號(hào)是有關(guān)聯(lián)的。N取得越大，誤差將越小。另一種處理方法是把P(y|x)看成Markov鏈的形式，這是有限記憶信道的問題。把信道某時(shí)刻的輸入和輸出序列看成為信道的狀態(tài)，那么，信道的統(tǒng)計(jì)特性可用在已知當(dāng)前時(shí)刻的輸入符號(hào)和前一時(shí)刻信道所處狀態(tài)的條件下，信道的輸出符號(hào)和所處狀態(tài)的聯(lián)合條件概率來描述，即用P(yn,Sn|xn,Sn－1)來描述。在本課程的討論中，我們僅僅考慮簡(jiǎn)單的單符號(hào)離散無記憶信道以及高斯白噪聲波形信道。4.1.3離散無記憶信道

設(shè)離散信道的輸入隨機(jī)變量為X，取值空間為{a1,a2,…,ar},輸出隨機(jī)變量為Y，取值空間為{b1,b2,…,bs}，信道的轉(zhuǎn)移概率為一組條件概率，即P(y|x)=P(y=bj|x=ai)=P(bj|ai)i=1,2,…,r;j=1,2,…,s(4.8)其中，(4.9)由于信道中存在隨機(jī)性干擾，因此有可能使傳輸產(chǎn)生錯(cuò)誤。這種信道干擾對(duì)傳輸?shù)挠绊懣梢杂棉D(zhuǎn)移概率P(bj|ai)（i=1,2,…,r;j=1,2,…,s）來描述。于是，信道矩陣P實(shí)際上是一個(gè)轉(zhuǎn)移概率矩陣，也稱為信道轉(zhuǎn)移概率矩陣。即P={P(bj|ai)=pij,i=1,2,…,r;j=1,2,…,s}(4.10)或

并且滿足。(4.11)

【例4.1】二進(jìn)制對(duì)稱信道（BinarySymmetricalChannel，BSC）如圖4-4所示。在圖4-4中，輸入、輸出隨機(jī)變量X,

Y={0,1}。因?yàn)閞=s=2,所以我們將此類信道稱為二進(jìn)制對(duì)稱信道。圖4-4二進(jìn)制對(duì)稱信道由前面的討論可知，二進(jìn)制對(duì)稱信道的轉(zhuǎn)移概率為(4.12)可以看出，表示單個(gè)符號(hào)無錯(cuò)誤傳輸?shù)母怕剩鴓表示單個(gè)符號(hào)在傳輸中發(fā)生錯(cuò)誤的概率。如果用信道矩陣寫出各轉(zhuǎn)移概率，則有：

此矩陣為一對(duì)稱矩陣，因此這種信道被稱為二進(jìn)制對(duì)稱信道。(4.13)4.1.4高斯白噪聲加性波形信道

信道中的噪聲是高斯白噪聲。具有高斯分布的白噪聲稱為高斯白噪聲。高斯噪聲和白噪聲是從不同的角度來定義的。高斯噪聲是指它的N維概率密度函數(shù)服從高斯分布，并不涉及其功率譜密度的形狀；白噪聲則是就其功率譜密度是均勻分布而言的，而不論它服從什么樣的概率分布。一般情況下，把既服從高斯分布而功率譜密度又是均勻分布的噪聲稱為高斯白噪聲。電阻內(nèi)的熱噪聲就是高斯白噪聲的一個(gè)典型實(shí)例。因此，通信系統(tǒng)中的波形信道常假設(shè)為高斯白噪聲信道。低頻限帶高斯白噪聲有一個(gè)很重要的性質(zhì)，即低頻限帶高斯白噪聲{n′(t)}(均值為零，功率譜密度為N0/2)是通過一個(gè)理想低通濾波器后所得到的。如果理想低通濾波器的帶寬為FHz，那么它的傳遞函數(shù)的頻率響應(yīng)為其他（考慮雙邊譜密度）因此低頻限帶高斯白噪聲的功率譜密度為

其自相關(guān)函數(shù)為其他其中，N0F=Pn′為噪聲平均功率。因?yàn)槠渚禐榱?，所以{n′(t)}的平均功率為

則

這表示，在時(shí)間間隔的兩個(gè)樣本點(diǎn)之間的相關(guān)函數(shù)等于零，即所以各樣本點(diǎn)之間不相關(guān)。也就是說，頻率受限(頻率限制在－F~F之間或限制在0~F之間)的高斯白噪聲{n′(t)}，其在有限T時(shí)間內(nèi)取樣后分解成N=2FT個(gè)連續(xù)型隨機(jī)變量n1、n2、…、nN時(shí)，這些隨機(jī)變量相鄰的時(shí)間間隔為，所以它們的相關(guān)函數(shù)等于零，它們之間是不相關(guān)的。又因?yàn)楦麟S機(jī)變量是高斯概率密度分布，所以隨機(jī)變量之間統(tǒng)計(jì)獨(dú)立。每個(gè)隨機(jī)變量ni(i=1,2,…,N)都是均值為零，方差為的高斯變量。4.2信道容量的定義

4.2.1信息傳輸率在信息傳輸系統(tǒng)中，信道每傳遞一個(gè)符號(hào)所能夠傳遞（載荷）的平均信息量稱為信道的信息傳輸率，記做R。在圖4-5所示的系統(tǒng)中，平均互信息I（X；Y）即為在信道的輸出端接收到符號(hào)集Y后，由每一個(gè)輸出符號(hào)中獲得的關(guān)于信源X的信息量。因此信道的信息傳輸率就是這樣的信息系統(tǒng)中的平均互信息，即R=I(X;Y)比特/符號(hào)(4.14)圖4-5信息傳輸系統(tǒng)模型有時(shí)我們關(guān)心的是信道在單位時(shí)間內(nèi)能夠傳遞多少信息量，或者是在傳輸一個(gè)符號(hào)的時(shí)間內(nèi)信道中平均傳遞的信息量。此時(shí)，若平均傳輸一個(gè)符號(hào)需要t秒，而每一符號(hào)傳送的信息量為I(X;Y)，則信道每秒傳輸?shù)男畔⒘勘銥?/p>

比特/秒(4.15)

通常將Rt稱為信息傳輸速率。4.2.2信道容量由第3章的討論可知，平均互信息I(X;Y)不但與信道的轉(zhuǎn)移概率P(y|x)有關(guān)，而且與信源的概率分布P(x)有關(guān)。因此R=I(X;Y)只表示出了傳輸信源符號(hào)時(shí)信道所傳送的信息率。在研究一個(gè)通信系統(tǒng)時(shí)我們希望能夠找到這樣的量，它能夠反映出給定信道所具有的傳輸信息的能力，即該信道傳輸信息的最大能力。在對(duì)互信息的討論中，我們已經(jīng)知道,對(duì)于I(X;Y)=I(P(x),P(y|x))

(4.16)當(dāng)給定信道轉(zhuǎn)移概率P(y|x)之后，I(X;Y)是信源概率分布P(x)的上凸函數(shù)。因此，對(duì)于一個(gè)信道轉(zhuǎn)移概率為P(y|x)的給定信道，總存在著一種信源（其概率分布為P(x)），使傳輸每一個(gè)符號(hào)平均獲得的信息量最大。這說明對(duì)于每一個(gè)給定的信道，都具有一個(gè)最大的信息傳輸率，這個(gè)最大的信息傳輸率反映出了該信道傳輸信息的極限能力。定義這個(gè)最大的信息傳輸率為該信道的信道容量C，即

(4.17)

如果平均傳輸一個(gè)符號(hào)需要t秒鐘，則給定信道在單位時(shí)間內(nèi)平均傳輸?shù)淖畲笮畔⒘?即信息容量)為比特/秒(4.18)由上述分析和定義可以看出，信道容量C與信源的概率分布P(x)并無函數(shù)關(guān)系，它只是信道轉(zhuǎn)移概率的函數(shù)，只與信道的統(tǒng)計(jì)特性P(y|x)有關(guān)。所以,C是描述信道傳輸信息能力的一個(gè)參數(shù)。信道容量的計(jì)算可以通過找出適當(dāng)?shù)腜(x)，使I(X;Y;P(x))為極大值來完成。

【例4.2】對(duì)于例4.1給出的二進(jìn)制對(duì)稱信道，設(shè)輸入信源的概率空間為

在這樣的通信系統(tǒng)中，可以求出平均互信息為根據(jù)聯(lián)合概率分布可求出輸出符號(hào)Y的邊緣概率為

即

P(y=0)=w(1－p)+(1－w)p

P(y=1)=wp+(1－w)(1－p)

因此

對(duì)于給定的信道，即固定參數(shù)p時(shí)，互信息H(X;Y)是w的上凸函數(shù)，函數(shù)曲線如圖4-6所示。圖4-6二進(jìn)制對(duì)稱信道的互信息由圖4-6可以看出，對(duì)于給定的二進(jìn)制對(duì)稱信道，當(dāng)信源X的概率分布不同時(shí)，在接收端平均由每個(gè)符號(hào)獲得的信息量不同。當(dāng)輸入符號(hào)集X是等概率分布，即

時(shí)，信道輸出端平均每個(gè)符號(hào)才能獲得最大信息量，并且這個(gè)最大的互信息(即此信道的信道容量)為

對(duì)于一般的信道，其信道容量的計(jì)算就是對(duì)互信息I(X;Y)求最大值的問題。由于一般信道的信道容量的計(jì)算比較復(fù)雜，因此本課程主要針對(duì)幾類特殊類型的信道，討論其信道容量的計(jì)算方法。4.3離散信道的信道容量4.3.1對(duì)稱信道的信道容量由前面的討論我們知道，離散信道可以由其轉(zhuǎn)移概率排成的信道矩陣加以描述。因此，若信道矩陣具有不同的特性，那么信道將有不同的特點(diǎn)。首先我們給出信道的可排列性：若矩陣的每一行都由同一符號(hào)集中諸元素的不同排列組成，并且每一列也是由同一符號(hào)集中諸元素的不同排列組成，則稱這樣的矩陣具有可排列性。對(duì)于離散無記憶信道，輸入隨機(jī)變量X∈{x1,x2,…,xr}，輸出隨機(jī)變量Y∈{y1,y2,…,ys}，若其r×s的信道矩陣［P(y|x)］具有可排列性，則將這類信道稱為對(duì)稱信道。例4.3】已知有兩個(gè)信道，其信道矩陣分別為由于這兩個(gè)矩陣都具有可排列性，因此它們所表示的信道是對(duì)稱信道。但是矩陣：不具有可排列性，所以它們所表示的信道不是對(duì)稱信道。若輸入符號(hào)和輸出符號(hào)個(gè)數(shù)相同，都等于r，且信道轉(zhuǎn)移矩陣為(4.19)其中,，則稱此信道為強(qiáng)對(duì)稱信道或均勻信道。這類信道總的錯(cuò)誤概率為p，對(duì)稱地分配給r－1個(gè)輸出符號(hào)，它是離散對(duì)稱信道的一個(gè)特例，其信道矩陣中各列之和也等于1。二元對(duì)稱信道就是r=2的強(qiáng)對(duì)稱信道。下面我們討論離散對(duì)稱信道的信道容量。設(shè)信道的轉(zhuǎn)移概率矩陣［P(y|x)］［x］具有對(duì)稱性，在考慮信道的輸入X與輸出Y之間的互信息時(shí)，設(shè)有一個(gè)對(duì)稱信道，其輸入X∈{x1,x2,…,xr}，輸出Y∈{y1,y2,…,ys}，r行、s列的信道矩陣［P(yj|xi)］具有對(duì)稱性。我們先分析一下此時(shí)條件熵的特點(diǎn)。(4.20)其中:

(4.21)是由［P(yj|xi)］中第i行元素構(gòu)成的熵函數(shù)。因?yàn)椋跴(yj|xi)］中的每一行都由的不同排列所構(gòu)成，所以若以i為參變量，則由對(duì)稱性可知：是與i無關(guān)的常量。因此

(4.22)條件熵H(Y|X)與信源X的分布P(xi)無關(guān)。此時(shí)

根據(jù)信道容量的定義，應(yīng)當(dāng)有

(4.23)此時(shí)，當(dāng)信源概率分布P(x)改變時(shí)只有隨機(jī)變量Y的熵H(Y)隨之改變，互信息I(X;Y)最大值的計(jì)算便轉(zhuǎn)化為求H(Y)的最大值問題。因?yàn)閅∈{y1,y2,…,ys}，所以由最大熵定理有：H(Y)≤logs當(dāng)且僅當(dāng)時(shí)等式成立。因此，應(yīng)當(dāng)找出使時(shí)信源的概率分布。由對(duì)稱信道的特點(diǎn)可知，［P(yj|xi)］的每一列都是由的不同排列構(gòu)成的,即有：

常量j=1,2,…,s

若信源X為等概率分布,即

i=1,2,…,r則常數(shù)由概率分布律可知，此時(shí)

，所以當(dāng)信源X為等概率分布時(shí)，對(duì)稱信道具有最大的信息傳輸率。因此，對(duì)稱信道的信道容量為

比特/符號(hào)(4.24)

【例4.4】設(shè)某信道為強(qiáng)對(duì)稱信道，其轉(zhuǎn)移概率矩陣為式(4.19)。根據(jù)其信道矩陣的特點(diǎn)，可知其信道容量為(4.25)對(duì)于強(qiáng)對(duì)稱信道，p表示總的錯(cuò)誤傳輸概率，而表示正確傳輸概率。顯然，強(qiáng)對(duì)稱信道在其輸入為等概率分布時(shí)達(dá)到其信道容量C。由式(4.24)可知，對(duì)于r=2的二進(jìn)制對(duì)稱信道，其信道容量為C=1－H(p)=1+plogp+(1－p)log(1－p)比特/符號(hào)4.3.2準(zhǔn)對(duì)稱信道的信道容量

設(shè)信道的輸入、輸出隨機(jī)變量取值為：X∈{x1,x2,…,xr}，Y∈{y1,y2,…,ys}，已知r×s的信道概率轉(zhuǎn)移矩陣P=［P(yj|xi)］不具有可排列性。但是，如果［p(yj|xi)］的s列可以劃分為m個(gè)不相交的子集(m<s)，各子集分別有s1,s2,…,sm個(gè)元（其中s1+s2+…+sm=s），由sk列組成的子矩陣Pk(k=1,2,…,m)都具有可排列性，則稱所表示的信道是準(zhǔn)對(duì)稱信道。由準(zhǔn)對(duì)稱信道的定義可以看出，具有可排列性的子矩陣Pk是通過對(duì)P的劃分而構(gòu)成的，因此P的每一行是具有可排列性的,即P中的每一行元素都是由同一符號(hào)集的不同排列而構(gòu)成的。

【例4.5】已知某信道的轉(zhuǎn)移概率矩陣為雖然P的每一行中的元素具有可排列性，但是列不滿足其他列元素重排的要求。故矩陣P不具有可排列性，此信道不是對(duì)稱信道。但是若將此矩陣的六列劃分為兩個(gè)不相交的子集，即s1：{2,5}s2：{1,3,4,6}則由每一子集構(gòu)成的子矩陣:都具有可排列性。因此雖然這個(gè)信道不是對(duì)稱信道，但是滿足準(zhǔn)對(duì)稱信道的要求，是一個(gè)準(zhǔn)對(duì)稱信道。由于準(zhǔn)對(duì)稱信道的信道矩陣P具有行可排列性，因此可以寫出：

準(zhǔn)對(duì)稱信道的信道容量應(yīng)滿足：(4.27)(4.26)因?yàn)镻各列不滿足可排列性，所以對(duì)于任意一種信源概率分布P(x)，都不可能使信道輸出Y呈現(xiàn)為等概率分布，對(duì)應(yīng)的信源概率分布P(x)需要進(jìn)一步分析才能得到。已知：根據(jù)前面矩陣劃分的關(guān)系，我們也將求和式劃分為m項(xiàng)，即

(4.28)其中,s1+s2+…+sm=s。對(duì)于式（4.28）中的第k項(xiàng)，集合sk(k=1,2,…,m)內(nèi)的符號(hào)yj(j=1,2,…,sk)發(fā)生概率的平均值為

顯然有

根據(jù)lnx≤x－1(x>0)，有：即如果每一個(gè)子集的信道輸出符號(hào)發(fā)生的概率相同，則可達(dá)到其最大值－skPk(y)lnPk(y)。因?yàn)樽泳仃嘝k是可排列的，即每一行元素均由的不同排列構(gòu)成，而且每一列元素也是由同一集合的不同排列構(gòu)成的，所以當(dāng)信源符號(hào)X為等概率分布，即時(shí)，一定能將使子集合sk中的輸出符號(hào)yj具有相同的概率分布，即式(4.28)中的每一內(nèi)和式均達(dá)到其最大值。于是我們得到了準(zhǔn)對(duì)稱信道的信道容量：

即準(zhǔn)對(duì)稱信道的信道容量等于等概率輸入的互信息。(4.29)

【例4.6】已知某信道的轉(zhuǎn)移概率如表4-1所示，計(jì)算此信道的信道容量。表4-1P(y|x)

解：此信道的信道矩陣為

P不滿足可排列性，故此信道不是對(duì)稱信道。但是若將矩陣的四個(gè)列分為兩個(gè)不相交的子集：s1：{1,3}s2：{2,4}則由每一子集構(gòu)成的子矩陣：都是可排列的。由此可知，此信道是準(zhǔn)對(duì)稱信道。根據(jù)準(zhǔn)對(duì)稱信道的信號(hào)的信道容量計(jì)算關(guān)系，取輸入隨機(jī)變量X為等概率分布，即，此時(shí)(x,y)的聯(lián)合概率分布及Y的邊緣概率分布如表4-2所示。表4-2P(x,y)由Y的邊緣概率分布可看出，在輸入X等概率分布時(shí)，雖然準(zhǔn)對(duì)稱信道的輸出Y不是等概率分布，但是對(duì)于每個(gè)子集s1和s2，子集中的符號(hào)是等概率的。由前面的分析可知，每個(gè)子集符號(hào)的概率均相等，保證了準(zhǔn)對(duì)稱信道輸出隨機(jī)變量Y的熵H（Y）達(dá)到其最大量。此時(shí)為又可求出因此，此準(zhǔn)對(duì)稱信道的信道容量為4.3.3可逆矩陣信道的信道容量

如果信道的輸入和輸出有相同的符號(hào)個(gè)數(shù)，即X∈{x1,x2,…,xn}Y∈{y1,y2,…,yn}且信道的矩陣［P(yj|xi)］=P的逆矩陣P－1存在，則此信道稱為可逆矩陣信道。對(duì)于給定的信道，輸入概率分布P(xi)改變時(shí)平均互信息I(X;Y)也將隨之改變。由于I(X;Y)是輸入概率分布的上凸函數(shù)，因此一定存在一個(gè)極值點(diǎn)，使I(X;Y)達(dá)到其最大值。根據(jù)信道容量的定義，這個(gè)極大值就是給定信道的信道容量。對(duì)于可逆矩陣信道，可以在給定的條件下運(yùn)用拉格朗日乘子法計(jì)算互信息I(X;Y)的條件極值求出其信道容量。設(shè)給定一個(gè)可逆矩陣信道，n×n的信道矩陣為為求出I(X;Y)在條件下的極值，構(gòu)造一個(gè)輔助函數(shù)φ：因?yàn)?，j=1,2,…,n,所以P(yj)也是輸入概率分布P(xi)的函數(shù)，并且有偏微分：為了計(jì)算互信息的條件極值，將輔助函數(shù)對(duì)輸入概率分布P(xi)求偏導(dǎo)，則有：因?yàn)樗?/p>

為了求出條件極值，令

即

(4.30)

顯然，式(4.30)為一個(gè)由n個(gè)方程構(gòu)成的方程組。求解此方程組可以得到I(X;Y)的條件極值點(diǎn)，即使I(X;Y)在滿足的條件下達(dá)到其最大值的一組輸入極值點(diǎn)概率分布P(x1),P(x2),…，P(xn)。在這組極值點(diǎn)概率分布下，互信息I(X;Y)即為給定信道的信道容量。下面我們計(jì)算在這組極值點(diǎn)輸入概率分布下的互信息I(X;Y)。對(duì)于式(4.30)表示的由n個(gè)方程構(gòu)成的方程組，將第i個(gè)方程的兩端同乘以極值點(diǎn)概率分布P(xi)，即

(4.31)將個(gè)方程的左、右兩端分別相加（相當(dāng)于將式(4.31)的左、右兩端分別對(duì)i=1,2,…,n求和），即

(4.32)顯然,式(4.32)左端即為互信息I(X;Y)的表達(dá)式。由于此時(shí)的互信息I(X;Y)是在使其達(dá)到最大值的極值點(diǎn)概率分布下得到的，即式(4.32)的左端為

因此，由信道容量的定義可知，所給信道的信道容量滿足下面關(guān)系式:

C=loge+λ

(4.33)在這個(gè)信道容量關(guān)系式中，由于λ為待定常數(shù)，因此我們還不能由此得到信道容量的值，需要利用給定信道的特性作進(jìn)一步的分布和推導(dǎo)。對(duì)于給定的信道，已知X、Y的離散集合有相同數(shù)目的元，信道轉(zhuǎn)移概率構(gòu)成的信道矩陣為一個(gè)方陣。在下面的分析中，將信道矩陣簡(jiǎn)單記做：其中,P(yj|xi)=pij表示信道矩陣的第i行、第j列元素。由于此信道是可逆矩陣信道，因此信道矩陣P的逆矩陣P－1存在。我們將該信道矩陣的n×n逆矩陣表示為P－1=R=［rkj］k,j=1,2,…,n其中,rkj為矩陣中的第k行、第j列元素。已知R與P是互逆的，它們滿足：由此互逆關(guān)系可以看出，R的第k行與P的第j列對(duì)應(yīng)元素的乘積并求和為

依據(jù)概率分布律應(yīng)有：因此應(yīng)用給定可逆矩陣信道的信道矩陣及其逆矩陣具有的這些關(guān)系，我們可做進(jìn)一步分析。將式(4.30)的兩端同乘以rki，即有：

上式左、右兩端分別對(duì)i=1,2,…,n求和：根據(jù)式(4.33)所給出的關(guān)系，可得到：

(4.34)在式(4.34)中，只有第二項(xiàng)中的P(yj)是未知量。應(yīng)用上述可逆矩陣信道的關(guān)系，該式第二項(xiàng)為則式(4.34)為此處我們?nèi)?duì)數(shù)底為2，并對(duì)上式兩端分別取以2為底的指數(shù)運(yùn)算，便可得到輸出Y的概率分布，即

(4.35)其中,k=1,2,…,n。式(4.35)也是一個(gè)由n個(gè)方程構(gòu)成的方程組。若將這n個(gè)方程的左、右兩端分別對(duì)k=1,2,…,n求和：

則得到：取以2為底的對(duì)數(shù)，得到：(4.36)此即為給定的可逆矩陣信道的信道容量，單位為比特/符號(hào)。

【例4.7】計(jì)算圖4-7所示信道的信道容量。

解：由圖4-7中所示信道轉(zhuǎn)移概率關(guān)系，可寫出信道的信道矩陣為

首先，我們判斷此信道是否為可逆矩陣信道，因圖4-7其伴隨矩陣為

于是得到信道矩陣P的逆陣為由于此信道矩陣存在，因此此信道是可逆矩陣信道。其信道容量可以由式(4.36)給出的計(jì)算關(guān)系得到：因此此即所給可逆矩陣信道的信道容量。對(duì)于可逆矩陣信道，在使用式(4.36)求出其信道容量C之后，由式(4.35)可以求出輸出符號(hào)Y的概率分布，即

再利用

,j=1,2,…,n的關(guān)系，可以求出在此時(shí)的信道容量C，即互信息I(X;Y)為最大值時(shí)所對(duì)應(yīng)的輸入隨機(jī)變量X的概率分布P(xi)，i=1,2,…,n。如果求出的輸入概率分布P(xi)滿足概率分布率要求，即0≤P(xi)≤1（的條件在輔助函數(shù)的構(gòu)造中已經(jīng)考慮）則表明上述計(jì)算是合理的，得出的信道容量C有效。但是，在可逆信道的信道容量計(jì)算中，輔助函數(shù)φ的構(gòu)造并未對(duì)0≤P(xi)≤1，i=1,2,…,n加以限制，計(jì)算信道容量C后得出的輸入概率分布中可能會(huì)有某些輸入符號(hào)的概率小于零。這表明在的條件下，

I(X;Y)極大值所對(duì)應(yīng)的輸入概率分布不滿足概率分布律的要求，所得到的C并不是給定信道的信道容量，采用這種信道容量的計(jì)算方法失效。上面我們對(duì)幾種特殊的信道討論了其信道容量的計(jì)算方法。對(duì)于更一般的情況，信道矩陣不一定是可逆的，信道的輸入與輸出符號(hào)的數(shù)目也并不一定相同。因此這些信道容量的計(jì)算方法所適用的范圍有明顯的限制。對(duì)于一般的信道，信道容量的計(jì)算是非常復(fù)雜的。這種計(jì)算的復(fù)雜性由信道容量的定義：

即可看出。這種最大值從互信息I(X;Y)與輸入概率分布的上凸關(guān)系來看一定存在，但對(duì)于一個(gè)任意的信道，在I(X;Y)與P(x1),P(x2),…,P(xn)所構(gòu)成的多元關(guān)系中，根據(jù)給定信道的特點(diǎn)求出這個(gè)最大的互信息顯然是困難的，幾乎不易得出正確的答案。4.4離散無記憶信道容量的迭代算法對(duì)于一般的離散無記憶信道而言，信道容量的計(jì)算比較復(fù)雜，可以用迭代算法實(shí)現(xiàn)。設(shè)離散無記憶信道的輸入符號(hào)集和相應(yīng)分布為X={x1,x2,…,xr}{P(xi),i=1,2,…,r}輸出符號(hào)集和相應(yīng)分布為

Y={y1,y2,…,ys}{P(yj),j=1,2,…,s}

信道轉(zhuǎn)移概率矩陣為

信道示意圖如圖4-8所示。圖4-8信道模型信道容量：

其中:(4.37)(4.39)(4.38)其中,Q(xi|yj)(i=1,2,…,r;j=1,2,…,s)稱為反條件概率，由［X,P］和信道轉(zhuǎn)移概率矩陣確定，可以設(shè)想為原信道的反向信道，如圖4-9所示。圖4-9反向信道該反向信道的轉(zhuǎn)移概率矩陣為

且滿足:

引入反向信道的概念后，平均互信息量I(X;Y)可以看做是輸入概率分布P(x)和反向信道轉(zhuǎn)移概率P(x|y)的函數(shù)，可記為：F{P(x),P(x|y)}。當(dāng)P(y)給定時(shí)，F(xiàn){P(x),P(x|y)}達(dá)到最大的分布P(x|y)由下述定理確定。

定理4.1

對(duì)任意P(x|y)，有I(X;Y)≥F{P(x),P(x|y)}

(4.40)當(dāng)且僅當(dāng)

時(shí)等式成立。證明：令

則當(dāng)且僅當(dāng)

P(xi|yj)=Q(xi|yj)i=1,2,…,r;j=1,2,…,s

時(shí)等式成立,而因此有證畢。上述定理說明：在給定輸入分布P(x)的條件下，可求得使F{P(y),P(x|y)}達(dá)到最大值的反向轉(zhuǎn)移概率分布P*(xi|yj)(i=1,2,…,r;j=1,2,…,s),即

最佳分布為P*(xi|yj)=Q(xi|yj)i=1,2,…,r;j=1,2,…,s因此(4.41)固定轉(zhuǎn)移概率P(x|y)時(shí)，F(xiàn){P(x),P(x|y)}可以對(duì)輸入分布P(x)求最大值。一般而言，信道容量C是在

條件下求I(X;Y)的最大值，故可用Lagrange乘子法。定義函數(shù):

顯然,f(P(x))和I(X;Y)具有相同的極大值。

又因?yàn)樗云渲?i=1,2,…,r?？紤]，令偏導(dǎo)數(shù)等于0得:

(4.42)設(shè)該方程組有一組解：P*(x1),P*(x2),…,P*(xr),滿足，求得極值為

C=λ+loge

(4.43)

定理4.2

當(dāng)且僅當(dāng)P(X)滿足

(4.44)時(shí)，g(P(x))=I(X;Y)達(dá)到最大值（信道容量）。

證明：

(4.45)先證充分性。由于

即

滿足式(4.42)，故P(x)為極值點(diǎn)P*(x)，得證。再證必要性。由于P(x)為極值點(diǎn)，因此它為L(zhǎng)agrange乘子法求偏導(dǎo)數(shù)的方程組中的一個(gè)解，式(4.42)成立，從而有

從而式(4.44)成立。同理可證，據(jù)式(4.37)，形式上固定P(x|y)，分布P(x)使F(P(x),P(x|y))達(dá)到最大值的充要條件為

而不妨取log的底為e，則

(4.46)

由于約束條件：因此

(4.47)這樣，通過交替地固定P(x)和P(x|y)，利用式(4.39)和式(4.47)就可以求得使F(P(x),P(x|y))為最大的分布，從而有以下的迭代算法。設(shè)初始分布為P(0)(x)，一般可取等概率分布，即

(4.48)令k=0,1,2,…為迭代序號(hào)，則迭代公式為(4.49)(4.50)(4.51)迭代步驟如下：

(1)取初始分布P(0)(x)。

(2)根據(jù)式(4.49)計(jì)算P(k)(xi|yj)(i=1,2,…,r;j=1,2,…,s)。

(3)根據(jù)式(4.50)計(jì)算P(k+1)(xi)(i=1,2,…,r)。

(4)根據(jù)式(4.51)計(jì)算C(k+1)。

(5)若|C(k+1)－C(k)|<δ，則轉(zhuǎn)向步驟（7）。

(6)令k=k+1，轉(zhuǎn)向步驟（2）。

(7)輸出P(k+1)(xi)和C(k+1)。該迭代算法的收斂性由下述定理給出。

定理4.3

對(duì)上述迭代算法有(4.52)等價(jià)表示：

(4.53)

證明：不妨令

(4.54)則而據(jù)式(4.54)有

設(shè)P*(x)是達(dá)到信道容量的最佳分布，即其中:(4.55)令

(4.56)(4.57)則式(4.55)可寫成

(4.58)由式(4.56)和式(4.57)可知：h*和h(k)分別是對(duì)應(yīng)最佳輸入分布和k步迭代時(shí)輸入分布值的輸出符號(hào)分布函數(shù)，故有從而

又因?yàn)?/p>

C≥C(k+1)

k=0,1,2,…

所以不等式右側(cè)與N無關(guān)，所以級(jí)數(shù)是收斂級(jí)數(shù)，即

證畢。該定理表明，迭代算法一定能得到任意接近信道容量的解，接近的程度取決于第5步中的值δ；算法的收斂速度與初始分布的選擇有關(guān)，初始分布越接近最佳分布，收斂速度越快。當(dāng)初始分布選為等概率分布時(shí)，有上式表明，在k足夠大后，C(k)以1/N的速度逼近信道容量C。4.5連續(xù)信道的信道容量和離散信道一樣，對(duì)固定的連續(xù)信道有一個(gè)最大的信息傳輸速率，稱之為信道容量，它也是信道可靠傳輸?shù)淖畲笮畔鬏斔俾?。一般連續(xù)信道的信道容量為

其中,p(x)為輸入矢量X的概率密度函數(shù)。比特/N個(gè)自由度(4.59)一般波形信道的信道容量為(4.60)其中,p(x)為輸入矢量X的概率密度函數(shù)。比特/秒若研究的是加性信道，則已知在加性信道中的信道傳輸概率密度函數(shù)就是噪聲的概率密度函數(shù)。條件熵h(Y|X)（即噪聲熵）就是噪聲源的熵h(n)。因此，一般多維加性連續(xù)信道的信道容量為

比特/N個(gè)自由(4.61)

又由式(4.60)得一般加性波形信道的信道容量為(4.62)比特/秒式(4.61)和式(4.62)中h(n)與輸入矢量X的概率密度函數(shù)p(x)無關(guān)（因輸入矢量X與噪聲矢量n統(tǒng)計(jì)獨(dú)立）。所以，求加性信道的信道容量就是求某種發(fā)送信號(hào)的概率密度函數(shù)使接收信號(hào)的熵h(Y)最大。由于在不同限制條件下，連續(xù)隨機(jī)變量有不同的最大連續(xù)差熵值,因此，由式(4.61)和式(4.62)可知，加性信道的信道容量C取決于噪聲的統(tǒng)計(jì)特性和輸入隨機(jī)矢量X所受的限制條件。一般實(shí)際信道中，無論輸入信號(hào)還是噪聲，它們的平均功率或能量總是有限的。所以本節(jié)只討論在平均功率受限的條件下，各種連續(xù)信道和波形信道的信道容量。4.5.1單符號(hào)高斯加性信道

單符號(hào)高斯加性信道是指信道的輸入和輸出都是取值連續(xù)的一維隨機(jī)變量，而加入信道的噪聲是加性高斯噪聲。設(shè)信道疊加的噪聲n是均值為0，方差為σ2的一維高斯噪聲，求得噪聲信源的熵為

(4.63)高斯加性信道的信道容量為

(4.64)式(4.64)中，只有h(Y)與輸入