信息論-復(fù)習(xí)資料(傅祖蕓版本).ppt

1、信息論與編碼,計(jì)算器,2,簡(jiǎn) 介,是一門(mén)應(yīng)用概率論、隨機(jī)過(guò)程、數(shù)理統(tǒng)計(jì)和近代代數(shù)的方法，來(lái)研究信息傳輸、提取和處理中一般規(guī)律的學(xué)科。,奠基人：美國(guó)數(shù)學(xué)家香農(nóng)（C.E.Shannon） 1948年“通信的數(shù)學(xué)理論”,3,簡(jiǎn) 介,信息論的基本問(wèn)題信息的度量 無(wú)失真信源編碼定理香農(nóng)第一定理 信道編碼定理香農(nóng)第二定理 信源編碼、信道編碼,緒 論,第1章,5,1.1 信息的概念,6,情報(bào)：是人們對(duì)于某個(gè)特定對(duì)象所見(jiàn)、所聞、所理解而產(chǎn)生的知識(shí)。 知識(shí)：一種具有普遍和概括性質(zhì)的高層次的信息 ，以實(shí)踐為基礎(chǔ)，通過(guò)抽象思維，對(duì)客觀事物規(guī)律性的概括。 消息：用文字、符號(hào)、語(yǔ)音、圖像等能夠被人們感覺(jué)器官所感知的形式

2、，把客觀物質(zhì)運(yùn)動(dòng)和主觀思維活動(dòng)的狀態(tài)表達(dá)出來(lái)。,幾個(gè)常見(jiàn)概念,7,香農(nóng)信息的度量,（1）樣本空間 某事物各種可能出現(xiàn)的不同狀態(tài)。 （2）概率測(cè)度 對(duì)每一個(gè)可能選擇的消息指定一個(gè)概率。 （3）概率空間 先驗(yàn)概率p(xi)： 選擇符號(hào)xi作為消息的概率。,樣本空間 概率測(cè)度,8,例：氣象預(yù)報(bào) 甲 乙,“甲地晴”比“乙地晴”的不確定性小。 某一事物狀態(tài)出現(xiàn)的概率越小，其不確定性越大。某一事物狀態(tài)出現(xiàn)的概率接近于1,即預(yù)料中肯定會(huì)出現(xiàn)的事件，那它的不確定性就接近于零。,9,對(duì)xi的不確定性可表示為先驗(yàn)概率p(xi)的倒數(shù)的某一函數(shù)。 （4）自信息 （5）互信息 先驗(yàn)的不確定性減去尚存的不確定性。 后驗(yàn)

3、概率p(ai | bj)：接收端收到消息bj后而發(fā)送端發(fā)的是ai的概率。,10,信息的特征,信息是物質(zhì)存在的普遍屬性，信息和能量、物質(zhì)規(guī)定了事物的功能和性能； 接收者在收到信息之前，對(duì)它的內(nèi)容是不知道的，所以，信息是新知識(shí)、新內(nèi)容；它使認(rèn)識(shí)主體對(duì)某一事物的未知性或不確定性減少的有用知識(shí)； 信息的存在具有普遍性、無(wú)限性、動(dòng)態(tài)性、時(shí)效性和相對(duì)獨(dú)立性； 信息可以產(chǎn)生，也可以消失，同時(shí)信息可以被傳遞、轉(zhuǎn)換、擴(kuò)散、復(fù)制、貯存、分割，具有可共享性； 信息是可以量度的，信息量有多少的差別。,11,1.2 信息論研究的對(duì)象、目的和內(nèi)容,12,研究對(duì)象：通信系統(tǒng)模型,加密密鑰,解密密鑰,13,信源：發(fā)送消息的源

4、 離散信源 模擬信源 信源是信息論的主要研究對(duì)象之一.我們不探討信源的內(nèi)部結(jié)構(gòu)和機(jī)理，而關(guān)注信源的輸出。重點(diǎn)討論其描述方法及性質(zhì)。 信宿：信息歸宿之意，亦即收信者或用戶，是信息傳送的終點(diǎn)或目的地。 信道：傳輸信息的物理媒介。,信源、信道、信宿,14,信源編碼器 通過(guò)信源編碼可以壓縮信源的冗余度,以提高通信系統(tǒng)傳輸消息的效率。 信源編碼器分為兩類 無(wú)失真信源編碼：適用于離散信源或數(shù)字信號(hào)； 限失真信源編碼：用于連續(xù)信源或模擬信號(hào),如語(yǔ)音、圖像等信號(hào)的數(shù)字處理。,信源編碼器與譯碼器,信源編碼器的主要指標(biāo) 是它的編碼效率。一般來(lái)說(shuō)，效率越高，編譯碼器的代價(jià)也將越大。 信源譯碼器 把信道譯碼器的輸出變

5、換成信宿所需的消息形式，相當(dāng)于信源編碼器的逆過(guò)程。,15,信道編碼器與譯碼器,信道編碼 主要作用是提高信息傳送的可靠性。 信道編碼器的作用 在信源編碼器輸出的代碼組上有目的地增加一些監(jiān)督碼元,使之具有檢錯(cuò)或糾錯(cuò)的能力。 信道編碼的主要方法 增大碼率或頻帶,即增大所需的信道容量。這恰與信源編碼相反。 信道譯碼器的作用 具有檢錯(cuò)或糾錯(cuò)的功能,它能將落在其檢錯(cuò)或糾錯(cuò)范圍內(nèi)的錯(cuò)傳碼元檢出或糾正,以提高傳輸消息的可靠性。,16,1.3 信息論的形成和發(fā)展,17,信息論是在長(zhǎng)期的通信工程實(shí)踐和理論研究的基礎(chǔ)上發(fā)展起來(lái)的。 簡(jiǎn) 史 現(xiàn)代信息論是從20世紀(jì)20年代奈奎斯特和哈特萊的工作開(kāi)始的： 1924年奈奎

6、斯特(Nyquist)的 “影響電報(bào)速率因素的確定” 。 1928年哈特萊(Hartley) 的“信息傳輸” 一文研究了通信系統(tǒng)傳輸信息的能力，并給出了信息度量方法。,信息論的形成,18,1946年柯切爾尼柯夫的學(xué)位論文“起伏噪聲下的潛在抗干擾理論”，根據(jù)最小錯(cuò)誤概率準(zhǔn)則和最小均方誤差準(zhǔn)則研究了離散和連續(xù)信道的最佳接收問(wèn)題。 1948年香農(nóng)的權(quán)威性長(zhǎng)文“通信的數(shù)學(xué)理論”，討論了信源和信道特性，1949年香農(nóng)“噪聲中的通信”，兩論文奠定了現(xiàn)代信息論的理論基礎(chǔ)。 此后，在基本理論和實(shí)際應(yīng)用方面，信息論都得到了巨大的發(fā)展。,第2章 離散信源及其信息測(cè)度,2.1 信源的數(shù)學(xué)模型及分類,2.2 離散信源

7、的信息熵,2.3 信息熵的基本性質(zhì),2.5 離散無(wú)記憶的擴(kuò)展信源,2.6 離散平穩(wěn)信源,2.7 馬爾可夫信源,2.8 信源剩余度與自然語(yǔ)言的熵,20,信源 產(chǎn)生消息或消息序列的源。消息攜帶信息，是信息的具體形式。 描述方法 通信過(guò)程中，信源發(fā)出何種消息是不確定的、是隨機(jī)的。 因此，信源可用隨機(jī)變量、隨機(jī)矢量或隨機(jī)過(guò)程（或樣本空間及其概率測(cè)度）來(lái)描述。 不同的信源根據(jù)其輸出消息的不同的隨機(jī)性質(zhì)進(jìn)行分類。,2.1 信源的數(shù)學(xué)模型及分類,21,1、隨機(jī)變量描述的信源（單符號(hào)）,特點(diǎn)：輸出單符號(hào)消息。符號(hào)集的取值A(chǔ):a1,a2,aq是有限的或可數(shù)的,可用離散型隨機(jī)變量X描述。 數(shù)學(xué)模型：設(shè)每個(gè)信源符號(hào)

