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 Communications Letters

The Syndrome Bit Flipping Algorithm for LDPC Codes

Emmanuel Boutillon, Chris Winstead, Fakhreddine Ghaffari

Published May 1, 2023• 10 citations
Publisher

Abstract

Performance of LDPC decoders at high SNR is dominated by trapping sets that induce an error floor in the performance curve. We propose a new algorithm that resolves trapping sets and lowers the error floor. The new algorithm, called Syndrome Bit Flipping (SBF), computes the sum of adjacent parity violations at each symbol node. Bits are flipped by comparing the syndrome sum against a time-varying threshold called the decoding key. SBF is compared to other bit-flipping decoders on the Binary Symmetric Channel (BSC), and is demonstrated as a post-processing step for a Noisy Gradient Descent Bit-Flipping (NGDBF) hardware decoder. We demonstrate the post-processing method for an LDPC code defined in the 802.3an standard, and find that the frame error rate is improved by at least two orders of magnitude, even as the required iterations are reduced by 33%.

DOI
10.1109/lcomm.2023.3272277

Related papers

Syndrome-Aided Gradient Descent Bit Flipping Algorithm for LDPC Decoding

Yuang Huang, Haiyang Liu

Gradient descent bit flipping (GDBF) algorithm is an important low-complexity method for decoding LDPC codes. In particular, the multi-bit GDBF decoding has the best decoding performance among BF algorithms if a suitable threshold is prescribed. However, extensive computer searches are needed to find such a threshold for a specific LDPC code. In this paper, we propose a syndrome-aided GDBF (SAGDBF) algorithm to address the problem. The thresholds in our algorithm are adaptively adjusted according to the syndrome values in the iterative process. Simulation results for different LDPC codes suggest that the error performances of the proposed SAGDBF algorithm are close to and even better than the original multi-bit GDBF algorithm at a relatively small number of iterations. In addition, the complexity increased in our proposed algorithm is negligible compared with the original multi-bit GDBF algorithm. Hence, the proposed algorithm is suitable for practical purposes.

IEEE International Conference on Computer and Communications (ICCC)•Dec 11, 2020•2 citations

An Improved Syndrome Bit Flipping Decoder with Narrowed Flipping Set for LDPC Codes

Wenlin Zhao, Jie Zhang, Li Li +1 more

In this paper, we propose an improved Syndrome Bit Flipping (SBF) decoding algorithm that utilizes narrowed flipping set. The narrowed flipping set is prone to contain all error bit positions with high probability. To construct the narrowed flipping set, part of its elements are selected according to channel information, and the rest are constructed by random selections. The narrowed flipping set mitigates possible error propagation by avoiding some non-error bits being unnessary flipped, thereby further improving the decoding performance of the original SBF algorithm. The simulation results show that the proposed algorithm can achieve about 1.2 dB bit error rate gain compared with the original SBF algorithm, with a modest increase in computational complexity.

IEEE International Conference on Computer and Communications (ICCC)•Dec 8, 2023•0 citations

Decoding LDPC codes via Noisy Gradient Descent Bit-Flipping with Re-Decoding

Tasnuva Tithi, Chris Winstead, Gopalakrishnan Sundararajan

In this paper, we consider the performance of the Noisy Gradient Descent Bit Flipping (NGDBF) algorithm under re-decoding of failed frames. NGDBF is a recent algorithm that uses a non-deterministic gradient descent search to decode low-density parity check (LDPC) codes. The proposed re-decode procedure obtains improved performance because the perturbations are independent at each re-decoding phase, therefore increasing the likelihood of successful decoding. We examine the benefits of re-decoding for an LDPC code from the IEEE 802.3an standard, and find that only a small fraction of re-decoded frames are needed to obtain significant performance benefits. When re-decoding is used, the NGDBF performance is very close to a benchmark offset min-sum decoder for the 802.3an code.

arXiv:1503.08913•Mar 31, 2015•6 citations

New hard decision decoder of LDPC codes using single Bit Flipping algorithm

Soufian Addi, Ahlam Berkani, Ahmed Azouaoui +1 more

The Bit-Flipping (BF) algorithm is considered as a hard decoding method for LDPC codes. It is much simpler than the probabilistic methods like Sum Product Algorithm (SPA), and can be efficiently implemented by electronic circuits. In this paper, we propose a new Bit Flipping algorithm for Low-Density Parity-Check codes (LDPC) called Single Bit-Flipping (SBF). Compared to the Gallager Bit-Flipping algorithm, the proposed algorithm employs criteria of flipping single bit chosen carefully. This method eliminates the risk for flipping more than one bit at a time that can induce additional error bits and propagate the errors to the later iterations. We present some results obtained by applying this new method that provides a gain in performance in comparison to the standard Gallager Bit-Flipping with low complexity.

International Conference on Wireless Networks and Mobile Communications (WINCOM)•Nov 1, 2017•5 citations

Two-bit bit flipping decoding of LDPC codes

Dung Viet Nguyen, Bane V. Vasic, Michael W. Marcellin

