第二章隨機(jī)過(guò)程的信息度量和漸近等分性

1、12.1 2.1 2.2 2.2 2.3 2.3 2.4 2.4 2.5 2.5 第二章第二章2 信源信源：是信息的來(lái)源是信息的來(lái)源, ,是產(chǎn)生消息是產(chǎn)生消息( (符號(hào)符號(hào)) )、消息序列、消息序列 ( (符號(hào)序列符號(hào)序列) )以及時(shí)間連續(xù)的消息的來(lái)源以及時(shí)間連續(xù)的消息的來(lái)源. . (1) (1)在一個(gè)固定的時(shí)刻在一個(gè)固定的時(shí)刻, ,信源發(fā)出的是一個(gè)隨機(jī)變量信源發(fā)出的是一個(gè)隨機(jī)變量. . (2)(2)隨著時(shí)間的延續(xù)，信源發(fā)出的是一個(gè)隨機(jī)過(guò)程隨著時(shí)間的延續(xù)，信源發(fā)出的是一個(gè)隨機(jī)過(guò)程. . l 信源的主要問(wèn)題信源的主要問(wèn)題如何描述信源的輸出（信源的建模問(wèn)題）如何描述信源的輸出（信源的建模問(wèn)題）怎樣

2、確定信源產(chǎn)生的信息量怎樣確定信源產(chǎn)生的信息量信源編碼信源編碼 第二章第二章1.1.信源的分類及其數(shù)學(xué)模型信源的分類及其數(shù)學(xué)模型312( )()NP XP X XX),(teX 時(shí)間時(shí)間 （空間）（空間）取值取值信源種類信源種類舉例舉例消息的數(shù)學(xué)描述消息的數(shù)學(xué)描述 離散離散離散離散 離散信源離散信源 ( (數(shù)字信源數(shù)字信源) )文字、數(shù)據(jù)文字、數(shù)據(jù)離散化圖象離散化圖象 離散隨機(jī)變量序列離散隨機(jī)變量序列 離散離散連續(xù)連續(xù) 連續(xù)信源連續(xù)信源 連續(xù)連續(xù)連續(xù)連續(xù) 波形信源波形信源 ( (模擬信源模擬信源) )語(yǔ)音、音樂(lè)語(yǔ)音、音樂(lè)、熱噪聲、熱噪聲、圖形、圖象圖形、圖象隨機(jī)過(guò)程隨機(jī)過(guò)程 連續(xù)連續(xù)離散離散 不

3、常見(jiàn)不常見(jiàn) 根據(jù)信源輸出消息在時(shí)間和取值上是離散或連續(xù)分類根據(jù)信源輸出消息在時(shí)間和取值上是離散或連續(xù)分類 4信號(hào)取值離散信號(hào)取值離散：信源輸出的消息是有限或可數(shù)的，而：信源輸出的消息是有限或可數(shù)的，而且每次只輸出其中一個(gè)消息且每次只輸出其中一個(gè)消息. . 如：如：拋硬幣拋硬幣！其數(shù)學(xué)模型是離散型的概率空間：其數(shù)學(xué)模型是離散型的概率空間：1212,(),(),( )()qqxxxXP xP xP xP x ()1iip a,( , )( )( )Xa bP xP x信號(hào)取值連續(xù)信號(hào)取值連續(xù)：信源輸出的是單個(gè)符號(hào)，但符號(hào)集的：信源輸出的是單個(gè)符號(hào)，但符號(hào)集的取值是連續(xù)的，或?qū)崝?shù)集取值是連續(xù)的，或?qū)?/p>

4、數(shù)集. . 如：如：語(yǔ)音信號(hào)某時(shí)間的連續(xù)數(shù)據(jù)語(yǔ)音信號(hào)某時(shí)間的連續(xù)數(shù)據(jù)！其數(shù)學(xué)模型是離散型的概率空間：其數(shù)學(xué)模型是離散型的概率空間： ( )1bap x dx 5波形信源波形信源：輸出的消息是時(shí)間連續(xù)，且符號(hào)集的取值：輸出的消息是時(shí)間連續(xù)，且符號(hào)集的取值也連續(xù)也連續(xù). . 如：如：多媒體通信系統(tǒng)的信號(hào)多媒體通信系統(tǒng)的信號(hào)！一般用一般用平穩(wěn)平穩(wěn)遍歷遍歷的隨機(jī)過(guò)程來(lái)描述波形信源的輸出的隨機(jī)過(guò)程來(lái)描述波形信源的輸出. .平穩(wěn)平穩(wěn)：在任意兩個(gè)不同時(shí)刻隨機(jī)變量的各維概率分布：在任意兩個(gè)不同時(shí)刻隨機(jī)變量的各維概率分布相同相同. . 如：如：自然英文字母自然英文字母！11( , , )nnnp xx tt11

5、(,)nnnpxx tt6 離散信源離散信源 信源每隔一個(gè)定長(zhǎng)時(shí)間段就發(fā)出一個(gè)隨機(jī)信源每隔一個(gè)定長(zhǎng)時(shí)間段就發(fā)出一個(gè)隨機(jī)變量；隨著時(shí)間的延續(xù)，信源發(fā)出的是隨機(jī)變量序變量；隨著時(shí)間的延續(xù)，信源發(fā)出的是隨機(jī)變量序列列 U-2U-1U0 U1U2， 其中其中 (1) Uk為第為第k個(gè)個(gè)時(shí)間段時(shí)間段發(fā)出的隨機(jī)變量發(fā)出的隨機(jī)變量； (2) 每個(gè)每個(gè)Uk都是一個(gè)離散型的隨機(jī)變量都是一個(gè)離散型的隨機(jī)變量. 信源的分類及其數(shù)學(xué)模型信源的分類及其數(shù)學(xué)模型71)1)根據(jù)信源發(fā)出的消息序列之間是否有統(tǒng)計(jì)依賴關(guān)系，根據(jù)信源發(fā)出的消息序列之間是否有統(tǒng)計(jì)依賴關(guān)系，信源可分為信源可分為有記憶信源、無(wú)記憶信源有記憶信源、無(wú)記憶

