信息論與編碼理論第3章 離散信源

信息論與編碼理論

第3章離散信源3.1信源的數(shù)學(xué)模型信源是信息的發(fā)源地。信息十分抽象，要通過消息（0-1序列、漢字、字母、圖像等）來研究信源。信源可以輸出多個符號，每個符號以一定的概率出現(xiàn)。因此可以用概率來描述信源。信源的數(shù)學(xué)模型X是信源能取的符號的集合；xi是信源符號；pi(p(xi))是信源符號出現(xiàn)的概率。二進(jìn)制信源：X={0,1}漢語：X={我,一,的,教,俄,…}英語：X={a,b,c,…,x,y,z}信源的例子數(shù)學(xué)模型則信源的輸出有可能是111011111011001110110011101110011010110010110011011100010011（23個0，37個1）110101100110010001111111000010001010011000011100001101001110（31個0，29個1）3.2信源的分類信源符號彼此之間的依存關(guān)系無記憶信源有記憶信源3.2.1無記憶信源無記憶信源：信源發(fā)出的一個個消息符號是相互獨立的。通俗來講：前面已經(jīng)出現(xiàn)的信源符號對后面將要出現(xiàn)哪個信源符號沒有影響例如：從一個袋子里摸球，50個紅的、50個白的，每次摸完之后放回則無論已經(jīng)摸過的球是紅的還是白的，再摸一次球，紅白出現(xiàn)的概率都是1/2如何用概率的方法定義無記憶信源？已經(jīng)出現(xiàn)的符號對將要出現(xiàn)的符號的概率沒有影響：p(x|y)=p(x)更確切地，設(shè)X=x1x2…xM是信源發(fā)出的符號序列3.2.2有記憶信源有記憶信源：信源先后發(fā)出的消息符號之間彼此依存、互不獨立。例如：自然語言、數(shù)字圖像等。p(們)=0.01,p(碗)=0.01p(們|我)=0.05,p(碗|我)=0.001現(xiàn)實存在的信源多是有記憶信源有記憶信源分類有限記憶信源無限記憶信源我們、要、的、把、看、…碗、機(jī)、水、書、框、…有限記憶信源和無限記憶信源有限記憶信源：信源發(fā)出的消息符號只與前若干個符號的關(guān)系比較密切，與更前面符號的關(guān)系逐漸減弱，直至無關(guān)。p(xi|xi-1xi-2…xi-m)m叫做記憶長度無限記憶信源：信源發(fā)出的消息符號與前面出現(xiàn)的所有符號都有關(guān)系。p(xi|xi-1xi-2xi-3…)例3-5

判斷下面這兩個信源的記憶特性，無記憶還是有記憶。信源模型均為因此1無記憶，2有記憶信源序列12條件概率3.3離散無記憶信源

3.3.1定義及熵定義3-1

信源X符號集為(x1,x2,…,xn)，n為信源發(fā)出的消息符號的個數(shù)，每個符號發(fā)生的概率為p(xi),i=1,2,…,n，這些消息符號彼此互不相關(guān)，且有則稱X為離散無記憶信源。3.3.1信源的熵定義3-2

信源中某個消息符號的自信息量I(xi)=-logp(xi)定義3-3

信源的平均自信息量（信源熵）信源熵的單位信源符號（消息符號）的自信息量表示該符號帶有多少比特的信息量因此信源熵表示的是平均每個符號帶有多少比特的信息量所以定義信源熵的單位為：比特/符號信源輸出哪個符號是不確定的一旦輸出一個符號，便消除了這種不確定性即帶來了信息因此仍然用概率衡量信源包含的信息量的大小信源熵的例子例3-5

二元信源

它的熵為：二元信源的信息熵H(X)是概率p的函數(shù)，通常用H(p)表示。信源熵的例子例3-6

信源熵的例子例3-7請從信息論的角度說明，為什么玩撲克牌的時候需要先洗牌？假設(shè)不考慮大小王，且自己先摸對方后摸，摸到的第一張牌是A。洗牌均勻分布，則對方也摸到A的概率是3/51，摸到其他牌的概率各為4/51，熵不洗牌易出現(xiàn)幾張同樣大小的牌連續(xù)出現(xiàn)。假設(shè)對方也摸到A的概率上升為39/51，摸到其他牌的概率各為1/51，熵可以一個符號一個符號的來研究信源，但有時這樣不能滿足實際應(yīng)用的需要。漢語：更多地考察的是句子，而不是漢字。英語：更多地考察的是單詞，而不是字母。圖像：更多地考察的是整幅圖像，而不是單個像素。N次擴(kuò)展信源：集合中的每一個元素是一個N維隨機(jī)矢量二進(jìn)制信源：X={00,01,10,11},N=2漢語：X={我們在上課，張三睡著了，…},N=5英語：X={the,car,ear,she,you,…},N=33.3.2離散無記憶信源的擴(kuò)展信源3.3.2N次擴(kuò)展信源

