Statistical physics of regular low-density parity-check error-correcting codes

Tatsuto Murayama, Yoshiyuki Kabashima, David Saad, Renato Vicente

Research output: Contribution to journalArticlepeer-review


A variation of Gallager error-correcting codes is investigated using statistical mechanics. In codes of this type, a given message is encoded into a codeword that comprises Boolean sums of message bits selected by two randomly constructed sparse matrices. The similarity of these codes to Ising spin systems with random interaction makes it possible to assess their typical performance by analytical methods developed in the study of disordered systems. The typical case solutions obtained via the replica method are consistent with those obtained in simulations using belief propagation decoding. We discuss the practical implications of the results obtained and suggest a computationally efficient construction for one of the more practical configurations.
Original languageEnglish
Pages (from-to)1577-1591
Number of pages15
JournalPhysical Review E
Issue number2
Publication statusPublished - 1 Aug 2000

Bibliographical note

Funding: Support by the JSPS RFTF program, The Royal Society, and EPSRC Grant No. GR/N00562 is acknowledged.


  • Computer simulation
  • Binary symmetric channel
  • Statistical mechanics


Dive into the research topics of 'Statistical physics of regular low-density parity-check error-correcting codes'. Together they form a unique fingerprint.

Cite this