信息論總結與復習2014-6

信息論與編碼

總結與復習 2014信息學院信息工程教研室牛秋娜本課程主要內容一個理論和三個編碼:

理論--------香農(nóng)信息論編碼--------信源編碼信道編碼保密編碼各編碼作用是？第一部分、信息論基礎1.1信源的信息理論:

1、信息的定義：（1）自信息I=log(1/p)=-logp

（2）通信完成后獲得的凈信息量=通信所消除掉的不確定度（3）信息的單位：對數(shù)的底取2時，自信息的單位叫比特(bit)。第一部分、信息論基礎1.1信源的信息理論2、信息熵的定義：（1）離散信源（2）連續(xù)信源第一部分、信息論基礎1.1信源的信息理論3、信息熵的特點（1）非負性：H(X)≥0（2）極值性：

《1》離散信源各符號等概率時出現(xiàn)極大值：

H0=logm

《2》連續(xù)信源信號幅度受限時均勻分布出現(xiàn)極大值：hmax(X)=log(b-a)；

《3》連續(xù)信源信號方差有限時高斯分布出現(xiàn)極大值：第一部分、信息論基礎1.1信源的信息理論4、離散序列的信息熵（1）無記憶信源的聯(lián)合熵與單符號熵：

H(X1X2……XN)=H(X1)+H(X2)+H(X3)+……+H(XN)=NH(X1)（2）有記憶信源的聯(lián)合熵與條件熵：

H(X1X2……XN)=H(X1)+H(X2|X1)+H(X3|X1X2)+……+H(XN|X1X2……XN-1)（3）平均符號熵：

HN=H(X1X2……XN)/

N第一部分、信息論基礎1.1信源的信息理論（4）序列信息熵的性質：

《1》條件熵不大于無條件熵，強條件熵不大于弱條件熵：H(X1)≥

H(X2|X1)≥

H(X3|X1X2)≥

…

……

≥H(XN|X1X2……XN-1)《2》條件熵不大于同階的平均符號熵:

HN

≥H(XN|X1X2……XN-1)《3》序列越長，平均每個符號的信息熵就越?。?/p>

H1

≥

H2

≥

H3

≥

……

≥HN總之：H0

>

H1

≥

H2

≥

H3

≥

……

≥HN≥H∞

（無記憶信源取等號。）第一部分、信息論基礎1.1信源的信息理論第一部分、信息論基礎1.1信源的信息理論5、馬爾可夫信源的信息熵（1）馬爾可夫信源的數(shù)學模型和定義：

N階馬爾可夫信源的關聯(lián)長度是N+1，N+2以外不關聯(lián)。（2）狀態(tài)、狀態(tài)轉移與穩(wěn)態(tài)概率：狀態(tài)、狀態(tài)轉移、狀態(tài)轉移圖、穩(wěn)定狀態(tài)、穩(wěn)態(tài)方程（3）穩(wěn)態(tài)符號概率：結論：N階馬氏信源穩(wěn)態(tài)信息熵(即極限熵)等于N+1階條件熵。（4）穩(wěn)態(tài)信息熵：[例1]已知二階馬爾可夫信源的條件概率：

p(0|00)=p(1|11)=0.8；p(0|01)=p(1|10)=0.6；求穩(wěn)態(tài)概率、穩(wěn)態(tài)符號概率、穩(wěn)態(tài)符號熵和穩(wěn)態(tài)信息熵。解：二階馬氏信源關聯(lián)長度=3，狀態(tài)由2符號組成，共有

4個狀態(tài)，分別為：E1=00；E2=01；E3=10；E4=11；已知的條件概率即是：

p(0|E1)=p(1|E4

)=0.8；p(0|E2)=p(1|E3

)=0.6；根據(jù)歸一化條件可求出另外4個狀態(tài)符號依賴關系為：

p(1|E1)=p(0|E4

)=0.2；p(1|E2

)=p(0|E3)=0.4；

第一部分、信息論基礎1.1信源的信息理論E4E3E2E10:0.80:0.40:0.21:0.81:0.21:0.41:0.60:0.6穩(wěn)態(tài)方程組是：第一部分、信息論基礎1.1信源的信息理論可解得：穩(wěn)態(tài)符號概率為：穩(wěn)態(tài)信息熵為：=0.895bit/符號第一部分、信息論基礎1.1信源的信息理論因此，穩(wěn)態(tài)符號熵=1bit/符號。第一部分、信息論基礎1.2信道的信息理論1.2信道的信息理論:

