Finite connectivity systems as error-correcting codes


We investigate the performance of parity check codes using the mapping onto spin glasses proposed by Sourlas. We study codes where each parity check comprises products of K bits selected from the original digital message with exactly C parity checks per message bit. We show, using the replica method, that these codes saturate Shannon's coding bound for <span class='mathrm'>K?8</span> 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 analogy between statistical physics methods and decoding by belief propagation is also discussed.

Publication DOI:
Divisions: College of Engineering & Physical Sciences > Systems analytics research institute (SARI)
Additional Information: Copyright of the American Physical Society
Uncontrolled Keywords: parity check codes,mapping spin glasses,Sourlas,Shannon,finite temperature,simulated annealing methods for decoding,noisy channels,Physics and Astronomy(all),Condensed Matter Physics,Statistical and Nonlinear Physics,Mathematical Physics
Publication ISSN: 1550-2376
Last Modified: 16 Jan 2024 08:03
Date Deposited: 30 Jul 2009 09:57
Full Text Link:
Related URLs: http://www.scop ... tnerID=8YFLogxK (Scopus URL)
http://link.aps ... hysRevE.60.5352 (Publisher URL)
PURE Output Type: Article
Published Date: 1999-11
Authors: Vicente, Renato
Saad, David (ORCID Profile 0000-0001-9821-2623)
Kabashima, Yoshiyuki



Version: Accepted Version

Export / Share Citation


Additional statistics for this record