© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:1402.2773 · IEEE Transactions on Communications

Noisy Gradient Descent Bit-Flip Decoding for LDPC Codes

Gopalakrishnan Sundararajan, Chris Winstead, Emmanuel Boutillon

Published Sep 9, 2014• 108 citations

Abstract

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.

DOI: 10.1109/tcomm.2014.2356458

Related papers

Tabu-List Noisy Gradient Descent Bit Flipping Decoding of LDPC Codes

Li Guo Zhang, Nan Liu, Zhiwen Pan +1 more

The Noisy Gradient Descent Bit Flipping (NGDBF) algorithm surpasses the previous Gradient Descent Bit Flipping (GDBF) and other Bit Flipping (BF) algorithms for decoding Low-Density Parity-Check (LDPC) codes. However, the NGDBF decoder sometimes cannot escape from the local maxima. To further enhance the performance of the NGDBF algorithm, an improved NGDBF algorithm called Tabu-List Noisy Gradient Descent Bit Flipping (TNGDBF) is proposed in this paper. A tabu-list is employed to help the NGDBF decoder escape from the local maxima. It is shown in the simulation results that the TNGDBF algorithm gains about 0.2 dB performance compared with NGDBF at the cost of a small amount of complexity increase.

International Conference on Wireless Communications and Signal Processing (WCSP)•Oct 1, 2019•2 citations

Improved noisy gradient descent bit-flipping algorithm over Rayleigh fading channel

Reza Biazaran, Hermann J. Helgert

Gradient descent bit flipping (GDBF) and its many variants have offered remarkable improvements over legacy, or modified, bit flipping decoding techniques in case of decoding low density parity check (LDPC) codes. GDBF method and its many variants, such as noisy gradient descent bit flipping (NGDBF) have been extensively studied and their performances have been assessed over multiple channels such as binary symmetric channel (BSC), binary erasure channel (BEC) and additive white Gaussian noise (AWGN) channel. However, performance of the said decoders in more realistic channels or channel conditions have not been equally studied. An improved noisy gradient descent bit flipping algorithm is proposed in this paper that optimally decodes LDPC encoded codewords over Rayleigh fading channel and under various fade rates. Comparing to NGDBF method, our proposed decoder provides substantial improvements in both error performance of the code, and in the number of iterations required to achieve the said error performance. It subsequently reduces the end-to-end latency in applications with low or ultra-low latency requirements.

International Journal of Power Electronics and Drive Systems/International Journal of Electrical and Computer Engineering•Mar 14, 2022•3 citations

An improved noisy gradient descent bit-flipping decoding algorithm for LDPC codes

Jun Asatani, Yuya Kondo, Kengo Katayama +2 more

Gradient descent bit-flipping (GDBF) algorithm achieves good error performance for decoding low density parity check codes. In the GDBF algorithm, a search point is apt to be trapped in a local optimum, which causes performance degradation of the GDBF algorithm. To overcome this issue, the noisy GDBF algorithm introduces random perturbation into the inversion function of each symbol, which decreases the probability of being trapped in a local optimum. In this paper, we develop the noisy GDBF algorithm by enhancing the threshold adaptation in multi-bit flipping procedure to improve the BER performance without increasing the time complexity.

International Symposium on Information Theory and its Applications•Oct 1, 2016•2 citations

Efficient Noisy Gradient Descent Bit-Flipping Algorithm for Decoding LDPC Codes

Kaiyang Peng, Jie Peng, Haiyang Liu

In this paper, we propose an efficient noisy gradient descent bit-flipping (NGDBF) algorithm for decoding LDPC codes. The proposed algorithm introduces random noise with uniform distribution on the interval$[-1,1]$into the inversion function of the GDBF algorithm. The proposed algorithm avoids the complicated operations in the noise generation of the conventional NGDBF algorithm. In addition, our proposed decoding algorithm does not rely on the SNR estimation and the scaling factor. Simulation results indicate that the proposed algorithm can achieve almost the same performance as the conventional NGDBF algorithm. Moreover, even the using of a linear feedback shift register with very small stage can generate sufficient randomness to reach such performance.

IEEE International Conference on Computer and Communications (ICCC)•Dec 12, 2025•0 citations

Gradient-Descent Bit-Flipping Decoding Based on Tabu Search for LDPC Codes

良介高橋, 祐一高野

This paper is concerned with bit-flipping algorithms for decoding low-density parity check codes. The gradient-descent bit flipping (GDBF) is known as a high-performance class of bitflipping algorithms; however, once GDBF becomes trapped at local optimal solutions, it cannot escape from them. Several algorithms, including noisy gradient-descent bit flipping (NGDBF), have been devised to overcome this drawback. For the same purpose, we develop a bit-flipping algorithm based on the tabu search, which is one of the most effective metaheuristics. The simulation results demonstrate that our algorithm achieved higher bit error rate performance than GDBF did. Moreover, our algorithm required a smaller number of iterations to find a good-quality solution than NGDBF did.

