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

arXiv:1209.5762 · International Conference on Communications

Nonbinary spatially-coupled LDPC codes on the binary erasure channel

Amina Piemontese, Alexandre Graell i Amat, Giulio Colavolpe

Published Jun 1, 2013• 13 citations
arXivHTMLPDF

Abstract

We analyze the asymptotic performance of non-binary spatially-coupled low-density parity-check (SC-LDPC) codes built on the general linear group, when the transmission takes place over the binary erasure channel. We propose an efficient method to derive an upper bound to the maximum a posteriori probability (MAP) threshold for nonbinary LDPC codes, and observe that the MAP performance of regular LDPC codes improves with the alphabet size. We then consider nonbinary SC-LDPC codes. We show that the same threshold saturation effect experienced by binary SC-LDPC codes occurs for the nonbinary codes, hence we conjecture that the BP threshold for large termination length approaches the MAP threshold of the underlying regular ensemble.

DOI
10.1109/icc.2013.6655049

Related papers

Threshold Saturation for Nonbinary SC-LDPC Codes on the Binary Erasure Channel

Iryna Andriyanova, Alexandre Graell i Amat

We analyze the asymptotic performance of nonbinary spatially coupled low-density parity-check (SC-LDPC) code ensembles defined over the general linear group on the binary erasure channel. In particular, we prove the threshold saturation of belief propagation decoding to the so-called potential threshold, using the proof technique based on potential functions introduced by Yedla et al., assuming that the potential function exists. We rewrite the density evolution of nonbinary SC-LDPC codes in an equivalent vector recursion form which is suited for the use of the potential function. We then discuss the existence of the potential function for the general case of vector recursions defined by multivariate polynomials, and give a method to construct it. We define a potential function in a slightly more general form than the one by Yedla et al., in order to make the technique based on potential functions applicable to the case of nonbinary LDPC codes. We show that the potential function exists if a solution to a carefully designed system of linear equations exists. Furthermore, we numerically show the existence of a solution to the system of linear equations for a large number of nonbinary LDPC code ensembles, which allows us to define their potential function and thus prove threshold saturation.

arXiv:1311.2003•IEEE Transactions on Information Theory•Mar 10, 2016•31 citations

An Entropy-based Proof of Threshold Saturation for Nonbinary SC-LDPC Ensembles on the BEC

Zhonghao Zhang, Mengnan Xu, Chongbin Xu +2 more

In this paper we are concerned with the asymptotic analysis of nonbinary spatially-coupled low-density parity-check (SC-LDPC) ensembles defined over GL$\left(2^{m}\right)$ (the general linear group of degree $m$ over GF$\left(2\right)$). Our purpose is to prove threshold saturation when the transmission takes place on the binary erasure channel (BEC). To this end, we establish the duality rule for entropy for nonbinary variable-node (VN) and check-node (CN) convolutional operators to accommodate the nonbinary density evolution (DE) analysis. Based on this, we construct the explicit forms of the potential functions for uncoupled and coupled DE recursions. In addition, we show that these functions exhibit similar monotonicity properties as those for binary LDPC and SC-LDPC ensembles over general binary memoryless symmetric (BMS) channels. This leads to the threshold saturation theorem and its converse for nonbinary SC-LDPC ensembles on the BEC, following the proof technique developed by S. Kumar et al.

arXiv:2006.11740•Jun 21, 2020•1 citation

Threshold analysis of non-binary spatially-coupled LDPC codes with windowed decoding

Lai Wei, Toshiaki Koike–Akino, David G. M. Mitchell +2 more

We study the iterative decoding threshold performance of non-binary spatially-coupled low-density parity-check (NB-SC-LDPC) code ensembles for both the binary erasure channel (BEC) and the binary-input additive white Gaussian noise channel (BIAWGNC), with particular emphasis on windowed decoding (WD). We consider both (2, 4)-regular and (3, 6)-regular NB-SC-LDPC code ensembles constructed using protographs and compute their thresholds using protograph versions of NB density evolution and NB extrinsic information transfer analysis. For these code ensembles, we show that WD of NB-SC-LDPC codes, which provides a significant decrease in latency and complexity compared to decoding across the entire parity-check matrix, results in a negligible decrease in the near-capacity performance for a sufficiently large window size W on both the BEC and the BIAWGNC. Also, we show that NBSC-LDPC code ensembles exhibit gains in the WD threshold compared to the corresponding block code ensembles decoded across the entire parity-check matrix, and that the gains increase as the finite field size q increases. Moreover, from the viewpoint of decoding complexity, we see that (3, 6)-regular NB-SC-LDPC codes are particularly attractive due to the fact that they achieve near-capacity thresholds even for small q and W.

