Serial Scheduling Algorithm of LDPC Decoding

Ming Zhao, Bin Xu

Liao Wei

Mingshan Liu, Shanshan Liu, Yuan Zhou +1 more

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.

Lei Jing, Caac Scientific

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.

Amrit Pal Singh, Sanjay Sharma

Eran Sharon, Simon N. Litsyn, Jacob Goldberger

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