The Statistical Physics of Regular Low-Density Parity-Check Error-Correcting Codes
arXiv:cond-mat/0003121 · doi:10.1103/PhysRevE.62.1577
Abstract
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 which 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 (BP) decoding. We discuss the practical implications of the results obtained and suggest a computationally efficient construction for one of the more practical configurations.
35 pages, 4 figures
References in corpus (5)
Cited by in corpus (32)
- Tight bounds for LDPC and LDGM codes under MAP decoding
- Finite Connectivity Attractor Neural Networks
- Parallel dynamics of disordered Ising spin systems on finitely connected random graphs
- Replicated Transfer Matrix Analysis of Ising Spin Models on `Small World' Lattices
- Error-correcting code on a cactus: a solvable model
- Statistical Mechanics of Low-Density Parity Check Error-Correcting Codes over Galois Fields
- Finitely connected vector spin systems with random matrix interactions
- Random Graph Coloring - a Statistical Physics Approach
- Finite-Connectivity Spin-Glass Phase Diagrams and Low Density Parity Check Codes
- Gallager error correcting codes for binary asymmetric channels
- Parallel dynamics of disordered Ising spin systems on finitely connected directed random graphs with arbitrary degree distributions
- Cavity approach for real variables on diluted graphs and application to synchronization in small-world lattices
- Tighter Decoding Reliability Bound for Gallager's Error-Correcting Code
- Spatially-Coupled MacKay-Neal Codes and Hsu-Anastasopoulos Codes
- Statistical Physics of Irregular Low-Density Parity-Check Codes
- Spin models on random graphs with controlled topologies beyond degree constraints
- Typical performance of low-density parity-check codes over general symmetric channels
- Statistical mechanics of typical set decoding
- Critical Noise Levels for LDPC decoding
- Phase transitions in the three-state Ising spin-glass model with finite connectivity
- Analysis of common attacks in LDPCC-based public-key cryptosystems
- Analyticity of the energy in an Ising spin glass with correlated disorder
- Two Lectures on Iterative Coding and Statistical Mechanics
- Spatially Coupled LDPC Codes for Decode-and-Forward in Erasure Relay Channel
- Code optimization, frozen glassy phase and improved decoding algorithms for low-density parity-check codes
- Statistical Mechanical Analysis of Low-Density Parity-Check Codes on General Markov Channel
- Statistical mechanics of LDPC codes on channels with memory
- Randomly Spread CDMA: Asymptotics via Statistical Physics
- Matrix completion based on Gaussian parameterized belief propagation
- Decision Theoretic Cutoff and ROC Analysis for Bayesian Optimal Group Testing
- Spatially-Coupled Binary MacKay-Neal Codes for Channels with Non-Binary Inputs and Affine Subspace Outputs
- Decay of Correlations for Sparse Graph Error Correcting Codes