Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:cs/0702111 · International Conference on Communications

Informed Dynamic Scheduling for Belief-Propagation Decoding of LDPC Codes

Andres I. Vila Casado, Miguel Griot, Richard D. Wesel

Published Jun 1, 2007• 132 citations
arXivHTMLPDF

Abstract

Low-density parity-check (LDPC) codes are usually decoded by running an iterative belief-propagation, or message-passing, algorithm over the factor graph of the code. The traditional message-passing schedule consists of updating all the variable nodes in the graph, using the same pre-update information, followed by updating all the check nodes of the graph, again, using the same pre-update information. Recently several studies show that sequential scheduling, in which messages are generated using the latest available information, significantly improves the convergence speed in terms of number of iterations. Sequential scheduling raises the problem of finding the best sequence of message updates. This paper presents practical scheduling strategies that use the value of the messages in the graph to find the next message to be updated. Simulation results show that these informed update sequences require significantly fewer iterations than standard sequential schedules. Furthermore, the paper shows that informed scheduling solves some standard trapping set errors. Therefore, it also outperforms traditional scheduling for a large numbers of iterations. Complexity and implementability issues are also addressed.

DOI
10.1109/icc.2007.158

Related papers

Informed Scheduling for Belief-Propagation Decoding of LDPC Codes

Andres I. Vila Casado, Miguel Griot, Richard D. Wesel

Abstract — Low-Density Parity-Check (LDPC) codes are usually decoded by running an iterative belief-propagation, or message-passing, algorithm over the factor graph of the code. The traditional message-passing schedule consists of updating all the variable nodes in the graph, using the same pre-update information, followed by updating all the check nodes of the graph, again, using the same pre-update information. Recently several studies show that sequential scheduling, in which messages are generated using the latest available information, significantly improves the convergence speed in terms of number of iterations. Sequential scheduling raises the problem of finding the best sequence of message updates. This paper presents practical scheduling strategies that use the value of the messages in the graph to find the next message to be updated. Simulation results show that these informed update sequences require significantly fewer iterations than standard sequential schedules. Complexity and implementability issues are also addressed. Index Terms — Belief propagation-algorithm, messagepassing schedule, error-control codes, low-density paritycheck codes. I.

•Feb 19, 2007•0 citations

LDPC Decoders with Informed Dynamic Scheduling

Andres I. Vila Casado, Miguel Griot, Richard D. Wesel

Low-Density Parity-Check (LDPC) codes are usually decoded by running an iterative belief-propagation (BP), or message-passing, algorithm over the factor graph of the code. The traditional message-passing scheduling, called flooding, consists of updating all the variable nodes in the graph, using the same pre-update information, followed by updating all the check nodes of the graph, again, using the same pre-update information. Recently, several studies show that sequential scheduling, in which messages are generated using the latest available information, significantly improves the convergence speed in terms of number of iterations. Sequential scheduling introduces the problem of finding the best sequence of message updates. We propose Informed Dynamic Scheduling (IDS) strategies that select the message-passing schedule according to the observed rate of change of the messages. In general, IDS strategies require computation to select the message to update but converge in fewer message updates because they focus on the part of the graph that has not converged. Moreover, IDS yields a lower error-rate performance than either flooding or sequential scheduling because IDS strategies overcome traditional trapping-set errors. This paper presents IDS strategies that address several issues including performance for short-blocklength codes, complexity, and implementability.

IEEE Transactions on Communications•Nov 9, 2010•137 citations

Improving LDPC Decoders via Informed Dynamic Scheduling

Andres I. Vila Casado, Miguel Griot, Richard D. Wesel

Low-Density Parity-Check (LDPC) codes are usually decoded by running an iterative belief-propagation (BP), or message-passing, algorithm over the factor graph of the code. The message-passing schedule of the BP algorithm significantly affects the performance of the LDPC decoder. The authors recently presented a novel message-passing schedule, called Informed Dynamic Scheduling (IDS), that selects the message-passing schedule according to the observed rate of change of the messages. IDS yields a lower error-rate performance than traditional message-passing schedules (such as flooding and LBP) because it solves traditional trapping-set errors. However, for short-blocklength LDPC codes, IDS algorithms present non-trapping-set errors in the error floor region. This paper presents a careful analysis of those errors and proposes mixed scheduling strategies, combining LBP with IDS, that solve these non-trapping-set errors. Also, we will show that some lower-complexity techniques, such as mixed scheduling, perform close to the best IDS strategies for larger-blocklength codes.

