中南大学信息论与编码讲义引言.ppt

信息论与编码 主讲教师 何毅 教材参考及参考书 教材 RobertJ McEliece著李斗等译 信息论与编码理论 电子工业出版社 2004 2参考书 姜丹 信息论与编码 中国科学技术大学出版社 2001 8曹雪虹 信息论与编码 清华大学出版社 2004 引言 本书研究的内容信息论的形成和发展几个概念几个编码信道编码定理 本课程研究的内容 信息论研究的内容非常广泛 本书的研究的内容 分为两个部分 信息论与编码 信息论主要从理论上解决下面的问题 1 什么是信息 如何度量信息 2 在信息传输中 基本的极限条件是什么 3 信息的压缩和恢复的极限条件是什么 4 从环境中抽取信息的极限条件是什么 5 设计什么样的设备才能达到这些极限 6 实际上接近极限的设备是否存在 本课程研究的内容 具体来说 第一部分讲解了香农信息论与编码理论的主要内容 如熵和信息量的基本概念与性质 以及信道 信源编码定理 第二部分介绍了一些香农编码理论的信道和信源编码方法 具体包括线性码 循环码 BCH和RS码 卷积码等信道纠错编码 以及变长信源编码等 信息论的形成和发展 20世纪20年代奈奎斯特 Nyquist H 和哈特莱 Hartley L V R 提出了信息的定义1924年奈奎斯特解释了信号带宽和信息速率之间的关系1928哈特莱最早研究了通信系统传输信息的能力 给出了信息度量方法1936年阿姆斯特朗 Armstrong 提出了增大带宽可以使抗干扰能力加强 信息论的形成和发展 1941 1944年香农对通信和密码进行深人研究 用概率论的方法研究通信系统 揭示了通信系统传递的对象就是信息 并对信息给以科学的定量描述 提出了信息熵的概念 指出通信系统的中心问题是在噪声下如何有效而可靠地传送信息以及实现这一目标的主要方法是编码等 香农因此成为信息论的奠基人 信息论的形成和发展 60年代信道编码技术有较大进展 使它成为信息论的又一重要分支 信源编码的研究落后于信道编码 香农1959年的文章 Codingtheoremsforadiscretesourcewithafidelitycriterion 系统地提出了信息率失真理论 它是数据压缩的数学基础 为各种信源编码的研究奠定了基础 信息论的形成和发展 到70年代 有关信息论的研究 从点与点间的单用户通信推广到多用户系统的研究 到目前为止 多用户信息论研究得不多 还有许多尚待解决的课题 几个概念 信息 消息 信号 数据信源 信道 信息 信息是指各个事物运动的状态及状态变化的方式 人们从来自对周围世界的观察得到的数据中获得信息 信息是抽象的意识或知识 它是看不见 摸不到的 人脑的思维活动产生的一种想法 当它仍储存在脑子中的时候它就是一种信息 消息 消息是指包含有信息的语言 文字和图像等 例如我们每天从广播节目 报纸和电视节目中获得各种新闻及其他消息 消息是具体的 它载荷信息 但它不是物理性的 信号 信号是消息的物理体现 为了在信道上传输消息 就必须把消息加载 调制 到具有某种物理特征的信号上去 信号是信息的载荷子或载体 是物理性的 如电信号 光信号等 信号 按照信息论或控制论的观点 在通信和控制系统中传送的本质内容是信息 系统中实际传输的则是测量的信号 信息包含在信号之中 信号是信息的载体 信号到了接收端 信息论里称为信宿 经过处理变成文字 语声或图像 人们再从中得到有用的信息 数据 载有信息的可观测 可传输 可存储及可处理的信号均称为数据 二进制对称信源 是一个可以发出定义为 0 1 的两种特定的实体 数率为单位时间内R个符号 称这些符号为比特 bits binarydigits 信源随机地发出这些比特 0 1 的数率概率相同 二进制对称信道 简称BSC 是一个单位时间内可以传送1比特数据的实体 但是该信道并不是完全可靠的 存在一个固定的概率p 称为原始误比特率 满足0 p 1 2 使输出比特与输入比特不相同 重复编码 多票判决译码 R 1 3 信源输出 10100信道编码 111000111000000信道输出 101011111001100信道解码 11100用Pe表示误比特率Pe P 2个信道错误 P 3个信道错误 3p2 1 p p3 3p2 2p3 p 重复编码 多票判决译码 R 1 2n 1 对于原始误比特率p 1 2的固定BSC 当n 时 Pe 0 即通过这些重复编码方式 可以使信道达到理想的可靠度 抛硬币方式编码 R 1 只传输信源比特的1 R部分 并让接收者以抛硬币的方式猜测其余的部分 多票判决编码 重复译码 R 3 信源输出 101110101000101信道编码 11101信道输出 10101信道解码 111000111000111Pe 1 4 1 p 3 4p 1 4 p 2 比 抛硬币 方式1 3 p 3小 多票判决编码 重复译码 R 2n 1 4 7 汉明码 R 4 7 编码方式 信源的4个比特为 x0 x1 x2 x3 附加3个比特奇偶校验码x4 x5 x6 x4 x1 x2 x3 mod2 x5 x0 x2 x3 mod2 x6 x0 x1 x3 mod2 举例 信源输出 0110信道编码 0110011 4 7 汉明码 译码分析 按下面方式重写奇偶校验式 x1 x2 x3 x4 0 x0 x2 x3 x5 0 x0 x1 x3 x6 0定义二进制矩阵H为 16个可能的码字x x0 x1 x2 x3 x4 x5 x6 都满足矩阵方程 4 7 汉明码 译码分析 如果传输的是矢量x 则接收的是矢量y x z z z0 z1 z6 称为错误图案 定义矢量s s0 s1 s6 为y的伴随式 syndrome 4 7 汉明码 译码分析 一旦计算出s 就通过方程sT HzT求解z 但只有三个方程却有七个未知量 因此对任一s 总有16个可能的z 例如 接收到y 0111001 则s 101 z的16个候选值为 0100000001001111000110001010000010101110010110110101000001011111001001100011011110101110101001110011011001011111最佳估计是z 0100000 从而对传输字的估计是x y z 0011001 最终估计四个信源比特是 0011 对于任意伴随式s HzT sT总存在重量为0或1的唯一解 若s 0 则sT必为H中的每一列 4 7 汉明码 译码算法 1 计算伴随式sT HyT 2 如果s 0 设置z 0 到第四步 3 寻找H中的唯一与s相同的列 使其对应的位为1 其余为0 4 设置x y z 5 输出x 的前四个分量 x 0 x 1 x 2 x 3 4 7 汉明码 误组率PE P x x Pe i 表示误比特率P x i xi 7 4 汉明码 R 7 4 编码算法 使