In this study, we investigate the characteristics of scheduling sequences that enable efficient decoding of generalized low-density parity-check (GLDPC) codes under the layered message-passing algorithm. In particular, we show that scheduling sequences leading to higher decoding efficiency should prioritize the update of constraint nodes corresponding to subcodes with larger minimum distance, fewer minimum-weight codewords, and shorter code length. Based on these characteristics, we design a scheduling algorithm, which further demonstrates the effectiveness of these characteristics through simulation experiments.
In this study, we investigate the characteristics of scheduling sequences that enable efficient decoding of generalized low-density parity-check (GLDPC) codes under the layered message-passing algorithm. In particular, we show that scheduling sequences leading to higher decoding efficiency should prioritize the update of constraint nodes corresponding to subcodes with larger minimum distance, fewer minimum-weight codewords, and shorter code length. Based on these characteristics, we design a scheduling algorithm, which further demonstrates the effectiveness of these characteristics through simulation experiments.
In this study, we analyze the characteristics of scheduling sequences for Layered belief propagation (LBP) that can result in efficient decoding on Low-density parity-check (LDPC) codes. Specifically, we claim that scheduling sequences leading to high decoding efficiency should prioritize updating check nodes with lower error probabilities aggregated from neighboring variable nodes. We prove this conclusion separately in both BEC and BI-AWGN channels. Some observable characteristics in "good" scheduling sequences regarding row weights, rows connected to punctured columns, and column weights can serve as corollaries to this conclusion. Based on these, we design a dynamic scheduling algorithm, which can further demonstrate the effectiveness of these characteristics through simulation experiments.
In this study, we analyze the characteristics of scheduling sequences for layered belief propagation (LBP) that can result in efficient decoding of low-density parity-check (LDPC) codes. Specifically, we claim that scheduling sequences leading to high decoding efficiency should prioritize updating check nodes with lower error probabilities aggregated from neighboring variable nodes. We prove this conclusion separately on both the BEC and the BI-AWGN channels. Some observable characteristics in “good” scheduling sequences regarding row weights, rows connected to punctured columns, and column weights can serve as corollaries to this conclusion. By comprehensively considering these characteristics of good scheduling, we design a multi-sequence nested scheduling scheme of layered decoding for 5G New Radio (NR) LDPC codes. The proposed schemes can obtain scheduling sequences for various rates of rate-compatible LDPC codes using small hardware storage. What’s more, by respectively storing double-sequence, triple-sequence, or more sequences to obtain scheduling sequences at various code rates, a trade-off can be made between decoder storage and decoding performance. Experimental results demonstrate that the proposed scheme achieves performance improvements compared to existing scheduling schemes at nearly all code rates.
This paper proposes an efficient scheduling algorithm for the layered decoding of block low-density parity-check (LDPC) codes. To efficiently configure check node-based scheduling groups, the proposed algorithm utilizes the base matrix of the block LDPC code for a block-by-block scheduling group configuration; i.e., the proposed algorithm generates a scheduling group of check nodes, satisfying the weight condition of the layered decoding, which is performed in block units (including several check nodes). Therefore, unlike the conventional scheduling algorithms performed in node units, the proposed algorithm can efficiently generate scheduling groups for layered decoding at low computational complexity and memory requirements. In addition, to accelerate the decoding convergence speed, check nodes are allocated in each scheduling group such that messages from check nodes up to the current group are delivered as evenly as possible to bit nodes. Simulation results confirm that the proposed algorithm can accelerate decoding convergence compared to other block-based scheduling algorithms for layered decoding of block LDPC codes.
An efficient decoding schedule for low-density parity-check (LDPC) codes that outperforms the conventional approach, in terms of both complexity and performance, is presented. Conventionally, in each iteration, all symbol nodes and, subsequently, all the check nodes, send messages to their neighbors ("flooding schedule"). In contrast, in the proposed method, the updating of nodes is performed according to a serial schedule which propagates the information twice as fast. A density evolution (DE) algorithm for asymptotic analysis of the new schedule is derived, showing that, when working near the code's capacity, the decoder converges in approximately half the number of iterations. In addition, a concentration theorem is proved, showing that, for a randomly chosen serial schedule, code graph, and decoder input, the decoder's performance approaches its expected one as predicted by the DE algorithm, when the code length increases.
Abstract — Low-Density Parity-Check (LDPC) codes are usually decoded by running an iterative belief-propagation, or message-passing, algorithm over the factor graph of the code. The traditional message-passing schedule 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 raises the problem of finding the best sequence of message updates. This paper presents practical scheduling strategies that use the value of the messages in the graph to find the next message to be updated. Simulation results show that these informed update sequences require significantly fewer iterations than standard sequential schedules. Complexity and implementability issues are also addressed. Index Terms — Belief propagation-algorithm, messagepassing schedule, error-control codes, low-density paritycheck codes. I.
Schedule plays an important role in layered belief propagation (BP) decoding of low-density parity-check (LDPC) codes. It affects the error-rate performance as well as convergence rate of the decoder. In this paper, an efficient scheduling scheme is proposed to arrange the updating order of check nodes for layered BP decoder of regular LDPC codes. This scheme selects check node one at a time based on the reliability of the variable nodes. Specifically each time the check node with maximum number of low-reliability neighbors is selected. For simplicity, we introduce the updating state instead of the real-time messages to represent variable-node reliability. Simulation results on regular LDPC codes prove that the proposed scheduling scheme can obtain efficient schedules with fast convergence and good error-rate performance.