信息論與編碼曹雪虹著第二章

第2章信源與信息熵2.1信源描述與分類(lèi)2.2離散信源的信息熵和互信息2.3離散序列信源的熵2.4連續(xù)信源的熵與互信息2.5冗余度12.1信源的描述與分類(lèi)信源定義:

信源是產(chǎn)生消息（符號(hào)）、消息序列和連續(xù)消息的來(lái)源。從數(shù)學(xué)上，由于消息的不確定性，因此，信源是產(chǎn)生隨機(jī)變量、隨機(jī)序列和隨機(jī)過(guò)程的源信源的基本特性是具有隨機(jī)不確定性22.1信源特性與分類(lèi)信源分類(lèi)(1)按信源發(fā)出消息在時(shí)間和幅度上分布情況離散信源:時(shí)間和幅度上都是離散分布的離散消息。如:文字、數(shù)字等。

單符號(hào)離散信源符號(hào)序列離散信源連續(xù)信源:時(shí)間或幅度上是連續(xù)分布的連續(xù)消息。如:話音、圖像等。32.1信源特性與分類(lèi)(2)按信源發(fā)出的符號(hào)之間關(guān)系無(wú)記憶信源:發(fā)出單個(gè)符號(hào)和發(fā)出符號(hào)序列無(wú)記憶信源。有記憶信源:發(fā)出符號(hào)序列的有記憶信源和發(fā)出符號(hào)序列的馬爾可夫信源。(3)按照輸出序列的平穩(wěn)性，可分為：平穩(wěn)信源非平穩(wěn)信源42.1信源描述與分類(lèi)幾個(gè)概念樣本空間：某事物各種可能出現(xiàn)的不同狀態(tài)，即所有可能選擇的消息集合。概率測(cè)度：每一個(gè)可能選擇消息的概率，又稱(chēng)先驗(yàn)概率。后驗(yàn)概率：指條件概率P(ai/bj)。概率空間：一個(gè)樣本空間和它的概率測(cè)度組合。52.1信源描述與分類(lèi)數(shù)學(xué)模型描述：通過(guò)概率空間描述（1）單符號(hào)離散信源其中,符號(hào)集A={u1,u2,u3……un}，UA成為U的樣本空間，且Pi≥0，。

62.1信源描述與分類(lèi)例如：對(duì)二進(jìn)制數(shù)字與數(shù)據(jù)信源72.1信源描述與分類(lèi)例如：有100個(gè)球，其中有80個(gè)紅色球，20個(gè)白色球，隨機(jī)取出一個(gè)球，然后放回，在隨機(jī)取一個(gè)球，如此反復(fù)。每次取球?yàn)楹畏N顏色作為消息，則隨機(jī)變量X的樣本空間集A={x1=“紅色”,x2=“白色”}，而X的概率分布p(x1)=0.8,p(x2)=0.2，信源的概率空間為82.1信源描述與分類(lèi)（2）離散序列信源：每次發(fā)出1組含2個(gè)以上符號(hào)的符號(hào)序列來(lái)代表一個(gè)消息的信源。每個(gè)消息要用符號(hào)序列來(lái)描述，即用隨機(jī)序列或隨機(jī)矢量來(lái)描述：

x

∈

{a1，a2

·

··an

}最簡(jiǎn)單L=2情況，此時(shí)信源其概率空間為：92.1信源描述與分類(lèi)舉例：以3位PCM（脈沖編碼調(diào)制）信源為例102.1信源描述與分類(lèi)當(dāng)p=1/2112.1信源描述與分類(lèi)（3）連續(xù)信源:輸出消息取值是無(wú)限的，即可能出現(xiàn)的消息數(shù)是不可數(shù)的無(wú)限值。其數(shù)學(xué)模型為連續(xù)型的概率空間且概率密度分布函數(shù)P(u)≥0,。符號(hào)集中的取值是介于（a,b）之間連續(xù)值，P(u)概率密度分布函數(shù)。122.1信源描述與分類(lèi)例如：

一個(gè)袋中有很多干電池，隨機(jī)摸出一個(gè)，測(cè)其電壓值作為輸出符號(hào)，該信源每次輸出一個(gè)符號(hào)，但符號(hào)取值在[0，1.5]之間的所有實(shí)數(shù)，可用連續(xù)型隨機(jī)變量U來(lái)描述，連續(xù)信源的概率空間為顯然滿足P(u)≥0,

。132.1信源描述與分類(lèi)無(wú)記憶信源定義：所發(fā)出的各個(gè)符號(hào)或符號(hào)序列之間無(wú)統(tǒng)計(jì)（概率）關(guān)聯(lián)性。則N維隨機(jī)矢量的聯(lián)合概率分布滿足P(X=X1X2X3…XN)=P１(Ｘ１)P２(Ｘ２)…PＮ(ＸＮ)142.1信源描述與分類(lèi)（1）單符號(hào)無(wú)記憶信源

定義：離散無(wú)記憶信源是由n個(gè)單符號(hào)消息組成的集合

X={x1，x2

···xn

}，這n個(gè)符號(hào)消息的概率分布為：稱(chēng)為符號(hào)xi

的先驗(yàn)概率,離散信源數(shù)學(xué)模型表示為：

稱(chēng)為概率空間,其中152.1信源描述與分類(lèi)例1：離散無(wú)記憶信源單個(gè)符號(hào)X={0,1}X={A,B,…,Z}

