The Dynamic Phase Transition for Decoding Algorithms

Abstract

The state-of-the-art error correcting codes are based on large random constructions (random graphs, random permutations, ...) and are decoded by linear-time iterative algorithms. Because of these features, they are remarkable examples of diluted mean-field spin glasses, both from the static and from the dynamic points of view. We analyze the behavior of decoding algorithms using the mapping onto statistical-physics models. This allows to understand the intrinsic (i.e. algorithm independent) features of this behavior.

40 pages, 29 eps figures

References in corpus (3)

• A ferromagnet with a glass transition
• The glassy phase of Gallager codes
• Exact solutions for diluted spin glasses and optimization problems

Cited by in corpus (27)

• Tight bounds for LDPC and LDGM codes under MAP decoding
• On the cooling-schedule dependence of the dynamics of mean-field glasses
• Replica bounds for diluted non-Poissonian spin systems
• Pairs of SAT Assignment in Random Boolean Formulae
• Life Above Threshold: From List Decoding to Area Theorem and MSE
• Finite-Connectivity Spin-Glass Phase Diagrams and Low Density Parity Check Codes
• Gallager error correcting codes for binary asymmetric channels
• Average and reliability error exponents in 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
• Approximate analysis of search algorithms with "physical" methods
• Statistical Mechanics Analysis of LDPC Coding in MIMO Gaussian Channels
• Spatial Coupling as a Proof Technique
• Cavity approach to the Sourlas code system
• Survey propagation at finite temperature: application to a Sourlas code as a toy model
• Analysis of common attacks in LDPCC-based public-key cryptosystems
• The random energy model in a magnetic field and joint source-channel coding
• Analyticity of the energy in an Ising spin glass with correlated disorder
• Two Lectures on Iterative Coding and Statistical Mechanics
• Magnetization enumerator of real-valued symmetric channels in Gallager error-correcting codes
• Code optimization, frozen glassy phase and improved decoding algorithms for low-density parity-check codes
• Error-correcting codes on scale-free networks
• Optimization and Physics: On the satisfiability of random Boolean formulae
• Gradient dynamics in reinforcement learning
• Error Exponents of Low-Density Parity-Check Codes on the Binary Erasure Channel
• The closest vector problem and the zero-temperature p-spin landscape for lossy compression
• Relations between random coding exponents and the statistical physics of random codes