《信息论与编码第.ppt》由会员分享，可在线阅读，更多相关《信息论与编码第.ppt（31页珍藏版）》请在三一文库上搜索。
1、,第1章 绪 论,1.1 信息传输系统 1.2 信息编码的发展,1.1 信息传输系统 1.1.1 信息传输的目标 研究通信系统的目的就是要找到信息传输过程的共同规律，以提高信息传输的可靠性、有效性、保密性和认证性，从而达到信息传输系统最优化。所谓可靠性高，就是要使信源发出的消息经过信道传输以后，尽可能准确地、不失真地再现在接收端。所谓有效性高，就是经济效果好，即用尽可能短的时间和尽可能少的设备来传送一定数量的信息。提高可靠性和提高有效性常常会发生矛盾，需要统筹兼顾。例如为了兼顾有效性(考虑经济效果)，有时就不一定要求绝对准确地在接收端再现原来的消息，可以允许有一定的误差或一定的失真，或者说允许
2、近似地再现原来的消息。所谓保密性，就是隐蔽和保护通信系统中传送的消息，使它只能被授权接收者获取，而不能被未授权者接收和理解。所谓认证性，是指接收者能正确判断所接收的消息的正确性，验证消息的完整性，确认消息不是伪造的和被篡改的。有效性、可靠性、保密性、认证性和经济性构成了现代通信系统对信息传输的全面要求，其中前四项正是本书要研究的主要内容。,1.1.2 信息传输系统模型 各种现代数字通信系统如电报、电话、无线电、电视、广播、因特网、遥测、遥控、雷达和导航等，虽然它们的形式和用途各不相同，但本质是相同的，都是信息的传输系统。为了便于研究信息传输和处理的共同规律，将各种通信系统中具有共同特性的部分抽
3、取出来，概括成一个统一的理论模型，如图11所示。通常称它为信息传输系统模型。 图11所示的模型也适用于其他的信息流通系统，如生物有机体的遗传系统，人体、动物的神经网络系统和视觉系统等，甚至人类社会的管理系统都可概括成这个模型。人们通过系统中消息的传输和处理来研究信息传输和处理的共同规律。信息传输或通信的目的，是要把收方不知道的信息及时、可靠、完整、安全而又经济地传送给指定的收方。该模型按功能可分为信源、编码器、信道、译码器、信宿五部分。,图11 信息传输系统模型,1信源 信源是产生消息和消息序列的源，它可以是人、生物、机器或其他事物，它是事物各种运动状态或存在状态的集合。信源发出的消息有语音、
4、图像、文字等，人的大脑思维活动也是一种信源。信源的输出是消息，消息是具体的，但它不是信息本身。另外，信源输出的消息是随机的、不确定的，但又有一定的规律性。信源输出的消息有多种形式，可以是离散的或连续的、平稳的或非平稳的、无记忆的或有记忆的。,2编码器 编码器可分为信源编码器、信道编码器和保密编码器三种。信源编码对信源输出的消息进行适当的变换和处理，把信息变换成信号，目的是为了提高信息传输的效率，使传输更为经济、有效，还要去掉一些与被传信息无关的多余度；信道编码是为了提高信息传输的可靠性而对消息进行的变换和处理；保密编码保证了信息的安全性。由于传输信息的媒质如电波、电缆等总是存在有各种人为或天然
5、的干扰和噪声，因此，为了提高整个通信系统传输信息的可靠性，就需要对加密器输出的信息进行一次纠错编码，人为地增加一些多余信息，使信息传输系统具有自动检错或纠错功能。当然对于各种实际的通信系统，编码器还应包括换能、调制、发射等各种变换处理功能。,3.信道 信道是信息传输和存储的媒介，是通信系统把载荷消息的信号从甲地传输到乙地的媒介。在狭义的通信系统中，实际信道有明线、电缆、波导、光纤、无线电波传播空间等，这些都属于传输电磁波能量的信道。当然，对广义的通信系统来说，信道还可以是其他的传输媒介。信道除了传送信号以外，还有存储信号的作用，在信道中还存在噪声和干扰，为了分析方便起见，把在系统其他部分产生的
6、干扰和噪声都等效地折合成信道干扰，看成是由一个噪声源产生的，它将作用于所传输的信号上。这样，信道输出的是已叠加了干扰的信号。由于干扰或噪声往往具有随机性，因此信道的特性也可以用概率空间来描述。,4.译码器 译码是编码的反变换。一般认为这种变换是可逆的。译码器也可分成信源译码器、信道译码器和保密译码器三种。 5信宿 信宿是消息传送的对象，即接收消息的人或机器。,5信宿 信宿是消息传送的对象，即接收消息的人或机器。 图11给出的模型只适用于收、发两端单向通信的情况。它只有一个信源和一个信宿，信息传输也是单向的。更一般的情况是：信源和信宿各有若干个，即信道有多个输入和多个输出。另外，信息传输也可以双
7、向进行。例如，广播通信是一个输入、多个输出的单向传输通信，因特网是多个输入、多个输出的多向传输通信，卫星通信网也是多个输入、多个输出的多向传输通信。,1.2 信息编码的发展 1.2.1 信源压缩编码的发展 1948年,香农在通信的数学理论一文中，用概率测度和数理统计的方法系统地讨论了通信的基本问题，得出了几个重要而带有普遍意义的结论。香农理论的核心是：在通信系统中采用适当的编码后能够实现高效率和高可靠性的信息传输，并得出了信源编码定理和信道编码定理。从数学观点看，这些定理是最优编码的存在定理。但从工程观点看，这些定理不是结构性的，不能从定理的结果直接得出实现最优编码的具体途径。然而，它们给出了
8、编码的性能极限，在理论上阐明了通信系统中各种因素的相互关系，为人们寻找最佳通信系统提供了重要的理论依据。,当已知信源符号的概率特性时，可计算它的信息熵，用它表示每个信源符号所载有的信息量。编码定理不但证明了必存在一种编码方法，使代码的平均长度可任意接近但不能低于信息熵，而且还阐明达到这一目标的途径，就是使概率与码长匹配。信源编码定理出现后，编码方法就趋向于合理化。从无失真信源编码定理出发，1948年，香农在论文中提出并给出了简单的编码方法(香农编码)；1952年，费诺(Fano)提出了一种费诺码；同年，霍夫曼(D.A.Huffman)构造了一种霍夫曼编码方法，并证明了它是最佳码。霍夫曼码是有限
9、长度的块码中最好的码，亦即它是代码总长度最短的码。1949年，克拉夫特(L.G.Kraft)提出了Kraft不等式，指出了即时码的码长必须满足的条件。后来，麦克米伦（B.McMillan）在1956年证明惟一可译码也满足此不等式。到1961年，卡拉什（J.Karush）简化了麦克米伦的证明方法。,霍夫曼码在实际中已有所应用，但它仍存在一些块码及变长码所具有的缺点。例如,概率特性必须精确地测定，它若略有变化，就需更换码表；对于二元信源，常需多个符号合起来编码，才能取得好的效果等。因此，霍夫曼码在实用中常需作一些改进，同时也就有研究非块码的必要性。算术码就是一种非块码，它是从整个序列的概率匹配的角
10、度来进行编码的。其实，此概念也是香农首先提出的，后经许多学者改进，已逐渐进入实用阶段。1968年前后，埃利斯(P.Elias)发展了香农费诺码，提出了算术编码的初步思路。而里斯桑内(JRissanen)在1976年给出和发展了算术编码；1982年，他和兰登(G.G.Langdon)一起将算术编码系统化，并省去了乘法运算，使其更为简化,易于实现。,若对概率特性未知或不确知的信源进行有效的编码，上述方法已无能为力。对有些信源，要确知信源的统计特性相当困难，尤其是高阶条件概率；何况有时信源的概率特性根本无法测定，或是否存在也不知道。例如,地震波信号就是如此，因为无法取得大量实验数据。当信源序列是非平
11、稳时，其概率特性随时间而变更，要测定这种信源的概率特性也近乎不可能。人们总希望能有一种编码方法通用于各类概率特性的信源，通用编码就是在信源统计特性未知时对信源进行编码，且使编码效率很高的一种码。,1977年，以色列学者兰佩尔（A.Lempel)和奇费（J.Ziv)提出了一种语法解析码，习惯上称之为LZ码。到1978年，他们又对这种基于字典的方法提出了改进算法，分别称为LZ77和LZ78。1984年,韦尔奇（T.A.Welch)以LZ编码中的LZ78算法为基础修改成一种实用的算法，后定名为LZW算法。LZW算法保留了LZ78算法的自适应性能，压缩效果也大致相同；但LZW算法的显著特点是逻辑性强，
12、易于硬件实现，且价格低廉，运算速度快。LZW算法已经作为一种通用压缩方法，广泛应用于二元数据的压缩。,前面介绍的无失真信源编码只适用于离散信源或数字信号，不适用于连续信源或模拟信号，如语音、图像等信号的数字处理。因为连续信源的每个样值所能载荷的信息量是无限的，而数字信号的值则是有限的，所以对连续信源不引入失真是不可能的。并且连续信号所对应的信宿一般是人，当失真在某一限度以下时是不易被人感觉到的。同时，信宿不论是人还是机器都存在一定的灵敏度和分辨力，超过信宿的灵敏度和分辨力所传送的信息是毫无意义的，也是完全没有必要的。比如语音信源，当分层量化超过28256级时，人耳就很难分辨，所以没有必要在量化
13、时超过256级。,对图像信源亦是如此，人们看电影时可以充分利用人眼的视觉暂留效应，当放映机放速达25张每秒以上时，人眼就能将离散的照片在人脑内反映成连续画面。若放速大大超过25张每秒，则对普通画面是毫无意义的。限失真信源编码的研究较信道编码和无失真信源编码落后十年左右。1948年，香农在其论文中已体现出了关于率失真函数的思想，在1959年,他发表的保真度准则下的离散信源编码定理首先提出了率失真函数及率失真信源编码定理。1971年，伯格尔的信息率失真理论是一本较全面地论述有关率失真理论的专著。率失真信源编码理论是信源编码的核心问题，是频带压缩、数据压缩的理论基础，直到今天它仍是信息论研究的课题。
14、,连续信源编成代码后就无法无失真地恢复成原来的连续值，此时只能根据率失真理论进行限失真编码。限失真编码实际上就是最佳量化问题。最佳标量量化常不能达到率失真函数所规定的R(D)值。后来人们又提出了矢量量化的概念，即将多个信源符号合成一个矢量并对它进行编码。从理论上讲，在某些条件下，用矢量量化来编码可以达到上述的R(D)值，但在实现上还是非常困难的，有待进一步的研究成果来改进。1955年，埃利斯提出了预测编码方法,经过改进,现已经成为美国军用通信语言压缩的标准算法。,预测编码利用前几个符号来预测后一个符号的值，预测值与实际值之差亦即预测误差作为待编码的符号，这些符号间的相关性就大为减弱，这样可提高
15、压缩比。变换编码是指样值空间的变换，例如从时域变到频域。在某些情况下，变换编码可减弱符号间的相关性，取得良好的压缩比。预测编码和变换编码已在实际中有所应用。从理论上说，怎样才能把有记忆信源转换成无记忆序列，目前尚无理想的方法，更没有不十分复杂而能实际应用的方法。,现在，编码理论与技术不仅在通信、计算机以及自动控制等电子学领域中得到直接的应用，而且还广泛地渗透到生物学、医学、生理学、语言学、社会学和经济学等领域。在编码理论与自动控制、系统工程、人工智能、仿生学、电子计算机等学科互相渗透、互相结合的基础上，形成了一些综合性的新兴学科。尤其是随着数学理论，如小波变换、分形几何理论、数学形态学等，以及
16、相关学科，如模式识别、人工智能、神经网络、感知生理心理学等的深入发展，世界范围内的有关专家一直在追求、寻找现有压缩编码的快速算法，同时，又在不断探索新的科学技术在压缩编码中的应用，因此，新颖、高效的现代压缩方法相继产生。,1.2.2 信道纠错编码的发展 在一部分科学家研究信源编码的同时，另外一部分科学家从事有关信道编码(纠错码)的研究工作。这一工作已取得了很大的进展，并已经形成一门独立的分支纠错码理论。 1950年,汉明(R.W.Hamming)发表的论文检错码与纠错码是开拓编码理论研究的第一篇论文。这篇论文主要考虑在大型计算机中如何纠正所出现的单个错误。1952年,费诺(RM.Fano)给出
17、并证明了费诺不等式，并给出了关于香农信道编码逆定理的证明；1957年，沃尔夫维兹采用类似典型序列方法证明了信道编码强逆定理；,1961年，费诺又描述了分组码中码率、码长和错误概率的关系，并提供了香农信道编码定理的充要性证明；1965年，格拉格尔(R.G.Gallager)发展了费诺的证明结论并提供了一种简明的证明方法；1972年,阿莫托(S.Arimoto)和布莱哈特(R.Blahut)分别发展了信道容量的迭代算法。1948年，香农首先分析并研究了高斯信道问题；1964年，霍尔辛格(JL.Holsinger)发展了有色高斯噪声信道容量的研究；1969年，平斯克尔(M.S.Pinsker)提出了
18、具有反馈的非白噪声高斯信道容量问题；1989年,科弗尔(T.M.Cover)对平斯克尔的结论给出了简洁的证明。从能够纠正单个错误的汉明码过渡到能够纠正多个错误的所谓BCH码，整整经历了10年的时间。,因此，可以说20世纪60年代是代数编码理论发展的鼎盛时期。20世纪70年代出现了高帕码(GoppaCode)，从而又把编码理论推向了一个新的高峰，到了80年代，茨伐斯曼(Tsfasman)等人运用代数几何的方法推广了高帕码的思想，指出存在GF(m)上的一列码。这一令人吃惊的结果给编码理论的进一步发展带来了新的希望。汉明码出现后，人们把代数方法引入到纠错码的研究中，形成了代数编码理论。由此找到了大量
19、可纠正多个错误的好码，而且提出了可实现的编译码方法。但代数编码的渐近性能很差，不能实现香农信道编码定理所指出的结果，因此，有些人于1960年左右提出了卷积码的概率译码，并逐步形成了一系列概率译码理论。尤其以维特比(Viterbi)译码为代表的译码方法被美国卫星通信系统所采用，使得香农理论成为真正具有实用意义的科学理论。,香农在1961年发表的论文双路通信信道开拓了网络信息论的研究。1970年以来，随着卫星通信、计算机通信网的迅速发展，网络信息理论的研究异常活跃，成为当前信息论的中心研究课题之一。一方面，艾斯惠特(RAhlswede)(1971年)和廖(HLiao)(1972年)找出了多元接入信
20、道的信道容量区，在1973年，沃尔夫(JKWolf)和斯莱平(DSlepian)将它推广到具有公共信息的多元接入信道中，科弗尔(TMCover)和艾斯惠特也于1983年分别发表文章讨论相关信源在多元接入信道中的传输问题。另一方面，在1972年,科弗尔提出了广播信道的研究，伯格曼斯(PBergmans)(1973年)、格拉格尔(1974年)、科弗尔(1975年)、马登(K.Marton)(1979年)、伊盖马尔(A.ElGamal)(1979年)和范德缪伦(E.C.VanderMeulen)(1979年)等人也先后分别研究了广播信道的容量区问题。近20多年来，对这一领域的活跃研究使得网络信息论的
21、存在理论日趋完善。,1.2.3 密码编码学的发展 香农在1949年发表的保密通信的信息理论论文中，首先用信息论的观点对信息保密问题作了全面的论述。由于保密问题的特殊性，直至1976年Diffe和Hellman发表的密码学的新方向一文提出了公开密钥密码体制后，保密通信问题才得到广泛研究。尤其在当今，信息的安全和保密问题更加突出和重要。人们把线性代数、初等数论、矩阵等知识引入保密问题的研究，已形成了独树一帜的一个分支密码学理论。 密码是一个古老的话题。早在4000多年前，古埃及人就开始使用密码来保密传递的消息。作为保密信息的手段，密码技术本身也处于秘密状态，基本上局限于军事目的，只为少数人所掌握和
22、控制，所以，它的发展受到了极大的限制。,20世纪70年代是密码学发展的重要时期。美国国家标准局(NBS，即现在的国家标准与技术研究所NIST)开始数据加密标准(Data Encryption Standard)的征集工作。1975年3月17日，NBS在Federal Register上公布了一个候选算法；1976年11月23日，该算法被正式确认为联邦标准DES，并授权在政府通信中使用。此后，DES被多个部门和标准化机构采纳，甚至成为事实上的国际标准，直到1998年该标准才正式退役。1976年11月，Diffie与Hellman的革命性论文密码学新方向(New Directions in Cry
23、ptography)发表，开辟了公开密钥密码学的新领域，成为现代密码学的一个里程碑。1978年，R.L.Rivest、A.Shamir和L.Adleman实现了RSA公钥密码体制，并成为了公钥密码的杰出代表和事实标准。,1969年,哥伦比亚大学的Stephen Wiesner首次提出“共轭编码(Conjugate Coding)”的概念。1984年，Bennett Charles等人在Wiesner的思想启发下，首次提出了基于量子理论的(现称为)BB84协议，从此量子密码理论宣告诞生。量子密码不同于以前的密码技术，是一种可以发现窃听行为、安全性基于量子定律的密码技术，可以抗击具有无限计算能力的
24、攻击。有人甚至认为，在量子计算机诞生之后，量子密码技术可能成为惟一的真正安全的密码技术。,1985年，N.Koblitz和V.Miller把椭圆曲线理论应用到公钥密码技术中，使公钥密码技术取得了重大进展，成为公钥密码技术研究的新方向。密码技术的另一个重要方向流密码(也称序列密码)理论同样也取得了重要的进展。1989年,R.Mathews、D.Wheeler、L.M.Pecora和Carroll等人把混沌理论引入到流密码及保密通信理论中，为序列密码理论开辟了一条新的途径。1997年9月12日，美国国家标准与技术研究所NIST开始征集新一代数据加密标准来接任即将退役的DES;2000年10月2日，
25、由比利时密码学家Joan Daemen和Vincent Rijmen提交的Rijndael算法被确定为AES算法。,2000年1月，欧盟启动了新欧洲数据加密、数字签名、数据完整性计划NESSIE，旨在提出一套强壮的包括分组密码、流密码、散列函数、消息认证码(MAC)、数字签名和公钥加密的密码标准，使欧洲工业界保持密码学研究领域的领先地位，到2002年底最终确定各类标准算法。,经典的密码学是关于加密和解密的理论，主要用于通信保密。在今天，密码学已得到了更加深入、广泛的发展。其内容已不再是单一的加、解密技术，已被有效、系统地用于电子数据的保密性、完整性、真实性和不可否认性等各个方面。其中，数据的保
26、密性就是对数据进行加密，使非法用户无法读懂数据信息以及读取信息；完整性是对数据完整性的鉴别，以确定数据是否被非法篡改;真实性是指数据来源和数据本身真实性的鉴别，保证合法用户可以应用密钥得到正确的信息不被欺骗；不可否认性是真实性的另一个方面，有时，不但要确定数据来自何方，而且还要求数据源不可否认发送的数据。,现代密码技术的应用已深入到信息安全的各个环节和对象。主要技术有：数据加密、密码分析、数字签名、信息鉴别、零知识认证、秘密共享，等等。密码学的数学工具也更加丰富，如概率统计、数论、组合、代数、混沌、椭圆曲线等，现代数学的许多领域都有密码学的足迹。,另一个值得一提的是近年来发展迅速的信息隐藏技术
27、。这是一种将需要保密的信息隐藏在公开信息中来保密、传输的技术，所以可以称为秘密的信息嵌入技术，它主要基于不在意信息传输的思想。相对而言，密码技术是一种公开的信息嵌入、刻意传输技术。如果把密钥视为秘密隐藏信息的秘密，那么广义上，密码技术也是一种信息隐藏技术，这种信息隐藏的秘密由密钥控制；狭义上隐藏信息的秘密由算法控制，如果算法暴露或公开，那么信息也就无法隐藏了，所以信息隐藏技术的另一个重要环节是不在意传输。将信息隐藏在平凡、经常性的公开信息(如广播、电视、图片等)中进行传输，使窃密者无从下手，以此达到逃避信息窥测的目的。数字水印、数字指纹等技术是信息隐藏技术的典型方法，已被广泛地应用于数字产品的产权保护上。,