第一章信息論基礎(chǔ)

第1章信息論基礎(chǔ)

第1章信息論基礎(chǔ)

內(nèi)容提要信息論是應(yīng)用近代概率統(tǒng)計(jì)方法研究信息傳輸、交換、存儲(chǔ)和處理的一門學(xué)科，也是源于通信實(shí)踐發(fā)展起來(lái)的一門新興應(yīng)用科學(xué)。本章首先引出信息的概念，簡(jiǎn)述信息傳輸系統(tǒng)模型的各個(gè)組成部分，進(jìn)而討論離散信源和離散信道的數(shù)學(xué)模型，簡(jiǎn)單介紹幾種常見(jiàn)的離散信源和離散信道。

1948年香農(nóng)在BellSystemTechnicalJournal上發(fā)表了《AMathematicalTheoryofCommunication》。

通信的基本問(wèn)題是在彼時(shí)彼地精確地或近似地再現(xiàn)此時(shí)此地發(fā)出的消息。1.1信息的概念物質(zhì)、能量和信息是構(gòu)成客觀世界的三大要素。信息是物質(zhì)和能量在空間和時(shí)間上分布的不均勻程度，或者說(shuō)信息是關(guān)于事物運(yùn)動(dòng)的狀態(tài)和規(guī)律。

通信系統(tǒng)中形式上傳輸?shù)氖窍?，?shí)質(zhì)上傳輸?shù)氖切畔ⅲ⒅邪畔?，消息是信息的載體。信息論是研究信息的基本性質(zhì)及度量方法，研究信息的獲取、傳輸、存儲(chǔ)和處理的一般規(guī)律的科學(xué)。

信息：信息是任何隨機(jī)事件發(fā)生后所包含的內(nèi)容（信息量．特點(diǎn)）

消息：消息是信息的載體（互聯(lián)網(wǎng)上的文字與圖像）信號(hào)：信號(hào)是消息的載體（調(diào)制原因）三者之間的關(guān)系:信息不等于消息，消息中包含信息，是信息的載體，信號(hào)攜帶消息，是消息的載體．

1.1信息的概念

20世紀(jì)20年代奈奎斯特（Nyquist，H．）和哈特萊（Hartley，L．V．R．）提出了信息的定義

1924年奈奎斯特解釋了信號(hào)帶寬和信息速率之間的關(guān)系

1928哈特萊最早研究了通信系統(tǒng)傳輸信息的能力，給出了信息度量方法

1936年阿姆斯特朗（Armstrong）提出了增大帶寬可以使抗干擾能力加強(qiáng)

1941～1944年香農(nóng)對(duì)通信和密碼進(jìn)行深人研究，用概率論的方法研究通信系統(tǒng)，揭示了通信系統(tǒng)傳遞的對(duì)象就是信息，并對(duì)信息給以科學(xué)的定量描述，提出了信息熵的概念。指出通信系統(tǒng)的中心問(wèn)題是在噪聲下如何有效而可靠地傳送信息以及實(shí)現(xiàn)這一目標(biāo)的主要方法是編碼等。香農(nóng)因此成為信息論的奠基人。

1.2信息論與編碼技術(shù)的發(fā)展簡(jiǎn)史

50年代信息論在學(xué)術(shù)界引起了巨大的反響

60年代信道編碼技術(shù)有較大進(jìn)展，使它成為信息論的又一重要分支；信源編碼的研究落后于信道編碼。香農(nóng)1959年的文章(Codingtheoremsforadiscretesourcewithafidelitycriterion)系統(tǒng)地提出了信息率失真理論，它是數(shù)據(jù)壓縮的數(shù)學(xué)基礎(chǔ)，為各種信源編碼的研究奠定了基礎(chǔ)

到70年代，有關(guān)信息論的研究，從點(diǎn)與點(diǎn)間的單用戶通信推廣到多用戶系統(tǒng)的研究。1972年蓋弗（Caer）發(fā)表了有關(guān)廣播信道的研究，以后陸續(xù)有關(guān)于多接入信道和廣播信道模型的研究，但由于這些問(wèn)題比較難，到目前為止，多用戶信息論研究得不多，還有許多尚待解決的課題。

對(duì)于信息論的研究，一般劃分為三個(gè)不同的范疇：廣義信息論，包括信息論在自然和社會(huì)中的新的應(yīng)用，如模式識(shí)別、機(jī)器翻譯、自學(xué)習(xí)自組織系統(tǒng)、心理學(xué)、生物學(xué)、經(jīng)濟(jì)學(xué)、社會(huì)學(xué)等一切與信息問(wèn)題有關(guān)的領(lǐng)域。實(shí)用信息論，研究信息傳輸和處理問(wèn)題，也就是狹義信息論方法在調(diào)制解調(diào)、編碼譯碼以及檢測(cè)理論等領(lǐng)域的應(yīng)用。狹義信息論，即通信的數(shù)學(xué)理論，主要研究狹義信息的度量方法，研究各種信源、信道的描述和信源、信道的編碼定理。1.3信息傳輸系統(tǒng)

通信的基本問(wèn)題是在彼時(shí)彼地精確地或近似地再現(xiàn)此時(shí)此地發(fā)出的消息。各種通信系統(tǒng)，一般可概括為圖1.1所示的統(tǒng)計(jì)模型：

