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 Communication Networks and Machine Learning (CNML)

Low-Computational Algorithm for Check Node Processing in Non-Binary LDPC Decoders

Shengjun Xiong, Lisheng Zhou, Yuxin Xiong, Dong Li

Published Feb 21, 2025• 0 citations
Publisher

Abstract

This paper presents a low-computational algorithm for the check node processing of non-binary low-density parity-check (NB-LPDC) decoders, the base algorithm that we use is the extended min-sum (EMS) algorithm, which has been widely studied in the recent literature, and has been shown to approach the performance of the belief propagation algorithm, with limited complexity. This algorithm, named novel bubble check, can reduce greatly the number of bubbles to be compared, this significant computational reduction is achieved without any performance loss. This algorithm is particularly suitable for NB-LPDC decoders in super-high order fields, which have superior performance in the presence of burst errors.

DOI
10.1145/3728199.3728255

Related papers

Bubble check: a simplified algorithm for elementary check node processing in extended min-sum non-binary LDPC decoders

Emmanuel Boutillon, Laura Conde-Canencia

A simplified algorithm for the check node processing of extended min-sum non-binary LDPC decoders is proposed. This novel technique, named bubble check, can reduce the number of compare operations by a factor of three at the elementary check node level. As this significant complexity reduction is achieved without any performance loss, this technique becomes highly attractive for hardware implementation.

Electronics Letters•Apr 29, 2010•72 citations

A Low-Complexity EMS Algorithm with Dynamic Message Truncation for Non-Binary LDPC Codes

Fulong Wang, Ming Zhan, Qian Zhang +4 more

The extended min-sum (EMS) algorithm is adopted for non-binary low density parity check (NB-LDPC) codes. The high complexity of EMS algorithm is a hot topic in recent years. Aiming at the problem, a low-complexity EMS algorithm based on NB-LDPC codes is proposed. Dynamic bubble-check (DBC) algorithm in elementary check node (ECN) steps is adopted to reduce the complexity of check node. Furthermore, the proposed algorithm dynamically truncates the length of the message vector by the number of decoding iterations. Taking the length of message vector truncated again as half of the original one as an example, the simulation results and complexity are analyzed. Analysis shows that, compared to the EMS algorithm, computational complexity of comparisons and real additions of check node of the proposed algorithm have reduced by about 70% and 25% respectively. Meantime, the decoding performance of the proposed algorithm approach that of EMS algorithm and the loss is only near 0.08 dB when the bit error rate (BER) is 10−3and the Galois field$GF(q)(q=16)$.

•Oct 14, 2021•0 citations

Non-binary LDPC decoder architectures

Zhang Xinmiao

This chapter reviews nonbinary low–density parity–check (NB–LDPC) decoder architectures, with emphasis given to algorithmic and architectural modification techniques for the check node units. The belief propagation (BP) for binary low-density parity-check decoding can be extended to decode NB–LDPC codes. In non–binary BP, the check node processing also computes sums of products of probabilities. The computations in non–binary check node processing can be considered as convolutions of the incoming messages. Multiplications in probability domain are implemented as additions in log domain. The most prominent ones are the extended Minsum algorithm and the Min–max algorithm. Both of them are log-domain algorithms. The approximations lead to slight performance loss compared to the BP, the hardware complexity has been greatly reduced in these algorithms, and only additions on the reliability messages are involved in their check node processing. The number of multiplications in the check node processing is reduced in the frequency–domain approach.

CRC Press eBooks•Jun 29, 2015•0 citations

Improved Extended Min-Sum Algorithm for Non-Binary LDPC Codes Based on Node Reliability

Yibing Li, Sitong Zhang, Fang Ye +3 more

