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)

Absorbing set characterization of array-based spatially coupled LDPC codes

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

Published Jun 1, 2014• 44 citations
Publisher

Abstract

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.

DOI
10.1109/isit.2014.6874960

Related papers

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

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

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

Analysis of Absorbing Sets for Array-Based LDPC Codes

Lara Dolecek, Zhengya Zhang, Venkat Anantharam +2 more

Low density parity check codes (LDPC) are known to perform very well under iterative decoding. However, these codes also exhibit a change in the slope of the bit error rate (BER) vs. signal to noise ratio (SNR) curve in the very low BER region. In our earlier work using hardware emulation in this deep BER regime we argue that this behavior can be attributed to specific structures within the Tanner graph associated with an LDPC code, called absorbing sets. In this paper we provide a detailed theoretical analysis of absorbing sets for array-based LDPC codes Cp.gamma. Specifically, we identify and enumerate all the smallest absorbing sets for these array-based LDPC codes with gamma = 2,3,4 with standard parity check matrix. Experiments carried out on the emulation platform show excellent agreement with our theoretical results.

International Conference on Communications•Jun 1, 2007•96 citations

Extremal absorbing sets in low-density parity-check codes

Emily McMillon, Allison Beemer, Christine A. Kelley

Absorbing sets are combinatorial structures in the Tanner graphs of low-density parity-check (LDPC) codes that have been shown to inhibit the high signal-to-noise ratio performance of iterative decoders over many communication channels. Absorbing sets of minimum size are the most likely to cause errors, and thus have been the focus of much research. In this paper, we determine the sizes of absorbing sets that can occur in general and left-regular LDPC code graphs, with emphasis on the range of $ b $ for a given $ a $ for which an $ (a,b) $-absorbing set may exist. We identify certain cases of extremal absorbing sets that are elementary, a particularly harmful class of absorbing sets, and also introduce the notion of minimal absorbing sets which will help in designing absorbing set removal algorithms.

Advances in Mathematics of Communications•Apr 7, 2021•3 citations
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.
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.
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.
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.
Low density parity check codes (LDPC) are known to perform very well under iterative decoding. However, these codes also exhibit a change in the slope of the bit error rate (BER) vs. signal to noise ratio (SNR) curve in the very low BER region. In our earlier work using hardware emulation in this deep BER regime we argue that this behavior can be attributed to specific structures within the Tanner graph associated with an LDPC code, called absorbing sets. In this paper we provide a detailed theoretical analysis of absorbing sets for array-based LDPC codes Cp.gamma. Specifically, we identify and enumerate all the smallest absorbing sets for these array-based LDPC codes with gamma = 2,3,4 with standard parity check matrix. Experiments carried out on the emulation platform show excellent agreement with our theoretical results.
Absorbing sets are combinatorial structures in the Tanner graphs of low-density parity-check (LDPC) codes that have been shown to inhibit the high signal-to-noise ratio performance of iterative decoders over many communication channels. Absorbing sets of minimum size are the most likely to cause errors, and thus have been the focus of much research. In this paper, we determine the sizes of absorbing sets that can occur in general and left-regular LDPC code graphs, with emphasis on the range of $ b $ for a given $ a $ for which an $ (a,b) $-absorbing set may exist. We identify certain cases of extremal absorbing sets that are elementary, a particularly harmful class of absorbing sets, and also introduce the notion of minimal absorbing sets which will help in designing absorbing set removal algorithms.