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

IEEE Transactions on Communications

Analysis of Binary and Ternary Message Passing Decoding for Generalized LDPC Codes

Emna Ben Yacoub, Gianluigi Liva

Published Jul 5, 2023• 1 citation
Publisher

Abstract

The performance of generalized low-density parity-check (GLDPC) codes under binary and ternary message passing decoding (BMP/TMP) is analyzed from a density evolution (DE) perspective. At the check nodes, two types of local decoders are considered, namely optimum a-posteriori probability (APP) soft-input soft-output decoding, and bounded distance decoding (BDD). The purpose is to shed light on the performance loss incurred by BMP and TMP decoding of GLDPC codes with respect to unquantized belief propagation (BP) decoding. A DE analysis for irregular code ensembles is developed for all the algorithms, which allows obtaining the scaling coefficients needed for the variable node operation of BMP and TMP decoders. The stability analysis for the case of bounded distance decoding at the check nodes is derived. The asymptotic DE analysis is confirmed by the finite-length simulation results. For the codes analyzed in this paper, which rely on extended Hamming component codes, the study shows that under BMP decoding, BDD at the check nodes yields almost the same performance as optimum APP check node processing, while under TMP decoding the loss incurred by the sub-optimum BDD at check nodes is within 0.7 dB, when compared with APP decoding at the check nodes.

DOI
10.1109/tcomm.2023.3292474

Related papers

Analysis of Binary and Ternary Message Passing Decoding for Generalized LDPC Codes

Emna Ben Yacoub, Gianluigi Liva

Binary and a ternary message passing decoding algorithms for generalized low-density parity-check codes are defined and analyzed. In all algorithms, the variable nodes exploit soft channel information. However, the exchanged messages between variable and check nodes are binary or ternary. Two types of local decoders are assumed at the check nodes, namely an optimum a-posteriori probability soft-input soft-output decoder, and a more practical bounded distance decoder. A density evolution analysis for irregular code ensembles is developed for all the introduced algorithms, which allows obtaining the scaling coefficients needed for the variable node operation. Finite-length simulation results confirm the validity of the asymptotic analysis.

International Symposium on Problems of Redundancy in Information and Control Systems (REDUNDANCY)•Oct 25, 2021•2 citations

Protograph-Based LDPC Code Design for Ternary Message Passing Decoding

Emna Ben Yacoub, Fabian Steiner, Balázs Matuz +1 more

A ternary message passing (TMP) decoding algorithm for low-density parity-check codes is developed. All messages exchanged between variable and check nodes have a ternary alphabet, and the variable nodes exploit soft information from the channel. A density evolution analysis is developed for unstructured and protograph-based ensembles. For unstructured ensembles the stability condition is derived. Optimized ensembles for TMP decoding show asymptotic gains of up to 0.6 dB with respect to ensembles optimized for binary message passing decoding. Finite length simulations of codes from TMP-optimized ensembles show gains of up to 0.5 dB under TMP compared to protograph-based codes designed for unquantized belief propagation decoding.

arXiv:1809.10910•Sep 28, 2018•17 citations

Density Evolution Analysis of Generalized Low-density Parity-check Codes under a Posteriori Probability Decoder

Chang, Dongxu, Qingqing Peng, Ma, Zhiming +2 more

In this study, the performance of generalized low-density parity-check (GLDPC) codes under the a posteriori probability (APP) decoder is analyzed. We explore the concentration, symmetry, and monotonicity properties of GLDPC codes under the APP decoder, extending the applicability of density evolution to GLDPC codes. On the binary memoryless symmetric channels, using the BEC and BI-AWGN channels as two examples, we demonstrate that with an appropriate proportion of generalized constraint (GC) nodes, GLDPC codes can reduce the original gap to capacity compared to their original LDPC counterparts. Additionally, on the BI-AWGN channel, we apply and improve the Gaussian approximation algorithm in the density evolution of GLDPC codes. By adopting Gaussian mixture distributions to approximate the message distributions from variable nodes and Gaussian distributions for those from constraint nodes, the precision of the channel parameter threshold can be significantly enhanced while maintaining a low computational complexity similar to that of Gaussian approximations. Furthermore, we identify a class of subcodes that can greatly simplify the performance analysis and practical decoding of GLDPC codes, which we refer to as message-invariant subcodes. Using the aforementioned techniques, our simulation experiments provide empirical evidence that GLDPC codes, when decoded with the APP decoder and equipped with the right fraction of GC nodes, can achieve substantial performance improvements compared to low-density parity-check (LDPC) codes.

arXiv:2404.01136•Apr 1, 2024•0 citations

One and Two Bit Message Passing for SC-LDPC Codes With Higher-Order Modulation

Fabian Steiner, Emna Ben Yacoub, Balazs Matuz +2 more