1、信道的數(shù)學模型：進入廣義信道的符號為ai∈A；從廣義信道出來的符號bj∈B；其前向概率為pij=p(bj|ai)。傳輸矩陣:第一部分、信息論基礎1.2信道的信息理論

2、信道有關的信息熵：（1）信源熵(先驗熵)：

（2）噪聲熵：（3）聯(lián)合熵：（4）接收符號熵：（5）損失熵(后驗熵)：第一部分、信息論基礎1.2信道的信息理論3.平均互信息計算公式：I(X;Y)=H(X)–H(X|Y)=H(Y)–H(Y|X)=H(X)+H(Y)–H(XY)

I(X;Y)

代表系統(tǒng)每完成收發(fā)一對符號的通信過程后，所消除掉的平均不確定度，即信宿從每個符號中平均所獲得的凈信息量。[例2]已知信源先驗概率p(x)={0.7,0.3}，信道傳輸矩陣；試計算各信息熵和互信息。

H(XY)=-0.21log0.21–0.14log0.14–0.35log0.35–0.12log0.12–0.09log0.09–0.09log0.09=2.3924bit/符號解:(1)先驗熵：

H(X)=-0.7log20.7–0.3log20.3=(-0.7lg0.7–0.3lg0.3)/lg2=0.881bit/符號

(2)聯(lián)合熵：第一部分、信息論基礎1.2信道的信息理論

H(Y|X)=–0.21log0.3–0.14log0.2–0.35log0.5–0.12log0.4–0.09log0.3–0.09log0.3=1.5114bit/符號(4)接收符號熵：由P(Y)=（0.21+0.12，0.14+0.09，0.35+0.09）

=（0.33,0.23,0.44）

H(Y)=-0.33log0.33-0.23log0.23-0.44log0.44=1.5366bit/符號(3)噪聲熵：由和第一部分、信息論基礎1.2信道的信息理論H(X|Y)=-0.21log(7/11)-……0.09log(9/44)=0.8558bit/符號

或：H(X|Y)=H(XY)-H(Y)=2.3924-1.5266=0.8558bit/符號(6)平均互信息：

I(X;Y)=H(X)-H(X|Y)=0.881–0.8558=0.0252bit/符號(5)損失熵：第一部分、信息論基礎1.2信道的信息理論第一部分、信息論基礎1.2信道的信息理論4.信道容量對稱信道：傳輸矩陣的各行都是一些相同元素的重排，各列也是一些相同元素的重排。（1）定義：對于給定的信道，總存在一個信源能使互信息取極大值，該極大值定義為信道的信道容量：信道容量反映了一個信道最大所能傳輸?shù)钠骄バ畔?，是給定信道的屬性。使傳信率等于信道容量的信源，稱為該信道的匹配信源。第一部分、信息論基礎1.2信道的信息理論（2）信道容量的計算：對于簡單信道要求能計算信道容量：1）無損信道：C=max{I(X;Y)}=max{H(X)}=logm；

2）無噪信道：C=max{I(X;Y)}=max{H(Y)}=logS；3）對稱信道：C=max{I(X;Y)}=logS-H(p1,p2,……,pS)；[例3]求對稱信道的信道容量。解：C

=log4-H(0.2,0.3,0.2,0.3)=2+(0.2log0.2+0.3log0.3)×2=0.03bit/符號；第一部分、信息論基礎1.2信道的信息理論（3）波形信道的信道容量：發(fā)送連續(xù)信號的信源是連續(xù)信源，傳輸連續(xù)信號的信道是波形信道。高斯加性噪聲波形信道的容量由Shannon公式給出：

C=Blog(1+PX/Pn

)香農(nóng)公式給出了帶寬B、信道容量和信噪比PX/Pn（注意是線性比值）三者之間的制約關系。信道容量不變

時帶寬與信噪比有互換關系。

第二部分、無失真信源編碼第二部分、無失真信源編碼2.1信源編碼理論1.1信源編碼理論:

1、信源的相對信息率和冗余度：

實際信源由于非等概，有記憶：

信源每個符號最大可以荷載的信息量是

H0=logm

平均每個符號的實際信息荷載量是H∞<HN<H(X)

（1）只要信息熵沒有達到最大值，就存在冗余。（2）定義相對信息率：

μ

=H∞/H

0

第二部分、無失真信源編碼2.1信源編碼理論

2、變長碼編碼原理：（1）概率匹配原則：信息量大(不常出現(xiàn))的符號用長碼，信息量小(經(jīng)常出現(xiàn))的符號用短碼。（2）平均碼長：（4）極限碼長