arXiv:1403.3583•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2014•19 citations

Density evolution, thresholds and the stability condition for non-binary LDPC codes

Vishwambhar Rathi, Rudiger L. Urbanke

The density evolution equations for non-binary low-density parity-check (LDPC) ensembles when transmission takes place over the binary erasure channel are derived. Ensembles defined with respect to the general linear group over the binary field are introduced. For these ensembles the density evolution equations can be written compactly. The density evolution for the general linear group helps in understanding the density evolution for codes defined with respect to finite fields. Thresholds are computed for different alphabet sizes for various LDPC ensembles. Surprisingly, the threshold is not a monotonic function of the alphabet size. The stability condition for non-binary LDPC ensembles over any binary memoryless symmetric channel is stated. Upper bounds on the MAP thresholds for various non-binary ensembles based on EXIT curves and the area theorem are given.

arXiv:cs/0511100•IEE Proceedings - Communications•Jan 1, 2005•101 citations

A Scaling Law to Predict the Finite-Length Performance of Spatially-Coupled LDPC Codes

Pablo M. Olmos, Rudiger L. Urbanke

Spatially-coupled low-density parity-check (SC-LDPC) codes are known to have excellent asymptotic properties. Much less is known regarding their finite-length performance. We propose a scaling law to predict the error probability of finite-length spatially coupled code ensembles when transmission takes place over the binary erasure channel. We discuss how the parameters of the scaling law are connected to fundamental quantities appearing in the asymptotic analysis of these ensembles and we verify that the predictions of the scaling law fit well to the data derived from simulations over a wide range of parameters. The ultimate goal of this line of research is to develop analytic tools for the design of SC-LDPC codes under practical constraints.

arXiv:1404.5719•IEEE Transactions on Information Theory•Apr 14, 2015•57 citations

A proof of threshold saturation for spatially-coupled LDPC codes on BMS channels

Santhosh Kumar, Andrew J. Young, Nicolas Macris +1 more

Low-density parity-check (LDPC) convolutional codes have been shown to exhibit excellent performance under low-complexity belief-propagation decoding [1], [2]. This phenomenon is now termed threshold saturation via spatial coupling. The underlying principle behind this appears to be very general and spatially-coupled (SC) codes have been successfully applied in numerous areas. Recently, SC regular LDPC codes have been proven to achieve capacity universally, over the class of binary memoryless symmetric (BMS) channels, under belief-propagation decoding [3], [4]. In [5], [6], potential functions are used to prove that the BP threshold of SC irregular LDPC ensembles saturates, for the binary erasure channel, to the conjectured MAP threshold (known as the Maxwell threshold) of the underlying irregular ensembles. In this paper, that proof technique is generalized to BMS channels, thereby extending some results of [4] to irregular LDPC ensembles. We also believe that this approach can be expanded to cover a wide class of graphical models whose message-passing rules are associated with a Bethe free energy.