162.1信源描述與分類(lèi)單符號(hào)無(wú)記憶信源的性質(zhì)它是最簡(jiǎn)單也是最基本的信源，是組成實(shí)際信源的基本單元。當(dāng)信源給定，其相應(yīng)的概率空間就已給定；反之，如果概率空間給定，這就表示相應(yīng)的信源已給定。所以，概率空間能表征這離散信源的統(tǒng)計(jì)特性，因此有時(shí)也把這個(gè)概率空間稱(chēng)為信源空間。這些信源可能輸出的消息數(shù)是有限的或可數(shù)的，而且每次只輸出其中一個(gè)消息。因此，可以用一個(gè)離散型隨機(jī)變量X來(lái)描述這個(gè)信源輸出的消息。這個(gè)隨機(jī)變量X的樣本空間就是符號(hào)集A；而X的概率分布就是各消息出現(xiàn)的先驗(yàn)概率，信源的概率空間必定是一個(gè)完備集。172.1信源描述與分類(lèi)(2)序列符號(hào)無(wú)記憶信源定義：每次發(fā)出1組含2個(gè)以上符號(hào)的符號(hào)序列來(lái)代表一個(gè)消息的信源。每個(gè)消息要用符號(hào)序列來(lái)描述，即用隨機(jī)序列或隨機(jī)矢量來(lái)描述,這些符號(hào)序列中的各個(gè)符號(hào)之間沒(méi)有統(tǒng)計(jì)關(guān)聯(lián)性,各個(gè)符號(hào)出現(xiàn)的概率是它自身的先驗(yàn)概率,即

P(X=X1X2X3…XN)=P1(X1)P2(X2)…PN(XN)182.1信源描述與分類(lèi)最簡(jiǎn)單L=2的情況，其概率分布為：其中：且192.1信源描述與分類(lèi)例:

符號(hào)序列X={00,01,10,11}X={AA,AB,…,AZ,BA,BB,…,BZ,…,ZZ}202.1信源描述與分類(lèi)(3)離散平穩(wěn)信源定義：信源輸出的隨機(jī)序列X=(Ｘ１,Ｘ２,…,ＸＮ)滿足：每個(gè)隨機(jī)變量Xi都是離散型隨機(jī)變量。隨機(jī)矢量X的各維概率分布都與時(shí)間起點(diǎn)無(wú)關(guān)。這樣的信源稱(chēng)為離散平穩(wěn)信源。一般來(lái)說(shuō)，我們假設(shè)信源輸出的是平穩(wěn)的隨機(jī)序列，也就是序列的統(tǒng)計(jì)性質(zhì)與時(shí)間的推移無(wú)關(guān)。很多序列符號(hào)無(wú)記憶信源也滿足這個(gè)假設(shè)。212.1信源描述與分類(lèi)例：在上一個(gè)例子中，如果每次取出兩個(gè)球，則兩個(gè)球的顏色組成的消息就是符號(hào)序列。如先取出一個(gè)球，記下顏色后再取出另外一個(gè)球，則每次取出的兩個(gè)球的顏色是獨(dú)立的，因而該信源是無(wú)記憶的，即發(fā)出符號(hào)序列的無(wú)記憶信源。由于布袋中紅球、白球的分布情況不隨時(shí)間變化，也就是信源發(fā)出的序列的統(tǒng)計(jì)性質(zhì)與時(shí)間的推移無(wú)關(guān)，是平穩(wěn)的隨機(jī)序列。這一點(diǎn)特別重要，會(huì)給問(wèn)題的分析帶來(lái)很大的方便，于是每個(gè)變量的一維分布都相同：有時(shí)也將這種信源稱(chēng)為離散無(wú)記憶信源X的L次擴(kuò)展信源。22離散平穩(wěn)信源特征:

平穩(wěn)信源發(fā)出的平穩(wěn)隨機(jī)序列前后的依賴(lài)關(guān)系與時(shí)間起點(diǎn)無(wú)關(guān).如果某時(shí)刻發(fā)出的符號(hào)與前面發(fā)出的N個(gè)符號(hào)有關(guān),那么任何時(shí)刻它們的依賴(lài)關(guān)系都是一樣的,

即232.1信源描述與分類(lèi)有記憶信源定義：所發(fā)出的各個(gè)符號(hào)或符號(hào)序列之間有統(tǒng)計(jì)（概率）關(guān)聯(lián)性。一般情況下，信源在不同時(shí)刻發(fā)出的符號(hào)之間是相互依賴(lài)的。表述有記憶信源要比表述無(wú)記憶信源困難得多。實(shí)際上可以限制隨機(jī)序列的記憶長(zhǎng)度。當(dāng)記憶長(zhǎng)度為m+1時(shí)，稱(chēng)這種有記憶信源為m階馬爾可夫信源。也就是信源每次發(fā)出的符號(hào)只與前m個(gè)符號(hào)有關(guān)，與更前面的符號(hào)無(wú)關(guān)。242.1信源描述與分類(lèi)(1)序列符號(hào)有記憶信源其概率分布比較復(fù)雜，需要引入條件概率來(lái)反映符號(hào)序列內(nèi)各個(gè)符號(hào)之間的記憶特征：在實(shí)際應(yīng)用中限制記憶的長(zhǎng)度，使問(wèn)題簡(jiǎn)化。252.1信源描述與分類(lèi)例：在一個(gè)布袋中放100個(gè)球，其中80個(gè)球是紅色的，20個(gè)球是白色的，隨機(jī)的從布袋中取球，則取出球的顏色帶有隨機(jī)性，由此布袋可看作一個(gè)離散信源。每次取球時(shí)，先取出一個(gè)球，記下顏色后不放回布袋，接著取另一個(gè)，這在取第二個(gè)球時(shí)布袋中紅白顏色球的概已于第一次不同，此時(shí)的概率分布與第一個(gè)球的顏色有關(guān)。因此是有記憶離散信源?，F(xiàn)實(shí)中還有許多其它的例子，如英文單詞，字母間是有關(guān)聯(lián)性的。不是任何字母都能組成有意義的單詞。262.1信源描述與分類(lèi)(2)馬爾可夫信源

