多符号离散信源的熵.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 证明 略例2 2 1 p40页求一个信源的二次扩展信源及其熵 注意 单位 9 离散平稳有记忆信源的N次扩展信源的熵 离散平稳有记忆信源的N次扩展信源的熵离散有记忆信源的N次扩展信源 信源输出的符号相关 且相关性用N个符号间的联合概率表示 离散平稳有记忆信源的N次扩展信源 记忆长度为N 的熵满足 10 例2 2 2 p44 设某二维离散信源X2 X1X2的原始信源X的模型为符号间的相关性用以下的条件概率 转移概率 表示 求原始信源熵H X 条件熵H X2 X1 二次扩展信源熵及其平均符号熵 11 解 12 将计算结果代入上式 1 206 1 542验证说明计算结果符合以上公式 说明 多符号消息的平均符号熵 原始单符号信源熵 这是由于符号之间的统计相关性造成的 要想提高信源对外提供的平均符号信息量 必须设法消除符号之间的相关性 冗余度 13 N维离散有记忆信源的极限熵 也称为 离散平稳有记忆信源的N次扩展信源的极限熵 极限熵 平均符号熵的N取极限值 即原始信源不断发符号 符号间的统计关系延伸到无穷 极限熵 代表一般离散平稳有记忆信源平均每发一个符号提供的信息量 14 15 马尔可夫信源的极限熵 在许多信源的输出序列中 符号之间的依赖关系是有限的 即 任何时刻信源符号发生的概率只与前面已经发出的若干符号相关 而与更前面发出的符号无关 如 随机变量序列中 m 1 时刻发出的随机变量Xm 1只和前面已经发出的m个随机变量X1X2 Xm有关 而与更前面的随机变量无关 Xi取值于单符号信源符号集合X这类信源称为m阶马尔可夫信源 m阶马尔可夫信源每次只发一个符号 每次发出的符号只与之前发出的m个符号相关 16 马尔可夫信源的组成需要两个条件 1 某时刻信源输出的符号只与之前的m个符号相关 这m个相关的符号称为 信源前一时刻所处的状态 m阶马尔可夫信源在时刻i发符号 17 18 2 某时刻信源所处的状态由该时刻输出的符号和前一时刻的状态唯一确定 问 m阶马尔可夫信源最多有多少种状态 nm 所有的状态构成状态空间S 每种状态以一定的概率发生 则得到的数学模型就是m阶马尔可夫信源的数学模型 19 m阶马尔可夫信源的数学模型 且满足 20 m阶马尔可夫信源的熵 也叫m 1次扩展信源 21 则 马尔可夫极限熵的计算式 22 例 已知一个二进制一阶马尔可夫信源 信源符号集合为X 0 1 符号间的条件概率为P 0 0 0 25P 1 0 0 75P 0 1 0 5P 1 1 0 5求状态转移概率和状态转移图 信源熵 解 因为是二进制一阶马尔可夫信源所以状态空间Si 或Sj 共包含nm 21 2种状态 s1 0 s2 1 状态转移概率为P s1 s1 0 25P s2 s1 0 75P s1 s2 0 5P s2 s2 0 5 23 状态转移图如下 S1 0 S2 1 0 75 0 5 0 5 0 25 24 该一阶马尔可夫信源极限熵为 25 状态概率 注 状态概率一定要列方程组求解 26 例2 2 4 P48 已知一个二进制二阶马尔可夫信源 信源符号集合为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求状态转移概率和极限熵 27 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 解 因为是二进制二阶马尔可夫信源所以状态空间Si共有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 28 状态转移图如下 29 该二阶马尔可夫信源的极限熵为 30 31 比较m阶马尔可夫信源和消息长度为m的有记忆信源m阶马尔可夫信源 尽管该信源的记忆长度为m 但符号间的依赖关系延伸到无穷 用状态转移概率来描述这种依赖关系 其熵为极限熵Hm 1 表示马尔可夫信源以转移概率发出每个符号提供的信息量 消息长度为m的有记忆信源 符号间的依赖关系仅限于每一个长度为m的消息 而消息之间是统计独立的 故其极限熵记作 32 信源的相关性和冗余度不同记忆长度 例m阶马氏信源的记忆长度为 m 的离散平稳信源的熵其中n为原始信源集合的符号个数 说明 记忆长度m越长 极限熵越小 越接近实际信源 33 信源熵的相对率 信源效率 实际熵与最大熵的比值信源冗余度 意义 针对最大熵而言 无用信息在其中所占的比例 应用 设计实际通信系统时 考虑效率方面 则应尽量压缩信源冗余度 使平均每发出一个符号的熵最大 考虑可靠性方面 应提高信源冗余度 使平均每个符号携带的平均信息量小 以降低每个符号发生错误时对整体符号的影响力 34 ThankYou