Abstract:

We explain the projection algebra technique, which makes possible an exact computation of the performance of an arbitrary parity-check error-correcting code as decoded by the belief propagation algorithm for the binary erasure channel. This technique improves on density evolution by exactly accounting for the statistical dependencies that exist between belief propagation messages. Although the exact projection algebra technique is computationally intractable for codes of large block-length, it can be efficiently approximated to give rigorous upper and lower bounds on the bit error rates of arbitrary parity-check codes.