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.
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, 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.
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.
The informed dynamic scheduling (IDS) strategies for the low-density parity check (LDPC) decoding have shown superior performance in error correction and convergence speed, particularly those based on reliability measures and residual belief propagation (RBP). However, the search for the most unreliable variable nodes and the residual precomputation required for each iteration of the IDS-LDPC increases the complexity of the decoding process which becomes more sequential, making it hard to exploit the parallelism of signal processing algorithms available in multicore platforms. To overcome this problem, a new, low-complexity scheduling system, called layered vicinal variable nodes scheduling (LWNS) is presented in this paper. With this LWNS, each variable node is updated by exchanging intrinsic information with all its associated control and variable nodes before moving to the next variable node updating. The proposed scheduling strategy is fixed by a preprocessing step of the parity control matrix instead of calculation of the residuals values and by computation of the most influential variable node instead the most unreliable metric. It also allows the parallel processing of independent Tanner graph subbranches identified and grouped in layers. Our simulation results show that the LWNS BP have an attractive convergence rate and better error correction performance with low complexity when compared to previous IDS decoders under the white Gaussian noise channel (AWGN).
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 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.