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

緒論信息論回答了通信的兩個(gè)最基本問(wèn)題:數(shù)據(jù)壓縮的極限；信道傳輸速率的極限；信息、消息和信號(hào)消息：信息的獻(xiàn)置(能被感知和理解、逵行傅遁和獴取)信息：事物遑覲犬熊或存在方式的不碓定性的描述(香的先^概率：P(a.)1自信息：I(ai)=log[P-i(ai)]；(信息接收的不碓定性)互信息：I(ajb尸log[P-i(aj)]-logPHaJb』;(信息接收的多少度量)l(若信道照干凰則互信息等於自信息等於0)僵黑占：明碾的敷孥模型、定量言十算；缺黑占：有遹用簸圉；信號(hào)點(diǎn);通信系統(tǒng)的模型通信系統(tǒng)的基本要求:有效、可靠、保密、認(rèn)證離散信源及其信息測(cè)度-離散信源的定義：翰出信息敷有限、每次只翰出一彳固；-事件畿生前：事件畿生的不碓定性；事件畿生后：畤冏含有的信息量；信息熵的定義及物理意義，信息熵的基本性質(zhì)定羲：自信息的敷孥期望(H(X)=-習(xí)P(ai)logP(ai)])信源的富恩髓信息測(cè)度每侗消息所提供的平均信息量；信源翰出前，信源的平均不碓定性；性W：(1)呈樸卸性；(2)碓定性；非^性；(4)撅展性(可拆勃；可加性；[H(XY)=H(X)+H(Y)]弓魚(yú)可加性；[H(XY)=H(X)+H(Y|X)]遁增性；(8片亟值性；[出旦馮區(qū)…,p)VH(q-i,,…，q-i)=logq]等概率分怖信源的平均不祁性最大：稠舄最大雕散熵定理；一離散無(wú)記憶信源的擴(kuò)展信源一擴(kuò)展信源的熵 H(X)=NH(X)一離散平穩(wěn)信源：聯(lián)合概率分布與時(shí)間起點(diǎn)無(wú)關(guān)；熵：聯(lián)合熵H(X1x2)=EEP(aia,)logP(aia,)條件熵h(x2|Xi)=-EEp(aia，)logp(ai|a，)關(guān)系：h(xix2)=h(x1)+h(x2Ix1)熵率:離散平穩(wěn)信源的極限熵=limH(XN|XiX2???XN-i)

—馬爾可夫信源:某一時(shí)刻的輸出只與此刻信源所處的狀態(tài)有關(guān)而與以前的狀態(tài)及以前的輸出符號(hào)都無(wú)關(guān)；—馬爾可夫信源的熵：Hm+1=H(Xm+i|XiX2^Xm)—信源剩余度熵的相對(duì)率n=H極限/H。信源剩余度(輸出符號(hào)間依賴強(qiáng)度)Y=i-n=i-H極限/H0離散信道及其信道容量—H(X;Y)=H(X)-H(X|Y)(2):P(bi(2):P(bi)]:P(ai)][P(b2)]:P(a2)]:P(b3)]=[P(a4)] (r手s):…]:…]:P(b)]:P(a)](1)P(abj)=P(a)P(b|a)=P(b)P(a|b)；1 iji jij>信道Q(小)里代卞)=1丫=(*,氐乂也,少,以]F:島敏'、婦—信道矩陣性^s r函俞出端收到的任一b.一定是翰入符號(hào)虜ar中的某一彳固送入信道； J '一信道疑義度的定義:收到Y(jié)彳爰封燮量X尚存在的平均不碓定性：一 H(X|Y)=E[H(X|b)]=EP(xy)log-iP(X|Y)j物理意義:噪馨造成的影警大??；一平均互信息的定義:收到Y(jié)彳爰平均每彳固符號(hào)彪恒得的^於X的信息量(物理意羲：反映翰入翰出麗侗隨檄燮量之冏的統(tǒng)言拌勺束款系)：I(X;Y)=H(X)-H(X|Y)=習(xí)P(xy)P(y|x)P-i(y)照噪一一g信道中：I(X;Y)=H(X)=H(Y)=0一信道容量的定義：信道每秒篁平均傅翰的信息量不胃舄信息傅翰速率，最大信息傅翰率不胃舄信道容量；一信道容量的計(jì)算：無(wú)噪信道(求H(X)植值):C=logr對(duì)稱信道(信道矩障的每一行或列是另一行或列的置換)：C=logs-H(P],P2,…,ps)強(qiáng)對(duì)稱信道：C=logr-plog(r-])-H(p);準(zhǔn)對(duì)稱信道：C=logr-H(Pi，P2,…，Ps)-習(xí)NklogMk(Nk是第虹固子矩障行元素之和，Mk是第k固子矩障列元素之和)一般離散信道(封所有可能的翰入概率分怖求平均互信息的最大值)：C=X+loge倏件：I(%;Y)=Es.=]P(b.|a,)*log[P(b.|a,)/P(b.)]<C一般離散信道當(dāng)尸占，并且信道矩陣p是非奇異陣時(shí)，信道容量的計(jì)算步驟如下、Z聲街阿)用=￡凡時(shí)碼)曜H婦但)H=】2…網(wǎng) J-1C=l喧時(shí)計(jì)算”12.")X計(jì)算信道容量C?計(jì)算輸出概率分布P飽…舟計(jì)算輸入概率分布P(%)(AL2r)如果P㈤瀏(41,2,.危)即可結(jié)束計(jì)算，第2步計(jì)算的C即為信道容量；否則要重新計(jì)算 .離散無(wú)記憶信道容量的迭代算法(S.Arimoto,R.E.Blahut,1972)如下;選擇初始概率分布F(理)=矽)(叫)計(jì)算。(并1/)和(?'344洲)區(qū)f/E氣阻坦血)m j。("1』)=111￡汽珥悶.Cr(n+1.h)=]n|max^判斷頃1+1兩。(壯頃)<0如果成立，轉(zhuǎn)第5步;否則轉(zhuǎn)第4步計(jì)算尸(口》然后轉(zhuǎn)第2步M信道容量OC(時(shí)1,町，結(jié)束一數(shù)據(jù)處理定理如果乂、Y、Z組成一個(gè)馬爾科夫鏈，則有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)相對(duì)剩余度=1-I(X;Y)/C無(wú)損信道的相對(duì)剩余度=1-H(X)/logr波形信源和波形信道道^信源的相削商：h(X)戶-/Rp(x)logp(x)dx波形信源的差熵： h(x(t))A=limN_>^h(XiX2-XN)連續(xù)信源的差商： I均勻分布連續(xù)信源的差商： ,—a<x<bp(A)—b—u0othersh(=Incrfft—心隹均勻分怖： ［丁」ht(X)=IF1og0-d) p(x)=《o建110-色)高斯信源的差商：I _女用￡p(x)=^=e^2 X,)\2tto-h(X)-log72^zo^+|-loge=—logZ^etT2成X)=-log2^ePN隹高斯信源的差商： 2A(X)=-log(2^)v|C|