6、信源. . 離散無(wú)記憶信源：離散無(wú)記憶信源：隨機(jī)變量隨機(jī)變量、U-2、U-1、U0、U1、U2、相互相互獨(dú)立獨(dú)立. . 簡(jiǎn)單信源：簡(jiǎn)單信源：信源在不同時(shí)刻發(fā)出的隨機(jī)變量有相同的概率分布信源在不同時(shí)刻發(fā)出的隨機(jī)變量有相同的概率分布. .離散無(wú)記憶離散無(wú)記憶簡(jiǎn)單簡(jiǎn)單信源：信源：離散無(wú)記憶信源發(fā)出的隨機(jī)變量具有相離散無(wú)記憶信源發(fā)出的隨機(jī)變量具有相同的概率分布同的概率分布. .信源的分類及其數(shù)學(xué)模型信源的分類及其數(shù)學(xué)模型8注意：注意：有記憶信源有記憶信源： 信源在不同時(shí)刻發(fā)出的隨機(jī)變量相互依賴信源在不同時(shí)刻發(fā)出的隨機(jī)變量相互依賴. .有限記憶信源有限記憶信源： 在有限時(shí)間差內(nèi)的信源隨機(jī)變量相互依賴在有

7、限時(shí)間差內(nèi)的信源隨機(jī)變量相互依賴. . 信源的分類及其數(shù)學(xué)模型信源的分類及其數(shù)學(xué)模型9()離散無(wú)記憶信源記憶長(zhǎng)度無(wú)限長(zhǎng)離散平穩(wěn)信源平穩(wěn)信源離散有記憶信源 記憶長(zhǎng)度有限隨機(jī)序列馬爾可夫信源連續(xù)平穩(wěn)信源非平穩(wěn)信源 隨機(jī)過(guò)程：波形信源2)2)根據(jù)信源發(fā)出的消息序列中的消息統(tǒng)計(jì)特性是否根據(jù)信源發(fā)出的消息序列中的消息統(tǒng)計(jì)特性是否保持不變，信源可分為保持不變，信源可分為平穩(wěn)信源、非平穩(wěn)信源平穩(wěn)信源、非平穩(wěn)信源. . 信源的分類及其數(shù)學(xué)模型信源的分類及其數(shù)學(xué)模型102.2.離散信源離散信源 離散信源離散信源（1 1）單符號(hào)離散信源單符號(hào)離散信源：信源輸出的消息是離散消息，：信源輸出的消息是離散消息，且每個(gè)符

8、號(hào)表示一條消息。且每個(gè)符號(hào)表示一條消息。 用用離散隨機(jī)變量離散隨機(jī)變量表示。表示。 記作：大寫(xiě)字母。記作：大寫(xiě)字母。（2 2）多符號(hào)離散信源多符號(hào)離散信源：信源輸出的消息是離散消息，：信源輸出的消息是離散消息，且多個(gè)符號(hào)表示一條消息。且多個(gè)符號(hào)表示一條消息。 用用隨機(jī)矢量隨機(jī)矢量表示。表示。（3 3）連續(xù)信源連續(xù)信源：信源輸出的消息是連續(xù)消息。：信源輸出的消息是連續(xù)消息。 用用隨機(jī)過(guò)程隨機(jī)過(guò)程表示。表示。11l 離散單符號(hào)信源離散單符號(hào)信源：輸出離散取值的單個(gè)符號(hào)的信源輸出離散取值的單個(gè)符號(hào)的信源. . 離散單符號(hào)信源離散單符號(hào)信源是是最簡(jiǎn)單、最基本最簡(jiǎn)單、最基本的信源，是組成實(shí)際信源的基本的

9、信源，是組成實(shí)際信源的基本單元，可以用一個(gè)離散隨機(jī)變量來(lái)表示單元，可以用一個(gè)離散隨機(jī)變量來(lái)表示. .l 離散單符號(hào)信源離散單符號(hào)信源X的概率空間的概率空間1212.()( )().()qqxxxXP Xp xp xp x()0ip x1()1niip x2.2.離散信源離散信源12l 信源輸出的所有消息的自信息的統(tǒng)計(jì)平均值，定信源輸出的所有消息的自信息的統(tǒng)計(jì)平均值，定義為信源的義為信源的平均自信息（信息熵）平均自信息（信息熵）1()log( )( )log( )niiiiH XEp xp xp x l 信息熵表示離散單符號(hào)信源的平均不確定性信息熵表示離散單符號(hào)信源的平均不確定性. .離散單符號(hào)

10、信源離散單符號(hào)信源13 實(shí)際信源往往輸出的消息是時(shí)間和空間上的一系列符號(hào)實(shí)際信源往往輸出的消息是時(shí)間和空間上的一系列符號(hào). .例如例如電報(bào)系統(tǒng)電報(bào)系統(tǒng), , 這類信源每次輸出的不是一個(gè)單個(gè)的符號(hào)，而是一個(gè)這類信源每次輸出的不是一個(gè)單個(gè)的符號(hào)，而是一個(gè)符號(hào)序列符號(hào)序列. . 通常一個(gè)消息序列的每一位出現(xiàn)哪個(gè)符號(hào)都是隨機(jī)的通常一個(gè)消息序列的每一位出現(xiàn)哪個(gè)符號(hào)都是隨機(jī)的, ,而且而且一般前后符號(hào)之間的出現(xiàn)是有統(tǒng)計(jì)依賴關(guān)系的一般前后符號(hào)之間的出現(xiàn)是有統(tǒng)計(jì)依賴關(guān)系的, ,這種信源稱為這種信源稱為多多符號(hào)離散信源符號(hào)離散信源. . 為了便于研究為了便于研究, ,假設(shè)隨機(jī)變量序列中隨機(jī)變量的各維聯(lián)合概假設(shè)隨

