离散马氏链信源课件

第六讲第六讲4.离散马氏链信源 平稳信源的m阶马尔可夫信源：信源发出的符号只与前面的m个符号有关，而与更前面出现的符号无关。用概率意义表达为:p(xt/xt-1,xt-2,xt-3,xt-m,)=p(xt/xt-1,xt-2,xt-m)5.状态转移描述对于m阶马尔可夫信源 在某一时刻（m1），信源符号出现的概率，仅与前面已出现的m个符号有关，而与更前面出现的符号无关。可通过引人状态转移概率，从而转化为马尔可夫链，即令 如果信源符号表中的数目为q，则由前面出现的m个符号所组成的序列si共有Qqm种，将这些序列看作是状态集S=s1,s2,sQ，则信源在某一时刻出现符号xj的概率就与信源此时所处的状态si有关，用条件概率表示为p(xj/si)，i=1,2,.,Q；j=l,2,q。当信源符号xj出现后，信源所处的状态将发生变化，并转人一个新的状态。用转移概率表示 如下:pij(m,n)=pSn=sj/Sm=si=psj/si si,sj S 状态转移概率p(sj/si)由信源符号条件概率p(xj/si)确定。为什么状态转移概率是一个条件概率?(1)状态转移概率Pij(m,n)表示已知在时刻m系统处于状态si，或Sm取值si的条件下，经(n-m)步后转移到状态sj的概率。(2)把Pij(m,n)理解为已知在时刻m系统处于状态i的条件下，在时刻n系统处于状态j的条件概率，故状态转移概率实际上是一个条件概率。两个基本转移概率性质:什么叫基本转移概率(一步转移概率)?当n=m+1时，把pij(m,m+1)记为pij(m)，m0，并称为基本转移概率(一步转移概率)。记齐次马尔可夫链转移概率具有时间推移不变性转移概率性质：转移概率可表示为：转移概率可表示为：k步转移概率表示为:k步转移概率矩阵:说明说明:一步转移概率矩阵为一步转移概率矩阵为:一步矩阵P中第i行元素对应于从某一个状态Si转移到所有状态Sj的转移概率，显然矩阵中的每一个元素都是非负的，并且每行之和均为1；一步矩阵P中第j列元素对应于从所有状态Si转移到同一个状态Sj的转移概率，列元素之和不一定为1。一步矩阵P中第i行元素对应于从某一个状态Si转移到所有状态Sj的转移概率，显然矩阵中的每一个元素都是非负的，并且每行之和均为1；第j列元素对应于从所有状态Si转移到同一个状态Sj的转移概率，列元素之和不一定为1。切普曼一柯尔莫郭洛夫方程 说明:(1)k步转移概率P(k)ij与l（lk)步和（k-l）步转移概率之间关系;(2)上式右侧是对第l步的所有可能取值求和，因而也就是k步转移概率。(3)当l=1时,矩阵表示:(p(k)=(p)(p(k-1)=(p)(p)(p(k-2)=(p)k 对于齐次马氏链来说，一步转移概率完全决定了k步转移概率。如何确定无条件概率?令初始概率为p0ip(S0si)如何确定平稳分布的 Wjp(Sk=sj)?其中,Wi和Wj均为稳态分布概率.分析:所以 有非零解W1,W2,WQ。如果再用 就可解得各稳态分布概率 Wj。若 的秩是(n-1)，则解是唯一的。马氏链的可约性马氏链可约性:若对所有 k，都有p(k)ij=0，就意味着一旦出现 Si以后不可能到达Sj,也就是不能各态遍历，或者状态中应把Sj取消，这样就成为可约的了。马氏链不可约性:对任意一对i和j，都存在至少一个k使p(k)ij0，这就是说从Si开始，总有可能到达 Sj.香农线图 S1S3S21/21/21/21/21S4S51/21/2可约马氏链可约马氏链1/21/2注意:(1)S1,S2,S3是三种状态，箭头是指从一个状态转移到另一个状态，旁边的数字代表转移概率。这就是香农提出的马尔可夫状态图，也叫香农线图。(2)由状态S3转移到S1的转移概率p(k)31=0，因为一进人状态S3就一直继续下去，而不会再转移到其他状态。P(k)41=0也是明显的，因S4和S1之间没有连接箭头，因此这种链就是可约的。马氏链周期性 非周期性，就是所有p(k)ii0的n中没有比1大的公因子。S1S4S21/21/21/2周期性马氏链周期性马氏链S31/21/21/21/21/21/2注意:(1)上图周期为2.因为从S1出发再回到S1所需的步数必为2，4，6，.(2)p(n)ij矩阵 当k为奇数时 当当k为偶数时为偶数时 若起始状态为s1，则 经奇数步后，Sk=sj的概率为 达不到稳定状态达不到稳定状态!经偶数步后经偶数步后例 2-4-2+TXrYr101qqpp输入的码Xr(r=1,2,)是相互独立的，取值0或1，且已知p(X=0)=p，p(X=1)=1-p=q，输出的码是Yr，显然有 Y1=X1，Y2X2 Y1 其中 表示模2加，那么Yr就是一个马氏链，因Yr确定后，Yr+1布只与Yr有关，与Yr-1、Yr-2等无关，且知Yr序列的条件概率为 p00=p(Y2=0/Y1=0)=p(X=0)=p p01=(Y2=1/Y1=0)=p(X=1)=q p10=p(Y2=0/Y1=1)=p(X=1)=q p11=p(Y2=1/Y1=1)=p(X=0)=p 说明:(1)转移矩阵为，它与r无关，因而是齐次的。(2)由图容易验证该马氏链具有不可约性和非周期性 问题：1.1.冗余度产生的原因？2.2.信息效率、冗余度的定义？第五节第五节 冗余度冗余度 问题1 1：冗余度产生的原因 冗余度（多余度、剩余度）表示给定信源在实际发出消息时所包含的多余信息。冗余度来自两个方面，一是信源符号间的相关性，由于信源输出符号间的依赖关系使得信源熵减小，这就是信源的相关性。相关程度越大，信源的实际熵越小，趋于极限熵H（X）；反之相关程度减小，信源实际熵就增大。另一个方面是信源符号分布的不均匀性，当等概率分布时信源熵最大。而实际应用中大多是不均匀分布，使得实际熵减小。当信源输出符号间彼此不存在依赖关系且为等概率分布时，信源实际熵趋于最大H0（X）。问题2 2：信息效率、冗余度的定义 信息效率 表示不肯定的程度 冗余度 表示肯定性的程度，因为肯定性不含有信息量，表示肯定性的程度，因为肯定性不含有信息量，因此是冗余的。因此是冗余的。书 P P28 28 例子 由上述例子可看出：由于各个符号出现的概率不均匀 所以：H H1 1H H0 0随着序列增长，字母间的相关性越来越强:所以：H H H H3 3H H2 2正是因为信源符号中存在的这些统计不均匀性和相关性，才使得信源存在冗余度。当英文字母的结构信息已预先充分获得时，可用合理符号来表达英语，例如传送或存储这些符号，可大量压缩，100100页的英语，大约只要2929页就可以了。结论：在实际通信系统中，为了提高传输效率，往往需要把信源的大量冗余进行压缩，即所谓信源编码。但是考虑通信中的抗干扰问题，则需要信源具有一定的冗余度。因此在传输之前通常加人某些特殊的冗余度，即所谓信道编码，以达到通信系统理想的传输有效性和可靠性。作业:2-18到2-21 2-23到2-29