Parallel versus sequential updating for Belief Propagation decoding

Abstract

sequential updating scheme (SUS) for the belief propagation algorithm is proposed, and is compared with the parallel (regular) updating scheme (PUS). Simulation results on various codes indicate that the number of iterations of the belief algorithm for the SUS is about one half of the required iterations for the PUS, where both decoding algorithms have the same error correction properties. The complexity per iteration for both schemes is similar, resulting in a lower total complexity for the SUS. The explanation of this effect is related to the inter-iteration information sharing, which is a property of only the SUS, and which increases the "correction gain" per iteration

15 pages, 3 figures, submitted to Phys. Rev. E june 2002

Cited by in corpus (8)

• Residual Belief Propagation: Informed Scheduling for Asynchronous Message Passing
• Cluster Variation Method in Statistical Physics and Probabilistic Graphical Models
• Informed Dynamic Scheduling for Belief-Propagation Decoding of LDPC Codes
• Parallel vs. Sequential Belief Propagation Decoding of LDPC Codes over GF(q) and Markov Sources
• A Survey on Trapping Sets and Stopping Sets
• The dynamics of competitive learning: the role of updates and memory
• $A+A\to \varnothing$ system in one dimension with particle motion determined by nearest neighbour distances: results for parallel updates
• Hybrid Decoding of Finite Geometry LDPC Codes