11、機(jī)變量序列中隨機(jī)變量的各維聯(lián)合概率分布率分布( (統(tǒng)計(jì)特性統(tǒng)計(jì)特性)均不隨時(shí)間的推移而變化均不隨時(shí)間的推移而變化, ,即信源所發(fā)出的符即信源所發(fā)出的符號(hào)序列的概率分布與時(shí)間的起點(diǎn)無(wú)關(guān)號(hào)序列的概率分布與時(shí)間的起點(diǎn)無(wú)關(guān), ,這種信源稱為這種信源稱為多符號(hào)離散多符號(hào)離散平穩(wěn)信源平穩(wěn)信源. .多符號(hào)離散信源可以用隨機(jī)變量序列來(lái)描述，即多符號(hào)離散信源可以用隨機(jī)變量序列來(lái)描述，即12nX XXX X離散多符號(hào)信源離散多符號(hào)信源14定義定義 對(duì)于離散隨機(jī)變量序列對(duì)于離散隨機(jī)變量序列 ，若任意，若任意兩個(gè)不同時(shí)刻兩個(gè)不同時(shí)刻i和和j( (大于大于1 1的任意整數(shù)的任意整數(shù)) )信源發(fā)出消息的信源發(fā)出消息的概率

12、分布完全相同，即對(duì)于任意的概率分布完全相同，即對(duì)于任意的 , , 和和 具有相同的概率分布，也具有相同的概率分布，也就是就是各維聯(lián)合概率分布均與時(shí)間起點(diǎn)無(wú)關(guān)的信源稱各維聯(lián)合概率分布均與時(shí)間起點(diǎn)無(wú)關(guān)的信源稱離散平離散平穩(wěn)信源。穩(wěn)信源。 nXXX21, 2, 1, 0N1iiiNX XX1jjjNX XX)()(jiXPXP)()(11jjiiXXPXXP11()()iii Njjj NP X XXP X XX離散平穩(wěn)信源離散平穩(wěn)信源15對(duì)離散平穩(wěn)信源，由聯(lián)合概率與條件概率的關(guān)系可以推出對(duì)離散平穩(wěn)信源，由聯(lián)合概率與條件概率的關(guān)系可以推出 )|()|(11jjiiXXPXXP1111(|)(|)i

13、Niii Nj Njjj NP XX XXP XX XX因此因此 )()()(21NXHXHXH)|()|()|(12312NNXXHXXHXXH31242321(|)(|)(|)NNNH XX XH XX XH XXX離散平穩(wěn)信源離散平穩(wěn)信源16如果一個(gè)信源序列是平穩(wěn)遍歷過(guò)平穩(wěn)程,遍稱信源為歷信源.平穩(wěn)遍歷信源平穩(wěn)遍歷信源1223( ,.)(,.),. 設(shè)為一個(gè)實(shí)數(shù)序列，用 表示移位算子，稱實(shí)數(shù)列的集合 為，如果當(dāng)且定平移不變義當(dāng)集僅xx xTTxx xATxAxA12( ,.)01. 稱一個(gè)平穩(wěn)過(guò)程為，如果對(duì)任何平移不變集定遍歷的有或義rAPx xA, 直觀地說(shuō) 一個(gè)遍歷的馬氏過(guò)程從任何一

14、個(gè)狀態(tài)出發(fā)可以正概率在有限步到達(dá)任何其它狀態(tài).17 隨機(jī)變量是定義在概率空間上取值為實(shí)數(shù)的函隨機(jī)變量是定義在概率空間上取值為實(shí)數(shù)的函數(shù)。因此我們可以像數(shù)學(xué)分析討論函數(shù)序列逐點(diǎn)收數(shù)。因此我們可以像數(shù)學(xué)分析討論函數(shù)序列逐點(diǎn)收斂性那樣去討論隨機(jī)變量序列在每個(gè)樣本點(diǎn)處的值斂性那樣去討論隨機(jī)變量序列在每個(gè)樣本點(diǎn)處的值的收斂性。的收斂性。 然而然而, ,由于隨機(jī)變量取值的隨機(jī)性由于隨機(jī)變量取值的隨機(jī)性, ,我們常常不我們常常不可能期望隨機(jī)變量序列在所有點(diǎn)處都存在極限。現(xiàn)可能期望隨機(jī)變量序列在所有點(diǎn)處都存在極限?，F(xiàn)在的問(wèn)題是研究極限是否在一個(gè)概率為在的問(wèn)題是研究極限是否在一個(gè)概率為1 1的點(diǎn)集上的點(diǎn)集上存在

15、。存在。 由于隨機(jī)變量序列向常數(shù)的收斂有多種不同的由于隨機(jī)變量序列向常數(shù)的收斂有多種不同的形式形式, ,按其收斂為按其收斂為依概率收斂依概率收斂, ,依概率依概率1 1收斂收斂, ,相對(duì)應(yīng)相對(duì)應(yīng)分別有弱大數(shù)定律、強(qiáng)大數(shù)定律。分別有弱大數(shù)定律、強(qiáng)大數(shù)定律。1812111,.,.1,0,1lim|1.:,1.nniiinrininiiXXXXEXaXanPXannXan 設(shè), 為相互獨(dú)立的隨機(jī)變量序列,并且服從相同的分布,有有限數(shù)學(xué)期望= ,則依概率收斂到即對(duì)任意的有 直觀的理解除去極小的可能性 只要 充定理(弱大數(shù)定律) 分大與 可任意接近弱大數(shù)定律弱大數(shù)定律191211,.,.1,1lim1.

16、,.nniiinrinikXXXXEXaXnaPXanX定理(強(qiáng)大數(shù)定律) 設(shè), 為相互獨(dú)立的隨機(jī)變量序列,并且服從相同的分布,有有限數(shù)學(xué)期望= ,則依概率1收斂到 即 一個(gè)信源序列如果使 定義強(qiáng)大數(shù)定律成立 稱為平均遍歷強(qiáng)大數(shù)定律強(qiáng)大數(shù)定律20121212(, )()( ),(,.,)(,.,)(,.,).,0,()( )( ).m nmmmm nH X YH XH YH XXXH XXXH XXXm nh mnh mh n因?yàn)樗詫?duì)任意的整數(shù)滿足的定義半可列稱加數(shù)列數(shù)( )()( )( )11,lim( )inf( ).設(shè)是滿足的半可加數(shù)列引則理nnf nf mnf mf nf nf nn

