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:1710.03619 · Allerton Conference on Communication, Control, and Computing

A generalized algebraic approach to optimizing SC-LDPC codes

Allison Beemer, Salman Habib, Christine A. Kelley, Jörg Kliewer

Published Oct 1, 2017• 24 citations
arXivHTMLPDF

Abstract

Spatially coupled low-density parity-check (SC-LDPC) codes are sparse graph codes that have recently become of interest due to their capacity-approaching performance on memoryless binary input channels. In this paper, we unify all existing SC-LDPC code construction methods under a new generalized description of SC-LDPC codes based on algebraic lifts of graphs. We present an improved low-complexity counting method for the special case of (3,3)-absorbing sets for array-based SC-LDPC codes, which we then use to optimize permutation assignments in SC-LDPC code construction. We show that codes constructed in this way are able to outperform previously published constructions, in terms of the number of dominant absorbing sets and with respect to both standard and windowed decoding.

DOI
10.1109/allerton.2017.8262802

Related papers

Design and Analysis of Graph-based Codes Using Algebraic Lifts and Decoding Networks

Allison Beemer

Error-correcting codes seek to address the problem of transmitting information efficiently and reliably across noisy channels. Among the most competitive codes developed in the last 70 years are low-density parity-check (LDPC) codes, a class of codes whose structure may be represented by sparse bipartite graphs. In addition to having the potential to be capacity-approaching, LDPC codes offer the significant practical advantage of low-complexity graph-based decoding algorithms. Graphical substructures called trapping sets, absorbing sets, and stopping sets characterize failure of these algorithms at high signal-to-noise ratios. This dissertation focuses on code design for and analysis of iterative graph-based message-passing decoders. The main contributions of this work include the following: the unification of spatially-coupled LDPC (SC-LDPC) code constructions under a single algebraic graph lift framework and the analysis of SC-LDPC code construction techniques from the perspective of removing harmful trapping and absorbing sets; analysis of the stopping and absorbing set parameters of hypergraph codes and finite geometry LDPC (FG-LDPC) codes; the introduction of multidimensional decoding networks that encode the behavior of hard-decision message-passing decoders; and the presentation of a novel Iteration Search Algorithm, a list decoder designed to improve the performance of hard-decision decoders. Adviser: Christine A. Kelley

•Jan 1, 2018•3 citations

Avoiding trapping sets in SC-LDPC codes under windowed decoding

Allison Beemer, Christine A. Kelley

Spatially coupled low-density parity-check (SC-LDPC) codes are sparse graph codes that have recently become of interest due to their capacity-approaching performance on memoryless binary input channels. Moreover, protograph SC-LDPC codes have been shown to be asymptotically good under certain conditions. SC-LDPC codes are amenable to a windowed decoder that allows decoding of blocks of bits to be done serially, making them good candidates for applications such as streaming. Depending on how they are constructed, however, the codes may still be prone to error floors. One key element in protograph SC-LDPC code design is the edge-spreading method used to couple copies of the base protograph in the construction of the SC-protograph. In this paper, we present an edge-spreading algorithm that is designed to remove trapping sets from the resulting SC-protograph that are harmful with respect to the windowed decoder, and we examine how to determine which trapping sets should be removed in the construction.

International Symposium on Information Theory and its Applications•Oct 1, 2016•12 citations

Optimized array-based spatially-coupled LDPC Codes: An absorbing set approach

Behzad Amiri, Amirhossein Reisizadeh, Jörg Kliewer +1 more

In the infinite blocklength regime, spatially-coupled LDPC codes are capable of achieving capacity-approaching performance under message-passing decoding. In the finite blocklength regime, it is known that absorbing sets compete with the codewords to be the output of sub-optimal message-passing decoders: the existence of such sets in the Tanner graph of LDPC codes causes performance degradation in the low error rate region. This paper presents a mathematical approach to finding the exact number of absorbing sets in array-based spatially-coupled (AB-SC) codes. Our analysis is universal in the sense that it is in principle applicable to absorbing sets of any size. Moreover, all design parameters of AB-SC codes such as the coupling length, the circulant size, and the cutting vector are considered in the presented count. Based on our analysis, we present an approach to find provably minimal cutting vectors, with respect to the number of absorbing sets, for the construction of AB-SC codes with various circulant sizes. Simulation results show the superior error floor performance of AB-SC codes with the minimal cutting vector compared to AB-SC codes with randomly-selected cutting vectors. We also provide the average number of non-binary absorbing sets in the Tanner graph of non-binary AB-SC codes constructed by uninformed (random) assignment of edge weights to a binary AB-SC code.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2015•13 citations

Absorbing set characterization of array-based spatially coupled LDPC codes

David G. M. Mitchell, Lara Dolecek, Daniel J. Costello

