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

IEEE Transactions on Information Theory

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

Massimo Battaglioni, Marco Baldi, Franco Chiaraluce

Published Feb 5, 2024• 4 citations
Publisher

Abstract

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.

DOI
10.1109/tit.2024.3362387

Related papers

Time-invariant spatially coupled low-density parity-check codes with small constraint length

Marco Baldi, Massimo Battaglioni, Franco Chiaraluce +1 more

We consider a special family of spatially coupled low-density parity-check (SC-LDPC) codes, that is, time-invariant low-density parity-check convolutional (LDPCC) codes, which are known in the literature for a long time. Codes of this kind are usually designed by starting from quasi-cyclic (QC) block codes, and applying suitable unwrapping procedures. We show that, by directly designing the LDPCC code syndrome former matrix without the constraints of the underlying QC block code, it is possible to achieve smaller constraint lengths with respect to the best solutions available in the literature. We also find theoretical lower bounds on the syndrome former constraint length for codes with a specified minimum length of the local cycles in their Tanner graphs. For this purpose, we exploit a new approach based on a numerical representation of the syndrome former matrix, which generalizes over a technique we already used to study a special subclass of the codes here considered.

arXiv:1605.05560•IEEE International Black Sea Conference on Communications and Networking•Jan 1, 2016•4 citations

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

Spatially coupled quasi-cyclic quantum LDPC codes

Manabu Hagiwara, Kenta Kasai, Hideki Imai +1 more

For designing low-density parity-check (LDPC) codes for quantum error-correction, we desire to satisfy the conflicting requirements below simultaneously. 1) The row weights of parity-check “should be large”: The minimum distances are bounded above by the minimum row weights of parity-check matrices of constituent classical codes. Small minimum distance tends to result in poor decoding performance at the error-floor region. 2) The row weights of parity-check matrices “should not be large”: The performance of the sum-product decoding algorithm at the water-fall region is degraded as the row weight increases. Recently, Kudekar et al. showed spatially-coupled (SC) LDPC codes exhibit capacity-achieving performance for classical channels. SC LDPC codes have both large row weight and capacity-achieving error-floor and water-fall performance. In this paper, we propose a new class of quantum LDPC codes based on spatially coupled quasi-cyclic LDPC codes. The performance outperforms that of quantum “non-coupled” quasi-cyclic LDPC codes.

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

Finite-Length Algebraic Spatially-Coupled Quasi-Cyclic LDPC Codes

Keke Liu, Mostafa El‐Khamy, Jungwon Lee

The replicate-and-mask (R&M) construction of finite-length spatially-coupled (SC) LDPC codes is proposed in this paper. The proposed R&M construction generalizes the conventional matrix unwrapping construction and contains it as a special case. The R&M construction of a class of algebraic spatially coupled (SC) quasi-cyclic (QC) LDPC codes over arbitrary finite fields is demonstrated. The girth, rank, and time-varying periodicity of the proposed R&M SC QC LDPC codes are analyzed. The error rate performance of finite-length nonbinary algebraic SC QC LDPC codes is investigated with window decoding. Compared to the conventional unwrapping construction, it is found through numerical simulations that the R&M construction resulted in SC QC LDPC codes with better block error rate performance and lower error floors. With a flooding schedule decoder, it is shown that the proposed R&M algebraic SC QC LDPC codes have better error performance than the corresponding LDPC block codes and random SC codes. The R&M construction of irregular SC QC LDPC codes is demonstrated. It is shown that low-complexity regular puncturing schemes can be deployed on these codes to construct families of rate-compatible irregular SC QC LDPC codes with good performance.

IEEE Journal on Selected Areas in Communications•Dec 4, 2015•31 citations

Design of Protograph-Based Quasi-Cyclic Spatially Coupled Ldpc Codes

Shuoshuo Wang, Zhanji Wu, Qihao Wu

