信息論與編碼-第5講-信源及其信息量4-馬爾科夫信源

第1頁(yè)2024/4/14第二章信源及其信息量本章重點(diǎn)：信源的統(tǒng)計(jì)特性和數(shù)學(xué)模型、各類信源的信息測(cè)度—熵及其性質(zhì)。2.1單符號(hào)離散信源2.2多符號(hào)離散平穩(wěn)信源2.3連續(xù)信源2.4離散無(wú)失真信源編碼定理2.5小結(jié)ElectronicsEngineeringDepartment,XXXXXxxXxxx第2頁(yè)2024/4/142.2多符號(hào)離散平穩(wěn)信源2.2.1多符號(hào)離散平穩(wěn)信源2.2.2離散平穩(wěn)無(wú)記憶信源2.2.3離散平穩(wěn)有記憶信源2.2.4馬爾可夫信源2.2.5信源冗余度第3頁(yè)2024/4/142.2.4馬爾可夫信源(1)馬爾可夫信源的定義(2)

m

階馬爾可夫信源(3)舉例2.2多符號(hào)離散平穩(wěn)信源第4頁(yè)2024/4/142.2.4馬爾可夫信源(1)馬爾可夫信源的定義①信源的狀態(tài)和符號(hào)集②馬爾可夫鏈③時(shí)齊的馬爾可夫鏈④馬爾可夫信源定義⑤結(jié)論2.2多符號(hào)離散平穩(wěn)信源第5頁(yè)2024/4/142.2.4馬爾可夫信源(1)馬爾可夫信源的定義①信源的狀態(tài)和符號(hào)集有一類信源，輸出的符號(hào)序列中符號(hào)之間的依賴關(guān)系是有限的，即任何時(shí)刻信源符號(hào)發(fā)生的概率只與前面已經(jīng)發(fā)出的若干個(gè)符號(hào)有關(guān)，而與更前面發(fā)出的符號(hào)無(wú)關(guān)。設(shè)符號(hào)集為

X

，狀態(tài)為

S。信源輸出的信息符號(hào)還與信源所處的狀態(tài)有關(guān)。狀態(tài)S∈{s1,s2,…,sJ}

符號(hào)X∈{x1,x2,…,xn}

每一時(shí)刻信源發(fā)出一個(gè)符號(hào)后，所處的狀態(tài)將發(fā)生轉(zhuǎn)移。2.2多符號(hào)離散平穩(wěn)信源第6頁(yè)2024/4/142.2.4馬爾可夫信源(1)馬爾可夫信源的定義①信源的狀態(tài)和符號(hào)集2.2多符號(hào)離散平穩(wěn)信源圖2.2.2二元二階馬爾科夫信源狀態(tài)轉(zhuǎn)移圖第7頁(yè)2024/4/142.2.4馬爾可夫信源(1)馬爾可夫信源的定義②馬爾可夫鏈信源輸出的隨機(jī)符號(hào)序列為：X1,X2,…,Xl－1,Xl,…信源所處的隨機(jī)狀態(tài)序列為：S1,S2,…,Sl－1,Sl,…在第l時(shí)刻，信源狀態(tài)為si時(shí)，輸出符號(hào)xk的概率為：pl(xk/si)=P(Xl=xk/Sl=si)另在第l－1時(shí)刻，信源狀態(tài)si時(shí)，下一時(shí)刻轉(zhuǎn)移到sj的狀態(tài)轉(zhuǎn)移概率為：pl(sj/si)=P(Sl=sj/Sl-1=si)稱信源的隨機(jī)狀態(tài)序列服從馬爾可夫鏈。2.2多符號(hào)離散平穩(wěn)信源第8頁(yè)2024/4/142.2.4馬爾可夫信源(1)馬爾可夫信源的定義③時(shí)齊馬爾可夫鏈一步轉(zhuǎn)移概率：狀態(tài)轉(zhuǎn)移概率

pl(sj/si)=P(Sl=sj/Sl-1=si)

稱為馬爾可夫鏈在時(shí)刻l的狀態(tài)一步轉(zhuǎn)移概率。時(shí)齊/齊次馬爾可夫鏈：一般情況下，狀態(tài)轉(zhuǎn)移概率和已知狀態(tài)下符號(hào)發(fā)生的概率均與時(shí)刻

