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

Electronics Letters

Derived dynamic scheduling for belief propagation decoding of LDPC codes

Xiaotian Xu, Hua Ren Zhou, Jiayi Zhao

Published Feb 1, 2024• 1 citation
Publisher

Abstract

Abstract Among numerous dynamic scheduling strategies for low‐density parity‐check codes, many of them are of high complexity due to repetitive computation and ordering of belief residuals. To address these challenges, two novel approaches are proposed: the derived informed variable‐to‐check residual belief propagation and the derived variable‐node and variable‐to‐check‐edge residual belief propagation for low‐density parity‐check codes. Simulation results show that the derived dynamic scheduling exhibits a substantial gain of approximately 0.15 dB in signal‐to‐noise ratio over the non‐derived one with considerably lower decoding complexity when targeting a bit‐error rate of 10 −4 .

DOI
10.1049/ell2.13130

Related papers

An efficient dynamic schedule for layered belief-propagation decoding of LDPC codes

Guojun Han, Xingcheng Liu

An efficient dynamic schedule for layered belief-propagation (LBP) decoding of low-density parity-check (LDPC) codes is presented, in which the check nodes connecting to a variable node with maximum relative message residual are chosen in each dynamic decoding iteration, and then LBP is performed for these check nodes. In this schedule we combined the features of lazy schedule and node-wise residual belief propagation (NWRBP) together while keeping the extra computational complexity very low. Simulation results show that the new schedule speeds up the convergence rate and greatly improves error performance at medium to high signal-to-noise ratio (SNR) when compared to the standard LBP decoding algorithm.

IEEE Communications Letters•Dec 1, 2009•29 citations

Dynamic Schedules Based on Variable Nodes Residual for LDPC Codes

Guojun Han, Xingcheng Liu

Layered belief-propagation (LBP) with dynamic schedule for low-density parity-check (LDPC) codes using variable nodes residual is presented. The proposed schedule outperforms the conventional LBP with predetermined schedule both in terms of convergence speed and error performance. As compared with node-wised residual belief-propagation (NRBP), it has much lower extra complexity. For LDPC code constructed by PEG, simulation results show that the new schedule offers better error performance and requires much lower extra complexity.

International Conference on Wireless Communications, Networking and Mobile Computing•Sep 1, 2009•4 citations

Reliability-based high-efficient dynamic schedules for belief propagation decoding of LDPC codes

Lijun Zhang, Jie Huang, L. L. Cheng

Four reliability-based high-efficient dynamic schedules (RHDS) for belief propagation (BP) decoding of low-density parity-check codes are proposed. The RHDS only processes one variable (or check) node, which has the maximum relative residual among all the variable (or check) nodes in each decoding iteration, thus keeping less greediness and decreasing complexity in comparison with egde-wise variable-to-check residual belief propagation (VC-RBP) algorithm. Simulation results show that RHDS's convergence rate is higher than VC-RBP while still keeping very low computational complexity.

International Conference on Signal Processing•Oct 1, 2012•3 citations

Variable-to-Check Residual Belief Propagation for informed dynamic scheduling of LDPC codes

Jung Hyun Kim, Mi-Young Nam, Hong‐Yeop Song +1 more

We propose Variable-to-Check Residual Belief Propagation (VCRBP) for LDPC decoding for faster convergence, better error correcting performance and lower complexity. It is similar to Residual Belief Propagation (RBP) that was recently applied to LDPC decoding by Vila Casado et al. because it is also a dynamic scheduling belief propagation using residuals, but it is different because its residuals are computed from variable-to-check message. Simulation shows that it out-performs with only maximum 8 iterations by about 0.3 dB compared with RBP at an FER of 10-4. Also, we propose node-wise VCRBP (N-VCRBP) for reducing complexity of VCRBP. N-VCRBP also exhibits the performance very close to VCRBP but with significantly lower decoding complexity.

International Symposium on Information Theory and its Applications•Dec 1, 2008•14 citations

Edge-Based Dynamic Scheduling for Belief-Propagation Decoding of LDPC and RS Codes

Chaudhry Adnan Aslam, Yong Liang Guan, Kui Cai