Low complexity decoding algorithms are necessary to meet data rate requirements in excess of 1 Tbps. In this paper, we study one and two bit message passing algorithms for belief propagation decoding of low-density parity-check (LDPC) codes and analyze them by density evolution. The variable nodes (VNs) exploit soft information from the channel output. To decrease the data flow, the messages exchanged between check nodes (CNs) and VNs are represented by one or two bits. The newly proposed quaternary message passing (QMP) algorithm is compared asymptotically and in finite length simulations to binary message passing (BMP) and ternary message passing (TMP) for spectrally efficient communication with higher-order modulation and probabilistic amplitude shaping (PAS). To showcase the potential for high throughput forward error correction, spatially coupled LDPC codes and a target spectral efficiency (SE) of 3 bits/QAM symbol are considered. Gains of about 0.7 dB and 0.1 dB are observed compared to BMP and TMP, respectively. The gap to unquantized belief propagation (BP) decoding is reduced to about 0.75 dB. For smaller code rates, the gain of QMP compared to TMP is more pronounced and amounts to 0.24 dB in the considered example.

arXiv:1902.10391•Journal of Lightwave Technology•Sep 24, 2019•21 citations

One and Two Bit Message Passing for SC-LDPC Codes with Higher-Order Modulation

Fabian Steiner, Ben Yacoub, Emna, Balázs Matuz +2 more

Low complexity decoding algorithms are necessary to meet data rate requirements in excess of 1 Tbps. In this paper, we study one and two bit message passing algorithms for belief propagation decoding of low-density parity-check (LDPC) codes and analyze them by density evolution. The variable nodes (VNs) exploit soft information from the channel output. To decrease the data flow, the messages exchanged between check nodes (CNs) and VNs are represented by one or two bits. The newly proposed quaternary message passing (QMP) algorithm is compared asymptotically and in finite length simulations to binary message passing (BMP) and ternary message passing (TMP) for spectrally efficient communication with higher-order modulation and probabilistic amplitude shaping (PAS). To showcase the potential for high throughput forward error correction, spatially coupled LDPC codes and a target spectral efficiency (SE) of 3 bits/QAM symbol are considered. Gains of about 0.7 dB and 0.1 dB are observed compared to BMP and TMP, respectively. The gap to unquantized belief propagation (BP) decoding is reduced to about 0.75 dB. For smaller code rates, the gain of QMP compared to TMP is more pronounced and amounts to 0.24 dB in the considered example.

•Jan 1, 2019•16 citations

Generalized LDPC codes and generalized stopping sets

N. Miladinovic, M.P.C. Fossorier

A generalized low-density parity check code (GLDPC) is a low-density parity check code in which the constraint nodes of the code graph are block codes, rather than single parity checks. In this paper, we study GLDPC codes which have BCH or Reed-Solomon codes as subcodes under bounded distance decoding (BDD). The performance of the proposed scheme is investigated in the limit case of an infinite length (cycle free) code used over a binary erasure channel (BEC) and the corresponding thresholds for iterative decoding are derived. The performance of the proposed scheme for finite code lengths over a BEC is investigated as well. Structures responsible for decoding failures are defined and a theoretical analysis over the ensemble of GLDPC codes which yields exact bit and block error rates of the ensemble average is derived. Unfortunately this study shows that GLDPC codes do not compare favorably with their LDPC counterpart over the BEC. Fortunately, it is also shown that under certain conditions, objects identified in the analysis of GLDPC codes over a BEC and the corresponding theoretical results remain useful to derive tight lower bounds on the performance of GLDPC codes over a binary symmetric channel (BSC). Simulation results show that the proposed method yields competitive performance with a good decoding complexity trade-off for the BSC.

