低密度奇偶校验码：设计、构造与统一框架

　　Error control codes protect the accuracy of data in modern information sys-tems，including computing，communication，and storage systems. Low-density parity-check （LDPC） codes and their relatives represent the state of the art in error control coding and are renowned for their ability to perform close to the theoretical limits. This book presents recent results on various LDPC code designs，making strong connections between two prominent design approaches，the algebraic-based and the graph theoretic-based constructions. New codes and code construction techniques are presented.Most methods for constructing LDPC codes can be classified into two general categories，the algebraic-based and the graph-theoretic-based constructions. The two best-known graph-theoretic-based construction methods are the progressive edge-growth （PEG） and the protograph-based （PTG-based） methods，devised in 2001 and 2003，respectively. Both of these techniques involve computer-aided design. One of the earliest algebraic-based methods for constructing LDPC codes is the superposition （SP） construction，proposed in 2002. In this book，the algebraic-based construction method is re-interpreted from both the algebraic and the graph-theoretic perspectives. From the algebraic point of view，it is shown that the SP-construction of LDPC codes includes，as special cases，most of the major algebraic construction methods developed since 2002. From the graph-theoretic point of view，it is shown that the SP-construction also includes the PTG-based construction as a special case. Based on this PTG/SP connection，an algebraic method is developed here to construct PTG-based LDPC codes.There are advantages to putting the algebraic-based and the PTG-based constructions into a single framework，the SP framework. One advantage is that SP descriptions of codes tend to be relatively compact，enabling simple code specifications in standards and textbooks. Another advantage to studying LDPC codes under the SP framework is that students and practitioners need only learn a single code design approach rather than the myriad approaches that exist in the published literature.Both binary and nonbinary code constructions will be presented under the SP framework. The SP-construction also leads to a new class of LDPC codes with a doubly quasi-cyclic （QC） structure as well as algebraic methods for constructing spatially and globally coupled LDPC codes. The globally coupled codes will be shown to possess a highly effective burst-erasure correction capability.A good number of new LDPC codes are constructed and simulated over thebinary-input additive white Gaussian noise channel and the binary erasure channel.This book will open the door for readers to understand many topics in modern LDPC codes that are scattered in the literature. It is intended as a self-study guide for students，researchers，and engineers interested in LDPC codes and their variations. The book explains the different design methodologies in detail and provides an ample number of code constructions along with simulations. The book shows that code design and construction are more of an art rather than science.Hopefully，after reading this book，the reader may gain enough artistic experience to produce codes that not only meet required specifications but also improve upon those reported here. To make the material widely accessible，the authors have kept the presentation as clear as possible and assumed only basic knowledge of terminology and results that are commonly covered in textbooks on coding theory.

　　李娟娥（Juane Li）博士毕业于美国加州大学戴维斯分校，师从国际编码理论权威林舒教授。她目前是美光科技公司（Micron Technology Inc.）的资深系统架构师。她的研究兴趣包括通信和存储系统的信道编码，以及低密度奇偶校验码的编码器和译码器的硬件实现。林舒（Shu Lin）是世界知名的编码理论专家，曾担任IEEE信息论学会主席。他本科毕业于台湾大学，博士毕业于美国的莱斯大学，后在夏威夷大学檀香山分校、得克萨斯农工大学、加州大学戴维斯分校等大学任教50余年。他是国际电气与电子工程师协会的终生杰出会士（IEEE Life Fellow），获得过洪堡研究奖（1996）、 IEEE第三千年奖章（2000）、NASA杰出公共成就奖章（2014）、马奎斯世界名人录终身成就奖（2019）和IEEE研究生教育奖（2020）。他在编码理论领域撰写过多部著作，“香农信息科学经典”系列里已出版了《差错控制编码 第2版》《信道编码：经典和现代方法》和《低密度奇偶校验码：设计、构造与统一框架》。哈立德·阿卜杜勒·加法尔（Khaled Abdel-Ghaffar）是加州大学戴维斯分校电子与计算机工程系的教授。他本科毕业于埃及亚历山大大学，博士毕业于美国加州理工学院。他的研究兴趣主要在编码理论，发表过100多篇学术论文，并曾担任 IEEE Transactions on Information Theory和IEEE Transactions on Communications的副主编。他和林舒教授是李娟娥博士在加州大学戴维斯分校的共同导师。威廉·瑞安（William E. Ryan）是通信理论和信道编码领域专家，是国际电气与电子工程师协会的杰出会士（IEEE Fellow）。他本科毕业于美国的凯斯西储大学，博士毕业于弗吉尼亚大学，后在新墨西哥州立大学和亚利桑那大学任教近20年，他目前是泽塔联合公司（Zeta Associates， Inc.）的高级合伙人。他的研究兴趣主要在编码和信号处理及其在数据存储和无线数据通信中的应用，发表过100多篇学术论文，并曾担任IEEE Transactions on Communications的副主编。他和林舒教授还一起著有《信道编码：经典和现代方法》一书。丹尼尔·科斯特洛（Daniel J. Costello， Jr.）是世界知名的编码理论专家，曾担任IEEE信息论学会主席。他本科毕业于西雅图大学，博士毕业于圣母大学，后在伊利诺伊理工学院和圣母大学任教50余年，并曾担任圣母大学电子工程系主任。他是国际电气与电子工程师协会的终生杰出会士（IEEE Life Fellow），获得过洪堡研究奖（1999）、IEEE第三千年奖章（2000）、IEEE信息论学会杰出服务奖（2013）和IEEE研究生教育奖（2015）。他和林舒教授还一起著有《差错控制编码 第2版》一书。

