信息論總復習

2023/2/31作業(yè)題52.13.(1)為了使電視圖像獲得良好的清晰度和規(guī)定的適當?shù)膶Ρ榷?，需要?×105個象素和10個不同亮度電平，求傳遞此圖像所需的信息率（比特/秒）。并設每秒要傳送30幀圖像，所有象素是獨立變化的，且所有亮度電平等概率出現(xiàn)？

(2)設某彩色電視系統(tǒng)，除了滿足對于黑白電視系統(tǒng)的上述要求外，還必須有30個不同的色彩度，試證明傳輸該彩色系統(tǒng)的信息率要比黑白系統(tǒng)的信息率約大2.5倍？2023/2/32作業(yè)題5解答.(1)每個象素亮度信源的概率空間為每個象素亮度含有的信息量每幀圖像信源就是離散亮度信源的無記憶N次擴展信源，可得每幀圖像含有的信息量為每秒30幀，則傳遞此圖像所需的信息率為2023/2/33作業(yè)題5解答.(2)色彩度信源的概率空間為每個色彩度含有的信息量亮度和色彩度是獨立同時出現(xiàn)的，每個象素含有的信息量為在每幀所用象素數(shù)和每秒傳送幀數(shù)相同時，信息率之比為2023/2/34作業(yè)題62.18.設有一個信源，它產(chǎn)生0,1序列的信息。它在任意時間而且不論以前發(fā)生過什么符號，均按P(0)=0.4，P(1)=0.6的概率發(fā)出符號。

(1)試問這個信源是否是平穩(wěn)的？

(2)試計算

(3)試計算H(x4)并寫出x4信源中可能有的所有符號。2023/2/35作業(yè)題6解答：(1)信源發(fā)出符號的概率分布與時間平移無關，而且信源發(fā)出的序列之間也是彼此無依賴的，因此該信源是平穩(wěn)的，而且是離散無記憶信源。

(2)2023/2/36作業(yè)題6(3)2023/2/37作業(yè)題72.22.一階馬爾可夫信源的狀態(tài)圖如圖2.8所示。信源X的符號集為{0,1,2}。

(1)求信源平穩(wěn)后的概率分布P(0),P(1),P(2)；

(2)求信源的熵H∞。

(3)近似認為此信源為無記憶時，符號的概率分布為平穩(wěn)分布，求近似信源的熵H(X),

并與H∞進行比較。

(4)對一階馬爾可夫信源p取何值時H∞最大，

當p=0和p=1時結果又如何。2023/2/38作業(yè)題72023/2/39作業(yè)題72023/2/310作業(yè)題72023/2/311作業(yè)題72023/2/312作業(yè)題82.23.一階馬爾可夫信源的狀態(tài)圖如圖2.9所示。信源X的符號集為{0,1,2}。

(1)求平穩(wěn)后信源的概率分布；

(2)求信源的熵H∞。

(3)求當p=0和p=1時信源的熵，并說明理由。2023/2/313作業(yè)題82023/2/314作業(yè)題82023/2/315作業(yè)題92.25.一黑白氣象傳真圖的消息只有黑色和白色兩種，即信源X={黑,白}。設黑色出現(xiàn)的概率為P(黑)=0.3，白色的出現(xiàn)概率P(白)=0.7。

(1)假設圖上黑白消息出現(xiàn)前后沒有關聯(lián)，求熵H(X)；

(2)假設消息前后有關聯(lián)，其依賴關系為P(白/白)=0.9，P(黑/白)=0.1，P(白/黑)=0.2，P(黑/黑)=0.8，求此一階馬爾可夫信源的熵H2(X)；

(3)分別求上述兩種信源的剩余度，比較和的大小，并說明其物理意義。2023/2/316作業(yè)題92023/2/317作業(yè)題9(2)2023/2/318作業(yè)題9(3)Ch3

