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

Journal of Communications and Networks

Iterative reliability-based modified majority-logic decoding for structured binary LDPC codes

Haiqiang Chen, Lingshan Luo, Youming Sun, Xiangcheng Li, Haibin Wan, Liping Luo, Tuanfa Qin

Published Aug 1, 2015• 3 citations
Publisher

Abstract

In this paper, we present an iterative reliability-based modified majority-logic decoding algorithm for two classes of structured low-density parity-check codes. Different from the conventional modified one-step majority-logic decoding algorithms, we design a turbo-like iterative strategy to recover the performance degradation caused by the simply flipping operation. The main computational loads of the presented algorithm include only binary logic and integer operations, resulting in low decoding complexity. Furthermore, by introducing the iterative set, a very small proportion (less than 6%) of variable nodes are involved in the reliability updating process, which can further reduce the computational complexity. Simulation results show that, combined with the factor correction technique and a well-designed non-uniform quantization scheme, the presented algorithm can achieve a significant performance improvement and a fast decoding speed, even with very small quantization levels (3-4 bits resolution). The presented algorithm provides a candidate for trade-offs between performance and complexity.

DOI
10.1109/jcn.2015.000064

Related papers

Reliability-based iterative proportionality-logic decoding of LDPC codes with adaptive decision

Youming Sun, Haiqiang Chen, Xiangcheng Li +2 more

In this paper, we present a reliability-based iterative proportionality-logic decoding algorithm for two classes of structured low-density parity-check (LDPC) codes. The main contributions of this paper include: 1) Syndrome messages instead of extrinsic messages are processed and exchanged between variable nodes and check nodes, which can reduce the decoding complexity; 2) a more flexible decision mechanism is developed in which the decision threshold can be self-adjusted during the iterative process. Such decision mechanism is particularly effective for decoding the majority-logic decodable codes; 3) only part of the variable nodes satisfying the pre-designed criterion are involved for the presented algorithm, which is in the proportionality-logic sense and can further reduce the computational complexity. Simulation results show that, when combined with factor correction techniques and appropriate proportionality parameter, the presented algorithm performs well and can achieve fast decoding convergence rate while maintaining relative low decoding complexity, especially for small quantized levels (3-4 bits). The presented algorithm provides a candidate for those application scenarios where the memory load and the energy consumption are extremely constrained.

Journal of Communications and Networks•Jun 1, 2015•2 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

Comparisons Between Reliability-Based Iterative Min-Sum and Majority-Logic Decoding Algorithms for LDPC Codes

Haiqiang Chen, Kai Zhang, Xiao Ma +1 more

A modified reliability-based iterative majority-logic decoding (MRBI-MLGD) algorithm for two classes of structured LDPC codes is presented based on a recent work by Huang et al. Compared with the original one, the modified algorithm has better performance with slightly increased complexity. Then a reliability-based iterative min-sum decoding (RBI-MSD) algorithm is presented. For the presented RBI-MSD algorithm, reliability-based integer messages are processed and exchanged between variable nodes and check nodes. The main computations include only binary logical operations and integer additions. Different from the conventional min-sum algorithm, the variable nodes pass full messages rather than extrinsic messages to check nodes. This can reduce the memory loads and the computational complexity but with a little (or negligible) performance degradation. Simulation results show that, compared with the (M)RBI-MLGD algorithms, the presented RBI-MSD algorithm achieves better error performance, faster decoding convergence rate and fewer quantization bits with moderate increased computational complexity. Furthermore, the RBI-MSD algorithm is also applicable to decoding random LDPC codes, a distinct difference from the (M)RBI-MLGD algorithms. Finally, we point out that the scaling factors employed in the MRBI-MLGD algorithm and the RBI-MSD algorithm can be optimized using discretized density evolution.

IEEE Transactions on Communications•Jun 28, 2011•23 citations

Improved iterative soft-reliability-based majority-logic decoding algorithm for non-binary low-density parity-check codes

