Instanton analysis of Low-Density Parity-Check codes in the error-floor regime

In this paper we develop instanton method introduced in V. Chernyak et al. (2004), M.G. Stepanov et al. (2005) to analyze quantitatively performance of low-density parity-check (LDPC) codes decoded iteratively in the so-called error-floor regime. We discuss statistical properties of the numerical instanton-amoeba scheme focusing on detailed analysis and comparison of two regular LDPC codes: Tanner's [155,64,20] and Margulis' [672,336,16] codes. In the regime of moderate values of the signal-to-noise ratio we critically compare results of the instanton-amoeba evaluations against the standard Monte Carlo calculations of the frame-error-rate

• Publication year

  2006

• Venue

  2006 IEEE International Symposium on Information Theory

• Publication date

  2006-01-16

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1109/ISIT.2006.261777arXiv cs/0601070
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Looping linear programming decoding of LDPC codes

  2006cited by this paper
• Diagnosis of weaknesses in modern error correction codes: a physics approach

  2005influential reference
• The error-floor of LDPC codes in the Laplacian channel

  2005influential reference
• Graph-Cover Decoding and Finite-Length Analysis of Message-Passing Iterative Decoding of LDPC Codes

  2005cited by this paper
• On the computation of the minimum distance of low-density parity-check codes

  2004cited by this paper
• Error correction on a tree: an instanton approach.

  2004cited by this paper
• Low-Density Parity-Check Codes

  2004cited by this paper
• Error Floors of LDPC Codes

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

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

  2001cited by this paper
• Good error-correcting codes based on very sparse matrices

  1997cited by this paper
• Codes and Decoding on General Graphs

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

  1982cited by this paper
• A Simplex Method for Function Minimization

  1965cited by this paper

• LUT-Optimized Decoding of QC-LDPC Codes for Flash Memory with EoL Layers Variation Model

  2025cites this paper
• A construction of random bigraphs and their application to error correction codes

  2025cites this paper
• An Modified Cole's Importance Sampling Method For Low Error Floor QC-LDPC Codes Construction

  2022cites this paper
• ADMM Check Node Penalized Decoders for LDPC Codes

  2021cites this paper
• Suppressing Fractional Pseudocodewords by Eliminating Small Instantons

  2016cites this paper
• ADMM decoding on trapping sets

  2015cites this paper
• Stopping Set Elimination by Parity-Check Matrix Extension via Integer Linear Programming

  2015cites this paper
• The ADMM Penalized Decoder for LDPC Codes

  2014influential citation
• Failures and Error Floors of Iterative Decoders

  2014cites this paper
• Instanton search algorithm for the ADMM penalized decoder

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

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

  2013cites this paper
• Cyclic and Quasi-Cyclic LDPC Codes on Constrained Parity-Check Matrices and Their Trapping Sets

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

  2012cites this paper
• A Deviation-Based Conditional Upper Bound on the Error Floor Performance for Min-Sum Decoding of Short LDPC Codes

  2012cites this paper
• Performance evaluation of irregular low-density parity-check codes at high signal-to-noise ratio

  2011cites this paper
• Trapping sets of structured LDPC codes

  2011cites this paper
• Low-Density Parity-Check Codes and Their Rateless Relatives

  2011cites this paper
• Lowering the Error Floor of LDPC Codes Using Cyclic Liftings

  2011cites this paper
• High-Rate Short-Block LDPC Codes for Iterative Decoding with Applications to High-Density Magnetic Recording Channels

  2011cites this paper
• Instantons causing iterative decoding to cycle

  2011cites this paper
• Cyclic and Quasi-Cyclic LDPC Codes on Row and Column Constrained Parity-Check Matrices and Their Trapping Sets

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

  2010cites this paper
• Instanton-based techniques for analysis and reduction of error floors of LDPC codes

  2009influential citation
• An efficient pseudo-codeword search algorithm for Belief Propagation decoding of LDPC codes

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

  2009influential citation
• An Efficient Algorithm to Find All Small-Size Stopping Sets of Low-Density Parity-Check Matrices

  2009cites this paper
• Near-capacity fixed-rate and rateless channel code constructions

  2009cites this paper
• Trapping Sets in Fountain Codes over Noisy Channels

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

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

  2008influential citation
• On the Hardness of Approximating Stopping and Trapping Sets in LDPC Codes

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

  2007cites this paper
• On the Exhaustion and Elimination of Trapping Sets: Algorithms & The Suppressing Effect

  2007influential citation
• Searching for low weight pseudo-codewords

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

  2007cites this paper
• Pseudo-codeword Landscape

  2007cites this paper
• Loop Calculus Helps to Improve Belief Propagation and Linear Programming Decodings of Low-Density-Parity-Check Codes

  2006cites this paper
• Exhausting Error-Prone Patterns in LDPC Codes

  2006influential citation
• Application de la mécanique statistique à trois problèmes hors d'équilibre : algorithmes, épidémies, milieux granulaires

  2006cites this paper
• An Efficient Pseudocodeword Search Algorithm for Linear Programming Decoding of LDPC Codes

  2006cites this paper