習題13.1.設信源通過一干擾信道，接收符號為Y=[y1,y2],信道傳遞概率如下圖所示。求①信源X中事件x1和x2分別含有的信息量。②收到消息yj(j=1,2)后，獲得的關于xi(i=1,2)的信息量。③信源X和信源Y的信息熵。④信道疑義度H(X/Y)和噪聲熵H(Y/X)。⑤接收到消息Y后獲得的平均互信息。習題1解答：互信息可以為正值也可以為負值，負值表明由于噪聲的存在，接收到一個消息后，對另一個消息是否出現(xiàn)的不確定性反而增加了。習題1解答：習題23.3.設二元對稱信道的傳遞概率為①若P(0)=3/4,P(1)=1/4,求H(X),H(X/Y),H(Y/X)和I(X;Y)。②求該信道的信道容量及達到信道容量時的輸入概率分布。習題2習題33.9.有一個二元對稱信道，其信道矩陣如下圖所示。設該信道以1500個二元符號/秒的速度傳輸輸入符號?，F(xiàn)有一消息序列共有14000個二元符號，并設在這消息中P(0)=P(1)=1/2。問從信息傳輸?shù)慕嵌葋砜紤]，10秒鐘內(nèi)能否將這消息序列無失真地傳送完？習題3解答：消息是一個二元序列，且為等概率分布，即P(0)=P(1)=1/2，故信源的熵為H(X)=1(bit/symbol)。則該消息序列含有的信息量＝14000(bit/symbol)。下面計算該二元對稱信道能傳輸?shù)淖畲蟮男畔鬏斔俾剩盒诺纻鬟f矩陣為：信道容量（最大信息傳輸率）為：

C=1-H(P)=1-H(0.98)≈0.8586bit/symbol重要知識點自信息的定義根據(jù)上述條件可以從數(shù)學上證明這種函數(shù)形式是對數(shù)函數(shù)，即：自信息的含義當事件發(fā)生前，表示事件（符號、消息）發(fā)生的不確定性當事件發(fā)生后，表示該事件所提供的信息量．例：求離散信源的自信息量

一次擲兩個色子，作為一個離散信源，求下列事件產(chǎn)生后提供的信息量：a.僅有一個為3；

b.至少有一個為4；c.兩個之和為偶數(shù)。解：一個色子有6個符號，兩個色子的總數(shù)（信源消息數(shù)）為36。

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)。離散信源數(shù)學模型離散型的概率空間集合X中，包含該信源所有可能輸出的消息，集合P中包含對應消息的概率，各個消息的輸出概率總和應該為1。信息熵的定義對消息的自信息取統(tǒng)計平均信息熵：信源一個消息狀態(tài)所具有的平均信息量。信息熵的含義信源的平均不確定性信源每個符號所攜帶的平均信息量H(X)表示隨機變量X的隨機性在無噪聲條件下，接受者收到一個消息所獲得的平均信息量二元信源X，其概率空間H(X)01/21p例32-3熵函數(shù)的性質離散隨機變量X的概率空間為記pi=p(xi)，則

由于概率的完備性，即，所以實際上是元函數(shù)。熵函數(shù)的數(shù)學特性包括:(1)對稱性（9）可加性(2)確定性(3)非負性(4)擴展性(5)連續(xù)性(6)遞增性(7)極值性(8)上凸性（7）極值性（最大離散熵定理）定理：

離散無記憶信源輸出n個不同的信息符號，當且僅當各個符號出現(xiàn)概率相等時(即

)，熵最大，即

概率的基本關系當X，Y獨立時，有p(x,y)=p(x)p(y)。概率的基本關系3.聯(lián)合熵和條件熵定義2.4隨機變量X和Y的聯(lián)合分布為p(xiyj)，則這兩個隨機變量的聯(lián)合熵定義為：

聯(lián)合熵表示對于二維隨機變量的平均不確定性。3.聯(lián)合熵和條件熵（續(xù)1）定義2.5隨機變量X和Y的條件熵定義為：條件熵表示已知一個隨機變量時，對另一個隨機變量的平均不確定性。各種熵之間的關系

H(XY)=H(X)+H(Y|X)=H(Y)+H(X|Y)H(X|Y)H(X)，H(Y|X)H(Y)H(XY)H(X)+H(Y)

