第3章離散信源2

1、1,第三章離散信源,2,離散信源的分類及其描述 離散信源的熵 信源的冗余度 信源符號序列分組定理 平穩(wěn)離散信源及其性質,本章內容提要,3,通信系統(tǒng)的任務是將信源的消息有效可靠地傳送到信宿。 信源消息是多種多樣的。 本章將重點討論信源的數(shù)學模型以及如何度量信源消息中的信息。,第3章離散信源,4,從信源發(fā)出的消息在時間上和幅度上的分布 分為離散信源和連續(xù)信源； 從信源消息是模擬的還是數(shù)字的 分為模擬信源和數(shù)字信源； 對數(shù)字信源還可分為二進制信源和多進制信源。 對于離散信源，根據(jù)符號的特點以及符號間的關聯(lián)性 可分無記憶離散信源和有記憶離散信源 對于前者，又可分為發(fā)出單個符號的無記憶離散信源和發(fā)出符號

2、序列的無記憶離散信源 對于后者，又可分為發(fā)出符號序列的有記憶離散信源和發(fā)出符號序列的馬爾可夫（Markov）信源,3.1 離散信源的分類及其描述,3.1.1信源的分類,5,從描述信源消息的隨機過程的平穩(wěn)性角度 分為平穩(wěn)信源和非平穩(wěn)信源 按隨機過程的類別 分為高斯信源、馬爾可夫信源等 根據(jù)人們對信源消息的感知 分為數(shù)據(jù)信源、文本信源、語音信源、圖像信源等，其中文本信源和語音信源都是針對人類語言、文字、聲樂等感知的，又通稱為自然語信源。,3.1 離散信源的分類及其描述,3.1.1信源的分類,6,信源的分類方法可以有多種，但本質上主要基于兩方面的考慮： 一是信源消息取值的集合以及消息取值時刻的集合，

3、由此可分為離散信源、連續(xù)信源或數(shù)字信源、模擬信源等； 二是信源消息的統(tǒng)計特性，由此可分為無記憶（Memoryless）信源、有記憶（Memory）源、平穩(wěn)信源、非平穩(wěn)信源、高斯信源、馬爾可夫信源等。,3.1 離散信源的分類及其描述,3.1.1信源的分類,7,本章討論離散信源，包括無記憶和有記憶兩類。 前者分為發(fā)出單個符號的離散無記憶信源和發(fā)出符號序列的離散無記憶信源兩種， 后者分為發(fā)出符號序列的離散有記憶信源和發(fā)出符號序列的馬爾可夫信源兩種。 離散無記憶信源發(fā)出的各個消息符號是相互獨立的 發(fā)出單個符號的離散無記憶信源：每次只發(fā)出一個符號且每個符號代表一個消息 發(fā)出符號序列的離散無記憶信源：每次

4、發(fā)出一組不少于兩個的符號序列來代表一個消息。,3.1 離散信源的分類及其描述,3.1.1信源的分類,8,離散有記憶信源發(fā)出的各個消息符號是相互關聯(lián)的 發(fā)出符號序列的離散有記憶信源 關聯(lián)性可用其聯(lián)合概率來表示 發(fā)出符號序列的馬爾可夫信源 關聯(lián)性可用其條件概率來表示,3.1 離散信源的分類及其描述,3.1.1信源的分類,9,研究信源最主要的目的是為信源編碼服務。 信源編碼的目標是用盡可能少的碼元符號或盡可能低的數(shù)據(jù)速率來描述信源輸出的消息。 怎樣的信源編碼才是好的或者說是有效的? 信源參數(shù)測量 離散信源的數(shù)學模型及其信息的度量,3.1 離散信源的分類及其描述,3.1.1信源的分類,10,可以簡單地

5、將自然語信源定義為以人類的自然語言作為輸出消息的信源。 自然語言又可以分為書面語言和聲音語言兩大類 書面語言由一個個文字符號構成，是一種典型的離散信源， 也是信息論中首先討論和研究最多的信源， 以英文和中文為例討論書面語言， 聲音語言的信源放在第6章討論。,3.1 離散信源的分類及其描述,3.1.2自然語信源,11,英文信源 先將英文看成僅由26個字母和空格構成，即暫不考慮標點符號及其他。 英文中字母的組合構成單詞，單詞的組合構成句子，句子的組合構成段落和文章。 在某一個統(tǒng)計集合中能得出其字母、單詞、句子的分布概率。 例如通過大量統(tǒng)計得到的26個字母和空格的出現(xiàn)概率如表3. 1所示。它構成了英

6、文字母和空格的信源空間。 僅僅按照表中的出現(xiàn)概率隨機構成的一串字母序列通常并不能構成英文單詞，。 其構成還有許多語法和修辭方面的制約，這種制約在數(shù)學關系上的反映就是其關聯(lián)性。,3.1 離散信源的分類及其描述,3.1.2自然語信源,12,表3.1的一維概率分布是反映不出英文構成的關聯(lián)性。,3.1 離散信源的分類及其描述,3.1.2自然語信源,13,中文信源，通常指漢字 由字組詞、由詞組句、由句成文的本質與英文一樣 中文與英文的重要區(qū)別是每個單字都有明確的意義，而且數(shù)量巨大 收入辭海的漢字有1.5萬左右 收入康熙字典、漢語大字典分別超過了4萬個和6萬個。 要給出漢字的信源空間，須對大量的漢字文獻進