l

有關(guān)。若這些概率與時(shí)刻

l

無(wú)關(guān)，即：

pl(xk/si)=p(xk/si)pl(sj/si)=p(sj/si)

則稱為時(shí)齊的或齊次的。此時(shí)的信源狀態(tài)服從時(shí)齊馬爾可夫鏈。2.2多符號(hào)離散平穩(wěn)信源第9頁(yè)2024/4/142.2.4馬爾可夫信源(1)馬爾可夫信源的定義④馬爾可夫信源定義馬爾可夫信源：信源輸出的符號(hào)和所處的狀態(tài)滿足下列兩個(gè)條件。某一時(shí)刻信源符號(hào)的輸出只與此刻信源所處的狀態(tài)有關(guān)，與以前的狀態(tài)和以前的輸出符號(hào)都無(wú)關(guān)。即：P(Xl=xk

/Sl=si

,Xl－1=xk1,Sl－1

=sj,…)=pl(xk

/si)當(dāng)具有時(shí)齊性時(shí)有：

pl(xk

/si)=p(xk

/si)122.2多符號(hào)離散平穩(wěn)信源第10頁(yè)2024/4/142.2.4馬爾可夫信源(1)馬爾可夫信源的定義④馬爾可夫信源定義說(shuō)明：若信源處于某一狀態(tài)si，當(dāng)它發(fā)出一個(gè)符號(hào)后，所處的狀態(tài)就變了；任何時(shí)刻信源所處的狀態(tài)完全由前一時(shí)刻的狀態(tài)和發(fā)出的符號(hào)決定;

因?yàn)闂l件概率p(xk/si)已給定，狀態(tài)的轉(zhuǎn)移滿足一定的概率分布，據(jù)此可求出狀態(tài)的一步轉(zhuǎn)移概率p(sj/si)。2.2多符號(hào)離散平穩(wěn)信源第11頁(yè)2024/4/142.2.4馬爾可夫信源(1)馬爾可夫信源的定義④馬爾可夫信源定義這種信源的狀態(tài)序列在數(shù)學(xué)上可以作為馬爾科夫鏈來(lái)處理。故可用馬爾科夫鏈的狀態(tài)轉(zhuǎn)移圖來(lái)描述信源。馬爾可夫鏈的狀態(tài)轉(zhuǎn)移圖：每個(gè)圓圈代表一種狀態(tài)，狀態(tài)之間的有向線代表某一狀態(tài)向另一狀態(tài)的轉(zhuǎn)移。有向線一側(cè)的符號(hào)和數(shù)字分別代表發(fā)出的符號(hào)和條件概率。2.2多符號(hào)離散平穩(wěn)信源第12頁(yè)2024/4/142.2.4馬爾可夫信源(1)馬爾可夫信源的定義2.2多符號(hào)離散平穩(wěn)信源

[例2.2.3]：設(shè)信源符號(hào)：X∈{x1,x2,x3}各狀態(tài)之間的轉(zhuǎn)移情況：信源所處的狀態(tài)：S∈{s1,s2,s3,s4,s5}

(1)馬爾可夫信源的定義[例2.2.3]：將圖中信源在

si狀態(tài)下發(fā)符號(hào)

xk

的條件概率p(xk/si)

用矩陣表示：由矩陣看出：第13頁(yè)2024/4/142.2.4馬爾可夫信源2.2多符號(hào)離散平穩(wěn)信源(1)馬爾可夫信源的定義[例2.2.3]：第14頁(yè)2024/4/142.2.4馬爾可夫信源由圖中看出：2.2多符號(hào)離散平穩(wěn)信源第15頁(yè)2024/4/142.2.4馬爾可夫信源(1)馬爾可夫信源的定義

[例2.2.3]：由圖中可得狀態(tài)的一步轉(zhuǎn)移概率：該信源滿足馬爾可夫信源定義。2.2多符號(hào)離散平穩(wěn)信源第16頁(yè)2024/4/142.2.4馬爾可夫信源(1)馬爾可夫信源的定義[例2.2.4]：有一個(gè)二元二階馬爾可夫信源，其信源符號(hào)集為[0,1]

，條件概率為：

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.52.2多符號(hào)離散平穩(wěn)信源第17頁(yè)2024/4/142.2.4馬爾可夫信源(1)馬爾可夫信源的定義

