第三章 信源及信源熵

第三章信源及信源熵第一頁，共六十頁，2022年，8月28日第三章信源及信源熵信源的主要問題：信源的描述（數(shù)學(xué)建模）；信源輸出信息能力的定量分析（信源熵）；信源信息的有效表示（信息編碼）。編碼器信道譯碼器信宿噪聲源信源第二頁，共六十頁，2022年，8月28日第三章信源及信源熵3.1信源的分類及其數(shù)學(xué)模型3.2離散單符號信源3.3離散多符號信源3.3.1離散平穩(wěn)信源3.3.2離散平穩(wěn)無記憶信源3.3.3離散平穩(wěn)有記憶信源3.3.4馬爾可夫信源3.4信源的相關(guān)性和剩余度第三頁，共六十頁，2022年，8月28日3.1信源的分類及其數(shù)學(xué)模型信源的分類分類1：根據(jù)信源輸出的消息在時間和取值上是離散或連續(xù)分。時間（空間)取值信源種類舉例數(shù)學(xué)描述離散離散離散信源（數(shù)字信源）文字、數(shù)據(jù)、離散化圖像

離散隨機(jī)變量序列

離散連續(xù)連續(xù)信號跳遠(yuǎn)比賽的結(jié)果、語音信號抽樣以后

連續(xù)隨機(jī)變量序列

連續(xù)連續(xù)波形信源（模擬信源）

語音、音樂、熱噪聲、圖形、圖像

隨機(jī)過程

連續(xù)離散不常見第四頁，共六十頁，2022年，8月28日3.1信源的分類及其數(shù)學(xué)模型分類2：根據(jù)各維隨機(jī)變量的概率分布是否隨時間的推移而變化分。 1）平穩(wěn)信源 2）非平穩(wěn)信源分類3：根據(jù)隨機(jī)變量間是否統(tǒng)計獨立分。 1）有記憶信源 2）無記憶信源第五頁，共六十頁，2022年，8月28日3.1信源的分類及其數(shù)學(xué)模型實際信源分類：信源第六頁，共六十頁，2022年，8月28日3.2離散單符號信源定義輸出單個離散取值的符號的信源稱為離散單符號信源。是最簡單也是最基本的信源，是組成實際信源的基本單元。用一個離散隨機(jī)變量表示。數(shù)學(xué)模型第七頁，共六十頁，2022年，8月28日3.2離散單符號信源信源輸出信息能力信源的平均自信息量（信息熵）：信源輸出的所有消息的自信息的統(tǒng)計平均值。舉例1 二元信源X輸出符號只有兩個，設(shè)為0和1。輸出符號發(fā)生的概率分別為p和q，p+q=1。即信源的概率空間為則該信源的熵為： 第八頁，共六十頁，2022年，8月28日3.2離散單符號信源舉例2 擲骰子： 為六元信源。則該信源的熵為： 第九頁，共六十頁，2022年，8月28日3.3離散多符號信源定義離散多符號信源：輸出為符號序列。用離散隨機(jī)變量序列（隨機(jī)矢量）表示，即：舉例以拋擲N次硬幣為研究對象的試驗中文自然語言文字離散多符號信源的實質(zhì)不是多個信源而是以由一個信源發(fā)出的多個符號為研究對象的等價信源。第十頁，共六十頁，2022年，8月28日3.3離散多符號信源理清與離散多符號信源相關(guān)的幾種常見信源的關(guān)系：離散平穩(wěn)信源

離散多符號信源輸出的隨機(jī)變量序列的統(tǒng)計特性往往比較復(fù)雜，分析起來比較困難。 為了便于分析，假設(shè)信源輸出的是平穩(wěn)隨機(jī)序列，即：

序列的統(tǒng)計特性與時間的推移（起點）無關(guān)。 實際中很多信源也滿足這個假設(shè)。舉例以拋擲N次硬幣為研究對象的試驗中文自然語言文字離散平穩(wěn)信源又分為無記憶信源和有記憶信源。均為離散平穩(wěn)信源第十一頁，共六十頁，2022年，8月28日3.3離散多符號信源離散平穩(wěn)無記憶信源

