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

A Low Complexity Decoding Algorithm for Majority-Logic Decodable Nonbinary LDPC Codes

Dayuan Zhao, Xiao Ma, Chao Chen, Baoming Bai

Published Oct 19, 2010• 44 citations
Publisher

Abstract

In this letter, we propose a low complexity decoding algorithm for majority-logic decodable nonbinary low-density parity-check (LDPC) codes. The proposed algorithm is initialized with the quantized squared Euclidean distances between the constellation points and the received signals. Like most of the existing reliability-based decoding algorithms, the proposed algorithm requires only integer operations and finite field operations and (hence) can be implemented with simple combinational logic circuits in practical systems. Simulation results show that the proposed algorithm suffers from a little performance degradation compared with FFT-QSPA. The algorithm provides a candidate for trade-offs between performance and complexity.

DOI
10.1109/lcomm.2010.100810.101403

Related papers

Two efficient and low-complexity iterative reliability-based majority-logic decoding algorithms for LDPC codes

Qin Huang, Jingyu Kang, Li Guo Zhang +2 more

This paper presents two novel iterative reliability-based majority-logic algorithms for decoding LDPC codes. Both algorithms are binary message-passing algorithms and require only logical operations and integer additions. Consequently, they can be implemented with simple combinational logic circuits. They either outperform or perform just well as the existing weighted bit-flipping or other reliability-based decoding algorithms for LDPC codes in error performance with a faster rate of decoding convergence and less decoding complexity. Compared to the sum-product algorithm for LDPC codes, they offer effective trade-offs between performance and decoding complexity.

IEEE Information Theory Workshop (ITW)•Jan 1, 2009•11 citations

Two reliability-based iterative majority-logic decoding algorithms for LDPC codes

Qin Huang, Jaewook Kang, Li Guo Zhang +2 more

This paper presents two novel reliability-based iterative majority-logic decoding algorithms for LDPC codes. Both algorithms are binary message-passing algorithms and require only logical operations and integer additions. Consequently, they can be implemented with simple combinational logic circuits. They either outperform or perform just as well as the existing weighted bit-flipping or other reliability-based iterative decoding algorithms for LDPC codes in error performance with a faster rate of decoding convergence and less decoding complexity. Compared to the sum-product algorithm for LDPC codes, they offer effective trade-offs between performance and decoding complexity.

IEEE Transactions on Communications•Dec 1, 2009•75 citations

Improved Iterative Hard- and Soft-Reliability Based Majority-Logic Decoding Algorithms for Non-Binary Low-Density Parity-Check Codes

Chenrong Xiong, Zhiyuan Yan

Non-binary low-density parity-check (LDPC) codes have some advantages over their binary counterparts, but unfortunately their decoding complexity is a significant challenge. The iterative hard- and soft-reliability based majority-logic decoding algorithms are attractive for nonbinary LDPC codes, since they involve only finite field additions and multiplications as well as integer operations and, hence, have significantly lower complexity than other algorithms. In this paper, we propose two improvements to the majority-logic decoding algorithms. Instead of the accumulation of reliability information in the existing majority-logic decoding algorithms, our first improvement is a new reliability information update. The new update not only results in better error performance and fewer iterations on average, but also further reduces computational complexity. Since existing majority-logic decoding algorithms tend to have a high error floor for codes whose parity check matrices have low column weights, our second improvement is a reselection scheme, which leads to much lower error floors, at the expense of more finite field operations and integer operations, by identifying periodic points, reselecting intermediate hard decisions, and changing reliability information.

arXiv:1408.3357•IEEE Transactions on Signal Processing•Aug 20, 2014•24 citations

Near Optimum Majority-Logic Based Decoding of Low-Density Parity-Check Codes

Telex M. N. Ngatched, Attahiru Sule Alfa, Jun Cai

A reliability-based iterative majority-logic decoding algorithm for regular low-density parity-check (LDPC) codes was recently proposed by Huang et al. In this paper we present an improved version of that algorithm by introducing a different reliability measure for each check-sum of the parity-check matrix, and taking it into account in the computation of the extrinsic information that is used to update the reliability measure of each received bit in each iteration. Some simulations results are given, which show that the new algorithm, while requiring very little additional computational complexity, not only achieves a considerable error performance gain over the standard one, but also, importantly, outperforms the iterative decoding based on belief propagation (IDBP), especially for short and medium block length finite-geometry (FG) LDPC codes.

International Conference on Communications•Jun 1, 2011•3 citations

A symbol-reliability based message-passing decoding algorithm for nonbinary LDPC codes over finite fields

Chao Chen, Baoming Bai, Xiao Ma +1 more

Based on the idea of plurality voting, we develop a low-complexity symbol-reliability based message-passing decoding algorithm for nonbinary low-density parity-check (LDPC) codes over finite fields. A key feature of the algorithm is that the message passed in the Tanner graph is the field element with the highest reliability. This leads to a very simple check node update. The algorithm requires only finite and integer operations. Moreover, the estimation of the signal-to-noise ratio (SNR) is not needed. Compared to the Fast Fourier Transform based q-ary sum-product algorithm (FFT-QSPA), the proposed decoding algorithm provides an excellent trade-off between performance and complexity for the nonbinary LDPC codes constructed based on finite geometries, finite fields and cyclotomic cosets.

International Symposium on Turbo Codes and Iterative Information Processing•Sep 1, 2010•9 citations

Iterative Linear Programming Decoding of Nonbinary LDPC Codes With Linear Complexity

Dina Goldin, David Burshtein

