Graphical Characterizations of Linear Programming Pseudocodewords for Cycle Codes

The performance of linear programming decoding is determined by the set of nonzero linear programming pseudocodewords. The minimum pseudoweight of this set of linear programming pseudocodewords is also generally accepted as a good predictor of the performance of iterative message-passing decoding. Since the linear programming decoder has a natural description based on the Tanner graph of a code, linear programming pseudocodewords can be analyzed from a graphical viewpoint. In this paper, two graphical characterizations of linear programming pseudocodewords of cycle codes are provided: one for the entire set of linear programming pseudocodewords, and one for the set of minimal linear programming pseudocodewords. The first of these characterizations is used to determine a formula for the minimum degree of a graph cover necessary to realize a linear programming pseudocodeword of a cycle code, and the second is used to prove a result concerning the asymptotic performance of the linear programming decoder when considering transmission over either the additive white Gaussian noise channel or the binary symmetric channel. Finally, a discussion contrasting these two characterizations both with each other and with Horn´s characterization of bad pseudocycles is provided.