干擾源

信道信道譯碼器信道編碼器信源譯碼器信源編碼器信宿信源等效信源等效信宿等效干擾信道圖1-1信息傳輸系統(tǒng)模型

這個(gè)模型包括以下五個(gè)部分：3.信道信道是信息傳輸和存儲(chǔ)的媒介。4.譯碼器譯碼是編碼的逆變換，分為信道譯碼和信源譯碼。5.信宿信宿是消息的接收者。2.編碼器編碼器是將消息變成適合于信道傳送的信號(hào)的設(shè)備。1.信源信源是產(chǎn)生消息的源。編碼器信源編碼器，提高傳輸效率信道編碼器，提高傳輸可靠性1.4香農(nóng)信息的定義

三個(gè)基本概念樣本空間:概率測(cè)度:概率空間:對(duì)于離散情況下概率空間1.先驗(yàn)概率：表示選擇符號(hào)作為消息的概率2.香農(nóng)信息量(自信息量)：（圖像）3.后驗(yàn)概率：表示接受端收到的消息為發(fā)送端收到的消息是4.互信息（收信者獲得的信息量）：2.香農(nóng)信息量：（圖像）補(bǔ)充例題1.3

離散信源及其數(shù)學(xué)模型信源是產(chǎn)生消息的源，根據(jù)X的不同情況，信源可分為以下類型：

根據(jù)信源的統(tǒng)計(jì)特性，離散信源又分為兩種：離散信源消息集X為離散集合。波形信源時(shí)間連續(xù)的信源。連續(xù)信源時(shí)間離散而空間連續(xù)的信源。無(wú)記憶信源

X的各時(shí)刻取值相互獨(dú)立。有記憶信源

X的各時(shí)刻取值互相有關(guān)聯(lián)。1.3.1離散無(wú)記憶信源

離散無(wú)記憶信源(DiscreteMemorylessSource，簡(jiǎn)記為DMS)輸出的是單個(gè)符號(hào)的消息，不同時(shí)刻發(fā)出的符號(hào)之間彼此統(tǒng)計(jì)獨(dú)立，而且符號(hào)集中的符號(hào)數(shù)目是有限的或可數(shù)的。離散無(wú)記憶信源的數(shù)學(xué)模型為離散型的概率空間，即：

p(ai

)：信源輸出符號(hào)消息ai的先驗(yàn)概率;

滿足：0

p(ai)1，1

in

聯(lián)合自信息量:聯(lián)合熵

滿足：0

p(aibj)1，1

in,1

jm,

§2.1單符號(hào)離散信源四、互信息量和條件互信息量⒈

互信息量的概念在通信系統(tǒng)中，發(fā)送端發(fā)出的信息經(jīng)有噪信道后，在接收端收到的信息量的多少要用互信息量來(lái)描述。設(shè)X為信源發(fā)出的離散消息集合；Y為信宿收到的離散消息集合；信源發(fā)出的消息，經(jīng)過(guò)有噪聲的信道傳遞到信宿；其間信源X和信宿Y的數(shù)學(xué)模型為：

在系統(tǒng)中，若信道是無(wú)噪的，收到信息bj后，即可獲得信息量I(aj)。若信道存在噪聲，在接收端收到bj后重新估計(jì)信源發(fā)出的各個(gè)消息→p(ai∣bj)。我們稱之為后驗(yàn)概率。0≦p(ai)≦1∑p(ai)=10≦p(bj)≦1∑p(bj)=1因此，我們稱：先驗(yàn)概率：信源發(fā)出消息ai的概率P(ai)。后驗(yàn)概率：信宿收到消息bj后,推測(cè)信源發(fā)出ai

的概率，即條件概率p(ai

∣bj)。⒉

互信息量的定義

ai的后驗(yàn)概率與先驗(yàn)概率之比的對(duì)數(shù)為bj對(duì)ai的互信息量。用I(ai;bj)表示?；バ畔⒘康扔谧孕畔⒘繙p去條件自信息量互信息有兩方面的含義：表示事件bj出現(xiàn)前后關(guān)于事件ai的不確定性減少的量；事件bj出現(xiàn)以后信宿獲得的關(guān)于事件ai的信息量。對(duì)互信息量的理解

⑴觀察者站在輸出端

I(ai;bj)=–logp(ai)–[–logp(ai|bj)]=I(ai)–I(ai|bj)I(ai)

：在

bj

一無(wú)所知的情況下ai

存在的不確定度；I(ai|bj)：收到bj

后對(duì)ai

仍然存在的不確定度；I(ai;bj)：收到bj

前和收到bj

后不確定度被消除的部分獲得信息量信道aibj⑵觀察者站在輸入端I(bj;ai)=logp(bj)–[–logp(bj|ai)]=I(bj)–I(bj|ai)

觀察者得知輸入端發(fā)出ai

前、后對(duì)輸出端出現(xiàn)bj

的不確定度的差。信道aibj⑶觀察者站在通信系統(tǒng)總體立場(chǎng)上互信息等于通信前后不確定度的差值通信前：X和Y之間沒(méi)有任何關(guān)系，即X、Y統(tǒng)計(jì)獨(dú)立。即

