Finite connectivity systems as error-correcting codes

Renato Vicente, David Saad, Yoshiyuki Kabashima

Research output: Contribution to journalArticle

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.
Original languageEnglish
Pages (from-to)5352-5366
Number of pages15
JournalPhysical Review E
Volume60
Issue number5
DOIs
Publication statusPublished - Nov 1999

Bibliographical note

Copyright of the American Physical Society

Keywords

  • parity check codes
  • mapping spin glasses
  • Sourlas
  • Shannon
  • finite temperature
  • simulated annealing methods for decoding
  • noisy channels

Fingerprint Dive into the research topics of 'Finite connectivity systems as error-correcting codes'. Together they form a unique fingerprint.

  • Cite this