A method which obtains a tight lower bound on the fractional distance of LDPC codes is proposed. This algorithm exhibits complexity which scales quadratically with the block length, and thus less than currently-known methods. We also show how the fundamental LP polytope for generalized LDPC codes and nonbinary LDPC codes can be obtained.
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.
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.
The problem of low-complexity linear programming (LP) decoding of nonbinary low-density parity-check (LDPC) codes is considered, and an iterative LP decoding algorithm is presented. Results that were previously derived for binary LDPC codes are extended to the nonbinary case. Both simple and generalized nonbinary LDPC codes are considered. It is shown how the algorithm can be implemented efficiently using a finite-field fast Fourier transform. Then, the convergence rate of the algorithm is analyzed. The complexity of the algorithm scales linearly in the block length, and it can approximate, up to an arbitrarily small relative error, the objective function of the exact LP solution. When applied to a typical code from an appropriate nonbinary LDPC code ensemble, the algorithm can correct a constant fraction of errors in linear (in the block length) computational complexity. Computer experiments with the new iterative LP decoding algorithm show that, in the error floor region, it can have better performance compared to belief propagation decoding, with similar computational requirements.
Linear Programming (LP) decoding of Low-Density Parity-Check (LDPC) codes has attracted much attention in the research community in the past few years. LP decoding has been derived for binary and nonbinary linear codes. However, the most important problem with LP decoding for both binary and nonbinary linear codes is that the complexity of standard LP solvers such as the simplex algorithm remains prohibitively large for codes of moderate to large block length. To address this problem, two low-complexity LP (LCLP) decoding algorithms for binary linear codes have been proposed by Vontobel and Koetter, henceforth called the basic LCLP decoding algorithm and the subgradient LCLP decoding algorithm. In this paper, we generalize these LCLP decoding algorithms to nonbinary linear codes. The computational complexity per iteration of the proposed nonbinary LCLP decoding algorithms scales linearly with the block length of the code. A modified BCJR algorithm for efficient check-node calculations in the nonbinary basic LCLP decoding algorithm is also proposed, which has complexity linear in the check node degree. Several simulation results are presented for nonbinary LDPC codes defined over Z4, GF(4), and GF(8) using quaternary phase-shift keying and 8-phase-shift keying, respectively, over the AWGN channel. It is shown that for some group-structured LDPC codes, the error-correcting performance of the nonbinary LCLP decoding algorithms is similar to or better than that of the min-sum decoding algorithm.
Finding the minimum distance of low-density-parity-check (LDPC) codes is an NP-hard problem. Different from all existing works that focus on binary LDPC codes, we in this paper aim to compute the minimum distance of nonbinary LDPC codes, motivated by the fact that operating in a large Galois field provides one important degree of freedom to achieve both good waterfall and error-floor performance. Our method is based on the existing nearest nonzero codeword search (NNCS) method, but several modifications are incorporated for nonbinary LDPC codes, including the modified error impulse pattern, the dithering method, and the nonbinary decoder. Numerical results on the estimated minimum distances show that a code's minimum distance can be increased by careful selection of nonzero elements of the parity check matrix, or by increasing the mean column weight, or by increasing the size of the Galois field. These results support observations that have been made based on simulated performance in the literature. Finally, we provide an upper bound on the minimum distance for nonbinary quasi-cyclic LDPC codes.
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.