2.2 多符號離散信源的熵.ppt

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