信息论基础 教学课件 作者 田宝玉 杨洁 贺志强

发布者:admin 发布时间:2019-10-24 07:51 浏览次数:

  信息论基础 教学课件 作者 田宝玉 杨洁 贺志强 王晓湘 chapter3.ppt

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  3.1.2 离散无记忆信源的数学模型 ▲ 单符号离散无记忆信源的数学模型: 3.1.2 离散无记忆信源的数学模型 离散马尔可夫信源 对于遍历马氏链,无论初始分布如何,当转移步数足够大时,状态概率分布总是趋于稳定值,与初始状态概率分布无关。 几点注释: 1)定理3.5.2给出了马氏源符号熵的计算方法: 先求每个状态下的条件符号熵,再用状态的概 率平均; 2)计算符号熵要用状态的平稳分布; 3)单位为比特/符号。 信源的相关性就是信源符号间的依赖程度。设信源有m个符号,那末对于不同情况可以分别计算信源的熵为: (符号独立等概) (独立信源) (一阶马氏源) (n-1阶马氏源) 由平稳性与熵的不增原理,有: 可见,符号相关程度越大,熵越小,反之亦然。 为描述信源的相关性,引入信源效率和剩 余度的概念。 信源效率 信源剩余度 1 离散信源X的N次扩展源的熵 ,仅当信源无记忆时等式成立; 离散信源X的N次扩展源的平均符号熵 ,仅当信源无记忆时等式成立。 2.有记忆信源的符号熵: 并且 3.马氏源的符号熵: 其中 , 4.信源剩余度 设独立随机序列 , , , , 随机序列 与 的关系为 其中 为模2加;问:(1)随机序列 是否为马氏链?(2)如果是马氏链,那么求状态转移概率并画状态转移概率图。 3.5.2 例 3.5.2 马氏源的产生模型(2) 解: 3.5.2 马氏源的产生模型(3) 序列 为有记忆序列,在n时刻的取值仅与n-1时刻与n-2时刻有关,而与以前的时间无关,因此 构成二阶马氏链。 有一个二元马氏链X,符号集为{0,1},其中符号转移概率为 , ;计算该信源三次扩展源的所有符号的概率。 3.5.3 例 3.5.3 马氏链N次扩展源的熵的计算(1) 解: 首先求平稳分布 3.5.3 马氏链N次扩展源的熵的计算(2) 类似得到 做映射 ,i = 0,…,N-m,其中i为时间标号,j为状态序号。 H(X1X2…XN) = H(Sm+1Sm+2…SN+1) 其中,Si=Xi-mXi-m+1…Xi-1 利用熵的可加性,将上式展开,并利用马氏性得 H(X1X2…XN) = H(Sm+1)+ H(Sm+2/Sm+1)+…+H(SN+1 /Sm+1Sm+2…SN) 3.5.3 马氏链N次扩展源的熵的计算(3) = H(Sm+1)+ H(Sm+2/Sm+1)+…+H(SN+1 /SN) = H(Sm+1)+ 3.5.3 马氏链N次扩展源的熵的计算(4) 该项由状态转移概率矩阵[P]的第j行所确定。写成矩阵形式 其中, ,为第i状态概率分布行矢量; ,为行矢量,其中每个元素由[P]的每一行所确定。 3.5.3 马氏链N次扩展源的熵的计算(5) ▲ 如果起始状态概率为平稳分布, 则 ▲ N次扩展源的平均符号熵为: 3.5.3 马氏链N次扩展源的熵的计算(6) ▲ 当信源从某一状态转移到另一状态时, 输出符号唯一, 则一个m阶马氏源的符号熵为: ▲ m阶马氏源符号熵仅由平稳分布和状态转移概率矩阵所决定。 3.5.4 马氏源符号熵的计算(1) 计算方法1: ▲ 当信源从某一状态转移到另一个新状态时,存在多个信源序列对应一个状态。这样由状态转移概率矩阵不能确定信源的熵,而只能以状态条件下信源的输出符号的概率求信源的熵。 ▲ 给定当前信源状态条件下信源的输出符号熵为: 计算方法2: 3.5.4 马氏源符号熵的计算(2) ▲ 在给定某特殊状态s1=j和以前的输出X1,X2,…Xm-1条件下当前输出符号Xm的熵满足: 对S1取平均 引理3.5.1: 3.5.4 马氏源符号熵的计算(3) 对于平稳信源,状态概率与时间起点无关,所以 对于m阶平稳马氏源的符号熵为 利用平稳性及马氏性,有 3.5.4 马氏源符号熵的计算(4) 当 给定条件下, 与以前的状态无关 ▲ 为状态平稳分布行矢量 ▲ h的各分量由状态转移概率矩阵的每一行得出的条件熵 3.5.4 马氏源符号熵的计算(5) 3.5.4 马氏源符号熵的计算(6) 定理3.5.2: 平稳马氏源的符号熵为 3.5.4 马氏源符号熵的计算(7) 求信源的极限符号熵 3.5.1 续 解: 例 3.5.4 马氏源符号熵的计算(8) 3.6 信源的相关性与剩余度 ▲信源的相关性 ▲信源剩余度(冗余度) ▲自然语言的相关性和剩余度 3.6.1 信源的相关性 3.6.2 信源剩余度(冗余度) 英文字母概率表 3.6.3 自然语言的相关性和剩余度(1) 0.0005 Z 0.0008 Q 0.0467 H 0.0164 Y 0.0152 P 0.0152 G 0.0013 X 0.0632 O 0.0208 F 0.0175 W 0.0574 N 0.1031 E 0.0083 V 0.0198 M 0.0317 D 0.0228 U 0.0321 L 0.0218 C 0.0796 T 0.0049 K 0.0127 B 0.0514 S 0.0008 J 0.0642 A 0.0484 R 0.0575 I 0.1859 空格 概率 字母 概率 字母 概率 字母 对于实际英文字母组成的信源: 3.6.3 自然语言的相关性和剩余度(2) (比特/符号) 汉字近似概率表 3.6.3 自然语言的相关性和剩余度(3) 0.003/7600 0.003 7600 Ⅳ 0.147/1775 (0.997-0.85)=0.147 2400-625=1775 Ⅲ 0.35/485 (0.85-0.5)=0.35 625-140=485 Ⅱ 0.5/140 0.5 140 Ⅰ 每个汉字的概率Pi 所占概率P 汉字个数 类别 根据上表,可近似估算汉语信源的信息熵: 3.6.3 自然语言的相关性和剩余度(4) (比特/符号) 本 章 小 结 (1) 本 章 小 结 (2) ▲ 马氏链的基本概念 ▲ 齐次马氏链 ▲ 马氏链状态分类 ▲ 马氏链的平稳分布 3.4 有限状态马尔可夫链 ▲ 随机序列 ▲ 每个随机变量 仅依赖于 定义: 3.4.1 马氏链的基本概念(1) ▲ 随机变量 :马氏链在n时刻的状态 ▲ :状态 ▲ 的集合S:状态集合 1) 一阶马氏链的当前状态只与前一个状态有关 2) n阶马氏链的当前状态只与前n个状态有关 3) 马氏链是时间离散,状态也离散的随机过程 4) 状态集合为有限集?有限状态马氏链 状态集合为无限集?无穷状态马氏链 3.4.1 马氏链的基本概念(2) ▲ 描述马氏链的最重要的参数:状态转移概率 ▲ 对于离散时刻m、n,相应的状态转移概率可表示为: 表示从时刻m的i状态转移到时刻n的j状态的概率,m-n表示转移的步数。 是经 步转移的概率。 3.4.1 马氏链的基本概念(3) ▲ ▲ ▲ 一步转移概率 ▲ K步转移概率 ▲ 0步转移概率 系统在任何时刻必处于S中某一状态 转移概率的主要性质: 3.4.1 马氏链的基本概念(4) ▲ 转移概率与起始时刻无关 ▲ ▲ K步转移概率也与起始时刻无关,写成 3.4.2 齐次马氏链 (1) 3.4.2 齐次马氏链 (2) 齐次马氏链的表示方法 转移概率矩阵 状态转移图 由状态 j 转移到状态 2 的概率; 非负 =1 网格图 状态转移图与矩阵有一一对应关系 每时刻的网格节点与马氏链的状态一一对应 3.4.2 齐次马氏链 (3) 3.4.1 一个矩阵,验证此矩阵对应一个齐次马氏链的转移概率矩阵并确定此马氏链的状态数 解: ① 例 元素非负 ② 状态数=3 每行和为1 =1 =1 =1 3.4.1续 画出此马氏链的网格图。 解: 例 3.4.2 齐次马氏链 (4) 3.7.1续 画出此马氏链的状态转移图 解: 例 3.4.2 齐次马氏链 (5) 1 3 2 1 / 3 1 / 4 1 / 3 1 / 4 1 / 4 1 / 4 1 / 3 1 / 2 1 / 2 3.7.1续 求从状态3到状态2的2步转移概率 解: 例 S 2 1/4 1/3 S 2 S 3 S 3 S 1 1/2 1/2 1/4 1/4 3.4.2 齐次马氏链 (6) 1) 计算从m时刻从s3经m+1时刻某状态sk到m+2时刻s2的转移概率 2) 对1)中计算的经m+1时刻的所有状态sk(k=1,2,3)概率相加,得到所求结果。计算得 下面分两步来计算: 3.4.2 齐次马氏链 (7) 计算从状态i到状态j的2步转移概率可通过下式: Kolmogorov-Chapman方程(1) 由此例可以看出: 2) 是 的第(i,j)个元素 3) 是 的m次幂 的第(i,j)个元素 4) Kolmogorov-Chapman方程(2) 5) 设马氏链的初始状态概率分布为 其中J为状态数,经k步转移后的状态概率分布为 ,则有: 因此,一个齐次马氏链,当初始状态概率分布给定后,可计算转移后任何时刻的状态概率分布。 3.4.2 设例3.4.1中马氏链的初始状态的概率分布为1/2、1/4、1/4,分别求1步转移后和2步转移后的状态的概率分布。 解: 例 Kolmogorov-Chapman方程(2) 3.4.3 马氏链状态分类 (1) ▲ 若对某一n≥1,有 ,则称状态j可由状态i到达,记为 i→j ▲ 如果 ,且 ,则称状态i与状态j可互通,记为 ▲定义每个状态都与该状态本身互通,即互通关系满足自反性 ▲ 互通关系还满足对称性和传递性 3.4.3 马氏链状态分类 (2) 3.4.3 按互通性将状态分成若干类(子集) 解: 例 3.4.3 马氏链状态分类 (3) 常返态 过渡态 周期的 非周期 最大公约数 1 =1 3.4.3 马氏链状态分类 (4) 对任何马氏链(有限或无限可数状态),同一类中所有状态都有相同周期。 定理3.4.1: 非周期的常返态称为遍历态 ▲ 定义: 若对任意整数m,n,马氏链的状态分布满足 则称 为平稳分布,或稳态分布 ▲ 其中, 为平稳分布行矢量 3.4.4 马氏链的平稳分布 (1) (3.4.11) 3.4.4 马氏链的平稳分布 (2) ▲ 平稳马氏链 ▲ 定理3.4.2 如果一个遍历有限状态马氏链的转移概率矩阵为[P],那么 (3.4.12) 3.4.4 马氏链的平稳分布 (3) 3.4.4 马氏链的平稳分布 (4) ▲ 对于有限状态马氏链,稳态分布恒存在 ▲ 如果马氏链中仅存在一个常返类,则方程(3.4.11)的解是唯一的;如果存在r个常返类,则具有r个线性独立的矢量解 ▲ 如果马氏链中仅存在一个常返类而且是非周期的(即遍历的),则(3.4.12)式成立;如果有多个常返类,但都是非周期的,则 也收敛,但矩阵的每行可能不同;如果马氏链具有一个或多个周期常返类,则 不收敛 3.4.4 马氏链的平稳分布 (5) 3.4.4 一马氏链的转移概率矩阵如下,问此马氏链是否具有遍历性并求平稳分布和 的值 解: 例 1 2 3 1 / 2 1 / 3 1 / 2 1 / 2 1 / 6 1 3.4.4 马氏链的平稳分布 (6) 一马氏链的状态转移矩阵如下,确定它的n次幂是否收敛并求其平稳分布 3.4.4 马氏链的平稳分布 (7) 3.4.5 解: 例 1 1 1 2 ▲ 马氏源的基本概念 ▲ 马氏源的产生模型 ▲ 马氏源N次扩展源熵的计算 ▲ 马氏源符号熵的计算 3.5 马尔可夫信源 ▲ 当前时刻输出符号的概率仅与当前时刻的信源状态有关 ▲ 当前时刻的信源状态由前一时刻信源状态和前一时刻输出符号唯一确定。 马氏源的定义: 3.5.1马氏源的基本概念(1) 给定二阶马氏源符号集A={0,1},转移概率分别为:p(0/00)=p(1/11)=0.8,p(1/00)=P(0/11)=0.2,p(0/01)=p(0/10)=p(1/01)=p(1/10)=0.5,确定该马氏源的状态,写出状态转移矩阵,画出信源的状态转移图。 3.5.1 例 3.5.1马氏源的基本概念(2) 解: 3.5.1马氏源的基本概念(3) m阶马氏链的符号转移概率已给定 2) 做m长符号序列到信源状态的映射 , 取遍 ,i=1,…,m; 状态取自 , 为状态数; 3) 符号转移概率转换成状态转移概率 其中 4) 得到一阶马氏源模型: m阶马氏源的处理方法 3.5.2 马氏源的产生模型(1) * * 第三章 离散信源 北京邮电大学 信息工程学院 ▲ 离散信源的分类与数学模型 ▲ 离散无记忆信源的熵 ▲ 离散平稳信源的熵 ▲ 有限状态马尔可夫链 ▲ 马尔可夫信源 ▲ 信源的相关性与剩余度 本章内容 3.1 离散信源的分类与数学模型 ▲ 信源离散信源的分类 ▲ 离散信源的数学模型 3.1.1 离散信源的分类 ▲ 根据信源符号取值→连续/离散 ▲ 根据输入符号间的依赖关系→无记忆/有记忆 ▲ 有限离散信源/无限离散信源 ▲ 平稳信源/非平稳信源 注释 ? A={a1,…,an} →信源的符号集 ? n →符号集的大小 ? ai →随机变量的取值 ? p(ai) → X= ai的概率。 3.1.1 一个二元无记忆信源,符号集A={0,1}, p为X=0的概率,q为X=1的概率,q=1-p;写出信源的模型。 解: 信源的模型: 例 单符号离散无记忆信源 ▲多维离散无记忆信源数学模型: ▲ 信源X的N次扩展源 :设信源为X,由X构成的N维随机矢量集合 ▲ 信源与其扩展源的关系: 离散无记忆信源的N次扩展源 N个连续输出的符号合并 3.1.2 求 例3.1.1 中信源的二次扩展模型。 解: ① 二元信源X的符号集为 {0,1} ② 例 离散无记忆信源的N次扩展源 ▲ 马氏链是随机过程,因此可看成信源,即马尔可夫信源;这种信源是有记忆信源。 ▲ 有限记忆的系统可以用有限状态机来描述。在有限状态机中,既包含状态之间的转移关系,也包含输出与状态之间的关系。 ▲ 可以从有限状态机的概念出发定义马尔可夫信源。 3.1.3 离散有记忆信源的数学模型 3.2 离散无记忆信源的熵 ▲单符号离散无记忆信源的熵 ▲离散无记忆信源N次扩展源的熵 3.2.1 3.2.1 单符号离散无记忆信源的熵 写出例3.1.1 中的二元无记忆信源的熵的表达式。 解: 例 ▲ 具有熵的一切性质 ▲ 对p的导函数为 ▲ p=0.5时,H(p)达到最大值1bit ▲ H(p)是p的上突函数 0.5 1 1 0 p H(p)的主要性质: 3.2.1 单符号离散无记忆信源的熵 3.2.2 离散无记忆信源N次扩展源的熵 定理3.2.1 离散无记忆信源X的N次扩展源 的熵等于信源X熵的N倍,即 证明: 熵的可加性 ① ② 3.2.2 给定离散无记忆信源模型: 求其二次扩展源熵。 解: 例 3.2.2 离散无记忆信源N次扩展源的熵 3.3 离散平稳信源的熵 ▲ 离散平稳信源 ▲ 离散平稳有记忆信源的熵 ▲ 信源X具有有限符号集 ▲ 信源产生随机序列 ▲ 对所有 有 3.3.1 离散平稳信源(1) 定义: 则称信源为离散平稳信源,所产生的序列为平稳序列 ▲ 平稳序列的统计特性与时间的推移无关 3.3.1 离散平稳信源(2) 3.3.1 一平稳信源X的符号集A={0,1},产生随机序列,其中P(x1=0)=p, 求P(xn=1)(n 1)的概率。 解: 例 平稳性 3.3.1 离散平稳信源(3) 3.3.1续 对同一信源,若P(x1=0,x2=1)=b 求P(x4=1/x3=0)。 解: 例 平稳性 3.3.1 离散平稳信源(4) ▲对于平稳信源,条件概率也是平稳的。一般地,有 ▲ 平稳信源的熵与时间起点无关,即 3.3.1 离散平稳信源(5) ▲ 根据平稳性和熵的不增原理 ▲对于X的N次扩展源, 定义平均符号熵为: 3.3.2 离散平稳有记忆信源的熵(1) ▲ 信源X的极限符号熵: 简称:符号熵/熵率 3.3.2 离散平稳有记忆信源的熵(2) 1) 不随N而增加 2) 3) 不随N而增加 4) 存在,且 说明:有记忆信源的符号也可通过计算极限条件熵得到 定理 3.3.1:任意离散平稳信源,若 3.3.2 离散平稳有记忆信源的熵(3) 1) 信源的平稳性 熵的不增原理 这说明对于平稳信源,条件越多,条件熵越不增加 3.3.2 离散平稳有记忆信源的熵(4) 2) 只要证明N个 的和不小于 平均符号熵不小于条件熵 3.3.2 离散平稳有记忆信源的熵(5) 3) 由于 平均符号熵不随序列的长度而增加 根据平均符号熵的定义和2)的结果,有 3.3.2 离散平稳有记忆信源的熵(6) 4) 通过以上证明可得, 3.3.2 离散平稳有记忆信源的熵(7) 先令 ,后令 ,得 另外,由(2)的结果,当 时,有 所以 证毕。 3.3.2 离散平稳有记忆信源的熵(8) ▲ 该定理提供了通过计算极限条件熵得到信源符号熵的方法;这样,当信源为有限记忆时,极限条件熵的计算要比极限平均符号熵的计算容易得多。 ▲ 极限熵等于最小的平均符号熵。 定理3.3.1的注释: 3.3.2 离散平稳有记忆信源的熵(9)

  请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。用户名:验证码:匿名?发表评论


上一篇:2020年南京邮电大学硕士研究生招生学院及专业方    下一篇:北京师范大学新闻传播学院334新闻与传播专业综