review.ppt

现代信息论基础 程琳兰州大学信息科学与技术学院电信系M Pmail chenglin Address DepartmentofElectronics InformationScience SchoolofInformationScience Engineering LanzhouUniversity TianshuiSouthernRoad222 GansuProvince P R China TheElementsofInformationTheory 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 2 复习提纲 Ch 1概述信息的基本概念信息与消息 信号等概念的区别信息传输系统的一般模型信息论研究的对象 目的和内容香农对信息论的主要贡献 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 3 Ch2 信源与信息熵 自信息量 平均信息量 信息熵 互信息量 平均互信息量离散信源的描述方法与基本分类离散信源熵的基本性质联合熵 条件熵以及平均互信息之间的关系信息处理定理m阶马尔科夫信源及其极限熵的计算连续信源熵 相对熵 和最大连续熵定理信源冗余度 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 4 Ch3 信道和信道容量 信道的分类各种信道的数学模型信道容量的概念特殊信道 如对称 准对称DMC 信道容量的计算香农公式及其应用 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 5 Ch4 信息率失真函数 失真函数 平均失真度 保真度准则 试验信道 信息率失真函数等基本概念信息率失真函数R D Vs 信道容量C 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 6 Ch5 信源编码 信源编码的目的和基本思想编码的基本概念 非 奇异码 惟一可译码 即时码 平均码长 编码效率等 惟一可译码存在的充要条件 即Kraft不等式 最佳编码的概念Huffman编码方法 Fano编码方法 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 7 Ch6 信道编码 1 信道编码的目的 基本思想及任务差错控制系统的三种方式及基本原理错误概率费诺不等式几种译码规则 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 8 Ch6 信道编码 2 线性分组码的基本概念及编译码方法线性分组码 汉明码距 完备码线性分组码的特点最小码距与检 纠错能力之间的关系许用码组 禁用码组系统码 典型的 生成矩阵 监督矩阵错误图样 伴随式 标准阵列等汉明码的参数及其特点 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 9 Ch6 信道编码 3 循环码的基本概念及编译码方法循环码 码多项式 生成多项式 监督多项式循环封闭性系统循环码的编码电路 工作过程等循环冗余校验CRC的检错原理 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 10 考试题型 判断题 并说明理由 10个 2分 个 20分简答题6个 5分 个 30分综合计算题3个 共50分 判断题 并说明理由 10个 2分 个 20分名词解释6个 3分 个 18分简答题6个 4分 个 24分综合计算题3个 共38分 A卷 B卷 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 11 名词解释主要涉及到 消息信号香农信息自信息量平均互信息信源编码信道编码信道疑义度信道含糊度离散无记忆信源平稳信源无 有记忆信道 信道容量保真度准则信息率失真函数平均码长编码效率最佳码完备码极大似然译码汉明距离错误图样线性分组码许用 禁用码组 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 12 考试题型 综合计算题主要是以下几个方面的内容 马尔科夫信源熵的计算各种熵 平均互信息的相关计算信源编码及其相关计算信道编码 线性分组码 循环码 设计 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 13 考试注意事项 判断题需要说明理由 尤其是 错误 的 最好把正确的内容写出来 名词解释 可以用自己的话把关键部分表述出来简答题 抓要点 不用太啰嗦综合计算题按照题目设计一步一步完成 中间可能需要用到计算器 科学计算的那种 主要是对数运算 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 14 习题讲解 解 1 由题意可知 此消息中共有14个 0 13个 1 12个 2 6个 3 则此消息的自信息量是 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 15 例一 2 此消息中共有45个符号 携带了87 81比特信息 则此消息中平均每个符号携带的信息量为特别说明 此题中信源熵为两者的值并不完全相等 Why 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 16 扩展此例题 假设该无记忆信源进行N次扩展 N 4 求扩展信源发出序列 0132 时的联合自信息量 求5个并列信源同时发出符号的联合熵 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 17 进一步拓展 符号之间有相关性 给定符号之间的转移关系 马氏信源 利用计算联合熵的方法或者利用马尔科夫信源的计算方法 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 18 例二 1 由状态转移图可知 这个三状态都是正规常返态 所以此马氏链是时齐的 状态有限和不可约闭集 其具有各态历经性 平稳后状态的极限分布存在 由图可知状态一步转移矩阵为 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 19 例二 有可得 2 一阶马尔科夫信源的熵为 3 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 20 例二 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 21 例三 每帧电视图像可以认为是由3 105个像素组成 所有像素均是独立变化 且每一像素又取128个不同的亮度电平 并设亮度电平等概率出现 1 问每帧图像含有多少信息量 2 若现有广播员在约10000个汉字的字汇中选1000个字来口述此电视图像 试问广播员描述此图像所广播的信息量是多少 假设汉字字汇是等概率分布 并彼此无依赖 3 若要恰当地描述此图像 广播员在口述中至少需用多少汉字 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 22 例三 1 每帧图像含有的信息量为 2 3 要恰当地描述此图像 广播员在口述中所需汉字 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 23 例四 P186 4 3 题目略解 连续随机变量X的熵为 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 24 例四 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 25 例四 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 26 例五 P134 3 2 题目略解 1 接收到第一个数字y1 0的概率为P y1 0 0 5p 0 5 1 p 0 5P y1 0 M1 p 8接收到第一个数字y1 0与M1之间的互信息 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 27 例五 2 接收到第二个数字也是0时 得到多少关于M1的附加互信息 P M100 p2 8因为信道无记忆P 00 M1 P 0 0 P 0 0 p2 3 同理增加了1 logP比特的信息 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 28 4 接收到第四个数字还是0 则P M10000 p4 8P 0000 M1 P 0 0 P 0 0 P 0 0 P 0 0 p4P 0000 p4 1 p 4 6 1 p 2p2 8 1 16I M1 0000 3 4logP log p4 1 p 4 6 1 p 2p2 I M1 0000 I M1 000 logP log p4 1 p 4 6 1 p 2p2 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 29 5 I M10000 3 4logP log p4 1 p 4 6 1 p 2p2 6 当P 1 上述过程变为确定事件 即发送零 必然收到0 I M10 1 I M100 2 I M1000 3 I M10000 3 当P 0 5 互信息为0 信道为最不确定信道 全损信道 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 30 例六 P188 4 18 题目略 证明 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 31 例六 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 32 例六 所以 利用Jason不等式 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 33 接下来要分别证明等号成立的充分必要条件关键是利用信道无记忆条件得到 后略 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 34 例七 P189 4 23 题目略解 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 35 例八 P393 9 1 题目略解 1 k 3 n 6 2 3 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 36 例八 解法二 设码字为他们之间的约束系数为根据许用码字可得 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 37 例九 P394 9 5 题目略 同P362 例9 6 解 1 根据系统码的定义可证明设码字其中为信息位为冗余位设根据有 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 38 例九 2 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 39 例九 续 BSC信道错误传递概率为P 计算按译码表译码引起的错误概率 0 1 0 1 P 1 P 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 40 例十 P395 9 11 题目略答 15 11 汉明循环码 1 只能纠正1位错误 dmin 3 2 若R x 是码多项式 则必定能被g x 整除 即 否则 R x 不是码多项式 所以 该接收多项式不是码多项式 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 41 例十 接 2 伴随式可以认为指示第十位出错 即错误图样多项式为纠错后所译成的码多项式为可验证 3 信息多项式对应的码多项式为 对应的码字序列为 000100010000101 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 42 例十 编码器电路 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 43 需要补充的内容 构造r元的紧致码 r元霍夫曼编码P340 8 4 参见P 308信源S的符号个数q应满足 缩减次数 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 44 回顾 Huffman编码 例1 信源的符号数目很少 a 0 b 1 2020年1月13日 兰州大学信息科学与工程学院电信 通信工程系 45 回顾 扩展的Huffman编码 例2 信源的符号的概率严重不对称 A a b c P a 0 95 P b 0 02 P c 0 03H 0 335bits symbolHuffman编码 a0b11c10K 1 05bits symbo