7、行統(tǒng)計 新華社曾對2億左右的漢字作了統(tǒng)計，得出了1850個漢字的使用率為98%的結論 當被統(tǒng)計的數(shù)量趨于無窮時，每個漢字的使用頻率應該趨于平穩(wěn),3.1 離散信源的分類及其描述,3.1.2自然語信源,14,漢字統(tǒng)計的成果已被總結成國家標準 例如：GB2312-80、GB18030-2000等， 給出了一級字庫、二級字庫和三級字庫 由于文字的使用總是與時俱進的，這種統(tǒng)計的工作必然一直是有意義的。 與英文類似，漢字同樣必須考慮其關聯(lián)性。,3.1 離散信源的分類及其描述,3.1.2自然語信源,15,可以用符號的聯(lián)合概率或條件概率來描述自然語信源的關聯(lián)性。 對于英文，可以將包含K個字母的單詞看成是具有K

8、個字母的符號序列，或稱為K重符號序列，將其作為一個整體消息，其聯(lián)合概率就已考慮了字母與字母間的關聯(lián)性了。 也可以把由漢字組成的中文詞匯作為符號序列。 還可以將句子、段落甚至整篇文章分別作為符號序列來考慮，用聯(lián)合概率來描述。 有了符號或符號序列的信源空間就可以度量它們出現(xiàn)時所給出的信息量，并可以計算它們的信源熵。,3.1 離散信源的分類及其描述,3.1.2自然語信源,16,但無論是符號概率還是符號序列的聯(lián)合概率都具有先驗概率的性質，只能描述靜態(tài)的情形，不能描述動態(tài)的過程。 條件概率描述了符號間的記憶特性，但它同時給出了符號間的轉移特性，故也稱之為轉移概率。 以用第一個字母為T來構成3個字母的英文

9、單詞為例，第二個字母為H的概率可以用條件概率 P(H|T)來表示，第三個字母為E的概率可以用條件概率P(E|TH)來表示，其他各種可能的組合也都可用其條件概率來表示。 用轉移概率來描述的信源是一種典型的馬爾可夫信源。,3.1 離散信源的分類及其描述,3.1.2自然語信源,17,馬爾可夫過程和馬爾可夫鏈的定義 定義3.1 設X(t)為一個隨機過程，若對任意的t1t2 tn時刻的隨機變量X(t1)，X(t2)，X(tn)，有 P( xn; tn | xn1, xn2, , x1; tn1, tn2, , t1) = P( xn; tn | xn1; tn1) (3.1) 則稱X(t)為單純馬爾可夫

10、過程或一階馬爾可夫過程。 一階馬爾可夫過程在tn時刻的隨機變量xn，僅和它前一時刻tn-1的隨機變量xn-1有關。,3.1 離散信源的分類及其描述,3.1.3馬爾可夫過程和馬爾可夫鏈,18,定義3.2 設X(t)為一個隨機過程，若對任意的t1t2tn k tn時刻的隨機變量X(t1)，X(t2)，X(tn k )，X(tn)，有 P( xn；tn |xn1, xn2, xn k, , x1；tn1, tn2, tn k, , t1) = P( xn；tn |xn1, xn2, , xn k ；tn1, tn2, tn k ) (3.2) 則稱X(t)為K階馬爾可夫過程。 定義3.2說明，K階馬

11、爾可夫過程在tn時刻的隨機變量xn，僅和它前k個時刻tn 1 , tn 2 , , tn k 的隨機變量xn 1 , xn 2, , xn k 有關。,3.1 離散信源的分類及其描述,3.1.3馬爾可夫過程和馬爾可夫鏈,19,當馬爾可夫過程的隨機變量的值和時間均取離散值時，該馬爾可夫過程就稱為馬爾可夫鏈。 定義3.3 設隨機過程X(t)在時間域T=t1，t2，tn的n個時刻上的狀態(tài)xk (k=1, 2, , n)都是離散型的隨機變量，并且xk有M個可能的取值s1，s2，sM，這M個取值構成一個狀態(tài)空間S，即S=s1，s2，sM，在n個時刻上的n個狀態(tài)構成一個隨機序列(x1，x2，xk1，xk，

12、xn1，xn)，對這個隨機序列，若 P( xn = si,n | xn1 = si,n 1 ，xn2 = si,n 2 ，x2 = si,2，x1 = si,1) = P( xn= si,n | xn1= si,n 1 ) (3.3) 則稱此序列為單純馬爾可夫鏈或一階馬爾可夫鏈。,3.1 離散信源的分類及其描述,3.1.3馬爾可夫過程和馬爾可夫鏈,20,定義3.3說明，一階馬爾可夫鏈在tn時刻取值xn= si,n的概率，僅與它前一時刻tn 1 的狀態(tài)xn-1有關，而與其他時刻的狀態(tài)無關。由此可見，一階馬爾可夫鏈的記憶長度為2個時刻tn 1 和tn。,3.1 離散信源的分類及其描述,3.1.3馬

