Probability of false decoding with LDPC codes - MathOverflow most recent 30 from http://mathoverflow.net2013-05-24T20:13:08Zhttp://mathoverflow.net/feeds/question/67875http://www.creativecommons.org/licenses/by-nc/2.5/rdfhttp://mathoverflow.net/questions/67875/probability-of-false-decoding-with-ldpc-codesProbability of false decoding with LDPC codesinfth20112011-06-15T16:00:37Z2011-06-15T16:12:34Z
<p>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:</p>
<p>\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$.</p>
<p>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.</p>