Paper Info
Title
Linear-programming decoding of Tanner codes with local-optimality certificates
Abstract
Given a channel observation y and a codeword x, we are interested in a one-sided error test that answers the questions: is x optimal with respect to y? is it unique? A positive answer for such a test is called a certificate for the optimality of a codeword. We present new certificates that are based on combinatorial characterization for local-optimality of a codeword in irregular Tanner codes. The certificate is based on weighted normalized trees in computation trees of the Tanner graph. These trees may have any finite height h (even greater than the girth of the Tanner graph). In addition, the degrees of local-code nodes are not restricted to two (i.e., skinny trees). We prove that local-optimality in this new characterization implies ML-optimality and LP-optimality, and show that a certificate can be computed efficiently. We apply the new local-optimality characterization to regular Tanner codes, and prove lower bounds on the noise thresholds of LP-decoding in MBIOS channels. When the noise is below these lower bounds, the probability that LP-decoding fails decays doubly exponentially in the girth of the Tanner graph.
Year
DOI
Venue
2012
10.1109/ISIT.2012.6284007
Information Theory Proceedings
Keywords
Field
DocType
binary codes,channel coding,decoding,linear programming,probability,trees (mathematics),LP-decoding,LP-optimality,MBIOS channel,ML-optimality,Tanner code,Tanner graph,channel observation,codeword,combinatorial characterization,computation tree,linear-programming decoding,local-optimality certificate,memoryless binary-input output-symmetric channel,one-sided error test,probability,weighted normalized tree
Discrete mathematics,Combinatorics,Sequential decoding,Binary code,Code word,Linear programming,Decoding methods,Tanner graph,Mathematics,Computation,Certificate
Conference
ISSN
ISBN
Citations 
2157-8095 E-ISBN : 978-1-4673-2578-3
978-1-4673-2578-3
0
PageRank 
References 
Authors
0.34
8
2
Name
Order
Citations
PageRank
Nissim Halabi183.58
Guy Even221.40