Improving convergence of Belief Propagation decoding
<|reference_start|>Improving convergence of Belief Propagation decoding: The decoding of Low-Density Parity-Check codes by the Belief Propagation (BP) algorithm is revisited. We check the iterative algorithm for its convergence to a codeword (termination), we run Monte Carlo simulations to find the probability distribution function of the termination time, n_it. Tested on an example [155, 64, 20] code, this termination curve shows a maximum and an extended algebraic tail at the highest values of n_it. Aiming to reduce the tail of the termination curve we consider a family of iterative algorithms modifying the standard BP by means of a simple relaxation. The relaxation parameter controls the convergence of the modified BP algorithm to a minimum of the Bethe free energy. The improvement is experimentally demonstrated for Additive-White-Gaussian-Noise channel in some range of the signal-to-noise ratios. We also discuss the trade-off between the relaxation parameter of the improved iterative scheme and the number of iterations.<|reference_end|>
@article{stepanov2006improving,
    title={Improving convergence of Belief Propagation decoding},
    author={M.G. Stepanov, M. Chertkov},
    journal={arXiv preprint arXiv:cs/0607112},
    year={2006},
    number={LA-UR-06-5058},
    archivePrefix={arXiv},
    eprint={cs/0607112},
    primaryClass={cs.IT math.IT}
}