Serial decoding schedules for low-density parity-check (LDPC) codes are described and analyzed. Conventionally, in each iteration all the variable nodes and subsequently all the check nodes send messages to their neighbors (“flooding schedule”). In contrast, in the considered methods, the updating of the nodes is implemented according to a serial schedule. The evolution of the decoding algorithm’s computation tree under serial scheduling is analyzed. The analysis shows that it grows twice as fast in comparison to the flooding schedule’s computation tree, indicating that the serial schedule propagates information twice as fast in the code’s underlying graph. Furthermore, asymptotic analysis of the serial schedule’s convergence rate is done using the Density Evolution (DE) algorithm. Applied to various ensembles of LDPC codes, it shows that when working near the ensemble’s threshold, for long enough codes the serial schedule is expected to converge in half the number of iterations compared to the standard flooding schedule. This observation is generally proved for the Binary Erasure Channel (BEC) under some likely assumptions. Finally, an accompanying concentration theorem is proved, justifying the asymptotic DE analysis assumptions. 1
Serial decoding schedules for low-density parity-check (LDPC) codes are described and analyzed. Conventionally, in each iteration all the variable nodes and subsequently all the check nodes send messages to their neighbors (“flooding schedule”). In contrast, in the considered methods, the updating of the nodes is implemented according to a serial schedule. The evolution of the decoding algorithm’s computation tree under serial scheduling is analyzed. The analysis shows that it grows twice as fast in comparison to the flooding schedule’s computation tree, indicating that the serial schedule propagates information twice as fast in the code’s underlying graph. Furthermore, asymptotic analysis of the serial schedule’s convergence rate is done using the Density Evolution (DE) algorithm. Applied to various ensembles of LDPC codes, it shows that when working near the ensemble’s threshold, for long enough codes the serial schedule is expected to converge in half the number of iterations compared to the standard flooding schedule. This observation is generally proved for the Binary Erasure Channel (BEC) under some likely assumptions. Finally, an accompanying concentration theorem is proved, justifying the asymptotic DE analysis assumptions. 1
Conventionally, in each low-density parity-check (LDPC) decoding iteration all the variable nodes and subsequently all the check nodes send messages to their neighbors (flooding schedule). An alternative, more efficient, approach is to update the nodes' messages serially (serial schedule). A theoretical analysis of serial message passing decoding schedules is presented. In particular, the evolution of the computation tree under serial scheduling is analyzed. It shows that the tree grows twice as fast in comparison to the flooding schedule's one, indicating that the serial schedule propagates information twice as fast in the code's underlying graph. Furthermore, an asymptotic analysis of the serial schedule's convergence rate is done using the density evolution (DE) algorithm. Applied to various ensembles of LDPC codes, it shows that for long codes the serial schedule is expected to converge in half the number of iterations compared to the standard flooding schedule, when working near the ensemble's threshold. This observation is generally proved for the binary erasure channel (BEC) under some natural assumptions. Finally, an accompanying concentration theorem is proved.
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.
Low-density parity-check (LDPC) codes are usually decoded by running an iterative belief-propagation algorithm over the factor graph of the code. In the traditional message-passing schedule, in each iteration all the variable nodes, and subsequently all the factor nodes, pass new messages to their neighbors. Recently several studies show that serial scheduling, in which messages are generated using the latest available information, significantly improves the convergence speed in terms of number of iterations. It was observed experimentally in several studies that the serial schedule converges in exactly half the number of iterations compared to the standard parallel schedule. In this correspondence we provide a theoretical motivation for this observation by proving it for single-path graphs.
Tanner graph of LDPC and flooding decoding algorithm are briefly introduced.On this condition,present serial decoding algorithm and semi-serial decoding algorithm which based on check nodes.By analysing DE(Density Evolution) and tree depth of message convergence,it's proved that the message convergence speed grows about twice as fast in the serial decoding algorithm compared to the flooding decoding algorithm,and reduce the decoding complexity.Respectively apply flooding decoding algorithm and serial decoding algorithm to simulate over AWGN channel.Theory and results of simulation show that the decoding performance could be improved by serial decoding algorithm.
Schedule is the order of passing messages between vertices of the bipartite graph defining an LDPC code in the process of decoding. Schedules affect the rate of decoding convergence. New efficient generalized serial schedules are described and analyzed, exhibiting significantly faster convergence compared to previously known schedules. For the proposed schedules, combinatorial and probabilistic analysis is presented, explaining the fast convergence observed in simulations. Using it, LDPC ensembles for which significantly better convergence rates can be achieved are identified. Specific code constructions from lifted graphs are further proposed, efficiently supporting the schedules. Examples based on regular LDPC codes are provided, in which the schedules achieve convergence speedup factors of up to 6 in comparison with the flooding schedule. Higher speedup factors are predicted by the analysis for irregular codes.
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.