a)馬爾可夫鏈定義：

若某事件發(fā)生的概率只與前m個(gè)事件相關(guān)，而與更前面的事件無(wú)關(guān)，那么該事件集合稱(chēng)為馬爾可夫鏈，其概率可描述為：272.1信源描述與分類(lèi)b)馬爾可夫信源定義：表述有記憶信源要比表述無(wú)記憶信源困難得多。實(shí)際上信源發(fā)出的符號(hào)往往只與前若干個(gè)符號(hào)的依賴(lài)關(guān)系強(qiáng)，而與更前面的符號(hào)依賴(lài)關(guān)系弱。為此，可以限制隨機(jī)序列的記憶長(zhǎng)度，這樣就構(gòu)成馬爾可夫鏈。當(dāng)記憶長(zhǎng)度為m+1時(shí)，稱(chēng)這種有記憶信源為m階馬爾可夫信源。也就是信源每次發(fā)出的符號(hào)只與前m個(gè)符號(hào)有關(guān)，與更前面的符號(hào)無(wú)關(guān).28c)一階馬爾可夫信源的數(shù)學(xué)描述如果上述條件概率與時(shí)間起點(diǎn)i無(wú)關(guān)，即信源輸出的符號(hào)序列可看成為時(shí)齊馬爾可夫鏈，則此信源稱(chēng)為時(shí)齊馬爾可信源。（齊次馬爾可夫信源）2.1信源描述與分類(lèi)292.1信源描述與分類(lèi)d)馬爾可夫狀態(tài)分析對(duì)于高階馬爾可夫鏈通常轉(zhuǎn)化為一階馬爾可夫過(guò)程來(lái)處理。對(duì)于m階馬爾可夫信源，將該時(shí)刻以前的出現(xiàn)的m個(gè)符號(hào)定義為一個(gè)狀態(tài)si，即：其中x

∈

{a1，a2

···an

}這樣，條件概率就可以表示為：302.1信源描述與分類(lèi)將該時(shí)刻以前出現(xiàn)的m個(gè)符號(hào)組成的序列定義為狀態(tài)si,即

si=(x1,x2,….xm),x1,x2,….xm

∈A={a1,a2,….an}

共有Q=nm種可能取值，即狀態(tài)集S={s1,s2…sQ}312.1信源描述與分類(lèi)更進(jìn)一步的，上述條件概率可以表示為狀態(tài)之間的轉(zhuǎn)移：更一般的，在時(shí)刻ｍ系統(tǒng)處于狀態(tài)的條件下，經(jīng)ｎ－ｍ步后轉(zhuǎn)移到狀態(tài)的概率用狀態(tài)轉(zhuǎn)移概率表示。也可以理解為在時(shí)刻ｍ系統(tǒng)處于狀態(tài)ｉ的條件下，在時(shí)刻ｎ系統(tǒng)處于狀態(tài)ｊ的條件概率，故狀態(tài)轉(zhuǎn)移概率實(shí)際上是一個(gè)條件概率。322.1信源描述與分類(lèi)通常特別關(guān)心ｎ－ｍ＝１的情況，即，記為稱(chēng)為基本轉(zhuǎn)移概率，也稱(chēng)為一步轉(zhuǎn)移概率。于是有：對(duì)于齊次馬爾可夫鏈，其轉(zhuǎn)移具有推移不變性，即只與狀態(tài)有關(guān)，與時(shí)刻無(wú)關(guān)，故可表示為：類(lèi)似的，可以定義ｋ步轉(zhuǎn)移概率：332.1信源描述與分類(lèi)轉(zhuǎn)移概率矩陣：系統(tǒng)在任一時(shí)刻可處于狀態(tài)空間中的任意一個(gè)狀態(tài)，因此轉(zhuǎn)移概率是個(gè)矩陣，利用一步轉(zhuǎn)移概率和ｋ步轉(zhuǎn)移概率可得：該矩陣中，每一個(gè)元素對(duì)應(yīng)一個(gè)轉(zhuǎn)移概率，整個(gè)矩陣表征了狀態(tài)空間中所有可能的轉(zhuǎn)移，并且每行代表了從一個(gè)狀態(tài)轉(zhuǎn)移到所有狀態(tài)的概率，轉(zhuǎn)移概率和均為１。每列代表了從所有狀態(tài)轉(zhuǎn)移到一個(gè)狀態(tài)的概率，概率之和不一定為１。34切普曼－柯?tīng)柲宸颍–hapman-Kormotopob)方程：上式右側(cè)是對(duì)所有可能值求和，因而也就是k步轉(zhuǎn)移概率，特別的當(dāng)l=1時(shí)，若用矩陣表示：從這一遞推關(guān)系可知，對(duì)于齊次馬爾可夫鏈，一步轉(zhuǎn)移概率完全決定了k步轉(zhuǎn)移概率。35為了確定條件概率，令初始概率（初始時(shí)各狀態(tài)的出現(xiàn)概率）為：某一狀態(tài)的概率為：這是一個(gè)計(jì)算狀態(tài)轉(zhuǎn)移概率的基本公式。36穩(wěn)態(tài)分布概率：若轉(zhuǎn)移概率的極限存在，即不論馬爾可夫鏈的起始狀態(tài)是什么，最后都將等于某固定值。穩(wěn)態(tài)分布的求法：應(yīng)用上述公式求穩(wěn)態(tài)分布需要馬爾可夫鏈為遍歷的，還需要滿足不可約性和非周期性。37不可約性：所謂不可約性，就是對(duì)于任一狀態(tài)，都可以達(dá)到另外一個(gè)狀態(tài)，即存在：否則即稱(chēng)該馬爾可夫鏈?zhǔn)强杉s的。如下圖中的馬爾可夫鏈就是可約的。

