2.2 多符號(hào)離散信源的熵.ppt

1 第2章信源熵 2 本章主要內(nèi)容 2 1單符號(hào)離散信源2 2多符號(hào)離散平穩(wěn)信源及熵2 3連續(xù)信源及熵 3 本節(jié)教學(xué)內(nèi)容 基本要求 1 教學(xué)內(nèi)容多符號(hào)離散序列信源及其熵馬爾可夫信源及其熵信息的冗余度2 基本要求掌握多符號(hào)離散序列信源熵的定義 性質(zhì)掌握馬爾可夫信源熵的模型及其計(jì)算掌握信息冗余度的含義 4 2 2多符號(hào)離散平穩(wěn)信源及熵 實(shí)際的信源輸出的消息是時(shí)間或空間上離散的一系列隨機(jī)變量 這類(lèi)信源每次輸出的不是一個(gè)單個(gè)的符號(hào) 而是一個(gè)符號(hào)序列 如電報(bào)系統(tǒng) 在信源輸出的序列中 每一位出現(xiàn)哪個(gè)符號(hào)都是隨機(jī)的 這種信源稱(chēng)為多符號(hào)離散信源 二元系統(tǒng)中 我們可以把兩個(gè)二元數(shù)字看成一組 會(huì)出現(xiàn)四種可能情況 00 01 10和11 我們可以把這四種情況看成一個(gè)新的信源稱(chēng)為二元無(wú)記憶信源的二次擴(kuò)展信源 相應(yīng)的 如果把N個(gè)二元數(shù)字看成一組 則新的信源稱(chēng)為二元無(wú)記憶信源的N次擴(kuò)展信源 5 如信源序列 000 001 111稱(chēng)為二元信源的3次擴(kuò)展信源 二元信源的N次擴(kuò)展信源 n元信源的N次擴(kuò)展信源 多符號(hào)離散信源 的定義 輸出消息長(zhǎng)度為N 消息中的每個(gè)符號(hào)取自集合X X中有n個(gè)單符號(hào)消息 則X的N次擴(kuò)展信源記作 XN 用N維矢量表示 N位 則該信源XN最多有nN條消息 6 平穩(wěn)隨機(jī)序列 所謂平穩(wěn)是指序列的統(tǒng)計(jì)性質(zhì)與時(shí)間的推移無(wú)關(guān) 非平穩(wěn)隨機(jī)序列 信源每發(fā)一個(gè)符號(hào)的概率與時(shí)間起點(diǎn)有關(guān) 離散無(wú)記憶信源 信源序列的前后符號(hào)之間是統(tǒng)計(jì)獨(dú)立的 離散有記憶信源 信源序列的前后符號(hào)之間是相關(guān)的 7 序列信息的熵 序列信息的熵 也稱(chēng) 離散無(wú)記憶信源的N次擴(kuò)展信源的熵 原始信源X的數(shù)學(xué)模型XN的數(shù)學(xué)模型 8 H XN NH X 證明 略例 p40頁(yè)求一個(gè)信源的二次擴(kuò)展信源及其熵 注意 單位 9 離散平穩(wěn)有記憶信源的N次擴(kuò)展信源的熵 離散平穩(wěn)有記憶信源的N次擴(kuò)展信源的熵離散有記憶信源的N次擴(kuò)展信源 信源輸出的符號(hào)相關(guān) 且相關(guān)性用N個(gè)符號(hào)間的聯(lián)合概率表示 離散平穩(wěn)有記憶信源的N次擴(kuò)展信源 記憶長(zhǎng)度為N 的熵滿(mǎn)足 10 例 設(shè)某二維離散信源X X1X2的原始信源X的模型為 符號(hào)間的相關(guān)性用以下的條件概率 轉(zhuǎn)移概率 表示 求原始信源熵H X 條件熵H X2 X1 二次擴(kuò)展信源熵及其平均符號(hào)熵 11 解 代入上式 1 206 1 542驗(yàn)證結(jié)論成立 說(shuō)明 多符號(hào)消息的平均符號(hào)熵小于等于信源熵 這是由于符號(hào)之間的統(tǒng)計(jì)相關(guān)性造成的 要想提高信源對(duì)外提供的平均符號(hào)信息量 必須設(shè)法消除符號(hào)之間的相關(guān)性 冗余度 12 N維離散有記憶信源的N次擴(kuò)展信源的極限熵 也稱(chēng)為 離散平穩(wěn)有記憶信源的N次擴(kuò)展信源的極限熵 13 14 馬爾可夫信源的極限熵 在許多信源的輸出序列中 符號(hào)之間的依賴(lài)關(guān)系是有限的 即 任何時(shí)刻信源符號(hào)發(fā)生的概率只與前面已經(jīng)發(fā)出的若干符號(hào)相關(guān) 而與更前面發(fā)出的符號(hào)無(wú)關(guān) 如 隨機(jī)變量序列中 m 1 時(shí)刻發(fā)出的隨機(jī)變量Xm 1只和前面已經(jīng)發(fā)出的m個(gè)隨機(jī)變量X1X2 Xm有關(guān) 而與更前面的隨機(jī)變量無(wú)關(guān) Xi取值于單符號(hào)信源符號(hào)集合X這類(lèi)信源稱(chēng)為m階馬爾可夫信源 也叫 m 1 次擴(kuò)展信源 m階馬爾可夫信源每次只發(fā)一個(gè)符號(hào) 每次發(fā)出的符號(hào)只與之前發(fā)出的m個(gè)符號(hào)相關(guān) 15 馬爾可夫信源的組成需要兩個(gè)條件 1 某時(shí)刻信源輸出的符號(hào)只與之前的m個(gè)符號(hào)相關(guān) 這m個(gè)相關(guān)的符號(hào)稱(chēng)為 信源前一時(shí)刻所處的狀態(tài) m階馬爾可夫信源在時(shí)刻i發(fā)符號(hào) 16 2 某時(shí)刻信源所處的狀態(tài)由該時(shí)刻輸出的符號(hào)和前一時(shí)刻的狀態(tài)唯一確定 問(wèn) m階馬爾可夫信源最多有多少種狀態(tài) nm 17 m階馬爾可夫信源的數(shù)學(xué)模型 且滿(mǎn)足 18 m階馬爾可夫信源的熵 19 則 馬爾可夫極限熵的計(jì)算式 20 例 已知一個(gè)二進(jìn)制一階馬爾可夫信源 信源符號(hào)集合為X 0 1 符號(hào)間的條件概率為P 0 0 0 25P 1 0 0 75P 0 1 0 5P 1 1 0 5求狀態(tài)轉(zhuǎn)移概率和狀態(tài)轉(zhuǎn)移圖 信源熵 解 因?yàn)槭嵌M(jìn)制一階馬爾可夫信源所以共有nm 21 2種狀態(tài) S1 0 S2 1 狀態(tài)轉(zhuǎn)移概率為P S1 S1 0 25P S2 S1 0 75P S1 S2 0 5P S2 S2 0 5 21 狀態(tài)轉(zhuǎn)移圖如下 S1 0 S2 1 0 75 0 5 0 5 0 25 22 該一階馬爾可夫信源極限熵為 23 狀態(tài)概率 注 狀態(tài)概率一定要列方程組求解 24 例 已知一個(gè)二進(jìn)制二階馬爾可夫信源 信源符號(hào)集合為X 0 1 狀態(tài)轉(zhuǎn)移圖符合 P 0 00 P 1 11 0 8P 1 00 P 0 11 0 2P 0 01 P 1 01 P 0 10 P 1 10 0 5求狀態(tài)轉(zhuǎn)移概率和極限熵 25 P S1 S1 P S4 S4 0 8P S2 S1 P S3 S4 0 2P S3 S2 P S4 S2 P S1 S3 P S2 S3 0 5 解 因?yàn)槭嵌M(jìn)制二階馬爾可夫信源所以共有nm 22 4種狀態(tài) S1 00 S2 01 S3 10 S4 11狀態(tài)轉(zhuǎn)移概率為P 0 00 P 1 11 0 800001111P 1 00 P 0 11 0 200011110P 0 01 P 1 01 P 0 10 P 1 10 0 501100111 發(fā)0 發(fā)1 發(fā)1 發(fā)0 發(fā)0 發(fā)1 P S1 S1 P S4 S4 0 8 P S2 S1 P S3 S4 0 2 P S3 S2 P S4 S2 0 5 P S1 S3 P S2 S3 0 5 26 狀態(tài)轉(zhuǎn)移圖如下 27 該二階馬爾可夫信源的極限熵為 28 29 比較m階馬爾可夫信源和消息長(zhǎng)度為m的有記憶信源m階馬爾可夫信源 盡管該信源的記憶長(zhǎng)度為m 但符號(hào)間的依賴(lài)關(guān)系延伸到無(wú)窮 用狀態(tài)轉(zhuǎn)移概率來(lái)描述這種依賴(lài)關(guān)系 其熵為極限熵Hm 1 表示馬爾可夫信源以轉(zhuǎn)移概率發(fā)出每個(gè)符號(hào)提供的信息量 消息長(zhǎng)度為m的有記憶信源 符號(hào)間的依賴(lài)關(guān)系僅限于每一個(gè)長(zhǎng)度為m的消息 而消息之間是統(tǒng)計(jì)獨(dú)立的 故其熵記作 30 信源的相關(guān)性和冗余度不同記憶長(zhǎng)度 例m階馬氏信源的記憶長(zhǎng)度為 m 的離散平穩(wěn)信源的熵其中n為原始信源集合的符號(hào)個(gè)數(shù) 說(shuō)明 記憶長(zhǎng)度m越長(zhǎng) 極限熵越小 越接近實(shí)際信源 31 信源熵的相對(duì)率 信源效率 實(shí)際熵與最大熵的比值信源冗余度 意義 針