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.
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.
LDPC and sum product decoding algorithm based on flooding schedule which invented by Gallager are briefly introduced.On this condition,present a serial schedule for LDPC decoding.Such serial decoding algorithm processes and passes messages according to some order of check nodes or variable nodes,assuring the updated messages could join iterative process immediately,therefore improve convergence property,and utilize the relationship between messages,improve message passing process,it can reduce required memory.Analyses the complexity of both algorithms,verifies the serial algorithm which based on check nodes could reduces decoding complexity greatly,and simulates over AWGN channel.Results of simulation show that the decoding performance could be improved by serial algorithm.
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
Message-passing mechanism is an important factor affecting the performance of LDPC decoding. In this paper, we introduce briefly LDPC and sum product decoding algorithm based on floodwater message-passing mechanism proposed by Gallager. On this basis, we introduce a serial mechanism based on check nodes and propose a concrete and feasible decoding algorithm modeling. This serial decoding algorithm processes and passes the messages in a definite sequence of check nodes for ensuring that the updated messages can immediately enter the iterative process so as to improve convergence characteristics of the message passing, and use the feature of interdependence between messages to fuse the message passing steps to reduce required memory and decoding complexity. We use respectively the floodwater decoding algorithm and serial decoding algorithm to perform the performance simulation over AWGN channel. The simulation results show that the decoding performance could be improved by serial decoding algorithm.
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.
The conventional message-passing schedule for LDPC decoding algorithms is the so-called flooding schedule. It has the disadvantage that the updated messages cannot be used until next iteration, thus reducing the convergence speed . In this case, the Layered Decoding algorithm (LBP) based on serial message-passing schedule is proposed. In this paper the decoding principle of LBP algorithm is briefly introduced, and then proposed its two improved algorithms, the grouped serial decoding algorithm (Grouped LBP) and the semi-serial decoding algorithm .They can improve LBP algorithm's decoding speed while maintaining a good decoding performance.
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.