In this paper, we deal with time-varing quasi-cyclic (QC) spatially-coupled (SC) low-density parity-check (LDPC) codes by lifting the coupled protographs. The construction method of girth-6 protographs for any code rate is proposed. We provide a theoretical lower bound on the syndrome former constraint length under condition of the protographs without 4-cycles in their Tanner graphs. Then we use periodic QC lifting method to search the QC-SC-LDPC matrices with larger girth based on the protographs. The minimum dimension size of QC-SC-LDPC codes is given to count the girth of QC-SC-LDPC codes with a semi- infinite binary-check matrix structure. The performance of such constructed codes with lower complexity and delay is superior to the LDPC block codes.

IEEE Wireless Communications and Networking Conference Workshops (WCNCW)•Apr 1, 2020•2 citations

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

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

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.

arXiv:1809.04253•IEEE Information Theory Workshop (ITW)•Nov 1, 2018•0 citations
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.
We consider a special family of spatially coupled low-density parity-check (SC-LDPC) codes, that is, time-invariant low-density parity-check convolutional (LDPCC) codes, which are known in the literature for a long time. Codes of this kind are usually designed by starting from quasi-cyclic (QC) block codes, and applying suitable unwrapping procedures. We show that, by directly designing the LDPCC code syndrome former matrix without the constraints of the underlying QC block code, it is possible to achieve smaller constraint lengths with respect to the best solutions available in the literature. We also find theoretical lower bounds on the syndrome former constraint length for codes with a specified minimum length of the local cycles in their Tanner graphs. For this purpose, we exploit a new approach based on a numerical representation of the syndrome former matrix, which generalizes over a technique we already used to study a special subclass of the codes here 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.
For designing low-density parity-check (LDPC) codes for quantum error-correction, we desire to satisfy the conflicting requirements below simultaneously. 1) The row weights of parity-check “should be large”: The minimum distances are bounded above by the minimum row weights of parity-check matrices of constituent classical codes. Small minimum distance tends to result in poor decoding performance at the error-floor region. 2) The row weights of parity-check matrices “should not be large”: The performance of the sum-product decoding algorithm at the water-fall region is degraded as the row weight increases. Recently, Kudekar et al. showed spatially-coupled (SC) LDPC codes exhibit capacity-achieving performance for classical channels. SC LDPC codes have both large row weight and capacity-achieving error-floor and water-fall performance. In this paper, we propose a new class of quantum LDPC codes based on spatially coupled quasi-cyclic LDPC codes. The performance outperforms that of quantum “non-coupled” quasi-cyclic LDPC codes.
The replicate-and-mask (R&M) construction of finite-length spatially-coupled (SC) LDPC codes is proposed in this paper. The proposed R&M construction generalizes the conventional matrix unwrapping construction and contains it as a special case. The R&M construction of a class of algebraic spatially coupled (SC) quasi-cyclic (QC) LDPC codes over arbitrary finite fields is demonstrated. The girth, rank, and time-varying periodicity of the proposed R&M SC QC LDPC codes are analyzed. The error rate performance of finite-length nonbinary algebraic SC QC LDPC codes is investigated with window decoding. Compared to the conventional unwrapping construction, it is found through numerical simulations that the R&M construction resulted in SC QC LDPC codes with better block error rate performance and lower error floors. With a flooding schedule decoder, it is shown that the proposed R&M algebraic SC QC LDPC codes have better error performance than the corresponding LDPC block codes and random SC codes. The R&M construction of irregular SC QC LDPC codes is demonstrated. It is shown that low-complexity regular puncturing schemes can be deployed on these codes to construct families of rate-compatible irregular SC QC LDPC codes with good performance.
In this paper, we deal with time-varing quasi-cyclic (QC) spatially-coupled (SC) low-density parity-check (LDPC) codes by lifting the coupled protographs. The construction method of girth-6 protographs for any code rate is proposed. We provide a theoretical lower bound on the syndrome former constraint length under condition of the protographs without 4-cycles in their Tanner graphs. Then we use periodic QC lifting method to search the QC-SC-LDPC matrices with larger girth based on the protographs. The minimum dimension size of QC-SC-LDPC codes is given to count the girth of QC-SC-LDPC codes with a semi- infinite binary-check matrix structure. The performance of such constructed codes with lower complexity and delay is superior to the LDPC block codes.
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.