信息論理論基礎(chǔ)

1、信息論理論基礎(chǔ)1第1頁，共118頁，2022年，5月20日，1點21分，星期一第2章 基本信息論2.1 信息度量2.2 離散信源的熵2.3 二元聯(lián)合信源的共熵與條件熵2.4 連續(xù)信源的熵2.5 熵速率和信道容量2.6 離散有噪聲信道的熵速率和信道容量2.7 連續(xù)有噪聲信道的熵速率和信道容量2.8 使信源與信道匹配的編碼2022/9/12第2頁，共118頁，2022年，5月20日，1點21分，星期一2.1 信息度量2022/9/13第3頁，共118頁，2022年，5月20日，1點21分，星期一2.1.1 信息度量的必要性通信的目的是為了傳遞信息。單位時間內(nèi)信道所傳遞的信息量稱為傳信率，它是衡量通

2、信系統(tǒng)性能的重要指標之一。為了得出通信系統(tǒng)的傳信率，必須對消息或信源所含有的信息有一個數(shù)量上的度量方法這就是我們研究信息度量的目的。 2022/9/14第4頁，共118頁，2022年，5月20日，1點21分，星期一2.1.2 信源的不確定性1. 研究不確定性的目的【例】A. 明天太陽將從東方升起。 B. 明天小張會給小王打電話。 C. 明天上午小張會給小王打電話。結(jié)論：(1) 信源發(fā)出的消息狀態(tài)應(yīng)該存在某種程度的不確定性；(2) 信息的多少與信源的不確定性有關(guān)。2022/9/15第5頁，共118頁，2022年，5月20日，1點21分，星期一2.不確定性的度量不確定程度 不確定程度可以直觀理解為

3、猜測某些隨機事件的難易程度。【例】布袋中有100個小球，大小、重量、手感完全相同，但顏色不同。從布袋中任取一球，猜測其顏色。 A. 99個紅球，1個白球； B. 50個紅球，50個白球； C. 25個紅球，25個白球，25個黑球，25個黃球。2022/9/16第6頁，共118頁，2022年，5月20日，1點21分，星期一(1) 不確定程度與信源概率空間有關(guān)；(2) 若狀態(tài)數(shù)相同，等概分布時不確定程度最大；(3) 等概分布時，狀態(tài)數(shù)越多則不確定程度越大。2022/9/17第7頁，共118頁，2022年，5月20日，1點21分，星期一3.不確定程度基本關(guān)系式Hartley公式 若信源X等概分布，則

4、其不確定程度H(x)與概率P滿足：P越大，則H(x)越??；當P =1時，則H(x) =0；當P =0時，則H(x) = ；信源不確定程度應(yīng)具有可加性。 若X與X相互獨立，則H(x, x)=H(x)+ H(x) 對數(shù)可以取2、e、10為底，相應(yīng)不確定程度的單位分別為比特(bit)、奈特(nat) 、哈特萊(Hartley) 。2022/9/18第8頁，共118頁，2022年，5月20日，1點21分，星期一不等概情況：消息xi的不確定程度2022/9/19第9頁，共118頁，2022年，5月20日，1點21分，星期一2.1.3 信息量1.概率基本關(guān)系式(1)(2)(3)2022/9/110第10頁

5、，共118頁，2022年，5月20日，1點21分，星期一(4)(5) 當X和Y相互獨立時，(6)2022/9/111第11頁，共118頁，2022年，5月20日，1點21分，星期一2.信息量的定義： 收信者收到一個消息后，所獲得的信息量等于不確定度的減少量。I=不確定度的減少量2022/9/112第12頁，共118頁，2022年，5月20日，1點21分，星期一3. 自信息量 在沒有噪聲的情況下，信源發(fā)出xi 接收者就會收到xi。這時接收者收到的信息量就等于xi本身含有的信息量，稱為信源狀態(tài)xi的自信息量，記為I(xi)。收到xi前對xi的不確定程度：H(xi)收到xi后對xi的不確定程度：0自

