An efficient algorithm for finding dominant trapping sets of LDPC codes

This paper presents an efficient algorithm for finding the dominant trapping sets of a low-density parity-check (LDPC) code. This algorithm can be used to estimate the error floor of LDPC codes or to be part of the apparatus to design LDPC codes with low error floors. The algorithm is initiated with a set of short cycles as the input. The cycles are then expanded recursively to dominant trapping sets of increasing size. At the core of the algorithm lies the analysis of the graphical structure of dominant trapping sets and the relationship of such structures to short cycles. The algorithm is universal in the sense that it can be used for an arbitrary graph and that it can be tailored to find other graphical objects, such as absorbing sets and Zyablov-Pinsker (ZP) trapping sets, known to dominate the performance of LDPC codes in the error floor region over different channels and for different iterative decoding algorithms. Simulation results on several LDPC codes demonstrate the accuracy and efficiency of the proposed algorithm. In particular, the algorithm is significantly faster than the existing search algorithms for dominant trapping sets.

• Publication year

  2011

• Venue

  International Symposium on Turbo Codes and Iterative Information Processing

• Publication date

  2011-08-23

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/TIT.2012.2205663arXiv 1108.4478
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On the Construction of Structured LDPC Codes Free of Small Trapping Sets

  2012cited by this paper
• Trapping set enumerators for specific LDPC codes

  2010influential reference
• Exhaustive search for small fully absorbing sets and the corresponding low error-floor decoder

  2010influential reference
• A message-passing algorithm for counting short cycles in a graph

  2010cited by this paper
• Lowering the error floor of LDPC codes using cyclic liftings

  2010cited by this paper
• An Efficient Algorithm to Find All Small-Size Stopping Sets of Low-Density Parity-Check Matrices

  2009cited by this paper
• Trapping set ontology

  2009cited by this paper
• Error rate estimation of low-density parity-check codes on binary symmetric channels using cycle enumeration

  2009cited by this paper
• On the dynamics of the error floor behavior in regular LDPC codes

  2009cited by this paper
• Predicting error floors of structured LDPC codes: deterministic bounds and estimates

  2009cited by this paper
• Toward low LDPC-code floors: a case study

  2009cited by this paper
• Finding All Small Error-Prone Substructures in LDPC Codes

  2009influential reference
• Generalized ACE Constrained Progressive Edge-Growth LDPC Code Design

  2008cited by this paper
• LDPC decoder strategies for achieving low error floors

  2008cited by this paper
• Error rate estimation of finite-length low-density parity-check codes decoded by soft-decision iterative algorithms

  2008cited by this paper
• Society for Industrial and Applied Mathematics(SIAM)

  2008cited by this paper
• Eliminating trapping sets in low-density parity-check codes by using Tanner graph covers

  2008cited by this paper
• On the Exhaustion and Elimination of Trapping Sets: Algorithms & The Suppressing Effect

  2007cited by this paper
• Asymptotic Spectra of Trapping Sets in Regular and Irregular LDPC Code Ensembles

  2007cited by this paper
• On the Hardness of Approximating Stopping and Trapping Sets

  2007influential reference
• Quantization Effects in Low-Density Parity-Check Decoders

  2007cited by this paper
• Evaluation of the Low Frame Error Rate Performance of LDPC Codes Using Importance Sampling

  2007cited by this paper
• Computing the Stopping Distance of a Tanner Graph Is NP-Hard

  2007cited by this paper
• Estimation of Bit and Frame Error Rates of Finite-Length Low-Density Parity-Check Codes on Binary Symmetric Channels

  2007cited by this paper
• On the Minimum Distance of Generalized LDPC Codes

  2007cited by this paper
• An Algorithm to Find All Small-Size Stopping Sets of Low-Density Parity-Check Matrices

  2007cited by this paper
• The Trapping Redundancy of Linear Block Codes

  2006cited by this paper
• Hardness of Approximation Results for the Problem of Finding the Stopping Distance in Tanner Graphs

  2006cited by this paper
• Estimation of Bit and Frame Error Rates of Low-Density Parity-Check Codes on Binary Symmetric Channels

  2006influential reference
• On the minimum distance of structured LDPC codes with two variable nodes of degree 2 per parity-check equation

  2006cited by this paper
• A General Method for Finding Low Error Rates of LDPC Codes

  2006influential reference
• An IS Simulation Technique for Very Low BER Performance Evaluation of LDPC Codes

  2006cited by this paper
• A performance improvement and error floor avoidance technique for belief propagation decoding of LDPC codes

  2005cited by this paper
