信息论复习笔记

1、1. 绪论信息论回答了通信的两个最基本问题:（1） 数据压缩的极限；（2） 信道传输速率的极限；信息、消息和信号消息：信息的載體（能被感知和理解、進行傳遞和獲取）信息：事物運動狀態或存在方式的不確定性的描述（香農）先驗概率：P(ai)自信息：I(ai)=logP-1(ai)； （信息接收的不確定性）互信息：I(ai;bi)= logP-1(ai)- logP-1(ai|bi);（信息接收的多少度量）（若信道無干擾，則互信息等於自信息等於0）優點：明確的數學模型、定量計算；缺點：有適用範圍；信號；通信系统的模型通信系统的基本要求:有效、可靠、保密、认证2. 离散信源及其信息测度 离散信源的定义：

2、輸出信息數有限、每次只輸出一個； 自信息的定义及物理意义事件發生前：事件發生的不確定性；事件發生后：時間含有的信息量；信息熵的定义及物理意义,信息熵的基本性质定義：自信息的數學期望（ H(X)= - P(ai)logP(ai) ）信源的總體信息測度（1） 每個消息所提供的平均信息量；（2） 信源輸出前，信源的平均不確定性；性質：（1） 對稱性；（2） 確定性；（3） 非負性；（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)= lo

3、gq 等概率分佈信源的平均不確定性最大，稱為最大離散熵定理； 离散无记忆信源的扩展信源 扩展信源的熵 H(X) = NH(X) 离散平稳信源：联合概率分布与时间起点无关；熵：联合熵 H(X1X2)=P(aiaj)logP(aiaj)条件熵 H(X2|X1)=-P(aiaj)logP(ai|aj)关系：H(X1X2)=H(X1)+H(X2|X1)熵率:离散平稳信源的极限熵 = limH(XN|X1X2XN-1) 马尔可夫信源:某一时刻的输出只与此刻信源所处的状态有关而与以前的状态及以前的输出符号都无关； 马尔可夫信源的熵：Hm+1=H(Xm+1|X1X2Xm) 信源剩余度 熵的相对率 = H极限

4、/H0信源剩余度 （输出符号间依赖强度）= 1-=1-H极限/H03. 离散信道及其信道容量 H(X;Y)=H(X)-H(X|Y) 离散信道的数学模型 信道矩阵性質（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) （rs） P(bs) P(ar) （3） 輸出端收到的任一bj一定是輸入符號ar中的某一個送入信道； 信道疑义度的定义：收到Y後對變量X尚存在的平均不確定性：H(X|Y)=EH(X|bj)=P(xy)log-1P(X|Y)物理意义:噪聲造成的影響大小； 平均互信息的定义：收

5、到Y後平均每個符號獲得的關於X的信息量（物理意義：反映輸入輸出兩個隨機變量之間的統計約束關係）：I(X;Y)= H(X)-H(X|Y) = P(xy)P(y|x)P-1(y)無噪一一對應信道中：I(X;Y)=H(X)=H(Y)0 信道容量的定义：信道每秒鐘平均傳輸的信息量稱為信息傳輸速率，最大信息傳輸率稱為信道容量； 信道容量的计算: 无噪信道(求H(X)極值)：C = logr 对称信道（信道矩陣的每一行或列是另一行或列的置換）：C = logs-H(p1,p2,ps) 强对称信道：C = logr-plog(r-1)-H(p)； 准对称信道：C = logr-H(p1,p2,ps)-Nkl

6、ogMk （Nk是第k個子矩陣行元素之和，Mk是第k個子矩陣列元素之和） 一般离散信道（對所有可能的輸入概率分佈求平均互信息的最大值）：C =loge條件：I(xi;Y) = sj=1P(bj|ai)*logP(bj|ai)/P(bj) C 数据处理定理如果X、Y、Z组成一个马尔科夫链，则有I(X;Z)I(X;Y)I(X;Z)I(Y;Z)信息不增性原理一般的数据处理原理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. 波形信源和波形信道連續信源的相對

