多符号离散信源的熵.ppt

第2章 信源熵 相比一张哈弗大学的文凭，养成良 好的习惯对一个人的成功更重要。 比尔.盖茨 1 本章主要内容 n2.1单符号离散信源 n2.2多符号离散平稳信源及熵 n2.3连续信源及熵 2 本节教学内容、基本要求 n1、教学内容 n多符号离散序列信源及其熵 n马尔可夫信源及其熵 n信息的冗余度 n2、基本要求 n掌握多符号离散序列信源熵的定义、性质 n掌握马尔可夫信源熵的模型及其计算 n掌握信息冗余度的含义 3 2.2 多符号离散平稳信源及熵 n实际的信源输出的消息是时间或空间上离散的一系列 随机变量。这类信源每次输出的不是一个单个的符号 ，而是一个符号序列。 n如电报系统。 n在信源输出的序列中，每一位出现哪个符号都是 随机的，这种信源称为多符号离散信源。 n二元系统中，我们可以把两个二元数字看成 一组，会出现四种可能情况：00、01、10和 11，我们可以把这四种情况看成一个新的信 源称为二元无记忆信源的二次扩展信源; n相应的，如果把N个二元数字看成一组，则新 的信源称为二元无记忆信源的N次扩展信源。 4 n如信源序列：000、001、.111 n称为二元信源的3次扩展信源。 n二元信源的N次扩展信源： nn元信源的N次扩展信源（多符号离散信源）的定义 ： n输出消息长度为N，消息中的每个符号取自集合 X，X中有n个单符号消息，则X的N次扩展信源 记作：XN，用N维矢量表示： N位 则该信源XN最多有nN条消息。 5 n平稳随机序列： n所谓平稳是指序列的统计性质与时间的推移无关。 n非平稳随机序列：信源每发一个符号的概率与时间起 点有关。 F离散无记忆信源：信源序列的前后符号之间是统计独 立的。 F离散有记忆信源：信源序列的前后符号之间是相关的 。 6 序列信息的熵 n序列信息的熵（也称：离散无记忆信源的N次扩展 信源的熵） n原始信源X的数学模型 nXN的数学模型： 7 nH(XN)=NH(X) 证明：略 n例2.2.1：p40页 求一个信源的二次扩展信源及 其熵。 n注意：单位 8 离散平稳有记忆信源的N次扩展信源的熵 n离散平稳有记忆信源的N次扩展信源的熵 n离散有记忆信源的N次扩展信源：信源输出的符号 相关，且相关性用N个符号间的联合概率表示。 n离散平稳有记忆信源的N次扩展信源（记忆长度为 N）的熵满足： 9 n例2.2.2：p44,设某二维离散信源X2=X1X2的原始 信源X的模型为 符号间的相关性用以下的条件概率（转移概率） 表示： 求原始信源熵H(X),条件熵H(X2|X1)，二次扩展 信源熵及其平均符号熵。 10 n解： 11 n将计算结果代入上式： 1.2061.542 验证说明计算结果符合以上公式。 n说明：多符号消息的平均符号熵=原始单符号信源熵 。这是由于符号之间的统计相关性造成的。 n要想提高信源对外提供的平均符号信息量，必须设法消 除符号之间的相关性（冗余度）。 12 N维离散有记忆信源的极限熵 n（也称为：离散平稳有记忆信源的N次扩展信源的极 限熵） 极限熵：平均符号熵的N取极限值，即原始信源不断发 符号，符号间的统计关系延伸到无穷。 极限熵:代表一般离散平稳有记忆信源平均每发一个符 号提供的信息量。 13 14 马尔可夫信源的极限熵 n在许多信源的输出序列中，符号之间的依赖关系是有限 的。 n即：任何时刻信源符号发生的概率只与前面已经发出的若 干符号相关，而与更前面发出的符号无关。 n如：随机变量序列中， (m+1)时刻发出的随机变量Xm+1 只和前面已经发出的m个随机变量X1 X2 Xm有关，而 与更前面的随机变量无关。 nXi取值于单符号信源符号集合X n这类信源称为m阶马尔可夫信源。 nm阶马尔可夫信源每次只发一个符号，每次发出的符号只 与之前发出的m 个符号相关。 15 n马尔可夫信源的组成需要两个条件： n（1）某时刻信源输出的符号只与之前的m个符号 相关，这m个相关的符号称为”信源前一时刻所处的 状态”。 nm阶马尔可夫信源在时刻i发符号 16 17 n（2）某时刻信源所处的状态由该时刻输出的符号 和前一时刻的状态唯一确定。 SiSi+1Si+2 问：m阶马尔可夫信源最多有多少种状态？ nm 所有的状态构成状态空间S，每种状态以 一定的概率发生，则得到的数学模型就是m阶 马尔可夫信源的数学模型。 18 nm阶马尔可夫信源的数学模型： 且满足 19 nm阶马尔可夫信源的熵： n： 也叫m+1次扩展信源 20 则： 马尔可夫极限 熵的计算式 令所有的状态组成一个状态集合Si或Sj 21 n例：已知一个二进制一阶马尔可夫信源，信源符 号集合为X=(0，1)，符号间的条件概率为 P(0/0)=0.25 P(1/0)=0.75 P(0/1)=0.5 P(1/1)=0.5 n求状态转移概率和状态转移图，信源熵。 解：因为是二进制一阶马尔可夫信源 所以状态空间Si (或Sj) 共包含nm=21=2种状态： s1=0,s2=1,状态转移概率为 P(s1/s1)=0.25 P(s2/s1)=0.75 P(s1/s2)=0.5 P(s2/s2)=0.5 22 n状态转移图如下： S1=0S2=1 0.75 0. 5 0. 50.25 23 n该一阶马尔可夫信源极限熵为： 24 n状态概率： 注：状态概 率一定要列 方程组求解 。 25 n例2.2.4：P48,已知一个二进制二阶马尔可夫信源 ，信源符号集合为X=(0，1)，状态转移图符合： P(0/00)= P(1/11)=0.8 P(1/00)= P(0/11)=0.2 P(0/01)= P(1/01)= P(0/10)=P(1/10)=0.5 n求状态转移概率和极限熵。 26 P(S1/S1)= P(S4/S4)=0.8 P(S2/S1)= P(S3/S4)=0.2 P(S3/S2)= P(S4/S2) =P(S1/S3) =P(S2/S3)=0.5 n解：因为是二进制二阶马尔可夫信源 所以状态空间Si共有nm=22=4种状态： s1=00,s2=01, s3=10，s4=11状态转移概率为 P(0/00)= P(1/11)=0.8 00 00 11 11 P(1/00)= P(0/11)=0.2 00 01 11 10 P(0/01)= P(1/01)= P(0/10)=P(1/10)=0.5 01 10 01 11 发0发1 发1 发0 发0发1 P(S1/S1)= P(S4/S4)=0.8 P(S2/S1)= P(S3/S4)=0.2 P(S3/S2)=P(S4/S2)=0.5 P(S1/S3)=P(S2/S3)=0.5 27 n状态转移图如下： S1=00 S4=11 0.20. 5 0. 5 0.8 S3=10S2=01 0.8 0.2 0. 5 0. 5 28 n该二阶马尔可夫信源的极限熵为： 29 30 n比较m阶马尔可夫信源和消息长度为m的有记忆信 源 nm阶马尔可夫信源：尽管该信源的记忆长度为m， 但符号间的依赖关系延伸到无穷，用状态转移概率 来描述这种依赖关系，其熵为极限熵Hm+1。 n表示马尔可夫信源以转移概率发出每个符号提供的信 息量。 n消息长度为m的有记忆信源：符号间的依赖关系仅 限于每一个长度为m的消息，而消息之间是统计独 立的，故其极限熵记作 31 n信源的相关性和冗余度 n不同记忆长度（例m阶马氏信源的记忆长度为:m） 的离散平稳信源的熵 n其中n为原始信源集合的符号个数。 n说明：记忆长度m越长，极限熵越小，越接近实 际信源 32 n信源熵的相对率(信源效率