∞=H∞/logr;（5）編碼效率：（3）Shannon變長碼編碼定理：第二部分、無失真信源編碼2.1信源編碼理論

3、唯一可譯性與即時性：（1）斷字問題：分組編碼的變長碼被連接起來發(fā)送，接收端如何才能將它們分開進行譯碼呢？（2）唯一可譯碼（3）即時碼：異前綴碼（或非延長碼）（4）構造碼樹的方法（5）克拉夫特不等式：唯一可譯碼的必要條件。[例5]以下哪些編碼一定不是惟一可譯碼？寫出每種編碼克拉夫特不等式的計算結果。碼A：0，10，11，101；碼B：1，01，001，0001；碼C：0，10，110，1110，111110；解：碼A：1/2+1/4+1/4+1/8>1，不能唯一可譯；碼B：

1/2+1/4+1/8+1/16<1,有可能唯一可譯；碼C：1/2+1/4+1/8+1/16+1/64<1，有可能唯一可譯；第二部分、無失真信源編碼2.1信源編碼理論第二部分、無失真信源編碼2.2編碼方法1.2編碼方法:

1、Huffman編碼：

（1）信源符號按概率大小排隊。

（2）合并概率最小的兩個符合為一個節(jié)點。

（3）節(jié)點參與排隊放在與自己概率相等符號后面。（4）重復這個過程直到合并完全部符號。

（5）標記每個分支的的0與1。（6）從根到葉的路徑就給出了相應符號的碼字。（7）計算平均碼長與編碼效率。

2、Huffman編碼的推廣：

擴展信源編碼；多元編碼[例6]設信源概率空間為，

編碼符號集為Y={0,1}，進行Huffman編碼（要求碼長發(fā)差最?。?。解：編碼為：

s1(10)，s2(11)，s3(010)，s4(011)，s5(0000)，s6(0001)，s7(0010)，s8(0011)

平均碼長：l=2.75H(X)=2.75bit/符號，η=100%

第二部分、無失真信源編碼2.2編碼方法第二部分、無失真信源編碼2.2編碼方法3、游程編碼適用于連0連1情況。等熵變換，沒有直接壓縮代碼，但將二元碼變成了多元碼。為使用Huffman編碼創(chuàng)造了條件。與MH編碼結合即傳真編碼。4、詞典編碼不依賴于概率的通用編碼。建立初始小詞典后邊輸入邊查詞典邊補充新詞條，以詞條序號為編碼。第三部分、信道編碼3.1信道編碼理論第三部分、信道編碼3.1信道編碼理論:

1、檢錯與糾錯原理：

（1）檢錯原理：添加冗余避免碼字非此即彼；

（2）糾錯原理：添加冗余拉大碼字漢明間距；

（3）漢明距離：兩碼字不同碼元的個數(shù)；（4）檢錯能力：d0≥e+1

糾錯能力：d0≥2t+1

糾檢同時：d0≥e+t+1(e>t)2、譯碼規(guī)則與錯誤概率：（1）最小錯誤準則：選聯(lián)合概率矩陣每列最大元素（2）最大似然準則：選傳輸概率矩陣每列最大元素（3）錯誤概率計算：未選中元素的總聯(lián)合概率（4）差錯率計算

（5）漏檢率計算3、幾種簡單的信道編碼：（1）重復碼（2）奇偶校驗碼（3）恒比碼第三部分、信道編碼3.1信道編碼理論3.2線性分組碼:

碼長為n，信息位為k，記作（n,k）；

監(jiān)督位r

＝n-k1、編碼

C=K?G

生成矩陣G是k×

n的矩陣。左半邊是k×k單位信息位方陣Ik右半邊是k×r的監(jiān)督位矩陣Q第三部分、信道編碼3.2線性分組碼2、糾錯和譯碼H一致校驗矩陣左半邊是r×k矩陣P右半邊是r×r單位方陣Ir；P與生成矩陣中的Q互為轉置關系：P=QT

監(jiān)督方程也可表示為：

C·HT

=0；滿足此方程的均為正確的許用碼字，否則，便是誤碼。第三部分、信道編碼3.2線性分組碼N維錯誤格式矢量

E

發(fā)送碼字為C，接收碼字為R

，三者的關系是：

E=CR；

R=C

E；

C=R

E；伴隨子向量S=R·HTS=R·HT=(C

E)·HT=C·HT

E·HT

=E·HT；若R=C，E為全零向量，則S=0；反之，若R≠C，則E≠0，導致S≠0；因此由伴隨子向量S是否為零就能檢查出接收碼R是否有誤。

