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

IEEE Communications Letters

Low-Complexity Belief-Propagation Decoding via Dynamic Silent-Variable-Node-Free Scheduling

Chaudhry Adnan Aslam, Yong Liang Guan, Kui Cai, Guojun Han

Published Oct 4, 2016• 25 citations
Publisher

Abstract

This letter presents a low-complexity scheduling scheme, referred to as the dynamic silent-variable-node-free scheduling (D-SVNFS) scheme, for the sequential belief propagation decoding of LDPC code. The D-SVNFS regulates the dynamic propagation of message updates based on the check-to-variable message residuals. To determine the next message update, it computes the on-demand message residuals and selects the largest one associated with the last updated variable and check nodes. In addition, the D-SVNFS attempts to propagate more message updates toward the erroneous variable nodes, trying to correct them with higher priority. It is shown that the proposed scheduling reduces the BP decoding complexity by up to 70% compared with prior-art SVNF scheme, without affecting the error-rate performance, at medium to high signal-to-noise ratio over the BI-AWGN and Rayleigh fading channels.

DOI
10.1109/lcomm.2016.2615016

Related papers

Two Informed Dynamic Scheduling Strategies for Iterative LDPC Decoders

Huang–Chang Lee, Yeong-Luh Ueng, Shan-Ming Yeh +1 more

When residual belief-propagation (RBP), which is a kind of informed dynamic scheduling (IDS), is applied to low-density parity-check (LDPC) codes, the convergence speed in error-rate performance can be significantly improved. However, the RBP decoders presented in previous literature suffer from poor convergence error-rate performance due to the two phenomena explored in this paper. The first is the greedy-group phenomenon, which results in a small part of the decoding graph occupying most of the decoding resources. By limiting the number of updates for each edge message in the decoding graph, the proposed Quota-based RBP (Q-RBP) schedule can reduce the probability of greedy groups forming. The other phenomenon is the silent-variable-nodes issue, which is a condition where some variable nodes have no chance of contributing their intrinsic messages to the decoding process. As a result, we propose the Silent-Variable-Node-Free RBP (SVNF-RBP) schedule, which can force all variable nodes to contribute their intrinsic messages to the decoding process equally. Both the Q-RBP and the SVNF-RBP provide appealing convergence speed and convergence error-rate performance compared to previous IDS decoders for both dedicated and punctured LDPC codes.

IEEE Transactions on Communications•Feb 1, 2013•47 citations

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

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

Variable-Node-Based Dynamic Scheduling Strategy for Belief-Propagation Decoding of LDPC Codes

Xingcheng Liu, Yuanbin Zhang, Ru Cui

Among the belief-propagation (BP) decoding algorithms of low-density parity-check (LDPC) codes, the algorithms based on dynamic scheduling strategy show excellent performance. In this letter, we propose a variable-node-based dynamic scheduling decoding algorithm. For the proposed algorithm, the reliability of variable nodes is evaluated based on the log-likelihood ratio (LLR) values and the parity-check equations; then, a more accurate dynamic selection strategy is presented. Simultaneously, the oscillating variable nodes are processed so that the influence of the spread of error messages caused by oscillation are suppressed. In addition, the proposed algorithm updates the same number of messages in one iteration as the original BP decoding algorithm does, which is different from some other dynamic decoding algorithms. Simulation results demonstrate that the proposed algorithm outperforms other algorithms.

IEEE Communications Letters•Dec 22, 2014•47 citations

Low-Complexity Check-Node-Based Serial Scheduling Belief Propagation for LDPC Codes

Lenan Wu

Compared to classic channel coding,Low-density parity-check(LDPC) codes have proved to be very powerful channel coding schemes with a broad range of applications.However,as maximum-likelihood decoding is too complex to implement,suboptimal decoders have to be employed.One of the most popular decoding algorithms of LDPC codes is belief propagation(BP) decoding.Informed Dynamic Scheduling(IDS) can provide a better BER performance,but hard to implement due to high computational complexity increased.In order to improve the convergence,a simple low-complexity sequential check-node-based scheduling strategy is proposed.A new check-node-based reliability measure is defined,which represents the degree of reliability approximately.The reliability measure is used for ordering while the actual message updates still use the exact BP equations.During an iteration,the schedule strategy finds an update sequence,which is arranged by the new defined reliability measure in ascending order.Complexity is compared among those algorithms.Mechanism why the new strategy works effective is presented.Simulation shows that the new approach significantly improves the BER performance using short-length block LDPC codes and reduces iterations.

Journal of Signal Processing•Jan 1, 2013•2 citations

Low-Complexity LDPC Decoding Algorithm Based on Layered Vicinal Variable Node Scheduling

Mhammed Benhayoun, Mouhcine Razi, Anas Mansouri +1 more

