Error-correcting code on a cactus: a solvable model

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.

7 pages, 3 figures, with minor corrections

References in corpus (5)

• Typical Performance of Gallager-type Error-Correcting Codes
• The Statistical Physics of Regular Low-Density Parity-Check Error-Correcting Codes
• Error-Correcting Codes That Nearly Saturate Shannon's Bound
• Finite-connectivity systems as error-correcting codes
• Finite size effects and error-free communication in Gaussian channels

Cited by in corpus (6)

• The Dynamic Phase Transition for Decoding Algorithms
• Statistical Mechanics of Low-Density Parity Check Error-Correcting Codes over Galois Fields
• Propagating beliefs in spin glass models
• Typical performance of low-density parity-check codes over general symmetric channels
• Critical Noise Levels for LDPC decoding
• Typical kernel size and number of sparse random matrices over GF(q) - a statistical physics approach