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.
To reduce the arithmetic complexity of bit-flipping algorithms, devised the GDBF algorithm as a gradient-descent optimization model for the ML decoding problem @cite_5 . Based on this model, the authors of @cite_5 obtained single-bit and multi-bit flipping algorithms that require mainly binary operations, similar to the original BFA. The GDBF methods require summation of binary parity-check values, which is less complex than the WBF algorithms that require summation over independently weighted syndrome values. The single-bit version of the GDBF algorithm (S-GDBF) requires a global search to discover the least reliable bit at each iteration. The multi-bit GDBF algorithm (M-GDBF) uses local threshold operations instead of a global search, hence achieving a faster initial convergence. In practice, the M-GDBF algorithm did not always provide stable convergence to the final solution. To improve convergence, the authors of @cite_5 adopted a mode-switching strategy in which M-GDBF decoding is always followed by a phase of S-GDBF decoding, leveraging high-speed in the first phase and accurate convergence in the second.
@cite_5
1493432783 2150266863 2123025473 2106664865
Gradient Descent Bit Flipping (GDBF) decoding has one of the best decoding performances of the bit flip type decoding algorithms for low density parity check code. Multi-bit type GDBF decoding, however, achieves good error performance only with suitable thresholds. In this paper, we propose multi-bit type GDBF decoding without using thresholds. The proposed method estimates the number of bits to flip from the received soft sequence using the characteristic of the probability density distribution of the additive white Gaussian noise channel. The error performance of the proposed method is almost equal to that of the conventional method despite not using thresholds. A novel class of bit-flipping (BF) algorithm for decoding low-density parity-check (LDPC) codes is presented. The proposed algorithms, which are referred to as gradient descent bit flipping (GDBF) algorithms, can be regarded as simplified gradient descent algorithms. The proposed algorithms exhibit better decoding performance than known BF algorithms, such as the weighted BF algorithm or the modified weighted BF algorithm for several LDPC codes. 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. In this correspondence, a new method for improving hard-decision bit-flipping decoding of low-density parity-check (LDPC) codes is presented. Bits with a number of unsatisfied check sums larger than a predetermined threshold are flipped with a probability p spl les 1 which is independent of the code considered. The probability p is incremented during decoding according to some rule. With a proper choice of the initial p, the proposed improved bit-flipping (BF) algorithm achieves gain not only in performance, but also in average decoding time for signal-to-noise ratio (SNR) values of interest with respect to p = 1.