A modified Gradient Descent Bit Flipping (GDBF) algorithm is proposed for decoding Low Density Parity Check (LDPC) codes on the binary-input additive white Gaussian noise channel. The new algorithm, called Noisy GDBF (NGDBF), introduces a random perturbation into each symbol metric at each iteration. The noise perturbation allows the algorithm to escape from undesirable local maxima, resulting in improved performance. A combination of heuristic improvements to the algorithm are proposed and evaluated. When the proposed heuristics are applied, NGDBF performs better than any previously reported GDBF variant, and comes within 0.5 dB of the belief propagation algorithm for several tested codes. Unlike other previous GDBF algorithms that provide an escape from local maxima, the proposed algorithm uses only local, fully parallelizable operations and does not require computing a global objective function or a sort over symbol metrics, making it highly efficient in comparison. The proposed NGDBF algorithm requires channel state information which must be obtained from a signal to noise ratio (SNR) estimator. Architectural details are presented for implementing the NGDBF algorithm. Complexity analysis and optimizations are also discussed.
In addition to recent work on low-complexity decoding, there has also been some exploration of noise-perturbed decoding using traditional MS and BP algorithms. demonstrated a beneficial effect of noise perturbations for the BP algorithm, using a method called dithered belief propagation @cite_1 . Kameni examined the effect of noise perturbations on MS decoders and found beneficial effects under certain conditions @cite_26 . The authors of @cite_14 offered the conjecture that noise perturbations assist the MS algorithm in escaping from spurious fixed-point attractors, similar to the hypothesis offered in this paper to motivate the NGDBF algorithm.
@cite_14 @cite_26 @cite_1
1668142578 2160400221 1983749341 2110529479
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. Two-dimensional (2-D) correction schemes are proposed to improve the performance of conventional min-sum (MS) decoding of irregular low density parity check codes. An iterative procedure based on parallel differential optimization is presented to obtain the optimal 2-D factors. Both density evolution analysis and simulation show that the proposed method provides a comparable performance as belief propagation (BP) decoding while requiring less complexity. Interestingly, the new method exhibits a lower error floor than that of BP decoding. With respect to conventional MS and 1-D normalized MS decodings, the 2-D normalized MS offers a better performance. The 2-D offset MS decoding exhibits a similar behavior. Applications of compressed sensing motivate the possibility of using different operators to encode and decode a signal of interest. Since it is clear that the operators cannot be too different, we can view the discrepancy between the two matrices as a perturbation. The stability of l 1 -minimization and greedy algorithms to recover the signal in the presence of additive noise is by now well-known. Recently however, work has been done to analyze these methods with noise in the measurement matrix, which generates a multiplicative noise term. This new framework of generalized perturbations (i.e., both additive and multiplicative noise) extends the prior work on stable signal recovery from incomplete and inaccurate measurements of Candes, Romberg and Tao using Basis Pursuit (BP), and of Needell and Tropp using Compressive Sampling Matching Pursuit (CoSaMP). We show, under reasonable assumptions, that the stability of the reconstructed signal by both BP and CoSaMP is limited by the noise level in the observation. Our analysis extends easily to arbitrary greedy methods. We introduce two dithered belief propagation decoding algorithms to lower the error floor with a minimal hardware overhead. One of the algorithms can additionally improve the decoding performance in the waterfall region using a large iteration limit but with a negligible increase in the average time complexity.