p(xi

yj)=p(xi)p(yj)，先驗(yàn)不確定度通信后：p(xi

yj)=p(xi)p(yj

|xi

)=p(yj)p(xi

|yj)，后驗(yàn)不確定度⒊互信息量的性質(zhì)1)互信息的對(duì)稱性2)互信息可為零物理含義：系統(tǒng)中干擾極大3)互信息可為正值或負(fù)值4)任何兩個(gè)事件之間的互信息不可能大于其中任一事件的自信息信息量的丟失，不確定性增加⒋條件互信息量定義：聯(lián)合集XYZ中，在給定ck的條件下ai與bj之間的互信息量定義為條件互信息量：在XYZ聯(lián)合集上，還有ai與bjck之間的互信息量由前式可得：此外，還有：將上式兩邊相加有：根據(jù)互易性有：例：有一信源U包含8個(gè)消息0—7，為了便于在二進(jìn)制信道上傳送，將它們編為三位二進(jìn)碼，信源的先驗(yàn)概率及相應(yīng)的代碼如下：試求：⑴填上表格中的后三列⑵x0與各消息的互信息量

⑶在收到（給定）x0條件下，y1與各消息的互信息量。

⑷

在收到（給定）x0y1條件下，z1與U3消息的互信息量.

⑸

收到整個(gè)代碼組x0y1z1出現(xiàn)后提供的有關(guān)消息U3的互信息量。信源消息二進(jìn)制代碼先驗(yàn)概率收到0后的后驗(yàn)概率收到01后的后驗(yàn)概率收到011后的后驗(yàn)概率0（U0）000（x0y0z0)1/41（U1）001（x0y0z1)1/42（U2）010（x0y1z0)1/83（U3）011（x0y1z1)1/84（U4）100（x1y0z0)1/165（U5）101（x1y0z1)1/166（U6）110（x1y1z0)1/167（U7）111（x1y1z1)1/16解：⑴收到第一個(gè)0(x0)后U0~U7的后驗(yàn)概率：信源消息二進(jìn)制代碼先驗(yàn)概率收到0后的后驗(yàn)概率收到01后的后驗(yàn)概率收到011后的后驗(yàn)概率0（U0）000（x0y0z0)1/41/31（U1）001（x0y0z1)1/41/32（U2）010（x0y1z0)1/81/63（U3）011（x0y1z1)1/81/64（U4）100（x1y0z0)1/1605（U5）101（x1y0z1)1/1606（U6）110（x1y1z0)1/1607（U7）111（x1y1z1)1/160收到01后的后驗(yàn)概率：收到011后的后驗(yàn)概率：信源消息二進(jìn)制代碼先驗(yàn)概率收到0后的后驗(yàn)概率收到01后的后驗(yàn)概率收到011后的后驗(yàn)概率0（U0）000（x0y0z0)1/41/3001（U1）001（x0y0z1)1/41/3002（U2）010（x0y1z0)1/81/61/203（U3）011（x0y1z1)1/81/61/214（U4）100（x1y0z0)1/160005（U5）101（x1y0z1)1/160006（U6）110（x1y1z0)1/160007（U7）111（x1y1z1)1/16000⑵x0與各消息的互信息量⑶在已收到（給定）x0條件下，y1與各消息的互信息量。⑷

在已收到（給定）x0y1條件下，z1與U3消息的互信息量.

⑸

收到整個(gè)代碼組x0y1z1出現(xiàn)后提供的有關(guān)消息U3的互信息量。物理含義

我們還可以用下式求得代碼組x0y1z1出現(xiàn)后提供有關(guān)U3的信息量：011

§2.1.5平均互信息量⒈平均互信息量的定義定義：互信息量I（ai;bj)在聯(lián)合概率空間p(aibj)中的統(tǒng)計(jì)平均值為平均互信息量同理有：⒉平均互信息量的物理意義平均互信息量可以定義為無(wú)條件熵與條件熵的差：H（X;Y)=H(X)－H(X∣Y)=H(Y)－H(Y∣X)=H(X)＋H(Y)－H(XY)H(X)是信源集的符號(hào)熵，即發(fā)送端發(fā)出的平均信息量。H(X∣Y)為信道干擾引起損失的平均信息量，即信道疑義度。所以該式表示為：接收到的平均信息量=發(fā)出的平均信息量－信道損失的

信息量。H(X)+H(Y)表示在通信前系統(tǒng)的先驗(yàn)不確定性。H(XY)表示輸入集符號(hào)經(jīng)有噪信道傳輸?shù)捷敵龆?，為系統(tǒng)的后驗(yàn)不確定性。所以該式表示為：接收到的平均信息量=系統(tǒng)的先驗(yàn)不確定性－系統(tǒng)的后驗(yàn)不確定性。H(Y)是輸出集的符號(hào)熵，表示要確認(rèn)Y所需的信息量H(Y∣X)為噪聲熵，表示發(fā)出X后要確認(rèn)Y尚需增加的信息量所以該式表示為：接收到的平均信息量=確認(rèn)Y所必需的平均信息量

—發(fā)出X后要確認(rèn)Y尚需增加的信息量。

⒊平均互信息量的性質(zhì)

⑴對(duì)稱性I（X；Y）=I（Y；X）⑵非負(fù)性I（X；Y）≧0⑶極值性I（X；Y）≦H（X）

I（X；Y）≦H（Y）⑷凸函數(shù)性

