Contents I. Introduction
The behavior of the BP [1] decoder for the case of finite-length codes does not have simple characteristics, and can be very hard to predict. Linear programming is a well-studied discipline that provides efficient analysis tools. The relationship between linear programming decoding [2] and BP decoding was observed and characterized [3], and the decision regions of these decoders are suggested to be tightly related. The LP decoder receives the channel likelihood ratios which define an objective function, for which it finds an optimal solution that satisfies a set of constraints. These constraints are inequalities arisen from a given parity -check matrix and form a polytope, also known as the fundamental polytope [4]. The fundamental polytope is a relaxation of the codewords polytope. It has a clear geometrical representation which is well-suited for finite-length analysis. The vertices of the fundamental polytope are every codeword, but also some non-codewords pseudocodewords [2]. The fundamental cone [4] is the conic hull of the fundamental polytope. It has a vertex in the origin, and its edges are also referred to as minimal pseudo-codewords [4] or generators [5]. The fundamental cone has a more compact representation than the fundamental polytope, and it is sufficient to consider the fundamental cone for evaluating the performance of the LP decoder [2], [4], [5].
