[2018年最新整理]2-6第2章4-5马尔可夫信源.ppt

第2章 信源熵 2.2 多符号离散平稳信源 2.2.1 序列信息的熵 2.2.2 离散平稳信源的数学模型 2.2.3 离散平稳信源的信息熵和极限熵 2.2.4 马尔可夫信源 2.2.5 信源冗余度和信息变差 马尔可夫信源－研究意义 为了求解平稳信源的极限熵，可以用N维的条件熵来近似 要近似离散平稳信源的极限熵，需要知道从1维－N维的条件概率分布，这在一般情况下比较困难 马尔可夫信源－研究意义 虽然马尔可夫信源是一个非平稳的信源，但是当马尔可夫信源进入稳定状态后，就可以看成一个平稳信源 马尔可夫信源熵的求解，只需要知道与前面N－1个分量的相互关系，即只需要知道N维条件概率分布即可，受约束程度大大降低 有限状态马尔可夫链 转移概率pij(m,n) 为了知道系统状态的转化情况，引入转移概率 它表示， 已知在时刻m系统处于状态Ei（Sm取值Ei）的条件下， 经(n-m)步后转移到状态Ej的概率； 或说，在时刻n系统处于状态Ej（Sn取值Ej）的概率； 故，它实际上是一个条件概率。 转移概率的性质： 基本（一步）转移概率 0,1,...,k步转移概率 K步转移矩阵 时齐马尔可夫链 切普曼-柯尔莫哥洛夫方程 具有遍历性的马尔可夫链 马尔可夫链的稳态分布 马尔可夫信源－基本概念 绝对的平稳信源是不存在的，非平稳信源仍然是主流。但一般的非平稳信源研究起来非常复杂。 马尔可夫信源是非平稳信源中的一个特例，满足马尔可夫链的性质，因此可以用马尔可夫链的性质求解信源熵。 马尔可夫信源－基本概念 为了描述马尔可夫信源，除了信源符号集外，还必须引入信源当时所处的“状态” ，信源在某时刻输出符号的概率，与此时信源所处的状态有关 定义信源符号集， 表示信源每一个分量可能的输出： 另外，我们还定义了信源所处的状态 马尔可夫信源－基本概念 【定义】如果信源的输出序列和信源所处的状态满足以下两个条件，该信源为马尔可夫信源 1、某时刻信源输出的符号只与信源所处的状态相关，与以前的状态及以前的输出无关。即 2、信源时刻所处的状态由前一时刻所处的状态，和前一时刻输出的符号唯一确定 马尔可夫信源－基本概念 第一个条件表明：信源的输出只与信源当前所处的状态有关，而与其他因素无关。 第二个条件表明：在特定的状态下，发出特定的符号后，信源状态发生跳变，且必定100％跳变到一个特定的状态。 马尔可夫信源－基本概念 马尔可夫信源输出的符号序列Xl完全由信源所处的状态Sl决定。所以，可将信源的输出符号系列变换成状态系列，将信源输出符号的不确定性问题变成信源状态的转换问题 马尔可夫信源－状态转移图 描述马尔可夫信源，我们可以用马尔可夫链的状态转移图。 1、把每个可能出现的状态用一个圆圈表示； 2、圆圈之间用有向线段连接，表示状态的迁移； 3、在有向线段旁边，注明发出的符号 及在状态 下发出 的条件概率 马尔可夫信源－状态转移图 该马尔可夫信源有三个状态： ，其中设为初始状态，初始概率为 ，等概率的转移到 这两个状态 马尔可夫信源－状态转移图 马尔可夫信源－状态转移图 为什么马尔可夫信源是非平稳的信源： 初始概率为： 进入 或 两个状态。之后无论在哪个状态，下一个输出的符号有80％的可能性是1，转移到 ，有20％的可能性是0，转移到 ，所以 ，与初始概率不同，不满足平稳信源的定义 马尔可夫信源－状态转移图 但是，如果我们把初始状态除外，信源总是以80％的概率发1，以20％的概率发0，处在稳定的状态，这时可以看作是平稳信源 从初始状态到平稳状态总是有个过程的。一般经过足够长的时间后，总能达到稳定状态 正是因为初始概率和稳定概率不一样，在进入稳定状态以前，马尔可夫信源是非平稳的；而在进入稳定状态后，马尔可夫信源可以看做是平稳的 m阶马尔可夫信源 所处的状态与符号序列有关 m阶马尔可夫信源，在任何时刻l，输出分量的概率分布只与前面m个分量的输出有关，我们可以把前面m个分量组成的序列做为l时刻信源所处的状态 如果信源的符号集是 则信源的状态共有个 m阶马尔可夫信源 举例：二元二阶马尔可夫信源。二元指信源可能的输出有2种取值，如0，1；二阶是说信源输出与前两个分量有关 这样的马尔可夫信源共有个 状态，是前两个分量可能取值的排列 m阶马尔可夫信源 对于m阶马尔可夫信源，状态的定义已经给出，状态转移图也可以很容易的画出 例：二元二阶马尔可夫信源，样本空间为(0, 1)，条件概率为： 要求画