13、爾可夫過程和馬爾可夫鏈,21,定義3.4 設隨機過程X(t)在時間域T=t1，t2，tn的n個時刻上的狀態(tài)xk (k =1，2，n)都是離散型的隨機變量，并且xk有M個可能的取值s1，s2，sM，這M個取值構成一個狀態(tài)空間S，即S=s1，s2，sM，在n個時刻上的n個狀態(tài)構成一個隨機序列(x1，x2，xk1，xk，xn1，xn)，對此隨機序列，若,P( xn= si, n | xn1= si, n 1, xn2= si, n 2, , xk= si, n k, , x2= si,2, x1= si,1) = P( xn = si, n | xn1 = si, n 1，xn2 = si, n 2

14、，xk = si, n k ) (3.4),則稱此序列為K 階馬爾可夫鏈,3.1 離散信源的分類及其描述,3.1.3馬爾可夫過程和馬爾可夫鏈,22,定義3.4說明，K 階馬爾可夫鏈在tn時刻取值xn = si, n的概率，與它前k個時刻tn 1，tn 2，tn k的k個狀態(tài) xn 1，xn2，xk有關。K 階馬爾可夫鏈的記憶長度為(k+1)個時刻。 馬爾可夫信源發(fā)出消息的方式體現(xiàn)在馬爾可夫鏈的狀態(tài)轉移上，可以用條件概率（或稱為轉移概率）來描述這種轉移。 例如，若一階馬爾可夫鏈在tk-1時刻隨機序列的取值 xk1 = si，而在下一個時刻tk隨機序列的取值xk= sj，分別稱為狀態(tài)si 和狀態(tài)s

15、j，簡稱為狀態(tài)i和狀態(tài)j，則由狀態(tài)i轉移到狀態(tài)j的轉移概率可寫為 P(j|i) = P( xk = sj | xk1 = si) (3.5),3.1 離散信源的分類及其描述,3.1.3馬爾可夫過程和馬爾可夫鏈,23,2. 馬爾可夫鏈的轉移概率 對于一階馬爾可夫鏈，每一時刻隨機變量xk ( k = 1，2，n )可能的取值都是狀態(tài)空間S = s1，s2，sM 中的一個，由式(3.5)，當i、j分別取1，2， ，M時，就得到M個狀態(tài)時所有可能的轉移概率，構成如下的矩陣： (3.6),3.1 離散信源的分類及其描述,3.1.3馬爾可夫過程和馬爾可夫鏈,24,式(3.6)是一個具有M 2個元素的方陣，

16、表示共有M2個可能的轉移概率數(shù)目 每行元素代表同一個起始狀態(tài)到M個不同的終止狀態(tài)的轉移概率， 每列元素代表M個不同的起始狀態(tài)到同一個終止狀態(tài)的轉移概率， 顯然有 i1, 2, , M (3.7),3.1 離散信源的分類及其描述,3.1.3馬爾可夫過程和馬爾可夫鏈,25,一階馬爾可夫鏈的狀態(tài)為si (i=1, 2, , M)。令S表示其狀態(tài)數(shù)，T表示轉移概率的總數(shù)目，則 S = M，T = M 2 (3.8) 對于K階馬爾可夫鏈，每個狀態(tài)都與前k個狀態(tài)有關，故狀態(tài)為(si, n，si, n 1， si, n 2，si, n k)，盡管每個狀態(tài)可能的取值仍然只是M個，但這時的狀態(tài)數(shù)為從M個可能的取

17、值中每次取出k個進行允許重復元素的全排列，故 S = M k (3.9) 而其轉移概率的總數(shù)目為 T = M k +1 (3.10),3.1 離散信源的分類及其描述,3.1.3馬爾可夫過程和馬爾可夫鏈,26,馬爾可夫鏈對那些在每次狀態(tài)轉移中發(fā)出消息的信源是一種很好的描述，這種信源被稱為離散馬爾可夫信源。 可以將馬爾可夫鏈狀態(tài)及其狀態(tài)轉移的情況用線圖的方法表示出來，這種含有狀態(tài)和狀態(tài)轉移的圖又稱為香農線圖。,3.1 離散信源的分類及其描述,3.1.3馬爾可夫過程和馬爾可夫鏈,27,例3.1 一個二進制二階馬爾可夫信源X，其信源符號集為0,1，條件概率給定為P(0|00) = P(1|11) =

