Finite connectivity systems as error-correcting codes

Vicente, Renato, Saad, David and Kabashima, Yoshiyuki (1999). Finite connectivity systems as error-correcting codes. Physical Review E, 60 (5), pp. 5352-5366.

Abstract

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: https://doi.org/10.1103/PhysRevE.60.5352
Divisions: Engineering & Applied Sciences > Mathematics
Engineering & Applied 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
Full Text Link:
Related URLs: http://www.scop ... tnerID=8YFLogxK (Scopus URL)
http://link.aps ... hysRevE.60.5352 (Publisher URL)
Published Date: 1999-11
Authors: Vicente, Renato
Saad, David ( 0000-0001-9821-2623)
Kabashima, Yoshiyuki

Download

[img]

Version: Accepted Version


Export / Share Citation


Statistics

Additional statistics for this record