若X與Y統(tǒng)計獨立，則H(XY)=H(X)+H(Y)例:離散無記憶信源的N次擴展信源離散無記憶信源為：X:{a1,a2,a3};P(X):{1/4,1/2,1/4}2次擴展信源為：:{A1…A9}信源的9個符號為：A1=a1a1A2=a1a2A3=a1a3A4=a2a1A5=a2a2A6=a2a3A7=a3a1A8=a3a2A9=a3a3第四節(jié)離散無記憶的擴展信源第四節(jié)離散無記憶的擴展信源其概率關系為:A1A2A3A4A5A6A7A8A91/161/81/161/81/41/81/161/81/16計算可知[例2-15]設某二維離散信源的原始信源的信源空間X={x1,x2,x3};P(X)={1/4,1/4,1/2},一維條件概率為：p(x1/x1)=1/2;p(x2/x1)=1/2;p(x3/x1)=0;p(x1/x2)=1/8;p(x2/x2)=3/4;p(x3/x2)=1/8;p(x1/x3)=0;p(x2/x3)=1/4;p(x3/x3)=3/4;原始信源的熵為：H(X)=1.5bit/符號條件熵：H(X2/X1)=1.4bit/符號可見：H(X2/X1)<H(X)二維信源的熵：H(X1,X2)=H(X1)+H(X2/X1)=2.9bit/每個信源符號提供的平均信息量為：H2(X1,X2)=H(X1,X2)/2=1.45bit/符號。第五節(jié)離散平穩(wěn)信源第六節(jié)馬爾可夫信源定義為各狀態(tài)的極限概率，則時齊、遍歷的馬爾可夫信源的熵為狀態(tài)轉移圖為不可約閉集，即對任意兩個狀態(tài)，總可以從一個狀態(tài)經(jīng)過有限步數(shù)轉移到另一個狀態(tài)；具有非周期性，從一個狀態(tài)到另一個狀態(tài)的步數(shù)不能具有周期性(3)舉例[例2.2.4]

二元2階馬爾可夫信源，原始信號X的符號集為{X1=0,X2=1}，其狀態(tài)空間共有nm=22=4個不同的狀態(tài)E：{e1=00,e2=01,e3=10,e4=11}

狀態(tài)轉移圖見右圖所示。解：p(e1/e1)=p(0/00)=0.8

p(e2/e1)=p(1/00)=0.2p(e3/e2)=p(0/01)=0.5p(e4/e2)=p(1/01)=0.5p(e1/e3)=p(0/10)=0.5p(e2/e3)=p(1/10)=0.5p(e3/e4)=p(0/11)=0.2p(e4/e4)=p(1/11)=0.8由二元信源X∈{0,1}得到的狀態(tài)空間(e1,e2,e3,e4)和相應的一步轉移概率構成的2階馬爾可夫信源模型為求出穩(wěn)定狀態(tài)下的p(ej)

，稱為狀態(tài)極限概率。將一步轉移概率代入上式得p(e1)=0.8p(e1)+0.5p(e3)p(e2)=0.2p(e1)+0.5p(e3)p(e3)=0.5p(e2)+0.2p(e4)p(e4)=0.5p(e2)+0.8p(e4)解方程組得p(e1)=p(e4)=5/14p(e2)=p(e3)=2/14計算極限熵第六節(jié)馬爾可夫信源例：一個二元二階馬爾可夫信源，信源符號集A={0,1}。信源開始時，它以概率p(0)=p(1)=0.5發(fā)出隨機變量X1。然后，下一單位時間輸出的隨機變量X2與X1有依賴關系，由條件概率p(x2|x1)表示：

再下一單元時間輸出隨機變量X3，而X3依賴于前面變量。依賴關系由條件概率p(x3|x1x2)表示：x1x1x20100.30.410.70.6第六節(jié)馬爾可夫信源由從第四單位時間開始，任意時刻信源發(fā)出的隨機變量Xi只與前面二個單位時間的隨機變量有關，根據(jù)題意可得信源的狀態(tài)轉移圖：x1x2x1x2x1x2x1x2X30001101100.40.20.30.410.60.80.70.6第六節(jié)馬爾可夫信源0.50.50.40.80.30.60.20.70.60.4第六節(jié)馬爾可夫信源解得：