IEEE Transactions on Communications•Feb 1, 2008•52 citations
The performance of generalized low-density parity-check (GLDPC) codes under binary and ternary message passing decoding (BMP/TMP) is analyzed from a density evolution (DE) perspective. At the check nodes, two types of local decoders are considered, namely optimum a-posteriori probability (APP) soft-input soft-output decoding, and bounded distance decoding (BDD). The purpose is to shed light on the performance loss incurred by BMP and TMP decoding of GLDPC codes with respect to unquantized belief propagation (BP) decoding. A DE analysis for irregular code ensembles is developed for all the algorithms, which allows obtaining the scaling coefficients needed for the variable node operation of BMP and TMP decoders. The stability analysis for the case of bounded distance decoding at the check nodes is derived. The asymptotic DE analysis is confirmed by the finite-length simulation results. For the codes analyzed in this paper, which rely on extended Hamming component codes, the study shows that under BMP decoding, BDD at the check nodes yields almost the same performance as optimum APP check node processing, while under TMP decoding the loss incurred by the sub-optimum BDD at check nodes is within 0.7 dB, when compared with APP decoding at the check nodes.
Binary and a ternary message passing decoding algorithms for generalized low-density parity-check codes are defined and analyzed. In all algorithms, the variable nodes exploit soft channel information. However, the exchanged messages between variable and check nodes are binary or ternary. Two types of local decoders are assumed at the check nodes, namely an optimum a-posteriori probability soft-input soft-output decoder, and a more practical bounded distance decoder. A density evolution analysis for irregular code ensembles is developed for all the introduced algorithms, which allows obtaining the scaling coefficients needed for the variable node operation. Finite-length simulation results confirm the validity of the asymptotic analysis.
A ternary message passing (TMP) decoding algorithm for low-density parity-check codes is developed. All messages exchanged between variable and check nodes have a ternary alphabet, and the variable nodes exploit soft information from the channel. A density evolution analysis is developed for unstructured and protograph-based ensembles. For unstructured ensembles the stability condition is derived. Optimized ensembles for TMP decoding show asymptotic gains of up to 0.6 dB with respect to ensembles optimized for binary message passing decoding. Finite length simulations of codes from TMP-optimized ensembles show gains of up to 0.5 dB under TMP compared to protograph-based codes designed for unquantized belief propagation decoding.
In this study, the performance of generalized low-density parity-check (GLDPC) codes under the a posteriori probability (APP) decoder is analyzed. We explore the concentration, symmetry, and monotonicity properties of GLDPC codes under the APP decoder, extending the applicability of density evolution to GLDPC codes. On the binary memoryless symmetric channels, using the BEC and BI-AWGN channels as two examples, we demonstrate that with an appropriate proportion of generalized constraint (GC) nodes, GLDPC codes can reduce the original gap to capacity compared to their original LDPC counterparts. Additionally, on the BI-AWGN channel, we apply and improve the Gaussian approximation algorithm in the density evolution of GLDPC codes. By adopting Gaussian mixture distributions to approximate the message distributions from variable nodes and Gaussian distributions for those from constraint nodes, the precision of the channel parameter threshold can be significantly enhanced while maintaining a low computational complexity similar to that of Gaussian approximations. Furthermore, we identify a class of subcodes that can greatly simplify the performance analysis and practical decoding of GLDPC codes, which we refer to as message-invariant subcodes. Using the aforementioned techniques, our simulation experiments provide empirical evidence that GLDPC codes, when decoded with the APP decoder and equipped with the right fraction of GC nodes, can achieve substantial performance improvements compared to low-density parity-check (LDPC) codes.
Low complexity decoding algorithms are necessary to meet data rate requirements in excess of 1 Tbps. In this paper, we study one and two bit message passing algorithms for belief propagation decoding of low-density parity-check (LDPC) codes and analyze them by density evolution. The variable nodes (VNs) exploit soft information from the channel output. To decrease the data flow, the messages exchanged between check nodes (CNs) and VNs are represented by one or two bits. The newly proposed quaternary message passing (QMP) algorithm is compared asymptotically and in finite length simulations to binary message passing (BMP) and ternary message passing (TMP) for spectrally efficient communication with higher-order modulation and probabilistic amplitude shaping (PAS). To showcase the potential for high throughput forward error correction, spatially coupled LDPC codes and a target spectral efficiency (SE) of 3 bits/QAM symbol are considered. Gains of about 0.7 dB and 0.1 dB are observed compared to BMP and TMP, respectively. The gap to unquantized belief propagation (BP) decoding is reduced to about 0.75 dB. For smaller code rates, the gain of QMP compared to TMP is more pronounced and amounts to 0.24 dB in the considered example.
Low complexity decoding algorithms are necessary to meet data rate requirements in excess of 1 Tbps. In this paper, we study one and two bit message passing algorithms for belief propagation decoding of low-density parity-check (LDPC) codes and analyze them by density evolution. The variable nodes (VNs) exploit soft information from the channel output. To decrease the data flow, the messages exchanged between check nodes (CNs) and VNs are represented by one or two bits. The newly proposed quaternary message passing (QMP) algorithm is compared asymptotically and in finite length simulations to binary message passing (BMP) and ternary message passing (TMP) for spectrally efficient communication with higher-order modulation and probabilistic amplitude shaping (PAS). To showcase the potential for high throughput forward error correction, spatially coupled LDPC codes and a target spectral efficiency (SE) of 3 bits/QAM symbol are considered. Gains of about 0.7 dB and 0.1 dB are observed compared to BMP and TMP, respectively. The gap to unquantized belief propagation (BP) decoding is reduced to about 0.75 dB. For smaller code rates, the gain of QMP compared to TMP is more pronounced and amounts to 0.24 dB in the considered example.
A generalized low-density parity check code (GLDPC) is a low-density parity check code in which the constraint nodes of the code graph are block codes, rather than single parity checks. In this paper, we study GLDPC codes which have BCH or Reed-Solomon codes as subcodes under bounded distance decoding (BDD). The performance of the proposed scheme is investigated in the limit case of an infinite length (cycle free) code used over a binary erasure channel (BEC) and the corresponding thresholds for iterative decoding are derived. The performance of the proposed scheme for finite code lengths over a BEC is investigated as well. Structures responsible for decoding failures are defined and a theoretical analysis over the ensemble of GLDPC codes which yields exact bit and block error rates of the ensemble average is derived. Unfortunately this study shows that GLDPC codes do not compare favorably with their LDPC counterpart over the BEC. Fortunately, it is also shown that under certain conditions, objects identified in the analysis of GLDPC codes over a BEC and the corresponding theoretical results remain useful to derive tight lower bounds on the performance of GLDPC codes over a binary symmetric channel (BSC). Simulation results show that the proposed method yields competitive performance with a good decoding complexity trade-off for the BSC.