2t=}差熵的性質(zhì)：可加性；(2)凸性；(3)可^性；(4)勤奐性(X「＞X2,差熵畬燮化)；(5)植值性：雕散信源的信源符號(hào)虜?shù)雀怕史植喇囆旁吹撵刈畲螅凰賌信源：-富峰值功率受限舄P。畤(翰出信號(hào)虜?shù)乃伯嚴(yán)桌逑拗启?P心/2)，此日寺信源翰出的速^隨檄燮量限制在[a,b]座，信源具有最大熵：h=log(b-a)如果隨橫矢量取值受限，則各隨橫分量MHW立并均勻分怖畤具有最大熵;-富信源翰出信號(hào)虜?shù)钠骄β时幌薅狿,則其信號(hào)虜幅度的概率密度分彳布舄高斯分彳布H寺，信源有最大熵：h=1/2大log2nePN^B?平穗信源如果其N^B?序列的餉方差矩障C被限定制N^B?矢量舄正太分布畤信源的熵最大。也就是N/名隹高斯信源的熵最大，其值舄1N2l°9\C\+~log2n6*熵功率：如果平均功率舄P的非高斯分布的信源的熵舄h"再熵也舄h的高斯信源的平均功率舄熵功率p<p*速^信源的剩宜余度PF*熵功率不等式：企Ia'""—香農(nóng)公式意義：（1）提高信噪比能增加信道容量，趟於0H寺信道容量趟於M0;（2）^出了照金最吳通信的傅翰速率的理言耕亟限，不胃舄香腹槌限；無(wú)失真信源編碼定理信源編碣-厘編剩宜余度信道編碣-增加剩宜余度—編碼：封信源的原始符號(hào)虜按一定的敷孥關(guān)麒腱行勤務(wù)一碼：（1）碣字；（2）碣元（碣符號(hào)虜）;（3）碣字畏度（碣畏）；—碼的分類：二元碣碣符號(hào)虜集只有0和1麗不重元素等畏非奇巽碣一定是唯―可^碣;用等畏碣封信源S編碣，必硝滿足qWri;燮畏碣、非奇巽碣（碣字都不相同）、奇巽碣（存在相同）、同閽布（每侗碣元的傅酬寺冏都相同）；唯一可^碣:漸近等分割性才蜀立等分怖的隨檄序列S1S2???SN，有ai=(S.S.???S.)€SS???S刖 11121N12N1 1 P-超P0)=-尋。時(shí)(氣七⑸—典型序列集的性質(zhì) g破+.:陪―邱樹(shù)出琨概率趟近1： P(Q,,)〉if,p(G。罰接近等概率分怖：2f"."<侗敷趟近2nM固：(I一3)2心&1、||gM|<2W(眼】—典型序列：|也—H⑸展 -1"(嘰H(S)<—信源編碼IH(S)+E等<^W定理：滿足r1頃畤，富N足豹大則可以^琨/ ")-2e.—< e乎m失真編碣，反之如果n—畤，則不可能^琨照失真編碣，富N足豹大H寺，^碣金最吳概率近似等於1；燮形：(1)llogr>NH(S)只要碣字傅翰的信息量大於信源序列揣帶的信息量，富恩可以^琨e乎M失真編碣；I編碣后信源的信息傅函俞率："信息傅翰率大於信源的熵,才能s^e乎m失真編碣:R'= >W(S)+e_H(S)_H($)77Rr=T— H(S)編碣效率： 寸"(最佳等劇喬〃(S)+「.)信源序列畏度N娉最吳概率的蒯系：D[/(SJ]研/⑴]N~&H\S)(1-^5如果碣畏滿足克拉夫特不等式則一定存在具有是檬碣畏的r元唯一可^勒麻且一定存在一侗具有相同碣畏的即畤碣；一唯一可譯碼的判斷：沒(méi)有一侗彳爰^分解集中包含有碣字；碣C的彳爰^分解集初SJ,S0=C,，「由所有滿足下面麗酬條件的S.備且成：1S'；Si_i=CSi；(沒(méi)有一侗碣字是另一侗碣字的前^)變長(zhǎng)信源編碼定理碣的平均畏度(平均碣畏)L=1= _H（S） _■（$）碣率：'‘心）T,%行（信道每秒篁的信息量）（平均每侗碣元揣帶的信息量；編喝爰信道的信息傅翰率）一無(wú)失真變長(zhǎng)信源（照噪信道）編碼定理（香農(nóng)第一定理）一個(gè)離散無(wú)記憶信源5的N次擴(kuò)展信漏*={%,%,??，,%},其炳為并有碼符號(hào)店…冉}。對(duì)信源S"進(jìn)行編碼，總可以找到一種編碼方法，構(gòu)成唯一可譯碼，使信源S中每個(gè)信源符號(hào)所需的平均碼長(zhǎng)滿足H（S）L.H（S）工1kigrNlogrNn*Nlogr無(wú)失真信源編碼定理可以推廣到平穩(wěn)有記憶信源地"§）〈虹<〃（耳S*“）*±Nlogr~NNlogrN1血顯=—!—lim17/（3&…SQ=%ntrNlogr汽JN' logf如果按照心）=卜g&］來(lái)編碼，則碼長(zhǎng)廈）對(duì)確切的概率分布地矽的均值滿足H（P）+D（P||q）<礎(chǔ)gH（力+D（F||彳）十1其中 只P||g）=?/V）log斜稱為相對(duì)蜻（relativeentropy）word.信源的信息熵是照失真信源厘編的桎限值意羲：在信道信息wm率r不大於信道容量c的情況下，鄉(xiāng)忠能封信源的輸出逵行遹富的褊碼，是的在照噪照揖信道上能照差鰭地以最大信息wm率cwm信息，但要令r大於c刖是不可能的；—編碼效率"(S)Mg一碼曲剩余度5受有噪信道編碼定理費(fèi)^不等式： n[X1')<U以七)log("1)H(PE)-接收到Y(jié)彳爰是否畬屋生PE徭吳的不碓定性；PElog(r-l)-富p建生彳爰，到底是由哪侗翰入符號(hào)虜造成的金最吳的最大不碓定性；富信源信道^定畤，信道疑羲度H(X|Y)就^定了^碣金最吳概率的下限；可通遺重彳復(fù)畿送，使接收端接收消息畤的金昔森減??；logM一信息傳輸率:n一信息傳輸率:logM尸5不附牌心5=瓜)

