%0 Journal Article
%T Improved linear programming decoding of LDPC codes and bounds on the minimum and fractional distance
%A David Burshtein
%A Idan Goldenberg
%J Mathematics
%D 2010
%I arXiv
%X We examine LDPC codes decoded using linear programming (LP). Four contributions to the LP framework are presented. First, a new method of tightening the LP relaxation, and thus improving the LP decoder, is proposed. Second, we present an algorithm which calculates a lower bound on the minimum distance of a specific code. This algorithm exhibits complexity which scales quadratically with the block length. Third, we propose a method to obtain a tight lower bound on the fractional distance, also with quadratic complexity, and thus less than previously-existing methods. Finally, we show how the fundamental LP polytope for generalized LDPC codes and nonbinary LDPC codes can be obtained.
%U http://arxiv.org/abs/1012.1425v1