平均互信息I(X;Y)信道傳遞概率分布P(Y/X)的U型凸函數(shù)平均互信息I(X;Y)是信源概率分布P(X)的型凸函數(shù)

定理說(shuō)明：對(duì)于一定的信道轉(zhuǎn)移概率分布，總可以找到某一個(gè)先驗(yàn)概率分布的信源X，使平均互信息量達(dá)到相應(yīng)的最大值Imax，這時(shí)稱這個(gè)信源為該信道的匹配信源?？梢哉f(shuō)不同的信道轉(zhuǎn)移概率對(duì)應(yīng)不同的Imax。

§2.1單符號(hào)離散信源例1：已知聯(lián)合概率分布如下，求：H(XY)，H(X),

H(Y),H(Y|X),H(X|Y)，I（X;Y)。行矢之和為p(xi)列矢之和為p(yj)

§2.1單符號(hào)離散信源解：由邊際分布得：由聯(lián)合分布可得：H(XY)=2.665bit/符號(hào)∴I(X;Y)=H(X)+H(Y)－H(XY)=1.257bit/符號(hào)

H(X∣Y)=H(X)－I（X;Y）=0.809bit/符號(hào)

H(Y∣X)=H(Y)－I（X;Y）=0.600bit/符號(hào)H(X)=2.066bit/符號(hào)H(Y)=1.856bit/符號(hào)

§2.1單符號(hào)離散信源例2：已知信源X={A,B,C},信源Y={D,E,F,G},其條件

概率分布和X的概率分布如下表。試求：聯(lián)合熵，噪聲熵，信道疑義度及平均互信息量。P(Y|X)DEFGP(X)A1/41/41/41/41/2B3/101/51/53/101/3C1/61/21/61/61/6

§2.1單符號(hào)離散信源解：由p(XY)=p(X)P(Y∣X)，即可由聯(lián)合分布通過(guò)邊際分布即可求得p(Y)P(XY)DEFGA1/81/81/81/8B1/101/151/151/10C1/361/121/361/36P(Y)91/36033/12079/36091/360H(XY)=3.417bit/符號(hào)；H(X)=1.46bit/符號(hào)；H(Y)=1.997bit/符號(hào)；H(Y|X)=1.95bit/符號(hào)；H(X|Y)=H(XY)-H(Y)=1.42bit/符號(hào)

§2.1單符號(hào)離散信源例3：設(shè)有一個(gè)系統(tǒng)傳送10個(gè)數(shù)字0，1，…9，奇數(shù)在傳送時(shí)以0.5的概率錯(cuò)成另外的奇數(shù)，而其它數(shù)字總能正確接收。試求，收到一個(gè)數(shù)字平均得到的信息量。解：設(shè)，10個(gè)發(fā)送的數(shù)字的概率分布為均勻分布，由已知得：∴

H(Y)=㏒10bit/符號(hào)

§2.1單符號(hào)離散信源1.3.2離散無(wú)記憶的擴(kuò)展信源

實(shí)際情況下，信源輸出的消息往往不是單個(gè)符號(hào)，而是由許多不同時(shí)刻發(fā)出的符號(hào)所組成的符號(hào)序列。設(shè)序列由N個(gè)符號(hào)組成，若這N個(gè)符號(hào)取自同一符號(hào)集{a1,a2,…,an}，并且先后發(fā)出的符號(hào)彼此間統(tǒng)計(jì)獨(dú)立，我們將這樣的信源稱作離散無(wú)記憶的N維擴(kuò)展信源。其數(shù)學(xué)模型為N維概率空間：

x為各種長(zhǎng)為N的符號(hào)序列，x=x1x2…

xN

，xi

{a1,a2,…,ak

}，1

i

N，序列集X={a1a1…

a1,a1a1…

a2,…,

akak…

ak

}，共有kN種序列，xX序列的概率p(x)=p(x1x2

…

xN)=

§2.2多符號(hào)離散平穩(wěn)信源實(shí)際信源輸出往往是符號(hào)序列，稱為離散多符號(hào)信源。即X=x1x2x3……，其特點(diǎn)：消息序列中的每一位的出現(xiàn)都是隨機(jī)的，即每一位都是隨機(jī)變量/隨機(jī)矢量。消息序列中的前后符號(hào)通常是相互依賴的。消息序列中的每一位的出現(xiàn)有時(shí)是隨時(shí)間變化的。這種信源我們稱之為多符號(hào)離散信源。若隨機(jī)矢量X中隨機(jī)變量的各維聯(lián)合概率分布與時(shí)間起點(diǎn)無(wú)關(guān)則稱隨機(jī)矢量X為多符號(hào)離散平穩(wěn)信源。當(dāng)離散平穩(wěn)無(wú)記憶信源信源發(fā)出固定長(zhǎng)度的消息序列時(shí)，則得到原信源的擴(kuò)展信源。例如在電報(bào)系統(tǒng)中，若信源輸出的是二個(gè)二元數(shù)字組成的符號(hào)序列，此時(shí)可認(rèn)為是一個(gè)新的信源，它由四個(gè)符號(hào)（00，01，10，11）組成，我們把該信源稱為二元無(wú)記憶信源的二次擴(kuò)展信源。如果把N個(gè)二元數(shù)字組成一組，則信源等效成一個(gè)具有2N個(gè)符號(hào)的新信源，把它稱為二元無(wú)記信源的N次擴(kuò)展信源。一般情況下，對(duì)一個(gè)離散無(wú)記憶信源X，其樣本空間為{x1,x2,…,xn}，對(duì)它的輸出消息序列，可用一組組長(zhǎng)度為N的序列來(lái)表示它。這時(shí)，它等效成一個(gè)新信源。新信源輸出的符號(hào)是N維離散隨機(jī)矢量X

