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:1809.04253 · IEEE Information Theory Workshop (ITW)

Free Pseudodistance Growth Rates for Spatially Coupled LDPC Codes over the BEC

Cunlu Zhou, David G. M. Mitchell, Roxana Smarandache

Published Nov 1, 2018• 0 citations
arXivHTMLPDF

Abstract

The minimum pseudoweight is an important parameter related to the decoding performance of LDPC codes with iterative message-passing decoding. In this paper, we consider ensembles of periodically time-varying spatially coupled LDPC (SC-LDPC) codes and the pseudocodewords arising from their finite graph covers of a fixed degree. We show that for certain (J,K)-regular SC-LDPC code ensembles and a fixed cover degree, the typical minimum pseudoweight of the unterminated (and associated tail-biting/terminated) SC-LDPC code ensembles grows linearly with the constraint (block) length as the constraint (block) length tends to infinity. We prove that one can bound the the free pseudodistance growth rate over a BEC from below (respectively, above) using the associated tail-biting (terminated) SC-LDPC code ensemble and show empirically that these bounds coincide for a sufficiently large period, which gives the exact free pseudodistance growth rate for the SC-LDPC ensemble considered.

DOI
10.1109/itw.2018.8613507

Related papers

Asymptotic distance properties of protograph-based spatially coupled LDPC codes over GF(q)

Kechao Huang, David G. M. Mitchell, Xiao Ma +1 more

In this paper, asymptotic methods are used to form lower and upper bounds on the typical free distance growth rate of ensembles of periodically time-varying protograph-based spatially coupled low-density parity-check (SC-LDPC) codes over GF(q). By evaluating and comparing these bounds, we find that the typical free distance of q-ary SC-LDPC codes increases linearly with constraint length and that the bounds coincide for a sufficiently large period. In particular, we show that the free distance to constraint length ratio of (3, 6)-regular q-ary SC-LDPC code ensembles exceeds the minimum distance to block length ratio of an underlying q-ary LDPC block code (LDPC-BC) ensemble. We also show that, similar to the minimum distance growth rate of the (3, 6)-regular q-ary LDPC-BC ensemble, the free distance growth rate of (3, 6)-regular q-ary SC-LDPC code ensembles increases with the field size q up to a certain point, and then it decreases as q increases further.

IEEE Information Theory Workshop (ITW)•Apr 1, 2015•1 citation

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

Exact free distance and trapping set growth rates for LDPC convolutional codes

David G. M. Mitchell, Alí Emre Pusane, Michael Lentmaier +1 more

Ensembles of (J,K)-regular low-density parity-check convolutional (LDPCC) codes are known to be asymptotically good, in the sense that the minimum free distance grows linearly with the constraint length. In this paper, we use a protograph-based analysis of terminated LDPCC codes to obtain an upper bound on the free distance growth rate of ensembles of periodically time-varying LDPCC codes. This bound is compared to a lower bound and evaluated numerically. It is found that, for a sufficiently large period, the bounds coincide. This approach is then extended to obtain bounds on the trapping set numbers, which define the size of the smallest, non-empty trapping sets, for these asymptotically good, periodically time-varying LDPCC code ensembles.

arXiv:1106.1414•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2011•16 citations

Bounds on the Free Distance of Periodically Time-Varying SC-LDPC Codes

Massimo Battaglioni, Marco Baldi, Franco Chiaraluce

Time-invariant spatially coupled low-density parity-check (TI-SC-LDPC) codes can be obtained by unwrapping quasi-cyclic (QC) LDPC block codes. This results in a free distance that is lower bounded by the minimum distance of the underlying QC-LDPC block codes. By introducing some variability in the syndrome former matrix, time-varying (TV) SC-LDPC codes are obtained, which trade an improved error correction performance for an increased decoding memory requirement and decoding complexity. A family of codes able to combine the advantages of TI-SC-LDPC codes with those of TV-SC-LDPC codes is that of periodically time-varying (PTV) SC-LDPC codes, based on a finite and periodic variation of the syndrome former matrix. In this paper we focus on such codes, and derive new upper bounds on the free distance of PTV-SC-LDPC code ensembles as well as on specific codes. By using these bounds, we show that PTV-SC-LDPC codes can achieve important improvements in the free distance over TI-SC-LDPC codes even using a very small period of variability, which corresponds to a minimal increase in memory and complexity. We also validate the new upper bounds through numerical experiments and assess the error correction performance of the corresponding codes through Monte Carlo simulations.