s1s2s31/21/21/211/2s4s51/21/21/21/238非周期性：所謂非周期性，就是的n中沒(méi)有比1大的公因子。圖中的矩陣就是周期為2的矩陣，其轉(zhuǎn)移概率為：因?yàn)楫?dāng)k為奇數(shù)或偶數(shù)時(shí)，其結(jié)果是不一樣的，這樣就達(dá)不到穩(wěn)定狀態(tài)，雖然按公式該方程組是可解的。s1s2s4s31/21/21/21/21/21/21/21/2含義？？39例題：1、如圖所示是一個(gè)相對(duì)碼編碼器，輸入的碼為相對(duì)獨(dú)立的，取值為0或1，且已知輸出的碼為，求其穩(wěn)態(tài)分布。+TXrYr01qqpp相對(duì)編碼器狀態(tài)轉(zhuǎn)移圖40例2、有一二階馬爾可夫鏈其狀態(tài)圖如圖所示，求其穩(wěn)態(tài)分布。s1s2s3s40110(0)1/4(1)1/2(0)1/500(0)1/211(1)4/5(0)3/4(0)1/3(1)2/341概率論知識(shí)復(fù)習(xí)基本事件：隨機(jī)試驗(yàn)的每一個(gè)可能的結(jié)果（樣本點(diǎn)）。樣本空間：基本事件的集合。復(fù)雜事件：多個(gè)基本事件所組成的事件。隨機(jī)事件：無(wú)論基本事件還是復(fù)雜事件，它們?cè)谠囼?yàn)中發(fā)生與否，都帶有隨機(jī)性。事件域：基本事件和復(fù)雜事件是樣本空間的子集，所有子集的的全體。概率空間：三要素—樣本空間、事件域（集合）、概率。先驗(yàn)概率：根據(jù)以往的統(tǒng)計(jì)規(guī)律得到的。42必須掌握的概率論知識(shí)1）條件概率2）聯(lián)合概率433)全概率：設(shè)B1,B2,…是一系列互不相容的事件(BiBj=0），且有B1∪B2∪…=Ω（樣本空間）；p（Bi）＞0，i=1，2，…，則對(duì)任一事件A，有：4)Bayes公式:

設(shè)B1,B2,…是一列互不相容的事件(BiBj=0），且有B1∪B2∪…=Ω（樣本空間）；

p（Bi）＞0，i=1，2，…，則對(duì)任一事件A，有：442.2離散信源熵與互信息信息量自信息量聯(lián)合自信息量條件自信息量單符號(hào)離散信源熵符號(hào)熵條件熵聯(lián)合熵452.2離散信源熵與互信息信息不確定性的消除信息的度量隨機(jī)性、概率相互獨(dú)立符合事件概率相乘、信息相加熵事件集的平均不確定性462.2離散信源熵與互信息自信息定義：對(duì)于給定的離散概率空間表示的信源，x=ai事件所對(duì)應(yīng)的（自）信息為以2為底，單位為比特（bit)以e為底，單位為奈特（nat)1nat=1.433bit以10為底，單位為笛特（det)1det=3.322bit轉(zhuǎn)換關(guān)系如下：1nat=log2e≈1.433bit，1det=log210≈3.322bit47例1若發(fā)出二進(jìn)制碼元0和1信源，當(dāng)符號(hào)概率為p(0)=1/4,p(1)=3/4，則這兩個(gè)符號(hào)所包含的自信息量分別為多少？解：I(0)=-Ib(1/4)=lb4=2bitI(1)=-Ib(3/4)=lb(4/3)=0.415bit可見(jiàn)，因?yàn)?出現(xiàn)的概率小，因而一旦出現(xiàn)，給予觀察者的信息量就很大。482.21自信息量例2英文字母中“e”的出現(xiàn)概率為0.105，“c”的出現(xiàn)概率為０.023，“o”的出現(xiàn)概率為0.001。分別計(jì)算它們的自信息量。解：“e”的自信息量“c”的自信息量“o”的自信息量49自信息量的幾個(gè)性質(zhì)：1）單調(diào)遞減性，若有兩個(gè)事件xi

，xj

其先驗(yàn)概率為p(xi)＜p(xj)，則事件xi

比事件xj有更大的不確定性，同時(shí)會(huì)帶來(lái)更多的信息量；I(xi

)>I(xj

)2）事件xi先驗(yàn)概率p(xi)=1（確定事件）,則不存在不確定性，同時(shí)不會(huì)帶來(lái)信息量，I(xi)=0.3）事件xi先驗(yàn)概率p(xi)=0（不可能事件）,則存在不確定性應(yīng)為無(wú)窮大，同時(shí)會(huì)帶來(lái)無(wú)窮的信息量；I(xi)→∞。4）可加性，兩個(gè)統(tǒng)計(jì)獨(dú)立事件的聯(lián)合自信息量應(yīng)等于它們各自信息量之和;則I(x，

y

)=

