信息论基础.ppt

信息论基础 主讲教师 张瑞娟 绪论第1章随机变量的信息度量第2章随机过程的信息度量和渐近等分性第3章数据压缩和信源编码第4章数据可靠传输和信道编码第5章限失真信源编码和率失真函数第6章连续信源和信道编码理论 绪论 信息论是应用近代概率统计方法研究信息传输 交换 存储和处理的一门学科 也是源于通信实践发展起来的一门新兴应用科学研究信息的基本性质及度量方法 研究信息的获取 传输 存储和处理的一般规律的科学研究可能性和存在性问题 为具体实现提供理论依据 信息论研究的主要内容 广义信息论 包括信息论在自然和社会中的新的应用 如模式识别 机器翻译 自学习自组织系统 心理学 生物学 经济学 社会学等一切与信息问题有关的领域 实用信息论 研究信息传输和处理问题 也就是狭义信息论方法在调制解调 编码译码以及检测理论等领域的应用 狭义信息论 即通信的数学理论 主要研究狭义信息的度量方法 研究各种信源 信道的描述和信源 信道的编码 3 信道信息传输和存储的媒介 4 译码器译码是编码的逆变换 分为信道译码和信源译码 5 信宿消息的接收者 2 编码器将消息变成适合于信道传送的信号的设备 1 信源产生消息的源 第1章随机变量的信息度量 1 1自信息 1 2熵 联合熵 条件熵 1 3相对熵和互信息 1 4信息量的一些基本性质 1 5广义熵习题课 1 1自信息 信息 通信领域指通信的消息 信号处理方面指包括了数字 数据 图像 语音等进行运算和处理所需的条件 内容和结果信源 消息的来源 信源的分类 离散信源和连续信源信源的表示方法 用随机变量X表示一个离散信源 X的可能取值 即信源可能输出的不同符号用集合 表示 自信息 信源发出的某个信号所含的信息量 记为自信息与信号发生概率之间关系 自信息满足的公理 1 2熵 联合熵 条件熵 熵 对整个信源来说 每个信号的平均信息量的多少定义1 2 1离散随机变量X的熵定义为 注意 熵只是概率分布p的函数 与X取什么值并无关系 对数底与熵单位的对应关系 1 3相对熵和互信息 级联处理器示意图 数据处理定理 数据处理过程中只会丢掉一些信息 绝不会创造出新的信息 这就是所谓的信息不增性 一般通信系统 1 4信息量的一些基本性质 1 5广义熵 习题课 第2章随机过程的信息度量和渐近等分性 2 1信源和随机过程的基本概念 2 2随机过程的信息度量 2 3渐近等分性质 2 4渐近等分在数据压缩中的应用 2 5Shannon McMillan Breiman定理 2 1信源和随机过程的基本概念 信源的模型表示成一个在信源字母集中取值的随机序列或随机过程信源分类信源可以按信号取值集合和信号取值时刻的连续性和离散性分类也可以按对应数学模型随机过程的统计特征来分类 信源分类 无记忆信源有记忆信源平稳或遍历信源马氏信源高斯信源 信源分类 随机过程 随机过程数学定义 随机过程分类 离散参数 离散状态的随机过程离散参数 连续状态的随机过程连续参数 离散状态的随机过程连续参数 连续状态的随机过程 严平稳过程 宽平稳过程 2 2随机过程的信息度量 2 3渐近等分性质 2 4信源编码定理 2 5Shannon McMillan Breiman定理 第3章数据压缩和信源编码 3 1等长码 3 2变长编码 3 3哈夫曼码 3 4香农码和费诺玛 信源编码 以提高通信有效性为目的的编码 通常通过压缩信源的冗余度来实现 采用的一般方法是压缩每个信源符号的平均比特数或信源的码率 即同样多的信息用较少的码率传送 使单位时间内传送的平均信息量增加 从而提高通信的有效性 信道编码 是以提高信息传输的可靠性为目的的编码 通常通过增加信源的冗余度来实现 采用的一般方法是增大码率 带宽 与信源编码正好相反 3 1等长码 信源编码理论是信息论的一个重要分支 其理论基础是信源编码的两个定理 无失真信源编码定理 是离散信源 数字信号编码的基础 限失真信源编码定理 是连续信源 模拟信号编码的基础 信源编码的分类 离散信源编码 连续信源编码和相关信源编码三类离散信源编码 独立信源编码 可做到无失真编码 连续信源编码 独立信源编码 只能做到限失真信源编码 相关信源编码 非独立信源编码 信源编码示意图 1 二元码 码符号集X 0 1 如果要将信源通过二元信道传输 必须将信源编成二元码 这也是最常用的一种码 2 等长码 若一组码中所有码字的长度都相同 称为等长码 3 变长码 若一组码中所有码字的长度各不相同 称为变长码 4 非奇异码 若一组码中所有码字都不相同 称为非奇异码 3 2变长编码 5 奇异码 若一组码中有相同的码字 称为奇异码 6 同价码 每个码字占相同的传输时间 8 唯一可译码 若码的任意一串有限长的码符号序列只能被唯一的译成所对应的信源符号序列 则称此码为唯一可译码 9 即时码 无需考虑后续码符号即可从码元符号序列译出码字的唯一码 码 10 码分类 2 即时码的树图构造法 树根 码字的起点 树枝数 码的进制数 结点 码字或码字的一部分 节数 码长 端点 码字 满树 等长码 非满树 变长码 1 0 信道定义 信道在通信系统中作用 研究信道的哪些问题 第4章数据可靠传输和信道编码 4 1离散无记忆信道和信道容量 4 2信道容量的计算 4 3信道编码理论 4 4带反馈的信道模型 4 5联合信源 信道编码定理 4 6线性分组码 一 信道分类 2 根据用户数量分类 分为单用户信道和多用户信道 3 根据信道输入端和输出端关系 分为无反馈信道和反馈信道 4 1数据可靠传输和信道编码 1 根据传输媒介的类型划分 4 根据信道的物理性质 分为固定参数信道和变参数信道5 根据输入输出信号的特点 分为离散信道 连续信道 半离散半连续信道 波形信道6 根据信道输入输出随机变量个数的多少 分为单符号信道和多符号信道 7 根据信道有无干扰 分为有干扰信道和无干扰信道8 根据信道有无记忆性 分为有记忆信道和无记忆信道9 根据信道中受噪声干扰的不同 分为随机差错信道和突发信道 二 离散信道的数学模型 信道通信模型框图 狭义信道模型 信道表示方法 衡量一个信息传递系统的好坏 有两个指标a 数量指标 信息传输率Rb 质量指标 平均错误率Pe信道编码的目的 使译码错误概率Pe在一定限制下使码率R达到最大 三点说明 1 信道容量C是R的上限 2 使得I X Y 达到最大值的输入分布称为最佳输入分布 3 I X Y 与输入概率分布和转移概率两者有关 三 特殊单符号离散信道的信道容量1 无噪信道a 具有一一对应关系的无噪信道 信道容量 b 具有扩展性能的无噪信道 c 具有归并性能的无噪信道 结论 无噪信道的信道容量C只决定于信道的输入符号数n或输出符号数m 与信源无关 2 对称信道 二进对称信道 另一种对称信道定义 推广 强对称信道 准对称信道定义如果转移概率矩阵P是输入对称矩阵 行可排列 而输出不对称 列不可排列 即转移概率矩阵P的每一行都包含同样的元素 而各列的元素可以不同 称该信道为准对称DMC信道 定义4 1 4 弱对称信道 如果转移概率矩阵的每一行都是其他行的置换 而每列的元素之和相等 称为弱对称信道 其信道容量为 4 2信道容量的计算 4 3信道编码理论 4 4带反馈的信道模型 有反馈信道模型 无反馈信道 输出端信号不反馈达到输入端带反馈信道 输出信号通过一定途径反馈到输入端 联合信源 信道通信模型 4 5联合信源 信道编码定理 4 6线性分组码 分组码是前向纠错码 它可以在无需重新发送的情况下检测出有限个错码 并加以纠正 一个具有q个元素的有限数域称为Galois场 记为GF q 任何一个码字可以表示为生成矩阵G的行向量gi的线性组合 第5章限失真信源编码和率失真函数 信道不可能实现对消息的完全无失真传输在现实生活中 不要求获得完全无失真的消息 只要求近似再现原消息允许一定失真 所以对信息率的要求降低信息率失真理论由香农提出 定义了R D 引入失真函数 计算在失真度条件下信息率的极小值 5 1限失真信源编码模型和率失真函数 5 2率失真函数的计算 5 3限失真信源编码定理 根据信道编码定理 我们可以把信道编码 信道和信道译码等价成是一个没有任何干扰的广义信道 这样收信者收到消息后 所产生的失真只是由信源编码带来的 5 1限失真信源编码模型和率失真函数 广义无扰信道 信源 信宿 试验信道 允许失真越大 信息传输率越小 反之 信息率越大信息传输率与信源编码引起的失真有关为了定量描述信息传输率与失真的关系可以略去广义的干扰信道用虚拟信道表示失真信源编码作用 即将信源编码看成是通过一个信道寻找在保真度准则下的最小互信息 现在我们要研究在给定允许失真的条件下 是否可以设计一种信源编码使信息传输率为最低 为此 我们首先讨论失真的测度 设信源变量为 其概率分布为 对于每一对 x y 我们指定一个非负的函数 称为单个符号的失真度 或称失真函数 接收端变量为 其概率分布为 失真度和平均失真度 失真函数用来表征信源发出一个符号 而在接收端再现成符号所引起的误差或失真 d越小表示失真越小 等于0表示没有失真 称为失真矩阵 失真度和平均失真度 失真函数用来表征信源发出一个符号 而在接收端再现成符号所引起的误差或失真 d越小表示失真越小 等于0表示没有失真 可以将所有的失真函数排列成矩阵的形式 1 失真矩阵为 汉明失真 在二元情况下 失真度和平均失真度 常用的失真函数 例1 对称信源n m 定义失真度为 当n m 3时 失真矩阵为 2 平方误差失真 3 绝对失真 失真度和平均失真度 例2 删除信源 对于二元删除信源r 2 s 3 失真度和平均失真度 2 平均失真度 若已知试验信道的传递概率 则平均失真度为 若平均失真度不大于我们所允许的失真D 我们称此为保真度准则 凡满足保真度准则的这些试验信道称为失真度D允许试验信道 把所有D失真允许的试验信道组成一个集合 用符号表示 失真度和平均失真度 例 求汉明失真的平均失真度 在通信中代表信源值与估计值不等的概率 汉明失真也称误差概率失真把保真度准则作为信道转移概率的约束 求信息率R I X Y 的最小值有实用意义 失真度和平均失真度 长度为n的信源符号序列的失真度 失真度和平均失真度 失真度和平均失真度 凡满足保真度准则的这些试验信道称为失真度D允许试验信道 把所有D失真允许的试验信道组成一个集合 用符号表示 信息率失真函数及其性质 一 信息率失真函数当信源和失真函数给定后 我们总希望在满足保真度准则下寻找平均互信息的最小值 也就是在中找一个信道 使平均互信息取极小值 这个最小值就是在的条件下 信源必须传输的最小平均信息量 改变试验信道求平均互信息的最小值 实质上是选择一种编码方式使信息传输率为最小 1 2 3 当给定信源X及失真矩阵 D 时 信源的最小平均失真度为 信息率失真函数及其性质 二 信息率失真函数的性质 1 和 信息率失真函数及其性质 1 R D 的定义域是 信息率失真函数及其性质 信源的最小平均失真度 允许失真度D的最小值为0 即不允许有失真 这要求失真矩阵中每行至少有一个为0 R 0 的最小值为H X 即信息传输率至少为信源的信息熵 满足最小失真度的试验信道是一个无噪无损信道 信息率失真函数及其性质 信息率失真函数及其性质 2 因为D越大 R D 越小 最小为0 当D再大时 R D 也只能为0 此时 发送与接收统计独立 即 失真度函数变为 信息率失真函数及其性