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.
Several researchers proposed alternative GDBF algorithms in order to obtain fully parallel bit-flipping and improved performance. proposed an Adaptive Threshold GDBF (AT-GDBF) algorithm that achieves good performance without the use of mode-switching, allowing for fully-parallel operation @cite_23 . The same authors also introduced an early-stopping condition (ES-AT-GDBF) that significantly reduces the average decoding iterations at lower Signal to Noise Ratio (SNR). Phromsa- proposed a more complex Reliability-Ratio Weighted GDBF algorithm (RRWGDBF) that uses a weighted summation over syndrome components with an adaptive threshold to obtain reduced latency @cite_25 . The RRWGDBF method has the drawback of increased arithmetic complexity because it performs a summation of weighted syndrome components, similar to previous WBF algorithms. proposed an improved multi-bit GDBF algorithm (IGDBF) that performs very close to the H-GDBF algorithm, but requires a global sort operation to determine which bits to flip @cite_11 .
@cite_25 @cite_23 @cite_11
1493432783 2150266863 2061867767 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. For LDPC decoding, a class of weighted bit-flipping algorithms is much simpler than a belief propagation algorithm. This work proposes a modified Gradient Descent Bit-Flipping algorithm based on Reliability Ratio with an adaptive threshold to address trade-off between performance and latency. From numerical results, the proposed algorithm achieves lower latency without an expense of performance. It yields average iteration reduction of 15–27 over SNR range from 2.5 dB to 4.5 dB. In addition, it provides better decoding performance gains, i.e. 0.05–0.25 dB over low-to-medium SNR range between 1.5 dB and 4 dB comparing to previous schemes. 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.