信息论复习-(1)

第一部分本章是信息论的基本概念，介绍的主要内容有：从通信的角度讲，信息论是应用近代概率统计方法研究狭义信息的度量方法，研究各种信源、信道的描述和信源、信道的编码定理。信息的特点：无确切定义，人人皆知的抽象概念信息的特征：抽象性和广泛性信息与消息、信号的关系香农信息论给出的信息的定义：1.信息的概念信息是事物运动状态或存在方式的不确定性的描述。2.什么是信息论（1）信息论的发展简史1948年，香农在《通信的数学理论》的论文中，用概率测度和数理统计的方法系统地讨论了通信的基本问题，得出了几个重要而带有普遍意义的结论。香农理论的核心是：在通信系统中采用适当的编码后能够实现高效率和高可靠性的信息传输，并得出了信源编码定理和信道编码定理。（2）信息论研究的对象干扰源信道信道译码器信道编码器信源译码器信源编码器信宿信源等效信源等效信宿等效干扰信道图1-1信息传输系统模型这个模型包括以下五个部分：3.信道信道是信息传输和存储的媒介。4.译码器译码是编码的逆变换，分为信道译码和信源译码。5.信宿信宿是消息的接收者。2.编码器编码器是将消息变成适合于信道传送的信号的设备。1.信源信源是产生消息的源。编码器信源编码器，提高传输效率信道编码器，提高传输可靠性第二部分1.信源的分类离散信源和连续信源；平稳信源和非平稳信源；有记忆信源和无记忆信源2.离散信源的信息熵（1）自信息1()log()iiIaPa()iIa有两个含义：1、当事件发生前，表示该事件发生的不确定性；2、当事件发生后，表示该事件所提供的信息量．（2）信息熵(平均自信息）11()[log]()log()()qiiiiHXEPaPapa（3）信息熵的物理含义①信息熵表示信源输出后，每个消息（或符号）所提供的平均信息量②信息熵表示信源输出前，信源的平均不确定性。③用信息熵来表征变量X的随机性3.信息熵的基本性质①非负性②对称性③确定性④扩展性⑤极值性⑥可加性⑦强可加性⑧递增性⑨上凸性HpppHppppnnn(,,...)(,,,...)12121HHH(,)(,)(,,,...)100110000112120lim(,,...,,)(,,...,)qqqqHpppHppp12(,,...,)(1/,1/,...,1/)logqHpppHqqqq),,,(),,,,(),,,,,,,(21121211211nmnnmnnnnmnmnpqpqpqHpppppHqqqpppHH(X)≥0H（XY）=H（X）+H（Y）H(XY)=H(X)+H(Y/X)熵函数H(P)是概率矢量P=（p1,p2,…,pn)的严格n型凸函数。4.离散无记忆扩展信源的信息熵（1）离散无记忆扩展信源的数学模型1212...()()...()NNNqqXpppP12()()()...()iiiiNPPaPaPaqiiiN,2,1,,,21（2）离散无记忆扩展信源的信息熵()()NHXNHX掌握扩展的方法5.离散平稳信源的信息熵（1）离散平稳信源的定义及数学模型)()()()()(),()(),(1)()(,),(),(,,,)(1211212121212112121NNNNiiiiiiiiiiiiiiiNNMiiMMaaaapaapapaaaPPaaaxxxxXXXXppppxPX其中（2）离散平稳信源的信息测度①联合熵1211()()log()qqijijijHXXPaaPaa②条件熵21211(|)()(|)qiiiHXXPaHXXa11()log(|)qqijjiijPaaPaa注意符号的前后依赖关系③平均符号熵121()(...)NNHXHXXXN④离散平稳信源信息熵的性质（1）条件熵随N的增加是非递增的（2）N给定时，平均符号熵大于等于条件熵（3）平均符号熵随N的增加是非递增的（4）121lim()lim(|...)NNNNNHHXHXXXX称为极限熵。H⑤各种信息熵之间的关系21(|)()HXXHX1212()()()2()HXXHXHXHX只有信源统计独立时等号成立。12121()()(|)HXXHXHXX6.马尔可夫信源及其信息熵（1）马尔可夫信源的定义若一个信源满足下面两个条件，则称为马尔可夫信源：①某一时刻信源输出的符号的概率只与当前所处的状态有关，而与以前的状态无关；②信源的下一个状态由当前状态和下一刻的输出唯一确定。（2）时齐遍历马尔可夫信源的信息熵（了解）7.信源剩余度①熵的相对率0HH0logHq②信源剩余度011HH第三专题一.信道的分类单用户信道和多用户信道；有反馈信道和无反馈信道；时变参数信道和固定参数信道；离散信道、连续信道、半连续半离散信道和波形信道；有记忆信道和无记忆信道；有噪信道和无噪信道。二.离散信道的数学模型1.一般离散信道（多维离散信道）P(Y/X)XY2.基本离散信道（单符号离散信道）1ara1bsb(|)jiPbaXY111212122212...............ssrrrsppppppPppp根据信道矩阵的特点，信道可分为：（1）对称离散信道（2）准对称离散信道（3）强对称离散信道3.无噪信道（无干扰信道）1()()(/)0()yfxyfxPyxyfx，并且无噪信道（1）无噪无损信道:一一对应关系（2）无噪有损信道：多对一关系有噪信道：信道转移概率不是0，1分布有噪无损信道：一对多关系，其后向概率为0，1分布；充要条件是信道矩阵中每一列有一个也仅有一个非零元素；4.离散无记忆信道（DMC）NiiiNNxyPxxxyyyPxyP12121)()()/(否则为有记忆信道；5.离散无记忆信道的N次扩展信道（信道编码时使用）(/)knhkPNikhkkkhhhiiNNabPaaabbbP1)()(2121XNYN111111)(aaaaa221111)(aaaaaNrrrrrraaaaa)(111111)(bbbbb221111)(bbbbbNssssssbbbbb)()/(khP（三）离散信道的平均互信息及其特性1.信道疑义度,1(/)[(/)()log(/)jXYHXYEHXbPxyPxy)()(log)()()(log)()(log);(yPxyPyPxPxyPxPyxPyxI2.互信息3.平均互信息);(YXIYXxPyxPxyP,)()(log)(YXyPxPxyPxyP,)()()(log)(YXyPxyPxyP,)()(log)(4.平均互信息的物理含义及与各类熵的关系（1）平均互信息与各类熵的关系H(X)H(Y)I(X;Y)H(X|Y)H(Y|X)I(X;Y)=H(X)-H(X/Y)=H(X)+H(Y)-H(XY)=H(Y)-H(Y/X)（2）平均互信息的物理含义①平均互信息表示接收到输出信号的前、后关于输入信号的平均不确定性的消除②平均互信息表示输入信号发出的前、后，关于输出信号的平均不确定性的消除③平均互信息表示信道的输出信号和输入信号之间相互提供平均信息量④平均互信息是输入信号和输出信号之间的统计依赖关系的信息量度⑤平均互信息表示信道中平均每个符号所能传达的信息量，就是信道的信息传输率R5.平均互信息的特性（1）平均互信息的非负性I(X;Y)=0（2）平均互信息的极值性I(X;Y)=H(X)I(Y;X)≤H(Y)（3）平均互信息量的交互性I(X；Y)=I(Y；X)（4）平均互信息的凸状性1平均互信息I(X;Y)是信源概率分布P(X)的型凸函数2平均互信息I(X;Y)信道传递概率分布P(Y/X)的U型凸函数6.I(XN;YN)与I（X；Y）的关系（了解）①如果信道是无记忆的，即1(/)(/)NiiiPyPyxx1(;)(;)NNNiiiIXYIXY则：②如果信源是无记忆的1(;)(;)NNNiiiIXYIXY③当离散信源和离散信道都是无记忆时，等号成立（五）离散信道的信道容量1.离散信道的信道容量信道容量：最大信息传输率CIXYHXHXYPXPXmax{(,)}max{()(/)}()()2.计算信道容量的方法（1）运用信道容量解得充要性（2）运用特殊信道的容量公式求解（3）运用r个方程求解（六）常见信道的平均互信息和信道容量1.无噪一一对应信道（无噪无损信道）I(X;Y)=H(X)=H(Y)C=logr=logs2.有噪无损信道此时信道疑义度为0，而信道噪声熵不为0，从而C=max{I(X;Y)}=max{H(X)-H(X/Y)}=max{H(X)}=logr3.无噪有损信道此时信道疑义度不为0，而信道噪声熵为0，从而C=max{I(X;Y)}=max{H(Y)-H(Y/X)}=max{H(Y)}=logs4.离散对称信道'''12max[()(,...)]sCHYHppplog2()1()CHpHp5.强对称信道log(,,,...,)111pppCrHprrrloglog(1)()rrHp6.二元对称信道7.准对称信道'''121log(,,...,)lognskkkCrHpppNM（七）无记忆N次扩展信道的I（X；Y）和容量(;)(;)NNIXYNIXYNCNC（八）信道剩余度定义：信道剩余度＝C-I(X;Y)信道的相对剩余度＝(;)1IXYC第四专题（一）信源编码和码的类型1.信源编码信源符号与码字之间的一一对应变换称为信源编码。2.码的类型二元码，三元码，r元码，等长码，变长码，非奇异码，奇异码，惟一可译码，非惟一可译码，即时码（二）即时码及其树图构造法（三）唯一可译码存在的充要条件（1）唯一可译码存在的充要条件是，满足Kraft不等式11qilir（2）若存在一组码长为的唯一可译码，则一定存在具有相同码长的即时码。所以，Kraft不等式也是即时码存在的充要条件。qlll,,21（四）唯一可译码的判断法唯一可译码的判断步骤：（1）观察是否是非奇异码。若是奇异码则一定不是唯一可译码。（2）计算是否满足Kraft不等式。若不满足一定不是唯一可译码。（3）将码画成一棵树图，观察是否满足即时码的树图构造，若满足则是唯一可译码。或：计算出分组码中所有可能的尾随后缀集合F，观察F中有没有包含任一码字，若无则为唯一可译码；若有则一定不是惟一可译码。（五）无失真等长信源编码定理()loglHSNr()2loglHSNr（六）无失真变长信源编码定理香农第一定理()()1loglogNHSLHSrNrNlim()rNLHS当则得：N(2)：若就存在唯一可译变长码，若则不存在唯一可译变长码。'()RHS'()RHS(3)无噪信道编码定理(R不大于信道容量C,R大于C)信源编码的实质(4)（七）无失真信源编码定理和数据压缩1.无失真数据压缩的极限值无失真信源编码定理（无论等长还是变长）在理论上指出离散信源的信息熵是信源无失真数据压缩的极限值。2.编码后信源信息率、码率和编码效率（1）编码后信源信息率'logNLRrN（2）码率码符号比特等长码/)/)((/)(NlSHRNLSHRN（3）编码效率()rHsLrLSHlog)(（4）码的剩余度1（八）最佳二元码平均码长为最短的即时码称为最佳码（又称紧致码）（九）霍夫曼码和其他编码方法1.香农码（1）香农码（只是确定了码长，可用树图法构造出即时码，但是这种方法编的码不是最佳码）（2）香农——费诺——埃利斯码（有系统的唯一的编码方法，但是一般情况下，编码效率不是很高）2.费诺码（适用于对分组概率相等或接近的信源编码）3.霍夫曼码哈夫曼码对信源的统计特性没有