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

Fingerprint

error correcting codes
decoding
replicas
parity
thermodynamics
propagation
approximation

Bibliographical note

Copyright of EDP Sciences

Keywords

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

Cite this

Vicente, Renato ; Saad, David ; Kabashima, Yoshiyuki. / Error-correcting code on a cactus : A solvable model. In: Europhysics Letters. 2000 ; Vol. 51, No. 6. pp. 698-704.
@article{70d9f78aa03147bc900afdd292aaebd0,
title = "Error-correcting code on a cactus: A solvable model",
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.",
keywords = "error-correcting codes, replica symmetric theory, finite systems, propagation decoding algorithm",
author = "Renato Vicente and David Saad and Yoshiyuki Kabashima",
note = "Copyright of EDP Sciences",
year = "2000",
month = "9",
day = "15",
doi = "10.1209/epl/i2000-00395-x",
language = "English",
volume = "51",
pages = "698--704",
journal = "Europhysics Letters",
issn = "0295-5075",
publisher = "IOP Publishing Ltd.",
number = "6",

}

Error-correcting code on a cactus : A solvable model. / Vicente, Renato; Saad, David; Kabashima, Yoshiyuki.

In: Europhysics Letters, Vol. 51, No. 6, 15.09.2000, p. 698-704.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Error-correcting code on a cactus

T2 - A solvable model

AU - Vicente, Renato

AU - Saad, David

AU - Kabashima, Yoshiyuki

N1 - Copyright of EDP Sciences

PY - 2000/9/15

Y1 - 2000/9/15

N2 - 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.

AB - 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.

KW - error-correcting codes

KW - replica symmetric theory

KW - finite systems

KW - propagation decoding algorithm

UR - http://www.scopus.com/inward/record.url?scp=0034637725&partnerID=8YFLogxK

UR - http://iopscience.iop.org/0295-5075/51/6/698/?ejredirect=.iopscience

U2 - 10.1209/epl/i2000-00395-x

DO - 10.1209/epl/i2000-00395-x

M3 - Article

VL - 51

SP - 698

EP - 704

JO - Europhysics Letters

JF - Europhysics Letters

SN - 0295-5075

IS - 6

ER -