信源發(fā)出的各個符號彼此是統(tǒng)計獨立的。 對于多符號信源X=(X1X2…XN)，各隨機(jī)變量Xi(i=1,2,…,N)之間是統(tǒng)計獨立的，即： 稱該多符號信源為離散無記憶信源的N次擴(kuò)展信源。舉例以拋擲N次硬幣為研究對象的試驗一般情況下，信源在不同時刻發(fā)出的符號之間是相互依賴的，這種信源就為有記憶信源。 第十二頁，共六十頁，2022年，8月28日3.3離散多符號信源離散平穩(wěn)有記憶信源

實際上，許多信源發(fā)出的符號往往只與前若干個符號的依賴關(guān)系強(qiáng)，而與更前面符號的依賴關(guān)系弱。因此，在研究分析時可限制隨機(jī)序列的記憶長度。 當(dāng)記憶長度為m+1時，稱這種有記憶信源為m階馬爾可夫信源，即：

信源每次發(fā)出的符號只與前m個符號有關(guān)，與更前面的符號無關(guān)。舉例（離散平穩(wěn)有記憶信源）中文自然語言文字第十三頁，共六十頁，2022年，8月28日3.3.1離散平穩(wěn)信源

定義：對于隨機(jī)變量序列，在任意兩個不同時刻和(和為大于1的任意整數(shù))信源發(fā)出消息的概率分布完全相同，即對于任意的，和具有相同的概率分布。也就是:即各維聯(lián)合概率分布均與時間起點無關(guān)的信源稱為離散平穩(wěn)信源。第十四頁，共六十頁，2022年，8月28日3.3.1離散平穩(wěn)信源推論1

離散平穩(wěn)信源的條件概率分布與時間起點無關(guān)，只與關(guān)聯(lián)長度N有關(guān)。第十五頁，共六十頁，2022年，8月28日3.3.1離散平穩(wěn)信源推論2

第十六頁，共六十頁，2022年，8月28日

離散多符號平穩(wěn)信源不確定度的度量：

對于離散多符號信源,我們引入熵率的概念，它表示信源輸出的符號序列中，平均每個符號所攜帶的信息量。定義（熵率）：

隨機(jī)變量序列中，對前N個隨機(jī)變量的聯(lián)合熵求平均：

稱為平均符號熵。如果當(dāng)

時上式極限存在，則稱為熵率，或稱為極限熵，記為

3.3.1離散平穩(wěn)信源第十七頁，共六十頁，2022年，8月28日3.3.2離散平穩(wěn)無記憶信源定義

信源發(fā)出的各個符號彼此是統(tǒng)計獨立的。 對于多符號信源X=(X1X2…XN)，各隨機(jī)變量Xi(i=1,2,…,N)之間是統(tǒng)計獨立的，即： 稱該多符號信源為離散無記憶信源的N次擴(kuò)展信源。舉例以拋擲N次硬幣為研究對象的試驗

第十八頁，共六十頁，2022年，8月28日3.3.2離散平穩(wěn)無記憶信源分析信源熵

N次擴(kuò)展信源（N長離散平穩(wěn)無記憶信源）的熵等于單符號離散信源熵的N倍。

對N個獨立的隨機(jī)變量X1,X2,……,XN，有：平穩(wěn)第十九頁，共六十頁，2022年，8月28日3.3.2離散平穩(wěn)無記憶信源熵率 離散平穩(wěn)無記憶信源的熵率等于單符號離散信源熵。例1

離散無記憶信源為：X:{a1,a2,a3}；P(X):{1/4,1/2,1/4}，試求： 1）該信源的熵； 2）寫出該信源的二次擴(kuò)展信源，并求其概率分布； 3）根據(jù)2）中結(jié)果求該信源二次擴(kuò)展信源的信源熵及熵率。第二十頁，共六十頁，2022年，8月28日3.3.2離散平穩(wěn)無記憶信源 2）寫出該信源的二次擴(kuò)展信源，并求其概率分布；解： 二次擴(kuò)展信源為： 信源符號為： 其概率分布為：：{A1…A9}A1=a1a1A2=a1a2A3=a1a3A4=a2a1A5=a2a2A6=a2a3A7=a3a1A8=a3a2A9=a3a3A1A2A3A4A5A6A7A8A91/161/81/161/81/41/81/161/81/16第二十一頁，共六十頁，2022年，8月28日3.3.2離散平穩(wěn)無記憶信源 3）根據(jù)2）中結(jié)果求該信源二次擴(kuò)展信源的信源熵及熵率。 計算可得： 可見：A1A2A3A4A5A6A7A8A91/161/81/161/81/41/81/161/81/16第二十二頁，共六十頁，2022年，8月28日3.3.3離散平穩(wěn)有記憶信源離散平穩(wěn)有記憶信源定義

