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 Symposium on Information Theory and its Applications

Modified min-sum algorithm with threshold filtering for nonbinary LDPC codes over GF(q)

Yue Liu, Jun Ning, Jinhong Yuan

Published Dec 1, 2008• 2 citations
Publisher

Abstract

In this paper, we propose a scheme to reduce the computation complexity of min-sum (MS) algorithm for decoding of nonbinary low-density parity-check (LDPC) codes over GF(q). Previously, MS algorithm reduced the decoding complexity by lowering the size of the configuration set for each variable node through a sorting. In the proposed scheme, we modify the MS algorithm by minimizing the size of the configuration set for each variable node through a filtering. In the filtering, the reduction of the set size can be controlled by a preset threshold. This way we can reduce the complexity more efficiently. Simulation results show, compared to the previous EMS algorithm, the complexity of proposed scheme is reduced with a negligible degradation in the code performance.

DOI
10.1109/isita.2008.4895537

Related papers

Nonbinary LDPC decoding by min-sum with Adaptive Message Control

Weiguo Tang, Jie Huang, Lei Wang +1 more

A new decoding algorithm, referred to as Min-Sum with Adaptive Message Control (AMC-MS), is proposed to reduce the decoding complexity of nonbinary LDPC codes. The proposed algorithm adaptively trims the message length of belief information to reduce the amount of arithmetic operations. Exploiting the fact that during the decoding iteration, the distribution of belief information will become more concentrated around the correct element in the case of convergence, the messages can be truncated accordingly by considering only a few entries with large likelihood. Simulation results with a GF(16) nonbinary LDPC code indicate that the proposed approach can reduce arithmetic operations by up to 65% compared with non-truncated cases. Compared with the state-of-the-art extended MS (EMS) decoding, the proposed AMC-MS algorithm can reduce the computation by up to 50%, thereby enabling low-complexity decoding of nonbinary LDPC codes.

IEEE International Conference on Acoustics Speech and Signal Processing•May 1, 2011•8 citations

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

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

A Variant of the EMS Decoding Algorithm for Nonbinary LDPC Codes

Shancheng Zhao, Zhifei Lu, Xiao Ma +1 more

This letter is concerned with low-complexity decoding algorithms for nonbinary low-density parity-check (NB-LDPC) codes. A new truncation rule based on an adaptive threshold μ is proposed for the extended min-sum (EMS) algorithm. The threshold μ is determined by the mean of the message vector. Therefore, it can be matched to channel observation and decoding iteration. The resulting algorithm is referred to as μ-EMS algorithm. Simulation results show that the μ-EMS algorithm performs almost as well as the Q-ary sum-product algorithm (QSPA). Simulation results also show that the μ-EMS algorithm is simpler than the other X-EMS algorithms for NB-LDPC over high order finite fields.

IEEE Communications Letters•Jul 16, 2013•24 citations

Improved Extended Min-sum Decoding Algorithm of LDPC Codes over GF(q)

Ba Xu, Zhongming Zhang, Ying-liang He +1 more

To overcome the drawback of the extended min-sum algorithm(EMS),an improved EMS decoding algorithm is proposed,which is designed for LDPC over GF(q).The algorithm adaptively chooses the rank of FHT in each iteration step according to the average variance of bit nodes' probability pairs.It differs from the original EMS algorithm in which the rank of FHT for each iteration step is a constant.Moreover,for oscillating variable nodes,the message of the previous iteration is added to the current message in the iterative procedure to reduce loss of performance and effects of oscillation.Experimental results show that the proposed algorithm can achieve better performance and converge faster than EMS with the same decoding complexity.

•Jan 1, 2010•0 citations

Decoding Algorithms for Nonbinary LDPC Codes Over GF$(q)$

David Declercq, M.P.C. Fossorier

In this letter, we address the problem of decoding nonbinary low-density parity-check (LDPC) codes over finite fields GF(q), with reasonable complexity and good performance. In the first part of the letter, we recall the original belief propagation (BP) decoding algorithm and its Fourier domain implementation. We show that the use of tensor notations for the messages is very convenient for the algorithm description and understanding. In the second part of the letter, we introduce a simplified decoder which is inspired by the min-sum decoder for binary LDPC codes. We called this decoder extended min-sum (EMS). We show that it is possible to greatly reduce the computational complexity of the check-node processing by computing approximate reliability measures with a limited number of values in a message. By choosing appropriate correction factors or offsets, we show that the EMS decoder performance is quite good, and in some cases better than the regular BP decoder. The optimal values of the factor and offset correction are obtained asymptotically with simulated density evolution. Our simulations on ultra-sparse codes over very-high-order fields show that nonbinary LDPC codes are promising for applications which require low frame-error rates for small or moderate codeword lengths. The EMS decoder is a good candidate for practical hardware implementations of such codes