8、ai出現(xiàn)的(先驗(yàn))概率p(ai) (i=1,2,q) 滿足：,概率空間能表征離散信源的統(tǒng)計(jì)特性，因此也稱概率空間為信源空間。,1）離散信源,22,1）平穩(wěn)信源,特點(diǎn): 信源輸出的消息由一符號(hào)序列所組成。 可用N維隨機(jī)矢量 X(X1,X2,XN)描述，且隨機(jī)矢量X的各維概率分布都與時(shí)間起點(diǎn)無(wú)關(guān) 。 離散平穩(wěn)信源：每個(gè)隨機(jī)變量Xi (i1,2,N)是取值離散的隨機(jī)變量。 連續(xù)平穩(wěn)信源：每個(gè)隨機(jī)變量Xi (i1,2,N)是取值連續(xù)的隨機(jī)變量。,2、隨機(jī)矢量描述的信源,23,2）離散無(wú)記憶平穩(wěn)信源,離散平穩(wěn)信源的特例，信源發(fā)出的符號(hào)都相互統(tǒng)計(jì)獨(dú)立，即各隨機(jī)變量Xi (i1,2,N)之間統(tǒng)計(jì)獨(dú)立。 性質(zhì)

9、： 獨(dú)立P(X)= P(X1, X2, ,XN)= P1(X1) P2(X2) PN(XN) 平穩(wěn)P1(Xi) = P2(Xi)= = PN(Xi) = P(Xi) （下標(biāo)1-N為時(shí)間標(biāo)志）,N維隨機(jī)矢量的一個(gè)取值，i(ai1 ai2aiN),P(aik)是符號(hào)集A的一維概率分布,若各隨機(jī)變量Xi取值同樣符號(hào)集A:a1,a2,aq，則,24,信源X的各輸出Xi間統(tǒng)計(jì)獨(dú)立、且取值同一符號(hào)集A。該信源 輸出的N維隨機(jī)矢量X為離散無(wú)記憶信源X的N次擴(kuò)展信源。 此擴(kuò)展信源取值為符號(hào)集i (ai1ai2aiN), 其中 (i1 , i2 ,iN =1,2 , ,q)， 其數(shù)學(xué)模型是X信源空間的N重空間：

10、,3）離散無(wú)記憶信源的N次擴(kuò)展信源,若X為離散無(wú)記憶信源：,25,4）有記憶信源,信源在不同時(shí)刻發(fā)出的符號(hào)之間是相互依賴的，即信源輸出的隨機(jī)序列X中，各隨機(jī)變量Xi之間相互依賴。 須使用隨機(jī)矢量的聯(lián)合概率分布和條件概率分布來(lái)說(shuō)明它們之間的關(guān)聯(lián)關(guān)系。 例：漢字組成的中文序列中，只有根據(jù)中文的語(yǔ)法、習(xí)慣用語(yǔ)、修辭制約和表達(dá)實(shí)際意義的制約所構(gòu)成的中文序列才是有意義的中文句子或文章。所以，在漢字序列中前后文字的出現(xiàn)是有依賴的，是彼此相關(guān)的。,26,5）m階馬爾可夫信源（非平穩(wěn)信源）,不同時(shí)刻發(fā)出的符號(hào)間的依賴關(guān)系,記憶信源的記憶長(zhǎng)度為m+1時(shí)，稱這種有記憶信源為m階馬爾可夫信源。 若上述條件概率與時(shí)間

11、起點(diǎn) i 無(wú)關(guān)，信源輸出的符號(hào)序列可看成為時(shí)齊馬爾可夫鏈，則此信源稱為時(shí)齊馬爾可夫信源。,27,2.2 離散信源的信息熵,基本的離散信源： 輸出單符號(hào)消息，且這些消息間兩兩互不相容。用一維隨機(jī)變量X來(lái)描述信源的輸出，其數(shù)學(xué)模型可抽象為:,問(wèn)題：這樣的信源能輸出多少信息? 每個(gè)消息的出現(xiàn)攜帶多少信息量?,28,信息的度量,要點(diǎn)： 信息的度量（信息量）和不確定性消除的程度有關(guān)，消除的不確定性獲得的信息量； 不確定性就是隨機(jī)性，可以用概率論和隨機(jī)過(guò)程來(lái)測(cè)度； 推論： 概率小信息量大，即信息量是概率的單調(diào)遞減函數(shù)； 信息量應(yīng)該具有可加性； 信息量的計(jì)算公式為（香農(nóng)（自）信息量的度量）：,29,2.1.

12、1 自信息,設(shè)離散信源X的概率空間為：,I(ai)代表兩種含義： （1）當(dāng)事件ai發(fā)生以前，表示事件ai發(fā)生的不確定性 （2）當(dāng)事件ai發(fā)生以后，表示事件ai所提供的信息量,自信息量：事件ai發(fā)生所含有的信息量,30,度量單位,計(jì)算自信息量時(shí)要注意有關(guān)事件發(fā)生概率的計(jì)算； 自信息量的單位取決于對(duì)數(shù)的底； 底為2，單位為“比特（bit, binary unit）”； 底為e，單位為“奈特（nat, nature unit）”； 底為10，單位為“哈特（hat, Hartley）”； 根據(jù)換底公式得：,一般計(jì)算都采用以“2”為底的對(duì)數(shù)，為了書(shū)寫(xiě)簡(jiǎn)潔，常把底數(shù)“2”略去不寫(xiě),1 nat = 1.44

13、bit , 1 hat = 3.32 bit；,31,收信者收到某消息獲得的信息量 不確定性減少的量 (收到此消息前關(guān)于某事件的不確定性) - (收到此消息后關(guān)于某事件的不確定性) 通信的實(shí)質(zhì)？ 即：傳遞信息，消除不確定性。,32,2.2.2 信息熵,對(duì)一個(gè)信源發(fā)出不同消息所含有的信息量也不同。所以自信息I(ai)是一個(gè)隨機(jī)變量，不能用它來(lái)作為整個(gè)信源的信息測(cè)度。 信息熵：自信息的數(shù)學(xué)期望，平均自信息量Hr(X)：,r進(jìn)制單位/符號(hào),33,熵的含義,熵是從整個(gè)集合的統(tǒng)計(jì)特性來(lái)考慮的，它從平均意義上來(lái)表征信源的總體特征。 信源輸出前，熵H(X)表示信源的平均不確定性； 信源輸出后，熵H(X)表示

14、每個(gè)消息的平均信息量； 信息熵H(X)表征了變量X的隨機(jī)性。,34,信息熵是信源概率空間的一種特殊函數(shù)。這個(gè)函數(shù)的取值大小，與信源的符號(hào)數(shù)及其概率分布有關(guān)。 用概率矢量P來(lái)表示概率分布P(x)：,3.3 信息熵的基本性質(zhì),則信息熵H(X)是概率矢量P或它的分量p1，p2，pq的q-1元函數(shù)(獨(dú)立變量只有q-1元)。則 H(X)可寫(xiě)成：,35,熵函數(shù)的向量形式,H(P)是概率矢量P的函數(shù)，稱為熵函數(shù)。 我們用下述表示方法： 用H(x)表示以離散隨機(jī)變量x描述的信源的信息熵； 用H(P)或H(p1, p2 , , pq )表示概率矢量為 P = (p1, p2 , , pq )的q個(gè)符號(hào)信源的信息

15、熵。 若當(dāng) q =2 時(shí)，因?yàn)?p1+p2 = 1, 所以將兩個(gè)符號(hào)的熵函數(shù)寫(xiě)成H(p1)或H(p2)。 熵函數(shù)H(P)是一種特殊函數(shù)，具有以下性質(zhì)。,36,熵函數(shù)性質(zhì),1、對(duì)稱性： H(P)的取值與分量 p1, p2 , , pq的順序無(wú)關(guān)。 說(shuō)明： H(P)= pi log pi 中的和式滿足交換率； 熵只與隨機(jī)變量的總體統(tǒng)計(jì)特性有關(guān)。 例子：,37,2、確定性：H(1,0)=H(1,0,0)=H(1,0,0,0)=0 說(shuō)明：從總體來(lái)看，信源雖然有不同的輸出符號(hào)，但它只有一個(gè)符號(hào)幾乎必然出現(xiàn)，而其它符號(hào)則是幾乎不可能出現(xiàn)，那么，這個(gè)信源是一個(gè)確知信源，其熵為零。,分析： 若Pi=1,Pil