6、信息量2022/9/113第13頁，共118頁，2022年，5月20日，1點21分，星期一【例】一次擲兩個色子，作為一個離散信源，求下列消息的自信息量。 a.僅有一個為3； b.至少有一個為4；c.兩個之和為偶數(shù)。 解：p(a)=10/36=5/18 p(b)=11/36 p(c)=18/36=1/2 I(a)=log(18/5)=1.848 (bit) I(b)=log(36/11)=1.7105 (bit) I(c)=log2=1 (bit)2022/9/114第14頁，共118頁，2022年，5月20日，1點21分，星期一4.互信息量： 在有噪聲信道下，假設(shè)信源發(fā)出的狀態(tài)為xi，接收者收

7、到的狀態(tài)為yj。接收者收到y(tǒng)j后，從yj中獲取到關(guān)于xi的信息量，就是信源發(fā)出xi后接收者收到的信息量，稱為互信息量，記為I(xi, yj)。2022/9/115第15頁，共118頁，2022年，5月20日，1點21分，星期一收到y(tǒng)j前對xi的不確定程度：收到y(tǒng)j后對xi的不確定程度：收到y(tǒng)j后對xi的不確定程度：2022/9/116第16頁，共118頁，2022年，5月20日，1點21分，星期一【例1】某電報系統(tǒng)發(fā)送傳號M和空號S的概率相等，即P(M)=P(S)=1/2。由于信道中噪聲的影響，使1/6的傳號收成空號，而半數(shù)的空號收成傳號。問收信者收到一個符號后所獲得的平均信息量是多少？ 解：

8、1.計算先驗概率、聯(lián)合概率和后驗概率 發(fā)送符號： 接收符號： x1：發(fā)M，x2：發(fā)S，y1：收M，y2：收S p(x1)=1/2，p(x2)=1/2 S S SSM M MM M M M MMS S SS S SM M M M Mp(x1y1)=5/12，p(x1y2)=1/12，p(x2y1)=1/4p(x2 y2)=1/4p(x1|y1)=5/8，p(x1|y2)=1/4，p(x2|y1)=3/8，p(x2| y2)=3/42022/9/117第17頁，共118頁，2022年，5月20日，1點21分，星期一2.計算收到一個消息所獲得的信息量2022/9/118第18頁，共118頁，2022

9、年，5月20日，1點21分，星期一3.計算收到一個消息所獲得的平均信息量2022/9/119第19頁，共118頁，2022年，5月20日，1點21分，星期一2.2 離散信源的熵2022/9/120第20頁，共118頁，2022年，5月20日，1點21分，星期一1.離散信源 離散信源是指只能輸出有限數(shù)量消息(狀態(tài))的信源。2.離散信源的熵 信源輸出一個消息(狀態(tài))所提供的平均信息量或信源的不肯定程度稱為信源熵。單位：bit/符號(消息)、nat/符號(消息)、Hartley/符號(消息)2022/9/121第21頁，共118頁，2022年，5月20日，1點21分，星期一【例1】計算只能輸出“1”

10、和“0”兩個消息(狀態(tài))的簡單二元信源的熵。解：假設(shè)p(1)=p, p(0)=1-p(0p1)(1)當p=1/2時，H(x)=1bit/符號(2)當p=0或p=1時，H(x)=0H(x)01/21p12022/9/122第22頁，共118頁，2022年，5月20日，1點21分，星期一3. 熵函數(shù)的性質(zhì)(1) 非負性 H(x) 0 由于 0p(xi)1 所以 log p(xi) 0 因此有 H(x)0 (2) 對稱性 (3) 確定性2022/9/123第23頁，共118頁，2022年，5月20日，1點21分，星期一(4) 極值性 且N越大，Hmax(x)越大離散信源的最大熵定理證明：作輔助函數(shù)2

11、022/9/124第24頁，共118頁，2022年，5月20日，1點21分，星期一令：可得代入到約束方程可得因此2022/9/125第25頁，共118頁，2022年，5月20日，1點21分，星期一2.3 二元聯(lián)合信源的共熵與條件熵2022/9/126第26頁，共118頁，2022年，5月20日，1點21分，星期一2.3.1 二元聯(lián)合信源的共熵1.定義 二元聯(lián)合信源的共熵是指二元聯(lián)合信源(X,Y)輸出一個組合消息狀態(tài)所發(fā)出的平均信息量，也稱為聯(lián)合熵，記作H(x,y)。2.表達式 (xi,yj)的信息量2022/9/127第27頁，共118頁，2022年，5月20日，1點21分，星期一2.3.2

