Name
Abstract | ||
|---|---|---|
We study error bounds for linear programming decoding of regular low-density parity-check (LDPC) codes. For memoryless binary-input output-symmetric channels, we prove bounds on the word error probability that are inverse doubly exponential in the girth of the factor graph. For memoryless binary-input AWGN channel, we prove lower bounds on the threshold for regular LDPC codes whose factor graphs have logarithmic girth under LP-decoding. Specifically, we prove a lower bound of σ = 0.735 (upper bound of [(Eb)/(N0)]=2.67 dB) on the threshold of (3, 6)-regular LDPC codes whose factor graphs have logarithmic girth. Our proof is an extension of a recent paper of Arora, Daskalakis, and Steurer [STOC 2009] who presented a novel probabilistic analysis of LP decoding over a binary symmetric channel. Their analysis is based on the primal LP representation and has an explicit connection to message passing algorithms. We extend this analysis to any MBIOS channel. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1109/TIT.2010.2094830 | Clinical Orthopaedics and Related Research |
Keywords | DocType | Volume |
memoryless channels,factor graph,lp decoding,regular ldpc codes,memoryless binary-input output-symmetric channel,error bound,mbios channel,binary symmetric channel,regular ldpc code,novel probabilistic analysis,logarithmic girth,regular low-density parity-check,random variables,ldpc code,error probability,upper bound,decoding,linear code,gaussian noise,linear programming,vectors | Journal | 57 |
Issue | ISSN | ISBN |
2 | 0018-9448 | 978-1-4244-7891-0 |
Citations | PageRank | References |
4 | 0.47 | 13 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nissim Halabi | 1 | 8 | 3.58 |
| G. Even | 2 | 100 | 7.19 |