16、ogPi=0；其他Pj趨于0 ，PjlogPj 趨于0。由羅比塔法則：,因此,38,3、非負(fù)性： H(P) 0 說(shuō)明： 隨機(jī)變量X的概率分布滿足0pi1，對(duì)數(shù)函數(shù)的底大于1時(shí)，log(pi) 0，-pilog(pi ) 0，即得的熵為正值。只有當(dāng)隨機(jī)變量是一確知量時(shí)熵才等于零。 這種非負(fù)性合適于離散信源的熵，對(duì)連續(xù)信源來(lái)說(shuō)這一性質(zhì)并不存在（基于差熵、相對(duì)熵概念）。,非負(fù)性體現(xiàn)信息是非負(fù)的。,39,4、擴(kuò)展性,說(shuō)明：信源的符號(hào)數(shù)增多時(shí)，若這些取值對(duì)應(yīng)的概率很小(接近于零)，則信源的熵不變。,所以，上式成立。,因?yàn)?趨于0,40,5、可加性 統(tǒng)計(jì)獨(dú)立信源X和Y的聯(lián)合信源XY的熵等于信源X和Y各自的

17、熵之和： H(XY) = H(X)+ H(Y) 即：,另外：可加性是熵函數(shù)的一個(gè)重要特性，正因具有可加性， 才能保證熵函數(shù)的形式是唯一的。,信源XY的符號(hào)聯(lián)合概率,41,證明：,=1,=1,42,例如，甲信源為,它們的聯(lián)合信源是,可計(jì)算得聯(lián)合信源的聯(lián)合熵： H(Z)=H(XY)=log(nm)=log m + log n =H(X) + H(Y),乙信源為,43,6、強(qiáng)可加性 兩個(gè)互相關(guān)聯(lián)的信源X和Y的聯(lián)合信源XY的熵等于信源X的熵加上在X已知條件下信源Y的條件熵。 H（XY）=H（X）+ H（Y | X）,證明： 設(shè)X、Y的概率分布為 X、Y之間存在關(guān)聯(lián)，用條件概率描述：,同時(shí)，聯(lián)合信源XY

18、的各個(gè)符號(hào)，由X、Y信源中的符號(hào)構(gòu)成，每個(gè)聯(lián)合符號(hào)的聯(lián)合概率為：,44,顯然,則,聯(lián)合概率,45,=1,條件熵,條件熵,46,條件熵： H（Y|X）表示信源 X 輸出一符號(hào)的條件下，信源Y再輸出一符號(hào)所能提供的平均信息量。,也即：,由前面的推導(dǎo)，可得：,47,7、遞增性,若原信源 X 中有一個(gè)符號(hào)分割成了m個(gè)元素(符號(hào))，這m個(gè)元素的概率之和等于原元素的概率，而其他符號(hào)的概率不變，則新信源的熵增加。 熵的增加量等于由分割而產(chǎn)生的不確定性量。,48,#（選講）# 證明: 可以從熵的定義或強(qiáng)可加性得出：,49,即得：,50,遞增性的推廣,它表示n個(gè)元素的信源熵可以遞推成(n-1)個(gè)二元信源的熵函數(shù)

19、的加權(quán)和。這樣，可使多元信源的熵函數(shù)的計(jì)算簡(jiǎn)化成計(jì)算若干個(gè)二元信源的熵函數(shù)。因此，熵函數(shù)的遞增性又可稱為遞推性。,51,#（選講）# 例：運(yùn)用熵函數(shù)的遞增性（的推廣），計(jì)算熵函數(shù)H(1/3，1/3，1/6，1/6)的數(shù)值。,52,8、極值性 在離散信源情況下，信源各符號(hào)等概率分布時(shí)，熵值達(dá)到最大。,等概率分布信源的平均不確定性為最大。這是一個(gè)重要結(jié)論，稱為最大離散熵定理。,證明： 因?yàn)閷?duì)數(shù)函數(shù)是型凸函數(shù)，滿足詹森不等式 Elog Y log EY，令矢量Y=1/P即（yi=1/pi），則有：,=1,53,特例：二進(jìn)制離散信源。 該信源符號(hào)只有二個(gè)，設(shè)為“0”和“1”。符號(hào)輸出的概率分別為“”和

20、“1- ”，即信源的概率空間為：,H(X) = -log (1-) log(1-) =H(),即信息熵H(x)是的函數(shù)。 取值于0，1區(qū)間，可畫(huà)出熵函數(shù)H() 的曲線來(lái)，如右圖所示。,54,熵函數(shù)H(P)是概率矢量P(p1，p2， ，pq)的 嚴(yán)格型凸函數(shù)(或稱上凸函數(shù))。 （因?yàn)镠(P)是由具有嚴(yán)格上凸性的對(duì)數(shù)函數(shù)-xlogx（二階導(dǎo)數(shù)0）的線性組合。） 即：對(duì)任意概率矢量 P1(p1,p2, ,pq )和 P2 (p1,p2, ,pq)， 和任意的 01，有： H P1+(1- )P2 H(P1)+(1-)H(P2) 因?yàn)殪睾瘮?shù)具有上凸性，所以熵函數(shù)具有極值，其最大值存在。,9、上凸性,5

21、5,擴(kuò)展信源的由來(lái)： 當(dāng)離散無(wú)記憶信源信源發(fā)出固定長(zhǎng)度的消息序列時(shí)，則得到原信源的擴(kuò)展信源。 例如：在電報(bào)系統(tǒng)中，若信源輸出的是二個(gè)符號(hào)組成的符號(hào)序列，此時(shí)可認(rèn)為是一個(gè)新的信源，它由四個(gè)符號(hào)（00，01，10，11）組成，我們把該信源稱為二元無(wú)記憶信源的二次擴(kuò)展信源。 更進(jìn)一步，如果把N個(gè)二元符號(hào)組成一組，則信源等效成一個(gè)具有2N個(gè)符號(hào)的新信源，把它稱為二元無(wú)記信源的N次擴(kuò)展信源。,2.4 離散無(wú)記憶的擴(kuò)展信源,56,概念： 一般地，對(duì)一個(gè)離散無(wú)記憶信源X，其樣本空間為a1,a2, ,aq ，對(duì)它的輸出消息序列，可用一組組長(zhǎng)度為N的序列來(lái)表示它。這時(shí)，它等效成一個(gè)新信源。 新信源輸出的符號(hào)是N

22、維離散隨機(jī)矢量 X =(X1 ，X2 , XN)， 其中每個(gè)分量Xi (i1,2,N)都是隨機(jī)變量，它們都取值于同一信源符號(hào)集，并且分量之間統(tǒng)計(jì)獨(dú)立，則由隨機(jī)矢量X組成的新信源稱為離散無(wú)記憶信源X的N次擴(kuò)展信源。,57,單符號(hào)離散無(wú)記憶信源X的數(shù)學(xué)模型：,N次擴(kuò)展信源與單符號(hào)離散信源比較，其輸出不是單個(gè)符號(hào)，而是一串N個(gè)相互獨(dú)立的符號(hào)序列： X(X1,X2, XN) ， 聯(lián)合分布密度 P(X)=P(X1X2XN) 它們把 X 等效為一個(gè)新信源-X的N次擴(kuò)展信源。,N次擴(kuò)展,N次擴(kuò)展信源,N次擴(kuò)展信源的數(shù)學(xué)模型,58,N次擴(kuò)展信源數(shù)學(xué)模型表示為：,因?yàn)槭菬o(wú)記憶的(彼此統(tǒng)計(jì)獨(dú)立)則：,59,性質(zhì)：

