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.
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.
Low‐density parity‐check (LDPC) codes have excellent performance for a wide range of applications at reasonable complexity. LDPC codes with short blocks avoid the high latency of codes with large block lengths, making them potential candidates for ultra reliable low‐latency applications of future wireless standards. In this work, a novel informed dynamic scheduling (IDS) strategy for decoding LDPC codes, denoted reliability‐based residual belief propagation (Rel‐RBP), is developed by exploiting the reliability of the message and the residuals of the possible updates to choose the messages to be used by the decoding algorithm. A different measure for each iteration of the IDS schemes is also presented, which underlies the high cost of those algorithms in terms of computational complexity and motivates the development of the proposed strategy. Simulations show that Rel‐RBP speeds up the decoding at reduced complexity and results in error rate performance gains over prior work.
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.
After the publication of the residual belief-propagation (RBP) algorithm, many low-density parity-check (LDPC) decoders using informed dynamic scheduling (IDS) have been investigated. In this paper, we propose the twofold-RBP (T-RBP) decoder that combines two residuals. Using T-RBP, significant improvement can be achieved in both convergence speed and convergence error-rate performance. In addition to T-RBP, the simplified-RBP (S-RBP) decoder is also proposed in order to reduce the complexity. Instead of comparing all the residuals of all edges in the code graph, as with previous IDS decoders, S-RBP only compares the residuals of the edges connected to a single check node, thus dramatically reduces the complexity without any significant degradation in performance. The proposed T-RBP and S-RBP can improve not only the performance of dedicated codes, but also that of punctured codes, especially the convergence speed. The improvement can make punctured LDPC codes more practical and becoming a competitive candidate for the rate compatible applications.
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 message-passing schedule of the BP algorithm significantly affects the performance of the LDPC decoder. The authors recently presented a novel message-passing schedule, called Informed Dynamic Scheduling (IDS), that selects the message-passing schedule according to the observed rate of change of the messages. IDS yields a lower error-rate performance than traditional message-passing schedules (such as flooding and LBP) because it solves traditional trapping-set errors. However, for short-blocklength LDPC codes, IDS algorithms present non-trapping-set errors in the error floor region. This paper presents a careful analysis of those errors and proposes mixed scheduling strategies, combining LBP with IDS, that solve these non-trapping-set errors. Also, we will show that some lower-complexity techniques, such as mixed scheduling, perform close to the best IDS strategies for larger-blocklength codes.
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.
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.