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

Advances in Mathematics of Communications

On the multiple threshold decoding of LDPC codes over GF(q)

Alexey Frolov, Victor Zyablov

Published Jan 1, 2017• 2 citations
Publisher

Abstract

We consider decoding of LDPC codes over GF(q) with a harddecision low-complexity majority algorithm, which is a generalization of the bit-flipping algorithm for binary LDPC codes. A modification of this algorithm with multiple thresholds is suggested. A lower estimate on the decoding radius realized by the new algorithm is derived. The estimate is shown to be better than the estimate for a single threshold majority decoder. At the same time, introducing multiple thresholds does not affect the order of decoding complexity.

DOI
10.3934/amc.2017007

Related papers

On the multiple threshold decoding of LDPC codes over GF(q)

Alexey Frolov, Victor Zyablov

We consider the decoding of LDPC codes over GF(q) with the low-complexity majority algorithm from [1]. A modification of this algorithm with multiple thresholds is suggested. A lower estimate on the decoding radius realized by the new algorithm is derived. The estimate is shown to be better than the estimate for a single threshold majority decoder. At the same time the transition to multiple thresholds does not affect the order of complexity.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2015•4 citations

On the Multiple Threshold Decoding of LDPC codes over GF(q)

Alexey Frolov, Victor Zyablov

We consider the decoding of LDPC codes over GF(q) with the low-complexity majority algorithm from [1]. A modification of this algorithm with multiple thresholds is suggested. A lower estimate on the decoding radius realized by the new algorithm is derived. The estimate is shown to be better than the estimate for a single threshold majority decoder. At the same time the transition to multiple thresholds does not affect the order of complexity.

arXiv:1502.06871•Feb 24, 2015•1 citation

On the Decoding Radius Realized by Low-Complexity Decoded Non-Binary Irregular LDPC Codes

Pavel S. Rybin, Alexey Frolov

In this paper we consider the low complexity majority-logic decoding algorithm for irregular non-binary low-density parity-check (LDPC) codes. The decoding algorithm is a generalization of the bit-flipping algorithm for binary LDPC codes. The lower estimate on the decoding radius realized by this algorithm is derived for the first time for irregular non-binary LDPC codes. We present the numerical results for the derived lower bound.

International Symposium on Information Theory and its Applications•Oct 1, 2018•1 citation

Multi-Threshold Bit Flipping Algorithm for Decoding Structured LDPC Codes

Yuanhua Liu, Xinliang Niu, Meiling Zhang

A novel bit-flipping (BF) decoding algorithm is proposed for structured low-density parity-check (LDPC) codes. The proposed BF algorithm which is called multi-threshold bit-flipping (MTBF) algorithm, flips multiple bits by using multiple thresholds at each iteration. It only requires some real operations before iterations and requires only logical operations during the iterations. The MTBF algorithm has lower complexity than the weighted bit-flipping algorithm and its modifications. Simulations show that the proposed algorithm has fast convergence speed and good performance.

IEEE Communications Letters•Nov 24, 2014•22 citations

Approximate iterative LP decoding of LDPC codes over GF(q) in linear complexity

Dina Goldin, David Burshtein

The problem of low-complexity approximated linear programming (LP) decoding of LDPC codes over GF(q) is considered. An iterative algorithm with linear complexity was proposed by Burshtein for the binary case. However, this algorithm cannot be trivially generalized for the non-binary case, since the derivation uses the even parity property of the check nodes, which does not hold for codes over GF(q). In this work the algorithm is generalized to the non-binary case. We show, that by applying this algorithm to a softened version of the non-binary LP problem proposed by Flanagan, Skachek, Byrne and Grefeath, we can obtain, with complexity linear in the block length, a feasible solution vector for the non-binary LP decoding problem, which is arbitrarily close to optimal in the following sense. The distance between the minimum value achieved by the exact LP decoder and the objective function value of the approximate solution, normalized by the block length of the code, can be made arbitrarily small. We present simulation results and comparisons with the belief propagation (BP) algorithm using-regular ternary LDPC codes. The proposed algorithm can be easily extended to generalized LDPC codes.

IEEE Convention of Electrical and Electronics Engineers in Israel•Nov 1, 2010•3 citations

Reduced complexity and improved performance decoding algorithm for nonbinary LDPC codes over GF(q)

Xin Chen, Aidong Men

Low-density parity-check (LDPC) codes over finite fields GF(q) have a better performance than those of the binary low-density parity-check codes, at short and medium block lengths, but the decoder of GF(q)-LDPC has more complexity. In this paper, we present a new reduced-complexity belief propagation (BP) decoding algorithm for GF(q)-LDPC codes by analyzing the reliability of code symbols. Instead of update all the variable nodes during iteration, we just update variable nodes which are mostly to be in an error. The algorithm also shows a property to reduce the effects of oscillating on decoding. The simulations prove that we could improve performance and reduce complexity at the same time for short and medium GF(q)-LDPC codes.

IEEE International Conference on Communication Technology (ICCT)•Nov 1, 2008•6 citations
We consider decoding of LDPC codes over GF(q) with a harddecision low-complexity majority algorithm, which is a generalization of the bit-flipping algorithm for binary LDPC codes. A modification of this algorithm with multiple thresholds is suggested. A lower estimate on the decoding radius realized by the new algorithm is derived. The estimate is shown to be better than the estimate for a single threshold majority decoder. At the same time, introducing multiple thresholds does not affect the order of decoding complexity.
A novel bit-flipping (BF) decoding algorithm is proposed for structured low-density parity-check (LDPC) codes. The proposed BF algorithm which is called multi-threshold bit-flipping (MTBF) algorithm, flips multiple bits by using multiple thresholds at each iteration. It only requires some real operations before iterations and requires only logical operations during the iterations. The MTBF algorithm has lower complexity than the weighted bit-flipping algorithm and its modifications. Simulations show that the proposed algorithm has fast convergence speed and good performance.
The problem of low-complexity approximated linear programming (LP) decoding of LDPC codes over GF(q) is considered. An iterative algorithm with linear complexity was proposed by Burshtein for the binary case. However, this algorithm cannot be trivially generalized for the non-binary case, since the derivation uses the even parity property of the check nodes, which does not hold for codes over GF(q). In this work the algorithm is generalized to the non-binary case. We show, that by applying this algorithm to a softened version of the non-binary LP problem proposed by Flanagan, Skachek, Byrne and Grefeath, we can obtain, with complexity linear in the block length, a feasible solution vector for the non-binary LP decoding problem, which is arbitrarily close to optimal in the following sense. The distance between the minimum value achieved by the exact LP decoder and the objective function value of the approximate solution, normalized by the block length of the code, can be made arbitrarily small. We present simulation results and comparisons with the belief propagation (BP) algorithm using-regular ternary LDPC codes. The proposed algorithm can be easily extended to generalized LDPC codes.
Low-density parity-check (LDPC) codes over finite fields GF(q) have a better performance than those of the binary low-density parity-check codes, at short and medium block lengths, but the decoder of GF(q)-LDPC has more complexity. In this paper, we present a new reduced-complexity belief propagation (BP) decoding algorithm for GF(q)-LDPC codes by analyzing the reliability of code symbols. Instead of update all the variable nodes during iteration, we just update variable nodes which are mostly to be in an error. The algorithm also shows a property to reduce the effects of oscillating on decoding. The simulations prove that we could improve performance and reduce complexity at the same time for short and medium GF(q)-LDPC codes.