•Mar 1, 2019•0 citations

Modified Noisy Gradient Descent Bit-Flipping Decoding Algorithms for LDPC Codes

Yidong Li, Wai M. Tam, Francis C. M. Lau

In this paper, we propose modified multi-bit noisy gradient descent bit flipping (M-NGDBF) algorithms for decoding low-density parity-check codes. To simplify the decoder design, we eliminate the use of Gaussian noise generators at the decoder and replace them with received signals after simple transformations. We then improve the convergence rate by removing the randomness in the M-NGDBF algorithm during the first few iterations. Subsequently, we construct a tabu-list to record bits that are flipped in the current iteration and allows these bits to be flipped in the next iteration only with a very small probability. Simulation results show that our proposed algorithms outperform the original M-NGDBF algorithm in terms of both bit error rate and convergence rate.

International Conference on Advanced Technologies for Communications•Oct 20, 2022•4 citations

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.

The Noisy Gradient Descent Bit Flipping (NGDBF) algorithm surpasses the previous Gradient Descent Bit Flipping (GDBF) and other Bit Flipping (BF) algorithms for decoding Low-Density Parity-Check (LDPC) codes. However, the NGDBF decoder sometimes cannot escape from the local maxima. To further enhance the performance of the NGDBF algorithm, an improved NGDBF algorithm called Tabu-List Noisy Gradient Descent Bit Flipping (TNGDBF) is proposed in this paper. A tabu-list is employed to help the NGDBF decoder escape from the local maxima. It is shown in the simulation results that the TNGDBF algorithm gains about 0.2 dB performance compared with NGDBF at the cost of a small amount of complexity increase.

Gradient descent bit flipping (GDBF) and its many variants have offered remarkable improvements over legacy, or modified, bit flipping decoding techniques in case of decoding low density parity check (LDPC) codes. GDBF method and its many variants, such as noisy gradient descent bit flipping (NGDBF) have been extensively studied and their performances have been assessed over multiple channels such as binary symmetric channel (BSC), binary erasure channel (BEC) and additive white Gaussian noise (AWGN) channel. However, performance of the said decoders in more realistic channels or channel conditions have not been equally studied. An improved noisy gradient descent bit flipping algorithm is proposed in this paper that optimally decodes LDPC encoded codewords over Rayleigh fading channel and under various fade rates. Comparing to NGDBF method, our proposed decoder provides substantial improvements in both error performance of the code, and in the number of iterations required to achieve the said error performance. It subsequently reduces the end-to-end latency in applications with low or ultra-low latency requirements.

Gradient descent bit-flipping (GDBF) algorithm achieves good error performance for decoding low density parity check codes. In the GDBF algorithm, a search point is apt to be trapped in a local optimum, which causes performance degradation of the GDBF algorithm. To overcome this issue, the noisy GDBF algorithm introduces random perturbation into the inversion function of each symbol, which decreases the probability of being trapped in a local optimum. In this paper, we develop the noisy GDBF algorithm by enhancing the threshold adaptation in multi-bit flipping procedure to improve the BER performance without increasing the time complexity.

In this paper, we propose an efficient noisy gradient descent bit-flipping (NGDBF) algorithm for decoding LDPC codes. The proposed algorithm introduces random noise with uniform distribution on the interval

[-1,1]

into the inversion function of the GDBF algorithm. The proposed algorithm avoids the complicated operations in the noise generation of the conventional NGDBF algorithm. In addition, our proposed decoding algorithm does not rely on the SNR estimation and the scaling factor. Simulation results indicate that the proposed algorithm can achieve almost the same performance as the conventional NGDBF algorithm. Moreover, even the using of a linear feedback shift register with very small stage can generate sufficient randomness to reach such performance.

This paper is concerned with bit-flipping algorithms for decoding low-density parity check codes. The gradient-descent bit flipping (GDBF) is known as a high-performance class of bitflipping algorithms; however, once GDBF becomes trapped at local optimal solutions, it cannot escape from them. Several algorithms, including noisy gradient-descent bit flipping (NGDBF), have been devised to overcome this drawback. For the same purpose, we develop a bit-flipping algorithm based on the tabu search, which is one of the most effective metaheuristics. The simulation results demonstrate that our algorithm achieved higher bit error rate performance than GDBF did. Moreover, our algorithm required a smaller number of iterations to find a good-quality solution than NGDBF did.

In this paper, we propose modified multi-bit noisy gradient descent bit flipping (M-NGDBF) algorithms for decoding low-density parity-check codes. To simplify the decoder design, we eliminate the use of Gaussian noise generators at the decoder and replace them with received signals after simple transformations. We then improve the convergence rate by removing the randomness in the M-NGDBF algorithm during the first few iterations. Subsequently, we construct a tabu-list to record bits that are flipped in the current iteration and allows these bits to be flipped in the next iteration only with a very small probability. Simulation results show that our proposed algorithms outperform the original M-NGDBF algorithm in terms of both bit error rate and convergence rate.