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

Non-Binary LDPC Decoder Based on Symbol Flipping with Multiple Votes

Francisco García-Herrero, David Declercq, Javier Valls

Published Apr 11, 2014• 36 citations
Publisher

Abstract

In this letter, a new algorithm to decode non-binary LDPC (NB-LDPC) codes is proposed. This algorithm is inspired from very low complexity decoders that have been proposed recently, in which only syndrome computations at the check node update are used, while performing symbol-flipping based update at the variable node. Usually, the low complexity decoders based on symbol flipping suffer from a non-negligible performance degradation compared to soft-decision NB-LDPC decoders. Our improved decoder makes use of a list of syndrome computations instead of a single one based on hard-decision, and builds soft information at the variable node input by assigning votes weighted by different amplitudes. Simulations show that using multiple votes with multiple weights yields better performance, while still maintaining the low complexity feature.

DOI
10.1109/lcomm.2014.030914.132867

Related papers

Multiple-Votes Parallel Symbol-Flipping Decoding Algorithm for Non-Binary LDPC Codes

Nhat-Quang Nhan, Telex M. N. Ngatched, Octavia A. Dobre +3 more

A novel decoding algorithm for non-binary low density parity check (NB-LDPC) codes is proposed. The algorithm builds on the recently designed parallel symbol-flipping decoding (PSFD) algorithm and combines a technique of error estimation and a method of multiple voting levels from each unsatisfied check-sum to the corresponding variable nodes. Simulations results, performed on a number of NB-LDPC codes of various lengths and column weights constructed using several methods, show that the new algorithm not only avoids using code-dependent voting threshold but also improves the error rate performance of the PSFD algorithm, particularly for low column weight parity-check matrices.

IEEE Communications Letters•Apr 1, 2015•20 citations

Low Complexity Bit Reliability and Predication Based Symbol Value Selection Decoding Algorithms for Non-Binary LDPC Codes

Waheed Ullah, Ling Cheng, Fambirai Takawira

The main challenge for hardware implementation of non-binary LDPC decoding is the high computational complexity and large memory requirement. To address this challenge, five new low complexity LDPC decoding algorithms are proposed in this paper. The proposed algorithms are developed specifically towards the low complexity, yet effective, decoding of the NB LDPC codes. The proposed decoding algorithms update, iteratively, the hard decision received vector to search for the valid codeword in the vector space of Galois field ${(GF)}$ . The selection criterion for least reliable symbol positions is based on the information from the failed checks and the reliability information from the Galois field structure as well as from the received channel soft information. To choose the correct value for the candidate symbol, two methods are used. The first method is based on the prediction of the error symbol from the set of Galois field symbols which maximize an objective function. In the second method, individual bits are flipped based on the reliability information obtained from the channel. Algorithms 1 and 2 flip a single symbol per iteration whilst the other three algorithms 3, 4 and 5 flip multiple symbols in each iteration. The proposed voting based Algorithms 1, 2 and 5 first short list the unreliable positions using a majority voting scheme and then choose the candidate symbol value from the set of the symbols in ${GF(q)}$ while not violating the field order ${q}$ . These methods simplify the decoding complexity in terms of computation and memory. Results and analysis of these algorithms show an appealing tradeoff between computational complexity and bit error rate performance for NB LDPC codes.

IEEE Access•Jan 1, 2020•13 citations

A Multiple-Voting-Based Decoding Algorithm for Nonbinary LDPC-Coded Modulation Systems

Min Zhu, Quan Guo, Hengzhou Xu +2 more

We propose a multiple-voting-based joint detection-decoding algorithm for nonbinary low-density parity-check (LDPC)-coded modulation systems. This algorithm is inspired from the reliability-based JDD algorithm for nonbinary LDPC-coded modulation systems, that has been proposed recently, in which the accumulated reliability of symbols based on one-step majority-logic decoding algorithm and the Chase-like local list decoding algorithm are used. However, the reliability-based JDD algorithm still has a significant performance degradation of at least 1 dB with low column weight (dv≤4). In order to reduce the performance degradation with low column weight, the proposed algorithm allows unfixed number of variable nodes to pass two symbols to the associated check node, in contrast with the reliability-based JDD algorithm, which allows only one variable node to pass two symbols to check node, when updating variable-to-check messages. Moreover, the votes are weighted differently according to the components of the list in the check-sum computation. Simulations show that the proposed algorithm yields better performance with low column weight, while still maintaining the low complexity feature.

IEEE Access•Jan 1, 2017•3 citations

Prediction and Voting Based Symbol Flipping Non-Binary LDPC Decoding Algorithms

Waheed Ullah, Ling Cheng, Fambirai Takawira