I(x)＋I(xiàn)(y

)5）非負(fù)性，自信息量永遠(yuǎn)不可能是負(fù)值，這由概率決定。502.2.2離散信源熵一、信源熵一個(gè)信源X發(fā)出的符號(hào)往往不只一個(gè)，各個(gè)符號(hào)的自信息量不同。信源X發(fā)出某特定符號(hào)提供的自信息量不適合描述信源X發(fā)出隨機(jī)符號(hào)提供的信息量。關(guān)心的是整個(gè)系統(tǒng)的統(tǒng)計(jì)特性，將信源符號(hào)集合的平均不確定度定義為熵。定義信息源的平均不確定度為信源中各個(gè)符號(hào)不確定度的數(shù)學(xué)期望，記作H(X)

其中

H(X)又稱(chēng)為信源X的信源熵（平均自信息量）。512.2.2離散信源熵例3一個(gè)布袋內(nèi)放100個(gè)球，其中80個(gè)球是紅色的，20個(gè)球是白色的，若隨機(jī)摸取一個(gè)球，猜測(cè)其顏色，求平均摸取一次所能獲得的自信息量。這一隨機(jī)事件的概率空間為為紅球，信息量為白球，信息量每次摸出一個(gè)球后又放回袋中，再進(jìn)行下一次摸取。隨機(jī)摸取n次后總共所獲得的信息量為522.2.2離散信源熵平均隨機(jī)摸取一次所獲得的信息量則為

自信息量只是表征信源中各個(gè)符號(hào)的不確定度，一個(gè)信源總是包含著多個(gè)符號(hào)消息，各個(gè)符號(hào)消息又按概率空間的先驗(yàn)概率分布，因而各個(gè)符號(hào)的自信息量就不同。53舉例3、4、5見(jiàn)P1954例題信源一：不等概信源信源二：等概信源熵H(X2)=-0.5log0.5-0.5log0.5=1（比特/符號(hào)）信源三:等概信源熵H(X3)=-4×0.25log0.25=log4=2（比特/符號(hào)）55

信源四：信源為確定事件

熵H(X4)=-0log0–1log1=0

計(jì)算結(jié)果說(shuō)明確定事件的熵為零信源五：一般情況下，二元信源的概率分布為熵H(X)=–δlog

δ-（1-δ）log（1-δ）記H2(δ)=–δlog

δ-（1-δ）log（1-δ）H2(δ)與δ的關(guān)系如圖所示。（如同勢(shì)均力敵的對(duì)手，其戰(zhàn)斗結(jié)果最難預(yù)料）

H2(δ)

00.51δ圖：H2(δ)與δ關(guān)系562.2.2離散信源熵例2.2.3二元信源是離散信源的一個(gè)特例。該信源X輸出符號(hào)只有兩個(gè)，設(shè)為0和1。輸出符號(hào)發(fā)生的概率分別為p和q，p+q=1。即信源的概率空間為可得二元信源熵為二元信源熵為信源信息熵H(X)是概率p的函數(shù)，通常用H(p)表示。函數(shù)曲線如圖572電視畫(huà)面有500×600像素點(diǎn)，10個(gè)灰度等級(jí)，各種畫(huà)面等可能出現(xiàn)，則有n=10300000個(gè)畫(huà)面

H(X)=logn=lg10300000=3×105det/畫(huà)面

=3.322×3×105bit/畫(huà)面

用10000字表寫(xiě)1000字文，各種1000字文等可能出現(xiàn)則有n=100001000=104000篇，

H(X)=lgn=lg104000=4000det/千字文

=3.32×4×103bit/千字文可見(jiàn)，一個(gè)電視畫(huà)面提供的信息量，要比一篇千字文提供的信息量大的多。58二、條件熵在給定yj條件下，xi的條件自信息量為：

I(x

i

|yj)=－logp(xi

|

yj)

集合X的條件熵為：

在給定Y（即各個(gè)yj）條件下，集合X的條件熵定義為：條件熵是條件自信息量的聯(lián)合概率加權(quán)統(tǒng)計(jì)平均值。59三、聯(lián)合熵（共熵）聯(lián)合熵是聯(lián)合符號(hào)集合XY上的每個(gè)元素對(duì)xi

,

yj的自信息量的概率加權(quán)的統(tǒng)計(jì)平均值。2.條件熵與聯(lián)合熵的關(guān)系

I(xi

|yj)=－logp(xi

|

yj)，I(x

i

yj)=－logp(xi

yj)因

全概率公式60所以H(X，Y)=H(X

)＋H(Y|X)同理H(X，Y)=H(Y)＋H(X|Y)

H(X，Y)

H(X)+H(Y)

例題1、P20612.2.5熵的性質(zhì)例2二進(jìn)制通信系統(tǒng)用符號(hào)“0”和“1”，由于存在失真，傳輸時(shí)會(huì)產(chǎn)生誤碼，用符號(hào)表示下列事件：u0：一個(gè)“0”發(fā)出；u1：一個(gè)“1”發(fā)出；v0：一個(gè)“0”收到；v1：一個(gè)“1”收到。給定下列概率：p(u=0)＝1/2，p(v0/u0)＝3/4，p(v0/u1)＝1/2，求

(1)已知發(fā)出一個(gè)“0”，收到符號(hào)后得到的信息量；

(2)已知發(fā)出的符號(hào)，收到符號(hào)后得到的信息量；

