信息論基礎(chǔ)總結(jié)

1、第1章信息論根底信息是物質(zhì)和能量在空間和時間上分布的不均勻程度,或者說信息是關(guān)于事物運動的狀態(tài)和規(guī)律.消息是能被人們感覺器官感知的客觀物質(zhì)和主觀思維的運動狀態(tài)或存在狀態(tài).通信系統(tǒng)中形式上傳輸?shù)氖窍?實質(zhì)上傳輸?shù)氖切畔?消息中包含信息,消息是信息的載體.信息論是研究信息的根本性質(zhì)及度量方法,研究信息的獲取、傳輸、存儲和處理的一般規(guī)律的科學(xué).狹義信息論信息論研究的范疇：? 實用信息論 廣義信息論信息傳輸系統(tǒng)信息傳輸系統(tǒng)的五個組成局部及功能：1 .信源信源是產(chǎn)生消息的源.2 .編碼器 編碼器是將消息變換成適合于信道傳送的信號的設(shè)備. 編碼器分為信源編碼器和信道編碼器兩種.3 .信道信道是信息傳輸和

2、存儲的媒介,如光纖、電纜、無線電波等.4 .譯碼器 譯碼器是編碼器的逆變換,分為信道譯碼器和信源譯碼器.5 .信宿信宿是消息的接收者,可以是人,也可以是機器.離散信源及其數(shù)學(xué)模型離散信源一消息集X為離散集合,即時間和空間均離散的信源.連續(xù)信源一時間離散而空間連續(xù)的信源.波形信源一時間和空間均連續(xù)的信源.無記憶信源一X的各時刻取值相互獨立. 有記憶信源一X的各時刻取值互相有關(guān)聯(lián).離散無記憶信源的數(shù)學(xué)模型一離散型的概率空間：XX2X|1jq(X)J _q(Xi) q®)q(xj.離散無記憶N維擴展信源的數(shù)學(xué)模型：X XiX2Xm_q(X) 一必Xi) q(X2)q(Xm)Xi e ai,

3、 a2,ak0 <q(Xi)< 11<i <II'、q(Xi) = 1i=1X=X1X2 - XN Xi a1； a2, , ak1< i < NNq(X) = q( x1x2 xN) = 口 q(Xi) i W離散信道及其數(shù)學(xué)模型離散信道一信道的輸入和輸出都是時間上離散、連續(xù)信道一信道的輸入和輸出都是時間上離散、取值離散的隨機序列. 離散信道有時也稱為數(shù)字信道.取值連續(xù)的隨機序列,又稱為模擬信道.半連續(xù)信道一輸入序列和輸出序列一個是離散的,而另一個是連續(xù)的.波形信道一信道的輸入和輸出都是時間上連續(xù),并且取值也連續(xù)的隨機信號.無記憶信道一信道的輸出y

4、只與當(dāng)前時刻的輸入 x有關(guān).有記憶信道一信道的輸出y不僅與當(dāng)前時刻的輸入 x有關(guān),還與以前的輸入有統(tǒng)計關(guān)系.離散無記憶信道的數(shù)學(xué)模型一信道轉(zhuǎn)移概率矩陣：信道輸入、輸出符號集為 X、YX=X1, X2,X|, Xi C ,a2,ak , 1W i w IY=y1,y2,yj, yj e b1,b2,2,iw j w j離散無記憶N維擴展信道的特性：序列的轉(zhuǎn)移概率 p(y I x) = p( y1y2 - yNi I x1x2 p(yiXi) p(y2X1)p(yjX1)p _ p(y1X2) p(y2 X2)p(yjX2)(MXi) p(y2Xi)p(yjXi)_J0< p(yj I Xi

5、 ) < 1£ p(yj Xi) =1jN)p(y x) =n p( yi Xi)Z p(y|X) =1yY通信中常用的概率函數(shù)討論 ：信道輸入符號集X=X1,X2,x-,xi,輸入符號XiCa1,a2,ak ,1 w i w I ；信道輸出符號集Y=y1,y2,3,yj,輸出符號yjC", b2,b0 ,1 w j w J；輸入符號Xi的概率記為q(x.稱為先驗概率,輸出符號 yj的概率記為w(yj);輸入符號為Xj輸出符號為 片時的概率記為p(yj刈稱為信道轉(zhuǎn)移概率,輸出符號為yj估計輸入符號是Xi的概率記為()(Xi I yj)稱為后驗概率；在輸入輸出XY二維聯(lián)

