J. M. Walsh, P. A. Regalia, and C. R. Johnson, Jr.
Submitted to IEEE Trans. Inform. Theory on September 25, 2005.
It has been previously shown that belief propagation converges to the bitwise a posteriori probabilities in factor graphs which are trees. The recent breakthrough applications of the algorithm to the decoding of LDPC and turbo codes, however, involve factor graphs with loops. Several authors have noted that in these instances the convergent points of belief propagation, while they offer decisions which yield low probability of bit error, do not approximate the bitwise a posteriori probabilities well. In this article, it is argued that belief propagation is an iterative method seeking critical points of a constrained sequence wide maximum likelihood estimation problem. If the constraining probability is equal to one, then the global maximum of the estimation problem is the maximum likelihood sequence detection. Simulation results then suggest that the constraining probability converges to one with successive iterations in instances where the belief propagation decoder provides decisions which give low bit error rates. Together with the sense of optimality of the stationary points, this suggests that in instances where the belief propagation algorithm is applied in factor graphs with loops but yields low probability of bit error, it is doing so because it is iteratively approximating the maximum likelihood sequence detection.