Computer Science – Information Theory
Scientific paper
2006-08-05
Computer Science
Information Theory
Appeared in International Symposium on Information Theory, Seattle, WA. July 2006. Revision: fixed author names in abstract (t
Scientific paper
A new approach for decoding binary linear codes by solving a linear program (LP) over a relaxed codeword polytope was recently proposed by Feldman et al. In this paper we investigate the structure of the polytope used in the LP relaxation decoding. We begin by showing that for expander codes, every fractional pseudocodeword always has at least a constant fraction of non-integral bits. We then prove that for expander codes, the active set of any fractional pseudocodeword is smaller by a constant fraction than the active set of any codeword. We exploit this fact to devise a decoding algorithm that provably outperforms the LP decoder for finite blocklengths. It proceeds by guessing facets of the polytope, and resolving the linear program on these facets. While the LP decoder succeeds only if the ML codeword has the highest likelihood over all pseudocodewords, we prove that for expander codes the proposed algorithm succeeds even with a constant number of pseudocodewords of higher likelihood. Moreover, the complexity of the proposed algorithm is only a constant factor larger than that of the LP decoder.
Dimakis Alexandros G.
Wainwright Martin J.
No associations
LandOfFree
Guessing Facets: Polytope Structure and Improved LP Decoder does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Guessing Facets: Polytope Structure and Improved LP Decoder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Guessing Facets: Polytope Structure and Improved LP Decoder will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-629355