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.
Recently, introduced a Parallel WBF (PWBF) algorithm, which reduces the drawbacks associated with single-bit flipping in the other WBF varieties @cite_10 . In the PWBF algorithm, the maximum (or minimum) @math metric is found within the subset of symbols associated with each parity-check. The authors of @cite_10 also developed a theory relating PWBF to the BP and MS algorithms, and showed that PWBF has performance comparable to IMWBF @cite_6 . In the PWBF algorithm, it is still necessary to find the maximum @math from a set of values, which costs delay, but the set size is significantly reduced compared to the other WBF methods, and it is independent of codeword length. In spite of these improvements, PWBF retains the complex arithmetic associated with IMWBF.
@cite_10 @cite_6
2165439096 2123025473
A parallel weighted bit-flipping (PWBF) decoding algorithm for low-density parity-check (LDPC) codes is proposed. Compared to the best known serial weighted bit-flipping decoding, the PWBF decoding converges significantly faster but with little performance penalty. For decoding of finite-geometry LDPC codes, we demonstrate through examples that the proposed PWBF decoding converges in about 5 iterations with performance very close to that of the standard belief-propagation decoding. A natural relationship between weighted bit-flipping (WBF) decoding and belief-propagation-like (BP-like) decoding is explored. This understanding can help us develop WBF algorithms from BP-like algorithms. For min-sum decoding, one can find that its WBF algorithm is the algorithm proposed by For BP decoding, we propose a new WBF algorithm and show its performance advantage. The proposed WBF algorithms are parallelized to achieve rapid convergence. Two efficient simulation-based procedures are proposed for the optimization of the associated thresholds.