無記憶二元信源的擴(kuò)展信源二次擴(kuò)展信源（N=2）qN=4=22，q=2，N=2例如：p(01)=p(0)p(1)=p(1-p)三次擴(kuò)展信源（N=3）qN=8=23，q=2，N=3例如：p(011)=p(0)p(1)p(1)=p(1-p)2N次擴(kuò)展信源的熵定理3-1

離散無記憶信源X的N次擴(kuò)展信源XN的熵等于信源X的熵的N倍，即H(XN)=NH(X)證明：擴(kuò)展信源熵的例子例3-9方法一方法二3.4馬爾可夫信源（有限記憶信源）

3.4.1馬爾可夫信源的定義定義3-5在信源X中，如果將要出現(xiàn)的符號僅與剛剛出現(xiàn)的m個符號有關(guān)，與更早出現(xiàn)的符號無關(guān)，則稱X為m階馬爾可夫信源，即例3-10信源X={0,1,2,3}，信源將要發(fā)出的符號是前面兩個符號的和對4的余數(shù)，即顯然這是一個2階馬爾可夫信源，因為將要出現(xiàn)的符號只與前面的兩個符號有關(guān)。每一個將要發(fā)出的符號只與前面的兩個符號相關(guān)，將這兩個符號連在一起，看做一個整體，我們把它叫做“狀態(tài)”?！盃顟B(tài)”是馬爾可夫信源中的一個重要概念，m階馬爾可夫信源的狀態(tài)由m個信源符號構(gòu)成。馬爾可夫信源中符號對符號序列的依賴關(guān)系就變?yōu)闋顟B(tài)對狀態(tài)的依賴關(guān)系，即3.4.2有限狀態(tài)馬爾可夫鏈定義3-6一個狀態(tài)序列：S1,S2,…,Sl,…，若滿足以下條件：有限性：可能的狀態(tài)數(shù)目J<∞，即只有有限個可能的狀態(tài)；馬氏性：系統(tǒng)將要達(dá)到的狀態(tài)，只與當(dāng)前的狀態(tài)有關(guān)，與更早的狀態(tài)無關(guān)，即則稱此隨機(jī)狀態(tài)序列為有限狀態(tài)馬爾可夫鏈。系統(tǒng)將要達(dá)到的狀態(tài)，僅與當(dāng)前剛剛輸出的狀態(tài)有關(guān)，與更前面的狀態(tài)（過去的狀態(tài)）無關(guān)。這種特性稱為馬爾可夫特性。馬爾可夫鏈并不是信源，它體現(xiàn)的是一種“一環(huán)扣一環(huán)”的性質(zhì)。描述馬爾可夫鏈的數(shù)學(xué)工具狀態(tài)轉(zhuǎn)移矩陣pkl表示由狀態(tài)Sk轉(zhuǎn)移為狀態(tài)Sl的概率狀態(tài)轉(zhuǎn)移圖狀態(tài)轉(zhuǎn)移矩陣和狀態(tài)轉(zhuǎn)移圖之間有一一對應(yīng)的關(guān)系。例3-11一個系統(tǒng)有2個狀態(tài){S1,S2}，狀態(tài)轉(zhuǎn)移矩陣為則狀態(tài)轉(zhuǎn)移圖為3.4.3馬爾可夫信源的馬爾可夫鏈性質(zhì)m階馬爾可夫信源中1個符號對m個符號的依賴關(guān)系轉(zhuǎn)換為狀態(tài)和狀態(tài)之間的“一環(huán)扣一環(huán)”的關(guān)系，因此馬爾可夫信源是具有馬爾可夫鏈性質(zhì)的信源由此可以給出馬爾可夫信源的另一個定義定義3-7

