Fundamentals of Classical and Modern Error-Correcting Codes

Cover
Half-title
Title page
Copyright information
Contents
List of Figures
List of Tables
Preface
Acknowledgments
1 Coding for Reliable Digital Information Transmission and Storage
1.1 Introduction
1.2 Categories of Error-Correcting Codes
1.3 Modulation and Demodulation
1.4 Hard-Decision and Soft-Decision Decodings
1.5 Maximum A Posteriori and Maximum Likelihood Decodings
1.6 Channel Capacity on Transmission Rate
1.7 Classification of Channel Errors
1.8 Error-Control Strategies
1.9 Measures of Performance
1.10 Contents of the Book
References
2 Some Elements of Modern Algebra and Graphs
2.1 Groups
2.1.1 Basic Definitions and Concepts
2.1.2 Finite Groups
2.1.3 Subgroups and Cosets
2.2 Finite Fields
2.2.1 Basic Definitions and Concepts
2.2.2 Prime Fields
2.2.3 Finite Fields with Orders of Prime Powers
2.3 Polynomials over Galois Field GF(2)
2.4 Construction of Galois Field GF(2[sup(m)])
2.5 Basic Properties and Structures of Galois Field GF(2[sup(m)])
2.6 Computations over Galois Field GF(2[sup(m)])
2.7 A General Construction of Finite Fields
2.8 Vector Spaces over Finite Fields
2.8.1 Basic Definitions and Concepts
2.8.2 Vector Spaces over Binary Field GF(2)
2.8.3 Vector Spaces over Nonbinary Field GF(q)
2.9 Matrices over Finite Fields
2.9.1 Concepts of Matrices over GF(2)
2.9.2 Operations of Matrices over GF(2)
2.9.3 Matrices over Nonbinary Field GF(q)
2.9.4 Determinants
2.10 Graphs
2.10.1 Basic Definitions and Concepts
2.10.2 Bipartite Graphs
Problems
References
3 Linear Block Codes
3.1 Definitions
3.2 Generator and Parity-Check Matrices
3.3 Systematic Linear Block Codes
3.4 Error Detection with Linear Block Codes
3.5 Syndrome and Error Patterns
3.6 Weight Distribution and Probability of Undetected Error
3.7 Minimum Distance of Linear Block Codes
3.8 Decoding of Linear Block Codes
3.9 Standard Array for Decoding Linear Block Codes
3.9.1 A Standard Array Decoding
3.9.2 Syndrome Decoding
3.10 Shortened and Extended Codes
3.11 Nonbinary Linear Block Codes
Problems
References
4 Binary Cyclic Codes
4.1 Characterization of Cyclic Codes
4.2 Structural Properties of Cyclic Codes
4.3 Existence of Cyclic Codes
4.4 Generator and Parity-Check Matrices of Cyclic Codes
4.5 Encoding of Cyclic Codes in Systematic Form
4.6 Syndrome Calculation and Error Detection
4.7 General Decoding of Cyclic Codes
4.8 Error-Trapping Decoding for Cyclic Codes
4.9 Shortened Cyclic Codes
4.10 Hamming Codes
4.11 Cyclic Redundancy Check Codes
4.12 Quadratic Residue Codes
4.13 Quasi-cyclic Codes
4.13.1 Definitions and Fundamental Structures
4.13.2 Generator and Parity-Check Matrices in Systematic Circulant Form
4.13.3 Encoding of QC Codes
4.13.4 Generator and Parity-Check Matrices in Semi-systematic Circulant Form
4.13.5 Shortened QC Codes
4.14 Nonbinary Cyclic Codes
4.15 Remarks
Problems
References
5 BCH Codes
5.1 Primitive Binary BCH Codes
5.2 Structural Properties of BCH Codes
5.3 Minimum Distance of BCH Codes
5.4 Syndrome Computation and Error Detection
5.5 Syndromes and Error Patterns
5.6 Error-Location Polynomials of BCH Codes
5.7 A Procedure for Decoding BCH Codes
5.8 Berlekamp–Massey Iterative Algorithm
5.9 Simplification of Decoding Binary BCH Codes
5.10 Finding Error Locations and Error Correction
5.11 Nonprimitive Binary BCH Codes
5.12 Remarks
Problems
References
6 Nonbinary BCH Codes and Reed–Solomon Codes
6.1 Nonbinary Primitive BCH Codes
6.2 Decoding Steps of Nonbinary BCH Codes
6.3 Syndrome and Error Pattern of Nonbinary BCH Codes
6.4 Error-Location Polynomial of Nonbinary BCH Codes
6.5 Error-Value Evaluator
6.6 Decoding of Nonbinary BCH Codes
6.7 Key-Equation
6.8 Reed–Solomon Codes
6.8.1 Primitive Reed–Solomon Codes
6.8.2 Nonprimitive Reed–Solomon Codes
6.9 Decoding Reed–Solomon Codes with Berlekamp–Massey Iterative Algorithm
6.10 Euclidean Algorithm for Finding GCD of Two Polynomials
6.11 Solving the Key-Equation with Euclidean Algorithm
6.12 Weight Distribution and Probability of Undetected Error of Reed–Solomon Codes
6.13 Remarks
Problems
References
7 Finite Geometries, Cyclic Finite-Geometry Codes, and Majority-Logic Decoding
7.1 Fundamental Concepts of Finite Geometries
7.2 Majority-Logic Decoding of Finite-Geometry Codes
7.3 Euclidean Geometries over Finite Fields
7.3.1 Basic Concepts and Properties
7.3.2 A Realization of Euclidean Geometries
7.3.3 Subgeometries of Euclidean Geometries
7.4 Cyclic Codes Constructed Based on Euclidean Geometries
7.4.1 Cyclic Codes on Two-Dimensional Euclidean Geometries
7.4.2 Cyclic Codes on Multi-Dimensional Euclidean Geometries
7.5 Projective Geometries
7.6 Cyclic Codes Constructed Based on Projective Geometries
7.7 Remarks
Problems
References
8 Reed–Muller Codes
8.1 A Review of Euclidean Geometries over GF(2)
8.2 Constructing RM Codes from Euclidean Geometries over GF(2)
8.3 Encoding of RM Codes
8.4 Successive Retrieval of Information Symbols
8.5 Majority-Logic Decoding through Successive Cancellations
8.6 Cyclic RM Codes
8.7 Remarks
Problems
References
9 Some Coding Techniques
9.1 Interleaving
9.2 Direct Product
9.3 Concatenation
9.3.1 Type-1 Serial Concatenation
9.3.2 Type-2 Serial Concatenation
9.3.3 Parallel Concatenation
9.4 |u|u+v|-Construction
9.5 Kronecker Product
9.6 Automatic-Repeat-Request Schemes
9.6.1 Basic ARQ Schemes
9.6.2 Mixed-Mode SR-ARQ Schemes
9.6.3 Hybrid ARQ Schemes
Problems
References
10 Correction of Error-Bursts and Erasures
10.1 Definitions and Structures of Burst-Error-Correcting Codes
10.2 Decoding of Single Burst-Error-Correcting Cyclic Codes
10.3 Fire Codes
10.4 Short Optimal and Nearly Optimal Single Burst-Error-Correcting Cyclic Codes
10.5 Interleaved Codes for Correcting Long Error-Bursts
10.6 Product Codes for Correcting Error-Bursts
10.7 Phased-Burst-Error-Correcting Codes
10.7.1 Interleaved and Product Codes
10.7.2 Codes Derived from RS Codes
10.7.3 Burton Codes
10.8 Characterization and Correction of Erasures
10.8.1 Correction of Errors and Erasures over BSECs
10.8.2 Correction of Erasures over BECs
10.8.3 RM Codes for Correcting Random Erasures
10.9 Correcting Erasure-Bursts over BBECs
10.9.1 Cyclic Codes for Correcting Single Erasure-Burst
10.9.2 Correction of Multiple Random Erasure-Bursts
10.10 RS Codes for Correcting Random Errors and Erasures
Problems
References
11 Introduction to Low-Density Parity-Check Codes
11.1 Definitions and Basic Concepts
11.2 Graphical Representation of LDPC Codes
11.3 Original Construction of LDPC Codes
11.3.1 Gallager Codes
11.3.2 MacKay Codes
11.4 Decoding of LDPC Codes
11.4.1 One-Step Majority-Logic Decoding
11.4.2 Bit-Flipping Decoding
11.4.3 Weighted One-Step Majority-Logic and Bit-Flipping Decodings
11.5 Iterative Decoding Based on Belief-Propagation
11.5.1 Message Passing
11.5.2 Sum-Product Algorithm
11.5.2.1 Applications of the SPA to BI-AWGN Channel, BSC, and BEC
11.5.3 Min-Sum Algorithm
11.6 Error Performance of LDPC Codes with Iterative Decoding
11.6.1 Error-Floor
11.6.2 Decoding Threshold
11.6.3 Overall Performance and Its Determinating Factors
11.7 Iterative Decoding of LDPC Codes over BECs
11.8 Categories of LDPC Code Constructions
11.9 Nonbinary LDPC Codes
Problems
References
12 Cyclic and Quasi-cyclic LDPC Codes on Finite Geometries
12.1 Cyclic-FG-LDPC Codes
12.2 A Complexity-Reduced Iterative Algorithm for Decoding Cyclic-FG-LDPC Codes
12.3 QC-EG-LDPC Codes
12.4 QC-PG-LDPC Codes
12.5 Construction of QC-EG-LDPC Codes by CPM-Dispersion
12.6 Masking Techniques
12.7 Construction of QC-FG-LDPC Codes by Circulant-Decomposition
12.8 A Complexity-Reduced Iterative Algorithm for Decoding QC-FG-LDPC Codes
12.9 Remarks
Problems
References
13 Partial Geometries and Their Associated QC-LDPC Codes
13.1 CPM-Dispersions of Finite-Field Elements
13.2 Matrices with RC-Constrained Structure
13.3 Definitions and Structural Properties of Partial Geometries
13.4 Partial Geometries Based on Prime-Order Cyclic Subgroups of Finite Fields and Their Associated QC-LDPC Codes
13.5 Partial Geometries Based on Prime Fields and Their Associated QC-LDPC Codes
13.6 Partial Geometries Based on Balanced Incomplete Block Designs and Their Associated QC-LDPC Codes
13.6.1 BIBDs and Partial Geometries
13.6.2 Class-1 Bose (N, M, t, r, 1)-BIBDs
13.6.3 Class-2 Bose (N, M, t, r, 1)-BIBDs
13.7 Remarks
Problems
References
14 Quasi-cyclic LDPC Codes Based on Finite Fields
14.1 Construction of QC-LDPC Codes Based on CPM-Dispersion
14.2 Construction of Type-I QC-LDPC Codes Based on Two Subsets of a Finite Field
14.3 Construction of Type-II QC-LDPC Codes Based on Two Subsets of a Finite Field
14.4 Masking-Matrix Design
14.4.1 Type-1 Design
14.4.2 Type-2 Design
14.4.3 Type-3 Design
14.5 A Search Algorithm for 2 × 2/3 × 3 SM-Constrained Base Matrices for Constructing Rate-1/2 QC-LDPC Codes
14.6 Designs of 2 × 2 SM-Constrained RS Base Matrices
14.7 Construction of Type-III QC-LDPC Codes Based on RS Codes
14.8 Construction of QC-RS-LDPC Codes with Girths at Least 8
14.9 A Special Class of QC-RS-LDPC Codes with Girth 8
14.10 Optimal Codes for Correcting Two Random CPM-Phased Erasure-Bursts
14.11 Globally Coupled LDPC Codes
14.12 Remarks
Problems
References
15 Graph-Theoretic LDPC Codes
15.1 Protograph-Based LDPC Codes
15.2 A Matrix-Theoretic Method for Constructing Protograph-Based LDPC Codes
15.3 Masking Matrices as Protomatrices
15.4 LDPC Codes on Progressive Edge-Growth Algorithms
15.5 Remarks
Problems
References
16 Collective Encoding and Soft-Decision Decoding of Cyclic Codes of Prime Lengths in Galois Fourier Transform Domain
16.1 Cyclic Codes of Prime Lengths and Their Hadamard Equivalents
16.2 Composing, Cascading, and Interleaving a Cyclic Code of Prime Length and Its Hadamard Equivalents
16.2.1 Composing
16.2.2 Cascading and Interleaving
16.3 Galois Fourier Transform of ICC Codes
16.4 Structural Properties of GFT-ICC Codes
16.5 Collective Encoding of GFT-ICC-LDPC Codes
16.6 Collective Iterative Soft-Decision Decoding of GFT-ICC-LDPC Codes
16.7 Analysis of the GFT-ISDD Scheme
16.7.1 Performance Measurements
16.7.2 Complexity
16.8 Joint Decoding of RS Codes with GFT-ISDD Scheme
16.9 Joint Decoding of BCH Codes with GFT-ISDD Scheme
16.10 Joint Decoding of QR Codes with GFT-ISDD Scheme
16.11 Code Shortening and Rate Reduction
16.11.1 Shortened GFT-ICC Codes
16.11.2 Reductions of Code Rate
16.12 Erasure Correction of GFT-ICC-RS-LDPC Codes
16.13 Remarks
Problems
References
17 Polar Codes
17.1 Kronecker Matrices and Their Structural Properties
17.2 Kronecker Mappings and Their Logical Implementations
17.3 Kronecker Vector Spaces and Codes
17.4 Definition and Polarized Encoding of Polar Codes
17.5 Successive Information Retrieval from a Polarized Codeword
17.6 Channel Polarization
17.6.1 Some Elements of Information Theory
17.6.2 Polarization Process
17.6.3 Channel Polarization Theorem
17.7 Construction of Polar Codes
17.8 Successive Cancellation Decoding
17.8.1 SC Decoding of Polar Codes of Length N = 2
17.8.2 SC Decoding of Polar Codes of Length N = 4
17.8.3 SC Decoding of Polar Codes of Length N = 2
17.9 Remarks
Problems
References
Appendix A Factorization of X[sup(n)] +1 over GF(2)
Appendix B A 2 2/3 3 SM-Constrained Masked Matrix Search Algorithm
Appendix C Proof of Theorem 14.4
Appendix D The 2 × 2 CPM-Array Cycle Structure of the Tanner Graph of C[sub(RS,n)](2,n)
Appendix E Iterative Decoding Algorithm for Nonbinary LDPC Codes
E.1 Introduction
E.2 Algorithm Derivation
E.2.1 VN Update
E.2.2 CN Update: Complex Version
E.2.3 CN Update: Fast Hadamard Transform Version
E.3 The Nonbinary LDPC Decoding Algorithm
Index