[例2.2.4]：信源任何時(shí)刻發(fā)出什么符號(hào)只與前二個(gè)符號(hào)有關(guān)，與更前面的符號(hào)無(wú)關(guān)。信源有nm=22=4種可能的狀態(tài)，即00,01,10,11，分別用s1,s2,s3,s4

表示。如果原來(lái)狀態(tài)為00，則此時(shí)刻只可能發(fā)出符號(hào)0或1，下一時(shí)刻只可能轉(zhuǎn)移到00和01狀態(tài)，不會(huì)轉(zhuǎn)移到10或11狀態(tài)。2.2多符號(hào)離散平穩(wěn)信源第18頁(yè)2024/4/142.2.4馬爾可夫信源(1)馬爾可夫信源的定義[例2.2.4]：處在00狀態(tài)時(shí)發(fā)符號(hào)0的概率為0.8，所以處在00狀態(tài)轉(zhuǎn)回到00狀態(tài)的概率為0.8。處在00狀態(tài)時(shí)發(fā)符號(hào)1的概率為0.2，所以00狀態(tài)轉(zhuǎn)移到01狀態(tài)的概率為0.2。2.2多符號(hào)離散平穩(wěn)信源第19頁(yè)2024/4/142.2.4馬爾可夫信源(1)馬爾可夫信源的定義[例2.2.4]：根據(jù)給定的條件概率，可以求得狀態(tài)之間的轉(zhuǎn)移概率（一步轉(zhuǎn)移概率）為:p(s1/s1)=p(s4/s4)=0.8p(s2/s1)=p(s3/s4)=0.2p(s3/s2)=p(s2/s3)=p(s4/s2)=p(s1/s3)=0.5

其它的狀態(tài)轉(zhuǎn)移概率都為零。2.2多符號(hào)離散平穩(wěn)信源第20頁(yè)2024/4/142.2.4馬爾可夫信源(1)馬爾可夫信源的定義[例2.2.4]：二元信源發(fā)出的一串二元序列可變換成狀態(tài)序列。例如：二元序列為…01011100…，狀態(tài)序列為…s2s3

s2

s4

s4

s3

s1…。這串狀態(tài)序列是時(shí)齊的馬爾可夫鏈，它在任何時(shí)刻l，狀態(tài)之間的轉(zhuǎn)移可由一步轉(zhuǎn)移概率確定。2.2多符號(hào)離散平穩(wěn)信源第21頁(yè)2024/4/142.2.4馬爾可夫信源(1)馬爾可夫信源的定義⑤結(jié)論：一般有記憶信源發(fā)出的是有關(guān)聯(lián)性的各符號(hào)構(gòu)成的整體消息，即發(fā)出的是符號(hào)序列，并用符號(hào)間的聯(lián)合概率描述這種關(guān)聯(lián)性；馬爾可夫信源的不同之處在于它用符號(hào)之間的轉(zhuǎn)移概率（條件概率）來(lái)描述這種關(guān)聯(lián)關(guān)系。即馬爾可夫信源是以轉(zhuǎn)移概率發(fā)出每個(gè)信源符號(hào)；轉(zhuǎn)移概率的大小取決于它與前面符號(hào)之間的關(guān)聯(lián)性。2.2多符號(hào)離散平穩(wěn)信源第22頁(yè)2024/4/142.2.4馬爾可夫信源(2)m階馬爾可夫信源①m階馬爾可夫信源②m階馬爾可夫信源的極限熵③有限齊次馬爾可夫鏈各態(tài)歷經(jīng)定理④有關(guān)問題的說(shuō)明2.2多符號(hào)離散平穩(wěn)信源第23頁(yè)2024/4/142.2.4馬爾可夫信源(2)m階馬爾可夫信源①m階馬爾可夫信源m階有記憶離散信源的狀態(tài)：對(duì)m階有記憶離散信源，在任何時(shí)刻l，符號(hào)發(fā)出的概率只與前面m個(gè)符號(hào)有關(guān)，把這m個(gè)符號(hào)看作信源在l時(shí)刻的狀態(tài)。

n—信源符號(hào)集符號(hào)個(gè)數(shù)

nm—信源不同的狀態(tài)數(shù)

