《纠错码的代数理论》概要介绍半个世纪以来由数字通信的可靠性要求所建立和不断发展的纠错码数学理论。书中不涉及纠错技术和工程具体实现问题，但也介绍了一些纠错译码算法。《纠错码的代数理论》本书适用于代数专业的研究生和具有较好代数基础的高年级本科生。书中所讲述的知识和方法对于研究信息科学与计算机科学中许多其他问题也会有所帮助。研究生数学丛书 M athem atics series for g raduate s tuden ts编审委员会主编:李大潜副主编:冯克勤编委:(姓氏按拼音字母排序)程崇庆陈木法陈叔平陈志杰李克正李忠邵嘉裕王维克文志英肖杰袁亚湘周青张伟平研究生数学丛书 M athem atics series for g raduate s tuden ts1.连续介质力学中的数学模型(M athematical Modeling in Continuum M echanics2.应用密码学(A pplied Cryptography3. Introduction to m alliavin calculus( Malliavin随杌变分引论)4.纠错码的代数理论(Algebraic theory of Error-Correcting Codes5.抽象代数学基础Fundamentals of Abstract Algebra6. Algebraic Geo mefry代数几何7.反问题(Inverse Problem总序数学是一门在非常广泛的意义下研究自然和社会现象中的数量关系和空间形式的科学。长期以来,在人们认识世界和改造世界的过程中,数学作为种精确的语言和一个有力的工具一直发挥着重要的作用。在现代,数学科学已构成包括纯粹数学及应用数学内涵的众多分支学科和许多新兴交叉学科的庞大的科学体系。作为各门科学的重要基础,作为“四化”建设的重要武器,作为人类文明的重要支柱,数学科学在很多重要的领域中已起着关键性甚至决定性的作用,数学技术已成为高技术的突出标志和重要组成部分,数学的影响和作用已深入到各行各业,可以说无处不在。马克思当年的预门科学只有当它成功地运用了数学之后,才算达到了真正完善的地步”,正在不断得到证实。在这样的背景下,数学科学的重要性已得到空前广泛的认同。在研究生(不限于数学专业的研究生)的培养中,重视数学基础的训练,强调数学思想的熏陶,也已成为一种必然的趋势。但是,国内研究生数学教材及参考读物的实际情况,无论从品种、数量及质量哪一方面来看,都远远不能适应这个形势,甚至也远远落后于本科生的数学教材。这已成为制约提高研究生培养质量的一个重要瓶颈。清华大学出版社和施普林格出版社 Springer verag作,倡议出版这一套《研究生数学丛书》 Mathematics Series for GraduateStudents)可望改善这方面的状况,为我国的研究生打好数学基础、提高数学素质起到积极的作用。根据数学这门科学的特点,同时考虑到研究生学习数学的基本要求和特有方式,这套以面向研究生(包括高年级本科生、硕士及博士研究生)的数学教材或参考读物,将力求体现以下的一些原则主题有理论或(和)应用方面的重要性;·在重点介绍基础性内容的前提下,兼顾学科前沿的重要发展趋势和研究成果;在讲授数学内容的同时,充分体现数学的思想方法和精神实质;·少而精,在较小的篇幅中展现基本的内容;Ⅵ纠错码的代数理论有相当好的可读性,适宜读者自学;·附有习题、思考题及参考资料目录,书末有索引,方便读者深入学习与思考为了有利于体现这些原则,本丛书将采取相当灵活的体例及风格:内容可以是纯粹数学、应用数学或数学与其他学科的交叉;可以是较系统地介绍某一个分支的教材,或是介绍某一前沿分支状况的综述,也可以是课外参考书;可以是原著,也可以是译著;可以是国内作者,也可以是国外作者;可以用中文编写,也可以用英文编写,等等。要实现本丛书的目标和宗旨,任重而道远,但千里之行,始于足下,在学界同仁和广大读者的支持和帮助下,让我们共同努力。李大潜2003年9月于上海纠错码的代数理论20世纪50年代以来,数字计算机和数字通信得到极大的发展。在今天,人们从每个层面上都能感受到计算机和通信的这种进步所产生的广泛而深刻的影响。除了技术进步之外,这种发展也得益于新的数学思想和工具的运用。数字脉冲信号的数学描述方式,从连续性数学( Fourier分析和 Laplace变换)一下子扩展到离散性数学(组合学、数论、代数)。与此同时,数字计算和数字通信中提出许多具有重要应用背景的数学问题,也促进离散性数学自身的发展,注入新的活力。本书的目的是介绍半个世纪以来,由数字通信的可靠性要求所建立和不断发展的纠错码数学理论。纠错码的数学理论是一个很好的题目,用来表达理论和应用之间相互联系和促进的过程。通信的可靠性提出纠错的要求,建立起明确的数学概念和问题,以反映工程上的需求,然后数学家用各种数学工具构作性能愈来愈好的纠错码纯粹数学和应用数学具有不尽相同的价值观念和美学标准。本书讲述纠错码的数学理论,不涉及纠错技术和工程具体实现问题,但是也要介绍一些纠错译码算法,这是应用中十分关心的数学问题。纯粹数学家可能只对构作好的纠错码更有兴趣,但是像关于BCH码的 Berlekamp-Massey算法这样的内容,对于工程师和应用数学家来说,不仅是必需和重要的,而且也是美的。纠错码的数学理论也是一个很好的场所,在这里,不同的数学知识和方法被用来解决通信中一个共同的课题,本书所用的数学工具主要涉及到组合学、初等数论、线性代数和抽象代数(群、环、域的基本知识)。事实上,近20年来纠错码的研究用到了更深刻的数学:代数几何、代数数论和群表示理论。这本书希望代数专业的研究生和具有较好代数基础的高年级本科生能够使用。本书的基本内容是前三章(到BCH码为止)。由于代数几何码需要较为专门的代数几何和代数数论知识(有限域上的代数曲线和代数函数域),本书略去这方面内容。最后一章介绍1996年产生的量子纠错码的数学理论,其中用到点群表示论(有限交换群的特征理论)。附录中介绍有限域的基本知识和线性移存器序列。Ⅷ纠错码的代数理论读者在本书中可以学到纠错码的基本知识,并通过这些材料能复习和加深关于初等数论、线性代数和抽象代数的知识与方法,这些知识和方法对于研究信息科学与计算机科学中许多其他问题也是有用的,我们希望读者通过对这些材料的学习,感受到数学工具和思考方式对应用领域的重要作用,并且能够在今后从事各种工作中,有意识地采用数学工具和思考方式,从而终生与数学相伴并喜欢它。冯克勤于清华园目录纠错码的代数理论总序前言Ⅶ1什么是纠错码1.1通信和纠错的数学模型··.·······························1.2纠错码的基本概念和主要数学问题纠错码的界·线性码…142.1生成阵和校验阵●·…142.2完全线性码: Hamming码和 Golay码…222.3MDS线性码:多项式码312.4二元Reed- Muller码…………………………392.5 M ac Williams恒等式●·463循环码…………………………………………543.1生成式和校验式…………543.2循环码的迹表达式603.3循环码的根,BCH码653.4 Goppa码………764量子纠错码814.1什么是量子纠错码824.2 Stabilizer量子码4.3由经典码构作量子码………………944.4量子权多项式和 Singleton界99附录A:有限域…108A.1有限域……………108纠错码的代数理论_A.2有限域上的多项式环115A.3有限域上的幂级数环…………123A.4有限域的加法特征129附录B:线性移存器序列………………………133B.1线性移存器序列…133B.2线性移存器的综合算法139参考文献145