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

Improving the Belief-Propagation Convergence of Irregular LDPC Codes Using Column-Weight Based Scheduling

Chaudhry Adnan Aslam, Yong Liang Guan, Kui Cai

Published Jun 11, 2015• 31 citations
Publisher

Abstract

In this letter, a novel scheduling scheme for decoding irregular low-density parity-check (LDPC) code, based on the column weight of variable nodes in the code graph, is introduced. In this scheme, the irregular LDPC code is decoded using the shuffled belief-propagation (BP) algorithm by selecting the variable nodes in descending order of their column weight. Via numerical simulation, it is shown that the proposed high-to-low column-weight based decoding schedule can noticeably increase the convergence speed at medium to high signal-to-noise ratio (SNR) over AWGN and Rayleigh fading channels without introducing additional complexity or error rate degradation. Furthermore, it is found that the improvement in decoding convergence is proportional to the maximum column-weight in the code graph.

DOI
10.1109/lcomm.2015.2444381

Related papers

Informed Fixed Scheduling for Faster Convergence of Shuffled Belief-Propagation Decoding

Chaudhry Adnan Aslam, Yong Liang Guan, Kui Cai +1 more

A novel informed fixed scheduling (IFS) scheme for shuffled belief-propagation (BP) decoding of binary low-density parity-check (LDPC) code is introduced to improve the BP decoding convergence. The IFS finds an appropriate order of variable nodes in accordance with the number of updated neighbors in the code graph, ensuring that the maximum number of latest message updates is utilized within a single iteration. This allows the utilization of most reliable message updates in a timely manner, leading to faster error-rate convergence. Simulation results show that the proposed IFS scheme improves the convergence speed of BP decoder by up to 20% for regular LDPC codes and 45% for irregular LDPC codes, without affecting the error-rate performance, at medium-to-high signal-to-noise ratio over binary-input additive white Gaussian noise channel.

IEEE Communications Letters•Oct 13, 2016•22 citations

An efficient scheduling scheme for layered belief propagation decoding of regular LDPC codes

Hua Li, Hong Wei Ding, Linhua Zheng +3 more

Schedule plays an important role in layered belief propagation (BP) decoding of low-density parity-check (LDPC) codes. It affects the error-rate performance as well as convergence rate of the decoder. In this paper, an efficient scheduling scheme is proposed to arrange the updating order of check nodes for layered BP decoder of regular LDPC codes. This scheme selects check node one at a time based on the reliability of the variable nodes. Specifically each time the check node with maximum number of low-reliability neighbors is selected. For simplicity, we introduce the updating state instead of the real-time messages to represent variable-node reliability. Simulation results on regular LDPC codes prove that the proposed scheduling scheme can obtain efficient schedules with fast convergence and good error-rate performance.

International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT)•Oct 1, 2016•6 citations

Improved Decoding of Binary and Non-Binary LDPC Codes by Probabilistic Shuffled Belief Propagation

Moritz Beermann, Laurent Schmalen, Peter Vary

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 utterly complex, suboptimal decoders have to be employed. One of the most popular decoding algorithms of LDPC codes is belief propagation (BP) decoding. In this paper, we present a novel scheduling for belief propagation decoding of LDPC codes. The new approach combines probabilistic scheduling with the known shuffled and check-shuffled serial scheduling algorithms. The resulting probabilistic shuffled and probabilistic check-shuffled decoders show a superior performance in terms of residual bit error rate. The drawback is that the convergence speed is slightly decreased. However, the convergence is still faster than for the standard and probabilistic flooding algorithms. Furthermore, we have adapted the probabilistic flooding schedule and the proposed probabilistic shuffled schedule to the non-binary case. We show that the aforementioned effects on the binary decoder can similarly be observed when applying the different schedules to the decoding of LDPC codes over higher order Galois fields.

International Conference on Communications•Jun 1, 2011•4 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

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

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
In this letter, a novel scheduling scheme for decoding irregular low-density parity-check (LDPC) code, based on the column weight of variable nodes in the code graph, is introduced. In this scheme, the irregular LDPC code is decoded using the shuffled belief-propagation (BP) algorithm by selecting the variable nodes in descending order of their column weight. Via numerical simulation, it is shown that the proposed high-to-low column-weight based decoding schedule can noticeably increase the convergence speed at medium to high signal-to-noise ratio (SNR) over AWGN and Rayleigh fading channels without introducing additional complexity or error rate degradation. Furthermore, it is found that the improvement in decoding convergence is proportional to the maximum column-weight in the code graph.
A novel informed fixed scheduling (IFS) scheme for shuffled belief-propagation (BP) decoding of binary low-density parity-check (LDPC) code is introduced to improve the BP decoding convergence. The IFS finds an appropriate order of variable nodes in accordance with the number of updated neighbors in the code graph, ensuring that the maximum number of latest message updates is utilized within a single iteration. This allows the utilization of most reliable message updates in a timely manner, leading to faster error-rate convergence. Simulation results show that the proposed IFS scheme improves the convergence speed of BP decoder by up to 20% for regular LDPC codes and 45% for irregular LDPC codes, without affecting the error-rate performance, at medium-to-high signal-to-noise ratio over binary-input additive white Gaussian noise channel.
Schedule plays an important role in layered belief propagation (BP) decoding of low-density parity-check (LDPC) codes. It affects the error-rate performance as well as convergence rate of the decoder. In this paper, an efficient scheduling scheme is proposed to arrange the updating order of check nodes for layered BP decoder of regular LDPC codes. This scheme selects check node one at a time based on the reliability of the variable nodes. Specifically each time the check node with maximum number of low-reliability neighbors is selected. For simplicity, we introduce the updating state instead of the real-time messages to represent variable-node reliability. Simulation results on regular LDPC codes prove that the proposed scheduling scheme can obtain efficient schedules with fast convergence and good error-rate performance.
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 utterly complex, suboptimal decoders have to be employed. One of the most popular decoding algorithms of LDPC codes is belief propagation (BP) decoding. In this paper, we present a novel scheduling for belief propagation decoding of LDPC codes. The new approach combines probabilistic scheduling with the known shuffled and check-shuffled serial scheduling algorithms. The resulting probabilistic shuffled and probabilistic check-shuffled decoders show a superior performance in terms of residual bit error rate. The drawback is that the convergence speed is slightly decreased. However, the convergence is still faster than for the standard and probabilistic flooding algorithms. Furthermore, we have adapted the probabilistic flooding schedule and the proposed probabilistic shuffled schedule to the non-binary case. We show that the aforementioned effects on the binary decoder can similarly be observed when applying the different schedules to the decoding of LDPC codes over higher order Galois fields.
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.
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.
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.