m+1—信源輸出依賴長(zhǎng)度信源輸出依賴長(zhǎng)度為m+1的隨機(jī)序列轉(zhuǎn)化為對(duì)應(yīng)的狀態(tài)序列，這種狀態(tài)序列符合簡(jiǎn)單的馬爾可夫鏈的性質(zhì)。2.2多符號(hào)離散平穩(wěn)信源第24頁(yè)2024/4/142.2.4馬爾可夫信源(2)m階馬爾可夫信源①m階馬爾可夫信源m階馬爾可夫信源數(shù)學(xué)模型：m階有記憶離散信源的數(shù)學(xué)模型可由一組信源符號(hào)集和一組條件概率確定：2.2多符號(hào)離散平穩(wěn)信源第25頁(yè)2024/4/142.2.4馬爾可夫信源(2)m

階馬爾可夫信源①m

階馬爾可夫信源一階馬爾可夫信源：當(dāng)m=1時(shí)，任何時(shí)刻信源符號(hào)發(fā)生的概率只與前面一個(gè)符號(hào)有關(guān)。

m階馬爾可夫信源的條件概率（考慮其平穩(wěn)性）2.2多符號(hào)離散平穩(wěn)信源第26頁(yè)2024/4/142.2.4馬爾可夫信源(2)m

階馬爾可夫信源②m階馬爾可夫信源的極限熵2.2多符號(hào)離散平穩(wěn)信源第27頁(yè)2024/4/142.2.4馬爾可夫信源(2)m

階馬爾可夫信源②m階馬爾可夫信源的極限熵上式中的可表示為狀態(tài)si(i=1,2,…,nm)；信源處于狀態(tài)

si時(shí)，再發(fā)下一個(gè)符號(hào)（或?qū)懗?/p>

xk），則信源從狀態(tài)si轉(zhuǎn)移到

sj，即。所以：其中p(si)(i=1,2,…,nm)

是m階馬爾可夫信源穩(wěn)定后的狀態(tài)極限概率，

p(sj/si)

是一步轉(zhuǎn)移概率。2.2多符號(hào)離散平穩(wěn)信源第28頁(yè)2024/4/142.2.4馬爾可夫信源(2)m

階馬爾可夫信源②m階馬爾可夫信源的極限熵這里利用了m階馬爾可夫信源“有限記憶長(zhǎng)度”的根本特性，使無(wú)限大參數(shù)N變?yōu)橛邢拗祄，把求極限熵的問題變成了一個(gè)求m階條件熵的問題。狀態(tài)一步轉(zhuǎn)移概率p(sj/si)

是給定或測(cè)定的。求解Hm+1條件熵的關(guān)鍵就是要得到p(si)(i=1,2,…,nm)

。p(si)

是馬爾可夫信源穩(wěn)定后(N→∞)各狀態(tài)的極限概率。有限狀態(tài)的馬爾可夫鏈：狀態(tài)空間的狀態(tài)是有限的。可列狀態(tài)的馬爾可夫鏈：狀態(tài)空間

I是{0,±1,±2,…}。2.2多符號(hào)離散平穩(wěn)信源第29頁(yè)2024/4/142.2.4馬爾可夫信源2.2多符號(hào)離散平穩(wěn)信源(2)m

階馬爾可夫信源③有限齊次馬爾可夫鏈各態(tài)歷經(jīng)定理定理：對(duì)于有限齊次馬爾可夫鏈，若存在一個(gè)正整數(shù)l0≥1，且經(jīng)過

l0步，從狀態(tài)

si轉(zhuǎn)移到

sj的

l0步轉(zhuǎn)移概率：第30頁(yè)2024/4/142.2.4馬爾可夫信源2.2多符號(hào)離散平穩(wěn)信源(2)m

階馬爾可夫信源③有限齊次馬爾可夫鏈各態(tài)歷經(jīng)定理第31頁(yè)2024/4/142.2.4馬爾可夫信源(2)m

階馬爾可夫信源③有限齊次馬爾可夫鏈各態(tài)歷經(jīng)定理凡具有各態(tài)歷經(jīng)性的

m

階馬爾可夫信源，其狀態(tài)極限概率p(si)

可由上式求出。有了p(si)

和測(cè)定的p(sj/si)，就可求出m

階馬爾可夫信源的熵Hm+1