若信源輸出的符號和狀態(tài)滿足下列條件，則稱此信源為m階馬爾可夫信源某一時刻，將要出現(xiàn)的信源符號只與當(dāng)時信源所處的狀態(tài)有關(guān)，與以前的狀態(tài)無關(guān)，即信源的狀態(tài)只由當(dāng)前輸出符號和前一時刻信源的狀態(tài)唯一確定，即3.4.4馬爾可夫信源的熵有的馬爾可夫信源輸出的狀態(tài)序列與系統(tǒng)的初始狀態(tài)有關(guān)例3-13信源X={0,1,2,3}，信源將要發(fā)出的符號是前面兩個符號的和對4的余數(shù)初始狀態(tài)狀態(tài)序列狀態(tài)分布符號序列信源分布信源熵（比特/符號）00000000000H(X)=002022220022022022…H(X)=0.918310100111122331101123101123…H(X)=1.792530300333322113303321303321…H(X)=1.7925無法給出信源熵的一個確定的值。因此本課程中，我們只研究狀態(tài)序列不受初始狀態(tài)影響的情況。這種馬爾可夫信源叫做平穩(wěn)馬爾可夫信源。平穩(wěn)馬爾可夫信源的含義包括兩點：經(jīng)過足夠長的時間之后，信源的nm個狀態(tài)出現(xiàn)的概率逐漸穩(wěn)定下來，不再發(fā)生變化狀態(tài)的穩(wěn)定分布與初始狀態(tài)無關(guān)，即無論信源一開始處在什么狀態(tài)，最終都將達(dá)到同樣的穩(wěn)定分布。平穩(wěn)馬爾可夫信源的判定定理3-2遍歷的馬爾可夫信源是平穩(wěn)馬爾可夫信源。如何判斷是否遍歷？狀態(tài)轉(zhuǎn)移圖：各個狀態(tài)是互相可達(dá)的狀態(tài)轉(zhuǎn)移矩陣：存在一個正整數(shù)N，使轉(zhuǎn)移矩陣PN中的所有元素均大于0。一步轉(zhuǎn)移矩陣和多步轉(zhuǎn)移矩陣轉(zhuǎn)移矩陣P表示一個狀態(tài)經(jīng)過1步轉(zhuǎn)移到另外一個狀態(tài)的矩陣，即轉(zhuǎn)移1次的概率，因此叫做一步轉(zhuǎn)移矩陣。多步轉(zhuǎn)移矩陣P(r)表示一個狀態(tài)經(jīng)過多次轉(zhuǎn)移，轉(zhuǎn)移到另外一個狀態(tài)的概率定理3-3設(shè)P為馬爾可夫信源的一步狀態(tài)轉(zhuǎn)移矩陣，該信源為平穩(wěn)馬爾可夫信源的充要條件是存在一個正整數(shù)N，使矩陣PN中的所有元素均大于0。例3-14設(shè)有一個二進(jìn)制二階馬爾可夫信源，其信源符號集為{0,1}，條件概率為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試判斷這個信源是否為平穩(wěn)馬爾可夫信源。解：3.4.4.2平穩(wěn)馬爾可夫信源的熵m階平穩(wěn)馬爾可夫信源的熵是在知道了已經(jīng)出現(xiàn)的m個符號的條件下，信源符號帶有的信息量的平均值，換句話說，平穩(wěn)馬爾可夫信源的熵實際上是一個條件熵如果則有：SP=S解方程可以求得各個p(Sj)求馬爾可夫信源熵的步驟判斷是否為平穩(wěn)馬爾可夫信源。對平穩(wěn)馬爾可夫信源，求出狀態(tài)的平穩(wěn)分布。根據(jù)公式（3-16）求得馬爾可夫信源的熵。馬爾可夫信源熵的例子例3-15接例3-14，求該平穩(wěn)馬爾可夫信源的熵。解：例3-14中已經(jīng)求出該信源為平穩(wěn)信源。設(shè)S=[p(00)p(01)p(10)p(11)]，有解得因此信源熵例3-16“投入-產(chǎn)出”模型：假設(shè)一個經(jīng)濟(jì)體系由煤炭、電力和鋼鐵三個部門組成。這是一個馬爾可夫鏈，狀態(tài)轉(zhuǎn)移矩陣P2中每一個元素均大于0，這是一個平穩(wěn)馬爾可夫鏈。產(chǎn)出部門采購部門煤炭電力鋼鐵煤炭0.00.60.4電力0.40.10.5鋼鐵0.60.20.2PC、PE、PS分別表示煤炭、電力和鋼鐵部門的平衡價格，

，則SP=S，解得如果鋼鐵部門的平衡價格是1億，則煤炭部門是9400萬，電力部門是8500萬。如果煤炭部門生產(chǎn)1.88萬噸煤，則每噸的價格是5000元；如果電力部門生產(chǎn)1.7億度電，則每度電的價格是0.5元。這就是國民生產(chǎn)中，確定每種商品單價的一個基本原則。極限熵對無限記憶信源，記憶長度無限，此時的熵叫做極限熵極限熵又叫做實際熵即當(dāng)前符號實際上能夠帶給我們的信息量。3.5離散平穩(wěn)信源如果信源輸出各個符號的概率與時間無關(guān)，即則稱此信源為一維平穩(wěn)信源。如果信源輸出長度為N的符號序列的概率與時間無關(guān)，即則稱此信源為N維平穩(wěn)信源。平穩(wěn)信源的熵平穩(wěn)信源輸出的長度為N的符號序列的聯(lián)合熵為長度為N的信源符號序列中平均每個符號所攜帶的信息量為平均符號熵，即設(shè)信源符號序列之間的記憶長度為N，若已知前面N?1個符號，則第N個符號所攜帶的平均信息量為條件熵，即性質(zhì)1.性質(zhì)1的含義是：我們知道的條件越多，越容易判斷事件的結(jié)果2.3.4.性質(zhì)2、3、4說明，當(dāng)平穩(wěn)信源輸出的符號序列長度達(dá)到無限大時，平均符號熵HN(X)和條件熵H(XN|X1X2…XN?1)都非遞增地收斂于平穩(wěn)信源的極限熵。3.6信源的相關(guān)性和剩余度

相關(guān)性H(XN|X1,…,XN-1)≤H(XN-1|X1,…,XN-2)≤H(XN-2|X1,…,XN-3)≤…≤H(X2|X1)≤H(X1)

輸出符號等概率分布時，