信源發(fā)出的符號間相互有依賴關(guān)系。分析信源熵獨立熵函數(shù)的鏈規(guī)則：對N個隨機(jī)變量X1,X2,……,XN，有：第二十三頁，共六十頁，2022年，8月28日回顧上節(jié)課的內(nèi)容信源及信源熵信源的主要問題信源的描述（數(shù)學(xué)建模）；信源輸出信息能力的定量分析（信源熵）；第二十四頁，共六十頁，2022年，8月28日回顧上節(jié)課的內(nèi)容離散單符號信源數(shù)學(xué)模型信息熵第二十五頁，共六十頁，2022年，8月28日回顧上節(jié)課的內(nèi)容離散多符號信源描述方法

實質(zhì)不是多個信源而是以由一個信源發(fā)出的多個符號為研究對象的等價信源。信息不確定程度的度量：熵率第二十六頁，共六十頁，2022年，8月28日回顧上節(jié)課的內(nèi)容實際信源分類：信源第二十七頁，共六十頁，2022年，8月28日3.3.3離散平穩(wěn)有記憶信源離散平穩(wěn)有記憶信源的幾個結(jié)論：（1）條件熵

隨N的增加是遞減的；

含義：記憶長度越長，條件熵越小； 即：序列的統(tǒng)計約束關(guān)系增加時，不確定性減少。（2）N給定時平均符號熵大于等于條件熵，即（3）平均符號熵隨N的增加是遞減的；

含義：序列的統(tǒng)計約束關(guān)系增加時，由于符號間的相關(guān)性，平均每個符號所攜帶的信息量減少。第二十八頁，共六十頁，2022年，8月28日3.3.3離散平穩(wěn)有記憶信源（4）如果，則存在，并且

含義：給出了計算熵率的另一種方法。 法1： 法2： 一般情況下，平穩(wěn)信源輸出的符號序列其相關(guān)性可追溯到最初的一個符號，故要準(zhǔn)確計算需確定無窮維聯(lián)合概率和條件概率，這相當(dāng)困難。為此：

常用N不太大時的平均符號熵或條件熵來作為熵率的近似值。第二十九頁，共六十頁，2022年，8月28日3.3.3離散平穩(wěn)有記憶信源馬爾可夫信源（離散平穩(wěn)有記憶信源的特例）：定義：信源在某時刻發(fā)出的符號僅與在此之前發(fā)出的有限個符號有關(guān)，而與更早些時候發(fā)出的符號無關(guān)，這稱為馬爾可夫性，這類信源稱為馬爾可夫信源。 如果信源在某時刻發(fā)出的符號僅與在此之前發(fā)出的m個符號有關(guān)，則稱為m階馬爾可夫信源。m階馬爾可夫信源熵率計算：馬爾可夫性平穩(wěn)性記憶長度？第三十頁，共六十頁，2022年，8月28日3.3.3離散平穩(wěn)有記憶信源例2

離散有記憶信源為：X:{x1,x2,x3}；P(X):{1/4,4/9,11/36}，輸出符號序列中，只有前后兩個符號有記憶，條件概率P(X2|X1)如下表所示：

求：1）該信源熵率； 2）比較H(X2|X1),?*H(X1X2),H(X)。x1x2x3x17/92/90x21/83/41/8x302/119/11X2X1第三十一頁，共六十頁，2022年，8月28日3.3.3離散平穩(wěn)有記憶信源解：

1)只有前后兩個符號有記憶，故為馬爾可夫信源，則： 2）比較H(X2|X1),?*H(X1X2),H(X)?？梢姡旱谌?，共六十頁，2022年，8月28日3.3.4馬爾可夫信源定義： 信源在某時刻發(fā)出的符號僅與在此之前發(fā)出的有限個符號有關(guān)，而與更早些時候發(fā)出的符號無關(guān)，這稱為馬爾可夫性，這類信源稱為馬爾可夫信源。

隨機(jī)矢量序列符號序列狀態(tài)序列（集）馬爾可夫鏈第三十三頁，共六十頁，2022年，8月28日3.3.4馬爾可夫信源馬爾可夫信源模型：對于一般的階馬爾可夫信源，它的概率空間可以表示成：令，從而得到馬爾可夫信源的狀態(tài)空間為：狀態(tài)空間由所有狀態(tài)及狀態(tài)間的狀態(tài)轉(zhuǎn)移概率組成。

