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 Turbo Codes and Iterative Information Processing

Simplified check node processing in nonbinary LDPC decoders

Emmanuel Boutillon, Laura Conde-Canencia

Published Sep 1, 2010• 38 citations
Publisher

Abstract

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.

DOI
10.1109/istc.2010.5613839

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

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

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

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

Reduced-memory forward-backward check node processing architecture for non-binary LDPC decoding

Xinmiao Zhang, Fang Cai

When the code length is moderate, non-binary low-density parity-check (NB-LDPC) codes can achieve better error-correcting performance than their binary counterparts at the cost of higher decoding complexity. The check node processing is a major bottleneck of NB-LDPC decoding. Its computation complexity can be reduced by an iterative forward-backward scheme. Nevertheless, large memory is required in this scheme to store intermediate results. In this paper, a novel check node processing scheme and corresponding VLSI architectures are proposed for the Min-max NB-LDPC decoding. The proposed scheme first sorts out a limited number of the most reliable input messages. Then the forward and backward processes are carried out using only these messages. In addition, an innovative approach is developed to derive the output messages from only a small number of intermediate results without noticeable performance loss. Accordingly, both the memory requirement and computation complexity are greatly reduced. For an example (837, 726) NB-LDPC code over GF(25), our proposed check node processing architecture can achieve at least 34% area reduction and about the same throughput compared to previous efforts based on the original forward-backward scheme.

IEEE International Midwest Symposium on Circuits and Systems (MWSCAS)•Aug 1, 2011•3 citations
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 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.
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 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.
When the code length is moderate, non-binary low-density parity-check (NB-LDPC) codes can achieve better error-correcting performance than their binary counterparts at the cost of higher decoding complexity. The check node processing is a major bottleneck of NB-LDPC decoding. Its computation complexity can be reduced by an iterative forward-backward scheme. Nevertheless, large memory is required in this scheme to store intermediate results. In this paper, a novel check node processing scheme and corresponding VLSI architectures are proposed for the Min-max NB-LDPC decoding. The proposed scheme first sorts out a limited number of the most reliable input messages. Then the forward and backward processes are carried out using only these messages. In addition, an innovative approach is developed to derive the output messages from only a small number of intermediate results without noticeable performance loss. Accordingly, both the memory requirement and computation complexity are greatly reduced. For an example (837, 726) NB-LDPC code over GF(25), our proposed check node processing architecture can achieve at least 34% area reduction and about the same throughput compared to previous efforts based on the original forward-backward scheme.