本书在第一版的基础上进行了彻底的修订和更新，包括了过去20年间该领域所有的重要新发展。本书增加了线性分组码的网格、基于可靠性的线性分组码软判决译码算法、基于网格的软判决译码算法、Turbo编码、低密度奇偶校验码、网格编码调制、分组编码调制7章全新的内容，重点阐述了编码理论和应用领域的三方面最新进展：获得高频谱效率的网格和分组编码调制、可实用的分组码软判决译码方法、分组码和卷积码的软输入和软输出迭代译码技术。

　　本书第二版延续了第一版的风格，作者仍以一种易于理解的方式揭示了复杂问题的本质，读者不必具备太多的数学知识就能理解这些内容。本书还包括了许多例子和性能曲线，用于帮助说明重要的概念。在每一章的章末都给出了大量的习题和参考资料。这使得本书无论是对于高年级本科生还是低年级研究生来说，作为关于编码理论课程的入门教材都非常合适。本书各章的内容较独立，教师可以根据学生的实际情况选讲若干章节。由于本书广泛涵盖了差错控制编码系统的基础理论和实际应用，并且给出了许多最优码的列表，这使得本书也非常适合于作为数字系统设计者的参考书。

无

本书首先归功于香农在1948年所做的“通过有噪传输信道实现可靠通信”的先驱性工作。香农的中心论题是：如果系统的信息传输速率小于信道容量，则通过选择适当的编译码技术就能实现可靠通信。由汉明、格雷等人于19世纪40年代后期所开创的设计好码和有效译码方法的工作，后来受到了许多研究者的关注。这方面的大多数工作在本质上是高度数学化的，因而对其深入理解需要有丰富的近世代数和概率论的背景知识。这对许多希望将这些技术应用于实际系统的工程师和计算机科学工作者来说无疑是一种障碍。本书的目的之一，就是用最少的数学基础知识，使读者能够理解和运用这些相当复杂的技术。
　　19世纪50年代和60年代的编码研究主要致力于发展有效的编译码器。1970年，有位作者首次出版了一本名为《纠错码入门》(An Introduction to Error-Correcting Codes)的书，这本书介绍了最初20年间分组码和卷积码技术的基础知识，以通俗易懂的方式阐述问题，并不追求数学上的严谨性。本书于1983年出版了第1版，同样着重于编码理论的基础知识，并增加了对70年代所发展的许多编码理论实际应用的介绍。第1版的主要内容还包括对分组码检错能力的深入分析，并对卷积码的软译码算法进行了着重讨论。
　　到了20世纪80年代和90年代，随着一些理论研究的进展及显著的实际应用，编码领域取得了突破性的发展。其中三个方面的发展尤其突出：二进制卷积码和分组码应用于扩展(非二进制)调制符号；可实际应用的分组码软译码算法取得发展；发现了用于分组码和卷积码的软输入、软输出迭代译码算法。这些新的进展革命性地改变了实际系统的编码方式，影响了高速数据调制解调器、数字移动蜂窝电话、卫星及空间通信、高密度数据存储等系统的设计。本版增加了七章新的内容，覆盖了这些专题：两章关于网格编码调制和分组编码调制技术，三章关于分组码的软译码技术，两章关于Turbo码和低密度单奇偶校验码及迭代译码。
　　由于本书的重点是介绍编码的基础理论，而新的技术内容又如此之多，一些特定的专题在本书中无法全部涵盖，例如代数几何码和删除校正码的新发展就没有被涉及。另外，虽然本书中所研究的编码技术可以被应用于数据存储系统，但是并没有直接讨论存储信道的特点。类似地，也未能对衰落信道的编码进行深入的讨论。除了前面提到的新增加的章节外，所有第1版的章节在第2版中都经过彻底的修订和更新。下文给出各个章节的简要介绍，并突出了区别于第1版的改动。
　　第1章对数据通信和存储系统中所采用的差错控制编码进行了综述。简单讨论调制解调的目的是想在一个完整的系统中将编码的作用定位到适当的地位。增加了两节新的内容，用于介绍编码调制、编码增益及香农限的概念。第2章从近世代数的观点来介绍一些为理解后面各章节内容所必需的概念，这些都可以被高年级大学生和实践工程师，以及计算机科学工作者所理解。
　　第3章到第10章详细介绍了分组码的基本原理。第3章介绍线性分组码，还包括对线性码检错能力的分析。第4章介绍了几类重要的线性分组码，其中增加了关于里德穆勒(ReedMuller)码的新内容。第5章介绍循环码的基本结构和性能，以及基于校正子的译码方法。第6章详细讨论了一类重要的码——BCH码，其中包括了BCH译码器的软件和硬件实现，以及采用BCH码的错误检测。第7章包括里德所罗门(ReedSolomon)码及其相关的扩充内容，增加了欧氏代数和频域译码的材料。第8章详细讨论了大数逻辑可译码，包括重要的欧氏几何码和射影几何码。第9章和第10章完全是新增加的内容。第9章发展了分组码的网格结构理论，为第14章介绍基于网格的软译码算法打下基础。第10章由Marc Fossorier教授执笔，详细讨论了分组码的基于可靠性的软译码算法，并介绍了迭代译码技术。
　　第11章到第13章介绍卷积码的基础知识。第11章介绍了卷积码，以编码器的状态图作为研究码的结构特性和距离特性的基础，并增加了关于反馈编码器和输入-输出重量枚举函数的新内容。第12章介绍卷积码的最优译码算法，重点介绍用于硬解调判决和软解调判决的(最大似然)维特比译码算法，增加了关于软输出维特比算法、(最大后验概率)BCJR算法及打孔和咬尾码调整技巧的介绍，另外还包括了基于编码器重量枚举函数的详细性能分析。第13章介绍面向卷积码的次优译码算法，重点介绍序列译码算法——ZJ(堆栈)算法和费诺算法，以及大数逻辑译码算法。我们对序列译码的计算性能这一难题进行了讨论，但是并未做详细的证明。新增的内容包括基于软判决的序列译码算法和大数逻辑译码算法。
　　在第14章中，将第12章介绍的卷积码的软译码算法推广到分组码。这一章全新的内容大量使用了第9章中介绍的分组码的网格结构。
　　第15章到第19章则涵盖了自从本书第1版出版后在该研究领域的重要进展。第15章介绍级联编码、多级译码及码分解的重要概念，它们构成了后面四章所介绍的新编码技术的基础。第16章到第19章是全新的内容。第16章介绍并行级联领域，或称Turbo编码，及其相关的基于第12章中介绍的BCJR算法的迭代译码技术，其中还包括基于均匀交织技术和EXIT表概念的性能分析。第17章全面介绍了低密度单奇偶校验码及其代数的、随机的和组合的构造方法，另外还讨论了几种译码算法并给出了对软判决置信度传播译码的完整推导。编码调制问题在第18章和第19章中讨论。第18章介绍网格编码调制的基本原理，其中包括旋转不变码和多维信号集的章节。第19章介绍分组编码调制，其中包括了多级调制和多级解调的重要概念。
　　本书的结尾处用了三章的篇幅介绍突发错误纠正和自动请求重传(ARQ)策略。第20章和第21章介绍了针对突发错误及衰落信道中经常遇到的突发和随机组合错误的纠正方法，其中包括了分组(见第20章)和卷积(见第21章)的纠突发错误码。第23章主要介绍用于双向通信信道的ARQ差错控制方法，讨论了纯ARQ(采用错误检测的重传)和混合ARQ(联合使用错误检测和错误纠正的重传)。
　　从内容上看，本书无论是作为教材，还是作为从事差错控制系统设计的工程师和计算机科学工作者的一本综合参考书，都有裨益。书中的三个附录包括了用于构造大多数分组码的代数基础。全书给出了许多不同译码方式下已知的最优分组码和卷积码的列表。这些对于设计者寻求某一特定应用中的最优码是有价值的。在这一版中，对这些表中定义的最优码的生成多项式和奇偶校验多项式采用了统一的八进制表示。书中还包括许多实际系统所采用的码的例子和特定编码系统的计算机仿真性能曲线。在每一章的末尾，作者都设计了一组作业习题。虽然有些问题深一些，但大多数问题是书中所讲内容的相对直接的应用。教师可从出版社获得部分题目的题解。每章的末尾还给出了参考文献。虽然我们不准备编辑完整的编码理论参考书目，但所列的参考目录可提供书中所涉及论题的细节。
　　本书可作为高年级本科生、研究生第一年或全日制研究生有关编码理论课程的入门教材，也可以作为想了解编码的基础知识及如何设计差错控制系统的工程师和计算机科学工作者的自学指南。
　　作为编码理论课程的教材，本书可分为两学期讲授。第一学期可包括第1~10章有关分组码的部分，第二学期讲授其余有关卷积码和高级的分组码专题。另一种可行的方案是第一学期讲授第1~8和11~13章，包括分组码和卷积码的基础知识，第二学期可以针对提高的专题。也可以选择本书中的部分内容在一个学期的课程中完成。分组码的课程可由第1~7章和第8~10、14~15、17、19~20及22章中的选择性专题组成，而第1、11~13、16、18和21章的内容可组成完整的卷积码的课程。
　　这里，我们要向Marc Fossorier教授表示真挚的谢意。他除了完成第10章的撰写外，还花费了大量的时间反复阅读了各个章节的手稿。我们也要感谢许多研究生和博士后助理，他们提出了许多建议并在本书的准备中提供帮助，包括进行计算机仿真、绘图、制表并将手稿转为LaTex格式。他们包括：Yu Kou、Cathy Liu、Rose Shao、Diana Stojanovic、Jun Xu、Lei Chen、Oscar Takeshita、Gil Shamir、Adrish Banerjee、Arvind Sridharan、Ching He、Wei Zhang和Ali Pusane。特别值得一提的是，Yu Kou、Cathy Liu和Adrish Banerjee对最后的手稿进行了校阅。
　　我们对国家科学基金会(National Science Foundation)和国家宇航局(National Aeronautics and Space Administration，NASA)对我们在编码领域的研究所给予的全力支持表示感谢。没有他们的协助，我们在编码方面的兴趣绝不可能发展到写这本书的地步。我们还要向在本书写作过程中提供设备和帮助的夏威夷大学玛诺亚分校(University of Hawaii,Manoa)，加利福尼亚大学戴维斯分校(University of California,Davis)，圣母大学(University of Notre Dame)和德国的洪堡基金会(Humboldt Foundation)表示感谢。
　　最后，我们要对我们的妻子、孩子和孙子们在本书的写作过程中不断的关怀和支持表示深深的谢意。