12、條件熵1.定義 X的狀態(tài)已知時， Y輸出一個狀態(tài)所發(fā)出的平均信息量稱為在X給定條件下，Y的條件熵，記作H(y|x)。 在Y 給定條件下， X的條件熵，記作H(x|y) 。2.表達式 已知xi的條件下， yj的信息量2022/9/128第28頁，共118頁，2022年，5月20日，1點21分，星期一3. H(x,y)=H(x)+H(y|x)= H(y)+H(x|y)證明：將 代入上式得由于因此2022/9/129第29頁，共118頁，2022年，5月20日，1點21分，星期一2.3.3 H(x,y) H(x)+H(y)的證明當X，Y相互獨立時取“=”，當X，Y相關(guān)時取“”證明： 由Lagrang

13、e中值定理可知 若f(x)在Z,Z+h上連續(xù)，在(Z,Z+h)上可微，則在(Z,Z+h)上至少有一點C，使得 f (Z+h)- f (Z)=h f (C) C= Z+h, 0 0 分子0，分母0 ii) aij 0，分母0 p(xi)p(yj)+ aij p(xi)p(yj)+ aij = p(xi,yj) 0 因此 X，Y相關(guān)時,H(x,y) H(x)+H(y)2022/9/134第34頁，共118頁，2022年，5月20日，1點21分，星期一推論1 由于 H(x,y) H(x)+H(y) H(x,y)=H(x)+H(y|x) 所以 H(x)+H(y|x) H(x)+H(y) 因此 同理推論

14、2 H(y|x) H(y)H(x|y) H(x)H(x,y, ,z) H(x)+H(y)+ +H(z)2022/9/135第35頁，共118頁，2022年，5月20日，1點21分，星期一【例1】有兩個同時輸出消息的信源X和Y，X能輸出A，B，C三個消息，Y能輸出D，E，F(xiàn)，G四個消息。P(x)和P(y|x)的具體數(shù)值如表所示。求H(x)，H(y)，H(x,y)和H(y|x) 。解：令 x1:A x2:B x3:C y1:D y2:E y3:F y4:GXABCP(x)1/21/31/6P(y|x)DEFG1/41/41/41/43/101/51/53/101/61/21/61/62022/9/

15、136第36頁，共118頁，2022年，5月20日，1點21分，星期一 (1) 由 可得 =3.417 bit/對符號Xx1x2x3p(xi)p(yj|xi)y1y2y3y4p(xi, yj)x1x2x3y1y2y3y41/21/31/61/41/41/41/43/101/53/101/51/61/61/61/21/81/81/81/81/101/151/101/151/361/121/361/362022/9/137第37頁，共118頁，2022年，5月20日，1點21分，星期一(2) =1.461 bit/符號(3) 由 可得 =1.997 bit/符號p(xi, yj)x1x2x3y1y

16、2y3y41/81/81/81/81/101/151/101/151/361/121/361/36p(y1)=91/360,p(y2)=99/360,p(y3)=79/360,p(y4)=91/3602022/9/138第38頁，共118頁，2022年，5月20日，1點21分，星期一(4) =1.956 bit/符號 或 由H(x,y)=H(x)+H(y|x)得 H(y|x) =H(x,y) -H(x) =3.417-1.461=1.956 bit/符號p(xi, yj)x1x2x3y1y2y3y41/81/81/81/81/101/151/101/151/361/121/361/36p(yj

17、|xi)x1x2x3y1y2y3y41/41/41/41/43/101/53/101/51/61/61/61/22022/9/139第39頁，共118頁，2022年，5月20日，1點21分，星期一離散平穩(wěn)有記憶信源的熵極限熵1.離散平穩(wěn)有記憶信源 所謂離散平穩(wěn)有記憶信源就是一種相關(guān)信源，信源發(fā)出的前后符號間具有相關(guān)性，并且信源的統(tǒng)計特性與時間無關(guān)。有記憶是指信源在某一個時刻的輸出狀態(tài)的統(tǒng)計特性與該信源以前的輸出狀態(tài)有關(guān)。 假設(shè)信源發(fā)出的第一個符號記作X1，第二個符號記作X2， ，第N個符號記作XN ， 若XN的概率分布與它前面的m個符號XN-1 ， XN-2 ， ， XN -m，有關(guān)，而與更前

