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 Transactions on Communications

Check Node Reliability-Based Scheduling for BP Decoding of Non-Binary LDPC Codes

Guojun Han, Yong Liang Guan, Xinmei Huang

Published Jan 21, 2013• 24 citations
Publisher

Abstract

Scheduling strategy is considered an important aspect of belief-propagation (BP) decoding of low-density parity-check (LDPC) codes because it affects the decoder's convergence rate, decoding complexity and error-correction performance. In this paper, we propose two new scheduling strategies for the BP decoding of non-binary LDPC (NB-LDPC) codes. Both the strategies are devised based on the concept of check node reliability and employ a heuristically defined threshold which can adapt to the communication channel variations. As the scheduling strategies only update a subset of the check nodes in each iteration, they result in reduced iteration cost. Furthermore, since the BP performs suboptimally for finite-length LDPC codes, especially for short-length LDPC codes, by enhancing the message propagation over the Tanner Graphs of short-length NB-LDPC codes, the new scheduling strategies can even improve the error-correction performances of BP decoding. Simulation results demonstrate that the new scheduling strategies provide good performance/complexity tradeoffs.

DOI
10.1109/tcomm.2013.011613.120249

Related papers

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

Research on scheduling strategy of non-binary LDPC codes decoding

Yaqiang Zhou, Yuan Tian, Yibing Li

Recently low-density parity check (LDPC) codes have been applied in more areas, and the research of non-binary LDPC codes has become more significant. In this paper, we establish a dynamic scheduling strategy to reduce complexity of non-binary LDPC codes decoding, and choose extended min-sum algorithm as the model. The dynamic scheduling strategy is based on the idea of nodes reliability. When decoding, we select a part of check nodes to update messages in real time according to the reliability rules, and only the variable nodes getting new messages can participate in the message propagation. Compared with usual standard flooding scheduling, this dynamic scheduling strategy can reduce decoding complexity effectively. We also optimize the message of variable nodes according to reliability, which ensure that the error correction performance of decoding algorithm is not affected. Our simulations over a BPSK-AWGN channel show that this dynamic scheduling strategy can reduce complexity in non-binary LDPC codes belief propagation decoding without affecting error correction performance.

Photonics & Electromagnetics Research Symposium - Fall (PIERS-Fall)•Nov 1, 2017•0 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

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

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

Research on LDPC code decoding algorithm based on scheduling strategy

Feng Xiao

With the rapid development of the channel coding technology, low density parity check(LDPC) code has been widely concerned by researchers all of the world as an approaching code to Shannon limit. Error floor is an important issue in the theory of LDPC codes and the research of iterative decoding algorithms. Based on the decoding of LDPC codes, a new improved decoding algorithm, Group Belief Propagation (GBP) based on variable nodes is proposed for the different scheduling strategies of the LDPC codes. According to the difference between the messages and the hard decision values, the variable nodes are divided into reliable nodes and unreliable nodes. And the unreliable nodes are priority to update. Further, the effect of threshold for judging the group on GBP strategy is analyzed. Simulation results show that the proposed algorithm can achieve better convergence and decoding performances compared to three classical scheduling algorithms. Meanwhile, it can overcome the error floor phenomenon caused by the trapping set effectively.

Chinese Control and Decision Conference (CCDC)•May 1, 2016•0 citations
Scheduling strategy is considered an important aspect of belief-propagation (BP) decoding of low-density parity-check (LDPC) codes because it affects the decoder's convergence rate, decoding complexity and error-correction performance. In this paper, we propose two new scheduling strategies for the BP decoding of non-binary LDPC (NB-LDPC) codes. Both the strategies are devised based on the concept of check node reliability and employ a heuristically defined threshold which can adapt to the communication channel variations. As the scheduling strategies only update a subset of the check nodes in each iteration, they result in reduced iteration cost. Furthermore, since the BP performs suboptimally for finite-length LDPC codes, especially for short-length LDPC codes, by enhancing the message propagation over the Tanner Graphs of short-length NB-LDPC codes, the new scheduling strategies can even improve the error-correction performances of BP decoding. Simulation results demonstrate that the new scheduling strategies provide good performance/complexity tradeoffs.
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.
Recently low-density parity check (LDPC) codes have been applied in more areas, and the research of non-binary LDPC codes has become more significant. In this paper, we establish a dynamic scheduling strategy to reduce complexity of non-binary LDPC codes decoding, and choose extended min-sum algorithm as the model. The dynamic scheduling strategy is based on the idea of nodes reliability. When decoding, we select a part of check nodes to update messages in real time according to the reliability rules, and only the variable nodes getting new messages can participate in the message propagation. Compared with usual standard flooding scheduling, this dynamic scheduling strategy can reduce decoding complexity effectively. We also optimize the message of variable nodes according to reliability, which ensure that the error correction performance of decoding algorithm is not affected. Our simulations over a BPSK-AWGN channel show that this dynamic scheduling strategy can reduce complexity in non-binary LDPC codes belief propagation decoding without affecting error correction performance.
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.
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.
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.
With the rapid development of the channel coding technology, low density parity check(LDPC) code has been widely concerned by researchers all of the world as an approaching code to Shannon limit. Error floor is an important issue in the theory of LDPC codes and the research of iterative decoding algorithms. Based on the decoding of LDPC codes, a new improved decoding algorithm, Group Belief Propagation (GBP) based on variable nodes is proposed for the different scheduling strategies of the LDPC codes. According to the difference between the messages and the hard decision values, the variable nodes are divided into reliable nodes and unreliable nodes. And the unreliable nodes are priority to update. Further, the effect of threshold for judging the group on GBP strategy is analyzed. Simulation results show that the proposed algorithm can achieve better convergence and decoding performances compared to three classical scheduling algorithms. Meanwhile, it can overcome the error floor phenomenon caused by the trapping set effectively.