＝0.8956當馬爾可夫信源達到穩(wěn)定后，符號0和1的分布概率可根據(jù)下式計算

因此得：

關于離散信源熵的總結實際信源非平穩(wěn)的有記憶隨機序列信源，其極限熵是不存在的；解決的方法是假設其為離散平穩(wěn)隨機序列信源，極限熵存在，但求困難；進一步假設其為m階Markov信源，用其極限熵Hm+1近似；再進一步假設為一階Markov信源，用其極限熵H1+1(X2/X1)來近似；最簡化的信源是離散無記憶信源，其熵為H(x)=H1(X);最后可以假定為等概的離散無記憶信源，其熵為H0(X)=logq第七節(jié)信源剩余度與自然語言的熵2、熵的相對率3、信源剩余度英文字母信源H0=log27=4.76bit(等概)H1=4.02bit（不等概）H1+1=3.32bit（一階M-信源）H2+1=3.1bit（二階M-信源）H∞=1.4bit第七節(jié)信源剩余度與自然語言的熵4、中文的剩余度

我們可以壓縮剩余度來壓縮信源，提高通信的有效性。第三章離散信道及其信道容量[P]=y1y2…ymx1p(y1/x1)p(y2/x1)…p(ym/x1)x2p(y1/x2)p(y2/x2)…p(ym/x2)……………xnp(y1/xn)p(y2/xn)…p(ym/xn)一般單符號離散信道的傳遞概率可以用矩陣表示信道轉移概率矩陣只要已知某一個信源符號的先驗概率及相應的轉移概率，就可以得到相應的交互信息量。交互信息量

一個二元信道，p(M)=p(S)=1/2，求互信息量I(xi,yj)。利用先驗概率和轉移概率求出后驗概率；可得：p(xi=M/yj=M)=5/8;p(xi=S/yj=M)=3/8;p(xi=S/yj=S)=3/4;p(xi=M/yj=S)=1/4;可分別求出互信息量I(xi,yj)=log(p(xi/yj)/p(xi))I(M,M)=0.322bit;p(xi=M/yj=M)=5/8>p(xi=M)=1/2I(S,S)=0.585bit;p(xi=S/yj=S)=3/4>p(xi=S)=1/2I(S,M)=-0.415bit;p(xi=S/yj=M)=3/8<P(xi=S)=1/2I(M,S)=-1bitp(xi=M/yj=S)=1/4<p(xi=M)=1/22、平均互信息I(X;Y)=H(X)-H(X/Y)因為H(X)表示傳輸前信源的不確定性，而H(X/Y)表示收到一個符號后，對信源尚存的不確定性，所以二者之差表示信道傳遞的信息量?；バ畔⑴c其他的熵之間的關系：I(X;Y)=H(X)-H(X/Y)=H(X)+H(Y)-H(XY)=H(Y)-H(Y/X)(3.34)H(XY)=H(X)+H(Y/X)=H(Y)+H(X/Y)I(X;Y)=H(X)-H(X/Y)=H(Y)-H(Y/X)

互信息I(X;Y)也表示輸出端H(Y)的不確定性和已知X的條件下關于Y的不確定性之差，也等于發(fā)送前后關于Y的不確定性之差。

H(X/Y)即信道疑義度，也表示通過有噪信道造成的損失，故也稱為損失熵，因此信源的熵等于收到的信息量加上損失的熵；而H(Y/X)表示已知輸入的情況下，對輸出端還殘留的不確定性，這個不確定性是由噪聲引起的，故也稱之為噪聲熵。互信息與各類熵之間的關系H(X,Y)

H(X/Y)H(Y/X)

H(X)H(Y)I(X,Y)聯(lián)合熵等于兩圓之和減去重疊部分，也等于一個圓加上另外一部分.圖1例子已知一個二元信源連接一個二元信道，如圖。求I(X;Y),H(XY),H(X/Y),(Y/X)。X={x1,x2},[p(xi)]={1/2,1/2}。解：(1)求聯(lián)合概率

