• / 47
  • 下载费用:16 金币  

第二章 信源与信源熵

关 键 词:
第二章 信源熵 第二章节信源 第二章信源熵
资源描述:
信息论与编码 第二章 信源及信源熵 信息论与编码 2. 1 信源的描述和分类 2. 2 离散信源熵和互信息 2. 3 连续信源的嫡和互信息 2. 4 离散序列信源的熵 2. 5 冗余度 重点:信源熵和互信息 难点:离散序列信源的熵 信息论与编码 2.1 信源的描述和分类 信源是信息的来源。信源的产生消息、消息序列以及 连续消息的来源。信源具有不确定性,可用概率统计特性 来描述。 一、信源的分类 1、按照信源每次输出符号的个数可分为单符号信源和多 符号信源。 单符号信源:是最简单也是最基本的信源,是组成实际信 源的基本单元。信源每次输出一个符号,通常用离散随机 变量和其概率分布来表示。 信息论与编码 多符号信源:信源每次发出一个符号序列,用随机矢量来 表示。 其中,为输出序列,共有q = 中可能取值。 2、按照时间和取值上的离散和连续性分类。 • 信息论与编码 离散信源是时间上和幅度上都是离散分布的信源,根据信源 发出符号之间的依赖关系可分为无记忆信源、有限记忆信源 和无限记忆信源。 离散无记忆信源:发出单个符号的无记忆信源; 发出符号序列的无记忆信源; 离散有记忆信源: 发出符号序列的有记忆信源 发出符号序列的马尔可夫信源 信息论与编码 二、离散平稳无记忆信源 平稳信源:若当t=i,t=j,有,则称信源是一维平稳的,即任 意两个不同时刻信源发出的符号的概率分布完全相同。若一 维平稳信源还满足,则称信源是二维平稳的,即任意时刻信 源连续发出两个符号的联合概率分布也完全相同。如果各维 联合概率分布均与时间起点无关,则称信源的完全平稳的, 简称离散平稳信源。 无记忆信源:信源发出符号出现的概率与前面符号无关。常 见的无记忆信源有投硬币、掷骰子等等。 无记忆信源各变量组成的随机序列的概率是各变量概率的乘 积, 即p(x) = p(x1x2…xL)= p(x1) p(x2)…p(xL)= 信息论与编码 无记忆信源包括单个符号的无记忆信源和符号序列的无记忆 信源,常见的单个符号的无记忆信源有书信文字、计算机的 代码、电报符号、阿拉伯数字码等等。这些信源输出的都是 单个符号(或代码)的消息,它们符号集的取值是有限的或 可数的。 单符号无记忆信源可以用一维的随机变量及其概率分布来表 示。 例如扔骰子,每次试验结果必然是1~6点中的某一个面朝 上。可以用一个离散型随机变量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,i2…im ∈(1,2, …q) m个字母组成的各种可能的序列就对应于信源全部可能的状 态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= 4 s1 = 00 s2 = 01 s3 = 10 s4 = 11 变换成对应的状态序列为…s2 s3 s2 s4 s4 s3 s1… 信息论与编码 设信源在时刻m处于si状态,它在下一时刻(m+1)状态转移到 sj的转移概率为: pij(m) = p{Sm+1=sj| Sm= si}={sj | si} pij(m):基本转移概率(一步转移概率)、 若pij(m)与m 的取值无关,则称为齐次(时齐)马尔可夫链。 pij= p{Sm+1=sj| Sm= si}= p{S2=sj| S1= si} pij具有下列性质:pij≥0 类似地,定义k步转移概率为pij(k)= p{Sm+k=sj| Sm= si} 由于系统在任一时刻可处于状态空间S ={ s1,s2,…,sQ}中 的任意一个状态,因此状态转移时,转移概率是一个矩阵 信息论与编码 也可将符号条件概率写成矩阵: 上两个矩阵,一般情况下是不同的。 齐次马尔可夫链可以用其状态转移图(香农线图)来表示, 图是一个有着6个状态的齐次马尔可夫链。 信息论与编码 齐次马尔可夫链中的状态可以根据其性质进行分类: 如状态si经若干步后总能到达状态sj,即存在k,使pij(k)>0, 则称si可到达sj; 若两个状态相互可到达,则称此二状态相通; 过渡态:一个状态经过若干步以后总能到达某一其他状态, 但不能从其他状态返回,如图中的状态s1; 吸收态:一个只能从自身返回到自身而不能到达其他任何状 态的状态,如图中的状态s6; 常返态:经有限步后迟早要返回的状态,如s2、s3、s4和s5 ; 周期性的:在常返态中,有些状态仅当k能被某整数d>1整 除时才有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.8 p(1/00)= p(x1/e1)= p(e2/e1)= 0.2 p(0/01)= p(x0/e2)= p(e3/e2)= 0.5 p(1/01)= p(x1/e2)= p(e4/e2)= 0.5 p(0/10)= p(x0/e3)= p(e1/e3)= 0.5 p(1/10)= p(x1/e3)= p(e2/e3)= 0.5 p(0/11)= p(x0/e4)= p(e3/e4)= 0.2 p(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.001=9.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(Y/X) 2) H(XY)=H(Y)+H(X/Y) 证明: 特别地,当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/2 H(Y)=H(1/4)=0.8113 X\Y01 01/41/4 11/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) =1-p(v0 |u0) =1/4 ⑵联合概率: p(u0v0) = p(v0 |u0) p(u0) = 3/4×1/2 = 3/8 p(u0v1) = p(v1 |u0) p(u0) = 1/4×1/2 = 1/8 p(u1v0) = p(v0 |u1) p(u1) = 1/2×1/2 = 1/4 p(u1v1) = p(v1 |u1) p(u1) = [1-p(v0 |u1)] =1/2×1/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)0 2.互易性 I(X;Y)= I(Y;X) 3.平均互信息和各种熵的关系 信息论与编码 当X和Y统计独立时,I(X;Y)=0 H(X)+H(Y)表示在通信前系统的先验不确定性。 H(XY)表示输入集符号经有噪信道传输到输出端,为系统的后 验不确定性。 所以该式表示为: 接收到的平均信息量=系统的先验不确定性-系统的后验 不确定性。 4.极值性 I(X;Y)≦H(X) I(X;Y)≦H(Y) 最好通信I(X;Y)= H(X)= H(Y) 最差通信X和Y统计独立,I(X;Y)=0 5.凸函数性 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(Y)=1.856 bit/符号 由联合分布可得:H(XY)=2.665 bit/符号 ∴I(X;Y)=H(X)+H(Y) -H(XY)=1.257 bit/符号 H(X∣Y)=H(X) -I(X;Y)=0.809 bit/符号 H(Y∣X)=H(Y) -I(X;Y)=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, X2…Xl…XL),序列中的单个符号变量, 即序列长为L。 设随机序列的概率为: 当信源无记忆(符号之间无相关性)时, p(xi)=p(xi1xi2…xiL) = 信息论与编码 若信源的序列满足平稳特性时,有p(xi1)=p(xi2)=… =p(xiL)=p,p(xi)=pL,则信源的序列熵又可表示为 H(X)=LH(x). 平均每个符号熵为 信息论与编码 二、离散有记忆序列信源的熵 1. 对于由两个符号组成的联合信源,有下列结论: (l)H(X1 X2)=H(X1)+H(X2/X1) = H(X2)+ H(X1/X2) (2)H(X1)≥H(X1/X2); H(X2) ≥ H(X2/X1) 当前后符号无依存关系时,有下列推论: H(X1 X2)=H(X1)+H(X2) H(X1)= H(X1/X2) H(X2)= H(X2/X1) 2. 由有限个有记忆序列信源符号组成的序列 设:信源输出的随机序列为X,X=(X1 X2…XL), 则信源的序列熵定义为 H(X)=H(X1X2…XL) =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)时间不变性 p{Xi1=x1,Xi2=x2,…,XiL=xL}= p{Xi1+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/X1X2……Xm)= Hm+1(X) 信息论与编码 2.5 冗余度 冗余度来自两个方面:一是信源符号间的相关性,由于信源 输出符号间的依赖关系使得信源熵减小,这就是信源的相关 性。相关程度越大,信源的实际熵越小;反之相关程度减小 ,信源实际熵就增大。二是信源符号分布的不均匀性,当等 概率分布时信源熵最大。 信息效率: 表示对信源的不肯定的程度。 冗余度 表示对信源分布的肯定性的程度,因为肯定性不含有信息量 ,因此是冗余的。 信息论与编码 在实际通信系统中,为了提高传输效率,往往需要把信源的 大量冗余进行压缩,即所谓信源编码。但是考虑通信中的抗 干扰问题,则需要信源具有一定的冗余度。因此在传输之前 通常加人某些特殊的冗余度,即所谓信道编码,以达到通信 系统中理想的传输有效性和可靠性。
展开阅读全文
  麦档网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:第二章 信源与信源熵
链接地址:https://www.maidoc.com/p-15475674.html

当前资源信息

0****

编号: 20180818145637564910

类型: 共享资源

格式: PPT

大小: 889.00KB

上传时间: 2019-10-09

关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

[email protected] 2018-2020 maidoc.com版权所有  文库上传用户QQ群:3303921 

麦档网为“文档C2C模式”,即用户上传的文档所得金币直接给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的金币归上传人(含作者)所有。
备案号:蜀ICP备17040478号-3  
川公网安备:51019002001290号 

本站提供办公文档学习资料考试资料文档下载


收起
展开