第三部分、信道編碼3.2線性分組碼糾錯：R錯一位的情況：S與HT的哪一行相同，就表明錯在哪一位。

R錯兩位以上：查表法，查R-C對照來譯碼。3、糾錯能力不等式：

2

r

≥Cn0+Cn1+Cn2+……+Cnt

完備碼：上式取等號的情況。漢明碼：糾1位錯的完備碼，2r

=1+n第三部分、信道編碼3.2線性分組碼3.3、循環(huán)碼1.碼多項式2.生成多項式——碼多項式中那個次數(shù)最低的非零多項式g(x)

第三部分、信道編碼3.3循環(huán)碼n-k=r次；常數(shù)項為1。任意碼多項式都是生成多項式g(x)的倍式。g(x)是xn-1的一個因式。3.編碼確定編碼的n、k、r

值；寫出給定信息位多項式：K(x)；左移r位：xr·k(x)計算監(jiān)督位多項式：

r(x)=xr·K(x)

modg(x)

；寫出碼多項式：C(x)=xr·K(x)

+r(x)

寫出碼字：C第三部分、信道編碼3.3循環(huán)碼間接編碼方法：由g(x)得到一個碼字，循環(huán)移位得到k個碼字；寫出生成矩陣，通過線性變換得到系統(tǒng)碼生成矩陣G；由生成方程C=K?G求出相應碼字?；颍貉h(huán)移位法第三部分、信道編碼3.3循環(huán)碼4.

糾錯、譯碼接收碼多項式R(x)；伴隨子多項式S(x)=R(x)modg(x)；若

S(x)=0，則表明接收碼無誤。若

S(x)≠0，表明接收碼有誤。S(x)=[C(x)+E(x)]modg(x)=E(x)modg(x)；列S(x)—E(x)對照表，由S(x)查出E(x)C(x)=R(x)+E(x)第三部分、信道編碼3.3循環(huán)碼第三部分、信道編碼3.4循環(huán)碼的擴展3.4、循環(huán)碼的擴展增余漢明碼漢明碼每個許用碼字+一位奇偶校驗位→成為(n+1,k)碼糾錯能力不變，校驗矩陣增加全1的一行，可以檢查兩位錯截短的循環(huán)碼

由(n,k)循環(huán)碼截短生成的(n-i,k-i)碼。如CRC碼監(jiān)督位沒有變，糾錯能力不變，糾錯方法不變。3.本原BCH碼：它是能糾正多位錯的循環(huán)碼。3.5、卷積碼1.(n,k,m)的含義

2.輸出對輸入的依賴關系監(jiān)督方程邏輯電路3.狀態(tài)轉移圖與格圖：狀態(tài)指寄存器的值。4.直接編碼第三部分、信道編碼3.5卷積碼[例7]已知(2,1,2)卷積碼監(jiān)督方程（1）畫出電路框圖。（2）畫出狀態(tài)轉移圖。解:(1)

由監(jiān)督方程:第三部分、信道編碼3.5卷積碼S1S2kc1c2aiai-2ai-100011011000110110/000/100/011/101/111/011/000/11（2）狀態(tài)轉移圖:第三部分、信道編碼3.5卷積碼S1S2kc1c2aiai-2ai-1S2S1注意！ai的狀態(tài)是ai-2ai-1即寄存器S2S1的值。（注意先后次序）kc1c2典型題目講解第五部分、典型題目一．填空：碼長為10最多可糾2位錯的線性分組碼可寫為(

)碼;2.監(jiān)督位為r=6的漢明碼，信息位為________位，編碼效率等于________，能夠糾正

位錯。

3.無失真信源編碼定理指出平均碼長的理論極限值

，此時編碼效率為

。4.信源編碼的主要目的是

；信道編碼的主要目的是

；保密編碼的主要目的是

。10,45757/63=0.905

1檢查糾正錯誤H∞/logr增強抗攻擊性1壓縮代碼長度5.已知在GF(24)中因式分解有：x15-1=m0(x)m1(x)m3(x)m5(x)m7(x)=(x+1)(x4+x+1)(x4+x3+x2+x+1)(x2+x+1)(x4+x3+1)，則(15，5)本原BCH編碼的生成多項式是_____________。

g(x)=LCM[m1(x)m3(x)m5(x)]=x10+x8+x5+x4+x2+x+16.某二元無記憶信源發(fā)出100個二元符號，其中有m個“1”，若P(0)=1/4，則總自信息為____________。7．信道誤碼率為p=10-3，采用三連重復碼編碼傳輸時的差錯率約為

