Finite-Connectivity Spin-Glass Phase Diagrams and Low Density Parity Check Codes

Abstract

We obtain phase diagrams of regular and irregular finite connectivity spin-glasses. Contact is firstly established between properties of the phase diagram and the performances of low density parity check codes (LDPC) within the Replica Symmetric (RS) ansatz. We then study the location of the dynamical and critical transition 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, away from the Nishimori line, in the low temperature region, the location of the dynamical transition line does change within the RSB theory, in comparison with the (RS) case. For LDPC decoding over the binary erasure channel we find, at zero temperature and rate R=1/4 an RS critical transition point located at p_c = 0.67 while the critical RSB transition point is located at p_c = 0.7450, to be compared with the corresponding Shannon bound 1-R. For the binary symmetric channel (BSC) we show that the low temperature reentrant behavior of the dynamical transition line, observed within the RS ansatz, changes within the RSB theory; the location of the dynamical transition point occurring at higher values of the channel noise. Possible practical implications to improve the performances of the state-of-the-art error correcting codes are discussed.

21 pages, 15 figures

References in corpus (17)

• The Bethe lattice spin glass revisited
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Optimisation problems and replica symmetry breaking in finite connectivity spin-glasses
• The Nishimori line and Bayesian Statistics
• The glassy phase of Gallager codes
• Exact solutions for diluted spin glasses and optimization problems
• The Statistical Physics of Regular Low-Density Parity-Check Error-Correcting Codes
• The Dynamic Phase Transition for Decoding Algorithms
• Finite-connectivity systems as error-correcting codes
• Domain-Wall Energies and Magnetization of the Two-Dimensional Random-Bond Ising Model
• Statistical Mechanics of Low-Density Parity Check Error-Correcting Codes over Galois Fields
• Spin glass models with ferromagnetically biased couplings on the Bethe lattice: analytic solutions and numerical simulations
• Multicritical Point Relations in Three Dual Pairs of Hierarchical-Lattice Ising Spin-Glasses
• Finite size effects and error-free communication in Gaussian channels
• Typical performance of low-density parity-check codes over general symmetric channels
• Critical Noise Levels for LDPC decoding
• Replicated Bethe Free Energy: A Variational Principle behind Survey Propagation

Cited by in corpus (6)

• Gallager error correcting codes for binary asymmetric channels
• Statistical Mechanics Analysis of LDPC Coding in MIMO Gaussian Channels
• Cavity approach to the Sourlas code system
• Code optimization, frozen glassy phase and improved decoding algorithms for low-density parity-check codes
• Spin-glass behaviour on random lattices
• Statistical mechanics of LDPC codes on channels with memory