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 language | English |
|---|---|
| Pages (from-to) | 698-704 |
| Number of pages | 7 |
| Journal | Europhysics Letters |
| Volume | 51 |
| Issue number | 6 |
| DOIs | |
| Publication status | Published - 15 Sep 2000 |
Fingerprint
Bibliographical note
Copyright of EDP SciencesKeywords
- error-correcting codes
- replica symmetric theory
- finite systems
- propagation decoding algorithm
Cite this
}
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 journal › Article
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 -