信息論第二章

信息論第二章第一頁，共四十六頁，2022年，8月28日2數(shù)字通信系統(tǒng)模型信道信源信源編碼加密信道編碼干擾源信宿信源解碼解密信道解碼加密密鑰解密密鑰uxykzvz'y'x'第二頁，共四十六頁，2022年，8月28日32.1信源的描述和分類2.2離散信源熵和互信息2.3離散序列信源的熵2.4連續(xù)信源的熵和互信息2.5冗余度內(nèi)容第三頁，共四十六頁，2022年，8月28日4重難點(diǎn)本章重點(diǎn)

信源的統(tǒng)計(jì)特性和數(shù)學(xué)模型、離散信源熵及其性質(zhì)、互信息本章難點(diǎn)馬爾科夫信源、離散序列有記憶信源的熵2.1信源的描述和分類2.2離散信源熵和互信息2.3離散序列信源的熵2.4連續(xù)信源的熵和互信息2.5冗余度第四頁，共四十六頁，2022年，8月28日52.1信源的描述和分類第五頁，共四十六頁，2022年，8月28日內(nèi)容2.1.1無記憶信源2.1.2有記憶信源2.1.3馬爾科夫信源6第六頁，共四十六頁，2022年，8月28日7信源信源產(chǎn)生消息(符號(hào))、消息序列和連續(xù)消息的來源產(chǎn)生隨機(jī)變量、隨機(jī)序列和隨機(jī)過程的源。在通信系統(tǒng)中收信者在未收到消息以前對(duì)信源發(fā)出什么消息是不確定的,是隨機(jī)的，所以可用隨機(jī)變量、隨機(jī)序列或隨機(jī)過程來描述信源輸出的消息,或者說用一個(gè)樣本空間及其概率測(cè)度—概率空間來描述信源信源的基本特性：具有隨機(jī)不確定性。第七頁，共四十六頁，2022年，8月28日8香農(nóng)信息論的基本點(diǎn)用隨機(jī)變量或隨機(jī)矢量來表示信源用概率論和隨機(jī)過程的理論來研究信息第八頁，共四十六頁，2022年，8月28日9一、信源分類2、離散信源：文字、數(shù)字、數(shù)據(jù)等符號(hào){離散無記憶信源離散有記憶信源{{發(fā)出單個(gè)符號(hào)的無記憶信源發(fā)出符號(hào)序列的無記憶信源發(fā)出符號(hào)序列的有記憶信源發(fā)出符號(hào)序列的馬爾可夫信源1、連續(xù)信源：語音、圖像、圖形從信源發(fā)出的消息在時(shí)間上和幅度上的分布第九頁，共四十六頁，2022年，8月28日10根據(jù)人們對(duì)信源消息的感知分為數(shù)據(jù)信源、文本信源、語音信源、圖像信源等，其中文本信源和語音信源都是針對(duì)人類語言、文字、聲樂等感知的，又通稱為自然語信源。從描述信源消息的隨機(jī)過程的平穩(wěn)性角度分為平穩(wěn)信源和非平穩(wěn)信源第十頁，共四十六頁，2022年，8月28日11信源的分類方法可以有多種，但本質(zhì)上主要基于兩方面的考慮：一是信源消息取值的集合以及消息取值時(shí)刻的集合，由此可分為離散信源、連續(xù)信源等；二是信源消息的統(tǒng)計(jì)特性，由此可分為無記憶（Memoryless）信源、有記憶（Memory）源、平穩(wěn)信源、非平穩(wěn)信源、高斯信源、馬爾可夫信源等。第十一頁，共四十六頁，2022年，8月28日122.1.1無記憶信源一、發(fā)出單個(gè)符號(hào)的無記憶離散信源：發(fā)出的消息是離散的，且一個(gè)符號(hào)代表一條完整的消息。消息數(shù)為有限或無限可列。用一維離散變量X來描述。例如扔骰子，每次試驗(yàn)結(jié)果必然是1～6點(diǎn)中的某一個(gè)面朝上。用一個(gè)離散型隨機(jī)變量X來描述這個(gè)信源輸出的消息。第十二頁，共四十六頁，2022年，8月28日13在實(shí)際情況中，存在著很多這樣的信源、例如投硬幣、書信文字、計(jì)算機(jī)的代碼、電報(bào)符號(hào)、阿拉伯?dāng)?shù)字碼等等。這些信源輸出的都是單個(gè)符號(hào)（或代碼）的消息，它們符號(hào)集的取值是有限的或可數(shù)的。第十三頁，共四十六頁，2022年，8月28日14信源的描述一個(gè)離散信源發(fā)出的各個(gè)符號(hào)消息的集合為：它們的概率分別為p(xi):xi的先驗(yàn)概率單符號(hào)離散信源的數(shù)學(xué)模型—概率空間a,b,c,…z第十四頁，共四十六頁，2022年，8月28日15二、發(fā)出單個(gè)符號(hào)的連續(xù)無記憶信源：輸出是的單個(gè)符號(hào)的消息，消息的數(shù)量是無限的?？捎靡痪S連續(xù)型隨機(jī)變量X描述單符號(hào)連續(xù)無記憶信源的概率空間消息的集合

隨機(jī)取一節(jié)干電池測(cè)其電壓值作為輸出符號(hào),符號(hào)取值為[0,1.5]之間的所有實(shí)數(shù)。

該信源就是發(fā)出單符號(hào)的連續(xù)無記憶信源第十五頁，共四十六頁，2022年，8月28日16上述的離散信源和連續(xù)信源是最簡單最基本的情況，信源輸出只輸出一個(gè)消息符號(hào)，所以可以用隨機(jī)變量來描述。信源的描述第十六頁，共四十六頁，2022年，8月28日17三、發(fā)出符號(hào)序列的信源：輸出的消息由符號(hào)序列組成，用隨機(jī)矢量X=(X1X2…Xl…XL)描述。需要用聯(lián)合概率分布表示信源特性。

L=2，X=(X1,X2)，其信源的概率空間為第十七頁，共四十六頁，2022年，8月28日18信源的描述隨機(jī)序列的概率—聯(lián)合概率當(dāng)信源無記憶時(shí)，即Xl(l=1,…,L)之間是無依賴的、統(tǒng)計(jì)獨(dú)立的，則隨機(jī)矢量的聯(lián)合概率分布滿足：第十八頁，共四十六頁，2022年，8月28日19離散信源X(n個(gè)信源符號(hào))的每次輸出L長符號(hào)序列消息x=(x1…xl…xL)x共有nL=n×n×…×n（共L個(gè)）種組合，即每個(gè)隨機(jī)變量取值有n種，那么L個(gè)隨機(jī)變量組成的隨機(jī)序列，其樣值共有nL種可能取值。有時(shí)將這種由信源X輸出的L長隨機(jī)序列X所描述的信源叫做離散信源X的L次擴(kuò)展信源。L次擴(kuò)展信源第十九頁，共四十六頁，2022年，8月28日20一般情況下,信源在不同時(shí)刻發(fā)出的符號(hào)之間是相互依賴的，也就是信源輸出的平穩(wěn)隨機(jī)序列X中，各隨機(jī)變量Xl之間是有依賴的。如在漢字序列中前后文字的出現(xiàn)是有依賴的，不能認(rèn)為是彼此不相關(guān)的。

有記憶信源第二十頁，共四十六頁，2022年，8月28日21離散有記憶序列信源：當(dāng)信源輸出的隨機(jī)矢量中各個(gè)分量之間不相互獨(dú)立而可以是任意相關(guān)的,則稱此類信源為有記憶信源。布袋摸球?qū)嶒?yàn)，每次取出兩個(gè)球，由兩個(gè)球的顏色組成的消息就是符號(hào)序列。若每次先取出一個(gè)球，記下顏色不放回布袋，再取第二個(gè)球。第二十一頁，共四十六頁，2022年，8月28日22表述有記憶信源要比表述無記憶信源困難得多需在N維隨機(jī)矢量的聯(lián)合概率分布中，引入條件概率分布來說明它們之間的關(guān)聯(lián)。第二十二頁，共四十六頁，2022年，8月28日232.1.3馬爾可夫信源馬爾可夫信源一類相對(duì)簡單的離散平穩(wěn)有記憶信源該信源在某一時(shí)刻發(fā)出字母的概率除與該字母有關(guān)外,只與此前發(fā)出的有限個(gè)字母有關(guān)m階馬爾可夫信源：信源輸出某一符號(hào)的概率僅與以前的m個(gè)符號(hào)有關(guān)，而與更前面的符號(hào)無關(guān)。條件概率一階馬爾可夫信源：第二十三頁，共四十六頁，2022年，8月28日24馬氏鏈的狀態(tài)變量若把前面有限個(gè)字母記作一個(gè)狀態(tài)S，則信源某一時(shí)刻發(fā)出某一字母的概率除與該字母有關(guān)外，只與該時(shí)刻信源所處的狀態(tài)有關(guān)。信源將來的狀態(tài)及其送出的字母將只與信源現(xiàn)在的狀態(tài)有關(guān)，而與信源過去的狀態(tài)無關(guān)。引入狀態(tài)變量的好處：使得高階馬爾科夫過程可以轉(zhuǎn)化為一階馬爾科夫過程處理。假設(shè)m階馬爾可夫信源的一個(gè)狀態(tài)含有m個(gè)字母第二十四頁，共四十六頁，2022年，8月28日25馬氏鏈的基本概念令si

