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

Tatsuto Murayama; Yoshiyuki Kabashima; David Saad; Renato Vicente

doi:10.1103/PhysRevE.62.1577

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

Tatsuto Murayama, Yoshiyuki Kabashima, David Saad, Renato Vicente

College of Engineering and Physical Sciences

Research output: Contribution to journal › Article › peer-review

Abstract

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 language	English
Pages (from-to)	1577-1591
Number of pages	15
Journal	Physical Review E
Volume	62
Issue number	2
DOIs	https://doi.org/10.1103/PhysRevE.62.1577
Publication status	Published - 1 Aug 2000

Bibliographical note

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

Keywords

Computer simulation
Binary symmetric channel
Statistical mechanics

Access to Document

10.1103/PhysRevE.62.1577

Cite this

@article{5eace182843246a1ae80f8cb4c63721f,

title = "Statistical physics of regular low-density parity-check error-correcting codes",

abstract = "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.",

keywords = "Computer simulation, Binary symmetric channel, Statistical mechanics",

author = "Tatsuto Murayama and Yoshiyuki Kabashima and David Saad and Renato Vicente",

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

year = "2000",

month = aug,

day = "1",

doi = "10.1103/PhysRevE.62.1577",

language = "English",

volume = "62",

pages = "1577--1591",

journal = "Physical Review E",

issn = "1063-651X",

publisher = "American Physical Society",

number = "2 ",

}

TY - JOUR

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

AU - Murayama, Tatsuto

AU - Kabashima, Yoshiyuki

AU - Saad, David

AU - Vicente, Renato

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

PY - 2000/8/1

Y1 - 2000/8/1

N2 - 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.

AB - 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.

KW - Computer simulation

KW - Binary symmetric channel

KW - Statistical mechanics

UR - http://www.scopus.com/inward/record.url?scp=0034239179&partnerID=8YFLogxK

UR - https://journals.aps.org/pre/abstract/10.1103/PhysRevE.62.1577

U2 - 10.1103/PhysRevE.62.1577

DO - 10.1103/PhysRevE.62.1577

M3 - Article

AN - SCOPUS:0034239179

SN - 1063-651X

VL - 62

SP - 1577

EP - 1591

JO - Physical Review E

JF - Physical Review E

IS - 2

ER -

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

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this