7、熵: h(X) = Rp(x)logp(x)dx 波形信源的差熵： h(x(t) =limN-h(X1X2XN)连续信源的差熵：均匀分布连续信源的差熵:N維均勻分佈：高斯信源的差熵：N維高斯信源的差熵：差熵的性质：（1）可加性；（2）凸性；（3）可負性；（4）變換性（X1-X2,差熵會變化）；（5）極值性：離散信源的信源符號等概率分佈時信源的熵最大;連續信源：當峰值功率受限為p時（輸出信號的瞬時電壓限制為(p)1/2），此時信源輸出的連續隨機變量限制在a,b內，信源具有最大熵：h=log(b-a)如果隨機矢量取值受限，則各隨機分量統計獨立并均勻分佈時具有最大熵； 當信源輸出信號的平均功率被限定

8、為P，則其信號幅度的概率密度分佈為高斯分佈時，信源有最大熵：h=1/2log2ePN維連續平穩信源如果其N維隨機序列的協方差矩陣C被限定，則N維隨機矢量為正太分佈時信源的熵最大。也就是N維高斯信源的熵最大，其值為12log|C|+N2log2e* 熵功率：如果平均功率為P的非高斯分佈的信源的熵為h，稱熵也為h的高斯信源的平均功率為熵功率P=12e2hPP* 連續信源的剩餘度 P-P* 熵功率不等式：e2h(X+Z)e2h(X)+e2h(Z) 香农公式意义：（1）提高信噪比能增加信道容量，趨於0時信道容量趨於無窮；（2）給出了無錯誤通信的傳輸速率的理論極限，稱為香農極限；EbN0=ln20.69

9、3110lgEbN0=10lgln2-1.6dB5. 无失真信源编码定理信源編碼 壓縮剩餘度信道編碼 增加剩餘度 编码：對信源的原始符號按一定的數學規則進行變換； 码：（1）碼字；（2）碼元(碼符號)； （3）碼字長度（碼長）； 码的分类：二元碼 碼符號集只有0和1兩種元素等長碼等長非奇異碼一定是唯一可譯碼；用等長碼對信源S編碼，必須滿足qrl；變長碼、非奇異碼（碼字都不相同）、奇異碼（存在相同）、同價碼（每個碼元的傳輸時間都相同）；唯一可譯碼： 渐近等分割性 獨立等分佈的隨機序列S1S2SN，有i=(Si1Si2SiN)S1S2SN 則-1NlogP(i)=-1NlogP(Si1Si2SiN

10、)PH(S) 典型序列集的性质出現概率趨近1： ，接近等概率分佈：個數趨近2NH個： 典型序列： 信源编码等長編碼定理：滿足lNH(S)+logr 時，當N足夠大則可以實現幾乎無失真編碼，反之如果lNH(S)-2logr 時，則不可能實現無失真編碼，當N足夠大時，譯碼錯誤概率近似等於1；變形：（1）llogrNH(S)：只要碼字傳輸的信息量大於信源序列攜帶的信息量，總可以實現幾乎無失真編碼；（2）編碼后信源的信息傳輸率：R，=lNlogr（3）信息傳輸率大於信源的熵，才能實現幾乎無失真編碼：R，=lNlogrH(S)+編碼效率：H(S)RH(S)lNlogr（最佳等長碼H(S)H(S)+）信源

11、序列長度N與錯誤概率的關係：NDI(Si)2=DI(si)H2(S)2(1-)2 克拉夫特不等式：i=1qr-li1如果碼長滿足克拉夫特不等式，則一定存在具有這樣碼長的r元唯一可譯碼，且一定存在一個具有相同碼長的即時碼； 唯一可译码的判断：沒有一個後綴分解集中包含有碼字；碼C的後綴分解集為Si，S0=C，Si由所有滿足下面兩個條件的Si組成：（1）Si-1Si=c；（2）Si-1=CSi；（沒有一個碼字是另一個碼字的前綴）变长信源编码定理碼的平均長度（平均碼長）Li=1qP(Si)li碼率： R=H(X)=H(S)L，Rt=H(S)tL (信道每秒鐘的信息量)(平均每個碼元攜帶的信息量;編碼後

12、信道的信息傳輸率) 无失真变长信源（無噪信道）编码定理(香农第一定理) 信源的信息熵是無失真信源壓縮的極限值意義：在信道信息傳輸率R不大於信道容量C的情況下，總能對信源的輸出進行適當的編碼，是的在無噪無損信道上能無差錯地以最大信息傳輸率C傳輸信息，但要令R大於C則是不可能的； 编码效率H(S)Llogr 码的剩余度1-=1-H(S)Llogr6. 有噪信道编码定理費諾不等式：H(PE)接收到Y後是否會產生PE錯誤的不確定性；PElog(r-1)當PE發生後，到底是由哪個輸入符號造成的錯誤的最大不確定性；當信源信道給定時，信道疑義度H(X|Y)就給定了譯碼錯誤概率的下限；可通過重複發送，使接收端

13、接收消息時的錯誤減小； 信息传输率： R=logMn（單位時間傳輸的信息量：Rt=logMnt） 码字距离：長度為n的兩個碼字之間的距離指兩個碼字之間對應位置上不同碼元的個數，通常稱為漢明距離：D(Ci,Cj)=k-1nCikCjk碼C的最小距離：dmin=minD(Ci,Cj)；編碼選擇碼字時，碼字間的距離越大越好；譯碼規則、編碼方法的選擇：（1）最小距離儘可能大；（2）譯碼將收到的序列譯成與之距離最近的哪個碼字；（3）令碼長足夠長； 联合渐近等分割性 有噪信道编码定理(香农第二定理)及其意义對有噪信道編碼定理的說明： 联合信源信道编码定理及其意义7. 保真度准则下的信源编码 失真度 d(u

14、i,vj)0（单个符号） 失真矩阵 平均失真度：某个信源在某一试验信道下的失真大小；長度為N的信源符號序列的失真函數：長度為N的信源符號序列的平均失真度：單個符號的平均失真度：信源和信道都是無記憶的，N為信源序列的平均失真度：信源的平均失真度： 信息率失真函数的定义：在滿足保真度準則下，信源信息傳輸率的下限是多少； 信息率失真函數和信道容量具有對偶性：其他性質：（1）在一定約束條件下是平均互信息的極小值； （2）非負性，下限值為0； （3）當R(D)=0時，所對應就是平均失真度的上界Dmax；（4）R(D)是允許失真度D的凸函數；（5）R(D)在定義域內連續；（6）R(D)是嚴格的單調遞減函數

15、； 保真度准则下的信源编码定理(香农第三定理)及其意义 反之，意義：說明在允許失真D的條件下，信源最小的，可達的信息傳輸率是信源的R(D)。 联合有失真信源信道编码定理及其意义 香農第一定理+香農第二定理：（1）只要信道的信道容量大於信源的極限熵，就能在信道中做到有效地、無錯誤地傳輸信息；（2）分兩步編碼處理方法與一步處理方法效果一樣好；香農第三定理+香農第二定理：（1）如果信源的極限熵大於信道的信道容量，只要在允許一定失真的條件下，仍能做到有效和可靠地傳輸信息；如此可歸納出信息傳輸定理：（1）離散無記憶信源S的信息率失真函數為R(D)，離散無記憶信道的信道容量為C，如果滿足：CRD則信源輸出

16、的信源序列能再次信道輸出端重現，其失真小於等於D。（2）離散無記憶信源S，其信息率失真函數為R(D)比特/信源符號，每秒輸出1Ts個信源符號；離散無記憶信道的信道容量為C比特/信道符號，每秒傳輸1Tc個信道符號，如果滿足：CTcR(D)Ts則信源輸出的信息能再此信道輸出端重現，其失真小於等於D。（3）離散無記憶信源S，其信息率失真函數為R(D)比特/信源符號，每秒輸出1Ts個信源符號；離散無記憶信道的信道容量為C比特/信道符號，每秒傳輸1Tc個信道符號，如果滿足：CTcR(D)Ts則在信道輸出端不能以失真小於等於D再現信源輸出的信息。實用意義：（1）保真度準則下的信源編碼定理是有失真信源壓縮的理論基礎；（2）在允許一定失真度的情況下，信源的信息率失真函數可以作為衡量各種壓縮編碼方法性能優劣的一種尺度； 信息率失真函数的计算:对称信源(汉明失真)二元對稱信源的信息率失真函數：r元對稱信源的信息率失真函數：高斯信源(平方误差失真)8. 无失真的信源编码 無失真信源編碼 熵編碼信源概率分佈是不均勻的；信源是由記憶的，具有相關性；香農編碼：選擇每個