Probability of false decoding with LDPC codes

Question

It is well known that given a binary linear code $C$ under maximum likelihood decoding the probability of false decoding $P_C$ in a Binary Symmetric Channel with cross over probability $p$, in other words, the probability of decoding a wrong codeword is lower bounded by:

\begin{equation} P_C(p)\leq\sum_{w=1}^nc_w\sum_{\lceil i=w/2\rceil }^w\binom{w}{i}p^i(1-p)^{w-i} \end{equation} where $c_w$ is the number of words in the code with hamming weight $w$.

This bound can be computed for codes with a known weight enumerator polynomial. I would be interested in bounding, not necessarily through the bound above, the false decoding probability for instances of LDPC codes, that is not for ensembles, and under belief propagation.

Answer 1

Generally speaking, understanding the decoding error probability of an LDPC code is a very difficult problem. Among major channels that have extensively been studied, as far as I know, binary erasure channels are the only ones that allow for a simple combinatorial characterization of the dominating error patterns. So, a combinatorial notion analogous to the minimum distance of a linear code for maximum likelihood decoding is not available for binary symmetric channels when it comes to iterative decoding based on brief propagation.

With that said, if you would like a bound through a strategy similar to considering minimum distance, you can analyze the decoding error probability of an LDPC code under brief propagation by identifying the kind of error pattern that will not be corrected no matter how many iterations the decoder performs. In other words, given a code, you try to figure out the kind of set $T$ of bits where brief propagation fails if the bits in $T$ all get flipped. Such error patterns are called trapping sets. (But different authors use different terms or the same term to mean different things, so be careful.) Given an LDPC code $\mathcal{C}$ and crossover probability $p$ of the channel (i.e., each bit is flipped with probability $p$), if you identify all small trapping sets of $\mathcal{C}$, in principle, you should be able to get a good estimate of the decoding error probability at the error floor region (i.e., when $p$ is small enough), assuming a sufficiently large number of iterations are performed.

The problem is that it is extremely difficult to identify all meaningful trapping sets for a given code because there is no combinatorial characterization. There are studies on algorithms that try to find dominating trapping sets of a given LDPC code (e.g., M. Karimi, A. H. Banihashemi, Efficient algorithm for finding dominant trapping sets of LDPC codes, IEEE Trans. Inf. Theory, 58 (2012) 6942-6958). But generally speaking, simulations are more practical for performance estimation purposes than trying to obtain an equivalent of the weight enumerator and compute the decoding error probability like you do with the number $c_w$ of codewords of Hamming weight $w$.

If you would like the exact decoding error probability for any crossover probability $p$ when a parity-check matrix $H$ of an LDPC code is given, there is a paper that studies this problem. As you already know, the standard decoding algorithm based on brief propagation for LDPC codes (i.e., the sum-product algorithm) is characterized by the probability $p'$ for initialization (which is usually the crossover probability of the channel) and the number $l$ of the maximum iterations. M. Hagiwara, M. P. C. Fossorier, H. Imai, Fixed initialization decoding of LDPC codes over a binary symmetric channel, IEEE Trans. Inf. Theory, 58 (2012) 2321-2329 proved that if $p'$ is fixed (so initialization probability $p'$ is generally not equal to crossover probability $p$), the decoding error probability is a polynomial function of $p$.

But we usually set $p'=p$. In this case, they proved that there are parity-check matrices for which the decoding error probabilities are not continuous functions of $p$.