18、0； P(1|00) = P(0|11) = 0.2; P(0|01) = P(0|10) = P(1|01) = P(1|10) = 0.5。試畫出其香農線圖。 解 信源符號只有0, 1兩種，即M = 2。 二階馬爾可夫信源，k = 2，故信源的狀態(tài)數(shù)為 S = M k = 22 = 4，即S = s1, s2, s3, s4= 00, 01, 10, 11，轉移狀態(tài)概率總數(shù)目為T = M k+1 = 8。 該信源在00狀態(tài)和11狀態(tài)，分別以0.8的概率發(fā)0和1而仍維持在00和11狀態(tài)，分別0.2的概率發(fā)1和0而進入01和10狀態(tài)； 在01狀態(tài)和10狀態(tài)，分別以0.5的概率發(fā)0和1而進入10

19、、11、00和01狀態(tài)。,3.1 離散信源的分類及其描述,3.1.3馬爾可夫過程和馬爾可夫鏈,28,圖3.1給出了該信源的兩種香農線圖。,3.1 離散信源的分類及其描述,3.1.3馬爾可夫過程和馬爾可夫鏈,圖3.1例3.1的兩種香農線圖,29,發(fā)出單符號消息離散無記憶信源的熵 發(fā)出符號序列消息離散無記憶信源的熵 發(fā)出符號序列消息離散有記憶信源的熵 發(fā)出符號序列消息的馬爾可夫信源的熵,3.2 離散信源的熵,30,定義3.5 若信源發(fā)出N個不同符號x1, x2, , xi, , xN ，分別代表N種不同的消息，各個符號的概率分別為P1, P2, , Pi, , PN且相互統(tǒng)計獨立，則稱這種信源為單

20、符號消息離散無記憶信源。 單符號消息離散無記憶信源中某個符號xi的出現(xiàn)給出的自信息量為I(xi)，則其信息熵H(X) ：,3.2.1發(fā)出單符號消息離散無記憶信源的熵,3.2 離散信源的熵,（3.11）,31,定義3.6 若信源發(fā)出的消息是由K個離散符號構成的符號序列，且各消息相互統(tǒng)計獨立，則稱此信源為發(fā)出符號序列消息離散無記憶信源。 發(fā)出符號序列消息離散無記憶信源的典型例子 ASCII 碼可以看成是由8個二進制符號構成的符號序列； 中文電報碼是由4個十進制符號構成的符號序列，而每個十進制符號又由5個二進制符號構成； 通信系統(tǒng)中的QPSK，根據(jù)2個二進制符號00，01，10，11進行相位調制等。

21、,3.2 離散信源的熵,3.2.2發(fā)出符號序列消息離散無記憶信源的熵,32,定義3.7 若單符號離散無記憶信源的信源空間為X P，對其進行K重擴展得到符號序列X=X1 X2 Xk，則稱擴展后的信源為離散無記憶信源X P的K重擴展信源，K重擴展得到符號序列記為XK。 如果擴展后的K重符號序列彼此統(tǒng)計獨立，則定義3.7與定義3.6等價，擴展后的信源亦是發(fā)出符號序列消息離散無記憶信源。 由于信源發(fā)出的符號序列彼此統(tǒng)計獨立，故發(fā)出符號序列消息離散無記憶信源的熵為 H(XK) = K H(X) =(3.12),3.2 離散信源的熵,3.2.2發(fā)出符號序列消息離散無記憶信源的熵,33,例3.2 設由一離散

22、無記憶信源 X： a1, a2, a3 P(X)：1/2, 1/4, 1/4 構成二重擴展信源X2，求該擴展信源的H(X2)。 解 二重擴展符號序列是aiaj (i, j = 1, 2,3 )，由式(3.12)，,3.2.2發(fā)出符號序列消息離散無記憶信源的熵,3.2 離散信源的熵,因為ai，aj統(tǒng)計獨立，故P(aiaj) = P(ai)P(aj)。略去計算過 程，得H(X2)=3 比特/符號序列 而擴展前原始信源的熵為,且有H(X2) = 2H(X)。,34,定義3.8 若信源發(fā)出的消息是由K個離散符號構成的符號序列，且各個消息相互統(tǒng)計相關，則稱這種信源為發(fā)出符號序列消息離散有記憶信源。 信源

23、消息間有記憶，也就是符號序列之間具有相關性，其關聯(lián)程度可以用轉移概率來描述。 下面通過一個二重擴展信源X2來看這種有記憶信源熵的情況。,3.2 離散信源的熵,3.2.3發(fā)出符號序列消息離散有記憶信源的熵,35,例3.3 已知某單符號離散信源的概率空間為 該信源發(fā)出的消息均為二重符號序列(ai，aj)，(i, j = 1, 2, 3)，兩個符號的關聯(lián)性用條件概率P(ai|aj)表示，如表3.2所示，求H(X2)。,3.2 離散信源的熵,3.2.3發(fā)出符號序列消息離散有記憶信源的熵,36,解 由例3.2，有 由P(aiaj) = P(ai )P(aj|ai)，可求出9個聯(lián)合概率 P(a1a1)=

