Parallel versus sequential updating for belief propagation decoding

DOI10.1016/J.PHYSA.2003.08.015MaRDI QIDQ1412924zbMATH OpenOpenAlexFDO

Authors Haggai Kfir, Ido Kanter

Publication date 30 November 2003

Published in Physica A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cond-mat/0207185

zbMATH Keywords

decoding algorithmsiterationserror corrections

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

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

Recommendations

• Bounds on the performance of belief propagation decoding
• Sequential decoding for multiple access channels
• scientific article; zbMATH DE number 3463521
• Fully Parallel Stochastic LDPC Decoders
• scientific article; zbMATH DE number 3490844
• Serial Schedules for Belief-Propagation: Analysis of Convergence Time
• Iterative decoding of one-step majority logic decodable codes based on belief propagation
• Sequential decoding for discrete input memoryless channels

Cites work

• scientific article; zbMATH DE number 3174791 (Why is no real title available?)
• A Mathematical Theory of Communication
• Design of capacity-approaching irregular low-density parity-check codes
• Finite-size effects and error-free communication in Gaussian channels
• Good error-correcting codes based on very sparse matrices
• Improved low-density parity-check codes using irregular graphs

Cited in

(1)

• Serial Schedules for Belief-Propagation: Analysis of Convergence Time

This page was built for publication: Parallel versus sequential updating for belief propagation decoding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1412924)