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 Information Theory (ISIT)

Ternary Min-Sum Algorithm

Ting-Wei Yang, Qi-Yue Yu

Published Jun 1, 2026• 0 citations
Publisher

Abstract

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.

DOI
10.1109/isit62367.2026.11653731

Related papers

A Low-Complexity Adaptive Extended Min-Sum Algorithm for Non-Binary LDPC Codes

Minho Kim, Kyeong-Bin Park, Ki‐Seok Chung

The extended min-sum algorithm (EMS) for decoding non-binary low density parity check (NB-LDPC) codes reduces the decoding complexity by truncating the message vector by retaining only the most reliable symbols. However, the EMS algorithm does not consider that the noise of the received codeword is gradually reduced as the iteration count goes up. In this paper, we propose a low-complexity adaptive EMS algorithm, called threshold-based EMS (TB-EMS). The TB-EMS algorithm has a simple adaptive rule to calculate the new message vector length compared to the A-EMS. The proposed algorithm selects one of two message vector lengths. Experimental results show that the proposed algorithm reduces the decoding complexity with minimal performance degradation compared with the EMS algorithm. Further, the decoding performance of the TB-EMS is better than A-EMS.

International Conference on Computational Intelligence and Applications (ICCIA)•Jun 1, 2020•3 citations

A new min-sum based decoding algorithm for non-binary LDPC codes

Chung-Li Wang, Zongwang Li, Shaohua Yang

Non-binary low-density parity-check (NB-LDPC) codes are robust to various channel impairments. In this paper, we present a new decoding algorithm for the NB-LDPC decoder that is based on the q-ary min-sum algorithm (QMSA). The new one modifies the check node (CN) computations of the QMSA into two steps. By reorganizing the message entries and providing the most likely symbol, a compressed intermediate message can be easily obtained and stored, from which the check-to-variable messages can be computed with a look-up table. Thus the decoder architecture can have a straightforward design for the CN with reduced complexity and memory requirements. Besides, the simulation results demonstrate that the proposed algorithm has negligible performance loss compared to the QMSA over AWGN channel.

2012 International Conference on Computing, Networking and Communications (ICNC)•Jan 1, 2012•6 citations

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

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

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

Liyuan Song, Hanxiang Yu, Xiaosong Zhang +2 more

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.

International Conference on Wireless Communications and Signal Processing (WCSP)•Oct 24, 2024•0 citations

Reduced-complexity extended Min-sum check node processing for non-binary LDPC decoding

Xinmiao Zhang, Fang Cai

Non-binary low-density parity-check (NB-LDPC) codes can achieve higher coding gain than binary LDPC codes when the code length is moderate at the cost of higher complexity. One major step of NB-LDPC decoding is check node processing. Previously, iterative forward-backward approaches are employed to implement this step. However, the storage of the intermediate results of the forward and backward computations requires large memory. In this paper, a novel check node processing scheme and corresponding VLSI architectures are proposed for the extended Min-sum NB-LDPC decoding. The proposed scheme only stores a limited number of sorted variable-to-check messages. Then the check-to-variable messages for different variable node are generated independently. For a (837, 726) NB-LDPC code over GF(25), the proposed architecture only requires 64% of the area of the previous design with the same throughput and error-correcting performance.

IEEE International Midwest Symposium on Circuits and Systems (MWSCAS)•Aug 1, 2010•5 citations
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.
The extended min-sum algorithm (EMS) for decoding non-binary low density parity check (NB-LDPC) codes reduces the decoding complexity by truncating the message vector by retaining only the most reliable symbols. However, the EMS algorithm does not consider that the noise of the received codeword is gradually reduced as the iteration count goes up. In this paper, we propose a low-complexity adaptive EMS algorithm, called threshold-based EMS (TB-EMS). The TB-EMS algorithm has a simple adaptive rule to calculate the new message vector length compared to the A-EMS. The proposed algorithm selects one of two message vector lengths. Experimental results show that the proposed algorithm reduces the decoding complexity with minimal performance degradation compared with the EMS algorithm. Further, the decoding performance of the TB-EMS is better than A-EMS.
Non-binary low-density parity-check (NB-LDPC) codes are robust to various channel impairments. In this paper, we present a new decoding algorithm for the NB-LDPC decoder that is based on the q-ary min-sum algorithm (QMSA). The new one modifies the check node (CN) computations of the QMSA into two steps. By reorganizing the message entries and providing the most likely symbol, a compressed intermediate message can be easily obtained and stored, from which the check-to-variable messages can be computed with a look-up table. Thus the decoder architecture can have a straightforward design for the CN with reduced complexity and memory requirements. Besides, the simulation results demonstrate that the proposed algorithm has negligible performance loss compared to the QMSA over AWGN channel.
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.
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.
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.
Non-binary low-density parity-check (NB-LDPC) codes can achieve higher coding gain than binary LDPC codes when the code length is moderate at the cost of higher complexity. One major step of NB-LDPC decoding is check node processing. Previously, iterative forward-backward approaches are employed to implement this step. However, the storage of the intermediate results of the forward and backward computations requires large memory. In this paper, a novel check node processing scheme and corresponding VLSI architectures are proposed for the extended Min-sum NB-LDPC decoding. The proposed scheme only stores a limited number of sorted variable-to-check messages. Then the check-to-variable messages for different variable node are generated independently. For a (837, 726) NB-LDPC code over GF(25), the proposed architecture only requires 64% of the area of the previous design with the same throughput and error-correcting performance.