IEEE Transactions on Communications•Apr 1, 2007•724 citations
In this paper, we propose a scheme to reduce the computation complexity of min-sum (MS) algorithm for decoding of nonbinary low-density parity-check (LDPC) codes over GF(q). Previously, MS algorithm reduced the decoding complexity by lowering the size of the configuration set for each variable node through a sorting. In the proposed scheme, we modify the MS algorithm by minimizing the size of the configuration set for each variable node through a filtering. In the filtering, the reduction of the set size can be controlled by a preset threshold. This way we can reduce the complexity more efficiently. Simulation results show, compared to the previous EMS algorithm, the complexity of proposed scheme is reduced with a negligible degradation in the code performance.
A new decoding algorithm, referred to as Min-Sum with Adaptive Message Control (AMC-MS), is proposed to reduce the decoding complexity of nonbinary LDPC codes. The proposed algorithm adaptively trims the message length of belief information to reduce the amount of arithmetic operations. Exploiting the fact that during the decoding iteration, the distribution of belief information will become more concentrated around the correct element in the case of convergence, the messages can be truncated accordingly by considering only a few entries with large likelihood. Simulation results with a GF(16) nonbinary LDPC code indicate that the proposed approach can reduce arithmetic operations by up to 65% compared with non-truncated cases. Compared with the state-of-the-art extended MS (EMS) decoding, the proposed AMC-MS algorithm can reduce the computation by up to 50%, thereby enabling low-complexity decoding of nonbinary LDPC codes.
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.
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.
This letter is concerned with low-complexity decoding algorithms for nonbinary low-density parity-check (NB-LDPC) codes. A new truncation rule based on an adaptive threshold μ is proposed for the extended min-sum (EMS) algorithm. The threshold μ is determined by the mean of the message vector. Therefore, it can be matched to channel observation and decoding iteration. The resulting algorithm is referred to as μ-EMS algorithm. Simulation results show that the μ-EMS algorithm performs almost as well as the Q-ary sum-product algorithm (QSPA). Simulation results also show that the μ-EMS algorithm is simpler than the other X-EMS algorithms for NB-LDPC over high order finite fields.
To overcome the drawback of the extended min-sum algorithm(EMS),an improved EMS decoding algorithm is proposed,which is designed for LDPC over GF(q).The algorithm adaptively chooses the rank of FHT in each iteration step according to the average variance of bit nodes' probability pairs.It differs from the original EMS algorithm in which the rank of FHT for each iteration step is a constant.Moreover,for oscillating variable nodes,the message of the previous iteration is added to the current message in the iterative procedure to reduce loss of performance and effects of oscillation.Experimental results show that the proposed algorithm can achieve better performance and converge faster than EMS with the same decoding complexity.
Decoding Algorithms for Nonbinary LDPC Codes Over GF(q)(q)(q)
In this letter, we address the problem of decoding nonbinary low-density parity-check (LDPC) codes over finite fields GF(q), with reasonable complexity and good performance. In the first part of the letter, we recall the original belief propagation (BP) decoding algorithm and its Fourier domain implementation. We show that the use of tensor notations for the messages is very convenient for the algorithm description and understanding. In the second part of the letter, we introduce a simplified decoder which is inspired by the min-sum decoder for binary LDPC codes. We called this decoder extended min-sum (EMS). We show that it is possible to greatly reduce the computational complexity of the check-node processing by computing approximate reliability measures with a limited number of values in a message. By choosing appropriate correction factors or offsets, we show that the EMS decoder performance is quite good, and in some cases better than the regular BP decoder. The optimal values of the factor and offset correction are obtained asymptotically with simulated density evolution. Our simulations on ultra-sparse codes over very-high-order fields show that nonbinary LDPC codes are promising for applications which require low frame-error rates for small or moderate codeword lengths. The EMS decoder is a good candidate for practical hardware implementations of such codes