Abstract-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, nit. Tested on an example [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-GaussianNoise 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. Low-Density Parity-Check (LDPC) codes [1], [2] are the best linear block error-correction codes known today [3] . In addition to being good codes, i.e. capable of decoding without errors in the thermodynamic limit of an infinitely long block length, these codes can also be decoded efficiently. The main idea of Belief Propagation (BP) decoding is in approximating the actual graphical model, formulated for solving statistical inference Maximum Likelihood (ML) or Maximum-A-Posteriori (MAP) problems, by a tree-like structure without loops. Being efficient but suboptimal the BP algorithm fails on certain configurations of the channel noise when close to optimal (but inefficient) MAP decoding would be successful. BP decoding allows a certain duality in interpretation. First of all, and following the so-called Bethe-free energy variational approach [4] , BP can be understood as a set of equations for beliefs (BP-equations) solving a constrained minimization problem. On the other hand, a more traditional approach is to interpret BP in terms of an iterative procedure -so-called BP iterative algorithm [1], [5], [2] . Being identical on a tree (as then BP equations are solved explicitly by iterations from leaves to the tree center) the two approaches are however distinct for a graphical problem with loops. In case of their convergence, BP algorithms find a minimum of the Bethe free energy [4], [6], [7] , however in a general case convergence of the standard iterative BP is not guaranteed. It is also understood that BP fails to converge primarily due to circling of messages in the process of iterations over the To enforce convergence of the iterative algorithm to a minimum of the Bethe Free energy some number of modifications of the standard iterative BP were discussed in recent years. The tree-based re-parametrization framework of [8] suggests to limit communication on the loopy graph, cutting some edges in a dynamical fashion so that the undesirable effects of circles are suppressed. Another, so-called concaveconvex procedure, introduced in [9] and generalized in [10] , suggests to decompose the Bethe free energy into concave and convex parts thus splitting the iterations into two sequential sub-steps. Noticing that convergence of the standard BP fails mainly due to overshooting of iterations, we develop in this paper a tunable relaxation (damping) that cures the problem. Compared with the aforementioned alternative methods, this approach can be practically more advantageous due to its simplicity and tunability. In its simplest form our modification of the BP iterative procedure is given by where Latin and Greek indexes stand for bits and checks and the bit/check relations, e.g. i ∈ α, α ∋ i express the LDPC code considered; h i is the channel noise-dependent value of log-likelihoods; and η (n) iα is the message associated at the nth iteration with the edge (of the respective Tanner graph) connecting i-th bit and α-th check. ∆ is a tunable parameter. By choosing a sufficiently small ∆ one can guarantee convergence of the iterative procedure to a minimum of the Bethe free energy. On the other hand ∆ = +∞ corresponds exactly to the standard iterative BP. In the sequel we derive and explain the modified iterative procedure (1) in detail. The manuscript is organized as follows. We introduce the Bethe free energy, the BP equation and the standard iterative BP in Section I. Performance of standard iterative BP, analyzed with a termination curve, is discussed in Section II. Section III describes continuous and sequentially discrete (iterative) versions of our relaxation method. We discuss performance of the modified iterative scheme in Section IV, where Bit-Error-Rate and the termination curve for an LDPC code performed over Additive-White-Gaussian-Noise (AWGN) channel are discussed for a range of interesting values of the Signal-to-Noise-Ratios (SNR). We also discuss here the trade-off between convergence and number of it-
In REF , the BP algorithm is well studied in the point of view of the Bethe energy and how it fails in the presence of cycles.
Improving convergence of Belief Propagation decoding
ArXiv
ArXiv
Computer Science Mathematics