Statistical physics of low density parity check error correcting codes

David Saad; Yoshiyuki Kabashima; Tatsuto Murayama; Renato Vicente

doi:10.1007/3-540-45325-3_27

Statistical physics of low density parity check error correcting codes

David Saad, Yoshiyuki Kabashima, Tatsuto Murayama, Renato Vicente

Research output: Chapter in Book/Published conference output › Chapter

Abstract

We study the performance of Low Density Parity Check (LDPC) error-correcting codes using the methods of statistical physics. LDPC codes are based on the generation of codewords using Boolean sums of the original message bits by employing two randomly-constructed sparse matrices. These codes can be mapped onto Ising spin models and studied using common methods of statistical physics. We examine various regular constructions and obtain insight into their theoretical and practical limitations. We also briefly report on results obtained for irregular code constructions, for codes with non-binary alphabet, and on how a finite system size effects the error probability.

Original language	English
Title of host publication	Cryptography and Coding
Editors	B. Honary
Place of Publication	Berlin / Heidelberg
Publisher	Springer
Pages	307-316
Number of pages	10
Volume	2260
ISBN (Print)	9783540430261
DOIs	https://doi.org/10.1007/3-540-45325-3_27
Publication status	Published - 1 Jan 2001
Event	Cryptography and Coding, 8-th IMA International Conference - Duration: 1 Jan 2001 → 1 Jan 2001

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer-Verlag

Conference

Conference	Cryptography and Coding, 8-th IMA International Conference
Period	1/01/01 → 1/01/01

Bibliographical note

The original publication is available at www.springerlink.com

Keywords

Low Density Parity Check (LDPC)
error correcting codes
statistical physics
boolean
sparse matrices
Ising spin models
irregular code
error probability

Access to Document

10.1007/3-540-45325-3_27

NCRG_2001_020.pdf
The original publication is available at www.springerlink.com
Accepted author manuscript, 214 KB

Cite this

@inbook{79fd05fa0622461891891c841bff5b6a,

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

abstract = "We study the performance of Low Density Parity Check (LDPC) error-correcting codes using the methods of statistical physics. LDPC codes are based on the generation of codewords using Boolean sums of the original message bits by employing two randomly-constructed sparse matrices. These codes can be mapped onto Ising spin models and studied using common methods of statistical physics. We examine various regular constructions and obtain insight into their theoretical and practical limitations. We also briefly report on results obtained for irregular code constructions, for codes with non-binary alphabet, and on how a finite system size effects the error probability.",

keywords = "Low Density Parity Check (LDPC), error correcting codes, statistical physics, boolean, sparse matrices, Ising spin models, irregular code, error probability",

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

note = "The original publication is available at www.springerlink.com; Cryptography and Coding, 8-th IMA International Conference ; Conference date: 01-01-2001 Through 01-01-2001",

year = "2001",

month = jan,

day = "1",

doi = "10.1007/3-540-45325-3_27",

language = "English",

isbn = "9783540430261",

volume = "2260",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "307--316",

editor = "B. Honary",

booktitle = "Cryptography and Coding",

address = "Germany",

}

TY - CHAP

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

AU - Saad, David

AU - Kabashima, Yoshiyuki

AU - Murayama, Tatsuto

AU - Vicente, Renato

N1 - The original publication is available at www.springerlink.com

PY - 2001/1/1

Y1 - 2001/1/1

N2 - We study the performance of Low Density Parity Check (LDPC) error-correcting codes using the methods of statistical physics. LDPC codes are based on the generation of codewords using Boolean sums of the original message bits by employing two randomly-constructed sparse matrices. These codes can be mapped onto Ising spin models and studied using common methods of statistical physics. We examine various regular constructions and obtain insight into their theoretical and practical limitations. We also briefly report on results obtained for irregular code constructions, for codes with non-binary alphabet, and on how a finite system size effects the error probability.

AB - We study the performance of Low Density Parity Check (LDPC) error-correcting codes using the methods of statistical physics. LDPC codes are based on the generation of codewords using Boolean sums of the original message bits by employing two randomly-constructed sparse matrices. These codes can be mapped onto Ising spin models and studied using common methods of statistical physics. We examine various regular constructions and obtain insight into their theoretical and practical limitations. We also briefly report on results obtained for irregular code constructions, for codes with non-binary alphabet, and on how a finite system size effects the error probability.

KW - Low Density Parity Check (LDPC)

KW - error correcting codes

KW - statistical physics

KW - boolean

KW - sparse matrices

KW - Ising spin models

KW - irregular code

KW - error probability

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

UR - http://www.springerlink.com/content/u302rqa22k1arbvw/

U2 - 10.1007/3-540-45325-3_27

DO - 10.1007/3-540-45325-3_27

M3 - Chapter

SN - 9783540430261

VL - 2260

T3 - Lecture Notes in Computer Science

SP - 307

EP - 316

BT - Cryptography and Coding

A2 - Honary, B.

PB - Springer

CY - Berlin / Heidelberg

T2 - Cryptography and Coding, 8-th IMA International Conference

Y2 - 1 January 2001 through 1 January 2001

ER -

Statistical physics of low density parity check error correcting codes

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this