• Algorithmic and combinatorial analysis of trapping sets in structured LDPC codes

  2005cited by this paper
• Graph-Cover Decoding and Finite-Length Analysis of Message-Passing Iterative Decoding of LDPC Codes

  2005cited by this paper
• IEEE 802.11n: enhancements for higher throughput in wireless LANs

  2005cited by this paper
• Regular and irregular progressive edge-growth tanner graphs

  2005cited by this paper
• Short Cycles in Random Regular Graphs

  2004cited by this paper
• Selective avoidance of cycles in irregular LDPC code construction

  2004cited by this paper
• Γ and B

  2004cited by this paper
• Design of efficiently encodable moderate-length high-rate irregular LDPC codes

  2004influential reference
• Improved progressive-edge-growth (PEG) construction of irregular LDPC codes

  2004cited by this paper
• Improved progressive-edge-growth (PEG) construction of irregular LDPC codes

  2004cited by this paper
• Weaknesses of Margulis and Ramanujan-Margulis low-density parity-check cCodes

  2003cited by this paper
• Error Floors of LDPC Codes

  2003cited by this paper
• Graph-covers and iterative decoding of nite length codes

  2003cited by this paper
• Finite-length analysis of low-density parity-check codes on the binary erasure channel

  2002cited by this paper
• A Class of Group-Structured LDPC Codes

  2001cited by this paper
• Design of capacity-approaching irregular low-density parity-check codes

  2001influential reference
• I and i

  2001cited by this paper
• On the construction of some capacity-approaching coding schemes

  2000cited by this paper
• IEEE Transactions on Information Theory

  1998cited by this paper
• Algorithms to Count Paths and Cycles

  1994cited by this paper
• Explicit constructions of graphs without short cycles and low density codes

  1982cited by this paper
• Finding All the Elementary Circuits of a Directed Graph

  1975cited by this paper

• Toward Universal Belief Propagation Decoding for Short Binary Block Codes

  2025cites this paper
• Belief Propagation Decoding for Short Codes on Structured Sparse Parity-Check Matrices

  2025cites this paper
• Linear Complexity Computation of Code Distance and Minimum Size of Trapping Sets for LDPC Codes with Bounded Treewidth

  2025cites this paper
• Improved Belief Propagation Decoding Algorithms for Surface Codes

  2024cites this paper
• On Construction of Low-Density Parity-Check Codes for Ultra-Reliable and Low Latency Communications

  2024cites this paper
• Collision Diversity SCRAM: Beyond the Sphere-Packing Bound

  2024cites this paper
• Mixed Integer Linear Programming Method for Energy-Based Model Trapping Sets Enumerating

  2024cites this paper
• An Efficient Strategy to Count Cycles in the Tanner Graph of Quasi-Cyclic LDPC Codes

  2023cites this paper
• A low-floor bit-mapping scheme for LDPC coded BICM for 5G and beyond systems

  2023cites this paper
• Using Partial Orthomorphisms to Construct Short Quasi-Cyclic LDPC Codes with Girth at Least 6

  2023cites this paper
• Low Error Floor QC-LDPC Codes Construction Using Modified Cole's Trapping Sets Enumerating

  2023cites this paper
• Spherical and Hyperbolic Toric Topology-Based Codes On Graph Embedding for Ising MRF Models: Classical and Quantum Topology Machine Learning

  2023cites this paper
• On the Tanner Cycle Distribution of QC-LDPC Codes from Polynomial Parity-Check Matrices

  2023cites this paper
• Decoding Short LDPC Codes via BP-RNN Diversity and Reliability-Based Post-Processing

  2022cites this paper
• Doped low-density parity-check codes

  2022cites this paper
• Effective identification of dominant fully absorbing sets for Raptor‐like LDPC codes

  2022influential citation
• An Modified Cole's Importance Sampling Method For Low Error Floor QC-LDPC Codes Construction

  2022cites this paper
• A Semi Linear State Space Model for Error Floor Estimation of LDPC Codes Over the AWGN Channel

  2022cites this paper
• On the Construction of QC-LDPC Codes Based on Integer Sequence With Low Error Floor

  2022cites this paper
• Low Complexity Generalized-LDPC Decoder Based on Trellis Splicing

  2021cites this paper
• Error Floor Analysis of LDPC Row Layered Decoders

  2021cites this paper
• Error Floor Estimation of LDPC Coded Modulation Systems Using Importance Sampling

  2021cites this paper
