第2講離散信源數(shù)學(xué)模型及其信息測度PPT課件

1、信源信源信道信道信宿信宿噪聲源噪聲源編碼器編碼器譯碼器譯碼器消息消息干擾干擾接收信號接收信號消息消息數(shù)字通信系統(tǒng)模型有效性、可靠性有效性、可靠性Review發(fā)送信號發(fā)送信號第1頁/共50頁第2頁/共50頁信源的數(shù)學(xué)描述信源的數(shù)學(xué)描述 通信系統(tǒng)中收信者在未收到消息以前對通信系統(tǒng)中收信者在未收到消息以前對信源發(fā)出什么消息是不確定的信源發(fā)出什么消息是不確定的,是隨機(jī)的是隨機(jī)的可用可用隨機(jī)變量、隨機(jī)序列或隨機(jī)過程隨機(jī)變量、隨機(jī)序列或隨機(jī)過程來來描述信源輸出的消息描述信源輸出的消息,或者說用一個(gè)樣本或者說用一個(gè)樣本空間及其概率測度空間及其概率測度概率空間概率空間來描述信來描述信源。源。第3頁/共50頁

2、不同的信源輸出的消息的不同的信源輸出的消息的隨機(jī)性質(zhì)隨機(jī)性質(zhì)不同，可以根不同，可以根據(jù)消息的不同的隨機(jī)性質(zhì)來對信源進(jìn)行分類：據(jù)消息的不同的隨機(jī)性質(zhì)來對信源進(jìn)行分類：按照某時(shí)刻信源輸出消息的取值集合的離散性和連按照某時(shí)刻信源輸出消息的取值集合的離散性和連續(xù)性續(xù)性, 信源可分為信源可分為離散信源離散信源和和連續(xù)信源。連續(xù)信源。按照信源輸出消息的所對應(yīng)的隨機(jī)序列中隨機(jī)變量按照信源輸出消息的所對應(yīng)的隨機(jī)序列中隨機(jī)變量前后之間有無依賴關(guān)系前后之間有無依賴關(guān)系, 信源可分為信源可分為無記憶信源無記憶信源和和有有記憶信源記憶信源。 按照信源輸出消息的所對應(yīng)的隨機(jī)序列的平穩(wěn)性按照信源輸出消息的所對應(yīng)的隨機(jī)序列

