How to quantify the error correction capacity of LDPC code?

As shown in title, I am studying the LDPC code recently. However, I still can not calculate the error correction capacity of it, maybe due to complex decoding algorithm. And there lacks easy understanding properties to infer the error correction.

An easy example is RS code (Reed solomon code). For the setting RS(N,k), while N is the block size and K is the useful symbol size. And the error correction capacity is (N-K)/2.

Is there any easy properties like RS code for LDPC code? Thanks!

2 Answers

It is a difficult problem to find the minimum distance of an LDPC. Vardy shows in The Intractability of Computing the Minimum Distance of a Code that it is NP-hard to find the minimum distance. Looking around one can find papers with various algorithms for minimum distance, but there won't be anything nice like for RS codes. For example, there is a randomized algorithm in On the Computation of the Minimum Distance of Low-Density Parity-Check Codes by Hu and Fossorier.

As @John mentioned, there is not general way and nice formula for computing the minimum distance of codes. The problem remain difficult for LDPC codes as like as other codes. But, there are several way to construct LDPC codes, as like as finite geometry, design theory, graph theory (prototype graphs), permutation circulant matrices, random construction and other ways. Sometimes if we have more information about the method of construction of LDPC codes, we can say much more. For example, if you have QC-LDPC codes, the girth of the code (shortest cycle in the Tanner graph of code) is at most $12$ and it forces the minimum distance to have nice bound. Also, if you know that your code does not have girth $4$, and it has fixed number of $1$ (say $\lambda$) in each columns of parity check matrix, then the minimum distance is at least $\lambda +1$.

So, it depends what is your way to constructing LDPC codes. Also, the predefined structure can help to write efficient program to find the minimum distance of the codes. Random sampling with MAGMA Algebra is a good way for finding the minimum distance of some structured LDPC codes. Also, MAGMA has function "MinimumDistance" which is useful for finding the minim distance of short length codes.

Anyway, in almost cases we can not find the minimum distance of LDPC codes and we have just some bound. But, because of the special method of decoding of such codes (itterative decoding), there are some other parameters which are important for avaluating the efficiency of codes. Short cycles ditribution, trapping sets, stopping sets, density and some other parameters are very important.

• It is very impressive! Thanks a lot! Jan 15, 2017 at 11:32