18、面的符號XN-m1 ， XN-m-2 ， 無關(guān)，則稱該離散信源的記憶長度為m 。平穩(wěn)是指信源的統(tǒng)計特性與時間無關(guān)。2022/9/140第40頁，共118頁，2022年，5月20日，1點21分，星期一2.極限熵的概念假設(shè)離散平穩(wěn)有記憶信源X發(fā)出了N個符號：X1， X2， ， XN 。則可以將這N個符號看作是一個N維聯(lián)合信源。N個符號提供的總的信息量為： H(X1， X2， ， XN )平均每個符號提供的平均信息量為 H(X1， X2， ， XN )/N對于實際信源來說，是一種無限長的序列，符號間相關(guān)性可以延伸到無窮。因此，離散平穩(wěn)有記憶信源輸出一個符號提供的平均信息量為： 這個熵稱為離散平穩(wěn)有記

19、憶信源的極限熵。2022/9/141第41頁，共118頁，2022年，5月20日，1點21分，星期一3. m階馬爾柯夫信源的極限熵如果一個離散平穩(wěn)有記憶信源在任意時刻輸出符號的概率僅依賴于它前面的m個時刻的輸出符號，而與更前面的符號無關(guān)，則該信源稱為記憶長度為m的離散平穩(wěn)有記憶信源，也稱為m階馬爾柯夫信源。馬爾柯夫信源是一種特殊的、比較接近實際的離散平穩(wěn)有記憶信源。2022/9/142第42頁，共118頁，2022年，5月20日，1點21分，星期一2022/9/143第43頁，共118頁，2022年，5月20日，1點21分，星期一對于m階馬爾柯夫信源Hm+1m階條件熵2022/9/144第44

20、頁，共118頁，2022年，5月20日，1點21分，星期一幾點說明：對于實際的離散非平穩(wěn)有記憶信源，其極限熵是不存在的；可以假設(shè)其為記憶長度為無窮大的離散平穩(wěn)有記憶信源，極限熵H存在，但求解困難；進一步假設(shè)其為m階Markov信源，用其極限熵Hm+1近似；再進一步假設(shè)其為一階Markov信源，用其極限熵H1+1近似；最簡化的信源是離散無記憶信源，其熵為H(x)；最后可以假定為等概的離散無記憶信源，其熵為log N。 H Hm+1 H1+1 H(x) log N2022/9/145第45頁，共118頁，2022年，5月20日，1點21分，星期一【例2】已知離散信源的概率分布為 (1) 當符號間無

21、相關(guān)性時，求該信源的熵。 解： bit/符號 X012P(X)11/364/91/42022/9/146第46頁，共118頁，2022年，5月20日，1點21分，星期一 (2) 若信源為有記憶信源，且記憶長度為1，求該信源的熵。 解：由 得P(Xi+1|Xi)Xi 0 1 2Xi+1012 P(Xi，Xi+1)Xi 0 1 2Xi+1012 9/11 2/1101/8 3/41/80 2/97/91/4 1/1801/18 1/31/180 1/187/362022/9/147第47頁，共118頁，2022年，5月20日，1點21分，星期一= 0.890 bit/符號2022/9/148第48

22、頁，共118頁，2022年，5月20日，1點21分，星期一2.3.4 消息的剩余度由于信源內(nèi)部的消息狀態(tài)的相關(guān)性和分布性，使其熵減少的現(xiàn)象稱為剩余。剩余產(chǎn)生的原因信源的不等概分布信源前后符號間具有相關(guān)性剩余的程度相對熵 剩余度內(nèi)熵=H(x)/Hmax(x)=Hmax(x) -H(x)2022/9/149第49頁，共118頁，2022年，5月20日，1點21分，星期一2.4 連續(xù)信源的熵2022/9/150第50頁，共118頁，2022年，5月20日，1點21分，星期一2.4.1 連續(xù)信源熵的定義 所謂連續(xù)信源就是指它們輸出的量是連續(xù)的。這種信源的輸出量，在任一時刻，在某個范圍內(nèi)可以取無窮多個數(shù)

