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

Spatially Coupled LDPC Codes Constructed From Protographs

David G. M. Mitchell, Michael Lentmaier, Daniel J. Costello

Published Jul 8, 2015• 298 citations
arXivHTMLPDF

Abstract

In this paper, we construct protograph-based spatially coupled low-density parity-check (LDPC) codes by coupling together a series of L disjoint, or uncoupled, LDPC code Tanner graphs into a single coupled chain. By varying L , we obtain a flexible family of code ensembles with varying rates and frame lengths that can share the same encoding and decoding architecture for arbitrary L . We demonstrate that the resulting codes combine the best features of optimized irregular and regular codes in one design: capacity approaching iterative belief propagation (BP) decoding thresholds and linear growth of minimum distance with block length. In particular, we show that, for sufficiently large L , the BP thresholds on both the binary erasure channel and the binary-input additive white Gaussian noise channel saturate to a particular value significantly better than the BP decoding threshold and numerically indistinguishable from the optimal maximum a posteriori decoding threshold of the uncoupled LDPC code. When all variable nodes in the coupled chain have degree greater than two, asymptotically the error probability converges at least doubly exponentially with decoding iterations and we obtain sequences of asymptotically good LDPC codes with fast convergence rates and BP thresholds close to the Shannon limit. Further, the gap to capacity decreases as the density of the graph increases, opening up a new way to construct capacity achieving codes on memoryless binary-input symmetric-output channels with low-complexity BP decoding.

DOI
10.1109/tit.2015.2453267

Related papers

Some results on spatially coupled protograph LDPC codes

Sudarsan V. S. Ranganathan, Kasra Vakilinia, Lara Dolecek +2 more

Spatially coupled low-density parity-check block codes (SC-LDPC-BCs) are a class of LDPC codes in which certain ensembles achieve capacity under iterative belief propagation decoding. Prior work has considered these codes mostly from a protograph perspective. Following this viewpoint, our work presents new protographs for the design of protograph-based SC-LDPC-BCs. A reciprocal channel approximation (RCA) analysis of the terminated protographs yields the asymptotic performance limits of the ensembles in terms of their iterative decoding thresholds. Our protographs possess the properties of linear minimum distance growth rate and excellent thresholds. We consider the following channels in our work: binary-input additive white Gaussian noise channel (BI-AWGNC), binary erasure channel (BEC), and binary symmetric channel (BSC). Our work focuses on obtaining good designs, with two classes of ensembles being asymptotically regular, for all the three channels while minimizing rate loss.

Information Theory and Applications Workshop (ITA)•Jan 1, 2016•3 citations

On the minimum distance of generalized spatially coupled LDPC codes

David G. M. Mitchell, Michael Lentmaier, Daniel J. Costello

Families of generalized spatially-coupled low-density parity-check (GSC-LDPC) code ensembles can be formed by terminating protograph-based generalized LDPC convolutional (GLDPCC) codes. It has previously been shown that ensembles of GSC-LDPC codes constructed from a protograph have better iterative decoding thresholds than their block code counterparts, and that, for large termination lengths, their thresholds coincide with the maximum a-posteriori (MAP) decoding threshold of the underlying generalized LDPC block code ensemble. Here we show that, in addition to their excellent iterative decoding thresholds, ensembles of GSC-LDPC codes are asymptotically good and have large minimum distance growth rates.

arXiv:1303.1858•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2013•23 citations

Asymptotically regular LDPC codes with linear distance growth and thresholds close to capacity

Michael Lentmaier, David G. M. Mitchell, Gerhard Paul Fettweis +1 more

Families of asymptotically regular LDPC block code ensembles can be formed by terminating (J, K)-regular protograph-based LDPC convolutional codes. By varying the termination length, we obtain a large selection of LDPC block code ensembles with varying code rates and substantially better iterative decoding thresholds than those of (J, K)-regular LDPC block code ensembles, despite the fact that the terminated ensembles are almost regular. Also, by means of an asymptotic weight enumerator analysis, we show that minimum distance grows linearly with block length for all of the ensembles in these families, i.e., the ensembles are asymptotically good. We find that, as the termination length increases, families of ¿asymptotically regular¿ codes with capacity approaching iterative decoding thresholds and declining minimum distance growth rates are obtained, allowing a code designer to trade-off between distance growth rate and threshold. Further, we show that the thresholds and the distance growth rates can be improved by carefully choosing the component protographs used in the code construction.

