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 International Symposium on Information Theory (ISIT)

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

Behzad Amiri, Amirhossein Reisizadeh, Jörg Kliewer, Lara Dolecek

Published Jun 1, 2015• 13 citations
Publisher

Abstract

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.

DOI
10.1109/isit.2015.7282415

Related papers

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

Optimized Design of Finite-Length Separable Circulant-Based Spatially-Coupled Codes: An Absorbing Set-Based Analysis

Behzad Amiri, Amirhossein Reisizadehmobarakeh, Homa Esfahanizadeh +2 more

In this paper, we characterize the finite-length performance of separable circulant-based spatially-coupled (SCB-SC) LDPC codes for transmission over the additive white Gaussian noise channel. For a general class of finite-length graph-based codes, it is known that the existence of small absorbing sets causes a performance degradation in the error floor regime. We first present the mathematical conditions for the existence of absorbing sets in binary SCB-SC codes. This analysis enables us to find the exact number of absorbing sets as a function of the design parameters. In particular, our results show that the choice of the cutting vector affects the number of absorbing sets and, therefore, the error floor performance of the code. For a fixed column weight, we find provably optimal cutting vectors that result in the least number of absorbing sets. Furthermore, we extend our analysis to nonbinary SCB-SC codes, where we show that the choice of the cutting vector is not as critical as in the binary case. We provide an algorithm which provably removes the problematic nonbinary absorbing sets from nonbinary SCB-SC codes by informed selection of edge labels. Our simulation results show the superior error floor performance of our designed binary and nonbinary SCB-SC codes compared with binary unstructured and nonbinary quasi-cyclic SC codes available in the open literature.

IEEE Transactions on Communications•Jan 1, 2016•21 citations

Edge spreading design of high rate array-based SC-LDPC codes

David G. M. Mitchell, Eirik Rosnes

Absorbing sets (ASs) 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 propose an edge spreading approach to construct high rate array-based spatially-coupled LDPC codes by jointly optimizing the AS spectrum and the minimum distance. By considering general edge spreadings and by considering a larger memory, we show that strictly better codes can be constructed, both in terms of achievable minimum distance for small-to-moderate block lengths and in terms of the number of small ASs.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2017•27 citations

A generalized algebraic approach to optimizing SC-LDPC codes

Allison Beemer, Salman Habib, Christine A. Kelley +1 more

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.

arXiv:1710.03619•Allerton Conference on Communication, Control, and Computing•Oct 1, 2017•24 citations

Analysis of Absorbing Sets and Fully Absorbing Sets of Array-Based LDPC Codes

Lara Dolecek, Zhengya Zhang, Venkat Anantharam +2 more

The class of low-density parity-check (LDPC) codes is attractive, since such codes can be decoded using practical message-passing algorithms, and their performance is known to approach the Shannon limits for suitably large block lengths. For the intermediate block lengths relevant in applications, however, many LDPC codes exhibit a so-called “error floor,” corresponding to a significant flattening in the curve that relates signal-to-noise ratio (SNR) to the bit-error rate (BER) level. Previous work has linked this behavior to combinatorial substructures within the Tanner graph associated with an LDPC code, known as (fully) absorbing sets. These fully absorbing sets correspond to a particular type of near-codewords or trapping sets that are stable under bit-flipping operations, and exert the dominant effect on the low BER behavior of structured LDPC codes. This paper provides a detailed theoretical analysis of these (fully) absorbing sets for the class of$C_{p, \gamma}$array-based LDPC codes, including the characterization of all minimal (fully) absorbing sets for the array-based LDPC codes for$\gamma = 2,3,4$, and moreover, it provides the development of techniques to enumerate them exactly. Theoretical results of this type provide a foundation for predicting and extrapolating the error floor behavior of LDPC codes.

IEEE Transactions on Information Theory•Jan 1, 2010•207 citations

Performance Bounds for Quantized Spatially Coupled LDPC Decoders Based on Absorbing Sets

Homayoon Hatami, David G. M. Mitchell, Daniel J. Costello +1 more