=(X1，X2,……,XN)，其中每個(gè)分量Xi(i＝1,2,…,N)都是隨機(jī)變量，它們都取值于同一信源符號(hào)集，并且分量之間統(tǒng)計(jì)獨(dú)立，則由隨機(jī)矢量X組成的新信源稱為離散無(wú)記憶信源X的N次擴(kuò)展信源。

2.2.1序列信息的熵離散無(wú)記憶信源X取值于集合，擴(kuò)展信源輸出為一組組長(zhǎng)度為N的消息序列，，其中每個(gè)分量Xi（i=1，2，…，N）都是隨機(jī)變量，都取值于同一集合，且分量之間統(tǒng)計(jì)獨(dú)立。離散無(wú)記憶信源X的N次擴(kuò)展信源單符號(hào)離散信源X的數(shù)學(xué)模型：?jiǎn)畏?hào)離散信源X的N次擴(kuò)展信源XN的數(shù)學(xué)模型：離散無(wú)記憶信源X的N次擴(kuò)展信源的熵就是離散信源X的熵的N倍0

p(ai)1例：有一離散平穩(wěn)無(wú)記憶信源，求這個(gè)信源的二次擴(kuò)展信源的熵。X2信源的元素a1a2a3a4a5a6a7a8a9消息序列x1x1x1x2x1x3x2x1x2x2x2x3x3x1x3x2x3x3概率p(ai)1/41/81/81/81/161/161/81/161/16解：二次擴(kuò)展信源：一、離散平穩(wěn)信源的數(shù)學(xué)定義

在一般情況下，信源在t=i

時(shí)刻將要發(fā)出什么樣的符號(hào)決定于兩方面：

(1)信源在t=i

時(shí)刻隨機(jī)變量Xi

取值的概率分布P(xi)。

[一般P(xi)P(xj)](2)t=i

時(shí)刻以前信源發(fā)出的符號(hào)。

[即與條件概率P(xi/xi-1xi-2…)有關(guān)]對(duì)平穩(wěn)隨機(jī)序列，序列的統(tǒng)計(jì)性質(zhì)與時(shí)間的推移無(wú)關(guān)，即信源發(fā)出符號(hào)序列的概率分布與時(shí)間起點(diǎn)無(wú)關(guān)。

2.2.2離散平穩(wěn)信源

平穩(wěn)隨機(jī)序列的數(shù)學(xué)定義如下：

若當(dāng)t=i，t=j時(shí)(i,j是大于1的任意整數(shù))，P(xi)=P(xj)=P(x)，則序列是一維平穩(wěn)的。具有這樣性質(zhì)的信源稱為一維平穩(wěn)信源。除上述條件外，如果聯(lián)合概率分布P(xixi+1)也與時(shí)間起點(diǎn)無(wú)關(guān)，即P(xixi+1)=P(xjxj+1)(i,j為任意整數(shù)且ij)，則信源稱為二維平穩(wěn)信源。它表示任何時(shí)刻信源發(fā)出二個(gè)符號(hào)的聯(lián)合概率分布也完全相等。如果各維聯(lián)合概率分布均與時(shí)間起點(diǎn)無(wú)關(guān)，那么，信源是完全平穩(wěn)的。這種各維聯(lián)合概率分布均與時(shí)間起點(diǎn)無(wú)關(guān)的完全平穩(wěn)信源稱為離散平穩(wěn)信源。這時(shí)有：P(xi)=P(xj)P(xi

xi+1)=P(xj

xj+1)……P(xi

xi+1…xi+N

)=P(xj

xj+1…xi+N

)不同時(shí)刻，概率分布相同由于聯(lián)合概率與條件概率有以下關(guān)系：結(jié)論：對(duì)于平穩(wěn)信源來(lái)說(shuō)，其條件概率均與時(shí)間起點(diǎn)無(wú)關(guān)，只與關(guān)聯(lián)長(zhǎng)度N有關(guān)。即平穩(wěn)信源發(fā)出的平穩(wěn)隨機(jī)序列前后的依賴關(guān)系與時(shí)間起點(diǎn)無(wú)關(guān)。從平穩(wěn)性可得：對(duì)平穩(wěn)信源如果某時(shí)刻發(fā)出什么符號(hào)只與前面發(fā)出的N個(gè)符號(hào)有關(guān)，那么任何時(shí)刻它們的依賴關(guān)系都是一樣的。即：2.2.2離散平穩(wěn)信源的信源熵和極限熵二維平穩(wěn)有記憶信源：信源輸出為一組組長(zhǎng)度為2的消息序列，符號(hào)序列組內(nèi)有統(tǒng)計(jì)關(guān)聯(lián)性，且假設(shè)組與組之間是統(tǒng)計(jì)獨(dú)立的。數(shù)學(xué)模型：得到一個(gè)新的離散無(wú)記憶信源集兩個(gè)有相互依賴關(guān)系的隨機(jī)變量X1和X2所組成的隨機(jī)矢量的聯(lián)合熵H(X),等于第一個(gè)隨機(jī)變量的熵H(X1)與第一個(gè)隨機(jī)變量X1已知的前提下，第二個(gè)隨機(jī)變量X2的條件熵H(X2/X1)之和。當(dāng)隨機(jī)變量X1和X2相互統(tǒng)計(jì)獨(dú)立時(shí)：當(dāng)隨機(jī)變量X1和X2取值于同一集合時(shí)：離散無(wú)記憶信源的二次擴(kuò)展信源可看成是二維離散平穩(wěn)信源的特例。注：例：設(shè)某二維離散信源的原始信源的信源模型：解：原始信源X的熵：中前后兩個(gè)符號(hào)的條件概率如下：P(X2/X1)x1x2x3x17/92/90x21/83/41/8x302/119/11條件熵：平均信息量：信源的相關(guān)性使信息熵變小。1.離散平穩(wěn)信源的信源熵：2.條件熵：條件熵隨N的增加而單調(diào)不增3.平均符號(hào)熵：N給定，平均符號(hào)熵大于等于條件熵平均符號(hào)熵隨N的增加而非遞增的4.極限熵：對(duì)于離散平穩(wěn)有記憶信源，當(dāng)依賴關(guān)系為無(wú)限長(zhǎng)時(shí)，平均符號(hào)熵和條件熵都非遞增的一致趨于平穩(wěn)有記憶信源的極限熵在很多信源的輸出序列中，符號(hào)之間的依賴關(guān)系是有限的，任何時(shí)刻信源符號(hào)發(fā)生的概率只與前邊已經(jīng)發(fā)出的若干個(gè)符號(hào)有關(guān)，而與更前面的符號(hào)無(wú)關(guān)。為了描述這類信源除了信源符號(hào)集外還要引入狀態(tài)集。這時(shí)，信源輸出消息符號(hào)還與信源所處的狀態(tài)有關(guān)。