• Construction of Time Invariant Spatially Coupled LDPC Codes Free of Small Trapping Sets

  2021cites this paper
• Error Floor Analysis of LDPC Column Layered Decoders

  2021cites this paper
• Review on 5G NR LDPC Code: Recommendations for DTTB System

  2021cites this paper
• Construction of Irregular Protograph-Based QC-LDPC Codes With Low Error Floor

  2021cites this paper
• Analysis of Absorbing Sets using Cosets and Syndromes

  2020cites this paper
• Counting Short Cycles in Bipartite Graphs: A Fast Technique/Algorithm and a Hardness Result

  2020cites this paper
• Error Floor Estimation of LDPC Decoders — A Code Independent Approach to Measuring the Harmfulness of Trapping Sets

  2020cites this paper
• Trapping Sets of Quantum LDPC Codes

  2020cites this paper
• On Finding Bipartite Graphs With a Small Number of Short Cycles and Large Girth

  2020cites this paper
• A survey on channel coding techniques for 5G wireless networks

  2019cites this paper
• On Computing the Number of Short Cycles in Bipartite Graphs Using the Spectrum of the Directed Edge Matrix

  2019cites this paper
• Construction of QC LDPC Codes With Low Error Floor by Efficient Systematic Search and Elimination of Trapping Sets

  2019cites this paper
• On the Computational Complexity of Finding Bipartite Graphs with a Small Number of Short Cycles and Large Girth

  2019cites this paper
• An Absorbing Set Analysis of Quantized LDPC Decoders

  2019cites this paper
• A new construction method of QC-LDPC codes with low error floor based on EETS and Zig-Zag

  2019cites this paper
• Cospectral Bipartite Graphs with the Same Degree Sequences but with Different Number of Large Cycles

  2019cites this paper
• A pr 2 01 6 Probabilistic bounds on the trapping redundancy of linear codes

  2018cites this paper
• From Cages to Trapping Sets: A New Technique to Derive Tight Upper Bounds on the Minimum Size of Trapping Sets and Minimum Distance of LDPC Codes

  2018cites this paper
• Trapping Set Analysis of Horizontal Layered Decoder

  2018cites this paper
• Design of Binary LDPC Codes With Parallel Vector Message Passing

  2018cites this paper
• On Lowering the Error Floor of Short-to-Medium Block Length Irregular Low Density Parity Check Codes

  2018cites this paper
• On Computing the Multiplicity of Cycles in Bipartite Graphs Using the Degree Distribution and the Spectrum of the Graph

  2018cites this paper
• Stopping Redundancy Hierarchy Beyond the Minimum Distance

  2018cites this paper
• A Combinatorial Methodology for Optimizing Non-Binary Graph-Based Codes: Theoretical Analysis and Applications in Data Storage

  2017cites this paper
• Asymptotic Average Number of Different Categories of Trapping Sets, Absorbing Sets and Stopping Sets in Random Regular and Irregular LDPC Code Ensembles

  2017cites this paper
• On the Tanner Graph Cycle Distribution of Random LDPC, Random Protograph-Based LDPC, and Random Quasi-Cyclic LDPC Code Ensembles

  2017cites this paper
• Hardness Results on Finding Leafless Elementary Trapping Sets and Elementary Absorbing Sets of LDPC Codes

  2017cites this paper
• Spatially Coupled Codes Optimized for Magnetic Recording Applications

  2017cites this paper
• On practical LDPC code construction for NAND flash applications

  2017cites this paper
• Multidimensional Decoding Networks for Trapping Set Analysis

  2017cites this paper
• From Cages to Trapping Sets and Codewords: A Technique to Derive Tight Upper Bounds on the Minimum Size of Trapping Sets and Minimum Distance of LDPC Codes

  2017cites this paper
• Asymptotic Average Multiplicity of Structures Within Different Categories of Trapping Sets, Absorbing Sets, and Stopping Sets in Random Regular and Irregular LDPC Code Ensembles

  2017cites this paper
• The weight consistency matrix framework for general non-binary LDPC code optimization: Applications in flash memories

  2016cites this paper
• An efficient exhaustive search algorithm for elementary trapping sets of variable-regular LDPC codes

  2016cites this paper
• Characterization and efficient exhaustive search algorithm for elementary trapping sets of irregular LDPC codes

  2016cites this paper
• Bounds on existence of odd and unique expanders

  2016influential citation
• Minimal characterization and provably efficient exhaustive search algorithm for elementary trapping sets of variable-regular LDPC codes

  2016cites this paper