6、合空間上,Xj*的聯(lián)合概率記為p(xiyj )o先驗概率、信道轉(zhuǎn)移概率、后驗概率和聯(lián)合概率應(yīng)滿足的一些性質(zhì)及關(guān)系0£q(Xi) w(yj) p( yj | 為)(xjyj) p(XiYj)三 1IJJII J% q(Xi)=1 、w(yj)=1' p(yj|Xi)=1' (Xi | yj) =1 .,= p(xyj)=1i =1j=1j =1i =1i=1j 二p(Xiyj) =q(Xi)p(yj|x) =w(yj)欠xjyj)IIw(yj)=£ p(Xiyj) =X q(Xi)p(yj|xi)i 1i 1JJq(Xi) = '、' p(X

7、yj) = '、w(yj)(為 yj) jvj w輸入與輸出 相互獨立時:p(yj Xi) = w(yj)(Xiyj) = q(Xi)p(Kyj) = q(Xi)w(yj)第2章信息的度量自信息量和條件自信息量一個事件的自信息量就是對其不確定性的度量.I (x) A -log q(x)(比特)自信息量的性質(zhì)：I (XiYj)A -log p(XiYj)(比特)I (為 y )Alog*(Xi y. (比特)(1) I(x)是q(x)的單調(diào)遞減函數(shù);(3)當(dāng) q(x)=1 時,I(x)=0;(2)信息量具有可加性；(4)當(dāng) q(x)=0 時,I(x)一0°.互信息量和條件互信息

