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 International Conference on Communication Software and Networks

High-Throughput Dynamic Scheduling for Belief-Propagation Decoding of LDPC Codes

Suipeng Xie, Xingcheng Liu

Published Jun 1, 2019• 0 citations
Publisher

Abstract

Low-density parity-check (LDPC) codes, usually decoded using the informed dynamic scheduling (IDS) algorithms, are well applicable to the 5th-generation communication systems (5G). However, the IDS algorithm is greedy because of the update-relayed trend. The update-relayed trend leads to the unreasonable allocation of decoding resources, which exerts a huge impact on the decoding performance. To solve this greedy problem, we proposed the decoding algorithm based on random select of check nodes with a predefined update range (RSPUR). By decoding with a narrow update range, the RSPUR algorithm effectively suppresses the update-relayed trend and allocates the decoding resources in a more rational way. Simulation results indicate that the proposed algorithm achieves excellent error-correction performance and high throughput compared to the previous IDS algorithms.

DOI
10.1109/iccsn.2019.8905289

Related papers

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

Enhanced Informed Dynamic BP Decoding Scheduling Strategies for 5G NR LDPC Codes

Tofar C.-Y. Chang, I-Hsiang Lee, Pin-Han Wang +2 more

We present an enhanced informed dynamic scheduling (IDS) strategy to avoid propagations of unreliable messages in the residual belief-propagation (RBP) algorithm for decoding low-density parity-check (LDPC) codes. To reduce the resource needed for updating the degree-one variable nodes (VNs) in an RBP-based algorithm for decoding 5G New Radio (NR) LDPC codes, we further introduce a process consisting of several simple procedures for managing the resource consumption. Simulation results demonstrate that our RBP algorithm based on the proposed IDS strategy outperforms existing RBP-based algorithms at the early decoding iterations. By using our degree-one VN resource managing approach, the performance of both the proposed and the existing decoders is significantly improved in decoding the 5G NR codes.

IEEE Vehicular Technology Conference•Sep 1, 2022•1 citation

LDPC decoding with locally informed dynamic scheduling based on the law of large numbers

Shuo Peng Liang, Suipeng Xie, Xingcheng Liu +1 more

Abstract The informed dynamic scheduling (IDS) strategies, in which the edge message with the maximum message‐residual is updated preferentially, achieve remarkable error‐correction performance when applied to low‐density parity‐check (LDPC) codes. However, the IDS strategies incur inferior convergence in iterative decoding owing to the greedy problem, which is called the update‐relayed trend here. In order to solve the greediness, two locally informed dynamic scheduling algorithms based on the law of large numbers are proposed. The proposed decoding algorithms use random select of check nodes over a predefined update range (RSPUR) which effectively suppresses the propagation of the update‐relayed trend and accordingly restrains the forming of multi‐update cycles. Moreover, the decoding algorithm is further improved based on random select of check nodes over an adjustable update range (RSCAR). The update ranges are selected based on the law of large numbers. Therefore, the computational resources can be allocated more equitably by increasing iterations. Simulation results show that both the proposed algorithms achieve excellent performance in terms of throughput and convergence with low decoding complexity over the Additive White Gaussian Noise (AWGN) and the fading channels compared to the previous IDS strategies. Hence, the proposed algorithms behave excellently over the wireless channels.

IET Communications•Mar 2, 2022•2 citations

Dynamic Scheduling Decoding of LDPC Codes Based on Tabu Search

Xingcheng Liu, Chunlei Fan, Xuechen Chen

The informed dynamic scheduling (IDS) strategy decoding algorithms performed exceptionally well for low-density parity-check codes in terms of the error-rate performance. However, the IDS decoding algorithm is greedy because of the unfair computation resources allocation among different variables nodes, which leads to poor convergence performance. In order to reduce the greediness of the IDS algorithm, the tabu search (TS) algorithm is introduced to the dynamic scheduling-based decoding in this paper. In the TS-based dynamic scheduling (TSDS) algorithm, the variable nodes in the Tanner graph are temporarily stored in a tabu list. In the decoding process with the TSDS algorithm, variable nodes stored in the tabu list will not be selected and updated until they are shifted out of the tabu list. Besides, an improved updating order is provided for the TSDS algorithm, by which the computational complexity can be decreased without the loss of error correction performance. Simulation results show that the proposed algorithm outperforms other decoding algorithms of interest in terms of bit error rate and convergence performance over the additive white Gaussian noise channel.

IEEE Transactions on Communications•Jul 28, 2017•14 citations

Knowledge-aided informed dynamic scheduling for LDPC decoding

Cornelius T. Healy, Rodrigo C. de Lamare

Low-density parity-check (LDPC) codes offer excellent performance at competitive levels of complexity. Short block length LDPC codes avoid the large processing latency incurred by the large block lengths classically considered for this class of codes, making them a potential candidate for next generation wireless communications systems. In this paper, a novel informed dynamic scheduling (IDS) approach for decoding LDPC codes is developed based on the use of the current message reliabilities and the residuals of the potential updates to select the messages passed in the graph during iterative Sum Product decoding. An alternative measure of the iteration of the IDS schemes is also proposed which highlights the high cost of those algorithms in terms of processing complexity and motivates the development of the proposed approach. The proposed Rel.-RBP decoding algorithm offers very fast convergence at reduced complexity and gains in error rate performance when compared to the previous schemes.

•Jun 1, 2015•8 citations

Improved Informed Dynamic Scheduling Strategies for 5G LDPC Codes

Kunyang Li, Huai-Yi Li, Li Juan DENG +3 more