Chenrong Xiong, Zhiyuan Yan

Non-binary low-density parity-check (LDPC) codes have some advantages as opposed to their binary counterparts, but unfortunately their decoding complexity is a significant challenge. Hence, the iterative soft-reliability-based (ISRB) majority-logic decoding algorithm is attractive for non-binary LDPC codes, since it involves only finite field additions and multiplications as well as integer additions and comparisons. In this paper, we propose an improved ISRB majority-logic decoding algorithm by using a new reliability update. Our improved algorithm achieves better error performance and faster convergence, while further reducing the computational complexity. For instance, for a (16, 16)-regular (255, 175) cyclic Euclidean geometry LDPC code over GF(28), the proposed algorithm achieves a 0.15 dB coding gain and improves the convergence speed by 10% at a block error rate of 10-4versus the ISRB majority-logic decoding algorithm. Compared with the ISRB majority-logic decoding algorithm, the proposed algorithm requires the same numbers of finite field additions and multiplications but fewer integer additions and comparisons. Furthermore, the ISRB majority-logic decoding algorithm is based on the accumulation of reliability information, and hence the numerical range of the reliability information increases with iterations. In contrast, the proposed reliability update has a fixed numerical range and thus simplifies hardware implementations.

Asilomar Conference on Signals, Systems and Computers (ACSSC)•Nov 1, 2011•23 citations

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

Dynamic Check Message Majority-Logic Decoding Algorithm for Non-binary LDPC Codes

Yichao Lu, Xiao Peng, Guifen Tian +1 more

