The best known practical algorithm for the decoding of low-density parity-check (LDPC) codes is the iterative sum-product or belief propagation algorithm, operating on a Tanner graph (TG) of the code. Conventionally, in each iteration, all the symbol nodes and subsequently all the check nodes in the TG pass new messages to their neighbors (the so-called "looding schedule"). In this work, we propose a new message-passing schedule, called "probabilistic schedule" Unlike flooding, the probabilistic schedule operates based on the structure of the TG, and probabilistically balances the frequency at which different symbol nodes update their outgoing messages in accordance with their girths. Our results show that, particularly for short block lengths, the new schedule offers a much better performance/complexity trade-off. For a particular example of a (1268,456) code, at no cost in complexity, the probabilistlc schedule not only decreases both the bit and message error rates by an order of magnitude, but also reduces the number of undetected errors considerably. This work shows the importance of scheduling in the performance of iterative decoding algorithms and suggests that a schedule which matches the structure of the TG can substantially improve the performance/complexity trade-off in the decoding of short LD-PC codes.

Additional Metadata
Conference 2001 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (PACRIM 2001)
Citation
Mao, Y. (Y.), & Banihashemi, A. (2001). Decoding low-density parity-check codes with probabilistic schedule. In IEEE Pacific RIM Conference on Communications, Computers, and Signal Processing - Proceedings (pp. 119–123).