=(xi1,

xi2,

…xim)xi1,,xi2,

…xim

∈{a1,

a2,

…an}狀態(tài)集S={s1,s2,…,sQ}Q=nm（狀態(tài)數(shù)目）信源輸出的隨機(jī)符號(hào)序列為：x1,x2,…xi-1,xi…信源所處的隨機(jī)狀態(tài)序列為：s1,s2,…si-1,si

…例：二元序列為…01011100…考慮m=2，Q=nm=22=4s1=00s2=01s3=10s4=11變換成對(duì)應(yīng)的狀態(tài)序列為

…s2s3s2s4s4s3s1……01011100…第二十五頁，共四十六頁，2022年，8月28日26轉(zhuǎn)移概率設(shè)信源在時(shí)刻m處于si狀態(tài),它在下一時(shí)刻(m+1)狀態(tài)轉(zhuǎn)移到sj的轉(zhuǎn)移概率為：

pij(m)=p{Sm+1=sj|Sm=si}=p{sj|si}pij(m)：基本轉(zhuǎn)移概率（一步轉(zhuǎn)移概率）齊次馬爾可夫鏈：pij(m)與m的取值無關(guān),則

pij=p{Sm+1=sj|Sm=si}=p{S2=sj|S1=si}pij具有下列性質(zhì)：