Preface
1 Introduction
2 Definitions，Concepts，and Fundamental Characteristics of LDPC Codes
2．1 Matrices and Matrix Dispersions of Finite Field Elements
2．2 Fundamental Structural Properties and Performance Characteristics of LDPC Codes
2．3 Discussion and Remarks
3 A Review of PTG-Based Construction of LDPC Codes
3．1 PTG-LDPC Code Construction
3．2 Conclusion and Remarks
4 An Algebraic Method for Constructing
QC-PTG-LDPC Codes and Code Ensembles
4．1 Construction of QC-PTG-LDPC Codes by Decomposing Base Matrices
4．2 Construction of RC-Constrained PTG Parity-Check Matrices
4．3 Examples
4．4 Construction of the Ensemble of PTG-LDPC Codes from an Algebraic Point of View
4．5 Discussion and Remarks
5 Superposition Construction of LDPC Codes
5．1 SP-Construction of LDPC Codes and Its Graphicallnterpretation
5．2 Ensembles of SP-LDPC Codes
5．3 Constraints on the Construction of SP-LDPC Codes Free of Cycles of Length 4
5．4 SP-Construction ofQC-LDPC Codes
5．5 SP-Base Matrices over Nonnegative Integers
5．6 Discussion and Remarks
6 Construction of Base Matrices and RC-Constrained Replacement Sets for SP-Construction
6．1 RC-Constrained Base Matrices
6．2 Construction of RC-Constrained Replacement Sets Based on Hamming Codes
6．3 Construction of RC-Constrained Replacement Sets Based on m-dimensional Euclidean Geometry EG(m，2) over GF(2)
6．4 Construction of RC-Constrained Replacement Sets Based on RC-Constrained Arrays of CPMs
6．5 Discussion and Remarks
7 SP-Construction of QC-LDPC Codes Using Matrix
Dispersion and Masking
7．1 A Deterministic SP-Construction of QC~LDPC Codes
7．2 Conditions on Girth of CPM-QC-SP-LDPC Codes
7．3 A Finite Field Construction of 2x2 SM-Constrained SP-Base
Matrices and Their Associated CPM-QC SP-LDPC Codes
7．4 Masking
7．5 Design ofMasking Matrices
7．6 Construction of CPM-QC-SP-LDPC Codes for Correcting
Bursts of Erasures by Masking
7．7 Discussion and Remarks
8 Doubly QC-LDPC Codes
8．1 Base Matrices with Cyclic Structure
8．2 CPM-D-SP-Construction of Doubly QC-LDPC Codes
8．3 Masking and Variations
8．4 SP-Construction of CPM-QC-SP-LDPC Codes
8．5 Discussion and Remarks
9 SP-Construction of Spatially Coupled QC-LDPC Codes
9．1 Base Matrices and Their Structural Properties
9．2 Type-l QC-SC-LDPC Codes
9．3 Type-2 QC-SC-LDPC Codes
9．4 Terminated and Tailbiting CPM-QC-SC-LDPC Codes
9．5 A More General Construction of Type-l CPM-QC-SC-LDPC Codes
9．6 A More General Construction of Type-2 CPM-QC-SC-LDPC Codes
9．7 Discussion and Remarks
……
10 Globally Coupled QC-LDPC Codes
11 SP-Construction of Nonbinary LDPC Codes
12 Conclusion and Remarks