LDPC Decoding by Parity Augmentation and Maximization

Two iterative decoding algorithms, which are alternatives to belief propagation (BP) decoding LDPC codes, are introduced in this paper. In parity augmentation (PA) decoding, probabilities are modifled in such a way that the probability of even parity is increased at every iteration. This is a low-complexity algorithm which does not require both row and column interleavers. We also examine the nature of the probability of even computation (which is also done in BP), providing evidence about the breakdown in decoding as the weight of the parity check matrix increases besides explanations related to short cycles in the Tanner graph. In parity maximization (PM) decoding, the probability of even parity is explicitly maximized at every iteration. Again there is low per-iteration complexity.