要點(diǎn)：限制關(guān)聯(lián)長(zhǎng)度

引入狀態(tài)概念

馬爾可夫信源:馬爾可夫信源是一類有限長(zhǎng)度記憶的非平穩(wěn)離散信源。b：信源某l時(shí)刻所處的狀態(tài)只由當(dāng)前輸出的符號(hào)和前一時(shí)刻信源所處的狀態(tài)唯一決定2.2.4馬爾可夫信源一、定義：若信源輸出的符號(hào)和所處的狀態(tài)滿足馬爾可夫鏈的條件：a：某一時(shí)刻信源輸出的符號(hào)只與此刻信源所處的狀態(tài)有關(guān)，而與以前的狀態(tài)和輸出的符號(hào)無(wú)關(guān)。若上述兩條件與時(shí)刻L無(wú)關(guān)，則具有時(shí)齊性（齊次性），稱為時(shí)齊馬爾可夫信源。馬爾可夫鏈的概念X1Xi+1X2XiXi+2SjXi-2Sj-1Xi-1…………Sj+1S2S1…………若信源隨機(jī)狀態(tài)序列服從馬爾可夫鏈，則稱該信源為馬爾可夫信源二、模型：（狀態(tài)轉(zhuǎn)移圖）例：設(shè)信源符號(hào)，信源所處的狀態(tài)

，各狀態(tài)之間的轉(zhuǎn)移情況如圖：馬爾可夫信源的狀態(tài)轉(zhuǎn)移圖

狀態(tài)轉(zhuǎn)移圖發(fā)出的轉(zhuǎn)移概率之和為1

狀態(tài)矩陣行矢為1條件概率三、m階馬爾可夫信源

m階馬爾可夫信源，它在任何時(shí)刻l，符號(hào)發(fā)生的概率只與前面的m個(gè)符號(hào)有關(guān)，可以把這前面的m個(gè)符號(hào)看作信源在此l時(shí)刻所處的狀態(tài)1、數(shù)學(xué)模型：當(dāng)m=1時(shí)，為一階馬爾可夫信源。2、m階馬氏信源熵注：（1）只有時(shí)齊遍歷（各態(tài)歷經(jīng)）的馬爾可夫信源，當(dāng)時(shí)間足夠長(zhǎng)達(dá)到穩(wěn)定以后才能等價(jià)成平穩(wěn)有記憶信源。各態(tài)歷經(jīng)：定理：對(duì)于有限齊次馬爾可夫鏈，若存在一個(gè)正整數(shù)l0≥1，對(duì)于一切i，j=1，2，…，nm，都有,則對(duì)于每一個(gè)j都存在不依賴于i的極限則稱這種馬爾可夫鏈?zhǔn)歉鲬B(tài)歷經(jīng)的。（2）此處聯(lián)合概率是時(shí)齊遍歷的m階馬爾可夫信源達(dá)到穩(wěn)定后的極限概率，與初始時(shí)刻符號(hào)概率分布不同對(duì)于m階馬爾可夫信源，這表明m階馬爾可夫信源的極限熵H∞就等于m階條件熵。由條件熵的概念有：時(shí)齊性限制關(guān)聯(lián)長(zhǎng)度時(shí)齊性定義式馬爾可夫信源的極限熵:例：某二元二階馬爾可夫信源，信源符號(hào)，其狀態(tài)空間共有nm=22=4個(gè)不同的狀態(tài)即各狀態(tài)之間的轉(zhuǎn)移情況如圖：有記憶信源的平均符號(hào)熵