17、n2.22.2隨即過(guò)程的總度量隨即過(guò)程的總度量3. 3. 隨機(jī)過(guò)程的信息度量隨機(jī)過(guò)程的信息度量211,1,2,.lim,1lim. 設(shè)實(shí)數(shù)列有極引限則理nnnnknka naaaan定義定義 隨機(jī)變量序列中，對(duì)前隨機(jī)變量序列中，對(duì)前N個(gè)隨機(jī)變量的聯(lián)個(gè)隨機(jī)變量的聯(lián)合熵求平均稱為合熵求平均稱為平均符號(hào)熵平均符號(hào)熵 . .121()(,)NNHH XXXNX X隨機(jī)過(guò)程的信息度量隨機(jī)過(guò)程的信息度量2212121()lim()lim(,)1inf(,)()defNNNNNNHXHH XXXNH XXXXN是平穩(wěn)信源X X如果當(dāng)如果當(dāng) 時(shí)上式極限存在，則時(shí)上式極限存在，則 被稱為被稱為熵率熵率，或，或極

18、限熵極限熵，記為，記為 Nlim()NNHX X隨機(jī)過(guò)程的信息度量隨機(jī)過(guò)程的信息度量2312,.,.,.,nXXXX為了便于計(jì)算 我們給出熵定理率的另一個(gè)等價(jià)形式 設(shè),是平穩(wěn)信源121(1)()lim(|,.,)存在;defnnnHXH XXXX(2)()().HXHX隨機(jī)過(guò)程的信息度量隨機(jī)過(guò)程的信息度量24 （2 2）對(duì)于收斂的實(shí)數(shù)列，）對(duì)于收斂的實(shí)數(shù)列， 即如果即如果 是一個(gè)收斂是一個(gè)收斂 于于 a 的實(shí)數(shù)列，那么的實(shí)數(shù)列，那么123,a a a 11limlimNkNNNkaaaN利用上述結(jié)論及熵的鏈法則可以推出利用上述結(jié)論及熵的鏈法則可以推出121lim(|)()NNNH XX XXH

19、X121lim()lim(,)()NNNNHH X XXHXNX1111lim(|,)NkkNkH XXXN1213121211lim()(|)(|)(|)NNNH XH XXH XX XNH XX XX25121,.,.()()nXXXXHXH X 設(shè),是無(wú)記憶信源,則熵率推論1.隨機(jī)過(guò)程的信息度量隨機(jī)過(guò)程的信息度量1211221,.,.()(|,.,1,()(|2nkkXXXXHXH XXXXkHXH XX設(shè),是k-階平穩(wěn)馬氏信源,則熵率);特別地時(shí)推論).26 為了研究離散平穩(wěn)無(wú)記憶信源的極限熵，把信源輸為了研究離散平穩(wěn)無(wú)記憶信源的極限熵，把信源輸出的符號(hào)序列看成是一組一組發(fā)出的。出的符

20、號(hào)序列看成是一組一組發(fā)出的。例例1 1 電報(bào)系統(tǒng)中電報(bào)系統(tǒng)中, ,可以認(rèn)為每可以認(rèn)為每2 2個(gè)二進(jìn)制數(shù)字組成一組。這個(gè)二進(jìn)制數(shù)字組成一組。這樣信源輸出的是由樣信源輸出的是由2 2個(gè)二進(jìn)制數(shù)字組成的一組組符號(hào)。這時(shí)個(gè)二進(jìn)制數(shù)字組成的一組組符號(hào)。這時(shí)可以將它們等效看成一個(gè)新的信源，它由四個(gè)符號(hào)可以將它們等效看成一個(gè)新的信源，它由四個(gè)符號(hào)00，01，10，11組成，把該信源稱為組成，把該信源稱為二進(jìn)制無(wú)記憶信源的二次擴(kuò)展二進(jìn)制無(wú)記憶信源的二次擴(kuò)展。例例2 2 如果把每三個(gè)二進(jìn)制數(shù)字組成一組，這樣長(zhǎng)度為如果把每三個(gè)二進(jìn)制數(shù)字組成一組，這樣長(zhǎng)度為3 3的二的二進(jìn)制序列就有進(jìn)制序列就有8 8種不同的符號(hào)，

21、可等效成一個(gè)具有種不同的符號(hào)，可等效成一個(gè)具有8 8個(gè)符號(hào)的個(gè)符號(hào)的信源，把它稱為信源，把它稱為二進(jìn)制無(wú)記憶信源的三次擴(kuò)展信源二進(jìn)制無(wú)記憶信源的三次擴(kuò)展信源。4.4.離散平穩(wěn)無(wú)記憶信源離散平穩(wěn)無(wú)記憶信源27l假定信源輸出的是假定信源輸出的是N長(zhǎng)符號(hào)序列，把它看成是一個(gè)新長(zhǎng)符號(hào)序列，把它看成是一個(gè)新信源，稱為信源，稱為離散平穩(wěn)無(wú)記憶信源的離散平穩(wěn)無(wú)記憶信源的N N次擴(kuò)展信源次擴(kuò)展信源，用，用N維離散隨機(jī)變量序列來(lái)表示：維離散隨機(jī)變量序列來(lái)表示：12NNX XXXX X1212()()()()()NiqNiqNXppppPXiG 是一個(gè)長(zhǎng)為是一個(gè)長(zhǎng)為N N的序列，的序列，12Niiiiax xx離

22、散平穩(wěn)無(wú)記憶信源離散平穩(wěn)無(wú)記憶信源lN N 次擴(kuò)展信源的概率空間為次擴(kuò)展信源的概率空間為28lN次擴(kuò)展信源次擴(kuò)展信源的熵的熵l離散平穩(wěn)無(wú)記憶信源的離散平穩(wěn)無(wú)記憶信源的N次擴(kuò)展信源的熵等于離散單次擴(kuò)展信源的熵等于離散單符號(hào)信源熵的符號(hào)信源熵的N倍倍1()()()log ()NqNiiiHH Xpp X()()()NHH XN H XXl離散平穩(wěn)無(wú)記憶信源的熵率離散平穩(wěn)無(wú)記憶信源的熵率1()lim()lim()()NNNHXHNH XH XNX離散平穩(wěn)無(wú)記憶信源離散平穩(wěn)無(wú)記憶信源29例例 設(shè)有一離散無(wú)記憶信源設(shè)有一離散無(wú)記憶信源X，其概率空間為，其概率空間為求該信源的熵率及二次擴(kuò)展信源的熵。求該信