23、值。 1.連續(xù)信源熵的表達式 可以利用離散信源熵的概念來定義連續(xù)信源熵。2022/9/151第51頁，共118頁，2022年，5月20日，1點21分，星期一離散信源X的概率分布為：當dx0時，H絕 H(x) 2022/9/152第52頁，共118頁，2022年，5月20日，1點21分，星期一定義連續(xù)信源的熵為： 2022/9/153第53頁，共118頁，2022年，5月20日，1點21分，星期一幾點說明：連續(xù)信源有無窮多個狀態(tài)，因此其絕對熵必然為無窮大。連續(xù)信源熵為一個相對熵。連續(xù)信源熵不具有非負性，可以為負值。研究信息傳輸問題時，分析信道的輸入和輸出的交互信息量時是求兩個熵的差，當采用相同的

24、量化過程時，兩個無窮大量將被抵消，不影響分析。2022/9/154第54頁，共118頁，2022年，5月20日，1點21分，星期一2.幾種典型連續(xù)信源的熵 均勻分布的連續(xù)信源熵設(shè)一維連續(xù)隨機變量X的取值區(qū)間是a,b，其概率密度函數(shù)為2022/9/155第55頁，共118頁，2022年，5月20日，1點21分，星期一(2) 高斯分布的連續(xù)信源熵其中，m是隨機變量X的均值2是隨機變量X的方差2022/9/156第56頁，共118頁，2022年，5月20日，1點21分，星期一2022/9/157第57頁，共118頁，2022年，5月20日，1點21分，星期一2.4.2 連續(xù)信源的最大熵變分法求函數(shù)p

25、=p(x)使g最大構(gòu)造令2022/9/158第58頁，共118頁，2022年，5月20日，1點21分，星期一 輸出幅度受限（瞬時功率受限）時的最大熵2022/9/159第59頁，共118頁，2022年，5月20日，1點21分，星期一結(jié)論：對于瞬時功率受限的連續(xù)信源，在假定信源狀態(tài)為獨立時，當信源為均勻分布時，具有最大熵。其最大熵為：2022/9/160第60頁，共118頁，2022年，5月20日，1點21分，星期一(2) 輸出平均功率受限時的最大熵2022/9/161第61頁，共118頁，2022年，5月20日，1點21分，星期一2022/9/162第62頁，共118頁，2022年，5月20日

26、，1點21分，星期一結(jié)論：（連續(xù)信源的最大熵定理）對于輸出平均功率受限的連續(xù)信源，在假設(shè)狀態(tài)相互獨立時，當其概率分布為均值為0的高斯分布時，具有最大熵。其最大熵值隨功率 N 的增加而增加。2022/9/163第63頁，共118頁，2022年，5月20日，1點21分，星期一2.4.3 熵功率對于平均功率受限的連續(xù)信源，當信源為高斯分布時有最大熵。當非高斯連續(xù)信源與高斯信源具有相同平均功率時，那么非高斯信源的熵一定小于高斯信源的熵。當非高斯連續(xù)信源與高斯信源具有相同熵時，那么非高斯信源的平均功率一定大于高斯信源的功率。1.定義 若平均功率為N的非高斯信源與平均功率為 的高斯信源的熵相同，則稱 為該

27、非高斯信源的熵功率。2022/9/164第64頁，共118頁，2022年，5月20日，1點21分，星期一高斯信源的熵為H，功率為非高斯信源的熵為H，功率為N因此結(jié)論：熵功率永遠小于信源的真正功率。2022/9/165第65頁，共118頁，2022年，5月20日，1點21分，星期一2.表達式 (1) 若非高斯信源的熵為H（單位為nat），熵功率功率為 則 因此(2) 若H的單位為bit，則(3) 若H的單位為Hartley，則2022/9/166第66頁，共118頁，2022年，5月20日，1點21分，星期一2.4.4 連續(xù)信源的共熵與條件熵離散信源的共熵和條件熵同離散信源相似，連續(xù)信源也可定義

28、其共熵和條件熵 2022/9/167第67頁，共118頁，2022年，5月20日，1點21分，星期一關(guān)于離散信源獨立熵、共熵和條件熵的幾個關(guān)系式，對于連續(xù)信源仍然成立。H(x,y)=H(x)+H(y|x)= H(y)+H(x|y)H(x,y) H(x)+H(y)H(y|x) H(y) H(x|y) H(x)2022/9/168第68頁，共118頁，2022年，5月20日，1點21分，星期一2.5 熵速率和信道容量2022/9/169第69頁，共118頁，2022年，5月20日，1點21分，星期一2.5.1 信源熵速率1.定義：信源在單位時間內(nèi)輸出的平均信息量稱為信源的熵速率，也稱為信息速率。2

