We propose a technique for improving LP decoding, based on the merging of check nodes. This technique can be applied to standard as well as generalized LDPC codes. Furthermore, we show how a recently-discovered linear-complexity LP decoder can be used to derive non-trivial lower bounds on the minimum distance of specific LDPC codes, with complexity that exhibits quadratic growth with respect to the block length. This bound can be refined using the check node merging technique. The lower bound on the minimum distance is shown to be an upper bound on the fractional distance of the code.
We propose a technique for improving LP decoding, based on the merging of check nodes. This technique can be applied to standard as well as generalized LDPC codes. Furthermore, we show how a recently-discovered linear-complexity LP decoder can be used to derive non-trivial lower bounds on the minimum distance of specific LDPC codes, with complexity that exhibits quadratic growth with respect to the block length. This bound can be refined using the check node merging technique. The lower bound on the minimum distance is shown to be an upper bound on the fractional distance of the code.
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.
The iterative algorithm, for low complexity linear programming (LP) decoding of low-density parity-check (LDPC) codes, proposed by Vontobel and Koetter, is considered. In this paper the convergence rate and computational complexity of this algorithm are studied using a scheduling scheme that we propose. In particular we are interested in obtaining a feasible vector in the LP decoding problem, with objective function value whose distance to the minimum, normalized by the block length, can be made arbitrarily small. It is shown that such a feasible vector can be obtained with linear, in the block length, computational complexity. Improved bounds on the convergence rate are also presented. The results extend to generalized LDPC (GLDPC) codes. It is also shown that previous results for LDPC and GLDPC codes, on the ability of the LP decoder to correct some fixed fraction of errors, hold with linear computational complexity when using the approximate iterative LP decoder.
The problem of low-complexity approximated linear programming (LP) decoding of LDPC codes over GF(q) is considered. An iterative algorithm with linear complexity was proposed by Burshtein for the binary case. However, this algorithm cannot be trivially generalized for the non-binary case, since the derivation uses the even parity property of the check nodes, which does not hold for codes over GF(q). In this work the algorithm is generalized to the non-binary case. We show, that by applying this algorithm to a softened version of the non-binary LP problem proposed by Flanagan, Skachek, Byrne and Grefeath, we can obtain, with complexity linear in the block length, a feasible solution vector for the non-binary LP decoding problem, which is arbitrarily close to optimal in the following sense. The distance between the minimum value achieved by the exact LP decoder and the objective function value of the approximate solution, normalized by the block length of the code, can be made arbitrarily small. We present simulation results and comparisons with the belief propagation (BP) algorithm using-regular ternary LDPC codes. The proposed algorithm can be easily extended to generalized LDPC codes.
The problem of low complexity linear programming (LP) decoding of low-density parity-check (LDPC) codes is considered. An iterative algorithm, similar to min-sum and belief propagation, for efficient approximate solution of this problem was proposed by Vontobel and Koetter. In this paper, the convergence rate and computational complexity of this algorithm are studied using a scheduling scheme that we propose. In particular, we are interested in obtaining a feasible vector in the LP decoding problem that is close to optimal in the following sense. The distance, normalized by the block length, between the minimum and the objective function value of this approximate solution can be made arbitrarily small. It is shown that such a feasible vector can be obtained with a computational complexity which scales linearly with the block length. Combined with previous results that have shown that the LP decoder can correct some fixed fraction of errors we conclude that this error correction can be achieved with linear computational complexity. This is achieved by first applying the iterative LP decoder that decodes the correct transmitted codeword up to an arbitrarily small fraction of erroneous bits, and then correcting the remaining errors using some standard method. These conclusions are also extended to generalized LDPC codes.
The problem of low complexity linear programming (LP) decoding of low-density parity-check (LDPC) codes is considered. An iterative algorithm for efficient approximate solution of this problem was proposed by Vontobel and Koetter. In this paper the convergence rate and computational complexity of this algorithm are studied. In particular we are interested in obtaining a feasible vector in the LP decoding problem, with objective function value whose distance to the minimum, normalized by the block length, can be made arbitrarily small. It is shown that such a feasible vector can be obtained in linear, in the block length, computational complexity. Combined with previous results, that have shown that the LP decoder can correct some fixed fraction of errors, we conclude that this error correction can be achieved with linear computational complexity.
New upper bounds on the rate of low-density parity-check (LDPC) codes as a function of the minimum distance of the code are derived. The bounds apply to regular LDPC codes, and sometimes also to right-regular LDPC codes. Their derivation is based on combinatorial arguments and linear programming. The new bounds improve upon the previous bounds due to Burshtein et al. It is proved that at least for high rates, regular LDPC codes with full-rank parity-check matrices have worse relative minimum distance than the one guaranteed by the Gilbert-Varshamov bound.