Cascaded Formulation of the Fundamental Polytope of General Linear Block Codes
Kai Yang, Xiaodong Wang, Jon Feldman · 2007
We propose a new linear programming formulation for the decoding of general linear block codes. Different from the original formulation given in [1], the number of total variables to characterize a parity-check constraint in our formulation is less than twice the degree of the corresponding check node. The equivalence between our new formulation and the original formulation is proven. Moreover, we show that any fundamental polytope is simply the intersection of a group of so-called minimum polytopes. Based on this, we propose a branch-and-bound method to compute a non-trivial lower bound to the minimum distance of a linear block code with affordable complexity.