Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

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

良介 高橋, 祐一 高野

Published Mar 1, 2019• 0 citations
Publisher

Abstract

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.

DOI
10.34360/00007893

Related papers

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

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

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

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

Hybrid iterative decoding for LDPC codes based on gradient descent bit-flipping algorithm

Hua Li, Hong Wei Ding, Linhua Zheng

Gradient descent bit-flipping (GDBF) decoding for low-density parity-check (LDPC) codes has gained great attentions because of low complexity and relatively good performance. However, the performance of the GDBF decoding is still much poorer than that of the MS algorithm. To further improve the performance, the iterative decoding process is introduced to GDBF decoding in this paper. At the end of each iteration, the latest information is used to update the reliability of the flipped bit, by which its reliability is greatly improved. Simulation results indicate that the proposed algorithm has about 0.4 dB performance gains compared to GDBF. Meanwhile, there is small computational complexity increased.

International Conference on Wireless Communications and Signal Processing (WCSP)•Oct 1, 2016•0 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
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.
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.
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.
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.
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) decoding for low-density parity-check (LDPC) codes has gained great attentions because of low complexity and relatively good performance. However, the performance of the GDBF decoding is still much poorer than that of the MS algorithm. To further improve the performance, the iterative decoding process is introduced to GDBF decoding in this paper. At the end of each iteration, the latest information is used to update the reliability of the flipped bit, by which its reliability is greatly improved. Simulation results indicate that the proposed algorithm has about 0.4 dB performance gains compared to GDBF. Meanwhile, there is small computational complexity increased.
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.