Abstract
An exact solution to a family of parity check error-correcting codes is provided by mapping the problem onto a Husimi cactus. The solution obtained in the thermodynamic limit recovers the replica-symmetric theory results and provides a very good approximation to finite systems of moderate size. The probability propagation decoding algorithm emerges naturally from the analysis. A phase transition between decoding success and failure phases is found to coincide with an information-theoretic upper bound. The method is employed to compare Gallager and MN codes.
| Original language | English |
|---|---|
| Pages (from-to) | 698-704 |
| Number of pages | 7 |
| Journal | Europhysics Letters |
| Volume | 51 |
| Issue number | 6 |
| DOIs | |
| Publication status | Published - 15 Sep 2000 |
Bibliographical note
Copyright of EDP SciencesKeywords
- error-correcting codes
- replica symmetric theory
- finite systems
- propagation decoding algorithm
Fingerprint Dive into the research topics of 'Error-correcting code on a cactus: A solvable model'. Together they form a unique fingerprint.
Cite this
Vicente, R., Saad, D., & Kabashima, Y. (2000). Error-correcting code on a cactus: A solvable model. Europhysics Letters, 51(6), 698-704. https://doi.org/10.1209/epl/i2000-00395-x