离散序列信源的熵课件

2024/7/51问题：1.如何描述离散无记忆序列信源的序列熵？2.如何描述离散有记忆序列信源（平稳序列和齐次遍历马氏链信源）的序列熵？第四节第四节 离散序列信源的熵离散序列信源的熵2023/8/131问题：第四节 离散序列信源的熵2024/7/522.4.1 离散无记忆信源的序列熵 设信源输出的随机序列为X，X（X1 X2XlXL），序列中的变量 即序列长为L。2023/8/1322.4.1 离散无记忆信源的序列熵 设信2024/7/53设：随机序列的概率为：p(X=xi)=p(X1=xi1,X2=xi2,XL=xiL)=p(xi1)p(xi2/xi1)p(xi3/xi1xi2)p(xiL/xi1xi2xiL-1)=p(xi1)p(xi2/xi1)p(xi3/xi12)p(xiL/xi1L-1)式中 xi1L-1=xi1xi2xiL-1 2023/8/133设：随机序列的概率为：2024/7/54分析：（1）当信源无记忆（序列中的符号之间无相关性）时，p(xi)=p(xi1xi2xiL)=2023/8/134分析：2024/7/55其中（2）若信源的序列满足平稳特性（与序号l无关）时，有p(xi1)=p(xi2)=p(xiL)=p，p(xi)pL，则信源的序列熵又可表示为H(X)=LH(x).平均每个符号熵为 HL(X)=H(X)/L=H(x)(单个符号信源的符号熵)2023/8/135其中2024/7/56第四讲第四讲2003年年5月月6日日2023/8/136第四讲2024/7/572.4.2 离散有记忆信源的序列熵 问题1.对于由两个符号组成的联合信源，有下列结 论：（l）H（X1 X2）H（X1）H（X2X1）=H（X2）+H（X1X2）（2）H（X1）H（X1X2）H（X2）H（X2X1）2023/8/1372.4.2 离散有记忆信源的序列熵 问2024/7/58当前后符号无依存关系时，有下列推论：H（X1 X2）H（X1）H（X2）H（X1）=H（X1X2）H（X2）=H（X2X1）2023/8/138当前后符号无依存关系时，有下列推论：2024/7/592.由有限个有记忆序列信源符号组成的序列 设：信源输出的随机序列为X，X(X1 X2XL)，则信源的序列熵定义为 H(X)=H(X1X2XL)=H(X1)+H(X2/X1)+H(XL/X1X2.XL-1)记作 H（X）=H（XL）=2023/8/139由有限个有记忆序列信源符号组成的序列 设2024/7/510平均每个符号的熵为 HL（X）=H（X）/L若当信源退化为无记忆时，有 H（X）=H（Xl）若进一步又满足平稳性时，则有 H（X）=LH（X）2023/8/1310平均每个符号的熵为 2024/7/511例2-4-1 已知:离散有记忆信源中各符号的概率空间为:现信源发出二重符号序列消息（ai,aj），这两个符号的概率关联性用条件概率p(aj/ai)表示，并由下表给出。求离散信源的序列熵和平均每个符号的熵?2023/8/1311例2-4-1 已知:离散有记忆信源中2024/7/512aiaja0a1a2a09/112/90a11/83/41/8a202/97/92023/8/1312ai 2024/7/513解：条件熵 H（X2X1）=比特/符号单符号信源熵 比特/符号发二重符号序列的熵 H（X1 X2）=H（X1）+H（X2/X1）=1.543+0.872=2.415 比特/符号平均符号熵 H2（X）=H（X2）/2=1.21 比特/符号2023/8/1313解：条件熵 2024/7/514说明：比较上述结果可得：H2（X）H1（X），即二重序列的符号熵值较单符号熵变小了，也就是不确定度减小了，这是由于符号之间存在关联性（相关性）造成的。2023/8/1314说明：2024/7/5153.离散平稳序列信源(1)时间不变性:联合概率具有时间推移不变性：pXi1=x1,Xi2=x2,.,XiL=xL =pXi1+h=x1,Xx2+h=x2,XiL+h=xL 2023/8/1315 离散平稳序列信源2024/7/516(2)H(XL/XL-1)是L的单调递减函数证明:H(XL/X1X2XL-1)H(XL/X2X3XL-1)(条件较多的熵小于或等于减少一些条件的熵)=H(XL-1/X1X2XL-2)（平 稳性）H(XL-1/X2X3XL-2)(条件较多的熵小于或等于减少一些条件的熵)=H(XL-2/X1X2XL-3)（平稳性）H(X2/X1)2023/8/1316(2)H(XL/XL-1)是L的单2024/7/517(3)HL(X)H(XL/XL-1)证明:HL(X)=H(X1X2XL)/L =H(X1)+H(X2/X1)+H(XL/X1X2XL-1)/L LH(XL/X1X2XL-1)/L =H(XL/XL-1)2023/8/1317(3)HL(X)H(XL/XL-2024/7/518(4)HL(X)是L的单调递减函数证明:LHL(X)=H(X1X2XL)=H(X1X2XL-1)+H(XL/X1X2XL-1)=(L-1)HL-1(X)+H(XL/XL-1)(L-1)HL-1(X)+HL(X)所以 HL(X)HL-1(X)同理,有 H(X)HL+1(X)HL(X)HL-1(X)H0(X)2023/8/1318(4)HL(X)是L的单调递减函数2024/7/519(5)H(X)=HL(X)=H(XL/X1X2XL-1)H(X)叫极限熵或极限信息量。证明：HL+k(X)=H(X1X2XL-1)+H(XL/X1X2XL-1)+H(XL+k/X1X2XL+k-1)H(X1X2XL-1)+H(XL/X1X2XL-1)+H(XL/X1X2XL-1)=H(X1X2XL-1)+H(XL/X1X2XL-1)2023/8/1319(5)H(X)=H2024/7/520当固定L时，有 HL+k(X)H(XL/X1X2XL-1)=H(XL/XL-1)又因为 H(XL/XL-1)HL(X)所以，当 时，HL(X)=HL+k(X)得：HL(X)=H(XL/X1X2XL-1)推广可得结论：H(X)H2(X)H1(X)H0(X)式中，H0(X)为等概率无记忆信源单个符号的熵，H1(X)为一般无记忆（不等概率）信源单个符号的熵H2(X)为两个符号组成的序列平均符号熵，依次类推。2023/8/1320当固定L时，有2024/7/521说明:(i)如何计算极限熵是一个十分困难的问题.(ii)在实际应用中常取有限L下的条件熵 H(XL/XL-1)作为H(X)的近似值。(iii)当平稳离散信源输出序列的相关性随着L的增加 迅速减小时，其序列熵的增加量H(XL/XL-1)与相关性有关，相关性很弱，则 H（XL/X1X2XL-1）H（XLX2 XL-1）=H（XL-1/X1 XL-2），增加量不再变小，所以平均符号熵也几乎不再减小。2023/8/1321说明:2024/7/522(6)设信源发出的符号只与前面的m个符号有关，而与更前面出现的符号无关时,有 H(X)=H(Xm+1/X1X2Xm)=Hm+1(X)证明:信源发出的符号只与前面的m个符号有关，而与更前面出现的符号无关。用概率意义表达为 p(xt/xt-1,xt-2,xt-3,xt-m,)=p(xt/xt-1,xt-2,xt-m)则根据（5）可得 =H(Xm+1/X1X2Xm)=Hm+1(X)2023/8/1322(6)设信源发出的符号只与前面的m个2024/7/5234.离散马氏链信源 平稳信源的m阶马尔可夫信源：信源发出的符号只与前面的m个符号有关，而与更前面出现的符号无关。用概率意义表达为:p(xt/xt-1,xt-2,xt-3,xt-m,)=p(xt/xt-1,xt-2,xt-m)2023/8/1323离散马氏链信源 平稳信源的m阶马尔2024/7/5245.状态转移描述对于m阶马尔可夫信源 2023/8/1324状态转移描述对于m阶马尔可夫信源 2024/7/525在某一时刻（m1），信源符号出现的概率，仅与前面已出现的m个符号有关，而与更前面出现的符号无关。可通过引人状态转移概率，从而转化为马尔可夫链，即令 2023/8/1325在某一时刻（m1），信源符号出现的概2024/7/526如果信源符号表中的数目为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)确定。2023/8/1326如果信源符号表中的数目为q，则由前面出2024/7/527为什么状态转移概率是一个条件概率?(1)状态转移概率Pij(m,n)表示已知在时刻m系统处于状态si，或Sm取值si的条件下，经(n-m)步后转移到状态sj的概率。(2)把Pij(m,n)理解为已知在时刻m系统处于状态i的条件下，在时刻n系统处于状态j的条件概率，故状态转移概率实际上是一个条件概率。2023/8/1327为什么状态转移概率是一个条件概率?(12024/7/528两个基本转移概率性质:2023/8/1328两个基本转移概率性质:2024/7/529什么叫基本转移概率(一步转移概率)?当n=m+1时，把pij(m,m+1)记为pij(m)，m0，并称为基本转移概率(一步转移概率)。记2023/8/1329什么叫基本转移概率(一步转移概率)?2024/7/530齐次马尔可夫链转移概率具有时间推移不变性转移概率性质：转移概率可表示为：转移概率可表示为：2023/8/1330齐次马尔可夫链转移概率具有时间推移不变2024/7/531k步转移概率表示为:k步转移概率矩阵:说明说明:一步转移概率矩阵为一步转移概率矩阵为:2023/8/1331k步转移概率表示为:k步转移概率矩阵2024/7/532一步矩阵P中第i行元素对应于从某一个状态Si转移到所有状态Sj的转移概率，显然矩阵中的每一个元素都是非负的，并且每行之和均为1；一步矩阵P中第j列元素对应于从所有状态Si转移到同一个状态Sj的转移概率，列元素之和不一定为1。2023/8/1332一步矩阵P中第i行元素对应于从某一个状2024/7/533切普曼一柯尔莫郭洛夫方程 说明:(1)k步转移概率P(k)ij与l（lk)步和（k-l）步转移概率之间关系;(2)上式右侧是对第l步的所有可能取值求和，因而也就是k步转移概率。2023/8/1333切普曼一柯尔莫郭洛夫方程 说明:2024/7/534 (3)当l=1时,矩阵表示:(p(k)=(p)(p(k-1)=(p)(p)(p(k-2)=(p)k 对于齐次马氏链来说，一步转移概率完全决定了k步转移概率。2023/8/1334 (3)当l=1时,2024/7/535如何确定无条件概率?令初始概率为p0ip(S0si)2023/8/1335如何确定无条件概率?令初始概率为p0i2024/7/536如何确定平稳分布的 Wjp(Sk=sj)?其中,Wi和Wj均为稳态分布概率.2023/8/1336如何确定平稳分布的 Wjp(Sk=s2024/7/537分析:2023/8/1337分析:2024/7/5382023/8/13382024/7/5392023/8/13392024/7/540所以 有非零解W1,W2,WQ。2023/8/1340所以 2024/7/541如果再用 就可解得各稳态分布概率 Wj。若 的秩是(n-1)，则解是唯一的。2023/8/1341如果再用 2024/7/542马氏链的可约性马氏链可约性:若对所有 k，都有p(k)ij=0，就意味着一旦出现 Si以后不可能到达Sj,也就是不能各态遍历，或者状态中应把Sj取消，这样就成为可约的了。马氏链不可约性:对任意一对i和j，都存在至少一个k使p(k)ij0，这就是说从Si开始，总有可能到达 Sj.2023/8/1342马氏链的可约性马氏链可约性:2024/7/543香农线图 S1S3S21/21/21/21/21S4S51/21/2可约马氏链可约马氏链1/21/22023/8/1343香农线图 S1S3S21/21/21/2024/7/544注意:(1)S1,S2,S3是三种状态，箭头是指从一个状态转移到另一个状态，旁边的数字代表转移概率。这就是香农提出的马尔可夫状态图，也叫香农线图。(2)由状态S3转移到S1的转移概率p(k)31=0，因为一进人状态S3就一直继续下去，而不会再转移到其他状态。P(k)41=0也是明显的，因S4和S1之间没有连接箭头，因此这种链就是可约的。2023/8/1344注意:2024/7/545马氏链周期性 非周期性，就是所有p(k)ii0的n中没有比1大的公因子。S1S4S21/21/21/2周期性马氏链周期性马氏链S31/21/21/21/21/21/22023/8/1345马氏链周期性 非周期性，就是所有p(k2024/7/546注意:(1)上图周期为2.因为从S1出发再回到S1所需的步数必为2，4，6，.(2)p(n)ij矩阵 2023/8/1346注意:2024/7/547当k为奇数时 当当k为偶数时为偶数时 2023/8/1347当k为奇数时 当k为偶数时 2024/7/548若起始状态为s1，则 经奇数步后，Sk=sj的概率为 经偶数步后经偶数步后2023/8/1348若起始状态为s1，则经偶数步后 2024/7/549 达不到稳定状态达不到稳定状态!虽然方程组虽然方程组 是有解是有解的为的为 ，所以，为使马氏链，所以，为使马氏链最后稳定，成为遍历的马氏链，还必须有不可约性和非最后稳定，成为遍历的马氏链，还必须有不可约性和非周期性。周期性。2023/8/1349 达不到稳定状态!虽然方程组 2024/7/550例 2-4-2+TXrYr101qqpp2023/8/1350例 2-4-2+TXrYr101qqp2024/7/551输入的码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序列的条件概率为 2023/8/1351输入的码Xr(r=1,2,)是相互独2024/7/552p00=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)由图容易验证该马氏链具有不可约性和非周期性 2023/8/1352p00=p(Y2=0/Y1=0)=p(2024/7/553看P26,例2-4-32023/8/1353看P26,例2-4-32024/7/554计算遍历的m阶马尔可夫信源提供的平均信息量对于齐次、遍历的马尔可夫链，其状态 由 唯一确定因此有：对上式两边同取对数，并对 和 取统计平均，然后取负，可以得到：左边2023/8/1354计算遍历的m阶马尔可夫信源提供的平均信2024/7/555右边即 2023/8/1355右边2024/7/556 是马尔可夫链的平稳分布，表示处于某一状态 时发出一个消息符号的不确定性 看P27,例2-4-4 2023/8/1356 是马尔可2024/7/557问题：1.1.冗余度产生的原因？2.2.信息效率、冗余度的定义？第五节第五节 冗余度冗余度 2023/8/1357问题：第五节 冗余度 2024/7/558问题1 1：冗余度产生的原因 冗余度（多余度、剩余度）表示给定信源在实际发出消息时所包含的多余信息。冗余度来自两个方面，一是信源符号间的相关性，由于信源输出符号间的依赖关系使得信源熵减小，这就是信源的相关性。相关程度越大，信源的实际熵越小，趋于极限熵H（X）；反之相关程度减小，信源实际熵就增大。另一个方面是信源符号分布的不均匀性，当等概率分布时信源熵最大。而实际应用中大多是不均匀分布，使得实际熵减小。当信源输出符号间彼此不存在依赖关系且为等概率分布时，信源实际熵趋于最大H0（X）。2023/8/1358问题1：冗余度产生的原因 冗余度（多余2024/7/559问题2 2：信息效率、冗余度的定义 信息效率 表示不肯定的程度 冗余度 表示肯定性的程度，因为肯定性不含有信息量，表示肯定性的程度，因为肯定性不含有信息量，因此是冗余的。因此是冗余的。2023/8/1359问题2：信息效率、冗余度的定义 信息效2024/7/560 书 P P28 28 例子 由上述例子可看出：由于各个符号出现的概率不均匀 所以：H H1 1H H0 0随着序列增长，字母间的相关性越来越强:所以：H H H H3 3H H2 2正是因为信源符号中存在的这些统计不均匀性和相关性，才使得信源存在冗余度。当英文字母的结构信息已预先充分获得时，可用合理符号来表达英语，例如传送或存储这些符号，可大量压缩，100100页的英语，大约只要2929页就可以了。2023/8/1360 书 P28 例子 由上述例子可看2024/7/561 结论：在实际通信系统中，为了提高传输效率，往往需要把信源的大量冗余进行压缩，即所谓信源编码。但是考虑通信中的抗干扰问题，则需要信源具有一定的冗余度。因此在传输之前通常加人某些特殊的冗余度，即所谓信道编码，以达到通信系统理想的传输有效性和可靠性。2023/8/1361 结论：2024/7/562作业:2-18到2-21 2-23到2-292023/8/1362作业: