第二章 信源及信源熵.ppt

信息论与编码信息论与编码第二章第二章 信源及信源熵信源及信源熵信息论与编码信息论与编码2.1 2.1 信源的描述和分类信源的描述和分类2.2 2.2 离散信源熵和互信息离散信源熵和互信息2.3 2.3 连续信源的嫡和互信息连续信源的嫡和互信息2.4 2.4 离散序列信源的熵离散序列信源的熵2.5 2.5 冗余度冗余度重点：信源熵和互信息重点：信源熵和互信息难点：离散序列信源的熵难点：离散序列信源的熵信息论与编码信息论与编码2.1 信源的描述和分类 信源是信息的来源。信源的产生消息、消息序列以及连续消息的来源。信源具有不确定性，可用概率统计特性来描述。一、信源的分类1、按照信源每次输出符号的个数可分为单符号信源和多符号信源。单符号信源：是最简单也是最基本的信源，是组成实际信源的基本单元。信源每次输出一个符号，通常用离散随机变量和其概率分布来表示。信息论与编码信息论与编码 多符号信源：信源每次发出一个符号序列，用随机矢量来表示。其中，为输出序列，共有q=中可能取值。2、按照时间和取值上的离散和连续性分类。信息论与编码信息论与编码离散信源是时间上和幅度上都是离散分布的信源，根据信源发出符号之间的依赖关系可分为无记忆信源、有限记忆信源和无限记忆信源。离散无记忆信源：发出单个符号的无记忆信源；发出符号序列的无记忆信源；离散有记忆信源：发出符号序列的有记忆信源 发出符号序列的马尔可夫信源信息论与编码信息论与编码二、离散平稳无记忆信源平稳信源：若当t=i,t=j,有,则称信源是一维平稳的，即任意两个不同时刻信源发出的符号的概率分布完全相同。若一维平稳信源还满足，则称信源是二维平稳的，即任意时刻信源连续发出两个符号的联合概率分布也完全相同。如果各维联合概率分布均与时间起点无关，则称信源的完全平稳的，简称离散平稳信源。无记忆信源：信源发出符号出现的概率与前面符号无关。常见的无记忆信源有投硬币、掷骰子等等。无记忆信源各变量组成的随机序列的概率是各变量概率的乘积，即p(x x)=p(x1x2xL)=p(x1)p(x2)p(xL)=信息论与编码信息论与编码无记忆信源包括单个符号的无记忆信源和符号序列的无记忆信源，常见的单个符号的无记忆信源有书信文字、计算机的代码、电报符号、阿拉伯数字码等等。这些信源输出的都是单个符号（或代码）的消息，它们符号集的取值是有限的或可数的。单符号无记忆信源可以用一维的随机变量及其概率分布来表示。例如扔骰子，每次试验结果必然是16点中的某一个面朝上。可以用一个离散型随机变量X来描述这个信源输出的消息。并满足 信息论与编码信息论与编码符号序列的无记忆信源可以用概率矢量来表示。将一维的单符号无记忆信源进行N维扩展可得到符号序列的无记忆信源。例如投三次硬币，“1”代表正面朝上，“0”代表反面朝上。信息论与编码信息论与编码三、马尔科夫信源若信源在某一时刻发出的符号概率除与该符号有关外，还与此前的符号有关，则此类信源为有记忆信源。如果与前面无限个符号有关，为无限记忆信源；如果仅与前面有限个符号有关，为有限记忆信源。有记忆信源序列的联合概率与条件概率有关将这有限个符号记为一个状态，在信源发出的符号概率除与次符号有关外，只与该时刻所处的状态有关，信源将来的状态及其发出的符号只与信源当前的状态有关，而与信源过去的状态无关。这种信源的一般数学模型就是马尔可夫过程，所以称这种信源为马尔可夫信源。信息论与编码信息论与编码马氏链的基本概念m阶马尔可夫信源：信源输出某一符号的概率仅与以前的m个符号有关，而与更前面的符号无关。p(xt|xt-1,xt-2,xt-3,xt-m,x1)=p(xt|xt-1,xt-2,xt-3,xt-m)令si=(xi 1 xi 2 xi m)i1,i2im(1,2,q)m个字母组成的各种可能的序列就对应于信源全部可能的状态S.状态集S S=s1,s2,sQ Q=qm信源输出的随机符号序列为：x1,x2,x i-1,x i信源所处的随机状态序列为：s1,s2,si-1,si,信息论与编码信息论与编码例：二元序列为01011100考虑m=2，Q=qm=22=4s1=00 s2=01 s3=10 s4=11变换成对应的状态序列为s2 s3 s2 s4 s4 s3 s1信息论与编码信息论与编码设信源在时刻m处于si状态，它在下一时刻(m+1)状态转移到sj的转移概率为：pij(m)=pSm+1=sj|Sm=si=sj|sipij(m)：基本转移概率（一步转移概率）、若pij(m)与m 的取值无关，则称为齐次(时齐)马尔可夫链。pij=pSm+1=sj|Sm=si=pS2=sj|S1=sipij具有下列性质：pij0类似地，定义k步转移概率为pij（k）=pSm+k=sj|Sm=si由于系统在任一时刻可处于状态空间S S=s1,s2,sQ中的任意一个状态，因此状态转移时，转移概率是一个矩阵 信息论与编码信息论与编码也可将符号条件概率写成矩阵：上两个矩阵，一般情况下是不同的。齐次马尔可夫链可以用其状态转移图（香农线图）来表示，图是一个有着6个状态的齐次马尔可夫链。信息论与编码信息论与编码齐次马尔可夫链中的状态可以根据其性质进行分类:如状态si经若干步后总能到达状态sj，即存在k,使pij(k)0，则称si可到达sj;若两个状态相互可到达,则称此二状态相通；过渡态：一个状态经过若干步以后总能到达某一其他状态，但不能从其他状态返回,如图中的状态s1；吸收态：一个只能从自身返回到自身而不能到达其他任何状态的状态，如图中的状态s6；常返态：经有限步后迟早要返回的状态，如s2、s3、s4和s5；周期性的：在常返态中，有些状态仅当k能被某整数d1整除时才有pij(k)0，如图中的状态s4和s5，其周期为2；非周期性的：对于pij(k)0的所有k值，其最大公约数为1。遍历状态：非周期的、常返的状态,如图中的状态s2和s3。闭集：状态空间中的某一子集中的任何一状态都不能到达子集以外的任何状态不可约的：闭集中除自身全体外再没有其他闭集的闭集信息论与编码信息论与编码一个不可约的、非周期的、状态有限的马尔可夫链其k步转移概率pij(k)在k时趋于一个和初始状态无关的极限概率p(sj)，它是满足方程组的唯一解；p(sj)或Wj：为马尔可夫链的一个平稳分布，且p(sj)或Wj就是系统此时处于状态sj的概率。信息论与编码信息论与编码例：设一个二元二阶马尔可夫信源，信源符号集为 X=0，1，输出符号的条件概率为：求该信源的状态转移图。信息论与编码信息论与编码解：p(0/00)=p(x0/e1)=p(e1/e1)=0.8p(1/00)=p(x1/e1)=p(e2/e1)=0.2p(0/01)=p(x0/e2)=p(e3/e2)=0.5p(1/01)=p(x1/e2)=p(e4/e2)=0.5p(0/10)=p(x0/e3)=p(e1/e3)=0.5p(1/10)=p(x1/e3)=p(e2/e3)=0.5p(0/11)=p(x0/e4)=p(e3/e4)=0.2p(1/11)=p(x1/e4)=p(e4/e4)=0.8信息论与编码信息论与编码例：有一个二元二阶马尔可夫信源,其信源符号集为0，1，已知符号条件概率：p(0|00)=1/2 p(1|00)=1/2 p(0|01)=1/3 p(1|01)=2/3 p(0|10)=1/4 p(1|10)=3/4 p(0|11)=1/5 p(1|11)=4/5求：信源全部状态及状态转移概率画出完整的二阶马尔可夫信源状态转移图。求平稳分布概率 信息论与编码信息论与编码解：信息论与编码信息论与编码2.2 离散信源熵和互信息一、自信息量信源发出的信息具有不确定性，而事件发生的不确定性与事件发生的概率大小有关，概率越小，不确定性越大，事件发生以后所含有的信息量就越大。小概率事件，不确定性大，一旦出现必然使人感到意外，因而产生的信息量就大；大概率事件，不确定性小，因而信息量小。因此随机变量的自信息量是该事件发生的概率的函数，并且应该满足一下条件：（1）是的严格递减函数，当 时，概率越小，事件发生后的信息量越大。（2）极端情况下，=0时，趋于无穷大；=1时，=0。（3）两个相对独立的不同的消息所提供的信息量应等于它们分别提供的信息量之和，即自信息满足可加性。自信息量信息论与编码信息论与编码自信息量Df：随机事件的自信息量定义为该事件发生概率的对数的负值，设事件的概率为 ，则它的自信息量定义为自信息量的单位与所用对数的底有关：对数底为2时，单位是比特；对数底是自然数e时，单位是奈特；对数底是10时，单位是哈特莱。一般采用以2为底的对数。条件自信息量Df：在事件yj出现的条件下，随机事件xi发生的条件概率为 ，则它的条件自信息量定义为条件概率对数的负值：联合自信息量Df：二维联合集XY上的元素（）的联合自信息量 信息论与编码信息论与编码例：英文字母中“e”出现的概率为0.105，“c”出现的概率为0.023，“o”出现的概率为0.001。分别计算它们的自信息量。解：“e”的自信息量 I(e)=log2 0.105=3.25 bit“c”的自信息量 I(c)=log2 0.023=5.44 bit“o”的自信息量 I(o)=log2 0.0019.97 bit信息论与编码信息论与编码例：设离散无记忆信源 ，其发出的信息(202120130213001203210110321010021032011223210)，求(1)此消息的自信息量是多少？(2)此消息中平均每符号携带的信息量是多少？解：(1)此消息总共有14个0、13个1、12个2、6个3，因此此消息发出的概率是：此消息的信息量是：(2)此消息中平均每符号携带的信息量是：信息论与编码信息论与编码二、离散信源熵信源熵用平均自信息量来表征整个信源的不确定性，平均自信息量又称为信源熵。为信源中各个符号不确定度的数学期望，即单位为：比特/符号 或者 比特/符号序列.信息熵H(X)是表示信源输出后，每个消息(或符号)所提供的平均信息量。某一信源，不管它是否输出符号，只要这些符号具有某些概率特性，必有信源的熵值。例：H(Y)H(X)信源Y比信源X的平均不确定性要大。信息论与编码信息论与编码条件熵定义：在给定某个yj条件下，xi的条件自信息量I(xi/yj)，X 集合的条件熵H（X/yj）为相应地，在给定X（即各个xi）的条件下，Y集合的条件熵H(Y/X)定义为:联合熵定义：联合熵是联合符号集合 XY上的每个元素对xiyj的自信息量的概率加权统计平均值，表示X和Y同时发生的不确定度。信息论与编码信息论与编码联合熵与条件熵有下列关系式：1)H（XY）H（X）H（YX）2)H（XY）H（Y）H（XY）证明：特别地，当X和Y相互独立时，H(XY)=H(X)+H(Y)信息论与编码信息论与编码例：随机变量X和Y的联合概率分布如表所示，求联合熵H(XY)和条件熵H(X/Y)解：=2/4+2/4+1/2=2.5由表可知H(Y/X=0)=1,H(Y/X=1)=0则H(Y/X)=1/2+0=1/2H(Y)=H(1/4)=0.8113XY0101/41/411/20信息论与编码信息论与编码例：二进制通信系统用符号“0”和“1”,由于存在失真,输时会产生误码,用符号表示下列事件：u0：一个“0”发出：u1：一个“1”发出 v0：一个“0”收到；v1：一个“1”收到。给定下列概率：p(u0)1/2,p(v0|u0)3/4，p(v0|u1)=1/2求：已知发出一个“0”,求收到符号后得到的信息量；已知发出的符号,求收到符号后得到的信息量知道发出的和收到的符号,求能得到的信息量；已知收到的符号，求被告知发出的符号得到的信息量。信息论与编码信息论与编码解：p(v1|u0)=1p(v0|u0)=1/4联合概率：p(u0v0)=p(v0|u0)p(u0)=3/41/2=3/8 p(u0v1)=p(v1|u0)p(u0)=1/41/2=1/8 p(u1v0)=p(v0|u1)p(u1)=1/21/2=1/4 p(u1v1)=p(v1|u1)p(u1)=1p(v0|u1)=1/21/2=1/4信息论与编码信息论与编码（3）（4）信息论与编码信息论与编码三、互信息贝叶斯公式：先验概率p(x)似然概率p(y/x)后验概率p(x/y)证据因子p(y)互信息一个事件所给出关于另一个事件的信息，信息论与编码信息论与编码互信息的性质1.互易性：2.当两事件相互独立时，互信息量为零；3.互信息可正可负。互信息为正时，说明一事件的出现有助于肯定另一事件的出现，反之，则是不利的。4.任何两事件之间的互信息量不可能大于其中任意事件的自信息量。信息论与编码信息论与编码例：某地区的天气分布情况如表所示如果有人告诉你：“今天不是晴天”，把这句话作为收到的信息 ，求收到后 ，与各种天气的互信息量。解：把各种天气记作：表示晴天，表示阴天，表示雨天，表示雪天。p(x1|y1)=0,p(x2|y1)=1/2,p(x3|y1)=1/4,p(x4|y1)=1/4 信息论与编码信息论与编码平均互信息 在XY的联合概率空间中的统计平均值为随机变量X和Y间的平均互信息。I(X;Y)=H(X)-H(X/Y)条件熵H(X/Y)表示给定随机变量Y后，对随机变量X仍然存在的不确定性，所以Y关于X的平均互信息是收到Y前后关于X的不确定度减少的量，也就是从Y所获得的关于X的平均自信息量。平均互信息的性质1.非负性 I(X;Y)02.互易性 I(X;Y)=I(Y;X)3.平均互信息和各种熵的关系 信息论与编码信息论与编码当X和Y统计独立时，I(X;Y)=0H(X)+H(Y)表示在通信前系统的先验不确定性。H(XY)表示输入集符号经有噪信道传输到输出端，为系统的后验不确定性。所以该式表示为：接收到的平均信息量=系统的先验不确定性系统的后验不确定性。4.极值性I I（X X；Y Y）H H（X X）I I（X X；Y Y）H H（Y Y）最好通信I I（X X；Y Y）=H=H（X X）=H=H（Y Y）最差通信最差通信X和Y统计独立，I(X;Y)=05.凸函数性P(X)一定时，平均互信息I(X;Y)是信道传递概率分布P(Y/X)的下凸函数，存在最小值，此时信道最差。P(Y/X)一定时，平均互信息I(X;Y)是信源概率分布P(X)的上凸函数，存在最大值，此时这个最大值即是信道容量。信息论与编码信息论与编码例:已知 联合概率分布如表所示，求：H(XY)，H(X),H(Y),H(Y|X),H(X|Y)，I（X;Y)。信息论与编码信息论与编码解：首先求出边缘概率分布 得H(X)=2.066 bit/H(X)=2.066 bit/符号符号 得H(Y)=1.856 bit/H(Y)=1.856 bit/符号符号由联合分布可得：由联合分布可得：H(XY)=2.665 bit/H(XY)=2.665 bit/符号符号I(X;Y)=H(X)+H(Y)I(X;Y)=H(X)+H(Y)H(XY)=1.257 bit/H(XY)=1.257 bit/符号符号 H(XY)=H(X)H(XY)=H(X)I I（X;YX;Y）=0.809 bit/=0.809 bit/符号符号 H(YX)=H(Y)H(YX)=H(Y)I I（X;YX;Y）=0.600 bit/=0.600 bit/符号符号信息论与编码信息论与编码四、数据处理中信息的变化平均条件互信息它表示随机变量Z给定后，从随机变量Y所得到的关于随机变量X信息量。平均联合互信息它表示从二维随机变量YZ所得到的关于随机变量X的信息量。信息论与编码信息论与编码五、熵的性质1.非负性2.对称性3.确定性4.香农辅助定理（极值性）对于任意两个n维概率矢量P=（p1，p2，pn）和Q=（q1，q2，qn），如下不等式成立:5.最大熵定理信息论与编码信息论与编码6.条件熵小于无条件熵（1）条件熵小于信源熵（2）两个条件下的条件熵小于一个条件下的条件熵（3）联合熵小于信源熵之和当X、Y相互独立时，有：信息论与编码信息论与编码2.3 连续信源的熵和互信息一、连续信源的熵随机变量的相对熵熵功率二、最大熵定理1.峰值功率受限均匀分布相对熵最大2.平均功率受限高斯分布相对熵最大3.平均功率大于等于熵功率信息论与编码信息论与编码2.4 离散序列信源的熵一、离散无记忆序列信源的熵设信源输出的随机序列/随机矢量为X，X（X1，X2XlXL），序列中的单个符号变量，即序列长为L。设随机序列的概率为：当信源无记忆（符号之间无相关性）时，p(xi)=p(xi1xi2xiL)=信息论与编码信息论与编码若信源的序列满足平稳特性时，有p(xi1)=p(xi2)=p(xiL)=p，p(xi)pL，则信源的序列熵又可表示为H(X)=LH(x).平均每个符号熵为信息论与编码信息论与编码二、离散有记忆序列信源的熵1.对于由两个符号组成的联合信源，有下列结论：（l）H（X1 X2）H（X1）H（X2X1）=H（X2）+H（X1X2）（2）H（X1）H（X1X2）;H（X2）H（X2X1）当前后符号无依存关系时，有下列推论：H（X1 X2）H（X1）H（X2）H（X1）=H（X1X2）H（X2）=H（X2X1）2.由有限个有记忆序列信源符号组成的序列设：信源输出的随机序列为X，X(X1 X2XL)，则信源的序列熵定义为 H(X)=H(X1X2XL)=H(X1)+H(X2/X1)+H(XL/X1X2.XL-1)记作 H（X）=H（XL）=平均每个符号的熵为 HL（X）=H（X）/L若当信源退化为无记忆时，有 H（X）=H（Xl）若进一步又满足平稳性时，则有 H（X）=LH（X）信息论与编码信息论与编码对离散平稳序列信源，有下列性质：（1）时间不变性pXi1=x1,Xi2=x2,XiL=xL=pXi1+h=x1,Xx2+h=x2,XiL+h=xL（2）H(XL/XL-1)是L的单调递减函数（3）HL(X)H(XL/XL-1)（4）HL(X)是L的单调递减函数（6）设信源发出的符号只与前面的m个符号有关，而与更前面出现的符号无关时,有H(X)H(Xm+1/X1X2Xm)Hm+1(X)信息论与编码信息论与编码2.5 冗余度冗余度来自两个方面：一是信源符号间的相关性，由于信源输出符号间的依赖关系使得信源熵减小，这就是信源的相关性。相关程度越大，信源的实际熵越小；反之相关程度减小，信源实际熵就增大。二是信源符号分布的不均匀性，当等概率分布时信源熵最大。信息效率:表示对信源的不肯定的程度。冗余度表示对信源分布的肯定性的程度，因为肯定性不含有信息量，因此是冗余的。信息论与编码信息论与编码在实际通信系统中，为了提高传输效率，往往需要把信源的大量冗余进行压缩，即所谓信源编码。但是考虑通信中的抗干扰问题，则需要信源具有一定的冗余度。因此在传输之前通常加人某些特殊的冗余度，即所谓信道编码，以达到通信系统中理想的传输有效性和可靠性。