p(x1,y1)=0.5×0.98=0.49p(x1,y2)=0.5×0.02=0.01p(x2,y1)=0.5×0.20=0.10p(x2,y2)=0.5×0.80=0.40(2)求p(yj)p(y1)=p(x1,y1)+p(x2,y1)=0.49+0.10=0.59p(y2)=p(x1,y2)+p(x2,y2)=0.01+0.40=0.41（3）求p(xi/yj)：p(x1/y1)=p(x1,y1)/p(y1)=0.831p(x2/y1)=p(x2,y1)/p(y1)=0.169p(x1/y2)=p(x1,y2)/p(y2)=0.024p(x2/y2)=p(x2,y2)/p(y2)=0.976(4)求熵

H(X)=1bit/符號，

H(Y)=0.98bit/符號

H(XY)=1.43bit/符號

I(X;Y)=H(X)+H(Y)-H(X,Y)=0.55bit/符號

H(X/Y)=0.45bit/符號

H(Y/X)=0.43bit/符號信道容量的定義信息傳輸率：

R=I(X,Y)=[H(X)-H(X/Y)]=[H(Y)-H(Y/X)]bit/符號對于每一個確定信道，都有一個信源分布，使得信息傳輸率達到最大值，我們把這個最大值稱為該信道的信道容量。信道容量與與信源無關，它是信道的特征參數(shù)，反應的是信道的最大的信息傳輸能力。

二元對稱信道信道容量二元對稱信道信道容量等于1-H(P)I(X;Y)w1/21-H(P)信道1和信道2串連構成了一個馬爾可夫鏈，有如下定理：X信道1信道2ZY圖馬爾可夫鏈

數(shù)據(jù)處理定理：無論經(jīng)過何種數(shù)據(jù)處理，都不會使信息量增加。定理3.8

若隨即變量X、Y、Z組成一個馬爾可夫鏈，如下圖，則有

I（X;Z）

I（X;Y）

（3.163）

I（X;Z）I（Y;Z）

（3.164）2、串行信道

【例】兩個離散信道，信道矩陣分別為P1、P2，將它們串行連接使用，計算總信道的信道矩陣。

信道剩余度定義為：信道剩余度

=

相對信道剩余度

=

表示信道的實際傳信率和信道容量之差。信道剩余度可以用來衡量信道利用率的高低。第六節(jié)信源與信道的匹配例如，某離散無記憶信源對二元離散信道的信道容量為：C＝1(比特／信道符號)

通過一個無噪無損二元離散信道進行傳輸。信源的信息熵為H(X)＝1.937(比特／信源符號)要使信源在此二元信道中傳輸，必須對X進行二元編碼：因此，必須通過合適的信源編碼，使信道的信息傳輸率接近或等于信道容量。對于碼(比特／信道符號)對于碼(比特／信道符號)即：要能夠盡量用較少的符號表示相同的信息，就可以提高信息的傳輸率，從而提高信道的利用率。

第5章無失真信源編碼（1）提高傳輸效率，用盡可能少的信道傳輸符號來傳遞信源消息，目的是提高傳輸效率，這是信源編碼主要應考慮的問題。這里又分兩種情況討論，即允許接收信號有一定的失真或不允許失真。提高抗干擾能力往往是以降低信息傳輸效率為代價的，而為了提高傳輸效率又往往削弱了其抗干擾能力。理論上已證明：至少存在最佳的編碼或信息處理方法，解決上述矛盾。（2）

增強通信的可靠性如何增加信號的抗干擾能力，提高傳輸?shù)目煽啃?，這是信道編碼主要考慮的問題。解決這一問題，一般是采用冗余編碼法，賦予信碼自身一定的糾錯和檢錯能力，只要采取適當?shù)男诺谰幋a和譯碼措施，就可使信道傳輸?shù)牟铄e概率降到允許的范圍之內(nèi)。Kraft不等式5.5變長碼定理5.4：即時碼存在的充要條件是碼長組合滿足Kraft不等式:唯一可譯碼存在的充要條件是例子

W1:滿足Kraft不等式，但只是唯一可譯碼，不是即時碼；碼長組合為1,2,3,4；W2:滿足Kraft不等式，是唯一可譯碼，也是即時碼；碼長組合為1,2,3,4；