24、P(a1) P(a1|a1)=(11/36)(9/11)=1/4 P(a1a2)= P(a1) P(a2|a1)=(11/36)(2/11)=1/18 P(a3a3)= P(a3) P(a3|a3)=(1/4)(7/9)=7/36 略去計算過程，得H(X2)=2.412 比特/符號序列,3.2 離散信源的熵,3.2.3發(fā)出符號序列消息離散有記憶信源的熵,37,也可由原始信源熵和條件熵求擴展后的熵，有 H(X)+ H(X2|X1) = 2.412比特/符號序列 可見 H(X2) =H(X)+H(X2|X1) H(X) H(X2|X1) H(X2)2H(X),3.2 離散信源的熵,3.2.3發(fā)出符

25、號序列消息離散有記憶信源的熵,38,上述結論說明符號間的關聯(lián)性使信源輸出的信息量減少 根據(jù)2.4.1討論的熵的鏈接準則 對于2重擴展信源，有H(X 2) =H(X)+H(X|X) 對于K重擴展信源，有 (3.13) 且 H(XK) KH(X)(3.14) 對比2.4.1和2.4.3中討論的熵的鏈接準則和熵的界，K重擴展信源是多維隨機變量的一種特例，故有時也稱式(3.13)為熵的鏈接公式。,3.2 離散信源的熵,3.2.3發(fā)出符號序列消息離散有記憶信源的熵,39,馬爾可夫信源在發(fā)生狀態(tài)轉移時發(fā)出消息。 設當前狀態(tài)為Ei，下一狀態(tài)Ej，則其轉移過程可表示為 假設在這個轉移中可能發(fā)出L個符號，則有L

26、個轉移概率P1(Ej|Ei)，P2(Ej|Ei) ，PL (Ej|Ei) 。 因此從狀態(tài)Ei轉移到狀態(tài)Ej的總的轉移概率為,3.2 離散信源的熵,3.2.4發(fā)出符號序列消息的馬爾可夫信源的熵,40,設發(fā)一個符號有J種轉移，則信源由Ei狀態(tài)發(fā)出一個符號的熵為 (3.16) 再假設當前狀態(tài)共有I 種可能，則有 (3.17),可見，馬爾可夫信源的熵為條件熵。,3.2 離散信源的熵,3.2.4發(fā)出符號序列消息的馬爾可夫信源的熵,41,將式(2.9)重寫如下： 可見，馬爾可夫信源的熵是一般條件熵的一個特例。 雖然馬爾可夫信源發(fā)出的是符號序列消息，但上面推出的熵，是平均每發(fā)出一個符號所給出的信息量，因此其

27、量綱仍為比特/符號，故和一般的條件熵在表達上完全相同。,3.2 離散信源的熵,3.2.4發(fā)出符號序列消息的馬爾可夫信源的熵,42,3.2 離散信源的熵,3.2.5各種離散信源的時間熵,應用中通常習慣于看單位時間里發(fā)出的平均信息量，由此得出時間熵的概念。 時間熵就是用單位時間來表示的熵 通常用Ht表示， 單位時間的主量綱用秒（s）表示，因此Ht的主量綱為比特每秒（b/s或bps） 也常用kb/s、Mb/s、Gb/s、Tb/s（或kbps、Mbps、Gbps、Tbps）等，分別表示千比特每秒、兆比特每秒、吉比特每秒。,43,1. 發(fā)出單個符號消息的離散無記憶信源的時間熵 首先定義符號消息的平均長度

28、 定義3.9 若信源為具有N個單個符號消息的離散信源，第i個符號消息占有的時間為bi秒，對應的概率為Pi，i1，2，N，則稱bi的統(tǒng)計平均值為該信源符號消息的平均時間長度或平均長度，用 表示，主量綱為秒/符號。即,3.2 離散信源的熵,3.2.5各種離散信源的時間熵,秒/符號(3.18),44,對發(fā)出單個符號消息的離散無記憶信源， 若其信源熵為H(X)，則其時間熵為,3.2 離散信源的熵,3.2.5各種離散信源的時間熵,若信源每秒平均發(fā)n個符號， 即 符號/秒 則 Ht = nH(X) b/s(3.20),b/s(3.19),45,發(fā)出符號序列消息的無記憶信源的時間熵 設發(fā)出符號序列消息的無記

29、憶信源是單個符號消息的離散無記憶信源的K重擴展，K重符號序列消息的平均長度用 表示，則有,3.2 離散信源的熵,3.2.5各種離散信源的時間熵,由于信源無記憶，故有,信源的時間熵為,46,其數(shù)值與發(fā)出單個符號消息的離散無記憶信源相同，但若該信源每秒平均發(fā)出n個K重符號序列消息，則有,3.2 離散信源的熵,3.2.5各種離散信源的時間熵,因此 Ht = nKH(X) b/s (3.24) 與式(3.20)比較，這種情況的時間熵比單個符號消息離散無記憶信源時大了K倍，這是由于n個K重符號序列消息的緣故。,符號序列/秒(3.23),47,3. 發(fā)出符號序列消息的有記憶信源的時間熵 消息之間的關聯(lián)性體

