《信息論與編碼》課件

1、第2章 信源與信息熵信源描述與分類離散信源的信息熵和互信息離散序列信源的熵連續(xù)信源的熵與互信息冗余度12.1信源的描述與分類信源是產(chǎn)生消息（符號(hào)）、消息序列和連續(xù)消息的來源。從數(shù)學(xué)上，由于消息的不確定性，因此，信源是產(chǎn)生隨機(jī)變量、隨機(jī)序列和隨機(jī)過程的源信源的基本特性是具有隨機(jī)不確定性22.1信源特性與分類分類時(shí)間 離散 連續(xù)幅度 離散 連續(xù)記憶 有 無三大類：?jiǎn)畏?hào)離散信源符號(hào)序列信源（有記憶和無記憶）連續(xù)信源3 2.1信源特性與分類離散無記憶序列信源布袋摸球?qū)嶒?yàn)，若每次取出兩個(gè)球，由兩個(gè)球的顏色組成的消息就是符號(hào)序列。若先取出一個(gè)球，記下顏色放回布袋，再取另一個(gè)球。42.1信源特性與分類離散

2、有記憶序列信源布袋摸球?qū)嶒?yàn)，每次取出兩個(gè)球，由兩個(gè)球的顏色組成的消息就是符號(hào)序列。若先取出一個(gè)球，記下顏色不放回布袋，再取另一個(gè)球。52.1信源特性與分類馬爾可夫信源當(dāng)信源的記憶長度為m+1時(shí)，該時(shí)該發(fā)出的符號(hào)與前m個(gè)符號(hào)有關(guān)聯(lián)性，而與更前面的符號(hào)無關(guān)。62.1信源描述與分類描述：通過概率空間描述單符號(hào)離散信源例如：對(duì)二進(jìn)制數(shù)字與數(shù)據(jù)信源72.1信源描述與分類連續(xù)信源82.1信源描述與分類離散序列信源以3位PCM信源為例92.1信源描述與分類當(dāng)p=1/2102.1信源描述與分類離散無記憶序列信源布袋摸球?qū)嶒?yàn)，若每次取出兩個(gè)球，由兩個(gè)球的顏色組成的消息就是符號(hào)序列。若先取出一個(gè)球，記下顏色放回布

3、袋，再取另一個(gè)球。112.1信源描述與分類離散有記憶序列信源布袋摸球?qū)嶒?yàn)，每次取出兩個(gè)球，由兩個(gè)球的顏色組成的消息就是符號(hào)序列。若先取出一個(gè)球，記下顏色不放回布袋，再取另一個(gè)球。122.1信源描述與分類馬爾可夫信源當(dāng)信源的記憶長度為m+1時(shí)，該時(shí)該發(fā)出的符號(hào)與前m個(gè)符號(hào)有關(guān)聯(lián)性，而與更前面的符號(hào)無關(guān)。132.1信源描述與分類馬爾可夫信源由于高階馬爾可夫信源需要引入矢量進(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)142.1信源描述與分類馬爾可夫信源更一般，經(jīng)過n-m步后

4、轉(zhuǎn)移至sj的概率15 2.1信源描述與分類馬爾可夫信源特別關(guān)心n-m=1情況，pij(m,m+1)16 2.1信源描述與分類馬爾可夫信源系統(tǒng)在任一時(shí)刻可處于狀態(tài)空間的任意一狀態(tài)，狀態(tài)轉(zhuǎn)移時(shí)，轉(zhuǎn)移概率是一個(gè)矩陣， 一步轉(zhuǎn)移轉(zhuǎn)移矩陣為17 2.1信源描述與分類馬爾可夫信源k步轉(zhuǎn)移概率pij(k)與l步和k-l步轉(zhuǎn)移概率之間滿足切普曼-柯爾莫郭洛夫方程。定義：如果從狀態(tài)I轉(zhuǎn)移到狀態(tài)j的概率與m無關(guān)，則稱這類MovKov鏈為齊次對(duì)于齊次馬爾可夫鏈，一步轉(zhuǎn)移概率完全決定了k步轉(zhuǎn)移概率。18 2.1信源描述與分類馬爾可夫信源定義：若齊次馬爾可夫鏈對(duì)一切I,j存在不依賴于I的極限，則稱其具有遍歷性，pj稱為