arXiv:1301.6111•Allerton Conference on Communication, Control, and Computing•Oct 1, 2012•3 citations
We analyze the asymptotic performance of non-binary spatially-coupled low-density parity-check (SC-LDPC) codes built on the general linear group, when the transmission takes place over the binary erasure channel. We propose an efficient method to derive an upper bound to the maximum a posteriori probability (MAP) threshold for nonbinary LDPC codes, and observe that the MAP performance of regular LDPC codes improves with the alphabet size. We then consider nonbinary SC-LDPC codes. We show that the same threshold saturation effect experienced by binary SC-LDPC codes occurs for the nonbinary codes, hence we conjecture that the BP threshold for large termination length approaches the MAP threshold of the underlying regular ensemble.
We analyze the asymptotic performance of nonbinary spatially coupled low-density parity-check (SC-LDPC) code ensembles defined over the general linear group on the binary erasure channel. In particular, we prove the threshold saturation of belief propagation decoding to the so-called potential threshold, using the proof technique based on potential functions introduced by Yedla et al., assuming that the potential function exists. We rewrite the density evolution of nonbinary SC-LDPC codes in an equivalent vector recursion form which is suited for the use of the potential function. We then discuss the existence of the potential function for the general case of vector recursions defined by multivariate polynomials, and give a method to construct it. We define a potential function in a slightly more general form than the one by Yedla et al., in order to make the technique based on potential functions applicable to the case of nonbinary LDPC codes. We show that the potential function exists if a solution to a carefully designed system of linear equations exists. Furthermore, we numerically show the existence of a solution to the system of linear equations for a large number of nonbinary LDPC code ensembles, which allows us to define their potential function and thus prove threshold saturation.
In this paper we are concerned with the asymptotic analysis of nonbinary spatially-coupled low-density parity-check (SC-LDPC) ensembles defined over GL(2m)\left(2^{m}\right)(2m) (the general linear group of degree mmm over GF(2)\left(2\right)(2)). Our purpose is to prove threshold saturation when the transmission takes place on the binary erasure channel (BEC). To this end, we establish the duality rule for entropy for nonbinary variable-node (VN) and check-node (CN) convolutional operators to accommodate the nonbinary density evolution (DE) analysis. Based on this, we construct the explicit forms of the potential functions for uncoupled and coupled DE recursions. In addition, we show that these functions exhibit similar monotonicity properties as those for binary LDPC and SC-LDPC ensembles over general binary memoryless symmetric (BMS) channels. This leads to the threshold saturation theorem and its converse for nonbinary SC-LDPC ensembles on the BEC, following the proof technique developed by S. Kumar et al.
We study the iterative decoding threshold performance of non-binary spatially-coupled low-density parity-check (NB-SC-LDPC) code ensembles for both the binary erasure channel (BEC) and the binary-input additive white Gaussian noise channel (BIAWGNC), with particular emphasis on windowed decoding (WD). We consider both (2, 4)-regular and (3, 6)-regular NB-SC-LDPC code ensembles constructed using protographs and compute their thresholds using protograph versions of NB density evolution and NB extrinsic information transfer analysis. For these code ensembles, we show that WD of NB-SC-LDPC codes, which provides a significant decrease in latency and complexity compared to decoding across the entire parity-check matrix, results in a negligible decrease in the near-capacity performance for a sufficiently large window size W on both the BEC and the BIAWGNC. Also, we show that NBSC-LDPC code ensembles exhibit gains in the WD threshold compared to the corresponding block code ensembles decoded across the entire parity-check matrix, and that the gains increase as the finite field size q increases. Moreover, from the viewpoint of decoding complexity, we see that (3, 6)-regular NB-SC-LDPC codes are particularly attractive due to the fact that they achieve near-capacity thresholds even for small q and W.
The density evolution equations for non-binary low-density parity-check (LDPC) ensembles when transmission takes place over the binary erasure channel are derived. Ensembles defined with respect to the general linear group over the binary field are introduced. For these ensembles the density evolution equations can be written compactly. The density evolution for the general linear group helps in understanding the density evolution for codes defined with respect to finite fields. Thresholds are computed for different alphabet sizes for various LDPC ensembles. Surprisingly, the threshold is not a monotonic function of the alphabet size. The stability condition for non-binary LDPC ensembles over any binary memoryless symmetric channel is stated. Upper bounds on the MAP thresholds for various non-binary ensembles based on EXIT curves and the area theorem are given.
Spatially-coupled low-density parity-check (SC-LDPC) codes are known to have excellent asymptotic properties. Much less is known regarding their finite-length performance. We propose a scaling law to predict the error probability of finite-length spatially coupled code ensembles when transmission takes place over the binary erasure channel. We discuss how the parameters of the scaling law are connected to fundamental quantities appearing in the asymptotic analysis of these ensembles and we verify that the predictions of the scaling law fit well to the data derived from simulations over a wide range of parameters. The ultimate goal of this line of research is to develop analytic tools for the design of SC-LDPC codes under practical constraints.
Low-density parity-check (LDPC) convolutional codes have been shown to exhibit excellent performance under low-complexity belief-propagation decoding [1], [2]. This phenomenon is now termed threshold saturation via spatial coupling. The underlying principle behind this appears to be very general and spatially-coupled (SC) codes have been successfully applied in numerous areas. Recently, SC regular LDPC codes have been proven to achieve capacity universally, over the class of binary memoryless symmetric (BMS) channels, under belief-propagation decoding [3], [4]. In [5], [6], potential functions are used to prove that the BP threshold of SC irregular LDPC ensembles saturates, for the binary erasure channel, to the conjectured MAP threshold (known as the Maxwell threshold) of the underlying irregular ensembles. In this paper, that proof technique is generalized to BMS channels, thereby extending some results of [4] to irregular LDPC ensembles. We also believe that this approach can be expanded to cover a wide class of graphical models whose message-passing rules are associated with a Bethe free energy.