arXiv:1005.1062•Information Theory and Applications Workshop (ITA)•Jan 1, 2010•35 citations

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•21 citations

Protograph based LDPC codes with minimum distance linearly growing with block size

D. Divsalar, C. Jones, Samuel J. Dolinar +1 more

We propose several LDPC code constructions that simultaneously achieve good threshold and error floor performance. Minimum distance is shown to grow linearly with block size (similar to regular codes of variable degree at least 3) by considering ensemble average weight enumerators. Our constructions are based on projected graph, or protograph, structures that support high-speed decoder implementations. As with irregular ensembles, our constructions are sensitive to the proportion of degree-2 variable nodes. A code with too few such nodes tends to have an iterative decoding threshold that is far from the capacity threshold. A code with too many such nodes tends to not exhibit a minimum distance that grows linearly in block length. In this paper we also show that preceding can be used to lower the threshold of regular LDPC codes. The decoding thresholds of the proposed codes, which have linearly increasing minimum distance in block size, outperform that of regular LDPC codes. Furthermore, a family of low to high rate codes, with thresholds that adhere closely to their respective channel capacity thresholds, is presented. Simulation results for a few example codes show that the proposed codes have low error floors as well as good threshold SNR performance.

Globecom•Jan 1, 2005•115 citations

Asymptotic Analysis of Spatially Coupled MacKay-Neal and Hsu-Anastasopoulos LDPC Codes

Daniel J. Costello, Michael Lentmaier, Kenta Kasai +1 more

MacKay-Neal (MN) and Hsu-Anastasopoulos (HA) low-density parity-check (LDPC) codes are known to achieve the capacity of memoryless binary-input symmetric-output channels under maximum likelihood (ML) decoding with bounded col- umn and row weight in their associated parity-check matrices. Recently, Kasai and Sakaniwa showed that spatially coupled (SC) versions of the MN and HA LDPC codes have belief propagation (BP) iterative decoding thresholds that approach capacity on the binary erasure channel (BEC) as the coupling length increases. In this paper, we extend the results of Kasai and Sakaniwa to the additive white Gaussian noise (AWGN) channel and show that the thresholds of the SC-MN and SC-HA ensembles approach capacity with bounded density as the coupling length increases, i.e., the number of edges per information bit approaches a finite value as the estimated BP threshold approaches the Shannon limit. We also perform an asymptotic weight enumerator analysis and show that, provided the density parameters are chosen to be sufficiently large, the SC-MN and SC-HA ensembles are asymptotically good. Further, for certain selections of parameters, some of these ensembles are shown to have both excellent thresholds and good distance properties. (Less)

