Finite-connectivity systems as error-correcting codes

Abstract

We investigate the performance of parity check codes using the mapping onto Ising spin systems proposed by Sourlas. We study codes where each parity check comprises products of K bits selected from the original digital message with exactly C checks per message bit. We show, using the replica method, that these codes saturate Shannon's coding bound for $K\to \infty$ when the code rate K/C is finite. We then examine the finite temperature case to asses the use of simulated annealing methods for decoding, study the performance of the finite K case and extend the analysis to accommodate different types of noisy channels. The connection between statistical physics and belief propagation decoders is discussed and the dynamics of the decoding itself is analyzed. Further insight into new approaches for improving the code performance is given.

32 pages, 12 figures, to appear in PRE

References in corpus (1)

• The Nishimori line and Bayesian Statistics

Cited by in corpus (19)

• 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
• Error-correcting code on a cactus: a solvable model
• The Cavity Approach to Parallel Dynamics of Ising Spins on a Graph
• Finite-Connectivity Spin-Glass Phase Diagrams and Low Density Parity Check Codes
• Gallager error correcting codes for binary asymmetric channels
• Parallel dynamics of disordered Ising spin systems on finitely connected directed random graphs with arbitrary degree distributions
• The Little-Hopfield model on a Random Graph
• Cascading Parity-Check Error-Correcting Codes
• Average and reliability error exponents in low-density parity-check codes
• Statistical Physics of Irregular Low-Density Parity-Check Codes
• Typical performance of low-density parity-check codes over general symmetric channels
• Cavity approach to the Sourlas code system
• Optimal Resource Allocation in Random Networks with Transportation Bandwidths
• Survey propagation at finite temperature: application to a Sourlas code as a toy model
• Statistical mechanics of LDPC codes on channels with memory
• Rate Distortion Theorem and the Multicritical Point of Spin Glass
• Statistical mechanical analysis of a hierarchical random code ensemble in signal processing