The problem of low-complexity linear programming (LP) decoding of nonbinary low-density parity-check (LDPC) codes is considered, and an iterative LP decoding algorithm is presented. Results that were previously derived for binary LDPC codes are extended to the nonbinary case. Both simple and generalized nonbinary LDPC codes are considered. It is shown how the algorithm can be implemented efficiently using a finite-field fast Fourier transform. Then, the convergence rate of the algorithm is analyzed. The complexity of the algorithm scales linearly in the block length, and it can approximate, up to an arbitrarily small relative error, the objective function of the exact LP solution. When applied to a typical code from an appropriate nonbinary LDPC code ensemble, the algorithm can correct a constant fraction of errors in linear (in the block length) computational complexity. Computer experiments with the new iterative LP decoding algorithm show that, in the error floor region, it can have better performance compared to belief propagation decoding, with similar computational requirements.

IEEE Transactions on Information Theory•Aug 6, 2012•17 citations
In this letter, we propose a low complexity decoding algorithm for majority-logic decodable nonbinary low-density parity-check (LDPC) codes. The proposed algorithm is initialized with the quantized squared Euclidean distances between the constellation points and the received signals. Like most of the existing reliability-based decoding algorithms, the proposed algorithm requires only integer operations and finite field operations and (hence) can be implemented with simple combinational logic circuits in practical systems. Simulation results show that the proposed algorithm suffers from a little performance degradation compared with FFT-QSPA. The algorithm provides a candidate for trade-offs between performance and complexity.
This paper presents two novel iterative reliability-based majority-logic algorithms for decoding LDPC codes. Both algorithms are binary message-passing algorithms and require only logical operations and integer additions. Consequently, they can be implemented with simple combinational logic circuits. They either outperform or perform just well as the existing weighted bit-flipping or other reliability-based decoding algorithms for LDPC codes in error performance with a faster rate of decoding convergence and less decoding complexity. Compared to the sum-product algorithm for LDPC codes, they offer effective trade-offs between performance and decoding complexity.
This paper presents two novel reliability-based iterative majority-logic decoding algorithms for LDPC codes. Both algorithms are binary message-passing algorithms and require only logical operations and integer additions. Consequently, they can be implemented with simple combinational logic circuits. They either outperform or perform just as well as the existing weighted bit-flipping or other reliability-based iterative decoding algorithms for LDPC codes in error performance with a faster rate of decoding convergence and less decoding complexity. Compared to the sum-product algorithm for LDPC codes, they offer effective trade-offs between performance and decoding complexity.
Non-binary low-density parity-check (LDPC) codes have some advantages over their binary counterparts, but unfortunately their decoding complexity is a significant challenge. The iterative hard- and soft-reliability based majority-logic decoding algorithms are attractive for nonbinary LDPC codes, since they involve only finite field additions and multiplications as well as integer operations and, hence, have significantly lower complexity than other algorithms. In this paper, we propose two improvements to the majority-logic decoding algorithms. Instead of the accumulation of reliability information in the existing majority-logic decoding algorithms, our first improvement is a new reliability information update. The new update not only results in better error performance and fewer iterations on average, but also further reduces computational complexity. Since existing majority-logic decoding algorithms tend to have a high error floor for codes whose parity check matrices have low column weights, our second improvement is a reselection scheme, which leads to much lower error floors, at the expense of more finite field operations and integer operations, by identifying periodic points, reselecting intermediate hard decisions, and changing reliability information.
A reliability-based iterative majority-logic decoding algorithm for regular low-density parity-check (LDPC) codes was recently proposed by Huang et al. In this paper we present an improved version of that algorithm by introducing a different reliability measure for each check-sum of the parity-check matrix, and taking it into account in the computation of the extrinsic information that is used to update the reliability measure of each received bit in each iteration. Some simulations results are given, which show that the new algorithm, while requiring very little additional computational complexity, not only achieves a considerable error performance gain over the standard one, but also, importantly, outperforms the iterative decoding based on belief propagation (IDBP), especially for short and medium block length finite-geometry (FG) LDPC codes.
Based on the idea of plurality voting, we develop a low-complexity symbol-reliability based message-passing decoding algorithm for nonbinary low-density parity-check (LDPC) codes over finite fields. A key feature of the algorithm is that the message passed in the Tanner graph is the field element with the highest reliability. This leads to a very simple check node update. The algorithm requires only finite and integer operations. Moreover, the estimation of the signal-to-noise ratio (SNR) is not needed. Compared to the Fast Fourier Transform based q-ary sum-product algorithm (FFT-QSPA), the proposed decoding algorithm provides an excellent trade-off between performance and complexity for the nonbinary LDPC codes constructed based on finite geometries, finite fields and cyclotomic cosets.
The problem of low-complexity linear programming (LP) decoding of nonbinary low-density parity-check (LDPC) codes is considered, and an iterative LP decoding algorithm is presented. Results that were previously derived for binary LDPC codes are extended to the nonbinary case. Both simple and generalized nonbinary LDPC codes are considered. It is shown how the algorithm can be implemented efficiently using a finite-field fast Fourier transform. Then, the convergence rate of the algorithm is analyzed. The complexity of the algorithm scales linearly in the block length, and it can approximate, up to an arbitrarily small relative error, the objective function of the exact LP solution. When applied to a typical code from an appropriate nonbinary LDPC code ensemble, the algorithm can correct a constant fraction of errors in linear (in the block length) computational complexity. Computer experiments with the new iterative LP decoding algorithm show that, in the error floor region, it can have better performance compared to belief propagation decoding, with similar computational requirements.