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

International Symposium on Information Theory and its Applications

Avoiding trapping sets in SC-LDPC codes under windowed decoding

Allison Beemer, Christine A. Kelley

Published Oct 1, 2016• 12 citations
OpenAlex

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. 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.

Related papers

A protograph-based design of quasi-cyclic spatially coupled LDPC codes

Li Chen, Shiyuan Mo, Daniel J. Costello +2 more

Spatially coupled (SC) low-density parity-check (LDPC) codes can achieve capacity approaching performance with low message recovery latency when using sliding window (SW) decoding. An SC-LDPC code constructed from a protograph can be generated by first coupling a chain of block protographs and then lifting the coupled protograph using permutation matrices. This paper introduces a systematic design of SC-LDPC codes to eliminate 4-cycles in the coupled photograph. Using a quasi-cyclic (QC) lifting, we obtain QC-SC-LDPC codes of girth at least eight. Coupling a chain of block protographs implies spreading edges from one protograph to the others. Our protograph-based design can be viewed as guiding the edge spreading and also the graph-lifting process. Simulation results show the design leads to improved decoding performance, particularly in the error floor, compared to random designs.

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

Efficient Search and Elimination of Harmful Objects in Optimized QC SC-LDPC Codes

Massimo Battaglioni, Franco Chiaraluce, Marco Baldi +1 more

The error correction performance of low-density parity-check (LDPC) codes under iterative message-passing decoding is degraded by the presence of certain harmful objects existing in their Tanner graph representation. Depending on the context, such harmful objects are known as stopping sets, trapping sets, absorbing sets, or pseudocodewords. In this paper, we propose a general procedure based on edge spreading that enables the design of quasi-cyclic (QC) spatially coupled low-density parity-check codes (SC-LDPCCs) that are derived from QC-LDPC block codes and possess a significantly reduced multiplicity of harmful objects with respect to the original QC-LDPC block code. This procedure relies on a novel algorithm that greedily spans the search space of potential candidates to reduce the multiplicity of the target harmful object(s) in the Tanner graph. The effectiveness of the method we propose is validated via examples and numerical computer simulations.

arXiv:1904.07158•Apr 15, 2019•3 citations

Optimizing quasi-cyclic spatially coupled LDPC codes by eliminating harmful objects

Massimo Battaglioni, Franco Chiaraluce, Marco Baldi +2 more

Abstract It is well known that some harmful objects in the Tanner graph of low-density parity-check (LDPC) codes have a negative impact on their error correction performance under iterative message-passing decoding. Depending on the channel and the decoding algorithm, these harmful objects are different in nature and can be stopping sets, trapping sets, absorbing sets, or pseudocodewords. Differently from LDPC block codes, the design of spatially coupled LDPC codes must take into account the semi-infinite nature of the code, while still reducing the number of harmful objects as much as possible. We propose a general procedure, based on edge spreading, enabling the design of good quasi-cyclic spatially coupled LDPC (QC-SC-LDPC) codes. These codes are derived from quasi-cyclic LDPC (QC-LDPC) block codes and contain a considerably reduced number of harmful objects with respect to the original QC-LDPC block codes. We use an efficient way of enumerating harmful objects in QC-SC-LDPCCs to obtain a fast algorithm that spans the search space of potential candidates to select those minimizing the multiplicity of the target harmful objects. We validate the effectiveness of our method via numerical simulations, showing that the newly designed codes achieve better error rate performance than codes presented in previous literature.

EURASIP Journal on Wireless Communications and Networking•Jul 25, 2023•5 citations

Efficient Search and Elimination of Harmful Objects for the Optimization of QC-SC-LDPC Codes

Massimo Battaglioni, Franco Chiaraluce, Marco Baldi +1 more

