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