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 International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC)

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

Waheed Ullah, Ling Cheng, Fambirai Takawira

Published Aug 1, 2020• 5 citations
Publisher

Abstract

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.

DOI
10.1109/pimrc48278.2020.9217108

Related papers

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

Majority decision based weighted symbol-flipping decoding for nonbinary LDPC codes

Bing Liu, Jun Gao, Gaoqi Dou +1 more

A new low-complexity symbol-flipping algorithm based on majority decision to decode nonbinary low-density parity-check (LDPC) codes is proposed. The decoding procedure updates iteratively the hard-decision received symbol vector in search of a valid codeword in the symbol vector space. Only one symbol is changed in each iteration, and symbol flipping function combines the number of failed checks and reliability of the received bits and calculated symbols. Flipped symbol position is determined by majority decision and flipped value is calculated by channel output. And an optional mechanism to avoid infinite loops in high Galois field search is also proposed. Our studies show that the algorithm achieves an appealing tradeoff between performance and complexity over relatively low Galois field for short to medium code length.

International Conference on Future Computer and Communication•Jan 1, 2010•4 citations

Weighted Symbol-Flipping Decoding for Nonbinary LDPC Codes

Bing Liu, Jun Gao, Gaoqi Dou +1 more

In this paper, a new low-complexity symbol-flipping algorithm to decode nonbinary low-density parity-check (LDPC) codes is proposed. The decoding procedure updates iteratively the hard-decision received symbol vector in search of a valid codeword in the symbol vector space. Only one symbol is changed in each iteration, and symbol flipping function combines the number of failed checks and reliability of the received bits and calculated symbols. An optional mechanism to avoid infinite loops in high Galois field search is also proposed. Our studies show that the algorithm achieves an appealing tradeoff between performance and complexity over relatively low Galois field for short to medium code length.

International Conference on Networks Security, Wireless Communications and Trusted Computing (NSWCTC)•Jan 1, 2010•25 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

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

Bit-Reliability Based Low-Complexity Decoding Algorithms for Non-Binary LDPC Codes

Qin Huang, Mu Zhang, Zulin Wang +1 more

This paper presents bit-reliability based majority-logic decoding (MLgD) algorithms for non-binary LDPC codes. The proposed algorithms pass only one Galois field element and its reliability along each edge of the Tanner graph of a non-binary LDPC code. Since their reliability updates are in terms of bits rather than symbols, they are more efficient than traditional MLgD based decoding algorithms. By weighting the soft reliability of the extrinsic information-sums based on their hard reliability, the proposed algorithms can achieve good error performance for non-binary LDPC codes with various column weights. Moreover, their computational complexity and memory consumption are remarkably reduced compared with existing MLgD based decoding algorithms. As a result, they provide effective tradeoffs between error performance and complexity for decoding of non-binary LDPC codes.

IEEE Transactions on Communications•Nov 12, 2014•36 citations
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.
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.
A new low-complexity symbol-flipping algorithm based on majority decision to decode nonbinary low-density parity-check (LDPC) codes is proposed. The decoding procedure updates iteratively the hard-decision received symbol vector in search of a valid codeword in the symbol vector space. Only one symbol is changed in each iteration, and symbol flipping function combines the number of failed checks and reliability of the received bits and calculated symbols. Flipped symbol position is determined by majority decision and flipped value is calculated by channel output. And an optional mechanism to avoid infinite loops in high Galois field search is also proposed. Our studies show that the algorithm achieves an appealing tradeoff between performance and complexity over relatively low Galois field for short to medium code length.
In this paper, a new low-complexity symbol-flipping algorithm to decode nonbinary low-density parity-check (LDPC) codes is proposed. The decoding procedure updates iteratively the hard-decision received symbol vector in search of a valid codeword in the symbol vector space. Only one symbol is changed in each iteration, and symbol flipping function combines the number of failed checks and reliability of the received bits and calculated symbols. An optional mechanism to avoid infinite loops in high Galois field search is also proposed. Our studies show that the algorithm achieves an appealing tradeoff between performance and complexity over relatively low Galois field for short to medium code length.
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.
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.
This paper presents bit-reliability based majority-logic decoding (MLgD) algorithms for non-binary LDPC codes. The proposed algorithms pass only one Galois field element and its reliability along each edge of the Tanner graph of a non-binary LDPC code. Since their reliability updates are in terms of bits rather than symbols, they are more efficient than traditional MLgD based decoding algorithms. By weighting the soft reliability of the extrinsic information-sums based on their hard reliability, the proposed algorithms can achieve good error performance for non-binary LDPC codes with various column weights. Moreover, their computational complexity and memory consumption are remarkably reduced compared with existing MLgD based decoding algorithms. As a result, they provide effective tradeoffs between error performance and complexity for decoding of non-binary LDPC codes.