Code optimization, frozen glassy phase and improved decoding algorithms for low-density parity-check codes

Abstract

The statistical physics properties of low-density parity-check codes for the binary symmetric channel are investigated as a spin glass problem with multi-spin interactions and quenched random fields by the cavity method. By evaluating the entropy function at the Nishimori temperature, we find that irregular constructions with heterogeneous degree distribution of check (bit) nodes have higher decoding thresholds compared to regular counterparts with homogeneous degree distribution. We also show that the instability of the mean-field calculation takes place only after the entropy crisis, suggesting the presence of a frozen glassy phase at low temperatures. When no prior knowledge of channel noise is assumed (searching for the ground state), we find that a reinforced strategy on normal belief propagation will boost the decoding threshold to a higher value than the normal belief propagation. This value is close to the dynamical transition where all local search heuristics fail to identify the true message (codeword or the ferromagnetic state). After the dynamical transition, the number of metastable states with larger energy density (than the ferromagnetic state) becomes exponentially numerous. When the noise level of the transmission channel approaches the static transition point, there starts to exist exponentially numerous codewords sharing the identical ferromagnetic energy.

12 pages, 6 figures, revised

References in corpus (24)

• The Bethe lattice spin glass revisited
• The structural glass transition and the entropy of the metastable states
• Statistical mechanics of image restoration and error-correcting codes
• The glassy phase of Gallager codes
• Typical Performance of Gallager-type Error-Correcting Codes
• The Statistical Physics of Regular Low-Density Parity-Check Error-Correcting Codes
• The Dynamic Phase Transition for Decoding Algorithms
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• Origin of the computational hardness for learning with binary synapses
• Error-Correcting Codes That Nearly Saturate Shannon's Bound
• Random multi-index matching problems
• On the number of circuits in random graphs
• Finite-Connectivity Spin-Glass Phase Diagrams and Low Density Parity Check Codes
• Gallager error correcting codes for binary asymmetric channels
• Minimizing energy below the glass thresholds
• Statistical Physics of Irregular Low-Density Parity-Check Codes
• Statistical mechanics of error exponents for error-correcting codes
• Typical performance of low-density parity-check codes over general symmetric channels
• Statistical mechanics of typical set decoding
• $T\to 0$ mean-field population dynamics approach for the random 3-satisfiability problem
• Critical Noise Levels for LDPC decoding
• Efficient data compression from statistical physics of codes over finite fields
• Cavity approach to the Sourlas code system
• Survey propagation at finite temperature: application to a Sourlas code as a toy model

Cited by in corpus (1)

• Unsupervised feature learning from finite data by message passing: discontinuous versus continuous phase transition