5、平穩(wěn)分布192.1信源描述與分類馬爾可夫信源定理：設(shè)有一齊次馬爾可夫鏈，其狀態(tài)轉(zhuǎn)移矩陣為P，其穩(wěn)態(tài)分布為wj202.1信源描述與分類不可約性，對(duì)于任意一對(duì)I和j， 都存在至少一個(gè)k，使pij(k)0.非周期性，所有pij(n)0的n中沒有比1大的公因子。定理：設(shè)P是某一馬爾可夫鏈的狀態(tài)轉(zhuǎn)移矩陣，則該穩(wěn)態(tài)分布存在的充要條件是存在一個(gè)正整數(shù)N，使矩陣PN中的所有元素均大于零。212.1信源描述與分類Eg. 一個(gè)相對(duì)編碼器，求平穩(wěn)分布22 2.1信源描述與分類Eg. 二階馬氏鏈，X0,1,求平穩(wěn)分布起始狀態(tài)000110111/201/401/203/4001/301/502/304/5S1(00)S

6、2(01)S3(10)S4(11)232.2離散信源熵與互信息信息量自信息量聯(lián)合自信息量條件自信息量單符號(hào)離散信源熵符號(hào)熵條件熵聯(lián)合熵242.2離散信源熵與互信息信息不確定性的消除信息的度量隨機(jī)性、概率相互獨(dú)立符合事件概率相乘、信息相加熵事件集的平均不確定性252.2離散信源熵與互信息直觀推導(dǎo)信息測(cè)度信息I應(yīng)該是消息概率p的遞降函數(shù)由兩個(gè)不同的消息（相互統(tǒng)計(jì)獨(dú)立）所提供的信息等于它們分別提供信息之和（可加性）262.2離散信源熵與互信息定義：對(duì)于給定的離散概率空間表示的信源，x=ai事件所對(duì)應(yīng)的（自）信息為以2為底，單位為比特（bit)以e為底，單位為奈特（nat) 1nat=1.433bit

7、以10為底，單位為笛特（det) 1det=3.322bit272.2離散信源熵與互信息定義：聯(lián)合概率空間中任一聯(lián)合事件的聯(lián)合（自）信息量為：定義：聯(lián)合概率空間中，事件x在事件y給定條件下的條件（自）信息量為：282.2離散信源熵與互信息聯(lián)合自信息、條件自信息與自信息間的關(guān)系292.2離散信源熵與互信息Eg1 設(shè)在一正方形棋盤上共有64個(gè)方格，如果甲將一粒棋子隨意地放在棋盤中的某方格內(nèi)，讓乙猜測(cè)棋子所在的位置：（1）將方格按順序編號(hào)，令乙猜測(cè)棋子所在方格的順序號(hào) （2）將方格按行和列編號(hào)，甲將棋子所在的方格的行（或列）編號(hào)告訴乙，再令乙猜測(cè)棋子所在列（或行）所在的位置。302.2離散信源熵與互

8、信息解：由于甲將一粒棋子隨意地放在棋盤中的某方格內(nèi)，因此棋子在棋盤中所處位置為二維等概率分布（1）聯(lián)合（自）信息量為 （2）條件（自）信息量為312.2離散信源熵與互信息Eg2. 一個(gè)布袋內(nèi)放100個(gè)球，其中80個(gè)球?yàn)榧t色，20球?yàn)榘咨?。若隨機(jī)摸取一個(gè)球，猜測(cè)其顏色，求平均摸取一次所獲得的（自）信息量。解：隨機(jī)事件的概率空間為322.2離散信源熵與互信息332.2離散信源熵與互信息單符號(hào)離散信源熵定義：對(duì)于給定離散概率空間表示的信源所定義的隨機(jī)變量I的數(shù)學(xué)期望為信源的信息熵，單位為比特/符號(hào)342.2離散信源熵與互信息離散信源條件熵定義：對(duì)于給定離散概率空間表示的信源所定義的隨機(jī)變量I（x/y

