Europhysics Letters Belief Propagation vs. Tap for Decoding Corrupted Mes- Sages
(received ; accepted) PACS. 89.70+c { Information science. PACS. 89.90+n { Other areas of general interest to physicists. Abstract. { We employ two diierent methods, based on belief propagation and TAP, for decoding corrupted messages encoded by employing Sourlas's method, where the code word comprises products of K bits selected randomly from the original message. We show that the equations obtained by the two approaches are similar and provide the same solution as the one obtained by the replica approach in some cases (K = 2). However, we also show that for K 3 and unbiased messages the iterative solution is sensitive to the initial conditions and is likely to provide erroneous solutions; and that it is generally beneecial to use Nishimori's temperature, especially in the case of biased messages. Belief networks 1], also termed Bayesian networks and innuence diagrams are diagrammatic representations of joint probability distributions over a set of variables. The set of variables is usually represented by the vertices of a graph, while arcs between vertices represent probabilis-tic dependencies between variables. Belief propagation provides a convenient mathematical tool for calculating iteratively joint probability distributions of variables, and have been used in a variety of cases to assess conditional probabilities and interdependencies between variables in complex systems. One of the most recent uses of belief propagation is in the eld of error correcting codes, especially for decoding corrupted messagess2] (for a review of graphical models and their use in the context of error-correcting codes see 3]). Error-correcting codes provide a mechanism for retrieving the original message after corruption due to noise during transmission. A new family of error-correcting codes, based on insights gained from statistical mechanics, has recently been suggested by Sourlas 4]. These codes can be mapped onto the many body Ising spin problem and can thus be analysed using methods adopted from statistical physics 5, 6, 7, 8, 9].