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

International Conference on Communications

MUDRI: A fault-tolerant decoding algorithm

Predrag Ivaniš, Omran Al Rasheed, Bane V. Vasic

Published Jun 1, 2015• 12 citations
Publisher

Abstract

We propose an improved version of probabilistic gradient descent bit flipping algorithm for decoding low density parity check codes, based on MUltiple Decoding attempts and Random re-Initializations (MUDRI). The proposed algorithm significantly increases the probability of correcting error patterns uncorrectable by the existing variants of bit-flipping algorithm. The performance of the algorithm implemented in noisy hardware is analyzed for various code types and codeword lengths, and shown to be superior compared to other hard decision algorithms. The MUDRI decoder is mostly insensitive to the failures in registers and logic gates and therefore represents a desirable solution for implementation in unreliable hardware.

DOI
10.1109/icc.2015.7248997

Related papers

Fault-Tolerant Probabilistic Gradient-Descent Bit Flipping Decoder

Omran Al Rasheed, Predrag Ivaniš, Bane V. Vasic

We propose a gradient descent type bit flipping algorithm for decoding low density parity check codes on the binary symmetric channel. Randomness introduced in the bit flipping rule makes this class of decoders not only superior to other decoding algorithms of this type, but also robust to logic-gate failures. We report a surprising discovery that for a broad range of gate failure probability our decoders actually benefit from faults in logic gates which serve as an inherent source of randomness and help the decoding algorithm to escape from local minima associated with trapping sets.

IEEE Communications Letters•Jul 30, 2014•83 citations

An Improved Gradient Descent Bit-Flipping Decoder for LDPC Codes

Hangxuan Cui, Jun Ting Lin, Zhongfeng Wang

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.

IEEE Transactions on Circuits and Systems I Regular Papers•Apr 17, 2019•30 citations

An improvement and a fast DSP implementation of the bit flipping algorithms for low density parity check decoder

Mouhcine Razi, Mhammed Benhayoun, Anass Mansouri +1 more

For low density parity check (LDPC) decoding, hard-decision algorithms are sometimes more suitable than the soft-decision ones. Particularly in the high throughput and high speed applications. However, there exists a considerable gap in performances between these two classes of algorithms in favor of soft-decision algorithms. In order to reduce this gap, in this work we introduce two new improved versions of the hard-decision algorithms, the adaptative gradient descent bit-flipping (AGDBF) and adaptative reliability ratio weighted GDBF (ARRWGDBF). An adaptative weighting and correction factor is introduced in each case to improve the performances of the two algorithms allowing an important gain of bit error rate. As a second contribution of this work a real time implementation of the proposed solutions on a digital signal processors (DSP) is performed in order to optimize and improve the performance of these new approchs. The results of numerical simulations and DSP implementation reveal a faster convergence with a low processing time and a reduction in consumed memory resources when compared to soft-decision algorithms. For the irregular LDPC code, our approachs achieves gains of 0.25 and 0.15 dB respectively for the AGDBF and ARRWGDBF algorithms.

International Journal of Power Electronics and Drive Systems/International Journal of Electrical and Computer Engineering•Aug 16, 2021•5 citations

Efficient Hardware Implementation of Probabilistic Gradient Descent Bit Flipping

B Srisailam, T Nagaraju

This paper presents a new Bit Flipping (BF) decoder, called Probabilistic Parallel Bit Flipping (PPBF) for Low-Density Parity-Check (LDPC) codes on the Binary Symmetric Channel.In PPBF, the flipping operation is preceded with a probabilistic behavior which is shown to improve significantly the error correction performance.The advantage of PPBF comes from the fact that, no global computation is required during the decoding process and from that, all the computations can be executed in the local computing units and in-parallel.PPBF provides a considerable improvement of the decoding frequency and complexity, compared to other known BF decoders, while obtaining a significant gain in error correction.One improved version of PPBF, called non-syndrome PPBF (NS-PPBF) is also introduced, in which the global syndrome check is moved out of the critical path and a new terminating mechanism is proposed.In order to show the superiority of the new decoders in terms of hardware efficiency and decoding throughput, the corresponding hardware architectures are presented in the second part of the paper.The ASIC synthesis results confirm that, the decoding frequency of the proposed decoders is significantly improved, much higher than the BF decoders of literature while requiring lower complexity to be efficiently implemented.