Low Density Parity Check (LDPC) codes have been widely applied in recent years, and Extended Min-Sum (EMS) decoding algorithm is the most practical algorithm, which has a fairly low computational cost. Due to the great loss in error correction performance of EMS algorithm, in this paper, we establish constraints to obtain reliable nodes while decoding and evaluate the reliability of the nodes. The nodes and information transferred between nodes are processed and optimized according to the reliability of the nodes. High reliability nodes will not be updated in the decoding process while the information of the sub-reliability nodes will be optimized in different situations, thereby improving the decoding accuracy. This algorithm can accelerate the convergence of the algorithm, while the reduced number of update nodes can control the increase of the computation to a certain extent, and maintain the advantage of the low computation quantity of EMS algorithm. Through simulation results and computational analysis, we prove that the improved algorithm has significantly improved error correction performance compared with the traditional EMS algorithm. Under the same conditions, it has completely entered the waterfall area at 3.6dB, and the EMS algorithm has not entered the waterfall area. By comparing the average iteration times of decoding of the two algorithms, the convergence speed of the algorithm can be reflected. Compared with EMS algorithm, the improved algorithm has significantly improved the convergence speed in most areas, which indicates that the processing of sub-reliable nodes accelerates the convergence of the algorithm. Finally, the average update times of the check nodes and variable nodes of the two algorithms are compared respectively. Although the improved algorithm introduces extra processing flow, it speeds up the convergence of the algorithm, and the computational cost of decoding is less expensive.

IEEE-APS Topical Conference on Antennas and Propagation in Wireless Communications (APWC)•Sep 1, 2019•0 citations

Selection-based Low-cost Check Node Operation for Extended Min-Sum Algorithm

Kyeong-Bin Park, Ki‐Seok Chung

Although non-binary low-density parity-check (NB-LDPC) codes have better error-correction capability than that of binary LDPC codes, their decoding complexity is significantly higher.Therefore, it is crucial to reduce the decoding complexity of NB-LDPC while maintaining their error-correction capability to adopt them for various applications.The extended min-sum (EMS) algorithm is widely used for decoding NB-LDPC codes, and it reduces the complexity of check node (CN) operations via message truncation.Herein, we propose a low-cost CN processing method to reduce the complexity of CN operations, which take most of the decoding time.Unlike existing studies on low complexity CN operations, the proposed method employs quick selection algorithm, thereby reducing the hardware complexity and CN operation time.The experimental results show that the proposed selection-based CN operation is more than three times faster and achieves better error-correction performance than the conventional EMS algorithm.

KSII Transactions on Internet and Information Systems•Feb 28, 2021•0 citations

Dynamic Bubble-Check Algorithm for Check Node Processing in Q-Ary LDPC Decoders

Wei Lin, Baoming Bai, Xiao Ma +1 more

A simplified algorithm for check node processing of extended min-sum (EMS) q-ary LDPC decoders is presented in this letter. Compared with the bubble check algorithm, the so-called dynamic bubble-check (DBC) algorithm aims to further reduce the computational complexity for the elementary check node (ECN) processing. By introducing two flag vectors in ECN processing, The DBC algorithm can use the minimum number of comparisons at each step. Simulation results show that, DBC algorithm uses significantly fewer comparison operations than the bubble check algorithm, and presents no performance loss compared with standard EMS algorithm on AWGN channels.