3、的平穩(wěn)性, 信源可分為信源可分為平穩(wěn)信源平穩(wěn)信源和和非平穩(wěn)信源非平穩(wěn)信源。信源的分類信源的分類第4頁/共50頁 離散信源離散信源：可能輸出的消息是有限的或可數(shù)：可能輸出的消息是有限的或可數(shù)的，每次只輸出一個(gè)消息，即兩兩不相容。的，每次只輸出一個(gè)消息，即兩兩不相容。 數(shù)學(xué)模型數(shù)學(xué)模型：)(,),(),(,)(,.,110110110qqqaPaPaPaaaxPXaaaX1)(10, 1)(0:10qiiiaPqiaP且滿足注：X代表隨機(jī)變量，指的是信源整體；ai代表信源的某個(gè)元素。簡單信源簡單信源第5頁/共50頁 數(shù)學(xué)模型：1)()(),()(badxxpxpbaxpX并滿足注：這里的p(x)代

4、表概率密度函數(shù)。簡單信源簡單信源 連續(xù)信源連續(xù)信源：可能輸出的消息數(shù)是無限的或不可：可能輸出的消息數(shù)是無限的或不可數(shù)的，每次只輸出一個(gè)消息。數(shù)的，每次只輸出一個(gè)消息。第6頁/共50頁離散信源在不同時(shí)刻發(fā)出的符號之間是無依賴的離散信源在不同時(shí)刻發(fā)出的符號之間是無依賴的彼此統(tǒng)計(jì)獨(dú)立的。彼此統(tǒng)計(jì)獨(dú)立的。)(,),(),(,)(110110qqaPaPaPaaaxPX其中，其中，110,qiaaaAa且101)(qiiaP離散無記憶信源第7頁/共50頁1012111101101)()()()() 1, 1 , 0,(,),()(,),(),(,)(21121NkNkNNNqiiNkiiiiiNkNki

5、iiiqqiNPaPaaaPPqiiiqiiaaaPPPPX并滿足：其中由離散無記憶信源輸出N長的隨機(jī)序列構(gòu)成的信源。離散無記憶信源N次擴(kuò)展信源4/ 14/ 14/ 14/ 111100100PX擲兩枚硬幣擲兩枚硬幣擲一枚硬幣擲一枚硬幣011/2 1/2XP 第8頁/共50頁 離散平穩(wěn)信源：輸出的隨機(jī)序列 中每個(gè)隨機(jī)變量 取值是離散的，并且隨機(jī)矢量X的各維概率分布不隨時(shí)間平移而改變。 連續(xù)平穩(wěn)信源：輸出的隨機(jī)序列 中每個(gè)隨機(jī)變量 取值是連續(xù)的，并且隨機(jī)矢量X的各維概率密度函數(shù)不隨時(shí)間平移而改變 離散無記憶信源：離散信源在不同時(shí)刻發(fā)出的符號之間是彼此統(tǒng)計(jì)獨(dú)立的。)(21NXXXX其它幾種常見信源

6、), 1(NiXi)(X21NXXX), 1(NiXi第9頁/共50頁 有記憶信源有記憶信源：輸出的隨機(jī)序列輸出的隨機(jī)序列X中各隨機(jī)變量之間中各隨機(jī)變量之間有依賴關(guān)系，但記憶長度有限。有依賴關(guān)系，但記憶長度有限。 m階馬爾可夫信源階馬爾可夫信源：信源每次發(fā)出的符號只與前：信源每次發(fā)出的符號只與前m個(gè)符號有關(guān)，與更前面的符號無關(guān)。個(gè)符號有關(guān)，與更前面的符號無關(guān)。 隨機(jī)波形信源隨機(jī)波形信源：信源輸出的消息在時(shí)間上和取值上：信源輸出的消息在時(shí)間上和取值上都是連續(xù)的。都是連續(xù)的。其它幾種常見信源第10頁/共50頁 設(shè)單符號離散信源的概率空間為設(shè)單符號離散信源的概率空間為)(,),(),(,)(2121

7、nnxpxpxpxxxxPX1)(, 1)(0:1niiixpxp且滿足自信息量定義 如果知道事件xi已發(fā)生，則該事件所給出的信息量稱為自信息，定義為:1,)(log)(1log)(axpxpxIiaiai第11頁/共50頁對數(shù)換底關(guān)系：aXXbbalogloglog自信息量定義 I (xi) 含義 當(dāng)事件xi發(fā)生以前,表示事件xi 發(fā)生的不確定性 當(dāng)事件xi發(fā)生以后,表示事件xi所含有的信息量 I (xi)單位 常用對數(shù)底是2,信息量的單位為比特(bits)； 若取自然對數(shù),則信息量的單位為奈特(nats); 1 natlog2e l.433 bit，aXXbablogloglog或或第12

8、頁/共50頁(1) I (xi)是非負(fù)值(2) 當(dāng)p(xi) = 1時(shí)，I(xi) = 0(3) 當(dāng)p(xi) = 0時(shí)，I(xi) = (4) I(xi)是先驗(yàn)概率p(xi)的單調(diào)遞減函數(shù)，即 當(dāng)p(x1)p(x2)時(shí)，I (x1)I (x2)(5)兩個(gè)獨(dú)立事件的聯(lián)合信息量等于它們分別的信息量之和，即統(tǒng)計(jì)獨(dú)立信源的信息量等于它們分別的信息量之和。自信息的性質(zhì)第13頁/共50頁 二進(jìn)制碼元二進(jìn)制碼元0,1,當(dāng)符號概率為當(dāng)符號概率為p(0)=1/4, p(1)=3/4,則這兩個(gè)符號的自信息量為：則這兩個(gè)符號的自信息量為： I(0) =-log2 (1/4)=log24= 2 bits I(1)

9、=-log2 (3/4) =0.4151 bits一個(gè)以等概率出現(xiàn)的二進(jìn)制碼元(0,1)所包含的自信息量為： 自信息量例題I(0)= I(1)= -log2 (1/2)=log22=1 bits第14頁/共50頁自信息量例題一次擲兩個(gè)色子，求下列事件發(fā)生后提供的信息量。一次擲兩個(gè)色子，求下列事件發(fā)生后提供的信息量。a.僅有一個(gè)為僅有一個(gè)為3；b.至少有一個(gè)為至少有一個(gè)為4；c.兩個(gè)之和為偶數(shù)。兩個(gè)之和為偶數(shù)。解：一個(gè)色子有6個(gè)符號，X=1,2,3,4,5,6，兩個(gè)色子的總數(shù)為36。a. 事件概率為5*2/36=5/18b. 事件概率為（52+1）/36=11/36c. 事件概率為63/36=1

10、/2則： I(a)=log(18/5)=1.848 (bits) I(b)=log(36/11)=1.7105 (bits) I(c)=log2=1 (bits)第15頁/共50頁考慮兩個(gè)隨機(jī)事件，其聯(lián)合概率空間考慮兩個(gè)隨機(jī)事件，其聯(lián)合概率空間為為1)(, 1)(0)(,),(),(,),(,)(11121111212111nimjjijimnmmnnmmyxpyxpyxpyxpyxpyxpyxyxyxyxyxyxXYPXY)(log)(jijiyxpyxI聯(lián)合自信息與條件自信息 在事件yj出現(xiàn)的條件下，隨機(jī)事件xi發(fā)生的 條件自信息量 )/(log)/(jijiyxpyxI條件自信息量 聯(lián)合

11、自信息量第16頁/共50頁 聯(lián)合自信息量和條件自信息量關(guān)系聯(lián)合自信息量和條件自信息量關(guān)系2222()log()log()()log()log()()()ijijijijijI x yp x yp xp yp xp yI xI y )/()()/()(log)/()()/()(log)(log)(jijjijijiijijijiyxIyIyxpywxyIxIxypxqyxpyxI當(dāng)X和Y獨(dú)立時(shí)，第17頁/共50頁 信源各個(gè)離散消息的信源各個(gè)離散消息的自信息量的數(shù)學(xué)期望自信息量的數(shù)學(xué)期望（即概率加（即概率加權(quán)的統(tǒng)計(jì)平均值）為信源的平均信息量，稱為信源的信權(quán)的統(tǒng)計(jì)平均值）為信源的平均信息量，稱為信源

12、的信息熵，也叫信源熵或香農(nóng)熵，簡稱熵。息熵，也叫信源熵或香農(nóng)熵，簡稱熵。 熵函數(shù)的自變量是熵函數(shù)的自變量是X表示信源整體，實(shí)質(zhì)上是離散無記憶信源平均不確表示信源整體，實(shí)質(zhì)上是離散無記憶信源平均不確定度的度量。定度的度量。與自信息不同與自信息不同,自信息表示某一消息所含有的信息量，它是自信息表示某一消息所含有的信息量，它是一個(gè)隨機(jī)變量一個(gè)隨機(jī)變量,不能用它來作為整個(gè)信源的信息測度。不能用它來作為整個(gè)信源的信息測度。 )(log)()(1log)()(1iniiiixpxpxpExIEXH信源熵定義第18頁/共50頁信源熵H(X)的物理含義 信源輸出后，每個(gè)離散消息所提供的平均信息量； 信源輸出前

13、，信源的平均不確定度； （反映了隨機(jī)變量X的隨機(jī)性） 對該信源輸出進(jìn)行無錯(cuò)編碼所需的最小編碼長度; 消除信源不確定度所需要的信息的量度.信源熵理解0limlog0,0 log 00zzz定 義注意注意:第19頁/共50頁 電視屏上約有電視屏上約有 500 600= 3105個(gè)格點(diǎn)，按每個(gè)格點(diǎn)，按每格點(diǎn)有格點(diǎn)有8個(gè)不同的灰度等級考慮，則共能組成個(gè)不同的灰度等級考慮，則共能組成 個(gè)不同的畫面。個(gè)不同的畫面。53 10221( )( )log( )log 1/8niiiH Xp xp x= 9 105 bits51038信源熵例題按等概率計(jì)算，平均每個(gè)畫面可提供的信息量為 第20頁/共50頁 有一篇

14、千字文章，假定每字可從萬字表中任選，則有一篇千字文章，假定每字可從萬字表中任選，則共有不同的千字文共有不同的千字文 N=100001000=104000 篇篇 仍按等概率仍按等概率1/100001000計(jì)算，平均每篇千字文可計(jì)算，平均每篇千字文可提供的提供的 信息量為信息量為 H(X) log2N 1.3 104 bits “一個(gè)電視畫面”平均提供的信息量遠(yuǎn)遠(yuǎn)超過“一篇千字文”提供的信息量。 信源熵例題第21頁/共50頁 例如有兩個(gè)信源，其概率空間分別為例如有兩個(gè)信源，其概率空間分別為: :01. 099. 0,)(21xxxpX5 . 05 . 0,)(21yyypYbitXH08. 001

15、. 0log01. 099. 0log99. 0)(bitYH15 .0log5 .05 .0log5 .0)(因?yàn)镠(Y) H(X) 所以信源Y比信源X的平均不確定性要大。 信源熵例題第22頁/共50頁 該信源該信源X輸出符號只有兩個(gè)輸出符號只有兩個(gè),設(shè)為設(shè)為0和和1輸出符號發(fā)輸出符號發(fā)生的概率分別為生的概率分別為p和和q，pq=l，即信源的概率空，即信源的概率空間為間為 qpPX10 則二元信源熵為 H(X)= -plogp-qlogq = -plogp- (1- p)log(1-p) = H(p) 信源熵例題第23頁/共50頁0 0.2 0.4 0.6 0.8 110.80.60.40.

