Low density parity check codes: a statistical physics perspective

Renato Vicente, David Saad, Yoshiyuki Kabashima

Research output: Chapter in Book/Report/Conference proceedingChapter (peer-reviewed)

Abstract

The modem digital communication systems are made transmission reliable by employing error correction technique for the redundancies. Codes in the low-density parity-check work along the principles of Hamming code, and the parity-check matrix is very sparse, and multiple errors can be corrected. The sparseness of the matrix allows for the decoding process to be carried out by probability propagation methods similar to those employed in Turbo codes. The relation between spin systems in statistical physics and digital error correcting codes is based on the existence of a simple isomorphism between the additive Boolean group and the multiplicative binary group. Shannon proved general results on the natural limits of compression and error-correction by setting up the framework known as information theory. Error-correction codes are based on mapping the original space of words onto a higher dimensional space in such a way that the typical distance between encoded words increases.
Original languageEnglish
Title of host publicationAdvances in electronics and electron physics
EditorsPeter W. Hawkes
PublisherElsevier
Pages231-353
Number of pages123
Volume125
ISBN (Electronic)978-0-12-804815-3
ISBN (Print)978-0-12014767-0, 012014767X
DOIs
Publication statusPublished - 2002

Publication series

NameAdvances in Imaging and Electron Physics
Volume125
ISSN (Print)1076-5670

Fingerprint

parity
physics
error correcting codes
pulse communication
modems
isomorphism
information theory
redundancy
decoding
matrices
telecommunication
propagation

Bibliographical note

Copyright of Academic Press part of Elsevier Science

Keywords

  • error-corrective codes
  • replica-symmetry-breaking
  • random energy model
  • finite-connectivity systems
  • spin-glasses
  • belief propagation
  • sparse matrices
  • solvable model
  • turbo codes
  • phase

Cite this

Vicente, R., Saad, D., & Kabashima, Y. (2002). Low density parity check codes: a statistical physics perspective. In P. W. Hawkes (Ed.), Advances in electronics and electron physics (Vol. 125, pp. 231-353). (Advances in Imaging and Electron Physics; Vol. 125). Elsevier. https://doi.org/10.1016/S1076-5670(02)80018-0
Vicente, Renato ; Saad, David ; Kabashima, Yoshiyuki. / Low density parity check codes: a statistical physics perspective. Advances in electronics and electron physics. editor / Peter W. Hawkes. Vol. 125 Elsevier, 2002. pp. 231-353 (Advances in Imaging and Electron Physics).
@inbook{418d634d9b3e4ba48ef23a50964a11cb,
title = "Low density parity check codes: a statistical physics perspective",
abstract = "The modem digital communication systems are made transmission reliable by employing error correction technique for the redundancies. Codes in the low-density parity-check work along the principles of Hamming code, and the parity-check matrix is very sparse, and multiple errors can be corrected. The sparseness of the matrix allows for the decoding process to be carried out by probability propagation methods similar to those employed in Turbo codes. The relation between spin systems in statistical physics and digital error correcting codes is based on the existence of a simple isomorphism between the additive Boolean group and the multiplicative binary group. Shannon proved general results on the natural limits of compression and error-correction by setting up the framework known as information theory. Error-correction codes are based on mapping the original space of words onto a higher dimensional space in such a way that the typical distance between encoded words increases.",
keywords = "error-corrective codes, replica-symmetry-breaking, random energy model, finite-connectivity systems, spin-glasses, belief propagation, sparse matrices, solvable model, turbo codes, phase",
author = "Renato Vicente and David Saad and Yoshiyuki Kabashima",
note = "Copyright of Academic Press part of Elsevier Science",
year = "2002",
doi = "10.1016/S1076-5670(02)80018-0",
language = "English",
isbn = "978-0-12014767-0",
volume = "125",
series = "Advances in Imaging and Electron Physics",
publisher = "Elsevier",
pages = "231--353",
editor = "Hawkes, {Peter W.}",
booktitle = "Advances in electronics and electron physics",
address = "Netherlands",

}

Vicente, R, Saad, D & Kabashima, Y 2002, Low density parity check codes: a statistical physics perspective. in PW Hawkes (ed.), Advances in electronics and electron physics. vol. 125, Advances in Imaging and Electron Physics, vol. 125, Elsevier, pp. 231-353. https://doi.org/10.1016/S1076-5670(02)80018-0

Low density parity check codes: a statistical physics perspective. / Vicente, Renato; Saad, David; Kabashima, Yoshiyuki.

Advances in electronics and electron physics. ed. / Peter W. Hawkes. Vol. 125 Elsevier, 2002. p. 231-353 (Advances in Imaging and Electron Physics; Vol. 125).

Research output: Chapter in Book/Report/Conference proceedingChapter (peer-reviewed)

TY - CHAP

T1 - Low density parity check codes: a statistical physics perspective

AU - Vicente, Renato

AU - Saad, David

AU - Kabashima, Yoshiyuki

N1 - Copyright of Academic Press part of Elsevier Science

PY - 2002

Y1 - 2002

N2 - The modem digital communication systems are made transmission reliable by employing error correction technique for the redundancies. Codes in the low-density parity-check work along the principles of Hamming code, and the parity-check matrix is very sparse, and multiple errors can be corrected. The sparseness of the matrix allows for the decoding process to be carried out by probability propagation methods similar to those employed in Turbo codes. The relation between spin systems in statistical physics and digital error correcting codes is based on the existence of a simple isomorphism between the additive Boolean group and the multiplicative binary group. Shannon proved general results on the natural limits of compression and error-correction by setting up the framework known as information theory. Error-correction codes are based on mapping the original space of words onto a higher dimensional space in such a way that the typical distance between encoded words increases.

AB - The modem digital communication systems are made transmission reliable by employing error correction technique for the redundancies. Codes in the low-density parity-check work along the principles of Hamming code, and the parity-check matrix is very sparse, and multiple errors can be corrected. The sparseness of the matrix allows for the decoding process to be carried out by probability propagation methods similar to those employed in Turbo codes. The relation between spin systems in statistical physics and digital error correcting codes is based on the existence of a simple isomorphism between the additive Boolean group and the multiplicative binary group. Shannon proved general results on the natural limits of compression and error-correction by setting up the framework known as information theory. Error-correction codes are based on mapping the original space of words onto a higher dimensional space in such a way that the typical distance between encoded words increases.

KW - error-corrective codes

KW - replica-symmetry-breaking

KW - random energy model

KW - finite-connectivity systems

KW - spin-glasses

KW - belief propagation

KW - sparse matrices

KW - solvable model

KW - turbo codes

KW - phase

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

UR - https://www.sciencedirect.com/science/article/pii/S1076567002800180?via%3Dihub

U2 - 10.1016/S1076-5670(02)80018-0

DO - 10.1016/S1076-5670(02)80018-0

M3 - Chapter (peer-reviewed)

SN - 978-0-12014767-0

SN - 012014767X

VL - 125

T3 - Advances in Imaging and Electron Physics

SP - 231

EP - 353

BT - Advances in electronics and electron physics

A2 - Hawkes, Peter W.

PB - Elsevier

ER -

Vicente R, Saad D, Kabashima Y. Low density parity check codes: a statistical physics perspective. In Hawkes PW, editor, Advances in electronics and electron physics. Vol. 125. Elsevier. 2002. p. 231-353. (Advances in Imaging and Electron Physics). https://doi.org/10.1016/S1076-5670(02)80018-0