23、源的熵率及二次擴(kuò)展信源的熵。123111244xxxXP X解解 離散單符號(hào)信源熵離散單符號(hào)信源熵321()()log()1.5iiiH Xp xp x 比特/符號(hào)() 1.5/HH X比特 符號(hào)熵率熵率30二次擴(kuò)展信源的概率空間二次擴(kuò)展信源的概率空間二次擴(kuò)展信源的熵二次擴(kuò)展信源的熵921()()()log ()3iiiHH Xpp X比特/符號(hào)211 121 231 342 152 262 373 183 293 32()()()()()()()()()1/ 41/81/81/81/161/161/81/161/16()x xx xx xx xx xx xx xx xx xXP X31l實(shí)際

24、信源常常是有記憶信源實(shí)際信源常常是有記憶信源. . 設(shè)信源輸出設(shè)信源輸出N N長(zhǎng)的符號(hào)序列，長(zhǎng)的符號(hào)序列，則可以用則可以用N N維隨機(jī)變量序列維隨機(jī)變量序列 來(lái)表示信源，其來(lái)表示信源，其中每個(gè)隨機(jī)變量之間存在統(tǒng)計(jì)依賴關(guān)系中每個(gè)隨機(jī)變量之間存在統(tǒng)計(jì)依賴關(guān)系. .lN N維隨機(jī)變量序列的聯(lián)合熵為維隨機(jī)變量序列的聯(lián)合熵為12NX XXX12()(,)NHH XXXX121312121()(|)(|)(|)NNH XH XXH XX XH XX XX離散平穩(wěn)有記憶信源離散平穩(wěn)有記憶信源3212314114936xxxXP X例例 信源信源X的信源模型為的信源模型為 輸出符號(hào)序列中，只有前后輸出符號(hào)序列

25、中，只有前后兩個(gè)符號(hào)之間有記憶，條件兩個(gè)符號(hào)之間有記憶，條件概率空間見(jiàn)右表。概率空間見(jiàn)右表。求熵率并求熵率并比較比較 H(X)、H(X2|X1) 、 1/2H(X1X2)的大小的大小.2X1X1x2x3x1x2x3x792901834180211911)|(12XXP條件概率條件概率 33解解 1)1) 121121lim(|)lim(|)(|)0.870NNNNNNHH XX XXH XXH XX比特比特/ /符號(hào)符號(hào) 2)2) 如果不考慮符號(hào)間的相關(guān)性，則信源熵為如果不考慮符號(hào)間的相關(guān)性，則信源熵為1 4 11()( ,)1.5424 9 36H XH比特比特/ /符號(hào)符號(hào) 3)3) 如果

26、把信源發(fā)出的符號(hào)看成是分組發(fā)出的，每?jī)蓚€(gè)如果把信源發(fā)出的符號(hào)看成是分組發(fā)出的，每?jī)蓚€(gè) 符號(hào)為一組，這個(gè)新信源的熵為符號(hào)為一組，這個(gè)新信源的熵為12121()()(|)2.412H X XH XH XX比特比特/ /兩個(gè)符號(hào)兩個(gè)符號(hào) 結(jié)論結(jié)論 121()()2HH X XH X34l馬爾可夫信源是一類相對(duì)簡(jiǎn)單的有記憶信源馬爾可夫信源是一類相對(duì)簡(jiǎn)單的有記憶信源. .l信源在某一時(shí)刻發(fā)出某一符號(hào)的概率，除與該符號(hào)信源在某一時(shí)刻發(fā)出某一符號(hào)的概率，除與該符號(hào)有關(guān)外，只與此前發(fā)出的有限個(gè)符號(hào)有關(guān)?；蛘哒f(shuō)有關(guān)外，只與此前發(fā)出的有限個(gè)符號(hào)有關(guān)。或者說(shuō)任何時(shí)刻信源符號(hào)發(fā)生的概率只與前面已經(jīng)發(fā)生過(guò)任何時(shí)刻信源符

27、號(hào)發(fā)生的概率只與前面已經(jīng)發(fā)生過(guò)的若干個(gè)符號(hào)有關(guān)，而與更前面的符號(hào)無(wú)關(guān)的若干個(gè)符號(hào)有關(guān)，而與更前面的符號(hào)無(wú)關(guān). . (1) 定義定義馬爾可夫信源馬爾可夫信源35l對(duì)于對(duì)于 m 階馬爾可夫信源階馬爾可夫信源121111121lim(|)lim(|)(|)NNNNN mN mNNmmmHH XX XXH XXXXH XX XXH(2) 熵率熵率l如何計(jì)算條件熵？如何計(jì)算條件熵？ 條件概率條件概率 通常是已知的，我們通常是已知的，我們需要求解的是聯(lián)合概率需要求解的是聯(lián)合概率 . .112(|)mmP XX XX12()mP X XX馬爾可夫信源馬爾可夫信源362121mmmXXXXX 1212mmmi

28、iiiix xx xx isjs1212mmmS SS SS1121(|)(|)(|)mmmiiiiiijip xx xxp xsp ss(3) 馬爾可夫信源馬爾可夫信源 馬爾可夫鏈馬爾可夫鏈馬爾可夫信源馬爾可夫信源37例例1 1 設(shè)一個(gè)二元一階馬爾可夫信源，信源符號(hào)集為設(shè)一個(gè)二元一階馬爾可夫信源，信源符號(hào)集為 ， 輸出符號(hào)的條件概率為輸出符號(hào)的條件概率為1, 0X(0|0)0.25, (1|0)0.75, (0|1)0.5, (1|1)0.5,pppp用狀態(tài)轉(zhuǎn)移圖來(lái)描述該信源。用狀態(tài)轉(zhuǎn)移圖來(lái)描述該信源。11：0.750：0.51：0.50：0.250s2s1二元一階馬爾可夫信源的轉(zhuǎn)移概率矩陣