16、2pH(p)H(p) = -plogp- (1- p)log(1-p)第24頁/共50頁條件熵是在聯(lián)合符號集合條件熵是在聯(lián)合符號集合XY上的上的條件自信息量的數(shù)學(xué)期望條件自信息量的數(shù)學(xué)期望。在已知隨機(jī)變量在已知隨機(jī)變量Y的條件下，隨機(jī)變量的條件下，隨機(jī)變量X的條件熵定義為：的條件熵定義為：)/(log)()/()()/()/(1111jimjnijijimjnijijiyxpyxpyxIyxpyxIEYXH 要用聯(lián)合概率加權(quán)條件熵是一個(gè)確定值，表示信宿在收到條件熵是一個(gè)確定值，表示信宿在收到Y(jié)后，信源后，信源X仍然存仍然存在的不確定度。這是傳輸失真所造成的。有時(shí)稱在的不確定度。這是傳輸失真所造

17、成的。有時(shí)稱H(X/Y)為為信道疑義度信道疑義度，也稱損失熵。稱條件熵，也稱損失熵。稱條件熵H(Y/X)為為噪聲熵噪聲熵。)/(log)()/()/(211ijnimjjiijxypyxpxyIEXYH條件熵第25頁/共50頁聯(lián)合離散符號集合聯(lián)合離散符號集合XY上的每個(gè)元素對上的每個(gè)元素對 的的聯(lián)合自信聯(lián)合自信息量的數(shù)學(xué)期望息量的數(shù)學(xué)期望。)(log)()()()(jinimjjijinimjjiyxpyxpyxIyxpXYH21111)/(log)()/()()/(kjiijkkjikjiijkkjizyxpzyxpzyxIzyxpZXYH2 )(jiyx聯(lián)合熵進(jìn)一步擴(kuò)展進(jìn)一步擴(kuò)展第26頁/

18、共50頁)()()()()(YXHYHXYHXHXYHNnnnNNNUUUUHUUUUHUUUHUUHUHUUUH112112121312121)()()()()()(熵、條件熵、聯(lián)合熵關(guān)系當(dāng)當(dāng)Ui相互獨(dú)立時(shí)相互獨(dú)立時(shí)121()()NNinH U UUH U當(dāng)當(dāng)X和和Y相互獨(dú)立時(shí)相互獨(dú)立時(shí)()()( )H XYH XH Y第27頁/共50頁 一個(gè)二進(jìn)信源一個(gè)二進(jìn)信源X發(fā)出符號集發(fā)出符號集0,1,經(jīng)過離散無記憶信經(jīng)過離散無記憶信道傳輸?shù)纻鬏?信道輸出用信道輸出用Y表示表示.由于信道中存在噪聲由于信道中存在噪聲,接收接收端除收到端除收到0和和1的符號外的符號外,還有不確定符號還有不確定符號“2”

