Parallel versus sequential updating for belief propagation decoding

Haggai Kfir and Ido Kanter

Physica A: Statistical Mechanics and its Applications, 2003, vol. 330, issue 1, 259-270

Abstract: A 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, furthermore, the SUS utilizes significantly less memory during the decoding process. We demonstrate that the acceleration in convergence time is related to the inter-iteration information sharing, which is a property of only the SUS, and which increases the “correction gain” per iteration. Finally, the connection between the dynamics of error correcting codes and physical systems is discussed.

Date: 2003
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437103006885
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:phsmap:v:330:y:2003:i:1:p:259-270

DOI: 10.1016/j.physa.2003.08.015

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().