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

IEICE Transactions on Communications

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

Wei Lin, Baoming Bai, Xiao Ma, Rong Xia Sun

Published Jan 1, 2012• 1 citation
Publisher

Abstract

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.

DOI
10.1587/transcom.e95.b.1815

Related papers

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

Dynamic extended mim-sum decoding algorithm for Q-ary LDPC codes

Xuepeng Wang

Decoded with the extended min-sum(EMS) algorithm,q-ary LDPC codes suffer great performance degradation compared with that decoded with the q-ary sum-product algorithm(QSPA) in case the length nm of message vectors is too small.To solve this problem,a dynamic EMS(D-EMS) algorithm is proposed in this paper.First,we examined the distribution of likelihood values among GF(q) symbols in the message vectors,and concluded that the likelihood values would concentrate to a small portion of symbols as the iteration number increases.Therefore,the D-EMS algorithm first set the length of message vectors to nm1,then truncate it to nm2 after certain decoding iterations,thus the decoding computational complexity can be efficiently reduced.Meanwhile,in order to reduce the complexity of real comparisons in the decoder,the proposed algorithm employs the bubble check(BC) algorithm during the check node elementary steps.Complexity analysis and simulation results indicate that,under appropriate parameter configurations,while efficiently reducing the decoding complexity of the EMS algorithm,the D-EMS algorithm performs nearly as well as the corresponding EMS algorithm over both AWGN and Rayleigh fading channels,and thus can be efficiently applied to practical communication systems based on q-ary LDPC codes.

Journal of Xidian University•Jan 1, 2012•0 citations

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

Joint Demodulation and EMS Decoding Algorithm for Q-ary LDPC Codes

Wei Lin -, Baoming Bai, Sheng Tong

To reduce the high decoding complexity of q-ary LDPC codes, a joint-demodulation and extended min-sum (JD-EMS) decoding algorithm is presented in this paper. By utilizing the squares of the distances between signal and constellation points over constellation graph as the decoder input soft messages, the proposed algorithm not only facilitates the computations of the decoder initial messages, but also avoids the performance loss due to conversions between probabilities and log-likelihoodratios. The elementary check node (ECN) processing is also improved in JD-EMS algorithm, thus the number of real additions can be reduced. Moreover, we also give an upper bound of the number of comparison candidates in the sorter at each ECN step. Simulation results indicate that, while significantly reducing the number of real additions at check nodes, JD-EMS algorithm performs as well as EMS algorithm on both AWGN and Rayleigh fading channels.

Journal of Convergence Information Technology•Jun 30, 2011•3 citations

Simplified check node processing in nonbinary LDPC decoders

Emmanuel Boutillon, Laura Conde-Canencia

This paper deals with low-complexity algorithms for the check node processing in nonbinary LDPC decoders. After a review of the state-of-the-art, we focus on an original solution to significantly reduce the order of complexity of the Extended Min-Sum decoder at the elementary check node level. The main originality of the so-called Bubble Check algorithm is the two-dimensional strategy for the check node processing, which leads to a reduction of the number of comparisons. The simulation results obtained for the Bubble Check show that this complexity reduction does not introduce any performance loss and that it is even possible to further reduce the number of comparisons. This motivated the search of a simplified architecture and led to the L-Bubble Check, which is the main contribution of the paper. The implementation of a forward/backward check node as a systolic architecture of L-Bubble elementary checks is also described. Finally, some FPGA synthesis results of a whole GF(64)-LDPC decoder implementation are presented.

International Symposium on Turbo Codes and Iterative Information Processing•Sep 1, 2010•38 citations

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

Shengjun Xiong, Lisheng Zhou, Yuxin Xiong +1 more

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.

International Conference on Communication Networks and Machine Learning (CNML)•Feb 21, 2025•0 citations
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.
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).
Decoded with the extended min-sum(EMS) algorithm,q-ary LDPC codes suffer great performance degradation compared with that decoded with the q-ary sum-product algorithm(QSPA) in case the length nm of message vectors is too small.To solve this problem,a dynamic EMS(D-EMS) algorithm is proposed in this paper.First,we examined the distribution of likelihood values among GF(q) symbols in the message vectors,and concluded that the likelihood values would concentrate to a small portion of symbols as the iteration number increases.Therefore,the D-EMS algorithm first set the length of message vectors to nm1,then truncate it to nm2 after certain decoding iterations,thus the decoding computational complexity can be efficiently reduced.Meanwhile,in order to reduce the complexity of real comparisons in the decoder,the proposed algorithm employs the bubble check(BC) algorithm during the check node elementary steps.Complexity analysis and simulation results indicate that,under appropriate parameter configurations,while efficiently reducing the decoding complexity of the EMS algorithm,the D-EMS algorithm performs nearly as well as the corresponding EMS algorithm over both AWGN and Rayleigh fading channels,and thus can be efficiently applied to practical communication systems based on q-ary LDPC codes.
To reduce the high decoding complexity of q-ary LDPC codes, a joint-demodulation and extended min-sum (JD-EMS) decoding algorithm is presented in this paper. By utilizing the squares of the distances between signal and constellation points over constellation graph as the decoder input soft messages, the proposed algorithm not only facilitates the computations of the decoder initial messages, but also avoids the performance loss due to conversions between probabilities and log-likelihoodratios. The elementary check node (ECN) processing is also improved in JD-EMS algorithm, thus the number of real additions can be reduced. Moreover, we also give an upper bound of the number of comparison candidates in the sorter at each ECN step. Simulation results indicate that, while significantly reducing the number of real additions at check nodes, JD-EMS algorithm performs as well as EMS algorithm on both AWGN and Rayleigh fading channels.
This paper deals with low-complexity algorithms for the check node processing in nonbinary LDPC decoders. After a review of the state-of-the-art, we focus on an original solution to significantly reduce the order of complexity of the Extended Min-Sum decoder at the elementary check node level. The main originality of the so-called Bubble Check algorithm is the two-dimensional strategy for the check node processing, which leads to a reduction of the number of comparisons. The simulation results obtained for the Bubble Check show that this complexity reduction does not introduce any performance loss and that it is even possible to further reduce the number of comparisons. This motivated the search of a simplified architecture and led to the L-Bubble Check, which is the main contribution of the paper. The implementation of a forward/backward check node as a systolic architecture of L-Bubble elementary checks is also described. Finally, some FPGA synthesis results of a whole GF(64)-LDPC decoder implementation are presented.
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.