信息论复习要点

信息论复习要点1.非奇异码：若一个码子中各码子都不相同，则称非奇异码，否则称为奇异码；2.唯一可以码：若任何有限长信源序列都能译成唯一的信源消息序列，则称为唯一可译码；3.二元最优码：就某一信源，存在最优的二进制码，其中至少有两个最长的码子有相同长度且仅最后一个码位有别。4.AWGN信道的容量：一个加性高斯白噪声（AWGN）信道的噪声功率谱为N0/2,输入信号平均功率为P，信道带宽为W，那么信道每单位时间的容量为：0log1PCWNW（容量单位为比特/秒）5.对于输入平均功率受限的加性高斯噪声信道，当传输速率R=C时，总可以找到一种编码方式，使得差错率任意小；反之，找不到使译码错误概率任意小的编码。6.信息率失真理论是有损数据压缩的理论基础，该理论的核心是在保真度准则下的信源编码定理，即香农第三定理。7.限失真信源编码定理：DRRD存在平均失真的信源编码8.限失真信源信道编码定理：DCRD存在平均失真的信源信道编码9.和信道及其容量：若一个信道分为若干子信道，且各子信道输入之间互不相交，输出之间也互不相交，信道总的输出与输入集合分为各子信道输出与输入之并集，而且每次传输只能用某个子信道，则称此信道为和信道。和信道容量：21log2iNCiC其中，iC为每个子信道的容量，第i个子信道的使用概率为：1222iiiCCCiNCir达到容量时的输入概率为各子信道达到容量时的输入概率乘以ir，N为子信道的个数。10.各种信息的概率公式：自信息：logIxpx；联合自信息：logIxypxy；条件自信息：|log|Ixypxy三者的关系：||IxyIxIyxIyIxy；互信息：|,loglog|pxpxyIxypxypx；互信息与自信息和条件自信息的关系：,|IxyIxIxy；11.最佳判决与译码准则：MAP准则：（输入不等概）（1）信道转移概率矩阵乘以信道输入符号概率得到联合概率矩阵；（2）联合概率矩阵每一列中找到一个最大的概率对应的输入符号就是译码；（3）正确概率是所有译码的概率和，错误概率是1与正确概率的差；ML准则：（输入等概）（1）信道转移概率矩阵中最大的概率对应的输入符号作为译码输出；（2）正确概率是联合概率分布中译码概率的和，错误概率是1与之的差；无记忆二元对称信道，最大似然准则等价于最小汉明距离准则；12.并联高斯信道的容量，能量分布和输入概率分布：（输入均值为0）（1）并联独立高斯信道：利用注水定理对能量进行分配，计算信道容量，达到容量时，两个信道的输入是独立的，所以输入的概率密度为：2212122212121,exp222xxpxx（2）关联相关高斯信道：将噪声自协方差矩阵分解（如下公式所示），找出等价矩阵，利用注水定理计算信道容量，得到能量分配和输入概率密度公式；43315031110122321313（3）反推得到输入概率的协方差矩阵，进而得到输入概率的密度公式；（4）对于独立并联高斯信道，达到容量时各子信道输入是独立的；（5）对于相关并联高斯信道，达到容量时各子信道输入是相关的；（6）在总噪声和输入平均能量约束都相同的条件下，相关并联高斯信道的容量大于独立并联高斯信道容量。信息论知识点串讲1.香农信息论的主要内容：“一个概念，三个定理”，就是信息熵的概念和3个编码定理。2.香农第一定理（无失真信源编码定理）：如果信源编码码率不小于信源的熵，就存在无失真编码；反之，不存在无失真编码。RH存在无失真信源编码3.香农第二定理（有噪信道编码定理）：如果信息传输速率小于信道容量，则总可以找到一种编码方式使得当编码序列足够长时传输差错任意小，反之不存在使差错无限小的编码。RC存在译码差错任意小的信道编码4.香农第三定理（限失真信源编码定理）：对任何失真测度0D，只要码子足够长，总可以找到一种编码，使得当信源编码的码率RD时，码的平均失真D；RRDD存在平均失真信源编码5.互信息：|;log|pxyIxyIxIxypx互易性；当两个事件相互独立时互信息为0；互信息可正可负；任何两个事件的互信息不大于任何一个自信息；6.条件熵：||xHYXpxHYx7.熵的基本性质：（1）对称性；（2）非负性；（3）可加性；（4）极值性；（5）上凸性；8.离散最大熵定理：当px等概率分布时，熵最大。9.各类熵的关系：|HXYHXHYX|XHYHY10.平均互信息：|;;Y|logxxypyxIXYpxIxpxpyxpy非负性；对称性；凸函数性（下凸函数）；极值性（最大值）；11.平均互信息与熵的关系：;|Y|IXYHXHXHYHYXHXHYHXY12.离散信源的熵：(1)离散无记忆信源：HXHp二元无记忆信源NNHXNHX离散无记忆信源的次扩展源(2)离散平稳有记忆信源的N次扩展源：12121121||NNNNHXHXXXHXHXXHXXXX121NNHXHXXXN121limNNHXHXXXN13.齐次马氏链：具有平稳转移概率的马氏链；(1)状态转移矩阵；（2）网格图；（3）状态转移图；N步转移概率：mnmnppp对于有限状态的马氏链，平稳分布一定存在；1231230011/21/31/61/21/201231123123123limkkp14.马尔可夫信源N次扩展源的熵：如果起始状态概率分布为平稳分布，则N次扩展源的熵：12TNHXXXHNmhh为状态转移矩阵每一行对应的熵的行向量一个m阶平稳的马氏源的符号熵：limTNNHXHXh信源效率：0HH信息剩余度：011HH15.对于有限状态马氏链，平稳分布一定存在且唯一（错）：状态转移矩阵的解并不是唯一，所以对于有限状态的马氏链，平稳分布一定存在但不一定唯一。16.连续信源：连续随机变量集的熵：loghXpxpxdx连续随机变量集的条件熵：|log|hXYpxypxydxdy连续随机变量集的联合熵：loghXYpxypxydxdy连续熵与离散熵的差别：(1)差熵可以作为信源平均不确定性的相对度量但不是绝对度量；(2)差熵不具有非负性；(3)在连续信源中，在一一对应变换的条件下，差熵可能发生变化；17.高斯随机变量：一维高斯随机变量：概率密度函数：221exp22xmgx熵：21log22hXe多维独立随机变量：概率密度函数：（以二维为例）222212121exp222yxxmxmgxy222222112exp2121xxyyxyxxyygxy熵：1/2222122log22hXe多维相关高斯随机变量集的熵：概率密度函数：1/21/211exp22detTNgxxmxm熵：1/Nlog2det2NNhXe18.连续最大熵定理：(1)限峰值最大熵定理：幅度受限的随机变量，当均匀分布时有最大熵；(2)限功率最大熵定理：功率受限的随机变量，当高斯分布时有最大熵；19.连续随机变量的平均互信息：;logpxyIXYpxydxdypxqy对称性；非负性；线性变换平均互信息不变性；20.离散集与连续集之间的平均互信息：|;logxypyxIXYpxpydyqx21.无失真信源编码：定长码信源编码定理、变长码信源编码定理、最优码——Huffman编码；22.定长码：只要非奇异就满足唯一可译；单信源符号无失真编码条件：lqr（q为信源符号数，l为定长码长度）N场信源符号序列无失真编码条件：loglogNlqqrlNr或logloglqNr为平均每个信源符号所需要码符号数定长码信源编码定理：loglrHXN当N足够大时，译码差错可以任意小；定长码编码速率（码率）：'loglRrN（比特/信源符号）编码效率：'logHXNHXRlr信息传输速率：NHXRl每个传输符号所含的信息量23.变长码：若一个码是唯一可译码，则必满足Kraft不等式，即11iqlir；单信源符号无失真编码条件：1loglogHXHXlrrN场信源符号序列无失真编码条件：1loglogHXHXlrrN编码码率：'logRlr（比特/信源符号）编码效率：'HXR传输速率：HXRl（比特/码符号）24.哈夫曼编码：（主要考虑二元哈夫曼编码）二元哈夫曼编码：二元最优码性质（参照上面总结）二元哈夫曼编码方式：略Huffman编码的特点：是一种最优码，编码结果不是唯一的；适合符号集大的信源；广泛应用；最小方差Huffman编码：在编码过程中，应尽量使码树中合并过的分支处于概率排序的高位，从而减小合并次数，使码长方差最小。码长方差：222iiipll25.一个平稳离散无记忆信道容量C定义为输入与输出平均互信息I(X；Y)的最大值，即max;pxCIXY信道容量的单位：比特/信道符号；当信道给定后，|pyx就固定，C仅与|pyx有关，而与px无关；C是信道传输最大信息速率能力的度量；无损信道：每个输出符号只对应一个输入符号（一多对应），即|0HXY；maxlogCHXr(r是输入符号集的大小)确定信道：每个输入符号都对应一个输出符号（多一对应），即|0HYX；maxlogCHYs(s是输出符号集的大小)无损确定信道：输入符号与输出符号是一一对应，即|X|0HYHXY；loglogCsr26.对称信道：若一个信道转移概率矩阵按输出可分为若干个子集，其中每个子集都有如下特性：即每一行是其他行的置换，每一列是其他列的置换，则信道称为对称信道。通常将转移矩阵分成多个子集的对称信道称为准对称或弱对称信道，而只有一个子集的对称信道称强对称信道。弱对称信道容量：11121,,sCHYHppp强对称信道容量：11121log,,sCsHppp一般情况信道容量的计算：;log,0ijiijijjpIaYpCq对于p;log,0ijiijijjpIaYpCq对于p27.级联信道：如果随机变量集合（X,Y,Z）构成马氏链，则称信道X-Y与Y-Z构成级联信道。级联信道转移概率矩阵为级联信道中各矩阵依次相乘，根据级联信道的转移矩阵特点，可按照前面介绍的计算离散信道容量的计算方法计算其信道容量。28.多维矢量信道及其容量：输入与输出的平均互信息：|;Y|logNNNNNxypyxIXHXHXYpxyqy对于离散无记忆信道，有1;Y,NNNiiiIXIXY对于无记忆信源：1;Y,NNNiiiIXIXY对于无记忆信源和无记忆信道：1;Y,NNNiiiIXIXY对于平稳无记忆信源和无记忆信道：1;Y,;NNNiiiIXIXYNIXY并联信道及其容量：1NiiCC，仅当各iX相互独立时，达到容量