m階馬爾科夫信源每發(fā)一個(gè)符號(hào)提供的平均信息量為H∞，而m個(gè)為一組的有記憶信源每發(fā)一個(gè)符號(hào)提供的平均信息量為二者是不同的。冗余度－1它表征信源信息率的多余程度，是描述信源客觀統(tǒng)計(jì)特性的一個(gè)物理量。由廣義Shannon不等式有：或：可見(jiàn)對(duì)于有記憶信源，最小單個(gè)消息熵應(yīng)為，即從理論上看，對(duì)有記憶信源只需傳送即可。但是這必需要掌握信源全部概率統(tǒng)計(jì)特性。這顯然是不現(xiàn)實(shí)的。實(shí)際上，往往只能掌握有限的維，這時(shí)需傳送，那么與理論值相比，就多傳送了。冗余度－2為了定量描述信源有效性，可定義：信源效率：

信源冗余度：（相對(duì)剩余）冗余度－3正由于信源存在著冗余度，即存在著不必要傳送的信息，因此信源也就存在進(jìn)一步壓縮信息率的可能性。冗余度越大，壓縮潛力也就越大?？梢?jiàn)它是信源編碼，數(shù)據(jù)壓縮的前提與理論基礎(chǔ)。字母

字母

字母空格ETOANIR0.20.1050.0720.06540.0630.0590.0550.054SHDLCF.UMP0.05020.0470.0350.0290.0230.02250.0210.0175Y.WGBVKXJ.QZ0.0120.0110.01050.0080.0030.0020.0010.001冗余度－4（舉例：計(jì)算英文文字信源的冗余度）首先給出英文字母（含空格）出現(xiàn)概率如下：冗余度－5（舉例：計(jì)算英文文字信源的冗余度）首先求得獨(dú)立等概率情況，即其次，計(jì)算獨(dú)立不等概率情況，再次，若僅考慮字母有一維相關(guān)性，求，最后，利用統(tǒng)計(jì)推斷方法求出，由于采用的逼近的方法和所取的樣本的不同，推算值也有不同，這里采用Shannon的推斷值。

由上述例子可看出：由于各個(gè)符號(hào)出現(xiàn)的概率不均勻

所以：H1＜H0隨著序列增長(zhǎng)，字母間的相關(guān)性越來(lái)越強(qiáng):

所以：H＜…＜H3＜H2正是因?yàn)樾旁捶?hào)中存在的這些統(tǒng)計(jì)不均勻性和相關(guān)性，才使得信源存在冗余度。當(dāng)英文字母的結(jié)構(gòu)信息已預(yù)先充分獲得時(shí)，可用合理符號(hào)來(lái)表達(dá)英語(yǔ)，例如傳送或存儲(chǔ)這些符號(hào)，可大量壓縮，100頁(yè)的英語(yǔ)，大約只要29頁(yè)就可以了。

冗余度－6這一結(jié)論說(shuō)明，英文信源，從理論上看71％是多余成分。直觀地說(shuō)100頁(yè)英文書，理論上看僅有29頁(yè)是有效的，其余71頁(yè)是多余的。正是由于這一多余量的存在，才有可能對(duì)英文信源進(jìn)行壓縮編碼。冗余度－7對(duì)于其它文字，也有不少人作了大量的統(tǒng)計(jì)工作，現(xiàn)簡(jiǎn)述如下：

英文法文德文西班牙文中文（按8千漢字計(jì)算）問(wèn)題1：冗余度產(chǎn)生的原因

冗余度（多余度、剩余度）表示給定信源在實(shí)際發(fā)出消息時(shí)所包含的多余信息。

冗余度來(lái)自兩個(gè)方面，一是信源符號(hào)間的相關(guān)性，由于信源輸出符號(hào)間的依賴關(guān)系使得信源熵減小，這就是信源的相關(guān)性。相關(guān)程度越大，信源的實(shí)際熵越小，趨于極限熵H（X）；反之相關(guān)程度減小，信源實(shí)際熵就增大。另一個(gè)方面是信源符號(hào)分布的不均勻性，當(dāng)?shù)雀怕史植紩r(shí)信源熵最大。而實(shí)際應(yīng)用中大多是不均勻分布，使得實(shí)際熵減小。當(dāng)信源輸出符號(hào)間彼此不存在依賴關(guān)系且為等概率分布時(shí)，信源實(shí)際熵趨于最大H0（X）。

結(jié)論：在實(shí)際通信系統(tǒng)中，為了提高傳輸效率，往往需要把信源的大量冗余進(jìn)行壓縮，即所謂信源編碼。但是考慮通信中的抗干擾問(wèn)題，則需要信源具有一定的冗余度。因此在傳輸之前通常加人某些特殊的冗余度，即所謂信道編碼，以達(dá)到通信系統(tǒng)理想的傳輸有效性和可靠性。

1.3.3離散平穩(wěn)有記憶信源

