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 Wireless Communications and Signal Processing (WCSP)

Pruning Path Min-Sum Decoding Algorithm for High-Rate Non-Binary LDPC Codes

Liyuan Song, Hanxiang Yu, Xiaosong Zhang, Ruoyang Qi, Yi Wu

Published Oct 24, 2024• 0 citations
Publisher

Abstract

The fixed path Min-Sum (FMS) algorithm efficiently decodes non-binary LDPC codes with low/moderate code rates, but suffers significant performance degradation for high code rates. This paper enhances its check node (CN) update by selecting deviation paths of high reliability according to their correct probabilities and positions over the trellis of a CN. Moreover, a path pruning strategy is introduced during the CN update to reduce the complexity of path search. Analysis results indicate that the proposed pruning path Min-Sum (PMS) algorithm efficiently decodes high-rate non-binary LDPC codes.

DOI
10.1109/wcsp62071.2024.10827053

Related papers

Set Message-Passing Decoding Algorithms for Regular Non-Binary LDPC Codes

Qin Huang, Liyuan Song, Zulin Wang

In the check node (CN) update of non-binary message-passing algorithms, each element of reliability vectors takes the same computational complexity. However, our analysis indicates that various elements in the same vector have various correct probabilities, thus have different contributions to error performance. In order to match computational complexity with correct probability, all elements in a vector are partitioned into different sets. For the extended min-sum (EMS) decoding, various strategies are applied for sets according to their correct probability. For the trellis-based EMS decoding, it is interesting that set partition only involves fixed paths, thus it does not need to search over the whole trellis of a CN. Complexity analysis and simulation results show that the proposed algorithms efficiently decode non-binary low-density parity-check codes, including ultra-sparse ones.

IEEE Transactions on Communications•Aug 28, 2017•19 citations

Set min-sum decoding algorithm for non-binary LDPC codes

Liyuan Song, Qin Huang, Zulin Wang

This paper reduces the complexity of decoding non-binary low-density parity-check (LDPC) codes by set partition. In the check node update, the input vectors are partitioned into several sets such that different elements in the virtual matrix enjoy various computational strategies. As a result, the proposed algorithm achieves high computational efficiency by setting strategies according to the correct probability of these elements. Simulation results indicate that it significantly decreases the complexity of check node update with negligible performance loss.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•8 citations

Ternary Min-Sum Algorithm

Ting-Wei Yang, Qi-Yue Yu

Ternary low-density parity-check (LDPC) codes over GF(3) are an appealing non-binary option for transmission with high bandwidth efficiency, but iterative decoding is often dominated by computationally intensive check node (CN) processing. This paper proposes a ternary min-sum (TMS) decoder by deriving an explicit low-complexity CN update that avoids trellis-based forward-backward dynamic programming (DP). Under the min-sum approximation, we apply an a posteriori probability (APP)-centered normalization and reformulate the CN update as a reduced-dimensional kernel minimization. We then prove that the minimizing relative-symbol vector can always be chosen to have Hamming weight at most two. This leads to a DP-free CN update that uses only comparisons and additions, with complexity that scales linearly with the CN degree. Compared to the extended min-sum (EMS) with selection size ne=2, simulation results show that the proposed TMS outperforms EMS by about 0.35 dB at BER near 10−5, and reduces the simulated CN complexity by 85.2% for the considered ternary LDPC code.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2026•0 citations

Minimum-Set Min-Sum Decoding Algorithms for Non-Binary LDPC Codes

Zhanxian Liu, Haijun Zhang, Jiahao Huo +1 more

During the check node (CN) update, the elements of input message vectors are redundant for the output message vectors. Hence, in this paper, we exactly select from the input message vectors the elements, which really have contributions to the error-correction performance and constitute the minimum set for the CN update. With adoption of the forward and backward (FB) scheme, an adaptive minimum-set min-sum algorithm (AMSA) is proposed to reduce the computation complexity of the FB process. In order to concurrently update the output vectors belonging to the same CN, we present a parallel minimum-set min-sum algorithm (PMSA) with lower memory complexity than the AMSA. Compared with the min-sum algorithms, the two proposed minimum-set based algorithms introduce no error performance loss.

IEEE Transactions on Communications•Aug 27, 2024•1 citation

An Improved Self-Corrected Min-Sum Decoding for LDPC Codes

Xingjin Li, Liguo Zhang, Jingxuan Tan +3 more

Low-Density Parity-Check (LDPC) code is a linear block code approaching the Shannon limit. The improvement of the decoding performance of LDPC codes is a hot research direction today. To improve the decoding performance of the self-correcting min-sum (SCMS) algorithm, an improved self-correcting min-sum (ISCMS) algorithm is proposed based on this algorithm. In the iterative decoding process of the ISCMS algorithm, the update rule of the check node (CN) is optimized to the update rule of the CN of the IOMS algorithm, which improves the accuracy of decoding from the processing of the CN. Simulation results show that the proposed ISCMS algorithm has better error performance and convergence performance than the SCMS algorithm with a small increase in computational complexity.

International Conference on Intelligent Systems and Knowledge Engineering (ISKE)•Nov 26, 2021•0 citations

Adaptive Extended Min-Sum Algorithm for Nonbinary LDPC Decoding

Xuan Guan, Yunsi Fei

