[工学]ch3离散信源.ppt

信息对抗技术研究所 教师：李琼 哈尔滨工业大学 第3章 离散信源 *计算机科学与技术学院2 主要内容 3.1 信源的数学模型及其分类 3.2 离散无记忆信源 3.3 离散无记忆信源的扩展信源 3.4 离散平稳信源 3.5 马尔可夫信源 3.6 信源的相关性和剩余度 *计算机科学与技术学院3 3.1 信源的数学模型及其分类 编码器 干扰器 信 源信 宿 消息 噪声 信道 信号+噪声信号 译码器 消息 v信息的来源称为信息源(Information Source)。 v信息是抽象的，需要通过消息（0-1序列、汉字、 字母、图像等）来研究信源。 二进制信源： X=0,1 汉语： X=人,口,手,山,水,田, 英语： X=a,b,c,x,y,z 莫尔斯电报： X= , ,字符间停顿，词之间停顿，句 子间停顿 *计算机科学与技术学院4 3.1.1 信源的数学模型 u如何对信源建模？ u特点：信源可以输出多个符号，每个符号以一定的概 率随机出现。 u因此可以用概率来描述信源。 X： 表示信源的随机变量； xi：表示信源符号； p(xi)：信源符号xi出现的概率。 *计算机科学与技术学院5 v 根据信源输出在时/空、幅度取值是否连续： 连续信源 时/空连续、幅度连续（如自然图像） 离散信源（数字信源）时/空离散、幅度离散 （如 数字图像） 3.1.2 信源的分类离散信源与连续信源 *6 数字图像示例 3.1.2 信源的分类离散信源与连续信源 *7 3.1.2 信源的分类 正常人 精神病患者 v 根据信源输出是否独 立： 有记忆信源 信源发出的 各个符号之间不是相互独立 的，是有依赖关系的。 无记忆信源信源发出的各 个消息符号是相互独立的， 是没有依赖关系的。 有记忆与无记忆信源 u无记忆信源：信源发出的各个消息符号是相互独立的， 是没有依赖关系的。 前面已经出现的信源符号对后面将要出现哪个信源符号没有影响 例如：一个袋子里有红球白球各50个，每次摸一个后放回， 则无论已摸过的球是红或白，再摸一次球，红白出现的概率都 是1/2 u如何用概率的方法定义无记忆信源？ 已出现符号对将要出现的符号的概率没有影响，p(x|y) = p(x). 设X=x1x2xM是信源发出的符号序列， 3.1.2 信源的分类无记忆信源 u有记忆信源：信源发出的各个符号之间不是相互 独立的，是有依赖关系的。 例如：自然语言、数字图像等。 p(们)=0.01, p(碗)=0.01 p(们|我)=0.05, p(碗|我)=0.001 u现实存在的信源多是有记忆信源 u有记忆信源分类 有限记忆信源 无限记忆信源 我 们、要、的、把、看、 碗、机、水、书、框、 3.1.2 信源的分类有记忆信源 3.1.2 信源的分类有限记忆信源和无限记忆信源 u有限记忆信源：信源发出的消息符号只与前若干 个符号的关系比较密切，与更前面符号的关系逐 渐减弱，直至无关。 up(xi | xi-1 xi-2 xi-m) 如果只与前m个符号有关系，则称m为记忆长度 u无限记忆信源：信源发出的消息符号与前面出现 的所有符号都有关系。 up(xi | xi-1 xi-2 xi-3 ) 3.2 离散无记忆信源 u定义3.2.1 信源X 的符号集为(x1, x2 , , xq)，q为 信源发出的消息符号的个数，每个符号发生的概 率为p(xi), i=1,2,q，这些消息符号彼此互不相关 ，且有 则称 X 为离散无记忆信源。 u定义3.2.2 信源中某个事件（消息符号）的自信息量 I(xi) = -log p(xi) u定义3.2.3 信源的平均自信息量（信源熵） u信源熵的单位 信源符号（消息符号）的自信息量表示该符号带有多少信息量 信源熵表示的是平均每个符号带有多少信息量 所以当底数为2时，信源熵的单位为：比特/符号 信源输出哪个符号是不确定的 一旦输出一个符号，便消除了这种不确定性 即带来了信息因此仍然用概率衡量信源包含的信息量的大小 3.2 离散无记忆信源 信源的自信息量和平均自信息量 信源熵的例子 u例3.2.1 解： 信源熵的例子 u例3.2.2 二元信源 它的熵为： u二元信源的信息熵 H(X)是概率p的函数， 通常用H(p)表示。 u可以一个符号一个符号的来研究信源，但有时这样 不能满足实际应用的需要。 汉语：更多地考察的是句子，而不是汉字。 英语：更多地考察的是单词，而不是字母。 图像：更多地考察的是整幅图像，而不是单个像素。 uN次扩展信源：集合中的每一个元素是一个N维随机 矢量 二进制信源： X=00,01,10,11, N=2 汉语： X=我们在上课，张三睡着了，, N=5 英语： X=the, car, ear, she, you, , N=3 3.3 离散无记忆信源的扩展信源 u二次扩展信源（N=2） uqN=4=22，q=2，N=2 u例如： p(01)=p(0)p(1)=p(1-p) u三次扩展信源（N=3） uqN=8=23，q=2，N=3 u例如： p(011)=p(0)p(1)p(1)=p(1-p)2 二元信源的扩展信源 u定义3.3.1 X是一个离散无记忆信源 则X的N次扩展信源为： u其中 离散无记忆信源的N次扩展 3.3.3 N次扩展信源的熵 u定义3.3.2 离散无记忆信源X的N次扩展信源XN的熵等于信 源X的熵的N倍，即 H(XN) = NH(X) u证明： 扩展信源熵的例子 u例3.3.1 u方法一 u方法二 3.4 离散平稳信源 3.4.1 离散平稳信源 u定义3.4.1 若信源产生的随机序列X1, X2, 满足： 所有X1, X2, 都取值于符号集A=(a1, a2, aq) 序列是平稳的，即对所有的非负整数i1, i2, iN, h及x1, x2, xN A，有 则称此信源为离散平稳信源。 u含义：信源所发符号序列的概率分布与时间起点无 关，概率是平稳的。 3.4.1 离散平稳信源 u一维平稳信源 u二维平稳信源 u完全平稳信源 (简称为平稳信源) (N为任意正整数) u离散平稳信源的条件概率也与时间起点无关 3.4.1 离散平稳信源 3.4.1离散平稳信源 离散平稳信源一定是离散无记忆信源吗？ uNO 无记忆：p(x|y)=p(x)，x出现的概率与已经出现的 符号无关。 平稳：p(x)不变，x出现的概率与时间无关。 3.4.2 二维平稳信源的熵 u联合熵： u条件熵： Which one is better？ 联合熵 或 条件熵？ u定义3.4.2 信源输出为N长符号序列，平均每个符号的熵 为： u定义3.4.3 信源输出为N长符号序列，当N，则极限 熵为 u极限熵的含义：信源输出的符号序列中，平均每个符号 带有的信息量，即实际的熵。 3.4.3 极限熵 u定理3.4.1 3.5 马尔可夫信源 u有限记忆信源：当前要输出的这个符号只 与前面已经输出的m个符号有关。 u这是具有马尔可夫链性质的信源。 3.5.1 有限状态马尔可夫链 u定义3.5.1 设Xn,nN+为一随机序列，时间参数集 N+=0,1,2,，状态空间S=S1, S2, SJ，若对所有 nN+，有 则称Xn,nN+为马尔可夫链。 u系统的将来的状态只与系统的现在的状态有关，与系 统的过去的状态无关这种特性称为马尔可夫特性 u什么是状态？ 将马尔可夫链用在不同的环境中，“状态”将具有不同的含义 。 转移概率 u在已知m时刻系统处于状态Si的条件下，在n时刻系 统处于状态Sj的概率, u转移概率：pij(m,n)=PXn=Sj|Xm=Si=PXn=j|Xm=i u实质：条件概率 u一步转移概率：n-m=1的情况，马尔可夫链最关心的 转移概率。 一步转移概率和k步转移概率 u一步转移概率（基本转移概率）： n-m=1 uk步转移概率: u规定 u转移矩阵： 所有的pij(k)(m) 组成一个矩阵 矩阵P中每一个元素 都是非负的，并且 每行之和均为1 时齐马尔可夫链 u定义3.5.2 如果在马尔可夫链中 pij(m)=PXm+1=j|Xm=i=pij 即从状态i转移到状态j的概率与m（时间）无关， 则称这类马尔可夫链为时齐马尔可夫链，或齐次马 尔可夫链，或具有平稳转移概率的马尔可夫链。 时齐马尔可夫链中 一步转移矩阵与多步转移矩阵之间的关系 u一步概率转移矩阵 u时齐马尔可夫链中存在切普曼-柯尔莫哥洛夫方程 u两步转移概率 转移矩阵与初始分布 u初始分布：系统一开始各个状态出现的概率 u初始分布不能由转移概率表示 转移概率：一个状态转移到另一个状态，涉及两个状态 初始分布：涉及一个状态 u由初始分布及各时刻的一步转移概率可以完整描述马尔可夫 链的统计特性。 n时刻的状态分布 初始状态分布 转移矩阵的n次幂n时刻的状态分布 齐次马尔可夫链的遍历性 u含义：无论初始分布是什么样的，经过足够长的转移之后，每 种状态出现的概率稳定下来。 u稳定=平稳？ NO 稳定：经过一个过程之后达到平稳 平稳：一定稳定 共同点：都指先验概率 求解稳态稳态 分布 u定理3.5.2 设P为某一马尔可夫链的状态转移矩阵，则该链稳态 分布存在稳态分布的充要条件是存在一个正整数N，使得矩阵 PN中所有的元素均大于零。 u等价于：存在一个状态Sj和正整数N，使得从任意初始状态出发 ，经过N步转以后，一定可以达到状态Sj。 u定理3.5.1 求解稳态稳态 分布例子 解： 3.5.2 马尔可夫信源 u具有马尔可夫链性质的信源 u状态：符号序列 u定义3.5.4 若信源输出的符号和状态满足下列条件则称此信 源为马尔可夫信源： 某一时刻信源符号的输出只与当时的信源状态有关，而与以前的状态 无关，即 信源状态只由前一时刻的状态和发出的符号唯一确定，即 u马尔可夫信源的实质 有限记忆信源 假设信源将要输出符号与 前m个符号有关，则状态由 m个符号构成 一阶马尔可夫信源与m阶马尔可夫信源 u一阶马尔可夫信源：状态中仅包含N=1个符号，共有 qN=q个状态。将要输出的符号仅与前1个符号有关。 um阶马尔可夫信源：状态中包含N=m个符号，共有 qN=qm个状态。将要输出的符号与前m个符号有关。 状态转移图 u这表明信源输出符号的不确定性问题转化成了信 源状态转移的问题。 u因此可以用马尔可夫链的状态转移图表示马尔可 夫信源 状态转移图的例子 u例3.5.2 二进制一阶马尔可夫信源 一阶：N=1，qN=2，即有2个状态S1=0和S2=1。 根据条件概率，可画出状态转移图 状态转移概率为 p(S1|S1)=p(0|S1)=0.25 p(S1|S2)=p(0|S2)=0.5 p(S2|S1)=p(1|S1)=0.75 p(S2|S2)=p(1|S2)=0.5 状态转移矩阵为S1 S2 S1 S2 状态转移图的例子 u例3.5.3 二进制二阶马尔可夫信源 二阶：N=2，qN=4，即有4个状态 S1=00、S2=01、S3=10、S4=11。 根据条件概率，可画出状态转移图 状态转移概率 p(S1|S1)=p(S4|S4)=0.8 p(S2|S1)=p(S3|S4)=0.2 p(S3|S2)=p(S1|S3)=p(S4|S2)=p(S2|S3)=0.5 状态转移矩阵为 S1 S2 S3 S4 S1 S2 S3 S4 遍历马尔可夫信源的熵 求马尔可夫信源的熵 求马尔可夫信源熵例子 u例3.5.4 二阶马尔可夫链的 状态转移图如图3.4， 求信源 熵。 解： u例3.5.4 二阶马尔可夫链的 状态转移图如图3.4， 求信源 熵。 解： 求马尔可夫信源熵例子 3.6 信源的相关性和剩余度 u即 信源输出符号间的依赖关系使得信源熵减小信源 的相关性。 u含义：由于信源符号间存在依赖关系，信源输出的符 号越多，越容易判断将要输出的符号是什么，即信源 熵（不确定性）越小。 定义3.6.1 信源剩余度定义为 R = 1- H/H0 H0：每个符号带有的最大的平均信息量 H：每个符号带有实际的平均信息量 H/H0：熵的相对率 3.6 信源的相关性和剩余度 u含义： 信源剩余度越大，表明信源的输出效率不高，即信 源符号之间的相关性越强；信源剩余度越小，表明信源输 出效率越高，即信源符号之间的相关性越弱。 张三住院了；张三没来上课 张三住院了；李四没来上课 u信源编码的目的：去除信源相关性，压缩。 作业 u 3.1-3.3 u 3.4（1） u 3.5（1）（2） u 3.7（1）（2）只计算H(X2) u 3.8 u 3.11，只画出状态转移图 u 3.13，只画出状态转移图 u 3.14，只画出状态转移图 u 3.15 u 请谈谈你对课本64页定义3.5.4的看法 信息对抗技术研究所 信息对抗技术研究所 附 录 马尔可夫链马尔可夫链性质性质 1. 互通性 定义：如果从状态i可到达状态j，同时从状态j也可到达状 态i，则称状态i和状态j是互通的。 结论： （1）任何状态的自身是互通的,因 为 （2）如果状态i和状态j是互通的，则状态j和状态i也是互 通的； （3）如果状态i和状态j是互通的，且状态j和状态k也是互 通的，则状态i和 状态k也是互通的。 2. 不可约性 类的概念： 根据互通的三个属性，状态可被分成1个或多个独立的类， 同一类中状态之间彼此是互通的（该类也可能只包含一种 状态）。 不可约性定义： 如果系统中的所有状态被归为一类，即所有状态之间都是 互通的，则该马尔可夫链被称为不可约。 3. 常返态、非常返态（瞬时态）和吸收态 非常返态定义： 如果过程一旦到达某状态后在未来决不会再回到此状态， 则称该状态为非常返态或瞬时状态。因此，当且仅当若存 在一个状态j（ji），只能从状态i可达该状态j，而从状态 j不可到达状