IEEE Transactions on Information Theory•Feb 5, 2024•4 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•40 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
The minimum pseudoweight is an important parameter related to the decoding performance of LDPC codes with iterative message-passing decoding. In this paper, we consider ensembles of periodically time-varying spatially coupled LDPC (SC-LDPC) codes and the pseudocodewords arising from their finite graph covers of a fixed degree. We show that for certain (J,K)-regular SC-LDPC code ensembles and a fixed cover degree, the typical minimum pseudoweight of the unterminated (and associated tail-biting/terminated) SC-LDPC code ensembles grows linearly with the constraint (block) length as the constraint (block) length tends to infinity. We prove that one can bound the the free pseudodistance growth rate over a BEC from below (respectively, above) using the associated tail-biting (terminated) SC-LDPC code ensemble and show empirically that these bounds coincide for a sufficiently large period, which gives the exact free pseudodistance growth rate for the SC-LDPC ensemble considered.
In this paper, asymptotic methods are used to form lower and upper bounds on the typical free distance growth rate of ensembles of periodically time-varying protograph-based spatially coupled low-density parity-check (SC-LDPC) codes over GF(q). By evaluating and comparing these bounds, we find that the typical free distance of q-ary SC-LDPC codes increases linearly with constraint length and that the bounds coincide for a sufficiently large period. In particular, we show that the free distance to constraint length ratio of (3, 6)-regular q-ary SC-LDPC code ensembles exceeds the minimum distance to block length ratio of an underlying q-ary LDPC block code (LDPC-BC) ensemble. We also show that, similar to the minimum distance growth rate of the (3, 6)-regular q-ary LDPC-BC ensemble, the free distance growth rate of (3, 6)-regular q-ary SC-LDPC code ensembles increases with the field size q up to a certain point, and then it decreases as q increases further.
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.
Ensembles of (J,K)-regular low-density parity-check convolutional (LDPCC) codes are known to be asymptotically good, in the sense that the minimum free distance grows linearly with the constraint length. In this paper, we use a protograph-based analysis of terminated LDPCC codes to obtain an upper bound on the free distance growth rate of ensembles of periodically time-varying LDPCC codes. This bound is compared to a lower bound and evaluated numerically. It is found that, for a sufficiently large period, the bounds coincide. This approach is then extended to obtain bounds on the trapping set numbers, which define the size of the smallest, non-empty trapping sets, for these asymptotically good, periodically time-varying LDPCC code ensembles.
Time-invariant spatially coupled low-density parity-check (TI-SC-LDPC) codes can be obtained by unwrapping quasi-cyclic (QC) LDPC block codes. This results in a free distance that is lower bounded by the minimum distance of the underlying QC-LDPC block codes. By introducing some variability in the syndrome former matrix, time-varying (TV) SC-LDPC codes are obtained, which trade an improved error correction performance for an increased decoding memory requirement and decoding complexity. A family of codes able to combine the advantages of TI-SC-LDPC codes with those of TV-SC-LDPC codes is that of periodically time-varying (PTV) SC-LDPC codes, based on a finite and periodic variation of the syndrome former matrix. In this paper we focus on such codes, and derive new upper bounds on the free distance of PTV-SC-LDPC code ensembles as well as on specific codes. By using these bounds, we show that PTV-SC-LDPC codes can achieve important improvements in the free distance over TI-SC-LDPC codes even using a very small period of variability, which corresponds to a minimal increase in memory and complexity. We also validate the new upper bounds through numerical experiments and assess the error correction performance of the corresponding codes through Monte Carlo simulations.
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.
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.