Absorbing sets are combinatorially defined objects existing in the Tanner graph of a low-density parity-check (LDPC) code that have been shown to cause failures in the iterative message-passing decoder when transmission occurs over the additive white Gaussian noise channel. In this paper, we study the absorbing set properties of a class of high-rate array-based spatially coupled LDPC (SC-LDPC) codes that are constructed by coupling together L array-based LDPC block codes. We prove that the smallest absorbing sets existing in the Tanner graph of the SC-LDPC code have the same size as those in the corresponding uncoupled LDPC codes, and the number of such sets grow linearly with L. We show that spatial coupling greatly reduces the average number (per symbol) of minimal sets compared to the uncoupled codes, and we explain that this reduction is due to many absorbing sets and small cycles being `broken' by the coupling process. The large reduction in the number of minimal absorbing sets suggests that array-based SC-LDPC codes will have significantly improved decoding performance in the high signal-to-noise ratio regime compared to the corresponding uncoupled LDPC codes.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2014•44 citations

Array-Based Spatially Coupled LDPC Codes Using Generalized Behrend Sequences

Suresh Kumar Venkataramanappa, Pavan Kumar, Deepak Mishra +1 more

We present a novel construction of quasi-cyclic (QC) low-density parity-check (LDPC) codes with arbitrary column weight and girth at least eight. Furthermore, we demonstrate that in the case of column weight three, the absorbing sets (3, 3) and (4, 2) can be entirely avoided in our construction, resulting in improved code performance. Building on the strong performance of our constructed QC-LDPC codes, we extend them to design several families of spatially coupled (SC) QC-LDPC codes, which further enhance decoding performance under windowed decoding. Simulation results under the additive white Gaussian noise (AWGN) channel demonstrate that the proposed QC-LDPC codes outperform the LDPC codes part of the space data systems standards. Additionally, we benchmark our proposed QC-LDPC and SC-QC-LDPC codes against existing girth-8 codes, observing significant improvements in the decoding performance of SC-QC-LDPC codes up to 1.1 dB compared to the protographbased construction by Shiyun Mo et al. [IEEE Trans. Commun.], while maintaining suitability for hardware implementation. The findings of this work contribute to the ongoing development of efficient LDPC codes suitable for ultra-reliable low-latency communications and area-efficient architecture designs.

•Jul 29, 2025•0 citations

Array-Based Spatially Coupled LDPC Codes Using Generalized Behrend Sequences

Suresh Kumar Venkataramanappa, Pavan Kumar, Deepak Mishra +1 more

We present a novel construction of quasi-cyclic (QC) low-density parity-check (LDPC) codes with arbitrary column weight and girth at least eight. Furthermore, we demonstrate that in the case of column weight three, the absorbing sets (3, 3) and (4, 2) can be entirely avoided in our construction, resulting in improved code performance. Building on the strong performance of our constructed QC-LDPC codes, we extend them to design several families of spatially coupled (SC) QC-LDPC codes, which further enhance decoding performance under windowed decoding. Simulation results under the additive white Gaussian noise (AWGN) channel demonstrate that the proposed QC-LDPC codes outperform the LDPC codes part of the space data systems standards. Additionally, we benchmark our proposed QC-LDPC and SC-QC-LDPC codes against existing girth-8 codes, observing significant improvements in the decoding performance of SC-QC-LDPC codes up to 1.1 dB compared to the protographbased construction by Shiyun Mo et al. [IEEE Trans. Commun.], while maintaining suitability for hardware implementation. The findings of this work contribute to the ongoing development of efficient LDPC codes suitable for ultra-reliable low-latency communications and area-efficient architecture designs.

•Oct 30, 2025•0 citations
Spatially coupled low-density parity-check (SC-LDPC) codes are sparse graph codes that have recently become of interest due to their capacity-approaching performance on memoryless binary input channels. In this paper, we unify all existing SC-LDPC code construction methods under a new generalized description of SC-LDPC codes based on algebraic lifts of graphs. We present an improved low-complexity counting method for the special case of (3,3)-absorbing sets for array-based SC-LDPC codes, which we then use to optimize permutation assignments in SC-LDPC code construction. We show that codes constructed in this way are able to outperform previously published constructions, in terms of the number of dominant absorbing sets and with respect to both standard and windowed decoding.
Error-correcting codes seek to address the problem of transmitting information efficiently and reliably across noisy channels. Among the most competitive codes developed in the last 70 years are low-density parity-check (LDPC) codes, a class of codes whose structure may be represented by sparse bipartite graphs. In addition to having the potential to be capacity-approaching, LDPC codes offer the significant practical advantage of low-complexity graph-based decoding algorithms. Graphical substructures called trapping sets, absorbing sets, and stopping sets characterize failure of these algorithms at high signal-to-noise ratios. This dissertation focuses on code design for and analysis of iterative graph-based message-passing decoders. The main contributions of this work include the following: the unification of spatially-coupled LDPC (SC-LDPC) code constructions under a single algebraic graph lift framework and the analysis of SC-LDPC code construction techniques from the perspective of removing harmful trapping and absorbing sets; analysis of the stopping and absorbing set parameters of hypergraph codes and finite geometry LDPC (FG-LDPC) codes; the introduction of multidimensional decoding networks that encode the behavior of hard-decision message-passing decoders; and the presentation of a novel Iteration Search Algorithm, a list decoder designed to improve the performance of hard-decision decoders. Adviser: Christine A. Kelley
Spatially coupled low-density parity-check (SC-LDPC) codes are sparse graph codes that have recently become of interest due to their capacity-approaching performance on memoryless binary input channels. Moreover, protograph SC-LDPC codes have been shown to be asymptotically good under certain conditions. SC-LDPC codes are amenable to a windowed decoder that allows decoding of blocks of bits to be done serially, making them good candidates for applications such as streaming. Depending on how they are constructed, however, the codes may still be prone to error floors. One key element in protograph SC-LDPC code design is the edge-spreading method used to couple copies of the base protograph in the construction of the SC-protograph. In this paper, we present an edge-spreading algorithm that is designed to remove trapping sets from the resulting SC-protograph that are harmful with respect to the windowed decoder, and we examine how to determine which trapping sets should be removed in the construction.
In the infinite blocklength regime, spatially-coupled LDPC codes are capable of achieving capacity-approaching performance under message-passing decoding. In the finite blocklength regime, it is known that absorbing sets compete with the codewords to be the output of sub-optimal message-passing decoders: the existence of such sets in the Tanner graph of LDPC codes causes performance degradation in the low error rate region. This paper presents a mathematical approach to finding the exact number of absorbing sets in array-based spatially-coupled (AB-SC) codes. Our analysis is universal in the sense that it is in principle applicable to absorbing sets of any size. Moreover, all design parameters of AB-SC codes such as the coupling length, the circulant size, and the cutting vector are considered in the presented count. Based on our analysis, we present an approach to find provably minimal cutting vectors, with respect to the number of absorbing sets, for the construction of AB-SC codes with various circulant sizes. Simulation results show the superior error floor performance of AB-SC codes with the minimal cutting vector compared to AB-SC codes with randomly-selected cutting vectors. We also provide the average number of non-binary absorbing sets in the Tanner graph of non-binary AB-SC codes constructed by uninformed (random) assignment of edge weights to a binary AB-SC code.
Absorbing sets are combinatorially defined objects existing in the Tanner graph of a low-density parity-check (LDPC) code that have been shown to cause failures in the iterative message-passing decoder when transmission occurs over the additive white Gaussian noise channel. In this paper, we study the absorbing set properties of a class of high-rate array-based spatially coupled LDPC (SC-LDPC) codes that are constructed by coupling together L array-based LDPC block codes. We prove that the smallest absorbing sets existing in the Tanner graph of the SC-LDPC code have the same size as those in the corresponding uncoupled LDPC codes, and the number of such sets grow linearly with L. We show that spatial coupling greatly reduces the average number (per symbol) of minimal sets compared to the uncoupled codes, and we explain that this reduction is due to many absorbing sets and small cycles being `broken' by the coupling process. The large reduction in the number of minimal absorbing sets suggests that array-based SC-LDPC codes will have significantly improved decoding performance in the high signal-to-noise ratio regime compared to the corresponding uncoupled LDPC codes.
We present a novel construction of quasi-cyclic (QC) low-density parity-check (LDPC) codes with arbitrary column weight and girth at least eight. Furthermore, we demonstrate that in the case of column weight three, the absorbing sets (3, 3) and (4, 2) can be entirely avoided in our construction, resulting in improved code performance. Building on the strong performance of our constructed QC-LDPC codes, we extend them to design several families of spatially coupled (SC) QC-LDPC codes, which further enhance decoding performance under windowed decoding. Simulation results under the additive white Gaussian noise (AWGN) channel demonstrate that the proposed QC-LDPC codes outperform the LDPC codes part of the space data systems standards. Additionally, we benchmark our proposed QC-LDPC and SC-QC-LDPC codes against existing girth-8 codes, observing significant improvements in the decoding performance of SC-QC-LDPC codes up to 1.1 dB compared to the protographbased construction by Shiyun Mo et al. [IEEE Trans. Commun.], while maintaining suitability for hardware implementation. The findings of this work contribute to the ongoing development of efficient LDPC codes suitable for ultra-reliable low-latency communications and area-efficient architecture designs.
We present a novel construction of quasi-cyclic (QC) low-density parity-check (LDPC) codes with arbitrary column weight and girth at least eight. Furthermore, we demonstrate that in the case of column weight three, the absorbing sets (3, 3) and (4, 2) can be entirely avoided in our construction, resulting in improved code performance. Building on the strong performance of our constructed QC-LDPC codes, we extend them to design several families of spatially coupled (SC) QC-LDPC codes, which further enhance decoding performance under windowed decoding. Simulation results under the additive white Gaussian noise (AWGN) channel demonstrate that the proposed QC-LDPC codes outperform the LDPC codes part of the space data systems standards. Additionally, we benchmark our proposed QC-LDPC and SC-QC-LDPC codes against existing girth-8 codes, observing significant improvements in the decoding performance of SC-QC-LDPC codes up to 1.1 dB compared to the protographbased construction by Shiyun Mo et al. [IEEE Trans. Commun.], while maintaining suitability for hardware implementation. The findings of this work contribute to the ongoing development of efficient LDPC codes suitable for ultra-reliable low-latency communications and area-efficient architecture designs.