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

International Conference on Future Computer and Communication

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

Bing Liu, Jun Gao, Gaoqi Dou, Wei Tao

Published Jan 1, 2010• 4 citations
Publisher

Abstract

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.

DOI
10.1109/icfcc.2010.5497659

Related papers

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

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

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

Hybrid weighted bit-flipping decoding algorithm for LDPC codes

Gaoqi Dou

To reduce loop-oscillation errors occurring in the weighted bit-flipping algorithm,a hybrid weighted bit-flipping decoding algorithm for low-density parity-check(LDPC) codes is proposed.The proposed algorithm updates multiple bits in each iteration,a random perturbation is added when the loop oscillation is detected which could reduce loop-oscillation errors by changing objective function.And these errors are analyzed from the mathematic perspective.Simulation results and complexity comparison show that the proposed algorithm achieves an appealing tradeoff among performance,convergence and complexity for structured LDPC codes compared with the best known weighted bit-flipping decoding algorithm.

Systems engineering and electronics•Jan 1, 2010•1 citation

Improved Bit-Flipping Method for Decoding Structured Low-Density Parity-Check Codes

Meiling Zhang

An improved bit-flipping(BF) algorithm with low complexity for decoding structured low-density parity-check codes(LDPC) is proposed to improve the performance of the hard-decision BF algorithm.The hard-decision bits are divided into two groups based on the magnitudes of the received symbols,and at each iteration,the proposed algorithm can flip more than one bit with using two thresholds,and the flipping error probability is effectively decreased.The improved BF algorithm requires some real number comparisons before iterations and requires only logical operations during the iterations.Compared with the weighted bit-flipping algorithm and its modifications,the new method is with significantly lower complexity.Simulations show that the proposed algorithm is provided with very fast convergence speed and excellent performance with significantly low complexity.

Beijing Youdian Xueyuan xuebao•Jan 1, 2012•0 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
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 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.
To reduce loop-oscillation errors occurring in the weighted bit-flipping algorithm,a hybrid weighted bit-flipping decoding algorithm for low-density parity-check(LDPC) codes is proposed.The proposed algorithm updates multiple bits in each iteration,a random perturbation is added when the loop oscillation is detected which could reduce loop-oscillation errors by changing objective function.And these errors are analyzed from the mathematic perspective.Simulation results and complexity comparison show that the proposed algorithm achieves an appealing tradeoff among performance,convergence and complexity for structured LDPC codes compared with the best known weighted bit-flipping decoding algorithm.
An improved bit-flipping(BF) algorithm with low complexity for decoding structured low-density parity-check codes(LDPC) is proposed to improve the performance of the hard-decision BF algorithm.The hard-decision bits are divided into two groups based on the magnitudes of the received symbols,and at each iteration,the proposed algorithm can flip more than one bit with using two thresholds,and the flipping error probability is effectively decreased.The improved BF algorithm requires some real number comparisons before iterations and requires only logical operations during the iterations.Compared with the weighted bit-flipping algorithm and its modifications,the new method is with significantly lower complexity.Simulations show that the proposed algorithm is provided with very fast convergence speed and excellent performance with significantly low complexity.
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.