　　林舒(Shu Lin)
　　加利福尼亚大学戴维斯分校(University of California,Davis)
　　夏威夷大学玛诺亚分校(University of Hawaii,Manoa)

　　DJ科斯特洛 Jr(Daniel JCostello,Jr)
　　圣母大学(University of Notre Dame)

译者序
前言
第1章用于可靠数字传输和存储的
编码
11引言
12码的类型
13调制和编码
14最大似然译码
15错误类型
16差错控制策略
17性能的衡量
18编码调制
参考文献
第2章代数引论
21群
22域
23二元域算术
24伽罗华域GF(2m)的构造
25伽罗华域GF(2m)的基本性质
26伽罗华域GF(2m)算术的计算举例
27向量空间
28矩阵
习题
参考文献
第3章线性分组码
31线性分组码概述
32校正子与差错检测
33分组码的最小距离
34分组码的检错和纠错能力
35标准阵与校正子译码
36BSC上线性码的漏检误码率
37单奇偶校验码、重复码及自偶码
习题
参考文献
第4章重要的线性分组码
41汉明码
42一类纠单个差错并检测两个
差错的码
43里德穆勒码
44里德穆勒码的其他构造方法
45码的平方构造法
46(24，12)格雷码
47乘积码
48交织码
习题
参考文献
第5章循环码
51循环码的描述
52循环码的生成矩阵与校检矩阵
53循环码的编码
54校正子计算和差错检测
55循环码的译码
56循环汉明码
57捕错译码
58改进的捕错译码
59(23，12)格雷码
591Kasami译码器
592系统搜索译码器
510缩短的循环码
511循环乘积码
512准循环码
习题
参考文献
第6章二进制BCH码
61二进制本原BCH码
62BCH码的译码
63求解错误位置多项式σ(X)的迭代
算法
64求解错误位置多项式σ(X)的简化
迭代算法
65求解错误位置数和纠错
66错误和删除的纠正
67伽罗华域运算的实现
68纠错的实现
681校正子的计算
682求解错误位置多项式σ(X)
683错误位置数的计算和纠错
69二进制BCH码的重量分布和错误
检测
610附注
习题
参考文献
第7章非二进制BCH码、RS码及其
译码算法
71q进制线性分组码
72GF（q)上的本原BCH码
73里德所罗门(RS)码
74非二进制BCH码和RS码的译码：
Berlekamp算法
75欧几里德译码算法
76频域译码
77错误和删除的纠正
习题
参考文献
第8章大数逻辑可译码与有限
几何码
81一步大数逻辑译码
82一类一步大数逻辑可译码
83其他的一步大数逻辑译码
831极长码
832差集码
84多步大数逻辑译码
85欧氏几何
86欧氏几何码
87二重EG码
88射影几何与射影几何码
89附注
习题
参考文献
第9章线性分组码的网格
91码的有限状态机模型和网格表示
92二进制线性分组码的比特级网格
93标记状态
94比特级网格的结构性质
95基于奇偶校验矩阵的状态标记和
网格构造
96网格的复杂度和对称性
97网格的分段和并行分解
98低重量子网格
99笛卡尔积
习题
参考文献
第10章基于可靠性的线性分组码软
判决译码算法
101软判决译码
102可靠性量度与基于可靠性的一般
译码方法
103译码码字的最优性充分条件
104广义最小距离译码算法与Chase
译码算法
1041GMD译码算法
1042Chase译码算法
1043Chase和GMD译码算法
的推广
105加权删除译码
106一种基于迭代处理最不可靠位的
最大似然译码算法
107缩减列表校正子译码算法
108最可靠独立位置重复处理译码
算法
1081最可靠和最不可靠基
1082基于优先级的搜索译码算法
1083分级统计译码算法
1084基于校正子的分级统计
译码算法
109加权大数逻辑译码
1091二进制对称信道(BSC)上RM码
的大数逻辑译码
1092基于可靠性信息的大数
逻辑译码
1010一步大数逻辑可译码的基于可靠性
的迭代译码
10101基于MAP的迭代译码
10102基于置信度传播的迭代译码
习题
参考文献
第11章卷积码
111卷积码的编码
112卷积码的结构特点
113卷积码的距离特性
习题
参考文献
第12章卷积码的最优译码
121维特比算法
122卷积码的性能界
123构造好的卷积码
124维特比算法的实现和性能
125软输出维特比算法(SOVA)
126BCJR算法
127打孔卷积码和咬尾卷积码
习题
参考文献
第13章卷积码的次优译码
131ZJ(堆栈)序列译码算法
132Fano序列译码算法
133序列译码的性能特点
134用于序列译码的码的构造
135大数逻辑译码
136大数逻辑译码的性能特点
137大数逻辑可译码的构造
1371自正交码
1372可正交码
习题
参考文献
第14章基于网格的软判决译码
算法
141维特比译码算法
142递归最大似然译码算法
1421网格分段的量度表
1422一个RMLD算法
1423最优网格分段
143基于低重量子网格的次优迭代译码
算法
1431生成候选码字
1432最优性测试和搜索区域
1433基于最小重量网格搜索的
迭代译码算法
1434计算复杂度
1435算法的改进
144MAP译码算法
1441基于比特级网格图的MAP
译码算法
1442双向和并行MAP译码
1443计算复杂度
145基于分段网格的MAP译码
1451算法
1452计算复杂度和存储要求
146MaxLogMAP译码算法
1461基于比特级网格的Maxlog
MAP译码
1462基于分段网格的Maxlog
MAP译码
1463logMAP算法
习题
参考文献
第15章级联编码、码分解与多阶段
译码
151单级级联码
152多级级联码
153多阶段软判决译码
154码的分解
155迭代多阶段MLD算法
156以卷积码作为内码的级联编码
方案
157二进制码级联
习题
参考文献
第16章Turbo编码
161Turbo编码简介
162Turbo码的距离特性
163Turbo码性能分析
164Turbo码的设计
165Turbo码的迭代译码
习题
参考文献
第17章低密度单奇偶校验码
171LDPC码简介
172线性分组码的泰纳图
173LDPC码的几何构造法
174EGLDPC码
175PGLDPC码
176LDPC码的译码
1761大数逻辑译码
1762比特翻转译码算法
1763加权大数逻辑译码与加权
比特翻转译码
1764和积算法
1765有限几何LDPC码的
性能
177基于行分裂与列分裂的码构造
方法
178拆散泰纳图中的环
179缩短的有限几何LDPC码
1710Gallager LDPC码的构造方法
1711掩码EGGallager LDPC码
1712使用循环分解构造的准循环码
1713基于GF(ps)域上有限几何的LDPC
码构造
1714随机LDPC码
1715非规则LDPC码
1716图论LDPC码
1717基于均衡不完全区组设计构造
LDPC码
1718基于具有2个信息符号的缩短RS
码构造LDPC码
1719LDPC码与Turbo码的级联
习题
参考文献
第18章网格编码调制
181网格编码调制简介
182TCM码的构造
183TCM性能分析
184旋转不变TCM
185多维TCM
习题
参考文献
第19章分组编码调制
191距离概念
192多级分组调制码
193多级BCM码的多阶段译码
1931第一阶段译码
1932第二阶段译码
1933第三阶段译码
194级联编码调制
1941单级级联编码调制系统
1942多级级联编码调制系统
195乘积编码调制
196非对称错误保护的多级编码调制
习题
参考文献
第20章纠突发错误码
201引言
202纠单个突发错误循环码的译码
203纠单个突发错误码
2031Fire码
2032短有效纠突发错误码
2033采用交织方法构造的纠突发
错误码
2034采用乘积方法构造的纠突发
错误码
204纠定段突发错误码
205纠突发和随机错误码
2051由RS码导出的码
2052级联码
2053能同时纠正突发和随机错误
的修正Fire码
习题
参考文献
第21章纠突发错误卷积码
211突发错误纠错能力的界
212纠突发错误卷积码
2121BerlekampPreparata码
2122IwadareMassey码
213交织卷积码
214同时纠突发和随机错误的卷积码
2141扩散码
2142突发发现码
2143突发捕获码
习题
参考文献
第22章自动请求重传（ARQ)策略
221基本ARQ方法
222采用有限容量接收缓存器的选择
重传ARQ
2221传输和重传过程
2222接收端的运行和错误恢复
过程
2223常态运行
2224阻塞态运行
2225吞吐效率
223混合模式重传ARQ
224混合ARQ方法
225一类半速率可逆码
226采用有限容量接收缓存器的Ⅱ型
混合选择重传ARQ
2261发送和重传过程
2262常态下接收端的运行
2263阻塞态下接收端的运行
2264吞吐效率2265可靠性
227采用卷积码的混合ARQ系统
228一个级联编码调制混合ARQ系统
2281系统中所采用的码
2282级联编码调制FEC子系统
及重传
2283一个特定系统
习题
参考文献
附录A伽罗华域的表
附录BGF(2m)中元素的最小多项式
附录C长度至210-1的二进制本原
BCH码的生成多项式

