编码理论第1章.ppt

1、第一章导论，吉林大学通信工程学院电子工程系田力华，第一章导论1.1信息传输系统1.1.1信息传输目标1.1.2信息传输系统模型1.2信息传输系统开发， 研究目标和现状1.2.1信息论的形成和发展1.2.2信源压缩编码的发展和研究目标1.2.3信道纠错编码的发展和研究目标1.2.4密码学的发展和研究目标1.2.5组合编码的发展和研究目标1.2.6信息论方法的应用和现状，第1章绪论，美国数学家赛申农，1.1信息传输系统，1.1.1信息传输的目标有效性、可靠性、保密性、认证和经济性， 1.1.2信息传输系统模型，为了便于研究信息传输和处理的一般规律，将各种通信系统中具有共同特征的部分提取出来，归纳成

2、统一的理论模型，如图1-1所示。 它通常被称为信息传输系统模型。该模型按功能可分为五个部分：信源编码器、信道解码器和信宿；12信息传输系统的发展、研究目标和现状；1.2.1信息论的形成和发展历史上，信息论的形成是两个人共同努力的结果，一个是通信工程学者，另一个是统计数学家。根据这一实际情况，本文从三个方面介绍了信息论的形成和发展。1.通信技术的理论基础。统计数学的一个分支。信号和信息处理的一般理论基础1.2.2信源压缩编码的发展和研究目标1。经典信源编码(1)无失真信源编码信源统计特性是已知的1948年，香农在他的论文通信的数学理论中给出了几个重要而普遍的结论。也就是说，在通信系统中采用适当的

3、编码之后，可以高效率和高可靠性地传输信息。从无损信源编码定理出发，香农于1948年提出并给出了一种简单的编码方法(Shannon coding)，费诺于1952年提出了一种费诺编码，而DAHuffman于同年构造了一种霍夫曼编码方法，被证明是最好的编码。算术码是一种非分组码，它是由整个序列的概率匹配来编码的。源统计特性未知的通用编码是一种在源统计特性未知的情况下，能够对源进行编码并使编码效率非常高的编码。在20世纪70年代末，以色列学者A.lempel和J.ziv提出了一种句法分析代码，通常被称为LZ代码。1977年，他们首次提出了这种基于字典的方法，1978年，他们分别提出了被称为LZ77和

4、LZ78的改进算法。1984年，韦尔奇在LZ编码中被修改为一种基于LZ78算法的实用算法，后来被命名为LZW算法。LZW算法作为一种通用的压缩方法在二进制数据压缩中得到了广泛的应用。(2)有限失真信源编码香农的率失真函数的思想已经体现在他1948年的论文中。1959年，他发表了保真准则下的离散信源编码定理，首次提出了率失真函数和率失真信源编码定理。率失真信源编码理论是信源编码的核心问题，是频带压缩和数据压缩的理论基础，也是当今信息论研究的主题。虽然现代信源编码的经典方法是基于信源的固有统计特性，并利用人类视觉系统的一些特性进行压缩编码，但这种方法并没有得到充分利用，而且随着感知生理学和心理学的

5、发展，人们越来越清楚地认识到，人类视觉感知的特性与统计意义上的信息分布是不一致的，即需要更多的信息来对这些特性进行统计表征，这对于视觉感知可能并不重要。从感知的角度来看，没有必要详细描述这部分特征。此时，编码技术的研究突破了传统香农理论的框架，注重对感知特征的利用，大大提高了编码压缩效率，这是事实基于经典信源编码理论，不难得到信源编码的两种基本方式：一是试图改变信源的概率分布，使其尽可能不均匀，然后用最佳编码方法使平均码长接近信息熵；其次，联合信源的冗余还在于信源之间的相关性，从而消除它们之间的相关性，使它们成为或几乎成为无关信源。基于第一种基本方法的编码方法包括霍夫曼编码、算术编码、游程编码

6、等。它们的压缩效率以它们的熵为极限值；基于基本方法2的编码方法包括预测编码、变换编码、混合编码、矢量量化等。并且它们中的大多数也受到信息熵的约束。1.2.3纠错编码的发展和研究目标1950年由RWHamming发表的检错码和纠错码一文是探索编码理论的第一篇论文。1952年，芬诺给出并证明了费诺不等式，并证明了香农信道编码的逆定理。1972年，SArimoto和RBlahut分别开发了信道容量的迭代算法。香农在1948年首次分析和研究了高斯信道问题。1964年，JL。霍尔辛格开展了有色高斯噪声信道容量的研究。1969年，MSPinsker提出了带反馈的非白噪声高斯信道容量问题；可以说，20世纪6

