信息論基礎第二章

第一頁，共六十八頁，2022年，8月28日1第一節(jié)信源和隨機過程的基本概念第二節(jié)隨機過程的信息度量第三節(jié)漸進等分性質(zhì)第四節(jié)漸進等分性質(zhì)在數(shù)據(jù)壓縮中的作用–信源編碼定理第五節(jié)Shannon-McMillan-Breiman定理第二頁，共六十八頁，2022年，8月28日2§2.1信源和隨機過程的基本概念 信源即信息的來源，信源的輸出稱為消息，消息有各種類型，如文本、語音、圖像等。消息要轉(zhuǎn)換成信號進行傳輸。 通常信源的輸出是隨機的，即事前無法肯定其輸出，但其服從一定的隨機規(guī)律，因此利用隨機過程或隨機序列來建立信源的數(shù)學模型成為必然。第三頁，共六十八頁，2022年，8月28日3 不同類型的信源具有不同的性質(zhì)，因此涉及到信源的分類。 按照信源的信號取值集合和信號取值時刻的離散或連續(xù)性可分為四類。 信源按其數(shù)學模型隨機過程的統(tǒng)計特征分類可分為有記憶/無記憶、平穩(wěn)、遍歷、馬氏等類型信源。 本章只討論離散信源。第四頁，共六十八頁，2022年，8月28日4離散隨機過程的定義 一個離散信源的輸出為一個取值于有限字母集的一個隨機過程，記為 其中稱為狀態(tài)集。一個離散隨機過程是一系列隨機變量，它是由一簇聯(lián)合分布

唯一決定第五頁，共六十八頁，2022年，8月28日5無記憶信源 當為相互獨立的隨機變量，且服從相同的分布：

對任意的i成立時，信源為無記憶信源第六頁，共六十八頁，2022年，8月28日6

k-階馬爾可夫信源 稱一個離散隨機過程為k-階馬爾可夫過程，如果

對任意的m>k>0和成立。 特別當k＝1時，稱為馬爾可夫過程，此時第七頁，共六十八頁，2022年，8月28日7 此時聯(lián)合概率可簡化為

如果一個信源序列是k-階馬爾可夫過程，稱信源為k-階馬爾可夫信源，k＝1時稱為馬爾可夫信源，對于k-階馬爾可夫信源通?？梢杂棉D(zhuǎn)移概率矩陣或狀態(tài)轉(zhuǎn)移圖描述。第八頁，共六十八頁，2022年，8月28日8例一階平穩(wěn)馬氏信源 設是取值于的一個一階平穩(wěn)馬氏信源，其平穩(wěn)分布為 一步轉(zhuǎn)移概率為第九頁，共六十八頁，2022年，8月28日9 則用轉(zhuǎn)移概率矩陣表示為

也可用狀態(tài)轉(zhuǎn)移圖表示為01第十頁，共六十八頁，2022年，8月28日10 其n長序列的聯(lián)合分布為：第十一頁，共六十八頁，2022年，8月28日11例二階平穩(wěn)馬氏信源 設是取值于的二階平穩(wěn)信源，其狀態(tài)可用兩個二進數(shù)字表示，共有四種00，01，10，11，信源的統(tǒng)計特性由以下轉(zhuǎn)移概率給出

用轉(zhuǎn)移概率矩陣表示為

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

用狀態(tài)轉(zhuǎn)移圖表示為00011110第十三頁，共六十八頁，2022年，8月28日13 如果把初始狀態(tài)記為，則信源的聯(lián)合分布為第十四頁，共六十八頁，2022年，8月28日14平穩(wěn)信源 稱離散隨機過程為平穩(wěn)的，若對任意的正整數(shù)k，及任意的正整數(shù) 與有相同的聯(lián)合分布，即

第十五頁，共六十八頁，2022年，8月28日15 如果一個馬氏過程是平穩(wěn)的，則

對任意的m>0成立，即此時轉(zhuǎn)移概率不依賴時間，此時稱狀態(tài)轉(zhuǎn)移矩陣 為馬氏過程的公共轉(zhuǎn)移矩陣，這時稱馬氏過程為齊次馬氏鏈。第十六頁，共六十八頁，2022年，8月28日16 若存在上的一個概率分布，滿足 則稱其為馬氏過程的平穩(wěn)分布。 顯然，對于平穩(wěn)馬氏過程來說 對任意的m>0成立，這時馬氏過程完全由該平穩(wěn)分布和轉(zhuǎn)移概率決定。 如果一個信源序列是平穩(wěn)過程，則稱該信源為平穩(wěn)信源，如果一個信源序列是平穩(wěn)馬氏過程，稱信源為平穩(wěn)馬氏信源。第十七頁，共六十八頁，2022年，8月28日17

