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

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

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

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

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

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

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

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

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

9、： 獨立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為時間標(biāo)志）,N維隨機矢量的一個取值，i(ai1 ai2aiN),P(aik)是符號集A的一維概率分布,若各隨機變量Xi取值同樣符號集A:a1,a2,aq，則,24,信源X的各輸出Xi間統(tǒng)計獨立、且取值同一符號集A。該信源 輸出的N維隨機矢量X為離散無記憶信源X的N次擴展信源。 此擴展信源取值為符號集i (ai1ai2aiN), 其中 (i1 , i2 ,iN =1,2 , ,q)， 其數(shù)學(xué)模型是X信源空間的N重空間：

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

11、起點 i 無關(guān)，信源輸出的符號序列可看成為時齊馬爾可夫鏈，則此信源稱為時齊馬爾可夫信源。,27,2.2 離散信源的信息熵,基本的離散信源： 輸出單符號消息，且這些消息間兩兩互不相容。用一維隨機變量X來描述信源的輸出，其數(shù)學(xué)模型可抽象為:,問題：這樣的信源能輸出多少信息? 每個消息的出現(xiàn)攜帶多少信息量?,28,信息的度量,要點： 信息的度量（信息量）和不確定性消除的程度有關(guān)，消除的不確定性獲得的信息量； 不確定性就是隨機性，可以用概率論和隨機過程來測度； 推論： 概率小信息量大，即信息量是概率的單調(diào)遞減函數(shù)； 信息量應(yīng)該具有可加性； 信息量的計算公式為（香農(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,度量單位,計算自信息量時要注意有關(guān)事件發(fā)生概率的計算； 自信息量的單位取決于對數(shù)的底； 底為2，單位為“比特（bit, binary unit）”； 底為e，單位為“奈特（nat, nature unit）”； 底為10，單位為“哈特（hat, Hartley）”； 根據(jù)換底公式得：,一般計算都采用以“2”為底的對數(shù)，為了書寫簡潔，常把底數(shù)“2”略去不寫,1 nat = 1.44

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

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

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

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

17、熵之和： H(XY) = H(X)+ H(Y) 即：,另外：可加性是熵函數(shù)的一個重要特性，正因具有可加性， 才能保證熵函數(shù)的形式是唯一的。,信源XY的符號聯(lián)合概率,41,證明：,=1,=1,42,例如，甲信源為,它們的聯(lián)合信源是,可計算得聯(lián)合信源的聯(lián)合熵： H(Z)=H(XY)=log(nm)=log m + log n =H(X) + H(Y),乙信源為,43,6、強可加性 兩個互相關(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)，用條件概率描述：,同時，聯(lián)合信源XY

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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),圖中，左邊的圓代表隨機變量X的熵，右邊的圓代表隨機變量Y的熵，兩個圓重疊部分是平均互信息I(X;Y)。每個圓減去I(X;Y)后剩余的部分代表兩個疑義

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

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

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

38、一個接收符號只對應(yīng)一個發(fā)送符號，而一個發(fā)送符號對應(yīng)多個接收符號，是一對多關(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.無噪有損信道（確定信道）,信道特點：輸入X與輸出Y之間為多對一關(guān)系，接收到符號Y后不能完全消除對X的不確定性。 前向概率 P(y | x) = 0 or 1 后向概率 P(x | y) 0 or 1 可計算損失熵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(Y)最大，且一定可以找到一種輸入分布，使得輸出符號Y達(dá)到等概率分布。,維拉圖,106,三類信道特點： 無噪無損信道：損失熵、損失熵皆為0； 無損信道：損失熵H(X|Y)為0，噪聲熵不為0； 無噪信道: 噪聲熵H(Y|X)為0，損失熵不為0； 這三類信道的信道容量的計算，從求平均互信息的極限問題退化為求信息熵的極值問題。,107,信道特

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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