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.

Divisions: College of Engineering & Physical Sciences > Systems analytics research institute (SARI)
Additional Information: Copyright of EDP Sciences
Publication ISSN: 1286-4854
Last Modified: 29 Nov 2023 10:01
Date Deposited: 10 Aug 2009 15:25
Full Text Link: 10.1209/epl/i2000-00395-x
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
Kabashima, Yoshiyuki



Version: Accepted Version

Export / Share Citation


Additional statistics for this record