30、現(xiàn)在信源熵中而不體現(xiàn)在平均長度中 若其信源熵為H(XK)，符號序列消息的平均長度為 ，則其時間熵依然應該是,3.2 離散信源的熵,3.2.5各種離散信源的時間熵,由于信源有記憶:,這時的時間熵同樣不會大于無記憶情況。,b/s (3.25),48,當然，可以用熵的鏈接公式(3.13)來變換H(XK )的形式，而平均長度仍可用式(3.18)來求。 這時，若該信源也是每秒平均發(fā)出n個K重符號序列消息，即 符號序列/秒，則其時間熵又可表示為 Ht = n H(XK ) b/s(3.26),3.2 離散信源的熵,3.2.5各種離散信源的時間熵,49,發(fā)出符號序列消息的馬爾可夫信源的時間熵 發(fā)出符號序列消

31、息的馬爾可夫信源的時間熵仍可用 來求。其信源熵H(X)已如式(3.17)所示。 下面討論信源發(fā)出所有符號的平均長度 。 假設從狀態(tài)Ei轉移到狀態(tài)Ej時，信源發(fā)出符號為 ，其長度為 ，發(fā)出該符號的概率為 Pl (j/i) ，Ei狀態(tài)的概率為P(i)，其余假設同前 從狀態(tài)Ei到狀態(tài)E j狀態(tài)轉移圖如圖3.2所示，則其平均長度為,3.2 離散信源的熵,3.2.5各種離散信源的時間熵,秒/符號 (3.26),50,圖3.2 馬爾可夫信源狀態(tài)Ei到狀態(tài)E j的狀態(tài)轉移圖,3.2 離散信源的熵,3.2.5各種離散信源的時間熵,51,所以 b/s (3.27),3.2 離散信源的熵,3.2.5各種離散信源的

32、時間熵,52,討論信源的最主要目的是為了得到高效率的信源編碼。 衡量信源編碼效率的尺度是什么呢？ 或者說能夠使信源編碼提高效率的根本原因是什么呢？ 本節(jié)討論的信源冗余度將回答這些問題。,3.3 信源的冗余度,53,定理3.1 設信源X中包含M個不同符號，其信源熵為H(X)，有 H(X) lb M(3.28) 當且僅當X中各個符號的概率全相等時，上式取等號，此時得到最大熵 H(X) max = lbM (3.29) 這一定理的證明，需要引用如下關系： ln 1 ( 0) (3.30) 當且僅當 = 1時，上式取等號。,3.3.1最大信源熵,3.3 信源的冗余度,54,證明 H(X) lbM =

33、= (3.31) 令 = 1/MP(x)，因為ln 1，( 0)，將其代入式(3.31)并利用換底公式，有 即 H(X) lbM 當且僅當 = 1/MP(x) = 1，即P(x) =1/M時等號成立。 證畢。,H(X) lbM ,3.3 信源的冗余度,3.3.1最大信源熵,55,定理3.1說明: 當一個信源中所有的符號消息為等概時，該信源的熵最大。 上一章式(2.29)和式(2.36)已分別對二維和n維隨機變量的情況，證明了其共熵不大于它們各自的熵之和。 這里從最大熵的角度給出共熵和K重擴展信源最大熵的兩個定理。,3.3 信源的冗余度,3.3.1最大信源熵,56,定理3.2 兩個集合X, Y的

34、共熵H(XY)與這兩個集合的信源熵H(X), H(Y)之間存在關系 H(XY) H(X) + H(Y) 當且僅當兩個集合相互獨立時，上式取等號，此時得最大熵 H(XY)max = H(X) + H(Y)(3.32) 其證明見對式(2.29)的證明。 定理3.2說明，當兩個集合之間相互獨立時，它們的共熵最大。,3.3 信源的冗余度,3.3.1最大信源熵,57,定理3.3 對于初始信源X經過K重擴展的信源，若初始信源熵為H(X)，擴展后的信源熵為H(XK )，有 H(XK ) KH(X) (3.33) 當且僅當K重符號序列消息的各個符號之間相互獨立時，上式取等號，此時得最大熵，為 H(XK )ma

35、x = KH(X) (3.34) 其證明同定理2.1的證明。 定理3.3說明，當K重擴展后信源的符號之間相互獨立時，其信源熵最大。,3.3 信源的冗余度,3.3.1最大信源熵,58,冗余度又稱為多余度，是編碼理論中的一個重要的概念。 在信源編碼中，人們總是在尋找壓縮信源冗余度的方法來提高傳輸?shù)挠行裕?在信道編碼中，人們又總是采取注入冗余度的方法來提高傳輸?shù)目煽啃浴?信源中存在著冗余度，冗余度可以用信源的熵值來表征，為此有如下的定義。,3.3 信源的冗余度,3.3.2信源的冗余度,59,定義3.10 設信源實際的熵為H，該種信源可能的最大熵為Hmax，則 為信源的冗余度。 信源的冗余度實際上就