pij≥0第二十六頁，共四十六頁，2022年，8月28日27若信源處于某一狀態(tài)si,當(dāng)它發(fā)出一個(gè)符號(hào)后,所處狀態(tài)就變了,任何時(shí)候信源處于什么狀態(tài)完全由前一時(shí)刻的狀態(tài)和發(fā)出符號(hào)決定。系統(tǒng)在任一時(shí)刻可處于狀態(tài)空間S={s1,s2,…,sQ}中的任意一個(gè)狀態(tài),狀態(tài)轉(zhuǎn)移時(shí),轉(zhuǎn)移概率矩陣符號(hào)條件概率矩陣區(qū)別第二十七頁，共四十六頁，2022年，8月28日28例2-1，如圖所示是一個(gè)相對(duì)碼編碼器,輸入的碼Xr(r=1,2,…)是相互獨(dú)立的，取值0或1，且已知P(X=0)=p,P(X=1)=1－p=q，輸出的碼是Yr。TXrYrYr-1+Yr是一個(gè)二元一階馬氏鏈,Yr確定后,Yr+1概率分布只與Yr有關(guān),與Yr-1

、Yr-2…等無關(guān)。注：⊕模2加第二十八頁，共四十六頁，2022年，8月28日29sos1pqqpp00=P(Y2=0/Y1=0)=P(X=0)=p狀態(tài)轉(zhuǎn)移矩陣與時(shí)刻無關(guān)，所以是齊次的。Yr的狀態(tài)轉(zhuǎn)移概率：p01=P(Y2=1/Y1=0)=P(X=1)=qp10=P(Y2=0/Y1=1)=P(X=1)=qp11=P(Y2=1/Y1=1)=P(X=0)=p