23、離散平穩(wěn)無(wú)記憶N次擴(kuò)展信源的熵 H(XN) = NH(X),其中：,同理計(jì)算式中其余各項(xiàng)，得到：,H(XN) = H(X)+H(X)+H(X)= N H(X),證明：,分解為N重求和,60,一、概念 在一般情況下，信源在 t = i 時(shí)刻將要發(fā)出什么樣的符號(hào)決定于兩方面： (1) 信源在 t = i 時(shí)刻，隨機(jī)變量Xi 取值的概率分布P(xi)。 一般 P(xi) P(xj) (2) t= i 時(shí)刻以前信源發(fā)出的符號(hào)。 即與條件概率P(xi|xi-1 xi-2)有關(guān) 平穩(wěn)隨機(jī)序列：其統(tǒng)計(jì)性質(zhì)與時(shí)間的推移無(wú)關(guān)，即信源發(fā)出符號(hào)序列的概率分布與時(shí)間起點(diǎn)無(wú)關(guān)。,2.5 離散平穩(wěn)信源,61,一維平穩(wěn)信源

24、： 若當(dāng)t = i，t = j時(shí) (i,j 是大于1的任意整數(shù))，信源輸出的隨機(jī)序列滿足一維概率分布時(shí)間起點(diǎn)無(wú)關(guān)條件 P(xi)=P(xj )=P(x) 二維平穩(wěn)信源： 除滿足上述一維平穩(wěn)信源條件外，如果聯(lián)合概率分布P(xixi+1)也與時(shí)間起點(diǎn)無(wú)關(guān)，即 P(xixi+1)=P(xjxj+1) (i,j為任意整數(shù)且ij) 它表示任何時(shí)刻，信源先后發(fā)出二個(gè)符號(hào)的聯(lián)合概率分布也完全相等。,62,完全平穩(wěn)信源： 如果各維聯(lián)合概率分布均與時(shí)間起點(diǎn)無(wú)關(guān)，那么信源是完全平穩(wěn)的（N為任意正整數(shù)）。,由于聯(lián)合概率與條件概率有以下關(guān)系：,63,平穩(wěn)信源的特點(diǎn)： 對(duì)于平穩(wěn)信源發(fā)出的隨機(jī)序列，其前后符號(hào)依賴的條件概

25、率均與時(shí)間起點(diǎn)無(wú)關(guān)，只與關(guān)聯(lián)長(zhǎng)度N有關(guān)。 如果某時(shí)刻發(fā)出什么符號(hào)只與前面發(fā)出的N個(gè)符號(hào)有關(guān)，那么由平穩(wěn)性，則任何時(shí)刻它們的依賴關(guān)系都是一樣的。,則由前面兩個(gè)關(guān)系，可推知各維條件概率也滿足時(shí)間起點(diǎn)無(wú)關(guān)性：,64,三、離散平穩(wěn)信源的極限熵 對(duì)于一般平穩(wěn)有記憶信源，設(shè)其概率空間為：,發(fā)出的符號(hào)序列為(X1，X2，XN， )，假設(shè)信源符號(hào)之間的依賴長(zhǎng)度為N，且各維概率分布為：,65,且滿足完備集條件，各維概率密度之和皆為1：,66,已知聯(lián)合概率分布，可得離散平穩(wěn)信源的一系列聯(lián)合熵：,N長(zhǎng)的信源符號(hào)序列中平均每符號(hào)攜帶的信息量為：,平均符號(hào)熵:,信息度量1平均符號(hào)熵,67,另一方面，因信源符號(hào)之間的依賴

26、關(guān)系長(zhǎng)度為N, 所以可以求出已知前面N-1個(gè)符號(hào)時(shí)，后面出現(xiàn)一個(gè)符號(hào)的平均不確定性。 條件熵: 若已知前面N一1個(gè)符號(hào)，后面出現(xiàn)一個(gè)符號(hào)的平均不確定性（平均信息量），即得一系列的條件熵：,信息度量2條件熵,68,對(duì)離散平穩(wěn)信源，若H1(X) ，則有： 1) 條件熵、平均符號(hào)熵都隨序列長(zhǎng)度N的增加是非遞增的； 2) 對(duì)于任意序列長(zhǎng)度N，平均符號(hào)熵不小于條件熵； 3) 極限熵 H 存在，并且等于序列長(zhǎng)度N無(wú)窮大時(shí)的平均符號(hào)熵或條件熵。,對(duì)于一般平穩(wěn)信源，求 H相當(dāng)困難（N取無(wú)窮大）。但N不很大時(shí)有： H HN(X) 或 H H(XN|X1X2XN-1)。,離散平穩(wěn)信源性質(zhì)總結(jié),近似計(jì)算,69,對(duì)離

27、散二維平穩(wěn)信源，一維和二維概率分布確定，且與時(shí)間推移無(wú)關(guān)。 對(duì)于這樣的二維平穩(wěn)信源，二符號(hào)之間的條件概率反映了前面輸出某一個(gè)符號(hào)、后面再輸出某一個(gè)符號(hào)的概率，其輸出符號(hào)序列中依賴關(guān)系是有限的，所以有：,特例分析：離散二維平穩(wěn)信源,70,聯(lián)合概率滿足完備性,邊緣分布概率,另外，可從聯(lián)合概率得到邊緣分布概率：,則條件熵表示為：,71,此時(shí)：,可見(jiàn)：離散二維平穩(wěn)信源的極限熵，等于條件熵 H(X2|X1) 。,N-2維邊緣概率,72,推廣： 一般情況，如果平穩(wěn)信源的記憶長(zhǎng)度有限，也即某時(shí)刻輸出什么符號(hào)只與前面的m個(gè)符號(hào)有關(guān)。 此時(shí)，則可用有限記憶長(zhǎng)度的條件熵來(lái)測(cè)度離散平穩(wěn)信源的極限熵：,73,第3章

28、離散信道及其信道容量,第一節(jié) 信道的數(shù)學(xué)模型及分類,第二節(jié) 平均互信息,第三節(jié) 平均互信息的特性,第四節(jié) 信道容量及其計(jì)算方法,第五節(jié) 離散無(wú)記憶擴(kuò)展信道及其信道容量,第六節(jié) 信源與信道的匹配,74,信道的任務(wù)： 以信號(hào)方式傳輸信息和存儲(chǔ)信息。 研究?jī)?nèi)容： 信道中能夠傳送或存儲(chǔ)的最大信息量，即信道容量。,75,3.1 信道的數(shù)學(xué)模型和分類,數(shù)字通信系統(tǒng)的一般模型,76,二、離散信道的數(shù)學(xué)模型,條件概率 P(y|x) 描述了輸入信號(hào)和輸出信號(hào)之間統(tǒng)計(jì)依賴關(guān)系，反映了信道的統(tǒng)計(jì)特性。根據(jù)信道的統(tǒng)計(jì)特性的不同，離散信道又可分成3種情況：,1.無(wú)干擾信道 2.有干擾無(wú)記憶信道 3.有干擾有記憶信道,7

29、7,(1)無(wú)干擾(無(wú)噪聲)信道 信道中沒(méi)有隨機(jī)性的干擾或者干擾很小，輸出符號(hào) y 與輸入符號(hào) x 之間有確定的、一 一對(duì)應(yīng)的關(guān)系。即： y f (x),78,(2) 有干擾無(wú)記憶信道 信道輸入和輸出之間的條件概率是一般的概率分布。 如果任一時(shí)刻輸出符號(hào)只統(tǒng)計(jì)依賴于對(duì)應(yīng)時(shí)刻的輸入符 號(hào)，則這種信道稱為無(wú)記憶信道。,(3) 有干擾(噪聲)有記憶信道 實(shí)際信道往往是既有干擾(噪聲)又有記憶的這種類型。 例如在數(shù)字信道中，由于信道濾波頻率特性不理想時(shí)造成了碼字間串?dāng)_。 在這一類信道中某一瞬間的輸出符號(hào)不但與對(duì)應(yīng)時(shí)刻的輸入符號(hào)有關(guān)，而且還與此以前其他時(shí)刻信道的輸入符號(hào)及輸出符號(hào)有關(guān)，這樣的信道稱為有記憶

