© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

International Symposium on Turbo Codes and Iterative Information Processing

Noise-aided gradient descent bit-flipping decoders approaching maximum likelihood decoding

David Declercq, Chris Winstead, Bane V. Vasic, Fakhreddine Ghaffari, Predrag Ivaniš, Emmanuel Boutillon

Published Sep 1, 2016• 10 citations

Abstract

In the recent literature, the study of iterative LDPC decoders implemented on faulty-hardware has led to the counter-intuitive conclusion that noisy decoders could perform better than their noiseless version. This peculiar behavior has been observed in the finite codeword length regime, where the noise perturbating the decoder dynamics help to escape the attraction of fixed points such as trapping sets. In this paper, we will study two recently introduced LDPC decoders derived from noisy versions of the gradient descent bit-flipping decoder (GDBF). Although the GDBF is known to be a simple decoder with limited error correction capability compared to more powerful softdecision decoders, it has been shown that the introduction of a random perturbation in the decoder could greatly improve the performance results, approaching and even surpassing belief propagation or min-sum based decoders. For both decoders, we evaluate the probability of escaping from a Trapping set, and relate this probability to the parameters of the injected noise distribution, using a Markovian model of the decoder transitions in the state space of errors localized on isolated trapping sets. In a second part of the paper, we present a modified scheduling of our algorithms for the binary symmetric channel, which allows to approach maximum likelihood decoding (MLD) at the cost of a very large number of iterations.

DOI: 10.1109/istc.2016.7593125

Related papers

Noisy Gradient Descent Bit-Flip Decoding for LDPC Codes

Gopalakrishnan Sundararajan, Chris Winstead, Emmanuel Boutillon

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.

arXiv:1402.2773•IEEE Transactions on Communications•Sep 9, 2014•108 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

A modified gradient descent bit flipping decoding scheme for LDPC codes

Mao-Ruei Li, Li-Min Jhuang, Yeong-Luh Ueng

It is known that the Gradient descent bit flipping (GDBF) algorithm is an effective hard-decision decoding algorithm for low-density parity-check (LDPC) codes. However, trapping in a local maximum limits its error-rate performance. This paper presents a modified GDBF scheme that can mitigate the trapping problem and hence can improve the error-rate performance. Compared to the conventional GDBF algorithm, the proposed method is able to improve the decoding performance of 0.3dB for an (18582, 16626) code. The (18582, 16626) LDPC decoder integrates 636k logic gates and achieves a throughput of 12.4 Gbps at a clock frequency of 200 MHz in a 90nm process.

SiPS ... design and implementation - IEEE Workshop on Signal Processing Systems•Oct 1, 2017•4 citations

An escaping scheme for gradient descent bit-flipping decoding of LDPC codes

Hua Li, Hong Wei Ding, Linhua Zheng

The gradient descent bit-flipping (GDBF) decoding algorithm offers an attractive tradeoff between performance and complexity compared with the other bit-flipping (BF) decoding algorithms. However, the performance of GDBF decoding is seriously effected by infinite decoding loop, which always results in decoding failure when maximal iteration number is reached. To avoid the decoding loop and improve the performance, an efficient escaping scheme is proposed for the GDBF algorithm in this paper. This scheme firstly introduces syndrome weight to detect the decoding loop. If a decoding loop is detected, the escaping mechanism works, where only the bit which can decrease the syndrome weight most efficiently is selected to be flipped. In addition, the excluding set is introduced to further prevent the local maximum. Simulation results show that the GDBF algorithm can obtain about 1 dB code gain by utilizing this scheme. Compared with noise GDBF, it has 0.1dB performance loss as well as lower complexity.

International Congress on Image and Signal Processing (CISP)•Oct 1, 2016•2 citations

Sign Aided Adaptive Noisy Gradient Descent Bit-Flipping Algorithm for LDPC Codes

Keyue Deng, Yuxing Chen, Suwen Song +1 more