(3)知道發(fā)出的和收到的符號(hào)能得到的信息量；

(4)已知收到的符號(hào)，被告知發(fā)出的符號(hào)得到的信息量。622.2.5熵的性質(zhì)解:(1)可求出(2)聯(lián)合概率632.2.5熵的性質(zhì)(3)因?yàn)閜(u0)＝p(u1)＝1/2，所以H(U)＝1比特/符號(hào)，H(UV)=H(U)+H(V/U)=1+0.91=1.91比特/符號(hào).(4)可求出642.2.3互信息簡(jiǎn)單的通信模型

若信源發(fā)出符號(hào)xi，由于信道存在干擾，收到的不是xi而是yi，從yi中獲取有關(guān)xi的信息量稱(chēng)為互信息量，用I(xi;yi)表示。信源X有干擾離散信道信宿Y干擾源65一、單符號(hào)互信息量1、信源發(fā)送符號(hào)xi，同時(shí)信宿接收符號(hào)yj的聯(lián)合概率：

其中：p(xi)為信源符號(hào)xi的先驗(yàn)概率。

p(yj

|xi)為信源符號(hào)xi

已發(fā)送，信宿接收到y(tǒng)j

的條件概率；稱(chēng)為信道的傳遞概率或轉(zhuǎn)移概率或前向概率。注意：p(y

i|xi)是在信源發(fā)送xi的情況下，信宿接收到

yi

的概率，該概率是可通過(guò)統(tǒng)計(jì)獲得的。

2、信宿接收符號(hào)yj的概率

[全概率公式]66

3、信宿接收yj后，推測(cè)信源發(fā)送的符號(hào)是xi的概率（后驗(yàn)概率）：p(xi|yi)[Bayes公式]

674、互信息量定義：后驗(yàn)概率與先驗(yàn)概率比值的對(duì)數(shù)稱(chēng)為互信息量，記為I(xi；yj)

1.當(dāng)p(xi

|yj

)=1，則I(xi;yj)=I(xi)2.當(dāng)xi，yj

互不相關(guān)，p(xi|

yj

)=

p(xi)，則I(xi

;yj)=03.互信息量單位bit685、互信息量的性質(zhì)

I(xi;yj)=I(yj

;xi)I(xi;yj)=I(xi)-I(xi

|yj

)I(xi;yj)=I(xi|

yj

)-I(yi)6、互信息量計(jì)算已知:信源符號(hào)xi的概率p(xi)---先驗(yàn)概率,

信源xi發(fā)送的條件下，信宿接收到y(tǒng)j的概率p(yj

|xi)

互信息量計(jì)算即如何求p(xi|yj)/p(xi)1.聯(lián)合概率

2.全概率

3.后驗(yàn)概率與先驗(yàn)概率之比69例某二元通信系統(tǒng)x0=0，x1=1，信源發(fā)送x0和x1

的概率分別為p(0)=1/2，p(1)=1/2;信宿y0=0,

y1=1

由于信道中有干擾，當(dāng)信源發(fā)送0時(shí)，信宿接收為0的概率p(y0|x0)=p(0|0)=3/4

信宿接收為1的概率p(y1|x0)=p(1|0)=1/4

當(dāng)信源發(fā)送1時(shí)，信宿接收為0的概率p(y0|x1)=p(0|1)=1/5

信宿接收為1的概率p(y1|x1)=p(1|1)=4/5

求互信息量

I(x0;y0),I(x0;y1),I(x0;y1),I(x0;y1)70

x0=0p(0|0)=3/4y0=0

p(0|1)=1/5p(1|0)=1/4x1=1p(1|1)=4/5y1=1

1.聯(lián)合概率

p(x0y0)=p(x0)p(y0|x0)=1/2×3/4=3/8

p(x0y1)=p(x0)p(y1|x0)=1/2×1/4=1/8

p(x1y0)=p(x1)p(y0|x1)=1/2×1/5=1/10p(x1y1)=p(x1)p(y1|x1)=1/2×4/5=4/10

712.全概率

p(y0)=p(x0y0)+p(x1y0)=3/8+1/10=19/40

p(y1)=p(x0y1)+p(x1y1)=1/8+4/10=21/403.后驗(yàn)概率與先驗(yàn)概率之比

p(x0|y0)/p(x0)=p(y0|x0)/p(y0)=3/4÷19/40=30/19p(x0|y1)/p(x0)=p(y1|

x0)/p(y1)=1/4÷21/40=10/21p(x1|y0)/p(x1)=p(y0|x1)/p(y0)=1/5÷19/40=8/19p(x1|y1)/p(x1)=p(y1|x1)/p(y1)=4/5÷21/40=32/21

724.互信息量

I(x0;y0)=log(30/19)bitI(x0;y1)

=log(10/21)bitI(x1;y0)=log(8/19)bitI(x1;y1)=log(32/21)bit73二、

平均互信息量定義互信息量I(xi

;yj)在聯(lián)合概率空間P(XY)上的統(tǒng)計(jì)平均值稱(chēng)平均互信息量,用I(X;Y)表示

平均互信息量單位bit/消息平均互信息量的兩種表示形式：（1）I(X;Y)=H(X)–H(X|Y);(2)I(X;Y)=H(Y)–H(Y|X).還可以得到

I(X;Y)=H(X)+H(Y)–H(XY)74物理意義

1、H(X)是符號(hào)集合X的熵或不確定度

2、H(X|Y)是當(dāng)信宿已收到Y(jié)時(shí)，X的條件熵或不確定度（仍有疑義），表示通信過(guò)程中信息在信道中的損失量，稱(chēng)為信道疑義度或疑義度；

