信息论复习笔记

1・绪论信息论回答了通信的两个最基本问题:（1） 数据压缩的极限；（2） 信道传输速率的极限;信息、消息和信号消息：信息的載體（能被感知和理解、進行傳遞和獲取）信息：事物運動狀態或存在方式的不確定性的描述（香農）先驗概率:P（ai）自信息：Ka^log;（信息接收的不確定性）互信息：1（印也）=log[P：（%）]-log[Pi（ajbi）];（信息接收的多少度量）（若信道無干擾，則互信息等於自信息等於0）優點：明確的數學模型、定量計算;缺點：有適用範缺點：有適用範信號；通信系统的模型

信源发送变换器信宿信源发送变换器信宿通信系统的基本要求:有效、可靠、保密、认证2・离散信源及其信息测度-离散信源的定义：輸出信息數有限、每次只輸岀一個;一自信息的定义及物理意义事件發生前：事件發生的不確定性;事件發生后：時間含有的信息量；信息爛的定义及物理意义，信息爛的基本性质定義：自信息的數學期望(H(X)=-2[P(ai)logP(ai)]定義：自信息的數學期望(H(X)=-2[P(ai)logP(ai)])信源的總體信息測度每個消息所提供的平均信息量；(2)信源輸出前，信源的平均不確定性;

性質：(1)對稱性；(2)確定性；非負性；(4)擴展性(可拆開)；(5)可加性；[H(XY)=H(X)+H(Y)](6)強可加性；[H(XY)=H(X)+H(Y|X)](7)遞增性;(7)遞增性;(8)極值性；[H(p1,P2,P3…,Pc)WH(q】,,…，q】)=logq]«■■■■»一离散无记忆信源的扩展信源—扩展信源的爛H(X)=NH(X)一离散平稳信源：联合概率分布与时间起点无关；:联合爛H(X1X2)=EEP(aiaj)logP(aiaJ)条件爛H(X2|X1)=-EEP(a1aj)logP(ai|%)关系:H(X1X2)=H(X1)+H(X21XJ爛率:离散平稳信源的极限爛=limH(XN|X1X2---XN.1)—马尔可夫信源:某一时刻的输出只与此刻信源所处的状态有关而与以前的状态及以前的输出符号都无关—马尔可夫信源的矯:%+严H(XtIXiXfXJ—信源剩余度爛的相对率n=H爛的相对率n=H极限/H。信源剩余度(辅出符号间依赖强度)Y=l-r|=1-Hjjj^/Ho信源剩余度3・离散信道及其信道容量

—H(X;Y)=H(X)・H(X|Y)一离散信道的数学模型►信道X=(召必，…,占,…冷)PQ►信道X=(召必，…,占,…冷)PQIx)Z：P(y|x)=iY=(鸥…必…豹F:[^，VA]一信道矩阵性質(1)P(a1bj)=P(a1)P(b]|ai)=P(bj一信道矩阵性質(1)P(a1bj)=P(a1)P(b]|ai)=P(bj)P(ai|bj；[P(bi)][P(b2)][P(b3)]=[][P(bs)][P(ai)][P(a2)][P(a4)][P(ar)]輸出端收到的任一©—定是輸入符號a「中的某一個送入信道；一信道疑义度的定义：收到丫後對變量X尚存在的平均不確定性:H(X|Y)=E[H(X|切卜刀P(xy)lo『P(X|Y)物理意义:噪聲造成的影響大小；平均互信息的定义：收到丫後平均每個符號獲得的關於X的信息量(物理意義：反映輸入輸出兩個隨機變量之間的統計約束I(X;Y)=H(X)-H(X|Y)=刀P(xy)P(y|x)P」(y)

無噪一一對應信道中：I(X;Y)=H(X)=H(Y)=O信道容量的定义:信道每秒鐘平均傳輸的信息量稱為信息傳輸速率，最大信息傳輸率稱為信道容量；一信道容量的计算:无噪信道（求H（X）極值）:C=logr对称信道（信道矩陣的每一行或列是另一行或列的置換）:C=logs・H（Pi,p2,・・・,pJ强对称信道:C=logr-plog（r-l）-H（p）;准对称信道：C=logr-H(p1,p2,---,ps)•刀NklogMNk是第k個子矩陣行元素之和，Mk是第k個子矩陣列元素之一般离散信道（對所有可能的輸入概率分佈求平均互信息的最大值）:C=X-Floge條件：I(xi；Y)=&j*p(bj|aJ*log[P(bj|ai)/P(bj)]wC一般离散信道当尸$,并FL一般离散信道当尸$,并FL信道矩阵P是非奇异阵时,信道容虽1212345计算0（/=1,2,…』）计算冶道容屋C的计算步骤如F：£尺勺©）“严£/^|叩嗨円坊河）（“12…』）c七工2色计算输出概率分布P（£）（M2・・・Q计算输入概率分布P（勺）（/=1,2,.-Z）如果％胆0（匸12・.$即可结束计算，第2步计算的C即为信道容量：否则要重新计算 „萬散无记忆信道容量的迭代算法(S.Arimoto,R.E.Blahut,1972)如卜:选择初始概率分布砂⑷,也屮匕)计算C(时M)和CS+M)■•匸~「、， p(%Ja=cxp?^|flJ，nZW^)J• t •C(n+1,”)■In工Pg)a,C*(n+l,n)=In^maxaj3.判断C(/i+1m)CS+1m)V£.如果成立，转第5步;否则转第4步4•计算然后转第2步%”5.信道容量C=C(n+L/i),结束—数据处理定理如果X、丫、Z组成一个马尔科夫链，则有I(X;Z)<I(X;Y)I(X;Z)<I(Y;Z)信息不増性原理一般的数据处理原理—信道剩余度＜C-I(X;Y)相对剩余度=1-I(X;Y)/C无损信道的相对剩余度=l-H(X)/logr4・波形信源和波形信道連縉信源的相對爛：h(X)A=-/Rp(x)logp(x)dx波形信源的差爛: h(x(t))A・limN*h(XiX2・・・XN)连续信源的差爛:均匀分布连续信源的差爛:小—

连续信源的差爛:均匀分布连续信源的差爛:小—

pW=<b-a0a<x<bothersh(X)=\og(b-a)Nh(X)=\og(b-a)N維均勻分佈：九G¥)=2Flog(b-°)1\l27rcr2g2a21\l27rcr2g2a2高斯信源的差爛:pM=h(X)=logy/ljro^+—loge=—log2/recr2

h(X)=-\0R2^ePN維高斯信源的差嫡:A(X)=llog(2^f|C|

\C\=tlaiN N"(X)二牙log2龙和罔…分)”仁为加尤)2 /=!差爛的性质:(1)可加性；(2)凸性;(3)可負性；(4)變換性(X1->X2)差爛會變化);(5)極值性:離散信源的信源符號等概率分佈時信源的矯最大;連給信源:•當峰值功率受限為b時(輸出信號的瞬時電壓限制為土(p)1/2),此時餅輸出的連砂機變虽限制钿bj內信源具有最大爛h-log(b-a)如果隨機矢量取值受限，則各隨機分董統計獨立并均勻分佈時具有最大埔；當信源輸出信號的平均功率被限定為P,則其信號幅度的概率密度分佈為高斯分佈時，信源有最大爛:h=l/2*log2nePN維連縉平穩信源如果其N維隨機序列的協方差矩陣C被限定,則N維隨機矢量為正太分佈時信源的烦最大。也就是N維高斯信源的爛最大,其值為1 N~log\C\+—logine*爛功率：如果平均功率為P的非高斯分佈的信源的爛為h,稱爛也為h的高斯信源的平均功率為爛功率2nP<P*連緡信源的剩餘度P-7*爛功率不等式:g2/i(X+Z)>e2h(X)+e2h(Z)—香农公式意义：（1）提高信噪比能增加信道容量,趨於0時信道容量趨於無窮；（2）給出了無錯誤通信的傳輸速率的理論極限，稱為香農極限；Eb£=bi2u0.6931No10®(斜=10lg(ln2)«-1.6dB5・无失真信源编码定理信源編碼壓縮剩餘度信道編碼-增加剩餘度-编码：對信源的原始符號按一定的數學規則進行變換；一码：（1）碼字；（2）碼元（碼符號）；（3）碼字長度（碼長）；一码的分类：二元碼碼符號集只有0和1兩種元素等長碼等長非奇異碼一定是唯一可譯碼；用等長碼對信源S編碼，必須滿足q灯；變長碼、非奇異碼（碼字都不相同）、奇異碼（存在相同）、同價碼（每個碼元的傳輸時間都相同）；唯一可譯碼：渐近等分割性獨立等分佈的隨機序列S1S2...SN,有ai=（SnSi2---SiN）€S]S2・・・Sn則1 1 p一币logP(a"=一币logP(SgSi2・・・Sg)tH(S)%：-典型序列集的性质出現概率趨近1:接近等概率分佈:2-N["(g]<F&)<2川【"(》】個數趨近出現概率趨近1:接近等概率分佈:2-N["(g]<F&)<2川【"(》】個數趨近2NH個:(1_5)2・回》S2助㈤T-典型序列:-H(S)-信源编码等長編碼定理：滿足£»鵲竺時，當N足夠大則可以實現幾乎無失真編碼，反之如果!<芈上竺時，則不可能實現無失真Nlogr編碼，當N足夠大時，譯碼錯誤概率近似等於1；變形:)llogr>NH(S):只要碼字傳輸的信息量大於信源序列攜帶的信息量，總可以實現幾乎無失真編碼；(2)編碼后信源的信息傳輸率:R，=glogir(3)信息傳輸率大於信源的爛，才能實現幾乎無失真編碼:

R'-百R'-百logr>H(S)+r編碼效率••占®」(S)信源序列長度N與錯誤概率的關係：皿（£）］D［心）］〃2N>———=H2(s)(1—小26一克拉夫特不等式：Mil厂H2(s)(1—小26如果碼長滿足克拉夫特不等式,則_定存在具有這樣碼長的「元唯一可譯碼，且一定存在一個具有相同碼長的即時碼;一唯一可译码的判断：沒有一個後綴分解集中包含有碼字碼C的後綴分解集為{S.},So=c,s由所有滿足下面兩個條件的S組成:SiSfc;Sm=CSi；（沒有一個碼字是另一個碼字的前綴）-变长信源编码定理碼的平均長度（平均碼長）碼率:R碼率:R=H(X)=竽尺=畔（信道每秒鐘的信息量）（平均每個碼元摘帶的信息量;編碼後信道的信息傳輸率）-无失真变长信源（無噪信道）编码定理（香农第一定理）一个离散无记忆信源S的N次扩展信源仁佃耳，…叫｝，其爛为//⑶），并有码符号衣｛X］七，…耳｝。对信源S"进行编码，总可以找到一种编码方法，构成唯一可译码，使信源S中每个信源符号所需的平均码长满足竺占<竺+丄logrN logrNNf®N logr无失真信源编码定理可以推广到平稳有i己忆信源H(S、Sj・SJJn<H(S比…SJ、】TVlogrNTVlogrN2N云処沪（昭…s”）=logr如果按照心吨而2N云処沪（昭…s”）=logr如果按照心吨而來编码，则码长心）对确切的概率分布PG）的均值满足〃(P)+D(PIS)S易[/($)]<H(P)+Q(P||g)+1其中其中称为相对爛(relativeentropy)信源的信息埔是無失真信源壓縮的極限值意義：在信道信息傳輸率R不大於信道容量C的情況下，總能對信源的輸出進行適當的編碼，是的在無噪無損信道上能無差錯地以最大信息傳輸率C傳輸信息，但要令R大於C則是不可能的；-编码效率_H(S)耳-llogr一码的剩余度1 1g)1 "一1llogr6・有噪信道编码定理費諾不等式：H（jf|r）＜n（^）+^iog（r-i）H（P』按收到丫後是否會產生Pe錯誤的不確定性；PElog（r-l）-@PE發生後，到底是由哪個輸入符號造成的錯誤的最大不確定性；當信源信道給定時，信道疑義度H（X|丫）就給定了譯碼錯誤概率的下限；可通過重複發送，使接收端接收消息時的錯誤減小；信息传输率：R單位時間傳輸的信息量

信息传输率：R單位時間傳輸的信息量一码字距离：長度為n的兩個碼字之間的距離指兩個碼字之間對應位置上不同碼元的個數，通常稱為漢明距離:nDG，Cj)匹见㊉址k—1碼C的最小距離：dmin=min{D(Ci,Cj)}；編碼選擇碼字時，碼字間的距離越大越好；譯碼規則、編碼方法的選擇:(1)最小距離儘可能大；(2)譯碼將收到的序列譯成與之距離最近的哪個碼字；(3)令碼長足夠長；-联合渐近等分割性对于任意小的正数咗0,8>0,当刀足够大时.有(1)尸(G.m))m(2)(3)2-<P(x)<(2)(3)<只丿)<2^H(rhg}<P(xy)<(1-5)2曲1S||G,,(X)||S2诃g】(1_§)2诃g)<||G“(y)|S2MW(rH<,(1_5)2啊"卜・】<||G“(JtT)||<2诃RM)对于任意小的正数£爼)，办足够大时(1) 2""(,/<r,XH2<,<p(y11)<2・."(皿》2引(2) ||S(X|y)||s2衲5"町如果录和y是统计独立的随机序列对，并^P(xy)有相同的边缘分布，即(人刃-P(幻p(y)・Hiy)则并对于任意正数&N0,当”足够人时有M(ty)eG^XY)］z(1-有噪信道编码定理(香农第二定理)及其意义有噪信道编码定理(香农第二定理)设离散无记忆信道［X,P(y|x),Y］,P(y|x)为信道传递概率，其信道容量为C。当信息传输率RvC时，只要码长刃足够长，总可以在输入X"符号集中找到M(=2“9个码字组成的一组码(2欣/)和相应的译码规则，使译码的平均错误概率任意小(PE->0)o设离散无记忆信道［X,P(y|x)，Y］，其信道容量为C。当信息传输率QC时，则无论码长川有多长，总也找不到一种编码M(=2”R,/0,使译码错误概率任意小。

芻豔饕畿｛，嘴信道’噪声功率为P”’帑宽为W'信（］）当R<C=JVlog1+（］）当R<C=JVlog1+总可以找到一种信道编码在信道中以信息传输率（码率）R传输信息,任意小；而使平均错误概率漏盘鶴轟2衆何信道编码'在信道中以R传输信息而對有噪信道編碼定理的說明：•信道容量是可达的.最大的可靠信息传输率-信息传输率不大于信道容量时，Pe以指数趋于0-信息传输率大于信道容量时，P卜以指数趋于1•背农第二定理说明错误概率趋于0的编码方法是存在的，但没有给出具体滋构拓分狂。-联合信源信道编码定理及其意义如果SFS&2…SJ是有限符号集的随机序列并满足渐近等分割性，又信源S极限<C则存在信源和信道编码，其匕->0。反之，对于任意平稳随机序列，若极限婀仁〉C,则错误概率远离0,即不可能在信道中以任意小的错误概率发送随机序列。7.保真度准则下的信源编码—失真度d（UbVj]^0（单个符号）一失真矩阵d（“2,片）〃（色川2）…d（“2,叫）• •• •• •他*2）…他，匕）-平均失真度：某个信源在某一试验信道下的失真大小；D=£[J（w.,vy）]=£[</（«,v）]D=工P（uv）d（u,v）=£ （叫）P（匕I“Jd（勺,vy）uy m長度為N的信源符號序列的失真函數：Nd(u,v)=卩)=》d%0j)/-I長度為N的信源符號序列的平均失真度:D(N)=E[d(u,v)]=工P(uv)J(u,v)=^P(u)P(v|u)d(u,v)uy uy單個符號的平均失真度：vv_ 1 _ ］尸 5久=-W)=-2Z^rN N仕i冃信源和信道都是無記憶的，N為信源序列的平均失真度:万(n)=£b/-I信源的平均失真度：_1-八/=1离散平稳信源b(N、=Nb保真度准则，平均失真度不大于所允许的失真N维信源序列的保真度准则b(N、SNDD失真许可的试验信道，满足保真度准则的试验信道斫{®|iO：DSQ}-信息率失真函数的定义：在滿足保真度準則下，信源信息傳輸率的下限是多少；&巧=min{/(t/；V)}P(叩斗)込心』®V)}信息率失真函數和信道容量具有對偶性:信息传输理论率失真理论信道P=[P(y\x)]失真测度如)信源p=(P(M))信源"(P(x))信道P=[P(v|w)J码信源码C\UNtC错误概率PE 1平均失真度万v信道容量C=max/(P(x))C-maxZ(P(x))P{xYE[X2^P3率失真函数R(D)=min/(P(v|w))P(v|m*BdR<C信道编码定理R>R(D)信源编码定理其他性質：(1)在一定約束條件下是平均互信息的極小值；(2)非負性，下限值為0；(3)當R[D)=O時，所對應就是平均失真度的上界Dmax；(4)R(D)是允許失真度D的凸函數;(5)R(D)在定義域內連縉;(6)R(D)是嚴格的單調遞減函數；-保真度准则下的信源编码定理(香农第三定理)及其意义设/?(D)为一离散无记忆平稳信源的信息率失真函数，并口有有限的失真测度。对于任意D20,e>0,§>0及任意足够长的码长n,则一定存在一种信源编码C,其码字个数为M=而编码后的平均失真度反之，不存在平均失真度为D，而平均信息传输率R'<R(D)的任何信源码。即对任意码长为川的信源码C,若码字个数M<2阿巧一定有d(C)>D意義：說明在允許失真D的條件下，信源最小的，可達的信息【輸率是信源的R(D)【輸率是信源的R(D)-联合有失真信源信道编码定理及其意义.香農第一定理+香農第二定理:(1)只要信道的信道容”於信砂殛限颅,就能在信道中做到有效地、無錯誤地傳輸信息；)分兩步編碼處理方法與一步處理方法效果一樣好)分兩步編碼處理方法與一步處理方法效果一樣好.香農第三定理+香農第二定理：(1)如果信源的極限爛大於信道的信道容量，只要在允許一定失真的條件下，仍能做到有效和可靠地傳輸信息；如此可歸納出信息傳輸定理：(1)離散無記憶信源S的信息率失真函數為R(D),離散無記憶信道的信道容量為C,如果滿足:C>R(D)

則信源輸出的信源序列能再次信道輸出端重現，其失真小於等於D。(2)離散無記憶信源S,其信息率失真函數為R(D)比特/信源符號，每秒輸出右個信源符號；離散無記憶信道的信道容量為C比特/信道符號，每秒傳輸右個信道符號，如果滿足：CR(D)—>則信源輸出的信息能再此信道輸出端重現，其失真小於等於D。(3)離散無記憶信源S,其信息率失真函數為R(D)比特/信源符號，每秒輸出右個信源符號；離散無記憶信道的信道容量為C比特/信道符號，每秒傳輸右個信道符號，如果滿足：CR(D)—<則在信道輸出端不能以失真小於等於D再現信源輸出的is息。實用意義：(1)保真度準則下的信源編碼定理是有失真信源壓縮的理論基礎(2源壓縮的理論基礎(2)在允許一定失真度的情況下，信源的信息率失真函數可以作為衡量各種壓縮編碼方法性能優劣的一種尺度；T言息率失真函数的计算:・对称信源（汉明失真）二元對稱信源的信息率失真函數:R(D)=HQ)-H(D)R(D)=HQ)-H(D)0<D<a)0 D>cdr元對稱信源的信息率失真函數:logr-Z)log(rr元對稱信源的信息率失真函數:logr-Z)log(r一1)一//(D)R(D)=，0D>\--.高斯信源（平方误差失真）/?(»)=<0D<a2/?(»)=<0D<a2D>a28.无失真的信源编码無失真信源編碼爛編碼.信源概率分佈是不均勻的；・信源是由記憶的，具有相關性；・香農編碼：選擇每個碼字的長度滿足:選擇每個碼字的長度滿足:這樣的碼長必定滿足滿足克拉夫特不等式,一定存在即時碼；平均碼長不超過上界：Lavr<Hr⑸+1當滿足信源概率分佈為P(Si)=日5時，香農編碼的平均碼長才能達到極限值；一般情況下，香農編碼德島的不是緊緻碼。_二元哈夫■码•—将g个希符号按概率分布的大小，以递减次序排列•把0和1分别分配给概率最小的两个信源符号，并将这两信源，称为信源S的缩减信源S]•将缩减信源S|的符号仍按概率大小以递减次序排列，再将0和1分别亦配给其概率最小的两个符号，并将这两个符号合并成一个新符号，得到包含”2个符号的缩减信源$2•狷决继续，直到缩减信源只包含两个符号为止，将0和1分别分配给最后两个符号•给噩福繚鞠飜議编码路径由后向前返回'備註：(1)得到的碼不是唯一；(2)如果合併後與其他信源符號概率相同，應排前；

(3)保證了概率大得符號對應短碼，概率小對應長碼，令短碼得到充分的利用；(4)每次縮減信源的最後兩個碼字只有最後一個碼元不同；(5)每次縮減信源的最長兩個碼字的碼長相同；~r元哈夫曼码•每次把r个概率最小的符号合并成一个信源符号，并分别分配0,1,(r-l)o•最后一步的缩减信源必须有I•个信源符号,因此信源S的符号个数g必须满足g=(厂一1)0+厂对于给定分布的任何信源，存在一个最佳二元即时码(其平均码长最短),此码满足以下性质^(2)两个最小概率的信源符号所对应的码字必具有相同的码(2)两个最小概率的信源符号所对应的码字必具有相同的码长。(3)两个垠小概率的信源符号所对应的码字，除故后一位码元不同外，