Low Density Parity Check (LDPC) codes over a Galois Field GF(q) can provide significantly better error- correcting quality than binary LDPC codes with moderate code length. However, the computational complexity and memory requirement of nonbinary codes are much higher, limiting the application of non- binary LDPC codes. In this paper, we propose an adaptive message truncation algorithm for non-binary LDPC decoding, guided by the estimated code error rates. Compared to the previous fixed message truncation method, it can cut the messages adaptively, and therefore provide better decoding quality and computation complexity reduction. To further reduce the computation, we propose another adaptive check node update algorithm, simplifying the decoding by reducing the number of check nodes updating. Our simulation results demonstrate that by combining these two algorithms together, the average message size can be reduced greatly and good decoding quality is achieved, at a little cost of iterations. Compared to the existing truncation algorithms, our approach can reduce the order of complexity to O(nalog2(na)) (where nais messages size), with less performance degradation.

Globecom•Dec 1, 2011•7 citations
The fixed path Min-Sum (FMS) algorithm efficiently decodes non-binary LDPC codes with low/moderate code rates, but suffers significant performance degradation for high code rates. This paper enhances its check node (CN) update by selecting deviation paths of high reliability according to their correct probabilities and positions over the trellis of a CN. Moreover, a path pruning strategy is introduced during the CN update to reduce the complexity of path search. Analysis results indicate that the proposed pruning path Min-Sum (PMS) algorithm efficiently decodes high-rate non-binary LDPC codes.
In the check node (CN) update of non-binary message-passing algorithms, each element of reliability vectors takes the same computational complexity. However, our analysis indicates that various elements in the same vector have various correct probabilities, thus have different contributions to error performance. In order to match computational complexity with correct probability, all elements in a vector are partitioned into different sets. For the extended min-sum (EMS) decoding, various strategies are applied for sets according to their correct probability. For the trellis-based EMS decoding, it is interesting that set partition only involves fixed paths, thus it does not need to search over the whole trellis of a CN. Complexity analysis and simulation results show that the proposed algorithms efficiently decode non-binary low-density parity-check codes, including ultra-sparse ones.
This paper reduces the complexity of decoding non-binary low-density parity-check (LDPC) codes by set partition. In the check node update, the input vectors are partitioned into several sets such that different elements in the virtual matrix enjoy various computational strategies. As a result, the proposed algorithm achieves high computational efficiency by setting strategies according to the correct probability of these elements. Simulation results indicate that it significantly decreases the complexity of check node update with negligible performance loss.
Ternary low-density parity-check (LDPC) codes over GF(3) are an appealing non-binary option for transmission with high bandwidth efficiency, but iterative decoding is often dominated by computationally intensive check node (CN) processing. This paper proposes a ternary min-sum (TMS) decoder by deriving an explicit low-complexity CN update that avoids trellis-based forward-backward dynamic programming (DP). Under the min-sum approximation, we apply an a posteriori probability (APP)-centered normalization and reformulate the CN update as a reduced-dimensional kernel minimization. We then prove that the minimizing relative-symbol vector can always be chosen to have Hamming weight at most two. This leads to a DP-free CN update that uses only comparisons and additions, with complexity that scales linearly with the CN degree. Compared to the extended min-sum (EMS) with selection size ne=2, simulation results show that the proposed TMS outperforms EMS by about 0.35 dB at BER near 10−5, and reduces the simulated CN complexity by 85.2% for the considered ternary LDPC code.
During the check node (CN) update, the elements of input message vectors are redundant for the output message vectors. Hence, in this paper, we exactly select from the input message vectors the elements, which really have contributions to the error-correction performance and constitute the minimum set for the CN update. With adoption of the forward and backward (FB) scheme, an adaptive minimum-set min-sum algorithm (AMSA) is proposed to reduce the computation complexity of the FB process. In order to concurrently update the output vectors belonging to the same CN, we present a parallel minimum-set min-sum algorithm (PMSA) with lower memory complexity than the AMSA. Compared with the min-sum algorithms, the two proposed minimum-set based algorithms introduce no error performance loss.
Low-Density Parity-Check (LDPC) code is a linear block code approaching the Shannon limit. The improvement of the decoding performance of LDPC codes is a hot research direction today. To improve the decoding performance of the self-correcting min-sum (SCMS) algorithm, an improved self-correcting min-sum (ISCMS) algorithm is proposed based on this algorithm. In the iterative decoding process of the ISCMS algorithm, the update rule of the check node (CN) is optimized to the update rule of the CN of the IOMS algorithm, which improves the accuracy of decoding from the processing of the CN. Simulation results show that the proposed ISCMS algorithm has better error performance and convergence performance than the SCMS algorithm with a small increase in computational complexity.
Low Density Parity Check (LDPC) codes over a Galois Field GF(q) can provide significantly better error- correcting quality than binary LDPC codes with moderate code length. However, the computational complexity and memory requirement of nonbinary codes are much higher, limiting the application of non- binary LDPC codes. In this paper, we propose an adaptive message truncation algorithm for non-binary LDPC decoding, guided by the estimated code error rates. Compared to the previous fixed message truncation method, it can cut the messages adaptively, and therefore provide better decoding quality and computation complexity reduction. To further reduce the computation, we propose another adaptive check node update algorithm, simplifying the decoding by reducing the number of check nodes updating. Our simulation results demonstrate that by combining these two algorithms together, the average message size can be reduced greatly and good decoding quality is achieved, at a little cost of iterations. Compared to the existing truncation algorithms, our approach can reduce the order of complexity to O(nalog2(na)) (where nais messages size), with less performance degradation.