。2.2多符號(hào)離散平穩(wěn)信源第32頁(yè)2024/4/142.2.4馬爾可夫信源(2)m

階馬爾可夫信源④有關(guān)問題的說(shuō)明m

階馬爾可夫信源在起始的有限時(shí)間內(nèi)，信源不是平穩(wěn)和遍歷/各態(tài)歷經(jīng)性的，狀態(tài)的概率分布有一段起始漸變過程。經(jīng)過足夠長(zhǎng)時(shí)間之后，信源處于什么狀態(tài)已與初始狀態(tài)無(wú)關(guān)，這時(shí)每種狀態(tài)出現(xiàn)的概率已達(dá)到一種穩(wěn)定分布。一般馬爾可夫信源并非是平穩(wěn)信源，但當(dāng)時(shí)齊、遍歷的馬爾可夫信源達(dá)到穩(wěn)定后，這時(shí)就可以看成是平穩(wěn)信源。2.2多符號(hào)離散平穩(wěn)信源(3)舉例[例2.2.4]：二元2階馬爾可夫信源，原始信號(hào)X

的符號(hào)集為

{X1=0,X2=1}，其狀態(tài)空間共有

nm=22=4個(gè)不同的狀態(tài)s1,s2,s3,s4，即：E：{s1=00,s2=01,s3=10,s4=11}

狀態(tài)轉(zhuǎn)移圖見右圖所示。解：p(s1/s1)=p(x1/s1)=p(0/00)=0.8

p(s2/s1)=p(x2/s1)=p(1/00)=0.2p(s3/s2)=p(x1/s2)=p(0/01)=0.5p(s4/s2)=p(x2/s2)=p(1/01)=0.5p(s1/s3)=p(x1/s3)=p(0/10)=0.5p(s2/s3)=p(x2/s3)=p(1/10)=0.5p(s3/s4)=p(x1/s4)=p(0/11)=0.2p(s4/s4)=p(x2/s4)=p(1/11)=0.8第33頁(yè)2024/4/142.2.4馬爾可夫信源2.2多符號(hào)離散平穩(wěn)信源第34頁(yè)2024/4/142.2.4馬爾可夫信源(3)舉例[例2.2.4]：由二元信源X∈{0,1}

得到的狀態(tài)空間(s1,s2,s3,s4)

和相應(yīng)的一步轉(zhuǎn)移概率構(gòu)成的2階馬爾可夫信源模型為：2.2多符號(hào)離散平穩(wěn)信源第35頁(yè)2024/4/142.2.4馬爾可夫信源(3)舉例[例2.2.4]：求出穩(wěn)定狀態(tài)下的p(sj)，稱為狀態(tài)極限概率。將一步轉(zhuǎn)移概率代入上式得:p(s1)=0.8p(s1)+0.5p(s3)p(s3)=0.5p(s2)+0.2p(s4)p(s2)=0.2p(s1)+0.5p(s3)p(s4)=0.5p(s2)+0.8p(s4)解方程組得：p(s1)=p(s4)=5/14p(s2)=p(s3)=2/14計(jì)算極限熵：2.2多符號(hào)離散平穩(wěn)信源第36頁(yè)2024/4/142.2.4馬爾可夫信源注意：H∞

并非在任何情況下都存在。對(duì)n

元

m

階馬爾可夫信源來(lái)說(shuō)，只有狀態(tài)極限概率p(sj)，j=1,2,…,nm都存在時(shí)，才能計(jì)算出H∞

。從理論上可以證明，如果m

階馬爾可夫信源穩(wěn)定后具有各態(tài)歷經(jīng)性，則狀態(tài)極限概率p(sj)

可根據(jù)下式求出:

m階馬爾可夫信源是離散平穩(wěn)有記憶信源的一個(gè)特例。2.2多符號(hào)離散平穩(wěn)信源第37頁(yè)2024/4/142.2.5信源冗余度(1)實(shí)際信源的近似(2)英語(yǔ)信源的熵(3)信源的冗余度(4)通信效率與可靠性的關(guān)系2.2多符號(hào)離散平穩(wěn)信源第38頁(yè)2024/4/142.2.5信源冗余度(1)實(shí)際信源的近似①實(shí)際信源近似為平穩(wěn)信源②離散平穩(wěn)信源近似為馬爾可夫信源③信源符號(hào)的相關(guān)性與提供的平均信息量2.2多符號(hào)離散平穩(wěn)信源第39頁(yè)2024/4/142.2.5信源冗余度(1)實(shí)際信源的近似①實(shí)際信源近似為平穩(wěn)信源實(shí)際信源可能是非平穩(wěn)的，極限熵H∞