8、量互信息量說明兩個隨機事件的相互約束程度.I (x;yj) = I (x) I(x yj)niog3 yj) q(x)P( yj x)(2-7)I (x； yj)= 10g= I (yj) - I(yj x)(yj)p(xyj)I(x；yj) =1og= I(x) I (yj) - I (xyj)(2-8)q(xi) (yj)式(2-7)的物理意義：在信源發(fā)出信號前,信宿收到y(tǒng)j的概率為3為),其不確定性用I (yj)度量.而信源發(fā)出符號xj后,由于干擾,使信宿收到Y(jié)=y丫2,yj中的哪個符號具有發(fā)散性,即信宿是否收到力仍存有不確定性,用I (力I劃度量.這二者之差就是事件發(fā)生過程中觀察者所獲

9、得的信息量.式(2-8)的物理意義：通信前 X、Y統(tǒng)計獨立,聯(lián)合概率為 P(xiyj)= q(xi)叫),不確定性用-log q(xi).) = I(xj)+I(yj)度量.通信后,由于信道轉(zhuǎn)移概率p(yj I引的存在,使符號xiyj有了某種關(guān)聯(lián),聯(lián)合概率P(xiyj)= q(xi) p(yj I xi),發(fā)xi收yj的不確定性用I(xiyj)= - log p(zyj)度量,二者之差就是通信過 程中,不與刀所得到的互信息量.互信息量的性質(zhì)：(1)互易性：I(xi ; yj)= I(yj ; xi )(2)可加性：I(xi ； yj zk)= I(xi ; yj )+ I(xi ; z yj)

10、(3)當(dāng)者,yj統(tǒng)計獨立時,互信息量I® ;yj)=0及條件互信息量(4)互信息量I(xi ;刀)可以是正數(shù),也可以是負數(shù).(5)兩個事件的互信息量不大于單個事件的自信息量,即有：I(x;yj zQ = 0I(x; y)I(x.I(yj)平均自信息量平均自信息量(嫡)H(X)&工 q(xi )I (xj = £ q(xi)10gq(xj(比特/符號)平均條件自信息量(條件嫡)H(X |Y)AZ Z p(yj)I(xi |yj) Z p3yj)10g4(為 | yj)(比特/符號) i ji jH(YX) A £2 p(xyj)I(yjX) =-£

11、 £ p(xyj)10gp(y 為)(比特/符號)i ji j從通信角度來看：假設(shè) X為信道輸入符號集,Y為信道輸出符號集,那么稱H(X | Y)為疑義度/模糊度或損失嫡；稱H (Y | X)為散布度或噪聲嫡.(1)對于無噪信道,X與Y 一對應(yīng),不存在疑義H (X | Y)=0,也不會產(chǎn)生錯位 H (Y | X)=0;(2)在強噪聲情況下,X與Y統(tǒng)計獨立,H(X | Y)=H(X), H(Y | X)=H(Y).聯(lián)合嫡 H(XY)£££ P(Yj)I(XiYj) =-H H p(x y.10gpJy.(比特/符號) 一i ji j嫡、條件嫡、聯(lián)合嫡的關(guān)系

12、：H (X Y) = H (X) + H (Y | X)= H (Y) +H (X | Y)當(dāng) X, Y 統(tǒng)計獨立時,H (X Y)= H(X)+ H(Y)極大離散嫡定理：設(shè)信源消息集X=x1, x2,xM的消息個數(shù)為 M,那么H(X)<1ogM,等號當(dāng)且僅當(dāng)信源 X中各消 息等概(=1/M)時成立,即各消息等概分布時,信源嫡最大.嫡函數(shù)的性質(zhì)：(1)對稱性 非負性 (3)確定性(4)擴展性 (5)可加性(6)條件嫡小于等于無條件嫡,即： H (X | Y)WH (X) , X,Y統(tǒng)計獨立時等號成立.(7)聯(lián)合嫡大于等于獨立事件的嫡,小于等于兩獨立事件嫡之和,即：,H(XY"H

13、(X)H(XY) >H(Y)H (XY) W H (X) + H (Y)平均互信息量(交互嫡)I(X;Y) = p(xi yj)I (x yj)二工 工i ji j*(xi yj)P(xi yj) 10g q(xi)(比特/符號)平均互信息量與信源嫡、條件嫡的關(guān)系(維拉圖)I (X;Y)= H(X)- H(X | Y)(2-35)I(X;Y)=H(Y)- H(Y | X)(2-36)I(X;Y) = H(X) + H(Y) H(XY)(2-37)從通信的角度討論：(2-35)式的物理意義：設(shè) X為發(fā)送消息符號集,Y為接收符號集,H(X)是輸入集的平均不確定性,H (X| Y)是觀察到Y(jié)后

14、,集X還保存的不確定性,二者之差I(lǐng)(X;Y)就是在接收過程中得到的關(guān)于X,丫的平均互信息量.(2-36)式的物理意義：H(Y)是觀察到Y(jié)所獲得的信息量,H (Y I X)是發(fā)出確定消息 X后,由于干擾而 使Y存在的平均不確定性,二者之差I(lǐng)(X ； Y)就是一次通信所獲得的信息量.(2-37)式的物理意義：通信前,隨機變量X和隨機變量Y可視為統(tǒng)計獨立,其先驗不確定性為 H(X)+ H(Y), 通信后,整個系統(tǒng)的后驗不確定性為H(XY),二者之差H(X) +H(丫)一H(XY)就是通信過程中不確定性減少的量,也就是通信過程中獲得的平均互信息量I(X ; Y)o(1)對于無噪信道,X 與 Y 一一對

15、應(yīng),H(X | Y)=0 從而 I(X ; Y)=H(X); H(Y | X)=0 從而 I(X ; Y)= H(Y);(2)對于強噪信道,X 與 Y 統(tǒng)計獨立,H(X | Y) =H(X)從而 I(X ; Y)=0; H(Y | X)= H(Y)從而 I(X ; Y) = 0.平均互信息量的性質(zhì)：I X;Y -0I X;Y < H (X)(1)非負性：I(X;YZ )>0(2)互易性：I(X ; Y)= I(Y ; X) (3)極值性：以A H(Y)定理2.1當(dāng)信道給定,即信道轉(zhuǎn)移概率 p(y|x)固定,平均互信息量I(X ;丫)是信源概率分布q(x)的n形凸函數(shù).定理2.2當(dāng)信

16、源給定,即信源分布概率q(x)固定,平均互信息量I(X ;Y)是信道轉(zhuǎn)移概率 p(y|x)的U形凸函數(shù).第3章離散信源無失真編碼信源編碼的目的： 提升傳輸效率. J無失真編碼,壓縮信源的冗余度,不改變信源的嫡.I.失真編碼,壓縮信源的嫡.信道編碼的目的： 增強通信的可靠性.信源編碼的功能：1將信源符號變換成適合信道傳輸?shù)姆枺?壓縮信源冗余度,提升傳輸效率.碼碼的分類奇異碼非奇異碼惟一可譯碼非惟一可譯碼變長碼等長碼平均碼長即時碼延長碼_ Mn =£ nmPCm式中nm是碼字Cm所對應(yīng)的碼字的長度,p Cm是碼字cm出現(xiàn)的概率.m 二iiiiiiiiiiii信息傳輸速率信息傳輸速率為信

17、道單位時間內(nèi)所傳輸?shù)男畔⒘?信道中平均每個碼符號所能傳送的信息量.H XRd =一比特/碼元時間n式中：HX為信源嫡；n為編碼后的平均碼長；時間以碼元時間傳輸一個碼符號的時間為單位.等長碼及等長編碼定理對單符號信源S的L次擴展信源SL進行等長編碼,要得到長為n的唯一可譯碼,必須滿足 KLWDn即 n log KL - log D其中：K為信源符號個數(shù),D為碼符號個數(shù),n/L表示信源序列中平均每個信源符號所需要的碼符號數(shù).定理3.1等長編碼定理 設(shè)離散無記憶信源 S =x1, x2,xk的嫡為H X, S的L維擴展信源為SL=Si,S2,SkL,對信源輸出的L長序列si, i = 1, 2,KL

18、進行等長編碼,碼字是長度為n的DPe < 8 e、8為無窮小量；反之進制符號串,當(dāng)滿足條件口下旦生生,那么L-8時,可使譯碼過失n . h x ；L log D編碼效率：L log D時,那么不可能實現(xiàn)無過失編碼._lhxn log D變長碼及變長編碼定理對于給定信源及碼符號集,使平均碼長到達最小的編碼方法稱為最正確編碼.在所有的唯一可譯碼中,平均碼長最小的碼稱為最正確碼緊致碼.M克拉夫特不等式:'、D % <1 m 1惟一可譯碼一定滿足克拉夫特不等式,滿足克拉夫特不等式的碼不一定是惟一可譯碼.定理3.3給定嫡為H (X)的離散無記憶信源,及有 D個元素的碼符號集,那么總可

19、找到一種無失真編碼方法,構(gòu)成惟一可譯碼,其平均碼長后滿足：HfX -H(X)nn ： 1 -log Dlog D定理3.4 變長編碼定理 (Shannon第一定理),其L次擴展信源給定嫡為H (X)的離散無記T言源一 X 1 _Xix2Xm 1Jq(X)J q(Xi) q®)q(XM)JI X IX1x21q(X) 1q(Xi) q(X2)XMq、)進行編碼,總可以找到一種惟一可譯碼,使碼長的嫡記為H (X),給定有D個元素的碼符號集,對擴展信源,滿足 H (XnL H(X 3 1log D - L log D L一6皿二log D log D Ln 一; H(X)當(dāng) L 時1Lmn

20、=.記 _L=n為信源每個符號所對應(yīng)的平均碼字數(shù),那么: LH(X)Rd = log Dn到達極限值.Shannon第一定理的物理意義：對信源進行編碼,使編碼后的碼集中各碼字盡可能等概分布,如果將這碼集看成為一個新的信源,這 時新信源所含信息量最大.編碼效率： ,H X log D H X= n n log D變長碼的編碼方法香農(nóng)(Shannon)編碼法；費諾(Fano)編碼法；霍夫曼(Huffman)編碼法.霍夫曼編碼法的指導(dǎo)思想是：概率小的消息賦予較大的碼長,概率大的消息賦予較小的碼長.掌握D=2即二進制霍夫曼編碼方法.第6章率失真編碼失真測度矩陣diidi2dijd _ d2id22 d

21、2jE* >. > «jdiidi2 d|j_其中：d1 j=d (xi ,yj)為信源方發(fā)送符號 外而信宿方判為yj引起的失真度._ I JI J平均失真 D=££ p(xyj)dij =££ q(Xi)p(yJx)diji 4 j 4i 4 j 4式中D是預(yù)先給定的失真度.保真度準(zhǔn)那么：D = v q Xi p yj |為dj m D率失真函數(shù)R(D) R D上min I X;Y : D M D)=p( y|x)意義：選才i p(y I x)即選擇某種編碼方法在滿足D <D的前提下,使I (X ; Y)到達最小值R(D),

22、這就是滿足平均失真D <D條件下的信源信息量可壓縮的最低程度.減函數(shù)DminM q(x)min d yjjiIDmax =min q(xjdijj i 1率失真函數(shù)的值域、定義域0< R (D) w H (X)D min w D w D max,率失真函數(shù)的性質(zhì)：(1) R(D)是D的U型凸函數(shù)(2) R(D)是D的連續(xù)、單調(diào)、(3)對于離散無記憶信源(DMS ), R (N ) (D) = N R (D)R(D)是每次傳送一個符號時的率失真函數(shù),R(N)(D)是每次傳送N個符號時的率失真函數(shù).率失真信源編碼定理對于離散無記憶平穩(wěn)信源,給定允許失真D,當(dāng)信息傳輸率 R>R(D

23、),那么只要信源序列 x = x1x2 - xN足夠長,一定存在一種編碼方法 (對應(yīng)一種實驗信道),使平均失真滿足_D E D +名,e是任意小的正數(shù). 反之,假設(shè)信息傳輸率 RvR(D),那么無論如何采用何種編碼方法,必有D > D .上述定理(香農(nóng)第三定理),R>R(D)的情況稱為 保真度準(zhǔn)那么下的率失真編碼定理,Rv R(D)的情況稱之為逆定理.第4章 離散信道的信道容量信道容量的定義CMaxIx；Y比特/碼符號,使I X; Y到達信道容量的分布q x為最正確分布.定理4.1如果信道是離散無記憶 DMC的,那么CN WNC,其中C是同一信道傳輸單符號時的信道容量.定理4.2使

24、平均互信息量I X; Y到達信道容量 C的充要條件是信道輸入概率分布x Xi X21q(X)j q(Xi) q(X2)xMq(xM)簡記為 q (X) = q (x1), q (x2),p (xM)滿足:I(X；Y)=CI(x；Y)<C假設(shè)q(x. 0假設(shè)q(x.= 0i = 1,2, ,M無損信道H (XI Y) = 0 I (X; Y) = H (X)C - max I (X ;Y) = maxH (X)q(x)q(x)確定信道H (Y I X) = 0 I (X; Y) = H (Y)C ： max I (X;Y) =maxH(Y)=q(x)w(y)行輸入對稱信道、列輸出對稱信道、

25、準(zhǔn)對稱信道對稱信道定理4.3實現(xiàn)DMC準(zhǔn)對稱信道的信道容量的分布為等概分布.信道容量的計算準(zhǔn)對稱信道信源只含兩個消息N并行信道并行組合信道的信道總?cè)萘浚篊 <Z Ckk工串行信道串行組合信道的信道轉(zhuǎn)移概率矩陣：lpy；|X= fpy. Xi.IpyJX：數(shù)據(jù)處理定理：無論經(jīng)過何種數(shù)據(jù)處理,都不會使信息量增加.第5章有噪信道編碼信源編碼的目的： 提升有效性.方法：壓縮信源的冗余度. 衡量指標(biāo)：信息傳輸速率.信道編碼的目的： 增強可靠性.方法：增加信源的冗余度. 衡量指標(biāo)：平均錯誤概率.譯碼總原那么： 錯誤概率最小(最正確譯碼).=> 最大后驗概率譯碼準(zhǔn)那么(=最大聯(lián)合概率譯碼準(zhǔn)那么)

26、極大似然譯碼準(zhǔn)那么(在信道輸入等概條件下為最正確譯碼準(zhǔn)那么)平均錯誤概率Pe =' P(Xy)X- Xk y有噪信道編碼定理(Shannon第二定理)對于任何離散無記憶信道 DMC ,存在信息傳輸率為 R,長為n的碼,當(dāng)n 一8時,平均過失概率pe< exp- nE(R) 一0,式中E (R)為可靠性函數(shù),E (R )在0<R<C的范圍內(nèi)為正.信道容量C是在滿足錯誤概率pe- 0時,信道所能容納的信息傳輸率的極限值.信道編碼逆定理信道容量C是可靠通信系統(tǒng)信息傳輸率的上界,當(dāng) R>C,不可能存在任何方法使過失概率任意小.費諾不等式H(X | Y) & H2(pe) + pelog