3、H(Y|X)可以看作唯一的確定信道噪聲所需的平均信息量，故稱(chēng)為噪聲熵或散布度；

4、

I(X;Y)表示信宿獲得的凈信息量；75物理含義（續(xù)）從通信的角度來(lái)討論平均互信息量I(X;Y)的物理意義設(shè)X為發(fā)送消息符號(hào)集，Y為接收符號(hào)集，H(X)是輸入集的平均不確定性,H（X︱Y）是觀察到Y(jié)后，集X還保留的不確定性，二者之差I(lǐng)(X;Y)就是在接收過(guò)程中得到的關(guān)于X,Y的平均互信息量。對(duì)于無(wú)擾信道，I(X;Y)=H(X)。對(duì)于強(qiáng)噪信道，I(X;Y)=0。由第一等式I(X;Y)=H（X）-H（X︱Y）看I(X;Y)的物理意義76由第二等式I(X;Y)=H（Y)-H（Y︱X）看I(X;Y)的物理意義對(duì)于無(wú)擾信道，有I(X;Y)=H(X)=H(Y)。對(duì)于強(qiáng)噪信道，有H（Y︱X）=H（Y），從而I(X;Y)=0。H(Y)是觀察到Y(jié)所獲得的信息量，H（Y︱X）是發(fā)出確定消息X后，由于干擾而使Y存在的平均不確定性，二者之差I(lǐng)(X;Y)就是一次通信所獲得的信息量。77通信前，隨機(jī)變量X和隨機(jī)變量Y可視為統(tǒng)計(jì)獨(dú)立，其先驗(yàn)不確定性為H(X)+H(Y)，通信后，整個(gè)系統(tǒng)的后驗(yàn)不確定性為H(XY)，二者之差H(X)+H(Y)-H(XY)就是通信過(guò)程中不確定性減少的量，也就是通信過(guò)程中獲得的平均互信息量I(X;Y)。由第三等式I(X;Y)=H(X)+H(Y)-H(X,Y)看I(X;Y)的物理意義結(jié)論：平均互信息量的大小與信道的傳輸能力有關(guān)：信道噪聲越大，平均互信息量越??；反之，信道噪聲越小，平均互信息量越大。782.2.3互信息疑義度條件熵H(X/Y)信道上的干擾和噪聲所造成的對(duì)信源符號(hào)x的平均不確定度．噪聲熵或散布度條件熵H(Y/X)可看作唯一地確定信道噪聲所需要的平均信息量．如果X與Y是相互獨(dú)立的，無(wú)法從Y中去提取關(guān)于X的信息，即H(X/Y)=H(X)，故稱(chēng)為全損離散信道。如果Y是X的確定的一一對(duì)應(yīng)函數(shù)，I(X;Y)＝H(X)，已知Y就完全解除了關(guān)于X的不確定度，所獲得的信息就是X的不確定度或熵。這可看成無(wú)擾離散信道．疑義度H(X/Y)為零，噪聲熵也為零。在一般情況下，X和Y既非相互獨(dú)立，也不是一一對(duì)應(yīng)，那么從Y獲得X的信息必在零與H(X)之間，即常小于X的熵。792.2.3互信息符號(hào)x與符號(hào)對(duì)yz之間的互信息量定義為條件互信息量是在給定z條件下，x與y之間的互信息量，定義為所以三維聯(lián)合集XYZ上的平均互信息量有I(X;YZ)=I(X;Y)+I(X;Z/Y)Ｉ(YZ;X)=I(Y;X)+I(Z;X/Y)Ｉ(X;YZ)=I(X;ZY)=I(X;Z)+I(X;Y/Z)802.2離散信源熵與互信息例1設(shè)在一正方形棋盤(pán)上共有64個(gè)方格，如果甲將一粒棋子隨意地放在棋盤(pán)中的某方格內(nèi)，讓乙猜測(cè)棋子所在的位置：（1）將方格按順序編號(hào)，令乙猜測(cè)棋子所在方格的順序號(hào)（2）將方格按行和列編號(hào)，甲將棋子所在的方格的行（或列）編號(hào)告訴乙，再令乙猜測(cè)棋子所在列（或行）所在的位置。812.2離散信源熵與互信息解：由于甲將一粒棋子隨意地放在棋盤(pán)中的某方格內(nèi)，因此棋子在棋盤(pán)中所處位置為二維等概率分布（1）聯(lián)合（自）信息量為（2）條件（自）信息量為822.2離散信源熵與互信息例2.一個(gè)布袋內(nèi)放100個(gè)球，其中80個(gè)球?yàn)榧t色，20球?yàn)榘咨Ｈ綦S機(jī)摸取一個(gè)球，猜測(cè)其顏色，求平均摸取一次所獲得的（自）信息量。解：隨機(jī)事件的概率空間為832.2離散信源熵與互信息842.2離散信源熵與互信息Eg1(p23)設(shè)信源發(fā)出8種消息符號(hào)，各消息等概發(fā)送，各符號(hào)分別用3位二進(jìn)碼元表示，并輸出事件。通過(guò)對(duì)輸出事件的觀察來(lái)推測(cè)信源的輸出。假設(shè)信源發(fā)出的消息x4，用二進(jìn)碼011表示，接收到每個(gè)二進(jìn)制碼元后得到有關(guān)x4信息。852.2離散信源熵與互信息862.2.4