Absorbing sets are known to be the primary factor in the error-floor performance of low-density parity-check (LDPC) codes with message passing decoders over the additive white Gaussian noise (AWGN) channel. Besides showing excellent waterfall performance, spatially coupled LDPC (SC-LDPC) codes that are constructed by an edge spreading technique are known to have fewer cycles and absorbing sets than their block code counterparts, and therefore to exhibit better error-floor performance. Based on our previously obtained results for quantized LDPC block decoders, we derive lower bounds on the performance of quantized SC-LDPC decoders, including both a flooding schedule decoder and a sliding window decoder. Numerical simulation results confirm the accuracy of the obtained bounds and show that, for quantized decoders, properly designed SC-LDPC codes have better error-floor performance than their underlying LDPC block codes.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2018•7 citations
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.
In this paper, we characterize the finite-length performance of separable circulant-based spatially-coupled (SCB-SC) LDPC codes for transmission over the additive white Gaussian noise channel. For a general class of finite-length graph-based codes, it is known that the existence of small absorbing sets causes a performance degradation in the error floor regime. We first present the mathematical conditions for the existence of absorbing sets in binary SCB-SC codes. This analysis enables us to find the exact number of absorbing sets as a function of the design parameters. In particular, our results show that the choice of the cutting vector affects the number of absorbing sets and, therefore, the error floor performance of the code. For a fixed column weight, we find provably optimal cutting vectors that result in the least number of absorbing sets. Furthermore, we extend our analysis to nonbinary SCB-SC codes, where we show that the choice of the cutting vector is not as critical as in the binary case. We provide an algorithm which provably removes the problematic nonbinary absorbing sets from nonbinary SCB-SC codes by informed selection of edge labels. Our simulation results show the superior error floor performance of our designed binary and nonbinary SCB-SC codes compared with binary unstructured and nonbinary quasi-cyclic SC codes available in the open literature.
Absorbing sets (ASs) 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 propose an edge spreading approach to construct high rate array-based spatially-coupled LDPC codes by jointly optimizing the AS spectrum and the minimum distance. By considering general edge spreadings and by considering a larger memory, we show that strictly better codes can be constructed, both in terms of achievable minimum distance for small-to-moderate block lengths and in terms of the number of small ASs.
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.
The class of low-density parity-check (LDPC) codes is attractive, since such codes can be decoded using practical message-passing algorithms, and their performance is known to approach the Shannon limits for suitably large block lengths. For the intermediate block lengths relevant in applications, however, many LDPC codes exhibit a so-called “error floor,” corresponding to a significant flattening in the curve that relates signal-to-noise ratio (SNR) to the bit-error rate (BER) level. Previous work has linked this behavior to combinatorial substructures within the Tanner graph associated with an LDPC code, known as (fully) absorbing sets. These fully absorbing sets correspond to a particular type of near-codewords or trapping sets that are stable under bit-flipping operations, and exert the dominant effect on the low BER behavior of structured LDPC codes. This paper provides a detailed theoretical analysis of these (fully) absorbing sets for the class ofCp,γC_{p, \gamma}Cp,γ​array-based LDPC codes, including the characterization of all minimal (fully) absorbing sets for the array-based LDPC codes forγ=2,3,4\gamma = 2,3,4γ=2,3,4, and moreover, it provides the development of techniques to enumerate them exactly. Theoretical results of this type provide a foundation for predicting and extrapolating the error floor behavior of LDPC codes.
Absorbing sets are known to be the primary factor in the error-floor performance of low-density parity-check (LDPC) codes with message passing decoders over the additive white Gaussian noise (AWGN) channel. Besides showing excellent waterfall performance, spatially coupled LDPC (SC-LDPC) codes that are constructed by an edge spreading technique are known to have fewer cycles and absorbing sets than their block code counterparts, and therefore to exhibit better error-floor performance. Based on our previously obtained results for quantized LDPC block decoders, we derive lower bounds on the performance of quantized SC-LDPC decoders, including both a flooding schedule decoder and a sliding window decoder. Numerical simulation results confirm the accuracy of the obtained bounds and show that, for quantized decoders, properly designed SC-LDPC codes have better error-floor performance than their underlying LDPC block codes.