Error-correcting code on a cactus: A solvable model

Renato Vicente, David Saad, Yoshiyuki Kabashima

    Research output: Contribution to journalArticlepeer-review


    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.

    Original languageEnglish
    Pages (from-to)698-704
    Number of pages7
    JournalEurophysics Letters
    Issue number6
    Publication statusPublished - 15 Sept 2000

    Bibliographical note

    Copyright of EDP Sciences


    • error-correcting codes
    • replica symmetric theory
    • finite systems
    • propagation decoding algorithm


    Dive into the research topics of 'Error-correcting code on a cactus: A solvable model'. Together they form a unique fingerprint.

    Cite this