2000/05/30 by Renato Vicente, David Saad, Yoshiyuki Kabashima · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Physics and Astronomy · #Cellular Automata and Applications #DNA and Biological Computing #Error Correcting Code Techniques #cond-mat.dis-nn
paper · pdf · doi:10.1209/epl/i2000-00395-x
published as Europhys. Lett. 51 (2000), 698-704 · 7 pages, 3 figures, with minor corrections
arxiv created 2000/05/30 · openalex publication_date 2000/09/15 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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.