• New Characterization and Efficient Exhaustive Search Algorithm for Leafless Elementary Trapping Sets of Variable-Regular LDPC Codes

  2016cites this paper
• Guest Editorial Channel Modeling, Coding and Signal Processing for Novel Physical Memory Devices and Systems

  2016cites this paper
• A General Non-Binary LDPC Code Optimization Framework Suitable for Dense Flash Memory and Magnetic Storage

  2016cites this paper
• Advanced Algebraic and Graph-Based ECC Schemes for Modern NVMs

  2016cites this paper
• Probabilistic bounds on the trapping redundancy of linear codes

  2016cites this paper
• Optimized Design of Finite-Length Separable Circulant-Based Spatially-Coupled Codes: An Absorbing Set-Based Analysis

  2016cites this paper
• Error Errore Eicitur: A Stochastic Resonance Paradigm for Reliable Storage of Information on Unreliable Media

  2016cites this paper
• Exhaustive Enumeration of Elementary Trapping Sets of an Arbitrary Tanner Graph

  2016cites this paper
• A local flat histogram method for evaluating the performance of LDPC codes

  2015cites this paper
• Design and Analysis of Efficient Algorithm for Counting and Enumerating Cycles in LDPC Codes

  2015cites this paper
• Theory and Practice of Non-Binary Graph-Based Codes: A Combinatorial View

  2015cites this paper
• New Characterization and Efficient Exhaustive Search Algorithm for Elementary Trapping Sets of Variable-Regular LDPC Codes

  2015cites this paper
• Enhancing LDPC code performance using pilot bits

  2015cites this paper
• Design of non-binary quasi-cyclic LDPC codes by absorbing set removal

  2014cites this paper
• Refined upper bounds on stopping redundancy of binary linear codes

  2014influential citation
• A technique for the identification of trapping sets in LDPC codes

  2014cites this paper
• On characterization of elementary trapping sets of variable-regular LDPC codes

  2014cites this paper
• An integer programming-based search technique for error-prone structures of LDPC codes

  2014cites this paper
• Two-Bit Bit Flipping Algorithms for LDPC Codes and Collective Error Correction

  2014cites this paper
• Finding Small Fundamental Instantons of LDPC Codes by Path Extension

  2014cites this paper
• Analysis and design of a new fountain codec under belief propagation

  2014cites this paper
• propagation de croyances.

  2013cites this paper
• Analysis and Enumeration of Absorbing Sets for Non-Binary Graph-Based Codes

  2013cites this paper
• An efficient exhaustive low-weight codeword search for structured LDPC codes

  2013cites this paper
• Low complexity iterative algorithms in channel coding and compressed sensing

  2013cites this paper
• Error Rate Estimation of Low-Density Parity-Check Codes Decoded by Quantized Soft-Decision Iterative Algorithms

  2013cites this paper
• On Characterization of Elementary Trapping Sets of Variable-Regular LDPC Codes

  2013cites this paper
• Probabilistic analysis of cycles in random Tanner graphs

  2013cites this paper
• LDPC Codes on Partial Geometries: Construction, Trapping Set Structure, and Puncturing

  2013cites this paper
• Construction of Structured Nonbinary Low-Density Parity-Check Codes

  2013cites this paper
• Error Floors of LDPC Codes and Related Topics

  2013influential citation
• On the Girth of Quasi-Cyclic Protograph LDPC Codes

  2013cites this paper
• Iterative Decoding Beyond Belief Propagation of Low-Density Parity-Check Codes

  2013cites this paper
• Message-Passing Algorithms for Counting Short Cycles in a Graph

  2013cites this paper
• Algorithmes itératifs à faible complexité pour le codage de canal et le compressed sensing. (Low Complexity Iterative Algorithms for Channel Coding and Compressed Sensing)

  2012influential citation
• The Cycle Consistency Matrix Approach to LDPC Absorbing Sets in Separable Circulant-Based Codes

  2012cites this paper
• Improving the Error Floor Performance of LDCP Codes with Better Codes and Better Decoders

  2012cites this paper
• A PEG Construction of Finite-Length LDPC Codes with Low Error Floor

  2012cites this paper
• Décodage itératif pour les codes LDPC au-delà de la propagation de croyances. (Iterative decoding beyond belief propagation for low-density parity-check codes)

  2012cites this paper
• Finding the Exhaustive List of Small Fully Absorbing Sets and Designing the Corresponding Low Error-Floor Decoder

  2012cites this paper
• An integer programming based trapping set search technique

  2012cites this paper