IEICE Transactions on Communications•Jan 1, 2012•1 citation
This paper presents a low-computational algorithm for the check node processing of non-binary low-density parity-check (NB-LPDC) decoders, the base algorithm that we use is the extended min-sum (EMS) algorithm, which has been widely studied in the recent literature, and has been shown to approach the performance of the belief propagation algorithm, with limited complexity. This algorithm, named novel bubble check, can reduce greatly the number of bubbles to be compared, this significant computational reduction is achieved without any performance loss. This algorithm is particularly suitable for NB-LPDC decoders in super-high order fields, which have superior performance in the presence of burst errors.
The extended min-sum (EMS) algorithm is adopted for non-binary low density parity check (NB-LDPC) codes. The high complexity of EMS algorithm is a hot topic in recent years. Aiming at the problem, a low-complexity EMS algorithm based on NB-LDPC codes is proposed. Dynamic bubble-check (DBC) algorithm in elementary check node (ECN) steps is adopted to reduce the complexity of check node. Furthermore, the proposed algorithm dynamically truncates the length of the message vector by the number of decoding iterations. Taking the length of message vector truncated again as half of the original one as an example, the simulation results and complexity are analyzed. Analysis shows that, compared to the EMS algorithm, computational complexity of comparisons and real additions of check node of the proposed algorithm have reduced by about 70% and 25% respectively. Meantime, the decoding performance of the proposed algorithm approach that of EMS algorithm and the loss is only near 0.08 dB when the bit error rate (BER) is 10−3and the Galois fieldGF(q)(q=16)GF(q)(q=16)GF(q)(q=16).
This chapter reviews nonbinary low–density parity–check (NB–LDPC) decoder architectures, with emphasis given to algorithmic and architectural modification techniques for the check node units. The belief propagation (BP) for binary low-density parity-check decoding can be extended to decode NB–LDPC codes. In non–binary BP, the check node processing also computes sums of products of probabilities. The computations in non–binary check node processing can be considered as convolutions of the incoming messages. Multiplications in probability domain are implemented as additions in log domain. The most prominent ones are the extended Minsum algorithm and the Min–max algorithm. Both of them are log-domain algorithms. The approximations lead to slight performance loss compared to the BP, the hardware complexity has been greatly reduced in these algorithms, and only additions on the reliability messages are involved in their check node processing. The number of multiplications in the check node processing is reduced in the frequency–domain approach.
Low Density Parity Check (LDPC) codes have been widely applied in recent years, and Extended Min-Sum (EMS) decoding algorithm is the most practical algorithm, which has a fairly low computational cost. Due to the great loss in error correction performance of EMS algorithm, in this paper, we establish constraints to obtain reliable nodes while decoding and evaluate the reliability of the nodes. The nodes and information transferred between nodes are processed and optimized according to the reliability of the nodes. High reliability nodes will not be updated in the decoding process while the information of the sub-reliability nodes will be optimized in different situations, thereby improving the decoding accuracy. This algorithm can accelerate the convergence of the algorithm, while the reduced number of update nodes can control the increase of the computation to a certain extent, and maintain the advantage of the low computation quantity of EMS algorithm. Through simulation results and computational analysis, we prove that the improved algorithm has significantly improved error correction performance compared with the traditional EMS algorithm. Under the same conditions, it has completely entered the waterfall area at 3.6dB, and the EMS algorithm has not entered the waterfall area. By comparing the average iteration times of decoding of the two algorithms, the convergence speed of the algorithm can be reflected. Compared with EMS algorithm, the improved algorithm has significantly improved the convergence speed in most areas, which indicates that the processing of sub-reliable nodes accelerates the convergence of the algorithm. Finally, the average update times of the check nodes and variable nodes of the two algorithms are compared respectively. Although the improved algorithm introduces extra processing flow, it speeds up the convergence of the algorithm, and the computational cost of decoding is less expensive.
Although non-binary low-density parity-check (NB-LDPC) codes have better error-correction capability than that of binary LDPC codes, their decoding complexity is significantly higher.Therefore, it is crucial to reduce the decoding complexity of NB-LDPC while maintaining their error-correction capability to adopt them for various applications.The extended min-sum (EMS) algorithm is widely used for decoding NB-LDPC codes, and it reduces the complexity of check node (CN) operations via message truncation.Herein, we propose a low-cost CN processing method to reduce the complexity of CN operations, which take most of the decoding time.Unlike existing studies on low complexity CN operations, the proposed method employs quick selection algorithm, thereby reducing the hardware complexity and CN operation time.The experimental results show that the proposed selection-based CN operation is more than three times faster and achieves better error-correction performance than the conventional EMS algorithm.
A simplified algorithm for check node processing of extended min-sum (EMS) q-ary LDPC decoders is presented in this letter. Compared with the bubble check algorithm, the so-called dynamic bubble-check (DBC) algorithm aims to further reduce the computational complexity for the elementary check node (ECN) processing. By introducing two flag vectors in ECN processing, The DBC algorithm can use the minimum number of comparisons at each step. Simulation results show that, DBC algorithm uses significantly fewer comparison operations than the bubble check algorithm, and presents no performance loss compared with standard EMS algorithm on AWGN channels.