An efficient message-passing schedule for LDPC decoding

An efficient decoding schedule for low-density parity-check (LDPC) codes that outperforms the conventional approach both in terms of 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.