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

IEEE Transactions on Circuits and Systems I Regular Papers

An Improved Gradient Descent Bit-Flipping Decoder for LDPC Codes

Hangxuan Cui, Jun Ting Lin, Zhongfeng Wang

Published Apr 17, 2019• 30 citations
Publisher

Abstract

Low-complexity and high-performance low-density parity-check (LDPC) decoders are highly demanded in various modern communication and storage systems. In this paper, a novel hard-decision decoding algorithm, called tabu-list random-penalty gradient descent bit-flipping (TRGDBF) algorithm, is proposed. Compared to the state-of-the-art hard-decision algorithms, the TRGDBF algorithm has much better error-correction performance due to several algorithmic improvements. First, a random-penalty term is introduced to the inversion function to help the decoder escape from trapping sets, which are the main causes of the error-floor phenomenon. Second, a tabu-list is employed to improve the decoding efficiency. Numerical results show that the TRGDBF algorithm can achieve up to two orders of magnitude better error-correction performance than the probabilistic gradient descent bit-flipping (PGDBF) algorithm and reduce the average iteration count by about 15%. In addition, a well-optimized hardware architecture is developed to implement the TRGDBF algorithm. Algorithmic transformation and architecture optimization are well explored to reduce the hardware complexity and latency. Synthesis results show that the TRGDBF decoder can work at a higher frequency and offer a larger throughput than the PGDBF decoder.

DOI
10.1109/tcsi.2019.2909653

Related papers

A New Probabilistic Gradient Descent Bit Flipping Decoder for LDPC Codes

Hangxuan Cui, Jun Ting Lin, Suwen Song +1 more

Probabilistic gradient descent bit-flipping (PGDBF) is the state-of-the-art hard-decision algorithm for decoding low-density parity-check (LDPC) codes on binary symmetric channel (BSC). However, there still exists a considerable performance gap between the PGDBF algorithm and soft-decision algorithms, especially in the error-floor region. To bridge this performance gap, a tabu-list aided PGDBF (T-PGDBF) algorithm is proposed in this paper. In the T-PGDBF algorithm, a tabu-list is employed to help the decoding escape from trapping sets, which is the main cause of the error-floor phenomenon. The bits which are flipped in the current iteration will be added to the tabu-list to prevent them being flipped in the next iteration. Simulation results show that the T-PGDBF algorithm offers a significant performance gain when compared to the PGDBF algorithm, which can reach that of soft-decision algorithms. We also present the hardware architecture to implement the T-PGDBF algorithm. Synthesis results show that the improved performance offered by the T-PGDBF algorithm can be obtained with a small hardware overhead.

IEEE International Symposium on Circuits and Systems proceedings•May 1, 2019•8 citations

Counter Random Gradient Descent Bit-Flipping Decoder for LDPC Codes

Keyue Deng, Hangxuan Cui, Jun Ting Lin +1 more

Tabu-list random-penalty gradient descent bit-flipping (TRGDBF) is a hard-decision algorithm for decoding low-density parity-check (LDPC) codes, which offers a significant improvement in error correction. However, compared to the current gradient descent bit-flipping (GDBF) variants, it converges slower and has no obvious performance advantage unless enough iterations are allowed. To accelerate the convergence speed, this paper presents a counter random GDBF (CRGDBF) algorithm in which a bit is forbidden to flip in the next iteration after being flipped several times. Incorporating the random operation, the forbidden-mechanism shows a dynamic property, facilitating the decoder more efficiently to break trapping sets. Simulation results show that the CRGDBF can achieve up to 5 times better decoding performance than the TRGDBF algorithm within finite iterations. Additionally, an architecture is presented for implementing the CRGDBF algorithm, demonstrating it only brings limited hardware overhead compared to the TRGDBF.

IEEE Computer Society Annual Symposium on VLSI•Jul 1, 2021•6 citations

Information Storage Bit-Flipping Decoder for LDPC Codes

Hangxuan Cui, Jun Ting Lin, Zhongfeng Wang

Tabu-list random-penalty gradient descent bit-flipping (TRGDBF) decoder is the state-of-the-art hard-decision low-density parity-check (LDPC) decoder in terms of error-correction performance on binary symmetric channel (BSC). However, the TRGDBF decoder suffers from a long critical path caused by the global maximum-finding operation, limiting the achievable throughput. This brief proposes an information storage bit-flipping (ISBF) decoder to solve this problem. Different from the existing bit-flipping (BF) decoders which adopt serial decoding manner, in the ISBF decoder, by storing the previous decoding information, the global maximum-finding operation can be executed in parallel to other decoding operations, significantly shortening the critical path. Moreover, a nonuniform flipping rule is incorporated to achieve a better decoding performance. We also present an efficient architecture to implement the ISBF decoder. The design example demonstrates that compared to other hard-decision BF decoders, the ISBF decoder could provide both the best decoding performance and throughput on BSC.

