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:1904.07158

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

Massimo Battaglioni, Franco Chiaraluce, Marco Baldi, David G. M. Mitchell

Published Apr 15, 2019• 3 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1904.07158

Related papers

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

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

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

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

Construction of Irregular Protograph-Based QC-LDPC Codes With Low Error Floor

Bashirreza Karimi, Amir H. Banihashemi

In this article, we design finite-length irregular protograph-based quasi-cyclic (QC) low-density parity-check (LDPC) codes with good waterfall performance and low error floor. To achieve a low error floor, we eliminate a targeted set of dominant elementary trapping sets (ETS) £ in the Tanner graph of the code. For a given rate and girth, the codes are designed to be free of the largest set of problematic ETSs for a given block length, or to have the shortest block length while a given set of ETSs is avoided. The design is based on a search algorithm that identifies whether any instance of any structure within £ exists in the Tanner graph of the constructed code or not. The search algorithm performs this task with minimal complexity, making it feasible to construct practical codes by running the search algorithm a large number of times. Simulation results are provided to demonstrate the superior performance of designed codes compared to similar state-of-the-art irregular QC-LDPC codes.

IEEE Transactions on Communications•Oct 2, 2020•18 citations
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.
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.
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.
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.
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 (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.
In this article, we design finite-length irregular protograph-based quasi-cyclic (QC) low-density parity-check (LDPC) codes with good waterfall performance and low error floor. To achieve a low error floor, we eliminate a targeted set of dominant elementary trapping sets (ETS) £ in the Tanner graph of the code. For a given rate and girth, the codes are designed to be free of the largest set of problematic ETSs for a given block length, or to have the shortest block length while a given set of ETSs is avoided. The design is based on a search algorithm that identifies whether any instance of any structure within £ exists in the Tanner graph of the constructed code or not. The search algorithm performs this task with minimal complexity, making it feasible to construct practical codes by running the search algorithm a large number of times. Simulation results are provided to demonstrate the superior performance of designed codes compared to similar state-of-the-art irregular QC-LDPC codes.