In this paper, we propose two new scheduling algorithms to address the issues of existing informed dynamic scheduling (IDS) decoding algorithms of short low-density parity-check (LDPC) codes for the fifth-generation (5G) new radio (NR). The first issue is the complexity problem, where the high complexity of IDS makes hardware implementation difficult. By considering the impact of puncturing for the first two columns of base matrices, the proposed least-punctured and sum-residual-based (LPSRB) algorithm can reduce decoding complexity. The second issue is the significant degradation of decoding performance when the code length is short. By fully utilizing residuals, the proposed novel residual belief propagation (NRBP) algorithm allocates a significant amount of decoding resources to the less convergent edges. Simulation results demonstrate that NRBP achieves better frame error rate (FER) performance for short LDPC codes.

IEEE International Conference on Communication Technology (ICCT)•Oct 20, 2023•1 citation
Low-density parity-check (LDPC) codes, usually decoded using the informed dynamic scheduling (IDS) algorithms, are well applicable to the 5th-generation communication systems (5G). However, the IDS algorithm is greedy because of the update-relayed trend. The update-relayed trend leads to the unreasonable allocation of decoding resources, which exerts a huge impact on the decoding performance. To solve this greedy problem, we proposed the decoding algorithm based on random select of check nodes with a predefined update range (RSPUR). By decoding with a narrow update range, the RSPUR algorithm effectively suppresses the update-relayed trend and allocates the decoding resources in a more rational way. Simulation results indicate that the proposed algorithm achieves excellent error-correction performance and high throughput compared to the previous IDS algorithms.
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.
We present an enhanced informed dynamic scheduling (IDS) strategy to avoid propagations of unreliable messages in the residual belief-propagation (RBP) algorithm for decoding low-density parity-check (LDPC) codes. To reduce the resource needed for updating the degree-one variable nodes (VNs) in an RBP-based algorithm for decoding 5G New Radio (NR) LDPC codes, we further introduce a process consisting of several simple procedures for managing the resource consumption. Simulation results demonstrate that our RBP algorithm based on the proposed IDS strategy outperforms existing RBP-based algorithms at the early decoding iterations. By using our degree-one VN resource managing approach, the performance of both the proposed and the existing decoders is significantly improved in decoding the 5G NR codes.
Abstract The informed dynamic scheduling (IDS) strategies, in which the edge message with the maximum message‐residual is updated preferentially, achieve remarkable error‐correction performance when applied to low‐density parity‐check (LDPC) codes. However, the IDS strategies incur inferior convergence in iterative decoding owing to the greedy problem, which is called the update‐relayed trend here. In order to solve the greediness, two locally informed dynamic scheduling algorithms based on the law of large numbers are proposed. The proposed decoding algorithms use random select of check nodes over a predefined update range (RSPUR) which effectively suppresses the propagation of the update‐relayed trend and accordingly restrains the forming of multi‐update cycles. Moreover, the decoding algorithm is further improved based on random select of check nodes over an adjustable update range (RSCAR). The update ranges are selected based on the law of large numbers. Therefore, the computational resources can be allocated more equitably by increasing iterations. Simulation results show that both the proposed algorithms achieve excellent performance in terms of throughput and convergence with low decoding complexity over the Additive White Gaussian Noise (AWGN) and the fading channels compared to the previous IDS strategies. Hence, the proposed algorithms behave excellently over the wireless channels.
The informed dynamic scheduling (IDS) strategy decoding algorithms performed exceptionally well for low-density parity-check codes in terms of the error-rate performance. However, the IDS decoding algorithm is greedy because of the unfair computation resources allocation among different variables nodes, which leads to poor convergence performance. In order to reduce the greediness of the IDS algorithm, the tabu search (TS) algorithm is introduced to the dynamic scheduling-based decoding in this paper. In the TS-based dynamic scheduling (TSDS) algorithm, the variable nodes in the Tanner graph are temporarily stored in a tabu list. In the decoding process with the TSDS algorithm, variable nodes stored in the tabu list will not be selected and updated until they are shifted out of the tabu list. Besides, an improved updating order is provided for the TSDS algorithm, by which the computational complexity can be decreased without the loss of error correction performance. Simulation results show that the proposed algorithm outperforms other decoding algorithms of interest in terms of bit error rate and convergence performance over the additive white Gaussian noise channel.
Low-density parity-check (LDPC) codes offer excellent performance at competitive levels of complexity. Short block length LDPC codes avoid the large processing latency incurred by the large block lengths classically considered for this class of codes, making them a potential candidate for next generation wireless communications systems. In this paper, a novel informed dynamic scheduling (IDS) approach for decoding LDPC codes is developed based on the use of the current message reliabilities and the residuals of the potential updates to select the messages passed in the graph during iterative Sum Product decoding. An alternative measure of the iteration of the IDS schemes is also proposed which highlights the high cost of those algorithms in terms of processing complexity and motivates the development of the proposed approach. The proposed Rel.-RBP decoding algorithm offers very fast convergence at reduced complexity and gains in error rate performance when compared to the previous schemes.
In this paper, we propose two new scheduling algorithms to address the issues of existing informed dynamic scheduling (IDS) decoding algorithms of short low-density parity-check (LDPC) codes for the fifth-generation (5G) new radio (NR). The first issue is the complexity problem, where the high complexity of IDS makes hardware implementation difficult. By considering the impact of puncturing for the first two columns of base matrices, the proposed least-punctured and sum-residual-based (LPSRB) algorithm can reduce decoding complexity. The second issue is the significant degradation of decoding performance when the code length is short. By fully utilizing residuals, the proposed novel residual belief propagation (NRBP) algorithm allocates a significant amount of decoding resources to the less convergent edges. Simulation results demonstrate that NRBP achieves better frame error rate (FER) performance for short LDPC codes.