遍歷信源 設為一實數(shù)列，用T表示移位算子，，稱實數(shù)列集合A為平移不變集，如果當且僅當。 稱一個平穩(wěn)過程為遍歷的，如果對任何平移不變集A有 直觀的說，遍歷的馬氏過程從任何一個狀態(tài)出發(fā)可以在有限步到達其他狀態(tài)。第十八頁，共六十八頁，2022年，8月28日18 大多數(shù)的馬氏信源是遍歷的，下一信源為非遍歷的00011110吸收態(tài)第十九頁，共六十八頁，2022年，8月28日19定理2.1.1弱大數(shù)定律第二十頁，共六十八頁，2022年，8月28日20定理2.1.2強大數(shù)定律第二十一頁，共六十八頁，2022年，8月28日21 一個信源序列如果使強大數(shù)定律成立，稱它為平均遍歷的。 一個無記憶信源在適當條件下是平均遍歷的。平穩(wěn)遍歷信源是平均遍歷的，但反之不成立。逆反命題是：一個信源如不滿足平均遍歷性（即強大數(shù)定律），則必是非遍歷的。第二十二頁，共六十八頁，2022年，8月28日22信源熵如何度量？[例]設某二維離散信源的原始信源的信源空間X={x1,x2,x3};P(X)={1/4,1/4,1/2},一維條件概率為：p(x1/x1)=1/2;p(x2/x1)=1/2;p(x3/x1)=0;p(x1/x2)=1/8;p(x2/x2)=3/4;p(x3/x2)=1/8;p(x1/x3)=0;p(x2/x3)=1/4;p(x3/x3)=3/4;原始信源的熵為：H(X)=1.5bit/符號條件熵：H(X2/X1)=1.4bit/符號可見：H(X2/X1)<H(X)二維信源的熵：H(X1,X2)=H(X1)+H(X2/X1)=2.9bit/消息每個信源符號提供的平均信息量為：H2(X)=H(X1,X2)/2=1.45bit/符號。第二十三頁，共六十八頁，2022年，8月28日23我們現(xiàn)在有兩種方法去近似信源的實際熵，一種是為1.45bit，但這種方法不太準確，因為它把兩個消息看成一組，認為兩組之間是統(tǒng)計獨立的，實際上它們之間是有關聯(lián)的；另一種是我們可以用條件熵來近似，為1.4bit，到底那一種正確呢？我們可以通過對一般離散平穩(wěn)信源的分析來找到這個答案。分析：我們用來近似信源的實際熵第二十四頁，共六十八頁，2022年，8月28日24§2.2隨機過程的信息度量

設是一個取值于有限字母集的離散隨機過程，記 為n維隨機變量的聯(lián)合熵，則有：

當隨機過程是平穩(wěn)的時，上式為第二十五頁，共六十八頁，2022年，8月28日25 滿足上式的數(shù)列稱為半可加數(shù)列，以下引理證明極限存在。

引理設是滿足的半可加數(shù)列，則第二十六頁，共六十八頁，2022年，8月28日26 設是平穩(wěn)信源，則 存在，且 稱為平穩(wěn)信源的熵率，以下給出其容易計算的另一形式。定理第二十七頁，共六十八頁，2022年，8月28日27定理 設為平穩(wěn)信源，則 （1）存在； （2） 證明：

第二十八頁，共六十八頁，2022年，8月28日28引理 數(shù)列 ，若有，則 證明：由已知，對任意 則當時第二十九頁，共六十八頁，2022年，8月28日29定理的證明 （1）易知是關于n遞減的，又由于條件熵的非負性，從而的極限存在。 （2）利用聯(lián)合熵的鏈式法則有

對上式兩邊取極限即得第三十頁，共六十八頁，2022年，8月28日30系 （1）設為無記憶信源，則熵率 （2）設為k-階馬爾可夫信源，則第三十一頁，共六十八頁，2022年，8月28日31 假設信源字母集的大小為n，易知 對于無無記憶信源來說有，這時如果信源概率分布不均勻，則不能最大限度攜帶信息，即存在冗余。 信息論中常用冗余度來描述信源輸出符合攜帶信息的有效程度。第三十二頁，共六十八頁，2022年，8月28日32定義 冗余度＝

相對冗余度＝

由定義可知冗余度越低，則信號攜帶信息的有效性越高，反正有效性約低。第三十三頁，共六十八頁，2022年，8月28日33 實際信源中很多都有相當大的冗余度，考慮一個輸出26個英文字母的信源 （1）若看作無記憶信源，且看作等概率且無空格，則該信源熵為

試分析此時冗余度？例題第三十四頁，共六十八頁，2022年，8月28日34space

0.2

;

E

0.105

;

T

0.072

;

O

0.0654

;

A

0.063

;

N

0.059

I

0.055

;

R

0.054

;

S

0.052

;

H

0.047

;

D

0.035

;

L

0.029

C

0.023

;

U

0.0225

;

M

0.021

;

P

0.0175

;

Y

0.012

;

W

0.012

G

0.011

;

B

0.0105

;

V

0.008

;

K

0.003

;

X

0.002

;

J

0.001

Q

0.001

;

Z

0.001