IEEE Transactions on Very Large Scale Integration (VLSI) Systems•Sep 17, 2020•18 citations

Design and Implementation of Hard-Decision LDPC Decoder

Yi Dong, Huimin Du, Shengfei Bai +3 more

Hard-decision LDPC decoders are widely used in communication and storage systems due to their simple circuits. However, existing hard decision LDPC decoding circuits lead to slow decoding convergence due to flipping according to the maximum energy value, reducing decoding performance. This paper proposes the Dual-Energy Probabilistic Gradient Descent Bit-Flipping (DPGDBF) hard-decision algorithm. If the energy value of the variable node reaches the threshold, all nodes with the threshold energy will be flipped, and the node with the sub-maximum threshold energy will be flipped with a certain probability. otherwise, only all variable nodes with the maximum energy value are flipped. The simulation results show that, in a limited iterative range, compared with Tabu-list Random-Penalty Gradient Descent Bit-Flipping (TRGDBF), for (2048, 1024) codes, the average number of decoding iterations of the algorithm is reduced by 12%, and the decoding performance is improved to a certain extent; for (9216,7680) codes, the average number of decoding iterations of the DPGDBF algorithm is reduced by 18%, and the decoding performance is improved by 4 times. In addition, this paper proposes a hardware implementation of the DPGDBF algorithm for (2048, 1024) codes, with a maximum clock frequency of 305.53MHz and a through-put of 19.52Gbps.

International Conference on Integrated Circuits and Microsystems (ICICM)•Oct 28, 2022•0 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

Efficient Hardware Implementation of Probabilistic Gradient Descent Bit-Flipping

Khoa Le, Fakhreddine Ghaffari, David Declercq +1 more

This paper deals with the hardware implementation of the recently introduced Probabilistic Gradient-Descent Bit-Flipping (PGDBF) decoder. The PGDBF is a new type of hard-decision decoder for Low-Density Parity-Check (LDPC) code, with improved error correction performance thanks to the introduction of deliberate random perturbation in the computing units. In the PGDBF, the random perturbation operates during the bit-flipping step, with the objective to avoid the attraction of so-called trapping-sets of the LDPC code. In this paper, we propose an efficient hardware architecture which minimizes the resource overhead needed to implement the random perturbations of the PGDBF. Our architecture is based on the use of a Short Random Sequence (SRS) that is duplicated to fully apply the PGDBF decoding rules, and on an optimization of the maximum finder unit. The generation of good SRS is crucial to maintain the outstanding decoding performance of PGDBF, and we propose two different methods with equivalent hardware overheads, but with different behaviors on different LDPC codes. Our designs show that the improved PGDBF performance gains can be obtained with a very small additional complexity, therefore providing a competitive hard-decision LDPC decoding solution for current standards.

