You are previewing Channel Codes.
O'Reilly logo
Channel Codes

Book Description

Channel coding lies at the heart of digital communication and data storage, and this detailed introduction describes the core theory as well as decoding algorithms, implementation details, and performance analyses. Known for their writing clarity, Professors Ryan and Lin provide the latest information on modern channel codes, including turbo and low-density parity-check (LDPC) codes. They also present detailed coverage of BCH codes, Reed-Solomon codes, convolutional codes, finite geometry codes, and product codes, providing a one-stop resource for both classical and modern coding techniques. Assuming no prior knowledge in the field of channel coding, the opening chapters begin with basic theory to introduce newcomers to the subject. Later chapters then extend to advanced topics such as code ensemble performance analyses and algebraic code design. 250 varied and stimulating end-of-chapter problems are also included to test and enhance learning, making this an essential resource for students and practitioners alike.

Table of Contents

  1. Cover
  2. Title Page
  3. Copyright Page
  4. Contents
  5. Preface
  6. 1 Coding and Capacity
    1. 1.1 Digital Data Communication and Storage
    2. 1.2 Channel-Coding Overview
    3. 1.3 Channel-Code Archetype: The (7,4) Hamming Code
    4. 1.4 Design Criteria and Performance Measures
    5. 1.5 Channel-Capacity Formulas for Common Channel Models
      1. 1.5.1 Capacity for Binary-Input Memoryless Channels
      2. 1.5.2 Coding Limits for M-ary-Input Memoryless Channels
      3. 1.5.3 Coding Limits for Channels with Memory
    6. Problems
    7. References
  7. 2 Finite Fields, Vector Spaces, Finite Geometries, and Graphs
    1. 2.1 Sets and Binary Operations
    2. 2.2 Groups
      1. 2.2.1 Basic Concepts of Groups
      2. 2.2.2 Finite Groups
      3. 2.2.3 Subgroups and Cosets
    3. 2.3 Fields
      1. 2.3.1 Definitions and Basic Concepts
      2. 2.3.2 Finite Fields
    4. 2.4 Vector Spaces
      1. 2.4.1 Basic Definitions and Properties
      2. 2.4.2 Linear Independence and Dimension
      3. 2.4.3 Finite Vector Spaces over Finite Fields
      4. 2.4.4 Inner Products and Dual Spaces
      5. 2.5 Polynomials over Finite Fields
    5. 2.6 Construction and Properties of Galois Fields
      1. 2.6.1 Construction of Galois Fields
      2. 2.6.2 Some Fundamental Properties of Finite Fields
      3. 2.6.3 Additive and Cyclic Subgroups
    6. 2.7 Finite Geometries
      1. 2.7.1 Euclidean Geometries
      2. 2.7.2 Projective Geometries
    7. 2.8 Graphs
      1. 2.8.1 Basic Concepts
      2. 2.8.2 Paths and Cycles
      3. 2.8.3 Bipartite Graphs
    8. Problems
    9. References
    10. Appendix A
  8. 3 Linear Block Codes
    1. 3.1 Introduction to Linear Block Codes
      1. 3.1.1 Generator and Parity-Check Matrices
      2. 3.1.2 Error Detection with Linear Block Codes
      3. 3.1.3 Weight Distribution and Minimum Hamming Distance of a Linear Block Code
      4. 3.1.4 Decoding of Linear Block Codes
    2. 3.2 Cyclic Codes
    3. 3.3 BCH Codes
    4. 3.3.1 Code Construction
      1. 3.3.2 Decoding
      2. 3.4 Nonbinary Linear Block Codes and Reed–Solomon Codes
    5. 3.5 Product, Interleaved, and Concatenated Codes
      1. 3.5.1 Product Codes
      2. 3.5.2 Interleaved Codes
      3. 3.5.3 Concatenated Codes
    6. 3.6 Quasi-Cyclic Codes
    7. 3.7 Repetition and Single-Parity-Check Codes
    8. Problems
    9. References
  9. 4 Convolutional Codes
    1. 4.1 The Convolutional Code Archetype
    2. 4.2 Algebraic Description of Convolutional Codes
    3. 4.3 Encoder Realizations and Classifications
      1. 4.3.1 Choice of Encoder Class
      2. 4.3.2 Catastrophic Encoders
      3. 4.3.3 Minimal Encoders
      4. 4.3.4 Design of Convolutional Codes
    4. 4.4 Alternative Convolutional Code Representations
      1. 4.4.1 Convolutional Codes as Semi-Infinite Linear Codes
      2. 4.4.2 Graphical Representations for Convolutional Code Encoders
    5. 4.5 Trellis-Based Decoders
      1. 4.5.1 MLSD and the Viterbi Algorithm
      2. 4.5.2 Differential Viterbi Decoding
      3. 4.5.3 Bit-wise MAP Decoding and the BCJR Algorithm
    6. 4.6 Performance Estimates for Trellis-Based Decoders
      1. 4.6.1 ML Decoder Performance for Block Codes
      2. 4.6.2 Weight Enumerators for Convolutional Codes
      3. 4.6.3 ML Decoder Performance for Convolutional Codes
    7. Problems
    8. References
  10. 5 Low-Density Parity-Check Codes
    1. 5.1 Representations of LDPC Codes
      1. 5.1.1 Matrix Representation
      2. 5.1.2 Graphical Representation
    2. 5.2 Classifications of LDPC Codes 5.2.1 Generalized LDPC Codes
    3. 5.3 Message Passing and the Turbo Principle
    4. 5.4 The Sum–Product Algorithm
      1. 5.4.1 Overview
      2. 5.4.2 Repetition Code MAP Decoder and APP Processor
      3. 5.4.3 Single-Parity-Check Code MAP Decoder and APP Processor
      4. 5.4.4 The Gallager SPA Decoder
      5. 5.4.5 The Box-Plus SPA Decoder
      6. 5.4.6 Comments on the Performance of the SPA Decoder
    5. 5.5 Reduced-Complexity SPA Approximations
      1. 5.5.1 The Min-Sum Decoder
      2. 5.5.2 The Attenuated and Offset Min-Sum Decoders
      3. 5.5.3 The Min-Sum-with-Correction Decoder
      4. 5.5.4 The Approximate Min* Decoder
      5. 5.5.5 The Richardson/Novichkov Decoder
      6. 5.5.6 The Reduced-Complexity Box-Plus Decoder
    6. 5.6 Iterative Decoders for Generalized LDPC Codes
    7. 5.7 Decoding Algorithms for the BEC and the BSC
      1. 5.7.1 Iterative Erasure Filling for the BEC
      2. 5.7.2 ML Decoder for the BEC
      3. 5.7.3 Gallager’s Algorithm A and Algorithm B for the BSC
      4. 5.7.4 The Bit-Flipping Algorithm for the BSC
    8. 5.8 Concluding Remarks
    9. Problems
    10. References
  11. 6 Computer-Based Design of LDPC Codes
    1. 6.1 The Original LDPC Codes
      1. 6.1.1 Gallager Codes
      2. 6.1.2 MacKay Codes
    2. 6.2 The PEG and ACE Code-Design Algorithms
      1. 6.2.1 The PEG Algorithm
      2. 6.2.2 The ACE Algorithm
    3. 6.3 Protograph LDPC Codes
      1. 6.3.1 Decoding Architectures for Protograph Codes
    4. 6.4 Multi-Edge-Type LDPC Codes
    5. 6.5 Single-Accumulator-Based LDPC Codes
      1. 6.5.1 Repeat–Accumulate Codes
      2. 6.5.2 Irregular Repeat–Accumulate Codes
      3. 6.5.3 Generalized Accumulator LDPC Codes
    6. 6.6 Double-Accumulator-Based LDPC Codes
      1. 6.6.1 Irregular Repeat–Accumulate–Accumulate Codes
      2. 6.6.2 Accumulate–Repeat–Accumulate Codes
    7. 6.7 Accumulator-Based Codes in Standards
    8. 6.8 Generalized LDPC Codes
      1. 6.8.1 A Rate-1/2 G-LDPC Code
    9. Problems
    10. References
  12. 7 Turbo Codes
    1. 7.1 Parallel-Concatenated Convolutional Codes
      1. 7.1.1 Critical Properties of RSC Codes
      2. 7.1.2 Critical Properties of the Interleaver
      3. 7.1.3 The Puncturer
      4. 7.1.4 Performance Estimate on the BI-AWGNC
    2. 7.2 The PCCC Iterative Decoder
      1. 7.2.1 Overview of the Iterative Decoder
      2. 7.2.2 Decoder Details
      3. 7.2.3 Summary of the PCCC Iterative Decoder
      4. 7.2.4 Lower-Complexity Approximations
    3. 7.3 Serial-Concatenated Convolutional Codes
      1. 7.3.1 Performance Estimate on the BI-AWGNC
      2. 7.3.2 The SCCC Iterative Decoder
      3. 7.3.3 Summary of the SCCC Iterative Decoder
    4. 7.4 Turbo Product Codes
      1. 7.4.1 Turbo Decoding of Product Codes
    5. Problems
    6. References
  13. 8 Ensemble Enumerators for Turbo and LDPC Codes
    1. 8.1 Notation
    2. 8.2 Ensemble Enumerators for Parallel-Concatenated Codes
      1. 8.2.1 Preliminaries
      2. 8.2.2 PCCC Ensemble Enumerators
    3. 8.3 Ensemble Enumerators for Serial-Concatenated Codes
      1. 8.3.1 Preliminaries
      2. 8.3.2 SCCC Ensemble Enumerators
    4. 8.4 Enumerators for Selected Accumulator-Based Codes
      1. 8.4.1 Enumerators for Repeat–Accumulate Codes
      2. 8.4.2 Enumerators for Irregular Repeat–Accumulate Codes
    5. 8.5 Enumerators for Protograph-Based LDPC Codes
      1. 8.5.1 Finite-Length Ensemble Weight Enumerators
      2. 8.5.2 Asymptotic Ensemble Weight Enumerators
      3. 8.5.3 On the Complexity of Computing Asymptotic Ensemble Enumerators
      4. 8.5.4 Ensemble Trapping-Set Enumerators
    6. Problems
    7. References
  14. 9 Ensemble Decoding Thresholds for LDPC and Turbo Codes
    1. 9.1 Density Evolution for Regular LDPC Codes
    2. 9.2 Density Evolution for Irregular LDPC Codes
    3. 9.3 Quantized Density Evolution
    4. 9.4 The Gaussian Approximation
      1. 9.4.1 GA for Regular LDPC Codes
      2. 9.4.2 GA for Irregular LDPC Codes
    5. 9.5 On the Universality of LDPC Codes
    6. 9.6 EXIT Charts for LDPC Codes
      1. 9.6.1 EXIT Charts for Regular LDPC Codes
      2. 9.6.2 EXIT Charts for Irregular LDPC Codes
      3. 9.6.3 EXIT Technique for Protograph-Based Codes
    7. 9.7 EXIT Charts for Turbo Codes
    8. 9.8 The Area Property for EXIT Charts
      1. 9.8.1 Serial-Concatenated Codes
      2. 9.8.2 LDPC Codes
    9. Problems
    10. References
  15. 10 Finite-Geometry LDPC Codes
    1. 10.1 Construction of LDPC Codes Based on Lines of Euclidean Geometries
      1. 10.1.1 A Class of Cyclic EG-LDPC Codes
      2. 10.1.2 A Class of Quasi-Cyclic EG-LDPC Codes
    2. 10.2 Construction of LDPC Codes Based on the Parallel Bundles of Lines in Euclidean Geometries
    3. 10.3 Construction of LDPC Codes Based on Decomposition of Euclidean Geometries
    4. 10.4 Construction of EG-LDPC Codes by Masking
      1. 10.4.1 Masking
      2. 10.4.2 Regular Masking
      3. 10.4.3 Irregular Masking
    5. 10.5 Construction of QC-EG-LDPC Codes by Circulant Decomposition
    6. 10.6 Construction of Cyclic and QC-LDPC Codes Based on Projective Geometries
      1. 10.6.1 Cyclic PG-LDPC Codes
      2. 10.6.2 Quasi-Cyclic PG-LDPC Codes
    7. 10.7 One-Step Majority-Logic and Bit-Flipping Decoding Algorithms for FG-LDPC Codes
      1. 10.7.1 The OSMLG Decoding Algorithm for LDPC Codes over the BSC
      2. 10.7.2 The BF Algorithm for Decoding LDPC Codes over the BSC
    8. 10.8 Weighted BF Decoding: Algorithm 1
    9. 10.9 Weighted BF Decoding: Algorithms 2 and 3
    10. 10.10 Concluding Remarks
    11. Problems
    12. References
  16. 11 Constructions of LDPC Codes Based on Finite Fields
    1. 11.1 Matrix Dispersions of Elements of a Finite Field
    2. 11.2 A General Construction of QC-LDPC Codes Based on Finite Fields
    3. 11.3 Construction of QC-LDPC Codes Based on the Minimum-Weight Codewords of an RS Code with Two Information Symbols
    4. 11.4 Construction of QC-LDPC Codes Based on the Universal Parity-Check Matrices of a Special Subclass of RS Codes
    5. 11.5 Construction of QC-LDPC Codes Based on Subgroups of a Finite Field
      1. 11.5.1 Construction of QC-LDPC Codes Based on Subgroups of the Additive Group of a Finite Field
      2. 11.5.2 Construction of QC-LDPC Codes Based on Subgroups of the Multiplicative Group of a Finite Field
    6. 11.6 Construction of QC-LDPC Code Based on the Additive Group of a Prime Field
    7. 11.7 Construction of QC-LDPC Codes Based on Primitive Elements of a Field
    8. 11.8 Construction of QC-LDPC Codes Based on the Intersecting Bundles of Lines of Euclidean Geometries
    9. 11.9 A Class of Structured RS-Based LDPC Codes
    10. Problems
    11. References
  17. 12 LDPC Codes Based on Combinatorial Designs, Graphs, and Superposition
    1. 12.1 Balanced Incomplete Block Designs and LDPC Codes
    2. 12.2 Class-I Bose BIBDs and QC-LDPC Codes
      1. 12.2.1 Class-I Bose BIBDs
      2. 12.2.2 Type-I Class-I Bose BIBD-LDPC Codes
      3. 12.2.3 Type-II Class-I Bose BIBD-LDPC Codes
    3. 12.3 Class-II Bose BIBDs and QC-LDPC Codes
      1. 12.3.1 Class-II Bose BIBDs
      2. 12.3.2 Type-I Class-II Bose BIBD-LDPC Codes
      3. 12.3.3 Type-II Class-II QC-BIBD-LDPC Codes
    4. 12.4 Construction of Type-II Bose BIBD-LDPC Codes by Dispersion
    5. 12.5 A Trellis-Based Construction of LDPC Codes
      1. 12.5.1 A Trellis-Based Method for Removing Short Cycles from a Bipartite Graph
      2. 12.5.2 Code Construction
    6. 12.6 Construction of LDPC Codes Based on Progressive Edge-Growth Tanner Graphs
    7. 12.7 Construction of LDPC Codes by Superposition
      1. 12.7.1 A General Superposition Construction of LDPC Codes
      2. 12.7.2 Construction of Base and Constituent Matrices
      3. 12.7.3 Superposition Construction of Product LDPC Codes
    8. 12.8 Two Classes of LDPC Codes with Girth 8
    9. Problems
    10. References
  18. 13 LDPC Codes for Binary Erasure Channels
    1. 13.1 Iterative Decoding of LDPC Codes for the BEC
    2. 13.2 Random-Erasure-Correction Capability
    3. 13.3 Good LDPC Codes for the BEC
    4. 13.4 Correction of Erasure-Bursts
    5. 13.5 Erasure-Burst-Correction Capabilities of Cyclic Finite-Geometry and Superposition LDPC Codes
      1. 13.5.1 Erasure-Burst-Correction with Cyclic Finite-Geometry LDPC Codes
      2. 13.5.2 Erasure-Burst-Correction with Superposition LDPC Codes
    6. 13.6 Asymptotically Optimal Erasure-Burst-Correction QC-LDPC Codes
    7. 13.7 Construction of QC-LDPC Codes by Array Dispersion
    8. 13.8 Cyclic Codes for Correcting Bursts of Erasures
    9. Problems
    10. References
  19. 14 Nonbinary LDPC Codes
    1. 14.1 Definitions
    2. 14.2 Decoding of Nonbinary LDPC Codes
      1. 14.2.1 The QSPA
      2. 14.2.2 The FFT-QSPA
    3. 14.3 Construction of Nonbinary LDPC Codes Based on Finite Geometries
      1. 14.3.1 A Class of qm-ary Cyclic EG-LDPC Codes
      2. 14.3.2 A Class of Nonbinary Quasi-Cyclic EG-LDPC Codes
      3. 14.3.3 A Class of Nonbinary Regular EG-LDPC Codes
      4. 14.3.4 Nonbinary LDPC Code Constructions Based on Projective Geometries
    4. 14.4 Constructions of Nonbinary QC-LDPC Codes Based on Finite Fields
      1. 14.4.1 Dispersion of Field Elements into Nonbinary Circulant Permutation Matrices
      2. 14.4.2 Construction of Nonbinary QC-LDPC Codes Based on Finite Fields
      3. 14.4.3 Construction of Nonbinary QC-LDPC Codes by Masking
      4. 14.4.4 Construction of Nonbinary QC-LDPC Codes by Array Dispersion
    5. 14.5 Construction of QC-EG-LDPC Codes Based on Parallel Flats in Euclidean Geometries and Matrix Dispersion
    6. 14.6 Construction of Nonbinary QC-EG-LDPC Codes Based on Intersecting Flats in Euclidean Geometries and Matrix Dispersion
    7. 14.7 Superposition–Dispersion Construction of Nonbinary QC-LDPC Codes
    8. Problems
    9. References
  20. 15 LDPC Code Applications and Advanced Topics
    1. 15.1 LDPC-Coded Modulation
      1. 15.1.1 Design Based on EXIT Charts
    2. 15.2 Turbo Equalization and LDPC Code Design for ISI Channels
      1. 15.2.1 Turbo Equalization
      2. 15.2.2 LDPC Code Design for ISI Channels
    3. 15.3 Estimation of LDPC Error Floors
      1. 15.3.1 The Error-Floor Phenomenon and Trapping Sets
      2. 15.3.2 Error-Floor Estimation
    4. 15.4 LDPC Decoder Design for Low Error Floors
      1. 15.4.1 Codes Under Study
      2. 15.4.2 The Bi-Mode Decoder
      3. 15.4.3 Concatenation and Bit-Pinning
      4. 15.4.4 Generalized-LDPC Decoder
      5. 15.4.5 Remarks
    5. 15.5 LDPC Convolutional Codes
    6. 15.6 Fountain Codes
      1. 15.6.1 Tornado Codes
      2. 15.6.2 Luby Transform Codes
      3. 15.6.3 Raptor Codes
    7. Problems
    8. References
  21. Index