当前课程知识点：信息论 > 第三章 信源的熵率、冗余度与马尔科夫信源编码 > 第十五讲 平稳有记忆Markov信源 > 第十五讲 平稳有记忆Markov信源课程视频
各位老师 同学大家好
上一讲我们针对离散无记忆独立同分布信源
我们重点讨论了非定长编码的最优编码
得到了平均码长定义
重点介绍了Huffman编码的基本原理
但是上一讲主要针对稳恒
离散无记忆信源
这一讲
我们重点给大家介绍离散有记忆信源
重点介绍Markov信源特性
对于一般的稳恒离散信源
考虑到信源某一时刻输出的字母
受其以前时刻发出字母的约束
从而使得信源熵减小
本讲将讨论一类相对简单的
离散稳恒有记忆信源
即信源将来的状态以及送出的状态
只与信源的现在的状态有关
而与信源过去的状态无关
因为将来的状态只取决于
现在的状态以及其后发出的字母
换句话说
将来的状态必须借助于
现在或者过去历史状态加以描述
一旦现在的状态确定
将来的状态
将不会再与过去状态发生联系
我们选择随机过程中Markov模型
来描述这种最简单又最常用的
离散有记忆信源
所以称该信源为Markov信源
本讲只研究时间离散
状态也离散的Markov信源
设信源的字母表为 a1 a2 ak等
信源的输出序列为u1 u2 等
若信源输出的某一个字母的概率
与以前的m字母无关
则此m个字母组成的各种可能的序列
就对应于信源全部可能的状态1到S
S等于K的m次方
信源在各时刻的状态
可以组成信源状态序列
记作 S1 S2 SN等等
信源在时刻n由状态i到时刻n+1时
对应的状态为j的概率
称为状态转移概率
记作式(1)
该式子表示为
n时刻目标在状态s经过1步
在n+1时刻到达状态j
若(1)表示状态转移过程与时间的起点无关
则此类Markov链为时间齐次的Markov链
Markv链的m步转移概率如式(2)所示
公式(2)表示
n时刻处于状态i
经过m步后
在m+n时刻目标所处的状态为j.
对于时齐次的Markov链
可借助于式(3) 表示
chapman-kolmogorov方程
如式(4)表示
式(4)可借助于图1表示
即m时刻状态i经过m步
在时刻m+n进入状态k
然后从状态k出发
经过r步骤最后到达状态j
大家必须注意
中间的r状态可以有很多种
所以必须借助于求和
对于时间齐次的Markov链
如式(5)所示;
时齐马尔科夫链可借助于
图2状态转移图表示
该图表示6个状态的时齐Markov链
时齐Markov中的各个状态
可根据其性质对其进行分类
如果状态i经过若干步后总能到达状态j
即存在n使得
如果n步转移概率大于零
则称状态i可到达状态j
若两状态相互之间可以到达
则称两状态互通
如果一个状态经过若干步以后
总能到达某一其他状态
但是不能从其他状态返回
则此状态为过渡态
如状态1
如果只能从自身返回到自身
而不能到达其他任何状态的状态称为吸收态
状态6
如果经过有限步以后
迟早要返回的状态称为常返态
如图中的2,3,4和5状态
在常返态中
有些状态仅当n能被整数d整除时
才有n步骤转移概率大于零
则称该状态为周期性的
如图中的4和5
其周期为2
对于n步骤转移概率大于零的所有n值
其最大公约数为1的状态称为非周期的
常返态的状态称为遍历状态
总结
根据状态空间之间的可达性
可对状态空间进行分解
若状态中的某一个子集中的任何一个状态
都不能到达子集以外的任何状态
则称该子集为闭集
闭集除了自身全体外
再没有其他闭集的闭集称为不可约的
如｛2 3 4 5｝
｛2,3｝和｛4,5｝
但2,3和4,5才是不可约的
当然
任何有限时齐Markov链的状态集合
总可以分解为既约闭集以及过渡态集合
吸收态集合
一个不可约非周期
状态有限的Markov链
其n步转移概率大于零时
在n趋于无穷大时刻
趋于一个与初始状态无关的极限概率P(j)
其满足方程组是式(6)的唯一解
称P(j)为Markov链的一个平稳分布
所以一个Markov链从一个既约的
遍历的状态集合出发
经过足够长的时间以后
此时Markov链具备稳恒性与遍历的特性
在此之前
其概率有一段的逐渐变化的过渡过程
在过渡过程阶段
需要用状态转移概率和初始时刻的概率
分布加以描述
时齐次Markov链物理模型
Markov信源
可以借助于等价的物理系统加以说明
通过该模型我们可以发现
独立同分布的离散无记忆信源
与Markov信源之间的联系
如图3所示
将独立同分布离散无记信源序列
输入一个系统
在物理结构上加一个反馈环节
如红箭头表示
输出信号即为Markov信源
此外对于非周期正常返
不可约遍历的Markov信源
从态序图上看
该态序图满足自反
对称以及传递的特性
对于稳恒离散Markov信源
本讲给出离散Markov信源的熵率计算公式
如式子(7)所示
本讲给出了稳恒离散的Markov信源的熵率
至于详细证明过程
这里不在详细的赘述
评述
Markov信源的熵率是由条件熵组成的
与离散无记忆信源相比
由于Markov信源字母的分布不均匀
以及信源字母序列的前后之间的约束关系
使Markov信源的熵率更小
Markov信源熵
可以借助于以前学过噪声熵
来类比逻辑的等效
但需要强调一下
信源熵在概念上决不能与噪声熵混淆
因为Markov信源熵描述的是信源
而噪声熵描述的是信道
物理意义扩展
将一步转移概率矩阵
等效为一个前向转移逻辑信道
将稳态分布作为输入等效的
独立同分布离散无记忆信源序列
Markov信源熵可以等价于等效的噪声熵
顺便提及一下
我们学过的数字电路中的时序电路
现态与次态之间的状态转移过程
就可以借助于离散稳恒的有记忆信源来描述
这里鉴于时间关系我们不再做详细地赘述
这一讲我们就讲到这里
-第一讲 信息论课程介绍以及信息论的概念 描述
--课件PPT
-第一章 学习材料
--思考与扩展
-第一章 作业
--第一章 作业
-同步阅读训练 关于中国新型肺炎数学模型的建立
--同步训练
-第二讲 离散熵 离散互信息 连续随机变量的熵与互信息
--第二讲 离散熵 离散互信息 连续随机变量的熵与互信息视频
--课件PPT
-第三讲 熵函数的定义
--第3讲PPT
-第四讲 熵函数的上凸性证明 案例的思考与扩展 熵函数的进一步讨论
--第四讲 熵函数的上凸性证明 案例的思考与扩展 熵函数的进一步讨论视频
--课件PPT
-第五讲二元变量的联合熵 联合熵的几种情形的讨论 联合熵不等式的证明
--第五讲 二元变量的联合熵 联合熵的几种情形的讨论 联合熵不等式的证明视频
-第六讲 互信息的定义 互信息的公式推导 平均互信息的几种情形的讨论
--第六讲 互信息的定义 互信息的公式推导 平均互信息的几种情形的讨论视频
-第七讲多变量平均互信息关系式证明 互信息函数的性质 互信息函数公式的进一步研究
--第七讲 多变量平均互信息关系式证明 互信息函数的性质 互信息函数公式的进一步研究视频
-第八讲 连续随机的熵函数与互信息
-第九讲 鉴别信息
-第二章 课程课件PPT
--第二章 学习材料
-第二章 作业练习与思考
--第二章 作业
--课外材料补充
-第十讲 平稳 离散 无记忆稳恒信源
-第十一讲 定长编码定义与渐进等同分割定理
-第十二讲 唯一可译码定理以及前缀码的构造
-第十三讲 变长编码的平均码长定理
-第十四讲 Huffman编码
-第十五讲 平稳有记忆Markov信源
-第十六讲 Markov信源的变长编码以及案例介绍
--第十六讲 Markov信源的变长编码以及案例介绍课程视频
-第三章 学习材料课件
-第三章 作业练习与思考
--第三章 作业
-第十七讲 信道、 信道模型以及分类
-第十八讲 前向信道状态转移概率矩阵引入与平均互信息
--第十八讲 前向信道状态转移概率矩阵引入与平均互信息课程视频
-第十九讲 离散无记忆信道的信道容量以及传输速率
-第二十讲 信道容量解的充分必要条件以及优化方法的介绍
--第二十讲 信道容量解的充分必要条件以及优化方法的介绍课程视频
-第二十一讲 对称离散无记忆信道
-第二十二讲 准对称离散无记忆信道 删除信道 案例分析
--第二十二讲 准对称离散无记忆信道 删除信道 案例分析课程视频
-第二十三讲 准对称离散无记忆信道案例分析
-第二十四讲 串联信道的信道容量
-第二十五讲 并联信道信道分类
-第二十六讲 连续信道
-第二十七讲 高斯分布函数在信道估计中的应用
-第二十八讲 重要定理的证明过程(重点关注证明过程技巧 如等效 与对数不等式的应用)
-第二十九讲 并联信道的信道容量费用函数优化建模以及在MIMO中的应用（5G 6G中应用）
--第二十九讲 并联信道的信道容量费用函数优化建模以及在MIMO中的应用课程视频
-第三十讲 模拟信道下的信道容量费用函数
-第四章 学习材料课件
--课堂课件PPT
--正交变换
-第四章 课外阅读材料 衰落信道描述 优化方法及介绍 5G 6G介绍
-- 课外阅读材料1
--阅读材料3
-第四章 作业练习与思考
--第四章 作业
-第三十一讲 熵压缩编码与信源的信息速率失真函数
-第五章 学习材料课件
--学习材料的补充
-第五章 作业
-第三十二讲 错误概率与译码似然准则
-第三十三讲 有噪信道编码以及最大似然准则引入
--菲诺不等式的讨论
--课件PPT
-第三十四讲 信道编码基本概念介绍
-第三十五讲 线性分组码的数学支撑 线性空间的引入
--第三十五讲 线性分组码的数学支撑 线性空间的引入课程视频
--课件PPT
-第三十六讲 线性分组码的生成矩阵与校验矩阵引入
-第三十七讲 伴随式 、错图样与译码
--课件PPT
-第三十八讲 循环码及其多项式描述 生成多项式引入
--第三十八讲 循环码及其多项式描述 生成多项式引入课程视频
--课件PPT
-第三十九讲 循环码及其矩阵描述
--课件PPT
-第四十讲 循环码的构造
--课件PPT
-第四十一讲 卷积码基本概念介绍
--课件PPT
-第四十二讲 卷积码及其图形描述 篱笆图 树形图
--第四十二讲 卷积码及其图形描述 篱笆图 树形图 课程视频
--课件PPT
-第四十三讲 卷积码的译码过程
-第六章 学习材料课件
--第六章 学习材料
-第六章 课外阅读材料 卷积码 阅读材料
-第六章 作业练习与思考
--第六章 作业
-翟永智关于Fano不等式以及Shannon第二定理 抗干扰定理知识点的详细解读
-第四十四讲 最小鉴别信息原理与最大熵原理
-第七章 学习材料课件
--第七章 学习材料
-第七章 作业练习与思考
--第七章 作业
-强化训练
--强化训练
-第二三四章计算证明题，请大家点击并下载 2020-2021期末考试试题以及答案
--2020-2021信息论期终考试题（命题人 翟永智 郑文秀 冯丹）
-2020年专家讲座PPT
--杰青讲座
--院士的讲座