中、英文句子中前后出現(xiàn)的漢字、字母往往是有依賴的。這種依賴性我們稱作有記憶。用聯(lián)合概率空間{X

,q(X)}來(lái)描述離散有記憶信源的輸出。信源在i時(shí)刻發(fā)出什么符號(hào)與i時(shí)刻以前信源所發(fā)出的符號(hào)有關(guān)，即由條件概率p(xixi-1

xi-2…)確定。如果該條件概率分布與時(shí)間起點(diǎn)無(wú)關(guān)，只與關(guān)聯(lián)長(zhǎng)度有關(guān)，則該信源為平穩(wěn)信源。對(duì)于離散平穩(wěn)有記憶信源，有：p(x1=a1)=p(x2=a1)=

…p(x2=a2x1=a1)=p(x3=a2x2=a1)=

…p(x3x2

x1)=p(x4x3

x2)=

…┇p(xi+Lxi+L-1

xi+L-2

…xi)=p(xj+Lxj+L-1

xj+L-2

…xj)=

…┇

【例1.4】

某離散平穩(wěn)信源，設(shè)信源發(fā)出的符號(hào)只與前一個(gè)符號(hào)有關(guān)，其關(guān)聯(lián)程度用表1-1所示聯(lián)合概率p(xi

xj

)表示（xi為前一個(gè)符號(hào)，xj為后一個(gè)符號(hào)）：

xj

xi01201/31/9011/91/181/6201/61/18表1-1p(xi

xj

)

滿足，由可計(jì)算出當(dāng)已知前一個(gè)符號(hào)xi時(shí)，后一個(gè)符號(hào)xj為0、1、2時(shí)的概率各為多少：

xj

xi01203/41/4011/31/61/2203/41/4表1-2p(xjxi)1.3.4馬爾可夫信源

馬爾可夫信源輸出的消息序列與信源的狀態(tài)滿足下列條件：

(1)某一時(shí)刻信源的輸出只與當(dāng)時(shí)的信源狀態(tài)有關(guān)，而與以前的狀態(tài)無(wú)關(guān)。p(xr=al

er=si,er-1=st,er-2=sn,…)=p(xr=al

er=si)，滿足。(2)某一時(shí)刻信源所處的狀態(tài)只由當(dāng)前的輸出符號(hào)和前一時(shí)刻的狀態(tài)唯一決定。當(dāng)時(shí)齊馬爾可夫信源達(dá)到平穩(wěn)分布時(shí)，滿足

p(er+1=sj

xr=al

,er=si)=1.4離散信道及其數(shù)學(xué)模型

信道是信息傳輸?shù)耐ǖ?，如圖1-3，信道可看作一個(gè)變換器，它將輸入消息x變換成輸出消息y，以信道轉(zhuǎn)移概率p(yx)來(lái)描述信道的統(tǒng)計(jì)特性。

信道p(y

x)xy圖1-3信道模型

無(wú)記憶信道X的各時(shí)刻取值相互獨(dú)立。有記憶信道

X的各時(shí)刻取值互相有關(guān)聯(lián)。信道可以按不同的特性進(jìn)行分類，根據(jù)輸入和輸出信號(hào)的特點(diǎn)可分為：波形信道

信道的輸入和輸出都是時(shí)間上連續(xù)，并且取值也連續(xù)的隨機(jī)信號(hào)。

半連續(xù)信道

輸入序列和輸出序列一個(gè)是離散的，而另一個(gè)是連續(xù)的。連續(xù)信道

信道的輸入和輸出都是時(shí)間上離散、取值連續(xù)的隨機(jī)序列，又稱為模擬信道離散信道

信道的輸入和輸出都是時(shí)間上離散、取值離散的隨機(jī)序列。離散信道有時(shí)也稱為數(shù)字信道。根據(jù)統(tǒng)計(jì)特性，即轉(zhuǎn)移概率p(yx)的不同，信道又可分類為：

1.4.1離散無(wú)記憶信道

離散無(wú)記憶信道的輸入和輸出消息都是離散無(wú)記憶的單個(gè)符號(hào)，輸入符號(hào)xi

{a1,a2,…,ak}，1

i

I，輸出符號(hào)yj

{b1,b2,…,bD

}，1

j

J，信道的特性可表示為轉(zhuǎn)移概率矩陣：p(yjxi

)對(duì)應(yīng)為已知輸入符號(hào)為xi，當(dāng)輸出符號(hào)為yj時(shí)的信道轉(zhuǎn)移概率，滿足0

p(yjxi

)1，且。

將信道特性表示成圖1-4的形式：

p(y1

x1)x1x2y1y2xIyJp(yJ

xI

)圖1-4單符號(hào)離散無(wú)記憶信道1.二元對(duì)稱信道(BinarySymmetricChannel，簡(jiǎn)記為BSC)這是一種很重要的信道，它的輸入符號(hào)x{0,1}，輸出符號(hào)y{0,1}，轉(zhuǎn)移概率p(yx)如圖1-5所示信道特性可表示為信道矩陣，其中p稱作信道錯(cuò)誤概率。下面列舉幾種常見(jiàn)的離散無(wú)記憶信道：圖2-10二進(jìn)制對(duì)稱信道1-p0

p

1011-p

p

圖1-6無(wú)干擾信道210011112

2.

無(wú)干擾信道這是一種最理想的信道，也稱作無(wú)噪信道，信道的輸入和輸出符號(hào)間有確定的一一對(duì)應(yīng)關(guān)系，

p(yx)=如圖