An approximation of maximum-likelihood decoding over the binary symmetric channel was introduced by Omura in 1972. This decoder employs an iterative, randomized algorithm whose behavior closely mimics that of the simplex algorithm. In this paper, we generalize Omura's decoder to operate on an arbitrary binary-input memoryless channel. Further, we prove that the probability of the generalized Omura decoder (and hence Omura's original decoder) returning a maximum-likelihood codeword approaches 1 as the number of iterations goes to infinity, a result that has hereto remained unproven.

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.

The role of pseudocodewords in causing non-codeword outputs in linear programming decoding, graph cover decoding, and iterative message-passing decoding is investigated. The three main types of pseudocodewords in the literature-linear programming pseudocodewords, graph cover pseudocodewords, and computation tree pseudocodewords-are reviewed and connections between them are explored. Some discrepancies in the literature on minimal and irreducible pseudocodewords are highlighted and clarified, and the minimal degree cover necessary to realize a pseudocodeword is found. Additionally, some conditions for the existence of connected realizations of graph cover pseudocodewords are given. This allows for further analysis of when graph cover pseudocodewords induce computation tree pseudocodewords. Finally, an example is offered that shows that existing theories on the distinction between graph cover pseudocodewords and computation tree pseudocodewords are incomplete.