LP Decoding Corrects a Constant Fraction of Errors
Authors:
- Tal MalkinTMTal Malkin
- Rocco A. ServedioRSRocco A. Servedio
- Cliff SteinCSCliff Stein
- Martin J. WainwrightMWMartin J. Wainwright
- 26 December 2006
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 53 (1) , 82-89
Abstract
We show that for low-density parity-check (LDPC) codes whose Tanner graphs have sufficient expansion, the linear programming (LP) decoder of Feldman, Karger, and Wainwright can correct a constant fraction of errors. A random graph will have sufficient expansion with high probability, and recent work shows that such graphs can be constructed efficiently. A key element of our method is the use of a dual witness: a zero-valued dual solution to the decoding linear program whose existence proves decoding success. We show that as long as no more than a certain constant fraction of the bits are flipped by the channel, we can find a dual witness. This new method can be used for proving bounds on the performance of any LP decoder, even in a probabilistic setting. Our result implies that the word error rate of the LP decoder decreases exponentially in the code length under the binary-symmetric channel (BSC). This is the first such error bound for LDPC codes using an analysis based on "pseudocodewords." Recent work by Koetter and Vontobel shows that LP decoding and min-sum decoding of LDPC codes are closely related by the "graph cover" structure of their pseudocodewords; in their terminology, our result implies that that there exist families of LDPC codes where the minimum BSC pseudoweight grows linearly in the block lengthKeywords
This publication has 25 references indexed in Scilit:
- Concatenated Codes: Serial and ParallelIEEE Transactions on Information Theory, 2005
- On nearly-MDS expander codes2004
- Error Exponents of Expander Codes under Linear-Complexity DecodingSIAM Journal on Discrete Mathematics, 2004
- Improved low-density parity-check codes using irregular graphs and belief propagation2002
- Finite-length analysis of low-density parity-check codes on the binary erasure channelIEEE Transactions on Information Theory, 2002
- Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets2002
- Elements of Information Theory2001
- Design of capacity-approaching irregular low-density parity-check codesIEEE Transactions on Information Theory, 2001
- On the Effective Weights of Pseudocodewords for Codes Defined on Graphs with Cycles2001
- A recursive approach to low complexity codesIEEE Transactions on Information Theory, 1981