Survey propagation for the cascading Sourlas code
arXiv:cond-mat/0604267 · doi:10.1088/0305-4470/39/34/005
Abstract
We investigate how insights from statistical physics, namely survey propagation, can improve decoding of a particular class of sparse error correcting codes. We show that a recently proposed algorithm, time averaged belief propagation, is in fact intimately linked to a specific survey propagation for which Parisi's replica symmetry breaking parameter is set to zero, and that the latter is always superior to belief propagation in the high connectivity limit. We briefly look at further improvements available by going to the second level of replica symmetry breaking.
14 pages, 5 figures
References in corpus (11)
- The Bethe lattice spin glass revisited
- The random K-satisfiability problem: from an analytic solution to an efficient algorithm
- A ferromagnet with a glass transition
- Instability of one-step replica-symmetry-broken phase in satisfiability problems
- Error-Correcting Codes That Nearly Saturate Shannon's Bound
- Propagating beliefs in spin glass models
- Spin glass models with ferromagnetically biased couplings on the Bethe lattice: analytic solutions and numerical simulations
- Cascading Parity-Check Error-Correcting Codes
- Finite size effects and error-free communication in Gaussian channels
- Replicated Bethe Free Energy: A Variational Principle behind Survey Propagation
- Survey propagation at finite temperature: application to a Sourlas code as a toy model