编码理论简介

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