The glassy phase of Gallager codes

Abstract

Gallager codes are the best error-correcting codes to-date. In this paper we study them by using the tools of statistical mechanics. The corresponding statistical mechanics model is a spin model on a sparse random graph. The model can be solved by elementary methods (i.e. without replicas) in a large connectivity limit. For low enough temperatures it presents a completely frozen glassy phase (q_{EA}=1). The same scenario is shown to hold for finite connectivities. In this case we adopt the replica approach and exhibit a one-step replica symmetry breaking order parameter. We argue that our ansatz yields the exact solution of the model. This allows us to determine the whole phase diagram and to understand the performances of Gallager codes.

27 pages, 8 eps figures

References in corpus (1)

• Exact solutions for diluted spin glasses and optimization problems

Cited by in corpus (36)

• Cellular Automata Models of Road Traffic
• Clustering of solutions in the random satisfiability problem
• Loop series for discrete statistical models on graphs
• Tight bounds for LDPC and LDGM codes under MAP decoding
• The Dynamic Phase Transition for Decoding Algorithms
• Diagnosis of weaknesses in modern error correction codes: a physics approach
• Pairs of SAT Assignment in Random Boolean Formulae
• Random multi-index matching problems
• Random subcubes as a toy model for constraint satisfaction problems
• Finite-Connectivity Spin-Glass Phase Diagrams and Low Density Parity Check Codes
• Sharp Bounds for Optimal Decoding of Low Density Parity Check Codes
• Gallager error correcting codes for binary asymmetric channels
• A frozen glass phase in the multi-index matching problem
• Average and reliability error exponents in low-density parity-check codes
• On the Asymptotic Weight and Stopping Set Distribution of Regular LDPC Ensembles
• Unsupervised feature learning from finite data by message passing: discontinuous versus continuous phase transition
• Statistical mechanics of error exponents for error-correcting codes
• Typical performance of low-density parity-check codes over general symmetric channels
• Critical Noise Levels for LDPC decoding
• Spatial Coupling as a Proof Technique
• Clustering in Hilbert space of a quantum optimization problem
• New Understanding of the Bethe Approximation and the Replica Method
• The random energy model in a magnetic field and joint source-channel coding
• Two Lectures on Iterative Coding and Statistical Mechanics
• Analyticity of the energy in an Ising spin glass with correlated disorder
• An exactly solvable random satisfiability problem
• Code optimization, frozen glassy phase and improved decoding algorithms for low-density parity-check codes
• Magnetization enumerator of real-valued symmetric channels in Gallager error-correcting codes
• Statistical Mechanical Analysis of Low-Density Parity-Check Codes on General Markov Channel
• Cumulative Distance Enumerators of Random Codes and their Thresholds
• The Generalized Area Theorem and Some of its Consequences
• Applications of correlation inequalities to low density graphical codes
• Tight Bounds on the Capacity of Binary Input random CDMA Systems
• Statistical mechanical analysis of a hierarchical random code ensemble in signal processing
• Relations between random coding exponents and the statistical physics of random codes
• Upper Bound on Error Exponent of Regular LDPC Codes Transmitted over the BEC