International Journal of Innovative Technology and Research•Jan 11, 2020•0 citations

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

An Improved Iterative Bit-flipping Decoding Algorithm for Low-density Parity-check Codes

Meiling Zhang

An improved iterative bit-flipping(BF) algorithm adapted for decoding low-density parity-check(LDPC) codes is proposed to improve the performance of the hard-decision BF decoding algorithm.The new algorithm uses an alternating threshold pattern to determine the bits whether to be flipped or not,and the flipping error probability is effectively decreased.Simulation results show that compared with BF algorithm,the improved BF algorithm improves both the error-correction performance and the convergence speed while maintaining the low computational complexity.

Telecommunication Engineering•Jan 1, 2012•0 citations
We propose an improved version of probabilistic gradient descent bit flipping algorithm for decoding low density parity check codes, based on MUltiple Decoding attempts and Random re-Initializations (MUDRI). The proposed algorithm significantly increases the probability of correcting error patterns uncorrectable by the existing variants of bit-flipping algorithm. The performance of the algorithm implemented in noisy hardware is analyzed for various code types and codeword lengths, and shown to be superior compared to other hard decision algorithms. The MUDRI decoder is mostly insensitive to the failures in registers and logic gates and therefore represents a desirable solution for implementation in unreliable hardware.
We propose a gradient descent type bit flipping algorithm for decoding low density parity check codes on the binary symmetric channel. Randomness introduced in the bit flipping rule makes this class of decoders not only superior to other decoding algorithms of this type, but also robust to logic-gate failures. We report a surprising discovery that for a broad range of gate failure probability our decoders actually benefit from faults in logic gates which serve as an inherent source of randomness and help the decoding algorithm to escape from local minima associated with trapping sets.
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.
For low density parity check (LDPC) decoding, hard-decision algorithms are sometimes more suitable than the soft-decision ones. Particularly in the high throughput and high speed applications. However, there exists a considerable gap in performances between these two classes of algorithms in favor of soft-decision algorithms. In order to reduce this gap, in this work we introduce two new improved versions of the hard-decision algorithms, the adaptative gradient descent bit-flipping (AGDBF) and adaptative reliability ratio weighted GDBF (ARRWGDBF). An adaptative weighting and correction factor is introduced in each case to improve the performances of the two algorithms allowing an important gain of bit error rate. As a second contribution of this work a real time implementation of the proposed solutions on a digital signal processors (DSP) is performed in order to optimize and improve the performance of these new approchs. The results of numerical simulations and DSP implementation reveal a faster convergence with a low processing time and a reduction in consumed memory resources when compared to soft-decision algorithms. For the irregular LDPC code, our approachs achieves gains of 0.25 and 0.15 dB respectively for the AGDBF and ARRWGDBF algorithms.
This paper presents a new Bit Flipping (BF) decoder, called Probabilistic Parallel Bit Flipping (PPBF) for Low-Density Parity-Check (LDPC) codes on the Binary Symmetric Channel.In PPBF, the flipping operation is preceded with a probabilistic behavior which is shown to improve significantly the error correction performance.The advantage of PPBF comes from the fact that, no global computation is required during the decoding process and from that, all the computations can be executed in the local computing units and in-parallel.PPBF provides a considerable improvement of the decoding frequency and complexity, compared to other known BF decoders, while obtaining a significant gain in error correction.One improved version of PPBF, called non-syndrome PPBF (NS-PPBF) is also introduced, in which the global syndrome check is moved out of the critical path and a new terminating mechanism is proposed.In order to show the superiority of the new decoders in terms of hardware efficiency and decoding throughput, the corresponding hardware architectures are presented in the second part of the paper.The ASIC synthesis results confirm that, the decoding frequency of the proposed decoders is significantly improved, much higher than the BF decoders of literature while requiring lower complexity to be efficiently implemented.
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.
An improved iterative bit-flipping(BF) algorithm adapted for decoding low-density parity-check(LDPC) codes is proposed to improve the performance of the hard-decision BF decoding algorithm.The new algorithm uses an alternating threshold pattern to determine the bits whether to be flipped or not,and the flipping error probability is effectively decreased.Simulation results show that compared with BF algorithm,the improved BF algorithm improves both the error-correction performance and the convergence speed while maintaining the low computational complexity.