一碼字距離：畏度舄n的麗侗碣字之冏的距雕指W^ffi字之冏封雁位置上不同碣元的侗敷，通常不胃舄溪明距雕：Dg=W^氣ffiC的最小距離隹:dmin=min(D(Ci,Cj));編ffi邀撐ffi字畤，ffi字冏的距雕越大越好；^ffi規(guī)則、編ffi方法的B>：最小距雕俺可能大；^ffi將收到的序列睪成典之距雕最近的哪侗ffi字;令碣畏足多?畏；一聯(lián)合漸近等分割性對(duì)于任意小的正數(shù)5>0,當(dāng)用足夠大時(shí)，有(1)(2)(3)印(1)(2)(3)印孔0))立7gjgl項(xiàng)P(q(AT))N-S<pg<zFErz】?-叫捫？*]匚p(F)< 明-<12項(xiàng)成叫5<戶(9)<丁而曷7(]_知2川"1?<11^(7)|<事1叩肋(]-坤廿叫微7引Gm(AY)||G皿E政對(duì)于任意小的正數(shù)8K,卸足夠大時(shí)(]) 2*5力q】<理y|X、<2-伸⑴町M月代島心#]號(hào)刊x|y)號(hào)2-n[H(j￥|1，>-2e](2)|任(幻』||女5同||G躊CF|x)||qW*”E如果支和反是統(tǒng)計(jì)獨(dú)立的隨機(jī)序列對(duì),并與P(xy)有相同的邊緣分布，即(xhy)-P(￡)P(y)=P(V)并對(duì)于任意正數(shù)蹌0,當(dāng)內(nèi)足夠大時(shí)有/Ki.y)e 湖I-一有噪信道編碼定理(香農(nóng)第二定理)及其意義有噪信道編碼定理(香農(nóng)第二定理)設(shè)離散無(wú)記憶信道[X,P(y|x),Y],P(yx)為信道傳遞概率，其信道容量為U當(dāng)信息傳輸率&<C時(shí)，只要碼長(zhǎng)旌足夠長(zhǎng)，總可以在輸入X咐號(hào)集中找到M(=2就)個(gè)碼字組成的一組碼(2吧加和相應(yīng)的譯碼規(guī)則，使譯碼的平均錯(cuò)誤概率任意小(PP^0)o設(shè)離散無(wú)記憶信道[X,P(y"),Y],其信道容量為當(dāng)信息傳輸率時(shí)，則無(wú)論碼長(zhǎng)用有多長(zhǎng)，總也找不到一種編碼M(=2吧心使譯碼錯(cuò)誤概率任意小。對(duì)于限帶高斯白噪聲加性信道，噪聲功率為P〃，帶寬為W,信號(hào)平均功率受限為此，則時(shí)，總可以找到一種信道編碼在當(dāng)/?<C=PTlog1+^時(shí)，總可以找到一種信道編碼在信道中以信息傳輸率(碼率)R傳輸信息，而使平均錯(cuò)誤概率任意?。?2)當(dāng)R>C,找不到任何信道編碼，在信道中以/?傳輸信息而使平均錯(cuò)誤概率任意小。封有噪信道編碣定理的^明：?信道容量是可達(dá)的、最大的可靠信息傳輸一信息傳輸率不大于信道容量時(shí)，Pe以指數(shù)趨于0-信息傳輸率大于信道容量時(shí)，Pe以指數(shù)趨于1?香農(nóng)第二定理說(shuō)明錯(cuò)誤概率趨于0的編碼方

