Finite connectivity systems as error-correcting codes

Renato Vicente, David Saad, Yoshiyuki Kabashima

Research output: Contribution to journalArticlepeer-review

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