符號轉(zhuǎn)移概率第三十四頁，共六十頁，2022年，8月28日3.3.4馬爾可夫信源狀態(tài)轉(zhuǎn)移概率計算：馬爾可夫鏈的狀態(tài)轉(zhuǎn)移圖 1）每個圓圈代表一種狀態(tài)； 2）狀態(tài)之間的有向線代表某一狀態(tài)向另一狀態(tài)的轉(zhuǎn)移； 3）有向線一側(cè)的符號和數(shù)字分別代表發(fā)出的符號和條件概率。二元一階馬爾可夫信源狀態(tài)轉(zhuǎn)移圖舉例：

一階馬爾可夫信源的狀態(tài)轉(zhuǎn)移概率等于符號轉(zhuǎn)移概率（信源輸出符號的條件概率）。

1：0.750：0.50：0.251：0.5第三十五頁，共六十頁，2022年，8月28日3.3.4馬爾可夫信源狀態(tài)轉(zhuǎn)移概率算法（以二元二階馬爾可夫信源為例）： 設(shè)一個二元二階馬爾可夫信源，原始符號集為{1,0}，信源輸出符號條件概率為： P(0|00)=P(1|11)=0.8P(1|00)=P(0|11)=0.2P(0|01)=P(0|10)=P(1|01)=P(1|10)=0.5試求其狀態(tài)轉(zhuǎn)移概率。解：1）確定狀態(tài)數(shù)：

由題得：可能的狀態(tài)為：qm第三十六頁，共六十頁，2022年，8月28日3.3.4馬爾可夫信源

2）由條件概率分析狀態(tài)轉(zhuǎn)移概率：

信源輸出符號條件概率為： P(0|00)=P(1|11)=0.8P(1|00)=P(0|11)=0.2P(0|01)=P(0|10)=P(1|01)=P(1|10)=0.5信源的狀態(tài)為：狀態(tài)之間的轉(zhuǎn)移概率為：p(s1|s1)=p(s2|s1)=p(s3|s1)=p(s4|s1)=p(s1|s2)=p(s2|s2)=p(s3|s2)=p(s4|s2)=p(s1|s3)=p(s2|s3)=p(s3|s3)=p(s4|s3)=p(s1|s4)=p(s2|s4)=p(s3|s4)=p(s4|s4)=第三十七頁，共六十頁，2022年，8月28日3.3.4馬爾可夫信源 則狀態(tài)轉(zhuǎn)移圖為： 也可寫作狀態(tài)轉(zhuǎn)移矩陣形式：01100:0.51:0.20:0.2000:0.8111:0.81:0.50:0.51:0.5ij第三十八頁，共六十頁，2022年，8月28日3.3.4馬爾可夫信源m階馬爾可夫信源熵率的計算：即：m階馬爾可夫信源的極限熵H∞等于條件熵Hm+1。（只介紹齊次遍歷馬爾可夫信源極限熵的計算。）（補(bǔ)充齊次遍歷馬爾可夫鏈的定義。）馬爾可夫性平穩(wěn)性第三十九頁，共六十頁，2022年，8月28日3.3.4馬爾可夫信源（補(bǔ)充內(nèi)容）補(bǔ)充：對一般的馬爾可夫鏈，其狀態(tài)轉(zhuǎn)移概率可表示為：含義為：

馬爾可夫鏈在m時刻處于si的條件下，在m+n時刻處于sj的轉(zhuǎn)移概率。當(dāng)n=1時，，稱為一步轉(zhuǎn)移概率，其對應(yīng)的矩陣記為：當(dāng)n=k≠1時，，稱為k步轉(zhuǎn)移概率，其對應(yīng)的矩陣記為：第四十頁，共六十頁，2022年，8月28日3.3.4馬爾可夫信源（補(bǔ)充內(nèi)容）齊次（時齊）馬爾可夫鏈： 馬爾可夫鏈的轉(zhuǎn)移概率只與狀態(tài)si、sj和時間間隔n有關(guān)，而與時間起點m無關(guān)。則，記為：當(dāng)n=1時，，稱為一步轉(zhuǎn)移概率，其對應(yīng)的矩陣記為P。當(dāng)n=k≠1時，，稱為k步轉(zhuǎn)移概率，其對應(yīng)的矩陣記為。對于齊次馬爾可夫鏈，一步轉(zhuǎn)移概率完全決定k步轉(zhuǎn)移概率，即：第四十一頁，共六十頁，2022年，8月28日3.3.4馬爾可夫信源m階馬爾可夫信源熵率的計算：

