Recent studies show that dynamic scheduling using the latest available information is superior to the flooding scheduling. While the existing works on informed dynamic scheduling focus on belief propagation (BP) based algorithm for binary LDPC codes, in this paper we devise novel methods which are appropriate for majority-logic decoding of non-binary LDPC codes. Firstly we propose a low complexity extrinsic message based decoding algorithm for non-binary LDPC codes. The novelty of this decoding algorithm lies in that we compute extrinsic messages and iteratively update the messages in every iteration. Then we propose a dynamic scheduling schemes specifically designed for majority-logic decoding of non-binary LDPC codes. The proposed scheduling method, named informed dynamic scheduling, can achieve better performance compared with the layered and the flooding schemes.
Recent studies show that dynamic scheduling using the latest available information is superior to the flooding scheduling. While the existing works on informed dynamic scheduling focus on belief propagation (BP) based algorithm for binary LDPC codes, in this paper we devise novel methods which are appropriate for majority-logic decoding of non-binary LDPC codes. Firstly we propose a low complexity extrinsic message based decoding algorithm for non-binary LDPC codes. The novelty of this decoding algorithm lies in that we compute extrinsic messages and iteratively update the messages in every iteration. Then we propose a dynamic scheduling schemes specifically designed for majority-logic decoding of non-binary LDPC codes. The proposed scheduling method, named informed dynamic scheduling, can achieve better performance compared with the layered and the flooding schemes.
Recent studies show that dynamic scheduling using the latest available information is superior to the flooding scheduling. While the existing works on informed dynamic scheduling focus on belief propagation (BP) based algorithm for binary LDPC codes, in this paper we devise a novel method which is appropriate for majority-logic decoding of non-binary LDPC codes. We firstly clarify that previous methods are not suitable for majority-logic decoding of non-binary LDPC codes. Then we give a practical scheduling strategy which utilizes the stability of check nodes to select the messages for propagation. Furthermore, we discuss the computational complexity of this proposed scheme in detail. Simulation results verify that our approach can achieve better performance compared with layered and flooding schemes.
The simultaneous flooding scheduling is popular for Low-Density Parity-Check (LDPC) Belief Propagation (BP) decoding. Non-simultaneous sequential scheduling is superior to the flooding scheduling, and asynchronous dynamic scheduling has better FER performance than the sequential scheduling. However, all strategies encounter the trouble of locating the error variable node. This paper proposes an informed dynamic scheduling strategy, which utilizes the instability of the variable node and the residual of the variable-to-check message to locate the message to be updated first. The informed dynamic scheduling overcomes the trapping sets effectively. This paper also designs an informed dynamic scheduling strategy with adaptivity to pass more messages in parallel, which effectively postpones the influence of cycles in the Tanner graph. In some sense, the strategy lengthens cycles. Simulation results show that the two informed dynamic scheduling strategies outperform other algorithms.
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.
The simultaneous flooding scheduling is popular for Low-Density Parity-Check (LDPC) Belief Propagation (BP) decoding. Non-simultaneous sequential scheduling is superior to the flooding scheduling, and asynchronous dynamic scheduling has better FER performance than the sequential scheduling. However, all strategies encounter the trouble of locating the error variable node. This paper proposes an informed dynamic scheduling strategy, which utilizes the instability of the variable node and the residual of the variable-to-check message to locate the message to be updated first. The informed dynamic scheduling overcomes the trapping sets effectively. This paper also designs an informed dynamic scheduling strategy with adaptivity to pass more messages in parallel, which effectively postpones the influence of cycles in the Tanner graph. In some sense, the strategy lengthens cycles. Simulation results show that the two informed dynamic scheduling strategies outperform other 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.
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.