2.2 多符号离散信源的熵.ppt

1 第2章信源熵 2 本章主要内容 2 1单符号离散信源2 2多符号离散平稳信源及熵2 3连续信源及熵 3 本节教学内容 基本要求 1 教学内容多符号离散序列信源及其熵马尔可夫信源及其熵信息的冗余度2 基本要求掌握多符号离散序列信源熵的定义 性质掌握马尔可夫信源熵的模型及其计算掌握信息冗余度的含义 4 2 2多符号离散平稳信源及熵 实际的信源输出的消息是时间或空间上离散的一系列随机变量 这类信源每次输出的不是一个单个的符号 而是一个符号序列 如电报系统 在信源输出的序列中 每一位出现哪个符号都是随机的 这种信源称为多符号离散信源 二元系统中 我们可以把两个二元数字看成一组 会出现四种可能情况 00 01 10和11 我们可以把这四种情况看成一个新的信源称为二元无记忆信源的二次扩展信源 相应的 如果把N个二元数字看成一组 则新的信源称为二元无记忆信源的N次扩展信源 5 如信源序列 000 001 111称为二元信源的3次扩展信源 二元信源的N次扩展信源 n元信源的N次扩展信源 多符号离散信源 的定义 输出消息长度为N 消息中的每个符号取自集合X X中有n个单符号消息 则X的N次扩展信源记作 XN 用N维矢量表示 N位 则该信源XN最多有nN条消息 6 平稳随机序列 所谓平稳是指序列的统计性质与时间的推移无关 非平稳随机序列 信源每发一个符号的概率与时间起点有关 离散无记忆信源 信源序列的前后符号之间是统计独立的 离散有记忆信源 信源序列的前后符号之间是相关的 7 序列信息的熵 序列信息的熵 也称 离散无记忆信源的N次扩展信源的熵 原始信源X的数学模型XN的数学模型 8 H XN NH X 证明 略例 p40页求一个信源的二次扩展信源及其熵 注意 单位 9 离散平稳有记忆信源的N次扩展信源的熵 离散平稳有记忆信源的N次扩展信源的熵离散有记忆信源的N次扩展信源 信源输出的符号相关 且相关性用N个符号间的联合概率表示 离散平稳有记忆信源的N次扩展信源 记忆长度为N 的熵满足 10 例 设某二维离散信源X X1X2的原始信源X的模型为 符号间的相关性用以下的条件概率 转移概率 表示 求原始信源熵H X 条件熵H X2 X1 二次扩展信源熵及其平均符号熵 11 解 代入上式 1 206 1 542验证结论成立 说明 多符号消息的平均符号熵小于等于信源熵 这是由于符号之间的统计相关性造成的 要想提高信源对外提供的平均符号信息量 必须设法消除符号之间的相关性 冗余度 12 N维离散有记忆信源的N次扩展信源的极限熵 也称为 离散平稳有记忆信源的N次扩展信源的极限熵 13 14 马尔可夫信源的极限熵 在许多信源的输出序列中 符号之间的依赖关系是有限的 即 任何时刻信源符号发生的概率只与前面已经发出的若干符号相关 而与更前面发出的符号无关 如 随机变量序列中 m 1 时刻发出的随机变量Xm 1只和前面已经发出的m个随机变量X1X2 Xm有关 而与更前面的随机变量无关 Xi取值于单符号信源符号集合X这类信源称为m阶马尔可夫信源 也叫 m 1 次扩展信源 m阶马尔可夫信源每次只发一个符号 每次发出的符号只与之前发出的m个符号相关 15 马尔可夫信源的组成需要两个条件 1 某时刻信源输出的符号只与之前的m个符号相关 这m个相关的符号称为 信源前一时刻所处的状态 m阶马尔可夫信源在时刻i发符号 16 2 某时刻信源所处的状态由该时刻输出的符号和前一时刻的状态唯一确定 问 m阶马尔可夫信源最多有多少种状态 nm 17 m阶马尔可夫信源的数学模型 且满足 18 m阶马尔可夫信源的熵 19 则 马尔可夫极限熵的计算式 20 例 已知一个二进制一阶马尔可夫信源 信源符号集合为X 0 1 符号间的条件概率为P 0 0 0 25P 1 0 0 75P 0 1 0 5P 1 1 0 5求状态转移概率和状态转移图 信源熵 解 因为是二进制一阶马尔可夫信源所以共有nm 21 2种状态 S1 0 S2 1 状态转移概率为P S1 S1 0 25P S2 S1 0 75P S1 S2 0 5P S2 S2 0 5 21 状态转移图如下 S1 0 S2 1 0 75 0 5 0 5 0 25 22 该一阶马尔可夫信源极限熵为 23 状态概率 注 状态概率一定要列方程组求解 24 例 已知一个二进制二阶马尔可夫信源 信源符号集合为X 0 1 状态转移图符合 P 0 00 P 1 11 0 8P 1 00 P 0 11 0 2P 0 01 P 1 01 P 0 10 P 1 10 0 5求状态转移概率和极限熵 25 P S1 S1 P S4 S4 0 8P S2 S1 P S3 S4 0 2P S3 S2 P S4 S2 P S1 S3 P S2 S3 0 5 解 因为是二进制二阶马尔可夫信源所以共有nm 22 4种状态 S1 00 S2 01 S3 10 S4 11状态转移概率为P 0 00 P 1 11 0 800001111P 1 00 P 0 11 0 200011110P 0 01 P 1 01 P 0 10 P 1 10 0 501100111 发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 26 状态转移图如下 27 该二阶马尔可夫信源的极限熵为 28 29 比较m阶马尔可夫信源和消息长度为m的有记忆信源m阶马尔可夫信源 尽管该信源的记忆长度为m 但符号间的依赖关系延伸到无穷 用状态转移概率来描述这种依赖关系 其熵为极限熵Hm 1 表示马尔可夫信源以转移概率发出每个符号提供的信息量 消息长度为m的有记忆信源 符号间的依赖关系仅限于每一个长度为m的消息 而消息之间是统计独立的 故其熵记作 30 信源的相关性和冗余度不同记忆长度 例m阶马氏信源的记忆长度为 m 的离散平稳信源的熵其中n为原始信源集合的符号个数 说明 记忆长度m越长 极限熵越小 越接近实际信源 31 信源熵的相对率 信源效率 实际熵与最大熵的比值信源冗余度 意义 针