IEEE Transactions on Circuits and Systems I Regular Papers•Dec 17, 2016•35 citations
Low-complexity and high-performance low-density parity-check (LDPC) decoders are highly demanded in various modern communication and storage systems. In this paper, a novel hard-decision decoding algorithm, called tabu-list random-penalty gradient descent bit-flipping (TRGDBF) algorithm, is proposed. Compared to the state-of-the-art hard-decision algorithms, the TRGDBF algorithm has much better error-correction performance due to several algorithmic improvements. First, a random-penalty term is introduced to the inversion function to help the decoder escape from trapping sets, which are the main causes of the error-floor phenomenon. Second, a tabu-list is employed to improve the decoding efficiency. Numerical results show that the TRGDBF algorithm can achieve up to two orders of magnitude better error-correction performance than the probabilistic gradient descent bit-flipping (PGDBF) algorithm and reduce the average iteration count by about 15%. In addition, a well-optimized hardware architecture is developed to implement the TRGDBF algorithm. Algorithmic transformation and architecture optimization are well explored to reduce the hardware complexity and latency. Synthesis results show that the TRGDBF decoder can work at a higher frequency and offer a larger throughput than the PGDBF decoder.
Probabilistic gradient descent bit-flipping (PGDBF) is the state-of-the-art hard-decision algorithm for decoding low-density parity-check (LDPC) codes on binary symmetric channel (BSC). However, there still exists a considerable performance gap between the PGDBF algorithm and soft-decision algorithms, especially in the error-floor region. To bridge this performance gap, a tabu-list aided PGDBF (T-PGDBF) algorithm is proposed in this paper. In the T-PGDBF algorithm, a tabu-list is employed to help the decoding escape from trapping sets, which is the main cause of the error-floor phenomenon. The bits which are flipped in the current iteration will be added to the tabu-list to prevent them being flipped in the next iteration. Simulation results show that the T-PGDBF algorithm offers a significant performance gain when compared to the PGDBF algorithm, which can reach that of soft-decision algorithms. We also present the hardware architecture to implement the T-PGDBF algorithm. Synthesis results show that the improved performance offered by the T-PGDBF algorithm can be obtained with a small hardware overhead.
Tabu-list random-penalty gradient descent bit-flipping (TRGDBF) is a hard-decision algorithm for decoding low-density parity-check (LDPC) codes, which offers a significant improvement in error correction. However, compared to the current gradient descent bit-flipping (GDBF) variants, it converges slower and has no obvious performance advantage unless enough iterations are allowed. To accelerate the convergence speed, this paper presents a counter random GDBF (CRGDBF) algorithm in which a bit is forbidden to flip in the next iteration after being flipped several times. Incorporating the random operation, the forbidden-mechanism shows a dynamic property, facilitating the decoder more efficiently to break trapping sets. Simulation results show that the CRGDBF can achieve up to 5 times better decoding performance than the TRGDBF algorithm within finite iterations. Additionally, an architecture is presented for implementing the CRGDBF algorithm, demonstrating it only brings limited hardware overhead compared to the TRGDBF.
Tabu-list random-penalty gradient descent bit-flipping (TRGDBF) decoder is the state-of-the-art hard-decision low-density parity-check (LDPC) decoder in terms of error-correction performance on binary symmetric channel (BSC). However, the TRGDBF decoder suffers from a long critical path caused by the global maximum-finding operation, limiting the achievable throughput. This brief proposes an information storage bit-flipping (ISBF) decoder to solve this problem. Different from the existing bit-flipping (BF) decoders which adopt serial decoding manner, in the ISBF decoder, by storing the previous decoding information, the global maximum-finding operation can be executed in parallel to other decoding operations, significantly shortening the critical path. Moreover, a nonuniform flipping rule is incorporated to achieve a better decoding performance. We also present an efficient architecture to implement the ISBF decoder. The design example demonstrates that compared to other hard-decision BF decoders, the ISBF decoder could provide both the best decoding performance and throughput on BSC.
Hard-decision LDPC decoders are widely used in communication and storage systems due to their simple circuits. However, existing hard decision LDPC decoding circuits lead to slow decoding convergence due to flipping according to the maximum energy value, reducing decoding performance. This paper proposes the Dual-Energy Probabilistic Gradient Descent Bit-Flipping (DPGDBF) hard-decision algorithm. If the energy value of the variable node reaches the threshold, all nodes with the threshold energy will be flipped, and the node with the sub-maximum threshold energy will be flipped with a certain probability. otherwise, only all variable nodes with the maximum energy value are flipped. The simulation results show that, in a limited iterative range, compared with Tabu-list Random-Penalty Gradient Descent Bit-Flipping (TRGDBF), for (2048, 1024) codes, the average number of decoding iterations of the algorithm is reduced by 12%, and the decoding performance is improved to a certain extent; for (9216,7680) codes, the average number of decoding iterations of the DPGDBF algorithm is reduced by 18%, and the decoding performance is improved by 4 times. In addition, this paper proposes a hardware implementation of the DPGDBF algorithm for (2048, 1024) codes, with a maximum clock frequency of 305.53MHz and a through-put of 19.52Gbps.
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.
This paper deals with the hardware implementation of the recently introduced Probabilistic Gradient-Descent Bit-Flipping (PGDBF) decoder. The PGDBF is a new type of hard-decision decoder for Low-Density Parity-Check (LDPC) code, with improved error correction performance thanks to the introduction of deliberate random perturbation in the computing units. In the PGDBF, the random perturbation operates during the bit-flipping step, with the objective to avoid the attraction of so-called trapping-sets of the LDPC code. In this paper, we propose an efficient hardware architecture which minimizes the resource overhead needed to implement the random perturbations of the PGDBF. Our architecture is based on the use of a Short Random Sequence (SRS) that is duplicated to fully apply the PGDBF decoding rules, and on an optimization of the maximum finder unit. The generation of good SRS is crucial to maintain the outstanding decoding performance of PGDBF, and we propose two different methods with equivalent hardware overheads, but with different behaviors on different LDPC codes. Our designs show that the improved PGDBF performance gains can be obtained with a very small additional complexity, therefore providing a competitive hard-decision LDPC decoding solution for current standards.