29、.離散信源的熵速率 若離散信源的熵為H(x)，符號速率為n，則其熵速率為H(x)=nH(x)3.連續(xù)信源的熵速率 假設(shè)連續(xù)信源的熵為H(x)，帶寬為W。 由采樣定理可知，當采樣頻率fs2W時，可由各采樣值無失真地恢復(fù)出原始信號，因此H(x)=2WH(x)2022/9/170第70頁，共118頁，2022年，5月20日，1點21分，星期一2.5.2 信道容量1.定義：所謂信道容量是指信道對信源一切可能的概率分布而言，能夠傳送的最大熵速率，即最大接收熵速率。無噪聲信道：C=Hmax(x)有噪聲信道：C C ，就不可能有象R C那樣的編碼方法。2022/9/198第98頁，共118頁，2022年，5

30、月20日，1點21分，星期一2.8.2 信源最佳化 傳輸效率無噪聲信道提高 ，就要使H最大化符號獨立化，解除符號間的相關(guān)性各符號概率均勻化信源最佳化2022/9/199第99頁，共118頁，2022年，5月20日，1點21分，星期一1.弱記憶信源（弱相關(guān)信源）如果信源的符號序列中，只有相鄰的少數(shù)幾個符號之間有統(tǒng)計相關(guān)性，而相距較遠的符號之間的統(tǒng)計相關(guān)性可以忽略不計，這種信源稱為弱記憶信源或弱相關(guān)信源。對于這種信源，我們可以把相關(guān)性較強的幾個相鄰符號看作一個大符號。于是這些大符號之間的相關(guān)性就小的多了。這種方法通常稱為延長法或合并法。2.8.3 符號獨立化2022/9/1100第100頁，共11

31、8頁，2022年，5月20日，1點21分，星期一2.強記憶信源（強相關(guān)信源）如果信源序列具有很強的相關(guān)性，以致于根據(jù)其中一部分符號就可以推測出其余的符號，這種信源稱為強記憶信源或強相關(guān)信源。對于這種信源，那些可以被推知（或預(yù)測）的符號就無需傳送。一般來說，難以完全精確的預(yù)測，而只能根據(jù)信源的統(tǒng)計特性作近似地預(yù)測。這時，我們不必傳輸序列本身，而只需傳送序列的實際值與預(yù)測值之差。這種方法通常稱為預(yù)測法。預(yù)測法應(yīng)用的典型例子就是增量調(diào)制和差分編碼調(diào)制。2022/9/1101第101頁，共118頁，2022年，5月20日，1點21分，星期一X=原始信源符號集；A=信道碼元符號集；W=輸出碼字（碼組）集

32、。2.8.4 概率均勻化最佳編碼1.編碼的基本知識(1)編碼器編碼器的作用：用A中的元素構(gòu)成各個碼字建立X與W的對應(yīng)關(guān)系2022/9/1102第102頁，共118頁，2022年，5月20日，1點21分，星期一(2) 幾個基本概念D元代碼若碼元符號集A中有D種元素（碼元），則該代碼稱為D元代碼。同價代碼若各碼元長度相同（占用時間相同），則該代碼稱為同價代碼。等長代碼若任一碼字都有同樣多個碼元構(gòu)成，則該代碼稱為等長代碼。例如， 00，01，10，11 等長代碼 0，10，110，111 非等長代碼 2022/9/1103第103頁，共118頁，2022年，5月20日，1點21分，星期一單義代碼若任

33、意一個有限長的碼字序列，只能唯一地分割成一個個碼字，則稱該代碼為單義代碼。例如， 0，10，110，111 單義代碼 0 0 1 0 1 0 1 1 0 0 0，10，110，010 非單義代碼 0 0 1 0 1 0 1 1 0 0 0 0 1 0 1 0 1 1 0 0 非續(xù)長代碼若任一個碼字都不是另一個碼字的續(xù)長，則稱該代碼為非續(xù)長代碼。例如， 0，10，110，111 非續(xù)長代碼 0，10，110，010 續(xù)長代碼|2022/9/1104第104頁，共118頁，2022年，5月20日，1點21分，星期一非續(xù)長代碼與單義代碼的關(guān)系例如， 0，10，110，111 是非續(xù)長代碼，也是單義代