The error correction performance of low-density parity-check codes under iterative message-passing decoding is degraded by the presence of certain harmful objects existing in their Tanner graph representation. Depending on the context, such harmful objects are known as stopping sets, trapping sets, absorbing sets, or pseudocodewords. In this paper, we propose a general procedure, based on edge spreading, that enables the design of good quasi-cyclic spatially coupled low-density parity-check codes. These codes are derived from quasi-cyclic low-density parity-check (QC-LDPC) block codes and possess a significantly reduced multiplicity of harmful objects with respect to the original QC-LDPC block codes. The proposed procedure relies on a novel algorithm that greedily spans the search space of potential candidates to reduce the multiplicity of the target harmful objects. The effectiveness of the method is validated via examples and numerical computer simulations.

Globecom•Dec 1, 2019•7 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

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
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.
Spatially coupled (SC) low-density parity-check (LDPC) codes can achieve capacity approaching performance with low message recovery latency when using sliding window (SW) decoding. An SC-LDPC code constructed from a protograph can be generated by first coupling a chain of block protographs and then lifting the coupled protograph using permutation matrices. This paper introduces a systematic design of SC-LDPC codes to eliminate 4-cycles in the coupled photograph. Using a quasi-cyclic (QC) lifting, we obtain QC-SC-LDPC codes of girth at least eight. Coupling a chain of block protographs implies spreading edges from one protograph to the others. Our protograph-based design can be viewed as guiding the edge spreading and also the graph-lifting process. Simulation results show the design leads to improved decoding performance, particularly in the error floor, compared to random designs.
The error correction performance of low-density parity-check (LDPC) codes under iterative message-passing decoding is degraded by the presence of certain harmful objects existing in their Tanner graph representation. Depending on the context, such harmful objects are known as stopping sets, trapping sets, absorbing sets, or pseudocodewords. In this paper, we propose a general procedure based on edge spreading that enables the design of quasi-cyclic (QC) spatially coupled low-density parity-check codes (SC-LDPCCs) that are derived from QC-LDPC block codes and possess a significantly reduced multiplicity of harmful objects with respect to the original QC-LDPC block code. This procedure relies on a novel algorithm that greedily spans the search space of potential candidates to reduce the multiplicity of the target harmful object(s) in the Tanner graph. The effectiveness of the method we propose is validated via examples and numerical computer simulations.
Abstract It is well known that some harmful objects in the Tanner graph of low-density parity-check (LDPC) codes have a negative impact on their error correction performance under iterative message-passing decoding. Depending on the channel and the decoding algorithm, these harmful objects are different in nature and can be stopping sets, trapping sets, absorbing sets, or pseudocodewords. Differently from LDPC block codes, the design of spatially coupled LDPC codes must take into account the semi-infinite nature of the code, while still reducing the number of harmful objects as much as possible. We propose a general procedure, based on edge spreading, enabling the design of good quasi-cyclic spatially coupled LDPC (QC-SC-LDPC) codes. These codes are derived from quasi-cyclic LDPC (QC-LDPC) block codes and contain a considerably reduced number of harmful objects with respect to the original QC-LDPC block codes. We use an efficient way of enumerating harmful objects in QC-SC-LDPCCs to obtain a fast algorithm that spans the search space of potential candidates to select those minimizing the multiplicity of the target harmful objects. We validate the effectiveness of our method via numerical simulations, showing that the newly designed codes achieve better error rate performance than codes presented in previous literature.
The error correction performance of low-density parity-check codes under iterative message-passing decoding is degraded by the presence of certain harmful objects existing in their Tanner graph representation. Depending on the context, such harmful objects are known as stopping sets, trapping sets, absorbing sets, or pseudocodewords. In this paper, we propose a general procedure, based on edge spreading, that enables the design of good quasi-cyclic spatially coupled low-density parity-check codes. These codes are derived from quasi-cyclic low-density parity-check (QC-LDPC) block codes and possess a significantly reduced multiplicity of harmful objects with respect to the original QC-LDPC block codes. The proposed procedure relies on a novel algorithm that greedily spans the search space of potential candidates to reduce the multiplicity of the target harmful objects. The effectiveness of the method is validated via examples and numerical computer simulations.
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.
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.