1 Coding and Capacity 1
1.1 Digital Data Communication and Storage 1
1.2 Channel-Coding Overview 3
1.3 Channel-Code Archetype：The（7，4）Hamming Code 4
1.4 Design Criteria and Performance Measures 7
1.5 Channel-Capacity Formulas for Common Channel Models 10
1.5.1 Capacity for Binary-Input Memoryless Channels 11
1.5.2 Coding Limits for M-ary-Input Memoryless Channels 18
1.5.3 Coding Limits for Channels with Memory 21
Problems 24
References 26
2 Finite Fields，Vector Spaces，Finite Geometries，and Graphs 28
2.1 Sets and Binary Operations 28
2.2 Groups 30
2.2.1 Basic Concepts of Groups 30
2.2.2 Finite Groups 32
2.2.3 Subgroups and Cosets 35
2.3 Fields 38
2.3.1 Definitions and Basic Concepts 38
2.3.2 Finite Fields 41
2.4 Vector Spaces 45
2.4.1 Basic Definitions and Properties 45
2.4.2 Linear Independence and Dimension 46
2.4.3 Finite Vector Spaces over Finite Fields 48
2.4.4 Inner Products and Dual Spaces 50
2.5 Polynomials over Finite Fields 51
2.6 Construction and Properties of Galois Fields 56
2.6.1 Construction of Galois Fields 56
2.6.2 Some Fundamental Properties of Finite Fields 64
2.6.3 Additive and Cyclic Subgroups 69
2.7 Finite Geometries 70
2.7.1 Euclidean Geometries 70
2.7.2 Projective Geometries 76
2.8 Graphs 80
2.8.1 Basic Concepts 80
2.8.2 Paths and Cycles 84
2.8.3 Bipartite Graphs 86
Problems 88
References 90
Appendix A 92
3 Linear Block Codes 94
3.1 Introduction to Linear Block Codes 94
3.1.1 Generator and Parity-Check Matrices 95
3.1.2 Error Detection with Linear Block Codes 98
3.1.3 Weight Distribution and Minimum Hamming Distance of a Linear Block Code 99
3.1.4 Decoding of Linear Block Codes 102
3.2 Cyclic Codes 106
3.3 BCH Codes 111
3.3.1 Code Construction 111
3.3.2 Decoding 114
3.4 Nonbinary Linear Block Codes and Reed-Solomon Codes 121
3.5 Product，Interleaved，and Concatenated Codes 129
3.5.1 Product Codes 129
3.5.2 Interleaved Codes 130
3.5.3 Concatenated Codes 131
3.6 Quasi-Cyclic Codes 133
3.7 Repetition and Single-Parity-Check Codes 142
Problems 143
References 145
4 Convolutional Codes 147
4.1 The Convolutional Code Archetype 147
4.2 Algebraic Description of Convolutional Codes 149
4.3 Encoder Realizations and Classifications 152
4.3.1 Choice of Encoder Class 157
4.3.2 Catastrophic Encoders 158
4.3.3 Minimal Encoders 159
4.3.4 Design of Convolutional Codes 163
4.4 Alternative Convolutional Code Representations 163
4.4.1 Convolutional Codes as Semi-Infinite Linear Codes 164
4.4.2 Graphical Representations for Convolutional Code Encoders 170
4.5 Trellis-Based Decoders 171
4.5.1 MLSD and the Viterbi Algorithm 172
4.5.2 Differential Viterbi Decoding 177
4.5.3 Bit-wise MAP Decoding and the BCJR Algorithm 180
4.6 Performance Estimates for Trellis-Based Decoders 187
4.6.1 ML Decoder Performance for Block Codes 187
4.6.2 Weight Enumerators for Convolutional Codes 189
4.6.3 ML Decoder Performance for Convolutional Codes 193
Problems 195
References 200
5 Low-Density Parity-Check Codes 201
5.1 Representations of LDPC Codes 201
5.1.1 Matrix Representation 201
5.1.2 Graphical Representation 202
5.2 Classifications of LDPC Codes 205
5.2.1 Generalized LDPC Codes 207
5.3 Message Passing and the Turbo Principle 208
5.4 The Sum-Product Algorithm 213
5.4.1 Overview 213
5.4.2 Repetition Code MAP Decoder and APP Processor 216
5.4.3 Single-Parity-Check Code MAP Decoder and APP Processor 217
5.4.4 The Gallager SPA Decoder 218
5.4.5 The Box-Plus SPA Decoder 222
5.4.6 Comments on the Performance of the SPA Decoder 225
5.5 Reduced-Complexity SPA Approximations 226
5.5.1 The Min-Sum Decoder 226
5.5.2 The Attenuated and Offset Min-Sum Decoders 229
5.5.3 The Min-Sum-with-Correction Decoder 231
5.5.4 The Approximate Min* Decoder 233
5.5.5 The Richardson/Novichkov Decoder 234
5.5.6 The Reduced-Complexity Box-Plus Decoder 236
5.6 Iterative Decoders for Generalized LDPC Codes 241
5.7 Decoding Algorithms for the BEC and the BSC 243
5.7.1 Iterative Erasure Filling for the BEC 243
5.7.2 ML Decoder for the BEC 244
5.7.3 Gallager’s Algorithm A and Algorithm B for the BSC 246
5.7.4 The Bit-Flipping Algorithm for the BSC 247
5.8 Concluding Remarks 248
Problems 248
References 254
6 Computer-Based Design of LDPC Codes 257
6.1 The Original LDPC Codes 257
6.1.1 Gallager Codes 257
6.1.2 MacKay Codes 258
6.2 The PEG and ACE Code-Design Algorithms 259
6.2.1 The PEG Algorithm 259
6.2.2 The ACE Algorithm 260
6.3 Protograph LDPC Codes 261
6.3.1 Decoding Architectures for Protograph Codes 264
6.4 Multi-Edge-Type LDPC Codes 265
6.5 Single-Accurnulator-Based LDPC Codes 266
6.5.1 Repeat -Accumulate Codes 267
6.5.2 Irregular Repeat-Accumulate Codes 267
6.5.3 Generalized Accumulator LDPC Codes 277
6.6 Double-Accumulator-Based LDPC Codes 277
6.6.1 Irregular Repeat -Accumulate-Accumulate Codes 278
6.6.2 Accumulate-Repeat-Accumulate Codes 279
6.7 Accurnulator-Based Codes in Standards 285
6.8 Generalized LDPC Codes 287
6.8.1 A Rate-1/2 G-LDPC Code 290
Problems 292
References 295
7 Turbo Codes 298
7.1 Parallel-Concatenated Convolutional Codes 298
7.1.1 Critical Properties of RSC Codes 299
7.1.2 Critical Properties of the Interleaver 300
7.1.3 The Puncturer 301
7.1.4 Performance Estimate on the BI-AWGNC 301
7.2 The PCCC Iterative Decoder 306
7.2.1 Overview of the Iterative Decoder 308
7.2.2 Decoder Details 309
7.2.3 Summary of the PCCC Iterative Decoder 313
7.2.4 Lower-Complexity Approximations 316
7.3 Serial-Concatenated Convolutional Codes 320
7.3.1 Performance Estimate on the BI-AWGNC 320
7.3.2 The SCCC Iterative Decoder 323
7.3.3 Summary of the SCCC Iterative Decoder 325
7.4 Turbo Product Codes 328
7.4.1 Turbo Decoding of Product Codes 330
Problems 335
References 337
8 Ensemble Enumerators for Turbo and LDPC Codes 339
8.1 Notation 340
8.2 Ensemble Enumerators for Parallel-Concatenated Codes 343
8.2.1 Preliminaries 343
8.2.2 PCCC Ensemble Enumerators 345
8.3 Ensemble Enumerators for Serial-Concatenated Codes 356
8.3.1 Preliminaries 356
8.3.2 SCCC Ensemble Enumerators 358
8.4 Enumerators for Selected Accumulator-Based Codes 362
8.4.1 Enumerators for Repeat-Accumulate Codes 362
8.4.2 Enumerators for Irregular Repeat-Accumulate Codes 364
8.5 Enumerators for Protograph-Based LDPC Codes 367
8.5.1 Finite-Length Ensemble Weight Enumerators 368
8.5.2 Asymptotic Ensemble Weight Enumerators 371
8.5.3 On the Complexity of Computing Asymptotic Ensemble Enumerators 376
8.5.4 Ensemble Trapping-Set Enumerators 379
Problems 383
References 386
9 Ensemble Decoding Thresholds for LDPC and Turbo Codes 388
9.1 Density Evolution for Regular LDPC Codes 388
9.2 Density Evolution for Irregular LDPC Codes 394
9.3 Quantized Density Evolution 399
9.4 The Gaussian Approximation 402
9.4.1 GA for Regular LDPC Codes 403
9.4.2 GA for Irregular LDPC Codes 404
9.5 On the Universality of LDPC Codes 407
9.6 EXIT Charts for LDPC Codes 412
9.6.1 EXIT Charts for Regular LDPC Codes 414
9.6.2 EXIT Charts for Irregular LDPC Codes 416
9.6.3 EXIT Technique for Protograph-Based Codes 417
9.7 EXIT Charts for Turbo Codes 420
9.8 The Area Property for EXIT Charts 424
9.8.1 Serial-Concatenated Codes 424
9.8.2 LDPC Codes 425
Problems 426
References 428
10 Finite-Geometry LDPC Codes 430
10.1 Construction of LDPC Codes Based on Lines of Euclidean Geometries 430
10.1.1 A Class of Cyclic EG-LDPC Codes 432
10.1.2 A Class of Quasi-Cyclic EG-LDPC Codes 434
10.2 Construction of LDPC Codes Based on the Parallel Bundles of Lines in Euclidean Geometries 436
10.3 Construction of LDPC Codes Based on Decomposition of Euclidean Geometries 439
10.4 Construction of EG-LDPC Codes by Masking 444
10.4.1 Masking 445
10.4.2 Regular Masking 446
10.4.3 Irregular Masking 447
10.5 Construction of QC-EG-LDPC Codes by Circulant Decomposition 450
10.6 Construction of Cyclic and QC-LDPC Codes Based on Projective Geometries 455
10.6.1 Cyclic PG-LDPC Codes 455
10.6.2 Quasi-Cyclic PG-LDPC Codes 458
10.7 One-Step Majority-Logic and Bit-Flipping Decoding Algorithms for FG-LDPC Codes 460
10.7.1 The OSMLG Decoding Algorithm for LDPC Codes over the BSC 461
10.7.2 The BF Algorithm for Decoding LDPC Codes over the BSC 468
10.8 Weighted BF Decoding：Algorithm 1 469
10.9 Weighted BF Decoding：Algorithms 2 and 3 472
10.10 Concluding Remarks 477
Problems 477
References 481
11 Constructions of LDPC Codes Based on Finite Fields 484
11.1 Matrix Dispersions of Elements of a Finite Field 484
11.2 A General Construction of QC-LDPC Codes Based on Finite Fields 485
11.3 Construction of QC-LDPC Codes Based on the Minimum-Weight Codewords of an RS Code with Two Information Symbols 487
11.4 Construction of QC-LDPC Codes Based on the Universal Parity-Check Matrices of a Special Subclass of RS Codes 495
11.5 Construction of QC-LDPC Codes Based on Subgroups of a Finite Field 501
11.5.1 Construction of QC-LDPC Codes Based on Subgroups of the Additive Group of a Finite Field 501
11.5.2 Construction of QC-LDPC Codes Based on Subgroups of the Multiplicative Group of a Finite Field 503
11.6 Construction of QC-LDPC Code Based on the Additive Group of a Prime Field 506
11.7 Construction of QC-LDPC Codes Based on Primitive Elements of a Field 510
11.8 Construction of QC-LDPC Codes Based on the Intersecting Bundles of Lines of Euclidean Geometries 512
11.9 A Class of Structured RS-Based LDPC Codes 516
Problems 520
References 522
12 LDPC Codes Based on Combinatorial Designs，Graphs，and Superposition 523
12.1 Balanced Incomplete Block Designs and LDPC Codes 523
12.2 Class-Ⅰ Bose BIBDs and QC-LDPC Codes 524
12.2.1 Class-Ⅰ Bose BIBDs 525
12.2.2 Type-Ⅰ Class-Ⅰ Bose BIBD-LDPC Codes 525
12.2.3 Type-Ⅱ Class-Ⅰ Bose BIBD-LDPC Codes 527
12.3 Class-Ⅱ Bose BIBDs and QC-LDPC Codes 530
12.3.1 Class-Ⅱ Bose BIBDs 531
12.3.2 Type-Ⅰ Class-Ⅱ Bose BIBD-LDPC Codes 531
12.3.3 Type-Ⅱ Class-Ⅱ QC-BIBD-LDPC Codes 533
12.4 Construction of Type-Ⅱ Bose BIBD-LDPC Codes by Dispersion 536
12.5 A Trellis-Based Construction of LDPC Codes 537
12.5.1 A Trellis-Based Method for Removing Short Cycles from a Bipartite Graph 538
12.5.2 Code Construction 540
12.6 Construction of LDPC Codes Based on Progressive Edge-Growth Tanner Graphs 542
12.7 Construction of LDPC Codes by Superposition 546
12.7.1 A General Superposition Construction of LDPC Codes 546
12.7.2 Construction of Base and Constituent Matrices 548
12.7.3 Superposition Construction of Product LDPC Codes 552
12.8 Two Classes of LDPC Codes with Girth 8 554
Problems 557
References 559
13 LDPC Codes for Binary Erasure Channels 561
13.1 Iterative Decoding of LDPC Codes for the BEC 561
13.2 Random-Erasure-Correction Capability 563
13.3 Good LDPC Codes for the BEC 565
13.4 Correction of Erasure-Bursts 570
13.5 Erasure-Burst-Correction Capabilities of Cyclic Finite-Geometry and Superposition LDPC Codes 573
13.5.1 Erasure-Burst-Correction with Cyclic Finite-Geometry LDPC Codes 573
13.5.2 Erasure-Burst-Correction with Superposition LDPC Codes 574
13.6 Asymptotically Optimal Erasure-Burst-Correction QC-LDPC Codes 575
13.7 Construction of QC-LDPC Codes by Array Dispersion 580
13.8 Cyclic Codes for Correcting Bursts of Erasures 586
Problems 589
References 590
14 Nonbinary LDPC Codes 592
14.1 Definitions 592
14.2 Decoding of Nonbinary LDPC Codes 593
14.2.1 The QSPA 593
14.2.2 The FFT-QSPA 598
14.3 Construction of Nonbinary LDPC Codes Based on Finite Geometries 600
14.3.1 A Class of q m-ary Cyclic EG-LDPC Codes 601
14.3.2 A Class of Nonbinary Quasi-Cyclic EG-LDPC Codes 607
14.3.3 A Class of Nonbinary Regular EG-LDPC Codes 610
14.3.4 Nonbinary LDPC Code Constructions Based on Projective Geometries 611
14.4 Constructions of Nonbinary QC-LDPC Codes Based on Finite Fields 614
14.4.1 Dispersion of Field Elements into Nonbinary Circulant Permutation Matrices 615
14.4.2 Construction of Nonbinary QC-LDPC Codes Based on Finite Fields 615
14.4.3 Construction of Nonbinary QC-LDPC Codes by Masking 617
14.4.4 Construction of Nonbinary QC-LDPC Codes by Array Dispersion 618
14.5 Construction of QC-EG-LDPC Codes Based on Parallel Flats in Euclidean Geometries and Matrix Dispersion 620
14.6 Construction of Nonbinary QC-EG-LDPC Codes Based on Intersecting Flats in Euclidean Geometries and Matrix Dispersion 624
14.7 Superposition-Dispersion Construction of Nonbinary QC-LDPC Codes 628
Problems 631
References 633
15 LDPC Code Applications and Advanced Topics 636
15.1 LDPC-Coded Modulation 636
15.1.1 Design Based on EXIT Charts 638
15.2 Turbo Equalization and LDPC Code Design for ISI Channels 644
15.2.1 Turbo Equalization 644
15.2.2 LDPC Code Design for ISI Channels 648
15.3 Estimation of LDPC Error Floors 651
15.3.1 The Error-Floor Phenomenon and Trapping Sets 651
15.3.2 Error-Floor Estimation 654
15.4 LDPC Decoder Design for Low Error Floors 657
15.4.1 Codes Under Study 659
15.4.2 The Bi-Mode Decoder 661
15.4.3 Concatenation and Bit-Pinning 666
15.4.4 Generalized-LDPC Decoder 668
15.4.5 Remarks 670
15.5 LDPC Convolutional Codes 670
15.6 Fountain Codes 672
15.6.1 Tornado Codes 673
15.6.2 Luby Transform Codes 674
15.6.3 Raptor Codes 675
Problems 676
References 677
Index 681