由林舒(Shu Lin)教授和DJ科斯特洛(Costello)教授撰写的《差错控制编码基础和应用》一书于1983年出版，作为一本深入浅出的普及型专业教材获得了巨大的成功。该书以通俗易懂的方式介绍了纠错码的理论和相关应用，它的中译本由西安电子科技大学的王育民教授和王新梅教授翻译，早已为国内读者所熟悉。20年后，林舒教授和科斯特洛教授对全书进行了全面的修订和更新，补充了纠错编码领域的大量最新发展内容，于2004年推出了第2版。
　　诚如作者在第2版前言中所述，在过去的20年间，纠错码理论和应用都取得了许多突破性的进展，最新的纠错编码技术已经非常逼近香农所指出的理论极限。纠错编码技术的发展深刻地影响了实际系统的设计，在高速调制解调、移动通信、卫星及空间通信、数据存储等领域得到了广泛的应用，例如低密度单奇偶校验(LDPC)码就已经被欧洲下一代数据广播标准DVB-S2和IEEE的10G以太网标准10GBASE-T所采用。在第2版中增加了全新的七章，分别对软译码、编码调制、Turbo码和LDPC码等内容进行了详尽的阐述，基本覆盖了近年来编码研究领域的最新进展，具体的内容安排可参见作者撰写的前言部分。
　　总体上，第2版保留了第1版的基本特色，在较少的数学背景知识基础上，以通俗易懂的方式阐述问题的本质，着重于基本概念的理解和应用。每章末尾的习题和参考材料对读者加深概念理解很有帮助，这使得本书非常适合作为编码理论课程的入门教材。同时，书中所给出的大量应用举例、性能仿真曲线及已知的最优码列表，使得本书也适合于作为从事数字系统设计的工作者的一本综合参考书。
　　由于本书的第2版仍保留了第1版的部分材料，尤其是在基础理论、分组码与卷积码的讨论和分析等方面。为保持与第1版的一致，在第2版的翻译过程中大量参考了王育民教授和王新梅教授译著的本书第1版中译本，在此特别做以说明并向王育民教授和王新梅教授表示谢意。
　　本书的翻译工作是集体的成果，晏坚、何元智、潘亚汉和陈华完成了主要章节的翻译以及全书的修订，此外，参与翻译工作的还有李倩、李斌、姜博、万鹏、郭代和翟立君。在本书的翻译过程中，得到了清华大学电子工程系曹志刚教授的悉心指导，在此致以诚挚的谢意。
　　由于本书篇幅较长，时间仓促，加之译者水平有限，错误和不妥之处当属难免，恳请读者批评指正。

　　晏坚
　　2007年2月于清华园