IEEE Information Theory Workshop (ITW)•Sep 1, 2007•31 citations

Effective Informed Dynamic Scheduling for Belief Propagation Decoding of LDPC Codes

Yi Gong, Xingcheng Liu, Weicai Ye +1 more

The simultaneous flooding scheduling is popular for Low-Density Parity-Check (LDPC) Belief Propagation (BP) decoding. Non-simultaneous sequential scheduling is superior to the flooding scheduling, and asynchronous dynamic scheduling has better FER performance than the sequential scheduling. However, all strategies encounter the trouble of locating the error variable node. This paper proposes an informed dynamic scheduling strategy, which utilizes the instability of the variable node and the residual of the variable-to-check message to locate the message to be updated first. The informed dynamic scheduling overcomes the trapping sets effectively. This paper also designs an informed dynamic scheduling strategy with adaptivity to pass more messages in parallel, which effectively postpones the influence of cycles in the Tanner graph. In some sense, the strategy lengthens cycles. Simulation results show that the two informed dynamic scheduling strategies outperform other algorithms.

IEEE Transactions on Communications•Aug 3, 2011•53 citations

Transactions Papers Effective Informed Dynamic Scheduling for Belief Propagation Decoding of LDPC Codes

Yi Gong, Xingcheng Liu, Guojun Han

The simultaneous flooding scheduling is popular for Low-Density Parity-Check (LDPC) Belief Propagation (BP) decoding. Non-simultaneous sequential scheduling is superior to the flooding scheduling, and asynchronous dynamic scheduling has better FER performance than the sequential scheduling. However, all strategies encounter the trouble of locating the error variable node. This paper proposes an informed dynamic scheduling strategy, which utilizes the instability of the variable node and the residual of the variable-to-check message to locate the message to be updated first. The informed dynamic scheduling overcomes the trapping sets effectively. This paper also designs an informed dynamic scheduling strategy with adaptivity to pass more messages in parallel, which effectively postpones the influence of cycles in the Tanner graph. In some sense, the strategy lengthens cycles. Simulation results show that the two informed dynamic scheduling strategies outperform other algorithms.

•Jan 1, 2011•0 citations

Serial Schedules for Belief-Propagation: Analysis of Convergence Time

Jacob Goldberger, Haggai Kfir

Low-density parity-check (LDPC) codes are usually decoded by running an iterative belief-propagation algorithm over the factor graph of the code. In the traditional message-passing schedule, in each iteration all the variable nodes, and subsequently all the factor nodes, pass new messages to their neighbors. Recently several studies show that serial scheduling, in which messages are generated using the latest available information, significantly improves the convergence speed in terms of number of iterations. It was observed experimentally in several studies that the serial schedule converges in exactly half the number of iterations compared to the standard parallel schedule. In this correspondence we provide a theoretical motivation for this observation by proving it for single-path graphs.

