信息论与编码ppt.ppt

信息论与编码 主讲 苗立刚基础楼319 计算机与通信工程学院2016年3月 课程目标与安排 它是信息处理方向的一门重要的专业基础课 是后续课程的基础 如通讯原理 数字图像处理 语音信号处理等 介绍信息科学的基础理论和基本方法 课程将基于一个通讯系统的抽象数学模型进行展开 课程分为基础理论和编码理论两部分组成 本课程以概率论为基础 数学推导较多 学习时主要把注意力集中到概念的理解上 不过分追求数学细节的推导 注意基本概念的理解 不断加深概念的把握 学习时注意理解各个概念的 用处 结合其他课程理解它的意义 而不要把它当作数学课来学习 课程特点 学时 32考试方式 开卷考试成绩 平时成绩 20 考试成绩 80 课程目标与安排 第一章绪论第二章信源熵第三章信道容量第四章信息率失真函数第五章信源编码第六章信道编码第七章密码体制的安全性测度 课程内容安排 课程目标与安排 课程目标与安排 参考书 曲炜 朱诗兵 信息论基础及应用 清华大学出版社 2005信息论与编码 陈运 周亮 陈新 电子工业出版社 2007傅祖芸 信息论与编码 电子工业出版社 2004周荫清 信息论基础 第3版 北京航空航天大学出版社 2006 有关的课程 高等数学 概率论 线性代数 第一章绪论 信息论基础 主讲 苗立刚基础楼318 计算机与通信工程学院2014年3月 第一章绪论 信息的有关概念通讯系统模型信息论的形成和发展历史 本章主要讨论的问题 信息的有关概念 信息 是信息论中最基本 最重要的概念 它是一个既抽象又复杂的概念 目前还没有一个统一的定义 百余种 信息 不同于消息在现代信息论形成之前 信息一直被看作是通信中消息的同义词 没有严格的数学含义 所谓消息 是用文字 符号 数据 语言 图片 图像等形式 把客观事物运动和主观思维活动的状态表达出来 消息是信息的载体 消息是表现形式 信息是实质 信息 不同于情报情报往往是军事学 文献学方面的习惯用词 它的含义比 信息 窄的多 一般只限于特殊的领域 是一类特殊的信息 情报 是人们对于某个特定对象所见 所闻 所理解产生的知识 信息 不同于知识知识是人们根据某种目的 从自然界收集得来的数据中整理 概括 提取得到的有价值的信息 是一种高层次的信息 知识是信息 但不等于信息的全体 信息 不同于信号把消息变换成适合信道传输的物理量 就是信号 信号是承载消息的物理量 信息的有关概念 信息的有关概念 信息的几种定义以信源为主的信息定义 以信道为主的信息定义和以信宿为主的信息定义 以信源为主的信息定义有 1 信息是事物之间的差异 Longo 1975 2 信息是有序性的度量 Wiener 1948 以信道为主的信息定义有 1 信息是通信传输的内容 Wiener 1950 2 信息是人与外界相互作用的过程中所交换的内容的名称 Wiener 1948 以信宿为主的信息定义有 1 信息是用来消除随机不定性的东西 Shannon 1948 2 信息是使概率分布发生变动的东西 Tribesetal 1971 仙农从研究通信系统传输的实质出发 对信息做出了科学的定义 仙农注意到 收信者在收到消息之前是不知道消息的具体内容的 通信系统消息的传输对收信者来说 是一个从不知到知的过程 或者从知之甚少到知之甚多的过程 或是从不确定到部分确定或全部确定的过程 因此 对于收信者来说 通信过程是消除事物状态的不确定性的过程 不确定性的消除 就获得了信息 原先的不确定性消除的越多 获得的信息就越多 信息 是事物运动状态或存在方式的不确定性的描述 这就是仙农关于信息的定义 信息的有关概念 信息的度量 信息的度量 信息量 和不确定性消除的程度有关 消除了多少不确定性 就获得了多少信息量 不确定性就是随机性 可以用概率论和随机过程来测度不确定性的大小 出现概率小的事件 其不确定性大 反之 不确定性小 由以上两点可知 概率小 信息量大 即信息量是概率的单调递减函数 此外 信息量应该具有可加性 信息的度量 由于信息量与概率成反比 并且具有可加性 可以证明 信息量的计算式为其中pk是事件xk发生的概率 这也是仙农关于 自 信息量的度量 概率信息 单位为bit 哈特莱早在20世纪20年代就提出用对数作为信息量的测度 哈特莱认为 消息和信息不同 多种多样 千姿百态的消息是信息的载体 消息究竟包含了多少信息 应该用消息出现的概率的对数来计算 从而他为信息度量找到了对数这一数学理论 通讯系统模型 信源 编码器 信道 译码器 干扰源 通信系统基本模型 消息 信号 消息 信宿 噪声 信源 消息的来源 如文字 语音 图像等编码器 把消息变换成信号 如信源编码 纠错编码 调制器信道 传递信号的媒介 如电缆 光纤 无线电波等噪声 信道中的干扰 如加性干扰 乘性干扰译码器 把信道输出的信号反变换 解调器 纠错译码器 信源译码器信宿 信息的接受端 接收消息的人或物 通讯系统模型 信源 消息的来源编码器 把消息变换成信号信道 传递信号的媒介译码器 把信道输出的信号反变换信宿 信息的接受端噪声 信道中的干扰 信源编码器 把信源发出的消息变换成由二进制码元 或多进制码元 组成的代码组以提高通信系统传输消息的效率 信源编码可分为无失真信源编码和限失真信源编码 目的 提高信息传输的有效性信道编码器 在信源编码器输出的代码组上有目的地增加一些监督码元 使之具有检错或纠错的能力 目的 提高信息传输的可靠性密码学 研究如何隐蔽消息中的信息内容 使它在传输过程中不被窃听 提高通信系统的安全性 目的 提高信息的安全性 编码问题可分解为三类 信源编码 信道编码和密码 在实际问题中 上述三类编码应统一考虑来提高通信系统的性能 这些编码的目标往往是相互矛盾的 电报常用的莫尔斯码就是按信息论的基本编码原则设计出来的 在一些商品上面有一张由粗细条纹组成的标签 从这张标签可以得知该商品的生产厂家 生产日期和价格等信息 这些标签是利用条形码设计出来的 非常方便 非常有用 应用越来越普遍 计算机的运算速度很高 要保证它几乎不出差错 相当于要求有100年的时间内不得有一秒钟的误差 这就需要利用纠错码来自动地及时地纠正所发生的错误 每出版一本书 都给定一个国际标准书号 ISBN 大大方便图书的销售 编目和收藏工作 编码的应用的几个例子 通讯系统模型 信息论的形成和发展 信息论是在长期通信工程的实践中 由通信技术与概率论 随机过程和数理统计相结合而逐步发展起来的一门科学 奈魁斯特 在1924年研究影响电报传递速度的因素时 就察觉到信息传输速度和频带宽度有关系 哈特莱 Hartley 在1928年用概率的观点来分析信息传输问题 仙农 ClaudeE Shannon 1948年发表 通信的数学理论 AMathematicalTheoryofCommunication 为创立信息论作出了决定性的贡献 香农因此成为信息论的奠基人 维纳 N Wiener 等 为信息论的进一步发展和拓展作了大量工作 主要在通信的统计理论与滤波器理论方面 第二章信源熵 信息论基础 主讲 苗立刚基础楼318 计算机与通信工程学院2014年3月 第二章信源熵 2 1单符号离散信源2 2多符号离散平稳信源2 3连续信源2 4离散无失真信源编码定理 本章主要讨论的问题 2 1单符号离散信源 单符号离散信源的数学模型 单符号信源 信源每次输出一个符号 用离散随机变量描述多符号信源 信源每次输出多个符号 符号序列 用离散随机矢量描述离散信源 信源符号取值离散 包括单符号和多符号信源连续信源 信源符号取值连续 用随机过程描述 结论 从概率 随机变量 过程 来研究信息信息 对事物状态 存在方式 不确定性的描述 2 1单符号离散信源 单符号离散信源的数学模型 注意 大写字母X Y Z代表随机变量 小写字母代表随机事件 概率复习 2 1单符号离散信源 由于信息量与概率成反比 并且具有可加性 自信息量的定义为 其中p xi 是事件xi发生的概率 这也是仙农关于 自 信息量的度量 概率信息 计算信息量主要要注意有关事件发生概率的计算 性质 非负 单调递减 当p xi 0时 I xi 不可能事件 当p xi 1时 I xi 0 确定事件自信息量I xi 的含义当事件xi发生以前 表示事件xi发生的不确定性 当事件xi发生以后 表示事件xi所提供的信息量 自信息量 单个随机事件 例1 从26个英文字母中 随即选取一个字母 则该事件的自信息量为I log2 1 26 4 7比特例2 设m比特的二进制数中的每一个是等概率出现的 这样的数共有2m个 则任何一个数出现的自信息为 I log2 1 2m m比特 符号 自信息量的单位自信息量的单位取决于对数的底 底为2 单位为 比特 bit 底为e 单位为 奈特 nat 底为10 单位为 哈特 hat 1nat 1 44bit 1hat 3 32bit 2 1单符号离散信源 例3 设天气预报有两种消息 晴天和雨天 出现的概率分别为1 4和3 4 我们分别用来表示晴天 以来表示雨天 则我们的信源模型如下 2 1单符号离散信源 联合自信息量 两个随机事件 二维联合集XY上的元素 xiyj 的联合自信息量定义为 含义 X xi Y yj同时发生时 带来的信息量 特例 若X Y独立 则I xiyj I xi I yj 2 1单符号离散信源 条件自信息量 两个随机事件 二维联合集XY中 对事件xi和yj 事件xi在事件yj给定的条件下的条件信息量定义为 联合自信息量和条件自信息量也满足非负和单调递减性 关系当X和Y独立时 2 1单符号离散信源 互信息量 两个随机事件 2 1单符号离散信源 信源发出消息的概率称为先验概率 信宿收到后推测信源发出的概率称为后验概率 定义的后验概率与先验概率比值的对数为对的互信息量 用表示 即互信息量等于自信息量减去条件自信息量 第三种表达方式 2 1单符号离散信源 含义 互信息I xi yj 自信息I xi 条件自信息I xi yj 1 I xi 信宿收到yj之前 对信源发xi的不确定度 2 I xi yj 信宿收到yj之后 对信源发xi的不确定度 3 I xi yj 收到yj而得到 关于xi 的互信息 不确定度的减少量 性质 1 对称性 I xi yj I yj xi 2 X与Y独立时 I xi yj 0 3 I xi yj 可为正 负 0 4 I xi yj I xi I xi yj I yj 2 1单符号离散信源 I xi yj 可为正 负 0的举例设yj代表 闪电 则当xi代表 打雷 时 I xi yj 0 I xi yj I xi 0当xi代表 下雨 时 I xi yj I xi I xi yj 0当xi代表 雾天 时 I xi yj I xi I xi yj 0当xi代表 飞机正点起飞 时 I xi yj I xi I xi yj 0 2 1单符号离散信源 条件互信息量 三个随机事件 联合集XYZ中 给定条件下 与之间的互信息量 其定义式 互信息量 2 1单符号离散信源 平均自信息量 信源熵 随机变量 单位 bit 信源 符号 这个平均自信息量的表达式和统计物理学中热熵的表达式很相似 在统计物理学中 热熵是一个物理系统杂乱性 无序性 的度量 这在概念上也有相似之处 因而就借用 熵 这个词把平均自信息量H X 称为 信源熵 通常研究单独一个事件或单独一个符号的信息量是不够的 往往需要研究整个事件集合或符号序列 如信源 的平均的信息量 总体特征 这就需要引入新的概念 定义自信息的数学期望为信源的平均信息量 2 1单符号离散信源 例 天气预报 有两个信源 则 说明第二个信源的平均不确定性更大一些 信息熵具有以下三种物理含义 1 表示信源输出前 信源的平均不确定性2 表示信源输出后 每个符号所携带的平均信息量3 反映了变量X的随机性 2 1单符号离散信源 例 设某信源输出四个符号 其符号集合的概率分布为 则其熵为 2 1单符号离散信源 例 电视屏上约有500 600 3 105个格点 按每点有10个不同的灰度等级考虑 则共能组成n 103x105个不同的画面 按等概率1 103x105计算 平均每个画面可提供的信息量为 3 105 3 32比特 画面 例 有一篇千字文章 假定每字可从万字表中任选 则共有不同的千字文N 100001000 104000篇 仍按等概率1 100001000计算 平均每篇千字文可提供的信息量为H X log2N 4 103 3 32 1 3 104比特 千字文 一个电视画面 平均提供的信息量远远超过 一篇千字文 提供的信息量 2 1单符号离散信源 熵函数的数学特性 熵函数可以表示为 二元熵 性质1 非负性 H X 0由于0 pi 1 所以logpi 0 logpi 0 则总有H X 0 2 1单符号离散信源 性质2 对称性 根据加法交换律可以证明 当变量交换顺序时熵函数的值不变 信源的熵只与概率空间的总体结构有关 而与个概率分量对应的状态顺序无关 性质3 扩展性 这说明信源空间中增加某些概率很小的符号 虽然当发出这些符号时 提供很大的信息量 但由于其概率接近于0 在信源熵中占极小的比重 使信源熵保持不变 2 1单符号离散信源 性质4 可加性 性质5 极值性 上式表明 对于具有n个符号的离散信源 只有在n个信源符号等可能出现的情况下 信源熵才能达到最大值 这也表明等概分布的信源的平均不确定性最大 这是一个很重要得结论 称为最大离散熵定理 例 对于一个二元信源H X H 1 2 1 2 log2 1bit H X plog2p 1 p log2 1 p H p 2 1单符号离散信源 性质6 确定性 当信源X的信源空间 X P 中 任一个概率分量等于1 根据完备空间特性 其它概率分量必为0 这时信源为一个确知信源 其熵为0 如果一个信源的输出符号几乎必然为某一状态 那么这个信源没有不确定性 信源输出符号后不提供任何信息量 性质7 上凸性 是概率分布 p1 p2 pq 的严格上凸函数 2 1单符号离散信源 设f X f x1 x2 xn 为一多元函数 若对于任意一个小于1的正数 0 f X1 1 f X2 则称f X 为定义域上的上凸函数 若 不成立 则为严格上凸函数若 则为下凸函数若 则为严格下凸函数 2 1单符号离散信源 H p 函数曲线如图所示 如果二元信源的输出符号是确定的 即p 1或q 1 则该信源不提供任何信息 反之 当二元信源符号0和1以等概率发生时 信源熵达到极大值 等于1比特信息量 2 1单符号离散信源 信源熵是从整个信源的统计特性来考虑的 它是从平均意义上来表征信源的总体信息测度的 对于某特定的信源 概率空间给定 其信源熵是一个特定的值 不同的信源因统计特性不同 其熵也不同 信源熵用以表征信息源的平均不确定性 平均自信息量是消除信源不确定性时所需信息的量度 即收到一个信源符号 全部解除了这个符号的不确定性 或者说获得这样大的信息量后 信源不确定性就被消除了 2 1单符号离散信源 信源熵和平均自信息量两者在数值上相等 但含义不同 某一信源 不管它是否输出符号 只要这些符号具有某些概率特性 就必有信源的熵值 这熵值在总体平均上才有意义 因而是一个确定的值 而另一方面 信息量则只有当信源输出的符号被接收者收到后才有意义 信息量就是给予接收者的信息度量 该值本身可以是随机量 也可以与接收者的情况有关 因此说信源熵是信源的平均不确定性的描述 一般情况下它并不等于平均获得的信息量 只是在无噪情况下 接收者才能正确无误地接收到信源所发出的信息 消除了信源熵H X 值大小的平均不确定性 所以获得的平均信息量就等于信源熵H X 的值 在一般情况下获得的信息量是两熵之差 并不是信源熵本身 2 1单符号离散信源 条件熵 思考 求条件熵时为什么要用联合概率加权 条件熵是在联合符号集合XY上的条件自信息量的数学期望 在已知随机变量X的条件下 随机变量Y的条件熵定义为 2 1单符号离散信源 条件概率 并且 当已知特定事件xi出现时 下一个出现的是yj的不确定性为 对集合Y中所有元素统计平均 其熵为 上述熵值再对集合Y中的元素做统计平均 得条件熵 同理可得 条件熵H X Y 是一个确定值 表示信宿在收到Y后 信源X仍然存在的不确定度 这是信道干扰所造成的 有时称H X Y 为信道疑义度 也称损失熵 如果没有干扰 H X Y 0 一般情括下H X Y 小于H X 说明经过信道传输 总能消除一些信源的不确定性 从而获得一些信息 条件熵H Y X 也是一个确定值 表示信源发出X后 信宿仍然存在的不确定度 这是由于噪声引起的 也称为噪声熵 2 1单符号离散信源 联合熵 共熵 联合离散符号集合XY上的每个元素对的联合自信息量的数学期望 说明 联合熵H XY 表示X和Y同时发生的不确定度 2 1单符号离散信源 加权熵 自学 对香农熵引入主观因素 效用权重系数 重量 定义 设信源X则加权熵Hw X 含义 消息xi的权重wi对I xi 的加权平均性质 略 2 1单符号离散信源 从通信系统角度看熵的意义 H X 表示信源边每个符号的平均信息量 信源熵 H Y 表示信宿边每个符号的平均信息量 信宿熵 H X Y 信道疑义度 含糊度 表示在输出端接收到Y后 发送端X尚存的平均不确定性 这个对X尚存的不确定性是由于信道干扰引起的 H Y X 噪声熵 表示在已知X后 对于输出Y尚存的平均不确定性 H XY 表示整个信息传输系统的平均不确定性 2 1单符号离散信源 各种熵的性质 联合熵H XY 与熵H X 及条件熵H X Y 之间存在下列关系 H XY H X H Y X H XY H Y H X Y 联合熵与信息熵的关系 H XY H X H Y 条件熵与信息熵的关系 H Y X H Y H X Y H X H XY H X H Y I X Y 2 1单符号离散信源 证明 2 1单符号离散信源 互信息量和平均互信息量 互信息量表示先验的不确定性减去尚存的不确定性 这就是收信者获得的信息量 互信息量可能为正数 负数 0 对于无干扰信道 I xi yj I xi 对于全损信道 I xi yj 0 定义 2 1单符号离散信源 为什么需要定义平均互信息量 互信息量是定量地研究信息流通问题的重要基础 但它只能定量地描述输入随机变量发出某个具体消息 输出变量出现某一个具体消息时 流经信道的信息量 此外还是随和变化而变化的随机变量 互信息量不能从整体上作为信道中信息流通的测度 这种测度应该是从整体的角度出发 在平均意义上度量每通过一个符号流经信道的平均信息量 定义互信息量在联合概率空间中的统计平均值为Y对X的平均互信息量 简称平均互信息 也称平均交互信息量或交互熵 2 1单符号离散信源 平均互信息量与其他熵的关系I X Y H X H X Y 因为H X 表示传输前信源的不确定性 而H X Y 表示收到一个符号后 对信源尚存的不确定性 所以二者之差信道传递的信息量 I X Y H Y H Y X I X Y 也表示输出端H Y 的不确定性和已知X的条件下关于Y的不确定性之差 也等于发送前后关于Y的不确定性之差 I X Y H X H Y H X Y I X Y 确定通过信道的信息量的多少 因此称它为信道传输率或传信率 2 1单符号离散信源 平均互信息量的性质非负性 即I X Y 0该性质表明 通过一个信道总能传递一些信息 最差的条件下 输入输出完全独立 不传递任何信息 互信息等于0 但决不会失去已知的信息 极值性 即I X Y H X 一般来说 信道疑义度H X Y 总是大于0 所以互信息总是小于信源的熵 只有当信道是无损信道时 信道疑义度等于0 互信息等于信源的熵 对称性 即I X Y I Y X I Y X 表示从X中提取关于的Y的信息量 实际上I X Y 和I Y X 只是观察者的立足点不同 对信道的输入X和输出Y的总体测度的两种表达形式 2 1单符号离散信源 I X Y 是二元函数 P X 的上凸函数 P Y X 的下凸函数 平均互信息的凸状性 2 1单符号离散信源 定理2 1对于固定的信道 平均互信息I X Y 是信源概率分布P X 的上凸函数 这就是说 对于一定的信道转移概率分布P Y X 总可以找到某一个先验概率分布的信源X 使平均交互信息量I X Y 达到相应的最大值Imax 这时称这个信源为该信道的匹配信源 可以说 不同的信道转移概率对应不同的Imax 2 1单符号离散信源 例 对于二元对称信道 如果信源分布X p 1 p 则 2 1单符号离散信源 2 1单符号离散信源 而 所以 当信道固定时 q为一个固定常数 平均互信息是信源分布的上凸函数 最大只为1 H q 图示曲线表明 对于固定信道 输入符号X的概率分布不同时 在接收端平均每个符号所获得的信息量就不同 当输入符号为等概率分布时 平均互信息量为最大值 接收每个符号所获得的信息量最大 信道容量的理论基础 定理2 2对于固定的信源 平均互信息I X Y 信道传递概率分布P Y X 的下凸函数 这就是说 对于一个已知先验概率为p的离散信源 总可以找到某一个转移概率分布的信道q 使平均互信息量达到相应的最小值Imin 2 1单符号离散信源 例 对于二元对称信道 当信源固定后 p为一个固定常数 改变信道特性q可获得不同的平均互信息I X Y 当q 1 2时 I X Y 0 即在信道输出端获得的信息最小 这意味着信源的信息全部损失在信道中 这是一种最差的信道 其噪声最大 信息率失真理论的基础 2 1单符号离散信源 对于无损信道 有I X Y H X H Y H XY H X Y H Y X 0对于全损信道 有I X Y 0H X Y H X H Y X H Y 2 1单符号离散信源 数据处理定理 自学 I X Z I Y Z I X Z I X Y 意义 信息不增原理 每经一次处理 可能丢失一部分信息 2 1单符号离散信源 各类熵与集合图的类比 2 1单符号离散信源 信道中熵的信息流图 H Y X 噪声熵 H X Y 信道疑义度 它们都是由于噪声干扰的存在而存在的 信道中存在噪声干扰 是减低信道传信能力的基本原因 2 1单符号离散信源 各种熵之间的关系 例 2 1单符号离散信源 作业 2 4 P68 2 6 P68 2 7 P68 2 10 P68 2 2多符号离散平稳信源 离散无记忆信源 发出的各个符号是相互独立的 发出的符号序列中的各个符号之间没有统计关联性 各个符号的出现概率是它自身的先验概率 离散有记忆信源 所发出的各个符号的概率是有关联的 发出单个符号的信源 是指信源每次只发出一个符号代表一个消息 发出符号序列的信源 是指信源每次发出一组含二个以上符号的符号序列代表一个消息 发出符号序列的有记忆信源 是指用信源发出的一个符号序列的整体概率 即联合概率 反映有记忆信源的特征 发出符号序列的马尔可夫信源 是指某一个符号出现的概率只与前面一个或有限个符号有关 而不依赖更前面的那些符号 这样的信源可以用信源发出符号序列内各个符号之间的条件概率来反映记忆特征 2 2多符号离散平稳信源 2 2多符号离散平稳信源 离散无记忆信源发出单个符号的无记忆信源 最简单的离散信源 自信息量信源熵 2 2多符号离散平稳信源 离散无记忆信源的扩展信源 实际信源输出的消息往往是时间上或空间上的一系列符号 如电报系统 序列中前后符号间一般是有统计依赖关系的 离散无记忆二进制信源X的二次扩展信源我们先讨论离散无记忆信源 此时 信源序列的前后符号之间是统计独立的 如在二元系统中 我们可以把两个二元数字看成一组 会出现四种可能情况 00 01 10和11 我们可以把这四种情况看成一个新的信源称为二元无记忆信源的二次扩展信源 相应的 如果把N个二元数字看成一组 则新的信源称为二元无记忆信源的N次扩展信源 则该信源的N次扩展信源为 一般情况下 设一个离散无记忆信源为 离散无记忆二进制信源X的三次扩展信源离散无记忆信源X的N次扩展信源 2 2多符号离散平稳信源 根据信息熵的定义 可以证明 对于离散无记忆的扩展信源 N次扩展信源的熵 2 2多符号离散平稳信源 注意 1 单位 bit sign 但含义不同 2 N次扩展信源的熵等于各符号熵之和 例 离散无记忆信源的N次扩展信源离散无记忆信源为 X a1 a2 a3 P X 1 4 1 2 1 4 2次扩展信源为 A1 A9 信源的9个符号为 其概率关系为 2 2多符号离散平稳信源 计算可知 2 2多符号离散平稳信源 2 2多符号离散平稳信源 离散平稳信源 一般来说 信源的前后消息之间有前后依赖关系 可以用随机矢量描述 信源在某一时刻发出什么样的值取决于两方面1 这一时刻该变量的概率分布2 这一时刻以前发出的消息如一个人讲话我们现在讨论平稳的随机序列 所谓平稳是指序列的统计性质与时间的推移无关 俩个任意时刻信源发出符号的概率分布完全相同 信源所发符号序列的概率分布与时间的起点无关 这种信源我们称之为离散序列平稳信源 2 2多符号离散平稳信源 2 2多符号离散平稳信源 离散平稳信源的熵 最简单的平稳信源 二维平稳信源 信源发出序列中只有前后两个符号间有依赖关系 我们可以对其二维扩展信源进行分析 信源的概率空间 假定X X1X2 则可得到一个新的信源 2 2多符号离散平稳信源 根据信息熵的定义 可得 1 联合熵 可以表征信源输出长度为2的符号的平均不确定性 或所含有的信息量 因此可以用作为二维平稳信源的信息熵的近似值 2 条件熵 则 2 2多符号离散平稳信源 另外还可以得到 只有信源统计独立时等号成立 结论 二维离散平稳有记忆信源的熵小于等于二维平稳无记忆信源的熵 可以证明 例 设某二维离散信源的原始信源的信源空间X x1 x2 x3 P X 1 4 1 4 1 2 一维条件概率为 p x1 x1 1 2 p x2 x1 1 2 p x3 x1 0 p x1 x2 1 8 p x2 x2 3 4 p x3 x2 1 8 p x1 x3 0 p x2 x3 1 4 p x3 x3 3 4 原始信源的熵为 H X 1 5bit 符号条件熵 H X2 X1 1 4bit 符号可见 H X2 X1 H X 二维信源的熵 H X1X2 H X1 H X2 X1 2 9bit 消息每个信源符号提供的平均信息量为 H2 X1X2 H X1X2 2 1 45bit 符号 2 2多符号离散平稳信源 2 2多符号离散平稳信源 对于离散平稳信源 当时 具有以下性质 N给定时 平均符号熵条件熵 平均符号熵随N增加是非递增的 条件较多的熵必小于或等于条件较少的熵 而条件熵必小于等于无条件熵 对于二维离散平稳信源 条件熵等于极限熵 因此条件熵就是二维离散平稳信源的真实熵 对于一般信源 求出极限熵是很困难的 然而 一般来说 取N不大时就可以得到与极限熵非常接近的条件熵和平均符号熵 因此可以用条件熵和平均符号熵来近似极限熵 2 2多符号离散平稳信源 课堂练习 分别写出I xi I xiyj I xi yj I xi yj H X H Y H XY H X Y H Y X I X Y 的表达式 并说明其含义 2 2多符号离散平稳信源 2 2多符号离散平稳信源 马尔可夫信源 在很多信源的输出序列中 符号之间的依赖关系是有限的 任何时刻信源符号发生的概率只与前边已经发出的若干个符号有关 而与更前面的符号无关 为了描述这类信源除了信源符号集外还要引入状态集 这时 信源输出消息符号还与信源所处的状态有关 若一个信源满足下面两个条件 则称为马尔可夫信源 1 某一时刻信源输出的符号的概率只与当前所处的状态有关 而与以前的状态无关 2 信源的当前状态由当前输出符号和前一时刻信源状态唯一确定 2 2多符号离散平稳信源 当信源在 m 1 时刻发出符号时 我们可把sj看成另一种状态 m时刻的状态 m 1时刻的状态 所谓 状态 指与当前输出符号有关的前m个随机变量序列 X1X2 Xm 的某一具体消息 用si表示 把这个具体消息看作是某个状态 2 2多符号离散平稳信源 某一时刻信源输出的符号的概率只与当前所处的状态有关 而与以前的状态无关 或者说只与此前已输出的若干个符号有关 即 把此前已输出的符号视为状态 信源的当前状态由当前输出符号和前一时刻信源状态唯一确定 该条件表明 若信源处于某一状态 当它发出一个符号后 所处的状态就变了 一定转移到另一状态 状态的转移依赖于发出的信源符号 因此任何时刻信源处在什么状态完全由前一时刻的状态和当前发出的符号决定 将信源输出符号的不确定性问题变换为讨论信源状态转换问题 状态之间的一步转移概率为 p sj si 2 2多符号离散平稳信源 由上例可知 m阶马尔可夫信源符号集共有n个符号 则信源共有个不同状态 信源在某一时刻时 必然处于某一种状态 等到下一个符号输出时 转移到另外一个状态 从而得到马尔可夫信源的状态空间 其状态转移图如下页 在状态转换图中 把信源的每一种状态用圆圈表示 用有向箭头表示信源发出某一符号后由一种状态到另一状态的转移 例 设有一二进制一阶马尔可夫信源 信源符号集为 1 0 条件概率定为 P 0 0 0 25P 0 1 0 50P 1 0 0 75P 1 1 0 50由于信源符号数q 2 因此二进制一阶信源仅有两个状态 S0 0 S1 1 由条件概率求得信源的状态转移概率为 P S1 S1 0 25 P S1 S2 0 50 P S2 S1 0 75 P S2 S2 0 50 2 2多符号离散平稳信源 例 设信源符号X x1 x2 x3 信源所处的状态S e1 e2 e3 e4 e5 各状态之间的转移情况由下图给出 2 2多符号离散平稳信源 将图中信源在ei状态下发符号xk的条件概率p xk ei 用矩阵表示 可以看出 2 2多符号离散平稳信源 M阶马尔可夫信源的平均信息量 即信源的极限熵 马尔可夫链的平稳分布若齐次马尔可夫链对一切i j存在不依赖于i的极限 则称其具有遍历性 p si 称为平稳分布 2 2多符号离散平稳信源 且满足 2 2多符号离散平稳信源 2 2多符号离散平稳信源 对于由二元信源X 0 1 得到的状态空间 s1 s2 s3 s4 容易验证求出稳定状态下的p sj 称为状态极限概率 将一步转移概率代入上式得p s1 0 8p s1 0 5p s3 p s2 0 2p s1 0 5p s3 p s3 0 5p s2 0 2p s4 p s4 0 5p s2 0 8p s4 2 2多符号离散平稳信源 解方程组得p s1 p s4 5 14p s2 p s3 2 14计算极限熵 2 2多符号离散平稳信源 信源的相关性和剩余度 平均符号熵随N增加是非递增的 也就是说信源输出符号间的相关程度越长 信源的实际熵越小 趋近于极限熵 若相关程度减小 信源实际熵增大 当信源输出符号间彼此不存在依存关系 且为等概率分布时 信源实际熵趋于最大熵H0 为了衡量信源的相关程度 引入信源剩余度 冗余度 的概念 冗余度 多余度 剩余度 表示给定信源在实际发出消息时所包含的多余信息 冗余度来自两个方面 一是信源符号间的相关性 由于信源输出符号间的依赖关系使得信源熵减小 这就是信源的相关性 相关程度越大 信源的实际熵越小 趋于极限熵H X 反之相关程度减小 信源实际熵就增大 另一个方面是信源符号分布的不均匀性 当等概率分布时信源熵最大 而实际应用中大多是不均匀分布 使得实际熵减小 当信源输出符号间彼此不存在依赖关系且为等概率分布时 信源实际熵趋于最大H0 X 相对熵率 H H0冗余度R 1 2 2多符号离散平稳信源 自然语言的熵 1 对于英文字母 2 对于中文 我们可以压缩剩余度来压缩信源 提高通信的可靠性 2 2多符号离散平稳信源 正是因为原始的信息都有冗余 才有可能对信息进行压缩 以尽量减少冗余 提高每个符号携带的信息量 但另一方面 冗余信息可以提高信息的抗干扰能力 如果信息的某部分在传输中被损坏 则通过冗余有可能将其恢复 冗余小 有效 冗余大 可靠 中国 中华人民共和国从提高信息传输效率的角度出发 总是希望减少剩余度 压缩 这是信源编码的作用 从提高信息抗干扰能力来看 总是希望增加或保留剩余度 这是信道编码的作用 2 2多符号离散平稳信源 作业 2 13 P69 2 16 P69 2 17 P69 2 2多符号离散平稳信源 2 3连续信源 连续信源的熵 连续信源是指输出在时间和取值上都连续的信源 属随机过程 x t 以概率密度描述平稳过程 统计特性与时间起点无关遍历过程 集平均 时间平均的平稳过程 2 3连续信源 熵计算两种方法 法一 连续消息 离散消息再用离散信源方法计算 法二 连续消息抽样 时间离散的连续消息分析时先量化 再令 0 分类 单变量信源 无记忆信源 与单符号离散源相似 随机过程中取一个时间t1多变量信源 有记忆信源 与多符号离散源相似 随机过程中取多个时间ti 说明 对单变量信源 可研究 数学期望 方差对两变量信源 可研究 自相关函数 2 3连续信源 2 3连续信源 一 单变量连续信源数学模型R 连续变量X的取值范围二 连续信源的熵由法二得 图2 3 1 上式中第2项为 即连续信源熵值无穷大 取值可能性无限多 舍第2项得定义 相对熵 2 3连续信源 二 连续信源的熵 两个连续变量 联合熵条件熵 2 3连续信源 2 3 2几种特殊连续信源的熵和最大熵定理 一 均匀分布信源 Hc X log2 b a 结论 熵值只与均匀分布间隔 b a 有关 若b a 1 则Hc X 为负 2 3连续信源 二 高斯分布信源 结论 熵值只与方差有关 与m无关 三 指数分布信源 结论 熵值只与数学期望m有关 2 3连续信源 四 最大熵定理1 限峰值功率的最大熵定理 均匀分布的连续信源具最大熵2 限平均功率的最大熵定理 高斯分布的连续信源具最大熵3 限均值的最大熵定理 指数分布的连续信源具最大熵 结论 连续信源的最大熵因条件而异 离散信源的最大熵出现于等概之时 2 3连续信源 1 连续熵可为负值 与离散熵不同 2 可加性Hc XY Hc X Hc Y X Hc Y Hc X Y Hc X1X2 XN Hc X1 Hc X2 X1 Hc X3 X1X2 Hc XN X1X2 XN 1 2 3连续信源 3 平均互信息的非负性Ic X Y Hc X Hc X Y Ic Y X Hc Y Hc Y X 对称性 Ic X Y Ic Y X 非负性 Ic X Y 0 Ic Y X 0条件熵不大于无条件熵Hc X Y Hc X Hc Y X Hc Y 2 3连续信源 1 信息变差Ip q Hc p x X Hc q x X 2 3 49 Hc p x X 最大熵 对应分布p x Hc q x X 实际熵 对应分布q x 说明 式 2 3 49 与I0 H0 H 相对应且有 实际熵Hc q x X Hc p x X Ip q 最大熵 最大的平均不确定度实际熵 测定q x 后还剩下的不定度于是 获得的信息量Ip q 不确定度的减少量 2 3连续信源 2 熵功率对零均值 平均功率 P 受限的信源 高斯分布p x 具最大值 m 0 P 2 对实际信源 分布为q x 也可写为 结论 冗余度 信息变差取决于限定功率与熵功率之比 2 3连续信源 2 4离散无失真信源编码定理 信源编码 以提高通信有效性为目的的编码 通常通过压缩信源的冗余度来实现 采用的方法是压缩每个信源符号的平均比特数或信源的码率 即同样多的信息用较少的码率传送 使单位时间内传送的平均信息量增加 从而提高通信的有效性 信源编码理论是信息论的一个重要分支 其理论基础是信源编码的两个定理 无失真信源编码定理 是离散信源 数字信号编码的基础 限失真信源编码定理 是连续信源 模拟信号编码的基础 如语音 图像等信号 信源编码的分类 离散信源编码 连续信源编码和相关信源编码三类 离散信源编码 独立信源编码 可做到无失真编码 连续信源编码 独立信源编码 只能做到限失真信源编码 相关信源编码 非独立信源编码 2 4离散无失真信源编码定理 香农信息论三大定理 第一定理 无失真信源编码定理第二定理 信道编码定理 包括离散和连续信道 第三定理 限失真信源编码定理 2 4离散无失真信源编码定理 信源编码信源符号 码符号 以适合信道传输的一种映射 变换 定长编码定理 由L个符号组成的 平均符号熵为H x 的平稳无记忆符号序列X 可用由K个码符号 每个有m种取值 组成的码序列作定长编码 对任意 0 0 有 1 正定理 只要则当L足够大时 译码差错必小于 2 逆定理 当时译码差错必为有限值 且当L足够大时 译码几乎必定出错 2 4离散无失真信源编码定理 说明 1 信息率 编码速率 R K L log2mbit 信源符号log2m 每个码符号的最大熵 bit 码符号 Klog2m 每个码符号序列最大熵 bit 码序列 K L log2m 编码后 平均每个信源符号所能载荷的最大信息量 2 4离散无失真信源编码定理 2 编码效率H X 编码前 平均每个信源符号包含的信息量R 编码后 平均每个信源符号所能传送的最大信息量若在正定理中取等号 R H X 于是 2 4离散无失真信源编码定理 3 正定理指出 当信息率R 单符号熵H X 时可做到几乎无失真译码 条件是L大 只要 译码差错率必小于 信源序列自信息方差 2 4离散无失真信源编码定理 3 逆定理指出 若R比H X 小一个 时 译码差错未必超过 若R比H X 小两个 时 译码差错必定大于 L 时必失真 4 结论 单符号 信源熵H X 实为一个界限当R H X 时 无失真译码当R H X 时 有失真译码 4 逆定理指出 若R比H X 小一个 时 译码差错未必超过 若R比H X 小两个 时 译码差错必定大于 L 时必失真 5 结论 单符号 信源熵H X 实为一个界限当R H X 时 无失真译码当R H X 时 有失真译码 2 4离散无失真信源编码定理 例2 给定信源模型 8种符号和概率算得 H X 2 55bit 信源符号 2 X 1 323 若要求 编码效率 90 由得 0 28 若要求 译码差错率 10 6 则L太大此外 相对熵率不高 2 4离散无失真信源编码定理 第三章信道容量 信息论与编码 主讲 苗立刚基础楼318 计算机与通信工程学院2014年3月 第三章信道容量 3 1单符号离散信道的数学模型 重点 3 2单符号离散信道的信道容量 重点 3 3多符号离散信道的信道容量 重点 3 4网络信息理论 自学 3 5连续信道 自学 3 6信道编码定理 重点 本章主要讨论的问题 3 1单符号离散信道的数学模型 单符号离散信道的数学模型及其分类 信道的数学模型 X 输入事件的集合 概率空间为 XP Y 输出事件的集合 概率空间为 YP 信道的分类 1 根据信道用户的多少 分为 单用户信道 输入 输出均只有一个多用户信道 输入 输出有多个2 根据输入输出信号的特点 分为 离散信道 输入 输出随机变量均离散取值连续信道 输入 输出随机变量均连续取值半离散 连续 信道 一为离散 另一为连续3 根据输入 输出随机变量的个数单符号信道 输入 输出均用随机变量表示多符号信道 输入 输出用随机矢量表示 3 1单符号离散信道的数学模型 4 根据信道上有无噪声 干扰 有噪 扰 信道无噪 扰 信道5 根据信道有无记忆特性无记忆信道 输出仅与当前输入有关 与先前输入无关有记忆信道 输出不仅与当前输入有关 还与先前输入有关 3 1单符号离散信道的数学模型 离散信道的数学模型 信道容量的定义 设离散信道的输入空间为 输出空间为 概率分布为 概率分布为 3 2单符号离散信道的信道容量 并有条件概率条件概率被称为信道的传递概率或转移概率 XY 将所有转移概率以矩阵方式列出 得 其中 该矩阵完全描述了信道在干扰作用下的统计特性 称为信道矩阵 n行m列 3 2单符号离散信道的信道容量 反信道矩阵 m行n列 其中 3 2单符号离散信道的信道容量 3 2单符号离散信道的信道容量 1 联合概率 其中 称为前向概率 描述信道的噪声特性 称为后向概率 有时也把称为先验概率 称为后验概率 2 输出符号的概率 3 后验概率 表明输出端收到任一符号 必定是输入端某一符号输入所致 离散信道中的概率关系 3 2单符号离散信道的信道容量 信道容量的定义 含义 给定信道时 对应各种信源分布 求取的最大平均互信息 给定信道时 理论上能传输的最大信息量 表征信道传送信息的最大能力 信道容量定义为平均互信息的最大值 平均互信息I X Y 是信源分布p x 的上凸函数 是信道传递概率p y x 的下凸函数 对于一个固定的信道 总存在一种信源 使传输每个符号平均获得的信息量I X Y 最大 信道容量C只与信道的统计特性p y x 有关 而与信源的分布p x 无关 它是信道的特征参数 反应的是信道的最大的信息传输能力 信息传输速率Rt 单位时间内平均传输的信息量 信息传输率R 信道中平均每个符号所能传送的信息量 由于平均互信息I X Y 的含义是接收到符号Y后 平均每个符号获得的关于X的信息量 因此信道信息传输率就是平均互信息 最大信息传输速率Ct 单位时间内平均传输的最大信息量 3 2单符号离散信道的信道容量 例 对于二元对称信道 如果信源分布X p 1 p 则 3 2单符号离散信道的信道容量 信道容量为 3 2单符号离散信道的信道容量 无损确定信道 一对一 n m 信道矩阵 单位阵 损失熵H X Y 0噪声熵H Y X 0I X Y H X H X Y H Y H Y X H X H Y 离散无噪信道 输出Y和输入X有确定关系 广义 a1a2a3an b1b2b3bn 3 2单符号离散信道的信道容量 无损信道 一对多 n m 具有扩展性的无噪信道 信道矩阵 每列只有一个非0元素 不全是0 1 信道疑义度 损失熵 H X Y 0噪声熵H Y X 0I X Y H X H X Y H Y H Y X H X H X H Y 思考 p x 应该怎样取值 a1a2a3 b1b2b3b4b5 3 2单符号离散信道的信道容量 确定信道 多对一 n m 具有归并性的无噪信道 信道矩阵 每行只有一个元素 1 其它全是0 损失熵H X Y 0噪声熵H Y X 0I X Y H X H X Y H Y H Y X H Y H X H Y 思考 p x 应该怎样取值 强对称离散信道 均匀信道 3 2单符号离散信道的信道容量 信道特点信道输入 输出均为n元每符号正确传输概率均为其他符号错误传输概率为p n 1 矩阵特点 1 n n阶对称阵 2 每行和为1 每列和为1 3 2单符号离散信道的信道容量 信道容量 可以看出 当输出等概分布时 即H Y log2n时达到信道容量 3 2单符号离散信道的信道容量 那么 在什么样的信源输入情况下 信道输出能等概分布呢 可以证明 输入等概分布时 离散对称信道的输出也为等概分布 结论 对强对称信道 输入等概 输出等概 可达到C 3 2单符号离散信道的信道容量 二进制对称信道 n 2 3 2单符号离散信道的信道容量 行可排列 矩阵每行各元素都来自同一集合QQ q1 q2 qm 排列可不同 列可排列 矩阵每列各元素都来自同一集合PP p1 p2 pn 排列可不同 矩阵可排列 矩阵的行 列皆可排列对称信道