9、)在集合X上的數(shù)學(xué)期望為給定y條件下信源的條件熵，單位為比特/序列352.2離散信源熵與互信息離散信源聯(lián)合熵定義：對(duì)于給定離散概率空間表示的信源所定義的隨機(jī)變量I（x，y)的數(shù)學(xué)期望為集合X和集合Y的信源聯(lián)合熵，單位為比特/序列362.2離散信源熵與互信息聯(lián)合熵、條件熵與熵的關(guān)系372.2離散信源熵與互信息單符號(hào)離散信源互信息定義：對(duì)于給定離散概率空間表示的信源，在出現(xiàn)y事件后所提供有關(guān)事件x的信息量定義互信息，單位為比特382.2離散信源熵與互信息單符號(hào)離散信源互信息392.2離散信源熵與互信息條件互信息量與聯(lián)合互信息量定義：對(duì)于給定離散概率空間表示的信源，在事件z給定條件下，事件x與事件y

10、之間的條件互信息量為：402.2離散信源熵與互信息條件互信息量與聯(lián)合互信息量定義：對(duì)于給定離散概率空間表示的信源，在事件x與聯(lián)合事件yz之間的聯(lián)合互信息量為：412.2離散信源熵與互信息Eg1(p23) 設(shè)信源發(fā)出8種消息符號(hào)，各消息等概發(fā)送，各符號(hào)分別用3位二進(jìn)碼元表示，并輸出事件。通過對(duì)輸出事件的觀察來推測(cè)信源的輸出。假設(shè)信源發(fā)出的消息x4，用二進(jìn)碼011表示， 接收到每個(gè)二進(jìn)制碼元后得到有關(guān)x4信息。422.2離散信源熵與互信息432.2離散信源熵與互信息平均互信息量 其中442.2離散信源熵與互信息熵的性質(zhì)對(duì)稱性非負(fù)性確定性香農(nóng)輔助定理最大熵定理?xiàng)l件熵小于無條件熵452.2離散信源熵與

11、互信息非負(fù)性462.2離散信源熵與互信息對(duì)稱性472.2離散信源熵與互信息確定性 香農(nóng)輔助定理482.2離散信源熵與互信息最大熵定理 條件熵小于無條件熵492.2離散信源熵與互信息平均互信息的性質(zhì)非負(fù)性互易性與熵和條件熵及聯(lián)合熵關(guān)系極值性凸性函數(shù)性質(zhì)信息不增性原理502.2離散信源熵與互信息非負(fù)性512.2離散信源熵與互信息互易性522.2離散信源熵與互信息平均互信息與熵的關(guān)系532.2離散信源熵與互信息互信息量與熵的關(guān)系542.2離散信源熵與互信息極值性552.2離散信源熵與互信息凸性函數(shù)當(dāng)條件概率分布給定時(shí)，平均互信息量是輸入概率分布的上凸函數(shù)當(dāng)集合X的概率分布保持不變時(shí)，平均互信息量是條

12、件概率分布的下凸函數(shù)562.2離散信源熵與互信息信息不增性57 2.3離散序列信源的熵離散無記憶信源的序列熵離散有記憶信源的序列熵58 2.3離散序列信源的熵離散無記憶信源的序列熵59 2.3離散序列信源的熵離散無記憶信源的序列熵平均每個(gè)符號(hào)熵（消息熵）60 2.3離散序列信源的熵離散有記憶信源的序列熵和消息熵61 2.3離散序列信源的熵Eg 求信源的序列熵和平均符號(hào)熵 a1a2a3a1a2a39/111/802/113/42/901/87/962 2.3離散序列信源的熵離散有記憶信源的序列熵和消息熵結(jié)論1 是L的單調(diào)非增函數(shù)結(jié)論2結(jié)論3 是L的單調(diào)非增函數(shù)結(jié)論463 2.3離散序列信源的熵馬氏鏈極限熵64 2.3離散序列信源的熵65 2.3離散序列信源的熵Eg 求馬氏鏈平均符號(hào)熵（三個(gè)狀態(tài)）66 2.4連續(xù)信源的熵與互信息幅度連續(xù)的單個(gè)符號(hào)信源熵67 2.4連續(xù)信源的熵與互信息幅度連續(xù)的單個(gè)符號(hào)信源