In this paper, we present two low complexity algorithms to decode non-binary LDPC codes. The proposed decoding algorithms update iteratively the hard decision received vector to search for a valid codeword in the vector space of Galois field (GF). The selection criterion for the position of unreliable symbols is based on failed checks and the information from the Galois field structure. In the first proposed algorithm, the flipping function is calculated for all symbols of the received sequence and multiple symbols are flipped in each iteration while in the second proposed algorithm, a single symbol is flipped per iteration. In the second method, unreliable positions are short-listed by using a majority voting scheme, and then the flipping function is computed to predict candidate symbols from the set of symbols in GF(q) while not violating the field order q. The proposed methods reduce the decoding complexity and memory use. The results of the algorithms show appealing tradeoffs between complexity and bit error rate performance for non-binary LDPC codes.

IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC)•Aug 1, 2020•5 citations

Multiple-Vote Symbol-Flipping Decoder for Nonbinary LDPC Codes

Francisco García-Herrero, Erbao Li, David Declercq +1 more

A multiple-vote symbol-flipping (MV-SF) decoding algorithm for nonbinary low-density parity-check (NB-LDPC) codes is proposed in this paper. Our algorithm improves the generalized bit-flipping algorithm (GBFDA) by considering the multiplicity of the candidates at the check-node output, to perform a more accurate symbol-flipping decision at the variable node update. The MV-SF algorithm greatly improves the frame error rate performance of GBFDA and approaches the performance of the best state-of-the-art decoders [extended min-sum and min-max (Min–Max)] with lower complexity. For a$(N=837,K=723)$NB-LDPC code over GF(32), the decoder derived from the proposed algorithm can reach a throughput higher than 500 Mb/s and a coding gain of 0.44 dB compared with the most efficient GBFDA architecture with only twice the silicon area. Our architecture has 27% efficiency gain compared with the best Min–Max architecture found in the literature, with a performance loss of just 0.21 dB at frame error rate$10^{-4}$.

IEEE Transactions on Very Large Scale Integration (VLSI) Systems•Feb 4, 2014•14 citations

Simplified Symbol Flipping Algorithms for Nonbinary Low-Density Parity-Check Codes

Jianyong Zhang

Based on the symbol-flipping algorithm with multiple-votes (MV-SF), this paper presents two simplified algorithms, symbol flipping with truncated and multiple votes (T-MV-SF) and symbol flipping with simplified and multiple votes (S-MV-SF), for nonbinary low-density parity-check(NB-LDPC) codes. Unlike previous symbol-flipping based algorithms (SFBAs), the T(S)-MV-SF uses the truncated voting information in each check and variable node update. The proposed algorithms also approximate the sorting function in each check update. Therefore, their complexity and memory consumption are remarkably reduced as compared with existing SFBAs. Furthermore, we introduce several parameters to compensate the information loss caused by the truncated voting information. After optimizing all the parameters, the proposed algorithms even have better performance than the MV-SF. As compared with the MV-SF, the maximum performance gain among all numerical examples is about 0.11 dB for the S-MV-SF on the (63, 37) code. The T-MV-SF has the largest reduction of the computational complexity on the (255, 175) code, which is about 80% of the complexity of the MV-SF. Moreover, the performance of the T-MV-SF is better than the MV-SF on the (255, 175) code. As a result, the proposed algorithms can effectively balance the error performance and complexity for decoding of NB-LDPCs.