29、與狀態(tài)轉(zhuǎn)移圖二元一階馬爾可夫信源的轉(zhuǎn)移概率矩陣與狀態(tài)轉(zhuǎn)移圖0.250.750.50.538 0.80.200000.500000.20.821122121(,)01400 011011|, (|,)2)(iiiriiiiiiXXXPXxXx XxP xx x設(shè)為取值于，的二階平穩(wěn)馬氏信源，其狀態(tài)可用兩個(gè)二進(jìn)制數(shù)字表示，共有 種，信源的統(tǒng)計(jì)特性則由以下的轉(zhuǎn)移概率簡(jiǎn)記例 二階平穩(wěn)為馬氏信源信源狀態(tài)轉(zhuǎn)移概率矩陣和狀態(tài)轉(zhuǎn)移圖為(0|00)0.8, (1|11)0.8, (1|00)(0|11)0.2(0|01)(0|10)(1|01)(1|10)0.5PPPPPPPP39原狀態(tài)為原狀

30、態(tài)為0000，則此刻只可能則此刻只可能發(fā)出發(fā)出0 0或或1.1.所以所以只可能轉(zhuǎn)到只可能轉(zhuǎn)到0000、0101狀態(tài)狀態(tài). .由于由于0000狀態(tài)時(shí)狀態(tài)時(shí)發(fā)信號(hào)發(fā)信號(hào)0 0的概率的概率為為0.80.8，所以轉(zhuǎn)，所以轉(zhuǎn)移概率移概率.40 平穩(wěn)遍歷信源：即信源序列是平穩(wěn)遍歷信源：即信源序列是平穩(wěn)遍歷平穩(wěn)遍歷過(guò)程過(guò)程. 隨機(jī)過(guò)程可以從隨機(jī)過(guò)程可以從任一狀態(tài)有限任一狀態(tài)有限步到達(dá)任何步到達(dá)任何其他狀態(tài)其他狀態(tài)41 反例反例 例例3.3.非遍歷信源非遍歷信源狀態(tài)轉(zhuǎn)移圖狀態(tài)轉(zhuǎn)移圖 (1|00)(0|11)0PP類似于概率論中著名的類似于概率論中著名的兩端帶有吸收壁的隨機(jī)兩端帶有吸收壁的隨機(jī)游動(dòng)

31、問(wèn)題游動(dòng)問(wèn)題. .質(zhì)點(diǎn)最終一定被兩端點(diǎn)質(zhì)點(diǎn)最終一定被兩端點(diǎn)之一吸收！之一吸收！42（4）馬爾可夫鏈）馬爾可夫鏈 設(shè)設(shè) 為一隨機(jī)序列，如果對(duì)所有為一隨機(jī)序列，如果對(duì)所有 ，有，有則稱則稱 為為馬爾可夫鏈馬爾可夫鏈.,1nXn 1n 11111211|,|nnnnnnininiininiP XsXsXsXsp XsXs,1nXn 12,JSs ss12,Ss sl 如果馬爾可夫鏈的狀態(tài)空間如果馬爾可夫鏈的狀態(tài)空間 有限，則稱有限，則稱為為有限狀態(tài)馬爾可夫鏈有限狀態(tài)馬爾可夫鏈；如果狀態(tài)空間；如果狀態(tài)空間 是無(wú)窮是無(wú)窮集合，則稱為集合，則稱為可數(shù)無(wú)窮狀態(tài)的馬爾可夫鏈可數(shù)無(wú)窮狀態(tài)的馬爾可夫鏈. 馬爾可夫

32、信源馬爾可夫信源43l 狀態(tài)轉(zhuǎn)移概率狀態(tài)轉(zhuǎn)移概率（描述馬氏鏈最重要的參數(shù)）（描述馬氏鏈最重要的參數(shù)）l 狀態(tài)轉(zhuǎn)移概率的性質(zhì)狀態(tài)轉(zhuǎn)移概率的性質(zhì)l 一步轉(zhuǎn)移概率一步轉(zhuǎn)移概率l k步轉(zhuǎn)移概率步轉(zhuǎn)移概率 ( , )|ijnjminmpm nP XsXsP Xj Xi( )0( , )1( )( , )1ijijj Sipm niipm n( ,1)( )ijijpm mpm( )( )|kijm kmpmP Xj Xi馬爾可夫信源馬爾可夫信源44l 齊次馬氏鏈可以用轉(zhuǎn)移概率矩陣或狀態(tài)轉(zhuǎn)移圖來(lái)描述齊次馬氏鏈可以用轉(zhuǎn)移概率矩陣或狀態(tài)轉(zhuǎn)移圖來(lái)描述.111212122212JJJJJJpppppppppP11

33、：0.750：0.51：0.50：0.250s2s11( )(|)ijmjmiijp mP XsXsp如果馬氏鏈狀態(tài)轉(zhuǎn)移概率與起始時(shí)刻無(wú)關(guān)，即對(duì)任意如果馬氏鏈狀態(tài)轉(zhuǎn)移概率與起始時(shí)刻無(wú)關(guān)，即對(duì)任意m m，有有 ，則稱為，則稱為齊次馬爾可夫鏈齊次馬爾可夫鏈，也稱具有也稱具有平穩(wěn)轉(zhuǎn)移概率的馬爾可夫鏈平穩(wěn)轉(zhuǎn)移概率的馬爾可夫鏈. . 馬爾可夫信源馬爾可夫信源45l 信源的相關(guān)性信源的相關(guān)性就是信源符號(hào)間的依賴程度。就是信源符號(hào)間的依賴程度。l 設(shè)信源有設(shè)信源有q q個(gè)符號(hào)，那么對(duì)于不同情況可以分別計(jì)算信源個(gè)符號(hào)，那么對(duì)于不同情況可以分別計(jì)算信源的熵的熵0logHq11()HH X221(|)HH XX1

34、112(|)mmmHH XX XX121lim(|)NNNHH XX XX（獨(dú)立等概信源）（獨(dú)立等概信源）（平穩(wěn)無(wú)記憶信源）（平穩(wěn)無(wú)記憶信源）(一階馬爾可夫信源一階馬爾可夫信源) (有記憶有記憶)(m階馬爾可夫信源階馬爾可夫信源) (有記憶有記憶)（記憶長(zhǎng)度無(wú)限的信源）（記憶長(zhǎng)度無(wú)限的信源）7.7.信源的相關(guān)性和冗余度信源的相關(guān)性和冗余度46l 對(duì)同一信源，采用不同的模型，計(jì)算得到的熵的對(duì)同一信源，采用不同的模型，計(jì)算得到的熵的關(guān)系為關(guān)系為0121mHHHHHl 由此可見(jiàn)，由于信源輸出符號(hào)之間的依賴關(guān)系而由此可見(jiàn)，由于信源輸出符號(hào)之間的依賴關(guān)系而使信源的平均符號(hào)熵減少。如果它們之間的依賴關(guān)使信

35、源的平均符號(hào)熵減少。如果它們之間的依賴關(guān)系即相關(guān)性越大，信源的平均符號(hào)熵越小。并且，系即相關(guān)性越大，信源的平均符號(hào)熵越小。并且，只有當(dāng)信源輸出符號(hào)之間彼此獨(dú)立且各符號(hào)以等概只有當(dāng)信源輸出符號(hào)之間彼此獨(dú)立且各符號(hào)以等概率分布時(shí)，信源的符號(hào)熵才有最大值。為了衡量信率分布時(shí)，信源的符號(hào)熵才有最大值。為了衡量信源的相關(guān)性程度，引入信源冗余度的概念源的相關(guān)性程度，引入信源冗余度的概念。信源的相關(guān)性和冗余度信源的相關(guān)性和冗余度47l 信源熵的相對(duì)率信源熵的相對(duì)率：信源實(shí)際信息熵與具有同樣：信源實(shí)際信息熵與具有同樣符號(hào)集的最大熵的比值，通常也稱為符號(hào)集的最大熵的比值，通常也稱為效率效率。00(),()log

36、.()HXHXHXl 信源的冗余度信源的冗余度0111logHHRH 首先給出熵的相對(duì)率的定義首先給出熵的相對(duì)率的定義冗余度越低冗余度越低, ,信源輸出信號(hào)攜帶信息的有效性越高信源輸出信號(hào)攜帶信息的有效性越高. .l信源的信源的相對(duì)冗余度相對(duì)冗余度（剩余度）（剩余度）log()HX7.7.信源的相關(guān)性和冗余度信源的相關(guān)性和冗余度48例例 計(jì)算漢字的剩余度。計(jì)算漢字的剩余度。 假設(shè)常用漢字約為假設(shè)常用漢字約為10000個(gè)，其中個(gè)，其中140個(gè)漢字出個(gè)漢字出現(xiàn)的概率占現(xiàn)的概率占50%，625個(gè)漢字（含個(gè)漢字（含140個(gè)）出現(xiàn)的概個(gè)）出現(xiàn)的概率占率占85%，2400個(gè)漢字（含個(gè)漢字（含625個(gè)）出現(xiàn)

37、的概率占個(gè)）出現(xiàn)的概率占99.7%，其余，其余7600個(gè)漢字出現(xiàn)的概率占個(gè)漢字出現(xiàn)的概率占0.3%，不考，不考慮符號(hào)間的相關(guān)性，只考慮它的概率分布，在這一慮符號(hào)間的相關(guān)性，只考慮它的概率分布，在這一級(jí)近似下計(jì)算漢字的剩余度級(jí)近似下計(jì)算漢字的剩余度. .49解解 為了計(jì)算方便，假設(shè)每類中漢字出現(xiàn)是等概率的。為了計(jì)算方便，假設(shè)每類中漢字出現(xiàn)是等概率的。類別類別漢字個(gè)數(shù)漢字個(gè)數(shù) 所占概率所占概率每個(gè)漢字的概率每個(gè)漢字的概率11400.50.5/1402625-140=4850.85-0.5=0.350.35/48532400-625=17750.997-0.85=0.1470.147/1775476

38、000.0030.003/7600H1=H(X) =9.773 bit/漢字H0=13.288 bit/漢字 1010.264HRH 50 緒論中提到信源編碼和信道編碼。信源編碼目的就緒論中提到信源編碼和信道編碼。信源編碼目的就是通過(guò)減少或消除信源冗余度來(lái)提高信息傳輸效率；是通過(guò)減少或消除信源冗余度來(lái)提高信息傳輸效率；信道編碼的目的是通過(guò)增加消息的冗余度來(lái)提高抗信道編碼的目的是通過(guò)增加消息的冗余度來(lái)提高抗干擾能力，即提高信息傳輸?shù)目煽啃?。因此，干擾能力，即提高信息傳輸?shù)目煽啃浴Ｒ虼?，信源信源編碼也稱為有效性編碼，信道編碼也稱為可靠性編編碼也稱為有效性編碼，信道編碼也稱為可靠性編碼。碼。 由于信

