Statistical physics of regular low-density parity-check error-correcting codes

A variation of Gallager error-correcting codes is investigated using statistical mechanics. In codes of this type, a given message is encoded into a codeword that comprises Boolean sums of message bits selected by two randomly constructed sparse matrices. The similarity of these codes to Ising spin systems with random interaction makes it possible to assess their typical performance by analytical methods developed in the study of disordered systems. The typical case solutions obtained via the replica method are consistent with those obtained in simulations using belief propagation decoding. We discuss the practical implications of the results obtained and suggest a computationally efficient construction for one of the more practical configurations.

• Publication year

  2000

• Venue

  Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics

• Publication date

  2000-03-08

• Fields of study

  Medicine, Physics, Mathematics

• Identifiers
  DOI 10.1103/PhysRevE.62.1577arXiv cond-mat/0003121PMID 11088619
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• Design of provably good low-density parity check codes

  2000cited by this paper
• Finite-connectivity systems as error-correcting codes.

  1999cited by this paper
• Finite-size effects and error-free communication in Gaussian channels

  1999cited by this paper
• Statistical mechanics of error-correcting codes

  1999cited by this paper
• Comparison of constructions of irregular Gallager codes

  1999cited by this paper
• Typical performance of gallager-type error-correcting codes

  1999cited by this paper
• Error-correcting codes that nearly saturate Shannon's bound

  1999cited by this paper
• Graphical Models for Machine Learning and Digital Communication

  1998cited by this paper
• Belief propagation vs. TAP for decoding corrupted messages

  1998cited by this paper
• The Nishimori line and Bayesian statistics

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

  1997cited by this paper
• Near Shannon limit performance of low density parity check codes

  1996cited by this paper
• In Advances in Neural Information Processing Systems

  1996cited by this paper
• Pearl, J. (1988, second printing 1991). Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan-Kaufmann.

  1994cited by this paper
• Spin Glasses, Error-Correcting Codes and Finite-Temperature Decoding

  1994cited by this paper
• Finite temperature error-correcting codes.

  1993cited by this paper
• Probabilistic reasoning in intelligent systems: Networks of plausible inference

  1991cited by this paper
• Spin-glass models as error-correcting codes

  1989cited by this paper
• Graph bipartitioning and spin glasses on a random network of fixed finite valence

  1987cited by this paper
• Internal Energy, Specific Heat and Correlation Function of the Bond-Random Ising Model

  1981cited by this paper
• Solution of 'Solvable model of a spin glass'

  1977cited by this paper
• The mathematical theory of communication

  1950cited by this paper
• A mathematical theory of communication

  1948cited by this paper

• A construction of random bigraphs and their application to error correction codes

  2025cites this paper
• Legislative rebellions and impeachments in a neural network society.

  2024cites this paper
• Rebellions and Impeachments in a Neural Network Society

  2023cites this paper
• Analyticity of the energy in an Ising spin glass with correlated disorder

  2021cites this paper
• Matrix completion based on Gaussian parameterized belief propagation

  2021cites this paper
• Decision Theoretic Cutoff and ROC Analysis for Bayesian Optimal Group Testing

  2021cites this paper
• LDPC Decoding Based On Statistical Mechanics Of Spin-Glasses: A Study

  2020influential citation
• Covariance Matrix of a Probability Distribution for Image Dictionaries in Compressed Sensing

  2018cites this paper
• Effects of smooth random surface on fluid monolayer thermodynamics

  2016cites this paper
• Performance of LDPC Decoding Algorithms with a Statistical Physics Theory Approach

  2015cites this paper
• Sparse Probabilistic Models - Phase Transitions and Solutions via Spatial Coupling

  2015cites this paper
• A Statistical-Physics Approach to the Analysisof Wireless Communication Systems

  2014cites this paper
• Code Optimization, Frozen Glassy Phase and Improved Decoding Algorithms for Low-Density Parity-Check Codes

  2014cites this paper
• Spatially-coupled multi-edge type LDPC codes with bounded degrees that achieve capacity on the BEC under BP decoding

  2013cites this paper
• Replica analysis of CDMA multiuser-demodulator for correlated data

  2013cites this paper
• New Understanding of the Bethe Approximation and the Replica Method

  2013cites this paper
• Spatial Coupling as a Proof Technique and Three Applications

  2013cites this paper
• Spatially-coupled binary MacKay-Neal codes for channels with non-binary inputs and affine subspace outputs

  2012cites this paper
• Asymptotic analysis of spatially coupled MacKay-Neal and Hsu-Anastasopoulos LDPC codes

  2012cites this paper
• Maximizer of the Posterior Marginal Estimate for Noise Reduction of JPEG-compressed Image

  2012cites this paper
• Spatially-coupled MacKay-Neal codes and Hsu-Anastasopoulos codes

  2011cites this paper