W3:滿足Kraft不等式，不是唯一可譯碼，也不是即時碼；碼長組合為1,2,3,3；W4:滿足Kraft不等式，是唯一可譯碼，也是即時碼；碼長組合為1,2,3,3

W5:不滿足Kraft不等式，不可能為唯一可譯碼；碼長組合為1,2,2,3；W6:滿足Kraft不等式，是唯一可譯碼，也是即時碼；為等長碼

變長唯一可譯碼判別方法步驟：1.構造F1

：考察C中所有碼字，如果一個碼字是另一個碼字的前綴，則將后綴作為F1

中的元素。2.構造：將C

與比較。如果C

中有碼字是中元素的前綴，則將相應的后綴放入中；同樣中若有元素是C

中碼字的前綴，也將相應的后綴放入中。3.檢驗：

1)如果是空集，則斷定碼C是唯一可譯碼，退出循環(huán)；

2)反之，如果中的某個元素與C中的某個元素相同，則斷定碼不是唯一可譯碼，退出循環(huán)。

3)如果上述兩個條件都不滿足，則返回步驟2。5.5變長碼變長唯一可譯碼判別方法C

F1

F2

F3

F4

F5adebdebadcbbcdebcdeadabbbaddebbbcde例：結論：F5中包含了C中的元素，因此該變長碼不是唯一可譯碼。5.5變長碼問題：判斷C={1,10,100,1000}是否是唯一可譯碼？abbcdebad設信源編碼后的碼字為：碼長為：則這個碼的平均長度為：平均每個碼元攜帶的信息量即編碼后的信息傳輸率為：對于給定的信源和碼符號集，若有一個唯一可譯碼，它的平均碼長小于其他唯一可譯碼的長度，則稱此碼為緊致碼或最佳碼，無失真信源編碼的基本問題就是尋找緊致碼。5.6變長信源編碼定理碼符號/信源符號無失真變長信源編碼定理

香農(nóng)第一定理（變長無失真信源編碼定理）：設離散無記憶信源的熵為H(S)，它的N次擴展信源為，對擴展信源進行編碼。總可以找到一種編碼方法，構成唯一可譯碼，使平均碼長滿足：

當時，有5.6變長信源編碼定理定理指出要做到無失真的信源編碼，信源每個符號所需要的平均碼元數(shù)就是信源的熵值，如果小于這個值，則唯一可譯碼不存在，可見，熵是無失真信源編碼的極限值。定理還指出，通過對擴展信源進行編碼，當N趨向于無窮時，平均碼長可以趨進該極限值。無失真變長信源編碼定理5.6變長信源編碼定理bit/信源符號碼符號/信源符號=bit/碼符號信息傳輸率(碼率)r進制單位/信源符號碼符號/信源符號信息傳輸率(碼率)5.6變長信源編碼定理碼的剩余度例子（１）例：S:{s1,s2},P(S):{0.2,0.8},A:{0,1}H(S)=1/5log5+4/5log(5/4)=0.72193bit/信源符號．碼字W:{W1=0,W2=1}．平均碼長:L=0.2×1+0.8×1=1信道碼元符號/信源符號。信道傳信率：R=H(S)/L=0.72193比特/信道碼元符號。5.6變長信源編碼定理例子（２）對二次擴展信源S2進行二元編碼W:{W1,W2,W3,W4}5.6變長信源編碼定理例子（３）平均碼長：L2=(16/25)×1+(4/25)×2+(4/25)×3+(1/25)×3=37/27信道碼元符號/2個信源符號原始信源每個信源符號的平均碼長L=L2/2=37/50信道碼元符號/信源符號信道傳信率為R=H(S)/L=0.72193/(37/50)=0.97比特/信道碼元符號。5.6變長信源編碼定理經(jīng)過信源的二次擴展，編碼復雜一點，但使傳信率（編碼效率）明顯提高。二元編碼的信道容量為1比特/碼元，當擴展次數(shù)增加時，傳信率將無限接近信道容量。5.6變長信源編碼定理8.1霍夫曼碼和其他編碼方法8.2Fano編碼方法8.3香農(nóng)-費諾-埃里斯編碼方法第8章無失真信源編碼Huffman碼將信源符號按概率從大到小的順序排列，令給兩個概率最小的信源符號sn-1和sn各分配一個碼元“0”和“1”，并將這兩個信源符號合并成一個新符號，并用這兩個最小的概率之和作為新符號的概率，結果得到一個只包含(n－1)個信源符號的新信源。稱為信源的第一次縮減信源，用S1表示。將縮減信源S1的符號仍按概率從大到小順序排列，重復步驟2，得到只含(n－2)個符號的縮減信源S2。重復上述步驟，直至縮減信源只剩兩個符號為止，此時所剩兩個符號的概率之和必為1。然后從最后一級縮減信源開始，依編碼路徑向前返回，就得到各信源符號所對應的碼字。編碼步驟如下：霍夫曼碼和其他編碼方法01010101Huffman碼霍夫曼碼和其他編碼方法Huffman碼離散信源如下:解：編碼過程略，Huffman編碼結果如下：霍夫曼碼和其他編碼方法Huffman碼平均碼長為信源熵為編碼效率為霍夫曼碼和其他編碼方法Huffman碼注意：霍夫曼編碼后的碼字不是惟一的。1）每次對縮減信源兩個概率最小的符號分配“0”或“1”碼元是任意的,因此編碼的結果是不唯一的；但0/1分配的上下順序在整個編碼過程中應保持一致，否則不能構成唯一可譯碼。2）縮減信源時，若合并后的概率與其他概率相等，這幾個概率的次序可任意排列，但得到的碼字不相同,對應的碼長也不相同,但平均碼長也不變。霍夫曼碼和其他編碼方法r元Huffman算法