The adjustment factor aided noisy gradient descent bit-flipping (ANGDBF) offers a significant improvement in error correction capability compared with other gradient descent bit-flipping (GDBF) variants. However, there still exists a considerable performance gap between the ANGDBF algorithm and the belief propagation (BP) algorithm. This paper presents a sign aided adaptive noisy GDBF (SANGDBF) algorithm, in which the mean of noise perturbation shows an adaptive property, facilitating the decoding process to escape from the local maxima more effectively. Moreover, the sign of the correlation term is fully utilized to improve the reliability of the inversion function. Simulation results show that the SANGDBF algorithm can achieve about 0.5 dB coding gain compared with the ANGDBF algorithm with limited hardware overhead.

IEEE International Conference on Computer and Communications (ICCC)•Dec 9, 2022•2 citations

In the recent literature, the study of iterative LDPC decoders implemented on faulty-hardware has led to the counter-intuitive conclusion that noisy decoders could perform better than their noiseless version. This peculiar behavior has been observed in the finite codeword length regime, where the noise perturbating the decoder dynamics help to escape the attraction of fixed points such as trapping sets. In this paper, we will study two recently introduced LDPC decoders derived from noisy versions of the gradient descent bit-flipping decoder (GDBF). Although the GDBF is known to be a simple decoder with limited error correction capability compared to more powerful softdecision decoders, it has been shown that the introduction of a random perturbation in the decoder could greatly improve the performance results, approaching and even surpassing belief propagation or min-sum based decoders. For both decoders, we evaluate the probability of escaping from a Trapping set, and relate this probability to the parameters of the injected noise distribution, using a Markovian model of the decoder transitions in the state space of errors localized on isolated trapping sets. In a second part of the paper, we present a modified scheduling of our algorithms for the binary symmetric channel, which allows to approach maximum likelihood decoding (MLD) at the cost of a very large number of iterations.

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.

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.

It is known that the Gradient descent bit flipping (GDBF) algorithm is an effective hard-decision decoding algorithm for low-density parity-check (LDPC) codes. However, trapping in a local maximum limits its error-rate performance. This paper presents a modified GDBF scheme that can mitigate the trapping problem and hence can improve the error-rate performance. Compared to the conventional GDBF algorithm, the proposed method is able to improve the decoding performance of 0.3dB for an (18582, 16626) code. The (18582, 16626) LDPC decoder integrates 636k logic gates and achieves a throughput of 12.4 Gbps at a clock frequency of 200 MHz in a 90nm process.

The gradient descent bit-flipping (GDBF) decoding algorithm offers an attractive tradeoff between performance and complexity compared with the other bit-flipping (BF) decoding algorithms. However, the performance of GDBF decoding is seriously effected by infinite decoding loop, which always results in decoding failure when maximal iteration number is reached. To avoid the decoding loop and improve the performance, an efficient escaping scheme is proposed for the GDBF algorithm in this paper. This scheme firstly introduces syndrome weight to detect the decoding loop. If a decoding loop is detected, the escaping mechanism works, where only the bit which can decrease the syndrome weight most efficiently is selected to be flipped. In addition, the excluding set is introduced to further prevent the local maximum. Simulation results show that the GDBF algorithm can obtain about 1 dB code gain by utilizing this scheme. Compared with noise GDBF, it has 0.1dB performance loss as well as lower complexity.

The adjustment factor aided noisy gradient descent bit-flipping (ANGDBF) offers a significant improvement in error correction capability compared with other gradient descent bit-flipping (GDBF) variants. However, there still exists a considerable performance gap between the ANGDBF algorithm and the belief propagation (BP) algorithm. This paper presents a sign aided adaptive noisy GDBF (SANGDBF) algorithm, in which the mean of noise perturbation shows an adaptive property, facilitating the decoding process to escape from the local maxima more effectively. Moreover, the sign of the correlation term is fully utilized to improve the reliability of the inversion function. Simulation results show that the SANGDBF algorithm can achieve about 0.5 dB coding gain compared with the ANGDBF algorithm with limited hardware overhead.