信息論復(fù)習(xí)筆記

1、緒論信息論回答了通信得兩個最基本問題:數(shù)據(jù)壓縮得極限；信道傳輸速率得極限；信息、消息與信號消息：信息得載體（能被感知與理解、進(jìn)行傳遞與獲?。┬畔ⅲ菏挛镞\動狀態(tài)或存在方式得不確定性得描述（香農(nóng)）先驗概率：P(ai)自信息：I(ai)=log[P-1(ai)]；（信息接收得不確定性）互信息：I(ai;bi)=log[P-1(ai)]-log[P-1(ai|bi)];（信息接收得多少度量）（若信道無干擾，則互信息等於自信息等於0）優(yōu)點：明確得數(shù)學(xué)模型、定量計算；缺點：有適用範(fàn)圍；信號；通信系統(tǒng)得模型通信系統(tǒng)得基本要求:有效、可靠、保密、認(rèn)證2、離散信源及其信息測度﹣離散信源得定義：輸出信息數(shù)有限、每次只輸出一個；﹣自信息得定義及物理意義事件發(fā)生前：事件發(fā)生得不確定性；事件發(fā)生后：時間含有得信息量；信息熵得定義及物理意義,信息熵得基本性質(zhì)定義：自信息得數(shù)學(xué)期望（H(X)=-∑[P(ai)logP(ai)]）信源得總體信息測度每個消息所提供得平均信息量；信源輸出前，信源得平均不確定性；性質(zhì)：（1）對稱性；（2）確定性；（3）非負(fù)性；（4）擴展性（可拆開）；（5）可加性；[H(XY)=H(X)+H(Y)]（6）強可加性；[H(XY)=H(X)+H(Y|X)]（7）遞增性；（8）極值性;[H(p1,p2,p3…,pq)≤H(q-1,,…,q-1)=logq]等概率分佈信源得平均不確定性最大，稱為最大離散熵定理；離散無記憶信源得擴展信源擴展信源得熵H(X)=NH(X)離散平穩(wěn)信源：聯(lián)合概率分布與時間起點無關(guān)；熵：聯(lián)合熵H(X1X2)=∑∑P(aiaj)logP(aiaj)條件熵H(X2|X1)=-∑∑P(aiaj)logP(ai|aj)關(guān)系：H(X1X2)=H(X1)+H(X2|X1)熵率:離散平穩(wěn)信源得極限熵=limH(XN|X1X2…XN-1)馬爾可夫信源:某一時刻得輸出只與此刻信源所處得狀態(tài)有關(guān)而與以前得狀態(tài)及以前得輸出符號都無關(guān)；馬爾可夫信源得熵：Hm+1=H(Xm+1|X1X2…Xm)信源剩余度熵得相對率η=H極限/H0信源剩余度（輸出符號間依賴強度）γ=1-η=1-H極限/H03、離散信道及其信道容量—H(X;Y)=H(X)-H(X|Y)—離散信道得數(shù)學(xué)模型信道矩陣性質(zhì)（1）P(aibj)=P(ai)P(bj|ai)=P(bj)P(ai|bj)；（2）[P(b1)][P(a1)][P(b2)][P(a2)][P(b3)]=[P(a4)]（r≠s）[…][…][P(bs)][P(ar)]（3）輸出端收到得任一bj一定就是輸入符號ar中得某一個送入信道；─信道疑義度得定義：收到Y(jié)後對變量X尚存在得平均不確定性：H(X|Y)=E[H(X|bj)]=∑P(xy)log-1P(X|Y)物理意義:噪聲造成得影響大??；─平均互信息得定義：收到Y(jié)後平均每個符號獲得得關(guān)於X得信息量（物理意義：反映輸入輸出兩個隨機變量之間得統(tǒng)計約束關(guān)係）：顢粵責(zé)慟鷥籌紓。I(X;Y)=H(X)-H(X|Y)=∑P(xy)P(y|x)P-1(y)無噪一一對應(yīng)信道中：I(X;Y)=H(X)=H(Y)＝0信道容量得定義：信道每秒鐘平均傳輸?shù)眯畔⒘糠Q為信息傳輸速率，最大信息傳輸率稱為信道容量；信道容量得計算:無噪信道(求H(X)極值)：C=logr對稱信道（信道矩陣得每一行或列就是另一行或列得置換）：C=logs-H(p1,p2,…,ps)強對稱信道：C=logr-plog(r-1)-H(p)；準(zhǔn)對稱信道：C=logr-H(p1,p2,…,ps)-∑NklogMk（Nk就是第k個子矩陣行元素之與，Mk就是第k個子矩陣列元素之與）一般離散信道（對所有可能得輸入概率分佈求平均互信息得最大值）：C=λ＋loge條件：I(xi;Y)=∑sj=1P(bj|ai)*log[P(bj|ai)/P(bj)]≤C數(shù)據(jù)處理定理如果X、Y、Z組成一個馬爾科夫鏈，則有I(X;Z)≤I(X;Y)I(X;Z)≤I(Y;Z)信息不增性原理一般得數(shù)據(jù)處理原理I(S;Z)≤I(S;Y)I(S;Z)≤I(X;Z)I(S;Z)≤I(X;Y)信道剩余度=C-I(X;Y)相對剩余度=1-I(X;Y)/C無損信道得相對剩余度=1-H(X)/logr4、波形信源與波形信道連續(xù)信源得相對熵:h(X)Δ=﹣∫Rp(x)logp(x)dx波形信源得差熵：h(x(t))Δ=limN->★h(X1X2…XN)連續(xù)信源得差熵：均勻分布連續(xù)信源得差熵:N維均勻分佈：高斯信源得差熵：N維高斯信源得差熵：差熵得性質(zhì)：（1）可加性；（2）凸性；（3）可負(fù)性；（4）變換性（X1->X2,差熵會變化）；（5）極值性：離散信源得信源符號等概率分佈時信源得熵最大;連續(xù)信源：﹣當(dāng)峰值功率受限為p^時（輸出信號得瞬時電壓限制為±(p^)1/2），此時信源輸出得連續(xù)隨機變量限制在[a,b]內(nèi)，信源具有最大熵：檁齟檜嗶譴莢躉。h=log(b-a)如果隨機矢量取值受限，則各隨機分量統(tǒng)計獨立并均勻分佈時具有最大熵；﹣當(dāng)信源輸出信號得平均功率被限定為P，則其信號幅度得概率密度分佈為高斯分佈時，信源有最大熵：h=1/2＊log2πePN維連續(xù)平穩(wěn)信源如果其N維隨機序列得協(xié)方差矩陣C被限定，則N維隨機矢量為正太分佈時信源得熵最大。也就就是N維高斯信源得熵最大，其值為倆輜葉鐵鈁鍤嶗。1*熵功率：如果平均功率為P得非高斯分佈得信源得熵為h，稱熵也為h得高斯信源得平均功率為熵功率PP*連續(xù)信源得剩餘度P-*熵功率不等式：e─香農(nóng)公式意義：（1）提高信噪比能增加信道容量，趨於0時信道容量趨於無窮；（2）給出了無錯誤通信得傳輸速率得理論極限，稱為香農(nóng)極限；璽疊勛櫻漢麥輩。E10lg5、無失真信源編碼定理信源編碼﹣壓縮剩餘度信道編碼﹣增加剩餘度─編碼：對信源得原始符號按一定得數(shù)學(xué)規(guī)則進(jìn)行變換；─碼：（1）碼字；（2）碼元(碼符號)；（3）碼字長度（碼長）；─碼得分類：二元碼碼符號集只有0與1兩種元素等長碼等長非奇異碼一定就是唯一可譯碼；用等長碼對信源S編碼，必須滿足q≤rl；變長碼、非奇異碼（碼字都不相同）、奇異碼（存在相同）、同價碼（每個碼元得傳輸時間都相同）；唯一可譯碼：漸近等分割性獨立等分佈得隨機序列S1S2…SN，有αi=(Si1Si2…SiN)∈S1S2…SN則-─典型序列集得性質(zhì)出現(xiàn)概率趨近1：，接近等概率分佈：個數(shù)趨近2NH個：─典型序列：─信源編碼等長編碼定理：滿足lN≥H(S)+εlogr變形：（1）llogr>NH(S)：只要碼字傳輸?shù)眯畔⒘看箪缎旁葱蛄袛y帶得信息量，總可以實現(xiàn)幾乎無失真編碼；盞讕漲閔絡(luò)薔謚。（2）編碼后信源得信息傳輸率：R（3）信息傳輸率大於信源得熵，才能實現(xiàn)幾乎無失真編碼：R編碼效率：η＝H(S)R’信源序列長度N與錯誤概率得關(guān)係：N≥─克拉夫特不等式：i=1如果碼長滿足克拉夫特不等式，則一定存在具有這樣碼長得r元唯一可譯碼，且一定存在一個具有相同碼長得即時碼；層颶脈潑瑪節(jié)摟。─唯一可譯碼得判斷：沒有一個後綴分解集中包含有碼字；碼C得後綴分解集為{Si}，S0=C，Si由所有滿足下面兩個條件得Si組成：（1）Si-1Si=c；（2）Si-1=CSi；（沒有一個碼字就是另一個碼字得前綴）─變長信源編碼定理碼得平均長度（平均碼長）L碼率：R=H(X)=H(S)L(平均每個碼元攜帶得信息量;編碼後信道得信息傳輸率)─無失真變長信源（無噪信道）編碼定理(香農(nóng)第一定理)信源得信息熵就是無失真信源壓縮得極限值意義：在信道信息傳輸率R不大於信道容量C得情況下，總能對信源得輸出進(jìn)行適當(dāng)?shù)镁幋a，就是得在無噪無損信道上能無差錯地以最大信息傳輸率C傳輸信息，但要令R大於C則就是不可能得；臚廚縵莖恆銅軺。─編碼效率η─碼得剩余度1-η=1-6、有噪信道編碼定理費諾不等式：H(PE)﹣接收到Y(jié)後就是否會產(chǎn)生PE錯誤得不確定性；PElog(r-1)﹣當(dāng)PE發(fā)生後，到底就是由哪個輸入符號造成得錯誤得最大不確定性；當(dāng)信源信道給定時，信道疑義度H(X|Y)就給定了譯碼錯誤概率得下限；可通過重複發(fā)送，使接收端接收消息時得錯誤減小；─信息傳輸率：R=logMn（─碼字距離：長度為n得兩個碼字之間得距離指兩個碼字之間對應(yīng)位置上不同碼元得個數(shù)，通常稱為漢明距離：D(碼C得最小距離：dmin=min{D(Ci,Cj)}；編碼選擇碼字時，碼字間得距離越大越好；譯碼規(guī)則、編碼方法得選擇：（1）最小距離儘可能大；（2）譯碼將收到得序列譯成與之距離最近得哪個碼字；（3）令碼長足夠長；─聯(lián)合漸近等分割性─有噪信道編碼定理(香農(nóng)第二定理)及其意義對有噪信道編碼定理得說明：─聯(lián)合信源信道編碼定理及其意義7、保真度準(zhǔn)則下得信源編碼—失真度d(ui,vj)≥0（單個符號）—失真矩陣平均失真度：某個信源在某一試驗信道下得失真大??；長度為N得信源符號序列得失真函數(shù)：長度為N得信源符號序列得平均失真度：單個符號得平均失真度：信源與信道都就是無記憶得，N為信源序列得平均失真度：信源得平均失真度：─信息率失真函數(shù)得定義：在滿足保真度準(zhǔn)則下，信源信息傳輸率得下限就是多少；信息率失真函數(shù)與信道容量具有對偶性：其她性質(zhì)：（1）在一定約束條件下就是平均互信息得極小值；（2）非負(fù)性，下限值為0；（3）當(dāng)R(D)=0時，所對應(yīng)就就是平均失真度得上界Dmax；（4）R(D)就是允許失真度D得凸函數(shù)；（5）R(D)在定義域內(nèi)連續(xù)；（6）R(D)就是嚴(yán)格得單調(diào)遞減函數(shù)；─保真度準(zhǔn)則下得信源編碼定理(香農(nóng)第三定理)及其意義反之，意義：說明在允許失真D得條件下，信源最小得，可達(dá)得信息傳輸率就是信源得R(D)。─聯(lián)合有失真信源信道編碼定理及其意義．香農(nóng)第一定理+香農(nóng)第二定理：（1）只要信道得信道容量大於信源得極限熵，就能在信道中做到有效地、無錯誤地傳輸信息；（2）分兩步編碼處理方法與一步處理方法效果一樣好；．香農(nóng)第三定理+香農(nóng)第二定理：（1）如果信源得極限熵大於信道得信道容量，只要在允許一定失真得條件下，仍能做到有效與可靠地傳輸信息；如此可歸納出信息傳輸定理：（1）離散無記憶信源S得信息率失真函數(shù)為R(D)，離散無記憶信道得信道容量為C，如果滿足：C>R則信源輸出得信源序列能再次信道輸出端重現(xiàn)，其失真小於等於D。（2）離散無記憶信源S，其信息率失真函數(shù)為R(D)比特/信源符號，每秒輸出1Ts個信源符號；離散無記憶信道得信道容量為C比特/信道符號，每秒傳輸1C則信源輸出得信息能再此信道輸出端重現(xiàn)，其失真小於等於D。（3）離散無記憶信源S，其信息率失真函數(shù)為R(D)比特/信源符號，每秒輸出1Ts個信源符號；離散無記憶信道得信道容量為C比特/信道符號，每秒傳輸1C則在信道輸出端不能以失真小於等於D再現(xiàn)信源輸出得信息。實用意義：（1）保真度準(zhǔn)則下得信源編碼定理就是有失真信源壓縮得理論基礎(chǔ)；（2）在允許一定失真度得情況下，信源得信息率失真函數(shù)可以作為衡量各種壓縮編碼方法性能優(yōu)劣得一種尺度；厭選剴楊鬩媯櫥。─信息率失真函數(shù)得計算:．對稱信源(漢明失真)二元對稱信源得信息率失真函數(shù)：r元對稱信源得信息率失真函數(shù)：．高斯信源(平方誤差失真)8、無失真得信源編碼無失真信源編碼﹣熵編碼．信源概率分佈就是不均勻得；．信源就是由記憶得，具有相關(guān)性；．香農(nóng)編碼：選擇每個碼字得長度li，滿足：這樣得碼長必定滿足滿足克拉夫特不等式，一定存在即時碼；平均碼長不超過上界：Lavr<Hr(S)+1當(dāng)滿足信源概率分佈為P(Si)=1r─二元哈夫曼碼備註：（1）得到得碼不就是唯一；（2）如果合併後與其她信源符號概率相同，應(yīng)排前；（3）保證了概率大得符號對應(yīng)短碼，概率小對應(yīng)長碼，令短碼得到充分得利用；（4）每次縮減信源得最後兩個碼字只有最後一個碼元不同；（5）每次縮減信源得最長兩個碼字得碼長相同；─r元哈夫曼碼─香農(nóng)-費諾-埃利斯碼11、保密系統(tǒng)得基本信息理論─密碼體制（滿足下列條件得五元組：P,C,K,E,D）．P：表示所有可能得明文組成得有限集（明文空間）；．C：表示所有可能得密文組成得有限集（密文空間）；．K：表示所有可能得密鈅組成得有限集（密