30、信道。,80,三、單符號(hào)離散信道,單符號(hào)離散信道特性： 輸入符號(hào)為X，取值于a1,a2, ,ar 輸出符號(hào)為Y，取值于b1,b2, ,bs 條件概率：P(y|x)P(y=bj|x=ai)P(bj|ai) 這一組條件概率稱為信道的傳遞概率或轉(zhuǎn)移概率。 信道中有干擾(噪聲)存在，可以用傳遞概率 P(bj|ai) 來(lái)描述干擾影響的大小。,81,一般簡(jiǎn)單的單符號(hào)離散信道可用 X, P(y|x) , Y 三者加以表述，其數(shù)學(xué)模型可以用如下概率空間 X, P(y|x) ,Y 也可用圖形來(lái)描述：,單符號(hào)離散信道,82,信道矩陣（轉(zhuǎn)移矩陣）模型 一般離散單符號(hào)信道的傳遞概率可用矩陣形式表示，即,矩陣P完全描述

31、了信道的特性，可用它作為離散單符號(hào)信道的另一種數(shù)學(xué)模型的形式。矩陣 P中元素有些是信道干擾引起的錯(cuò)誤概率，有些是信道正確傳輸?shù)母怕省?83,例 二元對(duì)稱信道，BSC，Binary Symmetrical Channel,解：此時(shí)，X:0,1 ; Y:0,1 ; r=s=2，a1=b1=0；a2=b2=1。 傳遞概率:,p是單個(gè)符號(hào)傳輸發(fā)生錯(cuò)誤的概率。 （1-p）表示是無(wú)錯(cuò)誤傳輸?shù)母怕省?轉(zhuǎn)移矩陣:,0 1 0 1,84,（1）聯(lián)合概率,其中,前向概率，描述信道的噪聲特性,后向概率（后驗(yàn)概率）,輸入符號(hào)的先驗(yàn)概率,單符號(hào)離散信道的相關(guān)概率關(guān)系,（2）輸出某符號(hào)的概率,85,含義： 輸出端收到的某

32、符號(hào)，必是輸入端某一符號(hào)輸入所致。,（3）后驗(yàn)概率,且,根據(jù)貝葉斯定理，可知：,86,3.2 信道疑義度與平均互信息,研究離散單符號(hào)信道的信息傳輸問(wèn)題。,一、信道疑義度,先驗(yàn)熵：即信道輸入信源X的熵,H(X)是在接收到輸出Y以前，關(guān)于輸入變量X的先驗(yàn)不確定性。,87,后驗(yàn)熵： 接收到bj后，關(guān)于輸入變量X的不確定性。,后驗(yàn)熵是當(dāng)信道接收端接收到輸出符號(hào)bj后，關(guān)于輸入符號(hào)的不確定性的信息測(cè)度。,88,信道疑義度： 后驗(yàn)熵在輸出符號(hào)集Y范圍內(nèi)是隨機(jī)量。對(duì)后驗(yàn)熵在符號(hào)集Y中求數(shù)學(xué)期望，即-信道疑義度：,89,互信息量 I(x ; y)： 收到消息y 后獲得關(guān)于x的信息量，即消除的不確定性量。,互信

33、息量表示先驗(yàn)的不確定性減去尚存的不確定性，是收信者獲得的信息量。 若互信息I(x ; y)0，說(shuō)明在收到信息量y以前對(duì)消息x是否出現(xiàn)的不確定性較?。坏捎谛诺涝肼暤拇嬖?，反而使得接收到消息y后，反而對(duì)x是否出現(xiàn)的不確定程度增加了。,二、平均互信息,90,平均互信息I(X; Y)：,接收到符號(hào) Y 后, 平均每個(gè)符號(hào)獲得的關(guān)于 X 的信息量，體現(xiàn)輸入與輸出兩個(gè)隨機(jī)變量間的統(tǒng)計(jì)約束程度。,91,另一角度：平均互信息=通信過(guò)程所消除的不確定性：,I(X;Y)是I (x ; y)的統(tǒng)計(jì)平均，可以證明I(X;Y)0 。 若I(X;Y) = 0，表示在信道輸出端接收到符號(hào)后不獲得任何關(guān)于輸入符號(hào)的信息。,

34、92,I(X;Y) I(X;Y) = H(X) - H(X|Y) I(X;Y) = H(Y) - H(Y|X) I(X;Y) = H(X) + H(Y) - H(XY) 其中：,平均互信息與各類熵的關(guān)系,93,維拉圖： 可用于各類熵與平均互信息之間關(guān)系 H(X|Y) = H(X) - I(X;Y) 損失熵 / 信道疑義度 H(Y|X) = H(Y) - I(X;Y) 噪聲熵 / 散布度 H(XY) = H(X)+H(Y)- I(X;Y),H(X),圖中，左邊的圓代表隨機(jī)變量X的熵，右邊的圓代表隨機(jī)變量Y的熵，兩個(gè)圓重疊部分是平均互信息I(X;Y)。每個(gè)圓減去I(X;Y)后剩余的部分代表兩個(gè)疑義

35、度。,94,信息傳輸率 信道中平均每個(gè)符號(hào)所能傳送的信息量。 而平均互信息I(X;Y)則反映了接收到一符號(hào)Y后 平均每個(gè)符號(hào)獲得的關(guān)于X的信息量。 因此，信息傳輸率可作如下定義： 信息傳輸率 R R = I(X;Y) = H(X) H(X|Y) (比特/符號(hào)),3.4 離散信道的信道容量,信息傳輸速率Rt ： 信道在單位時(shí)間內(nèi)平均傳輸?shù)男畔⒘?。即信道中平均每秒傳輸?shù)男畔⒘浚?Rt R/t = I(X;Y)/t = H(X)/t H(X|Y)/t （bit/s）,95,一、信道容量 由于平均互信息I(X;Y)是輸入隨機(jī)變量的型凸函數(shù) ，所以對(duì)一固定的信道，總存在一種信源的輸入分布概率，使傳輸每個(gè)

36、符號(hào)平均獲得的信息量最大。 信道容量：對(duì)任何一個(gè)固定信道，存在一個(gè)最大的信息傳輸率,（比特/符號(hào)）,與之相對(duì)應(yīng)的輸入分布概率P(X)則稱為最佳輸入分布。,96,(Bit/s),Ct仍稱為信道容量：,若平均傳輸一個(gè)符號(hào)需要 t 秒鐘，則信道在單位時(shí)間內(nèi)平均傳輸?shù)淖畲笮畔⒘繛镃t：,性質(zhì) 信道容量與輸入信源的概率分布無(wú)關(guān)，只是信道傳輸概率的函數(shù)，只與信道的統(tǒng)計(jì)特性有關(guān)。 信道容量是完全描述信道特性的參量，是信道的最大信息傳輸率。,97,即：,例 二元對(duì)稱信道容量的計(jì)算,因此，二元對(duì)稱信道的信道容量為：,前述二元對(duì)稱信道，I(X;Y),(比特符號(hào)),98,1.無(wú)噪無(wú)損信道（無(wú)噪一一對(duì)應(yīng)信道）,二、簡(jiǎn)

37、單離散信道的信道容量,例如：,也即,99,其信道矩陣是單位矩陣：,滿足：損失熵H(X|Y)=0、噪聲熵H(Y|X)=0，故 I(X;Y)=H(X)=H(Y),則信道容量：,維拉圖：,最佳輸入分布：等概率分布,100,2.有噪無(wú)損信道,信道特點(diǎn)：輸入一個(gè)符號(hào)X對(duì)應(yīng)若干個(gè)輸出符號(hào)Y，且每一個(gè)X值所對(duì)應(yīng)的Y值不重合。 輸入符號(hào)通過(guò)傳輸變換成了若干個(gè)輸出符號(hào)，不滿足一一對(duì)應(yīng)關(guān)系，但這些輸出符號(hào)仍可以分成互不相交的一些子集合。,例,101,一旦接收到符號(hào)Y后，可消除對(duì)X符號(hào)的不確定性。分析一下： 損失熵H(X|Y)， 噪聲熵H(Y|X),信道矩陣特點(diǎn)：除了每行元素之和為1外，每一列中只有一個(gè)非零項(xiàng)。表明