法是存在的，但沒(méi)有給出具體的構(gòu)造方法。一聯(lián)合信源信道編碼定理及其意義如果S『（S|S?…S「）是有限符號(hào)集的隨機(jī)序列并滿足漸近等分割性，乂信源S極限觸*則存在信源和信道編碼，其乙TO。反之，對(duì)于任意平穩(wěn)隨機(jī)序列，若極限廁則錯(cuò)誤概率遠(yuǎn)離0,即不可能在信道中以任意小的錯(cuò)誤概率發(fā)送隨機(jī)序列,保真度準(zhǔn)則下的信源編碼一失真度d（ui,vj）^0（單個(gè)符號(hào)）一失真矩陣一平均失真度：某個(gè)信源在某一試驗(yàn)信道下的失真大小;D=五［t/（外，七）］=E［d（u^v）\B=￡p（uv）dWj）=￡￡P(guān)（uJPG7」|丹）刁（％巧）uy s=ij=i畏度舄N的信源符號(hào)虜序列的失真函敷：N

d(u,v)= =￡d(%"h)/=i畏度舄N的信源符號(hào)虜序列的平均失真度：TOC\o"1-5"\h\zD(N)=￡[rf(u,v)]=￡P(guān)(uv)d(ii,v)=￡P(guān)(u)尸(v|u)d(u,v)ufv u,v罩侗符號(hào)虜?shù)钠骄д娑龋撼?G(如=土￡￡尸(W(0 )信源和信道都是照言己噫的，N舄信源序列的平均失真度：_ N_d(n)=￡q信源的平均失真度： ''離散平穩(wěn)信源萬(wàn)3)=M3保真度準(zhǔn)則，平均失真度不大于所允許的失真萬(wàn)WON維信源序列的保真度準(zhǔn)則DgWNDD失真許可的試驗(yàn)信道，滿足保真度準(zhǔn)則的試驗(yàn)信道 "腫g丐一信息率失真函數(shù)的定義：在滿足保真度率則下，信源信息傅翰率的下限是多少；R(O)=min{I(U;V)}F(v^u^Bd心件㈤腰挪u；v)}信息率失真函數(shù)和信道容量具有呈寸偶性:信息傳輸理論率失真理論信道P=[P。法)]失真測(cè)度d(u,v)信源P=(P(w))信源P=(P(x))信道P=[P(yg)]碼C:MTX"信源碼C"tC錯(cuò)誤概率PE平均失真度dn信道容量C=max1(尸(工))FG)C=maxI(P(x))坦工工瓦才之芷[率失真函數(shù)R(D)=minI(P(v\w))P(y]u)^BDR<C信道編碼定理R>R(D)信源編碼定理其他性W：(1)在一定的束，條件下是平均互信息的槌小值；非劊性，下限值部;富R(D)=0畤，所封雁就是平均失真度的上界Dmax；R(D)是允^失真度。的凸函敷；R(D)在定羲域內(nèi)速^；R(D)是霰格的罩^遁減函敷；一保真度準(zhǔn)則下的信源編碼定理(香農(nóng)第三定理)及其意義設(shè)&(Q)為一離散無(wú)記憶平穩(wěn)信源的信息率失真函數(shù)，并且有有限的失真測(cè)度。對(duì)于任意次0,￡>0,及任意足夠長(zhǎng)的碼長(zhǎng)小則一定存在一種信源編碼G其碼字個(gè)數(shù)為M=段”【乩功*】｝而編碼后的平均失真度d(C)<D+^反之，不存在平均失真度為D,而平均信息傳輸率7?5(。)的任何信源碼。即對(duì)任意碼長(zhǎng)為m的信源碼G若碼字個(gè)數(shù)M<2^一定有d(C)>D意S：^明在允^失真。的，條件下，信源最小的，可^的信息傅翰率是信源的R(D)。一聯(lián)合有失真信源信道編碼定理及其意義.香腹第一定理+香腹第二定理：只要信道的信道容量大於信源的槌限熵，就能在信道中做到有效地、照金最吳地傅翰信息；分麗步編碣虔理方法典一步虔理方法效果一檬好；.香腹第三定理+香腹第二定理：(1)如果信源的槌限熵大於信道的信道容量，只要在允^一定失真的，條件下，仍能做到有效和可靠地傅翰信息；如此可矗帚納出信息傅翰定理：雕散照言可意信源S的信息率失真函數(shù)舄R(D),雕散照言己噫信道的信道容量舄^如果滿足：C>R(D)則信源翰出的信源序列能再次信道翰出端重琨，其失真小於等於D。雕散照言己噫信源S,其信息率失真函敷舄R(D)比特1/信源符耽每秒翰出丁』固信源符號(hào)虜；雕散照御噫信道的1信道容量舄C比特/信道符耽每秒傅毓勺固信道符耽如果滿足：CR(D)則信源翰出的信息能再此信道翰出端重最其失真小於等於D。雕散照言己噫信源S,其信息率失真函敷舄R(D)比特1/信源符耽每秒翰出T.施信源符號(hào)虜；雕散照御噫信道的