即：齊次性馬爾可夫信源處于Si狀態(tài)的概率一步轉(zhuǎn)移概率第四十二頁，共六十頁，2022年，8月28日3.3.4馬爾可夫信源（補(bǔ)充內(nèi)容）某時刻的狀態(tài)的概率分布的確定：

在k時刻，馬爾可夫信源處于sj狀態(tài)的概率為： 其中，為初始概率。遍歷性（各態(tài)歷經(jīng)性）：

若齊次馬爾可夫鏈對一切i，j存在不依賴于i的極限：，并且，則稱其具有遍歷性（各態(tài)歷經(jīng)性），這時稱為極限分布或平穩(wěn)分布。含義： 馬爾可夫信源在初始時刻可以處于任意狀態(tài)，然后經(jīng)過足夠長的時間之后，信源所處的狀態(tài)已與初始狀態(tài)無關(guān)，這時，各種狀態(tài)出現(xiàn)的概率已達(dá)到一種穩(wěn)定分布，即平穩(wěn)分布，并將此分布記為Wj。第四十三頁，共六十頁，2022年，8月28日3.3.4馬爾可夫信源（補(bǔ)充內(nèi)容）時齊遍歷馬爾可夫信源某狀態(tài)概率分布的確定：

法1: 法2：

Wj是滿足方程組的唯一解。不易求解。Wj常用求解方法。第四十四頁，共六十頁，2022年，8月28日3.3.4馬爾可夫信源m階馬爾可夫信源熵率的計算：

即：齊次性極限分布Wi一步轉(zhuǎn)移概率第四十五頁，共六十頁，2022年，8月28日3.3.4馬爾可夫信源例：求圖示二階馬爾可夫信源 的極限熵。 解： 由圖得，該馬爾可夫信源為遍歷的，則：

1）求極限分布。

01100:0.51:0.20:0.2000:0.8111:0.81:0.50:0.51:0.5由狀態(tài)轉(zhuǎn)移圖中指向某狀態(tài)的箭頭確定。第四十六頁，共六十頁，2022年，8月28日3.3.4馬爾可夫信源2）求H∞。第四十七頁，共六十頁，2022年，8月28日3.3.4馬爾可夫信源2）求H∞。01100:0.51:0.20:0.2000:0.8111:0.81:0.50:0.51:0.5由狀態(tài)轉(zhuǎn)移圖中從某狀態(tài)發(fā)出的箭頭確定。第四十八頁，共六十頁，2022年，8月28日3.4信源的相關(guān)性和剩余度信源的相關(guān)性：定義：

信源輸出符號間的依賴關(guān)系。對于平穩(wěn)信源，可以用條件概率來描述信源間的相關(guān)性，且有：

離散平穩(wěn)信源m階Markov信源一階Markov信源實際信源離散無記憶信源等概的離散無記憶信源第四十九頁，共六十頁，2022年，8月28日3.4信源的相關(guān)性和剩余度信源的相關(guān)性：信源的記憶長度越長，信源熵越小。信源的記憶長度越短，信源熵越大。當(dāng)信源符號間彼此沒有任何依賴關(guān)系且呈等概率分布時，信源熵達(dá)到最大值。

對于固定的符號集，記憶長度短且概率分布相對均勻的信源更能有效地傳遞信息。第五十頁，共六十頁，2022年，8月28日3.4信源的相關(guān)性和剩余度舉例：

設(shè)信源符號集中符號個數(shù)為4。 則：符號獨立且等概時的最大熵H0為：log4=2bit； 若符號間有相關(guān)性且不等概分布，使得極限熵為1.2bit，則對由該符號集中10個符號構(gòu)成的消息，其信息熵為：1.2*10=12bit。 則： 1）信源1的10個符號可以表示的信息量為：20bit。 2）由信源2表示的12bit信息用信源1則只需6個符號即可。可見： 1）符號獨立且等概時的信源傳遞信息的效率高； 2）信源2中有4個符號是用于描述符號間的相關(guān)性的，而不是用于傳輸信息的，對于傳輸信息而言，這4個符號是冗余的。信源1信源2第五十一頁，共六十頁，2022年