38、一個(gè)接收符號(hào)只對(duì)應(yīng)一個(gè)發(fā)送符號(hào)，而一個(gè)發(fā)送符號(hào)對(duì)應(yīng)多個(gè)接收符號(hào)，是一對(duì)多關(guān)系。,102,所以 ： I(X;Y) = H(X) H(X|Y) = H(X) 且 I(X;Y) = H(Y) H(Y/X) H(Y) 則 I(X;Y) = H(X) H(Y),損失熵(信道疑義度)=0：,噪聲熵（散布度）0,103,則信道容量為：,最佳輸入分布：等概率分布。,維拉圖,104,3.無(wú)噪有損信道（確定信道）,信道特點(diǎn)：輸入X與輸出Y之間為多對(duì)一關(guān)系，接收到符號(hào)Y后不能完全消除對(duì)X的不確定性。 前向概率 P(y | x) = 0 or 1 后向概率 P(x | y) 0 or 1 可計(jì)算損失熵H(X|Y)、噪

39、聲熵H(Y|X)。,噪聲熵（散布度）=0,損失熵（信道疑義度）0,105,滿足： I(X;Y)=H(Y) H(Y/X) = H(Y) I(X;Y)=H(X) H(X/Y) H(X) 因此： I(X;Y)=H(Y) H(X),則信道容量為：,輸出符號(hào)等概率分布時(shí)H(Y)最大，且一定可以找到一種輸入分布，使得輸出符號(hào)Y達(dá)到等概率分布。,維拉圖,106,三類信道特點(diǎn)： 無(wú)噪無(wú)損信道：損失熵、損失熵皆為0； 無(wú)損信道：損失熵H(X|Y)為0，噪聲熵不為0； 無(wú)噪信道: 噪聲熵H(Y|X)為0，損失熵不為0； 這三類信道的信道容量的計(jì)算，從求平均互信息的極限問(wèn)題退化為求信息熵的極值問(wèn)題。,107,信道特

40、點(diǎn)： 信道矩陣P中每一行都是由同一集合p1，p2，ps 中的諸元素不同排列組成；信道矩陣P每一列也都是由同一集合 q1，q2，qr 中的諸元素不同排列組成。 一般sr。 當(dāng)r=s，兩個(gè)集合相同； 若rs，則qi是 pi的子集。,三、對(duì)稱離散信道的信道容量,例：,對(duì)稱離散信道,108,非對(duì)稱離散信道,強(qiáng)對(duì)稱信道（均勻信道）：若輸入/輸出符號(hào)個(gè)數(shù)相同，都等于r，且信道矩陣為,特點(diǎn)：總的錯(cuò)誤概率為 p ，對(duì)稱地平均分配給r-1個(gè)輸出符號(hào)。它是對(duì)稱離散信道的特例。,109,該項(xiàng)是固定Xx 時(shí)對(duì)Y求和，即對(duì)信道矩陣的行求熵。由于是對(duì)稱信道，所以H(Y/X= x )與 x 無(wú)關(guān)，為一常數(shù)。則,考察：對(duì)稱離

41、散信道的平均互信息 I(X;Y)=H(Y)-H(Y/X),其中,110,因此對(duì)稱離散信道的信道容量應(yīng)為：,可以看出，這是在某種P(x)分布情況下，使得輸出等概分布時(shí)，即 H(Y)=logs 時(shí)的信道容量。,在什么樣的信源輸入情況下，信道輸出等概分布呢？可以證明，輸入等概分布時(shí)，輸出也等概分布： 若輸入概率為等概率p(x)=1/r，則,111,因是對(duì)稱離散信道，信道矩陣的每一列元素之和相等 ：,則有,也就是：信道的輸出也是等概分布的：,112,注意： 信道容量本身與輸入無(wú)關(guān)；但只有當(dāng)滿足輸入的等概分布時(shí)，信息傳輸率才能達(dá)到信道容量。,那么對(duì)稱離散信道的信道容量：,113,在這個(gè)信道中，每個(gè)符號(hào)平

42、均能夠傳輸?shù)淖畲笮畔?.0817比特。,例 某對(duì)稱離散信道的信道矩陣如下，求其信道容量。,解：s=4, r=2,114,特例：對(duì)于二元對(duì)稱信道,這個(gè)式子很重要。,特例：對(duì)于強(qiáng)對(duì)稱信道，其信道容量為：,115,信道容量計(jì)算步驟 當(dāng)信道矩陣P是非奇異矩陣，信道容量計(jì)算過(guò)程： 1）計(jì)算j 2）計(jì)算信道容量C 3）計(jì)算輸出分布概率P(bj) 4）計(jì)算輸入分布概率P(ai),116,例 離散無(wú)記憶信道,不是對(duì)稱信道。r=s=4, 信道矩陣非奇異。利用：,117,則有,計(jì)算信道容量,計(jì)算輸出概率分布,可得,118,計(jì)算最佳輸入分布,根據(jù)方程組求解輸入分布,可得：,119,3.5 離散無(wú)記憶信道的擴(kuò)展信道

43、,對(duì)于離散無(wú)記憶信道 ( DMC，Discrete Memoryless Channel) ，其傳遞概率滿足：,可用 X，P( y / x )，Y 概率空間來(lái)描述。 設(shè)離散無(wú)記憶信道的 輸入符號(hào)集Aa1， ， ar， 輸出符號(hào)集Bb1 ， ， bs，信道矩陣為:,120,則此無(wú)記憶信道的N次擴(kuò)展信道的數(shù)學(xué)模型如圖所示:,而信道矩陣：,其中：,121,例 求二元無(wú)記憶對(duì)稱信道（BSC）的二次擴(kuò)展信道。 解：BSC的輸入和輸出變量X和Y的取值都是0或1，因此，二次擴(kuò)展信道的輸入符號(hào)集為A00，01，10，11，共有224個(gè)符號(hào)，輸出符號(hào)集為B 00，01，10，11。 由于是無(wú)記憶信道，可求得二次

44、擴(kuò)展信道的傳遞概率：,信道矩陣：,122,考察：無(wú)記憶信道的N次擴(kuò)展信道的平均互信息,123,定理3.5：對(duì)于一般離散信道，若信道的輸入隨機(jī)序列為X= (X1X2XN)，通過(guò)信道傳輸，接收到的隨機(jī)序列為Y(Y1Y2YN)。其中，Xi ，Yi是對(duì)應(yīng)第 i 時(shí)刻的隨機(jī)變量。 1）假若信道是無(wú)記憶的，即信道傳遞概率滿足：,2）假若輸入信源是無(wú)記憶的，即滿足,3）若信道和信源都是無(wú)記憶的，則：,124,無(wú)記憶N次擴(kuò)展信道的平均互信息 1）信道的輸入序列 X= (X1X2XN)中的隨機(jī)變量 Xi 取自于同一信源符號(hào)集，并且具有同一種概率分布; 2）通過(guò)相同的信道傳輸?shù)捷敵龆耍ㄐ诺纻鬟f概率不隨 i 改變）

45、隨機(jī)向量Y= (Y1Y2YN)中隨機(jī)變量Yi也取自同一符號(hào)集，則,由定理3.5，無(wú)記憶信道的N次擴(kuò)展信道 若信源也是無(wú)記憶的，則：,說(shuō)明：信源無(wú)記憶時(shí)，無(wú)記憶的N次擴(kuò)展信道的平均互信息等于原信道的平均互信息的N倍。,125,無(wú)記憶N次擴(kuò)展信道的信道容量 一般的離散無(wú)記憶信道的N次擴(kuò)展信道的信道容量是,某時(shí)刻 i 通過(guò)DMC傳輸?shù)淖畲笮畔⒘?信道的輸入隨機(jī)序列X= (X1X2XN)在同一信道中傳輸，故Ci=C,一般情況下，消息序列在離散無(wú)記憶的N次擴(kuò)展信道中傳輸?shù)男畔⒘浚?I（X;Y） NC 信道容量在信源是無(wú)記憶信源且每一個(gè)輸入變量Xi達(dá)到最佳分布時(shí)達(dá)到。,126,3.8 信源與信道的匹配,在