39、源存在冗余度由于信源存在冗余度, ,即存在一些不必要傳送的信息即存在一些不必要傳送的信息, ,因此信源也就存在進(jìn)一步壓縮其信息率的可能性。因此信源也就存在進(jìn)一步壓縮其信息率的可能性。 信源冗余度越大信源冗余度越大, ,其進(jìn)一步壓縮的潛力越大。這是信其進(jìn)一步壓縮的潛力越大。這是信源編碼與數(shù)據(jù)壓縮的前提與理論基礎(chǔ)。源編碼與數(shù)據(jù)壓縮的前提與理論基礎(chǔ)。512.3 2.3 52 信息論中，漸近等分性是弱大數(shù)定理的應(yīng)用信息論中，漸近等分性是弱大數(shù)定理的應(yīng)用. . 大數(shù)定理大數(shù)定理指出：對(duì)于統(tǒng)計(jì)獨(dú)立、有等同分布的隨指出：對(duì)于統(tǒng)計(jì)獨(dú)立、有等同分布的隨機(jī)變量機(jī)變量 ，只要，只要n足夠大，足夠大， 就接近就接近數(shù)

40、學(xué)期望數(shù)學(xué)期望 漸近等分性漸近等分性指出，對(duì)于統(tǒng)計(jì)獨(dú)立、有等同分布的指出，對(duì)于統(tǒng)計(jì)獨(dú)立、有等同分布的隨機(jī)變量隨機(jī)變量 ，只要，只要n足夠大，聯(lián)合概率足夠大，聯(lián)合概率就接近信源熵就接近信源熵12,nXXX11niiXnE X12,nXXX()H X2.3 2.3 8. 8. 漸近等分性質(zhì)漸近等分性質(zhì)531212( ),(),.,()() (). ()(),().()knnnnnnnnXp xXH XXXXXP XP XP XP XP XXP XP X 設(shè)都是互相獨(dú)立且服從相同的分布用表示有相同分布的生成變量 并設(shè)記由于信源的無(wú)記憶性,有. 因?yàn)槭请S機(jī)變量的函數(shù) 所以是隨機(jī)變量 下面討論的弱漸近等

