复旦周小林信息论2.信源与信息熵.ppt

* 普通高等教育“十五”国家级规划教材《信息论与编码》 2.3离散序列信源的熵 离散无记忆序列信源 布袋摸球实验，若每次取出两个球，由两个球的颜色组成的消息就是符号序列。若先取出一个球，记下颜色放回布袋，再取另一个球。 * 普通高等教育“十五”国家级规划教材《信息论与编码》 2.3离散序列信源的熵 离散有记忆序列信源 布袋摸球实验，每次取出两个球，由两个球的颜色组成的消息就是符号序列。若先取出一个球，记下颜色不放回布袋，再取另一个球。 * 普通高等教育“十五”国家级规划教材《信息论与编码》 2.3离散序列信源的熵 马尔可夫信源 当信源的记忆长度为m+1时，该时该发出的符号与前m个符号有关联性，而与更前面的符号无关。 * 普通高等教育“十五”国家级规划教材《信息论与编码》 2.3离散序列信源的熵 马尔可夫信源 由于高阶马尔可夫信源需要引入矢量进行分析，现方法将矢量转化为状态变量。定义状态： 信源在某一时刻出现符号概率xj与信源此时所处状态si有关，用条件概率表示p(xj/si),状态转移概率表示为p(sj/si) * 普通高等教育“十五”国家级规划教材《信息论与编码》 2.3离散序列信源的熵 马尔可夫信源 更一般，经过n-m步后转移至sj的概率 * 普通高等教育“十五”国家级规划教材《信息论与编码》 2.3离散序列信源的熵 马尔可夫信源 特别关心n-m=1情况，pij(m,m+1) * 普通高等教育“十五”国家级规划教材《信息论与编码》 2.3离散序列信源的熵 马尔可夫信源 系统在任一时刻可处于状态空间的任意一状态，状态转移时，转移概率是一个矩阵， 一步转移转移矩阵为 * 普通高等教育“十五”国家级规划教材《信息论与编码》 2.3 离散序列信源的熵 马尔可夫信源 k步转移概率pij(k)与l步和k-l步转移概率之间满足切普曼-柯尔莫郭洛夫方程。 定义：如果从状态i 转移到状态j 的概率与m无关，则称这类MovKov链为齐次 对于齐次马尔可夫链，一步转移概率完全决定了k步转移概率。 * 普通高等教育“十五”国家级规划教材《信息论与编码》 2.3离散序列信源的熵 马尔可夫信源 定义：若齐次马尔可夫链对一切i, j存在不依赖于i 的极限，则称其具有遍历性，pj 称为平稳分布 * 普通高等教育“十五”国家级规划教材《信息论与编码》 2.3离散序列信源的熵 马尔可夫信源 定理：设有一齐次马尔可夫链，其状态转移矩阵为P，其稳态分布为wj * 普通高等教育“十五”国家级规划教材《信息论与编码》 2.3离散序列信源的熵 不可约性，对于任意一对I和j， 都存在至少一个k，使pij(k)0. 非周期性，所有pij(n)0的n中没有比1大的公因子。 定理：设P是某一马尔可夫链的状态转移矩阵，则该稳态分布存在的充要条件是存在一个正整数N，使矩阵PN中的所有元素均大于零。 * 普通高等教育“十五”国家级规划教材《信息论与编码》 2.3离散序列信源的熵 Eg.2-1 一个相对编码器，求平稳分布 * 普通高等教育“十五”国家级规划教材《信息论与编码》 2.3离散序列信源的熵 Eg. 2-2 二阶马氏链，X?{0,1},求平稳分布 起始状态 00 01 10 11 1/2 0 1/4 0 1/2 0 3/4 0 0 1/3 0 1/5 0 2/3 0 4/5 S1(00) S2(01) S3(10) S4(11) * 普通高等教育“十五”国家级规划教材《信息论与编码》 2.3离散序列信源的熵 离散无记忆信源的序列熵 * 普通高等教育“十五”国家级规划教材《信息论与编码》 2.3离散序列信源的熵 离散无记忆信源的序列熵 平均每个符号熵（消息熵） * 普通高等教育“十五”国家级规划教材《信息论与编码》 2.3离散序列信源的熵 离散有记忆信源的序列熵和消息熵 * 普通高等教育“十五”国家级规划教材《信息论与编码》 2.3离散序列信源的熵 Eg 2-11 求信源的序列熵和平均符号熵 a1 a2 a3 a1 a2 a3 9/11 1/8 0 2/11 3/4 2/9 0 1/8 7/9 * 普通高等教育“十五”国家级规划教材《信息论与编码》 2.3离散序列信源的熵 离散有记忆信源的序列熵和消息熵 结论1 是L的单调非增函数 结论2 结论3 是L的单调非增函数 结论4 * 普通高等教育“十五”国家级规划教材《信息论与编码》 2.3离散序列信源的熵 马氏链极限熵 * 普通高等教育“十五”国家级规划教材《信息论与编码》 2.3离散序列信源的熵 * 普通高等教育“十五”国家级规划教材《信息