36、是信源在發(fā)出消息時無用信息量所占的百分比。,3.3 信源的冗余度,3.3.2信源的冗余度,60,舉例 英文26個字母加空格共27個符號，假如完全等概，則得英文的最大熵為 Hmax = lb27 4.755 比特/字母 而根據(jù)表3.1，可計算這27個符號的實際熵為 H = 0.1817lb20.1817 0.1073lb20.1073 0.00063lb20.00063 1 比特/字母 因此，該種信源的冗余度為 (4.7551)/4.755 79.0 %,3.3 信源的冗余度,3.3.2信源的冗余度,61,不同的統(tǒng)計可以得到不同的實際熵。 英文的冗余度是很大的，因為語言本身有很多固定的約束，它對

37、于信息傳輸是“多余” 。因此從信息傳輸?shù)慕嵌炔虐阉x為“冗余” 。 中文冗余度的統(tǒng)計比英文要復雜得多，中文的實際熵也比英文要難統(tǒng)計得多。 中文的最大熵是一個變量； 每一個單字都具有明確的意義，再由字組詞，字詞之間的相關性千變萬化。 以辭海（上海，1989年版）收集的大約15000漢字為信源符號消息，則中文的最大信源熵為Hmax lb15000 13.9 比特/漢字,3.3 信源的冗余度,3.3.2信源的冗余度,62,尚未找到給出中文實際熵和統(tǒng)計方法的文獻，但根據(jù)目前廣泛使用的文本壓縮軟件的壓縮率來看，中文的實際熵應該不會大于5比特/漢字，估計中文的冗余度大約也會在80%左右。,3.3 信源的

38、冗余度,3.3.2信源的冗余度,63,舉例說明 圖3.3給出了目前常用的幾種語音編碼的速率，假設圖中三種編碼方法PCM、ADPCM和Vocoder代表三個信源，分別稱為信源A、B、C，其輸出的碼流均為二進制數(shù)字信號，碼速率如圖所示，若各種編碼均沒有造成語音信息的損失，而信源C輸出的碼流已基本達到1、0等概和完全隨機，試求圖中三個信源的冗余度。,圖3.3 語音編碼的幾種速率,3.3 信源的冗余度,3.3.2信源的冗余度,64,圖中給出的碼速率就是各信源的時間熵，因此使用式(3.35)時均用時間熵。 可認為三個信源的實際熵都是8 kb/s，而三個信源的最大熵就是它們輸出碼序列的速率，即64 kb/

39、s, 32 kb/s, 8 kb/s 信源A冗余度為RA = (64 8 )/64 = 87.5% 信源B冗余度為RB = (32 8)/32 = 75% 信源C冗余度為RC = (8 8)/8 = 0 即信源C沒有冗余，這時由于假設信源C的輸出已是該信源最大熵。 目前的語音編碼器還做不到本例的假設條件，例如信源C中仍有冗余度，因此各信源實際的冗余度可能更大。 低速率的編碼通常會帶來語音信息的損失，且速率越低損失越大，但這對于理解語音信息的冗余度沒有影響。,3.3 信源的冗余度,3.3.2信源的冗余度,65,初始信源的冗余度通常是很大的，這為信源的壓縮編碼提供了可能 壓縮編碼的目標就是尋找某種

40、編碼方法，使得編碼后消息序列中的冗余度趨近于0 如果將這種編碼包含在信源中，也可以說是尋找某種能夠使信源冗余度趨近于0的編碼方法 冗余度成為衡量信源編碼效率的一個物理量，冗余度越低，編碼效率就越高。,3.3 信源的冗余度,3.3.2信源的冗余度,66,1.請給出平均互信息量的定義及性質，說說疑義度、散布度的定義及含義。 張程 2.請給出熵的鏈接準則和信息鏈接準則。證穎 3.請給出 n維隨機變量的共熵與它們各自的熵之間的關系。韓計海 4. 請簡述數(shù)據(jù)處理定理和數(shù)據(jù)處理不等式。 郭衍 5.請給出幾種信源的分類。 縱邦勝 6. 請說說用什么方法來描述自然語信源的關聯(lián)性。繩紅磊 7. 請給出發(fā)出符號序

41、列消息離散有記憶信源的熵 榮俊興 8. 請給出發(fā)出符號序列消息的馬爾可夫信源的熵 王巖 9. 請說說時間熵的定義、量綱 曹喜 10. 請舉例說明信源冗余度的定義。 唐岱,第三次課（2009年3月8日） 上次課的回顧,67,3.4 信源符號序列分組定理,設無記憶離散信源的信源空間為 X： x1, x2, , xi, , xN P(X)： P1, P2, ,Pi, , PN 它的熵為,假如將它進行K重擴展而得到K重符號序列，用矢量表示為 (3.36) 則這樣的符號序列有N K個。,68,3.4 信源符號序列分組定理,當K的值很大時，根據(jù)大數(shù)定律，這個序列會以很高的概率出現(xiàn)以下情況：符號x1約重復出

