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:2006.11740

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

Zhonghao Zhang, Mengnan Xu, Chongbin Xu, Zeng, Dan, Zhichao Sheng

Published Jun 21, 2020• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2006.11740

Related papers

Some Results on Density Evolution of Nonbinary SC-LDPC Ensembles Over the BEC

Mengnan Xu, Dan Zeng, Zhichao Sheng +2 more

In this paper, we present several theoretic results on density evolution (DE) for nonbinary spatially-coupled low-density parity-check (SC-LDPC) ensembles when the transmission takes place on the binary erasure channel (BEC). In specific, we establish the duality rule for entropy for the nonbinary variable-node (VN) and check-node (CN) operators in such a scenario. We define the partial order between densities and show that the VN and CN operators exhibit the property of partial order preservation. More importantly, we explicitly construct the potential functions for uncoupled and coupled DE recursions, the forms of which almost coincide with those for binary LDPC and SC-LDPC ensembles over general binary memoryless symmetric (BMS) channels. These theoretic findings greatly facilitate the proof of threshold saturation for nonbinary SC-LDPC ensembles on the BEC. Finally, we develop the threshold saturation theorem and its converse, following the lines established by S. Kumar et al.

IEEE International Symposium on Information Theory (ISIT)•Jul 12, 2021•1 citation

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

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

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 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

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
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.
In this paper, we present several theoretic results on density evolution (DE) for nonbinary spatially-coupled low-density parity-check (SC-LDPC) ensembles when the transmission takes place on the binary erasure channel (BEC). In specific, we establish the duality rule for entropy for the nonbinary variable-node (VN) and check-node (CN) operators in such a scenario. We define the partial order between densities and show that the VN and CN operators exhibit the property of partial order preservation. More importantly, we explicitly construct the potential functions for uncoupled and coupled DE recursions, the forms of which almost coincide with those for binary LDPC and SC-LDPC ensembles over general binary memoryless symmetric (BMS) channels. These theoretic findings greatly facilitate the proof of threshold saturation for nonbinary SC-LDPC ensembles on the BEC. Finally, we develop the threshold saturation theorem and its converse, following the lines established by S. Kumar et al.
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.
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.
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.
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.