r=3,A:{0,1,2}可知：平均碼長為L=2碼元/信源符號改進方法在6個信源符號的后面再加一個概率為0的符號，記為s7’,同時有p(s7’)=0，這個符號稱為虛假符號。將信源按7個符號進行三元編碼012012012改進方法霍夫曼碼和其他編碼方法算術編碼F(S)(信源符號序列的累積分布函數(shù))將[0,1)分割成許多小區(qū)間[F(s),F(s)+P(s))

。取小區(qū)間內(nèi)的一個點代表該序列，以該點數(shù)值的二進制小數(shù)表示該序列，取小數(shù)點后l位，若后面有尾數(shù)，就進位到第l位，得到的碼字C，碼字長度為舉例算術編碼例：設二元無記憶信源S={0,1}，其P(0)=1/4，P(1)=3/4。對二元序列11111100做算術編碼。解：P(s=11111100)=(3/4)6(1/4)2

F(s)=P(0)+P(1)P(0)+P(1)2P(0)+P(1)3P(0)+P(1)4P(0)+P(1)5P(0)=0.82202=0.110100100111

得C＝0.1101010，從而s的碼字為1101010。編碼效率第六章有噪信道編碼

第一節(jié)錯誤概率與譯碼規(guī)則第二節(jié)錯誤概率與編碼方法第四節(jié)有噪信道編碼定理第五節(jié)聯(lián)合信源信道編碼定理第六節(jié)糾錯編碼的基本思想

兩種重要的譯碼規(guī)則譯碼規(guī)則的選擇準則-----使平均錯誤概率最小最常用的譯碼規(guī)則，包括：

最大似然譯碼規(guī)則

最大后驗概率譯碼規(guī)則(最小錯誤概率準則)6.1錯誤概率與譯碼規(guī)則求最佳的譯碼規(guī)則例

設信道矩陣為，且輸入符號等概分布，即，求最佳的譯碼規(guī)則和平均錯誤概率。6.1錯誤概率與譯碼規(guī)則解：因為輸入符號為等概分布，所以由最大似然譯碼規(guī)則可得譯碼規(guī)則6.1錯誤概率與譯碼規(guī)則譯碼規(guī)則A譯碼規(guī)則B假設輸入等概，求以下譯碼規(guī)則的平均錯誤譯碼概率。計算PE例PE=0.6PE=0.6676.1錯誤概率與譯碼規(guī)則

碼1碼2碼3碼4碼5碼字00011100001110111000000110001000000011011011111010000001010011100101110111消息數(shù)M24448

