1999/04/30 by Renato Vicente, David Saad, Yoshiyuki Kabashima · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Physics and Astronomy · #DNA and Biological Computing #Error Correcting Code Techniques #Quantum Computing Algorithms and Architecture #cond-mat.dis-nn
paper · pdf · doi:10.1103/physreve.60.5352
published as Phys. Rev. E 60 5352-5366 (1999) · 32 pages, 12 figures, to appear in PRE
arxiv created 1999/08/20 · openalex publication_date 1999/11/01 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We investigate the performance of parity check codes using the mapping onto Ising spin systems proposed by Sourlas [Nature (London) 339, 693 (1989); Europhys. Lett. 25, 159 (1994)]. 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-->infinity when the code rate K/C is finite. We then examine the finite temperature case to assess 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.