Error-correcting code on a cactus: A solvable model
The Neural Computing Research Group, Aston University - Birmingham B4 7ET, UK
2 Department of Computational Intelligence and Systems Science Tokyo Institute of Technology, Yokohama 2268502, Japan
Accepted: 21 July 2000
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.
PACS: 89.90.+n – Other topics of general interest to physicists / 89.70.+c – Information science / 05.50.+q – Lattice theory and statistics (Ising, Potts, etc.)
© EDP Sciences, 2000