An Algorithm for the Computation of the Minimum Distance of LDPC Codes

The evaluation of the minimum distance of low-density parity-check (LDPC) codes remains an open problem due to the rather large dimension of the parity check matrix H associated with any practical code. In this article, we propose an effective modification of the error impulse (EI) technique for computation of the minimum distance of the LDPC codes. The EI method is successfully applied to sub-optimum decoding algorithms such as the iterative MAP decoding algorithm for turbo codes. We present novel modifications and extensions of this method to the sub-optimum iterative sum-product algorithm for LDPC codes. The performance of LDPC codes may be limited by pseudo-codewords. There are, however, cases when the LDPC decoder behaves as a maximum-likelihood (ML) decoder. This is specially so for randomly constructed LDPC codes operating at medium to high SNR values. In such cases, estimation of the minimum distance dm using the error-impulse method can be useful to assess asymptotic performance. In short, apart from theoretical interest in achievable dm, the technique is useful in checking whether an LDPC code is poor by virtue of having a low dm. But, if a code has a high dm, simulations would still be needed to assess real performance.