Majority-logic algorithms are devised for decoding non-binary LDPC codes in order to reduce computational complexity. However, compared with conventional belief propagation algorithms, majority-logic algorithms suffer from severe bit error performance degradation. This paper presents a low-complexity reliability-based algorithm aiming at improving error correcting ability of majority-logic algorithms. Reliability measures for check nodes are novelly introduced to realize mutual update between variable message and check message, and hence more efficient reliability propagation can be achieved, similar to belief-propagation algorithm. Simulation results on NB-LDPC codes with different characteristics demonstrate that our algorithm can reduce the bit error ratio by more than one order of magnitude and the coding gain enhancement over ISRB-MLGD can reach 0.2-2.0dB, compared with both the ISRB-MLGD and IISRB-MLGD algorithms. Moreover, simulations on typical LDPC codes show that the computational complexity of the proposed algorithm is closely equivalent to ISRB-MLGD algorithm, and is less than 10% of Min-max algorithm. As a result, the proposed algorithm achieves a more efficient trade-off between decoding computational complexity and error performance.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2014•0 citations
In this paper, we present an iterative reliability-based modified majority-logic decoding algorithm for two classes of structured low-density parity-check codes. Different from the conventional modified one-step majority-logic decoding algorithms, we design a turbo-like iterative strategy to recover the performance degradation caused by the simply flipping operation. The main computational loads of the presented algorithm include only binary logic and integer operations, resulting in low decoding complexity. Furthermore, by introducing the iterative set, a very small proportion (less than 6%) of variable nodes are involved in the reliability updating process, which can further reduce the computational complexity. Simulation results show that, combined with the factor correction technique and a well-designed non-uniform quantization scheme, the presented algorithm can achieve a significant performance improvement and a fast decoding speed, even with very small quantization levels (3-4 bits resolution). The presented algorithm provides a candidate for trade-offs between performance and complexity.
In this paper, we present a reliability-based iterative proportionality-logic decoding algorithm for two classes of structured low-density parity-check (LDPC) codes. The main contributions of this paper include: 1) Syndrome messages instead of extrinsic messages are processed and exchanged between variable nodes and check nodes, which can reduce the decoding complexity; 2) a more flexible decision mechanism is developed in which the decision threshold can be self-adjusted during the iterative process. Such decision mechanism is particularly effective for decoding the majority-logic decodable codes; 3) only part of the variable nodes satisfying the pre-designed criterion are involved for the presented algorithm, which is in the proportionality-logic sense and can further reduce the computational complexity. Simulation results show that, when combined with factor correction techniques and appropriate proportionality parameter, the presented algorithm performs well and can achieve fast decoding convergence rate while maintaining relative low decoding complexity, especially for small quantized levels (3-4 bits). The presented algorithm provides a candidate for those application scenarios where the memory load and the energy consumption are extremely constrained.
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 modified reliability-based iterative majority-logic decoding (MRBI-MLGD) algorithm for two classes of structured LDPC codes is presented based on a recent work by Huang et al. Compared with the original one, the modified algorithm has better performance with slightly increased complexity. Then a reliability-based iterative min-sum decoding (RBI-MSD) algorithm is presented. For the presented RBI-MSD algorithm, reliability-based integer messages are processed and exchanged between variable nodes and check nodes. The main computations include only binary logical operations and integer additions. Different from the conventional min-sum algorithm, the variable nodes pass full messages rather than extrinsic messages to check nodes. This can reduce the memory loads and the computational complexity but with a little (or negligible) performance degradation. Simulation results show that, compared with the (M)RBI-MLGD algorithms, the presented RBI-MSD algorithm achieves better error performance, faster decoding convergence rate and fewer quantization bits with moderate increased computational complexity. Furthermore, the RBI-MSD algorithm is also applicable to decoding random LDPC codes, a distinct difference from the (M)RBI-MLGD algorithms. Finally, we point out that the scaling factors employed in the MRBI-MLGD algorithm and the RBI-MSD algorithm can be optimized using discretized density evolution.
Non-binary low-density parity-check (LDPC) codes have some advantages as opposed to their binary counterparts, but unfortunately their decoding complexity is a significant challenge. Hence, the iterative soft-reliability-based (ISRB) majority-logic decoding algorithm is attractive for non-binary LDPC codes, since it involves only finite field additions and multiplications as well as integer additions and comparisons. In this paper, we propose an improved ISRB majority-logic decoding algorithm by using a new reliability update. Our improved algorithm achieves better error performance and faster convergence, while further reducing the computational complexity. For instance, for a (16, 16)-regular (255, 175) cyclic Euclidean geometry LDPC code over GF(28), the proposed algorithm achieves a 0.15 dB coding gain and improves the convergence speed by 10% at a block error rate of 10-4versus the ISRB majority-logic decoding algorithm. Compared with the ISRB majority-logic decoding algorithm, the proposed algorithm requires the same numbers of finite field additions and multiplications but fewer integer additions and comparisons. Furthermore, the ISRB majority-logic decoding algorithm is based on the accumulation of reliability information, and hence the numerical range of the reliability information increases with iterations. In contrast, the proposed reliability update has a fixed numerical range and thus simplifies hardware implementations.
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.
Majority-logic algorithms are devised for decoding non-binary LDPC codes in order to reduce computational complexity. However, compared with conventional belief propagation algorithms, majority-logic algorithms suffer from severe bit error performance degradation. This paper presents a low-complexity reliability-based algorithm aiming at improving error correcting ability of majority-logic algorithms. Reliability measures for check nodes are novelly introduced to realize mutual update between variable message and check message, and hence more efficient reliability propagation can be achieved, similar to belief-propagation algorithm. Simulation results on NB-LDPC codes with different characteristics demonstrate that our algorithm can reduce the bit error ratio by more than one order of magnitude and the coding gain enhancement over ISRB-MLGD can reach 0.2-2.0dB, compared with both the ISRB-MLGD and IISRB-MLGD algorithms. Moreover, simulations on typical LDPC codes show that the computational complexity of the proposed algorithm is closely equivalent to ISRB-MLGD algorithm, and is less than 10% of Min-max algorithm. As a result, the proposed algorithm achieves a more efficient trade-off between decoding computational complexity and error performance.