數(shù)據(jù)處理中信息的變化I(X;Z)=I(X;Y)+I(X;Z/Y)-I(X;Y/Z)集合符號(hào)替代（X代Y，Y代Z，Z代X）得

I(XY;Z)=I(X;Z)+I(Y;Z/X)將右邊的X和Y互換得

I(XY;Z)=I(Y;Z)+I(X;Z/Y)最后得

I(X;Z)=I(Y;Z)+I(X;Z/Y)-I(Y;Z/X)假設(shè)在Y條件下X與Z相互獨(dú)立，I(X;Z/Y)=0，而且I(X;Y/Z)和I(Y;Z/X)均非負(fù)量，則得出

I(X;Z)≤I(Y;Z)、I(X;Z)≤I(X;Y)信息不增性：數(shù)據(jù)處理過(guò)程中只會(huì)失掉一些信息，絕不會(huì)創(chuàng)造出新的信息．872.2離散信源熵與互信息熵的性質(zhì)對(duì)稱(chēng)性非負(fù)性確定性香農(nóng)輔助定理最大熵定理?xiàng)l件熵小于無(wú)條件熵882.2離散信源熵與互信息非負(fù)性892.2離散信源熵與互信息對(duì)稱(chēng)性902.2離散信源熵與互信息確定性

香農(nóng)輔助定理912.2離散信源熵與互信息最大熵定理

條件熵小于無(wú)條件熵922.2離散信源熵與互信息平均互信息與熵的關(guān)系932.2離散信源熵與互信息互信息量與熵的關(guān)系94

2.3離散序列信源的熵離散無(wú)記憶序列信源離散有記憶序列信源馬爾可夫信源離散無(wú)記憶信源的序列熵離散有記憶信源的序列熵95

2.3離散序列信源的熵離散無(wú)記憶序列信源布袋摸球?qū)嶒?yàn)，若每次取出兩個(gè)球，由兩個(gè)球的顏色組成的消息就是符號(hào)序列。若先取出一個(gè)球，記下顏色放回布袋，再取另一個(gè)球。96

2.3離散序列信源的熵離散有記憶序列信源布袋摸球?qū)嶒?yàn)，每次取出兩個(gè)球，由兩個(gè)球的顏色組成的消息就是符號(hào)序列。若先取出一個(gè)球，記下顏色不放回布袋，再取另一個(gè)球。97

2.3離散序列信源的熵馬爾可夫信源當(dāng)信源的記憶長(zhǎng)度為m+1時(shí)，該時(shí)該發(fā)出的符號(hào)與前m個(gè)符號(hào)有關(guān)聯(lián)性，而與更前面的符號(hào)無(wú)關(guān)。98

2.3離散序列信源的熵馬爾可夫信源由于高階馬爾可夫信源需要引入矢量進(jìn)行分析，現(xiàn)方法將矢量轉(zhuǎn)化為狀態(tài)變量。定義狀態(tài)：信源在某一時(shí)刻出現(xiàn)符號(hào)概率xj與信源此時(shí)所處狀態(tài)si有關(guān)，用條件概率表示p(xj/si),狀態(tài)轉(zhuǎn)移概率表示為p(sj/si)99

2.3離散序列信源的熵馬爾可夫信源更一般，經(jīng)過(guò)n-m步后轉(zhuǎn)移至sj的概率100

2.3離散序列信源的熵馬爾可夫信源特別關(guān)心n-m=1情況，pij(m,m+1)101

2.3離散序列信源的熵馬爾可夫信源系統(tǒng)在任一時(shí)刻可處于狀態(tài)空間的任意一狀態(tài)，狀態(tài)轉(zhuǎn)移時(shí)，轉(zhuǎn)移概率是一個(gè)矩陣，一步轉(zhuǎn)移轉(zhuǎn)移矩陣為102

2.3離散序列信源的熵馬爾可夫信源k步轉(zhuǎn)移概率pij(k)與l步和k-l步轉(zhuǎn)移概率之間滿足切普曼-柯?tīng)柲宸蚍匠?。定義：如果從狀態(tài)I轉(zhuǎn)移到狀態(tài)j的概率與m無(wú)關(guān)，則稱(chēng)這類(lèi)MovKov鏈為齊次對(duì)于齊次馬爾可夫鏈，一步轉(zhuǎn)移概率完全決定了k步轉(zhuǎn)移概率。103

2.3離散序列信源的熵馬爾可夫信源定義：若齊次馬爾可夫鏈對(duì)一切I,j存在不依賴(lài)于I的極限，則稱(chēng)其具有遍歷性，pj稱(chēng)為平穩(wěn)分布104

2.3離散序列信源的熵馬爾可夫信源定理：設(shè)有一齊次馬爾可夫鏈，其狀態(tài)轉(zhuǎn)移矩陣為P，其穩(wěn)態(tài)分布為wj105

2.3離散序列信源的熵不可約性，對(duì)于任意一對(duì)I和j，都存在至少一個(gè)k，使pij(k)>0.非周期性，所有pij(n)>0的n中沒(méi)有比1大的公因子。定理：設(shè)P是某一馬爾可夫鏈的狀態(tài)轉(zhuǎn)移矩陣，則該穩(wěn)態(tài)分布存在的充要條件是存在一個(gè)正整數(shù)N，使矩陣PN中的所有元素均大于零。106

2.3離散序列信源的熵Eg.一個(gè)相對(duì)編碼器，求平穩(wěn)分布107

2.3離散序列信源的熵Eg.二階馬氏鏈，X{0,1},求平穩(wěn)分布起始狀態(tài)000110111/201/401/203/4001/301/