19、已知已知: X的先驗(yàn)概率的先驗(yàn)概率: p(x0)=2/3, p(x1)= 1/3, 符號轉(zhuǎn)移概率：符號轉(zhuǎn)移概率： p(y0|x0)=3/4, p(y2|x0)=1/4 p(y1|x1)=1/2, p(y2|x1)=1/2，XY0101 23/41/21/21/4信源熵H(X)bitsHXH92. 031log3132log32)31,32()(例 題第28頁/共50頁得聯(lián)合概率：得聯(lián)合概率： p(x0y0) = p(x0) p(y0 |x0) = 2/33/4 = 1/2 p(x0y1) = p(x0) p(y1 |x0) = 0 p(x0y2) = p(x0) p(y2 |x0) = 2/3

20、1/4 = 1/6 p(x1y0) = p(x1) p(y0 |x1) = 0 p(x1y1) = p(x1) p(y1 |x1) = 1/31/2=1/6 p(x1y2) = p(x1) p(y2 |x1) = 1/31/2=1/6)/()()/()()(jijijijiyxpypxypxpyxpbitsxypyxpXYHijijji88. 021log6121log6141log6143log21)|(log),()|(由由例 題 噪聲熵噪聲熵 H(Y|X)XY0101 23/41/21/21/4第29頁/共50頁 聯(lián)合熵聯(lián)合熵 H(XY) H(XY)H(X)H(Y|X)=1.8 bits

21、)()(),()(11imjjijnijixpyxpypyxp得 p(y0) = p(xiy0) = p(x0y0) +p(x1y0) =1/2+0 = 1/2 p(y1) = p(xiy1) = p(x0y1) +p(x1y1) = 0+1/6 =1/6 p(y2) = p(xiy2) = p(x0y2) +p(x1y2) = 1/6+1/6=1/3 由由bitsHYH47. 161log6131log3121log21)61,31,21()(例 題信道輸出熵H(Y)第30頁/共50頁)()()()()|(1jjinijijijiypyxpyxpyxpyxp由由12/12/1)()()|(0

22、0000ypyxpyxp得得同理同理 p(x0 |y1)=0 ； p(x1 |y1)=1 p(x0 |y2)=1/2； p(x1 |y2)=1/20)()()|(00101ypyxpyxpbitsyxpyxpYXHjiijji33. 0)|(log),()|( 信道疑義度信道疑義度 H(X|Y)例 題或 H(X|Y)= H(XY)-H(Y)=1.8-1.47=0.33bit第31頁/共50頁KkkkKpppppHXH121log),()(),.,2 , 1(0, 11KkppkKkk熵的基本性質(zhì)KKpppxxxPX2121概率矢量概率矢量熵函數(shù)熵函數(shù)第32頁/共50頁非負(fù)性 非負(fù)性 H(X)0

23、 由于由于0pk1,所以所以logpk0，-logpk0，則總有則總有H(X)0。1( )logKkkkHppP第33頁/共50頁 對稱性對稱性),.,(),.,(12121KKKppppHpppH根據(jù)加法交換律可以證明，當(dāng)變量交換順序時(shí)熵函數(shù)的值不變, 即信源的熵只與概率空間的總體結(jié)構(gòu)有關(guān)，而與各概率分量對應(yīng)的狀態(tài)順序無關(guān)。 對稱性1( )logKkkkHppP第34頁/共50頁確定性當(dāng)信源X的信源空間X，P中，任一概率分量等于1，根據(jù)完備空間特性，其它概率分量必為0，這時(shí)信源為一個(gè)確知信源，其熵為0。 確定性HHH( , )( , )( , , ,. )1001100001( )logKk

24、kkHppP第35頁/共50頁),(),(lim21210KKKKpppHpppH這說明信源空間中增加某些概率很小的符號，這說明信源空間中增加某些概率很小的符號，雖然當(dāng)發(fā)出這些符號時(shí)，提供很大的信息量，雖然當(dāng)發(fā)出這些符號時(shí)，提供很大的信息量，但由于其概率接近于但由于其概率接近于0，在信源熵中占極小的，在信源熵中占極小的比重，比重， ，使信源熵保持不變。，使信源熵保持不變。 0loglim20 擴(kuò)展性擴(kuò)展性1( )logKkkkHppP第36頁/共50頁 可加性可加性)/()()()/()()(YXHYHXYHXYHXHXYH1)/()/()()(:)/()()/()/()(log)()/(lo

25、g)()(log)/()()/()(log)()(log)()(22222jijijijijijiiiijijjiiijijiijiijjijiijjixypxypxpyxpXYHXHXYHxypxpxpxypyxpxpxypxpxypxpyxpyxpyxpXYH利用證明證明: :可加性第37頁/共50頁 極值性極值性最大離散熵定理最大離散熵定理 ()logH XK信源信源X中包含中包含K個(gè)不同離散消息時(shí)，信源個(gè)不同離散消息時(shí)，信源熵熵 ，當(dāng)且僅當(dāng)，當(dāng)且僅當(dāng)X中各個(gè)消息中各個(gè)消息出現(xiàn)的概率全相等時(shí)，上式取等號。出現(xiàn)的概率全相等時(shí)，上式取等號。 表明等概信源的不確定性最大，具有最表明等概信源的不

26、確定性最大，具有最大熵，為大熵，為 log K極值性()logH XK第38頁/共50頁H(p)1.00.5 0 0.5 1 p 二元離散信源H(p) = -plogp- (1- p)log(1-p)第39頁/共50頁引理引理1（常用對數(shù)不等式）：常用對數(shù)不等式）：lnx x-1,當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)x=1時(shí)等號成立。時(shí)等號成立。令f(x)=lnx(x-1) ,則 11)(xxf可見，f(x)是x的上凸函數(shù)，且當(dāng)x=1時(shí)，f(x)有極大值。故 01)(2 xxf即 lnx(x-1)f(x)=lnx-(x-1) 0 證明：證明：第40頁/共50頁11loglogKKkkkkkkpppq 11Kkkp

27、1,1KkkqKkkkKKqppppH121log),(KkkkKkkkqppp11loglogKkkkkKkkkkpqpepqp11lnloglog0log1log111KkkKkkKkkkkpqepqpe 令令 ，可得，可得 即等概時(shí)熵最大，為即等概時(shí)熵最大，為 。證明：證明：Kqk1log K引理2香農(nóng)輔助定理12(,)logKKHp ppK12(,)KKHp pp第41頁/共50頁 極值性極值性最大離散熵定理最大離散熵定理 ()logH XK信源信源X中包含中包含K個(gè)不同離散消息時(shí)，信源個(gè)不同離散消息時(shí)，信源熵熵 ，當(dāng)且僅當(dāng)，當(dāng)且僅當(dāng)X中各個(gè)消息中各個(gè)消息出現(xiàn)的概率全相等時(shí)，上式取等號。出現(xiàn)的概率全相等時(shí)，上式取等號。 表明等概信源的不確定性最大，具有最表明等概信源的不確定性最大，具有最大熵，為大熵，為 log K極值性()logH XK第42頁/共50頁定理：1. H(X/Y) H(X) （條件熵不大于無條件熵） 2. H(XY) H(X)+H(Y)證明：基本定理,( )(/)()