信息论第2章节2010课件

第2章 离散信源及其信息度量,本章内容,2.1 信源的分类及描述 2.2 信源的数学模型 2.3 信息度量和信源熵 2.4信源熵的基本性质和定理 2.5 离散无记忆扩展信源 2.6 离散平稳信源 2.7 马尔可夫信源 2.8 信源的相关性和剩余度,2.1 信源的分类及描述,信源：是发出消息的源，信源的输出的是以符号形式出现的具体消息。,1）信源只输出一个消息符号 按信源发出的消息在时间和幅度上的分布来分类： 离散信源：符号集的取值是有限的。 连续信源：符号集的取值是无限的，即取值是连续的。,2）信源输出一系列符号序列 按信源发出的符号之间的关系来分类： 无记忆信源：信源发出的一个个消息符号彼此统计独立。 有记忆信源：信源发出的各消息符号之间有关联（比如马尔可夫信源）。,按信源的概率分布与时间起点的关系来分类： 平稳信源 非平稳信源,2.2 信源的数学模型,1、单符号离散信源的数学模型,2.3 离散信源信息的度量与信源熵,任何一个物理量的定义都应当符合客观规律和逻辑上的合理性，信息的度量也不例外。直观经验告诉我们： 消息中的信息量与消息发生的概率密切相关：出现消息出现的可能性越小，则消息携带的信息量就越大。 如果事件发生是必然的（概率为1），则它含有的信息量应为零。如果一个几乎不可能事件发生了（概率趋于0），则它含有巨大的信息量。 如果我们得到不是由一个事件而是由若干个独立事件构成的消息，那么我们得到的信息量就是若干个独立事件的信息量的总和。,一、自信息量I(xi)和信息熵H(X),它的单位取决于上式中对数的底数a， 如果取对数的底a=2，则信息量的单位为比特（bit）， 如果取对数的底a=e，则信息量的单位为奈特（nat）， 如果取对数的底a=10，则信息量的单位为哈特（Hart）,例： 已知二元信源输出“0”、“1”两种符号， （1）如果“0”、“1”出现概率相等，计算出现“0”的信息量； （2）如果“0”出现概率为1/3，计算出现“1”的信息量。 解：根据信息量的定义式，可以得到,自信息量的性质：,1）非负性。,2) 单调递减性。,3) 可加性。,2、平均自信息量H(X),是一个随机变量，它不能用来作为整个信源的信息度量。这样，我们引入平均自信息量来表述信源输出消息的不肯定性。,如果一个离散信源输出的消息符号集合为,信源输出的消息符号不同，所含有的信息量就不相同，因此，自信息量,平均自信息量又称为信源熵、信息熵 或无条件熵。,平均信息量可以表示为：,2、平均自信息量H(X),1）单位：它的常用单位为bit/符号。,2）性质 H(X)非负：H(X)0 等号成立的充要条件是当且仅当对某i，pi=1，其余pk=0(ki) 可见：确定信源的熵等于0。,最大熵出现在等概情况下。,例题：设有一个三进制信源，每个符号发生的概率分别为p(x1)=1/2，p(x2)=p(x3)=1/4. 试计算： 符号x1包含的信息量为多少？ 信源中每个符号平均包含的信息量？ 信源每分钟输出3600个符号，通过理想信道传输，收信者每秒钟接收到多少信息量？,解：H(X)=H(1/2,1/4,1/4)=1.5bit/符号,等概时（p=0.5)：随机变量具有最大的不确定性 p=0或1时：随机变量的不确定性消失。,例题：二元信源，每个符号发生的概率分别为p(x1)=p，p(x2)=1-p. 试计算信源熵，并画出熵函数H(p)和p的曲线图。,信息熵的物理意义 1）表示了信源输出前，信源的平均不确定性。 2）表示了信源输出后，每个消息或符号所提供的平均信息量。 3）信息熵反映了变量X的随机性。,二、联合自信息量I(xi,yj)和联合熵H(X,Y),物理意义：一对元素（xi，yj）所含的信息量。,物理意义：每对元素（xi，yj）所含的平均信息量。,例题：联合符号集合（X，Y）上的每个元素对的联合概率如下，试计算： 符号对（x1，y2)包含的信息量为多少？ 联合信源中平均每个符号对所包含的信息量？,解： I(x1,y2)=-log0.25=2bit H（X，Y）=H（0.25,0.25,0.25,0.25）=2bit/符号对,思考： 如何计算三个元素（xi,yj,zk）所含的信息量？ 联合信源（X，Y，Z）平均每组符号包含的信息量？ 更多元素包含的信息量？,三、条件自信息量I(xi/yj)和条件熵H(X/Y),性质： 非负 当且仅当p(xi/yj)=1时，I(xi/yj)=0 I(xi,yj)=I(yj)+I(xi/yj),物理意义： 表示在yj已知的条件下，出现符号xi所提供的信息量。 表示在给定yj条件下，仍对符号xi是否出现存在的不确定性。 如果信道输入为xi，信道输出为yj。 条件自信息量 表示收到消息yj之后，收信者仍对发送信源消息xi存在的不肯定性。 收信者通过信道传输收到yj得到关于xi的信息量 I(xi；yj)=I(xi)-I(xi/yj),H(X/Y)性质：非负 H(X,Y)=H(Y)+H(X/Y)=H(X)+H(Y/X),2、条件熵,当X表示信道输入，Y表示信道输出时，H(X/Y)表示信道损失，表示信宿收到Y后，对信源X仍然存在的不确定性，所以它又称为信道疑义度.,物理意义：,P（x=0）=2/3，信道模型如图所示。,解：,（3）已知发出的和收到的符号，求能得到的信息量。 （4）已知收到的符号，求被告知发出的符号得到的信息量。,例题： 二进制通信系统等概使用符号0和1，由于存在失真，传输时会产生误码，无记忆信道模型如下。试计算 （1）已知发出一个0，求收到符号后得到的信息量。 （2）已知发出的符号，求收到符号后得到的信息量。,解：,四、各种熵的关系,1) H(X,Y)=H(X)+H(Y/X)=H(Y)+H(X/Y) H(X,Y)H(X)+H(Y); X和Y统计独立时，取等号。 H(X/Y) H(X) ; X和Y统计独立时，取等号。 条件熵总是小于或等于无条件熵。,例题,已知两个独立的随机变量x、y的分布律如下，计算,计算H（X）、 H（Z）、 H（X/Y）、 H（XY）、 H（YZ）,五、互信息和平均互信息,3、平均互信息量（详见第3章）,当信道输入用X表示，信道输出用Y表示，则 条件熵H（X/Y）称为信道损失或者疑义度。,物理意义：收信者收到一个消息后所获得的平均信息量。,例题： 二进制通信系统等概使用符号0和1，由于存在失真，传输时会产生误码，无记忆信道模型如下。试计算 （1）H（X）、H（Y）、H（X，Y）、H（X/Y）、H（Y/X）。 （2）信宿收到一个符号后得到关于信源的平均信息量。,2.4 信息熵的基本性质,熵函数的性质:,2.5离散无记忆的扩展信源,1、离散无记忆扩展信源的定义,2、离散无记忆扩展信源的熵,序列熵：（单位为bit/序列）,平稳序列中平均每个符号的熵为： （单位为bit/符号）,离散无记忆信源的序列熵（离散无记忆扩展信源熵）,总 结：,例题：,某一无记忆信源的符号集为0，1，已知p(0)=1/4, p(1)=3/4。 （1）求符号的平均熵； （2）由100个符号构成的序列，求某一特定序列（例如有m个0和100-m个1）的自信息量的表达式； （3）计算（2）中的序列的熵。,解：（1）因为信源是无记忆信源，所以符号的平均熵,（2）某一特定序列（例如：m个0和100-m个1）出现的概率为,所以，自信息量为,（3）序列的熵,2.6 离散平稳信源,一般来说，信源输出的随机序列的统计特性比较复杂，分析起来也比较困难。为了便于分析，我们假设信源输出的是平稳的随机序列，也就是序列的统计性质与时间的推移无关。很多实际信源也满足这个假设。,2、序列中平均每个符号的熵（即平均符号熵）为：,1、序列熵（单位为bit/序列）,二、离散平稳信源的序列熵,当N=2时，可以证明,3、关于“离散平稳信源”的几个结论,例如：,例如：,即：当N给定时，平均符号熵不小于条件熵。,推广结论3可得：,4、实际应用中如何计算极限熵？,特别地，如果信源序列只是前后两个符号之间有关联性，则极限熵为,实际极限熵的近似值：,对于一般的平稳信源，按定义式来计算极限熵很困难。,1）有限N下的条件熵,2）有限N下的平均符号熵,思考的问题,写出离散平稳信源的序列熵和平均符号熵的计算式。它们是否适用于离散无记忆信源？ 极限熵的含义是什么？当消息符号只与前面m个符号有依赖关系，而与更前面发出的符号无依存关系时，此时的极限熵如何表达？,2.7 马尔可夫信源,实际中信源发出的消息符号往往只与前面若干个（比如m个）符号有较强的依赖关系，而与更前面发出的符号依存关系较弱，为此可限制随机序列的记忆长度（m+1），称为有限记忆信源（即阶马尔可夫信源）。,一、马尔可夫信源（即：有限记忆长度信源）,m阶马尔可夫信源,将该时刻以前出现的m个符号组成的序列定义为状态Ei,当信源符号xj出现后，信源所处的状态将发生变化，转入一个新的状态，可用状态转移概率 来表示。马尔可夫信源可用状态转移概率来描述, 也可以用状态转移图来表示。,例题：有一个二阶马尔科夫链X 0，1，其条件概率如下表所示，状态变量E=00，01，10，11,可得状态的一步转移概率,信源在Ei状态下输出符号ak的条件概率：,状态转移图？,1. 马尔可夫特性(无后效性) 已知系统的现在状态，那么系统的将来与过去无关。,2. 马尔可夫信源 某一时刻信源输出的符号只与此刻信源所处的状态有关，而与以前的状态和以前的输出符号无关。 信源在某一时刻所处的状态只由当前输出的符号和前一时刻信源的状态唯一决定。,3.马尔可夫信源的状态转移概率,性质,在 时刻系统处于状态i的条件下，在下一时刻系统处于状态j的条件概率,一步：,性质：,k步：,平稳信源的概率分布特性具有时间推移不变性，而齐次马尔可夫链只要求转移概率具有推移不变性，因此，一般说来，平稳包含齐次；但齐次不包含平稳。,4、 齐次马尔可夫链,如果状态转移概率具有时间推移不变性，则此信源称为齐次马尔可夫信源。,1)转移概率,2）转移概率矩阵,一步转移概率矩阵,性质：每个元素非负，每行之和为1。,k步转移概率矩阵,4）如何确定无条件概率 ？,说明：确定该概率，齐次马尔可夫链需要知道初始概率和转移概率。,5. 齐次遍历马尔可夫信源,如果齐次马尔可夫信源还满足遍历性，即当转移步数足够大时，达到平稳分布后，状态概率与起始状态无关，就称该信源为齐次遍历马尔可夫信源。,稳态分布：不管起始状态Ei是什么，马尔可夫链最后达到稳态。,如何计算齐次遍历马尔可夫链的状态极限概率？,求解方程组：,符号的极限概率？,m阶马尔可夫信源 记忆长度为m+1的有限记忆信源，称为m阶马尔可夫信源。 将该时刻以前出现的m个符号组成的序列定义为状态Si,状态转移概率,符号条件概率,稳态后的符号的极限概率：,复 习,如何计算m阶齐次遍历的马尔可夫链的极限概率？,例题：有一个二阶马尔科夫链X 0，1，其条件概率如下表所示，状态变量E=00，01，10，11,计算： （1）稳定后的状态概率分布； （2）稳定后的符号概率分布。,P（ak|Ei）,P（Ej|Ei）,对于m阶马尔科夫信源，极限熵为,复习：极限熵的定义,二、m阶齐次遍历的马尔可夫链的极限熵,概率 是马尔可夫链的状态的极限概率。,条件熵函数 表示信源处于某一状态 时， 发出一个消息符号的平均不确定性。,其中，,2）m阶齐次遍历的马尔可夫链的极限熵,m阶齐次遍历的马尔可夫链的极限熵,特殊地，对于一阶马尔可夫链的极限熵,一阶马尔可夫信源的状态空间Ei就等于信源符号集ai,1、根据状态转移图，写出一步转移概率矩阵，计算信源所处状态的稳态分布；,时齐遍历的马尔可夫信源极限熵的求解步骤,3、计算信源的极限熵。,一阶马尔可夫信源的状态空间Si就等于信源符号集ai,例题：有一个二阶马尔科夫链X 0，1，其条件概率如下表所示，状态变量S=00，01，10，1