IEEE Transactions on Communications•Jan 1, 2017•5 citations
In this letter, a new algorithm to decode non-binary LDPC (NB-LDPC) codes is proposed. This algorithm is inspired from very low complexity decoders that have been proposed recently, in which only syndrome computations at the check node update are used, while performing symbol-flipping based update at the variable node. Usually, the low complexity decoders based on symbol flipping suffer from a non-negligible performance degradation compared to soft-decision NB-LDPC decoders. Our improved decoder makes use of a list of syndrome computations instead of a single one based on hard-decision, and builds soft information at the variable node input by assigning votes weighted by different amplitudes. Simulations show that using multiple votes with multiple weights yields better performance, while still maintaining the low complexity feature.
A novel decoding algorithm for non-binary low density parity check (NB-LDPC) codes is proposed. The algorithm builds on the recently designed parallel symbol-flipping decoding (PSFD) algorithm and combines a technique of error estimation and a method of multiple voting levels from each unsatisfied check-sum to the corresponding variable nodes. Simulations results, performed on a number of NB-LDPC codes of various lengths and column weights constructed using several methods, show that the new algorithm not only avoids using code-dependent voting threshold but also improves the error rate performance of the PSFD algorithm, particularly for low column weight parity-check matrices.
The main challenge for hardware implementation of non-binary LDPC decoding is the high computational complexity and large memory requirement. To address this challenge, five new low complexity LDPC decoding algorithms are proposed in this paper. The proposed algorithms are developed specifically towards the low complexity, yet effective, decoding of the NB LDPC codes. The proposed decoding algorithms update, iteratively, the hard decision received vector to search for the valid codeword in the vector space of Galois field (GF){(GF)}(GF) . The selection criterion for least reliable symbol positions is based on the information from the failed checks and the reliability information from the Galois field structure as well as from the received channel soft information. To choose the correct value for the candidate symbol, two methods are used. The first method is based on the prediction of the error symbol from the set of Galois field symbols which maximize an objective function. In the second method, individual bits are flipped based on the reliability information obtained from the channel. Algorithms 1 and 2 flip a single symbol per iteration whilst the other three algorithms 3, 4 and 5 flip multiple symbols in each iteration. The proposed voting based Algorithms 1, 2 and 5 first short list the unreliable positions using a majority voting scheme and then choose the candidate symbol value from the set of the symbols in GF(q){GF(q)}GF(q) while not violating the field order q{q}q . These methods simplify the decoding complexity in terms of computation and memory. Results and analysis of these algorithms show an appealing tradeoff between computational complexity and bit error rate performance for NB LDPC codes.
We propose a multiple-voting-based joint detection-decoding algorithm for nonbinary low-density parity-check (LDPC)-coded modulation systems. This algorithm is inspired from the reliability-based JDD algorithm for nonbinary LDPC-coded modulation systems, that has been proposed recently, in which the accumulated reliability of symbols based on one-step majority-logic decoding algorithm and the Chase-like local list decoding algorithm are used. However, the reliability-based JDD algorithm still has a significant performance degradation of at least 1 dB with low column weight (dv≤4). In order to reduce the performance degradation with low column weight, the proposed algorithm allows unfixed number of variable nodes to pass two symbols to the associated check node, in contrast with the reliability-based JDD algorithm, which allows only one variable node to pass two symbols to check node, when updating variable-to-check messages. Moreover, the votes are weighted differently according to the components of the list in the check-sum computation. Simulations show that the proposed algorithm yields better performance with low column weight, while still maintaining the low complexity feature.
In this paper, we present two low complexity algorithms to decode non-binary LDPC codes. The proposed decoding algorithms update iteratively the hard decision received vector to search for a valid codeword in the vector space of Galois field (GF). The selection criterion for the position of unreliable symbols is based on failed checks and the information from the Galois field structure. In the first proposed algorithm, the flipping function is calculated for all symbols of the received sequence and multiple symbols are flipped in each iteration while in the second proposed algorithm, a single symbol is flipped per iteration. In the second method, unreliable positions are short-listed by using a majority voting scheme, and then the flipping function is computed to predict candidate symbols from the set of symbols in GF(q) while not violating the field order q. The proposed methods reduce the decoding complexity and memory use. The results of the algorithms show appealing tradeoffs between complexity and bit error rate performance for non-binary LDPC codes.
A multiple-vote symbol-flipping (MV-SF) decoding algorithm for nonbinary low-density parity-check (NB-LDPC) codes is proposed in this paper. Our algorithm improves the generalized bit-flipping algorithm (GBFDA) by considering the multiplicity of the candidates at the check-node output, to perform a more accurate symbol-flipping decision at the variable node update. The MV-SF algorithm greatly improves the frame error rate performance of GBFDA and approaches the performance of the best state-of-the-art decoders [extended min-sum and min-max (Min–Max)] with lower complexity. For a(N=837,K=723)(N=837,K=723)(N=837,K=723)NB-LDPC code over GF(32), the decoder derived from the proposed algorithm can reach a throughput higher than 500 Mb/s and a coding gain of 0.44 dB compared with the most efficient GBFDA architecture with only twice the silicon area. Our architecture has 27% efficiency gain compared with the best Min–Max architecture found in the literature, with a performance loss of just 0.21 dB at frame error rate10−410^{-4}10−4.
Based on the symbol-flipping algorithm with multiple-votes (MV-SF), this paper presents two simplified algorithms, symbol flipping with truncated and multiple votes (T-MV-SF) and symbol flipping with simplified and multiple votes (S-MV-SF), for nonbinary low-density parity-check(NB-LDPC) codes. Unlike previous symbol-flipping based algorithms (SFBAs), the T(S)-MV-SF uses the truncated voting information in each check and variable node update. The proposed algorithms also approximate the sorting function in each check update. Therefore, their complexity and memory consumption are remarkably reduced as compared with existing SFBAs. Furthermore, we introduce several parameters to compensate the information loss caused by the truncated voting information. After optimizing all the parameters, the proposed algorithms even have better performance than the MV-SF. As compared with the MV-SF, the maximum performance gain among all numerical examples is about 0.11 dB for the S-MV-SF on the (63, 37) code. The T-MV-SF has the largest reduction of the computational complexity on the (255, 175) code, which is about 80% of the complexity of the MV-SF. Moreover, the performance of the T-MV-SF is better than the MV-SF on the (255, 175) code. As a result, the proposed algorithms can effectively balance the error performance and complexity for decoding of NB-LDPCs.