Finite connectivity systems as error-correcting codes

Renato Vicente, David Saad, Yoshiyuki Kabashima

    Research output: Contribution to journalArticlepeer-review


    We investigate the performance of parity check codes using the mapping onto spin glasses proposed by Sourlas. We study codes where each parity check comprises products of K bits selected from the original digital message with exactly C parity checks per message bit. We show, using the replica method, that these codes saturate Shannon's coding bound for <span class='mathrm'>K?8</span> when the code rate K/C is finite. We then examine the finite temperature case to asses the use of simulated annealing methods for decoding, study the performance of the finite K case and extend the analysis to accommodate different types of noisy channels. The analogy between statistical physics methods and decoding by belief propagation is also discussed.
    Original languageEnglish
    Pages (from-to)5352-5366
    Number of pages15
    JournalPhysical Review E
    Issue number5
    Publication statusPublished - Nov 1999

    Bibliographical note

    Copyright of the American Physical Society


    • parity check codes
    • mapping spin glasses
    • Sourlas
    • Shannon
    • finite temperature
    • simulated annealing methods for decoding
    • noisy channels


    Dive into the research topics of 'Finite connectivity systems as error-correcting codes'. Together they form a unique fingerprint.

    Cite this