《编码理论简介》PPT课件.ppt

第2讲 编码理论简介 编码理论的基本问题 编码理论的发展历史 编码理论的内容和目的 编码理论的课后作业 完 编码理论的基本问题 如何提高一般通信系统的有效性和可靠性 如何提高加密通信系统的安全性 编码问题可以分为三类： 信源编码、信道编码、密码编码 一般通信系统模型 通信系统：电报、电话、电视、广播、遥测、遥 控、雷达和导航等 通信系统都可以看作信息传输系统： 信源编码器信道译码器信宿 噪声源 信号信号+干扰 干扰 信道编码 信源编码 信源译码 信道译码 加密通信系统模型 信 源 信源编码 信道编码 信 道 信道译码 信源译码 信 宿 加密编码 加密译码 噪声源 什么是信源编码 信源编码的主要目标是提高通信系统的有效性，它通 过对信源输出的消息进行适当的变换和处理，以达到 提高传输效率的目的 经典信源编码方法主要依据信源本身的固有统计特性 现代编码压缩技术则注重对人类感知特性的利用，使 得编码效率得以极大提高 信源编码要求尽量去掉冗余信息 什么是信道编码 信道编码的主要目标是研究如何提高信息传 送的可靠性，它通过对信源编码进行适当的 变换和处理使其具有自动检错和纠错功能 信道中的干扰使通信质量下降，也就是使信 息传送不可靠。对于模拟信号，表现在收到 的信号的信扰比下降；对于数字信号，表现 在误码率增大 信道编码需要适当增加冗余信息 什么是密码编码 密码编码是通信系统中的另一类编码问题， 它的目的是通过加密或隐藏防止非授权用户 对重要或机密信息的窃取、伪造和篡改，以 保证通信的安全性、真实性和完整性 发送端的明文信息经过编码后成为密文，当 授权者收到后，可用已有的密钥正确地译成 明文； 对于非授权者，因没有密钥而无法取得该信 息，从而保证通信的安全性 编码理论的发展历史 信源编码的发展历史 信道编码的发展历史 密码编码的发展历史 信源编码的发展历史 无失真信源编码的研究 限失真信源编码的研究 现代信源编码方法的研究 无失真信源编码的研究 无失真信源编码适用于离散信源或数字信号， 如文本数据 无失真信源编码不适用于连续信源或模拟信号 ，如语音图像等信号的数字处理 在概率特性已知条件下的无失真信源编码 在概率特性未知条件下的无失真信源编码 已知概率特性的无失真信源编码 1948年，无失真信源编码定理，香农编码 1952年，费诺(Fano)码，霍夫曼码(Huffman) 1956年，麦克米伦(McMillan)证明了惟一可译 码的克拉夫特(Kraft)不等式 1968年，埃利斯(Elias)，香农-费诺码 1976年，里斯桑内(Rissanen)，算术编码 1982年，里斯桑内和兰登（Langdon），算术 编码系统化，省去乘法 无失真信源编码定理 香农第一定理：必然存在一种编码方法，使码 的平均长度可任意接近但不能低于信息熵 克拉夫特(Kraft)不等式 其中r是码元个数，q是码的个数，ni是码长 码元个数的负码长幂之和不超过1 未知概率特性的无失真信源编码 这时对信源进行的编码称为通用编码 20世纪70年代末，以色列学者兰佩尔(A. Lempel)和 奇费(J.Ziv)提出一种语法解析码，习惯上简称LZ码 1977年他们首先提出这种方法，并于1978年作了改 进，分别称为LZ77和LZ78算法 1984年，韦尔奇（T.A.Welch)将LZ78算法修改成一 种实用的算法，后定名为LZW算法。 1990年，贝尔（T.C.Bell）做了一系列变化和改进 ，现在LZ码被广泛应用于文本数据压缩 限失真信源编码的研究 通过引入失真，对连续信源进行编码 限失真信源编码实际上就是最佳量化问题，它的研 究比信道编码和无失真信源编码落后约10年左右 1948年香农在其论文中体现了率失真函数的思想 1959年香农提出率失真函数，限失真信源编码定理 1971年伯格尔信息率失真理论 限失真信源编码就是在保证平均失真小于允许失真D 的条件下，如何实现最佳编码率R(D) 率失真函数R(D)简介 平均互信息量I(U;V)是信源分布P(U)=p(ui)和信道矩 阵P(V|U)=p(vj|ui)的函数，即： 设D为允许失真度，对给定信源分布P(U) ，如果把信 道矩阵P(V|U)限定在允许失真信道集合BD内选取，那 么 I(U;V)所能逼近的最小值就是率失真函数: 限失真信源编码定理 香农第三定理：在信息传输率RR(D) 时，只要 有足够的码长，则必然存在一种编码方法，使 译码平均失真可以任意接近允许失真D。 其中R(D)是率失真函数，也就是最佳编码率 现代信源编码方法的研究 寻找现有压缩编码的快速算法 寻找新颖高效的现代压缩方法，比如： 分形编码、小波编码 神经网络编码，DPCM编码 模型编码（Model Based Coding） 信道编码的发展历史 信道编码理论的研究 信道容量分析的研究 信道编码方法的研究 网络信息理论的研究 信道编码理论的研究 1948年，香农信道编码定理 1952年费诺(R.M.Fano)证明费诺不等式和香农 信道编码逆定理 1957年沃尔夫维兹证明信道编码强逆定理 1961年费诺描述分组码中码率、码长和错误率 的关系，并证明了香农信道编码定理的充要性 1965年格拉格尔(R.G.Gallager)发展并简洁地 证明了费诺的结论 香农信道编码定理 香农第二定理： 对于一个给定的离散无记忆信 道，如果信道容量为C，只要信息传输率RC时，无论码长是多少，总也找不 到一种编码方法，使译码错误率PE任意小 信道容量分析的研究 1948年香农分析了白色高斯信道容量问题 1964年霍尔辛格(J.L.Holsinger)发展了有色高斯 噪声信道容量的研究 1969年平斯克尔(M.S.Pinsker)提出了具有反馈 的非白噪声高斯信道容量问题； 1972年阿莫托(S.Arimoto)和布莱哈特(R.Blahut) 分别发展了信道容量的迭代算法 1989年科弗尔(T.M.Cover)简洁地证明了平斯克 尔的结论 白色高斯信道容量 信道容量的Shannon公式: 其中W为信号带宽，S为输入信号功率，N0为 信道加性Gaussian白噪声的单边功率谱密度。 想一想：在W+时，C的极限是多少？ 信道编码方法的研究 1950年汉明(R.W.Hamming)发表论文检错码与 纠错码，讨论如何纠正单个错误 1959年霍昆格姆(Hocgenghem)和1960年博斯 (Bose)及查德胡里(Chaudhuri)分别提出BCH码， 能够纠正多个随机错误 1960年前后卷积码及其译码方法的研究 20世纪60年代是代数编码理论发展的鼎盛时期 20世纪70年代出现了高帕码(Goppa Codes) 20世纪80年代，茨伐斯曼(Tsfasman)等人运用代 数几何的方法进一步推广了高帕码的思想 网络信息理论的研究 1961年香农发表论文双路通信信道 1970年以来，成为信息论的中心课题之一 1971年艾斯惠特(R.Alswede)和1972年廖(H.Liao) 找出了多元接入信道的信道容量区， 1973年沃尔 夫(J.K.Wolf)和斯莱平(D.Slepian)将它推广到具有 公共信息的多元接入信道中 1972年科弗尔(T.M.Cover)提出广播信道的研究， 后来学多学者分别研究了广播信道的容量区问题 1983年科弗尔和艾斯惠特分别发表论文讨论相关 信源在多元接入信道的传输问题 密码编码的发展历史 1949年香农发表论文保密通信的信息理论，首先 用信息论的观点对信息保密问题进行了全面的讨论 1976年，迪弗(Diffe)和海尔曼(Hellman)发表密码学 的新方向一文，提出了公开密钥密码体制后，保密 通信问题才得到广泛研究 1978年，Berlekamp、McEliece和Tilborg等证明了纠 错码理论中一般线性码的译码问题是难解的，同年 McEliece利用纠错码构造了第一个公钥密码体制 编码理论研究的内容和目的 信息论是以信息作为主要研究对象，以信息的 运动规律和基本原理作为主要内容 编码理论则是在信息论的基础上研究各种编码 方法，以便在实践中扩展人的信息功能 研究信源编码方法，实现信息传输的有效性 研究信道编码方法，实现信息传输的可靠性 研究密码编码方法，实现信息传输的安全性 信息传输的有效性 用尽可能短的时间和尽可能少的设备来传送 来传送一定数量的信息 最大限度地压缩每个信源符号的平均比特数 或信源的码率 信源编码是实现有效性的途径，其理论基础 是无失真信源编码定理（香农第一定理、无 噪信道编码定理）和限失真信源编码定理(香 农第三定理) 信息传输的可靠性 使信源发出的消息经过信道传输以后，尽可能 准确地、不失真地再现在接收端 信道编码是实现可靠性的途径，其理论基础是 香农信道编码定理（香农第二定理，有噪信道 编码定理） 信息传输的安全性 安全性包括保密性和认证性 保密性就是隐藏和保护通信系统中传送的信息 ，使它只能被授权接收者获取，而不能被未授 权者接收或理解 认证性就是接收者能正确判断所接收的消息的 正确性和完整性，而不是伪造的或篡改的 编码理论的课后作业 教材p.9: 1-1,1-3 设x1, x2, y1, y2是非负实数，且x1 x2, y1 y2，试证明 x1y2+x2y1 x1y1 +x2y2 设x1, x2是任意正实数，p1, p2是任意非负实数，且 p1+ p2=1，试证明 课堂练习1 设x1, x2, , xn是任意一组正实数，p1, p2, , pn是任 意一组和为1的非负实数，试问下面的不等式哪一 个正确，请证明pi=1/n的情况： 证明 课堂练习1的证明 不妨设pi=mi/N，m1+m2+mn=N，则： (x1m1x2m2 xnmn)1/N(m1x1+m2x2+ +mnxn)/N (x1p1x2p2 xnpn) p1x1+p2x2+ +pnxn 因任意实数可以用有理数逼近，故结论成立 课堂练习2 设x1, x2, , xn和y1, y2, , yn是任意两组固定的 非负实数，z1, z2, , zn是y1, y2, , yn的任意一 个排列，如果n1，试问下式： x1z1+x2z2+xnzn 在何时最大、何时最小？请证明