编码理论 第1章 绪论(第2版)

第1章绪论第1章绪论1.1信息传输系统1.2信息编码的发展第1章绪论1.1信息传输系统1.1.1信息传输的目标研究通信系统的目的就是要找到信息传输过程的共同规律，以提高信息传输的可靠性、有效性、保密性和认证性，从而达到信息传输系统最优化。第1章绪论可靠性高，就是要使信源发出的消息经过信道传输以后，尽可能准确地、不失真地再现在接收端。有效性高，就是经济效果好，即用尽可能短的时间和尽可能少的设备来传送一定数量的信息。注意：提高可靠性和提高有效性常常会发生矛盾，需要统筹兼顾。例如为了兼顾有效性(考虑经济效果)，有时就不一定要求绝对准确地在接收端再现原来的消息，可以允许有一定的误差或一定的失真，或者说允许近似地再现原来的消息。第1章绪论保密性，就是隐蔽和保护通信系统中传送的消息，使它只能被授权接收者获取，而不能被未授权者接收和理解。认证性，是指接收者能正确判断所接收的消息的正确性，验证消息的完整性，确认消息不是伪造的和被篡改的。第1章绪论1.1.2信息传输系统模型各种通信系统，如电报、电话、电视、广播、遥测、遥控、雷达和导航等，虽然它们的形式和用途各不相同，但本质是相同的，都是信息的传输系统。为了便于研究信息传输和处理的共同规律，将各种通信系统中具有共同特性的部分抽取出来，概括成一个统一的理论模型。第1章绪论译码图1―1通信系统模型信源编码加密信道编码信道信道译码解密信源译码信宿密钥源噪声密钥源信源通信系统模型编码第1章绪论信源–产生消息和消息序列的源，它可以是人、生物、机器或其他事物，是事物各种运动状态或存在状态的集合。–信源发出的消息消息可以是文字，语言，图像；可以离散，可以连续；信源可能出现的状态(即信源输出的消息)是随机的、不确定的，但又有一定的规律性。各部件功能第1章绪论编码器–分类：信源编码器、信道编码器、保密编码器–信源编码：对信源输出的消息进行适当的变换和处理，把信息变换成信号，目的是为了提高信息传输的效率，使传输更为经济、有效，还要去掉一些与被传信息无关的多余度；–信道编码：对信源编码输出变换，提高抗干扰性，是为了提高信息传输的可靠性而对消息进行的变换和处理；–保密编码：保证信息的安全性，保护系统中所传消息的真实性、完整性。第1章绪论信道–通信系统把载荷消息的信号从甲地传输到乙地的媒介。干扰源–信道中的噪声和干扰，以及为了分析方便起见，把在系统其他部分产生的干扰和噪声都等效地折合成信道干扰，看成是由一个噪声源产生的，它将作用于所传输的信号上。译码器–编码器的逆变换–分类：信源译码器、信道译码器、保密译码器信宿–消息传送的对象，即接收消息的人或机器。第1章绪论图1-1给出的模型只适用于收发两端单向通信的情况。它只有一个信源和一个信宿，信息传输也是单向的。更一般的情况是：信源和信宿各有若干个，即信道有多个输入和多个输出，另外信息传输也可以双向进行，例如广播通信是一个输入、多个输出的单向传输的通信，而卫星通信则是多个输入、多个输出的多向传输的通信。第1章绪论1.2信息编码的发展1948年，香农在《通信的数学理论》的论文中，用概率测度和数理统计的方法系统地讨论了通信的基本问题，得出了几个重要而带有普遍意义的结论。香农理论的核心是：在通信系统中采用适当的编码后能够实现高效率和高可靠性的信息传输，并得出了信源编码定理和信道编码定理。第1章绪论从无失真信源编码定理出发：•1948年，香农在论文中提出并给出了简单的编码方法(香农编码)；•1952年，费诺(Fano)提出了一种费诺码；•1952年，霍夫曼(D．A．Huffman)构造了一种霍夫曼编码方法，并证明了它是最佳码。•1956年，麦克米伦(B．McMillan)首先证明了惟一可译变长码的克拉夫特(Kraft)不等式。有限长度的块码中的代码总长度最短的码。缺陷：概率特性必须精确地测定，它若略有变化，就需更换码表等1.2.1信源压缩编码的发展第1章绪论•1968年前后，埃利斯(P．Elias)发展了香农―费诺码，提出了算术编码的初步思路；•1976年里斯桑内(J．Rissanen)给出和发展了算术编码;•1982年里斯桑内(J．Rissanen)和兰登(G．G．Langdon)一起将算术编码系统化，并省去了乘法运算，使其更为简化、易于实现。第1章绪论对概率特性未知或不确知的信源进行有效的编码，上述方法已无能为力。希望能有一种编码方法，通用于各类概率特性的信源。•20世纪70年代就有学者提出通用编码。•1977年齐弗(J．Ziv)和兰佩尔(A．Lempel)提出了LZ算法，它是适用于通用信源的编码算法之—。•1978年齐弗(J．Ziv)和兰佩尔(A．Lempel)又提出了改进算法，而且齐弗也证明此方法可达到信源的熵值。•1990年，贝尔(T．C.Bell)等在LZ算法基础上又做了一系列变化和改进，现在LZ码已广泛应用于文本的数据压缩中。第1章绪论从率失真信源编码理论出发•1948年，香农在其论文中已体现出了关于率失真函数的思想。•1959年他发表了“保真度准则下的离散信源编码定理”，首先提出了率失真函数及率失真信源编码定理。•1971年伯格尔的《信息率失真理论》是一本较全面地论述有关率失真理论的专著。是信源编码的核心问题，是频带压缩、数据压缩的理论基础。第1章绪论以上简述了根据香农两个编码定理发展起来的各种信源编码方法，也就是从概率论形成的语法信息出发，去掉冗余而达到压缩码率的目的。现在，编码理论与技术不仅在通信、计算机以及自动控制等电子学领域中得到直接的应用，而且还广泛地渗透到生物学、医学、生理学、语言学、社会学和经济学等各领域。在编码理论与自动控制、系统工程、人工智能、仿生学、电子计算机等学科互相渗透，互相结合的基础上，形成了一些综合性的新兴学科。第1章绪论现代编码方法：•基于小波变换WT的零树(Zerotree)矢量量化方法，它可以达到几百倍的压缩比，且可按不同的压缩比编码，灵活性大。据此，神经网络和模型基编码成为当今研究的热点之一。第1章绪论在研究信源编码的同时，另外一部分科学家从事信道编码(纠错码)的研究工作。这一工作已取得了很大的进展，并已经形成一门独立的分支——纠错码理论。•1950年汉明(R．W．Hamming)发表的论文《检错码与纠错码》是开拓编码理论研究的第一篇论文。这篇论文主要考虑在大型计算机中如何纠正所出现的单个错误。1.2.2信道纠错编码的发展第1章绪论•1952年费诺(R．M.Fano)给出并证明了费诺不等式，并给出了关于香农信道编码逆定理的证明；•1957年沃尔夫维兹采用了类似典型序列的方法证明了信道编码强逆定理；•1961年费诺又描述了分组码中码率、码长和错误概率的关系，并提供了香农信道编码定理的充要性证明；•1965年格拉格尔(R．G．Gallager)发展了费诺的证明结论并提供了一种简明的证明方法；•1972年阿莫托(S．Arimoto)和布莱哈特(R．Blahut)分别发展了信道容量的迭代算法。•1948年香农首先分析并研究了高斯信道问题；•1964年霍尔辛格(J．L.Holsinger)发展了有色高斯噪声信道容量的研究；第1章绪论•1969年平斯克尔(M．S．Pinsker)提出了具有反馈的非白噪声高斯信道容量问题；•1989年科弗尔(T．M．Cover)对平斯克尔的结论给出了简洁的证明。从能够纠正单个错误的汉明码过渡到能够纠正多个错误的所谓BCH码，整整经历了10年的时间。因此，可以说20世纪60年代是代数编码理论发展的鼎盛时期。•20世纪70年代出现了高帕码(GoppaCodes)，从而又把编码理论推向了一个新的高峰。第1章绪论•20世纪80年代，茨伐斯曼(Tsfasman)等人运用代数几何的方法推广了高帕码的思想，指出存在GF(m)上的一列码。•1960年前后提出了卷积码的概率译码，并逐步形成了一系列概率译码理论。•1961年香农的论文《双路通信信道》开拓了网络信息论的研究。•1970年以来，随着卫星通信、计算机通信网的迅速发展，网络信息理论的研究异常活跃，成为当前信息论的中心研究课题之一。•1971年艾斯惠特(R．Ahlswede)和1972年廖(H．Liao)找出了多元接入信道的信道容量区。1973年沃尔夫(J．K．Wolf)和斯莱平(D．Slepian)将它推广到具有公共信息的多元接入信道中。第1章绪论•1983年科弗尔(T．M．Cover)、艾斯惠特(R．Ahlswede)于分别发表文章讨论相关信源在多元接入信道的传输问题。•近20多年来，这一领域研究活跃，使得网络信息论的存在理论已日趋完善。第1章绪论随着人类进入信息时代，信息的传递、存储和交换日益骤增。现代化的通信网、计算机信息网，以及各种类型数据库和电子数据交换系统，特别是因特网的迅速发展，使得信息的安全和保密问题与越来越多的人密切相关。保密学是一门研究通信安全和保护信息资源的既古老而又年青的科学和技术，它包括密码编码学和密码分析学两方面。1.2.3密码编码学的发展第1章绪论•密码编码学是信息安全技术的核心，密码编码学的主要任务是寻求产生安全性高的有效密码算法和协议，以满足对消息进行加密或认证的要求。•密码分析学的主要任务是破译密码或伪造认证信息，实现窃取机密信息或进行诈骗破坏活动。•这两个分支既相互对立又相互依存，正是由于这种对立统一关系，才推动了密码学自身的发展。第1章绪论•1949年香农发表的《保密通信的信息理论》论文中，首先用信息论的观点对信息保密问题作了全面的论述。•1976年迪弗(Diffe)和海尔曼(Hellman)发表了《密码学的新方向》一文，提出了公开密钥密码体制后，保密通信问题才得到广泛研究。•尤其当今，信息的安全和保密问题更加突出和重要。人们把线性代数、初等数论、矩阵等引入保密问题的研究，已形成了独树一帜的分支——密码学理论。第1章绪论根据信息论的各种编码定理和上述通信系统的指标，编码问题可分解为信源编码、信道编码、密码编码三类。•信源编码主要目标是压缩每个信源符号的平均比特数或信源的码率。可分为经典编码方法和现代编码方法两大类。经典编码方法又可分为无失真信源编码和限失真信源编码。编码理论研究的内容第1章绪论实现途径：其一是设法改变信源的概率分布，使其尽可能地非均匀，再用最佳编码方法使平均码长逼近信源熵；编码方法有霍夫曼编码、算术编码、游程编码等其二是联合信源的冗余度也寓于信源间的相关性之中，去除它们之间的相关性，使之成为或差不多成为不相关信源。编码方法有预测编码、变换编码、混合编码、矢量量化等现代压缩编码方法是利用人的视觉感知特点与统计意义上的信息分布并不一致，突破了传统香农理论的框架，注重对感知特性的利用，使得编码压缩效率得以极大提高。第1章绪论•信道编码主要目标是提高信息传送的可靠性。主要方法是增大码率或频带，也就是增大所需的信道容量。复用技术第1章绪论•密码编码主要目标是提高信息传送的安全性。信息安全领域内“攻”与“守”之间的对抗也越来越激烈。信息伪装就是最近“热起来”的一种信息安全新手段。第1章绪论•发展趋势近年来，以计算机为核心的大规模信息网络对信息传输的质量要求更高了。不但要求既快速有效又能可靠地传递信息，而且关心如何设计通信系统中的各部分，使整个系统达到最佳。通常是对系统的各个部分单独设计，以使各部分的性能达到最佳，从而达到使整个系统最佳。自20世纪70年代中期以来，人们开始注意把通信系统的几个部件看成一个整体进行设计，以使系统达到最佳。在实际问题中，应将上述三类编码统一考虑以提高通信系统的性能。第1章绪论编码目标尽量好的效果尽量短的序列尽量少的差错尽量容易实现第1章绪论宏观意义上，编码理论：以信息作为主要研究对象以信息的运动规律和利用信息的原理作为主要的研究内容以信息科学方法论作为主要的研究方法，以扩大人的信息功能(特别是智力功能)为主要研究目标的一门新兴科学。