41、分性(AEP).8. 8. 漸近等分性質(zhì)漸近等分性質(zhì)5412(,1)1log(). )knnnXkPXXXXXnH X 對(duì)無(wú)記憶信源,有依概率收斂到其中定理漸近等分性質(zhì)漸近等分性質(zhì)1211log()log() (). ()nnP XP XP XP Xnn 證11log ()(log()()nkkP XEp XH Xn .由于相互獨(dú)立隨機(jī)變量的函數(shù)也是隨機(jī)變量及弱大數(shù)定理由于相互獨(dú)立隨機(jī)變量的函數(shù)也是隨機(jī)變量及弱大數(shù)定理Xi是統(tǒng)計(jì)獨(dú)立，是統(tǒng)計(jì)獨(dú)立，且服從分布且服從分布p(x);視為一個(gè)擴(kuò)展信源視為一個(gè)擴(kuò)展信源55 定義定義 稱滿足性質(zhì)稱滿足性質(zhì)的的n長(zhǎng)序列為弱典型序列，或長(zhǎng)序列為弱典型序列，或

42、- -典型序列典型序列. . 記所有集為記所有集為1|log()()|1nrPp XH Xn ( ).nW定義式等價(jià)于：定義式等價(jià)于：( )( ):1nnnnrrP WPXXW 漸近等分性質(zhì)漸近等分性質(zhì)下面研究弱典型序列的性質(zhì)：下面研究弱典型序列的性質(zhì)：56( )1()log()(),nnnXWH XP XH Xn 這時(shí)對(duì)每個(gè)都有1log()(),1|log()() |1.nnrP XH XnPP XH Xn因?yàn)橐栏怕适諗康郊磳?duì)0,( )( )( )1:|log()()|,:1.nnnnnnnrrWXP XH XnP WP XXW 記則()()()2.n H Xnn H Xp X即 2漸近等分

43、性質(zhì)漸近等分性質(zhì)弱弱典典型型序序列列的的性性質(zhì)：質(zhì)：57()()()()()()()()()()()()0,(1)()2;(2),:1;(3),1,(1).nnnHXnnHXnnnnrrnnHXnrnHXnnHnXXWp XnPWPXXWnWPWWW 對(duì)有若,則2當(dāng)充 分 大 時(shí) 當(dāng)充 分定大的 性 質(zhì)2:理時(shí)22( )()| 2nn XW()()2nnH XP X58()( )()()2;,.nnH XnnnnH XXP XWX 定理說(shuō)明了弱典型序列的概率弱典型序列集中元素個(gè)數(shù)但它不包括所有序列28. 8. 漸近等分性質(zhì)漸近等分性質(zhì),ninXnX 因?yàn)槿羧≈涤邢薹?hào)集則 長(zhǎng)的序列的總數(shù)是弱典

44、型序列集在其中所占比例為( )()(log()log0.21()()log)nnH XnnH XnniWXp XxH X22(當(dāng)不是均勻分布時(shí),弱典型序列只占全體序列的一小部分！弱典型序列只占全體序列的一小部分！592.4 2.4 60 任何一個(gè)離散隨機(jī)序列信源當(dāng)序列長(zhǎng)度任何一個(gè)離散隨機(jī)序列信源當(dāng)序列長(zhǎng)度n n 時(shí)時(shí), ,信源序列會(huì)產(chǎn)生兩極分化：信源序列會(huì)產(chǎn)生兩極分化： 大概率事件集合大概率事件集合 與小概率事件集合與小概率事件集合. . 由此可見(jiàn)，信源編碼只需對(duì)信源中由此可見(jiàn)，信源編碼只需對(duì)信源中少數(shù)少數(shù)落入典型落入典型大概率事件的集合的符號(hào)進(jìn)行編碼即可；大概率事件的集合的符號(hào)進(jìn)行編碼即可；

45、 而對(duì)而對(duì)大多數(shù)大多數(shù)屬于非典型小概率事件集合中的信源屬于非典型小概率事件集合中的信源符號(hào)無(wú)需編碼符號(hào)無(wú)需編碼. .碼字總數(shù)減少，碼字總數(shù)減少，所需碼長(zhǎng)可以減少所需碼長(zhǎng)可以減少2.42.4節(jié)節(jié) 9.9.信源編碼定理信源編碼定理611(,.,( ),nnXXXp xn 設(shè))是服從公共分布的無(wú)記憶信源產(chǎn)生的 長(zhǎng)序列 我們希望找到一種有效(1)編碼以后的碼字盡可能地少;(2)從碼字復(fù)的編碼方法原原序列的來(lái)描述這些序列,誤差概率使得盡可能小.9.9.信源編碼定理信源編碼定理62( )( )( )( )( )1,2,.,.,nnnnnnnninnXWIMWXWiIXWXW 一一種種有有效效的的編編碼碼方方法法是是