第二十九頁，共四十六頁，2022年，8月28日30馬爾可夫信源狀態(tài)轉(zhuǎn)移圖齊次馬爾可夫鏈可以用其狀態(tài)轉(zhuǎn)移圖(香農(nóng)線圖)表示每個(gè)圓圈代表一種狀態(tài)

狀態(tài)之間的有向線代表某一狀態(tài)向另一狀態(tài)的轉(zhuǎn)移有向線一側(cè)的符號(hào)和數(shù)字分別代表發(fā)出的符號(hào)和條件概率sos11/0.60/0.30/0.4s21/0.20/0.81/0.7第三十頁，共四十六頁，2022年，8月28日例2設(shè)一個(gè)二元一階馬爾科夫信源，信源符號(hào)集X={0,1}，信源輸出符號(hào)的條件概率為p(0|0)=0.25,p(0|1)=0.5,p(1|0)=0.75,p(1|1)=0.5求狀態(tài)轉(zhuǎn)移概率，畫出狀態(tài)轉(zhuǎn)移圖。解：311/0.750/0.51/0.5第三十一頁，共四十六頁，2022年，8月28日例3設(shè)有一個(gè)二元二階馬爾科夫信源，其信源符號(hào)集X={0,1}.狀態(tài)變化如下：在狀態(tài)為01時(shí)，若出現(xiàn)0，將零附到01后將第一位0擠出，狀態(tài)變?yōu)?0.其他狀態(tài)變化過程類似。信源輸出符號(hào)的條件概率為P(0|00)=p(1|11)=0.8,p(1|00)=p(0|11)=0.2，p(0|01)=p(0|10)=p(1|01)=p(1|10)=0.5求狀態(tài)轉(zhuǎn)移概率矩陣，畫出狀態(tài)轉(zhuǎn)移圖解：32第三十二頁，共四十六頁，2022年，8月28日33010/0.80/0.51/0.20/0.51/0.51/0.50/0.21/0.8第三十三頁，共四十六頁，2022年，8月28日34齊次馬爾可夫鏈中的狀態(tài)可以根據(jù)其性質(zhì)進(jìn)行分類:1、如狀態(tài)si經(jīng)若干步后總能到達(dá)狀態(tài)sj，即存在k,使pij(k)＞0，則稱si可到達(dá)sj;若兩個(gè)狀態(tài)相互可到達(dá),則稱此二狀態(tài)相通；2、過渡態(tài)：一個(gè)狀態(tài)經(jīng)過若干步以后總能到達(dá)某一其他狀態(tài)，但不能從其他狀態(tài)返回；3、吸收態(tài)：不能到達(dá)其他任何狀態(tài)的狀態(tài)；4、常返態(tài)：經(jīng)有限步后遲早要返回的狀態(tài)；5、周期性的：在常返態(tài)中，狀態(tài)中僅當(dāng)k能被某整數(shù)d＞1整除時(shí)才有pii(k)＞0；6、非周期性的：對(duì)于pii(k)＞0的所有k值，其最大公約數(shù)為1。第三十四頁，共四十六頁，2022年，8月28日35s3s2s4s5s1s6周期性的：在常返態(tài)中,狀態(tài)中僅當(dāng)k能被某整數(shù)d＞1整除時(shí)才有pii(k)＞0,圖中的周期為2；x5:1非周期性的：對(duì)于pii(k)＞0的所有k值，其最大公約數(shù)為1。常返態(tài)：經(jīng)有限步后遲早要返回的狀態(tài)，x4:1x3:1/2x2:1/2x3:1/2x2:1/2x2:1/2x4:1/4x1:1/4x6:1x6:1/4過渡態(tài)吸收態(tài)相通第三十五頁，共四十六頁，2022年，8月28日36馬爾可夫信源遍歷狀態(tài)：非周期的常返狀態(tài),如圖中的狀態(tài)s2和s3閉集：狀態(tài)空間中的某一子集中的任何一狀態(tài)都不能到達(dá)子集以外的任何狀態(tài)不可約的：閉集中除自身全體外再?zèng)]有其他閉集特殊結(jié)論第三十六頁，共四十六頁，2022年，8月28日37馬爾可夫信源一個(gè)不可約的、非周期的、狀態(tài)有限的馬爾可夫鏈其k步轉(zhuǎn)移概率pij(k)在k→∞時(shí)趨于一個(gè)和初始狀態(tài)無關(guān)的極限概率Wj，它是滿足方程組的唯一解；Wj

