复习提纲信息论.ppt
信息理论总复习信息学院电子工程系王琳,单符号离散信源自信息量用概率测度定义信息量设离散信源 X，其概率空间为如果知道事件 xi 已发生，则该事件所含有的自信息定义为当事件 xi 发生以前：表示事件 xi 发生的不确定性。当事件 xi 发生以后：表示事件 xi 所含有（或所提供）的信息量,第一部分 信源熵,平均信息量信源熵：自信息的数学期望。也称为信源的信息熵/信源熵/香农熵/无条件熵/熵函数/熵。信息熵的意义：信源的信息熵 H 是从整个信源的统计特性来考虑的。它是从平均意义上来表征信源的总体特性的。对于某特定的信源，其信息熵只有一个。不同的信源因统计特性不同，其熵也不同。信源熵的三种物理含义信源熵 H(X)是表示信源输出后每个消息/符号所提供的平均信息量；信源熵 H(X)是表示信源输出前，信源的平均不确定性；用信源熵 H(X)来表征变量 X 的随机性。,最大离散熵定理(极值性)：离散无记忆信源输出 n 个不同的信息符号，当且仅当各个符号出现概率相等时(即p(xi)=1/n)，熵最大。Hp(x1),p(x2),p(xn)H(1/n,1/n,1/n)=log2n 出现任何符号的可能性相等时，不确定性最大。,二进制信源的熵函数 H(p)为,离散无记忆信源的扩展离散无记忆信源 X 的 N 次扩展信源的熵等于离散信源X 的熵的 N 倍，即H(X)=H(XN)=NH(X)离散平稳信源：各维联合概率均与时间起点无关的完全平稳信源称为离散平稳信源。二维离散平稳信源的熵为,离散序列信源,平均符号熵：信源平均每发一个符号提供的信息量为离散平稳有记忆信源的极限熵：当 N 时，平均符号熵取极限值称之为极限熵或极限信息量。用 H表示，即极限熵的存在性：当离散有记忆信源是平稳信源时，极限熵等于关联长度 N时，条件熵H(XN/X1X2XN-1)的极限值，即极限熵的含义：代表了一般离散平稳有记忆信源平均每发一个符号提供的信息量。,马尔科夫信源定义状态转换图(香农线图)状态极限概率平稳、齐次马尔科夫信源熵信源熵的相对率：=H/H0信源冗余度：=1=(H0H)/H0信源的冗余度表示信源可压缩的程度。,连续信源的差熵为上式定义的熵在形式上和离散信源相似，也满足离散熵的主要特性，如可加性，但在概念上与离散熵有差异因为它失去了离散熵的部分含义和性质。具有最大熵的连续信源,连续信源熵有关问题说明连续信源熵并不是实际信源输出的绝对熵；连续信源的绝对熵还有一项正的无限大量，虽然 log2(ba)小于0，但两项相加还是正值，且一般还是一个无限大量。因为连续信源的可能取值数有无限多，若假定等概率，确知其输出值后所得信息量也将为无限大；Hc(X)已不能代表信源的平均不确定度，也不能代表连续信源输出的信息量。连续信源熵的意义这种定义可以与离散信源在形式上统一起来；在实际问题中常常讨论的是熵之间的差值问题，如信息变差、平均互信息等。在讨论熵差时，两个无限大量互相抵消。所以熵差具有信息的特征；连续信源的熵 Hc(X)具有相对性，因此 Hc(X)也称为相对熵。,信道疑义度H(X/Y)：表示信宿在收到 Y 后，信源 X 仍然存在的不确定度。是通过有噪信道传输后引起的信息量的损失，故也可称为损失熵。噪声熵H(Y/X)：表示在已知 X 的条件下，对于符号集 Y 尚存在的不确定性（疑义），这完全是由于信道中噪声引起的。联合熵 H(XY)：表示输入随机变量 X，经信道传输到达信宿，输出随机变量 Y。即收、发双方通信后，整个系统仍然存在的不确定度。,第二部分 信道,平均互信息量定义：互信息量 I(xi;yj)在联合概率空间 P(XY)中的统计平均值。从一个事件获得另一个事件的平均互信息需要消除不确定度，一旦消除了不确定度，就获得了信息。,站在输出端：I(X;Y)收到 Y 前、后关于 X 的不确定度减少的量。从 Y 获得的关于 X 的平均信息量。站在输入端：I(Y;X)发出 X 前、后关于 Y 的先验不确定度减少的量。站在总体：I(X;Y)通信前、后整个系统不确定度减少量。,BSC信道的平均互信息量 设二进制对称信道的输入概率空间为 转移概率如图所示。,平均互信息量当 q 不变(固定信道特性)时，可得 I(X;Y)随输入概率分布 p 变化的曲线，如图所示；二进制对称信道特性固定后，输入呈等概率分布时，平均而言在接收端可获得最大信息量。,当固定信源特性 p 时，I(X;Y)就是信道特性 q 的函数，如图所示；当二进制对称信道特性 q=/q=1/2时，信道输出端获得信息量最小，即等于0。说明信源的全部信息信息都损失在信道中了。这是一种最差的信道。,求信道容量的方法当信道特性 p(yj/xi)固定后，I(X;Y)随信源概率分布 p(xi)的变化而变化。调整 p(xi)，在接收端就能获得不同的信息量。由平均互信息的性质已知，I(X;Y)是 p(xi)的上凸函数，因此总能找到一种概率分布 p(xi)（即某一种信源），使信道所能传送的信息率为最大。C 和 Ct 都是求平均互信息 I(X;Y)的条件极大值问题，当输入信源概率分布 p(xi)调整好以后，C 和 Ct 已与 p(xi)无关，而仅仅是信道转移概率的函数，只与信道统计特性有关；信道容量是完全描述信道特性的参量；信道容量是信道能够传送的最大信息量。,信道容量,香农公式说明当信道容量一定时，增大信道带宽，可以降低对信噪功率比的要求；反之，当信道频带较窄时，可以通过提高信噪功率比来补偿。当信道频带无限时，其信道容量与信号功率成正比。,允许平均失真度：率失真函数中的自变量 D，也就是人们规定的平均失真度 的上限值。率失真函数的定义域问题就是在信源和失真函数已知的情况下，讨论允许平均失真度 D 的最小和最大值问题。D 的选取必须根据固定信源 X 的统计特性 P(X)和选定的失真函数 d(xi,yj)，在平均失真度 的可能取值范围内。,第三部分 信息率失真函数,常用的失真函数称为汉明失真矩阵。,单符号信源和单符号信道的信息率失真函数在信源和失真度给定以后，PD 是满足保真度准则 的试验信道集合，平均互信息 I(X;Y)是信道传递概率 p(yj/xi)的下凸函数，所以在 PD 中一定可以找到某个试验信道，使 I(X;Y)达到最小，即 这个最小值 R(D)称为信息率失真函数，简称率失真函数。在信源给定以后，总希望在允许一定失真的情况下，传送信源所必须的信息率越小越好。从接收端来看，就是在满足保真度准则 的条件下，寻找再现信源消息必须的最低平均信息量，即平均互信息的最小值。,对偶问题：信道容量和信息率失真函数的问题，都是求平均互信息极值问题。分三个方面说明：求极值问题特 性解决的问题,研究信道编码和率失真函数的意义研究信道容量的意义：在实际应用中，研究信道容量是为了解决在已知信道中传送最大信息率问题。目的是充分利用已给信道，使传输的信息量最大而发生错误的概率任意小，以提高通信的可靠性。这就是信道编码问题。研究信息率失真函数的意义：研究信息率失真函数是为了解决在已知信源和允许失真度D 的条件下，使信源必须传送给信宿的信息率最小。即用尽可能少的码符号尽快地传送尽可能多的信源消息，以提高通信的有效性。这是信源编码问题。,限失真信源编码定理（香农第三定理）：设一离散平稳无记忆信源的输出随机变量序列为 X=(X1,X2,XL)，若该信源的信息率失真函数是 R(D)，并选定有限的失真函数。对于任意允许平均失真度 D0，和任意小的0，当信息率 RR(D)，只要信源序列长度 L 足够长，一定存在一种编码方式 C，使译码后的平均失真度；反之，若 RR(D)，则无论用什么编码方式，必有，即译码平均失真必大于允许失真。信息率失真函数也是一个界限。只要信息率大于这个界限，译码失真就可限制在给定的范围内。即通信的过程中虽然有失真，但仍能满足要求，否则就不能满足要求。,信源编码定理（香农第一定理）等长信源编码变长信源编码的方法霍夫曼编码香农编码费诺编码游程编码算术编码平均码长与编码效率,第四部分 信源编码,当 则得：,最佳译码准则最大似然译码准则最小距离译码准则有噪信道编码定理（香农第二定理）,第五部分 信道编码,线性分组码：一致校验/监督矩阵H生成矩阵G伴随式S汉明纠错码循环码,信道编码定理：若有一离散无记忆平稳信道，其容量为 C，输入序列长度为 L，只要待传送的信息率 RC时，任何编码的 Pe 必大于零，当 L，Pe1。信道编码定理说明：同无失真信源编码定理类似，信道编码定理也是一个理想编码的存在性定理。它指出信道容量是一个临界值，只要信息传输率不超过这个临界值，信道就可几乎无失真地把信息传送过去，否则就会产生失真。,闭卷可带计算器计算题精确到小数点后2位,考试要求,