7、0年代是代数编码理论发展的全盛时期。Goppa码出现于20世纪70年代，将编码理论推向了一个新的高峰。汉明码出现后，人们将代数方法引入纠错码的研究，形成了代数编码理论。然而，代数编码的渐近性能非常差。因此，有人在1960年前后提出了卷积码的概率译码，并逐渐形成了一系列的概率译码理论。香农1961年的论文双向沟通渠道发展了网络信息论的研究。1971年和1972年，拉尔斯威德和赫利奥发现了多址信道的信道容量区域。1973年，JKWolf和DSlepian将其扩展到具有公共信息的多种访问渠道。TMCover和RAhlswede在1983年发表了一些文章，讨论了多接入信道中相关信源的传输。1972年，

8、TMCover提出了对广播频道的研究。1.2.4密码学的发展和研究目标1。自古以来，人类就面临着通信安全的需求。最古老的安全技术是人工操作，也就是说，信息(信号)的加密是通过人们使用纸、笔和一些辅助工具如代码本来实现的。古代的加密方法起源于隐写术，它出现在公元前440年的古希腊战争中。当时，为了安全地传递军事情报，奴隶主剃光了奴隶的头发，在奴隶的光头上写下了信息，头发长出后把奴隶送到另一个部门，再剃光他的头发，原始信息重新出现，从而实现了两个部落之间的秘密交流。在中国古代，有记载说，要表达的真正含义或“秘密语言”隐藏在诗歌或画卷中的特定位置，如藏族诗歌、藏族诗歌、失踪的诗歌和绘画等。大多数人只

9、注意诗歌或绘画的表面意境，而不注意或发现隐藏的“弦外之音”。经典密码经典密码的加密方法通常是单词替换，它是通过手工或机械转换来实现的。经典密码体制初步体现了现代密码体制的雏形，它比古代的加密方法更加复杂，变化不大。经典密码学的代表性密码系统主要包括单表代替密码、多表代替密码和轮密码。凯撒密码是典型的单表加密系统；多表替代密码中有维格纳密码和希尔密码。著名的英格玛密码是二战中使用的跑步者密码。轮式机器由一个键盘和一系列轮子组成，每个轮子是26个字母的任意组合。轮子通过齿轮连接，当一个轮子转动时，一个字母可以转换成另一个字母。根据该传输，当最后一个轮被处理时，可以获得加密的字母。现代密码学1949

10、年，香农的开创性论文保密系统的通信理论发表在贝尔系统技术杂志上，奠定了这一理论的基础20世纪70年代是密码学发展的重要时期，其间发生了两件大事。首先，国家标准局(NBS，现在的NIST)开始收集数据加密标准DES(数据加密标准)。后来，DES被许多部门和标准化组织采用为标准，甚至成为事实上的国际标准，并于1998年正式退役。其次，1976年11月，迪菲和赫尔曼的革命性论文密码学的新方向发表，开辟了公钥密码学的新领域，成为现代密码学的里程碑。1978年，RLRivest、AShamir和LAdleman实现了RSA公钥密码系统，成为公钥密码的杰出代表和事实上的标准。2000年1月，欧盟推出了新欧

11、洲数据加密、数字签名和数据完整性计划，旨在提出一套包括分组密码、流密码、哈希函数、消息认证码(MAC)、数字签名和公钥加密在内的强密码标准，使欧洲业界在密码研究领域保持领先地位，并最终在2002年底确定各种标准算法。组合编码的发展和研究目标近年来，以计算机为核心的大规模信息网络特别是互联网的建立和发展，对信息传输质量提出了更高的要求。通常，系统的每个部分都是单独设计的，以便优化每个部分和整个系统的性能。然而，自20世纪70年代中期以来，人们开始关注通信系统整体中几个组件的设计，以使系统达到最佳。例如，信源编码与纠错码相结合的设计，特别是纠错码与调制相结合的中医技术的出现，使系统增益达到几个分贝

12、，取得了显著的经济效益。文件传真中使用的数据压缩技术是实际使用的源编码技术。实践技术不同于纯粹的理论讨论。此外，虽然实用的编码方法是在理论的指导下进行的，但它不仅追求理论性质，如源编码的理论压缩比，还考虑理论性能和工程可实现性，这往往更重要，因此实用的方法往往难以优化。最后，为了匹配复杂的实际源统计，实际源编码方法通常不是单一的方法，而是最佳方法的组合。一维传真编码是一种结合霍夫曼编码和游程编码的实用信源编码方法。级联码是由短码构造长码的一种特殊而有效的方法。它最初是由福尼在1966年提出的。用这种方法构造的长码不需要像普通长码那样复杂的解码设备。通常，二进制(n1，k1)码C1用于内部编码，而另一个非二进制(n2，k2)码C2用于外部编码，以形成简单的级联码。一