：馬爾可夫鏈的一個(gè)平穩(wěn)分布，

Wj[或p(sj)]就是系統(tǒng)此時(shí)處于狀態(tài)sj的概率。無論隨機(jī)點(diǎn)從哪一個(gè)狀態(tài)si出發(fā)，當(dāng)轉(zhuǎn)移的步數(shù)k足夠大時(shí)，轉(zhuǎn)移到狀態(tài)sj的概率pij(k)都近似于一個(gè)常數(shù)Wj第三十七頁，共四十六頁，2022年，8月28日38sos11/0.60/0.30/0.4s21/0.20/0.81/0.7例4：求馬爾科夫鏈的穩(wěn)態(tài)分布律第三十八頁，共四十六頁，2022年，8月28日39例5：有一個(gè)二元二階馬爾可夫信源,其信源符號(hào)集為{0，1}，已知符號(hào)條件概率：

p(0|00)=1/2p(1|00)=1/2p(0|01)=1/3p(1|01)=2/3p(0|10)=1/4p(1|10)=3/4p(0|11)=1/5p(1|11)=4/5求：⑴信源全部狀態(tài)及狀態(tài)轉(zhuǎn)移概率⑵畫出完整的二階馬爾可夫信源狀態(tài)轉(zhuǎn)移圖。⑶求穩(wěn)定后的狀態(tài)分布概率以及符號(hào)分布概率

第三十九頁，共四十六頁，2022年，8月28日40狀態(tài)轉(zhuǎn)移概率矩陣符號(hào)條件概率矩陣(1)1/2(0)1/2(0)1/3(1)2/300011110s2s1s4s3(1)3/4(0)1/4(0)1/5(1)4/5第四十頁，共四十六頁，2022年，8月28日41穩(wěn)態(tài)分布概率穩(wěn)態(tài)后的符號(hào)概率分布第四十一頁，共四十六頁，2022年，8月28日42例6

一個(gè)二元二階馬爾可夫信源,其信源符號(hào)集為{0,1}信源開始時(shí)：p(0)=p(1)=0.5發(fā)出隨機(jī)變量X1。

下一單位時(shí)間：輸出隨機(jī)變量X2與X1有依賴關(guān)系x2x10100.30.410.70.6p(x2|x1)再下一單位時(shí)間：輸出隨機(jī)變量X3與X2X1有依賴關(guān)系x3x1x20001101100.40.20.30.410.60.80.70.6p(x3|x1x2)第四十二頁，共四十六頁，2022年，8月28日從第四單位時(shí)間開始，隨機(jī)變量Xi只與前面二個(gè)單位時(shí)間的隨機(jī)變量Xi-2Xi-1有依賴關(guān)系:p(xi|xi-1

xi-2…x2

x1)=p(xi|xi-1

xi-2)(i＞3)且

p(xi|xi-1

xi-2)=p(x3|x2x1)(i＞3)求：⑴信源狀態(tài)轉(zhuǎn)移情況和相應(yīng)概率；⑵畫出完整的二階馬爾可夫信源狀態(tài)轉(zhuǎn)移圖；⑶求平穩(wěn)分布概率；

（4）馬爾科夫信源達(dá)到穩(wěn)定后，0和1的分布概率。

第四十三頁，共四十六頁，2022年，8月28日44練習(xí)2-12-2第四十四頁，共四十六頁，2022年，8月28日45馬爾可夫鏈馬爾可夫鏈，因安德烈?馬爾可夫（，1856－1922）得名，是數(shù)學(xué)