不一定存在。有時(shí)為了方便假設(shè)它是平穩(wěn)的。測(cè)得N足夠大時(shí)的條件概率：P(XN/X1X2…XN-1)

，再計(jì)算出HN(X)，近似極限熵H∞

。2.2多符號(hào)離散平穩(wěn)信源第40頁(yè)2024/4/142.2.5信源冗余度(1)實(shí)際信源的近似②離散平穩(wěn)信源近似為馬爾可夫信源計(jì)算N

足夠大時(shí)的HN(X)

往往也十分困難，可進(jìn)一步假設(shè)離散平穩(wěn)信源是m

階馬爾可夫信源。信源熵用m階馬爾可夫信源的熵

Hm+1

來(lái)近似，需要測(cè)定的條件概率要少的多。近似程度的高低取決于記憶長(zhǎng)度m。越接近實(shí)際信源，m

值越大；反之對(duì)信源簡(jiǎn)化的越多，m

值越小。2.2多符號(hào)離散平穩(wěn)信源第41頁(yè)2024/4/142.2.5信源冗余度(1)實(shí)際信源的近似②離散平穩(wěn)信源近似為馬爾可夫信源最簡(jiǎn)單的馬爾可夫信源記憶長(zhǎng)度

m=1，信源熵：H2=

H1+1=H(X2/X1)當(dāng)

m=0時(shí)，信源變?yōu)殡x散無(wú)記憶信源，其熵可用H1(X)表示。繼續(xù)簡(jiǎn)化，假定信源是等概率分布的無(wú)記憶離散信源，這種信源的熵就是最大熵值

H0(X)=log2n。2.2多符號(hào)離散平穩(wěn)信源第42頁(yè)2024/4/142.2.5信源冗余度(1)實(shí)際信源的近似③信源符號(hào)的相關(guān)性與提供的平均信息量把多符號(hào)離散信源都用馬爾可夫信源來(lái)逼近，則記憶長(zhǎng)度不同，熵值就不同，意味著平均每發(fā)一個(gè)符號(hào)就有不同的信息量。log2n=H0≥H1≥H2≥…≥Hm≥H∞

所以信源的記憶長(zhǎng)度越長(zhǎng)，熵值越小。當(dāng)信源符號(hào)間彼此沒有任何依賴關(guān)系且呈等概率分布時(shí)，信源熵達(dá)到最大值。即信源符號(hào)的相關(guān)性越強(qiáng)，提供的平均信息量越小。2.2多符號(hào)離散平穩(wěn)信源第43頁(yè)2024/4/142.2.5信源冗余度(2)英語(yǔ)信源的熵①把英語(yǔ)看成是離散無(wú)記憶信源②把英語(yǔ)看成馬爾可夫信源2.2多符號(hào)離散平穩(wěn)信源第44頁(yè)2024/4/142.2.5信源冗余度(2)英語(yǔ)信源的熵①把英語(yǔ)看成是離散無(wú)記憶信源英語(yǔ)字母26個(gè)，加上一個(gè)空格，共

