Error-correcting code on a cactus:A solvable model


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.

Publication DOI:
Divisions: College of Engineering & Physical Sciences > Systems analytics research institute (SARI)
Additional Information: Copyright of EDP Sciences
Uncontrolled Keywords: error-correcting codes,replica symmetric theory,finite systems,propagation decoding algorithm,Physics and Astronomy(all)
Publication ISSN: 1286-4854
Last Modified: 06 May 2024 07:07
Date Deposited: 10 Aug 2009 15:25
Full Text Link:
Related URLs: http://www.scop ... tnerID=8YFLogxK (Scopus URL)
http://iopscien ... ect=.iopscience (Publisher URL)
PURE Output Type: Article
Published Date: 2000-09-15
Authors: Vicente, Renato
Saad, David (ORCID Profile 0000-0001-9821-2623)
Kabashima, Yoshiyuki



Version: Accepted Version

Export / Share Citation


Additional statistics for this record