In this paper, we propose a new class of bit flipping algorithms for low-density parity-check (LDPC) codes over the binary symmetric channel (BSC). Compared to the regular (parallel or serial) bit flipping algorithms, the proposed algorithms employ one additional bit at a variable node to represent its “strength.” The introduction of this additional bit increases the guaranteed error correction capability by a factor of at least 2. An additional bit can also be employed at a check node to capture information which is beneficial to decoding. A framework for failure analysis of the proposed algorithms is described. These algorithms outperform the Gallager A/B algorithm and the min-sum algorithm at much lower complexity. Concatenation of two-bit bit flipping algorithms show a potential to approach the performance of belief propagation (BP) decoding in the error floor region, also at lower complexity.

arXiv:1103.0801•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2011•7 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
Performance of LDPC decoders at high SNR is dominated by trapping sets that induce an error floor in the performance curve. We propose a new algorithm that resolves trapping sets and lowers the error floor. The new algorithm, called Syndrome Bit Flipping (SBF), computes the sum of adjacent parity violations at each symbol node. Bits are flipped by comparing the syndrome sum against a time-varying threshold called the decoding key. SBF is compared to other bit-flipping decoders on the Binary Symmetric Channel (BSC), and is demonstrated as a post-processing step for a Noisy Gradient Descent Bit-Flipping (NGDBF) hardware decoder. We demonstrate the post-processing method for an LDPC code defined in the 802.3an standard, and find that the frame error rate is improved by at least two orders of magnitude, even as the required iterations are reduced by 33%.
Gradient descent bit flipping (GDBF) algorithm is an important low-complexity method for decoding LDPC codes. In particular, the multi-bit GDBF decoding has the best decoding performance among BF algorithms if a suitable threshold is prescribed. However, extensive computer searches are needed to find such a threshold for a specific LDPC code. In this paper, we propose a syndrome-aided GDBF (SAGDBF) algorithm to address the problem. The thresholds in our algorithm are adaptively adjusted according to the syndrome values in the iterative process. Simulation results for different LDPC codes suggest that the error performances of the proposed SAGDBF algorithm are close to and even better than the original multi-bit GDBF algorithm at a relatively small number of iterations. In addition, the complexity increased in our proposed algorithm is negligible compared with the original multi-bit GDBF algorithm. Hence, the proposed algorithm is suitable for practical purposes.
In this paper, we propose an improved Syndrome Bit Flipping (SBF) decoding algorithm that utilizes narrowed flipping set. The narrowed flipping set is prone to contain all error bit positions with high probability. To construct the narrowed flipping set, part of its elements are selected according to channel information, and the rest are constructed by random selections. The narrowed flipping set mitigates possible error propagation by avoiding some non-error bits being unnessary flipped, thereby further improving the decoding performance of the original SBF algorithm. The simulation results show that the proposed algorithm can achieve about 1.2 dB bit error rate gain compared with the original SBF algorithm, with a modest increase in computational complexity.
In this paper, we consider the performance of the Noisy Gradient Descent Bit Flipping (NGDBF) algorithm under re-decoding of failed frames. NGDBF is a recent algorithm that uses a non-deterministic gradient descent search to decode low-density parity check (LDPC) codes. The proposed re-decode procedure obtains improved performance because the perturbations are independent at each re-decoding phase, therefore increasing the likelihood of successful decoding. We examine the benefits of re-decoding for an LDPC code from the IEEE 802.3an standard, and find that only a small fraction of re-decoded frames are needed to obtain significant performance benefits. When re-decoding is used, the NGDBF performance is very close to a benchmark offset min-sum decoder for the 802.3an code.
The Bit-Flipping (BF) algorithm is considered as a hard decoding method for LDPC codes. It is much simpler than the probabilistic methods like Sum Product Algorithm (SPA), and can be efficiently implemented by electronic circuits. In this paper, we propose a new Bit Flipping algorithm for Low-Density Parity-Check codes (LDPC) called Single Bit-Flipping (SBF). Compared to the Gallager Bit-Flipping algorithm, the proposed algorithm employs criteria of flipping single bit chosen carefully. This method eliminates the risk for flipping more than one bit at a time that can induce additional error bits and propagate the errors to the later iterations. We present some results obtained by applying this new method that provides a gain in performance in comparison to the standard Gallager Bit-Flipping with low complexity.
In this paper, we propose a new class of bit flipping algorithms for low-density parity-check (LDPC) codes over the binary symmetric channel (BSC). Compared to the regular (parallel or serial) bit flipping algorithms, the proposed algorithms employ one additional bit at a variable node to represent its “strength.” The introduction of this additional bit increases the guaranteed error correction capability by a factor of at least 2. An additional bit can also be employed at a check node to capture information which is beneficial to decoding. A framework for failure analysis of the proposed algorithms is described. These algorithms outperform the Gallager A/B algorithm and the min-sum algorithm at much lower complexity. Concatenation of two-bit bit flipping algorithms show a potential to approach the performance of belief propagation (BP) decoding in the error floor region, also at lower complexity.
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.