IEEE Transactions on Information Theory•Feb 29, 2008•23 citations
Low-density parity-check (LDPC) codes are usually decoded by running an iterative belief-propagation, or message-passing, algorithm over the factor graph of the code. The traditional message-passing schedule consists of updating all the variable nodes in the graph, using the same pre-update information, followed by updating all the check nodes of the graph, again, using the same pre-update information. Recently several studies show that sequential scheduling, in which messages are generated using the latest available information, significantly improves the convergence speed in terms of number of iterations. Sequential scheduling raises the problem of finding the best sequence of message updates. This paper presents practical scheduling strategies that use the value of the messages in the graph to find the next message to be updated. Simulation results show that these informed update sequences require significantly fewer iterations than standard sequential schedules. Furthermore, the paper shows that informed scheduling solves some standard trapping set errors. Therefore, it also outperforms traditional scheduling for a large numbers of iterations. Complexity and implementability issues are also addressed.
Abstract — Low-Density Parity-Check (LDPC) codes are usually decoded by running an iterative belief-propagation, or message-passing, algorithm over the factor graph of the code. The traditional message-passing schedule consists of updating all the variable nodes in the graph, using the same pre-update information, followed by updating all the check nodes of the graph, again, using the same pre-update information. Recently several studies show that sequential scheduling, in which messages are generated using the latest available information, significantly improves the convergence speed in terms of number of iterations. Sequential scheduling raises the problem of finding the best sequence of message updates. This paper presents practical scheduling strategies that use the value of the messages in the graph to find the next message to be updated. Simulation results show that these informed update sequences require significantly fewer iterations than standard sequential schedules. Complexity and implementability issues are also addressed. Index Terms — Belief propagation-algorithm, messagepassing schedule, error-control codes, low-density paritycheck codes. I.
Low-Density Parity-Check (LDPC) codes are usually decoded by running an iterative belief-propagation (BP), or message-passing, algorithm over the factor graph of the code. The traditional message-passing scheduling, called flooding, consists of updating all the variable nodes in the graph, using the same pre-update information, followed by updating all the check nodes of the graph, again, using the same pre-update information. Recently, several studies show that sequential scheduling, in which messages are generated using the latest available information, significantly improves the convergence speed in terms of number of iterations. Sequential scheduling introduces the problem of finding the best sequence of message updates. We propose Informed Dynamic Scheduling (IDS) strategies that select the message-passing schedule according to the observed rate of change of the messages. In general, IDS strategies require computation to select the message to update but converge in fewer message updates because they focus on the part of the graph that has not converged. Moreover, IDS yields a lower error-rate performance than either flooding or sequential scheduling because IDS strategies overcome traditional trapping-set errors. This paper presents IDS strategies that address several issues including performance for short-blocklength codes, complexity, and implementability.
Low-Density Parity-Check (LDPC) codes are usually decoded by running an iterative belief-propagation (BP), or message-passing, algorithm over the factor graph of the code. The message-passing schedule of the BP algorithm significantly affects the performance of the LDPC decoder. The authors recently presented a novel message-passing schedule, called Informed Dynamic Scheduling (IDS), that selects the message-passing schedule according to the observed rate of change of the messages. IDS yields a lower error-rate performance than traditional message-passing schedules (such as flooding and LBP) because it solves traditional trapping-set errors. However, for short-blocklength LDPC codes, IDS algorithms present non-trapping-set errors in the error floor region. This paper presents a careful analysis of those errors and proposes mixed scheduling strategies, combining LBP with IDS, that solve these non-trapping-set errors. Also, we will show that some lower-complexity techniques, such as mixed scheduling, perform close to the best IDS strategies for larger-blocklength codes.
The simultaneous flooding scheduling is popular for Low-Density Parity-Check (LDPC) Belief Propagation (BP) decoding. Non-simultaneous sequential scheduling is superior to the flooding scheduling, and asynchronous dynamic scheduling has better FER performance than the sequential scheduling. However, all strategies encounter the trouble of locating the error variable node. This paper proposes an informed dynamic scheduling strategy, which utilizes the instability of the variable node and the residual of the variable-to-check message to locate the message to be updated first. The informed dynamic scheduling overcomes the trapping sets effectively. This paper also designs an informed dynamic scheduling strategy with adaptivity to pass more messages in parallel, which effectively postpones the influence of cycles in the Tanner graph. In some sense, the strategy lengthens cycles. Simulation results show that the two informed dynamic scheduling strategies outperform other algorithms.
The simultaneous flooding scheduling is popular for Low-Density Parity-Check (LDPC) Belief Propagation (BP) decoding. Non-simultaneous sequential scheduling is superior to the flooding scheduling, and asynchronous dynamic scheduling has better FER performance than the sequential scheduling. However, all strategies encounter the trouble of locating the error variable node. This paper proposes an informed dynamic scheduling strategy, which utilizes the instability of the variable node and the residual of the variable-to-check message to locate the message to be updated first. The informed dynamic scheduling overcomes the trapping sets effectively. This paper also designs an informed dynamic scheduling strategy with adaptivity to pass more messages in parallel, which effectively postpones the influence of cycles in the Tanner graph. In some sense, the strategy lengthens cycles. Simulation results show that the two informed dynamic scheduling strategies outperform other algorithms.
Low-density parity-check (LDPC) codes are usually decoded by running an iterative belief-propagation algorithm over the factor graph of the code. In the traditional message-passing schedule, in each iteration all the variable nodes, and subsequently all the factor nodes, pass new messages to their neighbors. Recently several studies show that serial scheduling, in which messages are generated using the latest available information, significantly improves the convergence speed in terms of number of iterations. It was observed experimentally in several studies that the serial schedule converges in exactly half the number of iterations compared to the standard parallel schedule. In this correspondence we provide a theoretical motivation for this observation by proving it for single-path graphs.