34、碼。 0，01 是單義代碼，但不是非續(xù)長代碼。 0 0 0 1 0 0 0 1 0非續(xù)長代碼一定是單義的，但單義代碼不一定是非續(xù)長的。|2022/9/1105第105頁，共118頁，2022年，5月20日，1點21分，星期一單義代碼存在定理 設(shè)碼元符號集為A:a1,a2,aD，碼字集合為W:W1,W2,Wm，其碼長分別為n1,n2,nm；則單義代碼存在的充要條件為碼長組合滿足Kraft不等式，即Kraft不等式同時也是非續(xù)長代碼存在的充要條件；滿足Kraft不等式的碼長組合一定能構(gòu)成單義碼，單義碼的碼長組合一定滿足Kraft不等式；有些碼字的碼長組合滿足Kraft不等式，但不是單義碼。（編碼方

35、法不對） 2022/9/1106第106頁，共118頁，2022年，5月20日，1點21分，星期一【例】A=a1,a2,W=W1,W2,W3,W4,若各個碼字的碼長分別為n1=1,n2=n3=2,n4=3。問是否存在單義代碼？若n1=1,n2=2, n3=n4=3呢？解：(1) D=2，當n1=1,n2=n3=2,n4=3時 因此不存在單義代碼 (2) 當n1=1,n2=2, n3=n4=3時 因此存在單義代碼2022/9/1107第107頁，共118頁，2022年，5月20日，1點21分，星期一(3) 二元非續(xù)長代碼的構(gòu)成方法例如，A=0,1,W=W1,W2,W3,W4,各個碼字的碼長分別為

36、n1=1,n2=2, n3=n4=3 。“樹圖” W1=0 W2=10 W3=110 W4=111樹圖也可以用來解碼，如 1 0 0 1 1 0 0 1 0非續(xù)長碼：從頂點到任一碼字都不能經(jīng)過其他的碼字|根01W101W201W3W42022/9/1108第108頁，共118頁，2022年，5月20日，1點21分，星期一2.最佳編碼法（信源編碼，有效性編碼）例： X： A B C D P(X): 1/2 1/4 1/8 1/8 編碼1：A:00 ，B:01 ，C:10 ，D:11 碼長 L=2 碼元/符號 原始信源符號熵 H(S)=1.75 bit/符號 信道碼元熵 H(A)= H(S)/L=

37、0.875 bit/碼元 編碼效率 = R/C=H(A)/ H(A)max=0.875/1=87.5%2022/9/1109第109頁，共118頁，2022年，5月20日，1點21分，星期一編碼2：A:0 ，B:10 ，C:110 ，D:111平均碼長 =10.5+20.25+30.25=1.75 碼元/符號原始信源符號熵 H(S)=1.75 bit/符號信道碼元熵 H(A)= H(S)/ =1 bit/碼元編碼效率 = H(A)/ H(A)max=1/1=100%信源編碼的基本思想： 根據(jù)給定的消息概率，編碼成二元非續(xù)長代碼：消息概率大，編成的代碼短；消息概率小，編成的代碼長，從而減小平均碼

38、長，增大信道碼元熵，提高傳輸效率。2022/9/1110第110頁，共118頁，2022年，5月20日，1點21分，星期一(1)Shannon-Fano編碼法步驟：把原始信源的符號按概率從大到小重新排列；把信源符號按盡可能概率相等分為2組，分別分配給“0”和“1”碼元；將每個分組再次分組，直至分完；從左至右將分得的碼元排列即得碼字Wi。【例】假設(shè)有一個離散的獨立信源，可以輸出8個獨立的消息。其信源空間如下：X:ABCDEFGHP(X):0.10.180.40.050.060.10.070.042022/9/1111第111頁，共118頁，2022年，5月20日，1點21分，星期一等長編碼：A：

39、000 B：001 C：010 D：011E：100 F：101 G：110 H：111碼長為：L=3 碼元/符號原始信源的符號熵為： H(X)=-p(x)logp(x)=2.55 bit/符號信道碼元熵為： H(A)=H(X)/L= 2.55/3=0.85 bit/碼元編碼效率為 =R/C=H(A)/Hmax(A)=0.85/1=85%2022/9/1112第112頁，共118頁，2022年，5月20日，1點21分，星期一Shannon-Fano編碼：1st2nd3rd4thWiLiC0.4000002B0.1801012A0.101001003F0.101011013G0.07110011004E0.0611