Finite-connectivity spin-glass phase diagrams and low-density parity check codes

Migliorini, Gabriele and Saad, David (2006). Finite-connectivity spin-glass phase diagrams and low-density parity check codes. Physical Review E, 73 (2),

Abstract

We obtain phase diagrams of regular and irregular finite-connectivity spin glasses. Contact is first established between properties of the phase diagram and the performance of low-density parity check (LDPC) codes within the replica symmetric (RS) ansatz. We then study the location of the dynamical and critical transition points of these systems within the one step replica symmetry breaking theory (RSB), extending similar calculations that have been performed in the past for the Bethe spin-glass problem. We observe that the location of the dynamical transition line does change within the RSB theory, in comparison with the results obtained in the RS case. For LDPC decoding of messages transmitted over the binary erasure channel we find, at zero temperature and rate R=14, an RS critical transition point at pc 0.67 while the critical RSB transition point is located at pc 0.7450±0.0050, to be compared with the corresponding Shannon bound 1-R. For the binary symmetric channel we show that the low temperature reentrant behavior of the dynamical transition line, observed within the RS ansatz, changes its location when the RSB ansatz is employed; the dynamical transition point occurs at higher values of the channel noise. Possible practical implications to improve the performance of the state-of-the-art error correcting codes are discussed. © 2006 The American Physical Society.

Publication DOI: https://doi.org/10.1103/PhysRevE.73.026122
Divisions: Engineering & Applied Sciences > Mathematics
Engineering & Applied Sciences > Systems analytics research institute (SARI)
Additional Information: Copyright of the American Physical Society
Uncontrolled Keywords: finite connectivity spin-glasses,low density parity check codes,Replica Symmetric,replica symmetry breaking theory,Physics and Astronomy(all),Condensed Matter Physics,Statistical and Nonlinear Physics,Mathematical Physics
Full Text Link:
Related URLs: http://www.scop ... tnerID=8YFLogxK (Scopus URL)
http://link.aip ... 002026122000001 (Publisher URL)
Published Date: 2006-03-02
Authors: Migliorini, Gabriele
Saad, David ( 0000-0001-9821-2623)

Download

[img]

Version: Published Version


Export / Share Citation


Statistics

Additional statistics for this record