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:1311.2003 · IEEE Transactions on Information Theory

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

Iryna Andriyanova, Alexandre Graell i Amat

Published Mar 10, 2016• 31 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/tit.2016.2540800

Related papers

Nonbinary spatially-coupled LDPC codes on the binary erasure channel

Amina Piemontese, Alexandre Graell i Amat, Giulio Colavolpe

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.

arXiv:1209.5762•International Conference on Communications•Jun 1, 2013•13 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

A simple proof of threshold saturation for coupled scalar recursions

Arvind Yedla, Yung-Yih Jian, Phong S. Nguyen +1 more

Low-density parity-check (LDPC) convolutional codes (or spatially-coupled codes) have been shown to approach capacity on the binary erasure channel (BEC) and binary-input memoryless symmetric channels. The mechanism behind this spectacular performance is the threshold saturation phenomenon, which is characterized by the belief-propagation threshold of the spatially-coupled ensemble increasing to an intrinsic noise threshold defined by the uncoupled system. In this paper, we present a simple proof of threshold saturation that applies to a broad class of coupled scalar recursions. The conditions of the theorem are verified for the density-evolution (DE) equations of irregular LDPC codes on the BEC, a class of generalized LDPC codes, and the joint iterative decoding of LDPC codes on intersymbol-interference channels with erasure noise. Our approach is based on potential functions and was motivated mainly by the ideas of Takeuchi et al. The resulting proof is surprisingly simple when compared to previous methods.

arXiv:1204.5703•International Symposium on Turbo Codes and Iterative Information Processing•Aug 1, 2012•96 citations

A simple proof of threshold saturation for coupled vector recursions

Arvind Yedla, Yung-Yih Jian, Phong S. Nguyen +1 more

Convolutional low-density parity-check (LDPC) codes (or spatially-coupled codes) have now been shown to achieve capacity on binary-input memoryless symmetric channels. The principle behind this surprising result is the threshold-saturation phenomenon, which is defined by the belief-propagation threshold of the spatially-coupled ensemble saturating to a fundamental threshold defined by the uncoupled system. Previously, the authors demonstrated that potential functions can be used to provide a simple proof of threshold saturation for coupled scalar recursions. In this paper, we present a simple proof of threshold saturation that applies to a wide class of coupled vector recursions. The conditions of the theorem are verified for the density-evolution equations of: (i) joint decoding of irregular LDPC codes for a Slepian-Wolf problem with erasures, (ii) joint decoding of irregular LDPC codes on an erasure multiple-access channel, and (iii) admissible protograph codes on the BEC. This proves threshold saturation for these systems.

arXiv:1208.4080•IEEE Information Theory Workshop (ITW)•Sep 1, 2012•28 citations

A Proof of Threshold Saturation for Spatially-Coupled LDPC Codes on BMS Channels

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.

•Aug 17, 2016•31 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 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.
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.
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.
Low-density parity-check (LDPC) convolutional codes (or spatially-coupled codes) have been shown to approach capacity on the binary erasure channel (BEC) and binary-input memoryless symmetric channels. The mechanism behind this spectacular performance is the threshold saturation phenomenon, which is characterized by the belief-propagation threshold of the spatially-coupled ensemble increasing to an intrinsic noise threshold defined by the uncoupled system. In this paper, we present a simple proof of threshold saturation that applies to a broad class of coupled scalar recursions. The conditions of the theorem are verified for the density-evolution (DE) equations of irregular LDPC codes on the BEC, a class of generalized LDPC codes, and the joint iterative decoding of LDPC codes on intersymbol-interference channels with erasure noise. Our approach is based on potential functions and was motivated mainly by the ideas of Takeuchi et al. The resulting proof is surprisingly simple when compared to previous methods.
Convolutional low-density parity-check (LDPC) codes (or spatially-coupled codes) have now been shown to achieve capacity on binary-input memoryless symmetric channels. The principle behind this surprising result is the threshold-saturation phenomenon, which is defined by the belief-propagation threshold of the spatially-coupled ensemble saturating to a fundamental threshold defined by the uncoupled system. Previously, the authors demonstrated that potential functions can be used to provide a simple proof of threshold saturation for coupled scalar recursions. In this paper, we present a simple proof of threshold saturation that applies to a wide class of coupled vector recursions. The conditions of the theorem are verified for the density-evolution equations of: (i) joint decoding of irregular LDPC codes for a Slepian-Wolf problem with erasures, (ii) joint decoding of irregular LDPC codes on an erasure multiple-access channel, and (iii) admissible protograph codes on the BEC. This proves threshold saturation for these systems.
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.
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.