Error-correcting code on a cactus: A solvable model

Renato Vicente, David Saad, Yoshiyuki Kabashima

Research output: Contribution to journalArticle

Abstract

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
Volume51
Issue number6
DOIs
Publication statusPublished - 15 Sep 2000

Bibliographical note

Copyright of EDP Sciences

Keywords

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

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

  • Cite this