1信道容量舄C比特/信道符耽每秒傅藏勺固信道符耽如果滿足：CR（D）則在信道輸出端不能以失真小於等於D再現(xiàn)信源輸出的信息。^用意S：（1）保真度率則下的信源編碣定理是有失真信源厘編的理^基磴；（2）在允^―定失真度的情〉兄下，信源的信息率失真函數(shù)可以作舄衡量各不重厘編編碣方法性能僵劣的一才重尺度；一信息率失真函數(shù)的計(jì)算:.對(duì)稱信源（漢明失真）二元呈樸胃信源的信息率失真函敷:R(D)=H(a))-H(D)0<D<aR(D)=0 D>￡t)r元耕胃信源的信息率失真函敷:R(D)=logr-Dlog(r-l)-27(D)O<Z)<1--R(D)=￡>>!--.高斯信源（平方誤差失真）0D>a2

無(wú)失真的信源編碼照失真信源編碣-熵編碣.信源概率分怖是不均勻的；（頃2…（頃2…，q）邀撐每侗碣字的畏度4,滿足：/產(chǎn)log是檬的碣畏必定滿足滿足克拉夫特不等式，一定存在即畤碣;平均碣畏不超遺上界：Lavr<Hr(S)+1?門(mén)畤，香腹編碣的平均碣畏才p⑶)=富滿足信源概率分怖舄?門(mén)畤，香腹編碣的平均碣畏才能^到槌限值；一般情〉兄下，香腹編碣德島的不是B^ffio一二元哈夫曼碼?將q個(gè)信源符號(hào)按概率分布的大小，以遞減次序排列?把o和1分別分配給概率最小的兩個(gè)信源符號(hào)，并將這兩個(gè)信遮曾號(hào)合并成一個(gè)新符號(hào)，新符號(hào)的概率是這兩個(gè)唐源神號(hào)的概率之和，從而得到只包含時(shí)個(gè)符號(hào)的新信源，稱為信源s的縮減信源S]-將縮減信源s的符號(hào)仍按概率大小以遞減次序排列，再將。和1分別，配給其概率最小的兩個(gè)符號(hào)，并將這兩個(gè)符號(hào)合并成一個(gè)新符號(hào)，得到包含g-2個(gè)符號(hào)的縮減信源&?依次繼續(xù)，直到縮減信源只包含兩個(gè)符號(hào)為止，將。和1分別分配給最后兩個(gè)符號(hào)源開(kāi)始，依編碼路徑由后向前返回,對(duì)應(yīng)的碼手源開(kāi)始，依編碼路徑由后向前返回,對(duì)應(yīng)的碼手俺志主：(1)得到的碣不是唯一；如果合餅彳爰典其他信源符號(hào)虜概率相同，雁排前；保^了概率大得符號(hào)溉寸雁短喝概率小封雁畏喝令短碣得到充分的利用；每次編減信源的最彳爰麗侗碣字只有最彳爰一侗碣元不同；每次編減信源的最畏麗侗碣字的碣畏相同；一r元哈夫曼碼-每次把I?個(gè)概率最小的符號(hào)合并成一個(gè)信源符號(hào),并分別分配0,1,…,(r?l"?/r