Abstract

We show that for low-density parity-check (LDPC) codes with sufficient expansion, the linear programming (LP) decoder corrects a constant fraction of errors.

Keywords

Decoding methodsFraction (chemistry)Constant (computer programming)Low-density parity-check codeList decodingLinear programmingAlgorithmComputer scienceSequential decodingMathematicsConcatenated error correction codeBlock codeChemistry

Affiliated Institutions

Related Publications

Low-density parity-check codes

Robert G. Gallager

A low-density parity-check code is a code specified by a parity-check matrix with the following properties: each column contains a small fixed number <tex xmlns:mml="http://www....

1962 IEEE Transactions on Information Theory 10397 citations

Expander codes

M. Sipser , Daniel A. Spielman

Using expander graphs, we construct a new family of asymptotically good, linear error-correcting codes. These codes have linear time sequential decoding algorithms and logarithm...

1996 IEEE Transactions on Information Theory 920 citations

Publication Info

Year
2004
Type
article
Pages
69-69
Citations
41
Access
Closed

External Links

View on DOI.org

Social Impact

Altmetric
PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

41
OpenAlex

Cite This

Jon Feldman, Tal Malkin, Rocco A. Servedio et al. (2004). LP decoding corrects a constant fraction of errors. , 69-69. https://doi.org/10.1109/isit.2004.1365106

Identifiers

DOI
10.1109/isit.2004.1365106