This paper presents two low-complexity edge-based scheduling schemes, referred to as the e-Flooding and e-Shuffled schedules, for the belief-propagation (BP) decoding of low-density parity-check and Reed-Solomon codes. The proposed schedules selectively update the edges of the code graph based on the run-time reliability of variable and check nodes. Specifically, new message update is propagated exclusively along the unreliable edges of the code graph. This reduces the decoding complexity of BP algorithm as only a partial set of message updates is computed per decoding iteration. Besides, restricting the flow of message updates may also precludes the occurrence of some short graph cycles, which helps to preserve the BP message independence at certain variable and check nodes. Using numerical simulations, it is shown that the proposed edge-based schedules reduce the BP decoding complexity by more than 90% compared with the prior-art BP schedules, while simultaneously improving the error-rate performance, at medium-to-high signal-to-noise ratio over additive white Gaussian noise channel.

IEEE Transactions on Communications•Dec 9, 2016•21 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
Abstract Among numerous dynamic scheduling strategies for low‐density parity‐check codes, many of them are of high complexity due to repetitive computation and ordering of belief residuals. To address these challenges, two novel approaches are proposed: the derived informed variable‐to‐check residual belief propagation and the derived variable‐node and variable‐to‐check‐edge residual belief propagation for low‐density parity‐check codes. Simulation results show that the derived dynamic scheduling exhibits a substantial gain of approximately 0.15 dB in signal‐to‐noise ratio over the non‐derived one with considerably lower decoding complexity when targeting a bit‐error rate of 10 −4 .
An efficient dynamic schedule for layered belief-propagation (LBP) decoding of low-density parity-check (LDPC) codes is presented, in which the check nodes connecting to a variable node with maximum relative message residual are chosen in each dynamic decoding iteration, and then LBP is performed for these check nodes. In this schedule we combined the features of lazy schedule and node-wise residual belief propagation (NWRBP) together while keeping the extra computational complexity very low. Simulation results show that the new schedule speeds up the convergence rate and greatly improves error performance at medium to high signal-to-noise ratio (SNR) when compared to the standard LBP decoding algorithm.
Layered belief-propagation (LBP) with dynamic schedule for low-density parity-check (LDPC) codes using variable nodes residual is presented. The proposed schedule outperforms the conventional LBP with predetermined schedule both in terms of convergence speed and error performance. As compared with node-wised residual belief-propagation (NRBP), it has much lower extra complexity. For LDPC code constructed by PEG, simulation results show that the new schedule offers better error performance and requires much lower extra complexity.
Four reliability-based high-efficient dynamic schedules (RHDS) for belief propagation (BP) decoding of low-density parity-check codes are proposed. The RHDS only processes one variable (or check) node, which has the maximum relative residual among all the variable (or check) nodes in each decoding iteration, thus keeping less greediness and decreasing complexity in comparison with egde-wise variable-to-check residual belief propagation (VC-RBP) algorithm. Simulation results show that RHDS's convergence rate is higher than VC-RBP while still keeping very low computational complexity.
We propose Variable-to-Check Residual Belief Propagation (VCRBP) for LDPC decoding for faster convergence, better error correcting performance and lower complexity. It is similar to Residual Belief Propagation (RBP) that was recently applied to LDPC decoding by Vila Casado et al. because it is also a dynamic scheduling belief propagation using residuals, but it is different because its residuals are computed from variable-to-check message. Simulation shows that it out-performs with only maximum 8 iterations by about 0.3 dB compared with RBP at an FER of 10-4. Also, we propose node-wise VCRBP (N-VCRBP) for reducing complexity of VCRBP. N-VCRBP also exhibits the performance very close to VCRBP but with significantly lower decoding complexity.
This paper presents two low-complexity edge-based scheduling schemes, referred to as the e-Flooding and e-Shuffled schedules, for the belief-propagation (BP) decoding of low-density parity-check and Reed-Solomon codes. The proposed schedules selectively update the edges of the code graph based on the run-time reliability of variable and check nodes. Specifically, new message update is propagated exclusively along the unreliable edges of the code graph. This reduces the decoding complexity of BP algorithm as only a partial set of message updates is computed per decoding iteration. Besides, restricting the flow of message updates may also precludes the occurrence of some short graph cycles, which helps to preserve the BP message independence at certain variable and check nodes. Using numerical simulations, it is shown that the proposed edge-based schedules reduce the BP decoding complexity by more than 90% compared with the prior-art BP schedules, while simultaneously improving the error-rate performance, at medium-to-high signal-to-noise ratio over additive white Gaussian noise channel.
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.