The informed dynamic scheduling (IDS) strategies for the low-density parity check (LDPC) decoding have shown superior performance in error correction and convergence speed, particularly those based on reliability measures and residual belief propagation (RBP). However, the search for the most unreliable variable nodes and the residual precomputation required for each iteration of the IDS-LDPC increases the complexity of the decoding process which becomes more sequential, making it hard to exploit the parallelism of signal processing algorithms available in multicore platforms. To overcome this problem, a new, low-complexity scheduling system, called layered vicinal variable nodes scheduling (LWNS) is presented in this paper. With this LWNS, each variable node is updated by exchanging intrinsic information with all its associated control and variable nodes before moving to the next variable node updating. The proposed scheduling strategy is fixed by a preprocessing step of the parity control matrix instead of calculation of the residuals values and by computation of the most influential variable node instead the most unreliable metric. It also allows the parallel processing of independent Tanner graph subbranches identified and grouped in layers. Our simulation results show that the LWNS BP have an attractive convergence rate and better error correction performance with low complexity when compared to previous IDS decoders under the white Gaussian noise channel (AWGN).

Modelling and Simulation in Engineering•Jan 19, 2022•4 citations
This letter presents a low-complexity scheduling scheme, referred to as the dynamic silent-variable-node-free scheduling (D-SVNFS) scheme, for the sequential belief propagation decoding of LDPC code. The D-SVNFS regulates the dynamic propagation of message updates based on the check-to-variable message residuals. To determine the next message update, it computes the on-demand message residuals and selects the largest one associated with the last updated variable and check nodes. In addition, the D-SVNFS attempts to propagate more message updates toward the erroneous variable nodes, trying to correct them with higher priority. It is shown that the proposed scheduling reduces the BP decoding complexity by up to 70% compared with prior-art SVNF scheme, without affecting the error-rate performance, at medium to high signal-to-noise ratio over the BI-AWGN and Rayleigh fading channels.
When residual belief-propagation (RBP), which is a kind of informed dynamic scheduling (IDS), is applied to low-density parity-check (LDPC) codes, the convergence speed in error-rate performance can be significantly improved. However, the RBP decoders presented in previous literature suffer from poor convergence error-rate performance due to the two phenomena explored in this paper. The first is the greedy-group phenomenon, which results in a small part of the decoding graph occupying most of the decoding resources. By limiting the number of updates for each edge message in the decoding graph, the proposed Quota-based RBP (Q-RBP) schedule can reduce the probability of greedy groups forming. The other phenomenon is the silent-variable-nodes issue, which is a condition where some variable nodes have no chance of contributing their intrinsic messages to the decoding process. As a result, we propose the Silent-Variable-Node-Free RBP (SVNF-RBP) schedule, which can force all variable nodes to contribute their intrinsic messages to the decoding process equally. Both the Q-RBP and the SVNF-RBP provide appealing convergence speed and convergence error-rate performance compared to previous IDS decoders for both dedicated and punctured LDPC codes.
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.
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.
Among the belief-propagation (BP) decoding algorithms of low-density parity-check (LDPC) codes, the algorithms based on dynamic scheduling strategy show excellent performance. In this letter, we propose a variable-node-based dynamic scheduling decoding algorithm. For the proposed algorithm, the reliability of variable nodes is evaluated based on the log-likelihood ratio (LLR) values and the parity-check equations; then, a more accurate dynamic selection strategy is presented. Simultaneously, the oscillating variable nodes are processed so that the influence of the spread of error messages caused by oscillation are suppressed. In addition, the proposed algorithm updates the same number of messages in one iteration as the original BP decoding algorithm does, which is different from some other dynamic decoding algorithms. Simulation results demonstrate that the proposed algorithm outperforms other algorithms.
Compared to classic channel coding,Low-density parity-check(LDPC) codes have proved to be very powerful channel coding schemes with a broad range of applications.However,as maximum-likelihood decoding is too complex to implement,suboptimal decoders have to be employed.One of the most popular decoding algorithms of LDPC codes is belief propagation(BP) decoding.Informed Dynamic Scheduling(IDS) can provide a better BER performance,but hard to implement due to high computational complexity increased.In order to improve the convergence,a simple low-complexity sequential check-node-based scheduling strategy is proposed.A new check-node-based reliability measure is defined,which represents the degree of reliability approximately.The reliability measure is used for ordering while the actual message updates still use the exact BP equations.During an iteration,the schedule strategy finds an update sequence,which is arranged by the new defined reliability measure in ascending order.Complexity is compared among those algorithms.Mechanism why the new strategy works effective is presented.Simulation shows that the new approach significantly improves the BER performance using short-length block LDPC codes and reduces iterations.
The informed dynamic scheduling (IDS) strategies for the low-density parity check (LDPC) decoding have shown superior performance in error correction and convergence speed, particularly those based on reliability measures and residual belief propagation (RBP). However, the search for the most unreliable variable nodes and the residual precomputation required for each iteration of the IDS-LDPC increases the complexity of the decoding process which becomes more sequential, making it hard to exploit the parallelism of signal processing algorithms available in multicore platforms. To overcome this problem, a new, low-complexity scheduling system, called layered vicinal variable nodes scheduling (LWNS) is presented in this paper. With this LWNS, each variable node is updated by exchanging intrinsic information with all its associated control and variable nodes before moving to the next variable node updating. The proposed scheduling strategy is fixed by a preprocessing step of the parity control matrix instead of calculation of the residuals values and by computation of the most influential variable node instead the most unreliable metric. It also allows the parallel processing of independent Tanner graph subbranches identified and grouped in layers. Our simulation results show that the LWNS BP have an attractive convergence rate and better error correction performance with low complexity when compared to previous IDS decoders under the white Gaussian noise channel (AWGN).