•Jan 1, 2012•5 citations
In this paper, we construct protograph-based spatially coupled low-density parity-check (LDPC) codes by coupling together a series of L disjoint, or uncoupled, LDPC code Tanner graphs into a single coupled chain. By varying L , we obtain a flexible family of code ensembles with varying rates and frame lengths that can share the same encoding and decoding architecture for arbitrary L . We demonstrate that the resulting codes combine the best features of optimized irregular and regular codes in one design: capacity approaching iterative belief propagation (BP) decoding thresholds and linear growth of minimum distance with block length. In particular, we show that, for sufficiently large L , the BP thresholds on both the binary erasure channel and the binary-input additive white Gaussian noise channel saturate to a particular value significantly better than the BP decoding threshold and numerically indistinguishable from the optimal maximum a posteriori decoding threshold of the uncoupled LDPC code. When all variable nodes in the coupled chain have degree greater than two, asymptotically the error probability converges at least doubly exponentially with decoding iterations and we obtain sequences of asymptotically good LDPC codes with fast convergence rates and BP thresholds close to the Shannon limit. Further, the gap to capacity decreases as the density of the graph increases, opening up a new way to construct capacity achieving codes on memoryless binary-input symmetric-output channels with low-complexity BP decoding.
Spatially coupled low-density parity-check block codes (SC-LDPC-BCs) are a class of LDPC codes in which certain ensembles achieve capacity under iterative belief propagation decoding. Prior work has considered these codes mostly from a protograph perspective. Following this viewpoint, our work presents new protographs for the design of protograph-based SC-LDPC-BCs. A reciprocal channel approximation (RCA) analysis of the terminated protographs yields the asymptotic performance limits of the ensembles in terms of their iterative decoding thresholds. Our protographs possess the properties of linear minimum distance growth rate and excellent thresholds. We consider the following channels in our work: binary-input additive white Gaussian noise channel (BI-AWGNC), binary erasure channel (BEC), and binary symmetric channel (BSC). Our work focuses on obtaining good designs, with two classes of ensembles being asymptotically regular, for all the three channels while minimizing rate loss.
Families of generalized spatially-coupled low-density parity-check (GSC-LDPC) code ensembles can be formed by terminating protograph-based generalized LDPC convolutional (GLDPCC) codes. It has previously been shown that ensembles of GSC-LDPC codes constructed from a protograph have better iterative decoding thresholds than their block code counterparts, and that, for large termination lengths, their thresholds coincide with the maximum a-posteriori (MAP) decoding threshold of the underlying generalized LDPC block code ensemble. Here we show that, in addition to their excellent iterative decoding thresholds, ensembles of GSC-LDPC codes are asymptotically good and have large minimum distance growth rates.
Families of asymptotically regular LDPC block code ensembles can be formed by terminating (J, K)-regular protograph-based LDPC convolutional codes. By varying the termination length, we obtain a large selection of LDPC block code ensembles with varying code rates and substantially better iterative decoding thresholds than those of (J, K)-regular LDPC block code ensembles, despite the fact that the terminated ensembles are almost regular. Also, by means of an asymptotic weight enumerator analysis, we show that minimum distance grows linearly with block length for all of the ensembles in these families, i.e., the ensembles are asymptotically good. We find that, as the termination length increases, families of ¿asymptotically regular¿ codes with capacity approaching iterative decoding thresholds and declining minimum distance growth rates are obtained, allowing a code designer to trade-off between distance growth rate and threshold. Further, we show that the thresholds and the distance growth rates can be improved by carefully choosing the component protographs used in the code construction.
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.
We propose several LDPC code constructions that simultaneously achieve good threshold and error floor performance. Minimum distance is shown to grow linearly with block size (similar to regular codes of variable degree at least 3) by considering ensemble average weight enumerators. Our constructions are based on projected graph, or protograph, structures that support high-speed decoder implementations. As with irregular ensembles, our constructions are sensitive to the proportion of degree-2 variable nodes. A code with too few such nodes tends to have an iterative decoding threshold that is far from the capacity threshold. A code with too many such nodes tends to not exhibit a minimum distance that grows linearly in block length. In this paper we also show that preceding can be used to lower the threshold of regular LDPC codes. The decoding thresholds of the proposed codes, which have linearly increasing minimum distance in block size, outperform that of regular LDPC codes. Furthermore, a family of low to high rate codes, with thresholds that adhere closely to their respective channel capacity thresholds, is presented. Simulation results for a few example codes show that the proposed codes have low error floors as well as good threshold SNR performance.
MacKay-Neal (MN) and Hsu-Anastasopoulos (HA) low-density parity-check (LDPC) codes are known to achieve the capacity of memoryless binary-input symmetric-output channels under maximum likelihood (ML) decoding with bounded col- umn and row weight in their associated parity-check matrices. Recently, Kasai and Sakaniwa showed that spatially coupled (SC) versions of the MN and HA LDPC codes have belief propagation (BP) iterative decoding thresholds that approach capacity on the binary erasure channel (BEC) as the coupling length increases. In this paper, we extend the results of Kasai and Sakaniwa to the additive white Gaussian noise (AWGN) channel and show that the thresholds of the SC-MN and SC-HA ensembles approach capacity with bounded density as the coupling length increases, i.e., the number of edges per information bit approaches a finite value as the estimated BP threshold approaches the Shannon limit. We also perform an asymptotic weight enumerator analysis and show that, provided the density parameters are chosen to be sufficiently large, the SC-MN and SC-HA ensembles are asymptotically good. Further, for certain selections of parameters, some of these ensembles are shown to have both excellent thresholds and good distance properties. (Less)