46、一般情況下，當(dāng)信源與信道相連接時(shí)，其信息傳 輸率并未達(dá)到最大。若使信息傳輸率能達(dá)到或盡可能接 近于信道容量，只有在信源取最佳分布時(shí)才能實(shí)現(xiàn)。 “匹配” 當(dāng)信道確定后，信道的實(shí)際信息傳輸率與信源分布是密切相關(guān)的。當(dāng)達(dá)到信道容量時(shí)，稱信源與信道達(dá)到匹配，否則認(rèn)為信道有剩余。,127,信道剩余度,相對(duì)信道剩余度,信道的實(shí)際信息傳輸率和信道傳輸能力之差。,可以用來(lái)衡量信道利用率的高低。,特例 在無(wú)損信道中，信道容量 Clogr (r是信道輸入符號(hào)數(shù))。而I(X;Y)H(X)，因而： 信道的相對(duì)剩余度 = = 信源的剩余度,128,意 義 提高無(wú)損信道的信息傳輸率，就等于減少信源的剩余度。對(duì)于無(wú)損信道，

47、可通過(guò)信源編碼，減少信源剩余度，使信息傳輸率達(dá)到信道容量。 因此在通信系統(tǒng)中，應(yīng)將信源發(fā)出的符號(hào)轉(zhuǎn)換成適合信道傳輸?shù)姆?hào)，從而使信源與信道匹配。,例 某離散無(wú)記憶信源,通過(guò)一個(gè)無(wú)噪無(wú)損二元離散信道進(jìn)行傳輸。,129,分析： 此二元信道的信道容量為： C1 (比特信道符號(hào)) 信源的信息熵為 H(X)1.937 (比特信源符號(hào)) 要使多符號(hào)信源在此二元信道傳輸，須對(duì)X進(jìn)行二元編碼：,對(duì)于碼,(比特信道符號(hào)),對(duì)于碼,(比特信道符號(hào)),信道有剩余。因此，必須通過(guò)合適的信源編碼，使信道的信息傳輸率接近或等于信道容量。,130,第5章 無(wú)失真信源編碼定理,第一節(jié) 編碼器,第二節(jié) 等長(zhǎng)碼,第五節(jié) 變長(zhǎng)信源

48、編碼定理,第三節(jié) 等長(zhǎng)信源編碼定理,第四節(jié) 變長(zhǎng)碼,131,信息通過(guò)信道傳輸?shù)叫潘薜倪^(guò)程。要做到既不失真又快速地通信，需要解決兩個(gè)問(wèn)題： 信源編碼: 在不失真或允許一定失真條件下，提高信息傳輸率. 信道編碼: 在信道受到干擾的情況下，增加信號(hào)的抗干擾能力，同時(shí)又使得信息傳輸率最大. 最佳編碼： 一般來(lái)說(shuō)，抗干擾能與信息傳輸率二者相互矛盾。而編碼定理理論上證明，至少存在某種最佳的編碼能夠解決上述矛盾，做到既可靠又有效地傳輸信息。 信源編碼： 信源雖然多種多樣，但無(wú)論是哪種類型的信源，信源符號(hào)之間總存在相關(guān)性和分布的不均勻性，使得信源存在冗余度。信源編碼的目的就是要減少冗余，提高編碼效率。,引 言

49、,132,研究方法 研究信源編碼時(shí)，將信道編碼與譯碼看成是信道的一部分，從而突出信源編碼； 研究信道編碼時(shí)，將信源編碼與譯碼看成是信源與信宿的一部分，從而突出信道編碼。,5.1 編碼器,編碼器： 對(duì)信源的符號(hào)按一定的數(shù)學(xué)規(guī)則進(jìn)行的變換。 它可以看作這樣一個(gè)系統(tǒng)，它的輸入端為原始信源S，其符號(hào)集為 而信道所能傳輸?shù)姆?hào)集為,133,編碼器功能：用符號(hào)集X中的元素，將原始信源的符號(hào) 變換為相應(yīng)的碼字符號(hào) ，編碼器輸出符號(hào)集為 (碼或碼書(shū)) 稱為碼字，li 為碼字 的碼元個(gè)數(shù)（碼字長(zhǎng)度，碼長(zhǎng)）。碼字集合C稱為碼或碼書(shū)。,134,若要實(shí)現(xiàn)無(wú)失真編碼，這種映射應(yīng)是一一對(duì)應(yīng)的可逆映射。,編碼的形式化描述：

50、 從信源符號(hào)到碼符號(hào)的一種映射,或：,135,6、唯一可譯碼(單義可譯碼） 由碼構(gòu)成的任意一串有限長(zhǎng)的碼符號(hào)序列只能被唯一的譯成所對(duì)應(yīng)的信源符號(hào)序列。 否則,就為非惟一可譯碼或非單義可譯碼。,例：對(duì)于二元碼 ，當(dāng)任意給定一串碼字序列，例如 10001101 只可唯一地劃分為1,00,01,1,01，因此是惟一可譯碼； 而對(duì)另一個(gè)二元碼 ，當(dāng)碼字序列為 01001 可劃分為0,10,01或01,0,01，所以是非惟一可譯的。,136,唯一可譯碼的條件 1）不同的信源符號(hào)變換成不同的碼字(非奇異碼)； 2）任意有限長(zhǎng)的信源序列所對(duì)應(yīng)的碼元序列各不相同. 即: 碼的任意有限長(zhǎng)N次擴(kuò)展碼都是非奇異碼。

51、 Or: 碼符號(hào)序列的反變換也唯一的（擴(kuò)展碼非奇異） 原因： 若要使某一碼為惟一可譯碼，則對(duì)于任意有限長(zhǎng)的碼符號(hào)序列，必須只能被惟一地分割成一個(gè)個(gè)的碼字，才能實(shí)現(xiàn)唯一的譯碼。,137,無(wú)失真的編碼的一般條件 1）碼字與信源符號(hào)之間一一對(duì)應(yīng)（非奇異碼）； 2）碼符號(hào)序列的反變換也唯一的（擴(kuò)展碼非奇異）。 即：編碼必須是唯一可譯碼。否則，就會(huì)引起譯碼的錯(cuò)誤與失真。 等長(zhǎng)碼是唯一可譯碼的條件 若等長(zhǎng)碼是非奇異碼，則它的任意有限長(zhǎng)N次擴(kuò)展碼一定也是非奇異碼。 因此，等長(zhǎng)非奇異碼字一定是唯一可譯碼,因?yàn)椴捎霉潭ㄩL(zhǎng)度劃分碼字序列.,5.2 等長(zhǎng)碼,138,1）若對(duì)每個(gè)信源符號(hào)進(jìn)行等長(zhǎng)編碼，則必須滿足: 其

52、中: l是碼長(zhǎng)，r是碼符號(hào)集的碼元數(shù)，q信源符號(hào)數(shù)。,2）若對(duì)信源的N次擴(kuò)展信源進(jìn)行編碼，必須滿足:,表示平均每個(gè)信源符號(hào)所需的碼符號(hào)個(gè)數(shù)。,即,為了使等長(zhǎng)碼為非奇異碼（唯一可譯碼），那么:,139,例證：根據(jù)依賴關(guān)系，信源符號(hào)平均所需碼符號(hào)數(shù)可減少。 例 設(shè)信源,而其依賴關(guān)系為：,1）若不考慮符號(hào)間的依賴關(guān)系，可得每符號(hào)碼長(zhǎng)l2； 2）若考慮符號(hào)間的二元依賴關(guān)系，可作二次擴(kuò)展信源進(jìn)行分析。根據(jù)條件概率僅有4項(xiàng)的概率不為零，可得擴(kuò)展信源的碼長(zhǎng) l=2，而每個(gè)信源符號(hào)的平均碼長(zhǎng)為 l/N=1 。,140,5.3 等長(zhǎng)信源編碼定理,給出了等長(zhǎng)信源編碼所需碼長(zhǎng)的極限值。,定理 等長(zhǎng)信源編碼定理 一熵