。8.香農(nóng)信道編碼定理指出，無差錯傳輸?shù)膫餍怕什荒艽笥?/p>

。9.某理想通信系統(tǒng)，信噪比為3dB，為使功率節(jié)省一半又不損失信息量，帶寬應增加到原來的

_________倍。10.錯傳率為p的BSC的信道容量為_________________

11.若__________受限,輸出波幅度在[a,b]之內，則均勻分布的連續(xù)信源具有最大熵，熵值為__________；若_______受限，正態(tài)分布的連續(xù)信源具有最大熵，熵值為

；第五部分、典型題目3×10-6信道容量200-1.585m

1+plogp+(1-p)log(1-p)log(b-a)峰值功率平均功率

log23=1.585

第五部分、典型題目二．判斷(正確打√，錯誤打×)

1．信源符號的相關程度越大，信源的信息熵越大。2、異前綴碼一定是即時碼；3、信道編碼定理指出：信道無失真?zhèn)鬟f信息的條件是信息率小于信道容量；

4、Huffman編碼是單符號信源編碼的最佳編碼；

5、最大似然譯碼準則是使平均譯碼錯誤率最小的準則。6、滿足克拉夫特不等式的碼必定是惟一可譯碼。×√√√××第五部分、典型題目7、(15，11)碼是漢明碼。8、(23，12)碼不是完備碼。9、信源編碼中往往無法指出哪幾個碼元或符號是冗余，冗余表現(xiàn)為信息熵沒有達到最大值。10、恒比碼是線性分組碼。11、離散等概信源具有最大信息熵?！獭獭痢痢痰谖宀糠?、典型題目三．計算題：

1．一階馬爾可夫信源的狀態(tài)圖如右，信源X的符號集為{0,1,2}，圖中。分別求：(1)平穩(wěn)后的信源概率分布；(2)信源熵H∞；(3)求p=1時實際信源的熵，并說明所得結果的理由。解：(1)一階馬爾可夫信源，狀態(tài)為單個符號，信源符號集為X={0,1,2}，E1=0,E2=1,E3=2,穩(wěn)態(tài)概率滿足：Q(0)=

(1-p)Q(0)＋pQ(1)Q(1)=pQ(2)＋(1-p)Q(1)且，Q(0)+Q(1)＋Q(2)＝1解方程：Q(0)＝1/3；Q(1)＝1/3；Q(2)＝1/3；(2)

(3)實際信源熵為H∞。p=1時，理由：因為每種狀態(tài)都只發(fā)兩個符號，當一種符號概率為1時，另一個必然為0，實際上只發(fā)一種確定的符號，成為確定事件，其自信息為0。三種狀態(tài)下發(fā)出符號的自信息均為0，平均值也一定為0。因此不確定性為0，所以信源熵為0。2.二元無記憶信源發(fā)出a、b兩個符號，概率分別為0.7和0.3，試用三次擴展信源進行二元Huffman編碼。解：根據(jù)p(x1x2x3)=p(x1)p(x2)p(x3)不難求出三次擴展信源的概率空間為：

按8個符號的概率排隊，進行Huffman編碼第五部分、典型題目bbb

0.027

bba

0.063bab

0.063

abb

0.063

(0.09)(0.126)

baa

0.147

aba

0.147

aab

0.147

(0.216)(0.294)aaa

0.343

(0.363)

0.637

root

1010101010101010111010100110000110101100

碼字44443322碼長第五部分、典型題目

碼字00110100111000100110101011

碼長22334444

碼字平均長度：

LN=2.726；信源符號平均編碼長度：信源信息熵:H(X)=-0.3log0.3-0.7log0.7=0.881編碼效率：η=0.881/0.909=96.9%第五部分、典型題目3．二元信源每秒發(fā)出100個符號，若信源概率為0.6和0.4；信道傳輸矩陣為:；求發(fā)信率和傳信率。第五部分、典型題目解：發(fā)信率就是信源符號熵乘以碼率：Rb=RB·H(X)：

H(X)=-0.6log0.6-0.4log0.4=0.9710bit/符號

Rb=RBH(X)=97.1bit/s

傳信率就是平均互信息乘以碼率，Rt=RB·I(X;Y)

：聯(lián)合熵：H(XY)=1.7822;接收符號熵：H(Y)=0.9928;平均互信息：I(X;Y)=H(X)+H(Y)-H(XY)=0.1816bit/