42、現(xiàn)KP1次，符號x2約重復出現(xiàn)KP2次，符號xN約重復出現(xiàn)KPN次。 這意味著當K足夠大時，將會以趨向于1的概率出現(xiàn)以下情況：擴展后的很多序列都具有相同的組成，因此也具有相同的概率。也就是說，當K足夠大時，擴展后有相當多的符號序列是等概的。 可以將具有上述結構的序列稱為典型序列，而將其余的序列稱為非典型序列，如果典型序列的概率之和很大而非典型序列的概率之和很小，則僅用典型序列來代表擴展信源在很多場合是可行的。,69,既然所有的非典型序列的概率之和很小，對信源輸出來說，忽略它們而引入的誤差可以小于任何給定的值 將這一特性應用于信源的壓縮編碼中，這正是數(shù)據(jù)壓縮的本質 信源符號序列分組定理說明了上述

43、的分組是存在的，而且可以估算其典型序列的數(shù)目。 下面給出信源符號序列分組定理及其證明。,3.4 信源符號序列分組定理,70,(3.37),3.4 信源符號序列分組定理,71,證明 設擴展后符號序列中取符號xi值的次數(shù)為ni ( i =1, 2, , N)，由于信源是無記憶的，故有 (3.38) 兩邊取對數(shù)，有 (3.39) 由于 所以 (3.40),3.4 信源符號序列分組定理,72,ni /K=P(xi)+ i (3.41) 令 (3.42),3.4 信源符號序列分組定理,將式(3.41)代入(3.40)，有,(3.43),在NK個可能的符號序列中，對于任意的 0，將有一部分符號序列的 ma

44、x滿足,(3.44),73,稱滿足式(3.45)條件的符號序列稱為典型序列（Typical Set），將該種典型序列的集合記作G1，而稱不滿足式(3.45)條件的符號序列稱為非典型序列，將該種非典型序列的集合記作G2。 下面來估算落入G1 和G2中的概率。 對于集合G2，其中的符號序列不滿足式(3.44)，即至少存在一個值l，使,3.4 信源符號序列分組定理,則這些符號序列即能滿足,(3.46),74,如果把發(fā)生式(3.46)的事件記為El，則對于G2中所有序列，有 (3.47) 但根據(jù)大數(shù)定律，當K足夠大時，對于任意l 值總可以有一個整數(shù)K0，使當K K0時，對任意的 0，有 (3.48)

45、即nl /K依概率收斂到P(xl)。這樣，就得到G2組中符號序列的概率之和小于，即,3.4 信源符號序列分組定理,(3.49),75,所以G1中符號序列概率之和大于1，此結論即為式(3.37)。由于、都是任意給定的，故亦可以取 = ，定理依然成立。 證畢。 定理3.4被稱為信源符號序列分組定理，也有的文獻稱之為漸進均分特性。,3.4 信源符號序列分組定理,76,下面估計G1集合中典型符號序列的數(shù)目。 根據(jù)式(3.37)，有 (3.50) 式中的對數(shù)以2為底，則x在G1集合中的概率P(x)的范圍為 (3.51) 設G1內典型符號序列的數(shù)目為NG, 則 (3.52),3.4 信源符號序列分組定理,

46、因此,(3.53),(3.54),77,任意一個符號序列不在G1內必在G2內，因此 (3.55) 而 (3.56),3.4 信源符號序列分組定理,由式(3.51)知,(3.57),所以,由于、 很小，故有,(3.58),(3.59),(3.60),78,信源符號序列分組定理說明，對于K重擴展信源，只考慮典型符號序列對信源特性帶來的損失可以低到可被忽略的程度，這給出了信源壓縮編碼的理論依據(jù)。,3.4 信源符號序列分組定理,79,從描述信源消息隨機過程的平穩(wěn)性角度，信源可以分為平穩(wěn)信源和非平穩(wěn)信源 很多實際的信源在較短的一段時間內都可以用平穩(wěn)信源來描述 研究平穩(wěn)信源是研究非平穩(wěn)信源的基礎，故本節(jié)討論平穩(wěn)離散信源及其性質,3.5 平穩(wěn)離散信源及其性質,80,定義3.10 若一個離散信源發(fā)出的符號序列 ()，其出現(xiàn)概率與另一符號序列 ()的出現(xiàn)概率相等，那么這個離散信源稱為平穩(wěn)離散信源。 定義3.10說明，對于平穩(wěn)離散信源，若改變符號序列的起始位置，其概率的描述不變。 由該定義還可以看出，平穩(wěn)離散信源的定義對應的隨機過程是嚴平穩(wěn)的。 下面通過討論平穩(wěn)離散信源的熵來研究它的一些性質。,3.5 平穩(wěn)離散信源及其性質,81,（1）平穩(wěn)離散信源的極限熵 K重有記憶離散信源每發(fā)一個符號提供的平均信息量。 由于信源不斷發(fā)出符號，在時間域上總是一個近似無限長的符號序列； 又由于信源有記