53、為H(S)的離散無(wú)記憶信源，若對(duì)其N次擴(kuò)展信源進(jìn)行等長(zhǎng) r 元編碼，碼長(zhǎng)為l，對(duì)于任意 大于0，只要滿足,當(dāng)N足夠大時(shí)，則可以實(shí)現(xiàn)幾乎無(wú)失真編碼，反之，若：,則不可能實(shí)現(xiàn)無(wú)失真編碼，當(dāng)N趨向于無(wú)窮大時(shí)，譯碼錯(cuò)誤率接近于1。,141,1、唯一可譯變長(zhǎng)碼,5.4 變長(zhǎng)碼,優(yōu)勢(shì)：容易實(shí)現(xiàn)效率很高的編碼。,變長(zhǎng)碼也必須是唯一可譯碼，才能實(shí)現(xiàn)無(wú)失真編碼。,碼1是一個(gè)奇異碼，故不是唯一可譯碼； 碼2也不是唯一可譯碼，因?yàn)槭盏揭淮蛄?，無(wú)法唯一譯出對(duì)應(yīng)的原符號(hào)序列，如01000，即可譯作s4s3s1,也可譯作s4s1s3,s1s2s3或s1s2s1s1；,142,因此，對(duì)于碼C： 若其為唯一可譯碼，則必為非

54、奇異碼； 若其為即時(shí)碼，則必是唯一可譯碼；反之，作為唯一可譯碼，則不一定是即時(shí)碼。,所有的碼,非奇異碼,唯一可譯碼,即時(shí)碼（非延長(zhǎng)碼）,143,2、即時(shí)碼（非延時(shí)碼）的樹(shù)圖構(gòu)造法,對(duì)于給定碼字集合C，可用碼樹(shù)來(lái)描述。 同時(shí)，樹(shù)圖法可構(gòu)造即時(shí)碼。,144,非即時(shí)碼的樹(shù)圖 中間節(jié)點(diǎn)安排為碼字,1.樹(shù)圖中間節(jié)點(diǎn)不作為碼字； 2.一旦某節(jié)點(diǎn)作為碼字，則 不再繼續(xù)進(jìn)行分枝。 這樣可保證每個(gè)碼字不同，且滿足前綴條件碼的條件。,一般編碼方法 選擇相應(yīng)節(jié)點(diǎn)作為碼字：不同的路徑上的分支，對(duì)應(yīng)了相應(yīng)的碼元符號(hào)，則可得到所編碼字。,構(gòu)造即時(shí)碼,145,譯碼方法 因?yàn)槊恳淮a元對(duì)應(yīng)于一個(gè)的樹(shù)圖分枝路徑，則即時(shí)碼的樹(shù)圖可

55、以用來(lái)譯碼。譯碼器系統(tǒng)對(duì)一串符號(hào)序列譯碼過(guò)程： 1）首先從樹(shù)根出發(fā)，根據(jù)接收的第一個(gè)碼元符號(hào)來(lái)選擇應(yīng)走的第一條路徑； 2）若沿著所選路徑走到某中間節(jié)點(diǎn)，再根據(jù)接收的第二個(gè)碼元符號(hào)來(lái)選擇第二條路經(jīng)； 3）若又走到中間節(jié)點(diǎn)，再依次繼續(xù)選擇路徑，直到終端節(jié)點(diǎn)為止。這時(shí)，可根據(jù)所經(jīng)歷的枝路，判斷出所接收的碼字。 4）重新返回樹(shù)根，再作下一個(gè)接收碼字的判斷。 這樣，便可將接收到的一串碼符號(hào)序列譯成信源符號(hào)序列。,146,3、克拉夫特（Kraft）不等式,定理 對(duì)于碼符號(hào)為 的任意r元即時(shí)碼 ，若所對(duì)應(yīng)的碼長(zhǎng) ， 則必定滿足： 反之，若碼長(zhǎng)滿足上式，則一定存在這樣的即時(shí)碼 。,*可以證明，對(duì)于唯一可譯碼也

56、須滿足Kraft不等式。,這說(shuō)明，其他唯一可譯碼并不比即時(shí)碼占優(yōu)。 而即時(shí)碼很容易用樹(shù)圖法構(gòu)造，所以在討論唯一可譯碼時(shí)，只需要討論即時(shí)碼就可以了。,定理 若存在一個(gè)碼長(zhǎng)為 的唯一可譯碼，則一定存在一個(gè)同樣長(zhǎng)度的即時(shí)碼。,147,例：設(shè)二進(jìn)制碼樹(shù)中X=(a1 , a2 , a3 , a4), L1=1, L2=2,L3=2,L4=3,應(yīng)用Kraft不等式,得：,不存在滿足這種Li的唯一可譯碼,如果將各碼字長(zhǎng)度改成L1=1,L2=2,L3=3,L4=3,則,存在滿足這種Li唯一可譯碼,碼樹(shù),148,設(shè)信源,編碼后的碼字為：,碼長(zhǎng)為：,碼的平均長(zhǎng)度（平均碼長(zhǎng)）為：,5.5 變長(zhǎng)信源編碼定理,（碼符號(hào)

57、/信源符號(hào)）,碼的平均長(zhǎng)度,信息傳輸率（碼率）： 平均每個(gè)碼元攜帶的信息量，即編碼后信道的信息傳輸率：,（比特/碼符號(hào)）,149,若信道傳輸一個(gè)碼符號(hào)平均需要t秒鐘，則編碼后信道的每秒傳輸?shù)男畔⒘繛椋?（比特/秒）,由此可見(jiàn)： 平均碼長(zhǎng)越短，信息傳輸效率越高。,緊致碼（最佳碼） 對(duì)于某一信源和某一個(gè)碼符號(hào)集合，若有一個(gè)唯一可譯碼，它的平均碼長(zhǎng)小于其他唯一可譯碼的長(zhǎng)度。 無(wú)失真信源編碼的基本問(wèn)題就是尋找緊致碼。,150,定理 若對(duì)一熵為H(S)的離散無(wú)記憶信源 S 進(jìn)行r 元編碼，則總是可以找到一種無(wú)失真編碼方法構(gòu)成唯一可譯碼，使其平均碼長(zhǎng)滿足：,說(shuō)明： 下界：平均碼長(zhǎng)不能小于極限H(s)/lo

58、gr,否則唯一可譯碼不存在。 上界：給出了平均碼長(zhǎng)的上界。但并不是說(shuō)大于這個(gè)上界就不能構(gòu)成唯一可譯碼。而是說(shuō)在上界范圍內(nèi)，可找到唯一可譯碼。,151,無(wú)失真變長(zhǎng)信源編碼定理（香農(nóng)第一定理） 離散無(wú)記憶信源S的N次擴(kuò)展信源 ，其熵為 ，且編碼器碼元符號(hào)集為 . 對(duì)信源 進(jìn)行編碼，總可以找到一種編碼方法，構(gòu)成唯一可譯碼，使信源S中每個(gè)信源符號(hào)si所需要的平均碼長(zhǎng) 滿足,當(dāng) 則得：,152,定理含義： 要做到無(wú)失真信源編碼，變換每個(gè)信源符號(hào)平均所需最少的r元碼元數(shù)是信源的熵值。 若編碼的平均碼長(zhǎng)小于信源的熵，則唯一可譯碼不存在，在譯碼時(shí)必然帶來(lái)失真或差錯(cuò)。 同時(shí)，通過(guò)對(duì)擴(kuò)展信源進(jìn)行變長(zhǎng)編碼，當(dāng)擴(kuò)展長(zhǎng)度N足夠大時(shí)，平均碼長(zhǎng)可達(dá)到此極限值。 信源的