Statistical physics of regular low-density parity-check error-correcting codes
- 1 August 2000
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 62 (2) , 1577-1591
- https://doi.org/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 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.Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- Finite-size effects and error-free communication in Gaussian channelsJournal of Physics A: General Physics, 2000
- Typical Performance of Gallager-Type Error-Correcting CodesPhysical Review Letters, 2000
- Error-Correcting Codes That Nearly Saturate Shannon's BoundPhysical Review Letters, 1999
- Good error-correcting codes based on very sparse matricesIEEE Transactions on Information Theory, 1999
- Comparison of constructions of irregular Gallager codesIEEE Transactions on Communications, 1999
- Statistical mechanics of error-correcting codesEurophysics Letters, 1999
- Belief propagation vs. TAP for decoding corrupted messagesEurophysics Letters, 1998
- Near Shannon limit performance of low density paritycheck codesElectronics Letters, 1997
- Solution of 'Solvable model of a spin glass'Philosophical Magazine, 1977
- Low-density parity-check codesIEEE Transactions on Information Theory, 1962