TY - GEN
T1 - Improving convergence of belief propagation decoding
AU - Stepanov, M. G.
AU - Chertkov, M.
PY - 2006
Y1 - 2006
N2 - The decoding of Low-Density Parity-Check codes by the Belief Propagation (BP) algorithm is revisited. To check the iterative algorithm for its convergence to a codeword (termination), we run Monte Carlo simulations and find the probability distribution function of the termination time, nit. Tested on the [155, 64, 20] code, this termination curve shows a maximum and an extended algebraic tail at the highest values of nit. 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.
AB - The decoding of Low-Density Parity-Check codes by the Belief Propagation (BP) algorithm is revisited. To check the iterative algorithm for its convergence to a codeword (termination), we run Monte Carlo simulations and find the probability distribution function of the termination time, nit. Tested on the [155, 64, 20] code, this termination curve shows a maximum and an extended algebraic tail at the highest values of nit. 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.
UR - http://www.scopus.com/inward/record.url?scp=84940638942&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84940638942&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84940638942
T3 - 44th Annual Allerton Conference on Communication, Control, and Computing 2006
SP - 947
EP - 951
BT - 44th Annual Allerton Conference on Communication, Control, and Computing 2006
PB - University of Illinois at Urbana-Champaign, Coordinated Science Laboratory and Department of Computer and Electrical Engineering
T2 - 44th Annual Allerton Conference on Communication, Control, and Computing 2006
Y2 - 27 September 2006 through 29 September 2006
ER -