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

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