信息编码期末复习.pptVIP

期末复习第一章 2011.11 马尔可夫过程的概念 1. 马尔可夫性(无后效性) 马尔可夫性或无后效性. 即: 过程“将来”的情况与“过去”的情况是无关的 . 齐次马氏链、平稳性的概念. 一步转移概率矩阵的计算. 一步转移概率 一步转移概率矩阵 状态转移图 1230.5 0.25 路径： 经过一系列的转变状态i可以到状态j 可达： 两状态间有一条路径 互通 ： 两状态间互连 吸收态：只能出去不能进来 平稳概率 意义对固定的状态j,不管链在某一时刻的什么状 态 i出发, 通过长时间的转移到达状态 j 的概率都趋 于稳定。 信息的定义 n通信系统传输和处理的对象，泛指消 息和信号的具体内容和意义。 n通常需通过处理和分析来提取。 1.1.信源特性与分类 信源是产生消息的源，根据X的不同情况，信源可分为以下 类型： 连续信源：如果信源输出的随机变量取值于某一连续区间，为 连续信号，消息的个数是无穷值，就叫做连续信源。 离散信源：如果信源输出的随机变量取值于某一离散符号集 合，消息在时间和幅值上均是离散的，就叫做离散信源。 1. 离散无记忆信源 离散无记忆信源的数学模型为离散型的 概率空间，即： u2 , , ui , , p(u2), , p(ui), , 离散无记忆信源的概率密度函数 (u) （当满足无记忆条件时） （当进一步满足平稳性时） 离散有记忆信源的概率密度函数 若将离散序列信源发出的随机序列消息看作一阶马 氏链，则消息序列中任一时刻的消息 仅与其前面的一个 消息 有关，而与更前面的消息没有直接关系。 (u) （对于马氏链） （对于齐次马氏链） （对于齐次遍历马氏链） 自信息量：任意随机事件的自信息量 定义为该事件发生概率的对数的负值。 1.2.离散信源的信息熵 信息熵平均自信息量：随机变量I(pi)的数学 期望定义为平均自信息量 联合熵与条件熵： 定理1-2-2：熵函数的性质： 1.对称性 2.非负性 3.确定性 4.扩展性 5.递推性 6.可加性 定理1-2-2：熵函数的极值性 该性质表明，在离散情况下，信源U的各事件等概率 发生时，熵达到极大值。这个重要结论称为最大熵定 理。 事件的数目n越多，信源的熵值就越大（对数函数的单 调上升性）。 定理1-2-3：熵函数的上凸性 熵函数H(U)为pi= p(ui)的上凸函数 詹森（Jenson）不等式 当f(x)为下凸函数时： 当f(x)为上凸函数时： 离散无记忆信源的序列熵与消息熵 序列熵 H(U) （对平稳信源） （熵的可加性） 1.3.离散序列信源的熵 平均每个消息的熵消息熵HL(U) 离散序列信源的消息熵HL(U)等于单符号离散 信源的熵 定理1-3-1： 证明： 香农不等式 含义：熵不会因为附加条件的增加而有所增加。即 ，无条件熵大于等于有条件熵。 离散有记忆信源的序列熵与消息熵 定理1-3-3 对离散、平稳、有记忆信源， 下列结论成立: 证明：根据仙农不等式，无条件熵大于有条件熵 ，弱条件熵大于强条件熵。 含义：随着消息序列长度的增加，最后一个消息 的条件熵呈递减趋势，即序列所增加的熵越来 越小；只有当信源满足无记忆条件时，增加的 熵才保持不变 含义：序列的平均消息熵大于等于最后一个消息 的条件熵 含义：随着消息序列长度的增加，序列所增加的 熵越来越小，那么序列的平均消息熵也将越来 越小 含义：当消息序列的长度趋于无穷时，平均消息 熵（即极限熵）等于最后一个消息的条件熵 互信息定义 互信息量是通信系统的信宿从信 源所获得的信息量。 1.4.互信息 定理1-4-1：互信息的性质 I(U;V)=H（U）-H（UV） H（V）-H（VU） H(U)+ H(V)- H(U;V ) I(V;U) （1）对称性 （2）非负性 （3）互信息不大于信源熵 H(U)是信源U的信息熵,H(UV)是信宿接 收到V后，信源U还保留的熵，二者之差 I(U;V)就是在接收过程中得到的关于U,V的 互信息量。 对于无扰信道，I(U ; V)=H(U)。 对于强噪信道，I(U; V)= 0。 从通信的角度来讨论互信息 量I(U ; V)的物理意义 由第一等式I(U;V)= H(U)-H(UV)看I(U;V)的 物理意义： 对于无扰信道，有I(U;V)=H(U)=H(V)。 对于强噪信道，有H(VU)= H(V)，从而 I(U; V) = 0。 H(V)是信宿接收到V所获得的信息量，H(V U)是发出消息U后，由于干扰而使V存在的信 息熵，二者之差I(U;V)就是一次通信所获得的 信息量。 由第二等式I(U;V)= H(V)-H(VU)看I(U;V)的 物理意义： 通信前，随机变量U和随机变量V可视为统计 独立，其先验信息熵为H(U)+ H(V)， 通信后，整个系统的后验信息熵为H(U;V) 二者之差H(U)+ H(V)- H(U;V)就是通信过程中 信息熵减少的量，也就是通信过程中获得的互 信息量I(U; V)。 由第三等式I(U;V)= H(U)+ H(V)- H(U,V)看I(U;V) 的物理意义： 互信息量性质的意义 互信息量的对称性说明对于信道 两端的随机变量U和V，由V提取到的关于U 的信息量与从U中提取到的关于V的信息量 是一样的。只是观察者的立足点不同，对 信道两端的随机变量U和V之间的信息流通 的总体测度的两种不同的表达形式而已。 熵、条件熵、联合熵与互信息的关系 先验熵 接收符号熵 损失熵噪声熵 联合熵 互信息的定理 定理1-4-2 n当信道给定，即信道转移概率Pji固 定，互信息I(U ; V)是信源概率分布pi的 上凸函数。 n当信源给定，即信源分布概率pi固 定，互信息I(U ; V)是信道转移概率Pji的 下凸函数。 定理1-4-2说明: 信道固定时，对于不同的信源分布，信道输出端获 得的信息量是不同的。因此，对于每一个固定信道 ，一定存在一种信源（一种分布）pi ，使输出端获 得的信息量最大; 信源固定以后，用不同的信道来传输同一信源 符号时，在信道输出端获得的信息量是不同的。可见 ，对每一种信源一定存在一种最差的信道，此信道的 干扰最大，而使输出端获得的信息量最小。 信息不增性原理 在信息处理中，经常要对所 接收到的信息Y归并或分类为信息Z。 数据处理过程中只会失掉一 些消息，绝不会创造出新的信息，即信 息不增性。 定理1-4-5 信源效率和冗余度 n某信源的极限熵H与实际信息熵HL的比 值称为信源效率，即 n1减去信源效率称为信源冗余度,即 1.5.冗余度 第二章 限失真信源与信息率失真函数 失真测度及其性质 在信号空间中可以看作一类“距离”，它有性质 1当 2 3 在通信系统的信源和信宿的联合空间上定义 失真测度： 表示信源发出一个符号ui，而在接收端再现vj ，所引起的误差或失真。 R(D)函数的定义 香农定义了信息率失真函数R(D)，指 出：在允许一定失真度D的情况下，信源输出的 信息率可压缩到R(D)值。 对限失真信源，应该传送的最小信息 率是R(D)，而不是无失真情况下的信源熵H(U). 显然 H(U)R(D). 当且仅当 D=0时，等号成立； R(D) 根据前面在互信息中已讨论过 的性质： 互信息是 的下凸函数，其极限值存在。所 以在PD中一定可以找到某个试验信道，使互信 息达到最小，这个最小值就是信息率失真函数 R(D) ，简称率失真函数。 n信息率失真函数R(D)是假定信源给定的情 况下，在用户可以容忍的失真度内再现信源消 息所必须获得的最小平均信息量。率失真函数 一旦找到，就与求极值过程中选择的试验信道 不再有关，而只是信源特性的参量。不同的信 源，其R(D)是不同的。 n研究信息率失真函数是为了解决在已知信 源和允许失真度D的条件下，使信源必须传送 给信宿的信息率最小。即用尽可能少的码符号 传送尽可能多的信源消息，以提高通信的有效 性。这是信源编码问题。 第三章 信道与信道容量 n类似于对信源的统计描述，对信道而言 描述它的三要素是： 信道输入统计概率空间：XK，p(X) ， 信道输出的统计概率空间：YK，q(Y) ， 信道转移概率矩阵：P(Y |X)。 即： ，P ， ， 它可简化为： 3.1.2 信道描述 ， ， 信道容量的定义 离散强对称信道 一、强对称信道 强对称信道的两项重要特征： 其输入消息与输出消息相等，均 为n个，即m=n。且信道中总的误差概率 Pe,它将平均分配给(n-1)个传输的错误 。 信道转移概率矩阵中的每一行都是 第一行的重排列，即信道对输入是对称的； 每一列都是第一列的重排列，即信道对输出 也是对称的。 条件就对称而言，比条件更加本质 ，更加重要。若放弃条件，保留条件， 我们就可以得到一般性的对称信道。 二、对称信道 对这类一般对称信道有如下定理： 定理3-4-1：对于单个消息离散对称 信道，当且仅当信道输入输出均为等概 率分布时，信道达到容量值。 结论：对于离散单个消息对称信道 ，C为最佳输入分布时的最大输出熵。根据最 大熵定理，输出分布为等概率时其熵最大。 同时由于信道的对称性，此时输入的最佳分 布必然为等概率分布。 对称信道不要求输入分布和输出分 布相同，而只要求各自为等概率分布。显然 ，强对称信道是对称信道的特例。 n假如我们再将条件放松一些，比如信 道的输出集合可以划分为若干个不相等的 且具有对称信道性质的子集合。 三、 准对称信道 显然子阵P1,P2满足可排列性（行，列） n定理3-4-2：对于单消息、离散、准对 称信道，当且仅当信道输入为等概率分布 时，信道达容量值: 信道容量代价函数 信道冗余度 第4章 信息与通信系统的优化 系统优化的实质 研究系统在不同优化指标下，两类参量 （主、客观）之间的统计匹配与匹配的条件。 对无失真信 源 系统传输最有效 优化的目标 对限失真信 源 系统传输最可靠 系统传输最安全 以上三个指标、四个方面所讨论的系统 优化就构成了最著名的C. E. Shannon三个编码定理 与一个密码学基本定理。 Shannon编码第一定理 无失真信源编码定理：在无失真 条件下实现通信系统与信源统计特性相匹配 ： 当系统中传信率 RH(U)(信源熵)时， 最优的信源编、译码(f1 ,g1)存在； 反之，当RC时，最优信道编、译 码(f3 ,g3)不存在。 Shannon编码第三定理 信道编码定理：在平均误差准则 条件下，实现通信系统与信道统计特性相 匹配； 当RR(D)时，最优的限失真信源编 、译码(f 1,g 1)存在； 反之，当RR(D)时，最优的限 失真信源编、译码(f 1,g 1)不存在。 密码学基本定理 对掌握密钥的信宿V，通过最优化 的加、解密码(f2 ,g2)，使R=I(U,V)=H(U); 反之，对不掌握密钥的信宿V， 几乎找不到最优化的加、解密码(f2 ,g2)，所 以R=I(U,V) 0 第五章 信 源 编 码 5.1 无失真信源编码 离散信源的无失真编码实质上是 一种统计匹配编码。 信息论指出信源中的统计多余度 主要决定于以下两个主要因素：一是消息 概率分布的非均匀性，另一个是消息间的 相关性。对无记忆信源主要决定于概率分 布的非均匀性，但是，对于有记忆信源， 两者都起作用，且后者相关性更加重要。 5.1.1 等长编码定理 设离散无记忆信源U=U1 ，U2 ，Uk 的熵为H（U），可用K个符号进行等长度编码， x=(x1,xkxK)，且xkx1,xjxm。对任意的 0、0，只要满足 则当L足够大时，必可使译码差错小于。反 之，当 译码差错为有限值，当L足够大时，译码肯 定出错。 异前置码 定义：每个符号组合一旦构成码 字，以后的各类组合不能构成任何码字。 具有实时唯一可译性。 异前置码是一种实时的唯一可译 码，无需加同步信息，在接收端就能被分 离出来。在信源编码和数据压缩中这类编 码在理论上和实际上都有很大意义。 变长编码定理 定理5-1-2：设某单个离散消息 信源U=U1 ，U2 ，Uk的熵为H(U)，将它 编成m进制的码字，其平均码长 应满足下列 关系： 对于二进制，即m=2时，上述定理简化为： 定理5-1-4：对于平均消息(符号)熵为 H(U)的离散、平稳、无记忆信源，必存在 一种无失真编码方法，使平均每个消息(符 号)的信息率R满足不等式： H(U)RH(U)+ 其中为任意正数。 其具体编码方法如下： (1) 将信源消息(符号)按概率大小顺序排 队； (2) 从最小概率的两个消息开始编码，并 给予一定的编码规则，如小概率的下支路编为 1(或0)，大概率的上支路编为0(或1)，若两者 概率相等，仍是下支路为1上支路为0； 最佳变长编码哈夫曼编码 (3) 将已编码的两个消息对应概率合并， 并重新按概率大小排队，重复步骤(2)； (4) 重复步骤(3)，直至合并概率归一时为 止； (5) 编成的变长码是按后出先编方式，即 从概率归一的树根沿编码路线逆行至对应的消 息。 小消息集合实现统计匹配的变长编码 ，其基本思想是扩张信源。 对于有记忆信源，信源输出的各个 分量之间是有统计关联的，这种统计关联性可 以加以充分利用，预测编码就是基于这一思想 。它不是直接对信源输出的信号进行编码，而 是将信源输出信号通过预测变换后再对信源输 出与被预测值的差值进行编码。 预测 编 码 变 换 编 码 n由于信源序列往往具有很强的相关性，要 提高信源的效率首先要解除信源的相关性，解除 相关性可以在时域上进行，这就是上节中介绍的 预测编码，也可以在频域，甚至于广义频域(或 空域)内进行，这就是要在本节中介绍的域变换 编码，其数学基础是矩阵的正交变换。 第7章 信 道 编 码 码重、码距 码重(weight) 一个码组中“1”的数目， 又叫汉明(Hamming)重量。 码距(distance) 两个码组之间对应位置上1、0不同的 位数，又叫汉明(Hamming)距离。 检错、纠错能力 l为检查出e个错误，要求最小码距 为 l为纠正 t个错误，要求最小码距为 l为纠正 t 个错误，同时检查出 e 个错误，要求最小码距为 线性分组码 线性分组码中的线性是指码组中码元 间的约束关系是线性的，而分组则是对编 码方法而言。即编码时将每k个信息位分为 一组进行独立处理，变换成长度为n(nk) 的二进制码组。 f:Uk Cn f(uu)= f(u)f(u) 线性分组码 (n，k)线性分组码， n表示输出 的码组长度，k表示输入信息分组，将输入 信息分成k位一组进行编码，并按照一定线 性规律加上人为多余的码元，构成n(nk) 位一组的输出。 编码前的信息分组为 u=(u1u2uk)，编码后的码组为c= (c1c2cn)为线性分组码，其中k位为信 息为，n为码长，则编码效率为 R=k/n 由上述定义可见，一个线性分组 编码f是一个从矢量空间GF(2k)到另一个矢 量空间GF(2n)上的一组线性变换。它可应 用线性代数理论中有限维的矩阵来描述。 生成矩阵G n位的码组，可以由k个信息 位的输入消息u通过一个线性变换矩阵G来 产生，称G为码的生成矩阵。 若生成矩阵G能分解成两个子 矩阵时 G(I Q) 其中I为单位方阵，则称c为系 统码，称G为系统码的生成矩阵。 监督矩阵H （n，k）线性分组码，H 矩阵的n-k行就对应n-k个线性监督方 程组，可确定n-k个监督码，称H为码 的监督矩阵。 若H矩阵能分解成两个子 矩阵时 H(P I) 其中I为单位方阵，则称c 为系统码，称H为系统码的监督矩阵。 G和H的关系 线性分组码可以完全由生成矩 阵G和监督矩阵H所决定。一般在讨论编 码问题时，常采用生成矩阵G，而在讨论 译码问题时，常采用监督矩阵H。 生成矩阵G中每一行及其线性 组合都是（n,k）码的码字，可以得到G 和H有如下的关系： HGT=0T GHT=0T 系统码的编码 系统码的编码结构非常简单，比如 对(7,3)码，根据线性方程 c0=u0c3=u0u2 信息位 c1=u1 监督位 c4=u0u1u2 c2=u2c5=u0u1 c6=u1u2 在编码器的每组k个数字的后面，附 加上(n-k)个监督码就可得到所编出的n个码字 。 系统码的最优译码 发送的码字为c= (c1c2cn)， 传输中的差错矢量为e= (e1e2en)，那 么接收到的信号为： y=(y1 y2yn)c e 如果在传输中没有发