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.
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.
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.
The informed dynamic scheduling (IDS) strategies for decoding of low-density parity-check codes obtained superior performance in error correction performance and convergence speed. However, there are still two problems existing in the current IDS algorithms. The first is that the current IDS algorithms only preferentially update the selected unreliable messages, but they do not guarantee the updating is performed with reliable information. In this paper, a two-step message selecting strategy is introduced. On the basis of the two reliability metrics and two types of variable node residuals, the residual belief propagation (BP) decoding algorithm, short for TRM-TVRBP, is proposed. With the algorithm, the reliability of the updating-messages can be improved. The second is the greediness problem, prevalently existed in the IDS-like algorithms. The problem arises mainly from the fact that the major computing resources are allocated to or concentrated on some nodes and edges. To overcome the problem, the reliability metric-based RBP algorithm (RM-RBP) is proposed, which can force every variable node to contribute its intrinsic information to the iterative decoding. At the same time, the algorithm can force the related variable nodes to be updated, and make every edge have an equal opportunity of being updated. The simulation results show that both the TRM-TVRBP and the RM-RBP have appealing convergence rate and error-correcting performance compared with the previous IDS decoders over the white Gaussian noise (AWGN) channel.
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.
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.
Abstract The residual belief propagation (RBP) algorithm, which is the most classic informed dynamic scheduling strategy, achieves outstanding performance in error correction and can drastically accelerate convergence speed. However, the greedy algorithmic property of this iterative decoding will inevitably cause loss of decoding performance. To address this, a novel algorithm called the partial average bundle residual belief propagation (PABRBP) is proposed in this paper. According to the construction characteristics of a base matrix of protograph‐LDPC codes, informed dynamic scheduling (IDS) strategies are applied to an edge bundle of base matrices for the first time. This edge bundle of the base matrix can be applied to a corresponding cyclic permutation matrix. Furthermore, the update level of each bundle is determined by the value of the Partially Average Bundle Residual (PABR). Therefore, the edge message with the maximum residual in each bundle is updated in order, and the process of iterative decoding is less likely to become trapped in a local optimum. Additionally, the generation of silent nodes is reduced as much as possible. To further improve the PABRBP decoding performance for medium and long codes over the fading channel, the adjusted compensation term is periodically introduced. Analysis and simulation results show that PABRBP demonstrates a notable convergence quality and decoding performance improvement over the fading channels compared to existing state‐of‐art IDS algorithms.
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.