27個(gè)符號(hào)。英語(yǔ)信源的最大熵（等概率）：H0=log227=4.76（比特/符號(hào)）英語(yǔ)字母并非等概率出現(xiàn)，字母之間有嚴(yán)格的依賴關(guān)系。表2.2.2是對(duì)27個(gè)符號(hào)出現(xiàn)的概率統(tǒng)計(jì)結(jié)果。2.2多符號(hào)離散平穩(wěn)信源第45頁(yè)2024/4/142.2.5信源冗余度(2)英語(yǔ)信源的熵①把英語(yǔ)看成是離散無(wú)記憶信源2.2多符號(hào)離散平穩(wěn)信源第46頁(yè)2024/4/142.2.5信源冗余度(2)英語(yǔ)信源的熵①把英語(yǔ)看成是離散無(wú)記憶信源如果不考慮符號(hào)間的依賴關(guān)系，近似認(rèn)為信源是離散無(wú)記憶的，則：按表2.2.2的概率分布，隨機(jī)地選擇英語(yǔ)字母并排列起來(lái)，得到一個(gè)輸出序列：2.2多符號(hào)離散平穩(wěn)信源第47頁(yè)2024/4/142.2.5信源冗余度(2)英語(yǔ)信源的熵①把英語(yǔ)看成是離散無(wú)記憶信源AI_NGAE_ITE_NNR_ASAEV_OTE_BAINTHA_HYROO_PORE_SETRYGAIETRWCO_EHDUARU_EUEU_C_FT_NSREM_DIY_EESE_F_O_SRIS_R_UNNASHOR…這個(gè)序列看起來(lái)有點(diǎn)像英語(yǔ)，但不是。實(shí)際英語(yǔ)的某個(gè)字母出現(xiàn)后，后面的字母并非完全隨機(jī)出現(xiàn)，而是滿足一定關(guān)系的條件概率分布。例如T

后面出現(xiàn)H，R的可能性較大，出現(xiàn)

J，K，M，N

的可能性極小，而根本不會(huì)出現(xiàn)Q，F(xiàn)，X。即英語(yǔ)字母之間有強(qiáng)烈的依賴性。上述序列僅考慮了字母出現(xiàn)的概率，忽略了依賴關(guān)系。2.2多符號(hào)離散平穩(wěn)信源第48頁(yè)2024/4/142.2.5信源冗余度(2)英語(yǔ)信源的熵②把英語(yǔ)看成馬爾可夫信源為了進(jìn)一步逼近實(shí)際情況，可把英語(yǔ)信源近似看做1階，2階，…，∞階馬爾可夫信源，它們的熵為：H2=3.32（比特/符號(hào)）H3=3.1（比特/符號(hào)）若把英語(yǔ)信源近似成

2階馬爾可夫信源，可得到某個(gè)輸出序列：IANKS_CAN_OU_ANG_RLER_THTTED_OF_TO_SHOR_OF_TO_HAVEMEM_A_I_MAND_AND_BUT_WHISS_ITABLY_THERVEREER…2.2多符號(hào)離散平穩(wěn)信源第49頁(yè)2024/4/142.2.5信源冗余度(2)英語(yǔ)信源的熵②把英語(yǔ)看成馬爾可夫信源這個(gè)序列中被空格分開的兩字母或三字母，組成的大都是有意義的英語(yǔ)單詞，而四個(gè)以上字母組成的“單詞”，很難從英語(yǔ)詞典中查到。因?yàn)樵撔蛄袃H考慮了3個(gè)以下字母之間的依賴關(guān)系。實(shí)際英語(yǔ)字母之間的關(guān)系延伸到更多的符號(hào)，單詞之間也有依賴關(guān)系。有依賴關(guān)系的字母數(shù)越多，即馬爾可夫信源的階數(shù)越高，輸出的序列就越接近于實(shí)際情況。當(dāng)依賴關(guān)系延伸到無(wú)窮遠(yuǎn)時(shí)，信源輸出的就是真正的英語(yǔ)，此時(shí)可求出馬爾可夫的極限熵

H∞=1.4（比特/符號(hào)）2.2多符號(hào)離散平穩(wěn)信源第50頁(yè)2024/4/142.2.5信源冗余度(3)信源的冗余度①信息傳輸手段的浪費(fèi)②信源冗余度定義及意義③重要結(jié)論2.2多符號(hào)離散平穩(wěn)信源第51頁(yè)2024/4/142.2.5信源冗余度(3)信源的冗余度①信息傳輸手段的浪費(fèi)對(duì)一般離散平穩(wěn)信源，H∞就是實(shí)際信源熵。理論上只要有傳送H∞

的手段，就能把信源包含的信息全部發(fā)送出去。但實(shí)際上確定H∞

非常困難，只好用Hm+1

來(lái)代替。Hm+1>H∞，所以在傳輸手段上必然富裕，這樣做很不經(jīng)濟(jì)，特別是有時(shí)只能得到

H1，甚至H0，就更不經(jīng)濟(jì)。這種浪費(fèi)是由信源符號(hào)的相關(guān)性引起的。2.2多符號(hào)離散平穩(wěn)信源第52頁(yè)2024/4/142.2.5