第三十五頁，共六十八頁，2022年，8月28日35 實際上，英文字母出現(xiàn)的頻率不同，可在相關密碼分析的書中可以找到，資料表明，若不將空格算在內(nèi)，熵為4.15，若將空格算在內(nèi)，熵為4.05。 試計算冗余度？第三十六頁，共六十八頁，2022年，8月28日36 若把字母間的關系考慮進去，則每個字母的熵更低，若考慮兩個字母間的相關關系，即看作馬氏信源，則熵率為3.6，貝爾統(tǒng)計8個字母間的關系，即看作7-階馬爾可夫信源，則熵率為2.6。申農(nóng)估計當考慮100個字母間的關系時熵率只有1。 但是冗余也不是不必要的，冗余的存在為我們提高通訊效率提供了基礎。比如mp3能將cd壓縮到11%。 因為如果沒有冗余，則要求系統(tǒng)不能出任何的錯誤！冗余的存在提高了抗錯能力，比如對贛&*師范*&院。 因此，冗余的存在，從而對于信號的要求可以降低。第三十七頁，共六十八頁，2022年，8月28日37例 對例中的馬氏信源，計算熵率第三十八頁，共六十八頁，2022年，8月28日38 計算例中的二階馬氏信源的熵率。(從狀態(tài)的角度再研究，見課本)例第三十九頁，共六十八頁，2022年，8月28日39§2.3漸進等分性 考慮一個無記憶信源，其中都互相獨立且服從相同的分布，記 ，由于信源的無記憶性，有

信源序列的漸進等分性質(zhì)是大數(shù)定律在信息論中的應用，漸進等分性在信源編碼問題中有重要應用。要注意的是是一個隨機變量，因為它是隨機向量的函數(shù)。下面來證明它的弱漸進等分性。第四十頁，共六十八頁，2022年，8月28日40定理 對無記憶信源有 依概率收斂于

要正確理解這里的，它是一個長度為n的信源序列，這里所謂的“信源序列”就是說是信源在正常情況下的發(fā)出的序列，它的個數(shù)總和絕不等于第四十一頁，共六十八頁，2022年，8月28日41證明： 由信源的無記憶性知 及弱大數(shù)定理易得。第四十二頁，共六十八頁，2022年，8月28日42 由上述定理知依概率收斂于 即： 以上是從平均角度來說，即從平均來說每個符號攜帶的信息量與接近。 如果我們記為滿足以下性質(zhì)的序列 的集合：第四十三頁，共六十八頁，2022年，8月28日43

則定理等價于

這時對于每個都有第四十四頁，共六十八頁，2022年，8月28日44 或者等價的為

由此我們可以估計出集合中元素的個數(shù)，記為 一方面：

一方面：第四十五頁，共六十八頁，2022年，8月28日45弱典型序列/典型序列 稱集合中的序列為弱典型序列，或稱典型序列。 對于典型序列有以下性質(zhì)：

定理：對任給的，有 （1）如，則 （2）當n充分大時， （3）當n充分大時，第四十六頁，共六十八頁，2022年，8月28日46

（1）弱典型序列總數(shù)可能只占總序列的小部分。

注意：第四十七頁，共六十八頁，2022年，8月28日47（2）弱典型序列總的概率近似為1，而非弱典型序列總的概率很??；但是這并不意味著弱典型序列的概率都大于非典型序列的概率。 如下例： 假設一個二值離散無記憶信源，其公共概率分布為： 因此：第四十八頁，共六十八頁，2022年，8月28日48

而典型序列的個數(shù)滿足：第四十九頁，共六十八頁，2022年，8月28日49§2.4信源編碼定理 對于無記憶信源產(chǎn)生的長度為n的信息序列，現(xiàn)要對其進行編碼，我們希望編碼后的碼字數(shù)盡可能的少，而譯碼的錯誤概率盡可能小。 利用典型序列的理論我們可以做到這些。 我們將所有的n長的信息序列分成兩部分，對于弱典型序列，每一個序列給予一個碼字，則碼字個數(shù)記為M＝第五十頁，共六十八頁，2022年，8月28日50 分成兩部分，對于弱典型序列 中的每一個序列分配一個編號，稱為一個碼字，碼字集為，其編號總數(shù)為。對于非典型序列，則統(tǒng)一一個編號為1。 在從編碼后的碼字復原原序列時，如果收到的碼字，則能唯一的復原成原來的序列。如果收到的碼字為1，若原序列 ，則無法正確地復原，就會產(chǎn)生錯誤。第五十一頁，共六十八頁，2022年，8月28日51 我們記以上編碼的碼率為，其誤差概率為 由弱漸進等分性：于是其碼率滿足：第五十二頁，共六十八頁，2022年，8月28日52 其誤差概率為 由上知，當n充分大時，碼率接近于，而誤差概率趨于0，此謂之信源編碼正定理

第五十三頁，共六十八頁，2022年，8月28日53 反之，如果我們用少于比特的碼率對信源序列進行壓縮編碼行不行呢？答案是否定的?？梢宰C明，如果碼率，其中 不隨n改變，則當時。證明如下： 假設用碼率為的n長的分組碼進行編碼，則碼字總數(shù)為（ ），我們用其中一部分對典型序列進行編碼，其它的對非典第五十四頁，共六十八頁，2022年，8月28日54 型序列編碼，則能被編碼的典型序列的總概率的上界為：