• Spatially Coupled Protograph-Based LDPC Codes for Decode-and-Forward in Erasure Relay Channel

  2011cites this paper
• Statistical Mechanical Analysis of Low-Density Parity-Check Codes on General Markov Channel

  2011cites this paper
• Connection between annealed free energy and belief propagation on random factor graph ensembles

  2011cites this paper
• Phase transitions in the three-state Ising spin-glass model with finite connectivity.

  2011cites this paper
• λ-min algorithm using TAP approach

  2010cites this paper
• Statistical mechanics of spin models on graphs.

  2010cites this paper
• Magnetization performance of BP-Based algorithm

  2010influential citation
• Statistical Physics Approach to Design and Analysis of Multiuser Systems Under Channel Uncertainty

  2010cites this paper
• Magnetization Performance of LDPC Reduced-Complexity Decoding Algorithms

  2010cites this paper
• Generic Multiuser Detection and Statistical Physics

  2009cites this paper
• Low-Density Graph Codes That Are Optimal for Binning and Coding With Side Information

  2009cites this paper
• Decay of Correlations for Sparse Graph Error Correcting Codes

  2009cites this paper
• Parallel dynamics of disordered Ising spin systems on finitely connected directed random graphs with arbitrary degree distributions

  2009cites this paper
• Iterative decoding algorithms of LDPC codes using TAP approach

  2009influential citation
• On the equivalence of Ising models on ‘small-world’ networks and LDPC codes on channels with memory

  2009cites this paper
• Reduced-Comlexity Decoding of LDPC Codes Using TAP Approach

  2009influential citation
• Statistical physics methods for sparse graph codes

  2009cites this paper
• Spin models on random graphs with controlled topologies beyond degree constraints

  2008cites this paper
• Gallager error-correcting codes for binary asymmetric channels

  2008cites this paper
• Statistical-mechanical analysis of multiuser channel capacity with imperfect channel state information

  2008cites this paper
• A mean field theory of coded CDMA systems

  2008cites this paper
• Modern Coding Theory: The Statistical Mechanics and Computer Science Point of View

  2007cites this paper
• Griffith–Kelly–Sherman Correlation Inequalities: A Useful Tool in the Theory of Error Correcting Codes

  2007cites this paper
• Course 10 - Two Lectures on Iterative Coding and Statistical Mechanics

  2006cites this paper
• Randomly spread CDMA: asymptotics via statistical physics

  2005cites this paper
• Two Lectures on Iterative Coding and Statistical Mechanics

  2005cites this paper
• Maxwell Construction: The Hidden Bridge Between Iterative and Maximum a Posteriori Decoding

  2005cites this paper
• Finite-connectivity spin-glass phase diagrams and low-density parity check codes.

  2005cites this paper
• Correlation inequalities: a useful tool in the theory of LDPC codes

  2005cites this paper
• Finitely connected vector spin systems with random matrix interactions

  2005cites this paper
• Cavity approach for real variables on diluted graphs and application to synchronization in small-world lattices.

  2005cites this paper
• Information geometry of turbo and low-density parity-check codes

  2004cites this paper
• Replicated transfer matrix analysis of Ising spin models on 'small world' lattices

  2004cites this paper
• Tight bounds for LDPC and LDGM codes under MAP decoding

  2004influential citation
• Statistical mechanics of low-density parity-check codes

  2004influential citation
• A statistical-mechanical analysis of coded CDMA with regular LDPC codes

  2003cites this paper
• A CDMA multiuser detection algorithm on the basis of belief propagation

  2003cites this paper
• Finite connectivity attractor neural networks

  2003cites this paper
• Analysis of common attacks in public-key cryptosystems based on low-density parity-check codes.

  2003cites this paper
• Random graph coloring: statistical physics approach.

  2002cites this paper
• Typical performance of regular low-density parity-check codes over general symmetric channels

  2002cites this paper
• A statistical-mechanics approach to large-system analysis of CDMA multiuser detectors

  2002cites this paper
• Statistical mechanics of the data compression theorem

  2002cites this paper
• Critical noise levels for low-density parity check decoding.

  2002cites this paper
• Low-density parity-check codes—A statistical physics perspective

  2002cites this paper
• Statistical mechanics of typical set decoding.

  2001cites this paper
• Weight vs. Magnetization Enumerator for Gallager Codes

  2001cites this paper
• Information-Geometrical Significance of Sparsity in Gallager Codes

  2001cites this paper
• Tighter decoding reliability bound for Gallager's error-correcting code.

  2000cites this paper
• Statistical physics of irregular low-density parity-check codes

  1999cites this paper
• Mext Grant-in-aid for Scientific Research on Priority Areas " Statistical Mechanical Approach to Probabilistic Information Processing " Workshop on Mathematics of Statistical Inference ( Statistical Mechanics of Multi Terminal Data Compression — Theory and Practice —

  year unknowncites this paper