信息傳輸率R1/32/32/32/51碼的最小距離32131錯誤概率（最大似然譯碼）最小距離譯碼準則的譯碼和編碼在二元對稱信道中，最小距離譯碼準則等價于最大似然譯碼準則，也就是收到一個碼字后，把它譯成與它最近的輸入碼字，這樣可以使平均錯誤率最小應該選擇這樣的編碼方法：應盡量設法使選取的M個碼字中任意兩兩不同碼字的距離盡量大。6.2錯誤概率與編碼方法6.4有噪信道編碼定理1、有噪信道編碼定理（香農(nóng)第二定理）

如一個離散無記憶信道，信道容量為C。當信息傳輸率R≤C時，只要碼長足夠長，總可以在輸入符號集中找到M個碼字組成的一組碼和相應的譯碼準則，使信道輸出端的平均錯誤譯碼概率達到任意小。注：信息傳輸速率2、有噪信道編碼逆定理

如一個離散無記憶信道，信道容量為C。當信息傳輸率R>C（即）時，則無論碼長n多長，總找不到一種編碼使信道輸出端的平均錯誤譯碼概率達到任意小。6.4有噪信道編碼定理定理指出：信道容量是在信道中可靠傳輸信息的最大信息傳輸率。定理是一個存在定理，沒有給出具體的編碼方法，但它有助于指導各種通信系統(tǒng)的設計，有助于評價各種系統(tǒng)及編碼的效率。6.4有噪信道編碼定理糾錯碼的基本思想和漢明碼糾錯編碼<=>信道編碼Ch9信道的糾錯編碼線性分組碼的編碼過程分為兩步：把信息序列以每k個碼元分組，得到信息碼組編碼器按照預定的線性規(guī)則(可由線性方程組規(guī)定)，把信息碼組變換成n長碼字。其中(n－k)個監(jiān)督碼元由k個信息碼元的線性運算產(chǎn)生。信息位k個，有2k個不同的信息碼組，則有2k個碼字與它們一一對應。線性分組碼的編碼過程2、線性分組碼-----編碼過程編碼規(guī)則的矩陣表示：生成矩陣G編碼規(guī)則：線性分組碼的生成矩陣監(jiān)督方程2、線性分組碼-----編碼過程監(jiān)督方程的矩陣表示：線性分組碼的校驗矩陣

一致監(jiān)督矩陣H2、線性分組碼-----編碼過程監(jiān)督元可按下面方程組計算，求一致監(jiān)督矩陣H、生成的碼字及生成矩陣G(7,3)線性分組碼例

設碼字為C1,C2,C3為信息元，C4,C5

,C6

,C7為監(jiān)督元，每個碼元取0或12、線性分組碼-----編碼舉例(7,3)線性分組碼

監(jiān)督方程2、線性分組碼-----編碼舉例信息碼組(101)即C1=1,C2=0,C3=1代入監(jiān)督方程得：C4=0,C5=0,C6=1,C7=1由信息碼組(101)編出的碼字為(1010011)。其它7個碼字如右表。(7,3)線性分組碼

監(jiān)督方程2、線性分組碼-----編碼舉例(7,3)線性分組碼

監(jiān)督方程2、線性分組碼-----編碼舉例令(7,3)線性分組碼

2、線性分組碼-----編碼舉例線性系統(tǒng)碼生成碼字例(7,4)系統(tǒng)線性碼的生成矩陣為則2、線性分組碼-----系統(tǒng)碼系統(tǒng)碼的生成矩陣與校驗矩陣對于系統(tǒng)碼，生成矩陣可以表示為其中為維矩陣，為維單位矩陣。校驗矩陣可以表示為其中為維矩陣，為維單位矩陣，且由監(jiān)督矩陣可直接寫出它的生成矩陣HGT=02、線性分組碼-----系統(tǒng)碼系統(tǒng)碼的生成矩陣與校驗矩陣例已知(7,4)線性系統(tǒng)碼的監(jiān)督矩陣為2、線性分組碼-----系統(tǒng)碼關于碼的最小距離與糾、檢錯能力的關系有以下結論：對于（n，k）線性分組碼，設為最小漢明距離，則ee2e

+1線性分組碼的糾、檢