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 Communications

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

Jianyong Zhang

Published Jan 1, 2017• 5 citations
Publisher

Abstract

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.

DOI
10.1109/tcomm.2017.2719027

Related papers

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

Two Low-complexity Symbol Flipping Decoding Algorithms for Non-binary LDPC Codes

Haiqiang Chen, Yaolin Wang, Wenjuan Wei +4 more

Two low-complexity symbol flipping decoding algorithms, the Improved weighted-Algorithm B algorithm (Iwtd-AlgB) and the Truncation-based Distance-Symbol-Flipping-Decoding with Prediction (TD-SFDP) algorithm, are presented for non-binary Low Density Parity Check (LDPC) codes. For the Iwtd-AlgB algorithm, the scaling factor of the flipping metric can be replaced by the simple sums of the extrinsic information and the distance-based parameter, which can avoid the multiplication operations in the iterations and thus can reduce the decoding complexity. For the presented TD-SFDP algorithm, the variable nodes and the finite field symbols are truncated and classified based on the extrinsic information frequency and the flipping function. Only those nodes/symbols that satisfy the designed conditions can be involved in the message updating process. Simulations and numeric results show that, the presented two decoding algorithms can reduce the computational complexity at each iteration with a controllable performance degradation, thus can make efficient trade-offs between performance and complexity.

JOURNAL OF ELECTRONICS INFORMATION TECHNOLOGY•Jan 15, 2021•0 citations

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

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

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.

IEEE Communications Letters•Apr 11, 2014•36 citations

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

Symbol-flipping decoding of nonbinary LDPC codes over BI-AWGN channels

Lailson Ferreira dos Santos, Jaime Portugheis, Celso de Almeida

This paper analyzes a weighted symbol-flipping (SF) algorithm for nonbinary low density parity-check (NB-LDPC) codes over binary input AWGN (BI-AWGN) channels. The weighted SF algorithm has two main parts: the symbol-flipping function and the new candidate symbol rule. First, it is demonstrated that a rule for choosing the new candidate symbol based on absolute values of observed channel outputs is equivalent to a rule based on Euclidean distances. Then, it is verified that the weighting factor of flipping function has negligible impact on algorithm performance. Motivated by this fact, a SF decoding algorithm is proposed whose flipping function requires only syndrome values and flips symbols in parallel. It is observed that SF decoding outperforms WSF for q-ary codes with large q.

IEEE Latin-America Conference on Communications (LATINCOM)•Nov 1, 2014•1 citation

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
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.
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.
Two low-complexity symbol flipping decoding algorithms, the Improved weighted-Algorithm B algorithm (Iwtd-AlgB) and the Truncation-based Distance-Symbol-Flipping-Decoding with Prediction (TD-SFDP) algorithm, are presented for non-binary Low Density Parity Check (LDPC) codes. For the Iwtd-AlgB algorithm, the scaling factor of the flipping metric can be replaced by the simple sums of the extrinsic information and the distance-based parameter, which can avoid the multiplication operations in the iterations and thus can reduce the decoding complexity. For the presented TD-SFDP algorithm, the variable nodes and the finite field symbols are truncated and classified based on the extrinsic information frequency and the flipping function. Only those nodes/symbols that satisfy the designed conditions can be involved in the message updating process. Simulations and numeric results show that, the presented two decoding algorithms can reduce the computational complexity at each iteration with a controllable performance degradation, thus can make efficient trade-offs between performance and complexity.
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.
This paper analyzes a weighted symbol-flipping (SF) algorithm for nonbinary low density parity-check (NB-LDPC) codes over binary input AWGN (BI-AWGN) channels. The weighted SF algorithm has two main parts: the symbol-flipping function and the new candidate symbol rule. First, it is demonstrated that a rule for choosing the new candidate symbol based on absolute values of observed channel outputs is equivalent to a rule based on Euclidean distances. Then, it is verified that the weighting factor of flipping function has negligible impact on algorithm performance. Motivated by this fact, a SF decoding algorithm is proposed whose flipping function requires only syndrome values and flips symbols in parallel. It is observed that SF decoding outperforms WSF for q-ary codes with large q.
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.