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

Electronics Letters

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

Emmanuel Boutillon, Laura Conde-Canencia

Published Apr 29, 2010• 72 citations
Publisher

Abstract

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.

DOI
10.1049/el.2010.0566

Related papers

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

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

Extended-forward architecture for simplified check node processing in NB-LDPC decoders

Cédric Marchand, Emmanuel Boutillon, Hassan Harb +2 more

This paper focuses on low complexity architectures for check node processing in Non-Binary LDPC decoders. To be specific, we focus on Extended Min-Sum decoders and consider the state-of-the-art Forward-Backward and Syndrome-Based approaches. We recall the presorting technique that allows for significant complexity reduction at the Elementary Check Node level. The Extended-Forward architecture is then presented as an original new architecture for efficient syndrome calculation. These advances lead to a new architecture for check node processing with reduced area. As an example, we provide implementation results over GF(64) and code rate 5/6 showing complexity reduction by a factor of up to 2.6.

SiPS ... design and implementation - IEEE Workshop on Signal Processing Systems•Oct 1, 2017•4 citations

A Novel Architecture for Elementary-Check-Node Processing in Nonbinary LDPC Decoders

Oussama Abassi, Laura Conde-Canencia, Ali Chamas Al Ghouwayel +1 more

This brief presents an efficient architecture design for elementary-check-node processing in nonbinary low-density parity-check decoders based on the extended min-sum algorithm. This architecture relies on a simplified version of the bubble check algorithm and is implemented by the means of first-in-first-out. The adoption of this new design at the check node level results in a high-rate low-cost full-pipelined processor. A proof-of-concept implementation of this processor shows that the proposed architecture halves the occupied the field-programmable gate array (FPGA) surface and doubles the maximum frequency without modifying the input/output behavior of the previous one.

IEEE Transactions on Circuits & Systems II Express Briefs•Apr 7, 2016•22 citations

A Simplified Min-Sum Decoding Algorithm for Non-Binary LDPC Codes

Chung-Li Wang, Xiaoheng Chen, Zongwang Li +1 more

Non-binary low-density parity-check codes are robust to various channel impairments. However, based on the existing decoding algorithms, the decoder implementations are expensive because of their excessive computational complexity and memory usage. Based on the combinatorial optimization, we present an approximation method for the check node processing. The simulation results demonstrate that our scheme has small performance loss over the additive white Gaussian noise channel and independent Rayleigh fading channel. Furthermore, the proposed reduced-complexity realization provides significant savings on hardware, so it yields a good performance-complexity tradeoff and can be efficiently implemented.

arXiv:1207.5555•IEEE Transactions on Communications•Oct 22, 2012•50 citations
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.
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.
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.
This paper focuses on low complexity architectures for check node processing in Non-Binary LDPC decoders. To be specific, we focus on Extended Min-Sum decoders and consider the state-of-the-art Forward-Backward and Syndrome-Based approaches. We recall the presorting technique that allows for significant complexity reduction at the Elementary Check Node level. The Extended-Forward architecture is then presented as an original new architecture for efficient syndrome calculation. These advances lead to a new architecture for check node processing with reduced area. As an example, we provide implementation results over GF(64) and code rate 5/6 showing complexity reduction by a factor of up to 2.6.
This brief presents an efficient architecture design for elementary-check-node processing in nonbinary low-density parity-check decoders based on the extended min-sum algorithm. This architecture relies on a simplified version of the bubble check algorithm and is implemented by the means of first-in-first-out. The adoption of this new design at the check node level results in a high-rate low-cost full-pipelined processor. A proof-of-concept implementation of this processor shows that the proposed architecture halves the occupied the field-programmable gate array (FPGA) surface and doubles the maximum frequency without modifying the input/output behavior of the previous one.
Non-binary low-density parity-check codes are robust to various channel impairments. However, based on the existing decoding algorithms, the decoder implementations are expensive because of their excessive computational complexity and memory usage. Based on the combinatorial optimization, we present an approximation method for the check node processing. The simulation results demonstrate that our scheme has small performance loss over the additive white Gaussian noise channel and independent Rayleigh fading channel. Furthermore, the proposed reduced-complexity realization provides significant savings on hardware, so it yields a good performance-complexity tradeoff and can be efficiently implemented.