信息論總復(fù)習(xí)

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

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

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

(2)試計(jì)算

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

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

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

(2)求信源的熵H∞。

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

并與H∞進(jìn)行比較。

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

當(dāng)p=0和p=1時(shí)結(jié)果又如何。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的符號(hào)集為{0,1,2}。

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

(2)求信源的熵H∞。

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

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

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

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

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

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

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

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

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

離散無(wú)記憶信源輸出n個(gè)不同的信息符號(hào)，當(dāng)且僅當(dāng)各個(gè)符號(hào)出現(xiàn)概率相等時(shí)(即

)，熵最大，即

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

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

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

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

狀態(tài)轉(zhuǎn)移圖見(jiàn)右圖所示。解：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)和相應(yīng)的一步轉(zhuǎn)移概率構(gòu)成的2階馬爾可夫信源模型為求出穩(wěn)定狀態(tài)下的p(ej)

，稱為狀態(tài)極限概率。將一步轉(zhuǎn)移概率代入上式得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計(jì)算極限熵第六節(jié)馬爾可夫信源例：一個(gè)二元二階馬爾可夫信源，信源符號(hào)集A={0,1}。信源開(kāi)始時(shí)，它以概率p(0)=p(1)=0.5發(fā)出隨機(jī)變量X1。然后，下一單位時(shí)間輸出的隨機(jī)變量X2與X1有依賴關(guān)系，由條件概率p(x2|x1)表示：

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

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

因此得：

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

我們可以壓縮剩余度來(lái)壓縮信源，提高通信的有效性。第三章離散信道及其信道容量[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)一般單符號(hào)離散信道的傳遞概率可以用矩陣表示信道轉(zhuǎn)移概率矩陣只要已知某一個(gè)信源符號(hào)的先驗(yàn)概率及相應(yīng)的轉(zhuǎn)移概率，就可以得到相應(yīng)的交互信息量。交互信息量

一個(gè)二元信道，p(M)=p(S)=1/2，求互信息量I(xi,yj)。利用先驗(yàn)概率和轉(zhuǎn)移概率求出后驗(yàn)概率；可得：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)因?yàn)镠(X)表示傳輸前信源的不確定性，而H(X/Y)表示收到一個(gè)符號(hào)后，對(duì)信源尚存的不確定性，所以二者之差表示信道傳遞的信息量?；バ畔⑴c其他的熵之間的關(guān)系：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的條件下關(guān)于Y的不確定性之差，也等于發(fā)送前后關(guān)于Y的不確定性之差。

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

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

H(X)H(Y)I(X,Y)聯(lián)合熵等于兩圓之和減去重疊部分，也等于一個(gè)圓加上另外一部分.圖1例子已知一個(gè)二元信源連接一個(gè)二元信道，如圖。求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ào)，

H(Y)=0.98bit/符號(hào)

H(XY)=1.43bit/符號(hào)

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

H(X/Y)=0.45bit/符號(hào)

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

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

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

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

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

I（X;Z）

I（X;Y）

（3.163）

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

（3.164）2、串行信道

【例】?jī)蓚€(gè)離散信道，信道矩陣分別為P1、P2，將它們串行連接使用，計(jì)算總信道的信道矩陣。

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

=

相對(duì)信道剩余度

=

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

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

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

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

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

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

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

變長(zhǎng)唯一可譯碼判別方法步驟：1.構(gòu)造F1

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

中的元素。2.構(gòu)造：將C

與比較。如果C

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

中碼字的前綴，也將相應(yīng)的后綴放入中。3.檢驗(yàn)：

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

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

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

F1

F2

F3

F4

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

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

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

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

。取小區(qū)間內(nèi)的一個(gè)點(diǎn)代表該序列，以該點(diǎn)數(shù)值的二進(jìn)制小數(shù)表示該序列，取小數(shù)點(diǎn)后l位，若后面有尾數(shù)，就進(jìn)位到第l位，得到的碼字C，碼字長(zhǎng)度為舉例算術(shù)編碼例：設(shè)二元無(wú)記憶信源S={0,1}，其P(0)=1/4，P(1)=3/4。對(duì)二元序列11111100做算術(shù)編碼。解：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é)錯(cuò)誤概率與譯碼規(guī)則第二節(jié)錯(cuò)誤概率與編碼方法第四節(jié)有噪信道編碼定理第五節(jié)聯(lián)合信源信道編碼定理第六節(jié)糾錯(cuò)編碼的基本思想

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

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

最大后驗(yàn)概率譯碼規(guī)則(最小錯(cuò)誤概率準(zhǔn)則)6.1錯(cuò)誤概率與譯碼規(guī)則求最佳的譯碼規(guī)則例

設(shè)信道矩陣為，且輸入符號(hào)等概分布，即，求最佳的譯碼規(guī)則和平均錯(cuò)誤概率。6.1錯(cuò)誤概率與譯碼規(guī)則解：因?yàn)檩斎敕?hào)為等概分布，所以由最大似然譯碼規(guī)則可得譯碼規(guī)則6.1錯(cuò)誤概率與譯碼規(guī)則譯碼規(guī)則A譯碼規(guī)則B假設(shè)輸入等概，求以下譯碼規(guī)則的平均錯(cuò)誤譯碼概率。計(jì)算PE例PE=0.6PE=0.6676.1錯(cuò)誤概率與譯碼規(guī)則

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

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

如一個(gè)離散無(wú)記憶信道，信道容量為C。當(dāng)信息傳輸率R≤C時(shí)，只要碼長(zhǎng)足夠長(zhǎng)，總可以在輸入符號(hào)集中找到M個(gè)碼字組成的一組碼和相應(yīng)的譯碼準(zhǔn)則，使信道輸出端的平均錯(cuò)誤譯碼概率達(dá)到任意小。注：信息傳輸速率2、有噪信道編碼逆定理

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

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

設(shè)碼字為C1,C2,C3為信息元，C4,C5

,C6

,C7為監(jiān)督元，每個(gè)碼元取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個(gè)碼字如右表。(7,3)線性分組碼

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

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

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

+1線性分組碼的糾、檢