Typical Performance of Gallager-type Error-Correcting Codes
arXiv:cond-mat/9908104 · doi:10.1103/PhysRevLett.84.1355
Abstract
The performance of Gallager's error-correcting code is investigated via methods of statistical physics. In this approach, the transmitted codeword comprises products of the original message bits selected by two randomly-constructed sparse matrices; the number of non-zero row/column elements in these matrices constitutes a family of codes. We show that Shannon's channel capacity is saturated for many of the codes while slightly lower performance is obtained for others which may be of higher practical relevance. Decoding aspects are considered by employing the TAP approach which is identical to the commonly used belief-propagation-based decoding.
6 pages, latex, 1 figure
References in corpus (2)
Cited by in corpus (40)
- Exact solutions for diluted spin glasses and optimization problems
- Tight bounds for LDPC and LDGM codes under MAP decoding
- The Statistical Physics of Regular Low-Density Parity-Check Error-Correcting Codes
- The Dynamic Phase Transition for Decoding Algorithms
- Error-correcting code on a cactus: a solvable model
- Phase Transitions in Quantum Pattern Recognition
- Statistical mechanics of lossy data compression using a non-monotonic perceptron
- Statistical Mechanics of Low-Density Parity Check Error-Correcting Codes over Galois Fields
- Cryptographical Properties of Ising Spin Systems
- Random Graph Coloring - a Statistical Physics Approach
- Sharp Bounds for Optimal Decoding of Low Density Parity Check Codes
- Propagating beliefs in spin glass models
- Transient dynamics for sequence processing neural networks
- Tighter Decoding Reliability Bound for Gallager's Error-Correcting Code
- One step RSB scheme for the rate distortion function
- Stochastic dynamics of lexicon learning in an uncertain and nonuniform world
- Statistical Physics of Irregular Low-Density Parity-Check Codes
- Finite size effects and error-free communication in Gaussian channels
- Typical performance of low-density parity-check codes over general symmetric channels
- Statistical mechanics of lossy compression using multilayer perceptrons
- Statistical mechanics of typical set decoding
- Statistical mechanical analysis of sparse linear regression as a variable selection problem
- Critical Noise Levels for LDPC decoding
- Statistical mechanics of lossy compression for non-monotonic multilayer perceptrons
- Statistical Mechanics of Broadcast Channels Using Low Density Parity Check Codes
- Spatial Coupling as a Proof Technique
- High-Capacity Quantum Associative Memories
- Analysis of common attacks in LDPCC-based public-key cryptosystems
- Statistical Mechanics and Capacity-Approaching Error-Correcting Codes
- Parallel vs. Sequential Belief Propagation Decoding of LDPC Codes over GF(q) and Markov Sources
- Slowly evolving random graphs II: Adaptive geometry in finite-connectivity Hopfield models
- Analyticity of the energy in an Ising spin glass with correlated disorder
- Magnetization enumerator of real-valued symmetric channels in Gallager error-correcting codes
- Code optimization, frozen glassy phase and improved decoding algorithms for low-density parity-check codes
- Error-correcting codes on scale-free networks
- Belief Propagation for Error Correcting Codes and Lossy Compression Using Multilayer Perceptrons
- Parallel dynamics of continuous Hopfield model revisited
- Error correcting code using tree-like multilayer perceptron
- Weight vs Magnetization Enumerator for Gallager Codes
- Statistical mechanical analysis of a hierarchical random code ensemble in signal processing